1 //===-- LoopUtils.cpp - Loop Utility functions -------------------------===// 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 defines common loop utility functions. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/Transforms/Utils/LoopUtils.h" 14 #include "llvm/ADT/DenseSet.h" 15 #include "llvm/ADT/Optional.h" 16 #include "llvm/ADT/PriorityWorklist.h" 17 #include "llvm/ADT/ScopeExit.h" 18 #include "llvm/ADT/SetVector.h" 19 #include "llvm/ADT/SmallPtrSet.h" 20 #include "llvm/ADT/SmallVector.h" 21 #include "llvm/Analysis/AliasAnalysis.h" 22 #include "llvm/Analysis/BasicAliasAnalysis.h" 23 #include "llvm/Analysis/DomTreeUpdater.h" 24 #include "llvm/Analysis/GlobalsModRef.h" 25 #include "llvm/Analysis/InstructionSimplify.h" 26 #include "llvm/Analysis/LoopAccessAnalysis.h" 27 #include "llvm/Analysis/LoopInfo.h" 28 #include "llvm/Analysis/LoopPass.h" 29 #include "llvm/Analysis/MemorySSA.h" 30 #include "llvm/Analysis/MemorySSAUpdater.h" 31 #include "llvm/Analysis/MustExecute.h" 32 #include "llvm/Analysis/ScalarEvolution.h" 33 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" 34 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 35 #include "llvm/Analysis/TargetTransformInfo.h" 36 #include "llvm/Analysis/ValueTracking.h" 37 #include "llvm/IR/DIBuilder.h" 38 #include "llvm/IR/Dominators.h" 39 #include "llvm/IR/Instructions.h" 40 #include "llvm/IR/IntrinsicInst.h" 41 #include "llvm/IR/MDBuilder.h" 42 #include "llvm/IR/Module.h" 43 #include "llvm/IR/Operator.h" 44 #include "llvm/IR/PatternMatch.h" 45 #include "llvm/IR/ValueHandle.h" 46 #include "llvm/InitializePasses.h" 47 #include "llvm/Pass.h" 48 #include "llvm/Support/Debug.h" 49 #include "llvm/Support/KnownBits.h" 50 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 51 #include "llvm/Transforms/Utils/Local.h" 52 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" 53 54 using namespace llvm; 55 using namespace llvm::PatternMatch; 56 57 static cl::opt<bool> ForceReductionIntrinsic( 58 "force-reduction-intrinsics", cl::Hidden, 59 cl::desc("Force creating reduction intrinsics for testing."), 60 cl::init(false)); 61 62 #define DEBUG_TYPE "loop-utils" 63 64 static const char *LLVMLoopDisableNonforced = "llvm.loop.disable_nonforced"; 65 static const char *LLVMLoopDisableLICM = "llvm.licm.disable"; 66 static const char *LLVMLoopMustProgress = "llvm.loop.mustprogress"; 67 68 bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, 69 MemorySSAUpdater *MSSAU, 70 bool PreserveLCSSA) { 71 bool Changed = false; 72 73 // We re-use a vector for the in-loop predecesosrs. 74 SmallVector<BasicBlock *, 4> InLoopPredecessors; 75 76 auto RewriteExit = [&](BasicBlock *BB) { 77 assert(InLoopPredecessors.empty() && 78 "Must start with an empty predecessors list!"); 79 auto Cleanup = make_scope_exit([&] { InLoopPredecessors.clear(); }); 80 81 // See if there are any non-loop predecessors of this exit block and 82 // keep track of the in-loop predecessors. 83 bool IsDedicatedExit = true; 84 for (auto *PredBB : predecessors(BB)) 85 if (L->contains(PredBB)) { 86 if (isa<IndirectBrInst>(PredBB->getTerminator())) 87 // We cannot rewrite exiting edges from an indirectbr. 88 return false; 89 if (isa<CallBrInst>(PredBB->getTerminator())) 90 // We cannot rewrite exiting edges from a callbr. 91 return false; 92 93 InLoopPredecessors.push_back(PredBB); 94 } else { 95 IsDedicatedExit = false; 96 } 97 98 assert(!InLoopPredecessors.empty() && "Must have *some* loop predecessor!"); 99 100 // Nothing to do if this is already a dedicated exit. 101 if (IsDedicatedExit) 102 return false; 103 104 auto *NewExitBB = SplitBlockPredecessors( 105 BB, InLoopPredecessors, ".loopexit", DT, LI, MSSAU, PreserveLCSSA); 106 107 if (!NewExitBB) 108 LLVM_DEBUG( 109 dbgs() << "WARNING: Can't create a dedicated exit block for loop: " 110 << *L << "\n"); 111 else 112 LLVM_DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block " 113 << NewExitBB->getName() << "\n"); 114 return true; 115 }; 116 117 // Walk the exit blocks directly rather than building up a data structure for 118 // them, but only visit each one once. 119 SmallPtrSet<BasicBlock *, 4> Visited; 120 for (auto *BB : L->blocks()) 121 for (auto *SuccBB : successors(BB)) { 122 // We're looking for exit blocks so skip in-loop successors. 123 if (L->contains(SuccBB)) 124 continue; 125 126 // Visit each exit block exactly once. 127 if (!Visited.insert(SuccBB).second) 128 continue; 129 130 Changed |= RewriteExit(SuccBB); 131 } 132 133 return Changed; 134 } 135 136 /// Returns the instructions that use values defined in the loop. 137 SmallVector<Instruction *, 8> llvm::findDefsUsedOutsideOfLoop(Loop *L) { 138 SmallVector<Instruction *, 8> UsedOutside; 139 140 for (auto *Block : L->getBlocks()) 141 // FIXME: I believe that this could use copy_if if the Inst reference could 142 // be adapted into a pointer. 143 for (auto &Inst : *Block) { 144 auto Users = Inst.users(); 145 if (any_of(Users, [&](User *U) { 146 auto *Use = cast<Instruction>(U); 147 return !L->contains(Use->getParent()); 148 })) 149 UsedOutside.push_back(&Inst); 150 } 151 152 return UsedOutside; 153 } 154 155 void llvm::getLoopAnalysisUsage(AnalysisUsage &AU) { 156 // By definition, all loop passes need the LoopInfo analysis and the 157 // Dominator tree it depends on. Because they all participate in the loop 158 // pass manager, they must also preserve these. 159 AU.addRequired<DominatorTreeWrapperPass>(); 160 AU.addPreserved<DominatorTreeWrapperPass>(); 161 AU.addRequired<LoopInfoWrapperPass>(); 162 AU.addPreserved<LoopInfoWrapperPass>(); 163 164 // We must also preserve LoopSimplify and LCSSA. We locally access their IDs 165 // here because users shouldn't directly get them from this header. 166 extern char &LoopSimplifyID; 167 extern char &LCSSAID; 168 AU.addRequiredID(LoopSimplifyID); 169 AU.addPreservedID(LoopSimplifyID); 170 AU.addRequiredID(LCSSAID); 171 AU.addPreservedID(LCSSAID); 172 // This is used in the LPPassManager to perform LCSSA verification on passes 173 // which preserve lcssa form 174 AU.addRequired<LCSSAVerificationPass>(); 175 AU.addPreserved<LCSSAVerificationPass>(); 176 177 // Loop passes are designed to run inside of a loop pass manager which means 178 // that any function analyses they require must be required by the first loop 179 // pass in the manager (so that it is computed before the loop pass manager 180 // runs) and preserved by all loop pasess in the manager. To make this 181 // reasonably robust, the set needed for most loop passes is maintained here. 182 // If your loop pass requires an analysis not listed here, you will need to 183 // carefully audit the loop pass manager nesting structure that results. 184 AU.addRequired<AAResultsWrapperPass>(); 185 AU.addPreserved<AAResultsWrapperPass>(); 186 AU.addPreserved<BasicAAWrapperPass>(); 187 AU.addPreserved<GlobalsAAWrapperPass>(); 188 AU.addPreserved<SCEVAAWrapperPass>(); 189 AU.addRequired<ScalarEvolutionWrapperPass>(); 190 AU.addPreserved<ScalarEvolutionWrapperPass>(); 191 // FIXME: When all loop passes preserve MemorySSA, it can be required and 192 // preserved here instead of the individual handling in each pass. 193 } 194 195 /// Manually defined generic "LoopPass" dependency initialization. This is used 196 /// to initialize the exact set of passes from above in \c 197 /// getLoopAnalysisUsage. It can be used within a loop pass's initialization 198 /// with: 199 /// 200 /// INITIALIZE_PASS_DEPENDENCY(LoopPass) 201 /// 202 /// As-if "LoopPass" were a pass. 203 void llvm::initializeLoopPassPass(PassRegistry &Registry) { 204 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 205 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 206 INITIALIZE_PASS_DEPENDENCY(LoopSimplify) 207 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass) 208 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 209 INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass) 210 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) 211 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass) 212 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) 213 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass) 214 } 215 216 /// Create MDNode for input string. 217 static MDNode *createStringMetadata(Loop *TheLoop, StringRef Name, unsigned V) { 218 LLVMContext &Context = TheLoop->getHeader()->getContext(); 219 Metadata *MDs[] = { 220 MDString::get(Context, Name), 221 ConstantAsMetadata::get(ConstantInt::get(Type::getInt32Ty(Context), V))}; 222 return MDNode::get(Context, MDs); 223 } 224 225 /// Set input string into loop metadata by keeping other values intact. 226 /// If the string is already in loop metadata update value if it is 227 /// different. 228 void llvm::addStringMetadataToLoop(Loop *TheLoop, const char *StringMD, 229 unsigned V) { 230 SmallVector<Metadata *, 4> MDs(1); 231 // If the loop already has metadata, retain it. 232 MDNode *LoopID = TheLoop->getLoopID(); 233 if (LoopID) { 234 for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) { 235 MDNode *Node = cast<MDNode>(LoopID->getOperand(i)); 236 // If it is of form key = value, try to parse it. 237 if (Node->getNumOperands() == 2) { 238 MDString *S = dyn_cast<MDString>(Node->getOperand(0)); 239 if (S && S->getString().equals(StringMD)) { 240 ConstantInt *IntMD = 241 mdconst::extract_or_null<ConstantInt>(Node->getOperand(1)); 242 if (IntMD && IntMD->getSExtValue() == V) 243 // It is already in place. Do nothing. 244 return; 245 // We need to update the value, so just skip it here and it will 246 // be added after copying other existed nodes. 247 continue; 248 } 249 } 250 MDs.push_back(Node); 251 } 252 } 253 // Add new metadata. 254 MDs.push_back(createStringMetadata(TheLoop, StringMD, V)); 255 // Replace current metadata node with new one. 256 LLVMContext &Context = TheLoop->getHeader()->getContext(); 257 MDNode *NewLoopID = MDNode::get(Context, MDs); 258 // Set operand 0 to refer to the loop id itself. 259 NewLoopID->replaceOperandWith(0, NewLoopID); 260 TheLoop->setLoopID(NewLoopID); 261 } 262 263 /// Find string metadata for loop 264 /// 265 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an 266 /// operand or null otherwise. If the string metadata is not found return 267 /// Optional's not-a-value. 268 Optional<const MDOperand *> llvm::findStringMetadataForLoop(const Loop *TheLoop, 269 StringRef Name) { 270 MDNode *MD = findOptionMDForLoop(TheLoop, Name); 271 if (!MD) 272 return None; 273 switch (MD->getNumOperands()) { 274 case 1: 275 return nullptr; 276 case 2: 277 return &MD->getOperand(1); 278 default: 279 llvm_unreachable("loop metadata has 0 or 1 operand"); 280 } 281 } 282 283 static Optional<bool> getOptionalBoolLoopAttribute(const Loop *TheLoop, 284 StringRef Name) { 285 MDNode *MD = findOptionMDForLoop(TheLoop, Name); 286 if (!MD) 287 return None; 288 switch (MD->getNumOperands()) { 289 case 1: 290 // When the value is absent it is interpreted as 'attribute set'. 291 return true; 292 case 2: 293 if (ConstantInt *IntMD = 294 mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get())) 295 return IntMD->getZExtValue(); 296 return true; 297 } 298 llvm_unreachable("unexpected number of options"); 299 } 300 301 bool llvm::getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name) { 302 return getOptionalBoolLoopAttribute(TheLoop, Name).getValueOr(false); 303 } 304 305 Optional<ElementCount> 306 llvm::getOptionalElementCountLoopAttribute(Loop *TheLoop) { 307 Optional<int> Width = 308 getOptionalIntLoopAttribute(TheLoop, "llvm.loop.vectorize.width"); 309 310 if (Width.hasValue()) { 311 Optional<int> IsScalable = getOptionalIntLoopAttribute( 312 TheLoop, "llvm.loop.vectorize.scalable.enable"); 313 return ElementCount::get(*Width, IsScalable.getValueOr(false)); 314 } 315 316 return None; 317 } 318 319 llvm::Optional<int> llvm::getOptionalIntLoopAttribute(Loop *TheLoop, 320 StringRef Name) { 321 const MDOperand *AttrMD = 322 findStringMetadataForLoop(TheLoop, Name).getValueOr(nullptr); 323 if (!AttrMD) 324 return None; 325 326 ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get()); 327 if (!IntMD) 328 return None; 329 330 return IntMD->getSExtValue(); 331 } 332 333 Optional<MDNode *> llvm::makeFollowupLoopID( 334 MDNode *OrigLoopID, ArrayRef<StringRef> FollowupOptions, 335 const char *InheritOptionsExceptPrefix, bool AlwaysNew) { 336 if (!OrigLoopID) { 337 if (AlwaysNew) 338 return nullptr; 339 return None; 340 } 341 342 assert(OrigLoopID->getOperand(0) == OrigLoopID); 343 344 bool InheritAllAttrs = !InheritOptionsExceptPrefix; 345 bool InheritSomeAttrs = 346 InheritOptionsExceptPrefix && InheritOptionsExceptPrefix[0] != '\0'; 347 SmallVector<Metadata *, 8> MDs; 348 MDs.push_back(nullptr); 349 350 bool Changed = false; 351 if (InheritAllAttrs || InheritSomeAttrs) { 352 for (const MDOperand &Existing : drop_begin(OrigLoopID->operands())) { 353 MDNode *Op = cast<MDNode>(Existing.get()); 354 355 auto InheritThisAttribute = [InheritSomeAttrs, 356 InheritOptionsExceptPrefix](MDNode *Op) { 357 if (!InheritSomeAttrs) 358 return false; 359 360 // Skip malformatted attribute metadata nodes. 361 if (Op->getNumOperands() == 0) 362 return true; 363 Metadata *NameMD = Op->getOperand(0).get(); 364 if (!isa<MDString>(NameMD)) 365 return true; 366 StringRef AttrName = cast<MDString>(NameMD)->getString(); 367 368 // Do not inherit excluded attributes. 369 return !AttrName.startswith(InheritOptionsExceptPrefix); 370 }; 371 372 if (InheritThisAttribute(Op)) 373 MDs.push_back(Op); 374 else 375 Changed = true; 376 } 377 } else { 378 // Modified if we dropped at least one attribute. 379 Changed = OrigLoopID->getNumOperands() > 1; 380 } 381 382 bool HasAnyFollowup = false; 383 for (StringRef OptionName : FollowupOptions) { 384 MDNode *FollowupNode = findOptionMDForLoopID(OrigLoopID, OptionName); 385 if (!FollowupNode) 386 continue; 387 388 HasAnyFollowup = true; 389 for (const MDOperand &Option : drop_begin(FollowupNode->operands())) { 390 MDs.push_back(Option.get()); 391 Changed = true; 392 } 393 } 394 395 // Attributes of the followup loop not specified explicity, so signal to the 396 // transformation pass to add suitable attributes. 397 if (!AlwaysNew && !HasAnyFollowup) 398 return None; 399 400 // If no attributes were added or remove, the previous loop Id can be reused. 401 if (!AlwaysNew && !Changed) 402 return OrigLoopID; 403 404 // No attributes is equivalent to having no !llvm.loop metadata at all. 405 if (MDs.size() == 1) 406 return nullptr; 407 408 // Build the new loop ID. 409 MDTuple *FollowupLoopID = MDNode::get(OrigLoopID->getContext(), MDs); 410 FollowupLoopID->replaceOperandWith(0, FollowupLoopID); 411 return FollowupLoopID; 412 } 413 414 bool llvm::hasDisableAllTransformsHint(const Loop *L) { 415 return getBooleanLoopAttribute(L, LLVMLoopDisableNonforced); 416 } 417 418 bool llvm::hasDisableLICMTransformsHint(const Loop *L) { 419 return getBooleanLoopAttribute(L, LLVMLoopDisableLICM); 420 } 421 422 bool llvm::hasMustProgress(const Loop *L) { 423 return getBooleanLoopAttribute(L, LLVMLoopMustProgress); 424 } 425 426 TransformationMode llvm::hasUnrollTransformation(Loop *L) { 427 if (getBooleanLoopAttribute(L, "llvm.loop.unroll.disable")) 428 return TM_SuppressedByUser; 429 430 Optional<int> Count = 431 getOptionalIntLoopAttribute(L, "llvm.loop.unroll.count"); 432 if (Count.hasValue()) 433 return Count.getValue() == 1 ? TM_SuppressedByUser : TM_ForcedByUser; 434 435 if (getBooleanLoopAttribute(L, "llvm.loop.unroll.enable")) 436 return TM_ForcedByUser; 437 438 if (getBooleanLoopAttribute(L, "llvm.loop.unroll.full")) 439 return TM_ForcedByUser; 440 441 if (hasDisableAllTransformsHint(L)) 442 return TM_Disable; 443 444 return TM_Unspecified; 445 } 446 447 TransformationMode llvm::hasUnrollAndJamTransformation(Loop *L) { 448 if (getBooleanLoopAttribute(L, "llvm.loop.unroll_and_jam.disable")) 449 return TM_SuppressedByUser; 450 451 Optional<int> Count = 452 getOptionalIntLoopAttribute(L, "llvm.loop.unroll_and_jam.count"); 453 if (Count.hasValue()) 454 return Count.getValue() == 1 ? TM_SuppressedByUser : TM_ForcedByUser; 455 456 if (getBooleanLoopAttribute(L, "llvm.loop.unroll_and_jam.enable")) 457 return TM_ForcedByUser; 458 459 if (hasDisableAllTransformsHint(L)) 460 return TM_Disable; 461 462 return TM_Unspecified; 463 } 464 465 TransformationMode llvm::hasVectorizeTransformation(Loop *L) { 466 Optional<bool> Enable = 467 getOptionalBoolLoopAttribute(L, "llvm.loop.vectorize.enable"); 468 469 if (Enable == false) 470 return TM_SuppressedByUser; 471 472 Optional<ElementCount> VectorizeWidth = 473 getOptionalElementCountLoopAttribute(L); 474 Optional<int> InterleaveCount = 475 getOptionalIntLoopAttribute(L, "llvm.loop.interleave.count"); 476 477 // 'Forcing' vector width and interleave count to one effectively disables 478 // this tranformation. 479 if (Enable == true && VectorizeWidth && VectorizeWidth->isScalar() && 480 InterleaveCount == 1) 481 return TM_SuppressedByUser; 482 483 if (getBooleanLoopAttribute(L, "llvm.loop.isvectorized")) 484 return TM_Disable; 485 486 if (Enable == true) 487 return TM_ForcedByUser; 488 489 if ((VectorizeWidth && VectorizeWidth->isScalar()) && InterleaveCount == 1) 490 return TM_Disable; 491 492 if ((VectorizeWidth && VectorizeWidth->isVector()) || InterleaveCount > 1) 493 return TM_Enable; 494 495 if (hasDisableAllTransformsHint(L)) 496 return TM_Disable; 497 498 return TM_Unspecified; 499 } 500 501 TransformationMode llvm::hasDistributeTransformation(Loop *L) { 502 if (getBooleanLoopAttribute(L, "llvm.loop.distribute.enable")) 503 return TM_ForcedByUser; 504 505 if (hasDisableAllTransformsHint(L)) 506 return TM_Disable; 507 508 return TM_Unspecified; 509 } 510 511 TransformationMode llvm::hasLICMVersioningTransformation(Loop *L) { 512 if (getBooleanLoopAttribute(L, "llvm.loop.licm_versioning.disable")) 513 return TM_SuppressedByUser; 514 515 if (hasDisableAllTransformsHint(L)) 516 return TM_Disable; 517 518 return TM_Unspecified; 519 } 520 521 /// Does a BFS from a given node to all of its children inside a given loop. 522 /// The returned vector of nodes includes the starting point. 523 SmallVector<DomTreeNode *, 16> 524 llvm::collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop) { 525 SmallVector<DomTreeNode *, 16> Worklist; 526 auto AddRegionToWorklist = [&](DomTreeNode *DTN) { 527 // Only include subregions in the top level loop. 528 BasicBlock *BB = DTN->getBlock(); 529 if (CurLoop->contains(BB)) 530 Worklist.push_back(DTN); 531 }; 532 533 AddRegionToWorklist(N); 534 535 for (size_t I = 0; I < Worklist.size(); I++) { 536 for (DomTreeNode *Child : Worklist[I]->children()) 537 AddRegionToWorklist(Child); 538 } 539 540 return Worklist; 541 } 542 543 void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, 544 LoopInfo *LI, MemorySSA *MSSA) { 545 assert((!DT || L->isLCSSAForm(*DT)) && "Expected LCSSA!"); 546 auto *Preheader = L->getLoopPreheader(); 547 assert(Preheader && "Preheader should exist!"); 548 549 std::unique_ptr<MemorySSAUpdater> MSSAU; 550 if (MSSA) 551 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA); 552 553 // Now that we know the removal is safe, remove the loop by changing the 554 // branch from the preheader to go to the single exit block. 555 // 556 // Because we're deleting a large chunk of code at once, the sequence in which 557 // we remove things is very important to avoid invalidation issues. 558 559 // Tell ScalarEvolution that the loop is deleted. Do this before 560 // deleting the loop so that ScalarEvolution can look at the loop 561 // to determine what it needs to clean up. 562 if (SE) 563 SE->forgetLoop(L); 564 565 auto *OldBr = dyn_cast<BranchInst>(Preheader->getTerminator()); 566 assert(OldBr && "Preheader must end with a branch"); 567 assert(OldBr->isUnconditional() && "Preheader must have a single successor"); 568 // Connect the preheader to the exit block. Keep the old edge to the header 569 // around to perform the dominator tree update in two separate steps 570 // -- #1 insertion of the edge preheader -> exit and #2 deletion of the edge 571 // preheader -> header. 572 // 573 // 574 // 0. Preheader 1. Preheader 2. Preheader 575 // | | | | 576 // V | V | 577 // Header <--\ | Header <--\ | Header <--\ 578 // | | | | | | | | | | | 579 // | V | | | V | | | V | 580 // | Body --/ | | Body --/ | | Body --/ 581 // V V V V V 582 // Exit Exit Exit 583 // 584 // By doing this is two separate steps we can perform the dominator tree 585 // update without using the batch update API. 586 // 587 // Even when the loop is never executed, we cannot remove the edge from the 588 // source block to the exit block. Consider the case where the unexecuted loop 589 // branches back to an outer loop. If we deleted the loop and removed the edge 590 // coming to this inner loop, this will break the outer loop structure (by 591 // deleting the backedge of the outer loop). If the outer loop is indeed a 592 // non-loop, it will be deleted in a future iteration of loop deletion pass. 593 IRBuilder<> Builder(OldBr); 594 595 auto *ExitBlock = L->getUniqueExitBlock(); 596 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager); 597 if (ExitBlock) { 598 assert(ExitBlock && "Should have a unique exit block!"); 599 assert(L->hasDedicatedExits() && "Loop should have dedicated exits!"); 600 601 Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock); 602 // Remove the old branch. The conditional branch becomes a new terminator. 603 OldBr->eraseFromParent(); 604 605 // Rewrite phis in the exit block to get their inputs from the Preheader 606 // instead of the exiting block. 607 for (PHINode &P : ExitBlock->phis()) { 608 // Set the zero'th element of Phi to be from the preheader and remove all 609 // other incoming values. Given the loop has dedicated exits, all other 610 // incoming values must be from the exiting blocks. 611 int PredIndex = 0; 612 P.setIncomingBlock(PredIndex, Preheader); 613 // Removes all incoming values from all other exiting blocks (including 614 // duplicate values from an exiting block). 615 // Nuke all entries except the zero'th entry which is the preheader entry. 616 // NOTE! We need to remove Incoming Values in the reverse order as done 617 // below, to keep the indices valid for deletion (removeIncomingValues 618 // updates getNumIncomingValues and shifts all values down into the 619 // operand being deleted). 620 for (unsigned i = 0, e = P.getNumIncomingValues() - 1; i != e; ++i) 621 P.removeIncomingValue(e - i, false); 622 623 assert((P.getNumIncomingValues() == 1 && 624 P.getIncomingBlock(PredIndex) == Preheader) && 625 "Should have exactly one value and that's from the preheader!"); 626 } 627 628 if (DT) { 629 DTU.applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}}); 630 if (MSSA) { 631 MSSAU->applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}}, 632 *DT); 633 if (VerifyMemorySSA) 634 MSSA->verifyMemorySSA(); 635 } 636 } 637 638 // Disconnect the loop body by branching directly to its exit. 639 Builder.SetInsertPoint(Preheader->getTerminator()); 640 Builder.CreateBr(ExitBlock); 641 // Remove the old branch. 642 Preheader->getTerminator()->eraseFromParent(); 643 } else { 644 assert(L->hasNoExitBlocks() && 645 "Loop should have either zero or one exit blocks."); 646 647 Builder.SetInsertPoint(OldBr); 648 Builder.CreateUnreachable(); 649 Preheader->getTerminator()->eraseFromParent(); 650 } 651 652 if (DT) { 653 DTU.applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}}); 654 if (MSSA) { 655 MSSAU->applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}}, 656 *DT); 657 SmallSetVector<BasicBlock *, 8> DeadBlockSet(L->block_begin(), 658 L->block_end()); 659 MSSAU->removeBlocks(DeadBlockSet); 660 if (VerifyMemorySSA) 661 MSSA->verifyMemorySSA(); 662 } 663 } 664 665 // Use a map to unique and a vector to guarantee deterministic ordering. 666 llvm::SmallDenseSet<std::pair<DIVariable *, DIExpression *>, 4> DeadDebugSet; 667 llvm::SmallVector<DbgVariableIntrinsic *, 4> DeadDebugInst; 668 669 if (ExitBlock) { 670 // Given LCSSA form is satisfied, we should not have users of instructions 671 // within the dead loop outside of the loop. However, LCSSA doesn't take 672 // unreachable uses into account. We handle them here. 673 // We could do it after drop all references (in this case all users in the 674 // loop will be already eliminated and we have less work to do but according 675 // to API doc of User::dropAllReferences only valid operation after dropping 676 // references, is deletion. So let's substitute all usages of 677 // instruction from the loop with undef value of corresponding type first. 678 for (auto *Block : L->blocks()) 679 for (Instruction &I : *Block) { 680 auto *Undef = UndefValue::get(I.getType()); 681 for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); 682 UI != E;) { 683 Use &U = *UI; 684 ++UI; 685 if (auto *Usr = dyn_cast<Instruction>(U.getUser())) 686 if (L->contains(Usr->getParent())) 687 continue; 688 // If we have a DT then we can check that uses outside a loop only in 689 // unreachable block. 690 if (DT) 691 assert(!DT->isReachableFromEntry(U) && 692 "Unexpected user in reachable block"); 693 U.set(Undef); 694 } 695 auto *DVI = dyn_cast<DbgVariableIntrinsic>(&I); 696 if (!DVI) 697 continue; 698 auto Key = 699 DeadDebugSet.find({DVI->getVariable(), DVI->getExpression()}); 700 if (Key != DeadDebugSet.end()) 701 continue; 702 DeadDebugSet.insert({DVI->getVariable(), DVI->getExpression()}); 703 DeadDebugInst.push_back(DVI); 704 } 705 706 // After the loop has been deleted all the values defined and modified 707 // inside the loop are going to be unavailable. 708 // Since debug values in the loop have been deleted, inserting an undef 709 // dbg.value truncates the range of any dbg.value before the loop where the 710 // loop used to be. This is particularly important for constant values. 711 DIBuilder DIB(*ExitBlock->getModule()); 712 Instruction *InsertDbgValueBefore = ExitBlock->getFirstNonPHI(); 713 assert(InsertDbgValueBefore && 714 "There should be a non-PHI instruction in exit block, else these " 715 "instructions will have no parent."); 716 for (auto *DVI : DeadDebugInst) 717 DIB.insertDbgValueIntrinsic(UndefValue::get(Builder.getInt32Ty()), 718 DVI->getVariable(), DVI->getExpression(), 719 DVI->getDebugLoc(), InsertDbgValueBefore); 720 } 721 722 // Remove the block from the reference counting scheme, so that we can 723 // delete it freely later. 724 for (auto *Block : L->blocks()) 725 Block->dropAllReferences(); 726 727 if (MSSA && VerifyMemorySSA) 728 MSSA->verifyMemorySSA(); 729 730 if (LI) { 731 // Erase the instructions and the blocks without having to worry 732 // about ordering because we already dropped the references. 733 // NOTE: This iteration is safe because erasing the block does not remove 734 // its entry from the loop's block list. We do that in the next section. 735 for (Loop::block_iterator LpI = L->block_begin(), LpE = L->block_end(); 736 LpI != LpE; ++LpI) 737 (*LpI)->eraseFromParent(); 738 739 // Finally, the blocks from loopinfo. This has to happen late because 740 // otherwise our loop iterators won't work. 741 742 SmallPtrSet<BasicBlock *, 8> blocks; 743 blocks.insert(L->block_begin(), L->block_end()); 744 for (BasicBlock *BB : blocks) 745 LI->removeBlock(BB); 746 747 // The last step is to update LoopInfo now that we've eliminated this loop. 748 // Note: LoopInfo::erase remove the given loop and relink its subloops with 749 // its parent. While removeLoop/removeChildLoop remove the given loop but 750 // not relink its subloops, which is what we want. 751 if (Loop *ParentLoop = L->getParentLoop()) { 752 Loop::iterator I = find(*ParentLoop, L); 753 assert(I != ParentLoop->end() && "Couldn't find loop"); 754 ParentLoop->removeChildLoop(I); 755 } else { 756 Loop::iterator I = find(*LI, L); 757 assert(I != LI->end() && "Couldn't find loop"); 758 LI->removeLoop(I); 759 } 760 LI->destroy(L); 761 } 762 } 763 764 static Loop *getOutermostLoop(Loop *L) { 765 while (Loop *Parent = L->getParentLoop()) 766 L = Parent; 767 return L; 768 } 769 770 void llvm::breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, 771 LoopInfo &LI, MemorySSA *MSSA) { 772 auto *Latch = L->getLoopLatch(); 773 assert(Latch && "multiple latches not yet supported"); 774 auto *Header = L->getHeader(); 775 Loop *OutermostLoop = getOutermostLoop(L); 776 777 SE.forgetLoop(L); 778 779 // Note: By splitting the backedge, and then explicitly making it unreachable 780 // we gracefully handle corner cases such as non-bottom tested loops and the 781 // like. We also have the benefit of being able to reuse existing well tested 782 // code. It might be worth special casing the common bottom tested case at 783 // some point to avoid code churn. 784 785 std::unique_ptr<MemorySSAUpdater> MSSAU; 786 if (MSSA) 787 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA); 788 789 auto *BackedgeBB = SplitEdge(Latch, Header, &DT, &LI, MSSAU.get()); 790 791 DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Eager); 792 (void)changeToUnreachable(BackedgeBB->getTerminator(), /*UseTrap*/false, 793 /*PreserveLCSSA*/true, &DTU, MSSAU.get()); 794 795 // Erase (and destroy) this loop instance. Handles relinking sub-loops 796 // and blocks within the loop as needed. 797 LI.erase(L); 798 799 // If the loop we broke had a parent, then changeToUnreachable might have 800 // caused a block to be removed from the parent loop (see loop_nest_lcssa 801 // test case in zero-btc.ll for an example), thus changing the parent's 802 // exit blocks. If that happened, we need to rebuild LCSSA on the outermost 803 // loop which might have a had a block removed. 804 if (OutermostLoop != L) 805 formLCSSARecursively(*OutermostLoop, DT, &LI, &SE); 806 } 807 808 809 /// Checks if \p L has single exit through latch block except possibly 810 /// "deoptimizing" exits. Returns branch instruction terminating the loop 811 /// latch if above check is successful, nullptr otherwise. 812 static BranchInst *getExpectedExitLoopLatchBranch(Loop *L) { 813 BasicBlock *Latch = L->getLoopLatch(); 814 if (!Latch) 815 return nullptr; 816 817 BranchInst *LatchBR = dyn_cast<BranchInst>(Latch->getTerminator()); 818 if (!LatchBR || LatchBR->getNumSuccessors() != 2 || !L->isLoopExiting(Latch)) 819 return nullptr; 820 821 assert((LatchBR->getSuccessor(0) == L->getHeader() || 822 LatchBR->getSuccessor(1) == L->getHeader()) && 823 "At least one edge out of the latch must go to the header"); 824 825 SmallVector<BasicBlock *, 4> ExitBlocks; 826 L->getUniqueNonLatchExitBlocks(ExitBlocks); 827 if (any_of(ExitBlocks, [](const BasicBlock *EB) { 828 return !EB->getTerminatingDeoptimizeCall(); 829 })) 830 return nullptr; 831 832 return LatchBR; 833 } 834 835 Optional<unsigned> 836 llvm::getLoopEstimatedTripCount(Loop *L, 837 unsigned *EstimatedLoopInvocationWeight) { 838 // Support loops with an exiting latch and other existing exists only 839 // deoptimize. 840 BranchInst *LatchBranch = getExpectedExitLoopLatchBranch(L); 841 if (!LatchBranch) 842 return None; 843 844 // To estimate the number of times the loop body was executed, we want to 845 // know the number of times the backedge was taken, vs. the number of times 846 // we exited the loop. 847 uint64_t BackedgeTakenWeight, LatchExitWeight; 848 if (!LatchBranch->extractProfMetadata(BackedgeTakenWeight, LatchExitWeight)) 849 return None; 850 851 if (LatchBranch->getSuccessor(0) != L->getHeader()) 852 std::swap(BackedgeTakenWeight, LatchExitWeight); 853 854 if (!LatchExitWeight) 855 return None; 856 857 if (EstimatedLoopInvocationWeight) 858 *EstimatedLoopInvocationWeight = LatchExitWeight; 859 860 // Estimated backedge taken count is a ratio of the backedge taken weight by 861 // the weight of the edge exiting the loop, rounded to nearest. 862 uint64_t BackedgeTakenCount = 863 llvm::divideNearest(BackedgeTakenWeight, LatchExitWeight); 864 // Estimated trip count is one plus estimated backedge taken count. 865 return BackedgeTakenCount + 1; 866 } 867 868 bool llvm::setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount, 869 unsigned EstimatedloopInvocationWeight) { 870 // Support loops with an exiting latch and other existing exists only 871 // deoptimize. 872 BranchInst *LatchBranch = getExpectedExitLoopLatchBranch(L); 873 if (!LatchBranch) 874 return false; 875 876 // Calculate taken and exit weights. 877 unsigned LatchExitWeight = 0; 878 unsigned BackedgeTakenWeight = 0; 879 880 if (EstimatedTripCount > 0) { 881 LatchExitWeight = EstimatedloopInvocationWeight; 882 BackedgeTakenWeight = (EstimatedTripCount - 1) * LatchExitWeight; 883 } 884 885 // Make a swap if back edge is taken when condition is "false". 886 if (LatchBranch->getSuccessor(0) != L->getHeader()) 887 std::swap(BackedgeTakenWeight, LatchExitWeight); 888 889 MDBuilder MDB(LatchBranch->getContext()); 890 891 // Set/Update profile metadata. 892 LatchBranch->setMetadata( 893 LLVMContext::MD_prof, 894 MDB.createBranchWeights(BackedgeTakenWeight, LatchExitWeight)); 895 896 return true; 897 } 898 899 bool llvm::hasIterationCountInvariantInParent(Loop *InnerLoop, 900 ScalarEvolution &SE) { 901 Loop *OuterL = InnerLoop->getParentLoop(); 902 if (!OuterL) 903 return true; 904 905 // Get the backedge taken count for the inner loop 906 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch(); 907 const SCEV *InnerLoopBECountSC = SE.getExitCount(InnerLoop, InnerLoopLatch); 908 if (isa<SCEVCouldNotCompute>(InnerLoopBECountSC) || 909 !InnerLoopBECountSC->getType()->isIntegerTy()) 910 return false; 911 912 // Get whether count is invariant to the outer loop 913 ScalarEvolution::LoopDisposition LD = 914 SE.getLoopDisposition(InnerLoopBECountSC, OuterL); 915 if (LD != ScalarEvolution::LoopInvariant) 916 return false; 917 918 return true; 919 } 920 921 Value *llvm::createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left, 922 Value *Right) { 923 CmpInst::Predicate Pred; 924 switch (RK) { 925 default: 926 llvm_unreachable("Unknown min/max recurrence kind"); 927 case RecurKind::UMin: 928 Pred = CmpInst::ICMP_ULT; 929 break; 930 case RecurKind::UMax: 931 Pred = CmpInst::ICMP_UGT; 932 break; 933 case RecurKind::SMin: 934 Pred = CmpInst::ICMP_SLT; 935 break; 936 case RecurKind::SMax: 937 Pred = CmpInst::ICMP_SGT; 938 break; 939 case RecurKind::FMin: 940 Pred = CmpInst::FCMP_OLT; 941 break; 942 case RecurKind::FMax: 943 Pred = CmpInst::FCMP_OGT; 944 break; 945 } 946 947 // We only match FP sequences that are 'fast', so we can unconditionally 948 // set it on any generated instructions. 949 IRBuilderBase::FastMathFlagGuard FMFG(Builder); 950 FastMathFlags FMF; 951 FMF.setFast(); 952 Builder.setFastMathFlags(FMF); 953 Value *Cmp = Builder.CreateCmp(Pred, Left, Right, "rdx.minmax.cmp"); 954 Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select"); 955 return Select; 956 } 957 958 // Helper to generate an ordered reduction. 959 Value *llvm::getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src, 960 unsigned Op, RecurKind RdxKind, 961 ArrayRef<Value *> RedOps) { 962 unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements(); 963 964 // Extract and apply reduction ops in ascending order: 965 // e.g. ((((Acc + Scl[0]) + Scl[1]) + Scl[2]) + ) ... + Scl[VF-1] 966 Value *Result = Acc; 967 for (unsigned ExtractIdx = 0; ExtractIdx != VF; ++ExtractIdx) { 968 Value *Ext = 969 Builder.CreateExtractElement(Src, Builder.getInt32(ExtractIdx)); 970 971 if (Op != Instruction::ICmp && Op != Instruction::FCmp) { 972 Result = Builder.CreateBinOp((Instruction::BinaryOps)Op, Result, Ext, 973 "bin.rdx"); 974 } else { 975 assert(RecurrenceDescriptor::isMinMaxRecurrenceKind(RdxKind) && 976 "Invalid min/max"); 977 Result = createMinMaxOp(Builder, RdxKind, Result, Ext); 978 } 979 980 if (!RedOps.empty()) 981 propagateIRFlags(Result, RedOps); 982 } 983 984 return Result; 985 } 986 987 // Helper to generate a log2 shuffle reduction. 988 Value *llvm::getShuffleReduction(IRBuilderBase &Builder, Value *Src, 989 unsigned Op, RecurKind RdxKind, 990 ArrayRef<Value *> RedOps) { 991 unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements(); 992 // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles 993 // and vector ops, reducing the set of values being computed by half each 994 // round. 995 assert(isPowerOf2_32(VF) && 996 "Reduction emission only supported for pow2 vectors!"); 997 Value *TmpVec = Src; 998 SmallVector<int, 32> ShuffleMask(VF); 999 for (unsigned i = VF; i != 1; i >>= 1) { 1000 // Move the upper half of the vector to the lower half. 1001 for (unsigned j = 0; j != i / 2; ++j) 1002 ShuffleMask[j] = i / 2 + j; 1003 1004 // Fill the rest of the mask with undef. 1005 std::fill(&ShuffleMask[i / 2], ShuffleMask.end(), -1); 1006 1007 Value *Shuf = Builder.CreateShuffleVector(TmpVec, ShuffleMask, "rdx.shuf"); 1008 1009 if (Op != Instruction::ICmp && Op != Instruction::FCmp) { 1010 // The builder propagates its fast-math-flags setting. 1011 TmpVec = Builder.CreateBinOp((Instruction::BinaryOps)Op, TmpVec, Shuf, 1012 "bin.rdx"); 1013 } else { 1014 assert(RecurrenceDescriptor::isMinMaxRecurrenceKind(RdxKind) && 1015 "Invalid min/max"); 1016 TmpVec = createMinMaxOp(Builder, RdxKind, TmpVec, Shuf); 1017 } 1018 if (!RedOps.empty()) 1019 propagateIRFlags(TmpVec, RedOps); 1020 1021 // We may compute the reassociated scalar ops in a way that does not 1022 // preserve nsw/nuw etc. Conservatively, drop those flags. 1023 if (auto *ReductionInst = dyn_cast<Instruction>(TmpVec)) 1024 ReductionInst->dropPoisonGeneratingFlags(); 1025 } 1026 // The result is in the first element of the vector. 1027 return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0)); 1028 } 1029 1030 Value *llvm::createSimpleTargetReduction(IRBuilderBase &Builder, 1031 const TargetTransformInfo *TTI, 1032 Value *Src, RecurKind RdxKind, 1033 ArrayRef<Value *> RedOps) { 1034 unsigned Opcode = RecurrenceDescriptor::getOpcode(RdxKind); 1035 TargetTransformInfo::ReductionFlags RdxFlags; 1036 RdxFlags.IsMaxOp = RdxKind == RecurKind::SMax || RdxKind == RecurKind::UMax || 1037 RdxKind == RecurKind::FMax; 1038 RdxFlags.IsSigned = RdxKind == RecurKind::SMax || RdxKind == RecurKind::SMin; 1039 if (!ForceReductionIntrinsic && 1040 !TTI->useReductionIntrinsic(Opcode, Src->getType(), RdxFlags)) 1041 return getShuffleReduction(Builder, Src, Opcode, RdxKind, RedOps); 1042 1043 auto *SrcVecEltTy = cast<VectorType>(Src->getType())->getElementType(); 1044 switch (RdxKind) { 1045 case RecurKind::Add: 1046 return Builder.CreateAddReduce(Src); 1047 case RecurKind::Mul: 1048 return Builder.CreateMulReduce(Src); 1049 case RecurKind::And: 1050 return Builder.CreateAndReduce(Src); 1051 case RecurKind::Or: 1052 return Builder.CreateOrReduce(Src); 1053 case RecurKind::Xor: 1054 return Builder.CreateXorReduce(Src); 1055 case RecurKind::FAdd: 1056 return Builder.CreateFAddReduce(ConstantFP::getNegativeZero(SrcVecEltTy), 1057 Src); 1058 case RecurKind::FMul: 1059 return Builder.CreateFMulReduce(ConstantFP::get(SrcVecEltTy, 1.0), Src); 1060 case RecurKind::SMax: 1061 return Builder.CreateIntMaxReduce(Src, true); 1062 case RecurKind::SMin: 1063 return Builder.CreateIntMinReduce(Src, true); 1064 case RecurKind::UMax: 1065 return Builder.CreateIntMaxReduce(Src, false); 1066 case RecurKind::UMin: 1067 return Builder.CreateIntMinReduce(Src, false); 1068 case RecurKind::FMax: 1069 return Builder.CreateFPMaxReduce(Src); 1070 case RecurKind::FMin: 1071 return Builder.CreateFPMinReduce(Src); 1072 default: 1073 llvm_unreachable("Unhandled opcode"); 1074 } 1075 } 1076 1077 Value *llvm::createTargetReduction(IRBuilderBase &B, 1078 const TargetTransformInfo *TTI, 1079 RecurrenceDescriptor &Desc, Value *Src) { 1080 // TODO: Support in-order reductions based on the recurrence descriptor. 1081 // All ops in the reduction inherit fast-math-flags from the recurrence 1082 // descriptor. 1083 IRBuilderBase::FastMathFlagGuard FMFGuard(B); 1084 B.setFastMathFlags(Desc.getFastMathFlags()); 1085 return createSimpleTargetReduction(B, TTI, Src, Desc.getRecurrenceKind()); 1086 } 1087 1088 void llvm::propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue) { 1089 auto *VecOp = dyn_cast<Instruction>(I); 1090 if (!VecOp) 1091 return; 1092 auto *Intersection = (OpValue == nullptr) ? dyn_cast<Instruction>(VL[0]) 1093 : dyn_cast<Instruction>(OpValue); 1094 if (!Intersection) 1095 return; 1096 const unsigned Opcode = Intersection->getOpcode(); 1097 VecOp->copyIRFlags(Intersection); 1098 for (auto *V : VL) { 1099 auto *Instr = dyn_cast<Instruction>(V); 1100 if (!Instr) 1101 continue; 1102 if (OpValue == nullptr || Opcode == Instr->getOpcode()) 1103 VecOp->andIRFlags(V); 1104 } 1105 } 1106 1107 bool llvm::isKnownNegativeInLoop(const SCEV *S, const Loop *L, 1108 ScalarEvolution &SE) { 1109 const SCEV *Zero = SE.getZero(S->getType()); 1110 return SE.isAvailableAtLoopEntry(S, L) && 1111 SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SLT, S, Zero); 1112 } 1113 1114 bool llvm::isKnownNonNegativeInLoop(const SCEV *S, const Loop *L, 1115 ScalarEvolution &SE) { 1116 const SCEV *Zero = SE.getZero(S->getType()); 1117 return SE.isAvailableAtLoopEntry(S, L) && 1118 SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGE, S, Zero); 1119 } 1120 1121 bool llvm::cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, 1122 bool Signed) { 1123 unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth(); 1124 APInt Min = Signed ? APInt::getSignedMinValue(BitWidth) : 1125 APInt::getMinValue(BitWidth); 1126 auto Predicate = Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; 1127 return SE.isAvailableAtLoopEntry(S, L) && 1128 SE.isLoopEntryGuardedByCond(L, Predicate, S, 1129 SE.getConstant(Min)); 1130 } 1131 1132 bool llvm::cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, 1133 bool Signed) { 1134 unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth(); 1135 APInt Max = Signed ? APInt::getSignedMaxValue(BitWidth) : 1136 APInt::getMaxValue(BitWidth); 1137 auto Predicate = Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; 1138 return SE.isAvailableAtLoopEntry(S, L) && 1139 SE.isLoopEntryGuardedByCond(L, Predicate, S, 1140 SE.getConstant(Max)); 1141 } 1142 1143 //===----------------------------------------------------------------------===// 1144 // rewriteLoopExitValues - Optimize IV users outside the loop. 1145 // As a side effect, reduces the amount of IV processing within the loop. 1146 //===----------------------------------------------------------------------===// 1147 1148 // Return true if the SCEV expansion generated by the rewriter can replace the 1149 // original value. SCEV guarantees that it produces the same value, but the way 1150 // it is produced may be illegal IR. Ideally, this function will only be 1151 // called for verification. 1152 static bool isValidRewrite(ScalarEvolution *SE, Value *FromVal, Value *ToVal) { 1153 // If an SCEV expression subsumed multiple pointers, its expansion could 1154 // reassociate the GEP changing the base pointer. This is illegal because the 1155 // final address produced by a GEP chain must be inbounds relative to its 1156 // underlying object. Otherwise basic alias analysis, among other things, 1157 // could fail in a dangerous way. Ultimately, SCEV will be improved to avoid 1158 // producing an expression involving multiple pointers. Until then, we must 1159 // bail out here. 1160 // 1161 // Retrieve the pointer operand of the GEP. Don't use getUnderlyingObject 1162 // because it understands lcssa phis while SCEV does not. 1163 Value *FromPtr = FromVal; 1164 Value *ToPtr = ToVal; 1165 if (auto *GEP = dyn_cast<GEPOperator>(FromVal)) 1166 FromPtr = GEP->getPointerOperand(); 1167 1168 if (auto *GEP = dyn_cast<GEPOperator>(ToVal)) 1169 ToPtr = GEP->getPointerOperand(); 1170 1171 if (FromPtr != FromVal || ToPtr != ToVal) { 1172 // Quickly check the common case 1173 if (FromPtr == ToPtr) 1174 return true; 1175 1176 // SCEV may have rewritten an expression that produces the GEP's pointer 1177 // operand. That's ok as long as the pointer operand has the same base 1178 // pointer. Unlike getUnderlyingObject(), getPointerBase() will find the 1179 // base of a recurrence. This handles the case in which SCEV expansion 1180 // converts a pointer type recurrence into a nonrecurrent pointer base 1181 // indexed by an integer recurrence. 1182 1183 // If the GEP base pointer is a vector of pointers, abort. 1184 if (!FromPtr->getType()->isPointerTy() || !ToPtr->getType()->isPointerTy()) 1185 return false; 1186 1187 const SCEV *FromBase = SE->getPointerBase(SE->getSCEV(FromPtr)); 1188 const SCEV *ToBase = SE->getPointerBase(SE->getSCEV(ToPtr)); 1189 if (FromBase == ToBase) 1190 return true; 1191 1192 LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: GEP rewrite bail out " 1193 << *FromBase << " != " << *ToBase << "\n"); 1194 1195 return false; 1196 } 1197 return true; 1198 } 1199 1200 static bool hasHardUserWithinLoop(const Loop *L, const Instruction *I) { 1201 SmallPtrSet<const Instruction *, 8> Visited; 1202 SmallVector<const Instruction *, 8> WorkList; 1203 Visited.insert(I); 1204 WorkList.push_back(I); 1205 while (!WorkList.empty()) { 1206 const Instruction *Curr = WorkList.pop_back_val(); 1207 // This use is outside the loop, nothing to do. 1208 if (!L->contains(Curr)) 1209 continue; 1210 // Do we assume it is a "hard" use which will not be eliminated easily? 1211 if (Curr->mayHaveSideEffects()) 1212 return true; 1213 // Otherwise, add all its users to worklist. 1214 for (auto U : Curr->users()) { 1215 auto *UI = cast<Instruction>(U); 1216 if (Visited.insert(UI).second) 1217 WorkList.push_back(UI); 1218 } 1219 } 1220 return false; 1221 } 1222 1223 // Collect information about PHI nodes which can be transformed in 1224 // rewriteLoopExitValues. 1225 struct RewritePhi { 1226 PHINode *PN; // For which PHI node is this replacement? 1227 unsigned Ith; // For which incoming value? 1228 const SCEV *ExpansionSCEV; // The SCEV of the incoming value we are rewriting. 1229 Instruction *ExpansionPoint; // Where we'd like to expand that SCEV? 1230 bool HighCost; // Is this expansion a high-cost? 1231 1232 Value *Expansion = nullptr; 1233 bool ValidRewrite = false; 1234 1235 RewritePhi(PHINode *P, unsigned I, const SCEV *Val, Instruction *ExpansionPt, 1236 bool H) 1237 : PN(P), Ith(I), ExpansionSCEV(Val), ExpansionPoint(ExpansionPt), 1238 HighCost(H) {} 1239 }; 1240 1241 // Check whether it is possible to delete the loop after rewriting exit 1242 // value. If it is possible, ignore ReplaceExitValue and do rewriting 1243 // aggressively. 1244 static bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet) { 1245 BasicBlock *Preheader = L->getLoopPreheader(); 1246 // If there is no preheader, the loop will not be deleted. 1247 if (!Preheader) 1248 return false; 1249 1250 // In LoopDeletion pass Loop can be deleted when ExitingBlocks.size() > 1. 1251 // We obviate multiple ExitingBlocks case for simplicity. 1252 // TODO: If we see testcase with multiple ExitingBlocks can be deleted 1253 // after exit value rewriting, we can enhance the logic here. 1254 SmallVector<BasicBlock *, 4> ExitingBlocks; 1255 L->getExitingBlocks(ExitingBlocks); 1256 SmallVector<BasicBlock *, 8> ExitBlocks; 1257 L->getUniqueExitBlocks(ExitBlocks); 1258 if (ExitBlocks.size() != 1 || ExitingBlocks.size() != 1) 1259 return false; 1260 1261 BasicBlock *ExitBlock = ExitBlocks[0]; 1262 BasicBlock::iterator BI = ExitBlock->begin(); 1263 while (PHINode *P = dyn_cast<PHINode>(BI)) { 1264 Value *Incoming = P->getIncomingValueForBlock(ExitingBlocks[0]); 1265 1266 // If the Incoming value of P is found in RewritePhiSet, we know it 1267 // could be rewritten to use a loop invariant value in transformation 1268 // phase later. Skip it in the loop invariant check below. 1269 bool found = false; 1270 for (const RewritePhi &Phi : RewritePhiSet) { 1271 if (!Phi.ValidRewrite) 1272 continue; 1273 unsigned i = Phi.Ith; 1274 if (Phi.PN == P && (Phi.PN)->getIncomingValue(i) == Incoming) { 1275 found = true; 1276 break; 1277 } 1278 } 1279 1280 Instruction *I; 1281 if (!found && (I = dyn_cast<Instruction>(Incoming))) 1282 if (!L->hasLoopInvariantOperands(I)) 1283 return false; 1284 1285 ++BI; 1286 } 1287 1288 for (auto *BB : L->blocks()) 1289 if (llvm::any_of(*BB, [](Instruction &I) { 1290 return I.mayHaveSideEffects(); 1291 })) 1292 return false; 1293 1294 return true; 1295 } 1296 1297 int llvm::rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI, 1298 ScalarEvolution *SE, 1299 const TargetTransformInfo *TTI, 1300 SCEVExpander &Rewriter, DominatorTree *DT, 1301 ReplaceExitVal ReplaceExitValue, 1302 SmallVector<WeakTrackingVH, 16> &DeadInsts) { 1303 // Check a pre-condition. 1304 assert(L->isRecursivelyLCSSAForm(*DT, *LI) && 1305 "Indvars did not preserve LCSSA!"); 1306 1307 SmallVector<BasicBlock*, 8> ExitBlocks; 1308 L->getUniqueExitBlocks(ExitBlocks); 1309 1310 SmallVector<RewritePhi, 8> RewritePhiSet; 1311 // Find all values that are computed inside the loop, but used outside of it. 1312 // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan 1313 // the exit blocks of the loop to find them. 1314 for (BasicBlock *ExitBB : ExitBlocks) { 1315 // If there are no PHI nodes in this exit block, then no values defined 1316 // inside the loop are used on this path, skip it. 1317 PHINode *PN = dyn_cast<PHINode>(ExitBB->begin()); 1318 if (!PN) continue; 1319 1320 unsigned NumPreds = PN->getNumIncomingValues(); 1321 1322 // Iterate over all of the PHI nodes. 1323 BasicBlock::iterator BBI = ExitBB->begin(); 1324 while ((PN = dyn_cast<PHINode>(BBI++))) { 1325 if (PN->use_empty()) 1326 continue; // dead use, don't replace it 1327 1328 if (!SE->isSCEVable(PN->getType())) 1329 continue; 1330 1331 // It's necessary to tell ScalarEvolution about this explicitly so that 1332 // it can walk the def-use list and forget all SCEVs, as it may not be 1333 // watching the PHI itself. Once the new exit value is in place, there 1334 // may not be a def-use connection between the loop and every instruction 1335 // which got a SCEVAddRecExpr for that loop. 1336 SE->forgetValue(PN); 1337 1338 // Iterate over all of the values in all the PHI nodes. 1339 for (unsigned i = 0; i != NumPreds; ++i) { 1340 // If the value being merged in is not integer or is not defined 1341 // in the loop, skip it. 1342 Value *InVal = PN->getIncomingValue(i); 1343 if (!isa<Instruction>(InVal)) 1344 continue; 1345 1346 // If this pred is for a subloop, not L itself, skip it. 1347 if (LI->getLoopFor(PN->getIncomingBlock(i)) != L) 1348 continue; // The Block is in a subloop, skip it. 1349 1350 // Check that InVal is defined in the loop. 1351 Instruction *Inst = cast<Instruction>(InVal); 1352 if (!L->contains(Inst)) 1353 continue; 1354 1355 // Okay, this instruction has a user outside of the current loop 1356 // and varies predictably *inside* the loop. Evaluate the value it 1357 // contains when the loop exits, if possible. We prefer to start with 1358 // expressions which are true for all exits (so as to maximize 1359 // expression reuse by the SCEVExpander), but resort to per-exit 1360 // evaluation if that fails. 1361 const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop()); 1362 if (isa<SCEVCouldNotCompute>(ExitValue) || 1363 !SE->isLoopInvariant(ExitValue, L) || 1364 !isSafeToExpand(ExitValue, *SE)) { 1365 // TODO: This should probably be sunk into SCEV in some way; maybe a 1366 // getSCEVForExit(SCEV*, L, ExitingBB)? It can be generalized for 1367 // most SCEV expressions and other recurrence types (e.g. shift 1368 // recurrences). Is there existing code we can reuse? 1369 const SCEV *ExitCount = SE->getExitCount(L, PN->getIncomingBlock(i)); 1370 if (isa<SCEVCouldNotCompute>(ExitCount)) 1371 continue; 1372 if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Inst))) 1373 if (AddRec->getLoop() == L) 1374 ExitValue = AddRec->evaluateAtIteration(ExitCount, *SE); 1375 if (isa<SCEVCouldNotCompute>(ExitValue) || 1376 !SE->isLoopInvariant(ExitValue, L) || 1377 !isSafeToExpand(ExitValue, *SE)) 1378 continue; 1379 } 1380 1381 // Computing the value outside of the loop brings no benefit if it is 1382 // definitely used inside the loop in a way which can not be optimized 1383 // away. Avoid doing so unless we know we have a value which computes 1384 // the ExitValue already. TODO: This should be merged into SCEV 1385 // expander to leverage its knowledge of existing expressions. 1386 if (ReplaceExitValue != AlwaysRepl && !isa<SCEVConstant>(ExitValue) && 1387 !isa<SCEVUnknown>(ExitValue) && hasHardUserWithinLoop(L, Inst)) 1388 continue; 1389 1390 // Check if expansions of this SCEV would count as being high cost. 1391 bool HighCost = Rewriter.isHighCostExpansion( 1392 ExitValue, L, SCEVCheapExpansionBudget, TTI, Inst); 1393 1394 // Note that we must not perform expansions until after 1395 // we query *all* the costs, because if we perform temporary expansion 1396 // inbetween, one that we might not intend to keep, said expansion 1397 // *may* affect cost calculation of the the next SCEV's we'll query, 1398 // and next SCEV may errneously get smaller cost. 1399 1400 // Collect all the candidate PHINodes to be rewritten. 1401 RewritePhiSet.emplace_back(PN, i, ExitValue, Inst, HighCost); 1402 } 1403 } 1404 } 1405 1406 // Now that we've done preliminary filtering and billed all the SCEV's, 1407 // we can perform the last sanity check - the expansion must be valid. 1408 for (RewritePhi &Phi : RewritePhiSet) { 1409 Phi.Expansion = Rewriter.expandCodeFor(Phi.ExpansionSCEV, Phi.PN->getType(), 1410 Phi.ExpansionPoint); 1411 1412 LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: AfterLoopVal = " 1413 << *(Phi.Expansion) << '\n' 1414 << " LoopVal = " << *(Phi.ExpansionPoint) << "\n"); 1415 1416 // FIXME: isValidRewrite() is a hack. it should be an assert, eventually. 1417 Phi.ValidRewrite = isValidRewrite(SE, Phi.ExpansionPoint, Phi.Expansion); 1418 if (!Phi.ValidRewrite) { 1419 DeadInsts.push_back(Phi.Expansion); 1420 continue; 1421 } 1422 1423 #ifndef NDEBUG 1424 // If we reuse an instruction from a loop which is neither L nor one of 1425 // its containing loops, we end up breaking LCSSA form for this loop by 1426 // creating a new use of its instruction. 1427 if (auto *ExitInsn = dyn_cast<Instruction>(Phi.Expansion)) 1428 if (auto *EVL = LI->getLoopFor(ExitInsn->getParent())) 1429 if (EVL != L) 1430 assert(EVL->contains(L) && "LCSSA breach detected!"); 1431 #endif 1432 } 1433 1434 // TODO: after isValidRewrite() is an assertion, evaluate whether 1435 // it is beneficial to change how we calculate high-cost: 1436 // if we have SCEV 'A' which we know we will expand, should we calculate 1437 // the cost of other SCEV's after expanding SCEV 'A', 1438 // thus potentially giving cost bonus to those other SCEV's? 1439 1440 bool LoopCanBeDel = canLoopBeDeleted(L, RewritePhiSet); 1441 int NumReplaced = 0; 1442 1443 // Transformation. 1444 for (const RewritePhi &Phi : RewritePhiSet) { 1445 if (!Phi.ValidRewrite) 1446 continue; 1447 1448 PHINode *PN = Phi.PN; 1449 Value *ExitVal = Phi.Expansion; 1450 1451 // Only do the rewrite when the ExitValue can be expanded cheaply. 1452 // If LoopCanBeDel is true, rewrite exit value aggressively. 1453 if (ReplaceExitValue == OnlyCheapRepl && !LoopCanBeDel && Phi.HighCost) { 1454 DeadInsts.push_back(ExitVal); 1455 continue; 1456 } 1457 1458 NumReplaced++; 1459 Instruction *Inst = cast<Instruction>(PN->getIncomingValue(Phi.Ith)); 1460 PN->setIncomingValue(Phi.Ith, ExitVal); 1461 1462 // If this instruction is dead now, delete it. Don't do it now to avoid 1463 // invalidating iterators. 1464 if (isInstructionTriviallyDead(Inst, TLI)) 1465 DeadInsts.push_back(Inst); 1466 1467 // Replace PN with ExitVal if that is legal and does not break LCSSA. 1468 if (PN->getNumIncomingValues() == 1 && 1469 LI->replacementPreservesLCSSAForm(PN, ExitVal)) { 1470 PN->replaceAllUsesWith(ExitVal); 1471 PN->eraseFromParent(); 1472 } 1473 } 1474 1475 // The insertion point instruction may have been deleted; clear it out 1476 // so that the rewriter doesn't trip over it later. 1477 Rewriter.clearInsertPoint(); 1478 return NumReplaced; 1479 } 1480 1481 /// Set weights for \p UnrolledLoop and \p RemainderLoop based on weights for 1482 /// \p OrigLoop. 1483 void llvm::setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop, 1484 Loop *RemainderLoop, uint64_t UF) { 1485 assert(UF > 0 && "Zero unrolled factor is not supported"); 1486 assert(UnrolledLoop != RemainderLoop && 1487 "Unrolled and Remainder loops are expected to distinct"); 1488 1489 // Get number of iterations in the original scalar loop. 1490 unsigned OrigLoopInvocationWeight = 0; 1491 Optional<unsigned> OrigAverageTripCount = 1492 getLoopEstimatedTripCount(OrigLoop, &OrigLoopInvocationWeight); 1493 if (!OrigAverageTripCount) 1494 return; 1495 1496 // Calculate number of iterations in unrolled loop. 1497 unsigned UnrolledAverageTripCount = *OrigAverageTripCount / UF; 1498 // Calculate number of iterations for remainder loop. 1499 unsigned RemainderAverageTripCount = *OrigAverageTripCount % UF; 1500 1501 setLoopEstimatedTripCount(UnrolledLoop, UnrolledAverageTripCount, 1502 OrigLoopInvocationWeight); 1503 setLoopEstimatedTripCount(RemainderLoop, RemainderAverageTripCount, 1504 OrigLoopInvocationWeight); 1505 } 1506 1507 /// Utility that implements appending of loops onto a worklist. 1508 /// Loops are added in preorder (analogous for reverse postorder for trees), 1509 /// and the worklist is processed LIFO. 1510 template <typename RangeT> 1511 void llvm::appendReversedLoopsToWorklist( 1512 RangeT &&Loops, SmallPriorityWorklist<Loop *, 4> &Worklist) { 1513 // We use an internal worklist to build up the preorder traversal without 1514 // recursion. 1515 SmallVector<Loop *, 4> PreOrderLoops, PreOrderWorklist; 1516 1517 // We walk the initial sequence of loops in reverse because we generally want 1518 // to visit defs before uses and the worklist is LIFO. 1519 for (Loop *RootL : Loops) { 1520 assert(PreOrderLoops.empty() && "Must start with an empty preorder walk."); 1521 assert(PreOrderWorklist.empty() && 1522 "Must start with an empty preorder walk worklist."); 1523 PreOrderWorklist.push_back(RootL); 1524 do { 1525 Loop *L = PreOrderWorklist.pop_back_val(); 1526 PreOrderWorklist.append(L->begin(), L->end()); 1527 PreOrderLoops.push_back(L); 1528 } while (!PreOrderWorklist.empty()); 1529 1530 Worklist.insert(std::move(PreOrderLoops)); 1531 PreOrderLoops.clear(); 1532 } 1533 } 1534 1535 template <typename RangeT> 1536 void llvm::appendLoopsToWorklist(RangeT &&Loops, 1537 SmallPriorityWorklist<Loop *, 4> &Worklist) { 1538 appendReversedLoopsToWorklist(reverse(Loops), Worklist); 1539 } 1540 1541 template void llvm::appendLoopsToWorklist<ArrayRef<Loop *> &>( 1542 ArrayRef<Loop *> &Loops, SmallPriorityWorklist<Loop *, 4> &Worklist); 1543 1544 template void 1545 llvm::appendLoopsToWorklist<Loop &>(Loop &L, 1546 SmallPriorityWorklist<Loop *, 4> &Worklist); 1547 1548 void llvm::appendLoopsToWorklist(LoopInfo &LI, 1549 SmallPriorityWorklist<Loop *, 4> &Worklist) { 1550 appendReversedLoopsToWorklist(LI, Worklist); 1551 } 1552 1553 Loop *llvm::cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, 1554 LoopInfo *LI, LPPassManager *LPM) { 1555 Loop &New = *LI->AllocateLoop(); 1556 if (PL) 1557 PL->addChildLoop(&New); 1558 else 1559 LI->addTopLevelLoop(&New); 1560 1561 if (LPM) 1562 LPM->addLoop(New); 1563 1564 // Add all of the blocks in L to the new loop. 1565 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 1566 I != E; ++I) 1567 if (LI->getLoopFor(*I) == L) 1568 New.addBasicBlockToLoop(cast<BasicBlock>(VM[*I]), *LI); 1569 1570 // Add all of the subloops to the new loop. 1571 for (Loop *I : *L) 1572 cloneLoop(I, &New, VM, LI, LPM); 1573 1574 return &New; 1575 } 1576 1577 /// IR Values for the lower and upper bounds of a pointer evolution. We 1578 /// need to use value-handles because SCEV expansion can invalidate previously 1579 /// expanded values. Thus expansion of a pointer can invalidate the bounds for 1580 /// a previous one. 1581 struct PointerBounds { 1582 TrackingVH<Value> Start; 1583 TrackingVH<Value> End; 1584 }; 1585 1586 /// Expand code for the lower and upper bound of the pointer group \p CG 1587 /// in \p TheLoop. \return the values for the bounds. 1588 static PointerBounds expandBounds(const RuntimeCheckingPtrGroup *CG, 1589 Loop *TheLoop, Instruction *Loc, 1590 SCEVExpander &Exp, ScalarEvolution *SE) { 1591 // TODO: Add helper to retrieve pointers to CG. 1592 Value *Ptr = CG->RtCheck.Pointers[CG->Members[0]].PointerValue; 1593 const SCEV *Sc = SE->getSCEV(Ptr); 1594 1595 unsigned AS = Ptr->getType()->getPointerAddressSpace(); 1596 LLVMContext &Ctx = Loc->getContext(); 1597 1598 // Use this type for pointer arithmetic. 1599 Type *PtrArithTy = Type::getInt8PtrTy(Ctx, AS); 1600 1601 if (SE->isLoopInvariant(Sc, TheLoop)) { 1602 LLVM_DEBUG(dbgs() << "LAA: Adding RT check for a loop invariant ptr:" 1603 << *Ptr << "\n"); 1604 // Ptr could be in the loop body. If so, expand a new one at the correct 1605 // location. 1606 Instruction *Inst = dyn_cast<Instruction>(Ptr); 1607 Value *NewPtr = (Inst && TheLoop->contains(Inst)) 1608 ? Exp.expandCodeFor(Sc, PtrArithTy, Loc) 1609 : Ptr; 1610 // We must return a half-open range, which means incrementing Sc. 1611 const SCEV *ScPlusOne = SE->getAddExpr(Sc, SE->getOne(PtrArithTy)); 1612 Value *NewPtrPlusOne = Exp.expandCodeFor(ScPlusOne, PtrArithTy, Loc); 1613 return {NewPtr, NewPtrPlusOne}; 1614 } else { 1615 Value *Start = nullptr, *End = nullptr; 1616 LLVM_DEBUG(dbgs() << "LAA: Adding RT check for range:\n"); 1617 Start = Exp.expandCodeFor(CG->Low, PtrArithTy, Loc); 1618 End = Exp.expandCodeFor(CG->High, PtrArithTy, Loc); 1619 LLVM_DEBUG(dbgs() << "Start: " << *CG->Low << " End: " << *CG->High 1620 << "\n"); 1621 return {Start, End}; 1622 } 1623 } 1624 1625 /// Turns a collection of checks into a collection of expanded upper and 1626 /// lower bounds for both pointers in the check. 1627 static SmallVector<std::pair<PointerBounds, PointerBounds>, 4> 1628 expandBounds(const SmallVectorImpl<RuntimePointerCheck> &PointerChecks, Loop *L, 1629 Instruction *Loc, ScalarEvolution *SE, SCEVExpander &Exp) { 1630 SmallVector<std::pair<PointerBounds, PointerBounds>, 4> ChecksWithBounds; 1631 1632 // Here we're relying on the SCEV Expander's cache to only emit code for the 1633 // same bounds once. 1634 transform(PointerChecks, std::back_inserter(ChecksWithBounds), 1635 [&](const RuntimePointerCheck &Check) { 1636 PointerBounds First = expandBounds(Check.first, L, Loc, Exp, SE), 1637 Second = 1638 expandBounds(Check.second, L, Loc, Exp, SE); 1639 return std::make_pair(First, Second); 1640 }); 1641 1642 return ChecksWithBounds; 1643 } 1644 1645 std::pair<Instruction *, Instruction *> llvm::addRuntimeChecks( 1646 Instruction *Loc, Loop *TheLoop, 1647 const SmallVectorImpl<RuntimePointerCheck> &PointerChecks, 1648 ScalarEvolution *SE) { 1649 // TODO: Move noalias annotation code from LoopVersioning here and share with LV if possible. 1650 // TODO: Pass RtPtrChecking instead of PointerChecks and SE separately, if possible 1651 const DataLayout &DL = TheLoop->getHeader()->getModule()->getDataLayout(); 1652 SCEVExpander Exp(*SE, DL, "induction"); 1653 auto ExpandedChecks = expandBounds(PointerChecks, TheLoop, Loc, SE, Exp); 1654 1655 LLVMContext &Ctx = Loc->getContext(); 1656 Instruction *FirstInst = nullptr; 1657 IRBuilder<> ChkBuilder(Loc); 1658 // Our instructions might fold to a constant. 1659 Value *MemoryRuntimeCheck = nullptr; 1660 1661 // FIXME: this helper is currently a duplicate of the one in 1662 // LoopVectorize.cpp. 1663 auto GetFirstInst = [](Instruction *FirstInst, Value *V, 1664 Instruction *Loc) -> Instruction * { 1665 if (FirstInst) 1666 return FirstInst; 1667 if (Instruction *I = dyn_cast<Instruction>(V)) 1668 return I->getParent() == Loc->getParent() ? I : nullptr; 1669 return nullptr; 1670 }; 1671 1672 for (const auto &Check : ExpandedChecks) { 1673 const PointerBounds &A = Check.first, &B = Check.second; 1674 // Check if two pointers (A and B) conflict where conflict is computed as: 1675 // start(A) <= end(B) && start(B) <= end(A) 1676 unsigned AS0 = A.Start->getType()->getPointerAddressSpace(); 1677 unsigned AS1 = B.Start->getType()->getPointerAddressSpace(); 1678 1679 assert((AS0 == B.End->getType()->getPointerAddressSpace()) && 1680 (AS1 == A.End->getType()->getPointerAddressSpace()) && 1681 "Trying to bounds check pointers with different address spaces"); 1682 1683 Type *PtrArithTy0 = Type::getInt8PtrTy(Ctx, AS0); 1684 Type *PtrArithTy1 = Type::getInt8PtrTy(Ctx, AS1); 1685 1686 Value *Start0 = ChkBuilder.CreateBitCast(A.Start, PtrArithTy0, "bc"); 1687 Value *Start1 = ChkBuilder.CreateBitCast(B.Start, PtrArithTy1, "bc"); 1688 Value *End0 = ChkBuilder.CreateBitCast(A.End, PtrArithTy1, "bc"); 1689 Value *End1 = ChkBuilder.CreateBitCast(B.End, PtrArithTy0, "bc"); 1690 1691 // [A|B].Start points to the first accessed byte under base [A|B]. 1692 // [A|B].End points to the last accessed byte, plus one. 1693 // There is no conflict when the intervals are disjoint: 1694 // NoConflict = (B.Start >= A.End) || (A.Start >= B.End) 1695 // 1696 // bound0 = (B.Start < A.End) 1697 // bound1 = (A.Start < B.End) 1698 // IsConflict = bound0 & bound1 1699 Value *Cmp0 = ChkBuilder.CreateICmpULT(Start0, End1, "bound0"); 1700 FirstInst = GetFirstInst(FirstInst, Cmp0, Loc); 1701 Value *Cmp1 = ChkBuilder.CreateICmpULT(Start1, End0, "bound1"); 1702 FirstInst = GetFirstInst(FirstInst, Cmp1, Loc); 1703 Value *IsConflict = ChkBuilder.CreateAnd(Cmp0, Cmp1, "found.conflict"); 1704 FirstInst = GetFirstInst(FirstInst, IsConflict, Loc); 1705 if (MemoryRuntimeCheck) { 1706 IsConflict = 1707 ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict, "conflict.rdx"); 1708 FirstInst = GetFirstInst(FirstInst, IsConflict, Loc); 1709 } 1710 MemoryRuntimeCheck = IsConflict; 1711 } 1712 1713 if (!MemoryRuntimeCheck) 1714 return std::make_pair(nullptr, nullptr); 1715 1716 // We have to do this trickery because the IRBuilder might fold the check to a 1717 // constant expression in which case there is no Instruction anchored in a 1718 // the block. 1719 Instruction *Check = 1720 BinaryOperator::CreateAnd(MemoryRuntimeCheck, ConstantInt::getTrue(Ctx)); 1721 ChkBuilder.Insert(Check, "memcheck.conflict"); 1722 FirstInst = GetFirstInst(FirstInst, Check, Loc); 1723 return std::make_pair(FirstInst, Check); 1724 } 1725