1 salcianu 1.1.2.1 // PointerAnalysis.java, created Sat Jan 8 23:22:24 2000 by salcianu
2 cananian 1.1.2.85 // Copyright (C) 2000 Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
3 salcianu 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 salcianu 1.1.2.1 package harpoon.Analysis.PointerAnalysis;
5 salcianu 1.1.2.1
6 salcianu 1.1.2.33 import java.util.HashMap;
7 salcianu 1.1.2.23 import java.util.Map;
8 salcianu 1.1.2.1 import java.util.Iterator;
9 salcianu 1.1.2.1 import java.util.Enumeration;
10 salcianu 1.1.2.1 import java.util.Set;
11 salcianu 1.1.2.1 import java.util.HashSet;
12 salcianu 1.1.2.9 import java.util.Date;
13 salcianu 1.1.2.11 import java.util.Collections;
14 salcianu 1.1.2.14 import java.util.Arrays;
15 salcianu 1.1.2.14 import java.util.Comparator;
16 salcianu 1.12 import java.util.Collection;
17 salcianu 1.12 import java.util.List;
18 salcianu 1.12 import java.util.LinkedList;
19 salcianu 1.1.2.1
20 salcianu 1.1.2.51 import java.lang.reflect.Modifier;
21 salcianu 1.1.2.51
22 salcianu 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
23 salcianu 1.1.2.33 import harpoon.ClassFile.HCodeElement;
24 salcianu 1.1.2.2 import harpoon.ClassFile.HClass;
25 salcianu 1.1.2.1 import harpoon.ClassFile.HMethod;
26 salcianu 1.1.2.1 import harpoon.ClassFile.HField;
27 salcianu 1.1.2.47 import harpoon.ClassFile.HCode;
28 salcianu 1.1.2.81 import harpoon.ClassFile.Linker;
29 salcianu 1.1.2.47
30 salcianu 1.1.2.1 import harpoon.Analysis.Quads.CallGraph;
31 salcianu 1.1.2.1 import harpoon.Analysis.AllCallers;
32 salcianu 1.1.2.1 import harpoon.Analysis.ClassHierarchy;
33 salcianu 1.1.2.33 import harpoon.Util.LightBasicBlocks.LightBasicBlock;
34 salcianu 1.1.2.1
35 salcianu 1.1.2.1 import harpoon.Temp.Temp;
36 salcianu 1.1.2.1
37 salcianu 1.1.2.1 import harpoon.IR.Quads.Quad;
38 salcianu 1.1.2.1 import harpoon.IR.Quads.QuadVisitor;
39 salcianu 1.1.2.1 import harpoon.IR.Quads.HEADER;
40 salcianu 1.1.2.1 import harpoon.IR.Quads.METHOD;
41 salcianu 1.1.2.1 import harpoon.IR.Quads.AGET;
42 salcianu 1.1.2.1 import harpoon.IR.Quads.ALENGTH;
43 salcianu 1.1.2.1 import harpoon.IR.Quads.ANEW;
44 salcianu 1.7 import harpoon.IR.Quads.CONST;
45 salcianu 1.1.2.1 import harpoon.IR.Quads.ASET;
46 salcianu 1.1.2.1 import harpoon.IR.Quads.GET;
47 salcianu 1.1.2.1 import harpoon.IR.Quads.MOVE;
48 salcianu 1.1.2.1 import harpoon.IR.Quads.NEW;
49 salcianu 1.1.2.1 import harpoon.IR.Quads.RETURN;
50 salcianu 1.1.2.5 import harpoon.IR.Quads.THROW;
51 salcianu 1.1.2.1 import harpoon.IR.Quads.SET;
52 salcianu 1.1.2.6 import harpoon.IR.Quads.CALL;
53 salcianu 1.1.2.12 import harpoon.IR.Quads.MONITORENTER;
54 salcianu 1.1.2.12 import harpoon.IR.Quads.MONITOREXIT;
55 salcianu 1.1.2.1 import harpoon.IR.Quads.FOOTER;
56 salcianu 1.1.2.44 import harpoon.IR.Quads.TYPECAST;
57 salcianu 1.1.2.1
58 salcianu 1.1.2.25 import harpoon.Analysis.MetaMethods.MetaMethod;
59 salcianu 1.1.2.25 import harpoon.Analysis.MetaMethods.MetaCallGraph;
60 salcianu 1.1.2.25 import harpoon.Analysis.MetaMethods.MetaAllCallers;
61 salcianu 1.1.2.25
62 salcianu 1.12 import harpoon.Analysis.MetaMethods.GenType;
63 salcianu 1.1.2.47
64 salcianu 1.1.2.33 import harpoon.Util.LightBasicBlocks.LBBConverter;
65 salcianu 1.1.2.33 import harpoon.Util.LightBasicBlocks.CachingSCCLBBFactory;
66 salcianu 1.1.2.31 import harpoon.Util.Graphs.SCComponent;
67 salcianu 1.11 import harpoon.Util.Graphs.Navigator;
68 salcianu 1.12 import harpoon.Util.Graphs.DiGraph;
69 salcianu 1.12 import harpoon.Util.Graphs.ForwardNavigator;
70 salcianu 1.18 import harpoon.Util.Graphs.TopSortedCompDiGraph;
71 salcianu 1.1.2.31 import harpoon.Util.UComp;
72 cananian 1.16 import net.cscott.jutil.LinearSet;
73 salcianu 1.12
74 salcianu 1.12 import harpoon.Util.DataStructs.Relation;
75 salcianu 1.12 import harpoon.Util.DataStructs.LightRelation;
76 salcianu 1.1.2.1
77 salcianu 1.1.2.27 import harpoon.Util.Util;
78 salcianu 1.1.2.27
79 salcianu 1.1.2.1 /**
80 salcianu 1.1.2.16 * <code>PointerAnalysis</code> is the main class of the Pointer Analysis
81 salcianu 1.1.2.16 package. It is designed to act as a <i>query-object</i>: after being
82 salcianu 1.1.2.64 initialized, it can be asked to provide the Parallel Interaction Graph
83 salcianu 1.1.2.19 valid at the end of a specific method.
84 salcianu 1.1.2.1 *
85 cananian 1.1.2.85 * @author Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
86 salcianu 1.21 * @version $Id: PointerAnalysis.java,v 1.21 2004/03/06 21:52:24 salcianu Exp $
87 salcianu 1.1.2.1 */
88 salcianu 1.1.2.80 public class PointerAnalysis implements java.io.Serializable {
89 salcianu 1.1.2.66 public static final boolean DEBUG = false;
90 salcianu 1.1.2.66 public static final boolean DEBUG2 = false;
91 salcianu 1.1.2.60 public static final boolean DEBUG_SCC = true;
92 salcianu 1.1.2.74 public static final boolean DEBUG_INTRA = false;
93 salcianu 1.1.2.25
94 salcianu 1.1.2.71 /** crazy, isn't it? */
95 salcianu 1.1.2.71 public static boolean MEGA_DEBUG = false;
96 salcianu 1.12 public static boolean MEGA_DEBUG2 = false;
97 salcianu 1.12 private static boolean SHOW_INSTR = false;
98 salcianu 1.1.2.71
99 salcianu 1.1.2.75 /** Turns on the recording of the actions done by the program. */
100 salcianu 1.1.2.75 public static boolean RECORD_ACTIONS = false;
101 salcianu 1.1.2.75
102 salcianu 1.12 /** Hack to speed it up: it appears to me that the edge ordering
103 salcianu 1.12 relation is not extremely important: in recursive methods or in
104 salcianu 1.12 methods with loops, it tends to be just a cartesian product between
105 salcianu 1.12 I and O. */
106 salcianu 1.12 public static final boolean IGNORE_EO = true;
107 salcianu 1.12
108 salcianu 1.12
109 salcianu 1.12 /** Ignore what is load from a RETURN/EXCEPT node. Anyway, we
110 salcianu 1.12 cannot determine what is load from there. */
111 salcianu 1.12 public static boolean IGNORE_LOADS_FROM_NATIVES = true;
112 salcianu 1.12
113 salcianu 1.12 /** If <code>false</code>, do not keep track of all un-analyzed
114 salcianu 1.12 methods where a node escapes. Instead, just record the fact
115 salcianu 1.12 whether a node escapes (or not) in some un-analyzed method. */
116 salcianu 1.12 public static boolean CONDENSED_ESCAPE_INFO = true;
117 salcianu 1.12
118 salcianu 1.12 /** If <code>true</code>, compress all load nodes that escape into
119 salcianu 1.12 an unanalyzed method and/or a static field into the single
120 salcianu 1.12 summar node NodeRepository.LOST_SUMMARY</code> (currently,
121 salcianu 1.12 this is done only at the end of a method, when producing the
122 salcianu 1.12 external version of the <code>ParIntGraph</code>). This
123 salcianu 1.12 compression is applied to the external versions of the
124 salcianu 1.12 parallel interaction graphs, after the end of the fixed point
125 salcianu 1.12 computation for a SCC of methods. */
126 salcianu 1.12 public static boolean COMPRESS_LOST_NODES = true;
127 salcianu 1.12
128 salcianu 1.14 public static boolean TOPLAS_PAPER = true;
129 salcianu 1.14
130 salcianu 1.12 /** Same as <code>COMPRESS_LOST_NODES</code>, but done at the end
131 salcianu 1.12 of the analysis of each method. BREAKS MONOTONICITY! */
132 salcianu 1.12 public static boolean AGGRESSIVE_COMPRESS_LOST_NODES = true;
133 salcianu 1.12
134 salcianu 1.12 /** If <code>true</code>, then each time we try to load something
135 salcianu 1.12 from an escaped node that already has a few load nodes (for
136 salcianu 1.12 the field we load), we reuse the smallest existent node,
137 salcianu 1.12 instead of generating a node for that LOAD instruction.
138 salcianu 1.12 BREAKS MONOTONICITY! */
139 salcianu 1.12 public static boolean REUSE_LOAD_NODES = true;
140 salcianu 1.12
141 salcianu 1.12 /** Controls whether the analysis models the <code>null</code>
142 salcianu 1.12 references by edges to the special node <code>NULL</code>, or
143 salcianu 1.12 simply ignores them. */
144 salcianu 1.12 public static boolean TREAT_NULL = false;
145 salcianu 1.12
146 salcianu 1.12 /** Controls whether the analysis models references to constant
147 salcianu 1.12 Strings by edges to the special node <code>CONST</code>, or
148 salcianu 1.12 simply ignores them. */
149 salcianu 1.12 public static boolean TREAT_CONST = false;
150 salcianu 1.12
151 salcianu 1.12 /** If <code>true</code>, then we do not introduce edges about
152 salcianu 1.12 which we can infer that they violate the type declarations:
153 salcianu 1.12 e.g., an edge on the field "foo" from an inside node
154 salcianu 1.12 for <code>new Integer</code>. */
155 salcianu 1.12 public static boolean CONSIDER_TYPES = true;
156 salcianu 1.12
157 salcianu 1.20 /** Turns on the save memory mode. In this mode, some of the speed is
158 salcianu 1.1.2.61 sacrified for the sake of the memory consumption. More specifically,
159 salcianu 1.1.2.61 the <i>Interior</i>, large version of the Parallel Interaction Graph
160 salcianu 1.1.2.61 at the end of a method is no longer cached. */
161 salcianu 1.1.2.61 public static final boolean SAVE_MEMORY = false;
162 salcianu 1.1.2.61
163 salcianu 1.1.2.25 /** Makes the pointer analysis deterministic to make the debug easier.
164 salcianu 1.1.2.25 The main source of undeterminism in our code is the intensive use of
165 salcianu 1.1.2.25 <code>Set</code>s which doesn't offer any guarantee about the order
166 salcianu 1.1.2.64 in which they iterate over their elements. */
167 salcianu 1.1.2.14 public static final boolean DETERMINISTIC = true;
168 salcianu 1.1.2.25
169 salcianu 1.1.2.70 /** Turns on the printing of some timing info. */
170 salcianu 1.1.2.60 public static boolean TIMING = true;
171 salcianu 1.12 public static boolean FINE_TIMING = true;
172 salcianu 1.1.2.19 public static final boolean STATS = true;
173 salcianu 1.1.2.84 public static boolean SHOW_NODES = true;
174 salcianu 1.1.2.56 public static final boolean DETAILS2 = false;
175 salcianu 1.1.2.1
176 salcianu 1.1.2.26 /** Activates the calling context sensitivity. When this flag is
177 salcianu 1.1.2.26 on, the nodes from the graph of the callee are specialized for each
178 salcianu 1.1.2.21 call site (up to <code>MAX_SPEC_DEPTH</code> times). This increases
179 salcianu 1.1.2.26 the precision of the analysis but requires more time and memory. */
180 salcianu 1.1.2.29 public static boolean CALL_CONTEXT_SENSITIVE = false;
181 salcianu 1.1.2.21
182 salcianu 1.1.2.21 /** The specialization limit. This puts a limit to the otherwise
183 salcianu 1.1.2.21 exponential growth of the number of nodes in the analysis. */
184 salcianu 1.1.2.29 public static int MAX_SPEC_DEPTH = 1;
185 salcianu 1.1.2.21
186 salcianu 1.1.2.26 /** Activates the full thread sensitivity. When this flag is on,
187 salcianu 1.1.2.26 the analysis makes the distinction not only between the nodes
188 salcianu 1.1.2.26 allocated by the current thread and those allocated by all the
189 salcianu 1.1.2.26 others but also between the nodes allocated by threads with
190 salcianu 1.1.2.26 different run methods (for the time being, we cannot make the
191 salcianu 1.1.2.26 distinction between two threads with the same thread node). */
192 salcianu 1.1.2.29 public static boolean THREAD_SENSITIVE = false;
193 salcianu 1.1.2.26
194 salcianu 1.1.2.26 /** Activates the weak thread sensitivity. When this flag is
195 salcianu 1.1.2.26 on, the precision of the interthread analysis is increased:
196 salcianu 1.1.2.26 the nodes from the graph of the run method of the thread whose
197 salcianu 1.1.2.26 interactions with the current thread are analyzed are specialized
198 salcianu 1.1.2.26 to differenciate between the nodes created by that thread and
199 salcianu 1.1.2.26 the nodes created by the current one. This increases
200 salcianu 1.1.2.26 the precision of the analysis but requires more time and memory. */
201 salcianu 1.1.2.29 public static boolean WEAKLY_THREAD_SENSITIVE = false;
202 salcianu 1.1.2.26
203 salcianu 1.1.2.26 /** Activates the loop sensitivity. When this flag is on, the precision
204 salcianu 1.1.2.26 of the intra-method analysis is increased by making the difference
205 salcianu 1.1.2.26 between the last object allocated at a specific object creation
206 salcianu 1.1.2.26 site inside a loop and the objects allocated at the same object
207 salcianu 1.1.2.26 creation site but in the previous iterations. This enambles
208 salcianu 1.1.2.26 some strong optimizations but requires more time and memory. */
209 salcianu 1.1.2.29 public static boolean LOOP_SENSITIVE = false;
210 salcianu 1.1.2.26
211 salcianu 1.1.2.61 /** Array elements are modeled as fields of the array object, all of them
212 salcianu 1.1.2.61 with the same name since the analysis is not able to make the
213 salcianu 1.1.2.61 distinction between the fields.
214 salcianu 1.1.2.61 this name is supposed to be "as impossible as possible", so that we
215 salcianu 1.1.2.61 don't have any conflict with real fields. */
216 salcianu 1.1.2.38 public static final String ARRAY_CONTENT = "+ae+";
217 salcianu 1.1.2.1
218 salcianu 1.21 // Remove unreachable nodes
219 salcianu 1.1.2.75 public static final boolean DO_INTRA_PROC_TRIMMING = false;
220 salcianu 1.1.2.72
221 salcianu 1.1.2.81 // meta call graph
222 salcianu 1.1.2.81 private MetaCallGraph mcg;
223 salcianu 1.1.2.83 /** Returns the call graph graph used by <code>this</code>
224 salcianu 1.1.2.83 <code>PointerAnalysis</code> object. */
225 salcianu 1.1.2.25 public final MetaCallGraph getMetaCallGraph() { return mcg; }
226 salcianu 1.1.2.81
227 salcianu 1.1.2.81 // meta all callers
228 salcianu 1.1.2.81 private MetaAllCallers mac;
229 salcianu 1.1.2.83 /** Returns the all callers graph used by <code>this</code>
230 salcianu 1.1.2.83 <code>PointerAnalysis</code> object. */
231 salcianu 1.1.2.56 public final MetaAllCallers getMetaAllCallers() { return mac; }
232 salcianu 1.1.2.1
233 salcianu 1.1.2.83 // the factory that generates the SCC LBB representation (ie
234 salcianu 1.1.2.83 // strongly connected components of the light basic blocks of
235 salcianu 1.1.2.83 // quads) for the code of a method.
236 salcianu 1.1.2.83 private final CachingSCCLBBFactory scc_lbb_factory;
237 salcianu 1.1.2.83 /** Returns the SCC LBB factory used by <code>this</code>
238 salcianu 1.1.2.83 <code>PointerAnalysis</code> object. */
239 salcianu 1.1.2.83 public final CachingSCCLBBFactory getCachingSCCLBBFactory() {
240 salcianu 1.1.2.83 return scc_lbb_factory;
241 salcianu 1.1.2.83 }
242 salcianu 1.1.2.83
243 salcianu 1.1.2.81 // linker
244 salcianu 1.1.2.81 public Linker linker;
245 salcianu 1.1.2.81 public final Linker getLinker() { return linker; }
246 salcianu 1.1.2.81
247 salcianu 1.1.2.81
248 rinard 1.1.2.67 private Map hash_proc_interact_int = new HashMap();
249 rinard 1.1.2.67
250 rinard 1.1.2.67 private Map hash_proc_interact_ext = new HashMap();
251 rinard 1.1.2.67
252 salcianu 1.1.2.1 // Maintains the partial points-to and escape information for the
253 salcianu 1.1.2.1 // analyzed methods. This info is successively refined by the fixed
254 salcianu 1.1.2.1 // point algorithm until no further change is possible
255 salcianu 1.1.2.25 // mapping MetaMethod -> ParIntGraph.
256 salcianu 1.1.2.33 private Map hash_proc_int = new HashMap();
257 salcianu 1.1.2.1
258 salcianu 1.1.2.3 // Maintains the external view of the parallel interaction graphs
259 salcianu 1.1.2.3 // attached with the analyzed methods. These "bricks" are used
260 salcianu 1.1.2.3 // for the processing of the CALL nodes.
261 salcianu 1.1.2.25 // Mapping MetaMethod -> ParIntGraph.
262 salcianu 1.1.2.33 private Map hash_proc_ext = new HashMap();
263 salcianu 1.1.2.3
264 salcianu 1.21 /** Creates a <code>PointerAnalysis</code> object.
265 salcianu 1.1.2.61 *
266 salcianu 1.1.2.75 * @param mcg The (meta) Call Graph that models the caller-callee
267 salcianu 1.1.2.61 * relation between methods.
268 salcianu 1.1.2.61 * @param lbbconv The producer of the (Light) Basic Block representation
269 salcianu 1.1.2.61 * of a method body.
270 salcianu 1.1.2.61 *
271 salcianu 1.1.2.3 *</ul> */
272 salcianu 1.9 public PointerAnalysis(MetaCallGraph mcg,
273 salcianu 1.1.2.83 CachingSCCLBBFactory caching_scc_lbb_factory,
274 salcianu 1.12 Linker linker, ClassHierarchy ch) {
275 salcianu 1.1.2.75 this.mcg = mcg;
276 salcianu 1.9 this.mac = new MetaAllCallers(mcg);
277 salcianu 1.1.2.83 this.scc_lbb_factory = caching_scc_lbb_factory;
278 salcianu 1.1.2.83 // OLD STUFF: new CachingSCCLBBFactory(lbbconv);
279 salcianu 1.1.2.81 this.linker = linker;
280 salcianu 1.12 this.nodes = new NodeRepository(linker);
281 salcianu 1.12
282 salcianu 1.12 PointerAnalysis.ch = ch;
283 salcianu 1.12 PointerAnalysis.java_lang_Object = linker.forName("java.lang.Object");
284 salcianu 1.1.2.81
285 salcianu 1.1.2.82 InterProcPA.static_init(this);
286 salcianu 1.1.2.1 }
287 salcianu 1.1.2.1
288 salcianu 1.12 static ClassHierarchy ch = null;
289 salcianu 1.12 static HClass java_lang_Object = null;
290 salcianu 1.12
291 salcianu 1.1.2.61 // the set of already analyzed meta-methods
292 salcianu 1.20 private Set aamm = SAVE_MEMORY ? new HashSet() : null;
293 salcianu 1.1.2.61
294 salcianu 1.12 /** Returns the full (internal) <code>ParIntGraph</code> attached
295 salcianu 1.12 to the method <code>hm</code> i.e. the graph at the end of the
296 salcianu 1.12 method. If <code>mm</code> was not analyzed yet and
297 salcianu 1.12 <code>analyze</code> is true, analyze <code>mm</code> (and
298 salcianu 1.12 store the result of the analysis in the internal cache). May
299 salcianu 1.12 return <code>null</code> if <code>mm</code> is unanalyzable,
300 salcianu 1.12 or if it has not been analyzed yet and <code>analyze</code> is
301 salcianu 1.12 false. */
302 salcianu 1.12 public ParIntGraph getIntParIntGraph(MetaMethod mm, boolean analyze) {
303 salcianu 1.1.2.79 if(SAVE_MEMORY) {
304 salcianu 1.12 if(!aamm.contains(mm)) {
305 salcianu 1.12 if(!analyze) return null;
306 salcianu 1.1.2.61 analyze(mm);
307 salcianu 1.12 }
308 salcianu 1.1.2.61 analyze_intra_proc(mm);
309 salcianu 1.12 ParIntGraph pig = (ParIntGraph) hash_proc_int.get(mm);
310 salcianu 1.1.2.61 hash_proc_int.clear();
311 salcianu 1.1.2.61 return pig;
312 salcianu 1.1.2.61 }
313 salcianu 1.1.2.79 else {
314 salcianu 1.1.2.81 ParIntGraph pig = (ParIntGraph) hash_proc_int.get(mm);
315 salcianu 1.12 if((pig == null) && analyze) {
316 salcianu 1.1.2.61 analyze(mm);
317 salcianu 1.1.2.81 pig = (ParIntGraph) hash_proc_int.get(mm);
318 salcianu 1.1.2.61 }
319 salcianu 1.1.2.61 return pig;
320 salcianu 1.1.2.15 }
321 salcianu 1.1.2.1 }
322 salcianu 1.1.2.1
323 salcianu 1.12 /** Equivalent to
324 salcianu 1.12 <code>getIntParIntGraph</code>(<code>mm</code>,<code>true</code>). */
325 salcianu 1.12 public ParIntGraph getIntParIntGraph(MetaMethod mm) {
326 salcianu 1.12 return getIntParIntGraph(mm, true);
327 salcianu 1.12 }
328 salcianu 1.10
329 salcianu 1.12 /** That's what you probably want: equivalent to
330 salcianu 1.12 <code>getIntParIntGraph(new MetaMethod(hm, true))</code>. */
331 salcianu 1.10 public ParIntGraph getIntParIntGraph(HMethod hm) {
332 salcianu 1.10 return getIntParIntGraph(new MetaMethod(hm, true));
333 salcianu 1.10 }
334 salcianu 1.10
335 salcianu 1.1.2.3 /** Returns the simplified (external) <code>ParIntGraph</code> attached to
336 salcianu 1.1.2.3 * the method <code>hm</code> i.e. the graph at the end of the method.
337 salcianu 1.1.2.3 * of which only the parts reachable from the exterior (via parameters,
338 salcianu 1.1.2.7 * returned objects or static classes) have been preserved. The escape
339 salcianu 1.1.2.7 * function do not consider the parameters of the function (anyway, this
340 salcianu 1.1.2.7 * graph is supposed to be inlined into the graph of the caller, so the
341 salcianu 1.1.2.7 * parameters will disappear anyway).
342 salcianu 1.1.2.3 * Returns <code>null</code> if no such graph is available. */
343 salcianu 1.1.2.25 public ParIntGraph getExtParIntGraph(MetaMethod mm){
344 salcianu 1.1.2.75 return getExtParIntGraph(mm, true);
345 salcianu 1.1.2.15 }
346 salcianu 1.1.2.15
347 salcianu 1.10 public ParIntGraph getExtParIntGraph(HMethod hm) {
348 salcianu 1.10 return getExtParIntGraph(new MetaMethod(hm, true));
349 salcianu 1.10 }
350 salcianu 1.10
351 salcianu 1.1.2.34 // internal method doing the job
352 salcianu 1.1.2.34 ParIntGraph getExtParIntGraph(MetaMethod mm, boolean compute_it){
353 salcianu 1.1.2.63 ParIntGraph pig = (ParIntGraph) hash_proc_ext.get(mm);
354 salcianu 1.1.2.34 if((pig == null) && compute_it){
355 salcianu 1.1.2.34 analyze(mm);
356 salcianu 1.1.2.34 pig = (ParIntGraph)hash_proc_ext.get(mm);
357 salcianu 1.1.2.34 }
358 salcianu 1.1.2.34 return pig;
359 salcianu 1.1.2.34 }
360 salcianu 1.1.2.23
361 salcianu 1.1.2.27 // Returns a version of the external graph for meta-method hm that is
362 salcianu 1.1.2.23 // specialized for the call site q
363 salcianu 1.1.2.25 ParIntGraph getSpecializedExtParIntGraph(MetaMethod mm, CALL q){
364 salcianu 1.1.2.23 // first, search in the cache
365 salcianu 1.1.2.27 Map map_mm = (Map) cs_specs.get(mm);
366 salcianu 1.1.2.25 if(map_mm == null){
367 salcianu 1.1.2.33 map_mm = new HashMap();
368 salcianu 1.1.2.27 cs_specs.put(mm,map_mm);
369 salcianu 1.1.2.23 }
370 salcianu 1.1.2.27 ParIntGraph pig = (ParIntGraph) map_mm.get(q);
371 salcianu 1.1.2.27 if(pig != null) return pig;
372 salcianu 1.1.2.23
373 salcianu 1.1.2.23 // if the specialization was not already in the cache,
374 salcianu 1.1.2.23 // try to recover the original ParIntGraph (if it exists) and
375 salcianu 1.1.2.23 // specialize it
376 salcianu 1.1.2.23
377 salcianu 1.1.2.25 ParIntGraph original_pig = getExtParIntGraph(mm);
378 salcianu 1.1.2.23 if(original_pig == null) return null;
379 salcianu 1.1.2.23
380 salcianu 1.1.2.42 ParIntGraph new_pig = original_pig.csSpecialize(q);
381 salcianu 1.1.2.61
382 salcianu 1.1.2.61 if(!SAVE_MEMORY)
383 salcianu 1.21 map_mm.put(q, new_pig);
384 salcianu 1.1.2.23
385 salcianu 1.1.2.23 return new_pig;
386 salcianu 1.1.2.23 }
387 salcianu 1.1.2.27 // cache for call site sensitivity: Map<MetaMethod, Map<CALL,ParIntGraph>>
388 salcianu 1.1.2.33 private Map cs_specs = new HashMap();
389 salcianu 1.1.2.27
390 salcianu 1.1.2.27
391 salcianu 1.1.2.27 // Returns a specialized version of the external graph for meta-method mm;
392 salcianu 1.1.2.27 // mm is supposed to be the run method (the body) of a thread.
393 salcianu 1.1.2.27 ParIntGraph getSpecializedExtParIntGraph(MetaMethod mm){
394 salcianu 1.1.2.64
395 salcianu 1.1.2.27 ParIntGraph pig = (ParIntGraph) t_specs.get(mm);
396 salcianu 1.1.2.27 if(pig != null) return pig;
397 salcianu 1.1.2.27
398 salcianu 1.1.2.27 // if the specialization was not already in the cache,
399 salcianu 1.1.2.27 // try to recover the original ParIntGraph (if it exists) and
400 salcianu 1.1.2.27 // specialize it
401 salcianu 1.1.2.27
402 salcianu 1.1.2.27 ParIntGraph original_pig = getExtParIntGraph(mm);
403 salcianu 1.1.2.27 if(original_pig == null) return null;
404 salcianu 1.1.2.27
405 salcianu 1.1.2.27 ParIntGraph new_pig = null;
406 salcianu 1.1.2.27 if(THREAD_SENSITIVE)
407 salcianu 1.1.2.27 new_pig = original_pig.tSpecialize(mm);
408 salcianu 1.1.2.27 else
409 salcianu 1.1.2.27 if(WEAKLY_THREAD_SENSITIVE)
410 salcianu 1.1.2.42 new_pig = original_pig.wtSpecialize(mm);
411 cananian 1.3.2.1 else assert false : "The thread specialization is off!";
412 salcianu 1.1.2.27
413 salcianu 1.1.2.27 t_specs.put(mm,new_pig);
414 salcianu 1.1.2.27
415 salcianu 1.1.2.27 return new_pig;
416 salcianu 1.1.2.27 }
417 salcianu 1.1.2.27 // cache for thread sensitivity: Map<MetaMethod, ParIntGraph>
418 salcianu 1.1.2.33 private Map t_specs = new HashMap();
419 salcianu 1.1.2.27
420 salcianu 1.1.2.3
421 salcianu 1.1.2.3 /** Returns the parameter nodes of the method <code>hm</code>. This is
422 salcianu 1.1.2.3 * useful for the understanding of the <code>ParIntGraph</code> attached
423 salcianu 1.1.2.3 * to <code>hm</code> */
424 salcianu 1.1.2.25 public PANode[] getParamNodes(MetaMethod mm){
425 salcianu 1.1.2.25 return nodes.getAllParams(mm);
426 salcianu 1.1.2.2 }
427 salcianu 1.1.2.2
428 salcianu 1.1.2.15 /** Returns the parallel interaction graph for the end of the method
429 salcianu 1.1.2.15 <code>hm</code>. The interactions between <code>hm</code> and the
430 salcianu 1.1.2.15 threads it (transitively) starts are analyzed in order to
431 salcianu 1.1.2.15 "recover" some of the escaped nodes.<br>
432 salcianu 1.1.2.15 See Section 10 <i>Inter-thread Analysis</i> in the original paper of
433 salcianu 1.1.2.15 Martin and John Whaley for more details. */
434 salcianu 1.1.2.25 public ParIntGraph threadInteraction(MetaMethod mm){
435 salcianu 1.1.2.62 System.out.println("threadInteraction for " + mm);
436 salcianu 1.1.2.25 ParIntGraph pig = (ParIntGraph) getIntParIntGraph(mm);
437 salcianu 1.1.2.81 if(pig == null)
438 salcianu 1.1.2.81 return null;
439 salcianu 1.1.2.59 return InterThreadPA.resolve_threads(this, pig);
440 salcianu 1.1.2.15 }
441 rinard 1.1.2.67
442 rinard 1.1.2.67 private ParIntGraph threadExtInteraction(MetaMethod mm){
443 rinard 1.1.2.67 System.out.println("threadExtInteraction for " + mm);
444 rinard 1.1.2.67
445 rinard 1.1.2.67 ParIntGraph pig = (ParIntGraph) getIntThreadInteraction(mm);
446 salcianu 1.21 boolean is_main = mm.getHMethod().getName().equals("main");
447 salcianu 1.21 ParIntGraph shrinked_graph =
448 salcianu 1.21 pig.keepTheEssential(getParamNodes(mm), is_main);
449 salcianu 1.1.2.81
450 salcianu 1.1.2.81 // We try to correct some imprecisions in the analysis:
451 salcianu 1.1.2.81 // 1. if the meta-method is not returning an Object, clear
452 salcianu 1.1.2.81 // the return set of the shrinked_graph
453 salcianu 1.1.2.81 HMethod hm = mm.getHMethod();
454 salcianu 1.1.2.81 if(hm.getReturnType().isPrimitive())
455 salcianu 1.1.2.81 shrinked_graph.G.r.clear();
456 salcianu 1.1.2.81 // 2. if the meta-method doesn't throw any exception,
457 salcianu 1.1.2.81 // clear the exception set of the shrinked_graph.
458 salcianu 1.1.2.81 if(hm.getExceptionTypes().length == 0)
459 salcianu 1.1.2.81 shrinked_graph.G.excp.clear();
460 salcianu 1.1.2.81 return(shrinked_graph);
461 rinard 1.1.2.67 }
462 rinard 1.1.2.67
463 rinard 1.1.2.67 public ParIntGraph getExtThreadInteraction(MetaMethod mm){
464 rinard 1.1.2.67 ParIntGraph pig = (ParIntGraph)hash_proc_interact_ext.get(mm);
465 rinard 1.1.2.67 if(pig == null){
466 rinard 1.1.2.67 pig = threadExtInteraction(mm);
467 rinard 1.1.2.67 hash_proc_interact_ext.put(mm, pig);
468 rinard 1.1.2.67 }
469 rinard 1.1.2.67 return pig;
470 rinard 1.1.2.67 }
471 rinard 1.1.2.67
472 rinard 1.1.2.67 public ParIntGraph getIntThreadInteraction(MetaMethod mm){
473 salcianu 1.1.2.81 ParIntGraph pig = (ParIntGraph) hash_proc_interact_int.get(mm);
474 rinard 1.1.2.67 if(pig == null){
475 salcianu 1.1.2.75 pig = threadInteraction(mm);
476 rinard 1.1.2.67 hash_proc_interact_int.put(mm, pig);
477 rinard 1.1.2.67 }
478 rinard 1.1.2.67 return pig;
479 rinard 1.1.2.67 }
480 rinard 1.1.2.67
481 salcianu 1.1.2.25 // Worklist of <code>MetaMethod</code>s for the inter-procedural analysis
482 salcianu 1.12 private PAWorkList W_inter_proc = new PAWorkList();
483 salcianu 1.1.2.1
484 salcianu 1.1.2.1 // Worklist for the intra-procedural analysis; at any moment, it
485 salcianu 1.1.2.1 // contains only basic blocks from the same method.
486 salcianu 1.1.2.1 private PAWorkList W_intra_proc = new PAWorkList();
487 salcianu 1.1.2.1
488 salcianu 1.1.2.20 // Repository for node management.
489 salcianu 1.12 static NodeRepository nodes = null;
490 salcianu 1.1.2.81 public final NodeRepository getNodeRepository() { return nodes; }
491 salcianu 1.1.2.1
492 salcianu 1.1.2.64
493 salcianu 1.1.2.64 // Navigator for the mmethod SCC building phase. The code is complicated
494 salcianu 1.1.2.64 // by the fact that we are interested only in yet unexplored methods
495 salcianu 1.1.2.64 // (i.e. whose parallel interaction graphs are not yet in the cache).
496 salcianu 1.11 class MM_Navigator implements Navigator, java.io.Serializable {
497 salcianu 1.1.2.80 public Object[] next(Object node){
498 salcianu 1.4 MetaMethod[] mms = mcg.getCallees((MetaMethod) node);
499 salcianu 1.1.2.80 MetaMethod[] mms2 = get_new_mmethods(mms);
500 salcianu 1.1.2.80 return mms2;
501 salcianu 1.1.2.80 }
502 salcianu 1.1.2.80
503 salcianu 1.1.2.80 public Object[] prev(Object node){
504 salcianu 1.4 MetaMethod[] mms = mac.getCallers((MetaMethod) node);
505 salcianu 1.1.2.80 MetaMethod[] mms2 = get_new_mmethods(mms);
506 salcianu 1.1.2.80 return mms2;
507 salcianu 1.1.2.80 }
508 salcianu 1.1.2.80
509 salcianu 1.1.2.80 // selects only the (yet) unanalyzed methods
510 salcianu 1.1.2.80 private MetaMethod[] get_new_mmethods(MetaMethod[] mms){
511 salcianu 1.1.2.80 int count = 0;
512 salcianu 1.1.2.80 boolean good[] = new boolean[mms.length];
513 salcianu 1.1.2.80 for(int i = 0 ; i < mms.length ; i++)
514 salcianu 1.1.2.80 if(!hash_proc_ext.containsKey(mms[i])){
515 salcianu 1.1.2.80 good[i] = true;
516 salcianu 1.1.2.80 count++;
517 salcianu 1.1.2.64 }
518 salcianu 1.1.2.80 else
519 salcianu 1.1.2.80 good[i] = false;
520 salcianu 1.1.2.80
521 salcianu 1.1.2.80 MetaMethod[] new_mms = new MetaMethod[count];
522 salcianu 1.1.2.80 int j = 0;
523 salcianu 1.1.2.80 for(int i = 0 ; i < mms.length ; i++)
524 salcianu 1.1.2.80 if(good[i])
525 salcianu 1.1.2.80 new_mms[j++] = mms[i];
526 salcianu 1.1.2.80 return new_mms;
527 salcianu 1.1.2.80 }
528 salcianu 1.1.2.80 };
529 salcianu 1.1.2.80
530 salcianu 1.11 private Navigator mm_navigator = new MM_Navigator();
531 salcianu 1.1.2.80
532 salcianu 1.1.2.64
533 salcianu 1.1.2.64
534 salcianu 1.1.2.1 // Top-level procedure for the analysis. Receives the main method as
535 salcianu 1.1.2.75 // parameter.
536 salcianu 1.1.2.25 private void analyze(MetaMethod mm){
537 salcianu 1.1.2.75 //if(DEBUG)
538 salcianu 1.1.2.56 System.out.println("ANALYZE: " + mm);
539 salcianu 1.1.2.9
540 salcianu 1.1.2.64 long begin_time = TIMING ? System.currentTimeMillis() : 0;
541 salcianu 1.1.2.16
542 salcianu 1.1.2.9 if(DEBUG)
543 salcianu 1.20 System.out.println("Creating method SCCs");
544 salcianu 1.1.2.9
545 salcianu 1.1.2.25 // SCComponent.DETERMINISTIC = DETERMINISTIC;
546 salcianu 1.1.2.14
547 salcianu 1.18 // topologically sorted groups of mutually recursive methods
548 salcianu 1.18 // (the edges model the caller-callee interaction).
549 salcianu 1.19 TopSortedCompDiGraph<MetaMethod> ts_mmethods =
550 salcianu 1.18 new TopSortedCompDiGraph(Collections.singleton(mm), mm_navigator);
551 salcianu 1.1.2.9
552 salcianu 1.1.2.64 if(DEBUG_SCC || TIMING)
553 salcianu 1.18 Debug.display_mm_sccs(ts_mmethods, mcg,
554 salcianu 1.18 System.currentTimeMillis() - begin_time);
555 salcianu 1.1.2.9
556 salcianu 1.19 for(SCComponent scc : ts_mmethods.incrOrder()) {
557 salcianu 1.1.2.9 analyze_inter_proc_scc(scc);
558 salcianu 1.1.2.61
559 salcianu 1.1.2.77 if(SAVE_MEMORY) {
560 salcianu 1.20 for(Object mmethod : scc.nodes())
561 salcianu 1.20 aamm.add((MetaMethod) mmethod);
562 salcianu 1.1.2.77 }
563 salcianu 1.1.2.9 }
564 salcianu 1.1.2.16
565 salcianu 1.1.2.16 if(TIMING)
566 salcianu 1.1.2.25 System.out.println("analyze(" + mm + ") finished in " +
567 salcianu 1.1.2.21 (System.currentTimeMillis() - begin_time) + "ms");
568 salcianu 1.20 }
569 salcianu 1.1.2.64
570 salcianu 1.1.2.9 // inter-procedural analysis of a group of mutually recursive methods
571 salcianu 1.20 private void analyze_inter_proc_scc(SCComponent scc) {
572 salcianu 1.12 if(TIMING || DEBUG) {
573 salcianu 1.1.2.28 System.out.print("SCC" + scc.getId() +
574 salcianu 1.1.2.64 "\t (" + scc.size() + " meta-method(s)){");
575 salcianu 1.20 for(Object mm0 : scc.nodes())
576 salcianu 1.20 System.out.print("\n " + ((MetaMethod) mm0));
577 salcianu 1.1.2.28 System.out.print("} ... ");
578 salcianu 1.1.2.28 }
579 salcianu 1.1.2.28
580 salcianu 1.1.2.64 long b_time = TIMING ? System.currentTimeMillis() : 0;
581 salcianu 1.1.2.28
582 salcianu 1.1.2.9 // if SCC composed of a native or abstract method, return immediately!
583 salcianu 1.21 if(!analyzable(((MetaMethod) scc.nodes().iterator().next())
584 salcianu 1.21 .getHMethod())) {
585 salcianu 1.1.2.64 if(TIMING)
586 salcianu 1.12 System.out.println((System.currentTimeMillis() - b_time) +
587 salcianu 1.12 "ms + (unanalyzable)");
588 salcianu 1.1.2.9 return;
589 salcianu 1.1.2.9 }
590 salcianu 1.1.2.64
591 salcianu 1.14 // add only the "exit" methods to the worklist (methods that
592 salcianu 1.14 // call methods from outside their SCC); the other methods
593 salcianu 1.14 // will be eventually added by the fixed point alg.
594 salcianu 1.21 if(scc.exits().length != 0) {
595 salcianu 1.21 for(Object exit : scc.exits())
596 salcianu 1.21 W_inter_proc.add(exit);
597 salcianu 1.21 }
598 salcianu 1.21 else // special case: leaf SCC -> add all
599 salcianu 1.21 W_inter_proc.addAll(scc.nodes());
600 salcianu 1.1.2.9
601 salcianu 1.12 while(!W_inter_proc.isEmpty()) {
602 salcianu 1.1.2.1 // grab a method from the worklist
603 salcianu 1.1.2.25 MetaMethod mm_work = (MetaMethod) W_inter_proc.remove();
604 salcianu 1.1.2.1
605 salcianu 1.12 //if(DEBUG_INTRA)
606 salcianu 1.20 Debug.print_method_stats(mm_work, scc_lbb_factory);
607 salcianu 1.12
608 salcianu 1.1.2.25 ParIntGraph old_info = (ParIntGraph) hash_proc_ext.get(mm_work);
609 salcianu 1.1.2.25 analyze_intra_proc(mm_work);
610 salcianu 1.1.2.25 ParIntGraph new_info = (ParIntGraph) hash_proc_ext.get(mm_work);
611 salcianu 1.1.2.1
612 salcianu 1.20 if(scc.isLoop()) {
613 salcianu 1.12 if(REUSE_LOAD_NODES && (old_info != null)) {
614 salcianu 1.12 new_info.join(old_info);
615 salcianu 1.12 hash_proc_ext.put(mm_work, new_info);
616 salcianu 1.1.2.14 }
617 salcianu 1.12
618 salcianu 1.12 if(!new_info.equals(old_info)) { // new info?
619 salcianu 1.12
620 salcianu 1.12 System.out.println("HAS CHANGED!");
621 salcianu 1.12
622 salcianu 1.12 // since the original graph associated with
623 salcianu 1.12 // hm_work changed, the old specializations for it
624 salcianu 1.12 // are no longer actual;
625 salcianu 1.12 if(CALL_CONTEXT_SENSITIVE)
626 salcianu 1.12 cs_specs.remove(mm_work);
627 salcianu 1.12
628 salcianu 1.12 Object[] mms = mac.getCallers(mm_work);
629 salcianu 1.20 if(DETERMINISTIC)
630 salcianu 1.20 Arrays.sort(mms, UComp.uc);
631 salcianu 1.12 for(int i = 0; i < mms.length ; i++) {
632 salcianu 1.12 MetaMethod mm_caller = (MetaMethod) mms[i];
633 salcianu 1.12 if(scc.contains(mm_caller))
634 salcianu 1.12 W_inter_proc.add(mm_caller);
635 salcianu 1.12 }
636 salcianu 1.1.2.8 }
637 salcianu 1.12 else
638 salcianu 1.12 System.out.println("HAS NOT CHANGED!");
639 salcianu 1.1.2.1 }
640 salcianu 1.1.2.1 }
641 salcianu 1.1.2.9
642 salcianu 1.12 if(COMPRESS_LOST_NODES && !AGGRESSIVE_COMPRESS_LOST_NODES)
643 salcianu 1.12 post_compress(scc);
644 salcianu 1.12
645 salcianu 1.1.2.76 // clear various data structures to save some memory space
646 salcianu 1.12 analyze_inter_proc_scc_clean(scc);
647 salcianu 1.1.2.76
648 salcianu 1.1.2.76 if(TIMING)
649 salcianu 1.1.2.76 System.out.println((System.currentTimeMillis() - b_time) + "ms");
650 salcianu 1.1.2.76 }
651 salcianu 1.1.2.76
652 salcianu 1.12
653 salcianu 1.12 private void post_compress(SCComponent scc) {
654 salcianu 1.21 for(Object mm0 : scc.nodes()) {
655 salcianu 1.21 MetaMethod mm = (MetaMethod) mm0;
656 salcianu 1.12
657 salcianu 1.12 PANode[] nodes = getParamNodes(mm);
658 salcianu 1.12 ParIntGraph pig = (ParIntGraph) hash_proc_ext.get(mm);
659 salcianu 1.12
660 salcianu 1.12 hash_proc_ext.put
661 salcianu 1.13 (mm, pig.compressLostNodes(getLostNodes(mm)));
662 salcianu 1.12 }
663 salcianu 1.12 }
664 salcianu 1.20
665 salcianu 1.12
666 salcianu 1.1.2.76 // clean work data structs used by analyze_inter_proc_scc
667 salcianu 1.12 private void analyze_inter_proc_scc_clean(SCComponent scc) {
668 salcianu 1.21 // 1. get rid of the cache from the scc_lbb factory; anyway,
669 salcianu 1.21 // it is useless, since scc's methods are never reanalyzed.
670 salcianu 1.1.2.33 scc_lbb_factory.clear();
671 salcianu 1.1.2.41 // 2. the meta methods of this SCC will never be revisited, so the
672 salcianu 1.1.2.25 // specializations generated for the call sites inside them are not
673 salcianu 1.1.2.25 // usefull any more
674 salcianu 1.1.2.26 if(CALL_CONTEXT_SENSITIVE)
675 salcianu 1.1.2.27 cs_specs.clear();
676 salcianu 1.12 // 3. to save memory, the cache of "internal" graphs can be flushed
677 salcianu 1.20 // If necessary, these graphs can be reconstructed.
678 salcianu 1.12 if(SAVE_MEMORY) {
679 salcianu 1.1.2.61 System.out.println("hash_proc_int cleared!");
680 salcianu 1.1.2.61 hash_proc_int.clear();
681 salcianu 1.1.2.61 }
682 salcianu 1.1.2.1 }
683 salcianu 1.1.2.1
684 salcianu 1.1.2.44 private MetaMethod current_intra_mmethod = null;
685 salcianu 1.1.2.44 private ParIntGraph initial_pig = null;
686 salcianu 1.1.2.1
687 salcianu 1.6 private void analyze_intra_proc(MetaMethod mm) {
688 salcianu 1.21 _analyze_intra_proc(mm);
689 salcianu 1.21 // clear the LightBasicBlock -> ParIntGraph mapping
690 salcianu 1.21 lbb2pp.clear();
691 salcianu 1.6 }
692 salcianu 1.6
693 salcianu 1.6 // Performs the intra-procedural pointer analysis of method mm.
694 salcianu 1.21 private void _analyze_intra_proc(MetaMethod mm) {
695 salcianu 1.1.2.76 long b_time = System.currentTimeMillis();
696 salcianu 1.12 if(FINE_TIMING) reset_fine_timing();
697 salcianu 1.1.2.71
698 salcianu 1.1.2.25 current_intra_mmethod = mm;
699 salcianu 1.1.2.1
700 salcianu 1.1.2.9 // cut the method into SCCs of basic blocks
701 salcianu 1.19 TopSortedCompDiGraph<LightBasicBlock> ts_sccs =
702 salcianu 1.18 scc_lbb_factory.computeSCCLBB(mm.getHMethod());
703 salcianu 1.1.2.25
704 salcianu 1.20 if(DEBUG2 || MEGA_DEBUG)
705 salcianu 1.20 Debug.show_lbb_scc(mm, ts_sccs);
706 salcianu 1.20 if(STATS)
707 salcianu 1.20 Stats.record_mmethod_pass(mm, ts_sccs);
708 salcianu 1.1.2.9
709 salcianu 1.1.2.9 // construct the ParIntGraph at the beginning of the method
710 salcianu 1.20 initial_pig = get_mmethod_initial_pig(mm, ts_sccs);
711 salcianu 1.20 // propagate the information down the CFG
712 salcianu 1.19 for(SCComponent scc : ts_sccs.decrOrder())
713 salcianu 1.19 analyze_intra_proc_scc(scc);
714 salcianu 1.1.2.47
715 salcianu 1.20 if(FINE_TIMING) show_fine_timing(b_time);
716 salcianu 1.12 }
717 salcianu 1.12
718 salcianu 1.21
719 salcianu 1.21 Map/*<LightBasicBlock,ParIntGraphPair>*/ lbb2pp = new HashMap();
720 salcianu 1.21 private ParIntGraphPair getPIGPair(LightBasicBlock lbb) {
721 salcianu 1.21 return (ParIntGraphPair) lbb2pp.get(lbb);
722 salcianu 1.21 }
723 salcianu 1.21 private void putPIGPair(LightBasicBlock lbb, ParIntGraphPair pp) {
724 salcianu 1.21 lbb2pp.put(lbb, pp);
725 salcianu 1.21 }
726 salcianu 1.12
727 salcianu 1.12 private static void reset_fine_timing() {
728 salcianu 1.12 InterProcPA.total_interproc_time = 0;
729 salcianu 1.12 InterProcPA.total_mapping_time = 0;
730 salcianu 1.12 InterProcPA.total_merging_time = 0;
731 salcianu 1.12 InterProcPA.total_propagate_time = 0;
732 salcianu 1.12 InterProcPA.total_cleaning_time = 0;
733 salcianu 1.12 ParIntGraph.total_cloning_time = 0;
734 salcianu 1.12 ParIntGraph.total_equals_time = 0;
735 salcianu 1.12 ParIntGraph.total_join_time = 0;
736 salcianu 1.12 intra_join = 0;
737 salcianu 1.1.2.9 }
738 salcianu 1.12 private static long intra_join = 0;
739 salcianu 1.12
740 salcianu 1.20 private static void show_fine_timing(long b_time) {
741 salcianu 1.20 long delta = System.currentTimeMillis() - b_time;
742 salcianu 1.20 System.out.println
743 salcianu 1.20 ("Analysis time: " + delta + " ms\n" +
744 salcianu 1.21 "(intra: " + (delta - InterProcPA.total_interproc_time) +
745 salcianu 1.21 " inter: " + InterProcPA.total_interproc_time +
746 salcianu 1.20 " (map: " + InterProcPA.total_mapping_time +
747 salcianu 1.20 " mrg: " + InterProcPA.total_merging_time +
748 salcianu 1.20 " ppg: " + InterProcPA.total_propagate_time +
749 salcianu 1.20 " cln: " + InterProcPA.total_cleaning_time + ")" +
750 salcianu 1.20 " clone: " + ParIntGraph.total_cloning_time +
751 salcianu 1.20 " equals: " + ParIntGraph.total_equals_time +
752 salcianu 1.20 " join: " + ParIntGraph.total_join_time + " / " +
753 salcianu 1.20 intra_join + ")\n");
754 salcianu 1.20 }
755 salcianu 1.20
756 salcianu 1.12
757 salcianu 1.12 // DEBUG
758 salcianu 1.12 private Map/*<LightBasicBlock,Integer>*/ lbb2passes = null;
759 salcianu 1.1.2.9
760 salcianu 1.1.2.9 // Intra-procedural analysis of a strongly connected component of
761 salcianu 1.1.2.9 // basic blocks.
762 salcianu 1.1.2.9 private void analyze_intra_proc_scc(SCComponent scc){
763 salcianu 1.12 if(MEGA_DEBUG) {
764 salcianu 1.12 lbb2passes = new HashMap();
765 salcianu 1.20 for(Object lbb : scc.nodes())
766 salcianu 1.20 lbb2passes.put(lbb, new Integer(0));
767 salcianu 1.12 }
768 salcianu 1.12 if(DEBUG2 || MEGA_DEBUG)
769 salcianu 1.1.2.14 System.out.println("\nSCC" + scc.getId());
770 salcianu 1.1.2.14
771 salcianu 1.12 // add only the entry nodes to the worklist; the other basic
772 salcianu 1.12 // blocks will be eventually added too by the fixed point alg.
773 salcianu 1.21 if(scc.entries().length > 0) {
774 salcianu 1.21 for(Object entry : scc.entries())
775 salcianu 1.21 W_intra_proc.add(entry);
776 salcianu 1.21 }
777 salcianu 1.21 else // special case: top SCC; no entries -> add all nodes
778 salcianu 1.21 W_intra_proc.addAll(scc.nodes());
779 salcianu 1.12
780 salcianu 1.12 while(!W_intra_proc.isEmpty()) {
781 salcianu 1.1.2.9 // grab a Basic Block from the worklist
782 salcianu 1.1.2.33 LightBasicBlock lbb_work = (LightBasicBlock) W_intra_proc.remove();
783 salcianu 1.1.2.1
784 salcianu 1.21 ParIntGraphPair old_info = getPIGPair(lbb_work);
785 salcianu 1.21 analyze_basic_block(lbb_work);
786 salcianu 1.21 ParIntGraphPair new_info = getPIGPair(lbb_work);
787 salcianu 1.1.2.9
788 salcianu 1.12 // Some "optimizations" break the monotonicity of the
789 salcianu 1.20 // transfer functions. Make a "join" to restore it.
790 salcianu 1.12 if(REUSE_LOAD_NODES ||
791 salcianu 1.12 (COMPRESS_LOST_NODES && AGGRESSIVE_COMPRESS_LOST_NODES)) {
792 salcianu 1.12 long b_start = System.currentTimeMillis();
793 salcianu 1.12 if(new_info != null)
794 salcianu 1.12 new_info.join(old_info);
795 salcianu 1.12 intra_join += System.currentTimeMillis() - b_start;
796 salcianu 1.12 }
797 salcianu 1.1.2.71
798 salcianu 1.20 if(scc.isLoop()) {
799 salcianu 1.20 if(!ParIntGraphPair.identical(old_info, new_info)) {
800 salcianu 1.12
801 salcianu 1.20 if(MEGA_DEBUG)
802 salcianu 1.20 System.out.println("bb info changed!");
803 salcianu 1.12
804 salcianu 1.20 // yes! The succesors of the analyzed basic block
805 salcianu 1.20 // are potentially "interesting", so they should be added
806 salcianu 1.20 // to the intra-procedural worklist
807 salcianu 1.20 for(LightBasicBlock lbb_next : lbb_work.getNextLBBs()) {
808 salcianu 1.20 if(scc.contains(lbb_next))
809 salcianu 1.20 W_intra_proc.add(lbb_next);
810 salcianu 1.20 }
811 salcianu 1.1.2.14 }
812 salcianu 1.20 else
813 salcianu 1.20 if(MEGA_DEBUG)
814 salcianu 1.20 System.out.println("bb info has not changed!");
815 salcianu 1.1.2.1 }
816 salcianu 1.1.2.1 }
817 salcianu 1.1.2.24
818 salcianu 1.12 lbb2passes = null;
819 salcianu 1.1.2.1 }
820 salcianu 1.1.2.1
821 salcianu 1.1.2.1
822 salcianu 1.1.2.77 // The Parallel Interaction Graph which is updated by the
823 salcianu 1.1.2.77 // <code>analyze_basic_block</code>. This should normally be a
824 salcianu 1.1.2.77 // local variable of that function but it must be also accessible
825 salcianu 1.1.2.77 // to the <code>PAVisitor</code> class.
826 salcianu 1.1.2.33 private ParIntGraph lbbpig = null;
827 salcianu 1.1.2.1
828 salcianu 1.1.2.37 // The pair of ParIntGraphs computed by the inter-procedural analysis
829 salcianu 1.1.2.37 // will be put here.
830 salcianu 1.1.2.37 private ParIntGraphPair call_pp = null;
831 salcianu 1.1.2.37
832 salcianu 1.1.2.1 /** QuadVisitor for the <code>analyze_basic_block</code> */
833 salcianu 1.1.2.80 private class PAVisitor extends QuadVisitor
834 salcianu 1.1.2.80 implements java.io.Serializable {
835 salcianu 1.1.2.1
836 salcianu 1.1.2.44 /** Visit a general quad, other than those explicitly
837 salcianu 1.1.2.44 processed by the other <code>visit</code> methods. */
838 salcianu 1.1.2.1 public void visit(Quad q){
839 salcianu 1.1.2.44 // remove all the edges from the temps that are defined
840 salcianu 1.1.2.44 // by this quad.
841 salcianu 1.1.2.44 Temp[] defs = q.def();
842 salcianu 1.1.2.44 for(int i = 0; i < defs.length; i++)
843 salcianu 1.1.2.44 lbbpig.G.I.removeEdges(defs[i]);
844 salcianu 1.1.2.1 }
845 salcianu 1.1.2.1
846 salcianu 1.1.2.44 public void visit(HEADER q){
847 salcianu 1.1.2.44 // do nothing
848 salcianu 1.1.2.44 }
849 salcianu 1.1.2.44
850 salcianu 1.1.2.44 public void visit(METHOD q){
851 salcianu 1.1.2.44 // do nothing
852 salcianu 1.1.2.44 }
853 salcianu 1.1.2.44
854 salcianu 1.1.2.44
855 salcianu 1.1.2.1 /** Copy statements **/
856 salcianu 1.1.2.1 public void visit(MOVE q){
857 salcianu 1.1.2.33 lbbpig.G.I.removeEdges(q.dst());
858 salcianu 1.1.2.33 Set set = lbbpig.G.I.pointedNodes(q.src());
859 salcianu 1.1.2.33 lbbpig.G.I.addEdges(q.dst(),set);
860 salcianu 1.1.2.1 }
861 salcianu 1.1.2.1
862 salcianu 1.1.2.1
863 salcianu 1.1.2.1 // LOAD STATEMENTS
864 salcianu 1.1.2.1 /** Load statement; normal case */
865 salcianu 1.1.2.1 public void visit(GET q){
866 salcianu 1.1.2.1 Temp l2 = q.objectref();
867 salcianu 1.1.2.1 HField hf = q.field();
868 salcianu 1.1.2.46
869 salcianu 1.1.2.5 // do not analyze loads from non-pointer fields
870 salcianu 1.1.2.5 if(hf.getType().isPrimitive()) return;
871 salcianu 1.1.2.46
872 salcianu 1.1.2.75 if(l2 != null)
873 salcianu 1.12 process_load(q, q.dst(), l2, getFieldName(hf));
874 salcianu 1.12 else
875 salcianu 1.12 process_static_load(q);
876 salcianu 1.12 }
877 salcianu 1.12
878 salcianu 1.12
879 salcianu 1.12 private void process_static_load(GET q) {
880 salcianu 1.12 HField hf = q.field();
881 salcianu 1.12 String f = getFieldName(hf);
882 salcianu 1.12 Temp l = q.dst();
883 salcianu 1.12
884 salcianu 1.14 if(TOPLAS_PAPER) {
885 salcianu 1.14 lbbpig.G.I.removeEdges(l);
886 salcianu 1.14 lbbpig.G.I.addEdge(l, NodeRepository.LOST_SUMMARY);
887 salcianu 1.14 return;
888 salcianu 1.14 }
889 salcianu 1.14
890 salcianu 1.12 PANode static_node =
891 salcianu 1.12 nodes.getStaticNode(hf.getDeclaringClass().getName());
892 salcianu 1.12
893 salcianu 1.12 PANode target =
894 salcianu 1.12 COMPRESS_LOST_NODES ?
895 salcianu 1.12 NodeRepository.LOST_SUMMARY :
896 salcianu 1.12 nodes.getCodeNode(q, PANode.LOAD);
897 salcianu 1.12
898 salcianu 1.12 // set local variable state
899 salcianu 1.12 lbbpig.G.I.removeEdges(l);
900 salcianu 1.12 lbbpig.G.I.addEdge(l, target);
901 salcianu 1.12
902 salcianu 1.12 // add outside edge
903 salcianu 1.12 lbbpig.G.O.addEdge(static_node, f, target);
904 salcianu 1.12 record_load_edge(static_node, f, target);
905 salcianu 1.12
906 salcianu 1.12 // update escape info: set and propagate
907 salcianu 1.12 lbbpig.G.e.addNodeHole(static_node, static_node);
908 salcianu 1.12 lbbpig.G.propagate(Collections.singleton(static_node));
909 salcianu 1.1.2.1 }
910 salcianu 1.12
911 salcianu 1.1.2.1
912 salcianu 1.1.2.12 /** Load statement; special case - arrays. */
913 salcianu 1.4 public void visit(AGET q) {
914 salcianu 1.1.2.47 // AGET from an array of primitive objects (int, float, ...)
915 salcianu 1.4 if(q.type().isPrimitive()) {
916 salcianu 1.11 if(DEBUG2)
917 salcianu 1.1.2.48 System.out.println("NOT-PA RELEVANT AGET: " +
918 salcianu 1.1.2.48 q.getSourceFile() + ":" +
919 salcianu 1.1.2.48 q.getLineNumber() + " " + q);
920 salcianu 1.1.2.48 // not interesting for the pointer analysis
921 salcianu 1.1.2.47 lbbpig.G.I.removeEdges(q.dst());
922 salcianu 1.1.2.48 return;
923 salcianu 1.1.2.48 }
924 salcianu 1.4
925 salcianu 1.1.2.19 // All the elements of an array are collapsed in a single
926 salcianu 1.12 // node, referenced through a conventionally named field
927 salcianu 1.1.2.46 process_load(q, q.dst(), q.objectref(), ARRAY_CONTENT);
928 salcianu 1.1.2.1 }
929 salcianu 1.7
930 salcianu 1.1.2.12 /** Does the real processing of a load statement. */
931 salcianu 1.12 public void process_load(Quad q, Temp l1, Temp l2, String f) {
932 salcianu 1.1.2.33 Set set_aux = lbbpig.G.I.pointedNodes(l2);
933 salcianu 1.12 if(CONSIDER_TYPES)
934 salcianu 1.12 set_aux = selectNodesWithField(set_aux, f);
935 salcianu 1.12
936 salcianu 1.12 lbbpig.G.I.removeEdges(l1);
937 salcianu 1.12
938 salcianu 1.1.2.77 // set_S will contain the nodes that l1 will point to after q
939 salcianu 1.12 Set set_S = new LinearSet(lbbpig.G.I.pointedNodes(set_aux, f));
940 salcianu 1.12 // set_E will contain all the nodes that escape and don't
941 salcianu 1.12 // already have a load point on the f link; we need to
942 salcianu 1.12 // create a new load node iff this set is non-empty
943 salcianu 1.12 Set set_E = new LinearSet();
944 salcianu 1.12
945 cananian 1.17 for(Object nodeO : set_aux) {
946 cananian 1.17 PANode node = (PANode) nodeO;
947 salcianu 1.12
948 salcianu 1.12 if((IGNORE_LOADS_FROM_NATIVES &&
949 salcianu 1.12 ((node.type == PANode.EXCEPT) ||
950 salcianu 1.12 (node.type == PANode.RETURN))) ||
951 salcianu 1.12 // nodes loaded from lost nodes are lost too
952 salcianu 1.12 (COMPRESS_LOST_NODES &&
953 salcianu 1.12 (node == NodeRepository.LOST_SUMMARY))) {
954 salcianu 1.12 lbbpig.G.O.addEdge(node, f, NodeRepository.LOST_SUMMARY);
955 salcianu 1.12 set_S.add(NodeRepository.LOST_SUMMARY);
956 salcianu 1.12 continue;
957 salcianu 1.12 }
958 salcianu 1.12
959 salcianu 1.1.2.77 if(lbbpig.G.e.hasEscaped(node)) {
960 salcianu 1.12 if(REUSE_LOAD_NODES) {
961 salcianu 1.12 Set pointed = lbbpig.G.O.pointedNodes(node, f);
962 salcianu 1.12 if(pointed.isEmpty())
963 salcianu 1.12 set_E.add(node);
964 salcianu 1.12 else {
965 salcianu 1.12 PANode node2 = get_min_node(pointed);
966 salcianu 1.12 set_S.add(node2);
967 salcianu 1.12 record_load_edge(node, f, node2);
968 salcianu 1.12 }
969 salcianu 1.12 }
970 salcianu 1.12 else // always use the load node for this load instruction
971 salcianu 1.1.2.77 set_E.add(node);
972 salcianu 1.1.2.77 }
973 salcianu 1.1.2.1 }
974 salcianu 1.12
975 salcianu 1.12 if(!set_E.isEmpty()) {
976 salcianu 1.12 PANode load_node = nodes.getCodeNode(q, PANode.LOAD);
977 salcianu 1.12 set_S.add(load_node);
978 salcianu 1.12 lbbpig.G.O.addEdges(set_E, f, load_node);
979 salcianu 1.1.2.1 }
980 salcianu 1.1.2.46
981 salcianu 1.1.2.77 lbbpig.G.I.addEdges(l1, set_S);
982 salcianu 1.1.2.77
983 salcianu 1.12 if(!set_E.isEmpty())
984 salcianu 1.12 lbbpig.G.propagate(set_E);
985 salcianu 1.12 }
986 salcianu 1.12
987 salcianu 1.12 // records the load action and its ordering (if necessary)
988 salcianu 1.12 private void record_load_edge(PANode node, String f, PANode node2) {
989 salcianu 1.12 if(RECORD_ACTIONS)
990 salcianu 1.12 lbbpig.ar.add_ld(node, f, node2,
991 salcianu 1.12 ActionRepository.THIS_THREAD,
992 salcianu 1.12 lbbpig.tau.activeThreadSet());
993 salcianu 1.12 if(!IGNORE_EO)
994 salcianu 1.12 lbbpig.eo.add(Collections.singleton(node),
995 salcianu 1.12 f, node2, lbbpig.G.I);
996 salcianu 1.1.2.77 }
997 salcianu 1.1.2.12
998 salcianu 1.1.2.77 // Given a set of PANodes, returns the node having the minimal
999 salcianu 1.1.2.77 // number ID; the set of nodes is guaranteed not to be empty.
1000 salcianu 1.1.2.77 private PANode get_min_node(Set nodes) {
1001 salcianu 1.1.2.77 Iterator it = nodes.iterator();
1002 salcianu 1.1.2.77 PANode retval = (PANode) it.next();
1003 salcianu 1.1.2.77 int min_id = retval.number;
1004 salcianu 1.1.2.77 while(it.hasNext()) {
1005 salcianu 1.1.2.77 PANode node = (PANode) it.next();
1006 salcianu 1.1.2.77 if(node.number < min_id) {
1007 salcianu 1.1.2.77 min_id = node.number;
1008 salcianu 1.1.2.77 retval = node;
1009 salcianu 1.1.2.12 }
1010 salcianu 1.1.2.1 }
1011 salcianu 1.1.2.77 return retval;
1012 salcianu 1.1.2.1 }
1013 salcianu 1.1.2.1
1014 salcianu 1.1.2.1
1015 salcianu 1.1.2.1 // OBJECT CREATION SITES
1016 salcianu 1.1.2.1 /** Object creation sites; normal case */
1017 salcianu 1.7 public void visit(NEW q) {
1018 salcianu 1.7 PANode node = process_new(q, q.dst());
1019 salcianu 1.12 if(TREAT_NULL) {
1020 salcianu 1.12 HField[] fields = q.hclass().getFields();
1021 salcianu 1.12 for(int i = 0; i < fields.length; i++)
1022 salcianu 1.12 if(!fields[i].isStatic())
1023 salcianu 1.12 lbbpig.G.I.addEdge(node, getFieldName(fields[i]),
1024 salcianu 1.12 NodeRepository.NULL_NODE);
1025 salcianu 1.12 }
1026 salcianu 1.1.2.1 }
1027 salcianu 1.1.2.1
1028 salcianu 1.1.2.1 /** Object creation sites; special case - arrays */
1029 salcianu 1.7 public void visit(ANEW q) {
1030 salcianu 1.7 PANode node = process_new(q, q.dst());
1031 salcianu 1.12 if(TREAT_NULL)
1032 salcianu 1.12 lbbpig.G.I.addEdge(node, ARRAY_CONTENT,
1033 salcianu 1.12 NodeRepository.NULL_NODE);
1034 salcianu 1.1.2.1 }
1035 salcianu 1.1.2.1
1036 salcianu 1.7 private PANode process_new(Quad q, Temp tmp) {
1037 salcianu 1.1.2.1 // Kill_I = edges(I,l)
1038 salcianu 1.1.2.1 PANode node = nodes.getCodeNode(q,PANode.INSIDE);
1039 salcianu 1.1.2.33 lbbpig.G.I.removeEdges(tmp);
1040 salcianu 1.1.2.1 // Gen_I = {<l,n>}
1041 salcianu 1.1.2.33 lbbpig.G.I.addEdge(tmp,node);
1042 salcianu 1.7 return node;
1043 salcianu 1.1.2.1 }
1044 salcianu 1.1.2.1
1045 salcianu 1.7 public void visit(CONST q) {
1046 salcianu 1.11 // remove previous edges from q.dst()
1047 salcianu 1.11 lbbpig.G.I.removeEdges(q.dst());
1048 salcianu 1.12 if(TREAT_CONST) {
1049 salcianu 1.12 // if we load a reference to a constant object, make
1050 salcianu 1.12 // q.dst() to point to the corresponding node
1051 salcianu 1.12 if(!q.type().isPrimitive())
1052 salcianu 1.12 lbbpig.G.I.addEdge(q.dst(), nodes.getConstNode(q.value()));
1053 salcianu 1.12 }
1054 salcianu 1.12 }
1055 salcianu 1.12
1056 salcianu 1.12 public void visit(TYPECAST q) {
1057 salcianu 1.12 Temp l = q.objectref();
1058 salcianu 1.12 Set set = lbbpig.G.I.pointedNodes(l);
1059 salcianu 1.12 lbbpig.G.I.removeEdges(l);
1060 salcianu 1.12 lbbpig.G.I.addEdges(l, typeFilter(set, q.hclass()));
1061 salcianu 1.7 }
1062 salcianu 1.7
1063 salcianu 1.12
1064 salcianu 1.1.2.1 /** Return statement: r' = I(l) */
1065 salcianu 1.1.2.1 public void visit(RETURN q){
1066 salcianu 1.1.2.1 Temp tmp = q.retval();
1067 salcianu 1.1.2.1 // return without value; nothing to be done
1068 salcianu 1.1.2.1 if(tmp == null) return;
1069 salcianu 1.1.2.33 Set set = lbbpig.G.I.pointedNodes(tmp);
1070 salcianu 1.1.2.1 // TAKE CARE: r is assumed to be empty before!
1071 salcianu 1.1.2.33 lbbpig.G.r.addAll(set);
1072 salcianu 1.1.2.1 }
1073 salcianu 1.1.2.5
1074 salcianu 1.1.2.5 /** Return statement: r' = I(l) */
1075 salcianu 1.1.2.5 public void visit(THROW q){
1076 salcianu 1.1.2.5 Temp tmp = q.throwable();
1077 salcianu 1.1.2.33 Set set = lbbpig.G.I.pointedNodes(tmp);
1078 salcianu 1.1.2.25 // TAKE CARE: excp is assumed to be empty before!
1079 salcianu 1.1.2.33 lbbpig.G.excp.addAll(set);
1080 salcianu 1.1.2.5 }
1081 salcianu 1.1.2.1
1082 salcianu 1.1.2.1
1083 salcianu 1.1.2.1 // STORE STATEMENTS
1084 salcianu 1.1.2.1 /** Store statements; normal case */
1085 salcianu 1.1.2.1 public void visit(SET q){
1086 salcianu 1.12 Temp l1 = q.objectref();
1087 salcianu 1.12 Temp l2 = q.src();
1088 salcianu 1.1.2.1 HField hf = q.field();
1089 salcianu 1.12
1090 salcianu 1.12 String f = getFieldName(hf);
1091 salcianu 1.12
1092 salcianu 1.1.2.5 // do not analyze stores into non-pointer fields
1093 salcianu 1.1.2.5 if(hf.getType().isPrimitive()) return;
1094 salcianu 1.12
1095 salcianu 1.14 if(l1 == null) // special treatement of the static fields
1096 salcianu 1.14 process_static_store(hf, l2);
1097 salcianu 1.14 else
1098 salcianu 1.14 process_store(l1, f, q.src());
1099 salcianu 1.14 }
1100 salcianu 1.14
1101 salcianu 1.14
1102 salcianu 1.14 private void process_static_store(HField hf, Temp l2) {
1103 salcianu 1.14 if(TOPLAS_PAPER) {
1104 cananian 1.17 for(Object nodeO : lbbpig.G.I.pointedNodes(l2)) {
1105 cananian 1.17 PANode node = (PANode) nodeO;
1106 salcianu 1.14 lbbpig.G.e.addNodeHole(node,
1107 salcianu 1.14 NodeRepository.LOST_SUMMARY);
1108 salcianu 1.14 }
1109 salcianu 1.14 lbbpig.G.propagate(lbbpig.G.I.pointedNodes(l2));
1110 salcianu 1.12 return;
1111 salcianu 1.1.2.5 }
1112 salcianu 1.12
1113 salcianu 1.14 // get the corresponding artificial node
1114 salcianu 1.14 PANode static_node =
1115 salcianu 1.14 nodes.getStaticNode(hf.getDeclaringClass().getName());
1116 salcianu 1.14 lbbpig.G.I.addEdges(static_node, getFieldName(hf),
1117 salcianu 1.14 lbbpig.G.I.pointedNodes(l2));
1118 salcianu 1.14 lbbpig.G.e.addNodeHole(static_node, static_node);
1119 salcianu 1.14 lbbpig.G.propagate(Collections.singleton(static_node));
1120 salcianu 1.1.2.1 }
1121 salcianu 1.14
1122 salcianu 1.14
1123 salcianu 1.1.2.1 /** Store statement; special case - array */
1124 salcianu 1.1.2.1 public void visit(ASET q){
1125 salcianu 1.4 // ignore the ASETs on arrays of primitives
1126 salcianu 1.4 if(!q.type().isPrimitive())
1127 salcianu 1.4 // All array elements are collapsed in a single node
1128 salcianu 1.4 process_store(q.objectref(), ARRAY_CONTENT, q.src());
1129 salcianu 1.1.2.1 }
1130 salcianu 1.1.2.1
1131 salcianu 1.1.2.1 /** Does the real processing of a store statement */
1132 salcianu 1.1.2.1 public void process_store(Temp l1, String f, Temp l2){
1133 salcianu 1.1.2.33 Set set1 = lbbpig.G.I.pointedNodes(l1);
1134 salcianu 1.12 if(CONSIDER_TYPES)
1135 salcianu 1.12 set1 = selectNodesWithField(set1, f);
1136 salcianu 1.1.2.33 Set set2 = lbbpig.G.I.pointedNodes(l2);
1137 salcianu 1.1.2.1
1138 salcianu 1.7 lbbpig.G.I.addEdges(set1, f, set2);
1139 salcianu 1.1.2.33 lbbpig.G.propagate(set1);
1140 salcianu 1.1.2.6 }
1141 salcianu 1.1.2.6
1142 salcianu 1.1.2.38 public void process_thread_start_site(CALL q){
1143 salcianu 1.1.2.38 if(DEBUG2)
1144 salcianu 1.1.2.38 System.out.println("THREAD START SITE: " +
1145 salcianu 1.1.2.38 q.getSourceFile() + ":" +
1146 salcianu 1.1.2.38 q.getLineNumber());
1147 salcianu 1.1.2.38
1148 salcianu 1.1.2.38 // the parallel interaction graph in the case no thread
1149 salcianu 1.1.2.38 // is started due to some error and an exception is returned
1150 salcianu 1.1.2.38 // back from the "start()"
1151 salcianu 1.1.2.38 ParIntGraph lbbpig_no_thread = (ParIntGraph) (lbbpig.clone());
1152 salcianu 1.1.2.38
1153 salcianu 1.1.2.38 Temp l = q.params(0);
1154 salcianu 1.1.2.38 Set set = lbbpig.G.I.pointedNodes(l);
1155 salcianu 1.1.2.38 lbbpig.tau.incAll(set);
1156 salcianu 1.1.2.38
1157 cananian 1.17 for (Object ntO : set){
1158 cananian 1.17 PANode nt = (PANode) ntO;
1159 salcianu 1.1.2.38 lbbpig.G.e.addNodeHole(nt,nt);
1160 salcianu 1.1.2.38 lbbpig.G.propagate(Collections.singleton(nt));
1161 salcianu 1.1.2.38 }
1162 salcianu 1.1.2.6
1163 salcianu 1.1.2.44 call_pp = new ParIntGraphPair(lbbpig, lbbpig_no_thread);
1164 salcianu 1.1.2.38 }
1165 salcianu 1.1.2.13
1166 salcianu 1.1.2.38 public void visit(CALL q){
1167 salcianu 1.8 // System.out.println("CALL " + Util.code2str(q));
1168 salcianu 1.1.2.75
1169 salcianu 1.1.2.38 // treat the thread start sites specially
1170 salcianu 1.1.2.11 if(thread_start_site(q)){
1171 salcianu 1.1.2.38 process_thread_start_site(q);
1172 salcianu 1.1.2.11 return;
1173 salcianu 1.1.2.11 }
1174 salcianu 1.1.2.11
1175 salcianu 1.1.2.37 call_pp =
1176 salcianu 1.1.2.58 InterProcPA.analyze_call(PointerAnalysis.this,
1177 salcianu 1.1.2.58 current_intra_mmethod,
1178 salcianu 1.1.2.58 q, // the CALL site
1179 salcianu 1.1.2.58 lbbpig); // the graph before the call
1180 salcianu 1.1.2.1 }
1181 salcianu 1.1.2.11
1182 salcianu 1.1.2.11 // We are sure that the call site q corresponds to a thread start
1183 salcianu 1.1.2.11 // site if only java.lang.Thread.start can be called there. (If
1184 salcianu 1.1.2.11 // some other methods can be called, it is possible that some of
1185 salcianu 1.1.2.11 // them do not start a thread.)
1186 salcianu 1.14 private boolean thread_start_site(CALL q) {
1187 salcianu 1.1.2.25 MetaMethod mms[] = mcg.getCallees(current_intra_mmethod,q);
1188 salcianu 1.1.2.25 if(mms.length!=1) return false;
1189 salcianu 1.1.2.11
1190 salcianu 1.1.2.25 HMethod hm = mms[0].getHMethod();
1191 salcianu 1.1.2.11 String name = hm.getName();
1192 salcianu 1.1.2.11 if((name==null) || !name.equals("start")) return false;
1193 salcianu 1.1.2.11
1194 salcianu 1.1.2.11 if(hm.isStatic()) return false;
1195 salcianu 1.1.2.11 HClass hclass = hm.getDeclaringClass();
1196 salcianu 1.1.2.11 return hclass.getName().equals("java.lang.Thread");
1197 salcianu 1.1.2.11 }
1198 salcianu 1.1.2.12
1199 salcianu 1.1.2.12 /** Process an acquire statement. */
1200 salcianu 1.14 public void visit(MONITORENTER q) {
1201 salcianu 1.1.2.75 if(RECORD_ACTIONS)
1202 salcianu 1.1.2.75 process_acquire_release(q, q.lock());
1203 salcianu 1.1.2.12 }
1204 salcianu 1.1.2.12
1205 salcianu 1.1.2.12 /** Process a release statement. */
1206 salcianu 1.14 public void visit(MONITOREXIT q) {
1207 salcianu 1.1.2.75 if(RECORD_ACTIONS)
1208 salcianu 1.1.2.75 process_acquire_release(q, q.lock());
1209 salcianu 1.1.2.12 }
1210 salcianu 1.1.2.12
1211 salcianu 1.1.2.12 // Does the real processing for acquire/release statements.
1212 salcianu 1.1.2.42 private void process_acquire_release(Quad q, Temp l){
1213 salcianu 1.1.2.33 Set active_threads = lbbpig.tau.activeThreadSet();
1214 cananian 1.17 for (Object nodeO : lbbpig.G.I.pointedNodes(l)) {
1215 cananian 1.17 PANode node = (PANode) nodeO;
1216 salcianu 1.1.2.42 PASync sync = new PASync(node,ActionRepository.THIS_THREAD, q);
1217 salcianu 1.1.2.42 lbbpig.ar.add_sync(sync, active_threads);
1218 salcianu 1.1.2.12 }
1219 salcianu 1.1.2.24 }
1220 salcianu 1.1.2.1
1221 salcianu 1.1.2.24 /** End of the currently analyzed method; store the graph
1222 salcianu 1.1.2.24 in the hash table. */
1223 salcianu 1.12 public void visit(FOOTER q) {
1224 salcianu 1.1.2.3 // The full graph is stored in the hash_proc_int hashtable;
1225 salcianu 1.1.2.33 hash_proc_int.put(current_intra_mmethod,lbbpig);
1226 salcianu 1.1.2.3 // To obtain the external view of the method, the graph must be
1227 salcianu 1.1.2.3 // shrinked to the really necessary parts: only the stuff
1228 salcianu 1.1.2.3 // that is accessible from the "root" nodes (i.e. the nodes
1229 salcianu 1.1.2.3 // that can be accessed by the rest of the program - e.g.
1230 salcianu 1.1.2.3 // the caller).
1231 salcianu 1.12 if(MEGA_DEBUG)
1232 salcianu 1.12 System.out.println("Unshrinked graph: " + lbbpig);
1233 salcianu 1.12
1234 salcianu 1.13 Set/*<PANode>*/ lost_nodes =
1235 salcianu 1.12 (COMPRESS_LOST_NODES && AGGRESSIVE_COMPRESS_LOST_NODES) ?
1236 salcianu 1.13 getLostNodes(current_intra_mmethod) : null;
1237 salcianu 1.13
1238 salcianu 1.12 ParIntGraph shrinked_graph =
1239 salcianu 1.21 lbbpig.keepTheEssential
1240 salcianu 1.21 (getParamNodes(current_intra_mmethod), false, lost_nodes);
1241 salcianu 1.12
1242 salcianu 1.12 if(MEGA_DEBUG)
1243 salcianu 1.13 System.out.println("Shrinked graph: " + shrinked_graph);
1244 salcianu 1.1.2.44
1245 salcianu 1.1.2.3 // The external view of the graph is stored in the
1246 salcianu 1.1.2.3 // hash_proc_ext hashtable;
1247 salcianu 1.12 hash_proc_ext.put(current_intra_mmethod, shrinked_graph);
1248 salcianu 1.1.2.1 }
1249 cananian 1.1.2.57 }
1250 salcianu 1.1.2.1
1251 salcianu 1.1.2.32
1252 salcianu 1.4 // Quad Visitor used by analyze_basic_block
1253 salcianu 1.1.2.32 private PAVisitor pa_visitor = new PAVisitor();
1254 salcianu 1.1.2.1
1255 salcianu 1.1.2.3 /** Analyzes a basic block - a Parallel Interaction Graph is computed at
1256 salcianu 1.1.2.72 the beginning of the basic block, it is next updated by all the
1257 salcianu 1.1.2.72 instructions appearing in the basic block (in the order they appear
1258 salcianu 1.1.2.72 in the original program). */
1259 salcianu 1.20 private void analyze_basic_block(LightBasicBlock lbb) {
1260 salcianu 1.20 if(DEBUG2 || MEGA_DEBUG)
1261 salcianu 1.20 Debug.print_lbb(lbb, lbb2passes);
1262 salcianu 1.12
1263 salcianu 1.1.2.33 // lbbpig is the graph at the *bb point; it will be
1264 salcianu 1.1.2.44 // updated till it becomes the graph at the bb* point
1265 salcianu 1.1.2.33 lbbpig = get_initial_bb_pig(lbb);
1266 salcianu 1.1.2.1
1267 salcianu 1.1.2.1 // go through all the instructions of this basic block
1268 salcianu 1.1.2.33 HCodeElement[] instrs = lbb.getElements();
1269 salcianu 1.12 for(int i = 0; i < instrs.length; i++) {
1270 salcianu 1.1.2.33 Quad q = (Quad) instrs[i];
1271 salcianu 1.1.2.1
1272 salcianu 1.12 if(DEBUG2 || MEGA_DEBUG || SHOW_INSTR)
1273 salcianu 1.8 System.out.println("INSTR: " + Util.code2str(q));
1274 salcianu 1.1.2.1
1275 salcianu 1.1.2.1 // update the Parallel Interaction Graph according
1276 salcianu 1.1.2.1 // to the current instruction
1277 salcianu 1.1.2.32 q.accept(pa_visitor);
1278 salcianu 1.1.2.1 }
1279 salcianu 1.1.2.1
1280 salcianu 1.1.2.44 // if there was a pair, store the pair computed by the inter proc
1281 salcianu 1.1.2.44 // module, otherwise, only the first element of the pair is essential.
1282 salcianu 1.20 if(call_pp != null) {
1283 salcianu 1.21 putPIGPair(lbb, call_pp);
1284 salcianu 1.1.2.37 call_pp = null;
1285 salcianu 1.1.2.37 }
1286 salcianu 1.1.2.37 else
1287 salcianu 1.21 putPIGPair(lbb, new ParIntGraphPair(lbbpig, null));
1288 salcianu 1.1.2.8
1289 salcianu 1.21 if(DO_INTRA_PROC_TRIMMING)
1290 salcianu 1.21 do_intra_proc_trimming(lbb);
1291 salcianu 1.21 }
1292 salcianu 1.21
1293 salcianu 1.21 // remove unreachable nodes
1294 salcianu 1.21 private void do_intra_proc_trimming(LightBasicBlock lbb) {
1295 salcianu 1.21 PANode[] params = nodes.getAllParams(current_intra_mmethod);
1296 salcianu 1.21 ParIntGraphPair pp = getPIGPair(lbb);
1297 salcianu 1.21 for(int i = 0; i < 2; i++) {
1298 salcianu 1.21 if(pp.pig[i] != null)
1299 salcianu 1.21 pp.pig[i] = pp.pig[i].intra_proc_trimming(params);
1300 salcianu 1.1.2.72 }
1301 salcianu 1.1.2.1 }
1302 salcianu 1.1.2.1
1303 salcianu 1.21
1304 salcianu 1.12 // For each method, maintains the set of inside nodes that are
1305 salcianu 1.12 // merged into LOST during the analysis of that method. These
1306 salcianu 1.12 // nodes do not appear in the pig for the method, but they are
1307 salcianu 1.12 // definitely not captured ....
1308 salcianu 1.12 private Map/*<MetaMethod,Set<PANode>*/ mm2lost =
1309 salcianu 1.12 COMPRESS_LOST_NODES ? new HashMap() : null;
1310 salcianu 1.12
1311 salcianu 1.12 /** @return set of inside nodes that are merged into LOST during
1312 salcianu 1.12 the analysis of <code>mm</code>. These are nodes that do not
1313 salcianu 1.12 appear in the pig for the method, but clearly escape. */
1314 salcianu 1.12 public Set/*<PANode>*/ getLostNodes(MetaMethod mm) {
1315 salcianu 1.12 if(!COMPRESS_LOST_NODES)
1316 salcianu 1.12 return Collections.EMPTY_SET;
1317 salcianu 1.12 Set lost = (Set) mm2lost.get(mm);
1318 salcianu 1.13 if(lost == null) {
1319 salcianu 1.13 lost = new HashSet();
1320 salcianu 1.13 mm2lost.put(mm, lost);
1321 salcianu 1.13 }
1322 salcianu 1.12 return lost;
1323 salcianu 1.12 }
1324 salcianu 1.12
1325 salcianu 1.1.2.2 /** Returns the Parallel Interaction Graph at the point bb*
1326 salcianu 1.1.2.2 * The returned <code>ParIntGraph</code> must not be modified
1327 salcianu 1.1.2.2 * by the caller. This function is used by
1328 salcianu 1.1.2.3 * <code>get_initial_bb_pig</code>. */
1329 salcianu 1.1.2.37 private ParIntGraph get_after_bb_pig(LightBasicBlock lbb,
1330 salcianu 1.1.2.37 LightBasicBlock lbb_son){
1331 salcianu 1.1.2.37
1332 salcianu 1.21 ParIntGraphPair pp = getPIGPair(lbb);
1333 salcianu 1.21
1334 salcianu 1.1.2.44 if(pp == null)
1335 salcianu 1.1.2.37 return ParIntGraph.EMPTY_GRAPH;
1336 salcianu 1.1.2.37
1337 salcianu 1.1.2.37 int k = 0;
1338 salcianu 1.1.2.37 HCodeElement last_lbb = lbb.getLastElement();
1339 salcianu 1.1.2.37 if((last_lbb != null) && (last_lbb instanceof CALL)){
1340 salcianu 1.1.2.37 CALL call = (CALL) last_lbb;
1341 salcianu 1.1.2.37 HCodeElement first_lbb_son = lbb_son.getFirstElement();
1342 salcianu 1.1.2.37 if(!call.next(0).equals(first_lbb_son)) k = 1;
1343 salcianu 1.1.2.37 }
1344 salcianu 1.1.2.37
1345 salcianu 1.1.2.37 ParIntGraph pig = pp.pig[k];
1346 salcianu 1.20 return (pig==null) ? ParIntGraph.EMPTY_GRAPH : pig;
1347 salcianu 1.1.2.2 }
1348 salcianu 1.1.2.2
1349 salcianu 1.1.2.3
1350 salcianu 1.1.2.3 /** (Re)computes the Parallel Interaction Thread associated with
1351 salcianu 1.1.2.33 * the beginning of the <code>LightBasicBlock</code> <code>lbb</code>.
1352 salcianu 1.1.2.3 * This method is recomputing the stuff (instead of just grabbing it
1353 salcianu 1.1.2.3 * from the cache) because the information attached with some of
1354 salcianu 1.1.2.3 * the predecessors has changed (that's why <code>bb</code> is
1355 salcianu 1.1.2.3 * reanalyzed) */
1356 salcianu 1.1.2.33 private ParIntGraph get_initial_bb_pig(LightBasicBlock lbb){
1357 salcianu 1.1.2.33 LightBasicBlock[] prev = lbb.getPrevLBBs();
1358 salcianu 1.1.2.33 int len = prev.length;
1359 salcianu 1.20 if(len == 0) {
1360 salcianu 1.1.2.1 // This case is treated specially, it's about the
1361 salcianu 1.1.2.1 // graph at the beginning of the current method.
1362 salcianu 1.1.2.9 ParIntGraph pig = initial_pig;
1363 salcianu 1.1.2.2 return pig;
1364 salcianu 1.1.2.1 }
1365 salcianu 1.20 else {
1366 salcianu 1.1.2.1 // do the union of the <code>ParIntGraph</code>s attached to
1367 salcianu 1.1.2.1 // all the predecessors of this basic block
1368 salcianu 1.1.2.33 ParIntGraph pig =
1369 salcianu 1.1.2.37 (ParIntGraph) (get_after_bb_pig(prev[0], lbb)).clone();
1370 salcianu 1.1.2.33
1371 salcianu 1.1.2.33 for(int i = 1; i < len; i++)
1372 salcianu 1.1.2.37 pig.join(get_after_bb_pig(prev[i], lbb));
1373 salcianu 1.1.2.2
1374 salcianu 1.1.2.1 return pig;
1375 salcianu 1.1.2.1 }
1376 salcianu 1.1.2.1 }
1377 salcianu 1.1.2.1
1378 salcianu 1.1.2.1
1379 salcianu 1.1.2.3 /** Computes the parallel interaction graph at the beginning of a
1380 salcianu 1.1.2.3 * method; an almost empty graph except for the parameter nodes
1381 salcianu 1.1.2.3 * for the object formal parameter (i.e. primitive type parameters
1382 salcianu 1.1.2.3 * such as <code>int</code>, <code>float</code> do not have associated
1383 salcianu 1.1.2.3 * nodes */
1384 salcianu 1.20 private ParIntGraph get_mmethod_initial_pig
1385 salcianu 1.20 (MetaMethod mm, TopSortedCompDiGraph<LightBasicBlock> ts_sccs) {
1386 salcianu 1.20
1387 salcianu 1.21 LightBasicBlock first_bb = (LightBasicBlock)
1388 salcianu 1.21 ts_sccs.decrOrder().get(0).nodes().iterator().next();
1389 salcianu 1.20 HEADER first_hce = (HEADER) first_bb.getElements()[0];
1390 salcianu 1.20 METHOD m = (METHOD) first_hce.next(1);
1391 salcianu 1.20
1392 salcianu 1.1.2.25 Temp[] params = m.params();
1393 salcianu 1.1.2.25 HMethod hm = mm.getHMethod();
1394 salcianu 1.1.2.2 HClass[] types = hm.getParameterTypes();
1395 salcianu 1.1.2.1
1396 salcianu 1.1.2.1 ParIntGraph pig = new ParIntGraph();
1397 salcianu 1.1.2.2
1398 salcianu 1.1.2.3 // the following code is quite messy ... The problem is that I
1399 salcianu 1.1.2.3 // create param nodes only for the parameter with object types;
1400 salcianu 1.1.2.3 // unfortunately, the types could be found only in HMethod (and
1401 salcianu 1.1.2.68 // do not include the possible this parameter for non-static nodes)
1402 salcianu 1.1.2.3 // while the actual Temps associated with all the formal parameters
1403 salcianu 1.1.2.3 // could be found only in METHOD. So, we have to coordinate
1404 salcianu 1.1.2.3 // information from two different places and, even more, we have
1405 salcianu 1.1.2.3 // to handle the missing this parameter (which is present in METHOD
1406 salcianu 1.1.2.3 // but not in HMethod).
1407 salcianu 1.1.2.2 boolean isStatic =
1408 salcianu 1.1.2.2 java.lang.reflect.Modifier.isStatic(hm.getModifiers());
1409 salcianu 1.1.2.3 // if the method is non-static, the first parameter is not metioned
1410 salcianu 1.1.2.3 // in HMethod - it's the implicit this parameter.
1411 salcianu 1.1.2.81 int skew = isStatic ? 0 : 1;
1412 salcianu 1.1.2.3 // number of object formal parameters = the number of param nodes
1413 salcianu 1.1.2.2 int count = skew;
1414 salcianu 1.1.2.25 for(int i = 0; i < types.length; i++)
1415 salcianu 1.1.2.2 if(!types[i].isPrimitive()) count++;
1416 salcianu 1.1.2.1
1417 salcianu 1.1.2.72 nodes.addParamNodes(mm, count);
1418 salcianu 1.1.2.72 Stats.record_mmethod_params(mm, count);
1419 salcianu 1.1.2.1
1420 salcianu 1.1.2.1 // add all the edges of type <p,np> (i.e. parameter to
1421 salcianu 1.1.2.2 // parameter node) - just for the non-primitive types (e.g. int params
1422 salcianu 1.1.2.2 // do not clutter our analysis)
1423 salcianu 1.1.2.2 // the edges for the static fields will
1424 salcianu 1.1.2.1 // be added later.
1425 salcianu 1.1.2.2 count = 0;
1426 salcianu 1.1.2.25 for(int i = 0; i < params.length; i++)
1427 salcianu 1.1.2.2 if((i<skew) || ((i>=skew) && !types[i-skew].isPrimitive())){
1428 salcianu 1.1.2.25 PANode param_node = nodes.getParamNode(mm,count);
1429 salcianu 1.1.2.2 pig.G.I.addEdge(params[i],param_node);
1430 salcianu 1.1.2.2 // The param nodes are escaping through themselves */
1431 salcianu 1.1.2.2 pig.G.e.addNodeHole(param_node,param_node);
1432 salcianu 1.1.2.2 count++;
1433 salcianu 1.1.2.2 }
1434 salcianu 1.1.2.1
1435 salcianu 1.14 if(TOPLAS_PAPER)
1436 salcianu 1.14 pig.G.e.addNodeHole(NodeRepository.LOST_SUMMARY,
1437 salcianu 1.14 NodeRepository.LOST_SUMMARY);
1438 salcianu 1.14
1439 salcianu 1.1.2.1 return pig;
1440 salcianu 1.1.2.1 }
1441 salcianu 1.1.2.1
1442 salcianu 1.1.2.2 /** Check if <code>hm</code> can be analyzed by the pointer analysis. */
1443 salcianu 1.1.2.42 public static final boolean analyzable(HMethod hm){
1444 salcianu 1.1.2.8 int modifier = hm.getModifiers();
1445 salcianu 1.1.2.8 return ! (
1446 salcianu 1.1.2.8 (java.lang.reflect.Modifier.isNative(modifier)) ||
1447 salcianu 1.1.2.8 (java.lang.reflect.Modifier.isAbstract(modifier))
1448 salcianu 1.1.2.8 );
1449 salcianu 1.1.2.51 }
1450 salcianu 1.1.2.51
1451 salcianu 1.1.2.51
1452 salcianu 1.1.2.20 /** Prints some statistics. */
1453 salcianu 1.20 public final void print_stats() {
1454 salcianu 1.1.2.20 if(!STATS){
1455 salcianu 1.1.2.20 System.out.println("Statistics are deactivated.");
1456 salcianu 1.1.2.20 System.out.println("Turn on the PointerAnalysis.STATS flag!");
1457 salcianu 1.1.2.20 return;
1458 salcianu 1.1.2.20 }
1459 salcianu 1.1.2.20
1460 salcianu 1.1.2.20 Stats.print_stats();
1461 salcianu 1.1.2.20 nodes.print_stats();
1462 salcianu 1.1.2.20 System.out.println("==========================================");
1463 salcianu 1.14 if(SHOW_NODES) {
1464 salcianu 1.1.2.52 System.out.println("BASIC NODES");
1465 salcianu 1.1.2.52 System.out.println(nodes);
1466 salcianu 1.1.2.52 System.out.println("NODE SPECIALIZATIONS:");
1467 salcianu 1.1.2.52 nodes.show_specializations();
1468 salcianu 1.1.2.52 }
1469 salcianu 1.1.2.2 }
1470 salcianu 1.1.2.2
1471 salcianu 1.1.2.30
1472 salcianu 1.1.2.81 /** Returns the parallel interaction graph attached to the program point
1473 salcianu 1.1.2.81 right after <code>q</code> in the body of meta-method
1474 salcianu 1.1.2.81 <code>mm</code>. */
1475 salcianu 1.1.2.81 public final ParIntGraph getPIGAtQuad(MetaMethod mm, Quad q){
1476 salcianu 1.1.2.81 return getPigBeforeQuad(mm, q);
1477 salcianu 1.1.2.81 }
1478 salcianu 1.10
1479 salcianu 1.10 public final ParIntGraph getPIGAtQuad(HMethod hm, Quad q) {
1480 salcianu 1.10 return getPIGAtQuad(new MetaMethod(hm, true), q);
1481 salcianu 1.10 }
1482 salcianu 1.10
1483 salcianu 1.1.2.81
1484 salcianu 1.1.2.81 /** Returns the parallel interaction graph attached to the program point
1485 salcianu 1.1.2.81 right after <code>q</code> in the body of meta-method
1486 salcianu 1.1.2.81 <code>mm</code>. */
1487 salcianu 1.1.2.81 public final ParIntGraph getPigAfterQuad(MetaMethod mm, Quad q) {
1488 salcianu 1.1.2.81 return getPigForQuad(mm, q, AFTER_QUAD);
1489 salcianu 1.1.2.30 }
1490 salcianu 1.1.2.30
1491 salcianu 1.1.2.30 /** Returns the parallel interaction graph attached to the program point
1492 salcianu 1.1.2.30 right before <code>q</code> in the body of meta-method
1493 salcianu 1.1.2.30 <code>mm</code>. */
1494 salcianu 1.1.2.81 public final ParIntGraph getPigBeforeQuad(MetaMethod mm, Quad q) {
1495 salcianu 1.1.2.81 return getPigForQuad(mm, q, BEFORE_QUAD);
1496 salcianu 1.1.2.81 }
1497 salcianu 1.1.2.81
1498 salcianu 1.1.2.81
1499 salcianu 1.1.2.81 public final ParIntGraph getPigForQuad(MetaMethod mm, Quad q, int moment) {
1500 salcianu 1.6 assert mcg.getAllMetaMethods().contains(mm) :
1501 salcianu 1.6 "Uncalled/unknown meta-method!";
1502 salcianu 1.21
1503 salcianu 1.21 LightBasicBlock lbb = find_lbb4quad(mm, q);
1504 salcianu 1.20
1505 salcianu 1.1.2.30 // as all the ParIntGraph's for methods are computed, a simple
1506 salcianu 1.21 // intra-procedural analysis of mm is enough.
1507 salcianu 1.21 _analyze_intra_proc(mm); // don't delete the cache
1508 salcianu 1.21
1509 salcianu 1.21 // find the right basic block, and redo pointer analysis
1510 salcianu 1.21 // for that block, until we hit q.
1511 salcianu 1.1.2.81 ParIntGraph retval = analyze_lbb_for_q(lbb, q, moment);
1512 salcianu 1.1.2.61
1513 salcianu 1.21 // clear the LightBasicBlock -> ParIntGraph cache
1514 salcianu 1.21 lbb2pp.clear();
1515 salcianu 1.1.2.33
1516 salcianu 1.1.2.30 return retval;
1517 salcianu 1.1.2.33 }
1518 salcianu 1.1.2.33
1519 salcianu 1.21 // finds the LightBasicBlock of Quad q from (meta)method mm
1520 salcianu 1.21 private LightBasicBlock find_lbb4quad(MetaMethod mm, Quad q) {
1521 salcianu 1.21 LBBConverter lbbconv = scc_lbb_factory.getLBBConverter();
1522 salcianu 1.21 LightBasicBlock.Factory lbbf = lbbconv.convert2lbb(mm.getHMethod());
1523 salcianu 1.21 assert lbbf != null : "Unanalyzable method " + mm + "?!";
1524 salcianu 1.21 LightBasicBlock lbb = lbbf.getBlock(q);
1525 salcianu 1.21 assert lbb != null : "No (Light)BasicBlock found for " + q;
1526 salcianu 1.21 return lbb;
1527 salcianu 1.21 }
1528 salcianu 1.21
1529 salcianu 1.1.2.81 // constants for analyze_lbb_for_q
1530 salcianu 1.1.2.81 private final static int BEFORE_QUAD = 0;
1531 salcianu 1.1.2.81 private final static int AFTER_QUAD = 1;
1532 salcianu 1.1.2.81
1533 salcianu 1.1.2.81 /** Returns the parallel interaction graph valid at the program
1534 salcianu 1.1.2.81 point right before/after <code>q</code>. <code>q</code> belongs to
1535 salcianu 1.1.2.81 the light basic block <code>lbb</code> of the
1536 salcianu 1.1.2.81 <code>current_intra_mmethod</code>. The analysis is
1537 salcianu 1.1.2.81 re-executed from the beginning of <code>lbb</code>, to the
1538 salcianu 1.1.2.81 point immediately before/after <code>q</code> when we stop it and
1539 salcianu 1.1.2.81 return the parallel intercation graph valid at that moment. */
1540 salcianu 1.1.2.81 private ParIntGraph analyze_lbb_for_q(LightBasicBlock lbb, Quad q,
1541 salcianu 1.1.2.81 int moment) {
1542 salcianu 1.1.2.81 lbbpig = get_initial_bb_pig(lbb);
1543 salcianu 1.1.2.81 HCodeElement[] instrs = lbb.getElements();
1544 salcianu 1.6 for(int i = 0; i < instrs.length; i++) {
1545 salcianu 1.1.2.81 Quad q_curr = (Quad) instrs[i];
1546 salcianu 1.1.2.81 if((moment == BEFORE_QUAD) && q_curr.equals(q))
1547 salcianu 1.1.2.81 return lbbpig;
1548 salcianu 1.1.2.81 q_curr.accept(pa_visitor);
1549 salcianu 1.1.2.81 if((moment == AFTER_QUAD) && q_curr.equals(q))
1550 salcianu 1.1.2.81 return lbbpig;
1551 salcianu 1.1.2.81 }
1552 cananian 1.3.2.1 assert false : q + " was not in " + lbb;
1553 salcianu 1.1.2.81 return null; // this should never happen
1554 salcianu 1.1.2.81 }
1555 salcianu 1.1.2.81
1556 salcianu 1.21 // TODO: remove as soon as lbb2pp works
1557 salcianu 1.20 // activates some GC
1558 salcianu 1.20 private final void clear_lbb2pig(MetaMethod mm) {
1559 salcianu 1.20 // cut the method into SCCs of basic blocks
1560 salcianu 1.20 TopSortedCompDiGraph<LightBasicBlock> ts_sccs =
1561 salcianu 1.20 scc_lbb_factory.computeSCCLBB(mm.getHMethod());
1562 salcianu 1.20 for(SCComponent/*<LightBasicBlock>*/ scc : ts_sccs.incrOrder()) {
1563 salcianu 1.20 for(Object/*LightBasicBlock*/ lbb0 : scc.nodes() ) {
1564 salcianu 1.20 ((LightBasicBlock) lbb0).user_info = null;
1565 salcianu 1.20 }
1566 salcianu 1.20 }
1567 salcianu 1.1.2.39 }
1568 salcianu 1.1.2.74
1569 salcianu 1.1.2.30 /** Returns the set of the nodes pointed by the temporary <code>t</code>
1570 salcianu 1.1.2.30 at the point right before executing instruction <code>q</code>
1571 salcianu 1.1.2.30 from the body of meta-method <code>mm</code>. */
1572 salcianu 1.1.2.30 public final Set pointedNodes(MetaMethod mm, Quad q, Temp l){
1573 salcianu 1.1.2.30 // 1. obtain the Parallel Interaction Graph attached to the point
1574 salcianu 1.1.2.30 // right before the execution of q (noted .q in the article).
1575 salcianu 1.1.2.74 ParIntGraph pig = getPIGAtQuad(mm, q);
1576 salcianu 1.1.2.30 // 2. look at the nodes pointed by l; as from a temporary we can
1577 salcianu 1.1.2.30 // have only inside edges, it is enough to look in the I set.
1578 salcianu 1.1.2.30 return pig.G.I.pointedNodes(l);
1579 salcianu 1.1.2.30 }
1580 salcianu 1.1.2.45
1581 salcianu 1.1.2.81 // given a quad q, returns the method q is part of
1582 salcianu 1.1.2.81 private final HMethod quad2method(Quad q) {
1583 salcianu 1.1.2.81 return q.getFactory().getMethod();
1584 salcianu 1.1.2.81 }
1585 salcianu 1.1.2.74
1586 salcianu 1.1.2.74 public final Set pointedNodes(Quad q, Temp l) {
1587 salcianu 1.1.2.81 return pointedNodes(new MetaMethod(quad2method(q), true), q, l);
1588 salcianu 1.1.2.74 }
1589 salcianu 1.12
1590 salcianu 1.12
1591 salcianu 1.12 private Collection typeFilter(Set nodes, HClass hclass) {
1592 salcianu 1.12 List result = new LinkedList();
1593 cananian 1.17 for(Object nodeO : nodes) {
1594 cananian 1.17 PANode node = (PANode) nodeO;
1595 salcianu 1.12 if(node.type != PANode.INSIDE) {
1596 salcianu 1.12 result.add(node);
1597 salcianu 1.12 continue;
1598 salcianu 1.12 }
1599 salcianu 1.12 HClass type = getType(node);
1600 salcianu 1.12 if((type == null) || type.isInstanceOf(hclass))
1601 salcianu 1.12 result.add(node);
1602 salcianu 1.12 }
1603 salcianu 1.12 return result;
1604 salcianu 1.12 }
1605 salcianu 1.12
1606 salcianu 1.12 static HClass getType(PANode node) {
1607 salcianu 1.12 assert node.type == PANode.INSIDE;
1608 salcianu 1.12 HCodeElement q = nodes.node2Code(node);
1609 salcianu 1.12 if(q == null) return null;
1610 salcianu 1.12 if(q instanceof NEW)
1611 salcianu 1.12 return ((NEW) q).hclass();
1612 salcianu 1.12 else
1613 salcianu 1.12 return ((ANEW) q).hclass();
1614 salcianu 1.12 }
1615 salcianu 1.12
1616 salcianu 1.12
1617 salcianu 1.12 private static class PathEdge {
1618 salcianu 1.12 PathEdge(PathEdge pred, PANode start, String f, PANode end,
1619 salcianu 1.12 boolean inside) {
1620 salcianu 1.12 this.pred = pred;
1621 salcianu 1.12 this.start = start;
1622 salcianu 1.12 this.end = end;
1623 salcianu 1.12 this.f = f;
1624 salcianu 1.12 this.inside = inside;
1625 salcianu 1.12 }
1626 salcianu 1.12
1627 salcianu 1.12 final PathEdge pred;
1628 salcianu 1.12 final PANode start, end;
1629 salcianu 1.12 final String f;
1630 salcianu 1.12 final boolean inside;
1631 salcianu 1.12 }
1632 salcianu 1.12
1633 salcianu 1.12 private void find_trace(ParIntGraph pig) {
1634 salcianu 1.12 final LinkedList W = new LinkedList();
1635 salcianu 1.12 final Set reachable = new HashSet();
1636 salcianu 1.12
1637 salcianu 1.12 W.addLast(new PathEdge(null, null, null, NodeRepository.LOST_SUMMARY,
1638 salcianu 1.12 false));
1639 salcianu 1.12 reachable.add(NodeRepository.LOST_SUMMARY);
1640 salcianu 1.12 while(!W.isEmpty()) {
1641 salcianu 1.12 final PathEdge edge = (PathEdge) W.removeFirst();
1642 salcianu 1.12 final PANode node = edge.end;
1643 salcianu 1.12
1644 salcianu 1.12 if(node.number == 1533) {
1645 salcianu 1.12 print_path(edge);
1646 salcianu 1.12 System.exit(1);
1647 salcianu 1.12 }
1648 salcianu 1.12
1649 salcianu 1.12 pig.G.I.forAllEdges
1650 salcianu 1.12 (node,
1651 salcianu 1.12 new PAEdgeVisitor() {
1652 salcianu 1.12 public void visit(Temp v, PANode node) {}
1653 salcianu 1.12 public void visit(PANode node, String f, PANode node2) {
1654 salcianu 1.12 if(reachable.contains(node2)) return;
1655 salcianu 1.12 W.addLast(new PathEdge(edge, node, f, node2, true));
1656 salcianu 1.12 reachable.add(node2);
1657 salcianu 1.12 }
1658 salcianu 1.12 });
1659 salcianu 1.12
1660 salcianu 1.12 pig.G.O.forAllEdges
1661 salcianu 1.12 (node,
1662 salcianu 1.12 new PAEdgeVisitor() {
1663 salcianu 1.12 public void visit(Temp v, PANode node) {}
1664 salcianu 1.12 public void visit(PANode node, String f, PANode node2) {
1665 salcianu 1.12 if(reachable.contains(node2)) return;
1666 salcianu 1.12 W.addLast(new PathEdge(edge, node, f, node2, false));
1667 salcianu 1.12 reachable.add(node2);
1668 salcianu 1.12 }
1669 salcianu 1.12 });
1670 salcianu 1.12 }
1671 salcianu 1.12 }
1672 salcianu 1.12
1673 salcianu 1.12 private void print_path(PathEdge edge) {
1674 salcianu 1.12 System.out.println("\n\nEscapability path for " + edge.end);
1675 salcianu 1.12 print_path2(edge);
1676 salcianu 1.12 System.out.println();
1677 salcianu 1.12 }
1678 salcianu 1.12
1679 salcianu 1.12 private void print_path2(PathEdge edge) {
1680 salcianu 1.12 if(edge.pred != null) {
1681 salcianu 1.12 print_path2(edge.pred);
1682 salcianu 1.12 System.out.println
1683 salcianu 1.12 ((edge.inside ? "I" : "O") +
1684 salcianu 1.12 ": <" + edge.start + "," + edge.f + "," + edge.end + ">");
1685 salcianu 1.12 }
1686 salcianu 1.12 else
1687 salcianu 1.12 System.out.println("START: " + edge.end);
1688 salcianu 1.12 }
1689 salcianu 1.12
1690 salcianu 1.12 static Set/*<PANode>*/ selectNodesWithField(Set nodes, String f) {
1691 salcianu 1.12 Set result = new LinearSet();
1692 cananian 1.17 for(Object nodeO : nodes) {
1693 cananian 1.17 PANode node = (PANode) nodeO;
1694 salcianu 1.12 if(hasField(node, f))
1695 salcianu 1.12 result.add(node);
1696 salcianu 1.12 }
1697 salcianu 1.12 return result;
1698 salcianu 1.12 }
1699 salcianu 1.12
1700 salcianu 1.12
1701 salcianu 1.12 static boolean hasField(PANode node, String f) {
1702 salcianu 1.12 // now with caching!
1703 salcianu 1.12 hasFieldQuery.init(node, f);
1704 salcianu 1.12 Boolean answer = (Boolean) hasFieldCache.get(hasFieldQuery);
1705 salcianu 1.12 if(answer == null) {
1706 salcianu 1.12 answer = new Boolean(_hasField(node, f));
1707 salcianu 1.12 hasFieldCache.put(new HasFieldQuery(node, f), answer);
1708 salcianu 1.12 }
1709 salcianu 1.12 return answer.booleanValue();
1710 salcianu 1.12 }
1711 salcianu 1.12 private static class HasFieldQuery {
1712 salcianu 1.12 HasFieldQuery() { }
1713 salcianu 1.12 HasFieldQuery(PANode node, String f) { init(node, f); }
1714 salcianu 1.12 void init(PANode node, String f) {
1715 salcianu 1.12 this.node = node;
1716 salcianu 1.12 this.f = f;
1717 salcianu 1.12 this.hash = node.hashCode() ^ f.hashCode();
1718 salcianu 1.12 }
1719 salcianu 1.12 PANode node;
1720 salcianu 1.12 String f;
1721 salcianu 1.12 int hash;
1722 salcianu 1.12
1723 salcianu 1.12 public int hashCode() { return hash; }
1724 salcianu 1.12 public boolean equals(Object o) {
1725 salcianu 1.12 if(this.hashCode() != o.hashCode())
1726 salcianu 1.12 return false;
1727 salcianu 1.12 HasFieldQuery q = (HasFieldQuery) o;
1728 salcianu 1.12 return
1729 salcianu 1.12 (this.node == q.node) &&
1730 salcianu 1.20 (this.f.equals(q.f));
1731 salcianu 1.12 }
1732 salcianu 1.12 }
1733 salcianu 1.12 private static HasFieldQuery hasFieldQuery = new HasFieldQuery();
1734 salcianu 1.12 private static Map/*<HasFieldQuery,Boolean>*/ hasFieldCache =
1735 salcianu 1.12 new HashMap();
1736 salcianu 1.12
1737 salcianu 1.12 private static boolean _hasField(PANode node, String f) {
1738 salcianu 1.12 if(f.equals(PointerAnalysis.ARRAY_CONTENT))
1739 salcianu 1.12 return isArrayOfObjs(node);
1740 salcianu 1.12
1741 salcianu 1.12 GenType gts[] = node.getPossibleClasses();
1742 salcianu 1.12 if(gts == null)
1743 salcianu 1.12 return true;
1744 salcianu 1.12
1745 salcianu 1.12 for(int i = 0; i < gts.length; i++) {
1746 salcianu 1.12 GenType gt = gts[i];
1747 salcianu 1.12
1748 salcianu 1.12 if(gt.isPOLY()) {
1749 salcianu 1.12 if(gt.getHClass().getName().equals("java.lang.Object"))
1750 salcianu 1.12 return true;
1751 salcianu 1.14 Set/*<HClass>*/ allClasses = getAllConcreteClasses(gt);
1752 cananian 1.17 for(Object hclassO : allClasses) {
1753 cananian 1.17 HClass hclass = (HClass) hclassO;
1754 salcianu 1.12 if(classHasField(hclass, f))
1755 salcianu 1.12 return true;
1756 salcianu 1.12 }
1757 salcianu 1.12 }
1758 salcianu 1.12 else { // monomorphic type
1759 salcianu 1.12 if(classHasField(gt.getHClass(), f))
1760 salcianu 1.12 return true;
1761 salcianu 1.12 }
1762 salcianu 1.12 }
1763 salcianu 1.12
1764 salcianu 1.15 /* // debug code
1765 salcianu 1.12 System.out.println
1766 salcianu 1.12 ("YYY: no " + f + " in " + node + " type: " + pp_types(gts));
1767 salcianu 1.15 */
1768 salcianu 1.12
1769 salcianu 1.12 return false;
1770 salcianu 1.12 }
1771 salcianu 1.14
1772 salcianu 1.14 static Set/*<HClass>*/ getAllConcreteClasses(GenType gt) {
1773 salcianu 1.14 if(gt.isPOLY())
1774 salcianu 1.14 return
1775 salcianu 1.14 DiGraph.reachableVertices
1776 salcianu 1.14 (Collections.singleton(gt.getHClass()),
1777 salcianu 1.14 new ForwardNavigator() {
1778 salcianu 1.14 public Object[] next(Object node) {
1779 salcianu 1.14 Set sons = ch.children((HClass) node);
1780 salcianu 1.14 return sons.toArray(new HClass[sons.size()]);
1781 salcianu 1.14 }
1782 salcianu 1.14 });
1783 salcianu 1.14 else
1784 salcianu 1.14 return Collections.singleton(gt.getHClass());
1785 salcianu 1.14 }
1786 salcianu 1.12
1787 salcianu 1.14 static Set/*<HClass>*/ getAllConcreteClasses(GenType[] gts) {
1788 salcianu 1.14 Set result = new HashSet();
1789 salcianu 1.14 for(int i = 0; i < gts.length; i++)
1790 salcianu 1.14 result.addAll(getAllConcreteClasses(gts[i]));
1791 salcianu 1.14 return result;
1792 salcianu 1.14 }
1793 salcianu 1.12
1794 salcianu 1.12 private static boolean classHasField(HClass hclass, String f) {
1795 salcianu 1.12 if(hclass == null) return false;
1796 salcianu 1.12
1797 salcianu 1.12 HField fields[] = hclass.getDeclaredFields();
1798 salcianu 1.12 for(int i = 0; i < fields.length; i++) {
1799 salcianu 1.12 if(getFieldName(fields[i]).equals(f))
1800 salcianu 1.12 return true;
1801 salcianu 1.12 }
1802 salcianu 1.12
1803 salcianu 1.12 return classHasField(hclass.getSuperclass(), f);
1804 salcianu 1.12 }
1805 salcianu 1.12
1806 salcianu 1.12
1807 salcianu 1.12 static boolean isArrayOfObjs(PANode node) {
1808 salcianu 1.12 // now with caching!
1809 salcianu 1.12 Boolean answer = (Boolean) isArrayOfObjsCache.get(node);
1810 salcianu 1.12 if(answer == null) {
1811 salcianu 1.12 answer = new Boolean(_isArrayOfObjs(node));
1812 salcianu 1.12 isArrayOfObjsCache.put(node, answer);
1813 salcianu 1.12 }
1814 salcianu 1.12 return answer.booleanValue();
1815 salcianu 1.12 }
1816 salcianu 1.12 private static Map/*<PANode,Boolean>*/ isArrayOfObjsCache = new HashMap();
1817 salcianu 1.12
1818 salcianu 1.12 // does the real job
1819 salcianu 1.12 private static boolean _isArrayOfObjs(PANode node) {
1820 salcianu 1.12 GenType gts[] = node.getPossibleClasses();
1821 salcianu 1.12 if(gts == null) // conservative answer about unknown types
1822 salcianu 1.12 return true;
1823 salcianu 1.12
1824 salcianu 1.12 for(int i = 0; i < gts.length; i++) {
1825 salcianu 1.12 GenType gt = gts[i];
1826 salcianu 1.12 HClass hclass = gt.getHClass();
1827 salcianu 1.12 // an array is a special case of java.lang.Object
1828 salcianu 1.12 if(gt.isPOLY() && hclass.equals(java_lang_Object))
1829 salcianu 1.12 return true;
1830 salcianu 1.12
1831 salcianu 1.12 if(hclass.isArray() &&
1832 salcianu 1.12 !hclass.getComponentType().isPrimitive())
1833 salcianu 1.12 return true;
1834 salcianu 1.12 }
1835 salcianu 1.12
1836 salcianu 1.15 /* // debug code
1837 salcianu 1.12 System.out.println
1838 salcianu 1.12 ("YYY: not an array of objs: " + node + " type: " + pp_types(gts));
1839 salcianu 1.15 */
1840 salcianu 1.12
1841 salcianu 1.12 return false;
1842 salcianu 1.12 }
1843 salcianu 1.12
1844 salcianu 1.12
1845 salcianu 1.12 private static String pp_types(GenType[] gts) {
1846 salcianu 1.12 StringBuffer buff = new StringBuffer();
1847 salcianu 1.12 for(int i = 0; i < gts.length; i++) {
1848 salcianu 1.12 if(i != 0) buff.append(", ");
1849 salcianu 1.12 buff.append(gts[i]);
1850 salcianu 1.12 }
1851 salcianu 1.12 return buff.toString();
1852 salcianu 1.12 }
1853 salcianu 1.12
1854 salcianu 1.12 // If node may be an array of objects, than return a set of
1855 salcianu 1.12 // conservative estimates for the component types of the array
1856 salcianu 1.12 // Otherwise, return null.
1857 salcianu 1.12 static Set/*<HClass>*/ getObjArrayComp(PANode node) {
1858 salcianu 1.12
1859 salcianu 1.12 GenType gts[] = node.getPossibleClasses();
1860 salcianu 1.12 if(gts == null) // conservative answer about unknown types
1861 salcianu 1.12 return Collections.singleton(java_lang_Object);
1862 salcianu 1.12
1863 salcianu 1.12 Set compTypes = new LinearSet();
1864 salcianu 1.12
1865 salcianu 1.12 for(int i = 0; i < gts.length; i++) {
1866 salcianu 1.12 GenType gt = gts[i];
1867 salcianu 1.12 HClass hclass = gt.getHClass();
1868 salcianu 1.12 // an array is a special case of java.lang.Object
1869 salcianu 1.12 if(gt.isPOLY() && hclass.equals(java_lang_Object))
1870 salcianu 1.12 return Collections.singleton(java_lang_Object);
1871 salcianu 1.12
1872 salcianu 1.12 if(hclass.isArray() && !hclass.getComponentType().isPrimitive())
1873 salcianu 1.12 compTypes.add(hclass.getComponentType());
1874 salcianu 1.12 }
1875 salcianu 1.12
1876 salcianu 1.12 if(compTypes.size() == 0)
1877 salcianu 1.12 compTypes = null;
1878 salcianu 1.12
1879 salcianu 1.12 return compTypes;
1880 salcianu 1.12 }
1881 salcianu 1.12
1882 salcianu 1.12
1883 salcianu 1.12 // TODO: look at the type of the node directly
1884 salcianu 1.12 // select only the nodes that may represent arrays of objects
1885 salcianu 1.12 static Set/*<PANode>*/ selectArraysOfObjs(Set/*<PANode>*/ nodes) {
1886 salcianu 1.12 Set result = new HashSet();
1887 salcianu 1.12
1888 cananian 1.17 for(Object nodeO : nodes) {
1889 cananian 1.17 PANode node = (PANode) nodeO;
1890 salcianu 1.12 if(isArrayOfObjs(node))
1891 salcianu 1.12 result.add(node);
1892 salcianu 1.12 }
1893 salcianu 1.12
1894 salcianu 1.12 return result;
1895 salcianu 1.12 }
1896 salcianu 1.12
1897 salcianu 1.12 // TODO: use HFields, instead of Strings, as edge labels
1898 salcianu 1.12 // It's much healthier!
1899 salcianu 1.12 // returns the string name for a field
1900 salcianu 1.12 static String getFieldName(HField hf) {
1901 salcianu 1.12 String name = (String) getFieldNameCache.get(hf);
1902 salcianu 1.12 if(name == null) {
1903 salcianu 1.12 // it used to be only hf.getName();
1904 salcianu 1.12 name = hf.getDeclaringClass().getName() + "." + hf.getName();
1905 salcianu 1.12 getFieldNameCache.put(hf, name);
1906 salcianu 1.12 }
1907 salcianu 1.12 return name;
1908 salcianu 1.12 }
1909 salcianu 1.12 private static Map/*<HField,String>*/ getFieldNameCache = new HashMap();
1910 cananian 1.2 }