1 salcianu 1.1.2.1 // InterProcPA.java, created Tue Jan 18 11:04:20 2000 by salcianu
2 cananian 1.1.2.55 // Copyright (C) 2000 Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
3 salcianu 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 salcianu 1.1.2.1 package harpoon.Analysis.PointerAnalysis;
5 salcianu 1.1.2.1
6 salcianu 1.1.2.44 import java.util.Collection;
7 salcianu 1.1.2.1 import java.util.Iterator;
8 salcianu 1.1.2.1 import java.util.Enumeration;
9 salcianu 1.1.2.1 import java.util.Set;
10 salcianu 1.1.2.1 import java.util.HashSet;
11 salcianu 1.1.2.33 import java.util.Collections;
12 salcianu 1.1.2.44 import java.util.List;
13 salcianu 1.1.2.44 import java.util.LinkedList;
14 salcianu 1.1.2.52 import java.util.Map;
15 salcianu 1.1.2.52 import java.util.HashMap;
16 salcianu 1.1.2.1
17 salcianu 1.1.2.22 import java.lang.reflect.Modifier;
18 salcianu 1.1.2.22
19 salcianu 1.1.2.1 import harpoon.IR.Quads.CALL;
20 salcianu 1.8 import harpoon.IR.Quads.GET;
21 salcianu 1.8 import harpoon.IR.Quads.AGET;
22 salcianu 1.8 import harpoon.IR.Quads.NEW;
23 salcianu 1.8 import harpoon.IR.Quads.ANEW;
24 salcianu 1.1.2.1 import harpoon.Analysis.Quads.CallGraph;
25 salcianu 1.1.2.1 import harpoon.Temp.Temp;
26 salcianu 1.1.2.1
27 salcianu 1.1.2.33 import harpoon.ClassFile.HClass;
28 salcianu 1.1.2.33 import harpoon.ClassFile.HCode;
29 salcianu 1.1.2.19 import harpoon.ClassFile.HMethod;
30 salcianu 1.1.2.33 import harpoon.ClassFile.HField;
31 salcianu 1.1.2.53 import harpoon.ClassFile.Linker;
32 salcianu 1.8 import harpoon.ClassFile.HCodeElement;
33 cananian 1.10 import harpoon.ClassFile.NoSuchClassException;
34 salcianu 1.1.2.19
35 salcianu 1.1.2.16 import harpoon.Analysis.MetaMethods.MetaMethod;
36 salcianu 1.1.2.16 import harpoon.Analysis.MetaMethods.MetaCallGraph;
37 salcianu 1.8 import harpoon.Analysis.MetaMethods.GenType;
38 salcianu 1.1.2.1
39 salcianu 1.1.2.33 import harpoon.Util.TypeInference.ExactTemp;
40 salcianu 1.1.2.33 import harpoon.Util.TypeInference.TypeInference;
41 salcianu 1.1.2.33 import harpoon.IR.Quads.QuadFactory;
42 salcianu 1.1.2.33
43 salcianu 1.1.2.47 import harpoon.Util.DataStructs.Relation;
44 salcianu 1.1.2.48 import harpoon.Util.DataStructs.RelationImpl;
45 salcianu 1.1.2.47 import harpoon.Util.DataStructs.RelationEntryVisitor;
46 salcianu 1.1.2.47
47 salcianu 1.11 import harpoon.Util.Graphs.DiGraph;
48 salcianu 1.11 import harpoon.Util.Graphs.ForwardNavigator;
49 salcianu 1.11
50 salcianu 1.1.2.30 import harpoon.Util.Util;
51 salcianu 1.1.2.30
52 salcianu 1.1.2.1 /**
53 salcianu 1.1.2.1 * <code>InterProcPA</code> is a "functional" class (i.e. it
54 salcianu 1.1.2.1 * contains just some methods, no persistent data) that wraps
55 salcianu 1.1.2.1 * the inter-procedural part of the pointer analysis. Normally, this should
56 salcianu 1.1.2.1 * be a part of the <code>PointerAnalysis</code>, but that class is already
57 salcianu 1.1.2.40 * too big and some code segmentation is always good!<br>
58 salcianu 1.1.2.40 * In the implementation of this class, most of the methods are static and
59 salcianu 1.1.2.40 * have <code>PointerAnalysis pa</code> as their first argument. This stands
60 salcianu 1.1.2.40 * for the <code>this</code> <i>hidden</i> argument that would exist if all
61 salcianu 1.1.2.40 * those methods were in the <code>PointerAnalysis</code> class.
62 salcianu 1.1.2.1 *
63 cananian 1.1.2.55 * @author Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
64 cananian 1.12 * @version $Id: InterProcPA.java,v 1.12 2004/02/08 03:20:02 cananian Exp $
65 salcianu 1.1.2.1 */
66 salcianu 1.1.2.54 public abstract class InterProcPA implements java.io.Serializable {
67 salcianu 1.1.2.4
68 salcianu 1.1.2.41 /** Call sites with more than <code>MAX_CALLEES</code> callees are simply
69 salcianu 1.1.2.41 * considered to be holes. */
70 salcianu 1.11 public static final int MAX_CALLEES = 20;
71 salcianu 1.1.2.30
72 salcianu 1.1.2.41 /** Activates a lot of debug messages. */
73 salcianu 1.11 public static boolean DEBUG = false;
74 salcianu 1.1.2.10
75 salcianu 1.1.2.41 /** Displays some warnings, <i>eg</i> for the call sites with 0 callees.
76 salcianu 1.1.2.41 * This is not necessarily an error! For example, if an application
77 salcianu 1.1.2.41 * never instantiates a <code>SecurityManager</code>,
78 salcianu 1.1.2.41 * each call to a method of that class has ZERO callees! */
79 salcianu 1.1.2.42 public static final boolean WARNINGS = true;
80 salcianu 1.1.2.19
81 salcianu 1.8 /** Trust that a call to java.lang.Object.equals doesn't do
82 salcianu 1.8 anything interesting. */
83 salcianu 1.11 public static boolean TRUST_EQUALS = false;
84 salcianu 1.8
85 salcianu 1.8 /** Trust that a call to java.lang.Object.hashCode doesn't do
86 salcianu 1.8 anything interesting. */
87 salcianu 1.11 public static boolean TRUST_HASHCODE = false;
88 salcianu 1.8
89 salcianu 1.8 /** Trust that a call to java.lang.Object.toString doesn't do
90 salcianu 1.8 anything interesting. */
91 salcianu 1.11 public static boolean TRUST_TOSTRING = false;
92 salcianu 1.8
93 salcianu 1.5 private static final boolean CONSIDER_WES_GOOD = false;
94 salcianu 1.1.2.53
95 salcianu 1.1.2.4 /** Analyzes the call site <code>q</code> inside
96 salcianu 1.1.2.41 * <code>current_method</code>. If analyzing the call is not possible
97 salcianu 1.1.2.41 * (e.g. one of the callees is native, hence unanalyzable), the call
98 salcianu 1.1.2.41 * site is skipped and all the parameters are marked as escaping
99 salcianu 1.1.2.41 * through that call site.
100 salcianu 1.1.2.41 *
101 salcianu 1.1.2.41 * @param pa The <code>PointerAnalysis</code> object that
102 salcianu 1.1.2.41 * calls this method. This parameter stands for the <code>this</code>
103 salcianu 1.1.2.41 * pointer that would exist if this method were in the
104 salcianu 1.1.2.41 * <code>PointerAnalysis</code> class.
105 salcianu 1.1.2.41 * @param current_method The method that contains in its
106 salcianu 1.1.2.41 * code the call site <code>q</code>.
107 salcianu 1.1.2.41 * @param q The analyzed call site.
108 salcianu 1.1.2.41 * @param pig_before The parallel interaction graph at
109 salcianu 1.1.2.41 * the program point just before the call site; this graph will be
110 salcianu 1.1.2.41 * mutated, it is the responsability of the caller to clone it if it
111 salcianu 1.1.2.41 * is necessary somewhere else.
112 salcianu 1.1.2.41 *
113 salcianu 1.1.2.41 * @return Two graphs are returned: one for the normal return from
114 salcianu 1.1.2.41 * the procedure, the other one for a return due to an exception.
115 salcianu 1.1.2.41 */
116 salcianu 1.1.2.40 public static ParIntGraphPair analyze_call(PointerAnalysis pa,
117 salcianu 1.1.2.40 MetaMethod current_mmethod,
118 salcianu 1.1.2.18 CALL q,
119 salcianu 1.1.2.40 ParIntGraph pig_before) {
120 salcianu 1.8 long b_time =
121 salcianu 1.8 PointerAnalysis.FINE_TIMING ? System.currentTimeMillis() : 0;
122 salcianu 1.8
123 salcianu 1.8 ParIntGraphPair result =
124 salcianu 1.8 analyze_call2(pa, current_mmethod, q, pig_before);
125 salcianu 1.8 if(PointerAnalysis.FINE_TIMING)
126 salcianu 1.8 total_interproc_time += System.currentTimeMillis() - b_time;
127 salcianu 1.8 return result;
128 salcianu 1.8 }
129 salcianu 1.8
130 salcianu 1.8
131 salcianu 1.8 private static ParIntGraphPair analyze_call2(PointerAnalysis pa,
132 salcianu 1.8 MetaMethod current_mmethod,
133 salcianu 1.8 CALL q,
134 salcianu 1.8 ParIntGraph pig_before) {
135 salcianu 1.8
136 salcianu 1.11 HMethod src = q.getFactory().getMethod();
137 salcianu 1.8
138 salcianu 1.1.2.54 if(DEBUG || DEBUG_MU)
139 salcianu 1.1.2.54 System.out.println("\nInter-procedural analysis " +
140 salcianu 1.7 Util.code2str(q));
141 salcianu 1.1.2.32
142 salcianu 1.1.2.44 ParIntGraphPair pp_after = null;
143 salcianu 1.1.2.44
144 salcianu 1.1.2.44 // treat some very special native methods
145 salcianu 1.1.2.44 if((pp_after = treatVerySpecialNatives(pa, q, pig_before)) != null)
146 salcianu 1.1.2.44 return pp_after;
147 salcianu 1.1.2.32
148 salcianu 1.1.2.32 MetaMethod[] mms = pa.getMetaCallGraph().getCallees(current_mmethod,q);
149 salcianu 1.1.2.32 int nb_callees = mms.length;
150 salcianu 1.1.2.32
151 salcianu 1.1.2.32 // I count on the fact that if a call site has 0 callees, it
152 salcianu 1.1.2.32 // means that it doesn't occur in practice (because some classes
153 salcianu 1.1.2.44 // are not instantiated), not that the call graph is buggy!
154 salcianu 1.1.2.32 // So, the CALL is simply ignored.
155 salcianu 1.8 if(nb_callees == 0) {
156 salcianu 1.8 if(WARNINGS) {
157 salcianu 1.1.2.32 System.out.println("Warning: CALL site with no callee! ");
158 salcianu 1.7 System.out.println("Warning: " + Util.code2str(q));
159 salcianu 1.1.2.35 }
160 salcianu 1.1.2.35 return new ParIntGraphPair(pig_before, pig_before);
161 salcianu 1.1.2.32 }
162 salcianu 1.1.2.32
163 salcianu 1.1.2.32 // Due to the imprecisions in the call graph, most of them due to
164 salcianu 1.1.2.32 // dynamic dispatches, several call sites have a huge number of callees
165 salcianu 1.1.2.32 // These CALLs are not analyzed (i.e. they are treated as method holes)
166 salcianu 1.8 if(nb_callees > MAX_CALLEES) {
167 salcianu 1.8 //if(DEBUG)
168 salcianu 1.1.2.32 System.out.println("TOO MANY CALLEES (" + nb_callees + ") "+q);
169 salcianu 1.8 if((TRUST_EQUALS && q.method().equals(jlO_equals)) ||
170 salcianu 1.8 (TRUST_HASHCODE && q.method().equals(jlO_hashCode)) ||
171 salcianu 1.8 (TRUST_TOSTRING && q.method().equals(jlO_toString))) {
172 salcianu 1.8 //if(DEBUG)
173 salcianu 1.8 System.out.println("BUT equals/hashCode/toString ");
174 salcianu 1.8 return treatNatives(pa, new MetaMethod(q.method(), true),
175 salcianu 1.8 q, pig_before);
176 salcianu 1.8 }
177 salcianu 1.1.2.40 return skip_call(pa, q, pig_before, q.method());
178 salcianu 1.1.2.32 }
179 salcianu 1.1.2.32
180 salcianu 1.1.2.35 // For each analyzable callee mm, we store it in mms and its associated
181 salcianu 1.1.2.32 // parallel interaction graph in pigs. By "analyzable", we mean
182 salcianu 1.1.2.32 // (meta)-methods that are analyzable by the the Pointer Analysis PLUS
183 salcianu 1.1.2.32 // the so-called unharmful native methods - native method that we can't
184 salcianu 1.1.2.32 // analyze as we don't have their code but we know what their pig will
185 salcianu 1.1.2.32 // look like (for most of them it's empty - they don't create new
186 salcianu 1.8 // pointer links and don't do any relevant action (e.g., syncs)).
187 salcianu 1.1.2.32 //
188 salcianu 1.1.2.32 // For the unharmful native methods the associated pig will be null
189 salcianu 1.1.2.32 // (they will be specially treated inside mapUp).
190 salcianu 1.1.2.32 //
191 salcianu 1.1.2.32 // pig could be also null if the method has not be analyzed yet; this
192 salcianu 1.1.2.32 // happens only in strongly connected components of mutually recursive
193 salcianu 1.1.2.44 // methods. In this case, we simply don't consider that callee; the
194 salcianu 1.1.2.44 // called method will be analyzed later, this will force its callers
195 salcianu 1.1.2.44 // to be reanalyzed, so in the end it will be considered (due to the
196 salcianu 1.1.2.44 // fixed-point algorithm).
197 salcianu 1.1.2.32 int nb_callees_with_pig = 0;
198 salcianu 1.1.2.32 ParIntGraph pigs[] = new ParIntGraph[nb_callees];
199 salcianu 1.1.2.32 for(int i = 0; i < nb_callees; i++){
200 salcianu 1.1.2.32 HMethod hm = mms[i].getHMethod();
201 salcianu 1.1.2.32
202 salcianu 1.1.2.44 if(Modifier.isNative(hm.getModifiers())) {
203 salcianu 1.11 if(DEBUG)
204 salcianu 1.11 System.out.println("\nNATIVE: " + hm);
205 salcianu 1.11 if(isTotallyHarmful(hm)) {
206 salcianu 1.11 //if(DEBUG)
207 salcianu 1.11 System.out.print("\nNEED TO SKIP: " + Util.code2str(q));
208 salcianu 1.11 return skip_call(pa, q, pig_before, hm);
209 salcianu 1.11 }
210 salcianu 1.11 else {
211 salcianu 1.11 ParIntGraph pig = model_native(hm);
212 salcianu 1.11 pigs[nb_callees_with_pig] = pig;
213 salcianu 1.11 mms[nb_callees_with_pig] = mms[i];
214 salcianu 1.11 nb_callees_with_pig++;
215 salcianu 1.11 continue;
216 salcianu 1.11 }
217 salcianu 1.1.2.32 }
218 salcianu 1.1.2.53
219 salcianu 1.1.2.53 // RTJ stuff START - Wes's stuff is supposed to be safe
220 salcianu 1.1.2.53 if(CONSIDER_WES_GOOD) {
221 salcianu 1.1.2.53 if(wes_methods.contains(hm)) {
222 salcianu 1.1.2.53 pigs[nb_callees_with_pig] = null;
223 salcianu 1.1.2.53 mms[nb_callees_with_pig] = mms[i];
224 salcianu 1.1.2.53 nb_callees_with_pig++;
225 salcianu 1.1.2.53 continue;
226 salcianu 1.1.2.53 }
227 salcianu 1.1.2.53 }
228 salcianu 1.1.2.53 // RTJ stuff END
229 salcianu 1.1.2.53
230 salcianu 1.11 if(!(PointerAnalysis.analyzable(hm))) {
231 salcianu 1.8 //if(DEBUG)
232 salcianu 1.11 System.out.println("NEED TO SKIP2: " + Util.code2str(q));
233 salcianu 1.1.2.40 return skip_call(pa, q, pig_before, hm);
234 salcianu 1.1.2.32 }
235 salcianu 1.1.2.32
236 salcianu 1.1.2.32 ParIntGraph pig = pa.getExtParIntGraph(mms[i], false);
237 salcianu 1.8 if(pig != null) {
238 salcianu 1.1.2.32 pigs[nb_callees_with_pig] = pig;
239 salcianu 1.1.2.32 mms[nb_callees_with_pig] = mms[i];
240 salcianu 1.1.2.32 nb_callees_with_pig++;
241 salcianu 1.1.2.32 }
242 salcianu 1.1.2.32 }
243 salcianu 1.1.2.32
244 salcianu 1.1.2.32 // If none of the callers has been analyzed yet, do not do anything
245 salcianu 1.1.2.32 // (this can happen only in the strongly connected components of
246 salcianu 1.1.2.32 // mutually recursive methods).
247 salcianu 1.11 if(nb_callees_with_pig == 0) {
248 salcianu 1.11 ParIntGraph pig0 = (ParIntGraph) pig_before.clone();
249 salcianu 1.11 Temp l_R = q.retval();
250 salcianu 1.11 if(l_R != null) pig0.G.I.removeEdges(l_R);
251 salcianu 1.11 ParIntGraph pig1 = (ParIntGraph) pig_before.clone();
252 salcianu 1.11 Temp l_E = q.retex();
253 salcianu 1.11 if(l_E != null) pig1.G.I.removeEdges(l_E);
254 salcianu 1.11 return new ParIntGraphPair(pig0, pig1);
255 salcianu 1.11 }
256 salcianu 1.1.2.35
257 salcianu 1.1.2.32 // Specialize the graphs of the callees for the context sensitive PA
258 salcianu 1.1.2.32 if(PointerAnalysis.CALL_CONTEXT_SENSITIVE)
259 salcianu 1.1.2.32 for(int i = 0; i < nb_callees_with_pig; i++)
260 salcianu 1.1.2.32 if(pigs[i] != null){
261 salcianu 1.1.2.32 if(DEBUG)
262 salcianu 1.1.2.32 System.out.println("BEFORE SPEC: " + pigs[i]);
263 salcianu 1.1.2.44 pigs[i] = pa.getSpecializedExtParIntGraph(mms[i], q);
264 salcianu 1.1.2.32 if(DEBUG)
265 salcianu 1.1.2.32 System.out.println("AFTER SPEC: " + pigs[i]);
266 salcianu 1.1.2.32 }
267 salcianu 1.1.2.32
268 salcianu 1.1.2.32 // The graph after the CALL is a join of all the graphs obtained
269 salcianu 1.1.2.32 // by combining, for each callee mms[i], the graph before the CALL
270 salcianu 1.1.2.32 // with the graph at the end of mms[i].
271 salcianu 1.1.2.32 // The implementation is complicated by the need of doing only the
272 salcianu 1.1.2.32 // minimum number of clone() (cloning a ParIntGraph is very expensive).
273 salcianu 1.1.2.32
274 salcianu 1.1.2.32 // 1. Special case: only one callee; no ParIntGraph is cloned.
275 salcianu 1.11 if(nb_callees_with_pig == 1)
276 salcianu 1.1.2.40 return mapUp(pa, mms[0], q, pig_before, pigs[0]);
277 salcianu 1.1.2.32
278 salcianu 1.1.2.32 // 2. More than one callee:
279 salcianu 1.1.2.32 // 2.1. Compute the first term of the join operation.
280 salcianu 1.1.2.44 pp_after =
281 salcianu 1.1.2.44 mapUp(pa, mms[0], q, (ParIntGraph) pig_before.clone(), pigs[0]);
282 salcianu 1.1.2.32
283 salcianu 1.1.2.32 // 2.2. Join to it all the others, except for the last one.
284 salcianu 1.1.2.32 for(int i = 1; i < nb_callees_with_pig - 1; i++)
285 salcianu 1.1.2.40 pp_after.join(mapUp(pa, mms[i], q, (ParIntGraph)pig_before.clone(),
286 salcianu 1.1.2.40 pigs[i]));
287 salcianu 1.1.2.35
288 salcianu 1.1.2.32 // 2.3. Finally, join the graph for the last callee.
289 salcianu 1.1.2.32 MetaMethod last_mm = mms[nb_callees_with_pig - 1];
290 salcianu 1.1.2.32 pp_after.join
291 salcianu 1.1.2.40 (mapUp(pa, last_mm, q, pig_before, pigs[nb_callees_with_pig-1]));
292 salcianu 1.1.2.40
293 salcianu 1.1.2.32 return pp_after; // the long awaited moment!
294 salcianu 1.1.2.32 }
295 salcianu 1.1.2.32
296 salcianu 1.1.2.32
297 salcianu 1.1.2.18 /** Updates the ParIntGraph when the CALL is skipped. Two graphs are
298 salcianu 1.1.2.18 returned: one for the normal return from the procedure, the other
299 salcianu 1.1.2.18 one for a return due to an exception. */
300 salcianu 1.1.2.40 private static ParIntGraphPair skip_call(PointerAnalysis pa,
301 salcianu 1.1.2.40 CALL q, ParIntGraph pig_caller,
302 salcianu 1.1.2.35 HMethod hm) {
303 salcianu 1.1.2.24
304 salcianu 1.1.2.32 if(DEBUG)
305 salcianu 1.1.2.24 System.out.println("SKIP: " + q);
306 salcianu 1.1.2.24
307 salcianu 1.1.2.40 NodeRepository node_rep = pa.getNodeRepository();
308 salcianu 1.1.2.40
309 salcianu 1.1.2.1 // Construct the set S_M of the objects escaped through this unanalyzed
310 salcianu 1.1.2.1 // method invocation site.
311 salcianu 1.1.2.1 Set S_M = new HashSet();
312 salcianu 1.1.2.1 Temp[] params = q.params();
313 salcianu 1.1.2.18 for(int i = 0; i < params.length; i++)
314 salcianu 1.1.2.1 S_M.addAll(pig_caller.G.I.pointedNodes(params[i]));
315 salcianu 1.1.2.30
316 salcianu 1.1.2.1 // Update the escape information
317 salcianu 1.1.2.22 // 1. all the parameters are directly escaping into the method hole
318 salcianu 1.1.2.18 for(Iterator it = S_M.iterator(); it.hasNext(); )
319 salcianu 1.1.2.35 pig_caller.G.e.addMethodHole((PANode)it.next(), hm);
320 salcianu 1.1.2.22 // 2. propagate the new escape information
321 salcianu 1.1.2.1 pig_caller.G.propagate(S_M);
322 salcianu 1.1.2.18
323 salcianu 1.1.2.18 // clone the graph: we will have two distinct versions of it:
324 salcianu 1.1.2.18 // one on the 0-edge, the other on the 1-edge, corresponding
325 salcianu 1.1.2.18 // to the normal execution (return) respectively execution with
326 salcianu 1.1.2.18 // exceptions (throw).
327 salcianu 1.1.2.18 ParIntGraph pig_caller1 = (ParIntGraph) (pig_caller.clone());
328 salcianu 1.1.2.18
329 salcianu 1.1.2.18 // The names of the variables closely match those used in the
330 salcianu 1.1.2.18 // formal description of the algorithm (section 9.2)
331 salcianu 1.1.2.18
332 salcianu 1.1.2.18 // Set the edges for the result node in graph 0.
333 salcianu 1.1.2.23 // avoid generating useless nodes
334 salcianu 1.1.2.18 Temp l_R = q.retval();
335 salcianu 1.1.2.24 if(l_R != null){
336 salcianu 1.1.2.18 pig_caller.G.I.removeEdges(l_R);
337 salcianu 1.8 if(!hm.getReturnType().isPrimitive()) {
338 salcianu 1.1.2.24 PANode n_R = node_rep.getCodeNode(q, PANode.RETURN);
339 salcianu 1.1.2.24 pig_caller.G.I.addEdge(l_R, n_R);
340 salcianu 1.1.2.35 pig_caller.G.e.addMethodHole(n_R, hm);
341 salcianu 1.1.2.24 }
342 salcianu 1.1.2.18 }
343 salcianu 1.1.2.18
344 salcianu 1.1.2.18 // Set the edges for the exception node in graph 1.
345 salcianu 1.1.2.18 Temp l_E = q.retex();
346 salcianu 1.1.2.18 if(l_E != null){
347 salcianu 1.1.2.18 pig_caller1.G.I.removeEdges(l_E);
348 salcianu 1.1.2.18 PANode n_E = node_rep.getCodeNode(q, PANode.EXCEPT);
349 salcianu 1.1.2.18 pig_caller1.G.I.addEdge(l_E, n_E);
350 salcianu 1.1.2.35 pig_caller1.G.e.addMethodHole(n_E, hm);
351 salcianu 1.1.2.18 }
352 salcianu 1.1.2.18
353 salcianu 1.1.2.18 return new ParIntGraphPair(pig_caller, pig_caller1);
354 salcianu 1.1.2.1 }
355 salcianu 1.1.2.1
356 salcianu 1.1.2.1
357 salcianu 1.1.2.44 // Treat the calls to native methods.
358 salcianu 1.1.2.45 private static ParIntGraphPair treatNatives(PointerAnalysis pa,
359 salcianu 1.1.2.45 MetaMethod mm,
360 salcianu 1.1.2.45 CALL q,
361 salcianu 1.1.2.45 ParIntGraph pig_caller) {
362 salcianu 1.1.2.40 NodeRepository node_rep = pa.getNodeRepository();
363 salcianu 1.1.2.44 HMethod hm = mm.getHMethod();
364 salcianu 1.1.2.45 if(DEBUG) System.out.println("treatNatives: " + hm);
365 salcianu 1.1.2.44
366 salcianu 1.1.2.44 ParIntGraph pig_before = (ParIntGraph) pig_caller.clone();
367 salcianu 1.1.2.44
368 salcianu 1.1.2.44 if(!isUnharmful(hm))
369 salcianu 1.1.2.44 markEscapedParameters(q, hm, pig_before);
370 salcianu 1.1.2.30
371 salcianu 1.1.2.30 ParIntGraph pig0 = (ParIntGraph) pig_before.clone();
372 salcianu 1.11 ParIntGraph pig1 = pig_before;
373 salcianu 1.1.2.30
374 salcianu 1.1.2.30 Temp l_R = q.retval();
375 salcianu 1.11 if((l_R != null) && !hm.getReturnType().isPrimitive()) {
376 salcianu 1.1.2.30 pig0.G.I.removeEdges(l_R);
377 salcianu 1.1.2.30 PANode n_R = node_rep.getCodeNode(q, PANode.RETURN);
378 salcianu 1.1.2.30 pig0.G.I.addEdge(l_R, n_R);
379 salcianu 1.1.2.35 pig0.G.e.addMethodHole(n_R, hm);
380 salcianu 1.1.2.30 }
381 salcianu 1.1.2.30
382 salcianu 1.1.2.30 Temp l_E = q.retex();
383 salcianu 1.1.2.30 if(l_E != null){
384 salcianu 1.1.2.30 pig1.G.I.removeEdges(l_E);
385 salcianu 1.1.2.30 PANode n_E = node_rep.getCodeNode(q, PANode.EXCEPT);
386 salcianu 1.1.2.30 pig1.G.I.addEdge(l_E, n_E);
387 salcianu 1.1.2.35 pig1.G.e.addMethodHole(n_E, hm);
388 salcianu 1.1.2.30 }
389 salcianu 1.1.2.30
390 salcianu 1.1.2.44 return new ParIntGraphPair(pig0, pig1);
391 salcianu 1.1.2.44 }
392 salcianu 1.1.2.44
393 salcianu 1.1.2.44 private static void markEscapedParameters(CALL q, HMethod hm,
394 salcianu 1.1.2.44 ParIntGraph pig) {
395 salcianu 1.1.2.44 if(markEscapedParametersSpecial(q, hm, pig))
396 salcianu 1.1.2.44 return;
397 salcianu 1.1.2.44 List escaped = new LinkedList();
398 salcianu 1.1.2.44 Temp[] params = q.params();
399 salcianu 1.1.2.44 for(int i = 0; i < params.length; i++) {
400 salcianu 1.1.2.44 HClass hc = q.paramType(i);
401 salcianu 1.1.2.44 if(!hc.isPrimitive())
402 salcianu 1.1.2.44 escaped.addAll(pig.G.I.pointedNodes(params[i]));
403 salcianu 1.1.2.44 }
404 salcianu 1.1.2.44
405 salcianu 1.1.2.44 // Update the escape information
406 salcianu 1.1.2.44 // 1. all the object parameters directly escape into the method hole
407 salcianu 1.1.2.44 for(Iterator it = escaped.iterator(); it.hasNext(); )
408 salcianu 1.1.2.44 pig.G.e.addMethodHole((PANode)it.next(), hm);
409 salcianu 1.1.2.44 // 2. propagate the new escape information
410 salcianu 1.1.2.44 pig.G.propagate(escaped);
411 salcianu 1.1.2.30 }
412 salcianu 1.1.2.30
413 salcianu 1.1.2.44 // For some native methods, maybe only some of the parameters escape
414 salcianu 1.1.2.44 // (ie, we know that the others are not "harmed").
415 salcianu 1.1.2.44 // For the moment, we don't treat any method in this special way.
416 salcianu 1.1.2.44 private static boolean markEscapedParametersSpecial(CALL q, HMethod hm,
417 salcianu 1.1.2.44 ParIntGraph pig) {
418 salcianu 1.1.2.44 return false;
419 salcianu 1.1.2.44 }
420 salcianu 1.1.2.40
421 salcianu 1.1.2.40 /** Updates the graph of the caller at an analyzed call site. This consists
422 salcianu 1.1.2.1 * of mapping the important parts of the callee's graph into the graph of
423 salcianu 1.1.2.1 * the caller. See the paper of Martin and Whaley for a description of the
424 salcianu 1.1.2.1 * algorithm.<br>
425 salcianu 1.1.2.1 * <b>Parameters:</b>
426 salcianu 1.1.2.1 * <ul>
427 salcianu 1.1.2.1 * <li>The <code>CALL</code> quad that represents the call site.<br>
428 salcianu 1.1.2.1 * <li>The Parallel Interaction Graph of the caller
429 salcianu 1.1.2.1 *(<code>pig_caller</code>) that models the memory state just before the
430 salcianu 1.1.2.1 *call site.
431 salcianu 1.1.2.1 * <li>The Parallel Interaction Graph of the callee
432 salcianu 1.1.2.1 *(<code>pig_callee</code>). For efficiency reasons it's advisable to pass
433 salcianu 1.1.2.1 *the reduced, external view of that graph.
434 salcianu 1.1.2.1 * <li>The nodes representing the <b>formal</b> parameters of the callee.
435 salcianu 1.1.2.1 *The actual parameters do not need to be sent: they will be retrieved
436 salcianu 1.1.2.1 *from the <code>CALL</code> quad (the same for return and exception
437 salcianu 1.1.2.1 *temporaries.
438 salcianu 1.1.2.1 *</ul>
439 salcianu 1.1.2.1 */
440 salcianu 1.1.2.40 private static ParIntGraphPair mapUp(PointerAnalysis pa,
441 salcianu 1.1.2.40 MetaMethod mm,
442 salcianu 1.1.2.30 CALL q,
443 salcianu 1.1.2.18 ParIntGraph pig_caller,
444 salcianu 1.1.2.40 ParIntGraph pig_callee) {
445 salcianu 1.8
446 salcianu 1.1.2.44 // if native method, apply special treatment
447 salcianu 1.1.2.31 if(pig_callee == null)
448 salcianu 1.1.2.45 return treatNatives(pa, mm, q, pig_caller);
449 salcianu 1.1.2.40
450 salcianu 1.1.2.40 PANode[] callee_params = pa.getParamNodes(mm);
451 salcianu 1.11 if(callee_params == null)
452 salcianu 1.11 callee_params = get_params4native(mm, pa);
453 salcianu 1.1.2.10
454 salcianu 1.8 long b_time =
455 salcianu 1.8 PointerAnalysis.FINE_TIMING ? System.currentTimeMillis() : 0;
456 salcianu 1.8
457 salcianu 1.1.2.1 Relation mu =
458 salcianu 1.11 compute_mapping(q, pig_caller, pig_callee, callee_params, pa);
459 salcianu 1.1.2.6
460 salcianu 1.8 if(PointerAnalysis.FINE_TIMING) {
461 salcianu 1.8 long delta = System.currentTimeMillis() - b_time;
462 salcianu 1.8 total_mapping_time += delta;
463 salcianu 1.8 b_time = System.currentTimeMillis();
464 salcianu 1.8 }
465 salcianu 1.1.2.1
466 salcianu 1.8 PAEdgeSet old_caller_I =
467 salcianu 1.8 PointerAnalysis.RECORD_ACTIONS ?
468 salcianu 1.8 (PAEdgeSet) pig_caller.G.I.clone() : null;
469 salcianu 1.1.2.54
470 salcianu 1.1.2.10 // Inserts the image of the callee's graph into the caller's graph.
471 salcianu 1.1.2.10 Set params = new HashSet();
472 salcianu 1.1.2.54 for(int i = 0; i < callee_params.length; i++)
473 salcianu 1.1.2.54 if(!pig_callee.tau.isStarted(callee_params[i]))
474 salcianu 1.1.2.54 params.add(callee_params[i]);
475 salcianu 1.8
476 salcianu 1.8 Set ppgRoots = new HashSet();
477 salcianu 1.8 pig_caller.insertAllButArEo
478 salcianu 1.8 (pig_callee, mu, false, params, ppgRoots, false);
479 salcianu 1.1.2.10
480 salcianu 1.1.2.10 // bring the actions of the callee into the caller's graph
481 salcianu 1.1.2.48 if(PointerAnalysis.RECORD_ACTIONS)
482 salcianu 1.1.2.48 bring_actions(pig_caller.ar, pig_callee.ar,
483 salcianu 1.1.2.48 pig_caller.tau.activeThreadSet(), mu);
484 salcianu 1.1.2.5
485 salcianu 1.1.2.10 // bring the edge ordering relation into the caller's graph
486 salcianu 1.1.2.26 if(!PointerAnalysis.IGNORE_EO)
487 salcianu 1.1.2.26 bring_eo(pig_caller.eo, old_caller_I, pig_callee.eo,
488 salcianu 1.1.2.26 pig_callee.G.O, mu);
489 salcianu 1.1.2.10
490 salcianu 1.8 if(PointerAnalysis.FINE_TIMING) { // TIMING
491 salcianu 1.8 long delta = System.currentTimeMillis() - b_time;
492 salcianu 1.8 total_merging_time += delta;
493 salcianu 1.8 b_time = System.currentTimeMillis();
494 salcianu 1.8 }
495 salcianu 1.8
496 salcianu 1.1.2.10 // recompute the escape info
497 salcianu 1.8 pig_caller.G.propagate(ppgRoots);
498 salcianu 1.11
499 salcianu 1.8 if(PointerAnalysis.FINE_TIMING) {
500 salcianu 1.8 long delta = System.currentTimeMillis() - b_time;
501 salcianu 1.8 total_propagate_time += delta;
502 salcianu 1.8 b_time = System.currentTimeMillis();
503 salcianu 1.8 }
504 salcianu 1.1.2.10
505 salcianu 1.1.2.10 // simplify the graph by removing the empty loads
506 salcianu 1.1.2.10 pig_caller.removeEmptyLoads();
507 salcianu 1.8
508 salcianu 1.8 if(PointerAnalysis.FINE_TIMING) {
509 salcianu 1.8 long delta = System.currentTimeMillis() - b_time;
510 salcianu 1.8 total_cleaning_time += delta;
511 salcianu 1.8 b_time = System.currentTimeMillis();
512 salcianu 1.8 }
513 salcianu 1.1.2.10
514 salcianu 1.1.2.18 // make a copy of the parallel interaction graph
515 salcianu 1.1.2.18 ParIntGraph pig_caller1 = (ParIntGraph) (pig_caller.clone());
516 salcianu 1.8
517 salcianu 1.1.2.18 // set the edges for the exception on the out-edge 1
518 salcianu 1.1.2.18 set_edges_res_ex(q.retex() , mu, pig_caller1, pig_callee.G.excp);
519 salcianu 1.1.2.18 // set the edges for the result on the out-edge 0
520 salcianu 1.1.2.18 set_edges_res_ex(q.retval(), mu, pig_caller, pig_callee.G.r);
521 salcianu 1.1.2.1
522 salcianu 1.11 /*
523 salcianu 1.8 if(DEBUG) {
524 salcianu 1.1.2.18 System.out.println("Final graphs:{");
525 salcianu 1.1.2.18 System.out.println(" The graph on edge 0:");
526 salcianu 1.1.2.10 System.out.println(pig_caller);
527 salcianu 1.1.2.18 System.out.println(" The graph on edge 1:");
528 salcianu 1.1.2.18 System.out.println(pig_caller1);
529 salcianu 1.1.2.18 System.out.println("}");
530 salcianu 1.1.2.10 }
531 salcianu 1.11 */
532 salcianu 1.1.2.10
533 salcianu 1.1.2.18 return new ParIntGraphPair(pig_caller, pig_caller1);
534 salcianu 1.1.2.1 }
535 salcianu 1.1.2.54
536 salcianu 1.8 static long total_mapping_time = 0;
537 salcianu 1.8 static long total_merging_time = 0;
538 salcianu 1.8 static long total_propagate_time = 0;
539 salcianu 1.8 static long total_cleaning_time = 0;
540 salcianu 1.8 static long total_interproc_time = 0;
541 salcianu 1.1.2.54
542 salcianu 1.11
543 salcianu 1.11 private static PANode[] get_params4native
544 salcianu 1.11 (MetaMethod mm, PointerAnalysis pa) {
545 salcianu 1.11
546 salcianu 1.11 HMethod hm = mm.getHMethod();
547 salcianu 1.11 assert Modifier.isNative(hm.getModifiers());
548 salcianu 1.11
549 salcianu 1.11 HClass[] types = hm.getParameterTypes();
550 salcianu 1.11 int count =
551 salcianu 1.11 java.lang.reflect.Modifier.isStatic(hm.getModifiers()) ? 0 : 1;
552 salcianu 1.11 for(int i = 0; i < types.length; i++)
553 salcianu 1.11 if(!types[i].isPrimitive()) count++;
554 salcianu 1.11
555 salcianu 1.11 pa.getNodeRepository().addParamNodes(mm, count);
556 salcianu 1.11 return pa.getParamNodes(mm);
557 salcianu 1.11 }
558 salcianu 1.11
559 salcianu 1.11
560 salcianu 1.1.2.54 // Conversion array -> set
561 salcianu 1.1.2.54 private static final Set array2set(Object[] array) {
562 salcianu 1.1.2.54 Set result = new HashSet();
563 salcianu 1.1.2.54 for(int i = 0; i < array.length; i++)
564 salcianu 1.1.2.54 result.add(array[i]);
565 salcianu 1.1.2.54 return result;
566 salcianu 1.1.2.54 }
567 salcianu 1.1.2.54
568 salcianu 1.1.2.54 // activates the use of the new mapping constraints
569 salcianu 1.1.2.54 private static boolean NEW_MAPPING_CONSTRAINTS = false;
570 salcianu 1.1.2.54 public static boolean VERY_NEW_MAPPINGS = true;
571 salcianu 1.6
572 salcianu 1.6 // activates the use of constraints from Alex Salcianu's thesis.
573 salcianu 1.6 private static boolean THESIS_MAPPING_CONSTRAINTS = true;
574 salcianu 1.1.2.54 static {
575 salcianu 1.6 if(THESIS_MAPPING_CONSTRAINTS)
576 salcianu 1.6 System.out.println("InterProcPA: Alex Salcianu's SM thesis");
577 salcianu 1.9 System.out.println("MAX_CALLEES = " + MAX_CALLEES);
578 salcianu 1.6 }
579 salcianu 1.6
580 salcianu 1.6 // generates lots of debug messages about the construction of mu
581 salcianu 1.1.2.54 private static boolean DEBUG_MU = false;
582 salcianu 1.1.2.54
583 salcianu 1.1.2.54 // Computes the mapping mu of the callee nodes
584 salcianu 1.1.2.54 private static Relation compute_mapping
585 salcianu 1.1.2.54 (CALL q,
586 salcianu 1.1.2.54 ParIntGraph pig_caller, ParIntGraph pig_callee,
587 salcianu 1.11 PANode[] callee_params,
588 salcianu 1.11 PointerAnalysis pa) {
589 salcianu 1.1.2.54
590 salcianu 1.1.2.54 // use the new mapping constraints, if asked to do so
591 salcianu 1.6 if(THESIS_MAPPING_CONSTRAINTS)
592 salcianu 1.6 return ComputeInterProcMuClosure.computeInterProcMu
593 salcianu 1.11 (q, pig_caller, pig_callee, callee_params, pa);
594 salcianu 1.1.2.54
595 salcianu 1.1.2.54 // get the initial mapping: formal param -> actual parameter,
596 salcianu 1.1.2.54 // and class node -> class node
597 salcianu 1.1.2.54 Relation mu =
598 salcianu 1.1.2.54 get_initial_mapping(q, pig_caller, pig_callee, callee_params);
599 salcianu 1.1.2.54
600 salcianu 1.1.2.54 if(DEBUG_MU) System.out.println("Initial mapping:" + mu);
601 salcianu 1.1.2.54
602 salcianu 1.1.2.54 // update the node mapping by matching outside edges from the caller
603 salcianu 1.1.2.54 // with inside edges from the callee
604 salcianu 1.1.2.54 Set redundant_ln = new HashSet();
605 salcianu 1.1.2.54 match_edges(mu, pig_caller, pig_callee, redundant_ln);
606 salcianu 1.1.2.54
607 salcianu 1.1.2.54 if(DEBUG_MU) System.out.println("After matching edges:" + mu);
608 salcianu 1.1.2.54
609 salcianu 1.1.2.54 // all the nodes from the caller (except for PARAM) are
610 salcianu 1.1.2.54 // initially inserted into the caller's graph
611 salcianu 1.1.2.54 compute_the_final_mapping(mu, pig_callee, redundant_ln);
612 salcianu 1.1.2.54
613 salcianu 1.1.2.54 if(DEBUG_MU) System.out.println("Final mapping:" + mu);
614 salcianu 1.1.2.54
615 salcianu 1.1.2.54 return mu;
616 salcianu 1.1.2.54 }
617 salcianu 1.1.2.1
618 salcianu 1.1.2.40
619 salcianu 1.1.2.1 /** Sets the initial mapping: each formal parameter is mapped
620 salcianu 1.1.2.1 * to the nodes pointed to by the corresponding actual argument
621 salcianu 1.1.2.1 * (into the caller graph) and each static node is mapped to itself.
622 salcianu 1.1.2.1 * (only the static nodes that really point to something are important,
623 salcianu 1.1.2.1 * the leaf static nodes are not interesting in our analysis)
624 salcianu 1.1.2.1 */
625 salcianu 1.1.2.1 private static Relation get_initial_mapping(CALL q,
626 salcianu 1.1.2.1 ParIntGraph pig_caller,
627 salcianu 1.1.2.1 ParIntGraph pig_callee,
628 salcianu 1.1.2.49 PANode[] callee_params) {
629 salcianu 1.1.2.48 Relation mu = new RelationImpl();
630 salcianu 1.1.2.54
631 salcianu 1.1.2.54 // first, map the parameter nodes to the actual nodes being passed
632 salcianu 1.1.2.54 // as arguments in the call q
633 salcianu 1.1.2.54 map_parameters(mu, q, pig_caller, callee_params);
634 salcianu 1.1.2.54
635 salcianu 1.1.2.54 // next, map the static nodes to themselves;
636 salcianu 1.1.2.54 // only the static nodes that appear as sources of the outside edges
637 salcianu 1.1.2.54 // must be initially mapped
638 salcianu 1.1.2.54 process_STATICs(pig_callee.G.O.allSourceNodes(), mu);
639 salcianu 1.1.2.54
640 salcianu 1.1.2.54 return mu;
641 salcianu 1.1.2.54 }
642 salcianu 1.1.2.54
643 salcianu 1.1.2.54
644 salcianu 1.6 // Update the mapping mu to contain the mappings for the parameter nodes
645 salcianu 1.1.2.54 private static void map_parameters
646 salcianu 1.6 (Relation mu, CALL call,
647 salcianu 1.6 ParIntGraph pig_caller, PANode[] callee_params) {
648 salcianu 1.6 Temp[] args = call.params();
649 salcianu 1.1.2.2 int object_params_count = 0;
650 salcianu 1.1.2.2 // map the object formal parameter nodes to the actual arguments
651 salcianu 1.1.2.2 for(int i = 0; i < args.length; i++)
652 salcianu 1.6 if(!call.paramType(i).isPrimitive()) {
653 salcianu 1.1.2.2 mu.addAll(callee_params[object_params_count],
654 salcianu 1.1.2.2 pig_caller.G.I.pointedNodes(args[i]));
655 salcianu 1.1.2.2 object_params_count++;
656 salcianu 1.1.2.2 }
657 salcianu 1.6
658 salcianu 1.6 assert object_params_count == callee_params.length :
659 salcianu 1.6 "\tDifferent numbers of object formals (" +
660 salcianu 1.6 callee_params.length + ") and object arguments (" +
661 salcianu 1.7 object_params_count + ") for \n\t" + Util.code2str(call);
662 salcianu 1.6 }
663 salcianu 1.1.2.2
664 salcianu 1.1.2.1
665 salcianu 1.1.2.46 // aux method for get_initial_mapping
666 salcianu 1.1.2.46 private static void process_STATICs(final Set set, final Relation mu) {
667 cananian 1.12 for(Object nodeO : set) {
668 cananian 1.12 PANode node = (PANode) nodeO;
669 salcianu 1.1.2.46 if(node.type == PANode.STATIC)
670 salcianu 1.1.2.47 mu.add(node, node);
671 salcianu 1.1.2.46 }
672 salcianu 1.1.2.46 }
673 salcianu 1.1.2.1
674 salcianu 1.1.2.1 /** Matches outside edges from the graph of (used by ) the callee
675 salcianu 1.1.2.4 against inside edges from the graph of (created by) the caller.
676 salcianu 1.1.2.10 (repeated application of constraint 2). The goal of this method is
677 salcianu 1.1.2.54 to resolve the load nodes from the callee, i.e. to detect the
678 salcianu 1.1.2.10 nodes from the caller that each load node might represent. */
679 salcianu 1.1.2.1 private static void match_edges(Relation mu,
680 salcianu 1.1.2.1 ParIntGraph pig_caller,
681 salcianu 1.1.2.49 ParIntGraph pig_callee,
682 salcianu 1.1.2.49 final Set redundant_ln) {
683 salcianu 1.1.2.10
684 salcianu 1.1.2.1 PAWorkList W = new PAWorkList();
685 salcianu 1.1.2.4 // here is the new stuff; only nodes with new stuff are
686 salcianu 1.1.2.1 // put in the worklist W.
687 salcianu 1.1.2.1 Relation new_info = (Relation) mu.clone();
688 salcianu 1.1.2.1
689 salcianu 1.1.2.47 W.addAll(mu.keys());
690 salcianu 1.1.2.49 while(!W.isEmpty()) {
691 salcianu 1.1.2.1 PANode node1 = (PANode) W.remove();
692 salcianu 1.1.2.4
693 salcianu 1.1.2.4 // nodes3 stands for all the new instances of n3
694 salcianu 1.1.2.4 // from the inference rule
695 salcianu 1.1.2.47 HashSet nodes3 = new HashSet(new_info.getValues(node1));
696 salcianu 1.1.2.47 new_info.removeKey(node1);
697 salcianu 1.1.2.4
698 cananian 1.12 for (Object fO : pig_callee.G.O.allFlagsForNode(node1)) {
699 cananian 1.12 String f = (String) fO;
700 salcianu 1.1.2.49 // 1. matching outside edges/callee against inside edges/caller
701 salcianu 1.1.2.1 // nodes2 stands for all the nodes that could play
702 salcianu 1.1.2.1 // the role of n2 from the inference rule
703 salcianu 1.1.2.49 Set nodes2 = pig_callee.G.O.pointedNodes(node1, f);
704 salcianu 1.1.2.1 if(nodes2.isEmpty()) continue;
705 salcianu 1.1.2.1
706 salcianu 1.1.2.1 // nodes4 stands for all the nodes that could play
707 salcianu 1.1.2.1 // the role of n4 from the inference rule
708 salcianu 1.1.2.49 Set nodes4 = pig_caller.G.I.pointedNodes(nodes3, f);
709 salcianu 1.1.2.49 if(!nodes4.isEmpty()) {
710 salcianu 1.1.2.49 // set up the relation from any node from nodes2
711 salcianu 1.1.2.49 // to any node from nodes4
712 cananian 1.12 for(Object node2O : nodes2) {
713 cananian 1.12 PANode node2 = (PANode) node2O;
714 salcianu 1.1.2.49 boolean changed = false;
715 cananian 1.12 for(Object node4O : nodes4) {
716 cananian 1.12 PANode node4 = (PANode) node4O;
717 salcianu 1.1.2.49 if(mu.add(node2,node4)){
718 salcianu 1.1.2.49 changed = true;
719 salcianu 1.1.2.49 new_info.add(node2, node4);
720 salcianu 1.1.2.49 }
721 salcianu 1.1.2.49 }
722 salcianu 1.1.2.49 // nodes with new info are put in the worklist
723 salcianu 1.1.2.49 if(changed) W.add(node2);
724 salcianu 1.1.2.49 }
725 salcianu 1.1.2.49 }
726 salcianu 1.1.2.49
727 salcianu 1.1.2.49 // 2.matching outside edges/callee against outside edges/caller
728 salcianu 1.1.2.49 nodes4 = pig_caller.G.O.pointedNodes(nodes3, f);
729 salcianu 1.1.2.49 if(!nodes4.isEmpty()) {
730 salcianu 1.1.2.49 // set up the relation from any node from nodes2
731 salcianu 1.1.2.49 // to any node from nodes4
732 cananian 1.12 for(Object node2O : nodes2) {
733 cananian 1.12 PANode node2 = (PANode) node2O;
734 salcianu 1.1.2.49 int type2 = node2.type();
735 salcianu 1.1.2.49 boolean changed = false;
736 cananian 1.12 for(Object node4O : nodes4) {
737 cananian 1.12 PANode node4 = (PANode) node4O;
738 salcianu 1.1.2.49 if(mu.add(node2, node4)) {
739 salcianu 1.1.2.49 changed = true;
740 salcianu 1.1.2.49 new_info.add(node2, node4);
741 salcianu 1.1.2.49 if((type2 == PANode.LOAD) &&
742 salcianu 1.1.2.49 (node4.type() == PANode.LOAD))
743 salcianu 1.1.2.49 redundant_ln.add(node2);
744 salcianu 1.1.2.49 }
745 salcianu 1.1.2.1 }
746 salcianu 1.1.2.49 // nodes with new info are put in the worklist
747 salcianu 1.1.2.49 if(changed) W.add(node2);
748 salcianu 1.1.2.1 }
749 salcianu 1.1.2.1 }
750 salcianu 1.1.2.1 }
751 salcianu 1.1.2.1 }
752 salcianu 1.1.2.1 }
753 salcianu 1.1.2.1
754 salcianu 1.1.2.10 // Initially, all the nodes from the callee are put into the caller's
755 salcianu 1.1.2.10 // graph except for the PARAM nodes. Later, after recomputing the
756 salcianu 1.1.2.54 // escape info, the empty load nodes will be removed (together with
757 salcianu 1.1.2.10 // the related information)
758 salcianu 1.1.2.49 private static void compute_the_final_mapping
759 salcianu 1.1.2.49 (final Relation mu,
760 salcianu 1.1.2.49 final ParIntGraph pig_callee,
761 salcianu 1.1.2.49 final Set redundant_ln) {
762 salcianu 1.1.2.10 pig_callee.forAllNodes(new PANodeVisitor(){
763 salcianu 1.1.2.10 public void visit(PANode node){
764 salcianu 1.1.2.49 int type = node.type();
765 salcianu 1.1.2.49 if(type == PANode.LOAD) {
766 salcianu 1.1.2.49 if(!redundant_ln.contains(node))
767 salcianu 1.1.2.49 mu.add(node, node);
768 salcianu 1.1.2.49 return;
769 salcianu 1.1.2.49 }
770 salcianu 1.1.2.49 if(type != PANode.PARAM)
771 salcianu 1.1.2.49 mu.add(node, node);
772 salcianu 1.1.2.1 }
773 salcianu 1.1.2.10 });
774 salcianu 1.1.2.49 }
775 salcianu 1.1.2.49
776 salcianu 1.1.2.54
777 salcianu 1.1.2.1 /** Sets the edges for the result or the exception returned by the callee.
778 salcianu 1.1.2.1 * Remember the syntax of a method invocation:
779 salcianu 1.1.2.1 * <code><retval,retexc> = CALL (...)</code>. */
780 salcianu 1.1.2.1 private static void set_edges_res_ex(Temp l, Relation mu,
781 salcianu 1.1.2.24 ParIntGraph pig_caller, Set nodes){
782 salcianu 1.1.2.1 if(l == null) return;
783 salcianu 1.1.2.3 /// System.out.println("Setting the edges for " + l);
784 salcianu 1.1.2.1 pig_caller.G.I.removeEdges(l);
785 salcianu 1.1.2.1 Set mu_nodes = new HashSet();
786 salcianu 1.1.2.1 Iterator it = nodes.iterator();
787 salcianu 1.1.2.1 while(it.hasNext())
788 salcianu 1.1.2.47 mu_nodes.addAll(mu.getValues((PANode) it.next()));
789 salcianu 1.1.2.1 pig_caller.G.I.addEdges(l,mu_nodes);
790 salcianu 1.1.2.1 }
791 salcianu 1.1.2.1
792 salcianu 1.1.2.7
793 salcianu 1.1.2.7 private static void bring_actions(final ActionRepository ar_caller,
794 salcianu 1.1.2.7 final ActionRepository ar_callee,
795 salcianu 1.1.2.7 final Set active_threads_in_caller,
796 salcianu 1.8 final Relation mu) {
797 salcianu 1.1.2.7 // Add this "common-sense" rule to the mapping: the inter-procedural
798 salcianu 1.1.2.7 // analysis stays in the same thread.
799 salcianu 1.1.2.48 mu.add(ActionRepository.THIS_THREAD, ActionRepository.THIS_THREAD);
800 salcianu 1.1.2.7
801 salcianu 1.1.2.7 // Step 1. Put all the actions from the callee as being executed
802 salcianu 1.1.2.7 // in // with all the threads that are active in the caller.
803 salcianu 1.1.2.7 ActionVisitor act_visitor = new ActionVisitor(){
804 salcianu 1.1.2.7 public void visit_ld(PALoad load){
805 salcianu 1.1.2.7 if(!mu.contains(load.n2,load.n2)) return;
806 salcianu 1.1.2.47 ar_caller.add_ld(mu.getValues(load.n1),
807 salcianu 1.1.2.7 load.f,
808 salcianu 1.1.2.7 load.n2,
809 salcianu 1.1.2.47 mu.getValues(load.nt),
810 salcianu 1.1.2.7 active_threads_in_caller);
811 salcianu 1.1.2.7 }
812 salcianu 1.1.2.19 public void visit_sync(PASync sync){
813 salcianu 1.1.2.19 ar_caller.add_sync(sync.project(mu),
814 salcianu 1.1.2.7 active_threads_in_caller);
815 salcianu 1.1.2.7 }
816 salcianu 1.1.2.7 };
817 salcianu 1.1.2.7
818 salcianu 1.1.2.7 ar_callee.forAllActions(act_visitor);
819 salcianu 1.1.2.7
820 salcianu 1.1.2.7 // Step 2. Translate the "parallel action" items of information from
821 salcianu 1.1.2.7 // the callee, by applying the mu function on their components
822 salcianu 1.1.2.7 // (except for the n2 componenent of a load action which is left
823 salcianu 1.1.2.7 // unchanged if it's still present in the new graph.
824 salcianu 1.1.2.7 ParActionVisitor par_act_visitor = new ParActionVisitor(){
825 salcianu 1.1.2.7 public void visit_par_ld(PALoad load, PANode nt2){
826 salcianu 1.1.2.7 if(!mu.contains(load.n2,load.n2)) return;
827 salcianu 1.1.2.47 ar_caller.add_ld(mu.getValues(load.n1),
828 salcianu 1.1.2.7 load.f,
829 salcianu 1.1.2.7 load.n2,
830 salcianu 1.1.2.47 mu.getValues(load.nt),
831 salcianu 1.1.2.47 mu.getValues(nt2));
832 salcianu 1.1.2.7 }
833 salcianu 1.1.2.19 public void visit_par_sync(PASync sync, PANode nt2){
834 salcianu 1.1.2.19 ar_caller.add_sync(sync.project(mu),
835 salcianu 1.1.2.47 mu.getValues(nt2));
836 salcianu 1.1.2.7 }
837 salcianu 1.1.2.7 };
838 salcianu 1.1.2.7
839 salcianu 1.1.2.7 ar_callee.forAllParActions(par_act_visitor);
840 salcianu 1.1.2.7 }
841 salcianu 1.1.2.7
842 salcianu 1.1.2.40
843 salcianu 1.1.2.10 // Inserts the edge ordering relation of the callee into the graph of
844 salcianu 1.1.2.10 // the caller. In addition, records the fact that all the outside edges
845 salcianu 1.1.2.10 // from the callee appear after all the inside edges of the caller.
846 salcianu 1.1.2.10 private static void bring_eo(final EdgeOrdering eo_caller,
847 salcianu 1.1.2.10 final PAEdgeSet callerI,
848 salcianu 1.1.2.10 final EdgeOrdering eo_callee,
849 salcianu 1.1.2.10 final PAEdgeSet calleeO,
850 salcianu 1.1.2.10 final Relation mu){
851 salcianu 1.1.2.10
852 salcianu 1.1.2.10 eo_callee.forAllEntries(new RelationEntryVisitor(){
853 salcianu 1.1.2.10 public void visit(Object key, Object value){
854 salcianu 1.1.2.11 PAEdge eo = (PAEdge) key;
855 salcianu 1.1.2.11 PAEdge ei = (PAEdge) value;
856 salcianu 1.1.2.11 // make sure eo will appear into the new graph
857 salcianu 1.1.2.10 if(!mu.contains(eo.n2,eo.n2)) return;
858 salcianu 1.1.2.11
859 salcianu 1.1.2.47 Set ei_n1_set = mu.getValues(ei.n1);
860 salcianu 1.1.2.11 if(ei_n1_set.isEmpty()) return;
861 salcianu 1.1.2.47 Set ei_n2_set = mu.getValues(ei.n2);
862 salcianu 1.1.2.11 if(ei_n2_set.isEmpty()) return;
863 salcianu 1.1.2.47 Set eo_n1_set = mu.getValues(eo.n1);
864 salcianu 1.1.2.11 if(eo_n1_set.isEmpty()) return;
865 salcianu 1.1.2.11
866 cananian 1.12 for (Object ei_n1O : ei_n1_set){
867 cananian 1.12 PANode ei_n1 = (PANode) ei_n1O;
868 cananian 1.12 for (Object ei_n2O : ei_n2_set){
869 cananian 1.12 PANode ei_n2 = (PANode) ei_n2O;
870 salcianu 1.1.2.10 PAEdge new_ei = new PAEdge(ei_n1,ei.f,ei_n2);
871 cananian 1.12 for (Object eo_n1O : eo_n1_set){
872 cananian 1.12 PANode eo_n1 = (PANode) eo_n1O;
873 salcianu 1.1.2.10 eo_caller.add(new PAEdge(eo_n1,ei.f,eo.n2),
874 salcianu 1.1.2.10 new_ei);
875 salcianu 1.1.2.10 }
876 salcianu 1.1.2.10 }
877 salcianu 1.1.2.10 }
878 salcianu 1.1.2.10 }
879 salcianu 1.1.2.10 });
880 salcianu 1.1.2.7
881 salcianu 1.1.2.7
882 salcianu 1.1.2.10 // all the outside edges from the callee occur *after* all
883 salcianu 1.1.2.10 // the inside edges that exist in the caller right before the CALL
884 salcianu 1.1.2.10 calleeO.forAllEdges(new PAEdgeVisitor(){
885 salcianu 1.1.2.10 public void visit(Temp var, PANode node){}
886 salcianu 1.1.2.10 public void visit(PANode n1, String f, PANode n2){
887 salcianu 1.1.2.10 if(!mu.contains(n2,n2)) return;
888 salcianu 1.1.2.47 eo_caller.add(mu.getValues(n1),f,n2,callerI);
889 salcianu 1.1.2.10 }
890 salcianu 1.1.2.10 });
891 salcianu 1.1.2.10 }
892 salcianu 1.1.2.7
893 salcianu 1.1.2.40
894 salcianu 1.1.2.22 // Treats some native methods in a special way. Returns a pair of
895 salcianu 1.1.2.22 // ParIntGraphs or null if it cannot handle this call.
896 salcianu 1.1.2.44 private static ParIntGraphPair treatVerySpecialNatives
897 salcianu 1.1.2.44 (PointerAnalysis pa, CALL q, ParIntGraph pig_before){
898 salcianu 1.1.2.7
899 salcianu 1.1.2.22 HMethod hm = q.method();
900 salcianu 1.1.2.23 if(hm == null) return null;
901 salcianu 1.1.2.32 ParIntGraphPair pair = null;
902 salcianu 1.1.2.7
903 salcianu 1.1.2.32 if((pair = treat_arraycopy(pa, q, pig_before)) != null)
904 salcianu 1.1.2.32 return pair;
905 salcianu 1.1.2.32 if((pair = treat_clone(pa, q, pig_before)) != null)
906 salcianu 1.1.2.32 return pair;
907 salcianu 1.1.2.32
908 salcianu 1.1.2.32 return null;
909 salcianu 1.1.2.32 }
910 salcianu 1.1.2.32
911 salcianu 1.1.2.33
912 salcianu 1.1.2.33 // Aux method for treat_clone. It returns the set of possible types
913 salcianu 1.1.2.33 // (Set<HClass>) of the argument of clone(). Ugly code: I think we should
914 salcianu 1.1.2.33 // have a Quad form with types.
915 salcianu 1.1.2.33 private static Set aux_clone_get_types(CALL q){
916 salcianu 1.1.2.33 // The quad factory that generated this CALL quad
917 salcianu 1.1.2.33 QuadFactory qf = q.getFactory();
918 salcianu 1.1.2.33 // the method into which it appears.
919 salcianu 1.1.2.33 HMethod hm = qf.getMethod();
920 salcianu 1.1.2.33 // and the HCode containing the code of that method.
921 salcianu 1.1.2.33 HCode hcode = (HCode) qf.getParent();
922 salcianu 1.1.2.33 // et = Temp q.params(0) used in Quad q
923 salcianu 1.1.2.33 ExactTemp et = new ExactTemp(q, q.params(0));
924 salcianu 1.1.2.33
925 salcianu 1.1.2.33 TypeInference ti =
926 salcianu 1.1.2.33 new TypeInference(hm, hcode, Collections.singleton(et));
927 salcianu 1.1.2.33
928 salcianu 1.1.2.33 return ti.getType(et);
929 salcianu 1.1.2.33 }
930 salcianu 1.1.2.33
931 salcianu 1.1.2.40
932 salcianu 1.1.2.33 // Aux method for "treat_clone". Returns the set of all the fields
933 salcianu 1.1.2.33 // appearing in the types from the set "types".
934 salcianu 1.1.2.33 private static Set aux_clone_get_obj_fields(Set types){
935 salcianu 1.1.2.33 Set retval = new HashSet();
936 cananian 1.12 for(Object hclassO : types){
937 cananian 1.12 HClass hclass = (HClass) hclassO;
938 salcianu 1.8 if(hclass.isArray()) {
939 salcianu 1.1.2.33 System.out.println("CLONE: might be called for an array");
940 salcianu 1.8 retval.add(PointerAnalysis.ARRAY_CONTENT);
941 salcianu 1.8 }
942 salcianu 1.8 else {
943 salcianu 1.8 HField[] hfields = hclass.getFields();
944 salcianu 1.8 for(int i = 0; i < hfields.length; i++)
945 salcianu 1.8 if(!hfields[i].getType().isPrimitive())
946 salcianu 1.8 retval.add(PointerAnalysis.getFieldName(hfields[i]));
947 salcianu 1.8 }
948 salcianu 1.1.2.33 }
949 salcianu 1.1.2.33 return retval;
950 salcianu 1.1.2.33 }
951 salcianu 1.1.2.33
952 salcianu 1.1.2.33
953 salcianu 1.1.2.33 // Treat the sequence "ld t = n_src.f; store n_R.f = t;". For a clone()
954 salcianu 1.1.2.33 // call, this is done for all fields f of the cloned object.
955 salcianu 1.1.2.33 private static void aux_clone_treat_pseudo_ldst(CALL q, String f,
956 salcianu 1.1.2.33 PANode n_R, PANode n_src, ParIntGraph pig, NodeRepository node_rep){
957 salcianu 1.1.2.33
958 salcianu 1.1.2.33 // f_set contains all the nodes pointed to by <n_src, f>
959 salcianu 1.1.2.33 Set f_set = new HashSet(pig.G.I.pointedNodes(n_src, f));
960 salcianu 1.1.2.33
961 salcianu 1.1.2.33 if(pig.G.escaped(n_src)){
962 salcianu 1.1.2.33 PANode n_L = node_rep.getLoadNodeSpecial(q, f);
963 salcianu 1.1.2.33 pig.G.O.addEdge(n_src, f, n_L);
964 salcianu 1.1.2.48 if(PointerAnalysis.RECORD_ACTIONS)
965 salcianu 1.1.2.48 pig.ar.add_ld(n_src, f, n_L, ActionRepository.THIS_THREAD,
966 salcianu 1.1.2.48 pig.tau.activeThreadSet());
967 salcianu 1.1.2.48 if(!PointerAnalysis.IGNORE_EO) {
968 salcianu 1.1.2.48 // TODO: edge ordering relation (if we want to maintain it)
969 cananian 1.3.2.1 assert false : "edge ordering not implemented here!";
970 salcianu 1.1.2.48 }
971 salcianu 1.1.2.33 f_set.add(n_L);
972 salcianu 1.1.2.33 }
973 salcianu 1.1.2.33
974 salcianu 1.1.2.33 for(Iterator it = f_set.iterator(); it.hasNext();)
975 salcianu 1.1.2.33 pig.G.I.addEdge(n_R, f, (PANode) it.next());
976 salcianu 1.1.2.33 }
977 salcianu 1.1.2.33
978 salcianu 1.1.2.33
979 salcianu 1.1.2.32 // Specially treats
980 salcianu 1.1.2.32 // "protected native java.lang.Object java.lang.Object.clone()"
981 salcianu 1.1.2.32 private static ParIntGraphPair treat_clone(PointerAnalysis pa, CALL q,
982 salcianu 1.1.2.32 ParIntGraph pig_before){
983 salcianu 1.1.2.33 HMethod callee = q.method();
984 salcianu 1.1.2.33 if(!callee.getName().equals("clone") ||
985 salcianu 1.1.2.33 !callee.getDeclaringClass().getName().equals("java.lang.Object"))
986 salcianu 1.1.2.32 return null;
987 salcianu 1.1.2.32
988 salcianu 1.1.2.52 if(DEBUG)
989 salcianu 1.1.2.44 System.out.println("NATIVE (special): " + callee);
990 salcianu 1.1.2.44
991 salcianu 1.1.2.33 ParIntGraph pig_after0 = pig_before;
992 salcianu 1.1.2.33 ParIntGraph pig_after1 = (ParIntGraph) pig_before.clone();
993 salcianu 1.1.2.33
994 salcianu 1.1.2.33 // do the actions of the "clone()" method: create a new object (n_R),
995 salcianu 1.1.2.33 // copy the fields from the objects passed as params to clone to n_R
996 salcianu 1.8 NodeRepository node_rep = pa.getNodeRepository();
997 salcianu 1.8 // [AS] clone is a special way of creating objects; therefore,
998 salcianu 1.8 // it returns an INSIDE node, not a RETURN node. This also
999 salcianu 1.8 // protects us against losses of precision if we coalesce all
1000 salcianu 1.8 // RETURN nodes into LOST.
1001 salcianu 1.8 PANode n_R = node_rep.getCodeNode(q, PANode.INSIDE2);
1002 salcianu 1.1.2.33
1003 salcianu 1.1.2.33 Set lo_types = aux_clone_get_types(q);
1004 salcianu 1.1.2.39 if(DEBUG)
1005 salcianu 1.1.2.33 System.out.println("CLONE: POSSIBLE TYPES:" + lo_types);
1006 salcianu 1.1.2.33
1007 salcianu 1.1.2.33 Set flags = aux_clone_get_obj_fields(lo_types);
1008 salcianu 1.1.2.39 if(DEBUG)
1009 salcianu 1.1.2.33 System.out.println("CLONE: POSSIBLE FLAGS:" + flags);
1010 salcianu 1.1.2.33
1011 salcianu 1.1.2.33 int nb_flags = flags.size();
1012 salcianu 1.1.2.33
1013 salcianu 1.1.2.33 Temp lo = q.params(0);
1014 salcianu 1.1.2.33 Set srcs = pig_before.G.I.pointedNodes(lo);
1015 salcianu 1.1.2.33
1016 salcianu 1.1.2.33 Iterator it = flags.iterator();
1017 salcianu 1.1.2.33 for(int i = 0; i < nb_flags; i++){
1018 salcianu 1.1.2.33 String f = (String) it.next();
1019 cananian 1.12 for(Object n_srcO : srcs){
1020 cananian 1.12 PANode n_src = (PANode) n_srcO;
1021 salcianu 1.1.2.33 aux_clone_treat_pseudo_ldst(q, f, n_R, n_src, pig_after0,
1022 salcianu 1.1.2.33 node_rep);
1023 salcianu 1.1.2.33 }
1024 salcianu 1.1.2.33 }
1025 salcianu 1.1.2.33
1026 salcianu 1.1.2.33 // set the link l_R to the RETURN node
1027 salcianu 1.1.2.33 Temp l_R = q.retval();
1028 salcianu 1.1.2.33 if(l_R != null)
1029 salcianu 1.1.2.33 pig_after0.G.I.addEdge(l_R, n_R);
1030 salcianu 1.1.2.33
1031 salcianu 1.1.2.33 aux_native_treat_excp(q, pig_after1, node_rep);
1032 salcianu 1.1.2.33
1033 salcianu 1.1.2.33 return new ParIntGraphPair(pig_after0, pig_after1);
1034 salcianu 1.1.2.33 }
1035 salcianu 1.1.2.33
1036 salcianu 1.1.2.33
1037 salcianu 1.1.2.33 // Aux method for all the special treatments of native methods. If the
1038 salcianu 1.1.2.33 // called native method can return an exception, and there is a Temp l_E
1039 salcianu 1.1.2.33 // to receive (a pointer to) it, a PANode.EXCEPT node associated with this
1040 salcianu 1.1.2.33 // CALL is created (if it doesn't exist yet) and the proper link is set
1041 salcianu 1.1.2.33 // from l_E to n_E, in the parallel interaction graph "pig".
1042 salcianu 1.1.2.33 private static void aux_native_treat_excp(CALL q, ParIntGraph pig,
1043 salcianu 1.1.2.33 NodeRepository node_rep){
1044 salcianu 1.1.2.33 Temp l_E = q.retex();
1045 salcianu 1.1.2.33 HMethod hm = q.method();
1046 salcianu 1.1.2.33
1047 salcianu 1.1.2.33 if((l_E == null) || (hm.getExceptionTypes().length == 0)) return;
1048 salcianu 1.1.2.33
1049 salcianu 1.1.2.33 pig.G.I.removeEdges(l_E);
1050 salcianu 1.1.2.33 PANode n_E = node_rep.getCodeNode(q, PANode.EXCEPT);
1051 salcianu 1.1.2.33 pig.G.I.addEdge(l_E, n_E);
1052 salcianu 1.1.2.35 pig.G.e.addMethodHole(n_E, hm);
1053 salcianu 1.1.2.33 // no pig.G.propagate is necessary since n_E cannot point to anything
1054 salcianu 1.1.2.33 // that is not escaped into that native method.
1055 salcianu 1.1.2.22 }
1056 salcianu 1.1.2.3
1057 salcianu 1.1.2.22 // treat specially "public static native void java.lang.System.arraycopy
1058 salcianu 1.1.2.22 // (Object src, int, Object dst, int, int);
1059 salcianu 1.1.2.22 // We hope that we really know what arraycopy does ...
1060 salcianu 1.1.2.22 private static ParIntGraphPair treat_arraycopy(PointerAnalysis pa, CALL q,
1061 salcianu 1.8 ParIntGraph pig_before) {
1062 salcianu 1.1.2.22 HMethod hm = q.method();
1063 salcianu 1.1.2.22 if(!hm.getName().equals("arraycopy") ||
1064 salcianu 1.1.2.22 !hm.getDeclaringClass().getName().equals("java.lang.System"))
1065 salcianu 1.1.2.22 return null;
1066 salcianu 1.1.2.3
1067 salcianu 1.1.2.52 if(DEBUG)
1068 salcianu 1.7 System.out.println("NATIVE (special): " + Util.code2str(q));
1069 salcianu 1.1.2.3
1070 salcianu 1.1.2.22 // the conventional field name used for the array's entries
1071 salcianu 1.1.2.22 final String f = PointerAnalysis.ARRAY_CONTENT;
1072 salcianu 1.1.2.22
1073 salcianu 1.1.2.22 Temp l_src = q.params(0);
1074 salcianu 1.1.2.22 Temp l_dst = q.params(2);
1075 salcianu 1.1.2.22
1076 salcianu 1.8 Set dst_set =
1077 salcianu 1.8 PointerAnalysis.selectArraysOfObjs
1078 salcianu 1.8 (pig_before.G.I.pointedNodes(l_dst));
1079 salcianu 1.8 Set src_set =
1080 salcianu 1.8 PointerAnalysis.selectArraysOfObjs
1081 salcianu 1.8 (pig_before.G.I.pointedNodes(l_src));
1082 salcianu 1.1.2.22
1083 salcianu 1.8 Set set_S = pig_before.G.I.pointedNodes(src_set, f);
1084 salcianu 1.1.2.22
1085 salcianu 1.1.2.22 Set set_E = new HashSet();
1086 salcianu 1.8 Set gtypes = new HashSet();
1087 cananian 1.12 for(Object nodeO : src_set){
1088 cananian 1.12 PANode node = (PANode) nodeO;
1089 salcianu 1.8 if(pig_before.G.e.hasEscaped(node)) {
1090 salcianu 1.1.2.22 set_E.add(node);
1091 salcianu 1.8 Set compTypes = PointerAnalysis.getObjArrayComp(node);
1092 salcianu 1.8 for(Iterator it2 = compTypes.iterator(); it2.hasNext(); )
1093 salcianu 1.8 gtypes.add(new GenType((HClass) it2.next(), GenType.POLY));
1094 salcianu 1.8 }
1095 salcianu 1.1.2.22 }
1096 salcianu 1.1.2.3
1097 salcianu 1.1.2.22 NodeRepository node_rep = pa.getNodeRepository();
1098 salcianu 1.1.2.3
1099 salcianu 1.1.2.22 if(set_E.isEmpty())
1100 salcianu 1.1.2.22 pig_before.G.I.addEdges(dst_set, f, set_S);
1101 salcianu 1.1.2.48 else {
1102 salcianu 1.8 GenType[] gts =
1103 salcianu 1.8 (GenType[]) gtypes.toArray(new GenType[gtypes.size()]);
1104 salcianu 1.8 PANode load_node = node_rep.getCodeNode(q, PANode.LOAD, gts);
1105 salcianu 1.1.2.3
1106 salcianu 1.1.2.22 pig_before.G.O.addEdges(set_E, f, load_node);
1107 salcianu 1.1.2.28
1108 salcianu 1.1.2.28 if(!PointerAnalysis.IGNORE_EO)
1109 salcianu 1.1.2.28 pig_before.eo.add(set_E, f, load_node, pig_before.G.I);
1110 salcianu 1.1.2.22
1111 salcianu 1.1.2.22 set_S.add(load_node);
1112 salcianu 1.1.2.22 pig_before.G.I.addEdges(dst_set, f, set_S);
1113 salcianu 1.1.2.22
1114 salcianu 1.1.2.22 pig_before.G.propagate(set_E);
1115 salcianu 1.1.2.22
1116 salcianu 1.1.2.48 if(PointerAnalysis.RECORD_ACTIONS) {
1117 salcianu 1.1.2.48 // update the action repository
1118 salcianu 1.1.2.48 Set active_threads = pig_before.tau.activeThreadSet();
1119 salcianu 1.1.2.48 for(Iterator it_E = set_E.iterator(); it_E.hasNext(); )
1120 salcianu 1.1.2.48 pig_before.ar.add_ld((PANode) it_E.next(), f, load_node,
1121 salcianu 1.1.2.48 ActionRepository.THIS_THREAD,
1122 salcianu 1.1.2.48 active_threads);
1123 salcianu 1.1.2.48 }
1124 salcianu 1.1.2.22 }
1125 salcianu 1.1.2.22
1126 salcianu 1.1.2.22 ParIntGraph pig_after1 = (ParIntGraph) pig_before.clone();
1127 salcianu 1.1.2.22 // Set the edges for the exception node in graph 1.
1128 salcianu 1.1.2.22 Temp l_E = q.retex();
1129 salcianu 1.1.2.22 if(l_E != null){
1130 salcianu 1.1.2.22 pig_after1.G.I.removeEdges(l_E);
1131 salcianu 1.1.2.22 PANode n_E = node_rep.getCodeNode(q, PANode.EXCEPT);
1132 salcianu 1.1.2.22 pig_after1.G.I.addEdge(l_E, n_E);
1133 salcianu 1.1.2.35 pig_after1.G.e.addMethodHole(n_E, hm);
1134 salcianu 1.1.2.22 }
1135 salcianu 1.1.2.22 return new ParIntGraphPair(pig_before, pig_after1);
1136 salcianu 1.1.2.22 }
1137 salcianu 1.1.2.22
1138 salcianu 1.1.2.22
1139 salcianu 1.1.2.53 private static Set wes_methods = new HashSet();
1140 salcianu 1.1.2.53 private static void build_rtj_methods(Linker linker) {
1141 salcianu 1.1.2.53 String[][] methods = {
1142 salcianu 1.1.2.53 {"javax.realtime.RealtimeThread", "getMemoryArea"},
1143 salcianu 1.1.2.53 {"javax.realtime.RealtimeThread", "currentRealtimeThread"},
1144 salcianu 1.1.2.53 {"javax.realtime.MemoryArea", "checkAccess"},
1145 salcianu 1.1.2.53 {"javax.realtime.MemoryArea", "bless"},
1146 salcianu 1.1.2.53 {"javax.realtime.Stats", "addCheck"},
1147 salcianu 1.1.2.53 {"javax.realtime.Stats", "addNewObject"},
1148 salcianu 1.1.2.53 {"javax.realtime.Stats", "addNewArrayObject"},
1149 salcianu 1.1.2.53 {"javax.realtime.HeapMemory", "instance"},
1150 salcianu 1.1.2.54 {"javax.realtime.ImmortalMemory", "instance"},
1151 salcianu 1.1.2.54 {"javax.realtime.MemoryArea", "enterMemBlock"}
1152 salcianu 1.1.2.53 };
1153 salcianu 1.1.2.53 for(int i = 0; i < methods.length; i++)
1154 salcianu 1.1.2.53 wes_methods.addAll
1155 salcianu 1.1.2.53 (getMethods(methods[i][0], methods[i][1], linker));
1156 salcianu 1.1.2.53
1157 salcianu 1.5 if(DEBUG)
1158 salcianu 1.5 Util.print_collection(wes_methods, "Wes RTJ methods");
1159 salcianu 1.1.2.53 }
1160 salcianu 1.1.2.53
1161 salcianu 1.1.2.44 // Many native methods don't do any synchronizations on their object
1162 salcianu 1.1.2.44 // parameters, don't store them in static fields and don't modify the
1163 salcianu 1.1.2.44 // points-to graph accessible from these object parameters.
1164 salcianu 1.1.2.44 private static boolean isUnharmful(HMethod hm) {
1165 salcianu 1.1.2.53 return
1166 salcianu 1.1.2.53 uhms.contains(hm) ||
1167 salcianu 1.1.2.53 (CONSIDER_WES_GOOD && wes_methods.contains(hm));
1168 salcianu 1.1.2.44 }
1169 salcianu 1.1.2.44 // Checks whether a method is totally harmful (i.e. all the parameters
1170 salcianu 1.1.2.45 // must be marked as escaping into it). A CALL to such a method cannot
1171 salcianu 1.1.2.45 // be treated otherwise than by skipping it.
1172 salcianu 1.1.2.44 private static boolean isTotallyHarmful(HMethod hm) {
1173 salcianu 1.1.2.44 return !isUnharmful(hm); // for the moment, conservative treatment
1174 salcianu 1.1.2.44 }
1175 salcianu 1.1.2.54 public static Set getUnharmfulMethods() { return uhms; }
1176 salcianu 1.1.2.44 private static Set uhms = new HashSet();
1177 salcianu 1.1.2.53 private static void build_uhms(Linker linker) {
1178 salcianu 1.1.2.44 String[][] methods = {
1179 salcianu 1.1.2.50 {"java.io.File", "length0"},
1180 salcianu 1.1.2.50
1181 salcianu 1.1.2.44 {"java.io.FileInputStream", "open"},
1182 salcianu 1.1.2.44 {"java.io.FileInputStream", "close"},
1183 salcianu 1.1.2.44 {"java.io.FileInputStream", "available"},
1184 salcianu 1.1.2.44 {"java.io.FileInputStream", "read"},
1185 salcianu 1.1.2.44 {"java.io.FileInputStream", "readBytes"},
1186 salcianu 1.1.2.44
1187 salcianu 1.1.2.44 {"java.io.FileOutputStream", "open"},
1188 salcianu 1.1.2.44 {"java.io.FileOutputStream", "openAppend"},
1189 salcianu 1.1.2.44 {"java.io.FileOutputStream", "close"},
1190 salcianu 1.1.2.44 {"java.io.FileOutputStream", "write"},
1191 salcianu 1.1.2.44 {"java.io.FileOutputStream", "writeBytes"},
1192 salcianu 1.1.2.44
1193 salcianu 1.1.2.44 {"java.lang.Throwable", "printStackTrace0"},
1194 salcianu 1.1.2.44 {"java.lang.Throwable", "fillInStackTrace"},
1195 salcianu 1.1.2.44 {"java.lang.Class", "getName"},
1196 salcianu 1.1.2.44 {"java.lang.Class", "getPrimitiveClass"},
1197 salcianu 1.1.2.44
1198 salcianu 1.1.2.50 {"java.net.SocketOutputStream", "socketWrite"},
1199 salcianu 1.1.2.50 {"java.net.SocketInputStream", "socketRead"},
1200 salcianu 1.1.2.50
1201 salcianu 1.1.2.50 {"java.net.PlainSocketImpl", "socketClose"},
1202 salcianu 1.1.2.50 {"java.net.PlainSocketImpl", "socketAvailable"},
1203 salcianu 1.1.2.54
1204 salcianu 1.1.2.54 {"java.net.PlainSocketImpl", "socketAccept"},
1205 salcianu 1.1.2.54 {"java.net.PlainSocketImpl", "socketBind"},
1206 salcianu 1.1.2.54 {"java.net.PlainSocketImpl", "socketCreate"},
1207 salcianu 1.1.2.54 {"java.net.PlainSocketImpl", "socketListen"},
1208 salcianu 1.1.2.50
1209 salcianu 1.1.2.52 {"java.lang.Object", "hashCode"},
1210 salcianu 1.8 {"java.lang.Object", "equals"},
1211 salcianu 1.8 {"java.lang.Object", "toString"},
1212 salcianu 1.1.2.52
1213 salcianu 1.1.2.52 // this one does a sync on its argument; that's why it
1214 salcianu 1.1.2.52 // we also create a graph modelling its execution
1215 salcianu 1.1.2.52 {"java.lang.Object", "wait"},
1216 salcianu 1.1.2.52
1217 salcianu 1.1.2.52 {"java.lang.Thread", "isAlive"},
1218 salcianu 1.11 {"java.lang.Object", "getClass"},
1219 salcianu 1.11
1220 salcianu 1.11 {"java.lang.Class", "isArray"},
1221 salcianu 1.11 {"java.lang.Class", "getComponentType"},
1222 salcianu 1.11
1223 salcianu 1.11 {"java.lang.reflect.Method", "getName"},
1224 salcianu 1.11 {"java.lang.reflect.Method", "getDeclaringClass"},
1225 salcianu 1.11 {"java.lang.reflect.Method", "getModifiers"},
1226 salcianu 1.11 {"java.lang.reflect.Method", "getReturnType"},
1227 salcianu 1.11 {"java.lang.reflect.Method", "getParameterTypes"},
1228 salcianu 1.11 {"java.lang.reflect.Method", "getExceptionTypes"},
1229 salcianu 1.11
1230 salcianu 1.11 {"java.lang.reflect.Constructor", "getModifiers"},
1231 salcianu 1.11 {"java.lang.reflect.Constructor", "getParameterTypes"},
1232 salcianu 1.11 {"java.lang.reflect.Constructor", "getTypes"},
1233 salcianu 1.11
1234 salcianu 1.11 {"java.lang.reflect.Field", "getDeclaringClass"},
1235 salcianu 1.11 {"java.lang.reflect.Field", "getName"},
1236 salcianu 1.11 {"java.lang.reflect.Field", "getType"},
1237 salcianu 1.11
1238 salcianu 1.11 {"java.lang.reflect.Field", "getByte"},
1239 salcianu 1.11 {"java.lang.reflect.Field", "setByte"},
1240 salcianu 1.11 {"java.lang.reflect.Field", "getInt"},
1241 salcianu 1.11 {"java.lang.reflect.Field", "setInt"},
1242 salcianu 1.11 {"java.lang.reflect.Field", "getBoolean"},
1243 salcianu 1.11 {"java.lang.reflect.Field", "setBoolean"},
1244 salcianu 1.11 {"java.lang.reflect.Field", "getFloat"},
1245 salcianu 1.11 {"java.lang.reflect.Field", "setFloat"},
1246 salcianu 1.11 {"java.lang.reflect.Field", "getDouble"},
1247 salcianu 1.11 {"java.lang.reflect.Field", "setDouble"},
1248 salcianu 1.11 {"java.lang.reflect.Field", "getLong"},
1249 salcianu 1.11 {"java.lang.reflect.Field", "setLong"},
1250 salcianu 1.11 {"java.lang.reflect.Field", "getShort"},
1251 salcianu 1.11 {"java.lang.reflect.Field", "setShort"},
1252 salcianu 1.11 {"java.lang.reflect.Field", "getModifiers"},
1253 salcianu 1.11
1254 salcianu 1.11 {"java.lang.reflect.Array", "getLength"},
1255 salcianu 1.11 {"java.lang.reflect.Array", "getByte"},
1256 salcianu 1.11 {"java.lang.reflect.Array", "setByte"},
1257 salcianu 1.11 {"java.lang.reflect.Array", "getInt"},
1258 salcianu 1.11 {"java.lang.reflect.Array", "setInt"},
1259 salcianu 1.11 {"java.lang.reflect.Array", "getBoolean"},
1260 salcianu 1.11 {"java.lang.reflect.Array", "setBoolean"},
1261 salcianu 1.11 {"java.lang.reflect.Array", "getFloat"},
1262 salcianu 1.11 {"java.lang.reflect.Array", "setFloat"},
1263 salcianu 1.11 {"java.lang.reflect.Array", "getDouble"},
1264 salcianu 1.11 {"java.lang.reflect.Array", "setDouble"},
1265 salcianu 1.11 {"java.lang.reflect.Array", "getLong"},
1266 salcianu 1.11 {"java.lang.reflect.Array", "setLong"},
1267 salcianu 1.11 {"java.lang.reflect.Array", "getShort"},
1268 salcianu 1.11 {"java.lang.reflect.Array", "setShort"},
1269 salcianu 1.11
1270 salcianu 1.11 {"java.lang.reflect.Method", "getDeclaringClass"},
1271 salcianu 1.11 {"java.lang.reflect.Constructor", "getDeclaringClass"}
1272 salcianu 1.1.2.44 };
1273 salcianu 1.1.2.44
1274 salcianu 1.1.2.44 for(int i = 0; i < methods.length; i++)
1275 salcianu 1.1.2.53 uhms.addAll(getMethods(methods[i][0], methods[i][1], linker));
1276 salcianu 1.1.2.50
1277 salcianu 1.5 if(DEBUG)
1278 salcianu 1.5 Util.print_collection(uhms, "Unharmful methods");
1279 salcianu 1.1.2.44 }
1280 salcianu 1.1.2.44
1281 salcianu 1.1.2.44 // Returns all the methods having the name m_name
1282 salcianu 1.1.2.44 // that are declared in class c_name.
1283 salcianu 1.1.2.53 private static Collection getMethods(String c_name, String m_name,
1284 salcianu 1.1.2.53 Linker linker) {
1285 salcianu 1.1.2.44 List retval = new LinkedList();
1286 cananian 1.10 try {
1287 salcianu 1.1.2.53 HClass hclass = linker.forName(c_name);
1288 salcianu 1.1.2.44 HMethod[] hms = hclass.getDeclaredMethods();
1289 salcianu 1.1.2.44 for(int i = 0; i < hms.length; i++)
1290 salcianu 1.1.2.44 if(m_name.equals(hms[i].getName()))
1291 salcianu 1.1.2.44 retval.add(hms[i]);
1292 cananian 1.10 } catch (NoSuchClassException e) { /* ignore this class */ }
1293 salcianu 1.1.2.44 return retval;
1294 salcianu 1.1.2.44 }
1295 salcianu 1.1.2.52
1296 salcianu 1.1.2.52
1297 salcianu 1.1.2.52 private static ParIntGraph model_native(HMethod hm) {
1298 salcianu 1.1.2.52 ParIntGraph pig = (ParIntGraph) graphs_for_natives.get(hm);
1299 salcianu 1.1.2.52 return pig;
1300 salcianu 1.1.2.52 }
1301 salcianu 1.11
1302 salcianu 1.1.2.52 private static Map graphs_for_natives = new HashMap();
1303 salcianu 1.1.2.53 private static void build_graphs_for_natives(PointerAnalysis pa) {
1304 salcianu 1.8 add_graph4java_lang_Object_wait(pa);
1305 salcianu 1.8 }
1306 salcianu 1.8
1307 salcianu 1.8 private static void add_graph4java_lang_Object_wait
1308 salcianu 1.8 (PointerAnalysis pa) {
1309 salcianu 1.8
1310 salcianu 1.1.2.52 // java_lang_Object_wait
1311 salcianu 1.1.2.52 HMethod hm = get_method(pa, "java.lang.Object", "wait", 0);
1312 salcianu 1.1.2.52 MetaMethod mm = new MetaMethod(hm, true);
1313 salcianu 1.1.2.52
1314 salcianu 1.1.2.52 NodeRepository nodes = pa.getNodeRepository();
1315 salcianu 1.1.2.52 nodes.addParamNodes(mm, 1);
1316 salcianu 1.1.2.52 PANode node = nodes.getParamNode(mm, 0);
1317 salcianu 1.1.2.52
1318 salcianu 1.1.2.52 ParIntGraph pig = new ParIntGraph();
1319 salcianu 1.1.2.52 if(PointerAnalysis.RECORD_ACTIONS)
1320 salcianu 1.1.2.52 pig.ar.add_sync
1321 salcianu 1.8 (new PASync(node, ActionRepository.THIS_THREAD,null), null);
1322 salcianu 1.8
1323 salcianu 1.1.2.52 graphs_for_natives.put(hm, pig);
1324 salcianu 1.1.2.52 }
1325 salcianu 1.1.2.52
1326 salcianu 1.8
1327 salcianu 1.1.2.52 private static HMethod get_method(PointerAnalysis pa,
1328 salcianu 1.1.2.52 String cls_name, String mthd_name,
1329 salcianu 1.1.2.52 int nb_args) {
1330 salcianu 1.1.2.52 Set set = new HashSet();
1331 salcianu 1.1.2.52 HClass hclass = pa.getLinker().forName(cls_name);
1332 cananian 1.3.2.1 assert hclass != null : cls_name + " was not found!";
1333 salcianu 1.1.2.52
1334 salcianu 1.1.2.52 HMethod[] hms = hclass.getMethods();
1335 salcianu 1.1.2.52 for(int i = 0; i < hms.length; i++)
1336 salcianu 1.1.2.52 if(hms[i].getName().equals(mthd_name) &&
1337 salcianu 1.1.2.52 (hms[i].getParameterTypes().length == nb_args))
1338 salcianu 1.1.2.52 set.add(hms[i]);
1339 salcianu 1.1.2.52
1340 cananian 1.3.2.1 assert set.size() > 0 : mthd_name + "(" + nb_args +
1341 cananian 1.3.2.1 ") not found in " + cls_name;
1342 cananian 1.3.2.1 assert set.size() == 1 : "Too many methods";
1343 salcianu 1.1.2.52
1344 salcianu 1.1.2.52 return (HMethod) set.iterator().next();
1345 salcianu 1.1.2.53 }
1346 salcianu 1.1.2.53
1347 salcianu 1.1.2.53 // should be called before any other method
1348 salcianu 1.1.2.53 static void static_init(PointerAnalysis pa) {
1349 salcianu 1.1.2.53 build_uhms(pa.getLinker());
1350 salcianu 1.5
1351 salcianu 1.5 if(CONSIDER_WES_GOOD)
1352 salcianu 1.5 build_rtj_methods(pa.getLinker());
1353 salcianu 1.5
1354 salcianu 1.1.2.53 build_graphs_for_natives(pa);
1355 salcianu 1.8
1356 salcianu 1.8 jlO_equals = get_method(pa, "java.lang.Object", "equals", 1);
1357 salcianu 1.8 jlO_hashCode = get_method(pa, "java.lang.Object", "hashCode", 0);
1358 salcianu 1.8 jlO_toString = get_method(pa, "java.lang.Object", "toString", 0);
1359 salcianu 1.1.2.52 }
1360 salcianu 1.8
1361 salcianu 1.8 private static HMethod jlO_equals = null;
1362 salcianu 1.8 private static HMethod jlO_hashCode = null;
1363 salcianu 1.8 private static HMethod jlO_toString = null;
1364 cananian 1.2 }// end of the class