/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h

Bug Summary

File:	include/llvm/Analysis/LoopInfo.h
Warning:	line 473, column 57 Moved-from object 'Start' is moved

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name LoopInfo.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-9/lib/clang/9.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-9~svn359999/build-llvm/lib/Analysis -I /build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis -I /build/llvm-toolchain-snapshot-9~svn359999/build-llvm/include -I /build/llvm-toolchain-snapshot-9~svn359999/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/9.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-9/lib/clang/9.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-9~svn359999/build-llvm/lib/Analysis -fdebug-prefix-map=/build/llvm-toolchain-snapshot-9~svn359999=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2019-05-06-051613-19774-1 -x c++ /build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp -faddrsig

/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp

→

1//===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines the LoopInfo class that is used to identify natural loops
10// and determine the loop depth of various nodes of the CFG.  Note that the
11// loops identified may actually be several natural loops that share the same
12// header node... not just a single natural loop.
13//
14//===----------------------------------------------------------------------===//

16#include "llvm/Analysis/LoopInfo.h"
17#include "llvm/ADT/DepthFirstIterator.h"
18#include "llvm/ADT/ScopeExit.h"
19#include "llvm/ADT/SmallPtrSet.h"
20#include "llvm/Analysis/LoopInfoImpl.h"
21#include "llvm/Analysis/LoopIterator.h"
22#include "llvm/Analysis/ValueTracking.h"
23#include "llvm/Config/llvm-config.h"
24#include "llvm/IR/CFG.h"
25#include "llvm/IR/Constants.h"
26#include "llvm/IR/DebugLoc.h"
27#include "llvm/IR/Dominators.h"
28#include "llvm/IR/IRPrintingPasses.h"
29#include "llvm/IR/Instructions.h"
30#include "llvm/IR/LLVMContext.h"
31#include "llvm/IR/Metadata.h"
32#include "llvm/IR/PassManager.h"
33#include "llvm/Support/CommandLine.h"
34#include "llvm/Support/Debug.h"
35#include "llvm/Support/raw_ostream.h"
36#include <algorithm>
37using namespace llvm;

39// Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
40template class llvm::LoopBase<BasicBlock, Loop>;
41template class llvm::LoopInfoBase<BasicBlock, Loop>;

43// Always verify loopinfo if expensive checking is enabled.
44#ifdef EXPENSIVE_CHECKS
45bool llvm::VerifyLoopInfo = true;
46#else
47bool llvm::VerifyLoopInfo = false;
48#endif
49static cl::opt<bool, true>
  VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
                  cl::Hidden, cl::desc("Verify loop info (time consuming)"));

53//===----------------------------------------------------------------------===//
54// Loop implementation
55//

57bool Loop::isLoopInvariant(const Value *V) const {
if (const Instruction *I = dyn_cast<Instruction>(V))
  return !contains(I);
return true; // All non-instructions are loop invariant
61}

63bool Loop::hasLoopInvariantOperands(const Instruction *I) const {
return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
65}

67bool Loop::makeLoopInvariant(Value *V, bool &Changed,
                           Instruction *InsertPt) const {
if (Instruction *I = dyn_cast<Instruction>(V))
  return makeLoopInvariant(I, Changed, InsertPt);
return true; // All non-instructions are loop-invariant.
72}

74bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
                           Instruction *InsertPt) const {
// Test if the value is already loop-invariant.
if (isLoopInvariant(I))
  return true;
if (!isSafeToSpeculativelyExecute(I))
  return false;
if (I->mayReadFromMemory())
  return false;
// EH block instructions are immobile.
if (I->isEHPad())
  return false;
// Determine the insertion point, unless one was given.
if (!InsertPt) {
  BasicBlock *Preheader = getLoopPreheader();
  // Without a preheader, hoisting is not feasible.
  if (!Preheader)
    return false;
  InsertPt = Preheader->getTerminator();
}
// Don't hoist instructions with loop-variant operands.
for (Value *Operand : I->operands())
  if (!makeLoopInvariant(Operand, Changed, InsertPt))
    return false;

// Hoist.
I->moveBefore(InsertPt);

// There is possibility of hoisting this instruction above some arbitrary
// condition. Any metadata defined on it can be control dependent on this
// condition. Conservatively strip it here so that we don't give any wrong
// information to the optimizer.
I->dropUnknownNonDebugMetadata();

Changed = true;
return true;
110}

112bool Loop::getIncomingAndBackEdge(BasicBlock *&Incoming,
                                BasicBlock *&Backedge) const {
BasicBlock *H = getHeader();

Incoming = nullptr;
Backedge = nullptr;
pred_iterator PI = pred_begin(H);
assert(PI != pred_end(H) && "Loop must have at least one backedge!")((PI != pred_end(H) && "Loop must have at least one backedge!"
) ? static_cast<void> (0) : __assert_fail ("PI != pred_end(H) && \"Loop must have at least one backedge!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 119, __PRETTY_FUNCTION__));
Backedge = *PI++;
if (PI == pred_end(H))
  return false; // dead loop
Incoming = *PI++;
if (PI != pred_end(H))
  return false; // multiple backedges?

if (contains(Incoming)) {
  if (contains(Backedge))
    return false;
  std::swap(Incoming, Backedge);
} else if (!contains(Backedge))
  return false;

assert(Incoming && Backedge && "expected non-null incoming and backedges")((Incoming && Backedge && "expected non-null incoming and backedges"
) ? static_cast<void> (0) : __assert_fail ("Incoming && Backedge && \"expected non-null incoming and backedges\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 134, __PRETTY_FUNCTION__));
return true;
136}

138PHINode *Loop::getCanonicalInductionVariable() const {
BasicBlock *H = getHeader();

BasicBlock *Incoming = nullptr, *Backedge = nullptr;
if (!getIncomingAndBackEdge(Incoming, Backedge))
  return nullptr;

// Loop over all of the PHI nodes, looking for a canonical indvar.
for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) {
  PHINode *PN = cast<PHINode>(I);
  if (ConstantInt *CI =
          dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming)))
    if (CI->isZero())
      if (Instruction *Inc =
              dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
        if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(0) == PN)
          if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
            if (CI->isOne())
              return PN;
}
return nullptr;
159}

161// Check that 'BB' doesn't have any uses outside of the 'L'
162static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
                             DominatorTree &DT) {
for (const Instruction &I : BB) {
  // Tokens can't be used in PHI nodes and live-out tokens prevent loop
  // optimizations, so for the purposes of considered LCSSA form, we
  // can ignore them.
  if (I.getType()->isTokenTy())
    continue;

  for (const Use &U : I.uses()) {
    const Instruction *UI = cast<Instruction>(U.getUser());
    const BasicBlock *UserBB = UI->getParent();
    if (const PHINode *P = dyn_cast<PHINode>(UI))
      UserBB = P->getIncomingBlock(U);

    // Check the current block, as a fast-path, before checking whether
    // the use is anywhere in the loop.  Most values are used in the same
    // block they are defined in.  Also, blocks not reachable from the
    // entry are special; uses in them don't need to go through PHIs.
    if (UserBB != &BB && !L.contains(UserBB) &&
        DT.isReachableFromEntry(UserBB))
      return false;
  }
}
return true;
187}

189bool Loop::isLCSSAForm(DominatorTree &DT) const {
// For each block we check that it doesn't have any uses outside of this loop.
return all_of(this->blocks(), [&](const BasicBlock *BB) {
  return isBlockInLCSSAForm(*this, *BB, DT);
});
194}

196bool Loop::isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const {
// For each block we check that it doesn't have any uses outside of its
// innermost loop. This process will transitively guarantee that the current
// loop and all of the nested loops are in LCSSA form.
return all_of(this->blocks(), [&](const BasicBlock *BB) {
  return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT);
});
203}

205bool Loop::isLoopSimplifyForm() const {
// Normal-form loops have a preheader, a single backedge, and all of their
// exits have all their predecessors inside the loop.
return getLoopPreheader() && getLoopLatch() && hasDedicatedExits();
209}

211// Routines that reform the loop CFG and split edges often fail on indirectbr.
212bool Loop::isSafeToClone() const {
// Return false if any loop blocks contain indirectbrs, or there are any calls
// to noduplicate functions.
for (BasicBlock *BB : this->blocks()) {
  if (isa<IndirectBrInst>(BB->getTerminator()))
    return false;

  for (Instruction &I : *BB)
    if (auto CS = CallSite(&I))
      if (CS.cannotDuplicate())
        return false;
}
return true;
225}

227MDNode *Loop::getLoopID() const {
MDNode *LoopID = nullptr;

// Go through the latch blocks and check the terminator for the metadata.
SmallVector<BasicBlock *, 4> LatchesBlocks;
getLoopLatches(LatchesBlocks);
for (BasicBlock *BB : LatchesBlocks) {
  Instruction *TI = BB->getTerminator();
  MDNode *MD = TI->getMetadata(LLVMContext::MD_loop);

  if (!MD)
    return nullptr;

  if (!LoopID)
    LoopID = MD;
  else if (MD != LoopID)
    return nullptr;
}
if (!LoopID || LoopID->getNumOperands() == 0 ||
    LoopID->getOperand(0) != LoopID)
  return nullptr;
return LoopID;
249}

