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