1 vivien 1.1.2.1 // ODInterProcPA.java, created Tue Jan 18 11:04:20 2000 by salcianu
2 cananian 1.1.2.2 // Copyright (C) 2000 Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
3 vivien 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 vivien 1.1.2.1 package harpoon.Analysis.PointerAnalysis;
5 vivien 1.1.2.1
6 vivien 1.1.2.1 import java.util.Collection;
7 vivien 1.1.2.1 import java.util.Iterator;
8 vivien 1.1.2.1 import java.util.Enumeration;
9 vivien 1.1.2.1 import java.util.Set;
10 vivien 1.1.2.1 import java.util.Map;
11 vivien 1.1.2.1 import java.util.HashSet;
12 vivien 1.1.2.1 import java.util.Collections;
13 vivien 1.1.2.1 import java.util.List;
14 vivien 1.1.2.1 import java.util.LinkedList;
15 vivien 1.1.2.1
16 vivien 1.1.2.1 import java.lang.reflect.Modifier;
17 vivien 1.1.2.1
18 vivien 1.1.2.1 import harpoon.IR.Quads.CALL;
19 vivien 1.1.2.1 import harpoon.Analysis.Quads.CallGraph;
20 vivien 1.1.2.1 import harpoon.Temp.Temp;
21 vivien 1.1.2.1
22 vivien 1.1.2.1 import harpoon.ClassFile.HClass;
23 vivien 1.1.2.1 import harpoon.ClassFile.HCode;
24 vivien 1.1.2.1 import harpoon.ClassFile.HMethod;
25 vivien 1.1.2.1 import harpoon.ClassFile.HField;
26 vivien 1.1.2.1 import harpoon.ClassFile.Loader;
27 vivien 1.1.2.1
28 vivien 1.1.2.1 import harpoon.Analysis.MetaMethods.MetaMethod;
29 vivien 1.1.2.1 import harpoon.Analysis.MetaMethods.MetaCallGraph;
30 vivien 1.1.2.1
31 vivien 1.1.2.1 import harpoon.Util.TypeInference.ExactTemp;
32 vivien 1.1.2.1 import harpoon.Util.TypeInference.TypeInference;
33 vivien 1.1.2.1 import harpoon.IR.Quads.QuadFactory;
34 vivien 1.1.2.1
35 vivien 1.1.2.1
36 cananian 1.6 import net.cscott.jutil.LinearSet;
37 vivien 1.1.2.1 import harpoon.Util.DataStructs.Relation;
38 vivien 1.1.2.1 import harpoon.Util.DataStructs.LightRelation;
39 vivien 1.1.2.1 import harpoon.Util.DataStructs.LightMap;
40 vivien 1.1.2.1 import harpoon.Util.DataStructs.RelationEntryVisitor;
41 vivien 1.1.2.1
42 vivien 1.1.2.1 import harpoon.Util.Util;
43 vivien 1.1.2.1
44 vivien 1.1.2.1 /**
45 vivien 1.1.2.1 * <code>ODInterProcPA</code> is a "functional" class (i.e. it
46 vivien 1.1.2.1 * contains just some methods, no persistent data) that wraps
47 vivien 1.1.2.1 * the inter-procedural part of the pointer analysis. Normally, this should
48 vivien 1.1.2.1 * be a part of the <code>ODPointerAnalysis</code>, but that class is already
49 vivien 1.1.2.1 * too big and some code segmentation is always good!<br>
50 vivien 1.1.2.1 * In the implementation of this class, most of the methods are static and
51 vivien 1.1.2.1 * have <code>ODPointerAnalysis pa</code> as their first argument. This stands
52 vivien 1.1.2.1 * for the <code>this</code> <i>hidden</i> argument that would exist if all
53 vivien 1.1.2.1 * those methods were in the <code>ODPointerAnalysis</code> class.
54 vivien 1.1.2.1 *
55 cananian 1.1.2.2 * @author Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
56 cananian 1.7 * @version $Id: ODInterProcPA.java,v 1.7 2004/02/08 03:20:02 cananian Exp $
57 vivien 1.1.2.1 */
58 vivien 1.1.2.1 abstract class ODInterProcPA {
59 vivien 1.1.2.1
60 vivien 1.1.2.1 /** Call sites with more than <code>MAX_CALLEES</code> callees are simply
61 vivien 1.1.2.1 * considered to be holes. */
62 vivien 1.1.2.1 public static final int MAX_CALLEES = 5;
63 vivien 1.1.2.1
64 vivien 1.1.2.1 /** Activates a lot of debug messages. */
65 vivien 1.1.2.1 public static final boolean DEBUG = false;
66 vivien 1.1.2.1
67 vivien 1.1.2.1 /** Displays some warnings, <i>eg</i> for the call sites with 0 callees.
68 vivien 1.1.2.1 * This is not necessarily an error! For example, if an application
69 vivien 1.1.2.1 * never instantiates a <code>SecurityManager</code>,
70 vivien 1.1.2.1 * each call to a method of that class has ZERO callees! */
71 vivien 1.1.2.1 public static final boolean WARNINGS = true;
72 vivien 1.1.2.1
73 vivien 1.1.2.1
74 vivien 1.1.2.1 /** Specify the behaviour of the mapUP method for on demand
75 vivien 1.1.2.1 * analysis in very tricky cases.
76 vivien 1.1.2.1 */
77 vivien 1.1.2.1 public static boolean ret_strong_update = false;
78 vivien 1.1.2.1 public static boolean exc_strong_update = false;
79 vivien 1.1.2.1
80 vivien 1.1.2.1
81 vivien 1.1.2.1 /** Analyzes the call site <code>q</code> inside
82 vivien 1.1.2.1 * <code>current_method</code>. If analyzing the call is not possible
83 vivien 1.1.2.1 * (e.g. one of the callees is native, hence unanalyzable), the call
84 vivien 1.1.2.1 * site is skipped and all the parameters are marked as escaping
85 vivien 1.1.2.1 * through that call site.
86 vivien 1.1.2.1 *
87 vivien 1.1.2.1 * @param pa The <code>ODPointerAnalysis</code> object that
88 vivien 1.1.2.1 * calls this method. This parameter stands for the <code>this</code>
89 vivien 1.1.2.1 * pointer that would exist if this method were in the
90 vivien 1.1.2.1 * <code>ODPointerAnalysis</code> class.
91 vivien 1.1.2.1 * @param current_method The method that contains in its
92 vivien 1.1.2.1 * code the call site <code>q</code>.
93 vivien 1.1.2.1 * @param q The analyzed call site.
94 vivien 1.1.2.1 * @param pig_before The parallel interaction graph at
95 vivien 1.1.2.1 * the program point just before the call site; this graph will be
96 vivien 1.1.2.1 * mutated, it is the responsability of the caller to clone it if it
97 vivien 1.1.2.1 * is necessary somewhere else.
98 vivien 1.1.2.1 *
99 vivien 1.1.2.1 * @return Two graphs are returned: one for the normal return from
100 vivien 1.1.2.1 * the procedure, the other one for a return due to an exception.
101 vivien 1.1.2.1 */
102 vivien 1.1.2.1 public static ODParIntGraphPair analyze_call(ODPointerAnalysis pa,
103 vivien 1.1.2.1 MetaMethod current_mmethod,
104 vivien 1.1.2.1 CALL q,
105 vivien 1.1.2.1 ODParIntGraph pig_before) {
106 vivien 1.1.2.1 return analyze_call(pa, current_mmethod, q, pig_before, null, true, true);
107 vivien 1.1.2.1 }
108 vivien 1.1.2.1
109 vivien 1.1.2.1 public static ODParIntGraphPair analyze_call(ODPointerAnalysis pa,
110 vivien 1.1.2.1 MetaMethod current_mmethod,
111 vivien 1.1.2.1 CALL q,
112 vivien 1.1.2.1 ODParIntGraph pig_before,
113 vivien 1.1.2.1 MethodHole hole) {
114 vivien 1.1.2.1
115 vivien 1.1.2.1 return analyze_call(pa, current_mmethod, q, pig_before, null, true, true);
116 vivien 1.1.2.1 }
117 vivien 1.1.2.1
118 vivien 1.1.2.1 public static ODParIntGraphPair analyze_call(ODPointerAnalysis pa,
119 vivien 1.1.2.1 MetaMethod current_mmethod,
120 vivien 1.1.2.1 CALL q,
121 vivien 1.1.2.1 ODParIntGraph pig_before,
122 vivien 1.1.2.1 MethodHole hole,
123 vivien 1.1.2.1 boolean verbose) {
124 vivien 1.1.2.1
125 vivien 1.1.2.1 return analyze_call(pa, current_mmethod, q, pig_before, null, verbose, true);
126 vivien 1.1.2.1 }
127 vivien 1.1.2.1
128 vivien 1.1.2.1 public static ODParIntGraphPair analyze_call(ODPointerAnalysis pa,
129 vivien 1.1.2.1 MetaMethod current_mmethod,
130 vivien 1.1.2.1 CALL q,
131 vivien 1.1.2.1 ODParIntGraph pig_before,
132 vivien 1.1.2.1 MethodHole hole,
133 vivien 1.1.2.1 boolean verbose,
134 vivien 1.1.2.1 boolean updateformalnodes) {
135 vivien 1.1.2.1 if(DEBUG)
136 vivien 1.1.2.1 System.out.println("Inter-procedural analysis " + q);
137 vivien 1.1.2.1
138 vivien 1.1.2.1 ODParIntGraphPair pp_after = null;
139 vivien 1.1.2.1 System.out.println("analyze_call");
140 vivien 1.1.2.1
141 vivien 1.1.2.1 // treat some very special native methods
142 vivien 1.1.2.1 //tbu
143 vivien 1.1.2.1 if((pp_after = treatVerySpecialNatives(pa, q, pig_before)) != null)
144 vivien 1.1.2.1 return pp_after;
145 vivien 1.1.2.1
146 vivien 1.1.2.1 MetaMethod[] mms = null;
147 vivien 1.1.2.1 if (hole==null){
148 vivien 1.1.2.1 // System.out.println("Hole is null for " + current_mmethod + " and call " +
149 salcianu 1.5 // Util.code2str(q));
150 vivien 1.1.2.1 mms = pa.getMetaCallGraph().getCallees(current_mmethod, q);
151 vivien 1.1.2.1 // System.out.println("Result is " + mms);
152 vivien 1.1.2.1 // System.out.println("Size is " + mms.length);
153 vivien 1.1.2.1 // MetaMethod[] allthecallees =
154 vivien 1.1.2.1 // pa.getMetaCallGraph().getCallees(current_mmethod);
155 vivien 1.1.2.1 // System.out.println("Printing the " + allthecallees.length
156 vivien 1.1.2.1 // + " callees...");
157 vivien 1.1.2.1 // for(int i=0; i<allthecallees.length; i++){
158 vivien 1.1.2.1 // System.out.println("Callee " + i + ": " + allthecallees[i]);
159 vivien 1.1.2.1 // }
160 vivien 1.1.2.1
161 vivien 1.1.2.1 }
162 vivien 1.1.2.1 else
163 vivien 1.1.2.1 {
164 vivien 1.1.2.1 // System.out.println("Hole is not null");
165 vivien 1.1.2.1 mms = hole.callees();
166 vivien 1.1.2.1 }
167 vivien 1.1.2.1 int nb_callees = mms.length;
168 vivien 1.1.2.1
169 vivien 1.1.2.1 // I count on the fact that if a call site has 0 callees, it
170 vivien 1.1.2.1 // means that it doesn't occur in practice (because some classes
171 vivien 1.1.2.1 // are not instantiated), not that the call graph is buggy!
172 vivien 1.1.2.1 // So, the CALL is simply ignored.
173 vivien 1.1.2.1 if(nb_callees == 0){
174 vivien 1.1.2.1 if(WARNINGS){
175 vivien 1.1.2.1 System.out.println("Warning: CALL site with no callee! ");
176 salcianu 1.5 System.out.println("Warning: " + Util.code2str(q));
177 vivien 1.1.2.1 }
178 vivien 1.1.2.1 return new ODParIntGraphPair(pig_before, pig_before);
179 vivien 1.1.2.1 }
180 vivien 1.1.2.1
181 vivien 1.1.2.1 // Due to the imprecisions in the call graph, most of them due to
182 vivien 1.1.2.1 // dynamic dispatches, several call sites have a huge number of callees
183 vivien 1.1.2.1 // These CALLs are not analyzed (i.e. they are treated as method holes)
184 vivien 1.1.2.1 if(nb_callees > MAX_CALLEES){
185 vivien 1.1.2.1 if(DEBUG)
186 vivien 1.1.2.1 System.out.println("TOO MANY CALLEES (" + nb_callees + ") "+q);
187 vivien 1.1.2.1 // Classical skip_call as, even in ODA, we are not going
188 vivien 1.1.2.1 // to try later on to analyze this method hole.
189 vivien 1.1.2.1 return skip_call(pa, q, pig_before, q.method());
190 vivien 1.1.2.1 }
191 vivien 1.1.2.1
192 vivien 1.1.2.1 // For each analyzable callee mm, we store it in mms and its associated
193 vivien 1.1.2.1 // parallel interaction graph in pigs. By "analyzable", we mean
194 vivien 1.1.2.1 // (meta)-methods that are analyzable by the the Pointer Analysis PLUS
195 vivien 1.1.2.1 // the so-called unharmful native methods - native method that we can't
196 vivien 1.1.2.1 // analyze as we don't have their code but we know what their pig will
197 vivien 1.1.2.1 // look like (for most of them it's empty - they don't create new
198 vivien 1.1.2.1 // pointer links).
199 vivien 1.1.2.1 //
200 vivien 1.1.2.1 // For the unharmful native methods the associated pig will be null
201 vivien 1.1.2.1 // (they will be specially treated inside mapUp).
202 vivien 1.1.2.1 //
203 vivien 1.1.2.1 // pig could be also null if the method has not be analyzed yet; this
204 vivien 1.1.2.1 // happens only in strongly connected components of mutually recursive
205 vivien 1.1.2.1 // methods. In this case, we simply don't consider that callee; the
206 vivien 1.1.2.1 // called method will be analyzed later, this will force its callers
207 vivien 1.1.2.1 // to be reanalyzed, so in the end it will be considered (due to the
208 vivien 1.1.2.1 // fixed-point algorithm).
209 vivien 1.1.2.1 int nb_callees_with_pig = 0;
210 vivien 1.1.2.1 boolean allnatives=true;
211 vivien 1.1.2.1 ODParIntGraph pigs[] = new ODParIntGraph[nb_callees];
212 vivien 1.1.2.1 for(int i = 0; i < nb_callees; i++){
213 vivien 1.1.2.1 HMethod hm = mms[i].getHMethod();
214 vivien 1.1.2.1
215 vivien 1.1.2.1 if(Modifier.isNative(hm.getModifiers())) {
216 vivien 1.1.2.1 //if(DEBUG)
217 vivien 1.1.2.1 System.out.println("NATIVE: " + hm);
218 vivien 1.1.2.1 if(isTotallyHarmful(hm)) {
219 vivien 1.1.2.1 if(DEBUG)
220 salcianu 1.5 System.out.print("NEED TO SKIP: " + Util.code2str(q));
221 vivien 1.1.2.1 // Classical skip_call as, even in ODA, we are not
222 vivien 1.1.2.1 // going to try later on to analyze this method
223 vivien 1.1.2.1 // hole.
224 vivien 1.1.2.1 return skip_call(pa, q, pig_before, hm);
225 vivien 1.1.2.1 }
226 vivien 1.1.2.1 else {
227 vivien 1.1.2.1 pigs[nb_callees_with_pig] = null;
228 vivien 1.1.2.1 mms[nb_callees_with_pig] = mms[i];
229 vivien 1.1.2.1 nb_callees_with_pig++;
230 vivien 1.1.2.1 continue;
231 vivien 1.1.2.1 }
232 vivien 1.1.2.1 }
233 vivien 1.1.2.1
234 vivien 1.1.2.1 if(!(ODPointerAnalysis.analyzable(hm))){
235 vivien 1.1.2.1 if(DEBUG)
236 salcianu 1.5 System.out.println("NEED TO SKIP: " + Util.code2str(q));
237 vivien 1.1.2.1 // Classical skip_call as, even in ODA, we are not
238 vivien 1.1.2.1 // going to try later on to analyze this method hole.
239 vivien 1.1.2.1 return skip_call(pa, q, pig_before, hm);
240 vivien 1.1.2.1 }
241 vivien 1.1.2.1
242 vivien 1.1.2.1 // If we are here, mms[i] does not correspond to a native
243 vivien 1.1.2.1 // method.
244 vivien 1.1.2.1 allnatives=false;
245 vivien 1.1.2.1
246 vivien 1.1.2.1 //FV Take the pig computed at the previous level
247 vivien 1.1.2.1 // The skip happens later on
248 vivien 1.1.2.1 // if ((pa.BOUNDED_ANALYSIS_DEPTH==true)&&
249 vivien 1.1.2.1 // (pa.FIRST_ANALYSIS==true))
250 vivien 1.1.2.1 // return skip_call(pa, current_mmethod, q, pig_before,
251 vivien 1.1.2.1 // q.method(), mms);
252 vivien 1.1.2.1
253 vivien 1.1.2.1
254 vivien 1.1.2.1 // There will be a problem here...
255 vivien 1.1.2.1 // Should be refined later on (tbu)
256 vivien 1.1.2.1 if (!((pa.ON_DEMAND_ANALYSIS)&&(hole==null))){
257 vivien 1.1.2.1 pa.current_analysis_depth--;
258 vivien 1.1.2.1 ODParIntGraph pig = null;
259 vivien 1.1.2.1 if (pa.ON_DEMAND_ANALYSIS){
260 vivien 1.1.2.1 pig = pa.getIntParIntGraph(mms[i],true);
261 vivien 1.1.2.1 }
262 vivien 1.1.2.1 else {
263 vivien 1.1.2.1 pig = pa.getExtParIntGraph(mms[i], false);
264 vivien 1.1.2.1 }
265 vivien 1.1.2.1 pa.current_analysis_depth++;
266 vivien 1.1.2.1 if(pig != null){
267 vivien 1.1.2.1 pigs[nb_callees_with_pig] = pig;
268 vivien 1.1.2.1 mms[nb_callees_with_pig] = mms[i];
269 vivien 1.1.2.1 nb_callees_with_pig++;
270 vivien 1.1.2.1 }
271 vivien 1.1.2.1 }
272 vivien 1.1.2.1 }
273 vivien 1.1.2.1
274 vivien 1.1.2.1
275 vivien 1.1.2.1 //FV if we are analyzing at depth 0 in a bounded analyzis, we
276 vivien 1.1.2.1 //just have to skip the call
277 vivien 1.1.2.1 // Should be refined later on (tbu)
278 vivien 1.1.2.1 if ((!allnatives)&&
279 vivien 1.1.2.1 (hole==null)&&
280 vivien 1.1.2.1 (ODPointerAnalysis.ON_DEMAND_ANALYSIS))
281 vivien 1.1.2.1 return skip_call(pa, current_mmethod, q, pig_before,
282 vivien 1.1.2.1 q.method(), mms);
283 vivien 1.1.2.1 // If none of the callees has been analyzed yet, do not do anything
284 vivien 1.1.2.1 // (this can happen only in the strongly connected components of
285 vivien 1.1.2.1 // mutually recursive methods).
286 vivien 1.1.2.1 if(nb_callees_with_pig == 0){
287 vivien 1.1.2.1 return new ODParIntGraphPair(pig_before, pig_before);}
288 vivien 1.1.2.1
289 vivien 1.1.2.1 // Specialize the graphs of the callees for the context sensitive PA
290 vivien 1.1.2.1 if(ODPointerAnalysis.CALL_CONTEXT_SENSITIVE)
291 vivien 1.1.2.1 for(int i = 0; i < nb_callees_with_pig; i++)
292 vivien 1.1.2.1 if(pigs[i] != null){
293 vivien 1.1.2.1 if(DEBUG)
294 vivien 1.1.2.1 System.out.println("BEFORE SPEC: " + pigs[i]);
295 vivien 1.1.2.1 pigs[i] = pa.getSpecializedExtParIntGraph(mms[i], q);
296 vivien 1.1.2.1 if(DEBUG)
297 vivien 1.1.2.1 System.out.println("AFTER SPEC: " + pigs[i]);
298 vivien 1.1.2.1 }
299 vivien 1.1.2.1
300 vivien 1.1.2.1 // The graph after the CALL is a join of all the graphs obtained
301 vivien 1.1.2.1 // by combining, for each callee mms[i], the graph before the CALL
302 vivien 1.1.2.1 // with the graph at the end of mms[i].
303 vivien 1.1.2.1 // The implementation is complicated by the need of doing only the
304 vivien 1.1.2.1 // minimum number of clone() (cloning a ODParIntGraph is very expensive).
305 vivien 1.1.2.1
306 vivien 1.1.2.1 // 1. Special case: only one callee; no ODParIntGraph is cloned.
307 vivien 1.1.2.1 if(nb_callees_with_pig == 1) {
308 vivien 1.1.2.1 pp_after = mapUp(pa, mms[0], current_mmethod, q,
309 vivien 1.1.2.1 pig_before, pigs[0], hole, verbose,
310 vivien 1.1.2.1 updateformalnodes);
311 vivien 1.1.2.1 // tbu
312 vivien 1.1.2.1 // if (hole!=null)
313 vivien 1.1.2.1 // clean_call(pp_after,hole);
314 vivien 1.1.2.1
315 vivien 1.1.2.1 // if (pp_after.pig[0].isCoherent())
316 vivien 1.1.2.1 // System.out.println("PIG coherent (end of analyze_call)");
317 vivien 1.1.2.1 // else{
318 vivien 1.1.2.1 // System.err.println("PIG incoherent (end of analyze_call)");
319 vivien 1.1.2.1 // System.out.println("PIG incoherent (end of analyze_call)");
320 vivien 1.1.2.1 // System.out.println(pp_after.pig[0]);
321 vivien 1.1.2.1 // }
322 vivien 1.1.2.1 // if (pp_after.pig[1].isCoherent())
323 vivien 1.1.2.1 // System.out.println("PIG coherent (end of analyze_call)");
324 vivien 1.1.2.1 // else{
325 vivien 1.1.2.1 // System.err.println("PIG incoherent (end of analyze_call)");
326 vivien 1.1.2.1 // System.out.println("PIG incoherent (end of analyze_call)");
327 vivien 1.1.2.1 // System.out.println(pp_after.pig[1]);
328 vivien 1.1.2.1 // }
329 vivien 1.1.2.1
330 vivien 1.1.2.1
331 vivien 1.1.2.1 return pp_after;
332 vivien 1.1.2.1 }
333 vivien 1.1.2.1
334 vivien 1.1.2.1 // 2. More than one callee:
335 vivien 1.1.2.1 // 2.1. Compute the first term of the join operation.
336 vivien 1.1.2.1 ODParIntGraph pig_clone = (ODParIntGraph) pig_before.clone();
337 vivien 1.1.2.1 boolean jointype = true;
338 vivien 1.1.2.1 if(hole!=null) jointype = false;
339 vivien 1.1.2.1
340 vivien 1.1.2.1 pp_after =
341 vivien 1.1.2.1 mapUp(pa, mms[0], current_mmethod, q,
342 vivien 1.1.2.1 pig_before, pigs[0], hole, verbose,
343 vivien 1.1.2.1 updateformalnodes);
344 vivien 1.1.2.1
345 vivien 1.1.2.1
346 vivien 1.1.2.1 // 2.2. Join to it all the others, except for the last one.
347 vivien 1.1.2.1 for(int i = 1; i < nb_callees_with_pig - 1; i++) {
348 vivien 1.1.2.1 pp_after.join(mapUp(pa, mms[i], current_mmethod, q,
349 vivien 1.1.2.1 (ODParIntGraph)pig_clone.clone(),
350 vivien 1.1.2.1 pigs[i], hole, verbose, updateformalnodes),
351 vivien 1.1.2.1 jointype);
352 vivien 1.1.2.1 }
353 vivien 1.1.2.1
354 vivien 1.1.2.1 // 2.3. Finally, join the graph for the last callee.
355 vivien 1.1.2.1 MetaMethod last_mm = mms[nb_callees_with_pig - 1];
356 vivien 1.1.2.1 pp_after.join
357 vivien 1.1.2.1 (mapUp(pa, last_mm, current_mmethod, q,
358 vivien 1.1.2.1 pig_clone, pigs[nb_callees_with_pig-1], hole, verbose,
359 vivien 1.1.2.1 updateformalnodes),
360 vivien 1.1.2.1 jointype);
361 vivien 1.1.2.1
362 vivien 1.1.2.1 return pp_after; // the long awaited moment!
363 vivien 1.1.2.1 }
364 vivien 1.1.2.1
365 vivien 1.1.2.1
366 vivien 1.1.2.1 /** Updates the ODParIntGraph when the CALL is skipped. Two graphs are
367 vivien 1.1.2.1 returned: one for the normal return from the procedure, the other
368 vivien 1.1.2.1 one for a return due to an exception. */
369 vivien 1.1.2.1 // Called even in ODA, on methods which won't be analyzed
370 vivien 1.1.2.1 // afterwards.
371 vivien 1.1.2.1 private static ODParIntGraphPair skip_call(ODPointerAnalysis pa,
372 vivien 1.1.2.1 CALL q, ODParIntGraph pig_caller,
373 vivien 1.1.2.1 HMethod hm) {
374 vivien 1.1.2.1
375 vivien 1.1.2.1 // if (ODPointerAnalysis.ON_DEMAND_ANALYSIS)
376 vivien 1.1.2.1 // System.out.println("Classical skip_call");
377 vivien 1.1.2.1
378 vivien 1.1.2.1 if(DEBUG)
379 vivien 1.1.2.1 System.out.println("SKIP: " + q);
380 vivien 1.1.2.1 System.out.println("SKIP: " + q);
381 vivien 1.1.2.1 System.out.println("Classical skip_call " + hm);
382 vivien 1.1.2.1
383 vivien 1.1.2.1 NodeRepository node_rep = pa.getNodeRepository();
384 vivien 1.1.2.1
385 vivien 1.1.2.1 // Construct the set S_M of the objects escaped through this unanalyzed
386 vivien 1.1.2.1 // method invocation site.
387 vivien 1.1.2.1 Set S_M = new HashSet();
388 vivien 1.1.2.1 Temp[] params = q.params();
389 vivien 1.1.2.1 for(int i = 0; i < params.length; i++)
390 vivien 1.1.2.1 S_M.addAll(pig_caller.G.I.pointedNodes(params[i]));
391 vivien 1.1.2.1
392 vivien 1.1.2.1 // Update the escape information
393 vivien 1.1.2.1 // 1. all the parameters are directly escaping into the method hole
394 vivien 1.1.2.1 for(Iterator it = S_M.iterator(); it.hasNext(); )
395 vivien 1.1.2.1 pig_caller.G.e.addMethodHole((PANode)it.next(), hm);
396 vivien 1.1.2.1 // 2. propagate the new escape information
397 vivien 1.1.2.1 pig_caller.G.propagate(S_M);
398 vivien 1.1.2.1 // 3. No-update of the method holes and method holes history
399 vivien 1.1.2.1 // even if in ODA: this information is only needed is the
400 vivien 1.1.2.1 // holes will be analyzed later-on, which is not going to be
401 vivien 1.1.2.1 // the case!
402 vivien 1.1.2.1
403 vivien 1.1.2.1 // clone the graph: we will have two distinct versions of it:
404 vivien 1.1.2.1 // one on the 0-edge, the other on the 1-edge, corresponding
405 vivien 1.1.2.1 // to the normal execution (return) respectively execution with
406 vivien 1.1.2.1 // exceptions (throw).
407 vivien 1.1.2.1 ODParIntGraph pig_caller1 = (ODParIntGraph) (pig_caller.clone());
408 vivien 1.1.2.1
409 vivien 1.1.2.1 // The names of the variables closely match those used in the
410 vivien 1.1.2.1 // formal description of the algorithm (section 9.2)
411 vivien 1.1.2.1
412 vivien 1.1.2.1 // Set the edges for the result node in graph 0.
413 vivien 1.1.2.1 // avoid generating useless nodes
414 vivien 1.1.2.1 Temp l_R = q.retval();
415 vivien 1.1.2.1 if(l_R != null){
416 vivien 1.1.2.1 pig_caller.G.I.removeEdges(l_R);
417 vivien 1.1.2.1 if(!hm.getReturnType().isPrimitive()){
418 vivien 1.1.2.1 PANode n_R = node_rep.getCodeNode(q, PANode.RETURN);
419 vivien 1.1.2.1 pig_caller.G.I.addEdge(l_R, n_R);
420 vivien 1.1.2.1 // l_R is a variable: nothing more for ODA
421 vivien 1.1.2.1 pig_caller.G.e.addMethodHole(n_R, hm);
422 vivien 1.1.2.1 }
423 vivien 1.1.2.1 }
424 vivien 1.1.2.1
425 vivien 1.1.2.1 // Set the edges for the exception node in graph 1.
426 vivien 1.1.2.1 Temp l_E = q.retex();
427 vivien 1.1.2.1 if(l_E != null){
428 vivien 1.1.2.1 pig_caller1.G.I.removeEdges(l_E);
429 vivien 1.1.2.1 PANode n_E = node_rep.getCodeNode(q, PANode.EXCEPT);
430 vivien 1.1.2.1 pig_caller1.G.I.addEdge(l_E, n_E);
431 vivien 1.1.2.1 // l_E is a variable: nothing more for ODA
432 vivien 1.1.2.1 pig_caller1.G.e.addMethodHole(n_E, hm);
433 vivien 1.1.2.1 }
434 vivien 1.1.2.1
435 vivien 1.1.2.1 return new ODParIntGraphPair(pig_caller, pig_caller1);
436 vivien 1.1.2.1 }
437 vivien 1.1.2.1
438 vivien 1.1.2.1 private static ODParIntGraphPair skip_call(ODPointerAnalysis pa,
439 vivien 1.1.2.1 MetaMethod caller_mmethod,
440 vivien 1.1.2.1 CALL q, ODParIntGraph pig_caller,
441 vivien 1.1.2.1 HMethod hm,
442 vivien 1.1.2.1 MetaMethod [] mms) {
443 vivien 1.1.2.1
444 vivien 1.1.2.1 System.out.println("SKIP: " + q);
445 vivien 1.1.2.1 System.out.println("Modified skip_call " + hm);
446 vivien 1.1.2.1 // System.out.println("Pig (caller) before skip " + pig_caller);
447 vivien 1.1.2.1
448 vivien 1.1.2.1 if(DEBUG)
449 vivien 1.1.2.1 System.out.println("SKIP: " + q);
450 vivien 1.1.2.1
451 vivien 1.1.2.1 NodeRepository node_rep = pa.getNodeRepository();
452 vivien 1.1.2.1
453 vivien 1.1.2.1 // Construct the set S_M of the objects escaped through this unanalyzed
454 vivien 1.1.2.1 // method invocation site.
455 vivien 1.1.2.1 Set S_M = new HashSet();
456 vivien 1.1.2.1 Temp[] params = q.params();
457 vivien 1.1.2.1 Set caller_params[] = new Set[params.length];
458 vivien 1.1.2.1 for(int i = 0; i < params.length; i++){
459 vivien 1.1.2.1 caller_params[i] = pig_caller.G.I.pointedNodes(params[i]);
460 vivien 1.1.2.1 S_M.addAll(caller_params[i]);
461 vivien 1.1.2.1 }
462 vivien 1.1.2.1
463 vivien 1.1.2.1 // System.out.println(" number of objects escaping through this "
464 vivien 1.1.2.1 // +" unanalyzed method invocation site " +
465 vivien 1.1.2.1 // S_M.size() + "/" + params.length);
466 vivien 1.1.2.1
467 vivien 1.1.2.1 // Update the escape information
468 vivien 1.1.2.1 // 1. all the parameters are directly escaping into the method hole
469 vivien 1.1.2.1 for(Iterator it = S_M.iterator(); it.hasNext(); )
470 vivien 1.1.2.1 pig_caller.G.e.addMethodHole((PANode)it.next(), hm);
471 vivien 1.1.2.1
472 vivien 1.1.2.1 // 2. propagate the new escape information
473 vivien 1.1.2.1 pig_caller.G.propagate(S_M);
474 vivien 1.1.2.1
475 vivien 1.1.2.1
476 vivien 1.1.2.1
477 vivien 1.1.2.1
478 vivien 1.1.2.1 // // Just printing...
479 vivien 1.1.2.1 // System.out.println(" before the modifications ");
480 vivien 1.1.2.1 // System.out.println(" number of params : " + params.length);
481 vivien 1.1.2.1 // for(int i = 0; i < params.length; i++){
482 vivien 1.1.2.1 // System.out.print(" " + i + "-th param");
483 vivien 1.1.2.1 // Iterator parsetit=pig_caller.G.I.pointedNodes(params[i]).iterator();
484 vivien 1.1.2.1 // while(parsetit.hasNext()){
485 vivien 1.1.2.1 // PANode n = (PANode) parsetit.next();
486 vivien 1.1.2.1 // System.out.print(" " + n);
487 vivien 1.1.2.1 // }
488 vivien 1.1.2.1 // System.out.println("");
489 vivien 1.1.2.1 // }
490 vivien 1.1.2.1
491 vivien 1.1.2.1
492 vivien 1.1.2.1 // clone the graph: we will have two distinct versions of it:
493 vivien 1.1.2.1 // one on the 0-edge, the other on the 1-edge, corresponding
494 vivien 1.1.2.1 // to the normal execution (return) respectively execution with
495 vivien 1.1.2.1 // exceptions (throw).
496 vivien 1.1.2.1 ODParIntGraph pig_caller1 = (ODParIntGraph) (pig_caller.clone());
497 vivien 1.1.2.1
498 vivien 1.1.2.1 // The names of the variables closely match those used in the
499 vivien 1.1.2.1 // formal description of the algorithm (section 9.2)
500 vivien 1.1.2.1
501 vivien 1.1.2.1 // Set the edges for the result node in graph 0.
502 vivien 1.1.2.1 // avoid generating useless nodes
503 vivien 1.1.2.1 Temp l_R = q.retval();
504 vivien 1.1.2.1 PANode n_R = null;
505 vivien 1.1.2.1 if(l_R != null){
506 vivien 1.1.2.1 pig_caller.G.I.removeEdges(l_R);
507 vivien 1.1.2.1 if(!hm.getReturnType().isPrimitive()){
508 vivien 1.1.2.1 n_R = node_rep.getCodeNode(q, PANode.RETURN);
509 vivien 1.1.2.1 pig_caller.G.I.addEdge(l_R, n_R);
510 vivien 1.1.2.1 // l_R is a variable : nothing to add for ODA
511 vivien 1.1.2.1 pig_caller.G.e.addMethodHole(n_R, hm);
512 vivien 1.1.2.1 }
513 vivien 1.1.2.1 }
514 vivien 1.1.2.1
515 vivien 1.1.2.1 // Set the edges for the exception node in graph 1.
516 vivien 1.1.2.1 Temp l_E = q.retex();
517 vivien 1.1.2.1 PANode n_E = null;
518 vivien 1.1.2.1 if(l_E != null){
519 vivien 1.1.2.1 pig_caller1.G.I.removeEdges(l_E);
520 vivien 1.1.2.1 n_E = node_rep.getCodeNode(q, PANode.EXCEPT);
521 vivien 1.1.2.1 pig_caller1.G.I.addEdge(l_E, n_E);
522 vivien 1.1.2.1 // l_E is a variable : nothing to add for ODA
523 vivien 1.1.2.1 pig_caller1.G.e.addMethodHole(n_E, hm);
524 vivien 1.1.2.1 }
525 vivien 1.1.2.1
526 vivien 1.1.2.1
527 vivien 1.1.2.1 // 3. Update the MethodHole Set and method holes history of
528 vivien 1.1.2.1 // the caller, if we are in ODA.
529 vivien 1.1.2.1 if (pa.ON_DEMAND_ANALYSIS){
530 vivien 1.1.2.1 // Computation of the escaped called site number (in case
531 vivien 1.1.2.1 // of loop or recursion). This is a quick but safe hack.
532 vivien 1.1.2.1 // int number=0;
533 vivien 1.1.2.1 // for(Iterator n_it=pig_caller.method_holes.iterator();
534 vivien 1.1.2.1 // n_it.hasNext();){
535 vivien 1.1.2.1 // int n = ((MethodHole) n_it.next()).rank();
536 vivien 1.1.2.1 // if (n>number) number=n;
537 vivien 1.1.2.1 // }
538 vivien 1.1.2.1 // number++;
539 vivien 1.1.2.1
540 vivien 1.1.2.1 if(pa.ODA_precise)
541 vivien 1.1.2.1 pa.mh_number++;
542 vivien 1.1.2.1
543 vivien 1.1.2.1 //tbu depth...
544 vivien 1.1.2.1 MethodHole hole = new MethodHole(q, S_M, mms, caller_params,
545 vivien 1.1.2.1 n_R, n_E, pa.mh_number, 1);
546 vivien 1.1.2.1 pig_caller.odi.addHole(hole);
547 vivien 1.1.2.1 pig_caller1.odi.addHole(hole);
548 vivien 1.1.2.1 }
549 vivien 1.1.2.1
550 vivien 1.1.2.1 return new ODParIntGraphPair(pig_caller, pig_caller1);
551 vivien 1.1.2.1 }
552 vivien 1.1.2.1
553 vivien 1.1.2.1
554 vivien 1.1.2.1 // Treat the calls to native methods.
555 vivien 1.1.2.1 private static ODParIntGraphPair treatNatives(ODPointerAnalysis pa,
556 vivien 1.1.2.1 MetaMethod mm,
557 vivien 1.1.2.1 CALL q,
558 vivien 1.1.2.1 ODParIntGraph pig_caller) {
559 vivien 1.1.2.1 //TBU
560 vivien 1.1.2.1 NodeRepository node_rep = pa.getNodeRepository();
561 vivien 1.1.2.1 HMethod hm = mm.getHMethod();
562 vivien 1.1.2.1 if(DEBUG) System.out.println("treatNatives: " + hm);
563 vivien 1.1.2.1
564 vivien 1.1.2.1 // System.out.println("ERROR treatNatives: " + hm + " NOT MODIFIED !" );
565 vivien 1.1.2.1
566 vivien 1.1.2.1 ODParIntGraph pig_before = (ODParIntGraph) pig_caller.clone();
567 vivien 1.1.2.1
568 vivien 1.1.2.1 if(!isUnharmful(hm))
569 vivien 1.1.2.1 markEscapedParameters(q, hm, pig_before);
570 vivien 1.1.2.1
571 vivien 1.1.2.1 ODParIntGraph pig0 = (ODParIntGraph) pig_before.clone();
572 vivien 1.1.2.1 ODParIntGraph pig1 = (ODParIntGraph) pig_before.clone();
573 vivien 1.1.2.1
574 vivien 1.1.2.1 Temp l_R = q.retval();
575 vivien 1.1.2.1 if((l_R != null) && !hm.getReturnType().isPrimitive()){
576 vivien 1.1.2.1 pig0.G.I.removeEdges(l_R);
577 vivien 1.1.2.1 PANode n_R = node_rep.getCodeNode(q, PANode.RETURN);
578 vivien 1.1.2.1 pig0.G.I.addEdge(l_R, n_R);
579 vivien 1.1.2.1 pig0.G.e.addMethodHole(n_R, hm);
580 vivien 1.1.2.1 }
581 vivien 1.1.2.1
582 vivien 1.1.2.1 Temp l_E = q.retex();
583 vivien 1.1.2.1 if(l_E != null){
584 vivien 1.1.2.1 pig1.G.I.removeEdges(l_E);
585 vivien 1.1.2.1 PANode n_E = node_rep.getCodeNode(q, PANode.EXCEPT);
586 vivien 1.1.2.1 pig1.G.I.addEdge(l_E, n_E);
587 vivien 1.1.2.1 pig1.G.e.addMethodHole(n_E, hm);
588 vivien 1.1.2.1 }
589 vivien 1.1.2.1
590 vivien 1.1.2.1 return new ODParIntGraphPair(pig0, pig1);
591 vivien 1.1.2.1 }
592 vivien 1.1.2.1
593 vivien 1.1.2.1 private static void markEscapedParameters(CALL q, HMethod hm,
594 vivien 1.1.2.1 ODParIntGraph pig) {
595 vivien 1.1.2.1 if(markEscapedParametersSpecial(q, hm, pig))
596 vivien 1.1.2.1 return;
597 vivien 1.1.2.1 List escaped = new LinkedList();
598 vivien 1.1.2.1 Temp[] params = q.params();
599 vivien 1.1.2.1 for(int i = 0; i < params.length; i++) {
600 vivien 1.1.2.1 HClass hc = q.paramType(i);
601 vivien 1.1.2.1 if(!hc.isPrimitive())
602 vivien 1.1.2.1 escaped.addAll(pig.G.I.pointedNodes(params[i]));
603 vivien 1.1.2.1 }
604 vivien 1.1.2.1
605 vivien 1.1.2.1 // Update the escape information
606 vivien 1.1.2.1 // 1. all the object parameters directly escape into the method hole
607 vivien 1.1.2.1 for(Iterator it = escaped.iterator(); it.hasNext(); )
608 vivien 1.1.2.1 pig.G.e.addMethodHole((PANode)it.next(), hm);
609 vivien 1.1.2.1 // 2. propagate the new escape information
610 vivien 1.1.2.1 pig.G.propagate(escaped);
611 vivien 1.1.2.1 }
612 vivien 1.1.2.1
613 vivien 1.1.2.1 // For some native methods, maybe only some of the parameters escape
614 vivien 1.1.2.1 // (ie, we know that the others are not "harmed").
615 vivien 1.1.2.1 // For the moment, we don't treat any method in this special way.
616 vivien 1.1.2.1 private static boolean markEscapedParametersSpecial(CALL q, HMethod hm,
617 vivien 1.1.2.1 ODParIntGraph pig) {
618 vivien 1.1.2.1 return false;
619 vivien 1.1.2.1 }
620 vivien 1.1.2.1
621 vivien 1.1.2.1 /** Updates the graph of the caller at an analyzed call site. This consists
622 vivien 1.1.2.1 * of mapping the important parts of the callee's graph into the graph of
623 vivien 1.1.2.1 * the caller. See the paper of Martin and Whaley for a description of the
624 vivien 1.1.2.1 * algorithm.<br>
625 vivien 1.1.2.1 * <b>Parameters:</b>
626 vivien 1.1.2.1 * <ul>
627 vivien 1.1.2.1 * <li>The <code>CALL</code> quad that represents the call site.<br>
628 vivien 1.1.2.1 * <li>The Parallel Interaction Graph of the caller
629 vivien 1.1.2.1 *(<code>pig_caller</code>) that models the memory state just before the
630 vivien 1.1.2.1 *call site.
631 vivien 1.1.2.1 * <li>The Parallel Interaction Graph of the callee
632 vivien 1.1.2.1 *(<code>pig_callee</code>). For efficiency reasons it's advisable to pass
633 vivien 1.1.2.1 *the reduced, external view of that graph.
634 vivien 1.1.2.1 * <li>The nodes representing the <b>formal</b> parameters of the callee.
635 vivien 1.1.2.1 *The actual parameters do not need to be sent: they will be retrieved
636 vivien 1.1.2.1 *from the <code>CALL</code> quad (the same for return and exception
637 vivien 1.1.2.1 *temporaries.
638 vivien 1.1.2.1 *</ul>
639 vivien 1.1.2.1 */
640 vivien 1.1.2.1 private static ODParIntGraphPair mapUp(ODPointerAnalysis pa,
641 vivien 1.1.2.1 MetaMethod mm,
642 vivien 1.1.2.1 CALL q,
643 vivien 1.1.2.1 ODParIntGraph pig_caller,
644 vivien 1.1.2.1 ODParIntGraph pig_callee) {
645 vivien 1.1.2.1 System.err.println("ERROR: mapUp unmodified should not be called");
646 vivien 1.1.2.1
647 vivien 1.1.2.1 // if native method, apply special treatment
648 vivien 1.1.2.1 if(pig_callee == null)
649 vivien 1.1.2.1 return treatNatives(pa, mm, q, pig_caller);
650 vivien 1.1.2.1
651 vivien 1.1.2.1 PANode[] callee_params = pa.getParamNodes(mm);
652 vivien 1.1.2.1
653 vivien 1.1.2.1 if(DEBUG){
654 vivien 1.1.2.1 System.out.println("Pig_caller:" + pig_caller);
655 vivien 1.1.2.1 System.out.println("Pig_callee:" + pig_callee);
656 vivien 1.1.2.1 }
657 vivien 1.1.2.1
658 vivien 1.1.2.1 // get the initial mapping: formal param -> actual parameter,
659 vivien 1.1.2.1 // and class node -> class node
660 vivien 1.1.2.1 Relation mu =
661 vivien 1.1.2.1 get_initial_mapping(q,pig_caller,pig_callee,callee_params);
662 vivien 1.1.2.1
663 vivien 1.1.2.1 if(DEBUG) System.out.println("Initial mapping:" + mu);
664 vivien 1.1.2.1
665 vivien 1.1.2.1 // update the node mapping by matching outside edges from the caller
666 vivien 1.1.2.1 // with inside edges from the callee
667 vivien 1.1.2.1 match_edges(mu,pig_caller,pig_callee);
668 vivien 1.1.2.1
669 vivien 1.1.2.1 if(DEBUG) System.out.println("After matching edges:" + mu);
670 vivien 1.1.2.1
671 vivien 1.1.2.1 // all the nodes from the caller (except for PARAM) are
672 vivien 1.1.2.1 // initially inserted into the caller's graph
673 vivien 1.1.2.1 compute_the_final_mapping(mu,pig_caller,pig_callee);
674 vivien 1.1.2.1
675 vivien 1.1.2.1 if(DEBUG) System.out.println("Final mapping:" + mu);
676 vivien 1.1.2.1
677 vivien 1.1.2.1
678 vivien 1.1.2.1 PAEdgeSet old_caller_I = (PAEdgeSet) pig_caller.G.I.clone();
679 vivien 1.1.2.1
680 vivien 1.1.2.1 // Inserts the image of the callee's graph into the caller's graph.
681 vivien 1.1.2.1 Set params = new HashSet();
682 vivien 1.1.2.1 for(int i=0;i<callee_params.length;i++)
683 vivien 1.1.2.1 params.add(callee_params[i]);
684 vivien 1.1.2.1 pig_caller.insertAllButArEo(pig_callee, mu, false, params);
685 vivien 1.1.2.1
686 vivien 1.1.2.1 // bring the actions of the callee into the caller's graph
687 vivien 1.1.2.1 bring_actions(pig_caller.ar, pig_callee.ar,
688 vivien 1.1.2.1 pig_caller.tau.activeThreadSet(), mu);
689 vivien 1.1.2.1
690 vivien 1.1.2.1 // bring the edge ordering relation into the caller's graph
691 vivien 1.1.2.1 if(!ODPointerAnalysis.IGNORE_EO)
692 vivien 1.1.2.1 bring_eo(pig_caller.eo, old_caller_I, pig_callee.eo,
693 vivien 1.1.2.1 pig_callee.G.O, mu);
694 vivien 1.1.2.1
695 vivien 1.1.2.1 // recompute the escape info
696 vivien 1.1.2.1 pig_caller.G.propagate();
697 vivien 1.1.2.1
698 vivien 1.1.2.1 if(DEBUG)
699 vivien 1.1.2.1 System.out.println("Unsimplified graph:\n" + pig_caller);
700 vivien 1.1.2.1
701 vivien 1.1.2.1 // simplify the graph by removing the empty loads
702 vivien 1.1.2.1 // pig_caller.removeEmptyLoads();
703 vivien 1.1.2.1
704 vivien 1.1.2.1 if(DEBUG)
705 vivien 1.1.2.1 System.out.println("Simplified graph:\n" + pig_caller);
706 vivien 1.1.2.1
707 vivien 1.1.2.1 // make a copy of the parallel interaction graph
708 vivien 1.1.2.1 ODParIntGraph pig_caller1 = (ODParIntGraph) (pig_caller.clone());
709 vivien 1.1.2.1
710 vivien 1.1.2.1 // set the edges for the exception on the out-edge 1
711 vivien 1.1.2.1 set_edges_res_ex(q.retex() , mu, pig_caller1, pig_callee.G.excp);
712 vivien 1.1.2.1 // set the edges for the result on the out-edge 0
713 vivien 1.1.2.1 set_edges_res_ex(q.retval(), mu, pig_caller, pig_callee.G.r);
714 vivien 1.1.2.1
715 vivien 1.1.2.1 if(DEBUG){
716 vivien 1.1.2.1 System.out.println("Final graphs:{");
717 vivien 1.1.2.1 System.out.println(" The graph on edge 0:");
718 vivien 1.1.2.1 System.out.println(pig_caller);
719 vivien 1.1.2.1 System.out.println(" The graph on edge 1:");
720 vivien 1.1.2.1 System.out.println(pig_caller1);
721 vivien 1.1.2.1 System.out.println("}");
722 vivien 1.1.2.1 }
723 vivien 1.1.2.1
724 vivien 1.1.2.1 return new ODParIntGraphPair(pig_caller, pig_caller1);
725 vivien 1.1.2.1 }
726 vivien 1.1.2.1
727 vivien 1.1.2.1 private static ODParIntGraphPair mapUp(ODPointerAnalysis pa,
728 vivien 1.1.2.1 MetaMethod callee_mm,
729 vivien 1.1.2.1 MetaMethod caller_mm,
730 vivien 1.1.2.1 CALL q,
731 vivien 1.1.2.1 ODParIntGraph pig_caller,
732 vivien 1.1.2.1 ODParIntGraph pig_callee) {
733 vivien 1.1.2.1
734 vivien 1.1.2.1 return mapUp(pa, callee_mm, caller_mm, q,
735 vivien 1.1.2.1 pig_caller, pig_callee,
736 vivien 1.1.2.1 null, true, true);
737 vivien 1.1.2.1 }
738 vivien 1.1.2.1
739 vivien 1.1.2.1 private static ODParIntGraphPair mapUp(ODPointerAnalysis pa,
740 vivien 1.1.2.1 MetaMethod callee_mm,
741 vivien 1.1.2.1 MetaMethod caller_mm,
742 vivien 1.1.2.1 CALL q,
743 vivien 1.1.2.1 ODParIntGraph pig_caller,
744 vivien 1.1.2.1 ODParIntGraph pig_callee,
745 vivien 1.1.2.1 MethodHole m_hole) {
746 vivien 1.1.2.1 return mapUp(pa, callee_mm, caller_mm, q,
747 vivien 1.1.2.1 pig_caller, pig_callee,
748 vivien 1.1.2.1 m_hole, true, true);
749 vivien 1.1.2.1 }
750 vivien 1.1.2.1
751 vivien 1.1.2.1 private static ODParIntGraphPair mapUp(ODPointerAnalysis pa,
752 vivien 1.1.2.1 MetaMethod callee_mm,
753 vivien 1.1.2.1 MetaMethod caller_mm,
754 vivien 1.1.2.1 CALL q,
755 vivien 1.1.2.1 ODParIntGraph pig_caller,
756 vivien 1.1.2.1 ODParIntGraph pig_callee,
757 vivien 1.1.2.1 MethodHole virtual_m_hole,
758 vivien 1.1.2.1 boolean verbose,
759 vivien 1.1.2.1 boolean updateformalnodes) {
760 vivien 1.1.2.1 long m_start = System.currentTimeMillis();
761 vivien 1.1.2.1 System.out.println("*** in mapUp:");
762 vivien 1.1.2.1 ODPointerAnalysis.number_of_mapups++;
763 vivien 1.1.2.1 long u_end = 0, u_start = 0;
764 vivien 1.1.2.1
765 vivien 1.1.2.1 HashSet toberemoved = new HashSet();
766 vivien 1.1.2.1
767 vivien 1.1.2.1 // Real hole computation
768 vivien 1.1.2.1 MethodHole m_hole = null;
769 vivien 1.1.2.1
770 vivien 1.1.2.1 if (virtual_m_hole==null){
771 vivien 1.1.2.1 m_hole = virtual_m_hole;
772 vivien 1.1.2.1 }
773 vivien 1.1.2.1 else {
774 vivien 1.1.2.1 m_hole = virtual_m_hole.IsInAs(pig_caller.odi.skippedCS);
775 vivien 1.1.2.1
776 vivien 1.1.2.1 if (m_hole==null){
777 vivien 1.1.2.1 System.err.println("Hole not found !!!");
778 vivien 1.1.2.1 System.out.println("Hole not found !!!");
779 vivien 1.1.2.1 System.out.println("Hole = " + virtual_m_hole);
780 vivien 1.1.2.1 System.out.println("Set = " + pig_caller.odi.skippedCS);
781 vivien 1.1.2.1 }
782 vivien 1.1.2.1 else {
783 vivien 1.1.2.1 pig_caller.odi.skippedCS.remove(m_hole);
784 vivien 1.1.2.1 if (virtual_m_hole.IsInAs(pig_caller.odi.skippedCS)!=null){
785 vivien 1.1.2.1 System.err.println("Hole found TWICE !!!");
786 vivien 1.1.2.1 System.out.println("Hole found TWICE !!!");
787 vivien 1.1.2.1 System.out.println("Hole original = " + virtual_m_hole);
788 vivien 1.1.2.1 System.out.println("Hole found = " + m_hole);
789 vivien 1.1.2.1 // System.out.println("Set whithout hole= " + pig_caller.method_holes);
790 vivien 1.1.2.1 }
791 vivien 1.1.2.1 }
792 vivien 1.1.2.1 }
793 vivien 1.1.2.1
794 vivien 1.1.2.1
795 vivien 1.1.2.1 if ((m_hole!=null)&&
796 vivien 1.1.2.1 (!ODPointerAnalysis.ON_DEMAND_ANALYSIS))
797 vivien 1.1.2.1 System.err.println("Error in mapUp: arguments inconsistent with context.");
798 vivien 1.1.2.1
799 vivien 1.1.2.1
800 vivien 1.1.2.1 // if native method, apply special treatment
801 vivien 1.1.2.1 if(pig_callee == null){
802 vivien 1.1.2.1 if (m_hole==null)
803 vivien 1.1.2.1 return treatNatives(pa, callee_mm, q, pig_caller);
804 vivien 1.1.2.1 else{
805 vivien 1.1.2.1 System.err.println("Problem in mapUp, semi-inconsistency");
806 vivien 1.1.2.1 System.out.println("Problem in mapUp, semi-inconsistency");
807 vivien 1.1.2.1 System.out.println("Hole: " + m_hole);
808 vivien 1.1.2.1 System.out.println(pig_caller);
809 vivien 1.1.2.1 pig_caller.odi.remove(m_hole);
810 vivien 1.1.2.1 return treatNatives(pa, callee_mm, q, pig_caller);
811 vivien 1.1.2.1 }
812 vivien 1.1.2.1 }
813 vivien 1.1.2.1
814 vivien 1.1.2.1
815 vivien 1.1.2.1 PANode [] callee_params = pa.getParamNodes(callee_mm);
816 vivien 1.1.2.1
817 vivien 1.1.2.1 // pig_caller.G.flushCaches();
818 vivien 1.1.2.1 // pig_caller.G.propagate();
819 vivien 1.1.2.1
820 vivien 1.1.2.1 if(DEBUG)
821 vivien 1.1.2.1 {
822 vivien 1.1.2.1 System.out.println("Pig_caller:" + pig_caller);
823 vivien 1.1.2.1 System.out.println("Pig_callee:" + pig_callee);
824 vivien 1.1.2.1 }
825 vivien 1.1.2.1
826 vivien 1.1.2.1
827 vivien 1.1.2.1 // get the initial mapping: formal param -> actual parameter,
828 vivien 1.1.2.1 // and class node -> class node
829 vivien 1.1.2.1 Relation first_mapping = null;
830 vivien 1.1.2.1 if (m_hole==null)
831 vivien 1.1.2.1 first_mapping = get_initial_mapping(q,pig_caller,pig_callee,callee_params);
832 vivien 1.1.2.1 else
833 vivien 1.1.2.1 first_mapping = get_initial_mapping(q,pig_callee,callee_params,m_hole);
834 vivien 1.1.2.1
835 vivien 1.1.2.1 // Printing
836 vivien 1.1.2.1 if(verbose) System.out.println("First mapping " + first_mapping);
837 vivien 1.1.2.1
838 vivien 1.1.2.1 if (verbose) {
839 vivien 1.1.2.1 for(int i=0; i<callee_params.length;i++){
840 vivien 1.1.2.1 System.out.print("Param " + callee_params[i] + "->");
841 cananian 1.7 for (Object node_imgO : first_mapping.getValues(callee_params[i])) {
842 cananian 1.7 PANode node_img = (PANode) node_imgO;
843 vivien 1.1.2.1 System.out.print(" " + node_img);
844 vivien 1.1.2.1 }
845 vivien 1.1.2.1 System.out.println();
846 vivien 1.1.2.1 }
847 vivien 1.1.2.1 }
848 vivien 1.1.2.1
849 vivien 1.1.2.1
850 vivien 1.1.2.1 if(DEBUG) System.out.println("Initial mapping:" + first_mapping);
851 vivien 1.1.2.1
852 vivien 1.1.2.1 // update the node mapping by matching outside edges from the caller
853 vivien 1.1.2.1 // with inside and outside edges from the callee
854 vivien 1.1.2.1 //tbu
855 vivien 1.1.2.1 if(verbose) System.out.println("Before matching edges:" + first_mapping);
856 vivien 1.1.2.1 if ((m_hole==null)||(!pa.ODA_precise))
857 vivien 1.1.2.1 match_edges(first_mapping, pig_caller, pig_callee);
858 vivien 1.1.2.1 else
859 vivien 1.1.2.1 match_edges(first_mapping, pig_caller, pig_callee, m_hole);
860 vivien 1.1.2.1
861 vivien 1.1.2.1 if(DEBUG) System.out.println("After matching edges:" + first_mapping);
862 vivien 1.1.2.1 if (verbose)
863 vivien 1.1.2.1 System.out.println("After matching edges:" + first_mapping);
864 vivien 1.1.2.1
865 vivien 1.1.2.1 // all the nodes from the callee (except for PARAM) are
866 vivien 1.1.2.1 // initially inserted into the caller's graph
867 vivien 1.1.2.1 compute_the_final_mapping(first_mapping,pig_caller,pig_callee);
868 vivien 1.1.2.1
869 vivien 1.1.2.1 if(verbose)
870 vivien 1.1.2.1 System.out.println("After final mapping:" + first_mapping);
871 vivien 1.1.2.1
872 vivien 1.1.2.1
873 vivien 1.1.2.1 // Inserts the image of the callee's graph into the caller's graph.
874 vivien 1.1.2.1 Set params = new HashSet();
875 vivien 1.1.2.1 for(int i=0;i<callee_params.length;i++)
876 vivien 1.1.2.1 params.add(callee_params[i]);
877 vivien 1.1.2.1
878 vivien 1.1.2.1 if (!ODPointerAnalysis.ON_DEMAND_ANALYSIS){
879 vivien 1.1.2.1 PAEdgeSet old_caller_I = (PAEdgeSet) pig_caller.G.I.clone();
880 vivien 1.1.2.1 pig_caller.insertAllButArEo(pig_callee, first_mapping, false, params);
881 vivien 1.1.2.1
882 vivien 1.1.2.1 // bring the actions of the callee into the caller's graph
883 vivien 1.1.2.1 bring_actions(pig_caller.ar, pig_callee.ar,
884 vivien 1.1.2.1 pig_caller.tau.activeThreadSet(), first_mapping);
885 vivien 1.1.2.1
886 vivien 1.1.2.1 // bring the edge ordering relation into the caller's graph
887 vivien 1.1.2.1 if(!ODPointerAnalysis.IGNORE_EO)
888 vivien 1.1.2.1 bring_eo(pig_caller.eo, old_caller_I, pig_callee.eo,
889 vivien 1.1.2.1 pig_callee.G.O, first_mapping);
890 vivien 1.1.2.1 }
891 vivien 1.1.2.1 else{
892 vivien 1.1.2.1 // tbu problem if m_hole==null
893 vivien 1.1.2.1 Set holes_b4_callee = pig_caller.odi.predecessors(m_hole);
894 vivien 1.1.2.1
895 vivien 1.1.2.1 PAEdgeSet org_O = (PAEdgeSet) pig_caller.G.O.clone();
896 vivien 1.1.2.1 PAEdgeSet org_I = (PAEdgeSet) pig_caller.G.I.clone();
897 vivien 1.1.2.1
898 vivien 1.1.2.1 ODInformation temp_odi = new ODInformation(pig_caller.odi.precise);
899 vivien 1.1.2.1 ODInformation tmp_odi_2 = new ODInformation(pig_caller.odi.precise);
900 vivien 1.1.2.1
901 vivien 1.1.2.1 if(verbose) System.out.println("B4 insertAllButArEoTau");
902 vivien 1.1.2.1 pig_caller.insertAllButArEoTau(pig_callee, first_mapping,
903 vivien 1.1.2.1 params,
904 vivien 1.1.2.1 holes_b4_callee,
905 vivien 1.1.2.1 temp_odi);
906 vivien 1.1.2.1 if(verbose) System.out.println("After insertAllButArEoTau");
907 vivien 1.1.2.1
908 vivien 1.1.2.1
909 vivien 1.1.2.1 pig_caller.G.flushCaches();
910 vivien 1.1.2.1 pig_caller.G.propagate();
911 vivien 1.1.2.1 // System.out.println("After first mapping " + pig_caller);
912 vivien 1.1.2.1
913 vivien 1.1.2.1 // The following won't be used if m_hole!=null, but the
914 vivien 1.1.2.1 // definition is common to enable more code sharing.
915 vivien 1.1.2.1 Relation second_mapping = null;
916 vivien 1.1.2.1 LightRelation second_mapping_extended =
917 vivien 1.1.2.1 new LightRelation();
918 vivien 1.1.2.1
919 vivien 1.1.2.1 if (m_hole!=null){
920 vivien 1.1.2.1 // We compute the interaction between the part of the
921 vivien 1.1.2.1 // caller pig *after* the call site, and the callee.
922 vivien 1.1.2.1
923 vivien 1.1.2.1 Relation nu = new LightRelation();
924 vivien 1.1.2.1 if ((m_hole.ret()!=null)&&
925 vivien 1.1.2.1 (pig_callee.G.r!=null)&&(!(pig_callee.G.r.isEmpty())))
926 vivien 1.1.2.1 nu.addAll(m_hole.ret(),pig_callee.G.r);
927 vivien 1.1.2.1 if ((m_hole.exc()!=null)&&
928 vivien 1.1.2.1 (pig_callee.G.excp!=null)&&(!(pig_callee.G.excp.isEmpty())))
929 vivien 1.1.2.1 nu.addAll(m_hole.exc(),pig_callee.G.excp);
930 vivien 1.1.2.1
931 vivien 1.1.2.1 if(verbose) System.out.println("Mapping before match " + nu);
932 vivien 1.1.2.1
933 vivien 1.1.2.1 match_edges(nu, first_mapping,
934 vivien 1.1.2.1 org_O,
935 vivien 1.1.2.1 pig_callee, pig_caller,
936 vivien 1.1.2.1 m_hole);
937 vivien 1.1.2.1
938 vivien 1.1.2.1 if (verbose) System.out.println("Mapping after match " + nu);
939 vivien 1.1.2.1
940 vivien 1.1.2.1 Relation extended_first_mapping =
941 vivien 1.1.2.1 (Relation) first_mapping.clone();
942 vivien 1.1.2.1
943 vivien 1.1.2.1 second_mapping =
944 vivien 1.1.2.1 projection(nu, extended_first_mapping);
945 vivien 1.1.2.1
946 vivien 1.1.2.1 if (verbose)
947 vivien 1.1.2.1 System.out.println("Mapping after projection " + second_mapping);
948 vivien 1.1.2.1
949 vivien 1.1.2.1 pig_caller.insertAllButArEoTau(org_O,
950 vivien 1.1.2.1 org_I,
951 vivien 1.1.2.1 second_mapping,
952 vivien 1.1.2.1 tmp_odi_2);
953 vivien 1.1.2.1
954 vivien 1.1.2.1
955 vivien 1.1.2.1 pig_caller.G.flushCaches();
956 vivien 1.1.2.1 pig_caller.G.propagate();
957 vivien 1.1.2.1 // System.out.println("After second mapping " + pig_caller);
958 vivien 1.1.2.1
959 vivien 1.1.2.1
960 vivien 1.1.2.1 if (updateformalnodes){
961 vivien 1.1.2.1 if (m_hole.ret()!=null)
962 vivien 1.1.2.1 toberemoved.add(m_hole.ret());
963 vivien 1.1.2.1 if (m_hole.exc()!=null)
964 vivien 1.1.2.1 toberemoved.add(m_hole.exc());
965 vivien 1.1.2.1 }
966 vivien 1.1.2.1
967 vivien 1.1.2.1 second_mapping_extended =
968 vivien 1.1.2.1 create_extended_mapping(pig_caller,
969 vivien 1.1.2.1 second_mapping,
970 vivien 1.1.2.1 toberemoved);
971 vivien 1.1.2.1
972 vivien 1.1.2.1 }
973 vivien 1.1.2.1
974 vivien 1.1.2.1 // ************************
975 vivien 1.1.2.1 // Updating escape functions of actual return and exception nodes
976 vivien 1.1.2.1 // ************************
977 vivien 1.1.2.1
978 vivien 1.1.2.1 if (m_hole.ret()!=null){
979 vivien 1.1.2.1 Set ret_methodholes = pig_caller.G.e.methodHolesSet(m_hole.ret());
980 vivien 1.1.2.1 if((!updateformalnodes)&&(ODInterProcPA.ret_strong_update))
981 vivien 1.1.2.1 ret_methodholes.remove(m_hole.callsite().method());
982 vivien 1.1.2.1 Set ret_nodesholes = pig_caller.G.e.nodeHolesSet(m_hole.ret());
983 vivien 1.1.2.1
984 cananian 1.7 for(Object ret_nO : pig_callee.G.r){
985 cananian 1.7 PANode ret_n = (PANode) ret_nO;
986 vivien 1.1.2.1 pig_caller.G.e.addMethodHoles(ret_n, ret_methodholes);
987 vivien 1.1.2.1 pig_caller.G.e.addNodeHoles(ret_n, ret_nodesholes);
988 vivien 1.1.2.1 }
989 vivien 1.1.2.1 }
990 vivien 1.1.2.1
991 vivien 1.1.2.1 if (m_hole.exc()!=null){
992 vivien 1.1.2.1 Set exc_methodholes = pig_caller.G.e.methodHolesSet(m_hole.exc());
993 vivien 1.1.2.1 if((!updateformalnodes)&&(ODInterProcPA.exc_strong_update))
994 vivien 1.1.2.1 exc_methodholes.remove(m_hole.callsite().method());
995 vivien 1.1.2.1 Set exc_nodesholes = pig_caller.G.e.nodeHolesSet(m_hole.exc());
996 cananian 1.7 for(Object excp_nO : pig_callee.G.excp){
997 cananian 1.7 PANode excp_n = (PANode) excp_nO;
998 vivien 1.1.2.1 pig_caller.G.e.addMethodHoles(excp_n, exc_methodholes);
999 vivien 1.1.2.1 pig_caller.G.e.addNodeHoles (excp_n, exc_nodesholes);
1000 vivien 1.1.2.1 }
1001 vivien 1.1.2.1 }
1002 vivien 1.1.2.1
1003 vivien 1.1.2.1 pig_caller.G.flushCaches();
1004 vivien 1.1.2.1 pig_caller.G.propagate();
1005 vivien 1.1.2.1 // System.out.println("After escape function update " + pig_caller);
1006 vivien 1.1.2.1
1007 vivien 1.1.2.1
1008 vivien 1.1.2.1 // **********************************
1009 vivien 1.1.2.1 // Updating return and exception sets
1010 vivien 1.1.2.1 // **********************************
1011 vivien 1.1.2.1
1012 vivien 1.1.2.1 if (m_hole!=null){
1013 vivien 1.1.2.1 Set new_ret = new LinearSet();
1014 vivien 1.1.2.1 projection(pig_caller.G.r,
1015 vivien 1.1.2.1 second_mapping_extended, new_ret);
1016 vivien 1.1.2.1 Set new_excp = new LinearSet();
1017 vivien 1.1.2.1 projection(pig_caller.G.excp,
1018 vivien 1.1.2.1 second_mapping_extended, new_excp);
1019 vivien 1.1.2.1
1020 vivien 1.1.2.1 pig_caller.G.r = new_ret;
1021 vivien 1.1.2.1 pig_caller.G.excp = new_excp;
1022 vivien 1.1.2.1 }
1023 vivien 1.1.2.1 // else{
1024 vivien 1.1.2.1 // new_ret = pig_caller.G.r;
1025 vivien 1.1.2.1 // new_excp = pig_caller.G.excp;
1026 vivien 1.1.2.1 // }
1027 vivien 1.1.2.1
1028 vivien 1.1.2.1
1029 vivien 1.1.2.1 // **********************************
1030 vivien 1.1.2.1 // Updating the classical part of the graph
1031 vivien 1.1.2.1 // **********************************
1032 vivien 1.1.2.1
1033 vivien 1.1.2.1 // Cleaning the formal exception and return node of the
1034 vivien 1.1.2.1 // method hole.
1035 vivien 1.1.2.1 if (updateformalnodes)
1036 vivien 1.1.2.1 clean_call(pig_caller, m_hole);
1037 vivien 1.1.2.1
1038 vivien 1.1.2.1 // Recomputing the escape info
1039 vivien 1.1.2.1 pig_caller.G.flushCaches();
1040 vivien 1.1.2.1 pig_caller.G.propagate();
1041 vivien 1.1.2.1 pig_caller.G.getReachableFromR();
1042 vivien 1.1.2.1 pig_caller.G.getReachableFromExcp();
1043 vivien 1.1.2.1
1044 vivien 1.1.2.1 if(DEBUG)
1045 vivien 1.1.2.1 System.out.println("Unsimplified graph:\n" + pig_caller);
1046 vivien 1.1.2.1
1047 vivien 1.1.2.1 // simplify the graph by removing the empty loads
1048 vivien 1.1.2.1 //pig_caller.removeEmptyLoads();
1049 vivien 1.1.2.1 Set emptyloads = new HashSet();
1050 vivien 1.1.2.1 Set fakeOutEdges = new HashSet();
1051 vivien 1.1.2.1 pig_caller.removeEmptyLoads(emptyloads, fakeOutEdges);
1052 vivien 1.1.2.1
1053 vivien 1.1.2.1 if(DEBUG)
1054 vivien 1.1.2.1 System.out.println("first_mapping : " + first_mapping);
1055 vivien 1.1.2.1 if(DEBUG)
1056 vivien 1.1.2.1 System.out.println("Empty loads : " + emptyloads);
1057 vivien 1.1.2.1
1058 vivien 1.1.2.1
1059 vivien 1.1.2.1 toberemoved.addAll(emptyloads);
1060 vivien 1.1.2.1
1061 vivien 1.1.2.1 if(DEBUG)
1062 vivien 1.1.2.1 System.out.println("Simplified graph:\n" + pig_caller);
1063 vivien 1.1.2.1
1064 vivien 1.1.2.1 // Cleaning the first and second mapping from the empty
1065 vivien 1.1.2.1 // load nodes. (The second mapping is notbused later on,
1066 vivien 1.1.2.1 // we only update the seconde mapping extended which is
1067 vivien 1.1.2.1 // used).
1068 cananian 1.7 for(Object nO : emptyloads){
1069 cananian 1.7 PANode n = (PANode) nO;
1070 vivien 1.1.2.1 first_mapping.remove(n,n);
1071 vivien 1.1.2.1 second_mapping_extended.remove(n,n);
1072 vivien 1.1.2.1 }
1073 vivien 1.1.2.1
1074 vivien 1.1.2.1 u_start = System.currentTimeMillis();
1075 vivien 1.1.2.1 ODInformation new_odi = new ODInformation(pig_caller.odi.precise);
1076 vivien 1.1.2.1 Set par_locks = pig_caller.odi.update(new_odi, pig_caller, pig_callee,
1077 vivien 1.1.2.1 first_mapping, second_mapping_extended,
1078 vivien 1.1.2.1 m_hole,
1079 vivien 1.1.2.1 temp_odi, tmp_odi_2, toberemoved);
1080 vivien 1.1.2.1 u_end = System.currentTimeMillis();
1081 vivien 1.1.2.1
1082 vivien 1.1.2.1 // ***************************
1083 vivien 1.1.2.1 // Updating active threads set
1084 vivien 1.1.2.1 // ***************************
1085 vivien 1.1.2.1
1086 vivien 1.1.2.1 PAThreadMap new_caller_threads = null;
1087 vivien 1.1.2.1
1088 vivien 1.1.2.1 if (m_hole!=null){
1089 vivien 1.1.2.1 new_caller_threads = (PAThreadMap) pig_caller.tau.clone();
1090 vivien 1.1.2.1 new_caller_threads.insert(new_caller_threads,
1091 vivien 1.1.2.1 second_mapping_extended);
1092 vivien 1.1.2.1 }
1093 vivien 1.1.2.1 else {
1094 vivien 1.1.2.1 new_caller_threads = pig_caller.tau;
1095 vivien 1.1.2.1 }
1096 vivien 1.1.2.1
1097 vivien 1.1.2.1 new_caller_threads.insert(pig_callee.tau, first_mapping);
1098 vivien 1.1.2.1
1099 vivien 1.1.2.1 PAThreadMap new_callee_threads = new PAThreadMap();
1100 vivien 1.1.2.1 new_callee_threads.insert(pig_callee.tau, first_mapping);
1101 vivien 1.1.2.1
1102 vivien 1.1.2.1
1103 vivien 1.1.2.1 // ***************************
1104 vivien 1.1.2.1 // Updating action repository
1105 vivien 1.1.2.1 // ***************************
1106 vivien 1.1.2.1
1107 vivien 1.1.2.1 // updating the actions of the caller (if necessary)
1108 vivien 1.1.2.1 ActionRepository new_ar_caller = null;
1109 vivien 1.1.2.1 if (m_hole!=null){
1110 vivien 1.1.2.1 new_ar_caller = new ActionRepository();
1111 vivien 1.1.2.1 update_actions(pig_caller.ar, new_ar_caller,
1112 vivien 1.1.2.1 second_mapping_extended);
1113 vivien 1.1.2.1 }
1114 vivien 1.1.2.1 else {
1115 vivien 1.1.2.1 new_ar_caller = pig_caller.ar;
1116 vivien 1.1.2.1 }
1117 vivien 1.1.2.1
1118 vivien 1.1.2.1 // bring the actions of the callee into the caller's graph
1119 vivien 1.1.2.1 // The use of pig_caller.tau.activeThreadSet() is
1120 vivien 1.1.2.1 // conservative.
1121 vivien 1.1.2.1 bring_actions(new_ar_caller, pig_callee.ar,
1122 vivien 1.1.2.1 pig_caller.tau.activeThreadSet(), first_mapping);
1123 vivien 1.1.2.1
1124 vivien 1.1.2.1 // add actions relative to loads of the caller which
1125 vivien 1.1.2.1 // happened in parallel to the callee
1126 vivien 1.1.2.1 if (m_hole!=null){
1127 vivien 1.1.2.1 actions_add_ld(pig_callee.odi,
1128 vivien 1.1.2.1 pig_caller,
1129 vivien 1.1.2.1 new_ar_caller,
1130 vivien 1.1.2.1 second_mapping_extended,
1131 vivien 1.1.2.1 m_hole,
1132 vivien 1.1.2.1 new_callee_threads.activeThreadSet());
1133 vivien 1.1.2.1
1134 vivien 1.1.2.1 actions_add_sync(new_ar_caller,
1135 vivien 1.1.2.1 par_locks,
1136 vivien 1.1.2.1 new_callee_threads.activeThreadSet());
1137 vivien 1.1.2.1 }
1138 vivien 1.1.2.1
1139 vivien 1.1.2.1
1140 vivien 1.1.2.1
1141 vivien 1.1.2.1 //***********************
1142 vivien 1.1.2.1 // Storing the new values
1143 vivien 1.1.2.1 //***********************
1144 vivien 1.1.2.1
1145 vivien 1.1.2.1 pig_caller.odi = new_odi;
1146 vivien 1.1.2.1 pig_caller.tau = new_caller_threads;
1147 vivien 1.1.2.1 pig_caller.ar = new_ar_caller;
1148 vivien 1.1.2.1 }
1149 vivien 1.1.2.1
1150 vivien 1.1.2.1 // Cleaning the formal exception and return node.
1151 vivien 1.1.2.1 if (updateformalnodes)
1152 vivien 1.1.2.1 clean_call(pig_caller, m_hole);
1153 vivien 1.1.2.1
1154 vivien 1.1.2.1 // recompute the escape info
1155 vivien 1.1.2.1 pig_caller.G.flushCaches();
1156 vivien 1.1.2.1 pig_caller.G.propagate();
1157 vivien 1.1.2.1 pig_caller.G.getReachableFromR();
1158 vivien 1.1.2.1 pig_caller.G.getReachableFromExcp();
1159 vivien 1.1.2.1
1160 vivien 1.1.2.1
1161 vivien 1.1.2.1 if(DEBUG)
1162 vivien 1.1.2.1 System.out.println("Unsimplified graph:\n" + pig_caller);
1163 vivien 1.1.2.1
1164 vivien 1.1.2.1 // simplify the graph by removing the empty loads
1165 vivien 1.1.2.1 //pig_caller.removeEmptyLoads();
1166 vivien 1.1.2.1 // Set emptyloads = new HashSet();
1167 vivien 1.1.2.1 // Set fakeOutEdges = new HashSet();
1168 vivien 1.1.2.1 // pig_caller.removeEmptyLoads(emptyloads, fakeOutEdges);
1169 vivien 1.1.2.1
1170 vivien 1.1.2.1 if(DEBUG)
1171 vivien 1.1.2.1 System.out.println("Simplified graph:\n" + pig_caller);
1172 vivien 1.1.2.1
1173 vivien 1.1.2.1 // make a copy of the parallel interaction graph
1174 vivien 1.1.2.1 ODParIntGraph pig_caller1 = null;
1175 vivien 1.1.2.1
1176 vivien 1.1.2.1
1177 vivien 1.1.2.1 if (m_hole==null){
1178 vivien 1.1.2.1 pig_caller1 = (ODParIntGraph) (pig_caller.clone());
1179 vivien 1.1.2.1 // set the edges for the exception on the out-edge 1
1180 vivien 1.1.2.1 set_edges_res_ex(q.retex() , first_mapping, pig_caller1, pig_callee.G.excp);
1181 vivien 1.1.2.1 // set the edges for the result on the out-edge 0
1182 vivien 1.1.2.1 set_edges_res_ex(q.retval(), first_mapping, pig_caller, pig_callee.G.r);
1183 vivien 1.1.2.1 }
1184 vivien 1.1.2.1 else{
1185 vivien 1.1.2.1 pig_caller1 = pig_caller;
1186 vivien 1.1.2.1 // pig_callee.G.excp and pig_callee.G.r have already been
1187 vivien 1.1.2.1 // updated and we are not interested in the value of variables...
1188 vivien 1.1.2.1 }
1189 vivien 1.1.2.1
1190 vivien 1.1.2.1
1191 vivien 1.1.2.1 if(DEBUG){
1192 vivien 1.1.2.1 System.out.println("Final graphs:{");
1193 vivien 1.1.2.1 System.out.println(" The graph on edge 0:");
1194 vivien 1.1.2.1 System.out.println(pig_caller);
1195 vivien 1.1.2.1 System.out.println(" The graph on edge 1:");
1196 vivien 1.1.2.1 System.out.println(pig_caller1);
1197 vivien 1.1.2.1 System.out.println("}");
1198 vivien 1.1.2.1 }
1199 vivien 1.1.2.1
1200 vivien 1.1.2.1 long m_end = System.currentTimeMillis();
1201 vivien 1.1.2.1 // System.err.println("Timing mapUp: " + (m_end - m_start) + "ms for "+
1202 vivien 1.1.2.1 // caller_mm);
1203 vivien 1.1.2.1 // System.out.println("Final graph:");
1204 vivien 1.1.2.1 // System.out.println(pig_caller);
1205 vivien 1.1.2.1
1206 vivien 1.1.2.1 System.out.print("Timing mapUp: " + (m_end - m_start) + "ms for "+
1207 vivien 1.1.2.1 caller_mm);
1208 vivien 1.1.2.1 System.out.println("[update : " + (u_end - u_start) + "]");
1209 vivien 1.1.2.1 return new ODParIntGraphPair(pig_caller, pig_caller1);
1210 vivien 1.1.2.1 }
1211 vivien 1.1.2.1
1212 vivien 1.1.2.1
1213 vivien 1.1.2.1
1214 vivien 1.1.2.1 // private static void map_callee_method_holes(ODPointerAnalysis pa,
1215 vivien 1.1.2.1 // MetaMethod caller_mm,
1216 vivien 1.1.2.1 // MetaMethod callee_mm,
1217 vivien 1.1.2.1 // Relation mu,
1218 vivien 1.1.2.1 // CALL q){
1219 vivien 1.1.2.1
1220 vivien 1.1.2.1 // // Preparation of the caller enhanced escape function
1221 vivien 1.1.2.1 // Set _holeset = (Set)pa.hash_method_holes.get(caller_mm);
1222 vivien 1.1.2.1 // HashSet holeset = null;
1223 vivien 1.1.2.1 // if (_holeset==null)
1224 vivien 1.1.2.1 // holeset = new HashSet();
1225 vivien 1.1.2.1 // else
1226 vivien 1.1.2.1 // holeset = (HashSet) _holeset;
1227 vivien 1.1.2.1
1228 vivien 1.1.2.1
1229 vivien 1.1.2.1 // // Specialization of the callee enhanced escape function
1230 vivien 1.1.2.1 // Set calleeset = (Set) pa.hash_method_holes.get(callee_mm);
1231 vivien 1.1.2.1
1232 vivien 1.1.2.1 // if (calleeset==null)
1233 vivien 1.1.2.1 // System.out.println(" no callee enhanced escape function");
1234 vivien 1.1.2.1 // else{
1235 vivien 1.1.2.1 // HashSet calleeHset = (HashSet) calleeset;
1236 vivien 1.1.2.1 // HashSet mappedcalleeset = new HashSet();
1237 vivien 1.1.2.1
1238 vivien 1.1.2.1 // System.out.println(" Original callee enhanced escape function");
1239 vivien 1.1.2.1 // for(Iterator it = calleeHset.iterator(); it.hasNext(); ){
1240 vivien 1.1.2.1 // MethodHole hole = (MethodHole) it.next();
1241 vivien 1.1.2.1 // System.out.println(" " + hole);
1242 vivien 1.1.2.1 // }
1243 vivien 1.1.2.1
1244 vivien 1.1.2.1 // // Loop on the MethodHoles
1245 vivien 1.1.2.1 // for(Iterator it = calleeHset.iterator(); it.hasNext(); ){
1246 vivien 1.1.2.1 // MethodHole hole = (MethodHole) it.next();
1247 vivien 1.1.2.1
1248 vivien 1.1.2.1 // Set [] old_caller_params = hole.ungroupedparameters();
1249 vivien 1.1.2.1 // Set oldparams = hole.parameters();
1250 vivien 1.1.2.1 // CALL site = hole.callsite();
1251 vivien 1.1.2.1 // HMethod hm = site.method();
1252 vivien 1.1.2.1
1253 vivien 1.1.2.1 // // Initialization of the new array of parameters
1254 vivien 1.1.2.1 // Set [] new_caller_params = new Set[old_caller_params.length];
1255 vivien 1.1.2.1 // for(int i = 0; i< old_caller_params.length; i++)
1256 vivien 1.1.2.1 // new_caller_params[i] = new HashSet();
1257 vivien 1.1.2.1
1258 vivien 1.1.2.1 // // Loop on the parameters
1259 vivien 1.1.2.1 // for(int i = 0; i< old_caller_params.length; i++)
1260 vivien 1.1.2.1 // if ((old_caller_params[i]!=null)&&
1261 vivien 1.1.2.1 // (!(old_caller_params[i].isEmpty())))
1262 vivien 1.1.2.1 // // Loop on the possible values for the current
1263 vivien 1.1.2.1 // // parameter
1264 vivien 1.1.2.1 // for(Iterator parit = (old_caller_params[i]).iterator();
1265 vivien 1.1.2.1 // parit.hasNext(); ){
1266 vivien 1.1.2.1 // PANode param = (PANode) parit.next();
1267 vivien 1.1.2.1
1268 vivien 1.1.2.1 // // If the node param is a key in mu, it is
1269 vivien 1.1.2.1 // // a formal parameter. We project it on
1270 vivien 1.1.2.1 // // the correspondant possible actual
1271 vivien 1.1.2.1 // // argument.
1272 vivien 1.1.2.1 // if (mu.containsKey(param)){
1273 vivien 1.1.2.1 // Set projection = mu.getValues(param);
1274 vivien 1.1.2.1 // (new_caller_params[i]).addAll(projection);
1275 vivien 1.1.2.1 // }
1276 vivien 1.1.2.1 // else
1277 vivien 1.1.2.1 // // Otherwise, we check whether the
1278 vivien 1.1.2.1 // // node param is a node which is
1279 vivien 1.1.2.1 // // specialized, and replace it by its
1280 vivien 1.1.2.1 // // specialization.
1281 vivien 1.1.2.1 // if ((ODPointerAnalysis.CALL_CONTEXT_SENSITIVE)&&
1282 vivien 1.1.2.1 // (param.csSpecialize(q)!=null))
1283 vivien 1.1.2.1 // (new_caller_params[i]).add(param.csSpecialize(q));
1284 vivien 1.1.2.1 // else
1285 vivien 1.1.2.1 // (new_caller_params[i]).add(param);
1286 vivien 1.1.2.1 // }
1287 vivien 1.1.2.1 // // Finally the mapped and specialized callee's
1288 vivien 1.1.2.1 // // MethodHoles is added to the set.
1289 vivien 1.1.2.1 // mappedcalleeset.add(new MethodHole(hole, new_caller_params));
1290 vivien 1.1.2.1 // }
1291 vivien 1.1.2.1
1292 vivien 1.1.2.1
1293 vivien 1.1.2.1 // System.out.println(" Updated callee enhanced escape function");
1294 vivien 1.1.2.1 // for(Iterator it = mappedcalleeset.iterator(); it.hasNext(); ){
1295 vivien 1.1.2.1 // MethodHole hole = (MethodHole) it.next();
1296 vivien 1.1.2.1 // System.out.println(" " + hole);
1297 vivien 1.1.2.1 // }
1298 vivien 1.1.2.1
1299 vivien 1.1.2.1 // // The set of the mapped and specialized callee's
1300 vivien 1.1.2.1 // // MethodHoles is added to the caller's
1301 vivien 1.1.2.1 // holeset.addAll((Set)mappedcalleeset);
1302 vivien 1.1.2.1 // pa.hash_method_holes.put(caller_mm, holeset);
1303 vivien 1.1.2.1 // }
1304 vivien 1.1.2.1 // }
1305 vivien 1.1.2.1
1306 vivien 1.1.2.1
1307 vivien 1.1.2.1
1308 vivien 1.1.2.1 /** Sets the initial mapping: each formal parameter is mapped
1309 vivien 1.1.2.1 * to the nodes pointed to by the corresponding actual argument
1310 vivien 1.1.2.1 * (into the caller graph) and each static node is mapped to itself.
1311 vivien 1.1.2.1 * (only the static nodes that really point to something are important,
1312 vivien 1.1.2.1 * the leaf static nodes are not interesting in our analysis)
1313 vivien 1.1.2.1 */
1314 vivien 1.1.2.1 private static Relation get_initial_mapping(CALL q,
1315 vivien 1.1.2.1 ODParIntGraph pig_caller,
1316 vivien 1.1.2.1 ODParIntGraph pig_callee,
1317 vivien 1.1.2.1 PANode[] callee_params){
1318 vivien 1.1.2.1 Relation mu = new LightRelation();
1319 vivien 1.1.2.1 Temp[] args = q.params();
1320 vivien 1.1.2.1 int object_params_count = 0;
1321 vivien 1.1.2.1
1322 vivien 1.1.2.1 // map the object formal parameter nodes to the actual arguments
1323 vivien 1.1.2.1 System.out.println("get_initial_mapping for " + args.length + " parameter(s)");
1324 vivien 1.1.2.1 for(int i = 0; i < args.length; i++){
1325 vivien 1.1.2.1 if(!q.paramType(i).isPrimitive()){
1326 vivien 1.1.2.1 // System.out.println(" for the " + i + "-th parameter (" +
1327 vivien 1.1.2.1 // callee_params[object_params_count] + ")");
1328 vivien 1.1.2.1
1329 vivien 1.1.2.1 mu.addAll(callee_params[object_params_count],
1330 vivien 1.1.2.1 pig_caller.G.I.pointedNodes(args[i]));
1331 vivien 1.1.2.1 object_params_count++;
1332 vivien 1.1.2.1
1333 vivien 1.1.2.1 // Just for debugging
1334 vivien 1.1.2.1 Set caller_params = pig_caller.G.I.pointedNodes(args[i]);
1335 vivien 1.1.2.1 if (caller_params.size()==0){
1336 vivien 1.1.2.1 System.out.println(" param " + args[i] + " -> emptyset");
1337 vivien 1.1.2.1 }
1338 vivien 1.1.2.1 else{
1339 vivien 1.1.2.1 Iterator parsetit=(caller_params).iterator();
1340 vivien 1.1.2.1 System.out.print(" param " + args[i] + " ->");
1341 vivien 1.1.2.1 while(parsetit.hasNext()){
1342 vivien 1.1.2.1 PANode n = (PANode) parsetit.next();
1343 vivien 1.1.2.1 System.out.print(" " + n);
1344 vivien 1.1.2.1 }
1345 vivien 1.1.2.1 System.out.println(" .");
1346 vivien 1.1.2.1 }
1347 vivien 1.1.2.1
1348 vivien 1.1.2.1
1349 vivien 1.1.2.1 }
1350 vivien 1.1.2.1 else{
1351 vivien 1.1.2.1 System.out.println(" for the " + i + "-th parameter.");
1352 vivien 1.1.2.1 }
1353 vivien 1.1.2.1 }
1354 vivien 1.1.2.1
1355 vivien 1.1.2.1 if(object_params_count != callee_params.length){
1356 vivien 1.1.2.1 System.err.println("Fatal error in get_initial_mapping");
1357 vivien 1.1.2.1 System.out.println("\tDifferent numbers of object formal " +
1358 vivien 1.1.2.1 "parameters (" + callee_params.length +
1359 vivien 1.1.2.1 ") and object arguments (" +
1360 vivien 1.1.2.1 object_params_count + ")");
1361 vivien 1.1.2.1 System.out.println(q);
1362 vivien 1.1.2.1 System.exit(1);
1363 vivien 1.1.2.1 }
1364 vivien 1.1.2.1
1365 vivien 1.1.2.1 // map the static nodes to themselves;
1366 vivien 1.1.2.1 // only the static nodes that appear as sources of the outside edges
1367 vivien 1.1.2.1 // must be initially mapped
1368 vivien 1.1.2.1 process_STATICs(pig_callee.G.O.allSourceNodes(), mu);
1369 vivien 1.1.2.1
1370 vivien 1.1.2.1 return mu;
1371 vivien 1.1.2.1 }
1372 vivien 1.1.2.1
1373 vivien 1.1.2.1 private static Relation get_initial_mapping(CALL q,
1374 vivien 1.1.2.1 ODParIntGraph pig_callee,
1375 vivien 1.1.2.1 PANode[] callee_params,
1376 vivien 1.1.2.1 MethodHole hole){
1377 vivien 1.1.2.1 Relation mu = new LightRelation();
1378 vivien 1.1.2.1 Temp[] args = q.params();
1379 vivien 1.1.2.1 Set [] caller_params = hole.ungroupedparameters();
1380 vivien 1.1.2.1 int object_params_count = 0;
1381 vivien 1.1.2.1
1382 vivien 1.1.2.1 // map the object formal parameter nodes to the actual arguments
1383 vivien 1.1.2.1 // System.out.println("get_initial_mapping for " + args.length + " parameter(s)");
1384 vivien 1.1.2.1 for(int i = 0; i < args.length; i++){
1385 vivien 1.1.2.1 if(!q.paramType(i).isPrimitive()){
1386 vivien 1.1.2.1 // System.out.println(" for the " + i + "-th parameter (" +
1387 vivien 1.1.2.1 // callee_params[object_params_count] + ")");
1388 vivien 1.1.2.1
1389 vivien 1.1.2.1 mu.addAll(callee_params[object_params_count],
1390 vivien 1.1.2.1 caller_params[i]);
1391 vivien 1.1.2.1 object_params_count++;
1392 vivien 1.1.2.1
1393 vivien 1.1.2.1
1394 vivien 1.1.2.1 // Just for debugging
1395 vivien 1.1.2.1 Set caller_params_i = caller_params[i];
1396 vivien 1.1.2.1 if (caller_params_i.size()==0){
1397 vivien 1.1.2.1 System.out.println(" param " + i + " -> emptyset");
1398 vivien 1.1.2.1 }
1399 vivien 1.1.2.1 // else{
1400 vivien 1.1.2.1 // Iterator parsetit=(caller_params_i).iterator();
1401 vivien 1.1.2.1 // System.out.print(" param " + args[i] + " ->");
1402 vivien 1.1.2.1 // while(parsetit.hasNext()){
1403 vivien 1.1.2.1 // PANode n = (PANode) parsetit.next();
1404 vivien 1.1.2.1 // System.out.print(" " + n);
1405 vivien 1.1.2.1 // }
1406 vivien 1.1.2.1 // System.out.println(" .");
1407 vivien 1.1.2.1 // }
1408 vivien 1.1.2.1
1409 vivien 1.1.2.1
1410 vivien 1.1.2.1 }
1411 vivien 1.1.2.1 // else{
1412 vivien 1.1.2.1 // System.out.println(" for the " + i + "-th parameter.");
1413 vivien 1.1.2.1 // }
1414 vivien 1.1.2.1 }
1415 vivien 1.1.2.1
1416 vivien 1.1.2.1 if(object_params_count != callee_params.length){
1417 vivien 1.1.2.1 System.err.println("Fatal error in get_initial_mapping");
1418 vivien 1.1.2.1 System.out.println("\tDifferent numbers of object formal " +
1419 vivien 1.1.2.1 "parameters (" + callee_params.length +
1420 vivien 1.1.2.1 ") and object arguments (" +
1421 vivien 1.1.2.1 object_params_count + ")");
1422 vivien 1.1.2.1 System.out.println(q);
1423 vivien 1.1.2.1 System.exit(1);
1424 vivien 1.1.2.1 }
1425 vivien 1.1.2.1
1426 vivien 1.1.2.1 // map the static nodes to themselves;
1427 vivien 1.1.2.1 // only the static nodes that appear as sources of the outside edges
1428 vivien 1.1.2.1 // must be initially mapped
1429 vivien 1.1.2.1 process_STATICs(pig_callee.G.O.allSourceNodes(), mu);
1430 vivien 1.1.2.1
1431 vivien 1.1.2.1 return mu;
1432 vivien 1.1.2.1 }
1433 vivien 1.1.2.1
1434 vivien 1.1.2.1
1435 vivien 1.1.2.1 private static Relation get_secondary_mapping(CALL q,
1436 vivien 1.1.2.1 ODParIntGraph pig_callee,
1437 vivien 1.1.2.1 PANode[] callee_params,
1438 vivien 1.1.2.1 MethodHole hole,
1439 vivien 1.1.2.1 Set nodes,
1440 vivien 1.1.2.1 Relation mu,
1441 vivien 1.1.2.1 boolean type){
1442 vivien 1.1.2.1 Relation nu = new LightRelation();
1443 vivien 1.1.2.1 Temp[] args = q.params();
1444 vivien 1.1.2.1 Set [] caller_params = hole.ungroupedparameters();
1445 vivien 1.1.2.1
1446 vivien 1.1.2.1 // map the actual arguments to themselves
1447 vivien 1.1.2.1 for(int i = 0; i < args.length; i++)
1448 vivien 1.1.2.1 if(!q.paramType(i).isPrimitive())
1449 cananian 1.7 for(Object nodeO : caller_params[i]){
1450 cananian 1.7 PANode node = (PANode) nodeO;
1451 vivien 1.1.2.1 nu.add(node,node);
1452 vivien 1.1.2.1 }
1453 vivien 1.1.2.1
1454 vivien 1.1.2.1 PANode org = null;
1455 vivien 1.1.2.1 if (type==true) {//We are dealing with the return nodes
1456 vivien 1.1.2.1 // We map the formal return node to the actuals ones
1457 vivien 1.1.2.1 org = hole.ret();
1458 vivien 1.1.2.1 }
1459 vivien 1.1.2.1 else{
1460 vivien 1.1.2.1 // We map the formal exception node to the actuals ones
1461 vivien 1.1.2.1 org = hole.exc();
1462 vivien 1.1.2.1 }
1463 vivien 1.1.2.1
1464 vivien 1.1.2.1 // Set of the return/exception nodes (after the mu mapping)
1465 vivien 1.1.2.1 final Set mu_nodes = new HashSet();
1466 vivien 1.1.2.1 Iterator it = nodes.iterator();
1467 vivien 1.1.2.1 while(it.hasNext())
1468 vivien 1.1.2.1 mu_nodes.addAll(mu.getValues((PANode) it.next()));
1469 vivien 1.1.2.1 // pig_caller.G.I.addEdges(l,mu_nodes);
1470 vivien 1.1.2.1
1471 vivien 1.1.2.1 nu.addAll(org,mu_nodes);
1472 vivien 1.1.2.1
1473 vivien 1.1.2.1 System.out.print(" " + org + "->");
1474 vivien 1.1.2.1 if ((nodes!=null)&&(!nodes.isEmpty()))
1475 cananian 1.7 for(Object nO : nodes){
1476 cananian 1.7 PANode n = (PANode) nO;
1477 vivien 1.1.2.1 System.out.print(" " + n);
1478 vivien 1.1.2.1 }
1479 vivien 1.1.2.1 System.out.print(" ->");
1480 vivien 1.1.2.1 if ((mu_nodes!=null)&&(!mu_nodes.isEmpty()))
1481 cananian 1.7 for(Object m_nO : mu_nodes){
1482 cananian 1.7 PANode m_n = (PANode) m_nO;
1483 vivien 1.1.2.1 System.out.print(" " + m_n);
1484 vivien 1.1.2.1 }
1485 vivien 1.1.2.1 System.out.println(".");
1486 vivien 1.1.2.1
1487 vivien 1.1.2.1 return nu;
1488 vivien 1.1.2.1 }
1489 vivien 1.1.2.1
1490 vivien 1.1.2.1 private static Relation get_secondary_mapping(ODParIntGraph pig_callee,
1491 vivien 1.1.2.1 PANode[] callee_params,
1492 vivien 1.1.2.1 MethodHole hole){
1493 vivien 1.1.2.1 Relation nu = new LightRelation();
1494 vivien 1.1.2.1 CALL q = hole.callsite();
1495 vivien 1.1.2.1 int n_args = q.params().length;
1496 vivien 1.1.2.1 Set [] caller_params = hole.ungroupedparameters();
1497 vivien 1.1.2.1
1498 vivien 1.1.2.1 int object_params_count = 0;
1499 vivien 1.1.2.1
1500 vivien 1.1.2.1 // map the object actual argumenst nodes to the formal parameters
1501 vivien 1.1.2.1 for(int i = 0; i < n_args; i++){
1502 vivien 1.1.2.1 if(!q.paramType(i).isPrimitive()){
1503 vivien 1.1.2.1 for(Iterator it = caller_params[i].iterator(); it.hasNext();)
1504 vivien 1.1.2.1 nu.add(it.next(),callee_params[object_params_count]);
1505 vivien 1.1.2.1
1506 vivien 1.1.2.1 object_params_count++;
1507 vivien 1.1.2.1 }
1508 vivien 1.1.2.1 }
1509 vivien 1.1.2.1
1510 vivien 1.1.2.1 if(object_params_count != callee_params.length){
1511 vivien 1.1.2.1 System.err.println("Fatal error in get_initial_mapping");
1512 vivien 1.1.2.1 System.out.println("\tDifferent numbers of object formal " +
1513 vivien 1.1.2.1 "parameters (" + callee_params.length +
1514 vivien 1.1.2.1 ") and object arguments (" +
1515 vivien 1.1.2.1 object_params_count + ")");
1516 vivien 1.1.2.1 System.out.println(q);
1517 vivien 1.1.2.1 System.exit(1);
1518 vivien 1.1.2.1 }
1519 vivien 1.1.2.1
1520 vivien 1.1.2.1 // Map the formal return node to the actual return nodes
1521 vivien 1.1.2.1 // System.out.println("before adding return hole " + hole.ret());
1522 vivien 1.1.2.1 // print_relation(nu);
1523 vivien 1.1.2.1 nu.addAll(hole.ret(), pig_callee.G.r);
1524 vivien 1.1.2.1 // System.out.println(" after adding return hole " + hole.ret());
1525 vivien 1.1.2.1 // print_relation(nu);
1526 vivien 1.1.2.1
1527 vivien 1.1.2.1 // Map the formal exception node to the actual exception nodes
1528 vivien 1.1.2.1 nu.addAll(hole.exc(), pig_callee.G.excp);
1529 vivien 1.1.2.1
1530 vivien 1.1.2.1
1531 vivien 1.1.2.1
1532 vivien 1.1.2.1 // map the static nodes to themselves; only the static nodes
1533 vivien 1.1.2.1 // that appear as sources of the outside edges must be
1534 vivien 1.1.2.1 // initially mapped
1535 vivien 1.1.2.1 //
1536 vivien 1.1.2.1 // Is this necessary ?
1537 vivien 1.1.2.1
1538 vivien 1.1.2.1 process_STATICs(pig_callee.G.O.allSourceNodes(), nu);
1539 vivien 1.1.2.1
1540 vivien 1.1.2.1 return nu;
1541 vivien 1.1.2.1 }
1542 vivien 1.1.2.1
1543 vivien 1.1.2.1
1544 vivien 1.1.2.1 private static void map_mapping(Relation reference, Relation addenda){
1545 vivien 1.1.2.1 Set keys = addenda.keys();
1546 cananian 1.7 for(Object mappedO : keys){
1547 cananian 1.7 PANode mapped = (PANode) mappedO;
1548 vivien 1.1.2.1 Set image = addenda.getValues(mapped);
1549 vivien 1.1.2.1 reference.addAll(mapped, projection(image, reference, new LinearSet()));
1550 vivien 1.1.2.1 }
1551 vivien 1.1.2.1 }
1552 vivien 1.1.2.1
1553 vivien 1.1.2.1
1554 vivien 1.1.2.1
1555 vivien 1.1.2.1 // private static Set [] get_caller_params(CALL q, ODParIntGraph pig_caller){
1556 vivien 1.1.2.1 // Temp[] args = q.params();
1557 vivien 1.1.2.1 // Set caller_params[args];
1558 vivien 1.1.2.1 // int object_params_count = 0;
1559 vivien 1.1.2.1
1560 vivien 1.1.2.1 // // map the object formal parameter nodes to the actual arguments
1561 vivien 1.1.2.1 // System.out.println("get_initial_mapping for " + args.length + " parameter(s)");
1562 vivien 1.1.2.1 // for(int i = 0; i < args.length; i++){
1563 vivien 1.1.2.1 // if(!q.paramType(i).isPrimitive()){
1564 vivien 1.1.2.1 // caller_params[i] = pig_caller.G.I.pointedNodes(args[i]);
1565 vivien 1.1.2.1
1566 vivien 1.1.2.1 // if (caller_params[i].size()==0){
1567 vivien 1.1.2.1 // System.out.println(" param " + args[i] + " -> emptyset");
1568 vivien 1.1.2.1 // }
1569 vivien 1.1.2.1 // else{
1570 vivien 1.1.2.1 // Iterator parsetit=(caller_params).iterator();
1571 vivien 1.1.2.1 // System.out.print(" param " + args[i] + " ->");
1572 vivien 1.1.2.1 // while(parsetit.hasNext()){
1573 vivien 1.1.2.1 // PANode n = (PANode) parsetit.next();
1574 vivien 1.1.2.1 // System.out.print(" " + n);
1575 vivien 1.1.2.1 // }
1576 vivien 1.1.2.1 // System.out.println(" .");
1577 vivien 1.1.2.1 // }
1578 vivien 1.1.2.1 // object_params_count++;
1579 vivien 1.1.2.1
1580 vivien 1.1.2.1 // }
1581 vivien 1.1.2.1 // else{
1582 vivien 1.1.2.1 // System.out.println(" for the " + i + "-th parameter.");
1583 vivien 1.1.2.1 // }
1584 vivien 1.1.2.1 // }
1585 vivien 1.1.2.1
1586 vivien 1.1.2.1 // return caller_params;
1587 vivien 1.1.2.1 // }
1588 vivien 1.1.2.1
1589 vivien 1.1.2.1 // aux method for get_initial_mapping
1590 vivien 1.1.2.1 private static void process_STATICs(final Set set, final Relation mu) {
1591 cananian 1.7 for(Object nodeO : set) {
1592 cananian 1.7 PANode node = (PANode) nodeO;
1593 vivien 1.1.2.1 if(node.type == PANode.STATIC)
1594 vivien 1.1.2.1 mu.add(node, node);
1595 vivien 1.1.2.1 }
1596 vivien 1.1.2.1 }
1597 vivien 1.1.2.1
1598 vivien 1.1.2.1
1599 vivien 1.1.2.1
1600 vivien 1.1.2.1 /** Matches outside edges from the graph of (used by ) the callee
1601 vivien 1.1.2.1 against inside and outside edges from the graph of (created
1602 vivien 1.1.2.1 by) the caller. (repeated application of constraint 2). The
1603 vivien 1.1.2.1 goal of this method is to resolve the load nodes from the
1604 vivien 1.1.2.1 callee, i.e. to detect the nodes from the caller that each
1605 vivien 1.1.2.1 load node might represent. */
1606 vivien 1.1.2.1 private static void match_edges(Relation mu,
1607 vivien 1.1.2.1 ODParIntGraph pig_caller,
1608 vivien 1.1.2.1 ODParIntGraph pig_callee){
1609 vivien 1.1.2.1
1610 vivien 1.1.2.1 PAWorkList W = new PAWorkList();
1611 vivien 1.1.2.1 // here is the new stuff; only nodes with new stuff are
1612 vivien 1.1.2.1 // put in the worklist W.
1613 vivien 1.1.2.1 Relation new_info = (Relation) mu.clone();
1614 vivien 1.1.2.1
1615 vivien 1.1.2.1 W.addAll(mu.keys());
1616 vivien 1.1.2.1 while(!W.isEmpty()){
1617 vivien 1.1.2.1 PANode node1 = (PANode) W.remove();
1618 vivien 1.1.2.1
1619 vivien 1.1.2.1 // nodes3 stands for all the new instances of n3
1620 vivien 1.1.2.1 // from the inference rule
1621 vivien 1.1.2.1 HashSet nodes3 = new HashSet(new_info.getValues(node1));
1622 vivien 1.1.2.1 new_info.removeKey(node1);
1623 vivien 1.1.2.1
1624 cananian 1.7 for (Object fO : pig_callee.G.O.allFlagsForNode(node1)) {
1625 cananian 1.7 String f = (String) fO;
1626 vivien 1.1.2.1
1627 vivien 1.1.2.1 // nodes2 stands for all the nodes that could play
1628 vivien 1.1.2.1 // the role of n2 from the inference rule
1629 vivien 1.1.2.1 Set nodes2 = pig_callee.G.O.pointedNodes(node1,f);
1630 vivien 1.1.2.1 if(nodes2.isEmpty()) continue;
1631 vivien 1.1.2.1
1632 vivien 1.1.2.1 // nodes4 stands for all the nodes that could play
1633 vivien 1.1.2.1 // the role of n4 from the inference rule
1634 vivien 1.1.2.1 Set nodes4 = pig_caller.G.I.pointedNodes(nodes3,f);
1635 vivien 1.1.2.1 nodes4.addAll(pig_caller.G.O.pointedNodes(nodes3,f));
1636 vivien 1.1.2.1
1637 vivien 1.1.2.1 if(nodes4.isEmpty()) continue;
1638 vivien 1.1.2.1
1639 vivien 1.1.2.1 // set up the relation from any node from nodes2
1640 vivien 1.1.2.1 // to any node from nodes4
1641 cananian 1.7 for(Object node2O : nodes2) {
1642 cananian 1.7 PANode node2 = (PANode) node2O;
1643 vivien 1.1.2.1 boolean changed = false;
1644 cananian 1.7 for(Object node4O : nodes4) {
1645 cananian 1.7 PANode node4 = (PANode) node4O;
1646 vivien 1.1.2.1 if(mu.add(node2,node4)){
1647 vivien 1.1.2.1 changed = true;
1648 vivien 1.1.2.1 new_info.add(node2,node4);
1649 vivien 1.1.2.1 }
1650 vivien 1.1.2.1 }
1651 vivien 1.1.2.1 // nodes with new info are put in the worklist
1652 vivien 1.1.2.1 if(changed) W.add(node2);
1653 vivien 1.1.2.1 }
1654 vivien 1.1.2.1 }
1655 vivien 1.1.2.1 }
1656 vivien 1.1.2.1 }
1657 vivien 1.1.2.1
1658 vivien 1.1.2.1 // private static void match_edges(Relation mu,
1659 vivien 1.1.2.1 // ODParIntGraph pig_caller,
1660 vivien 1.1.2.1 // ODParIntGraph pig_callee,
1661 vivien 1.1.2.1 // MethodHole hole){
1662 vivien 1.1.2.1
1663 vivien 1.1.2.1 // PAWorkList W = new PAWorkList();
1664 vivien 1.1.2.1 // // here is the new stuff; only nodes with new stuff are
1665 vivien 1.1.2.1 // // put in the worklist W.
1666 vivien 1.1.2.1 // Relation new_info = (Relation) mu.clone();
1667 vivien 1.1.2.1
1668 vivien 1.1.2.1 // W.addAll(mu.keys());
1669 vivien 1.1.2.1 // while(!W.isEmpty()){
1670 vivien 1.1.2.1 // PANode node1 = (PANode) W.remove();
1671 vivien 1.1.2.1
1672 vivien 1.1.2.1 // // nodes3 stands for all the new instances of n3
1673 vivien 1.1.2.1 // // from the inference rule
1674 vivien 1.1.2.1 // HashSet nodes3 = new HashSet(new_info.getValues(node1));
1675 vivien 1.1.2.1 // new_info.removeKey(node1);
1676 vivien 1.1.2.1
1677 vivien 1.1.2.1 // Iterator itf = pig_callee.G.O.allFlagsForNode(node1).iterator();
1678 vivien 1.1.2.1 // while(itf.hasNext()) {
1679 vivien 1.1.2.1 // String f = (String) itf.next();
1680 vivien 1.1.2.1
1681 vivien 1.1.2.1 // // nodes2 stands for all the nodes that could play
1682 vivien 1.1.2.1 // // the role of n2 from the inference rule
1683 vivien 1.1.2.1 // Set nodes2 = pig_callee.G.O.pointedNodes(node1,f);
1684 vivien 1.1.2.1 // if(nodes2.isEmpty()) continue;
1685 vivien 1.1.2.1
1686 vivien 1.1.2.1 // // nodes4 stands for all the nodes that could play
1687 vivien 1.1.2.1 // // the role of n4 from the inference rule
1688 vivien 1.1.2.1 // for(Iterator n3_it = nodes3.iterator(); n3_it.hasNext(); ) {
1689 vivien 1.1.2.1 // PANode node3 = (PANode) n3_it.next();
1690 vivien 1.1.2.1 // Set nodes4 = pig_caller.G.I.pointedNodes(node3,f);
1691 vivien 1.1.2.1 // if ((nodes4==null)||(nodes4.isEmpty())) continue;
1692 vivien 1.1.2.1
1693 vivien 1.1.2.1 // Map i_from_node3 = (Map) pig_caller.in_edge_always.get(node3);
1694 vivien 1.1.2.1 // if (i_from_node3==null) {
1695 vivien 1.1.2.1 // System.err.println("Error. Map should not be null...");
1696 vivien 1.1.2.1 // System.out.println("Error. Map should not be null...");
1697 vivien 1.1.2.1 // System.out.println("Map (pig_caller.in_edge_always) : ");
1698 vivien 1.1.2.1 // ODPointerAnalysis.print_edge_mh_map(pig_caller.in_edge_always);
1699 vivien 1.1.2.1 // System.out.println(" n1 " + node1 + " -> " + f +
1700 vivien 1.1.2.1 // " -> " + nodes2);
1701 vivien 1.1.2.1 // System.out.println(" n1 " + node1 + " |-> nodes3 "
1702 vivien 1.1.2.1 // + nodes3);
1703 vivien 1.1.2.1 // System.out.println(" n3 " + node3 + " -> " + f +
1704 vivien 1.1.2.1 // " -> " + nodes4);
1705 vivien 1.1.2.1
1706 vivien 1.1.2.1 // continue;
1707 vivien 1.1.2.1 // }
1708 vivien 1.1.2.1
1709 vivien 1.1.2.1 // Relation node3_f = (Relation) i_from_node3.get(f);
1710 vivien 1.1.2.1 // if (node3_f==null){
1711 vivien 1.1.2.1 // System.err.println("Error. Relation should not be null...");
1712 vivien 1.1.2.1 // continue;
1713 vivien 1.1.2.1 // }
1714 vivien 1.1.2.1
1715 vivien 1.1.2.1 // for(Iterator it4 = nodes4.iterator(); it4.hasNext(); ) {
1716 vivien 1.1.2.1 // PANode node4 = (PANode)it4.next();
1717 vivien 1.1.2.1 // Set node3_f_node4 = (Set) node3_f.getValues(node4);
1718 vivien 1.1.2.1
1719 vivien 1.1.2.1 // // The edge may preexist the call site to be
1720 vivien 1.1.2.1 // // considered
1721 vivien 1.1.2.1 // if (!node3_f_node4.contains(hole)){
1722 vivien 1.1.2.1 // // set up the relation from any node from
1723 vivien 1.1.2.1 // // nodes2 to any node from nodes4
1724 vivien 1.1.2.1
1725 vivien 1.1.2.1 // for(Iterator it2 = nodes2.iterator(); it2.hasNext(); ) {
1726 vivien 1.1.2.1 // PANode node2 = (PANode)it2.next();
1727 vivien 1.1.2.1 // if(mu.add(node2,node4)){
1728 vivien 1.1.2.1 // new_info.add(node2,node4);
1729 vivien 1.1.2.1 // // nodes with new info are put in the worklist
1730 vivien 1.1.2.1 // W.add(node2);
1731 vivien 1.1.2.1 // }
1732 vivien 1.1.2.1 // }
1733 vivien 1.1.2.1 // }
1734 vivien 1.1.2.1 // }
1735 vivien 1.1.2.1 // }
1736 vivien 1.1.2.1
1737 vivien 1.1.2.1
1738 vivien 1.1.2.1 // // nodes6 stands for all the nodes that could play
1739 vivien 1.1.2.1 // // the role of n6 from the inference rule
1740 vivien 1.1.2.1 // for(Iterator n5_it = nodes3.iterator(); n5_it.hasNext(); ) {
1741 vivien 1.1.2.1 // PANode node5 = (PANode) n5_it.next();
1742 vivien 1.1.2.1 // Set nodes6 = pig_caller.G.O.pointedNodes(node5,f);
1743 vivien 1.1.2.1 // // if (nodes6==null) continue;
1744 vivien 1.1.2.1 // if ((nodes6==null)||(nodes6.isEmpty())) continue;
1745 vivien 1.1.2.1
1746 vivien 1.1.2.1 // Map i_from_node5 = (Map) pig_caller.out_edge_always.get(node5);
1747 vivien 1.1.2.1 // if (i_from_node5==null) {
1748 vivien 1.1.2.1 // System.err.println("Error. Map should not be null...");
1749 vivien 1.1.2.1 // System.out.println("Error. Map should not be null...");
1750 vivien 1.1.2.1 // System.out.println("Map : ");
1751 vivien 1.1.2.1 // ODPointerAnalysis.print_edge_mh_map(pig_caller.out_edge_always);
1752 vivien 1.1.2.1 // continue;
1753 vivien 1.1.2.1 // }
1754 vivien 1.1.2.1
1755 vivien 1.1.2.1 // Relation node5_f = (Relation) i_from_node5.get(f);
1756 vivien 1.1.2.1 // if (node5_f==null){
1757 vivien 1.1.2.1 // System.err.println("Error. Relation should not be null...");
1758 vivien 1.1.2.1 // continue;
1759 vivien 1.1.2.1 // }
1760 vivien 1.1.2.1
1761 vivien 1.1.2.1 // for(Iterator it6 = nodes6.iterator(); it6.hasNext(); ) {
1762 vivien 1.1.2.1 // PANode node6 = (PANode)it6.next();
1763 vivien 1.1.2.1 // Set node5_f_node6 = (Set) node5_f.getValues(node6);
1764 vivien 1.1.2.1
1765 vivien 1.1.2.1 // // The edge may preexist the call site to be
1766 vivien 1.1.2.1 // // considered
1767 vivien 1.1.2.1 // if (!node5_f_node6.contains(hole)){
1768 vivien 1.1.2.1 // // set up the relation from any node from
1769 vivien 1.1.2.1 // // nodes2 to any node from nodes6
1770 vivien 1.1.2.1
1771 vivien 1.1.2.1 // for(Iterator it2 = nodes2.iterator(); it2.hasNext(); ) {
1772 vivien 1.1.2.1 // PANode node2 = (PANode)it2.next();
1773 vivien 1.1.2.1 // if(mu.add(node2,node6)){
1774 vivien 1.1.2.1 // new_info.add(node2,node6);
1775 vivien 1.1.2.1 // // nodes with new info are put in the worklist
1776 vivien 1.1.2.1 // W.add(node2);
1777 vivien 1.1.2.1 // }
1778 vivien 1.1.2.1 // }
1779 vivien 1.1.2.1 // }
1780 vivien 1.1.2.1 // }
1781 vivien 1.1.2.1 // }
1782 vivien 1.1.2.1 // }
1783 vivien 1.1.2.1 // }
1784 vivien 1.1.2.1 // }
1785 vivien 1.1.2.1
1786 vivien 1.1.2.1 private static void match_edges(Relation mu,
1787 vivien 1.1.2.1 ODParIntGraph pig_caller,
1788 vivien 1.1.2.1 ODParIntGraph pig_callee,
1789 vivien 1.1.2.1 MethodHole hole)
1790 vivien 1.1.2.1 {
1791 vivien 1.1.2.1 PAWorkList W = new PAWorkList();
1792 vivien 1.1.2.1 // here is the new stuff; only nodes with new stuff are
1793 vivien 1.1.2.1 // put in the worklist W.
1794 vivien 1.1.2.1 Relation new_info = (Relation) mu.clone();
1795 vivien 1.1.2.1
1796 vivien 1.1.2.1 W.addAll(mu.keys());
1797 vivien 1.1.2.1 while(!W.isEmpty()){
1798 vivien 1.1.2.1 PANode node1 = (PANode) W.remove();
1799 vivien 1.1.2.1
1800 vivien 1.1.2.1 // nodes3 stands for all the new instances of n3
1801 vivien 1.1.2.1 // from the inference rule
1802 vivien 1.1.2.1 HashSet nodes3 = new HashSet(new_info.getValues(node1));
1803 vivien 1.1.2.1 new_info.removeKey(node1);
1804 vivien 1.1.2.1
1805 cananian 1.7 for (Object fO : pig_callee.G.O.allFlagsForNode(node1)) {
1806 cananian 1.7 String f = (String) fO;
1807 vivien 1.1.2.1
1808 vivien 1.1.2.1 // nodes2 stands for all the nodes that could play
1809 vivien 1.1.2.1 // the role of n2 from the inference rule
1810 vivien 1.1.2.1 Set nodes2 = pig_callee.G.O.pointedNodes(node1,f);
1811 vivien 1.1.2.1 if(nodes2.isEmpty()) continue;
1812 vivien 1.1.2.1
1813 vivien 1.1.2.1 // nodes4 stands for all the nodes that could play
1814 vivien 1.1.2.1 // the role of n4 from the inference rule
1815 cananian 1.7 for(Object node3O : nodes3) {
1816 cananian 1.7 PANode node3 = (PANode) node3O;
1817 vivien 1.1.2.1 Set nodes4 = pig_caller.G.I.pointedNodes(node3,f);
1818 vivien 1.1.2.1 if ((nodes4==null)||(nodes4.isEmpty())) continue;
1819 vivien 1.1.2.1
1820 vivien 1.1.2.1 Map i_from_node3 = (Map) pig_caller.odi.inAlways.edges.get(node3);
1821 vivien 1.1.2.1 if (i_from_node3==null) {
1822 vivien 1.1.2.1 System.err.println("Error. Map should not be null...");
1823 vivien 1.1.2.1 System.out.println("Error. Map should not be null...");
1824 vivien 1.1.2.1 System.out.println("Map (pig_caller.in_edge_always) : " +
1825 vivien 1.1.2.1 pig_caller.odi.inAlways);
1826 vivien 1.1.2.1 System.out.println(" n1 " + node1 + " -> " + f +
1827 vivien 1.1.2.1 " -> " + nodes2);
1828 vivien 1.1.2.1 System.out.println(" n1 " + node1 + " |-> nodes3 "
1829 vivien 1.1.2.1 + nodes3);
1830 vivien 1.1.2.1 System.out.println(" n3 " + node3 + " -> " + f +
1831 vivien 1.1.2.1 " -> " + nodes4);
1832 vivien 1.1.2.1
1833 vivien 1.1.2.1 continue;
1834 vivien 1.1.2.1 }
1835 vivien 1.1.2.1
1836 vivien 1.1.2.1 Relation node3_f = (Relation) i_from_node3.get(f);
1837 vivien 1.1.2.1 if (node3_f==null){
1838 vivien 1.1.2.1 System.err.println("Error. Relation should not be null...");
1839 vivien 1.1.2.1 continue;
1840 vivien 1.1.2.1 }
1841 vivien 1.1.2.1
1842 cananian 1.7 for(Object node4O : nodes4) {
1843 cananian 1.7 PANode node4 = (PANode) node4O;
1844 vivien 1.1.2.1 Set node3_f_node4 = (Set) node3_f.getValues(node4);
1845 vivien 1.1.2.1
1846 vivien 1.1.2.1 // The edge may preexist the call site to be
1847 vivien 1.1.2.1 // considered
1848 vivien 1.1.2.1 if (!node3_f_node4.contains(hole)){
1849 vivien 1.1.2.1 // set up the relation from any node from
1850 vivien 1.1.2.1 // nodes2 to any node from nodes4
1851 vivien 1.1.2.1
1852 cananian 1.7 for(Object node2O : nodes2) {
1853 cananian 1.7 PANode node2 = (PANode) node2O;
1854 vivien 1.1.2.1 if(mu.add(node2,node4)){
1855 vivien 1.1.2.1 new_info.add(node2,node4);
1856 vivien 1.1.2.1 // nodes with new info are put in the worklist
1857 vivien 1.1.2.1 W.add(node2);
1858 vivien 1.1.2.1 }
1859 vivien 1.1.2.1 }
1860 vivien 1.1.2.1 }
1861 vivien 1.1.2.1 }
1862 vivien 1.1.2.1 }
1863 vivien 1.1.2.1
1864 vivien 1.1.2.1
1865 vivien 1.1.2.1 // nodes6 stands for all the nodes that could play
1866 vivien 1.1.2.1 // the role of n6 from the inference rule
1867 cananian 1.7 for(Object node5O : nodes3) {
1868 cananian 1.7 PANode node5 = (PANode) node5O;
1869 vivien 1.1.2.1 Set nodes6 = pig_caller.G.O.pointedNodes(node5,f);
1870 vivien 1.1.2.1 // if (nodes6==null) continue;
1871 vivien 1.1.2.1 if ((nodes6==null)||(nodes6.isEmpty())) continue;
1872 vivien 1.1.2.1
1873 vivien 1.1.2.1 Map i_from_node5 = (Map) pig_caller.odi.outAlways.edges.get(node5);
1874 vivien 1.1.2.1 if (i_from_node5==null) {
1875 vivien 1.1.2.1 System.err.println("Error. Map should not be null...");
1876 vivien 1.1.2.1 System.out.println("Error. Map should not be null...");
1877 vivien 1.1.2.1 System.out.println("Map : "+
1878 vivien 1.1.2.1 pig_caller.odi.outAlways);
1879 vivien 1.1.2.1 continue;
1880 vivien 1.1.2.1 }
1881 vivien 1.1.2.1
1882 vivien 1.1.2.1 Relation node5_f = (Relation) i_from_node5.get(f);
1883 vivien 1.1.2.1 if (node5_f==null){
1884 vivien 1.1.2.1 System.err.println("Error. Relation should not be null...");
1885 vivien 1.1.2.1 continue;
1886 vivien 1.1.2.1 }
1887 vivien 1.1.2.1
1888 cananian 1.7 for(Object node6O : nodes6) {
1889 cananian 1.7 PANode node6 = (PANode) node6O;
1890 vivien 1.1.2.1 Set node5_f_node6 = (Set) node5_f.getValues(node6);
1891 vivien 1.1.2.1
1892 vivien 1.1.2.1 // The edge may preexist the call site to be
1893 vivien 1.1.2.1 // considered
1894 vivien 1.1.2.1 if (!node5_f_node6.contains(hole)){
1895 vivien 1.1.2.1 // set up the relation from any node from
1896 vivien 1.1.2.1 // nodes2 to any node from nodes6
1897 vivien 1.1.2.1
1898 cananian 1.7 for(Object node2O : nodes2) {
1899 cananian 1.7 PANode node2 = (PANode) node2O;
1900 vivien 1.1.2.1 if(mu.add(node2,node6)){
1901 vivien 1.1.2.1 new_info.add(node2,node6);
1902 vivien 1.1.2.1 // nodes with new info are put in the worklist
1903 vivien 1.1.2.1 W.add(node2);
1904 vivien 1.1.2.1 }
1905 vivien 1.1.2.1 }
1906 vivien 1.1.2.1 }
1907 vivien 1.1.2.1 }
1908 vivien 1.1.2.1 }
1909 vivien 1.1.2.1 }
1910 vivien 1.1.2.1 }
1911 vivien 1.1.2.1 }
1912 vivien 1.1.2.1
1913 vivien 1.1.2.1
1914 vivien 1.1.2.1
1915 vivien 1.1.2.1 // This function is only used for the second phase of the matching
1916 vivien 1.1.2.1 // caller/callee in case of ODA, when the mapup is made after an
1917 vivien 1.1.2.1 // initial skip.
1918 vivien 1.1.2.1
1919 vivien 1.1.2.1 // private static void match_edges(Relation mu,
1920 vivien 1.1.2.1 // Relation first_mapping,
1921 vivien 1.1.2.1 // PAEdgeSet O,
1922 vivien 1.1.2.1 // ODParIntGraph pig_callee,
1923 vivien 1.1.2.1 // Map edges_maybe,
1924 vivien 1.1.2.1 // MethodHole hole){
1925 vivien 1.1.2.1
1926 vivien 1.1.2.1 // PAWorkList W = new PAWorkList();
1927 vivien 1.1.2.1 // // here is the new stuff; only nodes with new stuff are
1928 vivien 1.1.2.1 // // put in the worklist W.
1929 vivien 1.1.2.1 // Relation new_info = (Relation) mu.clone();
1930 vivien 1.1.2.1
1931 vivien 1.1.2.1 // // We store all the nodes that we know must be mapped (formal
1932 vivien 1.1.2.1 // // return and exception nodes)
1933 vivien 1.1.2.1 // W.addAll(mu.keys());
1934 vivien 1.1.2.1 // Set formal_nodes = mu.keys();
1935 vivien 1.1.2.1
1936 vivien 1.1.2.1 // // In order to know which nodes in the caller are mapped to by
1937 vivien 1.1.2.1 // // nodes in the callee, we ``reverse'' the first mapping.
1938 vivien 1.1.2.1 // Relation ancestor = new LightRelation();
1939 vivien 1.1.2.1 // for(Iterator key_it=first_mapping.keys().iterator(); key_it.hasNext(); ){
1940 vivien 1.1.2.1 // PANode source = (PANode) key_it.next();
1941 vivien 1.1.2.1 // for(Iterator sinks_it=first_mapping.getValues(source).iterator();
1942 vivien 1.1.2.1 // sinks_it.hasNext(); )
1943 vivien 1.1.2.1 // ancestor.add(sinks_it.next(),source);
1944 vivien 1.1.2.1 // }
1945 vivien 1.1.2.1
1946 vivien 1.1.2.1 // // We look for outside edges in the caller, which may happen
1947 vivien 1.1.2.1 // // *after* the skipped call site, and whose tail is mapped
1948 vivien 1.1.2.1 // // unto by one node in the callee.
1949 vivien 1.1.2.1 // for(Iterator n_it=edges_maybe.keySet().iterator(); n_it.hasNext(); ){
1950 vivien 1.1.2.1 // boolean not_included = true;
1951 vivien 1.1.2.1
1952 vivien 1.1.2.1 // PANode tail = (PANode) n_it.next();
1953 vivien 1.1.2.1 // // If one of the callee nodes is mapped to this node we
1954 vivien 1.1.2.1 // // process it, else we are not going any further.
1955 vivien 1.1.2.1 // // if (ancestor.getValues(tail)==null) continue;
1956 vivien 1.1.2.1 // if (!(ancestor.containsKey(tail))) continue;
1957 vivien 1.1.2.1
1958 vivien 1.1.2.1 // Map from_tail = (Map) edges_maybe.get(tail);
1959 vivien 1.1.2.1 // for(Iterator k_it = from_tail.keySet().iterator();
1960 vivien 1.1.2.1 // k_it.hasNext() && not_included; )
1961 vivien 1.1.2.1 // {
1962 vivien 1.1.2.1 // String f = (String) k_it.next();
1963 vivien 1.1.2.1 // Relation from_f = (Relation) from_tail.get(f);
1964 vivien 1.1.2.1 // for(Iterator t_it = from_f.keys().iterator();
1965 vivien 1.1.2.1 // t_it.hasNext() && not_included; )
1966 vivien 1.1.2.1 // {
1967 vivien 1.1.2.1 // PANode head = (PANode) t_it.next();
1968 vivien 1.1.2.1 // if (from_f.getValues(head).contains(hole)){
1969 vivien 1.1.2.1 // W.add(tail);
1970 vivien 1.1.2.1 // not_included=false;
1971 vivien 1.1.2.1 // }
1972 vivien 1.1.2.1 // }
1973 vivien 1.1.2.1 // }
1974 vivien 1.1.2.1 // }
1975 vivien 1.1.2.1
1976 vivien 1.1.2.1 // while(!W.isEmpty()){
1977 vivien 1.1.2.1 // PANode node1 = (PANode) W.remove();
1978 vivien 1.1.2.1
1979 vivien 1.1.2.1 // // nodes3 stands for all the new instances of n3
1980 vivien 1.1.2.1 // // from the inference rule
1981 vivien 1.1.2.1 // HashSet nodes3 = new HashSet(new_info.getValues(node1));
1982 vivien 1.1.2.1 // new_info.removeKey(node1);
1983 vivien 1.1.2.1
1984 vivien 1.1.2.1 // Map from_node1 = (Map) edges_maybe.get(node1);
1985 vivien 1.1.2.1 // if (from_node1==null){
1986 vivien 1.1.2.1 // // if (!(formal_nodes.contains(node1))){
1987 vivien 1.1.2.1 // // System.err.println("Strange... (really possible !)");
1988 vivien 1.1.2.1 // // System.out.println("Strange... (really possible !)");
1989 vivien 1.1.2.1 // // System.out.println("n1 " + node1);
1990 vivien 1.1.2.1 // // System.out.println("edges_maybe ");
1991 vivien 1.1.2.1 // // ODPointerAnalysis.print_edge_mh_map(edges_maybe);
1992 vivien 1.1.2.1 // // }
1993 vivien 1.1.2.1 // continue;
1994 vivien 1.1.2.1 // }
1995 vivien 1.1.2.1
1996 vivien 1.1.2.1 // // Iterator itf = pig_caller.G.O.allFlagsForNode(node1).iterator();
1997 vivien 1.1.2.1 // Iterator itf = O.allFlagsForNode(node1).iterator();
1998 vivien 1.1.2.1 // while(itf.hasNext()) {
1999 vivien 1.1.2.1 // String f = (String) itf.next();
2000 vivien 1.1.2.1 // Relation node1_f = (Relation) from_node1.get(f);
2001 vivien 1.1.2.1 // if (node1_f==null){
2002 vivien 1.1.2.1 // // In fact, this happens if the outside edge was
2003 vivien 1.1.2.1 // // created during the first part of the
2004 vivien 1.1.2.1 // // mapping. In that case, this edge is not a
2005 vivien 1.1.2.1 // // candidate.
2006 vivien 1.1.2.1 // System.err.println("Bug... ");
2007 vivien 1.1.2.1 // System.out.println("Bug... ");
2008 vivien 1.1.2.1 // System.out.println("n1 " + node1 + " -> " + f);
2009 vivien 1.1.2.1 // continue;
2010 vivien 1.1.2.1 // }
2011 vivien 1.1.2.1 // // nodes2 stands for all the nodes that could play
2012 vivien 1.1.2.1 // // the role of n2 from the inference rule
2013 vivien 1.1.2.1 // // Set nodes2 = pig_caller.G.O.pointedNodes(node1,f);
2014 vivien 1.1.2.1 // Set nodes2 = O.pointedNodes(node1,f);
2015 vivien 1.1.2.1 // if(nodes2.isEmpty()) continue;
2016 vivien 1.1.2.1
2017 vivien 1.1.2.1
2018 vivien 1.1.2.1 // // nodes4 stands for all the nodes that could play
2019 vivien 1.1.2.1 // // the role of n4 from the inference rule
2020 vivien 1.1.2.1 // Set nodes4 = pig_callee.G.I.pointedNodes(nodes3,f);
2021 vivien 1.1.2.1 // nodes4.addAll(pig_callee.G.O.pointedNodes(nodes3,f));
2022 vivien 1.1.2.1
2023 vivien 1.1.2.1 // if(nodes4.isEmpty()) continue;
2024 vivien 1.1.2.1
2025 vivien 1.1.2.1 // // set up the relation from any node from nodes2
2026 vivien 1.1.2.1 // // to any node from nodes4
2027 vivien 1.1.2.1 // for(Iterator it2 = nodes2.iterator(); it2.hasNext(); ) {
2028 vivien 1.1.2.1 // PANode node2 = (PANode)it2.next();
2029 vivien 1.1.2.1
2030 vivien 1.1.2.1 // // The edges must possibly have been created after
2031 vivien 1.1.2.1 // // the call site to be considered
2032 vivien 1.1.2.1 // if (! ((node1_f.getValues(node2)).contains(hole)))
2033 vivien 1.1.2.1 // continue;
2034 vivien 1.1.2.1
2035 vivien 1.1.2.1 // boolean changed = false;
2036 vivien 1.1.2.1
2037 vivien 1.1.2.1 // for(Iterator it4 = nodes4.iterator(); it4.hasNext(); ) {
2038 vivien 1.1.2.1 // PANode node4 = (PANode)it4.next();
2039 vivien 1.1.2.1 // if(mu.add(node2,node4)){
2040 vivien 1.1.2.1 // changed = true;
2041 vivien 1.1.2.1 // new_info.add(node2,node4);
2042 vivien 1.1.2.1 // }
2043 vivien 1.1.2.1 // }
2044 vivien 1.1.2.1 // //tbu
2045 vivien 1.1.2.1 // // if(mu.add(node2,node2)){
2046 vivien 1.1.2.1 // // changed = true;
2047 vivien 1.1.2.1 // // new_info.add(node2,node2);
2048 vivien 1.1.2.1 // // }
2049 vivien 1.1.2.1
2050 vivien 1.1.2.1 // // nodes with new info are put in the worklist
2051 vivien 1.1.2.1 // if(changed) W.add(node2);
2052 vivien 1.1.2.1 // }
2053 vivien 1.1.2.1 // }
2054 vivien 1.1.2.1 // }
2055 vivien 1.1.2.1 // }
2056 vivien 1.1.2.1
2057 vivien 1.1.2.1
2058 vivien 1.1.2.1 private static void match_edges(Relation mu,
2059 vivien 1.1.2.1 Relation first_mapping,
2060 vivien 1.1.2.1 PAEdgeSet O,
2061 vivien 1.1.2.1 ODParIntGraph pig_callee,
2062 vivien 1.1.2.1 ODParIntGraph pig_caller,
2063 vivien 1.1.2.1 MethodHole hole){
2064 vivien 1.1.2.1
2065 vivien 1.1.2.1 boolean precise = pig_caller.odi.precise;
2066 vivien 1.1.2.1
2067 vivien 1.1.2.1 final PAWorkList W = new PAWorkList();
2068 vivien 1.1.2.1 // here is the new stuff; only nodes with new stuff are
2069 vivien 1.1.2.1 // put in the worklist W.
2070 vivien 1.1.2.1 Relation new_info = (Relation) mu.clone();
2071 vivien 1.1.2.1
2072 vivien 1.1.2.1 // We store all the nodes that we know must be mapped (formal
2073 vivien 1.1.2.1 // return and exception nodes)
2074 vivien 1.1.2.1 W.addAll(mu.keys());
2075 vivien 1.1.2.1 Set formal_nodes = mu.keys();
2076 vivien 1.1.2.1
2077 vivien 1.1.2.1 // In order to know which nodes in the caller are mapped to by
2078 vivien 1.1.2.1 // nodes in the callee, we ``reverse'' the first mapping.
2079 vivien 1.1.2.1 final Relation ancestor = new LightRelation();
2080 cananian 1.7 for(Object sourceO : first_mapping.keys()){
2081 cananian 1.7 PANode source = (PANode) sourceO;
2082 vivien 1.1.2.1 for(Iterator sinks_it=first_mapping.getValues(source).iterator();
2083 vivien 1.1.2.1 sinks_it.hasNext(); )
2084 vivien 1.1.2.1 ancestor.add(sinks_it.next(),source);
2085 vivien 1.1.2.1 }
2086 vivien 1.1.2.1
2087 vivien 1.1.2.1 // We look for outside edges in the caller, which may happen
2088 vivien 1.1.2.1 // *after* the skipped call site, and whose tail is mapped
2089 vivien 1.1.2.1 // unto by one node in the callee.
2090 vivien 1.1.2.1 if(precise){
2091 vivien 1.1.2.1 for(Iterator n_it=pig_caller.odi.outMaybe.edges.keySet().iterator();
2092 vivien 1.1.2.1 n_it.hasNext(); ){
2093 vivien 1.1.2.1 boolean not_included = true;
2094 vivien 1.1.2.1
2095 vivien 1.1.2.1 PANode tail = (PANode) n_it.next();
2096 vivien 1.1.2.1 // If one of the callee nodes is mapped to this node
2097 vivien 1.1.2.1 // we process it, else we are not going any further.
2098 vivien 1.1.2.1 if (!(ancestor.containsKey(tail))) continue;
2099 vivien 1.1.2.1
2100 vivien 1.1.2.1 Map from_tail = (Map) pig_caller.odi.outMaybe.edges.get(tail);
2101 vivien 1.1.2.1 for(Iterator k_it = from_tail.keySet().iterator();
2102 vivien 1.1.2.1 k_it.hasNext() && not_included; )
2103 vivien 1.1.2.1 {
2104 vivien 1.1.2.1 String f = (String) k_it.next();
2105 vivien 1.1.2.1 Relation from_f = (Relation) from_tail.get(f);
2106 vivien 1.1.2.1 for(Iterator t_it = from_f.keys().iterator();
2107 vivien 1.1.2.1 t_it.hasNext() && not_included; )
2108 vivien 1.1.2.1 {
2109 vivien 1.1.2.1 PANode head = (PANode) t_it.next();
2110 vivien 1.1.2.1 if (from_f.getValues(head).contains(hole)){
2111 vivien 1.1.2.1 W.add(tail);
2112 vivien 1.1.2.1 not_included=false;
2113 vivien 1.1.2.1 }
2114 vivien 1.1.2.1 }
2115 vivien 1.1.2.1 }
2116 vivien 1.1.2.1 }
2117 vivien 1.1.2.1 }
2118 vivien 1.1.2.1 else{
2119 vivien 1.1.2.1 PAEdgeVisitor visitor_O = new PAEdgeVisitor(){
2120 vivien 1.1.2.1 public void visit(Temp var, PANode node){
2121 cananian 1.3.2.1 assert false : (" var2node edge in O: " +
2122 vivien 1.1.2.1 var + "->" + node);
2123 vivien 1.1.2.1 }
2124 vivien 1.1.2.1 public void visit(PANode node1,String f, PANode node2){
2125 vivien 1.1.2.1 if(ancestor.containsKey(node1))
2126 vivien 1.1.2.1 W.add(node1);
2127 vivien 1.1.2.1 }
2128 vivien 1.1.2.1 };
2129 vivien 1.1.2.1
2130 vivien 1.1.2.1 pig_caller.G.O.forAllEdges(visitor_O);
2131 vivien 1.1.2.1 }
2132 vivien 1.1.2.1
2133 vivien 1.1.2.1
2134 vivien 1.1.2.1 Map from_node1 =null;
2135 vivien 1.1.2.1 Relation node1_f = null;
2136 vivien 1.1.2.1
2137 vivien 1.1.2.1 while(!W.isEmpty()){
2138 vivien 1.1.2.1 PANode node1 = (PANode) W.remove();
2139 vivien 1.1.2.1
2140 vivien 1.1.2.1 // nodes3 stands for all the new instances of n3
2141 vivien 1.1.2.1 // from the inference rule
2142 vivien 1.1.2.1 HashSet nodes3 = new HashSet(new_info.getValues(node1));
2143 vivien 1.1.2.1 new_info.removeKey(node1);
2144 vivien 1.1.2.1
2145 vivien 1.1.2.1 if(precise){
2146 vivien 1.1.2.1 from_node1 = (Map) pig_caller.odi.outMaybe.edges.get(node1);
2147 vivien 1.1.2.1 if (from_node1==null){
2148 vivien 1.1.2.1 continue;
2149 vivien 1.1.2.1 }
2150 vivien 1.1.2.1 }
2151 vivien 1.1.2.1
2152 cananian 1.7 for (Object fO : O.allFlagsForNode(node1)) {
2153 cananian 1.7 String f = (String) fO;
2154 vivien 1.1.2.1
2155 vivien 1.1.2.1 if(precise){
2156 vivien 1.1.2.1 node1_f = (Relation) from_node1.get(f);
2157 vivien 1.1.2.1 if (node1_f==null){
2158 vivien 1.1.2.1 // In fact, this happens if the outside edge was
2159 vivien 1.1.2.1 // created during the first part of the
2160 vivien 1.1.2.1 // mapping. In that case, this edge is not a
2161 vivien 1.1.2.1 // candidate.
2162 vivien 1.1.2.1 System.err.println("Bug... ");
2163 vivien 1.1.2.1 System.out.println("Bug... ");
2164 vivien 1.1.2.1 System.out.println("n1 " + node1 + " -> " + f);
2165 vivien 1.1.2.1 continue;
2166 vivien 1.1.2.1 }
2167 vivien 1.1.2.1 }
2168 vivien 1.1.2.1 // nodes2 stands for all the nodes that could play
2169 vivien 1.1.2.1 // the role of n2 from the inference rule
2170 vivien 1.1.2.1 Set nodes2 = O.pointedNodes(node1,f);
2171 vivien 1.1.2.1 if(nodes2.isEmpty()) continue;
2172 vivien 1.1.2.1
2173 vivien 1.1.2.1
2174 vivien 1.1.2.1 // nodes4 stands for all the nodes that could play
2175 vivien 1.1.2.1 // the role of n4 from the inference rule
2176 vivien 1.1.2.1 Set nodes4 = pig_callee.G.I.pointedNodes(nodes3,f);
2177 vivien 1.1.2.1 nodes4.addAll(pig_callee.G.O.pointedNodes(nodes3,f));
2178 vivien 1.1.2.1
2179 vivien 1.1.2.1 if(nodes4.isEmpty()) continue;
2180 vivien 1.1.2.1
2181 vivien 1.1.2.1 // set up the relation from any node from nodes2
2182 vivien 1.1.2.1 // to any node from nodes4
2183 cananian 1.7 for(Object node2O : nodes2) {
2184 cananian 1.7 PANode node2 = (PANode) node2O;
2185 vivien 1.1.2.1
2186 vivien 1.1.2.1 // The edges must possibly have been created after
2187 vivien 1.1.2.1 // the call site to be considered
2188 vivien 1.1.2.1 if ((precise)&& (! ((node1_f.getValues(node2)).contains(hole))))
2189 vivien 1.1.2.1 continue;
2190 vivien 1.1.2.1
2191 vivien 1.1.2.1 boolean changed = false;
2192 vivien 1.1.2.1
2193 cananian 1.7 for(Object node4O : nodes4) {
2194 cananian 1.7 PANode node4 = (PANode) node4O;
2195 vivien 1.1.2.1 if(mu.add(node2,node4)){
2196 vivien 1.1.2.1 changed = true;
2197 vivien 1.1.2.1 new_info.add(node2,node4);
2198 vivien 1.1.2.1 }
2199 vivien 1.1.2.1 }
2200 vivien 1.1.2.1 //tbu
2201 vivien 1.1.2.1 // if(mu.add(node2,node2)){
2202 vivien 1.1.2.1 // changed = true;
2203 vivien 1.1.2.1 // new_info.add(node2,node2);
2204 vivien 1.1.2.1 // }
2205 vivien 1.1.2.1
2206 vivien 1.1.2.1 // nodes with new info are put in the worklist
2207 vivien 1.1.2.1 if(changed) W.add(node2);
2208 vivien 1.1.2.1 }
2209 vivien 1.1.2.1 }
2210 vivien 1.1.2.1 }
2211 vivien 1.1.2.1 }
2212 vivien 1.1.2.1
2213 vivien 1.1.2.1
2214 vivien 1.1.2.1 private static void match_edges(Relation mu,
2215 vivien 1.1.2.1 PAEdgeSet candidate,
2216 vivien 1.1.2.1 PAEdgeSet reference){
2217 vivien 1.1.2.1
2218 vivien 1.1.2.1 PAWorkList W = new PAWorkList();
2219 vivien 1.1.2.1 // here is the new stuff; only nodes with new stuff are
2220 vivien 1.1.2.1 // put in the worklist W.
2221 vivien 1.1.2.1 Relation new_info = (Relation) mu.clone();
2222 vivien 1.1.2.1
2223 vivien 1.1.2.1 W.addAll(mu.keys());
2224 vivien 1.1.2.1 while(!W.isEmpty()){
2225 vivien 1.1.2.1 PANode node1 = (PANode) W.remove();
2226 vivien 1.1.2.1
2227 vivien 1.1.2.1 // nodes3 stands for all the new instances of n3
2228 vivien 1.1.2.1 // from the inference rule
2229 vivien 1.1.2.1 HashSet nodes3 = new HashSet(new_info.getValues(node1));
2230 vivien 1.1.2.1 new_info.removeKey(node1);
2231 vivien 1.1.2.1
2232 cananian 1.7 for (Object fO : candidate.allFlagsForNode(node1)) {
2233 cananian 1.7 String f = (String) fO;
2234 vivien 1.1.2.1
2235 vivien 1.1.2.1 // nodes2 stands for all the nodes that could play
2236 vivien 1.1.2.1 // the role of n2 from the inference rule
2237 vivien 1.1.2.1 Set nodes2 = candidate.pointedNodes(node1,f);
2238 vivien 1.1.2.1 if(nodes2.isEmpty()) continue;
2239 vivien 1.1.2.1
2240 vivien 1.1.2.1 // nodes4 stands for all the nodes that could play
2241 vivien 1.1.2.1 // the role of n4 from the inference rule
2242 vivien 1.1.2.1 Set nodes4 = reference.pointedNodes(nodes3,f);
2243 vivien 1.1.2.1 if(nodes4.isEmpty()) continue;
2244 vivien 1.1.2.1
2245 vivien 1.1.2.1 // set up the relation from any node from nodes2
2246 vivien 1.1.2.1 // to any node from nodes4
2247 cananian 1.7 for(Object node2O : nodes2) {
2248 cananian 1.7 PANode node2 = (PANode) node2O;
2249 vivien 1.1.2.1 boolean changed = false;
2250 cananian 1.7 for(Object node4O : nodes4) {
2251 cananian 1.7 PANode node4 = (PANode) node4O;
2252 vivien 1.1.2.1 if(mu.add(node2,node4)){
2253 vivien 1.1.2.1 changed = true;
2254 vivien 1.1.2.1 new_info.add(node2,node4);
2255 vivien 1.1.2.1 }
2256 vivien 1.1.2.1 }
2257 vivien 1.1.2.1 // nodes with new info are put in the worklist
2258 vivien 1.1.2.1 if(changed) W.add(node2);
2259 vivien 1.1.2.1 }
2260 vivien 1.1.2.1 }
2261 vivien 1.1.2.1 }
2262 vivien 1.1.2.1 }
2263 vivien 1.1.2.1
2264 vivien 1.1.2.1 // Initially, all the nodes from the callee are put into the caller's
2265 vivien 1.1.2.1 // graph except for the PARAM nodes. Later, after recomputing the
2266 vivien 1.1.2.1 // escape info, the empty load nodes will be removed (together with
2267 vivien 1.1.2.1 // the related information)
2268 vivien 1.1.2.1 private static void compute_the_final_mapping(final Relation mu,
2269 vivien 1.1.2.1 final ODParIntGraph pig_caller,
2270 vivien 1.1.2.1 final ODParIntGraph pig_callee){
2271 vivien 1.1.2.1 pig_callee.forAllNodes(new PANodeVisitor(){
2272 vivien 1.1.2.1 public void visit(PANode node){
2273 vivien 1.1.2.1 if(node.type() != PANode.PARAM)
2274 vivien 1.1.2.1 mu.add(node,node);
2275 vivien 1.1.2.1 }
2276 vivien 1.1.2.1 });
2277 vivien 1.1.2.1 }
2278 vivien 1.1.2.1
2279 vivien 1.1.2.1 private static void compute_the_final_mapping(final Relation mu,
2280 vivien 1.1.2.1 final ODParIntGraph pig_caller) {
2281 vivien 1.1.2.1 pig_caller.forAllNodes(new PANodeVisitor(){
2282 vivien 1.1.2.1 public void visit(PANode node){
2283 vivien 1.1.2.1 mu.add(node,node);
2284 vivien 1.1.2.1 }
2285 vivien 1.1.2.1 });
2286 vivien 1.1.2.1 }
2287 vivien 1.1.2.1
2288 vivien 1.1.2.1
2289 vivien 1.1.2.1 /** Sets the edges for the result or the exception returned by the callee.
2290 vivien 1.1.2.1 * Remember the syntax of a method invocation:
2291 vivien 1.1.2.1 * <code><retval,retexc> = CALL (...)</code>. */
2292 vivien 1.1.2.1 private static void set_edges_res_ex(Temp l, Relation mu,
2293 vivien 1.1.2.1 ODParIntGraph pig_caller, Set nodes){
2294 vivien 1.1.2.1 if(l == null) return;
2295 vivien 1.1.2.1 /// System.out.println("Setting the edges for " + l);
2296 vivien 1.1.2.1 pig_caller.G.I.removeEdges(l);
2297 vivien 1.1.2.1 Set mu_nodes = new HashSet();
2298 vivien 1.1.2.1 Iterator it = nodes.iterator();
2299 vivien 1.1.2.1 while(it.hasNext())
2300 vivien 1.1.2.1 mu_nodes.addAll(mu.getValues((PANode) it.next()));
2301 vivien 1.1.2.1 pig_caller.G.I.addEdges(l,mu_nodes);
2302 vivien 1.1.2.1 }
2303 vivien 1.1.2.1
2304 vivien 1.1.2.1 private static void set_edges_res_ex_soft(Temp l, Relation mu,
2305 vivien 1.1.2.1 ODParIntGraph pig_caller, Set nodes){
2306 vivien 1.1.2.1
2307 vivien 1.1.2.1 // Update of the caller Return and Exception nodes
2308 vivien 1.1.2.1 Set mu_ret_nodes = projection(pig_caller.G.r, mu, new LinearSet());
2309 vivien 1.1.2.1 // System.out.println("pig_caller.G.r");
2310 vivien 1.1.2.1 // print_nodeset(pig_caller.G.r);
2311 vivien 1.1.2.1 // System.out.println("mu_ret_nodes");
2312 vivien 1.1.2.1 // print_nodeset(mu_ret_nodes);
2313 vivien 1.1.2.1 pig_caller.G.r = mu_ret_nodes;
2314 vivien 1.1.2.1
2315 vivien 1.1.2.1 Set mu_exc_nodes = projection(pig_caller.G.excp, mu, new LinearSet());
2316 vivien 1.1.2.1 // System.out.println("pig_caller.G.excp");
2317 vivien 1.1.2.1 // print_nodeset(pig_caller.G.excp);
2318 vivien 1.1.2.1 // System.out.println("mu_exc_nodes");
2319 vivien 1.1.2.1 // print_nodeset(mu_exc_nodes);
2320 vivien 1.1.2.1 pig_caller.G.excp = mu_exc_nodes;
2321 vivien 1.1.2.1
2322 vivien 1.1.2.1 if(l == null) return;
2323 vivien 1.1.2.1 /// System.out.println("Setting the edges for " + l);
2324 vivien 1.1.2.1 Set mu_nodes = new HashSet();
2325 vivien 1.1.2.1 Iterator it = nodes.iterator();
2326 vivien 1.1.2.1 while(it.hasNext())
2327 vivien 1.1.2.1 mu_nodes.addAll(mu.getValues((PANode) it.next()));
2328 vivien 1.1.2.1 pig_caller.G.I.addEdges(l,mu_nodes);
2329 vivien 1.1.2.1 }
2330 vivien 1.1.2.1
2331 vivien 1.1.2.1 private static void set_edges_res_ex(Temp l, Relation mu,
2332 vivien 1.1.2.1 final ODParIntGraph pig_caller, final Set nodes,
2333 vivien 1.1.2.1 final PANode org){
2334 vivien 1.1.2.1 System.out.println("In set_edges_res_ex (" + l + ")");
2335 vivien 1.1.2.1 if(l == null) return;
2336 vivien 1.1.2.1 /// System.out.println("Setting the edges for " + l);
2337 vivien 1.1.2.1 final Set mu_nodes = new HashSet();
2338 vivien 1.1.2.1 Iterator it = nodes.iterator();
2339 vivien 1.1.2.1 while(it.hasNext())
2340 vivien 1.1.2.1 mu_nodes.addAll(mu.getValues((PANode) it.next()));
2341 vivien 1.1.2.1 pig_caller.G.I.addEdges(l,mu_nodes);
2342 vivien 1.1.2.1
2343 vivien 1.1.2.1 System.out.print(" mu_nodes: " + org + " ->");
2344 vivien 1.1.2.1 it = mu_nodes.iterator();
2345 vivien 1.1.2.1 while(it.hasNext())
2346 vivien 1.1.2.1 System.out.print(" " + (PANode) it.next());
2347 vivien 1.1.2.1 System.out.println(" ("+ mu_nodes.size() +").");
2348 vivien 1.1.2.1
2349 vivien 1.1.2.1 System.out.print(" nodes: " + org + " ->");
2350 vivien 1.1.2.1 it = nodes.iterator();
2351 vivien 1.1.2.1 while(it.hasNext())
2352 vivien 1.1.2.1 System.out.print(" " + (PANode) it.next());
2353 vivien 1.1.2.1 System.out.println(" ("+ nodes.size() +").");
2354 vivien 1.1.2.1
2355 vivien 1.1.2.1 /// Memory Leak : copy !
2356 vivien 1.1.2.1 if (org!=null){
2357 vivien 1.1.2.1 PAEdgeSet copy = (PAEdgeSet) pig_caller.G.I.clone();
2358 vivien 1.1.2.1 PAEdgeVisitor myvisitor = new PAEdgeVisitor(){
2359 vivien 1.1.2.1 public void visit(Temp tt, PANode node){
2360 vivien 1.1.2.1 System.out.println(node);
2361 vivien 1.1.2.1 if(node.equals(org))
2362 vivien 1.1.2.1 pig_caller.G.I.addEdges(tt, nodes);
2363 vivien 1.1.2.1 // pig_caller.G.I.addEdges(tt, mu_nodes);
2364 vivien 1.1.2.1 }
2365 vivien 1.1.2.1 public void visit(PANode node1, String f, PANode node2){
2366 vivien 1.1.2.1 System.out.println(node2);
2367 vivien 1.1.2.1 if(node2==org)
2368 vivien 1.1.2.1 pig_caller.G.I.addEdges(node1, f, nodes);
2369 vivien 1.1.2.1 // pig_caller.G.I.addEdges(node1, f, mu_nodes);
2370 vivien 1.1.2.1 }
2371 vivien 1.1.2.1 };
2372 vivien 1.1.2.1 copy.forAllEdges(myvisitor);
2373 vivien 1.1.2.1 }
2374 vivien 1.1.2.1 }
2375 vivien 1.1.2.1
2376 vivien 1.1.2.1
2377 vivien 1.1.2.1 private static void bring_actions(final ActionRepository ar_caller,
2378 vivien 1.1.2.1 final ActionRepository ar_callee,
2379 vivien 1.1.2.1 final Set active_threads_in_caller,
2380 vivien 1.1.2.1 final Relation mu){
2381 vivien 1.1.2.1 // Add this "common-sense" rule to the mapping: the inter-procedural
2382 vivien 1.1.2.1 // analysis stays in the same thread.
2383 vivien 1.1.2.1 mu.add(ActionRepository.THIS_THREAD,ActionRepository.THIS_THREAD);
2384 vivien 1.1.2.1
2385 vivien 1.1.2.1 // Step 1. Put all the actions from the callee as being executed
2386 vivien 1.1.2.1 // in // with all the threads that are active in the caller.
2387 vivien 1.1.2.1 ActionVisitor act_visitor = new ActionVisitor(){
2388 vivien 1.1.2.1 public void visit_ld(PALoad load){
2389 vivien 1.1.2.1 if(!mu.contains(load.n2,load.n2)) return;
2390 vivien 1.1.2.1 ar_caller.add_ld(mu.getValues(load.n1),
2391 vivien 1.1.2.1 load.f,
2392 vivien 1.1.2.1 load.n2,
2393 vivien 1.1.2.1 mu.getValues(load.nt),
2394 vivien 1.1.2.1 active_threads_in_caller);
2395 vivien 1.1.2.1 }
2396 vivien 1.1.2.1 public void visit_sync(PASync sync){
2397 vivien 1.1.2.1 ar_caller.add_sync(sync.project(mu),
2398 vivien 1.1.2.1 active_threads_in_caller);
2399 vivien 1.1.2.1 }
2400 vivien 1.1.2.1 };
2401 vivien 1.1.2.1
2402 vivien 1.1.2.1 ar_callee.forAllActions(act_visitor);
2403 vivien 1.1.2.1
2404 vivien 1.1.2.1 // Step 2. Translate the "parallel action" items of
2405 vivien 1.1.2.1 // information from the callee, by applying the mu function on
2406 vivien 1.1.2.1 // their components (except for the n2 component of a load
2407 vivien 1.1.2.1 // action which is left unchanged if it's still present in the
2408 vivien 1.1.2.1 // new graph).
2409 vivien 1.1.2.1 ParActionVisitor par_act_visitor = new ParActionVisitor(){
2410 vivien 1.1.2.1 public void visit_par_ld(PALoad load, PANode nt2){
2411 vivien 1.1.2.1 if(!mu.contains(load.n2,load.n2)) return;
2412 vivien 1.1.2.1 ar_caller.add_ld(mu.getValues(load.n1),
2413 vivien 1.1.2.1 load.f,
2414 vivien 1.1.2.1 load.n2,
2415 vivien 1.1.2.1 mu.getValues(load.nt),
2416 vivien 1.1.2.1 mu.getValues(nt2));
2417 vivien 1.1.2.1 }
2418 vivien 1.1.2.1 public void visit_par_sync(PASync sync, PANode nt2){
2419 vivien 1.1.2.1 ar_caller.add_sync(sync.project(mu),
2420 vivien 1.1.2.1 mu.getValues(nt2));
2421 vivien 1.1.2.1 }
2422 vivien 1.1.2.1 };
2423 vivien 1.1.2.1
2424 vivien 1.1.2.1 ar_callee.forAllParActions(par_act_visitor);
2425 vivien 1.1.2.1 }
2426 vivien 1.1.2.1
2427 vivien 1.1.2.1
2428 vivien 1.1.2.1 private static void update_actions(final ActionRepository org_ar,
2429 vivien 1.1.2.1 final ActionRepository new_ar,
2430 vivien 1.1.2.1 final Relation mu){
2431 vivien 1.1.2.1 // Add this "common-sense" rule to the mapping: the inter-procedural
2432 vivien 1.1.2.1 // analysis stays in the same thread.
2433 vivien 1.1.2.1 mu.add(ActionRepository.THIS_THREAD,ActionRepository.THIS_THREAD);
2434 vivien 1.1.2.1
2435 vivien 1.1.2.1 ActionVisitor act_visitor = new ActionVisitor(){
2436 vivien 1.1.2.1 public void visit_ld(PALoad load){
2437 vivien 1.1.2.1 new_ar.add_ld(mu.getValues(load.n1),
2438 vivien 1.1.2.1 load.f,
2439 vivien 1.1.2.1 mu.getValues(load.n2),
2440 vivien 1.1.2.1 mu.getValues(load.nt),
2441 vivien 1.1.2.1 Collections.EMPTY_SET);
2442 vivien 1.1.2.1 }
2443 vivien 1.1.2.1 public void visit_sync(PASync sync){
2444 vivien 1.1.2.1 new_ar.add_sync(sync.project(mu),
2445 vivien 1.1.2.1 Collections.EMPTY_SET);
2446 vivien 1.1.2.1 }
2447 vivien 1.1.2.1 };
2448 vivien 1.1.2.1
2449 vivien 1.1.2.1 org_ar.forAllActions(act_visitor);
2450 vivien 1.1.2.1
2451 vivien 1.1.2.1 // Step 2. Translate the "parallel action" items of
2452 vivien 1.1.2.1 // information from the callee, by applying the mu function on
2453 vivien 1.1.2.1 // their components (except for the n2 component of a load
2454 vivien 1.1.2.1 // action which is left unchanged if it's still present in the
2455 vivien 1.1.2.1 // new graph).
2456 vivien 1.1.2.1 ParActionVisitor par_act_visitor = new ParActionVisitor(){
2457 vivien 1.1.2.1 public void visit_par_ld(PALoad load, PANode nt2){
2458 vivien 1.1.2.1 new_ar.add_ld(mu.getValues(load.n1),
2459 vivien 1.1.2.1 load.f,
2460 vivien 1.1.2.1 mu.getValues(load.n2),
2461 vivien 1.1.2.1 mu.getValues(load.nt),
2462 vivien 1.1.2.1 mu.getValues(nt2));
2463 vivien 1.1.2.1 }
2464 vivien 1.1.2.1 public void visit_par_sync(PASync sync, PANode nt2){
2465 vivien 1.1.2.1 new_ar.add_sync(sync.project(mu),
2466 vivien 1.1.2.1 mu.getValues(nt2));
2467 vivien 1.1.2.1 }
2468 vivien 1.1.2.1 };
2469 vivien 1.1.2.1
2470 vivien 1.1.2.1 org_ar.forAllParActions(par_act_visitor);
2471 vivien 1.1.2.1 }
2472 vivien 1.1.2.1
2473 vivien 1.1.2.1 private static void actions_add_ld(ODInformation callee_odi,
2474 vivien 1.1.2.1 final ODParIntGraph pig_caller,
2475 vivien 1.1.2.1 final ActionRepository ar,
2476 vivien 1.1.2.1 final Relation mapping,
2477 vivien 1.1.2.1 MethodHole hole,
2478 vivien 1.1.2.1 final Set callee_threads
2479 vivien 1.1.2.1 )
2480 vivien 1.1.2.1 {
2481 vivien 1.1.2.1 if (callee_odi.precise){
2482 cananian 1.7 for(Object n1O : callee_odi.outMaybe.edges.keySet()){
2483 cananian 1.7 PANode n1 = (PANode) n1O;
2484 vivien 1.1.2.1 Map n1_map = (Map) callee_odi.outMaybe.edges.get(n1);
2485 cananian 1.7 for(Object fO : n1_map.keySet()){
2486 cananian 1.7 String f = (String) fO;
2487 vivien 1.1.2.1 Relation n1_f = (Relation) n1_map.get(f);
2488 cananian 1.7 for(Object n2O : n1_f.keys()){
2489 cananian 1.7 PANode n2 = (PANode) n2O;
2490 vivien 1.1.2.1 if (n1_f.getValues(n2).contains(hole))
2491 vivien 1.1.2.1 ar.add_ld(mapping.getValues(n1),
2492 vivien 1.1.2.1 f,
2493 vivien 1.1.2.1 mapping.getValues(n2),
2494 vivien 1.1.2.1 ActionRepository.THIS_THREAD,
2495 vivien 1.1.2.1 callee_threads);
2496 vivien 1.1.2.1 }
2497 vivien 1.1.2.1 }
2498 vivien 1.1.2.1 }
2499 vivien 1.1.2.1 }
2500 vivien 1.1.2.1 else{
2501 vivien 1.1.2.1 PAEdgeVisitor visitor_O = new PAEdgeVisitor(){
2502 vivien 1.1.2.1 public void visit(Temp var, PANode node){
2503 cananian 1.3.2.1 assert false : (" var2node edge in O: " +
2504 vivien 1.1.2.1 var + "->" + node);
2505 vivien 1.1.2.1 }
2506 vivien 1.1.2.1 public void visit(PANode node1,String f, PANode node2){
2507 vivien 1.1.2.1 ar.add_ld(mapping.getValues(node1),
2508 vivien 1.1.2.1 f,
2509 vivien 1.1.2.1 mapping.getValues(node2),
2510 vivien 1.1.2.1 ActionRepository.THIS_THREAD,
2511 vivien 1.1.2.1 callee_threads);
2512 vivien 1.1.2.1 }
2513 vivien 1.1.2.1 };
2514 vivien 1.1.2.1 pig_caller.G.O.forAllEdges(visitor_O);
2515 vivien 1.1.2.1 }
2516 vivien 1.1.2.1 }
2517 vivien 1.1.2.1
2518 vivien 1.1.2.1 private static void actions_add_sync(ActionRepository ar,
2519 vivien 1.1.2.1 Set par_locks,
2520 vivien 1.1.2.1 Set callee_threads
2521 vivien 1.1.2.1 )
2522 vivien 1.1.2.1 {
2523 vivien 1.1.2.1 for(Iterator it=par_locks.iterator();it.hasNext(); )
2524 vivien 1.1.2.1 ar.add_sync((PASync) it.next(), callee_threads);
2525 vivien 1.1.2.1 }
2526 vivien 1.1.2.1
2527 vivien 1.1.2.1
2528 vivien 1.1.2.1 // Inserts the edge ordering relation of the callee into the graph of
2529 vivien 1.1.2.1 // the caller. In addition, records the fact that all the outside edges
2530 vivien 1.1.2.1 // from the callee appear after all the inside edges of the caller.
2531 vivien 1.1.2.1 private static void bring_eo(final EdgeOrdering eo_caller,
2532 vivien 1.1.2.1 final PAEdgeSet callerI,
2533 vivien 1.1.2.1 final EdgeOrdering eo_callee,
2534 vivien 1.1.2.1 final PAEdgeSet calleeO,
2535 vivien 1.1.2.1 final Relation mu){
2536 vivien 1.1.2.1
2537 vivien 1.1.2.1 eo_callee.forAllEntries(new RelationEntryVisitor(){
2538 vivien 1.1.2.1 public void visit(Object key, Object value){
2539 vivien 1.1.2.1 PAEdge eo = (PAEdge) key;
2540 vivien 1.1.2.1 PAEdge ei = (PAEdge) value;
2541 vivien 1.1.2.1 // make sure eo will appear into the new graph
2542 vivien 1.1.2.1 if(!mu.contains(eo.n2,eo.n2)) return;
2543 vivien 1.1.2.1
2544 vivien 1.1.2.1 Set ei_n1_set = mu.getValues(ei.n1);
2545 vivien 1.1.2.1 if(ei_n1_set.isEmpty()) return;
2546 vivien 1.1.2.1 Set ei_n2_set = mu.getValues(ei.n2);
2547 vivien 1.1.2.1 if(ei_n2_set.isEmpty()) return;
2548 vivien 1.1.2.1 Set eo_n1_set = mu.getValues(eo.n1);
2549 vivien 1.1.2.1 if(eo_n1_set.isEmpty()) return;
2550 vivien 1.1.2.1
2551 cananian 1.7 for (Object ei_n1O : ei_n1_set){
2552 cananian 1.7 PANode ei_n1 = (PANode) ei_n1O;
2553 cananian 1.7 for (Object ei_n2O : ei_n2_set){
2554 cananian 1.7 PANode ei_n2 = (PANode) ei_n2O;
2555 vivien 1.1.2.1 PAEdge new_ei = new PAEdge(ei_n1,ei.f,ei_n2);
2556 cananian 1.7 for (Object eo_n1O : eo_n1_set){
2557 cananian 1.7 PANode eo_n1 = (PANode) eo_n1O;
2558 vivien 1.1.2.1 eo_caller.add(new PAEdge(eo_n1,ei.f,eo.n2),
2559 vivien 1.1.2.1 new_ei);
2560 vivien 1.1.2.1 }
2561 vivien 1.1.2.1 }
2562 vivien 1.1.2.1 }
2563 vivien 1.1.2.1 }
2564 vivien 1.1.2.1 });
2565 vivien 1.1.2.1
2566 vivien 1.1.2.1
2567 vivien 1.1.2.1 // all the outside edges from the callee occur *after* all
2568 vivien 1.1.2.1 // the inside edges that exist in the caller right before the CALL
2569 vivien 1.1.2.1 calleeO.forAllEdges(new PAEdgeVisitor(){
2570 vivien 1.1.2.1 public void visit(Temp var, PANode node){}
2571 vivien 1.1.2.1 public void visit(PANode n1, String f, PANode n2){
2572 vivien 1.1.2.1 if(!mu.contains(n2,n2)) return;
2573 vivien 1.1.2.1 eo_caller.add(mu.getValues(n1),f,n2,callerI);
2574 vivien 1.1.2.1 }
2575 vivien 1.1.2.1 });
2576 vivien 1.1.2.1 }
2577 vivien 1.1.2.1
2578 vivien 1.1.2.1
2579 vivien 1.1.2.1 // Treats some native methods in a special way. Returns a pair of
2580 vivien 1.1.2.1 // ODParIntGraphs or null if it cannot handle this call.
2581 vivien 1.1.2.1 private static ODParIntGraphPair treatVerySpecialNatives
2582 vivien 1.1.2.1 (ODPointerAnalysis pa, CALL q, ODParIntGraph pig_before){
2583 vivien 1.1.2.1
2584 vivien 1.1.2.1 HMethod hm = q.method();
2585 vivien 1.1.2.1 if(hm == null) return null;
2586 vivien 1.1.2.1 ODParIntGraphPair pair = null;
2587 vivien 1.1.2.1
2588 vivien 1.1.2.1 if((pair = treat_arraycopy(pa, q, pig_before)) != null)
2589 vivien 1.1.2.1 return pair;
2590 vivien 1.1.2.1 if((pair = treat_clone(pa, q, pig_before)) != null)
2591 vivien 1.1.2.1 return pair;
2592 vivien 1.1.2.1
2593 vivien 1.1.2.1 return null;
2594 vivien 1.1.2.1 }
2595 vivien 1.1.2.1
2596 vivien 1.1.2.1
2597 vivien 1.1.2.1 // Aux method for treat_clone. It returns the set of possible types
2598 vivien 1.1.2.1 // (Set<HClass>) of the argument of clone(). Ugly code: I think we should
2599 vivien 1.1.2.1 // have a Quad form with types.
2600 vivien 1.1.2.1 private static Set aux_clone_get_types(CALL q){
2601 vivien 1.1.2.1 // The quad factory that generated this CALL quad
2602 vivien 1.1.2.1 QuadFactory qf = q.getFactory();
2603 vivien 1.1.2.1 // the method into which it appears.
2604 vivien 1.1.2.1 HMethod hm = qf.getMethod();
2605 vivien 1.1.2.1 // and the HCode containing the code of that method.
2606 vivien 1.1.2.1 HCode hcode = (HCode) qf.getParent();
2607 vivien 1.1.2.1 // et = Temp q.params(0) used in Quad q
2608 vivien 1.1.2.1 ExactTemp et = new ExactTemp(q, q.params(0));
2609 vivien 1.1.2.1
2610 vivien 1.1.2.1 TypeInference ti =
2611 vivien 1.1.2.1 new TypeInference(hm, hcode, Collections.singleton(et));
2612 vivien 1.1.2.1
2613 vivien 1.1.2.1 return ti.getType(et);
2614 vivien 1.1.2.1 }
2615 vivien 1.1.2.1
2616 vivien 1.1.2.1
2617 vivien 1.1.2.1 // Aux method for "treat_clone". Returns the set of all the fields
2618 vivien 1.1.2.1 // appearing in the types from the set "types".
2619 vivien 1.1.2.1 private static Set aux_clone_get_obj_fields(Set types){
2620 vivien 1.1.2.1 Set retval = new HashSet();
2621 cananian 1.7 for(Object hclassO : types){
2622 cananian 1.7 HClass hclass = (HClass) hclassO;
2623 vivien 1.1.2.1 if(hclass.isArray())
2624 vivien 1.1.2.1 System.out.println("CLONE: might be called for an array");
2625 vivien 1.1.2.1 HField[] hfields = hclass.getFields();
2626 vivien 1.1.2.1 for(int i = 0; i < hfields.length; i++)
2627 vivien 1.1.2.1 if(!hfields[i].getType().isPrimitive())
2628 vivien 1.1.2.1 retval.add(hfields[i].getName());
2629 vivien 1.1.2.1 }
2630 vivien 1.1.2.1 return retval;
2631 vivien 1.1.2.1 }
2632 vivien 1.1.2.1
2633 vivien 1.1.2.1
2634 vivien 1.1.2.1 // Treat the sequence "ld t = n_src.f; store n_R.f = t;". For a clone()
2635 vivien 1.1.2.1 // call, this is done for all fields f of the cloned object.
2636 vivien 1.1.2.1 private static void aux_clone_treat_pseudo_ldst(CALL q, String f,
2637 vivien 1.1.2.1 PANode n_R, PANode n_src, ODParIntGraph pig, NodeRepository node_rep){
2638 vivien 1.1.2.1
2639 vivien 1.1.2.1 // f_set contains all the nodes pointed to by <n_src, f>
2640 vivien 1.1.2.1 Set f_set = new HashSet(pig.G.I.pointedNodes(n_src, f));
2641 vivien 1.1.2.1
2642 vivien 1.1.2.1 if(pig.G.escaped(n_src)){
2643 vivien 1.1.2.1 PANode n_L = node_rep.getLoadNodeSpecial(q, f);
2644 vivien 1.1.2.1 pig.G.O.addEdge(n_src, f, n_L);
2645 vivien 1.1.2.1 if (ODPointerAnalysis.ON_DEMAND_ANALYSIS){
2646 vivien 1.1.2.1 pig.odi.addOutsideEdges(n_src, f, n_L);
2647 vivien 1.1.2.1 }
2648 vivien 1.1.2.1
2649 vivien 1.1.2.1 pig.ar.add_ld(n_src, f, n_L, ActionRepository.THIS_THREAD,
2650 vivien 1.1.2.1 pig.tau.activeThreadSet());
2651 vivien 1.1.2.1 // TODO: edge ordering relation (if we want to maintain it)
2652 vivien 1.1.2.1 f_set.add(n_L);
2653 vivien 1.1.2.1 }
2654 vivien 1.1.2.1
2655 cananian 1.7 for(Object nO : f_set){
2656 cananian 1.7 PANode n = (PANode) nO;
2657 vivien 1.1.2.1 pig.G.I.addEdge(n_R, f, n);
2658 vivien 1.1.2.1 if (ODPointerAnalysis.ON_DEMAND_ANALYSIS){
2659 vivien 1.1.2.1 pig.odi.addInsideEdges(n_R, f, n);
2660 vivien 1.1.2.1 }
2661 vivien 1.1.2.1 }
2662 vivien 1.1.2.1 }
2663 vivien 1.1.2.1
2664 vivien 1.1.2.1
2665 vivien 1.1.2.1 // Specially treats
2666 vivien 1.1.2.1 // "protected native java.lang.Object java.lang.Object.clone()"
2667 vivien 1.1.2.1 private static ODParIntGraphPair treat_clone(ODPointerAnalysis pa, CALL q,
2668 vivien 1.1.2.1 ODParIntGraph pig_before){
2669 vivien 1.1.2.1 HMethod callee = q.method();
2670 vivien 1.1.2.1 if(!callee.getName().equals("clone") ||
2671 vivien 1.1.2.1 !callee.getDeclaringClass().getName().equals("java.lang.Object"))
2672 vivien 1.1.2.1 return null;
2673 vivien 1.1.2.1
2674 vivien 1.1.2.1 //if(DEBUG)
2675 vivien 1.1.2.1 System.out.println("NATIVE (special): " + callee);
2676 vivien 1.1.2.1
2677 vivien 1.1.2.1 ODParIntGraph pig_after0 = pig_before;
2678 vivien 1.1.2.1 ODParIntGraph pig_after1 = (ODParIntGraph) pig_before.clone();
2679 vivien 1.1.2.1
2680 vivien 1.1.2.1 // do the actions of the "clone()" method: create a new object (n_R),
2681 vivien 1.1.2.1 // copy the fields from the objects passed as params to clone to n_R
2682 vivien 1.1.2.1 NodeRepository node_rep = pa.getNodeRepository();
2683 vivien 1.1.2.1 PANode n_R = node_rep.getCodeNode(q, PANode.RETURN);
2684 vivien 1.1.2.1
2685 vivien 1.1.2.1 Set lo_types = aux_clone_get_types(q);
2686 vivien 1.1.2.1 if(DEBUG)
2687 vivien 1.1.2.1 System.out.println("CLONE: POSSIBLE TYPES:" + lo_types);
2688 vivien 1.1.2.1
2689 vivien 1.1.2.1 Set flags = aux_clone_get_obj_fields(lo_types);
2690 vivien 1.1.2.1 if(DEBUG)
2691 vivien 1.1.2.1 System.out.println("CLONE: POSSIBLE FLAGS:" + flags);
2692 vivien 1.1.2.1
2693 vivien 1.1.2.1 int nb_flags = flags.size();
2694 vivien 1.1.2.1
2695 vivien 1.1.2.1 Temp lo = q.params(0);
2696 vivien 1.1.2.1 Set srcs = pig_before.G.I.pointedNodes(lo);
2697 vivien 1.1.2.1
2698 vivien 1.1.2.1 Iterator it = flags.iterator();
2699 vivien 1.1.2.1 for(int i = 0; i < nb_flags; i++){
2700 vivien 1.1.2.1 String f = (String) it.next();
2701 cananian 1.7 for(Object n_srcO : srcs){
2702 cananian 1.7 PANode n_src = (PANode) n_srcO;
2703 vivien 1.1.2.1 aux_clone_treat_pseudo_ldst(q, f, n_R, n_src, pig_after0,
2704 vivien 1.1.2.1 node_rep);
2705 vivien 1.1.2.1 }
2706 vivien 1.1.2.1 }
2707 vivien 1.1.2.1
2708 vivien 1.1.2.1 // set the link l_R to the RETURN node
2709 vivien 1.1.2.1 Temp l_R = q.retval();
2710 vivien 1.1.2.1 if(l_R != null)
2711 vivien 1.1.2.1 pig_after0.G.I.addEdge(l_R, n_R);
2712 vivien 1.1.2.1
2713 vivien 1.1.2.1 aux_native_treat_excp(q, pig_after1, node_rep);
2714 vivien 1.1.2.1
2715 vivien 1.1.2.1 return new ODParIntGraphPair(pig_after0, pig_after1);
2716 vivien 1.1.2.1 }
2717 vivien 1.1.2.1
2718 vivien 1.1.2.1
2719 vivien 1.1.2.1 // Aux method for all the special treatments of native methods. If the
2720 vivien 1.1.2.1 // called native method can return an exception, and there is a Temp l_E
2721 vivien 1.1.2.1 // to receive (a pointer to) it, a PANode.EXCEPT node associated with this
2722 vivien 1.1.2.1 // CALL is created (if it doesn't exist yet) and the proper link is set
2723 vivien 1.1.2.1 // from l_E to n_E, in the parallel interaction graph "pig".
2724 vivien 1.1.2.1 private static void aux_native_treat_excp(CALL q, ODParIntGraph pig,
2725 vivien 1.1.2.1 NodeRepository node_rep){
2726 vivien 1.1.2.1 Temp l_E = q.retex();
2727 vivien 1.1.2.1 HMethod hm = q.method();
2728 vivien 1.1.2.1
2729 vivien 1.1.2.1 if((l_E == null) || (hm.getExceptionTypes().length == 0)) return;
2730 vivien 1.1.2.1
2731 vivien 1.1.2.1 pig.G.I.removeEdges(l_E);
2732 vivien 1.1.2.1 PANode n_E = node_rep.getCodeNode(q, PANode.EXCEPT);
2733 vivien 1.1.2.1 pig.G.I.addEdge(l_E, n_E);
2734 vivien 1.1.2.1 pig.G.e.addMethodHole(n_E, hm);
2735 vivien 1.1.2.1 // no pig.G.propagate is necessary since n_E cannot point to anything
2736 vivien 1.1.2.1 // that is not escaped into that native method.
2737 vivien 1.1.2.1 }
2738 vivien 1.1.2.1
2739 vivien 1.1.2.1 // treat specially "public static native void java.lang.System.arraycopy
2740 vivien 1.1.2.1 // (Object src, int, Object dst, int, int);
2741 vivien 1.1.2.1 // We hope that we really know what arraycopy does ...
2742 vivien 1.1.2.1 private static ODParIntGraphPair treat_arraycopy(ODPointerAnalysis pa, CALL q,
2743 vivien 1.1.2.1 ODParIntGraph pig_before){
2744 vivien 1.1.2.1 HMethod hm = q.method();
2745 vivien 1.1.2.1 if(!hm.getName().equals("arraycopy") ||
2746 vivien 1.1.2.1 !hm.getDeclaringClass().getName().equals("java.lang.System"))
2747 vivien 1.1.2.1 return null;
2748 vivien 1.1.2.1
2749 vivien 1.1.2.1 //if(DEBUG)
2750 salcianu 1.5 System.out.println("NATIVE (special): " + Util.code2str(q));
2751 vivien 1.1.2.1
2752 vivien 1.1.2.1 // the conventional field name used for the array's entries
2753 vivien 1.1.2.1 final String f = ODPointerAnalysis.ARRAY_CONTENT;
2754 vivien 1.1.2.1
2755 vivien 1.1.2.1 Temp l_src = q.params(0);
2756 vivien 1.1.2.1 Temp l_dst = q.params(2);
2757 vivien 1.1.2.1
2758 vivien 1.1.2.1 Set dst_set = pig_before.G.I.pointedNodes(l_dst);
2759 vivien 1.1.2.1
2760 vivien 1.1.2.1 Set src_set = pig_before.G.I.pointedNodes(l_src);
2761 vivien 1.1.2.1 Set set_S =
2762 vivien 1.1.2.1 pig_before.G.I.pointedNodes(src_set, f);
2763 vivien 1.1.2.1
2764 vivien 1.1.2.1 Set set_E = new HashSet();
2765 cananian 1.7 for(Object nodeO : src_set){
2766 cananian 1.7 PANode node = (PANode) nodeO;
2767 vivien 1.1.2.1 if(pig_before.G.e.hasEscaped(node))
2768 vivien 1.1.2.1 set_E.add(node);
2769 vivien 1.1.2.1 }
2770 vivien 1.1.2.1
2771 vivien 1.1.2.1 NodeRepository node_rep = pa.getNodeRepository();
2772 vivien 1.1.2.1
2773 vivien 1.1.2.1 if(set_E.isEmpty()){
2774 vivien 1.1.2.1 pig_before.G.I.addEdges(dst_set, f, set_S);
2775 vivien 1.1.2.1 if (ODPointerAnalysis.ON_DEMAND_ANALYSIS){
2776 vivien 1.1.2.1 pig_before.odi.addInsideEdges(dst_set, f, set_S);
2777 vivien 1.1.2.1 }
2778 vivien 1.1.2.1 }
2779 vivien 1.1.2.1 else{
2780 vivien 1.1.2.1 PANode load_node = node_rep.getCodeNode(q, PANode.LOAD);
2781 vivien 1.1.2.1
2782 vivien 1.1.2.1 pig_before.G.O.addEdges(set_E, f, load_node);
2783 vivien 1.1.2.1 if (ODPointerAnalysis.ON_DEMAND_ANALYSIS){
2784 vivien 1.1.2.1 pig_before.odi.addOutsideEdges(set_E, f, load_node);
2785 vivien 1.1.2.1 }
2786 vivien 1.1.2.1
2787 vivien 1.1.2.1 if(!ODPointerAnalysis.IGNORE_EO)
2788 vivien 1.1.2.1 pig_before.eo.add(set_E, f, load_node, pig_before.G.I);
2789 vivien 1.1.2.1
2790 vivien 1.1.2.1 set_S.add(load_node);
2791 vivien 1.1.2.1 pig_before.G.I.addEdges(dst_set, f, set_S);
2792 vivien 1.1.2.1 if (ODPointerAnalysis.ON_DEMAND_ANALYSIS){
2793 vivien 1.1.2.1 pig_before.odi.addInsideEdges(dst_set, f, set_S);
2794 vivien 1.1.2.1 }
2795 vivien 1.1.2.1 pig_before.G.propagate(set_E);
2796 vivien 1.1.2.1
2797 vivien 1.1.2.1 // update the action repository
2798 vivien 1.1.2.1 Set active_threads = pig_before.tau.activeThreadSet();
2799 vivien 1.1.2.1 for(Iterator it_E = set_E.iterator(); it_E.hasNext(); )
2800 vivien 1.1.2.1 pig_before.ar.add_ld((PANode) it_E.next(), f, load_node,
2801 vivien 1.1.2.1 ActionRepository.THIS_THREAD,
2802 vivien 1.1.2.1 active_threads);
2803 vivien 1.1.2.1 }
2804 vivien 1.1.2.1
2805 vivien 1.1.2.1 ODParIntGraph pig_after1 = (ODParIntGraph) pig_before.clone();
2806 vivien 1.1.2.1 // Set the edges for the exception node in graph 1.
2807 vivien 1.1.2.1 Temp l_E = q.retex();
2808 vivien 1.1.2.1 if(l_E != null){
2809 vivien 1.1.2.1 pig_after1.G.I.removeEdges(l_E);
2810 vivien 1.1.2.1 PANode n_E = node_rep.getCodeNode(q, PANode.EXCEPT);
2811 vivien 1.1.2.1 pig_after1.G.I.addEdge(l_E, n_E);
2812 vivien 1.1.2.1 pig_after1.G.e.addMethodHole(n_E, hm);
2813 vivien 1.1.2.1 }
2814 vivien 1.1.2.1 return new ODParIntGraphPair(pig_before, pig_after1);
2815 vivien 1.1.2.1 }
2816 vivien 1.1.2.1
2817 vivien 1.1.2.1
2818 vivien 1.1.2.1 // Many native methods don't do any synchronizations on their object
2819 vivien 1.1.2.1 // parameters, don't store them in static fields and don't modify the
2820 vivien 1.1.2.1 // points-to graph accessible from these object parameters.
2821 vivien 1.1.2.1 private static boolean isUnharmful(HMethod hm) {
2822 vivien 1.1.2.1 return uhms.contains(hm);
2823 vivien 1.1.2.1 }
2824 vivien 1.1.2.1 // Checks whether a method is totally harmful (i.e. all the parameters
2825 vivien 1.1.2.1 // must be marked as escaping into it). A CALL to such a method cannot
2826 vivien 1.1.2.1 // be treated otherwise than by skipping it.
2827 vivien 1.1.2.1 private static boolean isTotallyHarmful(HMethod hm) {
2828 vivien 1.1.2.1 return !isUnharmful(hm); // for the moment, conservative treatment
2829 vivien 1.1.2.1 }
2830 vivien 1.1.2.1 private static Set uhms = new HashSet();
2831 vivien 1.1.2.1 static{
2832 vivien 1.1.2.1 String[][] methods = {
2833 vivien 1.1.2.1 {"java.io.FileInputStream", "open"},
2834 vivien 1.1.2.1 {"java.io.FileInputStream", "close"},
2835 vivien 1.1.2.1 {"java.io.FileInputStream", "available"},
2836 vivien 1.1.2.1 {"java.io.FileInputStream", "read"},
2837 vivien 1.1.2.1 {"java.io.FileInputStream", "readBytes"},
2838 vivien 1.1.2.1
2839 vivien 1.1.2.1 {"java.io.FileOutputStream", "open"},
2840 vivien 1.1.2.1 {"java.io.FileOutputStream", "openAppend"},
2841 vivien 1.1.2.1 {"java.io.FileOutputStream", "close"},
2842 vivien 1.1.2.1 {"java.io.FileOutputStream", "write"},
2843 vivien 1.1.2.1 {"java.io.FileOutputStream", "writeBytes"},
2844 vivien 1.1.2.1
2845 vivien 1.1.2.1 {"java.lang.Throwable", "printStackTrace0"},
2846 vivien 1.1.2.1 {"java.lang.Throwable", "fillInStackTrace"},
2847 vivien 1.1.2.1 {"java.lang.Class", "getName"},
2848 vivien 1.1.2.1 {"java.lang.Class", "getPrimitiveClass"},
2849 vivien 1.1.2.1
2850 vivien 1.1.2.1 {"java.lang.Object", "hashCode"}
2851 vivien 1.1.2.1 };
2852 vivien 1.1.2.1
2853 vivien 1.1.2.1 for(int i = 0; i < methods.length; i++)
2854 vivien 1.1.2.1 uhms.addAll(getMethods(methods[i][0], methods[i][1]));
2855 vivien 1.1.2.1 }
2856 vivien 1.1.2.1
2857 vivien 1.1.2.1 // Returns all the methods having the name m_name
2858 vivien 1.1.2.1 // that are declared in class c_name.
2859 vivien 1.1.2.1 private static Collection getMethods(String c_name, String m_name) {
2860 vivien 1.1.2.1 List retval = new LinkedList();
2861 vivien 1.1.2.1 HClass hclass = Loader.systemLinker.forName(c_name);
2862 vivien 1.1.2.1 HMethod[] hms = hclass.getDeclaredMethods();
2863 vivien 1.1.2.1 for(int i = 0; i < hms.length; i++)
2864 vivien 1.1.2.1 if(m_name.equals(hms[i].getName()))
2865 vivien 1.1.2.1 retval.add(hms[i]);
2866 vivien 1.1.2.1 return retval;
2867 vivien 1.1.2.1 }
2868 vivien 1.1.2.1
2869 vivien 1.1.2.1
2870 vivien 1.1.2.1 // After a method hole has been analyzed for all possible callees,
2871 vivien 1.1.2.1 // the formal return and exception nodes are removed for the pig.
2872 vivien 1.1.2.1
2873 vivien 1.1.2.1 public static void clean_call(ODParIntGraphPair pp, MethodHole hole){
2874 vivien 1.1.2.1 clean_call(pp.pig[0],hole);
2875 vivien 1.1.2.1 clean_call(pp.pig[1],hole);
2876 vivien 1.1.2.1 }
2877 vivien 1.1.2.1
2878 vivien 1.1.2.1 public static void clean_call(ODParIntGraph pig, MethodHole hole){
2879 vivien 1.1.2.1 HashSet nodes = new HashSet();
2880 vivien 1.1.2.1 if (hole.ret()!=null) nodes.add(hole.ret());
2881 vivien 1.1.2.1 if (hole.exc()!=null) nodes.add(hole.exc());
2882 vivien 1.1.2.1 if (!nodes.isEmpty())
2883 vivien 1.1.2.1 pig.remove(nodes);
2884 vivien 1.1.2.1 // System.out.println(" Pig after cleaning" + pig);
2885 vivien 1.1.2.1 }
2886 vivien 1.1.2.1
2887 vivien 1.1.2.1 public static void print_relation(Relation mu){
2888 vivien 1.1.2.1 Set keys = mu.keys();
2889 cananian 1.7 for(Object sourceO : keys){
2890 cananian 1.7 PANode source = (PANode) sourceO;
2891 vivien 1.1.2.1 System.out.print(" " + source + " ->");
2892 vivien 1.1.2.1 Set sinks = mu.getValues(source);
2893 cananian 1.7 for(Object sinkO : sinks){
2894 cananian 1.7 PANode sink = (PANode) sinkO;
2895 vivien 1.1.2.1 System.out.print(" " + sink);
2896 vivien 1.1.2.1 }
2897 vivien 1.1.2.1 System.out.println(".");
2898 vivien 1.1.2.1 }
2899 vivien 1.1.2.1 }
2900 vivien 1.1.2.1
2901 vivien 1.1.2.1 public static Set projection(Set nodes, Relation mu, Set mu_nodes){
2902 vivien 1.1.2.1 Iterator it = nodes.iterator();
2903 vivien 1.1.2.1 while(it.hasNext())
2904 vivien 1.1.2.1 mu_nodes.addAll(mu.getValues(it.next()));
2905 vivien 1.1.2.1
2906 vivien 1.1.2.1 return mu_nodes;
2907 vivien 1.1.2.1 }
2908 vivien 1.1.2.1
2909 vivien 1.1.2.1 public static void print_nodeset(Set nodes){
2910 vivien 1.1.2.1 System.out.print(" ");
2911 vivien 1.1.2.1 Iterator it = nodes.iterator();
2912 vivien 1.1.2.1 while(it.hasNext())
2913 vivien 1.1.2.1 System.out.print(" " + ((PANode) it.next()));
2914 vivien 1.1.2.1 System.out.println();
2915 vivien 1.1.2.1 }
2916 vivien 1.1.2.1
2917 vivien 1.1.2.1 private static Relation projection(Relation original, Relation projecting){
2918 vivien 1.1.2.1 Relation mapping = new LightRelation();
2919 vivien 1.1.2.1
2920 cananian 1.7 for(Object n_orgO : original.keys()){
2921 cananian 1.7 PANode n_org = (PANode) n_orgO;
2922 vivien 1.1.2.1 for(Iterator inter_it = original.getValues(n_org).iterator();
2923 vivien 1.1.2.1 inter_it.hasNext(); )
2924 vivien 1.1.2.1 mapping.addAll(n_org,projecting.getValues(inter_it.next()));
2925 vivien 1.1.2.1 }
2926 vivien 1.1.2.1
2927 vivien 1.1.2.1 return mapping;
2928 vivien 1.1.2.1 }
2929 vivien 1.1.2.1
2930 vivien 1.1.2.1
2931 vivien 1.1.2.1 public static LightRelation create_extended_mapping(ODParIntGraph pig,
2932 vivien 1.1.2.1 final Relation mapping,
2933 vivien 1.1.2.1 Set toberemoved)
2934 vivien 1.1.2.1 {
2935 vivien 1.1.2.1 final LightRelation mapping_extended = (LightRelation) mapping.clone();
2936 vivien 1.1.2.1
2937 vivien 1.1.2.1 pig.forAllNodes(new PANodeVisitor(){
2938 vivien 1.1.2.1 public void visit(PANode node){
2939 vivien 1.1.2.1 mapping_extended.add(node,node);
2940 vivien 1.1.2.1 }
2941 vivien 1.1.2.1 });
2942 vivien 1.1.2.1
2943 cananian 1.7 for(Object nO : toberemoved) {
2944 cananian 1.7 PANode n = (PANode) nO;
2945 vivien 1.1.2.1 mapping_extended.remove(n,n);
2946 vivien 1.1.2.1 }
2947 vivien 1.1.2.1
2948 vivien 1.1.2.1 return mapping_extended;
2949 vivien 1.1.2.1 }
2950 vivien 1.1.2.1
2951 cananian 1.2 }// end of the class