251void Loop::setLoopID(MDNode *LoopID) const {
assert((!LoopID || LoopID->getNumOperands() > 0) &&(((!LoopID || LoopID->getNumOperands() > 0) && "Loop ID needs at least one operand"
) ? static_cast<void> (0) : __assert_fail ("(!LoopID || LoopID->getNumOperands() > 0) && \"Loop ID needs at least one operand\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 253, __PRETTY_FUNCTION__))
       "Loop ID needs at least one operand")(((!LoopID || LoopID->getNumOperands() > 0) && "Loop ID needs at least one operand"
) ? static_cast<void> (0) : __assert_fail ("(!LoopID || LoopID->getNumOperands() > 0) && \"Loop ID needs at least one operand\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 253, __PRETTY_FUNCTION__));
assert((!LoopID || LoopID->getOperand(0) == LoopID) &&(((!LoopID || LoopID->getOperand(0) == LoopID) && "Loop ID should refer to itself"
) ? static_cast<void> (0) : __assert_fail ("(!LoopID || LoopID->getOperand(0) == LoopID) && \"Loop ID should refer to itself\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 255, __PRETTY_FUNCTION__))
       "Loop ID should refer to itself")(((!LoopID || LoopID->getOperand(0) == LoopID) && "Loop ID should refer to itself"
) ? static_cast<void> (0) : __assert_fail ("(!LoopID || LoopID->getOperand(0) == LoopID) && \"Loop ID should refer to itself\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 255, __PRETTY_FUNCTION__));

SmallVector<BasicBlock *, 4> LoopLatches;
getLoopLatches(LoopLatches);
for (BasicBlock *BB : LoopLatches)
  BB->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
261}

263void Loop::setLoopAlreadyUnrolled() {
LLVMContext &Context = getHeader()->getContext();

MDNode *DisableUnrollMD =
    MDNode::get(Context, MDString::get(Context, "llvm.loop.unroll.disable"));
MDNode *LoopID = getLoopID();
MDNode *NewLoopID = makePostTransformationMetadata(
    Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD});
setLoopID(NewLoopID);
272}

274bool Loop::isAnnotatedParallel() const {
MDNode *DesiredLoopIdMetadata = getLoopID();

if (!DesiredLoopIdMetadata)
  return false;

MDNode *ParallelAccesses =
    findOptionMDForLoop(this, "llvm.loop.parallel_accesses");
SmallPtrSet<MDNode *, 4>
    ParallelAccessGroups; // For scalable 'contains' check.
if (ParallelAccesses) {
  for (const MDOperand &MD : drop_begin(ParallelAccesses->operands(), 1)) {
    MDNode *AccGroup = cast<MDNode>(MD.get());
    assert(isValidAsAccessGroup(AccGroup) &&((isValidAsAccessGroup(AccGroup) && "List item must be an access group"
) ? static_cast<void> (0) : __assert_fail ("isValidAsAccessGroup(AccGroup) && \"List item must be an access group\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 288, __PRETTY_FUNCTION__))
           "List item must be an access group")((isValidAsAccessGroup(AccGroup) && "List item must be an access group"
) ? static_cast<void> (0) : __assert_fail ("isValidAsAccessGroup(AccGroup) && \"List item must be an access group\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 288, __PRETTY_FUNCTION__));
    ParallelAccessGroups.insert(AccGroup);
  }
}

// The loop branch contains the parallel loop metadata. In order to ensure
// that any parallel-loop-unaware optimization pass hasn't added loop-carried
// dependencies (thus converted the loop back to a sequential loop), check
// that all the memory instructions in the loop belong to an access group that
// is parallel to this loop.
for (BasicBlock *BB : this->blocks()) {
  for (Instruction &I : *BB) {
    if (!I.mayReadOrWriteMemory())
      continue;

    if (MDNode *AccessGroup = I.getMetadata(LLVMContext::MD_access_group)) {
      auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool {
        if (AG->getNumOperands() == 0) {
          assert(isValidAsAccessGroup(AG) && "Item must be an access group")((isValidAsAccessGroup(AG) && "Item must be an access group"
) ? static_cast<void> (0) : __assert_fail ("isValidAsAccessGroup(AG) && \"Item must be an access group\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 306, __PRETTY_FUNCTION__));
          return ParallelAccessGroups.count(AG);
        }

        for (const MDOperand &AccessListItem : AG->operands()) {
          MDNode *AccGroup = cast<MDNode>(AccessListItem.get());
          assert(isValidAsAccessGroup(AccGroup) &&((isValidAsAccessGroup(AccGroup) && "List item must be an access group"
) ? static_cast<void> (0) : __assert_fail ("isValidAsAccessGroup(AccGroup) && \"List item must be an access group\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 313, __PRETTY_FUNCTION__))
                 "List item must be an access group")((isValidAsAccessGroup(AccGroup) && "List item must be an access group"
) ? static_cast<void> (0) : __assert_fail ("isValidAsAccessGroup(AccGroup) && \"List item must be an access group\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 313, __PRETTY_FUNCTION__));
          if (ParallelAccessGroups.count(AccGroup))
            return true;
        }
        return false;
      };

      if (ContainsAccessGroup(AccessGroup))
        continue;
    }

    // The memory instruction can refer to the loop identifier metadata
    // directly or indirectly through another list metadata (in case of
    // nested parallel loops). The loop identifier metadata refers to
    // itself so we can check both cases with the same routine.
    MDNode *LoopIdMD =
        I.getMetadata(LLVMContext::MD_mem_parallel_loop_access);

    if (!LoopIdMD)
      return false;

    bool LoopIdMDFound = false;
    for (const MDOperand &MDOp : LoopIdMD->operands()) {
      if (MDOp == DesiredLoopIdMetadata) {
        LoopIdMDFound = true;
        break;
      }
    }

    if (!LoopIdMDFound)
      return false;
  }
}
return true;
347}

349DebugLoc Loop::getStartLoc() const { return getLocRange().getStart(); }
1
Calling 'Loop::getLocRange'→

351Loop::LocRange Loop::getLocRange() const {
// If we have a debug location in the loop ID, then use it.
if (MDNode *LoopID = getLoopID()) {
2
←
Assuming 'LoopID' is null→
3
←
Taking false branch→
  DebugLoc Start;
  // We use the first DebugLoc in the header as the start location of the loop
  // and if there is a second DebugLoc in the header we use it as end location
  // of the loop.
  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
    if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) {
      if (!Start)
        Start = DebugLoc(L);
      else
        return LocRange(Start, DebugLoc(L));
    }
  }

  if (Start)
    return LocRange(Start);
}

// Try the pre-header first.
if (BasicBlock *PHeadBB = getLoopPreheader())
4
←
Assuming 'PHeadBB' is null→
5
←
Taking false branch→
  if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
    return LocRange(DL);

// If we have no pre-header or there are no instructions with debug
// info in it, try the header.
if (BasicBlock *HeadBB = getHeader())
6
←
Assuming 'HeadBB' is non-null→
7
←
Taking true branch→
  return LocRange(HeadBB->getTerminator()->getDebugLoc());
8
←
Calling constructor for 'LocRange'→

return LocRange();
382}

384#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
385LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void Loop::dump() const { print(dbgs()); }

387LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void Loop::dumpVerbose() const {
print(dbgs(), /*Depth=*/0, /*Verbose=*/true);
389}
390#endif

392//===----------------------------------------------------------------------===//
393// UnloopUpdater implementation
394//

396namespace {
397/// Find the new parent loop for all blocks within the "unloop" whose last
398/// backedges has just been removed.
399class UnloopUpdater {
Loop &Unloop;
LoopInfo *LI;

LoopBlocksDFS DFS;

// Map unloop's immediate subloops to their nearest reachable parents. Nested
// loops within these subloops will not change parents. However, an immediate
// subloop's new parent will be the nearest loop reachable from either its own
// exits *or* any of its nested loop's exits.
DenseMap<Loop *, Loop *> SubloopParents;

// Flag the presence of an irreducible backedge whose destination is a block
// directly contained by the original unloop.
bool FoundIB;

415public:
UnloopUpdater(Loop *UL, LoopInfo *LInfo)
    : Unloop(*UL), LI(LInfo), DFS(UL), FoundIB(false) {}

void updateBlockParents();

void removeBlocksFromAncestors();

void updateSubloopParents();

425protected:
Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
427};
428} // end anonymous namespace

430/// Update the parent loop for all blocks that are directly contained within the
431/// original "unloop".
432void UnloopUpdater::updateBlockParents() {
if (Unloop.getNumBlocks()) {
  // Perform a post order CFG traversal of all blocks within this loop,
  // propagating the nearest loop from successors to predecessors.
  LoopBlocksTraversal Traversal(DFS, LI);
  for (BasicBlock *POI : Traversal) {

    Loop *L = LI->getLoopFor(POI);
    Loop *NL = getNearestLoop(POI, L);

    if (NL != L) {
      // For reducible loops, NL is now an ancestor of Unloop.
      assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&(((NL != &Unloop && (!NL || NL->contains(&
Unloop))) && "uninitialized successor") ? static_cast
<void> (0) : __assert_fail ("(NL != &Unloop && (!NL || NL->contains(&Unloop))) && \"uninitialized successor\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 445, __PRETTY_FUNCTION__))
             "uninitialized successor")(((NL != &Unloop && (!NL || NL->contains(&
Unloop))) && "uninitialized successor") ? static_cast
<void> (0) : __assert_fail ("(NL != &Unloop && (!NL || NL->contains(&Unloop))) && \"uninitialized successor\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 445, __PRETTY_FUNCTION__));
      LI->changeLoopFor(POI, NL);
    } else {
      // Or the current block is part of a subloop, in which case its parent
      // is unchanged.
      assert((FoundIB || Unloop.contains(L)) && "uninitialized successor")(((FoundIB || Unloop.contains(L)) && "uninitialized successor"
) ? static_cast<void> (0) : __assert_fail ("(FoundIB || Unloop.contains(L)) && \"uninitialized successor\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 450, __PRETTY_FUNCTION__));
    }
  }
}
// Each irreducible loop within the unloop induces a round of iteration using
// the DFS result cached by Traversal.
bool Changed = FoundIB;
for (unsigned NIters = 0; Changed; ++NIters) {
  assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm")((NIters < Unloop.getNumBlocks() && "runaway iterative algorithm"
) ? static_cast<void> (0) : __assert_fail ("NIters < Unloop.getNumBlocks() && \"runaway iterative algorithm\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 458, __PRETTY_FUNCTION__));

  // Iterate over the postorder list of blocks, propagating the nearest loop
  // from successors to predecessors as before.
  Changed = false;
  for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
                                 POE = DFS.endPostorder();
       POI != POE; ++POI) {

    Loop *L = LI->getLoopFor(*POI);
    Loop *NL = getNearestLoop(*POI, L);
    if (NL != L) {
      assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&((NL != &Unloop && (!NL || NL->contains(&Unloop
)) && "uninitialized successor") ? static_cast<void
> (0) : __assert_fail ("NL != &Unloop && (!NL || NL->contains(&Unloop)) && \"uninitialized successor\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 471, __PRETTY_FUNCTION__))
             "uninitialized successor")((NL != &Unloop && (!NL || NL->contains(&Unloop
)) && "uninitialized successor") ? static_cast<void
> (0) : __assert_fail ("NL != &Unloop && (!NL || NL->contains(&Unloop)) && \"uninitialized successor\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 471, __PRETTY_FUNCTION__));
      LI->changeLoopFor(*POI, NL);
      Changed = true;
    }
  }
}
477}

479/// Remove unloop's blocks from all ancestors below their new parents.
480void UnloopUpdater::removeBlocksFromAncestors() {
// Remove all unloop's blocks (including those in nested subloops) from
// ancestors below the new parent loop.
for (Loop::block_iterator BI = Unloop.block_begin(), BE = Unloop.block_end();
     BI != BE; ++BI) {
  Loop *OuterParent = LI->getLoopFor(*BI);
  if (Unloop.contains(OuterParent)) {
    while (OuterParent->getParentLoop() != &Unloop)
      OuterParent = OuterParent->getParentLoop();
    OuterParent = SubloopParents[OuterParent];
  }
  // Remove blocks from former Ancestors except Unloop itself which will be
  // deleted.
  for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
       OldParent = OldParent->getParentLoop()) {
    assert(OldParent && "new loop is not an ancestor of the original")((OldParent && "new loop is not an ancestor of the original"
) ? static_cast<void> (0) : __assert_fail ("OldParent && \"new loop is not an ancestor of the original\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 495, __PRETTY_FUNCTION__));
    OldParent->removeBlockFromLoop(*BI);
  }
}
499}

501/// Update the parent loop for all subloops directly nested within unloop.
502void UnloopUpdater::updateSubloopParents() {
while (!Unloop.empty()) {
  Loop *Subloop = *std::prev(Unloop.end());
  Unloop.removeChildLoop(std::prev(Unloop.end()));

  assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop")((SubloopParents.count(Subloop) && "DFS failed to visit subloop"
) ? static_cast<void> (0) : __assert_fail ("SubloopParents.count(Subloop) && \"DFS failed to visit subloop\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 507, __PRETTY_FUNCTION__));
  if (Loop *Parent = SubloopParents[Subloop])
    Parent->addChildLoop(Subloop);
  else
    LI->addTopLevelLoop(Subloop);
}
513}

515/// Return the nearest parent loop among this block's successors. If a successor
516/// is a subloop header, consider its parent to be the nearest parent of the
517/// subloop's exits.
518///
519/// For subloop blocks, simply update SubloopParents and return NULL.
520Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {

// Initially for blocks directly contained by Unloop, NearLoop == Unloop and
// is considered uninitialized.
Loop *NearLoop = BBLoop;

Loop *Subloop = nullptr;
if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
  Subloop = NearLoop;
  // Find the subloop ancestor that is directly contained within Unloop.
  while (Subloop->getParentLoop() != &Unloop) {
    Subloop = Subloop->getParentLoop();
    assert(Subloop && "subloop is not an ancestor of the original loop")((Subloop && "subloop is not an ancestor of the original loop"
) ? static_cast<void> (0) : __assert_fail ("Subloop && \"subloop is not an ancestor of the original loop\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 532, __PRETTY_FUNCTION__));
  }
  // Get the current nearest parent of the Subloop exits, initially Unloop.
  NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
}

succ_iterator I = succ_begin(BB), E = succ_end(BB);
if (I == E) {
  assert(!Subloop && "subloop blocks must have a successor")((!Subloop && "subloop blocks must have a successor")
 ? static_cast<void> (0) : __assert_fail ("!Subloop && \"subloop blocks must have a successor\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 540, __PRETTY_FUNCTION__));
  NearLoop = nullptr; // unloop blocks may now exit the function.
}
for (; I != E; ++I) {
  if (*I == BB)
    continue; // self loops are uninteresting

  Loop *L = LI->getLoopFor(*I);
  if (L == &Unloop) {
    // This successor has not been processed. This path must lead to an
    // irreducible backedge.
    assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB")(((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB"
) ? static_cast<void> (0) : __assert_fail ("(FoundIB || !DFS.hasPostorder(*I)) && \"should have seen IB\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 551, __PRETTY_FUNCTION__));
    FoundIB = true;
  }
  if (L != &Unloop && Unloop.contains(L)) {
    // Successor is in a subloop.
    if (Subloop)
      continue; // Branching within subloops. Ignore it.

    // BB branches from the original into a subloop header.
    assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops")((L->getParentLoop() == &Unloop && "cannot skip into nested loops"
) ? static_cast<void> (0) : __assert_fail ("L->getParentLoop() == &Unloop && \"cannot skip into nested loops\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 560, __PRETTY_FUNCTION__));

    // Get the current nearest parent of the Subloop's exits.
    L = SubloopParents[L];
    // L could be Unloop if the only exit was an irreducible backedge.
  }
  if (L == &Unloop) {
    continue;
  }
  // Handle critical edges from Unloop into a sibling loop.
  if (L && !L->contains(&Unloop)) {
    L = L->getParentLoop();
  }
  // Remember the nearest parent loop among successors or subloop exits.
  if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
    NearLoop = L;
}
if (Subloop) {
  SubloopParents[Subloop] = NearLoop;
  return BBLoop;
}
return NearLoop;
582}

584LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }

586bool LoopInfo::invalidate(Function &F, const PreservedAnalyses &PA,
                        FunctionAnalysisManager::Invalidator &) {
// Check whether the analysis, all analyses on functions, or the function's
// CFG have been preserved.
auto PAC = PA.getChecker<LoopAnalysis>();
return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
         PAC.preservedSet<CFGAnalyses>());
593}

595void LoopInfo::erase(Loop *Unloop) {
assert(!Unloop->isInvalid() && "Loop has already been erased!")((!Unloop->isInvalid() && "Loop has already been erased!"
) ? static_cast<void> (0) : __assert_fail ("!Unloop->isInvalid() && \"Loop has already been erased!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 596, __PRETTY_FUNCTION__));

auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); });

// First handle the special case of no parent loop to simplify the algorithm.
if (!Unloop->getParentLoop()) {
  // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
  for (Loop::block_iterator I = Unloop->block_begin(),
                            E = Unloop->block_end();
       I != E; ++I) {

    // Don't reparent blocks in subloops.
    if (getLoopFor(*I) != Unloop)
      continue;

    // Blocks no longer have a parent but are still referenced by Unloop until
    // the Unloop object is deleted.
    changeLoopFor(*I, nullptr);
  }

  // Remove the loop from the top-level LoopInfo object.
  for (iterator I = begin();; ++I) {
    assert(I != end() && "Couldn't find loop")((I != end() && "Couldn't find loop") ? static_cast<
void> (0) : __assert_fail ("I != end() && \"Couldn't find loop\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 618, __PRETTY_FUNCTION__));
    if (*I == Unloop) {
      removeLoop(I);
      break;
    }
  }

  // Move all of the subloops to the top-level.
  while (!Unloop->empty())
    addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));

  return;
}

// Update the parent loop for all blocks within the loop. Blocks within
// subloops will not change parents.
UnloopUpdater Updater(Unloop, this);
Updater.updateBlockParents();

// Remove blocks from former ancestor loops.
Updater.removeBlocksFromAncestors();

// Add direct subloops as children in their new parent loop.
Updater.updateSubloopParents();

// Remove unloop from its parent loop.
Loop *ParentLoop = Unloop->getParentLoop();
for (Loop::iterator I = ParentLoop->begin();; ++I) {
  assert(I != ParentLoop->end() && "Couldn't find loop")((I != ParentLoop->end() && "Couldn't find loop") ?
 static_cast<void> (0) : __assert_fail ("I != ParentLoop->end() && \"Couldn't find loop\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 646, __PRETTY_FUNCTION__));
  if (*I == Unloop) {
    ParentLoop->removeChildLoop(I);
    break;
  }
}
652}

654AnalysisKey LoopAnalysis::Key;

656LoopInfo LoopAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
// FIXME: Currently we create a LoopInfo from scratch for every function.
// This may prove to be too wasteful due to deallocating and re-allocating
// memory each time for the underlying map and vector datastructures. At some
// point it may prove worthwhile to use a freelist and recycle LoopInfo
// objects. I don't want to add that kind of complexity until the scope of
// the problem is better understood.
LoopInfo LI;
LI.analyze(AM.getResult<DominatorTreeAnalysis>(F));
return LI;
666}

668PreservedAnalyses LoopPrinterPass::run(Function &F,
                                     FunctionAnalysisManager &AM) {
AM.getResult<LoopAnalysis>(F).print(OS);
return PreservedAnalyses::all();
672}

674void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {

if (forcePrintModuleIR()) {
  // handling -print-module-scope
  OS << Banner << " (loop: ";
  L.getHeader()->printAsOperand(OS, false);
  OS << ")\n";

  // printing whole module
  OS << *L.getHeader()->getModule();
  return;
}

OS << Banner;

auto *PreHeader = L.getLoopPreheader();
if (PreHeader) {
  OS << "\n; Preheader:";
  PreHeader->print(OS);
  OS << "\n; Loop:";
}

for (auto *Block : L.blocks())
  if (Block)
    Block->print(OS);
  else
    OS << "Printing <null> block";

SmallVector<BasicBlock *, 8> ExitBlocks;
L.getExitBlocks(ExitBlocks);
if (!ExitBlocks.empty()) {
  OS << "\n; Exit blocks";
  for (auto *Block : ExitBlocks)
    if (Block)
      Block->print(OS);
    else
      OS << "Printing <null> block";
}
712}

714MDNode *llvm::findOptionMDForLoopID(MDNode *LoopID, StringRef Name) {
// No loop metadata node, no loop properties.
if (!LoopID)
  return nullptr;

// First operand should refer to the metadata node itself, for legacy reasons.
assert(LoopID->getNumOperands() > 0 && "requires at least one operand")((LoopID->getNumOperands() > 0 && "requires at least one operand"
) ? static_cast<void> (0) : __assert_fail ("LoopID->getNumOperands() > 0 && \"requires at least one operand\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 720, __PRETTY_FUNCTION__));
assert(LoopID->getOperand(0) == LoopID && "invalid loop id")((LoopID->getOperand(0) == LoopID && "invalid loop id"
) ? static_cast<void> (0) : __assert_fail ("LoopID->getOperand(0) == LoopID && \"invalid loop id\""
, "/build/llvm-toolchain-snapshot-9~svn359999/lib/Analysis/LoopInfo.cpp"
, 721, __PRETTY_FUNCTION__));

// Iterate over the metdata node operands and look for MDString metadata.
for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
  MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
  if (!MD || MD->getNumOperands() < 1)
    continue;
  MDString *S = dyn_cast<MDString>(MD->getOperand(0));
  if (!S)
    continue;
  // Return the operand node if MDString holds expected metadata.
  if (Name.equals(S->getString()))
    return MD;
}

// Loop property not found.
return nullptr;
738}

740MDNode *llvm::findOptionMDForLoop(const Loop *TheLoop, StringRef Name) {
return findOptionMDForLoopID(TheLoop->getLoopID(), Name);
742}

744bool llvm::isValidAsAccessGroup(MDNode *Node) {
return Node->getNumOperands() == 0 && Node->isDistinct();
746}

748MDNode *llvm::makePostTransformationMetadata(LLVMContext &Context,
                                           MDNode *OrigLoopID,
                                           ArrayRef<StringRef> RemovePrefixes,
                                           ArrayRef<MDNode *> AddAttrs) {
// First remove any existing loop metadata related to this transformation.
SmallVector<Metadata *, 4> MDs;

// Reserve first location for self reference to the LoopID metadata node.
TempMDTuple TempNode = MDNode::getTemporary(Context, None);
MDs.push_back(TempNode.get());

// Remove metadata for the transformation that has been applied or that became
// outdated.
if (OrigLoopID) {
  for (unsigned i = 1, ie = OrigLoopID->getNumOperands(); i < ie; ++i) {
    bool IsVectorMetadata = false;
    Metadata *Op = OrigLoopID->getOperand(i);
    if (MDNode *MD = dyn_cast<MDNode>(Op)) {
      const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
      if (S)
        IsVectorMetadata =
            llvm::any_of(RemovePrefixes, [S](StringRef Prefix) -> bool {
              return S->getString().startswith(Prefix);
            });
    }
    if (!IsVectorMetadata)
      MDs.push_back(Op);
  }
}

// Add metadata to avoid reapplying a transformation, such as
// llvm.loop.unroll.disable and llvm.loop.isvectorized.
MDs.append(AddAttrs.begin(), AddAttrs.end());

MDNode *NewLoopID = MDNode::getDistinct(Context, MDs);
// Replace the temporary node with a self-reference.
NewLoopID->replaceOperandWith(0, NewLoopID);
return NewLoopID;
786}

788//===----------------------------------------------------------------------===//
789// LoopInfo implementation
790//

792char LoopInfoWrapperPass::ID = 0;
793INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",static void *initializeLoopInfoWrapperPassPassOnce(PassRegistry
 &Registry) {
                    true, true)static void *initializeLoopInfoWrapperPassPassOnce(PassRegistry
 &Registry) {
795INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
796INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information",PassInfo *PI = new PassInfo( "Natural Loop Information", "loops"
, &LoopInfoWrapperPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<LoopInfoWrapperPass>), true, true); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeLoopInfoWrapperPassPassFlag
; void llvm::initializeLoopInfoWrapperPassPass(PassRegistry &
Registry) { llvm::call_once(InitializeLoopInfoWrapperPassPassFlag
, initializeLoopInfoWrapperPassPassOnce, std::ref(Registry));
 }
                  true, true)PassInfo *PI = new PassInfo( "Natural Loop Information", "loops"
, &LoopInfoWrapperPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<LoopInfoWrapperPass>), true, true); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeLoopInfoWrapperPassPassFlag
; void llvm::initializeLoopInfoWrapperPassPass(PassRegistry &
Registry) { llvm::call_once(InitializeLoopInfoWrapperPassPassFlag
, initializeLoopInfoWrapperPassPassOnce, std::ref(Registry));
 }

799bool LoopInfoWrapperPass::runOnFunction(Function &) {
releaseMemory();
LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
return false;
803}

805void LoopInfoWrapperPass::verifyAnalysis() const {
// LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
// function each time verifyAnalysis is called is very expensive. The
// -verify-loop-info option can enable this. In order to perform some
// checking by default, LoopPass has been taught to call verifyLoop manually
// during loop pass sequences.
if (VerifyLoopInfo) {
  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
  LI.verify(DT);
}
815}

817void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<DominatorTreeWrapperPass>();
820}

822void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
LI.print(OS);
824}

826PreservedAnalyses LoopVerifierPass::run(Function &F,
                                      FunctionAnalysisManager &AM) {
LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
LI.verify(DT);
return PreservedAnalyses::all();
832}

834//===----------------------------------------------------------------------===//
835// LoopBlocksDFS implementation
836//

838/// Traverse the loop blocks and store the DFS result.
839/// Useful for clients that just want the final DFS result and don't need to
840/// visit blocks during the initial traversal.
841void LoopBlocksDFS::perform(LoopInfo *LI) {
LoopBlocksTraversal Traversal(*this, LI);
for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
                                      POE = Traversal.end();
     POI != POE; ++POI)
  ;
847}

←

/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h

1//===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator -------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines the LoopInfo class that is used to identify natural loops
10// and determine the loop depth of various nodes of the CFG.  A natural loop
11// has exactly one entry-point, which is called the header. Note that natural
12// loops may actually be several loops that share the same header node.
13//
14// This analysis calculates the nesting structure of loops in a function.  For
15// each natural loop identified, this analysis identifies natural loops
16// contained entirely within the loop and the basic blocks the make up the loop.
17//
18// It can calculate on the fly various bits of information, for example:
19//
20//  * whether there is a preheader for the loop
21//  * the number of back edges to the header
22//  * whether or not a particular block branches out of the loop
23//  * the successor blocks of the loop
24//  * the loop depth
25//  * etc...
26//
27// Note that this analysis specifically identifies *Loops* not cycles or SCCs
28// in the CFG.  There can be strongly connected components in the CFG which
29// this analysis will not recognize and that will not be represented by a Loop
30// instance.  In particular, a Loop might be inside such a non-loop SCC, or a
31// non-loop SCC might contain a sub-SCC which is a Loop.
32//
33//===----------------------------------------------------------------------===//

35#ifndef LLVM_ANALYSIS_LOOPINFO_H
36#define LLVM_ANALYSIS_LOOPINFO_H

38#include "llvm/ADT/DenseMap.h"
39#include "llvm/ADT/DenseSet.h"
40#include "llvm/ADT/GraphTraits.h"
41#include "llvm/ADT/SmallPtrSet.h"
42#include "llvm/ADT/SmallVector.h"
43#include "llvm/IR/CFG.h"
44#include "llvm/IR/Instruction.h"
45#include "llvm/IR/Instructions.h"
46#include "llvm/IR/PassManager.h"
47#include "llvm/Pass.h"
48#include "llvm/Support/Allocator.h"
49#include <algorithm>
50#include <utility>

52namespace llvm {

54class DominatorTree;
55class LoopInfo;
56class Loop;
57class MDNode;
58class PHINode;
59class raw_ostream;
60template <class N, bool IsPostDom> class DominatorTreeBase;
61template <class N, class M> class LoopInfoBase;
62template <class N, class M> class LoopBase;

64//===----------------------------------------------------------------------===//
65/// Instances of this class are used to represent loops that are detected in the
66/// flow graph.
67///
68template <class BlockT, class LoopT> class LoopBase {
LoopT *ParentLoop;
// Loops contained entirely within this one.
std::vector<LoopT *> SubLoops;

// The list of blocks in this loop. First entry is the header node.
std::vector<BlockT *> Blocks;

SmallPtrSet<const BlockT *, 8> DenseBlockSet;

78#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
/// Indicator that this loop is no longer a valid loop.
bool IsInvalid = false;
81#endif

LoopBase(const LoopBase<BlockT, LoopT> &) = delete;
const LoopBase<BlockT, LoopT> &
operator=(const LoopBase<BlockT, LoopT> &) = delete;

87public:
/// Return the nesting level of this loop.  An outer-most loop has depth 1,
/// for consistency with loop depth values used for basic blocks, where depth
/// 0 is used for blocks not inside any loops.
unsigned getLoopDepth() const {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 92, __PRETTY_FUNCTION__));
  unsigned D = 1;
  for (const LoopT *CurLoop = ParentLoop; CurLoop;
       CurLoop = CurLoop->ParentLoop)
    ++D;
  return D;
}
BlockT *getHeader() const { return getBlocks().front(); }
LoopT *getParentLoop() const { return ParentLoop; }

/// This is a raw interface for bypassing addChildLoop.
void setParentLoop(LoopT *L) {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 104, __PRETTY_FUNCTION__));
  ParentLoop = L;
}

/// Return true if the specified loop is contained within in this loop.
bool contains(const LoopT *L) const {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 110, __PRETTY_FUNCTION__));
  if (L == this)
    return true;
  if (!L)
    return false;
  return contains(L->getParentLoop());
}

/// Return true if the specified basic block is in this loop.
bool contains(const BlockT *BB) const {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 120, __PRETTY_FUNCTION__));
  return DenseBlockSet.count(BB);
}

/// Return true if the specified instruction is in this loop.
template <class InstT> bool contains(const InstT *Inst) const {
  return contains(Inst->getParent());
}

/// Return the loops contained entirely within this loop.
const std::vector<LoopT *> &getSubLoops() const {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 131, __PRETTY_FUNCTION__));
  return SubLoops;
}
std::vector<LoopT *> &getSubLoopsVector() {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 135, __PRETTY_FUNCTION__));
  return SubLoops;
}
typedef typename std::vector<LoopT *>::const_iterator iterator;
typedef
    typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator;
iterator begin() const { return getSubLoops().begin(); }
iterator end() const { return getSubLoops().end(); }
reverse_iterator rbegin() const { return getSubLoops().rbegin(); }
reverse_iterator rend() const { return getSubLoops().rend(); }
bool empty() const { return getSubLoops().empty(); }

/// Get a list of the basic blocks which make up this loop.
ArrayRef<BlockT *> getBlocks() const {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 149, __PRETTY_FUNCTION__));
  return Blocks;
}
typedef typename ArrayRef<BlockT *>::const_iterator block_iterator;
block_iterator block_begin() const { return getBlocks().begin(); }
block_iterator block_end() const { return getBlocks().end(); }
inline iterator_range<block_iterator> blocks() const {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 156, __PRETTY_FUNCTION__));
  return make_range(block_begin(), block_end());
}

/// Get the number of blocks in this loop in constant time.
/// Invalidate the loop, indicating that it is no longer a loop.
unsigned getNumBlocks() const {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 163, __PRETTY_FUNCTION__));
  return Blocks.size();
}

/// Return a direct, mutable handle to the blocks vector so that we can
/// mutate it efficiently with techniques like `std::remove`.
std::vector<BlockT *> &getBlocksVector() {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 170, __PRETTY_FUNCTION__));
  return Blocks;
}
/// Return a direct, mutable handle to the blocks set so that we can
/// mutate it efficiently.
SmallPtrSetImpl<const BlockT *> &getBlocksSet() {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 176, __PRETTY_FUNCTION__));
  return DenseBlockSet;
}

