109467b48Spatrick //===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
209467b48Spatrick //
309467b48Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
409467b48Spatrick // See https://llvm.org/LICENSE.txt for license information.
509467b48Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
609467b48Spatrick //
709467b48Spatrick //===----------------------------------------------------------------------===//
809467b48Spatrick //
909467b48Spatrick // This file defines the LoopInfo class that is used to identify natural loops
1009467b48Spatrick // and determine the loop depth of various nodes of the CFG. Note that the
1109467b48Spatrick // loops identified may actually be several natural loops that share the same
1209467b48Spatrick // header node... not just a single natural loop.
1309467b48Spatrick //
1409467b48Spatrick //===----------------------------------------------------------------------===//
1509467b48Spatrick
1609467b48Spatrick #include "llvm/Analysis/LoopInfo.h"
1709467b48Spatrick #include "llvm/ADT/ScopeExit.h"
1809467b48Spatrick #include "llvm/ADT/SmallPtrSet.h"
1909467b48Spatrick #include "llvm/Analysis/IVDescriptors.h"
2009467b48Spatrick #include "llvm/Analysis/LoopInfoImpl.h"
2109467b48Spatrick #include "llvm/Analysis/LoopIterator.h"
2273471bf0Spatrick #include "llvm/Analysis/LoopNestAnalysis.h"
2309467b48Spatrick #include "llvm/Analysis/MemorySSA.h"
2409467b48Spatrick #include "llvm/Analysis/MemorySSAUpdater.h"
2509467b48Spatrick #include "llvm/Analysis/ScalarEvolutionExpressions.h"
2609467b48Spatrick #include "llvm/Analysis/ValueTracking.h"
2709467b48Spatrick #include "llvm/Config/llvm-config.h"
2809467b48Spatrick #include "llvm/IR/CFG.h"
2909467b48Spatrick #include "llvm/IR/Constants.h"
3009467b48Spatrick #include "llvm/IR/DebugLoc.h"
3109467b48Spatrick #include "llvm/IR/Dominators.h"
3209467b48Spatrick #include "llvm/IR/Instructions.h"
3309467b48Spatrick #include "llvm/IR/LLVMContext.h"
3409467b48Spatrick #include "llvm/IR/Metadata.h"
3509467b48Spatrick #include "llvm/IR/PassManager.h"
3673471bf0Spatrick #include "llvm/IR/PrintPasses.h"
3709467b48Spatrick #include "llvm/InitializePasses.h"
3809467b48Spatrick #include "llvm/Support/CommandLine.h"
3909467b48Spatrick #include "llvm/Support/raw_ostream.h"
4009467b48Spatrick using namespace llvm;
4109467b48Spatrick
4209467b48Spatrick // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
4309467b48Spatrick template class llvm::LoopBase<BasicBlock, Loop>;
4409467b48Spatrick template class llvm::LoopInfoBase<BasicBlock, Loop>;
4509467b48Spatrick
4609467b48Spatrick // Always verify loopinfo if expensive checking is enabled.
4709467b48Spatrick #ifdef EXPENSIVE_CHECKS
4809467b48Spatrick bool llvm::VerifyLoopInfo = true;
4909467b48Spatrick #else
5009467b48Spatrick bool llvm::VerifyLoopInfo = false;
5109467b48Spatrick #endif
5209467b48Spatrick static cl::opt<bool, true>
5309467b48Spatrick VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
5409467b48Spatrick cl::Hidden, cl::desc("Verify loop info (time consuming)"));
5509467b48Spatrick
5609467b48Spatrick //===----------------------------------------------------------------------===//
5709467b48Spatrick // Loop implementation
5809467b48Spatrick //
5909467b48Spatrick
isLoopInvariant(const Value * V) const6009467b48Spatrick bool Loop::isLoopInvariant(const Value *V) const {
6109467b48Spatrick if (const Instruction *I = dyn_cast<Instruction>(V))
6209467b48Spatrick return !contains(I);
6309467b48Spatrick return true; // All non-instructions are loop invariant
6409467b48Spatrick }
6509467b48Spatrick
hasLoopInvariantOperands(const Instruction * I) const6609467b48Spatrick bool Loop::hasLoopInvariantOperands(const Instruction *I) const {
6709467b48Spatrick return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
6809467b48Spatrick }
6909467b48Spatrick
makeLoopInvariant(Value * V,bool & Changed,Instruction * InsertPt,MemorySSAUpdater * MSSAU,ScalarEvolution * SE) const7009467b48Spatrick bool Loop::makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt,
71*d415bd75Srobert MemorySSAUpdater *MSSAU,
72*d415bd75Srobert ScalarEvolution *SE) const {
7309467b48Spatrick if (Instruction *I = dyn_cast<Instruction>(V))
74*d415bd75Srobert return makeLoopInvariant(I, Changed, InsertPt, MSSAU, SE);
7509467b48Spatrick return true; // All non-instructions are loop-invariant.
7609467b48Spatrick }
7709467b48Spatrick
makeLoopInvariant(Instruction * I,bool & Changed,Instruction * InsertPt,MemorySSAUpdater * MSSAU,ScalarEvolution * SE) const7809467b48Spatrick bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
79*d415bd75Srobert Instruction *InsertPt, MemorySSAUpdater *MSSAU,
80*d415bd75Srobert ScalarEvolution *SE) const {
8109467b48Spatrick // Test if the value is already loop-invariant.
8209467b48Spatrick if (isLoopInvariant(I))
8309467b48Spatrick return true;
8409467b48Spatrick if (!isSafeToSpeculativelyExecute(I))
8509467b48Spatrick return false;
8609467b48Spatrick if (I->mayReadFromMemory())
8709467b48Spatrick return false;
8809467b48Spatrick // EH block instructions are immobile.
8909467b48Spatrick if (I->isEHPad())
9009467b48Spatrick return false;
9109467b48Spatrick // Determine the insertion point, unless one was given.
9209467b48Spatrick if (!InsertPt) {
9309467b48Spatrick BasicBlock *Preheader = getLoopPreheader();
9409467b48Spatrick // Without a preheader, hoisting is not feasible.
9509467b48Spatrick if (!Preheader)
9609467b48Spatrick return false;
9709467b48Spatrick InsertPt = Preheader->getTerminator();
9809467b48Spatrick }
9909467b48Spatrick // Don't hoist instructions with loop-variant operands.
10009467b48Spatrick for (Value *Operand : I->operands())
101*d415bd75Srobert if (!makeLoopInvariant(Operand, Changed, InsertPt, MSSAU, SE))
10209467b48Spatrick return false;
10309467b48Spatrick
10409467b48Spatrick // Hoist.
10509467b48Spatrick I->moveBefore(InsertPt);
10609467b48Spatrick if (MSSAU)
10709467b48Spatrick if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(I))
10809467b48Spatrick MSSAU->moveToPlace(MUD, InsertPt->getParent(),
10909467b48Spatrick MemorySSA::BeforeTerminator);
11009467b48Spatrick
11109467b48Spatrick // There is possibility of hoisting this instruction above some arbitrary
11209467b48Spatrick // condition. Any metadata defined on it can be control dependent on this
11309467b48Spatrick // condition. Conservatively strip it here so that we don't give any wrong
11409467b48Spatrick // information to the optimizer.
11509467b48Spatrick I->dropUnknownNonDebugMetadata();
11609467b48Spatrick
117*d415bd75Srobert if (SE)
118*d415bd75Srobert SE->forgetBlockAndLoopDispositions(I);
119*d415bd75Srobert
12009467b48Spatrick Changed = true;
12109467b48Spatrick return true;
12209467b48Spatrick }
12309467b48Spatrick
getIncomingAndBackEdge(BasicBlock * & Incoming,BasicBlock * & Backedge) const12409467b48Spatrick bool Loop::getIncomingAndBackEdge(BasicBlock *&Incoming,
12509467b48Spatrick BasicBlock *&Backedge) const {
12609467b48Spatrick BasicBlock *H = getHeader();
12709467b48Spatrick
12809467b48Spatrick Incoming = nullptr;
12909467b48Spatrick Backedge = nullptr;
13009467b48Spatrick pred_iterator PI = pred_begin(H);
13109467b48Spatrick assert(PI != pred_end(H) && "Loop must have at least one backedge!");
13209467b48Spatrick Backedge = *PI++;
13309467b48Spatrick if (PI == pred_end(H))
13409467b48Spatrick return false; // dead loop
13509467b48Spatrick Incoming = *PI++;
13609467b48Spatrick if (PI != pred_end(H))
13709467b48Spatrick return false; // multiple backedges?
13809467b48Spatrick
13909467b48Spatrick if (contains(Incoming)) {
14009467b48Spatrick if (contains(Backedge))
14109467b48Spatrick return false;
14209467b48Spatrick std::swap(Incoming, Backedge);
14309467b48Spatrick } else if (!contains(Backedge))
14409467b48Spatrick return false;
14509467b48Spatrick
14609467b48Spatrick assert(Incoming && Backedge && "expected non-null incoming and backedges");
14709467b48Spatrick return true;
14809467b48Spatrick }
14909467b48Spatrick
getCanonicalInductionVariable() const15009467b48Spatrick PHINode *Loop::getCanonicalInductionVariable() const {
15109467b48Spatrick BasicBlock *H = getHeader();
15209467b48Spatrick
15309467b48Spatrick BasicBlock *Incoming = nullptr, *Backedge = nullptr;
15409467b48Spatrick if (!getIncomingAndBackEdge(Incoming, Backedge))
15509467b48Spatrick return nullptr;
15609467b48Spatrick
15709467b48Spatrick // Loop over all of the PHI nodes, looking for a canonical indvar.
15809467b48Spatrick for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) {
15909467b48Spatrick PHINode *PN = cast<PHINode>(I);
16009467b48Spatrick if (ConstantInt *CI =
16109467b48Spatrick dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming)))
16209467b48Spatrick if (CI->isZero())
16309467b48Spatrick if (Instruction *Inc =
16409467b48Spatrick dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
16509467b48Spatrick if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(0) == PN)
16609467b48Spatrick if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
16709467b48Spatrick if (CI->isOne())
16809467b48Spatrick return PN;
16909467b48Spatrick }
17009467b48Spatrick return nullptr;
17109467b48Spatrick }
17209467b48Spatrick
17309467b48Spatrick /// Get the latch condition instruction.
getLatchCmpInst() const17473471bf0Spatrick ICmpInst *Loop::getLatchCmpInst() const {
17573471bf0Spatrick if (BasicBlock *Latch = getLoopLatch())
17609467b48Spatrick if (BranchInst *BI = dyn_cast_or_null<BranchInst>(Latch->getTerminator()))
17709467b48Spatrick if (BI->isConditional())
17809467b48Spatrick return dyn_cast<ICmpInst>(BI->getCondition());
17909467b48Spatrick
18009467b48Spatrick return nullptr;
18109467b48Spatrick }
18209467b48Spatrick
18309467b48Spatrick /// Return the final value of the loop induction variable if found.
findFinalIVValue(const Loop & L,const PHINode & IndVar,const Instruction & StepInst)18409467b48Spatrick static Value *findFinalIVValue(const Loop &L, const PHINode &IndVar,
18509467b48Spatrick const Instruction &StepInst) {
18673471bf0Spatrick ICmpInst *LatchCmpInst = L.getLatchCmpInst();
18709467b48Spatrick if (!LatchCmpInst)
18809467b48Spatrick return nullptr;
18909467b48Spatrick
19009467b48Spatrick Value *Op0 = LatchCmpInst->getOperand(0);
19109467b48Spatrick Value *Op1 = LatchCmpInst->getOperand(1);
19209467b48Spatrick if (Op0 == &IndVar || Op0 == &StepInst)
19309467b48Spatrick return Op1;
19409467b48Spatrick
19509467b48Spatrick if (Op1 == &IndVar || Op1 == &StepInst)
19609467b48Spatrick return Op0;
19709467b48Spatrick
19809467b48Spatrick return nullptr;
19909467b48Spatrick }
20009467b48Spatrick
201*d415bd75Srobert std::optional<Loop::LoopBounds>
getBounds(const Loop & L,PHINode & IndVar,ScalarEvolution & SE)202*d415bd75Srobert Loop::LoopBounds::getBounds(const Loop &L, PHINode &IndVar,
20309467b48Spatrick ScalarEvolution &SE) {
20409467b48Spatrick InductionDescriptor IndDesc;
20509467b48Spatrick if (!InductionDescriptor::isInductionPHI(&IndVar, &L, &SE, IndDesc))
206*d415bd75Srobert return std::nullopt;
20709467b48Spatrick
20809467b48Spatrick Value *InitialIVValue = IndDesc.getStartValue();
20909467b48Spatrick Instruction *StepInst = IndDesc.getInductionBinOp();
21009467b48Spatrick if (!InitialIVValue || !StepInst)
211*d415bd75Srobert return std::nullopt;
21209467b48Spatrick
21309467b48Spatrick const SCEV *Step = IndDesc.getStep();
21409467b48Spatrick Value *StepInstOp1 = StepInst->getOperand(1);
21509467b48Spatrick Value *StepInstOp0 = StepInst->getOperand(0);
21609467b48Spatrick Value *StepValue = nullptr;
21709467b48Spatrick if (SE.getSCEV(StepInstOp1) == Step)
21809467b48Spatrick StepValue = StepInstOp1;
21909467b48Spatrick else if (SE.getSCEV(StepInstOp0) == Step)
22009467b48Spatrick StepValue = StepInstOp0;
22109467b48Spatrick
22209467b48Spatrick Value *FinalIVValue = findFinalIVValue(L, IndVar, *StepInst);
22309467b48Spatrick if (!FinalIVValue)
224*d415bd75Srobert return std::nullopt;
22509467b48Spatrick
22609467b48Spatrick return LoopBounds(L, *InitialIVValue, *StepInst, StepValue, *FinalIVValue,
22709467b48Spatrick SE);
22809467b48Spatrick }
22909467b48Spatrick
23009467b48Spatrick using Direction = Loop::LoopBounds::Direction;
23109467b48Spatrick
getCanonicalPredicate() const23209467b48Spatrick ICmpInst::Predicate Loop::LoopBounds::getCanonicalPredicate() const {
23309467b48Spatrick BasicBlock *Latch = L.getLoopLatch();
23409467b48Spatrick assert(Latch && "Expecting valid latch");
23509467b48Spatrick
23609467b48Spatrick BranchInst *BI = dyn_cast_or_null<BranchInst>(Latch->getTerminator());
23709467b48Spatrick assert(BI && BI->isConditional() && "Expecting conditional latch branch");
23809467b48Spatrick
23909467b48Spatrick ICmpInst *LatchCmpInst = dyn_cast<ICmpInst>(BI->getCondition());
24009467b48Spatrick assert(LatchCmpInst &&
24109467b48Spatrick "Expecting the latch compare instruction to be a CmpInst");
24209467b48Spatrick
24309467b48Spatrick // Need to inverse the predicate when first successor is not the loop
24409467b48Spatrick // header
24509467b48Spatrick ICmpInst::Predicate Pred = (BI->getSuccessor(0) == L.getHeader())
24609467b48Spatrick ? LatchCmpInst->getPredicate()
24709467b48Spatrick : LatchCmpInst->getInversePredicate();
24809467b48Spatrick
24909467b48Spatrick if (LatchCmpInst->getOperand(0) == &getFinalIVValue())
25009467b48Spatrick Pred = ICmpInst::getSwappedPredicate(Pred);
25109467b48Spatrick
25209467b48Spatrick // Need to flip strictness of the predicate when the latch compare instruction
25309467b48Spatrick // is not using StepInst
25409467b48Spatrick if (LatchCmpInst->getOperand(0) == &getStepInst() ||
25509467b48Spatrick LatchCmpInst->getOperand(1) == &getStepInst())
25609467b48Spatrick return Pred;
25709467b48Spatrick
25809467b48Spatrick // Cannot flip strictness of NE and EQ
25909467b48Spatrick if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ)
26009467b48Spatrick return ICmpInst::getFlippedStrictnessPredicate(Pred);
26109467b48Spatrick
26209467b48Spatrick Direction D = getDirection();
26309467b48Spatrick if (D == Direction::Increasing)
26409467b48Spatrick return ICmpInst::ICMP_SLT;
26509467b48Spatrick
26609467b48Spatrick if (D == Direction::Decreasing)
26709467b48Spatrick return ICmpInst::ICMP_SGT;
26809467b48Spatrick
26909467b48Spatrick // If cannot determine the direction, then unable to find the canonical
27009467b48Spatrick // predicate
27109467b48Spatrick return ICmpInst::BAD_ICMP_PREDICATE;
27209467b48Spatrick }
27309467b48Spatrick
getDirection() const27409467b48Spatrick Direction Loop::LoopBounds::getDirection() const {
27509467b48Spatrick if (const SCEVAddRecExpr *StepAddRecExpr =
27609467b48Spatrick dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&getStepInst())))
27709467b48Spatrick if (const SCEV *StepRecur = StepAddRecExpr->getStepRecurrence(SE)) {
27809467b48Spatrick if (SE.isKnownPositive(StepRecur))
27909467b48Spatrick return Direction::Increasing;
28009467b48Spatrick if (SE.isKnownNegative(StepRecur))
28109467b48Spatrick return Direction::Decreasing;
28209467b48Spatrick }
28309467b48Spatrick
28409467b48Spatrick return Direction::Unknown;
28509467b48Spatrick }
28609467b48Spatrick
getBounds(ScalarEvolution & SE) const287*d415bd75Srobert std::optional<Loop::LoopBounds> Loop::getBounds(ScalarEvolution &SE) const {
28809467b48Spatrick if (PHINode *IndVar = getInductionVariable(SE))
28909467b48Spatrick return LoopBounds::getBounds(*this, *IndVar, SE);
29009467b48Spatrick
291*d415bd75Srobert return std::nullopt;
29209467b48Spatrick }
29309467b48Spatrick
getInductionVariable(ScalarEvolution & SE) const29409467b48Spatrick PHINode *Loop::getInductionVariable(ScalarEvolution &SE) const {
29509467b48Spatrick if (!isLoopSimplifyForm())
29609467b48Spatrick return nullptr;
29709467b48Spatrick
29809467b48Spatrick BasicBlock *Header = getHeader();
29909467b48Spatrick assert(Header && "Expected a valid loop header");
30073471bf0Spatrick ICmpInst *CmpInst = getLatchCmpInst();
30109467b48Spatrick if (!CmpInst)
30209467b48Spatrick return nullptr;
30309467b48Spatrick
304*d415bd75Srobert Value *LatchCmpOp0 = CmpInst->getOperand(0);
305*d415bd75Srobert Value *LatchCmpOp1 = CmpInst->getOperand(1);
30609467b48Spatrick
30709467b48Spatrick for (PHINode &IndVar : Header->phis()) {
30809467b48Spatrick InductionDescriptor IndDesc;
30909467b48Spatrick if (!InductionDescriptor::isInductionPHI(&IndVar, this, &SE, IndDesc))
31009467b48Spatrick continue;
31109467b48Spatrick
312*d415bd75Srobert BasicBlock *Latch = getLoopLatch();
313*d415bd75Srobert Value *StepInst = IndVar.getIncomingValueForBlock(Latch);
31409467b48Spatrick
31509467b48Spatrick // case 1:
31609467b48Spatrick // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
31709467b48Spatrick // StepInst = IndVar + step
31809467b48Spatrick // cmp = StepInst < FinalValue
31909467b48Spatrick if (StepInst == LatchCmpOp0 || StepInst == LatchCmpOp1)
32009467b48Spatrick return &IndVar;
32109467b48Spatrick
32209467b48Spatrick // case 2:
32309467b48Spatrick // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
32409467b48Spatrick // StepInst = IndVar + step
32509467b48Spatrick // cmp = IndVar < FinalValue
32609467b48Spatrick if (&IndVar == LatchCmpOp0 || &IndVar == LatchCmpOp1)
32709467b48Spatrick return &IndVar;
32809467b48Spatrick }
32909467b48Spatrick
33009467b48Spatrick return nullptr;
33109467b48Spatrick }
33209467b48Spatrick
getInductionDescriptor(ScalarEvolution & SE,InductionDescriptor & IndDesc) const33309467b48Spatrick bool Loop::getInductionDescriptor(ScalarEvolution &SE,
33409467b48Spatrick InductionDescriptor &IndDesc) const {
33509467b48Spatrick if (PHINode *IndVar = getInductionVariable(SE))
33609467b48Spatrick return InductionDescriptor::isInductionPHI(IndVar, this, &SE, IndDesc);
33709467b48Spatrick
33809467b48Spatrick return false;
33909467b48Spatrick }
34009467b48Spatrick
isAuxiliaryInductionVariable(PHINode & AuxIndVar,ScalarEvolution & SE) const34109467b48Spatrick bool Loop::isAuxiliaryInductionVariable(PHINode &AuxIndVar,
34209467b48Spatrick ScalarEvolution &SE) const {
34309467b48Spatrick // Located in the loop header
34409467b48Spatrick BasicBlock *Header = getHeader();
34509467b48Spatrick if (AuxIndVar.getParent() != Header)
34609467b48Spatrick return false;
34709467b48Spatrick
34809467b48Spatrick // No uses outside of the loop
34909467b48Spatrick for (User *U : AuxIndVar.users())
35009467b48Spatrick if (const Instruction *I = dyn_cast<Instruction>(U))
35109467b48Spatrick if (!contains(I))
35209467b48Spatrick return false;
35309467b48Spatrick
35409467b48Spatrick InductionDescriptor IndDesc;
35509467b48Spatrick if (!InductionDescriptor::isInductionPHI(&AuxIndVar, this, &SE, IndDesc))
35609467b48Spatrick return false;
35709467b48Spatrick
35809467b48Spatrick // The step instruction opcode should be add or sub.
35909467b48Spatrick if (IndDesc.getInductionOpcode() != Instruction::Add &&
36009467b48Spatrick IndDesc.getInductionOpcode() != Instruction::Sub)
36109467b48Spatrick return false;
36209467b48Spatrick
36309467b48Spatrick // Incremented by a loop invariant step for each loop iteration
36409467b48Spatrick return SE.isLoopInvariant(IndDesc.getStep(), this);
36509467b48Spatrick }
36609467b48Spatrick
getLoopGuardBranch() const36709467b48Spatrick BranchInst *Loop::getLoopGuardBranch() const {
36809467b48Spatrick if (!isLoopSimplifyForm())
36909467b48Spatrick return nullptr;
37009467b48Spatrick
37109467b48Spatrick BasicBlock *Preheader = getLoopPreheader();
37209467b48Spatrick assert(Preheader && getLoopLatch() &&
37309467b48Spatrick "Expecting a loop with valid preheader and latch");
37409467b48Spatrick
37509467b48Spatrick // Loop should be in rotate form.
37609467b48Spatrick if (!isRotatedForm())
37709467b48Spatrick return nullptr;
37809467b48Spatrick
37909467b48Spatrick // Disallow loops with more than one unique exit block, as we do not verify
38009467b48Spatrick // that GuardOtherSucc post dominates all exit blocks.
38109467b48Spatrick BasicBlock *ExitFromLatch = getUniqueExitBlock();
38209467b48Spatrick if (!ExitFromLatch)
38309467b48Spatrick return nullptr;
38409467b48Spatrick
38509467b48Spatrick BasicBlock *GuardBB = Preheader->getUniquePredecessor();
38609467b48Spatrick if (!GuardBB)
38709467b48Spatrick return nullptr;
38809467b48Spatrick
38909467b48Spatrick assert(GuardBB->getTerminator() && "Expecting valid guard terminator");
39009467b48Spatrick
39109467b48Spatrick BranchInst *GuardBI = dyn_cast<BranchInst>(GuardBB->getTerminator());
39209467b48Spatrick if (!GuardBI || GuardBI->isUnconditional())
39309467b48Spatrick return nullptr;
39409467b48Spatrick
39509467b48Spatrick BasicBlock *GuardOtherSucc = (GuardBI->getSuccessor(0) == Preheader)
39609467b48Spatrick ? GuardBI->getSuccessor(1)
39709467b48Spatrick : GuardBI->getSuccessor(0);
39873471bf0Spatrick
39973471bf0Spatrick // Check if ExitFromLatch (or any BasicBlock which is an empty unique
40073471bf0Spatrick // successor of ExitFromLatch) is equal to GuardOtherSucc. If
40173471bf0Spatrick // skipEmptyBlockUntil returns GuardOtherSucc, then the guard branch for the
40273471bf0Spatrick // loop is GuardBI (return GuardBI), otherwise return nullptr.
40373471bf0Spatrick if (&LoopNest::skipEmptyBlockUntil(ExitFromLatch, GuardOtherSucc,
40473471bf0Spatrick /*CheckUniquePred=*/true) ==
40573471bf0Spatrick GuardOtherSucc)
40673471bf0Spatrick return GuardBI;
40773471bf0Spatrick else
40873471bf0Spatrick return nullptr;
40909467b48Spatrick }
41009467b48Spatrick
isCanonical(ScalarEvolution & SE) const41109467b48Spatrick bool Loop::isCanonical(ScalarEvolution &SE) const {
41209467b48Spatrick InductionDescriptor IndDesc;
41309467b48Spatrick if (!getInductionDescriptor(SE, IndDesc))
41409467b48Spatrick return false;
41509467b48Spatrick
41609467b48Spatrick ConstantInt *Init = dyn_cast_or_null<ConstantInt>(IndDesc.getStartValue());
41709467b48Spatrick if (!Init || !Init->isZero())
41809467b48Spatrick return false;
41909467b48Spatrick
42009467b48Spatrick if (IndDesc.getInductionOpcode() != Instruction::Add)
42109467b48Spatrick return false;
42209467b48Spatrick
42309467b48Spatrick ConstantInt *Step = IndDesc.getConstIntStepValue();
42409467b48Spatrick if (!Step || !Step->isOne())
42509467b48Spatrick return false;
42609467b48Spatrick
42709467b48Spatrick return true;
42809467b48Spatrick }
42909467b48Spatrick
43009467b48Spatrick // Check that 'BB' doesn't have any uses outside of the 'L'
isBlockInLCSSAForm(const Loop & L,const BasicBlock & BB,const DominatorTree & DT,bool IgnoreTokens)43109467b48Spatrick static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
432*d415bd75Srobert const DominatorTree &DT, bool IgnoreTokens) {
43309467b48Spatrick for (const Instruction &I : BB) {
43409467b48Spatrick // Tokens can't be used in PHI nodes and live-out tokens prevent loop
43509467b48Spatrick // optimizations, so for the purposes of considered LCSSA form, we
43609467b48Spatrick // can ignore them.
437*d415bd75Srobert if (IgnoreTokens && I.getType()->isTokenTy())
43809467b48Spatrick continue;
43909467b48Spatrick
44009467b48Spatrick for (const Use &U : I.uses()) {
44109467b48Spatrick const Instruction *UI = cast<Instruction>(U.getUser());
44209467b48Spatrick const BasicBlock *UserBB = UI->getParent();
44373471bf0Spatrick
44473471bf0Spatrick // For practical purposes, we consider that the use in a PHI
44573471bf0Spatrick // occurs in the respective predecessor block. For more info,
44673471bf0Spatrick // see the `phi` doc in LangRef and the LCSSA doc.
44709467b48Spatrick if (const PHINode *P = dyn_cast<PHINode>(UI))
44809467b48Spatrick UserBB = P->getIncomingBlock(U);
44909467b48Spatrick
45009467b48Spatrick // Check the current block, as a fast-path, before checking whether
45109467b48Spatrick // the use is anywhere in the loop. Most values are used in the same
45209467b48Spatrick // block they are defined in. Also, blocks not reachable from the
45309467b48Spatrick // entry are special; uses in them don't need to go through PHIs.
45409467b48Spatrick if (UserBB != &BB && !L.contains(UserBB) &&
45509467b48Spatrick DT.isReachableFromEntry(UserBB))
45609467b48Spatrick return false;
45709467b48Spatrick }
45809467b48Spatrick }
45909467b48Spatrick return true;
46009467b48Spatrick }
46109467b48Spatrick
isLCSSAForm(const DominatorTree & DT,bool IgnoreTokens) const462*d415bd75Srobert bool Loop::isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens) const {
46309467b48Spatrick // For each block we check that it doesn't have any uses outside of this loop.
46409467b48Spatrick return all_of(this->blocks(), [&](const BasicBlock *BB) {
465*d415bd75Srobert return isBlockInLCSSAForm(*this, *BB, DT, IgnoreTokens);
46609467b48Spatrick });
46709467b48Spatrick }
46809467b48Spatrick
isRecursivelyLCSSAForm(const DominatorTree & DT,const LoopInfo & LI,bool IgnoreTokens) const469*d415bd75Srobert bool Loop::isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI,
470*d415bd75Srobert bool IgnoreTokens) const {
47109467b48Spatrick // For each block we check that it doesn't have any uses outside of its
47209467b48Spatrick // innermost loop. This process will transitively guarantee that the current
47309467b48Spatrick // loop and all of the nested loops are in LCSSA form.
47409467b48Spatrick return all_of(this->blocks(), [&](const BasicBlock *BB) {
475*d415bd75Srobert return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT, IgnoreTokens);
47609467b48Spatrick });
47709467b48Spatrick }
47809467b48Spatrick
isLoopSimplifyForm() const47909467b48Spatrick bool Loop::isLoopSimplifyForm() const {
48009467b48Spatrick // Normal-form loops have a preheader, a single backedge, and all of their
48109467b48Spatrick // exits have all their predecessors inside the loop.
48209467b48Spatrick return getLoopPreheader() && getLoopLatch() && hasDedicatedExits();
48309467b48Spatrick }
48409467b48Spatrick
48509467b48Spatrick // Routines that reform the loop CFG and split edges often fail on indirectbr.
isSafeToClone() const48609467b48Spatrick bool Loop::isSafeToClone() const {
48709467b48Spatrick // Return false if any loop blocks contain indirectbrs, or there are any calls
48809467b48Spatrick // to noduplicate functions.
48909467b48Spatrick for (BasicBlock *BB : this->blocks()) {
490*d415bd75Srobert if (isa<IndirectBrInst>(BB->getTerminator()))
49109467b48Spatrick return false;
49209467b48Spatrick
49309467b48Spatrick for (Instruction &I : *BB)
494097a140dSpatrick if (auto *CB = dyn_cast<CallBase>(&I))
495097a140dSpatrick if (CB->cannotDuplicate())
49609467b48Spatrick return false;
49709467b48Spatrick }
49809467b48Spatrick return true;
49909467b48Spatrick }
50009467b48Spatrick
getLoopID() const50109467b48Spatrick MDNode *Loop::getLoopID() const {
50209467b48Spatrick MDNode *LoopID = nullptr;
50309467b48Spatrick
50409467b48Spatrick // Go through the latch blocks and check the terminator for the metadata.
50509467b48Spatrick SmallVector<BasicBlock *, 4> LatchesBlocks;
50609467b48Spatrick getLoopLatches(LatchesBlocks);
50709467b48Spatrick for (BasicBlock *BB : LatchesBlocks) {
50809467b48Spatrick Instruction *TI = BB->getTerminator();
50909467b48Spatrick MDNode *MD = TI->getMetadata(LLVMContext::MD_loop);
51009467b48Spatrick
51109467b48Spatrick if (!MD)
51209467b48Spatrick return nullptr;
51309467b48Spatrick
51409467b48Spatrick if (!LoopID)
51509467b48Spatrick LoopID = MD;
51609467b48Spatrick else if (MD != LoopID)
51709467b48Spatrick return nullptr;
51809467b48Spatrick }
51909467b48Spatrick if (!LoopID || LoopID->getNumOperands() == 0 ||
52009467b48Spatrick LoopID->getOperand(0) != LoopID)
52109467b48Spatrick return nullptr;
52209467b48Spatrick return LoopID;
52309467b48Spatrick }
52409467b48Spatrick
setLoopID(MDNode * LoopID) const52509467b48Spatrick void Loop::setLoopID(MDNode *LoopID) const {
52609467b48Spatrick assert((!LoopID || LoopID->getNumOperands() > 0) &&
52709467b48Spatrick "Loop ID needs at least one operand");
52809467b48Spatrick assert((!LoopID || LoopID->getOperand(0) == LoopID) &&
52909467b48Spatrick "Loop ID should refer to itself");
53009467b48Spatrick
53109467b48Spatrick SmallVector<BasicBlock *, 4> LoopLatches;
53209467b48Spatrick getLoopLatches(LoopLatches);
53309467b48Spatrick for (BasicBlock *BB : LoopLatches)
53409467b48Spatrick BB->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
53509467b48Spatrick }
53609467b48Spatrick
setLoopAlreadyUnrolled()53709467b48Spatrick void Loop::setLoopAlreadyUnrolled() {
53809467b48Spatrick LLVMContext &Context = getHeader()->getContext();
53909467b48Spatrick
54009467b48Spatrick MDNode *DisableUnrollMD =
54109467b48Spatrick MDNode::get(Context, MDString::get(Context, "llvm.loop.unroll.disable"));
54209467b48Spatrick MDNode *LoopID = getLoopID();
54309467b48Spatrick MDNode *NewLoopID = makePostTransformationMetadata(
54409467b48Spatrick Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD});
54509467b48Spatrick setLoopID(NewLoopID);
54609467b48Spatrick }
54709467b48Spatrick
setLoopMustProgress()54873471bf0Spatrick void Loop::setLoopMustProgress() {
54973471bf0Spatrick LLVMContext &Context = getHeader()->getContext();
55073471bf0Spatrick
55173471bf0Spatrick MDNode *MustProgress = findOptionMDForLoop(this, "llvm.loop.mustprogress");
55273471bf0Spatrick
55373471bf0Spatrick if (MustProgress)
55473471bf0Spatrick return;
55573471bf0Spatrick
55673471bf0Spatrick MDNode *MustProgressMD =
55773471bf0Spatrick MDNode::get(Context, MDString::get(Context, "llvm.loop.mustprogress"));
55873471bf0Spatrick MDNode *LoopID = getLoopID();
55973471bf0Spatrick MDNode *NewLoopID =
56073471bf0Spatrick makePostTransformationMetadata(Context, LoopID, {}, {MustProgressMD});
56173471bf0Spatrick setLoopID(NewLoopID);
56273471bf0Spatrick }
56373471bf0Spatrick
isAnnotatedParallel() const56409467b48Spatrick bool Loop::isAnnotatedParallel() const {
56509467b48Spatrick MDNode *DesiredLoopIdMetadata = getLoopID();
56609467b48Spatrick
56709467b48Spatrick if (!DesiredLoopIdMetadata)
56809467b48Spatrick return false;
56909467b48Spatrick
57009467b48Spatrick MDNode *ParallelAccesses =
57109467b48Spatrick findOptionMDForLoop(this, "llvm.loop.parallel_accesses");
57209467b48Spatrick SmallPtrSet<MDNode *, 4>
57309467b48Spatrick ParallelAccessGroups; // For scalable 'contains' check.
57409467b48Spatrick if (ParallelAccesses) {
57573471bf0Spatrick for (const MDOperand &MD : drop_begin(ParallelAccesses->operands())) {
57609467b48Spatrick MDNode *AccGroup = cast<MDNode>(MD.get());
57709467b48Spatrick assert(isValidAsAccessGroup(AccGroup) &&
57809467b48Spatrick "List item must be an access group");
57909467b48Spatrick ParallelAccessGroups.insert(AccGroup);
58009467b48Spatrick }
58109467b48Spatrick }
58209467b48Spatrick
58309467b48Spatrick // The loop branch contains the parallel loop metadata. In order to ensure
58409467b48Spatrick // that any parallel-loop-unaware optimization pass hasn't added loop-carried
58509467b48Spatrick // dependencies (thus converted the loop back to a sequential loop), check
58609467b48Spatrick // that all the memory instructions in the loop belong to an access group that
58709467b48Spatrick // is parallel to this loop.
58809467b48Spatrick for (BasicBlock *BB : this->blocks()) {
58909467b48Spatrick for (Instruction &I : *BB) {
59009467b48Spatrick if (!I.mayReadOrWriteMemory())
59109467b48Spatrick continue;
59209467b48Spatrick
59309467b48Spatrick if (MDNode *AccessGroup = I.getMetadata(LLVMContext::MD_access_group)) {
59409467b48Spatrick auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool {
59509467b48Spatrick if (AG->getNumOperands() == 0) {
59609467b48Spatrick assert(isValidAsAccessGroup(AG) && "Item must be an access group");
59709467b48Spatrick return ParallelAccessGroups.count(AG);
59809467b48Spatrick }
59909467b48Spatrick
60009467b48Spatrick for (const MDOperand &AccessListItem : AG->operands()) {
60109467b48Spatrick MDNode *AccGroup = cast<MDNode>(AccessListItem.get());
60209467b48Spatrick assert(isValidAsAccessGroup(AccGroup) &&
60309467b48Spatrick "List item must be an access group");
60409467b48Spatrick if (ParallelAccessGroups.count(AccGroup))
60509467b48Spatrick return true;
60609467b48Spatrick }
60709467b48Spatrick return false;
60809467b48Spatrick };
60909467b48Spatrick
61009467b48Spatrick if (ContainsAccessGroup(AccessGroup))
61109467b48Spatrick continue;
61209467b48Spatrick }
61309467b48Spatrick
61409467b48Spatrick // The memory instruction can refer to the loop identifier metadata
61509467b48Spatrick // directly or indirectly through another list metadata (in case of
61609467b48Spatrick // nested parallel loops). The loop identifier metadata refers to
61709467b48Spatrick // itself so we can check both cases with the same routine.
61809467b48Spatrick MDNode *LoopIdMD =
61909467b48Spatrick I.getMetadata(LLVMContext::MD_mem_parallel_loop_access);
62009467b48Spatrick
62109467b48Spatrick if (!LoopIdMD)
62209467b48Spatrick return false;
62309467b48Spatrick
62473471bf0Spatrick if (!llvm::is_contained(LoopIdMD->operands(), DesiredLoopIdMetadata))
62509467b48Spatrick return false;
62609467b48Spatrick }
62709467b48Spatrick }
62809467b48Spatrick return true;
62909467b48Spatrick }
63009467b48Spatrick
getStartLoc() const63109467b48Spatrick DebugLoc Loop::getStartLoc() const { return getLocRange().getStart(); }
63209467b48Spatrick
getLocRange() const63309467b48Spatrick Loop::LocRange Loop::getLocRange() const {
63409467b48Spatrick // If we have a debug location in the loop ID, then use it.
63509467b48Spatrick if (MDNode *LoopID = getLoopID()) {
63609467b48Spatrick DebugLoc Start;
63709467b48Spatrick // We use the first DebugLoc in the header as the start location of the loop
63809467b48Spatrick // and if there is a second DebugLoc in the header we use it as end location
63909467b48Spatrick // of the loop.
64009467b48Spatrick for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
64109467b48Spatrick if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) {
64209467b48Spatrick if (!Start)
64309467b48Spatrick Start = DebugLoc(L);
64409467b48Spatrick else
64509467b48Spatrick return LocRange(Start, DebugLoc(L));
64609467b48Spatrick }
64709467b48Spatrick }
64809467b48Spatrick
64909467b48Spatrick if (Start)
65009467b48Spatrick return LocRange(Start);
65109467b48Spatrick }
65209467b48Spatrick
65309467b48Spatrick // Try the pre-header first.
65409467b48Spatrick if (BasicBlock *PHeadBB = getLoopPreheader())
65509467b48Spatrick if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
65609467b48Spatrick return LocRange(DL);
65709467b48Spatrick
65809467b48Spatrick // If we have no pre-header or there are no instructions with debug
65909467b48Spatrick // info in it, try the header.
66009467b48Spatrick if (BasicBlock *HeadBB = getHeader())
66109467b48Spatrick return LocRange(HeadBB->getTerminator()->getDebugLoc());
66209467b48Spatrick
66309467b48Spatrick return LocRange();
66409467b48Spatrick }
66509467b48Spatrick
66609467b48Spatrick #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const66709467b48Spatrick LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
66809467b48Spatrick
dumpVerbose() const66909467b48Spatrick LLVM_DUMP_METHOD void Loop::dumpVerbose() const {
67073471bf0Spatrick print(dbgs(), /*Verbose=*/true);
67109467b48Spatrick }
67209467b48Spatrick #endif
67309467b48Spatrick
67409467b48Spatrick //===----------------------------------------------------------------------===//
67509467b48Spatrick // UnloopUpdater implementation
67609467b48Spatrick //
67709467b48Spatrick
67809467b48Spatrick namespace {
67909467b48Spatrick /// Find the new parent loop for all blocks within the "unloop" whose last
68009467b48Spatrick /// backedges has just been removed.
68109467b48Spatrick class UnloopUpdater {
68209467b48Spatrick Loop &Unloop;
68309467b48Spatrick LoopInfo *LI;
68409467b48Spatrick
68509467b48Spatrick LoopBlocksDFS DFS;
68609467b48Spatrick
68709467b48Spatrick // Map unloop's immediate subloops to their nearest reachable parents. Nested
68809467b48Spatrick // loops within these subloops will not change parents. However, an immediate
68909467b48Spatrick // subloop's new parent will be the nearest loop reachable from either its own
69009467b48Spatrick // exits *or* any of its nested loop's exits.
69109467b48Spatrick DenseMap<Loop *, Loop *> SubloopParents;
69209467b48Spatrick
69309467b48Spatrick // Flag the presence of an irreducible backedge whose destination is a block
69409467b48Spatrick // directly contained by the original unloop.
695*d415bd75Srobert bool FoundIB = false;
69609467b48Spatrick
69709467b48Spatrick public:
UnloopUpdater(Loop * UL,LoopInfo * LInfo)698*d415bd75Srobert UnloopUpdater(Loop *UL, LoopInfo *LInfo) : Unloop(*UL), LI(LInfo), DFS(UL) {}
69909467b48Spatrick
70009467b48Spatrick void updateBlockParents();
70109467b48Spatrick
70209467b48Spatrick void removeBlocksFromAncestors();
70309467b48Spatrick
70409467b48Spatrick void updateSubloopParents();
70509467b48Spatrick
70609467b48Spatrick protected:
70709467b48Spatrick Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
70809467b48Spatrick };
70909467b48Spatrick } // end anonymous namespace
71009467b48Spatrick
71109467b48Spatrick /// Update the parent loop for all blocks that are directly contained within the
71209467b48Spatrick /// original "unloop".
updateBlockParents()71309467b48Spatrick void UnloopUpdater::updateBlockParents() {
71409467b48Spatrick if (Unloop.getNumBlocks()) {
71509467b48Spatrick // Perform a post order CFG traversal of all blocks within this loop,
71609467b48Spatrick // propagating the nearest loop from successors to predecessors.
71709467b48Spatrick LoopBlocksTraversal Traversal(DFS, LI);
71809467b48Spatrick for (BasicBlock *POI : Traversal) {
71909467b48Spatrick
72009467b48Spatrick Loop *L = LI->getLoopFor(POI);
72109467b48Spatrick Loop *NL = getNearestLoop(POI, L);
72209467b48Spatrick
72309467b48Spatrick if (NL != L) {
72409467b48Spatrick // For reducible loops, NL is now an ancestor of Unloop.
72509467b48Spatrick assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
72609467b48Spatrick "uninitialized successor");
72709467b48Spatrick LI->changeLoopFor(POI, NL);
72809467b48Spatrick } else {
72909467b48Spatrick // Or the current block is part of a subloop, in which case its parent
73009467b48Spatrick // is unchanged.
73109467b48Spatrick assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
73209467b48Spatrick }
73309467b48Spatrick }
73409467b48Spatrick }
73509467b48Spatrick // Each irreducible loop within the unloop induces a round of iteration using
73609467b48Spatrick // the DFS result cached by Traversal.
73709467b48Spatrick bool Changed = FoundIB;
73809467b48Spatrick for (unsigned NIters = 0; Changed; ++NIters) {
73909467b48Spatrick assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
740*d415bd75Srobert (void) NIters;
74109467b48Spatrick
74209467b48Spatrick // Iterate over the postorder list of blocks, propagating the nearest loop
74309467b48Spatrick // from successors to predecessors as before.
74409467b48Spatrick Changed = false;
74509467b48Spatrick for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
74609467b48Spatrick POE = DFS.endPostorder();
74709467b48Spatrick POI != POE; ++POI) {
74809467b48Spatrick
74909467b48Spatrick Loop *L = LI->getLoopFor(*POI);
75009467b48Spatrick Loop *NL = getNearestLoop(*POI, L);
75109467b48Spatrick if (NL != L) {
75209467b48Spatrick assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&
75309467b48Spatrick "uninitialized successor");
75409467b48Spatrick LI->changeLoopFor(*POI, NL);
75509467b48Spatrick Changed = true;
75609467b48Spatrick }
75709467b48Spatrick }
75809467b48Spatrick }
75909467b48Spatrick }
76009467b48Spatrick
76109467b48Spatrick /// Remove unloop's blocks from all ancestors below their new parents.
removeBlocksFromAncestors()76209467b48Spatrick void UnloopUpdater::removeBlocksFromAncestors() {
76309467b48Spatrick // Remove all unloop's blocks (including those in nested subloops) from
76409467b48Spatrick // ancestors below the new parent loop.
76573471bf0Spatrick for (BasicBlock *BB : Unloop.blocks()) {
76673471bf0Spatrick Loop *OuterParent = LI->getLoopFor(BB);
76709467b48Spatrick if (Unloop.contains(OuterParent)) {
76809467b48Spatrick while (OuterParent->getParentLoop() != &Unloop)
76909467b48Spatrick OuterParent = OuterParent->getParentLoop();
77009467b48Spatrick OuterParent = SubloopParents[OuterParent];
77109467b48Spatrick }
77209467b48Spatrick // Remove blocks from former Ancestors except Unloop itself which will be
77309467b48Spatrick // deleted.
77409467b48Spatrick for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
77509467b48Spatrick OldParent = OldParent->getParentLoop()) {
77609467b48Spatrick assert(OldParent && "new loop is not an ancestor of the original");
77773471bf0Spatrick OldParent->removeBlockFromLoop(BB);
77809467b48Spatrick }
77909467b48Spatrick }
78009467b48Spatrick }
78109467b48Spatrick
78209467b48Spatrick /// Update the parent loop for all subloops directly nested within unloop.
updateSubloopParents()78309467b48Spatrick void UnloopUpdater::updateSubloopParents() {
78473471bf0Spatrick while (!Unloop.isInnermost()) {
78509467b48Spatrick Loop *Subloop = *std::prev(Unloop.end());
78609467b48Spatrick Unloop.removeChildLoop(std::prev(Unloop.end()));
78709467b48Spatrick
78809467b48Spatrick assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
78909467b48Spatrick if (Loop *Parent = SubloopParents[Subloop])
79009467b48Spatrick Parent->addChildLoop(Subloop);
79109467b48Spatrick else
79209467b48Spatrick LI->addTopLevelLoop(Subloop);
79309467b48Spatrick }
79409467b48Spatrick }
79509467b48Spatrick
79609467b48Spatrick /// Return the nearest parent loop among this block's successors. If a successor
79709467b48Spatrick /// is a subloop header, consider its parent to be the nearest parent of the
79809467b48Spatrick /// subloop's exits.
79909467b48Spatrick ///
80009467b48Spatrick /// For subloop blocks, simply update SubloopParents and return NULL.
getNearestLoop(BasicBlock * BB,Loop * BBLoop)80109467b48Spatrick Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
80209467b48Spatrick
80309467b48Spatrick // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
80409467b48Spatrick // is considered uninitialized.
80509467b48Spatrick Loop *NearLoop = BBLoop;
80609467b48Spatrick
80709467b48Spatrick Loop *Subloop = nullptr;
80809467b48Spatrick if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
80909467b48Spatrick Subloop = NearLoop;
81009467b48Spatrick // Find the subloop ancestor that is directly contained within Unloop.
81109467b48Spatrick while (Subloop->getParentLoop() != &Unloop) {
81209467b48Spatrick Subloop = Subloop->getParentLoop();
81309467b48Spatrick assert(Subloop && "subloop is not an ancestor of the original loop");
81409467b48Spatrick }
81509467b48Spatrick // Get the current nearest parent of the Subloop exits, initially Unloop.
81609467b48Spatrick NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
81709467b48Spatrick }
81809467b48Spatrick
81909467b48Spatrick succ_iterator I = succ_begin(BB), E = succ_end(BB);
82009467b48Spatrick if (I == E) {
82109467b48Spatrick assert(!Subloop && "subloop blocks must have a successor");
82209467b48Spatrick NearLoop = nullptr; // unloop blocks may now exit the function.
82309467b48Spatrick }
82409467b48Spatrick for (; I != E; ++I) {
82509467b48Spatrick if (*I == BB)
82609467b48Spatrick continue; // self loops are uninteresting
82709467b48Spatrick
82809467b48Spatrick Loop *L = LI->getLoopFor(*I);
82909467b48Spatrick if (L == &Unloop) {
83009467b48Spatrick // This successor has not been processed. This path must lead to an
83109467b48Spatrick // irreducible backedge.
83209467b48Spatrick assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB");
83309467b48Spatrick FoundIB = true;
83409467b48Spatrick }
83509467b48Spatrick if (L != &Unloop && Unloop.contains(L)) {
83609467b48Spatrick // Successor is in a subloop.
83709467b48Spatrick if (Subloop)
83809467b48Spatrick continue; // Branching within subloops. Ignore it.
83909467b48Spatrick
84009467b48Spatrick // BB branches from the original into a subloop header.
84109467b48Spatrick assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops");
84209467b48Spatrick
84309467b48Spatrick // Get the current nearest parent of the Subloop's exits.
84409467b48Spatrick L = SubloopParents[L];
84509467b48Spatrick // L could be Unloop if the only exit was an irreducible backedge.
84609467b48Spatrick }
84709467b48Spatrick if (L == &Unloop) {
84809467b48Spatrick continue;
84909467b48Spatrick }
85009467b48Spatrick // Handle critical edges from Unloop into a sibling loop.
85109467b48Spatrick if (L && !L->contains(&Unloop)) {
85209467b48Spatrick L = L->getParentLoop();
85309467b48Spatrick }
85409467b48Spatrick // Remember the nearest parent loop among successors or subloop exits.
85509467b48Spatrick if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
85609467b48Spatrick NearLoop = L;
85709467b48Spatrick }
85809467b48Spatrick if (Subloop) {
85909467b48Spatrick SubloopParents[Subloop] = NearLoop;
86009467b48Spatrick return BBLoop;
86109467b48Spatrick }
86209467b48Spatrick return NearLoop;
86309467b48Spatrick }
86409467b48Spatrick
LoopInfo(const DomTreeBase<BasicBlock> & DomTree)86509467b48Spatrick LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
86609467b48Spatrick
invalidate(Function & F,const PreservedAnalyses & PA,FunctionAnalysisManager::Invalidator &)86709467b48Spatrick bool LoopInfo::invalidate(Function &F, const PreservedAnalyses &PA,
86809467b48Spatrick FunctionAnalysisManager::Invalidator &) {
86909467b48Spatrick // Check whether the analysis, all analyses on functions, or the function's
87009467b48Spatrick // CFG have been preserved.
87109467b48Spatrick auto PAC = PA.getChecker<LoopAnalysis>();
87209467b48Spatrick return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
87309467b48Spatrick PAC.preservedSet<CFGAnalyses>());
87409467b48Spatrick }
87509467b48Spatrick
erase(Loop * Unloop)87609467b48Spatrick void LoopInfo::erase(Loop *Unloop) {
87709467b48Spatrick assert(!Unloop->isInvalid() && "Loop has already been erased!");
87809467b48Spatrick
87909467b48Spatrick auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); });
88009467b48Spatrick
88109467b48Spatrick // First handle the special case of no parent loop to simplify the algorithm.
88273471bf0Spatrick if (Unloop->isOutermost()) {
88309467b48Spatrick // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
88473471bf0Spatrick for (BasicBlock *BB : Unloop->blocks()) {
88509467b48Spatrick // Don't reparent blocks in subloops.
88673471bf0Spatrick if (getLoopFor(BB) != Unloop)
88709467b48Spatrick continue;
88809467b48Spatrick
88909467b48Spatrick // Blocks no longer have a parent but are still referenced by Unloop until
89009467b48Spatrick // the Unloop object is deleted.
89173471bf0Spatrick changeLoopFor(BB, nullptr);
89209467b48Spatrick }
89309467b48Spatrick
89409467b48Spatrick // Remove the loop from the top-level LoopInfo object.
89509467b48Spatrick for (iterator I = begin();; ++I) {
89609467b48Spatrick assert(I != end() && "Couldn't find loop");
89709467b48Spatrick if (*I == Unloop) {
89809467b48Spatrick removeLoop(I);
89909467b48Spatrick break;
90009467b48Spatrick }
90109467b48Spatrick }
90209467b48Spatrick
90309467b48Spatrick // Move all of the subloops to the top-level.
90473471bf0Spatrick while (!Unloop->isInnermost())
90509467b48Spatrick addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
90609467b48Spatrick
90709467b48Spatrick return;
90809467b48Spatrick }
90909467b48Spatrick
91009467b48Spatrick // Update the parent loop for all blocks within the loop. Blocks within
91109467b48Spatrick // subloops will not change parents.
91209467b48Spatrick UnloopUpdater Updater(Unloop, this);
91309467b48Spatrick Updater.updateBlockParents();
91409467b48Spatrick
91509467b48Spatrick // Remove blocks from former ancestor loops.
91609467b48Spatrick Updater.removeBlocksFromAncestors();
91709467b48Spatrick
91809467b48Spatrick // Add direct subloops as children in their new parent loop.
91909467b48Spatrick Updater.updateSubloopParents();
92009467b48Spatrick
92109467b48Spatrick // Remove unloop from its parent loop.
92209467b48Spatrick Loop *ParentLoop = Unloop->getParentLoop();
92309467b48Spatrick for (Loop::iterator I = ParentLoop->begin();; ++I) {
92409467b48Spatrick assert(I != ParentLoop->end() && "Couldn't find loop");
92509467b48Spatrick if (*I == Unloop) {
92609467b48Spatrick ParentLoop->removeChildLoop(I);
92709467b48Spatrick break;
92809467b48Spatrick }
92909467b48Spatrick }
93009467b48Spatrick }
93109467b48Spatrick
93273471bf0Spatrick bool
wouldBeOutOfLoopUseRequiringLCSSA(const Value * V,const BasicBlock * ExitBB) const93373471bf0Spatrick LoopInfo::wouldBeOutOfLoopUseRequiringLCSSA(const Value *V,
93473471bf0Spatrick const BasicBlock *ExitBB) const {
93573471bf0Spatrick if (V->getType()->isTokenTy())
93673471bf0Spatrick // We can't form PHIs of token type, so the definition of LCSSA excludes
93773471bf0Spatrick // values of that type.
93873471bf0Spatrick return false;
93973471bf0Spatrick
94073471bf0Spatrick const Instruction *I = dyn_cast<Instruction>(V);
94173471bf0Spatrick if (!I)
94273471bf0Spatrick return false;
94373471bf0Spatrick const Loop *L = getLoopFor(I->getParent());
94473471bf0Spatrick if (!L)
94573471bf0Spatrick return false;
94673471bf0Spatrick if (L->contains(ExitBB))
94773471bf0Spatrick // Could be an exit bb of a subloop and contained in defining loop
94873471bf0Spatrick return false;
94973471bf0Spatrick
95073471bf0Spatrick // We found a (new) out-of-loop use location, for a value defined in-loop.
95173471bf0Spatrick // (Note that because of LCSSA, we don't have to account for values defined
95273471bf0Spatrick // in sibling loops. Such values will have LCSSA phis of their own in the
95373471bf0Spatrick // common parent loop.)
95473471bf0Spatrick return true;
95573471bf0Spatrick }
95673471bf0Spatrick
95709467b48Spatrick AnalysisKey LoopAnalysis::Key;
95809467b48Spatrick
run(Function & F,FunctionAnalysisManager & AM)95909467b48Spatrick LoopInfo LoopAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
96009467b48Spatrick // FIXME: Currently we create a LoopInfo from scratch for every function.
96109467b48Spatrick // This may prove to be too wasteful due to deallocating and re-allocating
96209467b48Spatrick // memory each time for the underlying map and vector datastructures. At some
96309467b48Spatrick // point it may prove worthwhile to use a freelist and recycle LoopInfo
96409467b48Spatrick // objects. I don't want to add that kind of complexity until the scope of
96509467b48Spatrick // the problem is better understood.
96609467b48Spatrick LoopInfo LI;
96709467b48Spatrick LI.analyze(AM.getResult<DominatorTreeAnalysis>(F));
96809467b48Spatrick return LI;
96909467b48Spatrick }
97009467b48Spatrick
run(Function & F,FunctionAnalysisManager & AM)97109467b48Spatrick PreservedAnalyses LoopPrinterPass::run(Function &F,
97209467b48Spatrick FunctionAnalysisManager &AM) {
97309467b48Spatrick AM.getResult<LoopAnalysis>(F).print(OS);
97409467b48Spatrick return PreservedAnalyses::all();
97509467b48Spatrick }
97609467b48Spatrick
printLoop(Loop & L,raw_ostream & OS,const std::string & Banner)97709467b48Spatrick void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
97809467b48Spatrick
97909467b48Spatrick if (forcePrintModuleIR()) {
98009467b48Spatrick // handling -print-module-scope
98109467b48Spatrick OS << Banner << " (loop: ";
98209467b48Spatrick L.getHeader()->printAsOperand(OS, false);
98309467b48Spatrick OS << ")\n";
98409467b48Spatrick
98509467b48Spatrick // printing whole module
98609467b48Spatrick OS << *L.getHeader()->getModule();
98709467b48Spatrick return;
98809467b48Spatrick }
98909467b48Spatrick
99009467b48Spatrick OS << Banner;
99109467b48Spatrick
99209467b48Spatrick auto *PreHeader = L.getLoopPreheader();
99309467b48Spatrick if (PreHeader) {
99409467b48Spatrick OS << "\n; Preheader:";
99509467b48Spatrick PreHeader->print(OS);
99609467b48Spatrick OS << "\n; Loop:";
99709467b48Spatrick }
99809467b48Spatrick
99909467b48Spatrick for (auto *Block : L.blocks())
100009467b48Spatrick if (Block)
100109467b48Spatrick Block->print(OS);
100209467b48Spatrick else
100309467b48Spatrick OS << "Printing <null> block";
100409467b48Spatrick
100509467b48Spatrick SmallVector<BasicBlock *, 8> ExitBlocks;
100609467b48Spatrick L.getExitBlocks(ExitBlocks);
100709467b48Spatrick if (!ExitBlocks.empty()) {
100809467b48Spatrick OS << "\n; Exit blocks";
100909467b48Spatrick for (auto *Block : ExitBlocks)
101009467b48Spatrick if (Block)
101109467b48Spatrick Block->print(OS);
101209467b48Spatrick else
101309467b48Spatrick OS << "Printing <null> block";
101409467b48Spatrick }
101509467b48Spatrick }
101609467b48Spatrick
findOptionMDForLoopID(MDNode * LoopID,StringRef Name)101709467b48Spatrick MDNode *llvm::findOptionMDForLoopID(MDNode *LoopID, StringRef Name) {
101809467b48Spatrick // No loop metadata node, no loop properties.
101909467b48Spatrick if (!LoopID)
102009467b48Spatrick return nullptr;
102109467b48Spatrick
102209467b48Spatrick // First operand should refer to the metadata node itself, for legacy reasons.
102309467b48Spatrick assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
102409467b48Spatrick assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
102509467b48Spatrick
102609467b48Spatrick // Iterate over the metdata node operands and look for MDString metadata.
102709467b48Spatrick for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
102809467b48Spatrick MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
102909467b48Spatrick if (!MD || MD->getNumOperands() < 1)
103009467b48Spatrick continue;
103109467b48Spatrick MDString *S = dyn_cast<MDString>(MD->getOperand(0));
103209467b48Spatrick if (!S)
103309467b48Spatrick continue;
103409467b48Spatrick // Return the operand node if MDString holds expected metadata.
103509467b48Spatrick if (Name.equals(S->getString()))
103609467b48Spatrick return MD;
103709467b48Spatrick }
103809467b48Spatrick
103909467b48Spatrick // Loop property not found.
104009467b48Spatrick return nullptr;
104109467b48Spatrick }
104209467b48Spatrick
findOptionMDForLoop(const Loop * TheLoop,StringRef Name)104309467b48Spatrick MDNode *llvm::findOptionMDForLoop(const Loop *TheLoop, StringRef Name) {
104409467b48Spatrick return findOptionMDForLoopID(TheLoop->getLoopID(), Name);
104509467b48Spatrick }
104609467b48Spatrick
104773471bf0Spatrick /// Find string metadata for loop
104873471bf0Spatrick ///
104973471bf0Spatrick /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
105073471bf0Spatrick /// operand or null otherwise. If the string metadata is not found return
105173471bf0Spatrick /// Optional's not-a-value.
1052*d415bd75Srobert std::optional<const MDOperand *>
findStringMetadataForLoop(const Loop * TheLoop,StringRef Name)1053*d415bd75Srobert llvm::findStringMetadataForLoop(const Loop *TheLoop, StringRef Name) {
105473471bf0Spatrick MDNode *MD = findOptionMDForLoop(TheLoop, Name);
105573471bf0Spatrick if (!MD)
1056*d415bd75Srobert return std::nullopt;
105773471bf0Spatrick switch (MD->getNumOperands()) {
105873471bf0Spatrick case 1:
105973471bf0Spatrick return nullptr;
106073471bf0Spatrick case 2:
106173471bf0Spatrick return &MD->getOperand(1);
106273471bf0Spatrick default:
106373471bf0Spatrick llvm_unreachable("loop metadata has 0 or 1 operand");
106473471bf0Spatrick }
106573471bf0Spatrick }
106673471bf0Spatrick
getOptionalBoolLoopAttribute(const Loop * TheLoop,StringRef Name)1067*d415bd75Srobert std::optional<bool> llvm::getOptionalBoolLoopAttribute(const Loop *TheLoop,
106873471bf0Spatrick StringRef Name) {
106973471bf0Spatrick MDNode *MD = findOptionMDForLoop(TheLoop, Name);
107073471bf0Spatrick if (!MD)
1071*d415bd75Srobert return std::nullopt;
107273471bf0Spatrick switch (MD->getNumOperands()) {
107373471bf0Spatrick case 1:
107473471bf0Spatrick // When the value is absent it is interpreted as 'attribute set'.
107573471bf0Spatrick return true;
107673471bf0Spatrick case 2:
107773471bf0Spatrick if (ConstantInt *IntMD =
107873471bf0Spatrick mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get()))
107973471bf0Spatrick return IntMD->getZExtValue();
108073471bf0Spatrick return true;
108173471bf0Spatrick }
108273471bf0Spatrick llvm_unreachable("unexpected number of options");
108373471bf0Spatrick }
108473471bf0Spatrick
getBooleanLoopAttribute(const Loop * TheLoop,StringRef Name)108573471bf0Spatrick bool llvm::getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name) {
1086*d415bd75Srobert return getOptionalBoolLoopAttribute(TheLoop, Name).value_or(false);
108773471bf0Spatrick }
108873471bf0Spatrick
getOptionalIntLoopAttribute(const Loop * TheLoop,StringRef Name)1089*d415bd75Srobert std::optional<int> llvm::getOptionalIntLoopAttribute(const Loop *TheLoop,
109073471bf0Spatrick StringRef Name) {
109173471bf0Spatrick const MDOperand *AttrMD =
1092*d415bd75Srobert findStringMetadataForLoop(TheLoop, Name).value_or(nullptr);
109373471bf0Spatrick if (!AttrMD)
1094*d415bd75Srobert return std::nullopt;
109573471bf0Spatrick
109673471bf0Spatrick ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get());
109773471bf0Spatrick if (!IntMD)
1098*d415bd75Srobert return std::nullopt;
109973471bf0Spatrick
110073471bf0Spatrick return IntMD->getSExtValue();
110173471bf0Spatrick }
110273471bf0Spatrick
getIntLoopAttribute(const Loop * TheLoop,StringRef Name,int Default)1103*d415bd75Srobert int llvm::getIntLoopAttribute(const Loop *TheLoop, StringRef Name,
1104*d415bd75Srobert int Default) {
1105*d415bd75Srobert return getOptionalIntLoopAttribute(TheLoop, Name).value_or(Default);
1106*d415bd75Srobert }
1107*d415bd75Srobert
isFinite(const Loop * L)1108*d415bd75Srobert bool llvm::isFinite(const Loop *L) {
1109*d415bd75Srobert return L->getHeader()->getParent()->willReturn();
1110*d415bd75Srobert }
1111*d415bd75Srobert
111273471bf0Spatrick static const char *LLVMLoopMustProgress = "llvm.loop.mustprogress";
111373471bf0Spatrick
hasMustProgress(const Loop * L)111473471bf0Spatrick bool llvm::hasMustProgress(const Loop *L) {
111573471bf0Spatrick return getBooleanLoopAttribute(L, LLVMLoopMustProgress);
111673471bf0Spatrick }
111773471bf0Spatrick
isMustProgress(const Loop * L)111873471bf0Spatrick bool llvm::isMustProgress(const Loop *L) {
111973471bf0Spatrick return L->getHeader()->getParent()->mustProgress() || hasMustProgress(L);
112073471bf0Spatrick }
112173471bf0Spatrick
isValidAsAccessGroup(MDNode * Node)112209467b48Spatrick bool llvm::isValidAsAccessGroup(MDNode *Node) {
112309467b48Spatrick return Node->getNumOperands() == 0 && Node->isDistinct();
112409467b48Spatrick }
112509467b48Spatrick
makePostTransformationMetadata(LLVMContext & Context,MDNode * OrigLoopID,ArrayRef<StringRef> RemovePrefixes,ArrayRef<MDNode * > AddAttrs)112609467b48Spatrick MDNode *llvm::makePostTransformationMetadata(LLVMContext &Context,
112709467b48Spatrick MDNode *OrigLoopID,
112809467b48Spatrick ArrayRef<StringRef> RemovePrefixes,
112909467b48Spatrick ArrayRef<MDNode *> AddAttrs) {
113009467b48Spatrick // First remove any existing loop metadata related to this transformation.
113109467b48Spatrick SmallVector<Metadata *, 4> MDs;
113209467b48Spatrick
113309467b48Spatrick // Reserve first location for self reference to the LoopID metadata node.
113473471bf0Spatrick MDs.push_back(nullptr);
113509467b48Spatrick
113609467b48Spatrick // Remove metadata for the transformation that has been applied or that became
113709467b48Spatrick // outdated.
113809467b48Spatrick if (OrigLoopID) {
113909467b48Spatrick for (unsigned i = 1, ie = OrigLoopID->getNumOperands(); i < ie; ++i) {
114009467b48Spatrick bool IsVectorMetadata = false;
114109467b48Spatrick Metadata *Op = OrigLoopID->getOperand(i);
114209467b48Spatrick if (MDNode *MD = dyn_cast<MDNode>(Op)) {
114309467b48Spatrick const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
114409467b48Spatrick if (S)
114509467b48Spatrick IsVectorMetadata =
114609467b48Spatrick llvm::any_of(RemovePrefixes, [S](StringRef Prefix) -> bool {
114709467b48Spatrick return S->getString().startswith(Prefix);
114809467b48Spatrick });
114909467b48Spatrick }
115009467b48Spatrick if (!IsVectorMetadata)
115109467b48Spatrick MDs.push_back(Op);
115209467b48Spatrick }
115309467b48Spatrick }
115409467b48Spatrick
115509467b48Spatrick // Add metadata to avoid reapplying a transformation, such as
115609467b48Spatrick // llvm.loop.unroll.disable and llvm.loop.isvectorized.
115709467b48Spatrick MDs.append(AddAttrs.begin(), AddAttrs.end());
115809467b48Spatrick
115909467b48Spatrick MDNode *NewLoopID = MDNode::getDistinct(Context, MDs);
116009467b48Spatrick // Replace the temporary node with a self-reference.
116109467b48Spatrick NewLoopID->replaceOperandWith(0, NewLoopID);
116209467b48Spatrick return NewLoopID;
116309467b48Spatrick }
116409467b48Spatrick
116509467b48Spatrick //===----------------------------------------------------------------------===//
116609467b48Spatrick // LoopInfo implementation
116709467b48Spatrick //
116809467b48Spatrick
LoopInfoWrapperPass()116909467b48Spatrick LoopInfoWrapperPass::LoopInfoWrapperPass() : FunctionPass(ID) {
117009467b48Spatrick initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());
117109467b48Spatrick }
117209467b48Spatrick
117309467b48Spatrick char LoopInfoWrapperPass::ID = 0;
117409467b48Spatrick INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
117509467b48Spatrick true, true)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)117609467b48Spatrick INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
117709467b48Spatrick INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information",
117809467b48Spatrick true, true)
117909467b48Spatrick
118009467b48Spatrick bool LoopInfoWrapperPass::runOnFunction(Function &) {
118109467b48Spatrick releaseMemory();
118209467b48Spatrick LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
118309467b48Spatrick return false;
118409467b48Spatrick }
118509467b48Spatrick
verifyAnalysis() const118609467b48Spatrick void LoopInfoWrapperPass::verifyAnalysis() const {
118709467b48Spatrick // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
118809467b48Spatrick // function each time verifyAnalysis is called is very expensive. The
118909467b48Spatrick // -verify-loop-info option can enable this. In order to perform some
119009467b48Spatrick // checking by default, LoopPass has been taught to call verifyLoop manually
119109467b48Spatrick // during loop pass sequences.
119209467b48Spatrick if (VerifyLoopInfo) {
119309467b48Spatrick auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
119409467b48Spatrick LI.verify(DT);
119509467b48Spatrick }
119609467b48Spatrick }
119709467b48Spatrick
getAnalysisUsage(AnalysisUsage & AU) const119809467b48Spatrick void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
119909467b48Spatrick AU.setPreservesAll();
120009467b48Spatrick AU.addRequiredTransitive<DominatorTreeWrapperPass>();
120109467b48Spatrick }
120209467b48Spatrick
print(raw_ostream & OS,const Module *) const120309467b48Spatrick void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
120409467b48Spatrick LI.print(OS);
120509467b48Spatrick }
120609467b48Spatrick
run(Function & F,FunctionAnalysisManager & AM)120709467b48Spatrick PreservedAnalyses LoopVerifierPass::run(Function &F,
120809467b48Spatrick FunctionAnalysisManager &AM) {
120909467b48Spatrick LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
121009467b48Spatrick auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
121109467b48Spatrick LI.verify(DT);
121209467b48Spatrick return PreservedAnalyses::all();
121309467b48Spatrick }
121409467b48Spatrick
121509467b48Spatrick //===----------------------------------------------------------------------===//
121609467b48Spatrick // LoopBlocksDFS implementation
121709467b48Spatrick //
121809467b48Spatrick
121909467b48Spatrick /// Traverse the loop blocks and store the DFS result.
122009467b48Spatrick /// Useful for clients that just want the final DFS result and don't need to
122109467b48Spatrick /// visit blocks during the initial traversal.
perform(LoopInfo * LI)122209467b48Spatrick void LoopBlocksDFS::perform(LoopInfo *LI) {
122309467b48Spatrick LoopBlocksTraversal Traversal(*this, LI);
122409467b48Spatrick for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
122509467b48Spatrick POE = Traversal.end();
122609467b48Spatrick POI != POE; ++POI)
122709467b48Spatrick ;
122809467b48Spatrick }
1229