LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

InlineFunction.cpp

Go to the documentation of this file.
00001 //===- InlineFunction.cpp - Code to perform function inlining -------------===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements inlining of a function into a call site, resolving
00011 // parameters and the return value as appropriate.
00012 //
00013 // FIXME: This pass should transform alloca instructions in the called function
00014 // into alloca/dealloca pairs!  Or perhaps it should refuse to inline them!
00015 //
00016 //===----------------------------------------------------------------------===//
00017 
00018 #include "llvm/Transforms/Utils/Cloning.h"
00019 #include "llvm/Constants.h"
00020 #include "llvm/DerivedTypes.h"
00021 #include "llvm/Module.h"
00022 #include "llvm/Instructions.h"
00023 #include "llvm/Intrinsics.h"
00024 #include "llvm/Support/CallSite.h"
00025 using namespace llvm;
00026 
00027 bool llvm::InlineFunction(CallInst *CI) { return InlineFunction(CallSite(CI)); }
00028 bool llvm::InlineFunction(InvokeInst *II) {return InlineFunction(CallSite(II));}
00029 
00030 // InlineFunction - This function inlines the called function into the basic
00031 // block of the caller.  This returns false if it is not possible to inline this
00032 // call.  The program is still in a well defined state if this occurs though.
00033 //
00034 // Note that this only does one level of inlining.  For example, if the 
00035 // instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now 
00036 // exists in the instruction stream.  Similiarly this will inline a recursive
00037 // function by one level.
00038 //
00039 bool llvm::InlineFunction(CallSite CS) {
00040   Instruction *TheCall = CS.getInstruction();
00041   assert(TheCall->getParent() && TheCall->getParent()->getParent() &&
00042          "Instruction not in function!");
00043 
00044   const Function *CalledFunc = CS.getCalledFunction();
00045   if (CalledFunc == 0 ||          // Can't inline external function or indirect
00046       CalledFunc->isExternal() || // call, or call to a vararg function!
00047       CalledFunc->getFunctionType()->isVarArg()) return false;
00048 
00049   BasicBlock *OrigBB = TheCall->getParent();
00050   Function *Caller = OrigBB->getParent();
00051 
00052   // Get an iterator to the last basic block in the function, which will have
00053   // the new function inlined after it.
00054   //
00055   Function::iterator LastBlock = &Caller->back();
00056 
00057   // Make sure to capture all of the return instructions from the cloned
00058   // function.
00059   std::vector<ReturnInst*> Returns;
00060   { // Scope to destroy ValueMap after cloning.
00061     // Calculate the vector of arguments to pass into the function cloner...
00062     std::map<const Value*, Value*> ValueMap;
00063     assert(std::distance(CalledFunc->abegin(), CalledFunc->aend()) == 
00064            std::distance(CS.arg_begin(), CS.arg_end()) &&
00065            "No varargs calls can be inlined!");
00066     
00067     CallSite::arg_iterator AI = CS.arg_begin();
00068     for (Function::const_aiterator I = CalledFunc->abegin(),
00069            E = CalledFunc->aend(); I != E; ++I, ++AI)
00070       ValueMap[I] = *AI;
00071     
00072     // Clone the entire body of the callee into the caller.  
00073     CloneFunctionInto(Caller, CalledFunc, ValueMap, Returns, ".i");
00074   }    
00075 
00076   // Remember the first block that is newly cloned over.
00077   Function::iterator FirstNewBlock = LastBlock; ++FirstNewBlock;
00078 
00079   // If there are any alloca instructions in the block that used to be the entry
00080   // block for the callee, move them to the entry block of the caller.  First
00081   // calculate which instruction they should be inserted before.  We insert the
00082   // instructions at the end of the current alloca list.
00083   //
00084   if (isa<AllocaInst>(FirstNewBlock->begin())) {
00085     BasicBlock::iterator InsertPoint = Caller->begin()->begin();
00086     for (BasicBlock::iterator I = FirstNewBlock->begin(),
00087            E = FirstNewBlock->end(); I != E; )
00088       if (AllocaInst *AI = dyn_cast<AllocaInst>(I++))
00089         if (isa<Constant>(AI->getArraySize())) {
00090           // Scan for the block of allocas that we can move over.
00091           while (isa<AllocaInst>(I) &&
00092                  isa<Constant>(cast<AllocaInst>(I)->getArraySize()))
00093             ++I;
00094 
00095           // Transfer all of the allocas over in a block.  Using splice means
00096           // that they instructions aren't removed from the symbol table, then
00097           // reinserted.
00098           Caller->front().getInstList().splice(InsertPoint,
00099                                                FirstNewBlock->getInstList(),
00100                                                AI, I);
00101         }
00102   }
00103 
00104   // If we are inlining for an invoke instruction, we must make sure to rewrite
00105   // any inlined 'unwind' instructions into branches to the invoke exception
00106   // destination, and call instructions into invoke instructions.
00107   if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) {
00108     BasicBlock *InvokeDest = II->getUnwindDest();
00109     std::vector<Value*> InvokeDestPHIValues;
00110 
00111     // If there are PHI nodes in the exceptional destination block, we need to
00112     // keep track of which values came into them from this invoke, then remove
00113     // the entry for this block.
00114     for (BasicBlock::iterator I = InvokeDest->begin(); isa<PHINode>(I); ++I) {
00115       PHINode *PN = cast<PHINode>(I);
00116       // Save the value to use for this edge...
00117       InvokeDestPHIValues.push_back(PN->getIncomingValueForBlock(OrigBB));
00118     }
00119 
00120     for (Function::iterator BB = FirstNewBlock, E = Caller->end();
00121          BB != E; ++BB) {
00122       for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
00123         // We only need to check for function calls: inlined invoke instructions
00124         // require no special handling...
00125         if (CallInst *CI = dyn_cast<CallInst>(I)) {
00126           // Convert this function call into an invoke instruction... if it's
00127           // not an intrinsic function call (which are known to not throw).
00128           if (CI->getCalledFunction() &&
00129               CI->getCalledFunction()->getIntrinsicID()) {
00130             ++I;
00131           } else {
00132             // First, split the basic block...
00133             BasicBlock *Split = BB->splitBasicBlock(CI, CI->getName()+".noexc");
00134             
00135             // Next, create the new invoke instruction, inserting it at the end
00136             // of the old basic block.
00137             InvokeInst *II =
00138               new InvokeInst(CI->getCalledValue(), Split, InvokeDest, 
00139                             std::vector<Value*>(CI->op_begin()+1, CI->op_end()),
00140                              CI->getName(), BB->getTerminator());
00141 
00142             // Make sure that anything using the call now uses the invoke!
00143             CI->replaceAllUsesWith(II);
00144             
00145             // Delete the unconditional branch inserted by splitBasicBlock
00146             BB->getInstList().pop_back();
00147             Split->getInstList().pop_front();  // Delete the original call
00148             
00149             // Update any PHI nodes in the exceptional block to indicate that
00150             // there is now a new entry in them.
00151             unsigned i = 0;
00152             for (BasicBlock::iterator I = InvokeDest->begin();
00153                  isa<PHINode>(I); ++I, ++i) {
00154               PHINode *PN = cast<PHINode>(I);
00155               PN->addIncoming(InvokeDestPHIValues[i], BB);
00156             }
00157             
00158             // This basic block is now complete, start scanning the next one.
00159             break;
00160           }
00161         } else {
00162           ++I;
00163         }
00164       }
00165 
00166       if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) {
00167         // An UnwindInst requires special handling when it gets inlined into an
00168         // invoke site.  Once this happens, we know that the unwind would cause
00169         // a control transfer to the invoke exception destination, so we can
00170         // transform it into a direct branch to the exception destination.
00171         new BranchInst(InvokeDest, UI);
00172 
00173         // Delete the unwind instruction!
00174         UI->getParent()->getInstList().pop_back();
00175 
00176         // Update any PHI nodes in the exceptional block to indicate that
00177         // there is now a new entry in them.
00178         unsigned i = 0;
00179         for (BasicBlock::iterator I = InvokeDest->begin();
00180              isa<PHINode>(I); ++I, ++i) {
00181           PHINode *PN = cast<PHINode>(I);
00182           PN->addIncoming(InvokeDestPHIValues[i], BB);
00183         }
00184       }
00185     }
00186 
00187     // Now that everything is happy, we have one final detail.  The PHI nodes in
00188     // the exception destination block still have entries due to the original
00189     // invoke instruction.  Eliminate these entries (which might even delete the
00190     // PHI node) now.
00191     InvokeDest->removePredecessor(II->getParent());
00192   }
00193 
00194   // If we cloned in _exactly one_ basic block, and if that block ends in a
00195   // return instruction, we splice the body of the inlined callee directly into
00196   // the calling basic block.
00197   if (Returns.size() == 1 && std::distance(FirstNewBlock, Caller->end()) == 1) {
00198     // Move all of the instructions right before the call.
00199     OrigBB->getInstList().splice(TheCall, FirstNewBlock->getInstList(),
00200                                  FirstNewBlock->begin(), FirstNewBlock->end());
00201     // Remove the cloned basic block.
00202     Caller->getBasicBlockList().pop_back();
00203     
00204     // If the call site was an invoke instruction, add a branch to the normal
00205     // destination.
00206     if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall))
00207       new BranchInst(II->getNormalDest(), TheCall);
00208 
00209     // If the return instruction returned a value, replace uses of the call with
00210     // uses of the returned value.
00211     if (!TheCall->use_empty())
00212       TheCall->replaceAllUsesWith(Returns[0]->getReturnValue());
00213 
00214     // Since we are now done with the Call/Invoke, we can delete it.
00215     TheCall->getParent()->getInstList().erase(TheCall);
00216 
00217     // Since we are now done with the return instruction, delete it also.
00218     Returns[0]->getParent()->getInstList().erase(Returns[0]);
00219 
00220     // We are now done with the inlining.
00221     return true;
00222   }
00223 
00224   // Otherwise, we have the normal case, of more than one block to inline or
00225   // multiple return sites.
00226 
00227   // We want to clone the entire callee function into the hole between the
00228   // "starter" and "ender" blocks.  How we accomplish this depends on whether
00229   // this is an invoke instruction or a call instruction.
00230   BasicBlock *AfterCallBB;
00231   if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) {
00232     
00233     // Add an unconditional branch to make this look like the CallInst case...
00234     BranchInst *NewBr = new BranchInst(II->getNormalDest(), TheCall);
00235     
00236     // Split the basic block.  This guarantees that no PHI nodes will have to be
00237     // updated due to new incoming edges, and make the invoke case more
00238     // symmetric to the call case.
00239     AfterCallBB = OrigBB->splitBasicBlock(NewBr,
00240                                           CalledFunc->getName()+".entry");
00241     
00242   } else {  // It's a call
00243     // If this is a call instruction, we need to split the basic block that
00244     // the call lives in.
00245     //
00246     AfterCallBB = OrigBB->splitBasicBlock(TheCall,
00247                                           CalledFunc->getName()+".entry");
00248   }
00249 
00250   // Change the branch that used to go to AfterCallBB to branch to the first
00251   // basic block of the inlined function.
00252   //
00253   TerminatorInst *Br = OrigBB->getTerminator();
00254   assert(Br && Br->getOpcode() == Instruction::Br && 
00255          "splitBasicBlock broken!");
00256   Br->setOperand(0, FirstNewBlock);
00257 
00258 
00259   // Now that the function is correct, make it a little bit nicer.  In
00260   // particular, move the basic blocks inserted from the end of the function
00261   // into the space made by splitting the source basic block.
00262   //
00263   Caller->getBasicBlockList().splice(AfterCallBB, Caller->getBasicBlockList(),
00264                                      FirstNewBlock, Caller->end());
00265 
00266   // Handle all of the return instructions that we just cloned in, and eliminate
00267   // any users of the original call/invoke instruction.
00268   if (Returns.size() > 1) {
00269     // The PHI node should go at the front of the new basic block to merge all
00270     // possible incoming values.
00271     //
00272     PHINode *PHI = 0;
00273     if (!TheCall->use_empty()) {
00274       PHI = new PHINode(CalledFunc->getReturnType(),
00275                         TheCall->getName(), AfterCallBB->begin());
00276         
00277       // Anything that used the result of the function call should now use the
00278       // PHI node as their operand.
00279       //
00280       TheCall->replaceAllUsesWith(PHI);
00281     }
00282       
00283     // Loop over all of the return instructions, turning them into unconditional
00284     // branches to the merge point now, and adding entries to the PHI node as
00285     // appropriate.
00286     for (unsigned i = 0, e = Returns.size(); i != e; ++i) {
00287       ReturnInst *RI = Returns[i];
00288         
00289       if (PHI) {
00290         assert(RI->getReturnValue() && "Ret should have value!");
00291         assert(RI->getReturnValue()->getType() == PHI->getType() && 
00292                "Ret value not consistent in function!");
00293         PHI->addIncoming(RI->getReturnValue(), RI->getParent());
00294       }
00295         
00296       // Add a branch to the merge point where the PHI node lives if it exists.
00297       new BranchInst(AfterCallBB, RI);
00298         
00299       // Delete the return instruction now
00300       RI->getParent()->getInstList().erase(RI);
00301     }
00302       
00303   } else if (!Returns.empty()) {
00304     // Otherwise, if there is exactly one return value, just replace anything
00305     // using the return value of the call with the computed value.
00306     if (!TheCall->use_empty())
00307       TheCall->replaceAllUsesWith(Returns[0]->getReturnValue());
00308       
00309     // Splice the code from the return block into the block that it will return
00310     // to, which contains the code that was after the call.
00311     BasicBlock *ReturnBB = Returns[0]->getParent();
00312     AfterCallBB->getInstList().splice(AfterCallBB->begin(),
00313                                       ReturnBB->getInstList());
00314 
00315     // Update PHI nodes that use the ReturnBB to use the AfterCallBB.
00316     ReturnBB->replaceAllUsesWith(AfterCallBB);
00317       
00318     // Delete the return instruction now and empty ReturnBB now.
00319     Returns[0]->eraseFromParent();
00320     ReturnBB->eraseFromParent();
00321   } else if (!TheCall->use_empty()) {
00322     // No returns, but something is using the return value of the call.  Just
00323     // nuke the result.
00324     TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType()));
00325   }
00326     
00327   // Since we are now done with the Call/Invoke, we can delete it.
00328   TheCall->eraseFromParent();
00329 
00330   // We should always be able to fold the entry block of the function into the
00331   // single predecessor of the block...
00332   assert(cast<BranchInst>(Br)->isUnconditional() && "splitBasicBlock broken!");
00333   BasicBlock *CalleeEntry = cast<BranchInst>(Br)->getSuccessor(0);
00334 
00335   // Splice the code entry block into calling block, right before the
00336   // unconditional branch.
00337   OrigBB->getInstList().splice(Br, CalleeEntry->getInstList());
00338   CalleeEntry->replaceAllUsesWith(OrigBB);  // Update PHI nodes
00339 
00340   // Remove the unconditional branch.
00341   OrigBB->getInstList().erase(Br);
00342 
00343   // Now we can remove the CalleeEntry block, which is now empty.
00344   Caller->getBasicBlockList().erase(CalleeEntry);
00345   return true;
00346 }