/// Return a direct, immutable handle to the blocks set.
const SmallPtrSetImpl<const BlockT *> &getBlocksSet() const {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 182, __PRETTY_FUNCTION__));
  return DenseBlockSet;
}

/// Return true if this loop is no longer valid.  The only valid use of this
/// helper is "assert(L.isInvalid())" or equivalent, since IsInvalid is set to
/// true by the destructor.  In other words, if this accessor returns true,
/// the caller has already triggered UB by calling this accessor; and so it
/// can only be called in a context where a return value of true indicates a
/// programmer error.
bool isInvalid() const {
193#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
  return IsInvalid;
195#else
  return false;
197#endif
}

/// True if terminator in the block can branch to another block that is
/// outside of the current loop.
bool isLoopExiting(const BlockT *BB) const {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 203, __PRETTY_FUNCTION__));
  for (const auto &Succ : children<const BlockT *>(BB)) {
    if (!contains(Succ))
      return true;
  }
  return false;
}

/// Returns true if \p BB is a loop-latch.
/// A latch block is a block that contains a branch back to the header.
/// This function is useful when there are multiple latches in a loop
/// because \fn getLoopLatch will return nullptr in that case.
bool isLoopLatch(const BlockT *BB) const {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 216, __PRETTY_FUNCTION__));
  assert(contains(BB) && "block does not belong to the loop")((contains(BB) && "block does not belong to the loop"
) ? static_cast<void> (0) : __assert_fail ("contains(BB) && \"block does not belong to the loop\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 217, __PRETTY_FUNCTION__));

  BlockT *Header = getHeader();
  auto PredBegin = GraphTraits<Inverse<BlockT *>>::child_begin(Header);
  auto PredEnd = GraphTraits<Inverse<BlockT *>>::child_end(Header);
  return std::find(PredBegin, PredEnd, BB) != PredEnd;
}

/// Calculate the number of back edges to the loop header.
unsigned getNumBackEdges() const {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 227, __PRETTY_FUNCTION__));
  unsigned NumBackEdges = 0;
  BlockT *H = getHeader();

  for (const auto Pred : children<Inverse<BlockT *>>(H))
    if (contains(Pred))
      ++NumBackEdges;

  return NumBackEdges;
}

