[LoopInfo] Port loop exit interfaces from Loop to LoopBase

[dcaballe]

Summary

This patch ports hasDedicatedExits, getUniqueExitBlocks and
getUniqueExitBlock in Loop to LoopBase so that they can be used
from other LoopBase sub-classes. GraphTraits are used to replace the
BasicBlock specific code in the original implementation. These
three interfaces are needed in VPLoop (VPlan).

[chandlerc]

Minor cleanups, and then this should be good.

BTW, do you have commit access?

include/llvm/Analysis/LoopInfoImpl.h

85–86 ↗

(On Diff #153669)

Delete - this is a stale doxygen commment, and the API is documented in the header.

101–104 ↗

(On Diff #153669)

Delete, same as above.

150–151 ↗

(On Diff #153669)

Delete, same as above.

[dcaballe]

Addressing Chandler's comments. Thanks, Chandler!
Yes, I have commit access.

[chandlerc]

LGTM

llvm/trunk/include/llvm/Analysis/LoopInfo.h

#endif
   /// 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
public:
   /// 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();
 
-  /// 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<BasicBlock *> &ExitBlocks) const;
-
-  /// If getUniqueExitBlocks would return exactly one block, return that block.
-  /// Otherwise return null.
-  BasicBlock *getUniqueExitBlock() const;
-
   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.

llvm/trunk/include/llvm/Analysis/LoopInfoImpl.h

BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
   assert(!isInvalid() && "Loop not in a valid state!");
   SmallVector<BlockT *, 8> ExitBlocks;
   getExitBlocks(ExitBlocks);
   if (ExitBlocks.size() == 1)
     return ExitBlocks[0];
   return nullptr;
 }
 
+template <class BlockT, class LoopT>
+bool LoopBase<BlockT, LoopT>::hasDedicatedExits() const {
+  // Each predecessor of each exit block of a normal loop is contained
+  // within the loop.
+  SmallVector<BlockT *, 4> ExitBlocks;
+  getExitBlocks(ExitBlocks);
+  for (BlockT *EB : ExitBlocks)
+    for (BlockT *Predecessor : children<Inverse<BlockT *>>(EB))
+      if (!contains(Predecessor))
+        return false;
+  // All the requirements are met.
+  return true;
+}
+
+template <class BlockT, class LoopT>
+void LoopBase<BlockT, LoopT>::getUniqueExitBlocks(
+    SmallVectorImpl<BlockT *> &ExitBlocks) const {
+  typedef GraphTraits<BlockT *> BlockTraits;
+  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
+
+  assert(hasDedicatedExits() &&
+         "getUniqueExitBlocks assumes the loop has canonical form exits!");
+
+  SmallVector<BlockT *, 32> SwitchExitBlocks;
+  for (BlockT *Block : this->blocks()) {
+    SwitchExitBlocks.clear();
+    for (BlockT *Successor : children<BlockT *>(Block)) {
+      // If block is inside the loop then it is not an exit block.
+      if (contains(Successor))
+        continue;
+
+      BlockT *FirstPred = *InvBlockTraits::child_begin(Successor);
+
+      // If current basic block is this exit block's first predecessor then only
+      // insert exit block in to the output ExitBlocks vector. This ensures that
+      // same exit block is not inserted twice into ExitBlocks vector.
+      if (Block != FirstPred)
+        continue;
+
+      // If a terminator has more then two successors, for example SwitchInst,
+      // then it is possible that there are multiple edges from current block to
+      // one exit block.
+      if (std::distance(BlockTraits::child_begin(Block),
+                        BlockTraits::child_end(Block)) <= 2) {
+        ExitBlocks.push_back(Successor);
+        continue;
+      }
+
+      // In case of multiple edges from current block to exit block, collect
+      // only one edge in ExitBlocks. Use switchExitBlocks to keep track of
+      // duplicate edges.
+      if (!is_contained(SwitchExitBlocks, Successor)) {
+        SwitchExitBlocks.push_back(Successor);
+        ExitBlocks.push_back(Successor);
+      }
+    }
+  }
+}
+
+template <class BlockT, class LoopT>
+BlockT *LoopBase<BlockT, LoopT>::getUniqueExitBlock() const {
+  SmallVector<BlockT *, 8> UniqueExitBlocks;
+  getUniqueExitBlocks(UniqueExitBlocks);
+  if (UniqueExitBlocks.size() == 1)
+    return UniqueExitBlocks[0];
+  return nullptr;
+}
+
 /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
 template <class BlockT, class LoopT>
 void LoopBase<BlockT, LoopT>::getExitEdges(
     SmallVectorImpl<Edge> &ExitEdges) const {
   assert(!isInvalid() && "Loop not in a valid state!");
   for (const auto BB : blocks())
     for (const auto &Succ : children<BlockT *>(BB))
       if (!contains(Succ))

llvm/trunk/lib/Analysis/LoopInfo.cpp

Loop::LocRange Loop::getLocRange() const {
   // If we have no pre-header or there are no instructions with debug
   // info in it, try the header.
   if (BasicBlock *HeadBB = getHeader())
     return LocRange(HeadBB->getTerminator()->getDebugLoc());
 
   return LocRange();
 }
 
-bool Loop::hasDedicatedExits() const {
-  // Each predecessor of each exit block of a normal loop is contained
-  // within the loop.
-  SmallVector<BasicBlock *, 4> ExitBlocks;
-  getExitBlocks(ExitBlocks);
-  for (BasicBlock *BB : ExitBlocks)
-    for (BasicBlock *Predecessor : predecessors(BB))
-      if (!contains(Predecessor))
-        return false;
-  // All the requirements are met.
-  return true;
-}
-
-void Loop::getUniqueExitBlocks(
-    SmallVectorImpl<BasicBlock *> &ExitBlocks) const {
-  assert(hasDedicatedExits() &&
-         "getUniqueExitBlocks assumes the loop has canonical form exits!");
-
-  SmallVector<BasicBlock *, 32> SwitchExitBlocks;
-  for (BasicBlock *BB : this->blocks()) {
-    SwitchExitBlocks.clear();
-    for (BasicBlock *Successor : successors(BB)) {
-      // If block is inside the loop then it is not an exit block.
-      if (contains(Successor))
-        continue;
-
-      pred_iterator PI = pred_begin(Successor);
-      BasicBlock *FirstPred = *PI;
-
-      // If current basic block is this exit block's first predecessor
-      // then only insert exit block in to the output ExitBlocks vector.
-      // This ensures that same exit block is not inserted twice into
-      // ExitBlocks vector.
-      if (BB != FirstPred)
-        continue;
-
-      // If a terminator has more then two successors, for example SwitchInst,
-      // then it is possible that there are multiple edges from current block
-      // to one exit block.
-      if (succ_size(BB) <= 2) {
-        ExitBlocks.push_back(Successor);
-        continue;
-      }
-
-      // In case of multiple edges from current block to exit block, collect
-      // only one edge in ExitBlocks. Use switchExitBlocks to keep track of
-      // duplicate edges.
-      if (!is_contained(SwitchExitBlocks, Successor)) {
-        SwitchExitBlocks.push_back(Successor);
-        ExitBlocks.push_back(Successor);
-      }
-    }
-  }
-}
-
-BasicBlock *Loop::getUniqueExitBlock() const {
-  SmallVector<BasicBlock *, 8> UniqueExitBlocks;
-  getUniqueExitBlocks(UniqueExitBlocks);
-  if (UniqueExitBlocks.size() == 1)
-    return UniqueExitBlocks[0];
-  return nullptr;
-}
-
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
 
 LLVM_DUMP_METHOD void Loop::dumpVerbose() const {
   print(dbgs(), /*Depth=*/0, /*Verbose=*/true);
 }
 #endif