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