//===--------------------------------------------------------------------===//
// APIs for simple analysis of the loop.
//
// Note that all of these methods can fail on general loops (ie, there may not
// be a preheader, etc).  For best success, the loop simplification and
// induction variable canonicalization pass should be used to normalize loops
// for easy analysis.  These methods assume canonical loops.

/// Return all blocks inside the loop that have successors outside of the
/// loop. These are the blocks _inside of the current loop_ which branch out.
/// The returned list is always unique.
void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const;

/// If getExitingBlocks would return exactly one block, return that block.
/// Otherwise return null.
BlockT *getExitingBlock() const;

/// Return all of the successor blocks of this loop. These are the blocks
/// _outside of the current loop_ which are branched to.
void getExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;

/// If getExitBlocks would return exactly one block, return that block.
/// Otherwise return null.
BlockT *getExitBlock() const;

/// Return true if no exit block for the loop has a predecessor that is
/// outside the loop.
bool hasDedicatedExits() const;

/// Return all unique successor blocks of this loop.
/// These are the blocks _outside of the current loop_ which are branched to.
/// This assumes that loop exits are in canonical form, i.e. all exits are
/// dedicated exits.
void getUniqueExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;

/// If getUniqueExitBlocks would return exactly one block, return that block.
/// Otherwise return null.
BlockT *getUniqueExitBlock() const;

