[LoopInfo] Extend getExitEdges API

[skatkov]

Summary

Add an ability to provide an output argument to store loop exit edges
with pair of const and non-const BasicBlocks.

[fhahn]

include/llvm/Analysis/LoopInfo.h

282

Is there a reason why the implementation was moved to here? Could it stay in LoopInfoImpl.h?

[skatkov]

include/llvm/Analysis/LoopInfo.h

282

Yes, there is a reason. To support both const and non-const ParamBlockT in SmallVector argument I introduced the new template parameter ParamBockT. As a result if I keep the implementation in LoopInfoImpl.h I have a compilation error due to users includes this header. So the movement to this header is required.

[fhahn]

include/llvm/Analysis/LoopInfo.h

282

On second thought, it looks like getExitEdges has only a single user, so maybe it would be better to just change the original API from const to non-const and update LoopPredication?

This would be in line with most of the other APIs, that already return non-const BlockT*, exactly for the reason that most APIs expect non-const blocks.

[skatkov]

include/llvm/Analysis/LoopInfo.h

282

I can do this.
I just wonder what wrong with movement of this code from LoopInfoImpl.h to LoopInfo.h and support both const and non-const cases?

[fhahn]

include/llvm/Analysis/LoopInfo.h

282

Nothing per-se, IMO it is just slightly preferable to keep the changes as simple as possible/required; and given most other functions in LoopBase already return non-const, it seems reasonable to bring getExitEdges in line.

(Potential drawbacks are increased compile-time/size, as LoopInfo.h is widely used and it adds an additional step to git-blame)

[reames]

Given all the other APIs on this class work in terms of BlockT*, not const BlockT*, I think it would be more consistent to just change the definition of Edge in this case. The one caller should be trivial to update.

In theory, being const correct is better, but consistency in the code overrides to me.

If you want to make the suggested change to Edge, feel free to submit without further review.

[skatkov]

Abandon in favor of https://reviews.llvm.org/D64309

include/llvm/Analysis/LoopInfo.h

#endif
   /// 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;
+  template <class ParamBlockT>
+  void getExitEdges(SmallVectorImpl<std::pair<ParamBlockT *, ParamBlockT *> > &
+                        ExitEdges) const {
+    // Assert that ParamBlockT and BlockT are the same +/- const qualifier.
+    static_assert(
+        std::is_same<typename std::remove_const<BlockT>::type,
+                     typename std::remove_const<ParamBlockT>::type>::value,
+        "not same!");
+    assert(!isInvalid() && "Loop not in a valid state!");
+    for (const auto BB : blocks())
+      for (const auto &Succ : children<BlockT *>(BB))
+        if (!contains(Succ))
+          // Not in current loop? It must be an exit block.
+          ExitEdges.emplace_back(BB, Succ);
+  }
 
   /// 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;

include/llvm/Analysis/LoopInfoImpl.h

 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))
-        // Not in current loop? It must be an exit block.
-        ExitEdges.emplace_back(BB, Succ);
-}
-
 /// getLoopPreheader - 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 and it is legal to hoist instructions into the
 /// predecessor. 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.
 ///

unittests/Analysis/LoopInfoTest.cpp

runWithLoopInfoPlus(
         PHINode &Instruction_usedoutside = cast<PHINode>(*(++II));
         EXPECT_FALSE(
             L->isAuxiliaryInductionVariable(Instruction_usedoutside, SE));
         PHINode &Instruction_mulopcode = cast<PHINode>(*(++II));
         EXPECT_FALSE(
             L->isAuxiliaryInductionVariable(Instruction_mulopcode, SE));
       });
 }
+
+// Check that getExitEdges works for both const and non const ExitEdges param.
+TEST(LoopInfoTest, LoopGetExitEdges) {
+  const char *ModuleStr =
+      "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
+      "define void @foo(i32 %n) {\n"
+      "entry:\n"
+      "  br i1 undef, label %for.cond, label %for.end\n"
+      "for.cond:\n"
+      "  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n"
+      "  %cmp = icmp slt i32 %i.0, %n\n"
+      "  br i1 %cmp, label %for.inc, label %for.end\n"
+      "for.inc:\n"
+      "  %inc = add nsw i32 %i.0, 1\n"
+      "  br label %for.cond\n"
+      "for.end:\n"
+      "  ret void\n"
+      "}\n";
+
+  // Parse the module.
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
+
+  runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
+    Function::iterator FI = F.begin();
+    // First basic block is entry - skip it.
+    BasicBlock *Header = &*(++FI);
+    assert(Header->getName() == "for.cond");
+    Loop *L = LI.getLoopFor(Header);
+
+    SmallVector<std::pair<BasicBlock *, BasicBlock *>, 1> NonConstExitEdges;
+    SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 1>
+    ConstExitEdges;
+    // Get Loop Edges.
+    L->getExitEdges(NonConstExitEdges);
+    L->getExitEdges(ConstExitEdges);
+
+    // Check result.
+    EXPECT_TRUE(NonConstExitEdges.size() == 1);
+    EXPECT_TRUE(ConstExitEdges.size() == 1);
+  });
+}