1 cananian 1.1.2.1 // JumpOptimization.java, created Wed Feb 16 18:19:49 2000 by cananian
2 cananian 1.1.2.1 // Copyright (C) 2000 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.Analysis.Tree;
5 cananian 1.1.2.1
6 cananian 1.1.2.2 import harpoon.ClassFile.HCode;
7 cananian 1.1.2.2 import harpoon.ClassFile.HCodeEdge;
8 cananian 1.1.2.2 import harpoon.ClassFile.HCodeFactory;
9 cananian 1.1.2.2 import harpoon.ClassFile.HMethod;
10 cananian 1.1.2.1 import harpoon.IR.Properties.CFGrapher;
11 cananian 1.1.2.2 import harpoon.IR.Tree.BINOP;
12 cananian 1.1.2.2 import harpoon.IR.Tree.Bop;
13 cananian 1.1.2.2 import harpoon.IR.Tree.CALL;
14 cananian 1.1.2.2 import harpoon.IR.Tree.CJUMP;
15 cananian 1.1.2.2 import harpoon.IR.Tree.CanonicalTreeCode;
16 cananian 1.1.2.2 import harpoon.IR.Tree.Code;
17 cananian 1.1.2.2 import harpoon.IR.Tree.DerivationGenerator;
18 cananian 1.1.2.2 import harpoon.IR.Tree.Exp;
19 cananian 1.1.2.2 import harpoon.IR.Tree.JUMP;
20 cananian 1.1.2.2 import harpoon.IR.Tree.LABEL;
21 cananian 1.1.2.2 import harpoon.IR.Tree.NAME;
22 cananian 1.1.2.2 import harpoon.IR.Tree.Stm;
23 cananian 1.1.2.2 import harpoon.IR.Tree.Tree;
24 cananian 1.1.2.2 import harpoon.IR.Tree.TreeFactory;
25 cananian 1.1.2.2 import harpoon.IR.Tree.TreeKind;
26 cananian 1.1.2.1 import harpoon.Temp.Label;
27 cananian 1.8 import net.cscott.jutil.DisjointSet;
28 cananian 1.1.2.2 import harpoon.Util.Util;
29 cananian 1.1.2.1
30 cananian 1.1.2.2 import java.util.Arrays;
31 cananian 1.1.2.2 import java.util.Iterator;
32 cananian 1.1.2.2 import java.util.List;
33 cananian 1.1.2.1 /**
34 cananian 1.1.2.1 * <code>JumpOptimization</code> removes branches-to-branches
35 cananian 1.1.2.1 * and redundant labels.
36 cananian 1.1.2.1 *
37 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
38 cananian 1.8 * @version $Id: JumpOptimization.java,v 1.8 2004/02/08 01:54:29 cananian Exp $
39 cananian 1.1.2.1 */
40 cananian 1.1.2.1 public abstract class JumpOptimization extends Simplification {
41 cananian 1.1.2.1 // hide constructor
42 cananian 1.1.2.1 private JumpOptimization() { }
43 cananian 1.1.2.1
44 cananian 1.1.2.1 /** Code factory for applying JumpOptimization to a
45 cananian 1.1.2.1 * canonical tree. Clones the tree before doing
46 cananian 1.1.2.1 * optimization in-place. */
47 cananian 1.1.2.1 public static HCodeFactory codeFactory(final HCodeFactory parent) {
48 cananian 1.3.2.1 assert parent.getCodeName().equals(CanonicalTreeCode.codename);
49 cananian 1.1.2.1 return new HCodeFactory() {
50 cananian 1.1.2.1 public HCode convert(HMethod m) {
51 cananian 1.1.2.1 HCode hc = parent.convert(m);
52 cananian 1.1.2.1 if (hc!=null) {
53 cananian 1.1.2.1 harpoon.IR.Tree.Code code = (harpoon.IR.Tree.Code) hc;
54 cananian 1.1.2.1 // clone code...
55 cananian 1.1.2.5 code = (harpoon.IR.Tree.Code) code.clone(m).hcode();
56 cananian 1.1.2.1 DerivationGenerator dg = null;
57 cananian 1.1.2.1 try {
58 cananian 1.1.2.1 dg = (DerivationGenerator) code.getTreeDerivation();
59 cananian 1.1.2.1 } catch (ClassCastException ex) { /* i guess not */ }
60 cananian 1.1.2.1 // ...do analysis and modify cloned code in-place.
61 cananian 1.1.2.1 simplify((Stm)code.getRootElement(), dg, HCE_RULES(code));
62 cananian 1.1.2.1 hc = code;
63 cananian 1.1.2.1 }
64 cananian 1.1.2.1 return hc;
65 cananian 1.1.2.1 }
66 cananian 1.1.2.1 public String getCodeName() { return parent.getCodeName(); }
67 cananian 1.1.2.1 public void clear(HMethod m) { parent.clear(m); }
68 cananian 1.1.2.1 };
69 cananian 1.1.2.1 }
70 cananian 1.1.2.1
71 cananian 1.6 public static List<Rule> HCE_RULES(final harpoon.IR.Tree.Code code) {
72 cananian 1.6 final CFGrapher<Tree> cfgr = code.getGrapher();
73 cananian 1.1.2.1 // collect info about useless branches
74 cananian 1.6 final DisjointSet<Label> labelmap = new DisjointSet<Label>();
75 cananian 1.6 for (Iterator<Tree> it=code.getElementsI(); it.hasNext(); ) {
76 cananian 1.6 Tree tr = it.next();
77 cananian 1.1.2.1 if (tr.kind() == TreeKind.LABEL) {
78 cananian 1.1.2.1 LABEL label = (LABEL) tr;
79 cananian 1.7 List<HCodeEdge<Tree>> succ = cfgr.succC(label);
80 cananian 1.7 if (succ.size()==1 &&
81 cananian 1.7 succ.get(0).to().kind() == TreeKind.JUMP) {
82 cananian 1.7 JUMP jump = (JUMP) succ.get(0).to();
83 cananian 1.3.2.1 assert jump.targets!=null;
84 cananian 1.1.2.6 // note that self-loops are not considered useless.
85 cananian 1.1.2.6 if (jump.targets.tail==null && // only one target.
86 cananian 1.1.2.6 !label.label.equals(jump.targets.head)) {
87 cananian 1.1.2.1 labelmap.union(label.label, jump.targets.head);
88 cananian 1.5 assert labelmap.find(label.label)
89 cananian 1.5 .equals(labelmap.find(jump.targets.head));
90 cananian 1.1.2.1 }
91 cananian 1.1.2.1 }
92 cananian 1.1.2.1 }
93 cananian 1.1.2.1 }
94 cananian 1.1.2.1 // now make rules.
95 cananian 1.1.2.1 return Arrays.asList(new Rule[] {
96 cananian 1.1.2.1 // JUMP(NAME(l)) --> JUMP(NAME(map(l)))
97 cananian 1.1.2.1 new Rule("redirJump") {
98 cananian 1.1.2.1 public boolean match(Stm s) {
99 cananian 1.1.2.1 if (s.kind() != TreeKind.JUMP) return false;
100 cananian 1.1.2.1 JUMP jump = (JUMP) s;
101 cananian 1.1.2.1 return jump.targets.tail==null &&
102 cananian 1.1.2.1 labelmap.find(jump.targets.head)!=jump.targets.head;
103 cananian 1.1.2.1 }
104 cananian 1.1.2.1 public Stm apply(TreeFactory tf,Stm s,DerivationGenerator dg) {
105 cananian 1.1.2.1 JUMP jump = (JUMP) s;
106 cananian 1.1.2.1 return new JUMP(tf, s,
107 cananian 1.1.2.1 (Label) labelmap.find(jump.targets.head));
108 cananian 1.1.2.1 }
109 cananian 1.1.2.1 },
110 cananian 1.1.2.1 // CJUMP(x, iftrue, iffalse) -> CJUMP(x, map(iftrue), map(iffalse))
111 cananian 1.1.2.1 new Rule("redirCjump") {
112 cananian 1.1.2.1 public boolean match(Stm s) {
113 cananian 1.1.2.1 if (s.kind() != TreeKind.CJUMP) return false;
114 cananian 1.1.2.1 CJUMP cjump = (CJUMP) s;
115 cananian 1.1.2.1 return labelmap.find(cjump.iftrue)!=cjump.iftrue ||
116 cananian 1.1.2.1 labelmap.find(cjump.iffalse)!=cjump.iffalse;
117 cananian 1.1.2.1 }
118 cananian 1.1.2.1 public Stm apply(TreeFactory tf,Stm s,DerivationGenerator dg) {
119 cananian 1.1.2.1 CJUMP cjump = (CJUMP) s;
120 cananian 1.1.2.1 return new CJUMP(tf, s, cjump.getTest(),
121 cananian 1.1.2.1 (Label) labelmap.find(cjump.iftrue),
122 cananian 1.1.2.1 (Label) labelmap.find(cjump.iffalse));
123 cananian 1.1.2.1 }
124 cananian 1.1.2.1 },
125 cananian 1.1.2.1 // CALL(.., NAME(handler), ..) -> CALL(.., NAME(map(handler)), ..)
126 cananian 1.1.2.1 new Rule("redirHandler") {
127 cananian 1.1.2.1 public boolean match(Stm s) {
128 cananian 1.1.2.1 if (s.kind() != TreeKind.CALL) return false;
129 cananian 1.1.2.1 CALL call = (CALL) s;
130 cananian 1.1.2.1 Label l = call.getHandler().label;
131 cananian 1.1.2.1 return labelmap.find(l) != l;
132 cananian 1.1.2.1 }
133 cananian 1.1.2.1 public Stm apply(TreeFactory tf,Stm s,DerivationGenerator dg) {
134 cananian 1.1.2.1 CALL call = (CALL) s;
135 cananian 1.1.2.1 NAME oldhandler = call.getHandler();
136 cananian 1.1.2.1 NAME newhandler =
137 cananian 1.1.2.1 new NAME(tf, oldhandler,
138 cananian 1.1.2.1 (Label) labelmap.find(oldhandler.label) );
139 cananian 1.1.2.1 return new CALL(tf, s, call.getRetval(), call.getRetex(),
140 cananian 1.1.2.1 call.getFunc(), call.getArgs(),
141 cananian 1.1.2.1 newhandler, call.isTailCall);
142 cananian 1.1.2.2 }
143 cananian 1.1.2.2 },
144 cananian 1.1.2.2 // this rule will flip CJUMPs to achieve better lay-out.
145 cananian 1.1.2.3 // CJUMP(BINOP(op, ..), iftrue, iffalse) ; LABEL(iftrue) -->
146 cananian 1.1.2.2 // CJUMP(BINOP(inv(op),..), iffalse, iftrue)
147 cananian 1.1.2.2 new Rule("flipCjump") {
148 cananian 1.1.2.2 public boolean match(Stm s) {
149 cananian 1.1.2.2 if (s.kind() != TreeKind.CJUMP) return false;
150 cananian 1.1.2.2 CJUMP cjump = (CJUMP) s;
151 cananian 1.1.2.2 if (cjump.getTest().kind() != TreeKind.BINOP) return false;
152 cananian 1.1.2.2 BINOP binop = (BINOP) cjump.getTest();
153 cananian 1.1.2.2 if (!contains(_OP(binop.op),
154 cananian 1.1.2.2 _CMPEQ|_CMPNE|_CMPGT|_CMPGE|_CMPLT|_CMPLE))
155 cananian 1.1.2.2 return false;
156 cananian 1.1.2.2 // now check if the next label corresponds to the iffalse.
157 cananian 1.1.2.2 Stm next = next(s);
158 cananian 1.1.2.2 if (next.kind() != TreeKind.LABEL) return false;
159 cananian 1.1.2.2 LABEL l = (LABEL) next;
160 cananian 1.1.2.3 return l.label == cjump.iftrue;
161 cananian 1.1.2.2 }
162 cananian 1.1.2.2 public Stm apply(TreeFactory tf,Stm s,DerivationGenerator dg) {
163 cananian 1.1.2.2 CJUMP cjump = (CJUMP) s;
164 cananian 1.1.2.2 BINOP binop = (BINOP) cjump.getTest();
165 cananian 1.1.2.2 return new CJUMP
166 cananian 1.1.2.2 (tf, cjump, new BINOP
167 cananian 1.1.2.2 (tf, binop, binop.optype,
168 cananian 1.1.2.2 Bop.invert(binop.op),
169 cananian 1.1.2.2 binop.getLeft(), binop.getRight()),
170 cananian 1.1.2.2 cjump.iffalse, cjump.iftrue);
171 cananian 1.1.2.2 }
172 cananian 1.1.2.2 // find the next Stm in layout order, skipping SEQs.
173 cananian 1.1.2.2 Stm next(Stm s) {
174 cananian 1.1.2.2 // go up until we find a SEQ that we're not the
175 cananian 1.1.2.2 // right-most child of.
176 cananian 1.1.2.2 while (s.getSibling()==null)
177 cananian 1.1.2.2 s = (Stm) s.getParent();
178 cananian 1.1.2.2 // assert that our parent is a SEQ here.
179 cananian 1.3.2.1 assert s.getParent().kind()==TreeKind.SEQ;
180 cananian 1.1.2.2 // step over to the right...
181 cananian 1.1.2.2 s = (Stm) s.getSibling();
182 cananian 1.1.2.2 // ...and zip down the left side of the subtree until
183 cananian 1.1.2.2 // we find something other than a SEQ.
184 cananian 1.1.2.2 while (s.kind()==TreeKind.SEQ)
185 cananian 1.1.2.2 s = (Stm) s.getFirstChild();
186 cananian 1.1.2.2 // done. this is it.
187 cananian 1.1.2.2 return s;
188 cananian 1.1.2.1 }
189 cananian 1.1.2.1 },
190 cananian 1.1.2.1 });
191 cananian 1.1.2.1 }
192 cananian 1.2 }