/// Edge type.
typedef std::pair<const BlockT *, const BlockT *> Edge;

/// Return all pairs of (_inside_block_,_outside_block_).
void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const;

/// If there is a preheader for this loop, return it. A loop has a preheader
/// if there is only one edge to the header of the loop from outside of the
/// loop. If this is the case, the block branching to the header of the loop
/// is the preheader node.
///
/// This method returns null if there is no preheader for the loop.
BlockT *getLoopPreheader() const;

/// If the given loop's header has exactly one unique predecessor outside the
/// loop, return it. Otherwise return null.
///  This is less strict that the loop "preheader" concept, which requires
/// the predecessor to have exactly one successor.
BlockT *getLoopPredecessor() const;

/// If there is a single latch block for this loop, return it.
/// A latch block is a block that contains a branch back to the header.
BlockT *getLoopLatch() const;

/// Return all loop latch blocks of this loop. A latch block is a block that
/// contains a branch back to the header.
void getLoopLatches(SmallVectorImpl<BlockT *> &LoopLatches) const {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 304, __PRETTY_FUNCTION__));
  BlockT *H = getHeader();
  for (const auto Pred : children<Inverse<BlockT *>>(H))
    if (contains(Pred))
      LoopLatches.push_back(Pred);
}

//===--------------------------------------------------------------------===//
// APIs for updating loop information after changing the CFG
//

/// This method is used by other analyses to update loop information.
/// NewBB is set to be a new member of the current loop.
/// Because of this, it is added as a member of all parent loops, and is added
/// to the specified LoopInfo object as being in the current basic block.  It
/// is not valid to replace the loop header with this method.
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LI);

/// This is used when splitting loops up. It replaces the OldChild entry in
/// our children list with NewChild, and updates the parent pointer of
/// OldChild to be null and the NewChild to be this loop.
/// This updates the loop depth of the new child.
void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild);

