1 cananian 1.1.2.7 // AlgebraicSimplification.java, created Sat Dec 18 17:42:19 1999 by duncan
2 cananian 1.1.2.7 // Copyright (C) 1998 Duncan Bryce <duncan@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 cananian 1.1.2.8 import harpoon.ClassFile.HCode;
7 cananian 1.1.2.8 import harpoon.ClassFile.HCodeFactory;
8 cananian 1.1.2.8 import harpoon.ClassFile.HMethod;
9 duncan 1.1.2.1 import harpoon.IR.Tree.BINOP;
10 duncan 1.1.2.1 import harpoon.IR.Tree.Bop;
11 cananian 1.1.2.8 import harpoon.IR.Tree.CanonicalTreeCode;
12 duncan 1.1.2.1 import harpoon.IR.Tree.Code;
13 duncan 1.1.2.1 import harpoon.IR.Tree.CONST;
14 cananian 1.1.2.16 import harpoon.IR.Tree.DerivationGenerator;
15 duncan 1.1.2.1 import harpoon.IR.Tree.ESEQ;
16 jwhaley 1.1.2.20 import harpoon.IR.Tree.EXPR;
17 duncan 1.1.2.1 import harpoon.IR.Tree.Exp;
18 duncan 1.1.2.1 import harpoon.IR.Tree.ExpList;
19 cananian 1.1.2.17 import harpoon.IR.Tree.MOVE;
20 duncan 1.1.2.1 import harpoon.IR.Tree.SEQ;
21 duncan 1.1.2.1 import harpoon.IR.Tree.Stm;
22 cananian 1.1.2.17 import harpoon.IR.Tree.TEMP;
23 duncan 1.1.2.1 import harpoon.IR.Tree.Tree;
24 duncan 1.1.2.1 import harpoon.IR.Tree.TreeFactory;
25 duncan 1.1.2.1 import harpoon.IR.Tree.TreeKind;
26 duncan 1.1.2.1 import harpoon.IR.Tree.TreeVisitor;
27 duncan 1.1.2.1 import harpoon.IR.Tree.Type;
28 duncan 1.1.2.1 import harpoon.IR.Tree.UNOP;
29 duncan 1.1.2.1 import harpoon.IR.Tree.Uop;
30 cananian 1.1.2.17 import harpoon.Temp.Temp;
31 duncan 1.1.2.1
32 duncan 1.1.2.1 import java.util.ArrayList;
33 cananian 1.1.2.8 import java.util.Collections;
34 duncan 1.1.2.1 import java.util.Iterator;
35 duncan 1.1.2.1 import java.util.List;
36 duncan 1.1.2.1 import java.util.Stack;
37 duncan 1.1.2.1
38 cananian 1.7 import net.cscott.jutil.Util;
39 duncan 1.1.2.1 /**
40 duncan 1.1.2.1 * <code>AlgebraicSimplification</code> performs algebraic simplification
41 duncan 1.1.2.1 * on canonical trees.
42 duncan 1.1.2.1 *
43 duncan 1.1.2.1 * <B>Warning:</B> this performs modifications on the tree form in place.
44 duncan 1.1.2.1 *
45 duncan 1.1.2.1 * @author Duncan Bryce <duncan@lcs.mit.edu>
46 cananian 1.7 * @version $Id: AlgebraicSimplification.java,v 1.7 2004/02/08 01:54:28 cananian Exp $
47 duncan 1.1.2.1 */
48 cananian 1.1.2.15 public abstract class AlgebraicSimplification extends Simplification {
49 cananian 1.1.2.8 // hide constructor
50 cananian 1.1.2.8 private AlgebraicSimplification() { }
51 cananian 1.1.2.8
52 cananian 1.1.2.8 private final static List _DEFAULT_RULES = new ArrayList();
53 cananian 1.1.2.8 /** Default alegraic simplification rules. */
54 cananian 1.1.2.8 public final static List DEFAULT_RULES = // protect the rules list.
55 cananian 1.1.2.8 Collections.unmodifiableList(_DEFAULT_RULES);
56 cananian 1.1.2.8
57 cananian 1.1.2.8 /** Code factory for applying the default set of simplifications to
58 cananian 1.1.2.8 * the given tree form. Clones the tree before simplifying it
59 cananian 1.1.2.8 * in-place. */
60 cananian 1.1.2.8 public static HCodeFactory codeFactory(final HCodeFactory parent) {
61 cananian 1.1.2.8 return codeFactory(parent, DEFAULT_RULES);
62 cananian 1.1.2.8 }
63 duncan 1.1.2.1
64 duncan 1.1.2.1 // Static initialization: add all available rules to the rule set.
65 duncan 1.1.2.1 //
66 duncan 1.1.2.1 static {
67 cananian 1.5 // -K1 --> K2
68 cananian 1.5 // ~K1 --> K2
69 cananian 1.5 // (byte)K1 --> K2
70 cananian 1.5 // (char)K1 --> K2
71 cananian 1.5 // (short)K1 --> K2
72 cananian 1.5 Rule simplifyConstants = new Rule("simplifyConstants") {
73 cananian 1.5 public boolean match(Exp e) {
74 cananian 1.5 if (_KIND(e) != _UNOP) { return false; }
75 cananian 1.5 else {
76 cananian 1.5 UNOP u = (UNOP)e;
77 cananian 1.5 return
78 cananian 1.5 (u.op==Uop.NEG || u.op==Uop.NOT ||
79 cananian 1.5 u.op==Uop.I2B || u.op==Uop.I2C || u.op==Uop.I2S) &&
80 cananian 1.5 contains(_KIND(u.getOperand()), _CONST) &&
81 cananian 1.5 (!u.isFloatingPoint()) &&
82 cananian 1.5 // 'null' is only pointer const but we can't be sure
83 cananian 1.5 // than null==0 (may have alternate value w/ pointer
84 cananian 1.5 // twiddling, etc).
85 cananian 1.5 u.getOperand().type() != Type.POINTER;
86 cananian 1.5 }
87 cananian 1.5 }
88 cananian 1.5
89 cananian 1.5 public Exp apply(TreeFactory tf, Exp e, DerivationGenerator dg) {
90 cananian 1.5 UNOP u = (UNOP)e;
91 cananian 1.5 CONST k1 = (CONST)u.getOperand();
92 cananian 1.5
93 cananian 1.5 Object k2 = harpoon.IR.Tree.UNOP.evalValue
94 cananian 1.5 (tf, u.op, u.optype, k1.value);
95 cananian 1.5
96 cananian 1.5
97 cananian 1.5 switch (u.type()) {
98 cananian 1.5 case Type.POINTER:
99 cananian 1.5 assert k1.type()==Type.INT;
100 cananian 1.5 case Type.INT:
101 cananian 1.5 return new CONST(tf,u,((Integer)k2).intValue());
102 cananian 1.5 case Type.LONG:
103 cananian 1.5 return new CONST(tf,u,((Long)k2).longValue());
104 cananian 1.5 default:
105 cananian 1.5 throw new Error("Invalid type: " + u.type());
106 cananian 1.5 }
107 cananian 1.5 }
108 cananian 1.5 };
109 cananian 1.5
110 duncan 1.1.2.1 // K1 + K2 --> K3
111 duncan 1.1.2.1 // K1 * K2 --> K3
112 duncan 1.1.2.1 // K1 << K2 --> K3
113 duncan 1.1.2.1 // K1 >> K2 --> K3
114 duncan 1.1.2.1 // K1 >>> K2 --> K3
115 duncan 1.1.2.1 // K1 & K2 --> K3
116 duncan 1.1.2.1 // K1 | K2 --> K3
117 duncan 1.1.2.1 // K1 ^ K2 --> K3
118 duncan 1.1.2.1 //
119 cananian 1.1.2.15 Rule combineConstants = new Rule("combineConstants") {
120 duncan 1.1.2.1 public boolean match(Exp e) {
121 duncan 1.1.2.1 if (_KIND(e) != _BINOP) { return false; }
122 duncan 1.1.2.1 else {
123 duncan 1.1.2.1 BINOP b = (BINOP)e;
124 duncan 1.1.2.1 return
125 cananian 1.1.2.13 contains(_OP(b.op),
126 cananian 1.1.2.13 _ADD|_MUL|_SHL|_SHR|_USHR|_AND|_OR|_XOR) &&
127 cananian 1.1.2.13 contains(_KIND(b.getLeft()), _CONST) &&
128 cananian 1.1.2.13 contains(_KIND(b.getRight()), _CONST) &&
129 cananian 1.1.2.25 (!b.isFloatingPoint()) &&
130 cananian 1.1.2.25 // 'null' is only pointer const but we can't be sure
131 cananian 1.1.2.25 // than null==0 (may have alternate value w/ pointer
132 cananian 1.1.2.25 // twiddling, etc).
133 cananian 1.1.2.26 b.getLeft().type() != Type.POINTER &&
134 cananian 1.1.2.26 b.getRight().type() != Type.POINTER;
135 duncan 1.1.2.1 }
136 duncan 1.1.2.1 }
137 duncan 1.1.2.1
138 cananian 1.1.2.16 public Exp apply(TreeFactory tf, Exp e, DerivationGenerator dg) {
139 duncan 1.1.2.1 BINOP b = (BINOP)e;
140 duncan 1.1.2.4 CONST k1 = (CONST)b.getLeft();
141 duncan 1.1.2.4 CONST k2 = (CONST)b.getRight();
142 duncan 1.1.2.1
143 duncan 1.1.2.1 Object k1pk2 = harpoon.IR.Tree.BINOP.evalValue
144 duncan 1.1.2.1 (tf, b.op, b.optype, k1.value, k2.value);
145 duncan 1.1.2.1
146 cananian 1.6 int ty = b.type();
147 cananian 1.6 if (ty==Type.POINTER)
148 cananian 1.6 ty = e.isDoubleWord() ? Type.LONG : Type.INT;
149 cananian 1.6 switch (ty) {
150 duncan 1.1.2.1 case Type.INT:
151 duncan 1.1.2.1 return new CONST(tf,b,((Integer)k1pk2).intValue());
152 duncan 1.1.2.1 case Type.LONG:
153 duncan 1.1.2.1 return new CONST(tf,b,((Long)k1pk2).longValue());
154 duncan 1.1.2.1 default:
155 cananian 1.1.2.9 throw new Error("Invalid type: " + b.type());
156 duncan 1.1.2.1 }
157 duncan 1.1.2.1 }
158 duncan 1.1.2.1 };
159 duncan 1.1.2.1
160 duncan 1.1.2.1 // const + exp --> exp + const
161 duncan 1.1.2.1 // const * exp --> exp * const
162 duncan 1.1.2.1 // const & exp --> exp & const
163 duncan 1.1.2.1 // const | exp --> exp | const
164 duncan 1.1.2.1 // const ^ exp --> exp ^ const
165 cananian 1.1.2.11 // const ==exp --> exp ==const
166 cananian 1.1.2.19 // const !=exp --> exp !=const
167 duncan 1.1.2.1 //
168 cananian 1.1.2.15 Rule commute = new Rule("commute") {
169 duncan 1.1.2.1 public boolean match(Exp e) {
170 duncan 1.1.2.1 if (_KIND(e) != _BINOP) { return false; }
171 duncan 1.1.2.1 else {
172 duncan 1.1.2.1 BINOP b = (BINOP)e;
173 duncan 1.1.2.1 return
174 cananian 1.1.2.19 Bop.isCommutative(b.op) &&
175 cananian 1.1.2.13 contains(_KIND(b.getLeft()), _CONST) &&
176 cananian 1.1.2.13 !contains(_KIND(b.getRight()), _CONST) &&
177 cananian 1.1.2.13 !b.isFloatingPoint();
178 duncan 1.1.2.1 }
179 duncan 1.1.2.1 }
180 cananian 1.1.2.16 public Exp apply(TreeFactory tf, Exp e, DerivationGenerator dg) {
181 duncan 1.1.2.1 BINOP b = (BINOP)e;
182 duncan 1.1.2.4 return new BINOP(tf, b, b.optype, b.op, b.getRight(), b.getLeft());
183 duncan 1.1.2.1 }
184 duncan 1.1.2.1 };
185 duncan 1.1.2.1
186 duncan 1.1.2.1
187 cananian 1.1.2.21 // const < exp --> exp > const
188 cananian 1.1.2.21 // const <=exp --> exp >=const
189 cananian 1.1.2.21 // const > exp --> exp < const
190 cananian 1.1.2.21 // const >=exp --> exp <=const
191 cananian 1.1.2.21 //
192 cananian 1.1.2.21 Rule commute2 = new Rule("commute2") {
193 cananian 1.1.2.21 public boolean match(Exp e) {
194 cananian 1.1.2.21 if (_KIND(e) != _BINOP) { return false; }
195 cananian 1.1.2.21 else {
196 cananian 1.1.2.21 BINOP b = (BINOP)e;
197 cananian 1.1.2.21 return
198 cananian 1.1.2.21 (b.op==Bop.CMPLT || b.op==Bop.CMPLE ||
199 cananian 1.1.2.21 b.op==Bop.CMPGT || b.op==Bop.CMPGE) &&
200 cananian 1.1.2.21 contains(_KIND(b.getLeft()), _CONST) &&
201 cananian 1.1.2.21 !contains(_KIND(b.getRight()), _CONST);
202 cananian 1.1.2.21 }
203 cananian 1.1.2.21 }
204 cananian 1.1.2.21 public Exp apply(TreeFactory tf, Exp e, DerivationGenerator dg) {
205 cananian 1.1.2.21 BINOP b = (BINOP)e;
206 cananian 1.1.2.21 int op;
207 cananian 1.1.2.21 switch(b.op) {
208 cananian 1.1.2.21 case Bop.CMPLT: op=Bop.CMPGT; break;
209 cananian 1.1.2.21 case Bop.CMPLE: op=Bop.CMPGE; break;
210 cananian 1.1.2.21 case Bop.CMPGE: op=Bop.CMPLE; break;
211 cananian 1.1.2.21 case Bop.CMPGT: op=Bop.CMPLT; break;
212 cananian 1.1.2.21 default: throw new Error("impossible");
213 cananian 1.1.2.21 }
214 cananian 1.1.2.21 return new BINOP(tf, b, b.optype, op, b.getRight(), b.getLeft());
215 cananian 1.1.2.21 }
216 cananian 1.1.2.21 };
217 cananian 1.1.2.21
218 cananian 1.1.2.21
219 cananian 1.1.2.11 // (exp + const) + const --> exp + (const + const)
220 cananian 1.1.2.11 // (exp * const) * const --> exp * (const * const)
221 cananian 1.1.2.11 // (exp & const) & const --> exp & (const & const)
222 cananian 1.1.2.11 // (exp | const) | const --> exp | (const | const)
223 cananian 1.1.2.11 // (exp ^ const) ^ const --> exp ^ (const ^ const)
224 cananian 1.1.2.11 // note that == is not associative.
225 cananian 1.1.2.15 Rule associate = new Rule("associate") {
226 cananian 1.1.2.11 public boolean match(Exp e) {
227 cananian 1.1.2.11 if (_KIND(e) != _BINOP) return false;
228 cananian 1.1.2.11 BINOP b1 = (BINOP) e;
229 cananian 1.1.2.11 if (_KIND(b1.getLeft()) != _BINOP) return false;
230 cananian 1.1.2.11 BINOP b2 = (BINOP) b1.getLeft();
231 cananian 1.1.2.11 if (b1.op != b2.op) return false;
232 cananian 1.1.2.11 return
233 cananian 1.1.2.13 contains(_OP(b1.op), _ADD|_MUL|_AND|_OR|_XOR) &&
234 cananian 1.1.2.13 contains(_KIND(b1.getRight()), _CONST) &&
235 cananian 1.1.2.13 contains(_KIND(b2.getRight()), _CONST) &&
236 cananian 1.1.2.11 (b1.operandType() == b2.operandType()) &&
237 cananian 1.1.2.13 !b1.isFloatingPoint();
238 cananian 1.1.2.11 }
239 cananian 1.1.2.16 public Exp apply(TreeFactory tf, Exp e, DerivationGenerator dg) {
240 cananian 1.1.2.11 BINOP b1 = (BINOP) e;
241 cananian 1.1.2.11 BINOP b2 = (BINOP) b1.getLeft();
242 cananian 1.1.2.11 int bop = b1.op, optype = b1.optype;
243 cananian 1.1.2.11 // be careful not to screw with commutativity.
244 cananian 1.1.2.11 return new BINOP(tf, e, optype, bop, b2.getLeft(),
245 cananian 1.1.2.11 new BINOP(tf, e, optype, bop,
246 cananian 1.1.2.11 b2.getRight(), b1.getRight()));
247 cananian 1.1.2.11 }
248 cananian 1.1.2.11 };
249 cananian 1.1.2.11
250 cananian 1.1.2.11
251 cananian 1.1.2.13 // exp & 0 --> 0
252 cananian 1.1.2.13 // exp * 0 --> 0
253 cananian 1.1.2.13 // exp % 1 --> 0
254 cananian 1.1.2.25 // (don't optimize '& null' case because not guaranteed that null==0)
255 cananian 1.1.2.13 //
256 cananian 1.1.2.15 Rule makeZero = new Rule("makeZero") {
257 cananian 1.1.2.17 // NOTE: this rule creates non-canonical tree form.
258 cananian 1.1.2.13 public boolean match(Exp e) {
259 cananian 1.1.2.13 if (_KIND(e) != _BINOP) { return false; }
260 cananian 1.1.2.13 else {
261 cananian 1.1.2.13 BINOP b = (BINOP)e;
262 cananian 1.1.2.13 if (b.type()!=Type.INT && b.type()!=Type.LONG)
263 cananian 1.1.2.13 return false;
264 cananian 1.1.2.13 // first the weird rem case
265 cananian 1.1.2.13 if (b.op == Bop.REM &&
266 cananian 1.1.2.13 contains(_KIND(b.getRight()), _CONST1)) return true;
267 cananian 1.1.2.13 // now 'operation with zero' cases
268 cananian 1.1.2.13 return contains(_OP(b.op), _AND|_MUL) &&
269 cananian 1.1.2.13 contains(_KIND(b.getRight()), _CONST0);
270 cananian 1.1.2.13 }
271 cananian 1.1.2.13 }
272 cananian 1.1.2.16 public Exp apply(TreeFactory tf, Exp e, DerivationGenerator dg) {
273 cananian 1.1.2.13 BINOP b = (BINOP)e;
274 cananian 1.1.2.17 CONST c;
275 cananian 1.1.2.13 if (b.type()==Type.INT)
276 cananian 1.1.2.17 c = new CONST(tf, e, (int) 0);
277 cananian 1.1.2.17 else if (b.type()==Type.LONG)
278 cananian 1.1.2.17 c = new CONST(tf, e, (long) 0);
279 cananian 1.1.2.17 else throw new Error("ack");
280 jwhaley 1.1.2.20 return new ESEQ(tf, b, new EXPR(tf, b, b.getLeft()), c);
281 cananian 1.1.2.13 }
282 cananian 1.1.2.13 };
283 cananian 1.1.2.13
284 cananian 1.1.2.13
285 duncan 1.1.2.1 // exp + 0 --> exp,
286 cananian 1.1.2.13 // exp | 0 --> exp,
287 cananian 1.1.2.13 // exp ^ 0 --> exp,
288 duncan 1.1.2.1 // exp << 0 --> exp,
289 duncan 1.1.2.1 // exp >> 0 --> exp,
290 duncan 1.1.2.1 // exp >>> 0 --> exp
291 cananian 1.1.2.13 // exp * 1 --> exp
292 cananian 1.1.2.13 // exp / 1 --> exp
293 cananian 1.1.2.25 // (don't optimize '+ null' case because not guaranteed that null==0)
294 duncan 1.1.2.1 //
295 cananian 1.1.2.15 Rule removeZero = new Rule("removeZero") {
296 duncan 1.1.2.1 public boolean match(Exp e) {
297 duncan 1.1.2.1 if (_KIND(e) != _BINOP) { return false; }
298 duncan 1.1.2.1 else {
299 duncan 1.1.2.1 BINOP b = (BINOP)e;
300 cananian 1.1.2.13 if (b.isFloatingPoint()) return false;
301 cananian 1.1.2.13 // first handle mul/div cases.
302 cananian 1.1.2.13 if (contains(_OP(b.op), _MUL|_DIV) &&
303 cananian 1.1.2.13 contains(_KIND(b.getRight()), _CONST1)) return true;
304 cananian 1.1.2.13 // now the 'operation-with-zero' cases.
305 duncan 1.1.2.1 return
306 cananian 1.1.2.13 contains(_OP(b.op), _ADD|_OR|_XOR|_SHL|_SHR|_USHR) &&
307 cananian 1.1.2.13 contains(_KIND(b.getRight()), _CONST0);
308 duncan 1.1.2.1 }
309 duncan 1.1.2.1 }
310 cananian 1.1.2.16 public Exp apply(TreeFactory tf, Exp e, DerivationGenerator dg) {
311 duncan 1.1.2.1 BINOP b = (BINOP)e;
312 duncan 1.1.2.4 return b.getLeft();
313 duncan 1.1.2.1 }
314 duncan 1.1.2.1 };
315 duncan 1.1.2.1
316 duncan 1.1.2.1
317 cananian 1.1.2.13 // x ^ -1 --> ~ x
318 cananian 1.1.2.13 //
319 cananian 1.1.2.15 Rule createNot = new Rule("createNot") {
320 cananian 1.1.2.13 // note that since Qop doesn't have NOT, we have to recreate it.
321 cananian 1.1.2.13 public boolean match(Exp e) {
322 cananian 1.1.2.13 if (_KIND(e) != _BINOP) return false;
323 cananian 1.1.2.13 BINOP b = (BINOP) e;
324 cananian 1.1.2.13 if (b.op != Bop.XOR ) return false;
325 cananian 1.1.2.13 return contains(_KIND(b.getRight()), _CONSTm1);
326 cananian 1.1.2.13 }
327 cananian 1.1.2.16 public Exp apply(TreeFactory tf, Exp e, DerivationGenerator dg) {
328 cananian 1.1.2.13 BINOP b = (BINOP) e;
329 cananian 1.3.2.1 assert b.op == Bop.XOR;
330 cananian 1.1.2.13 return new UNOP(tf, e, b.optype, Uop.NOT, b.getLeft());
331 cananian 1.1.2.13 }
332 cananian 1.1.2.13 };
333 cananian 1.1.2.13
334 cananian 1.1.2.13
335 duncan 1.1.2.1 // -(-i) --> i
336 cananian 1.1.2.13 // ~(~i) --> i
337 duncan 1.1.2.1 //
338 cananian 1.1.2.15 Rule doubleNegative = new Rule("doubleNegative") {
339 duncan 1.1.2.1 public boolean match(Exp e) {
340 duncan 1.1.2.1 if (_KIND(e) != _UNOP) { return false; }
341 duncan 1.1.2.1 else {
342 duncan 1.1.2.1 UNOP u1 = (UNOP)e;
343 duncan 1.1.2.4 if (_KIND(u1.getOperand()) != _UNOP) { return false; }
344 duncan 1.1.2.1 else {
345 duncan 1.1.2.4 UNOP u2 = (UNOP)u1.getOperand();
346 cananian 1.1.2.13 return (u1.op == Uop.NEG && u2.op == Uop.NEG) ||
347 cananian 1.1.2.13 (u1.op == Uop.NOT && u2.op == Uop.NOT);
348 duncan 1.1.2.1 }
349 duncan 1.1.2.1 }
350 duncan 1.1.2.1 }
351 cananian 1.1.2.16 public Exp apply(TreeFactory tf, Exp e, DerivationGenerator dg) {
352 duncan 1.1.2.1 UNOP u1 = (UNOP)e;
353 duncan 1.1.2.4 UNOP u2 = (UNOP)u1.getOperand();
354 cananian 1.3.2.1 assert u1.op == u2.op;
355 duncan 1.1.2.4 return u2.getOperand();
356 duncan 1.1.2.1 }
357 duncan 1.1.2.1 };
358 duncan 1.1.2.1
359 duncan 1.1.2.1 // -0 --> 0
360 duncan 1.1.2.1 //
361 cananian 1.1.2.15 Rule negZero = new Rule("negZero") {
362 duncan 1.1.2.1 public boolean match(Exp e) {
363 duncan 1.1.2.1 if (_KIND(e) != _UNOP) { return false; }
364 duncan 1.1.2.1 else {
365 duncan 1.1.2.1 UNOP u = (UNOP)e;
366 cananian 1.1.2.13 if (u.isFloatingPoint()) return false;
367 cananian 1.1.2.18 if (u.op != Uop.NEG) return false;
368 cananian 1.1.2.13 return contains(_KIND(u.getOperand()), _CONST0);
369 duncan 1.1.2.1 }
370 duncan 1.1.2.1 }
371 cananian 1.1.2.16 public Exp apply(TreeFactory tf, Exp e, DerivationGenerator dg) {
372 duncan 1.1.2.1 UNOP u = (UNOP)e;
373 cananian 1.3.2.1 assert contains(_KIND(u.getOperand()), _CONST0);
374 duncan 1.1.2.4 return u.getOperand();
375 duncan 1.1.2.1 }
376 duncan 1.1.2.1 };
377 duncan 1.1.2.1
378 cananian 1.1.2.13 // exp * const --> (recoded as shifts)
379 cananian 1.1.2.15 Rule mulToShift = new Rule("mulToShift") {
380 cananian 1.1.2.17 // NOTE: this rule may create non-canonical form.
381 duncan 1.1.2.1 public boolean match (Exp e) {
382 duncan 1.1.2.1 if (_KIND(e) != _BINOP) { return false; }
383 duncan 1.1.2.1 else {
384 duncan 1.1.2.1 BINOP b = (BINOP)e;
385 cananian 1.1.2.13 if (b.op != Bop.MUL) return false;
386 cananian 1.1.2.13 if (!contains(_KIND(b.getRight()), _CONST)) return false;
387 cananian 1.1.2.13 if (contains(_KIND(b.getLeft()), _CONST)) return false;
388 duncan 1.1.2.2 else {
389 duncan 1.1.2.4 CONST c = (CONST)b.getRight();
390 duncan 1.1.2.2 return
391 duncan 1.1.2.2 c.value.longValue() > 0 &&
392 duncan 1.1.2.2 !b.isFloatingPoint();
393 duncan 1.1.2.2 }
394 duncan 1.1.2.1 }
395 duncan 1.1.2.1 }
396 cananian 1.1.2.16 public Exp apply(TreeFactory tf, Exp e, DerivationGenerator dg) {
397 duncan 1.1.2.1 BINOP b = (BINOP)e;
398 duncan 1.1.2.4 return mul2shift(b.getLeft(), (CONST)b.getRight());
399 duncan 1.1.2.1 }
400 duncan 1.1.2.1 };
401 duncan 1.1.2.1
402 duncan 1.1.2.1
403 cananian 1.1.2.13 // exp / const --> (recoded as multiplication)
404 cananian 1.1.2.15 Rule divToMul = new Rule("divToMul") {
405 cananian 1.1.2.17 // NOTE: this rule may create non-canonical form.
406 duncan 1.1.2.1 public boolean match(Exp e) {
407 cananian 1.1.2.12 if (e.type() != Type.INT ) return false;
408 duncan 1.1.2.1 if (_KIND(e) != _BINOP) { return false; }
409 duncan 1.1.2.1 else {
410 duncan 1.1.2.1 BINOP b = (BINOP)e;
411 cananian 1.1.2.13 return b.op == Bop.DIV &&
412 cananian 1.1.2.13 contains(_KIND(b.getRight()), _CONST) &&
413 cananian 1.1.2.13 !contains(_KIND(b.getLeft()), _CONST);
414 duncan 1.1.2.1 }
415 duncan 1.1.2.1 }
416 cananian 1.1.2.16 public Exp apply(TreeFactory tf, Exp e, DerivationGenerator dg) {
417 duncan 1.1.2.1 BINOP b = (BINOP)e;
418 cananian 1.3.2.1 assert b.op == Bop.DIV;
419 cananian 1.1.2.22 return div2mul(b.getLeft(),
420 cananian 1.1.2.22 ((CONST)b.getRight()).value.intValue());
421 duncan 1.1.2.1 }
422 duncan 1.1.2.1 };
423 duncan 1.1.2.1
424 duncan 1.1.2.1 // Add rules to the rule set.
425 duncan 1.1.2.1 //
426 cananian 1.5 _DEFAULT_RULES.add(simplifyConstants);
427 cananian 1.1.2.8 _DEFAULT_RULES.add(combineConstants);
428 cananian 1.1.2.17 _DEFAULT_RULES.add(makeZero); // non-canonical
429 cananian 1.1.2.8 _DEFAULT_RULES.add(removeZero);
430 cananian 1.1.2.8 _DEFAULT_RULES.add(commute);
431 cananian 1.1.2.21 _DEFAULT_RULES.add(commute2);
432 cananian 1.1.2.11 _DEFAULT_RULES.add(associate);
433 cananian 1.1.2.13 _DEFAULT_RULES.add(createNot);
434 cananian 1.1.2.8 _DEFAULT_RULES.add(doubleNegative);
435 cananian 1.1.2.8 _DEFAULT_RULES.add(negZero);
436 cananian 1.1.2.17 _DEFAULT_RULES.add(mulToShift); // non-canonical
437 cananian 1.1.2.24 _DEFAULT_RULES.add(divToMul); // non-canonical
438 cananian 1.1.2.17
439 cananian 1.1.2.17 // and re-canonicalize
440 cananian 1.1.2.17 _DEFAULT_RULES.addAll(Canonicalize.RULES);
441 duncan 1.1.2.1 }
442 duncan 1.1.2.1
443 duncan 1.1.2.1 //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//
444 duncan 1.1.2.1 // //
445 duncan 1.1.2.1 // Simplification Routines //
446 duncan 1.1.2.1 // //
447 duncan 1.1.2.1 //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//
448 duncan 1.1.2.1
449 duncan 1.1.2.1
450 duncan 1.1.2.1 /**
451 duncan 1.1.2.1 * Converts an arbitrary division by a constant into a series of
452 duncan 1.1.2.1 * multiplications, shifts, and bitwise operations. Based on the
453 duncan 1.1.2.1 * paper <i>Division by Invariant Integers using Multiplication</i>,
454 duncan 1.1.2.1 * by Granlund and Montgomery.
455 duncan 1.1.2.1 *
456 duncan 1.1.2.1 * This method is used internally by the
457 duncan 1.1.2.1 * <code>AlgebraicSimplification</code> class. However, this method is
458 duncan 1.1.2.1 * public because it could conceivably be of use in other transformations.
459 duncan 1.1.2.1 *
460 duncan 1.1.2.1 * <b>Requires:</b> d is a 32-bit integer constant
461 duncan 1.1.2.1 *
462 duncan 1.1.2.1 * @return an Exp which contains no divisions, yet
463 duncan 1.1.2.1 * represents the same value as (n/d).
464 cananian 1.1.2.17 * not guaranteed to be in canonical form.
465 duncan 1.1.2.1 */
466 cananian 1.1.2.22 public static Exp div2mul(Exp n, int dVal) {
467 cananian 1.1.2.22 TreeFactory tf = n.getFactory();
468 cananian 1.1.2.22 // if d<0, n/d == -(n/|d|)
469 cananian 1.1.2.22 // note that we do NOT negate *n*, as that fails for n=-2^(N-1)
470 cananian 1.1.2.22 if (dVal < 0)
471 cananian 1.1.2.22 return new UNOP(tf, n, Type.INT, Uop.NEG,
472 cananian 1.1.2.22 div2mul_positive(n, -dVal));
473 cananian 1.1.2.22 else return div2mul_positive(n, dVal);
474 cananian 1.1.2.22 }
475 cananian 1.1.2.22 // input is positive now.
476 cananian 1.1.2.22 private static Exp div2mul_positive(Exp n, int dAbs) {
477 cananian 1.1.2.23 final int N=32;
478 cananian 1.3.2.1 assert dAbs >= 0;
479 duncan 1.1.2.1
480 duncan 1.1.2.1 // Get a TreeFactory to use in creating new tree objects
481 duncan 1.1.2.1 TreeFactory tf = n.getFactory();
482 duncan 1.1.2.1
483 cananian 1.1.2.22 if (dAbs == 0) { // Don't process div-by-0
484 cananian 1.1.2.22 return new BINOP(tf,n,Type.INT,Bop.DIV,n,new CONST(tf, n, dAbs));
485 duncan 1.1.2.1 }
486 duncan 1.1.2.1 else if (dAbs == 1) { // Dividing by 1
487 duncan 1.1.2.1 return n;
488 duncan 1.1.2.1 }
489 cananian 1.1.2.23 MultiplierTuple tuple = CHOOSE_MULTIPLIER(dAbs, N-1);
490 cananian 1.1.2.23 long m = tuple.m_high;
491 cananian 1.1.2.23 int sh_post = tuple.sh_post;
492 cananian 1.1.2.23 int l = tuple.l;
493 cananian 1.1.2.23
494 cananian 1.1.2.23 if (dAbs == (1 << l)) { // Dividing by a power of 2
495 cananian 1.1.2.23 return new BINOP(tf, n, Type.INT, Bop.SHR, n, new CONST(tf, n, l));
496 duncan 1.1.2.1 }
497 duncan 1.1.2.1 else {
498 cananian 1.3.2.1 assert m < (1L<<N);
499 cananian 1.1.2.17 // we need to reuse n.
500 cananian 1.1.2.17 Temp t = new Temp(tf.tempFactory(), "dm");
501 cananian 1.1.2.17 MOVE move = new MOVE(tf, n, new TEMP(tf, n, Type.INT, t), n);
502 cananian 1.1.2.23 // q0 = MULUH(m, EOR(n_sign,n))
503 cananian 1.1.2.23 Exp q0 = new UNOP
504 cananian 1.1.2.26 (tf, n, Type.LONG, Uop._2I,
505 duncan 1.1.2.1 new BINOP
506 cananian 1.1.2.23 (tf, n, Type.LONG, Bop.USHR,
507 cananian 1.1.2.23 new BINOP
508 cananian 1.1.2.23 (tf, n, Type.LONG, Bop.MUL,
509 cananian 1.1.2.23 new CONST(tf, n, m),
510 cananian 1.1.2.23 new UNOP
511 cananian 1.1.2.26 (tf, n, Type.INT, Uop._2L,
512 cananian 1.1.2.23 new BINOP
513 cananian 1.1.2.23 (tf, n, Type.INT, Bop.XOR,
514 cananian 1.1.2.23 new BINOP // n_sign = n >> N-1
515 cananian 1.1.2.23 (tf, n, Type.INT, Bop.SHR,
516 cananian 1.1.2.23 new TEMP(tf, n, Type.INT, t),
517 cananian 1.1.2.23 new CONST(tf, n, N-1)),
518 cananian 1.1.2.23 new TEMP(tf, n, Type.INT, t)))),
519 cananian 1.1.2.23 new CONST(tf, n, N)));
520 cananian 1.1.2.23 // q1 = EOR(n_sign, SRL(q0, sh_post))
521 cananian 1.1.2.23 Exp q1 = new BINOP
522 cananian 1.1.2.23 (tf, n, Type.INT, Bop.XOR,
523 cananian 1.1.2.23 new BINOP // n_sign = n >> N-1
524 cananian 1.1.2.23 (tf, n, Type.INT, Bop.SHR,
525 cananian 1.1.2.23 new TEMP(tf, n, Type.INT, t),
526 cananian 1.1.2.23 new CONST(tf, n, N-1)),
527 cananian 1.1.2.23 new BINOP // SRL(q0, sh_post)
528 cananian 1.1.2.23 (tf, n, Type.INT, Bop.USHR,
529 cananian 1.1.2.23 q0, new CONST(tf, n, sh_post)
530 cananian 1.1.2.23 ));
531 cananian 1.1.2.23 // done.
532 cananian 1.1.2.22 return new ESEQ(tf, n, move/* move n into t*/, q1);
533 duncan 1.1.2.1 }
534 duncan 1.1.2.1 }
535 cananian 1.1.2.23 private static class MultiplierTuple {
536 cananian 1.1.2.23 final long m_high; // range is 0 to 2^32
537 cananian 1.1.2.23 final int sh_post, l;
538 cananian 1.1.2.23 MultiplierTuple(long m_high, int sh_post, int l) {
539 cananian 1.1.2.23 this.m_high=m_high; this.sh_post=sh_post; this.l=l;
540 cananian 1.1.2.23 }
541 cananian 1.1.2.23 }
542 cananian 1.1.2.23 private static MultiplierTuple CHOOSE_MULTIPLIER(int d, int prec) {
543 cananian 1.1.2.23 final int N=32; // size of int.
544 cananian 1.3.2.1 assert 1<=d;
545 cananian 1.3.2.1 assert 1<=prec && prec<=N;
546 cananian 1.1.2.23 // Finds m, sh_post, l such that:
547 cananian 1.1.2.23 // 2^(l-1) < d <= 2^l
548 cananian 1.1.2.23 // 0 <= sh_post <= l. If sh_post>0, then N+sh_post <= l+prec
549 cananian 1.1.2.23 // 2^(N+sh_post) < m*d <= 2^(N+sh_post)*(1-2^(-prec))
550 cananian 1.1.2.23 // Corollary: If d<=2^prec, then
551 cananian 1.1.2.23 // m < 2^(N+sh_post)*(1+2^(1-l))/d <= 2^(N+sh_post-l+1).
552 cananian 1.1.2.23 // Hence m fits in max(prec, N-l)+1 bits (unsigned)
553 cananian 1.1.2.23 int l = Util.log2c(d), sh_post = l;
554 cananian 1.1.2.23 // m_low = floor((2^(N+l))/d)
555 cananian 1.1.2.23 // we compute it as m_low = 2^N + (m_low-2^N) to avoid overflow
556 cananian 1.1.2.23 // in the numerator.
557 cananian 1.1.2.24 long m_low = (1L<<N) + ((((1L<<l)-d)<<N)/d);
558 cananian 1.1.2.24 // m_high = floor((2^(N+l)+2^(N+l-prec))/d)
559 cananian 1.1.2.23 // as above, m_high = 2^N + (m_high-2^N) to avoid overflow.
560 cananian 1.1.2.23 long m_high= (1L<<N) +
561 cananian 1.1.2.24 ((((1L<<(l+prec))+(1L<<l)-(((long)d)<<prec))<<(N-prec))/d);
562 cananian 1.3.2.1 assert m_low < m_high;
563 cananian 1.1.2.23 while ((m_low/2) < (m_high/2) && sh_post > 0) {
564 cananian 1.1.2.23 m_low/=2; m_high/=2; sh_post--;
565 cananian 1.1.2.23 } /* reduce to lowest terms */
566 cananian 1.1.2.23 return new MultiplierTuple(m_high, sh_post, l); // 3 outputs
567 cananian 1.1.2.23 }
568 cananian 1.1.2.23
569 duncan 1.1.2.1 /**
570 duncan 1.1.2.1 * Converts an arbitrary multiplication by a positive constant into a
571 duncan 1.1.2.1 * series of shifts, additions, and multiplies. Based on the m4 macros
572 duncan 1.1.2.1 * found in the text <i>Sparc Architecture, Assembly Language,
573 duncan 1.1.2.1 * Programming, & C</i>, by Richard P. Paul.
574 duncan 1.1.2.1 *
575 duncan 1.1.2.1 * This method is used internally by the
576 duncan 1.1.2.1 * <code>AlgebraicSimplification</code> class. However, this method is
577 duncan 1.1.2.1 * public because it could conceivably be of use in other transformations.
578 duncan 1.1.2.1 *
579 duncan 1.1.2.2 * <b>Requires:</b> m is a <i>positive</i> 32-bit or 64-bit
580 duncan 1.1.2.2 * integer constant
581 duncan 1.1.2.1 *
582 duncan 1.1.2.1 * @return an Exp which contains no multiplications, yet
583 duncan 1.1.2.1 * represents the same value as (n*m).
584 duncan 1.1.2.1 */
585 duncan 1.1.2.1 public static Exp mul2shift(Exp n, CONST m) {
586 duncan 1.1.2.1 TreeFactory tf = n.getFactory();
587 duncan 1.1.2.1
588 duncan 1.1.2.2 int numbits = n.isDoubleWord() ? 64 : 32;
589 duncan 1.1.2.2 int ones = 0;
590 duncan 1.1.2.1 long multiplier = m.value.longValue();
591 duncan 1.1.2.1 Exp product = new CONST(tf, n, 0);
592 duncan 1.1.2.1
593 cananian 1.1.2.17 // copy to temp in case we need to reuse n.
594 cananian 1.1.2.17 Temp t = new Temp(tf.tempFactory(), "dm");
595 cananian 1.1.2.17 MOVE move = new MOVE(tf, n, new TEMP(tf, n, n.type(), t), n);
596 cananian 1.1.2.17 TEMP Tlast = null; // keep the last TEMP generated around.
597 cananian 1.1.2.17 int numuses = 0; // count how many times we've referenced TEMP t
598 cananian 1.1.2.17
599 duncan 1.1.2.1 for (int i=0; i<numbits; i++) {
600 duncan 1.1.2.1 int bitI = (int)((multiplier >> i) & 1);
601 duncan 1.1.2.2 if (bitI == 0) {
602 duncan 1.1.2.2 if (ones < 3) { // Not enough ones to warrant a booth recoding
603 duncan 1.1.2.2 for (int bit = i-ones; bit<i; bit++) {
604 cananian 1.1.2.17 Tlast = new TEMP(tf, n, n.type(), t); numuses++;
605 duncan 1.1.2.2 product = new BINOP
606 duncan 1.1.2.2 (tf, n, n.type(), Bop.ADD,
607 duncan 1.1.2.2 product,
608 duncan 1.1.2.2 new BINOP
609 duncan 1.1.2.2 (tf, n, n.type(), Bop.SHL,
610 cananian 1.1.2.17 Tlast,
611 duncan 1.1.2.2 new CONST(tf, n, bit)));
612 duncan 1.1.2.2 }
613 duncan 1.1.2.2 }
614 duncan 1.1.2.2 else { // In this case we will see gains from a booth recoding
615 cananian 1.1.2.17 Tlast = new TEMP(tf, n, n.type(), t); numuses++;
616 duncan 1.1.2.2 product = new BINOP
617 duncan 1.1.2.2 (tf, n, n.type(), Bop.ADD,
618 duncan 1.1.2.2 product,
619 duncan 1.1.2.2 new UNOP
620 duncan 1.1.2.2 (tf, n, n.type(), Uop.NEG,
621 duncan 1.1.2.2 new BINOP
622 duncan 1.1.2.2 (tf, n, n.type(), Bop.SHL,
623 cananian 1.1.2.17 Tlast,
624 duncan 1.1.2.2 new CONST(tf, n, i-ones))));
625 duncan 1.1.2.2
626 cananian 1.1.2.17 Tlast = new TEMP(tf, n, n.type(), t); numuses++;
627 duncan 1.1.2.2 product = new BINOP
628 duncan 1.1.2.2 (tf, n, n.type(), Bop.ADD,
629 duncan 1.1.2.2 product,
630 duncan 1.1.2.2 new BINOP
631 duncan 1.1.2.2 (tf, n, n.type(), Bop.SHL,
632 cananian 1.1.2.17 Tlast,
633 duncan 1.1.2.2 new CONST(tf, n, i)));
634 duncan 1.1.2.2 }
635 duncan 1.1.2.2 ones = 0; // Reset the count of ones.
636 duncan 1.1.2.2
637 duncan 1.1.2.2 } // if (bitI == 0) {
638 duncan 1.1.2.1 else {
639 duncan 1.1.2.2 // The current bit is a one. Increase the ones count.
640 duncan 1.1.2.2 ones++;
641 duncan 1.1.2.1 }
642 duncan 1.1.2.1 }
643 duncan 1.1.2.2
644 cananian 1.1.2.17 // either chain the MOVE together w/ the product, or replace
645 cananian 1.1.2.17 // the only TEMP with n.
646 jwhaley 1.1.2.20 if (numuses==0) return new ESEQ(tf, n, new EXPR(tf, n, n), product);
647 cananian 1.1.2.17 if (numuses==1) {
648 cananian 1.1.2.17 Tlast.replace(n); // replace TEMP(t) with n itself.
649 cananian 1.1.2.17 return product; // no need to separate variable.
650 cananian 1.1.2.17 }
651 cananian 1.1.2.17 return new ESEQ(tf, n, move, product); // move n into t, then compute.
652 duncan 1.1.2.1 }
653 cananian 1.2 }