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.inlining;
014
015 import static org.jikesrvm.compilers.opt.ir.Operators.IG_CLASS_TEST;
016 import static org.jikesrvm.compilers.opt.ir.Operators.IG_METHOD_TEST;
017 import static org.jikesrvm.compilers.opt.ir.Operators.IG_PATCH_POINT;
018 import static org.jikesrvm.compilers.opt.ir.Operators.INSTANCEOF_NOTNULL;
019 import static org.jikesrvm.compilers.opt.ir.Operators.INT_IFCMP;
020 import static org.jikesrvm.compilers.opt.ir.Operators.MUST_IMPLEMENT_INTERFACE;
021
022 import java.util.Enumeration;
023
024 import org.jikesrvm.VM;
025 import org.jikesrvm.adaptive.controller.Controller;
026 import org.jikesrvm.adaptive.database.AOSDatabase;
027 import org.jikesrvm.classloader.RVMClass;
028 import org.jikesrvm.classloader.RVMMethod;
029 import org.jikesrvm.classloader.NormalMethod;
030 import org.jikesrvm.classloader.RVMType;
031 import org.jikesrvm.classloader.TypeReference;
032 import org.jikesrvm.compilers.opt.ClassLoaderProxy;
033 import org.jikesrvm.compilers.opt.OptOptions;
034 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
035 import org.jikesrvm.compilers.opt.bc2ir.BC2IR;
036 import org.jikesrvm.compilers.opt.bc2ir.GenerationContext;
037 import org.jikesrvm.compilers.opt.driver.OptConstants;
038 import org.jikesrvm.compilers.opt.ir.BasicBlock;
039 import org.jikesrvm.compilers.opt.ir.BasicBlockEnumeration;
040 import org.jikesrvm.compilers.opt.ir.Call;
041 import org.jikesrvm.compilers.opt.ir.ExceptionHandlerBasicBlock;
042 import org.jikesrvm.compilers.opt.ir.ExceptionHandlerBasicBlockBag;
043 import org.jikesrvm.compilers.opt.ir.IR;
044 import org.jikesrvm.compilers.opt.ir.IfCmp;
045 import org.jikesrvm.compilers.opt.ir.InlineGuard;
046 import org.jikesrvm.compilers.opt.ir.InstanceOf;
047 import org.jikesrvm.compilers.opt.ir.Instruction;
048 import org.jikesrvm.compilers.opt.ir.Register;
049 import org.jikesrvm.compilers.opt.ir.TypeCheck;
050 import org.jikesrvm.compilers.opt.ir.operand.BranchProfileOperand;
051 import org.jikesrvm.compilers.opt.ir.operand.ConditionOperand;
052 import org.jikesrvm.compilers.opt.ir.operand.IntConstantOperand;
053 import org.jikesrvm.compilers.opt.ir.operand.MethodOperand;
054 import org.jikesrvm.compilers.opt.ir.operand.Operand;
055 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
056 import org.jikesrvm.compilers.opt.ir.operand.TypeOperand;
057
058 /**
059 * This class contains the high level logic for executing an inlining decision.
060 *
061 *
062 * @see InlineDecision
063 * @see GenerationContext
064 */
065 public class Inliner {
066
067 /**
068 * The following flag enables debug counters and requires an adaptive boot
069 * image and flag "INSERT_DEBUGGING_COUNTERS" to be true. See instrumentation
070 * section of the user guide for more information.
071 */
072 private static final boolean COUNT_FAILED_GUARDS = false;
073
074 /**
075 * Execute an inlining decision inlDec for the CALL instruction
076 * callSite that is contained in ir.
077 *
078 * @param inlDec the inlining decision to execute
079 * @param ir the governing IR
080 * @param callSite the call site to inline
081 */
082 public static void execute(InlineDecision inlDec, IR ir, Instruction callSite) {
083 // Find out where the call site is and isolate it in its own basic block.
084 BasicBlock bb = callSite.getBasicBlock().segregateInstruction(callSite, ir);
085 BasicBlock in = bb.prevBasicBlockInCodeOrder();
086 BasicBlock out = bb.nextBasicBlockInCodeOrder();
087 // Clear the sratch object of any register operands being
088 // passed as parameters.
089 // BC2IR uses this field for its own purposes, and will be confused
090 // if the scratch object has been used by someone else and not cleared.
091 for (int i = 0; i < Call.getNumberOfParams(callSite); i++) {
092 Operand arg = Call.getParam(callSite, i);
093 if (arg instanceof RegisterOperand) {
094 ((RegisterOperand) arg).scratchObject = null;
095 }
096 }
097 // We need to ensure that inlining the CALL instruction does not
098 // insert any new exceptional edges into the CFG that were not
099 // present before the inlining. Note that inlining the CALL may
100 // introduce new CALLS, for which we don't know the exception
101 // behavior. However, we know that any new PEIs introduced in the
102 // inlined code had better not add exceptional edges to the
103 // original CFG. So, create a new ExceptionHandlerBasicBlockBag
104 // which will enforce this behavior.
105 ExceptionHandlerBasicBlock[] catchBlocks = new ExceptionHandlerBasicBlock[bb.getNumberOfExceptionalOut()];
106 Enumeration<BasicBlock> e = bb.getExceptionalOut();
107 for (int i = 0; i < catchBlocks.length; i++) {
108 catchBlocks[i] = (ExceptionHandlerBasicBlock) e.nextElement();
109 }
110 ExceptionHandlerBasicBlockBag bag = new ExceptionHandlerBasicBlockBag(catchBlocks, null);
111
112 // Execute the inlining decision, updating ir.gc's state.
113 GenerationContext childgc = execute(inlDec, ir.gc, bag, callSite);
114 // Splice the callee into the caller's code order
115 ir.cfg.removeFromCFGAndCodeOrder(bb);
116 ir.cfg.breakCodeOrder(in, out);
117 ir.cfg.linkInCodeOrder(in, childgc.cfg.firstInCodeOrder());
118 ir.cfg.linkInCodeOrder(childgc.cfg.lastInCodeOrder(), out);
119 // Splice the callee into the caller's CFG
120 in.insertOut(childgc.prologue);
121 if (childgc.epilogue != null) {
122 childgc.epilogue.insertOut(out);
123 }
124 }
125
126 /**
127 * Return a generation context that represents the
128 * execution of inlDec in the context <parent,ebag> for
129 * the call instruction callSite.
130 * <p> PRECONDITION: inlDec.isYes()
131 * <p> POSTCONDITIONS:
132 * Let gc be the returned generation context.
133 * <ul>
134 * <li> gc.cfg.firstInCodeOrder is the entry to the inlined context
135 * <li>gc.cfg.lastInCodeOrder is the exit from the inlined context
136 * <li> GenerationContext.transferState(parent, child) has been called.
137 * </ul>
138 *
139 * @param inlDec the inlining decision to execute
140 * @param parent the caller generation context
141 * @param ebag exception handler scope for the caller
142 * @param callSite the callsite to execute
143 * @return a generation context that represents the execution of the
144 * inline decision in the given context
145 */
146 public static GenerationContext execute(InlineDecision inlDec, GenerationContext parent,
147 ExceptionHandlerBasicBlockBag ebag, Instruction callSite) {
148 if (inlDec.needsGuard()) {
149 //Step 1: create the synthetic generation context we'll
150 // return to our caller.
151 GenerationContext container = GenerationContext.createSynthetic(parent, ebag);
152 container.cfg.breakCodeOrder(container.prologue, container.epilogue);
153 // Step 2: (a) Print a message (optional)
154 // (b) Generate the child GC for each target
155 RVMMethod[] targets = inlDec.getTargets();
156 byte[] guards = inlDec.getGuards();
157 GenerationContext[] children = new GenerationContext[targets.length];
158 for (int i = 0; i < targets.length; i++) {
159 NormalMethod callee = (NormalMethod) targets[i];
160 // (a)
161 if (parent.options.PRINT_INLINE_REPORT) {
162 String guard = guards[i] == OptOptions.INLINE_GUARD_CLASS_TEST ? " (class test) " : " (method test) ";
163 VM.sysWrite("\tGuarded inline" + guard + " " + callee +
164 " into " + callSite.position.getMethod() +
165 " at bytecode " + callSite.bcIndex + "\n");
166 }
167 // (b)
168 children[i] = GenerationContext.createChildContext(parent, ebag, callee, callSite);
169 BC2IR.generateHIR(children[i]);
170 GenerationContext.transferState(parent, children[i]);
171 }
172 // Step 3: Merge together result from children into container.
173 // Note: if the child ended with only exception control flow, then
174 // child.result will be null, which we want to interpret as top.
175 // Operand.meet interprets null as bottom, so we have to do some
176 // special purpose coding wrapping the calls to Operand.meet.
177 if (Call.hasResult(callSite)) {
178 Register reg = Call.getResult(callSite).getRegister();
179 container.result = children[0].result;
180 for (int i = 1; i < targets.length; i++) {
181 if (children[i].result != null) {
182 container.result = (container.result == null) ? children[i].result : Operand.meet(container.result, children[i].result, reg);
183 }
184 }
185
186
187 if (!inlDec.OSRTestFailed()) {
188 // Account for the non-predicted case as well...
189 RegisterOperand failureCaseResult = Call.getResult(callSite).copyRO();
190 container.result = (container.result == null) ? failureCaseResult : Operand.meet(container.result, failureCaseResult, reg);
191 }
192 }
193
194 // Step 4: Create a block to contain a copy of the original call or an OSR_Yieldpoint
195 // to cover the case that all predictions fail.
196 BasicBlock testFailed = new BasicBlock(callSite.bcIndex, callSite.position, parent.cfg);
197 testFailed.exceptionHandlers = ebag;
198
199 if (COUNT_FAILED_GUARDS && Controller.options.INSERT_DEBUGGING_COUNTERS) {
200 // Get a dynamic count of how many times guards fail at runtime.
201 // Need a name for the event to count. In this example, a
202 // separate counter for each method by using the method name
203 // as the event name. You could also have used just the string
204 // "Guarded inline failed" to keep only one counter.
205 String eventName = "Guarded inline failed: " + callSite.position.getMethod().toString();
206 // Create instruction that will increment the counter
207 // corresponding to the named event.
208 Instruction counterInst = AOSDatabase.debuggingCounterData.getCounterInstructionForEvent(eventName);
209 testFailed.appendInstruction(counterInst);
210 }
211
212 if (inlDec.OSRTestFailed()) {
213 // note where we're storing the osr barrier instruction
214 Instruction lastOsrBarrier = (Instruction)callSite.scratchObject;
215 Instruction s = BC2IR._osrHelper(lastOsrBarrier);
216 s.position = callSite.position;
217 s.bcIndex = callSite.bcIndex;
218 testFailed.appendInstruction(s);
219 testFailed.insertOut(parent.exit);
220 } else {
221 Instruction call = callSite.copyWithoutLinks();
222 Call.getMethod(call).setIsGuardedInlineOffBranch(true);
223 call.bcIndex = callSite.bcIndex;
224 call.position = callSite.position;
225 testFailed.appendInstruction(call);
226 testFailed.insertOut(container.epilogue);
227 // This is ugly....since we didn't call BC2IR to generate the
228 // block with callSite we have to initialize the block's exception
229 // behavior manually.
230 // We can't call createSubBlock to do it because callSite may not
231 // be in a basic block yet (when execute is invoked from
232 // BC2IR.maybeInlineMethod).
233 if (ebag != null) {
234 for (BasicBlockEnumeration e = ebag.enumerator(); e.hasMoreElements();) {
235 BasicBlock handler = e.next();
236 testFailed.insertOut(handler);
237 }
238 }
239 testFailed.setCanThrowExceptions();
240 testFailed.setMayThrowUncaughtException();
241 }
242 container.cfg.linkInCodeOrder(testFailed, container.epilogue);
243 testFailed.setInfrequent();
244
245 // Step 5: Patch together all the callees by generating guard blocks
246 BasicBlock firstIfBlock = testFailed;
247 // Note: We know that receiver must be a register
248 // operand (and not a string constant) because we are doing a
249 // guarded inlining....if it was a string constant we'd have
250 // been able to inline without a guard.
251 Operand receiver = Call.getParam(callSite, 0);
252 MethodOperand mo = Call.getMethod(callSite);
253 boolean isInterface = mo.isInterface();
254 if (isInterface) {
255 if (VM.BuildForIMTInterfaceInvocation) {
256 RVMType interfaceType = mo.getTarget().getDeclaringClass();
257 TypeReference recTypeRef = receiver.getType();
258 RVMClass recType = (RVMClass) recTypeRef.peekType();
259 // Attempt to avoid inserting the check by seeing if the
260 // known static type of the receiver implements the interface.
261 boolean requiresImplementsTest = true;
262 if (recType != null && recType.isResolved() && !recType.isInterface()) {
263 byte doesImplement = ClassLoaderProxy.includesType(interfaceType.getTypeRef(), recTypeRef);
264 requiresImplementsTest = doesImplement != OptConstants.YES;
265 }
266 if (requiresImplementsTest) {
267 RegisterOperand checkedReceiver = parent.temps.makeTemp(receiver);
268 Instruction dtc =
269 TypeCheck.create(MUST_IMPLEMENT_INTERFACE,
270 checkedReceiver,
271 receiver.copy(),
272 new TypeOperand(interfaceType),
273 Call.getGuard(callSite).copy());
274 dtc.copyPosition(callSite);
275 checkedReceiver.refine(interfaceType.getTypeRef());
276 Call.setParam(callSite, 0, checkedReceiver.copyRO());
277 testFailed.prependInstruction(dtc);
278 }
279 }
280 }
281 // Basic idea of loop: Path together an if...else if.... else...
282 // chain from the bottom (testFailed). Some excessive cuteness
283 // to allow us to have multiple if blocks for a single
284 // "logical" test and to share test insertion for interfaces/virtuals.
285 for (int i = children.length - 1; i >= 0; i--, testFailed = firstIfBlock) {
286 firstIfBlock = new BasicBlock(callSite.bcIndex, callSite.position, parent.cfg);
287 firstIfBlock.exceptionHandlers = ebag;
288 BasicBlock lastIfBlock = firstIfBlock;
289 RVMMethod target = children[i].method;
290 Instruction tmp;
291
292 if (isInterface) {
293 RVMClass callDeclClass = mo.getTarget().getDeclaringClass();
294 if (!callDeclClass.isInterface()) {
295 // Part of ensuring that we catch IncompatibleClassChangeErrors
296 // is making sure that we know that callDeclClass is an
297 // interface before we attempt to side-step the usual invoke
298 // interface sequence.
299 // If we don't know at least this much, we can't do the inlining.
300 // We used online profile data to tell us that the target was a
301 // frequently called method from this (interface invoke)
302 // callSite, so it would be truly bizarre for us to not be able
303 // to establish that callDeclClass is an interface now.
304 // If we were using static heuristics to do guarded inlining
305 // of interface calls, then we'd probably need to do the
306 // "right" thing and detect this situation
307 // before we generated all of the childCFG's and got them
308 // entangled into the parent (due to exceptional control flow).
309 // This potential entanglement is what forces us to bail on
310 // the entire compilation.
311 throw new OptimizingCompilerException(
312 "Attempted guarded inline of invoke interface when decl class of target method may not be an interface");
313 }
314
315 // We potentially have to generate IR to perform two tests here:
316 // (1) Does the receiver object implement callDeclClass?
317 // (2) Given that it does, is target the method that would
318 // be invoked for this receiver?
319 // It is quite common to be able to answer (1) "YES" at compile
320 // time, in which case we only have to generate IR to establish
321 // (2) at runtime.
322 byte doesImplement = ClassLoaderProxy.
323 includesType(callDeclClass.getTypeRef(), target.getDeclaringClass().getTypeRef());
324 if (doesImplement != OptConstants.YES) {
325 // We can't be sure at compile time that the receiver implements
326 // the interface. So, inject a test to make sure that it does.
327 // Unlike the above case, this can actually happen (when
328 // the method is inherited but only the child actually
329 // implements the interface).
330 if (parent.options.PRINT_INLINE_REPORT) {
331 VM.sysWrite("\t\tRequired additional instanceof " + callDeclClass + " test\n");
332 }
333 firstIfBlock = new BasicBlock(callSite.bcIndex, callSite.position, parent.cfg);
334 firstIfBlock.exceptionHandlers = ebag;
335
336 RegisterOperand instanceOfResult = parent.temps.makeTempInt();
337 tmp =
338 InstanceOf.create(INSTANCEOF_NOTNULL,
339 instanceOfResult,
340 new TypeOperand(callDeclClass),
341 receiver.copy(),
342 Call.getGuard(callSite));
343 tmp.copyPosition(callSite);
344 firstIfBlock.appendInstruction(tmp);
345
346 tmp =
347 IfCmp.create(INT_IFCMP,
348 parent.temps.makeTempValidation(),
349 instanceOfResult.copyD2U(),
350 new IntConstantOperand(0),
351 ConditionOperand.EQUAL(),
352 testFailed.makeJumpTarget(),
353 BranchProfileOperand.unlikely());
354 tmp.copyPosition(callSite);
355 firstIfBlock.appendInstruction(tmp);
356
357 firstIfBlock.insertOut(testFailed);
358 firstIfBlock.insertOut(lastIfBlock);
359 container.cfg.linkInCodeOrder(firstIfBlock, lastIfBlock);
360 }
361 }
362
363 if (guards[i] == OptOptions.INLINE_GUARD_CLASS_TEST) {
364 tmp =
365 InlineGuard.create(IG_CLASS_TEST,
366 receiver.copy(),
367 Call.getGuard(callSite).copy(),
368 new TypeOperand(target.getDeclaringClass()),
369 testFailed.makeJumpTarget(),
370 BranchProfileOperand.unlikely());
371 } else if (guards[i] == OptOptions.INLINE_GUARD_METHOD_TEST) {
372 // method test for interface requires additional check if
373 // the reciever's class is a subclass of inlined method's
374 // declaring class.
375 if (isInterface) {
376 RegisterOperand t = parent.temps.makeTempInt();
377 Instruction test =
378 InstanceOf.create(INSTANCEOF_NOTNULL,
379 t,
380 new TypeOperand(target.getDeclaringClass().getTypeRef()),
381 receiver.copy());
382 test.copyPosition(callSite);
383 lastIfBlock.appendInstruction(test);
384
385 Instruction cmp =
386 IfCmp.create(INT_IFCMP,
387 parent.temps.makeTempValidation(),
388 t.copyD2U(),
389 new IntConstantOperand(0),
390 ConditionOperand.EQUAL(),
391 testFailed.makeJumpTarget(),
392 BranchProfileOperand.unlikely());
393 cmp.copyPosition(callSite);
394 lastIfBlock.appendInstruction(cmp);
395
396 BasicBlock subclassTest = new BasicBlock(callSite.bcIndex, callSite.position, parent.cfg);
397
398 lastIfBlock.insertOut(testFailed);
399 lastIfBlock.insertOut(subclassTest);
400
401 container.cfg.linkInCodeOrder(lastIfBlock, subclassTest);
402
403 lastIfBlock = subclassTest;
404 }
405
406 tmp =
407 InlineGuard.create(IG_METHOD_TEST,
408 receiver.copy(),
409 Call.getGuard(callSite).copy(),
410 MethodOperand.VIRTUAL(target.getMemberRef().asMethodReference(), target),
411 testFailed.makeJumpTarget(),
412 BranchProfileOperand.unlikely());
413 } else {
414 tmp =
415 InlineGuard.create(IG_PATCH_POINT,
416 receiver.copy(),
417 Call.getGuard(callSite).copy(),
418 MethodOperand.VIRTUAL(target.getMemberRef().asMethodReference(), target),
419 testFailed.makeJumpTarget(),
420 inlDec.OSRTestFailed() ? BranchProfileOperand.never() : BranchProfileOperand.unlikely());
421 }
422 tmp.copyPosition(callSite);
423 lastIfBlock.appendInstruction(tmp);
424
425 lastIfBlock.insertOut(testFailed);
426 lastIfBlock.insertOut(children[i].prologue);
427 container.cfg.linkInCodeOrder(lastIfBlock, children[i].cfg.firstInCodeOrder());
428 if (children[i].epilogue != null) {
429 children[i].epilogue.appendInstruction(container.epilogue.makeGOTO());
430 children[i].epilogue.insertOut(container.epilogue);
431 }
432 container.cfg.linkInCodeOrder(children[i].cfg.lastInCodeOrder(), testFailed);
433 }
434 //Step 6: finsh by linking container.prologue & testFailed
435 container.prologue.insertOut(testFailed);
436 container.cfg.linkInCodeOrder(container.prologue, testFailed);
437 return container;
438 } else {
439 if (VM.VerifyAssertions) VM._assert(inlDec.getNumberOfTargets() == 1);
440 NormalMethod callee = (NormalMethod) inlDec.getTargets()[0];
441 if (parent.options.PRINT_INLINE_REPORT) {
442 VM.sysWrite("\tInline " + callee +
443 " into " + callSite.position.getMethod() +
444 " at bytecode " + callSite.bcIndex + "\n");
445 }
446 GenerationContext child = GenerationContext.
447 createChildContext(parent, ebag, callee, callSite);
448 BC2IR.generateHIR(child);
449 GenerationContext.transferState(parent, child);
450 return child;
451 }
452 }
453 }