/// Add the specified loop to be a child of this loop.
/// This updates the loop depth of the new child.
void addChildLoop(LoopT *NewChild) {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 331, __PRETTY_FUNCTION__));
  assert(!NewChild->ParentLoop && "NewChild already has a parent!")((!NewChild->ParentLoop && "NewChild already has a parent!"
) ? static_cast<void> (0) : __assert_fail ("!NewChild->ParentLoop && \"NewChild already has a parent!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 332, __PRETTY_FUNCTION__));
  NewChild->ParentLoop = static_cast<LoopT *>(this);
  SubLoops.push_back(NewChild);
}

/// This removes the specified child from being a subloop of this loop. The
/// loop is not deleted, as it will presumably be inserted into another loop.
LoopT *removeChildLoop(iterator I) {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 340, __PRETTY_FUNCTION__));
  assert(I != SubLoops.end() && "Cannot remove end iterator!")((I != SubLoops.end() && "Cannot remove end iterator!"
) ? static_cast<void> (0) : __assert_fail ("I != SubLoops.end() && \"Cannot remove end iterator!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 341, __PRETTY_FUNCTION__));
  LoopT *Child = *I;
  assert(Child->ParentLoop == this && "Child is not a child of this loop!")((Child->ParentLoop == this && "Child is not a child of this loop!"
) ? static_cast<void> (0) : __assert_fail ("Child->ParentLoop == this && \"Child is not a child of this loop!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 343, __PRETTY_FUNCTION__));
  SubLoops.erase(SubLoops.begin() + (I - begin()));
  Child->ParentLoop = nullptr;
  return Child;
}

/// This removes the specified child from being a subloop of this loop. The
/// loop is not deleted, as it will presumably be inserted into another loop.
LoopT *removeChildLoop(LoopT *Child) {
  return removeChildLoop(llvm::find(*this, Child));
}

/// This adds a basic block directly to the basic block list.
/// This should only be used by transformations that create new loops.  Other
/// transformations should use addBasicBlockToLoop.
void addBlockEntry(BlockT *BB) {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 359, __PRETTY_FUNCTION__));
  Blocks.push_back(BB);
  DenseBlockSet.insert(BB);
}

/// interface to reverse Blocks[from, end of loop] in this loop
void reverseBlock(unsigned from) {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 366, __PRETTY_FUNCTION__));
  std::reverse(Blocks.begin() + from, Blocks.end());
}

/// interface to do reserve() for Blocks
void reserveBlocks(unsigned size) {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 372, __PRETTY_FUNCTION__));
  Blocks.reserve(size);
}

/// This method is used to move BB (which must be part of this loop) to be the
/// loop header of the loop (the block that dominates all others).
void moveToHeader(BlockT *BB) {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 379, __PRETTY_FUNCTION__));
  if (Blocks[0] == BB)
    return;
  for (unsigned i = 0;; ++i) {
    assert(i != Blocks.size() && "Loop does not contain BB!")((i != Blocks.size() && "Loop does not contain BB!") ?
 static_cast<void> (0) : __assert_fail ("i != Blocks.size() && \"Loop does not contain BB!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 383, __PRETTY_FUNCTION__));
    if (Blocks[i] == BB) {
      Blocks[i] = Blocks[0];
      Blocks[0] = BB;
      return;
    }
  }
}

/// This removes the specified basic block from the current loop, updating the
/// Blocks as appropriate. This does not update the mapping in the LoopInfo
/// class.
void removeBlockFromLoop(BlockT *BB) {
  assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 396, __PRETTY_FUNCTION__));
  auto I = find(Blocks, BB);
  assert(I != Blocks.end() && "N is not in this list!")((I != Blocks.end() && "N is not in this list!") ? static_cast
<void> (0) : __assert_fail ("I != Blocks.end() && \"N is not in this list!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 398, __PRETTY_FUNCTION__));
  Blocks.erase(I);

  DenseBlockSet.erase(BB);
}

/// Verify loop structure
void verifyLoop() const;

/// Verify loop structure of this loop and all nested loops.
void verifyLoopNest(DenseSet<const LoopT *> *Loops) const;

/// Returns true if the loop is annotated parallel.
///
/// Derived classes can override this method using static template
/// polymorphism.
bool isAnnotatedParallel() const { return false; }

/// Print loop with all the BBs inside it.
void print(raw_ostream &OS, unsigned Depth = 0, bool Verbose = false) const;

419protected:
friend class LoopInfoBase<BlockT, LoopT>;

/// This creates an empty loop.
LoopBase() : ParentLoop(nullptr) {}

explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) {
  Blocks.push_back(BB);
  DenseBlockSet.insert(BB);
}

// Since loop passes like SCEV are allowed to key analysis results off of
// `Loop` pointers, we cannot re-use pointers within a loop pass manager.
// This means loop passes should not be `delete` ing `Loop` objects directly
// (and risk a later `Loop` allocation re-using the address of a previous one)
// but should be using LoopInfo::markAsRemoved, which keeps around the `Loop`
// pointer till the end of the lifetime of the `LoopInfo` object.
//
// To make it easier to follow this rule, we mark the destructor as
// non-public.
~LoopBase() {
  for (auto *SubLoop : SubLoops)
    SubLoop->~LoopT();

443#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
  IsInvalid = true;
445#endif
  SubLoops.clear();
  Blocks.clear();
  DenseBlockSet.clear();
  ParentLoop = nullptr;
}
451};

453template <class BlockT, class LoopT>
454raw_ostream &operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) {
Loop.print(OS);
return OS;
457}

459// Implementation in LoopInfoImpl.h
460extern template class LoopBase<BasicBlock, Loop>;

462/// Represents a single loop in the control flow graph.  Note that not all SCCs
463/// in the CFG are necessarily loops.
464class Loop : public LoopBase<BasicBlock, Loop> {
465public:
/// A range representing the start and end location of a loop.
class LocRange {
  DebugLoc Start;
  DebugLoc End;

public:
  LocRange() {}
  LocRange(DebugLoc Start) : Start(std::move(Start)), End(std::move(Start)) {}
9
←
Object 'Start' is moved→
10
←
Moved-from object 'Start' is moved
  LocRange(DebugLoc Start, DebugLoc End)
      : Start(std::move(Start)), End(std::move(End)) {}

  const DebugLoc &getStart() const { return Start; }
  const DebugLoc &getEnd() const { return End; }

  /// Check for null.
  ///
  explicit operator bool() const { return Start && End; }
};

/// Return true if the specified value is loop invariant.
bool isLoopInvariant(const Value *V) const;

/// Return true if all the operands of the specified instruction are loop
/// invariant.
bool hasLoopInvariantOperands(const Instruction *I) const;

/// If the given value is an instruction inside of the loop and it can be
/// hoisted, do so to make it trivially loop-invariant.
/// Return true if the value after any hoisting is loop invariant. This
/// function can be used as a slightly more aggressive replacement for
/// isLoopInvariant.
///
/// If InsertPt is specified, it is the point to hoist instructions to.
/// If null, the terminator of the loop preheader is used.
bool makeLoopInvariant(Value *V, bool &Changed,
                       Instruction *InsertPt = nullptr) const;

/// If the given instruction is inside of the loop and it can be hoisted, do
/// so to make it trivially loop-invariant.
/// Return true if the instruction after any hoisting is loop invariant. This
/// function can be used as a slightly more aggressive replacement for
/// isLoopInvariant.
///
/// If InsertPt is specified, it is the point to hoist instructions to.
/// If null, the terminator of the loop preheader is used.
///
bool makeLoopInvariant(Instruction *I, bool &Changed,
                       Instruction *InsertPt = nullptr) const;

/// Check to see if the loop has a canonical induction variable: an integer
/// recurrence that starts at 0 and increments by one each time through the
/// loop. If so, return the phi node that corresponds to it.
///
/// The IndVarSimplify pass transforms loops to have a canonical induction
/// variable.
///
PHINode *getCanonicalInductionVariable() const;

/// Obtain the unique incoming and back edge. Return false if they are
/// non-unique or the loop is dead; otherwise, return true.
bool getIncomingAndBackEdge(BasicBlock *&Incoming,
                            BasicBlock *&Backedge) const;

/// Return true if the Loop is in LCSSA form.
bool isLCSSAForm(DominatorTree &DT) const;

/// Return true if this Loop and all inner subloops are in LCSSA form.
bool isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const;

/// Return true if the Loop is in the form that the LoopSimplify form
/// transforms loops to, which is sometimes called normal form.
bool isLoopSimplifyForm() const;

/// Return true if the loop body is safe to clone in practice.
bool isSafeToClone() const;

/// Returns true if the loop is annotated parallel.
///
/// A parallel loop can be assumed to not contain any dependencies between
/// iterations by the compiler. That is, any loop-carried dependency checking
/// can be skipped completely when parallelizing the loop on the target
/// machine. Thus, if the parallel loop information originates from the
/// programmer, e.g. via the OpenMP parallel for pragma, it is the
/// programmer's responsibility to ensure there are no loop-carried
/// dependencies. The final execution order of the instructions across
/// iterations is not guaranteed, thus, the end result might or might not
/// implement actual concurrent execution of instructions across multiple
/// iterations.
bool isAnnotatedParallel() const;

/// Return the llvm.loop loop id metadata node for this loop if it is present.
///
/// If this loop contains the same llvm.loop metadata on each branch to the
/// header then the node is returned. If any latch instruction does not
/// contain llvm.loop or if multiple latches contain different nodes then
/// 0 is returned.
MDNode *getLoopID() const;
/// Set the llvm.loop loop id metadata for this loop.
///
/// The LoopID metadata node will be added to each terminator instruction in
/// the loop that branches to the loop header.
///
/// The LoopID metadata node should have one or more operands and the first
/// operand should be the node itself.
void setLoopID(MDNode *LoopID) const;

/// Add llvm.loop.unroll.disable to this loop's loop id metadata.
///
/// Remove existing unroll metadata and add unroll disable metadata to
/// indicate the loop has already been unrolled.  This prevents a loop
/// from being unrolled more than is directed by a pragma if the loop
/// unrolling pass is run more than once (which it generally is).
void setLoopAlreadyUnrolled();

void dump() const;
void dumpVerbose() const;

/// Return the debug location of the start of this loop.
/// This looks for a BB terminating instruction with a known debug
/// location by looking at the preheader and header blocks. If it
/// cannot find a terminating instruction with location information,
/// it returns an unknown location.
DebugLoc getStartLoc() const;

/// Return the source code span of the loop.
LocRange getLocRange() const;

StringRef getName() const {
  if (BasicBlock *Header = getHeader())
    if (Header->hasName())
      return Header->getName();
  return "<unnamed loop>";
}

600private:
Loop() = default;

friend class LoopInfoBase<BasicBlock, Loop>;
friend class LoopBase<BasicBlock, Loop>;
explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {}
~Loop() = default;
607};

