1 salcianu 1.1.2.1 // MAInfo.java, created Mon Apr 3 18:17:57 2000 by salcianu
2 cananian 1.1.2.56 // 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.21
5 salcianu 1.1.2.1 package harpoon.Analysis.PointerAnalysis;
6 salcianu 1.1.2.1
7 salcianu 1.1.2.46 import java.io.PrintWriter;
8 salcianu 1.1.2.52 import java.io.Serializable;
9 salcianu 1.1.2.46
10 salcianu 1.1.2.46 import java.util.Arrays;
11 salcianu 1.1.2.1 import java.util.Iterator;
12 salcianu 1.1.2.46 import java.util.ListIterator;
13 salcianu 1.1.2.1 import java.util.Set;
14 salcianu 1.1.2.1 import java.util.HashSet;
15 salcianu 1.1.2.1 import java.util.Map;
16 salcianu 1.1.2.1 import java.util.HashMap;
17 salcianu 1.1.2.46 import java.util.Hashtable;
18 salcianu 1.1.2.46 import java.util.Collection;
19 salcianu 1.1.2.46 import java.util.List;
20 salcianu 1.1.2.46 import java.util.Comparator;
21 salcianu 1.1.2.46 import java.util.LinkedList;
22 salcianu 1.1.2.46 import java.util.Vector;
23 salcianu 1.1.2.54 import java.util.Collections;
24 salcianu 1.1.2.46
25 salcianu 1.1.2.1 import harpoon.ClassFile.HCodeElement;
26 salcianu 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
27 salcianu 1.1.2.48 import harpoon.ClassFile.CachingCodeFactory;
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.1 import harpoon.ClassFile.HMethod;
31 salcianu 1.1.2.13 import harpoon.ClassFile.Linker;
32 salcianu 1.1.2.1 import harpoon.Analysis.Maps.AllocationInformation;
33 salcianu 1.1.2.1
34 bdemsky 1.1.2.33 import harpoon.Analysis.Quads.Unreachable;
35 bdemsky 1.1.2.33
36 salcianu 1.1.2.1 import harpoon.Analysis.MetaMethods.MetaMethod;
37 salcianu 1.1.2.18 import harpoon.Analysis.MetaMethods.MetaCallGraph;
38 salcianu 1.1.2.21 import harpoon.Analysis.MetaMethods.MetaAllCallers;
39 salcianu 1.1.2.1
40 salcianu 1.1.2.1 import harpoon.Analysis.DefaultAllocationInformation;
41 salcianu 1.1.2.1
42 salcianu 1.1.2.1 import harpoon.IR.Quads.Edge;
43 salcianu 1.1.2.1 import harpoon.IR.Quads.Quad;
44 salcianu 1.1.2.1 import harpoon.IR.Quads.METHOD;
45 salcianu 1.1.2.1 import harpoon.IR.Quads.HEADER;
46 salcianu 1.1.2.1 import harpoon.IR.Quads.NEW;
47 salcianu 1.1.2.1 import harpoon.IR.Quads.ANEW;
48 salcianu 1.1.2.1 import harpoon.IR.Quads.MOVE;
49 salcianu 1.1.2.4 import harpoon.IR.Quads.CALL;
50 salcianu 1.1.2.26 import harpoon.IR.Quads.RETURN;
51 salcianu 1.1.2.26 import harpoon.IR.Quads.THROW;
52 salcianu 1.1.2.26 import harpoon.IR.Quads.NOP;
53 bdemsky 1.1.2.33 import harpoon.IR.Quads.PHI;
54 salcianu 1.1.2.1 import harpoon.IR.Quads.QuadFactory;
55 salcianu 1.9 import harpoon.IR.Quads.Code;
56 salcianu 1.1.2.1
57 salcianu 1.1.2.1 import harpoon.Temp.Temp;
58 salcianu 1.1.2.1 import harpoon.Temp.TempFactory;
59 salcianu 1.1.2.1
60 salcianu 1.1.2.1 import harpoon.Util.Util;
61 cananian 1.18 import net.cscott.jutil.WorkSet;
62 salcianu 1.1.2.1
63 salcianu 1.1.2.53 import harpoon.Util.LightBasicBlocks.CachingSCCLBBFactory;
64 salcianu 1.1.2.53 import harpoon.Util.LightBasicBlocks.LightBasicBlock;
65 salcianu 1.1.2.26
66 salcianu 1.1.2.26 import harpoon.IR.Quads.QuadVisitor;
67 salcianu 1.10 import harpoon.Util.Graphs.Navigator;
68 salcianu 1.1.2.26 import harpoon.Util.Graphs.SCComponent;
69 salcianu 1.20 import harpoon.Util.Graphs.TopSortedCompDiGraph;
70 salcianu 1.1.2.26
71 salcianu 1.1.2.32 import harpoon.Util.DataStructs.Relation;
72 salcianu 1.1.2.32 import harpoon.Util.DataStructs.LightRelation;
73 salcianu 1.1.2.32
74 salcianu 1.1.2.32
75 salcianu 1.1.2.1 /**
76 salcianu 1.1.2.1 * <code>MAInfo</code>
77 salcianu 1.1.2.1 *
78 cananian 1.1.2.56 * @author Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
79 salcianu 1.22 * @version $Id: MAInfo.java,v 1.22 2004/03/06 21:52:23 salcianu Exp $
80 salcianu 1.1.2.1 */
81 salcianu 1.1.2.52 public class MAInfo implements AllocationInformation, Serializable {
82 salcianu 1.1.2.10
83 salcianu 1.1.2.48 /** Options for the <code>MAInfo</code> processing. */
84 salcianu 1.1.2.52 public static class MAInfoOptions implements Cloneable, Serializable {
85 salcianu 1.1.2.1
86 salcianu 1.14
87 salcianu 1.14 public boolean IGNORE_INIT_CODE = true;
88 salcianu 1.14
89 salcianu 1.1.2.48 /** Controls the generation of stack allocation hints.
90 salcianu 1.1.2.48 Default <code>false</code>. */
91 salcianu 1.1.2.48 public boolean DO_STACK_ALLOCATION = false;
92 salcianu 1.1.2.48
93 salcianu 1.1.2.53 /** Forbids stack allocation in a loop. Should be one of the
94 salcianu 1.1.2.53 <code>STACK_ALLOCATE_*</code> constants. Default is
95 salcianu 1.1.2.53 <code>STACK_ALLOCATE_NOT_IN_LOOPS</code>. */
96 salcianu 1.1.2.53 public int STACK_ALLOCATION_POLICY = STACK_ALLOCATE_NOT_IN_LOOPS;
97 salcianu 1.8
98 salcianu 1.8 /** Don't stack allocate anything. */
99 salcianu 1.8 public static final int STACK_ALLOCATE_NOTHING = 0;
100 salcianu 1.8 /** Don't stack allocate in loops. */
101 salcianu 1.8 public static final int STACK_ALLOCATE_NOT_IN_LOOPS = 1;
102 salcianu 1.1.2.53 /** Stack allocate everything that's captured. */
103 salcianu 1.8 public static final int STACK_ALLOCATE_ALWAYS = 2;
104 salcianu 1.1.2.53
105 salcianu 1.8 /** Return true if policy is STACK_ALLOCATE_NOT_IN_LOOPS. */
106 salcianu 1.8 public boolean stack_allocate_not_in_loops() {
107 salcianu 1.8 return STACK_ALLOCATION_POLICY == STACK_ALLOCATE_NOT_IN_LOOPS;
108 salcianu 1.1.2.53 }
109 salcianu 1.8
110 salcianu 1.1.2.48 /** Controls the generation of thread local heap allocation hints.
111 salcianu 1.1.2.48 Default <code>false</code>. */
112 salcianu 1.1.2.48 public boolean DO_THREAD_ALLOCATION = false;
113 salcianu 1.1.2.48
114 salcianu 1.1.2.54 /** Enables the application of some method inlining to
115 salcianu 1.1.2.54 increase the effectiveness of the stack allocation. Only
116 salcianu 1.1.2.54 inlinings that increase the effectiveness of the stack
117 salcianu 1.1.2.54 allocation are done. Default <code>false</code>. */
118 salcianu 1.1.2.54 public boolean DO_INLINING_FOR_SA = false;
119 salcianu 1.1.2.54
120 salcianu 1.1.2.54 /** Enables the application of some method inlining to
121 salcianu 1.1.2.54 increase the effectiveness of the thread local heap
122 salcianu 1.1.2.54 allocation. Default <code>false</code>. */
123 salcianu 1.1.2.54 public boolean DO_INLINING_FOR_TA = false;
124 salcianu 1.1.2.54
125 salcianu 1.1.2.54 /** Checks whether any inlining is requested. */
126 salcianu 1.1.2.54 public boolean do_inlining() {
127 salcianu 1.1.2.54 return DO_INLINING_FOR_SA || DO_INLINING_FOR_TA;
128 salcianu 1.1.2.54 }
129 salcianu 1.1.2.48
130 salcianu 1.1.2.48 /** Enables the use of preallocation: if an object will be
131 salcianu 1.1.2.48 accessed only by a thread (<i>ie</i> it is created just to
132 salcianu 1.1.2.48 pass some parameters to a thread), it can be preallocated into
133 salcianu 1.1.2.48 the heap of that thread. For the moment, it is potentially
134 salcianu 1.1.2.48 dangerous so it is deactivated by default.
135 salcianu 1.1.2.48 Default <code>false</code>. */
136 salcianu 1.1.2.48 public boolean DO_PREALLOCATION = false;
137 salcianu 1.1.2.48
138 salcianu 1.1.2.48 /** Controls the detection of the objects for whom there are
139 salcianu 1.1.2.48 no concurrent synchronizations. This objects are marked with a
140 salcianu 1.1.2.48 special flag to reduce the cost of synchronization operations.
141 salcianu 1.1.2.48 Default <code>false</code>. */
142 salcianu 1.1.2.48 public boolean GEN_SYNC_FLAG = false;
143 salcianu 1.1.2.48
144 salcianu 1.1.2.48 /** Use the interthread analysis inside <code>MAInfo</code>.
145 salcianu 1.1.2.48 If this analysis is too buggy or time/memory expensive,
146 salcianu 1.1.2.48 you can disable it through this flag. <b>NOTE:</b> this
147 salcianu 1.1.2.48 will also disable some of the optimizations (<i>eg</i> the
148 salcianu 1.1.2.48 preallocation).
149 salcianu 1.1.2.48 Default <code>false</code>. */
150 salcianu 1.1.2.48 public boolean USE_INTER_THREAD = false;
151 salcianu 1.1.2.48
152 salcianu 1.1.2.48 /** The current implementation is able to inline call strings of
153 salcianu 1.1.2.48 length bigger than one.
154 salcianu 1.1.2.48 Default value is 2. */
155 salcianu 1.1.2.48 public int MAX_INLINING_LEVEL = 2;
156 salcianu 1.1.2.48
157 salcianu 1.1.2.48 /** The maximal size to which we can inflate the size of a method
158 salcianu 1.1.2.48 through inlining.
159 salcianu 1.1.2.54 Default is <code>1000</code> quads. */
160 salcianu 1.1.2.52 public int MAX_METHOD_SIZE = 1000;
161 salcianu 1.1.2.48
162 salcianu 1.1.2.54 /** The maximal size of a method that can be inlined.
163 salcianu 1.1.2.54 Default is <code>100</code> quads. */
164 salcianu 1.1.2.54 public int MAX_INLINABLE_METHOD_SIZE = 100;
165 salcianu 1.1.2.54
166 salcianu 1.1.2.48 /** Pretty printer. */
167 salcianu 1.1.2.48 public void print(String prefix) {
168 salcianu 1.1.2.48 print_opt(prefix, "DO_STACK_ALLOCATION", DO_STACK_ALLOCATION);
169 salcianu 1.1.2.53 if(DO_STACK_ALLOCATION) {
170 salcianu 1.1.2.53 System.out.print(prefix + "\tSTACK_ALLOCATION_POLICY = ");
171 salcianu 1.8 switch(STACK_ALLOCATION_POLICY) {
172 salcianu 1.8 case STACK_ALLOCATE_ALWAYS:
173 salcianu 1.1.2.53 System.out.println("STACK_ALLOCATE_ALWAYS");
174 salcianu 1.8 break;
175 salcianu 1.8 case STACK_ALLOCATE_NOT_IN_LOOPS:
176 salcianu 1.8 System.out.println("STACK_ALLOCATE_NOT_IN_LOOPS");
177 salcianu 1.8 break;
178 salcianu 1.8 default:
179 salcianu 1.8 System.out.println("unknown -> fatal!");
180 salcianu 1.8 System.exit(1);
181 salcianu 1.1.2.53 }
182 salcianu 1.1.2.53 }
183 salcianu 1.1.2.48 print_opt(prefix, "DO_THREAD_ALLOCATION", DO_THREAD_ALLOCATION);
184 salcianu 1.1.2.48 print_opt(prefix, "DO_PREALLOCATION", DO_PREALLOCATION);
185 salcianu 1.1.2.48 print_opt(prefix, "GEN_SYNC_FLAG", GEN_SYNC_FLAG);
186 salcianu 1.1.2.48 print_opt(prefix, "USE_INTER_THREAD", USE_INTER_THREAD);
187 salcianu 1.1.2.54 if(DO_INLINING_FOR_SA || DO_INLINING_FOR_TA) {
188 salcianu 1.1.2.54 print_opt(prefix, "DO_INLINING_FOR_SA", DO_INLINING_FOR_SA);
189 salcianu 1.1.2.54 print_opt(prefix, "DO_INLINING_FOR_TA", DO_INLINING_FOR_TA);
190 salcianu 1.17 System.out.println(prefix + "\tMAX_INLINING_LEVEL = " +
191 salcianu 1.17 MAX_INLINING_LEVEL);
192 salcianu 1.1.2.48 System.out.println(prefix + "\tMAX_METHOD_SIZE = " +
193 salcianu 1.1.2.48 MAX_METHOD_SIZE);
194 salcianu 1.1.2.48 }
195 salcianu 1.1.2.48 }
196 salcianu 1.1.2.48 // Auxiliary method for the pretty printer.
197 salcianu 1.1.2.48 private void print_opt(String prefix, String flag_name, boolean flag) {
198 salcianu 1.1.2.48 System.out.println(prefix + flag_name + " " +
199 salcianu 1.1.2.48 (flag ? "on" : "off"));
200 salcianu 1.1.2.48 }
201 salcianu 1.1.2.48
202 salcianu 1.1.2.48 public Object clone() {
203 salcianu 1.1.2.48 try{
204 salcianu 1.1.2.48 return super.clone();
205 salcianu 1.1.2.48 }
206 salcianu 1.1.2.48 catch (CloneNotSupportedException e) {
207 salcianu 1.1.2.48 throw new Error("Should never happen! " + e);
208 salcianu 1.1.2.48 }
209 salcianu 1.1.2.48 }
210 salcianu 1.1.2.48 };
211 salcianu 1.1.2.46
212 salcianu 1.1.2.48
213 salcianu 1.1.2.48 private static boolean DEBUG = false;
214 salcianu 1.1.2.49 // Controls the "inlining chains" - related debug messages
215 salcianu 1.1.2.49 private final boolean DEBUG_IC = false;
216 salcianu 1.1.2.49
217 salcianu 1.1.2.25
218 salcianu 1.1.2.27 /** Forces the allocation of ALL the threads on the stack. Of course,
219 salcianu 1.1.2.27 dummy and unsafe. */
220 salcianu 1.1.2.28 public static boolean NO_TG = false;
221 salcianu 1.1.2.27
222 salcianu 1.1.2.1 PointerAnalysis pa;
223 salcianu 1.1.2.1 HCodeFactory hcf;
224 salcianu 1.1.2.48 Linker linker;
225 salcianu 1.1.2.1 // the meta-method we are interested in (only those that could be
226 salcianu 1.1.2.1 // started by the main or by one of the threads (transitively) started
227 salcianu 1.1.2.1 // by the main thread.
228 salcianu 1.1.2.1 Set mms;
229 salcianu 1.1.2.2 NodeRepository node_rep;
230 salcianu 1.1.2.18 MetaCallGraph mcg;
231 salcianu 1.1.2.21 MetaAllCallers mac;
232 salcianu 1.1.2.6
233 salcianu 1.1.2.48 private MAInfoOptions opt = null;
234 salcianu 1.1.2.39
235 salcianu 1.1.2.53 // the factory that generates the SCC LBB representation (ie
236 salcianu 1.1.2.53 // strongly connected components of the light basic blocks of
237 salcianu 1.1.2.53 // quads) for the code of a method.
238 salcianu 1.1.2.53 private CachingSCCLBBFactory caching_scc_lbb_factory = null;
239 salcianu 1.1.2.53
240 salcianu 1.1.2.1 /** Creates a <code>MAInfo</code>. */
241 salcianu 1.1.2.53 public MAInfo(PointerAnalysis pa, HCodeFactory hcf,
242 salcianu 1.1.2.53 Linker linker, Set mms,
243 salcianu 1.1.2.48 final MAInfoOptions opt) {
244 cananian 1.3.2.1 assert hcf instanceof CachingCodeFactory : "hcf should be a CachingCodeFactory!";
245 salcianu 1.1.2.1 this.pa = pa;
246 salcianu 1.1.2.18 this.mcg = pa.getMetaCallGraph();
247 salcianu 1.1.2.21 this.mac = pa.getMetaAllCallers();
248 salcianu 1.1.2.53 this.caching_scc_lbb_factory = pa.getCachingSCCLBBFactory();
249 salcianu 1.1.2.1 this.hcf = hcf;
250 salcianu 1.1.2.48 this.linker = linker;
251 salcianu 1.1.2.1 this.mms = mms;
252 salcianu 1.1.2.1 this.node_rep = pa.getNodeRepository();
253 salcianu 1.1.2.48
254 salcianu 1.1.2.48 this.opt = (MAInfoOptions) opt.clone();
255 salcianu 1.1.2.48
256 salcianu 1.1.2.48 java_lang_Thread = linker.forName("java.lang.Thread");
257 salcianu 1.1.2.48 java_lang_Throwable = linker.forName("java.lang.Throwable");
258 salcianu 1.14 //init_good_holes();
259 salcianu 1.1.2.48
260 salcianu 1.1.2.1 analyze();
261 salcianu 1.1.2.25 // the nullify part was moved to prepareForSerialization
262 salcianu 1.1.2.22 }
263 salcianu 1.1.2.25
264 salcianu 1.1.2.25 /** Nullifies some stuff to make the serialization possible.
265 salcianu 1.1.2.25 This method <b>MUST</b> be called before serializing <code>this</code>
266 salcianu 1.1.2.25 object. */
267 salcianu 1.1.2.48 public void prepareForSerialization() {
268 salcianu 1.1.2.2 this.pa = null;
269 salcianu 1.1.2.2 this.hcf = null;
270 salcianu 1.1.2.2 this.mms = null;
271 salcianu 1.1.2.19 this.mcg = null;
272 salcianu 1.1.2.21 this.mac = null;
273 salcianu 1.1.2.2 this.node_rep = null;
274 salcianu 1.1.2.1 }
275 salcianu 1.1.2.1
276 salcianu 1.1.2.48
277 salcianu 1.1.2.48
278 salcianu 1.1.2.48 private void init_good_holes() {
279 salcianu 1.1.2.48 good_holes = new HashSet();
280 salcianu 1.1.2.48
281 salcianu 1.1.2.48 // "java.lang.Thread.currentThread()" is not harmful with regard to
282 salcianu 1.1.2.48 // the thread specific heaps stuff; add it to the set "good_holes"
283 salcianu 1.1.2.48 HClass hclass = linker.forName("java.lang.Thread");
284 salcianu 1.1.2.48 HMethod[] hms = hclass.getDeclaredMethods();
285 salcianu 1.1.2.48 for(int i = 0; i < hms.length; i++)
286 salcianu 1.1.2.48 if("currentThread".equals(hms[i].getName()))
287 salcianu 1.1.2.48 good_holes.add(hms[i]);
288 salcianu 1.1.2.48
289 salcianu 1.1.2.48 if(DEBUG)
290 salcianu 1.14 System.out.println("\nGOOD HOLES: " + good_holes);
291 salcianu 1.1.2.48 }
292 salcianu 1.1.2.48
293 salcianu 1.1.2.48 private Set good_holes = null;
294 salcianu 1.1.2.48 private HClass java_lang_Thread = null;
295 salcianu 1.1.2.48 private HClass java_lang_Throwable = null;
296 salcianu 1.1.2.48
297 salcianu 1.1.2.48
298 salcianu 1.1.2.1 // Map<NEW, AllocationProperties>
299 salcianu 1.1.2.10 private final Map aps = new HashMap();
300 salcianu 1.1.2.1
301 salcianu 1.1.2.1 /** Returns the allocation policy for <code>allocationSite</code>. */
302 salcianu 1.1.2.6 public AllocationInformation.AllocationProperties query
303 salcianu 1.16 (HCodeElement allocationSite) {
304 salcianu 1.1.2.1
305 salcianu 1.1.2.1 AllocationInformation.AllocationProperties ap =
306 salcianu 1.1.2.1 (AllocationInformation.AllocationProperties)
307 salcianu 1.1.2.1 aps.get(allocationSite);
308 salcianu 1.1.2.1
309 salcianu 1.1.2.1 if(ap != null)
310 salcianu 1.1.2.1 return ap;
311 salcianu 1.1.2.1
312 salcianu 1.5 // conservative allocation property: in the global heap
313 kkz 1.1.2.24 return new MyAP(getAllocatedType(allocationSite));
314 salcianu 1.1.2.1 }
315 salcianu 1.1.2.1
316 salcianu 1.1.2.38 // returns the AllocationProperties object for the object creation site q
317 salcianu 1.1.2.38 // if no such object exists, create a default one.
318 salcianu 1.1.2.38 private MyAP getAPObj(Quad q){
319 salcianu 1.1.2.38 MyAP retval = (MyAP) aps.get(q);
320 salcianu 1.1.2.38 if(retval == null)
321 salcianu 1.1.2.38 aps.put(q, retval = new MyAP(getAllocatedType(q)));
322 salcianu 1.1.2.38 return retval;
323 salcianu 1.1.2.38 }
324 salcianu 1.1.2.38
325 salcianu 1.1.2.38 // Set the allocation policy for q to be ap. Discard whatever allocation
326 salcianu 1.1.2.38 // policy info was assigned to q before.
327 salcianu 1.1.2.38 private void setAPObj(Quad q, MyAP ap) {
328 salcianu 1.1.2.38 aps.put(q, ap);
329 salcianu 1.1.2.38 }
330 salcianu 1.1.2.38
331 salcianu 1.1.2.25 // map to store the inline hints:
332 salcianu 1.1.2.25 // CALL to be inlined -> array of (A)NEWs that can be stack allocated
333 salcianu 1.1.2.25 private Map ih = null;
334 salcianu 1.1.2.25
335 salcianu 1.1.2.53 private static long time() {
336 salcianu 1.1.2.53 return System.currentTimeMillis();
337 salcianu 1.1.2.53 }
338 salcianu 1.1.2.53
339 salcianu 1.1.2.2 // analyze all the methods
340 salcianu 1.1.2.46 public void analyze() {
341 salcianu 1.1.2.54 if(opt.do_inlining() ||
342 salcianu 1.1.2.53 (opt.DO_STACK_ALLOCATION && opt.stack_allocate_not_in_loops()))
343 salcianu 1.1.2.53 build_quad2scc();
344 salcianu 1.1.2.53
345 salcianu 1.1.2.54 if(opt.do_inlining()) {
346 salcianu 1.17 chains = new LinkedList();
347 salcianu 1.17 hm2rang = get_hm2rang();
348 salcianu 1.1.2.49 }
349 salcianu 1.1.2.46
350 cananian 1.19 for(Object mmO : mms){
351 cananian 1.19 MetaMethod mm = (MetaMethod) mmO;
352 salcianu 1.1.2.1 if(pa.analyzable(mm.getHMethod()))
353 salcianu 1.1.2.1 analyze_mm(mm);
354 salcianu 1.1.2.1 }
355 salcianu 1.12
356 salcianu 1.12 //if(DEBUG)
357 salcianu 1.12 pa.print_stats();
358 salcianu 1.1.2.46
359 salcianu 1.1.2.54 if(opt.do_inlining()) {
360 salcianu 1.17 process_inlining_chains();
361 salcianu 1.17 chains = null;
362 salcianu 1.17 hm2rang = null;
363 salcianu 1.1.2.46 }
364 salcianu 1.1.2.53 quad2scc = null;
365 salcianu 1.1.2.46 }
366 salcianu 1.1.2.46
367 salcianu 1.10 private Map/*<HMethod,Integer>*/ hm2rang;
368 salcianu 1.1.2.46
369 salcianu 1.1.2.49 // compute a function rang : HMethods -> natural numbers such that
370 salcianu 1.1.2.49 // if m1 calls m2, rang(m1) >= rang(m2). Basically, the leafs of the call
371 salcianu 1.1.2.49 // graph will have the smallest rang; all the methods from the same
372 salcianu 1.1.2.49 // strongly connected component of the call graph have the same rang.
373 salcianu 1.10 private Map/*<HMethod,Integer>*/ get_hm2rang() {
374 salcianu 1.1.2.49 if(DEBUG_IC)
375 salcianu 1.20 System.out.println("set_hm2rang\n Method rank:");
376 salcianu 1.1.2.46
377 salcianu 1.10 Map/*<HMethod,Integer>*/hm2rang = new HashMap/*<HMethod,Integer>*/();
378 salcianu 1.1.2.46 int counter = 0;
379 salcianu 1.20
380 salcianu 1.21 for(SCComponent scc :
381 salcianu 1.21 (new TopSortedCompDiGraph<MetaMethod>(mcg)).incrOrder()) {
382 salcianu 1.22 for(Object hm0 : scc.nodes()) {
383 salcianu 1.22 HMethod hm = ((MetaMethod) hm0).getHMethod();
384 salcianu 1.1.2.49 if(DEBUG_IC)
385 salcianu 1.1.2.46 System.out.println(hm + " -> " + counter);
386 salcianu 1.1.2.46 hm2rang.put(hm, new Integer(counter));
387 salcianu 1.1.2.46 }
388 salcianu 1.1.2.46 counter++;
389 salcianu 1.1.2.25 }
390 salcianu 1.1.2.49 if(DEBUG_IC)
391 salcianu 1.1.2.46 System.out.println("======================================");
392 salcianu 1.10
393 salcianu 1.10 return hm2rang;
394 salcianu 1.1.2.46 }
395 salcianu 1.1.2.46
396 salcianu 1.1.2.46
397 salcianu 1.1.2.46
398 salcianu 1.1.2.2 // get the type of the object allocated by the object creation site hce;
399 salcianu 1.1.2.2 // hce should be NEW or ANEW.
400 salcianu 1.1.2.55 public static HClass getAllocatedType(final HCodeElement hce){
401 salcianu 1.1.2.1 if(hce instanceof NEW)
402 salcianu 1.1.2.1 return ((NEW) hce).hclass();
403 salcianu 1.1.2.1 if(hce instanceof ANEW)
404 salcianu 1.1.2.1 return ((ANEW) hce).hclass();
405 cananian 1.3.2.1 assert false : ("Not a NEW or ANEW: " + hce);
406 salcianu 1.1.2.1 return null; // should never happen
407 salcianu 1.1.2.1 }
408 salcianu 1.1.2.1
409 salcianu 1.1.2.38
410 salcianu 1.1.2.38
411 salcianu 1.1.2.38 //////////////////////////////////////////////////////////////////
412 salcianu 1.1.2.38 ///////// analyze_mm START ///////////////////////////////////////
413 salcianu 1.1.2.38
414 salcianu 1.1.2.25 /* Analyze a single method: take the object creation sites from it
415 salcianu 1.1.2.25 and generate an allocation policy for each one. */
416 salcianu 1.14 private final void analyze_mm(MetaMethod mm) {
417 salcianu 1.1.2.25 if(DEBUG)
418 salcianu 1.1.2.25 System.out.println("\n\nMAInfo: Analyzed Meta-Method: " + mm);
419 salcianu 1.1.2.9
420 salcianu 1.1.2.38 HCode hcode = hcf.convert(mm.getHMethod());
421 salcianu 1.14 if(hcode == null)
422 salcianu 1.14 return; // unanalyzable method
423 salcianu 1.9 ((Code) hcode).setAllocationInformation(this);
424 salcianu 1.1.2.13
425 salcianu 1.14 // Obtain a clone of the internal pig (no interthread analysis yet)
426 salcianu 1.14 // at the end of hm and "cosmetize" it a bit.
427 salcianu 1.14 ParIntGraph pig = pa.getIntParIntGraph(mm);
428 salcianu 1.14 if(pig == null) {
429 salcianu 1.14 if(DEBUG)
430 salcianu 1.14 System.out.println("PA cannot analyze " + mm);
431 salcianu 1.14 return;
432 salcianu 1.14 }
433 salcianu 1.14 pig = (ParIntGraph) pig.clone();
434 salcianu 1.14 pig.G.flushCaches();
435 salcianu 1.14 //pig.G.e.removeMethodHoles(good_holes);
436 salcianu 1.14 Set lost = pa.getLostNodes(mm);
437 salcianu 1.14 if(DEBUG)
438 salcianu 1.14 System.out.println("Parallel Interaction Graph:" + pig);
439 salcianu 1.14
440 salcianu 1.1.2.43 Set nodes = new HashSet();
441 salcianu 1.1.2.43 for(Iterator it = hcode.getElementsI(); it.hasNext(); ) {
442 salcianu 1.1.2.43 Quad quad = (Quad) it.next();
443 salcianu 1.12 if((quad instanceof NEW) || (quad instanceof ANEW)) {
444 salcianu 1.12 // it is possible that exceptions have been coalesced
445 salcianu 1.12 // (and we cannot retrieve their allocation site).
446 salcianu 1.12 // anyway, there is little interest in
447 salcianu 1.12 // stack-allocating exceptions!
448 salcianu 1.12 PANode node = node_rep.getCodeNode(quad, PANode.INSIDE);
449 salcianu 1.12 if(node_rep.node2Code(node) != null)
450 salcianu 1.12 nodes.add(node);
451 salcianu 1.12 }
452 salcianu 1.1.2.43 }
453 salcianu 1.1.2.49
454 salcianu 1.1.2.49 if(DEBUG)
455 salcianu 1.1.2.49 System.out.println("inside nodes " + mm.getHMethod() +
456 salcianu 1.1.2.49 " " + nodes);
457 salcianu 1.1.2.43
458 salcianu 1.14 generate_aps(mm, pig, lost, nodes);
459 salcianu 1.1.2.1
460 salcianu 1.1.2.48 if(opt.DO_PREALLOCATION)
461 salcianu 1.1.2.38 try_prealloc(mm, hcode, pig);
462 salcianu 1.1.2.1
463 salcianu 1.1.2.57 if(opt.DO_THREAD_ALLOCATION)
464 salcianu 1.1.2.57 set_make_heap(pig.tau.activeThreadSet());
465 salcianu 1.1.2.57
466 salcianu 1.1.2.57 // handle_tg_stuff(pig);
467 salcianu 1.1.2.38
468 salcianu 1.17 if(opt.do_inlining() && (opt.MAX_INLINING_LEVEL > 0))
469 salcianu 1.1.2.51 generate_inlining_chains(mm);
470 salcianu 1.1.2.38 }
471 salcianu 1.1.2.7
472 salcianu 1.1.2.38 // Auxiliary method for analyze_mm.
473 salcianu 1.1.2.38 // INPUT: a metamethod mm and the pig at its end.
474 salcianu 1.1.2.38 // ACTION: goes over all the level 0 inside nodes from pig
475 salcianu 1.1.2.38 // and try to stack allocate or thread allocate them.
476 salcianu 1.14 private void generate_aps(MetaMethod mm, ParIntGraph pig, Set lost,
477 salcianu 1.14 Set nodes) {
478 salcianu 1.1.2.39 // we study only level 0 nodes (ie allocated in THIS method).
479 salcianu 1.1.2.43 // Set nodes = getLevel0InsideNodes(pig);
480 salcianu 1.1.2.25
481 salcianu 1.1.2.48 if(opt.DO_STACK_ALLOCATION) {
482 salcianu 1.1.2.39 if(DEBUG) System.out.println("Stack allocation");
483 salcianu 1.14 generate_aps_sa(mm, pig, lost, nodes);
484 salcianu 1.1.2.39 }
485 salcianu 1.1.2.39
486 salcianu 1.1.2.48 if(opt.DO_THREAD_ALLOCATION) {
487 salcianu 1.1.2.39 if(DEBUG) System.out.println("Thread allocation");
488 salcianu 1.14 generate_aps_ta(mm, nodes);
489 salcianu 1.1.2.39 }
490 salcianu 1.1.2.39
491 salcianu 1.1.2.48 if(opt.GEN_SYNC_FLAG) {
492 salcianu 1.1.2.39 if(DEBUG) System.out.println("Generating sync flag");
493 salcianu 1.14 generate_aps_ns(mm, nodes);
494 salcianu 1.1.2.39 }
495 salcianu 1.1.2.39 }
496 salcianu 1.1.2.39
497 salcianu 1.1.2.39 // aux method for generate_aps: generate stack allocation hints
498 salcianu 1.14 private void generate_aps_sa(MetaMethod mm, ParIntGraph pig, Set lost,
499 salcianu 1.14 Set nodes) {
500 cananian 1.19 for(Object nodeO : nodes) {
501 cananian 1.19 PANode node = (PANode) nodeO;
502 salcianu 1.1.2.39 Quad q = (Quad) node_rep.node2Code(node);
503 cananian 1.3.2.1 assert q != null : "No quad for " + node;
504 salcianu 1.1.2.39 MyAP ap = getAPObj(q);
505 salcianu 1.1.2.39
506 salcianu 1.14 if((!lost.contains(node) && pig.G.captured(node)) &&
507 salcianu 1.14 stack_alloc_extra_cond(node, q)) {
508 salcianu 1.9 ap.sa = true;
509 salcianu 1.1.2.39 if(DEBUG)
510 salcianu 1.1.2.39 System.out.println("STACK: " + node +
511 salcianu 1.1.2.39 " was stack allocated " +
512 salcianu 1.6 Util.getLine(q));
513 salcianu 1.1.2.1 }
514 salcianu 1.1.2.39 }
515 salcianu 1.1.2.39 }
516 salcianu 1.9
517 salcianu 1.1.2.39 // aux method for generate_aps: generate thread allocation hints
518 salcianu 1.14 private void generate_aps_ta(MetaMethod mm, Set nodes) {
519 salcianu 1.1.2.39 HMethod hm = mm.getHMethod();
520 cananian 1.19 for(Object nodeO : nodes) {
521 cananian 1.19 PANode node = (PANode) nodeO;
522 salcianu 1.1.2.39 Quad q = (Quad) node_rep.node2Code(node);
523 cananian 1.3.2.1 assert q != null : "No quad for " + node;
524 salcianu 1.1.2.39 MyAP ap = getAPObj(q);
525 salcianu 1.14
526 salcianu 1.14 // CRAZY DEBUG; REMOVE
527 salcianu 1.14 /*
528 salcianu 1.14 DEBUG =
529 salcianu 1.14 (q instanceof NEW) &&
530 salcianu 1.15 ((NEW) q).hclass().getName().equals
531 salcianu 1.15 ("java.io.BufferedInputStream");
532 salcianu 1.14 */
533 salcianu 1.14
534 salcianu 1.1.2.39 if(!ap.sa) {
535 salcianu 1.1.2.39 // the node is not stack allocated; maybe we can
536 salcianu 1.1.2.39 // thread allocate it
537 salcianu 1.14
538 salcianu 1.14 if(DEBUG)
539 salcianu 1.14 System.out.println("\ngen_ta for " + node + " from " +
540 salcianu 1.14 Util.code2str(q));
541 salcianu 1.14
542 salcianu 1.1.2.38 if(remainInThread(node, hm, "")) {
543 salcianu 1.1.2.38 ap.ta = true; // thread allocation
544 salcianu 1.1.2.38 ap.ah = null; // on the current heap
545 salcianu 1.1.2.38 if(DEBUG)
546 salcianu 1.1.2.38 System.out.println("THREAD: " + node +
547 salcianu 1.1.2.38 " was thread allocated " +
548 salcianu 1.6 Util.getLine(q));
549 salcianu 1.1.2.1 }
550 salcianu 1.1.2.39 }
551 salcianu 1.14
552 salcianu 1.14 DEBUG = false;
553 salcianu 1.1.2.39 }
554 salcianu 1.1.2.39 }
555 salcianu 1.9
556 salcianu 1.1.2.39 // aux method for generate_aps: generate "no syncs" hints
557 salcianu 1.14 private void generate_aps_ns(MetaMethod mm, Set nodes) {
558 cananian 1.19 for(Object nodeO : nodes) {
559 cananian 1.19 PANode node = (PANode) nodeO;
560 salcianu 1.1.2.39 Quad q = (Quad) node_rep.node2Code(node);
561 salcianu 1.14 if(! (q instanceof NEW)) continue;
562 salcianu 1.1.2.39 MyAP ap = getAPObj((Quad) node_rep.node2Code(node));
563 salcianu 1.1.2.39 if(ap.sa || ap.ta)
564 salcianu 1.1.2.39 ap.ns = true; // trivial setting of ns
565 salcianu 1.14 else {// the hard work ...
566 salcianu 1.1.2.39 ap.ns = noConflictingSyncs(node, mm);
567 salcianu 1.14 if(ap.ns)
568 salcianu 1.14 System.out.println("BRAVO: " + node + " " +
569 salcianu 1.6 Util.code2str(q));
570 salcianu 1.1.2.1 }
571 salcianu 1.1.2.1 }
572 salcianu 1.1.2.38 }
573 salcianu 1.1.2.13
574 salcianu 1.1.2.38 // Returns the INSIDE nodes of level 0 from pig (that is supposed to
575 salcianu 1.1.2.38 // be attached to the end of some procedure): the set of all the
576 salcianu 1.1.2.38 // inside nodes that appear in pig and are not the specialization of any
577 salcianu 1.1.2.38 // other node (ie they are allocated in exactly that method and in the
578 salcianu 1.1.2.38 // current thread).
579 salcianu 1.1.2.38 private Set getLevel0InsideNodes(ParIntGraph pig) {
580 salcianu 1.1.2.38 final Set retval = new HashSet();
581 salcianu 1.1.2.38 pig.forAllNodes(new PANodeVisitor() {
582 salcianu 1.14 public void visit(PANode node) {
583 salcianu 1.14 if((node.type == PANode.INSIDE) && !(node.isTSpec()) &&
584 salcianu 1.14 (node.getCallChainDepth() == 0)) {
585 salcianu 1.14 retval.add(node);
586 salcianu 1.1.2.38 }
587 salcianu 1.14 }
588 salcianu 1.14 });
589 salcianu 1.1.2.38 retval.remove(ActionRepository.THIS_THREAD);
590 salcianu 1.1.2.38 return retval;
591 salcianu 1.1.2.38 }
592 salcianu 1.1.2.13
593 salcianu 1.1.2.38 // Auxiliary method for analyze_mm.
594 salcianu 1.1.2.38 // Do some dummy things. Hopefully, this will be improved in the future.
595 salcianu 1.1.2.38 private void handle_tg_stuff(ParIntGraph pig) {
596 salcianu 1.1.2.29 /// DUMMY CODE: we don't have NSTK_malloc_with_heap yet
597 salcianu 1.1.2.52 //if(!NO_TG)
598 salcianu 1.1.2.52 set_make_heap(pig.tau.activeThreadSet());
599 salcianu 1.1.2.38
600 salcianu 1.1.2.28 /// DUMMY CODE: Stack allocate ALL the threads
601 salcianu 1.1.2.28 if(NO_TG) {
602 salcianu 1.1.2.27 Set set = getLevel0InsideNodes(pig);
603 cananian 1.19 for(Object nodeO : set) {
604 cananian 1.19 PANode node = (PANode) nodeO;
605 salcianu 1.1.2.27 Quad q = (Quad) node_rep.node2Code(node);
606 salcianu 1.1.2.28 if(q == null) {
607 salcianu 1.1.2.28 System.out.println("BELL: " + node + " " + q);
608 salcianu 1.1.2.28 continue;
609 salcianu 1.1.2.28 }
610 salcianu 1.1.2.27 if(thread_on_stack(node, q)) {
611 salcianu 1.1.2.27 MyAP ap = getAPObj(q);
612 salcianu 1.1.2.28 ap.sa = true;
613 salcianu 1.1.2.29 ap.ta = false;
614 salcianu 1.1.2.27 }
615 salcianu 1.1.2.27 }
616 salcianu 1.1.2.27 }
617 salcianu 1.1.2.25 }
618 salcianu 1.1.2.1
619 salcianu 1.1.2.38 // Auxiliary method for analyze_mm.
620 salcianu 1.1.2.38 // Set the allocation policy info such that each of the threads allocated
621 salcianu 1.1.2.38 // and started into the currently analyzed method has a thread specific
622 salcianu 1.1.2.38 // heap associated with it.
623 salcianu 1.1.2.42 private void set_make_heap(Set threads) {
624 cananian 1.19 for(Object ntO : threads) {
625 cananian 1.19 PANode nt = (PANode) ntO;
626 salcianu 1.1.2.13 if((nt.type != PANode.INSIDE) ||
627 salcianu 1.1.2.13 (nt.getCallChainDepth() != 0) ||
628 salcianu 1.1.2.13 (nt.isTSpec())) continue;
629 salcianu 1.1.2.13
630 salcianu 1.1.2.13 NEW qnt = (NEW) node_rep.node2Code(nt);
631 salcianu 1.1.2.13 MyAP ap = getAPObj(qnt);
632 salcianu 1.1.2.13 ap.mh = true;
633 salcianu 1.6 System.out.println("set_make_heap: " + Util.code2str(qnt));
634 salcianu 1.1.2.13 }
635 salcianu 1.1.2.1 }
636 salcianu 1.1.2.1
637 salcianu 1.1.2.38 ///////// analyze_mm END /////////////////////////////////////////
638 salcianu 1.1.2.38 //////////////////////////////////////////////////////////////////
639 salcianu 1.1.2.13
640 salcianu 1.1.2.1
641 salcianu 1.1.2.13
642 salcianu 1.1.2.38 /** Checks whether <code>node</code> escapes only in the caller:
643 salcianu 1.1.2.38 it is reached through a parameter or it is returned from the
644 salcianu 1.1.2.38 method but not lost due to some other reasons. */
645 salcianu 1.14 private boolean lostOnlyInCaller(PANode node, ParIntGraph pig) {
646 salcianu 1.1.2.38 return
647 salcianu 1.14 ! ( lostInAStatic(node, pig) ||
648 salcianu 1.1.2.38 lostInAMethodHole(node, pig) ||
649 salcianu 1.1.2.38 lostInAThread(node, pig) );
650 salcianu 1.1.2.1 }
651 salcianu 1.1.2.1
652 salcianu 1.1.2.38 /** Checks whether <code>node</code> escapes through a static field. */
653 salcianu 1.1.2.38 private boolean lostInAStatic(PANode node, ParIntGraph pig) {
654 cananian 1.19 for(Object nholeO : pig.G.e.nodeHolesSet(node)){
655 cananian 1.19 PANode nhole = (PANode) nholeO;
656 salcianu 1.1.2.38 if(nhole.type == PANode.STATIC)
657 salcianu 1.1.2.38 return true;
658 salcianu 1.1.2.38 }
659 salcianu 1.1.2.38 return false;
660 salcianu 1.1.2.1 }
661 salcianu 1.1.2.1
662 salcianu 1.1.2.1
663 salcianu 1.1.2.38 /** Checks whether <code>node</code> escapes into a method hole. */
664 salcianu 1.1.2.38 private boolean lostInAMethodHole(PANode node, ParIntGraph pig) {
665 salcianu 1.1.2.38 return pig.G.e.hasEscapedIntoAMethod(node);
666 salcianu 1.1.2.1 }
667 salcianu 1.1.2.1
668 salcianu 1.1.2.26
669 salcianu 1.1.2.38 /** Checks whether <code>node</code> escapes in the caller: it is reachable
670 salcianu 1.1.2.38 from a parameter or from one of the returned nodes (method result and
671 salcianu 1.1.2.38 exceptions). */
672 salcianu 1.1.2.38 private boolean lostInCaller(PANode node, ParIntGraph pig) {
673 salcianu 1.1.2.38 // 1. maybe node escapes through a parameter
674 cananian 1.19 for(Object nholeO : pig.G.e.nodeHolesSet(node)){
675 cananian 1.19 PANode nhole = (PANode) nholeO;
676 salcianu 1.1.2.38 if(nhole.type == PANode.PARAM)
677 salcianu 1.1.2.38 return true;
678 salcianu 1.1.2.13 }
679 salcianu 1.1.2.38 // 2. maybe node escapes through a returned node
680 salcianu 1.1.2.38 return
681 salcianu 1.1.2.38 pig.G.getReachableFromR().contains(node) ||
682 salcianu 1.1.2.38 pig.G.getReachableFromExcp().contains(node);
683 salcianu 1.1.2.1 }
684 salcianu 1.1.2.4
685 salcianu 1.1.2.4
686 salcianu 1.1.2.38 /** Checks whether <code>node</code> escapes in a thread. */
687 salcianu 1.1.2.38 private boolean lostInAThread(PANode node, ParIntGraph pig) {
688 salcianu 1.1.2.38 // threads is the set of thread nodes from pig
689 salcianu 1.1.2.38 Set threads = pig.tau.activeThreadSet();
690 salcianu 1.1.2.38 // go over all the node holes node escapes into and
691 salcianu 1.1.2.38 // check if any of them corresponds to a thread.
692 cananian 1.19 for(Object nholeO : pig.G.e.nodeHolesSet(node)){
693 cananian 1.19 PANode nhole = (PANode) nholeO;
694 salcianu 1.1.2.38 if(threads.contains(nhole))
695 salcianu 1.1.2.38 return true;
696 salcianu 1.1.2.4 }
697 salcianu 1.1.2.38 return false;
698 salcianu 1.1.2.4 }
699 salcianu 1.1.2.38
700 salcianu 1.1.2.38
701 salcianu 1.1.2.38 ////////////////////////////////////////////////////////////////////
702 salcianu 1.1.2.38 /////////////// remainInThread START ///////////////////////////////
703 salcianu 1.1.2.4
704 salcianu 1.1.2.21 private static int MAX_LEVEL_BOTTOM_MODE = 10;
705 salcianu 1.1.2.21 private boolean remainInThreadBottom(PANode node, MetaMethod mm,
706 salcianu 1.14 int level, String ident) {
707 salcianu 1.1.2.25 if(DEBUG)
708 salcianu 1.1.2.25 System.out.println(ident + "remainInThreadBottom called for " +
709 salcianu 1.1.2.25 node + " mm = " + mm);
710 salcianu 1.1.2.21
711 salcianu 1.14 if(!mms.contains(mm)) {
712 salcianu 1.14 if(DEBUG)
713 salcianu 1.14 System.out.println(mm + " was not analyzed -> false");
714 salcianu 1.14 return false;
715 salcianu 1.14 }
716 salcianu 1.14
717 salcianu 1.1.2.21 ParIntGraph pig = pa.getIntParIntGraph(mm);
718 salcianu 1.14 // the analysis is unable to analyze mm
719 salcianu 1.14 if(pig == null) {
720 salcianu 1.14 if(DEBUG)
721 salcianu 1.14 System.out.println("PA cannot analyze " + mm + " -> false");
722 salcianu 1.14 return false;
723 salcianu 1.14 }
724 salcianu 1.14 Set/*<PANode>*/ lost = pa.getLostNodes(mm);
725 salcianu 1.14 if(DEBUG) {
726 salcianu 1.14 System.out.println("PIG: " + pig);
727 salcianu 1.14 System.out.println("Lost nodes = " + lost);
728 salcianu 1.14 }
729 salcianu 1.14
730 salcianu 1.14 if(pa.getLostNodes(mm).contains(node)) {
731 salcianu 1.14 if(DEBUG)
732 salcianu 1.14 System.out.println(ident + node + " is lost -> false");
733 salcianu 1.14 return false;
734 salcianu 1.14 }
735 salcianu 1.1.2.21
736 salcianu 1.14 if(pig.G.captured(node)) {
737 salcianu 1.1.2.25 if(DEBUG)
738 salcianu 1.1.2.25 System.out.println(ident + node+ " is captured -> true");
739 salcianu 1.1.2.21 return true;
740 salcianu 1.1.2.21 }
741 salcianu 1.1.2.21
742 salcianu 1.14 if(!lostOnlyInCaller(node, pig)) {
743 salcianu 1.1.2.25 if(DEBUG)
744 salcianu 1.1.2.25 System.out.println(ident + node +
745 salcianu 1.1.2.25 " escapes somewhere else -> false");
746 salcianu 1.1.2.21 return false;
747 salcianu 1.1.2.21 }
748 salcianu 1.1.2.21
749 salcianu 1.14 if(level == MAX_LEVEL_BOTTOM_MODE) {
750 salcianu 1.1.2.25 if(DEBUG)
751 salcianu 1.1.2.25 System.out.println(ident + node +
752 salcianu 1.1.2.25 "max level reached -> false");
753 salcianu 1.1.2.21 return false;
754 salcianu 1.1.2.21 }
755 salcianu 1.1.2.21
756 salcianu 1.1.2.21 MetaMethod[] callers = mac.getCallers(mm);
757 salcianu 1.1.2.22
758 salcianu 1.14 // This is a very, very delicate case: if there is no caller,
759 salcianu 1.14 // it means the currently analyzed method is either "main" or
760 salcianu 1.14 // the run method of some thread; the node might be accessible
761 salcianu 1.14 // from outside the current thread => we conservatively return
762 salcianu 1.14 // "false".
763 salcianu 1.14 if(callers.length == 0) {
764 salcianu 1.1.2.25 if(DEBUG)
765 salcianu 1.14 System.out.println(ident + node + " pours out of main/run");
766 salcianu 1.1.2.22 return false;
767 salcianu 1.1.2.22 }
768 salcianu 1.1.2.22
769 salcianu 1.14 for(int i = 0; i < callers.length; i++) {
770 salcianu 1.14 if(!remainInThreadBottom(node, callers[i], level+1, ident + " ")) {
771 salcianu 1.1.2.25 if(DEBUG)
772 salcianu 1.1.2.25 System.out.println(ident + node + " -> false");
773 salcianu 1.1.2.21 return false;
774 salcianu 1.1.2.21 }
775 salcianu 1.1.2.21 }
776 salcianu 1.1.2.21
777 salcianu 1.1.2.25 if(DEBUG)
778 salcianu 1.14 System.out.println(ident + node + " stays in current thread");
779 salcianu 1.14
780 salcianu 1.1.2.21 return true;
781 salcianu 1.1.2.21 }
782 salcianu 1.1.2.21
783 salcianu 1.1.2.21
784 salcianu 1.1.2.38 // Checks whether node defined into hm, remains into the current
785 salcianu 1.1.2.4 // thread even if it escapes from the method which defines it.
786 salcianu 1.14 private boolean remainInThread(PANode node, HMethod hm, String ident) {
787 salcianu 1.1.2.25 if(DEBUG)
788 salcianu 1.1.2.25 System.out.println(ident + "remainInThread called for " +
789 salcianu 1.1.2.25 node + " hm = " + hm);
790 salcianu 1.1.2.18
791 salcianu 1.1.2.21 if(node.getCallChainDepth() == PointerAnalysis.MAX_SPEC_DEPTH){
792 salcianu 1.1.2.21 System.out.println(ident + node + " is too old -> might escape");
793 salcianu 1.1.2.4 return false;
794 salcianu 1.1.2.21 }
795 salcianu 1.1.2.4
796 salcianu 1.1.2.4 MetaMethod mm = new MetaMethod(hm, true);
797 salcianu 1.1.2.4 ParIntGraph pig = pa.getIntParIntGraph(mm);
798 salcianu 1.14 if(pig == null) // PA unable to process mm
799 salcianu 1.14 return false;
800 salcianu 1.15 Set/*<PANode>*/ lost = pa.getLostNodes(mm);
801 salcianu 1.15 if(DEBUG) {
802 salcianu 1.15 System.out.println("PIG: " + pig);
803 salcianu 1.15 System.out.println("Lost nodes = " + lost);
804 salcianu 1.15 }
805 salcianu 1.14
806 salcianu 1.15 if(lost.contains(node)) {
807 salcianu 1.14 if(DEBUG)
808 salcianu 1.14 System.out.println(ident + node + " is lost -> false");
809 salcianu 1.14 return false;
810 salcianu 1.14 }
811 salcianu 1.1.2.18
812 salcianu 1.1.2.21 if(pig.G.captured(node)){
813 salcianu 1.1.2.25 if(DEBUG)
814 salcianu 1.1.2.25 System.out.println(ident + node+ " is captured -> true");
815 salcianu 1.1.2.4 return true;
816 salcianu 1.1.2.21 }
817 salcianu 1.1.2.21
818 salcianu 1.1.2.38 if(!lostOnlyInCaller(node, pig)) {
819 salcianu 1.1.2.25 if(DEBUG)
820 salcianu 1.1.2.25 System.out.println(ident + node +
821 salcianu 1.1.2.25 " escapes somewhere else -> false");
822 salcianu 1.1.2.18 return false;
823 salcianu 1.1.2.21 }
824 salcianu 1.1.2.4
825 salcianu 1.14 if(!PointerAnalysis.CALL_CONTEXT_SENSITIVE ||
826 salcianu 1.14 (node.getCallChainDepth() == PointerAnalysis.MAX_SPEC_DEPTH - 1)) {
827 salcianu 1.1.2.25 if(DEBUG)
828 salcianu 1.1.2.25 System.out.println(ident + node +
829 salcianu 1.1.2.25 " is almost too old and uncaptured -> " +
830 salcianu 1.1.2.25 "bottom mode");
831 salcianu 1.14 PANode node2 = PointerAnalysis.CALL_CONTEXT_SENSITIVE ?
832 salcianu 1.14 node.getBottom() : node;
833 salcianu 1.14 boolean retval = remainInThreadBottom(node2, mm, 0, ident);
834 salcianu 1.1.2.25 if(DEBUG)
835 salcianu 1.1.2.25 System.out.println(ident + node + " " + retval);
836 salcianu 1.1.2.21 return retval;
837 salcianu 1.1.2.21 }
838 salcianu 1.1.2.21
839 cananian 1.19 for(Object entryO : node.getAllCSSpecs()){
840 cananian 1.19 Map.Entry entry = (Map.Entry) entryO;
841 salcianu 1.1.2.4 CALL call = (CALL) entry.getKey();
842 salcianu 1.1.2.4 PANode spec = (PANode) entry.getValue();
843 salcianu 1.1.2.4
844 salcianu 1.1.2.46 HMethod hm_caller = quad2method(call);
845 salcianu 1.1.2.4
846 salcianu 1.14 if(!remainInThread(spec, hm_caller, ident + " ")) {
847 salcianu 1.1.2.25 if(DEBUG)
848 salcianu 1.1.2.25 System.out.println(ident + node +
849 salcianu 1.1.2.25 " might escape -> false");
850 salcianu 1.1.2.4 return false;
851 salcianu 1.1.2.21 }
852 salcianu 1.1.2.4 }
853 salcianu 1.1.2.4
854 salcianu 1.1.2.25 if(DEBUG)
855 salcianu 1.1.2.25 System.out.println(ident + node +
856 salcianu 1.1.2.25 " remains in thread -> true");
857 salcianu 1.1.2.21
858 salcianu 1.1.2.22 return true;
859 salcianu 1.1.2.4 }
860 salcianu 1.1.2.4
861 salcianu 1.1.2.38 /////////////// remainInThread END /////////////////////////////////
862 salcianu 1.1.2.38 ////////////////////////////////////////////////////////////////////
863 salcianu 1.1.2.38
864 salcianu 1.1.2.38
865 salcianu 1.1.2.38 ///////////////////////////////////////////////////////////////////////
866 salcianu 1.1.2.38 /////////////// noConflictingSyncs START /////////////////////////////
867 salcianu 1.1.2.38
868 salcianu 1.1.2.38 // Checks whether the synchronizations done on node are useless or not.
869 salcianu 1.1.2.38 private boolean noConflictingSyncs(PANode node, MetaMethod mm) {
870 salcianu 1.1.2.38 return noConflictingSyncs(node, mm, 0, "");
871 salcianu 1.1.2.38 }
872 salcianu 1.1.2.38
873 salcianu 1.1.2.38 // Set up a limit for the length of the reverse call paths we explore
874 salcianu 1.1.2.38 private static final int MAX_LEVEL_NO_CONCURRENT_SYNCS =
875 salcianu 1.1.2.38 PointerAnalysis.MAX_SPEC_DEPTH + 10;
876 salcianu 1.1.2.38
877 salcianu 1.1.2.38 // Does the real job of noConflictingSyncs(node, mm); the algorithm should
878 salcianu 1.1.2.38 // be quite easy from the comments I've put into the code.
879 salcianu 1.1.2.38 private boolean noConflictingSyncs(PANode node, MetaMethod mm,
880 salcianu 1.1.2.38 int level, String ident) {
881 salcianu 1.14
882 salcianu 1.1.2.39 if(DEBUG)
883 salcianu 1.14 System.out.print(ident + "noConflictingSyncs \n" +
884 salcianu 1.1.2.39 "\tnode = " + node +
885 salcianu 1.1.2.39 "\tcreated at " +
886 salcianu 1.6 Util.code2str
887 salcianu 1.1.2.39 (node_rep.node2Code
888 salcianu 1.1.2.39 (node != null ? node.getRoot() : null)) + "\n" +
889 salcianu 1.1.2.39 "\tmm = " + mm + "\n" +
890 salcianu 1.1.2.39 "\tlevel = " + level + "\n");
891 salcianu 1.1.2.39
892 salcianu 1.1.2.39 // Catch some strange case when a node is reported as escaping in
893 salcianu 1.1.2.39 // the graph of the callee but it's absent from the caller's graph
894 salcianu 1.1.2.39 // (which means it's not really escaping)
895 salcianu 1.9
896 salcianu 1.9 // TODO: DEBUG THIS!
897 salcianu 1.9 if(node == null) return true;
898 salcianu 1.9 // assert node != null;
899 salcianu 1.1.2.39
900 salcianu 1.1.2.38 if(level > MAInfo.MAX_LEVEL_NO_CONCURRENT_SYNCS)
901 salcianu 1.1.2.38 return false;
902 salcianu 1.1.2.38
903 salcianu 1.14 // avoid analyzing forbiden methods
904 salcianu 1.14 if(!mms.contains(mm))
905 salcianu 1.14 return false;
906 salcianu 1.1.2.38 ParIntGraph pig = pa.getIntParIntGraph(mm);
907 salcianu 1.14 if(pig == null) // PA unable to process mm
908 salcianu 1.14 return false;
909 salcianu 1.1.2.38
910 salcianu 1.14 // Case 1: node escapes into the entire program -> false
911 salcianu 1.14 if(pa.getLostNodes(mm).contains(node) ||
912 salcianu 1.14 lostInAStatic(node, pig) || lostInAMethodHole(node, pig))
913 salcianu 1.14 return false;
914 salcianu 1.14
915 salcianu 1.14 // Case 2: node is captured in mm -> true
916 salcianu 1.1.2.38 if(pig.G.captured(node))
917 salcianu 1.1.2.38 return true;
918 salcianu 1.1.2.38
919 salcianu 1.1.2.38 // Case 3: node escapes into the caller(s) -> recursively call
920 salcianu 1.1.2.38 // the function on each of the callers and compute a big AND.
921 salcianu 1.1.2.38 if(lostInCaller(node, pig)) {
922 salcianu 1.1.2.38 MetaMethod[] callers = mac.getCallers(mm);
923 salcianu 1.1.2.38 // This is a very, very delicate case: if there is no caller,
924 salcianu 1.1.2.38 // it means the currently analyzed method is either "main" or
925 salcianu 1.1.2.38 // the run method of some thread; the node might be accessible
926 salcianu 1.1.2.38 // from outside the current thread => we conservatively return
927 salcianu 1.1.2.38 // "false".
928 salcianu 1.1.2.38 if(callers.length == 0)
929 salcianu 1.1.2.38 return false;
930 salcianu 1.1.2.38
931 salcianu 1.1.2.57 // Case 3.1: we are still far from the bottom ie we
932 salcianu 1.1.2.57 // have precise information about the specializations
933 salcianu 1.1.2.57 // of node and their corresponding CALL sites.
934 salcianu 1.1.2.57 if(PointerAnalysis.CALL_CONTEXT_SENSITIVE &&
935 salcianu 1.1.2.57 (node.getCallChainDepth() <
936 salcianu 1.1.2.57 PointerAnalysis.MAX_SPEC_DEPTH - 1)) {
937 salcianu 1.1.2.57
938 cananian 1.19 for(Object entryO : node.getAllCSSpecs()) {
939 cananian 1.19 Map.Entry entry = (Map.Entry) entryO;
940 salcianu 1.1.2.38 CALL call = (CALL) entry.getKey();
941 salcianu 1.1.2.38 PANode spec = (PANode) entry.getValue();
942 salcianu 1.1.2.38
943 salcianu 1.1.2.38 MetaMethod mm_caller =
944 salcianu 1.1.2.38 new MetaMethod(call.getFactory().getMethod(), true);
945 salcianu 1.1.2.38
946 salcianu 1.1.2.38 if(!noConflictingSyncs(spec, mm_caller,
947 salcianu 1.1.2.38 level + 1, ident + " "))
948 salcianu 1.1.2.38 return false;
949 salcianu 1.1.2.38 }
950 salcianu 1.1.2.38 return true;
951 salcianu 1.1.2.38 }
952 salcianu 1.1.2.38
953 salcianu 1.1.2.38 // Case 3.2: the bottom was/is about to be reached; we have to
954 salcianu 1.1.2.38 // go and inspect all the callers of mm.
955 salcianu 1.1.2.38 for(int i = 0; i < callers.length; i++) {
956 salcianu 1.1.2.57 PANode node2 =
957 salcianu 1.1.2.57 PointerAnalysis.CALL_CONTEXT_SENSITIVE ?
958 salcianu 1.1.2.57 node.getBottom() : node;
959 salcianu 1.1.2.57
960 salcianu 1.1.2.57 if(!noConflictingSyncs(node2, callers[i], level + 1,
961 salcianu 1.1.2.38 ident + " "))
962 salcianu 1.1.2.38 return false;
963 salcianu 1.1.2.38 }
964 salcianu 1.1.2.38 return true;
965 salcianu 1.1.2.38 }
966 salcianu 1.1.2.38
967 salcianu 1.1.2.38 // Case 4: node doesn't escape into a static, a method hole or the
968 salcianu 1.1.2.38 // caller, so it must escape only into one/more thread(s).
969 salcianu 1.1.2.44
970 salcianu 1.1.2.44 // some conservative guards
971 salcianu 1.1.2.48 if(!(opt.USE_INTER_THREAD && PointerAnalysis.RECORD_ACTIONS))
972 salcianu 1.1.2.40 return false;
973 salcianu 1.1.2.48
974 salcianu 1.1.2.48 System.out.println("CHKPT 1: " + node + " mm = " + mm);
975 salcianu 1.1.2.48
976 salcianu 1.1.2.48 // ParIntGraph pig_t = pa.threadInteraction(mm);
977 salcianu 1.1.2.48 ParIntGraph pig_t = pa.getIntThreadInteraction(mm);
978 salcianu 1.1.2.38 // if node is not captured in pig_t, we give up (it means that the
979 salcianu 1.1.2.38 // thread that accesses might put it in some static, method hole etc.
980 salcianu 1.1.2.38 if(!pig_t.G.captured(node))
981 salcianu 1.1.2.38 return false;
982 salcianu 1.1.2.48
983 salcianu 1.1.2.38 // otherwise, we see if there are any conflicting syncs on node
984 salcianu 1.1.2.38 return noConcurrentSyncs(node, pig_t);
985 salcianu 1.1.2.38 }
986 salcianu 1.1.2.38
987 salcianu 1.1.2.38 // auxiliary method for noConflictingSyncs
988 salcianu 1.1.2.38 // Checks whether the syncs on node that appear in pig are
989 salcianu 1.1.2.38 // nonconflicting (ie cannot occur at the same time) or not.
990 salcianu 1.1.2.38 private boolean noConcurrentSyncs(PANode node, ParIntGraph pig) {
991 salcianu 1.1.2.39 System.out.print("noConcurrentSyncs \n" +
992 salcianu 1.1.2.39 "\tnode = " + node +
993 salcianu 1.1.2.39 "\tcreated at " +
994 salcianu 1.6 Util.code2str
995 salcianu 1.1.2.39 (node_rep.node2Code
996 salcianu 1.1.2.39 (node != null ? node.getRoot() : null)) + "\n");
997 salcianu 1.1.2.38 return pig.ar.independent(node);
998 salcianu 1.1.2.38 }
999 salcianu 1.1.2.38
1000 salcianu 1.1.2.38 /////////////// noConflictingSyncs END / /////////////////////////////
1001 salcianu 1.1.2.38 ///////////////////////////////////////////////////////////////////////
1002 salcianu 1.1.2.38
1003 salcianu 1.1.2.23
1004 salcianu 1.1.2.23 /** Checks some additional conditions for the stack allocation of the
1005 salcianu 1.1.2.23 objects created at Quad q (something else than just captured(node)
1006 salcianu 1.1.2.23
1007 salcianu 1.1.2.23 For the time being, we do just a minor hack to save our experimental
1008 salcianu 1.1.2.23 results: the Thread objects that are captured (e.g. a Thread object
1009 salcianu 1.1.2.23 that is created but never started and remains captured into its
1010 salcianu 1.1.2.23 creating method) should NOT be stack allocated. The constructor
1011 salcianu 1.1.2.23 of Thread does a very nasty thing: it puts a reference to the
1012 salcianu 1.1.2.23 newly created Thread object into the ThreadGroup of the current
1013 salcianu 1.1.2.23 Thread. Normally, this means that any thread escapes into the
1014 salcianu 1.1.2.23 currentThread native method but we did some special tricks for this
1015 salcianu 1.1.2.23 case to ignore it (so that we can allocate a Thread object in its
1016 salcianu 1.1.2.23 own thread specific heap).
1017 salcianu 1.1.2.23
1018 salcianu 1.1.2.23 Normally, some other conditions should be tested too: e.g. do not
1019 salcianu 1.1.2.23 stack allocate objects that are too big etc. */
1020 salcianu 1.1.2.23 private boolean stack_alloc_extra_cond(PANode node, Quad q) {
1021 salcianu 1.1.2.53 // if the appropriate options is turned on in opt,
1022 salcianu 1.1.2.53 // refuse to do stack allocation in a loop
1023 salcianu 1.1.2.53 if(opt.stack_allocate_not_in_loops() && in_a_loop(q)) {
1024 salcianu 1.6 System.out.println("stack_alloc_extra_cond: " + Util.code2str(q) +
1025 salcianu 1.1.2.53 " is in a LOOP -> don't sa");
1026 salcianu 1.1.2.53 return false;
1027 salcianu 1.1.2.53 }
1028 salcianu 1.1.2.53
1029 salcianu 1.1.2.23 // a hack for the Thread objects ...
1030 salcianu 1.1.2.23 HClass hclass = getAllocatedType(q);
1031 salcianu 1.1.2.23 if(java_lang_Thread.isSuperclassOf(hclass)){
1032 salcianu 1.1.2.23 //if(DEBUG)
1033 salcianu 1.1.2.23 System.out.println(node + " allocated in " + q +
1034 salcianu 1.1.2.23 " could be a thread -> NOT stack alloc");
1035 salcianu 1.1.2.23 return false;
1036 salcianu 1.1.2.23 }
1037 salcianu 1.1.2.23 // ... and nothing else
1038 salcianu 1.1.2.23 return true;
1039 salcianu 1.1.2.23 }
1040 salcianu 1.1.2.27
1041 salcianu 1.1.2.53
1042 salcianu 1.1.2.53 /** Checks whether Quad q is in a loop; this is equivalent to
1043 salcianu 1.1.2.53 testing if it's in a strongly connected component of Quads. */
1044 salcianu 1.1.2.53 private boolean in_a_loop(Quad q) {
1045 salcianu 1.1.2.53 SCComponent scc = (SCComponent) quad2scc.get(q);
1046 salcianu 1.1.2.53 return scc.isLoop();
1047 salcianu 1.1.2.53 }
1048 salcianu 1.1.2.53
1049 salcianu 1.1.2.53 // map quad -> strongly connected component
1050 salcianu 1.1.2.53 private Map quad2scc = null;
1051 salcianu 1.1.2.53
1052 salcianu 1.1.2.53 private void build_quad2scc() {
1053 salcianu 1.1.2.53 long tstart = time();
1054 salcianu 1.1.2.53 quad2scc = new HashMap();
1055 salcianu 1.1.2.53 System.out.print("quad2scc construction ... ");
1056 salcianu 1.1.2.53 for(Iterator it = mcg.getAllMetaMethods().iterator(); it.hasNext(); ) {
1057 salcianu 1.1.2.53 HMethod hm = ((MetaMethod) it.next()).getHMethod();
1058 salcianu 1.1.2.53 HCode hcode = hcf.convert(hm);
1059 salcianu 1.1.2.53 if(hcode != null)
1060 salcianu 1.1.2.53 extend_quad2scc(hm);
1061 salcianu 1.1.2.53 }
1062 salcianu 1.1.2.53 System.out.println((time() - tstart) + " ms");
1063 salcianu 1.1.2.53 }
1064 salcianu 1.1.2.53
1065 salcianu 1.1.2.53 private void extend_quad2scc(HMethod hm) {
1066 salcianu 1.21 for(SCComponent scc :
1067 salcianu 1.22 caching_scc_lbb_factory.computeSCCLBB(hm).decrOrder()) {
1068 salcianu 1.22 for(Object lbb0 : scc.nodes()) {
1069 salcianu 1.22 LightBasicBlock lbb = (LightBasicBlock) lbb0;
1070 salcianu 1.22 for(HCodeElement hce : lbb.getElements())
1071 salcianu 1.22 quad2scc.put(hce, scc);
1072 salcianu 1.1.2.53 }
1073 salcianu 1.1.2.53 }
1074 salcianu 1.1.2.53 }
1075 salcianu 1.1.2.53
1076 salcianu 1.1.2.53
1077 salcianu 1.1.2.27 private boolean thread_on_stack(PANode node, Quad q) {
1078 salcianu 1.1.2.27 HClass hclass = getAllocatedType(q);
1079 salcianu 1.1.2.27 if(java_lang_Thread.isSuperclassOf(hclass)) {
1080 salcianu 1.1.2.28 // if(DEBUG)
1081 salcianu 1.6 System.out.println(Util.code2str(q) + " Thread on Stack");
1082 salcianu 1.1.2.27 return true;
1083 salcianu 1.1.2.27 }
1084 salcianu 1.1.2.27 return false;
1085 salcianu 1.1.2.27 }
1086 salcianu 1.1.2.27
1087 salcianu 1.1.2.27
1088 salcianu 1.1.2.1
1089 salcianu 1.1.2.1 /** Pretty printer for debug. */
1090 salcianu 1.1.2.41 public void print() {
1091 salcianu 1.14 long nb_sa = 0;
1092 salcianu 1.14 long nb_ta = 0;
1093 salcianu 1.14 long nb_ns = 0;
1094 salcianu 1.14
1095 salcianu 1.9 System.out.println("\n(INTERESTING) ALLOCATION PROPERTIES:");
1096 cananian 1.19 for(Object newqO : aps.keySet()) {
1097 cananian 1.19 Quad newq = (Quad) newqO;
1098 salcianu 1.1.2.1 MyAP ap = (MyAP) aps.get(newq);
1099 salcianu 1.1.2.22 HMethod hm = newq.getFactory().getMethod();
1100 salcianu 1.1.2.22 HClass hclass = hm.getDeclaringClass();
1101 salcianu 1.1.2.26 PANode node = node_rep.getCodeNode(newq, PANode.INSIDE, false);
1102 salcianu 1.9
1103 salcianu 1.16 /*
1104 salcianu 1.9 // don't print uninteresting allocation properties
1105 salcianu 1.9 if(!(ap.canBeStackAllocated() || ap.canBeThreadAllocated() ||
1106 salcianu 1.9 ap.noSync())) continue;
1107 salcianu 1.16 */
1108 salcianu 1.9
1109 salcianu 1.14 if(ap.canBeStackAllocated()) nb_sa++;
1110 salcianu 1.14 if(ap.canBeThreadAllocated()) nb_ta++;
1111 salcianu 1.14 if(ap.noSync()) nb_ns++;
1112 salcianu 1.14
1113 salcianu 1.1.2.11 System.out.println(hclass.getPackage() + "." +
1114 salcianu 1.1.2.11 newq.getSourceFile() + ":" +
1115 salcianu 1.1.2.1 newq.getLineNumber() + " " +
1116 salcianu 1.1.2.22 newq + "(" + node + ") (" +
1117 salcianu 1.1.2.22 hm + ") \t -> " + ap);
1118 salcianu 1.1.2.1 }
1119 salcianu 1.1.2.1 System.out.println("====================");
1120 salcianu 1.14 System.out.println("TOTAL ALLOCATION SITES:\t" + aps.keySet().size());
1121 salcianu 1.14 System.out.println("SA SITES:\t" + nb_sa);
1122 salcianu 1.14 System.out.println("TA SITES:\t" + nb_ta);
1123 salcianu 1.14 System.out.println("NS SITES:\t" + nb_ns);
1124 salcianu 1.14 System.out.println("====================");
1125 salcianu 1.1.2.25 }
1126 salcianu 1.1.2.25
1127 salcianu 1.1.2.38
1128 salcianu 1.1.2.38 /////////////////////////////////////////////////////////////////////
1129 salcianu 1.1.2.38 //////////// try_prealloc START /////////////////////////////////////
1130 salcianu 1.1.2.38 // PERSONAL ADVICE: This is buggy, incomplete and dummy code.
1131 salcianu 1.1.2.38 // Try to stay away from it.
1132 salcianu 1.1.2.38
1133 salcianu 1.1.2.38 // hope that this evil string really doesn't exist anywhere else
1134 salcianu 1.1.2.38 private static String my_scope = "pa!";
1135 salcianu 1.1.2.38 private static final TempFactory
1136 salcianu 1.1.2.38 temp_factory = Temp.tempFactory(my_scope);
1137 salcianu 1.1.2.38
1138 salcianu 1.1.2.38 // try to apply some aggressive preallocation into the thread specific
1139 salcianu 1.1.2.38 // heap.
1140 salcianu 1.1.2.38 private void try_prealloc(MetaMethod mm, HCode hcode, ParIntGraph pig) {
1141 salcianu 1.1.2.48 System.out.println("try_prealloc(" + mm.getHMethod() + ")");
1142 salcianu 1.1.2.48
1143 salcianu 1.1.2.38 // not very clear if we really need to clone it but it's safer
1144 salcianu 1.1.2.38 PAThreadMap tau = (PAThreadMap) pig.tau.clone();
1145 salcianu 1.1.2.38
1146 salcianu 1.1.2.38 if(tau.activeThreadSet().size() != 1) return;
1147 salcianu 1.1.2.38
1148 salcianu 1.1.2.38 Set active_threads = tau.activeThreadSet();
1149 salcianu 1.1.2.38 PANode nt = (PANode) (active_threads.iterator().next());
1150 salcianu 1.1.2.38
1151 salcianu 1.1.2.38 // protect against some patological cases
1152 salcianu 1.1.2.38 if((nt.type != PANode.INSIDE) ||
1153 salcianu 1.1.2.38 (nt.getCallChainDepth() != 0) ||
1154 salcianu 1.1.2.38 (nt.isTSpec()) ||
1155 salcianu 1.1.2.38 (tau.getValue(nt) != 1))
1156 salcianu 1.1.2.38 return;
1157 salcianu 1.1.2.38
1158 salcianu 1.1.2.38 // pray that no thread is allocated through an ANEW!
1159 salcianu 1.1.2.38 // (it seems quite a reasonable assumption)
1160 salcianu 1.1.2.38 NEW qnt = (NEW) node_rep.node2Code(nt);
1161 salcianu 1.1.2.38
1162 salcianu 1.1.2.48
1163 salcianu 1.1.2.38 // compute the nodes pointed to by the thread node at the moment of
1164 salcianu 1.1.2.38 // the "start()" call. Since we analyze only "good" programs (we
1165 salcianu 1.1.2.38 // have to produce a paper, don't we?) we know that the start() is
1166 salcianu 1.1.2.38 // the last operation in the method so we just take the info from
1167 salcianu 1.1.2.38 // the graph at the end of the method.
1168 salcianu 1.1.2.38 Set pointed = pig.G.I.pointedNodes(nt);
1169 salcianu 1.1.2.38
1170 salcianu 1.1.2.38 ////////
1171 salcianu 1.1.2.38 //if(DEBUG)
1172 salcianu 1.1.2.38 //System.out.println("Pointed = " + pointed);
1173 salcianu 1.1.2.38
1174 salcianu 1.1.2.38 // retain in "pointed" only the nodes allocated in this method,
1175 salcianu 1.1.2.38 // and which escaped only through the thread nt.
1176 salcianu 1.1.2.48 for(Iterator it = pointed.iterator(); it.hasNext(); ) {
1177 salcianu 1.1.2.38 PANode node = (PANode) it.next();
1178 salcianu 1.1.2.38 if( (node.type != PANode.INSIDE) ||
1179 salcianu 1.1.2.38 (node.getCallChainDepth() != 0) ||
1180 salcianu 1.1.2.48 !escapes_only_in_thread(node, nt, pig) ) {
1181 salcianu 1.1.2.38 /// System.out.println(node + " escapes somewhere else too");
1182 salcianu 1.1.2.38 it.remove();
1183 salcianu 1.1.2.38 }
1184 salcianu 1.1.2.38 }
1185 salcianu 1.1.2.38
1186 salcianu 1.1.2.48 Set to_prealloc = new HashSet(pointed);
1187 salcianu 1.1.2.48 to_prealloc.add(nt);
1188 salcianu 1.1.2.48
1189 salcianu 1.1.2.38 ////////
1190 salcianu 1.1.2.38 ///if(DEBUG)
1191 salcianu 1.1.2.38 //System.out.println("Good Pointed = " + pointed);
1192 salcianu 1.1.2.38
1193 salcianu 1.1.2.38 // grab into "news" the set of the NEW/ANEW quads allocating objects
1194 salcianu 1.1.2.38 // that should be put into the heap of "nt".
1195 salcianu 1.1.2.38 Set news = new HashSet();
1196 cananian 1.19 for(Object nodeO : pointed) {
1197 cananian 1.19 PANode node = (PANode) nodeO;
1198 salcianu 1.1.2.38 news.add(node_rep.node2Code(node));
1199 salcianu 1.1.2.38 }
1200 salcianu 1.1.2.38
1201 salcianu 1.1.2.48 if(news.isEmpty()) {
1202 salcianu 1.1.2.48 System.out.println("preallocation: " + qnt);
1203 salcianu 1.1.2.48
1204 salcianu 1.1.2.38 // specially treat this simple case:
1205 salcianu 1.1.2.38 // just allocate the thread node nt on its own heap
1206 salcianu 1.1.2.38 MyAP ap = getAPObj(qnt);
1207 salcianu 1.1.2.38 ap.ta = true; // allocate on thread specific heap
1208 salcianu 1.16 if(opt.GEN_SYNC_FLAG)
1209 salcianu 1.16 ap.ns = true; // SYNC
1210 salcianu 1.1.2.48 ap.mh = true; // makeHeap
1211 salcianu 1.1.2.38 // ap.ah = qnt.dst(); // use own heap
1212 salcianu 1.1.2.38 return;
1213 salcianu 1.1.2.38 }
1214 salcianu 1.1.2.38
1215 salcianu 1.1.2.38 // this NEW no longer exists
1216 salcianu 1.1.2.38 aps.remove(qnt);
1217 salcianu 1.1.2.38
1218 salcianu 1.1.2.38 Temp l2 = new Temp(temp_factory);
1219 salcianu 1.1.2.38 QuadFactory qf = qnt.getFactory();
1220 salcianu 1.1.2.38 MOVE moveq = new MOVE(qf, null, qnt.dst(), l2);
1221 salcianu 1.1.2.38 NEW newq = new NEW(qf, null, l2, qnt.hclass());
1222 salcianu 1.1.2.38
1223 salcianu 1.1.2.38 // insert the MOVE instead of the original allocation
1224 salcianu 1.1.2.38 Quad.replace(qnt, moveq);
1225 salcianu 1.1.2.38 // insert the new NEW quad right after the METHOD quad
1226 salcianu 1.1.2.38 // (at the very top of the method)
1227 salcianu 1.1.2.38 insert_newq((METHOD) (((Quad)hcode.getRootElement()).next(1)), newq);
1228 salcianu 1.1.2.38
1229 salcianu 1.1.2.38 // since the object creation site for the thread node has been changed,
1230 salcianu 1.1.2.38 // we need to update the node2code relation.
1231 salcianu 1.1.2.38 node_rep.updateNode2Code(nt, newq);
1232 salcianu 1.1.2.38
1233 salcianu 1.1.2.38 // the thread object should be allocated in its own
1234 salcianu 1.1.2.38 // thread specific heap.
1235 salcianu 1.1.2.38 MyAP newq_ap = getAPObj(newq);
1236 salcianu 1.1.2.38
1237 salcianu 1.1.2.48 newq_ap.ta = true; // thread allocation
1238 salcianu 1.16 if(opt.GEN_SYNC_FLAG)
1239 salcianu 1.16 newq_ap.ns = true; // SYNC
1240 salcianu 1.1.2.48 newq_ap.mh = true; // makeHeap for the thread object
1241 salcianu 1.1.2.38 // newq_ap.ah = newq.dst(); // use own heap
1242 salcianu 1.1.2.38 HClass hclass = getAllocatedType(newq);
1243 salcianu 1.1.2.38 newq_ap.hip =
1244 salcianu 1.1.2.38 DefaultAllocationInformation.hasInteriorPointers(hclass);
1245 salcianu 1.1.2.38
1246 salcianu 1.1.2.38 // the objects pointed by the thread node and which don't escape
1247 salcianu 1.1.2.38 // anywhere else are allocated on the heap of the thread node
1248 cananian 1.19 for(Object cnewqO : news){
1249 cananian 1.19 Quad cnewq = (Quad) cnewqO;
1250 salcianu 1.1.2.38 MyAP cnewq_ap = getAPObj(cnewq);
1251 salcianu 1.1.2.38 cnewq_ap.ta = true;
1252 salcianu 1.16 if(opt.GEN_SYNC_FLAG)
1253 salcianu 1.16 cnewq_ap.ns = true; // SYNC
1254 salcianu 1.1.2.38 cnewq_ap.ah = l2;
1255 salcianu 1.1.2.38 }
1256 salcianu 1.1.2.38
1257 salcianu 1.1.2.48 // if(DEBUG){
1258 salcianu 1.1.2.38 System.out.println("After the preallocation transformation:");
1259 salcianu 1.1.2.38 hcode.print(new java.io.PrintWriter(System.out, true));
1260 salcianu 1.1.2.38 System.out.println("Thread specific NEW:");
1261 cananian 1.19 for(Object new_siteO : news){
1262 cananian 1.19 Quad new_site = (Quad) new_siteO;
1263 salcianu 1.1.2.38 System.out.println(new_site.getSourceFile() + ":" +
1264 salcianu 1.1.2.38 new_site.getLineNumber() + " " +
1265 salcianu 1.1.2.38 new_site);
1266 salcianu 1.1.2.38 }
1267 salcianu 1.1.2.48 //}
1268 salcianu 1.1.2.38 }
1269 salcianu 1.1.2.38
1270 salcianu 1.1.2.38 // checks whether "node" escapes only through the thread node "nt".
1271 salcianu 1.1.2.38 private boolean escapes_only_in_thread(PANode node, PANode nt,
1272 salcianu 1.1.2.38 ParIntGraph pig){
1273 salcianu 1.1.2.38 if(pig.G.e.hasEscapedIntoAMethod(node)){
1274 salcianu 1.1.2.38 if(DEBUG)
1275 salcianu 1.1.2.38 System.out.println(node + " escapes into a method");
1276 salcianu 1.1.2.38 return false;
1277 salcianu 1.1.2.38 }
1278 salcianu 1.1.2.38 if(pig.G.getReachableFromR().contains(node)) {
1279 salcianu 1.1.2.38 if(DEBUG)
1280 salcianu 1.1.2.38 System.out.println(node + " is reachable from R");
1281 salcianu 1.1.2.38 return false;
1282 salcianu 1.1.2.38 }
1283 salcianu 1.1.2.38 if(pig.G.getReachableFromExcp().contains(node)) {
1284 salcianu 1.1.2.38 if(DEBUG)
1285 salcianu 1.1.2.38 System.out.println(node + " is reachable from Excp");
1286 salcianu 1.1.2.38 return false;
1287 salcianu 1.1.2.38 }
1288 salcianu 1.1.2.38 return true;
1289 salcianu 1.1.2.38 }
1290 salcianu 1.1.2.38
1291 salcianu 1.1.2.38 private void insert_newq(METHOD method, NEW newq){
1292 cananian 1.3.2.1 assert method.nextLength() == 1 : "A METHOD quad should have exactly one successor!";
1293 salcianu 1.1.2.38 Edge nextedge = method.nextEdge(0);
1294 salcianu 1.1.2.38 Quad nextquad = method.next(0);
1295 salcianu 1.1.2.38 Quad.addEdge(method, nextedge.which_succ(), newq, 0);
1296 salcianu 1.1.2.38 Quad.addEdge(newq, 0, nextquad, nextedge.which_pred());
1297 salcianu 1.1.2.38 }
1298 salcianu 1.1.2.38
1299 salcianu 1.1.2.38 //////////// try_prealloc END ///////////////////////////////////////
1300 salcianu 1.1.2.38 /////////////////////////////////////////////////////////////////////
1301 salcianu 1.1.2.38
1302 salcianu 1.1.2.38
1303 salcianu 1.1.2.38
1304 salcianu 1.1.2.38 /////////////////////////////////////////////////////////////////////
1305 salcianu 1.1.2.38 //////////// INLINING STUFF START ///////////////////////////////////
1306 salcianu 1.1.2.26
1307 salcianu 1.1.2.48 //////////// B. AUXILIARY METHODS FOR INLINING START //////////////////
1308 salcianu 1.1.2.48
1309 salcianu 1.14 private Set getInterestingLevel0InsideNodes(MetaMethod mm,
1310 salcianu 1.14 ParIntGraph pig) {
1311 salcianu 1.1.2.48 Set A = new HashSet();
1312 salcianu 1.14 HCode hcode = hcf.convert(mm.getHMethod());
1313 salcianu 1.14 Set lost = pa.getLostNodes(mm);
1314 salcianu 1.1.2.53 for(Iterator it = hcode.getElementsI(); it.hasNext(); ) {
1315 salcianu 1.1.2.53 Quad q = (Quad) it.next();
1316 salcianu 1.1.2.53 if((q instanceof NEW) || (q instanceof ANEW)) {
1317 salcianu 1.1.2.53 PANode node = node_rep.getCodeNode(q, PANode.INSIDE);
1318 salcianu 1.14 if(!pig.G.captured(node) && !lost.contains(node) &&
1319 salcianu 1.14 lostOnlyInCaller(node, pig)) {
1320 salcianu 1.1.2.54 // we are not interested in stack allocating the exceptions
1321 salcianu 1.1.2.54 // since they don't appear in normal case and so, they
1322 salcianu 1.1.2.54 // are not critical for the memory management
1323 salcianu 1.1.2.54 HClass hclass = getAllocatedType(q);
1324 salcianu 1.1.2.54 if(!java_lang_Throwable.isSuperclassOf(hclass))
1325 salcianu 1.1.2.54 A.add(node);
1326 salcianu 1.1.2.54 }
1327 salcianu 1.1.2.53 }
1328 salcianu 1.1.2.53 }
1329 salcianu 1.1.2.53 return A;
1330 salcianu 1.1.2.53 }
1331 salcianu 1.1.2.53
1332 salcianu 1.1.2.48 /* Normally, we should refuse to inline calls that are inside loops
1333 salcianu 1.1.2.48 because that + stack allocation might lead to stack overflow errors.
1334 salcianu 1.12 However, at this moment we don't test this condition.
1335 salcianu 1.12
1336 salcianu 1.12 Note: the advanced inlining tests this in other part. */
1337 salcianu 1.1.2.48 private boolean good_cs(CALL cs){
1338 salcianu 1.1.2.48 return true;
1339 salcianu 1.1.2.26 }
1340 salcianu 1.1.2.26
1341 salcianu 1.1.2.26
1342 salcianu 1.1.2.48 // given a quad q, returns the method q is part of
1343 salcianu 1.1.2.48 private final HMethod quad2method(Quad q) {
1344 salcianu 1.1.2.48 return q.getFactory().getMethod();
1345 salcianu 1.1.2.46 }
1346 salcianu 1.1.2.46
1347 salcianu 1.1.2.46
1348 salcianu 1.9 /** Replace call site cs from hmethod with a clone of hcallee's
1349 salcianu 1.9 code.
1350 salcianu 1.9
1351 salcianu 1.9 @return map from the quads of the original hcallee to the
1352 salcianu 1.9 quads of its clone (these are the quads that are inserted in
1353 salcianu 1.9 hcaller's code). */
1354 salcianu 1.1.2.48 private Map inline_call_site(CALL cs, HMethod hcaller, HMethod hcallee,
1355 salcianu 1.1.2.46 HCodeFactory hcf) {
1356 salcianu 1.1.2.46 System.out.println("INLINING " + call2str(cs));
1357 salcianu 1.1.2.46
1358 salcianu 1.1.2.26 Map old2new = new HashMap();
1359 salcianu 1.1.2.26
1360 salcianu 1.1.2.26 HEADER header_new = null;
1361 salcianu 1.1.2.46 try {
1362 salcianu 1.1.2.48 header_new = get_cloned_code(cs, hcaller, hcallee, old2new, hcf);
1363 salcianu 1.1.2.48 } catch(CloneNotSupportedException e) {
1364 salcianu 1.1.2.48 throw new Error("Should never happen! " + e);
1365 salcianu 1.1.2.48 }
1366 salcianu 1.1.2.26
1367 salcianu 1.1.2.26 METHOD qm = (METHOD) (header_new.next(1));
1368 salcianu 1.1.2.26
1369 salcianu 1.1.2.26 // add the code for the parameter passing
1370 salcianu 1.1.2.26 add_entry_sequence(cs, qm);
1371 salcianu 1.1.2.26
1372 salcianu 1.1.2.26 modify_return_and_throw(cs, header_new);
1373 salcianu 1.1.2.26
1374 salcianu 1.1.2.26 translate_ap(old2new);
1375 salcianu 1.1.2.26
1376 salcianu 1.1.2.46 return old2new;
1377 salcianu 1.1.2.26 }
1378 salcianu 1.1.2.26
1379 salcianu 1.1.2.26
1380 salcianu 1.1.2.46 private void extra_stack_allocation(Quad[] news, Map old2new) {
1381 salcianu 1.1.2.26 for(int i = 0; i < news.length; i++) {
1382 salcianu 1.1.2.26 Quad q = (Quad) old2new.get(news[i]);
1383 salcianu 1.1.2.46
1384 cananian 1.3.2.1 assert q != null : "Warning: no new Quad for " +
1385 salcianu 1.6 Util.code2str(news[i]) + " in [ " +
1386 cananian 1.3.2.1 quad2method(news[i]) + " ]";
1387 salcianu 1.1.2.46
1388 salcianu 1.6 System.out.println("STKALLOC " + Util.code2str(q));
1389 salcianu 1.1.2.46
1390 salcianu 1.1.2.54 MyAP ap = getAPObj(q);
1391 salcianu 1.1.2.54 // new MyAP(getAllocatedType(q));
1392 salcianu 1.1.2.26 ap.sa = true;
1393 salcianu 1.16 if(opt.GEN_SYNC_FLAG)
1394 salcianu 1.16 ap.ns = true; // SYNC
1395 salcianu 1.1.2.26 setAPObj(q, ap);
1396 salcianu 1.1.2.26 }
1397 salcianu 1.1.2.26 }
1398 salcianu 1.1.2.52
1399 salcianu 1.1.2.52
1400 salcianu 1.1.2.54 private void extra_thread_allocation(Quad[] news, Map old2new) {
1401 salcianu 1.1.2.54 for(int i = 0; i < news.length; i++) {
1402 salcianu 1.1.2.54 Quad q = (Quad) old2new.get(news[i]);
1403 salcianu 1.1.2.54
1404 cananian 1.3.2.1 assert q != null : "Warning: no new Quad for " +
1405 salcianu 1.6 Util.code2str(news[i]) + " in [ " +
1406 cananian 1.3.2.1 quad2method(news[i]) + " ]";
1407 salcianu 1.1.2.54
1408 salcianu 1.6 System.out.println("THRALLOC " + Util.code2str(q));
1409 salcianu 1.1.2.54
1410 salcianu 1.1.2.54 MyAP ap = getAPObj(q);
1411 salcianu 1.1.2.54 // new MyAP(getAllocatedType(q));
1412 salcianu 1.1.2.54 if(!ap.sa) ap.ta = true;
1413 salcianu 1.16 if(opt.GEN_SYNC_FLAG)
1414 salcianu 1.16 ap.ns = true; // SYNC
1415 salcianu 1.1.2.54 setAPObj(q, ap);
1416 salcianu 1.1.2.54 }
1417 salcianu 1.1.2.54 }
1418 salcianu 1.1.2.54
1419 salcianu 1.1.2.54
1420 salcianu 1.1.2.52 // Returns an HCodeElement that can be used as the provider of
1421 salcianu 1.1.2.52 // source file and line number for the creation of new Quads.
1422 salcianu 1.1.2.52 private HCodeElement get_inl_hce(final CALL cs) {
1423 salcianu 1.1.2.52 HCodeElement result = new HCodeElement() {
1424 salcianu 1.1.2.52 public int getID() {
1425 cananian 1.3.2.1 assert false : "Unimplemented";
1426 salcianu 1.1.2.52 // this should never happen
1427 salcianu 1.1.2.52 return 0;
1428 salcianu 1.1.2.52 }
1429 salcianu 1.1.2.52 public String getSourceFile() {
1430 salcianu 1.1.2.52 return
1431 salcianu 1.1.2.52 "INL_" + cs.getSourceFile() + "_" +
1432 salcianu 1.1.2.52 cs.getLineNumber();
1433 salcianu 1.1.2.52 }
1434 salcianu 1.1.2.52 public int getLineNumber() {
1435 salcianu 1.1.2.52 return 1;
1436 salcianu 1.1.2.52 }
1437 salcianu 1.1.2.52 };
1438 salcianu 1.1.2.52 return result;
1439 salcianu 1.1.2.52 }
1440 salcianu 1.1.2.26
1441 salcianu 1.1.2.26
1442 salcianu 1.1.2.26 private void add_entry_sequence(CALL cs, METHOD qm) {
1443 salcianu 1.1.2.52 HCodeElement inl_hce = get_inl_hce(cs);
1444 salcianu 1.1.2.52
1445 salcianu 1.1.2.52 Quad replace_cs = new NOP(cs.getFactory(), inl_hce);
1446 salcianu 1.1.2.26
1447 salcianu 1.1.2.26 move_pred_edges(cs, replace_cs);
1448 salcianu 1.1.2.26
1449 salcianu 1.9 assert cs.paramsLength() == qm.paramsLength() :
1450 salcianu 1.9 " different nb. of parameters between CALL and METHOD";
1451 salcianu 1.1.2.26
1452 salcianu 1.1.2.26 Quad previous = replace_cs;
1453 salcianu 1.1.2.26
1454 salcianu 1.1.2.26 int nb_params = cs.paramsLength();
1455 salcianu 1.1.2.26 for(int i = 0; i < nb_params; i++) {
1456 salcianu 1.1.2.26 Temp formal = qm.params(i);
1457 salcianu 1.1.2.26 Temp actual = cs.params(i);
1458 salcianu 1.1.2.26 // emulate the Java parameter passing semantics
1459 salcianu 1.1.2.52 MOVE move = new MOVE(cs.getFactory(), inl_hce, formal, actual);
1460 salcianu 1.1.2.26 Quad.addEdge(previous, 0, move, 0);
1461 salcianu 1.1.2.26 previous = move;
1462 salcianu 1.1.2.26 }
1463 salcianu 1.1.2.26
1464 salcianu 1.1.2.26 // the edge pointing to the first instruction of the method body
1465 salcianu 1.1.2.26 Edge edge = qm.nextEdge(0);
1466 cananian 1.13 Quad.addEdge(previous, 0, edge.to(), edge.which_pred());
1467 salcianu 1.1.2.26 }
1468 salcianu 1.1.2.26
1469 salcianu 1.1.2.26
1470 salcianu 1.1.2.26 private void modify_return_and_throw(final CALL cs, final HEADER header) {
1471 salcianu 1.1.2.52 final HCodeElement inl_hce = get_inl_hce(cs);
1472 salcianu 1.1.2.52
1473 bdemsky 1.1.2.33 class QVisitor extends QuadVisitor {
1474 bdemsky 1.1.2.33 Set returnset;
1475 bdemsky 1.1.2.33 Set throwset;
1476 bdemsky 1.1.2.33 QVisitor() {
1477 salcianu 1.1.2.46 returnset = new WorkSet();
1478 salcianu 1.1.2.46 throwset = new WorkSet();
1479 bdemsky 1.1.2.33 }
1480 bdemsky 1.1.2.33
1481 bdemsky 1.1.2.33 public void finish() {
1482 salcianu 1.1.2.52 PHI returnphi = new PHI(cs.getFactory(), inl_hce, new Temp[0],
1483 salcianu 1.1.2.46 returnset.size());
1484 salcianu 1.1.2.46 int edge = 0;
1485 bdemsky 1.1.2.33 for(Iterator returnit=returnset.iterator();returnit.hasNext();)
1486 salcianu 1.1.2.38 Quad.addEdge((Quad)returnit.next(), 0, returnphi, edge++);
1487 bdemsky 1.1.2.33
1488 salcianu 1.1.2.38 Quad.addEdge(returnphi, 0, cs.next(0),
1489 salcianu 1.1.2.38 cs.nextEdge(0).which_pred());
1490 bdemsky 1.1.2.33
1491 salcianu 1.1.2.52 PHI throwphi = new PHI(cs.getFactory(), inl_hce, new Temp[0],
1492 salcianu 1.1.2.46 throwset.size());
1493 salcianu 1.1.2.46 edge = 0;
1494 bdemsky 1.1.2.33 for(Iterator throwit=throwset.iterator();throwit.hasNext();)
1495 salcianu 1.1.2.38 Quad.addEdge((Quad)throwit.next(), 0, throwphi, edge++);
1496 bdemsky 1.1.2.33
1497 salcianu 1.1.2.38 Quad.addEdge(throwphi, 0, cs.next(1),
1498 salcianu 1.1.2.38 cs.nextEdge(1).which_pred());
1499 bdemsky 1.1.2.33 }
1500 bdemsky 1.1.2.33
1501 salcianu 1.1.2.46 public void visit(Quad q) {}
1502 bdemsky 1.1.2.33
1503 bdemsky 1.1.2.33 public void visit(RETURN q) {
1504 bdemsky 1.1.2.33 Temp retVal = cs.retval();
1505 bdemsky 1.1.2.33
1506 salcianu 1.1.2.52 Quad replace = (retVal != null) ?
1507 salcianu 1.1.2.52 ((Quad) new MOVE
1508 salcianu 1.1.2.52 (cs.getFactory(), inl_hce, retVal, q.retval())) :
1509 salcianu 1.1.2.52 ((Quad) new NOP(cs.getFactory(), inl_hce));
1510 bdemsky 1.1.2.33
1511 bdemsky 1.1.2.33 // make the predecessors of q point to replace
1512 bdemsky 1.1.2.33 move_pred_edges(q, replace);
1513 bdemsky 1.1.2.33
1514 bdemsky 1.1.2.33 // the only succesor of replace should now be the
1515 bdemsky 1.1.2.33 // 0-successor of the CALL instruction (normal return)
1516 bdemsky 1.1.2.33 returnset.add(replace);
1517 bdemsky 1.1.2.33 }
1518 bdemsky 1.1.2.33
1519 bdemsky 1.1.2.33 public void visit(THROW q) {
1520 bdemsky 1.1.2.33 Temp retEx = cs.retex();
1521 bdemsky 1.1.2.33
1522 salcianu 1.1.2.52 Quad replace = (retEx != null) ?
1523 salcianu 1.1.2.52 ((Quad) new MOVE
1524 salcianu 1.1.2.52 (cs.getFactory(), inl_hce, retEx, q.throwable())) :
1525 salcianu 1.1.2.52 ((Quad) new NOP(cs.getFactory(), inl_hce));
1526 bdemsky 1.1.2.33
1527 bdemsky 1.1.2.33 // make the predecessors of q point to replace
1528 bdemsky 1.1.2.33 move_pred_edges(q, replace);
1529 bdemsky 1.1.2.33
1530 bdemsky 1.1.2.33 // the only succesor of replace should now be the
1531 bdemsky 1.1.2.33 // 1-successor of the CALL instruction (exception return)
1532 bdemsky 1.1.2.33 throwset.add(replace);
1533 bdemsky 1.1.2.33 }
1534 bdemsky 1.1.2.33 };
1535 salcianu 1.1.2.46 QVisitor inlining_qv = new QVisitor();
1536 salcianu 1.1.2.26 apply_qv_to_tree(header, inlining_qv);
1537 bdemsky 1.1.2.33 inlining_qv.finish();
1538 salcianu 1.1.2.26 }
1539 salcianu 1.1.2.26
1540 salcianu 1.1.2.26
1541 salcianu 1.1.2.26 private static void apply_qv_to_tree(Quad q, QuadVisitor qv) {
1542 salcianu 1.1.2.26 recursive_apply_qv(q, qv, new HashSet());
1543 salcianu 1.1.2.26 }
1544 salcianu 1.1.2.26
1545 salcianu 1.1.2.26 private static void recursive_apply_qv(Quad q, QuadVisitor qv, Set seen) {
1546 salcianu 1.1.2.26 if(!seen.add(q)) return; // q has already been seen
1547 salcianu 1.1.2.26
1548 salcianu 1.1.2.26 q.accept(qv);
1549 salcianu 1.1.2.26
1550 salcianu 1.1.2.26 int nb_next = q.nextLength();
1551 salcianu 1.1.2.26 for(int i = 0; i < nb_next; i++)
1552 salcianu 1.1.2.26 recursive_apply_qv(q.next(i), qv, seen);
1553 salcianu 1.1.2.26 }
1554 salcianu 1.1.2.26
1555 salcianu 1.1.2.26
1556 salcianu 1.1.2.26 // For any predecessor pred of oldq, replace the arc pred->oldq
1557 salcianu 1.1.2.26 // with old->newq.
1558 salcianu 1.1.2.26 private static void move_pred_edges(Quad oldq, Quad newq) {
1559 salcianu 1.1.2.26 Edge[] edges = oldq.prevEdge();
1560 salcianu 1.1.2.26 for(int i = 0; i < edges.length; i++) {
1561 salcianu 1.1.2.26 Edge e = edges[i];
1562 cananian 1.13 Quad.addEdge(e.from(), e.which_succ(),
1563 salcianu 1.1.2.26 newq, e.which_pred());
1564 salcianu 1.1.2.25 }
1565 salcianu 1.1.2.25 }
1566 salcianu 1.1.2.25
1567 salcianu 1.1.2.26 private void translate_ap(Map old2new) {
1568 cananian 1.19 for(Object entryO : old2new.entrySet()) {
1569 cananian 1.19 Map.Entry entry = (Map.Entry) entryO;
1570 salcianu 1.1.2.26 Quad old_q = (Quad) entry.getKey();
1571 salcianu 1.1.2.26 Quad new_q = (Quad) entry.getValue();
1572 salcianu 1.1.2.46 if(!((old_q instanceof NEW) || (old_q instanceof ANEW)))
1573 salcianu 1.1.2.46 continue;
1574 salcianu 1.1.2.26 setAPObj(new_q, (MyAP) (getAPObj(old_q).clone()));
1575 salcianu 1.1.2.26 }
1576 salcianu 1.1.2.26 }
1577 salcianu 1.1.2.26
1578 salcianu 1.1.2.46 private HEADER get_cloned_code(CALL cs, HMethod caller, HMethod callee,
1579 salcianu 1.1.2.26 Map old2new, HCodeFactory hcf)
1580 salcianu 1.1.2.26 throws CloneNotSupportedException {
1581 salcianu 1.1.2.43
1582 salcianu 1.1.2.46 HCode hcode_orig = hcf.convert(callee);
1583 salcianu 1.1.2.26
1584 salcianu 1.1.2.26 HEADER header_orig =
1585 salcianu 1.1.2.26 (HEADER) hcode_orig.getRootElement();
1586 salcianu 1.1.2.26 HEADER header_new =
1587 salcianu 1.1.2.26 (HEADER) Quad.clone(cs.getFactory(), header_orig);
1588 salcianu 1.1.2.26
1589 salcianu 1.1.2.26 fill_the_map(header_orig, header_new, old2new, new HashSet());
1590 salcianu 1.1.2.26
1591 salcianu 1.1.2.26 return header_new;
1592 salcianu 1.1.2.26 }
1593 salcianu 1.1.2.26
1594 salcianu 1.1.2.26
1595 salcianu 1.1.2.26 // recursively explore two HCode's (the second is the clone of the first
1596 salcianu 1.1.2.46 // one) and set up a mapping "old NEW/ANEW/CALL -> new NEW/ANEW/CALL
1597 salcianu 1.1.2.26 private static void fill_the_map(Quad q1, Quad q2, Map map, Set seen) {
1598 salcianu 1.1.2.26 // avoid entering infinite loops: return when we meet a previously
1599 salcianu 1.1.2.26 // seen instruction
1600 salcianu 1.1.2.26 if(!seen.add(q1)) return;
1601 salcianu 1.1.2.26
1602 salcianu 1.1.2.46 if( (q1 instanceof NEW) ||
1603 salcianu 1.1.2.46 (q1 instanceof ANEW) ||
1604 salcianu 1.1.2.46 (q1 instanceof CALL) )
1605 salcianu 1.1.2.26 map.put(q1, q2);
1606 salcianu 1.1.2.26
1607 salcianu 1.1.2.26 Quad[] next1 = q1.next();
1608 salcianu 1.1.2.26 Quad[] next2 = q2.next();
1609 salcianu 1.1.2.26
1610 cananian 1.3.2.1 assert next1.length == next2.length : " Possible error in HCode.clone()";
1611 salcianu 1.1.2.26
1612 salcianu 1.1.2.26 for(int i = 0; i < next1.length; i++)
1613 salcianu 1.1.2.26 fill_the_map(next1[i], next2[i], map, seen);
1614 salcianu 1.1.2.1 }
1615 salcianu 1.1.2.1
1616 salcianu 1.1.2.48 private boolean hcodeOf(final HCode hcode,
1617 salcianu 1.1.2.48 final String cls_name, final String method_name) {
1618 salcianu 1.1.2.48 HMethod hm = hcode.getMethod();
1619 salcianu 1.1.2.48 return isThisMethod(hm, cls_name, method_name);
1620 salcianu 1.1.2.48 }
1621 salcianu 1.1.2.48
1622 salcianu 1.1.2.48 private boolean isThisMethod(final HMethod hm, final String cls_name,
1623 salcianu 1.1.2.48 final String method_name) {
1624 salcianu 1.1.2.48 HClass hc = hm.getDeclaringClass();
1625 salcianu 1.1.2.48
1626 salcianu 1.1.2.48 return
1627 salcianu 1.1.2.48 hm.getName().equals(method_name) &&
1628 salcianu 1.1.2.48 hc.getName().equals(cls_name);
1629 salcianu 1.1.2.48 }
1630 salcianu 1.1.2.48
1631 salcianu 1.1.2.48
1632 salcianu 1.1.2.48
1633 salcianu 1.1.2.48 private String call2str(CALL cs) {
1634 salcianu 1.1.2.48 return
1635 salcianu 1.6 Util.code2str(cs) + " [ " + quad2method(cs) + " ] ";
1636 salcianu 1.1.2.48 }
1637 salcianu 1.1.2.48
1638 salcianu 1.1.2.48
1639 salcianu 1.1.2.48 private void print_modified_hcode(HMethod hm,
1640 salcianu 1.1.2.48 final Collection new_quads) {
1641 salcianu 1.1.2.48 print_modified_hcode(hcf.convert(hm), new_quads);
1642 salcianu 1.1.2.48 }
1643 salcianu 1.1.2.48
1644 salcianu 1.1.2.48 private void print_modified_hcode(HCode hcode,
1645 salcianu 1.1.2.48 final Collection new_quads) {
1646 salcianu 1.1.2.48 class MyCallBack extends HCode.PrintCallback {
1647 salcianu 1.1.2.48 public void printBefore(PrintWriter pw, HCodeElement hce) {
1648 salcianu 1.1.2.48 if(new_quads.contains(hce))
1649 salcianu 1.1.2.48 pw.print(" *** ");
1650 salcianu 1.1.2.48 else
1651 salcianu 1.1.2.48 pw.print(" ");
1652 salcianu 1.1.2.48 }
1653 salcianu 1.1.2.48 public void printAfter(PrintWriter pw, HCodeElement hce) {}
1654 salcianu 1.1.2.48 };
1655 salcianu 1.1.2.48
1656 salcianu 1.1.2.48 hcode.print(new PrintWriter(System.out, true), new MyCallBack());
1657 salcianu 1.1.2.48 System.out.println("========================================\n");
1658 salcianu 1.1.2.48 }
1659 salcianu 1.1.2.48
1660 salcianu 1.1.2.48 // Given a call instruction cs, return the method whose body contains cs.
1661 salcianu 1.1.2.48 private HMethod extract_caller(CALL cs) {
1662 salcianu 1.1.2.48 return quad2method(cs);
1663 salcianu 1.1.2.48 }
1664 salcianu 1.1.2.48
1665 salcianu 1.1.2.48 // Given a call instruction cs, return the method that is called by cs.
1666 salcianu 1.1.2.48 private HMethod extract_callee(CALL cs) {
1667 salcianu 1.1.2.48 MetaMethod mm_caller = new MetaMethod(extract_caller(cs), true);
1668 salcianu 1.1.2.48 MetaMethod[] mm_callees = mcg.getCallees(mm_caller, cs);
1669 salcianu 1.1.2.48 if(mm_callees.length == 0) return null;
1670 salcianu 1.12 assert mm_callees.length == 1 :
1671 salcianu 1.12 "More than one callee for " + cs + "; " + mm_callees.length;
1672 salcianu 1.1.2.48 return mm_callees[0].getHMethod();
1673 salcianu 1.1.2.48 }
1674 salcianu 1.1.2.46
1675 salcianu 1.1.2.46
1676 salcianu 1.1.2.48 //////////// C. ADVANCED INLINING STUFF START ///////////////////////
1677 salcianu 1.1.2.46
1678 salcianu 1.1.2.46 // Given a (meta) method mm, generates inlining chains that will
1679 salcianu 1.1.2.46 // make some object creation sites stack allocatable.
1680 salcianu 1.1.2.46 // An inlining chain will be a list of calls like:
1681 salcianu 1.1.2.46 // call m1 (occuring in the body of m2)
1682 salcianu 1.1.2.46 // call m2 (occuring in the body of m3)
1683 salcianu 1.1.2.46 // ...
1684 salcianu 1.1.2.46 // call mk-1 (occuring in the body of mk)
1685 salcianu 1.1.2.46 // where m1 == mm. Also, forall i, mi and mi+1 should appear in
1686 salcianu 1.1.2.46 // different strongly connected components in the call graph (to avoid
1687 salcianu 1.1.2.46 // circular inlining in nests of mutually recursive methods).
1688 salcianu 1.1.2.46 private void generate_inlining_chains(MetaMethod mm) {
1689 salcianu 1.1.2.46 ParIntGraph pig = pa.getExtParIntGraph(mm);
1690 salcianu 1.14 Set nodes = getInterestingLevel0InsideNodes(mm, pig);
1691 salcianu 1.12 if(nodes.isEmpty()) return;
1692 salcianu 1.1.2.54 Set sa_nodes = new HashSet();
1693 salcianu 1.1.2.54 Set ta_nodes = new HashSet();
1694 salcianu 1.1.2.54 split_nodes(nodes, sa_nodes, ta_nodes);
1695 salcianu 1.1.2.46
1696 salcianu 1.1.2.46 current_chain_cs = new LinkedList();
1697 salcianu 1.1.2.46 current_chain_callees = new LinkedList();
1698 salcianu 1.1.2.46
1699 salcianu 1.1.2.54 discover_inlining_chains(mm, sa_nodes, ta_nodes, 0);
1700 salcianu 1.1.2.46
1701 salcianu 1.1.2.46 current_chain_cs = null;
1702 salcianu 1.1.2.46 current_chain_callees = null;
1703 salcianu 1.1.2.46 }
1704 salcianu 1.1.2.46 private LinkedList current_chain_cs;
1705 salcianu 1.1.2.46 private LinkedList current_chain_callees;
1706 salcianu 1.1.2.54
1707 salcianu 1.1.2.54 private void split_nodes(Set nodes, Set sa_nodes, Set ta_nodes) {
1708 cananian 1.19 for(Object nodeO : nodes) {
1709 cananian 1.19 PANode node = (PANode) nodeO;
1710 salcianu 1.1.2.53 Quad q = (Quad) node_rep.node2Code(node);
1711 salcianu 1.1.2.54 if(opt.stack_allocate_not_in_loops() && in_a_loop(q)) {
1712 salcianu 1.14 if(DEBUG)
1713 salcianu 1.14 System.out.println("split_nodes: " + Util.code2str(q) +
1714 salcianu 1.14 " in a loop -> no sa, try to ta");
1715 salcianu 1.1.2.54 ta_nodes.add(node);
1716 salcianu 1.1.2.53 }
1717 salcianu 1.1.2.54 else
1718 salcianu 1.1.2.54 sa_nodes.add(node);
1719 salcianu 1.1.2.53 }
1720 salcianu 1.1.2.53 }
1721 salcianu 1.1.2.53
1722 salcianu 1.1.2.46 private int get_rang(HMethod hm) {
1723 salcianu 1.1.2.46 return ((Integer) hm2rang.get(hm)).intValue();
1724 salcianu 1.1.2.46 }
1725 salcianu 1.1.2.46
1726 salcianu 1.1.2.46 private boolean good_cs2(CALL cs) {
1727 salcianu 1.1.2.46 int rang_caller = get_rang(extract_caller(cs));
1728 salcianu 1.1.2.46 int rang_callee = get_rang(extract_callee(cs));
1729 cananian 1.3.2.1 assert rang_caller >= rang_callee : "Bad method rangs " + cs;
1730 salcianu 1.12
1731 salcianu 1.12 if(DEBUG && !(rang_caller > rang_callee))
1732 salcianu 1.12 System.out.println("BAD cs (equal ranks)" + Util.code2str(cs));
1733 salcianu 1.12
1734 salcianu 1.1.2.46 return rang_caller > rang_callee;
1735 salcianu 1.1.2.46 }
1736 salcianu 1.1.2.46
1737 salcianu 1.1.2.46 // Parameters:
1738 salcianu 1.1.2.46 // nodes - the set of PANodes that escape from some method called by mm,
1739 salcianu 1.1.2.46 // only into the caller (ie mm).
1740 salcianu 1.12 // level - nodes originate in a callee at distance "level" in the call
1741 salcianu 1.1.2.46 // graph; to be able to stack allocate them, an inlining chain of length
1742 salcianu 1.12 // at least "level" is necessary.
1743 salcianu 1.1.2.54 private void discover_inlining_chains(MetaMethod mm,
1744 salcianu 1.1.2.54 Set sa_nodes, Set ta_nodes,
1745 salcianu 1.1.2.47 int level) {
1746 salcianu 1.12
1747 salcianu 1.12 String header = null;
1748 salcianu 1.12 if(DEBUG) {
1749 salcianu 1.12 StringBuffer buff = new StringBuffer();
1750 salcianu 1.12 for(int i = 0; i < level; i++)
1751 salcianu 1.12 buff.append(" ");
1752 salcianu 1.12 buff.append("dinlc: ");
1753 salcianu 1.12 header = buff.toString();
1754 salcianu 1.12 System.out.println(header + "ENTRY " + mm.getHMethod() + " , " + sa_nodes + " , " + ta_nodes + " , " + level);
1755 salcianu 1.12 }
1756 salcianu 1.12
1757 salcianu 1.1.2.46 // iterate through all the call sites where mm is called
1758 salcianu 1.1.2.46 MetaMethod[] callers = mac.getCallers(mm);
1759 salcianu 1.1.2.46 for(int i = 0; i < callers.length; i++) {
1760 salcianu 1.1.2.46 MetaMethod mcaller = callers[i];
1761 salcianu 1.1.2.46
1762 salcianu 1.14 // mcaller should not be optimized
1763 salcianu 1.14 if(!mms.contains(mcaller)) continue;
1764 salcianu 1.14 ParIntGraph pig_caller = pa.getIntParIntGraph(mcaller);
1765 salcianu 1.14 // the analysis is unable to analyze mcaller
1766 salcianu 1.14 if(pig_caller == null) continue;
1767 salcianu 1.14
1768 salcianu 1.14 Set/*<PANode>*/ lost_caller = pa.getLostNodes(mcaller);
1769 salcianu 1.14 Set/*<CALL>*/ call_sites = mcg.getCallSites(mcaller);
1770 salcianu 1.12
1771 salcianu 1.12 if(DEBUG)
1772 salcianu 1.12 System.out.println(header + "CALLER: " + mcaller.getHMethod());
1773 salcianu 1.12
1774 cananian 1.19 for(Object csO : call_sites) {
1775 cananian 1.19 CALL cs = (CALL) csO;
1776 salcianu 1.1.2.53
1777 salcianu 1.1.2.46 MetaMethod[] callees = mcg.getCallees(mcaller, cs);
1778 salcianu 1.15 if(callees.length == 0) {
1779 salcianu 1.15 System.out.println
1780 salcianu 1.15 ("there has to be at least one callee: " +
1781 salcianu 1.15 Util.code2str(cs));
1782 salcianu 1.15 continue;
1783 salcianu 1.15 }
1784 salcianu 1.12
1785 salcianu 1.12 // we can only inline call sites that calls only mm
1786 salcianu 1.12 if((callees.length != 1) || !callees[0].equals(mm)
1787 salcianu 1.14 || !good_cs2(cs) )
1788 salcianu 1.12 continue;
1789 salcianu 1.12
1790 salcianu 1.12 if(DEBUG)
1791 salcianu 1.12 System.out.println(header + "good: " + Util.code2str(cs));
1792 salcianu 1.12
1793 salcianu 1.1.2.54 // refuse to stack allocate stuff in a loop
1794 salcianu 1.1.2.54 if(opt.stack_allocate_not_in_loops() && in_a_loop(cs)) {
1795 salcianu 1.12 if(DEBUG)
1796 salcianu 1.12 System.out.println(header + Util.code2str(cs) +
1797 salcianu 1.12 " is in a loop -> don't sa");
1798 salcianu 1.1.2.54 ta_nodes = new HashSet(ta_nodes);
1799 cananian 1.19 for(Object nodeO : sa_nodes) {
1800 cananian 1.19 PANode node = (PANode) nodeO;
1801 salcianu 1.1.2.54 MyAP ap = getAP_special(node);
1802 salcianu 1.1.2.54 if(!ap.ta)
1803 salcianu 1.1.2.54 ta_nodes.add(node);
1804 salcianu 1.1.2.54 }
1805 salcianu 1.1.2.54 sa_nodes = Collections.EMPTY_SET;
1806 salcianu 1.1.2.54 }
1807 salcianu 1.1.2.46
1808 salcianu 1.1.2.46 current_chain_cs.addLast(cs);
1809 salcianu 1.1.2.46 current_chain_callees.addLast(mm.getHMethod());
1810 salcianu 1.1.2.54
1811 salcianu 1.1.2.46 // compute specializations of nodes for cs
1812 salcianu 1.1.2.54 Set sa_specs = specializeNodes(sa_nodes, cs);
1813 salcianu 1.1.2.54 Set ta_specs = specializeNodes(ta_nodes, cs);
1814 salcianu 1.1.2.54
1815 salcianu 1.1.2.46 // B = specs that are captured in mcaller
1816 salcianu 1.14 Set sa_B = captured_subset(sa_specs, pig_caller, lost_caller);
1817 salcianu 1.14 Set ta_B = captured_subset(ta_specs, pig_caller, lost_caller);
1818 salcianu 1.12
1819 salcianu 1.12 if(DEBUG &&
1820 salcianu 1.12 opt.DO_STACK_ALLOCATION && opt.DO_INLINING_FOR_SA)
1821 salcianu 1.12 System.out.println(header + "sa_specs=" + sa_specs +
1822 salcianu 1.12 " sa_B=" + sa_B);
1823 salcianu 1.12
1824 salcianu 1.12 if(DEBUG &&
1825 salcianu 1.12 opt.DO_THREAD_ALLOCATION && opt.DO_INLINING_FOR_TA)
1826 salcianu 1.12 System.out.println(header + " ta_B=" + ta_B);
1827 salcianu 1.1.2.46
1828 salcianu 1.1.2.46 // here we have some good inlining chain; mark it
1829 salcianu 1.1.2.54 if((opt.DO_STACK_ALLOCATION &&
1830 salcianu 1.1.2.54 opt.DO_INLINING_FOR_SA && !sa_B.isEmpty()) ||
1831 salcianu 1.1.2.54 (opt.DO_THREAD_ALLOCATION &&
1832 salcianu 1.1.2.54 opt.DO_INLINING_FOR_TA && !ta_B.isEmpty())) {
1833 salcianu 1.12 InliningChain new_ic =
1834 salcianu 1.12 new InliningChain(current_chain_cs,
1835 salcianu 1.12 current_chain_callees,
1836 salcianu 1.12 get_news(sa_B),
1837 salcianu 1.12 get_news(ta_B));
1838 salcianu 1.12 if(DEBUG)
1839 salcianu 1.12 System.out.print(header + "chain: " + new_ic);
1840 salcianu 1.12 if(new_ic.isAcceptable())
1841 salcianu 1.12 chains.add(new_ic);
1842 salcianu 1.1.2.46 }
1843 salcianu 1.1.2.46
1844 salcianu 1.1.2.48 // the length of current_chain_cs is level + 1
1845 salcianu 1.1.2.48 if(level + 1 < opt.MAX_INLINING_LEVEL) {
1846 salcianu 1.14
1847 salcianu 1.14 // avoid inlining the class initializers: past experience
1848 salcianu 1.14 // showed this might lead to circular dependencies in the
1849 salcianu 1.14 // static initializer code
1850 salcianu 1.14 if(mcaller.getHMethod().getName().equals("<clinit>"))
1851 salcianu 1.14 continue;
1852 salcianu 1.14
1853 salcianu 1.1.2.46 // C = specs that escape only in caller
1854 salcianu 1.14 Set sa_C = only_in_caller_subset(sa_specs, pig_caller,
1855 salcianu 1.14 lost_caller);
1856 salcianu 1.14 Set ta_C = only_in_caller_subset(ta_specs, pig_caller,
1857 salcianu 1.14 lost_caller);
1858 salcianu 1.1.2.46
1859 salcianu 1.1.2.54 if((opt.DO_STACK_ALLOCATION &&
1860 salcianu 1.1.2.54 opt.DO_INLINING_FOR_SA && !sa_C.isEmpty()) ||
1861 salcianu 1.1.2.54 (opt.DO_THREAD_ALLOCATION &&
1862 salcianu 1.1.2.54 opt.DO_INLINING_FOR_TA && !ta_C.isEmpty()))
1863 salcianu 1.1.2.54 discover_inlining_chains
1864 salcianu 1.9 (mcaller, sa_C, ta_C, level + 1);
1865 salcianu 1.1.2.46 }
1866 salcianu 1.12 else {
1867 salcianu 1.12 if(DEBUG)
1868 salcianu 1.12 System.out.println(header + "too deep " + (level+2));
1869 salcianu 1.12 }
1870 salcianu 1.1.2.54
1871 salcianu 1.1.2.46 current_chain_cs.removeLast();
1872 salcianu 1.1.2.46 current_chain_callees.removeLast();
1873 salcianu 1.1.2.46 }
1874 salcianu 1.1.2.46 }
1875 salcianu 1.1.2.46 }
1876 salcianu 1.1.2.46
1877 salcianu 1.1.2.54
1878 salcianu 1.1.2.54 // get the allocation policy object associated with the object creation
1879 salcianu 1.1.2.54 // site for node. node might be a specialization so we have to go first
1880 salcianu 1.1.2.54 // to its root node and take the AP of this one.
1881 salcianu 1.1.2.54 private MyAP getAP_special(PANode node) {
1882 salcianu 1.1.2.54 PANode root = node.getRoot();
1883 salcianu 1.1.2.54 Quad q = (Quad) node_rep.node2Code(root);
1884 salcianu 1.1.2.54 return getAPObj(q);
1885 salcianu 1.1.2.54 }
1886 salcianu 1.1.2.54
1887 salcianu 1.1.2.54
1888 salcianu 1.1.2.51 private LinkedList chains = null;
1889 salcianu 1.1.2.46
1890 salcianu 1.1.2.46
1891 salcianu 1.1.2.46 // Computes the set of NEW / ANEW quads that created the nodes
1892 salcianu 1.1.2.46 private Set get_news(final Set nodes) {
1893 salcianu 1.1.2.46 Set result = new HashSet();
1894 salcianu 1.1.2.46 for(Iterator it = nodes.iterator(); it.hasNext(); ) {
1895 salcianu 1.1.2.46 PANode node = ((PANode) it.next()).getRoot();
1896 salcianu 1.1.2.46 Quad quad = (Quad) node_rep.node2Code(node);
1897 cananian 1.3.2.1 assert quad != null : "No quad for " + node;
1898 salcianu 1.1.2.46 result.add(quad);
1899 salcianu 1.1.2.46 }
1900 salcianu 1.1.2.46 return result;
1901 salcianu 1.1.2.46 }
1902 salcianu 1.1.2.46
1903 salcianu 1.1.2.46
1904 salcianu 1.1.2.46 // specialize a set of nodes for a given call site
1905 salcianu 1.1.2.46 private Set specializeNodes(final Set nodes, final CALL cs) {
1906 salcianu 1.1.2.46 Set result = new HashSet();
1907 cananian 1.19 for(Object nodeO : nodes) {
1908 cananian 1.19 PANode node = (PANode) nodeO;
1909 salcianu 1.1.2.46 PANode spec = node.csSpecialize(cs);
1910 salcianu 1.1.2.46 if(spec == null) continue;
1911 salcianu 1.1.2.46 result.add(spec);
1912 salcianu 1.1.2.46 }
1913 salcianu 1.1.2.46 return result;
1914 salcianu 1.1.2.46 }
1915 salcianu 1.1.2.46
1916 salcianu 1.1.2.46
1917 salcianu 1.1.2.46 // Returns a subset of nodes containing the nodes captured in pig
1918 salcianu 1.1.2.46 private Set captured_subset(final Set nodes,
1919 salcianu 1.14 final ParIntGraph pig,
1920 salcianu 1.14 final Set lost) {
1921 salcianu 1.1.2.46 Set result = new HashSet();
1922 cananian 1.19 for(Object nodeO : nodes) {
1923 cananian 1.19 PANode node = (PANode) nodeO;
1924 salcianu 1.14 if(!lost.contains(pig) && pig.G.captured(node))
1925 salcianu 1.1.2.46 result.add(node);
1926 salcianu 1.1.2.46 }
1927 salcianu 1.1.2.46 return result;
1928 salcianu 1.1.2.46 }
1929 salcianu 1.1.2.46
1930 salcianu 1.1.2.46 // Returns a subset of nodes containing the nodes that escape
1931 salcianu 1.1.2.46 // only (exactly) in the caller
1932 salcianu 1.1.2.46 private Set only_in_caller_subset(final Set nodes,
1933 salcianu 1.14 final ParIntGraph pig,
1934 salcianu 1.14 final Set lost) {
1935 salcianu 1.1.2.46 Set result = new HashSet();
1936 cananian 1.19 for(Object nodeO : nodes) {
1937 cananian 1.19 PANode node = (PANode) nodeO;
1938 salcianu 1.12 if(pig.G.captured(node)) continue;
1939 salcianu 1.12
1940 salcianu 1.14 if(!lost.contains(node) && lostOnlyInCaller(node, pig))
1941 salcianu 1.1.2.46 result.add(node);
1942 salcianu 1.12 else {
1943 salcianu 1.12 if(DEBUG) {
1944 salcianu 1.12 System.out.println("only_in_caller_subset: " + node + " escapes somewhere else" + pig.G.e.nodeHolesSet(node));
1945 salcianu 1.12 }
1946 salcianu 1.12 }
1947 salcianu 1.1.2.46 }
1948 salcianu 1.1.2.46 return result;
1949 salcianu 1.1.2.46 }
1950 salcianu 1.1.2.46
1951 salcianu 1.1.2.46
1952 salcianu 1.1.2.46 private void extra_stack_allocation(Set news) {
1953 cananian 1.19 for(Object qO : news) {
1954 cananian 1.19 Quad q = (Quad) qO;
1955 salcianu 1.1.2.46
1956 salcianu 1.6 System.out.println("STKALLOC " + Util.code2str(q));
1957 salcianu 1.1.2.46
1958 salcianu 1.1.2.54 MyAP ap = getAPObj(q);
1959 salcianu 1.1.2.54 // new MyAP(getAllocatedType(q));
1960 salcianu 1.1.2.54 ap.sa = true;
1961 salcianu 1.16 if(opt.GEN_SYNC_FLAG)
1962 salcianu 1.16 ap.ns = true; // SYNC
1963 salcianu 1.1.2.54 setAPObj(q, ap);
1964 salcianu 1.1.2.54 }
1965 salcianu 1.1.2.54 }
1966 salcianu 1.1.2.54
1967 salcianu 1.1.2.54
1968 salcianu 1.1.2.54 private void extra_thread_allocation(Set news) {
1969 cananian 1.19 for(Object qO : news) {
1970 cananian 1.19 Quad q = (Quad) qO;
1971 salcianu 1.1.2.54
1972 salcianu 1.6 System.out.println("THRALLOC " + Util.code2str(q));
1973 salcianu 1.1.2.54
1974 salcianu 1.1.2.54 MyAP ap = getAPObj(q);
1975 salcianu 1.1.2.54 // new MyAP(getAllocatedType(q));
1976 salcianu 1.1.2.54 ap.ta = true;
1977 salcianu 1.16 if(opt.GEN_SYNC_FLAG)
1978 salcianu 1.16 ap.ns = true; // SYNC
1979 salcianu 1.1.2.46 setAPObj(q, ap);
1980 salcianu 1.1.2.46 }
1981 salcianu 1.1.2.46 }
1982 salcianu 1.1.2.46
1983 salcianu 1.1.2.46
1984 salcianu 1.1.2.46 private class InliningChain {
1985 salcianu 1.1.2.46 private LinkedList calls;
1986 salcianu 1.1.2.46 private LinkedList callees;
1987 salcianu 1.1.2.54 private Set sa_news;
1988 salcianu 1.1.2.54 private Set ta_news;
1989 salcianu 1.1.2.46
1990 salcianu 1.1.2.46 InliningChain(final LinkedList calls,
1991 salcianu 1.1.2.54 final LinkedList callees,
1992 salcianu 1.1.2.54 final Set sa_news,
1993 salcianu 1.1.2.54 final Set ta_news) {
1994 salcianu 1.1.2.46 this.calls = (LinkedList) calls.clone();
1995 salcianu 1.1.2.46 this.callees = (LinkedList) callees.clone();
1996 salcianu 1.1.2.54 this.sa_news = new HashSet(sa_news);
1997 salcianu 1.1.2.54 this.ta_news = new HashSet(ta_news);
1998 salcianu 1.1.2.46 }
1999 salcianu 1.1.2.46
2000 salcianu 1.1.2.54 Set get_sa_news() { return sa_news; }
2001 salcianu 1.1.2.54 Set get_ta_news() { return ta_news; }
2002 salcianu 1.1.2.46
2003 salcianu 1.1.2.46 public String toString() {
2004 salcianu 1.1.2.46 StringBuffer buff = new StringBuffer();
2005 salcianu 1.1.2.46 buff.append("INLINING CHAIN (" + calls.size() + "): {\n CALLS:\n");
2006 cananian 1.19 for(Object csO : calls) {
2007 cananian 1.19 CALL cs = (CALL) csO;
2008 salcianu 1.9 buff.append(" ")
2009 salcianu 1.9 .append(Util.code2str(cs))
2010 salcianu 1.9 .append(" [ ")
2011 salcianu 1.9 .append(extract_caller(cs))
2012 salcianu 1.9 .append(" ] { ")
2013 salcianu 1.9 .append(extract_callee(cs))
2014 salcianu 1.9 .append(" }\n");
2015 salcianu 1.1.2.46 }
2016 salcianu 1.9
2017 salcianu 1.1.2.54 present_news(buff, " STACK ALLOCATABLE STUFF:", get_sa_news());
2018 salcianu 1.1.2.54 present_news(buff, " THREAD ALLOCATABLE STUFF:", get_ta_news());
2019 salcianu 1.1.2.54 buff.append("}\n");
2020 salcianu 1.1.2.54 return buff.toString();
2021 salcianu 1.1.2.54 }
2022 salcianu 1.1.2.54
2023 salcianu 1.1.2.54 // aux method for pretty printing of sa/ta news
2024 salcianu 1.1.2.54 private void present_news(StringBuffer buff, String message,
2025 salcianu 1.1.2.54 Set news) {
2026 salcianu 1.1.2.54 if(news.isEmpty()) return;
2027 salcianu 1.9 buff.append(message).append("\n");
2028 salcianu 1.1.2.46 for(Iterator it = news.iterator(); it.hasNext(); ) {
2029 salcianu 1.9 buff.append(" ")
2030 salcianu 1.9 .append(Util.code2str((Quad) it.next()))
2031 salcianu 1.9 .append("\n");
2032 salcianu 1.1.2.46 }
2033 salcianu 1.1.2.46 }
2034 salcianu 1.1.2.46
2035 salcianu 1.1.2.47
2036 salcianu 1.1.2.51 // test whether the size of the inlined method will be smaller
2037 salcianu 1.1.2.47 // than the maximum acceptable one.
2038 salcianu 1.1.2.47 public boolean isAcceptable() {
2039 salcianu 1.1.2.47 if(isDone()) return true;
2040 salcianu 1.1.2.47 int size = get_method_size(extract_caller(getLastCall()));
2041 cananian 1.19 for(Object csO : calls) {
2042 cananian 1.19 CALL cs = (CALL) csO;
2043 salcianu 1.1.2.47 HMethod hm = extract_callee(cs);
2044 salcianu 1.1.2.54 if(get_method_size(hm) > opt.MAX_INLINABLE_METHOD_SIZE)
2045 salcianu 1.1.2.54 return false;
2046 salcianu 1.1.2.54 //if(hm != null)
2047 salcianu 1.1.2.54 size += get_method_size(hm);
2048 salcianu 1.1.2.47 }
2049 salcianu 1.1.2.48 return size < opt.MAX_METHOD_SIZE;
2050 salcianu 1.1.2.47 }
2051 salcianu 1.1.2.48
2052 salcianu 1.1.2.47 private int get_method_size(HMethod hm) {
2053 salcianu 1.1.2.47 HCode hcode = hcf.convert(hm);
2054 salcianu 1.1.2.47 return hcode.getElementsL().size();
2055 salcianu 1.1.2.47 }
2056 salcianu 1.1.2.47
2057 salcianu 1.1.2.46 // The call cs has just been inlined. As a consequence, any inlining
2058 salcianu 1.1.2.46 // chain containing cs should be updated in the following way: cs
2059 salcianu 1.1.2.46 // must be removed from there and the previous call in the chain
2060 salcianu 1.1.2.46 // updated according to the old2new map.
2061 salcianu 1.1.2.46 void update_ic(CALL cs, Map old2new) {
2062 salcianu 1.1.2.46 if(isDone()) return;
2063 salcianu 1.1.2.46 if(!calls.contains(cs)) return;
2064 salcianu 1.1.2.46
2065 salcianu 1.1.2.46 if(DEBUG_IC)
2066 salcianu 1.1.2.46 System.out.println("update_ic(" + cs + ") for " + this);
2067 salcianu 1.1.2.46
2068 salcianu 1.1.2.46 CALL first_cs = (CALL) calls.getFirst();
2069 salcianu 1.1.2.46 if(first_cs == cs) {
2070 salcianu 1.1.2.46 if(DEBUG_IC)
2071 salcianu 1.1.2.46 System.out.println("The news are modified");
2072 salcianu 1.1.2.54 sa_news = project_set(sa_news, old2new);
2073 salcianu 1.1.2.54 ta_news = project_set(ta_news, old2new);
2074 salcianu 1.1.2.46 }
2075 salcianu 1.1.2.46
2076 salcianu 1.1.2.46 ListIterator ithm = callees.listIterator(0);
2077 salcianu 1.1.2.46 for(ListIterator it = calls.listIterator(0); it.hasNext(); ) {
2078 salcianu 1.1.2.46 CALL current = (CALL) it.next();
2079 salcianu 1.1.2.46 HMethod current_callee = (HMethod) ithm.next();
2080 salcianu 1.1.2.46
2081 salcianu 1.1.2.46 if(cs == current) {
2082 salcianu 1.1.2.46 it.remove(); // this inlining has already been done
2083 salcianu 1.1.2.46 ithm.remove(); // it is hence unnecessary
2084 salcianu 1.1.2.46
2085 salcianu 1.1.2.46 if(it.hasPrevious()) {
2086 salcianu 1.1.2.46 CALL previous = (CALL) it.previous();
2087 salcianu 1.1.2.46 CALL new_prev = (CALL) old2new.get(previous);
2088 salcianu 1.1.2.46 if(DEBUG_IC) {
2089 salcianu 1.1.2.46 System.out.println("previous = " + previous);
2090 salcianu 1.1.2.46 System.out.println("new_prev = " + new_prev);
2091 salcianu 1.1.2.46 }
2092 salcianu 1.1.2.46 it.remove(); // replace the previous call with
2093 salcianu 1.1.2.46 it.add(new_prev); // its updated version
2094 salcianu 1.1.2.46 }
2095 salcianu 1.1.2.46
2096 salcianu 1.1.2.46 if(DEBUG_IC)
2097 salcianu 1.1.2.46 System.out.println("After " + this);
2098 salcianu 1.1.2.46
2099 salcianu 1.1.2.54 if(isDone()) {
2100 salcianu 1.1.2.54 extra_stack_allocation(sa_news);
2101 salcianu 1.1.2.54 extra_thread_allocation(ta_news);
2102 salcianu 1.1.2.54 }
2103 salcianu 1.1.2.46 }
2104 salcianu 1.1.2.46 }
2105 salcianu 1.1.2.46 }
2106 salcianu 1.1.2.46
2107 salcianu 1.1.2.46 private Set project_set(Set set, Map old2new) {
2108 salcianu 1.1.2.46 Set result = new HashSet();
2109 cananian 1.19 for(Object old_quadO : set) {
2110 cananian 1.19 Quad old_quad = (Quad) old_quadO;
2111 salcianu 1.1.2.46 Quad new_quad = (Quad) old2new.get(old_quad);
2112 cananian 1.3.2.1 assert new_quad != null : "Warning: no new Quad for " +
2113 salcianu 1.6 Util.code2str(old_quad) + " in [ " +
2114 cananian 1.3.2.1 quad2method(old_quad) + " ]";
2115 salcianu 1.1.2.46 result.add(new_quad);
2116 salcianu 1.1.2.46 }
2117 salcianu 1.1.2.46 return result;
2118 salcianu 1.1.2.46 }
2119 salcianu 1.1.2.46
2120 salcianu 1.1.2.46
2121 salcianu 1.1.2.46 CALL getLastCall() {
2122 cananian 1.3.2.1 assert !isDone() : "You shouldn't call this!";
2123 salcianu 1.1.2.46 return (CALL) calls.getLast();
2124 salcianu 1.1.2.46 }
2125 salcianu 1.1.2.46
2126 salcianu 1.1.2.46
2127 salcianu 1.1.2.46 HMethod getLastCallee() {
2128 cananian 1.3.2.1 assert !isDone() : "You shouldn't call this!";
2129 salcianu 1.1.2.46 return (HMethod) callees.getLast();
2130 salcianu 1.1.2.46 }
2131 salcianu 1.1.2.46
2132 salcianu 1.1.2.46
2133 salcianu 1.1.2.46 boolean isDone() {
2134 salcianu 1.1.2.46 return calls.isEmpty();
2135 salcianu 1.1.2.46 }
2136 salcianu 1.1.2.46
2137 salcianu 1.1.2.51
2138 salcianu 1.1.2.46 // Returns the rang of the last method (the one where everything in
2139 salcianu 1.1.2.46 // this inlining chain is going to be inlined).
2140 salcianu 1.1.2.46 int get_rang() {
2141 salcianu 1.1.2.46 return MAInfo.this.get_rang(extract_caller(getLastCall()));
2142 salcianu 1.1.2.46 }
2143 salcianu 1.9 };
2144 salcianu 1.1.2.47
2145 salcianu 1.9
2146 salcianu 1.9 private void process_chain(InliningChain ic) {
2147 salcianu 1.9 if(ic.isDone()) return;
2148 salcianu 1.9 // if(DEBUG)
2149 salcianu 1.9 System.out.println("\n\nPROCESSING " + ic);
2150 salcianu 1.9
2151 salcianu 1.9 while(!ic.isDone()) {
2152 salcianu 1.9 CALL cs = ic.getLastCall();
2153 salcianu 1.9 HMethod hcaller = extract_caller(cs);
2154 salcianu 1.9 System.out.println("hcaller = " + hcaller);
2155 salcianu 1.9
2156 salcianu 1.9 HCode hcode = hcf.convert(hcaller);
2157 salcianu 1.9
2158 salcianu 1.9 HMethod hcallee = ic.getLastCallee();
2159 salcianu 1.9 Map old2new = inline_call_site(cs, hcaller, hcallee, hcf);
2160 salcianu 1.9
2161 salcianu 1.9 // update all the Inlining Chains
2162 salcianu 1.9 for(Iterator it = chains.iterator(); it.hasNext(); )
2163 salcianu 1.9 ((InliningChain) it.next()).update_ic(cs, old2new);
2164 salcianu 1.1.2.47 }
2165 salcianu 1.9 }
2166 salcianu 1.1.2.46
2167 salcianu 1.1.2.46
2168 salcianu 1.1.2.46 private void sort_chains() {
2169 salcianu 1.1.2.46 Object[] ics = chains.toArray(new Object[chains.size()]);
2170 salcianu 1.9 Arrays.sort
2171 salcianu 1.9 (ics,
2172 salcianu 1.9 new Comparator() {
2173 salcianu 1.1.2.46 public int compare(Object obj1, Object obj2) {
2174 salcianu 1.1.2.46 int rang1 = ((InliningChain) obj1).get_rang();
2175 salcianu 1.1.2.46 int rang2 = ((InliningChain) obj2).get_rang();
2176 salcianu 1.1.2.46 if(rang1 < rang2) return -1;
2177 salcianu 1.1.2.46 if(rang1 == rang2) return 0;
2178 salcianu 1.1.2.46 return 1;
2179 salcianu 1.1.2.46 }
2180 salcianu 1.1.2.46 public boolean equals(Object obj) {
2181 salcianu 1.1.2.46 return obj == this;
2182 salcianu 1.1.2.46 }
2183 salcianu 1.1.2.46 });
2184 salcianu 1.1.2.46 chains = new LinkedList();
2185 salcianu 1.1.2.46 for(int i = 0; i < ics.length; i++)
2186 salcianu 1.1.2.46 chains.addLast(ics[i]);
2187 salcianu 1.1.2.46 }
2188 salcianu 1.1.2.46
2189 salcianu 1.1.2.46
2190 salcianu 1.1.2.46 private void process_inlining_chains() {
2191 salcianu 1.12 // if(DEBUG_IC) {
2192 salcianu 1.1.2.49 Util.print_collection(chains, "\n\nINLINING CHAINS");
2193 salcianu 1.1.2.49 System.out.println("=======================");
2194 salcianu 1.12 //}
2195 salcianu 1.1.2.52
2196 salcianu 1.9 // db debug
2197 salcianu 1.1.2.52 System.out.println("Chains that influence Main.run");
2198 cananian 1.19 for(Object icO : chains) {
2199 cananian 1.19 InliningChain ic = (InliningChain) icO;
2200 salcianu 1.1.2.52 HMethod hm = ic.getLastCallee();
2201 salcianu 1.1.2.52 if(hm.getName().equals("run") &&
2202 salcianu 1.1.2.52 hm.getClass().getName().equals("Main"))
2203 salcianu 1.9 System.out.println(ic);
2204 salcianu 1.9 }
2205 salcianu 1.9 System.out.println("============================");
2206 salcianu 1.9
2207 salcianu 1.9 sort_chains();
2208 salcianu 1.9
2209 salcianu 1.9 Set toPrune = new HashSet();
2210 salcianu 1.9 for(Iterator it = chains.iterator(); it.hasNext(); ) {
2211 salcianu 1.9 CALL cs = ((InliningChain) it.next()).getLastCall();
2212 salcianu 1.9 toPrune.add(cs.getFactory().getParent());
2213 salcianu 1.9 }
2214 salcianu 1.9
2215 salcianu 1.9 for(Iterator it = chains.iterator(); it.hasNext(); )
2216 salcianu 1.9 process_chain((InliningChain) it.next());
2217 salcianu 1.9
2218 salcianu 1.9 // remove the newly introduced unreachable code
2219 cananian 1.19 for(Object hcodeO : toPrune) {
2220 cananian 1.19 Code hcode = (Code) hcodeO;
2221 salcianu 1.9 if(DEBUG_IC)
2222 salcianu 1.9 System.out.print("Pruning " + hcode.getMethod());
2223 salcianu 1.9 Unreachable.prune(hcode);
2224 salcianu 1.9 }
2225 salcianu 1.1.2.46 }
2226 salcianu 1.9
2227 salcianu 1.1.2.48 //////////// INLINING STUFF END /////////////////////////////////////
2228 salcianu 1.1.2.48 /////////////////////////////////////////////////////////////////////
2229 salcianu 1.1.2.1 }
2230 cananian 1.2