1 cananian 1.1.2.1 // MayReadOracle.java, created Wed Nov 7 10:38:43 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.ClassFile.HClass;
7 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
8 cananian 1.1.2.3 import harpoon.ClassFile.HConstructor;
9 cananian 1.1.2.1 import harpoon.ClassFile.HField;
10 cananian 1.1.2.1 import harpoon.ClassFile.HMethod;
11 cananian 1.1.2.1 import harpoon.IR.Quads.CALL;
12 cananian 1.1.2.1 import harpoon.IR.Quads.Edge;
13 cananian 1.1.2.1 import harpoon.IR.Quads.GET;
14 cananian 1.1.2.1 import harpoon.IR.Quads.HEADER;
15 cananian 1.1.2.1 import harpoon.IR.Quads.PHI;
16 cananian 1.1.2.1 import harpoon.IR.Quads.Quad;
17 cananian 1.1.2.1 import harpoon.IR.Quads.QuadVisitor;
18 cananian 1.1.2.1 import harpoon.IR.Quads.RETURN;
19 cananian 1.1.2.1 import harpoon.IR.Quads.SIGMA;
20 cananian 1.1.2.1 import harpoon.IR.Quads.THROW;
21 cananian 1.5 import net.cscott.jutil.DisjointSet;
22 cananian 1.1.2.1 import harpoon.Util.Util;
23 cananian 1.5 import net.cscott.jutil.WorkSet;
24 cananian 1.5 import net.cscott.jutil.AggregateSetFactory;
25 cananian 1.5 import net.cscott.jutil.SetFactory;
26 cananian 1.1.2.1
27 cananian 1.1.2.1 import java.util.Collections;
28 cananian 1.1.2.1 import java.util.HashMap;
29 cananian 1.1.2.1 import java.util.HashSet;
30 cananian 1.1.2.1 import java.util.Iterator;
31 cananian 1.1.2.1 import java.util.Map;
32 cananian 1.1.2.1 import java.util.Set;
33 cananian 1.1.2.1
34 cananian 1.1.2.1 /**
35 cananian 1.1.2.1 * A <code>MayReadOracle</code> tells you which fields of a given
36 cananian 1.1.2.1 * class 'may' be read on the given edge.
37 cananian 1.1.2.1 *
38 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
39 cananian 1.5 * @version $Id: MayReadOracle.java,v 1.5 2004/02/08 01:53:14 cananian Exp $
40 cananian 1.1.2.1 */
41 cananian 1.1.2.1 public class MayReadOracle {
42 cananian 1.1.2.1 final Map results = new HashMap();
43 cananian 1.1.2.1 final DisjointSet aliasMap = new DisjointSet();
44 cananian 1.1.2.1
45 cananian 1.1.2.1 /** Returns the set of fields possibly-read before edge <code>e</code>
46 cananian 1.1.2.1 * is executed. The edge must belong to the <code>HCode</code>
47 cananian 1.1.2.1 * given to this class' constructor. */
48 cananian 1.1.2.1 public Set mayReadAt(Edge e) {
49 cananian 1.1.2.1 EdgeProp ep = (EdgeProp) results.get(aliasMap.find(e));
50 cananian 1.3.2.1 assert ep!=null : e;
51 cananian 1.1.2.1 return Collections.unmodifiableSet(ep.reads);
52 cananian 1.1.2.1 }
53 cananian 1.1.2.1
54 cananian 1.1.2.1 /** Creates a <code>MayReadOracle</code> using the quad-ssi representation
55 cananian 1.1.2.1 * <code>hc</code> of some method and global information about read fields
56 cananian 1.1.2.1 * provided by <code>fso</code>. We will return results for only
57 cananian 1.1.2.1 * fields declared by class <code>which</code>, unless <code>which</code>
58 cananian 1.1.2.3 * is null, in which case we'll return results for all fields.
59 cananian 1.1.2.3 * If <code>specialHandlingForConstructors</code> is <code>true</code>,
60 cananian 1.1.2.3 * then when analyzing a constructor we will only consider fields of
61 cananian 1.1.2.3 * objects which *may* be <code>this</code> (parameter 0 of the
62 cananian 1.1.2.3 * constructor) as reads. This is useful if we are trying to determine
63 cananian 1.1.2.3 * whether a field is read before it is defined in a constructor,
64 cananian 1.1.2.3 * for example. With <code>specialHandlingForConstructors</code> equal
65 cananian 1.1.2.3 * to <code>false</code>, no reads are ignored.
66 cananian 1.1.2.3 */
67 cananian 1.1.2.1 public MayReadOracle(HCode hc, FieldSyncOracle fso,
68 cananian 1.1.2.3 CallGraph cg, HClass which,
69 cananian 1.1.2.3 boolean specialHandlingForConstructors) {
70 cananian 1.1.2.3 // we only need a mustparamoracle if special handling and hc
71 cananian 1.1.2.3 // corresponds to a constructor.
72 cananian 1.1.2.3 MustParamOracle mpo = null;
73 cananian 1.1.2.3 if (specialHandlingForConstructors && isConstructor(hc.getMethod()))
74 cananian 1.1.2.3 mpo = new MustParamOracle(hc);
75 cananian 1.1.2.1 // create new visitor
76 cananian 1.1.2.3 ReadVisitor rv = new ReadVisitor(which, hc.getMethod(), fso, cg, mpo);
77 cananian 1.1.2.1 // add HEADER quad to work list.
78 cananian 1.1.2.1 rv.W.add(hc.getRootElement());
79 cananian 1.1.2.1 // iterate until worklist is empty.
80 cananian 1.1.2.1 while (!rv.W.isEmpty())
81 cananian 1.1.2.1 ((Quad)rv.W.pop()).accept(rv);
82 cananian 1.1.2.1 // done! all results are in rv.results map (w/ 'aliasMap')
83 cananian 1.1.2.1 }
84 cananian 1.1.2.1 /** 'reads' set of a edge, along with which 'next' quad to
85 cananian 1.1.2.1 * evaluate if/when the reads-set changes. */
86 cananian 1.1.2.1 static class EdgeProp {
87 cananian 1.1.2.1 final Set reads;
88 cananian 1.1.2.1 Quad next; // updatable.
89 cananian 1.1.2.1 EdgeProp(Set reads, Quad next) {
90 cananian 1.1.2.1 this.reads=reads; this.next=next;
91 cananian 1.1.2.1 }
92 cananian 1.1.2.1 }
93 cananian 1.1.2.1 /** this is the visitor class which does the real work.
94 cananian 1.1.2.1 * Theory of operation: straight data-flow on edges. If any
95 cananian 1.1.2.1 * quad modifies its outset, it adds the next quad to the worklist.
96 cananian 1.1.2.1 * We continue until worklist is empty. To speed iteration, any
97 cananian 1.1.2.1 * quad which does not change the outset (i.e. the transfer function
98 cananian 1.1.2.1 * between its in-set and out-set is the identity function) is
99 cananian 1.1.2.1 * skipped over in subsequent passes by aliasing its in-edge to its
100 cananian 1.1.2.1 * out-edge. */
101 cananian 1.1.2.1 class ReadVisitor extends QuadVisitor {
102 cananian 1.1.2.1 final HClass declaringClass;
103 cananian 1.1.2.1 final HMethod thisMethod;
104 cananian 1.1.2.1 final WorkSet W = new WorkSet();
105 cananian 1.1.2.1 final FieldSyncOracle fso;
106 cananian 1.1.2.3 final MustParamOracle mpo; // only non-null if special handling.
107 cananian 1.1.2.1 final CallGraph cg;
108 cananian 1.1.2.1 final SetFactory sf = new AggregateSetFactory();
109 cananian 1.1.2.1 // our task: given an inset, create an outset.
110 cananian 1.1.2.1 // the inset corresponds to q.prev(x) (which is 'in')
111 cananian 1.1.2.1 // filtered through the aliasMap (which is 'real').
112 cananian 1.1.2.1 ReadVisitor(HClass declaringClass, HMethod thisMethod,
113 cananian 1.1.2.3 FieldSyncOracle fso, CallGraph cg, MustParamOracle mpo) {
114 cananian 1.1.2.1 this.declaringClass = declaringClass;
115 cananian 1.1.2.1 this.thisMethod = thisMethod;
116 cananian 1.1.2.1 this.fso = fso;
117 cananian 1.1.2.3 this.mpo = mpo;
118 cananian 1.1.2.1 this.cg = cg;
119 cananian 1.1.2.1 }
120 cananian 1.1.2.1 /** initialize the analysis. HEADER generates our initial out-set. */
121 cananian 1.1.2.1 public void visit(HEADER q) {
122 cananian 1.1.2.1 // no in-set. empty out-set. continue with METHOD (edge 1).
123 cananian 1.1.2.1 Edge out=q.nextEdge(1);
124 cananian 1.3.2.1 assert !results.containsKey(aliasMap.find(out));
125 cananian 1.1.2.1 EdgeProp nep = new EdgeProp(Collections.EMPTY_SET, (Quad)out.to());
126 cananian 1.1.2.1 results.put(aliasMap.find(out), nep);
127 cananian 1.1.2.1 W.add(nep.next);
128 cananian 1.1.2.1 }
129 cananian 1.1.2.1 /** this method handles all 'no-change' in-to-out transfer functions.
130 cananian 1.1.2.1 * we basically just map the in edge to the out edge, with some
131 cananian 1.1.2.1 * magic involved to get the results maps and such to work out
132 cananian 1.1.2.1 * right. */
133 cananian 1.1.2.1 public void visit(Quad q) {
134 cananian 1.1.2.1 // one input, one output. add alias from in to out edge.
135 cananian 1.3.2.1 assert q.prevLength()==1 && q.nextLength()==1;
136 cananian 1.1.2.1 Edge in = q.prevEdge(0), out=q.nextEdge(0);
137 cananian 1.1.2.1 // fetch inset and next.
138 cananian 1.1.2.1 EdgeProp oep = (EdgeProp) results.remove(aliasMap.find(in));
139 cananian 1.3.2.1 assert oep!=null;
140 cananian 1.1.2.1 // inset becomes outset (no change) but update 'next'.
141 cananian 1.1.2.1 EdgeProp nep = oep;
142 cananian 1.1.2.1 nep.next = q.next(0);
143 cananian 1.1.2.1 // merge 'out' with 'in'...
144 cananian 1.1.2.1 aliasMap.union(in, out);
145 cananian 1.1.2.1 // ...re-put outset.
146 cananian 1.1.2.1 results.put(aliasMap.find(out), nep);
147 cananian 1.1.2.1 // ta-da!
148 cananian 1.1.2.1 W.add(nep.next);
149 cananian 1.1.2.1 }
150 cananian 1.1.2.1 /** GET possibly adds a field to its out-set. */
151 cananian 1.1.2.1 public void visit(GET q) {
152 cananian 1.1.2.1 // ignore if this get is not from the class we're interested in.
153 cananian 1.1.2.1 if (declaringClass != null &&
154 cananian 1.1.2.1 !q.field().getDeclaringClass().equals(declaringClass)) {
155 cananian 1.1.2.1 visit((Quad)q);
156 cananian 1.1.2.1 return;
157 cananian 1.1.2.1 }
158 cananian 1.1.2.1 // outset = inset + this field.
159 cananian 1.1.2.1 boolean changed = false;
160 cananian 1.1.2.1 Edge in = q.prevEdge(0), out=q.nextEdge(0);
161 cananian 1.1.2.1 EdgeProp oep = (EdgeProp) results.get(aliasMap.find(in));
162 cananian 1.3.2.1 assert oep!=null;
163 cananian 1.1.2.1 EdgeProp nep = (EdgeProp) results.get(aliasMap.find(out));
164 cananian 1.1.2.1 if (nep==null) {
165 cananian 1.1.2.1 nep = new EdgeProp(sf.makeSet(oep.reads), q.next(0));
166 cananian 1.1.2.1 results.put(aliasMap.find(out), nep);
167 cananian 1.1.2.1 changed = true;
168 cananian 1.1.2.1 }
169 cananian 1.1.2.3 if (isOkay(q) && nep.reads.add(q.field()))
170 cananian 1.1.2.1 changed = true;
171 cananian 1.1.2.1 // if something changed, add nep.next to work set.
172 cananian 1.1.2.1 if (changed)
173 cananian 1.1.2.1 W.add(nep.next);
174 cananian 1.1.2.1 }
175 cananian 1.1.2.3 /** this implements the 'special handling for constructors' */
176 cananian 1.1.2.3 boolean isOkay(GET q) {
177 cananian 1.1.2.3 if (mpo==null) return true; // always okay if not special handling
178 cananian 1.1.2.3 return mpo.isMustParam(q.objectref()) &&
179 cananian 1.1.2.3 mpo.whichMustParam(q.objectref())==0;
180 cananian 1.1.2.3 }
181 cananian 1.1.2.1 /** A CALL adds all fields possibly-read by the methods
182 cananian 1.1.2.1 * possibly-called by it to its out-set. */
183 cananian 1.1.2.1 public void visit(CALL q) {
184 cananian 1.1.2.1 Edge in = q.prevEdge(0);
185 cananian 1.1.2.1 EdgeProp oep = (EdgeProp) results.get(aliasMap.find(in));
186 cananian 1.3.2.1 assert oep!=null;
187 cananian 1.1.2.1 // find methods callable from q.
188 cananian 1.1.2.1 HMethod[] callable = cg.calls(thisMethod, q);
189 cananian 1.1.2.1 // any any fields which *may* be read by one of these methods.
190 cananian 1.1.2.1 Set mayRead = new HashSet();
191 cananian 1.1.2.1 for (int i=0; i<callable.length; i++)
192 cananian 1.1.2.1 mayRead.addAll(fso.fieldsRead(callable[i]));
193 cananian 1.1.2.1 // filter out the fields we're not interested in.
194 cananian 1.1.2.1 if (declaringClass!=null)
195 cananian 1.1.2.1 for (Iterator it=mayRead.iterator(); it.hasNext(); )
196 cananian 1.1.2.1 if (!((HField)it.next()).getDeclaringClass()
197 cananian 1.1.2.1 .equals(declaringClass))
198 cananian 1.1.2.1 it.remove();
199 cananian 1.1.2.1 // add to all out-sets
200 cananian 1.1.2.1 for (int i=0; i<q.nextLength(); i++) {
201 cananian 1.1.2.1 boolean changed = false;
202 cananian 1.1.2.1 Edge out = q.nextEdge(i);
203 cananian 1.1.2.1 EdgeProp nep = (EdgeProp) results.get(aliasMap.find(out));
204 cananian 1.1.2.1 if (nep==null) {
205 cananian 1.1.2.1 nep = new EdgeProp(sf.makeSet(oep.reads), (Quad)out.to());
206 cananian 1.1.2.1 results.put(aliasMap.find(out), nep);
207 cananian 1.1.2.1 changed=true;
208 cananian 1.1.2.1 }
209 cananian 1.1.2.1 if (nep.reads.addAll(mayRead))
210 cananian 1.1.2.1 changed=true;
211 cananian 1.1.2.1 if (changed)
212 cananian 1.1.2.1 W.add(nep.next);
213 cananian 1.1.2.1 }
214 cananian 1.1.2.1 }
215 cananian 1.1.2.1 // we could refactor both the PHI and SIGMA *and* one-in-one-out
216 cananian 1.1.2.1 // non-GET cases together into one method, but I think it's
217 cananian 1.1.2.1 // easier to read if we keep them a *little* separate, at least.
218 cananian 1.1.2.1 // I *did* combine PHI and SIGMA into the following method,
219 cananian 1.1.2.1 // which deals with both. all out-sets get all in-sets added
220 cananian 1.1.2.1 // to them.
221 cananian 1.1.2.1 void visitPhiSigma(Quad q) {
222 cananian 1.1.2.1 // for all 'out' edges...
223 cananian 1.1.2.1 for (int i=0; i<q.nextLength(); i++) {
224 cananian 1.1.2.1 boolean changed=false;
225 cananian 1.1.2.1 // get current out-set.
226 cananian 1.1.2.1 Edge out = q.nextEdge(i);
227 cananian 1.1.2.1 EdgeProp nep = (EdgeProp) results.get(aliasMap.find(out));
228 cananian 1.1.2.1 // merge over all 'in' edges...
229 cananian 1.1.2.1 for (int j=0; j<q.prevLength(); j++) {
230 cananian 1.1.2.1 // get current in-set.
231 cananian 1.1.2.1 Edge in = q.prevEdge(j);
232 cananian 1.1.2.1 EdgeProp oep = (EdgeProp) results.get(aliasMap.find(in));
233 cananian 1.1.2.1 if (oep==null) {
234 cananian 1.3.2.1 assert q.prevLength()>1; // only for PHIs.
235 cananian 1.1.2.1 continue; // skip this edge; nothing yet known.
236 cananian 1.1.2.1 }
237 cananian 1.1.2.1 if (nep==null) {
238 cananian 1.1.2.1 // if we don't have an out-set yet, create one.
239 cananian 1.1.2.1 // the one-in-one-out non-quad special case
240 cananian 1.1.2.1 // would go in here. but we're going to keep
241 cananian 1.1.2.1 // this clean.
242 cananian 1.1.2.1 changed=true;
243 cananian 1.1.2.1 // (new out set with 'reads' of the in-set.
244 cananian 1.1.2.1 nep = new EdgeProp(sf.makeSet(oep.reads),
245 cananian 1.1.2.1 (Quad) out.to());
246 cananian 1.1.2.1 results.put(aliasMap.find(out), nep);
247 cananian 1.1.2.1 } else if (nep.reads.addAll(oep.reads))
248 cananian 1.1.2.1 // we added stuff to the out-set.
249 cananian 1.1.2.1 changed = true;
250 cananian 1.1.2.1 }
251 cananian 1.1.2.1 // if anything changed, add our successor to the worklist.
252 cananian 1.1.2.1 if (changed)
253 cananian 1.1.2.1 W.add(nep.next);
254 cananian 1.1.2.1 }
255 cananian 1.1.2.1 }
256 cananian 1.1.2.1 public void visit(PHI q) { visitPhiSigma(q); }
257 cananian 1.1.2.1 public void visit(SIGMA q) { visitPhiSigma(q); }
258 cananian 1.1.2.1
259 cananian 1.1.2.1 // RETURN and THROW are the end of the line. no out-set.
260 cananian 1.1.2.1 public void visit(RETURN q) { /* do nothing */ }
261 cananian 1.1.2.1 public void visit(THROW q) { /* do nothing */ }
262 cananian 1.1.2.1 }
263 cananian 1.1.2.1
264 cananian 1.1.2.3 /** return a conservative approximation to whether this is a constructor
265 cananian 1.1.2.3 * or not. it's always safe to return true. */
266 cananian 1.1.2.3 private static boolean isConstructor(HMethod hm) {
267 cananian 1.1.2.3 // this is tricky, because we want split constructors to count, too,
268 cananian 1.1.2.3 // even though renamed constructors (such as generated by initcheck,
269 cananian 1.1.2.3 // for instance) won't always be instanceof HConstructor. Look
270 cananian 1.1.2.3 // for names starting with '<init>', as well.
271 cananian 1.1.2.3 if (hm instanceof HConstructor) return true;
272 cananian 1.1.2.3 if (hm.getName().startsWith("<init>")) return true;
273 cananian 1.1.2.3 // XXX: what about methods generated by RuntimeMethod Cloner?
274 cananian 1.1.2.3 // we could try methods ending with <init>, but then the
275 cananian 1.1.2.3 // declaringclass information would be wrong.
276 cananian 1.1.2.3 //if (hm.getName().endsWidth("<init>")) return true;//not safe yet.
277 cananian 1.1.2.3 return false;
278 cananian 1.1.2.3 }
279 cananian 1.2 }