609//===----------------------------------------------------------------------===//
610/// This class builds and contains all of the top-level loop
611/// structures in the specified function.
612///

614template <class BlockT, class LoopT> class LoopInfoBase {
// BBMap - Mapping of basic blocks to the inner most loop they occur in
DenseMap<const BlockT *, LoopT *> BBMap;
std::vector<LoopT *> TopLevelLoops;
BumpPtrAllocator LoopAllocator;

friend class LoopBase<BlockT, LoopT>;
friend class LoopInfo;

void operator=(const LoopInfoBase &) = delete;
LoopInfoBase(const LoopInfoBase &) = delete;

626public:
LoopInfoBase() {}
~LoopInfoBase() { releaseMemory(); }

LoopInfoBase(LoopInfoBase &&Arg)
    : BBMap(std::move(Arg.BBMap)),
      TopLevelLoops(std::move(Arg.TopLevelLoops)),
      LoopAllocator(std::move(Arg.LoopAllocator)) {
  // We have to clear the arguments top level loops as we've taken ownership.
  Arg.TopLevelLoops.clear();
}
LoopInfoBase &operator=(LoopInfoBase &&RHS) {
  BBMap = std::move(RHS.BBMap);

  for (auto *L : TopLevelLoops)
    L->~LoopT();

  TopLevelLoops = std::move(RHS.TopLevelLoops);
  LoopAllocator = std::move(RHS.LoopAllocator);
  RHS.TopLevelLoops.clear();
  return *this;
}

void releaseMemory() {
  BBMap.clear();

  for (auto *L : TopLevelLoops)
    L->~LoopT();
  TopLevelLoops.clear();
  LoopAllocator.Reset();
}

template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) {
  LoopT *Storage = LoopAllocator.Allocate<LoopT>();
  return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
}

/// iterator/begin/end - The interface to the top-level loops in the current
/// function.
///
typedef typename std::vector<LoopT *>::const_iterator iterator;
typedef
    typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator;
iterator begin() const { return TopLevelLoops.begin(); }
iterator end() const { return TopLevelLoops.end(); }
reverse_iterator rbegin() const { return TopLevelLoops.rbegin(); }
reverse_iterator rend() const { return TopLevelLoops.rend(); }
bool empty() const { return TopLevelLoops.empty(); }

/// Return all of the loops in the function in preorder across the loop
/// nests, with siblings in forward program order.
///
/// Note that because loops form a forest of trees, preorder is equivalent to
/// reverse postorder.
SmallVector<LoopT *, 4> getLoopsInPreorder();

/// Return all of the loops in the function in preorder across the loop
/// nests, with siblings in *reverse* program order.
///
/// Note that because loops form a forest of trees, preorder is equivalent to
/// reverse postorder.
///
/// Also note that this is *not* a reverse preorder. Only the siblings are in
/// reverse program order.
SmallVector<LoopT *, 4> getLoopsInReverseSiblingPreorder();

/// Return the inner most loop that BB lives in. If a basic block is in no
/// loop (for example the entry node), null is returned.
LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); }

/// Same as getLoopFor.
const LoopT *operator[](const BlockT *BB) const { return getLoopFor(BB); }

/// Return the loop nesting level of the specified block. A depth of 0 means
/// the block is not inside any loop.
unsigned getLoopDepth(const BlockT *BB) const {
  const LoopT *L = getLoopFor(BB);
  return L ? L->getLoopDepth() : 0;
}

// True if the block is a loop header node
bool isLoopHeader(const BlockT *BB) const {
  const LoopT *L = getLoopFor(BB);
  return L && L->getHeader() == BB;
}

