1 cananian 1.1.2.1 // AlgebraicSimplification.java, created Sat Dec 18 17:42:19 1999 by duncan
2 cananian 1.1.2.1 // Copyright (C) 1998 Duncan Bryce <duncan@lcs.mit.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.1 import harpoon.ClassFile.HCode;
7 cananian 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
8 cananian 1.1.2.1 import harpoon.ClassFile.HMethod;
9 cananian 1.1.2.1 import harpoon.IR.Tree.BINOP;
10 cananian 1.1.2.1 import harpoon.IR.Tree.Bop;
11 cananian 1.1.2.1 import harpoon.IR.Tree.CanonicalTreeCode;
12 cananian 1.1.2.1 import harpoon.IR.Tree.Code;
13 cananian 1.1.2.1 import harpoon.IR.Tree.CONST;
14 cananian 1.1.2.3 import harpoon.IR.Tree.DerivationGenerator;
15 cananian 1.1.2.1 import harpoon.IR.Tree.ESEQ;
16 cananian 1.1.2.1 import harpoon.IR.Tree.Exp;
17 cananian 1.1.2.1 import harpoon.IR.Tree.ExpList;
18 cananian 1.1.2.1 import harpoon.IR.Tree.SEQ;
19 cananian 1.1.2.1 import harpoon.IR.Tree.Stm;
20 cananian 1.1.2.1 import harpoon.IR.Tree.Tree;
21 cananian 1.1.2.1 import harpoon.IR.Tree.TreeFactory;
22 cananian 1.1.2.1 import harpoon.IR.Tree.TreeKind;
23 cananian 1.1.2.1 import harpoon.IR.Tree.TreeVisitor;
24 cananian 1.1.2.1 import harpoon.IR.Tree.Type;
25 cananian 1.1.2.1 import harpoon.IR.Tree.UNOP;
26 cananian 1.1.2.1 import harpoon.IR.Tree.Uop;
27 cananian 1.1.2.1 import harpoon.Util.Util;
28 cananian 1.1.2.1
29 cananian 1.1.2.1 import java.util.ArrayList;
30 cananian 1.1.2.1 import java.util.Collections;
31 cananian 1.1.2.1 import java.util.Iterator;
32 cananian 1.1.2.1 import java.util.List;
33 cananian 1.1.2.1 import java.util.Stack;
34 cananian 1.1.2.1
35 cananian 1.1.2.1 /**
36 cananian 1.1.2.1 * <code>Simplification</code> is a general-purpose simplification engine
37 cananian 1.1.2.1 * for trees.
38 cananian 1.1.2.1 *
39 cananian 1.1.2.1 * <B>Warning:</B> this performs modifications on the tree form in place.
40 cananian 1.1.2.1 *
41 cananian 1.1.2.1 * @author Duncan Bryce <duncan@lcs.mit.edu>
42 cananian 1.4 * @version $Id: Simplification.java,v 1.4 2002/04/10 03:02:06 cananian Exp $
43 cananian 1.1.2.1 */
44 cananian 1.1.2.1 public abstract class Simplification {
45 cananian 1.1.2.1 private static final boolean debug = false;
46 cananian 1.1.2.1 // hide constructor
47 cananian 1.1.2.1 protected Simplification() { }
48 cananian 1.1.2.1
49 cananian 1.1.2.1 /**
50 cananian 1.1.2.1 * Code factory for applying a set of simplification rules to
51 cananian 1.1.2.1 * tree form. Clones the tree before simplifying it in-place.
52 cananian 1.1.2.1 */
53 cananian 1.1.2.1 public static HCodeFactory codeFactory(final HCodeFactory parent,
54 cananian 1.3.2.2 final List<Rule> rules) {
55 cananian 1.3.2.1 assert parent.getCodeName().equals(CanonicalTreeCode.codename);
56 cananian 1.1.2.1 return new HCodeFactory() {
57 cananian 1.1.2.1 public HCode convert(HMethod m) {
58 cananian 1.1.2.1 HCode hc = parent.convert(m);
59 cananian 1.1.2.1 if (hc!=null) {
60 cananian 1.1.2.1 harpoon.IR.Tree.Code code = (harpoon.IR.Tree.Code) hc;
61 cananian 1.1.2.2 // clone code...
62 cananian 1.1.2.9 code = (harpoon.IR.Tree.Code) code.clone(m).hcode();
63 cananian 1.1.2.3 DerivationGenerator dg = null;
64 cananian 1.1.2.3 try {
65 cananian 1.1.2.3 dg = (DerivationGenerator) code.getTreeDerivation();
66 cananian 1.1.2.3 } catch (ClassCastException ex) { /* i guess not */ }
67 cananian 1.1.2.2 // ...and modify cloned code in-place.
68 cananian 1.1.2.3 simplify((Stm)code.getRootElement(), dg, rules);
69 cananian 1.1.2.5 hc = code;
70 cananian 1.1.2.1 }
71 cananian 1.1.2.1 return hc;
72 cananian 1.1.2.1 }
73 cananian 1.1.2.1 public String getCodeName() { return parent.getCodeName(); }
74 cananian 1.1.2.1 public void clear(HMethod m) { parent.clear(m); }
75 cananian 1.1.2.1 };
76 cananian 1.1.2.1 }
77 cananian 1.1.2.1
78 cananian 1.1.2.1 // Define new operator constants that can be masked together.
79 cananian 1.1.2.1 protected final static int _CMPLT = (1<<0);
80 cananian 1.1.2.1 protected final static int _CMPLE = (1<<1);
81 cananian 1.1.2.1 protected final static int _CMPEQ = (1<<2);
82 cananian 1.1.2.7 protected final static int _CMPNE = (1<<15);
83 cananian 1.1.2.1 protected final static int _CMPGE = (1<<3);
84 cananian 1.1.2.1 protected final static int _CMPGT = (1<<4);
85 cananian 1.1.2.1 protected final static int _ADD = (1<<5);
86 cananian 1.1.2.1 protected final static int _MUL = (1<<6);
87 cananian 1.1.2.1 protected final static int _DIV = (1<<7);
88 cananian 1.1.2.1 protected final static int _REM = (1<<8);
89 cananian 1.1.2.1 protected final static int _SHL = (1<<9);
90 cananian 1.1.2.1 protected final static int _SHR = (1<<10);
91 cananian 1.1.2.1 protected final static int _USHR = (1<<11);
92 cananian 1.1.2.1 protected final static int _AND = (1<<12);
93 cananian 1.1.2.1 protected final static int _OR = (1<<13);
94 cananian 1.1.2.1 protected final static int _XOR = (1<<14);
95 cananian 1.1.2.1
96 cananian 1.1.2.1 // Define new TreeKind constants that can be masked together.
97 cananian 1.1.2.1 protected final static int _ALIGN = (1<<0);
98 cananian 1.1.2.1 protected final static int _BINOP = (1<<1);
99 cananian 1.1.2.1 protected final static int _CALL = (1<<2);
100 cananian 1.1.2.1 protected final static int _CJUMP = (1<<3);
101 cananian 1.1.2.1 // _CONST represents all constants including 0 and null.
102 cananian 1.1.2.1 // _CONST0 _CONST1 _CONSTm1 and _CONSTNULL represent specific constants.
103 cananian 1.1.2.1 protected final static int _CONST = (1<<4);
104 cananian 1.1.2.1 protected final static int _DATUM = (1<<5);
105 cananian 1.1.2.1 protected final static int _ESEQ = (1<<6);
106 jwhaley 1.1.2.8 protected final static int _EXPR = (1<<7);
107 cananian 1.1.2.1 protected final static int _JUMP = (1<<8);
108 cananian 1.1.2.1 protected final static int _LABEL = (1<<9);
109 cananian 1.1.2.1 protected final static int _MEM = (1<<10);
110 cananian 1.1.2.1 protected final static int _METHOD = (1<<11);
111 cananian 1.1.2.1 protected final static int _MOVE = (1<<12);
112 cananian 1.1.2.1 protected final static int _NAME = (1<<13);
113 cananian 1.1.2.1 protected final static int _NATIVECALL = (1<<14);
114 cananian 1.1.2.1 protected final static int _RETURN = (1<<15);
115 cananian 1.1.2.1 protected final static int _SEGMENT = (1<<16);
116 cananian 1.1.2.1 protected final static int _SEQ = (1<<17);
117 cananian 1.1.2.1 protected final static int _TEMP = (1<<18);
118 cananian 1.1.2.1 protected final static int _THROW = (1<<19);
119 cananian 1.1.2.1 protected final static int _UNOP = (1<<20);
120 cananian 1.1.2.1
121 cananian 1.1.2.1 // Define more specialized types used to match rules.
122 cananian 1.1.2.1 protected final static int _CONSTNULL = (1<<21);
123 cananian 1.1.2.1 protected final static int _CONSTm1 = (1<<22);
124 cananian 1.1.2.1 protected final static int _CONST0 = (1<<23);
125 cananian 1.1.2.1 protected final static int _CONST1 = (1<<24);
126 cananian 1.1.2.1
127 cananian 1.1.2.1 /**
128 cananian 1.1.2.1 * Performs simplification on <code>root</code>, using the
129 cananian 1.1.2.1 * specified set of simplification rules.
130 cananian 1.1.2.1 * <b>Requires:</b>
131 cananian 1.1.2.1 * <OL>
132 cananian 1.1.2.1 * <LI><code>root</code> is a tree.
133 cananian 1.1.2.1 * <LI>Each element of <code>rules</code> is an implementation of the
134 cananian 1.1.2.1 * <code>Simplification.Rule</code> interface.
135 cananian 1.1.2.1 * <LI>The supplied set of rules monotonically reduces all possible
136 cananian 1.1.2.1 * <code>Tree</code> objects to some fixed point.
137 cananian 1.1.2.1 * </OL>
138 cananian 1.1.2.1 *
139 cananian 1.1.2.1 * @param root the tree to simplify
140 cananian 1.1.2.3 * @param dg a <code>DerivationGenerator</code> for the tree,
141 cananian 1.1.2.3 * or <code>null</code> to generate no type information.
142 cananian 1.1.2.1 * @param rules the set of simplification rules to apply to the elements
143 cananian 1.1.2.1 * of <code>root</code>.
144 cananian 1.1.2.1 */
145 cananian 1.3.2.2 public static void simplify(Tree root, DerivationGenerator dg, List<Rule> rules)
146 cananian 1.1.2.3 {
147 cananian 1.1.2.1 // Shouldn't pass a null ptr.
148 cananian 1.3.2.1 assert root != null && rules != null;
149 cananian 1.1.2.1
150 cananian 1.1.2.1 // Perform the simplification.
151 cananian 1.1.2.3 while (new SimplificationVisitor(root, dg, rules).changed())
152 cananian 1.1.2.1 /* repeat */ ;
153 cananian 1.1.2.1 }
154 cananian 1.1.2.1
155 cananian 1.1.2.1 /**
156 cananian 1.1.2.1 * A class to applies simplification rules to elements of a canonical
157 cananian 1.1.2.1 * tree form.
158 cananian 1.1.2.1 */
159 cananian 1.1.2.1 private static class SimplificationVisitor extends TreeVisitor {
160 cananian 1.1.2.3 private final TreeFactory tf;
161 cananian 1.1.2.3 private final DerivationGenerator dg;
162 cananian 1.1.2.4 private final Rule[] rules;
163 cananian 1.1.2.1 private boolean changed = false;
164 cananian 1.1.2.1
165 cananian 1.1.2.3 public SimplificationVisitor(Tree root, DerivationGenerator dg,
166 cananian 1.3.2.2 List<Rule> rules) {
167 cananian 1.1.2.3 this.tf = root.getFactory();
168 cananian 1.1.2.3 this.dg = dg;
169 cananian 1.3.2.2 this.rules = rules.toArray(new Rule[rules.size()]);
170 cananian 1.1.2.1 // evaluate each subtree from leaves up to root.
171 cananian 1.1.2.1 postorder(root);
172 cananian 1.1.2.1 }
173 cananian 1.1.2.1 void postorder(Tree t) {
174 cananian 1.1.2.1 // post-order traversal: visit all children first.
175 cananian 1.1.2.1 for (Tree tp = t.getFirstChild(); tp!=null; ) {
176 cananian 1.1.2.1 Tree one = tp;
177 cananian 1.1.2.1 tp=tp.getSibling();// advance *before* we (possibly) unlink tp!
178 cananian 1.1.2.1 postorder(one);
179 cananian 1.1.2.1 }
180 cananian 1.1.2.1 // now visit this.
181 cananian 1.1.2.1 t.accept(this);
182 cananian 1.1.2.1 }
183 cananian 1.1.2.1 public boolean changed() { return changed; }
184 cananian 1.1.2.1
185 cananian 1.1.2.1 public void visit(Tree t) {
186 cananian 1.1.2.1 throw new Error("No defaults here.");
187 cananian 1.1.2.1 }
188 cananian 1.1.2.1
189 cananian 1.1.2.1 public void visit(Exp e) {
190 cananian 1.1.2.10 boolean done = false;
191 cananian 1.1.2.10 RESTART: while (!done) {
192 cananian 1.1.2.4 for (int i=0; i<rules.length; i++) {
193 cananian 1.1.2.4 Rule rule = rules[i];
194 cananian 1.1.2.1 if (rule.match(e)) {
195 cananian 1.1.2.3 Exp simpleE = rule.apply(tf, e, dg);
196 cananian 1.1.2.1 if (debug)
197 cananian 1.1.2.1 System.out.println("Replacing: " + e + " with " +
198 cananian 1.1.2.1 simpleE + " by rule " + rule);
199 cananian 1.1.2.10 e.replace(simpleE);// XXX: simpleE cannot contain e
200 cananian 1.1.2.1 e = simpleE;
201 cananian 1.1.2.1 changed = true;
202 cananian 1.1.2.1 // revisit this.
203 cananian 1.1.2.1 continue RESTART;
204 cananian 1.1.2.1 }
205 cananian 1.1.2.1 }
206 cananian 1.1.2.10 done = true; // okay, so this is just a hacked-together 'goto'
207 cananian 1.1.2.10 }
208 cananian 1.1.2.1 }
209 cananian 1.1.2.1
210 cananian 1.1.2.1 public void visit(Stm s) {
211 cananian 1.1.2.10 boolean done = false;
212 cananian 1.1.2.10 RESTART: while (!done) {
213 cananian 1.1.2.4 for (int i=0; i<rules.length; i++) {
214 cananian 1.1.2.4 Rule rule = rules[i];
215 cananian 1.1.2.1 if (rule.match(s)) {
216 cananian 1.1.2.3 Stm simpleS = rule.apply(tf, s, dg);
217 cananian 1.1.2.1 if (debug)
218 cananian 1.1.2.1 System.out.println("Replacing: " + s + " with " +
219 cananian 1.1.2.1 simpleS + " by rule " + rule);
220 cananian 1.1.2.10 s.replace(simpleS);// XXX: simpleS cannot contain e
221 cananian 1.1.2.1 s = simpleS;
222 cananian 1.1.2.1 changed = true;
223 cananian 1.1.2.1 // revisit this.
224 cananian 1.1.2.1 continue RESTART;
225 cananian 1.1.2.1 }
226 cananian 1.1.2.1 }
227 cananian 1.1.2.10 done = true; // okay, so this is just a hacked-together 'goto'
228 cananian 1.1.2.10 }
229 cananian 1.1.2.1 }
230 cananian 1.1.2.1 }
231 cananian 1.1.2.1
232 cananian 1.1.2.1 //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//
233 cananian 1.1.2.1 // //
234 cananian 1.1.2.1 // Auxiliary Classes //
235 cananian 1.1.2.1 // //
236 cananian 1.1.2.1 //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//
237 cananian 1.1.2.1
238 cananian 1.1.2.1 /**
239 cananian 1.1.2.1 * A simplification rule for use with the tree simplifier.
240 cananian 1.1.2.1 */
241 cananian 1.1.2.1 public static abstract class Rule {
242 cananian 1.1.2.1 private final String _name;
243 cananian 1.1.2.1 public Rule(String name) { this._name = name; }
244 cananian 1.1.2.1 /** Returns a human-readable name for this rule. */
245 cananian 1.1.2.1 public String toString() { return _name; }
246 cananian 1.1.2.1 /** Returns true if <code>exp</code> matches this rule. */
247 cananian 1.1.2.1 public boolean match(Exp exp) { return false; }
248 cananian 1.1.2.1 /** Applies this rule to <code>exp</code>, and returns the result.
249 cananian 1.1.2.1 * <code>apply()</code> should always succeed when
250 cananian 1.1.2.1 * <code>match()</code> returns <code>true</code>. Otherwise,
251 cananian 1.1.2.1 * the behavior of <code>apply</code> is undefined.
252 cananian 1.1.2.10 * The returned <code>Exp</code> cannot contain the parameter
253 cananian 1.1.2.10 * <code>exp</code>, although it can contain its children.
254 cananian 1.1.2.10 * (use exp.build(tf, exp.kids()) to workaround this limitation.)
255 cananian 1.1.2.1 */
256 cananian 1.1.2.3 public Exp apply(TreeFactory tf, Exp exp, DerivationGenerator dg) {
257 cananian 1.1.2.3 throw new Error("unimplemented");
258 cananian 1.1.2.3 }
259 cananian 1.1.2.1
260 cananian 1.1.2.1 /** Returns true if <code>stm</code> matches this rule. */
261 cananian 1.1.2.1 public boolean match(Stm stm) { return false; }
262 cananian 1.1.2.1 /** Applies this rule to <code>stm</code>, and returns the result.
263 cananian 1.1.2.1 * <code>apply()</code> should always succeed when
264 cananian 1.1.2.1 * <code>match()</code> returns <code>true</code>. Otherwise,
265 cananian 1.1.2.1 * the behavior of <code>apply</code> is undefined.
266 cananian 1.1.2.10 * The returned <code>Stm</code> cannot contain the parameter
267 cananian 1.1.2.10 * <code>stm</code>, although it can contain its children.
268 cananian 1.1.2.10 * (use stm.build(tf, stm.kids()) to workaround this limitation.)
269 cananian 1.1.2.1 */
270 cananian 1.1.2.3 public Stm apply(TreeFactory tf, Stm stm, DerivationGenerator dg) {
271 cananian 1.1.2.3 throw new Error("unimplemented");
272 cananian 1.1.2.3 }
273 cananian 1.1.2.1 }
274 cananian 1.1.2.1
275 cananian 1.1.2.1 /** Convenience function to test whether any of the bits in
276 cananian 1.1.2.1 * <code>mask</code> are set in <code>val</code>. */
277 cananian 1.1.2.1 protected static boolean contains(int val, int mask) {
278 cananian 1.1.2.1 return (val & mask) != 0;
279 cananian 1.1.2.1 }
280 cananian 1.1.2.1 protected static int _KIND(Tree t) {
281 cananian 1.1.2.1 switch (t.kind()) {
282 cananian 1.1.2.1 case TreeKind.ALIGN: return _ALIGN;
283 cananian 1.1.2.1 case TreeKind.BINOP: return _BINOP;
284 cananian 1.1.2.1 case TreeKind.CALL: return _CALL;
285 cananian 1.1.2.1 case TreeKind.CJUMP: return _CJUMP;
286 cananian 1.1.2.1 case TreeKind.CONST:
287 cananian 1.1.2.1 CONST c = (CONST)t;
288 cananian 1.1.2.1 return _CONST |
289 cananian 1.1.2.6 (c.isFloatingPoint() ? 0 :
290 cananian 1.1.2.11 // note that CONSTNULL is not necessarily same as CONST0
291 cananian 1.1.2.6 c.value == null ? _CONSTNULL :
292 cananian 1.1.2.6 c.value.longValue() == 0 ? _CONST0 :
293 cananian 1.1.2.6 c.value.longValue() == 1 ? _CONST1 :
294 cananian 1.1.2.6 c.value.longValue() ==-1 ? _CONSTm1:
295 cananian 1.1.2.1 0);
296 cananian 1.1.2.1 case TreeKind.DATUM: return _DATUM;
297 cananian 1.1.2.1 case TreeKind.ESEQ: return _ESEQ;
298 jwhaley 1.1.2.8 case TreeKind.EXPR: return _EXPR;
299 cananian 1.1.2.1 case TreeKind.JUMP: return _JUMP;
300 cananian 1.1.2.1 case TreeKind.LABEL: return _LABEL;
301 cananian 1.1.2.1 case TreeKind.MEM: return _MEM;
302 cananian 1.1.2.1 case TreeKind.METHOD: return _METHOD;
303 cananian 1.1.2.1 case TreeKind.MOVE: return _MOVE;
304 cananian 1.1.2.1 case TreeKind.NAME: return _NAME;
305 cananian 1.1.2.1 case TreeKind.NATIVECALL: return _NATIVECALL;
306 cananian 1.1.2.1 case TreeKind.RETURN: return _RETURN;
307 cananian 1.1.2.1 case TreeKind.SEGMENT: return _SEGMENT;
308 cananian 1.1.2.1 case TreeKind.SEQ: return _SEQ;
309 cananian 1.1.2.1 case TreeKind.TEMP: return _TEMP;
310 cananian 1.1.2.1 case TreeKind.THROW: return _THROW;
311 cananian 1.1.2.1 case TreeKind.UNOP: return _UNOP;
312 cananian 1.1.2.1 default: throw new Error("Unrecognized type: " + t.kind());
313 cananian 1.1.2.1 }
314 cananian 1.1.2.1 }
315 cananian 1.1.2.1
316 cananian 1.1.2.1 protected static int _OP(int op) {
317 cananian 1.1.2.1 switch (op) {
318 cananian 1.1.2.1 case Bop.CMPLT: return _CMPLT;
319 cananian 1.1.2.1 case Bop.CMPLE: return _CMPLE;
320 cananian 1.1.2.1 case Bop.CMPEQ: return _CMPEQ;
321 cananian 1.1.2.7 case Bop.CMPNE: return _CMPNE;
322 cananian 1.1.2.1 case Bop.CMPGE: return _CMPGE;
323 cananian 1.1.2.1 case Bop.CMPGT: return _CMPGT;
324 cananian 1.1.2.1 case Bop.ADD: return _ADD;
325 cananian 1.1.2.1 case Bop.MUL: return _MUL;
326 cananian 1.1.2.1 case Bop.DIV: return _DIV;
327 cananian 1.1.2.1 case Bop.REM: return _REM;
328 cananian 1.1.2.1 case Bop.SHL: return _SHL;
329 cananian 1.1.2.1 case Bop.SHR: return _SHR;
330 cananian 1.1.2.1 case Bop.USHR: return _USHR;
331 cananian 1.1.2.1 case Bop.AND: return _AND;
332 cananian 1.1.2.1 case Bop.OR: return _OR;
333 cananian 1.1.2.1 case Bop.XOR: return _XOR;
334 cananian 1.1.2.1 default: throw new Error("Unrecognized op: " + op);
335 cananian 1.1.2.1 }
336 cananian 1.1.2.1 }
337 cananian 1.2 }