xref: /openbsd-src/gnu/llvm/llvm/lib/Analysis/LoopInfo.cpp (revision d415bd752c734aee168c4ee86ff32e8cc249eb16)
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