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