1 cananian 1.1.2.1 // TypeInfo.java, created Thu Sep 10 14:58:21 1998 by cananian
2 cananian 1.1.2.1 // Copyright (C) 1998 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.Analysis.Quads;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.Analysis.UseDef;
7 cananian 1.1.2.1 import harpoon.Analysis.Maps.UseDefMap;
8 cananian 1.1.2.3 import harpoon.ClassFile.HClass;
9 cananian 1.1.2.3 import harpoon.ClassFile.HCodeElement;
10 cananian 1.1.2.3 import harpoon.ClassFile.HMethod;
11 cananian 1.1.2.7 import harpoon.ClassFile.Linker;
12 cananian 1.1.2.3 import harpoon.IR.Quads.Qop;
13 cananian 1.1.2.3 import harpoon.IR.Quads.Quad;
14 cananian 1.1.2.3 import harpoon.IR.Quads.QuadVisitor;
15 cananian 1.1.2.3 import harpoon.IR.Quads.AGET;
16 cananian 1.1.2.3 import harpoon.IR.Quads.ALENGTH;
17 cananian 1.1.2.3 import harpoon.IR.Quads.ANEW;
18 cananian 1.1.2.3 import harpoon.IR.Quads.ASET;
19 cananian 1.1.2.3 import harpoon.IR.Quads.CALL;
20 cananian 1.1.2.3 import harpoon.IR.Quads.CJMP;
21 cananian 1.1.2.3 import harpoon.IR.Quads.COMPONENTOF;
22 cananian 1.1.2.3 import harpoon.IR.Quads.CONST;
23 cananian 1.1.2.3 import harpoon.IR.Quads.GET;
24 cananian 1.1.2.3 import harpoon.IR.Quads.INSTANCEOF;
25 cananian 1.1.2.3 import harpoon.IR.Quads.METHOD;
26 cananian 1.1.2.3 import harpoon.IR.Quads.MOVE;
27 cananian 1.1.2.3 import harpoon.IR.Quads.NEW;
28 cananian 1.1.2.3 import harpoon.IR.Quads.OPER;
29 cananian 1.1.2.3 import harpoon.IR.Quads.PHI;
30 cananian 1.1.2.3 import harpoon.IR.Quads.RETURN;
31 cananian 1.1.2.3 import harpoon.IR.Quads.SET;
32 cananian 1.1.2.3 import harpoon.IR.Quads.SIGMA;
33 cananian 1.1.2.3 import harpoon.IR.Quads.SWITCH;
34 cananian 1.1.2.3 import harpoon.IR.Quads.THROW;
35 cananian 1.1.2.10 import harpoon.IR.Quads.TYPESWITCH;
36 cananian 1.1.2.3 import harpoon.Temp.Temp;
37 cananian 1.1.2.1 import harpoon.Util.Util;
38 cananian 1.1.2.1 import harpoon.Util.Worklist;
39 cananian 1.1.2.11 import harpoon.Util.Collections.WorkSet;
40 cananian 1.1.2.1 import harpoon.Util.HClassUtil;
41 cananian 1.1.2.1
42 cananian 1.1.2.1 import java.util.Vector;
43 cananian 1.1.2.8 import java.util.HashMap;
44 cananian 1.1.2.8 import java.util.Map;
45 cananian 1.1.2.1 /**
46 cananian 1.1.2.1 * <code>TypeInfo</code> is a simple type analysis tool for quad-ssi form.
47 cananian 1.1.2.1 *
48 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
49 cananian 1.5 * @version $Id: TypeInfo.java,v 1.5 2003/07/11 09:38:35 cananian Exp $
50 cananian 1.1.2.1 */
51 cananian 1.1.2.1
52 cananian 1.5 public class TypeInfo implements harpoon.Analysis.Maps.ExactTypeMap<Quad> {
53 cananian 1.5 UseDefMap<Quad> usedef;
54 bdemsky 1.1.2.4 boolean verifierBehavior;
55 cananian 1.1.2.1
56 cananian 1.5 Map<Temp,ExactType> map = new HashMap<Temp,ExactType>();
57 cananian 1.1.2.1
58 cananian 1.1.2.1 /** Creates a <code>TypeInfo</code> analyzer for the specified
59 cananian 1.1.2.12 * <code>HCode</code>, which must be in quad-ssi form.
60 cananian 1.1.2.1 */
61 cananian 1.5 public TypeInfo(harpoon.IR.Quads.Code hc, UseDefMap<Quad> usedef) {
62 cananian 1.1.2.9 this(hc, usedef, false);
63 bdemsky 1.1.2.4 }
64 bdemsky 1.1.2.4
65 bdemsky 1.1.2.4 /** Creates a <code>TypeInfo</code> analyzer for the specified
66 cananian 1.1.2.12 * <code>HCode</code>, which must be in quad-ssi form.
67 cananian 1.1.2.5 * If <code>vBehavior</code> is true, the TypeInfo pass's IQ drops
68 cananian 1.1.2.5 * to the same level as a typical bytecode verifier; i.e. it gathers
69 cananian 1.1.2.5 * no information from instanceof's and such. Because of the IQ
70 cananian 1.1.2.5 * drop, the verifier sometimes can't determine that the operand
71 cananian 1.1.2.5 * of an AGET is really an array; with <code>vBehaviour</code> true
72 cananian 1.1.2.5 * the <code>TypeInfo</code> handles this case gracefully, rather than
73 cananian 1.1.2.5 * failing an assertion.
74 bdemsky 1.1.2.4 */
75 cananian 1.5 public TypeInfo(harpoon.IR.Quads.Code hc, UseDefMap<Quad> usedef, boolean vBehavior) {
76 bdemsky 1.1.2.4 this.usedef = usedef;
77 bdemsky 1.1.2.4 this.verifierBehavior=vBehavior;
78 cananian 1.3.2.1 assert hc.getName().equals(harpoon.IR.Quads.QuadSSI.codename);
79 cananian 1.1.2.1 analyze(hc);
80 cananian 1.1.2.1 }
81 cananian 1.1.2.1
82 cananian 1.1.2.1 /** Creates a <code>TypeInfo</code> analyzer for the specified
83 cananian 1.1.2.12 * <code>HCode</code>, which must be in quad-ssi form.
84 cananian 1.1.2.1 */
85 cananian 1.5 public TypeInfo(harpoon.IR.Quads.Code hc) { this(hc, new UseDef<Quad>()); }
86 cananian 1.1.2.1
87 cananian 1.5 public HClass typeMap(Quad hce, Temp t)
88 cananian 1.1.2.9 throws TypeNotKnownException { return exactType(hce, t).type; }
89 cananian 1.5 public boolean isExactType(Quad hce, Temp t)
90 cananian 1.1.2.9 throws TypeNotKnownException { return exactType(hce, t).isExact; }
91 cananian 1.5 private ExactType exactType(Quad hce, Temp t)
92 cananian 1.1.2.9 throws TypeNotKnownException {
93 cananian 1.5 assert hce!=null : "HCE is null! "+hce+"/"+t;
94 cananian 1.5 assert t!=null : "t is null! "+hce+"/"+t;
95 cananian 1.1.2.9 if (hce==null || t==null) throw new NullPointerException();
96 cananian 1.1.2.9 if (!hasType(hce, t)) throw new TypeNotKnownException(hce, t);
97 cananian 1.5 return map.get(t);
98 cananian 1.1.2.9 }
99 cananian 1.5 private boolean hasType(Quad hce, Temp t) {
100 cananian 1.1.2.9 return map.containsKey(t);
101 cananian 1.1.2.1 }
102 cananian 1.1.2.1
103 cananian 1.1.2.12 private void analyze(harpoon.IR.Quads.Code hc) {
104 cananian 1.5 Quad ql[] = hc.getElements();
105 cananian 1.1.2.1
106 cananian 1.5 WorkSet<Quad> worklist = new WorkSet<Quad>(); // use as FIFO
107 cananian 1.1.2.1 for (int i=0; i<ql.length; i++)
108 cananian 1.1.2.8 worklist.add(ql[i]);
109 cananian 1.1.2.1
110 cananian 1.1.2.1 // hack to handle typecasting:
111 cananian 1.1.2.1 // keep track of booleans defined by instanceof's and acmpeq's.
112 cananian 1.5 Map<Temp,Quad> checkcast = new HashMap<Temp,Quad>();
113 bdemsky 1.1.2.4 if (!verifierBehavior)
114 bdemsky 1.1.2.4 for (int i=0; i<ql.length; i++)
115 bdemsky 1.1.2.4 if (ql[i] instanceof INSTANCEOF ||
116 bdemsky 1.1.2.4 ql[i] instanceof OPER)
117 bdemsky 1.1.2.4 checkcast.put(ql[i].def()[0], ql[i]);
118 cananian 1.1.2.1
119 bdemsky 1.1.2.4 TypeInfoVisitor tiv = new TypeInfoVisitor(hc, checkcast, verifierBehavior);
120 cananian 1.1.2.1 while(!worklist.isEmpty()) {
121 cananian 1.5 Quad q = worklist.removeFirst(); // use as FIFO
122 cananian 1.1.2.1 tiv.modified = false;
123 cananian 1.1.2.2 q.accept(tiv);
124 cananian 1.1.2.1 if (tiv.modified) {
125 cananian 1.1.2.1 Temp[] d = q.def();
126 cananian 1.1.2.1 for (int i=0; i<d.length; i++) {
127 cananian 1.5 Quad[] u = usedef.useMap(hc, d[i]);
128 cananian 1.1.2.1 for (int j=0; j<u.length; j++) {
129 cananian 1.5 worklist.add(u[j]); // only pushes unique quads.
130 cananian 1.1.2.1 }
131 cananian 1.1.2.1 }
132 cananian 1.1.2.1 }
133 cananian 1.1.2.1 }
134 cananian 1.1.2.1 }
135 cananian 1.1.2.1
136 cananian 1.1.2.1 class TypeInfoVisitor extends QuadVisitor {
137 cananian 1.1.2.12 harpoon.IR.Quads.Code hc;
138 cananian 1.1.2.1 boolean modified = false;
139 cananian 1.5 Map<Temp,Quad> checkcast;
140 bdemsky 1.1.2.4 HClass hclassObj;
141 bdemsky 1.1.2.4 boolean verifierBehavior;
142 cananian 1.1.2.7 Linker linker;
143 bdemsky 1.1.2.4
144 cananian 1.5 TypeInfoVisitor(harpoon.IR.Quads.Code hc, Map<Temp,Quad> checkcast, boolean verifierBehavior) {
145 bdemsky 1.1.2.4 this.hc = hc; this.checkcast = checkcast;
146 bdemsky 1.1.2.4 this.verifierBehavior=verifierBehavior;
147 cananian 1.1.2.7 this.linker = hc.getMethod().getDeclaringClass().getLinker();
148 bdemsky 1.1.2.4 if (verifierBehavior)
149 cananian 1.1.2.7 this.hclassObj=linker.forName("java.lang.Object");
150 bdemsky 1.1.2.4 }
151 cananian 1.1.2.1
152 cananian 1.1.2.1 public void visit(Quad q) { modified = false; }
153 cananian 1.1.2.1
154 cananian 1.1.2.1 public void visit(AGET q) {
155 cananian 1.1.2.9 if (!hasType(q, q.objectref())) { modified=false; return; }
156 cananian 1.1.2.1 HClass ty = typeMap(q, q.objectref());
157 cananian 1.1.2.9 if (ty==HClass.Void) { modified=false; return; }
158 bdemsky 1.1.2.4 if (!verifierBehavior) {
159 cananian 1.3.2.1 assert ty.isArray();
160 cananian 1.1.2.9 modified = merge(q, q.dst(),
161 cananian 1.1.2.9 inexact(toInternal(ty.getComponentType())));
162 bdemsky 1.1.2.4 }
163 bdemsky 1.1.2.4 else
164 cananian 1.1.2.9 modified = merge(q, q.dst(),
165 cananian 1.1.2.9 inexact(toInternal(ty.isArray() ?
166 cananian 1.1.2.9 ty.getComponentType() :
167 cananian 1.1.2.9 hclassObj)));
168 cananian 1.1.2.1 }
169 cananian 1.1.2.1 public void visit(ALENGTH q) {
170 cananian 1.1.2.9 modified = merge(q, q.dst(), exact(HClass.Int));
171 cananian 1.1.2.1 }
172 cananian 1.1.2.1 public void visit(ANEW q) {
173 cananian 1.1.2.9 modified = merge(q, q.dst(), exact(q.hclass()));
174 cananian 1.1.2.1 }
175 cananian 1.1.2.1 public void visit(CALL q) {
176 cananian 1.1.2.1 boolean r1 = (q.retval()==null) ? false:
177 cananian 1.1.2.9 merge(q, q.retval(),
178 cananian 1.1.2.9 inexact(toInternal(q.method().getReturnType())));
179 cananian 1.1.2.1 // XXX specify class of exception better.
180 cananian 1.1.2.9 boolean r2 = merge(q,q.retex(),
181 cananian 1.1.2.9 inexact(linker.forName("java.lang.Throwable")));
182 cananian 1.1.2.1 modified = r1 || r2;
183 cananian 1.1.2.3
184 cananian 1.1.2.3 // deal with SIGMA functions in CALL
185 cananian 1.1.2.3 for (int i=0; i<q.numSigmas(); i++) {
186 cananian 1.1.2.3 if (q.src(i)==null) continue;
187 cananian 1.1.2.9 if (!hasType(q, q.src(i))) continue;
188 cananian 1.1.2.9 ExactType ty = exactType(q, q.src(i));
189 cananian 1.1.2.3 for (int j=0; j<q.arity(); j++)
190 cananian 1.1.2.3 if (merge(q, q.dst(i,j), ty))
191 cananian 1.1.2.3 modified = true;
192 cananian 1.1.2.3 }
193 cananian 1.1.2.1 }
194 cananian 1.1.2.1 public void visit(COMPONENTOF q) {
195 cananian 1.1.2.9 modified = merge(q, q.dst(), exact(toInternal(HClass.Boolean)));
196 cananian 1.1.2.1 }
197 cananian 1.1.2.1 public void visit(CONST q) {
198 cananian 1.1.2.9 modified = merge(q, q.dst(), exact(toInternal(q.type())));
199 cananian 1.1.2.1 }
200 cananian 1.1.2.1 public void visit(GET q) {
201 cananian 1.1.2.9 modified = merge(q, q.dst(),
202 cananian 1.1.2.9 inexact(toInternal(q.field().getType())));
203 cananian 1.1.2.1 }
204 cananian 1.1.2.1 public void visit(INSTANCEOF q) {
205 cananian 1.1.2.9 modified = merge(q, q.dst(), exact(toInternal(HClass.Boolean)));
206 cananian 1.1.2.1 }
207 cananian 1.1.2.1 public void visit(METHOD q) {
208 cananian 1.1.2.1 boolean r = false;
209 cananian 1.1.2.1 HMethod m = hc.getMethod();
210 cananian 1.1.2.1 HClass[] pt = m.getParameterTypes();
211 cananian 1.1.2.1 int offset = m.isStatic()?0:1;
212 cananian 1.1.2.1 for (int i=offset; i<q.paramsLength(); i++)
213 cananian 1.1.2.9 if (merge(q, q.params(i), inexact(toInternal(pt[i-offset]))))
214 cananian 1.1.2.1 r = true;
215 cananian 1.1.2.1 if (!m.isStatic())
216 cananian 1.1.2.9 r = merge(q, q.params(0), inexact(m.getDeclaringClass())) || r;
217 cananian 1.1.2.1 modified = r;
218 cananian 1.1.2.1 }
219 cananian 1.1.2.1 public void visit(MOVE q) {
220 cananian 1.1.2.9 if (!hasType(q, q.src())) { modified = false; return; }
221 cananian 1.1.2.9 modified = merge(q, q.dst(), exactType(q, q.src()));
222 cananian 1.1.2.1 }
223 cananian 1.1.2.1 public void visit(NEW q) {
224 cananian 1.1.2.9 modified = merge(q, q.dst(), exact(q.hclass()));
225 cananian 1.1.2.1 }
226 cananian 1.1.2.1 public void visit(OPER q) {
227 cananian 1.1.2.9 modified = merge(q, q.dst(), exact(toInternal(q.evalType())));
228 cananian 1.1.2.1 }
229 cananian 1.1.2.1 public void visit(PHI q) {
230 cananian 1.1.2.1 boolean r = false;
231 cananian 1.1.2.1 for (int i=0; i<q.numPhis(); i++)
232 cananian 1.1.2.1 for (int j=0; j<q.arity(); j++) {
233 cananian 1.1.2.1 if (q.src(i,j)==null) continue;
234 cananian 1.1.2.9 if (!hasType(q, q.src(i,j))) continue;
235 cananian 1.1.2.9 if (merge(q, q.dst(i), exactType(q, q.src(i,j))))
236 cananian 1.1.2.1 r = true;
237 cananian 1.1.2.1 }
238 cananian 1.1.2.1 modified = r;
239 cananian 1.1.2.1 }
240 cananian 1.1.2.1 public void visit(SIGMA q) {
241 cananian 1.1.2.1 boolean r = false;
242 cananian 1.1.2.1 for (int i=0; i<q.numSigmas(); i++) {
243 cananian 1.1.2.1 if (q.src(i)==null) continue;
244 cananian 1.1.2.9 if (!hasType(q, q.src(i))) continue;
245 cananian 1.1.2.9 ExactType ty = exactType(q, q.src(i));
246 cananian 1.1.2.1 for (int j=0; j<q.arity(); j++)
247 cananian 1.1.2.1 if (merge(q, q.dst(i,j), ty))
248 cananian 1.1.2.1 r = true;
249 cananian 1.1.2.10 }
250 cananian 1.1.2.10 modified = r;
251 cananian 1.1.2.10 }
252 cananian 1.1.2.10 /* TYPESWITCH: we know the type of the index exactly */
253 cananian 1.1.2.10 public void visit(TYPESWITCH q) {
254 cananian 1.1.2.10 boolean r = false;
255 cananian 1.1.2.10 for (int i=0; i<q.numSigmas(); i++) {
256 cananian 1.1.2.10 if (q.src(i)==null) continue;
257 cananian 1.1.2.10 if (!hasType(q, q.src(i))) continue;
258 cananian 1.1.2.10 ExactType ty = exactType(q, q.src(i));
259 cananian 1.1.2.10 for (int j=0; j<q.arity(); j++)
260 cananian 1.1.2.10 if (q.src(i) == q.index() && j<q.keysLength())
261 cananian 1.1.2.10 // we know narrower type.
262 cananian 1.1.2.10 r= merge(q, q.dst(i, j),inexact(q.keys(j))) || r;
263 cananian 1.1.2.10 else
264 cananian 1.1.2.10 r= merge(q, q.dst(i,j), ty) || r;
265 cananian 1.1.2.1 }
266 cananian 1.1.2.1 modified = r;
267 cananian 1.1.2.1 }
268 cananian 1.1.2.1 /* CJMP should actually somehow split and not merge types,
269 cananian 1.1.2.1 i.e. use the information at branch site to find narrower types? */
270 cananian 1.1.2.1 public void visit(CJMP q) {
271 cananian 1.1.2.1 // special case typecasting. (CHECKCAST in bytecode)
272 cananian 1.1.2.1 // special case comparisons against NULL.
273 cananian 1.1.2.1 INSTANCEOF idef = null; // CJMP test is from this INSTANCEOF
274 cananian 1.1.2.1 OPER odef = null; // CJMP test is from this OPER
275 cananian 1.5 Quad def = checkcast.get(q.test());
276 cananian 1.1.2.1 if (def instanceof INSTANCEOF) idef = (INSTANCEOF)def;
277 cananian 1.1.2.1 if (def instanceof OPER) odef = (OPER)def;
278 cananian 1.1.2.1
279 cananian 1.1.2.1 boolean r = false;
280 cananian 1.1.2.1 for (int i=0; i<q.numSigmas(); i++) {
281 cananian 1.1.2.1 if (q.src(i)==null) continue;
282 cananian 1.1.2.9 if (!hasType(q, q.src(i))) continue;
283 cananian 1.1.2.9 ExactType ty = exactType(q, q.src(i));
284 cananian 1.1.2.1 for (int j=0; j<q.arity(); j++) {
285 cananian 1.1.2.1 if (j==1) { // sometimes we gain info on true side of cjmp
286 cananian 1.1.2.1 if (idef != null && idef.src() == q.src(i)) {
287 cananian 1.1.2.1 // test from INSTANCEOF. we know class if true.
288 cananian 1.1.2.9 r= merge(q,q.dst(i,j),inexact(idef.hclass())) || r;
289 cananian 1.1.2.1 continue;
290 cananian 1.1.2.1 }
291 cananian 1.1.2.1 if (odef != null && odef.opcode()==Qop.ACMPEQ) {
292 cananian 1.1.2.9 try { // check to be sure we've got enough info:
293 cananian 1.1.2.1 HClass left = typeMap(odef, odef.operands(0));
294 cananian 1.1.2.1 HClass right= typeMap(odef, odef.operands(1));
295 cananian 1.1.2.1 // ACMPEQ. Types are identical if true.
296 cananian 1.1.2.1 if (odef.operands(0) == q.src(i) &&
297 cananian 1.1.2.1 right == HClass.Void) {
298 cananian 1.1.2.9 r = merge(q, q.dst(i,j), exact(right)) || r;
299 cananian 1.1.2.1 continue;
300 cananian 1.1.2.1 }
301 cananian 1.1.2.1 if (odef.operands(1) == q.src(i) &&
302 cananian 1.1.2.1 left == HClass.Void) {
303 cananian 1.1.2.9 r = merge(q, q.dst(i,j), exact(left)) || r;
304 cananian 1.1.2.1 continue;
305 cananian 1.1.2.1 }
306 cananian 1.1.2.9 } catch (TypeNotKnownException tnke) { continue; }
307 cananian 1.1.2.1 }
308 cananian 1.1.2.1 }
309 cananian 1.1.2.1 // fall back
310 cananian 1.1.2.1 r = merge(q, q.dst(i,j), ty) || r;
311 cananian 1.1.2.1 }
312 cananian 1.1.2.1 }
313 cananian 1.1.2.1 modified = r;
314 cananian 1.1.2.1 }
315 cananian 1.1.2.1 }
316 cananian 1.1.2.1
317 cananian 1.1.2.1 HClass toInternal(HClass c) {
318 cananian 1.1.2.1 if (c.equals(HClass.Byte) || c.equals(HClass.Short) ||
319 cananian 1.1.2.1 c.equals(HClass.Char) || c.equals(HClass.Boolean))
320 cananian 1.1.2.1 return HClass.Int;
321 cananian 1.1.2.1 return c;
322 cananian 1.1.2.1 }
323 cananian 1.1.2.9 /* utility */
324 cananian 1.1.2.9 ExactType exact(HClass c) { return new ExactType(c, true); }
325 cananian 1.1.2.9 ExactType inexact(HClass c) { return new ExactType(c, false); }
326 cananian 1.1.2.9
327 cananian 1.5 boolean merge(Quad hce, Temp t, ExactType newType) {
328 cananian 1.1.2.9 if (!hasType(hce, t)) { map.put(t, newType); return true; }
329 cananian 1.5 ExactType oldType = map.get(t);
330 cananian 1.1.2.9 if (oldType.equals(newType)) return false;
331 cananian 1.1.2.1 // special case 'Void' HClass, which is used for null constants.
332 cananian 1.1.2.9 if (oldType.type==HClass.Void && newType.type != HClass.Void) {
333 cananian 1.1.2.1 map.put(t, newType); return true;
334 cananian 1.1.2.9 } else if (newType.type == HClass.Void)
335 cananian 1.1.2.1 return false;
336 cananian 1.1.2.1
337 cananian 1.1.2.1 // handle object types (possibly arrays)
338 cananian 1.1.2.9 HClass merged = HClassUtil.commonParent(oldType.type, newType.type);
339 cananian 1.1.2.1 // if the merged value is different from the old value, update...
340 cananian 1.1.2.9 if (merged==oldType.type) return false;
341 cananian 1.1.2.9 map.put(t, new ExactType(merged, false/* merged type is not exact*/));
342 cananian 1.1.2.1 return true;
343 cananian 1.1.2.1 }
344 cananian 1.1.2.1 }
345 bdemsky 1.1.2.4
346 cananian 1.2