1 kkz 1.1.2.18 // ConstantPropagation.java, created Fri Aug 24 22:57:03 2001 by kkz
2 kkz 1.1.2.18 // Copyright (C) 2000 Karen Zee <kkz@tmi.lcs.mit.edu>
3 cananian 1.1.2.7 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 duncan 1.1.2.1 package harpoon.Analysis.Tree;
5 duncan 1.1.2.1
6 kkz 1.1.2.18 import harpoon.Analysis.ReachingDefs;
7 kkz 1.1.2.18 import harpoon.Analysis.ReachingDefsAltImpl;
8 kkz 1.1.2.18 import harpoon.Analysis.ReachingDefsImpl;
9 kkz 1.1.2.18 import harpoon.ClassFile.HCodeAndMaps;
10 kkz 1.1.2.18 import harpoon.ClassFile.HCode;
11 kkz 1.1.2.18 import harpoon.ClassFile.HCodeFactory;
12 pnkfelix 1.1.2.5 import harpoon.IR.Properties.CFGrapher;
13 cananian 1.1.2.14 import harpoon.IR.Properties.UseDefer;
14 kkz 1.1.2.18 import harpoon.IR.Tree.ALIGN;
15 kkz 1.1.2.18 import harpoon.IR.Tree.BINOP;
16 kkz 1.1.2.18 import harpoon.IR.Tree.CJUMP;
17 duncan 1.1.2.1 import harpoon.IR.Tree.CONST;
18 kkz 1.1.2.18 import harpoon.IR.Tree.CanonicalTreeCode;
19 kkz 1.1.2.18 import harpoon.IR.Tree.Code;
20 kkz 1.1.2.18 import harpoon.IR.Tree.DATUM;
21 kkz 1.1.2.18 import harpoon.IR.Tree.EXPR;
22 kkz 1.1.2.18 import harpoon.IR.Tree.Exp;
23 kkz 1.1.2.18 import harpoon.IR.Tree.ExpList;
24 kkz 1.1.2.18 import harpoon.IR.Tree.INVOCATION;
25 kkz 1.1.2.18 import harpoon.IR.Tree.JUMP;
26 kkz 1.1.2.18 import harpoon.IR.Tree.LABEL;
27 kkz 1.1.2.18 import harpoon.IR.Tree.MEM;
28 kkz 1.1.2.18 import harpoon.IR.Tree.METHOD;
29 kkz 1.1.2.18 import harpoon.IR.Tree.MOVE;
30 kkz 1.1.2.18 import harpoon.IR.Tree.NAME;
31 kkz 1.1.2.18 import harpoon.IR.Tree.Print;
32 kkz 1.1.2.18 import harpoon.IR.Tree.RETURN;
33 kkz 1.1.2.18 import harpoon.IR.Tree.SEGMENT;
34 duncan 1.1.2.1 import harpoon.IR.Tree.Stm;
35 kkz 1.1.2.18 import harpoon.IR.Tree.TEMP;
36 kkz 1.1.2.18 import harpoon.IR.Tree.THROW;
37 duncan 1.1.2.1 import harpoon.IR.Tree.Tree;
38 duncan 1.1.2.1 import harpoon.IR.Tree.TreeKind;
39 kkz 1.1.2.18 import harpoon.IR.Tree.TreeVisitor;
40 kkz 1.1.2.18 import harpoon.IR.Tree.UNOP;
41 kkz 1.1.2.18 import harpoon.Temp.Temp;
42 duncan 1.1.2.1 import harpoon.Util.Util;
43 duncan 1.1.2.1
44 kkz 1.1.2.18 import java.util.Iterator;
45 kkz 1.1.2.18 import java.util.Set;
46 duncan 1.1.2.1
47 duncan 1.1.2.1 /**
48 kkz 1.1.2.18 * <code>ConstantPropagation</code> performs constant
49 kkz 1.1.2.18 * propagation on canonical tree form.
50 duncan 1.1.2.1 *
51 kkz 1.1.2.18 * @author Karen Zee <kkz@tmi.lcs.mit.edu>
52 cananian 1.4 * @version $Id: ConstantPropagation.java,v 1.4 2002/04/10 03:02:06 cananian Exp $
53 duncan 1.1.2.1 */
54 kkz 1.1.2.18 public class ConstantPropagation extends
55 kkz 1.1.2.18 harpoon.Analysis.Transformation.MethodMutator {
56 kkz 1.1.2.18
57 kkz 1.1.2.18 /** Creates a <code>ConstantPropagation</code>. */
58 kkz 1.1.2.18 public ConstantPropagation(HCodeFactory parent) {
59 kkz 1.1.2.18 super(parent);
60 cananian 1.3.2.1 assert parent.getCodeName().equals(CanonicalTreeCode.codename);
61 kkz 1.1.2.18 }
62 duncan 1.1.2.1
63 kkz 1.1.2.18 protected HCode mutateHCode(HCodeAndMaps input) {
64 kkz 1.1.2.18 Code hc = (Code) input.hcode();
65 kkz 1.1.2.18 String old = Print.print((Tree)hc.getRootElement());
66 kkz 1.1.2.18 CFGrapher cfger = hc.getGrapher();
67 kkz 1.1.2.18 TreeVisitor tv = new ConstPropVisitor(hc);
68 kkz 1.1.2.18 // we put all elements in array to avoid screwing up the
69 kkz 1.1.2.18 // iterator as we mutate the tree in-place.
70 kkz 1.1.2.18 Object[] elements = cfger.getElements(hc).toArray();
71 kkz 1.1.2.18 for (int i=0; i < elements.length; i++) {
72 kkz 1.1.2.18 ((Stm) elements[i]).accept(tv);
73 kkz 1.1.2.18 }
74 kkz 1.1.2.18 return hc;
75 duncan 1.1.2.1 }
76 duncan 1.1.2.1
77 kkz 1.1.2.18 private static class ConstPropVisitor extends TreeVisitor {
78 kkz 1.1.2.18 private ReachingDefs rd;
79 kkz 1.1.2.18 boolean changed = false;
80 kkz 1.1.2.18
81 kkz 1.1.2.18 ConstPropVisitor(Code hc) {
82 kkz 1.1.2.18 this.rd = new ReachingDefsAltImpl(hc,
83 kkz 1.1.2.18 hc.getGrapher(),
84 kkz 1.1.2.18 hc.getUseDefer());
85 kkz 1.1.2.18 }
86 kkz 1.1.2.18
87 kkz 1.1.2.18 // should never get here
88 cananian 1.3.2.1 public void visit (Tree t) { assert false; }
89 kkz 1.1.2.18
90 kkz 1.1.2.18 // ALIGNs are okay
91 kkz 1.1.2.18 public void visit(ALIGN a) { }
92 kkz 1.1.2.18
93 kkz 1.1.2.18 // for BINOPs, tricky
94 kkz 1.1.2.18 public void visit(BINOP b) {
95 kkz 1.1.2.18 // go up until we find a Stm so we can use a UseDefer
96 kkz 1.1.2.18 Tree parent = parentStm(b);
97 cananian 1.3.2.1 assert parent != null;
98 kkz 1.1.2.18 Exp left = b.getLeft();
99 kkz 1.1.2.18 if (left.kind() == TreeKind.TEMP) {
100 kkz 1.1.2.18 Exp val = constant((TEMP)left, (Stm)parent, rd);
101 kkz 1.1.2.18 if (val != null) b.setLeft(val);
102 kkz 1.1.2.18 } else {
103 kkz 1.1.2.18 left.accept(this);
104 kkz 1.1.2.18 }
105 kkz 1.1.2.18 Exp right = b.getRight();
106 kkz 1.1.2.18 if (right.kind() == TreeKind.TEMP) {
107 kkz 1.1.2.18 Exp val = constant((TEMP)right, (Stm)parent, rd);
108 kkz 1.1.2.18 if (val != null) b.setRight(val);
109 kkz 1.1.2.18 } else {
110 kkz 1.1.2.18 right.accept(this);
111 duncan 1.1.2.1 }
112 duncan 1.1.2.1 }
113 duncan 1.1.2.1
114 kkz 1.1.2.18 // for CJUMPs, check test condition
115 kkz 1.1.2.18 public void visit(CJUMP c) {
116 kkz 1.1.2.18 Exp test = c.getTest();
117 kkz 1.1.2.18 if (test.kind() == TreeKind.TEMP) {
118 kkz 1.1.2.18 Exp val = constant((TEMP)test, c, rd);
119 kkz 1.1.2.18 if (val != null) c.setTest(val);
120 kkz 1.1.2.18 } else {
121 kkz 1.1.2.18 test.accept(this);
122 kkz 1.1.2.18 }
123 duncan 1.1.2.1 }
124 duncan 1.1.2.1
125 kkz 1.1.2.18 // CONSTs are already okay
126 kkz 1.1.2.18 public void visit(CONST c) { }
127 kkz 1.1.2.18
128 kkz 1.1.2.18 // for DATUM, check data
129 kkz 1.1.2.18 public void visit(DATUM d) {
130 kkz 1.1.2.18 Exp data = d.getData();
131 kkz 1.1.2.18 if (data.kind() == TreeKind.TEMP) {
132 kkz 1.1.2.18 Exp val = constant((TEMP)data, d, rd);
133 kkz 1.1.2.18 if (val != null) d.setData(val);
134 kkz 1.1.2.18 } else {
135 kkz 1.1.2.18 data.accept(this);
136 duncan 1.1.2.1 }
137 duncan 1.1.2.1 }
138 duncan 1.1.2.1
139 kkz 1.1.2.18 // for EXPRs, check exp
140 kkz 1.1.2.18 public void visit(EXPR e) {
141 kkz 1.1.2.18 Exp exp = e.getExp();
142 kkz 1.1.2.18 if (exp.kind() == TreeKind.TEMP) {
143 kkz 1.1.2.18 Exp val = constant((TEMP)exp, e, rd);
144 kkz 1.1.2.18 if (val != null) e.setExp(val);
145 kkz 1.1.2.18 } else {
146 kkz 1.1.2.18 exp.accept(this);
147 duncan 1.1.2.1 }
148 duncan 1.1.2.1 }
149 duncan 1.1.2.1
150 kkz 1.1.2.18 // for INVOCATIONs, check func and args
151 kkz 1.1.2.18 public void visit (INVOCATION i) {
152 kkz 1.1.2.18 Exp func = i.getFunc();
153 kkz 1.1.2.18 if (func.kind() == TreeKind.TEMP) {
154 kkz 1.1.2.18 Exp val = constant((TEMP)func, i, rd);
155 kkz 1.1.2.18 if (val != null) i.setFunc(val);
156 kkz 1.1.2.18 } else {
157 kkz 1.1.2.18 func.accept(this);
158 kkz 1.1.2.18 }
159 kkz 1.1.2.18 ExpList args = i.getArgs();
160 kkz 1.1.2.18 while(args != null) {
161 kkz 1.1.2.18 Exp arg = args.head;
162 kkz 1.1.2.18 if (arg.kind() == TreeKind.TEMP) {
163 kkz 1.1.2.18 Exp val = constant((TEMP)arg, i, rd);
164 kkz 1.1.2.18 if (val != null)
165 kkz 1.1.2.18 i.setArgs(ExpList.replace(i.getArgs(), arg, val));
166 kkz 1.1.2.18 } else {
167 kkz 1.1.2.18 arg.accept(this);
168 kkz 1.1.2.18 }
169 kkz 1.1.2.18 args = args.tail;
170 kkz 1.1.2.18 }
171 duncan 1.1.2.1 }
172 duncan 1.1.2.1
173 kkz 1.1.2.18 // for JUMPs, check exp
174 kkz 1.1.2.18 public void visit(JUMP j) {
175 kkz 1.1.2.18 Exp exp = j.getExp();
176 kkz 1.1.2.18 if (exp.kind() == TreeKind.TEMP) {
177 kkz 1.1.2.18 Exp val = constant((TEMP)exp, j, rd);
178 kkz 1.1.2.18 if (val != null) j.setExp(val);
179 kkz 1.1.2.18 } else {
180 kkz 1.1.2.18 exp.accept(this);
181 duncan 1.1.2.1 }
182 duncan 1.1.2.1 }
183 duncan 1.1.2.1
184 kkz 1.1.2.18 // LABELs are okay
185 kkz 1.1.2.18 public void visit(LABEL l) { }
186 kkz 1.1.2.18
187 kkz 1.1.2.18 // for MEMs, tricky
188 kkz 1.1.2.18 public void visit(MEM m) {
189 kkz 1.1.2.18 // go up until we find a Stm so we can use a UseDefer
190 kkz 1.1.2.18 Tree parent = parentStm(m);
191 cananian 1.3.2.1 assert parent != null;
192 kkz 1.1.2.18 Exp exp = m.getExp();
193 kkz 1.1.2.18 if (exp.kind() == TreeKind.TEMP) {
194 kkz 1.1.2.18 Exp val = constant((TEMP)exp, (Stm)parent, rd);
195 kkz 1.1.2.18 if (val != null) m.setExp(val);
196 kkz 1.1.2.18 } else {
197 kkz 1.1.2.18 exp.accept(this);
198 duncan 1.1.2.3 }
199 duncan 1.1.2.1 }
200 duncan 1.1.2.1
201 kkz 1.1.2.18 // METHODs are okay
202 kkz 1.1.2.18 public void visit(METHOD m) { }
203 kkz 1.1.2.18
204 kkz 1.1.2.18 // for MOVEs, check the src
205 kkz 1.1.2.18 public void visit(MOVE m) {
206 kkz 1.1.2.18 Exp src = m.getSrc();
207 kkz 1.1.2.18 if (src.kind() == TreeKind.TEMP) {
208 kkz 1.1.2.18 Exp val = constant((TEMP)src, m, rd);
209 kkz 1.1.2.18 if (val != null) m.setSrc(val);
210 kkz 1.1.2.18 } else {
211 kkz 1.1.2.18 src.accept(this);
212 duncan 1.1.2.1 }
213 duncan 1.1.2.1 }
214 duncan 1.1.2.1
215 kkz 1.1.2.18 // NAMEs are okay
216 kkz 1.1.2.18 public void visit(NAME n) { }
217 kkz 1.1.2.18
218 kkz 1.1.2.18 // for RETURNs, check retval
219 kkz 1.1.2.18 public void visit(RETURN r) {
220 kkz 1.1.2.18 Exp retval = r.getRetval();
221 kkz 1.1.2.18 if (retval.kind() == TreeKind.TEMP) {
222 kkz 1.1.2.18 Exp val = constant((TEMP)retval, r, rd);
223 kkz 1.1.2.18 if (val != null) r.setRetval(val);
224 kkz 1.1.2.18 } else {
225 kkz 1.1.2.18 retval.accept(this);
226 kkz 1.1.2.18 }
227 kkz 1.1.2.18 }
228 kkz 1.1.2.18
229 kkz 1.1.2.18 // SEGMENTs are okay
230 kkz 1.1.2.18 public void visit(SEGMENT s) { }
231 kkz 1.1.2.18
232 kkz 1.1.2.18 // TEMPs are okay
233 kkz 1.1.2.18 public void visit(TEMP t) { }
234 kkz 1.1.2.18
235 kkz 1.1.2.18 // for THROWs, check retex and handler
236 kkz 1.1.2.18 public void visit(THROW t) {
237 kkz 1.1.2.18 Exp retex = t.getRetex();
238 kkz 1.1.2.18 if (retex.kind() == TreeKind.TEMP) {
239 kkz 1.1.2.18 Exp val = constant((TEMP)retex, t, rd);
240 kkz 1.1.2.18 if (val != null) t.setRetex(val);
241 kkz 1.1.2.18 } else {
242 kkz 1.1.2.18 retex.accept(this);
243 kkz 1.1.2.18 }
244 kkz 1.1.2.18 Exp handler = t.getHandler();
245 kkz 1.1.2.18 if (handler.kind() == TreeKind.TEMP) {
246 kkz 1.1.2.18 Exp val = constant((TEMP)handler, t, rd);
247 kkz 1.1.2.18 if (val != null) t.setHandler(val);
248 kkz 1.1.2.18 } else {
249 kkz 1.1.2.18 handler.accept(this);
250 kkz 1.1.2.18 }
251 kkz 1.1.2.18 }
252 kkz 1.1.2.18
253 kkz 1.1.2.18 // for UNOPs, tricky
254 kkz 1.1.2.18 public void visit(UNOP u) {
255 kkz 1.1.2.18 // go up until we find a Stm so we can use a UseDefer
256 kkz 1.1.2.18 Tree parent = parentStm(u);
257 cananian 1.3.2.1 assert parent != null;
258 kkz 1.1.2.18 Exp operand = u.getOperand();
259 kkz 1.1.2.18 if (operand.kind() == TreeKind.TEMP) {
260 kkz 1.1.2.18 Exp val = constant((TEMP)operand, (Stm)parent, rd);
261 kkz 1.1.2.18 if (val != null) u.setOperand(val);
262 kkz 1.1.2.18 } else {
263 kkz 1.1.2.18 operand.accept(this);
264 kkz 1.1.2.18 }
265 kkz 1.1.2.18 }
266 kkz 1.1.2.18
267 kkz 1.1.2.18 // returns the parent Stm to whom this Exp belongs
268 kkz 1.1.2.18 private static Stm parentStm(Exp exp) {
269 kkz 1.1.2.18 Tree parent = exp.getParent();
270 kkz 1.1.2.18 while (!(parent instanceof Stm))
271 kkz 1.1.2.18 parent = parent.getParent();
272 kkz 1.1.2.18 return (Stm)parent;
273 kkz 1.1.2.18 }
274 kkz 1.1.2.18
275 kkz 1.1.2.18 // returns a CONST or NAME if the given TEMP can be
276 kkz 1.1.2.18 // replaced by such. else returns null.
277 kkz 1.1.2.18 private static Exp constant(TEMP T, Stm parent, ReachingDefs rd) {
278 kkz 1.1.2.18 Set s = rd.reachingDefs(parent, T.temp);
279 kkz 1.1.2.18 // if no definitions reach, then this
280 kkz 1.1.2.18 // is dead code, and we're done
281 kkz 1.1.2.18 if (s.size() == 0)
282 kkz 1.1.2.18 return null;
283 kkz 1.1.2.18 // all the definitions must be MOVEs with
284 kkz 1.1.2.18 // equivalent CONSTs or NAMEs as sources
285 kkz 1.1.2.18 Iterator it = s.iterator();
286 kkz 1.1.2.18 // all definitions are Stms
287 kkz 1.1.2.18 Stm first = (Stm) it.next();
288 kkz 1.1.2.18 if (first.kind() != TreeKind.MOVE) return null;
289 kkz 1.1.2.18 Exp firstSrc = ((MOVE) first).getSrc();
290 kkz 1.1.2.18 // if the first MOVE we see fits
291 kkz 1.1.2.18 // our criterion, continue
292 kkz 1.1.2.18 // all subsequent MOVEs must have
293 kkz 1.1.2.18 // equivalent sources
294 kkz 1.1.2.18 if (firstSrc.kind() == TreeKind.CONST) {
295 kkz 1.1.2.18 CONST c = (CONST) firstSrc;
296 kkz 1.1.2.18 while(it.hasNext()) {
297 kkz 1.1.2.18 // check for match
298 kkz 1.1.2.18 Stm stm = (Stm) it.next();
299 kkz 1.1.2.18 Number n = c.value();
300 kkz 1.1.2.18 if (stm.kind() != TreeKind.MOVE) return null;
301 kkz 1.1.2.18 Exp src = ((MOVE) stm).getSrc();
302 kkz 1.1.2.18 if (src.kind() != TreeKind.CONST ||
303 kkz 1.1.2.18 src.type() != c.type())
304 kkz 1.1.2.18 return null;
305 kkz 1.1.2.18 if (n == null) {
306 kkz 1.1.2.18 if (((CONST) src).value() != null) return null;
307 kkz 1.1.2.18 } else {
308 kkz 1.1.2.18 if (!((CONST) src).value().equals(n)) return null;
309 duncan 1.1.2.1 }
310 duncan 1.1.2.1 }
311 kkz 1.1.2.18 // done!
312 kkz 1.1.2.18 return (Exp)c.clone();
313 kkz 1.1.2.18 } else if (firstSrc.kind() == TreeKind.NAME) {
314 kkz 1.1.2.18 NAME n = (NAME) firstSrc;
315 kkz 1.1.2.18 while(it.hasNext()) {
316 kkz 1.1.2.18 // check for match
317 kkz 1.1.2.18 Stm stm = (Stm) it.next();
318 kkz 1.1.2.18 if (stm.kind() != TreeKind.MOVE) return null;
319 kkz 1.1.2.18 Exp src = ((MOVE) stm).getSrc();
320 kkz 1.1.2.18 if (src.kind() != TreeKind.NAME ||
321 kkz 1.1.2.18 !((NAME) src).label.equals(n.label))
322 kkz 1.1.2.18 return null;
323 kkz 1.1.2.18 // all NAMEs have type Type.POINTER
324 cananian 1.3.2.1 assert src.type() == n.type();
325 kkz 1.1.2.18 }
326 kkz 1.1.2.18 // done!
327 kkz 1.1.2.18 return (Exp)n.clone();
328 duncan 1.1.2.1 }
329 kkz 1.1.2.18 return null;
330 duncan 1.1.2.6 }
331 duncan 1.1.2.1 }
332 cananian 1.2 }