1 cananian 1.1.2.1 // SCC.java, created Fri Sep 18 17:45:07 1998 by cananian
2 cananian 1.1.2.1 // Copyright (C) 1998 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.Quads.SCC;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.Analysis.Maps.ConstMap;
7 cananian 1.1.2.11 import harpoon.Analysis.Maps.ExactTypeMap;
8 cananian 1.1.2.1 import harpoon.Analysis.Maps.ExecMap;
9 cananian 1.1.2.1 import harpoon.Analysis.Maps.TypeMap;
10 cananian 1.1.2.1 import harpoon.Analysis.Maps.UseDefMap;
11 cananian 1.1.2.8 import harpoon.ClassFile.HClass;
12 cananian 1.1.2.8 import harpoon.ClassFile.HCode;
13 cananian 1.1.2.8 import harpoon.ClassFile.HCodeEdge;
14 cananian 1.1.2.8 import harpoon.ClassFile.HCodeElement;
15 cananian 1.1.2.8 import harpoon.ClassFile.HField;
16 cananian 1.1.2.8 import harpoon.ClassFile.HMethod;
17 cananian 1.1.2.8 import harpoon.ClassFile.Linker;
18 cananian 1.1.2.8 import harpoon.IR.Quads.AGET;
19 cananian 1.1.2.8 import harpoon.IR.Quads.ALENGTH;
20 cananian 1.1.2.8 import harpoon.IR.Quads.ANEW;
21 cananian 1.1.2.8 import harpoon.IR.Quads.ASET;
22 cananian 1.1.2.8 import harpoon.IR.Quads.CALL;
23 cananian 1.1.2.8 import harpoon.IR.Quads.CJMP;
24 cananian 1.1.2.8 import harpoon.IR.Quads.COMPONENTOF;
25 cananian 1.1.2.8 import harpoon.IR.Quads.CONST;
26 cananian 1.1.2.8 import harpoon.IR.Quads.Edge;
27 cananian 1.1.2.8 import harpoon.IR.Quads.FOOTER;
28 cananian 1.1.2.8 import harpoon.IR.Quads.GET;
29 cananian 1.1.2.8 import harpoon.IR.Quads.HEADER;
30 cananian 1.1.2.8 import harpoon.IR.Quads.INSTANCEOF;
31 cananian 1.1.2.8 import harpoon.IR.Quads.METHOD;
32 cananian 1.1.2.8 import harpoon.IR.Quads.MONITORENTER;
33 cananian 1.1.2.8 import harpoon.IR.Quads.MONITOREXIT;
34 cananian 1.1.2.8 import harpoon.IR.Quads.MOVE;
35 cananian 1.1.2.8 import harpoon.IR.Quads.NEW;
36 cananian 1.1.2.8 import harpoon.IR.Quads.NOP;
37 cananian 1.1.2.8 import harpoon.IR.Quads.OPER;
38 cananian 1.1.2.8 import harpoon.IR.Quads.OperVisitor;
39 cananian 1.1.2.8 import harpoon.IR.Quads.PHI;
40 cananian 1.1.2.8 import harpoon.IR.Quads.Qop;
41 cananian 1.1.2.8 import harpoon.IR.Quads.Quad;
42 cananian 1.1.2.8 import harpoon.IR.Quads.QuadSSI;
43 cananian 1.1.2.8 import harpoon.IR.Quads.QuadVisitor;
44 cananian 1.1.2.8 import harpoon.IR.Quads.RETURN;
45 cananian 1.1.2.8 import harpoon.IR.Quads.SET;
46 cananian 1.1.2.16 import harpoon.IR.Quads.SIGMA;
47 cananian 1.1.2.8 import harpoon.IR.Quads.SWITCH;
48 cananian 1.1.2.8 import harpoon.IR.Quads.THROW;
49 cananian 1.1.2.10 import harpoon.IR.Quads.TYPESWITCH;
50 cananian 1.1.2.1 import harpoon.Temp.Temp;
51 cananian 1.1.2.16 import harpoon.Temp.TempMap;
52 cananian 1.3.2.2 import harpoon.Util.ArrayIterator;
53 cananian 1.1.2.1 import harpoon.Util.HClassUtil;
54 cananian 1.1.2.1 import harpoon.Util.Worklist;
55 cananian 1.1.2.27 import harpoon.Util.Collections.WorkSet;
56 cananian 1.1.2.1
57 cananian 1.1.2.21 import java.util.Arrays;
58 cananian 1.1.2.1 import java.util.Enumeration;
59 cananian 1.1.2.9 import java.util.HashMap;
60 cananian 1.1.2.9 import java.util.HashSet;
61 cananian 1.3.2.2 import java.util.Iterator;
62 cananian 1.1.2.9 import java.util.Map;
63 cananian 1.1.2.9 import java.util.Set;
64 cananian 1.7
65 cananian 1.7 import net.cscott.jutil.Util;
66 cananian 1.1.2.1 /**
67 cananian 1.1.2.1 * <code>SCCAnalysis</code> implements Sparse Conditional Constant Propagation,
68 cananian 1.1.2.1 * with extensions to allow type and bitwidth analysis. Fun, fun, fun.
69 cananian 1.1.2.6 * <p>Only works with quads in SSI form.
70 cananian 1.1.2.1 *
71 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
72 cananian 1.7 * @version $Id: SCCAnalysis.java,v 1.7 2004/02/08 01:53:44 cananian Exp $
73 cananian 1.1.2.1 */
74 cananian 1.1.2.1
75 cananian 1.1.2.11 public class SCCAnalysis implements ExactTypeMap, ConstMap, ExecMap {
76 cananian 1.1.2.21 private final static boolean DEBUG=false;
77 cananian 1.1.2.7 final Linker linker;
78 cananian 1.1.2.1 UseDefMap udm;
79 cananian 1.1.2.1
80 cananian 1.1.2.1 /** Creates a <code>SCC</code>. */
81 cananian 1.1.2.1 public SCCAnalysis(HCode hc, UseDefMap usedef) {
82 cananian 1.3.2.1 assert hc.getName().equals(QuadSSI.codename);
83 cananian 1.1.2.7 this.linker = hc.getMethod().getDeclaringClass().getLinker();
84 cananian 1.1.2.1 this.udm = usedef;
85 cananian 1.1.2.1 analyze(hc);
86 cananian 1.1.2.21 // DEBUG:
87 cananian 1.1.2.21 if (DEBUG) hc.print(new java.io.PrintWriter(System.out),
88 cananian 1.1.2.21 new HCode.PrintCallback() {
89 cananian 1.1.2.21 public void printAfter(java.io.PrintWriter pw, HCodeElement hce) {
90 cananian 1.1.2.21 Quad q = (Quad) hce;
91 cananian 1.1.2.21 HashMap hm = new HashMap(V);
92 cananian 1.1.2.21 HashSet temps = new HashSet(Arrays.asList(q.use()));
93 cananian 1.1.2.21 temps.addAll(Arrays.asList(q.def()));
94 cananian 1.1.2.21 hm.keySet().retainAll(temps);
95 cananian 1.1.2.21 pw.println(hm);
96 cananian 1.1.2.21 }
97 cananian 1.1.2.21 });
98 cananian 1.1.2.1 }
99 cananian 1.1.2.1 /** Creates a <code>SCC</code>, and uses <code>UseDef</code> for the
100 cananian 1.1.2.1 * <code>UseDefMap</code>. */
101 cananian 1.1.2.1 public SCCAnalysis(HCode hc) {
102 cananian 1.1.2.1 this(hc, new harpoon.Analysis.UseDef());
103 cananian 1.1.2.1 }
104 cananian 1.1.2.1
105 cananian 1.1.2.1 /*-----------------------------*/
106 cananian 1.1.2.1 // Class state.
107 cananian 1.1.2.1 /** Set of all executable edges. */
108 cananian 1.1.2.1 Set Ee = new HashSet();
109 cananian 1.1.2.1 /** Set of all executable quads. */
110 cananian 1.1.2.1 Set Eq = new HashSet();
111 cananian 1.1.2.1 /** Mapping from <code>Temp</code>s to lattice values. */
112 cananian 1.1.2.9 Map V = new HashMap();
113 cananian 1.1.2.1
114 cananian 1.1.2.1 /*---------------------------*/
115 cananian 1.1.2.1 // public information accessor methods.
116 cananian 1.1.2.1
117 cananian 1.1.2.1 /** Determine whether <code>Quad</code> <code>q</code>
118 cananian 1.1.2.1 * is executable. */
119 cananian 1.1.2.1 public boolean execMap(HCodeElement quad) {
120 cananian 1.1.2.1 // ignore hc
121 cananian 1.1.2.1 return Eq.contains(quad);
122 cananian 1.1.2.1 }
123 cananian 1.1.2.1 /** Determine whether <code>Edge</code> <code>e</code>
124 cananian 1.1.2.1 * is executable. */
125 cananian 1.1.2.1 public boolean execMap(HCodeEdge edge) {
126 cananian 1.1.2.1 // ignore hc
127 cananian 1.1.2.1 return Ee.contains(edge);
128 cananian 1.1.2.1 }
129 cananian 1.1.2.1 /** Determine the static type of <code>Temp</code> <code>t</code> in
130 cananian 1.1.2.1 * <code>HMethod</code> <code>m</code>. */
131 cananian 1.1.2.1 public HClass typeMap(HCodeElement hce, Temp t) {
132 cananian 1.1.2.1 // ignore hce
133 cananian 1.1.2.1 LatticeVal v = (LatticeVal) V.get(t);
134 cananian 1.1.2.1 if (v instanceof xClass) return ((xClass)v).type();
135 cananian 1.1.2.1 return null;
136 cananian 1.1.2.1 }
137 cananian 1.1.2.11 /** Determine whether the static type of <code>Temp</code> <code>t</code>
138 cananian 1.1.2.11 * defined at <code>hce</code> is exact (or whether the runtime type
139 cananian 1.1.2.11 * could be a subclass of the static type). */
140 cananian 1.1.2.11 public boolean isExactType(HCodeElement hce, Temp t) {
141 cananian 1.1.2.11 // ignore hce
142 cananian 1.1.2.11 return V.get(t) instanceof xClassExact;
143 cananian 1.1.2.11 }
144 cananian 1.1.2.16 /** Determine whether the given <code>Temp</code> can possibly be
145 cananian 1.1.2.16 * <code>null</code>. */
146 cananian 1.1.2.16 public boolean isPossiblyNull(HCodeElement hce, Temp t) {
147 cananian 1.1.2.16 return !(V.get(t) instanceof xClassNonNull);
148 cananian 1.1.2.16 }
149 cananian 1.1.2.1 /** Determine whether <code>Temp</code> <code>t</code>
150 cananian 1.1.2.1 * has a constant value. */
151 cananian 1.1.2.1 public boolean isConst(HCodeElement hce, Temp t) {
152 cananian 1.1.2.1 // ignore hce -- this is SSA form
153 cananian 1.1.2.1 return (V.get(t) instanceof xConstant);
154 cananian 1.1.2.1 }
155 cananian 1.1.2.1 /** Determine the constant value of <code>Temp</code> <code>t</code>.
156 cananian 1.1.2.1 * @exception Error if <code>Temp</code> <code>t</code> is not a constant.
157 cananian 1.1.2.1 */
158 cananian 1.1.2.1 public Object constMap(HCodeElement hce, Temp t) {
159 cananian 1.1.2.1 // ignore hce -- this is SSA form.
160 cananian 1.1.2.1 LatticeVal v = (LatticeVal) V.get(t);
161 cananian 1.1.2.1 if (v instanceof xConstant) return ((xConstant)v).constValue();
162 cananian 1.1.2.1 throw new Error(t.toString() + " not a constant");
163 cananian 1.1.2.1 }
164 cananian 1.1.2.1
165 cananian 1.1.2.1 /** Determine the positive bit width of <code>Temp</code> <code>t</code>.
166 cananian 1.1.2.1 */
167 cananian 1.1.2.1 public int plusWidthMap(HCodeElement hce, Temp t) {
168 cananian 1.1.2.1 // ignore hce -- this is SSA form
169 cananian 1.1.2.1 LatticeVal v = (LatticeVal) V.get(t);
170 cananian 1.1.2.1 if (v==null) throw new Error("Unknown "+t);
171 cananian 1.1.2.1 xBitWidth bw = extractWidth(v);
172 cananian 1.1.2.1 return bw.plusWidth();
173 cananian 1.1.2.1 }
174 cananian 1.1.2.1 /** Determine the negative bit width of <code>Temp</code> <code>t</code>.
175 cananian 1.1.2.1 */
176 cananian 1.1.2.1 public int minusWidthMap(HCodeElement hce, Temp t) {
177 cananian 1.1.2.1 // ignore hce -- this is SSA form.
178 cananian 1.1.2.1 LatticeVal v = (LatticeVal) V.get(t);
179 cananian 1.1.2.1 if (v==null) throw new Error("Unknown "+t);
180 cananian 1.1.2.1 xBitWidth bw = extractWidth(v);
181 cananian 1.1.2.1 return bw.minusWidth();
182 cananian 1.1.2.1 }
183 cananian 1.1.2.1
184 cananian 1.1.2.1 /*---------------------------*/
185 cananian 1.1.2.1 // Analysis code.
186 cananian 1.1.2.1
187 cananian 1.1.2.1 /** Main analysis method. */
188 cananian 1.1.2.1 private void analyze(HCode hc) {
189 cananian 1.1.2.1 // Initialize worklists.
190 cananian 1.1.2.9 Worklist Wv = new WorkSet(); // variable worklist.
191 cananian 1.1.2.9 Worklist Wq = new WorkSet(); // block worklist.
192 cananian 1.1.2.1
193 cananian 1.1.2.1 // Make instance of visitor class.
194 cananian 1.1.2.1 SCCVisitor visitor = new SCCVisitor(hc, Wv, Wq);
195 cananian 1.1.2.1
196 cananian 1.1.2.1 // put the root entry on the worklist and mark it executable.
197 cananian 1.1.2.1 HCodeElement root = hc.getRootElement();
198 cananian 1.3.2.1 assert root instanceof Quad : "SCC analysis works only on QuadSSI form.";
199 cananian 1.1.2.1 Wq.push(root);
200 cananian 1.1.2.9 Eq.add(root);
201 cananian 1.1.2.1
202 cananian 1.1.2.1 // Iterate.
203 cananian 1.1.2.1 while (! (Wq.isEmpty() && Wv.isEmpty()) ) { // until both are empty.
204 cananian 1.1.2.1
205 cananian 1.1.2.1 if (!Wq.isEmpty()) { // grab statement from We if we can.
206 cananian 1.1.2.1 Quad q = (Quad) Wq.pull();
207 cananian 1.1.2.1 // Rule 2: for any executable block with
208 cananian 1.1.2.1 // only one successor C, set edge leading to C executable.
209 cananian 1.1.2.1 if (q.next().length==1) {
210 cananian 1.1.2.1 raiseE(Ee, Eq, Wq, q.nextEdge(0));
211 cananian 1.1.2.1 }
212 cananian 1.1.2.1 // check conditions 3-8 for q.
213 cananian 1.1.2.2 q.accept(visitor);
214 cananian 1.1.2.1 }
215 cananian 1.1.2.1
216 cananian 1.1.2.1 if (!Wv.isEmpty()) { // grab temp from Wv is possible.
217 cananian 1.1.2.1 Temp t = (Temp) Wv.pull();
218 cananian 1.1.2.1 // for every use of t...
219 cananian 1.3.2.2 for (Iterator it=new ArrayIterator(udm.useMap(hc, t));
220 cananian 1.3.2.2 it.hasNext(); )
221 cananian 1.1.2.1 // check conditions 3-8
222 cananian 1.3.2.2 ((Quad) it.next()).accept(visitor);
223 cananian 1.1.2.1 }
224 cananian 1.1.2.1 } // end while loop.
225 cananian 1.1.2.1 } // end analysis.
226 cananian 1.1.2.1
227 cananian 1.1.2.1 /*----------------------------------------*/
228 cananian 1.1.2.1 // raising values in the lattice:
229 cananian 1.1.2.1
230 cananian 1.1.2.1 /** Raise edge e in Ee/Eq, adding target q to Wq if necessary. */
231 cananian 1.1.2.1 void raiseE(Set Ee, Set Eq, Worklist Wq, Edge e) {
232 cananian 1.1.2.1 Quad q = (Quad) e.to();
233 cananian 1.1.2.28 if (Ee.add(e)) {
234 cananian 1.1.2.28 // if making this edge executable for the first time, verify
235 cananian 1.1.2.28 // that destination 'q' is marked executable, and add q to the
236 cananian 1.1.2.28 // work list to be looked at (may be a PHI, needs to be re-eval).
237 cananian 1.1.2.28 // NOTE that this works even if: quad's already been added
238 cananian 1.1.2.28 // to Eq (this may happen for PHIs) and even if this edge leads
239 cananian 1.1.2.28 // to itself (infinite loop in the program).
240 cananian 1.1.2.28 Eq.add(q);
241 cananian 1.1.2.28 Wq.push(q);
242 cananian 1.1.2.28 }
243 cananian 1.1.2.1 }
244 cananian 1.1.2.1 /** Raise element t to a in V, adding t to Wv if necessary. */
245 cananian 1.1.2.9 void raiseV(Map V, Worklist Wv, Temp t, LatticeVal a) {
246 cananian 1.1.2.1 LatticeVal old = (LatticeVal) V.get(t);
247 cananian 1.1.2.1 if (corruptor!=null) a=corruptor.corrupt(a); // support incrementalism
248 cananian 1.1.2.1 // only allow raising value in lattice.
249 cananian 1.1.2.21 if (old != null) {
250 cananian 1.1.2.21 a = a.merge(old);
251 cananian 1.1.2.21 if (old.equals(a) && a.equals(old)) return; // same old same old
252 cananian 1.1.2.21 }
253 cananian 1.1.2.1 V.put(t, a);
254 cananian 1.1.2.1 Wv.push(t);
255 cananian 1.1.2.1 }
256 cananian 1.1.2.1 /*------------------------------------------------------------*/
257 cananian 1.1.2.1 // VISITOR CLASS (the real guts of the routine)
258 cananian 1.1.2.1 class SCCVisitor extends QuadVisitor {
259 cananian 1.1.2.1 // local reference to HCode.
260 cananian 1.1.2.1 HCode hc;
261 cananian 1.1.2.1 // local references to worklists.
262 cananian 1.1.2.1 Worklist Wv, Wq;
263 cananian 1.1.2.1 // give us an OperVisitor class to go along with this.
264 cananian 1.1.2.1 OperVisitor opVisitor = new SCCOpVisitor();
265 cananian 1.1.2.1
266 cananian 1.1.2.1 SCCVisitor(HCode hc, Worklist Wv, Worklist Wq) {
267 cananian 1.1.2.1 this.hc = hc; this.Wv = Wv; this.Wq = Wq;
268 cananian 1.1.2.1 }
269 cananian 1.1.2.1
270 cananian 1.1.2.1 // utility functions.
271 cananian 1.1.2.1 LatticeVal get(Temp t) { return (LatticeVal) V.get(t); }
272 cananian 1.1.2.1
273 cananian 1.1.2.22 void handleSigmas(CJMP q, boolean falseTaken, boolean trueTaken) {
274 cananian 1.1.2.22 // for every sigma source:
275 cananian 1.1.2.22 for (int i=0; i < q.numSigmas(); i++) {
276 cananian 1.1.2.22 LatticeVal v = get( q.src(i) );
277 cananian 1.1.2.22 if (v == null) continue; // skip: insufficient info.
278 cananian 1.1.2.22 // check if this is the CJMP condition.
279 cananian 1.1.2.22 if (useSigmas && q.test() == q.src(i)) {
280 cananian 1.1.2.22 // we know that the conditional is zero on the false leg
281 cananian 1.1.2.22 if (falseTaken)
282 cananian 1.1.2.22 raiseV(V, Wv, q.dst(i,0),
283 cananian 1.1.2.22 new xIntConstant(toInternal(HClass.Boolean),0));
284 cananian 1.1.2.22 // CJMP test is possibly non-boolean, so we don't in fact
285 cananian 1.1.2.22 // know the value of the true side (except that it is
286 cananian 1.1.2.22 // non-zero)
287 cananian 1.1.2.22 if (trueTaken) raiseV(V, Wv, q.dst(i,1), v.rename(q, 1));
288 cananian 1.1.2.22 } else {
289 cananian 1.1.2.22 // fall back.
290 cananian 1.1.2.22 if (falseTaken) raiseV(V, Wv, q.dst(i,0), v.rename(q, 0));
291 cananian 1.1.2.22 if (trueTaken) raiseV(V, Wv, q.dst(i,1), v.rename(q, 1));
292 cananian 1.1.2.22 }
293 cananian 1.1.2.22 }
294 cananian 1.1.2.22 }
295 cananian 1.1.2.22 void handleSigmas(CJMP q, xInstanceofResult io,
296 cananian 1.1.2.22 boolean falseTaken, boolean trueTaken) {
297 cananian 1.1.2.1 // for every sigma source:
298 cananian 1.1.2.1 for (int i=0; i < q.numSigmas(); i++) {
299 cananian 1.1.2.1 // check if this is the CJMP condition.
300 cananian 1.1.2.1 if (q.test() == q.src(i)) { // known value after branch
301 cananian 1.1.2.22 if (falseTaken) raiseV(V, Wv, q.dst(i,0),
302 cananian 1.1.2.22 io.makeKnown(false).rename(q,0));
303 cananian 1.1.2.22 if (trueTaken) raiseV(V, Wv, q.dst(i,1),
304 cananian 1.1.2.22 io.makeKnown(true).rename(q,1));
305 cananian 1.1.2.1 continue; // go on.
306 cananian 1.1.2.1 }
307 cananian 1.1.2.1
308 cananian 1.1.2.1 LatticeVal v = get( q.src(i) );
309 cananian 1.1.2.1 if (v == null) continue; // skip: insufficient info.
310 cananian 1.1.2.1
311 cananian 1.1.2.1 // check to see if this is the temp tested by INSTANCEOF
312 cananian 1.1.2.16 if (q.src(i) == io.tested()) {
313 cananian 1.1.2.1 // no new info on false branch.
314 cananian 1.1.2.22 if (falseTaken)
315 cananian 1.1.2.22 raiseV(V, Wv, q.dst(i,0), v.rename(q, 0));
316 cananian 1.1.2.1 // we know q.dst[i][1] is INSTANCEOF def.hclass
317 cananian 1.1.2.1 // secret inside info: INSTANCEOF src is always non-null.
318 cananian 1.1.2.23 HClass hcI = io.def().hclass();
319 cananian 1.1.2.23 HClass hcV = ((xClass)v).type();
320 cananian 1.1.2.23 // use more specific type
321 cananian 1.1.2.23 if (!hcI.isInterface() && !hcV.isInterface() &&
322 cananian 1.1.2.23 hcI.isSuperclassOf(hcV))
323 cananian 1.1.2.23 hcI = hcV;
324 cananian 1.1.2.23 LatticeVal nv = new xClassNonNull(hcI);
325 cananian 1.1.2.23 // use more specific of original class, instanceof.
326 cananian 1.1.2.23 if (v.isLowerThan(nv)) nv = v;
327 cananian 1.1.2.22 if (trueTaken)
328 cananian 1.1.2.23 raiseV(V, Wv, q.dst(i,1), nv);
329 cananian 1.1.2.1 } else {
330 cananian 1.1.2.1 // fall back.
331 cananian 1.1.2.22 if (falseTaken) raiseV(V, Wv, q.dst(i,0), v.rename(q, 0));
332 cananian 1.1.2.22 if (trueTaken) raiseV(V, Wv, q.dst(i,1), v.rename(q, 1));
333 cananian 1.1.2.1 }
334 cananian 1.1.2.1 }
335 cananian 1.1.2.1 }
336 cananian 1.1.2.22 void handleSigmas(CJMP q, xOperBooleanResult or,
337 cananian 1.1.2.22 boolean falseTaken, boolean trueTaken) {
338 cananian 1.1.2.16 int opc = or.def().opcode();
339 cananian 1.1.2.16 int opa = or.operands().length;
340 cananian 1.1.2.16 LatticeVal left = opa<1?null:get(or.operands()[0]);
341 cananian 1.1.2.16 LatticeVal right= opa<2?null:get(or.operands()[1]);
342 cananian 1.1.2.1
343 cananian 1.1.2.1 // for every sigma source:
344 cananian 1.1.2.1 for (int i=0; i < q.numSigmas(); i++) {
345 cananian 1.1.2.1 // check if this is the CJMP condition.
346 cananian 1.1.2.1 if (q.test() == q.src(i)) {
347 cananian 1.1.2.22 if (falseTaken) raiseV(V, Wv, q.dst(i,0),
348 cananian 1.1.2.22 or.makeKnown(false).rename(q,0));
349 cananian 1.1.2.22 if (trueTaken) raiseV(V, Wv, q.dst(i,1),
350 cananian 1.1.2.22 or.makeKnown(true).rename(q,1));
351 cananian 1.1.2.1 continue; // go on.
352 cananian 1.1.2.1 }
353 cananian 1.1.2.1
354 cananian 1.1.2.1 LatticeVal v = get( q.src(i) );
355 cananian 1.1.2.1 if (v == null) continue; // skip: insufficient info.
356 cananian 1.1.2.1
357 cananian 1.1.2.1 // check to see if it comes from the OPER defining the boolean.
358 cananian 1.1.2.1 boolean handled = false;
359 cananian 1.1.2.22 boolean leftIsSource = false, swapped = false;
360 cananian 1.1.2.16 if (q.src(i) == or.operands()[0]) { // left is source.
361 cananian 1.1.2.22 leftIsSource = true;
362 cananian 1.1.2.22 } else if (q.src(i) == or.operands()[1]) { // right is source.
363 cananian 1.1.2.22 LatticeVal t = left; left = right; right = t;
364 cananian 1.1.2.22 leftIsSource = true; swapped = true;
365 cananian 1.1.2.22 }
366 cananian 1.1.2.22 if (leftIsSource) {
367 cananian 1.1.2.1 if (opc == Qop.ACMPEQ &&
368 cananian 1.1.2.1 left instanceof xClass && // not already xClassNonNull
369 cananian 1.1.2.22 (!(left instanceof xNullConstant)) &&
370 cananian 1.1.2.1 right instanceof xNullConstant) {
371 cananian 1.1.2.22 if (falseTaken)
372 cananian 1.1.2.22 raiseV(V, Wv, q.dst(i,0), // false branch: non-null
373 cananian 1.1.2.22 new xClassNonNull( ((xClass)left).type() ));
374 cananian 1.1.2.22 if (trueTaken)
375 cananian 1.1.2.22 raiseV(V, Wv, q.dst(i,1), // true branch: null
376 cananian 1.1.2.22 new xNullConstant() );
377 cananian 1.1.2.1 handled = true;
378 cananian 1.1.2.1 } else if ((opc == Qop.ICMPEQ || opc == Qop.LCMPEQ ||
379 cananian 1.1.2.1 opc == Qop.FCMPEQ || opc == Qop.DCMPEQ) &&
380 cananian 1.1.2.1 right instanceof xConstant) {
381 cananian 1.1.2.22 if (falseTaken)
382 cananian 1.1.2.22 raiseV(V, Wv, q.dst(i,0), // false branch: no info
383 cananian 1.1.2.22 left.rename(q, 0));
384 cananian 1.1.2.22 if (trueTaken)
385 cananian 1.1.2.22 raiseV(V, Wv, q.dst(i,1), // true branch: constant!
386 cananian 1.1.2.22 right.rename(q, 1));
387 cananian 1.1.2.1 handled = true;
388 cananian 1.1.2.22 } else if ((opc == Qop.ICMPGT || opc == Qop.LCMPGT ) &&
389 cananian 1.1.2.1 right instanceof xBitWidth) {
390 cananian 1.1.2.1 xBitWidth bw = (xBitWidth) right;
391 cananian 1.1.2.22 xBitWidth sr = extractWidth(left);
392 cananian 1.1.2.22 xBitWidth lessThan = new xBitWidth
393 cananian 1.1.2.22 (sr.type(),
394 cananian 1.1.2.22 sr.minusWidth(),
395 cananian 1.1.2.22 Math.min(sr.plusWidth(), bw.plusWidth()) );
396 cananian 1.1.2.22 xBitWidth greaterThan = new xBitWidth
397 cananian 1.1.2.22 (sr.type(),
398 cananian 1.1.2.22 Math.min(sr.minusWidth(),bw.minusWidth()),
399 cananian 1.1.2.22 sr.plusWidth() );
400 cananian 1.1.2.23 // use more specific of original class, xBitWidth.
401 cananian 1.1.2.23 if (left.isLowerThan(lessThan))
402 cananian 1.1.2.23 lessThan = (xBitWidth) left;
403 cananian 1.1.2.23 if (left.isLowerThan(greaterThan))
404 cananian 1.1.2.23 greaterThan = (xBitWidth) left;
405 cananian 1.1.2.1 // false branch:
406 cananian 1.1.2.22 if (falseTaken)
407 cananian 1.1.2.22 raiseV(V, Wv, q.dst(i,0),
408 cananian 1.1.2.22 swapped ? greaterThan : lessThan);
409 cananian 1.1.2.1 // true branch.
410 cananian 1.1.2.22 if (trueTaken)
411 cananian 1.1.2.22 raiseV(V, Wv, q.dst(i,1),
412 cananian 1.1.2.22 swapped ? lessThan : greaterThan);
413 cananian 1.1.2.1 handled = true;
414 cananian 1.1.2.1 }
415 cananian 1.1.2.1 }
416 cananian 1.1.2.1 // fall back.
417 cananian 1.1.2.1 if (!handled) {
418 cananian 1.1.2.22 if (falseTaken) raiseV(V, Wv, q.dst(i,0), v.rename(q, 0));
419 cananian 1.1.2.22 if (trueTaken) raiseV(V, Wv, q.dst(i,1), v.rename(q, 1));
420 cananian 1.1.2.1 }
421 cananian 1.1.2.1 }
422 cananian 1.1.2.1 }
423 cananian 1.1.2.1
424 cananian 1.1.2.1 // visitation.
425 cananian 1.1.2.1 public void visit(Quad q) { /* do nothing. */ }
426 cananian 1.1.2.1 public void visit(AGET q) {
427 cananian 1.1.2.1 LatticeVal v = get( q.objectref() );
428 cananian 1.1.2.22 if (corruptor==null)
429 cananian 1.3.2.1 assert v==null || v instanceof xClassNonNull;
430 cananian 1.1.2.1 if (v instanceof xClass)
431 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
432 cananian 1.1.2.1 new xClass( toInternal( ((xClass)v).type().getComponentType() ) ) );
433 cananian 1.1.2.1 }
434 cananian 1.1.2.1 public void visit(ALENGTH q) {
435 cananian 1.1.2.1 LatticeVal v = get( q.objectref() );
436 cananian 1.1.2.22 if (corruptor==null)
437 cananian 1.3.2.1 assert v==null || v instanceof xClassNonNull;
438 cananian 1.1.2.1 if (v instanceof xClassArray)
439 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
440 cananian 1.1.2.1 new xIntConstant(HClass.Int,
441 cananian 1.1.2.1 ((xClassArray)v).length() ) );
442 cananian 1.1.2.1 else if (v instanceof xClass) // length is non-negative.
443 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xBitWidth(HClass.Int, 0, 32) );
444 cananian 1.1.2.1 }
445 cananian 1.1.2.1 public void visit(ANEW q) { // dst of ANEW is non-null.
446 cananian 1.1.2.1 if (q.dimsLength()==1) {
447 cananian 1.1.2.1 LatticeVal v = get( q.dims(0) );
448 cananian 1.1.2.1 if (v instanceof xIntConstant) {
449 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
450 cananian 1.1.2.1 new xClassArray(q.hclass(),
451 cananian 1.1.2.1 (int) ((xIntConstant)v).value()) );
452 cananian 1.1.2.1 return;
453 cananian 1.1.2.1 } else if (v == null) return; // bottom.
454 cananian 1.1.2.1 }
455 cananian 1.1.2.11 raiseV(V, Wv, q.dst(), new xClassExact(q.hclass()) );
456 cananian 1.1.2.1 }
457 cananian 1.1.2.22 public void visit(ASET q) {
458 cananian 1.1.2.22 LatticeVal v = get( q.objectref() );
459 cananian 1.1.2.22 if (corruptor==null)
460 cananian 1.3.2.1 assert v==null || v instanceof xClassNonNull;
461 cananian 1.1.2.22 /* do nothing. */
462 cananian 1.1.2.22 }
463 cananian 1.1.2.1 public void visit(CALL q) {
464 cananian 1.1.2.22 if (corruptor==null)
465 cananian 1.3.2.1 assert (q.isVirtual() ?
466 cananian 1.1.2.22 get( q.params(0) )==null ||
467 cananian 1.3.2.1 get( q.params(0) ) instanceof xClassNonNull : true) : q;
468 cananian 1.1.2.1 if (q.retval() != null) {
469 cananian 1.1.2.1 // in the bytecode world, everything's an int.
470 cananian 1.1.2.1 HClass ty = q.method().getReturnType();
471 cananian 1.1.2.1 LatticeVal v = new xClass(toInternal(ty));
472 cananian 1.1.2.1 if (ty==HClass.Byte)
473 cananian 1.1.2.1 v = new xBitWidth(toInternal(HClass.Byte), 8, 7);
474 cananian 1.1.2.1 else if (ty==HClass.Short)
475 cananian 1.1.2.1 v = new xBitWidth(toInternal(HClass.Short), 16, 15);
476 cananian 1.1.2.1 else if (ty==HClass.Char)
477 cananian 1.1.2.1 v = new xBitWidth(toInternal(HClass.Char), 0, 16);
478 cananian 1.1.2.1 else if (ty==HClass.Boolean)
479 cananian 1.1.2.1 v = new xBitWidth(toInternal(HClass.Boolean),0, 1);
480 cananian 1.1.2.1 else if (ty.isPrimitive())
481 cananian 1.1.2.1 v = new xClassNonNull(toInternal(ty));
482 cananian 1.1.2.1 raiseV(V, Wv, q.retval(), v);
483 cananian 1.1.2.1 }
484 cananian 1.1.2.1 raiseV(V, Wv, q.retex(),
485 cananian 1.1.2.16 new xClassNonNull( linker.forName("java.lang.Throwable") ));
486 cananian 1.1.2.3 // both outgoing edges are potentially executable.
487 cananian 1.1.2.3 raiseE(Ee, Eq, Wq, q.nextEdge(1) );
488 cananian 1.1.2.3 raiseE(Ee, Eq, Wq, q.nextEdge(0) );
489 cananian 1.1.2.3 // handle SIGMAs
490 cananian 1.1.2.3 for (int i=0; i < q.numSigmas(); i++) {
491 cananian 1.1.2.3 // no q.src(x) should equal retval or retex...
492 cananian 1.1.2.3 // not that it would particularly break anything if it
493 cananian 1.1.2.3 // did.
494 cananian 1.1.2.3 LatticeVal v2 = get ( q.src(i) );
495 cananian 1.1.2.3 if (v2 != null) {
496 cananian 1.1.2.16 raiseV(V, Wv, q.dst(i, 0), v2.rename(q, 0));
497 cananian 1.1.2.16 raiseV(V, Wv, q.dst(i, 1), v2.rename(q, 1));
498 cananian 1.1.2.3 }
499 cananian 1.1.2.3 }
500 cananian 1.1.2.1 }
501 cananian 1.1.2.1 public void visit(CJMP q) {
502 cananian 1.1.2.1 // is test constant?
503 cananian 1.1.2.1 LatticeVal v = get( q.test() );
504 cananian 1.1.2.1 if (v instanceof xIntConstant) {
505 cananian 1.1.2.1 boolean test = ((xIntConstant)v).value()!=0;
506 cananian 1.1.2.1
507 cananian 1.1.2.1 if (test)
508 cananian 1.1.2.1 raiseE(Ee, Eq, Wq, q.nextEdge(1) ); // true edge.
509 cananian 1.1.2.1 else
510 cananian 1.1.2.1 raiseE(Ee, Eq, Wq, q.nextEdge(0) ); // false edge.
511 cananian 1.1.2.1 // handle sigmas.
512 cananian 1.1.2.22 if (useSigmas && v instanceof xOperBooleanResult)
513 cananian 1.1.2.22 handleSigmas((CJMP) q, (xOperBooleanResult)v,
514 cananian 1.1.2.22 !test, test);
515 cananian 1.1.2.22 else if (useSigmas && v instanceof xInstanceofResult)
516 cananian 1.1.2.22 handleSigmas((CJMP) q, (xInstanceofResult) v,
517 cananian 1.1.2.22 !test, test);
518 cananian 1.1.2.22 else // fallback.
519 cananian 1.1.2.22 handleSigmas((CJMP) q, !test, test);
520 cananian 1.1.2.1 return; // done.
521 cananian 1.1.2.1 } else if (v instanceof xClass) { // ie, not bottom.
522 cananian 1.1.2.1 // both edges are potentially executable.
523 cananian 1.1.2.1 raiseE(Ee, Eq, Wq, q.nextEdge(1) );
524 cananian 1.1.2.1 raiseE(Ee, Eq, Wq, q.nextEdge(0) );
525 cananian 1.1.2.1
526 cananian 1.1.2.1 // look at definition of boolean condition.
527 cananian 1.1.2.16 if (useSigmas && v instanceof xOperBooleanResult)
528 cananian 1.1.2.22 handleSigmas((CJMP) q, (xOperBooleanResult)v, true, true);
529 cananian 1.1.2.16 else if (useSigmas && v instanceof xInstanceofResult)
530 cananian 1.1.2.22 handleSigmas((CJMP) q, (xInstanceofResult) v, true, true);
531 cananian 1.1.2.1 else // fallback.
532 cananian 1.1.2.22 handleSigmas((CJMP) q, true, true);
533 cananian 1.1.2.1 }
534 cananian 1.1.2.1 }
535 cananian 1.1.2.1 public void visit(COMPONENTOF q) {
536 cananian 1.1.2.1 // we're guaranteed that q.arrayref is non-null here.
537 cananian 1.1.2.1 LatticeVal vA = get( q.arrayref() );
538 cananian 1.1.2.1 LatticeVal vO = get( q.objectref() );
539 cananian 1.1.2.1 if (vA instanceof xClass && vO instanceof xClass) {
540 cananian 1.1.2.1 HClass hcA = ((xClass) vA).type().getComponentType() ;
541 cananian 1.1.2.1 HClass hcO = ((xClass) vO).type();
542 cananian 1.1.2.1 if (hcA==null) { // can't prove type is array; usually this
543 cananian 1.1.2.1 // means we've turned useSigmas off.
544 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xBitWidth(toInternal(HClass.Boolean),0,1));
545 cananian 1.1.2.1 return;
546 cananian 1.1.2.1 }
547 cananian 1.1.2.1 hcA = toInternal(hcA); // normalize external types.
548 cananian 1.1.2.1 // special case when q.objectref is null
549 cananian 1.1.2.1 if (hcO == HClass.Void) // always true.
550 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xIntConstant(toInternal(HClass.Boolean),1));
551 cananian 1.1.2.23 else if (vA instanceof xClassExact &&
552 cananian 1.1.2.23 hcO.isInstanceOf(hcA)) // always true
553 cananian 1.1.2.23 raiseV(V, Wv, q.dst(), new xIntConstant(toInternal(HClass.Boolean),1));
554 cananian 1.1.2.23 else if (vO instanceof xClassExact &&
555 cananian 1.1.2.23 !hcO.isInstanceOf(hcA)) // always false
556 cananian 1.1.2.23 raiseV(V, Wv, q.dst(), new xIntConstant(toInternal(HClass.Boolean),0));
557 cananian 1.6 else if (hcA.isInterface() ||
558 cananian 1.6 hcO.isInterface() ||
559 cananian 1.6 hcO.isInstanceOf(hcA) ||
560 cananian 1.1.2.15 hcA.isInstanceOf(hcO)) // unknowable.
561 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xBitWidth(toInternal(HClass.Boolean),0,1));
562 cananian 1.1.2.1 else // always false.
563 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xIntConstant(toInternal(HClass.Boolean),0));
564 cananian 1.1.2.1 }
565 cananian 1.1.2.1 }
566 cananian 1.1.2.1 public void visit(CONST q) {
567 cananian 1.1.2.1 if (q.type() == HClass.Void) // null constant
568 cananian 1.1.2.1 raiseV(V,Wv, q.dst(), new xNullConstant() );
569 cananian 1.1.2.7 else if (q.type()==linker.forName("java.lang.String"))// string constant
570 cananian 1.1.2.1 raiseV(V,Wv, q.dst(), new xStringConstant(q.type(),q.value()));
571 cananian 1.1.2.1 else if (q.type()==HClass.Float || q.type()==HClass.Double) // f-p
572 cananian 1.1.2.1 raiseV(V,Wv, q.dst(), new xFloatConstant(q.type(),q.value()) );
573 cananian 1.1.2.1 else if (q.type()==HClass.Int || q.type() == HClass.Long)
574 cananian 1.1.2.1 raiseV(V,Wv, q.dst(),
575 cananian 1.1.2.1 new xIntConstant(q.type(),
576 cananian 1.1.2.1 ((Number)q.value()).longValue()));
577 cananian 1.1.2.13 else if (q.type()==linker.forName("java.lang.Class") ||
578 cananian 1.1.2.13 q.type()==linker.forName("java.lang.reflect.Field") ||
579 cananian 1.1.2.13 q.type()==linker.forName("java.lang.reflect.Method"))
580 cananian 1.1.2.13 raiseV(V,Wv, q.dst(), new xClassNonNull( q.type() ) );
581 cananian 1.1.2.1 else throw new Error("Unknown CONST type: "+q.type());
582 cananian 1.1.2.1 }
583 cananian 1.1.2.1 public void visit(FOOTER q) { /* do nothing. */ }
584 cananian 1.1.2.1 public void visit(GET q) {
585 cananian 1.1.2.22 if (corruptor==null)
586 cananian 1.3.2.1 assert (q.objectref()!=null ?
587 cananian 1.1.2.22 get(q.objectref())==null ||
588 cananian 1.3.2.1 get(q.objectref()) instanceof xClassNonNull : true) : q;
589 cananian 1.1.2.1 HClass type = toInternal(q.field().getType());
590 cananian 1.1.2.1 if (q.field().isConstant()) {
591 cananian 1.1.2.1 Object val = q.field().getConstant();
592 cananian 1.1.2.7 if (type == linker.forName("java.lang.String"))
593 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xStringConstant(type, val) );
594 cananian 1.1.2.1 else if (type == HClass.Float || type == HClass.Double )
595 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xFloatConstant(type, val) );
596 cananian 1.1.2.1 else if (type == HClass.Int || type == HClass.Long)
597 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
598 cananian 1.1.2.1 new xIntConstant(type,((Number)val).longValue() ) );
599 cananian 1.1.2.1 else throw new Error("Unknown constant field type: "+type);
600 cananian 1.1.2.1 } else raiseV(V, Wv, q.dst(), new xClass( type ) );
601 cananian 1.1.2.1 }
602 cananian 1.1.2.1 public void visit(HEADER q) {
603 cananian 1.1.2.1 // mark both edges executable.
604 cananian 1.1.2.1 raiseE(Ee, Eq, Wq, q.nextEdge(0));
605 cananian 1.1.2.1 raiseE(Ee, Eq, Wq, q.nextEdge(1));
606 cananian 1.1.2.1 }
607 cananian 1.1.2.1 public void visit(INSTANCEOF q) {
608 cananian 1.1.2.1 // no guarantee that src is not null.
609 cananian 1.1.2.1 LatticeVal v = get( q.src() );
610 cananian 1.1.2.4 if (v instanceof xNullConstant) // always false.
611 cananian 1.1.2.22 raiseV(V, Wv, q.dst(), new xInstanceofResultKnown(q,false));
612 cananian 1.6 else if (v instanceof xClassExact) { // always known.
613 cananian 1.6 HClass hcO = ((xClassNonNull)v).type();
614 cananian 1.6 assert !hcO.isInterface();//but can be an array type.
615 cananian 1.6 boolean result = hcO.isInstanceOf(q.hclass());
616 cananian 1.6 raiseV(V,Wv, q.dst(), new xInstanceofResultKnown(q,result));
617 cananian 1.6 }
618 cananian 1.1.2.1 else if (v instanceof xClassNonNull) { // analyzable
619 cananian 1.1.2.1 HClass hcO = ((xClassNonNull)v).type();
620 cananian 1.1.2.1 if (hcO.isInstanceOf(q.hclass())) // always true
621 cananian 1.1.2.22 raiseV(V,Wv, q.dst(), new xInstanceofResultKnown(q,true));
622 cananian 1.6 else if (q.hclass().isInterface() || hcO.isInterface() ||
623 cananian 1.6 q.hclass().isInstanceOf(hcO)) // unknowable.
624 cananian 1.1.2.22 raiseV(V,Wv, q.dst(), new xInstanceofResultUnknown(q));
625 cananian 1.1.2.1 else // always false.
626 cananian 1.1.2.22 raiseV(V,Wv, q.dst(), new xInstanceofResultKnown(q,false));
627 cananian 1.1.2.1 }
628 cananian 1.1.2.1 else if (v instanceof xClass) { // could be null.
629 cananian 1.1.2.1 HClass hcO = ((xClass)v).type();
630 cananian 1.6 if (q.hclass().isInterface() || hcO.isInterface() ||
631 cananian 1.6 q.hclass().isInstanceOf(hcO) ||
632 cananian 1.1.2.1 hcO.isInstanceOf(q.hclass()) ) // unknowable.
633 cananian 1.1.2.22 raiseV(V,Wv, q.dst(), new xInstanceofResultUnknown(q));
634 cananian 1.1.2.1 else // always false (even if src==null)
635 cananian 1.1.2.22 raiseV(V,Wv, q.dst(), new xInstanceofResultKnown(q,false));
636 cananian 1.1.2.1 }
637 cananian 1.1.2.1 }
638 cananian 1.1.2.1 public void visit(METHOD q) {
639 cananian 1.1.2.1 HMethod m = hc.getMethod();
640 cananian 1.1.2.1 HClass[] pt = m.getParameterTypes();
641 cananian 1.1.2.1 int j=0;
642 cananian 1.1.2.1 if (!m.isStatic() ) // raise 'this' variable (non-null!)
643 cananian 1.1.2.1 raiseV(V, Wv, q.params(j++),
644 cananian 1.1.2.1 new xClassNonNull( m.getDeclaringClass() ) );
645 cananian 1.1.2.1 for (int k=0; k < pt.length; j++, k++)
646 cananian 1.1.2.1 if (pt[k].isPrimitive())
647 cananian 1.1.2.1 raiseV(V, Wv, q.params(j), new xClassNonNull( toInternal(pt[k]) ) );
648 cananian 1.1.2.1 else
649 cananian 1.1.2.1 raiseV(V, Wv, q.params(j), new xClass( pt[k] ) );
650 cananian 1.1.2.1 }
651 cananian 1.1.2.22 public void visit(MONITORENTER q) {
652 cananian 1.1.2.22 LatticeVal v = get( q.lock() );
653 cananian 1.3.2.1 assert v==null || v instanceof xClassNonNull;
654 cananian 1.1.2.22 /* do nothing. */
655 cananian 1.1.2.22 }
656 cananian 1.1.2.22 public void visit(MONITOREXIT q) {
657 cananian 1.1.2.22 LatticeVal v = get( q.lock() );
658 cananian 1.3.2.1 assert v==null || v instanceof xClassNonNull;
659 cananian 1.1.2.22 /* do nothing. */
660 cananian 1.1.2.22 }
661 cananian 1.1.2.1 public void visit(MOVE q) {
662 cananian 1.1.2.1 LatticeVal v = get ( q.src() );
663 cananian 1.1.2.1 if (v != null)
664 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), v);
665 cananian 1.1.2.1 }
666 cananian 1.1.2.1 public void visit(NEW q) {
667 cananian 1.1.2.11 raiseV(V, Wv, q.dst(), new xClassExact( q.hclass() ) );
668 cananian 1.1.2.1 }
669 cananian 1.1.2.1 public void visit(NOP q) { /* do nothing. */ }
670 cananian 1.1.2.1 public void visit(OPER q) {
671 cananian 1.1.2.1 int opc = q.opcode();
672 cananian 1.1.2.1 boolean allConst = true;
673 cananian 1.1.2.1 boolean allWidth = true;
674 cananian 1.1.2.1
675 cananian 1.1.2.1 Object[] op = new Object[q.operandsLength()];
676 cananian 1.1.2.1 for (int i=0; i < q.operandsLength(); i++) {
677 cananian 1.1.2.1 LatticeVal v = get( q.operands(i) );
678 cananian 1.1.2.1 if (v==null) return; // can't eval yet.
679 cananian 1.1.2.1 if (v instanceof xConstant)
680 cananian 1.1.2.1 op[i] = ((xConstant)v).constValue();
681 cananian 1.1.2.1 else if (v instanceof xBitWidth)
682 cananian 1.1.2.1 allConst = false;
683 cananian 1.1.2.1 else
684 cananian 1.1.2.1 allConst = allWidth = false;
685 cananian 1.1.2.1 }
686 cananian 1.1.2.1 if (allConst) {
687 cananian 1.1.2.1 // RULE 3:
688 cananian 1.1.2.1 HClass ty = q.evalType();
689 cananian 1.1.2.1 Object o = q.evalValue(op);
690 cananian 1.1.2.1 if (ty == HClass.Boolean)
691 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
692 cananian 1.1.2.22 new xOperBooleanResultKnown
693 cananian 1.1.2.22 (q,((Boolean)o).booleanValue()));
694 cananian 1.1.2.1 else if (ty == HClass.Int || ty == HClass.Long)
695 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
696 cananian 1.1.2.1 new xIntConstant(ty, ((Number)o).longValue() ) );
697 cananian 1.1.2.1 else if (ty == HClass.Float || ty == HClass.Double)
698 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xFloatConstant(ty, o) );
699 cananian 1.1.2.1 else throw new Error("Unknown OPER result type: "+ty);
700 cananian 1.1.2.1 } else if ((allWidth) ||
701 cananian 1.1.2.1 opc == Qop.I2B || opc == Qop.I2C || opc == Qop.I2L ||
702 cananian 1.1.2.1 opc == Qop.I2S || opc == Qop.L2I) {
703 cananian 1.1.2.1 // do something intelligent with the bitwidths.
704 cananian 1.1.2.2 q.accept(opVisitor);
705 cananian 1.1.2.1 } else { // not all constant, not all known widths...
706 cananian 1.1.2.1 // special-case ACMPEQ x, null
707 cananian 1.1.2.1 if (opc == Qop.ACMPEQ &&
708 cananian 1.1.2.1 ((get( q.operands(0) ) instanceof xNullConstant &&
709 cananian 1.1.2.1 get( q.operands(1) ) instanceof xClassNonNull) ||
710 cananian 1.1.2.1 (get( q.operands(0) ) instanceof xClassNonNull &&
711 cananian 1.1.2.1 get( q.operands(1) ) instanceof xNullConstant) ) )
712 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), // always false.
713 cananian 1.1.2.22 new xOperBooleanResultKnown(q, false));
714 cananian 1.1.2.16 // special case boolean operations.
715 cananian 1.1.2.16 else if (opc == Qop.ACMPEQ ||
716 cananian 1.1.2.16 opc == Qop.DCMPEQ || opc == Qop.DCMPGE ||
717 cananian 1.1.2.16 opc == Qop.DCMPGT ||
718 cananian 1.1.2.16 opc == Qop.FCMPEQ || opc == Qop.FCMPGE ||
719 cananian 1.1.2.16 opc == Qop.FCMPGT ||
720 cananian 1.1.2.16 opc == Qop.ICMPEQ || opc == Qop.ICMPGT ||
721 cananian 1.1.2.16 opc == Qop.LCMPEQ || opc == Qop.LCMPGT)
722 cananian 1.1.2.22 raiseV(V, Wv, q.dst(), new xOperBooleanResultUnknown(q));
723 cananian 1.1.2.1 else {
724 cananian 1.1.2.1 // RULE 4:
725 cananian 1.1.2.1 HClass ty = q.evalType();
726 cananian 1.1.2.1 if (ty.isPrimitive())
727 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xClassNonNull( toInternal(ty) ) );
728 cananian 1.1.2.1 else
729 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xClass( ty ) );
730 cananian 1.1.2.1 }
731 cananian 1.1.2.1 }
732 cananian 1.1.2.1 }
733 cananian 1.1.2.1 public void visit(PHI q) {
734 cananian 1.1.2.1 for (int i=0; i<q.numPhis(); i++) { // for each phi-function.
735 cananian 1.1.2.21 LatticeVal merged = null;
736 cananian 1.1.2.1 for (int j=0; j < q.arity(); j++) {
737 cananian 1.1.2.1 if (!Ee.contains( q.prevEdge(j) ))
738 cananian 1.1.2.1 continue; // skip non-executable edges.
739 cananian 1.1.2.1 LatticeVal v = get ( q.src(i,j) );
740 cananian 1.1.2.1 if (v == null)
741 cananian 1.1.2.1 continue; // skip this arg function.
742 cananian 1.1.2.21 v = v.rename(q, j);
743 cananian 1.1.2.21 if (merged == null)
744 cananian 1.1.2.21 merged = v; // first valid value
745 cananian 1.1.2.21 else merged = merged.merge(v);
746 cananian 1.1.2.1 }
747 cananian 1.1.2.1 // assess results.
748 cananian 1.1.2.21 if (merged == null)
749 cananian 1.1.2.1 continue; // nothing to go on.
750 cananian 1.1.2.21 else raiseV(V, Wv, q.dst(i), merged);
751 cananian 1.1.2.1 } // for each phi function.
752 cananian 1.1.2.1 }
753 cananian 1.1.2.1 public void visit(RETURN q) { /* do nothing. */ }
754 cananian 1.1.2.22 public void visit(SET q) {
755 cananian 1.1.2.22 if (corruptor==null)
756 cananian 1.3.2.1 assert (q.objectref()!=null ?
757 cananian 1.1.2.22 get(q.objectref())==null ||
758 cananian 1.3.2.1 get(q.objectref()) instanceof xClassNonNull : true) : q;
759 cananian 1.1.2.22 /* do nothing. */
760 cananian 1.1.2.22 }
761 cananian 1.1.2.1 public void visit(SWITCH q) {
762 cananian 1.1.2.1 LatticeVal v = get( q.index() );
763 cananian 1.1.2.1 if (v instanceof xIntConstant) {
764 cananian 1.1.2.1 int index = (int) ((xIntConstant)v).value();
765 cananian 1.1.2.1 int i;
766 cananian 1.1.2.1 for (i=0; i<q.keysLength(); i++)
767 cananian 1.1.2.1 if (q.keys(i) == index)
768 cananian 1.1.2.1 break;
769 cananian 1.1.2.1 // now i has the target index, even for the default case.
770 cananian 1.1.2.1 raiseE(Ee, Eq, Wq, q.nextEdge(i) ); // executable edge.
771 cananian 1.1.2.1 // handle sigmas.
772 cananian 1.1.2.1 for (int j=0; j < q.numSigmas(); j++) {
773 cananian 1.1.2.1 LatticeVal v2 = get( q.src(j) );
774 cananian 1.1.2.1 if (v2 != null)
775 cananian 1.1.2.16 raiseV(V, Wv, q.dst(j,i), v2.rename(q,i));
776 cananian 1.1.2.1 }
777 cananian 1.1.2.1 }
778 cananian 1.1.2.1 else if (v != null) {
779 cananian 1.1.2.23 xBitWidth bw = extractWidth(v);
780 cananian 1.1.2.23 // mark some edges executable & propagate to all sigmas.
781 cananian 1.1.2.24 int executable=0;
782 cananian 1.1.2.23 for (int j=0; j < q.nextEdge().length; j++) {
783 cananian 1.1.2.24 if (j<q.keysLength()) { // non-default edge.
784 cananian 1.1.2.23 // learn stuff about cases from bitwidth of v.
785 cananian 1.1.2.23 int k = q.keys(j);
786 cananian 1.1.2.23 if (k>0 && Util.fls(k) > bw.plusWidth())
787 cananian 1.1.2.23 continue; // key too large to be selected.
788 cananian 1.1.2.23 if (k<0 && Util.fls(-k) > bw.minusWidth())
789 cananian 1.1.2.23 continue; // key too small to be selected.
790 cananian 1.1.2.24 executable++;
791 cananian 1.1.2.24 } else {
792 cananian 1.1.2.24 // pigeon-hole principle: default edge is executable
793 cananian 1.1.2.24 // iff number of executable edges (so far) is less
794 cananian 1.1.2.24 // than possible number of cases constrained by
795 cananian 1.1.2.24 // plusWidth and minusWidth.
796 cananian 1.1.2.24 // --- bail if plusWidth/minusWidth too large; we
797 cananian 1.1.2.24 // know (we hope!) that switch can't have this
798 cananian 1.1.2.24 // many edges.
799 cananian 1.1.2.24 if (bw.plusWidth<30 && bw.minusWidth<30) {
800 cananian 1.1.2.24 // number of cases is (2^pw + 2^mw)-1
801 cananian 1.1.2.24 // (don't count zero twice!)
802 cananian 1.1.2.24 long cases = -1 +
803 cananian 1.1.2.24 (1L<<bw.plusWidth()) + (1L<<bw.minusWidth());
804 cananian 1.3.2.1 assert executable<=cases;
805 cananian 1.1.2.24 if (executable==cases)
806 cananian 1.1.2.24 continue; // default not executable.
807 cananian 1.1.2.24 }
808 cananian 1.1.2.23 }
809 cananian 1.1.2.23 raiseE(Ee, Eq, Wq, q.nextEdge(j) );
810 cananian 1.1.2.23 for (int i=0; i < q.numSigmas(); i++) {
811 cananian 1.1.2.23 LatticeVal v2 = get( q.src(i) );
812 cananian 1.1.2.23 if (v2 != null)
813 cananian 1.1.2.16 raiseV(V, Wv, q.dst(i,j), v2.rename(q,j));
814 cananian 1.1.2.23 }
815 cananian 1.1.2.1 }
816 cananian 1.1.2.1 }
817 cananian 1.1.2.1 }
818 cananian 1.1.2.22 public void visit(THROW q) {
819 cananian 1.1.2.22 if (corruptor==null)
820 cananian 1.3.2.1 assert get(q.throwable())==null ||
821 cananian 1.3.2.1 get(q.throwable()) instanceof xClassNonNull;
822 cananian 1.1.2.22 /* do nothing. */
823 cananian 1.1.2.22 }
824 cananian 1.1.2.10 public void visit(TYPESWITCH q) {
825 cananian 1.1.2.10 LatticeVal v = get( q.index() );
826 cananian 1.1.2.10 if (v instanceof xClass) {
827 cananian 1.1.2.10 HClass type = ((xClass)v).type();
828 cananian 1.1.2.10 boolean catchAll = false;
829 cananian 1.1.2.10 for (int i=0; i<q.keysLength(); i++) {
830 cananian 1.1.2.10 if (type.isInstanceOf(q.keys(i))) {// catches all remaining
831 cananian 1.1.2.14 raiseE(Ee, Eq, Wq, q.nextEdge(i) );
832 cananian 1.1.2.10 catchAll = true;
833 cananian 1.1.2.10 break;
834 cananian 1.1.2.10 }
835 cananian 1.6 if (q.keys(i).isInterface() || type.isInterface() ||
836 cananian 1.6 q.keys(i).isInstanceOf(type)) // executable
837 cananian 1.6 raiseE(Ee, Eq, Wq, q.nextEdge(i) );
838 cananian 1.1.2.10 }
839 cananian 1.1.2.12 if ((!q.hasDefault()) ||
840 cananian 1.1.2.12 (catchAll && v instanceof xClassNonNull))
841 cananian 1.1.2.10 /* default edge never taken */;
842 cananian 1.1.2.10 else // make the default case executable.
843 cananian 1.1.2.10 raiseE(Ee, Eq, Wq, q.nextEdge(q.keysLength()));
844 cananian 1.1.2.10
845 cananian 1.1.2.10 // handle sigmas.
846 cananian 1.1.2.10 for (int i=0; i < q.arity(); i++) {
847 cananian 1.1.2.10 if (!Ee.contains(q.nextEdge(i))) continue;//only raise exec
848 cananian 1.1.2.10 for (int j=0; j < q.numSigmas(); j++) {
849 cananian 1.1.2.10 if (q.src(j)==q.index() && i<q.keysLength())
850 cananian 1.1.2.10 raiseV(V, Wv, q.dst(j,i),
851 cananian 1.1.2.10 new xClassNonNull(q.keys(i)));
852 cananian 1.1.2.10 else {
853 cananian 1.1.2.10 LatticeVal v2 = get( q.src(j) );
854 cananian 1.1.2.10 if (v2 != null)
855 cananian 1.1.2.16 raiseV(V, Wv, q.dst(j,i), v2.rename(q,i));
856 cananian 1.1.2.10 }
857 cananian 1.1.2.10 }
858 cananian 1.1.2.10 }
859 cananian 1.1.2.10 }
860 cananian 1.1.2.10 else if (v != null) {
861 cananian 1.1.2.10 // mark all edges executable & propagate to all sigmas.
862 cananian 1.1.2.12 for (int i=0; i < q.nextLength(); i++)
863 cananian 1.1.2.10 raiseE(Ee, Eq, Wq, q.nextEdge(i) );
864 cananian 1.1.2.10 for (int i=0; i < q.numSigmas(); i++) {
865 cananian 1.1.2.10 LatticeVal v2 = get( q.src(i) );
866 cananian 1.1.2.10 if (v2 != null)
867 cananian 1.1.2.10 for (int j=0; j < q.arity(); j++)
868 cananian 1.1.2.16 raiseV(V, Wv, q.dst(i,j), v2.rename(q,j));
869 cananian 1.1.2.10 }
870 cananian 1.1.2.10 }
871 cananian 1.1.2.10 }
872 cananian 1.1.2.1
873 cananian 1.1.2.1 /*------------------------------------------------------------*/
874 cananian 1.1.2.1 // VISITOR CLASS FOR OPER (ugh. lots of cases)
875 cananian 1.1.2.1 class SCCOpVisitor extends OperVisitor {
876 cananian 1.1.2.1
877 cananian 1.1.2.1 public void visit_default(OPER q) {
878 cananian 1.1.2.1 HClass ty = q.evalType();
879 cananian 1.1.2.1 if (ty.isPrimitive())
880 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xClassNonNull( toInternal(ty) ) );
881 cananian 1.1.2.1 else
882 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xClass( ty ) );
883 cananian 1.1.2.1 }
884 cananian 1.1.2.17 // comparisons
885 cananian 1.1.2.17 void visit_cmpeq(OPER q) {
886 cananian 1.1.2.17 xBitWidth left = extractWidth( get( q.operands(0) ) );
887 cananian 1.1.2.17 xBitWidth right= extractWidth( get( q.operands(1) ) );
888 cananian 1.1.2.17 // comparisons against a constant.
889 cananian 1.1.2.17 if ((left instanceof xIntConstant &&// left a constant and
890 cananian 1.1.2.17 ((left.minusWidth()==0 && // right smaller than left.
891 cananian 1.1.2.17 right.plusWidth() < left.plusWidth()) ||
892 cananian 1.1.2.17 (left.plusWidth()==0 &&
893 cananian 1.1.2.17 right.minusWidth() < left.minusWidth()))) || // or...
894 cananian 1.1.2.17 (right instanceof xIntConstant &&// right a constant and
895 cananian 1.1.2.17 ((right.minusWidth()==0 && // left smaller than right.
896 cananian 1.1.2.17 left.plusWidth() < right.plusWidth()) ||
897 cananian 1.1.2.17 (right.plusWidth()==0 &&
898 cananian 1.1.2.17 left.minusWidth() < right.minusWidth()))) )
899 cananian 1.1.2.17 // okay, comparison can never be true.
900 cananian 1.1.2.17 raiseV(V, Wv, q.dst(),
901 cananian 1.1.2.22 new xOperBooleanResultKnown(q,false));
902 cananian 1.1.2.17 else // okay, nothing known.
903 cananian 1.1.2.22 raiseV(V, Wv, q.dst(), new xOperBooleanResultUnknown(q));
904 cananian 1.1.2.17 }
905 cananian 1.1.2.17 public void visit_icmpeq(OPER q) { visit_cmpeq(q); }
906 cananian 1.1.2.17 public void visit_lcmpeq(OPER q) { visit_cmpeq(q); }
907 cananian 1.1.2.17 void visit_cmpgt(OPER q) {
908 cananian 1.1.2.17 xBitWidth left = extractWidth( get( q.operands(0) ) );
909 cananian 1.1.2.17 xBitWidth right= extractWidth( get( q.operands(1) ) );
910 cananian 1.1.2.17 // comparisons against a non-zero constant.
911 cananian 1.1.2.17 if ((left instanceof xIntConstant &&
912 cananian 1.1.2.17 ((xIntConstant)left).value()!=0 &&
913 cananian 1.1.2.17 left.plusWidth() > right.plusWidth()) ||
914 cananian 1.1.2.17 (right instanceof xIntConstant &&
915 cananian 1.1.2.17 ((xIntConstant)right).value()!=0 &&
916 cananian 1.1.2.17 right.minusWidth() > left.minusWidth()))
917 cananian 1.1.2.17 // comparison is always true
918 cananian 1.1.2.22 raiseV(V,Wv, q.dst(), new xOperBooleanResultKnown(q,true));
919 cananian 1.1.2.17 else if ((left instanceof xIntConstant &&
920 cananian 1.1.2.17 ((xIntConstant)left).value()!=0 &&
921 cananian 1.1.2.17 left.minusWidth() > right.minusWidth()) ||
922 cananian 1.1.2.17 (right instanceof xIntConstant &&
923 cananian 1.1.2.17 ((xIntConstant)right).value()!=0 &&
924 cananian 1.1.2.17 right.plusWidth() > left.plusWidth()))
925 cananian 1.1.2.17 // comparison is always false
926 cananian 1.1.2.22 raiseV(V,Wv, q.dst(),new xOperBooleanResultKnown(q,false));
927 cananian 1.1.2.17 // comparisons against zero.
928 cananian 1.1.2.17 else if ((left instanceof xIntConstant &&
929 cananian 1.1.2.17 ((xIntConstant)left).value()==0 &&
930 cananian 1.1.2.17 right.minusWidth()==0) ||
931 cananian 1.1.2.17 (right instanceof xIntConstant &&
932 cananian 1.1.2.17 ((xIntConstant)right).value()==0 &&
933 cananian 1.1.2.17 left.plusWidth()==0))
934 cananian 1.1.2.17 // comparison is always false. 0 > 0+ or 0- > 0
935 cananian 1.1.2.22 raiseV(V,Wv, q.dst(),new xOperBooleanResultKnown(q,false));
936 cananian 1.1.2.17 else // okay, nothing known.
937 cananian 1.1.2.22 raiseV(V, Wv, q.dst(), new xOperBooleanResultUnknown(q));
938 cananian 1.1.2.17 }
939 cananian 1.1.2.17 public void visit_icmpgt(OPER q) { visit_cmpgt(q); }
940 cananian 1.1.2.17 public void visit_lcmpgt(OPER q) { visit_cmpgt(q); }
941 cananian 1.1.2.17 // conversions
942 cananian 1.1.2.1 public void visit_i2b(OPER q) {
943 cananian 1.1.2.1 xBitWidth bw = extractWidth( get( q.operands(0) ) );
944 cananian 1.5 int mbw = bw.minusWidth(), pbw = bw.plusWidth();
945 cananian 1.5 if (bw.plusWidth>=8)
946 cananian 1.5 mbw = 8; // large + val may become large - val.
947 cananian 1.5 if (bw.minusWidth()>=8)
948 cananian 1.5 pbw = 7; // large - val may become large + val.
949 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
950 cananian 1.1.2.1 new xBitWidth(HClass.Int,
951 cananian 1.5 Math.min(8, mbw),
952 cananian 1.5 Math.min(7, pbw) ));
953 cananian 1.1.2.1 }
954 cananian 1.1.2.1 public void visit_i2c(OPER q) {
955 cananian 1.1.2.1 xBitWidth bw = extractWidth( get( q.operands(0) ) );
956 cananian 1.5 int mbw = bw.minusWidth(), pbw = bw.plusWidth();
957 cananian 1.5 if (bw.minusWidth()>0)
958 cananian 1.5 pbw = 16; // - val may become large + val.
959 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
960 cananian 1.1.2.1 new xBitWidth(HClass.Int, 0,
961 cananian 1.5 Math.min(16, pbw) ));
962 cananian 1.1.2.1 }
963 cananian 1.1.2.1 public void visit_i2l(OPER q) {
964 cananian 1.1.2.1 xBitWidth bw = extractWidth( get( q.operands(0) ) );
965 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
966 cananian 1.1.2.1 new xBitWidth(HClass.Long,
967 cananian 1.1.2.1 Math.min(32, bw.minusWidth()),
968 cananian 1.1.2.1 Math.min(31, bw.plusWidth()) ));
969 cananian 1.1.2.1 }
970 cananian 1.1.2.1 public void visit_i2s(OPER q) {
971 cananian 1.1.2.1 xBitWidth bw = extractWidth( get( q.operands(0) ) );
972 cananian 1.5 int mbw = bw.minusWidth(), pbw = bw.plusWidth();
973 cananian 1.5 if (bw.plusWidth>=16)
974 cananian 1.5 mbw = 16; // large + val may become large - val.
975 cananian 1.5 if (bw.minusWidth()>=16)
976 cananian 1.5 pbw = 15; // large - val may become large + val.
977 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
978 cananian 1.1.2.1 new xBitWidth(HClass.Int,
979 cananian 1.5 Math.min(16, mbw),
980 cananian 1.5 Math.min(15, pbw) ));
981 cananian 1.1.2.1 }
982 cananian 1.1.2.1 public void visit_l2i(OPER q) {
983 cananian 1.1.2.1 xBitWidth bw = extractWidth( get( q.operands(0) ) );
984 cananian 1.5 int mbw = bw.minusWidth(), pbw = bw.plusWidth();
985 cananian 1.5 if (bw.plusWidth>=32)
986 cananian 1.5 mbw = 32; // large + val may become large - val.
987 cananian 1.5 if (bw.minusWidth()>=32)
988 cananian 1.5 pbw = 31; // large - val may become large + val.
989 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
990 cananian 1.1.2.1 new xBitWidth(HClass.Int,
991 cananian 1.5 Math.min(32, mbw),
992 cananian 1.5 Math.min(31, pbw) ));
993 cananian 1.1.2.1 }
994 cananian 1.1.2.17 // binops
995 cananian 1.5 void visit_add(OPER q, int maxbits) {
996 cananian 1.1.2.1 xBitWidth left = extractWidth( get( q.operands(0) ) );
997 cananian 1.1.2.1 xBitWidth right= extractWidth( get( q.operands(1) ) );
998 cananian 1.1.2.1 int m = Math.max( left.minusWidth(), right.minusWidth() );
999 cananian 1.1.2.1 int p = Math.max( left.plusWidth(), right.plusWidth() );
1000 cananian 1.1.2.1 // zero plus zero is always zero, but other numbers grow.
1001 cananian 1.5 // also 0+x: x doesn't grow.
1002 cananian 1.5 if (left.minusWidth()>0 && right.minusWidth()>0) m++;
1003 cananian 1.5 if (left.plusWidth()>0 && right.plusWidth()>0) p++;
1004 cananian 1.5 // handle overflow.
1005 cananian 1.5 if (p >= maxbits)
1006 cananian 1.5 m = maxbits; // large + val becomes large - val.
1007 cananian 1.5 if (m >= maxbits)
1008 cananian 1.5 p = maxbits-1; // large - val becomes large + val.
1009 cananian 1.5 // okay, raise it!
1010 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1011 cananian 1.1.2.1 }
1012 cananian 1.5 public void visit_iadd(OPER q) { visit_add(q, 32); }
1013 cananian 1.5 public void visit_ladd(OPER q) { visit_add(q, 64); }
1014 cananian 1.1.2.1
1015 cananian 1.1.2.1 void visit_and(OPER q) {
1016 cananian 1.1.2.1 xBitWidth left = extractWidth( get( q.operands(0) ) );
1017 cananian 1.1.2.1 xBitWidth right= extractWidth( get( q.operands(1) ) );
1018 cananian 1.1.2.1 // if there are zero crossings, we have worst-case performance.
1019 cananian 1.1.2.1 int m = Math.max( left.minusWidth(), right.minusWidth() );
1020 cananian 1.1.2.1 int p = Math.max( left.plusWidth(), right.plusWidth() );
1021 cananian 1.1.2.1 // check for special positive-number cases.
1022 cananian 1.1.2.1 if (left.minusWidth()==0 && right.minusWidth()==0)
1023 cananian 1.1.2.1 p = Math.min( left.plusWidth(), right.plusWidth() );
1024 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1025 cananian 1.1.2.1 }
1026 cananian 1.1.2.1 public void visit_iand(OPER q) { visit_and(q); }
1027 cananian 1.1.2.1 public void visit_land(OPER q) { visit_and(q); }
1028 cananian 1.1.2.1
1029 cananian 1.1.2.1 void visit_div(OPER q) {
1030 cananian 1.1.2.1 // we can ignore divide-by-zero.
1031 cananian 1.1.2.1 xBitWidth left = extractWidth( get( q.operands(0) ) );
1032 cananian 1.1.2.1 xBitWidth right= extractWidth( get( q.operands(1) ) );
1033 cananian 1.1.2.1 // worst case: either number both pos and neg
1034 cananian 1.1.2.1 int m = Math.max(left.minusWidth(), left.plusWidth());
1035 cananian 1.1.2.1 int p = Math.max(left.minusWidth(), left.plusWidth());
1036 cananian 1.1.2.1 // check for special one-quadrant cases.
1037 cananian 1.1.2.1 if (left.minusWidth()==0) {
1038 cananian 1.1.2.1 if (right.minusWidth()==0) m=0; // result positive
1039 cananian 1.1.2.1 if (right.plusWidth()==0) p=0; // result negative
1040 cananian 1.1.2.1 }
1041 cananian 1.1.2.1 if (left.plusWidth()==0) {
1042 cananian 1.1.2.1 if (right.minusWidth()==0) m=0; // result negative
1043 cananian 1.1.2.1 if (right.plusWidth()==0) p=0; // result positive
1044 cananian 1.1.2.1 }
1045 cananian 1.1.2.1 // special case if divisor is a constant.
1046 cananian 1.1.2.1 if (right instanceof xIntConstant) {
1047 cananian 1.1.2.1 if (right.minusWidth()==0) { // a positive constant
1048 cananian 1.1.2.1 m = Math.max(0, left.minusWidth() - right.plusWidth());
1049 cananian 1.1.2.1 p = Math.max(0, left.plusWidth() - right.plusWidth());
1050 cananian 1.1.2.1 }
1051 cananian 1.1.2.1 if (right.plusWidth()==0) { // a negative constant
1052 cananian 1.1.2.1 m = Math.max(0, left.minusWidth()-right.minusWidth());
1053 cananian 1.1.2.1 p = Math.max(0, left.plusWidth() -right.minusWidth());
1054 cananian 1.1.2.1 }
1055 cananian 1.1.2.1 }
1056 cananian 1.5 // XXX overflow?
1057 cananian 1.1.2.1 // done.
1058 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1059 cananian 1.1.2.1 }
1060 cananian 1.1.2.1 public void visit_idiv(OPER q) { visit_div(q); }
1061 cananian 1.1.2.1 public void visit_ldiv(OPER q) { visit_div(q); }
1062 cananian 1.1.2.1
1063 cananian 1.5 void visit_mul(OPER q, int maxbits) {
1064 cananian 1.1.2.1 xBitWidth left = extractWidth( get( q.operands(0) ) );
1065 cananian 1.1.2.1 xBitWidth right= extractWidth( get( q.operands(1) ) );
1066 cananian 1.1.2.1 // worst case: either number both pos and neg
1067 cananian 1.1.2.1 int m = Math.max(left.minusWidth() + right.plusWidth(),
1068 cananian 1.1.2.1 left.plusWidth() + right.minusWidth());
1069 cananian 1.1.2.1 int p = Math.max(left.minusWidth() + right.minusWidth(),
1070 cananian 1.1.2.1 left.plusWidth() + right.plusWidth());
1071 cananian 1.1.2.1 // special case multiplication by zero, one, and two.
1072 cananian 1.1.2.26 if (right instanceof xIntConstant) { // switch r and l
1073 cananian 1.1.2.26 xBitWidth temp=left; left=right; right=temp;
1074 cananian 1.1.2.26 }
1075 cananian 1.1.2.1 if (left instanceof xIntConstant) {
1076 cananian 1.1.2.1 long val = ((xIntConstant)left).value();
1077 cananian 1.1.2.1 if (val==0) {
1078 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), left); return;
1079 cananian 1.1.2.1 }
1080 cananian 1.1.2.1 if (val==1) {
1081 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), right); return;
1082 cananian 1.1.2.1 }
1083 cananian 1.1.2.1 if (val==2) {
1084 cananian 1.1.2.1 m = right.minusWidth()+1;
1085 cananian 1.1.2.1 p = right.plusWidth() +1;
1086 cananian 1.1.2.1 }
1087 cananian 1.1.2.1 }
1088 cananian 1.1.2.1 // XXX special case multiplication by one-bit quantities?
1089 cananian 1.5 // handle overflow.
1090 cananian 1.5 if (p >= maxbits)
1091 cananian 1.5 m = maxbits; // large + val becomes large - val.
1092 cananian 1.5 if (m >= maxbits)
1093 cananian 1.5 p = maxbits-1; // large - val becomes large + val.
1094 cananian 1.1.2.1 // done.
1095 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1096 cananian 1.1.2.1 }
1097 cananian 1.5 public void visit_imul(OPER q) { visit_mul(q,32); }
1098 cananian 1.5 public void visit_lmul(OPER q) { visit_mul(q,64); }
1099 cananian 1.1.2.1
1100 cananian 1.5 void visit_neg(OPER q, int maxbits) {
1101 cananian 1.1.2.1 xBitWidth bw = extractWidth( get( q.operands(0) ) );
1102 cananian 1.1.2.1 int m = bw.plusWidth();
1103 cananian 1.1.2.1 int p = bw.minusWidth();
1104 cananian 1.5 // special case: negating the largest neg num results in neg
1105 cananian 1.5 if (bw.minusWidth() >= maxbits)
1106 cananian 1.5 m = maxbits; // -X = X for largest negative number
1107 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1108 cananian 1.1.2.1 }
1109 cananian 1.5 public void visit_ineg(OPER q) { visit_neg(q, 32); }
1110 cananian 1.5 public void visit_lneg(OPER q) { visit_neg(q, 64); }
1111 cananian 1.1.2.5
1112 cananian 1.1.2.5 void visit_or(OPER q) {
1113 cananian 1.1.2.5 xBitWidth left = extractWidth( get( q.operands(0) ) );
1114 cananian 1.1.2.5 xBitWidth right= extractWidth( get( q.operands(1) ) );
1115 cananian 1.1.2.5 // if there are zero crossings, we have worst-case performance.
1116 cananian 1.1.2.5 // XXX: check this "worst-case" computation; might be overly
1117 cananian 1.1.2.5 // conservative. If definitely correct for the
1118 cananian 1.1.2.5 // positive-number-only case.
1119 cananian 1.1.2.5 int m = Math.max( left.minusWidth(), right.minusWidth() );
1120 cananian 1.1.2.5 int p = Math.max( left.plusWidth(), right.plusWidth() );
1121 cananian 1.1.2.5 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1122 cananian 1.1.2.5 }
1123 cananian 1.1.2.5 public void visit_ior(OPER q) { visit_or(q); }
1124 cananian 1.1.2.5 public void visit_lor(OPER q) { visit_or(q); }
1125 cananian 1.1.2.26
1126 cananian 1.1.2.26 void visit_rem(OPER q) {
1127 cananian 1.1.2.26 // we don't have to worry about division by zero.
1128 cananian 1.1.2.26 xBitWidth left = extractWidth( get( q.operands(0) ) );
1129 cananian 1.1.2.26 xBitWidth right= extractWidth( get( q.operands(1) ) );
1130 cananian 1.1.2.26 // from JLS 15.17.3: "the result of the remainder
1131 cananian 1.1.2.26 // operation can be negative only if the dividend is
1132 cananian 1.1.2.26 // negative, and can be positive only if the dividend
1133 cananian 1.1.2.26 // is positive; moreover, the magnitude of the result
1134 cananian 1.1.2.26 // is always less than the magnitude of the divisor."
1135 cananian 1.1.2.26 if (right instanceof xIntConstant) {
1136 cananian 1.1.2.26 // use the fact that result is strictly less to narrow
1137 cananian 1.1.2.26 long val = ((xIntConstant)right).value();
1138 cananian 1.1.2.26 right = new xIntConstant(right.type(), val-1 );
1139 cananian 1.1.2.26 }
1140 cananian 1.1.2.26 int absmag=Math.max(left.minusWidth(), left.plusWidth());
1141 cananian 1.1.2.26 // abs value of result will also always be smaller than
1142 cananian 1.1.2.26 // abs value of dividend.
1143 cananian 1.1.2.26 int m = Math.min(right.minusWidth(), absmag);
1144 cananian 1.1.2.26 int p = Math.min(right.plusWidth(), absmag);
1145 cananian 1.5 // XXX overflow?
1146 cananian 1.1.2.26 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1147 cananian 1.1.2.26 }
1148 cananian 1.1.2.26 public void visit_irem(OPER q) { visit_rem(q); }
1149 cananian 1.1.2.26 public void visit_lrem(OPER q) { visit_rem(q); }
1150 cananian 1.1.2.26
1151 cananian 1.1.2.26 // SHIFTS. From the JLS, 15.19: "If the promoted type of
1152 cananian 1.1.2.26 // the left-hand operand is int, only the five
1153 cananian 1.1.2.26 // lowest-order bits of the right-hand operand are used as
1154 cananian 1.1.2.26 // the shift distance. It is as if the right-hand operand
1155 cananian 1.1.2.26 // were subjected to a bitwise logical AND operator &
1156 cananian 1.1.2.26 // (15.22.1) with the mask value 0x1f. The shift distance
1157 cananian 1.1.2.26 // actually used is therefore always in the range 0 to 31,
1158 cananian 1.1.2.26 // inclusive.
1159 cananian 1.1.2.26 //
1160 cananian 1.1.2.26 // "If the promoted type of the left-hand operand is long,
1161 cananian 1.1.2.26 // then only the six lowest-order bits of the right-hand
1162 cananian 1.1.2.26 // operand are used as the shift distance. It is as if the
1163 cananian 1.1.2.26 // right-hand operand were subjected to a bitwise logical
1164 cananian 1.1.2.26 // AND operator & (15.22.1) with the mask value 0x3f. The
1165 cananian 1.1.2.26 // shift distance actually used is therefore always in the
1166 cananian 1.1.2.26 // range 0 to 63, inclusive."
1167 cananian 1.1.2.26
1168 cananian 1.1.2.26 void visit_shl(OPER q, boolean isLong) {
1169 cananian 1.1.2.26 xBitWidth left = extractWidth( get( q.operands(0) ) );
1170 cananian 1.1.2.26 xBitWidth right= extractWidth( get( q.operands(1) ) );
1171 cananian 1.1.2.26 int shift;
1172 cananian 1.1.2.26 // compute largest possible shift.
1173 cananian 1.1.2.26 if (right instanceof xIntConstant) {
1174 cananian 1.1.2.26 // we know the shift exactly. whoo-hoo!
1175 cananian 1.1.2.26 long val = ((xIntConstant)right).value();
1176 cananian 1.1.2.26 shift = (int) (val & (isLong ? 0x3F : 0x1F ));
1177 cananian 1.1.2.26 // equivalent to mult by constant 2^shift.
1178 cananian 1.1.2.26 } else if (right.minusWidth()==0 &&
1179 cananian 1.1.2.26 right.plusWidth() < (isLong ? 6 : 5)) {
1180 cananian 1.1.2.26 //largest value possible on right is (2^p)-1.
1181 cananian 1.1.2.26 shift = (1<<right.plusWidth())-1;
1182 cananian 1.1.2.26 } else
1183 cananian 1.1.2.26 shift = (isLong) ? 63 : 31;
1184 cananian 1.1.2.26 // okay. nominally widths are width+shift.
1185 cananian 1.1.2.26 int m = left.minusWidth()+shift;
1186 cananian 1.1.2.26 int p = left.plusWidth()+shift;
1187 cananian 1.1.2.26 // zero shifted by anything is still zero, though.
1188 cananian 1.1.2.26 if (left.minusWidth()==0) m=0;
1189 cananian 1.1.2.26 if (left.plusWidth()==0) p=0;
1190 cananian 1.1.2.26 // if we could corrupt the sign bit, all bets are off.
1191 cananian 1.1.2.26 boolean canFrobSign =
1192 cananian 1.1.2.26 /* can leftmost one move into sign bit? */
1193 cananian 1.1.2.26 ( (left.plusWidth()+shift) >= (isLong?64:32) ) ||
1194 cananian 1.1.2.26 /* can leftmost zero move into sign bit? */
1195 cananian 1.1.2.26 ( (left.minusWidth()+shift) >= (isLong?64:32) );
1196 cananian 1.1.2.26 if (canFrobSign) { m=1000; p=1000; }
1197 cananian 1.1.2.26 // rely on bitwidth limiting the below.
1198 cananian 1.1.2.26 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1199 cananian 1.1.2.26 }
1200 cananian 1.1.2.26 public void visit_ishl(OPER q) { visit_shl(q, false); }
1201 cananian 1.1.2.26 public void visit_lshl(OPER q) { visit_shl(q, true); }
1202 cananian 1.1.2.26
1203 cananian 1.1.2.26 void visit_shr(OPER q, boolean isSigned, boolean isLong) {
1204 cananian 1.1.2.26 xBitWidth left = extractWidth( get( q.operands(0) ) );
1205 cananian 1.1.2.26 xBitWidth right= extractWidth( get( q.operands(1) ) );
1206 cananian 1.1.2.26 int shift; boolean exactlyZero=false;
1207 cananian 1.1.2.26 // compute smallest possible shift.
1208 cananian 1.1.2.26 if (right instanceof xIntConstant) {
1209 cananian 1.1.2.26 // we know the shift exactly. whoo-hoo!
1210 cananian 1.1.2.26 long val = ((xIntConstant)right).value();
1211 cananian 1.1.2.26 shift = (int) (val & (isLong ? 0x3F : 0x1F ));
1212 cananian 1.1.2.26 if (shift==0) exactlyZero=true;
1213 cananian 1.1.2.26 } else
1214 cananian 1.1.2.26 // smallest possible shift is zero.
1215 cananian 1.1.2.26 shift = 0;
1216 cananian 1.1.2.26 // okay. nominally widths are width-shift.
1217 cananian 1.1.2.26 int m = Math.max(0, left.minusWidth()-shift);
1218 cananian 1.1.2.26 int p = Math.max(0, left.plusWidth()-shift);
1219 cananian 1.1.2.26 // zero shifted by anything is still zero, though.
1220 cananian 1.1.2.26 if (left.minusWidth()==0) m=0;
1221 cananian 1.1.2.26 if (left.plusWidth()==0) p=0;
1222 cananian 1.1.2.26 // if we could corrupt the sign bit, negative numbers
1223 cananian 1.1.2.26 // can become large positive numbers.
1224 cananian 1.1.2.26 if (left.minusWidth()>0 && !isSigned && !exactlyZero)
1225 cananian 1.1.2.26 p=Math.max(p, (isLong?64:32)-shift);
1226 cananian 1.1.2.26 // rely on bitwidth limiting the below.
1227 cananian 1.1.2.26 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1228 cananian 1.1.2.26 }
1229 cananian 1.1.2.26 public void visit_ishr(OPER q) { visit_shr(q, false, false); }
1230 cananian 1.1.2.26 public void visit_lshr(OPER q) { visit_shr(q, false, true); }
1231 cananian 1.1.2.26 public void visit_iushr(OPER q) { visit_shr(q, true, false); }
1232 cananian 1.1.2.26 public void visit_lushr(OPER q) { visit_shr(q, true, true); }
1233 cananian 1.1.2.26
1234 cananian 1.1.2.26 void visit_xor(OPER q) {
1235 cananian 1.1.2.26 xBitWidth left = extractWidth( get( q.operands(0) ) );
1236 cananian 1.1.2.26 xBitWidth right= extractWidth( get( q.operands(1) ) );
1237 cananian 1.1.2.26 int mL=left.minusWidth(), pL=left.plusWidth();
1238 cananian 1.1.2.26 int mR=right.minusWidth(), pR=right.plusWidth();
1239 cananian 1.1.2.26 int m=0, p=0;
1240 cananian 1.1.2.26 // note that <0,0>=constant zero is included in plus range
1241 cananian 1.1.2.26 // (i.e. all ranges are said to have '+' components (the 0) )
1242 cananian 1.1.2.26 // <0,pL> xor <0,pR> = <0,MAX(pL,pR)>
1243 cananian 1.1.2.26 if (pL>=0 && pR>=0)
1244 cananian 1.1.2.26 p = Math.max(p, Math.max(pL, pR));
1245 cananian 1.1.2.26 // <0,pL> xor <mR,0> = <MAX(pL,mR),0>
1246 cananian 1.1.2.26 if (pL>=0 && mR>0)
1247 cananian 1.1.2.26 m = Math.max(m, Math.max(pL, mR));
1248 cananian 1.1.2.26 // <mL,0> xor <0,pR> = <MAX(mL,pR),0>
1249 cananian 1.1.2.26 if (mL>0 && pR>=0)
1250 cananian 1.1.2.26 m = Math.max(m, Math.max(mL, pR));
1251 cananian 1.1.2.26 // <mL,0> xor <mR,0> = <0,MAX(mL,mR)>
1252 cananian 1.1.2.26 if (mL>0 && mR>0)
1253 cananian 1.1.2.26 p = Math.max(p, Math.max(mL, mR));
1254 cananian 1.1.2.26 // ta-da!
1255 cananian 1.1.2.26 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1256 cananian 1.1.2.26 }
1257 cananian 1.1.2.26 public void visit_ixor(OPER q) { visit_xor(q); }
1258 cananian 1.1.2.26 public void visit_lxor(OPER q) { visit_xor(q); }
1259 cananian 1.1.2.1 }
1260 cananian 1.1.2.1 }
1261 cananian 1.1.2.1 /*-------------------------------------------------------------*/
1262 cananian 1.1.2.1 // Extract bitwidth information from unwilling victims.
1263 cananian 1.1.2.1 xBitWidth extractWidth(LatticeVal v) {
1264 cananian 1.1.2.1 if (v instanceof xBitWidth)
1265 cananian 1.1.2.1 return (xBitWidth) v;
1266 cananian 1.1.2.1 if (! (v instanceof xClass) )
1267 cananian 1.1.2.1 throw new Error("Something's seriously screwed up.");
1268 cananian 1.1.2.1 xClass xc = (xClass) v;
1269 cananian 1.1.2.1 // trust xBitWidth to properly limit.
1270 cananian 1.1.2.1 return new xBitWidth(xc.type(), 1000, 1000);
1271 cananian 1.1.2.1 }
1272 cananian 1.1.2.1
1273 cananian 1.1.2.1 // Deal with the fact that external Byte/Short/Char/Boolean classes
1274 cananian 1.1.2.1 // are represented internally as ints.
1275 cananian 1.1.2.1
1276 cananian 1.1.2.1 static HClass toInternal(HClass c) {
1277 cananian 1.1.2.1 if (c.equals(HClass.Byte) || c.equals(HClass.Short) ||
1278 cananian 1.1.2.1 c.equals(HClass.Char) || c.equals(HClass.Boolean))
1279 cananian 1.1.2.1 return HClass.Int;
1280 cananian 1.1.2.1 return c;
1281 cananian 1.1.2.1 }
1282 cananian 1.1.2.1
1283 cananian 1.1.2.1 /*-------------------------------------------------------------*/
1284 cananian 1.1.2.1 // Lattice classes.
1285 cananian 1.1.2.1
1286 cananian 1.1.2.1 /** No information obtainable about a temp. */
1287 cananian 1.1.2.21 static abstract class LatticeVal {
1288 cananian 1.1.2.1 public String toString() { return "Top"; }
1289 cananian 1.1.2.1 public boolean equals(Object o) { return o instanceof LatticeVal; }
1290 cananian 1.1.2.21 // merge.
1291 cananian 1.1.2.21 public abstract LatticeVal merge(LatticeVal v);
1292 cananian 1.1.2.23 // narrow.
1293 cananian 1.1.2.23 public abstract boolean isLowerThan(LatticeVal v);
1294 cananian 1.1.2.16 // by default, the renaming does nothing.
1295 cananian 1.1.2.16 public LatticeVal rename(PHI p, int i) { return this; }
1296 cananian 1.1.2.16 public LatticeVal rename(SIGMA s, int i) { return this; }
1297 cananian 1.1.2.1 }
1298 cananian 1.1.2.1 /** A typed temp. */
1299 cananian 1.1.2.1 static class xClass extends LatticeVal {
1300 cananian 1.1.2.1 protected HClass type;
1301 cananian 1.1.2.1 public xClass(HClass type) {
1302 cananian 1.3.2.1 assert type!=HClass.Boolean && type!=HClass.Byte &&
1303 cananian 1.3.2.1 type!=HClass.Short && type!=HClass.Char : "Not an internal type ("+type+")";
1304 cananian 1.1.2.1 this.type = type;
1305 cananian 1.1.2.1 }
1306 cananian 1.1.2.1 public HClass type() { return type; }
1307 cananian 1.1.2.1 public String toString() {
1308 cananian 1.1.2.1 return "xClass: " + type;
1309 cananian 1.1.2.1 }
1310 cananian 1.1.2.21 public boolean equals(Object o) { return _equals(o); }
1311 cananian 1.1.2.21 private boolean _equals(Object o) {
1312 cananian 1.1.2.1 xClass xc;
1313 cananian 1.1.2.1 try { xc=(xClass) o; }
1314 cananian 1.1.2.1 catch (ClassCastException e) { return false;}
1315 cananian 1.1.2.1 return xc!=null && xc.type.equals(type);
1316 cananian 1.1.2.1 }
1317 cananian 1.1.2.21 public LatticeVal merge(LatticeVal v) {
1318 cananian 1.1.2.21 xClass vv = (xClass) v;
1319 cananian 1.1.2.21 return new xClass(mergeTypes(this.type, vv.type));
1320 cananian 1.1.2.21 }
1321 cananian 1.1.2.23 public boolean isLowerThan(LatticeVal v) {
1322 cananian 1.1.2.23 return !(v instanceof xClass);
1323 cananian 1.1.2.23 }
1324 cananian 1.1.2.21 // Class merge function.
1325 cananian 1.1.2.21 static HClass mergeTypes(HClass a, HClass b) {
1326 cananian 1.3.2.1 assert a!=null && b!=null;
1327 cananian 1.1.2.21 if (a==b) return a; // take care of primitive types.
1328 cananian 1.1.2.21
1329 cananian 1.1.2.21 // Special case 'Void' Hclass, used for null constants.
1330 cananian 1.1.2.21 if (a==HClass.Void)
1331 cananian 1.1.2.21 return b;
1332 cananian 1.1.2.21 if (b==HClass.Void)
1333 cananian 1.1.2.21 return a;
1334 cananian 1.1.2.21
1335 cananian 1.1.2.21 // by this point better be array ref or object, not primitive type.
1336 cananian 1.3.2.1 assert (!a.isPrimitive()) && (!b.isPrimitive());
1337 cananian 1.1.2.21 return HClassUtil.commonParent(a,b);
1338 cananian 1.1.2.1 }
1339 cananian 1.1.2.1 }
1340 cananian 1.1.2.1 /** A single class type; guaranteed the value is not null. */
1341 cananian 1.1.2.1 static class xClassNonNull extends xClass {
1342 cananian 1.1.2.1 public xClassNonNull(HClass type) {
1343 cananian 1.1.2.1 super( type );
1344 cananian 1.3.2.1 assert type!=HClass.Void;
1345 cananian 1.1.2.1 }
1346 cananian 1.1.2.1 public String toString() {
1347 cananian 1.1.2.1 return "xClassNonNull: { " + type + " }";
1348 cananian 1.1.2.1 }
1349 cananian 1.1.2.21 public boolean equals(Object o) { return _equals(o); }
1350 cananian 1.1.2.21 private boolean _equals(Object o) {
1351 cananian 1.1.2.1 return (o instanceof xClassNonNull && super.equals(o));
1352 cananian 1.1.2.1 }
1353 cananian 1.1.2.21 public LatticeVal merge(LatticeVal v) {
1354 cananian 1.1.2.21 if (!(v instanceof xClassNonNull)) return super.merge(v);
1355 cananian 1.1.2.21 xClassNonNull vv = (xClassNonNull) v;
1356 cananian 1.1.2.21 return new xClassNonNull(mergeTypes(this.type, vv.type));
1357 cananian 1.1.2.1 }
1358 cananian 1.1.2.23 public boolean isLowerThan(LatticeVal v) {
1359 cananian 1.1.2.23 return !(v instanceof xClassNonNull);
1360 cananian 1.1.2.23 }
1361 cananian 1.1.2.1 }
1362 cananian 1.1.2.11 /** An object of the specified *exact* type (not a subtype). */
1363 cananian 1.1.2.11 static class xClassExact extends xClassNonNull {
1364 cananian 1.1.2.11 public xClassExact(HClass type) {
1365 cananian 1.1.2.11 super(type);
1366 cananian 1.6 assert !type.isInterface(); // interface types can't be exact.
1367 cananian 1.1.2.11 }
1368 cananian 1.1.2.11 public String toString() {
1369 cananian 1.1.2.11 return "xClassExact: { " + type + " }";
1370 cananian 1.1.2.11 }
1371 cananian 1.1.2.21 public boolean equals(Object o) { return _equals(o); }
1372 cananian 1.1.2.21 private boolean _equals(Object o) {
1373 cananian 1.1.2.11 return (o instanceof xClassExact && super.equals(o));
1374 cananian 1.1.2.11 }
1375 cananian 1.1.2.21 public LatticeVal merge(LatticeVal v) {
1376 cananian 1.1.2.21 if (this._equals(v)) return new xClassExact(type);
1377 cananian 1.1.2.21 return super.merge(v);
1378 cananian 1.1.2.11 }
1379 cananian 1.1.2.23 public boolean isLowerThan(LatticeVal v) {
1380 cananian 1.1.2.23 return !(v instanceof xClassExact);
1381 cananian 1.1.2.23 }
1382 cananian 1.1.2.11 }
1383 cananian 1.1.2.1 /** An array with constant length. The array is not null, of course. */
1384 cananian 1.1.2.11 static class xClassArray extends xClassExact {
1385 cananian 1.1.2.1 protected int length;
1386 cananian 1.1.2.1 public xClassArray(HClass type, int length) {
1387 cananian 1.1.2.1 super(type);
1388 cananian 1.1.2.1 this.length = length;
1389 cananian 1.1.2.1 }
1390 cananian 1.1.2.1 public int length() { return length; }
1391 cananian 1.1.2.1 public String toString() {
1392 cananian 1.1.2.1 return "xClassArray: " +
1393 cananian 1.1.2.1 type.getComponentType() + "["+length+"]";
1394 cananian 1.1.2.1 }
1395 cananian 1.1.2.21 public boolean equals(Object o) { return _equals(o); }
1396 cananian 1.1.2.21 private boolean _equals(Object o) {
1397 cananian 1.1.2.1 xClassArray xca;
1398 cananian 1.1.2.1 try { xca = (xClassArray) o; }
1399 cananian 1.1.2.1 catch (ClassCastException e) { return false; }
1400 cananian 1.1.2.1 return xca!=null && super.equals(xca) && xca.length == length;
1401 cananian 1.1.2.1 }
1402 cananian 1.1.2.21 public LatticeVal merge(LatticeVal v) {
1403 cananian 1.1.2.21 if (this._equals(v)) return new xClassArray(type,length);
1404 cananian 1.1.2.21 return super.merge(v);
1405 cananian 1.1.2.1 }
1406 cananian 1.1.2.23 public boolean isLowerThan(LatticeVal v) {
1407 cananian 1.1.2.23 return !(v instanceof xClassArray);
1408 cananian 1.1.2.23 }
1409 cananian 1.1.2.1 }
1410 cananian 1.1.2.1 /** An integer value of the specified bitwidth. */
1411 cananian 1.1.2.11 static class xBitWidth extends xClassExact {
1412 cananian 1.1.2.1 /** Highest significant bit for positive numbers. */
1413 cananian 1.1.2.1 protected int plusWidth;
1414 cananian 1.1.2.1 /** Highest significant bit for negative numbers. */
1415 cananian 1.1.2.1 protected int minusWidth;
1416 cananian 1.1.2.1 /** Constructor. */
1417 cananian 1.1.2.1 public xBitWidth(HClass type, int minusWidth, int plusWidth) {
1418 cananian 1.1.2.1 super(toInternal(type));
1419 cananian 1.1.2.1 // limit.
1420 cananian 1.1.2.1 if (type == HClass.Long) {
1421 cananian 1.1.2.1 this.minusWidth = Math.min(64, minusWidth);
1422 cananian 1.1.2.1 this.plusWidth = Math.min(63, plusWidth);
1423 cananian 1.1.2.1 } else if (type == HClass.Int) {
1424 cananian 1.1.2.1 this.minusWidth = Math.min(32, minusWidth);
1425 cananian 1.1.2.1 this.plusWidth = Math.min(31, plusWidth);
1426 cananian 1.1.2.1 } else // NON-CANONICAL TYPES: CAREFUL! (this.type fixed by above)
1427 cananian 1.1.2.1 if (type == HClass.Boolean) {
1428 cananian 1.1.2.1 this.minusWidth = Math.min( 0, minusWidth);
1429 cananian 1.1.2.1 this.plusWidth = Math.min( 1, plusWidth);
1430 cananian 1.1.2.1 } else if (type == HClass.Short) {
1431 cananian 1.1.2.1 this.minusWidth = Math.min(16, minusWidth);
1432 cananian 1.1.2.1 this.plusWidth = Math.min(15, plusWidth);
1433 cananian 1.1.2.1 } else if (type == HClass.Byte) {
1434 cananian 1.1.2.1 this.minusWidth = Math.min( 8, minusWidth);
1435 cananian 1.1.2.1 this.plusWidth = Math.min( 7, plusWidth);
1436 cananian 1.1.2.1 } else if (type == HClass.Char) {
1437 cananian 1.1.2.1 this.minusWidth = Math.min( 0, minusWidth);
1438 cananian 1.1.2.1 this.plusWidth = Math.min(16, plusWidth);
1439 cananian 1.1.2.1 } else throw new Error("Unknown type for xBitWidth: "+type);
1440 cananian 1.1.2.1 }
1441 cananian 1.1.2.1 public int minusWidth() { return minusWidth; }
1442 cananian 1.1.2.1 public int plusWidth () { return plusWidth; }
1443 cananian 1.1.2.1 public String toString() {
1444 cananian 1.1.2.1 return "xBitWidth: " + type + " " +
1445 cananian 1.1.2.1 "-"+minusWidth+"+"+plusWidth+" bits";
1446 cananian 1.1.2.1 }
1447 cananian 1.1.2.21 public boolean equals(Object o) { return _equals(o); }
1448 cananian 1.1.2.21 private boolean _equals(Object o) {
1449 cananian 1.1.2.1 xBitWidth xbw;
1450 cananian 1.1.2.1 try { xbw = (xBitWidth) o; }
1451 cananian 1.1.2.1 catch (ClassCastException e) { return false; }
1452 cananian 1.1.2.1 return xbw!=null && super.equals(xbw) &&
1453 cananian 1.1.2.1 xbw.minusWidth == minusWidth &&
1454 cananian 1.1.2.1 xbw.plusWidth == plusWidth;
1455 cananian 1.1.2.1 }
1456 cananian 1.1.2.21 public LatticeVal merge(LatticeVal v) {
1457 cananian 1.1.2.21 if (!(v instanceof xBitWidth)) return super.merge(v);
1458 cananian 1.1.2.21 // bitwidth merge
1459 cananian 1.1.2.21 xBitWidth vv = (xBitWidth) v;
1460 cananian 1.1.2.21 if (!this.type.equals(vv.type)) return super.merge(vv);
1461 cananian 1.1.2.21 return new xBitWidth
1462 cananian 1.1.2.21 (this.type,
1463 cananian 1.1.2.21 Math.max(this.minusWidth, vv.minusWidth),
1464 cananian 1.1.2.21 Math.max(this.plusWidth, vv.plusWidth));
1465 cananian 1.1.2.16 }
1466 cananian 1.1.2.23 public boolean isLowerThan(LatticeVal v) {
1467 cananian 1.1.2.23 return !(v instanceof xBitWidth);
1468 cananian 1.1.2.23 }
1469 cananian 1.1.2.16 }
1470 cananian 1.1.2.16 /** An integer value which is the result of an INSTANCEOF. */
1471 cananian 1.1.2.22 static class xInstanceofResultUnknown extends xBitWidth
1472 cananian 1.1.2.22 implements xInstanceofResult {
1473 cananian 1.1.2.16 Temp tested;
1474 cananian 1.1.2.16 INSTANCEOF q;
1475 cananian 1.1.2.22 public xInstanceofResultUnknown(INSTANCEOF q) { this(q, q.src()); }
1476 cananian 1.1.2.22 xInstanceofResultUnknown(INSTANCEOF q, Temp tested) {
1477 cananian 1.1.2.16 super(toInternal(HClass.Boolean),0,1);
1478 cananian 1.1.2.16 this.q = q;
1479 cananian 1.1.2.16 this.tested = tested;
1480 cananian 1.1.2.16 }
1481 cananian 1.1.2.16 public Temp tested() { return tested; }
1482 cananian 1.1.2.16 public INSTANCEOF def() { return q; }
1483 cananian 1.1.2.16 public String toString() {
1484 cananian 1.1.2.22 return "xInstanceofResultUnknown: " + type + " " +q;
1485 cananian 1.1.2.16 }
1486 cananian 1.1.2.21 public boolean equals(Object o) { return _equals(o); }
1487 cananian 1.1.2.21 private boolean _equals(Object o) {
1488 cananian 1.1.2.22 return (o instanceof xInstanceofResultUnknown && super.equals(o) &&
1489 cananian 1.1.2.22 ((xInstanceofResultUnknown)o).q == q &&
1490 cananian 1.1.2.22 ((xInstanceofResultUnknown)o).tested == tested);
1491 cananian 1.1.2.16 }
1492 cananian 1.1.2.21 public LatticeVal merge(LatticeVal v) {
1493 cananian 1.1.2.22 if (v instanceof xInstanceofResult)
1494 cananian 1.1.2.22 // xInstanceofResultKnown merged with
1495 cananian 1.1.2.22 // xInstanceofResultKnown or xInstanceofResultUnknown
1496 cananian 1.1.2.22 return makeUnknown();
1497 cananian 1.1.2.22 // all others.
1498 cananian 1.1.2.21 return super.merge(v);
1499 cananian 1.1.2.16 }
1500 cananian 1.1.2.23 public boolean isLowerThan(LatticeVal v) {
1501 cananian 1.1.2.23 return !(v instanceof xBitWidth);
1502 cananian 1.1.2.23 }
1503 cananian 1.1.2.22 public xInstanceofResultKnown makeKnown(boolean nvalue) {
1504 cananian 1.1.2.22 return new xInstanceofResultKnown(q,tested,nvalue?1:0);
1505 cananian 1.1.2.22 }
1506 cananian 1.1.2.22 public xInstanceofResultUnknown makeUnknown() {
1507 cananian 1.1.2.22 return new xInstanceofResultUnknown(q,tested);
1508 cananian 1.1.2.22 }
1509 cananian 1.1.2.16 // override renaming functions.
1510 cananian 1.1.2.16 public LatticeVal rename(PHI q, int j) {
1511 cananian 1.1.2.16 for (int i=0; i<q.numPhis(); i++)
1512 cananian 1.1.2.16 if (q.src(i, j)==this.tested)
1513 cananian 1.1.2.22 return new xInstanceofResultUnknown(def(), q.dst(i));
1514 cananian 1.1.2.16 return this;
1515 cananian 1.1.2.16 }
1516 cananian 1.1.2.16 public LatticeVal rename(SIGMA q, int j) {
1517 cananian 1.1.2.16 for (int i=0; i<q.numSigmas(); i++)
1518 cananian 1.1.2.16 if (q.src(i)==this.tested)
1519 cananian 1.1.2.22 return new xInstanceofResultUnknown(def(), q.dst(i, j));
1520 cananian 1.1.2.16 return this;
1521 cananian 1.1.2.16 }
1522 cananian 1.1.2.16 }
1523 cananian 1.1.2.22 /** An unknown boolean value which is the result of an OPER. */
1524 cananian 1.1.2.22 static class xOperBooleanResultUnknown extends xBitWidth
1525 cananian 1.1.2.22 implements xOperBooleanResult {
1526 cananian 1.1.2.16 OPER q;
1527 cananian 1.1.2.16 Temp[] operands;
1528 cananian 1.1.2.22 public xOperBooleanResultUnknown(OPER q) { this(q, q.operands()); }
1529 cananian 1.1.2.22 xOperBooleanResultUnknown(OPER q, Temp[] operands) {
1530 cananian 1.1.2.16 super(toInternal(HClass.Boolean),0,1);
1531 cananian 1.1.2.16 this.q = q;
1532 cananian 1.1.2.16 this.operands = operands;
1533 cananian 1.1.2.16 }
1534 cananian 1.1.2.16 public Temp[] operands() { return operands; }
1535 cananian 1.1.2.16 public OPER def() { return q; }
1536 cananian 1.1.2.16 public String toString() {
1537 cananian 1.1.2.22 return "xOperBooleanResultUnknown: " + type + " " +q;
1538 cananian 1.1.2.16 }
1539 cananian 1.1.2.21 public boolean equals(Object o) { return _equals(o); }
1540 cananian 1.1.2.21 private boolean _equals(Object o) {
1541 cananian 1.1.2.16 if (o==this) return true; // common case.
1542 cananian 1.1.2.22 if (!(o instanceof xOperBooleanResultUnknown)) return false;
1543 cananian 1.1.2.16 if (!super.equals(o)) return false;
1544 cananian 1.1.2.22 xOperBooleanResultUnknown oo = (xOperBooleanResultUnknown)o;
1545 cananian 1.1.2.16 if (oo.q != q) return false;
1546 cananian 1.1.2.16 if (oo.operands.length != operands.length) return false;
1547 cananian 1.1.2.16 for (int i=0; i<operands.length; i++)
1548 cananian 1.1.2.16 if (oo.operands[i] != operands[i]) return false;
1549 cananian 1.1.2.16 return true;
1550 cananian 1.1.2.16 }
1551 cananian 1.1.2.21 public LatticeVal merge(LatticeVal v) {
1552 cananian 1.1.2.22 if (v instanceof xOperBooleanResult)
1553 cananian 1.1.2.22 // xOperBooleanResultKnown merged with
1554 cananian 1.1.2.22 // xOperBooleanResultKnown or xOperBooleanResultUnknown
1555 cananian 1.1.2.22 return makeUnknown();
1556 cananian 1.1.2.22 // all others.
1557 cananian 1.1.2.21 return super.merge(v);
1558 cananian 1.1.2.16 }
1559 cananian 1.1.2.23 public boolean isLowerThan(LatticeVal v) {
1560 cananian 1.1.2.23 return !(v instanceof xBitWidth);
1561 cananian 1.1.2.23 }
1562 cananian 1.1.2.22 public xOperBooleanResultKnown makeKnown(boolean nvalue) {
1563 cananian 1.1.2.22 return new xOperBooleanResultKnown(q,operands,nvalue?1:0);
1564 cananian 1.1.2.22 }
1565 cananian 1.1.2.22 public xOperBooleanResultUnknown makeUnknown() {
1566 cananian 1.1.2.22 return new xOperBooleanResultUnknown(q,operands);
1567 cananian 1.1.2.22 }
1568 cananian 1.1.2.16 // override renaming functions.
1569 cananian 1.1.2.16 public LatticeVal rename(PHI q, int j) {
1570 cananian 1.1.2.16 MyTempMap mtm = new MyTempMap();
1571 cananian 1.1.2.16 for (int i=0; i<q.numPhis(); i++)
1572 cananian 1.1.2.16 mtm.put(q.src(i,j), q.dst(i));
1573 cananian 1.1.2.22 return new xOperBooleanResultUnknown(def(), mtm.tempMap(operands()));
1574 cananian 1.1.2.16 }
1575 cananian 1.1.2.16 public LatticeVal rename(SIGMA q, int j) {
1576 cananian 1.1.2.16 MyTempMap mtm = new MyTempMap();
1577 cananian 1.1.2.16 for (int i=0; i<q.numSigmas(); i++)
1578 cananian 1.1.2.16 mtm.put(q.src(i), q.dst(i, j));
1579 cananian 1.1.2.22 return new xOperBooleanResultUnknown(def(), mtm.tempMap(operands()));
1580 cananian 1.1.2.16 }
1581 cananian 1.1.2.16 private static class MyTempMap extends HashMap implements TempMap {
1582 cananian 1.1.2.16 public Temp tempMap(Temp t) {
1583 cananian 1.1.2.16 return containsKey(t) ? (Temp) get(t) : t;
1584 cananian 1.1.2.16 }
1585 cananian 1.1.2.16 public Temp[] tempMap(Temp[] t) {
1586 cananian 1.1.2.16 Temp[] r = new Temp[t.length];
1587 cananian 1.1.2.16 for (int i=0; i<r.length; i++)
1588 cananian 1.1.2.16 r[i] = tempMap(t[i]);
1589 cananian 1.1.2.16 return r;
1590 cananian 1.1.2.16 }
1591 cananian 1.1.2.1 }
1592 cananian 1.1.2.1 }
1593 cananian 1.1.2.1 /** An integer or boolean constant. */
1594 cananian 1.1.2.1 static class xIntConstant extends xBitWidth implements xConstant {
1595 cananian 1.1.2.1 protected long value;
1596 cananian 1.1.2.1 public xIntConstant(HClass type, long value) {
1597 cananian 1.1.2.1 super(type, value<0?Util.fls(-value):0, value>0?Util.fls(value):0);
1598 cananian 1.1.2.1 this.value = value;
1599 cananian 1.1.2.1 }
1600 cananian 1.1.2.1 public long value() { return value; }
1601 cananian 1.1.2.1 public Object constValue() {
1602 cananian 1.1.2.1 if (type==HClass.Int) return new Integer((int)value);
1603 cananian 1.1.2.1 if (type==HClass.Long) return new Long((long)value);
1604 cananian 1.1.2.1 //if (type==HClass.Boolean) return new Integer(value!=0?1:0);
1605 cananian 1.1.2.1 throw new Error("Unknown integer constant type.");
1606 cananian 1.1.2.1 }
1607 cananian 1.1.2.1 public String toString() {
1608 cananian 1.1.2.1 return "xIntConstant: " + type + " " + value;
1609 cananian 1.1.2.1 }
1610 cananian 1.1.2.21 public boolean equals(Object o) { return _equals(o); }
1611 cananian 1.1.2.21 private boolean _equals(Object o) {
1612 cananian 1.1.2.1 return (o instanceof xIntConstant && super.equals(o) &&
1613 cananian 1.1.2.1 ((xIntConstant)o).value == value);
1614 cananian 1.1.2.1 }
1615 cananian 1.1.2.21 public LatticeVal merge(LatticeVal v) {
1616 cananian 1.1.2.21 if (this._equals(v)) return new xIntConstant(type,value);
1617 cananian 1.1.2.21 return super.merge(v);
1618 cananian 1.1.2.1 }
1619 cananian 1.1.2.23 public boolean isLowerThan(LatticeVal v) {
1620 cananian 1.1.2.23 return !(v instanceof xIntConstant);
1621 cananian 1.1.2.23 }
1622 cananian 1.1.2.1 }
1623 cananian 1.1.2.22 /** An integer value which is the result of an INSTANCEOF. */
1624 cananian 1.1.2.22 static class xInstanceofResultKnown extends xIntConstant
1625 cananian 1.1.2.22 implements xInstanceofResult {
1626 cananian 1.1.2.22 Temp tested;
1627 cananian 1.1.2.22 INSTANCEOF q;
1628 cananian 1.1.2.22 public xInstanceofResultKnown(INSTANCEOF q, boolean value) {
1629 cananian 1.1.2.22 this(q, q.src(), value?1:0);
1630 cananian 1.1.2.22 }
1631 cananian 1.1.2.22 private xInstanceofResultKnown(INSTANCEOF q, Temp tested, long value) {
1632 cananian 1.1.2.22 super(toInternal(HClass.Boolean),value);
1633 cananian 1.1.2.22 this.q = q;
1634 cananian 1.1.2.22 this.tested = tested;
1635 cananian 1.3.2.1 assert value==0 || value==1;
1636 cananian 1.1.2.22 }
1637 cananian 1.1.2.22 public Temp tested() { return tested; }
1638 cananian 1.1.2.22 public INSTANCEOF def() { return q; }
1639 cananian 1.1.2.22 public String toString() {
1640 cananian 1.1.2.22 return "xInstanceofResultKnown: " + value + " " +q;
1641 cananian 1.1.2.22 }
1642 cananian 1.1.2.22 public boolean equals(Object o) { return _equals(o); }
1643 cananian 1.1.2.22 private boolean _equals(Object o) {
1644 cananian 1.1.2.22 return (o instanceof xInstanceofResultKnown && super.equals(o) &&
1645 cananian 1.1.2.22 ((xInstanceofResultKnown)o).q == q &&
1646 cananian 1.1.2.22 ((xInstanceofResultKnown)o).tested == tested);
1647 cananian 1.1.2.22 }
1648 cananian 1.1.2.22 public LatticeVal merge(LatticeVal v) {
1649 cananian 1.1.2.22 if (v instanceof xInstanceofResult)
1650 cananian 1.1.2.22 // xInstanceofResultKnown merged with
1651 cananian 1.1.2.22 // xInstanceofResultKnown or xInstanceofResultUnknown
1652 cananian 1.1.2.22 return this._equals(v) ? (LatticeVal)
1653 cananian 1.1.2.22 makeKnown(value!=0) : makeUnknown();
1654 cananian 1.1.2.22 // all others.
1655 cananian 1.1.2.22 return super.merge(v);
1656 cananian 1.1.2.22 }
1657 cananian 1.1.2.23 public boolean isLowerThan(LatticeVal v) {
1658 cananian 1.1.2.23 return !(v instanceof xIntConstant);
1659 cananian 1.1.2.23 }
1660 cananian 1.1.2.22 public xInstanceofResultKnown makeKnown(boolean nvalue) {
1661 cananian 1.1.2.22 return new xInstanceofResultKnown(q,tested,nvalue?1:0);
1662 cananian 1.1.2.22 }
1663 cananian 1.1.2.22 public xInstanceofResultUnknown makeUnknown() {
1664 cananian 1.1.2.22 return new xInstanceofResultUnknown(q,tested);
1665 cananian 1.1.2.22 }
1666 cananian 1.1.2.22 // override renaming functions.
1667 cananian 1.1.2.22 public LatticeVal rename(PHI q, int j) {
1668 cananian 1.1.2.22 for (int i=0; i<q.numPhis(); i++)
1669 cananian 1.1.2.22 if (q.src(i, j)==this.tested)
1670 cananian 1.1.2.22 return new xInstanceofResultKnown(def(), q.dst(i), value);
1671 cananian 1.1.2.22 return this;
1672 cananian 1.1.2.22 }
1673 cananian 1.1.2.22 public LatticeVal rename(SIGMA q, int j) {
1674 cananian 1.1.2.22 for (int i=0; i<q.numSigmas(); i++)
1675 cananian 1.1.2.22 if (q.src(i)==this.tested)
1676 cananian 1.1.2.22 return new xInstanceofResultKnown(def(),q.dst(i, j),value);
1677 cananian 1.1.2.22 return this;
1678 cananian 1.1.2.22 }
1679 cananian 1.1.2.22 }
1680 cananian 1.1.2.22 /** A known boolean value which is the result of an OPER. */
1681 cananian 1.1.2.22 static class xOperBooleanResultKnown extends xIntConstant
1682 cananian 1.1.2.22 implements xOperBooleanResult {
1683 cananian 1.1.2.22 OPER q;
1684 cananian 1.1.2.22 Temp[] operands;
1685 cananian 1.1.2.22 public xOperBooleanResultKnown(OPER q, boolean value) {
1686 cananian 1.1.2.22 this(q, q.operands(), value?1:0);
1687 cananian 1.1.2.22 }
1688 cananian 1.1.2.22 xOperBooleanResultKnown(OPER q, Temp[] operands, long value)
1689 cananian 1.1.2.22 {
1690 cananian 1.1.2.22 super(toInternal(HClass.Boolean),value);
1691 cananian 1.1.2.22 this.q = q;
1692 cananian 1.1.2.22 this.operands = operands;
1693 cananian 1.3.2.1 assert value==0 || value==1;
1694 cananian 1.1.2.22 }
1695 cananian 1.1.2.22 public Temp[] operands() { return operands; }
1696 cananian 1.1.2.22 public OPER def() { return q; }
1697 cananian 1.1.2.22 public String toString() {
1698 cananian 1.1.2.22 return "xOperBooleanResultKnown: " + value + " " +q;
1699 cananian 1.1.2.22 }
1700 cananian 1.1.2.22 public boolean equals(Object o) { return _equals(o); }
1701 cananian 1.1.2.22 private boolean _equals(Object o) {
1702 cananian 1.1.2.22 if (o==this) return true; // common case.
1703 cananian 1.1.2.22 if (!(o instanceof xOperBooleanResultKnown)) return false;
1704 cananian 1.1.2.22 if (!super.equals(o)) return false;
1705 cananian 1.1.2.22 xOperBooleanResultKnown oo = (xOperBooleanResultKnown)o;
1706 cananian 1.1.2.22 if (oo.q != q) return false;
1707 cananian 1.1.2.22 if (oo.operands.length != operands.length) return false;
1708 cananian 1.1.2.22 for (int i=0; i<operands.length; i++)
1709 cananian 1.1.2.22 if (oo.operands[i] != operands[i]) return false;
1710 cananian 1.1.2.22 return true;
1711 cananian 1.1.2.22 }
1712 cananian 1.1.2.22 public LatticeVal merge(LatticeVal v) {
1713 cananian 1.1.2.22 if (v instanceof xOperBooleanResult)
1714 cananian 1.1.2.22 // xOperBooleanResultKnown merged with
1715 cananian 1.1.2.22 // xOperBooleanResultKnown or xOperBooleanResultUnknown
1716 cananian 1.1.2.22 return this._equals(v) ? (LatticeVal)
1717 cananian 1.1.2.22 makeKnown(value!=0) : makeUnknown();
1718 cananian 1.1.2.22 // all others.
1719 cananian 1.1.2.22 return super.merge(v);
1720 cananian 1.1.2.22 }
1721 cananian 1.1.2.23 public boolean isLowerThan(LatticeVal v) {
1722 cananian 1.1.2.23 return !(v instanceof xIntConstant);
1723 cananian 1.1.2.23 }
1724 cananian 1.1.2.22 public xOperBooleanResultKnown makeKnown(boolean nvalue) {
1725 cananian 1.1.2.22 return new xOperBooleanResultKnown(q,operands,nvalue?1:0);
1726 cananian 1.1.2.22 }
1727 cananian 1.1.2.22 public xOperBooleanResultUnknown makeUnknown() {
1728 cananian 1.1.2.22 return new xOperBooleanResultUnknown(q,operands);
1729 cananian 1.1.2.22 }
1730 cananian 1.1.2.22 // override renaming functions.
1731 cananian 1.1.2.22 public LatticeVal rename(PHI q, int j) {
1732 cananian 1.1.2.22 MyTempMap mtm = new MyTempMap();
1733 cananian 1.1.2.22 for (int i=0; i<q.numPhis(); i++)
1734 cananian 1.1.2.22 mtm.put(q.src(i,j), q.dst(i));
1735 cananian 1.1.2.22 return new xOperBooleanResultKnown(def(), mtm.tempMap(operands()),
1736 cananian 1.1.2.22 value);
1737 cananian 1.1.2.22 }
1738 cananian 1.1.2.22 public LatticeVal rename(SIGMA q, int j) {
1739 cananian 1.1.2.22 MyTempMap mtm = new MyTempMap();
1740 cananian 1.1.2.22 for (int i=0; i<q.numSigmas(); i++)
1741 cananian 1.1.2.22 mtm.put(q.src(i), q.dst(i, j));
1742 cananian 1.1.2.22 return new xOperBooleanResultKnown(def(), mtm.tempMap(operands()),
1743 cananian 1.1.2.22 value);
1744 cananian 1.1.2.22 }
1745 cananian 1.1.2.22 private static class MyTempMap extends HashMap implements TempMap {
1746 cananian 1.1.2.22 public Temp tempMap(Temp t) {
1747 cananian 1.1.2.22 return containsKey(t) ? (Temp) get(t) : t;
1748 cananian 1.1.2.22 }
1749 cananian 1.1.2.22 public Temp[] tempMap(Temp[] t) {
1750 cananian 1.1.2.22 Temp[] r = new Temp[t.length];
1751 cananian 1.1.2.22 for (int i=0; i<r.length; i++)
1752 cananian 1.1.2.22 r[i] = tempMap(t[i]);
1753 cananian 1.1.2.22 return r;
1754 cananian 1.1.2.22 }
1755 cananian 1.1.2.22 }
1756 cananian 1.1.2.22 }
1757 cananian 1.1.2.1 static class xNullConstant extends xClass implements xConstant {
1758 cananian 1.1.2.1 public xNullConstant() {
1759 cananian 1.1.2.1 super(HClass.Void);
1760 cananian 1.1.2.1 }
1761 cananian 1.1.2.1 public Object constValue() { return null; }
1762 cananian 1.1.2.1 public String toString() {
1763 cananian 1.1.2.1 return "xNullConstant: null";
1764 cananian 1.1.2.1 }
1765 cananian 1.1.2.21 public boolean equals(Object o) { return _equals(o); }
1766 cananian 1.1.2.21 private boolean _equals(Object o) {
1767 cananian 1.1.2.1 return (o instanceof xNullConstant);
1768 cananian 1.1.2.1 }
1769 cananian 1.1.2.21 public LatticeVal merge(LatticeVal v) {
1770 cananian 1.1.2.21 if (this._equals(v)) return new xNullConstant();
1771 cananian 1.1.2.21 return super.merge(v);
1772 cananian 1.1.2.1 }
1773 cananian 1.1.2.23 public boolean isLowerThan(LatticeVal v) {
1774 cananian 1.1.2.23 return !(v instanceof xNullConstant);
1775 cananian 1.1.2.23 }
1776 cananian 1.1.2.1 }
1777 cananian 1.1.2.11 static class xFloatConstant extends xClassExact
1778 cananian 1.1.2.1 implements xConstant {
1779 cananian 1.1.2.1 protected Object value;
1780 cananian 1.1.2.1 public xFloatConstant(HClass type, Object value) {
1781 cananian 1.1.2.1 super(type); this.value = value;
1782 cananian 1.1.2.1 }
1783 cananian 1.1.2.1 public Object constValue() { return value; }
1784 cananian 1.1.2.1 public String toString() {
1785 cananian 1.1.2.1 return "xFloatConstant: " + type + " " + value.toString();
1786 cananian 1.1.2.1 }
1787 cananian 1.1.2.21 public boolean equals(Object o) { return _equals(o); }
1788 cananian 1.1.2.21 private boolean _equals(Object o) {
1789 cananian 1.1.2.1 return (o instanceof xFloatConstant && super.equals(o) &&
1790 cananian 1.1.2.1 ((xFloatConstant)o).value.equals(value));
1791 cananian 1.1.2.1 }
1792 cananian 1.1.2.21 public LatticeVal merge(LatticeVal v) {
1793 cananian 1.1.2.21 if (this._equals(v)) return new xFloatConstant(type, value);
1794 cananian 1.1.2.21 return super.merge(v);
1795 cananian 1.1.2.1 }
1796 cananian 1.1.2.23 public boolean isLowerThan(LatticeVal v) {
1797 cananian 1.1.2.23 return !(v instanceof xFloatConstant);
1798 cananian 1.1.2.23 }
1799 cananian 1.1.2.1 }
1800 cananian 1.1.2.11 static class xStringConstant extends xClassExact
1801 cananian 1.1.2.1 implements xConstant {
1802 cananian 1.1.2.1 protected Object value;
1803 cananian 1.1.2.1 public xStringConstant(HClass type, Object value) {
1804 cananian 1.1.2.19 super(type);
1805 cananian 1.1.2.19 // note that the string constant objects are intern()ed.
1806 cananian 1.1.2.19 // doing this here ensures that evaluating ACMPEQ with constant
1807 cananian 1.1.2.19 // args works correctly.
1808 cananian 1.1.2.19 this.value = ((String)value).intern();
1809 cananian 1.1.2.1 }
1810 cananian 1.1.2.1 public Object constValue() { return value; }
1811 cananian 1.1.2.1 public String toString() {
1812 cananian 1.1.2.1 return "xStringConstant: " +
1813 cananian 1.7 "\"" + harpoon.Util.Util.escape(value.toString()) + "\"";
1814 cananian 1.1.2.1 }
1815 cananian 1.1.2.21 public boolean equals(Object o) { return _equals(o); }
1816 cananian 1.1.2.21 private boolean _equals(Object o) {
1817 cananian 1.1.2.1 return (o instanceof xStringConstant && super.equals(o) &&
1818 cananian 1.1.2.1 ((xStringConstant)o).value.equals(value));
1819 cananian 1.1.2.1 }
1820 cananian 1.1.2.21 public LatticeVal merge(LatticeVal v) {
1821 cananian 1.1.2.21 if (this._equals(v)) return new xStringConstant(type, value);
1822 cananian 1.1.2.21 return super.merge(v);
1823 cananian 1.1.2.23 }
1824 cananian 1.1.2.23 public boolean isLowerThan(LatticeVal v) {
1825 cananian 1.1.2.23 return !(v instanceof xStringConstant);
1826 cananian 1.1.2.1 }
1827 cananian 1.1.2.1 }
1828 cananian 1.1.2.1 static interface xConstant {
1829 cananian 1.1.2.1 public Object constValue();
1830 cananian 1.1.2.1 }
1831 cananian 1.1.2.22 static interface xInstanceofResult {
1832 cananian 1.1.2.22 public Temp tested();
1833 cananian 1.1.2.22 public INSTANCEOF def();
1834 cananian 1.1.2.22 public xInstanceofResultKnown makeKnown(boolean value);
1835 cananian 1.1.2.22 public xInstanceofResultUnknown makeUnknown();
1836 cananian 1.1.2.22 }
1837 cananian 1.1.2.22 static interface xOperBooleanResult {
1838 cananian 1.1.2.22 public Temp[] operands();
1839 cananian 1.1.2.22 public OPER def();
1840 cananian 1.1.2.22 public xOperBooleanResultKnown makeKnown(boolean value);
1841 cananian 1.1.2.22 public xOperBooleanResultUnknown makeUnknown();
1842 cananian 1.1.2.22 }
1843 cananian 1.1.2.1 /////////////////////////////////////////////////////////
1844 cananian 1.1.2.1 // ways to degrade the analysis to collect statistics.
1845 cananian 1.1.2.1 private final Corruptor corruptor = null; // no corruption.
1846 cananian 1.1.2.1 private final boolean useSigmas = true;
1847 cananian 1.1.2.1 /** A <code>Corruptor</code> lets you 'dumb-down' the analysis
1848 cananian 1.1.2.1 * incrementally, so that we can generate numbers showing that
1849 cananian 1.1.2.1 * every step makes it better and better. */
1850 cananian 1.1.2.1 static abstract class Corruptor {
1851 cananian 1.1.2.1 /** make this lattice value worse than we know it to be. */
1852 cananian 1.1.2.1 abstract LatticeVal corrupt(LatticeVal v);
1853 cananian 1.1.2.1 }
1854 cananian 1.1.2.1 static final Corruptor nobitwidth = new Corruptor() {
1855 cananian 1.1.2.1 public LatticeVal corrupt(LatticeVal v) {
1856 cananian 1.1.2.22 if (v!=null && v.toString().startsWith("xBitWidth:"))
1857 cananian 1.1.2.22 return new xClassExact(((xClassExact)v).type);
1858 cananian 1.1.2.1 return v;
1859 cananian 1.1.2.1 }
1860 cananian 1.1.2.1 };
1861 cananian 1.1.2.1 static final Corruptor nofixedarray = new Corruptor() {
1862 cananian 1.1.2.1 public LatticeVal corrupt(LatticeVal v) {
1863 cananian 1.1.2.1 v = nobitwidth.corrupt(v);
1864 cananian 1.1.2.1 if (v instanceof xClassArray)
1865 cananian 1.1.2.1 return new xClassNonNull(((xClassNonNull)v).type);
1866 cananian 1.1.2.1 return v;
1867 cananian 1.1.2.1 }
1868 cananian 1.1.2.1 };
1869 cananian 1.1.2.1 static final Corruptor nonullpointer = new Corruptor() {
1870 cananian 1.1.2.1 public LatticeVal corrupt(LatticeVal v) {
1871 cananian 1.1.2.1 if (v instanceof xClassNonNull)
1872 cananian 1.1.2.1 return new xClass(((xClassNonNull)v).type);
1873 cananian 1.1.2.1 return v;
1874 cananian 1.1.2.1 }
1875 cananian 1.1.2.1 };
1876 cananian 1.1.2.1 static final Corruptor nononint = new Corruptor() {
1877 cananian 1.1.2.1 public LatticeVal corrupt(LatticeVal v) {
1878 cananian 1.1.2.1 v = nonullpointer.corrupt(v);
1879 cananian 1.1.2.1 if (v instanceof xFloatConstant ||
1880 cananian 1.1.2.1 v instanceof xStringConstant ||
1881 cananian 1.1.2.1 (v instanceof xIntConstant && ((xClass)v).type!=HClass.Int))
1882 cananian 1.1.2.1 return new xClass(((xClass)v).type);
1883 cananian 1.1.2.1 return v;
1884 cananian 1.1.2.1 }
1885 cananian 1.1.2.1 };
1886 cananian 1.2 }