1 //===- InlineFunction.cpp - Code to perform function inlining -------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements inlining of a function into a call site, resolving 10 // parameters and the return value as appropriate. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/ADT/DenseMap.h" 15 #include "llvm/ADT/None.h" 16 #include "llvm/ADT/Optional.h" 17 #include "llvm/ADT/STLExtras.h" 18 #include "llvm/ADT/SetVector.h" 19 #include "llvm/ADT/SmallPtrSet.h" 20 #include "llvm/ADT/SmallVector.h" 21 #include "llvm/ADT/StringExtras.h" 22 #include "llvm/ADT/iterator_range.h" 23 #include "llvm/Analysis/AliasAnalysis.h" 24 #include "llvm/Analysis/AssumptionCache.h" 25 #include "llvm/Analysis/BlockFrequencyInfo.h" 26 #include "llvm/Analysis/CallGraph.h" 27 #include "llvm/Analysis/CaptureTracking.h" 28 #include "llvm/Analysis/EHPersonalities.h" 29 #include "llvm/Analysis/InstructionSimplify.h" 30 #include "llvm/Analysis/ProfileSummaryInfo.h" 31 #include "llvm/Transforms/Utils/Local.h" 32 #include "llvm/Analysis/ValueTracking.h" 33 #include "llvm/Analysis/VectorUtils.h" 34 #include "llvm/IR/Argument.h" 35 #include "llvm/IR/BasicBlock.h" 36 #include "llvm/IR/CFG.h" 37 #include "llvm/IR/Constant.h" 38 #include "llvm/IR/Constants.h" 39 #include "llvm/IR/DIBuilder.h" 40 #include "llvm/IR/DataLayout.h" 41 #include "llvm/IR/DebugInfoMetadata.h" 42 #include "llvm/IR/DebugLoc.h" 43 #include "llvm/IR/DerivedTypes.h" 44 #include "llvm/IR/Dominators.h" 45 #include "llvm/IR/Function.h" 46 #include "llvm/IR/IRBuilder.h" 47 #include "llvm/IR/InstrTypes.h" 48 #include "llvm/IR/Instruction.h" 49 #include "llvm/IR/Instructions.h" 50 #include "llvm/IR/IntrinsicInst.h" 51 #include "llvm/IR/Intrinsics.h" 52 #include "llvm/IR/LLVMContext.h" 53 #include "llvm/IR/MDBuilder.h" 54 #include "llvm/IR/Metadata.h" 55 #include "llvm/IR/Module.h" 56 #include "llvm/IR/Type.h" 57 #include "llvm/IR/User.h" 58 #include "llvm/IR/Value.h" 59 #include "llvm/Support/Casting.h" 60 #include "llvm/Support/CommandLine.h" 61 #include "llvm/Support/ErrorHandling.h" 62 #include "llvm/Transforms/Utils/AssumeBundleBuilder.h" 63 #include "llvm/Transforms/Utils/Cloning.h" 64 #include "llvm/Transforms/Utils/ValueMapper.h" 65 #include <algorithm> 66 #include <cassert> 67 #include <cstdint> 68 #include <iterator> 69 #include <limits> 70 #include <string> 71 #include <utility> 72 #include <vector> 73 74 using namespace llvm; 75 using ProfileCount = Function::ProfileCount; 76 77 static cl::opt<bool> 78 EnableNoAliasConversion("enable-noalias-to-md-conversion", cl::init(true), 79 cl::Hidden, 80 cl::desc("Convert noalias attributes to metadata during inlining.")); 81 82 static cl::opt<bool> 83 UseNoAliasIntrinsic("use-noalias-intrinsic-during-inlining", cl::Hidden, 84 cl::ZeroOrMore, cl::init(true), 85 cl::desc("Use the llvm.experimental.noalias.scope.decl " 86 "intrinsic during inlining.")); 87 88 // Disabled by default, because the added alignment assumptions may increase 89 // compile-time and block optimizations. This option is not suitable for use 90 // with frontends that emit comprehensive parameter alignment annotations. 91 static cl::opt<bool> 92 PreserveAlignmentAssumptions("preserve-alignment-assumptions-during-inlining", 93 cl::init(false), cl::Hidden, 94 cl::desc("Convert align attributes to assumptions during inlining.")); 95 96 static cl::opt<bool> UpdateReturnAttributes( 97 "update-return-attrs", cl::init(true), cl::Hidden, 98 cl::desc("Update return attributes on calls within inlined body")); 99 100 static cl::opt<unsigned> InlinerAttributeWindow( 101 "max-inst-checked-for-throw-during-inlining", cl::Hidden, 102 cl::desc("the maximum number of instructions analyzed for may throw during " 103 "attribute inference in inlined body"), 104 cl::init(4)); 105 106 namespace { 107 108 /// A class for recording information about inlining a landing pad. 109 class LandingPadInliningInfo { 110 /// Destination of the invoke's unwind. 111 BasicBlock *OuterResumeDest; 112 113 /// Destination for the callee's resume. 114 BasicBlock *InnerResumeDest = nullptr; 115 116 /// LandingPadInst associated with the invoke. 117 LandingPadInst *CallerLPad = nullptr; 118 119 /// PHI for EH values from landingpad insts. 120 PHINode *InnerEHValuesPHI = nullptr; 121 122 SmallVector<Value*, 8> UnwindDestPHIValues; 123 124 public: 125 LandingPadInliningInfo(InvokeInst *II) 126 : OuterResumeDest(II->getUnwindDest()) { 127 // If there are PHI nodes in the unwind destination block, we need to keep 128 // track of which values came into them from the invoke before removing 129 // the edge from this block. 130 BasicBlock *InvokeBB = II->getParent(); 131 BasicBlock::iterator I = OuterResumeDest->begin(); 132 for (; isa<PHINode>(I); ++I) { 133 // Save the value to use for this edge. 134 PHINode *PHI = cast<PHINode>(I); 135 UnwindDestPHIValues.push_back(PHI->getIncomingValueForBlock(InvokeBB)); 136 } 137 138 CallerLPad = cast<LandingPadInst>(I); 139 } 140 141 /// The outer unwind destination is the target of 142 /// unwind edges introduced for calls within the inlined function. 143 BasicBlock *getOuterResumeDest() const { 144 return OuterResumeDest; 145 } 146 147 BasicBlock *getInnerResumeDest(); 148 149 LandingPadInst *getLandingPadInst() const { return CallerLPad; } 150 151 /// Forward the 'resume' instruction to the caller's landing pad block. 152 /// When the landing pad block has only one predecessor, this is 153 /// a simple branch. When there is more than one predecessor, we need to 154 /// split the landing pad block after the landingpad instruction and jump 155 /// to there. 156 void forwardResume(ResumeInst *RI, 157 SmallPtrSetImpl<LandingPadInst*> &InlinedLPads); 158 159 /// Add incoming-PHI values to the unwind destination block for the given 160 /// basic block, using the values for the original invoke's source block. 161 void addIncomingPHIValuesFor(BasicBlock *BB) const { 162 addIncomingPHIValuesForInto(BB, OuterResumeDest); 163 } 164 165 void addIncomingPHIValuesForInto(BasicBlock *src, BasicBlock *dest) const { 166 BasicBlock::iterator I = dest->begin(); 167 for (unsigned i = 0, e = UnwindDestPHIValues.size(); i != e; ++i, ++I) { 168 PHINode *phi = cast<PHINode>(I); 169 phi->addIncoming(UnwindDestPHIValues[i], src); 170 } 171 } 172 }; 173 174 } // end anonymous namespace 175 176 /// Get or create a target for the branch from ResumeInsts. 177 BasicBlock *LandingPadInliningInfo::getInnerResumeDest() { 178 if (InnerResumeDest) return InnerResumeDest; 179 180 // Split the landing pad. 181 BasicBlock::iterator SplitPoint = ++CallerLPad->getIterator(); 182 InnerResumeDest = 183 OuterResumeDest->splitBasicBlock(SplitPoint, 184 OuterResumeDest->getName() + ".body"); 185 186 // The number of incoming edges we expect to the inner landing pad. 187 const unsigned PHICapacity = 2; 188 189 // Create corresponding new PHIs for all the PHIs in the outer landing pad. 190 Instruction *InsertPoint = &InnerResumeDest->front(); 191 BasicBlock::iterator I = OuterResumeDest->begin(); 192 for (unsigned i = 0, e = UnwindDestPHIValues.size(); i != e; ++i, ++I) { 193 PHINode *OuterPHI = cast<PHINode>(I); 194 PHINode *InnerPHI = PHINode::Create(OuterPHI->getType(), PHICapacity, 195 OuterPHI->getName() + ".lpad-body", 196 InsertPoint); 197 OuterPHI->replaceAllUsesWith(InnerPHI); 198 InnerPHI->addIncoming(OuterPHI, OuterResumeDest); 199 } 200 201 // Create a PHI for the exception values. 202 InnerEHValuesPHI = PHINode::Create(CallerLPad->getType(), PHICapacity, 203 "eh.lpad-body", InsertPoint); 204 CallerLPad->replaceAllUsesWith(InnerEHValuesPHI); 205 InnerEHValuesPHI->addIncoming(CallerLPad, OuterResumeDest); 206 207 // All done. 208 return InnerResumeDest; 209 } 210 211 /// Forward the 'resume' instruction to the caller's landing pad block. 212 /// When the landing pad block has only one predecessor, this is a simple 213 /// branch. When there is more than one predecessor, we need to split the 214 /// landing pad block after the landingpad instruction and jump to there. 215 void LandingPadInliningInfo::forwardResume( 216 ResumeInst *RI, SmallPtrSetImpl<LandingPadInst *> &InlinedLPads) { 217 BasicBlock *Dest = getInnerResumeDest(); 218 BasicBlock *Src = RI->getParent(); 219 220 BranchInst::Create(Dest, Src); 221 222 // Update the PHIs in the destination. They were inserted in an order which 223 // makes this work. 224 addIncomingPHIValuesForInto(Src, Dest); 225 226 InnerEHValuesPHI->addIncoming(RI->getOperand(0), Src); 227 RI->eraseFromParent(); 228 } 229 230 /// Helper for getUnwindDestToken/getUnwindDestTokenHelper. 231 static Value *getParentPad(Value *EHPad) { 232 if (auto *FPI = dyn_cast<FuncletPadInst>(EHPad)) 233 return FPI->getParentPad(); 234 return cast<CatchSwitchInst>(EHPad)->getParentPad(); 235 } 236 237 using UnwindDestMemoTy = DenseMap<Instruction *, Value *>; 238 239 /// Helper for getUnwindDestToken that does the descendant-ward part of 240 /// the search. 241 static Value *getUnwindDestTokenHelper(Instruction *EHPad, 242 UnwindDestMemoTy &MemoMap) { 243 SmallVector<Instruction *, 8> Worklist(1, EHPad); 244 245 while (!Worklist.empty()) { 246 Instruction *CurrentPad = Worklist.pop_back_val(); 247 // We only put pads on the worklist that aren't in the MemoMap. When 248 // we find an unwind dest for a pad we may update its ancestors, but 249 // the queue only ever contains uncles/great-uncles/etc. of CurrentPad, 250 // so they should never get updated while queued on the worklist. 251 assert(!MemoMap.count(CurrentPad)); 252 Value *UnwindDestToken = nullptr; 253 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(CurrentPad)) { 254 if (CatchSwitch->hasUnwindDest()) { 255 UnwindDestToken = CatchSwitch->getUnwindDest()->getFirstNonPHI(); 256 } else { 257 // Catchswitch doesn't have a 'nounwind' variant, and one might be 258 // annotated as "unwinds to caller" when really it's nounwind (see 259 // e.g. SimplifyCFGOpt::SimplifyUnreachable), so we can't infer the 260 // parent's unwind dest from this. We can check its catchpads' 261 // descendants, since they might include a cleanuppad with an 262 // "unwinds to caller" cleanupret, which can be trusted. 263 for (auto HI = CatchSwitch->handler_begin(), 264 HE = CatchSwitch->handler_end(); 265 HI != HE && !UnwindDestToken; ++HI) { 266 BasicBlock *HandlerBlock = *HI; 267 auto *CatchPad = cast<CatchPadInst>(HandlerBlock->getFirstNonPHI()); 268 for (User *Child : CatchPad->users()) { 269 // Intentionally ignore invokes here -- since the catchswitch is 270 // marked "unwind to caller", it would be a verifier error if it 271 // contained an invoke which unwinds out of it, so any invoke we'd 272 // encounter must unwind to some child of the catch. 273 if (!isa<CleanupPadInst>(Child) && !isa<CatchSwitchInst>(Child)) 274 continue; 275 276 Instruction *ChildPad = cast<Instruction>(Child); 277 auto Memo = MemoMap.find(ChildPad); 278 if (Memo == MemoMap.end()) { 279 // Haven't figured out this child pad yet; queue it. 280 Worklist.push_back(ChildPad); 281 continue; 282 } 283 // We've already checked this child, but might have found that 284 // it offers no proof either way. 285 Value *ChildUnwindDestToken = Memo->second; 286 if (!ChildUnwindDestToken) 287 continue; 288 // We already know the child's unwind dest, which can either 289 // be ConstantTokenNone to indicate unwind to caller, or can 290 // be another child of the catchpad. Only the former indicates 291 // the unwind dest of the catchswitch. 292 if (isa<ConstantTokenNone>(ChildUnwindDestToken)) { 293 UnwindDestToken = ChildUnwindDestToken; 294 break; 295 } 296 assert(getParentPad(ChildUnwindDestToken) == CatchPad); 297 } 298 } 299 } 300 } else { 301 auto *CleanupPad = cast<CleanupPadInst>(CurrentPad); 302 for (User *U : CleanupPad->users()) { 303 if (auto *CleanupRet = dyn_cast<CleanupReturnInst>(U)) { 304 if (BasicBlock *RetUnwindDest = CleanupRet->getUnwindDest()) 305 UnwindDestToken = RetUnwindDest->getFirstNonPHI(); 306 else 307 UnwindDestToken = ConstantTokenNone::get(CleanupPad->getContext()); 308 break; 309 } 310 Value *ChildUnwindDestToken; 311 if (auto *Invoke = dyn_cast<InvokeInst>(U)) { 312 ChildUnwindDestToken = Invoke->getUnwindDest()->getFirstNonPHI(); 313 } else if (isa<CleanupPadInst>(U) || isa<CatchSwitchInst>(U)) { 314 Instruction *ChildPad = cast<Instruction>(U); 315 auto Memo = MemoMap.find(ChildPad); 316 if (Memo == MemoMap.end()) { 317 // Haven't resolved this child yet; queue it and keep searching. 318 Worklist.push_back(ChildPad); 319 continue; 320 } 321 // We've checked this child, but still need to ignore it if it 322 // had no proof either way. 323 ChildUnwindDestToken = Memo->second; 324 if (!ChildUnwindDestToken) 325 continue; 326 } else { 327 // Not a relevant user of the cleanuppad 328 continue; 329 } 330 // In a well-formed program, the child/invoke must either unwind to 331 // an(other) child of the cleanup, or exit the cleanup. In the 332 // first case, continue searching. 333 if (isa<Instruction>(ChildUnwindDestToken) && 334 getParentPad(ChildUnwindDestToken) == CleanupPad) 335 continue; 336 UnwindDestToken = ChildUnwindDestToken; 337 break; 338 } 339 } 340 // If we haven't found an unwind dest for CurrentPad, we may have queued its 341 // children, so move on to the next in the worklist. 342 if (!UnwindDestToken) 343 continue; 344 345 // Now we know that CurrentPad unwinds to UnwindDestToken. It also exits 346 // any ancestors of CurrentPad up to but not including UnwindDestToken's 347 // parent pad. Record this in the memo map, and check to see if the 348 // original EHPad being queried is one of the ones exited. 349 Value *UnwindParent; 350 if (auto *UnwindPad = dyn_cast<Instruction>(UnwindDestToken)) 351 UnwindParent = getParentPad(UnwindPad); 352 else 353 UnwindParent = nullptr; 354 bool ExitedOriginalPad = false; 355 for (Instruction *ExitedPad = CurrentPad; 356 ExitedPad && ExitedPad != UnwindParent; 357 ExitedPad = dyn_cast<Instruction>(getParentPad(ExitedPad))) { 358 // Skip over catchpads since they just follow their catchswitches. 359 if (isa<CatchPadInst>(ExitedPad)) 360 continue; 361 MemoMap[ExitedPad] = UnwindDestToken; 362 ExitedOriginalPad |= (ExitedPad == EHPad); 363 } 364 365 if (ExitedOriginalPad) 366 return UnwindDestToken; 367 368 // Continue the search. 369 } 370 371 // No definitive information is contained within this funclet. 372 return nullptr; 373 } 374 375 /// Given an EH pad, find where it unwinds. If it unwinds to an EH pad, 376 /// return that pad instruction. If it unwinds to caller, return 377 /// ConstantTokenNone. If it does not have a definitive unwind destination, 378 /// return nullptr. 379 /// 380 /// This routine gets invoked for calls in funclets in inlinees when inlining 381 /// an invoke. Since many funclets don't have calls inside them, it's queried 382 /// on-demand rather than building a map of pads to unwind dests up front. 383 /// Determining a funclet's unwind dest may require recursively searching its 384 /// descendants, and also ancestors and cousins if the descendants don't provide 385 /// an answer. Since most funclets will have their unwind dest immediately 386 /// available as the unwind dest of a catchswitch or cleanupret, this routine 387 /// searches top-down from the given pad and then up. To avoid worst-case 388 /// quadratic run-time given that approach, it uses a memo map to avoid 389 /// re-processing funclet trees. The callers that rewrite the IR as they go 390 /// take advantage of this, for correctness, by checking/forcing rewritten 391 /// pads' entries to match the original callee view. 392 static Value *getUnwindDestToken(Instruction *EHPad, 393 UnwindDestMemoTy &MemoMap) { 394 // Catchpads unwind to the same place as their catchswitch; 395 // redirct any queries on catchpads so the code below can 396 // deal with just catchswitches and cleanuppads. 397 if (auto *CPI = dyn_cast<CatchPadInst>(EHPad)) 398 EHPad = CPI->getCatchSwitch(); 399 400 // Check if we've already determined the unwind dest for this pad. 401 auto Memo = MemoMap.find(EHPad); 402 if (Memo != MemoMap.end()) 403 return Memo->second; 404 405 // Search EHPad and, if necessary, its descendants. 406 Value *UnwindDestToken = getUnwindDestTokenHelper(EHPad, MemoMap); 407 assert((UnwindDestToken == nullptr) != (MemoMap.count(EHPad) != 0)); 408 if (UnwindDestToken) 409 return UnwindDestToken; 410 411 // No information is available for this EHPad from itself or any of its 412 // descendants. An unwind all the way out to a pad in the caller would 413 // need also to agree with the unwind dest of the parent funclet, so 414 // search up the chain to try to find a funclet with information. Put 415 // null entries in the memo map to avoid re-processing as we go up. 416 MemoMap[EHPad] = nullptr; 417 #ifndef NDEBUG 418 SmallPtrSet<Instruction *, 4> TempMemos; 419 TempMemos.insert(EHPad); 420 #endif 421 Instruction *LastUselessPad = EHPad; 422 Value *AncestorToken; 423 for (AncestorToken = getParentPad(EHPad); 424 auto *AncestorPad = dyn_cast<Instruction>(AncestorToken); 425 AncestorToken = getParentPad(AncestorToken)) { 426 // Skip over catchpads since they just follow their catchswitches. 427 if (isa<CatchPadInst>(AncestorPad)) 428 continue; 429 // If the MemoMap had an entry mapping AncestorPad to nullptr, since we 430 // haven't yet called getUnwindDestTokenHelper for AncestorPad in this 431 // call to getUnwindDestToken, that would mean that AncestorPad had no 432 // information in itself, its descendants, or its ancestors. If that 433 // were the case, then we should also have recorded the lack of information 434 // for the descendant that we're coming from. So assert that we don't 435 // find a null entry in the MemoMap for AncestorPad. 436 assert(!MemoMap.count(AncestorPad) || MemoMap[AncestorPad]); 437 auto AncestorMemo = MemoMap.find(AncestorPad); 438 if (AncestorMemo == MemoMap.end()) { 439 UnwindDestToken = getUnwindDestTokenHelper(AncestorPad, MemoMap); 440 } else { 441 UnwindDestToken = AncestorMemo->second; 442 } 443 if (UnwindDestToken) 444 break; 445 LastUselessPad = AncestorPad; 446 MemoMap[LastUselessPad] = nullptr; 447 #ifndef NDEBUG 448 TempMemos.insert(LastUselessPad); 449 #endif 450 } 451 452 // We know that getUnwindDestTokenHelper was called on LastUselessPad and 453 // returned nullptr (and likewise for EHPad and any of its ancestors up to 454 // LastUselessPad), so LastUselessPad has no information from below. Since 455 // getUnwindDestTokenHelper must investigate all downward paths through 456 // no-information nodes to prove that a node has no information like this, 457 // and since any time it finds information it records it in the MemoMap for 458 // not just the immediately-containing funclet but also any ancestors also 459 // exited, it must be the case that, walking downward from LastUselessPad, 460 // visiting just those nodes which have not been mapped to an unwind dest 461 // by getUnwindDestTokenHelper (the nullptr TempMemos notwithstanding, since 462 // they are just used to keep getUnwindDestTokenHelper from repeating work), 463 // any node visited must have been exhaustively searched with no information 464 // for it found. 465 SmallVector<Instruction *, 8> Worklist(1, LastUselessPad); 466 while (!Worklist.empty()) { 467 Instruction *UselessPad = Worklist.pop_back_val(); 468 auto Memo = MemoMap.find(UselessPad); 469 if (Memo != MemoMap.end() && Memo->second) { 470 // Here the name 'UselessPad' is a bit of a misnomer, because we've found 471 // that it is a funclet that does have information about unwinding to 472 // a particular destination; its parent was a useless pad. 473 // Since its parent has no information, the unwind edge must not escape 474 // the parent, and must target a sibling of this pad. This local unwind 475 // gives us no information about EHPad. Leave it and the subtree rooted 476 // at it alone. 477 assert(getParentPad(Memo->second) == getParentPad(UselessPad)); 478 continue; 479 } 480 // We know we don't have information for UselesPad. If it has an entry in 481 // the MemoMap (mapping it to nullptr), it must be one of the TempMemos 482 // added on this invocation of getUnwindDestToken; if a previous invocation 483 // recorded nullptr, it would have had to prove that the ancestors of 484 // UselessPad, which include LastUselessPad, had no information, and that 485 // in turn would have required proving that the descendants of 486 // LastUselesPad, which include EHPad, have no information about 487 // LastUselessPad, which would imply that EHPad was mapped to nullptr in 488 // the MemoMap on that invocation, which isn't the case if we got here. 489 assert(!MemoMap.count(UselessPad) || TempMemos.count(UselessPad)); 490 // Assert as we enumerate users that 'UselessPad' doesn't have any unwind 491 // information that we'd be contradicting by making a map entry for it 492 // (which is something that getUnwindDestTokenHelper must have proved for 493 // us to get here). Just assert on is direct users here; the checks in 494 // this downward walk at its descendants will verify that they don't have 495 // any unwind edges that exit 'UselessPad' either (i.e. they either have no 496 // unwind edges or unwind to a sibling). 497 MemoMap[UselessPad] = UnwindDestToken; 498 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(UselessPad)) { 499 assert(CatchSwitch->getUnwindDest() == nullptr && "Expected useless pad"); 500 for (BasicBlock *HandlerBlock : CatchSwitch->handlers()) { 501 auto *CatchPad = HandlerBlock->getFirstNonPHI(); 502 for (User *U : CatchPad->users()) { 503 assert( 504 (!isa<InvokeInst>(U) || 505 (getParentPad( 506 cast<InvokeInst>(U)->getUnwindDest()->getFirstNonPHI()) == 507 CatchPad)) && 508 "Expected useless pad"); 509 if (isa<CatchSwitchInst>(U) || isa<CleanupPadInst>(U)) 510 Worklist.push_back(cast<Instruction>(U)); 511 } 512 } 513 } else { 514 assert(isa<CleanupPadInst>(UselessPad)); 515 for (User *U : UselessPad->users()) { 516 assert(!isa<CleanupReturnInst>(U) && "Expected useless pad"); 517 assert((!isa<InvokeInst>(U) || 518 (getParentPad( 519 cast<InvokeInst>(U)->getUnwindDest()->getFirstNonPHI()) == 520 UselessPad)) && 521 "Expected useless pad"); 522 if (isa<CatchSwitchInst>(U) || isa<CleanupPadInst>(U)) 523 Worklist.push_back(cast<Instruction>(U)); 524 } 525 } 526 } 527 528 return UnwindDestToken; 529 } 530 531 /// When we inline a basic block into an invoke, 532 /// we have to turn all of the calls that can throw into invokes. 533 /// This function analyze BB to see if there are any calls, and if so, 534 /// it rewrites them to be invokes that jump to InvokeDest and fills in the PHI 535 /// nodes in that block with the values specified in InvokeDestPHIValues. 536 static BasicBlock *HandleCallsInBlockInlinedThroughInvoke( 537 BasicBlock *BB, BasicBlock *UnwindEdge, 538 UnwindDestMemoTy *FuncletUnwindMap = nullptr) { 539 for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) { 540 Instruction *I = &*BBI++; 541 542 // We only need to check for function calls: inlined invoke 543 // instructions require no special handling. 544 CallInst *CI = dyn_cast<CallInst>(I); 545 546 if (!CI || CI->doesNotThrow() || CI->isInlineAsm()) 547 continue; 548 549 // We do not need to (and in fact, cannot) convert possibly throwing calls 550 // to @llvm.experimental_deoptimize (resp. @llvm.experimental.guard) into 551 // invokes. The caller's "segment" of the deoptimization continuation 552 // attached to the newly inlined @llvm.experimental_deoptimize 553 // (resp. @llvm.experimental.guard) call should contain the exception 554 // handling logic, if any. 555 if (auto *F = CI->getCalledFunction()) 556 if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize || 557 F->getIntrinsicID() == Intrinsic::experimental_guard) 558 continue; 559 560 if (auto FuncletBundle = CI->getOperandBundle(LLVMContext::OB_funclet)) { 561 // This call is nested inside a funclet. If that funclet has an unwind 562 // destination within the inlinee, then unwinding out of this call would 563 // be UB. Rewriting this call to an invoke which targets the inlined 564 // invoke's unwind dest would give the call's parent funclet multiple 565 // unwind destinations, which is something that subsequent EH table 566 // generation can't handle and that the veirifer rejects. So when we 567 // see such a call, leave it as a call. 568 auto *FuncletPad = cast<Instruction>(FuncletBundle->Inputs[0]); 569 Value *UnwindDestToken = 570 getUnwindDestToken(FuncletPad, *FuncletUnwindMap); 571 if (UnwindDestToken && !isa<ConstantTokenNone>(UnwindDestToken)) 572 continue; 573 #ifndef NDEBUG 574 Instruction *MemoKey; 575 if (auto *CatchPad = dyn_cast<CatchPadInst>(FuncletPad)) 576 MemoKey = CatchPad->getCatchSwitch(); 577 else 578 MemoKey = FuncletPad; 579 assert(FuncletUnwindMap->count(MemoKey) && 580 (*FuncletUnwindMap)[MemoKey] == UnwindDestToken && 581 "must get memoized to avoid confusing later searches"); 582 #endif // NDEBUG 583 } 584 585 changeToInvokeAndSplitBasicBlock(CI, UnwindEdge); 586 return BB; 587 } 588 return nullptr; 589 } 590 591 /// If we inlined an invoke site, we need to convert calls 592 /// in the body of the inlined function into invokes. 593 /// 594 /// II is the invoke instruction being inlined. FirstNewBlock is the first 595 /// block of the inlined code (the last block is the end of the function), 596 /// and InlineCodeInfo is information about the code that got inlined. 597 static void HandleInlinedLandingPad(InvokeInst *II, BasicBlock *FirstNewBlock, 598 ClonedCodeInfo &InlinedCodeInfo) { 599 BasicBlock *InvokeDest = II->getUnwindDest(); 600 601 Function *Caller = FirstNewBlock->getParent(); 602 603 // The inlined code is currently at the end of the function, scan from the 604 // start of the inlined code to its end, checking for stuff we need to 605 // rewrite. 606 LandingPadInliningInfo Invoke(II); 607 608 // Get all of the inlined landing pad instructions. 609 SmallPtrSet<LandingPadInst*, 16> InlinedLPads; 610 for (Function::iterator I = FirstNewBlock->getIterator(), E = Caller->end(); 611 I != E; ++I) 612 if (InvokeInst *II = dyn_cast<InvokeInst>(I->getTerminator())) 613 InlinedLPads.insert(II->getLandingPadInst()); 614 615 // Append the clauses from the outer landing pad instruction into the inlined 616 // landing pad instructions. 617 LandingPadInst *OuterLPad = Invoke.getLandingPadInst(); 618 for (LandingPadInst *InlinedLPad : InlinedLPads) { 619 unsigned OuterNum = OuterLPad->getNumClauses(); 620 InlinedLPad->reserveClauses(OuterNum); 621 for (unsigned OuterIdx = 0; OuterIdx != OuterNum; ++OuterIdx) 622 InlinedLPad->addClause(OuterLPad->getClause(OuterIdx)); 623 if (OuterLPad->isCleanup()) 624 InlinedLPad->setCleanup(true); 625 } 626 627 for (Function::iterator BB = FirstNewBlock->getIterator(), E = Caller->end(); 628 BB != E; ++BB) { 629 if (InlinedCodeInfo.ContainsCalls) 630 if (BasicBlock *NewBB = HandleCallsInBlockInlinedThroughInvoke( 631 &*BB, Invoke.getOuterResumeDest())) 632 // Update any PHI nodes in the exceptional block to indicate that there 633 // is now a new entry in them. 634 Invoke.addIncomingPHIValuesFor(NewBB); 635 636 // Forward any resumes that are remaining here. 637 if (ResumeInst *RI = dyn_cast<ResumeInst>(BB->getTerminator())) 638 Invoke.forwardResume(RI, InlinedLPads); 639 } 640 641 // Now that everything is happy, we have one final detail. The PHI nodes in 642 // the exception destination block still have entries due to the original 643 // invoke instruction. Eliminate these entries (which might even delete the 644 // PHI node) now. 645 InvokeDest->removePredecessor(II->getParent()); 646 } 647 648 /// If we inlined an invoke site, we need to convert calls 649 /// in the body of the inlined function into invokes. 650 /// 651 /// II is the invoke instruction being inlined. FirstNewBlock is the first 652 /// block of the inlined code (the last block is the end of the function), 653 /// and InlineCodeInfo is information about the code that got inlined. 654 static void HandleInlinedEHPad(InvokeInst *II, BasicBlock *FirstNewBlock, 655 ClonedCodeInfo &InlinedCodeInfo) { 656 BasicBlock *UnwindDest = II->getUnwindDest(); 657 Function *Caller = FirstNewBlock->getParent(); 658 659 assert(UnwindDest->getFirstNonPHI()->isEHPad() && "unexpected BasicBlock!"); 660 661 // If there are PHI nodes in the unwind destination block, we need to keep 662 // track of which values came into them from the invoke before removing the 663 // edge from this block. 664 SmallVector<Value *, 8> UnwindDestPHIValues; 665 BasicBlock *InvokeBB = II->getParent(); 666 for (Instruction &I : *UnwindDest) { 667 // Save the value to use for this edge. 668 PHINode *PHI = dyn_cast<PHINode>(&I); 669 if (!PHI) 670 break; 671 UnwindDestPHIValues.push_back(PHI->getIncomingValueForBlock(InvokeBB)); 672 } 673 674 // Add incoming-PHI values to the unwind destination block for the given basic 675 // block, using the values for the original invoke's source block. 676 auto UpdatePHINodes = [&](BasicBlock *Src) { 677 BasicBlock::iterator I = UnwindDest->begin(); 678 for (Value *V : UnwindDestPHIValues) { 679 PHINode *PHI = cast<PHINode>(I); 680 PHI->addIncoming(V, Src); 681 ++I; 682 } 683 }; 684 685 // This connects all the instructions which 'unwind to caller' to the invoke 686 // destination. 687 UnwindDestMemoTy FuncletUnwindMap; 688 for (Function::iterator BB = FirstNewBlock->getIterator(), E = Caller->end(); 689 BB != E; ++BB) { 690 if (auto *CRI = dyn_cast<CleanupReturnInst>(BB->getTerminator())) { 691 if (CRI->unwindsToCaller()) { 692 auto *CleanupPad = CRI->getCleanupPad(); 693 CleanupReturnInst::Create(CleanupPad, UnwindDest, CRI); 694 CRI->eraseFromParent(); 695 UpdatePHINodes(&*BB); 696 // Finding a cleanupret with an unwind destination would confuse 697 // subsequent calls to getUnwindDestToken, so map the cleanuppad 698 // to short-circuit any such calls and recognize this as an "unwind 699 // to caller" cleanup. 700 assert(!FuncletUnwindMap.count(CleanupPad) || 701 isa<ConstantTokenNone>(FuncletUnwindMap[CleanupPad])); 702 FuncletUnwindMap[CleanupPad] = 703 ConstantTokenNone::get(Caller->getContext()); 704 } 705 } 706 707 Instruction *I = BB->getFirstNonPHI(); 708 if (!I->isEHPad()) 709 continue; 710 711 Instruction *Replacement = nullptr; 712 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(I)) { 713 if (CatchSwitch->unwindsToCaller()) { 714 Value *UnwindDestToken; 715 if (auto *ParentPad = 716 dyn_cast<Instruction>(CatchSwitch->getParentPad())) { 717 // This catchswitch is nested inside another funclet. If that 718 // funclet has an unwind destination within the inlinee, then 719 // unwinding out of this catchswitch would be UB. Rewriting this 720 // catchswitch to unwind to the inlined invoke's unwind dest would 721 // give the parent funclet multiple unwind destinations, which is 722 // something that subsequent EH table generation can't handle and 723 // that the veirifer rejects. So when we see such a call, leave it 724 // as "unwind to caller". 725 UnwindDestToken = getUnwindDestToken(ParentPad, FuncletUnwindMap); 726 if (UnwindDestToken && !isa<ConstantTokenNone>(UnwindDestToken)) 727 continue; 728 } else { 729 // This catchswitch has no parent to inherit constraints from, and 730 // none of its descendants can have an unwind edge that exits it and 731 // targets another funclet in the inlinee. It may or may not have a 732 // descendant that definitively has an unwind to caller. In either 733 // case, we'll have to assume that any unwinds out of it may need to 734 // be routed to the caller, so treat it as though it has a definitive 735 // unwind to caller. 736 UnwindDestToken = ConstantTokenNone::get(Caller->getContext()); 737 } 738 auto *NewCatchSwitch = CatchSwitchInst::Create( 739 CatchSwitch->getParentPad(), UnwindDest, 740 CatchSwitch->getNumHandlers(), CatchSwitch->getName(), 741 CatchSwitch); 742 for (BasicBlock *PadBB : CatchSwitch->handlers()) 743 NewCatchSwitch->addHandler(PadBB); 744 // Propagate info for the old catchswitch over to the new one in 745 // the unwind map. This also serves to short-circuit any subsequent 746 // checks for the unwind dest of this catchswitch, which would get 747 // confused if they found the outer handler in the callee. 748 FuncletUnwindMap[NewCatchSwitch] = UnwindDestToken; 749 Replacement = NewCatchSwitch; 750 } 751 } else if (!isa<FuncletPadInst>(I)) { 752 llvm_unreachable("unexpected EHPad!"); 753 } 754 755 if (Replacement) { 756 Replacement->takeName(I); 757 I->replaceAllUsesWith(Replacement); 758 I->eraseFromParent(); 759 UpdatePHINodes(&*BB); 760 } 761 } 762 763 if (InlinedCodeInfo.ContainsCalls) 764 for (Function::iterator BB = FirstNewBlock->getIterator(), 765 E = Caller->end(); 766 BB != E; ++BB) 767 if (BasicBlock *NewBB = HandleCallsInBlockInlinedThroughInvoke( 768 &*BB, UnwindDest, &FuncletUnwindMap)) 769 // Update any PHI nodes in the exceptional block to indicate that there 770 // is now a new entry in them. 771 UpdatePHINodes(NewBB); 772 773 // Now that everything is happy, we have one final detail. The PHI nodes in 774 // the exception destination block still have entries due to the original 775 // invoke instruction. Eliminate these entries (which might even delete the 776 // PHI node) now. 777 UnwindDest->removePredecessor(InvokeBB); 778 } 779 780 /// When inlining a call site that has !llvm.mem.parallel_loop_access, 781 /// !llvm.access.group, !alias.scope or !noalias metadata, that metadata should 782 /// be propagated to all memory-accessing cloned instructions. 783 static void PropagateCallSiteMetadata(CallBase &CB, ValueToValueMapTy &VMap) { 784 MDNode *MemParallelLoopAccess = 785 CB.getMetadata(LLVMContext::MD_mem_parallel_loop_access); 786 MDNode *AccessGroup = CB.getMetadata(LLVMContext::MD_access_group); 787 MDNode *AliasScope = CB.getMetadata(LLVMContext::MD_alias_scope); 788 MDNode *NoAlias = CB.getMetadata(LLVMContext::MD_noalias); 789 if (!MemParallelLoopAccess && !AccessGroup && !AliasScope && !NoAlias) 790 return; 791 792 for (ValueToValueMapTy::iterator VMI = VMap.begin(), VMIE = VMap.end(); 793 VMI != VMIE; ++VMI) { 794 // Check that key is an instruction, to skip the Argument mapping, which 795 // points to an instruction in the original function, not the inlined one. 796 if (!VMI->second || !isa<Instruction>(VMI->first)) 797 continue; 798 799 Instruction *NI = dyn_cast<Instruction>(VMI->second); 800 if (!NI) 801 continue; 802 803 // This metadata is only relevant for instructions that access memory. 804 if (!NI->mayReadOrWriteMemory()) 805 continue; 806 807 if (MemParallelLoopAccess) { 808 // TODO: This probably should not overwrite MemParalleLoopAccess. 809 MemParallelLoopAccess = MDNode::concatenate( 810 NI->getMetadata(LLVMContext::MD_mem_parallel_loop_access), 811 MemParallelLoopAccess); 812 NI->setMetadata(LLVMContext::MD_mem_parallel_loop_access, 813 MemParallelLoopAccess); 814 } 815 816 if (AccessGroup) 817 NI->setMetadata(LLVMContext::MD_access_group, uniteAccessGroups( 818 NI->getMetadata(LLVMContext::MD_access_group), AccessGroup)); 819 820 if (AliasScope) 821 NI->setMetadata(LLVMContext::MD_alias_scope, MDNode::concatenate( 822 NI->getMetadata(LLVMContext::MD_alias_scope), AliasScope)); 823 824 if (NoAlias) 825 NI->setMetadata(LLVMContext::MD_noalias, MDNode::concatenate( 826 NI->getMetadata(LLVMContext::MD_noalias), NoAlias)); 827 } 828 } 829 830 /// Utility for cloning !noalias and !alias.scope metadata. When a code region 831 /// using scoped alias metadata is inlined, the aliasing relationships may not 832 /// hold between the two version. It is necessary to create a deep clone of the 833 /// metadata, putting the two versions in separate scope domains. 834 class ScopedAliasMetadataDeepCloner { 835 using MetadataMap = DenseMap<const MDNode *, TrackingMDNodeRef>; 836 SetVector<const MDNode *> MD; 837 MetadataMap MDMap; 838 void addRecursiveMetadataUses(); 839 840 public: 841 ScopedAliasMetadataDeepCloner(const Function *F); 842 843 /// Create a new clone of the scoped alias metadata, which will be used by 844 /// subsequent remap() calls. 845 void clone(); 846 847 /// Remap instructions in the given VMap from the original to the cloned 848 /// metadata. 849 void remap(ValueToValueMapTy &VMap); 850 }; 851 852 ScopedAliasMetadataDeepCloner::ScopedAliasMetadataDeepCloner( 853 const Function *F) { 854 for (const BasicBlock &BB : *F) { 855 for (const Instruction &I : BB) { 856 if (const MDNode *M = I.getMetadata(LLVMContext::MD_alias_scope)) 857 MD.insert(M); 858 if (const MDNode *M = I.getMetadata(LLVMContext::MD_noalias)) 859 MD.insert(M); 860 861 // We also need to clone the metadata in noalias intrinsics. 862 if (const auto *Decl = dyn_cast<NoAliasScopeDeclInst>(&I)) 863 MD.insert(Decl->getScopeList()); 864 } 865 } 866 addRecursiveMetadataUses(); 867 } 868 869 void ScopedAliasMetadataDeepCloner::addRecursiveMetadataUses() { 870 SmallVector<const Metadata *, 16> Queue(MD.begin(), MD.end()); 871 while (!Queue.empty()) { 872 const MDNode *M = cast<MDNode>(Queue.pop_back_val()); 873 for (const Metadata *Op : M->operands()) 874 if (const MDNode *OpMD = dyn_cast<MDNode>(Op)) 875 if (MD.insert(OpMD)) 876 Queue.push_back(OpMD); 877 } 878 } 879 880 void ScopedAliasMetadataDeepCloner::clone() { 881 assert(MDMap.empty() && "clone() already called ?"); 882 883 SmallVector<TempMDTuple, 16> DummyNodes; 884 for (const MDNode *I : MD) { 885 DummyNodes.push_back(MDTuple::getTemporary(I->getContext(), None)); 886 MDMap[I].reset(DummyNodes.back().get()); 887 } 888 889 // Create new metadata nodes to replace the dummy nodes, replacing old 890 // metadata references with either a dummy node or an already-created new 891 // node. 892 SmallVector<Metadata *, 4> NewOps; 893 for (const MDNode *I : MD) { 894 for (const Metadata *Op : I->operands()) { 895 if (const MDNode *M = dyn_cast<MDNode>(Op)) 896 NewOps.push_back(MDMap[M]); 897 else 898 NewOps.push_back(const_cast<Metadata *>(Op)); 899 } 900 901 MDNode *NewM = MDNode::get(I->getContext(), NewOps); 902 MDTuple *TempM = cast<MDTuple>(MDMap[I]); 903 assert(TempM->isTemporary() && "Expected temporary node"); 904 905 TempM->replaceAllUsesWith(NewM); 906 NewOps.clear(); 907 } 908 } 909 910 void ScopedAliasMetadataDeepCloner::remap(ValueToValueMapTy &VMap) { 911 if (MDMap.empty()) 912 return; // Nothing to do. 913 914 for (auto Entry : VMap) { 915 // Check that key is an instruction, to skip the Argument mapping, which 916 // points to an instruction in the original function, not the inlined one. 917 if (!Entry->second || !isa<Instruction>(Entry->first)) 918 continue; 919 920 Instruction *I = dyn_cast<Instruction>(Entry->second); 921 if (!I) 922 continue; 923 924 if (MDNode *M = I->getMetadata(LLVMContext::MD_alias_scope)) 925 I->setMetadata(LLVMContext::MD_alias_scope, MDMap[M]); 926 927 if (MDNode *M = I->getMetadata(LLVMContext::MD_noalias)) 928 I->setMetadata(LLVMContext::MD_noalias, MDMap[M]); 929 930 if (auto *Decl = dyn_cast<NoAliasScopeDeclInst>(I)) 931 Decl->setScopeList(MDMap[Decl->getScopeList()]); 932 } 933 } 934 935 /// If the inlined function has noalias arguments, 936 /// then add new alias scopes for each noalias argument, tag the mapped noalias 937 /// parameters with noalias metadata specifying the new scope, and tag all 938 /// non-derived loads, stores and memory intrinsics with the new alias scopes. 939 static void AddAliasScopeMetadata(CallBase &CB, ValueToValueMapTy &VMap, 940 const DataLayout &DL, AAResults *CalleeAAR) { 941 if (!EnableNoAliasConversion) 942 return; 943 944 const Function *CalledFunc = CB.getCalledFunction(); 945 SmallVector<const Argument *, 4> NoAliasArgs; 946 947 for (const Argument &Arg : CalledFunc->args()) 948 if (CB.paramHasAttr(Arg.getArgNo(), Attribute::NoAlias) && !Arg.use_empty()) 949 NoAliasArgs.push_back(&Arg); 950 951 if (NoAliasArgs.empty()) 952 return; 953 954 // To do a good job, if a noalias variable is captured, we need to know if 955 // the capture point dominates the particular use we're considering. 956 DominatorTree DT; 957 DT.recalculate(const_cast<Function&>(*CalledFunc)); 958 959 // noalias indicates that pointer values based on the argument do not alias 960 // pointer values which are not based on it. So we add a new "scope" for each 961 // noalias function argument. Accesses using pointers based on that argument 962 // become part of that alias scope, accesses using pointers not based on that 963 // argument are tagged as noalias with that scope. 964 965 DenseMap<const Argument *, MDNode *> NewScopes; 966 MDBuilder MDB(CalledFunc->getContext()); 967 968 // Create a new scope domain for this function. 969 MDNode *NewDomain = 970 MDB.createAnonymousAliasScopeDomain(CalledFunc->getName()); 971 for (unsigned i = 0, e = NoAliasArgs.size(); i != e; ++i) { 972 const Argument *A = NoAliasArgs[i]; 973 974 std::string Name = std::string(CalledFunc->getName()); 975 if (A->hasName()) { 976 Name += ": %"; 977 Name += A->getName(); 978 } else { 979 Name += ": argument "; 980 Name += utostr(i); 981 } 982 983 // Note: We always create a new anonymous root here. This is true regardless 984 // of the linkage of the callee because the aliasing "scope" is not just a 985 // property of the callee, but also all control dependencies in the caller. 986 MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name); 987 NewScopes.insert(std::make_pair(A, NewScope)); 988 989 if (UseNoAliasIntrinsic) { 990 // Introduce a llvm.experimental.noalias.scope.decl for the noalias 991 // argument. 992 MDNode *AScopeList = MDNode::get(CalledFunc->getContext(), NewScope); 993 auto *NoAliasDecl = 994 IRBuilder<>(&CB).CreateNoAliasScopeDeclaration(AScopeList); 995 // Ignore the result for now. The result will be used when the 996 // llvm.noalias intrinsic is introduced. 997 (void)NoAliasDecl; 998 } 999 } 1000 1001 // Iterate over all new instructions in the map; for all memory-access 1002 // instructions, add the alias scope metadata. 1003 for (ValueToValueMapTy::iterator VMI = VMap.begin(), VMIE = VMap.end(); 1004 VMI != VMIE; ++VMI) { 1005 if (const Instruction *I = dyn_cast<Instruction>(VMI->first)) { 1006 if (!VMI->second) 1007 continue; 1008 1009 Instruction *NI = dyn_cast<Instruction>(VMI->second); 1010 if (!NI) 1011 continue; 1012 1013 bool IsArgMemOnlyCall = false, IsFuncCall = false; 1014 SmallVector<const Value *, 2> PtrArgs; 1015 1016 if (const LoadInst *LI = dyn_cast<LoadInst>(I)) 1017 PtrArgs.push_back(LI->getPointerOperand()); 1018 else if (const StoreInst *SI = dyn_cast<StoreInst>(I)) 1019 PtrArgs.push_back(SI->getPointerOperand()); 1020 else if (const VAArgInst *VAAI = dyn_cast<VAArgInst>(I)) 1021 PtrArgs.push_back(VAAI->getPointerOperand()); 1022 else if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(I)) 1023 PtrArgs.push_back(CXI->getPointerOperand()); 1024 else if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I)) 1025 PtrArgs.push_back(RMWI->getPointerOperand()); 1026 else if (const auto *Call = dyn_cast<CallBase>(I)) { 1027 // If we know that the call does not access memory, then we'll still 1028 // know that about the inlined clone of this call site, and we don't 1029 // need to add metadata. 1030 if (Call->doesNotAccessMemory()) 1031 continue; 1032 1033 IsFuncCall = true; 1034 if (CalleeAAR) { 1035 FunctionModRefBehavior MRB = CalleeAAR->getModRefBehavior(Call); 1036 if (AAResults::onlyAccessesArgPointees(MRB)) 1037 IsArgMemOnlyCall = true; 1038 } 1039 1040 for (Value *Arg : Call->args()) { 1041 // We need to check the underlying objects of all arguments, not just 1042 // the pointer arguments, because we might be passing pointers as 1043 // integers, etc. 1044 // However, if we know that the call only accesses pointer arguments, 1045 // then we only need to check the pointer arguments. 1046 if (IsArgMemOnlyCall && !Arg->getType()->isPointerTy()) 1047 continue; 1048 1049 PtrArgs.push_back(Arg); 1050 } 1051 } 1052 1053 // If we found no pointers, then this instruction is not suitable for 1054 // pairing with an instruction to receive aliasing metadata. 1055 // However, if this is a call, this we might just alias with none of the 1056 // noalias arguments. 1057 if (PtrArgs.empty() && !IsFuncCall) 1058 continue; 1059 1060 // It is possible that there is only one underlying object, but you 1061 // need to go through several PHIs to see it, and thus could be 1062 // repeated in the Objects list. 1063 SmallPtrSet<const Value *, 4> ObjSet; 1064 SmallVector<Metadata *, 4> Scopes, NoAliases; 1065 1066 SmallSetVector<const Argument *, 4> NAPtrArgs; 1067 for (const Value *V : PtrArgs) { 1068 SmallVector<const Value *, 4> Objects; 1069 getUnderlyingObjects(V, Objects, /* LI = */ nullptr); 1070 1071 for (const Value *O : Objects) 1072 ObjSet.insert(O); 1073 } 1074 1075 // Figure out if we're derived from anything that is not a noalias 1076 // argument. 1077 bool CanDeriveViaCapture = false, UsesAliasingPtr = false; 1078 for (const Value *V : ObjSet) { 1079 // Is this value a constant that cannot be derived from any pointer 1080 // value (we need to exclude constant expressions, for example, that 1081 // are formed from arithmetic on global symbols). 1082 bool IsNonPtrConst = isa<ConstantInt>(V) || isa<ConstantFP>(V) || 1083 isa<ConstantPointerNull>(V) || 1084 isa<ConstantDataVector>(V) || isa<UndefValue>(V); 1085 if (IsNonPtrConst) 1086 continue; 1087 1088 // If this is anything other than a noalias argument, then we cannot 1089 // completely describe the aliasing properties using alias.scope 1090 // metadata (and, thus, won't add any). 1091 if (const Argument *A = dyn_cast<Argument>(V)) { 1092 if (!CB.paramHasAttr(A->getArgNo(), Attribute::NoAlias)) 1093 UsesAliasingPtr = true; 1094 } else { 1095 UsesAliasingPtr = true; 1096 } 1097 1098 // If this is not some identified function-local object (which cannot 1099 // directly alias a noalias argument), or some other argument (which, 1100 // by definition, also cannot alias a noalias argument), then we could 1101 // alias a noalias argument that has been captured). 1102 if (!isa<Argument>(V) && 1103 !isIdentifiedFunctionLocal(const_cast<Value*>(V))) 1104 CanDeriveViaCapture = true; 1105 } 1106 1107 // A function call can always get captured noalias pointers (via other 1108 // parameters, globals, etc.). 1109 if (IsFuncCall && !IsArgMemOnlyCall) 1110 CanDeriveViaCapture = true; 1111 1112 // First, we want to figure out all of the sets with which we definitely 1113 // don't alias. Iterate over all noalias set, and add those for which: 1114 // 1. The noalias argument is not in the set of objects from which we 1115 // definitely derive. 1116 // 2. The noalias argument has not yet been captured. 1117 // An arbitrary function that might load pointers could see captured 1118 // noalias arguments via other noalias arguments or globals, and so we 1119 // must always check for prior capture. 1120 for (const Argument *A : NoAliasArgs) { 1121 if (!ObjSet.count(A) && (!CanDeriveViaCapture || 1122 // It might be tempting to skip the 1123 // PointerMayBeCapturedBefore check if 1124 // A->hasNoCaptureAttr() is true, but this is 1125 // incorrect because nocapture only guarantees 1126 // that no copies outlive the function, not 1127 // that the value cannot be locally captured. 1128 !PointerMayBeCapturedBefore(A, 1129 /* ReturnCaptures */ false, 1130 /* StoreCaptures */ false, I, &DT))) 1131 NoAliases.push_back(NewScopes[A]); 1132 } 1133 1134 if (!NoAliases.empty()) 1135 NI->setMetadata(LLVMContext::MD_noalias, 1136 MDNode::concatenate( 1137 NI->getMetadata(LLVMContext::MD_noalias), 1138 MDNode::get(CalledFunc->getContext(), NoAliases))); 1139 1140 // Next, we want to figure out all of the sets to which we might belong. 1141 // We might belong to a set if the noalias argument is in the set of 1142 // underlying objects. If there is some non-noalias argument in our list 1143 // of underlying objects, then we cannot add a scope because the fact 1144 // that some access does not alias with any set of our noalias arguments 1145 // cannot itself guarantee that it does not alias with this access 1146 // (because there is some pointer of unknown origin involved and the 1147 // other access might also depend on this pointer). We also cannot add 1148 // scopes to arbitrary functions unless we know they don't access any 1149 // non-parameter pointer-values. 1150 bool CanAddScopes = !UsesAliasingPtr; 1151 if (CanAddScopes && IsFuncCall) 1152 CanAddScopes = IsArgMemOnlyCall; 1153 1154 if (CanAddScopes) 1155 for (const Argument *A : NoAliasArgs) { 1156 if (ObjSet.count(A)) 1157 Scopes.push_back(NewScopes[A]); 1158 } 1159 1160 if (!Scopes.empty()) 1161 NI->setMetadata( 1162 LLVMContext::MD_alias_scope, 1163 MDNode::concatenate(NI->getMetadata(LLVMContext::MD_alias_scope), 1164 MDNode::get(CalledFunc->getContext(), Scopes))); 1165 } 1166 } 1167 } 1168 1169 static bool MayContainThrowingOrExitingCall(Instruction *Begin, 1170 Instruction *End) { 1171 1172 assert(Begin->getParent() == End->getParent() && 1173 "Expected to be in same basic block!"); 1174 unsigned NumInstChecked = 0; 1175 // Check that all instructions in the range [Begin, End) are guaranteed to 1176 // transfer execution to successor. 1177 for (auto &I : make_range(Begin->getIterator(), End->getIterator())) 1178 if (NumInstChecked++ > InlinerAttributeWindow || 1179 !isGuaranteedToTransferExecutionToSuccessor(&I)) 1180 return true; 1181 return false; 1182 } 1183 1184 static AttrBuilder IdentifyValidAttributes(CallBase &CB) { 1185 1186 AttrBuilder AB(CB.getAttributes(), AttributeList::ReturnIndex); 1187 if (AB.empty()) 1188 return AB; 1189 AttrBuilder Valid; 1190 // Only allow these white listed attributes to be propagated back to the 1191 // callee. This is because other attributes may only be valid on the call 1192 // itself, i.e. attributes such as signext and zeroext. 1193 if (auto DerefBytes = AB.getDereferenceableBytes()) 1194 Valid.addDereferenceableAttr(DerefBytes); 1195 if (auto DerefOrNullBytes = AB.getDereferenceableOrNullBytes()) 1196 Valid.addDereferenceableOrNullAttr(DerefOrNullBytes); 1197 if (AB.contains(Attribute::NoAlias)) 1198 Valid.addAttribute(Attribute::NoAlias); 1199 if (AB.contains(Attribute::NonNull)) 1200 Valid.addAttribute(Attribute::NonNull); 1201 return Valid; 1202 } 1203 1204 static void AddReturnAttributes(CallBase &CB, ValueToValueMapTy &VMap) { 1205 if (!UpdateReturnAttributes) 1206 return; 1207 1208 AttrBuilder Valid = IdentifyValidAttributes(CB); 1209 if (Valid.empty()) 1210 return; 1211 auto *CalledFunction = CB.getCalledFunction(); 1212 auto &Context = CalledFunction->getContext(); 1213 1214 for (auto &BB : *CalledFunction) { 1215 auto *RI = dyn_cast<ReturnInst>(BB.getTerminator()); 1216 if (!RI || !isa<CallBase>(RI->getOperand(0))) 1217 continue; 1218 auto *RetVal = cast<CallBase>(RI->getOperand(0)); 1219 // Sanity check that the cloned RetVal exists and is a call, otherwise we 1220 // cannot add the attributes on the cloned RetVal. 1221 // Simplification during inlining could have transformed the cloned 1222 // instruction. 1223 auto *NewRetVal = dyn_cast_or_null<CallBase>(VMap.lookup(RetVal)); 1224 if (!NewRetVal) 1225 continue; 1226 // Backward propagation of attributes to the returned value may be incorrect 1227 // if it is control flow dependent. 1228 // Consider: 1229 // @callee { 1230 // %rv = call @foo() 1231 // %rv2 = call @bar() 1232 // if (%rv2 != null) 1233 // return %rv2 1234 // if (%rv == null) 1235 // exit() 1236 // return %rv 1237 // } 1238 // caller() { 1239 // %val = call nonnull @callee() 1240 // } 1241 // Here we cannot add the nonnull attribute on either foo or bar. So, we 1242 // limit the check to both RetVal and RI are in the same basic block and 1243 // there are no throwing/exiting instructions between these instructions. 1244 if (RI->getParent() != RetVal->getParent() || 1245 MayContainThrowingOrExitingCall(RetVal, RI)) 1246 continue; 1247 // Add to the existing attributes of NewRetVal, i.e. the cloned call 1248 // instruction. 1249 // NB! When we have the same attribute already existing on NewRetVal, but 1250 // with a differing value, the AttributeList's merge API honours the already 1251 // existing attribute value (i.e. attributes such as dereferenceable, 1252 // dereferenceable_or_null etc). See AttrBuilder::merge for more details. 1253 AttributeList AL = NewRetVal->getAttributes(); 1254 AttributeList NewAL = 1255 AL.addAttributes(Context, AttributeList::ReturnIndex, Valid); 1256 NewRetVal->setAttributes(NewAL); 1257 } 1258 } 1259 1260 /// If the inlined function has non-byval align arguments, then 1261 /// add @llvm.assume-based alignment assumptions to preserve this information. 1262 static void AddAlignmentAssumptions(CallBase &CB, InlineFunctionInfo &IFI) { 1263 if (!PreserveAlignmentAssumptions || !IFI.GetAssumptionCache) 1264 return; 1265 1266 AssumptionCache *AC = &IFI.GetAssumptionCache(*CB.getCaller()); 1267 auto &DL = CB.getCaller()->getParent()->getDataLayout(); 1268 1269 // To avoid inserting redundant assumptions, we should check for assumptions 1270 // already in the caller. To do this, we might need a DT of the caller. 1271 DominatorTree DT; 1272 bool DTCalculated = false; 1273 1274 Function *CalledFunc = CB.getCalledFunction(); 1275 for (Argument &Arg : CalledFunc->args()) { 1276 unsigned Align = Arg.getType()->isPointerTy() ? Arg.getParamAlignment() : 0; 1277 if (Align && !Arg.hasPassPointeeByValueCopyAttr() && !Arg.hasNUses(0)) { 1278 if (!DTCalculated) { 1279 DT.recalculate(*CB.getCaller()); 1280 DTCalculated = true; 1281 } 1282 1283 // If we can already prove the asserted alignment in the context of the 1284 // caller, then don't bother inserting the assumption. 1285 Value *ArgVal = CB.getArgOperand(Arg.getArgNo()); 1286 if (getKnownAlignment(ArgVal, DL, &CB, AC, &DT) >= Align) 1287 continue; 1288 1289 CallInst *NewAsmp = 1290 IRBuilder<>(&CB).CreateAlignmentAssumption(DL, ArgVal, Align); 1291 AC->registerAssumption(NewAsmp); 1292 } 1293 } 1294 } 1295 1296 /// Once we have cloned code over from a callee into the caller, 1297 /// update the specified callgraph to reflect the changes we made. 1298 /// Note that it's possible that not all code was copied over, so only 1299 /// some edges of the callgraph may remain. 1300 static void UpdateCallGraphAfterInlining(CallBase &CB, 1301 Function::iterator FirstNewBlock, 1302 ValueToValueMapTy &VMap, 1303 InlineFunctionInfo &IFI) { 1304 CallGraph &CG = *IFI.CG; 1305 const Function *Caller = CB.getCaller(); 1306 const Function *Callee = CB.getCalledFunction(); 1307 CallGraphNode *CalleeNode = CG[Callee]; 1308 CallGraphNode *CallerNode = CG[Caller]; 1309 1310 // Since we inlined some uninlined call sites in the callee into the caller, 1311 // add edges from the caller to all of the callees of the callee. 1312 CallGraphNode::iterator I = CalleeNode->begin(), E = CalleeNode->end(); 1313 1314 // Consider the case where CalleeNode == CallerNode. 1315 CallGraphNode::CalledFunctionsVector CallCache; 1316 if (CalleeNode == CallerNode) { 1317 CallCache.assign(I, E); 1318 I = CallCache.begin(); 1319 E = CallCache.end(); 1320 } 1321 1322 for (; I != E; ++I) { 1323 // Skip 'refererence' call records. 1324 if (!I->first) 1325 continue; 1326 1327 const Value *OrigCall = *I->first; 1328 1329 ValueToValueMapTy::iterator VMI = VMap.find(OrigCall); 1330 // Only copy the edge if the call was inlined! 1331 if (VMI == VMap.end() || VMI->second == nullptr) 1332 continue; 1333 1334 // If the call was inlined, but then constant folded, there is no edge to 1335 // add. Check for this case. 1336 auto *NewCall = dyn_cast<CallBase>(VMI->second); 1337 if (!NewCall) 1338 continue; 1339 1340 // We do not treat intrinsic calls like real function calls because we 1341 // expect them to become inline code; do not add an edge for an intrinsic. 1342 if (NewCall->getCalledFunction() && 1343 NewCall->getCalledFunction()->isIntrinsic()) 1344 continue; 1345 1346 // Remember that this call site got inlined for the client of 1347 // InlineFunction. 1348 IFI.InlinedCalls.push_back(NewCall); 1349 1350 // It's possible that inlining the callsite will cause it to go from an 1351 // indirect to a direct call by resolving a function pointer. If this 1352 // happens, set the callee of the new call site to a more precise 1353 // destination. This can also happen if the call graph node of the caller 1354 // was just unnecessarily imprecise. 1355 if (!I->second->getFunction()) 1356 if (Function *F = NewCall->getCalledFunction()) { 1357 // Indirect call site resolved to direct call. 1358 CallerNode->addCalledFunction(NewCall, CG[F]); 1359 1360 continue; 1361 } 1362 1363 CallerNode->addCalledFunction(NewCall, I->second); 1364 } 1365 1366 // Update the call graph by deleting the edge from Callee to Caller. We must 1367 // do this after the loop above in case Caller and Callee are the same. 1368 CallerNode->removeCallEdgeFor(*cast<CallBase>(&CB)); 1369 } 1370 1371 static void HandleByValArgumentInit(Value *Dst, Value *Src, Module *M, 1372 BasicBlock *InsertBlock, 1373 InlineFunctionInfo &IFI) { 1374 Type *AggTy = cast<PointerType>(Src->getType())->getElementType(); 1375 IRBuilder<> Builder(InsertBlock, InsertBlock->begin()); 1376 1377 Value *Size = Builder.getInt64(M->getDataLayout().getTypeStoreSize(AggTy)); 1378 1379 // Always generate a memcpy of alignment 1 here because we don't know 1380 // the alignment of the src pointer. Other optimizations can infer 1381 // better alignment. 1382 Builder.CreateMemCpy(Dst, /*DstAlign*/ Align(1), Src, 1383 /*SrcAlign*/ Align(1), Size); 1384 } 1385 1386 /// When inlining a call site that has a byval argument, 1387 /// we have to make the implicit memcpy explicit by adding it. 1388 static Value *HandleByValArgument(Value *Arg, Instruction *TheCall, 1389 const Function *CalledFunc, 1390 InlineFunctionInfo &IFI, 1391 unsigned ByValAlignment) { 1392 PointerType *ArgTy = cast<PointerType>(Arg->getType()); 1393 Type *AggTy = ArgTy->getElementType(); 1394 1395 Function *Caller = TheCall->getFunction(); 1396 const DataLayout &DL = Caller->getParent()->getDataLayout(); 1397 1398 // If the called function is readonly, then it could not mutate the caller's 1399 // copy of the byval'd memory. In this case, it is safe to elide the copy and 1400 // temporary. 1401 if (CalledFunc->onlyReadsMemory()) { 1402 // If the byval argument has a specified alignment that is greater than the 1403 // passed in pointer, then we either have to round up the input pointer or 1404 // give up on this transformation. 1405 if (ByValAlignment <= 1) // 0 = unspecified, 1 = no particular alignment. 1406 return Arg; 1407 1408 AssumptionCache *AC = 1409 IFI.GetAssumptionCache ? &IFI.GetAssumptionCache(*Caller) : nullptr; 1410 1411 // If the pointer is already known to be sufficiently aligned, or if we can 1412 // round it up to a larger alignment, then we don't need a temporary. 1413 if (getOrEnforceKnownAlignment(Arg, Align(ByValAlignment), DL, TheCall, 1414 AC) >= ByValAlignment) 1415 return Arg; 1416 1417 // Otherwise, we have to make a memcpy to get a safe alignment. This is bad 1418 // for code quality, but rarely happens and is required for correctness. 1419 } 1420 1421 // Create the alloca. If we have DataLayout, use nice alignment. 1422 Align Alignment(DL.getPrefTypeAlignment(AggTy)); 1423 1424 // If the byval had an alignment specified, we *must* use at least that 1425 // alignment, as it is required by the byval argument (and uses of the 1426 // pointer inside the callee). 1427 Alignment = max(Alignment, MaybeAlign(ByValAlignment)); 1428 1429 Value *NewAlloca = 1430 new AllocaInst(AggTy, DL.getAllocaAddrSpace(), nullptr, Alignment, 1431 Arg->getName(), &*Caller->begin()->begin()); 1432 IFI.StaticAllocas.push_back(cast<AllocaInst>(NewAlloca)); 1433 1434 // Uses of the argument in the function should use our new alloca 1435 // instead. 1436 return NewAlloca; 1437 } 1438 1439 // Check whether this Value is used by a lifetime intrinsic. 1440 static bool isUsedByLifetimeMarker(Value *V) { 1441 for (User *U : V->users()) 1442 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(U)) 1443 if (II->isLifetimeStartOrEnd()) 1444 return true; 1445 return false; 1446 } 1447 1448 // Check whether the given alloca already has 1449 // lifetime.start or lifetime.end intrinsics. 1450 static bool hasLifetimeMarkers(AllocaInst *AI) { 1451 Type *Ty = AI->getType(); 1452 Type *Int8PtrTy = Type::getInt8PtrTy(Ty->getContext(), 1453 Ty->getPointerAddressSpace()); 1454 if (Ty == Int8PtrTy) 1455 return isUsedByLifetimeMarker(AI); 1456 1457 // Do a scan to find all the casts to i8*. 1458 for (User *U : AI->users()) { 1459 if (U->getType() != Int8PtrTy) continue; 1460 if (U->stripPointerCasts() != AI) continue; 1461 if (isUsedByLifetimeMarker(U)) 1462 return true; 1463 } 1464 return false; 1465 } 1466 1467 /// Return the result of AI->isStaticAlloca() if AI were moved to the entry 1468 /// block. Allocas used in inalloca calls and allocas of dynamic array size 1469 /// cannot be static. 1470 static bool allocaWouldBeStaticInEntry(const AllocaInst *AI ) { 1471 return isa<Constant>(AI->getArraySize()) && !AI->isUsedWithInAlloca(); 1472 } 1473 1474 /// Returns a DebugLoc for a new DILocation which is a clone of \p OrigDL 1475 /// inlined at \p InlinedAt. \p IANodes is an inlined-at cache. 1476 static DebugLoc inlineDebugLoc(DebugLoc OrigDL, DILocation *InlinedAt, 1477 LLVMContext &Ctx, 1478 DenseMap<const MDNode *, MDNode *> &IANodes) { 1479 auto IA = DebugLoc::appendInlinedAt(OrigDL, InlinedAt, Ctx, IANodes); 1480 return DILocation::get(Ctx, OrigDL.getLine(), OrigDL.getCol(), 1481 OrigDL.getScope(), IA); 1482 } 1483 1484 /// Update inlined instructions' line numbers to 1485 /// to encode location where these instructions are inlined. 1486 static void fixupLineNumbers(Function *Fn, Function::iterator FI, 1487 Instruction *TheCall, bool CalleeHasDebugInfo) { 1488 const DebugLoc &TheCallDL = TheCall->getDebugLoc(); 1489 if (!TheCallDL) 1490 return; 1491 1492 auto &Ctx = Fn->getContext(); 1493 DILocation *InlinedAtNode = TheCallDL; 1494 1495 // Create a unique call site, not to be confused with any other call from the 1496 // same location. 1497 InlinedAtNode = DILocation::getDistinct( 1498 Ctx, InlinedAtNode->getLine(), InlinedAtNode->getColumn(), 1499 InlinedAtNode->getScope(), InlinedAtNode->getInlinedAt()); 1500 1501 // Cache the inlined-at nodes as they're built so they are reused, without 1502 // this every instruction's inlined-at chain would become distinct from each 1503 // other. 1504 DenseMap<const MDNode *, MDNode *> IANodes; 1505 1506 // Check if we are not generating inline line tables and want to use 1507 // the call site location instead. 1508 bool NoInlineLineTables = Fn->hasFnAttribute("no-inline-line-tables"); 1509 1510 for (; FI != Fn->end(); ++FI) { 1511 for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); 1512 BI != BE; ++BI) { 1513 // Loop metadata needs to be updated so that the start and end locs 1514 // reference inlined-at locations. 1515 auto updateLoopInfoLoc = [&Ctx, &InlinedAtNode, &IANodes]( 1516 const DILocation &Loc) -> DILocation * { 1517 return inlineDebugLoc(&Loc, InlinedAtNode, Ctx, IANodes).get(); 1518 }; 1519 updateLoopMetadataDebugLocations(*BI, updateLoopInfoLoc); 1520 1521 if (!NoInlineLineTables) 1522 if (DebugLoc DL = BI->getDebugLoc()) { 1523 DebugLoc IDL = 1524 inlineDebugLoc(DL, InlinedAtNode, BI->getContext(), IANodes); 1525 BI->setDebugLoc(IDL); 1526 continue; 1527 } 1528 1529 if (CalleeHasDebugInfo && !NoInlineLineTables) 1530 continue; 1531 1532 // If the inlined instruction has no line number, or if inline info 1533 // is not being generated, make it look as if it originates from the call 1534 // location. This is important for ((__always_inline, __nodebug__)) 1535 // functions which must use caller location for all instructions in their 1536 // function body. 1537 1538 // Don't update static allocas, as they may get moved later. 1539 if (auto *AI = dyn_cast<AllocaInst>(BI)) 1540 if (allocaWouldBeStaticInEntry(AI)) 1541 continue; 1542 1543 BI->setDebugLoc(TheCallDL); 1544 } 1545 1546 // Remove debug info intrinsics if we're not keeping inline info. 1547 if (NoInlineLineTables) { 1548 BasicBlock::iterator BI = FI->begin(); 1549 while (BI != FI->end()) { 1550 if (isa<DbgInfoIntrinsic>(BI)) { 1551 BI = BI->eraseFromParent(); 1552 continue; 1553 } 1554 ++BI; 1555 } 1556 } 1557 1558 } 1559 } 1560 1561 /// Update the block frequencies of the caller after a callee has been inlined. 1562 /// 1563 /// Each block cloned into the caller has its block frequency scaled by the 1564 /// ratio of CallSiteFreq/CalleeEntryFreq. This ensures that the cloned copy of 1565 /// callee's entry block gets the same frequency as the callsite block and the 1566 /// relative frequencies of all cloned blocks remain the same after cloning. 1567 static void updateCallerBFI(BasicBlock *CallSiteBlock, 1568 const ValueToValueMapTy &VMap, 1569 BlockFrequencyInfo *CallerBFI, 1570 BlockFrequencyInfo *CalleeBFI, 1571 const BasicBlock &CalleeEntryBlock) { 1572 SmallPtrSet<BasicBlock *, 16> ClonedBBs; 1573 for (auto Entry : VMap) { 1574 if (!isa<BasicBlock>(Entry.first) || !Entry.second) 1575 continue; 1576 auto *OrigBB = cast<BasicBlock>(Entry.first); 1577 auto *ClonedBB = cast<BasicBlock>(Entry.second); 1578 uint64_t Freq = CalleeBFI->getBlockFreq(OrigBB).getFrequency(); 1579 if (!ClonedBBs.insert(ClonedBB).second) { 1580 // Multiple blocks in the callee might get mapped to one cloned block in 1581 // the caller since we prune the callee as we clone it. When that happens, 1582 // we want to use the maximum among the original blocks' frequencies. 1583 uint64_t NewFreq = CallerBFI->getBlockFreq(ClonedBB).getFrequency(); 1584 if (NewFreq > Freq) 1585 Freq = NewFreq; 1586 } 1587 CallerBFI->setBlockFreq(ClonedBB, Freq); 1588 } 1589 BasicBlock *EntryClone = cast<BasicBlock>(VMap.lookup(&CalleeEntryBlock)); 1590 CallerBFI->setBlockFreqAndScale( 1591 EntryClone, CallerBFI->getBlockFreq(CallSiteBlock).getFrequency(), 1592 ClonedBBs); 1593 } 1594 1595 /// Update the branch metadata for cloned call instructions. 1596 static void updateCallProfile(Function *Callee, const ValueToValueMapTy &VMap, 1597 const ProfileCount &CalleeEntryCount, 1598 const CallBase &TheCall, ProfileSummaryInfo *PSI, 1599 BlockFrequencyInfo *CallerBFI) { 1600 if (!CalleeEntryCount.hasValue() || CalleeEntryCount.isSynthetic() || 1601 CalleeEntryCount.getCount() < 1) 1602 return; 1603 auto CallSiteCount = PSI ? PSI->getProfileCount(TheCall, CallerBFI) : None; 1604 int64_t CallCount = 1605 std::min(CallSiteCount.getValueOr(0), CalleeEntryCount.getCount()); 1606 updateProfileCallee(Callee, -CallCount, &VMap); 1607 } 1608 1609 void llvm::updateProfileCallee( 1610 Function *Callee, int64_t entryDelta, 1611 const ValueMap<const Value *, WeakTrackingVH> *VMap) { 1612 auto CalleeCount = Callee->getEntryCount(); 1613 if (!CalleeCount.hasValue()) 1614 return; 1615 1616 uint64_t priorEntryCount = CalleeCount.getCount(); 1617 uint64_t newEntryCount; 1618 1619 // Since CallSiteCount is an estimate, it could exceed the original callee 1620 // count and has to be set to 0 so guard against underflow. 1621 if (entryDelta < 0 && static_cast<uint64_t>(-entryDelta) > priorEntryCount) 1622 newEntryCount = 0; 1623 else 1624 newEntryCount = priorEntryCount + entryDelta; 1625 1626 // During inlining ? 1627 if (VMap) { 1628 uint64_t cloneEntryCount = priorEntryCount - newEntryCount; 1629 for (auto Entry : *VMap) 1630 if (isa<CallInst>(Entry.first)) 1631 if (auto *CI = dyn_cast_or_null<CallInst>(Entry.second)) 1632 CI->updateProfWeight(cloneEntryCount, priorEntryCount); 1633 } 1634 1635 if (entryDelta) { 1636 Callee->setEntryCount(newEntryCount); 1637 1638 for (BasicBlock &BB : *Callee) 1639 // No need to update the callsite if it is pruned during inlining. 1640 if (!VMap || VMap->count(&BB)) 1641 for (Instruction &I : BB) 1642 if (CallInst *CI = dyn_cast<CallInst>(&I)) 1643 CI->updateProfWeight(newEntryCount, priorEntryCount); 1644 } 1645 } 1646 1647 /// This function inlines the called function into the basic block of the 1648 /// caller. This returns false if it is not possible to inline this call. 1649 /// The program is still in a well defined state if this occurs though. 1650 /// 1651 /// Note that this only does one level of inlining. For example, if the 1652 /// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now 1653 /// exists in the instruction stream. Similarly this will inline a recursive 1654 /// function by one level. 1655 llvm::InlineResult llvm::InlineFunction(CallBase &CB, InlineFunctionInfo &IFI, 1656 AAResults *CalleeAAR, 1657 bool InsertLifetime, 1658 Function *ForwardVarArgsTo) { 1659 assert(CB.getParent() && CB.getFunction() && "Instruction not in function!"); 1660 1661 // FIXME: we don't inline callbr yet. 1662 if (isa<CallBrInst>(CB)) 1663 return InlineResult::failure("We don't inline callbr yet."); 1664 1665 // If IFI has any state in it, zap it before we fill it in. 1666 IFI.reset(); 1667 1668 Function *CalledFunc = CB.getCalledFunction(); 1669 if (!CalledFunc || // Can't inline external function or indirect 1670 CalledFunc->isDeclaration()) // call! 1671 return InlineResult::failure("external or indirect"); 1672 1673 // The inliner does not know how to inline through calls with operand bundles 1674 // in general ... 1675 if (CB.hasOperandBundles()) { 1676 for (int i = 0, e = CB.getNumOperandBundles(); i != e; ++i) { 1677 uint32_t Tag = CB.getOperandBundleAt(i).getTagID(); 1678 // ... but it knows how to inline through "deopt" operand bundles ... 1679 if (Tag == LLVMContext::OB_deopt) 1680 continue; 1681 // ... and "funclet" operand bundles. 1682 if (Tag == LLVMContext::OB_funclet) 1683 continue; 1684 1685 return InlineResult::failure("unsupported operand bundle"); 1686 } 1687 } 1688 1689 // If the call to the callee cannot throw, set the 'nounwind' flag on any 1690 // calls that we inline. 1691 bool MarkNoUnwind = CB.doesNotThrow(); 1692 1693 BasicBlock *OrigBB = CB.getParent(); 1694 Function *Caller = OrigBB->getParent(); 1695 1696 // GC poses two hazards to inlining, which only occur when the callee has GC: 1697 // 1. If the caller has no GC, then the callee's GC must be propagated to the 1698 // caller. 1699 // 2. If the caller has a differing GC, it is invalid to inline. 1700 if (CalledFunc->hasGC()) { 1701 if (!Caller->hasGC()) 1702 Caller->setGC(CalledFunc->getGC()); 1703 else if (CalledFunc->getGC() != Caller->getGC()) 1704 return InlineResult::failure("incompatible GC"); 1705 } 1706 1707 // Get the personality function from the callee if it contains a landing pad. 1708 Constant *CalledPersonality = 1709 CalledFunc->hasPersonalityFn() 1710 ? CalledFunc->getPersonalityFn()->stripPointerCasts() 1711 : nullptr; 1712 1713 // Find the personality function used by the landing pads of the caller. If it 1714 // exists, then check to see that it matches the personality function used in 1715 // the callee. 1716 Constant *CallerPersonality = 1717 Caller->hasPersonalityFn() 1718 ? Caller->getPersonalityFn()->stripPointerCasts() 1719 : nullptr; 1720 if (CalledPersonality) { 1721 if (!CallerPersonality) 1722 Caller->setPersonalityFn(CalledPersonality); 1723 // If the personality functions match, then we can perform the 1724 // inlining. Otherwise, we can't inline. 1725 // TODO: This isn't 100% true. Some personality functions are proper 1726 // supersets of others and can be used in place of the other. 1727 else if (CalledPersonality != CallerPersonality) 1728 return InlineResult::failure("incompatible personality"); 1729 } 1730 1731 // We need to figure out which funclet the callsite was in so that we may 1732 // properly nest the callee. 1733 Instruction *CallSiteEHPad = nullptr; 1734 if (CallerPersonality) { 1735 EHPersonality Personality = classifyEHPersonality(CallerPersonality); 1736 if (isScopedEHPersonality(Personality)) { 1737 Optional<OperandBundleUse> ParentFunclet = 1738 CB.getOperandBundle(LLVMContext::OB_funclet); 1739 if (ParentFunclet) 1740 CallSiteEHPad = cast<FuncletPadInst>(ParentFunclet->Inputs.front()); 1741 1742 // OK, the inlining site is legal. What about the target function? 1743 1744 if (CallSiteEHPad) { 1745 if (Personality == EHPersonality::MSVC_CXX) { 1746 // The MSVC personality cannot tolerate catches getting inlined into 1747 // cleanup funclets. 1748 if (isa<CleanupPadInst>(CallSiteEHPad)) { 1749 // Ok, the call site is within a cleanuppad. Let's check the callee 1750 // for catchpads. 1751 for (const BasicBlock &CalledBB : *CalledFunc) { 1752 if (isa<CatchSwitchInst>(CalledBB.getFirstNonPHI())) 1753 return InlineResult::failure("catch in cleanup funclet"); 1754 } 1755 } 1756 } else if (isAsynchronousEHPersonality(Personality)) { 1757 // SEH is even less tolerant, there may not be any sort of exceptional 1758 // funclet in the callee. 1759 for (const BasicBlock &CalledBB : *CalledFunc) { 1760 if (CalledBB.isEHPad()) 1761 return InlineResult::failure("SEH in cleanup funclet"); 1762 } 1763 } 1764 } 1765 } 1766 } 1767 1768 // Determine if we are dealing with a call in an EHPad which does not unwind 1769 // to caller. 1770 bool EHPadForCallUnwindsLocally = false; 1771 if (CallSiteEHPad && isa<CallInst>(CB)) { 1772 UnwindDestMemoTy FuncletUnwindMap; 1773 Value *CallSiteUnwindDestToken = 1774 getUnwindDestToken(CallSiteEHPad, FuncletUnwindMap); 1775 1776 EHPadForCallUnwindsLocally = 1777 CallSiteUnwindDestToken && 1778 !isa<ConstantTokenNone>(CallSiteUnwindDestToken); 1779 } 1780 1781 // Get an iterator to the last basic block in the function, which will have 1782 // the new function inlined after it. 1783 Function::iterator LastBlock = --Caller->end(); 1784 1785 // Make sure to capture all of the return instructions from the cloned 1786 // function. 1787 SmallVector<ReturnInst*, 8> Returns; 1788 ClonedCodeInfo InlinedFunctionInfo; 1789 Function::iterator FirstNewBlock; 1790 1791 { // Scope to destroy VMap after cloning. 1792 ValueToValueMapTy VMap; 1793 // Keep a list of pair (dst, src) to emit byval initializations. 1794 SmallVector<std::pair<Value*, Value*>, 4> ByValInit; 1795 1796 // When inlining a function that contains noalias scope metadata, 1797 // this metadata needs to be cloned so that the inlined blocks 1798 // have different "unique scopes" at every call site. 1799 // Track the metadata that must be cloned. Do this before other changes to 1800 // the function, so that we do not get in trouble when inlining caller == 1801 // callee. 1802 ScopedAliasMetadataDeepCloner SAMetadataCloner(CB.getCalledFunction()); 1803 1804 auto &DL = Caller->getParent()->getDataLayout(); 1805 1806 // Calculate the vector of arguments to pass into the function cloner, which 1807 // matches up the formal to the actual argument values. 1808 auto AI = CB.arg_begin(); 1809 unsigned ArgNo = 0; 1810 for (Function::arg_iterator I = CalledFunc->arg_begin(), 1811 E = CalledFunc->arg_end(); I != E; ++I, ++AI, ++ArgNo) { 1812 Value *ActualArg = *AI; 1813 1814 // When byval arguments actually inlined, we need to make the copy implied 1815 // by them explicit. However, we don't do this if the callee is readonly 1816 // or readnone, because the copy would be unneeded: the callee doesn't 1817 // modify the struct. 1818 if (CB.isByValArgument(ArgNo)) { 1819 ActualArg = HandleByValArgument(ActualArg, &CB, CalledFunc, IFI, 1820 CalledFunc->getParamAlignment(ArgNo)); 1821 if (ActualArg != *AI) 1822 ByValInit.push_back(std::make_pair(ActualArg, (Value*) *AI)); 1823 } 1824 1825 VMap[&*I] = ActualArg; 1826 } 1827 1828 // TODO: Remove this when users have been updated to the assume bundles. 1829 // Add alignment assumptions if necessary. We do this before the inlined 1830 // instructions are actually cloned into the caller so that we can easily 1831 // check what will be known at the start of the inlined code. 1832 AddAlignmentAssumptions(CB, IFI); 1833 1834 AssumptionCache *AC = 1835 IFI.GetAssumptionCache ? &IFI.GetAssumptionCache(*Caller) : nullptr; 1836 1837 /// Preserve all attributes on of the call and its parameters. 1838 salvageKnowledge(&CB, AC); 1839 1840 // We want the inliner to prune the code as it copies. We would LOVE to 1841 // have no dead or constant instructions leftover after inlining occurs 1842 // (which can happen, e.g., because an argument was constant), but we'll be 1843 // happy with whatever the cloner can do. 1844 CloneAndPruneFunctionInto(Caller, CalledFunc, VMap, 1845 /*ModuleLevelChanges=*/false, Returns, ".i", 1846 &InlinedFunctionInfo, &CB); 1847 // Remember the first block that is newly cloned over. 1848 FirstNewBlock = LastBlock; ++FirstNewBlock; 1849 1850 if (IFI.CallerBFI != nullptr && IFI.CalleeBFI != nullptr) 1851 // Update the BFI of blocks cloned into the caller. 1852 updateCallerBFI(OrigBB, VMap, IFI.CallerBFI, IFI.CalleeBFI, 1853 CalledFunc->front()); 1854 1855 updateCallProfile(CalledFunc, VMap, CalledFunc->getEntryCount(), CB, 1856 IFI.PSI, IFI.CallerBFI); 1857 1858 // Inject byval arguments initialization. 1859 for (std::pair<Value*, Value*> &Init : ByValInit) 1860 HandleByValArgumentInit(Init.first, Init.second, Caller->getParent(), 1861 &*FirstNewBlock, IFI); 1862 1863 Optional<OperandBundleUse> ParentDeopt = 1864 CB.getOperandBundle(LLVMContext::OB_deopt); 1865 if (ParentDeopt) { 1866 SmallVector<OperandBundleDef, 2> OpDefs; 1867 1868 for (auto &VH : InlinedFunctionInfo.OperandBundleCallSites) { 1869 CallBase *ICS = dyn_cast_or_null<CallBase>(VH); 1870 if (!ICS) 1871 continue; // instruction was DCE'd or RAUW'ed to undef 1872 1873 OpDefs.clear(); 1874 1875 OpDefs.reserve(ICS->getNumOperandBundles()); 1876 1877 for (unsigned COBi = 0, COBe = ICS->getNumOperandBundles(); COBi < COBe; 1878 ++COBi) { 1879 auto ChildOB = ICS->getOperandBundleAt(COBi); 1880 if (ChildOB.getTagID() != LLVMContext::OB_deopt) { 1881 // If the inlined call has other operand bundles, let them be 1882 OpDefs.emplace_back(ChildOB); 1883 continue; 1884 } 1885 1886 // It may be useful to separate this logic (of handling operand 1887 // bundles) out to a separate "policy" component if this gets crowded. 1888 // Prepend the parent's deoptimization continuation to the newly 1889 // inlined call's deoptimization continuation. 1890 std::vector<Value *> MergedDeoptArgs; 1891 MergedDeoptArgs.reserve(ParentDeopt->Inputs.size() + 1892 ChildOB.Inputs.size()); 1893 1894 llvm::append_range(MergedDeoptArgs, ParentDeopt->Inputs); 1895 llvm::append_range(MergedDeoptArgs, ChildOB.Inputs); 1896 1897 OpDefs.emplace_back("deopt", std::move(MergedDeoptArgs)); 1898 } 1899 1900 Instruction *NewI = CallBase::Create(ICS, OpDefs, ICS); 1901 1902 // Note: the RAUW does the appropriate fixup in VMap, so we need to do 1903 // this even if the call returns void. 1904 ICS->replaceAllUsesWith(NewI); 1905 1906 VH = nullptr; 1907 ICS->eraseFromParent(); 1908 } 1909 } 1910 1911 // Update the callgraph if requested. 1912 if (IFI.CG) 1913 UpdateCallGraphAfterInlining(CB, FirstNewBlock, VMap, IFI); 1914 1915 // For 'nodebug' functions, the associated DISubprogram is always null. 1916 // Conservatively avoid propagating the callsite debug location to 1917 // instructions inlined from a function whose DISubprogram is not null. 1918 fixupLineNumbers(Caller, FirstNewBlock, &CB, 1919 CalledFunc->getSubprogram() != nullptr); 1920 1921 // Now clone the inlined noalias scope metadata. 1922 SAMetadataCloner.clone(); 1923 SAMetadataCloner.remap(VMap); 1924 1925 // Add noalias metadata if necessary. 1926 AddAliasScopeMetadata(CB, VMap, DL, CalleeAAR); 1927 1928 // Clone return attributes on the callsite into the calls within the inlined 1929 // function which feed into its return value. 1930 AddReturnAttributes(CB, VMap); 1931 1932 // Propagate metadata on the callsite if necessary. 1933 PropagateCallSiteMetadata(CB, VMap); 1934 1935 // Register any cloned assumptions. 1936 if (IFI.GetAssumptionCache) 1937 for (BasicBlock &NewBlock : 1938 make_range(FirstNewBlock->getIterator(), Caller->end())) 1939 for (Instruction &I : NewBlock) 1940 if (auto *II = dyn_cast<IntrinsicInst>(&I)) 1941 if (II->getIntrinsicID() == Intrinsic::assume) 1942 IFI.GetAssumptionCache(*Caller).registerAssumption(II); 1943 } 1944 1945 // If there are any alloca instructions in the block that used to be the entry 1946 // block for the callee, move them to the entry block of the caller. First 1947 // calculate which instruction they should be inserted before. We insert the 1948 // instructions at the end of the current alloca list. 1949 { 1950 BasicBlock::iterator InsertPoint = Caller->begin()->begin(); 1951 for (BasicBlock::iterator I = FirstNewBlock->begin(), 1952 E = FirstNewBlock->end(); I != E; ) { 1953 AllocaInst *AI = dyn_cast<AllocaInst>(I++); 1954 if (!AI) continue; 1955 1956 // If the alloca is now dead, remove it. This often occurs due to code 1957 // specialization. 1958 if (AI->use_empty()) { 1959 AI->eraseFromParent(); 1960 continue; 1961 } 1962 1963 if (!allocaWouldBeStaticInEntry(AI)) 1964 continue; 1965 1966 // Keep track of the static allocas that we inline into the caller. 1967 IFI.StaticAllocas.push_back(AI); 1968 1969 // Scan for the block of allocas that we can move over, and move them 1970 // all at once. 1971 while (isa<AllocaInst>(I) && 1972 !cast<AllocaInst>(I)->use_empty() && 1973 allocaWouldBeStaticInEntry(cast<AllocaInst>(I))) { 1974 IFI.StaticAllocas.push_back(cast<AllocaInst>(I)); 1975 ++I; 1976 } 1977 1978 // Transfer all of the allocas over in a block. Using splice means 1979 // that the instructions aren't removed from the symbol table, then 1980 // reinserted. 1981 Caller->getEntryBlock().getInstList().splice( 1982 InsertPoint, FirstNewBlock->getInstList(), AI->getIterator(), I); 1983 } 1984 } 1985 1986 SmallVector<Value*,4> VarArgsToForward; 1987 SmallVector<AttributeSet, 4> VarArgsAttrs; 1988 for (unsigned i = CalledFunc->getFunctionType()->getNumParams(); 1989 i < CB.getNumArgOperands(); i++) { 1990 VarArgsToForward.push_back(CB.getArgOperand(i)); 1991 VarArgsAttrs.push_back(CB.getAttributes().getParamAttributes(i)); 1992 } 1993 1994 bool InlinedMustTailCalls = false, InlinedDeoptimizeCalls = false; 1995 if (InlinedFunctionInfo.ContainsCalls) { 1996 CallInst::TailCallKind CallSiteTailKind = CallInst::TCK_None; 1997 if (CallInst *CI = dyn_cast<CallInst>(&CB)) 1998 CallSiteTailKind = CI->getTailCallKind(); 1999 2000 // For inlining purposes, the "notail" marker is the same as no marker. 2001 if (CallSiteTailKind == CallInst::TCK_NoTail) 2002 CallSiteTailKind = CallInst::TCK_None; 2003 2004 for (Function::iterator BB = FirstNewBlock, E = Caller->end(); BB != E; 2005 ++BB) { 2006 for (auto II = BB->begin(); II != BB->end();) { 2007 Instruction &I = *II++; 2008 CallInst *CI = dyn_cast<CallInst>(&I); 2009 if (!CI) 2010 continue; 2011 2012 // Forward varargs from inlined call site to calls to the 2013 // ForwardVarArgsTo function, if requested, and to musttail calls. 2014 if (!VarArgsToForward.empty() && 2015 ((ForwardVarArgsTo && 2016 CI->getCalledFunction() == ForwardVarArgsTo) || 2017 CI->isMustTailCall())) { 2018 // Collect attributes for non-vararg parameters. 2019 AttributeList Attrs = CI->getAttributes(); 2020 SmallVector<AttributeSet, 8> ArgAttrs; 2021 if (!Attrs.isEmpty() || !VarArgsAttrs.empty()) { 2022 for (unsigned ArgNo = 0; 2023 ArgNo < CI->getFunctionType()->getNumParams(); ++ArgNo) 2024 ArgAttrs.push_back(Attrs.getParamAttributes(ArgNo)); 2025 } 2026 2027 // Add VarArg attributes. 2028 ArgAttrs.append(VarArgsAttrs.begin(), VarArgsAttrs.end()); 2029 Attrs = AttributeList::get(CI->getContext(), Attrs.getFnAttributes(), 2030 Attrs.getRetAttributes(), ArgAttrs); 2031 // Add VarArgs to existing parameters. 2032 SmallVector<Value *, 6> Params(CI->arg_operands()); 2033 Params.append(VarArgsToForward.begin(), VarArgsToForward.end()); 2034 CallInst *NewCI = CallInst::Create( 2035 CI->getFunctionType(), CI->getCalledOperand(), Params, "", CI); 2036 NewCI->setDebugLoc(CI->getDebugLoc()); 2037 NewCI->setAttributes(Attrs); 2038 NewCI->setCallingConv(CI->getCallingConv()); 2039 CI->replaceAllUsesWith(NewCI); 2040 CI->eraseFromParent(); 2041 CI = NewCI; 2042 } 2043 2044 if (Function *F = CI->getCalledFunction()) 2045 InlinedDeoptimizeCalls |= 2046 F->getIntrinsicID() == Intrinsic::experimental_deoptimize; 2047 2048 // We need to reduce the strength of any inlined tail calls. For 2049 // musttail, we have to avoid introducing potential unbounded stack 2050 // growth. For example, if functions 'f' and 'g' are mutually recursive 2051 // with musttail, we can inline 'g' into 'f' so long as we preserve 2052 // musttail on the cloned call to 'f'. If either the inlined call site 2053 // or the cloned call site is *not* musttail, the program already has 2054 // one frame of stack growth, so it's safe to remove musttail. Here is 2055 // a table of example transformations: 2056 // 2057 // f -> musttail g -> musttail f ==> f -> musttail f 2058 // f -> musttail g -> tail f ==> f -> tail f 2059 // f -> g -> musttail f ==> f -> f 2060 // f -> g -> tail f ==> f -> f 2061 // 2062 // Inlined notail calls should remain notail calls. 2063 CallInst::TailCallKind ChildTCK = CI->getTailCallKind(); 2064 if (ChildTCK != CallInst::TCK_NoTail) 2065 ChildTCK = std::min(CallSiteTailKind, ChildTCK); 2066 CI->setTailCallKind(ChildTCK); 2067 InlinedMustTailCalls |= CI->isMustTailCall(); 2068 2069 // Calls inlined through a 'nounwind' call site should be marked 2070 // 'nounwind'. 2071 if (MarkNoUnwind) 2072 CI->setDoesNotThrow(); 2073 } 2074 } 2075 } 2076 2077 // Leave lifetime markers for the static alloca's, scoping them to the 2078 // function we just inlined. 2079 if (InsertLifetime && !IFI.StaticAllocas.empty()) { 2080 IRBuilder<> builder(&FirstNewBlock->front()); 2081 for (unsigned ai = 0, ae = IFI.StaticAllocas.size(); ai != ae; ++ai) { 2082 AllocaInst *AI = IFI.StaticAllocas[ai]; 2083 // Don't mark swifterror allocas. They can't have bitcast uses. 2084 if (AI->isSwiftError()) 2085 continue; 2086 2087 // If the alloca is already scoped to something smaller than the whole 2088 // function then there's no need to add redundant, less accurate markers. 2089 if (hasLifetimeMarkers(AI)) 2090 continue; 2091 2092 // Try to determine the size of the allocation. 2093 ConstantInt *AllocaSize = nullptr; 2094 if (ConstantInt *AIArraySize = 2095 dyn_cast<ConstantInt>(AI->getArraySize())) { 2096 auto &DL = Caller->getParent()->getDataLayout(); 2097 Type *AllocaType = AI->getAllocatedType(); 2098 TypeSize AllocaTypeSize = DL.getTypeAllocSize(AllocaType); 2099 uint64_t AllocaArraySize = AIArraySize->getLimitedValue(); 2100 2101 // Don't add markers for zero-sized allocas. 2102 if (AllocaArraySize == 0) 2103 continue; 2104 2105 // Check that array size doesn't saturate uint64_t and doesn't 2106 // overflow when it's multiplied by type size. 2107 if (!AllocaTypeSize.isScalable() && 2108 AllocaArraySize != std::numeric_limits<uint64_t>::max() && 2109 std::numeric_limits<uint64_t>::max() / AllocaArraySize >= 2110 AllocaTypeSize.getFixedSize()) { 2111 AllocaSize = ConstantInt::get(Type::getInt64Ty(AI->getContext()), 2112 AllocaArraySize * AllocaTypeSize); 2113 } 2114 } 2115 2116 builder.CreateLifetimeStart(AI, AllocaSize); 2117 for (ReturnInst *RI : Returns) { 2118 // Don't insert llvm.lifetime.end calls between a musttail or deoptimize 2119 // call and a return. The return kills all local allocas. 2120 if (InlinedMustTailCalls && 2121 RI->getParent()->getTerminatingMustTailCall()) 2122 continue; 2123 if (InlinedDeoptimizeCalls && 2124 RI->getParent()->getTerminatingDeoptimizeCall()) 2125 continue; 2126 IRBuilder<>(RI).CreateLifetimeEnd(AI, AllocaSize); 2127 } 2128 } 2129 } 2130 2131 // If the inlined code contained dynamic alloca instructions, wrap the inlined 2132 // code with llvm.stacksave/llvm.stackrestore intrinsics. 2133 if (InlinedFunctionInfo.ContainsDynamicAllocas) { 2134 Module *M = Caller->getParent(); 2135 // Get the two intrinsics we care about. 2136 Function *StackSave = Intrinsic::getDeclaration(M, Intrinsic::stacksave); 2137 Function *StackRestore=Intrinsic::getDeclaration(M,Intrinsic::stackrestore); 2138 2139 // Insert the llvm.stacksave. 2140 CallInst *SavedPtr = IRBuilder<>(&*FirstNewBlock, FirstNewBlock->begin()) 2141 .CreateCall(StackSave, {}, "savedstack"); 2142 2143 // Insert a call to llvm.stackrestore before any return instructions in the 2144 // inlined function. 2145 for (ReturnInst *RI : Returns) { 2146 // Don't insert llvm.stackrestore calls between a musttail or deoptimize 2147 // call and a return. The return will restore the stack pointer. 2148 if (InlinedMustTailCalls && RI->getParent()->getTerminatingMustTailCall()) 2149 continue; 2150 if (InlinedDeoptimizeCalls && RI->getParent()->getTerminatingDeoptimizeCall()) 2151 continue; 2152 IRBuilder<>(RI).CreateCall(StackRestore, SavedPtr); 2153 } 2154 } 2155 2156 // If we are inlining for an invoke instruction, we must make sure to rewrite 2157 // any call instructions into invoke instructions. This is sensitive to which 2158 // funclet pads were top-level in the inlinee, so must be done before 2159 // rewriting the "parent pad" links. 2160 if (auto *II = dyn_cast<InvokeInst>(&CB)) { 2161 BasicBlock *UnwindDest = II->getUnwindDest(); 2162 Instruction *FirstNonPHI = UnwindDest->getFirstNonPHI(); 2163 if (isa<LandingPadInst>(FirstNonPHI)) { 2164 HandleInlinedLandingPad(II, &*FirstNewBlock, InlinedFunctionInfo); 2165 } else { 2166 HandleInlinedEHPad(II, &*FirstNewBlock, InlinedFunctionInfo); 2167 } 2168 } 2169 2170 // Update the lexical scopes of the new funclets and callsites. 2171 // Anything that had 'none' as its parent is now nested inside the callsite's 2172 // EHPad. 2173 2174 if (CallSiteEHPad) { 2175 for (Function::iterator BB = FirstNewBlock->getIterator(), 2176 E = Caller->end(); 2177 BB != E; ++BB) { 2178 // Add bundle operands to any top-level call sites. 2179 SmallVector<OperandBundleDef, 1> OpBundles; 2180 for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;) { 2181 CallBase *I = dyn_cast<CallBase>(&*BBI++); 2182 if (!I) 2183 continue; 2184 2185 // Skip call sites which are nounwind intrinsics. 2186 auto *CalledFn = 2187 dyn_cast<Function>(I->getCalledOperand()->stripPointerCasts()); 2188 if (CalledFn && CalledFn->isIntrinsic() && I->doesNotThrow()) 2189 continue; 2190 2191 // Skip call sites which already have a "funclet" bundle. 2192 if (I->getOperandBundle(LLVMContext::OB_funclet)) 2193 continue; 2194 2195 I->getOperandBundlesAsDefs(OpBundles); 2196 OpBundles.emplace_back("funclet", CallSiteEHPad); 2197 2198 Instruction *NewInst = CallBase::Create(I, OpBundles, I); 2199 NewInst->takeName(I); 2200 I->replaceAllUsesWith(NewInst); 2201 I->eraseFromParent(); 2202 2203 OpBundles.clear(); 2204 } 2205 2206 // It is problematic if the inlinee has a cleanupret which unwinds to 2207 // caller and we inline it into a call site which doesn't unwind but into 2208 // an EH pad that does. Such an edge must be dynamically unreachable. 2209 // As such, we replace the cleanupret with unreachable. 2210 if (auto *CleanupRet = dyn_cast<CleanupReturnInst>(BB->getTerminator())) 2211 if (CleanupRet->unwindsToCaller() && EHPadForCallUnwindsLocally) 2212 changeToUnreachable(CleanupRet, /*UseLLVMTrap=*/false); 2213 2214 Instruction *I = BB->getFirstNonPHI(); 2215 if (!I->isEHPad()) 2216 continue; 2217 2218 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(I)) { 2219 if (isa<ConstantTokenNone>(CatchSwitch->getParentPad())) 2220 CatchSwitch->setParentPad(CallSiteEHPad); 2221 } else { 2222 auto *FPI = cast<FuncletPadInst>(I); 2223 if (isa<ConstantTokenNone>(FPI->getParentPad())) 2224 FPI->setParentPad(CallSiteEHPad); 2225 } 2226 } 2227 } 2228 2229 if (InlinedDeoptimizeCalls) { 2230 // We need to at least remove the deoptimizing returns from the Return set, 2231 // so that the control flow from those returns does not get merged into the 2232 // caller (but terminate it instead). If the caller's return type does not 2233 // match the callee's return type, we also need to change the return type of 2234 // the intrinsic. 2235 if (Caller->getReturnType() == CB.getType()) { 2236 llvm::erase_if(Returns, [](ReturnInst *RI) { 2237 return RI->getParent()->getTerminatingDeoptimizeCall() != nullptr; 2238 }); 2239 } else { 2240 SmallVector<ReturnInst *, 8> NormalReturns; 2241 Function *NewDeoptIntrinsic = Intrinsic::getDeclaration( 2242 Caller->getParent(), Intrinsic::experimental_deoptimize, 2243 {Caller->getReturnType()}); 2244 2245 for (ReturnInst *RI : Returns) { 2246 CallInst *DeoptCall = RI->getParent()->getTerminatingDeoptimizeCall(); 2247 if (!DeoptCall) { 2248 NormalReturns.push_back(RI); 2249 continue; 2250 } 2251 2252 // The calling convention on the deoptimize call itself may be bogus, 2253 // since the code we're inlining may have undefined behavior (and may 2254 // never actually execute at runtime); but all 2255 // @llvm.experimental.deoptimize declarations have to have the same 2256 // calling convention in a well-formed module. 2257 auto CallingConv = DeoptCall->getCalledFunction()->getCallingConv(); 2258 NewDeoptIntrinsic->setCallingConv(CallingConv); 2259 auto *CurBB = RI->getParent(); 2260 RI->eraseFromParent(); 2261 2262 SmallVector<Value *, 4> CallArgs(DeoptCall->args()); 2263 2264 SmallVector<OperandBundleDef, 1> OpBundles; 2265 DeoptCall->getOperandBundlesAsDefs(OpBundles); 2266 DeoptCall->eraseFromParent(); 2267 assert(!OpBundles.empty() && 2268 "Expected at least the deopt operand bundle"); 2269 2270 IRBuilder<> Builder(CurBB); 2271 CallInst *NewDeoptCall = 2272 Builder.CreateCall(NewDeoptIntrinsic, CallArgs, OpBundles); 2273 NewDeoptCall->setCallingConv(CallingConv); 2274 if (NewDeoptCall->getType()->isVoidTy()) 2275 Builder.CreateRetVoid(); 2276 else 2277 Builder.CreateRet(NewDeoptCall); 2278 } 2279 2280 // Leave behind the normal returns so we can merge control flow. 2281 std::swap(Returns, NormalReturns); 2282 } 2283 } 2284 2285 // Handle any inlined musttail call sites. In order for a new call site to be 2286 // musttail, the source of the clone and the inlined call site must have been 2287 // musttail. Therefore it's safe to return without merging control into the 2288 // phi below. 2289 if (InlinedMustTailCalls) { 2290 // Check if we need to bitcast the result of any musttail calls. 2291 Type *NewRetTy = Caller->getReturnType(); 2292 bool NeedBitCast = !CB.use_empty() && CB.getType() != NewRetTy; 2293 2294 // Handle the returns preceded by musttail calls separately. 2295 SmallVector<ReturnInst *, 8> NormalReturns; 2296 for (ReturnInst *RI : Returns) { 2297 CallInst *ReturnedMustTail = 2298 RI->getParent()->getTerminatingMustTailCall(); 2299 if (!ReturnedMustTail) { 2300 NormalReturns.push_back(RI); 2301 continue; 2302 } 2303 if (!NeedBitCast) 2304 continue; 2305 2306 // Delete the old return and any preceding bitcast. 2307 BasicBlock *CurBB = RI->getParent(); 2308 auto *OldCast = dyn_cast_or_null<BitCastInst>(RI->getReturnValue()); 2309 RI->eraseFromParent(); 2310 if (OldCast) 2311 OldCast->eraseFromParent(); 2312 2313 // Insert a new bitcast and return with the right type. 2314 IRBuilder<> Builder(CurBB); 2315 Builder.CreateRet(Builder.CreateBitCast(ReturnedMustTail, NewRetTy)); 2316 } 2317 2318 // Leave behind the normal returns so we can merge control flow. 2319 std::swap(Returns, NormalReturns); 2320 } 2321 2322 // Now that all of the transforms on the inlined code have taken place but 2323 // before we splice the inlined code into the CFG and lose track of which 2324 // blocks were actually inlined, collect the call sites. We only do this if 2325 // call graph updates weren't requested, as those provide value handle based 2326 // tracking of inlined call sites instead. 2327 if (InlinedFunctionInfo.ContainsCalls && !IFI.CG) { 2328 // Otherwise just collect the raw call sites that were inlined. 2329 for (BasicBlock &NewBB : 2330 make_range(FirstNewBlock->getIterator(), Caller->end())) 2331 for (Instruction &I : NewBB) 2332 if (auto *CB = dyn_cast<CallBase>(&I)) 2333 IFI.InlinedCallSites.push_back(CB); 2334 } 2335 2336 // If we cloned in _exactly one_ basic block, and if that block ends in a 2337 // return instruction, we splice the body of the inlined callee directly into 2338 // the calling basic block. 2339 if (Returns.size() == 1 && std::distance(FirstNewBlock, Caller->end()) == 1) { 2340 // Move all of the instructions right before the call. 2341 OrigBB->getInstList().splice(CB.getIterator(), FirstNewBlock->getInstList(), 2342 FirstNewBlock->begin(), FirstNewBlock->end()); 2343 // Remove the cloned basic block. 2344 Caller->getBasicBlockList().pop_back(); 2345 2346 // If the call site was an invoke instruction, add a branch to the normal 2347 // destination. 2348 if (InvokeInst *II = dyn_cast<InvokeInst>(&CB)) { 2349 BranchInst *NewBr = BranchInst::Create(II->getNormalDest(), &CB); 2350 NewBr->setDebugLoc(Returns[0]->getDebugLoc()); 2351 } 2352 2353 // If the return instruction returned a value, replace uses of the call with 2354 // uses of the returned value. 2355 if (!CB.use_empty()) { 2356 ReturnInst *R = Returns[0]; 2357 if (&CB == R->getReturnValue()) 2358 CB.replaceAllUsesWith(UndefValue::get(CB.getType())); 2359 else 2360 CB.replaceAllUsesWith(R->getReturnValue()); 2361 } 2362 // Since we are now done with the Call/Invoke, we can delete it. 2363 CB.eraseFromParent(); 2364 2365 // Since we are now done with the return instruction, delete it also. 2366 Returns[0]->eraseFromParent(); 2367 2368 // We are now done with the inlining. 2369 return InlineResult::success(); 2370 } 2371 2372 // Otherwise, we have the normal case, of more than one block to inline or 2373 // multiple return sites. 2374 2375 // We want to clone the entire callee function into the hole between the 2376 // "starter" and "ender" blocks. How we accomplish this depends on whether 2377 // this is an invoke instruction or a call instruction. 2378 BasicBlock *AfterCallBB; 2379 BranchInst *CreatedBranchToNormalDest = nullptr; 2380 if (InvokeInst *II = dyn_cast<InvokeInst>(&CB)) { 2381 2382 // Add an unconditional branch to make this look like the CallInst case... 2383 CreatedBranchToNormalDest = BranchInst::Create(II->getNormalDest(), &CB); 2384 2385 // Split the basic block. This guarantees that no PHI nodes will have to be 2386 // updated due to new incoming edges, and make the invoke case more 2387 // symmetric to the call case. 2388 AfterCallBB = 2389 OrigBB->splitBasicBlock(CreatedBranchToNormalDest->getIterator(), 2390 CalledFunc->getName() + ".exit"); 2391 2392 } else { // It's a call 2393 // If this is a call instruction, we need to split the basic block that 2394 // the call lives in. 2395 // 2396 AfterCallBB = OrigBB->splitBasicBlock(CB.getIterator(), 2397 CalledFunc->getName() + ".exit"); 2398 } 2399 2400 if (IFI.CallerBFI) { 2401 // Copy original BB's block frequency to AfterCallBB 2402 IFI.CallerBFI->setBlockFreq( 2403 AfterCallBB, IFI.CallerBFI->getBlockFreq(OrigBB).getFrequency()); 2404 } 2405 2406 // Change the branch that used to go to AfterCallBB to branch to the first 2407 // basic block of the inlined function. 2408 // 2409 Instruction *Br = OrigBB->getTerminator(); 2410 assert(Br && Br->getOpcode() == Instruction::Br && 2411 "splitBasicBlock broken!"); 2412 Br->setOperand(0, &*FirstNewBlock); 2413 2414 // Now that the function is correct, make it a little bit nicer. In 2415 // particular, move the basic blocks inserted from the end of the function 2416 // into the space made by splitting the source basic block. 2417 Caller->getBasicBlockList().splice(AfterCallBB->getIterator(), 2418 Caller->getBasicBlockList(), FirstNewBlock, 2419 Caller->end()); 2420 2421 // Handle all of the return instructions that we just cloned in, and eliminate 2422 // any users of the original call/invoke instruction. 2423 Type *RTy = CalledFunc->getReturnType(); 2424 2425 PHINode *PHI = nullptr; 2426 if (Returns.size() > 1) { 2427 // The PHI node should go at the front of the new basic block to merge all 2428 // possible incoming values. 2429 if (!CB.use_empty()) { 2430 PHI = PHINode::Create(RTy, Returns.size(), CB.getName(), 2431 &AfterCallBB->front()); 2432 // Anything that used the result of the function call should now use the 2433 // PHI node as their operand. 2434 CB.replaceAllUsesWith(PHI); 2435 } 2436 2437 // Loop over all of the return instructions adding entries to the PHI node 2438 // as appropriate. 2439 if (PHI) { 2440 for (unsigned i = 0, e = Returns.size(); i != e; ++i) { 2441 ReturnInst *RI = Returns[i]; 2442 assert(RI->getReturnValue()->getType() == PHI->getType() && 2443 "Ret value not consistent in function!"); 2444 PHI->addIncoming(RI->getReturnValue(), RI->getParent()); 2445 } 2446 } 2447 2448 // Add a branch to the merge points and remove return instructions. 2449 DebugLoc Loc; 2450 for (unsigned i = 0, e = Returns.size(); i != e; ++i) { 2451 ReturnInst *RI = Returns[i]; 2452 BranchInst* BI = BranchInst::Create(AfterCallBB, RI); 2453 Loc = RI->getDebugLoc(); 2454 BI->setDebugLoc(Loc); 2455 RI->eraseFromParent(); 2456 } 2457 // We need to set the debug location to *somewhere* inside the 2458 // inlined function. The line number may be nonsensical, but the 2459 // instruction will at least be associated with the right 2460 // function. 2461 if (CreatedBranchToNormalDest) 2462 CreatedBranchToNormalDest->setDebugLoc(Loc); 2463 } else if (!Returns.empty()) { 2464 // Otherwise, if there is exactly one return value, just replace anything 2465 // using the return value of the call with the computed value. 2466 if (!CB.use_empty()) { 2467 if (&CB == Returns[0]->getReturnValue()) 2468 CB.replaceAllUsesWith(UndefValue::get(CB.getType())); 2469 else 2470 CB.replaceAllUsesWith(Returns[0]->getReturnValue()); 2471 } 2472 2473 // Update PHI nodes that use the ReturnBB to use the AfterCallBB. 2474 BasicBlock *ReturnBB = Returns[0]->getParent(); 2475 ReturnBB->replaceAllUsesWith(AfterCallBB); 2476 2477 // Splice the code from the return block into the block that it will return 2478 // to, which contains the code that was after the call. 2479 AfterCallBB->getInstList().splice(AfterCallBB->begin(), 2480 ReturnBB->getInstList()); 2481 2482 if (CreatedBranchToNormalDest) 2483 CreatedBranchToNormalDest->setDebugLoc(Returns[0]->getDebugLoc()); 2484 2485 // Delete the return instruction now and empty ReturnBB now. 2486 Returns[0]->eraseFromParent(); 2487 ReturnBB->eraseFromParent(); 2488 } else if (!CB.use_empty()) { 2489 // No returns, but something is using the return value of the call. Just 2490 // nuke the result. 2491 CB.replaceAllUsesWith(UndefValue::get(CB.getType())); 2492 } 2493 2494 // Since we are now done with the Call/Invoke, we can delete it. 2495 CB.eraseFromParent(); 2496 2497 // If we inlined any musttail calls and the original return is now 2498 // unreachable, delete it. It can only contain a bitcast and ret. 2499 if (InlinedMustTailCalls && pred_empty(AfterCallBB)) 2500 AfterCallBB->eraseFromParent(); 2501 2502 // We should always be able to fold the entry block of the function into the 2503 // single predecessor of the block... 2504 assert(cast<BranchInst>(Br)->isUnconditional() && "splitBasicBlock broken!"); 2505 BasicBlock *CalleeEntry = cast<BranchInst>(Br)->getSuccessor(0); 2506 2507 // Splice the code entry block into calling block, right before the 2508 // unconditional branch. 2509 CalleeEntry->replaceAllUsesWith(OrigBB); // Update PHI nodes 2510 OrigBB->getInstList().splice(Br->getIterator(), CalleeEntry->getInstList()); 2511 2512 // Remove the unconditional branch. 2513 OrigBB->getInstList().erase(Br); 2514 2515 // Now we can remove the CalleeEntry block, which is now empty. 2516 Caller->getBasicBlockList().erase(CalleeEntry); 2517 2518 // If we inserted a phi node, check to see if it has a single value (e.g. all 2519 // the entries are the same or undef). If so, remove the PHI so it doesn't 2520 // block other optimizations. 2521 if (PHI) { 2522 AssumptionCache *AC = 2523 IFI.GetAssumptionCache ? &IFI.GetAssumptionCache(*Caller) : nullptr; 2524 auto &DL = Caller->getParent()->getDataLayout(); 2525 if (Value *V = SimplifyInstruction(PHI, {DL, nullptr, nullptr, AC})) { 2526 PHI->replaceAllUsesWith(V); 2527 PHI->eraseFromParent(); 2528 } 2529 } 2530 2531 return InlineResult::success(); 2532 } 2533