/// This removes the specified top-level loop from this loop info object.
/// The loop is not deleted, as it will presumably be inserted into
/// another loop.
LoopT *removeLoop(iterator I) {
  assert(I != end() && "Cannot remove end iterator!")((I != end() && "Cannot remove end iterator!") ? static_cast
<void> (0) : __assert_fail ("I != end() && \"Cannot remove end iterator!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 716, __PRETTY_FUNCTION__));
  LoopT *L = *I;
  assert(!L->getParentLoop() && "Not a top-level loop!")((!L->getParentLoop() && "Not a top-level loop!") ?
 static_cast<void> (0) : __assert_fail ("!L->getParentLoop() && \"Not a top-level loop!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 718, __PRETTY_FUNCTION__));
  TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin()));
  return L;
}

/// Change the top-level loop that contains BB to the specified loop.
/// This should be used by transformations that restructure the loop hierarchy
/// tree.
void changeLoopFor(BlockT *BB, LoopT *L) {
  if (!L) {
    BBMap.erase(BB);
    return;
  }
  BBMap[BB] = L;
}

/// Replace the specified loop in the top-level loops list with the indicated
/// loop.
void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop) {
  auto I = find(TopLevelLoops, OldLoop);
  assert(I != TopLevelLoops.end() && "Old loop not at top level!")((I != TopLevelLoops.end() && "Old loop not at top level!"
) ? static_cast<void> (0) : __assert_fail ("I != TopLevelLoops.end() && \"Old loop not at top level!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 738, __PRETTY_FUNCTION__));
  *I = NewLoop;
  assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop &&((!NewLoop->ParentLoop && !OldLoop->ParentLoop &&
 "Loops already embedded into a subloop!") ? static_cast<void
> (0) : __assert_fail ("!NewLoop->ParentLoop && !OldLoop->ParentLoop && \"Loops already embedded into a subloop!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 741, __PRETTY_FUNCTION__))
         "Loops already embedded into a subloop!")((!NewLoop->ParentLoop && !OldLoop->ParentLoop &&
 "Loops already embedded into a subloop!") ? static_cast<void
> (0) : __assert_fail ("!NewLoop->ParentLoop && !OldLoop->ParentLoop && \"Loops already embedded into a subloop!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 741, __PRETTY_FUNCTION__));
}

/// This adds the specified loop to the collection of top-level loops.
void addTopLevelLoop(LoopT *New) {
  assert(!New->getParentLoop() && "Loop already in subloop!")((!New->getParentLoop() && "Loop already in subloop!"
) ? static_cast<void> (0) : __assert_fail ("!New->getParentLoop() && \"Loop already in subloop!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 746, __PRETTY_FUNCTION__));
  TopLevelLoops.push_back(New);
}

/// This method completely removes BB from all data structures,
/// including all of the Loop objects it is nested in and our mapping from
/// BasicBlocks to loops.
void removeBlock(BlockT *BB) {
  auto I = BBMap.find(BB);
  if (I != BBMap.end()) {
    for (LoopT *L = I->second; L; L = L->getParentLoop())
      L->removeBlockFromLoop(BB);

    BBMap.erase(I);
  }
}

// Internals

static bool isNotAlreadyContainedIn(const LoopT *SubLoop,
                                    const LoopT *ParentLoop) {
  if (!SubLoop)
    return true;
  if (SubLoop == ParentLoop)
    return false;
  return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);
}

/// Create the loop forest using a stable algorithm.
void analyze(const DominatorTreeBase<BlockT, false> &DomTree);

// Debugging
void print(raw_ostream &OS) const;

void verify(const DominatorTreeBase<BlockT, false> &DomTree) const;

/// Destroy a loop that has been removed from the `LoopInfo` nest.
///
/// This runs the destructor of the loop object making it invalid to
/// reference afterward. The memory is retained so that the *pointer* to the
/// loop remains valid.
///
/// The caller is responsible for removing this loop from the loop nest and
/// otherwise disconnecting it from the broader `LoopInfo` data structures.
/// Callers that don't naturally handle this themselves should probably call
/// `erase' instead.
void destroy(LoopT *L) {
  L->~LoopT();

  // Since LoopAllocator is a BumpPtrAllocator, this Deallocate only poisons
  // \c L, but the pointer remains valid for non-dereferencing uses.
  LoopAllocator.Deallocate(L);
}
799};

801// Implementation in LoopInfoImpl.h
802extern template class LoopInfoBase<BasicBlock, Loop>;

804class LoopInfo : public LoopInfoBase<BasicBlock, Loop> {
typedef LoopInfoBase<BasicBlock, Loop> BaseT;

friend class LoopBase<BasicBlock, Loop>;

void operator=(const LoopInfo &) = delete;
LoopInfo(const LoopInfo &) = delete;

812public:
LoopInfo() {}
explicit LoopInfo(const DominatorTreeBase<BasicBlock, false> &DomTree);

LoopInfo(LoopInfo &&Arg) : BaseT(std::move(static_cast<BaseT &>(Arg))) {}
LoopInfo &operator=(LoopInfo &&RHS) {
  BaseT::operator=(std::move(static_cast<BaseT &>(RHS)));
  return *this;
}

/// Handle invalidation explicitly.
bool invalidate(Function &F, const PreservedAnalyses &PA,
                FunctionAnalysisManager::Invalidator &);

// Most of the public interface is provided via LoopInfoBase.

/// Update LoopInfo after removing the last backedge from a loop. This updates
/// the loop forest and parent loops for each block so that \c L is no longer
/// referenced, but does not actually delete \c L immediately. The pointer
/// will remain valid until this LoopInfo's memory is released.
void erase(Loop *L);

/// Returns true if replacing From with To everywhere is guaranteed to
/// preserve LCSSA form.
bool replacementPreservesLCSSAForm(Instruction *From, Value *To) {
  // Preserving LCSSA form is only problematic if the replacing value is an
  // instruction.
  Instruction *I = dyn_cast<Instruction>(To);
  if (!I)
    return true;
  // If both instructions are defined in the same basic block then replacement
  // cannot break LCSSA form.
  if (I->getParent() == From->getParent())
    return true;
  // If the instruction is not defined in a loop then it can safely replace
  // anything.
  Loop *ToLoop = getLoopFor(I->getParent());
  if (!ToLoop)
    return true;
  // If the replacing instruction is defined in the same loop as the original
  // instruction, or in a loop that contains it as an inner loop, then using
  // it as a replacement will not break LCSSA form.
  return ToLoop->contains(getLoopFor(From->getParent()));
}

/// Checks if moving a specific instruction can break LCSSA in any loop.
///
/// Return true if moving \p Inst to before \p NewLoc will break LCSSA,
/// assuming that the function containing \p Inst and \p NewLoc is currently
/// in LCSSA form.
bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc) {
  assert(Inst->getFunction() == NewLoc->getFunction() &&((Inst->getFunction() == NewLoc->getFunction() &&
 "Can't reason about IPO!") ? static_cast<void> (0) : __assert_fail
 ("Inst->getFunction() == NewLoc->getFunction() && \"Can't reason about IPO!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 864, __PRETTY_FUNCTION__))
         "Can't reason about IPO!")((Inst->getFunction() == NewLoc->getFunction() &&
 "Can't reason about IPO!") ? static_cast<void> (0) : __assert_fail
 ("Inst->getFunction() == NewLoc->getFunction() && \"Can't reason about IPO!\""
, "/build/llvm-toolchain-snapshot-9~svn359999/include/llvm/Analysis/LoopInfo.h"
, 864, __PRETTY_FUNCTION__));

  auto *OldBB = Inst->getParent();
  auto *NewBB = NewLoc->getParent();

  // Movement within the same loop does not break LCSSA (the equality check is
  // to avoid doing a hashtable lookup in case of intra-block movement).
  if (OldBB == NewBB)
    return true;

  auto *OldLoop = getLoopFor(OldBB);
  auto *NewLoop = getLoopFor(NewBB);

  if (OldLoop == NewLoop)
    return true;

  // Check if Outer contains Inner; with the null loop counting as the
  // "outermost" loop.
  auto Contains = [](const Loop *Outer, const Loop *Inner) {
    return !Outer || Outer->contains(Inner);
  };

  // To check that the movement of Inst to before NewLoc does not break LCSSA,
  // we need to check two sets of uses for possible LCSSA violations at
  // NewLoc: the users of NewInst, and the operands of NewInst.

  // If we know we're hoisting Inst out of an inner loop to an outer loop,
  // then the uses *of* Inst don't need to be checked.

  if (!Contains(NewLoop, OldLoop)) {
    for (Use &U : Inst->uses()) {
      auto *UI = cast<Instruction>(U.getUser());
      auto *UBB = isa<PHINode>(UI) ? cast<PHINode>(UI)->getIncomingBlock(U)
                                   : UI->getParent();
      if (UBB != NewBB && getLoopFor(UBB) != NewLoop)
        return false;
    }
  }

  // If we know we're sinking Inst from an outer loop into an inner loop, then
  // the *operands* of Inst don't need to be checked.

  if (!Contains(OldLoop, NewLoop)) {
    // See below on why we can't handle phi nodes here.
    if (isa<PHINode>(Inst))
      return false;

    for (Use &U : Inst->operands()) {
      auto *DefI = dyn_cast<Instruction>(U.get());
      if (!DefI)
        return false;

      // This would need adjustment if we allow Inst to be a phi node -- the
      // new use block won't simply be NewBB.

      auto *DefBlock = DefI->getParent();
      if (DefBlock != NewBB && getLoopFor(DefBlock) != NewLoop)
        return false;
    }
  }

  return true;
}
927};

929// Allow clients to walk the list of nested loops...
930template <> struct GraphTraits<const Loop *> {
typedef const Loop *NodeRef;
typedef LoopInfo::iterator ChildIteratorType;

static NodeRef getEntryNode(const Loop *L) { return L; }
static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
static ChildIteratorType child_end(NodeRef N) { return N->end(); }
937};

939template <> struct GraphTraits<Loop *> {
typedef Loop *NodeRef;
typedef LoopInfo::iterator ChildIteratorType;

static NodeRef getEntryNode(Loop *L) { return L; }
static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
static ChildIteratorType child_end(NodeRef N) { return N->end(); }
946};

948/// Analysis pass that exposes the \c LoopInfo for a function.
949class LoopAnalysis : public AnalysisInfoMixin<LoopAnalysis> {
friend AnalysisInfoMixin<LoopAnalysis>;
static AnalysisKey Key;

953public:
typedef LoopInfo Result;

LoopInfo run(Function &F, FunctionAnalysisManager &AM);
957};

959/// Printer pass for the \c LoopAnalysis results.
960class LoopPrinterPass : public PassInfoMixin<LoopPrinterPass> {
raw_ostream &OS;

963public:
explicit LoopPrinterPass(raw_ostream &OS) : OS(OS) {}
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
966};

968/// Verifier pass for the \c LoopAnalysis results.
969struct LoopVerifierPass : public PassInfoMixin<LoopVerifierPass> {
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
971};

973/// The legacy pass manager's analysis pass to compute loop information.
974class LoopInfoWrapperPass : public FunctionPass {
LoopInfo LI;

977public:
static char ID; // Pass identification, replacement for typeid

LoopInfoWrapperPass() : FunctionPass(ID) {
  initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());
}

LoopInfo &getLoopInfo() { return LI; }
const LoopInfo &getLoopInfo() const { return LI; }

/// Calculate the natural loop information for a given function.
bool runOnFunction(Function &F) override;

void verifyAnalysis() const override;

void releaseMemory() override { LI.releaseMemory(); }

void print(raw_ostream &O, const Module *M = nullptr) const override;

void getAnalysisUsage(AnalysisUsage &AU) const override;
997};

999/// Function to print a loop's contents as LLVM's text IR assembly.
1000void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner = "");

1002/// Find and return the loop attribute node for the attribute @p Name in
1003/// @p LoopID. Return nullptr if there is no such attribute.
1004MDNode *findOptionMDForLoopID(MDNode *LoopID, StringRef Name);

1006/// Find string metadata for a loop.
1007///
1008/// Returns the MDNode where the first operand is the metadata's name. The
1009/// following operands are the metadata's values. If no metadata with @p Name is
1010/// found, return nullptr.
1011MDNode *findOptionMDForLoop(const Loop *TheLoop, StringRef Name);

1013/// Return whether an MDNode might represent an access group.
1014///
1015/// Access group metadata nodes have to be distinct and empty. Being
1016/// always-empty ensures that it never needs to be changed (which -- because
1017/// MDNodes are designed immutable -- would require creating a new MDNode). Note
1018/// that this is not a sufficient condition: not every distinct and empty NDNode
1019/// is representing an access group.
1020bool isValidAsAccessGroup(MDNode *AccGroup);

1022/// Create a new LoopID after the loop has been transformed.
1023///
1024/// This can be used when no follow-up loop attributes are defined
1025/// (llvm::makeFollowupLoopID returning None) to stop transformations to be
1026/// applied again.
1027///
1028/// @param Context        The LLVMContext in which to create the new LoopID.
1029/// @param OrigLoopID     The original LoopID; can be nullptr if the original
1030///                       loop has no LoopID.
1031/// @param RemovePrefixes Remove all loop attributes that have these prefixes.
1032///                       Use to remove metadata of the transformation that has
1033///                       been applied.
1034/// @param AddAttrs       Add these loop attributes to the new LoopID.
1035///
1036/// @return A new LoopID that can be applied using Loop::setLoopID().
1037llvm::MDNode *
1038makePostTransformationMetadata(llvm::LLVMContext &Context, MDNode *OrigLoopID,
                             llvm::ArrayRef<llvm::StringRef> RemovePrefixes,
                             llvm::ArrayRef<llvm::MDNode *> AddAttrs);

1042} // End llvm namespace

1044#endif