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.SizeOpt;
5 cananian 1.1.2.1
6 cananian 1.1.2.2 import harpoon.Analysis.ClassHierarchy;
7 cananian 1.3 import harpoon.Analysis.Context;
8 cananian 1.3 import harpoon.Analysis.GenericContextFactory;
9 cananian 1.1.2.1 import harpoon.Analysis.Maps.ConstMap;
10 cananian 1.1.2.1 import harpoon.Analysis.Maps.ExactTypeMap;
11 cananian 1.1.2.1 import harpoon.Analysis.Maps.ExecMap;
12 cananian 1.1.2.1 import harpoon.Analysis.Maps.UseDefMap;
13 cananian 1.1.2.17 import harpoon.Analysis.Quads.DefiniteInitOracle;
14 cananian 1.1.2.1 import harpoon.ClassFile.HClass;
15 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
16 cananian 1.1.2.1 import harpoon.ClassFile.HCodeEdge;
17 cananian 1.1.2.1 import harpoon.ClassFile.HCodeElement;
18 cananian 1.1.2.2 import harpoon.ClassFile.HCodeFactory;
19 cananian 1.1.2.1 import harpoon.ClassFile.HField;
20 cananian 1.1.2.1 import harpoon.ClassFile.HMethod;
21 cananian 1.1.2.1 import harpoon.ClassFile.Linker;
22 cananian 1.1.2.1 import harpoon.IR.Quads.AGET;
23 cananian 1.1.2.1 import harpoon.IR.Quads.ALENGTH;
24 cananian 1.1.2.1 import harpoon.IR.Quads.ANEW;
25 cananian 1.1.2.1 import harpoon.IR.Quads.ASET;
26 cananian 1.1.2.1 import harpoon.IR.Quads.CALL;
27 cananian 1.1.2.1 import harpoon.IR.Quads.CJMP;
28 cananian 1.1.2.1 import harpoon.IR.Quads.COMPONENTOF;
29 cananian 1.1.2.1 import harpoon.IR.Quads.CONST;
30 cananian 1.1.2.1 import harpoon.IR.Quads.Edge;
31 cananian 1.1.2.1 import harpoon.IR.Quads.FOOTER;
32 cananian 1.1.2.1 import harpoon.IR.Quads.GET;
33 cananian 1.1.2.1 import harpoon.IR.Quads.HEADER;
34 cananian 1.1.2.1 import harpoon.IR.Quads.INSTANCEOF;
35 cananian 1.1.2.1 import harpoon.IR.Quads.METHOD;
36 cananian 1.1.2.1 import harpoon.IR.Quads.MONITORENTER;
37 cananian 1.1.2.1 import harpoon.IR.Quads.MONITOREXIT;
38 cananian 1.1.2.1 import harpoon.IR.Quads.MOVE;
39 cananian 1.1.2.1 import harpoon.IR.Quads.NEW;
40 cananian 1.1.2.1 import harpoon.IR.Quads.NOP;
41 cananian 1.1.2.1 import harpoon.IR.Quads.OPER;
42 cananian 1.1.2.1 import harpoon.IR.Quads.OperVisitor;
43 cananian 1.1.2.1 import harpoon.IR.Quads.PHI;
44 cananian 1.1.2.1 import harpoon.IR.Quads.Qop;
45 cananian 1.1.2.1 import harpoon.IR.Quads.Quad;
46 cananian 1.1.2.2 import harpoon.IR.Quads.QuadFactory;
47 cananian 1.1.2.1 import harpoon.IR.Quads.QuadSSI;
48 cananian 1.1.2.1 import harpoon.IR.Quads.QuadVisitor;
49 cananian 1.1.2.1 import harpoon.IR.Quads.RETURN;
50 cananian 1.1.2.1 import harpoon.IR.Quads.SET;
51 cananian 1.1.2.1 import harpoon.IR.Quads.SIGMA;
52 cananian 1.1.2.1 import harpoon.IR.Quads.SWITCH;
53 cananian 1.1.2.1 import harpoon.IR.Quads.THROW;
54 cananian 1.1.2.1 import harpoon.IR.Quads.TYPESWITCH;
55 cananian 1.1.2.1 import harpoon.Temp.Temp;
56 cananian 1.1.2.1 import harpoon.Temp.TempMap;
57 cananian 1.9 import net.cscott.jutil.Default;
58 cananian 1.1.2.1 import harpoon.Util.HClassUtil;
59 cananian 1.1.2.9 import harpoon.Util.ParseUtil;
60 cananian 1.1.2.20 import harpoon.Util.Collections.WorkSet;
61 cananian 1.1.2.2 import harpoon.Util.Worklist;
62 cananian 1.9 import net.cscott.jutil.AggregateMapFactory;
63 cananian 1.9 import net.cscott.jutil.AggregateSetFactory;
64 cananian 1.9 import net.cscott.jutil.Factories;
65 cananian 1.9 import net.cscott.jutil.GenericMultiMap;
66 cananian 1.9 import net.cscott.jutil.MapSet;
67 cananian 1.9 import net.cscott.jutil.MultiMap;
68 cananian 1.9 import net.cscott.jutil.MultiMapSet;
69 cananian 1.1.2.1
70 cananian 1.1.2.2 import java.lang.reflect.Modifier;
71 cananian 1.1.2.4 import java.util.Arrays;
72 cananian 1.1.2.3 import java.util.ArrayList;
73 cananian 1.1.2.2 import java.util.Collection;
74 cananian 1.1.2.1 import java.util.HashMap;
75 cananian 1.1.2.1 import java.util.HashSet;
76 cananian 1.1.2.2 import java.util.Iterator;
77 cananian 1.1.2.3 import java.util.List;
78 cananian 1.1.2.1 import java.util.Map;
79 cananian 1.1.2.1 import java.util.Set;
80 cananian 1.9
81 cananian 1.9 import net.cscott.jutil.Util;
82 cananian 1.1.2.1 /**
83 cananian 1.1.2.1 * <code>BitWidthAnalysis</code> implements Sparse Conditional Constant
84 cananian 1.1.2.1 * Propagation, with extensions to allow type and bitwidth analysis.
85 cananian 1.1.2.1 * It combines the intraprocedural SCC analysis with an interprocedural
86 cananian 1.1.2.1 * driver to infer the widths of object fields.
87 cananian 1.1.2.1 * <p>Only works with quads in SSI form.
88 cananian 1.1.2.1 *
89 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
90 cananian 1.10 * @version $Id: BitWidthAnalysis.java,v 1.10 2004/02/08 03:20:22 cananian Exp $
91 cananian 1.1.2.1 */
92 cananian 1.1.2.1
93 cananian 1.1.2.1 public class BitWidthAnalysis implements ExactTypeMap, ConstMap, ExecMap {
94 cananian 1.1.2.14 final static int CONTEXT_SENSITIVITY =
95 cananian 1.1.2.14 Integer.parseInt(System.getProperty("harpoon.sizeopt.context", "0"));
96 cananian 1.1.2.5 final static boolean DEBUG = false;
97 cananian 1.1.2.1 final Linker linker;
98 cananian 1.1.2.2 final HCodeFactory hcf;
99 cananian 1.1.2.2 final ClassHierarchy ch;
100 cananian 1.1.2.17 final DefiniteInitOracle dio;
101 cananian 1.1.2.1
102 cananian 1.1.2.9 public BitWidthAnalysis(Linker linker, HCodeFactory hcf,
103 cananian 1.1.2.9 ClassHierarchy ch, Set roots, String resourceName){
104 cananian 1.1.2.9 this(linker, hcf, ch, roots, parseResource(linker, resourceName));
105 cananian 1.1.2.9 }
106 cananian 1.1.2.1 /** Creates a <code>BitWidthAnalysis</code>. */
107 cananian 1.1.2.2 public BitWidthAnalysis(Linker linker, HCodeFactory hcf,
108 cananian 1.1.2.9 ClassHierarchy ch, Set roots, Set fieldRoots) {
109 cananian 1.4.2.1 assert hcf.getCodeName().equals(QuadSSI.codename);
110 cananian 1.1.2.2 this.linker = linker;
111 cananian 1.1.2.2 this.hcf = hcf;
112 cananian 1.1.2.2 this.ch = ch;
113 cananian 1.1.2.17 this.dio = new DefiniteInitOracle(hcf, ch);
114 cananian 1.1.2.9 analyze(roots, fieldRoots);
115 cananian 1.1.2.5 /* accounting: */
116 cananian 1.1.2.5 long before=0, before8=0, after=0, after8=0;
117 cananian 1.10 for (Object hfO : Vf.keySet()) {
118 cananian 1.10 HField hf = (HField) hfO;
119 cananian 1.1.2.5 HClass ty = hf.getType();
120 cananian 1.1.2.5 if (ty==HClass.Byte) { before+=8+7; before8+=1; }
121 cananian 1.1.2.5 else if (ty==HClass.Short) { before+=16+15; before8+=2; }
122 cananian 1.1.2.5 else if (ty==HClass.Char) { before+=0+16; before8+=2; }
123 cananian 1.1.2.5 else if (ty==HClass.Boolean) { before+=0+1; before8+=1; }
124 cananian 1.1.2.5 else if (ty==HClass.Int) { before+=32+31; before8+=4; }
125 cananian 1.1.2.5 else if (ty==HClass.Long) { before+=64+63; before8+=8; }
126 cananian 1.1.2.5 else continue; // not an integer type.
127 cananian 1.1.2.5 xBitWidth small= extractWidth((LatticeVal) Vf.get(hf));
128 cananian 1.1.2.5 after+=small.plusWidth()+small.minusWidth();
129 cananian 1.1.2.5 // round to byte allocations.
130 cananian 1.1.2.5 int bytes = (Math.max(small.minusWidth(),small.plusWidth())+7)/8;
131 cananian 1.1.2.5 after8 += bytes==3 ? 4 : bytes;
132 cananian 1.1.2.5 }
133 cananian 1.1.2.10 System.out.println("BITWIDTH RESULTS: "+after+"/"+before+" bits; "+
134 cananian 1.1.2.10 after8+"/"+before8+" bytes");
135 cananian 1.1.2.6 HashSet flds = new HashSet(5*ch.classes().size());
136 cananian 1.1.2.6 for (Iterator it=ch.classes().iterator(); it.hasNext(); )
137 cananian 1.1.2.6 flds.addAll(Arrays.asList(((HClass)it.next()).getFields()));
138 cananian 1.1.2.6 for (Iterator it=flds.iterator(); it.hasNext(); )
139 cananian 1.1.2.6 if (((HField)it.next()).isStatic()) it.remove();
140 cananian 1.1.2.6 int ttl = flds.size();
141 cananian 1.1.2.6 flds.retainAll(fieldMap.keySet());
142 cananian 1.1.2.6 int lft = flds.size();
143 cananian 1.1.2.6 for (Iterator it=flds.iterator(); it.hasNext(); )
144 cananian 1.1.2.6 if (isConst((HField)it.next())) it.remove();
145 cananian 1.1.2.6 int lss = flds.size();
146 cananian 1.1.2.6 System.out.println("BITWIDTH RESULTS: "+lss+"/"+lft+"/"+ttl+" unread fields");
147 cananian 1.1.2.22 System.out.println("TOTAL CLASSES: "+ch.classes().size());
148 cananian 1.1.2.1 }
149 cananian 1.1.2.1
150 cananian 1.1.2.1 /*-----------------------------*/
151 cananian 1.1.2.1 // Class state.
152 cananian 1.1.2.14 /** Base Context */
153 cananian 1.3 final Context base =
154 cananian 1.3 new GenericContextFactory(CONTEXT_SENSITIVITY, true)
155 cananian 1.3 .makeEmptyContext();
156 cananian 1.1.2.14 /** Set of all executable [edge,context] pairs. */
157 cananian 1.1.2.14 final MultiMapSet Ee = (MultiMapSet)
158 cananian 1.1.2.14 new GenericMultiMap(new AggregateSetFactory()).entrySet();
159 cananian 1.1.2.14 /** Set of all executable [quad,context] pairs. */
160 cananian 1.1.2.14 final MultiMapSet Eq = (MultiMapSet)
161 cananian 1.1.2.14 new GenericMultiMap(new AggregateSetFactory()).entrySet();
162 cananian 1.1.2.14 /** Mapping from <code>Temp</code>s to [context,lattice value] pairs. */
163 cananian 1.1.2.14 final MultiMap V = new GenericMultiMap
164 cananian 1.1.2.14 (Factories.mapSetFactory(new AggregateMapFactory()));
165 cananian 1.1.2.2 /** Mapping from <code>HField</code>s to lattice values. */
166 cananian 1.1.2.2 final Map Vf = new HashMap();
167 cananian 1.1.2.2 /** Mapping from <code>Temp</code>s to <code>Quad</code>s which use them.*/
168 cananian 1.1.2.2 final MultiMap useMap = new GenericMultiMap(Factories.arrayListFactory);
169 cananian 1.1.2.14 /** Mapping from <code>HField</code>s to
170 cananian 1.1.2.14 * [<code>Quad</code>,<code>Context</code>]) pairs which read them. */
171 cananian 1.1.2.2 final MultiMap fieldMap = new GenericMultiMap(new AggregateSetFactory());
172 cananian 1.1.2.9 /** Set of root fields */
173 cananian 1.1.2.9 final Set fieldRoots = new HashSet();
174 cananian 1.1.2.3 /** Mapping from <code>HMethod</code>s to <code>METHOD</code>s. */
175 cananian 1.1.2.3 final Map methodMap = new HashMap();
176 cananian 1.1.2.14 /** Mapping from [<code>HMethod</code>s, callee context] to
177 cananian 1.1.2.14 * [<code>CALL</code> quad, caller context] pairs which may invoke
178 cananian 1.1.2.14 * them (with the specified callee context). */
179 cananian 1.1.2.3 final MultiMap callMap = new GenericMultiMap(new AggregateSetFactory());
180 cananian 1.1.2.14 /** Mapping from [<code>HMethod</code>,callee context] pairs to all
181 cananian 1.1.2.14 * executable <code>RETURN</code>s in that context. */
182 cananian 1.1.2.6 final MultiMap returnMap = new GenericMultiMap(new AggregateSetFactory());
183 cananian 1.1.2.14 /** Mapping from [<code>HMethod</code>,callee context] pairs to all
184 cananian 1.1.2.14 * executable <code>THROW</code>s in that context. */
185 cananian 1.1.2.6 final MultiMap throwMap = new GenericMultiMap(new AggregateSetFactory());
186 cananian 1.8 /** Keep a list around of all the 'definitely initialized' fields
187 cananian 1.8 * we're asked about. Some of these may need to be thunked with
188 cananian 1.8 * a value because their declaring class ends up never instantiated.
189 cananian 1.8 */
190 cananian 1.8 final Set diFields = new HashSet();
191 cananian 1.1.2.1
192 cananian 1.1.2.1 /*---------------------------*/
193 cananian 1.1.2.1 // public information accessor methods.
194 cananian 1.1.2.1
195 cananian 1.1.2.6 /** Determine whether the given <code>HField</code> is ever read. */
196 cananian 1.1.2.6 public boolean isRead(HField hf) {
197 cananian 1.1.2.9 return fieldMap.containsKey(hf) || fieldRoots.contains(hf);
198 cananian 1.1.2.6 }
199 cananian 1.1.2.1 /** Determine whether <code>Quad</code> <code>q</code>
200 cananian 1.1.2.1 * is executable. */
201 cananian 1.1.2.1 public boolean execMap(HCodeElement quad) {
202 cananian 1.1.2.14 return Eq.asMultiMap().containsKey(quad);
203 cananian 1.1.2.1 }
204 cananian 1.1.2.1 /** Determine whether <code>Edge</code> <code>e</code>
205 cananian 1.1.2.1 * is executable. */
206 cananian 1.1.2.1 public boolean execMap(HCodeEdge edge) {
207 cananian 1.1.2.14 return Ee.asMultiMap().containsKey(edge);
208 cananian 1.1.2.14 }
209 cananian 1.1.2.14 /** Merge types for <code>Temp</code> t over all contexts in which it
210 cananian 1.1.2.14 * is defined. */
211 cananian 1.1.2.14 private LatticeVal VforAllContexts(Temp t) {
212 cananian 1.1.2.14 // merge over v's type in all contexts.
213 cananian 1.1.2.14 LatticeVal v=null; // start.
214 cananian 1.1.2.14 // V is a map from t to a map from context to value.
215 cananian 1.1.2.14 // get all values for t
216 cananian 1.1.2.14 for (Iterator it=((MapSet)V.getValues(t)).asMap().values().iterator();
217 cananian 1.1.2.14 it.hasNext(); ) {
218 cananian 1.1.2.14 // merge the values.
219 cananian 1.1.2.14 if (v==null) v = (LatticeVal) it.next();
220 cananian 1.1.2.14 else v = v.merge((LatticeVal) it.next());
221 cananian 1.1.2.14 }
222 cananian 1.1.2.14 // return merged value, or null if there were no values.
223 cananian 1.1.2.14 return v;
224 cananian 1.1.2.1 }
225 cananian 1.1.2.1 /** Determine the static type of <code>Temp</code> <code>t</code> in
226 cananian 1.1.2.1 * <code>HMethod</code> <code>m</code>. */
227 cananian 1.1.2.1 public HClass typeMap(HCodeElement hce, Temp t) {
228 cananian 1.1.2.14 LatticeVal v = VforAllContexts(t);
229 cananian 1.1.2.1 if (v instanceof xClass) return ((xClass)v).type();
230 cananian 1.1.2.1 return null;
231 cananian 1.1.2.1 }
232 cananian 1.1.2.6 /** Determine the static type of <code>Temp</code> <code>t</code> in
233 cananian 1.1.2.6 * <code>HMethod</code> <code>m</code>. */
234 cananian 1.1.2.6 public HClass typeMap(HField hf) {
235 cananian 1.1.2.6 LatticeVal v = get( hf );
236 cananian 1.1.2.6 if (v instanceof xClass) return ((xClass)v).type();
237 cananian 1.1.2.6 return null;
238 cananian 1.1.2.6 }
239 cananian 1.1.2.1 /** Determine whether the static type of <code>Temp</code> <code>t</code>
240 cananian 1.1.2.1 * defined at <code>hce</code> is exact (or whether the runtime type
241 cananian 1.1.2.1 * could be a subclass of the static type). */
242 cananian 1.1.2.1 public boolean isExactType(HCodeElement hce, Temp t) {
243 cananian 1.1.2.1 // ignore hce
244 cananian 1.1.2.14 return VforAllContexts(t) instanceof xClassExact;
245 cananian 1.1.2.1 }
246 cananian 1.1.2.1 /** Determine whether the given <code>Temp</code> can possibly be
247 cananian 1.1.2.1 * <code>null</code>. */
248 cananian 1.1.2.1 public boolean isPossiblyNull(HCodeElement hce, Temp t) {
249 cananian 1.1.2.14 return !(VforAllContexts(t) instanceof xClassNonNull);
250 cananian 1.1.2.1 }
251 cananian 1.1.2.1 /** Determine whether <code>Temp</code> <code>t</code>
252 cananian 1.1.2.1 * has a constant value. */
253 cananian 1.1.2.1 public boolean isConst(HCodeElement hce, Temp t) {
254 cananian 1.1.2.1 // ignore hce -- this is SSA form
255 cananian 1.1.2.14 return (VforAllContexts(t) instanceof xConstant);
256 cananian 1.1.2.1 }
257 cananian 1.1.2.1 /** Determine the constant value of <code>Temp</code> <code>t</code>.
258 cananian 1.1.2.1 * @exception Error if <code>Temp</code> <code>t</code> is not a constant.
259 cananian 1.1.2.1 */
260 cananian 1.1.2.1 public Object constMap(HCodeElement hce, Temp t) {
261 cananian 1.1.2.1 // ignore hce -- this is SSA form.
262 cananian 1.1.2.14 LatticeVal v = VforAllContexts(t);
263 cananian 1.1.2.1 if (v instanceof xConstant) return ((xConstant)v).constValue();
264 cananian 1.1.2.1 throw new Error(t.toString() + " not a constant");
265 cananian 1.1.2.1 }
266 cananian 1.1.2.6 /** Determine whether <code>HField</code> <code>hf</code>
267 cananian 1.1.2.6 * has a constant value. */
268 cananian 1.1.2.6 public boolean isConst(HField hf) {
269 cananian 1.1.2.6 return (get(hf) instanceof xConstant);
270 cananian 1.1.2.6 }
271 cananian 1.1.2.6 /** Determine the constant value of <code>HField</code> <code>hf</code>.
272 cananian 1.1.2.6 * @exception Error if <code>HField</code> <code>hf</code> is not a
273 cananian 1.1.2.6 * constant.
274 cananian 1.1.2.6 */
275 cananian 1.1.2.6 public Object constMap(HField hf) {
276 cananian 1.1.2.6 LatticeVal v = get(hf);
277 cananian 1.1.2.6 if (v instanceof xConstant) return ((xConstant)v).constValue();
278 cananian 1.1.2.6 throw new Error(hf + " not a constant");
279 cananian 1.1.2.6 }
280 cananian 1.1.2.1
281 cananian 1.1.2.1 /** Determine the positive bit width of <code>Temp</code> <code>t</code>.
282 cananian 1.1.2.1 */
283 cananian 1.1.2.1 public int plusWidthMap(HCodeElement hce, Temp t) {
284 cananian 1.1.2.1 // ignore hce -- this is SSA form
285 cananian 1.1.2.14 LatticeVal v = VforAllContexts(t);
286 cananian 1.1.2.1 if (v==null) throw new Error("Unknown "+t);
287 cananian 1.1.2.1 xBitWidth bw = extractWidth(v);
288 cananian 1.1.2.1 return bw.plusWidth();
289 cananian 1.1.2.1 }
290 cananian 1.1.2.1 /** Determine the negative bit width of <code>Temp</code> <code>t</code>.
291 cananian 1.1.2.1 */
292 cananian 1.1.2.1 public int minusWidthMap(HCodeElement hce, Temp t) {
293 cananian 1.1.2.1 // ignore hce -- this is SSA form.
294 cananian 1.1.2.14 LatticeVal v = VforAllContexts(t);
295 cananian 1.1.2.1 if (v==null) throw new Error("Unknown "+t);
296 cananian 1.1.2.1 xBitWidth bw = extractWidth(v);
297 cananian 1.1.2.1 return bw.minusWidth();
298 cananian 1.1.2.1 }
299 cananian 1.1.2.6 /** Determine the positive bit width of <code>HField</code>
300 cananian 1.1.2.6 * <code>hf</code>.
301 cananian 1.1.2.6 */
302 cananian 1.1.2.6 public int plusWidthMap(HField hf) {
303 cananian 1.1.2.6 LatticeVal v = get( hf );
304 cananian 1.1.2.6 if (v==null) throw new Error("Unknown "+hf);
305 cananian 1.1.2.6 xBitWidth bw = extractWidth(v);
306 cananian 1.1.2.6 return bw.plusWidth();
307 cananian 1.1.2.6 }
308 cananian 1.1.2.6 /** Determine the negative bit width of <code>HField</code>
309 cananian 1.1.2.6 * <code>hf</code>.
310 cananian 1.1.2.6 */
311 cananian 1.1.2.6 public int minusWidthMap(HField hf) {
312 cananian 1.1.2.6 LatticeVal v = get( hf );
313 cananian 1.1.2.6 if (v==null) throw new Error("Unknown "+hf);
314 cananian 1.1.2.6 xBitWidth bw = extractWidth(v);
315 cananian 1.1.2.6 return bw.minusWidth();
316 cananian 1.1.2.6 }
317 cananian 1.1.2.1
318 cananian 1.1.2.3 /** Create methodMap, useMap */
319 cananian 1.1.2.3 private void scan_one(HMethod hm) {
320 cananian 1.1.2.2 HCode hc = hcf.convert(hm);
321 cananian 1.1.2.2 if (hc==null) return; // abstract method.
322 cananian 1.1.2.3 if (DEBUG) System.out.println("SCAN_ONE: "+hm);
323 cananian 1.1.2.2 for (Iterator it=hc.getElementsI(); it.hasNext(); ) {
324 cananian 1.1.2.2 Quad q = (Quad) it.next();
325 cananian 1.1.2.2 // add entries to useMap.
326 cananian 1.1.2.2 Temp[] used = q.use();
327 cananian 1.1.2.2 for (int i=0; i<used.length; i++)
328 cananian 1.1.2.2 useMap.add(used[i], q);
329 cananian 1.1.2.3 // add entry to methodMap
330 cananian 1.1.2.3 if (q instanceof METHOD)
331 cananian 1.1.2.3 methodMap.put(hm, q);
332 cananian 1.1.2.2 }
333 cananian 1.1.2.2 }
334 cananian 1.1.2.2
335 cananian 1.1.2.1 /*---------------------------*/
336 cananian 1.1.2.1 // Analysis code.
337 cananian 1.1.2.1
338 cananian 1.1.2.1 /** Main analysis method. */
339 cananian 1.1.2.9 private void analyze(Set roots, Set my_fieldRoots) {
340 cananian 1.1.2.1 // Initialize worklists.
341 cananian 1.1.2.1 Worklist Wv = new WorkSet(); // variable worklist.
342 cananian 1.1.2.1 Worklist Wq = new WorkSet(); // block worklist.
343 cananian 1.1.2.2 Worklist Wf = new WorkSet(); // field worklist.
344 cananian 1.1.2.1
345 cananian 1.1.2.1 // Make instance of visitor class.
346 cananian 1.1.2.2 SCCVisitor visitor = new SCCVisitor(Wv, Wq, Wf);
347 cananian 1.1.2.1
348 cananian 1.1.2.3 // make root methods set (ignore classes)
349 cananian 1.1.2.3 List root_methods = new ArrayList(roots);
350 cananian 1.1.2.3 for (Iterator it=root_methods.iterator(); it.hasNext(); )
351 cananian 1.1.2.3 if (!(it.next() instanceof HMethod))
352 cananian 1.1.2.3 it.remove();
353 cananian 1.1.2.3 // all static initializers to root methods set
354 cananian 1.1.2.3 for (Iterator it=ch.classes().iterator(); it.hasNext(); ) {
355 cananian 1.1.2.3 HMethod hm = ((HClass)it.next()).getClassInitializer();
356 cananian 1.1.2.3 if (hm!=null) root_methods.add(hm);
357 cananian 1.1.2.3 }
358 cananian 1.1.2.3 // put all root methods on the worklist & mark as executable.
359 cananian 1.10 for (Object hmO : root_methods) {
360 cananian 1.10 HMethod hm = (HMethod) hmO;
361 cananian 1.1.2.3 scan_one(hm);
362 cananian 1.1.2.3 METHOD method = (METHOD) methodMap.get(hm);
363 cananian 1.1.2.3 if (method==null) continue; // native method in root set.
364 cananian 1.1.2.14 Wq.push(Default.pair(base, method));
365 cananian 1.1.2.14 Eq.add(Default.entry(method,base));
366 cananian 1.1.2.3 // set up parameters.
367 cananian 1.1.2.3 int j=0;
368 cananian 1.1.2.3 if ( !hm.isStatic() ) // raise 'this' variable (non-null!)
369 cananian 1.1.2.14 raiseV(V, Wv, base, method.params(j++),
370 cananian 1.1.2.3 new xClassNonNull( hm.getDeclaringClass() ) );
371 cananian 1.1.2.3 HClass[] pt = hm.getParameterTypes();
372 cananian 1.1.2.3 for (int k=0; k < pt.length; j++, k++)
373 cananian 1.1.2.14 raiseV(V, Wv, base, method.params(j),
374 cananian 1.1.2.3 pt[k].isPrimitive() ?
375 cananian 1.1.2.3 new xClassNonNull( toInternal(pt[k]) ) :
376 cananian 1.1.2.3 new xClass( pt[k] ) );
377 cananian 1.1.2.3 }
378 cananian 1.1.2.3 // XXX: main method *could* use xClassExact on String[] arg.
379 cananian 1.1.2.1
380 cananian 1.1.2.9 // raise field root types.
381 cananian 1.10 for (Object hfO : my_fieldRoots) {
382 cananian 1.10 HField hf = (HField) hfO;
383 cananian 1.1.2.9 HClass ty = hf.getType();
384 cananian 1.1.2.14 mergeV(Wf, hf, ty.isPrimitive() ?
385 cananian 1.1.2.9 new xClassNonNull( toInternal(ty) ) :
386 cananian 1.1.2.9 new xClass( ty ) );
387 cananian 1.1.2.9 this.fieldRoots.add(hf);
388 cananian 1.1.2.6 }
389 cananian 1.1.2.6
390 cananian 1.1.2.2 // Iterate until worklists are empty.
391 cananian 1.8 do {
392 cananian 1.1.2.2 while (! (Wq.isEmpty() && Wv.isEmpty() && Wf.isEmpty()) ) {
393 cananian 1.1.2.1
394 cananian 1.1.2.1 if (!Wq.isEmpty()) { // grab statement from We if we can.
395 cananian 1.1.2.14 List pair = (List) Wq.pull();
396 cananian 1.1.2.14 Context c = (Context) pair.get(0);
397 cananian 1.1.2.14 Quad q = (Quad) pair.get(1);
398 cananian 1.1.2.1 // Rule 2: for any executable block with
399 cananian 1.1.2.1 // only one successor C, set edge leading to C executable.
400 cananian 1.1.2.7 if (q.nextLength()==1) {
401 cananian 1.1.2.14 raiseE(Ee, Eq, Wq, c, q.nextEdge(0));
402 cananian 1.1.2.1 }
403 cananian 1.1.2.1 // check conditions 3-8 for q.
404 cananian 1.1.2.14 visitor.context = c;
405 cananian 1.1.2.1 q.accept(visitor);
406 cananian 1.1.2.1 }
407 cananian 1.1.2.1
408 cananian 1.1.2.2 if (!Wv.isEmpty()) { // grab temp from Wv if possible.
409 cananian 1.1.2.14 List pair = (List) Wv.pull();
410 cananian 1.1.2.14 Context c = (Context) pair.get(0);
411 cananian 1.1.2.14 Temp t = (Temp) pair.get(1);
412 cananian 1.1.2.1 // for every use of t...
413 cananian 1.1.2.14 for (Iterator it=useMap.getValues(t).iterator();it.hasNext();){
414 cananian 1.1.2.1 // check conditions 3-8
415 cananian 1.1.2.14 visitor.context = c;
416 cananian 1.1.2.2 ((Quad) it.next()).accept(visitor);
417 cananian 1.1.2.14 }
418 cananian 1.1.2.2 }
419 cananian 1.1.2.2
420 cananian 1.1.2.2 if (!Wf.isEmpty()) { // grab field from Wf if possible.
421 cananian 1.1.2.2 HField hf = (HField) Wf.pull();
422 cananian 1.1.2.2 // for every read of hf...
423 cananian 1.10 for (Object pairO : fieldMap.getValues(hf)) {
424 cananian 1.10 List pair = (List) pairO;
425 cananian 1.1.2.14 visitor.context = (Context) pair.get(0);
426 cananian 1.1.2.2 // check conditions 3-8
427 cananian 1.1.2.14 ((Quad) pair.get(1)).accept(visitor);
428 cananian 1.1.2.14 }
429 cananian 1.1.2.1 }
430 cananian 1.1.2.1 } // end while loop.
431 cananian 1.8
432 cananian 1.8 // OKAY, sometimes we get in a weird spot: we've left definitely
433 cananian 1.8 // intialized fields at bottom, but then their declaring fields
434 cananian 1.8 // end up uninstantiated (this analysis tells us their constructors
435 cananian 1.8 // are never called; but the classhierarchy wasn't smart enough
436 cananian 1.8 // to know this). Now the uses of those fields are left hanging
437 cananian 1.8 // around, still waiting for a value from the definite initializer.
438 cananian 1.8 // We're going to let a separate class hierarchy analysis figure
439 cananian 1.8 // out that the class is uninstantiated LATER, for now we're just
440 cananian 1.8 // going to hack some values into its fields to keep things going.
441 cananian 1.8 // NOTE that these values will never be used at runtime.
442 cananian 1.8 boolean changed = false;
443 cananian 1.10 for (Object hfO : diFields) {
444 cananian 1.10 HField hf = (HField) hfO;
445 cananian 1.8 if (get(hf)==null) { // STILL BOTTOM!
446 cananian 1.8 System.err.println("INFO: "+hf.getDeclaringClass()+
447 cananian 1.8 " is uninstantiated!");
448 cananian 1.8 // set to zero value.
449 cananian 1.8 changed = true;
450 cananian 1.8 HClass type = hf.getType();
451 cananian 1.8 if (!type.isPrimitive())
452 cananian 1.8 mergeV(Wf, hf, new xNullConstant());
453 cananian 1.8 else if (type==HClass.Float)
454 cananian 1.8 mergeV(Wf, hf, new xFloatConstant(type, new Float(0.0)));
455 cananian 1.8 else if (type == HClass.Double)
456 cananian 1.8 mergeV(Wf, hf, new xFloatConstant(type, new Double(0.0)));
457 cananian 1.8 else if (type == HClass.Int || type==HClass.Long)
458 cananian 1.8 mergeV(Wf, hf, new xIntConstant(type, 0 ));
459 cananian 1.8 else throw new Error("Unknown field type: "+type);
460 cananian 1.8 }
461 cananian 1.8 }
462 cananian 1.8 diFields.clear();
463 cananian 1.8 // wouldn't a goto statement be so much clearer?
464 cananian 1.8 if (!changed) break;
465 cananian 1.8 } while (true); // go up and do it all again.
466 cananian 1.1.2.1 } // end analysis.
467 cananian 1.1.2.1
468 cananian 1.1.2.1 /*----------------------------------------*/
469 cananian 1.1.2.1 // raising values in the lattice:
470 cananian 1.1.2.1
471 cananian 1.1.2.1 /** Raise edge e in Ee/Eq, adding target q to Wq if necessary. */
472 cananian 1.1.2.14 void raiseE(Set Ee, Set Eq, Worklist Wq, Context c, Edge e) {
473 cananian 1.1.2.1 Quad q = (Quad) e.to();
474 cananian 1.1.2.21 if (Ee.add(Default.entry(e, c))) {
475 cananian 1.1.2.21 // if making this edge executable for the first time, verify
476 cananian 1.1.2.21 // that destination 'q' is marked executable, and add q to the
477 cananian 1.1.2.21 // work list to be looked at (may be a PHI, needs to be re-eval).
478 cananian 1.1.2.21 // NOTE that this works even if: quad's already been added
479 cananian 1.1.2.21 // to Eq (this may happen for PHIs) and even if this edge leads
480 cananian 1.1.2.21 // to itself (infinite loop in the program).
481 cananian 1.1.2.21 Eq.add(Default.entry(q,c));
482 cananian 1.1.2.21 Wq.push(Default.pair(c, q));
483 cananian 1.1.2.21 }
484 cananian 1.1.2.1 }
485 cananian 1.1.2.1 /** Raise element t to a in V, adding t to Wv if necessary. */
486 cananian 1.1.2.14 void raiseV(MultiMap V, Worklist Wv, Context c, Temp t, LatticeVal a) {
487 cananian 1.4.2.1 assert a!=null;
488 cananian 1.1.2.14 LatticeVal old = get( c, t );
489 cananian 1.1.2.1 if (corruptor!=null) a=corruptor.corrupt(a); // support incrementalism
490 cananian 1.1.2.1 // only allow raising value in lattice.
491 cananian 1.1.2.4 if (old != null) {
492 cananian 1.1.2.4 a = a.merge(old);
493 cananian 1.1.2.4 if (old.equals(a) && a.equals(old)) return; // same old same old
494 cananian 1.1.2.4 }
495 cananian 1.1.2.14 ((MapSet)V.getValues(t)).asMap().put(c, a);
496 cananian 1.1.2.14 Wv.push(Default.pair(c,t));
497 cananian 1.1.2.1 }
498 cananian 1.1.2.4 /** Merge a with type of element t in V, adding t to Wv if necessary. */
499 cananian 1.1.2.14 void mergeV(MultiMap V, Worklist Wv, Context c, Temp t, LatticeVal a) {
500 cananian 1.1.2.14 raiseV(V, Wv, c, t, a);
501 cananian 1.1.2.4 }
502 cananian 1.1.2.4 /** Merge a with type of field hf in Vf, adding reads of hf to Wf if
503 cananian 1.1.2.4 necessary. */
504 cananian 1.1.2.14 void mergeV(Worklist Wf, HField hf, LatticeVal a) {
505 cananian 1.4.2.1 assert a!=null;
506 cananian 1.1.2.2 LatticeVal old = get( hf );
507 cananian 1.1.2.2 if (corruptor!=null) a=corruptor.corrupt(a); // support incrementalism
508 cananian 1.1.2.4 if (old != null) {
509 cananian 1.1.2.4 a = a.merge(old);
510 cananian 1.1.2.4 if (old.equals(a) && a.equals(old)) return; // no change.
511 cananian 1.1.2.12 }
512 cananian 1.1.2.12 // careful with small types: limit to what they are defined to hold.
513 cananian 1.1.2.12 if (toInternal(hf.getType())!=hf.getType()) {
514 cananian 1.1.2.12 // trust xBitWidth to properly limit
515 cananian 1.1.2.12 xBitWidth bw = new xBitWidth(hf.getType(), 1000, 1000);
516 cananian 1.1.2.12 xBitWidth aa = extractWidth(a);
517 cananian 1.1.2.12 if (aa.plusWidth() > bw.plusWidth() ||
518 cananian 1.1.2.12 aa.minusWidth() > bw.minusWidth()) {
519 cananian 1.1.2.12 // oops: we have to limit the size of a.
520 cananian 1.1.2.12 // xxx: should we ever get a *constant* larger than the
521 cananian 1.1.2.12 // field can hold?
522 cananian 1.4.2.1 assert !(a instanceof xIntConstant);
523 cananian 1.1.2.12 a = new xBitWidth(aa.type(),
524 cananian 1.1.2.12 Math.min(aa.plusWidth(), bw.plusWidth()),
525 cananian 1.1.2.12 Math.min(aa.minusWidth(), bw.minusWidth()));
526 cananian 1.1.2.12 // bail if no change from old value.
527 cananian 1.1.2.12 if (old!=null && old.equals(a) && a.equals(old)) return;
528 cananian 1.1.2.12 }
529 cananian 1.1.2.4 }
530 cananian 1.1.2.2 Vf.put(hf, a);
531 cananian 1.1.2.2 Wf.push(hf);
532 cananian 1.1.2.2 }
533 cananian 1.1.2.2
534 cananian 1.1.2.2 // utility functions.
535 cananian 1.1.2.14 LatticeVal get(Context c, Temp t) {
536 cananian 1.1.2.14 return (LatticeVal) ((MapSet)V.getValues(t)).asMap().get(c);
537 cananian 1.1.2.14 }
538 cananian 1.1.2.2 LatticeVal get(HField hf) {
539 cananian 1.1.2.2 // if value in cache, use it.
540 cananian 1.1.2.2 if (Vf.containsKey(hf)) return (LatticeVal) Vf.get(hf);
541 cananian 1.1.2.2 HClass type = toInternal(hf.getType());
542 cananian 1.1.2.2 // deal with constant fields.
543 cananian 1.1.2.2 if (hf.isConstant()) {
544 cananian 1.1.2.2 Object val = hf.getConstant();
545 cananian 1.1.2.2 if (type == linker.forName("java.lang.String"))
546 cananian 1.1.2.2 return new xStringConstant(type, val);
547 cananian 1.1.2.2 else if (type == HClass.Float || type == HClass.Double )
548 cananian 1.1.2.2 return new xFloatConstant(type, val);
549 cananian 1.1.2.2 else if (type == HClass.Int || type == HClass.Long)
550 cananian 1.1.2.2 return new xIntConstant(type,((Number)val).longValue() );
551 cananian 1.1.2.2 else throw new Error("Unknown constant field type: "+type);
552 cananian 1.1.2.2 }
553 cananian 1.1.2.2 // final fields will be explicitly initialized.
554 cananian 1.1.2.2 if (Modifier.isFinal(hf.getModifiers()))
555 cananian 1.1.2.2 return null; // bottom
556 cananian 1.1.2.17 // definitely initialized fields can be bottom until initialization.
557 cananian 1.8 if (dio.isDefinitelyInitialized(hf)) {
558 cananian 1.8 diFields.add(hf); // remember this for later.
559 cananian 1.1.2.17 return null; // bottom
560 cananian 1.8 }
561 cananian 1.1.2.2 // else assume that field is set to zero upon object creation.
562 cananian 1.1.2.2 if (!type.isPrimitive()) return new xNullConstant();
563 cananian 1.1.2.2 if (type==HClass.Float)
564 cananian 1.1.2.2 return new xFloatConstant(type, new Float(0.0));
565 cananian 1.1.2.2 if (type == HClass.Double)
566 cananian 1.1.2.2 return new xFloatConstant(type, new Double(0.0));
567 cananian 1.1.2.2 if (type == HClass.Int || type==HClass.Long)
568 cananian 1.1.2.2 return new xIntConstant(type, 0 );
569 cananian 1.1.2.2 else throw new Error("Unknown field type: "+type);
570 cananian 1.1.2.2 }
571 cananian 1.1.2.2
572 cananian 1.1.2.1 /*------------------------------------------------------------*/
573 cananian 1.1.2.1 // VISITOR CLASS (the real guts of the routine)
574 cananian 1.1.2.1 class SCCVisitor extends QuadVisitor {
575 cananian 1.1.2.1 // local references to worklists.
576 cananian 1.1.2.2 final Worklist Wv, Wq, Wf;
577 cananian 1.1.2.1 // give us an OperVisitor class to go along with this.
578 cananian 1.1.2.2 final OperVisitor opVisitor = new SCCOpVisitor();
579 cananian 1.1.2.14 // current context.
580 cananian 1.1.2.14 Context context;
581 cananian 1.1.2.1
582 cananian 1.1.2.2 SCCVisitor(Worklist Wv, Worklist Wq, Worklist Wf) {
583 cananian 1.1.2.2 this.Wv = Wv; this.Wq = Wq; this.Wf = Wf;
584 cananian 1.1.2.1 }
585 cananian 1.1.2.1
586 cananian 1.1.2.14 // implicit context!
587 cananian 1.1.2.14 void raiseE(Set Ee, Set Eq, Worklist Wq, Edge e) {
588 cananian 1.1.2.14 raiseE(Ee, Eq, Wq, context, e);
589 cananian 1.1.2.14 }
590 cananian 1.1.2.14 void raiseV(MultiMap V, Worklist Wv, Temp t, LatticeVal a) {
591 cananian 1.1.2.14 raiseV(V, Wv, context, t, a);
592 cananian 1.1.2.14 }
593 cananian 1.1.2.14 void mergeV(MultiMap V, Worklist Wv, Temp t, LatticeVal a) {
594 cananian 1.1.2.14 raiseV(V, Wv, context, t, a);
595 cananian 1.1.2.14 }
596 cananian 1.1.2.14 LatticeVal get(Temp t) {
597 cananian 1.1.2.14 return get(context, t);
598 cananian 1.1.2.14 }
599 cananian 1.1.2.14 // yuck, this is broken, but the inner class declarations shadow
600 cananian 1.1.2.14 // the outer declarations (even though method params are distinct!)
601 cananian 1.1.2.14 void raiseE(Set Ee, Set Eq, Worklist Wq, Context c, Edge e) {
602 cananian 1.1.2.14 BitWidthAnalysis.this.raiseE(Ee, Eq, Wq, c, e);
603 cananian 1.1.2.14 }
604 cananian 1.1.2.14 void raiseV(MultiMap V, Worklist Wv, Context c, Temp t, LatticeVal a) {
605 cananian 1.1.2.14 BitWidthAnalysis.this.raiseV(V, Wv, c, t, a);
606 cananian 1.1.2.14 }
607 cananian 1.1.2.14 void mergeV(MultiMap V, Worklist Wv, Context c, Temp t, LatticeVal a) {
608 cananian 1.1.2.14 BitWidthAnalysis.this.raiseV(V, Wv, c, t, a);
609 cananian 1.1.2.14 }
610 cananian 1.1.2.14 LatticeVal get(Context c, Temp t) {
611 cananian 1.1.2.14 return BitWidthAnalysis.this.get(c, t);
612 cananian 1.1.2.14 }
613 cananian 1.1.2.14 LatticeVal get(HField hf) {
614 cananian 1.1.2.14 return BitWidthAnalysis.this.get(hf);
615 cananian 1.1.2.14 }
616 cananian 1.1.2.14 void mergeV(Worklist Wf, HField hf, LatticeVal a) {
617 cananian 1.1.2.14 BitWidthAnalysis.this.mergeV(Wf, hf, a);
618 cananian 1.1.2.14 }
619 cananian 1.1.2.14
620 cananian 1.1.2.4 void handleSigmas(CJMP q, boolean falseTaken, boolean trueTaken) {
621 cananian 1.1.2.4 // for every sigma source:
622 cananian 1.1.2.4 for (int i=0; i < q.numSigmas(); i++) {
623 cananian 1.1.2.4 LatticeVal v = get( q.src(i) );
624 cananian 1.1.2.4 if (v == null) continue; // skip: insufficient info.
625 cananian 1.1.2.4 // check if this is the CJMP condition.
626 cananian 1.1.2.4 if (useSigmas && q.test() == q.src(i)) {
627 cananian 1.1.2.4 // we know that the conditional is zero on the false leg
628 cananian 1.1.2.4 if (falseTaken)
629 cananian 1.1.2.4 raiseV(V, Wv, q.dst(i,0),
630 cananian 1.1.2.4 new xIntConstant(toInternal(HClass.Boolean),0));
631 cananian 1.1.2.4 // CJMP test is possibly non-boolean, so we don't in fact
632 cananian 1.1.2.4 // know the value of the true side (except that it is
633 cananian 1.1.2.4 // non-zero)
634 cananian 1.1.2.4 if (trueTaken) raiseV(V, Wv, q.dst(i,1), v.rename(q, 1));
635 cananian 1.1.2.4 } else {
636 cananian 1.1.2.4 // fall back.
637 cananian 1.1.2.4 if (falseTaken) raiseV(V, Wv, q.dst(i,0), v.rename(q, 0));
638 cananian 1.1.2.4 if (trueTaken) raiseV(V, Wv, q.dst(i,1), v.rename(q, 1));
639 cananian 1.1.2.4 }
640 cananian 1.1.2.4 }
641 cananian 1.1.2.4 }
642 cananian 1.1.2.4 void handleSigmas(CJMP q, xInstanceofResult io,
643 cananian 1.1.2.4 boolean falseTaken, boolean trueTaken) {
644 cananian 1.1.2.1 // for every sigma source:
645 cananian 1.1.2.1 for (int i=0; i < q.numSigmas(); i++) {
646 cananian 1.1.2.1 // check if this is the CJMP condition.
647 cananian 1.1.2.1 if (q.test() == q.src(i)) { // known value after branch
648 cananian 1.1.2.4 if (falseTaken) raiseV(V, Wv, q.dst(i,0),
649 cananian 1.1.2.4 io.makeKnown(false).rename(q,0));
650 cananian 1.1.2.4 if (trueTaken) raiseV(V, Wv, q.dst(i,1),
651 cananian 1.1.2.4 io.makeKnown(true).rename(q,1));
652 cananian 1.1.2.1 continue; // go on.
653 cananian 1.1.2.1 }
654 cananian 1.1.2.1
655 cananian 1.1.2.1 LatticeVal v = get( q.src(i) );
656 cananian 1.1.2.1 if (v == null) continue; // skip: insufficient info.
657 cananian 1.1.2.1
658 cananian 1.1.2.1 // check to see if this is the temp tested by INSTANCEOF
659 cananian 1.1.2.1 if (q.src(i) == io.tested()) {
660 cananian 1.1.2.1 // no new info on false branch.
661 cananian 1.1.2.4 if (falseTaken)
662 cananian 1.1.2.4 raiseV(V, Wv, q.dst(i,0), v.rename(q, 0));
663 cananian 1.1.2.1 // we know q.dst[i][1] is INSTANCEOF def.hclass
664 cananian 1.1.2.1 // secret inside info: INSTANCEOF src is always non-null.
665 cananian 1.1.2.5 HClass hcI = io.def().hclass();
666 cananian 1.1.2.5 HClass hcV = ((xClass)v).type();
667 cananian 1.1.2.5 // use more specific type
668 cananian 1.1.2.5 if (!hcI.isInterface() && !hcV.isInterface() &&
669 cananian 1.1.2.5 hcI.isSuperclassOf(hcV))
670 cananian 1.1.2.5 hcI = hcV;
671 cananian 1.1.2.5 LatticeVal nv = new xClassNonNull(hcI);
672 cananian 1.1.2.5 // use more specific of original class, instanceof.
673 cananian 1.1.2.5 if (v.isLowerThan(nv)) nv = v;
674 cananian 1.1.2.4 if (trueTaken)
675 cananian 1.1.2.5 raiseV(V, Wv, q.dst(i,1), nv);
676 cananian 1.1.2.1 } else {
677 cananian 1.1.2.1 // fall back.
678 cananian 1.1.2.4 if (falseTaken) raiseV(V, Wv, q.dst(i,0), v.rename(q, 0));
679 cananian 1.1.2.4 if (trueTaken) raiseV(V, Wv, q.dst(i,1), v.rename(q, 1));
680 cananian 1.1.2.1 }
681 cananian 1.1.2.1 }
682 cananian 1.1.2.1 }
683 cananian 1.1.2.4 void handleSigmas(CJMP q, xOperBooleanResult or,
684 cananian 1.1.2.4 boolean falseTaken, boolean trueTaken) {
685 cananian 1.1.2.1 int opc = or.def().opcode();
686 cananian 1.1.2.1 int opa = or.operands().length;
687 cananian 1.1.2.1 LatticeVal left = opa<1?null:get(or.operands()[0]);
688 cananian 1.1.2.1 LatticeVal right= opa<2?null:get(or.operands()[1]);
689 cananian 1.1.2.1
690 cananian 1.1.2.1 // for every sigma source:
691 cananian 1.1.2.1 for (int i=0; i < q.numSigmas(); i++) {
692 cananian 1.1.2.1 // check if this is the CJMP condition.
693 cananian 1.1.2.1 if (q.test() == q.src(i)) {
694 cananian 1.1.2.4 if (falseTaken) raiseV(V, Wv, q.dst(i,0),
695 cananian 1.1.2.4 or.makeKnown(false).rename(q,0));
696 cananian 1.1.2.4 if (trueTaken) raiseV(V, Wv, q.dst(i,1),
697 cananian 1.1.2.4 or.makeKnown(true).rename(q,1));
698 cananian 1.1.2.1 continue; // go on.
699 cananian 1.1.2.1 }
700 cananian 1.1.2.1
701 cananian 1.1.2.1 LatticeVal v = get( q.src(i) );
702 cananian 1.1.2.1 if (v == null) continue; // skip: insufficient info.
703 cananian 1.1.2.1
704 cananian 1.1.2.1 // check to see if it comes from the OPER defining the boolean.
705 cananian 1.1.2.1 boolean handled = false;
706 cananian 1.1.2.4 boolean leftIsSource = false, swapped = false;
707 cananian 1.1.2.1 if (q.src(i) == or.operands()[0]) { // left is source.
708 cananian 1.1.2.4 leftIsSource = true;
709 cananian 1.1.2.4 } else if (q.src(i) == or.operands()[1]) { // right is source.
710 cananian 1.1.2.4 LatticeVal t = left; left = right; right = t;
711 cananian 1.1.2.4 leftIsSource = true; swapped = true;
712 cananian 1.1.2.4 }
713 cananian 1.1.2.4 if (leftIsSource) {
714 cananian 1.1.2.1 if (opc == Qop.ACMPEQ &&
715 cananian 1.1.2.1 left instanceof xClass && // not already xClassNonNull
716 cananian 1.1.2.4 (!(left instanceof xNullConstant)) &&
717 cananian 1.1.2.1 right instanceof xNullConstant) {
718 cananian 1.1.2.4 if (falseTaken)
719 cananian 1.1.2.4 raiseV(V, Wv, q.dst(i,0), // false branch: non-null
720 cananian 1.1.2.4 new xClassNonNull( ((xClass)left).type() ));
721 cananian 1.1.2.4 if (trueTaken)
722 cananian 1.1.2.4 raiseV(V, Wv, q.dst(i,1), // true branch: null
723 cananian 1.1.2.4 new xNullConstant() );
724 cananian 1.1.2.1 handled = true;
725 cananian 1.1.2.1 } else if ((opc == Qop.ICMPEQ || opc == Qop.LCMPEQ ||
726 cananian 1.1.2.1 opc == Qop.FCMPEQ || opc == Qop.DCMPEQ) &&
727 cananian 1.1.2.1 right instanceof xConstant) {
728 cananian 1.1.2.4 if (falseTaken)
729 cananian 1.1.2.4 raiseV(V, Wv, q.dst(i,0), // false branch: no info
730 cananian 1.1.2.4 left.rename(q, 0));
731 cananian 1.1.2.4 if (trueTaken)
732 cananian 1.1.2.4 raiseV(V, Wv, q.dst(i,1), // true branch: constant!
733 cananian 1.1.2.4 right.rename(q, 1));
734 cananian 1.1.2.1 handled = true;
735 cananian 1.1.2.4 } else if ((opc == Qop.ICMPGT || opc == Qop.LCMPGT ) &&
736 cananian 1.1.2.1 right instanceof xBitWidth) {
737 cananian 1.1.2.1 xBitWidth bw = (xBitWidth) right;
738 cananian 1.1.2.4 xBitWidth sr = extractWidth(left);
739 cananian 1.1.2.4 xBitWidth lessThan = new xBitWidth
740 cananian 1.1.2.4 (sr.type(),
741 cananian 1.1.2.4 sr.minusWidth(),
742 cananian 1.1.2.4 Math.min(sr.plusWidth(), bw.plusWidth()) );
743 cananian 1.1.2.4 xBitWidth greaterThan = new xBitWidth
744 cananian 1.1.2.4 (sr.type(),
745 cananian 1.1.2.4 Math.min(sr.minusWidth(),bw.minusWidth()),
746 cananian 1.1.2.4 sr.plusWidth() );
747 cananian 1.1.2.5 // use more specific of original class, xBitWidth.
748 cananian 1.1.2.5 if (left.isLowerThan(lessThan))
749 cananian 1.1.2.5 lessThan = (xBitWidth) left;
750 cananian 1.1.2.5 if (left.isLowerThan(greaterThan))
751 cananian 1.1.2.5 greaterThan = (xBitWidth) left;
752 cananian 1.1.2.1 // false branch:
753 cananian 1.1.2.4 if (falseTaken)
754 cananian 1.1.2.4 raiseV(V, Wv, q.dst(i,0),
755 cananian 1.1.2.4 swapped ? greaterThan : lessThan);
756 cananian 1.1.2.1 // true branch.
757 cananian 1.1.2.4 if (trueTaken)
758 cananian 1.1.2.4 raiseV(V, Wv, q.dst(i,1),
759 cananian 1.1.2.4 swapped ? lessThan : greaterThan);
760 cananian 1.1.2.1 handled = true;
761 cananian 1.1.2.1 }
762 cananian 1.1.2.1 }
763 cananian 1.1.2.1 // fall back.
764 cananian 1.1.2.1 if (!handled) {
765 cananian 1.1.2.4 if (falseTaken) raiseV(V, Wv, q.dst(i,0), v.rename(q, 0));
766 cananian 1.1.2.4 if (trueTaken) raiseV(V, Wv, q.dst(i,1), v.rename(q, 1));
767 cananian 1.1.2.1 }
768 cananian 1.1.2.1 }
769 cananian 1.1.2.1 }
770 cananian 1.1.2.1
771 cananian 1.1.2.1 // visitation.
772 cananian 1.1.2.1 public void visit(Quad q) { /* do nothing. */ }
773 cananian 1.1.2.1 public void visit(AGET q) {
774 cananian 1.1.2.1 LatticeVal v = get( q.objectref() );
775 cananian 1.1.2.4 if (corruptor==null)
776 cananian 1.4.2.1 assert v==null || v instanceof xClassNonNull;
777 cananian 1.1.2.1 if (v instanceof xClass)
778 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
779 cananian 1.1.2.1 new xClass( toInternal( ((xClass)v).type().getComponentType() ) ) );
780 cananian 1.1.2.1 }
781 cananian 1.1.2.1 public void visit(ALENGTH q) {
782 cananian 1.1.2.1 LatticeVal v = get( q.objectref() );
783 cananian 1.1.2.4 if (corruptor==null)
784 cananian 1.4.2.1 assert v==null || v instanceof xClassNonNull;
785 cananian 1.1.2.1 if (v instanceof xClassArray)
786 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
787 cananian 1.1.2.1 new xIntConstant(HClass.Int,
788 cananian 1.1.2.1 ((xClassArray)v).length() ) );
789 cananian 1.1.2.1 else if (v instanceof xClass) // length is non-negative.
790 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xBitWidth(HClass.Int, 0, 32) );
791 cananian 1.1.2.1 }
792 cananian 1.1.2.1 public void visit(ANEW q) { // dst of ANEW is non-null.
793 cananian 1.1.2.1 if (q.dimsLength()==1) {
794 cananian 1.1.2.1 LatticeVal v = get( q.dims(0) );
795 cananian 1.1.2.1 if (v instanceof xIntConstant) {
796 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
797 cananian 1.1.2.1 new xClassArray(q.hclass(),
798 cananian 1.1.2.1 (int) ((xIntConstant)v).value()) );
799 cananian 1.1.2.1 return;
800 cananian 1.1.2.1 } else if (v == null) return; // bottom.
801 cananian 1.1.2.1 }
802 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xClassExact(q.hclass()) );
803 cananian 1.1.2.1 }
804 cananian 1.1.2.4 public void visit(ASET q) {
805 cananian 1.1.2.4 LatticeVal v = get( q.objectref() );
806 cananian 1.1.2.4 if (corruptor==null)
807 cananian 1.4.2.1 assert v==null || v instanceof xClassNonNull;
808 cananian 1.1.2.4 /* do nothing. */
809 cananian 1.1.2.4 }
810 cananian 1.1.2.1 public void visit(CALL q) {
811 cananian 1.1.2.4 if (corruptor==null)
812 cananian 1.4.2.1 assert (q.isVirtual() ?
813 cananian 1.1.2.4 get( q.params(0) )==null ||
814 cananian 1.4.2.1 get( q.params(0) ) instanceof xClassNonNull : true) : q;
815 cananian 1.1.2.3 // don't analyze this quad until all params are known.
816 cananian 1.1.2.3 for (int i=0; i<q.paramsLength(); i++)
817 cananian 1.1.2.3 if (get(q.params(i))==null)
818 cananian 1.1.2.3 return;
819 cananian 1.1.2.3 // find methods callable from this site.
820 cananian 1.1.2.3 HMethod hm = q.method();
821 cananian 1.1.2.3 List callable = new ArrayList(4);
822 cananian 1.1.2.3 if (q.isVirtual()) { // need type info for virtual methods.
823 cananian 1.4.2.1 assert !hm.isStatic();
824 cananian 1.1.2.3 LatticeVal v = get( q.params(0) );
825 cananian 1.1.2.3 HClass ty = ((xClass) v).type();
826 cananian 1.4.2.1 assert !ty.isPrimitive() : v;
827 cananian 1.1.2.3 // when hm.getDeclaringClass() is an interface, the
828 cananian 1.1.2.3 // implementations may not share a common superclass which
829 cananian 1.1.2.3 // implements that interface.
830 cananian 1.1.2.3 if (!ty.isInstanceOf(hm.getDeclaringClass()))
831 cananian 1.1.2.3 ty = hm.getDeclaringClass(); // always safe to fall back.
832 cananian 1.1.2.3 hm = ty.getMethod(hm.getName(), hm.getDescriptor());
833 cananian 1.1.2.3 if (!(v instanceof xClassExact))
834 cananian 1.1.2.3 callable.addAll(ch.overrides(ty,hm,true));
835 cananian 1.1.2.3 }
836 cananian 1.1.2.3 callable.add(hm);
837 cananian 1.1.2.13 // weird special stuff for possible calls to Thread.start():
838 cananian 1.1.2.13 // they cause calls to Thread.run()
839 cananian 1.1.2.13 if (callable.contains(linker.forName("java.lang.Thread")
840 cananian 1.1.2.13 .getMethod("start", "()V"))) {
841 cananian 1.1.2.13 // do a virtual dispatch to Thread.run() as well.
842 cananian 1.1.2.13 LatticeVal v = get( q.params(0) );
843 cananian 1.1.2.13 HClass ty = ((xClass) v).type();
844 cananian 1.4.2.1 assert ty.isInstanceOf
845 cananian 1.4.2.1 (linker.forName("java.lang.Thread")) : v;
846 cananian 1.1.2.13 hm = ty.getMethod("run", "()V");
847 cananian 1.1.2.13 if (!(v instanceof xClassExact))
848 cananian 1.1.2.13 callable.addAll(ch.overrides(ty,hm,true));
849 cananian 1.1.2.13 callable.add(hm);
850 cananian 1.1.2.13 }
851 cananian 1.1.2.3 // for every callable method, raise its Vparam.
852 cananian 1.1.2.3 // flag if any callable methods are native.
853 cananian 1.1.2.6 boolean anyNative = false;
854 cananian 1.1.2.3 Temp[] myparams = q.params();
855 cananian 1.10 for (Object hmmO : callable) {
856 cananian 1.10 HMethod hmm = (HMethod) hmmO;
857 cananian 1.1.2.14 // create new context (using this call site)
858 cananian 1.1.2.14 Context nc = context.addElement(q);
859 cananian 1.1.2.14 // keep callMap updated.
860 cananian 1.1.2.14 callMap.add(Default.pair(nc, hmm), Default.pair(context, q));
861 cananian 1.1.2.14 // okay, raise types of METHOD for this context.
862 cananian 1.1.2.3 if (Modifier.isNative(hmm.getModifiers())) anyNative = true;
863 cananian 1.1.2.3 if (!methodMap.containsKey(hmm)) scan_one(hmm);
864 cananian 1.1.2.3 METHOD method = (METHOD) methodMap.get(hmm);
865 cananian 1.1.2.3 if (method==null) continue; // abstract or native method.
866 cananian 1.1.2.18 int i=0;
867 cananian 1.1.2.18 if (!hmm.isStatic()) {
868 cananian 1.1.2.18 // 'this' parameter gets narrowed by the call.
869 cananian 1.1.2.18 mergeV(V, Wv, nc, method.params(i),
870 cananian 1.1.2.18 narrowThis(hmm.getDeclaringClass(),
871 cananian 1.1.2.18 get(myparams[i])) );
872 cananian 1.1.2.18 i++;
873 cananian 1.1.2.18 }
874 cananian 1.1.2.18 // handle all the non-'this' parameters.
875 cananian 1.1.2.18 for ( ; i<myparams.length; i++)
876 cananian 1.1.2.14 mergeV(V, Wv, nc, method.params(i), get( myparams[i] ));
877 cananian 1.1.2.3 // also mark "method" executable.
878 cananian 1.1.2.14 raiseE(Ee, Eq, Wq, nc, method.prevEdge(0));
879 cananian 1.1.2.3 // analysis of "method" (in particular, the RETURN/THROW
880 cananian 1.1.2.3 // quads) will raiseE on appropriate outgoing edge and
881 cananian 1.1.2.3 // raiseV on retval/retex.
882 cananian 1.1.2.14 // (only interested in returns with given callee context)
883 cananian 1.10 for (Object rO : returnMap.getValues(Default.pair(nc,hmm))
884 cananian 1.10 ) {
885 cananian 1.10 RETURN r = (RETURN) rO;
886 cananian 1.1.2.7 if (r.retval()!=null) {
887 cananian 1.1.2.14 LatticeVal v = get( nc, r.retval() );
888 cananian 1.1.2.7 if (v==null) continue;
889 cananian 1.1.2.7 mergeV(V, Wv, q.retval(), v);
890 cananian 1.1.2.7 }
891 cananian 1.1.2.6 raiseE(Ee, Eq, Wq, q.nextEdge(0) );
892 cananian 1.1.2.6 }
893 cananian 1.10 for (Object tO : throwMap.getValues(Default.pair(nc,hmm))
894 cananian 1.10 ) {
895 cananian 1.10 THROW t = (THROW) tO;
896 cananian 1.1.2.14 LatticeVal v = get( nc, t.throwable() );
897 cananian 1.1.2.6 if (v==null) continue;
898 cananian 1.1.2.6 mergeV(V, Wv, q.retex(), v);
899 cananian 1.1.2.6 raiseE(Ee, Eq, Wq, q.nextEdge(1) );
900 cananian 1.1.2.6 }
901 cananian 1.1.2.3 }
902 cananian 1.1.2.6 if (anyNative) {
903 cananian 1.1.2.3 // if *native* method in callable methods set, then use
904 cananian 1.1.2.3 // conservative retval/retex/edge assumptions.
905 cananian 1.1.2.1 if (q.retval() != null) {
906 cananian 1.1.2.1 // in the bytecode world, everything's an int.
907 cananian 1.1.2.1 HClass ty = q.method().getReturnType();
908 cananian 1.1.2.1 LatticeVal v = new xClass(toInternal(ty));
909 cananian 1.1.2.1 if (ty==HClass.Byte)
910 cananian 1.1.2.1 v = new xBitWidth(toInternal(HClass.Byte), 8, 7);
911 cananian 1.1.2.1 else if (ty==HClass.Short)
912 cananian 1.1.2.1 v = new xBitWidth(toInternal(HClass.Short), 16, 15);
913 cananian 1.1.2.1 else if (ty==HClass.Char)
914 cananian 1.1.2.1 v = new xBitWidth(toInternal(HClass.Char), 0, 16);
915 cananian 1.1.2.1 else if (ty==HClass.Boolean)
916 cananian 1.1.2.1 v = new xBitWidth(toInternal(HClass.Boolean),0, 1);
917 cananian 1.1.2.1 else if (ty.isPrimitive())
918 cananian 1.1.2.1 v = new xClassNonNull(toInternal(ty));
919 cananian 1.1.2.4 mergeV(V, Wv, q.retval(), v);
920 cananian 1.1.2.1 }
921 cananian 1.1.2.4 mergeV(V, Wv, q.retex(),
922 cananian 1.1.2.1 new xClassNonNull( linker.forName("java.lang.Throwable") ));
923 cananian 1.1.2.1 // both outgoing edges are potentially executable.
924 cananian 1.1.2.1 raiseE(Ee, Eq, Wq, q.nextEdge(1) );
925 cananian 1.1.2.1 raiseE(Ee, Eq, Wq, q.nextEdge(0) );
926 cananian 1.1.2.6 }
927 cananian 1.1.2.1 // handle SIGMAs
928 cananian 1.1.2.1 for (int i=0; i < q.numSigmas(); i++) {
929 cananian 1.1.2.1 // no q.src(x) should equal retval or retex...
930 cananian 1.1.2.1 // not that it would particularly break anything if it
931 cananian 1.1.2.1 // did.
932 cananian 1.1.2.1 LatticeVal v2 = get ( q.src(i) );
933 cananian 1.1.2.6 if (v2 == null) continue;
934 cananian 1.1.2.6 if (execMap(q.nextEdge(0)))
935 cananian 1.1.2.1 raiseV(V, Wv, q.dst(i, 0), v2.rename(q, 0));
936 cananian 1.1.2.6 if (execMap(q.nextEdge(1)))
937 cananian 1.1.2.1 raiseV(V, Wv, q.dst(i, 1), v2.rename(q, 1));
938 cananian 1.1.2.1 }
939 cananian 1.1.2.18 }
940 cananian 1.1.2.18 /** private helper method to narrow the type of a 'this' pointer
941 cananian 1.1.2.18 * down to the given class (which defines the class method we're
942 cananian 1.1.2.18 * going to invoke). */
943 cananian 1.1.2.18 private LatticeVal narrowThis(HClass hc, LatticeVal v) {
944 cananian 1.4.2.1 assert v instanceof xClassNonNull : "'this' pointer should always be known non-null.";
945 cananian 1.1.2.18 xClassNonNull vv = (xClassNonNull) v;
946 cananian 1.4.2.1 assert !hc.isInterface(); // hc comes from method decl.
947 cananian 1.1.2.18 // vv can be interface, in which case we *do* want to narrow.
948 cananian 1.1.2.18 // but an interface can never be an instanceof a non-interface.
949 cananian 1.1.2.18 if (vv.type().isInstanceOf(hc)) return vv;
950 cananian 1.4.2.1 assert !(v instanceof xClassExact) : "how can 'this' be exact when it needs narrowing?";
951 cananian 1.1.2.18 return new xClassNonNull(hc);
952 cananian 1.1.2.1 }
953 cananian 1.1.2.1 public void visit(CJMP q) {
954 cananian 1.1.2.1 // is test constant?
955 cananian 1.1.2.1 LatticeVal v = get( q.test() );
956 cananian 1.1.2.1 if (v instanceof xIntConstant) {
957 cananian 1.1.2.1 boolean test = ((xIntConstant)v).value()!=0;
958 cananian 1.1.2.1
959 cananian 1.1.2.1 if (test)
960 cananian 1.1.2.1 raiseE(Ee, Eq, Wq, q.nextEdge(1) ); // true edge.
961 cananian 1.1.2.1 else
962 cananian 1.1.2.1 raiseE(Ee, Eq, Wq, q.nextEdge(0) ); // false edge.
963 cananian 1.1.2.1 // handle sigmas.
964 cananian 1.1.2.4 if (useSigmas && v instanceof xOperBooleanResult)
965 cananian 1.1.2.4 handleSigmas((CJMP) q, (xOperBooleanResult)v,
966 cananian 1.1.2.4 !test, test);
967 cananian 1.1.2.4 else if (useSigmas && v instanceof xInstanceofResult)
968 cananian 1.1.2.4 handleSigmas((CJMP) q, (xInstanceofResult) v,
969 cananian 1.1.2.4 !test, test);
970 cananian 1.1.2.4 else // fallback.
971 cananian 1.1.2.4 handleSigmas((CJMP) q, !test, test);
972 cananian 1.1.2.1 return; // done.
973 cananian 1.1.2.1 } else if (v instanceof xClass) { // ie, not bottom.
974 cananian 1.1.2.1 // both edges are potentially executable.
975 cananian 1.1.2.1 raiseE(Ee, Eq, Wq, q.nextEdge(1) );
976 cananian 1.1.2.1 raiseE(Ee, Eq, Wq, q.nextEdge(0) );
977 cananian 1.1.2.1
978 cananian 1.1.2.1 // look at definition of boolean condition.
979 cananian 1.1.2.1 if (useSigmas && v instanceof xOperBooleanResult)
980 cananian 1.1.2.4 handleSigmas((CJMP) q, (xOperBooleanResult)v, true, true);
981 cananian 1.1.2.1 else if (useSigmas && v instanceof xInstanceofResult)
982 cananian 1.1.2.4 handleSigmas((CJMP) q, (xInstanceofResult) v, true, true);
983 cananian 1.1.2.1 else // fallback.
984 cananian 1.1.2.4 handleSigmas((CJMP) q, true, true);
985 cananian 1.1.2.1 }
986 cananian 1.1.2.1 }
987 cananian 1.1.2.1 public void visit(COMPONENTOF q) {
988 cananian 1.1.2.1 // we're guaranteed that q.arrayref is non-null here.
989 cananian 1.1.2.1 LatticeVal vA = get( q.arrayref() );
990 cananian 1.1.2.1 LatticeVal vO = get( q.objectref() );
991 cananian 1.1.2.1 if (vA instanceof xClass && vO instanceof xClass) {
992 cananian 1.1.2.1 HClass hcA = ((xClass) vA).type().getComponentType() ;
993 cananian 1.1.2.1 HClass hcO = ((xClass) vO).type();
994 cananian 1.1.2.1 if (hcA==null) { // can't prove type is array; usually this
995 cananian 1.1.2.1 // means we've turned useSigmas off.
996 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xBitWidth(toInternal(HClass.Boolean),0,1));
997 cananian 1.1.2.1 return;
998 cananian 1.1.2.1 }
999 cananian 1.1.2.1 hcA = toInternal(hcA); // normalize external types.
1000 cananian 1.1.2.1 // special case when q.objectref is null
1001 cananian 1.1.2.1 if (hcO == HClass.Void) // always true.
1002 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xIntConstant(toInternal(HClass.Boolean),1));
1003 cananian 1.1.2.5 else if (vA instanceof xClassExact &&
1004 cananian 1.1.2.5 hcO.isInstanceOf(hcA)) // always true
1005 cananian 1.1.2.5 raiseV(V, Wv, q.dst(), new xIntConstant(toInternal(HClass.Boolean),1));
1006 cananian 1.1.2.5 else if (vO instanceof xClassExact &&
1007 cananian 1.1.2.5 !hcO.isInstanceOf(hcA)) // always false
1008 cananian 1.1.2.5 raiseV(V, Wv, q.dst(), new xIntConstant(toInternal(HClass.Boolean),0));
1009 cananian 1.7 else if (hcA.isInterface() ||
1010 cananian 1.7 hcO.isInterface() ||
1011 cananian 1.7 hcO.isInstanceOf(hcA) ||
1012 cananian 1.1.2.1 hcA.isInstanceOf(hcO)) // unknowable.
1013 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xBitWidth(toInternal(HClass.Boolean),0,1));
1014 cananian 1.1.2.1 else // always false.
1015 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xIntConstant(toInternal(HClass.Boolean),0));
1016 cananian 1.1.2.1 }
1017 cananian 1.1.2.1 }
1018 cananian 1.1.2.1 public void visit(CONST q) {
1019 cananian 1.1.2.1 if (q.type() == HClass.Void) // null constant
1020 cananian 1.1.2.1 raiseV(V,Wv, q.dst(), new xNullConstant() );
1021 cananian 1.1.2.1 else if (q.type()==linker.forName("java.lang.String"))// string constant
1022 cananian 1.1.2.1 raiseV(V,Wv, q.dst(), new xStringConstant(q.type(),q.value()));
1023 cananian 1.1.2.1 else if (q.type()==HClass.Float || q.type()==HClass.Double) // f-p
1024 cananian 1.1.2.1 raiseV(V,Wv, q.dst(), new xFloatConstant(q.type(),q.value()) );
1025 cananian 1.1.2.1 else if (q.type()==HClass.Int || q.type() == HClass.Long)
1026 cananian 1.1.2.1 raiseV(V,Wv, q.dst(),
1027 cananian 1.1.2.1 new xIntConstant(q.type(),
1028 cananian 1.1.2.1 ((Number)q.value()).longValue()));
1029 cananian 1.1.2.1 else if (q.type()==linker.forName("java.lang.Class") ||
1030 cananian 1.1.2.1 q.type()==linker.forName("java.lang.reflect.Field") ||
1031 cananian 1.1.2.1 q.type()==linker.forName("java.lang.reflect.Method"))
1032 cananian 1.1.2.1 raiseV(V,Wv, q.dst(), new xClassNonNull( q.type() ) );
1033 cananian 1.1.2.1 else throw new Error("Unknown CONST type: "+q.type());
1034 cananian 1.1.2.1 }
1035 cananian 1.1.2.1 public void visit(FOOTER q) { /* do nothing. */ }
1036 cananian 1.1.2.1 public void visit(GET q) {
1037 cananian 1.1.2.4 if (corruptor==null)
1038 cananian 1.4.2.1 assert (q.objectref()!=null ?
1039 cananian 1.1.2.4 get(q.objectref())==null ||
1040 cananian 1.4.2.1 get(q.objectref()) instanceof xClassNonNull : true) : q;
1041 cananian 1.1.2.7 // add to list of reading quads.
1042 cananian 1.1.2.14 fieldMap.add(q.field(), Default.pair(context, q));
1043 cananian 1.1.2.2 // variable gets current lattice val of field.
1044 cananian 1.1.2.3 LatticeVal v = get( q.field() );
1045 cananian 1.1.2.3 if (v==null) return; // wait for field initialization.
1046 cananian 1.1.2.3 raiseV(V, Wv, q.dst(), v);
1047 cananian 1.1.2.3 if (DEBUG) System.out.println("READ OF "+q.field()+" GETS "+get( q.field() ));
1048 cananian 1.1.2.1 }
1049 cananian 1.1.2.1 public void visit(HEADER q) {
1050 cananian 1.4.2.1 assert false; /* we should "skip to the METHOD" */
1051 cananian 1.1.2.1 }
1052 cananian 1.1.2.1 public void visit(INSTANCEOF q) {
1053 cananian 1.1.2.1 // no guarantee that src is not null.
1054 cananian 1.1.2.1 LatticeVal v = get( q.src() );
1055 cananian 1.1.2.1 if (v instanceof xNullConstant) // always false.
1056 cananian 1.1.2.4 raiseV(V, Wv, q.dst(), new xInstanceofResultKnown(q,false));
1057 cananian 1.7 else if (v instanceof xClassExact) { // always known.
1058 cananian 1.7 HClass hcO = ((xClassNonNull)v).type();
1059 cananian 1.7 assert !hcO.isInterface();//but can be an array type.
1060 cananian 1.7 boolean result = hcO.isInstanceOf(q.hclass());
1061 cananian 1.7 raiseV(V,Wv, q.dst(), new xInstanceofResultKnown(q,result));
1062 cananian 1.7 }
1063 cananian 1.1.2.1 else if (v instanceof xClassNonNull) { // analyzable
1064 cananian 1.1.2.1 HClass hcO = ((xClassNonNull)v).type();
1065 cananian 1.1.2.1 if (hcO.isInstanceOf(q.hclass())) // always true
1066 cananian 1.1.2.4 raiseV(V,Wv, q.dst(), new xInstanceofResultKnown(q,true));
1067 cananian 1.7 else if (q.hclass().isInterface() || hcO.isInterface() ||
1068 cananian 1.7 q.hclass().isInstanceOf(hcO)) // unknowable.
1069 cananian 1.1.2.4 raiseV(V,Wv, q.dst(), new xInstanceofResultUnknown(q));
1070 cananian 1.1.2.1 else // always false.
1071 cananian 1.1.2.4 raiseV(V,Wv, q.dst(), new xInstanceofResultKnown(q,false));
1072 cananian 1.1.2.1 }
1073 cananian 1.1.2.1 else if (v instanceof xClass) { // could be null.
1074 cananian 1.1.2.1 HClass hcO = ((xClass)v).type();
1075 cananian 1.7 if (q.hclass().isInterface() || hcO.isInterface() ||
1076 cananian 1.7 q.hclass().isInstanceOf(hcO) ||
1077 cananian 1.1.2.1 hcO.isInstanceOf(q.hclass()) ) // unknowable.
1078 cananian 1.1.2.4 raiseV(V,Wv, q.dst(), new xInstanceofResultUnknown(q));
1079 cananian 1.1.2.1 else // always false (even if src==null)
1080 cananian 1.1.2.4 raiseV(V,Wv, q.dst(), new xInstanceofResultKnown(q,false));
1081 cananian 1.1.2.1 }
1082 cananian 1.1.2.1 }
1083 cananian 1.1.2.1 public void visit(METHOD q) {
1084 cananian 1.1.2.3 /* do very little */
1085 cananian 1.4.2.1 assert methodMap.get(q.getFactory().getMethod())==q;
1086 cananian 1.1.2.3 if (DEBUG) System.out.println("METHOD: "+q.getFactory().getMethod());
1087 cananian 1.1.2.1 }
1088 cananian 1.1.2.4 public void visit(MONITORENTER q) {
1089 cananian 1.1.2.4 LatticeVal v = get( q.lock() );
1090 cananian 1.4.2.1 assert v==null || v instanceof xClassNonNull;
1091 cananian 1.1.2.4 /* do nothing. */
1092 cananian 1.1.2.4 }
1093 cananian 1.1.2.4 public void visit(MONITOREXIT q) {
1094 cananian 1.1.2.4 LatticeVal v = get( q.lock() );
1095 cananian 1.4.2.1 assert v==null || v instanceof xClassNonNull;
1096 cananian 1.1.2.4 /* do nothing. */
1097 cananian 1.1.2.4 }
1098 cananian 1.1.2.1 public void visit(MOVE q) {
1099 cananian 1.1.2.1 LatticeVal v = get ( q.src() );
1100 cananian 1.1.2.1 if (v != null)
1101 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), v);
1102 cananian 1.1.2.1 }
1103 cananian 1.1.2.1 public void visit(NEW q) {
1104 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xClassExact( q.hclass() ) );
1105 cananian 1.1.2.1 }
1106 cananian 1.1.2.1 public void visit(NOP q) { /* do nothing. */ }
1107 cananian 1.1.2.1 public void visit(OPER q) {
1108 cananian 1.1.2.1 int opc = q.opcode();
1109 cananian 1.1.2.1 boolean allConst = true;
1110 cananian 1.1.2.1 boolean allWidth = true;
1111 cananian 1.1.2.1
1112 cananian 1.1.2.1 Object[] op = new Object[q.operandsLength()];
1113 cananian 1.1.2.1 for (int i=0; i < q.operandsLength(); i++) {
1114 cananian 1.1.2.1 LatticeVal v = get( q.operands(i) );
1115 cananian 1.1.2.1 if (v==null) return; // can't eval yet.
1116 cananian 1.1.2.1 if (v instanceof xConstant)
1117 cananian 1.1.2.1 op[i] = ((xConstant)v).constValue();
1118 cananian 1.1.2.1 else if (v instanceof xBitWidth)
1119 cananian 1.1.2.1 allConst = false;
1120 cananian 1.1.2.1 else
1121 cananian 1.1.2.1 allConst = allWidth = false;
1122 cananian 1.1.2.1 }
1123 cananian 1.1.2.1 if (allConst) {
1124 cananian 1.1.2.1 // RULE 3:
1125 cananian 1.1.2.1 HClass ty = q.evalType();
1126 cananian 1.1.2.1 Object o = q.evalValue(op);
1127 cananian 1.1.2.1 if (ty == HClass.Boolean)
1128 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
1129 cananian 1.1.2.4 new xOperBooleanResultKnown
1130 cananian 1.1.2.4 (q,((Boolean)o).booleanValue()));
1131 cananian 1.1.2.1 else if (ty == HClass.Int || ty == HClass.Long)
1132 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
1133 cananian 1.1.2.1 new xIntConstant(ty, ((Number)o).longValue() ) );
1134 cananian 1.1.2.1 else if (ty == HClass.Float || ty == HClass.Double)
1135 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xFloatConstant(ty, o) );
1136 cananian 1.1.2.1 else throw new Error("Unknown OPER result type: "+ty);
1137 cananian 1.1.2.1 } else if ((allWidth) ||
1138 cananian 1.1.2.1 opc == Qop.I2B || opc == Qop.I2C || opc == Qop.I2L ||
1139 cananian 1.1.2.1 opc == Qop.I2S || opc == Qop.L2I) {
1140 cananian 1.1.2.1 // do something intelligent with the bitwidths.
1141 cananian 1.1.2.1 q.accept(opVisitor);
1142 cananian 1.1.2.1 } else { // not all constant, not all known widths...
1143 cananian 1.1.2.1 // special-case ACMPEQ x, null
1144 cananian 1.1.2.1 if (opc == Qop.ACMPEQ &&
1145 cananian 1.1.2.1 ((get( q.operands(0) ) instanceof xNullConstant &&
1146 cananian 1.1.2.1 get( q.operands(1) ) instanceof xClassNonNull) ||
1147 cananian 1.1.2.1 (get( q.operands(0) ) instanceof xClassNonNull &&
1148 cananian 1.1.2.1 get( q.operands(1) ) instanceof xNullConstant) ) )
1149 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), // always false.
1150 cananian 1.1.2.4 new xOperBooleanResultKnown(q, false));
1151 cananian 1.1.2.1 // special case boolean operations.
1152 cananian 1.1.2.1 else if (opc == Qop.ACMPEQ ||
1153 cananian 1.1.2.1 opc == Qop.DCMPEQ || opc == Qop.DCMPGE ||
1154 cananian 1.1.2.1 opc == Qop.DCMPGT ||
1155 cananian 1.1.2.1 opc == Qop.FCMPEQ || opc == Qop.FCMPGE ||
1156 cananian 1.1.2.1 opc == Qop.FCMPGT ||
1157 cananian 1.1.2.1 opc == Qop.ICMPEQ || opc == Qop.ICMPGT ||
1158 cananian 1.1.2.1 opc == Qop.LCMPEQ || opc == Qop.LCMPGT)
1159 cananian 1.1.2.4 raiseV(V, Wv, q.dst(), new xOperBooleanResultUnknown(q));
1160 cananian 1.1.2.1 else {
1161 cananian 1.1.2.1 // RULE 4:
1162 cananian 1.1.2.1 HClass ty = q.evalType();
1163 cananian 1.1.2.1 if (ty.isPrimitive())
1164 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xClassNonNull( toInternal(ty) ) );
1165 cananian 1.1.2.1 else
1166 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xClass( ty ) );
1167 cananian 1.1.2.1 }
1168 cananian 1.1.2.1 }
1169 cananian 1.1.2.1 }
1170 cananian 1.1.2.1 public void visit(PHI q) {
1171 cananian 1.1.2.1 for (int i=0; i<q.numPhis(); i++) { // for each phi-function.
1172 cananian 1.1.2.4 LatticeVal merged = null;
1173 cananian 1.1.2.1 for (int j=0; j < q.arity(); j++) {
1174 cananian 1.1.2.14 if (!Ee.contains( Default.entry(q.prevEdge(j), context) ))
1175 cananian 1.1.2.1 continue; // skip non-executable edges.
1176 cananian 1.1.2.1 LatticeVal v = get ( q.src(i,j) );
1177 cananian 1.1.2.1 if (v == null)
1178 cananian 1.1.2.1 continue; // skip this arg function.
1179 cananian 1.1.2.4 v = v.rename(q, j);
1180 cananian 1.1.2.4 if (merged == null)
1181 cananian 1.1.2.4 merged = v; // first valid value
1182 cananian 1.1.2.4 else merged = merged.merge(v);
1183 cananian 1.1.2.1 }
1184 cananian 1.1.2.1 // assess results.
1185 cananian 1.1.2.4 if (merged == null)
1186 cananian 1.1.2.1 continue; // nothing to go on.
1187 cananian 1.1.2.4 else raiseV(V, Wv, q.dst(i), merged);
1188 cananian 1.1.2.1 } // for each phi function.
1189 cananian 1.1.2.1 }
1190 cananian 1.1.2.3 public void visit(RETURN q) {
1191 cananian 1.1.2.14 returnMap.add
1192 cananian 1.1.2.14 ( Default.pair(context, q.getFactory().getMethod()), q );
1193 cananian 1.1.2.7 if (q.retval() != null && get( q.retval() )==null)
1194 cananian 1.1.2.7 return; // wait for definition!
1195 cananian 1.1.2.14 // for all CALLs which may invoke this method in this context...
1196 cananian 1.10 for (Object pairO : callMap.getValues
1197 cananian 1.1.2.14 (Default.pair(context, q.getFactory().getMethod()))
1198 cananian 1.10 ) {
1199 cananian 1.10 List pair = (List) pairO;
1200 cananian 1.1.2.14 Context cc = (Context) pair.get(0); // caller's context
1201 cananian 1.1.2.14 CALL call = (CALL) pair.get(1);
1202 cananian 1.1.2.4 // mergeV on retval.
1203 cananian 1.1.2.3 if (q.retval()!=null)
1204 cananian 1.1.2.14 mergeV(V, Wv, cc, call.retval(), get( q.retval() ));
1205 cananian 1.1.2.3 // raiseE on appropriate outgoing edge.
1206 cananian 1.1.2.14 raiseE(Ee, Eq, Wq, cc, call.nextEdge(0));
1207 cananian 1.1.2.3 // (don't forget sigmas)
1208 cananian 1.1.2.3 for (int i=0; i < call.numSigmas(); i++) {
1209 cananian 1.1.2.14 LatticeVal v2 = get ( cc, call.src(i) );
1210 cananian 1.1.2.3 if (v2 != null)
1211 cananian 1.1.2.14 raiseV(V, Wv, cc, call.dst(i, 0), v2.rename(call, 0));
1212 cananian 1.1.2.3 }
1213 cananian 1.1.2.3 }
1214 cananian 1.1.2.3 }
1215 cananian 1.1.2.2 public void visit(SET q) {
1216 cananian 1.1.2.4 if (corruptor==null)
1217 cananian 1.4.2.1 assert (q.objectref()!=null ?
1218 cananian 1.1.2.4 get(q.objectref())==null ||
1219 cananian 1.4.2.1 get(q.objectref()) instanceof xClassNonNull : true) : q;
1220 cananian 1.1.2.2 /* widen type of field */
1221 cananian 1.1.2.2 LatticeVal v = get( q.src() );
1222 cananian 1.1.2.2 if (v != null)
1223 cananian 1.1.2.14 mergeV(Wf, q.field(), v);
1224 cananian 1.1.2.3 if (DEBUG) System.out.println("WRITE TO "+q.field()+" OF "+get( q.field() ));
1225 cananian 1.1.2.2 }
1226 cananian 1.1.2.1 public void visit(SWITCH q) {
1227 cananian 1.1.2.1 LatticeVal v = get( q.index() );
1228 cananian 1.1.2.1 if (v instanceof xIntConstant) {
1229 cananian 1.1.2.1 int index = (int) ((xIntConstant)v).value();
1230 cananian 1.1.2.1 int i;
1231 cananian 1.1.2.1 for (i=0; i<q.keysLength(); i++)
1232 cananian 1.1.2.1 if (q.keys(i) == index)
1233 cananian 1.1.2.1 break;
1234 cananian 1.1.2.1 // now i has the target index, even for the default case.
1235 cananian 1.1.2.1 raiseE(Ee, Eq, Wq, q.nextEdge(i) ); // executable edge.
1236 cananian 1.1.2.1 // handle sigmas.
1237 cananian 1.1.2.1 for (int j=0; j < q.numSigmas(); j++) {
1238 cananian 1.1.2.1 LatticeVal v2 = get( q.src(j) );
1239 cananian 1.1.2.1 if (v2 != null)
1240 cananian 1.1.2.1 raiseV(V, Wv, q.dst(j,i), v2.rename(q,i));
1241 cananian 1.1.2.1 }
1242 cananian 1.1.2.1 }
1243 cananian 1.1.2.1 else if (v != null) {
1244 cananian 1.1.2.5 xBitWidth bw = extractWidth(v);
1245 cananian 1.1.2.5 // mark some edges executable & propagate to all sigmas.
1246 cananian 1.1.2.11 int executable=0;
1247 cananian 1.1.2.5 for (int j=0; j < q.nextEdge().length; j++) {
1248 cananian 1.1.2.11 if (j<q.keysLength()) { // non-default edge.
1249 cananian 1.1.2.5 // learn stuff about cases from bitwidth of v.
1250 cananian 1.1.2.5 int k = q.keys(j);
1251 cananian 1.1.2.5 if (k>0 && Util.fls(k) > bw.plusWidth())
1252 cananian 1.1.2.5 continue; // key too large to be selected.
1253 cananian 1.1.2.5 if (k<0 && Util.fls(-k) > bw.minusWidth())
1254 cananian 1.1.2.5 continue; // key too small to be selected.
1255 cananian 1.1.2.11 executable++;
1256 cananian 1.1.2.11 } else {
1257 cananian 1.1.2.11 // pigeon-hole principle: default edge is executable
1258 cananian 1.1.2.11 // iff number of executable edges (so far) is less
1259 cananian 1.1.2.11 // than possible number of cases constrained by
1260 cananian 1.1.2.11 // plusWidth and minusWidth.
1261 cananian 1.1.2.11 // --- bail if plusWidth/minusWidth too large; we
1262 cananian 1.1.2.11 // know (we hope!) that switch can't have this
1263 cananian 1.1.2.11 // many edges.
1264 cananian 1.1.2.11 if (bw.plusWidth<30 && bw.minusWidth<30) {
1265 cananian 1.1.2.11 // number of cases is (2^pw + 2^mw)-1
1266 cananian 1.1.2.11 // (don't count zero twice!)
1267 cananian 1.1.2.11 long cases = -1 +
1268 cananian 1.1.2.11 (1L<<bw.plusWidth()) + (1L<<bw.minusWidth());
1269 cananian 1.4.2.1 assert executable<=cases;
1270 cananian 1.1.2.11 if (executable==cases)
1271 cananian 1.1.2.11 continue; // default not executable.
1272 cananian 1.1.2.11 }
1273 cananian 1.1.2.5 }
1274 cananian 1.1.2.5 raiseE(Ee, Eq, Wq, q.nextEdge(j) );
1275 cananian 1.1.2.5 for (int i=0; i < q.numSigmas(); i++) {
1276 cananian 1.1.2.5 LatticeVal v2 = get( q.src(i) );
1277 cananian 1.1.2.5 if (v2 != null)
1278 cananian 1.1.2.1 raiseV(V, Wv, q.dst(i,j), v2.rename(q,j));
1279 cananian 1.1.2.5 }
1280 cananian 1.1.2.1 }
1281 cananian 1.1.2.1 }
1282 cananian 1.1.2.1 }
1283 cananian 1.1.2.3 public void visit(THROW q) {
1284 cananian 1.1.2.4 if (corruptor==null)
1285 cananian 1.4.2.1 assert get(q.throwable())==null ||
1286 cananian 1.4.2.1 get(q.throwable()) instanceof xClassNonNull;
1287 cananian 1.1.2.14 throwMap.add
1288 cananian 1.1.2.14 ( Default.pair(context, q.getFactory().getMethod()), q );
1289 cananian 1.1.2.3 if (get( q.throwable() )==null) return; // wait for definition!
1290 cananian 1.1.2.14 // for all CALLs which may invoke this method in this context...
1291 cananian 1.10 for (Object pairO : callMap.getValues
1292 cananian 1.1.2.14 (Default.pair(context, q.getFactory().getMethod()))
1293 cananian 1.10 ) {
1294 cananian 1.10 List pair = (List) pairO;
1295 cananian 1.1.2.14 Context cc = (Context) pair.get(0); //caller's context
1296 cananian 1.1.2.14 CALL call = (CALL) pair.get(1);
1297 cananian 1.1.2.4 // mergeV on retex.
1298 cananian 1.1.2.14 mergeV(V, Wv, cc, call.retex(), get( q.throwable() ));
1299 cananian 1.1.2.3 // raiseE on appropriate outgoing edge.
1300 cananian 1.1.2.14 raiseE(Ee, Eq, Wq, cc, call.nextEdge(1));
1301 cananian 1.1.2.3 // (don't forget sigmas)
1302 cananian 1.1.2.3 for (int i=0; i < call.numSigmas(); i++) {
1303 cananian 1.1.2.14 LatticeVal v2 = get ( cc, call.src(i) );
1304 cananian 1.1.2.3 if (v2 != null)
1305 cananian 1.1.2.14 raiseV(V, Wv, cc, call.dst(i, 1), v2.rename(call, 1));
1306 cananian 1.1.2.3 }
1307 cananian 1.1.2.3 }
1308 cananian 1.1.2.3 }
1309 cananian 1.1.2.1 public void visit(TYPESWITCH q) {
1310 cananian 1.1.2.1 LatticeVal v = get( q.index() );
1311 cananian 1.1.2.1 if (v instanceof xClass) {
1312 cananian 1.1.2.1 HClass type = ((xClass)v).type();
1313 cananian 1.1.2.1 boolean catchAll = false;
1314 cananian 1.1.2.1 for (int i=0; i<q.keysLength(); i++) {
1315 cananian 1.1.2.1 if (type.isInstanceOf(q.keys(i))) {// catches all remaining
1316 cananian 1.1.2.1 raiseE(Ee, Eq, Wq, q.nextEdge(i) );
1317 cananian 1.1.2.1 catchAll = true;
1318 cananian 1.1.2.1 break;
1319 cananian 1.1.2.1 }
1320 cananian 1.7 if (q.keys(i).isInterface() || type.isInterface() ||
1321 cananian 1.7 q.keys(i).isInstanceOf(type)) // executable
1322 cananian 1.7 raiseE(Ee, Eq, Wq, q.nextEdge(i) );
1323 cananian 1.1.2.1 }
1324 cananian 1.1.2.1 if ((!q.hasDefault()) ||
1325 cananian 1.1.2.1 (catchAll && v instanceof xClassNonNull))
1326 cananian 1.1.2.1 /* default edge never taken */;
1327 cananian 1.1.2.1 else // make the default case executable.
1328 cananian 1.1.2.1 raiseE(Ee, Eq, Wq, q.nextEdge(q.keysLength()));
1329 cananian 1.1.2.1
1330 cananian 1.1.2.1 // handle sigmas.
1331 cananian 1.1.2.1 for (int i=0; i < q.arity(); i++) {
1332 cananian 1.1.2.14 if (!Ee.contains( Default.entry(q.nextEdge(i),context) ))
1333 cananian 1.1.2.14 continue;//only raise exec
1334 cananian 1.1.2.1 for (int j=0; j < q.numSigmas(); j++) {
1335 cananian 1.1.2.1 if (q.src(j)==q.index() && i<q.keysLength())
1336 cananian 1.1.2.1 raiseV(V, Wv, q.dst(j,i),
1337 cananian 1.1.2.1 new xClassNonNull(q.keys(i)));
1338 cananian 1.1.2.1 else {
1339 cananian 1.1.2.1 LatticeVal v2 = get( q.src(j) );
1340 cananian 1.1.2.1 if (v2 != null)
1341 cananian 1.1.2.1 raiseV(V, Wv, q.dst(j,i), v2.rename(q,i));
1342 cananian 1.1.2.1 }
1343 cananian 1.1.2.1 }
1344 cananian 1.1.2.1 }
1345 cananian 1.1.2.1 }
1346 cananian 1.1.2.1 else if (v != null) {
1347 cananian 1.1.2.1 // mark all edges executable & propagate to all sigmas.
1348 cananian 1.1.2.1 for (int i=0; i < q.nextLength(); i++)
1349 cananian 1.1.2.1 raiseE(Ee, Eq, Wq, q.nextEdge(i) );
1350 cananian 1.1.2.1 for (int i=0; i < q.numSigmas(); i++) {
1351 cananian 1.1.2.1 LatticeVal v2 = get( q.src(i) );
1352 cananian 1.1.2.1 if (v2 != null)
1353 cananian 1.1.2.1 for (int j=0; j < q.arity(); j++)
1354 cananian 1.1.2.1 raiseV(V, Wv, q.dst(i,j), v2.rename(q,j));
1355 cananian 1.1.2.1 }
1356 cananian 1.1.2.1 }
1357 cananian 1.1.2.1 }
1358 cananian 1.1.2.1
1359 cananian 1.1.2.1 /*------------------------------------------------------------*/
1360 cananian 1.1.2.1 // VISITOR CLASS FOR OPER (ugh. lots of cases)
1361 cananian 1.1.2.1 class SCCOpVisitor extends OperVisitor {
1362 cananian 1.1.2.1
1363 cananian 1.1.2.1 public void visit_default(OPER q) {
1364 cananian 1.1.2.1 HClass ty = q.evalType();
1365 cananian 1.1.2.1 if (ty.isPrimitive())
1366 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xClassNonNull( toInternal(ty) ) );
1367 cananian 1.1.2.1 else
1368 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xClass( ty ) );
1369 cananian 1.1.2.1 }
1370 cananian 1.1.2.1 // comparisons
1371 cananian 1.1.2.1 void visit_cmpeq(OPER q) {
1372 cananian 1.1.2.1 xBitWidth left = extractWidth( get( q.operands(0) ) );
1373 cananian 1.1.2.1 xBitWidth right= extractWidth( get( q.operands(1) ) );
1374 cananian 1.1.2.1 // comparisons against a constant.
1375 cananian 1.1.2.1 if ((left instanceof xIntConstant &&// left a constant and
1376 cananian 1.1.2.1 ((left.minusWidth()==0 && // right smaller than left.
1377 cananian 1.1.2.1 right.plusWidth() < left.plusWidth()) ||
1378 cananian 1.1.2.1 (left.plusWidth()==0 &&
1379 cananian 1.1.2.1 right.minusWidth() < left.minusWidth()))) || // or...
1380 cananian 1.1.2.1 (right instanceof xIntConstant &&// right a constant and
1381 cananian 1.1.2.1 ((right.minusWidth()==0 && // left smaller than right.
1382 cananian 1.1.2.1 left.plusWidth() < right.plusWidth()) ||
1383 cananian 1.1.2.1 (right.plusWidth()==0 &&
1384 cananian 1.1.2.1 left.minusWidth() < right.minusWidth()))) )
1385 cananian 1.1.2.1 // okay, comparison can never be true.
1386 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
1387 cananian 1.1.2.4 new xOperBooleanResultKnown(q,false));
1388 cananian 1.1.2.1 else // okay, nothing known.
1389 cananian 1.1.2.4 raiseV(V, Wv, q.dst(), new xOperBooleanResultUnknown(q));
1390 cananian 1.1.2.1 }
1391 cananian 1.1.2.1 public void visit_icmpeq(OPER q) { visit_cmpeq(q); }
1392 cananian 1.1.2.1 public void visit_lcmpeq(OPER q) { visit_cmpeq(q); }
1393 cananian 1.1.2.1 void visit_cmpgt(OPER q) {
1394 cananian 1.1.2.1 xBitWidth left = extractWidth( get( q.operands(0) ) );
1395 cananian 1.1.2.1 xBitWidth right= extractWidth( get( q.operands(1) ) );
1396 cananian 1.1.2.1 // comparisons against a non-zero constant.
1397 cananian 1.1.2.1 if ((left instanceof xIntConstant &&
1398 cananian 1.1.2.1 ((xIntConstant)left).value()!=0 &&
1399 cananian 1.1.2.1 left.plusWidth() > right.plusWidth()) ||
1400 cananian 1.1.2.1 (right instanceof xIntConstant &&
1401 cananian 1.1.2.1 ((xIntConstant)right).value()!=0 &&
1402 cananian 1.1.2.1 right.minusWidth() > left.minusWidth()))
1403 cananian 1.1.2.1 // comparison is always true
1404 cananian 1.1.2.4 raiseV(V,Wv, q.dst(), new xOperBooleanResultKnown(q,true));
1405 cananian 1.1.2.1 else if ((left instanceof xIntConstant &&
1406 cananian 1.1.2.1 ((xIntConstant)left).value()!=0 &&
1407 cananian 1.1.2.1 left.minusWidth() > right.minusWidth()) ||
1408 cananian 1.1.2.1 (right instanceof xIntConstant &&
1409 cananian 1.1.2.1 ((xIntConstant)right).value()!=0 &&
1410 cananian 1.1.2.1 right.plusWidth() > left.plusWidth()))
1411 cananian 1.1.2.1 // comparison is always false
1412 cananian 1.1.2.4 raiseV(V,Wv, q.dst(),new xOperBooleanResultKnown(q,false));
1413 cananian 1.1.2.1 // comparisons against zero.
1414 cananian 1.1.2.1 else if ((left instanceof xIntConstant &&
1415 cananian 1.1.2.1 ((xIntConstant)left).value()==0 &&
1416 cananian 1.1.2.1 right.minusWidth()==0) ||
1417 cananian 1.1.2.1 (right instanceof xIntConstant &&
1418 cananian 1.1.2.1 ((xIntConstant)right).value()==0 &&
1419 cananian 1.1.2.1 left.plusWidth()==0))
1420 cananian 1.1.2.1 // comparison is always false. 0 > 0+ or 0- > 0
1421 cananian 1.1.2.4 raiseV(V,Wv, q.dst(),new xOperBooleanResultKnown(q,false));
1422 cananian 1.1.2.1 else // okay, nothing known.
1423 cananian 1.1.2.4 raiseV(V, Wv, q.dst(), new xOperBooleanResultUnknown(q));
1424 cananian 1.1.2.1 }
1425 cananian 1.1.2.1 public void visit_icmpgt(OPER q) { visit_cmpgt(q); }
1426 cananian 1.1.2.1 public void visit_lcmpgt(OPER q) { visit_cmpgt(q); }
1427 cananian 1.1.2.1 // conversions
1428 cananian 1.1.2.1 public void visit_i2b(OPER q) {
1429 cananian 1.1.2.1 xBitWidth bw = extractWidth( get( q.operands(0) ) );
1430 cananian 1.6 int mbw = bw.minusWidth(), pbw = bw.plusWidth();
1431 cananian 1.6 if (bw.plusWidth>=8)
1432 cananian 1.6 mbw = 8; // large + val may become large - val.
1433 cananian 1.6 if (bw.minusWidth()>=8)
1434 cananian 1.6 pbw = 7; // large - val may become large + val.
1435 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
1436 cananian 1.1.2.1 new xBitWidth(HClass.Int,
1437 cananian 1.6 Math.min(8, mbw),
1438 cananian 1.6 Math.min(7, pbw) ));
1439 cananian 1.1.2.1 }
1440 cananian 1.1.2.1 public void visit_i2c(OPER q) {
1441 cananian 1.1.2.1 xBitWidth bw = extractWidth( get( q.operands(0) ) );
1442 cananian 1.6 int mbw = bw.minusWidth(), pbw = bw.plusWidth();
1443 cananian 1.6 if (bw.minusWidth()>0)
1444 cananian 1.6 pbw = 16; // - val may become large + val.
1445 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
1446 cananian 1.1.2.1 new xBitWidth(HClass.Int, 0,
1447 cananian 1.6 Math.min(16, pbw) ));
1448 cananian 1.1.2.1 }
1449 cananian 1.1.2.1 public void visit_i2l(OPER q) {
1450 cananian 1.1.2.1 xBitWidth bw = extractWidth( get( q.operands(0) ) );
1451 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
1452 cananian 1.1.2.1 new xBitWidth(HClass.Long,
1453 cananian 1.1.2.1 Math.min(32, bw.minusWidth()),
1454 cananian 1.1.2.1 Math.min(31, bw.plusWidth()) ));
1455 cananian 1.1.2.1 }
1456 cananian 1.1.2.1 public void visit_i2s(OPER q) {
1457 cananian 1.1.2.1 xBitWidth bw = extractWidth( get( q.operands(0) ) );
1458 cananian 1.6 int mbw = bw.minusWidth(), pbw = bw.plusWidth();
1459 cananian 1.6 if (bw.plusWidth>=16)
1460 cananian 1.6 mbw = 16; // large + val may become large - val.
1461 cananian 1.6 if (bw.minusWidth()>=16)
1462 cananian 1.6 pbw = 15; // large - val may become large + val.
1463 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
1464 cananian 1.1.2.1 new xBitWidth(HClass.Int,
1465 cananian 1.6 Math.min(16, mbw),
1466 cananian 1.6 Math.min(15, pbw) ));
1467 cananian 1.1.2.1 }
1468 cananian 1.1.2.1 public void visit_l2i(OPER q) {
1469 cananian 1.1.2.1 xBitWidth bw = extractWidth( get( q.operands(0) ) );
1470 cananian 1.6 int mbw = bw.minusWidth(), pbw = bw.plusWidth();
1471 cananian 1.6 if (bw.plusWidth>=32)
1472 cananian 1.6 mbw = 32; // large + val may become large - val.
1473 cananian 1.6 if (bw.minusWidth()>=32)
1474 cananian 1.6 pbw = 31; // large - val may become large + val.
1475 cananian 1.1.2.1 raiseV(V, Wv, q.dst(),
1476 cananian 1.1.2.1 new xBitWidth(HClass.Int,
1477 cananian 1.6 Math.min(32, mbw),
1478 cananian 1.6 Math.min(31, pbw) ));
1479 cananian 1.1.2.1 }
1480 cananian 1.1.2.1 // binops
1481 cananian 1.6 void visit_add(OPER q, int maxbits) {
1482 cananian 1.1.2.1 xBitWidth left = extractWidth( get( q.operands(0) ) );
1483 cananian 1.1.2.1 xBitWidth right= extractWidth( get( q.operands(1) ) );
1484 cananian 1.1.2.1 int m = Math.max( left.minusWidth(), right.minusWidth() );
1485 cananian 1.1.2.1 int p = Math.max( left.plusWidth(), right.plusWidth() );
1486 cananian 1.1.2.1 // zero plus zero is always zero, but other numbers grow.
1487 cananian 1.6 // also 0+x: x doesn't grow.
1488 cananian 1.6 if (left.minusWidth()>0 && right.minusWidth()>0) m++;
1489 cananian 1.6 if (left.plusWidth()>0 && right.plusWidth()>0) p++;
1490 cananian 1.6 // handle overflow.
1491 cananian 1.6 if (p >= maxbits)
1492 cananian 1.6 m = maxbits; // large + val becomes large - val.
1493 cananian 1.6 if (m >= maxbits)
1494 cananian 1.6 p = maxbits-1; // large - val becomes large + val.
1495 cananian 1.6 // okay, raise it!
1496 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1497 cananian 1.1.2.1 }
1498 cananian 1.6 public void visit_iadd(OPER q) { visit_add(q, 32); }
1499 cananian 1.6 public void visit_ladd(OPER q) { visit_add(q, 64); }
1500 cananian 1.1.2.1
1501 cananian 1.1.2.1 void visit_and(OPER q) {
1502 cananian 1.1.2.1 xBitWidth left = extractWidth( get( q.operands(0) ) );
1503 cananian 1.1.2.1 xBitWidth right= extractWidth( get( q.operands(1) ) );
1504 cananian 1.1.2.1 // if there are zero crossings, we have worst-case performance.
1505 cananian 1.1.2.1 int m = Math.max( left.minusWidth(), right.minusWidth() );
1506 cananian 1.1.2.1 int p = Math.max( left.plusWidth(), right.plusWidth() );
1507 cananian 1.1.2.1 // check for special positive-number cases.
1508 cananian 1.1.2.1 if (left.minusWidth()==0 && right.minusWidth()==0)
1509 cananian 1.1.2.1 p = Math.min( left.plusWidth(), right.plusWidth() );
1510 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1511 cananian 1.1.2.1 }
1512 cananian 1.1.2.1 public void visit_iand(OPER q) { visit_and(q); }
1513 cananian 1.1.2.1 public void visit_land(OPER q) { visit_and(q); }
1514 cananian 1.1.2.1
1515 cananian 1.1.2.1 void visit_div(OPER q) {
1516 cananian 1.1.2.1 // we can ignore divide-by-zero.
1517 cananian 1.1.2.1 xBitWidth left = extractWidth( get( q.operands(0) ) );
1518 cananian 1.1.2.1 xBitWidth right= extractWidth( get( q.operands(1) ) );
1519 cananian 1.1.2.1 // worst case: either number both pos and neg
1520 cananian 1.1.2.1 int m = Math.max(left.minusWidth(), left.plusWidth());
1521 cananian 1.1.2.1 int p = Math.max(left.minusWidth(), left.plusWidth());
1522 cananian 1.1.2.1 // check for special one-quadrant cases.
1523 cananian 1.1.2.1 if (left.minusWidth()==0) {
1524 cananian 1.1.2.1 if (right.minusWidth()==0) m=0; // result positive
1525 cananian 1.1.2.1 if (right.plusWidth()==0) p=0; // result negative
1526 cananian 1.1.2.1 }
1527 cananian 1.1.2.1 if (left.plusWidth()==0) {
1528 cananian 1.1.2.1 if (right.minusWidth()==0) m=0; // result negative
1529 cananian 1.1.2.1 if (right.plusWidth()==0) p=0; // result positive
1530 cananian 1.1.2.1 }
1531 cananian 1.1.2.1 // special case if divisor is a constant.
1532 cananian 1.1.2.1 if (right instanceof xIntConstant) {
1533 cananian 1.1.2.1 if (right.minusWidth()==0) { // a positive constant
1534 cananian 1.1.2.1 m = Math.max(0, left.minusWidth() - right.plusWidth());
1535 cananian 1.1.2.1 p = Math.max(0, left.plusWidth() - right.plusWidth());
1536 cananian 1.1.2.1 }
1537 cananian 1.1.2.1 if (right.plusWidth()==0) { // a negative constant
1538 cananian 1.1.2.1 m = Math.max(0, left.minusWidth()-right.minusWidth());
1539 cananian 1.1.2.1 p = Math.max(0, left.plusWidth() -right.minusWidth());
1540 cananian 1.1.2.1 }
1541 cananian 1.1.2.1 }
1542 cananian 1.6 // XXX overflow?
1543 cananian 1.1.2.1 // done.
1544 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1545 cananian 1.1.2.1 }
1546 cananian 1.1.2.1 public void visit_idiv(OPER q) { visit_div(q); }
1547 cananian 1.1.2.1 public void visit_ldiv(OPER q) { visit_div(q); }
1548 cananian 1.1.2.1
1549 cananian 1.6 void visit_mul(OPER q, int maxbits) {
1550 cananian 1.1.2.1 xBitWidth left = extractWidth( get( q.operands(0) ) );
1551 cananian 1.1.2.1 xBitWidth right= extractWidth( get( q.operands(1) ) );
1552 cananian 1.1.2.1 // worst case: either number both pos and neg
1553 cananian 1.1.2.1 int m = Math.max(left.minusWidth() + right.plusWidth(),
1554 cananian 1.1.2.1 left.plusWidth() + right.minusWidth());
1555 cananian 1.1.2.1 int p = Math.max(left.minusWidth() + right.minusWidth(),
1556 cananian 1.1.2.1 left.plusWidth() + right.plusWidth());
1557 cananian 1.1.2.1 // special case multiplication by zero, one, and two.
1558 cananian 1.1.2.16 if (right instanceof xIntConstant) { // switch r and l
1559 cananian 1.1.2.16 xBitWidth temp=left; left=right; right=temp;
1560 cananian 1.1.2.16 }
1561 cananian 1.1.2.1 if (left instanceof xIntConstant) {
1562 cananian 1.1.2.1 long val = ((xIntConstant)left).value();
1563 cananian 1.1.2.1 if (val==0) {
1564 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), left); return;
1565 cananian 1.1.2.1 }
1566 cananian 1.1.2.1 if (val==1) {
1567 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), right); return;
1568 cananian 1.1.2.1 }
1569 cananian 1.1.2.1 if (val==2) {
1570 cananian 1.1.2.1 m = right.minusWidth()+1;
1571 cananian 1.1.2.1 p = right.plusWidth() +1;
1572 cananian 1.1.2.1 }
1573 cananian 1.1.2.1 }
1574 cananian 1.1.2.1 // XXX special case multiplication by one-bit quantities?
1575 cananian 1.6 // handle overflow.
1576 cananian 1.6 if (p >= maxbits)
1577 cananian 1.6 m = maxbits; // large + val becomes large - val.
1578 cananian 1.6 if (m >= maxbits)
1579 cananian 1.6 p = maxbits-1; // large - val becomes large + val.
1580 cananian 1.1.2.1 // done.
1581 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1582 cananian 1.1.2.1 }
1583 cananian 1.6 public void visit_imul(OPER q) { visit_mul(q,32); }
1584 cananian 1.6 public void visit_lmul(OPER q) { visit_mul(q,64); }
1585 cananian 1.1.2.1
1586 cananian 1.6 void visit_neg(OPER q, int maxbits) {
1587 cananian 1.1.2.1 xBitWidth bw = extractWidth( get( q.operands(0) ) );
1588 cananian 1.1.2.1 int m = bw.plusWidth();
1589 cananian 1.1.2.1 int p = bw.minusWidth();
1590 cananian 1.6 // special case: negating the largest neg num results in neg
1591 cananian 1.6 if (bw.minusWidth() >= maxbits)
1592 cananian 1.6 m = maxbits; // -X = X for largest negative number
1593 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1594 cananian 1.1.2.1 }
1595 cananian 1.6 public void visit_ineg(OPER q) { visit_neg(q, 32); }
1596 cananian 1.6 public void visit_lneg(OPER q) { visit_neg(q, 64); }
1597 cananian 1.1.2.1
1598 cananian 1.1.2.1 void visit_or(OPER q) {
1599 cananian 1.1.2.1 xBitWidth left = extractWidth( get( q.operands(0) ) );
1600 cananian 1.1.2.1 xBitWidth right= extractWidth( get( q.operands(1) ) );
1601 cananian 1.1.2.1 // if there are zero crossings, we have worst-case performance.
1602 cananian 1.1.2.1 // XXX: check this "worst-case" computation; might be overly
1603 cananian 1.1.2.1 // conservative. If definitely correct for the
1604 cananian 1.1.2.1 // positive-number-only case.
1605 cananian 1.1.2.1 int m = Math.max( left.minusWidth(), right.minusWidth() );
1606 cananian 1.1.2.1 int p = Math.max( left.plusWidth(), right.plusWidth() );
1607 cananian 1.1.2.1 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1608 cananian 1.1.2.1 }
1609 cananian 1.1.2.1 public void visit_ior(OPER q) { visit_or(q); }
1610 cananian 1.1.2.1 public void visit_lor(OPER q) { visit_or(q); }
1611 cananian 1.1.2.16
1612 cananian 1.1.2.16 void visit_rem(OPER q) {
1613 cananian 1.1.2.16 // we don't have to worry about division by zero.
1614 cananian 1.1.2.16 xBitWidth left = extractWidth( get( q.operands(0) ) );
1615 cananian 1.1.2.16 xBitWidth right= extractWidth( get( q.operands(1) ) );
1616 cananian 1.1.2.16 // from JLS 15.17.3: "the result of the remainder
1617 cananian 1.1.2.16 // operation can be negative only if the dividend is
1618 cananian 1.1.2.16 // negative, and can be positive only if the dividend
1619 cananian 1.1.2.16 // is positive; moreover, the magnitude of the result
1620 cananian 1.1.2.16 // is always less than the magnitude of the divisor."
1621 cananian 1.1.2.16 if (right instanceof xIntConstant) {
1622 cananian 1.1.2.16 // use the fact that result is strictly less to narrow
1623 cananian 1.1.2.16 long val = ((xIntConstant)right).value();
1624 cananian 1.1.2.16 right = new xIntConstant(right.type(), val-1 );
1625 cananian 1.1.2.16 }
1626 cananian 1.1.2.16 int absmag=Math.max(left.minusWidth(), left.plusWidth());
1627 cananian 1.1.2.16 // abs value of result will also always be smaller than
1628 cananian 1.1.2.16 // abs value of dividend.
1629 cananian 1.1.2.16 int m = Math.min(right.minusWidth(), absmag);
1630 cananian 1.1.2.16 int p = Math.min(right.plusWidth(), absmag);
1631 cananian 1.6 // XXX overflow?
1632 cananian 1.1.2.16 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1633 cananian 1.1.2.16 }
1634 cananian 1.1.2.16 public void visit_irem(OPER q) { visit_rem(q); }
1635 cananian 1.1.2.16 public void visit_lrem(OPER q) { visit_rem(q); }
1636 cananian 1.1.2.16
1637 cananian 1.1.2.16 // SHIFTS. From the JLS, 15.19: "If the promoted type of
1638 cananian 1.1.2.16 // the left-hand operand is int, only the five
1639 cananian 1.1.2.16 // lowest-order bits of the right-hand operand are used as
1640 cananian 1.1.2.16 // the shift distance. It is as if the right-hand operand
1641 cananian 1.1.2.16 // were subjected to a bitwise logical AND operator &
1642 cananian 1.1.2.16 // (15.22.1) with the mask value 0x1f. The shift distance
1643 cananian 1.1.2.16 // actually used is therefore always in the range 0 to 31,
1644 cananian 1.1.2.16 // inclusive.
1645 cananian 1.1.2.16 //
1646 cananian 1.1.2.16 // "If the promoted type of the left-hand operand is long,
1647 cananian 1.1.2.16 // then only the six lowest-order bits of the right-hand
1648 cananian 1.1.2.16 // operand are used as the shift distance. It is as if the
1649 cananian 1.1.2.16 // right-hand operand were subjected to a bitwise logical
1650 cananian 1.1.2.16 // AND operator & (15.22.1) with the mask value 0x3f. The
1651 cananian 1.1.2.16 // shift distance actually used is therefore always in the
1652 cananian 1.1.2.16 // range 0 to 63, inclusive."
1653 cananian 1.1.2.16
1654 cananian 1.1.2.16 void visit_shl(OPER q, boolean isLong) {
1655 cananian 1.1.2.16 xBitWidth left = extractWidth( get( q.operands(0) ) );
1656 cananian 1.1.2.16 xBitWidth right= extractWidth( get( q.operands(1) ) );
1657 cananian 1.1.2.16 int shift;
1658 cananian 1.1.2.16 // compute largest possible shift.
1659 cananian 1.1.2.16 if (right instanceof xIntConstant) {
1660 cananian 1.1.2.16 // we know the shift exactly. whoo-hoo!
1661 cananian 1.1.2.16 long val = ((xIntConstant)right).value();
1662 cananian 1.1.2.16 shift = (int) (val & (isLong ? 0x3F : 0x1F ));
1663 cananian 1.1.2.16 // equivalent to mult by constant 2^shift.
1664 cananian 1.1.2.16 } else if (right.minusWidth()==0 &&
1665 cananian 1.1.2.16 right.plusWidth() < (isLong ? 6 : 5)) {
1666 cananian 1.1.2.16 //largest value possible on right is (2^p)-1.
1667 cananian 1.1.2.16 shift = (1<<right.plusWidth())-1;
1668 cananian 1.1.2.16 } else
1669 cananian 1.1.2.16 shift = (isLong) ? 63 : 31;
1670 cananian 1.1.2.16 // okay. nominally widths are width+shift.
1671 cananian 1.1.2.16 int m = left.minusWidth()+shift;
1672 cananian 1.1.2.16 int p = left.plusWidth()+shift;
1673 cananian 1.1.2.16 // zero shifted by anything is still zero, though.
1674 cananian 1.1.2.16 if (left.minusWidth()==0) m=0;
1675 cananian 1.1.2.16 if (left.plusWidth()==0) p=0;
1676 cananian 1.1.2.16 // if we could corrupt the sign bit, all bets are off.
1677 cananian 1.1.2.16 boolean canFrobSign =
1678 cananian 1.1.2.16 /* can leftmost one move into sign bit? */
1679 cananian 1.1.2.16 ( (left.plusWidth()+shift) >= (isLong?64:32) ) ||
1680 cananian 1.1.2.16 /* can leftmost zero move into sign bit? */
1681 cananian 1.1.2.16 ( (left.minusWidth()+shift) >= (isLong?64:32) );
1682 cananian 1.1.2.16 if (canFrobSign) { m=1000; p=1000; }
1683 cananian 1.1.2.16 // rely on bitwidth limiting the below.
1684 cananian 1.1.2.16 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1685 cananian 1.1.2.16 }
1686 cananian 1.1.2.16 public void visit_ishl(OPER q) { visit_shl(q, false); }
1687 cananian 1.1.2.16 public void visit_lshl(OPER q) { visit_shl(q, true); }
1688 cananian 1.1.2.16
1689 cananian 1.1.2.16 void visit_shr(OPER q, boolean isSigned, boolean isLong) {
1690 cananian 1.1.2.16 xBitWidth left = extractWidth( get( q.operands(0) ) );
1691 cananian 1.1.2.16 xBitWidth right= extractWidth( get( q.operands(1) ) );
1692 cananian 1.1.2.16 int shift; boolean exactlyZero=false;
1693 cananian 1.1.2.16 // compute smallest possible shift.
1694 cananian 1.1.2.16 if (right instanceof xIntConstant) {
1695 cananian 1.1.2.16 // we know the shift exactly. whoo-hoo!
1696 cananian 1.1.2.16 long val = ((xIntConstant)right).value();
1697 cananian 1.1.2.16 shift = (int) (val & (isLong ? 0x3F : 0x1F ));
1698 cananian 1.1.2.16 if (shift==0) exactlyZero=true;
1699 cananian 1.1.2.16 } else
1700 cananian 1.1.2.16 // smallest possible shift is zero.
1701 cananian 1.1.2.16 shift = 0;
1702 cananian 1.1.2.16 // okay. nominally widths are width-shift.
1703 cananian 1.1.2.16 int m = Math.max(0, left.minusWidth()-shift);
1704 cananian 1.1.2.16 int p = Math.max(0, left.plusWidth()-shift);
1705 cananian 1.1.2.16 // zero shifted by anything is still zero, though.
1706 cananian 1.1.2.16 if (left.minusWidth()==0) m=0;
1707 cananian 1.1.2.16 if (left.plusWidth()==0) p=0;
1708 cananian 1.1.2.16 // if we could corrupt the sign bit, negative numbers
1709 cananian 1.1.2.16 // can become large positive numbers.
1710 cananian 1.1.2.16 if (left.minusWidth()>0 && !isSigned && !exactlyZero)
1711 cananian 1.1.2.16 p=Math.max(p, (isLong?64:32)-shift);
1712 cananian 1.1.2.16 // rely on bitwidth limiting the below.
1713 cananian 1.1.2.16 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1714 cananian 1.1.2.16 }
1715 cananian 1.1.2.16 public void visit_ishr(OPER q) { visit_shr(q, false, false); }
1716 cananian 1.1.2.16 public void visit_lshr(OPER q) { visit_shr(q, false, true); }
1717 cananian 1.1.2.16 public void visit_iushr(OPER q) { visit_shr(q, true, false); }
1718 cananian 1.1.2.16 public void visit_lushr(OPER q) { visit_shr(q, true, true); }
1719 cananian 1.1.2.16
1720 cananian 1.1.2.16 void visit_xor(OPER q) {
1721 cananian 1.1.2.16 xBitWidth left = extractWidth( get( q.operands(0) ) );
1722 cananian 1.1.2.16 xBitWidth right= extractWidth( get( q.operands(1) ) );
1723 cananian 1.1.2.16 int mL=left.minusWidth(), pL=left.plusWidth();
1724 cananian 1.1.2.16 int mR=right.minusWidth(), pR=right.plusWidth();
1725 cananian 1.1.2.16 int m=0, p=0;
1726 cananian 1.1.2.16 // note that <0,0>=constant zero is included in plus range
1727 cananian 1.1.2.16 // (i.e. all ranges are said to have '+' components (the 0) )
1728 cananian 1.1.2.16 // <0,pL> xor <0,pR> = <0,MAX(pL,pR)>
1729 cananian 1.1.2.16 if (pL>=0 && pR>=0)
1730 cananian 1.1.2.16 p = Math.max(p, Math.max(pL, pR));
1731 cananian 1.1.2.16 // <0,pL> xor <mR,0> = <MAX(pL,mR),0>
1732 cananian 1.1.2.16 if (pL>=0 && mR>0)
1733 cananian 1.1.2.16 m = Math.max(m, Math.max(pL, mR));
1734 cananian 1.1.2.16 // <mL,0> xor <0,pR> = <MAX(mL,pR),0>
1735 cananian 1.1.2.16 if (mL>0 && pR>=0)
1736 cananian 1.1.2.16 m = Math.max(m, Math.max(mL, pR));
1737 cananian 1.1.2.16 // <mL,0> xor <mR,0> = <0,MAX(mL,mR)>
1738 cananian 1.1.2.16 if (mL>0 && mR>0)
1739 cananian 1.1.2.16 p = Math.max(p, Math.max(mL, mR));
1740 cananian 1.1.2.16 // ta-da!
1741 cananian 1.1.2.16 raiseV(V, Wv, q.dst(), new xBitWidth(q.evalType(), m, p) );
1742 cananian 1.1.2.16 }
1743 cananian 1.1.2.16 public void visit_ixor(OPER q) { visit_xor(q); }
1744 cananian 1.1.2.16 public void visit_lxor(OPER q) { visit_xor(q); }
1745 cananian 1.1.2.1 }
1746 cananian 1.1.2.1 }
1747 cananian 1.1.2.1 /*-------------------------------------------------------------*/
1748 cananian 1.1.2.1 // Extract bitwidth information from unwilling victims.
1749 cananian 1.1.2.1 xBitWidth extractWidth(LatticeVal v) {
1750 cananian 1.1.2.1 if (v instanceof xBitWidth)
1751 cananian 1.1.2.1 return (xBitWidth) v;
1752 cananian 1.1.2.1 if (! (v instanceof xClass) )
1753 cananian 1.1.2.1 throw new Error("Something's seriously screwed up.");
1754 cananian 1.1.2.1 xClass xc = (xClass) v;
1755 cananian 1.1.2.1 // trust xBitWidth to properly limit.
1756 cananian 1.1.2.1 return new xBitWidth(xc.type(), 1000, 1000);
1757 cananian 1.1.2.1 }
1758 cananian 1.1.2.1
1759 cananian 1.1.2.1 // Deal with the fact that external Byte/Short/Char/Boolean classes
1760 cananian 1.1.2.1 // are represented internally as ints.
1761 cananian 1.1.2.1
1762 cananian 1.1.2.1 static HClass toInternal(HClass c) {
1763 cananian 1.1.2.1 if (c.equals(HClass.Byte) || c.equals(HClass.Short) ||
1764 cananian 1.1.2.1 c.equals(HClass.Char) || c.equals(HClass.Boolean))
1765 cananian 1.1.2.1 return HClass.Int;
1766 cananian 1.1.2.1 return c;
1767 cananian 1.1.2.1 }
1768 cananian 1.1.2.1
1769 cananian 1.1.2.1 /*-------------------------------------------------------------*/
1770 cananian 1.1.2.1 // Lattice classes.
1771 cananian 1.1.2.1
1772 cananian 1.1.2.1 /** No information obtainable about a temp. */
1773 cananian 1.1.2.4 static abstract class LatticeVal {
1774 cananian 1.1.2.1 public String toString() { return "Top"; }
1775 cananian 1.1.2.1 public boolean equals(Object o) { return o instanceof LatticeVal; }
1776 cananian 1.1.2.4 // merge.
1777 cananian 1.1.2.4 public abstract LatticeVal merge(LatticeVal v);
1778 cananian 1.1.2.5 // narrow.
1779 cananian 1.1.2.5 public abstract boolean isLowerThan(LatticeVal v);
1780 cananian 1.1.2.1 // by default, the renaming does nothing.
1781 cananian 1.1.2.1 public LatticeVal rename(PHI p, int i) { return this; }
1782 cananian 1.1.2.1 public LatticeVal rename(SIGMA s, int i) { return this; }
1783 cananian 1.1.2.1 }
1784 cananian 1.1.2.1 /** A typed temp. */
1785 cananian 1.1.2.1 static class xClass extends LatticeVal {
1786 cananian 1.1.2.1 protected HClass type;
1787 cananian 1.1.2.1 public xClass(HClass type) {
1788 cananian 1.4.2.1 assert type!=HClass.Boolean && type!=HClass.Byte &&
1789 cananian 1.4.2.1 type!=HClass.Short && type!=HClass.Char : "Not an internal type ("+type+")";
1790 cananian 1.1.2.1 this.type = type;
1791 cananian 1.1.2.1 }
1792 cananian 1.1.2.1 public HClass type() { return type; }
1793 cananian 1.1.2.1 public String toString() {
1794 cananian 1.1.2.1 return "xClass: " + type;
1795 cananian 1.1.2.1 }
1796 cananian 1.1.2.4 public boolean equals(Object o) { return _equals(o); }
1797 cananian 1.1.2.4 private boolean _equals(Object o) {
1798 cananian 1.1.2.1 xClass xc;
1799 cananian 1.1.2.1 try { xc=(xClass) o; }
1800 cananian 1.1.2.1 catch (ClassCastException e) { return false;}
1801 cananian 1.1.2.1 return xc!=null && xc.type.equals(type);
1802 cananian 1.1.2.1 }
1803 cananian 1.1.2.4 public LatticeVal merge(LatticeVal v) {
1804 cananian 1.1.2.4 xClass vv = (xClass) v;
1805 cananian 1.1.2.4 return new xClass(mergeTypes(this.type, vv.type));
1806 cananian 1.1.2.4 }
1807 cananian 1.1.2.5 public boolean isLowerThan(LatticeVal v) {
1808 cananian 1.1.2.5 return !(v instanceof xClass);
1809 cananian 1.1.2.5 }
1810 cananian 1.1.2.4 // Class merge function.
1811 cananian 1.1.2.4 static HClass mergeTypes(HClass a, HClass b) {
1812 cananian 1.4.2.1 assert a!=null && b!=null;
1813 cananian 1.1.2.4 if (a==b) return a; // take care of primitive types.
1814 cananian 1.1.2.4
1815 cananian 1.1.2.4 // Special case 'Void' Hclass, used for null constants.
1816 cananian 1.1.2.4 if (a==HClass.Void)
1817 cananian 1.1.2.4 return b;
1818 cananian 1.1.2.4 if (b==HClass.Void)
1819 cananian 1.1.2.4 return a;
1820 cananian 1.1.2.4
1821 cananian 1.1.2.4 // by this point better be array ref or object, not primitive type.
1822 cananian 1.4.2.1 assert (!a.isPrimitive()) && (!b.isPrimitive());
1823 cananian 1.1.2.4 return HClassUtil.commonParent(a,b);
1824 cananian 1.1.2.1 }
1825 cananian 1.1.2.1 }
1826 cananian 1.1.2.1 /** A single class type; guaranteed the value is not null. */
1827 cananian 1.1.2.1 static class xClassNonNull extends xClass {
1828 cananian 1.1.2.1 public xClassNonNull(HClass type) {
1829 cananian 1.1.2.1 super( type );
1830 cananian 1.4.2.1 assert type!=HClass.Void;
1831 cananian 1.1.2.1 }
1832 cananian 1.1.2.1 public String toString() {
1833 cananian 1.1.2.1 return "xClassNonNull: { " + type + " }";
1834 cananian 1.1.2.1 }
1835 cananian 1.1.2.4 public boolean equals(Object o) { return _equals(o); }
1836 cananian 1.1.2.4 private boolean _equals(Object o) {
1837 cananian 1.1.2.1 return (o instanceof xClassNonNull && super.equals(o));
1838 cananian 1.1.2.1 }
1839 cananian 1.1.2.4 public LatticeVal merge(LatticeVal v) {
1840 cananian 1.1.2.4 if (!(v instanceof xClassNonNull)) return super.merge(v);
1841 cananian 1.1.2.4 xClassNonNull vv = (xClassNonNull) v;
1842 cananian 1.1.2.4 return new xClassNonNull(mergeTypes(this.type, vv.type));
1843 cananian 1.1.2.1 }
1844 cananian 1.1.2.5 public boolean isLowerThan(LatticeVal v) {
1845 cananian 1.1.2.5 return !(v instanceof xClassNonNull);
1846 cananian 1.1.2.5 }
1847 cananian 1.1.2.1 }
1848 cananian 1.1.2.1 /** An object of the specified *exact* type (not a subtype). */
1849 cananian 1.1.2.1 static class xClassExact extends xClassNonNull {
1850 cananian 1.1.2.1 public xClassExact(HClass type) {
1851 cananian 1.1.2.1 super(type);
1852 cananian 1.7 assert !type.isInterface(); // interface types can't be exact.
1853 cananian 1.1.2.1 }
1854 cananian 1.1.2.1 public String toString() {
1855 cananian 1.1.2.1 return "xClassExact: { " + type + " }";
1856 cananian 1.1.2.1 }
1857 cananian 1.1.2.4 public boolean equals(Object o) { return _equals(o); }
1858 cananian 1.1.2.4 private boolean _equals(Object o) {
1859 cananian 1.1.2.1 return (o instanceof xClassExact && super.equals(o));
1860 cananian 1.1.2.1 }
1861 cananian 1.1.2.4 public LatticeVal merge(LatticeVal v) {
1862 cananian 1.1.2.4 if (this._equals(v)) return new xClassExact(type);
1863 cananian 1.1.2.4 return super.merge(v);
1864 cananian 1.1.2.1 }
1865 cananian 1.1.2.5 public boolean isLowerThan(LatticeVal v) {
1866 cananian 1.1.2.5 return !(v instanceof xClassExact);
1867 cananian 1.1.2.5 }
1868 cananian 1.1.2.1 }
1869 cananian 1.1.2.1 /** An array with constant length. The array is not null, of course. */
1870 cananian 1.1.2.1 static class xClassArray extends xClassExact {
1871 cananian 1.1.2.1 protected int length;
1872 cananian 1.1.2.1 public xClassArray(HClass type, int length) {
1873 cananian 1.1.2.1 super(type);
1874 cananian 1.1.2.1 this.length = length;
1875 cananian 1.1.2.1 }
1876 cananian 1.1.2.1 public int length() { return length; }
1877 cananian 1.1.2.1 public String toString() {
1878 cananian 1.1.2.1 return "xClassArray: " +
1879 cananian 1.1.2.1 type.getComponentType() + "["+length+"]";
1880 cananian 1.1.2.1 }
1881 cananian 1.1.2.4 public boolean equals(Object o) { return _equals(o); }
1882 cananian 1.1.2.4 private boolean _equals(Object o) {
1883 cananian 1.1.2.1 xClassArray xca;
1884 cananian 1.1.2.1 try { xca = (xClassArray) o; }
1885 cananian 1.1.2.1 catch (ClassCastException e) { return false; }
1886 cananian 1.1.2.1 return xca!=null && super.equals(xca) && xca.length == length;
1887 cananian 1.1.2.1 }
1888 cananian 1.1.2.4 public LatticeVal merge(LatticeVal v) {
1889 cananian 1.1.2.4 if (this._equals(v)) return new xClassArray(type,length);
1890 cananian 1.1.2.4 return super.merge(v);
1891 cananian 1.1.2.1 }
1892 cananian 1.1.2.5 public boolean isLowerThan(LatticeVal v) {
1893 cananian 1.1.2.5 return !(v instanceof xClassArray);
1894 cananian 1.1.2.5 }
1895 cananian 1.1.2.1 }
1896 cananian 1.1.2.1 /** An integer value of the specified bitwidth. */
1897 cananian 1.1.2.1 static class xBitWidth extends xClassExact {
1898 cananian 1.1.2.1 /** Highest significant bit for positive numbers. */
1899 cananian 1.1.2.1 protected int plusWidth;
1900 cananian 1.1.2.1 /** Highest significant bit for negative numbers. */
1901 cananian 1.1.2.1 protected int minusWidth;
1902 cananian 1.1.2.1 /** Constructor. */
1903 cananian 1.1.2.1 public xBitWidth(HClass type, int minusWidth, int plusWidth) {
1904 cananian 1.1.2.1 super(toInternal(type));
1905 cananian 1.1.2.1 // limit.
1906 cananian 1.1.2.1 if (type == HClass.Long) {
1907 cananian 1.1.2.1 this.minusWidth = Math.min(64, minusWidth);
1908 cananian 1.1.2.1 this.plusWidth = Math.min(63, plusWidth);
1909 cananian 1.1.2.1 } else if (type == HClass.Int) {
1910 cananian 1.1.2.1 this.minusWidth = Math.min(32, minusWidth);
1911 cananian 1.1.2.1 this.plusWidth = Math.min(31, plusWidth);
1912 cananian 1.1.2.1 } else // NON-CANONICAL TYPES: CAREFUL! (this.type fixed by above)
1913 cananian 1.1.2.1 if (type == HClass.Boolean) {
1914 cananian 1.1.2.1 this.minusWidth = Math.min( 0, minusWidth);
1915 cananian 1.1.2.1 this.plusWidth = Math.min( 1, plusWidth);
1916 cananian 1.1.2.1 } else if (type == HClass.Short) {
1917 cananian 1.1.2.1 this.minusWidth = Math.min(16, minusWidth);
1918 cananian 1.1.2.1 this.plusWidth = Math.min(15, plusWidth);
1919 cananian 1.1.2.1 } else if (type == HClass.Byte) {
1920 cananian 1.1.2.1 this.minusWidth = Math.min( 8, minusWidth);
1921 cananian 1.1.2.1 this.plusWidth = Math.min( 7, plusWidth);
1922 cananian 1.1.2.1 } else if (type == HClass.Char) {
1923 cananian 1.1.2.1 this.minusWidth = Math.min( 0, minusWidth);
1924 cananian 1.1.2.1 this.plusWidth = Math.min(16, plusWidth);
1925 cananian 1.1.2.1 } else throw new Error("Unknown type for xBitWidth: "+type);
1926 cananian 1.1.2.1 }
1927 cananian 1.1.2.1 public int minusWidth() { return minusWidth; }
1928 cananian 1.1.2.1 public int plusWidth () { return plusWidth; }
1929 cananian 1.1.2.1 public String toString() {
1930 cananian 1.1.2.1 return "xBitWidth: " + type + " " +
1931 cananian 1.1.2.1 "-"+minusWidth+"+"+plusWidth+" bits";
1932 cananian 1.1.2.1 }
1933 cananian 1.1.2.4 public boolean equals(Object o) { return _equals(o); }
1934 cananian 1.1.2.4 private boolean _equals(Object o) {
1935 cananian 1.1.2.1 xBitWidth xbw;
1936 cananian 1.1.2.1 try { xbw = (xBitWidth) o; }
1937 cananian 1.1.2.1 catch (ClassCastException e) { return false; }
1938 cananian 1.1.2.1 return xbw!=null && super.equals(xbw) &&
1939 cananian 1.1.2.1 xbw.minusWidth == minusWidth &&
1940 cananian 1.1.2.1 xbw.plusWidth == plusWidth;
1941 cananian 1.1.2.1 }
1942 cananian 1.1.2.4 public LatticeVal merge(LatticeVal v) {
1943 cananian 1.1.2.4 if (!(v instanceof xBitWidth)) return super.merge(v);
1944 cananian 1.1.2.4 // bitwidth merge
1945 cananian 1.1.2.4 xBitWidth vv = (xBitWidth) v;
1946 cananian 1.1.2.4 if (!this.type.equals(vv.type)) return super.merge(vv);
1947 cananian 1.1.2.4 return new xBitWidth
1948 cananian 1.1.2.4 (this.type,
1949 cananian 1.1.2.4 Math.max(this.minusWidth, vv.minusWidth),
1950 cananian 1.1.2.4 Math.max(this.plusWidth, vv.plusWidth));
1951 cananian 1.1.2.1 }
1952 cananian 1.1.2.5 public boolean isLowerThan(LatticeVal v) {
1953 cananian 1.1.2.5 return !(v instanceof xBitWidth);
1954 cananian 1.1.2.5 }
1955 cananian 1.1.2.1 }
1956 cananian 1.1.2.1 /** An integer value which is the result of an INSTANCEOF. */
1957 cananian 1.1.2.4 static class xInstanceofResultUnknown extends xBitWidth
1958 cananian 1.1.2.4 implements xInstanceofResult {
1959 cananian 1.1.2.1 Temp tested;
1960 cananian 1.1.2.1 INSTANCEOF q;
1961 cananian 1.1.2.4 public xInstanceofResultUnknown(INSTANCEOF q) { this(q, q.src()); }
1962 cananian 1.1.2.4 xInstanceofResultUnknown(INSTANCEOF q, Temp tested) {
1963 cananian 1.1.2.1 super(toInternal(HClass.Boolean),0,1);
1964 cananian 1.1.2.1 this.q = q;
1965 cananian 1.1.2.1 this.tested = tested;
1966 cananian 1.1.2.1 }
1967 cananian 1.1.2.1 public Temp tested() { return tested; }
1968 cananian 1.1.2.1 public INSTANCEOF def() { return q; }
1969 cananian 1.1.2.1 public String toString() {
1970 cananian 1.1.2.4 return "xInstanceofResultUnknown: " + type + " " +q;
1971 cananian 1.1.2.1 }
1972 cananian 1.1.2.4 public boolean equals(Object o) { return _equals(o); }
1973 cananian 1.1.2.4 private boolean _equals(Object o) {
1974 cananian 1.1.2.4 return (o instanceof xInstanceofResultUnknown && super.equals(o) &&
1975 cananian 1.1.2.4 ((xInstanceofResultUnknown)o).q == q &&
1976 cananian 1.1.2.4 ((xInstanceofResultUnknown)o).tested == tested);
1977 cananian 1.1.2.4 }
1978 cananian 1.1.2.4 public LatticeVal merge(LatticeVal v) {
1979 cananian 1.1.2.4 if (v instanceof xInstanceofResult)
1980 cananian 1.1.2.4 // xInstanceofResultKnown merged with
1981 cananian 1.1.2.4 // xInstanceofResultKnown or xInstanceofResultUnknown
1982 cananian 1.1.2.4 return makeUnknown();
1983 cananian 1.1.2.4 // all others.
1984 cananian 1.1.2.4 return super.merge(v);
1985 cananian 1.1.2.4 }
1986 cananian 1.1.2.5 public boolean isLowerThan(LatticeVal v) {
1987 cananian 1.1.2.5 return !(v instanceof xBitWidth);
1988 cananian 1.1.2.5 }
1989 cananian 1.1.2.4 public xInstanceofResultKnown makeKnown(boolean nvalue) {
1990 cananian 1.1.2.4 return new xInstanceofResultKnown(q,tested,nvalue?1:0);
1991 cananian 1.1.2.4 }
1992 cananian 1.1.2.4 public xInstanceofResultUnknown makeUnknown() {
1993 cananian 1.1.2.4 return new xInstanceofResultUnknown(q,tested);
1994 cananian 1.1.2.1 }
1995 cananian 1.1.2.1 // override renaming functions.
1996 cananian 1.1.2.1 public LatticeVal rename(PHI q, int j) {
1997 cananian 1.1.2.1 for (int i=0; i<q.numPhis(); i++)
1998 cananian 1.1.2.1 if (q.src(i, j)==this.tested)
1999 cananian 1.1.2.4 return new xInstanceofResultUnknown(def(), q.dst(i));
2000 cananian 1.1.2.1 return this;
2001 cananian 1.1.2.1 }
2002 cananian 1.1.2.1 public LatticeVal rename(SIGMA q, int j) {
2003 cananian 1.1.2.1 for (int i=0; i<q.numSigmas(); i++)
2004 cananian 1.1.2.1 if (q.src(i)==this.tested)
2005 cananian 1.1.2.4 return new xInstanceofResultUnknown(def(), q.dst(i, j));
2006 cananian 1.1.2.1 return this;
2007 cananian 1.1.2.1 }
2008 cananian 1.1.2.1 }
2009 cananian 1.1.2.4 /** An unknown boolean value which is the result of an OPER. */
2010 cananian 1.1.2.4 static class xOperBooleanResultUnknown extends xBitWidth
2011 cananian 1.1.2.4 implements xOperBooleanResult {
2012 cananian 1.1.2.1 OPER q;
2013 cananian 1.1.2.1 Temp[] operands;
2014 cananian 1.1.2.4 public xOperBooleanResultUnknown(OPER q) { this(q, q.operands()); }
2015 cananian 1.1.2.4 xOperBooleanResultUnknown(OPER q, Temp[] operands) {
2016 cananian 1.1.2.1 super(toInternal(HClass.Boolean),0,1);
2017 cananian 1.1.2.1 this.q = q;
2018 cananian 1.1.2.1 this.operands = operands;
2019 cananian 1.1.2.1 }
2020 cananian 1.1.2.1 public Temp[] operands() { return operands; }
2021 cananian 1.1.2.1 public OPER def() { return q; }
2022 cananian 1.1.2.1 public String toString() {
2023 cananian 1.1.2.4 return "xOperBooleanResultUnknown: " + type + " " +q;
2024 cananian 1.1.2.1 }
2025 cananian 1.1.2.4 public boolean equals(Object o) { return _equals(o); }
2026 cananian 1.1.2.4 private boolean _equals(Object o) {
2027 cananian 1.1.2.1 if (o==this) return true; // common case.
2028 cananian 1.1.2.4 if (!(o instanceof xOperBooleanResultUnknown)) return false;
2029 cananian 1.1.2.1 if (!super.equals(o)) return false;
2030 cananian 1.1.2.4 xOperBooleanResultUnknown oo = (xOperBooleanResultUnknown)o;
2031 cananian 1.1.2.1 if (oo.q != q) return false;
2032 cananian 1.1.2.1 if (oo.operands.length != operands.length) return false;
2033 cananian 1.1.2.1 for (int i=0; i<operands.length; i++)
2034 cananian 1.1.2.1 if (oo.operands[i] != operands[i]) return false;
2035 cananian 1.1.2.1 return true;
2036 cananian 1.1.2.1 }
2037 cananian 1.1.2.4 public LatticeVal merge(LatticeVal v) {
2038 cananian 1.1.2.4 if (v instanceof xOperBooleanResult)
2039 cananian 1.1.2.4 // xOperBooleanResultKnown merged with
2040 cananian 1.1.2.4 // xOperBooleanResultKnown or xOperBooleanResultUnknown
2041 cananian 1.1.2.4 return makeUnknown();
2042 cananian 1.1.2.4 // all others.
2043 cananian 1.1.2.4 return super.merge(v);
2044 cananian 1.1.2.4 }
2045 cananian 1.1.2.5 public boolean isLowerThan(LatticeVal v) {
2046 cananian 1.1.2.5 return !(v instanceof xBitWidth);
2047 cananian 1.1.2.5 }
2048 cananian 1.1.2.4 public xOperBooleanResultKnown makeKnown(boolean nvalue) {
2049 cananian 1.1.2.4 return new xOperBooleanResultKnown(q,operands,nvalue?1:0);
2050 cananian 1.1.2.4 }
2051 cananian 1.1.2.4 public xOperBooleanResultUnknown makeUnknown() {
2052 cananian 1.1.2.4 return new xOperBooleanResultUnknown(q,operands);
2053 cananian 1.1.2.1 }
2054 cananian 1.1.2.1 // override renaming functions.
2055 cananian 1.1.2.1 public LatticeVal rename(PHI q, int j) {
2056 cananian 1.1.2.1 MyTempMap mtm = new MyTempMap();
2057 cananian 1.1.2.1 for (int i=0; i<q.numPhis(); i++)
2058 cananian 1.1.2.1 mtm.put(q.src(i,j), q.dst(i));
2059 cananian 1.1.2.4 return new xOperBooleanResultUnknown(def(), mtm.tempMap(operands()));
2060 cananian 1.1.2.1 }
2061 cananian 1.1.2.1 public LatticeVal rename(SIGMA q, int j) {
2062 cananian 1.1.2.1 MyTempMap mtm = new MyTempMap();
2063 cananian 1.1.2.1 for (int i=0; i<q.numSigmas(); i++)
2064 cananian 1.1.2.1 mtm.put(q.src(i), q.dst(i, j));
2065 cananian 1.1.2.4 return new xOperBooleanResultUnknown(def(), mtm.tempMap(operands()));
2066 cananian 1.1.2.1 }
2067 cananian 1.1.2.1 private static class MyTempMap extends HashMap implements TempMap {
2068 cananian 1.1.2.1 public Temp tempMap(Temp t) {
2069 pnkfelix 1.1.2.8 return containsKey(t) ? (Temp) super.get(t) : t;
2070 cananian 1.1.2.1 }
2071 cananian 1.1.2.1 public Temp[] tempMap(Temp[] t) {
2072 cananian 1.1.2.1 Temp[] r = new Temp[t.length];
2073 cananian 1.1.2.1 for (int i=0; i<r.length; i++)
2074 cananian 1.1.2.1 r[i] = tempMap(t[i]);
2075 cananian 1.1.2.1 return r;
2076 cananian 1.1.2.1 }
2077 cananian 1.1.2.1 }
2078 cananian 1.1.2.1 }
2079 cananian 1.1.2.1 /** An integer or boolean constant. */
2080 cananian 1.1.2.1 static class xIntConstant extends xBitWidth implements xConstant {
2081 cananian 1.1.2.1 protected long value;
2082 cananian 1.1.2.1 public xIntConstant(HClass type, long value) {
2083 cananian 1.1.2.1 super(type, value<0?Util.fls(-value):0, value>0?Util.fls(value):0);
2084 cananian 1.1.2.1 this.value = value;
2085 cananian 1.1.2.1 }
2086 cananian 1.1.2.1 public long value() { return value; }
2087 cananian 1.1.2.1 public Object constValue() {
2088 cananian 1.1.2.1 if (type==HClass.Int) return new Integer((int)value);
2089 cananian 1.1.2.1 if (type==HClass.Long) return new Long((long)value);
2090 cananian 1.1.2.1 //if (type==HClass.Boolean) return new Integer(value!=0?1:0);
2091 cananian 1.1.2.1 throw new Error("Unknown integer constant type.");
2092 cananian 1.1.2.1 }
2093 cananian 1.1.2.1 public String toString() {
2094 cananian 1.1.2.1 return "xIntConstant: " + type + " " + value;
2095 cananian 1.1.2.1 }
2096 cananian 1.1.2.4 public boolean equals(Object o) { return _equals(o); }
2097 cananian 1.1.2.4 private boolean _equals(Object o) {
2098 cananian 1.1.2.1 return (o instanceof xIntConstant && super.equals(o) &&
2099 cananian 1.1.2.1 ((xIntConstant)o).value == value);
2100 cananian 1.1.2.1 }
2101 cananian 1.1.2.4 public LatticeVal merge(LatticeVal v) {
2102 cananian 1.1.2.4 if (this._equals(v)) return new xIntConstant(type,value);
2103 cananian 1.1.2.4 return super.merge(v);
2104 cananian 1.1.2.4 }
2105 cananian 1.1.2.5 public boolean isLowerThan(LatticeVal v) {
2106 cananian 1.1.2.5 return !(v instanceof xIntConstant);
2107 cananian 1.1.2.5 }
2108 cananian 1.1.2.4 }
2109 cananian 1.1.2.4 /** An integer value which is the result of an INSTANCEOF. */
2110 cananian 1.1.2.4 static class xInstanceofResultKnown extends xIntConstant
2111 cananian 1.1.2.4 implements xInstanceofResult {
2112 cananian 1.1.2.4 Temp tested;
2113 cananian 1.1.2.4 INSTANCEOF q;
2114 cananian 1.1.2.4 public xInstanceofResultKnown(INSTANCEOF q, boolean value) {
2115 cananian 1.1.2.4 this(q, q.src(), value?1:0);
2116 cananian 1.1.2.4 }
2117 cananian 1.1.2.4 private xInstanceofResultKnown(INSTANCEOF q, Temp tested, long value) {
2118 cananian 1.1.2.4 super(toInternal(HClass.Boolean),value);
2119 cananian 1.1.2.4 this.q = q;
2120 cananian 1.1.2.4 this.tested = tested;
2121 cananian 1.4.2.1 assert value==0 || value==1;
2122 cananian 1.1.2.4 }
2123 cananian 1.1.2.4 public Temp tested() { return tested; }
2124 cananian 1.1.2.4 public INSTANCEOF def() { return q; }
2125 cananian 1.1.2.4 public String toString() {
2126 cananian 1.1.2.4 return "xInstanceofResultKnown: " + value + " " +q;
2127 cananian 1.1.2.4 }
2128 cananian 1.1.2.4 public boolean equals(Object o) { return _equals(o); }
2129 cananian 1.1.2.4 private boolean _equals(Object o) {
2130 cananian 1.1.2.4 return (o instanceof xInstanceofResultKnown && super.equals(o) &&
2131 cananian 1.1.2.4 ((xInstanceofResultKnown)o).q == q &&
2132 cananian 1.1.2.4 ((xInstanceofResultKnown)o).tested == tested);
2133 cananian 1.1.2.4 }
2134 cananian 1.1.2.4 public LatticeVal merge(LatticeVal v) {
2135 cananian 1.1.2.4 if (v instanceof xInstanceofResult)
2136 cananian 1.1.2.4 // xInstanceofResultKnown merged with
2137 cananian 1.1.2.4 // xInstanceofResultKnown or xInstanceofResultUnknown
2138 cananian 1.1.2.4 return this._equals(v) ? (LatticeVal)
2139 cananian 1.1.2.4 makeKnown(value!=0) : makeUnknown();
2140 cananian 1.1.2.4 // all others.
2141 cananian 1.1.2.4 return super.merge(v);
2142 cananian 1.1.2.4 }
2143 cananian 1.1.2.5 public boolean isLowerThan(LatticeVal v) {
2144 cananian 1.1.2.5 return !(v instanceof xIntConstant);
2145 cananian 1.1.2.5 }
2146 cananian 1.1.2.4 public xInstanceofResultKnown makeKnown(boolean nvalue) {
2147 cananian 1.1.2.4 return new xInstanceofResultKnown(q,tested,nvalue?1:0);
2148 cananian 1.1.2.4 }
2149 cananian 1.1.2.4 public xInstanceofResultUnknown makeUnknown() {
2150 cananian 1.1.2.4 return new xInstanceofResultUnknown(q,tested);
2151 cananian 1.1.2.4 }
2152 cananian 1.1.2.4 // override renaming functions.
2153 cananian 1.1.2.4 public LatticeVal rename(PHI q, int j) {
2154 cananian 1.1.2.4 for (int i=0; i<q.numPhis(); i++)
2155 cananian 1.1.2.4 if (q.src(i, j)==this.tested)
2156 cananian 1.1.2.4 return new xInstanceofResultKnown(def(), q.dst(i), value);
2157 cananian 1.1.2.4 return this;
2158 cananian 1.1.2.4 }
2159 cananian 1.1.2.4 public LatticeVal rename(SIGMA q, int j) {
2160 cananian 1.1.2.4 for (int i=0; i<q.numSigmas(); i++)
2161 cananian 1.1.2.4 if (q.src(i)==this.tested)
2162 cananian 1.1.2.4 return new xInstanceofResultKnown(def(),q.dst(i, j),value);
2163 cananian 1.1.2.4 return this;
2164 cananian 1.1.2.4 }
2165 cananian 1.1.2.4 }
2166 cananian 1.1.2.4 /** A known boolean value which is the result of an OPER. */
2167 cananian 1.1.2.4 static class xOperBooleanResultKnown extends xIntConstant
2168 cananian 1.1.2.4 implements xOperBooleanResult {
2169 cananian 1.1.2.4 OPER q;
2170 cananian 1.1.2.4 Temp[] operands;
2171 cananian 1.1.2.4 public xOperBooleanResultKnown(OPER q, boolean value) {
2172 cananian 1.1.2.4 this(q, q.operands(), value?1:0);
2173 cananian 1.1.2.4 }
2174 cananian 1.1.2.4 xOperBooleanResultKnown(OPER q, Temp[] operands, long value)
2175 cananian 1.1.2.4 {
2176 cananian 1.1.2.4 super(toInternal(HClass.Boolean),value);
2177 cananian 1.1.2.4 this.q = q;
2178 cananian 1.1.2.4 this.operands = operands;
2179 cananian 1.4.2.1 assert value==0 || value==1;
2180 cananian 1.1.2.4 }
2181 cananian 1.1.2.4 public Temp[] operands() { return operands; }
2182 cananian 1.1.2.4 public OPER def() { return q; }
2183 cananian 1.1.2.4 public String toString() {
2184 cananian 1.1.2.4 return "xOperBooleanResultKnown: " + value + " " +q;
2185 cananian 1.1.2.4 }
2186 cananian 1.1.2.4 public boolean equals(Object o) { return _equals(o); }
2187 cananian 1.1.2.4 private boolean _equals(Object o) {
2188 cananian 1.1.2.4 if (o==this) return true; // common case.
2189 cananian 1.1.2.4 if (!(o instanceof xOperBooleanResultKnown)) return false;
2190 cananian 1.1.2.4 if (!super.equals(o)) return false;
2191 cananian 1.1.2.4 xOperBooleanResultKnown oo = (xOperBooleanResultKnown)o;
2192 cananian 1.1.2.4 if (oo.q != q) return false;
2193 cananian 1.1.2.4 if (oo.operands.length != operands.length) return false;
2194 cananian 1.1.2.4 for (int i=0; i<operands.length; i++)
2195 cananian 1.1.2.4 if (oo.operands[i] != operands[i]) return false;
2196 cananian 1.1.2.1 return true;
2197 cananian 1.1.2.1 }
2198 cananian 1.1.2.4 public LatticeVal merge(LatticeVal v) {
2199 cananian 1.1.2.4 if (v instanceof xOperBooleanResult)
2200 cananian 1.1.2.4 // xOperBooleanResultKnown merged with
2201 cananian 1.1.2.4 // xOperBooleanResultKnown or xOperBooleanResultUnknown
2202 cananian 1.1.2.4 return this._equals(v) ? (LatticeVal)
2203 cananian 1.1.2.4 makeKnown(value!=0) : makeUnknown();
2204 cananian 1.1.2.4 // all others.
2205 cananian 1.1.2.4 return super.merge(v);
2206 cananian 1.1.2.4 }
2207 cananian 1.1.2.5 public boolean isLowerThan(LatticeVal v) {
2208 cananian 1.1.2.5 return !(v instanceof xIntConstant);
2209 cananian 1.1.2.5 }
2210 cananian 1.1.2.4 public xOperBooleanResultKnown makeKnown(boolean nvalue) {
2211 cananian 1.1.2.4 return new xOperBooleanResultKnown(q,operands,nvalue?1:0);
2212 cananian 1.1.2.4 }
2213 cananian 1.1.2.4 public xOperBooleanResultUnknown makeUnknown() {
2214 cananian 1.1.2.4 return new xOperBooleanResultUnknown(q,operands);
2215 cananian 1.1.2.4 }
2216 cananian 1.1.2.4 // override renaming functions.
2217 cananian 1.1.2.4 public LatticeVal rename(PHI q, int j) {
2218 cananian 1.1.2.4 MyTempMap mtm = new MyTempMap();
2219 cananian 1.1.2.4 for (int i=0; i<q.numPhis(); i++)
2220 cananian 1.1.2.4 mtm.put(q.src(i,j), q.dst(i));
2221 cananian 1.1.2.4 return new xOperBooleanResultKnown(def(), mtm.tempMap(operands()),
2222 cananian 1.1.2.4 value);
2223 cananian 1.1.2.4 }
2224 cananian 1.1.2.4 public LatticeVal rename(SIGMA q, int j) {
2225 cananian 1.1.2.4 MyTempMap mtm = new MyTempMap();
2226 cananian 1.1.2.4 for (int i=0; i<q.numSigmas(); i++)
2227 cananian 1.1.2.4 mtm.put(q.src(i), q.dst(i, j));
2228 cananian 1.1.2.4 return new xOperBooleanResultKnown(def(), mtm.tempMap(operands()),
2229 cananian 1.1.2.4 value);
2230 cananian 1.1.2.4 }
2231 cananian 1.1.2.4 private static class MyTempMap extends HashMap implements TempMap {
2232 cananian 1.1.2.4 public Temp tempMap(Temp t) {
2233 pnkfelix 1.1.2.8 return containsKey(t) ? (Temp) super.get(t) : t;
2234 cananian 1.1.2.4 }
2235 cananian 1.1.2.4 public Temp[] tempMap(Temp[] t) {
2236 cananian 1.1.2.4 Temp[] r = new Temp[t.length];
2237 cananian 1.1.2.4 for (int i=0; i<r.length; i++)
2238 cananian 1.1.2.4 r[i] = tempMap(t[i]);
2239 cananian 1.1.2.4 return r;
2240 cananian 1.1.2.4 }
2241 cananian 1.1.2.4 }
2242 cananian 1.1.2.1 }
2243 cananian 1.1.2.1 static class xNullConstant extends xClass implements xConstant {
2244 cananian 1.1.2.1 public xNullConstant() {
2245 cananian 1.1.2.1 super(HClass.Void);
2246 cananian 1.1.2.1 }
2247 cananian 1.1.2.1 public Object constValue() { return null; }
2248 cananian 1.1.2.1 public String toString() {
2249 cananian 1.1.2.1 return "xNullConstant: null";
2250 cananian 1.1.2.1 }
2251 cananian 1.1.2.4 public boolean equals(Object o) { return _equals(o); }
2252 cananian 1.1.2.4 private boolean _equals(Object o) {
2253 cananian 1.1.2.1 return (o instanceof xNullConstant);
2254 cananian 1.1.2.1 }
2255 cananian 1.1.2.4 public LatticeVal merge(LatticeVal v) {
2256 cananian 1.1.2.4 if (this._equals(v)) return new xNullConstant();
2257 cananian 1.1.2.4 return super.merge(v);
2258 cananian 1.1.2.1 }
2259 cananian 1.1.2.5 public boolean isLowerThan(LatticeVal v) {
2260 cananian 1.1.2.5 return !(v instanceof xNullConstant);
2261 cananian 1.1.2.5 }
2262 cananian 1.1.2.1 }
2263 cananian 1.1.2.1 static class xFloatConstant extends xClassExact
2264 cananian 1.1.2.1 implements xConstant {
2265 cananian 1.1.2.1 protected Object value;
2266 cananian 1.1.2.1 public xFloatConstant(HClass type, Object value) {
2267 cananian 1.1.2.1 super(type); this.value = value;
2268 cananian 1.1.2.1 }
2269 cananian 1.1.2.1 public Object constValue() { return value; }
2270 cananian 1.1.2.1 public String toString() {
2271 cananian 1.1.2.1 return "xFloatConstant: " + type + " " + value.toString();
2272 cananian 1.1.2.1 }
2273 cananian 1.1.2.4 public boolean equals(Object o) { return _equals(o); }
2274 cananian 1.1.2.4 private boolean _equals(Object o) {
2275 cananian 1.1.2.1 return (o instanceof xFloatConstant && super.equals(o) &&
2276 cananian 1.1.2.1 ((xFloatConstant)o).value.equals(value));
2277 cananian 1.1.2.1 }
2278 cananian 1.1.2.4 public LatticeVal merge(LatticeVal v) {
2279 cananian 1.1.2.4 if (this._equals(v)) return new xFloatConstant(type, value);
2280 cananian 1.1.2.4 return super.merge(v);
2281 cananian 1.1.2.1 }
2282 cananian 1.1.2.5 public boolean isLowerThan(LatticeVal v) {
2283 cananian 1.1.2.5 return !(v instanceof xFloatConstant);
2284 cananian 1.1.2.5 }
2285 cananian 1.1.2.1 }
2286 cananian 1.1.2.1 static class xStringConstant extends xClassExact
2287 cananian 1.1.2.1 implements xConstant {
2288 cananian 1.1.2.1 protected Object value;
2289 cananian 1.1.2.1 public xStringConstant(HClass type, Object value) {
2290 cananian 1.1.2.1 super(type);
2291 cananian 1.1.2.1 // note that the string constant objects are intern()ed.
2292 cananian 1.1.2.1 // doing this here ensures that evaluating ACMPEQ with constant
2293 cananian 1.1.2.1 // args works correctly.
2294 cananian 1.1.2.1 this.value = ((String)value).intern();
2295 cananian 1.1.2.1 }
2296 cananian 1.1.2.1 public Object constValue() { return value; }
2297 cananian 1.1.2.1 public String toString() {
2298 cananian 1.1.2.1 return "xStringConstant: " +
2299 cananian 1.9 "\"" + harpoon.Util.Util.escape(value.toString()) + "\"";
2300 cananian 1.1.2.1 }
2301 cananian 1.1.2.4 public boolean equals(Object o) { return _equals(o); }
2302 cananian 1.1.2.4 private boolean _equals(Object o) {
2303 cananian 1.1.2.1 return (o instanceof xStringConstant && super.equals(o) &&
2304 cananian 1.1.2.1 ((xStringConstant)o).value.equals(value));
2305 cananian 1.1.2.1 }
2306 cananian 1.1.2.4 public LatticeVal merge(LatticeVal v) {
2307 cananian 1.1.2.4 if (this._equals(v)) return new xStringConstant(type, value);
2308 cananian 1.1.2.4 return super.merge(v);
2309 cananian 1.1.2.5 }
2310 cananian 1.1.2.5 public boolean isLowerThan(LatticeVal v) {
2311 cananian 1.1.2.5 return !(v instanceof xStringConstant);
2312 cananian 1.1.2.1 }
2313 cananian 1.1.2.1 }
2314 cananian 1.1.2.1 static interface xConstant {
2315 cananian 1.1.2.1 public Object constValue();
2316 cananian 1.1.2.1 }
2317 cananian 1.1.2.4 static interface xInstanceofResult {
2318 cananian 1.1.2.4 public Temp tested();
2319 cananian 1.1.2.4 public INSTANCEOF def();
2320 cananian 1.1.2.4 public xInstanceofResultKnown makeKnown(boolean value);
2321 cananian 1.1.2.4 public xInstanceofResultUnknown makeUnknown();
2322 cananian 1.1.2.4 }
2323 cananian 1.1.2.4 static interface xOperBooleanResult {
2324 cananian 1.1.2.4 public Temp[] operands();
2325 cananian 1.1.2.4 public OPER def();
2326 cananian 1.1.2.4 public xOperBooleanResultKnown makeKnown(boolean value);
2327 cananian 1.1.2.4 public xOperBooleanResultUnknown makeUnknown();
2328 cananian 1.1.2.4 }
2329 cananian 1.1.2.1 /////////////////////////////////////////////////////////
2330 cananian 1.1.2.1 // ways to degrade the analysis to collect statistics.
2331 cananian 1.1.2.1 private final Corruptor corruptor = null; // no corruption.
2332 cananian 1.1.2.1 private final boolean useSigmas = true;
2333 cananian 1.1.2.1 /** A <code>Corruptor</code> lets you 'dumb-down' the analysis
2334 cananian 1.1.2.1 * incrementally, so that we can generate numbers showing that
2335 cananian 1.1.2.1 * every step makes it better and better. */
2336 cananian 1.1.2.1 static abstract class Corruptor {
2337 cananian 1.1.2.1 /** make this lattice value worse than we know it to be. */
2338 cananian 1.1.2.1 abstract LatticeVal corrupt(LatticeVal v);
2339 cananian 1.1.2.1 }
2340 cananian 1.1.2.1 static final Corruptor nobitwidth = new Corruptor() {
2341 cananian 1.1.2.1 public LatticeVal corrupt(LatticeVal v) {
2342 cananian 1.1.2.4 if (v!=null && v.toString().startsWith("xBitWidth:"))
2343 cananian 1.1.2.4 return new xClassExact(((xClassExact)v).type);
2344 cananian 1.1.2.1 return v;
2345 cananian 1.1.2.1 }
2346 cananian 1.1.2.1 };
2347 cananian 1.1.2.1 static final Corruptor nofixedarray = new Corruptor() {
2348 cananian 1.1.2.1 public LatticeVal corrupt(LatticeVal v) {
2349 cananian 1.1.2.1 v = nobitwidth.corrupt(v);
2350 cananian 1.1.2.1 if (v instanceof xClassArray)
2351 cananian 1.1.2.1 return new xClassNonNull(((xClassNonNull)v).type);
2352 cananian 1.1.2.1 return v;
2353 cananian 1.1.2.1 }
2354 cananian 1.1.2.1 };
2355 cananian 1.1.2.1 static final Corruptor nonullpointer = new Corruptor() {
2356 cananian 1.1.2.1 public LatticeVal corrupt(LatticeVal v) {
2357 cananian 1.1.2.1 if (v instanceof xClassNonNull)
2358 cananian 1.1.2.1 return new xClass(((xClassNonNull)v).type);
2359 cananian 1.1.2.1 return v;
2360 cananian 1.1.2.1 }
2361 cananian 1.1.2.1 };
2362 cananian 1.1.2.1 static final Corruptor nononint = new Corruptor() {
2363 cananian 1.1.2.1 public LatticeVal corrupt(LatticeVal v) {
2364 cananian 1.1.2.1 v = nonullpointer.corrupt(v);
2365 cananian 1.1.2.1 if (v instanceof xFloatConstant ||
2366 cananian 1.1.2.1 v instanceof xStringConstant ||
2367 cananian 1.1.2.1 (v instanceof xIntConstant && ((xClass)v).type!=HClass.Int))
2368 cananian 1.1.2.1 return new xClass(((xClass)v).type);
2369 cananian 1.1.2.1 return v;
2370 cananian 1.1.2.1 }
2371 cananian 1.1.2.1 };
2372 cananian 1.1.2.14
2373 cananian 1.1.2.9 private static Set parseResource(final Linker l, String resourceName) {
2374 cananian 1.1.2.9 final Set result = new HashSet();
2375 cananian 1.1.2.9 try {
2376 cananian 1.1.2.9 ParseUtil.readResource(resourceName, new ParseUtil.StringParser() {
2377 cananian 1.1.2.9 public void parseString(String s)
2378 cananian 1.1.2.9 throws ParseUtil.BadLineException {
2379 cananian 1.1.2.9 result.add(ParseUtil.parseField(l, s));
2380 cananian 1.1.2.9 }
2381 cananian 1.1.2.9 });
2382 cananian 1.1.2.9 } catch (java.io.IOException ex) {
2383 cananian 1.1.2.9 System.err.println("ERROR READING FIELD ROOTS, SKIPPING REST.");
2384 cananian 1.1.2.9 System.err.println(ex.toString());
2385 cananian 1.1.2.9 }
2386 cananian 1.1.2.9 // done.
2387 cananian 1.1.2.9 return result;
2388 cananian 1.1.2.9 }
2389 cananian 1.2 }