1 cananian 1.1.2.1 // AlignmentAnalysis.java, created Thu Mar 14 01:19:55 2002 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.1 import harpoon.Analysis.ClassHierarchy;
7 cananian 1.1.2.1 import harpoon.Analysis.DomTree;
8 cananian 1.1.2.1 import harpoon.Analysis.ReachingDefs;
9 cananian 1.1.2.1 import harpoon.Analysis.ReachingDefsAltImpl;
10 cananian 1.1.2.1 import harpoon.Analysis.Maps.Derivation.DList;
11 cananian 1.1.2.1 import harpoon.Backend.Generic.Runtime.TreeBuilder;
12 cananian 1.1.2.1 import harpoon.ClassFile.HClass;
13 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
14 cananian 1.1.2.1 import harpoon.ClassFile.HCode.PrintCallback;
15 cananian 1.1.2.1 import harpoon.ClassFile.HCodeElement;
16 cananian 1.1.2.1 import harpoon.IR.Properties.CFGrapher;
17 cananian 1.1.2.1 import harpoon.IR.Properties.UseDefer;
18 cananian 1.1.2.1 import harpoon.IR.Tree.BINOP;
19 cananian 1.1.2.1 import harpoon.IR.Tree.Bop;
20 cananian 1.1.2.1 import harpoon.IR.Tree.CALL;
21 cananian 1.1.2.1 import harpoon.IR.Tree.CONST;
22 cananian 1.1.2.1 import harpoon.IR.Tree.Code;
23 cananian 1.1.2.1 import harpoon.IR.Tree.ESEQ;
24 cananian 1.1.2.1 import harpoon.IR.Tree.Exp;
25 cananian 1.1.2.1 import harpoon.IR.Tree.ExpList;
26 cananian 1.1.2.1 import harpoon.IR.Tree.INVOCATION;
27 cananian 1.1.2.1 import harpoon.IR.Tree.MEM;
28 cananian 1.1.2.1 import harpoon.IR.Tree.METHOD;
29 cananian 1.1.2.1 import harpoon.IR.Tree.MOVE;
30 cananian 1.1.2.1 import harpoon.IR.Tree.NAME;
31 cananian 1.1.2.1 import harpoon.IR.Tree.Print;
32 cananian 1.1.2.1 import harpoon.IR.Tree.Stm;
33 cananian 1.1.2.1 import harpoon.IR.Tree.TEMP;
34 cananian 1.1.2.1 import harpoon.IR.Tree.Tree;
35 cananian 1.1.2.1 import harpoon.IR.Tree.TreeDerivation;
36 cananian 1.1.2.1 import harpoon.IR.Tree.TreeKind;
37 cananian 1.1.2.1 import harpoon.IR.Tree.TreeVisitor;
38 cananian 1.1.2.1 import harpoon.IR.Tree.Type;
39 cananian 1.1.2.1 import harpoon.IR.Tree.UNOP;
40 cananian 1.1.2.1 import harpoon.IR.Tree.Uop;
41 cananian 1.1.2.1 import harpoon.Temp.Label;
42 cananian 1.1.2.1 import harpoon.Temp.Temp;
43 cananian 1.1.2.1
44 cananian 1.1.2.1 import java.util.Arrays;
45 cananian 1.1.2.1 import java.util.Collection;
46 cananian 1.1.2.1 import java.util.Collections;
47 cananian 1.1.2.1 import java.util.HashMap;
48 cananian 1.1.2.1 import java.util.HashSet;
49 cananian 1.1.2.1 import java.util.Iterator;
50 cananian 1.1.2.1 import java.util.List;
51 cananian 1.1.2.1 import java.util.Map;
52 cananian 1.1.2.1 import java.util.Set;
53 cananian 1.3
54 cananian 1.3 import net.cscott.jutil.GenericMultiMap;
55 cananian 1.3 import net.cscott.jutil.MultiMap;
56 cananian 1.3 import net.cscott.jutil.Default;
57 cananian 1.3 import net.cscott.jutil.Environment;
58 cananian 1.3 import net.cscott.jutil.HashEnvironment;
59 cananian 1.3 import net.cscott.jutil.Util;
60 cananian 1.3 import net.cscott.jutil.WorkSet;
61 cananian 1.1.2.1 /**
62 cananian 1.1.2.1 * <code>AlignmentAnalysis</code> computes the alignment
63 cananian 1.1.2.1 * (some offset modulo some number from some base) of every
64 cananian 1.1.2.1 * typed pointer in a Tree. It is a dataflow analysis.
65 cananian 1.1.2.1 *
66 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
67 cananian 1.4 * @version $Id: AlignmentAnalysis.java,v 1.4 2004/02/08 03:20:34 cananian Exp $
68 cananian 1.1.2.1 */
69 cananian 1.1.2.1 public class AlignmentAnalysis {
70 cananian 1.1.2.1
71 cananian 1.1.2.1 final ReachingDefs<Tree> rd;
72 cananian 1.1.2.1 final TreeDerivation td;
73 cananian 1.1.2.1 /** Creates a <code>AlignmentAnalysis</code>. */
74 cananian 1.1.2.1 public AlignmentAnalysis(Code c, CFGrapher<Tree> cfg, UseDefer<Tree> udr,
75 cananian 1.1.2.1 TreeDerivation td) {
76 cananian 1.1.2.1 this.rd = new ReachingDefsAltImpl<Tree>(c, cfg, udr);
77 cananian 1.1.2.1 this.td = td;
78 cananian 1.1.2.1 new StmVisitor(c, cfg, udr);
79 cananian 1.1.2.1 }
80 cananian 1.1.2.1 /* dataflow result accessor functions */
81 cananian 1.1.2.1 public Value valueOf(Exp e, Stm root) {
82 cananian 1.1.2.1 return new ValueVisitor(e, root).value;
83 cananian 1.1.2.1 }
84 cananian 1.1.2.1 /* temp x stm-to-value mapping */
85 cananian 1.1.2.1 private Map<Map.Entry<Temp,Stm>,Value> valueMap =
86 cananian 1.1.2.1 new HashMap<Map.Entry<Temp,Stm>,Value>();
87 cananian 1.1.2.1 public Value valueUseAt(Temp t, Stm s) {
88 cananian 1.1.2.1 Value v = Value.NOINFO;
89 cananian 1.1.2.1 Set<Tree> rdset=rd.reachingDefs(s, t);
90 cananian 1.1.2.1 for (Iterator<Tree> it=rdset.iterator(); it.hasNext(); )
91 cananian 1.1.2.1 v = v.unify(valueDefAt(t, (Stm)it.next()));
92 cananian 1.1.2.1 return v.fillKGroup(rdset, t);
93 cananian 1.1.2.1 }
94 cananian 1.1.2.1 public Value valueDefAt(Temp t, Stm s) {
95 cananian 1.1.2.1 Value v = valueMap.get(Default.entry(t,s));
96 cananian 1.1.2.1 return (v==null) ? Value.NOINFO : v;
97 cananian 1.1.2.1 }
98 cananian 1.1.2.1 /** visitor class to do dataflow through statements */
99 cananian 1.1.2.1 private class StmVisitor extends TreeVisitor {
100 cananian 1.1.2.1 MultiMap<Map.Entry<Temp,Stm>,Stm> uses =
101 cananian 1.1.2.1 new GenericMultiMap<Map.Entry<Temp,Stm>,Stm>();
102 cananian 1.1.2.1 WorkSet<Stm> ws = new WorkSet<Stm>();
103 cananian 1.1.2.1 StmVisitor(Code c, CFGrapher<Tree> cfg, UseDefer<Tree> udr) {
104 cananian 1.1.2.1 /* create uses map & add all elements to worklist. */
105 cananian 1.1.2.1 for (Iterator<Tree> it=cfg.getElements(c).iterator();
106 cananian 1.1.2.1 it.hasNext(); ) {
107 cananian 1.1.2.1 Stm s = (Stm) it.next();
108 cananian 1.4 for (Temp u : udr.useC(s)) {
109 cananian 1.1.2.1 for (Iterator<Tree> it3=rd.reachingDefs(s, u).iterator();
110 cananian 1.1.2.1 it3.hasNext(); ) {
111 cananian 1.1.2.1 Stm d = (Stm) it3.next();
112 cananian 1.1.2.1 uses.add(Default.entry(u,d), s);
113 cananian 1.1.2.1 }
114 cananian 1.1.2.1 }
115 cananian 1.1.2.1 // add all statements s to worklist.
116 cananian 1.1.2.1 ws.addLast(s);
117 cananian 1.1.2.1 }
118 cananian 1.1.2.1 /* for each element on the worklist... */
119 cananian 1.1.2.1 while (!ws.isEmpty()) {
120 cananian 1.1.2.1 Stm s = ws.removeFirst();
121 cananian 1.1.2.1 s.accept(this);
122 cananian 1.1.2.1 }
123 cananian 1.1.2.1 }
124 cananian 1.1.2.1 public void update(Temp t, Stm def, Value v) {
125 cananian 1.1.2.1 assert t!=null && def!=null && v!=null;
126 cananian 1.1.2.1 Map.Entry<Temp,Stm> pair = Default.entry(t, def);
127 cananian 1.1.2.1 Value old = valueMap.put(pair, v);
128 cananian 1.1.2.1 if (old==null || !old.equals(v))
129 cananian 1.1.2.1 //put uses of t on the workset.
130 cananian 1.1.2.1 for (Iterator<Stm> it = uses.getValues(pair).iterator();
131 cananian 1.1.2.1 it.hasNext(); )
132 cananian 1.1.2.1 ws.addLast(it.next());
133 cananian 1.1.2.1 }
134 cananian 1.1.2.1 public void visit(Tree e) { assert false; }
135 cananian 1.1.2.1 public void visit(Stm s) { /* no defs */ }
136 cananian 1.1.2.1 public void visit(INVOCATION s) {
137 cananian 1.1.2.1 TEMP t = s.getRetval();
138 cananian 1.1.2.1 if (t!=null)
139 cananian 1.1.2.1 update(t.temp, s,
140 cananian 1.1.2.1 new BaseAndOffset(new TempDefPoint(t, s), 0));
141 cananian 1.1.2.1 }
142 cananian 1.1.2.1 public void visit(CALL s) {
143 cananian 1.1.2.1 visit((INVOCATION)s);
144 cananian 1.1.2.1 TEMP t = s.getRetex();
145 cananian 1.1.2.1 update(t.temp, s,
146 cananian 1.1.2.1 new BaseAndOffset(new TempDefPoint(t, s), 0));
147 cananian 1.1.2.1 }
148 cananian 1.1.2.1 public void visit(METHOD s) {
149 cananian 1.1.2.1 for (int i=0; i<s.getParamsLength(); i++) {
150 cananian 1.1.2.1 TEMP t = s.getParams(i);
151 cananian 1.1.2.1 update(t.temp, s,
152 cananian 1.1.2.1 new BaseAndOffset(new TempDefPoint(t, s), 0));
153 cananian 1.1.2.1 }
154 cananian 1.1.2.1 }
155 cananian 1.1.2.1 public void visit(MOVE s) {
156 cananian 1.1.2.1 if (s.getDst().kind()==TreeKind.TEMP) {
157 cananian 1.1.2.1 TEMP t = (TEMP) s.getDst();
158 cananian 1.1.2.1 Value v = valueOf(s.getSrc(), s);
159 cananian 1.1.2.1 if (s.getDst().type()==Type.POINTER &&
160 cananian 1.1.2.1 v.isBaseKnown() &&
161 cananian 1.1.2.1 !((BaseAndOffset)v).def.isWellTyped())
162 cananian 1.1.2.1 update(t.temp, s,
163 cananian 1.1.2.1 new BaseAndOffset(new TempDefPoint(t, s),0));
164 cananian 1.1.2.1 else {
165 cananian 1.1.2.1 // if kgroup is unset, fill it now.
166 cananian 1.1.2.1 update(t.temp, s, v.fillKGroup(s, t.temp));
167 cananian 1.1.2.1 }
168 cananian 1.1.2.1 }
169 cananian 1.1.2.1 }
170 cananian 1.1.2.1 }
171 cananian 1.1.2.1 /** visitor class to compute Values of expression trees. */
172 cananian 1.1.2.1 private class ValueVisitor extends TreeVisitor {
173 cananian 1.1.2.1 final Stm root;
174 cananian 1.1.2.1 Value value;
175 cananian 1.1.2.1 ValueVisitor(Exp e, Stm root) {
176 cananian 1.1.2.1 this.root=root;
177 cananian 1.1.2.1 this.value= (e.type()==Type.INT || e.type()==Type.LONG)
178 cananian 1.1.2.1 ? Value.SOMEINT : Value.BOTTOM;
179 cananian 1.1.2.1 e.accept(this);
180 cananian 1.1.2.1 }
181 cananian 1.1.2.1 public void visit(Tree e) { assert false; }
182 cananian 1.1.2.1 public void visit(CONST c) {
183 cananian 1.1.2.1 if (c.type()==Type.INT || c.type()==Type.LONG)
184 cananian 1.1.2.1 this.value = new Constant(c.value().longValue());
185 cananian 1.1.2.1 }
186 cananian 1.1.2.1 public void visit(ESEQ e) {
187 cananian 1.1.2.1 this.value=valueOf(e.getExp(), root);
188 cananian 1.1.2.1 }
189 cananian 1.1.2.1 public void visit(MEM e) { /* bottom */ }
190 cananian 1.1.2.1 public void visit(NAME e) {
191 cananian 1.1.2.1 this.value = new BaseAndOffset(new NameDefPoint(e), 0);
192 cananian 1.1.2.1 }
193 cananian 1.1.2.1 public void visit(BINOP e) {
194 cananian 1.1.2.1 if (e.op==Bop.ADD) {
195 cananian 1.1.2.1 Value left = valueOf(e.getLeft(), root);
196 cananian 1.1.2.1 Value right= valueOf(e.getRight(), root);
197 cananian 1.1.2.1 this.value = left.add(right);
198 cananian 1.1.2.1 } else if (e.op==Bop.MUL) {
199 cananian 1.1.2.1 Value left = valueOf(e.getLeft(), root);
200 cananian 1.1.2.1 Value right= valueOf(e.getRight(), root);
201 cananian 1.1.2.1 this.value = left.mul(right);
202 cananian 1.1.2.1 } else if (e.op==Bop.SHL) {
203 cananian 1.1.2.1 Value left = valueOf(e.getLeft(), root);
204 cananian 1.1.2.1 Value right= valueOf(e.getRight(), root);
205 cananian 1.1.2.1 Value mult = (right instanceof Constant) ?
206 cananian 1.1.2.1 new Constant(1<<((Constant)right).number) :
207 cananian 1.1.2.1 Value.SOMEINT;
208 cananian 1.1.2.1 this.value = left.mul(mult);
209 cananian 1.1.2.1 }
210 cananian 1.1.2.1 }
211 cananian 1.1.2.1 public void visit(UNOP e) {
212 cananian 1.1.2.1 if (e.op==Uop.NEG) {
213 cananian 1.1.2.1 Value op = valueOf(e.getOperand(), root);
214 cananian 1.1.2.1 this.value = op.negate();
215 cananian 1.1.2.1 }
216 cananian 1.1.2.1 }
217 cananian 1.1.2.1 public void visit(TEMP t) {
218 cananian 1.1.2.1 this.value = valueUseAt(t.temp, root);
219 cananian 1.1.2.1 }
220 cananian 1.1.2.1 }
221 cananian 1.1.2.1 /* the value lattice: top/bottom, constants, and base pointers
222 cananian 1.1.2.1 * with known and unknown offsets, modulo a constant. */
223 cananian 1.1.2.1 // op rules: most specific is 'this'. base ptrs more spec than consts.
224 cananian 1.1.2.1 public static abstract class Value { // bottom/noinfo.
225 cananian 1.1.2.1 abstract protected int specificity();
226 cananian 1.1.2.2 public boolean isBaseKnown() { return false; }
227 cananian 1.1.2.2 public boolean isOffsetKnown() { return false; }
228 cananian 1.1.2.1 Value fillKGroup(Set defs, Temp t) { return this; }
229 cananian 1.1.2.1 final Value fillKGroup(Stm def, Temp t) {
230 cananian 1.1.2.1 return fillKGroup(Collections.singleton(def), t);
231 cananian 1.1.2.1 }
232 cananian 1.1.2.1 Value unify(Value v) {
233 cananian 1.1.2.1 assert this!=NOINFO;
234 cananian 1.1.2.1 if (v==NOINFO) return this;
235 cananian 1.1.2.1 return BOTTOM;
236 cananian 1.1.2.1 }
237 cananian 1.1.2.1 final Value add(Value v) {
238 cananian 1.1.2.1 return (this.specificity()>v.specificity()) ?
239 cananian 1.1.2.1 this._add(v) : v._add(this);
240 cananian 1.1.2.1 }
241 cananian 1.1.2.1 protected abstract Value _add(Value v);
242 cananian 1.1.2.1 final Value mul(Value v) {
243 cananian 1.1.2.1 return (this.specificity()>v.specificity()) ?
244 cananian 1.1.2.1 this._mul(v) : v._mul(this);
245 cananian 1.1.2.1 }
246 cananian 1.1.2.1 protected abstract Value _mul(Value v);
247 cananian 1.1.2.1 abstract Value negate();
248 cananian 1.1.2.1 static final Value BOTTOM = new Value() {
249 cananian 1.1.2.1 protected int specificity() { return 0; }
250 cananian 1.1.2.1 protected Value _add(Value v) { return BOTTOM; }
251 cananian 1.1.2.1 protected Value _mul(Value v) { return BOTTOM; }
252 cananian 1.1.2.1 Value negate() { return BOTTOM; }
253 cananian 1.1.2.1 public String toString() { return "BOTTOM"; }
254 cananian 1.1.2.1 };
255 cananian 1.1.2.1 static final Value SOMEINT = new IntegerValue();
256 cananian 1.1.2.1 static final Value NOINFO = new Value() {
257 cananian 1.1.2.1 protected int specificity() { return 5; }
258 cananian 1.1.2.1 Value unify(Value v) { return v; }
259 cananian 1.1.2.1 protected Value _add(Value v) { return NOINFO; }
260 cananian 1.1.2.1 protected Value _mul(Value v) { return NOINFO; }
261 cananian 1.1.2.1 Value negate() { return NOINFO; }
262 cananian 1.1.2.1 public String toString() { return "NO INFO"; }
263 cananian 1.1.2.1 };
264 cananian 1.1.2.1 }
265 cananian 1.1.2.1 public static class IntegerValue extends Value {
266 cananian 1.1.2.1 protected int specificity() { return 1; }
267 cananian 1.1.2.1 IntegerValue() {
268 cananian 1.1.2.1 assert this instanceof ConstantModuloN ||
269 cananian 1.1.2.1 Value.SOMEINT==null;
270 cananian 1.1.2.1 }
271 cananian 1.1.2.1 Value unify(Value v) {
272 cananian 1.1.2.1 if (!(v instanceof IntegerValue)) return super.unify(v);
273 cananian 1.1.2.1 // IntegerValue is common superclass of this and v.
274 cananian 1.1.2.1 return Value.SOMEINT;
275 cananian 1.1.2.1 }
276 cananian 1.1.2.1 protected Value _add(Value v) {
277 cananian 1.1.2.1 // must handle v=BOTTOM, v=SOMEINT
278 cananian 1.1.2.1 if (v instanceof IntegerValue) return Value.SOMEINT;
279 cananian 1.1.2.1 return Value.BOTTOM;
280 cananian 1.1.2.1 }
281 cananian 1.1.2.1 protected Value _mul(Value v) {
282 cananian 1.1.2.1 // must handle v=BOTTOM, v=SOMEINT
283 cananian 1.1.2.1 if (v instanceof IntegerValue) return Value.SOMEINT;
284 cananian 1.1.2.1 return Value.BOTTOM;
285 cananian 1.1.2.1 }
286 cananian 1.1.2.1 Value negate() { return this; }
287 cananian 1.1.2.1 public String toString() { return "X"; }
288 cananian 1.1.2.1 }
289 cananian 1.1.2.1 public static class ConstantModuloN extends IntegerValue {
290 cananian 1.1.2.1 protected int specificity() { return 2; }
291 cananian 1.1.2.2 public final long number; public final long modulus;
292 cananian 1.1.2.2 public final KGroup kgroup;
293 cananian 1.1.2.1 ConstantModuloN(long number, long modulus, KGroup kgroup) {
294 cananian 1.1.2.1 this.number=number; this.modulus=modulus; this.kgroup=kgroup;
295 cananian 1.1.2.1 assert modulus>1;
296 cananian 1.1.2.1 assert kgroup!=null || (number>=0 && number<modulus);
297 cananian 1.1.2.1 }
298 cananian 1.1.2.1 protected ConstantModuloN(long number) {
299 cananian 1.1.2.1 assert this instanceof Constant;
300 cananian 1.1.2.1 this.number=number; this.modulus=0; this.kgroup=null;
301 cananian 1.1.2.1 }
302 cananian 1.1.2.2 public boolean isOffsetKnown() { return true; }
303 cananian 1.1.2.1 Value fillKGroup(Set defs, Temp t) {
304 cananian 1.1.2.1 if (kgroup!=null || this instanceof Constant)
305 cananian 1.1.2.1 return this;
306 cananian 1.1.2.1 return new ConstantModuloN(mymod(number, modulus),modulus,
307 cananian 1.1.2.1 new KGroup(defs, t));
308 cananian 1.1.2.1 }
309 cananian 1.1.2.1 Value unify(Value v) {
310 cananian 1.1.2.1 if (!(v instanceof ConstantModuloN)) return super.unify(v);
311 cananian 1.1.2.1 // preserve k-group equality if this==v
312 cananian 1.1.2.1 if (this.equals(v)) return this;
313 cananian 1.1.2.1 // ConstantModuloN is common superclass of this and v.
314 cananian 1.1.2.1 ConstantModuloN large, small;
315 cananian 1.1.2.1 if (this.modulus > ((ConstantModuloN)v).modulus) {
316 cananian 1.1.2.1 large=this; small=(ConstantModuloN)v;
317 cananian 1.1.2.1 } else {
318 cananian 1.1.2.1 small=this; large=(ConstantModuloN)v;
319 cananian 1.1.2.1 }
320 cananian 1.1.2.1 assert large.modulus>0;
321 cananian 1.1.2.1 long off=0, mod=1;
322 cananian 1.1.2.1 if ((small.modulus==0 || small.modulus==large.modulus) &&
323 cananian 1.1.2.1 mymod(small.number, large.modulus) ==
324 cananian 1.1.2.1 mymod(large.number, large.modulus)) {//(a mod b) join c
325 cananian 1.1.2.1 off=large.number; mod=large.modulus;
326 cananian 1.1.2.1 } else if (small.modulus > 0) { // (a mod b) join (c mod d)
327 cananian 1.1.2.1 mod=Util.gcd(large.modulus, small.modulus);
328 cananian 1.1.2.1 if (large.number!=small.number)
329 cananian 1.1.2.1 mod=Util.gcd(mod, Math.abs(large.number-small.number));
330 cananian 1.1.2.1 off=small.number;
331 cananian 1.1.2.1 } // others?
332 cananian 1.1.2.1 if (mod>1)
333 cananian 1.1.2.1 return new ConstantModuloN(mymod(off,mod), mod, null);
334 cananian 1.1.2.1 // can't unify the constants.
335 cananian 1.1.2.1 return Value.SOMEINT;
336 cananian 1.1.2.1 }
337 cananian 1.1.2.1 protected Value _add(Value v) {
338 cananian 1.1.2.1 // must handle v=BOTTOM, SOMEINT, CONSTANTMODULON, CONSTANT
339 cananian 1.1.2.1 // and this=CONSTANTMODULON, CONSTANT
340 cananian 1.1.2.1 if (v==Value.BOTTOM) return v;
341 cananian 1.1.2.1 if (v==Value.SOMEINT) return Value.SOMEINT;
342 cananian 1.1.2.1 ConstantModuloN large, small;
343 cananian 1.1.2.1 if (this.modulus > ((ConstantModuloN)v).modulus) {
344 cananian 1.1.2.1 large=this; small=(ConstantModuloN)v;
345 cananian 1.1.2.1 } else {
346 cananian 1.1.2.1 small=this; large=(ConstantModuloN)v;
347 cananian 1.1.2.1 }
348 cananian 1.1.2.1 if (small.modulus>0) {// (a mod b)+(c mod d)
349 cananian 1.1.2.1 if (large.kgroup==small.kgroup && large.kgroup!=null)
350 cananian 1.1.2.1 // (a+k*b)+(c+k*d) = (a+c)+k*(b+d)
351 cananian 1.1.2.1 return new ConstantModuloN
352 cananian 1.1.2.1 (large.number+small.number,
353 cananian 1.1.2.1 large.modulus+small.modulus, large.kgroup);
354 cananian 1.1.2.1 // (a mod b)+(c mod d)=(a+c) mod gcd(b, d)
355 cananian 1.1.2.1 long mod = Util.gcd(small.modulus, large.modulus);
356 cananian 1.1.2.1 if (mod>1)
357 cananian 1.1.2.1 return new ConstantModuloN
358 cananian 1.1.2.1 (mymod(large.number+small.number,mod), mod, null);
359 cananian 1.1.2.1 } else if (large.modulus>0) { // (a mod b)+c
360 cananian 1.1.2.1 long off=large.number+small.number;
361 cananian 1.1.2.1 if (large.kgroup==null) off=mymod(off, large.modulus);
362 cananian 1.1.2.1 return new ConstantModuloN(off, large.modulus,
363 cananian 1.1.2.1 large.kgroup);
364 cananian 1.1.2.1 } else return new Constant(large.number+small.number);
365 cananian 1.1.2.1 return Value.SOMEINT;
366 cananian 1.1.2.1 }
367 cananian 1.1.2.1 protected Value _mul(Value v) {
368 cananian 1.1.2.1 // handles v=BOTTOM, v=SOMEINT, v=CONSTANTMODULON
369 cananian 1.1.2.1 if (v==Value.BOTTOM) return v;
370 cananian 1.1.2.1 if (v==Value.SOMEINT) {
371 cananian 1.1.2.1 // SOMEINT*(0 mod b) = 0 mod b
372 cananian 1.1.2.1 // SOMEINT*(a mod b) = 0 mod gcd(a,b)
373 cananian 1.1.2.1 if (this.number==0)
374 cananian 1.1.2.1 return new ConstantModuloN(0, this.modulus, null);
375 cananian 1.1.2.1 long mod = Util.gcd(this.number, this.modulus);
376 cananian 1.1.2.1 if (mod>1)
377 cananian 1.1.2.1 return new ConstantModuloN(0, mod, null);
378 cananian 1.1.2.1 return Value.SOMEINT;
379 cananian 1.1.2.1 }
380 cananian 1.1.2.1 ConstantModuloN cmn = (ConstantModuloN) v;
381 cananian 1.1.2.1 // (a mod b) * (c mod d) = (ac) mod gdb(b, d)
382 cananian 1.1.2.1 assert cmn.modulus>1 && this.modulus>1;
383 cananian 1.1.2.1 long mod = Util.gcd(this.modulus, cmn.modulus);
384 cananian 1.1.2.1 if (mod>1)
385 cananian 1.1.2.1 return new ConstantModuloN
386 cananian 1.1.2.1 (mymod(this.number*cmn.number,mod), mod, null);
387 cananian 1.1.2.1 else return Value.SOMEINT;
388 cananian 1.1.2.1 }
389 cananian 1.1.2.1 Value negate() {
390 cananian 1.1.2.1 return new ConstantModuloN(mymod(modulus-number,modulus),
391 cananian 1.1.2.1 modulus, null/*k'=-k*/);
392 cananian 1.1.2.1 }
393 cananian 1.1.2.1 public boolean equals(Object o) {
394 cananian 1.1.2.1 if (!(o instanceof ConstantModuloN)) return false;
395 cananian 1.1.2.1 ConstantModuloN cmn = (ConstantModuloN) o;
396 cananian 1.1.2.1 return (this.kgroup==null ? cmn.kgroup==null :
397 cananian 1.1.2.1 (cmn.kgroup!=null &&
398 cananian 1.1.2.1 this.kgroup.equals(cmn.kgroup))) &&
399 cananian 1.1.2.1 this.number == cmn.number &&
400 cananian 1.1.2.1 this.modulus == cmn.modulus;
401 cananian 1.1.2.1 }
402 cananian 1.1.2.1 public int hashCode() { return (int)number + 7*(int)modulus; }
403 cananian 1.1.2.1 public String toString() {
404 cananian 1.1.2.1 return number+((modulus==0)?"":(" mod "+modulus+" k:"+kgroup));
405 cananian 1.1.2.1 }
406 cananian 1.1.2.1 }
407 cananian 1.1.2.1 public static class Constant extends ConstantModuloN {
408 cananian 1.1.2.1 protected int specificity() { return 3; }
409 cananian 1.1.2.1 Constant(long number) { super(number); }
410 cananian 1.1.2.1 Value unify(Value v) {
411 cananian 1.1.2.1 if (!(v instanceof Constant)) return super.unify(v);
412 cananian 1.1.2.1 // Constant is common superclass of this and v.
413 cananian 1.1.2.1 Constant c = (Constant) v;
414 cananian 1.1.2.1 if (this.number==c.number)
415 cananian 1.1.2.1 return new Constant(this.number);
416 cananian 1.1.2.1 long small=Math.min(this.number, c.number);
417 cananian 1.1.2.1 long large=Math.max(this.number, c.number);
418 cananian 1.1.2.1 long mod=(large-small);
419 cananian 1.1.2.1 assert mymod(small, mod)==mymod(large, mod);
420 cananian 1.1.2.1 if (mod>1)
421 cananian 1.1.2.1 return new ConstantModuloN(mymod(small, mod), mod, null);
422 cananian 1.1.2.1 return Value.SOMEINT;
423 cananian 1.1.2.1 }
424 cananian 1.1.2.1 protected Value _mul(Value v) {
425 cananian 1.1.2.1 // must handle BOTTOM, SOMEINT, CONSTANTMODULON, CONSTANT
426 cananian 1.1.2.1 if (v==Value.BOTTOM) return v;
427 cananian 1.1.2.1 if (v==Value.SOMEINT) {
428 cananian 1.1.2.1 // SOMEINT * c = 0 mod c
429 cananian 1.1.2.1 if (this.number>1)
430 cananian 1.1.2.1 return new ConstantModuloN(0, this.number, null);
431 cananian 1.1.2.1 if (this.number<-1)
432 cananian 1.1.2.1 return new ConstantModuloN(0, -this.number, null)
433 cananian 1.1.2.1 .negate();
434 cananian 1.1.2.1 return Value.SOMEINT;
435 cananian 1.1.2.1 }
436 cananian 1.1.2.1 ConstantModuloN cmn = (ConstantModuloN) v;
437 cananian 1.1.2.1 if (cmn.modulus>1) {
438 cananian 1.1.2.1 long mult = Math.abs(this.number);
439 cananian 1.1.2.1 Value r = new ConstantModuloN(cmn.number*mult,
440 cananian 1.1.2.1 cmn.modulus*mult,
441 cananian 1.1.2.1 cmn.kgroup);
442 cananian 1.1.2.1 return (this.number>=0) ? r : r.negate();
443 cananian 1.1.2.1 }
444 cananian 1.1.2.1 assert cmn.modulus==0 && this.modulus==0;
445 cananian 1.1.2.1 return new Constant(cmn.number * this.number);
446 cananian 1.1.2.1 }
447 cananian 1.1.2.1 Value negate() { return new Constant(-this.number); }
448 cananian 1.1.2.1 }
449 cananian 1.1.2.1 public static class BaseAndOffset extends Value {
450 cananian 1.1.2.1 protected int specificity() { return 4; }
451 cananian 1.1.2.2 public final DefPoint def;
452 cananian 1.1.2.2 public final IntegerValue offset;
453 cananian 1.1.2.1 BaseAndOffset(DefPoint def, IntegerValue offset) {
454 cananian 1.1.2.1 this.def = def; this.offset = offset;
455 cananian 1.1.2.1 }
456 cananian 1.1.2.1 // special case:
457 cananian 1.1.2.1 BaseAndOffset(DefPoint def, long offset) {
458 cananian 1.1.2.1 this(def, new Constant(offset));
459 cananian 1.1.2.1 }
460 cananian 1.1.2.2 public boolean isBaseKnown() { return true; }
461 cananian 1.1.2.2 public boolean isOffsetKnown() { return offset.isOffsetKnown(); }
462 cananian 1.1.2.1 Value fillKGroup(Set defs, Temp t) {
463 cananian 1.1.2.1 return new BaseAndOffset(def, (IntegerValue)
464 cananian 1.1.2.1 offset.fillKGroup(defs, t));
465 cananian 1.1.2.1 }
466 cananian 1.1.2.1 Value unify(Value v) {
467 cananian 1.1.2.1 if (!(v instanceof BaseAndOffset)) return super.unify(v);
468 cananian 1.1.2.1 // BaseAndOffset is common superclass of this and v
469 cananian 1.1.2.1 BaseAndOffset ko = (BaseAndOffset) v;
470 cananian 1.1.2.1 if (this.def.equals(ko.def)) {
471 cananian 1.1.2.1 Value cc = this.offset.unify(ko.offset);
472 cananian 1.1.2.1 if (cc instanceof IntegerValue)
473 cananian 1.1.2.1 return new BaseAndOffset(def, (IntegerValue) cc);
474 cananian 1.1.2.1 }
475 cananian 1.1.2.1 return Value.BOTTOM;
476 cananian 1.1.2.1 }
477 cananian 1.1.2.1 protected Value _add(Value v) {
478 cananian 1.1.2.1 // must handle BOTTOM, SOMEINT, CMN, C, BAO
479 cananian 1.1.2.1 if (!(v instanceof IntegerValue)) return Value.BOTTOM;
480 cananian 1.1.2.1 Value cc = this.offset.add(v);
481 cananian 1.1.2.1 assert cc instanceof IntegerValue;
482 cananian 1.1.2.1 return new BaseAndOffset(def, (IntegerValue) cc);
483 cananian 1.1.2.1 }
484 cananian 1.1.2.1 protected Value _mul(Value v) {
485 cananian 1.1.2.1 // must handle BOTTOM, SOMEINT, CMN, C, BAO.
486 cananian 1.1.2.1 return Value.BOTTOM;
487 cananian 1.1.2.1 }
488 cananian 1.1.2.1 Value negate() { return Value.BOTTOM; }
489 cananian 1.1.2.1 public boolean equals(Object o) {
490 cananian 1.1.2.1 if (!(o instanceof BaseAndOffset)) return false;
491 cananian 1.1.2.1 BaseAndOffset bao = (BaseAndOffset) o;
492 cananian 1.1.2.1 return this.def.equals(bao.def) &&
493 cananian 1.1.2.1 this.offset.equals(bao.offset);
494 cananian 1.1.2.1 }
495 cananian 1.1.2.1 public int hashCode() {
496 cananian 1.1.2.1 return def.hashCode()+7*offset.hashCode();
497 cananian 1.1.2.1 }
498 cananian 1.1.2.1 public String toString() { return def+"+"+offset; }
499 cananian 1.1.2.1 }
500 cananian 1.1.2.1 // utility function
501 cananian 1.1.2.1 /** returns the positive value of a mod b, even when a is negative. */
502 cananian 1.1.2.1 private static long mymod(long a, long b) {
503 cananian 1.1.2.1 assert b>0;
504 cananian 1.1.2.1 long r = a % b;
505 cananian 1.1.2.1 return (r<0) ? (b+r) : r;
506 cananian 1.1.2.1 }
507 cananian 1.1.2.1 /*------------------------------------------------------------- */
508 cananian 1.1.2.1 /* both pointers in temps and pointer constants can be def points */
509 cananian 1.1.2.1 public abstract class DefPoint {
510 cananian 1.1.2.2 public abstract HClass type();
511 cananian 1.1.2.2 public final boolean isWellTyped() {
512 cananian 1.1.2.1 HClass hc=type();
513 cananian 1.1.2.1 return hc!=null && !hc.isPrimitive();
514 cananian 1.1.2.1 }
515 cananian 1.1.2.1 }
516 cananian 1.1.2.1 public class TempDefPoint extends DefPoint {
517 cananian 1.1.2.2 public final TEMP base; public final Stm def;
518 cananian 1.1.2.1 TempDefPoint(TEMP base, Stm def) { this.base=base; this.def=def; }
519 cananian 1.1.2.2 public HClass type() { return td.typeMap(base); }
520 cananian 1.1.2.1 public boolean equals(Object o) {
521 cananian 1.1.2.1 return o instanceof TempDefPoint &&
522 cananian 1.1.2.1 base.temp.equals(((TempDefPoint)o).base.temp) &&
523 cananian 1.1.2.1 def.equals(((TempDefPoint)o).def);
524 cananian 1.1.2.1 }
525 cananian 1.1.2.1 public int hashCode() {
526 cananian 1.1.2.1 return base.temp.hashCode() ^ def.hashCode();
527 cananian 1.1.2.1 }
528 cananian 1.1.2.1 public String toString() { return base.temp.toString(); }
529 cananian 1.1.2.1 }
530 cananian 1.1.2.1 public class NameDefPoint extends DefPoint {
531 cananian 1.1.2.2 public final NAME name;
532 cananian 1.1.2.1 NameDefPoint(NAME name) { this.name = name; }
533 cananian 1.1.2.1 public boolean equals(Object o) {
534 cananian 1.1.2.1 return o instanceof NameDefPoint &&
535 cananian 1.1.2.1 name.label.equals(((NameDefPoint)o).name.label);
536 cananian 1.1.2.1 }
537 cananian 1.1.2.2 public HClass type() { return td.typeMap(name); }
538 cananian 1.1.2.1 public int hashCode() { return name.label.hashCode(); }
539 cananian 1.1.2.1 public String toString() { return name.label.toString(); }
540 cananian 1.1.2.1 }
541 cananian 1.1.2.1
542 cananian 1.1.2.1 /** a k-group is a "phi-function" definition point. */
543 cananian 1.1.2.1 public static class KGroup {
544 cananian 1.1.2.1 final Set defs; final Temp t;
545 cananian 1.1.2.1 KGroup(Set defs, Temp t) { this.defs=defs; this.t=t; }
546 cananian 1.1.2.1 public String toString() { return "<"+t+","+defs+">"; }
547 cananian 1.1.2.1 public boolean equals(Object o) {
548 cananian 1.1.2.1 if (!(o instanceof KGroup)) return false;
549 cananian 1.1.2.1 KGroup kg = (KGroup) o;
550 cananian 1.1.2.1 return this.t.equals(kg.t) && this.defs.equals(kg.defs);
551 cananian 1.1.2.1 }
552 cananian 1.1.2.1 public int hashCode() { return t.hashCode() + 11*defs.hashCode(); }
553 cananian 1.1.2.1 }
554 cananian 1.2 }