1 cananian 1.1.2.1 // DefiniteInitOracle.java, created Mon Nov 5 16:14:29 2001 by cananian
2 cananian 1.1.2.1 // Copyright (C) 2000 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.Analysis.Quads;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.Analysis.ClassHierarchy;
7 cananian 1.1.2.1 import harpoon.Analysis.DomTree;
8 cananian 1.1.2.1 import harpoon.ClassFile.HClass;
9 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
10 cananian 1.1.2.1 import harpoon.ClassFile.HCodeElement;
11 cananian 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
12 cananian 1.1.2.1 import harpoon.ClassFile.HConstructor;
13 cananian 1.1.2.1 import harpoon.ClassFile.HField;
14 cananian 1.1.2.1 import harpoon.ClassFile.HMethod;
15 cananian 1.1.2.1 import harpoon.IR.Quads.CALL;
16 cananian 1.1.2.5 import harpoon.IR.Quads.Edge;
17 cananian 1.1.2.1 import harpoon.IR.Quads.METHOD;
18 cananian 1.1.2.1 import harpoon.IR.Quads.MOVE;
19 cananian 1.1.2.1 import harpoon.IR.Quads.PHI;
20 cananian 1.1.2.1 import harpoon.IR.Quads.Quad;
21 cananian 1.1.2.5 import harpoon.IR.Quads.QuadFactory;
22 cananian 1.1.2.1 import harpoon.IR.Quads.QuadVisitor;
23 cananian 1.1.2.1 import harpoon.IR.Quads.RETURN;
24 cananian 1.1.2.1 import harpoon.IR.Quads.SET;
25 cananian 1.1.2.1 import harpoon.IR.Quads.SIGMA;
26 cananian 1.5 import net.cscott.jutil.AggregateSetFactory;
27 cananian 1.5 import net.cscott.jutil.GenericMultiMap;
28 cananian 1.5 import net.cscott.jutil.MultiMap;
29 cananian 1.1.2.6 import harpoon.Util.Util;
30 cananian 1.1.2.1
31 cananian 1.1.2.1 import java.util.Arrays;
32 cananian 1.1.2.1 import java.util.Collections;
33 cananian 1.1.2.3 import java.util.HashMap;
34 cananian 1.1.2.1 import java.util.HashSet;
35 cananian 1.1.2.1 import java.util.Iterator;
36 cananian 1.1.2.1 import java.util.List;
37 cananian 1.1.2.3 import java.util.Map;
38 cananian 1.1.2.1 import java.util.Set;
39 cananian 1.1.2.1
40 cananian 1.1.2.1 /**
41 cananian 1.1.2.1 * A <code>DefiniteInitOracle</code> tells you whether a given
42 cananian 1.1.2.1 * field is "definitely initialized" before control flow leaves
43 cananian 1.1.2.5 * every constructor of its declaring class. A field is not
44 cananian 1.1.2.5 * considered to be "definitely initialized" if it "may" be read
45 cananian 1.1.2.5 * before its definite initialization point.
46 cananian 1.1.2.1 *
47 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
48 cananian 1.6 * @version $Id: DefiniteInitOracle.java,v 1.6 2004/02/08 03:20:10 cananian Exp $
49 cananian 1.1.2.1 */
50 cananian 1.1.2.1 public class DefiniteInitOracle {
51 cananian 1.1.2.5 private static final boolean DEBUG=true;
52 cananian 1.1.2.3 final HCodeFactory hcf;
53 cananian 1.1.2.1 final ClassHierarchy ch;
54 cananian 1.1.2.1 final Set notDefinitelyInitialized = new HashSet();
55 cananian 1.1.2.1
56 cananian 1.1.2.1 /** Queries the <code>DefiniteInitOracle</code>; returns <code>true</code>
57 cananian 1.1.2.1 * iff every constructor for the declaring class of <code>hf</code>
58 cananian 1.1.2.1 * *must* define the field before any reference to the field is made.
59 cananian 1.1.2.1 */
60 cananian 1.1.2.1 public boolean isDefinitelyInitialized(HField hf) {
61 cananian 1.1.2.1 if (hf.isStatic()) return false; // XXX: would need to look at <clinit>
62 cananian 1.1.2.1 if (!ch.instantiatedClasses().contains(hf.getDeclaringClass()))
63 cananian 1.1.2.1 return false; // never instantiated; thus not def. initialized.
64 cananian 1.1.2.1 return !notDefinitelyInitialized.contains(hf);
65 cananian 1.1.2.1 }
66 cananian 1.1.2.1 /** Creates a <code>DefiniteInitOracle</code> which will use
67 cananian 1.1.2.1 * the given code factory and hierarchy approximation. For best
68 cananian 1.1.2.1 * results, the code factory should produce SSI or SSA form. */
69 cananian 1.1.2.1 public DefiniteInitOracle(HCodeFactory hcf, ClassHierarchy ch) {
70 cananian 1.1.2.3 this.hcf = hcf;
71 cananian 1.1.2.1 this.ch = ch;
72 cananian 1.1.2.5 this.cg = new CallGraphImpl(ch, hcf);
73 cananian 1.1.2.5 this.fso = new FieldSyncOracle(hcf, ch, cg);
74 cananian 1.1.2.1 // for each constructor:
75 cananian 1.6 for (Object hmO : ch.callableMethods()) {
76 cananian 1.6 HMethod hm = (HMethod) hmO;
77 cananian 1.1.2.2 if (!isConstructor(hm)) continue;
78 cananian 1.1.2.3 Set di = getNotDefInit(hm);
79 cananian 1.1.2.3 notDefinitelyInitialized.addAll(di);
80 cananian 1.1.2.3 }
81 cananian 1.1.2.4 // free memory.
82 cananian 1.1.2.4 fso=null;
83 cananian 1.1.2.5 cg=null;
84 cananian 1.1.2.4 ndiCache=null;
85 cananian 1.1.2.3 // done!
86 cananian 1.1.2.5 if (DEBUG) { // debugging:
87 cananian 1.1.2.5 System.out.println("DEFINITELY INITIALIZED FIELDS:");
88 cananian 1.6 for (Object hcO : ch.classes()) {
89 cananian 1.6 HClass hc = (HClass) hcO;
90 cananian 1.6 for (Object hfO : hc.getDeclaredFields()) {
91 cananian 1.6 HField hf = (HField) hfO;
92 cananian 1.1.2.5 if (isDefinitelyInitialized(hf))
93 cananian 1.1.2.5 System.out.println(" "+hf);
94 cananian 1.1.2.5 }
95 cananian 1.1.2.5 }
96 cananian 1.1.2.5 System.out.println("------------------------------");
97 cananian 1.1.2.5 }
98 cananian 1.1.2.3 }
99 cananian 1.1.2.4
100 cananian 1.1.2.4 // only used during analysis; clear afterwards
101 cananian 1.1.2.4 FieldSyncOracle fso;
102 cananian 1.1.2.5 CallGraph cg;
103 cananian 1.1.2.4 Map ndiCache = new HashMap();
104 cananian 1.1.2.4
105 cananian 1.1.2.3 Set getNotDefInit(HMethod hm) {
106 cananian 1.1.2.3 if (!ndiCache.containsKey(hm)) {
107 cananian 1.1.2.3 Set notDefinitelyInitialized = new HashSet();
108 cananian 1.1.2.1 HCode hc = hcf.convert(hm);
109 cananian 1.3.2.1 assert hc!=null : hm;
110 cananian 1.1.2.1 // compute dominator tree.
111 cananian 1.1.2.1 DomTree dt = new DomTree(hc, false);
112 cananian 1.1.2.5 // compute MayReadOracle
113 cananian 1.1.2.5 MayReadOracle mro = new MayReadOracle(hc, fso, cg,
114 cananian 1.1.2.8 hm.getDeclaringClass(),
115 cananian 1.1.2.8 true/*special handling!*/);
116 cananian 1.1.2.6 // compute MustParamOracle (to find variables which must contain
117 cananian 1.1.2.6 // 'this')
118 cananian 1.1.2.6 MustParamOracle mpo = new MustParamOracle(hc);
119 cananian 1.1.2.1 // make analysis results cache.
120 cananian 1.1.2.1 MultiMap cache = new GenericMultiMap(new AggregateSetFactory());
121 cananian 1.1.2.1 // for each exit point:
122 cananian 1.1.2.5 for (Iterator it2=findExitPoints(hc).iterator(); it2.hasNext(); ) {
123 cananian 1.1.2.1 // recursively determine set of 'definitely initialized'
124 cananian 1.1.2.1 // fields.
125 cananian 1.1.2.1 Set definit = findDefInit((HCodeElement)it2.next(),
126 cananian 1.1.2.6 dt, mpo, mro, cache);
127 cananian 1.1.2.1 // add any fields which are *not* definitely initialized to
128 cananian 1.1.2.1 // our set.
129 cananian 1.6 for (Object hfO : hm.getDeclaringClass().getDeclaredFields()) {
130 cananian 1.6 HField hf = (HField) hfO;
131 cananian 1.1.2.1 if (hf.isStatic()) continue;
132 cananian 1.1.2.1 if (definit.contains(hf)) continue; // definitely init'd
133 cananian 1.1.2.1 // not definitely init'd!
134 cananian 1.1.2.1 notDefinitelyInitialized.add(hf);
135 cananian 1.1.2.1 }
136 cananian 1.1.2.1 }
137 cananian 1.1.2.3 // okay, cache this!
138 cananian 1.1.2.3 ndiCache.put
139 cananian 1.1.2.3 (hm, Collections.unmodifiableSet(notDefinitelyInitialized));
140 cananian 1.1.2.1 }
141 cananian 1.1.2.3 return (Set) ndiCache.get(hm);
142 cananian 1.1.2.1 }
143 cananian 1.1.2.2 /** return a conservative approximation to whether this is a constructor
144 cananian 1.1.2.2 * or not. it's always safe to return true. */
145 cananian 1.1.2.2 boolean isConstructor(HMethod hm) {
146 cananian 1.1.2.2 // this is tricky, because we want split constructors to count, too,
147 cananian 1.1.2.2 // even though renamed constructors (such as generated by initcheck,
148 cananian 1.1.2.2 // for instance) won't always be instanceof HConstructor. Look
149 cananian 1.1.2.2 // for names starting with '<init>', as well.
150 cananian 1.1.2.2 if (hm instanceof HConstructor) return true;
151 cananian 1.1.2.2 if (hm.getName().startsWith("<init>")) return true;
152 cananian 1.1.2.2 // XXX: what about methods generated by RuntimeMethod Cloner?
153 cananian 1.1.2.2 // we could try methods ending with <init>, but then the
154 cananian 1.1.2.2 // declaringclass information would be wrong.
155 cananian 1.1.2.2 //if (hm.getName().endsWidth("<init>")) return true;//not safe yet.
156 cananian 1.1.2.2 return false;
157 cananian 1.1.2.2 }
158 cananian 1.1.2.3 /** Is this a 'this' constructor? Safe to return false if unsure. */
159 cananian 1.1.2.3 boolean isThisConstructor(HMethod hm, HCodeElement me) {
160 cananian 1.1.2.3 return isConstructor(hm) && // assumes this method is precise.
161 cananian 1.1.2.3 hm.getDeclaringClass().equals
162 cananian 1.1.2.3 (((Quad)me).getFactory().getMethod().getDeclaringClass());
163 cananian 1.1.2.3 }
164 cananian 1.1.2.3 /** Is this a super constructor? Safe to return false if unsure. */
165 cananian 1.1.2.3 boolean isSuperConstructor(HMethod hm, HCodeElement me) {
166 cananian 1.1.2.3 return isConstructor(hm) && // assumes this method is precise.
167 cananian 1.1.2.3 hm.getDeclaringClass().equals
168 cananian 1.1.2.3 (((Quad)me).getFactory().getMethod().getDeclaringClass()
169 cananian 1.1.2.3 .getSuperclass());
170 cananian 1.1.2.3 }
171 cananian 1.1.2.1
172 cananian 1.1.2.5 Set findExitPoints(HCode hc) {
173 cananian 1.1.2.5 // exit points are returns.
174 cananian 1.1.2.5 Set exits = new HashSet();
175 cananian 1.1.2.5 for (Iterator it=hc.getElementsI(); it.hasNext(); ) {
176 cananian 1.1.2.5 Quad q = (Quad) it.next();
177 cananian 1.1.2.5 if (q instanceof RETURN)
178 cananian 1.1.2.5 exits.add(q);
179 cananian 1.1.2.4 }
180 cananian 1.1.2.5 return Collections.unmodifiableSet(exits);
181 cananian 1.1.2.1 }
182 cananian 1.1.2.1 Set findDefInit(HCodeElement exit,
183 cananian 1.1.2.6 DomTree dt, MustParamOracle mpo, MayReadOracle mro,
184 cananian 1.1.2.5 MultiMap cache) {
185 cananian 1.1.2.1 return Collections.unmodifiableSet
186 cananian 1.1.2.6 (getDefBefore(exit, dt, mpo, mro, cache));
187 cananian 1.1.2.1 }
188 cananian 1.1.2.1 private Set getDefBefore(HCodeElement hce,
189 cananian 1.1.2.6 DomTree dt, MustParamOracle mpo,
190 cananian 1.1.2.6 MayReadOracle mro, MultiMap cache) {
191 cananian 1.1.2.1 if (!cache.containsKey(hce)) {
192 cananian 1.1.2.1 // get immediate dominator.
193 cananian 1.1.2.1 HCodeElement idom = dt.idom(hce);
194 cananian 1.1.2.1 if (idom!=null) { // if this *has* an immediate dominator...
195 cananian 1.1.2.1 // get *its* definite initializations.
196 cananian 1.1.2.6 Set definit = getDefBefore(idom, dt, mpo, mro, cache);
197 cananian 1.1.2.1 // all of these are also definitely initialized at this point.
198 cananian 1.1.2.1 cache.addAll(hce, definit);
199 cananian 1.1.2.5 // collect set of reads before this quad.
200 cananian 1.1.2.5 Set readBefore = new HashSet();
201 cananian 1.1.2.5 Edge[] prevEdges = ((Quad)hce).prevEdge();
202 cananian 1.1.2.5 for (int i=0; i < prevEdges.length; i++)
203 cananian 1.1.2.5 readBefore.addAll(mro.mayReadAt(prevEdges[i]));
204 cananian 1.1.2.1 // is the idom itself an initialization?
205 cananian 1.1.2.1 if (idom instanceof SET) {
206 cananian 1.1.2.1 SET q = (SET) idom;
207 cananian 1.1.2.1 if (q.objectref()!=null &&
208 cananian 1.1.2.6 mpo.isMustParam(q.objectref()) &&
209 cananian 1.1.2.6 mpo.whichMustParam(q.objectref())==0/*'this'*/) {
210 cananian 1.1.2.5 // not a definite init if this field can be read before
211 cananian 1.1.2.5 if (!readBefore.contains(q.field()))
212 cananian 1.1.2.5 // baby! add this to the definitely-init'd set!
213 cananian 1.1.2.5 cache.add(hce, q.field());
214 cananian 1.1.2.3 }
215 cananian 1.1.2.3 } else if (idom instanceof CALL) {
216 cananian 1.1.2.3 CALL q = (CALL) idom;
217 cananian 1.1.2.3 // could this be a 'this' constructor?
218 cananian 1.1.2.3 if (isThisConstructor(q.method(), q)) {
219 cananian 1.1.2.5 // add all the definitely-initialized vars which
220 cananian 1.1.2.5 // have not been read-before.
221 cananian 1.1.2.3 Set ndi = getNotDefInit(q.method());
222 cananian 1.1.2.3 HClass hc = q.method().getDeclaringClass(); // 'this'
223 cananian 1.6 for (Object hfO : hc.getDeclaredFields()) {
224 cananian 1.6 HField hf = (HField) hfO;
225 cananian 1.1.2.3 if (hf.isStatic()) continue;
226 cananian 1.1.2.3 if (ndi.contains(hf)) continue; // not def init'd
227 cananian 1.1.2.5 if (!readBefore.contains(hf))
228 cananian 1.1.2.5 cache.add(hce, hf); // def init'd!
229 cananian 1.1.2.3 }
230 cananian 1.1.2.1 }
231 cananian 1.1.2.1 }
232 cananian 1.1.2.1 }
233 cananian 1.1.2.1 // done.
234 cananian 1.1.2.1 }
235 cananian 1.1.2.1 return (Set) cache.getValues(hce);
236 cananian 1.1.2.1 }
237 cananian 1.2 }