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