1 salcianu 1.1.2.1 // MetaCallGraphImpl.java, created Wed Mar 8 15:20:29 2000 by salcianu
2 cananian 1.1.2.27 // 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.MetaMethods;
5 salcianu 1.1.2.1
6 salcianu 1.1.2.25 import java.util.Arrays;
7 salcianu 1.1.2.1 import java.util.Map;
8 salcianu 1.1.2.1 import java.util.HashMap;
9 salcianu 1.1.2.1 import java.util.Set;
10 salcianu 1.1.2.1 import java.util.HashSet;
11 salcianu 1.5 import java.util.List;
12 salcianu 1.5 import java.util.LinkedList;
13 salcianu 1.1.2.1 import java.util.Iterator;
14 salcianu 1.5 import java.util.Collection;
15 salcianu 1.1.2.1 import java.util.Collections;
16 salcianu 1.1.2.1
17 salcianu 1.1.2.1 import java.lang.reflect.Modifier;
18 salcianu 1.1.2.1
19 salcianu 1.1.2.1 import harpoon.Analysis.ClassHierarchy;
20 salcianu 1.1.2.1 import harpoon.Analysis.ReachingDefs;
21 salcianu 1.1.2.1 import harpoon.Analysis.ReachingDefsImpl;
22 salcianu 1.7 import harpoon.Analysis.SSxReachingDefsImpl;
23 salcianu 1.1.2.1 import harpoon.Analysis.BasicBlock;
24 salcianu 1.1.2.1 import harpoon.ClassFile.HCodeElement;
25 salcianu 1.1.2.28 import harpoon.ClassFile.HCodeFactory;
26 salcianu 1.1.2.28 import harpoon.ClassFile.CachingCodeFactory;
27 salcianu 1.1.2.1 import harpoon.ClassFile.HMethod;
28 salcianu 1.1.2.1 import harpoon.ClassFile.HCode;
29 salcianu 1.1.2.1 import harpoon.ClassFile.HClass;
30 salcianu 1.1.2.18 import harpoon.ClassFile.Linker;
31 salcianu 1.1.2.1
32 salcianu 1.5 import harpoon.IR.Quads.Code;
33 salcianu 1.1.2.1 import harpoon.IR.Quads.QuadVisitor;
34 salcianu 1.1.2.1 import harpoon.IR.Quads.Quad;
35 salcianu 1.7 import harpoon.IR.Quads.QuadNoSSA;
36 salcianu 1.7 import harpoon.IR.Quads.QuadSSA;
37 salcianu 1.7 import harpoon.IR.Quads.QuadSSI;
38 salcianu 1.1.2.1 import harpoon.IR.Quads.HEADER;
39 salcianu 1.1.2.1 import harpoon.IR.Quads.METHOD;
40 salcianu 1.1.2.1 import harpoon.IR.Quads.CALL;
41 salcianu 1.1.2.1 import harpoon.IR.Quads.MOVE;
42 salcianu 1.1.2.1 import harpoon.IR.Quads.GET;
43 salcianu 1.1.2.1 import harpoon.IR.Quads.AGET;
44 salcianu 1.1.2.1 import harpoon.IR.Quads.NEW;
45 salcianu 1.1.2.1 import harpoon.IR.Quads.ANEW;
46 salcianu 1.1.2.1 import harpoon.IR.Quads.TYPECAST;
47 salcianu 1.1.2.1 import harpoon.IR.Quads.CONST;
48 salcianu 1.5 import harpoon.IR.Quads.SIGMA;
49 salcianu 1.5 import harpoon.IR.Quads.PHI;
50 salcianu 1.5 import harpoon.IR.Quads.CJMP;
51 salcianu 1.5 import harpoon.IR.Quads.INSTANCEOF;
52 salcianu 1.7 import harpoon.IR.Quads.OPER;
53 salcianu 1.7 import harpoon.IR.Quads.CONST;
54 salcianu 1.7 import harpoon.IR.Quads.Qop;
55 salcianu 1.1.2.1
56 salcianu 1.1.2.1 import harpoon.Temp.Temp;
57 salcianu 1.1.2.1
58 salcianu 1.13 import harpoon.Util.Graphs.DiGraph;
59 salcianu 1.1.2.6 import harpoon.Util.Graphs.SCComponent;
60 salcianu 1.11 import harpoon.Util.Graphs.Navigator;
61 salcianu 1.13 import harpoon.Util.Graphs.TopSortedCompDiGraph;
62 salcianu 1.1.2.1 import harpoon.Analysis.PointerAnalysis.PAWorkList;
63 salcianu 1.1.2.23 import harpoon.Analysis.PointerAnalysis.Debug;
64 salcianu 1.1.2.1
65 salcianu 1.1.2.1 import harpoon.Util.Util;
66 salcianu 1.1.2.25 import harpoon.Util.UComp;
67 salcianu 1.1.2.1
68 salcianu 1.1.2.21 import harpoon.Util.DataStructs.Relation;
69 salcianu 1.1.2.24 import harpoon.Util.DataStructs.RelationImpl;
70 salcianu 1.1.2.21 import harpoon.Util.DataStructs.RelationEntryVisitor;
71 salcianu 1.1.2.21
72 salcianu 1.1.2.21
73 salcianu 1.1.2.1 /**
74 salcianu 1.1.2.1 * <code>MetaCallGraphImpl</code> is a full-power implementation of the
75 salcianu 1.1.2.24 <code>MetaCallGraph</code> interface. This is <i>the</i> class to use
76 salcianu 1.1.2.24 if you want to play with meta-methods.<br>
77 salcianu 1.1.2.1
78 salcianu 1.1.2.1 Otherwise, you can simply use
79 salcianu 1.1.2.1 <code>FakeCallGraph</code> which allows you to run things that need
80 salcianu 1.1.2.1 meta method representation of the program even without generating them
81 salcianu 1.1.2.1 by simply providing a meta methods-like interface for the standard
82 salcianu 1.1.2.1 <code>CallGraph</code>.
83 salcianu 1.1.2.1 *
84 cananian 1.1.2.27 * @author Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
85 salcianu 1.15 * @version $Id: MetaCallGraphImpl.java,v 1.15 2004/03/06 21:52:21 salcianu Exp $
86 salcianu 1.1.2.1 */
87 salcianu 1.1.2.20 public class MetaCallGraphImpl extends MetaCallGraphAbstr {
88 salcianu 1.1.2.1
89 salcianu 1.8 public static boolean COLL_HACK = false;
90 salcianu 1.8 private static boolean DEBUG_COLL_HACK = true;
91 salcianu 1.8
92 salcianu 1.8 // true if a collection may be stored into a collection
93 salcianu 1.8 private boolean no_coll_in_coll = true;
94 salcianu 1.8
95 salcianu 1.8 // If a call might call a native, we don't try to detect all the
96 salcianu 1.8 // methods that are called there: pointer analysis would anyway
97 salcianu 1.8 // skip that call (and consider it a source of escapability)
98 salcianu 1.8 public static boolean TOUGH_ON_NATIVES = false;
99 salcianu 1.8
100 salcianu 1.1.2.1 private static boolean DEBUG = false;
101 salcianu 1.1.2.8 private static boolean DEBUG_CH = false;
102 salcianu 1.1.2.18 private static boolean COUNTER = true;
103 salcianu 1.1.2.1
104 salcianu 1.1.2.25 /** Make sure the results of the query methods (getCalles like) don't
105 salcianu 1.1.2.25 depend on the run; facilitate the debugging. */
106 salcianu 1.1.2.25 public static final boolean DETERMINISTIC = true;
107 salcianu 1.1.2.25
108 salcianu 1.1.2.24 private static int SPEC_BOUND = 3;
109 salcianu 1.1.2.24
110 salcianu 1.1.2.1 // in "caution" mode, plenty of tests are done to protect ourselves
111 salcianu 1.1.2.1 // against errors in other components (ex: ReachingDefs)
112 salcianu 1.1.2.8 private static final boolean CAUTION = true;
113 salcianu 1.1.2.1
114 salcianu 1.1.2.28 private CachingCodeFactory hcf;
115 salcianu 1.1.2.5 private ClassHierarchy ch;
116 salcianu 1.8 private Linker linker;
117 salcianu 1.1.2.1
118 salcianu 1.1.2.24 // the set of the classes T such that a new T instruction might be executed
119 salcianu 1.1.2.24 // by the analyzed application.
120 salcianu 1.1.2.24 private Set instantiated_classes = null;
121 salcianu 1.1.2.24
122 salcianu 1.7 // indicates whether we use the SSA / SSI format
123 salcianu 1.7 private boolean ssx_form = false;
124 salcianu 1.7
125 salcianu 1.8 // Any method can throw an exception that is subclass of these
126 salcianu 1.8 // two classes (without explicitly declaring it).
127 salcianu 1.8 private HClass jl_RuntimeException;
128 salcianu 1.8 private HClass jl_Error;
129 salcianu 1.8 private HClass jl_Thread;
130 salcianu 1.8 private HClass jl_Runnable;
131 salcianu 1.8 private HClass jl_Object;
132 salcianu 1.8 private HMethod hm_HashtablePut;
133 salcianu 1.8
134 salcianu 1.1.2.1 /** Creates a <code>MetaCallGraphImpl</code>. It must receive, in its
135 salcianu 1.1.2.4 last parameter, the <code>main</code> method of the program. */
136 salcianu 1.8 public MetaCallGraphImpl(CachingCodeFactory hcf, Linker linker,
137 salcianu 1.8 ClassHierarchy ch, Set hmroots) {
138 salcianu 1.5
139 salcianu 1.5 assert
140 salcianu 1.7 hcf.getCodeName().equals(QuadNoSSA.codename) ||
141 salcianu 1.7 hcf.getCodeName().equals(QuadSSA.codename) ||
142 salcianu 1.7 hcf.getCodeName().equals(QuadSSI.codename) :
143 salcianu 1.5 "Cannot work with " + hcf.getCodeName();
144 salcianu 1.5
145 salcianu 1.7 ssx_form =
146 salcianu 1.7 hcf.getCodeName().equals(QuadSSA.codename) ||
147 salcianu 1.7 hcf.getCodeName().equals(QuadSSI.codename);
148 salcianu 1.7
149 salcianu 1.5 System.out.println("MetaCallGraphImpl started with " +
150 salcianu 1.8 hcf.getCodeName() + " ssx = " + ssx_form +
151 salcianu 1.8 (COLL_HACK ? "COLL_HACK" : ""));
152 salcianu 1.5
153 salcianu 1.1.2.28 this.hcf = hcf;
154 salcianu 1.1.2.28 this.ch = ch;
155 salcianu 1.8 this.linker = linker;
156 salcianu 1.8 init_class_handlers();
157 salcianu 1.8
158 salcianu 1.8 build_meta_call_graph(hmroots);
159 salcianu 1.8 // convert the big format (Set oriented) into the compact one (arrays)
160 salcianu 1.8 compact();
161 salcianu 1.8 // clean up temporary data to free up some space
162 salcianu 1.8 cleanup_temp_data();
163 salcianu 1.8 }
164 salcianu 1.8
165 salcianu 1.8
166 salcianu 1.8 private void build_meta_call_graph(Set hmroots) {
167 salcianu 1.8 compute_instantiated_classes();
168 salcianu 1.8
169 salcianu 1.8 if(COLL_HACK)
170 salcianu 1.8 init_coll_hack();
171 salcianu 1.8
172 salcianu 1.8 if(COUNTER)
173 salcianu 1.8 System.out.println();
174 salcianu 1.8
175 salcianu 1.8 // analyze all the roots
176 salcianu 1.8 for(Iterator it = hmroots.iterator(); it.hasNext(); )
177 salcianu 1.8 analyze(new MetaMethod((HMethod) it.next(), true));
178 salcianu 1.8
179 salcianu 1.8 if(COLL_HACK) {
180 salcianu 1.8 // remove some unrealizable edges from the call graph
181 salcianu 1.8 trim_call_graph();
182 salcianu 1.8 // print some debug info
183 salcianu 1.8 if(DEBUG_COLL_HACK)
184 salcianu 1.8 print_coll_hack_debug();
185 salcianu 1.8 }
186 salcianu 1.8 }
187 salcianu 1.8
188 salcianu 1.8
189 salcianu 1.8 private void cleanup_temp_data() {
190 salcianu 1.8 // activate the GC
191 salcianu 1.8 callees1 = null;
192 salcianu 1.8 callees2 = null;
193 salcianu 1.8 this.ch = null;
194 salcianu 1.8 this.hcf = null;
195 salcianu 1.8 cleanup_class_handlers();
196 salcianu 1.8
197 salcianu 1.8 ets2et = null;
198 salcianu 1.8 mh2md = null;
199 salcianu 1.8 param_types = null;
200 salcianu 1.8
201 salcianu 1.8 // null these out so that we can serialize the object [CSA]
202 salcianu 1.8 // (alternatively, could mark all of these as 'transient')
203 salcianu 1.8 qvis_dd = null;
204 salcianu 1.8 qvis_ti = null;
205 salcianu 1.8 ets2et = null;
206 salcianu 1.8 ets_test = null;
207 salcianu 1.8 implementers = null;
208 salcianu 1.8 kids = null;
209 salcianu 1.8 instantiated_classes = null;
210 salcianu 1.8
211 salcianu 1.8 if(COLL_HACK)
212 salcianu 1.8 cleanup_coll_hack();
213 salcianu 1.8
214 salcianu 1.8 // okay, now garbage-collect.
215 salcianu 1.8 System.gc();
216 salcianu 1.8 }
217 salcianu 1.8
218 salcianu 1.8
219 salcianu 1.8 private void init_class_handlers() {
220 salcianu 1.8 jl_Thread = linker.forName("java.lang.Thread");
221 salcianu 1.8 jl_Runnable = linker.forName("java.lang.Runnable");
222 salcianu 1.8 jl_RuntimeException = linker.forName("java.lang.RuntimeException");
223 salcianu 1.8 jl_Error = linker.forName("java.lang.Error");
224 salcianu 1.8 }
225 salcianu 1.8
226 salcianu 1.8 private void cleanup_class_handlers() {
227 salcianu 1.8 jl_Thread = null;
228 salcianu 1.8 jl_Runnable = null;
229 salcianu 1.8 jl_RuntimeException = null;
230 salcianu 1.8 jl_Error = null;
231 salcianu 1.8 }
232 salcianu 1.8
233 salcianu 1.1.2.9
234 salcianu 1.8 private void compute_instantiated_classes() {
235 salcianu 1.1.2.24 // HACK: Normally, the call graph and the set instantiated_classes
236 salcianu 1.1.2.24 // should be computed simultaneously; we use the ClassHierarchy
237 salcianu 1.1.2.24 // to get the latter.
238 salcianu 1.5 // For any type T such that a "new T" might be executed, there is at
239 salcianu 1.1.2.24 // least one method of T executed. So, we can approximate the set
240 salcianu 1.1.2.24 // of actually instantiated classes by looking at the declaring
241 salcianu 1.1.2.24 // class of all callable methods.
242 salcianu 1.1.2.24 instantiated_classes = new HashSet();
243 salcianu 1.1.2.24 Set old_ic = ch.instantiatedClasses();
244 cananian 1.12 for(Object hmO : ch.callableMethods()) {
245 cananian 1.12 HMethod hm = (HMethod) hmO;
246 salcianu 1.1.2.24 if(Modifier.isStatic(hm.getModifiers())) continue;
247 salcianu 1.1.2.24 HClass hclass = hm.getDeclaringClass();
248 salcianu 1.1.2.24 if(Modifier.isAbstract(hclass.getModifiers())) continue;
249 salcianu 1.1.2.24 if(old_ic.contains(hclass))
250 salcianu 1.1.2.24 instantiated_classes.add(hclass);
251 salcianu 1.1.2.24 }
252 salcianu 1.1.2.24 // however, there is an exception: the arrays (they are objects too)
253 cananian 1.12 for(Object hclassO : ch.instantiatedClasses()) {
254 cananian 1.12 HClass hclass = (HClass) hclassO;
255 salcianu 1.1.2.24 if(hclass.isArray())
256 salcianu 1.1.2.24 instantiated_classes.add(hclass);
257 salcianu 1.1.2.24 }
258 salcianu 1.1.2.24
259 salcianu 1.1.2.24 if(DEBUG_CH) {
260 salcianu 1.1.2.24 Set cls = instantiated_classes;
261 salcianu 1.1.2.24 System.out.println("INSTANTIATED CLASS(ES) (" +
262 salcianu 1.1.2.24 cls.size() + ") : {");
263 salcianu 1.1.2.24 for(Iterator it = cls.iterator(); it.hasNext(); )
264 salcianu 1.1.2.24 System.out.println(" " + ((HClass) it.next()));
265 salcianu 1.1.2.24 System.out.println("}");
266 salcianu 1.1.2.24 }
267 salcianu 1.8 }
268 salcianu 1.1.2.24
269 salcianu 1.1.2.1
270 salcianu 1.1.2.1 // Converts the big format (Set oriented) into the compact one (arrays)
271 salcianu 1.1.2.1 // Takes the data from callees1(2) and puts it into callees1(2)_cmpct
272 salcianu 1.8 private void compact() {
273 cananian 1.12 for(Object mmO : callees1.keys()) {
274 cananian 1.12 MetaMethod mm = (MetaMethod) mmO;
275 salcianu 1.1.2.21 Set callees = callees1.getValues(mm);
276 salcianu 1.1.2.1 MetaMethod[] mms =
277 salcianu 1.1.2.1 (MetaMethod[]) callees.toArray(new MetaMethod[callees.size()]);
278 salcianu 1.1.2.25 if(DETERMINISTIC)
279 salcianu 1.1.2.25 Arrays.sort(mms, UComp.uc);
280 salcianu 1.1.2.25 callees1_cmpct.put(mm, mms);
281 salcianu 1.1.2.1 }
282 salcianu 1.1.2.1
283 cananian 1.12 for(Object mmO : callees2.keySet()) {
284 cananian 1.12 MetaMethod mm = (MetaMethod) mmO;
285 salcianu 1.1.2.1 Relation rel = (Relation) callees2.get(mm);
286 salcianu 1.1.2.1 Map map_cmpct = (Map) callees2_cmpct.get(mm);
287 salcianu 1.1.2.1 if(map_cmpct == null)
288 salcianu 1.1.2.1 callees2_cmpct.put(mm,map_cmpct = new HashMap());
289 cananian 1.12 for(Object csO : rel.keys()){
290 cananian 1.12 CALL cs = (CALL) csO;
291 salcianu 1.1.2.1 // cees is the set of callees in "mm" at call site "cs".
292 salcianu 1.1.2.21 Set cees = rel.getValues(cs);
293 salcianu 1.1.2.1 MetaMethod[] mms =
294 salcianu 1.1.2.1 (MetaMethod[]) cees.toArray(new MetaMethod[cees.size()]);
295 salcianu 1.1.2.25 if(DETERMINISTIC)
296 salcianu 1.1.2.25 Arrays.sort(mms, UComp.uc);
297 salcianu 1.1.2.25 map_cmpct.put(cs, mms);
298 salcianu 1.1.2.1 }
299 salcianu 1.1.2.1 }
300 salcianu 1.1.2.1 }
301 salcianu 1.1.2.1
302 salcianu 1.1.2.1 // Relation<MetaMethod, MetaMethod> stores the association between
303 salcianu 1.1.2.1 // the caller and its callees
304 salcianu 1.1.2.24 private Relation callees1 = new RelationImpl();
305 salcianu 1.1.2.1
306 salcianu 1.1.2.1 // Map<MetaMethod,Relation<CALL,MetaMethod>> stores the association
307 salcianu 1.1.2.1 // between the caller and its calees at a specific call site
308 salcianu 1.1.2.1 private Map callees2 = new HashMap();
309 salcianu 1.1.2.1
310 salcianu 1.1.2.9 // Build up the meta call graph, starting from a "root" method.
311 salcianu 1.1.2.9 // The classic example of a root method is "main", but there could
312 salcianu 1.1.2.9 // be others called by the JVM before main.
313 salcianu 1.8 private void analyze(HMethod root) {
314 salcianu 1.8 if(COLL_HACK && root.equals(hm_HashtablePut)) {
315 salcianu 1.8 if(DEBUG_COLL_HACK)
316 salcianu 1.8 System.out.println("COLL_HACK: treat Hashtable.put: " +
317 salcianu 1.8 "java.util.Properties x String x String");
318 salcianu 1.8
319 salcianu 1.8 GenType hashmap_gt =
320 salcianu 1.8 new GenType(linker.forName("java.util.Properties"),
321 salcianu 1.8 GenType.MONO);
322 salcianu 1.8 GenType key_gt =
323 salcianu 1.8 new GenType(linker.forName("java.lang.String"), GenType.POLY);
324 salcianu 1.8 GenType value_gt = key_gt;
325 salcianu 1.8 GenType[] gts = new GenType[]{hashmap_gt, key_gt, value_gt};
326 salcianu 1.8 analyze(new MetaMethod(root, gts));
327 salcianu 1.8
328 salcianu 1.8 return;
329 salcianu 1.8 }
330 salcianu 1.8
331 salcianu 1.1.2.9 // we are extremely conservative: a root method could be called
332 salcianu 1.1.2.9 // with any subtypes for its arguments, so we treat it as a
333 salcianu 1.1.2.9 // polymorphic one.
334 salcianu 1.8 analyze(new MetaMethod(root, true));
335 salcianu 1.1.2.1 }
336 salcianu 1.1.2.1
337 salcianu 1.8
338 salcianu 1.1.2.1 private PAWorkList WMM = null;
339 salcianu 1.1.2.1 private Set analyzed_mm = null;
340 salcianu 1.1.2.1 private MetaMethod mm_work = null;
341 salcianu 1.1.2.1
342 salcianu 1.1.2.9 private int mm_count = 0;
343 salcianu 1.1.2.9
344 salcianu 1.1.2.1 private void analyze(MetaMethod root_mm){
345 salcianu 1.1.2.9 if(COUNTER)
346 salcianu 1.1.2.26 System.out.print(root_mm + " ");
347 salcianu 1.1.2.9
348 salcianu 1.1.2.1 analyzed_mm = new HashSet();
349 salcianu 1.1.2.1 WMM = new PAWorkList();
350 salcianu 1.1.2.1 WMM.add(root_mm);
351 salcianu 1.1.2.1 while(!WMM.isEmpty()){
352 salcianu 1.1.2.1 mm_work = (MetaMethod) WMM.remove();
353 salcianu 1.1.2.9
354 salcianu 1.8 /*
355 salcianu 1.8 if(COLL_HACK == true)
356 salcianu 1.8 coll_hack_examine_method(mm_work);
357 salcianu 1.8 */
358 salcianu 1.8
359 salcianu 1.5 if(COUNTER) {
360 salcianu 1.1.2.9 mm_count++;
361 salcianu 1.1.2.26 if(mm_count % 10 == 0)
362 salcianu 1.1.2.26 System.out.print(".");
363 salcianu 1.1.2.9 }
364 salcianu 1.1.2.9
365 salcianu 1.1.2.1 analyzed_mm.add(mm_work);
366 salcianu 1.1.2.1 analyze_meta_method();
367 salcianu 1.1.2.1 }
368 salcianu 1.5
369 salcianu 1.1.2.1 all_meta_methods.addAll(analyzed_mm);
370 salcianu 1.1.2.9
371 salcianu 1.8 // enable some GC!
372 salcianu 1.8 analyzed_mm = null;
373 salcianu 1.8 WMM = null;
374 salcianu 1.8 mm_work = null;
375 salcianu 1.8
376 salcianu 1.1.2.9 if(COUNTER)
377 salcianu 1.1.2.26 System.out.println(" " + mm_count + " analyzed meta-method(s)");
378 salcianu 1.1.2.1 }
379 salcianu 1.1.2.1
380 salcianu 1.5 private Collection calls = null;
381 salcianu 1.1.2.1
382 salcianu 1.1.2.24 private void analyze_meta_method() {
383 salcianu 1.9 if(DEBUG)
384 salcianu 1.1.2.24 System.out.println("\n\n%%: " + mm_work);
385 salcianu 1.1.2.1
386 salcianu 1.1.2.1 HMethod hm = mm_work.getHMethod();
387 salcianu 1.1.2.1
388 salcianu 1.1.2.1 // native method, no code for analysis -> return immediately
389 salcianu 1.1.2.1 if(Modifier.isNative(hm.getModifiers())) return;
390 salcianu 1.1.2.1
391 salcianu 1.1.2.24 MethodData md = get_method_data(hm);
392 salcianu 1.1.2.24 ets2et = md.ets2et;
393 salcianu 1.1.2.24 calls = md.calls;
394 salcianu 1.1.2.1
395 salcianu 1.7 if(DEBUG)
396 salcianu 1.7 display_mm_data(mm_work);
397 salcianu 1.1.2.1
398 salcianu 1.5 set_parameter_types(mm_work, hcf.convert(hm));
399 salcianu 1.1.2.1
400 salcianu 1.13 compute_types(md.sccs);
401 salcianu 1.1.2.1 analyze_calls();
402 salcianu 1.1.2.1
403 salcianu 1.1.2.3 // before quiting this meta-method, remove the types we computed
404 salcianu 1.1.2.3 // for the ExactTemps. The component graph of ExactTemps (and so,
405 salcianu 1.1.2.24 // the ExactTemps themselves) is specific to an HMethod and so,
406 salcianu 1.1.2.3 // they can be shared by many meta-methods derived from the same
407 salcianu 1.1.2.3 // HMethod. Of course, I don't want the next analyzed meta-method
408 salcianu 1.1.2.3 // to use the types computed for this one.
409 salcianu 1.15 for(SCComponent scc : md.sccs)
410 salcianu 1.15 for(Object ets0 : scc.nodes())
411 salcianu 1.15 ((ExactTemp) ets0).clearTypeSet();
412 salcianu 1.1.2.1 }
413 salcianu 1.1.2.1
414 salcianu 1.1.2.1
415 salcianu 1.1.2.1 // after the types of all the interesting ExactTemps are known,
416 salcianu 1.1.2.1 // examine each call site from this metamethod and build the
417 salcianu 1.1.2.1 // meta-call-graph.
418 salcianu 1.1.2.1 private void analyze_calls(){
419 salcianu 1.1.2.1 for(Iterator it_calls = calls.iterator();it_calls.hasNext();)
420 salcianu 1.1.2.1 analyze_one_call((CALL) it_calls.next());
421 salcianu 1.1.2.1 }
422 salcianu 1.1.2.1
423 salcianu 1.1.2.1 ////// "analyze_one_call" related stuff BEGIN ==========
424 salcianu 1.1.2.1
425 salcianu 1.1.2.1 // Records the fact that mcaller could call mcallee at the call site cs.
426 salcianu 1.1.2.1 private void record_call(MetaMethod mcaller, CALL cs, MetaMethod mcallee){
427 salcianu 1.1.2.1 callees1.add(mcaller,mcallee);
428 salcianu 1.1.2.1 Relation rel = (Relation) callees2.get(mcaller);
429 salcianu 1.1.2.1 if(rel == null)
430 salcianu 1.1.2.24 callees2.put(mcaller,rel = new RelationImpl());
431 salcianu 1.1.2.1 rel.add(cs,mcallee);
432 salcianu 1.1.2.1 }
433 salcianu 1.1.2.1
434 salcianu 1.1.2.1 // the specialized types will be stored here.
435 salcianu 1.1.2.1 private GenType[] param_types = null;
436 salcianu 1.1.2.1
437 salcianu 1.1.2.1 // counts the number of metamethods called at a "virtual" call site.
438 salcianu 1.1.2.1 private int nb_meta_methods;
439 salcianu 1.1.2.1
440 salcianu 1.1.2.1 // determine the exact meta-method which is called at the call site "cs",
441 salcianu 1.1.2.1 // based on the specialized types found in "param_types".
442 salcianu 1.5 private void specialize_the_call(HMethod hm, CALL cs) {
443 salcianu 1.5 if(DEBUG) {
444 salcianu 1.5 System.out.println("hm = " + hm);
445 salcianu 1.5 System.out.println("cs = " + cs);
446 salcianu 1.5 System.out.print("param_types = [ ");
447 salcianu 1.5 for(int i = 0; i < param_types.length ; i++)
448 salcianu 1.5 System.out.print(param_types[i] + " ");
449 salcianu 1.5 System.out.println("]");
450 salcianu 1.5 }
451 salcianu 1.8
452 salcianu 1.8 if(COLL_HACK)
453 salcianu 1.8 coll_hack_fix_params(hm, cs);
454 salcianu 1.8
455 salcianu 1.8 MetaMethod mm_callee = new MetaMethod(hm, param_types);
456 salcianu 1.5 nb_meta_methods++;
457 salcianu 1.5 record_call(mm_work, cs, mm_callee);
458 salcianu 1.8 if(!analyzed_mm.contains(mm_callee)) {
459 salcianu 1.8
460 salcianu 1.8 // TODO: MOVE it TO THE WMM loop
461 salcianu 1.8 if(COLL_HACK == true)
462 salcianu 1.8 coll_hack_examine_method(mm_callee);
463 salcianu 1.8
464 salcianu 1.5 WMM.add(mm_callee);
465 salcianu 1.8 }
466 salcianu 1.8 }
467 salcianu 1.8
468 salcianu 1.8
469 salcianu 1.8 // COLL_HACK methods BEGIN
470 salcianu 1.8
471 salcianu 1.8 // HashSet is implemented as a HashMap where all values are equal
472 salcianu 1.8 // to a preallocated Object. Therefore, when Map.put is called
473 salcianu 1.8 // from HashSet, the second parameter is not any Object, but
474 salcianu 1.8 // exactly Object. If we were able to infere the concrete types
475 salcianu 1.8 // stored in object fields, this hack wouldn't be necessary :)
476 salcianu 1.8 // TODO: implement a real analysis for field concrete types
477 salcianu 1.8 private void coll_hack_fix_params(HMethod hm, CALL cs) {
478 salcianu 1.8 HMethod caller = mm_work.getHMethod();
479 salcianu 1.8
480 salcianu 1.8 assert hm != null;
481 salcianu 1.8 assert caller != null;
482 salcianu 1.8 assert jl_Map != null;
483 salcianu 1.8 assert jl_Object != null;
484 salcianu 1.8
485 salcianu 1.8 if(caller.getDeclaringClass().equals(ju_HashSet) &&
486 salcianu 1.8 hm.getName().equals("put") &&
487 salcianu 1.8 jl_Map.isSuperinterfaceOf(hm.getDeclaringClass()))
488 salcianu 1.8 param_types[2] = new GenType(jl_Object, GenType.MONO);
489 salcianu 1.1.2.1 }
490 salcianu 1.1.2.1
491 salcianu 1.8
492 salcianu 1.8 private void coll_hack_examine_method(MetaMethod mm) {
493 salcianu 1.8 if(// Collection.add(ELEMENT);
494 salcianu 1.8 test_coll(mm, "java.util.Collection", "add", 1, 1) ||
495 salcianu 1.8 // Map.put(KEY, value);
496 salcianu 1.8 test_coll(mm, "java.util.Map", "put", 2, 1) ||
497 salcianu 1.8 // Map.put(key, VALUE);
498 salcianu 1.8 test_coll(mm, "java.util.Map", "put", 2, 2) ||
499 salcianu 1.8 // List.add(index, ELEMENT);
500 salcianu 1.8 test_coll(mm, "java.util.List", "add", 2, 2) ||
501 salcianu 1.8 // Vector.addElement(ELEMENT);
502 salcianu 1.8 test_coll(mm, "java.util.Vector", "addElement", 1, 1) ||
503 salcianu 1.8 // Vector.copyInto(ELEMENT[]);
504 salcianu 1.8 test_coll2(mm, "java.util.Vector", "copyInto", 1, 1)) {
505 salcianu 1.8 // you can put some debug message here
506 salcianu 1.8 }
507 salcianu 1.8 }
508 salcianu 1.8
509 salcianu 1.8 private boolean test_coll2(MetaMethod mm, String cls, String mthd,
510 salcianu 1.8 int arity, int index) {
511 salcianu 1.8
512 salcianu 1.8 if(!is_this_method(mm, cls, mthd, arity))
513 salcianu 1.8 return false;
514 salcianu 1.8
515 salcianu 1.8 GenType gt = mm.getType(index);
516 salcianu 1.8 HClass hclass = gt.getHClass();
517 salcianu 1.8
518 salcianu 1.8 assert hclass.getComponentType() == null :
519 salcianu 1.8 "mm.getType(index) is expected to be an array: " + mm;
520 salcianu 1.8
521 salcianu 1.8 Set els =
522 salcianu 1.8 get_instantiated_children(new GenType(hclass, GenType.POLY));
523 salcianu 1.8 put_in_colls.addAll(els);
524 salcianu 1.8
525 salcianu 1.8 if(mthd.equals("put"))
526 salcianu 1.8 if(index == 1) keys_put_in_maps.addAll(els);
527 salcianu 1.8 else if(index == 2) values_put_in_maps.addAll(els);
528 salcianu 1.8 else assert false : "unexpected index " + index;
529 salcianu 1.8
530 salcianu 1.8 return
531 salcianu 1.8 intersect(els, inst_colls);
532 salcianu 1.8 }
533 salcianu 1.8
534 salcianu 1.8
535 salcianu 1.8 // Checks whether mm corresponds to a method called "mthd" from a
536 salcianu 1.8 // subclass of "cls" and having "arity" arguments.
537 salcianu 1.8 private boolean is_this_method(MetaMethod mm, String cls, String mthd,
538 salcianu 1.8 int arity) {
539 salcianu 1.8 HMethod hm = mm.getHMethod();
540 salcianu 1.8
541 salcianu 1.8 if(hm.isStatic() ||
542 salcianu 1.8 !hm.getName().equals(mthd) ||
543 salcianu 1.8 (hm.getParameterNames().length != arity)) return false;
544 salcianu 1.8
545 salcianu 1.8 // name2colls stores the most popular classes
546 salcianu 1.8 HClass hcoll = (HClass) name2coll.get(cls);
547 salcianu 1.8
548 salcianu 1.8 if(hcoll == null)
549 salcianu 1.8 hcoll = linker.forName(cls);
550 salcianu 1.8
551 salcianu 1.8 return
552 salcianu 1.8 ((hcoll.isInterface() &&
553 salcianu 1.8 hcoll.isSuperinterfaceOf(hm.getDeclaringClass()))
554 salcianu 1.8 ||
555 salcianu 1.8 (!hcoll.isInterface() &&
556 salcianu 1.8 hcoll.isSuperclassOf(hm.getDeclaringClass())));
557 salcianu 1.8 }
558 salcianu 1.8
559 salcianu 1.8
560 salcianu 1.8 // Checks whether mm is a method of a subclass of "cls", has name
561 salcianu 1.8 // "mthd", arity "arity" and param_types[index] might be a
562 salcianu 1.8 // collection (ie, it implements java.util.Collection or
563 salcianu 1.8 // java.util.Map).
564 salcianu 1.8 //
565 salcianu 1.8 // Also the type of the argument is stored in the appropriate set:
566 salcianu 1.8 // hash keys, hash values and / or collection elements.
567 salcianu 1.8 //
568 salcianu 1.8 // Note: We start counting parameters from 1 (0 is this).
569 salcianu 1.8 private boolean test_coll(MetaMethod mm, String cls, String mthd,
570 salcianu 1.8 int arity, int index) {
571 salcianu 1.8 if(!is_this_method(mm, cls, mthd, arity))
572 salcianu 1.8 return false;
573 salcianu 1.8
574 salcianu 1.8 GenType gt = mm.getType(index);
575 salcianu 1.8
576 salcianu 1.8 System.out.println
577 salcianu 1.8 ("test_coll:\n\t mm = " + mm + "\n\t gt = " + gt);
578 salcianu 1.8
579 salcianu 1.8 Set els = get_instantiated_children(gt);
580 salcianu 1.8 if(put_in_colls.addAll(els)) {
581 salcianu 1.8 System.out.println
582 salcianu 1.8 ("COLL_HACK: new put_in_colls:" +
583 salcianu 1.8 "\n caller = " + mm_work +
584 salcianu 1.8 "\n callee = " + mm +
585 salcianu 1.8 "\n index = " + index +
586 salcianu 1.8 "\n els = " + els);
587 salcianu 1.8 }
588 salcianu 1.8
589 salcianu 1.8 if(mthd.equals("put"))
590 salcianu 1.8 if(index == 1) keys_put_in_maps.addAll(els);
591 salcianu 1.8 else if(index == 2) values_put_in_maps.addAll(els);
592 salcianu 1.8 else assert false : "unexpected index " + index;
593 salcianu 1.8
594 salcianu 1.8 return
595 salcianu 1.8 intersect(els, inst_colls);
596 salcianu 1.8 }
597 salcianu 1.8
598 salcianu 1.8 // auxiliary data for COLL_HACK
599 salcianu 1.8 private static Map name2coll = null;
600 salcianu 1.8 // instr_collections = inst_colls + inst_maps
601 salcianu 1.8 private static Set inst_colls = null;
602 salcianu 1.8 // Set of types put into collections: maps, sets, lists etc.
603 salcianu 1.8 private Set put_in_colls;
604 salcianu 1.8 // Set of types used as keys in maps
605 salcianu 1.8 private Set keys_put_in_maps;
606 salcianu 1.8 // Set of types used as values in maps
607 salcianu 1.8 private Set values_put_in_maps;
608 salcianu 1.8
609 salcianu 1.8
610 salcianu 1.8 // initialize data structs used by COLL_HACK activated code
611 salcianu 1.8 private void init_coll_hack() {
612 salcianu 1.8
613 salcianu 1.8 jl_Object = linker.forName("java.lang.Object");
614 salcianu 1.8 ju_HashSet = linker.forName("java.util.HashSet");
615 salcianu 1.8
616 salcianu 1.8 hm_HashtablePut =
617 salcianu 1.8 linker.forName("java.util.Hashtable").
618 salcianu 1.8 getMethod("put", new HClass[] {jl_Object, jl_Object});
619 salcianu 1.8
620 salcianu 1.8 assert hm_HashtablePut != null;
621 salcianu 1.8
622 salcianu 1.8 name2coll = new HashMap();
623 salcianu 1.8 inst_colls = new HashSet();
624 salcianu 1.8 for(int i = 0; i < relv_colls.length; i++) {
625 salcianu 1.8 HClass hclass = linker.forName(relv_colls[i]);
626 salcianu 1.8 inst_colls.addAll(get_instantiated_children(hclass));
627 salcianu 1.8 name2coll.put(relv_colls[i], hclass);
628 salcianu 1.8 }
629 salcianu 1.8 put_in_colls = new HashSet();
630 salcianu 1.8 keys_put_in_maps = new HashSet();
631 salcianu 1.8 values_put_in_maps = new HashSet();
632 salcianu 1.8
633 salcianu 1.8 jl_Collection = (HClass) name2coll.get("java.util.Collection");
634 salcianu 1.8 jl_Map = (HClass) name2coll.get("java.util.Map");
635 salcianu 1.8
636 salcianu 1.8 if(DEBUG_COLL_HACK)
637 salcianu 1.8 Util.print_collection(inst_colls, "Inst. collections");
638 salcianu 1.8
639 cananian 1.12 for(Object collO : inst_colls) {
640 cananian 1.12 HClass coll = (HClass) collO;
641 salcianu 1.8 if(!"java.util".equals(coll.getPackage())) {
642 salcianu 1.8 System.out.println
643 salcianu 1.8 ("COLL_HACK: Non java.util collections created: " +
644 salcianu 1.8 coll + "\n\t=> COLL_HACK turned off!");
645 salcianu 1.8 COLL_HACK = false;
646 salcianu 1.8 }
647 salcianu 1.8 }
648 salcianu 1.8 }
649 salcianu 1.8 private static String[] relv_colls = {
650 salcianu 1.8 "java.util.Collection", "java.util.Map",
651 salcianu 1.8 "java.util.List", "java.util.Vector"
652 salcianu 1.8 };
653 salcianu 1.8
654 salcianu 1.8 private HClass jl_Collection;
655 salcianu 1.8 private HClass jl_Map;
656 salcianu 1.8 private HClass ju_HashSet;
657 salcianu 1.8
658 salcianu 1.8 private void cleanup_coll_hack() {
659 salcianu 1.8 name2coll = null;
660 salcianu 1.8 inst_colls = null;
661 salcianu 1.8 put_in_colls = null;
662 salcianu 1.8 keys_put_in_maps = null;
663 salcianu 1.8 values_put_in_maps = null;
664 salcianu 1.8 jl_Object = null;
665 salcianu 1.8 ju_HashSet = null;
666 salcianu 1.8 hm_HashtablePut = null;
667 salcianu 1.8 jl_Collection = null;
668 salcianu 1.8 jl_Map = null;
669 salcianu 1.8 map_upcalls = null;
670 salcianu 1.8 coll_upcalls = null;
671 salcianu 1.8 }
672 salcianu 1.8
673 salcianu 1.8 // checks whether set1 and set2 have a common element
674 salcianu 1.8 private boolean intersect(Set set1, Set set2) {
675 salcianu 1.8 for(Iterator it = set1.iterator(); it.hasNext(); )
676 salcianu 1.8 if(set2.contains(it.next()))
677 salcianu 1.8 return true;
678 salcianu 1.8 return false;
679 salcianu 1.8 }
680 salcianu 1.8
681 salcianu 1.8
682 salcianu 1.8 private void trim_call_graph() {
683 salcianu 1.8 if(DEBUG_COLL_HACK)
684 salcianu 1.8 System.out.println("\nCOLL_HACK: trim_call_graph");
685 salcianu 1.8
686 salcianu 1.8 init_upcalls_sets();
687 salcianu 1.8
688 cananian 1.12 for(Object mmO : all_meta_methods) {
689 cananian 1.12 MetaMethod mm = (MetaMethod) mmO;
690 salcianu 1.8 Set upcalls = allowed_upcalls_methods(mm.getHMethod());
691 salcianu 1.8 // upcalls == nulls means mm is not a collection method
692 salcianu 1.8 // any upcalls are possible
693 salcianu 1.8 if(upcalls == null)
694 salcianu 1.8 continue;
695 salcianu 1.8
696 salcianu 1.8 trim_callees(mm, upcalls);
697 salcianu 1.8 }
698 salcianu 1.8 }
699 salcianu 1.8
700 salcianu 1.8 private void trim_callees(MetaMethod mm, Set upcalls) {
701 salcianu 1.8 if(!callees2.containsKey(mm))
702 salcianu 1.8 return;
703 salcianu 1.8
704 salcianu 1.8 Relation rel = (Relation) callees2.get(mm);
705 salcianu 1.8 Set calls = new HashSet(rel.keys());
706 cananian 1.12 for(Object csO : calls) {
707 cananian 1.12 CALL cs = (CALL) csO;
708 salcianu 1.8 // non-virtual call sites cannot be trimmed
709 salcianu 1.8 if(!cs.isVirtual())
710 salcianu 1.8 continue;
711 salcianu 1.8 Set to_remove = new HashSet();
712 cananian 1.12 for(Object mm_calleeO : rel.getValues(cs)) {
713 cananian 1.12 MetaMethod mm_callee = (MetaMethod) mm_calleeO;
714 salcianu 1.8 HMethod hm_callee = mm_callee.getHMethod();
715 salcianu 1.8 if((hm_callee.getName().equals("equals") ||
716 salcianu 1.8 hm_callee.getName().equals("hashCode")) &&
717 salcianu 1.8 !upcalls.contains(hm_callee))
718 salcianu 1.8 to_remove.add(mm_callee);
719 salcianu 1.8 }
720 salcianu 1.8 rel.removeAll(cs, to_remove);
721 salcianu 1.8 }
722 salcianu 1.8
723 salcianu 1.8 // computes in callees the set of all mm's callees
724 salcianu 1.8 Set callees = new HashSet();
725 cananian 1.12 for(Object csO : calls) {
726 cananian 1.12 CALL cs = (CALL) csO;
727 salcianu 1.8 callees.addAll(rel.getValues(cs));
728 salcianu 1.8 }
729 salcianu 1.8
730 salcianu 1.8 // update callees1
731 salcianu 1.8 callees1.removeKey(mm); // 1. remove all old methods
732 salcianu 1.8 callees1.addAll(mm, callees); // 2. add new ones (fewer)
733 salcianu 1.8 }
734 salcianu 1.8
735 salcianu 1.8
736 salcianu 1.8 // "equals" & "hashCode" methods that may NOT be called from
737 salcianu 1.8 // collections = complement of equals/hashCode methods of classes
738 salcianu 1.8 // from put_in_colls
739 salcianu 1.8 private Set coll_upcalls;
740 salcianu 1.8 // "equals" & "hashCode" methods that may NOT be called from maps
741 salcianu 1.8 // = complement of equals/hashCode methods of classes from
742 salcianu 1.8 // keys/values_put_in_maps
743 salcianu 1.8 private Set map_upcalls;
744 salcianu 1.8
745 salcianu 1.8 // initialize the sets collection_upcalls and map_upcalls
746 salcianu 1.8 private void init_upcalls_sets() {
747 salcianu 1.8 HClass[] empty_args = new HClass[0];
748 salcianu 1.8 HClass[] one_obj = new HClass[]{jl_Object};
749 salcianu 1.8
750 salcianu 1.8 coll_upcalls = new HashSet();
751 salcianu 1.8 map_upcalls = new HashSet();
752 salcianu 1.8
753 cananian 1.12 for(Object hclassO : instantiated_classes) {
754 cananian 1.12 HClass hclass = (HClass) hclassO;
755 salcianu 1.8 if(put_in_colls.contains(hclass)) {
756 salcianu 1.8 coll_upcalls.add(hclass.getMethod("equals", one_obj));
757 salcianu 1.8 coll_upcalls.add(hclass.getMethod("hashCode", empty_args));
758 salcianu 1.8 }
759 salcianu 1.8 }
760 salcianu 1.8
761 cananian 1.12 for(Object hclassO : instantiated_classes) {
762 cananian 1.12 HClass hclass = (HClass) hclassO;
763 salcianu 1.8 if(keys_put_in_maps.contains(hclass) ||
764 salcianu 1.8 values_put_in_maps.contains(hclass)) {
765 salcianu 1.8 map_upcalls.add(hclass.getMethod("equals", one_obj));
766 salcianu 1.8 map_upcalls.add(hclass.getMethod("hashCode", empty_args));
767 salcianu 1.8 }
768 salcianu 1.8 }
769 salcianu 1.8
770 salcianu 1.8 if(DEBUG_COLL_HACK) {
771 salcianu 1.8 Util.print_collection(coll_upcalls, "coll_upcalls");
772 salcianu 1.8 Util.print_collection(map_upcalls, "map_upcalls");
773 salcianu 1.8 }
774 salcianu 1.8 }
775 salcianu 1.8
776 salcianu 1.8 // returns the set of methods that cannot be called from hm
777 salcianu 1.8 private Set allowed_upcalls_methods(HMethod hm) {
778 salcianu 1.8 HClass hclass = hm.getDeclaringClass();
779 salcianu 1.8
780 salcianu 1.8 if(jl_Map.isSuperinterfaceOf(hclass) &&
781 salcianu 1.8 "java.util".equals(hclass.getPackage()))
782 salcianu 1.8 return map_upcalls;
783 salcianu 1.8 else if((jl_Collection.isSuperinterfaceOf(hclass)) &&
784 salcianu 1.8 "java.util".equals(hclass.getPackage()))
785 salcianu 1.8 return coll_upcalls;
786 salcianu 1.8 else
787 salcianu 1.8 return null;
788 salcianu 1.8 }
789 salcianu 1.8
790 salcianu 1.8 private void print_coll_hack_debug() {
791 salcianu 1.8 Util.print_collection(put_in_colls, "COLL_HACK: Put into collections");
792 salcianu 1.8 Util.print_collection(keys_put_in_maps, "COLL_HACK: Map keys");
793 salcianu 1.8 Util.print_collection(values_put_in_maps, "COLL_HACK: Map values");
794 salcianu 1.8 }
795 salcianu 1.8
796 salcianu 1.8 // COLL_HACK methods END
797 salcianu 1.8
798 salcianu 1.1.2.1 // "rec" generates all the possible combinations of types for the
799 salcianu 1.1.2.1 // parameters of "hm", generates metamethods, records the caller-callee
800 salcianu 1.1.2.1 // interactions and add the new metamethods to the worklist of metamethods.
801 salcianu 1.1.2.1 private void rec(HMethod hm, CALL cs, int pos, int max_pos){
802 salcianu 1.1.2.1 if(pos == max_pos){
803 salcianu 1.1.2.1 // all the types have been specialized
804 salcianu 1.1.2.1 specialize_the_call(hm,cs);
805 salcianu 1.1.2.1 return;
806 salcianu 1.1.2.1 }
807 salcianu 1.1.2.1
808 salcianu 1.1.2.1 if(cs.paramType(pos).isPrimitive()){
809 salcianu 1.5 param_types[pos] = new GenType(cs.paramType(pos), GenType.MONO);
810 salcianu 1.5 rec(hm, cs, pos+1, max_pos);
811 salcianu 1.1.2.1 return;
812 salcianu 1.1.2.1 }
813 salcianu 1.1.2.1
814 salcianu 1.1.2.24 // For any possible ExactType T of the pos-th param, set
815 salcianu 1.1.2.24 // param_types[pos] to it and recurse on the remaining params.
816 salcianu 1.1.2.24 ExactTemp et = getExactTemp(cs.params(pos), cs, ExactTemp.USE);
817 salcianu 1.1.2.24
818 salcianu 1.5 assert !et.getTypeSet().isEmpty() :
819 salcianu 1.5 "\nNo possible type detected for " + et.t +
820 salcianu 1.5 "\n in method " + cs.getFactory().getMethod() +
821 salcianu 1.5 "\n at instr " + cs.getSourceFile() + ":" +
822 salcianu 1.5 cs.getLineNumber() + " " + cs;
823 salcianu 1.1.2.24
824 salcianu 1.1.2.24 for(Iterator it_types = et.getTypes(); it_types.hasNext(); ) {
825 salcianu 1.1.2.24 GenType gt = (GenType) it_types.next();
826 salcianu 1.1.2.24 param_types[pos] = gt;
827 salcianu 1.1.2.24 rec(hm, cs, pos+1, max_pos);
828 salcianu 1.1.2.1 }
829 salcianu 1.5
830 salcianu 1.1.2.1 }
831 salcianu 1.1.2.1
832 salcianu 1.1.2.23
833 salcianu 1.1.2.1 // Checks whether calling "hm" starts a thread or not.
834 salcianu 1.1.2.1 private boolean thread_start_site(HMethod hm){
835 salcianu 1.1.2.1 String name = hm.getName();
836 salcianu 1.1.2.1 if(hm.getParameterNames().length != 0) return false;
837 salcianu 1.1.2.1 if((name==null) || !name.equals("start")) return false;
838 salcianu 1.1.2.1 if(hm.isStatic()) return false;
839 salcianu 1.1.2.1 HClass hclass = hm.getDeclaringClass();
840 salcianu 1.1.2.1 return hclass.getName().equals("java.lang.Thread");
841 salcianu 1.1.2.1 }
842 salcianu 1.1.2.1
843 salcianu 1.1.2.1 // Examine a possible thread start site
844 salcianu 1.1.2.13 private boolean check_thread_start_site(CALL cs){
845 salcianu 1.1.2.13 if(!thread_start_site(cs.method())) return false;
846 salcianu 1.1.2.1
847 salcianu 1.1.2.23 boolean found_a_run = false;
848 salcianu 1.1.2.23
849 salcianu 1.1.2.24 // etbase.t points to the receiver class
850 salcianu 1.1.2.24 ExactTemp etbase = getExactTemp(cs.params(0), cs, ExactTemp.USE);
851 salcianu 1.1.2.13
852 salcianu 1.1.2.24 for(Iterator it_gt = etbase.getTypes(); it_gt.hasNext(); ) {
853 salcianu 1.1.2.24 GenType gt = (GenType) it_gt.next();
854 salcianu 1.1.2.24 Set cls = gt.isPOLY() ?
855 salcianu 1.1.2.24 get_instantiated_children(gt.getHClass()) :
856 salcianu 1.1.2.24 Collections.singleton(gt.getHClass());
857 salcianu 1.1.2.24
858 salcianu 1.1.2.24 for(Iterator it_cls = cls.iterator(); it_cls.hasNext(); ) {
859 salcianu 1.1.2.24 boolean hr = has_a_run(cs, (HClass) it_cls.next());
860 salcianu 1.1.2.24 found_a_run = found_a_run || hr;
861 salcianu 1.1.2.13 }
862 salcianu 1.1.2.1 }
863 salcianu 1.1.2.23
864 salcianu 1.1.2.23 // The 2nd possibility of launching a thread a Java: calling
865 salcianu 1.1.2.23 // start() on a Thread object that doesn't implement run() but
866 salcianu 1.1.2.23 // points to a Runnable object.
867 salcianu 1.1.2.23 // We have to do a very conservative analysis here: examine ANY
868 salcianu 1.1.2.23 // object that implements Runnable and take its run method.
869 salcianu 1.1.2.23
870 salcianu 1.1.2.24 Set runnables = get_instantiated_children(jl_Runnable);
871 salcianu 1.1.2.23 for(Iterator it_cls = runnables.iterator(); it_cls.hasNext(); ) {
872 salcianu 1.1.2.23 boolean hr = has_a_run(cs, (HClass) it_cls.next());
873 salcianu 1.1.2.23 found_a_run = found_a_run || hr;
874 salcianu 1.1.2.23 }
875 salcianu 1.1.2.13
876 cananian 1.3.2.1 assert found_a_run : "No run method was found for " + cs;
877 salcianu 1.1.2.13
878 salcianu 1.1.2.13 return true;
879 salcianu 1.1.2.1 }
880 salcianu 1.1.2.1
881 salcianu 1.1.2.23 // Check if hclass has a "run" method. If positive, this method
882 salcianu 1.1.2.23 // could be started as a thread body; it must be put in the meta method
883 salcianu 1.1.2.23 // worklist if it hasn't been seen before.
884 salcianu 1.1.2.23 private boolean has_a_run(CALL cs, HClass hclass){
885 salcianu 1.1.2.1 HMethod run = null;
886 salcianu 1.1.2.1
887 salcianu 1.1.2.1 HMethod[] hms = hclass.getMethods();
888 salcianu 1.1.2.1 for(int i = 0; i < hms.length ; i++){
889 salcianu 1.1.2.1 if(!hms[i].getName().equals("run")) continue;
890 salcianu 1.1.2.1 int modifs = hms[i].getModifiers();
891 salcianu 1.1.2.1 if(Modifier.isAbstract(modifs) ||
892 salcianu 1.1.2.1 Modifier.isStatic(modifs) ||
893 salcianu 1.1.2.1 Modifier.isNative(modifs) ||
894 salcianu 1.1.2.1 !Modifier.isPublic(modifs)) continue;
895 salcianu 1.1.2.1 if(hms[i].getParameterNames().length != 0) continue;
896 salcianu 1.1.2.1 run = hms[i];
897 salcianu 1.1.2.1 break;
898 salcianu 1.1.2.1 }
899 salcianu 1.1.2.1
900 salcianu 1.1.2.23 if(run == null) return false;
901 salcianu 1.1.2.1
902 salcianu 1.1.2.1 // create a new MetaMethod corresponding to the run method and try
903 salcianu 1.1.2.1 // to put it into the worklist if it's really new.
904 salcianu 1.1.2.1 GenType gtbase = new GenType(hclass,GenType.MONO);
905 salcianu 1.1.2.1 MetaMethod mm = new MetaMethod(run,new GenType[]{gtbase});
906 salcianu 1.1.2.1 if(!analyzed_mm.contains(mm))
907 salcianu 1.1.2.1 WMM.add(mm);
908 salcianu 1.1.2.12
909 salcianu 1.1.2.13 run_mms.add(mm);
910 salcianu 1.1.2.1
911 salcianu 1.1.2.23 // if(DEBUG)
912 salcianu 1.1.2.26 System.out.println("\nTHREAD START SITE:" +
913 salcianu 1.1.2.13 cs.getSourceFile() + ":" +
914 salcianu 1.1.2.13 cs.getLineNumber() + " " +
915 salcianu 1.1.2.13 cs + " => " + mm);
916 salcianu 1.1.2.23 return true;
917 salcianu 1.1.2.1 }
918 salcianu 1.1.2.1
919 salcianu 1.1.2.24 private long call_time = 0L;
920 salcianu 1.1.2.24 private int nb_calls = 0;
921 salcianu 1.1.2.24 private int nb_big_calls = 0;
922 salcianu 1.1.2.24
923 salcianu 1.1.2.1 // analyze the CALL site "cs" inside the MetaMethod "mm".
924 salcianu 1.1.2.24 private void analyze_one_call(CALL cs) {
925 salcianu 1.1.2.1 HMethod hm = cs.method();
926 salcianu 1.1.2.1 int nb_params = cs.paramsLength();
927 salcianu 1.1.2.1 param_types = new GenType[nb_params];
928 salcianu 1.1.2.1
929 salcianu 1.8 if(DEBUG)
930 salcianu 1.8 System.out.println("$$:analyze_call(" + cs + ")");
931 salcianu 1.1.2.1
932 salcianu 1.1.2.1 // for 'special' invocations, we know the method exactly
933 salcianu 1.8 if(!cs.isVirtual() || cs.isStatic()) {
934 salcianu 1.1.2.1 if(DEBUG) System.out.println("//: " + cs);
935 salcianu 1.1.2.23 if(Modifier.isNative(hm.getModifiers()))
936 salcianu 1.1.2.23 check_thread_start_site(cs);
937 salcianu 1.1.2.1 rec(hm,cs,0,nb_params);
938 salcianu 1.1.2.1 return;
939 salcianu 1.1.2.1 }
940 salcianu 1.1.2.1
941 salcianu 1.8 check_thread_start_site(cs);
942 salcianu 1.8
943 salcianu 1.1.2.1 // for native methods, specialization doesn't make any sense
944 salcianu 1.1.2.1 // because we cannot analyze their body.
945 salcianu 1.8 if(TOUGH_ON_NATIVES && Modifier.isNative(hm.getModifiers())) {
946 salcianu 1.8 param_types[0] =
947 salcianu 1.8 new GenType(hm.getDeclaringClass(), GenType.POLY);
948 salcianu 1.1.2.1 HClass[] types = hm.getParameterTypes();
949 salcianu 1.1.2.1 for(int i = 0; i < types.length; i++)
950 salcianu 1.1.2.1 param_types[i+1] = new GenType(types[i],GenType.POLY);
951 salcianu 1.1.2.15 specialize_the_call(hm, cs);
952 salcianu 1.1.2.1 return;
953 salcianu 1.1.2.1 }
954 salcianu 1.1.2.1
955 salcianu 1.1.2.1 nb_meta_methods = 0;
956 salcianu 1.1.2.1
957 salcianu 1.1.2.1 if(nb_params == 0)
958 cananian 1.3.2.1 assert false : "Non static method with no parameters " + cs;
959 salcianu 1.1.2.1
960 salcianu 1.1.2.1 // the first parameter (the method receiver) must be treated specially
961 salcianu 1.1.2.24 ExactTemp etbase = getExactTemp(cs.params(0), cs, ExactTemp.USE);
962 salcianu 1.1.2.24 if(CAUTION && etbase.getTypeSet().isEmpty())
963 cananian 1.3.2.1 assert false : "No possible type detected for " + etbase;
964 salcianu 1.1.2.1
965 salcianu 1.1.2.24 boolean poly = false;
966 salcianu 1.1.2.1
967 salcianu 1.1.2.24 long start = time();
968 salcianu 1.1.2.24
969 salcianu 1.1.2.24 for(Iterator it_types = etbase.getTypes(); it_types.hasNext(); ) {
970 salcianu 1.1.2.24 GenType gt = (GenType) it_types.next();
971 salcianu 1.1.2.24 if(gt.isPOLY()) {
972 salcianu 1.1.2.24 poly = true;
973 salcianu 1.1.2.24 treat_poly_base(hm, cs, gt);
974 salcianu 1.1.2.1 }
975 salcianu 1.1.2.24 else
976 salcianu 1.1.2.24 treat_mono_base(hm, cs, gt);
977 salcianu 1.1.2.1 }
978 salcianu 1.1.2.1
979 salcianu 1.1.2.24 call_time += time() - start;
980 salcianu 1.1.2.24 nb_calls++;
981 salcianu 1.1.2.24
982 salcianu 1.1.2.1 if(DEBUG)
983 salcianu 1.1.2.1 System.out.println("||: " + cs + " calls " + nb_meta_methods +
984 salcianu 1.1.2.1 " meta-method(s)");
985 salcianu 1.1.2.1
986 salcianu 1.1.2.24 if(DEBUG_CH && (nb_meta_methods == 0)) {
987 salcianu 1.1.2.24 System.out.println("ALARM!<\n" + " mm = " + mm_work +
988 salcianu 1.1.2.24 "\n " +
989 salcianu 1.1.2.24 (poly ? "POLY" : "MONO") +
990 salcianu 1.10 " cs = " + Util.code2str(cs) +
991 salcianu 1.1.2.24 "> 0 callees!");
992 salcianu 1.1.2.24 // display the SCC of exact temps and their types
993 salcianu 1.1.2.24 display_mm_data(mm_work);
994 salcianu 1.1.2.3 }
995 salcianu 1.1.2.3
996 salcianu 1.1.2.1 param_types = null; // enable the GC
997 salcianu 1.1.2.1 }
998 salcianu 1.1.2.1
999 salcianu 1.1.2.24 private void display_mm_data(MetaMethod mm) {
1000 salcianu 1.1.2.24 HMethod hm = mm_work.getHMethod();
1001 salcianu 1.1.2.24 MethodData md = get_method_data(hm);
1002 salcianu 1.7 System.out.println("\n\nDATA FOR " + mm_work + ":");
1003 salcianu 1.1.2.24 System.out.println(md);
1004 salcianu 1.7 System.out.println("\nCOMPUTED TYPES:");
1005 salcianu 1.14 for(SCComponent scc : md.sccs) {
1006 salcianu 1.15 for(Object etO : scc.nodes()) {
1007 cananian 1.12 ExactTemp et = (ExactTemp) etO;
1008 salcianu 1.1.2.24 System.out.println("< " + et.t + ", " +
1009 salcianu 1.13 ((et.ud == ExactTemp.USE) ? "USE" : "DEF") +
1010 salcianu 1.10 ", " + Util.code2str(et.q) +
1011 salcianu 1.1.2.24 " > has type(s) {");
1012 salcianu 1.1.2.24 for(Iterator it2 = et.getTypes(); it2.hasNext(); )
1013 salcianu 1.1.2.24 System.out.println("\t" + ((GenType) it2.next()));
1014 salcianu 1.1.2.24 System.out.println("}");
1015 salcianu 1.1.2.24 }
1016 salcianu 1.13 }
1017 salcianu 1.1.2.24
1018 salcianu 1.7 System.out.println("\nCODE:");
1019 salcianu 1.1.2.28 HCode hcode = hcf.convert(hm);
1020 salcianu 1.1.2.24 hcode.print(new java.io.PrintWriter(System.out, true));
1021 salcianu 1.1.2.24 System.out.println("--------------------------------------");
1022 salcianu 1.1.2.24 }
1023 salcianu 1.1.2.24
1024 salcianu 1.1.2.24
1025 salcianu 1.1.2.1 // Treat the case of a polymorphic type for the receiver of the method hm
1026 salcianu 1.1.2.24 private void treat_poly_base(HMethod hm, CALL cs, GenType gt) {
1027 salcianu 1.1.2.24 Set classes = get_possible_classes(gt.getHClass(), hm);
1028 salcianu 1.1.2.24
1029 salcianu 1.1.2.24 // compute the set of objects that actually provide an
1030 salcianu 1.1.2.24 // implementation for the method hm
1031 salcianu 1.1.2.24 implementers.clear();
1032 salcianu 1.1.2.24 nb_cls = 0;
1033 cananian 1.12 for(Object cO : classes) {
1034 cananian 1.12 HClass c = (HClass) cO;
1035 salcianu 1.1.2.1 // fix some strange bug
1036 salcianu 1.1.2.1 if(c.isPrimitive()) continue;
1037 salcianu 1.1.2.24 HMethod callee = c.getMethod(hm.getName(), hm.getDescriptor());
1038 salcianu 1.1.2.24 HClass dc = callee.getDeclaringClass();
1039 salcianu 1.1.2.24 implementers.add(dc);
1040 salcianu 1.1.2.24 cls[nb_cls] = c;
1041 salcianu 1.1.2.24 impl[nb_cls] = dc;
1042 salcianu 1.1.2.24 nb_cls++;
1043 salcianu 1.1.2.24 }
1044 salcianu 1.1.2.24
1045 salcianu 1.1.2.24 nb_big_calls++;
1046 salcianu 1.1.2.24
1047 cananian 1.12 for(Object cO : implementers) {
1048 cananian 1.12 HClass c = (HClass) cO;
1049 salcianu 1.1.2.24 HMethod callee = c.getMethod(hm.getName(), hm.getDescriptor());
1050 salcianu 1.1.2.24
1051 salcianu 1.1.2.24 nb_kids = 0;
1052 salcianu 1.1.2.24 for(int i = 0; i < nb_cls; i++)
1053 salcianu 1.1.2.24 if(c.equals(impl[i]))
1054 salcianu 1.1.2.24 kids[nb_kids++] = cls[i];
1055 salcianu 1.1.2.24
1056 salcianu 1.1.2.24 if(nb_kids > SPEC_BOUND) {
1057 salcianu 1.1.2.24 param_types[0] = new GenType(c, GenType.POLY);
1058 salcianu 1.1.2.24 rec(callee, cs, 1, cs.paramsLength());
1059 salcianu 1.1.2.24 }
1060 salcianu 1.1.2.24 else {
1061 salcianu 1.1.2.24 for(int i = 0; i < nb_kids; i++) {
1062 salcianu 1.1.2.24 param_types[0] = new GenType(kids[i], GenType.MONO);
1063 salcianu 1.1.2.24 rec(callee, cs, 1, cs.paramsLength());
1064 salcianu 1.1.2.24 }
1065 salcianu 1.1.2.24 }
1066 salcianu 1.1.2.1 }
1067 salcianu 1.1.2.1 }
1068 salcianu 1.1.2.24 private Set implementers = new HashSet();
1069 salcianu 1.1.2.24 private HClass kids[] = new HClass[1000];
1070 salcianu 1.1.2.24 private int nb_kids = 0;
1071 salcianu 1.1.2.24 private HClass cls[] = new HClass[1000];
1072 salcianu 1.1.2.24 private HClass impl[] = new HClass[1000];
1073 salcianu 1.1.2.24 private int nb_cls = 0;
1074 salcianu 1.1.2.24
1075 salcianu 1.1.2.24 // Returns the set of all the instantiated (sub)classes of root
1076 salcianu 1.1.2.24 // (including root) that implement the method "hm".
1077 salcianu 1.1.2.24 private Set get_possible_classes(HClass root, HMethod hm) {
1078 salcianu 1.1.2.24 Set children =
1079 salcianu 1.1.2.24 get_instantiated_children(root);
1080 salcianu 1.8
1081 salcianu 1.1.2.1 Set possible_classes = new HashSet();
1082 salcianu 1.1.2.1
1083 cananian 1.12 for(Object cO : children) {
1084 cananian 1.12 HClass c = (HClass) cO;
1085 salcianu 1.1.2.24 if(Modifier.isAbstract(c.getModifiers()))
1086 salcianu 1.1.2.24 continue;
1087 salcianu 1.1.2.1 boolean implemented = true;
1088 salcianu 1.1.2.1 HMethod callee = null;
1089 salcianu 1.1.2.1 try{
1090 salcianu 1.1.2.24 callee = c.getMethod(hm.getName(), hm.getDescriptor());
1091 salcianu 1.1.2.1 }catch(NoSuchMethodError nsme){
1092 salcianu 1.1.2.1 implemented = false;
1093 salcianu 1.1.2.1 }
1094 salcianu 1.1.2.1 if(implemented && !Modifier.isAbstract(callee.getModifiers()))
1095 salcianu 1.1.2.1 possible_classes.add(c);
1096 salcianu 1.1.2.1 }
1097 salcianu 1.1.2.1
1098 salcianu 1.1.2.1 return possible_classes;
1099 salcianu 1.1.2.1 }
1100 salcianu 1.8
1101 salcianu 1.8 private Set get_instantiated_children(GenType gt) {
1102 salcianu 1.8 HClass hclass = gt.getHClass();
1103 salcianu 1.8 if(gt.isPOLY())
1104 salcianu 1.8 return get_instantiated_children(hclass);
1105 salcianu 1.8 else if(instantiated_classes.contains(hclass))
1106 salcianu 1.8 return Collections.singleton(hclass);
1107 salcianu 1.8 else
1108 salcianu 1.8 return Collections.EMPTY_SET;
1109 salcianu 1.8 }
1110 salcianu 1.1.2.1
1111 salcianu 1.1.2.1 // Returns the set of all the subclasses of class root that could
1112 salcianu 1.1.2.1 // be instantiated by the program.
1113 salcianu 1.1.2.24 Set get_instantiated_children(HClass root){
1114 salcianu 1.1.2.1 Set children = new HashSet();
1115 salcianu 1.1.2.1 PAWorkList Wc = new PAWorkList();
1116 salcianu 1.1.2.1 Wc.add(root);
1117 salcianu 1.1.2.24 while(!Wc.isEmpty()) {
1118 salcianu 1.1.2.1 HClass c = (HClass) Wc.remove();
1119 salcianu 1.1.2.24 if(instantiated_classes.contains(c))
1120 salcianu 1.1.2.1 children.add(c);
1121 salcianu 1.1.2.24 for(Iterator it = ch.children(c).iterator(); it.hasNext(); )
1122 salcianu 1.1.2.24 Wc.add(it.next());
1123 salcianu 1.1.2.1 }
1124 salcianu 1.1.2.1 return children;
1125 salcianu 1.1.2.1 }
1126 salcianu 1.1.2.1
1127 salcianu 1.1.2.1 // Treat the case of a monomorphyc type for the receiver of the method hm
1128 salcianu 1.1.2.24 private void treat_mono_base(HMethod hm, CALL cs, GenType gt) {
1129 salcianu 1.1.2.1 HClass c = gt.getHClass();
1130 salcianu 1.1.2.3 // fix some strange bug: HClass.Void keeps appearing here!
1131 salcianu 1.1.2.1 if(c.isPrimitive()) return;
1132 salcianu 1.1.2.24
1133 salcianu 1.1.2.24 //System.out.println("SMALL call " + cs);
1134 salcianu 1.1.2.24
1135 salcianu 1.1.2.1 HMethod callee = null;
1136 salcianu 1.1.2.1 boolean implements_hm = true;
1137 salcianu 1.1.2.1 try{
1138 salcianu 1.1.2.24 callee = c.getMethod(hm.getName(), hm.getDescriptor());
1139 salcianu 1.1.2.1 }
1140 salcianu 1.1.2.1 catch(NoSuchMethodError nsme){
1141 salcianu 1.1.2.24 System.out.println("treat_mono_base: " +
1142 salcianu 1.10 Util.code2str(cs) + " " + nsme);
1143 salcianu 1.1.2.1 implements_hm = false;
1144 salcianu 1.1.2.1 }
1145 salcianu 1.1.2.24
1146 salcianu 1.1.2.24 //System.out.println(" callee = " + callee);
1147 salcianu 1.1.2.24
1148 salcianu 1.1.2.1 if(implements_hm && !Modifier.isAbstract(callee.getModifiers())){
1149 salcianu 1.1.2.1 param_types[0] = gt;
1150 salcianu 1.1.2.24 rec(callee, cs, 1, cs.paramsLength());
1151 salcianu 1.1.2.1 }
1152 salcianu 1.1.2.1 }
1153 salcianu 1.1.2.1
1154 salcianu 1.1.2.1 ////// "analyze_one_call" related stuff END ===========
1155 salcianu 1.1.2.1
1156 salcianu 1.1.2.24
1157 salcianu 1.1.2.24 // Computes the set of the exact temps we are interested in
1158 salcianu 1.1.2.24 // (the arguments of the CALLs from the code of the analyzed method).
1159 salcianu 1.5 private final Set get_initial_set(ReachingDefs rdef, Collection calls) {
1160 salcianu 1.1.2.24 Set initial_set = new HashSet();
1161 cananian 1.12 for(Object qO : calls) {
1162 cananian 1.12 CALL q = (CALL) qO;
1163 salcianu 1.1.2.1 int nb_params = q.paramsLength();
1164 salcianu 1.1.2.1 for(int i = 0; i < nb_params; i++)
1165 salcianu 1.1.2.24 if(!q.paramType(i).isPrimitive()) {
1166 salcianu 1.1.2.1 Temp t = q.params(i);
1167 salcianu 1.1.2.24 initial_set.add(getExactTemp(t, q, ExactTemp.USE));
1168 salcianu 1.1.2.1 }
1169 salcianu 1.1.2.1 }
1170 salcianu 1.1.2.24
1171 salcianu 1.1.2.24 return initial_set;
1172 salcianu 1.1.2.1 }
1173 salcianu 1.1.2.1
1174 salcianu 1.1.2.1 // Data attached to a method
1175 salcianu 1.1.2.24 private class MethodData {
1176 salcianu 1.13 // The SCCs (in decreasing topological order)
1177 salcianu 1.14 List<SCComponent/*<??>*/> sccs;
1178 salcianu 1.1.2.24 // The ets2et map for this method (see the comments around ets2et)
1179 salcianu 1.1.2.1 Map ets2et;
1180 salcianu 1.1.2.24 // The set of CALL quads occuring in the code of the method
1181 salcianu 1.5 Collection calls;
1182 salcianu 1.1.2.24
1183 salcianu 1.14 MethodData(List<SCComponent/*<>*/> sccs,
1184 salcianu 1.13 Map ets2et, Collection calls) {
1185 salcianu 1.13 this.sccs = sccs;
1186 salcianu 1.1.2.1 this.ets2et = ets2et;
1187 salcianu 1.1.2.24 this.calls = calls;
1188 salcianu 1.1.2.24 }
1189 salcianu 1.1.2.24
1190 salcianu 1.1.2.24 public String toString() {
1191 salcianu 1.1.2.24 StringBuffer buff = new StringBuffer();
1192 salcianu 1.1.2.24 buff.append("SCC(s):\n" );
1193 salcianu 1.14 for(SCComponent scc : sccs) {
1194 salcianu 1.1.2.24 buff.append(scc.toString());
1195 salcianu 1.1.2.24 }
1196 salcianu 1.1.2.24 buff.append("CALL(s):");
1197 salcianu 1.1.2.24 for(Iterator it = calls.iterator(); it.hasNext(); )
1198 salcianu 1.1.2.24 buff.append("\n " + it.next().toString());
1199 salcianu 1.1.2.24 return buff.toString();
1200 salcianu 1.1.2.1 }
1201 salcianu 1.1.2.1 }
1202 salcianu 1.1.2.1
1203 salcianu 1.7 // return an appropriate impl. of ReachingDefs for hcode
1204 salcianu 1.7 private ReachingDefs getReachingDefsImpl(HCode hcode) {
1205 salcianu 1.7 if(ssx_form)
1206 salcianu 1.7 return new SSxReachingDefsImpl(hcode);
1207 salcianu 1.7 else
1208 salcianu 1.7 return new ReachingDefsImpl(hcode);
1209 salcianu 1.7 }
1210 salcianu 1.7
1211 salcianu 1.1.2.1 // Map<HMethod,MethodData>
1212 salcianu 1.1.2.1 private Map mh2md = new HashMap();
1213 salcianu 1.1.2.1 // Adds some caching over "compute_md".
1214 salcianu 1.8 private MethodData get_method_data(HMethod hm) {
1215 salcianu 1.1.2.1 MethodData md = (MethodData) mh2md.get(hm);
1216 salcianu 1.5 if(md == null) { // if not in the cache, build it from scratch
1217 salcianu 1.1.2.28 HCode hcode = hcf.convert(hm);
1218 salcianu 1.5 Collection calls = ((Code) hcode).selectCALLs();
1219 salcianu 1.1.2.1 // initialize the ets2et map (see the comments near its definition)
1220 salcianu 1.1.2.24 ets2et = new HashMap();
1221 salcianu 1.7 ReachingDefs rdef = getReachingDefsImpl(hcode);
1222 salcianu 1.14 md = new MethodData(compute_sccs(get_initial_set(rdef, calls),
1223 salcianu 1.14 rdef),
1224 salcianu 1.14 ets2et, calls);
1225 salcianu 1.1.2.24 mh2md.put(hm, md);
1226 salcianu 1.1.2.1 }
1227 salcianu 1.1.2.1 return md;
1228 salcianu 1.1.2.1 }
1229 salcianu 1.1.2.1
1230 salcianu 1.1.2.1
1231 salcianu 1.1.2.24 // an "exact" temp: the Temp "t" defined in the Quad "q"
1232 salcianu 1.1.2.24 private class ExactTemp {
1233 salcianu 1.1.2.24
1234 salcianu 1.1.2.24 Temp t; // the Temp t that is
1235 salcianu 1.1.2.24 int ud; // defined/used in
1236 salcianu 1.1.2.24 Quad q; // quad q
1237 salcianu 1.1.2.24
1238 salcianu 1.1.2.24 static final int DEF = 0;
1239 salcianu 1.1.2.24 static final int USE = 1;
1240 salcianu 1.1.2.1
1241 salcianu 1.1.2.1 // Set<GenType> - the possible types of this ExactTemp.
1242 salcianu 1.1.2.24 Set gtypes;
1243 salcianu 1.1.2.1
1244 salcianu 1.1.2.24 // The ExactTemps whose types are influenced by the type of this one.
1245 salcianu 1.1.2.1 ExactTemp[] next = new ExactTemp[0];
1246 salcianu 1.1.2.24 // The ExactTemps whose types influence the type of this one.
1247 salcianu 1.1.2.1 ExactTemp[] prev = new ExactTemp[0];
1248 salcianu 1.1.2.1
1249 salcianu 1.1.2.24 ExactTemp(Temp t, Quad q, int ud){
1250 salcianu 1.1.2.24 this.t = t;
1251 salcianu 1.1.2.24 this.q = q;
1252 salcianu 1.1.2.24 this.ud = ud;
1253 salcianu 1.1.2.24 this.gtypes = new HashSet();
1254 salcianu 1.1.2.1 }
1255 salcianu 1.1.2.1
1256 salcianu 1.1.2.1 /** Returns an iterator over the set of all the possible types
1257 salcianu 1.1.2.1 for <code>this</code> <code>ExactTemp</code>. */
1258 salcianu 1.1.2.3 Iterator getTypes(){
1259 salcianu 1.1.2.1 return gtypes.iterator();
1260 salcianu 1.1.2.1 }
1261 salcianu 1.1.2.1
1262 salcianu 1.1.2.1 /** Returns the set of all the possible types
1263 salcianu 1.1.2.1 for <code>this</code> <code>ExactTemp</code>. */
1264 salcianu 1.1.2.3 Set getTypeSet(){
1265 salcianu 1.1.2.1 return gtypes;
1266 salcianu 1.1.2.1 }
1267 salcianu 1.1.2.1
1268 salcianu 1.1.2.3 /** Clears the set of possible types for <code>this</code> ExactTemp.*/
1269 salcianu 1.1.2.3 void clearTypeSet(){
1270 salcianu 1.1.2.3 gtypes.clear();
1271 salcianu 1.1.2.3 }
1272 salcianu 1.1.2.3
1273 salcianu 1.1.2.1 /** Adds the type <code>gt</code> to the set of possible
1274 salcianu 1.1.2.1 types for <code>this</code> <code>ExactTemp</code>. */
1275 salcianu 1.1.2.1 void addType(GenType type){
1276 salcianu 1.1.2.1
1277 salcianu 1.1.2.1 if(type.isPOLY()){
1278 salcianu 1.1.2.1 // TODO : add some caching here
1279 salcianu 1.1.2.24 Set children = get_instantiated_children(type.getHClass());
1280 salcianu 1.1.2.1 if(children.size() == 1)
1281 salcianu 1.1.2.1 type = new GenType((HClass)children.iterator().next(),
1282 salcianu 1.1.2.1 GenType.MONO);
1283 salcianu 1.1.2.1 }
1284 salcianu 1.1.2.1
1285 salcianu 1.5 List to_remove = new LinkedList();
1286 salcianu 1.1.2.1
1287 cananian 1.12 for(Object gtO : gtypes){
1288 cananian 1.12 GenType gt = (GenType) gtO;
1289 salcianu 1.5 // no new information here
1290 salcianu 1.5 if(type.included(gt, ch))
1291 salcianu 1.1.2.1 return;
1292 salcianu 1.5 // the new information we add makes some old one redundant
1293 salcianu 1.5 if(gt.included(type, ch))
1294 salcianu 1.1.2.1 to_remove.add(type);
1295 salcianu 1.1.2.1 }
1296 salcianu 1.1.2.1
1297 salcianu 1.5 for(Iterator it = to_remove.iterator(); it.hasNext(); )
1298 salcianu 1.5 gtypes.remove((GenType) it.next());
1299 salcianu 1.1.2.1
1300 salcianu 1.1.2.1 gtypes.add(type);
1301 salcianu 1.1.2.1 }
1302 salcianu 1.1.2.1
1303 salcianu 1.1.2.1 /** Adds the types from the set <code>gts</code> to the set of possible
1304 salcianu 1.1.2.1 types for <code>this</code> <code>ExactTemp</code>. */
1305 salcianu 1.1.2.1 void addTypes(Set gts){
1306 salcianu 1.1.2.1 for(Iterator it = gts.iterator(); it.hasNext();)
1307 salcianu 1.1.2.1 addType((GenType) it.next());
1308 salcianu 1.1.2.1 }
1309 salcianu 1.1.2.1
1310 salcianu 1.1.2.3 String shortDescription(){
1311 salcianu 1.1.2.24 return "<" + t.toString() + ", " +
1312 salcianu 1.1.2.24 ((ud == ExactTemp.DEF) ? "DEF" : "USE") + ", " +
1313 salcianu 1.10 Util.code2str(q) + ">";
1314 salcianu 1.1.2.1 }
1315 salcianu 1.1.2.1
1316 salcianu 1.1.2.1 public String toString(){
1317 salcianu 1.1.2.1 StringBuffer buffer = new StringBuffer();
1318 salcianu 1.1.2.1 buffer.append(shortDescription());
1319 salcianu 1.1.2.1 if((next.length == 0) && (prev.length == 0)){
1320 salcianu 1.1.2.1 buffer.append("\n");
1321 salcianu 1.1.2.1 return buffer.toString();
1322 salcianu 1.1.2.1 }
1323 salcianu 1.1.2.1 buffer.append("(\n");
1324 salcianu 1.1.2.1 if(next.length > 0){
1325 salcianu 1.1.2.24 buffer.append("The following defs depends on this one:\n");
1326 salcianu 1.1.2.1 for(int i = 0 ; i < next.length ; i++)
1327 salcianu 1.1.2.1 buffer.append(" " +
1328 salcianu 1.1.2.1 (next[i]==null?"null":
1329 salcianu 1.1.2.1 next[i].shortDescription()) + "\n");
1330 salcianu 1.1.2.1 }
1331 salcianu 1.1.2.1 if(prev.length > 0){
1332 salcianu 1.1.2.24 buffer.append("Depends on the following defs:\n");
1333 salcianu 1.1.2.1 for(int i = 0 ; i < prev.length ; i++)
1334 salcianu 1.1.2.1 buffer.append(" " + prev[i].shortDescription() + "\n");
1335 salcianu 1.1.2.1 }
1336 salcianu 1.1.2.1 buffer.append(")");
1337 salcianu 1.1.2.1 return buffer.toString();
1338 salcianu 1.1.2.1 }
1339 salcianu 1.1.2.1 }
1340 salcianu 1.1.2.1
1341 salcianu 1.1.2.1
1342 salcianu 1.1.2.1 ////// DEPENDENCY DETECTION (getDependencies) - BEGIN
1343 salcianu 1.1.2.1
1344 salcianu 1.1.2.24 // Quad visitor class for the dependency detection. This class is
1345 salcianu 1.1.2.24 // declared here (and not inside getDependencies as it were more elegant)
1346 salcianu 1.1.2.24 // such that we are able to allocate a single QuadVisitorDD for the
1347 salcianu 1.1.2.24 // entire meta call graph construction (instead of one for each analyzed
1348 salcianu 1.1.2.24 // ExactTemp).
1349 salcianu 1.1.2.24 private class QuadVisitorDD extends QuadVisitor {
1350 salcianu 1.1.2.24
1351 salcianu 1.1.2.24 ExactTemp[] deps = null;
1352 salcianu 1.1.2.24 Temp t = null;
1353 salcianu 1.5 int ud = ExactTemp.DEF;
1354 salcianu 1.1.2.24 ReachingDefs rdef = null;
1355 salcianu 1.1.2.24
1356 salcianu 1.1.2.24 public void visit(MOVE q) {
1357 salcianu 1.1.2.24 if(CAUTION && !t.equals(q.dst())) stop_no_def(q);
1358 salcianu 1.1.2.24 add_deps(q.src(), q);
1359 salcianu 1.1.2.24 }
1360 salcianu 1.1.2.24
1361 salcianu 1.1.2.24 public void visit(AGET q) {
1362 salcianu 1.1.2.24 if(CAUTION && !t.equals(q.dst())) stop_no_def(q);
1363 salcianu 1.1.2.24 add_deps(q.objectref(), q);
1364 salcianu 1.1.2.24 }
1365 salcianu 1.1.2.24
1366 salcianu 1.1.2.24 public void visit(CALL q) {
1367 salcianu 1.1.2.24 if(ud == ExactTemp.DEF) {
1368 salcianu 1.5 if(t.equals(q.retval()) || t.equals(q.retex())) {
1369 salcianu 1.5 // t's type will be determined by method signature
1370 salcianu 1.1.2.1 }
1371 salcianu 1.5 else
1372 salcianu 1.5 visit((SIGMA) q);
1373 salcianu 1.5
1374 salcianu 1.1.2.24 return;
1375 salcianu 1.1.2.1 }
1376 salcianu 1.5
1377 salcianu 1.1.2.24 Set rdefs = rdef.reachingDefs(q, t);
1378 salcianu 1.1.2.24 deps = new ExactTemp[rdefs.size()];
1379 salcianu 1.1.2.24 Iterator it = rdefs.iterator();
1380 salcianu 1.1.2.24 for(int i = 0; i < rdefs.size(); i++) {
1381 salcianu 1.1.2.24 Quad qdef = (Quad) it.next();
1382 salcianu 1.1.2.24 deps[i] = getExactTemp(t, qdef, ExactTemp.DEF);
1383 salcianu 1.1.2.1 }
1384 salcianu 1.1.2.24 }
1385 salcianu 1.1.2.24
1386 salcianu 1.1.2.24 public void visit(NEW q) {
1387 salcianu 1.1.2.24 if(CAUTION && !t.equals(q.dst())) stop_no_def(q);
1388 salcianu 1.1.2.24 }
1389 salcianu 1.1.2.24
1390 salcianu 1.1.2.24 public void visit(ANEW q) {
1391 salcianu 1.1.2.24 if(CAUTION && !t.equals(q.dst())) stop_no_def(q);
1392 salcianu 1.1.2.24 }
1393 salcianu 1.1.2.24
1394 salcianu 1.1.2.24 public void visit(TYPECAST q) {
1395 salcianu 1.5 /*
1396 salcianu 1.5 System.out.println
1397 salcianu 1.5 ("\n\ttypecast: " +
1398 salcianu 1.10 harpoon.Analysis.PointerAnalysis.Util.code2str(q) + "\n");
1399 salcianu 1.5 */
1400 salcianu 1.5
1401 salcianu 1.1.2.24 if(CAUTION && !t.equals(q.objectref())) stop_no_def(q);
1402 salcianu 1.1.2.24 }
1403 salcianu 1.1.2.24
1404 salcianu 1.1.2.24 public void visit(GET q) {
1405 salcianu 1.1.2.24 if(CAUTION && !t.equals(q.dst())) stop_no_def(q);
1406 salcianu 1.1.2.24 }
1407 salcianu 1.1.2.24
1408 salcianu 1.1.2.24 public void visit(METHOD q) {
1409 salcianu 1.1.2.24 // do nothing: the type of "et" defined here does not
1410 salcianu 1.1.2.24 // depend on any other ExactType's type.
1411 salcianu 1.5 if(CAUTION) {
1412 salcianu 1.1.2.24 boolean found = false;
1413 salcianu 1.1.2.24 for(int i = 0; i < q.paramsLength(); i++)
1414 salcianu 1.5 if(q.params(i).equals(t)) {
1415 salcianu 1.1.2.24 found = true;
1416 salcianu 1.1.2.24 break;
1417 salcianu 1.1.2.24 }
1418 salcianu 1.1.2.24 if(!found) stop_no_def(q);
1419 salcianu 1.1.2.1 }
1420 salcianu 1.1.2.24 }
1421 salcianu 1.1.2.24
1422 salcianu 1.1.2.24 public void visit(CONST q) {
1423 salcianu 1.1.2.24 if(CAUTION && !t.equals(q.dst())) stop_no_def(q);
1424 salcianu 1.1.2.24 }
1425 salcianu 1.5
1426 salcianu 1.5
1427 salcianu 1.5 // SSI additions BEGIN
1428 salcianu 1.5 public void visit(PHI q) {
1429 salcianu 1.5 int numPhis = q.numPhis();
1430 salcianu 1.5 for(int i = 0; i < numPhis; i++)
1431 salcianu 1.5 if(t.equals(q.dst(i))) {
1432 salcianu 1.5 add_deps(q.src(i), q);
1433 salcianu 1.5 return;
1434 salcianu 1.5 }
1435 salcianu 1.5
1436 salcianu 1.5 stop_no_def(q);
1437 salcianu 1.5 }
1438 salcianu 1.5
1439 salcianu 1.5
1440 salcianu 1.5 // recognize the translation of a TYPECAST in QuadSSI:
1441 salcianu 1.5 // a CJMP t2 preceded by a t2 = t INSTANCEOF hclass; treat it
1442 salcianu 1.5 // as a TYPECAST
1443 salcianu 1.5 public void visit(CJMP q) {
1444 salcianu 1.7 if(ssx_form && (is_typecast(q, t) != null)) {
1445 salcianu 1.5 // do nothing; t's type will be determined by the typecast
1446 salcianu 1.7 }
1447 salcianu 1.7 else if(is_nulltest(q, t)) {
1448 salcianu 1.7 // Once again, do nothing
1449 salcianu 1.7 // t will be null, ie HClass.Void
1450 salcianu 1.5 }
1451 salcianu 1.5 else
1452 salcianu 1.5 visit((SIGMA) q);
1453 salcianu 1.5 }
1454 salcianu 1.5
1455 salcianu 1.5
1456 salcianu 1.5 public void visit(SIGMA q) {
1457 salcianu 1.5 int numSigmas = q.numSigmas();
1458 salcianu 1.5 for(int i = 0; i < numSigmas; i++) {
1459 salcianu 1.5 // src(i) goes into dst(i)[0] ... dst(i)[dst.length-1]
1460 salcianu 1.5 Temp dst[] = q.dst(i);
1461 salcianu 1.5 for(int j = 0; j < dst.length; j++)
1462 salcianu 1.5 if(t.equals(dst[j])) {
1463 salcianu 1.5 add_deps(q.src(i), q);
1464 salcianu 1.5 return;
1465 salcianu 1.5 }
1466 salcianu 1.5 }
1467 salcianu 1.5
1468 salcianu 1.5 stop_no_def(q);
1469 salcianu 1.5 }
1470 salcianu 1.5 // SSI additions END
1471 salcianu 1.5
1472 salcianu 1.1.2.24 // catch the forgotten quads
1473 salcianu 1.1.2.24 public void visit(Quad q) {
1474 salcianu 1.5 assert false : "Unsupported Quad " + q;
1475 salcianu 1.1.2.24 }
1476 salcianu 1.1.2.24
1477 salcianu 1.1.2.24 // crash the system in the most spectacular way
1478 salcianu 1.1.2.24 private void stop_no_def(Quad q) {
1479 cananian 1.3.2.1 assert false : q + " doesn't define " + t;
1480 salcianu 1.1.2.24 }
1481 salcianu 1.1.2.24
1482 salcianu 1.1.2.24 // The Temp "tdep" is used in quad "q" to define "t" and
1483 salcianu 1.1.2.24 // can affect its type. This function qoes along the list
1484 salcianu 1.1.2.24 // of possible definitions for tdep and put the corresponding
1485 salcianu 1.1.2.24 // ExactTemp's in the array of dependencies for <t,q>.
1486 salcianu 1.1.2.24 private void add_deps(Temp tdep, Quad q) {
1487 salcianu 1.5 Set set = new HashSet();
1488 salcianu 1.5 collect_deps(tdep, q, set);
1489 salcianu 1.5 deps = (ExactTemp[]) set.toArray(new ExactTemp[set.size()]);
1490 salcianu 1.5 }
1491 salcianu 1.5
1492 salcianu 1.5 private void add_deps(Temp src[], Quad q) {
1493 salcianu 1.5 Set set = new HashSet();
1494 salcianu 1.5 for(int i = 0; i < src.length; i++)
1495 salcianu 1.5 collect_deps(src[i], q, set);
1496 salcianu 1.5 deps = (ExactTemp[]) set.toArray(new ExactTemp[set.size()]);
1497 salcianu 1.5 }
1498 salcianu 1.5
1499 salcianu 1.5 // collect into set the exact temps that flow into <tdep, q>
1500 salcianu 1.5 private void collect_deps(Temp tdep, Quad q, Set set) {
1501 salcianu 1.1.2.24 Set reaching_defs = rdef.reachingDefs(q, tdep);
1502 salcianu 1.5
1503 salcianu 1.5 assert
1504 salcianu 1.5 !reaching_defs.isEmpty() :
1505 salcianu 1.5 "Temp " + tdep + " in " + q + " has no reaching definition!";
1506 salcianu 1.5
1507 cananian 1.12 for(Object qdefO : reaching_defs) {
1508 cananian 1.12 Quad qdef = (Quad) qdefO;
1509 salcianu 1.5 set.add(getExactTemp(tdep, qdef));
1510 salcianu 1.1.2.1 }
1511 salcianu 1.1.2.24 }
1512 salcianu 1.5
1513 salcianu 1.5
1514 salcianu 1.1.2.24 };
1515 salcianu 1.1.2.24 private QuadVisitorDD qvis_dd = new QuadVisitorDD();
1516 salcianu 1.1.2.1
1517 salcianu 1.5
1518 salcianu 1.5 private void show_deps(ExactTemp et, ExactTemp deps[]) {
1519 salcianu 1.5 System.out.print("\nDeps for " + et.shortDescription() + " = { ");
1520 salcianu 1.5 for(int i = 0; (deps != null) && (i < deps.length); i++)
1521 salcianu 1.5 System.out.print(deps[i].shortDescription() + " ");
1522 salcianu 1.5 System.out.println(" } ");
1523 salcianu 1.5 }
1524 salcianu 1.5
1525 salcianu 1.5
1526 salcianu 1.1.2.1 // Returns all the ExactTemps whose types influence the type of the
1527 salcianu 1.1.2.1 // ExactType et.
1528 salcianu 1.1.2.24 private ExactTemp[] getDependencies(ExactTemp et, ReachingDefs rdef) {
1529 salcianu 1.1.2.24 qvis_dd.t = et.t;
1530 salcianu 1.1.2.24 qvis_dd.ud = et.ud;
1531 salcianu 1.1.2.24 qvis_dd.deps = null;
1532 salcianu 1.1.2.24 qvis_dd.rdef = rdef;
1533 salcianu 1.5
1534 salcianu 1.1.2.24 et.q.accept(qvis_dd);
1535 salcianu 1.5
1536 salcianu 1.1.2.24 if(qvis_dd.deps == null)
1537 salcianu 1.1.2.1 return (new ExactTemp[0]);
1538 salcianu 1.1.2.24 return qvis_dd.deps;
1539 salcianu 1.1.2.1 }
1540 salcianu 1.1.2.1
1541 salcianu 1.5
1542 salcianu 1.5 // Checks whether q corresponds to a typecast that defines t to be
1543 salcianu 1.5 // the restriction of some temp t2 to some class hclass. This means:
1544 salcianu 1.5 // 1. q has a single predecessor: tb = t2 INSTANCEOF hclass
1545 salcianu 1.5 // 2. q has the form CJMP tb
1546 salcianu 1.5 // 3. t is t2 variant on branch 1: < _ , t > = sigma(t2)
1547 salcianu 1.5 // If all these conditions are true, return hclass, o.w. return null
1548 salcianu 1.5 private static HClass is_typecast(CJMP q, Temp t) {
1549 salcianu 1.5 if(q.prevLength() == 1) {
1550 salcianu 1.5 Quad prev = q.prev(0);
1551 salcianu 1.5 if(prev instanceof INSTANCEOF) {
1552 salcianu 1.5 INSTANCEOF inst = (INSTANCEOF) prev;
1553 salcianu 1.6 Temp tb = inst.dst();
1554 salcianu 1.6 if(tb.equals(q.test())) {
1555 salcianu 1.5 Temp tested = inst.src();
1556 salcianu 1.5 int i = getSigmaForTemp(q, tested);
1557 salcianu 1.6
1558 salcianu 1.6 if(i == -1) return null;
1559 salcianu 1.6
1560 salcianu 1.5 Temp dst[] = q.dst(i);
1561 salcianu 1.5 if(t.equals(dst[1])) {
1562 salcianu 1.5 // this is actually a typecast !
1563 salcianu 1.5 return inst.hclass();
1564 salcianu 1.5 }
1565 salcianu 1.5 }
1566 salcianu 1.5 }
1567 salcianu 1.5 }
1568 salcianu 1.5 // not a typecast
1569 salcianu 1.5 return null;
1570 salcianu 1.5 }
1571 salcianu 1.5
1572 salcianu 1.7
1573 salcianu 1.7 // Checks whether t is defined as the restriction on the true
1574 salcianu 1.7 // branch of a test t2 == null (in that case t is null, ie type
1575 salcianu 1.7 // Void).
1576 salcianu 1.7 //
1577 salcianu 1.7 // Right way to do it: verify that all following cond hold:
1578 salcianu 1.7 // q = CJMP tb; SIGMA: < _ , t> = t2
1579 salcianu 1.7 // tb is defined by tb = OPER acmpeq(t2, t_null)
1580 salcianu 1.7 // t_null is defined by t_null = CONST null
1581 salcianu 1.7 //
1582 salcianu 1.7 // MIT hack:
1583 salcianu 1.7 // suppose they come in the order: CONST, OPER, SIGMA
1584 salcianu 1.7 // this way we don't need reaching defs here.
1585 salcianu 1.7 private static boolean is_nulltest(CJMP q, Temp t) {
1586 salcianu 1.7 if((q.prevLength() != 1) ||
1587 salcianu 1.7 !(q.prev(0) instanceof OPER))
1588 salcianu 1.7 return false;
1589 salcianu 1.7 OPER oper = (OPER) q.prev(0);
1590 salcianu 1.7
1591 salcianu 1.7 if(!oper.dst().equals(q.test()) ||
1592 salcianu 1.7 (oper.opcode() != Qop.ACMPEQ))
1593 salcianu 1.7 return false;
1594 salcianu 1.7
1595 salcianu 1.7 if((oper.prevLength() != 1) ||
1596 salcianu 1.7 !(oper.prev(0) instanceof CONST))
1597 salcianu 1.7 return false;
1598 salcianu 1.7 CONST con = (CONST) oper.prev(0);
1599 salcianu 1.7
1600 salcianu 1.7 if(con.type() != HClass.Void)
1601 salcianu 1.7 return false;
1602 salcianu 1.7
1603 salcianu 1.7 Temp t_null = con.dst();
1604 salcianu 1.7 Temp t2 = null;
1605 salcianu 1.7 if(t_null.equals(oper.operands(0)))
1606 salcianu 1.7 t2 = oper.operands(1);
1607 salcianu 1.7 else if(t_null.equals(oper.operands(1)))
1608 salcianu 1.7 t2 = oper.operands(0);
1609 salcianu 1.7 else
1610 salcianu 1.7 return false;
1611 salcianu 1.7
1612 salcianu 1.7 int i = getSigmaForTemp(q, t2);
1613 salcianu 1.7 if(i == -1) return false;
1614 salcianu 1.7
1615 salcianu 1.7 return t.equals(q.dst(i)[1]);
1616 salcianu 1.7 }
1617 salcianu 1.7
1618 salcianu 1.7
1619 salcianu 1.5 // returns the index of the sigma function that has t_src as a
1620 salcianu 1.5 // source in the big SIGMA node q (with potentially many sigma
1621 salcianu 1.5 // functions)
1622 salcianu 1.5 private static int getSigmaForTemp(SIGMA q, Temp t_src) {
1623 salcianu 1.5 for(int i = 0; i < q.numSigmas(); i++) {
1624 salcianu 1.5 if(q.src(i).equals(t_src))
1625 salcianu 1.5 return i; // we found it!
1626 salcianu 1.5 }
1627 salcianu 1.5 // t is not defined by this SIGMA
1628 salcianu 1.5 return -1;
1629 salcianu 1.5 }
1630 salcianu 1.5
1631 salcianu 1.1.2.1 ////// DEPENDENCY DETECTION (getDependencies) - END
1632 salcianu 1.1.2.1
1633 salcianu 1.1.2.24
1634 salcianu 1.1.2.1 // The following code is responsible for assuring that at most one
1635 salcianu 1.1.2.24 // ExactTemp object representing the temp t defined/used at quad q exists
1636 salcianu 1.1.2.1 // at the execution time. This is necessary since we keep the next and
1637 salcianu 1.1.2.1 // prev info *into* the ExactTemp structure and not in a map (for
1638 salcianu 1.1.2.1 // efficiency reasons), so all the info related to a conceptual ExactTemp
1639 salcianu 1.1.2.1 // must be in a single place.
1640 salcianu 1.1.2.24 // This is enforced by having a Map<ExactTempS,ExactTemp> that maps
1641 salcianu 1.1.2.24 // an ExactTempS (just a <t, q, ud> tuple) to the full ExactTemp object.
1642 salcianu 1.1.2.24 // When we need the ExactTemp for a given <t, q, ud>
1643 salcianu 1.1.2.24 // pair, we search <t, q, ud> in that map; if found we return the existent
1644 salcianu 1.1.2.1 // object, otherwise we create a new one and put it into the map.
1645 salcianu 1.1.2.1 // Of course, no part of the program should dirrectly allocate an
1646 salcianu 1.1.2.1 // ExactTemp, instead the "getExactTemp" function should be called.
1647 salcianu 1.1.2.24 private class ExactTempS { // S for short
1648 salcianu 1.1.2.1 Temp t;
1649 salcianu 1.1.2.1 Quad q;
1650 salcianu 1.1.2.24 int ud;
1651 salcianu 1.1.2.24 ExactTempS(Temp t, Quad q, int ud) {
1652 salcianu 1.1.2.24 this.t = t;
1653 salcianu 1.1.2.24 this.q = q;
1654 salcianu 1.1.2.24 this.ud = ud;
1655 salcianu 1.1.2.1 }
1656 salcianu 1.1.2.1 public int hashCode(){
1657 salcianu 1.1.2.24 return t.hashCode() + q.hashCode() + ud;
1658 salcianu 1.1.2.1 }
1659 salcianu 1.1.2.1 public boolean equals(Object o){
1660 salcianu 1.1.2.1 ExactTempS ets2 = (ExactTempS) o;
1661 salcianu 1.1.2.24 return
1662 salcianu 1.1.2.24 (this.t == ets2.t) &&
1663 salcianu 1.1.2.24 (this.q == ets2.q) &&
1664 salcianu 1.1.2.24 (this.ud == ets2.ud);
1665 salcianu 1.1.2.1 }
1666 salcianu 1.1.2.1 }
1667 salcianu 1.1.2.1 private Map ets2et = null;
1668 salcianu 1.1.2.24 private ExactTempS ets_test = new ExactTempS(null, null, ExactTemp.DEF);
1669 salcianu 1.1.2.24 private ExactTemp getExactTemp(Temp t, Quad q, int ud) {
1670 salcianu 1.1.2.24 ets_test.t = t;
1671 salcianu 1.1.2.24 ets_test.q = q;
1672 salcianu 1.1.2.24 ets_test.ud = ud;
1673 salcianu 1.1.2.1 ExactTemp et = (ExactTemp) ets2et.get(ets_test);
1674 salcianu 1.8 if(et == null) {
1675 salcianu 1.1.2.24 et = new ExactTemp(t, q, ud);
1676 salcianu 1.1.2.24 ExactTempS ets = new ExactTempS(t, q, ud);
1677 salcianu 1.1.2.24 ets2et.put(ets, et);
1678 salcianu 1.1.2.1 }
1679 salcianu 1.1.2.1 return et;
1680 salcianu 1.1.2.1 }
1681 salcianu 1.1.2.24 private ExactTemp getExactTemp(Temp t, Quad q) {
1682 salcianu 1.1.2.24 return getExactTemp(t, q, ExactTemp.DEF);
1683 salcianu 1.1.2.24 }
1684 salcianu 1.1.2.24
1685 salcianu 1.1.2.1 // the end of "unique ExactTemp" code.
1686 salcianu 1.1.2.1
1687 salcianu 1.1.2.1
1688 salcianu 1.13 // Computes the reverse topologically sorted list of strongly connected
1689 salcianu 1.1.2.1 // components containing the definitions of the "interesting" temps.
1690 salcianu 1.1.2.1 // The edges between this nodes models the relation
1691 salcianu 1.1.2.24 // "the type of ExactType x influences the type of the ExactType y"
1692 salcianu 1.14 private List<SCComponent> compute_sccs
1693 salcianu 1.13 (Set initial_set, ReachingDefs rdef) {
1694 salcianu 1.1.2.24 // 1. Compute the graph: ExactTemps, successors and predecessors.
1695 salcianu 1.5 // predecessors are put into the prev field of the ExactTemps;
1696 salcianu 1.1.2.24 // successors are not put into the ExactTemps, but into a separate
1697 salcianu 1.1.2.24 // relation - "next_rel" - as they are gradually discovered.
1698 salcianu 1.1.2.24 // ReachingDefs gives us the prev part.
1699 salcianu 1.1.2.24 Relation next_rel = new RelationImpl();
1700 salcianu 1.1.2.1 Set already_visited = new HashSet();
1701 salcianu 1.1.2.1 PAWorkList W = new PAWorkList();
1702 salcianu 1.5
1703 salcianu 1.1.2.1 W.addAll(initial_set);
1704 salcianu 1.1.2.1 while(!W.isEmpty()){
1705 salcianu 1.1.2.1 ExactTemp et = (ExactTemp) W.remove();
1706 salcianu 1.1.2.1 already_visited.add(et);
1707 salcianu 1.1.2.1
1708 salcianu 1.1.2.24 et.prev = getDependencies(et, rdef);
1709 salcianu 1.1.2.3
1710 salcianu 1.1.2.24 for(int i = 0; i < et.prev.length; i++){
1711 salcianu 1.1.2.24 ExactTemp et2 = (ExactTemp) et.prev[i];
1712 salcianu 1.1.2.1
1713 salcianu 1.5 assert (et2 != null) : "Something wrong with " + et;
1714 salcianu 1.1.2.1
1715 salcianu 1.1.2.24 next_rel.add(et2, et);
1716 salcianu 1.1.2.1 if(!already_visited.contains(et2))
1717 salcianu 1.1.2.1 W.add(et2);
1718 salcianu 1.1.2.1 }
1719 salcianu 1.1.2.1 }
1720 salcianu 1.1.2.1
1721 salcianu 1.1.2.1 // now, put the predecessors in the ExactTemps
1722 cananian 1.12 for(Object etO : next_rel.keys()) {
1723 cananian 1.12 ExactTemp et = (ExactTemp) etO;
1724 salcianu 1.1.2.24 Set next = next_rel.getValues(et);
1725 salcianu 1.1.2.24 et.next = (ExactTemp[]) next.toArray(new ExactTemp[next.size()]);
1726 salcianu 1.1.2.1 }
1727 salcianu 1.1.2.1
1728 salcianu 1.1.2.24 // 2. Build the component graph and sort it topollogically.
1729 salcianu 1.1.2.24
1730 salcianu 1.1.2.24 // Navigator into the graph of ExactTemps. prev returns the ExactTemps
1731 salcianu 1.1.2.24 // whose types influence the type of "node" ExactTemp; next returns
1732 salcianu 1.1.2.24 // the ExactTemps whose types are affected by the type of node.
1733 salcianu 1.11 Navigator et_navigator = new Navigator() {
1734 salcianu 1.11 public Object[] next(Object node){
1735 salcianu 1.11 return ((ExactTemp) node).next;
1736 salcianu 1.11 }
1737 salcianu 1.11 public Object[] prev(Object node){
1738 salcianu 1.11 return ((ExactTemp) node).prev;
1739 salcianu 1.11 }
1740 salcianu 1.11 };
1741 salcianu 1.11
1742 salcianu 1.13 return
1743 salcianu 1.13 (new TopSortedCompDiGraph
1744 salcianu 1.13 (DiGraph.diGraph(already_visited, et_navigator))).
1745 salcianu 1.13 decrOrder();
1746 salcianu 1.1.2.1 }
1747 salcianu 1.1.2.1
1748 salcianu 1.1.2.1
1749 salcianu 1.1.2.1 // Set the types of the parameters of the method underlying mm, using the
1750 salcianu 1.1.2.1 // appropriate type specializations.
1751 salcianu 1.1.2.1 private void set_parameter_types(MetaMethod mm, HCode hcode){
1752 salcianu 1.1.2.1 METHOD m = (METHOD) ((HEADER) hcode.getRootElement()).next(1);
1753 salcianu 1.1.2.1
1754 salcianu 1.1.2.1 int nb_params = m.paramsLength();
1755 salcianu 1.1.2.1 if(CAUTION && (nb_params != mm.nbParams()))
1756 cananian 1.3.2.1 assert false : "Wrong number of params in " + m;
1757 salcianu 1.1.2.1
1758 salcianu 1.1.2.1 for(int i = 0; i < nb_params ; i++)
1759 salcianu 1.1.2.24 getExactTemp(m.params(i), m).addType(mm.getType(i));
1760 salcianu 1.1.2.1 }
1761 salcianu 1.1.2.1
1762 salcianu 1.1.2.1
1763 salcianu 1.1.2.1 // computes the types of the interesting ExactTemps, starting
1764 salcianu 1.1.2.1 // with those in the strongly connected component "scc".
1765 salcianu 1.14 private void compute_types(List<SCComponent> sccs) {
1766 salcianu 1.13 try {
1767 salcianu 1.14 for(SCComponent scc : sccs)
1768 salcianu 1.14 process_scc(scc);
1769 salcianu 1.7 }
1770 salcianu 1.7 catch(AssertionError e) {
1771 salcianu 1.7 display_mm_data(mm_work);
1772 salcianu 1.7 throw e;
1773 salcianu 1.7 }
1774 salcianu 1.1.2.1 }
1775 salcianu 1.1.2.1
1776 salcianu 1.1.2.1 // TYPE INFERENCE QUAD VISITOR - BEGIN
1777 salcianu 1.1.2.1
1778 salcianu 1.1.2.24 private class QuadVisitorTI extends QuadVisitor {
1779 salcianu 1.1.2.1
1780 salcianu 1.1.2.24 Temp t = null;
1781 salcianu 1.1.2.24 ExactTemp et = null;
1782 salcianu 1.1.2.23
1783 salcianu 1.1.2.24 public void visit(MOVE q) {
1784 salcianu 1.1.2.23 if(CAUTION && !t.equals(q.dst()))
1785 salcianu 1.1.2.23 stop_no_def(q);
1786 salcianu 1.5 treat_move_use();
1787 salcianu 1.1.2.23 }
1788 salcianu 1.5
1789 salcianu 1.1.2.24 public void visit(GET q) {
1790 salcianu 1.1.2.23 if(CAUTION && !t.equals(q.dst()))
1791 salcianu 1.1.2.23 stop_no_def(q);
1792 salcianu 1.1.2.24 et.addType(new GenType(q.field().getType(), GenType.POLY));
1793 salcianu 1.1.2.23 }
1794 salcianu 1.1.2.24
1795 salcianu 1.1.2.24 public void visit(AGET q) {
1796 salcianu 1.1.2.23 if(CAUTION && !t.equals(q.dst()))
1797 salcianu 1.1.2.23 stop_no_def(q);
1798 salcianu 1.1.2.1
1799 salcianu 1.1.2.23 // For all the possible types for the source array, take
1800 salcianu 1.1.2.23 // the type of the component
1801 salcianu 1.1.2.24 for(int i = 0; i < et.prev.length; i++) {
1802 salcianu 1.1.2.24 ExactTemp eta = et.prev[i];
1803 salcianu 1.1.2.24 for(Iterator it_types = eta.getTypes(); it_types.hasNext(); ) {
1804 salcianu 1.1.2.24 HClass c = ((GenType) it_types.next()).getHClass();
1805 salcianu 1.7 if(c.equals(HClass.Void)) {
1806 salcianu 1.1.2.23 et.addType(new GenType(HClass.Void, GenType.MONO));
1807 salcianu 1.7 // commented it: I think continue is the right attitude!
1808 salcianu 1.7 // NO!
1809 salcianu 1.7 // continue;
1810 salcianu 1.7 }
1811 salcianu 1.1.2.24 else {
1812 salcianu 1.1.2.23 HClass hcomp = c.getComponentType();
1813 salcianu 1.5 assert
1814 salcianu 1.5 hcomp != null :
1815 salcianu 1.7 "\n" + q.objectref() +
1816 salcianu 1.7 " could have the non-array type <" + c + "> in " +
1817 salcianu 1.10 Util.code2str(q);
1818 salcianu 1.1.2.24 et.addType(new GenType(hcomp, GenType.POLY));
1819 salcianu 1.1.2.1 }
1820 salcianu 1.1.2.1 }
1821 salcianu 1.1.2.1 }
1822 salcianu 1.1.2.23 }
1823 salcianu 1.1.2.23
1824 salcianu 1.1.2.24 public void visit(CALL q) {
1825 salcianu 1.1.2.24 if(et.ud == ExactTemp.DEF) {
1826 salcianu 1.1.2.24 if(t.equals(q.retval())) {
1827 salcianu 1.1.2.24 et.addType(new GenType(q.method().getReturnType(),
1828 salcianu 1.1.2.24 GenType.POLY));
1829 salcianu 1.1.2.24 return;
1830 salcianu 1.1.2.24 }
1831 salcianu 1.1.2.24 if(t.equals(q.retex())) {
1832 salcianu 1.1.2.24 HClass[] excp = q.method().getExceptionTypes();
1833 salcianu 1.1.2.24 for(int i = 0; i < excp.length; i++)
1834 salcianu 1.5 et.addType(new GenType(excp[i], GenType.POLY));
1835 salcianu 1.1.2.24 // According to the JLS, exceptions that are subclasses of
1836 salcianu 1.1.2.24 // java.lang.RuntimeException and java.lang.Error need
1837 salcianu 1.1.2.24 // not be explicitly declared; they can be thrown by any
1838 salcianu 1.1.2.24 // method.
1839 salcianu 1.1.2.24 et.addType(new GenType(jl_RuntimeException, GenType.POLY));
1840 salcianu 1.1.2.24 et.addType(new GenType(jl_Error, GenType.POLY));
1841 salcianu 1.1.2.24 return;
1842 salcianu 1.1.2.24 }
1843 salcianu 1.5
1844 salcianu 1.5 visit((SIGMA) q);
1845 salcianu 1.1.2.1 }
1846 salcianu 1.5 else // it's a USE; we just have to merge the reaching defs
1847 salcianu 1.5 treat_move_use();
1848 salcianu 1.1.2.23 }
1849 salcianu 1.1.2.23
1850 salcianu 1.1.2.24 public void visit(NEW q) {
1851 salcianu 1.1.2.23 if(CAUTION && !t.equals(q.dst()))
1852 salcianu 1.1.2.23 stop_no_def(q);
1853 salcianu 1.1.2.23 et.addType(new GenType(q.hclass(),GenType.MONO));
1854 salcianu 1.1.2.23 }
1855 salcianu 1.1.2.23
1856 salcianu 1.1.2.24 public void visit(ANEW q) {
1857 salcianu 1.1.2.23 if(CAUTION && !t.equals(q.dst()))
1858 salcianu 1.1.2.23 stop_no_def(q);
1859 salcianu 1.1.2.23 et.addType(new GenType(q.hclass(),GenType.MONO));
1860 salcianu 1.1.2.23 }
1861 salcianu 1.1.2.1
1862 salcianu 1.1.2.24 public void visit(TYPECAST q) {
1863 salcianu 1.1.2.23 if(CAUTION && !t.equals(q.objectref()))
1864 salcianu 1.1.2.23 stop_no_def(q);
1865 salcianu 1.1.2.23 et.addType(new GenType(q.hclass(), GenType.POLY));
1866 salcianu 1.1.2.23 }
1867 salcianu 1.1.2.23
1868 salcianu 1.1.2.24 public void visit(METHOD q) {
1869 salcianu 1.1.2.23 // do nothing; the types of the parameters have been
1870 salcianu 1.1.2.23 // already set by set_parameter_types.
1871 salcianu 1.1.2.24 if(CAUTION) {
1872 salcianu 1.1.2.23 boolean found = false;
1873 salcianu 1.1.2.23 for(int i = 0; i < q.paramsLength(); i++)
1874 salcianu 1.1.2.23 if(q.params(i).equals(t)){
1875 salcianu 1.1.2.23 found = true;
1876 salcianu 1.1.2.23 break;
1877 salcianu 1.1.2.23 }
1878 salcianu 1.1.2.23 if(!found) stop_no_def(q);
1879 salcianu 1.1.2.1 }
1880 salcianu 1.1.2.23 }
1881 salcianu 1.1.2.23
1882 salcianu 1.1.2.24 public void visit(CONST q) {
1883 salcianu 1.1.2.24 if(CAUTION) {
1884 salcianu 1.1.2.23 if(!t.equals(q.dst())) stop_no_def(q);
1885 salcianu 1.1.2.1 }
1886 salcianu 1.1.2.23 et.addType(new GenType(q.type(), GenType.MONO));
1887 salcianu 1.1.2.23 }
1888 salcianu 1.5
1889 salcianu 1.5 // SSI additions BEGIN
1890 salcianu 1.5 public void visit(PHI q) {
1891 salcianu 1.5 treat_move_use();
1892 salcianu 1.5 }
1893 salcianu 1.5
1894 salcianu 1.5 // recognize the translation of a TYPECAST in QuadSSI:
1895 salcianu 1.5 // a CJMP t2 preceded by a t2 = t INSTANCEOF hclass
1896 salcianu 1.5 public void visit(CJMP q) {
1897 salcianu 1.7 HClass hclass = null;
1898 salcianu 1.7 if(ssx_form && ((hclass = is_typecast(q, t)) != null)) {
1899 salcianu 1.5 et.addType(new GenType(hclass, GenType.POLY));
1900 salcianu 1.7 }
1901 salcianu 1.7 else if(is_nulltest(q, t)) {
1902 salcianu 1.7 // t is t2's restriction on the true branch of a
1903 salcianu 1.7 // t2 != null test -> it is always null
1904 salcianu 1.7 et.addType(new GenType(HClass.Void, GenType.MONO));
1905 salcianu 1.7 }
1906 salcianu 1.5 else
1907 salcianu 1.5 visit((SIGMA) q);
1908 salcianu 1.5 }
1909 salcianu 1.5
1910 salcianu 1.5 public void visit(SIGMA q) {
1911 salcianu 1.5 treat_move_use();
1912 salcianu 1.5 }
1913 salcianu 1.5 // SSI additions END
1914 salcianu 1.5
1915 salcianu 1.5 // treat MOVE-like instructions
1916 salcianu 1.5 private void treat_move_use() {
1917 salcianu 1.5 for(int i = 0; i < et.prev.length; i++)
1918 salcianu 1.5 et.addTypes(et.prev[i].getTypeSet());
1919 salcianu 1.5 }
1920 salcianu 1.7
1921 salcianu 1.1.2.24 public void visit(Quad q) {
1922 cananian 1.3.2.1 assert false : "Unsupported Quad " + q;
1923 salcianu 1.1.2.23 }
1924 salcianu 1.1.2.23
1925 salcianu 1.1.2.24 private void stop_no_def(Quad q) {
1926 cananian 1.3.2.1 assert false : q + " doesn't define " + t;
1927 salcianu 1.1.2.23 }
1928 salcianu 1.1.2.23
1929 salcianu 1.1.2.23 };
1930 salcianu 1.1.2.24 private QuadVisitorTI qvis_ti = new QuadVisitorTI();
1931 salcianu 1.1.2.23
1932 salcianu 1.1.2.1 // TYPE INFERENCE QUAD VISITOR - END
1933 salcianu 1.1.2.1
1934 salcianu 1.1.2.1
1935 salcianu 1.1.2.24 private void process_scc(SCComponent scc) {
1936 salcianu 1.1.2.1 final PAWorkList W = new PAWorkList();
1937 salcianu 1.1.2.1
1938 salcianu 1.1.2.1 if(DEBUG)
1939 salcianu 1.7 System.out.println("\n\nProcessing " + scc);
1940 salcianu 1.1.2.1
1941 salcianu 1.15 W.addAll(scc.nodes());
1942 salcianu 1.5 while(!W.isEmpty()) {
1943 salcianu 1.1.2.1 ExactTemp et = (ExactTemp) W.remove();
1944 salcianu 1.1.2.1
1945 salcianu 1.1.2.24 // This inelegant modality of passing parameters to the
1946 salcianu 1.1.2.24 // type inference quad visitor is motivated by our struggle to
1947 salcianu 1.1.2.24 // create a single QuadVisitorTI object.
1948 salcianu 1.1.2.24 qvis_ti.t = et.t;
1949 salcianu 1.1.2.24 qvis_ti.et = et;
1950 salcianu 1.1.2.1
1951 salcianu 1.1.2.1 Set old_gen_type = new HashSet(et.getTypeSet());
1952 salcianu 1.1.2.24 et.q.accept(qvis_ti);
1953 salcianu 1.1.2.1 Set new_gen_type = et.getTypeSet();
1954 salcianu 1.1.2.1
1955 salcianu 1.1.2.1 if(!new_gen_type.equals(old_gen_type))
1956 salcianu 1.1.2.24 for(int i = 0; i < et.next.length; i++){
1957 salcianu 1.1.2.24 ExactTemp et2 = et.next[i];
1958 salcianu 1.1.2.24 if(scc.contains(et2)) W.add(et2);
1959 salcianu 1.1.2.1 }
1960 salcianu 1.1.2.1 }
1961 salcianu 1.1.2.1
1962 salcianu 1.1.2.1 if(DEBUG)
1963 salcianu 1.15 for(Object etO : scc.nodes()){
1964 cananian 1.12 ExactTemp et = (ExactTemp) etO;
1965 salcianu 1.7 System.out.println("\n##:< " + et.shortDescription() +
1966 salcianu 1.7 " -> " + et.getTypeSet() + " >\n");
1967 salcianu 1.1.2.1 }
1968 salcianu 1.1.2.1 }
1969 salcianu 1.1.2.1
1970 salcianu 1.1.2.24
1971 salcianu 1.1.2.24 private static long time() {
1972 salcianu 1.1.2.24 return System.currentTimeMillis();
1973 salcianu 1.1.2.24 }
1974 salcianu 1.1.2.1 }
1975 cananian 1.2