001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.compilers.opt.escape;
014
015 import java.util.ArrayList;
016 import java.util.Enumeration;
017 import java.util.HashSet;
018 import java.util.Iterator;
019 import java.util.Set;
020 import org.jikesrvm.VM;
021 import org.jikesrvm.classloader.RVMMethod;
022 import org.jikesrvm.classloader.NormalMethod;
023 import org.jikesrvm.compilers.opt.DefUse;
024 import org.jikesrvm.compilers.opt.MagicNotImplementedException;
025 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
026 import org.jikesrvm.compilers.opt.OptOptions;
027 import org.jikesrvm.compilers.opt.Simple;
028 import org.jikesrvm.compilers.opt.bc2ir.ConvertBCtoHIR;
029 import org.jikesrvm.compilers.opt.driver.CompilationPlan;
030 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
031 import org.jikesrvm.compilers.opt.driver.OptimizationPlanCompositeElement;
032 import org.jikesrvm.compilers.opt.driver.OptimizationPlanElement;
033 import org.jikesrvm.compilers.opt.driver.OptimizingCompiler;
034 import org.jikesrvm.compilers.opt.ir.AStore;
035 import org.jikesrvm.compilers.opt.ir.Call;
036 import org.jikesrvm.compilers.opt.ir.Move;
037 import org.jikesrvm.compilers.opt.ir.IR;
038 import org.jikesrvm.compilers.opt.ir.Instruction;
039 import org.jikesrvm.compilers.opt.ir.Operators;
040 import static org.jikesrvm.compilers.opt.ir.Operators.ADDR_2INT_opcode;
041 import static org.jikesrvm.compilers.opt.ir.Operators.ADDR_2LONG_opcode;
042 import static org.jikesrvm.compilers.opt.ir.Operators.ARRAYLENGTH_opcode;
043 import static org.jikesrvm.compilers.opt.ir.Operators.ATHROW_opcode;
044 import static org.jikesrvm.compilers.opt.ir.Operators.ATTEMPT_ADDR_opcode;
045 import static org.jikesrvm.compilers.opt.ir.Operators.ATTEMPT_INT_opcode;
046 import static org.jikesrvm.compilers.opt.ir.Operators.ATTEMPT_LONG_opcode;
047 import static org.jikesrvm.compilers.opt.ir.Operators.BOOLEAN_CMP_ADDR_opcode;
048 import static org.jikesrvm.compilers.opt.ir.Operators.BOOLEAN_CMP_INT_opcode;
049 import static org.jikesrvm.compilers.opt.ir.Operators.BOUNDS_CHECK_opcode;
050 import static org.jikesrvm.compilers.opt.ir.Operators.BYTE_ALOAD_opcode;
051 import static org.jikesrvm.compilers.opt.ir.Operators.BYTE_ASTORE_opcode;
052 import static org.jikesrvm.compilers.opt.ir.Operators.BYTE_LOAD_opcode;
053 import static org.jikesrvm.compilers.opt.ir.Operators.BYTE_STORE_opcode;
054 import static org.jikesrvm.compilers.opt.ir.Operators.CALL_opcode;
055 import static org.jikesrvm.compilers.opt.ir.Operators.CHECKCAST_NOTNULL_opcode;
056 import static org.jikesrvm.compilers.opt.ir.Operators.CHECKCAST_UNRESOLVED_opcode;
057 import static org.jikesrvm.compilers.opt.ir.Operators.CHECKCAST_opcode;
058 import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_ALOAD_opcode;
059 import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_ASTORE_opcode;
060 import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_LOAD_opcode;
061 import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_STORE_opcode;
062 import static org.jikesrvm.compilers.opt.ir.Operators.FLOAT_ALOAD_opcode;
063 import static org.jikesrvm.compilers.opt.ir.Operators.FLOAT_ASTORE_opcode;
064 import static org.jikesrvm.compilers.opt.ir.Operators.FLOAT_LOAD_opcode;
065 import static org.jikesrvm.compilers.opt.ir.Operators.FLOAT_STORE_opcode;
066 import static org.jikesrvm.compilers.opt.ir.Operators.GETFIELD_opcode;
067 import static org.jikesrvm.compilers.opt.ir.Operators.GETSTATIC_opcode;
068 import static org.jikesrvm.compilers.opt.ir.Operators.GET_CAUGHT_EXCEPTION_opcode;
069 import static org.jikesrvm.compilers.opt.ir.Operators.GET_OBJ_TIB_opcode;
070 import static org.jikesrvm.compilers.opt.ir.Operators.GET_TYPE_FROM_TIB_opcode;
071 import static org.jikesrvm.compilers.opt.ir.Operators.IG_CLASS_TEST_opcode;
072 import static org.jikesrvm.compilers.opt.ir.Operators.IG_METHOD_TEST_opcode;
073 import static org.jikesrvm.compilers.opt.ir.Operators.IG_PATCH_POINT_opcode;
074 import static org.jikesrvm.compilers.opt.ir.Operators.INSTANCEOF_NOTNULL_opcode;
075 import static org.jikesrvm.compilers.opt.ir.Operators.INSTANCEOF_UNRESOLVED_opcode;
076 import static org.jikesrvm.compilers.opt.ir.Operators.INSTANCEOF_opcode;
077 import static org.jikesrvm.compilers.opt.ir.Operators.INT_2ADDRSigExt_opcode;
078 import static org.jikesrvm.compilers.opt.ir.Operators.INT_2ADDRZerExt_opcode;
079 import static org.jikesrvm.compilers.opt.ir.Operators.INT_2LONG_opcode;
080 import static org.jikesrvm.compilers.opt.ir.Operators.INT_ADD_opcode;
081 import static org.jikesrvm.compilers.opt.ir.Operators.INT_ALOAD_opcode;
082 import static org.jikesrvm.compilers.opt.ir.Operators.INT_AND_opcode;
083 import static org.jikesrvm.compilers.opt.ir.Operators.INT_ASTORE_opcode;
084 import static org.jikesrvm.compilers.opt.ir.Operators.INT_COND_MOVE_opcode;
085 import static org.jikesrvm.compilers.opt.ir.Operators.INT_DIV_opcode;
086 import static org.jikesrvm.compilers.opt.ir.Operators.INT_IFCMP_opcode;
087 import static org.jikesrvm.compilers.opt.ir.Operators.INT_LOAD_opcode;
088 import static org.jikesrvm.compilers.opt.ir.Operators.INT_MOVE_opcode;
089 import static org.jikesrvm.compilers.opt.ir.Operators.INT_MUL_opcode;
090 import static org.jikesrvm.compilers.opt.ir.Operators.INT_NEG_opcode;
091 import static org.jikesrvm.compilers.opt.ir.Operators.INT_OR_opcode;
092 import static org.jikesrvm.compilers.opt.ir.Operators.INT_REM_opcode;
093 import static org.jikesrvm.compilers.opt.ir.Operators.INT_SHL_opcode;
094 import static org.jikesrvm.compilers.opt.ir.Operators.INT_SHR_opcode;
095 import static org.jikesrvm.compilers.opt.ir.Operators.INT_STORE_opcode;
096 import static org.jikesrvm.compilers.opt.ir.Operators.INT_SUB_opcode;
097 import static org.jikesrvm.compilers.opt.ir.Operators.INT_USHR_opcode;
098 import static org.jikesrvm.compilers.opt.ir.Operators.INT_XOR_opcode;
099 import static org.jikesrvm.compilers.opt.ir.Operators.INT_ZERO_CHECK_opcode;
100 import static org.jikesrvm.compilers.opt.ir.Operators.IR_PROLOGUE_opcode;
101 import static org.jikesrvm.compilers.opt.ir.Operators.LONG_ALOAD_opcode;
102 import static org.jikesrvm.compilers.opt.ir.Operators.LONG_ASTORE_opcode;
103 import static org.jikesrvm.compilers.opt.ir.Operators.LONG_LOAD_opcode;
104 import static org.jikesrvm.compilers.opt.ir.Operators.LONG_STORE_opcode;
105 import static org.jikesrvm.compilers.opt.ir.Operators.MONITORENTER_opcode;
106 import static org.jikesrvm.compilers.opt.ir.Operators.MONITOREXIT_opcode;
107 import static org.jikesrvm.compilers.opt.ir.Operators.MUST_IMPLEMENT_INTERFACE_opcode;
108 import static org.jikesrvm.compilers.opt.ir.Operators.NEWARRAY_UNRESOLVED_opcode;
109 import static org.jikesrvm.compilers.opt.ir.Operators.NEWARRAY_opcode;
110 import static org.jikesrvm.compilers.opt.ir.Operators.NEWOBJMULTIARRAY_opcode;
111 import static org.jikesrvm.compilers.opt.ir.Operators.NEW_UNRESOLVED_opcode;
112 import static org.jikesrvm.compilers.opt.ir.Operators.NEW_opcode;
113 import static org.jikesrvm.compilers.opt.ir.Operators.NULL_CHECK_opcode;
114 import static org.jikesrvm.compilers.opt.ir.Operators.OBJARRAY_STORE_CHECK_NOTNULL_opcode;
115 import static org.jikesrvm.compilers.opt.ir.Operators.OBJARRAY_STORE_CHECK_opcode;
116 import static org.jikesrvm.compilers.opt.ir.Operators.PHI_opcode;
117 import static org.jikesrvm.compilers.opt.ir.Operators.PREPARE_ADDR_opcode;
118 import static org.jikesrvm.compilers.opt.ir.Operators.PREPARE_INT_opcode;
119 import static org.jikesrvm.compilers.opt.ir.Operators.PREPARE_LONG_opcode;
120 import static org.jikesrvm.compilers.opt.ir.Operators.PUTFIELD_opcode;
121 import static org.jikesrvm.compilers.opt.ir.Operators.PUTSTATIC_opcode;
122 import static org.jikesrvm.compilers.opt.ir.Operators.REF_ADD_opcode;
123 import static org.jikesrvm.compilers.opt.ir.Operators.REF_ALOAD_opcode;
124 import static org.jikesrvm.compilers.opt.ir.Operators.REF_AND_opcode;
125 import static org.jikesrvm.compilers.opt.ir.Operators.REF_ASTORE_opcode;
126 import static org.jikesrvm.compilers.opt.ir.Operators.REF_COND_MOVE_opcode;
127 import static org.jikesrvm.compilers.opt.ir.Operators.REF_IFCMP_opcode;
128 import static org.jikesrvm.compilers.opt.ir.Operators.REF_LOAD_opcode;
129 import static org.jikesrvm.compilers.opt.ir.Operators.REF_MOVE_opcode;
130 import static org.jikesrvm.compilers.opt.ir.Operators.REF_OR_opcode;
131 import static org.jikesrvm.compilers.opt.ir.Operators.REF_SHL_opcode;
132 import static org.jikesrvm.compilers.opt.ir.Operators.REF_SHR_opcode;
133 import static org.jikesrvm.compilers.opt.ir.Operators.REF_STORE_opcode;
134 import static org.jikesrvm.compilers.opt.ir.Operators.REF_SUB_opcode;
135 import static org.jikesrvm.compilers.opt.ir.Operators.REF_USHR_opcode;
136 import static org.jikesrvm.compilers.opt.ir.Operators.REF_XOR_opcode;
137 import static org.jikesrvm.compilers.opt.ir.Operators.RETURN_opcode;
138 import static org.jikesrvm.compilers.opt.ir.Operators.SET_CAUGHT_EXCEPTION_opcode;
139 import static org.jikesrvm.compilers.opt.ir.Operators.SHORT_ALOAD_opcode;
140 import static org.jikesrvm.compilers.opt.ir.Operators.SHORT_ASTORE_opcode;
141 import static org.jikesrvm.compilers.opt.ir.Operators.SHORT_LOAD_opcode;
142 import static org.jikesrvm.compilers.opt.ir.Operators.SHORT_STORE_opcode;
143 import static org.jikesrvm.compilers.opt.ir.Operators.SYSCALL_opcode;
144 import static org.jikesrvm.compilers.opt.ir.Operators.UBYTE_ALOAD_opcode;
145 import static org.jikesrvm.compilers.opt.ir.Operators.UBYTE_LOAD_opcode;
146 import static org.jikesrvm.compilers.opt.ir.Operators.USHORT_ALOAD_opcode;
147 import static org.jikesrvm.compilers.opt.ir.Operators.USHORT_LOAD_opcode;
148 import static org.jikesrvm.compilers.opt.ir.Operators.YIELDPOINT_OSR_opcode;
149 import org.jikesrvm.compilers.opt.ir.Register;
150 import org.jikesrvm.compilers.opt.ir.PutField;
151 import org.jikesrvm.compilers.opt.ir.PutStatic;
152 import org.jikesrvm.compilers.opt.ir.ResultCarrier;
153 import org.jikesrvm.compilers.opt.ir.Return;
154 import org.jikesrvm.compilers.opt.ir.Store;
155 import org.jikesrvm.compilers.opt.ir.operand.MethodOperand;
156 import org.jikesrvm.compilers.opt.ir.operand.Operand;
157 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
158
159 /**
160 * Simple flow-insensitive escape analysis
161 *
162 * <p> TODO: This would be more effective if formulated as a data-flow
163 * problem, and solved with iteration
164 */
165 class SimpleEscape extends CompilerPhase {
166 /**
167 * Return this instance of this phase. This phase contains no
168 * per-compilation instance fields.
169 * @param ir not used
170 * @return this
171 */
172 @Override
173 public CompilerPhase newExecution(IR ir) {
174 return this;
175 }
176
177 @Override
178 public final boolean shouldPerform(OptOptions options) {
179 return options.ESCAPE_SIMPLE_IPA;
180 }
181
182 @Override
183 public final String getName() {
184 return "Simple Escape Analysis";
185 }
186
187 @Override
188 public final boolean printingEnabled(OptOptions options, boolean before) {
189 return false;
190 }
191
192 @Override
193 public void perform(IR ir) {
194 SimpleEscape analyzer = new SimpleEscape();
195 analyzer.simpleEscapeAnalysis(ir);
196 }
197
198 /**
199 * Perform the escape analysis for a method. Returns an
200 * object holding the result of the analysis
201 *
202 * <p> Side effect: updates method summary database to hold
203 * escape analysis result for parameters
204 *
205 * @param ir IR for the target method
206 */
207 public FI_EscapeSummary simpleEscapeAnalysis(IR ir) {
208 final boolean DEBUG = false;
209 if (DEBUG) {
210 VM.sysWrite("ENTER Simple Escape Analysis " + ir.method + "\n");
211 }
212 if (DEBUG) {
213 ir.printInstructions();
214 }
215 // create a method summary object for this method
216 RVMMethod m = ir.method;
217 MethodSummary summ = SummaryDatabase.findOrCreateMethodSummary(m);
218 summ.setInProgress(true);
219 FI_EscapeSummary result = new FI_EscapeSummary();
220 // set up register lists, SSA flags
221 DefUse.computeDU(ir);
222 DefUse.recomputeSSA(ir);
223 // pass through registers, and mark escape information
224 for (Register reg = ir.regpool.getFirstSymbolicRegister(); reg != null; reg = reg.getNext()) {
225 // skip the following types of registers:
226 if (reg.isFloatingPoint()) {
227 continue;
228 }
229 if (reg.isInteger()) {
230 continue;
231 }
232 if (reg.isLong()) {
233 continue;
234 }
235 if (reg.isCondition()) {
236 continue;
237 }
238 if (reg.isValidation()) {
239 continue;
240 }
241 if (reg.isPhysical()) {
242 continue;
243 }
244 if (!reg.isSSA()) {
245 continue;
246 }
247 AnalysisResult escapes = checkAllAppearances(reg, ir);
248 if (escapes.threadLocal) {
249 result.setThreadLocal(reg, true);
250 }
251 if (escapes.methodLocal) {
252 result.setMethodLocal(reg, true);
253 }
254 }
255 // update the method summary database to note whether
256 // parameters may escape
257 int numParam = 0;
258 for (Enumeration<Operand> e = ir.getParameters(); e.hasMoreElements(); numParam++) {
259 Register p = ((RegisterOperand) e.nextElement()).getRegister();
260 if (result.isThreadLocal(p)) {
261 summ.setParameterMayEscapeThread(numParam, false);
262 } else {
263 summ.setParameterMayEscapeThread(numParam, true);
264 }
265 }
266
267 // update the method summary to note whether the return value
268 // may escape
269 boolean foundEscapingReturn = false;
270 for (Iterator<Operand> itr = iterateReturnValues(ir); itr.hasNext();) {
271 Operand op = itr.next();
272 if (op == null) {
273 continue;
274 }
275 if (op.isRegister()) {
276 Register r = op.asRegister().getRegister();
277 if (!result.isThreadLocal(r)) {
278 foundEscapingReturn = true;
279 }
280 }
281 }
282 if (!foundEscapingReturn) {
283 summ.setResultMayEscapeThread(false);
284 }
285 // record that we're done with analysis
286 summ.setInProgress(false);
287 if (DEBUG) {
288 VM.sysWrite("LEAVE Simple Escape Analysis " + ir.method + "\n");
289 }
290 return result;
291 }
292
293 /**
294 * This member represents the directions to the optimizing compiler to
295 * perform escape analysis on a method, but do <em> not </em> generate
296 * code.
297 */
298 private static final OptimizationPlanElement escapePlan = initEscapePlan();
299
300 /**
301 * Check all appearances of a register, to see if any object pointed
302 * to by this register may escape this thread and/or method.
303 *
304 * @param reg the register to check
305 * @param ir the governing IR
306 * @return true if it may escape this thread, false otherwise
307 */
308 private static AnalysisResult checkAllAppearances(Register reg, IR ir) {
309 return new AnalysisResult(!checkIfUseEscapesThread(reg, ir, null),
310 !checkIfUseEscapesMethod(reg, ir, null));
311 }
312 private static boolean checkIfUseEscapesThread(Register reg, IR ir, Set<Register> visited) {
313 for (RegisterOperand use = reg.useList; use != null; use = use.getNext()) {
314
315 if (VM.VerifyAssertions && use.getType() == null) {
316 ir.printInstructions();
317 VM._assert(VM.NOT_REACHED, "type of " + use + " is null");
318 }
319
320 // if the type is primitive, just say it escapes
321 // TODO: handle this more cleanly
322 if (use.getType().isPrimitiveType()) {
323 return true;
324 }
325 if (checkEscapesThread(use, ir, visited)) {
326 return true;
327 }
328 }
329 for (RegisterOperand def = reg.defList; def != null; def = def.getNext()) {
330
331 if (VM.VerifyAssertions && def.getType() == null) {
332 ir.printInstructions();
333 VM._assert(VM.NOT_REACHED, "type of " + def + " is null");
334 }
335
336 // if the type is primitive, just say it escapes
337 // TODO: handle this more cleanly
338 if (def.getType() == null || def.getType().isPrimitiveType()) {
339 return true;
340 }
341 if (checkEscapesThread(def, ir, visited)) {
342 return true;
343 }
344 }
345 return false;
346 }
347 private static boolean checkIfUseEscapesMethod(Register reg, IR ir, Set<Register> visited) {
348 for (RegisterOperand use = reg.useList; use != null; use = use.getNext()) {
349 if (VM.VerifyAssertions && use.getType() == null) {
350 ir.printInstructions();
351 VM._assert(VM.NOT_REACHED, "type of " + use + " is null");
352 }
353
354 // if the type is primitive, just say it escapes
355 // TODO: handle this more cleanly
356 if (use.getType().isPrimitiveType()) {
357 return false;
358 }
359 if (checkEscapesMethod(use, ir, visited)) {
360 return true;
361 }
362 }
363 for (RegisterOperand def = reg.defList; def != null; def = def.getNext()) {
364 if (VM.VerifyAssertions && def.getType() == null) {
365 ir.printInstructions();
366 VM._assert(VM.NOT_REACHED, "type of " + def + " is null");
367 }
368
369 // if the type is primitive, just say it escapes
370 // TODO: handle this more cleanly
371 if (def.getType() == null || def.getType().isPrimitiveType()) {
372 return true;
373 }
374 if (checkEscapesMethod(def, ir, visited)) {
375 return true;
376 }
377 }
378 return false;
379 }
380
381 /**
382 * Check a single use, to see if this use may cause the object
383 * referenced to escape from this thread.
384 *
385 * @param use the use to check
386 * @param ir the governing IR
387 * @return {@code true} if it may escape, {@code false} otherwise
388 */
389 private static boolean checkEscapesThread(RegisterOperand use, IR ir, Set<Register> visited) {
390 Instruction inst = use.instruction;
391 switch (inst.getOpcode()) {
392 case INT_ASTORE_opcode:
393 case LONG_ASTORE_opcode:
394 case FLOAT_ASTORE_opcode:
395 case DOUBLE_ASTORE_opcode:
396 case BYTE_ASTORE_opcode:
397 case SHORT_ASTORE_opcode:
398 case REF_ASTORE_opcode:
399 // as long as we don't store this operand elsewhere, all
400 // is OK
401 Operand value = AStore.getValue(inst);
402 return value == use;
403 case GETFIELD_opcode:
404 case GETSTATIC_opcode:
405 case INT_ALOAD_opcode:
406 case LONG_ALOAD_opcode:
407 case FLOAT_ALOAD_opcode:
408 case DOUBLE_ALOAD_opcode:
409 case BYTE_ALOAD_opcode:
410 case UBYTE_ALOAD_opcode:
411 case BYTE_LOAD_opcode:
412 case UBYTE_LOAD_opcode:
413 case SHORT_ALOAD_opcode:
414 case USHORT_ALOAD_opcode:
415 case SHORT_LOAD_opcode:
416 case USHORT_LOAD_opcode:
417 case REF_ALOAD_opcode:
418 case INT_LOAD_opcode:
419 case LONG_LOAD_opcode:
420 case FLOAT_LOAD_opcode:
421 case DOUBLE_LOAD_opcode:
422 case REF_LOAD_opcode:
423 // all is OK, unless we load this register from memory
424 Operand result = ResultCarrier.getResult(inst);
425 return result == use;
426 case PUTFIELD_opcode:
427 // as long as we don't store this operand elsewhere, all
428 // is OK. TODO: add more smarts.
429 value = PutField.getValue(inst);
430 return value == use;
431 case PUTSTATIC_opcode:
432 // as long as we don't store this operand elsewhere, all
433 // is OK. TODO: add more smarts.
434 value = PutStatic.getValue(inst);
435 return value == use;
436 case BYTE_STORE_opcode:
437 case SHORT_STORE_opcode:
438 case REF_STORE_opcode:
439 case INT_STORE_opcode:
440 case LONG_STORE_opcode:
441 case FLOAT_STORE_opcode:
442 case DOUBLE_STORE_opcode:
443 // as long as we don't store this operand elsewhere, all
444 // is OK. TODO: add more smarts.
445 value = Store.getValue(inst);
446 return value == use;
447 // the following instructions never cause an object to
448 // escape
449 case BOUNDS_CHECK_opcode:
450 case MONITORENTER_opcode:
451 case MONITOREXIT_opcode:
452 case NULL_CHECK_opcode:
453 case ARRAYLENGTH_opcode:
454 case REF_IFCMP_opcode:
455 case INT_IFCMP_opcode:
456 case IG_PATCH_POINT_opcode:
457 case IG_CLASS_TEST_opcode:
458 case IG_METHOD_TEST_opcode:
459 case BOOLEAN_CMP_INT_opcode:
460 case BOOLEAN_CMP_ADDR_opcode:
461 case OBJARRAY_STORE_CHECK_opcode:
462 case OBJARRAY_STORE_CHECK_NOTNULL_opcode:
463 case GET_OBJ_TIB_opcode:
464 case GET_TYPE_FROM_TIB_opcode:
465 case NEW_opcode:
466 case NEWARRAY_opcode:
467 case NEWOBJMULTIARRAY_opcode:
468 case NEW_UNRESOLVED_opcode:
469 case NEWARRAY_UNRESOLVED_opcode:
470 case INSTANCEOF_opcode:
471 case INSTANCEOF_NOTNULL_opcode:
472 case INSTANCEOF_UNRESOLVED_opcode:
473 case CHECKCAST_opcode:
474 case MUST_IMPLEMENT_INTERFACE_opcode:
475 case CHECKCAST_NOTNULL_opcode:
476 case CHECKCAST_UNRESOLVED_opcode:
477 case GET_CAUGHT_EXCEPTION_opcode:
478 case IR_PROLOGUE_opcode:
479 return false;
480 case RETURN_opcode:
481 // a return instruction might cause an object to escape,
482 // but not a parameter (whose escape properties are determined
483 // by caller)
484 return !ir.isParameter(use);
485 case CALL_opcode:
486 MethodOperand mop = Call.getMethod(inst);
487 if (mop == null) {
488 return true;
489 }
490 if (!mop.hasPreciseTarget()) {
491 // if we're not sure of the dynamic target, give up
492 return true;
493 }
494 // pure methods don't let object escape
495 if (mop.getTarget().isPure()) {
496 return false;
497 }
498 // Assume non-annotated native methods let object escape
499 if (mop.getTarget().isNative()) {
500 return false;
501 }
502 // try to get a method summary for the called method
503 MethodSummary summ = findOrCreateMethodSummary(mop.getTarget(), ir.options);
504 if (summ == null) {
505 // couldn't get one. assume the object escapes
506 return true;
507 }
508 // if use is result of the call...
509 if (use == Call.getResult(inst)) {
510 return summ.resultMayEscapeThread();
511 }
512 // use is a parameter to the call. Find out which one.
513 int p = getParameterIndex(use, inst);
514 return summ.parameterMayEscapeThread(p);
515 case REF_MOVE_opcode: {
516 Register copy = Move.getResult(inst).getRegister();
517 if (!copy.isSSA()) {
518 return true;
519 } else {
520 if (visited == null) {
521 visited = new HashSet<Register>();
522 }
523 visited.add(use.getRegister());
524 if (visited.contains(copy)) {
525 return false;
526 } else {
527 return checkIfUseEscapesThread(copy, ir, visited);
528 }
529 }
530 }
531 case ATHROW_opcode:
532 case PREPARE_INT_opcode:
533 case PREPARE_ADDR_opcode:
534 case PREPARE_LONG_opcode:
535 case ATTEMPT_LONG_opcode:
536 case ATTEMPT_INT_opcode:
537 case ATTEMPT_ADDR_opcode:
538 case INT_MOVE_opcode:
539 case INT_ADD_opcode:
540 case REF_ADD_opcode:
541 case INT_MUL_opcode:
542 case INT_DIV_opcode:
543 case INT_REM_opcode:
544 case INT_NEG_opcode:
545 case INT_ZERO_CHECK_opcode:
546 case INT_OR_opcode:
547 case INT_AND_opcode:
548 case INT_XOR_opcode:
549 case REF_OR_opcode:
550 case REF_AND_opcode:
551 case REF_XOR_opcode:
552 case INT_SUB_opcode:
553 case REF_SUB_opcode:
554 case INT_SHL_opcode:
555 case INT_SHR_opcode:
556 case INT_USHR_opcode:
557 case SYSCALL_opcode:
558 case REF_SHL_opcode:
559 case REF_SHR_opcode:
560 case REF_USHR_opcode:
561 case SET_CAUGHT_EXCEPTION_opcode:
562 case PHI_opcode:
563 case INT_2LONG_opcode:
564 case REF_COND_MOVE_opcode:
565 case INT_COND_MOVE_opcode:
566 case INT_2ADDRSigExt_opcode:
567 case INT_2ADDRZerExt_opcode:
568 case ADDR_2INT_opcode:
569 case ADDR_2LONG_opcode:
570 // we don't currently analyze these instructions,
571 // so conservatively assume everything escapes
572 // TODO: add more smarts
573 case YIELDPOINT_OSR_opcode:
574 // on stack replacement really a part of the current method, but
575 // we do not know exactly, so be conservative
576 return true;
577 default:
578 return Operators.helper.mayEscapeThread(inst);
579 }
580 }
581
582 /**
583 * Check a single use, to see if this use may cause the object
584 * referenced to escape from this method.
585 *
586 * @param use the use to check
587 * @param ir the governing IR
588 * @return true if it may escape, false otherwise
589 */
590 private static boolean checkEscapesMethod(RegisterOperand use, IR ir, Set<Register> visited) {
591 Instruction inst = use.instruction;
592 try {
593 switch (inst.getOpcode()) {
594 case INT_ASTORE_opcode:
595 case LONG_ASTORE_opcode:
596 case FLOAT_ASTORE_opcode:
597 case DOUBLE_ASTORE_opcode:
598 case BYTE_ASTORE_opcode:
599 case SHORT_ASTORE_opcode:
600 case REF_ASTORE_opcode:
601 // as long as we don't store this operand elsewhere, all
602 // is OK
603 Operand value = AStore.getValue(inst);
604 return value == use;
605 case GETFIELD_opcode:
606 case GETSTATIC_opcode:
607 case INT_ALOAD_opcode:
608 case LONG_ALOAD_opcode:
609 case FLOAT_ALOAD_opcode:
610 case DOUBLE_ALOAD_opcode:
611 case BYTE_ALOAD_opcode:
612 case UBYTE_ALOAD_opcode:
613 case BYTE_LOAD_opcode:
614 case UBYTE_LOAD_opcode:
615 case USHORT_ALOAD_opcode:
616 case SHORT_ALOAD_opcode:
617 case USHORT_LOAD_opcode:
618 case SHORT_LOAD_opcode:
619 case REF_ALOAD_opcode:
620 case INT_LOAD_opcode:
621 case LONG_LOAD_opcode:
622 case FLOAT_LOAD_opcode:
623 case DOUBLE_LOAD_opcode:
624 case REF_LOAD_opcode:
625 // all is OK, unless we load this register from memory
626 Operand result = ResultCarrier.getResult(inst);
627 return result == use;
628 case PUTFIELD_opcode:
629 // as long as we don't store this operand elsewhere, all
630 // is OK. TODO: add more smarts.
631 value = PutField.getValue(inst);
632 return value == use;
633 case PUTSTATIC_opcode:
634 // as long as we don't store this operand elsewhere, all
635 // is OK. TODO: add more smarts.
636 value = PutStatic.getValue(inst);
637 return value == use;
638 case BYTE_STORE_opcode:
639 case SHORT_STORE_opcode:
640 case REF_STORE_opcode:
641 case INT_STORE_opcode:
642 case LONG_STORE_opcode:
643 case FLOAT_STORE_opcode:
644 case DOUBLE_STORE_opcode:
645 // as long as we don't store this operand elsewhere, all
646 // is OK. TODO: add more smarts.
647 value = Store.getValue(inst);
648 return value == use;
649 // the following instructions never cause an object to
650 // escape
651 case BOUNDS_CHECK_opcode:
652 case MONITORENTER_opcode:
653 case MONITOREXIT_opcode:
654 case NULL_CHECK_opcode:
655 case ARRAYLENGTH_opcode:
656 case REF_IFCMP_opcode:
657 case INT_IFCMP_opcode:
658 case IG_PATCH_POINT_opcode:
659 case IG_CLASS_TEST_opcode:
660 case IG_METHOD_TEST_opcode:
661 case BOOLEAN_CMP_INT_opcode:
662 case BOOLEAN_CMP_ADDR_opcode:
663 case OBJARRAY_STORE_CHECK_opcode:
664 case OBJARRAY_STORE_CHECK_NOTNULL_opcode:
665 case GET_OBJ_TIB_opcode:
666 case GET_TYPE_FROM_TIB_opcode:
667 case NEW_opcode:
668 case NEWARRAY_opcode:
669 case NEWOBJMULTIARRAY_opcode:
670 case NEW_UNRESOLVED_opcode:
671 case NEWARRAY_UNRESOLVED_opcode:
672 case INSTANCEOF_opcode:
673 case INSTANCEOF_NOTNULL_opcode:
674 case INSTANCEOF_UNRESOLVED_opcode:
675 case CHECKCAST_opcode:
676 case MUST_IMPLEMENT_INTERFACE_opcode:
677 case CHECKCAST_NOTNULL_opcode:
678 case CHECKCAST_UNRESOLVED_opcode:
679 case GET_CAUGHT_EXCEPTION_opcode:
680 case IR_PROLOGUE_opcode:
681 return false;
682 case RETURN_opcode:
683 // a return instruction causes an object to escape this method.
684 return true;
685 case CALL_opcode: {
686 // A call instruction causes an object to escape this method
687 // except when the target is to Throwable.<init> (which we never inline)
688 MethodOperand mop = Call.getMethod(inst);
689 if (mop != null && mop.hasPreciseTarget()) {
690 RVMMethod target = mop.getTarget();
691 if (target.hasNoEscapesAnnotation()) {
692 return false;
693 }
694 }
695 return true;
696 }
697 case REF_MOVE_opcode: {
698 if (visited == null) {
699 visited = new HashSet<Register>();
700 }
701 Register copy = Move.getResult(inst).getRegister();
702 if(!copy.isSSA()) {
703 return true;
704 } else {
705 visited.add(use.getRegister());
706 if (visited.contains(copy)) {
707 return false;
708 } else {
709 boolean result2 = checkIfUseEscapesMethod(copy, ir, visited);
710 return result2;
711 }
712 }
713 }
714 case ATHROW_opcode:
715 case PREPARE_INT_opcode:
716 case PREPARE_ADDR_opcode:
717 case ATTEMPT_INT_opcode:
718 case ATTEMPT_ADDR_opcode:
719 case PREPARE_LONG_opcode:
720 case ATTEMPT_LONG_opcode:
721 case INT_MOVE_opcode:
722 case INT_ADD_opcode:
723 case REF_ADD_opcode:
724 case INT_MUL_opcode:
725 case INT_DIV_opcode:
726 case INT_REM_opcode:
727 case INT_NEG_opcode:
728 case INT_ZERO_CHECK_opcode:
729 case INT_OR_opcode:
730 case INT_AND_opcode:
731 case INT_XOR_opcode:
732 case REF_OR_opcode:
733 case REF_AND_opcode:
734 case REF_XOR_opcode:
735 case INT_SUB_opcode:
736 case REF_SUB_opcode:
737 case INT_SHL_opcode:
738 case INT_SHR_opcode:
739 case INT_USHR_opcode:
740 case SYSCALL_opcode:
741 case REF_SHL_opcode:
742 case REF_SHR_opcode:
743 case REF_USHR_opcode:
744 case SET_CAUGHT_EXCEPTION_opcode:
745 case PHI_opcode:
746 case INT_2LONG_opcode:
747 case REF_COND_MOVE_opcode:
748 case INT_COND_MOVE_opcode:
749 case INT_2ADDRSigExt_opcode:
750 case INT_2ADDRZerExt_opcode:
751 case ADDR_2INT_opcode:
752 case ADDR_2LONG_opcode:
753 case YIELDPOINT_OSR_opcode:
754 // we don't currently analyze these instructions,
755 // so conservatively assume everything escapes
756 // TODO: add more smarts
757 return true;
758 default:
759 return Operators.helper.mayEscapeMethod(inst);
760 }
761 } catch (Exception e) {
762 OptimizingCompilerException oe = new OptimizingCompilerException("Error handling use ("+ use +") of: "+ inst);
763 oe.initCause(e);
764 throw oe;
765 }
766 }
767
768 /**
769 * Which parameter to a call instruction corresponds to op?
770 * <p> PRECONDITION: Call.conforms(s)
771 */
772 private static int getParameterIndex(Operand op, Instruction s) {
773 for (int i = 0; i < Call.getNumberOfParams(s); i++) {
774 Operand p = Call.getParam(s, i);
775 if (p == op) {
776 return i;
777 }
778 }
779 throw new OptimizingCompilerException("Parameter not found" + op + s);
780 }
781
782 /**
783 * If a method summary exists for a method, get it.
784 * Else, iff SIMPLE_ESCAPE_IPA,
785 * perform escape analysis, which will create the method
786 * summary as a side effect, and return the summary
787 */
788 private static MethodSummary findOrCreateMethodSummary(RVMMethod m, OptOptions options) {
789 MethodSummary summ = SummaryDatabase.findMethodSummary(m);
790 if (summ == null) {
791 if (options.ESCAPE_SIMPLE_IPA) {
792 performSimpleEscapeAnalysis(m, options);
793 summ = SummaryDatabase.findMethodSummary(m);
794 }
795 return summ;
796 } else {
797 return summ;
798 }
799 }
800
801 /**
802 * Perform the simple escape analysis for a method.
803 */
804 private static void performSimpleEscapeAnalysis(RVMMethod m, OptOptions options) {
805 if (!options.ESCAPE_SIMPLE_IPA) {
806 return;
807 }
808 // do not perform for unloaded methods
809 MethodSummary summ = SummaryDatabase.findMethodSummary(m);
810 if (summ != null) {
811 // do not attempt to perform escape analysis recursively
812 if (summ.inProgress()) {
813 return;
814 }
815 }
816 CompilationPlan plan = new CompilationPlan((NormalMethod) m, escapePlan, null, options);
817 plan.analyzeOnly = true;
818 try {
819 OptimizingCompiler.compile(plan);
820 } catch (MagicNotImplementedException e) {
821 summ.setInProgress(false); // summary stays at bottom
822 }
823 }
824
825 /**
826 * Static initializer: set up the compilation plan for
827 * simple escape analysis of a method.
828 */
829 private static OptimizationPlanElement initEscapePlan() {
830 return OptimizationPlanCompositeElement.compose("Escape Analysis",
831 new Object[]{new ConvertBCtoHIR(),
832 new Simple(1, true, true, false, false),
833 new SimpleEscape()});
834 }
835
836 /**
837 * Return an iterator over the operands that serve as return values
838 * in an IR
839 *
840 * <p> TODO: Move this utility elsewhere
841 */
842 private static Iterator<Operand> iterateReturnValues(IR ir) {
843 ArrayList<Operand> returnValues = new ArrayList<Operand>();
844 for (Enumeration<Instruction> e = ir.forwardInstrEnumerator(); e.hasMoreElements();) {
845 Instruction s = e.nextElement();
846 if (Return.conforms(s)) {
847 returnValues.add(Return.getVal(s));
848 }
849 }
850 return returnValues.iterator();
851 }
852
853 /**
854 * Utility class used to hold the result of the escape analysis.
855 */
856 private static final class AnalysisResult {
857 /**
858 * Was the result "the register must point to thread-local objects"?
859 */
860 final boolean threadLocal;
861 /**
862 * Was the result "the register must point to method-local objects"?
863 */
864 final boolean methodLocal;
865 /**
866 * Constructor
867 */
868 AnalysisResult(boolean tl, boolean ml) {
869 threadLocal = tl;
870 methodLocal = ml;
871 }
872 }
873 }