[LOOPINFO] Add member function to retrieve loops in breadth-first order

[etiotto]

Summary

LoopInfo contains a utility to retrieve loops in depth-first order (preorder traversal). This patch adds a similar utility to retrieve loops in breadth-first order.

[jdoerfert]

llvm/include/llvm/Analysis/LoopInfo.h

363

This is just a hunch but isn't this potentially expensive? What if we do not remove old elements in the worklist, e.g.:

while (Idx < Worklist.size()) {
  L = Worklist[Idx++];
  Worklist.append(L->begin(), L->end());
  BreadthFirstLoops.append(L->begin(), L->end());
}

Unrelated, why rbegin/rend? I would not associate an order in the loop levels with BFS, maybe document that there is one if you use these.

[fhahn]

AFAIK, GraphTraits is implemented for Loop and you should be able to just use breadth_first from ADT/BreadthFirstIterator.h. It should return a breadth-first iterator range over the sub loops. Given it is a one-liner, I am not sure we would need to add a special method to LoopBase.

[Meinersbur]

What's the intended use?

Test case?

[etiotto]

I can use breadth_first from ADT/BreadthFirstIterator.h to collect the loops in breadth-first order. Arguably the getLoopsInPreorder() member functions could also be removed in favor of using ADT/DepthFirstIterator.h (need to confirm whether that does a preorder traversal).

[fhahn]

In D64359#1576307, @etiotto wrote:

I can use breadth_first from ADT/BreadthFirstIterator.h to collect the loops in breadth-first order. Arguably the getLoopsInPreorder() member functions could also be removed in favor of using ADT/DepthFirstIterator.h (need to confirm whether that does a preorder traversal).

Yep, that was something I wanted to look into as a follow up.

llvm/include/llvm/Analysis/LoopInfo.h

#endif
   SmallVector<LoopT *, 4> getLoopsInPreorder() {
     SmallVector<LoopT *, 4> PreOrderLoops;
     LoopT *CurLoop = static_cast<LoopT *>(this);
     PreOrderLoops.push_back(CurLoop);
     getInnerLoopsInPreorder(*CurLoop, PreOrderLoops);
     return PreOrderLoops;
   }
 
+  /// Return all inner loops in the loop nest rooted by the loop in
+  /// breadth-first order.
+  template <class Type>
+  static void
+  getInnerLoopsInBreadthFirstOrder(const LoopT &L,
+                                   SmallVectorImpl<Type> &BreadthFirstLoops) {
+    SmallVector<LoopT *, 4> BreadthFirstWorklist;
+    BreadthFirstWorklist.push_back(const_cast<LoopT *>(&L));
+
+    while (!BreadthFirstWorklist.empty()) {
+      LoopT *L = BreadthFirstWorklist.pop_back_val();
+      const auto &SubLoops = L->getSubLoops();
+      if (!SubLoops.empty()) {
+        BreadthFirstWorklist.insert(BreadthFirstWorklist.begin(),
+                                    SubLoops.rbegin(), SubLoops.rend());
+        BreadthFirstLoops.append(SubLoops.begin(), SubLoops.end());
+      }
+    }
+  }
+
+  /// Return all loops in the loop nest rooted by the loop in breadth-first
+  /// order.
+  SmallVector<const LoopT *, 4> getLoopsInBreadthFirstOrder() const {
+    SmallVector<const LoopT *, 4> BreadthFirstLoops;
+    const LoopT *CurLoop = static_cast<const LoopT *>(this);
+    BreadthFirstLoops.push_back(CurLoop);
+    getInnerLoopsInBreadthFirstOrder(*CurLoop, BreadthFirstLoops);
+    return BreadthFirstLoops;
+  }
+  SmallVector<LoopT *, 4> getLoopsInBreadthFirstOrder() {
+    SmallVector<LoopT *, 4> BreadthFirstLoops;
+    LoopT *CurLoop = static_cast<LoopT *>(this);
+    BreadthFirstLoops.push_back(CurLoop);
+    getInnerLoopsInBreadthFirstOrder(*CurLoop, BreadthFirstLoops);
+    return BreadthFirstLoops;
+  }
+
   //===--------------------------------------------------------------------===//
   // 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