[LoopInfo] empty() -> isInnermost(), add isOutermost()

[baziotis]

I created the review instead of just committing to discuss that it may be a good idea to even rename this e.g. to "isInnermost()".
With "empty()", it's not clear if the implementation is:
return getSubLoops().empty() or return !getNumBlocks() (or something else)

[fhahn]

In D82895#2123465, @baziotis wrote:

I created the review instead of just committing to discuss that it may be a good idea to even rename this e.g. to "isInnermost()".
With "empty()", it's not clear if the implementation is:
return getSubLoops().empty() or return !getNumBlocks() (or something else)

I think using empty makes sense in the context of begin() and end() also iterating over subloops.

llvm/include/llvm/Analysis/LoopInfo.h

158

make a doc-comment (///)? It might be good to mention sub-loops in the comment, e.g something like Return true if the loop contains any sub-loops.

[baziotis]

In D82895#2123566, @fhahn wrote:

In D82895#2123465, @baziotis wrote:

I created the review instead of just committing to discuss that it may be a good idea to even rename this e.g. to "isInnermost()".
With "empty()", it's not clear if the implementation is:
return getSubLoops().empty() or return !getNumBlocks() (or something else)

I think using empty makes sense in the context of begin() and end()

Indeed.

also iterating over subloops.

I think that isInnermost() would make even more sense. That is, one iterates until they reach the innermost loop.

Personally, in uses like this: https://github.com/llvm/llvm-project/blob/master/llvm/lib/Analysis/LoopAccessAnalysis.cpp#L1768
it doesn't make much sense (although here it does because of the comment and error msg).

One alternative would be to make an isInnermost() wrapper.

[baziotis]

Address comment.

[jdoerfert]

I think that isInnermost() would make even more sense.

I'm fine with adding bool isInnermost() const { return empty(); } and while we are at it, bool isOutermost().

@fhahn @Meinersbur @Whitney @etiotto Objections?

[etiotto]

In D82895#2129028, @jdoerfert wrote:

I think that isInnermost() would make even more sense.

I'm fine with adding bool isInnermost() const { return empty(); } and while we are at it, bool isOutermost().

@fhahn @Meinersbur @Whitney @etiotto Objections?

I think the proposed name isInnermost is fine. No objections on my part.

[Whitney]

In D82895#2129028, @jdoerfert wrote:

I think that isInnermost() would make even more sense.

I'm fine with adding bool isInnermost() const { return empty(); } and while we are at it, bool isOutermost().

@fhahn @Meinersbur @Whitney @etiotto Objections?

No objections as well.

[baziotis]

Thanks for the reviews, I'm updating.

[baziotis]

Added isInnermost/Outermost.

[fhahn]

In D82895#2129028, @jdoerfert wrote:

I think that isInnermost() would make even more sense.

I'm fine with adding bool isInnermost() const { return empty(); } and while we are at it, bool isOutermost().

@fhahn @Meinersbur @Whitney @etiotto Objections?

Hm, adding multiple ways to check the same thing may lead to other problems. IMO it will be more confusing if some places use !L->getParentLoop() and other L->isOutermost(). Same for isInnerMost()/empty().

Loops form a hierarchical structure and personally I think the existing helpers make sense in that context. It is also consistent with similar data structures (for example, I don't think there are isLeaf/isRoot helpers for DominatorTree). I would prefer to keep the interface leaner (with the new docstring for empty the docs are quite explicit), but it is not something I feel too strongly about in this case if others feel the benefit outweighs the cost/churn. If they get added, I think the users should be updated, otherwise things get more confusing than they are now.

[baziotis]

I partially agree but also IMHO empty() is confusing enough so that introducing isInnermost/Outermost has benefit that outweighs the cost. A Loop can contain both BBs and loops which is different than DominatorTree AFAIK (which can only contain BBs).
This is a big source of confusion when one comes across it in the code (and as I said, personally I assumed it had to do with the BBs).

Of course though, I don't have any kind of strong opinion. We can wait for other people's opinions.

[Meinersbur]

In D82895#2130151, @fhahn wrote:

Hm, adding multiple ways to check the same thing may lead to other problems. IMO it will be more confusing if some places use !L->getParentLoop() and other L->isOutermost().

There are often multiple ways for the same goal, for instance LoadInst::getPointerOperand() and LoadInst::getOperand(0). One makes the intention clearer than the other.

Same for isInnerMost()/empty().

Since these are identical, I'd tend to remove one. In these case I'd remove empty() since Loop does not represent a container.

llvm/include/llvm/Analysis/LoopInfo.h

159

isInnermost should be documented using a doc-string as well (or grouped together with empty() using /// @{ / /// @})

160

make this a doc-string as well?

[baziotis]

In D82895#2137834, @Meinersbur wrote:

In D82895#2130151, @fhahn wrote:

Hm, adding multiple ways to check the same thing may lead to other problems. IMO it will be more confusing if some places use !L->getParentLoop() and other L->isOutermost().

There are often multiple ways for the same goal, for instance LoadInst::getPointerOperand() and LoadInst::getOperand(0). One makes the intention clearer than the other.

Same for isInnerMost()/empty().

Since these are identical, I'd tend to remove one. In these case I'd remove empty() since Loop does not represent a container.

This the orthogonality vs expressiveness and I'm sure we all value each under certain circumstances. That said, I too agree that if we were to take
a step towards orthogonality, that would be to replace empty(), rather than not introducing isInnermost/Outermost.

llvm/include/llvm/Analysis/LoopInfo.h

160

I added it as non-doc comment intentionally but probably bad thought. I'll fix that.

[Meinersbur]

@baziotis Are you going to update this diff?

@fhahn OK with renaming empty() to isInnermost()?

[baziotis]

@baziotis Are you going to update this diff?

Thanks, I had forgotten about this.

@fhahn OK with renaming empty() to isInnermost()?

I'd say that now we see all the places empty() was used, for most of them the name isInnermost() makes more sense.

[fhahn]

In D82895#2283534, @baziotis wrote:

@baziotis Are you going to update this diff?

Thanks, I had forgotten about this.

@fhahn OK with renaming empty() to isInnermost()?

I'd say that now we see all the places empty() was used, for most of them the name isInnermost() makes more sense.

Thanks for updating!

LGTM, although it would be good to also update the code to use isOutermost.

llvm/include/llvm/Analysis/LoopInfo.h

161

It would be good to frame the comment in terms of the returned value, e.g. Return true if the loop does not have a parent loop (= is the outermost loop).

[Meinersbur]

llvm/include/llvm/Analysis/LoopInfo.h

158

Could you please add a remark about the following into the comments: LoopInfo does not detect irreducible control flow, just natural loops. That is, it is possible that there is cyclic control flow within the "innermost loop". LoopVectorize for instance explicitly checks for this, see collectSupportedLoops. There can also be be cyclic control-flow around the "outermost loop" (I think). IMHO this caveat is important to mention.

[baziotis]

Address comments

[baziotis]

llvm/include/llvm/Analysis/LoopInfo.h

158

If we wanted to appear on both function's doc, I think I'd have to add it twice. So I added it above both and I mention (natural) in each function.

[MaskRay]

API changes may cause problems to other backends. It is a good idea to test -DLLVM_TARGETS_TO_BUILD=ALL

[baziotis]

In D82895#2288745, @MaskRay wrote:

API changes may cause problems to other backends. It is a good idea to test -DLLVM_TARGETS_TO_BUILD=ALL

True, I'm sorry. I tested all targets and it should be fine now. Thanks to you and @darkbuck for pushing the two fixes.

llvm/include/llvm/Analysis/LoopInfo.h

public:
   }
   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(); }
+
+  // LoopInfo does not detect irreducible control flow, just natural
+  // loops. That is, it is possible that there is cyclic control
+  // flow within the "innermost loop" or around the "outermost
+  // loop".
+
+  /// Return true if the loop does not contain any (natural) loops.
+  bool isInnermost() const { return getSubLoops().empty(); }
+  /// Return true if the loop does not have a parent (natural) loop
+  // (i.e. it is outermost, which is the same as top-level).
+  bool isOutermost() const { return getParentLoop() == nullptr; }
 
   /// Get a list of the basic blocks which make up this loop.
   ArrayRef<BlockT *> getBlocks() const {
     assert(!isInvalid() && "Loop not in a valid state!");
     return Blocks;
   }
   typedef typename ArrayRef<BlockT *>::const_iterator block_iterator;
   block_iterator block_begin() const { return getBlocks().begin(); }
public:
   std::vector<LoopT *> &getTopLevelLoopsVector() { return TopLevelLoops; }
 
   /// 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!");
     LoopT *L = *I;
-    assert(!L->getParentLoop() && "Not a top-level loop!");
+    assert(L->isOutermost() && "Not a top-level loop!");
     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) {
void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop) {
     assert(I != TopLevelLoops.end() && "Old loop not at top level!");
     *I = NewLoop;
     assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop &&
            "Loops already embedded into a subloop!");
   }
 
   /// This adds the specified loop to the collection of top-level loops.
   void addTopLevelLoop(LoopT *New) {
-    assert(!New->getParentLoop() && "Loop already in subloop!");
+    assert(New->isOutermost() && "Loop already in subloop!");
     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);

