LLVM  mainline
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 is distributed under the University of Illinois Open Source
00006 // 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 //===----------------------------------------------------------------------===//
00014 
00015 #include "llvm/Transforms/Utils/Cloning.h"
00016 #include "llvm/ADT/SetVector.h"
00017 #include "llvm/ADT/SmallSet.h"
00018 #include "llvm/ADT/SmallVector.h"
00019 #include "llvm/ADT/StringExtras.h"
00020 #include "llvm/Analysis/AliasAnalysis.h"
00021 #include "llvm/Analysis/AssumptionCache.h"
00022 #include "llvm/Analysis/CallGraph.h"
00023 #include "llvm/Analysis/CaptureTracking.h"
00024 #include "llvm/Analysis/EHPersonalities.h"
00025 #include "llvm/Analysis/InstructionSimplify.h"
00026 #include "llvm/Analysis/ValueTracking.h"
00027 #include "llvm/IR/Attributes.h"
00028 #include "llvm/IR/CallSite.h"
00029 #include "llvm/IR/CFG.h"
00030 #include "llvm/IR/Constants.h"
00031 #include "llvm/IR/DataLayout.h"
00032 #include "llvm/IR/DebugInfo.h"
00033 #include "llvm/IR/DerivedTypes.h"
00034 #include "llvm/IR/DIBuilder.h"
00035 #include "llvm/IR/Dominators.h"
00036 #include "llvm/IR/IRBuilder.h"
00037 #include "llvm/IR/Instructions.h"
00038 #include "llvm/IR/IntrinsicInst.h"
00039 #include "llvm/IR/Intrinsics.h"
00040 #include "llvm/IR/MDBuilder.h"
00041 #include "llvm/IR/Module.h"
00042 #include "llvm/Transforms/Utils/Local.h"
00043 #include "llvm/Support/CommandLine.h"
00044 #include <algorithm>
00045 
00046 using namespace llvm;
00047 
00048 static cl::opt<bool>
00049 EnableNoAliasConversion("enable-noalias-to-md-conversion", cl::init(true),
00050   cl::Hidden,
00051   cl::desc("Convert noalias attributes to metadata during inlining."));
00052 
00053 static cl::opt<bool>
00054 PreserveAlignmentAssumptions("preserve-alignment-assumptions-during-inlining",
00055   cl::init(true), cl::Hidden,
00056   cl::desc("Convert align attributes to assumptions during inlining."));
00057 
00058 bool llvm::InlineFunction(CallInst *CI, InlineFunctionInfo &IFI,
00059                           AAResults *CalleeAAR, bool InsertLifetime) {
00060   return InlineFunction(CallSite(CI), IFI, CalleeAAR, InsertLifetime);
00061 }
00062 bool llvm::InlineFunction(InvokeInst *II, InlineFunctionInfo &IFI,
00063                           AAResults *CalleeAAR, bool InsertLifetime) {
00064   return InlineFunction(CallSite(II), IFI, CalleeAAR, InsertLifetime);
00065 }
00066 
00067 namespace {
00068   /// A class for recording information about inlining a landing pad.
00069   class LandingPadInliningInfo {
00070     BasicBlock *OuterResumeDest; ///< Destination of the invoke's unwind.
00071     BasicBlock *InnerResumeDest; ///< Destination for the callee's resume.
00072     LandingPadInst *CallerLPad;  ///< LandingPadInst associated with the invoke.
00073     PHINode *InnerEHValuesPHI;   ///< PHI for EH values from landingpad insts.
00074     SmallVector<Value*, 8> UnwindDestPHIValues;
00075 
00076   public:
00077     LandingPadInliningInfo(InvokeInst *II)
00078       : OuterResumeDest(II->getUnwindDest()), InnerResumeDest(nullptr),
00079         CallerLPad(nullptr), InnerEHValuesPHI(nullptr) {
00080       // If there are PHI nodes in the unwind destination block, we need to keep
00081       // track of which values came into them from the invoke before removing
00082       // the edge from this block.
00083       llvm::BasicBlock *InvokeBB = II->getParent();
00084       BasicBlock::iterator I = OuterResumeDest->begin();
00085       for (; isa<PHINode>(I); ++I) {
00086         // Save the value to use for this edge.
00087         PHINode *PHI = cast<PHINode>(I);
00088         UnwindDestPHIValues.push_back(PHI->getIncomingValueForBlock(InvokeBB));
00089       }
00090 
00091       CallerLPad = cast<LandingPadInst>(I);
00092     }
00093 
00094     /// The outer unwind destination is the target of
00095     /// unwind edges introduced for calls within the inlined function.
00096     BasicBlock *getOuterResumeDest() const {
00097       return OuterResumeDest;
00098     }
00099 
00100     BasicBlock *getInnerResumeDest();
00101 
00102     LandingPadInst *getLandingPadInst() const { return CallerLPad; }
00103 
00104     /// Forward the 'resume' instruction to the caller's landing pad block.
00105     /// When the landing pad block has only one predecessor, this is
00106     /// a simple branch. When there is more than one predecessor, we need to
00107     /// split the landing pad block after the landingpad instruction and jump
00108     /// to there.
00109     void forwardResume(ResumeInst *RI,
00110                        SmallPtrSetImpl<LandingPadInst*> &InlinedLPads);
00111 
00112     /// Add incoming-PHI values to the unwind destination block for the given
00113     /// basic block, using the values for the original invoke's source block.
00114     void addIncomingPHIValuesFor(BasicBlock *BB) const {
00115       addIncomingPHIValuesForInto(BB, OuterResumeDest);
00116     }
00117 
00118     void addIncomingPHIValuesForInto(BasicBlock *src, BasicBlock *dest) const {
00119       BasicBlock::iterator I = dest->begin();
00120       for (unsigned i = 0, e = UnwindDestPHIValues.size(); i != e; ++i, ++I) {
00121         PHINode *phi = cast<PHINode>(I);
00122         phi->addIncoming(UnwindDestPHIValues[i], src);
00123       }
00124     }
00125   };
00126 } // anonymous namespace
00127 
00128 /// Get or create a target for the branch from ResumeInsts.
00129 BasicBlock *LandingPadInliningInfo::getInnerResumeDest() {
00130   if (InnerResumeDest) return InnerResumeDest;
00131 
00132   // Split the landing pad.
00133   BasicBlock::iterator SplitPoint = ++CallerLPad->getIterator();
00134   InnerResumeDest =
00135     OuterResumeDest->splitBasicBlock(SplitPoint,
00136                                      OuterResumeDest->getName() + ".body");
00137 
00138   // The number of incoming edges we expect to the inner landing pad.
00139   const unsigned PHICapacity = 2;
00140 
00141   // Create corresponding new PHIs for all the PHIs in the outer landing pad.
00142   Instruction *InsertPoint = &InnerResumeDest->front();
00143   BasicBlock::iterator I = OuterResumeDest->begin();
00144   for (unsigned i = 0, e = UnwindDestPHIValues.size(); i != e; ++i, ++I) {
00145     PHINode *OuterPHI = cast<PHINode>(I);
00146     PHINode *InnerPHI = PHINode::Create(OuterPHI->getType(), PHICapacity,
00147                                         OuterPHI->getName() + ".lpad-body",
00148                                         InsertPoint);
00149     OuterPHI->replaceAllUsesWith(InnerPHI);
00150     InnerPHI->addIncoming(OuterPHI, OuterResumeDest);
00151   }
00152 
00153   // Create a PHI for the exception values.
00154   InnerEHValuesPHI = PHINode::Create(CallerLPad->getType(), PHICapacity,
00155                                      "eh.lpad-body", InsertPoint);
00156   CallerLPad->replaceAllUsesWith(InnerEHValuesPHI);
00157   InnerEHValuesPHI->addIncoming(CallerLPad, OuterResumeDest);
00158 
00159   // All done.
00160   return InnerResumeDest;
00161 }
00162 
00163 /// Forward the 'resume' instruction to the caller's landing pad block.
00164 /// When the landing pad block has only one predecessor, this is a simple
00165 /// branch. When there is more than one predecessor, we need to split the
00166 /// landing pad block after the landingpad instruction and jump to there.
00167 void LandingPadInliningInfo::forwardResume(
00168     ResumeInst *RI, SmallPtrSetImpl<LandingPadInst *> &InlinedLPads) {
00169   BasicBlock *Dest = getInnerResumeDest();
00170   BasicBlock *Src = RI->getParent();
00171 
00172   BranchInst::Create(Dest, Src);
00173 
00174   // Update the PHIs in the destination. They were inserted in an order which
00175   // makes this work.
00176   addIncomingPHIValuesForInto(Src, Dest);
00177 
00178   InnerEHValuesPHI->addIncoming(RI->getOperand(0), Src);
00179   RI->eraseFromParent();
00180 }
00181 
00182 /// Helper for getUnwindDestToken/getUnwindDestTokenHelper.
00183 static Value *getParentPad(Value *EHPad) {
00184   if (auto *FPI = dyn_cast<FuncletPadInst>(EHPad))
00185     return FPI->getParentPad();
00186   return cast<CatchSwitchInst>(EHPad)->getParentPad();
00187 }
00188 
00189 typedef DenseMap<Instruction *, Value *> UnwindDestMemoTy;
00190 
00191 /// Helper for getUnwindDestToken that does the descendant-ward part of
00192 /// the search.
00193 static Value *getUnwindDestTokenHelper(Instruction *EHPad,
00194                                        UnwindDestMemoTy &MemoMap) {
00195   SmallVector<Instruction *, 8> Worklist(1, EHPad);
00196 
00197   while (!Worklist.empty()) {
00198     Instruction *CurrentPad = Worklist.pop_back_val();
00199     // We only put pads on the worklist that aren't in the MemoMap.  When
00200     // we find an unwind dest for a pad we may update its ancestors, but
00201     // the queue only ever contains uncles/great-uncles/etc. of CurrentPad,
00202     // so they should never get updated while queued on the worklist.
00203     assert(!MemoMap.count(CurrentPad));
00204     Value *UnwindDestToken = nullptr;
00205     if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(CurrentPad)) {
00206       if (CatchSwitch->hasUnwindDest()) {
00207         UnwindDestToken = CatchSwitch->getUnwindDest()->getFirstNonPHI();
00208       } else {
00209         // Catchswitch doesn't have a 'nounwind' variant, and one might be
00210         // annotated as "unwinds to caller" when really it's nounwind (see
00211         // e.g. SimplifyCFGOpt::SimplifyUnreachable), so we can't infer the
00212         // parent's unwind dest from this.  We can check its catchpads'
00213         // descendants, since they might include a cleanuppad with an
00214         // "unwinds to caller" cleanupret, which can be trusted.
00215         for (auto HI = CatchSwitch->handler_begin(),
00216                   HE = CatchSwitch->handler_end();
00217              HI != HE && !UnwindDestToken; ++HI) {
00218           BasicBlock *HandlerBlock = *HI;
00219           auto *CatchPad = cast<CatchPadInst>(HandlerBlock->getFirstNonPHI());
00220           for (User *Child : CatchPad->users()) {
00221             // Intentionally ignore invokes here -- since the catchswitch is
00222             // marked "unwind to caller", it would be a verifier error if it
00223             // contained an invoke which unwinds out of it, so any invoke we'd
00224             // encounter must unwind to some child of the catch.
00225             if (!isa<CleanupPadInst>(Child) && !isa<CatchSwitchInst>(Child))
00226               continue;
00227 
00228             Instruction *ChildPad = cast<Instruction>(Child);
00229             auto Memo = MemoMap.find(ChildPad);
00230             if (Memo == MemoMap.end()) {
00231               // Haven't figure out this child pad yet; queue it.
00232               Worklist.push_back(ChildPad);
00233               continue;
00234             }
00235             // We've already checked this child, but might have found that
00236             // it offers no proof either way.
00237             Value *ChildUnwindDestToken = Memo->second;
00238             if (!ChildUnwindDestToken)
00239               continue;
00240             // We already know the child's unwind dest, which can either
00241             // be ConstantTokenNone to indicate unwind to caller, or can
00242             // be another child of the catchpad.  Only the former indicates
00243             // the unwind dest of the catchswitch.
00244             if (isa<ConstantTokenNone>(ChildUnwindDestToken)) {
00245               UnwindDestToken = ChildUnwindDestToken;
00246               break;
00247             }
00248             assert(getParentPad(ChildUnwindDestToken) == CatchPad);
00249           }
00250         }
00251       }
00252     } else {
00253       auto *CleanupPad = cast<CleanupPadInst>(CurrentPad);
00254       for (User *U : CleanupPad->users()) {
00255         if (auto *CleanupRet = dyn_cast<CleanupReturnInst>(U)) {
00256           if (BasicBlock *RetUnwindDest = CleanupRet->getUnwindDest())
00257             UnwindDestToken = RetUnwindDest->getFirstNonPHI();
00258           else
00259             UnwindDestToken = ConstantTokenNone::get(CleanupPad->getContext());
00260           break;
00261         }
00262         Value *ChildUnwindDestToken;
00263         if (auto *Invoke = dyn_cast<InvokeInst>(U)) {
00264           ChildUnwindDestToken = Invoke->getUnwindDest()->getFirstNonPHI();
00265         } else if (isa<CleanupPadInst>(U) || isa<CatchSwitchInst>(U)) {
00266           Instruction *ChildPad = cast<Instruction>(U);
00267           auto Memo = MemoMap.find(ChildPad);
00268           if (Memo == MemoMap.end()) {
00269             // Haven't resolved this child yet; queue it and keep searching.
00270             Worklist.push_back(ChildPad);
00271             continue;
00272           }
00273           // We've checked this child, but still need to ignore it if it
00274           // had no proof either way.
00275           ChildUnwindDestToken = Memo->second;
00276           if (!ChildUnwindDestToken)
00277             continue;
00278         } else {
00279           // Not a relevant user of the cleanuppad
00280           continue;
00281         }
00282         // In a well-formed program, the child/invoke must either unwind to
00283         // an(other) child of the cleanup, or exit the cleanup.  In the
00284         // first case, continue searching.
00285         if (isa<Instruction>(ChildUnwindDestToken) &&
00286             getParentPad(ChildUnwindDestToken) == CleanupPad)
00287           continue;
00288         UnwindDestToken = ChildUnwindDestToken;
00289         break;
00290       }
00291     }
00292     // If we haven't found an unwind dest for CurrentPad, we may have queued its
00293     // children, so move on to the next in the worklist.
00294     if (!UnwindDestToken)
00295       continue;
00296 
00297     // Now we know that CurrentPad unwinds to UnwindDestToken.  It also exits
00298     // any ancestors of CurrentPad up to but not including UnwindDestToken's
00299     // parent pad.  Record this in the memo map, and check to see if the
00300     // original EHPad being queried is one of the ones exited.
00301     Value *UnwindParent;
00302     if (auto *UnwindPad = dyn_cast<Instruction>(UnwindDestToken))
00303       UnwindParent = getParentPad(UnwindPad);
00304     else
00305       UnwindParent = nullptr;
00306     bool ExitedOriginalPad = false;
00307     for (Instruction *ExitedPad = CurrentPad;
00308          ExitedPad && ExitedPad != UnwindParent;
00309          ExitedPad = dyn_cast<Instruction>(getParentPad(ExitedPad))) {
00310       // Skip over catchpads since they just follow their catchswitches.
00311       if (isa<CatchPadInst>(ExitedPad))
00312         continue;
00313       MemoMap[ExitedPad] = UnwindDestToken;
00314       ExitedOriginalPad |= (ExitedPad == EHPad);
00315     }
00316 
00317     if (ExitedOriginalPad)
00318       return UnwindDestToken;
00319 
00320     // Continue the search.
00321   }
00322 
00323   // No definitive information is contained within this funclet.
00324   return nullptr;
00325 }
00326 
00327 /// Given an EH pad, find where it unwinds.  If it unwinds to an EH pad,
00328 /// return that pad instruction.  If it unwinds to caller, return
00329 /// ConstantTokenNone.  If it does not have a definitive unwind destination,
00330 /// return nullptr.
00331 ///
00332 /// This routine gets invoked for calls in funclets in inlinees when inlining
00333 /// an invoke.  Since many funclets don't have calls inside them, it's queried
00334 /// on-demand rather than building a map of pads to unwind dests up front.
00335 /// Determining a funclet's unwind dest may require recursively searching its
00336 /// descendants, and also ancestors and cousins if the descendants don't provide
00337 /// an answer.  Since most funclets will have their unwind dest immediately
00338 /// available as the unwind dest of a catchswitch or cleanupret, this routine
00339 /// searches top-down from the given pad and then up. To avoid worst-case
00340 /// quadratic run-time given that approach, it uses a memo map to avoid
00341 /// re-processing funclet trees.  The callers that rewrite the IR as they go
00342 /// take advantage of this, for correctness, by checking/forcing rewritten
00343 /// pads' entries to match the original callee view.
00344 static Value *getUnwindDestToken(Instruction *EHPad,
00345                                  UnwindDestMemoTy &MemoMap) {
00346   // Catchpads unwind to the same place as their catchswitch;
00347   // redirct any queries on catchpads so the code below can
00348   // deal with just catchswitches and cleanuppads.
00349   if (auto *CPI = dyn_cast<CatchPadInst>(EHPad))
00350     EHPad = CPI->getCatchSwitch();
00351 
00352   // Check if we've already determined the unwind dest for this pad.
00353   auto Memo = MemoMap.find(EHPad);
00354   if (Memo != MemoMap.end())
00355     return Memo->second;
00356 
00357   // Search EHPad and, if necessary, its descendants.
00358   Value *UnwindDestToken = getUnwindDestTokenHelper(EHPad, MemoMap);
00359   assert((UnwindDestToken == nullptr) != (MemoMap.count(EHPad) != 0));
00360   if (UnwindDestToken)
00361     return UnwindDestToken;
00362 
00363   // No information is available for this EHPad from itself or any of its
00364   // descendants.  An unwind all the way out to a pad in the caller would
00365   // need also to agree with the unwind dest of the parent funclet, so
00366   // search up the chain to try to find a funclet with information.  Put
00367   // null entries in the memo map to avoid re-processing as we go up.
00368   MemoMap[EHPad] = nullptr;
00369   Instruction *LastUselessPad = EHPad;
00370   Value *AncestorToken;
00371   for (AncestorToken = getParentPad(EHPad);
00372        auto *AncestorPad = dyn_cast<Instruction>(AncestorToken);
00373        AncestorToken = getParentPad(AncestorToken)) {
00374     // Skip over catchpads since they just follow their catchswitches.
00375     if (isa<CatchPadInst>(AncestorPad))
00376       continue;
00377     assert(!MemoMap.count(AncestorPad) || MemoMap[AncestorPad]);
00378     auto AncestorMemo = MemoMap.find(AncestorPad);
00379     if (AncestorMemo == MemoMap.end()) {
00380       UnwindDestToken = getUnwindDestTokenHelper(AncestorPad, MemoMap);
00381     } else {
00382       UnwindDestToken = AncestorMemo->second;
00383     }
00384     if (UnwindDestToken)
00385       break;
00386     LastUselessPad = AncestorPad;
00387   }
00388 
00389   // Since the whole tree under LastUselessPad has no information, it all must
00390   // match UnwindDestToken; record that to avoid repeating the search.
00391   SmallVector<Instruction *, 8> Worklist(1, LastUselessPad);
00392   while (!Worklist.empty()) {
00393     Instruction *UselessPad = Worklist.pop_back_val();
00394     assert(!MemoMap.count(UselessPad) || MemoMap[UselessPad] == nullptr);
00395     MemoMap[UselessPad] = UnwindDestToken;
00396     if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(UselessPad)) {
00397       for (BasicBlock *HandlerBlock : CatchSwitch->handlers())
00398         for (User *U : HandlerBlock->getFirstNonPHI()->users())
00399           if (isa<CatchSwitchInst>(U) || isa<CleanupPadInst>(U))
00400             Worklist.push_back(cast<Instruction>(U));
00401     } else {
00402       assert(isa<CleanupPadInst>(UselessPad));
00403       for (User *U : UselessPad->users())
00404         if (isa<CatchSwitchInst>(U) || isa<CleanupPadInst>(U))
00405           Worklist.push_back(cast<Instruction>(U));
00406     }
00407   }
00408 
00409   return UnwindDestToken;
00410 }
00411 
00412 /// When we inline a basic block into an invoke,
00413 /// we have to turn all of the calls that can throw into invokes.
00414 /// This function analyze BB to see if there are any calls, and if so,
00415 /// it rewrites them to be invokes that jump to InvokeDest and fills in the PHI
00416 /// nodes in that block with the values specified in InvokeDestPHIValues.
00417 static BasicBlock *HandleCallsInBlockInlinedThroughInvoke(
00418     BasicBlock *BB, BasicBlock *UnwindEdge,
00419     UnwindDestMemoTy *FuncletUnwindMap = nullptr) {
00420   for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) {
00421     Instruction *I = &*BBI++;
00422 
00423     // We only need to check for function calls: inlined invoke
00424     // instructions require no special handling.
00425     CallInst *CI = dyn_cast<CallInst>(I);
00426 
00427     if (!CI || CI->doesNotThrow() || isa<InlineAsm>(CI->getCalledValue()))
00428       continue;
00429 
00430     if (auto FuncletBundle = CI->getOperandBundle(LLVMContext::OB_funclet)) {
00431       // This call is nested inside a funclet.  If that funclet has an unwind
00432       // destination within the inlinee, then unwinding out of this call would
00433       // be UB.  Rewriting this call to an invoke which targets the inlined
00434       // invoke's unwind dest would give the call's parent funclet multiple
00435       // unwind destinations, which is something that subsequent EH table
00436       // generation can't handle and that the veirifer rejects.  So when we
00437       // see such a call, leave it as a call.
00438       auto *FuncletPad = cast<Instruction>(FuncletBundle->Inputs[0]);
00439       Value *UnwindDestToken =
00440           getUnwindDestToken(FuncletPad, *FuncletUnwindMap);
00441       if (UnwindDestToken && !isa<ConstantTokenNone>(UnwindDestToken))
00442         continue;
00443 #ifndef NDEBUG
00444       Instruction *MemoKey;
00445       if (auto *CatchPad = dyn_cast<CatchPadInst>(FuncletPad))
00446         MemoKey = CatchPad->getCatchSwitch();
00447       else
00448         MemoKey = FuncletPad;
00449       assert(FuncletUnwindMap->count(MemoKey) &&
00450              (*FuncletUnwindMap)[MemoKey] == UnwindDestToken &&
00451              "must get memoized to avoid confusing later searches");
00452 #endif // NDEBUG
00453     }
00454 
00455     // Convert this function call into an invoke instruction.  First, split the
00456     // basic block.
00457     BasicBlock *Split =
00458         BB->splitBasicBlock(CI->getIterator(), CI->getName() + ".noexc");
00459 
00460     // Delete the unconditional branch inserted by splitBasicBlock
00461     BB->getInstList().pop_back();
00462 
00463     // Create the new invoke instruction.
00464     SmallVector<Value*, 8> InvokeArgs(CI->arg_begin(), CI->arg_end());
00465     SmallVector<OperandBundleDef, 1> OpBundles;
00466 
00467     CI->getOperandBundlesAsDefs(OpBundles);
00468 
00469     // Note: we're round tripping operand bundles through memory here, and that
00470     // can potentially be avoided with a cleverer API design that we do not have
00471     // as of this time.
00472 
00473     InvokeInst *II =
00474         InvokeInst::Create(CI->getCalledValue(), Split, UnwindEdge, InvokeArgs,
00475                            OpBundles, CI->getName(), BB);
00476     II->setDebugLoc(CI->getDebugLoc());
00477     II->setCallingConv(CI->getCallingConv());
00478     II->setAttributes(CI->getAttributes());
00479     
00480     // Make sure that anything using the call now uses the invoke!  This also
00481     // updates the CallGraph if present, because it uses a WeakVH.
00482     CI->replaceAllUsesWith(II);
00483 
00484     // Delete the original call
00485     Split->getInstList().pop_front();
00486     return BB;
00487   }
00488   return nullptr;
00489 }
00490 
00491 /// If we inlined an invoke site, we need to convert calls
00492 /// in the body of the inlined function into invokes.
00493 ///
00494 /// II is the invoke instruction being inlined.  FirstNewBlock is the first
00495 /// block of the inlined code (the last block is the end of the function),
00496 /// and InlineCodeInfo is information about the code that got inlined.
00497 static void HandleInlinedLandingPad(InvokeInst *II, BasicBlock *FirstNewBlock,
00498                                     ClonedCodeInfo &InlinedCodeInfo) {
00499   BasicBlock *InvokeDest = II->getUnwindDest();
00500 
00501   Function *Caller = FirstNewBlock->getParent();
00502 
00503   // The inlined code is currently at the end of the function, scan from the
00504   // start of the inlined code to its end, checking for stuff we need to
00505   // rewrite.
00506   LandingPadInliningInfo Invoke(II);
00507 
00508   // Get all of the inlined landing pad instructions.
00509   SmallPtrSet<LandingPadInst*, 16> InlinedLPads;
00510   for (Function::iterator I = FirstNewBlock->getIterator(), E = Caller->end();
00511        I != E; ++I)
00512     if (InvokeInst *II = dyn_cast<InvokeInst>(I->getTerminator()))
00513       InlinedLPads.insert(II->getLandingPadInst());
00514 
00515   // Append the clauses from the outer landing pad instruction into the inlined
00516   // landing pad instructions.
00517   LandingPadInst *OuterLPad = Invoke.getLandingPadInst();
00518   for (LandingPadInst *InlinedLPad : InlinedLPads) {
00519     unsigned OuterNum = OuterLPad->getNumClauses();
00520     InlinedLPad->reserveClauses(OuterNum);
00521     for (unsigned OuterIdx = 0; OuterIdx != OuterNum; ++OuterIdx)
00522       InlinedLPad->addClause(OuterLPad->getClause(OuterIdx));
00523     if (OuterLPad->isCleanup())
00524       InlinedLPad->setCleanup(true);
00525   }
00526 
00527   for (Function::iterator BB = FirstNewBlock->getIterator(), E = Caller->end();
00528        BB != E; ++BB) {
00529     if (InlinedCodeInfo.ContainsCalls)
00530       if (BasicBlock *NewBB = HandleCallsInBlockInlinedThroughInvoke(
00531               &*BB, Invoke.getOuterResumeDest()))
00532         // Update any PHI nodes in the exceptional block to indicate that there
00533         // is now a new entry in them.
00534         Invoke.addIncomingPHIValuesFor(NewBB);
00535 
00536     // Forward any resumes that are remaining here.
00537     if (ResumeInst *RI = dyn_cast<ResumeInst>(BB->getTerminator()))
00538       Invoke.forwardResume(RI, InlinedLPads);
00539   }
00540 
00541   // Now that everything is happy, we have one final detail.  The PHI nodes in
00542   // the exception destination block still have entries due to the original
00543   // invoke instruction. Eliminate these entries (which might even delete the
00544   // PHI node) now.
00545   InvokeDest->removePredecessor(II->getParent());
00546 }
00547 
00548 /// If we inlined an invoke site, we need to convert calls
00549 /// in the body of the inlined function into invokes.
00550 ///
00551 /// II is the invoke instruction being inlined.  FirstNewBlock is the first
00552 /// block of the inlined code (the last block is the end of the function),
00553 /// and InlineCodeInfo is information about the code that got inlined.
00554 static void HandleInlinedEHPad(InvokeInst *II, BasicBlock *FirstNewBlock,
00555                                ClonedCodeInfo &InlinedCodeInfo) {
00556   BasicBlock *UnwindDest = II->getUnwindDest();
00557   Function *Caller = FirstNewBlock->getParent();
00558 
00559   assert(UnwindDest->getFirstNonPHI()->isEHPad() && "unexpected BasicBlock!");
00560 
00561   // If there are PHI nodes in the unwind destination block, we need to keep
00562   // track of which values came into them from the invoke before removing the
00563   // edge from this block.
00564   SmallVector<Value *, 8> UnwindDestPHIValues;
00565   llvm::BasicBlock *InvokeBB = II->getParent();
00566   for (Instruction &I : *UnwindDest) {
00567     // Save the value to use for this edge.
00568     PHINode *PHI = dyn_cast<PHINode>(&I);
00569     if (!PHI)
00570       break;
00571     UnwindDestPHIValues.push_back(PHI->getIncomingValueForBlock(InvokeBB));
00572   }
00573 
00574   // Add incoming-PHI values to the unwind destination block for the given basic
00575   // block, using the values for the original invoke's source block.
00576   auto UpdatePHINodes = [&](BasicBlock *Src) {
00577     BasicBlock::iterator I = UnwindDest->begin();
00578     for (Value *V : UnwindDestPHIValues) {
00579       PHINode *PHI = cast<PHINode>(I);
00580       PHI->addIncoming(V, Src);
00581       ++I;
00582     }
00583   };
00584 
00585   // This connects all the instructions which 'unwind to caller' to the invoke
00586   // destination.
00587   UnwindDestMemoTy FuncletUnwindMap;
00588   for (Function::iterator BB = FirstNewBlock->getIterator(), E = Caller->end();
00589        BB != E; ++BB) {
00590     if (auto *CRI = dyn_cast<CleanupReturnInst>(BB->getTerminator())) {
00591       if (CRI->unwindsToCaller()) {
00592         auto *CleanupPad = CRI->getCleanupPad();
00593         CleanupReturnInst::Create(CleanupPad, UnwindDest, CRI);
00594         CRI->eraseFromParent();
00595         UpdatePHINodes(&*BB);
00596         // Finding a cleanupret with an unwind destination would confuse
00597         // subsequent calls to getUnwindDestToken, so map the cleanuppad
00598         // to short-circuit any such calls and recognize this as an "unwind
00599         // to caller" cleanup.
00600         assert(!FuncletUnwindMap.count(CleanupPad) ||
00601                isa<ConstantTokenNone>(FuncletUnwindMap[CleanupPad]));
00602         FuncletUnwindMap[CleanupPad] =
00603             ConstantTokenNone::get(Caller->getContext());
00604       }
00605     }
00606 
00607     Instruction *I = BB->getFirstNonPHI();
00608     if (!I->isEHPad())
00609       continue;
00610 
00611     Instruction *Replacement = nullptr;
00612     if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(I)) {
00613       if (CatchSwitch->unwindsToCaller()) {
00614         Value *UnwindDestToken;
00615         if (auto *ParentPad =
00616                 dyn_cast<Instruction>(CatchSwitch->getParentPad())) {
00617           // This catchswitch is nested inside another funclet.  If that
00618           // funclet has an unwind destination within the inlinee, then
00619           // unwinding out of this catchswitch would be UB.  Rewriting this
00620           // catchswitch to unwind to the inlined invoke's unwind dest would
00621           // give the parent funclet multiple unwind destinations, which is
00622           // something that subsequent EH table generation can't handle and
00623           // that the veirifer rejects.  So when we see such a call, leave it
00624           // as "unwind to caller".
00625           UnwindDestToken = getUnwindDestToken(ParentPad, FuncletUnwindMap);
00626           if (UnwindDestToken && !isa<ConstantTokenNone>(UnwindDestToken))
00627             continue;
00628         } else {
00629           // This catchswitch has no parent to inherit constraints from, and
00630           // none of its descendants can have an unwind edge that exits it and
00631           // targets another funclet in the inlinee.  It may or may not have a
00632           // descendant that definitively has an unwind to caller.  In either
00633           // case, we'll have to assume that any unwinds out of it may need to
00634           // be routed to the caller, so treat it as though it has a definitive
00635           // unwind to caller.
00636           UnwindDestToken = ConstantTokenNone::get(Caller->getContext());
00637         }
00638         auto *NewCatchSwitch = CatchSwitchInst::Create(
00639             CatchSwitch->getParentPad(), UnwindDest,
00640             CatchSwitch->getNumHandlers(), CatchSwitch->getName(),
00641             CatchSwitch);
00642         for (BasicBlock *PadBB : CatchSwitch->handlers())
00643           NewCatchSwitch->addHandler(PadBB);
00644         // Propagate info for the old catchswitch over to the new one in
00645         // the unwind map.  This also serves to short-circuit any subsequent
00646         // checks for the unwind dest of this catchswitch, which would get
00647         // confused if they found the outer handler in the callee.
00648         FuncletUnwindMap[NewCatchSwitch] = UnwindDestToken;
00649         Replacement = NewCatchSwitch;
00650       }
00651     } else if (!isa<FuncletPadInst>(I)) {
00652       llvm_unreachable("unexpected EHPad!");
00653     }
00654 
00655     if (Replacement) {
00656       Replacement->takeName(I);
00657       I->replaceAllUsesWith(Replacement);
00658       I->eraseFromParent();
00659       UpdatePHINodes(&*BB);
00660     }
00661   }
00662 
00663   if (InlinedCodeInfo.ContainsCalls)
00664     for (Function::iterator BB = FirstNewBlock->getIterator(),
00665                             E = Caller->end();
00666          BB != E; ++BB)
00667       if (BasicBlock *NewBB = HandleCallsInBlockInlinedThroughInvoke(
00668               &*BB, UnwindDest, &FuncletUnwindMap))
00669         // Update any PHI nodes in the exceptional block to indicate that there
00670         // is now a new entry in them.
00671         UpdatePHINodes(NewBB);
00672 
00673   // Now that everything is happy, we have one final detail.  The PHI nodes in
00674   // the exception destination block still have entries due to the original
00675   // invoke instruction. Eliminate these entries (which might even delete the
00676   // PHI node) now.
00677   UnwindDest->removePredecessor(InvokeBB);
00678 }
00679 
00680 /// When inlining a function that contains noalias scope metadata,
00681 /// this metadata needs to be cloned so that the inlined blocks
00682 /// have different "unqiue scopes" at every call site. Were this not done, then
00683 /// aliasing scopes from a function inlined into a caller multiple times could
00684 /// not be differentiated (and this would lead to miscompiles because the
00685 /// non-aliasing property communicated by the metadata could have
00686 /// call-site-specific control dependencies).
00687 static void CloneAliasScopeMetadata(CallSite CS, ValueToValueMapTy &VMap) {
00688   const Function *CalledFunc = CS.getCalledFunction();
00689   SetVector<const MDNode *> MD;
00690 
00691   // Note: We could only clone the metadata if it is already used in the
00692   // caller. I'm omitting that check here because it might confuse
00693   // inter-procedural alias analysis passes. We can revisit this if it becomes
00694   // an efficiency or overhead problem.
00695 
00696   for (Function::const_iterator I = CalledFunc->begin(), IE = CalledFunc->end();
00697        I != IE; ++I)
00698     for (BasicBlock::const_iterator J = I->begin(), JE = I->end(); J != JE; ++J) {
00699       if (const MDNode *M = J->getMetadata(LLVMContext::MD_alias_scope))
00700         MD.insert(M);
00701       if (const MDNode *M = J->getMetadata(LLVMContext::MD_noalias))
00702         MD.insert(M);
00703     }
00704 
00705   if (MD.empty())
00706     return;
00707 
00708   // Walk the existing metadata, adding the complete (perhaps cyclic) chain to
00709   // the set.
00710   SmallVector<const Metadata *, 16> Queue(MD.begin(), MD.end());
00711   while (!Queue.empty()) {
00712     const MDNode *M = cast<MDNode>(Queue.pop_back_val());
00713     for (unsigned i = 0, ie = M->getNumOperands(); i != ie; ++i)
00714       if (const MDNode *M1 = dyn_cast<MDNode>(M->getOperand(i)))
00715         if (MD.insert(M1))
00716           Queue.push_back(M1);
00717   }
00718 
00719   // Now we have a complete set of all metadata in the chains used to specify
00720   // the noalias scopes and the lists of those scopes.
00721   SmallVector<TempMDTuple, 16> DummyNodes;
00722   DenseMap<const MDNode *, TrackingMDNodeRef> MDMap;
00723   for (SetVector<const MDNode *>::iterator I = MD.begin(), IE = MD.end();
00724        I != IE; ++I) {
00725     DummyNodes.push_back(MDTuple::getTemporary(CalledFunc->getContext(), None));
00726     MDMap[*I].reset(DummyNodes.back().get());
00727   }
00728 
00729   // Create new metadata nodes to replace the dummy nodes, replacing old
00730   // metadata references with either a dummy node or an already-created new
00731   // node.
00732   for (SetVector<const MDNode *>::iterator I = MD.begin(), IE = MD.end();
00733        I != IE; ++I) {
00734     SmallVector<Metadata *, 4> NewOps;
00735     for (unsigned i = 0, ie = (*I)->getNumOperands(); i != ie; ++i) {
00736       const Metadata *V = (*I)->getOperand(i);
00737       if (const MDNode *M = dyn_cast<MDNode>(V))
00738         NewOps.push_back(MDMap[M]);
00739       else
00740         NewOps.push_back(const_cast<Metadata *>(V));
00741     }
00742 
00743     MDNode *NewM = MDNode::get(CalledFunc->getContext(), NewOps);
00744     MDTuple *TempM = cast<MDTuple>(MDMap[*I]);
00745     assert(TempM->isTemporary() && "Expected temporary node");
00746 
00747     TempM->replaceAllUsesWith(NewM);
00748   }
00749 
00750   // Now replace the metadata in the new inlined instructions with the
00751   // repacements from the map.
00752   for (ValueToValueMapTy::iterator VMI = VMap.begin(), VMIE = VMap.end();
00753        VMI != VMIE; ++VMI) {
00754     if (!VMI->second)
00755       continue;
00756 
00757     Instruction *NI = dyn_cast<Instruction>(VMI->second);
00758     if (!NI)
00759       continue;
00760 
00761     if (MDNode *M = NI->getMetadata(LLVMContext::MD_alias_scope)) {
00762       MDNode *NewMD = MDMap[M];
00763       // If the call site also had alias scope metadata (a list of scopes to
00764       // which instructions inside it might belong), propagate those scopes to
00765       // the inlined instructions.
00766       if (MDNode *CSM =
00767               CS.getInstruction()->getMetadata(LLVMContext::MD_alias_scope))
00768         NewMD = MDNode::concatenate(NewMD, CSM);
00769       NI->setMetadata(LLVMContext::MD_alias_scope, NewMD);
00770     } else if (NI->mayReadOrWriteMemory()) {
00771       if (MDNode *M =
00772               CS.getInstruction()->getMetadata(LLVMContext::MD_alias_scope))
00773         NI->setMetadata(LLVMContext::MD_alias_scope, M);
00774     }
00775 
00776     if (MDNode *M = NI->getMetadata(LLVMContext::MD_noalias)) {
00777       MDNode *NewMD = MDMap[M];
00778       // If the call site also had noalias metadata (a list of scopes with
00779       // which instructions inside it don't alias), propagate those scopes to
00780       // the inlined instructions.
00781       if (MDNode *CSM =
00782               CS.getInstruction()->getMetadata(LLVMContext::MD_noalias))
00783         NewMD = MDNode::concatenate(NewMD, CSM);
00784       NI->setMetadata(LLVMContext::MD_noalias, NewMD);
00785     } else if (NI->mayReadOrWriteMemory()) {
00786       if (MDNode *M = CS.getInstruction()->getMetadata(LLVMContext::MD_noalias))
00787         NI->setMetadata(LLVMContext::MD_noalias, M);
00788     }
00789   }
00790 }
00791 
00792 /// If the inlined function has noalias arguments,
00793 /// then add new alias scopes for each noalias argument, tag the mapped noalias
00794 /// parameters with noalias metadata specifying the new scope, and tag all
00795 /// non-derived loads, stores and memory intrinsics with the new alias scopes.
00796 static void AddAliasScopeMetadata(CallSite CS, ValueToValueMapTy &VMap,
00797                                   const DataLayout &DL, AAResults *CalleeAAR) {
00798   if (!EnableNoAliasConversion)
00799     return;
00800 
00801   const Function *CalledFunc = CS.getCalledFunction();
00802   SmallVector<const Argument *, 4> NoAliasArgs;
00803 
00804   for (const Argument &Arg : CalledFunc->args())
00805     if (Arg.hasNoAliasAttr() && !Arg.use_empty())
00806       NoAliasArgs.push_back(&Arg);
00807 
00808   if (NoAliasArgs.empty())
00809     return;
00810 
00811   // To do a good job, if a noalias variable is captured, we need to know if
00812   // the capture point dominates the particular use we're considering.
00813   DominatorTree DT;
00814   DT.recalculate(const_cast<Function&>(*CalledFunc));
00815 
00816   // noalias indicates that pointer values based on the argument do not alias
00817   // pointer values which are not based on it. So we add a new "scope" for each
00818   // noalias function argument. Accesses using pointers based on that argument
00819   // become part of that alias scope, accesses using pointers not based on that
00820   // argument are tagged as noalias with that scope.
00821 
00822   DenseMap<const Argument *, MDNode *> NewScopes;
00823   MDBuilder MDB(CalledFunc->getContext());
00824 
00825   // Create a new scope domain for this function.
00826   MDNode *NewDomain =
00827     MDB.createAnonymousAliasScopeDomain(CalledFunc->getName());
00828   for (unsigned i = 0, e = NoAliasArgs.size(); i != e; ++i) {
00829     const Argument *A = NoAliasArgs[i];
00830 
00831     std::string Name = CalledFunc->getName();
00832     if (A->hasName()) {
00833       Name += ": %";
00834       Name += A->getName();
00835     } else {
00836       Name += ": argument ";
00837       Name += utostr(i);
00838     }
00839 
00840     // Note: We always create a new anonymous root here. This is true regardless
00841     // of the linkage of the callee because the aliasing "scope" is not just a
00842     // property of the callee, but also all control dependencies in the caller.
00843     MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name);
00844     NewScopes.insert(std::make_pair(A, NewScope));
00845   }
00846 
00847   // Iterate over all new instructions in the map; for all memory-access
00848   // instructions, add the alias scope metadata.
00849   for (ValueToValueMapTy::iterator VMI = VMap.begin(), VMIE = VMap.end();
00850        VMI != VMIE; ++VMI) {
00851     if (const Instruction *I = dyn_cast<Instruction>(VMI->first)) {
00852       if (!VMI->second)
00853         continue;
00854 
00855       Instruction *NI = dyn_cast<Instruction>(VMI->second);
00856       if (!NI)
00857         continue;
00858 
00859       bool IsArgMemOnlyCall = false, IsFuncCall = false;
00860       SmallVector<const Value *, 2> PtrArgs;
00861 
00862       if (const LoadInst *LI = dyn_cast<LoadInst>(I))
00863         PtrArgs.push_back(LI->getPointerOperand());
00864       else if (const StoreInst *SI = dyn_cast<StoreInst>(I))
00865         PtrArgs.push_back(SI->getPointerOperand());
00866       else if (const VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
00867         PtrArgs.push_back(VAAI->getPointerOperand());
00868       else if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(I))
00869         PtrArgs.push_back(CXI->getPointerOperand());
00870       else if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I))
00871         PtrArgs.push_back(RMWI->getPointerOperand());
00872       else if (ImmutableCallSite ICS = ImmutableCallSite(I)) {
00873         // If we know that the call does not access memory, then we'll still
00874         // know that about the inlined clone of this call site, and we don't
00875         // need to add metadata.
00876         if (ICS.doesNotAccessMemory())
00877           continue;
00878 
00879         IsFuncCall = true;
00880         if (CalleeAAR) {
00881           FunctionModRefBehavior MRB = CalleeAAR->getModRefBehavior(ICS);
00882           if (MRB == FMRB_OnlyAccessesArgumentPointees ||
00883               MRB == FMRB_OnlyReadsArgumentPointees)
00884             IsArgMemOnlyCall = true;
00885         }
00886 
00887         for (Value *Arg : ICS.args()) {
00888           // We need to check the underlying objects of all arguments, not just
00889           // the pointer arguments, because we might be passing pointers as
00890           // integers, etc.
00891           // However, if we know that the call only accesses pointer arguments,
00892           // then we only need to check the pointer arguments.
00893           if (IsArgMemOnlyCall && !Arg->getType()->isPointerTy())
00894             continue;
00895 
00896           PtrArgs.push_back(Arg);
00897         }
00898       }
00899 
00900       // If we found no pointers, then this instruction is not suitable for
00901       // pairing with an instruction to receive aliasing metadata.
00902       // However, if this is a call, this we might just alias with none of the
00903       // noalias arguments.
00904       if (PtrArgs.empty() && !IsFuncCall)
00905         continue;
00906 
00907       // It is possible that there is only one underlying object, but you
00908       // need to go through several PHIs to see it, and thus could be
00909       // repeated in the Objects list.
00910       SmallPtrSet<const Value *, 4> ObjSet;
00911       SmallVector<Metadata *, 4> Scopes, NoAliases;
00912 
00913       SmallSetVector<const Argument *, 4> NAPtrArgs;
00914       for (const Value *V : PtrArgs) {
00915         SmallVector<Value *, 4> Objects;
00916         GetUnderlyingObjects(const_cast<Value*>(V),
00917                              Objects, DL, /* LI = */ nullptr);
00918 
00919         for (Value *O : Objects)
00920           ObjSet.insert(O);
00921       }
00922 
00923       // Figure out if we're derived from anything that is not a noalias
00924       // argument.
00925       bool CanDeriveViaCapture = false, UsesAliasingPtr = false;
00926       for (const Value *V : ObjSet) {
00927         // Is this value a constant that cannot be derived from any pointer
00928         // value (we need to exclude constant expressions, for example, that
00929         // are formed from arithmetic on global symbols).
00930         bool IsNonPtrConst = isa<ConstantInt>(V) || isa<ConstantFP>(V) ||
00931                              isa<ConstantPointerNull>(V) ||
00932                              isa<ConstantDataVector>(V) || isa<UndefValue>(V);
00933         if (IsNonPtrConst)
00934           continue;
00935 
00936         // If this is anything other than a noalias argument, then we cannot
00937         // completely describe the aliasing properties using alias.scope
00938         // metadata (and, thus, won't add any).
00939         if (const Argument *A = dyn_cast<Argument>(V)) {
00940           if (!A->hasNoAliasAttr())
00941             UsesAliasingPtr = true;
00942         } else {
00943           UsesAliasingPtr = true;
00944         }
00945 
00946         // If this is not some identified function-local object (which cannot
00947         // directly alias a noalias argument), or some other argument (which,
00948         // by definition, also cannot alias a noalias argument), then we could
00949         // alias a noalias argument that has been captured).
00950         if (!isa<Argument>(V) &&
00951             !isIdentifiedFunctionLocal(const_cast<Value*>(V)))
00952           CanDeriveViaCapture = true;
00953       }
00954 
00955       // A function call can always get captured noalias pointers (via other
00956       // parameters, globals, etc.).
00957       if (IsFuncCall && !IsArgMemOnlyCall)
00958         CanDeriveViaCapture = true;
00959 
00960       // First, we want to figure out all of the sets with which we definitely
00961       // don't alias. Iterate over all noalias set, and add those for which:
00962       //   1. The noalias argument is not in the set of objects from which we
00963       //      definitely derive.
00964       //   2. The noalias argument has not yet been captured.
00965       // An arbitrary function that might load pointers could see captured
00966       // noalias arguments via other noalias arguments or globals, and so we
00967       // must always check for prior capture.
00968       for (const Argument *A : NoAliasArgs) {
00969         if (!ObjSet.count(A) && (!CanDeriveViaCapture ||
00970                                  // It might be tempting to skip the
00971                                  // PointerMayBeCapturedBefore check if
00972                                  // A->hasNoCaptureAttr() is true, but this is
00973                                  // incorrect because nocapture only guarantees
00974                                  // that no copies outlive the function, not
00975                                  // that the value cannot be locally captured.
00976                                  !PointerMayBeCapturedBefore(A,
00977                                    /* ReturnCaptures */ false,
00978                                    /* StoreCaptures */ false, I, &DT)))
00979           NoAliases.push_back(NewScopes[A]);
00980       }
00981 
00982       if (!NoAliases.empty())
00983         NI->setMetadata(LLVMContext::MD_noalias,
00984                         MDNode::concatenate(
00985                             NI->getMetadata(LLVMContext::MD_noalias),
00986                             MDNode::get(CalledFunc->getContext(), NoAliases)));
00987 
00988       // Next, we want to figure out all of the sets to which we might belong.
00989       // We might belong to a set if the noalias argument is in the set of
00990       // underlying objects. If there is some non-noalias argument in our list
00991       // of underlying objects, then we cannot add a scope because the fact
00992       // that some access does not alias with any set of our noalias arguments
00993       // cannot itself guarantee that it does not alias with this access
00994       // (because there is some pointer of unknown origin involved and the
00995       // other access might also depend on this pointer). We also cannot add
00996       // scopes to arbitrary functions unless we know they don't access any
00997       // non-parameter pointer-values.
00998       bool CanAddScopes = !UsesAliasingPtr;
00999       if (CanAddScopes && IsFuncCall)
01000         CanAddScopes = IsArgMemOnlyCall;
01001 
01002       if (CanAddScopes)
01003         for (const Argument *A : NoAliasArgs) {
01004           if (ObjSet.count(A))
01005             Scopes.push_back(NewScopes[A]);
01006         }
01007 
01008       if (!Scopes.empty())
01009         NI->setMetadata(
01010             LLVMContext::MD_alias_scope,
01011             MDNode::concatenate(NI->getMetadata(LLVMContext::MD_alias_scope),
01012                                 MDNode::get(CalledFunc->getContext(), Scopes)));
01013     }
01014   }
01015 }
01016 
01017 /// If the inlined function has non-byval align arguments, then
01018 /// add @llvm.assume-based alignment assumptions to preserve this information.
01019 static void AddAlignmentAssumptions(CallSite CS, InlineFunctionInfo &IFI) {
01020   if (!PreserveAlignmentAssumptions)
01021     return;
01022   auto &DL = CS.getCaller()->getParent()->getDataLayout();
01023 
01024   // To avoid inserting redundant assumptions, we should check for assumptions
01025   // already in the caller. To do this, we might need a DT of the caller.
01026   DominatorTree DT;
01027   bool DTCalculated = false;
01028 
01029   Function *CalledFunc = CS.getCalledFunction();
01030   for (Function::arg_iterator I = CalledFunc->arg_begin(),
01031                               E = CalledFunc->arg_end();
01032        I != E; ++I) {
01033     unsigned Align = I->getType()->isPointerTy() ? I->getParamAlignment() : 0;
01034     if (Align && !I->hasByValOrInAllocaAttr() && !I->hasNUses(0)) {
01035       if (!DTCalculated) {
01036         DT.recalculate(const_cast<Function&>(*CS.getInstruction()->getParent()
01037                                                ->getParent()));
01038         DTCalculated = true;
01039       }
01040 
01041       // If we can already prove the asserted alignment in the context of the
01042       // caller, then don't bother inserting the assumption.
01043       Value *Arg = CS.getArgument(I->getArgNo());
01044       if (getKnownAlignment(Arg, DL, CS.getInstruction(),
01045                             &IFI.ACT->getAssumptionCache(*CS.getCaller()),
01046                             &DT) >= Align)
01047         continue;
01048 
01049       IRBuilder<>(CS.getInstruction())
01050           .CreateAlignmentAssumption(DL, Arg, Align);
01051     }
01052   }
01053 }
01054 
01055 /// Once we have cloned code over from a callee into the caller,
01056 /// update the specified callgraph to reflect the changes we made.
01057 /// Note that it's possible that not all code was copied over, so only
01058 /// some edges of the callgraph may remain.
01059 static void UpdateCallGraphAfterInlining(CallSite CS,
01060                                          Function::iterator FirstNewBlock,
01061                                          ValueToValueMapTy &VMap,
01062                                          InlineFunctionInfo &IFI) {
01063   CallGraph &CG = *IFI.CG;
01064   const Function *Caller = CS.getInstruction()->getParent()->getParent();
01065   const Function *Callee = CS.getCalledFunction();
01066   CallGraphNode *CalleeNode = CG[Callee];
01067   CallGraphNode *CallerNode = CG[Caller];
01068 
01069   // Since we inlined some uninlined call sites in the callee into the caller,
01070   // add edges from the caller to all of the callees of the callee.
01071   CallGraphNode::iterator I = CalleeNode->begin(), E = CalleeNode->end();
01072 
01073   // Consider the case where CalleeNode == CallerNode.
01074   CallGraphNode::CalledFunctionsVector CallCache;
01075   if (CalleeNode == CallerNode) {
01076     CallCache.assign(I, E);
01077     I = CallCache.begin();
01078     E = CallCache.end();
01079   }
01080 
01081   for (; I != E; ++I) {
01082     const Value *OrigCall = I->first;
01083 
01084     ValueToValueMapTy::iterator VMI = VMap.find(OrigCall);
01085     // Only copy the edge if the call was inlined!
01086     if (VMI == VMap.end() || VMI->second == nullptr)
01087       continue;
01088     
01089     // If the call was inlined, but then constant folded, there is no edge to
01090     // add.  Check for this case.
01091     Instruction *NewCall = dyn_cast<Instruction>(VMI->second);
01092     if (!NewCall)
01093       continue;
01094 
01095     // We do not treat intrinsic calls like real function calls because we
01096     // expect them to become inline code; do not add an edge for an intrinsic.
01097     CallSite CS = CallSite(NewCall);
01098     if (CS && CS.getCalledFunction() && CS.getCalledFunction()->isIntrinsic())
01099       continue;
01100     
01101     // Remember that this call site got inlined for the client of
01102     // InlineFunction.
01103     IFI.InlinedCalls.push_back(NewCall);
01104 
01105     // It's possible that inlining the callsite will cause it to go from an
01106     // indirect to a direct call by resolving a function pointer.  If this
01107     // happens, set the callee of the new call site to a more precise
01108     // destination.  This can also happen if the call graph node of the caller
01109     // was just unnecessarily imprecise.
01110     if (!I->second->getFunction())
01111       if (Function *F = CallSite(NewCall).getCalledFunction()) {
01112         // Indirect call site resolved to direct call.
01113         CallerNode->addCalledFunction(CallSite(NewCall), CG[F]);
01114 
01115         continue;
01116       }
01117 
01118     CallerNode->addCalledFunction(CallSite(NewCall), I->second);
01119   }
01120   
01121   // Update the call graph by deleting the edge from Callee to Caller.  We must
01122   // do this after the loop above in case Caller and Callee are the same.
01123   CallerNode->removeCallEdgeFor(CS);
01124 }
01125 
01126 static void HandleByValArgumentInit(Value *Dst, Value *Src, Module *M,
01127                                     BasicBlock *InsertBlock,
01128                                     InlineFunctionInfo &IFI) {
01129   Type *AggTy = cast<PointerType>(Src->getType())->getElementType();
01130   IRBuilder<> Builder(InsertBlock, InsertBlock->begin());
01131 
01132   Value *Size = Builder.getInt64(M->getDataLayout().getTypeStoreSize(AggTy));
01133 
01134   // Always generate a memcpy of alignment 1 here because we don't know
01135   // the alignment of the src pointer.  Other optimizations can infer
01136   // better alignment.
01137   Builder.CreateMemCpy(Dst, Src, Size, /*Align=*/1);
01138 }
01139 
01140 /// When inlining a call site that has a byval argument,
01141 /// we have to make the implicit memcpy explicit by adding it.
01142 static Value *HandleByValArgument(Value *Arg, Instruction *TheCall,
01143                                   const Function *CalledFunc,
01144                                   InlineFunctionInfo &IFI,
01145                                   unsigned ByValAlignment) {
01146   PointerType *ArgTy = cast<PointerType>(Arg->getType());
01147   Type *AggTy = ArgTy->getElementType();
01148 
01149   Function *Caller = TheCall->getParent()->getParent();
01150 
01151   // If the called function is readonly, then it could not mutate the caller's
01152   // copy of the byval'd memory.  In this case, it is safe to elide the copy and
01153   // temporary.
01154   if (CalledFunc->onlyReadsMemory()) {
01155     // If the byval argument has a specified alignment that is greater than the
01156     // passed in pointer, then we either have to round up the input pointer or
01157     // give up on this transformation.
01158     if (ByValAlignment <= 1)  // 0 = unspecified, 1 = no particular alignment.
01159       return Arg;
01160 
01161     const DataLayout &DL = Caller->getParent()->getDataLayout();
01162 
01163     // If the pointer is already known to be sufficiently aligned, or if we can
01164     // round it up to a larger alignment, then we don't need a temporary.
01165     if (getOrEnforceKnownAlignment(Arg, ByValAlignment, DL, TheCall,
01166                                    &IFI.ACT->getAssumptionCache(*Caller)) >=
01167         ByValAlignment)
01168       return Arg;
01169     
01170     // Otherwise, we have to make a memcpy to get a safe alignment.  This is bad
01171     // for code quality, but rarely happens and is required for correctness.
01172   }
01173 
01174   // Create the alloca.  If we have DataLayout, use nice alignment.
01175   unsigned Align =
01176       Caller->getParent()->getDataLayout().getPrefTypeAlignment(AggTy);
01177 
01178   // If the byval had an alignment specified, we *must* use at least that
01179   // alignment, as it is required by the byval argument (and uses of the
01180   // pointer inside the callee).
01181   Align = std::max(Align, ByValAlignment);
01182   
01183   Value *NewAlloca = new AllocaInst(AggTy, nullptr, Align, Arg->getName(), 
01184                                     &*Caller->begin()->begin());
01185   IFI.StaticAllocas.push_back(cast<AllocaInst>(NewAlloca));
01186   
01187   // Uses of the argument in the function should use our new alloca
01188   // instead.
01189   return NewAlloca;
01190 }
01191 
01192 // Check whether this Value is used by a lifetime intrinsic.
01193 static bool isUsedByLifetimeMarker(Value *V) {
01194   for (User *U : V->users()) {
01195     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(U)) {
01196       switch (II->getIntrinsicID()) {
01197       default: break;
01198       case Intrinsic::lifetime_start:
01199       case Intrinsic::lifetime_end:
01200         return true;
01201       }
01202     }
01203   }
01204   return false;
01205 }
01206 
01207 // Check whether the given alloca already has
01208 // lifetime.start or lifetime.end intrinsics.
01209 static bool hasLifetimeMarkers(AllocaInst *AI) {
01210   Type *Ty = AI->getType();
01211   Type *Int8PtrTy = Type::getInt8PtrTy(Ty->getContext(),
01212                                        Ty->getPointerAddressSpace());
01213   if (Ty == Int8PtrTy)
01214     return isUsedByLifetimeMarker(AI);
01215 
01216   // Do a scan to find all the casts to i8*.
01217   for (User *U : AI->users()) {
01218     if (U->getType() != Int8PtrTy) continue;
01219     if (U->stripPointerCasts() != AI) continue;
01220     if (isUsedByLifetimeMarker(U))
01221       return true;
01222   }
01223   return false;
01224 }
01225 
01226 /// Rebuild the entire inlined-at chain for this instruction so that the top of
01227 /// the chain now is inlined-at the new call site.
01228 static DebugLoc
01229 updateInlinedAtInfo(DebugLoc DL, DILocation *InlinedAtNode, LLVMContext &Ctx,
01230                     DenseMap<const DILocation *, DILocation *> &IANodes) {
01231   SmallVector<DILocation *, 3> InlinedAtLocations;
01232   DILocation *Last = InlinedAtNode;
01233   DILocation *CurInlinedAt = DL;
01234 
01235   // Gather all the inlined-at nodes
01236   while (DILocation *IA = CurInlinedAt->getInlinedAt()) {
01237     // Skip any we've already built nodes for
01238     if (DILocation *Found = IANodes[IA]) {
01239       Last = Found;
01240       break;
01241     }
01242 
01243     InlinedAtLocations.push_back(IA);
01244     CurInlinedAt = IA;
01245   }
01246 
01247   // Starting from the top, rebuild the nodes to point to the new inlined-at
01248   // location (then rebuilding the rest of the chain behind it) and update the
01249   // map of already-constructed inlined-at nodes.
01250   for (const DILocation *MD : make_range(InlinedAtLocations.rbegin(),
01251                                          InlinedAtLocations.rend())) {
01252     Last = IANodes[MD] = DILocation::getDistinct(
01253         Ctx, MD->getLine(), MD->getColumn(), MD->getScope(), Last);
01254   }
01255 
01256   // And finally create the normal location for this instruction, referring to
01257   // the new inlined-at chain.
01258   return DebugLoc::get(DL.getLine(), DL.getCol(), DL.getScope(), Last);
01259 }
01260 
01261 /// Update inlined instructions' line numbers to
01262 /// to encode location where these instructions are inlined.
01263 static void fixupLineNumbers(Function *Fn, Function::iterator FI,
01264                              Instruction *TheCall) {
01265   DebugLoc TheCallDL = TheCall->getDebugLoc();
01266   if (!TheCallDL)
01267     return;
01268 
01269   auto &Ctx = Fn->getContext();
01270   DILocation *InlinedAtNode = TheCallDL;
01271 
01272   // Create a unique call site, not to be confused with any other call from the
01273   // same location.
01274   InlinedAtNode = DILocation::getDistinct(
01275       Ctx, InlinedAtNode->getLine(), InlinedAtNode->getColumn(),
01276       InlinedAtNode->getScope(), InlinedAtNode->getInlinedAt());
01277 
01278   // Cache the inlined-at nodes as they're built so they are reused, without
01279   // this every instruction's inlined-at chain would become distinct from each
01280   // other.
01281   DenseMap<const DILocation *, DILocation *> IANodes;
01282 
01283   for (; FI != Fn->end(); ++FI) {
01284     for (BasicBlock::iterator BI = FI->begin(), BE = FI->end();
01285          BI != BE; ++BI) {
01286       DebugLoc DL = BI->getDebugLoc();
01287       if (!DL) {
01288         // If the inlined instruction has no line number, make it look as if it
01289         // originates from the call location. This is important for
01290         // ((__always_inline__, __nodebug__)) functions which must use caller
01291         // location for all instructions in their function body.
01292 
01293         // Don't update static allocas, as they may get moved later.
01294         if (auto *AI = dyn_cast<AllocaInst>(BI))
01295           if (isa<Constant>(AI->getArraySize()))
01296             continue;
01297 
01298         BI->setDebugLoc(TheCallDL);
01299       } else {
01300         BI->setDebugLoc(updateInlinedAtInfo(DL, InlinedAtNode, BI->getContext(), IANodes));
01301       }
01302     }
01303   }
01304 }
01305 
01306 /// This function inlines the called function into the basic block of the
01307 /// caller. This returns false if it is not possible to inline this call.
01308 /// The program is still in a well defined state if this occurs though.
01309 ///
01310 /// Note that this only does one level of inlining.  For example, if the
01311 /// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now
01312 /// exists in the instruction stream.  Similarly this will inline a recursive
01313 /// function by one level.
01314 bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI,
01315                           AAResults *CalleeAAR, bool InsertLifetime) {
01316   Instruction *TheCall = CS.getInstruction();
01317   assert(TheCall->getParent() && TheCall->getParent()->getParent() &&
01318          "Instruction not in function!");
01319 
01320   // If IFI has any state in it, zap it before we fill it in.
01321   IFI.reset();
01322   
01323   const Function *CalledFunc = CS.getCalledFunction();
01324   if (!CalledFunc ||              // Can't inline external function or indirect
01325       CalledFunc->isDeclaration() || // call, or call to a vararg function!
01326       CalledFunc->getFunctionType()->isVarArg()) return false;
01327 
01328   // The inliner does not know how to inline through calls with operand bundles
01329   // in general ...
01330   if (CS.hasOperandBundles()) {
01331     for (int i = 0, e = CS.getNumOperandBundles(); i != e; ++i) {
01332       uint32_t Tag = CS.getOperandBundleAt(i).getTagID();
01333       // ... but it knows how to inline through "deopt" operand bundles ...
01334       if (Tag == LLVMContext::OB_deopt)
01335         continue;
01336       // ... and "funclet" operand bundles.
01337       if (Tag == LLVMContext::OB_funclet)
01338         continue;
01339 
01340       return false;
01341     }
01342   }
01343 
01344   // If the call to the callee cannot throw, set the 'nounwind' flag on any
01345   // calls that we inline.
01346   bool MarkNoUnwind = CS.doesNotThrow();
01347 
01348   BasicBlock *OrigBB = TheCall->getParent();
01349   Function *Caller = OrigBB->getParent();
01350 
01351   // GC poses two hazards to inlining, which only occur when the callee has GC:
01352   //  1. If the caller has no GC, then the callee's GC must be propagated to the
01353   //     caller.
01354   //  2. If the caller has a differing GC, it is invalid to inline.
01355   if (CalledFunc->hasGC()) {
01356     if (!Caller->hasGC())
01357       Caller->setGC(CalledFunc->getGC());
01358     else if (CalledFunc->getGC() != Caller->getGC())
01359       return false;
01360   }
01361 
01362   // Get the personality function from the callee if it contains a landing pad.
01363   Constant *CalledPersonality =
01364       CalledFunc->hasPersonalityFn()
01365           ? CalledFunc->getPersonalityFn()->stripPointerCasts()
01366           : nullptr;
01367 
01368   // Find the personality function used by the landing pads of the caller. If it
01369   // exists, then check to see that it matches the personality function used in
01370   // the callee.
01371   Constant *CallerPersonality =
01372       Caller->hasPersonalityFn()
01373           ? Caller->getPersonalityFn()->stripPointerCasts()
01374           : nullptr;
01375   if (CalledPersonality) {
01376     if (!CallerPersonality)
01377       Caller->setPersonalityFn(CalledPersonality);
01378     // If the personality functions match, then we can perform the
01379     // inlining. Otherwise, we can't inline.
01380     // TODO: This isn't 100% true. Some personality functions are proper
01381     //       supersets of others and can be used in place of the other.
01382     else if (CalledPersonality != CallerPersonality)
01383       return false;
01384   }
01385 
01386   // We need to figure out which funclet the callsite was in so that we may
01387   // properly nest the callee.
01388   Instruction *CallSiteEHPad = nullptr;
01389   if (CallerPersonality) {
01390     EHPersonality Personality = classifyEHPersonality(CallerPersonality);
01391     if (isFuncletEHPersonality(Personality)) {
01392       Optional<OperandBundleUse> ParentFunclet =
01393           CS.getOperandBundle(LLVMContext::OB_funclet);
01394       if (ParentFunclet)
01395         CallSiteEHPad = cast<FuncletPadInst>(ParentFunclet->Inputs.front());
01396 
01397       // OK, the inlining site is legal.  What about the target function?
01398 
01399       if (CallSiteEHPad) {
01400         if (Personality == EHPersonality::MSVC_CXX) {
01401           // The MSVC personality cannot tolerate catches getting inlined into
01402           // cleanup funclets.
01403           if (isa<CleanupPadInst>(CallSiteEHPad)) {
01404             // Ok, the call site is within a cleanuppad.  Let's check the callee
01405             // for catchpads.
01406             for (const BasicBlock &CalledBB : *CalledFunc) {
01407               if (isa<CatchSwitchInst>(CalledBB.getFirstNonPHI()))
01408                 return false;
01409             }
01410           }
01411         } else if (isAsynchronousEHPersonality(Personality)) {
01412           // SEH is even less tolerant, there may not be any sort of exceptional
01413           // funclet in the callee.
01414           for (const BasicBlock &CalledBB : *CalledFunc) {
01415             if (CalledBB.isEHPad())
01416               return false;
01417           }
01418         }
01419       }
01420     }
01421   }
01422 
01423   // Get an iterator to the last basic block in the function, which will have
01424   // the new function inlined after it.
01425   Function::iterator LastBlock = --Caller->end();
01426 
01427   // Make sure to capture all of the return instructions from the cloned
01428   // function.
01429   SmallVector<ReturnInst*, 8> Returns;
01430   ClonedCodeInfo InlinedFunctionInfo;
01431   Function::iterator FirstNewBlock;
01432 
01433   { // Scope to destroy VMap after cloning.
01434     ValueToValueMapTy VMap;
01435     // Keep a list of pair (dst, src) to emit byval initializations.
01436     SmallVector<std::pair<Value*, Value*>, 4> ByValInit;
01437 
01438     auto &DL = Caller->getParent()->getDataLayout();
01439 
01440     assert(CalledFunc->arg_size() == CS.arg_size() &&
01441            "No varargs calls can be inlined!");
01442 
01443     // Calculate the vector of arguments to pass into the function cloner, which
01444     // matches up the formal to the actual argument values.
01445     CallSite::arg_iterator AI = CS.arg_begin();
01446     unsigned ArgNo = 0;
01447     for (Function::const_arg_iterator I = CalledFunc->arg_begin(),
01448          E = CalledFunc->arg_end(); I != E; ++I, ++AI, ++ArgNo) {
01449       Value *ActualArg = *AI;
01450 
01451       // When byval arguments actually inlined, we need to make the copy implied
01452       // by them explicit.  However, we don't do this if the callee is readonly
01453       // or readnone, because the copy would be unneeded: the callee doesn't
01454       // modify the struct.
01455       if (CS.isByValArgument(ArgNo)) {
01456         ActualArg = HandleByValArgument(ActualArg, TheCall, CalledFunc, IFI,
01457                                         CalledFunc->getParamAlignment(ArgNo+1));
01458         if (ActualArg != *AI)
01459           ByValInit.push_back(std::make_pair(ActualArg, (Value*) *AI));
01460       }
01461 
01462       VMap[&*I] = ActualArg;
01463     }
01464 
01465     // Add alignment assumptions if necessary. We do this before the inlined
01466     // instructions are actually cloned into the caller so that we can easily
01467     // check what will be known at the start of the inlined code.
01468     AddAlignmentAssumptions(CS, IFI);
01469 
01470     // We want the inliner to prune the code as it copies.  We would LOVE to
01471     // have no dead or constant instructions leftover after inlining occurs
01472     // (which can happen, e.g., because an argument was constant), but we'll be
01473     // happy with whatever the cloner can do.
01474     CloneAndPruneFunctionInto(Caller, CalledFunc, VMap,
01475                               /*ModuleLevelChanges=*/false, Returns, ".i",
01476                               &InlinedFunctionInfo, TheCall);
01477 
01478     // Remember the first block that is newly cloned over.
01479     FirstNewBlock = LastBlock; ++FirstNewBlock;
01480 
01481     // Inject byval arguments initialization.
01482     for (std::pair<Value*, Value*> &Init : ByValInit)
01483       HandleByValArgumentInit(Init.first, Init.second, Caller->getParent(),
01484                               &*FirstNewBlock, IFI);
01485 
01486     Optional<OperandBundleUse> ParentDeopt =
01487         CS.getOperandBundle(LLVMContext::OB_deopt);
01488     if (ParentDeopt) {
01489       SmallVector<OperandBundleDef, 2> OpDefs;
01490 
01491       for (auto &VH : InlinedFunctionInfo.OperandBundleCallSites) {
01492         Instruction *I = dyn_cast_or_null<Instruction>(VH);
01493         if (!I) continue;  // instruction was DCE'd or RAUW'ed to undef
01494 
01495         OpDefs.clear();
01496 
01497         CallSite ICS(I);
01498         OpDefs.reserve(ICS.getNumOperandBundles());
01499 
01500         for (unsigned i = 0, e = ICS.getNumOperandBundles(); i < e; ++i) {
01501           auto ChildOB = ICS.getOperandBundleAt(i);
01502           if (ChildOB.getTagID() != LLVMContext::OB_deopt) {
01503             // If the inlined call has other operand bundles, let them be
01504             OpDefs.emplace_back(ChildOB);
01505             continue;
01506           }
01507 
01508           // It may be useful to separate this logic (of handling operand
01509           // bundles) out to a separate "policy" component if this gets crowded.
01510           // Prepend the parent's deoptimization continuation to the newly
01511           // inlined call's deoptimization continuation.
01512           std::vector<Value *> MergedDeoptArgs;
01513           MergedDeoptArgs.reserve(ParentDeopt->Inputs.size() +
01514                                   ChildOB.Inputs.size());
01515 
01516           MergedDeoptArgs.insert(MergedDeoptArgs.end(),
01517                                  ParentDeopt->Inputs.begin(),
01518                                  ParentDeopt->Inputs.end());
01519           MergedDeoptArgs.insert(MergedDeoptArgs.end(), ChildOB.Inputs.begin(),
01520                                  ChildOB.Inputs.end());
01521 
01522           OpDefs.emplace_back("deopt", std::move(MergedDeoptArgs));
01523         }
01524 
01525         Instruction *NewI = nullptr;
01526         if (isa<CallInst>(I))
01527           NewI = CallInst::Create(cast<CallInst>(I), OpDefs, I);
01528         else
01529           NewI = InvokeInst::Create(cast<InvokeInst>(I), OpDefs, I);
01530 
01531         // Note: the RAUW does the appropriate fixup in VMap, so we need to do
01532         // this even if the call returns void.
01533         I->replaceAllUsesWith(NewI);
01534 
01535         VH = nullptr;
01536         I->eraseFromParent();
01537       }
01538     }
01539 
01540     // Update the callgraph if requested.
01541     if (IFI.CG)
01542       UpdateCallGraphAfterInlining(CS, FirstNewBlock, VMap, IFI);
01543 
01544     // Update inlined instructions' line number information.
01545     fixupLineNumbers(Caller, FirstNewBlock, TheCall);
01546 
01547     // Clone existing noalias metadata if necessary.
01548     CloneAliasScopeMetadata(CS, VMap);
01549 
01550     // Add noalias metadata if necessary.
01551     AddAliasScopeMetadata(CS, VMap, DL, CalleeAAR);
01552 
01553     // FIXME: We could register any cloned assumptions instead of clearing the
01554     // whole function's cache.
01555     if (IFI.ACT)
01556       IFI.ACT->getAssumptionCache(*Caller).clear();
01557   }
01558 
01559   // If there are any alloca instructions in the block that used to be the entry
01560   // block for the callee, move them to the entry block of the caller.  First
01561   // calculate which instruction they should be inserted before.  We insert the
01562   // instructions at the end of the current alloca list.
01563   {
01564     BasicBlock::iterator InsertPoint = Caller->begin()->begin();
01565     for (BasicBlock::iterator I = FirstNewBlock->begin(),
01566          E = FirstNewBlock->end(); I != E; ) {
01567       AllocaInst *AI = dyn_cast<AllocaInst>(I++);
01568       if (!AI) continue;
01569       
01570       // If the alloca is now dead, remove it.  This often occurs due to code
01571       // specialization.
01572       if (AI->use_empty()) {
01573         AI->eraseFromParent();
01574         continue;
01575       }
01576 
01577       if (!isa<Constant>(AI->getArraySize()))
01578         continue;
01579       
01580       // Keep track of the static allocas that we inline into the caller.
01581       IFI.StaticAllocas.push_back(AI);
01582       
01583       // Scan for the block of allocas that we can move over, and move them
01584       // all at once.
01585       while (isa<AllocaInst>(I) &&
01586              isa<Constant>(cast<AllocaInst>(I)->getArraySize())) {
01587         IFI.StaticAllocas.push_back(cast<AllocaInst>(I));
01588         ++I;
01589       }
01590 
01591       // Transfer all of the allocas over in a block.  Using splice means
01592       // that the instructions aren't removed from the symbol table, then
01593       // reinserted.
01594       Caller->getEntryBlock().getInstList().splice(
01595           InsertPoint, FirstNewBlock->getInstList(), AI->getIterator(), I);
01596     }
01597     // Move any dbg.declares describing the allocas into the entry basic block.
01598     DIBuilder DIB(*Caller->getParent());
01599     for (auto &AI : IFI.StaticAllocas)
01600       replaceDbgDeclareForAlloca(AI, AI, DIB, /*Deref=*/false);
01601   }
01602 
01603   bool InlinedMustTailCalls = false;
01604   if (InlinedFunctionInfo.ContainsCalls) {
01605     CallInst::TailCallKind CallSiteTailKind = CallInst::TCK_None;
01606     if (CallInst *CI = dyn_cast<CallInst>(TheCall))
01607       CallSiteTailKind = CI->getTailCallKind();
01608 
01609     for (Function::iterator BB = FirstNewBlock, E = Caller->end(); BB != E;
01610          ++BB) {
01611       for (Instruction &I : *BB) {
01612         CallInst *CI = dyn_cast<CallInst>(&I);
01613         if (!CI)
01614           continue;
01615 
01616         // We need to reduce the strength of any inlined tail calls.  For
01617         // musttail, we have to avoid introducing potential unbounded stack
01618         // growth.  For example, if functions 'f' and 'g' are mutually recursive
01619         // with musttail, we can inline 'g' into 'f' so long as we preserve
01620         // musttail on the cloned call to 'f'.  If either the inlined call site
01621         // or the cloned call site is *not* musttail, the program already has
01622         // one frame of stack growth, so it's safe to remove musttail.  Here is
01623         // a table of example transformations:
01624         //
01625         //    f -> musttail g -> musttail f  ==>  f -> musttail f
01626         //    f -> musttail g ->     tail f  ==>  f ->     tail f
01627         //    f ->          g -> musttail f  ==>  f ->          f
01628         //    f ->          g ->     tail f  ==>  f ->          f
01629         CallInst::TailCallKind ChildTCK = CI->getTailCallKind();
01630         ChildTCK = std::min(CallSiteTailKind, ChildTCK);
01631         CI->setTailCallKind(ChildTCK);
01632         InlinedMustTailCalls |= CI->isMustTailCall();
01633 
01634         // Calls inlined through a 'nounwind' call site should be marked
01635         // 'nounwind'.
01636         if (MarkNoUnwind)
01637           CI->setDoesNotThrow();
01638       }
01639     }
01640   }
01641 
01642   // Leave lifetime markers for the static alloca's, scoping them to the
01643   // function we just inlined.
01644   if (InsertLifetime && !IFI.StaticAllocas.empty()) {
01645     IRBuilder<> builder(&FirstNewBlock->front());
01646     for (unsigned ai = 0, ae = IFI.StaticAllocas.size(); ai != ae; ++ai) {
01647       AllocaInst *AI = IFI.StaticAllocas[ai];
01648 
01649       // If the alloca is already scoped to something smaller than the whole
01650       // function then there's no need to add redundant, less accurate markers.
01651       if (hasLifetimeMarkers(AI))
01652         continue;
01653 
01654       // Try to determine the size of the allocation.
01655       ConstantInt *AllocaSize = nullptr;
01656       if (ConstantInt *AIArraySize =
01657           dyn_cast<ConstantInt>(AI->getArraySize())) {
01658         auto &DL = Caller->getParent()->getDataLayout();
01659         Type *AllocaType = AI->getAllocatedType();
01660         uint64_t AllocaTypeSize = DL.getTypeAllocSize(AllocaType);
01661         uint64_t AllocaArraySize = AIArraySize->getLimitedValue();
01662 
01663         // Don't add markers for zero-sized allocas.
01664         if (AllocaArraySize == 0)
01665           continue;
01666 
01667         // Check that array size doesn't saturate uint64_t and doesn't
01668         // overflow when it's multiplied by type size.
01669         if (AllocaArraySize != ~0ULL &&
01670             UINT64_MAX / AllocaArraySize >= AllocaTypeSize) {
01671           AllocaSize = ConstantInt::get(Type::getInt64Ty(AI->getContext()),
01672                                         AllocaArraySize * AllocaTypeSize);
01673         }
01674       }
01675 
01676       builder.CreateLifetimeStart(AI, AllocaSize);
01677       for (ReturnInst *RI : Returns) {
01678         // Don't insert llvm.lifetime.end calls between a musttail call and a
01679         // return.  The return kills all local allocas.
01680         if (InlinedMustTailCalls &&
01681             RI->getParent()->getTerminatingMustTailCall())
01682           continue;
01683         IRBuilder<>(RI).CreateLifetimeEnd(AI, AllocaSize);
01684       }
01685     }
01686   }
01687 
01688   // If the inlined code contained dynamic alloca instructions, wrap the inlined
01689   // code with llvm.stacksave/llvm.stackrestore intrinsics.
01690   if (InlinedFunctionInfo.ContainsDynamicAllocas) {
01691     Module *M = Caller->getParent();
01692     // Get the two intrinsics we care about.
01693     Function *StackSave = Intrinsic::getDeclaration(M, Intrinsic::stacksave);
01694     Function *StackRestore=Intrinsic::getDeclaration(M,Intrinsic::stackrestore);
01695 
01696     // Insert the llvm.stacksave.
01697     CallInst *SavedPtr = IRBuilder<>(&*FirstNewBlock, FirstNewBlock->begin())
01698                              .CreateCall(StackSave, {}, "savedstack");
01699 
01700     // Insert a call to llvm.stackrestore before any return instructions in the
01701     // inlined function.
01702     for (ReturnInst *RI : Returns) {
01703       // Don't insert llvm.stackrestore calls between a musttail call and a
01704       // return.  The return will restore the stack pointer.
01705       if (InlinedMustTailCalls && RI->getParent()->getTerminatingMustTailCall())
01706         continue;
01707       IRBuilder<>(RI).CreateCall(StackRestore, SavedPtr);
01708     }
01709   }
01710 
01711   // If we are inlining for an invoke instruction, we must make sure to rewrite
01712   // any call instructions into invoke instructions.  This is sensitive to which
01713   // funclet pads were top-level in the inlinee, so must be done before
01714   // rewriting the "parent pad" links.
01715   if (auto *II = dyn_cast<InvokeInst>(TheCall)) {
01716     BasicBlock *UnwindDest = II->getUnwindDest();
01717     Instruction *FirstNonPHI = UnwindDest->getFirstNonPHI();
01718     if (isa<LandingPadInst>(FirstNonPHI)) {
01719       HandleInlinedLandingPad(II, &*FirstNewBlock, InlinedFunctionInfo);
01720     } else {
01721       HandleInlinedEHPad(II, &*FirstNewBlock, InlinedFunctionInfo);
01722     }
01723   }
01724 
01725   // Update the lexical scopes of the new funclets and callsites.
01726   // Anything that had 'none' as its parent is now nested inside the callsite's
01727   // EHPad.
01728 
01729   if (CallSiteEHPad) {
01730     for (Function::iterator BB = FirstNewBlock->getIterator(),
01731                             E = Caller->end();
01732          BB != E; ++BB) {
01733       // Add bundle operands to any top-level call sites.
01734       SmallVector<OperandBundleDef, 1> OpBundles;
01735       for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;) {
01736         Instruction *I = &*BBI++;
01737         CallSite CS(I);
01738         if (!CS)
01739           continue;
01740 
01741         // Skip call sites which are nounwind intrinsics.
01742         auto *CalledFn =
01743             dyn_cast<Function>(CS.getCalledValue()->stripPointerCasts());
01744         if (CalledFn && CalledFn->isIntrinsic() && CS.doesNotThrow())
01745           continue;
01746 
01747         // Skip call sites which already have a "funclet" bundle.
01748         if (CS.getOperandBundle(LLVMContext::OB_funclet))
01749           continue;
01750 
01751         CS.getOperandBundlesAsDefs(OpBundles);
01752         OpBundles.emplace_back("funclet", CallSiteEHPad);
01753 
01754         Instruction *NewInst;
01755         if (CS.isCall())
01756           NewInst = CallInst::Create(cast<CallInst>(I), OpBundles, I);
01757         else
01758           NewInst = InvokeInst::Create(cast<InvokeInst>(I), OpBundles, I);
01759         NewInst->takeName(I);
01760         I->replaceAllUsesWith(NewInst);
01761         I->eraseFromParent();
01762 
01763         OpBundles.clear();
01764       }
01765 
01766       Instruction *I = BB->getFirstNonPHI();
01767       if (!I->isEHPad())
01768         continue;
01769 
01770       if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(I)) {
01771         if (isa<ConstantTokenNone>(CatchSwitch->getParentPad()))
01772           CatchSwitch->setParentPad(CallSiteEHPad);
01773       } else {
01774         auto *FPI = cast<FuncletPadInst>(I);
01775         if (isa<ConstantTokenNone>(FPI->getParentPad()))
01776           FPI->setParentPad(CallSiteEHPad);
01777       }
01778     }
01779   }
01780 
01781   // Handle any inlined musttail call sites.  In order for a new call site to be
01782   // musttail, the source of the clone and the inlined call site must have been
01783   // musttail.  Therefore it's safe to return without merging control into the
01784   // phi below.
01785   if (InlinedMustTailCalls) {
01786     // Check if we need to bitcast the result of any musttail calls.
01787     Type *NewRetTy = Caller->getReturnType();
01788     bool NeedBitCast = !TheCall->use_empty() && TheCall->getType() != NewRetTy;
01789 
01790     // Handle the returns preceded by musttail calls separately.
01791     SmallVector<ReturnInst *, 8> NormalReturns;
01792     for (ReturnInst *RI : Returns) {
01793       CallInst *ReturnedMustTail =
01794           RI->getParent()->getTerminatingMustTailCall();
01795       if (!ReturnedMustTail) {
01796         NormalReturns.push_back(RI);
01797         continue;
01798       }
01799       if (!NeedBitCast)
01800         continue;
01801 
01802       // Delete the old return and any preceding bitcast.
01803       BasicBlock *CurBB = RI->getParent();
01804       auto *OldCast = dyn_cast_or_null<BitCastInst>(RI->getReturnValue());
01805       RI->eraseFromParent();
01806       if (OldCast)
01807         OldCast->eraseFromParent();
01808 
01809       // Insert a new bitcast and return with the right type.
01810       IRBuilder<> Builder(CurBB);
01811       Builder.CreateRet(Builder.CreateBitCast(ReturnedMustTail, NewRetTy));
01812     }
01813 
01814     // Leave behind the normal returns so we can merge control flow.
01815     std::swap(Returns, NormalReturns);
01816   }
01817 
01818   // If we cloned in _exactly one_ basic block, and if that block ends in a
01819   // return instruction, we splice the body of the inlined callee directly into
01820   // the calling basic block.
01821   if (Returns.size() == 1 && std::distance(FirstNewBlock, Caller->end()) == 1) {
01822     // Move all of the instructions right before the call.
01823     OrigBB->getInstList().splice(TheCall->getIterator(),
01824                                  FirstNewBlock->getInstList(),
01825                                  FirstNewBlock->begin(), FirstNewBlock->end());
01826     // Remove the cloned basic block.
01827     Caller->getBasicBlockList().pop_back();
01828 
01829     // If the call site was an invoke instruction, add a branch to the normal
01830     // destination.
01831     if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) {
01832       BranchInst *NewBr = BranchInst::Create(II->getNormalDest(), TheCall);
01833       NewBr->setDebugLoc(Returns[0]->getDebugLoc());
01834     }
01835 
01836     // If the return instruction returned a value, replace uses of the call with
01837     // uses of the returned value.
01838     if (!TheCall->use_empty()) {
01839       ReturnInst *R = Returns[0];
01840       if (TheCall == R->getReturnValue())
01841         TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType()));
01842       else
01843         TheCall->replaceAllUsesWith(R->getReturnValue());
01844     }
01845     // Since we are now done with the Call/Invoke, we can delete it.
01846     TheCall->eraseFromParent();
01847 
01848     // Since we are now done with the return instruction, delete it also.
01849     Returns[0]->eraseFromParent();
01850 
01851     // We are now done with the inlining.
01852     return true;
01853   }
01854 
01855   // Otherwise, we have the normal case, of more than one block to inline or
01856   // multiple return sites.
01857 
01858   // We want to clone the entire callee function into the hole between the
01859   // "starter" and "ender" blocks.  How we accomplish this depends on whether
01860   // this is an invoke instruction or a call instruction.
01861   BasicBlock *AfterCallBB;
01862   BranchInst *CreatedBranchToNormalDest = nullptr;
01863   if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) {
01864 
01865     // Add an unconditional branch to make this look like the CallInst case...
01866     CreatedBranchToNormalDest = BranchInst::Create(II->getNormalDest(), TheCall);
01867 
01868     // Split the basic block.  This guarantees that no PHI nodes will have to be
01869     // updated due to new incoming edges, and make the invoke case more
01870     // symmetric to the call case.
01871     AfterCallBB =
01872         OrigBB->splitBasicBlock(CreatedBranchToNormalDest->getIterator(),
01873                                 CalledFunc->getName() + ".exit");
01874 
01875   } else {  // It's a call
01876     // If this is a call instruction, we need to split the basic block that
01877     // the call lives in.
01878     //
01879     AfterCallBB = OrigBB->splitBasicBlock(TheCall->getIterator(),
01880                                           CalledFunc->getName() + ".exit");
01881   }
01882 
01883   // Change the branch that used to go to AfterCallBB to branch to the first
01884   // basic block of the inlined function.
01885   //
01886   TerminatorInst *Br = OrigBB->getTerminator();
01887   assert(Br && Br->getOpcode() == Instruction::Br &&
01888          "splitBasicBlock broken!");
01889   Br->setOperand(0, &*FirstNewBlock);
01890 
01891   // Now that the function is correct, make it a little bit nicer.  In
01892   // particular, move the basic blocks inserted from the end of the function
01893   // into the space made by splitting the source basic block.
01894   Caller->getBasicBlockList().splice(AfterCallBB->getIterator(),
01895                                      Caller->getBasicBlockList(), FirstNewBlock,
01896                                      Caller->end());
01897 
01898   // Handle all of the return instructions that we just cloned in, and eliminate
01899   // any users of the original call/invoke instruction.
01900   Type *RTy = CalledFunc->getReturnType();
01901 
01902   PHINode *PHI = nullptr;
01903   if (Returns.size() > 1) {
01904     // The PHI node should go at the front of the new basic block to merge all
01905     // possible incoming values.
01906     if (!TheCall->use_empty()) {
01907       PHI = PHINode::Create(RTy, Returns.size(), TheCall->getName(),
01908                             &AfterCallBB->front());
01909       // Anything that used the result of the function call should now use the
01910       // PHI node as their operand.
01911       TheCall->replaceAllUsesWith(PHI);
01912     }
01913 
01914     // Loop over all of the return instructions adding entries to the PHI node
01915     // as appropriate.
01916     if (PHI) {
01917       for (unsigned i = 0, e = Returns.size(); i != e; ++i) {
01918         ReturnInst *RI = Returns[i];
01919         assert(RI->getReturnValue()->getType() == PHI->getType() &&
01920                "Ret value not consistent in function!");
01921         PHI->addIncoming(RI->getReturnValue(), RI->getParent());
01922       }
01923     }
01924 
01925     // Add a branch to the merge points and remove return instructions.
01926     DebugLoc Loc;
01927     for (unsigned i = 0, e = Returns.size(); i != e; ++i) {
01928       ReturnInst *RI = Returns[i];
01929       BranchInst* BI = BranchInst::Create(AfterCallBB, RI);
01930       Loc = RI->getDebugLoc();
01931       BI->setDebugLoc(Loc);
01932       RI->eraseFromParent();
01933     }
01934     // We need to set the debug location to *somewhere* inside the
01935     // inlined function. The line number may be nonsensical, but the
01936     // instruction will at least be associated with the right
01937     // function.
01938     if (CreatedBranchToNormalDest)
01939       CreatedBranchToNormalDest->setDebugLoc(Loc);
01940   } else if (!Returns.empty()) {
01941     // Otherwise, if there is exactly one return value, just replace anything
01942     // using the return value of the call with the computed value.
01943     if (!TheCall->use_empty()) {
01944       if (TheCall == Returns[0]->getReturnValue())
01945         TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType()));
01946       else
01947         TheCall->replaceAllUsesWith(Returns[0]->getReturnValue());
01948     }
01949 
01950     // Update PHI nodes that use the ReturnBB to use the AfterCallBB.
01951     BasicBlock *ReturnBB = Returns[0]->getParent();
01952     ReturnBB->replaceAllUsesWith(AfterCallBB);
01953 
01954     // Splice the code from the return block into the block that it will return
01955     // to, which contains the code that was after the call.
01956     AfterCallBB->getInstList().splice(AfterCallBB->begin(),
01957                                       ReturnBB->getInstList());
01958 
01959     if (CreatedBranchToNormalDest)
01960       CreatedBranchToNormalDest->setDebugLoc(Returns[0]->getDebugLoc());
01961 
01962     // Delete the return instruction now and empty ReturnBB now.
01963     Returns[0]->eraseFromParent();
01964     ReturnBB->eraseFromParent();
01965   } else if (!TheCall->use_empty()) {
01966     // No returns, but something is using the return value of the call.  Just
01967     // nuke the result.
01968     TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType()));
01969   }
01970 
01971   // Since we are now done with the Call/Invoke, we can delete it.
01972   TheCall->eraseFromParent();
01973 
01974   // If we inlined any musttail calls and the original return is now
01975   // unreachable, delete it.  It can only contain a bitcast and ret.
01976   if (InlinedMustTailCalls && pred_begin(AfterCallBB) == pred_end(AfterCallBB))
01977     AfterCallBB->eraseFromParent();
01978 
01979   // We should always be able to fold the entry block of the function into the
01980   // single predecessor of the block...
01981   assert(cast<BranchInst>(Br)->isUnconditional() && "splitBasicBlock broken!");
01982   BasicBlock *CalleeEntry = cast<BranchInst>(Br)->getSuccessor(0);
01983 
01984   // Splice the code entry block into calling block, right before the
01985   // unconditional branch.
01986   CalleeEntry->replaceAllUsesWith(OrigBB);  // Update PHI nodes
01987   OrigBB->getInstList().splice(Br->getIterator(), CalleeEntry->getInstList());
01988 
01989   // Remove the unconditional branch.
01990   OrigBB->getInstList().erase(Br);
01991 
01992   // Now we can remove the CalleeEntry block, which is now empty.
01993   Caller->getBasicBlockList().erase(CalleeEntry);
01994 
01995   // If we inserted a phi node, check to see if it has a single value (e.g. all
01996   // the entries are the same or undef).  If so, remove the PHI so it doesn't
01997   // block other optimizations.
01998   if (PHI) {
01999     auto &DL = Caller->getParent()->getDataLayout();
02000     if (Value *V = SimplifyInstruction(PHI, DL, nullptr, nullptr,
02001                                        &IFI.ACT->getAssumptionCache(*Caller))) {
02002       PHI->replaceAllUsesWith(V);
02003       PHI->eraseFromParent();
02004     }
02005   }
02006 
02007   return true;
02008 }