X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FInlineFunction.cpp;h=e9f0e28ad6506b900bb991909b5ceea9721d7b13;hb=f48509787acfcfc3f9eee2fb3084c2e8c7b4a009;hp=75c9ccdd7a936b5f03fb386dce923d9926ab335f;hpb=9ee17208115482441953127615231c59a2f4d052;p=oota-llvm.git diff --git a/lib/Transforms/Utils/InlineFunction.cpp b/lib/Transforms/Utils/InlineFunction.cpp index 75c9ccdd7a9..e9f0e28ad65 100644 --- a/lib/Transforms/Utils/InlineFunction.cpp +++ b/lib/Transforms/Utils/InlineFunction.cpp @@ -13,31 +13,159 @@ //===----------------------------------------------------------------------===// #include "llvm/Transforms/Utils/Cloning.h" -#include "llvm/Constants.h" -#include "llvm/DerivedTypes.h" -#include "llvm/LLVMContext.h" -#include "llvm/Module.h" -#include "llvm/Instructions.h" -#include "llvm/IntrinsicInst.h" -#include "llvm/Intrinsics.h" -#include "llvm/Attributes.h" -#include "llvm/Analysis/CallGraph.h" -#include "llvm/Analysis/DebugInfo.h" -#include "llvm/Target/TargetData.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringExtras.h" +#include "llvm/Analysis/CallGraph.h" +#include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/DebugInfo.h" +#include "llvm/IR/Attributes.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Intrinsics.h" +#include "llvm/IR/Module.h" #include "llvm/Support/CallSite.h" +#include "llvm/Transforms/Utils/Local.h" using namespace llvm; -bool llvm::InlineFunction(CallInst *CI, CallGraph *CG, const TargetData *TD, - SmallVectorImpl *StaticAllocas) { - return InlineFunction(CallSite(CI), CG, TD, StaticAllocas); +bool llvm::InlineFunction(CallInst *CI, InlineFunctionInfo &IFI, + bool InsertLifetime) { + return InlineFunction(CallSite(CI), IFI, InsertLifetime); +} +bool llvm::InlineFunction(InvokeInst *II, InlineFunctionInfo &IFI, + bool InsertLifetime) { + return InlineFunction(CallSite(II), IFI, InsertLifetime); +} + +namespace { + /// A class for recording information about inlining through an invoke. + class InvokeInliningInfo { + BasicBlock *OuterResumeDest; ///< Destination of the invoke's unwind. + BasicBlock *InnerResumeDest; ///< Destination for the callee's resume. + LandingPadInst *CallerLPad; ///< LandingPadInst associated with the invoke. + PHINode *InnerEHValuesPHI; ///< PHI for EH values from landingpad insts. + SmallVector UnwindDestPHIValues; + + public: + InvokeInliningInfo(InvokeInst *II) + : OuterResumeDest(II->getUnwindDest()), InnerResumeDest(0), + CallerLPad(0), InnerEHValuesPHI(0) { + // If there are PHI nodes in the unwind destination block, we need to keep + // track of which values came into them from the invoke before removing + // the edge from this block. + llvm::BasicBlock *InvokeBB = II->getParent(); + BasicBlock::iterator I = OuterResumeDest->begin(); + for (; isa(I); ++I) { + // Save the value to use for this edge. + PHINode *PHI = cast(I); + UnwindDestPHIValues.push_back(PHI->getIncomingValueForBlock(InvokeBB)); + } + + CallerLPad = cast(I); + } + + /// getOuterResumeDest - The outer unwind destination is the target of + /// unwind edges introduced for calls within the inlined function. + BasicBlock *getOuterResumeDest() const { + return OuterResumeDest; + } + + BasicBlock *getInnerResumeDest(); + + LandingPadInst *getLandingPadInst() const { return CallerLPad; } + + /// forwardResume - Forward the 'resume' instruction to the caller's landing + /// pad block. When the landing pad block has only one predecessor, this is + /// a simple branch. When there is more than one predecessor, we need to + /// split the landing pad block after the landingpad instruction and jump + /// to there. + void forwardResume(ResumeInst *RI, + SmallPtrSet &InlinedLPads); + + /// addIncomingPHIValuesFor - Add incoming-PHI values to the unwind + /// destination block for the given basic block, using the values for the + /// original invoke's source block. + void addIncomingPHIValuesFor(BasicBlock *BB) const { + addIncomingPHIValuesForInto(BB, OuterResumeDest); + } + + void addIncomingPHIValuesForInto(BasicBlock *src, BasicBlock *dest) const { + BasicBlock::iterator I = dest->begin(); + for (unsigned i = 0, e = UnwindDestPHIValues.size(); i != e; ++i, ++I) { + PHINode *phi = cast(I); + phi->addIncoming(UnwindDestPHIValues[i], src); + } + } + }; } -bool llvm::InlineFunction(InvokeInst *II, CallGraph *CG, const TargetData *TD, - SmallVectorImpl *StaticAllocas) { - return InlineFunction(CallSite(II), CG, TD, StaticAllocas); + +/// getInnerResumeDest - Get or create a target for the branch from ResumeInsts. +BasicBlock *InvokeInliningInfo::getInnerResumeDest() { + if (InnerResumeDest) return InnerResumeDest; + + // Split the landing pad. + BasicBlock::iterator SplitPoint = CallerLPad; ++SplitPoint; + InnerResumeDest = + OuterResumeDest->splitBasicBlock(SplitPoint, + OuterResumeDest->getName() + ".body"); + + // The number of incoming edges we expect to the inner landing pad. + const unsigned PHICapacity = 2; + + // Create corresponding new PHIs for all the PHIs in the outer landing pad. + BasicBlock::iterator InsertPoint = InnerResumeDest->begin(); + BasicBlock::iterator I = OuterResumeDest->begin(); + for (unsigned i = 0, e = UnwindDestPHIValues.size(); i != e; ++i, ++I) { + PHINode *OuterPHI = cast(I); + PHINode *InnerPHI = PHINode::Create(OuterPHI->getType(), PHICapacity, + OuterPHI->getName() + ".lpad-body", + InsertPoint); + OuterPHI->replaceAllUsesWith(InnerPHI); + InnerPHI->addIncoming(OuterPHI, OuterResumeDest); + } + + // Create a PHI for the exception values. + InnerEHValuesPHI = PHINode::Create(CallerLPad->getType(), PHICapacity, + "eh.lpad-body", InsertPoint); + CallerLPad->replaceAllUsesWith(InnerEHValuesPHI); + InnerEHValuesPHI->addIncoming(CallerLPad, OuterResumeDest); + + // All done. + return InnerResumeDest; } +/// forwardResume - Forward the 'resume' instruction to the caller's landing pad +/// block. When the landing pad block has only one predecessor, this is a simple +/// branch. When there is more than one predecessor, we need to split the +/// landing pad block after the landingpad instruction and jump to there. +void InvokeInliningInfo::forwardResume(ResumeInst *RI, + SmallPtrSet &InlinedLPads) { + BasicBlock *Dest = getInnerResumeDest(); + LandingPadInst *OuterLPad = getLandingPadInst(); + BasicBlock *Src = RI->getParent(); + + BranchInst::Create(Dest, Src); + + // Update the PHIs in the destination. They were inserted in an order which + // makes this work. + addIncomingPHIValuesForInto(Src, Dest); + + InnerEHValuesPHI->addIncoming(RI->getOperand(0), Src); + RI->eraseFromParent(); + + // Append the clauses from the outer landing pad instruction into the inlined + // landing pad instructions. + for (SmallPtrSet::iterator I = InlinedLPads.begin(), + E = InlinedLPads.end(); I != E; ++I) { + LandingPadInst *InlinedLPad = *I; + for (unsigned OuterIdx = 0, OuterNum = OuterLPad->getNumClauses(); + OuterIdx != OuterNum; ++OuterIdx) + InlinedLPad->addClause(OuterLPad->getClause(OuterIdx)); + } +} /// HandleCallsInBlockInlinedThroughInvoke - When we inline a basic block into /// an invoke, we have to turn all of the calls that can throw into @@ -45,60 +173,63 @@ bool llvm::InlineFunction(InvokeInst *II, CallGraph *CG, const TargetData *TD, /// it rewrites them to be invokes that jump to InvokeDest and fills in the PHI /// nodes in that block with the values specified in InvokeDestPHIValues. /// -static void HandleCallsInBlockInlinedThroughInvoke(BasicBlock *BB, - BasicBlock *InvokeDest, - const SmallVectorImpl &InvokeDestPHIValues) { +/// Returns true to indicate that the next block should be skipped. +static bool HandleCallsInBlockInlinedThroughInvoke(BasicBlock *BB, + InvokeInliningInfo &Invoke) { + LandingPadInst *LPI = Invoke.getLandingPadInst(); + for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) { Instruction *I = BBI++; - + + if (LandingPadInst *L = dyn_cast(I)) { + unsigned NumClauses = LPI->getNumClauses(); + L->reserveClauses(NumClauses); + for (unsigned i = 0; i != NumClauses; ++i) + L->addClause(LPI->getClause(i)); + } + // We only need to check for function calls: inlined invoke // instructions require no special handling. CallInst *CI = dyn_cast(I); - if (CI == 0) continue; - + // If this call cannot unwind, don't convert it to an invoke. - if (CI->doesNotThrow()) + if (!CI || CI->doesNotThrow()) continue; - - // Convert this function call into an invoke instruction. - // First, split the basic block. + + // Convert this function call into an invoke instruction. First, split the + // basic block. BasicBlock *Split = BB->splitBasicBlock(CI, CI->getName()+".noexc"); - - // Next, create the new invoke instruction, inserting it at the end - // of the old basic block. - SmallVector InvokeArgs(CI->op_begin()+1, CI->op_end()); - InvokeInst *II = - InvokeInst::Create(CI->getCalledValue(), Split, InvokeDest, - InvokeArgs.begin(), InvokeArgs.end(), - CI->getName(), BB->getTerminator()); + + // Delete the unconditional branch inserted by splitBasicBlock + BB->getInstList().pop_back(); + + // Create the new invoke instruction. + ImmutableCallSite CS(CI); + SmallVector InvokeArgs(CS.arg_begin(), CS.arg_end()); + InvokeInst *II = InvokeInst::Create(CI->getCalledValue(), Split, + Invoke.getOuterResumeDest(), + InvokeArgs, CI->getName(), BB); II->setCallingConv(CI->getCallingConv()); II->setAttributes(CI->getAttributes()); // Make sure that anything using the call now uses the invoke! This also - // updates the CallGraph if present. + // updates the CallGraph if present, because it uses a WeakVH. CI->replaceAllUsesWith(II); - - // Delete the unconditional branch inserted by splitBasicBlock - BB->getInstList().pop_back(); - Split->getInstList().pop_front(); // Delete the original call - - // Update any PHI nodes in the exceptional block to indicate that - // there is now a new entry in them. - unsigned i = 0; - for (BasicBlock::iterator I = InvokeDest->begin(); - isa(I); ++I, ++i) - cast(I)->addIncoming(InvokeDestPHIValues[i], BB); - - // This basic block is now complete, the caller will continue scanning the - // next one. - return; + + // Delete the original call + Split->getInstList().pop_front(); + + // Update any PHI nodes in the exceptional block to indicate that there is + // now a new entry in them. + Invoke.addIncomingPHIValuesFor(BB); + return false; } + + return false; } - /// HandleInlinedInvoke - If we inlined an invoke site, we need to convert calls -/// in the body of the inlined function into invokes and turn unwind -/// instructions into branches to the invoke unwind dest. +/// in the body of the inlined function into invokes. /// /// II is the invoke instruction being inlined. FirstNewBlock is the first /// block of the inlined code (the last block is the end of the function), @@ -106,62 +237,36 @@ static void HandleCallsInBlockInlinedThroughInvoke(BasicBlock *BB, static void HandleInlinedInvoke(InvokeInst *II, BasicBlock *FirstNewBlock, ClonedCodeInfo &InlinedCodeInfo) { BasicBlock *InvokeDest = II->getUnwindDest(); - SmallVector InvokeDestPHIValues; - - // If there are PHI nodes in the unwind destination block, we need to - // keep track of which values came into them from this invoke, then remove - // the entry for this block. - BasicBlock *InvokeBlock = II->getParent(); - for (BasicBlock::iterator I = InvokeDest->begin(); isa(I); ++I) { - PHINode *PN = cast(I); - // Save the value to use for this edge. - InvokeDestPHIValues.push_back(PN->getIncomingValueForBlock(InvokeBlock)); - } Function *Caller = FirstNewBlock->getParent(); // The inlined code is currently at the end of the function, scan from the // start of the inlined code to its end, checking for stuff we need to - // rewrite. If the code doesn't have calls or unwinds, we know there is - // nothing to rewrite. - if (!InlinedCodeInfo.ContainsCalls && !InlinedCodeInfo.ContainsUnwinds) { - // Now that everything is happy, we have one final detail. The PHI nodes in - // the exception destination block still have entries due to the original - // invoke instruction. Eliminate these entries (which might even delete the - // PHI node) now. - InvokeDest->removePredecessor(II->getParent()); - return; - } - + // rewrite. + InvokeInliningInfo Invoke(II); + + // Get all of the inlined landing pad instructions. + SmallPtrSet InlinedLPads; + for (Function::iterator I = FirstNewBlock, E = Caller->end(); I != E; ++I) + if (InvokeInst *II = dyn_cast(I->getTerminator())) + InlinedLPads.insert(II->getLandingPadInst()); + for (Function::iterator BB = FirstNewBlock, E = Caller->end(); BB != E; ++BB){ if (InlinedCodeInfo.ContainsCalls) - HandleCallsInBlockInlinedThroughInvoke(BB, InvokeDest, - InvokeDestPHIValues); - - if (UnwindInst *UI = dyn_cast(BB->getTerminator())) { - // An UnwindInst requires special handling when it gets inlined into an - // invoke site. Once this happens, we know that the unwind would cause - // a control transfer to the invoke exception destination, so we can - // transform it into a direct branch to the exception destination. - BranchInst::Create(InvokeDest, UI); - - // Delete the unwind instruction! - UI->eraseFromParent(); - - // Update any PHI nodes in the exceptional block to indicate that - // there is now a new entry in them. - unsigned i = 0; - for (BasicBlock::iterator I = InvokeDest->begin(); - isa(I); ++I, ++i) { - PHINode *PN = cast(I); - PN->addIncoming(InvokeDestPHIValues[i], BB); + if (HandleCallsInBlockInlinedThroughInvoke(BB, Invoke)) { + // Honor a request to skip the next block. + ++BB; + continue; } - } + + // Forward any resumes that are remaining here. + if (ResumeInst *RI = dyn_cast(BB->getTerminator())) + Invoke.forwardResume(RI, InlinedLPads); } // Now that everything is happy, we have one final detail. The PHI nodes in // the exception destination block still have entries due to the original - // invoke instruction. Eliminate these entries (which might even delete the + // invoke instruction. Eliminate these entries (which might even delete the // PHI node) now. InvokeDest->removePredecessor(II->getParent()); } @@ -172,8 +277,9 @@ static void HandleInlinedInvoke(InvokeInst *II, BasicBlock *FirstNewBlock, /// some edges of the callgraph may remain. static void UpdateCallGraphAfterInlining(CallSite CS, Function::iterator FirstNewBlock, - DenseMap &ValueMap, - CallGraph &CG) { + ValueToValueMapTy &VMap, + InlineFunctionInfo &IFI) { + CallGraph &CG = *IFI.CG; const Function *Caller = CS.getInstruction()->getParent()->getParent(); const Function *Callee = CS.getCalledFunction(); CallGraphNode *CalleeNode = CG[Callee]; @@ -194,15 +300,34 @@ static void UpdateCallGraphAfterInlining(CallSite CS, for (; I != E; ++I) { const Value *OrigCall = I->first; - DenseMap::iterator VMI = ValueMap.find(OrigCall); + ValueToValueMapTy::iterator VMI = VMap.find(OrigCall); // Only copy the edge if the call was inlined! - if (VMI == ValueMap.end() || VMI->second == 0) + if (VMI == VMap.end() || VMI->second == 0) continue; // If the call was inlined, but then constant folded, there is no edge to // add. Check for this case. - if (Instruction *NewCall = dyn_cast(VMI->second)) - CallerNode->addCalledFunction(CallSite::get(NewCall), I->second); + Instruction *NewCall = dyn_cast(VMI->second); + if (NewCall == 0) continue; + + // Remember that this call site got inlined for the client of + // InlineFunction. + IFI.InlinedCalls.push_back(NewCall); + + // It's possible that inlining the callsite will cause it to go from an + // indirect to a direct call by resolving a function pointer. If this + // happens, set the callee of the new call site to a more precise + // destination. This can also happen if the call graph node of the caller + // was just unnecessarily imprecise. + if (I->second->getFunction() == 0) + if (Function *F = CallSite(NewCall).getCalledFunction()) { + // Indirect call site resolved to direct call. + CallerNode->addCalledFunction(CallSite(NewCall), CG[F]); + + continue; + } + + CallerNode->addCalledFunction(CallSite(NewCall), I->second); } // Update the call graph by deleting the edge from Callee to Caller. We must @@ -210,28 +335,181 @@ static void UpdateCallGraphAfterInlining(CallSite CS, CallerNode->removeCallEdgeFor(CS); } -// InlineFunction - This function inlines the called function into the basic -// block of the caller. This returns false if it is not possible to inline this -// call. The program is still in a well defined state if this occurs though. -// -// Note that this only does one level of inlining. For example, if the -// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now -// exists in the instruction stream. Similiarly this will inline a recursive -// function by one level. -// -bool llvm::InlineFunction(CallSite CS, CallGraph *CG, const TargetData *TD, - SmallVectorImpl *StaticAllocas) { +/// HandleByValArgument - When inlining a call site that has a byval argument, +/// we have to make the implicit memcpy explicit by adding it. +static Value *HandleByValArgument(Value *Arg, Instruction *TheCall, + const Function *CalledFunc, + InlineFunctionInfo &IFI, + unsigned ByValAlignment) { + Type *AggTy = cast(Arg->getType())->getElementType(); + + // If the called function is readonly, then it could not mutate the caller's + // copy of the byval'd memory. In this case, it is safe to elide the copy and + // temporary. + if (CalledFunc->onlyReadsMemory()) { + // If the byval argument has a specified alignment that is greater than the + // passed in pointer, then we either have to round up the input pointer or + // give up on this transformation. + if (ByValAlignment <= 1) // 0 = unspecified, 1 = no particular alignment. + return Arg; + + // If the pointer is already known to be sufficiently aligned, or if we can + // round it up to a larger alignment, then we don't need a temporary. + if (getOrEnforceKnownAlignment(Arg, ByValAlignment, + IFI.TD) >= ByValAlignment) + return Arg; + + // Otherwise, we have to make a memcpy to get a safe alignment. This is bad + // for code quality, but rarely happens and is required for correctness. + } + + LLVMContext &Context = Arg->getContext(); + + Type *VoidPtrTy = Type::getInt8PtrTy(Context); + + // Create the alloca. If we have DataLayout, use nice alignment. + unsigned Align = 1; + if (IFI.TD) + Align = IFI.TD->getPrefTypeAlignment(AggTy); + + // If the byval had an alignment specified, we *must* use at least that + // alignment, as it is required by the byval argument (and uses of the + // pointer inside the callee). + Align = std::max(Align, ByValAlignment); + + Function *Caller = TheCall->getParent()->getParent(); + + Value *NewAlloca = new AllocaInst(AggTy, 0, Align, Arg->getName(), + &*Caller->begin()->begin()); + // Emit a memcpy. + Type *Tys[3] = {VoidPtrTy, VoidPtrTy, Type::getInt64Ty(Context)}; + Function *MemCpyFn = Intrinsic::getDeclaration(Caller->getParent(), + Intrinsic::memcpy, + Tys); + Value *DestCast = new BitCastInst(NewAlloca, VoidPtrTy, "tmp", TheCall); + Value *SrcCast = new BitCastInst(Arg, VoidPtrTy, "tmp", TheCall); + + Value *Size; + if (IFI.TD == 0) + Size = ConstantExpr::getSizeOf(AggTy); + else + Size = ConstantInt::get(Type::getInt64Ty(Context), + IFI.TD->getTypeStoreSize(AggTy)); + + // Always generate a memcpy of alignment 1 here because we don't know + // the alignment of the src pointer. Other optimizations can infer + // better alignment. + Value *CallArgs[] = { + DestCast, SrcCast, Size, + ConstantInt::get(Type::getInt32Ty(Context), 1), + ConstantInt::getFalse(Context) // isVolatile + }; + IRBuilder<>(TheCall).CreateCall(MemCpyFn, CallArgs); + + // Uses of the argument in the function should use our new alloca + // instead. + return NewAlloca; +} + +// isUsedByLifetimeMarker - Check whether this Value is used by a lifetime +// intrinsic. +static bool isUsedByLifetimeMarker(Value *V) { + for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE; + ++UI) { + if (IntrinsicInst *II = dyn_cast(*UI)) { + switch (II->getIntrinsicID()) { + default: break; + case Intrinsic::lifetime_start: + case Intrinsic::lifetime_end: + return true; + } + } + } + return false; +} + +// hasLifetimeMarkers - Check whether the given alloca already has +// lifetime.start or lifetime.end intrinsics. +static bool hasLifetimeMarkers(AllocaInst *AI) { + Type *Int8PtrTy = Type::getInt8PtrTy(AI->getType()->getContext()); + if (AI->getType() == Int8PtrTy) + return isUsedByLifetimeMarker(AI); + + // Do a scan to find all the casts to i8*. + for (Value::use_iterator I = AI->use_begin(), E = AI->use_end(); I != E; + ++I) { + if (I->getType() != Int8PtrTy) continue; + if (I->stripPointerCasts() != AI) continue; + if (isUsedByLifetimeMarker(*I)) + return true; + } + return false; +} + +/// updateInlinedAtInfo - Helper function used by fixupLineNumbers to +/// recursively update InlinedAtEntry of a DebugLoc. +static DebugLoc updateInlinedAtInfo(const DebugLoc &DL, + const DebugLoc &InlinedAtDL, + LLVMContext &Ctx) { + if (MDNode *IA = DL.getInlinedAt(Ctx)) { + DebugLoc NewInlinedAtDL + = updateInlinedAtInfo(DebugLoc::getFromDILocation(IA), InlinedAtDL, Ctx); + return DebugLoc::get(DL.getLine(), DL.getCol(), DL.getScope(Ctx), + NewInlinedAtDL.getAsMDNode(Ctx)); + } + + return DebugLoc::get(DL.getLine(), DL.getCol(), DL.getScope(Ctx), + InlinedAtDL.getAsMDNode(Ctx)); +} + +/// fixupLineNumbers - Update inlined instructions' line numbers to +/// to encode location where these instructions are inlined. +static void fixupLineNumbers(Function *Fn, Function::iterator FI, + Instruction *TheCall) { + DebugLoc TheCallDL = TheCall->getDebugLoc(); + if (TheCallDL.isUnknown()) + return; + + for (; FI != Fn->end(); ++FI) { + for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); + BI != BE; ++BI) { + DebugLoc DL = BI->getDebugLoc(); + if (!DL.isUnknown()) { + BI->setDebugLoc(updateInlinedAtInfo(DL, TheCallDL, BI->getContext())); + if (DbgValueInst *DVI = dyn_cast(BI)) { + LLVMContext &Ctx = BI->getContext(); + MDNode *InlinedAt = BI->getDebugLoc().getInlinedAt(Ctx); + DVI->setOperand(2, createInlinedVariable(DVI->getVariable(), + InlinedAt, Ctx)); + } + } + } + } +} + +/// InlineFunction - This function inlines the called function into the basic +/// block of the caller. This returns false if it is not possible to inline +/// this call. The program is still in a well defined state if this occurs +/// though. +/// +/// Note that this only does one level of inlining. For example, if the +/// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now +/// exists in the instruction stream. Similarly this will inline a recursive +/// function by one level. +bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI, + bool InsertLifetime) { Instruction *TheCall = CS.getInstruction(); - LLVMContext &Context = TheCall->getContext(); assert(TheCall->getParent() && TheCall->getParent()->getParent() && "Instruction not in function!"); + // If IFI has any state in it, zap it before we fill it in. + IFI.reset(); + const Function *CalledFunc = CS.getCalledFunction(); if (CalledFunc == 0 || // Can't inline external function or indirect CalledFunc->isDeclaration() || // call, or call to a vararg function! CalledFunc->getFunctionType()->isVarArg()) return false; - // If the call to the callee is not a tail call, we must clear the 'tail' // flags on any calls that we inline. bool MustClearTailCallFlags = @@ -255,9 +533,40 @@ bool llvm::InlineFunction(CallSite CS, CallGraph *CG, const TargetData *TD, return false; } + // Get the personality function from the callee if it contains a landing pad. + Value *CalleePersonality = 0; + for (Function::const_iterator I = CalledFunc->begin(), E = CalledFunc->end(); + I != E; ++I) + if (const InvokeInst *II = dyn_cast(I->getTerminator())) { + const BasicBlock *BB = II->getUnwindDest(); + const LandingPadInst *LP = BB->getLandingPadInst(); + CalleePersonality = LP->getPersonalityFn(); + break; + } + + // Find the personality function used by the landing pads of the caller. If it + // exists, then check to see that it matches the personality function used in + // the callee. + if (CalleePersonality) { + for (Function::const_iterator I = Caller->begin(), E = Caller->end(); + I != E; ++I) + if (const InvokeInst *II = dyn_cast(I->getTerminator())) { + const BasicBlock *BB = II->getUnwindDest(); + const LandingPadInst *LP = BB->getLandingPadInst(); + + // If the personality functions match, then we can perform the + // inlining. Otherwise, we can't inline. + // TODO: This isn't 100% true. Some personality functions are proper + // supersets of others and can be used in place of the other. + if (LP->getPersonalityFn() != CalleePersonality) + return false; + + break; + } + } + // Get an iterator to the last basic block in the function, which will have // the new function inlined after it. - // Function::iterator LastBlock = &Caller->back(); // Make sure to capture all of the return instructions from the cloned @@ -266,8 +575,8 @@ bool llvm::InlineFunction(CallSite CS, CallGraph *CG, const TargetData *TD, ClonedCodeInfo InlinedFunctionInfo; Function::iterator FirstNewBlock; - { // Scope to destroy ValueMap after cloning. - DenseMap ValueMap; + { // Scope to destroy VMap after cloning. + ValueToValueMapTy VMap; assert(CalledFunc->arg_size() == CS.arg_size() && "No varargs calls can be inlined!"); @@ -284,79 +593,42 @@ bool llvm::InlineFunction(CallSite CS, CallGraph *CG, const TargetData *TD, // by them explicit. However, we don't do this if the callee is readonly // or readnone, because the copy would be unneeded: the callee doesn't // modify the struct. - if (CalledFunc->paramHasAttr(ArgNo+1, Attribute::ByVal) && - !CalledFunc->onlyReadsMemory()) { - const Type *AggTy = cast(I->getType())->getElementType(); - const Type *VoidPtrTy = - Type::getInt8PtrTy(Context); - - // Create the alloca. If we have TargetData, use nice alignment. - unsigned Align = 1; - if (TD) Align = TD->getPrefTypeAlignment(AggTy); - Value *NewAlloca = new AllocaInst(AggTy, 0, Align, - I->getName(), - &*Caller->begin()->begin()); - // Emit a memcpy. - const Type *Tys[3] = {VoidPtrTy, VoidPtrTy, Type::getInt64Ty(Context)}; - Function *MemCpyFn = Intrinsic::getDeclaration(Caller->getParent(), - Intrinsic::memcpy, - Tys, 3); - Value *DestCast = new BitCastInst(NewAlloca, VoidPtrTy, "tmp", TheCall); - Value *SrcCast = new BitCastInst(*AI, VoidPtrTy, "tmp", TheCall); - - Value *Size; - if (TD == 0) - Size = ConstantExpr::getSizeOf(AggTy); - else - Size = ConstantInt::get(Type::getInt64Ty(Context), - TD->getTypeStoreSize(AggTy)); - - // Always generate a memcpy of alignment 1 here because we don't know - // the alignment of the src pointer. Other optimizations can infer - // better alignment. - Value *CallArgs[] = { - DestCast, SrcCast, Size, - ConstantInt::get(Type::getInt32Ty(Context), 1), - ConstantInt::get(Type::getInt1Ty(Context), 0) - }; - CallInst *TheMemCpy = - CallInst::Create(MemCpyFn, CallArgs, CallArgs+5, "", TheCall); - - // If we have a call graph, update it. - if (CG) { - CallGraphNode *MemCpyCGN = CG->getOrInsertFunction(MemCpyFn); - CallGraphNode *CallerNode = (*CG)[Caller]; - CallerNode->addCalledFunction(TheMemCpy, MemCpyCGN); - } - - // Uses of the argument in the function should use our new alloca - // instead. - ActualArg = NewAlloca; + if (CS.isByValArgument(ArgNo)) { + ActualArg = HandleByValArgument(ActualArg, TheCall, CalledFunc, IFI, + CalledFunc->getParamAlignment(ArgNo+1)); + + // Calls that we inline may use the new alloca, so we need to clear + // their 'tail' flags if HandleByValArgument introduced a new alloca and + // the callee has calls. + MustClearTailCallFlags |= ActualArg != *AI; } - ValueMap[I] = ActualArg; + VMap[I] = ActualArg; } // We want the inliner to prune the code as it copies. We would LOVE to // have no dead or constant instructions leftover after inlining occurs // (which can happen, e.g., because an argument was constant), but we'll be // happy with whatever the cloner can do. - CloneAndPruneFunctionInto(Caller, CalledFunc, ValueMap, Returns, ".i", - &InlinedFunctionInfo, TD, TheCall); + CloneAndPruneFunctionInto(Caller, CalledFunc, VMap, + /*ModuleLevelChanges=*/false, Returns, ".i", + &InlinedFunctionInfo, IFI.TD, TheCall); // Remember the first block that is newly cloned over. FirstNewBlock = LastBlock; ++FirstNewBlock; // Update the callgraph if requested. - if (CG) - UpdateCallGraphAfterInlining(CS, FirstNewBlock, ValueMap, *CG); + if (IFI.CG) + UpdateCallGraphAfterInlining(CS, FirstNewBlock, VMap, IFI); + + // Update inlined instructions' line number information. + fixupLineNumbers(Caller, FirstNewBlock, TheCall); } // If there are any alloca instructions in the block that used to be the entry // block for the callee, move them to the entry block of the caller. First // calculate which instruction they should be inserted before. We insert the // instructions at the end of the current alloca list. - // { BasicBlock::iterator InsertPoint = Caller->begin()->begin(); for (BasicBlock::iterator I = FirstNewBlock->begin(), @@ -374,15 +646,14 @@ bool llvm::InlineFunction(CallSite CS, CallGraph *CG, const TargetData *TD, if (!isa(AI->getArraySize())) continue; - // Keep track of the static allocas that we inline into the caller if the - // StaticAllocas pointer is non-null. - if (StaticAllocas) StaticAllocas->push_back(AI); + // Keep track of the static allocas that we inline into the caller. + IFI.StaticAllocas.push_back(AI); // Scan for the block of allocas that we can move over, and move them // all at once. while (isa(I) && isa(cast(I)->getArraySize())) { - if (StaticAllocas) StaticAllocas->push_back(cast(I)); + IFI.StaticAllocas.push_back(cast(I)); ++I; } @@ -395,6 +666,45 @@ bool llvm::InlineFunction(CallSite CS, CallGraph *CG, const TargetData *TD, } } + // Leave lifetime markers for the static alloca's, scoping them to the + // function we just inlined. + if (InsertLifetime && !IFI.StaticAllocas.empty()) { + IRBuilder<> builder(FirstNewBlock->begin()); + for (unsigned ai = 0, ae = IFI.StaticAllocas.size(); ai != ae; ++ai) { + AllocaInst *AI = IFI.StaticAllocas[ai]; + + // If the alloca is already scoped to something smaller than the whole + // function then there's no need to add redundant, less accurate markers. + if (hasLifetimeMarkers(AI)) + continue; + + // Try to determine the size of the allocation. + ConstantInt *AllocaSize = 0; + if (ConstantInt *AIArraySize = + dyn_cast(AI->getArraySize())) { + if (IFI.TD) { + Type *AllocaType = AI->getAllocatedType(); + uint64_t AllocaTypeSize = IFI.TD->getTypeAllocSize(AllocaType); + uint64_t AllocaArraySize = AIArraySize->getLimitedValue(); + assert(AllocaArraySize > 0 && "array size of AllocaInst is zero"); + // Check that array size doesn't saturate uint64_t and doesn't + // overflow when it's multiplied by type size. + if (AllocaArraySize != ~0ULL && + UINT64_MAX / AllocaArraySize >= AllocaTypeSize) { + AllocaSize = ConstantInt::get(Type::getInt64Ty(AI->getContext()), + AllocaArraySize * AllocaTypeSize); + } + } + } + + builder.CreateLifetimeStart(AI, AllocaSize); + for (unsigned ri = 0, re = Returns.size(); ri != re; ++ri) { + IRBuilder<> builder(Returns[ri]); + builder.CreateLifetimeEnd(AI, AllocaSize); + } + } + } + // If the inlined code contained dynamic alloca instructions, wrap the inlined // code with llvm.stacksave/llvm.stackrestore intrinsics. if (InlinedFunctionInfo.ContainsDynamicAllocas) { @@ -403,40 +713,14 @@ bool llvm::InlineFunction(CallSite CS, CallGraph *CG, const TargetData *TD, Function *StackSave = Intrinsic::getDeclaration(M, Intrinsic::stacksave); Function *StackRestore=Intrinsic::getDeclaration(M,Intrinsic::stackrestore); - // If we are preserving the callgraph, add edges to the stacksave/restore - // functions for the calls we insert. - CallGraphNode *StackSaveCGN = 0, *StackRestoreCGN = 0, *CallerNode = 0; - if (CG) { - StackSaveCGN = CG->getOrInsertFunction(StackSave); - StackRestoreCGN = CG->getOrInsertFunction(StackRestore); - CallerNode = (*CG)[Caller]; - } - // Insert the llvm.stacksave. - CallInst *SavedPtr = CallInst::Create(StackSave, "savedstack", - FirstNewBlock->begin()); - if (CG) CallerNode->addCalledFunction(SavedPtr, StackSaveCGN); + CallInst *SavedPtr = IRBuilder<>(FirstNewBlock, FirstNewBlock->begin()) + .CreateCall(StackSave, "savedstack"); // Insert a call to llvm.stackrestore before any return instructions in the // inlined function. for (unsigned i = 0, e = Returns.size(); i != e; ++i) { - CallInst *CI = CallInst::Create(StackRestore, SavedPtr, "", Returns[i]); - if (CG) CallerNode->addCalledFunction(CI, StackRestoreCGN); - } - - // Count the number of StackRestore calls we insert. - unsigned NumStackRestores = Returns.size(); - - // If we are inlining an invoke instruction, insert restores before each - // unwind. These unwinds will be rewritten into branches later. - if (InlinedFunctionInfo.ContainsUnwinds && isa(TheCall)) { - for (Function::iterator BB = FirstNewBlock, E = Caller->end(); - BB != E; ++BB) - if (UnwindInst *UI = dyn_cast(BB->getTerminator())) { - CallInst *CI = CallInst::Create(StackRestore, SavedPtr, "", UI); - if (CG) CallerNode->addCalledFunction(CI, StackRestoreCGN); - ++NumStackRestores; - } + IRBuilder<>(Returns[i]).CreateCall(StackRestore, SavedPtr); } } @@ -457,21 +741,8 @@ bool llvm::InlineFunction(CallSite CS, CallGraph *CG, const TargetData *TD, } } - // If we are inlining through a 'nounwind' call site then any inlined 'unwind' - // instructions are unreachable. - if (InlinedFunctionInfo.ContainsUnwinds && MarkNoUnwind) - for (Function::iterator BB = FirstNewBlock, E = Caller->end(); - BB != E; ++BB) { - TerminatorInst *Term = BB->getTerminator(); - if (isa(Term)) { - new UnreachableInst(Context, Term); - BB->getInstList().erase(Term); - } - } - // If we are inlining for an invoke instruction, we must make sure to rewrite - // any inlined 'unwind' instructions into branches to the invoke exception - // destination, and call instructions into invoke instructions. + // any call instructions into invoke instructions. if (InvokeInst *II = dyn_cast(TheCall)) HandleInlinedInvoke(II, FirstNewBlock, InlinedFunctionInfo); @@ -487,8 +758,10 @@ bool llvm::InlineFunction(CallSite CS, CallGraph *CG, const TargetData *TD, // If the call site was an invoke instruction, add a branch to the normal // destination. - if (InvokeInst *II = dyn_cast(TheCall)) - BranchInst::Create(II->getNormalDest(), TheCall); + if (InvokeInst *II = dyn_cast(TheCall)) { + BranchInst *NewBr = BranchInst::Create(II->getNormalDest(), TheCall); + NewBr->setDebugLoc(Returns[0]->getDebugLoc()); + } // If the return instruction returned a value, replace uses of the call with // uses of the returned value. @@ -516,15 +789,16 @@ bool llvm::InlineFunction(CallSite CS, CallGraph *CG, const TargetData *TD, // "starter" and "ender" blocks. How we accomplish this depends on whether // this is an invoke instruction or a call instruction. BasicBlock *AfterCallBB; + BranchInst *CreatedBranchToNormalDest = NULL; if (InvokeInst *II = dyn_cast(TheCall)) { // Add an unconditional branch to make this look like the CallInst case... - BranchInst *NewBr = BranchInst::Create(II->getNormalDest(), TheCall); + CreatedBranchToNormalDest = BranchInst::Create(II->getNormalDest(), TheCall); // Split the basic block. This guarantees that no PHI nodes will have to be // updated due to new incoming edges, and make the invoke case more // symmetric to the call case. - AfterCallBB = OrigBB->splitBasicBlock(NewBr, + AfterCallBB = OrigBB->splitBasicBlock(CreatedBranchToNormalDest, CalledFunc->getName()+".exit"); } else { // It's a call @@ -552,14 +826,14 @@ bool llvm::InlineFunction(CallSite CS, CallGraph *CG, const TargetData *TD, // Handle all of the return instructions that we just cloned in, and eliminate // any users of the original call/invoke instruction. - const Type *RTy = CalledFunc->getReturnType(); + Type *RTy = CalledFunc->getReturnType(); + PHINode *PHI = 0; if (Returns.size() > 1) { // The PHI node should go at the front of the new basic block to merge all // possible incoming values. - PHINode *PHI = 0; if (!TheCall->use_empty()) { - PHI = PHINode::Create(RTy, TheCall->getName(), + PHI = PHINode::Create(RTy, Returns.size(), TheCall->getName(), AfterCallBB->begin()); // Anything that used the result of the function call should now use the // PHI node as their operand. @@ -575,14 +849,6 @@ bool llvm::InlineFunction(CallSite CS, CallGraph *CG, const TargetData *TD, "Ret value not consistent in function!"); PHI->addIncoming(RI->getReturnValue(), RI->getParent()); } - - // Now that we inserted the PHI, check to see if it has a single value - // (e.g. all the entries are the same or undef). If so, remove the PHI so - // it doesn't block other optimizations. - if (Value *V = PHI->hasConstantValue()) { - PHI->replaceAllUsesWith(V); - PHI->eraseFromParent(); - } } @@ -602,14 +868,17 @@ bool llvm::InlineFunction(CallSite CS, CallGraph *CG, const TargetData *TD, TheCall->replaceAllUsesWith(Returns[0]->getReturnValue()); } + // Update PHI nodes that use the ReturnBB to use the AfterCallBB. + BasicBlock *ReturnBB = Returns[0]->getParent(); + ReturnBB->replaceAllUsesWith(AfterCallBB); + // Splice the code from the return block into the block that it will return // to, which contains the code that was after the call. - BasicBlock *ReturnBB = Returns[0]->getParent(); AfterCallBB->getInstList().splice(AfterCallBB->begin(), ReturnBB->getInstList()); - // Update PHI nodes that use the ReturnBB to use the AfterCallBB. - ReturnBB->replaceAllUsesWith(AfterCallBB); + if (CreatedBranchToNormalDest) + CreatedBranchToNormalDest->setDebugLoc(Returns[0]->getDebugLoc()); // Delete the return instruction now and empty ReturnBB now. Returns[0]->eraseFromParent(); @@ -630,8 +899,8 @@ bool llvm::InlineFunction(CallSite CS, CallGraph *CG, const TargetData *TD, // Splice the code entry block into calling block, right before the // unconditional branch. - OrigBB->getInstList().splice(Br, CalleeEntry->getInstList()); CalleeEntry->replaceAllUsesWith(OrigBB); // Update PHI nodes + OrigBB->getInstList().splice(Br, CalleeEntry->getInstList()); // Remove the unconditional branch. OrigBB->getInstList().erase(Br); @@ -639,5 +908,15 @@ bool llvm::InlineFunction(CallSite CS, CallGraph *CG, const TargetData *TD, // Now we can remove the CalleeEntry block, which is now empty. Caller->getBasicBlockList().erase(CalleeEntry); + // If we inserted a phi node, check to see if it has a single value (e.g. all + // the entries are the same or undef). If so, remove the PHI so it doesn't + // block other optimizations. + if (PHI) { + if (Value *V = SimplifyInstruction(PHI, IFI.TD)) { + PHI->replaceAllUsesWith(V); + PHI->eraseFromParent(); + } + } + return true; }