llvm/include/llvm/Analysis/LoopInfoImpl.h

 /// subloop header, add the subloop to its parent in PostOrder, then reverse the
 /// Block and Subloop vectors of the now complete subloop to achieve RPO.
 template <class BlockT, class LoopT>
 void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
   LoopT *Subloop = LI->getLoopFor(Block);
   if (Subloop && Block == Subloop->getHeader()) {
     // We reach this point once per subloop after processing all the blocks in
     // the subloop.
-    if (Subloop->getParentLoop())
+    if (!Subloop->isOutermost())
       Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
     else
       LI->addTopLevelLoop(Subloop);
 
     // For convenience, Blocks and Subloops are inserted in postorder. Reverse
     // the lists, except for the loop header, which is always at the beginning.
     Subloop->reverseBlock(1);
     std::reverse(Subloop->getSubLoopsVector().begin(),

 }
 #endif
 
 template <class BlockT, class LoopT>
 void LoopInfoBase<BlockT, LoopT>::verify(
     const DomTreeBase<BlockT> &DomTree) const {
   DenseSet<const LoopT *> Loops;
   for (iterator I = begin(), E = end(); I != E; ++I) {
-    assert(!(*I)->getParentLoop() && "Top-level loop has a parent!");
+    assert((*I)->isOutermost() && "Top-level loop has a parent!");
     (*I)->verifyLoopNest(&Loops);
   }
 
 // Verify that blocks are mapped to valid loops.
 #ifndef NDEBUG
   for (auto &Entry : BBMap) {
     const BlockT *BB = Entry.first;
     LoopT *L = Entry.second;

llvm/lib/Analysis/LoopAccessAnalysis.cpp

 
 bool LoopAccessInfo::canAnalyzeLoop() {
   // We need to have a loop header.
   LLVM_DEBUG(dbgs() << "LAA: Found a loop in "
                     << TheLoop->getHeader()->getParent()->getName() << ": "
                     << TheLoop->getHeader()->getName() << '\n');
 
   // We can only analyze innermost loops.
-  if (!TheLoop->empty()) {
+  if (!TheLoop->isInnermost()) {
     LLVM_DEBUG(dbgs() << "LAA: loop is not the innermost loop\n");
     recordAnalysis("NotInnerMostLoop") << "loop is not the innermost loop";
     return false;
   }
 
   // We must have a single backedge.
   if (TheLoop->getNumBackEdges() != 1) {
     LLVM_DEBUG(

llvm/lib/Analysis/LoopCacheAnalysis.cpp

CacheCost::CacheCost(const LoopVectorTy &Loops, const LoopInfo &LI,
   }
 
   calculateCacheFootprint();
 }
 
 std::unique_ptr<CacheCost>
 CacheCost::getCacheCost(Loop &Root, LoopStandardAnalysisResults &AR,
                         DependenceInfo &DI, Optional<unsigned> TRT) {
-  if (Root.getParentLoop()) {
+  if (!Root.isOutermost()) {
     LLVM_DEBUG(dbgs() << "Expecting the outermost loop in a loop nest\n");
     return nullptr;
   }
 
   LoopVectorTy Loops;
   for (Loop *L : breadth_first(&Root))
     Loops.push_back(L);
 

llvm/lib/Analysis/LoopInfo.cpp

for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
       assert(OldParent && "new loop is not an ancestor of the original");
       OldParent->removeBlockFromLoop(*BI);
     }
   }
 }
 
 /// Update the parent loop for all subloops directly nested within unloop.
 void UnloopUpdater::updateSubloopParents() {
-  while (!Unloop.empty()) {
+  while (!Unloop.isInnermost()) {
     Loop *Subloop = *std::prev(Unloop.end());
     Unloop.removeChildLoop(std::prev(Unloop.end()));
 
     assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
     if (Loop *Parent = SubloopParents[Subloop])
       Parent->addChildLoop(Subloop);
     else
       LI->addTopLevelLoop(Subloop);

 }
 
 void LoopInfo::erase(Loop *Unloop) {
   assert(!Unloop->isInvalid() && "Loop has already been erased!");
 
   auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); });
 
   // First handle the special case of no parent loop to simplify the algorithm.
-  if (!Unloop->getParentLoop()) {
+  if (Unloop->isOutermost()) {
     // 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");
       if (*I == Unloop) {
         removeLoop(I);
         break;
       }
     }
 
     // Move all of the subloops to the top-level.
-    while (!Unloop->empty())
+    while (!Unloop->isInnermost())
       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);

llvm/lib/Analysis/LoopNestAnalysis.cpp

 
 std::unique_ptr<LoopNest> LoopNest::getLoopNest(Loop &Root,
                                                 ScalarEvolution &SE) {
   return std::make_unique<LoopNest>(Root, SE);
 }
 
 bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
                                   ScalarEvolution &SE) {
-  assert(!OuterLoop.getSubLoops().empty() && "Outer loop should have subloops");
-  assert(InnerLoop.getParentLoop() && "Inner loop should have a parent");
+  assert(!OuterLoop.isInnermost() && "Outer loop should have subloops");
+  assert(!InnerLoop.isOutermost() && "Inner loop should have a parent");
   LLVM_DEBUG(dbgs() << "Checking whether loop '" << OuterLoop.getName()
                     << "' and '" << InnerLoop.getName()
                     << "' are perfectly nested.\n");
 
   // Determine whether the loops structure satisfies the following requirements:
   //  - the inner loop should be the outer loop's only child
   //  - the outer loop header should 'flow' into the inner loop preheader
   //    or jump around the inner loop to the outer loop latch

llvm/lib/Analysis/LoopPass.cpp

 LPPassManager::LPPassManager()
   : FunctionPass(ID), PMDataManager() {
   LI = nullptr;
   CurrentLoop = nullptr;
 }
 
 // Insert loop into loop nest (LoopInfo) and loop queue (LQ).
 void LPPassManager::addLoop(Loop &L) {
-  if (!L.getParentLoop()) {
+  if (L.isOutermost()) {
     // This is the top level loop.
     LQ.push_front(&L);
     return;
   }
 
   // Insert L into the loop queue after the parent loop.
   for (auto I = LQ.begin(), E = LQ.end(); I != E; ++I) {
     if (*I == L.getParentLoop()) {

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

static void emitBasicBlockLoopComments(const MachineBasicBlock &MBB,
   raw_ostream &OS = AP.OutStreamer->GetCommentOS();
 
   PrintParentLoopComment(OS, Loop->getParentLoop(), AP.getFunctionNumber());
 
   OS << "=>";
   OS.indent(Loop->getLoopDepth()*2-2);
 
   OS << "This ";
-  if (Loop->empty())
+  if (Loop->isInnermost())
     OS << "Inner ";
   OS << "Loop Header: Depth=" + Twine(Loop->getLoopDepth()) << '\n';
 
   PrintChildLoopComment(OS, Loop, AP.getFunctionNumber());
 }
 
 /// emitBasicBlockStart - This method prints the label for the specified
 /// MachineBasicBlock, an alignment (if present) and a comment describing

llvm/lib/CodeGen/HardwareLoops.cpp

bool HardwareLoops::runOnFunction(Function &F) {
   auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
   LibInfo = TLIP ? &TLIP->getTLI(F) : nullptr;
   PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
   M = F.getParent();
 
   for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) {
     Loop *L = *I;
-    if (!L->getParentLoop())
+    if (L->isOutermost())
       TryConvertLoop(L);
   }
 
   return MadeChange;
 }
 
 // Return true if the search should stop, which will be when an inner loop is
 // converted and the parent loop doesn't support containing a hardware loop.

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

bool ARMLowOverheadLoops::runOnMachineFunction(MachineFunction &mf) {
   TII = static_cast<const ARMBaseInstrInfo*>(ST.getInstrInfo());
   TRI = ST.getRegisterInfo();
   BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(*MF));
   BBUtils->computeAllBlockSizes();
   BBUtils->adjustBBOffsetsAfter(&MF->front());
 
   bool Changed = false;
   for (auto ML : *MLI) {
-    if (!ML->getParentLoop())
+    if (ML->isOutermost())
       Changed |= ProcessLoop(ML);
   }
   Changed |= RevertNonLoops();
   return Changed;
 }
 
 bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) {
 

llvm/lib/Target/Hexagon/HexagonHardwareLoops.cpp

bool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) {
   MLI = &getAnalysis<MachineLoopInfo>();
   MRI = &MF.getRegInfo();
   MDT = &getAnalysis<MachineDominatorTree>();
   const HexagonSubtarget &HST = MF.getSubtarget<HexagonSubtarget>();
   TII = HST.getInstrInfo();
   TRI = HST.getRegisterInfo();
 
   for (auto &L : *MLI)
-    if (!L->getParentLoop()) {
+    if (L->isOutermost()) {
       bool L0Used = false;
       bool L1Used = false;
       Changed |= convertToHardwareLoop(L, L0Used, L1Used);
     }
 
   return Changed;
 }
 

llvm/lib/Transforms/Scalar/LICM.cpp

if (!HasCatchSwitch) {
       Changed |= Promoted;
     }
   }
 
   // Check that neither this loop nor its parent have had LCSSA broken. LICM is
   // specifically moving instructions across the loop boundary and so it is
   // especially in need of sanity checking here.
   assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!");
-  assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) &&
+  assert((L->isOutermost() || L->getParentLoop()->isLCSSAForm(*DT)) &&
          "Parent loop not left in LCSSA form after LICM!");
 
   if (MSSAU.get() && VerifyMemorySSA)
     MSSAU->getMemorySSA()->verifyMemorySSA();
 
   if (Changed && SE)
     SE->forgetLoopDispositions(L);
   return Changed;

llvm/lib/Transforms/Scalar/LoopDataPrefetch.cpp

void addInstruction(Instruction *I, DominatorTree *DT = nullptr,
     }
   }
 };
 
 bool LoopDataPrefetch::runOnLoop(Loop *L) {
   bool MadeChange = false;
 
   // Only prefetch in the inner-most loop
-  if (!L->empty())
+  if (!L->isInnermost())
     return MadeChange;
 
   SmallPtrSet<const Value *, 32> EphValues;
   CodeMetrics::collectEphemeralValues(L, AC, EphValues);
 
   // Calculate the number of iterations ahead to prefetch
   CodeMetrics Metrics;
   bool HasCall = false;

llvm/lib/Transforms/Scalar/LoopDistribute.cpp

public:
   LoopDistributeForLoop(Loop *L, Function *F, LoopInfo *LI, DominatorTree *DT,
                         ScalarEvolution *SE, OptimizationRemarkEmitter *ORE)
       : L(L), F(F), LI(LI), DT(DT), SE(SE), ORE(ORE) {
     setForced();
   }
 
   /// Try to distribute an inner-most loop.
   bool processLoop(std::function<const LoopAccessInfo &(Loop &)> &GetLAA) {
-    assert(L->empty() && "Only process inner loops.");
+    assert(L->isInnermost() && "Only process inner loops.");
 
     LLVM_DEBUG(dbgs() << "\nLDist: In \""
                       << L->getHeader()->getParent()->getName()
                       << "\" checking " << *L << "\n");
 
     if (!L->getExitBlock())
       return fail("MultipleExitBlocks", "multiple exit blocks");
     if (!L->isLoopSimplifyForm())
static bool runImpl(Function &F, LoopInfo *LI, DominatorTree *DT,
   // Build up a worklist of inner-loops to vectorize. This is necessary as the
   // act of distributing a loop creates new loops and can invalidate iterators
   // across the loops.
   SmallVector<Loop *, 8> Worklist;
 
   for (Loop *TopLevelLoop : *LI)
     for (Loop *L : depth_first(TopLevelLoop))
       // We only handle inner-most loops.
-      if (L->empty())
+      if (L->isInnermost())
         Worklist.push_back(L);
 
   // Now walk the identified inner loops.
   bool Changed = false;
   for (Loop *L : Worklist) {
     LoopDistributeForLoop LDL(L, &F, LI, DT, SE, ORE);
 
     // If distribution was forced for the specific loop to be

llvm/lib/Transforms/Scalar/LoopFuse.cpp

SmallVector<BasicBlock *, 8> Blocks(FC1.L->block_begin(),
                                         FC1.L->block_end());
     for (BasicBlock *BB : Blocks) {
       FC0.L->addBlockEntry(BB);
       FC1.L->removeBlockFromLoop(BB);
       if (LI.getLoopFor(BB) != FC1.L)
         continue;
       LI.changeLoopFor(BB, FC0.L);
     }
-    while (!FC1.L->empty()) {
+    while (!FC1.L->isInnermost()) {
       const auto &ChildLoopIt = FC1.L->begin();
       Loop *ChildLoop = *ChildLoopIt;
       FC1.L->removeChildLoop(ChildLoopIt);
       FC0.L->addChildLoop(ChildLoop);
     }
 
     // Delete the now empty loop L1.
     LI.erase(FC1.L);
SmallVector<BasicBlock *, 8> Blocks(FC1.L->block_begin(),
                                         FC1.L->block_end());
     for (BasicBlock *BB : Blocks) {
       FC0.L->addBlockEntry(BB);
       FC1.L->removeBlockFromLoop(BB);
       if (LI.getLoopFor(BB) != FC1.L)
         continue;
       LI.changeLoopFor(BB, FC0.L);
     }
-    while (!FC1.L->empty()) {
+    while (!FC1.L->isInnermost()) {
       const auto &ChildLoopIt = FC1.L->begin();
       Loop *ChildLoop = *ChildLoopIt;
       FC1.L->removeChildLoop(ChildLoopIt);
       FC0.L->addChildLoop(ChildLoop);
     }
 
     // Delete the now empty loop L1.
     LI.erase(FC1.L);

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

 }
 
 // When compiling for codesize we avoid idiom recognition for a multi-block loop
 // unless it is a loop_memset idiom or a memset/memcpy idiom in a nested loop.
 //
 bool LoopIdiomRecognize::avoidLIRForMultiBlockLoop(bool IsMemset,
                                                    bool IsLoopMemset) {
   if (ApplyCodeSizeHeuristics && CurLoop->getNumBlocks() > 1) {
-    if (!CurLoop->getParentLoop() && (!IsMemset || !IsLoopMemset)) {
+    if (CurLoop->isOutermost() && (!IsMemset || !IsLoopMemset)) {
       LLVM_DEBUG(dbgs() << "  " << CurLoop->getHeader()->getParent()->getName()
                         << " : LIR " << (IsMemset ? "Memset" : "Memcpy")
                         << " avoided: multi-block top-level loop\n");
       return true;
     }
   }
 
   return false;

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

if (OuterLoopParent) {
     // Remove the loop from its parent loop.
     removeChildLoop(OuterLoopParent, NewInner);
     removeChildLoop(NewInner, NewOuter);
     OuterLoopParent->addChildLoop(NewOuter);
   } else {
     removeChildLoop(NewInner, NewOuter);
     LI->changeTopLevelLoop(NewInner, NewOuter);
   }
-  while (!NewOuter->empty())
+  while (!NewOuter->isInnermost())
     NewInner->addChildLoop(NewOuter->removeChildLoop(NewOuter->begin()));
   NewOuter->addChildLoop(NewInner);
 
   // BBs from the original inner loop.
   SmallVector<BasicBlock *, 8> OrigInnerBBs(NewOuter->blocks());
 
   // Add BBs from the original outer loop to the original inner loop (excluding
   // BBs already in inner loop)

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

eliminateLoadsAcrossLoops(Function &F, LoopInfo &LI, DominatorTree &DT,
   // FIXME: This logic comes from other passes that actually change the loop
   // nest structure. It isn't clear this is necessary (or useful) for a pass
   // which merely optimizes the use of loads in a loop.
   SmallVector<Loop *, 8> Worklist;
 
   for (Loop *TopLevelLoop : LI)
     for (Loop *L : depth_first(TopLevelLoop))
       // We only handle inner-most loops.
-      if (L->empty())
+      if (L->isInnermost())
         Worklist.push_back(L);
 
   // Now walk the identified inner loops.
   bool Changed = false;
   for (Loop *L : Worklist) {
     // The actual work is performed by LoadEliminationForLoop.
     LoadEliminationForLoop LEL(L, &LI, GetLAI(*L), &DT, BFI, PSI);
     Changed |= LEL.processLoop();

llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp

void deleteDeadLoopBlocks() {
     // it requires loop's preheader to be strictly in loop's parent. We cannot
     // just remove blocks one by one, because after removal of preheader we may
     // break this invariant for the dead loop. So we detatch and erase all dead
     // loops beforehand.
     for (auto *BB : DeadLoopBlocks)
       if (LI.isLoopHeader(BB)) {
         assert(LI.getLoopFor(BB) != &L && "Attempt to remove current loop!");
         Loop *DL = LI.getLoopFor(BB);
-        if (DL->getParentLoop()) {
+        if (!DL->isOutermost()) {
           for (auto *PL = DL->getParentLoop(); PL; PL = PL->getParentLoop())
             for (auto *BB : DL->getBlocks())
               PL->removeBlockFromLoop(BB);
           DL->getParentLoop()->removeChildLoop(DL);
           LI.addTopLevelLoop(DL);
         }
         LI.erase(DL);
       }

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

#endif // DEBUG
   // First, perform some low-level loop optimizations.
   OptimizeShadowIV();
   OptimizeLoopTermCond();
 
   // If loop preparation eliminates all interesting IV users, bail.
   if (IU.empty()) return;
 
   // Skip nested loops until we can model them better with formulae.
-  if (!L->empty()) {
+  if (!L->isInnermost()) {
     LLVM_DEBUG(dbgs() << "LSR skipping outer loop " << *L << "\n");
     return;
   }
 
   // Start collecting data and preparing for the solver.
   CollectChains();
   CollectInterestingTypesAndFactors();
   CollectFixupsAndInitialFormulae();

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

static Optional<EstimatedUnrollCost> analyzeLoopUnrollCost(
   // to them without checking for overflows, and we already don't want to
   // analyze *massive* trip counts, so we force the max to be reasonably small.
   assert(MaxIterationsCountToAnalyze <
              (unsigned)(std::numeric_limits<int>::max() / 2) &&
          "The unroll iterations max is too large!");
 
   // Only analyze inner loops. We can't properly estimate cost of nested loops
   // and we won't visit inner loops again anyway.
-  if (!L->empty())
+  if (!L->isInnermost())
     return None;
 
   // Don't simulate loops with a big or unknown tripcount
   if (!TripCount || TripCount > MaxIterationsCountToAnalyze)
     return None;
 
   SmallSetVector<BasicBlock *, 16> BBWorklist;
   SmallSetVector<std::pair<BasicBlock *, BasicBlock *>, 4> ExitWorklist;

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

static Loop *cloneLoopNest(Loop &OrigRootL, Loop *RootParentL,
   // a different parent and because we most commonly are cloning leaf loops.
   Loop *ClonedRootL = LI.AllocateLoop();
   if (RootParentL)
     RootParentL->addChildLoop(ClonedRootL);
   else
     LI.addTopLevelLoop(ClonedRootL);
   AddClonedBlocksToLoop(OrigRootL, *ClonedRootL);
 
-  if (OrigRootL.empty())
+  if (OrigRootL.isInnermost())
     return ClonedRootL;
 
   // If we have a nest, we can quickly clone the entire loop nest using an
   // iterative approach because it is a tree. We keep the cloned parent in the
   // data structure to avoid repeatedly querying through a map to find it.
   SmallVector<std::pair<Loop *, Loop *>, 16> LoopsToClone;
   // Build up the loops to clone in reverse order as we'll clone them from the
   // back.
#endif
   // For non-child cloned loops and hoisted loops, we just need to update LCSSA
   // and we can do it in any order as they don't nest relative to each other.
   //
   // Also check if any of the loops we have updated have become top-level loops
   // as that will necessitate widening the outer loop scope.
   for (Loop *UpdatedL :
        llvm::concat<Loop *>(NonChildClonedLoops, HoistedLoops)) {
     UpdateLoop(*UpdatedL);
-    if (!UpdatedL->getParentLoop())
+    if (UpdatedL->isOutermost())
       OuterExitL = nullptr;
   }
   if (IsStillLoop) {
     UpdateLoop(L);
-    if (!L.getParentLoop())
+    if (L.isOutermost())
       OuterExitL = nullptr;
   }
 
   // If the original loop had exit blocks, walk up through the outer most loop
   // of those exit blocks to update LCSSA and form updated dedicated exits.
   if (OuterExitL != &L)
     for (Loop *OuterL = ParentL; OuterL != OuterExitL;
          OuterL = OuterL->getParentLoop())

llvm/lib/Transforms/Utils/LoopPeel.cpp

void llvm::computePeelCount(Loop *L, unsigned LoopSize,
   unsigned TargetPeelCount = PP.PeelCount;
   PP.PeelCount = 0;
   if (!canPeel(L))
     return;
 
   // Only try to peel innermost loops by default.
   // The constraint can be relaxed by the target in TTI.getUnrollingPreferences
   // or by the flag -unroll-allow-loop-nests-peeling.
-  if (!PP.AllowLoopNestsPeeling && !L->empty())
+  if (!PP.AllowLoopNestsPeeling && !L->isInnermost())
     return;
 
   // If the user provided a peel count, use that.
   bool UserPeelCount = UnrollForcePeelCount.getNumOccurrences() > 0;
   if (UserPeelCount) {
     LLVM_DEBUG(dbgs() << "Force-peeling first " << UnrollForcePeelCount
                       << " iterations.\n");
     PP.PeelCount = UnrollForcePeelCount;

llvm/lib/Transforms/Utils/LoopVersioning.cpp

bool runImpl(LoopInfo *LI, function_ref<const LoopAccessInfo &(Loop &)> GetLAA,
   // Build up a worklist of inner-loops to version. This is necessary as the
   // act of versioning a loop creates new loops and can invalidate iterators
   // across the loops.
   SmallVector<Loop *, 8> Worklist;
 
   for (Loop *TopLevelLoop : *LI)
     for (Loop *L : depth_first(TopLevelLoop))
       // We only handle inner-most loops.
-      if (L->empty())
+      if (L->isInnermost())
         Worklist.push_back(L);
 
   // Now walk the identified inner loops.
   bool Changed = false;
   for (Loop *L : Worklist) {
     const LoopAccessInfo &LAI = GetLAA(*L);
     if (L->isLoopSimplifyForm() && !LAI.hasConvergentOp() &&
         (LAI.getNumRuntimePointerChecks() ||

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

int LoopVectorizationLegality::isConsecutivePtr(Value *Ptr) {
   return 0;
 }
 
 bool LoopVectorizationLegality::isUniform(Value *V) {
   return LAI->isUniform(V);
 }
 
 bool LoopVectorizationLegality::canVectorizeOuterLoop() {
-  assert(!TheLoop->empty() && "We are not vectorizing an outer loop.");
+  assert(!TheLoop->isInnermost() && "We are not vectorizing an outer loop.");
   // Store the result and return it at the end instead of exiting early, in case
   // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
   bool Result = true;
   bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
 
   for (BasicBlock *BB : TheLoop->blocks()) {
     // Check whether the BB terminator is a BranchInst. Any other terminator is
     // not supported yet.
bool LoopVectorizationLegality::canVectorizeWithIfConvert() {
 
   // We can if-convert this loop.
   return true;
 }
 
 // Helper function to canVectorizeLoopNestCFG.
 bool LoopVectorizationLegality::canVectorizeLoopCFG(Loop *Lp,
                                                     bool UseVPlanNativePath) {
-  assert((UseVPlanNativePath || Lp->empty()) &&
+  assert((UseVPlanNativePath || Lp->isInnermost()) &&
          "VPlan-native path is not enabled.");
 
   // TODO: ORE should be improved to show more accurate information when an
   // outer loop can't be vectorized because a nested loop is not understood or
   // legal. Something like: "outer_loop_location: loop not vectorized:
   // (inner_loop_location) loop control flow is not understood by vectorizer".
 
   // Store the result and return it at the end instead of exiting early, in case
bool LoopVectorizationLegality::canVectorize(bool UseVPlanNativePath) {
   }
 
   // We need to have a loop header.
   LLVM_DEBUG(dbgs() << "LV: Found a loop: " << TheLoop->getHeader()->getName()
                     << '\n');
 
   // Specific checks for outer loops. We skip the remaining legal checks at this
   // point because they don't support outer loops.
-  if (!TheLoop->empty()) {
+  if (!TheLoop->isInnermost()) {
     assert(UseVPlanNativePath && "VPlan-native path is not enabled.");
 
     if (!canVectorizeOuterLoop()) {
       reportVectorizationFailure("Unsupported outer loop",
                                  "unsupported outer loop",
                                  "UnsupportedOuterLoop",
                                  ORE, TheLoop);
       // TODO: Implement DoExtraAnalysis when subsequent legal checks support
       // outer loops.
       return false;
     }
 
     LLVM_DEBUG(dbgs() << "LV: We can vectorize this outer loop!\n");
     return Result;
   }
 
-  assert(TheLoop->empty() && "Inner loop expected.");
+  assert(TheLoop->isInnermost() && "Inner loop expected.");
   // Check if we can if-convert non-single-bb loops.
   unsigned NumBlocks = TheLoop->getNumBlocks();
   if (NumBlocks != 1 && !canVectorizeWithIfConvert()) {
     LLVM_DEBUG(dbgs() << "LV: Can't if-convert the loop.\n");
     if (DoExtraAnalysis)
       Result = false;
     else
       return false;

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

 // (i.e., LV must check that vectorization is legal) whereas pragma 'omp simd'
 // provides *explicit vectorization hints* (LV can bypass legal checks and
 // assume that vectorization is legal). However, both hints are implemented
 // using the same metadata (llvm.loop.vectorize, processed by
 // LoopVectorizeHints). This will be fixed in the future when the native IR
 // representation for pragma 'omp simd' is introduced.
 static bool isExplicitVecOuterLoop(Loop *OuterLp,
                                    OptimizationRemarkEmitter *ORE) {
-  assert(!OuterLp->empty() && "This is not an outer loop");
+  assert(!OuterLp->isInnermost() && "This is not an outer loop");
   LoopVectorizeHints Hints(OuterLp, true /*DisableInterleaving*/, *ORE);
 
   // Only outer loops with an explicit vectorization hint are supported.
   // Unannotated outer loops are ignored.
   if (Hints.getForce() == LoopVectorizeHints::FK_Undefined)
     return false;
 
   Function *Fn = OuterLp->getHeader()->getParent();

 
 static void collectSupportedLoops(Loop &L, LoopInfo *LI,
                                   OptimizationRemarkEmitter *ORE,
                                   SmallVectorImpl<Loop *> &V) {
   // Collect inner loops and outer loops without irreducible control flow. For
   // now, only collect outer loops that have explicit vectorization hints. If we
   // are stress testing the VPlan H-CFG construction, we collect the outermost
   // loop of every loop nest.
-  if (L.empty() || VPlanBuildStressTest ||
+  if (L.isInnermost() || VPlanBuildStressTest ||
       (EnableVPlanNativePath && isExplicitVecOuterLoop(&L, ORE))) {
     LoopBlocksRPO RPOT(&L);
     RPOT.perform(LI);
     if (!containsIrreducibleCFG<const BasicBlock *>(RPOT, *LI)) {
       V.push_back(&L);
       // TODO: Collect inner loops inside marked outer loops in case
       // vectorization fails for the outer loop. Do not invoke
       // 'containsIrreducibleCFG' again for inner loops when the outer loop is

 VectorizationFactor
 LoopVectorizationPlanner::planInVPlanNativePath(ElementCount UserVF) {
   assert(!UserVF.isScalable() && "scalable vectors not yet supported");
   ElementCount VF = UserVF;
   // Outer loop handling: They may require CFG and instruction level
   // transformations before even evaluating whether vectorization is profitable.
   // Since we cannot modify the incoming IR, we need to build VPlan upfront in
   // the vectorization pipeline.
-  if (!OrigLoop->empty()) {
+  if (!OrigLoop->isInnermost()) {
     // If the user doesn't provide a vectorization factor, determine a
     // reasonable one.
     if (UserVF.isZero()) {
       VF = ElementCount::getFixed(
           determineVPlanVF(TTI->getRegisterBitWidth(true /* Vector*/), CM));
       LLVM_DEBUG(dbgs() << "LV: VPlan computed VF " << VF << ".\n");
 
       // Make sure we have a VF > 1 for stress testing.
LLVM_DEBUG(
       dbgs() << "LV: Not vectorizing. Inner loops aren't supported in the "
                 "VPlan-native path.\n");
   return VectorizationFactor::Disabled();
 }
 
 Optional<VectorizationFactor>
 LoopVectorizationPlanner::plan(ElementCount UserVF, unsigned UserIC) {
   assert(!UserVF.isScalable() && "scalable vectorization not yet handled");
-  assert(OrigLoop->empty() && "Inner loop expected.");
+  assert(OrigLoop->isInnermost() && "Inner loop expected.");
   Optional<unsigned> MaybeMaxVF =
       CM.computeMaxVF(UserVF.getKnownMinValue(), UserIC);
   if (!MaybeMaxVF) // Cases that should not to be vectorized nor interleaved.
     return None;
 
   // Invalidate interleave groups if all blocks of loop will be predicated.
   if (CM.blockNeedsPredication(OrigLoop->getHeader()) &&
       !useMaskedInterleavedAccesses(*TTI)) {
return new VPWidenSelectRecipe(*SI, Plan->mapToVPValues(SI->operands()),
                                    InvariantCond);
   }
 
   return tryToWiden(Instr, *Plan);
 }
 
 void LoopVectorizationPlanner::buildVPlansWithVPRecipes(unsigned MinVF,
                                                         unsigned MaxVF) {
-  assert(OrigLoop->empty() && "Inner loop expected.");
+  assert(OrigLoop->isInnermost() && "Inner loop expected.");
 
   // Collect conditions feeding internal conditional branches; they need to be
   // represented in VPlan for it to model masking.
   SmallPtrSet<Value *, 1> NeedDef;
 
   auto *Latch = OrigLoop->getLoopLatch();
   for (BasicBlock *BB : OrigLoop->blocks()) {
     if (BB == Latch)
VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
   return Plan;
 }
 
 VPlanPtr LoopVectorizationPlanner::buildVPlan(VFRange &Range) {
   // Outer loop handling: They may require CFG and instruction level
   // transformations before even evaluating whether vectorization is profitable.
   // Since we cannot modify the incoming IR, we need to build VPlan upfront in
   // the vectorization pipeline.
-  assert(!OrigLoop->empty());
+  assert(!OrigLoop->isInnermost());
   assert(EnableVPlanNativePath && "VPlan-native path is not enabled.");
 
   // Create new empty VPlan
   auto Plan = std::make_unique<VPlan>();
 
   // Build hierarchical CFG
   VPlanHCFGBuilder HCFGBuilder(OrigLoop, LI, *Plan);
   HCFGBuilder.buildHierarchicalCFG();

 
 LoopVectorizePass::LoopVectorizePass(LoopVectorizeOptions Opts)
     : InterleaveOnlyWhenForced(Opts.InterleaveOnlyWhenForced ||
                                !EnableLoopInterleaving),
       VectorizeOnlyWhenForced(Opts.VectorizeOnlyWhenForced ||
                               !EnableLoopVectorization) {}
 
 bool LoopVectorizePass::processLoop(Loop *L) {
-  assert((EnableVPlanNativePath || L->empty()) &&
+  assert((EnableVPlanNativePath || L->isInnermost()) &&
          "VPlan-native path is not enabled. Only process inner loops.");
 
 #ifndef NDEBUG
   const std::string DebugLocStr = getDebugLocString(L);
 #endif /* NDEBUG */
 
   LLVM_DEBUG(dbgs() << "\nLV: Checking a loop in \""
                     << L->getHeader()->getParent()->getName() << "\" from "
#endif /* NDEBUG */
   ScalarEpilogueLowering SEL = getScalarEpilogueLowering(
       F, L, Hints, PSI, BFI, TTI, TLI, AC, LI, PSE.getSE(), DT, LVL);
 
   // Entrance to the VPlan-native vectorization path. Outer loops are processed
   // here. They may require CFG and instruction level transformations before
   // even evaluating whether vectorization is profitable. Since we cannot modify
   // the incoming IR, we need to build VPlan upfront in the vectorization
   // pipeline.
-  if (!L->empty())
+  if (!L->isInnermost())
     return processLoopInVPlanNativePath(L, PSE, LI, DT, &LVL, TTI, TLI, DB, AC,
                                         ORE, BFI, PSI, Hints);
 
-  assert(L->empty() && "Inner loop expected.");
+  assert(L->isInnermost() && "Inner loop expected.");
 
   // Check the loop for a trip count threshold: vectorize loops with a tiny trip
   // count by optimizing for size, to minimize overheads.
   auto ExpectedTC = getSmallBestKnownTC(*SE, L);
   if (ExpectedTC && *ExpectedTC < TinyTripCountVectorThreshold) {
     LLVM_DEBUG(dbgs() << "LV: Found a loop with a very small trip count. "
                       << "This loop is worth vectorizing only if no scalar "
                       << "iteration overheads are incurred.");