1 //===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===// 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 the LoopInfo class that is used to identify natural loops 10 // and determine the loop depth of various nodes of the CFG. Note that the 11 // loops identified may actually be several natural loops that share the same 12 // header node... not just a single natural loop. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #include "llvm/Analysis/LoopInfo.h" 17 #include "llvm/ADT/ScopeExit.h" 18 #include "llvm/ADT/SmallPtrSet.h" 19 #include "llvm/Analysis/IVDescriptors.h" 20 #include "llvm/Analysis/LoopInfoImpl.h" 21 #include "llvm/Analysis/LoopIterator.h" 22 #include "llvm/Analysis/LoopNestAnalysis.h" 23 #include "llvm/Analysis/MemorySSA.h" 24 #include "llvm/Analysis/MemorySSAUpdater.h" 25 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 26 #include "llvm/Analysis/ValueTracking.h" 27 #include "llvm/Config/llvm-config.h" 28 #include "llvm/IR/CFG.h" 29 #include "llvm/IR/Constants.h" 30 #include "llvm/IR/DebugLoc.h" 31 #include "llvm/IR/Dominators.h" 32 #include "llvm/IR/Instructions.h" 33 #include "llvm/IR/LLVMContext.h" 34 #include "llvm/IR/Metadata.h" 35 #include "llvm/IR/PassManager.h" 36 #include "llvm/IR/PrintPasses.h" 37 #include "llvm/InitializePasses.h" 38 #include "llvm/Support/CommandLine.h" 39 #include "llvm/Support/raw_ostream.h" 40 using namespace llvm; 41 42 // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops. 43 template class llvm::LoopBase<BasicBlock, Loop>; 44 template class llvm::LoopInfoBase<BasicBlock, Loop>; 45 46 // Always verify loopinfo if expensive checking is enabled. 47 #ifdef EXPENSIVE_CHECKS 48 bool llvm::VerifyLoopInfo = true; 49 #else 50 bool llvm::VerifyLoopInfo = false; 51 #endif 52 static cl::opt<bool, true> 53 VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), 54 cl::Hidden, cl::desc("Verify loop info (time consuming)")); 55 56 //===----------------------------------------------------------------------===// 57 // Loop implementation 58 // 59 60 bool Loop::isLoopInvariant(const Value *V) const { 61 if (const Instruction *I = dyn_cast<Instruction>(V)) 62 return !contains(I); 63 return true; // All non-instructions are loop invariant 64 } 65 66 bool Loop::hasLoopInvariantOperands(const Instruction *I) const { 67 return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); }); 68 } 69 70 bool Loop::makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt, 71 MemorySSAUpdater *MSSAU) const { 72 if (Instruction *I = dyn_cast<Instruction>(V)) 73 return makeLoopInvariant(I, Changed, InsertPt, MSSAU); 74 return true; // All non-instructions are loop-invariant. 75 } 76 77 bool Loop::makeLoopInvariant(Instruction *I, bool &Changed, 78 Instruction *InsertPt, 79 MemorySSAUpdater *MSSAU) const { 80 // Test if the value is already loop-invariant. 81 if (isLoopInvariant(I)) 82 return true; 83 if (!isSafeToSpeculativelyExecute(I)) 84 return false; 85 if (I->mayReadFromMemory()) 86 return false; 87 // EH block instructions are immobile. 88 if (I->isEHPad()) 89 return false; 90 // Determine the insertion point, unless one was given. 91 if (!InsertPt) { 92 BasicBlock *Preheader = getLoopPreheader(); 93 // Without a preheader, hoisting is not feasible. 94 if (!Preheader) 95 return false; 96 InsertPt = Preheader->getTerminator(); 97 } 98 // Don't hoist instructions with loop-variant operands. 99 for (Value *Operand : I->operands()) 100 if (!makeLoopInvariant(Operand, Changed, InsertPt, MSSAU)) 101 return false; 102 103 // Hoist. 104 I->moveBefore(InsertPt); 105 if (MSSAU) 106 if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(I)) 107 MSSAU->moveToPlace(MUD, InsertPt->getParent(), 108 MemorySSA::BeforeTerminator); 109 110 // There is possibility of hoisting this instruction above some arbitrary 111 // condition. Any metadata defined on it can be control dependent on this 112 // condition. Conservatively strip it here so that we don't give any wrong 113 // information to the optimizer. 114 I->dropUnknownNonDebugMetadata(); 115 116 Changed = true; 117 return true; 118 } 119 120 bool Loop::getIncomingAndBackEdge(BasicBlock *&Incoming, 121 BasicBlock *&Backedge) const { 122 BasicBlock *H = getHeader(); 123 124 Incoming = nullptr; 125 Backedge = nullptr; 126 pred_iterator PI = pred_begin(H); 127 assert(PI != pred_end(H) && "Loop must have at least one backedge!"); 128 Backedge = *PI++; 129 if (PI == pred_end(H)) 130 return false; // dead loop 131 Incoming = *PI++; 132 if (PI != pred_end(H)) 133 return false; // multiple backedges? 134 135 if (contains(Incoming)) { 136 if (contains(Backedge)) 137 return false; 138 std::swap(Incoming, Backedge); 139 } else if (!contains(Backedge)) 140 return false; 141 142 assert(Incoming && Backedge && "expected non-null incoming and backedges"); 143 return true; 144 } 145 146 PHINode *Loop::getCanonicalInductionVariable() const { 147 BasicBlock *H = getHeader(); 148 149 BasicBlock *Incoming = nullptr, *Backedge = nullptr; 150 if (!getIncomingAndBackEdge(Incoming, Backedge)) 151 return nullptr; 152 153 // Loop over all of the PHI nodes, looking for a canonical indvar. 154 for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) { 155 PHINode *PN = cast<PHINode>(I); 156 if (ConstantInt *CI = 157 dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming))) 158 if (CI->isZero()) 159 if (Instruction *Inc = 160 dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge))) 161 if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(0) == PN) 162 if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1))) 163 if (CI->isOne()) 164 return PN; 165 } 166 return nullptr; 167 } 168 169 /// Get the latch condition instruction. 170 ICmpInst *Loop::getLatchCmpInst() const { 171 if (BasicBlock *Latch = getLoopLatch()) 172 if (BranchInst *BI = dyn_cast_or_null<BranchInst>(Latch->getTerminator())) 173 if (BI->isConditional()) 174 return dyn_cast<ICmpInst>(BI->getCondition()); 175 176 return nullptr; 177 } 178 179 /// Return the final value of the loop induction variable if found. 180 static Value *findFinalIVValue(const Loop &L, const PHINode &IndVar, 181 const Instruction &StepInst) { 182 ICmpInst *LatchCmpInst = L.getLatchCmpInst(); 183 if (!LatchCmpInst) 184 return nullptr; 185 186 Value *Op0 = LatchCmpInst->getOperand(0); 187 Value *Op1 = LatchCmpInst->getOperand(1); 188 if (Op0 == &IndVar || Op0 == &StepInst) 189 return Op1; 190 191 if (Op1 == &IndVar || Op1 == &StepInst) 192 return Op0; 193 194 return nullptr; 195 } 196 197 Optional<Loop::LoopBounds> Loop::LoopBounds::getBounds(const Loop &L, 198 PHINode &IndVar, 199 ScalarEvolution &SE) { 200 InductionDescriptor IndDesc; 201 if (!InductionDescriptor::isInductionPHI(&IndVar, &L, &SE, IndDesc)) 202 return None; 203 204 Value *InitialIVValue = IndDesc.getStartValue(); 205 Instruction *StepInst = IndDesc.getInductionBinOp(); 206 if (!InitialIVValue || !StepInst) 207 return None; 208 209 const SCEV *Step = IndDesc.getStep(); 210 Value *StepInstOp1 = StepInst->getOperand(1); 211 Value *StepInstOp0 = StepInst->getOperand(0); 212 Value *StepValue = nullptr; 213 if (SE.getSCEV(StepInstOp1) == Step) 214 StepValue = StepInstOp1; 215 else if (SE.getSCEV(StepInstOp0) == Step) 216 StepValue = StepInstOp0; 217 218 Value *FinalIVValue = findFinalIVValue(L, IndVar, *StepInst); 219 if (!FinalIVValue) 220 return None; 221 222 return LoopBounds(L, *InitialIVValue, *StepInst, StepValue, *FinalIVValue, 223 SE); 224 } 225 226 using Direction = Loop::LoopBounds::Direction; 227 228 ICmpInst::Predicate Loop::LoopBounds::getCanonicalPredicate() const { 229 BasicBlock *Latch = L.getLoopLatch(); 230 assert(Latch && "Expecting valid latch"); 231 232 BranchInst *BI = dyn_cast_or_null<BranchInst>(Latch->getTerminator()); 233 assert(BI && BI->isConditional() && "Expecting conditional latch branch"); 234 235 ICmpInst *LatchCmpInst = dyn_cast<ICmpInst>(BI->getCondition()); 236 assert(LatchCmpInst && 237 "Expecting the latch compare instruction to be a CmpInst"); 238 239 // Need to inverse the predicate when first successor is not the loop 240 // header 241 ICmpInst::Predicate Pred = (BI->getSuccessor(0) == L.getHeader()) 242 ? LatchCmpInst->getPredicate() 243 : LatchCmpInst->getInversePredicate(); 244 245 if (LatchCmpInst->getOperand(0) == &getFinalIVValue()) 246 Pred = ICmpInst::getSwappedPredicate(Pred); 247 248 // Need to flip strictness of the predicate when the latch compare instruction 249 // is not using StepInst 250 if (LatchCmpInst->getOperand(0) == &getStepInst() || 251 LatchCmpInst->getOperand(1) == &getStepInst()) 252 return Pred; 253 254 // Cannot flip strictness of NE and EQ 255 if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ) 256 return ICmpInst::getFlippedStrictnessPredicate(Pred); 257 258 Direction D = getDirection(); 259 if (D == Direction::Increasing) 260 return ICmpInst::ICMP_SLT; 261 262 if (D == Direction::Decreasing) 263 return ICmpInst::ICMP_SGT; 264 265 // If cannot determine the direction, then unable to find the canonical 266 // predicate 267 return ICmpInst::BAD_ICMP_PREDICATE; 268 } 269 270 Direction Loop::LoopBounds::getDirection() const { 271 if (const SCEVAddRecExpr *StepAddRecExpr = 272 dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&getStepInst()))) 273 if (const SCEV *StepRecur = StepAddRecExpr->getStepRecurrence(SE)) { 274 if (SE.isKnownPositive(StepRecur)) 275 return Direction::Increasing; 276 if (SE.isKnownNegative(StepRecur)) 277 return Direction::Decreasing; 278 } 279 280 return Direction::Unknown; 281 } 282 283 Optional<Loop::LoopBounds> Loop::getBounds(ScalarEvolution &SE) const { 284 if (PHINode *IndVar = getInductionVariable(SE)) 285 return LoopBounds::getBounds(*this, *IndVar, SE); 286 287 return None; 288 } 289 290 PHINode *Loop::getInductionVariable(ScalarEvolution &SE) const { 291 if (!isLoopSimplifyForm()) 292 return nullptr; 293 294 BasicBlock *Header = getHeader(); 295 assert(Header && "Expected a valid loop header"); 296 ICmpInst *CmpInst = getLatchCmpInst(); 297 if (!CmpInst) 298 return nullptr; 299 300 Value *LatchCmpOp0 = CmpInst->getOperand(0); 301 Value *LatchCmpOp1 = CmpInst->getOperand(1); 302 303 for (PHINode &IndVar : Header->phis()) { 304 InductionDescriptor IndDesc; 305 if (!InductionDescriptor::isInductionPHI(&IndVar, this, &SE, IndDesc)) 306 continue; 307 308 BasicBlock *Latch = getLoopLatch(); 309 Value *StepInst = IndVar.getIncomingValueForBlock(Latch); 310 311 // case 1: 312 // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}] 313 // StepInst = IndVar + step 314 // cmp = StepInst < FinalValue 315 if (StepInst == LatchCmpOp0 || StepInst == LatchCmpOp1) 316 return &IndVar; 317 318 // case 2: 319 // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}] 320 // StepInst = IndVar + step 321 // cmp = IndVar < FinalValue 322 if (&IndVar == LatchCmpOp0 || &IndVar == LatchCmpOp1) 323 return &IndVar; 324 } 325 326 return nullptr; 327 } 328 329 bool Loop::getInductionDescriptor(ScalarEvolution &SE, 330 InductionDescriptor &IndDesc) const { 331 if (PHINode *IndVar = getInductionVariable(SE)) 332 return InductionDescriptor::isInductionPHI(IndVar, this, &SE, IndDesc); 333 334 return false; 335 } 336 337 bool Loop::isAuxiliaryInductionVariable(PHINode &AuxIndVar, 338 ScalarEvolution &SE) const { 339 // Located in the loop header 340 BasicBlock *Header = getHeader(); 341 if (AuxIndVar.getParent() != Header) 342 return false; 343 344 // No uses outside of the loop 345 for (User *U : AuxIndVar.users()) 346 if (const Instruction *I = dyn_cast<Instruction>(U)) 347 if (!contains(I)) 348 return false; 349 350 InductionDescriptor IndDesc; 351 if (!InductionDescriptor::isInductionPHI(&AuxIndVar, this, &SE, IndDesc)) 352 return false; 353 354 // The step instruction opcode should be add or sub. 355 if (IndDesc.getInductionOpcode() != Instruction::Add && 356 IndDesc.getInductionOpcode() != Instruction::Sub) 357 return false; 358 359 // Incremented by a loop invariant step for each loop iteration 360 return SE.isLoopInvariant(IndDesc.getStep(), this); 361 } 362 363 BranchInst *Loop::getLoopGuardBranch() const { 364 if (!isLoopSimplifyForm()) 365 return nullptr; 366 367 BasicBlock *Preheader = getLoopPreheader(); 368 assert(Preheader && getLoopLatch() && 369 "Expecting a loop with valid preheader and latch"); 370 371 // Loop should be in rotate form. 372 if (!isRotatedForm()) 373 return nullptr; 374 375 // Disallow loops with more than one unique exit block, as we do not verify 376 // that GuardOtherSucc post dominates all exit blocks. 377 BasicBlock *ExitFromLatch = getUniqueExitBlock(); 378 if (!ExitFromLatch) 379 return nullptr; 380 381 BasicBlock *GuardBB = Preheader->getUniquePredecessor(); 382 if (!GuardBB) 383 return nullptr; 384 385 assert(GuardBB->getTerminator() && "Expecting valid guard terminator"); 386 387 BranchInst *GuardBI = dyn_cast<BranchInst>(GuardBB->getTerminator()); 388 if (!GuardBI || GuardBI->isUnconditional()) 389 return nullptr; 390 391 BasicBlock *GuardOtherSucc = (GuardBI->getSuccessor(0) == Preheader) 392 ? GuardBI->getSuccessor(1) 393 : GuardBI->getSuccessor(0); 394 395 // Check if ExitFromLatch (or any BasicBlock which is an empty unique 396 // successor of ExitFromLatch) is equal to GuardOtherSucc. If 397 // skipEmptyBlockUntil returns GuardOtherSucc, then the guard branch for the 398 // loop is GuardBI (return GuardBI), otherwise return nullptr. 399 if (&LoopNest::skipEmptyBlockUntil(ExitFromLatch, GuardOtherSucc, 400 /*CheckUniquePred=*/true) == 401 GuardOtherSucc) 402 return GuardBI; 403 else 404 return nullptr; 405 } 406 407 bool Loop::isCanonical(ScalarEvolution &SE) const { 408 InductionDescriptor IndDesc; 409 if (!getInductionDescriptor(SE, IndDesc)) 410 return false; 411 412 ConstantInt *Init = dyn_cast_or_null<ConstantInt>(IndDesc.getStartValue()); 413 if (!Init || !Init->isZero()) 414 return false; 415 416 if (IndDesc.getInductionOpcode() != Instruction::Add) 417 return false; 418 419 ConstantInt *Step = IndDesc.getConstIntStepValue(); 420 if (!Step || !Step->isOne()) 421 return false; 422 423 return true; 424 } 425 426 // Check that 'BB' doesn't have any uses outside of the 'L' 427 static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB, 428 const DominatorTree &DT, bool IgnoreTokens) { 429 for (const Instruction &I : BB) { 430 // Tokens can't be used in PHI nodes and live-out tokens prevent loop 431 // optimizations, so for the purposes of considered LCSSA form, we 432 // can ignore them. 433 if (IgnoreTokens && I.getType()->isTokenTy()) 434 continue; 435 436 for (const Use &U : I.uses()) { 437 const Instruction *UI = cast<Instruction>(U.getUser()); 438 const BasicBlock *UserBB = UI->getParent(); 439 440 // For practical purposes, we consider that the use in a PHI 441 // occurs in the respective predecessor block. For more info, 442 // see the `phi` doc in LangRef and the LCSSA doc. 443 if (const PHINode *P = dyn_cast<PHINode>(UI)) 444 UserBB = P->getIncomingBlock(U); 445 446 // Check the current block, as a fast-path, before checking whether 447 // the use is anywhere in the loop. Most values are used in the same 448 // block they are defined in. Also, blocks not reachable from the 449 // entry are special; uses in them don't need to go through PHIs. 450 if (UserBB != &BB && !L.contains(UserBB) && 451 DT.isReachableFromEntry(UserBB)) 452 return false; 453 } 454 } 455 return true; 456 } 457 458 bool Loop::isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens) const { 459 // For each block we check that it doesn't have any uses outside of this loop. 460 return all_of(this->blocks(), [&](const BasicBlock *BB) { 461 return isBlockInLCSSAForm(*this, *BB, DT, IgnoreTokens); 462 }); 463 } 464 465 bool Loop::isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI, 466 bool IgnoreTokens) const { 467 // For each block we check that it doesn't have any uses outside of its 468 // innermost loop. This process will transitively guarantee that the current 469 // loop and all of the nested loops are in LCSSA form. 470 return all_of(this->blocks(), [&](const BasicBlock *BB) { 471 return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT, IgnoreTokens); 472 }); 473 } 474 475 bool Loop::isLoopSimplifyForm() const { 476 // Normal-form loops have a preheader, a single backedge, and all of their 477 // exits have all their predecessors inside the loop. 478 return getLoopPreheader() && getLoopLatch() && hasDedicatedExits(); 479 } 480 481 // Routines that reform the loop CFG and split edges often fail on indirectbr. 482 bool Loop::isSafeToClone() const { 483 // Return false if any loop blocks contain indirectbrs, or there are any calls 484 // to noduplicate functions. 485 for (BasicBlock *BB : this->blocks()) { 486 if (isa<IndirectBrInst>(BB->getTerminator())) 487 return false; 488 489 for (Instruction &I : *BB) 490 if (auto *CB = dyn_cast<CallBase>(&I)) 491 if (CB->cannotDuplicate()) 492 return false; 493 } 494 return true; 495 } 496 497 MDNode *Loop::getLoopID() const { 498 MDNode *LoopID = nullptr; 499 500 // Go through the latch blocks and check the terminator for the metadata. 501 SmallVector<BasicBlock *, 4> LatchesBlocks; 502 getLoopLatches(LatchesBlocks); 503 for (BasicBlock *BB : LatchesBlocks) { 504 Instruction *TI = BB->getTerminator(); 505 MDNode *MD = TI->getMetadata(LLVMContext::MD_loop); 506 507 if (!MD) 508 return nullptr; 509 510 if (!LoopID) 511 LoopID = MD; 512 else if (MD != LoopID) 513 return nullptr; 514 } 515 if (!LoopID || LoopID->getNumOperands() == 0 || 516 LoopID->getOperand(0) != LoopID) 517 return nullptr; 518 return LoopID; 519 } 520 521 void Loop::setLoopID(MDNode *LoopID) const { 522 assert((!LoopID || LoopID->getNumOperands() > 0) && 523 "Loop ID needs at least one operand"); 524 assert((!LoopID || LoopID->getOperand(0) == LoopID) && 525 "Loop ID should refer to itself"); 526 527 SmallVector<BasicBlock *, 4> LoopLatches; 528 getLoopLatches(LoopLatches); 529 for (BasicBlock *BB : LoopLatches) 530 BB->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID); 531 } 532 533 void Loop::setLoopAlreadyUnrolled() { 534 LLVMContext &Context = getHeader()->getContext(); 535 536 MDNode *DisableUnrollMD = 537 MDNode::get(Context, MDString::get(Context, "llvm.loop.unroll.disable")); 538 MDNode *LoopID = getLoopID(); 539 MDNode *NewLoopID = makePostTransformationMetadata( 540 Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD}); 541 setLoopID(NewLoopID); 542 } 543 544 void Loop::setLoopMustProgress() { 545 LLVMContext &Context = getHeader()->getContext(); 546 547 MDNode *MustProgress = findOptionMDForLoop(this, "llvm.loop.mustprogress"); 548 549 if (MustProgress) 550 return; 551 552 MDNode *MustProgressMD = 553 MDNode::get(Context, MDString::get(Context, "llvm.loop.mustprogress")); 554 MDNode *LoopID = getLoopID(); 555 MDNode *NewLoopID = 556 makePostTransformationMetadata(Context, LoopID, {}, {MustProgressMD}); 557 setLoopID(NewLoopID); 558 } 559 560 bool Loop::isAnnotatedParallel() const { 561 MDNode *DesiredLoopIdMetadata = getLoopID(); 562 563 if (!DesiredLoopIdMetadata) 564 return false; 565 566 MDNode *ParallelAccesses = 567 findOptionMDForLoop(this, "llvm.loop.parallel_accesses"); 568 SmallPtrSet<MDNode *, 4> 569 ParallelAccessGroups; // For scalable 'contains' check. 570 if (ParallelAccesses) { 571 for (const MDOperand &MD : drop_begin(ParallelAccesses->operands())) { 572 MDNode *AccGroup = cast<MDNode>(MD.get()); 573 assert(isValidAsAccessGroup(AccGroup) && 574 "List item must be an access group"); 575 ParallelAccessGroups.insert(AccGroup); 576 } 577 } 578 579 // The loop branch contains the parallel loop metadata. In order to ensure 580 // that any parallel-loop-unaware optimization pass hasn't added loop-carried 581 // dependencies (thus converted the loop back to a sequential loop), check 582 // that all the memory instructions in the loop belong to an access group that 583 // is parallel to this loop. 584 for (BasicBlock *BB : this->blocks()) { 585 for (Instruction &I : *BB) { 586 if (!I.mayReadOrWriteMemory()) 587 continue; 588 589 if (MDNode *AccessGroup = I.getMetadata(LLVMContext::MD_access_group)) { 590 auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool { 591 if (AG->getNumOperands() == 0) { 592 assert(isValidAsAccessGroup(AG) && "Item must be an access group"); 593 return ParallelAccessGroups.count(AG); 594 } 595 596 for (const MDOperand &AccessListItem : AG->operands()) { 597 MDNode *AccGroup = cast<MDNode>(AccessListItem.get()); 598 assert(isValidAsAccessGroup(AccGroup) && 599 "List item must be an access group"); 600 if (ParallelAccessGroups.count(AccGroup)) 601 return true; 602 } 603 return false; 604 }; 605 606 if (ContainsAccessGroup(AccessGroup)) 607 continue; 608 } 609 610 // The memory instruction can refer to the loop identifier metadata 611 // directly or indirectly through another list metadata (in case of 612 // nested parallel loops). The loop identifier metadata refers to 613 // itself so we can check both cases with the same routine. 614 MDNode *LoopIdMD = 615 I.getMetadata(LLVMContext::MD_mem_parallel_loop_access); 616 617 if (!LoopIdMD) 618 return false; 619 620 if (!llvm::is_contained(LoopIdMD->operands(), DesiredLoopIdMetadata)) 621 return false; 622 } 623 } 624 return true; 625 } 626 627 DebugLoc Loop::getStartLoc() const { return getLocRange().getStart(); } 628 629 Loop::LocRange Loop::getLocRange() const { 630 // If we have a debug location in the loop ID, then use it. 631 if (MDNode *LoopID = getLoopID()) { 632 DebugLoc Start; 633 // We use the first DebugLoc in the header as the start location of the loop 634 // and if there is a second DebugLoc in the header we use it as end location 635 // of the loop. 636 for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) { 637 if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) { 638 if (!Start) 639 Start = DebugLoc(L); 640 else 641 return LocRange(Start, DebugLoc(L)); 642 } 643 } 644 645 if (Start) 646 return LocRange(Start); 647 } 648 649 // Try the pre-header first. 650 if (BasicBlock *PHeadBB = getLoopPreheader()) 651 if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc()) 652 return LocRange(DL); 653 654 // If we have no pre-header or there are no instructions with debug 655 // info in it, try the header. 656 if (BasicBlock *HeadBB = getHeader()) 657 return LocRange(HeadBB->getTerminator()->getDebugLoc()); 658 659 return LocRange(); 660 } 661 662 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 663 LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); } 664 665 LLVM_DUMP_METHOD void Loop::dumpVerbose() const { 666 print(dbgs(), /*Verbose=*/true); 667 } 668 #endif 669 670 //===----------------------------------------------------------------------===// 671 // UnloopUpdater implementation 672 // 673 674 namespace { 675 /// Find the new parent loop for all blocks within the "unloop" whose last 676 /// backedges has just been removed. 677 class UnloopUpdater { 678 Loop &Unloop; 679 LoopInfo *LI; 680 681 LoopBlocksDFS DFS; 682 683 // Map unloop's immediate subloops to their nearest reachable parents. Nested 684 // loops within these subloops will not change parents. However, an immediate 685 // subloop's new parent will be the nearest loop reachable from either its own 686 // exits *or* any of its nested loop's exits. 687 DenseMap<Loop *, Loop *> SubloopParents; 688 689 // Flag the presence of an irreducible backedge whose destination is a block 690 // directly contained by the original unloop. 691 bool FoundIB = false; 692 693 public: 694 UnloopUpdater(Loop *UL, LoopInfo *LInfo) : Unloop(*UL), LI(LInfo), DFS(UL) {} 695 696 void updateBlockParents(); 697 698 void removeBlocksFromAncestors(); 699 700 void updateSubloopParents(); 701 702 protected: 703 Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop); 704 }; 705 } // end anonymous namespace 706 707 /// Update the parent loop for all blocks that are directly contained within the 708 /// original "unloop". 709 void UnloopUpdater::updateBlockParents() { 710 if (Unloop.getNumBlocks()) { 711 // Perform a post order CFG traversal of all blocks within this loop, 712 // propagating the nearest loop from successors to predecessors. 713 LoopBlocksTraversal Traversal(DFS, LI); 714 for (BasicBlock *POI : Traversal) { 715 716 Loop *L = LI->getLoopFor(POI); 717 Loop *NL = getNearestLoop(POI, L); 718 719 if (NL != L) { 720 // For reducible loops, NL is now an ancestor of Unloop. 721 assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) && 722 "uninitialized successor"); 723 LI->changeLoopFor(POI, NL); 724 } else { 725 // Or the current block is part of a subloop, in which case its parent 726 // is unchanged. 727 assert((FoundIB || Unloop.contains(L)) && "uninitialized successor"); 728 } 729 } 730 } 731 // Each irreducible loop within the unloop induces a round of iteration using 732 // the DFS result cached by Traversal. 733 bool Changed = FoundIB; 734 for (unsigned NIters = 0; Changed; ++NIters) { 735 assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm"); 736 (void) NIters; 737 738 // Iterate over the postorder list of blocks, propagating the nearest loop 739 // from successors to predecessors as before. 740 Changed = false; 741 for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(), 742 POE = DFS.endPostorder(); 743 POI != POE; ++POI) { 744 745 Loop *L = LI->getLoopFor(*POI); 746 Loop *NL = getNearestLoop(*POI, L); 747 if (NL != L) { 748 assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) && 749 "uninitialized successor"); 750 LI->changeLoopFor(*POI, NL); 751 Changed = true; 752 } 753 } 754 } 755 } 756 757 /// Remove unloop's blocks from all ancestors below their new parents. 758 void UnloopUpdater::removeBlocksFromAncestors() { 759 // Remove all unloop's blocks (including those in nested subloops) from 760 // ancestors below the new parent loop. 761 for (BasicBlock *BB : Unloop.blocks()) { 762 Loop *OuterParent = LI->getLoopFor(BB); 763 if (Unloop.contains(OuterParent)) { 764 while (OuterParent->getParentLoop() != &Unloop) 765 OuterParent = OuterParent->getParentLoop(); 766 OuterParent = SubloopParents[OuterParent]; 767 } 768 // Remove blocks from former Ancestors except Unloop itself which will be 769 // deleted. 770 for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent; 771 OldParent = OldParent->getParentLoop()) { 772 assert(OldParent && "new loop is not an ancestor of the original"); 773 OldParent->removeBlockFromLoop(BB); 774 } 775 } 776 } 777 778 /// Update the parent loop for all subloops directly nested within unloop. 779 void UnloopUpdater::updateSubloopParents() { 780 while (!Unloop.isInnermost()) { 781 Loop *Subloop = *std::prev(Unloop.end()); 782 Unloop.removeChildLoop(std::prev(Unloop.end())); 783 784 assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop"); 785 if (Loop *Parent = SubloopParents[Subloop]) 786 Parent->addChildLoop(Subloop); 787 else 788 LI->addTopLevelLoop(Subloop); 789 } 790 } 791 792 /// Return the nearest parent loop among this block's successors. If a successor 793 /// is a subloop header, consider its parent to be the nearest parent of the 794 /// subloop's exits. 795 /// 796 /// For subloop blocks, simply update SubloopParents and return NULL. 797 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) { 798 799 // Initially for blocks directly contained by Unloop, NearLoop == Unloop and 800 // is considered uninitialized. 801 Loop *NearLoop = BBLoop; 802 803 Loop *Subloop = nullptr; 804 if (NearLoop != &Unloop && Unloop.contains(NearLoop)) { 805 Subloop = NearLoop; 806 // Find the subloop ancestor that is directly contained within Unloop. 807 while (Subloop->getParentLoop() != &Unloop) { 808 Subloop = Subloop->getParentLoop(); 809 assert(Subloop && "subloop is not an ancestor of the original loop"); 810 } 811 // Get the current nearest parent of the Subloop exits, initially Unloop. 812 NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second; 813 } 814 815 succ_iterator I = succ_begin(BB), E = succ_end(BB); 816 if (I == E) { 817 assert(!Subloop && "subloop blocks must have a successor"); 818 NearLoop = nullptr; // unloop blocks may now exit the function. 819 } 820 for (; I != E; ++I) { 821 if (*I == BB) 822 continue; // self loops are uninteresting 823 824 Loop *L = LI->getLoopFor(*I); 825 if (L == &Unloop) { 826 // This successor has not been processed. This path must lead to an 827 // irreducible backedge. 828 assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB"); 829 FoundIB = true; 830 } 831 if (L != &Unloop && Unloop.contains(L)) { 832 // Successor is in a subloop. 833 if (Subloop) 834 continue; // Branching within subloops. Ignore it. 835 836 // BB branches from the original into a subloop header. 837 assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops"); 838 839 // Get the current nearest parent of the Subloop's exits. 840 L = SubloopParents[L]; 841 // L could be Unloop if the only exit was an irreducible backedge. 842 } 843 if (L == &Unloop) { 844 continue; 845 } 846 // Handle critical edges from Unloop into a sibling loop. 847 if (L && !L->contains(&Unloop)) { 848 L = L->getParentLoop(); 849 } 850 // Remember the nearest parent loop among successors or subloop exits. 851 if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L)) 852 NearLoop = L; 853 } 854 if (Subloop) { 855 SubloopParents[Subloop] = NearLoop; 856 return BBLoop; 857 } 858 return NearLoop; 859 } 860 861 LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); } 862 863 bool LoopInfo::invalidate(Function &F, const PreservedAnalyses &PA, 864 FunctionAnalysisManager::Invalidator &) { 865 // Check whether the analysis, all analyses on functions, or the function's 866 // CFG have been preserved. 867 auto PAC = PA.getChecker<LoopAnalysis>(); 868 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() || 869 PAC.preservedSet<CFGAnalyses>()); 870 } 871 872 void LoopInfo::erase(Loop *Unloop) { 873 assert(!Unloop->isInvalid() && "Loop has already been erased!"); 874 875 auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); }); 876 877 // First handle the special case of no parent loop to simplify the algorithm. 878 if (Unloop->isOutermost()) { 879 // Since BBLoop had no parent, Unloop blocks are no longer in a loop. 880 for (BasicBlock *BB : Unloop->blocks()) { 881 // Don't reparent blocks in subloops. 882 if (getLoopFor(BB) != Unloop) 883 continue; 884 885 // Blocks no longer have a parent but are still referenced by Unloop until 886 // the Unloop object is deleted. 887 changeLoopFor(BB, nullptr); 888 } 889 890 // Remove the loop from the top-level LoopInfo object. 891 for (iterator I = begin();; ++I) { 892 assert(I != end() && "Couldn't find loop"); 893 if (*I == Unloop) { 894 removeLoop(I); 895 break; 896 } 897 } 898 899 // Move all of the subloops to the top-level. 900 while (!Unloop->isInnermost()) 901 addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end()))); 902 903 return; 904 } 905 906 // Update the parent loop for all blocks within the loop. Blocks within 907 // subloops will not change parents. 908 UnloopUpdater Updater(Unloop, this); 909 Updater.updateBlockParents(); 910 911 // Remove blocks from former ancestor loops. 912 Updater.removeBlocksFromAncestors(); 913 914 // Add direct subloops as children in their new parent loop. 915 Updater.updateSubloopParents(); 916 917 // Remove unloop from its parent loop. 918 Loop *ParentLoop = Unloop->getParentLoop(); 919 for (Loop::iterator I = ParentLoop->begin();; ++I) { 920 assert(I != ParentLoop->end() && "Couldn't find loop"); 921 if (*I == Unloop) { 922 ParentLoop->removeChildLoop(I); 923 break; 924 } 925 } 926 } 927 928 bool 929 LoopInfo::wouldBeOutOfLoopUseRequiringLCSSA(const Value *V, 930 const BasicBlock *ExitBB) const { 931 if (V->getType()->isTokenTy()) 932 // We can't form PHIs of token type, so the definition of LCSSA excludes 933 // values of that type. 934 return false; 935 936 const Instruction *I = dyn_cast<Instruction>(V); 937 if (!I) 938 return false; 939 const Loop *L = getLoopFor(I->getParent()); 940 if (!L) 941 return false; 942 if (L->contains(ExitBB)) 943 // Could be an exit bb of a subloop and contained in defining loop 944 return false; 945 946 // We found a (new) out-of-loop use location, for a value defined in-loop. 947 // (Note that because of LCSSA, we don't have to account for values defined 948 // in sibling loops. Such values will have LCSSA phis of their own in the 949 // common parent loop.) 950 return true; 951 } 952 953 AnalysisKey LoopAnalysis::Key; 954 955 LoopInfo LoopAnalysis::run(Function &F, FunctionAnalysisManager &AM) { 956 // FIXME: Currently we create a LoopInfo from scratch for every function. 957 // This may prove to be too wasteful due to deallocating and re-allocating 958 // memory each time for the underlying map and vector datastructures. At some 959 // point it may prove worthwhile to use a freelist and recycle LoopInfo 960 // objects. I don't want to add that kind of complexity until the scope of 961 // the problem is better understood. 962 LoopInfo LI; 963 LI.analyze(AM.getResult<DominatorTreeAnalysis>(F)); 964 return LI; 965 } 966 967 PreservedAnalyses LoopPrinterPass::run(Function &F, 968 FunctionAnalysisManager &AM) { 969 AM.getResult<LoopAnalysis>(F).print(OS); 970 return PreservedAnalyses::all(); 971 } 972 973 void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) { 974 975 if (forcePrintModuleIR()) { 976 // handling -print-module-scope 977 OS << Banner << " (loop: "; 978 L.getHeader()->printAsOperand(OS, false); 979 OS << ")\n"; 980 981 // printing whole module 982 OS << *L.getHeader()->getModule(); 983 return; 984 } 985 986 OS << Banner; 987 988 auto *PreHeader = L.getLoopPreheader(); 989 if (PreHeader) { 990 OS << "\n; Preheader:"; 991 PreHeader->print(OS); 992 OS << "\n; Loop:"; 993 } 994 995 for (auto *Block : L.blocks()) 996 if (Block) 997 Block->print(OS); 998 else 999 OS << "Printing <null> block"; 1000 1001 SmallVector<BasicBlock *, 8> ExitBlocks; 1002 L.getExitBlocks(ExitBlocks); 1003 if (!ExitBlocks.empty()) { 1004 OS << "\n; Exit blocks"; 1005 for (auto *Block : ExitBlocks) 1006 if (Block) 1007 Block->print(OS); 1008 else 1009 OS << "Printing <null> block"; 1010 } 1011 } 1012 1013 MDNode *llvm::findOptionMDForLoopID(MDNode *LoopID, StringRef Name) { 1014 // No loop metadata node, no loop properties. 1015 if (!LoopID) 1016 return nullptr; 1017 1018 // First operand should refer to the metadata node itself, for legacy reasons. 1019 assert(LoopID->getNumOperands() > 0 && "requires at least one operand"); 1020 assert(LoopID->getOperand(0) == LoopID && "invalid loop id"); 1021 1022 // Iterate over the metdata node operands and look for MDString metadata. 1023 for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) { 1024 MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i)); 1025 if (!MD || MD->getNumOperands() < 1) 1026 continue; 1027 MDString *S = dyn_cast<MDString>(MD->getOperand(0)); 1028 if (!S) 1029 continue; 1030 // Return the operand node if MDString holds expected metadata. 1031 if (Name.equals(S->getString())) 1032 return MD; 1033 } 1034 1035 // Loop property not found. 1036 return nullptr; 1037 } 1038 1039 MDNode *llvm::findOptionMDForLoop(const Loop *TheLoop, StringRef Name) { 1040 return findOptionMDForLoopID(TheLoop->getLoopID(), Name); 1041 } 1042 1043 /// Find string metadata for loop 1044 /// 1045 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an 1046 /// operand or null otherwise. If the string metadata is not found return 1047 /// Optional's not-a-value. 1048 Optional<const MDOperand *> llvm::findStringMetadataForLoop(const Loop *TheLoop, 1049 StringRef Name) { 1050 MDNode *MD = findOptionMDForLoop(TheLoop, Name); 1051 if (!MD) 1052 return None; 1053 switch (MD->getNumOperands()) { 1054 case 1: 1055 return nullptr; 1056 case 2: 1057 return &MD->getOperand(1); 1058 default: 1059 llvm_unreachable("loop metadata has 0 or 1 operand"); 1060 } 1061 } 1062 1063 Optional<bool> llvm::getOptionalBoolLoopAttribute(const Loop *TheLoop, 1064 StringRef Name) { 1065 MDNode *MD = findOptionMDForLoop(TheLoop, Name); 1066 if (!MD) 1067 return None; 1068 switch (MD->getNumOperands()) { 1069 case 1: 1070 // When the value is absent it is interpreted as 'attribute set'. 1071 return true; 1072 case 2: 1073 if (ConstantInt *IntMD = 1074 mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get())) 1075 return IntMD->getZExtValue(); 1076 return true; 1077 } 1078 llvm_unreachable("unexpected number of options"); 1079 } 1080 1081 bool llvm::getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name) { 1082 return getOptionalBoolLoopAttribute(TheLoop, Name).value_or(false); 1083 } 1084 1085 llvm::Optional<int> llvm::getOptionalIntLoopAttribute(const Loop *TheLoop, 1086 StringRef Name) { 1087 const MDOperand *AttrMD = 1088 findStringMetadataForLoop(TheLoop, Name).value_or(nullptr); 1089 if (!AttrMD) 1090 return None; 1091 1092 ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get()); 1093 if (!IntMD) 1094 return None; 1095 1096 return IntMD->getSExtValue(); 1097 } 1098 1099 int llvm::getIntLoopAttribute(const Loop *TheLoop, StringRef Name, 1100 int Default) { 1101 return getOptionalIntLoopAttribute(TheLoop, Name).value_or(Default); 1102 } 1103 1104 bool llvm::isFinite(const Loop *L) { 1105 return L->getHeader()->getParent()->willReturn(); 1106 } 1107 1108 static const char *LLVMLoopMustProgress = "llvm.loop.mustprogress"; 1109 1110 bool llvm::hasMustProgress(const Loop *L) { 1111 return getBooleanLoopAttribute(L, LLVMLoopMustProgress); 1112 } 1113 1114 bool llvm::isMustProgress(const Loop *L) { 1115 return L->getHeader()->getParent()->mustProgress() || hasMustProgress(L); 1116 } 1117 1118 bool llvm::isValidAsAccessGroup(MDNode *Node) { 1119 return Node->getNumOperands() == 0 && Node->isDistinct(); 1120 } 1121 1122 MDNode *llvm::makePostTransformationMetadata(LLVMContext &Context, 1123 MDNode *OrigLoopID, 1124 ArrayRef<StringRef> RemovePrefixes, 1125 ArrayRef<MDNode *> AddAttrs) { 1126 // First remove any existing loop metadata related to this transformation. 1127 SmallVector<Metadata *, 4> MDs; 1128 1129 // Reserve first location for self reference to the LoopID metadata node. 1130 MDs.push_back(nullptr); 1131 1132 // Remove metadata for the transformation that has been applied or that became 1133 // outdated. 1134 if (OrigLoopID) { 1135 for (unsigned i = 1, ie = OrigLoopID->getNumOperands(); i < ie; ++i) { 1136 bool IsVectorMetadata = false; 1137 Metadata *Op = OrigLoopID->getOperand(i); 1138 if (MDNode *MD = dyn_cast<MDNode>(Op)) { 1139 const MDString *S = dyn_cast<MDString>(MD->getOperand(0)); 1140 if (S) 1141 IsVectorMetadata = 1142 llvm::any_of(RemovePrefixes, [S](StringRef Prefix) -> bool { 1143 return S->getString().startswith(Prefix); 1144 }); 1145 } 1146 if (!IsVectorMetadata) 1147 MDs.push_back(Op); 1148 } 1149 } 1150 1151 // Add metadata to avoid reapplying a transformation, such as 1152 // llvm.loop.unroll.disable and llvm.loop.isvectorized. 1153 MDs.append(AddAttrs.begin(), AddAttrs.end()); 1154 1155 MDNode *NewLoopID = MDNode::getDistinct(Context, MDs); 1156 // Replace the temporary node with a self-reference. 1157 NewLoopID->replaceOperandWith(0, NewLoopID); 1158 return NewLoopID; 1159 } 1160 1161 //===----------------------------------------------------------------------===// 1162 // LoopInfo implementation 1163 // 1164 1165 LoopInfoWrapperPass::LoopInfoWrapperPass() : FunctionPass(ID) { 1166 initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry()); 1167 } 1168 1169 char LoopInfoWrapperPass::ID = 0; 1170 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information", 1171 true, true) 1172 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 1173 INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information", 1174 true, true) 1175 1176 bool LoopInfoWrapperPass::runOnFunction(Function &) { 1177 releaseMemory(); 1178 LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree()); 1179 return false; 1180 } 1181 1182 void LoopInfoWrapperPass::verifyAnalysis() const { 1183 // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the 1184 // function each time verifyAnalysis is called is very expensive. The 1185 // -verify-loop-info option can enable this. In order to perform some 1186 // checking by default, LoopPass has been taught to call verifyLoop manually 1187 // during loop pass sequences. 1188 if (VerifyLoopInfo) { 1189 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 1190 LI.verify(DT); 1191 } 1192 } 1193 1194 void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 1195 AU.setPreservesAll(); 1196 AU.addRequiredTransitive<DominatorTreeWrapperPass>(); 1197 } 1198 1199 void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const { 1200 LI.print(OS); 1201 } 1202 1203 PreservedAnalyses LoopVerifierPass::run(Function &F, 1204 FunctionAnalysisManager &AM) { 1205 LoopInfo &LI = AM.getResult<LoopAnalysis>(F); 1206 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 1207 LI.verify(DT); 1208 return PreservedAnalyses::all(); 1209 } 1210 1211 //===----------------------------------------------------------------------===// 1212 // LoopBlocksDFS implementation 1213 // 1214 1215 /// Traverse the loop blocks and store the DFS result. 1216 /// Useful for clients that just want the final DFS result and don't need to 1217 /// visit blocks during the initial traversal. 1218 void LoopBlocksDFS::perform(LoopInfo *LI) { 1219 LoopBlocksTraversal Traversal(*this, LI); 1220 for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(), 1221 POE = Traversal.end(); 1222 POI != POE; ++POI) 1223 ; 1224 } 1225