152419Sjulian//===- InlineFunction.cpp - Code to perform function inlining -------------===// 252419Sjulian// 352419Sjulian// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 452419Sjulian// See https://llvm.org/LICENSE.txt for license information. 552419Sjulian// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 652419Sjulian// 752419Sjulian//===----------------------------------------------------------------------===// 852419Sjulian// 952419Sjulian// This file implements inlining of a function into a call site, resolving 1052419Sjulian// parameters and the return value as appropriate. 1152419Sjulian// 1252419Sjulian//===----------------------------------------------------------------------===// 1352419Sjulian 1452419Sjulian#include "llvm/ADT/DenseMap.h" 1552419Sjulian#include "llvm/ADT/None.h" 1652419Sjulian#include "llvm/ADT/Optional.h" 1752419Sjulian#include "llvm/ADT/STLExtras.h" 1852419Sjulian#include "llvm/ADT/SetVector.h" 1952419Sjulian#include "llvm/ADT/SmallPtrSet.h" 2052419Sjulian#include "llvm/ADT/SmallVector.h" 2152419Sjulian#include "llvm/ADT/StringExtras.h" 2252419Sjulian#include "llvm/ADT/iterator_range.h" 2352419Sjulian#include "llvm/Analysis/AliasAnalysis.h" 2452419Sjulian#include "llvm/Analysis/AssumptionCache.h" 2552419Sjulian#include "llvm/Analysis/BlockFrequencyInfo.h" 2652419Sjulian#include "llvm/Analysis/CallGraph.h" 2752419Sjulian#include "llvm/Analysis/CaptureTracking.h" 2852419Sjulian#include "llvm/Analysis/EHPersonalities.h" 2952419Sjulian#include "llvm/Analysis/InstructionSimplify.h" 3052419Sjulian#include "llvm/Analysis/ProfileSummaryInfo.h" 3152419Sjulian#include "llvm/Transforms/Utils/Local.h" 3252419Sjulian#include "llvm/Analysis/ValueTracking.h" 3352419Sjulian#include "llvm/Analysis/VectorUtils.h" 3452419Sjulian#include "llvm/IR/Argument.h" 3552419Sjulian#include "llvm/IR/BasicBlock.h" 3652419Sjulian#include "llvm/IR/CFG.h" 3752419Sjulian#include "llvm/IR/CallSite.h" 3852419Sjulian#include "llvm/IR/Constant.h" 3952419Sjulian#include "llvm/IR/Constants.h" 4052419Sjulian#include "llvm/IR/DIBuilder.h" 4152419Sjulian#include "llvm/IR/DataLayout.h" 4252419Sjulian#include "llvm/IR/DebugInfoMetadata.h" 4352419Sjulian#include "llvm/IR/DebugLoc.h" 4452419Sjulian#include "llvm/IR/DerivedTypes.h" 4552419Sjulian#include "llvm/IR/Dominators.h" 4652419Sjulian#include "llvm/IR/Function.h" 4752419Sjulian#include "llvm/IR/IRBuilder.h" 4852419Sjulian#include "llvm/IR/InstrTypes.h" 4952419Sjulian#include "llvm/IR/Instruction.h" 5052419Sjulian#include "llvm/IR/Instructions.h" 5152419Sjulian#include "llvm/IR/IntrinsicInst.h" 5252419Sjulian#include "llvm/IR/Intrinsics.h" 5352419Sjulian#include "llvm/IR/LLVMContext.h" 5452419Sjulian#include "llvm/IR/MDBuilder.h" 5552419Sjulian#include "llvm/IR/Metadata.h" 5652419Sjulian#include "llvm/IR/Module.h" 5752843Sphk#include "llvm/IR/Type.h" 5852816Sarchie#include "llvm/IR/User.h" 5952419Sjulian#include "llvm/IR/Value.h" 6052419Sjulian#include "llvm/Support/Casting.h" 6152419Sjulian#include "llvm/Support/CommandLine.h" 6252419Sjulian#include "llvm/Support/ErrorHandling.h" 6352419Sjulian#include "llvm/Transforms/Utils/Cloning.h" 6453913Sarchie#include "llvm/Transforms/Utils/ValueMapper.h" 6552419Sjulian#include <algorithm> 6652419Sjulian#include <cassert> 6752419Sjulian#include <cstdint> 6852419Sjulian#include <iterator> 6952419Sjulian#include <limits> 7052419Sjulian#include <string> 7152419Sjulian#include <utility> 7252722Sjulian#include <vector> 7352722Sjulian 7452722Sjulianusing namespace llvm; 7552722Sjulianusing ProfileCount = Function::ProfileCount; 7652722Sjulian 7752419Sjulianstatic cl::opt<bool> 7852419SjulianEnableNoAliasConversion("enable-noalias-to-md-conversion", cl::init(true), 7952419Sjulian cl::Hidden, 8052419Sjulian cl::desc("Convert noalias attributes to metadata during inlining.")); 8152419Sjulian 8259728Sjulianstatic cl::opt<bool> 8359728SjulianPreserveAlignmentAssumptions("preserve-alignment-assumptions-during-inlining", 8452722Sjulian cl::init(true), cl::Hidden, 8552419Sjulian cl::desc("Convert align attributes to assumptions during inlining.")); 8652419Sjulian 8752419Sjulianllvm::InlineResult llvm::InlineFunction(CallBase *CB, InlineFunctionInfo &IFI, 8852419Sjulian AAResults *CalleeAAR, 8952419Sjulian bool InsertLifetime) { 9052419Sjulian return InlineFunction(CallSite(CB), IFI, CalleeAAR, InsertLifetime); 9152419Sjulian} 9252419Sjulian 9352419Sjuliannamespace { 9452419Sjulian 9552419Sjulian /// A class for recording information about inlining a landing pad. 9652722Sjulian class LandingPadInliningInfo { 9752722Sjulian /// Destination of the invoke's unwind. 9853403Sarchie BasicBlock *OuterResumeDest; 9953403Sarchie 10053403Sarchie /// Destination for the callee's resume. 10153403Sarchie BasicBlock *InnerResumeDest = nullptr; 10253403Sarchie 10353403Sarchie /// LandingPadInst associated with the invoke. 10453403Sarchie LandingPadInst *CallerLPad = nullptr; 10553403Sarchie 10653403Sarchie /// PHI for EH values from landingpad insts. 10753403Sarchie PHINode *InnerEHValuesPHI = nullptr; 10853403Sarchie 10953403Sarchie SmallVector<Value*, 8> UnwindDestPHIValues; 11053403Sarchie 11153403Sarchie public: 11253403Sarchie LandingPadInliningInfo(InvokeInst *II) 11353403Sarchie : OuterResumeDest(II->getUnwindDest()) { 11453403Sarchie // If there are PHI nodes in the unwind destination block, we need to keep 11552722Sjulian // track of which values came into them from the invoke before removing 11653403Sarchie // the edge from this block. 11752419Sjulian BasicBlock *InvokeBB = II->getParent(); 11853913Sarchie BasicBlock::iterator I = OuterResumeDest->begin(); 11953913Sarchie for (; isa<PHINode>(I); ++I) { 12053913Sarchie // Save the value to use for this edge. 12153913Sarchie PHINode *PHI = cast<PHINode>(I); 12253913Sarchie UnwindDestPHIValues.push_back(PHI->getIncomingValueForBlock(InvokeBB)); 12353913Sarchie } 12453913Sarchie 12553913Sarchie CallerLPad = cast<LandingPadInst>(I); 12653913Sarchie } 12753913Sarchie 12853913Sarchie /// The outer unwind destination is the target of 12953913Sarchie /// unwind edges introduced for calls within the inlined function. 13053913Sarchie BasicBlock *getOuterResumeDest() const { 13153913Sarchie return OuterResumeDest; 13253913Sarchie } 13353913Sarchie 13453913Sarchie BasicBlock *getInnerResumeDest(); 13553913Sarchie 13653913Sarchie LandingPadInst *getLandingPadInst() const { return CallerLPad; } 13753913Sarchie 13853913Sarchie /// Forward the 'resume' instruction to the caller's landing pad block. 13953913Sarchie /// When the landing pad block has only one predecessor, this is 14053913Sarchie /// a simple branch. When there is more than one predecessor, we need to 14153913Sarchie /// split the landing pad block after the landingpad instruction and jump 14253913Sarchie /// to there. 14353913Sarchie void forwardResume(ResumeInst *RI, 14453913Sarchie SmallPtrSetImpl<LandingPadInst*> &InlinedLPads); 14553913Sarchie 14653913Sarchie /// Add incoming-PHI values to the unwind destination block for the given 14753913Sarchie /// basic block, using the values for the original invoke's source block. 14853913Sarchie void addIncomingPHIValuesFor(BasicBlock *BB) const { 14953913Sarchie addIncomingPHIValuesForInto(BB, OuterResumeDest); 15053913Sarchie } 15153913Sarchie 15253913Sarchie void addIncomingPHIValuesForInto(BasicBlock *src, BasicBlock *dest) const { 15353913Sarchie BasicBlock::iterator I = dest->begin(); 15453913Sarchie for (unsigned i = 0, e = UnwindDestPHIValues.size(); i != e; ++i, ++I) { 15553913Sarchie PHINode *phi = cast<PHINode>(I); 15653913Sarchie phi->addIncoming(UnwindDestPHIValues[i], src); 15753913Sarchie } 15853913Sarchie } 15953913Sarchie }; 16053913Sarchie 16153913Sarchie} // end anonymous namespace 16253913Sarchie 16353913Sarchie/// Get or create a target for the branch from ResumeInsts. 16453913SarchieBasicBlock *LandingPadInliningInfo::getInnerResumeDest() { 16553913Sarchie if (InnerResumeDest) return InnerResumeDest; 16653913Sarchie 16753913Sarchie // Split the landing pad. 16853913Sarchie BasicBlock::iterator SplitPoint = ++CallerLPad->getIterator(); 16953913Sarchie InnerResumeDest = 17053913Sarchie OuterResumeDest->splitBasicBlock(SplitPoint, 17153913Sarchie OuterResumeDest->getName() + ".body"); 17253913Sarchie 17353913Sarchie // The number of incoming edges we expect to the inner landing pad. 17453913Sarchie const unsigned PHICapacity = 2; 17553913Sarchie 17653913Sarchie // Create corresponding new PHIs for all the PHIs in the outer landing pad. 17753913Sarchie Instruction *InsertPoint = &InnerResumeDest->front(); 17853913Sarchie BasicBlock::iterator I = OuterResumeDest->begin(); 17953913Sarchie for (unsigned i = 0, e = UnwindDestPHIValues.size(); i != e; ++i, ++I) { 18053913Sarchie PHINode *OuterPHI = cast<PHINode>(I); 18153913Sarchie PHINode *InnerPHI = PHINode::Create(OuterPHI->getType(), PHICapacity, 18253913Sarchie OuterPHI->getName() + ".lpad-body", 18353913Sarchie InsertPoint); 18453913Sarchie OuterPHI->replaceAllUsesWith(InnerPHI); 18553913Sarchie InnerPHI->addIncoming(OuterPHI, OuterResumeDest); 18653913Sarchie } 18753913Sarchie 18853913Sarchie // Create a PHI for the exception values. 18953913Sarchie InnerEHValuesPHI = PHINode::Create(CallerLPad->getType(), PHICapacity, 19053913Sarchie "eh.lpad-body", InsertPoint); 19153913Sarchie CallerLPad->replaceAllUsesWith(InnerEHValuesPHI); 19253913Sarchie InnerEHValuesPHI->addIncoming(CallerLPad, OuterResumeDest); 19353913Sarchie 19453913Sarchie // All done. 19553913Sarchie return InnerResumeDest; 19653913Sarchie} 19753913Sarchie 19853913Sarchie/// Forward the 'resume' instruction to the caller's landing pad block. 19953913Sarchie/// When the landing pad block has only one predecessor, this is a simple 20053913Sarchie/// branch. When there is more than one predecessor, we need to split the 20153913Sarchie/// landing pad block after the landingpad instruction and jump to there. 20253913Sarchievoid LandingPadInliningInfo::forwardResume( 20353913Sarchie ResumeInst *RI, SmallPtrSetImpl<LandingPadInst *> &InlinedLPads) { 20453913Sarchie BasicBlock *Dest = getInnerResumeDest(); 20553913Sarchie BasicBlock *Src = RI->getParent(); 20653913Sarchie 20753913Sarchie BranchInst::Create(Dest, Src); 20853913Sarchie 20953913Sarchie // Update the PHIs in the destination. They were inserted in an order which 21053913Sarchie // makes this work. 21153913Sarchie addIncomingPHIValuesForInto(Src, Dest); 21253913Sarchie 21353913Sarchie InnerEHValuesPHI->addIncoming(RI->getOperand(0), Src); 21453913Sarchie RI->eraseFromParent(); 21553913Sarchie} 21653913Sarchie 21753913Sarchie/// Helper for getUnwindDestToken/getUnwindDestTokenHelper. 21853913Sarchiestatic Value *getParentPad(Value *EHPad) { 21953913Sarchie if (auto *FPI = dyn_cast<FuncletPadInst>(EHPad)) 22053913Sarchie return FPI->getParentPad(); 22153913Sarchie return cast<CatchSwitchInst>(EHPad)->getParentPad(); 22253913Sarchie} 22353913Sarchie 22453913Sarchieusing UnwindDestMemoTy = DenseMap<Instruction *, Value *>; 22553913Sarchie 22653913Sarchie/// Helper for getUnwindDestToken that does the descendant-ward part of 22753913Sarchie/// the search. 22853913Sarchiestatic Value *getUnwindDestTokenHelper(Instruction *EHPad, 22953913Sarchie UnwindDestMemoTy &MemoMap) { 23053913Sarchie SmallVector<Instruction *, 8> Worklist(1, EHPad); 23153913Sarchie 23253913Sarchie while (!Worklist.empty()) { 23353913Sarchie Instruction *CurrentPad = Worklist.pop_back_val(); 23453913Sarchie // We only put pads on the worklist that aren't in the MemoMap. When 23553913Sarchie // we find an unwind dest for a pad we may update its ancestors, but 23653913Sarchie // the queue only ever contains uncles/great-uncles/etc. of CurrentPad, 23753913Sarchie // so they should never get updated while queued on the worklist. 23853913Sarchie assert(!MemoMap.count(CurrentPad)); 23953913Sarchie Value *UnwindDestToken = nullptr; 24053913Sarchie if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(CurrentPad)) { 24153913Sarchie if (CatchSwitch->hasUnwindDest()) { 24253913Sarchie UnwindDestToken = CatchSwitch->getUnwindDest()->getFirstNonPHI(); 24353913Sarchie } else { 24453913Sarchie // Catchswitch doesn't have a 'nounwind' variant, and one might be 24553913Sarchie // annotated as "unwinds to caller" when really it's nounwind (see 24653913Sarchie // e.g. SimplifyCFGOpt::SimplifyUnreachable), so we can't infer the 24753913Sarchie // parent's unwind dest from this. We can check its catchpads' 24853913Sarchie // descendants, since they might include a cleanuppad with an 24953913Sarchie // "unwinds to caller" cleanupret, which can be trusted. 25053913Sarchie for (auto HI = CatchSwitch->handler_begin(), 25153913Sarchie HE = CatchSwitch->handler_end(); 25253913Sarchie HI != HE && !UnwindDestToken; ++HI) { 25353913Sarchie BasicBlock *HandlerBlock = *HI; 25453913Sarchie auto *CatchPad = cast<CatchPadInst>(HandlerBlock->getFirstNonPHI()); 25553913Sarchie for (User *Child : CatchPad->users()) { 25653913Sarchie // Intentionally ignore invokes here -- since the catchswitch is 25753913Sarchie // marked "unwind to caller", it would be a verifier error if it 25853913Sarchie // contained an invoke which unwinds out of it, so any invoke we'd 25953913Sarchie // encounter must unwind to some child of the catch. 26053913Sarchie if (!isa<CleanupPadInst>(Child) && !isa<CatchSwitchInst>(Child)) 26153913Sarchie continue; 26253913Sarchie 26353913Sarchie Instruction *ChildPad = cast<Instruction>(Child); 26453913Sarchie auto Memo = MemoMap.find(ChildPad); 26553913Sarchie if (Memo == MemoMap.end()) { 26653913Sarchie // Haven't figured out this child pad yet; queue it. 26753913Sarchie Worklist.push_back(ChildPad); 26853913Sarchie continue; 26953913Sarchie } 27053913Sarchie // We've already checked this child, but might have found that 27153913Sarchie // it offers no proof either way. 27253913Sarchie Value *ChildUnwindDestToken = Memo->second; 27353913Sarchie if (!ChildUnwindDestToken) 27453913Sarchie continue; 27553913Sarchie // We already know the child's unwind dest, which can either 27653913Sarchie // be ConstantTokenNone to indicate unwind to caller, or can 27753913Sarchie // be another child of the catchpad. Only the former indicates 27853913Sarchie // the unwind dest of the catchswitch. 27953913Sarchie if (isa<ConstantTokenNone>(ChildUnwindDestToken)) { 28053913Sarchie UnwindDestToken = ChildUnwindDestToken; 28153913Sarchie break; 28253913Sarchie } 28353913Sarchie assert(getParentPad(ChildUnwindDestToken) == CatchPad); 28453913Sarchie } 28553913Sarchie } 28653913Sarchie } 28753913Sarchie } else { 28853913Sarchie auto *CleanupPad = cast<CleanupPadInst>(CurrentPad); 28953913Sarchie for (User *U : CleanupPad->users()) { 29053913Sarchie if (auto *CleanupRet = dyn_cast<CleanupReturnInst>(U)) { 29152419Sjulian if (BasicBlock *RetUnwindDest = CleanupRet->getUnwindDest()) 29252419Sjulian UnwindDestToken = RetUnwindDest->getFirstNonPHI(); 29352419Sjulian else 29452419Sjulian UnwindDestToken = ConstantTokenNone::get(CleanupPad->getContext()); 29552419Sjulian break; 29652419Sjulian } 29752419Sjulian Value *ChildUnwindDestToken; 29852419Sjulian if (auto *Invoke = dyn_cast<InvokeInst>(U)) { 29952419Sjulian ChildUnwindDestToken = Invoke->getUnwindDest()->getFirstNonPHI(); 30052419Sjulian } else if (isa<CleanupPadInst>(U) || isa<CatchSwitchInst>(U)) { 30152419Sjulian Instruction *ChildPad = cast<Instruction>(U); 30252419Sjulian auto Memo = MemoMap.find(ChildPad); 30352419Sjulian if (Memo == MemoMap.end()) { 30452419Sjulian // Haven't resolved this child yet; queue it and keep searching. 30552419Sjulian Worklist.push_back(ChildPad); 30652419Sjulian continue; 30752419Sjulian } 30852419Sjulian // We've checked this child, but still need to ignore it if it 30952419Sjulian // had no proof either way. 31052419Sjulian ChildUnwindDestToken = Memo->second; 31152419Sjulian if (!ChildUnwindDestToken) 31252419Sjulian continue; 31352419Sjulian } else { 31452419Sjulian // Not a relevant user of the cleanuppad 31552419Sjulian continue; 31652419Sjulian } 31752419Sjulian // In a well-formed program, the child/invoke must either unwind to 31852419Sjulian // an(other) child of the cleanup, or exit the cleanup. In the 31952419Sjulian // first case, continue searching. 32052419Sjulian if (isa<Instruction>(ChildUnwindDestToken) && 32152419Sjulian getParentPad(ChildUnwindDestToken) == CleanupPad) 32252419Sjulian continue; 32352419Sjulian UnwindDestToken = ChildUnwindDestToken; 32452419Sjulian break; 32552419Sjulian } 32652419Sjulian } 32752419Sjulian // If we haven't found an unwind dest for CurrentPad, we may have queued its 32852419Sjulian // children, so move on to the next in the worklist. 32952419Sjulian if (!UnwindDestToken) 33052419Sjulian continue; 33152419Sjulian 33252419Sjulian // Now we know that CurrentPad unwinds to UnwindDestToken. It also exits 33352419Sjulian // any ancestors of CurrentPad up to but not including UnwindDestToken's 33452419Sjulian // parent pad. Record this in the memo map, and check to see if the 33552419Sjulian // original EHPad being queried is one of the ones exited. 33652419Sjulian Value *UnwindParent; 33752419Sjulian if (auto *UnwindPad = dyn_cast<Instruction>(UnwindDestToken)) 33852419Sjulian UnwindParent = getParentPad(UnwindPad); 33952419Sjulian else 34052419Sjulian UnwindParent = nullptr; 34152419Sjulian bool ExitedOriginalPad = false; 34252419Sjulian for (Instruction *ExitedPad = CurrentPad; 34352419Sjulian ExitedPad && ExitedPad != UnwindParent; 34452419Sjulian ExitedPad = dyn_cast<Instruction>(getParentPad(ExitedPad))) { 34552419Sjulian // Skip over catchpads since they just follow their catchswitches. 34652419Sjulian if (isa<CatchPadInst>(ExitedPad)) 34752419Sjulian continue; 34852419Sjulian MemoMap[ExitedPad] = UnwindDestToken; 34952419Sjulian ExitedOriginalPad |= (ExitedPad == EHPad); 35052419Sjulian } 35152419Sjulian 35252419Sjulian if (ExitedOriginalPad) 35352419Sjulian return UnwindDestToken; 35452419Sjulian 35552419Sjulian // Continue the search. 35652419Sjulian } 35752419Sjulian 35852419Sjulian // No definitive information is contained within this funclet. 35952419Sjulian return nullptr; 36052419Sjulian} 36152419Sjulian 36252419Sjulian/// Given an EH pad, find where it unwinds. If it unwinds to an EH pad, 36352419Sjulian/// return that pad instruction. If it unwinds to caller, return 36452419Sjulian/// ConstantTokenNone. If it does not have a definitive unwind destination, 36552419Sjulian/// return nullptr. 36652419Sjulian/// 36752419Sjulian/// This routine gets invoked for calls in funclets in inlinees when inlining 36852722Sjulian/// an invoke. Since many funclets don't have calls inside them, it's queried 36952722Sjulian/// on-demand rather than building a map of pads to unwind dests up front. 37052722Sjulian/// Determining a funclet's unwind dest may require recursively searching its 37152722Sjulian/// descendants, and also ancestors and cousins if the descendants don't provide 37252419Sjulian/// an answer. Since most funclets will have their unwind dest immediately 37352419Sjulian/// available as the unwind dest of a catchswitch or cleanupret, this routine 37452419Sjulian/// searches top-down from the given pad and then up. To avoid worst-case 37552419Sjulian/// quadratic run-time given that approach, it uses a memo map to avoid 37652419Sjulian/// re-processing funclet trees. The callers that rewrite the IR as they go 37752419Sjulian/// take advantage of this, for correctness, by checking/forcing rewritten 37852419Sjulian/// pads' entries to match the original callee view. 37952419Sjulianstatic Value *getUnwindDestToken(Instruction *EHPad, 38052419Sjulian UnwindDestMemoTy &MemoMap) { 38152419Sjulian // Catchpads unwind to the same place as their catchswitch; 38252419Sjulian // redirct any queries on catchpads so the code below can 38352419Sjulian // deal with just catchswitches and cleanuppads. 38452419Sjulian if (auto *CPI = dyn_cast<CatchPadInst>(EHPad)) 38552419Sjulian EHPad = CPI->getCatchSwitch(); 38652419Sjulian 38752419Sjulian // Check if we've already determined the unwind dest for this pad. 38852419Sjulian auto Memo = MemoMap.find(EHPad); 38952419Sjulian if (Memo != MemoMap.end()) 39052419Sjulian return Memo->second; 39152419Sjulian 39252419Sjulian // Search EHPad and, if necessary, its descendants. 39352419Sjulian Value *UnwindDestToken = getUnwindDestTokenHelper(EHPad, MemoMap); 39452419Sjulian assert((UnwindDestToken == nullptr) != (MemoMap.count(EHPad) != 0)); 39552419Sjulian if (UnwindDestToken) 39652419Sjulian return UnwindDestToken; 39752419Sjulian 39852419Sjulian // No information is available for this EHPad from itself or any of its 39952419Sjulian // descendants. An unwind all the way out to a pad in the caller would 40052419Sjulian // need also to agree with the unwind dest of the parent funclet, so 40152419Sjulian // search up the chain to try to find a funclet with information. Put 40252419Sjulian // null entries in the memo map to avoid re-processing as we go up. 40352419Sjulian MemoMap[EHPad] = nullptr; 40452419Sjulian#ifndef NDEBUG 40552419Sjulian SmallPtrSet<Instruction *, 4> TempMemos; 40652419Sjulian TempMemos.insert(EHPad); 40752419Sjulian#endif 40852419Sjulian Instruction *LastUselessPad = EHPad; 40952419Sjulian Value *AncestorToken; 41052419Sjulian for (AncestorToken = getParentPad(EHPad); 41152419Sjulian auto *AncestorPad = dyn_cast<Instruction>(AncestorToken); 41252419Sjulian AncestorToken = getParentPad(AncestorToken)) { 41352419Sjulian // Skip over catchpads since they just follow their catchswitches. 41452419Sjulian if (isa<CatchPadInst>(AncestorPad)) 41552419Sjulian continue; 41652419Sjulian // If the MemoMap had an entry mapping AncestorPad to nullptr, since we 41752419Sjulian // haven't yet called getUnwindDestTokenHelper for AncestorPad in this 41852419Sjulian // call to getUnwindDestToken, that would mean that AncestorPad had no 41952419Sjulian // information in itself, its descendants, or its ancestors. If that 42052419Sjulian // were the case, then we should also have recorded the lack of information 42152419Sjulian // for the descendant that we're coming from. So assert that we don't 42252419Sjulian // find a null entry in the MemoMap for AncestorPad. 42352419Sjulian assert(!MemoMap.count(AncestorPad) || MemoMap[AncestorPad]); 42452419Sjulian auto AncestorMemo = MemoMap.find(AncestorPad); 42552419Sjulian if (AncestorMemo == MemoMap.end()) { 42652419Sjulian UnwindDestToken = getUnwindDestTokenHelper(AncestorPad, MemoMap); 42752419Sjulian } else { 42852419Sjulian UnwindDestToken = AncestorMemo->second; 42952419Sjulian } 43052419Sjulian if (UnwindDestToken) 43152419Sjulian break; 43252419Sjulian LastUselessPad = AncestorPad; 43352419Sjulian MemoMap[LastUselessPad] = nullptr; 43452419Sjulian#ifndef NDEBUG 43552419Sjulian TempMemos.insert(LastUselessPad); 43652419Sjulian#endif 43752419Sjulian } 43852419Sjulian 43952419Sjulian // We know that getUnwindDestTokenHelper was called on LastUselessPad and 44052722Sjulian // returned nullptr (and likewise for EHPad and any of its ancestors up to 44152419Sjulian // LastUselessPad), so LastUselessPad has no information from below. Since 44252419Sjulian // getUnwindDestTokenHelper must investigate all downward paths through 44352419Sjulian // no-information nodes to prove that a node has no information like this, 44452419Sjulian // and since any time it finds information it records it in the MemoMap for 44552419Sjulian // not just the immediately-containing funclet but also any ancestors also 44652419Sjulian // exited, it must be the case that, walking downward from LastUselessPad, 44752419Sjulian // visiting just those nodes which have not been mapped to an unwind dest 44852419Sjulian // by getUnwindDestTokenHelper (the nullptr TempMemos notwithstanding, since 44952419Sjulian // they are just used to keep getUnwindDestTokenHelper from repeating work), 45052419Sjulian // any node visited must have been exhaustively searched with no information 45152419Sjulian // for it found. 45252419Sjulian SmallVector<Instruction *, 8> Worklist(1, LastUselessPad); 45352419Sjulian while (!Worklist.empty()) { 45452419Sjulian Instruction *UselessPad = Worklist.pop_back_val(); 45552419Sjulian auto Memo = MemoMap.find(UselessPad); 45652419Sjulian if (Memo != MemoMap.end() && Memo->second) { 45752419Sjulian // Here the name 'UselessPad' is a bit of a misnomer, because we've found 45852419Sjulian // that it is a funclet that does have information about unwinding to 45952419Sjulian // a particular destination; its parent was a useless pad. 46052419Sjulian // Since its parent has no information, the unwind edge must not escape 46152419Sjulian // the parent, and must target a sibling of this pad. This local unwind 46252419Sjulian // gives us no information about EHPad. Leave it and the subtree rooted 46352419Sjulian // at it alone. 46452419Sjulian assert(getParentPad(Memo->second) == getParentPad(UselessPad)); 46552419Sjulian continue; 46653403Sarchie } 46753403Sarchie // We know we don't have information for UselesPad. If it has an entry in 46852419Sjulian // the MemoMap (mapping it to nullptr), it must be one of the TempMemos 46952419Sjulian // added on this invocation of getUnwindDestToken; if a previous invocation 47052419Sjulian // recorded nullptr, it would have had to prove that the ancestors of 47152419Sjulian // UselessPad, which include LastUselessPad, had no information, and that 47252419Sjulian // in turn would have required proving that the descendants of 47352419Sjulian // LastUselesPad, which include EHPad, have no information about 47452419Sjulian // LastUselessPad, which would imply that EHPad was mapped to nullptr in 47552419Sjulian // the MemoMap on that invocation, which isn't the case if we got here. 47652419Sjulian assert(!MemoMap.count(UselessPad) || TempMemos.count(UselessPad)); 47752419Sjulian // Assert as we enumerate users that 'UselessPad' doesn't have any unwind 47852419Sjulian // information that we'd be contradicting by making a map entry for it 47952419Sjulian // (which is something that getUnwindDestTokenHelper must have proved for 48052419Sjulian // us to get here). Just assert on is direct users here; the checks in 48152419Sjulian // this downward walk at its descendants will verify that they don't have 48252419Sjulian // any unwind edges that exit 'UselessPad' either (i.e. they either have no 48352419Sjulian // unwind edges or unwind to a sibling). 48452419Sjulian MemoMap[UselessPad] = UnwindDestToken; 48552419Sjulian if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(UselessPad)) { 48652419Sjulian assert(CatchSwitch->getUnwindDest() == nullptr && "Expected useless pad"); 48752419Sjulian for (BasicBlock *HandlerBlock : CatchSwitch->handlers()) { 48852419Sjulian auto *CatchPad = HandlerBlock->getFirstNonPHI(); 48952419Sjulian for (User *U : CatchPad->users()) { 49052419Sjulian assert( 49152419Sjulian (!isa<InvokeInst>(U) || 49252419Sjulian (getParentPad( 49352419Sjulian cast<InvokeInst>(U)->getUnwindDest()->getFirstNonPHI()) == 49452419Sjulian CatchPad)) && 49552419Sjulian "Expected useless pad"); 49652722Sjulian if (isa<CatchSwitchInst>(U) || isa<CleanupPadInst>(U)) 49752722Sjulian Worklist.push_back(cast<Instruction>(U)); 49852722Sjulian } 49952722Sjulian } 50052722Sjulian } else { 50152722Sjulian assert(isa<CleanupPadInst>(UselessPad)); 50252722Sjulian for (User *U : UselessPad->users()) { 50352722Sjulian assert(!isa<CleanupReturnInst>(U) && "Expected useless pad"); 50452722Sjulian assert((!isa<InvokeInst>(U) || 50552722Sjulian (getParentPad( 50652722Sjulian cast<InvokeInst>(U)->getUnwindDest()->getFirstNonPHI()) == 50752722Sjulian UselessPad)) && 50852722Sjulian "Expected useless pad"); 50952722Sjulian if (isa<CatchSwitchInst>(U) || isa<CleanupPadInst>(U)) 51052722Sjulian Worklist.push_back(cast<Instruction>(U)); 51152722Sjulian } 51252722Sjulian } 51352722Sjulian } 51452722Sjulian 51552722Sjulian return UnwindDestToken; 51652419Sjulian} 51752419Sjulian 51852419Sjulian/// When we inline a basic block into an invoke, 51952419Sjulian/// we have to turn all of the calls that can throw into invokes. 52052419Sjulian/// This function analyze BB to see if there are any calls, and if so, 52152419Sjulian/// it rewrites them to be invokes that jump to InvokeDest and fills in the PHI 52252419Sjulian/// nodes in that block with the values specified in InvokeDestPHIValues. 52352419Sjulianstatic BasicBlock *HandleCallsInBlockInlinedThroughInvoke( 52452419Sjulian BasicBlock *BB, BasicBlock *UnwindEdge, 52552419Sjulian UnwindDestMemoTy *FuncletUnwindMap = nullptr) { 52652419Sjulian for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) { 52752419Sjulian Instruction *I = &*BBI++; 52852419Sjulian 52952419Sjulian // We only need to check for function calls: inlined invoke 53052419Sjulian // instructions require no special handling. 53152419Sjulian CallInst *CI = dyn_cast<CallInst>(I); 53252419Sjulian 53352419Sjulian if (!CI || CI->doesNotThrow() || isa<InlineAsm>(CI->getCalledValue())) 53452419Sjulian continue; 53552419Sjulian 53652722Sjulian // We do not need to (and in fact, cannot) convert possibly throwing calls 53752419Sjulian // to @llvm.experimental_deoptimize (resp. @llvm.experimental.guard) into 53852419Sjulian // invokes. The caller's "segment" of the deoptimization continuation 53952419Sjulian // attached to the newly inlined @llvm.experimental_deoptimize 54052419Sjulian // (resp. @llvm.experimental.guard) call should contain the exception 54152419Sjulian // handling logic, if any. 54252419Sjulian if (auto *F = CI->getCalledFunction()) 54352419Sjulian if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize || 54452419Sjulian F->getIntrinsicID() == Intrinsic::experimental_guard) 54552419Sjulian continue; 54652419Sjulian 54752419Sjulian if (auto FuncletBundle = CI->getOperandBundle(LLVMContext::OB_funclet)) { 54852419Sjulian // This call is nested inside a funclet. If that funclet has an unwind 54952419Sjulian // destination within the inlinee, then unwinding out of this call would 55052419Sjulian // be UB. Rewriting this call to an invoke which targets the inlined 55152419Sjulian // invoke's unwind dest would give the call's parent funclet multiple 55252419Sjulian // unwind destinations, which is something that subsequent EH table 55352419Sjulian // generation can't handle and that the veirifer rejects. So when we 55452419Sjulian // see such a call, leave it as a call. 55552419Sjulian auto *FuncletPad = cast<Instruction>(FuncletBundle->Inputs[0]); 55652419Sjulian Value *UnwindDestToken = 55752419Sjulian getUnwindDestToken(FuncletPad, *FuncletUnwindMap); 55852419Sjulian if (UnwindDestToken && !isa<ConstantTokenNone>(UnwindDestToken)) 55952419Sjulian continue; 56052419Sjulian#ifndef NDEBUG 56152419Sjulian Instruction *MemoKey; 56252419Sjulian if (auto *CatchPad = dyn_cast<CatchPadInst>(FuncletPad)) 56352419Sjulian MemoKey = CatchPad->getCatchSwitch(); 56452419Sjulian else 56552419Sjulian MemoKey = FuncletPad; 56652419Sjulian assert(FuncletUnwindMap->count(MemoKey) && 56752419Sjulian (*FuncletUnwindMap)[MemoKey] == UnwindDestToken && 56852419Sjulian "must get memoized to avoid confusing later searches"); 56952419Sjulian#endif // NDEBUG 57052419Sjulian } 57152419Sjulian 57252419Sjulian changeToInvokeAndSplitBasicBlock(CI, UnwindEdge); 57352419Sjulian return BB; 57452419Sjulian } 57552419Sjulian return nullptr; 57652722Sjulian} 57752722Sjulian 57852419Sjulian/// If we inlined an invoke site, we need to convert calls 57952419Sjulian/// in the body of the inlined function into invokes. 58052419Sjulian/// 58152419Sjulian/// II is the invoke instruction being inlined. FirstNewBlock is the first 58252419Sjulian/// block of the inlined code (the last block is the end of the function), 58352419Sjulian/// and InlineCodeInfo is information about the code that got inlined. 58452722Sjulianstatic void HandleInlinedLandingPad(InvokeInst *II, BasicBlock *FirstNewBlock, 58552722Sjulian ClonedCodeInfo &InlinedCodeInfo) { 58652419Sjulian BasicBlock *InvokeDest = II->getUnwindDest(); 58752419Sjulian 58852419Sjulian Function *Caller = FirstNewBlock->getParent(); 58952419Sjulian 59052419Sjulian // The inlined code is currently at the end of the function, scan from the 59152419Sjulian // start of the inlined code to its end, checking for stuff we need to 59252419Sjulian // rewrite. 59352419Sjulian LandingPadInliningInfo Invoke(II); 59452419Sjulian 59552419Sjulian // Get all of the inlined landing pad instructions. 59652419Sjulian SmallPtrSet<LandingPadInst*, 16> InlinedLPads; 59752722Sjulian for (Function::iterator I = FirstNewBlock->getIterator(), E = Caller->end(); 59852722Sjulian I != E; ++I) 59952419Sjulian if (InvokeInst *II = dyn_cast<InvokeInst>(I->getTerminator())) 60052722Sjulian InlinedLPads.insert(II->getLandingPadInst()); 60152419Sjulian 60252419Sjulian // Append the clauses from the outer landing pad instruction into the inlined 60352816Sarchie // landing pad instructions. 60453648Sarchie LandingPadInst *OuterLPad = Invoke.getLandingPadInst(); 60552816Sarchie for (LandingPadInst *InlinedLPad : InlinedLPads) { 60652419Sjulian unsigned OuterNum = OuterLPad->getNumClauses(); 60752816Sarchie InlinedLPad->reserveClauses(OuterNum); 60852816Sarchie for (unsigned OuterIdx = 0; OuterIdx != OuterNum; ++OuterIdx) 60952951Sjulian InlinedLPad->addClause(OuterLPad->getClause(OuterIdx)); 61052816Sarchie if (OuterLPad->isCleanup()) 61152419Sjulian InlinedLPad->setCleanup(true); 61252816Sarchie } 61352816Sarchie 61452951Sjulian for (Function::iterator BB = FirstNewBlock->getIterator(), E = Caller->end(); 61553042Sjulian BB != E; ++BB) { 61652816Sarchie if (InlinedCodeInfo.ContainsCalls) 61752419Sjulian if (BasicBlock *NewBB = HandleCallsInBlockInlinedThroughInvoke( 61852419Sjulian &*BB, Invoke.getOuterResumeDest())) 61952419Sjulian // Update any PHI nodes in the exceptional block to indicate that there 62052419Sjulian // is now a new entry in them. 62152419Sjulian Invoke.addIncomingPHIValuesFor(NewBB); 62252419Sjulian 62352419Sjulian // Forward any resumes that are remaining here. 62452419Sjulian if (ResumeInst *RI = dyn_cast<ResumeInst>(BB->getTerminator())) 62552419Sjulian Invoke.forwardResume(RI, InlinedLPads); 62652419Sjulian } 62752419Sjulian 62852419Sjulian // Now that everything is happy, we have one final detail. The PHI nodes in 62952419Sjulian // the exception destination block still have entries due to the original 63052419Sjulian // invoke instruction. Eliminate these entries (which might even delete the 63152419Sjulian // PHI node) now. 63252419Sjulian InvokeDest->removePredecessor(II->getParent()); 63352419Sjulian} 63452419Sjulian 63552419Sjulian/// If we inlined an invoke site, we need to convert calls 63652419Sjulian/// in the body of the inlined function into invokes. 63752419Sjulian/// 63852419Sjulian/// II is the invoke instruction being inlined. FirstNewBlock is the first 63952419Sjulian/// block of the inlined code (the last block is the end of the function), 64052419Sjulian/// and InlineCodeInfo is information about the code that got inlined. 64152419Sjulianstatic void HandleInlinedEHPad(InvokeInst *II, BasicBlock *FirstNewBlock, 64252419Sjulian ClonedCodeInfo &InlinedCodeInfo) { 64352419Sjulian BasicBlock *UnwindDest = II->getUnwindDest(); 64452419Sjulian Function *Caller = FirstNewBlock->getParent(); 64552419Sjulian 64652419Sjulian assert(UnwindDest->getFirstNonPHI()->isEHPad() && "unexpected BasicBlock!"); 64752419Sjulian 64852419Sjulian // If there are PHI nodes in the unwind destination block, we need to keep 64952419Sjulian // track of which values came into them from the invoke before removing the 65052419Sjulian // edge from this block. 65152419Sjulian SmallVector<Value *, 8> UnwindDestPHIValues; 65252419Sjulian BasicBlock *InvokeBB = II->getParent(); 65352419Sjulian for (Instruction &I : *UnwindDest) { 65452419Sjulian // Save the value to use for this edge. 65552419Sjulian PHINode *PHI = dyn_cast<PHINode>(&I); 65652419Sjulian if (!PHI) 65752419Sjulian break; 65852419Sjulian UnwindDestPHIValues.push_back(PHI->getIncomingValueForBlock(InvokeBB)); 65952419Sjulian } 66052419Sjulian 66152419Sjulian // Add incoming-PHI values to the unwind destination block for the given basic 66252419Sjulian // block, using the values for the original invoke's source block. 66352419Sjulian auto UpdatePHINodes = [&](BasicBlock *Src) { 66452419Sjulian BasicBlock::iterator I = UnwindDest->begin(); 66554096Sarchie for (Value *V : UnwindDestPHIValues) { 66654096Sarchie PHINode *PHI = cast<PHINode>(I); 66754096Sarchie PHI->addIncoming(V, Src); 66852419Sjulian ++I; 66952419Sjulian } 67052419Sjulian }; 67152419Sjulian 67252419Sjulian // This connects all the instructions which 'unwind to caller' to the invoke 67352419Sjulian // destination. 67452419Sjulian UnwindDestMemoTy FuncletUnwindMap; 67552419Sjulian for (Function::iterator BB = FirstNewBlock->getIterator(), E = Caller->end(); 67652419Sjulian BB != E; ++BB) { 67752419Sjulian if (auto *CRI = dyn_cast<CleanupReturnInst>(BB->getTerminator())) { 67852419Sjulian if (CRI->unwindsToCaller()) { 67952419Sjulian auto *CleanupPad = CRI->getCleanupPad(); 68052419Sjulian CleanupReturnInst::Create(CleanupPad, UnwindDest, CRI); 68152419Sjulian CRI->eraseFromParent(); 68252419Sjulian UpdatePHINodes(&*BB); 68352419Sjulian // Finding a cleanupret with an unwind destination would confuse 68452419Sjulian // subsequent calls to getUnwindDestToken, so map the cleanuppad 68552419Sjulian // to short-circuit any such calls and recognize this as an "unwind 68652419Sjulian // to caller" cleanup. 68752419Sjulian assert(!FuncletUnwindMap.count(CleanupPad) || 68852419Sjulian isa<ConstantTokenNone>(FuncletUnwindMap[CleanupPad])); 68952419Sjulian FuncletUnwindMap[CleanupPad] = 69052419Sjulian ConstantTokenNone::get(Caller->getContext()); 69152419Sjulian } 69252419Sjulian } 69352419Sjulian 69452419Sjulian Instruction *I = BB->getFirstNonPHI(); 69552419Sjulian if (!I->isEHPad()) 69652419Sjulian continue; 69752419Sjulian 69852419Sjulian Instruction *Replacement = nullptr; 69952419Sjulian if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(I)) { 70052419Sjulian if (CatchSwitch->unwindsToCaller()) { 70152419Sjulian Value *UnwindDestToken; 70252419Sjulian if (auto *ParentPad = 70352419Sjulian dyn_cast<Instruction>(CatchSwitch->getParentPad())) { 70452419Sjulian // This catchswitch is nested inside another funclet. If that 70552419Sjulian // funclet has an unwind destination within the inlinee, then 70652419Sjulian // unwinding out of this catchswitch would be UB. Rewriting this 70752419Sjulian // catchswitch to unwind to the inlined invoke's unwind dest would 70852419Sjulian // give the parent funclet multiple unwind destinations, which is 70952419Sjulian // something that subsequent EH table generation can't handle and 71052419Sjulian // that the veirifer rejects. So when we see such a call, leave it 71152419Sjulian // as "unwind to caller". 71252419Sjulian UnwindDestToken = getUnwindDestToken(ParentPad, FuncletUnwindMap); 71352419Sjulian if (UnwindDestToken && !isa<ConstantTokenNone>(UnwindDestToken)) 71452419Sjulian continue; 71552419Sjulian } else { 71652419Sjulian // This catchswitch has no parent to inherit constraints from, and 71752419Sjulian // none of its descendants can have an unwind edge that exits it and 71852419Sjulian // targets another funclet in the inlinee. It may or may not have a 71952419Sjulian // descendant that definitively has an unwind to caller. In either 72052419Sjulian // case, we'll have to assume that any unwinds out of it may need to 72152419Sjulian // be routed to the caller, so treat it as though it has a definitive 72252419Sjulian // unwind to caller. 72352419Sjulian UnwindDestToken = ConstantTokenNone::get(Caller->getContext()); 72452419Sjulian } 72552419Sjulian auto *NewCatchSwitch = CatchSwitchInst::Create( 72652419Sjulian CatchSwitch->getParentPad(), UnwindDest, 72752419Sjulian CatchSwitch->getNumHandlers(), CatchSwitch->getName(), 72852419Sjulian CatchSwitch); 72952419Sjulian for (BasicBlock *PadBB : CatchSwitch->handlers()) 73052419Sjulian NewCatchSwitch->addHandler(PadBB); 73152419Sjulian // Propagate info for the old catchswitch over to the new one in 73252419Sjulian // the unwind map. This also serves to short-circuit any subsequent 73352419Sjulian // checks for the unwind dest of this catchswitch, which would get 73452419Sjulian // confused if they found the outer handler in the callee. 73552419Sjulian FuncletUnwindMap[NewCatchSwitch] = UnwindDestToken; 73652419Sjulian Replacement = NewCatchSwitch; 73752419Sjulian } 73852419Sjulian } else if (!isa<FuncletPadInst>(I)) { 73952419Sjulian llvm_unreachable("unexpected EHPad!"); 74052419Sjulian } 74152419Sjulian 74254096Sarchie if (Replacement) { 74354096Sarchie Replacement->takeName(I); 74454096Sarchie I->replaceAllUsesWith(Replacement); 74554096Sarchie I->eraseFromParent(); 74654096Sarchie UpdatePHINodes(&*BB); 74754096Sarchie } 74854096Sarchie } 74954096Sarchie 75054096Sarchie if (InlinedCodeInfo.ContainsCalls) 75154096Sarchie for (Function::iterator BB = FirstNewBlock->getIterator(), 75254096Sarchie E = Caller->end(); 75354096Sarchie BB != E; ++BB) 75454096Sarchie if (BasicBlock *NewBB = HandleCallsInBlockInlinedThroughInvoke( 75554096Sarchie &*BB, UnwindDest, &FuncletUnwindMap)) 75654096Sarchie // Update any PHI nodes in the exceptional block to indicate that there 75754096Sarchie // is now a new entry in them. 75854096Sarchie UpdatePHINodes(NewBB); 75954096Sarchie 76054096Sarchie // Now that everything is happy, we have one final detail. The PHI nodes in 76154096Sarchie // the exception destination block still have entries due to the original 76252419Sjulian // invoke instruction. Eliminate these entries (which might even delete the 76352419Sjulian // PHI node) now. 76452419Sjulian UnwindDest->removePredecessor(InvokeBB); 76552419Sjulian} 76652419Sjulian 76752419Sjulian/// When inlining a call site that has !llvm.mem.parallel_loop_access or 76852419Sjulian/// llvm.access.group metadata, that metadata should be propagated to all 76952419Sjulian/// memory-accessing cloned instructions. 77052419Sjulianstatic void PropagateParallelLoopAccessMetadata(CallSite CS, 77152419Sjulian ValueToValueMapTy &VMap) { 77252419Sjulian MDNode *M = 77352419Sjulian CS.getInstruction()->getMetadata(LLVMContext::MD_mem_parallel_loop_access); 77452419Sjulian MDNode *CallAccessGroup = 77552419Sjulian CS.getInstruction()->getMetadata(LLVMContext::MD_access_group); 77652419Sjulian if (!M && !CallAccessGroup) 77752419Sjulian return; 77852419Sjulian 77952419Sjulian for (ValueToValueMapTy::iterator VMI = VMap.begin(), VMIE = VMap.end(); 78052419Sjulian VMI != VMIE; ++VMI) { 78152419Sjulian if (!VMI->second) 78252419Sjulian continue; 78352419Sjulian 78452419Sjulian Instruction *NI = dyn_cast<Instruction>(VMI->second); 78552419Sjulian if (!NI) 78652419Sjulian continue; 78752419Sjulian 78852419Sjulian if (M) { 78952419Sjulian if (MDNode *PM = 79052419Sjulian NI->getMetadata(LLVMContext::MD_mem_parallel_loop_access)) { 79152419Sjulian M = MDNode::concatenate(PM, M); 79252419Sjulian NI->setMetadata(LLVMContext::MD_mem_parallel_loop_access, M); 79352419Sjulian } else if (NI->mayReadOrWriteMemory()) { 79452419Sjulian NI->setMetadata(LLVMContext::MD_mem_parallel_loop_access, M); 79552419Sjulian } 79652419Sjulian } 79752419Sjulian 79852419Sjulian if (NI->mayReadOrWriteMemory()) { 79952419Sjulian MDNode *UnitedAccGroups = uniteAccessGroups( 80052419Sjulian NI->getMetadata(LLVMContext::MD_access_group), CallAccessGroup); 80152419Sjulian NI->setMetadata(LLVMContext::MD_access_group, UnitedAccGroups); 80252419Sjulian } 80352419Sjulian } 80452419Sjulian} 80552419Sjulian 80652419Sjulian/// When inlining a function that contains noalias scope metadata, 80752419Sjulian/// this metadata needs to be cloned so that the inlined blocks 80852419Sjulian/// have different "unique scopes" at every call site. Were this not done, then 80952419Sjulian/// aliasing scopes from a function inlined into a caller multiple times could 81052419Sjulian/// not be differentiated (and this would lead to miscompiles because the 81152419Sjulian/// non-aliasing property communicated by the metadata could have 81252419Sjulian/// call-site-specific control dependencies). 81352419Sjulianstatic void CloneAliasScopeMetadata(CallSite CS, ValueToValueMapTy &VMap) { 81452419Sjulian const Function *CalledFunc = CS.getCalledFunction(); 81552419Sjulian SetVector<const MDNode *> MD; 81652419Sjulian 81752419Sjulian // Note: We could only clone the metadata if it is already used in the 81852419Sjulian // caller. I'm omitting that check here because it might confuse 81952419Sjulian // inter-procedural alias analysis passes. We can revisit this if it becomes 82052419Sjulian // an efficiency or overhead problem. 82152419Sjulian 82252419Sjulian for (const BasicBlock &I : *CalledFunc) 82352419Sjulian for (const Instruction &J : I) { 82452419Sjulian if (const MDNode *M = J.getMetadata(LLVMContext::MD_alias_scope)) 82552419Sjulian MD.insert(M); 82652419Sjulian if (const MDNode *M = J.getMetadata(LLVMContext::MD_noalias)) 82752419Sjulian MD.insert(M); 82852419Sjulian } 82952419Sjulian 83052419Sjulian if (MD.empty()) 83152419Sjulian return; 83252419Sjulian 83352419Sjulian // Walk the existing metadata, adding the complete (perhaps cyclic) chain to 83452419Sjulian // the set. 83552419Sjulian SmallVector<const Metadata *, 16> Queue(MD.begin(), MD.end()); 83652419Sjulian while (!Queue.empty()) { 83752419Sjulian const MDNode *M = cast<MDNode>(Queue.pop_back_val()); 83852419Sjulian for (unsigned i = 0, ie = M->getNumOperands(); i != ie; ++i) 83952419Sjulian if (const MDNode *M1 = dyn_cast<MDNode>(M->getOperand(i))) 84052419Sjulian if (MD.insert(M1)) 84152419Sjulian Queue.push_back(M1); 84252419Sjulian } 84352419Sjulian 84452419Sjulian // Now we have a complete set of all metadata in the chains used to specify 84552419Sjulian // the noalias scopes and the lists of those scopes. 84652419Sjulian SmallVector<TempMDTuple, 16> DummyNodes; 84752419Sjulian DenseMap<const MDNode *, TrackingMDNodeRef> MDMap; 84852419Sjulian for (const MDNode *I : MD) { 84952419Sjulian DummyNodes.push_back(MDTuple::getTemporary(CalledFunc->getContext(), None)); 85052419Sjulian MDMap[I].reset(DummyNodes.back().get()); 85152419Sjulian } 85252419Sjulian 85352419Sjulian // Create new metadata nodes to replace the dummy nodes, replacing old 85452419Sjulian // metadata references with either a dummy node or an already-created new 85552419Sjulian // node. 85652419Sjulian for (const MDNode *I : MD) { 85752419Sjulian SmallVector<Metadata *, 4> NewOps; 85852419Sjulian for (unsigned i = 0, ie = I->getNumOperands(); i != ie; ++i) { 85952419Sjulian const Metadata *V = I->getOperand(i); 86052419Sjulian if (const MDNode *M = dyn_cast<MDNode>(V)) 86152419Sjulian NewOps.push_back(MDMap[M]); 86252419Sjulian else 86352419Sjulian NewOps.push_back(const_cast<Metadata *>(V)); 86452419Sjulian } 86552419Sjulian 86652419Sjulian MDNode *NewM = MDNode::get(CalledFunc->getContext(), NewOps); 86752419Sjulian MDTuple *TempM = cast<MDTuple>(MDMap[I]); 86852419Sjulian assert(TempM->isTemporary() && "Expected temporary node"); 86952419Sjulian 87052419Sjulian TempM->replaceAllUsesWith(NewM); 87152419Sjulian } 87252419Sjulian 87352419Sjulian // Now replace the metadata in the new inlined instructions with the 87452419Sjulian // repacements from the map. 87552419Sjulian for (ValueToValueMapTy::iterator VMI = VMap.begin(), VMIE = VMap.end(); 87652419Sjulian VMI != VMIE; ++VMI) { 87752419Sjulian if (!VMI->second) 87852419Sjulian continue; 87952419Sjulian 88052419Sjulian Instruction *NI = dyn_cast<Instruction>(VMI->second); 88152419Sjulian if (!NI) 88252419Sjulian continue; 88352419Sjulian 88452419Sjulian if (MDNode *M = NI->getMetadata(LLVMContext::MD_alias_scope)) { 88552419Sjulian MDNode *NewMD = MDMap[M]; 88652419Sjulian // If the call site also had alias scope metadata (a list of scopes to 88752419Sjulian // which instructions inside it might belong), propagate those scopes to 88852419Sjulian // the inlined instructions. 88952419Sjulian if (MDNode *CSM = 89052419Sjulian CS.getInstruction()->getMetadata(LLVMContext::MD_alias_scope)) 89152419Sjulian NewMD = MDNode::concatenate(NewMD, CSM); 89252419Sjulian NI->setMetadata(LLVMContext::MD_alias_scope, NewMD); 89352419Sjulian } else if (NI->mayReadOrWriteMemory()) { 89452419Sjulian if (MDNode *M = 89552419Sjulian CS.getInstruction()->getMetadata(LLVMContext::MD_alias_scope)) 89652419Sjulian NI->setMetadata(LLVMContext::MD_alias_scope, M); 89752419Sjulian } 89852419Sjulian 89952419Sjulian if (MDNode *M = NI->getMetadata(LLVMContext::MD_noalias)) { 90052419Sjulian MDNode *NewMD = MDMap[M]; 90152419Sjulian // If the call site also had noalias metadata (a list of scopes with 90252419Sjulian // which instructions inside it don't alias), propagate those scopes to 90352419Sjulian // the inlined instructions. 90452419Sjulian if (MDNode *CSM = 90552419Sjulian CS.getInstruction()->getMetadata(LLVMContext::MD_noalias)) 90652419Sjulian NewMD = MDNode::concatenate(NewMD, CSM); 90752419Sjulian NI->setMetadata(LLVMContext::MD_noalias, NewMD); 90852419Sjulian } else if (NI->mayReadOrWriteMemory()) { 90952419Sjulian if (MDNode *M = CS.getInstruction()->getMetadata(LLVMContext::MD_noalias)) 91052419Sjulian NI->setMetadata(LLVMContext::MD_noalias, M); 91152419Sjulian } 91252419Sjulian } 91352419Sjulian} 91452419Sjulian 91552419Sjulian/// If the inlined function has noalias arguments, 91652419Sjulian/// then add new alias scopes for each noalias argument, tag the mapped noalias 91752419Sjulian/// parameters with noalias metadata specifying the new scope, and tag all 91852419Sjulian/// non-derived loads, stores and memory intrinsics with the new alias scopes. 91952419Sjulianstatic void AddAliasScopeMetadata(CallSite CS, ValueToValueMapTy &VMap, 92052419Sjulian const DataLayout &DL, AAResults *CalleeAAR) { 92152419Sjulian if (!EnableNoAliasConversion) 92252419Sjulian return; 92352419Sjulian 92452419Sjulian const Function *CalledFunc = CS.getCalledFunction(); 92552419Sjulian SmallVector<const Argument *, 4> NoAliasArgs; 92652419Sjulian 92752419Sjulian for (const Argument &Arg : CalledFunc->args()) 92852419Sjulian if (Arg.hasNoAliasAttr() && !Arg.use_empty()) 92952419Sjulian NoAliasArgs.push_back(&Arg); 93052419Sjulian 93152419Sjulian if (NoAliasArgs.empty()) 93252419Sjulian return; 93352419Sjulian 93452419Sjulian // To do a good job, if a noalias variable is captured, we need to know if 93552419Sjulian // the capture point dominates the particular use we're considering. 93652419Sjulian DominatorTree DT; 93752419Sjulian DT.recalculate(const_cast<Function&>(*CalledFunc)); 93852419Sjulian 93952419Sjulian // noalias indicates that pointer values based on the argument do not alias 94052419Sjulian // pointer values which are not based on it. So we add a new "scope" for each 94152419Sjulian // noalias function argument. Accesses using pointers based on that argument 94252419Sjulian // become part of that alias scope, accesses using pointers not based on that 94352419Sjulian // argument are tagged as noalias with that scope. 94452419Sjulian 94552419Sjulian DenseMap<const Argument *, MDNode *> NewScopes; 94652419Sjulian MDBuilder MDB(CalledFunc->getContext()); 94752419Sjulian 94852419Sjulian // Create a new scope domain for this function. 94952419Sjulian MDNode *NewDomain = 95052419Sjulian MDB.createAnonymousAliasScopeDomain(CalledFunc->getName()); 95152419Sjulian for (unsigned i = 0, e = NoAliasArgs.size(); i != e; ++i) { 95252419Sjulian const Argument *A = NoAliasArgs[i]; 95352419Sjulian 95452419Sjulian std::string Name = CalledFunc->getName(); 95552419Sjulian if (A->hasName()) { 95652419Sjulian Name += ": %"; 95752419Sjulian Name += A->getName(); 95852419Sjulian } else { 95952419Sjulian Name += ": argument "; 96052419Sjulian Name += utostr(i); 96152419Sjulian } 96252419Sjulian 96352419Sjulian // Note: We always create a new anonymous root here. This is true regardless 96452419Sjulian // of the linkage of the callee because the aliasing "scope" is not just a 96552419Sjulian // property of the callee, but also all control dependencies in the caller. 96652419Sjulian MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name); 96752419Sjulian NewScopes.insert(std::make_pair(A, NewScope)); 96852419Sjulian } 96952419Sjulian 97052419Sjulian // Iterate over all new instructions in the map; for all memory-access 97152419Sjulian // instructions, add the alias scope metadata. 97252419Sjulian for (ValueToValueMapTy::iterator VMI = VMap.begin(), VMIE = VMap.end(); 97352419Sjulian VMI != VMIE; ++VMI) { 97452419Sjulian if (const Instruction *I = dyn_cast<Instruction>(VMI->first)) { 97552419Sjulian if (!VMI->second) 97652419Sjulian continue; 97752419Sjulian 97852419Sjulian Instruction *NI = dyn_cast<Instruction>(VMI->second); 97952419Sjulian if (!NI) 98052419Sjulian continue; 98152419Sjulian 98252419Sjulian bool IsArgMemOnlyCall = false, IsFuncCall = false; 98352419Sjulian SmallVector<const Value *, 2> PtrArgs; 98452419Sjulian 98552419Sjulian if (const LoadInst *LI = dyn_cast<LoadInst>(I)) 98652419Sjulian PtrArgs.push_back(LI->getPointerOperand()); 98752419Sjulian else if (const StoreInst *SI = dyn_cast<StoreInst>(I)) 98852419Sjulian PtrArgs.push_back(SI->getPointerOperand()); 98952419Sjulian else if (const VAArgInst *VAAI = dyn_cast<VAArgInst>(I)) 99052419Sjulian PtrArgs.push_back(VAAI->getPointerOperand()); 99152419Sjulian else if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(I)) 99252419Sjulian PtrArgs.push_back(CXI->getPointerOperand()); 99352419Sjulian else if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I)) 99452419Sjulian PtrArgs.push_back(RMWI->getPointerOperand()); 99552419Sjulian else if (const auto *Call = dyn_cast<CallBase>(I)) { 99652419Sjulian // If we know that the call does not access memory, then we'll still 99752419Sjulian // know that about the inlined clone of this call site, and we don't 99852419Sjulian // need to add metadata. 99952419Sjulian if (Call->doesNotAccessMemory()) 100052419Sjulian continue; 100152419Sjulian 100252419Sjulian IsFuncCall = true; 100352419Sjulian if (CalleeAAR) { 100452419Sjulian FunctionModRefBehavior MRB = CalleeAAR->getModRefBehavior(Call); 100552419Sjulian if (MRB == FMRB_OnlyAccessesArgumentPointees || 100652419Sjulian MRB == FMRB_OnlyReadsArgumentPointees) 100752419Sjulian IsArgMemOnlyCall = true; 100852419Sjulian } 100952419Sjulian 101052419Sjulian for (Value *Arg : Call->args()) { 101152419Sjulian // We need to check the underlying objects of all arguments, not just 101252419Sjulian // the pointer arguments, because we might be passing pointers as 101352419Sjulian // integers, etc. 101452419Sjulian // However, if we know that the call only accesses pointer arguments, 101552419Sjulian // then we only need to check the pointer arguments. 101652419Sjulian if (IsArgMemOnlyCall && !Arg->getType()->isPointerTy()) 101752419Sjulian continue; 101852419Sjulian 101959728Sjulian PtrArgs.push_back(Arg); 102059728Sjulian } 102152419Sjulian } 102252419Sjulian 102352419Sjulian // If we found no pointers, then this instruction is not suitable for 102452419Sjulian // pairing with an instruction to receive aliasing metadata. 102552419Sjulian // However, if this is a call, this we might just alias with none of the 102652419Sjulian // noalias arguments. 102759728Sjulian if (PtrArgs.empty() && !IsFuncCall) 102852419Sjulian continue; 102952419Sjulian 103052419Sjulian // It is possible that there is only one underlying object, but you 103152419Sjulian // need to go through several PHIs to see it, and thus could be 103252419Sjulian // repeated in the Objects list. 103352419Sjulian SmallPtrSet<const Value *, 4> ObjSet; 103452419Sjulian SmallVector<Metadata *, 4> Scopes, NoAliases; 103552419Sjulian 103652419Sjulian SmallSetVector<const Argument *, 4> NAPtrArgs; 103752419Sjulian for (const Value *V : PtrArgs) { 103852419Sjulian SmallVector<const Value *, 4> Objects; 103952419Sjulian GetUnderlyingObjects(V, Objects, DL, /* LI = */ nullptr); 104052419Sjulian 104152419Sjulian for (const Value *O : Objects) 104252419Sjulian ObjSet.insert(O); 104352419Sjulian } 104452419Sjulian 104552419Sjulian // Figure out if we're derived from anything that is not a noalias 104652419Sjulian // argument. 104752419Sjulian bool CanDeriveViaCapture = false, UsesAliasingPtr = false; 104852419Sjulian for (const Value *V : ObjSet) { 104952419Sjulian // Is this value a constant that cannot be derived from any pointer 105052419Sjulian // value (we need to exclude constant expressions, for example, that 105152419Sjulian // are formed from arithmetic on global symbols). 105252419Sjulian bool IsNonPtrConst = isa<ConstantInt>(V) || isa<ConstantFP>(V) || 105352419Sjulian isa<ConstantPointerNull>(V) || 105452419Sjulian isa<ConstantDataVector>(V) || isa<UndefValue>(V); 105552419Sjulian if (IsNonPtrConst) 105652419Sjulian continue; 105752419Sjulian 105852419Sjulian // If this is anything other than a noalias argument, then we cannot 105952419Sjulian // completely describe the aliasing properties using alias.scope 106052419Sjulian // metadata (and, thus, won't add any). 106152419Sjulian if (const Argument *A = dyn_cast<Argument>(V)) { 106252419Sjulian if (!A->hasNoAliasAttr()) 106352419Sjulian UsesAliasingPtr = true; 106452419Sjulian } else { 106552419Sjulian UsesAliasingPtr = true; 106652419Sjulian } 106752419Sjulian 106852419Sjulian // If this is not some identified function-local object (which cannot 106952419Sjulian // directly alias a noalias argument), or some other argument (which, 107052419Sjulian // by definition, also cannot alias a noalias argument), then we could 107152419Sjulian // alias a noalias argument that has been captured). 107252419Sjulian if (!isa<Argument>(V) && 107352419Sjulian !isIdentifiedFunctionLocal(const_cast<Value*>(V))) 107452419Sjulian CanDeriveViaCapture = true; 107552419Sjulian } 107652419Sjulian 107752419Sjulian // A function call can always get captured noalias pointers (via other 107852419Sjulian // parameters, globals, etc.). 107952419Sjulian if (IsFuncCall && !IsArgMemOnlyCall) 108052419Sjulian CanDeriveViaCapture = true; 108152419Sjulian 108254096Sarchie // First, we want to figure out all of the sets with which we definitely 108352419Sjulian // don't alias. Iterate over all noalias set, and add those for which: 108452419Sjulian // 1. The noalias argument is not in the set of objects from which we 108552419Sjulian // definitely derive. 108652419Sjulian // 2. The noalias argument has not yet been captured. 108752419Sjulian // An arbitrary function that might load pointers could see captured 108852419Sjulian // noalias arguments via other noalias arguments or globals, and so we 108952419Sjulian // must always check for prior capture. 109052419Sjulian for (const Argument *A : NoAliasArgs) { 109152419Sjulian if (!ObjSet.count(A) && (!CanDeriveViaCapture || 109252419Sjulian // It might be tempting to skip the 109352419Sjulian // PointerMayBeCapturedBefore check if 109452419Sjulian // A->hasNoCaptureAttr() is true, but this is 109552419Sjulian // incorrect because nocapture only guarantees 109652419Sjulian // that no copies outlive the function, not 109752419Sjulian // that the value cannot be locally captured. 109852419Sjulian !PointerMayBeCapturedBefore(A, 109952419Sjulian /* ReturnCaptures */ false, 110052419Sjulian /* StoreCaptures */ false, I, &DT))) 110152419Sjulian NoAliases.push_back(NewScopes[A]); 110252419Sjulian } 110352419Sjulian 110452419Sjulian if (!NoAliases.empty()) 110552419Sjulian NI->setMetadata(LLVMContext::MD_noalias, 110652419Sjulian MDNode::concatenate( 110752419Sjulian NI->getMetadata(LLVMContext::MD_noalias), 110852419Sjulian MDNode::get(CalledFunc->getContext(), NoAliases))); 110952419Sjulian 111052419Sjulian // Next, we want to figure out all of the sets to which we might belong. 111152419Sjulian // We might belong to a set if the noalias argument is in the set of 111252722Sjulian // underlying objects. If there is some non-noalias argument in our list 111352419Sjulian // of underlying objects, then we cannot add a scope because the fact 111452419Sjulian // that some access does not alias with any set of our noalias arguments 111552419Sjulian // cannot itself guarantee that it does not alias with this access 111652419Sjulian // (because there is some pointer of unknown origin involved and the 111759728Sjulian // other access might also depend on this pointer). We also cannot add 111859728Sjulian // scopes to arbitrary functions unless we know they don't access any 111952419Sjulian // non-parameter pointer-values. 112052419Sjulian bool CanAddScopes = !UsesAliasingPtr; 112152419Sjulian if (CanAddScopes && IsFuncCall) 112252419Sjulian CanAddScopes = IsArgMemOnlyCall; 112352419Sjulian 112452419Sjulian if (CanAddScopes) 112552419Sjulian for (const Argument *A : NoAliasArgs) { 112652419Sjulian if (ObjSet.count(A)) 112752419Sjulian Scopes.push_back(NewScopes[A]); 112852419Sjulian } 112959728Sjulian 113052419Sjulian if (!Scopes.empty()) 113152419Sjulian NI->setMetadata( 113252419Sjulian LLVMContext::MD_alias_scope, 113359728Sjulian MDNode::concatenate(NI->getMetadata(LLVMContext::MD_alias_scope), 113452419Sjulian MDNode::get(CalledFunc->getContext(), Scopes))); 113552419Sjulian } 113652419Sjulian } 113759728Sjulian} 113852419Sjulian 113952419Sjulian/// If the inlined function has non-byval align arguments, then 114052419Sjulian/// add @llvm.assume-based alignment assumptions to preserve this information. 114152419Sjulianstatic void AddAlignmentAssumptions(CallSite CS, InlineFunctionInfo &IFI) { 114252419Sjulian if (!PreserveAlignmentAssumptions || !IFI.GetAssumptionCache) 114352419Sjulian return; 114452419Sjulian 114552419Sjulian AssumptionCache *AC = &(*IFI.GetAssumptionCache)(*CS.getCaller()); 114652419Sjulian auto &DL = CS.getCaller()->getParent()->getDataLayout(); 114752419Sjulian 114852419Sjulian // To avoid inserting redundant assumptions, we should check for assumptions 114952419Sjulian // already in the caller. To do this, we might need a DT of the caller. 115052419Sjulian DominatorTree DT; 115152419Sjulian bool DTCalculated = false; 115252419Sjulian 115352419Sjulian Function *CalledFunc = CS.getCalledFunction(); 115452419Sjulian for (Argument &Arg : CalledFunc->args()) { 115552419Sjulian unsigned Align = Arg.getType()->isPointerTy() ? Arg.getParamAlignment() : 0; 115652419Sjulian if (Align && !Arg.hasByValOrInAllocaAttr() && !Arg.hasNUses(0)) { 115759728Sjulian if (!DTCalculated) { 115852419Sjulian DT.recalculate(*CS.getCaller()); 115952419Sjulian DTCalculated = true; 116059728Sjulian } 116152419Sjulian 116252419Sjulian // If we can already prove the asserted alignment in the context of the 116352419Sjulian // caller, then don't bother inserting the assumption. 116452419Sjulian Value *ArgVal = CS.getArgument(Arg.getArgNo()); 116552419Sjulian if (getKnownAlignment(ArgVal, DL, CS.getInstruction(), AC, &DT) >= Align) 116652419Sjulian continue; 116752419Sjulian 116852419Sjulian CallInst *NewAsmp = IRBuilder<>(CS.getInstruction()) 116952419Sjulian .CreateAlignmentAssumption(DL, ArgVal, Align); 117059728Sjulian AC->registerAssumption(NewAsmp); 117152419Sjulian } 117252419Sjulian } 117352419Sjulian} 117452419Sjulian 117552419Sjulian/// Once we have cloned code over from a callee into the caller, 117652419Sjulian/// update the specified callgraph to reflect the changes we made. 117752419Sjulian/// Note that it's possible that not all code was copied over, so only 117852419Sjulian/// some edges of the callgraph may remain. 117952419Sjulianstatic void UpdateCallGraphAfterInlining(CallSite CS, 118052419Sjulian Function::iterator FirstNewBlock, 118152419Sjulian ValueToValueMapTy &VMap, 118252419Sjulian InlineFunctionInfo &IFI) { 118352419Sjulian CallGraph &CG = *IFI.CG; 118452419Sjulian const Function *Caller = CS.getCaller(); 118552419Sjulian const Function *Callee = CS.getCalledFunction(); 118652419Sjulian CallGraphNode *CalleeNode = CG[Callee]; 118752419Sjulian CallGraphNode *CallerNode = CG[Caller]; 118852419Sjulian 118952419Sjulian // Since we inlined some uninlined call sites in the callee into the caller, 119059728Sjulian // add edges from the caller to all of the callees of the callee. 119152419Sjulian CallGraphNode::iterator I = CalleeNode->begin(), E = CalleeNode->end(); 119252419Sjulian 119352419Sjulian // Consider the case where CalleeNode == CallerNode. 119452419Sjulian CallGraphNode::CalledFunctionsVector CallCache; 119552419Sjulian if (CalleeNode == CallerNode) { 119652419Sjulian CallCache.assign(I, E); 119752419Sjulian I = CallCache.begin(); 119852419Sjulian E = CallCache.end(); 119952419Sjulian } 120052419Sjulian 120152419Sjulian for (; I != E; ++I) { 120252419Sjulian const Value *OrigCall = I->first; 120352419Sjulian 120452419Sjulian ValueToValueMapTy::iterator VMI = VMap.find(OrigCall); 120552419Sjulian // Only copy the edge if the call was inlined! 120652419Sjulian if (VMI == VMap.end() || VMI->second == nullptr) 120752419Sjulian continue; 120852419Sjulian 120952419Sjulian // If the call was inlined, but then constant folded, there is no edge to 121052419Sjulian // add. Check for this case. 121152419Sjulian auto *NewCall = dyn_cast<CallBase>(VMI->second); 121252419Sjulian if (!NewCall) 121352419Sjulian continue; 121452419Sjulian 121552419Sjulian // We do not treat intrinsic calls like real function calls because we 121652419Sjulian // expect them to become inline code; do not add an edge for an intrinsic. 121752419Sjulian if (NewCall->getCalledFunction() && 121852419Sjulian NewCall->getCalledFunction()->isIntrinsic()) 121952419Sjulian continue; 122052419Sjulian 122152419Sjulian // Remember that this call site got inlined for the client of 122252419Sjulian // InlineFunction. 122352419Sjulian IFI.InlinedCalls.push_back(NewCall); 122452419Sjulian 122552419Sjulian // It's possible that inlining the callsite will cause it to go from an 122652419Sjulian // indirect to a direct call by resolving a function pointer. If this 122752419Sjulian // happens, set the callee of the new call site to a more precise 122852419Sjulian // destination. This can also happen if the call graph node of the caller 122952419Sjulian // was just unnecessarily imprecise. 123059728Sjulian if (!I->second->getFunction()) 123152419Sjulian if (Function *F = NewCall->getCalledFunction()) { 123252419Sjulian // Indirect call site resolved to direct call. 123352419Sjulian CallerNode->addCalledFunction(NewCall, CG[F]); 123452419Sjulian 123552419Sjulian continue; 123652419Sjulian } 123752419Sjulian 123852419Sjulian CallerNode->addCalledFunction(NewCall, I->second); 123952419Sjulian } 124052419Sjulian 124152419Sjulian // Update the call graph by deleting the edge from Callee to Caller. We must 124252419Sjulian // do this after the loop above in case Caller and Callee are the same. 124352419Sjulian CallerNode->removeCallEdgeFor(*cast<CallBase>(CS.getInstruction())); 124452419Sjulian} 124552419Sjulian 124652419Sjulianstatic void HandleByValArgumentInit(Value *Dst, Value *Src, Module *M, 124752419Sjulian BasicBlock *InsertBlock, 124852419Sjulian InlineFunctionInfo &IFI) { 124952419Sjulian Type *AggTy = cast<PointerType>(Src->getType())->getElementType(); 125052419Sjulian IRBuilder<> Builder(InsertBlock, InsertBlock->begin()); 125152419Sjulian 125252419Sjulian Value *Size = Builder.getInt64(M->getDataLayout().getTypeStoreSize(AggTy)); 125352419Sjulian 125452419Sjulian // Always generate a memcpy of alignment 1 here because we don't know 125552419Sjulian // the alignment of the src pointer. Other optimizations can infer 125652419Sjulian // better alignment. 125752419Sjulian Builder.CreateMemCpy(Dst, /*DstAlign*/ Align::None(), Src, 125854096Sarchie /*SrcAlign*/ Align::None(), Size); 125952419Sjulian} 126052419Sjulian 126152419Sjulian/// When inlining a call site that has a byval argument, 126252419Sjulian/// we have to make the implicit memcpy explicit by adding it. 126352419Sjulianstatic Value *HandleByValArgument(Value *Arg, Instruction *TheCall, 126452419Sjulian const Function *CalledFunc, 126552419Sjulian InlineFunctionInfo &IFI, 126652419Sjulian unsigned ByValAlignment) { 126752419Sjulian PointerType *ArgTy = cast<PointerType>(Arg->getType()); 126852419Sjulian Type *AggTy = ArgTy->getElementType(); 126952419Sjulian 127052419Sjulian Function *Caller = TheCall->getFunction(); 127152419Sjulian const DataLayout &DL = Caller->getParent()->getDataLayout(); 127252419Sjulian 127352419Sjulian // If the called function is readonly, then it could not mutate the caller's 127452419Sjulian // copy of the byval'd memory. In this case, it is safe to elide the copy and 127552419Sjulian // temporary. 127652419Sjulian if (CalledFunc->onlyReadsMemory()) { 127752419Sjulian // If the byval argument has a specified alignment that is greater than the 127852419Sjulian // passed in pointer, then we either have to round up the input pointer or 127952419Sjulian // give up on this transformation. 128052419Sjulian if (ByValAlignment <= 1) // 0 = unspecified, 1 = no particular alignment. 128152419Sjulian return Arg; 128252419Sjulian 128352722Sjulian AssumptionCache *AC = 128452419Sjulian IFI.GetAssumptionCache ? &(*IFI.GetAssumptionCache)(*Caller) : nullptr; 128552419Sjulian 128652419Sjulian // If the pointer is already known to be sufficiently aligned, or if we can 128752419Sjulian // round it up to a larger alignment, then we don't need a temporary. 128852419Sjulian if (getOrEnforceKnownAlignment(Arg, ByValAlignment, DL, TheCall, AC) >= 128952419Sjulian ByValAlignment) 129052419Sjulian return Arg; 129152419Sjulian 129252419Sjulian // Otherwise, we have to make a memcpy to get a safe alignment. This is bad 129352419Sjulian // for code quality, but rarely happens and is required for correctness. 129452419Sjulian } 129552419Sjulian 129652419Sjulian // Create the alloca. If we have DataLayout, use nice alignment. 129752419Sjulian Align Alignment(DL.getPrefTypeAlignment(AggTy)); 129852419Sjulian 129952419Sjulian // If the byval had an alignment specified, we *must* use at least that 130052419Sjulian // alignment, as it is required by the byval argument (and uses of the 130152419Sjulian // pointer inside the callee). 130252419Sjulian Alignment = max(Alignment, MaybeAlign(ByValAlignment)); 130352419Sjulian 130452419Sjulian Value *NewAlloca = 130552419Sjulian new AllocaInst(AggTy, DL.getAllocaAddrSpace(), nullptr, Alignment, 130652419Sjulian Arg->getName(), &*Caller->begin()->begin()); 130752419Sjulian IFI.StaticAllocas.push_back(cast<AllocaInst>(NewAlloca)); 130852419Sjulian 130952419Sjulian // Uses of the argument in the function should use our new alloca 131052419Sjulian // instead. 131152419Sjulian return NewAlloca; 131252419Sjulian} 131352419Sjulian 131452722Sjulian// Check whether this Value is used by a lifetime intrinsic. 131552419Sjulianstatic bool isUsedByLifetimeMarker(Value *V) { 131652419Sjulian for (User *U : V->users()) 131752419Sjulian if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(U)) 131852419Sjulian if (II->isLifetimeStartOrEnd()) 131952419Sjulian return true; 132052419Sjulian return false; 132152419Sjulian} 132252419Sjulian 132352419Sjulian// Check whether the given alloca already has 132452419Sjulian// lifetime.start or lifetime.end intrinsics. 132552419Sjulianstatic bool hasLifetimeMarkers(AllocaInst *AI) { 132652419Sjulian Type *Ty = AI->getType(); 132752419Sjulian Type *Int8PtrTy = Type::getInt8PtrTy(Ty->getContext(), 132852419Sjulian Ty->getPointerAddressSpace()); 132952419Sjulian if (Ty == Int8PtrTy) 133052419Sjulian return isUsedByLifetimeMarker(AI); 133152419Sjulian 133252419Sjulian // Do a scan to find all the casts to i8*. 133352419Sjulian for (User *U : AI->users()) { 133452419Sjulian if (U->getType() != Int8PtrTy) continue; 133552722Sjulian if (U->stripPointerCasts() != AI) continue; 133652419Sjulian if (isUsedByLifetimeMarker(U)) 133752419Sjulian return true; 133852419Sjulian } 133952419Sjulian return false; 134052419Sjulian} 134152419Sjulian 134252419Sjulian/// Return the result of AI->isStaticAlloca() if AI were moved to the entry 134352419Sjulian/// block. Allocas used in inalloca calls and allocas of dynamic array size 134452419Sjulian/// cannot be static. 134552419Sjulianstatic bool allocaWouldBeStaticInEntry(const AllocaInst *AI ) { 134652419Sjulian return isa<Constant>(AI->getArraySize()) && !AI->isUsedWithInAlloca(); 134752419Sjulian} 134852419Sjulian 134952419Sjulian/// Returns a DebugLoc for a new DILocation which is a clone of \p OrigDL 135052419Sjulian/// inlined at \p InlinedAt. \p IANodes is an inlined-at cache. 135152419Sjulianstatic DebugLoc inlineDebugLoc(DebugLoc OrigDL, DILocation *InlinedAt, 135252419Sjulian LLVMContext &Ctx, 135352419Sjulian DenseMap<const MDNode *, MDNode *> &IANodes) { 135452419Sjulian auto IA = DebugLoc::appendInlinedAt(OrigDL, InlinedAt, Ctx, IANodes); 135552419Sjulian return DebugLoc::get(OrigDL.getLine(), OrigDL.getCol(), OrigDL.getScope(), 135652419Sjulian IA); 135752419Sjulian} 135852419Sjulian 135952419Sjulian/// Returns the LoopID for a loop which has has been cloned from another 136052419Sjulian/// function for inlining with the new inlined-at start and end locs. 136152419Sjulianstatic MDNode *inlineLoopID(const MDNode *OrigLoopId, DILocation *InlinedAt, 136252419Sjulian LLVMContext &Ctx, 136352419Sjulian DenseMap<const MDNode *, MDNode *> &IANodes) { 136452419Sjulian assert(OrigLoopId && OrigLoopId->getNumOperands() > 0 && 136552419Sjulian "Loop ID needs at least one operand"); 136652419Sjulian assert(OrigLoopId && OrigLoopId->getOperand(0).get() == OrigLoopId && 136752419Sjulian "Loop ID should refer to itself"); 136852419Sjulian 136952419Sjulian // Save space for the self-referential LoopID. 137052419Sjulian SmallVector<Metadata *, 4> MDs = {nullptr}; 137152419Sjulian 137252419Sjulian for (unsigned i = 1; i < OrigLoopId->getNumOperands(); ++i) { 137352419Sjulian Metadata *MD = OrigLoopId->getOperand(i); 137452419Sjulian // Update the DILocations to encode the inlined-at metadata. 137552419Sjulian if (DILocation *DL = dyn_cast<DILocation>(MD)) 137652419Sjulian MDs.push_back(inlineDebugLoc(DL, InlinedAt, Ctx, IANodes)); 137752419Sjulian else 137852419Sjulian MDs.push_back(MD); 137952419Sjulian } 138052419Sjulian 138152419Sjulian MDNode *NewLoopID = MDNode::getDistinct(Ctx, MDs); 138252419Sjulian // Insert the self-referential LoopID. 138352419Sjulian NewLoopID->replaceOperandWith(0, NewLoopID); 138452419Sjulian return NewLoopID; 138552419Sjulian} 138652419Sjulian 138752419Sjulian/// Update inlined instructions' line numbers to 138852419Sjulian/// to encode location where these instructions are inlined. 138952419Sjulianstatic void fixupLineNumbers(Function *Fn, Function::iterator FI, 139052419Sjulian Instruction *TheCall, bool CalleeHasDebugInfo) { 139152419Sjulian const DebugLoc &TheCallDL = TheCall->getDebugLoc(); 139252419Sjulian if (!TheCallDL) 139352722Sjulian return; 139452419Sjulian 139552419Sjulian auto &Ctx = Fn->getContext(); 139652419Sjulian DILocation *InlinedAtNode = TheCallDL; 139752419Sjulian 139852419Sjulian // Create a unique call site, not to be confused with any other call from the 139952419Sjulian // same location. 140052419Sjulian InlinedAtNode = DILocation::getDistinct( 140152419Sjulian Ctx, InlinedAtNode->getLine(), InlinedAtNode->getColumn(), 140252419Sjulian InlinedAtNode->getScope(), InlinedAtNode->getInlinedAt()); 140352419Sjulian 140452419Sjulian // Cache the inlined-at nodes as they're built so they are reused, without 140552419Sjulian // this every instruction's inlined-at chain would become distinct from each 140652419Sjulian // other. 140752419Sjulian DenseMap<const MDNode *, MDNode *> IANodes; 140852419Sjulian 140952419Sjulian // Check if we are not generating inline line tables and want to use 141052419Sjulian // the call site location instead. 141152419Sjulian bool NoInlineLineTables = Fn->hasFnAttribute("no-inline-line-tables"); 141252419Sjulian 141352419Sjulian for (; FI != Fn->end(); ++FI) { 141452419Sjulian for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); 141552419Sjulian BI != BE; ++BI) { 141652419Sjulian // Loop metadata needs to be updated so that the start and end locs 141752419Sjulian // reference inlined-at locations. 141852419Sjulian if (MDNode *LoopID = BI->getMetadata(LLVMContext::MD_loop)) { 141952419Sjulian MDNode *NewLoopID = 142052419Sjulian inlineLoopID(LoopID, InlinedAtNode, BI->getContext(), IANodes); 142152419Sjulian BI->setMetadata(LLVMContext::MD_loop, NewLoopID); 142252419Sjulian } 142352419Sjulian 142452419Sjulian if (!NoInlineLineTables) 142552419Sjulian if (DebugLoc DL = BI->getDebugLoc()) { 142652419Sjulian DebugLoc IDL = 142752419Sjulian inlineDebugLoc(DL, InlinedAtNode, BI->getContext(), IANodes); 142852419Sjulian BI->setDebugLoc(IDL); 142952419Sjulian continue; 143052419Sjulian } 143152419Sjulian 143252419Sjulian if (CalleeHasDebugInfo && !NoInlineLineTables) 143352419Sjulian continue; 143452419Sjulian 143552419Sjulian // If the inlined instruction has no line number, or if inline info 143652419Sjulian // is not being generated, make it look as if it originates from the call 143752419Sjulian // location. This is important for ((__always_inline, __nodebug__)) 143852419Sjulian // functions which must use caller location for all instructions in their 143952419Sjulian // function body. 144052419Sjulian 144152419Sjulian // Don't update static allocas, as they may get moved later. 144252419Sjulian if (auto *AI = dyn_cast<AllocaInst>(BI)) 144352419Sjulian if (allocaWouldBeStaticInEntry(AI)) 144452419Sjulian continue; 144552419Sjulian 144652419Sjulian BI->setDebugLoc(TheCallDL); 144752419Sjulian } 144853913Sarchie 144953913Sarchie // Remove debug info intrinsics if we're not keeping inline info. 145053913Sarchie if (NoInlineLineTables) { 145153913Sarchie BasicBlock::iterator BI = FI->begin(); 145253913Sarchie while (BI != FI->end()) { 145353913Sarchie if (isa<DbgInfoIntrinsic>(BI)) { 145453913Sarchie BI = BI->eraseFromParent(); 145553913Sarchie continue; 145653913Sarchie } 145753913Sarchie ++BI; 145853913Sarchie } 145953913Sarchie } 146053913Sarchie 146153913Sarchie } 146253913Sarchie} 146353913Sarchie 146453913Sarchie/// Update the block frequencies of the caller after a callee has been inlined. 146553913Sarchie/// 146653913Sarchie/// Each block cloned into the caller has its block frequency scaled by the 146753913Sarchie/// ratio of CallSiteFreq/CalleeEntryFreq. This ensures that the cloned copy of 146853913Sarchie/// callee's entry block gets the same frequency as the callsite block and the 146953913Sarchie/// relative frequencies of all cloned blocks remain the same after cloning. 147053913Sarchiestatic void updateCallerBFI(BasicBlock *CallSiteBlock, 147153913Sarchie const ValueToValueMapTy &VMap, 147253913Sarchie BlockFrequencyInfo *CallerBFI, 147353913Sarchie BlockFrequencyInfo *CalleeBFI, 147453913Sarchie const BasicBlock &CalleeEntryBlock) { 147553913Sarchie SmallPtrSet<BasicBlock *, 16> ClonedBBs; 147653913Sarchie for (auto Entry : VMap) { 147753913Sarchie if (!isa<BasicBlock>(Entry.first) || !Entry.second) 147853913Sarchie continue; 147953913Sarchie auto *OrigBB = cast<BasicBlock>(Entry.first); 148053913Sarchie auto *ClonedBB = cast<BasicBlock>(Entry.second); 148153913Sarchie uint64_t Freq = CalleeBFI->getBlockFreq(OrigBB).getFrequency(); 148253913Sarchie if (!ClonedBBs.insert(ClonedBB).second) { 148353913Sarchie // Multiple blocks in the callee might get mapped to one cloned block in 148453913Sarchie // the caller since we prune the callee as we clone it. When that happens, 148553913Sarchie // we want to use the maximum among the original blocks' frequencies. 148653913Sarchie uint64_t NewFreq = CallerBFI->getBlockFreq(ClonedBB).getFrequency(); 148753913Sarchie if (NewFreq > Freq) 148853913Sarchie Freq = NewFreq; 148953913Sarchie } 149053913Sarchie CallerBFI->setBlockFreq(ClonedBB, Freq); 149153913Sarchie } 149253913Sarchie BasicBlock *EntryClone = cast<BasicBlock>(VMap.lookup(&CalleeEntryBlock)); 149353913Sarchie CallerBFI->setBlockFreqAndScale( 149453913Sarchie EntryClone, CallerBFI->getBlockFreq(CallSiteBlock).getFrequency(), 149553913Sarchie ClonedBBs); 149653913Sarchie} 149753913Sarchie 149853913Sarchie/// Update the branch metadata for cloned call instructions. 149953913Sarchiestatic void updateCallProfile(Function *Callee, const ValueToValueMapTy &VMap, 150053913Sarchie const ProfileCount &CalleeEntryCount, 150153913Sarchie const Instruction *TheCall, 150253913Sarchie ProfileSummaryInfo *PSI, 150353913Sarchie BlockFrequencyInfo *CallerBFI) { 150453913Sarchie if (!CalleeEntryCount.hasValue() || CalleeEntryCount.isSynthetic() || 150553913Sarchie CalleeEntryCount.getCount() < 1) 150653913Sarchie return; 150753913Sarchie auto CallSiteCount = PSI ? PSI->getProfileCount(TheCall, CallerBFI) : None; 150853913Sarchie int64_t CallCount = 150953913Sarchie std::min(CallSiteCount.hasValue() ? CallSiteCount.getValue() : 0, 151053913Sarchie CalleeEntryCount.getCount()); 151153913Sarchie updateProfileCallee(Callee, -CallCount, &VMap); 151253913Sarchie} 151353913Sarchie 151453913Sarchievoid llvm::updateProfileCallee( 151553913Sarchie Function *Callee, int64_t entryDelta, 151653913Sarchie const ValueMap<const Value *, WeakTrackingVH> *VMap) { 151753913Sarchie auto CalleeCount = Callee->getEntryCount(); 151853913Sarchie if (!CalleeCount.hasValue()) 151953913Sarchie return; 152053913Sarchie 152153913Sarchie uint64_t priorEntryCount = CalleeCount.getCount(); 152253913Sarchie uint64_t newEntryCount; 152353913Sarchie 152453913Sarchie // Since CallSiteCount is an estimate, it could exceed the original callee 152553913Sarchie // count and has to be set to 0 so guard against underflow. 152653913Sarchie if (entryDelta < 0 && static_cast<uint64_t>(-entryDelta) > priorEntryCount) 152759178Sarchie newEntryCount = 0; 152853913Sarchie else 152953913Sarchie newEntryCount = priorEntryCount + entryDelta; 153053913Sarchie 153153913Sarchie // During inlining ? 153253913Sarchie if (VMap) { 153353913Sarchie uint64_t cloneEntryCount = priorEntryCount - newEntryCount; 153453913Sarchie for (auto Entry : *VMap) 153553913Sarchie if (isa<CallInst>(Entry.first)) 153653913Sarchie if (auto *CI = dyn_cast_or_null<CallInst>(Entry.second)) 153753913Sarchie CI->updateProfWeight(cloneEntryCount, priorEntryCount); 153853913Sarchie } 153953913Sarchie 154053913Sarchie if (entryDelta) { 154153913Sarchie Callee->setEntryCount(newEntryCount); 154253913Sarchie 154353913Sarchie for (BasicBlock &BB : *Callee) 154453913Sarchie // No need to update the callsite if it is pruned during inlining. 154553913Sarchie if (!VMap || VMap->count(&BB)) 154653913Sarchie for (Instruction &I : BB) 154753913Sarchie if (CallInst *CI = dyn_cast<CallInst>(&I)) 154853913Sarchie CI->updateProfWeight(newEntryCount, priorEntryCount); 154953913Sarchie } 155053913Sarchie} 155153913Sarchie 155253913Sarchie/// This function inlines the called function into the basic block of the 155353913Sarchie/// caller. This returns false if it is not possible to inline this call. 155453913Sarchie/// The program is still in a well defined state if this occurs though. 155553913Sarchie/// 155653913Sarchie/// Note that this only does one level of inlining. For example, if the 155753913Sarchie/// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now 155853913Sarchie/// exists in the instruction stream. Similarly this will inline a recursive 155953913Sarchie/// function by one level. 156053913Sarchiellvm::InlineResult llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI, 156153913Sarchie AAResults *CalleeAAR, 156253913Sarchie bool InsertLifetime, 156353913Sarchie Function *ForwardVarArgsTo) { 156453913Sarchie Instruction *TheCall = CS.getInstruction(); 156553913Sarchie assert(TheCall->getParent() && TheCall->getFunction() 156653913Sarchie && "Instruction not in function!"); 156753913Sarchie 156853913Sarchie // FIXME: we don't inline callbr yet. 156953913Sarchie if (isa<CallBrInst>(TheCall)) 157053913Sarchie return false; 157153913Sarchie 157253913Sarchie // If IFI has any state in it, zap it before we fill it in. 157353913Sarchie IFI.reset(); 157453913Sarchie 157553913Sarchie Function *CalledFunc = CS.getCalledFunction(); 157653913Sarchie if (!CalledFunc || // Can't inline external function or indirect 157753913Sarchie CalledFunc->isDeclaration()) // call! 157853913Sarchie return "external or indirect"; 157953913Sarchie 158053913Sarchie // The inliner does not know how to inline through calls with operand bundles 158153913Sarchie // in general ... 158253913Sarchie if (CS.hasOperandBundles()) { 158353913Sarchie for (int i = 0, e = CS.getNumOperandBundles(); i != e; ++i) { 158453913Sarchie uint32_t Tag = CS.getOperandBundleAt(i).getTagID(); 158553913Sarchie // ... but it knows how to inline through "deopt" operand bundles ... 158653913Sarchie if (Tag == LLVMContext::OB_deopt) 158753913Sarchie continue; 158853913Sarchie // ... and "funclet" operand bundles. 158953913Sarchie if (Tag == LLVMContext::OB_funclet) 159053913Sarchie continue; 159153913Sarchie 159253913Sarchie return "unsupported operand bundle"; 159352419Sjulian } 159452419Sjulian } 159552419Sjulian 159652419Sjulian // If the call to the callee cannot throw, set the 'nounwind' flag on any 159752419Sjulian // calls that we inline. 159852419Sjulian bool MarkNoUnwind = CS.doesNotThrow(); 159952419Sjulian 160052419Sjulian BasicBlock *OrigBB = TheCall->getParent(); 160152419Sjulian Function *Caller = OrigBB->getParent(); 160252419Sjulian 160352419Sjulian // GC poses two hazards to inlining, which only occur when the callee has GC: 160452419Sjulian // 1. If the caller has no GC, then the callee's GC must be propagated to the 160559728Sjulian // caller. 160659728Sjulian // 2. If the caller has a differing GC, it is invalid to inline. 160752419Sjulian if (CalledFunc->hasGC()) { 160852419Sjulian if (!Caller->hasGC()) 160952419Sjulian Caller->setGC(CalledFunc->getGC()); 161052419Sjulian else if (CalledFunc->getGC() != Caller->getGC()) 161152419Sjulian return "incompatible GC"; 161252419Sjulian } 161352419Sjulian 161452419Sjulian // Get the personality function from the callee if it contains a landing pad. 161552419Sjulian Constant *CalledPersonality = 161652419Sjulian CalledFunc->hasPersonalityFn() 161752419Sjulian ? CalledFunc->getPersonalityFn()->stripPointerCasts() 161852419Sjulian : nullptr; 161952419Sjulian 162052419Sjulian // Find the personality function used by the landing pads of the caller. If it 162159728Sjulian // exists, then check to see that it matches the personality function used in 162259728Sjulian // the callee. 162352419Sjulian Constant *CallerPersonality = 162459728Sjulian Caller->hasPersonalityFn() 162552419Sjulian ? Caller->getPersonalityFn()->stripPointerCasts() 162652419Sjulian : nullptr; 162753403Sarchie if (CalledPersonality) { 162852419Sjulian if (!CallerPersonality) 162952419Sjulian Caller->setPersonalityFn(CalledPersonality); 163052419Sjulian // If the personality functions match, then we can perform the 163159728Sjulian // inlining. Otherwise, we can't inline. 163259728Sjulian // TODO: This isn't 100% true. Some personality functions are proper 163352419Sjulian // supersets of others and can be used in place of the other. 163452419Sjulian else if (CalledPersonality != CallerPersonality) 163552419Sjulian return "incompatible personality"; 163652419Sjulian } 163752419Sjulian 163852419Sjulian // We need to figure out which funclet the callsite was in so that we may 163952419Sjulian // properly nest the callee. 164052419Sjulian Instruction *CallSiteEHPad = nullptr; 164152419Sjulian if (CallerPersonality) { 164252419Sjulian EHPersonality Personality = classifyEHPersonality(CallerPersonality); 164352419Sjulian if (isScopedEHPersonality(Personality)) { 164452419Sjulian Optional<OperandBundleUse> ParentFunclet = 164552419Sjulian CS.getOperandBundle(LLVMContext::OB_funclet); 164652419Sjulian if (ParentFunclet) 164752419Sjulian CallSiteEHPad = cast<FuncletPadInst>(ParentFunclet->Inputs.front()); 164852419Sjulian 164952419Sjulian // OK, the inlining site is legal. What about the target function? 165059728Sjulian 165159728Sjulian if (CallSiteEHPad) { 165252419Sjulian if (Personality == EHPersonality::MSVC_CXX) { 165359728Sjulian // The MSVC personality cannot tolerate catches getting inlined into 165452419Sjulian // cleanup funclets. 165552419Sjulian if (isa<CleanupPadInst>(CallSiteEHPad)) { 165653403Sarchie // Ok, the call site is within a cleanuppad. Let's check the callee 165752419Sjulian // for catchpads. 165859728Sjulian for (const BasicBlock &CalledBB : *CalledFunc) { 165959728Sjulian if (isa<CatchSwitchInst>(CalledBB.getFirstNonPHI())) 166059728Sjulian return "catch in cleanup funclet"; 166159728Sjulian } 166252419Sjulian } 166359728Sjulian } else if (isAsynchronousEHPersonality(Personality)) { 166459728Sjulian // SEH is even less tolerant, there may not be any sort of exceptional 166559728Sjulian // funclet in the callee. 166659728Sjulian for (const BasicBlock &CalledBB : *CalledFunc) { 166759728Sjulian if (CalledBB.isEHPad()) 166859728Sjulian return "SEH in cleanup funclet"; 166959728Sjulian } 167059728Sjulian } 167152419Sjulian } 167252419Sjulian } 167352419Sjulian } 167452419Sjulian 167552419Sjulian // Determine if we are dealing with a call in an EHPad which does not unwind 167652419Sjulian // to caller. 167752419Sjulian bool EHPadForCallUnwindsLocally = false; 167852419Sjulian if (CallSiteEHPad && CS.isCall()) { 167952419Sjulian UnwindDestMemoTy FuncletUnwindMap; 168052419Sjulian Value *CallSiteUnwindDestToken = 168152419Sjulian getUnwindDestToken(CallSiteEHPad, FuncletUnwindMap); 168252419Sjulian 168352419Sjulian EHPadForCallUnwindsLocally = 168452419Sjulian CallSiteUnwindDestToken && 168552419Sjulian !isa<ConstantTokenNone>(CallSiteUnwindDestToken); 168652419Sjulian } 168752419Sjulian 168852419Sjulian // Get an iterator to the last basic block in the function, which will have 168952419Sjulian // the new function inlined after it. 169052419Sjulian Function::iterator LastBlock = --Caller->end(); 169152419Sjulian 169252419Sjulian // Make sure to capture all of the return instructions from the cloned 169352419Sjulian // function. 169452419Sjulian SmallVector<ReturnInst*, 8> Returns; 169552419Sjulian ClonedCodeInfo InlinedFunctionInfo; 169652419Sjulian Function::iterator FirstNewBlock; 169752419Sjulian 169852419Sjulian { // Scope to destroy VMap after cloning. 169952419Sjulian ValueToValueMapTy VMap; 170052419Sjulian // Keep a list of pair (dst, src) to emit byval initializations. 170152419Sjulian SmallVector<std::pair<Value*, Value*>, 4> ByValInit; 170252419Sjulian 170352419Sjulian auto &DL = Caller->getParent()->getDataLayout(); 170452419Sjulian 170552419Sjulian // Calculate the vector of arguments to pass into the function cloner, which 170652419Sjulian // matches up the formal to the actual argument values. 170752419Sjulian CallSite::arg_iterator AI = CS.arg_begin(); 170852419Sjulian unsigned ArgNo = 0; 170952419Sjulian for (Function::arg_iterator I = CalledFunc->arg_begin(), 171052419Sjulian E = CalledFunc->arg_end(); I != E; ++I, ++AI, ++ArgNo) { 171152419Sjulian Value *ActualArg = *AI; 171252419Sjulian 171352419Sjulian // When byval arguments actually inlined, we need to make the copy implied 171452419Sjulian // by them explicit. However, we don't do this if the callee is readonly 171552419Sjulian // or readnone, because the copy would be unneeded: the callee doesn't 171652419Sjulian // modify the struct. 171752419Sjulian if (CS.isByValArgument(ArgNo)) { 171852419Sjulian ActualArg = HandleByValArgument(ActualArg, TheCall, CalledFunc, IFI, 171952419Sjulian CalledFunc->getParamAlignment(ArgNo)); 172052419Sjulian if (ActualArg != *AI) 172152419Sjulian ByValInit.push_back(std::make_pair(ActualArg, (Value*) *AI)); 172252419Sjulian } 172352419Sjulian 172452419Sjulian VMap[&*I] = ActualArg; 172552419Sjulian } 172652419Sjulian 172752419Sjulian // Add alignment assumptions if necessary. We do this before the inlined 172852419Sjulian // instructions are actually cloned into the caller so that we can easily 172952419Sjulian // check what will be known at the start of the inlined code. 173052419Sjulian AddAlignmentAssumptions(CS, IFI); 173152419Sjulian 173252419Sjulian // We want the inliner to prune the code as it copies. We would LOVE to 173352419Sjulian // have no dead or constant instructions leftover after inlining occurs 173452419Sjulian // (which can happen, e.g., because an argument was constant), but we'll be 173552419Sjulian // happy with whatever the cloner can do. 173652419Sjulian CloneAndPruneFunctionInto(Caller, CalledFunc, VMap, 173752419Sjulian /*ModuleLevelChanges=*/false, Returns, ".i", 173852419Sjulian &InlinedFunctionInfo, TheCall); 173952419Sjulian // Remember the first block that is newly cloned over. 174052419Sjulian FirstNewBlock = LastBlock; ++FirstNewBlock; 174152419Sjulian 174252419Sjulian if (IFI.CallerBFI != nullptr && IFI.CalleeBFI != nullptr) 174352419Sjulian // Update the BFI of blocks cloned into the caller. 174452419Sjulian updateCallerBFI(OrigBB, VMap, IFI.CallerBFI, IFI.CalleeBFI, 174552419Sjulian CalledFunc->front()); 174652419Sjulian 174752419Sjulian updateCallProfile(CalledFunc, VMap, CalledFunc->getEntryCount(), TheCall, 174852419Sjulian IFI.PSI, IFI.CallerBFI); 174952419Sjulian 175052419Sjulian // Inject byval arguments initialization. 175152419Sjulian for (std::pair<Value*, Value*> &Init : ByValInit) 175252419Sjulian HandleByValArgumentInit(Init.first, Init.second, Caller->getParent(), 175352419Sjulian &*FirstNewBlock, IFI); 175452419Sjulian 175552419Sjulian Optional<OperandBundleUse> ParentDeopt = 175652419Sjulian CS.getOperandBundle(LLVMContext::OB_deopt); 175752419Sjulian if (ParentDeopt) { 175852419Sjulian SmallVector<OperandBundleDef, 2> OpDefs; 175952419Sjulian 176052419Sjulian for (auto &VH : InlinedFunctionInfo.OperandBundleCallSites) { 176152419Sjulian Instruction *I = dyn_cast_or_null<Instruction>(VH); 176252419Sjulian if (!I) continue; // instruction was DCE'd or RAUW'ed to undef 176352419Sjulian 176452419Sjulian OpDefs.clear(); 176552419Sjulian 176652419Sjulian CallSite ICS(I); 176752419Sjulian OpDefs.reserve(ICS.getNumOperandBundles()); 176852419Sjulian 176952419Sjulian for (unsigned i = 0, e = ICS.getNumOperandBundles(); i < e; ++i) { 177052419Sjulian auto ChildOB = ICS.getOperandBundleAt(i); 177152419Sjulian if (ChildOB.getTagID() != LLVMContext::OB_deopt) { 177252419Sjulian // If the inlined call has other operand bundles, let them be 177352419Sjulian OpDefs.emplace_back(ChildOB); 177452419Sjulian continue; 177552419Sjulian } 177652419Sjulian 177752419Sjulian // It may be useful to separate this logic (of handling operand 177852419Sjulian // bundles) out to a separate "policy" component if this gets crowded. 177952419Sjulian // Prepend the parent's deoptimization continuation to the newly 178052419Sjulian // inlined call's deoptimization continuation. 178152419Sjulian std::vector<Value *> MergedDeoptArgs; 178252419Sjulian MergedDeoptArgs.reserve(ParentDeopt->Inputs.size() + 178352419Sjulian ChildOB.Inputs.size()); 178452419Sjulian 178552419Sjulian MergedDeoptArgs.insert(MergedDeoptArgs.end(), 178652419Sjulian ParentDeopt->Inputs.begin(), 178752419Sjulian ParentDeopt->Inputs.end()); 178852419Sjulian MergedDeoptArgs.insert(MergedDeoptArgs.end(), ChildOB.Inputs.begin(), 178959728Sjulian ChildOB.Inputs.end()); 179052419Sjulian 179152419Sjulian OpDefs.emplace_back("deopt", std::move(MergedDeoptArgs)); 179252419Sjulian } 179352419Sjulian 179452419Sjulian Instruction *NewI = nullptr; 179552419Sjulian if (isa<CallInst>(I)) 179652419Sjulian NewI = CallInst::Create(cast<CallInst>(I), OpDefs, I); 179752419Sjulian else if (isa<CallBrInst>(I)) 179852419Sjulian NewI = CallBrInst::Create(cast<CallBrInst>(I), OpDefs, I); 179952419Sjulian else 180052419Sjulian NewI = InvokeInst::Create(cast<InvokeInst>(I), OpDefs, I); 180152419Sjulian 180252419Sjulian // Note: the RAUW does the appropriate fixup in VMap, so we need to do 180352419Sjulian // this even if the call returns void. 180452419Sjulian I->replaceAllUsesWith(NewI); 180552419Sjulian 180652419Sjulian VH = nullptr; 180752419Sjulian I->eraseFromParent(); 180852419Sjulian } 180952419Sjulian } 181052419Sjulian 181152419Sjulian // Update the callgraph if requested. 181252419Sjulian if (IFI.CG) 181352419Sjulian UpdateCallGraphAfterInlining(CS, FirstNewBlock, VMap, IFI); 181452419Sjulian 181552419Sjulian // For 'nodebug' functions, the associated DISubprogram is always null. 181652419Sjulian // Conservatively avoid propagating the callsite debug location to 181752419Sjulian // instructions inlined from a function whose DISubprogram is not null. 181852419Sjulian fixupLineNumbers(Caller, FirstNewBlock, TheCall, 181952419Sjulian CalledFunc->getSubprogram() != nullptr); 182052419Sjulian 182152419Sjulian // Clone existing noalias metadata if necessary. 182252419Sjulian CloneAliasScopeMetadata(CS, VMap); 182352419Sjulian 182452419Sjulian // Add noalias metadata if necessary. 182552419Sjulian AddAliasScopeMetadata(CS, VMap, DL, CalleeAAR); 182652419Sjulian 182752419Sjulian // Propagate llvm.mem.parallel_loop_access if necessary. 182852419Sjulian PropagateParallelLoopAccessMetadata(CS, VMap); 182952419Sjulian 183052419Sjulian // Register any cloned assumptions. 183152419Sjulian if (IFI.GetAssumptionCache) 183252419Sjulian for (BasicBlock &NewBlock : 183352419Sjulian make_range(FirstNewBlock->getIterator(), Caller->end())) 183452419Sjulian for (Instruction &I : NewBlock) { 183552419Sjulian if (auto *II = dyn_cast<IntrinsicInst>(&I)) 183652419Sjulian if (II->getIntrinsicID() == Intrinsic::assume) 183752419Sjulian (*IFI.GetAssumptionCache)(*Caller).registerAssumption(II); 183852419Sjulian } 183952419Sjulian } 184052419Sjulian 184152419Sjulian // If there are any alloca instructions in the block that used to be the entry 184252419Sjulian // block for the callee, move them to the entry block of the caller. First 184352419Sjulian // calculate which instruction they should be inserted before. We insert the 184452419Sjulian // instructions at the end of the current alloca list. 184552419Sjulian { 184652419Sjulian BasicBlock::iterator InsertPoint = Caller->begin()->begin(); 184752419Sjulian for (BasicBlock::iterator I = FirstNewBlock->begin(), 184852419Sjulian E = FirstNewBlock->end(); I != E; ) { 184952419Sjulian AllocaInst *AI = dyn_cast<AllocaInst>(I++); 185052419Sjulian if (!AI) continue; 185152419Sjulian 185252419Sjulian // If the alloca is now dead, remove it. This often occurs due to code 185352419Sjulian // specialization. 185452419Sjulian if (AI->use_empty()) { 185552419Sjulian AI->eraseFromParent(); 185652419Sjulian continue; 185752419Sjulian } 185852419Sjulian 185952419Sjulian if (!allocaWouldBeStaticInEntry(AI)) 186052419Sjulian continue; 186152419Sjulian 186252419Sjulian // Keep track of the static allocas that we inline into the caller. 186352419Sjulian IFI.StaticAllocas.push_back(AI); 186452419Sjulian 186552419Sjulian // Scan for the block of allocas that we can move over, and move them 186652419Sjulian // all at once. 186752419Sjulian while (isa<AllocaInst>(I) && 186852419Sjulian !cast<AllocaInst>(I)->use_empty() && 186952419Sjulian allocaWouldBeStaticInEntry(cast<AllocaInst>(I))) { 187052419Sjulian IFI.StaticAllocas.push_back(cast<AllocaInst>(I)); 187152419Sjulian ++I; 187252419Sjulian } 187352419Sjulian 187452419Sjulian // Transfer all of the allocas over in a block. Using splice means 187552419Sjulian // that the instructions aren't removed from the symbol table, then 187652419Sjulian // reinserted. 187752419Sjulian Caller->getEntryBlock().getInstList().splice( 187852419Sjulian InsertPoint, FirstNewBlock->getInstList(), AI->getIterator(), I); 187952419Sjulian } 188052419Sjulian // Move any dbg.declares describing the allocas into the entry basic block. 188152419Sjulian DIBuilder DIB(*Caller->getParent()); 188252419Sjulian for (auto &AI : IFI.StaticAllocas) 188352419Sjulian replaceDbgDeclareForAlloca(AI, AI, DIB, DIExpression::ApplyOffset, 0); 188452419Sjulian } 188552419Sjulian 188652419Sjulian SmallVector<Value*,4> VarArgsToForward; 188752419Sjulian SmallVector<AttributeSet, 4> VarArgsAttrs; 188852419Sjulian for (unsigned i = CalledFunc->getFunctionType()->getNumParams(); 188952419Sjulian i < CS.getNumArgOperands(); i++) { 189052419Sjulian VarArgsToForward.push_back(CS.getArgOperand(i)); 189152419Sjulian VarArgsAttrs.push_back(CS.getAttributes().getParamAttributes(i)); 189252419Sjulian } 189352419Sjulian 189452419Sjulian bool InlinedMustTailCalls = false, InlinedDeoptimizeCalls = false; 189552419Sjulian if (InlinedFunctionInfo.ContainsCalls) { 189652419Sjulian CallInst::TailCallKind CallSiteTailKind = CallInst::TCK_None; 189758013Sarchie if (CallInst *CI = dyn_cast<CallInst>(TheCall)) 189852419Sjulian CallSiteTailKind = CI->getTailCallKind(); 189952419Sjulian 190052419Sjulian // For inlining purposes, the "notail" marker is the same as no marker. 190152419Sjulian if (CallSiteTailKind == CallInst::TCK_NoTail) 190252419Sjulian CallSiteTailKind = CallInst::TCK_None; 190352419Sjulian 190459728Sjulian for (Function::iterator BB = FirstNewBlock, E = Caller->end(); BB != E; 190552419Sjulian ++BB) { 190652722Sjulian for (auto II = BB->begin(); II != BB->end();) { 190759728Sjulian Instruction &I = *II++; 190852419Sjulian CallInst *CI = dyn_cast<CallInst>(&I); 190952419Sjulian if (!CI) 191052419Sjulian continue; 191152419Sjulian 191252419Sjulian // Forward varargs from inlined call site to calls to the 191352419Sjulian // ForwardVarArgsTo function, if requested, and to musttail calls. 191452419Sjulian if (!VarArgsToForward.empty() && 191552419Sjulian ((ForwardVarArgsTo && 191652419Sjulian CI->getCalledFunction() == ForwardVarArgsTo) || 191752419Sjulian CI->isMustTailCall())) { 191852419Sjulian // Collect attributes for non-vararg parameters. 191952419Sjulian AttributeList Attrs = CI->getAttributes(); 192052419Sjulian SmallVector<AttributeSet, 8> ArgAttrs; 192152419Sjulian if (!Attrs.isEmpty() || !VarArgsAttrs.empty()) { 192252419Sjulian for (unsigned ArgNo = 0; 192352419Sjulian ArgNo < CI->getFunctionType()->getNumParams(); ++ArgNo) 192452419Sjulian ArgAttrs.push_back(Attrs.getParamAttributes(ArgNo)); 192559728Sjulian } 192652419Sjulian 192759728Sjulian // Add VarArg attributes. 192859728Sjulian ArgAttrs.append(VarArgsAttrs.begin(), VarArgsAttrs.end()); 192952419Sjulian Attrs = AttributeList::get(CI->getContext(), Attrs.getFnAttributes(), 193052419Sjulian Attrs.getRetAttributes(), ArgAttrs); 193152419Sjulian // Add VarArgs to existing parameters. 193252419Sjulian SmallVector<Value *, 6> Params(CI->arg_operands()); 193352419Sjulian Params.append(VarArgsToForward.begin(), VarArgsToForward.end()); 193452419Sjulian CallInst *NewCI = CallInst::Create( 193552419Sjulian CI->getFunctionType(), CI->getCalledOperand(), Params, "", CI); 193652419Sjulian NewCI->setDebugLoc(CI->getDebugLoc()); 193752419Sjulian NewCI->setAttributes(Attrs); 193852419Sjulian NewCI->setCallingConv(CI->getCallingConv()); 193952419Sjulian CI->replaceAllUsesWith(NewCI); 194052419Sjulian CI->eraseFromParent(); 194152419Sjulian CI = NewCI; 194252419Sjulian } 194352419Sjulian 194452419Sjulian if (Function *F = CI->getCalledFunction()) 194552419Sjulian InlinedDeoptimizeCalls |= 194652419Sjulian F->getIntrinsicID() == Intrinsic::experimental_deoptimize; 194752419Sjulian 194852419Sjulian // We need to reduce the strength of any inlined tail calls. For 194952419Sjulian // musttail, we have to avoid introducing potential unbounded stack 195052419Sjulian // growth. For example, if functions 'f' and 'g' are mutually recursive 195152419Sjulian // with musttail, we can inline 'g' into 'f' so long as we preserve 195252419Sjulian // musttail on the cloned call to 'f'. If either the inlined call site 195352419Sjulian // or the cloned call site is *not* musttail, the program already has 195452419Sjulian // one frame of stack growth, so it's safe to remove musttail. Here is 195552419Sjulian // a table of example transformations: 195652419Sjulian // 195752419Sjulian // f -> musttail g -> musttail f ==> f -> musttail f 195852419Sjulian // f -> musttail g -> tail f ==> f -> tail f 195952419Sjulian // f -> g -> musttail f ==> f -> f 196052419Sjulian // f -> g -> tail f ==> f -> f 196152419Sjulian // 196252419Sjulian // Inlined notail calls should remain notail calls. 196352419Sjulian CallInst::TailCallKind ChildTCK = CI->getTailCallKind(); 196452419Sjulian if (ChildTCK != CallInst::TCK_NoTail) 196552419Sjulian ChildTCK = std::min(CallSiteTailKind, ChildTCK); 196652419Sjulian CI->setTailCallKind(ChildTCK); 196752419Sjulian InlinedMustTailCalls |= CI->isMustTailCall(); 196852419Sjulian 196952419Sjulian // Calls inlined through a 'nounwind' call site should be marked 197052419Sjulian // 'nounwind'. 197152419Sjulian if (MarkNoUnwind) 197252419Sjulian CI->setDoesNotThrow(); 197352419Sjulian } 197452419Sjulian } 197552419Sjulian } 197652419Sjulian 197752419Sjulian // Leave lifetime markers for the static alloca's, scoping them to the 197852419Sjulian // function we just inlined. 197952419Sjulian if (InsertLifetime && !IFI.StaticAllocas.empty()) { 198052419Sjulian IRBuilder<> builder(&FirstNewBlock->front()); 198152419Sjulian for (unsigned ai = 0, ae = IFI.StaticAllocas.size(); ai != ae; ++ai) { 198252419Sjulian AllocaInst *AI = IFI.StaticAllocas[ai]; 198352419Sjulian // Don't mark swifterror allocas. They can't have bitcast uses. 198452419Sjulian if (AI->isSwiftError()) 198559728Sjulian continue; 198652419Sjulian 198759728Sjulian // If the alloca is already scoped to something smaller than the whole 198859728Sjulian // function then there's no need to add redundant, less accurate markers. 198959728Sjulian if (hasLifetimeMarkers(AI)) 199059728Sjulian continue; 199159728Sjulian 199259728Sjulian // Try to determine the size of the allocation. 199359728Sjulian ConstantInt *AllocaSize = nullptr; 199459728Sjulian if (ConstantInt *AIArraySize = 199559728Sjulian dyn_cast<ConstantInt>(AI->getArraySize())) { 199659728Sjulian auto &DL = Caller->getParent()->getDataLayout(); 199759728Sjulian Type *AllocaType = AI->getAllocatedType(); 199859728Sjulian uint64_t AllocaTypeSize = DL.getTypeAllocSize(AllocaType); 199952419Sjulian uint64_t AllocaArraySize = AIArraySize->getLimitedValue(); 200052419Sjulian 200152419Sjulian // Don't add markers for zero-sized allocas. 200252419Sjulian if (AllocaArraySize == 0) 200359728Sjulian continue; 200452419Sjulian 200552419Sjulian // Check that array size doesn't saturate uint64_t and doesn't 200652419Sjulian // overflow when it's multiplied by type size. 200752419Sjulian if (AllocaArraySize != std::numeric_limits<uint64_t>::max() && 200852419Sjulian std::numeric_limits<uint64_t>::max() / AllocaArraySize >= 200952419Sjulian AllocaTypeSize) { 201052419Sjulian AllocaSize = ConstantInt::get(Type::getInt64Ty(AI->getContext()), 201152419Sjulian AllocaArraySize * AllocaTypeSize); 201252419Sjulian } 201352419Sjulian } 201452419Sjulian 201552419Sjulian builder.CreateLifetimeStart(AI, AllocaSize); 2016 for (ReturnInst *RI : Returns) { 2017 // Don't insert llvm.lifetime.end calls between a musttail or deoptimize 2018 // call and a return. The return kills all local allocas. 2019 if (InlinedMustTailCalls && 2020 RI->getParent()->getTerminatingMustTailCall()) 2021 continue; 2022 if (InlinedDeoptimizeCalls && 2023 RI->getParent()->getTerminatingDeoptimizeCall()) 2024 continue; 2025 IRBuilder<>(RI).CreateLifetimeEnd(AI, AllocaSize); 2026 } 2027 } 2028 } 2029 2030 // If the inlined code contained dynamic alloca instructions, wrap the inlined 2031 // code with llvm.stacksave/llvm.stackrestore intrinsics. 2032 if (InlinedFunctionInfo.ContainsDynamicAllocas) { 2033 Module *M = Caller->getParent(); 2034 // Get the two intrinsics we care about. 2035 Function *StackSave = Intrinsic::getDeclaration(M, Intrinsic::stacksave); 2036 Function *StackRestore=Intrinsic::getDeclaration(M,Intrinsic::stackrestore); 2037 2038 // Insert the llvm.stacksave. 2039 CallInst *SavedPtr = IRBuilder<>(&*FirstNewBlock, FirstNewBlock->begin()) 2040 .CreateCall(StackSave, {}, "savedstack"); 2041 2042 // Insert a call to llvm.stackrestore before any return instructions in the 2043 // inlined function. 2044 for (ReturnInst *RI : Returns) { 2045 // Don't insert llvm.stackrestore calls between a musttail or deoptimize 2046 // call and a return. The return will restore the stack pointer. 2047 if (InlinedMustTailCalls && RI->getParent()->getTerminatingMustTailCall()) 2048 continue; 2049 if (InlinedDeoptimizeCalls && RI->getParent()->getTerminatingDeoptimizeCall()) 2050 continue; 2051 IRBuilder<>(RI).CreateCall(StackRestore, SavedPtr); 2052 } 2053 } 2054 2055 // If we are inlining for an invoke instruction, we must make sure to rewrite 2056 // any call instructions into invoke instructions. This is sensitive to which 2057 // funclet pads were top-level in the inlinee, so must be done before 2058 // rewriting the "parent pad" links. 2059 if (auto *II = dyn_cast<InvokeInst>(TheCall)) { 2060 BasicBlock *UnwindDest = II->getUnwindDest(); 2061 Instruction *FirstNonPHI = UnwindDest->getFirstNonPHI(); 2062 if (isa<LandingPadInst>(FirstNonPHI)) { 2063 HandleInlinedLandingPad(II, &*FirstNewBlock, InlinedFunctionInfo); 2064 } else { 2065 HandleInlinedEHPad(II, &*FirstNewBlock, InlinedFunctionInfo); 2066 } 2067 } 2068 2069 // Update the lexical scopes of the new funclets and callsites. 2070 // Anything that had 'none' as its parent is now nested inside the callsite's 2071 // EHPad. 2072 2073 if (CallSiteEHPad) { 2074 for (Function::iterator BB = FirstNewBlock->getIterator(), 2075 E = Caller->end(); 2076 BB != E; ++BB) { 2077 // Add bundle operands to any top-level call sites. 2078 SmallVector<OperandBundleDef, 1> OpBundles; 2079 for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;) { 2080 Instruction *I = &*BBI++; 2081 CallSite CS(I); 2082 if (!CS) 2083 continue; 2084 2085 // Skip call sites which are nounwind intrinsics. 2086 auto *CalledFn = 2087 dyn_cast<Function>(CS.getCalledValue()->stripPointerCasts()); 2088 if (CalledFn && CalledFn->isIntrinsic() && CS.doesNotThrow()) 2089 continue; 2090 2091 // Skip call sites which already have a "funclet" bundle. 2092 if (CS.getOperandBundle(LLVMContext::OB_funclet)) 2093 continue; 2094 2095 CS.getOperandBundlesAsDefs(OpBundles); 2096 OpBundles.emplace_back("funclet", CallSiteEHPad); 2097 2098 Instruction *NewInst; 2099 if (CS.isCall()) 2100 NewInst = CallInst::Create(cast<CallInst>(I), OpBundles, I); 2101 else if (CS.isCallBr()) 2102 NewInst = CallBrInst::Create(cast<CallBrInst>(I), OpBundles, I); 2103 else 2104 NewInst = InvokeInst::Create(cast<InvokeInst>(I), OpBundles, I); 2105 NewInst->takeName(I); 2106 I->replaceAllUsesWith(NewInst); 2107 I->eraseFromParent(); 2108 2109 OpBundles.clear(); 2110 } 2111 2112 // It is problematic if the inlinee has a cleanupret which unwinds to 2113 // caller and we inline it into a call site which doesn't unwind but into 2114 // an EH pad that does. Such an edge must be dynamically unreachable. 2115 // As such, we replace the cleanupret with unreachable. 2116 if (auto *CleanupRet = dyn_cast<CleanupReturnInst>(BB->getTerminator())) 2117 if (CleanupRet->unwindsToCaller() && EHPadForCallUnwindsLocally) 2118 changeToUnreachable(CleanupRet, /*UseLLVMTrap=*/false); 2119 2120 Instruction *I = BB->getFirstNonPHI(); 2121 if (!I->isEHPad()) 2122 continue; 2123 2124 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(I)) { 2125 if (isa<ConstantTokenNone>(CatchSwitch->getParentPad())) 2126 CatchSwitch->setParentPad(CallSiteEHPad); 2127 } else { 2128 auto *FPI = cast<FuncletPadInst>(I); 2129 if (isa<ConstantTokenNone>(FPI->getParentPad())) 2130 FPI->setParentPad(CallSiteEHPad); 2131 } 2132 } 2133 } 2134 2135 if (InlinedDeoptimizeCalls) { 2136 // We need to at least remove the deoptimizing returns from the Return set, 2137 // so that the control flow from those returns does not get merged into the 2138 // caller (but terminate it instead). If the caller's return type does not 2139 // match the callee's return type, we also need to change the return type of 2140 // the intrinsic. 2141 if (Caller->getReturnType() == TheCall->getType()) { 2142 auto NewEnd = llvm::remove_if(Returns, [](ReturnInst *RI) { 2143 return RI->getParent()->getTerminatingDeoptimizeCall() != nullptr; 2144 }); 2145 Returns.erase(NewEnd, Returns.end()); 2146 } else { 2147 SmallVector<ReturnInst *, 8> NormalReturns; 2148 Function *NewDeoptIntrinsic = Intrinsic::getDeclaration( 2149 Caller->getParent(), Intrinsic::experimental_deoptimize, 2150 {Caller->getReturnType()}); 2151 2152 for (ReturnInst *RI : Returns) { 2153 CallInst *DeoptCall = RI->getParent()->getTerminatingDeoptimizeCall(); 2154 if (!DeoptCall) { 2155 NormalReturns.push_back(RI); 2156 continue; 2157 } 2158 2159 // The calling convention on the deoptimize call itself may be bogus, 2160 // since the code we're inlining may have undefined behavior (and may 2161 // never actually execute at runtime); but all 2162 // @llvm.experimental.deoptimize declarations have to have the same 2163 // calling convention in a well-formed module. 2164 auto CallingConv = DeoptCall->getCalledFunction()->getCallingConv(); 2165 NewDeoptIntrinsic->setCallingConv(CallingConv); 2166 auto *CurBB = RI->getParent(); 2167 RI->eraseFromParent(); 2168 2169 SmallVector<Value *, 4> CallArgs(DeoptCall->arg_begin(), 2170 DeoptCall->arg_end()); 2171 2172 SmallVector<OperandBundleDef, 1> OpBundles; 2173 DeoptCall->getOperandBundlesAsDefs(OpBundles); 2174 DeoptCall->eraseFromParent(); 2175 assert(!OpBundles.empty() && 2176 "Expected at least the deopt operand bundle"); 2177 2178 IRBuilder<> Builder(CurBB); 2179 CallInst *NewDeoptCall = 2180 Builder.CreateCall(NewDeoptIntrinsic, CallArgs, OpBundles); 2181 NewDeoptCall->setCallingConv(CallingConv); 2182 if (NewDeoptCall->getType()->isVoidTy()) 2183 Builder.CreateRetVoid(); 2184 else 2185 Builder.CreateRet(NewDeoptCall); 2186 } 2187 2188 // Leave behind the normal returns so we can merge control flow. 2189 std::swap(Returns, NormalReturns); 2190 } 2191 } 2192 2193 // Handle any inlined musttail call sites. In order for a new call site to be 2194 // musttail, the source of the clone and the inlined call site must have been 2195 // musttail. Therefore it's safe to return without merging control into the 2196 // phi below. 2197 if (InlinedMustTailCalls) { 2198 // Check if we need to bitcast the result of any musttail calls. 2199 Type *NewRetTy = Caller->getReturnType(); 2200 bool NeedBitCast = !TheCall->use_empty() && TheCall->getType() != NewRetTy; 2201 2202 // Handle the returns preceded by musttail calls separately. 2203 SmallVector<ReturnInst *, 8> NormalReturns; 2204 for (ReturnInst *RI : Returns) { 2205 CallInst *ReturnedMustTail = 2206 RI->getParent()->getTerminatingMustTailCall(); 2207 if (!ReturnedMustTail) { 2208 NormalReturns.push_back(RI); 2209 continue; 2210 } 2211 if (!NeedBitCast) 2212 continue; 2213 2214 // Delete the old return and any preceding bitcast. 2215 BasicBlock *CurBB = RI->getParent(); 2216 auto *OldCast = dyn_cast_or_null<BitCastInst>(RI->getReturnValue()); 2217 RI->eraseFromParent(); 2218 if (OldCast) 2219 OldCast->eraseFromParent(); 2220 2221 // Insert a new bitcast and return with the right type. 2222 IRBuilder<> Builder(CurBB); 2223 Builder.CreateRet(Builder.CreateBitCast(ReturnedMustTail, NewRetTy)); 2224 } 2225 2226 // Leave behind the normal returns so we can merge control flow. 2227 std::swap(Returns, NormalReturns); 2228 } 2229 2230 // Now that all of the transforms on the inlined code have taken place but 2231 // before we splice the inlined code into the CFG and lose track of which 2232 // blocks were actually inlined, collect the call sites. We only do this if 2233 // call graph updates weren't requested, as those provide value handle based 2234 // tracking of inlined call sites instead. 2235 if (InlinedFunctionInfo.ContainsCalls && !IFI.CG) { 2236 // Otherwise just collect the raw call sites that were inlined. 2237 for (BasicBlock &NewBB : 2238 make_range(FirstNewBlock->getIterator(), Caller->end())) 2239 for (Instruction &I : NewBB) 2240 if (auto CS = CallSite(&I)) 2241 IFI.InlinedCallSites.push_back(CS); 2242 } 2243 2244 // If we cloned in _exactly one_ basic block, and if that block ends in a 2245 // return instruction, we splice the body of the inlined callee directly into 2246 // the calling basic block. 2247 if (Returns.size() == 1 && std::distance(FirstNewBlock, Caller->end()) == 1) { 2248 // Move all of the instructions right before the call. 2249 OrigBB->getInstList().splice(TheCall->getIterator(), 2250 FirstNewBlock->getInstList(), 2251 FirstNewBlock->begin(), FirstNewBlock->end()); 2252 // Remove the cloned basic block. 2253 Caller->getBasicBlockList().pop_back(); 2254 2255 // If the call site was an invoke instruction, add a branch to the normal 2256 // destination. 2257 if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) { 2258 BranchInst *NewBr = BranchInst::Create(II->getNormalDest(), TheCall); 2259 NewBr->setDebugLoc(Returns[0]->getDebugLoc()); 2260 } 2261 2262 // If the return instruction returned a value, replace uses of the call with 2263 // uses of the returned value. 2264 if (!TheCall->use_empty()) { 2265 ReturnInst *R = Returns[0]; 2266 if (TheCall == R->getReturnValue()) 2267 TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType())); 2268 else 2269 TheCall->replaceAllUsesWith(R->getReturnValue()); 2270 } 2271 // Since we are now done with the Call/Invoke, we can delete it. 2272 TheCall->eraseFromParent(); 2273 2274 // Since we are now done with the return instruction, delete it also. 2275 Returns[0]->eraseFromParent(); 2276 2277 // We are now done with the inlining. 2278 return true; 2279 } 2280 2281 // Otherwise, we have the normal case, of more than one block to inline or 2282 // multiple return sites. 2283 2284 // We want to clone the entire callee function into the hole between the 2285 // "starter" and "ender" blocks. How we accomplish this depends on whether 2286 // this is an invoke instruction or a call instruction. 2287 BasicBlock *AfterCallBB; 2288 BranchInst *CreatedBranchToNormalDest = nullptr; 2289 if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) { 2290 2291 // Add an unconditional branch to make this look like the CallInst case... 2292 CreatedBranchToNormalDest = BranchInst::Create(II->getNormalDest(), TheCall); 2293 2294 // Split the basic block. This guarantees that no PHI nodes will have to be 2295 // updated due to new incoming edges, and make the invoke case more 2296 // symmetric to the call case. 2297 AfterCallBB = 2298 OrigBB->splitBasicBlock(CreatedBranchToNormalDest->getIterator(), 2299 CalledFunc->getName() + ".exit"); 2300 2301 } else { // It's a call 2302 // If this is a call instruction, we need to split the basic block that 2303 // the call lives in. 2304 // 2305 AfterCallBB = OrigBB->splitBasicBlock(TheCall->getIterator(), 2306 CalledFunc->getName() + ".exit"); 2307 } 2308 2309 if (IFI.CallerBFI) { 2310 // Copy original BB's block frequency to AfterCallBB 2311 IFI.CallerBFI->setBlockFreq( 2312 AfterCallBB, IFI.CallerBFI->getBlockFreq(OrigBB).getFrequency()); 2313 } 2314 2315 // Change the branch that used to go to AfterCallBB to branch to the first 2316 // basic block of the inlined function. 2317 // 2318 Instruction *Br = OrigBB->getTerminator(); 2319 assert(Br && Br->getOpcode() == Instruction::Br && 2320 "splitBasicBlock broken!"); 2321 Br->setOperand(0, &*FirstNewBlock); 2322 2323 // Now that the function is correct, make it a little bit nicer. In 2324 // particular, move the basic blocks inserted from the end of the function 2325 // into the space made by splitting the source basic block. 2326 Caller->getBasicBlockList().splice(AfterCallBB->getIterator(), 2327 Caller->getBasicBlockList(), FirstNewBlock, 2328 Caller->end()); 2329 2330 // Handle all of the return instructions that we just cloned in, and eliminate 2331 // any users of the original call/invoke instruction. 2332 Type *RTy = CalledFunc->getReturnType(); 2333 2334 PHINode *PHI = nullptr; 2335 if (Returns.size() > 1) { 2336 // The PHI node should go at the front of the new basic block to merge all 2337 // possible incoming values. 2338 if (!TheCall->use_empty()) { 2339 PHI = PHINode::Create(RTy, Returns.size(), TheCall->getName(), 2340 &AfterCallBB->front()); 2341 // Anything that used the result of the function call should now use the 2342 // PHI node as their operand. 2343 TheCall->replaceAllUsesWith(PHI); 2344 } 2345 2346 // Loop over all of the return instructions adding entries to the PHI node 2347 // as appropriate. 2348 if (PHI) { 2349 for (unsigned i = 0, e = Returns.size(); i != e; ++i) { 2350 ReturnInst *RI = Returns[i]; 2351 assert(RI->getReturnValue()->getType() == PHI->getType() && 2352 "Ret value not consistent in function!"); 2353 PHI->addIncoming(RI->getReturnValue(), RI->getParent()); 2354 } 2355 } 2356 2357 // Add a branch to the merge points and remove return instructions. 2358 DebugLoc Loc; 2359 for (unsigned i = 0, e = Returns.size(); i != e; ++i) { 2360 ReturnInst *RI = Returns[i]; 2361 BranchInst* BI = BranchInst::Create(AfterCallBB, RI); 2362 Loc = RI->getDebugLoc(); 2363 BI->setDebugLoc(Loc); 2364 RI->eraseFromParent(); 2365 } 2366 // We need to set the debug location to *somewhere* inside the 2367 // inlined function. The line number may be nonsensical, but the 2368 // instruction will at least be associated with the right 2369 // function. 2370 if (CreatedBranchToNormalDest) 2371 CreatedBranchToNormalDest->setDebugLoc(Loc); 2372 } else if (!Returns.empty()) { 2373 // Otherwise, if there is exactly one return value, just replace anything 2374 // using the return value of the call with the computed value. 2375 if (!TheCall->use_empty()) { 2376 if (TheCall == Returns[0]->getReturnValue()) 2377 TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType())); 2378 else 2379 TheCall->replaceAllUsesWith(Returns[0]->getReturnValue()); 2380 } 2381 2382 // Update PHI nodes that use the ReturnBB to use the AfterCallBB. 2383 BasicBlock *ReturnBB = Returns[0]->getParent(); 2384 ReturnBB->replaceAllUsesWith(AfterCallBB); 2385 2386 // Splice the code from the return block into the block that it will return 2387 // to, which contains the code that was after the call. 2388 AfterCallBB->getInstList().splice(AfterCallBB->begin(), 2389 ReturnBB->getInstList()); 2390 2391 if (CreatedBranchToNormalDest) 2392 CreatedBranchToNormalDest->setDebugLoc(Returns[0]->getDebugLoc()); 2393 2394 // Delete the return instruction now and empty ReturnBB now. 2395 Returns[0]->eraseFromParent(); 2396 ReturnBB->eraseFromParent(); 2397 } else if (!TheCall->use_empty()) { 2398 // No returns, but something is using the return value of the call. Just 2399 // nuke the result. 2400 TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType())); 2401 } 2402 2403 // Since we are now done with the Call/Invoke, we can delete it. 2404 TheCall->eraseFromParent(); 2405 2406 // If we inlined any musttail calls and the original return is now 2407 // unreachable, delete it. It can only contain a bitcast and ret. 2408 if (InlinedMustTailCalls && pred_begin(AfterCallBB) == pred_end(AfterCallBB)) 2409 AfterCallBB->eraseFromParent(); 2410 2411 // We should always be able to fold the entry block of the function into the 2412 // single predecessor of the block... 2413 assert(cast<BranchInst>(Br)->isUnconditional() && "splitBasicBlock broken!"); 2414 BasicBlock *CalleeEntry = cast<BranchInst>(Br)->getSuccessor(0); 2415 2416 // Splice the code entry block into calling block, right before the 2417 // unconditional branch. 2418 CalleeEntry->replaceAllUsesWith(OrigBB); // Update PHI nodes 2419 OrigBB->getInstList().splice(Br->getIterator(), CalleeEntry->getInstList()); 2420 2421 // Remove the unconditional branch. 2422 OrigBB->getInstList().erase(Br); 2423 2424 // Now we can remove the CalleeEntry block, which is now empty. 2425 Caller->getBasicBlockList().erase(CalleeEntry); 2426 2427 // If we inserted a phi node, check to see if it has a single value (e.g. all 2428 // the entries are the same or undef). If so, remove the PHI so it doesn't 2429 // block other optimizations. 2430 if (PHI) { 2431 AssumptionCache *AC = 2432 IFI.GetAssumptionCache ? &(*IFI.GetAssumptionCache)(*Caller) : nullptr; 2433 auto &DL = Caller->getParent()->getDataLayout(); 2434 if (Value *V = SimplifyInstruction(PHI, {DL, nullptr, nullptr, AC})) { 2435 PHI->replaceAllUsesWith(V); 2436 PHI->eraseFromParent(); 2437 } 2438 } 2439 2440 return true; 2441} 2442