[Loop] Add isRotated method to Loop class.

Summary:
This patch adds a method to determine if a loop is in rotated form (the latch is
an exiting block). It also modifies the getLoopGuardBranch method to use this
new method. This method can also be used in Loopfusion. Once this patch lands I
will make the corresponding changes there.

Reviewers: jdoerfert, Meinersbur, dmgreen, etiotto, Whitney, fhahn, hfinkel

Reviewed By: Meinersbur

Subscribers: hiraditya, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D65958

3 files changed, 63 insertions, 1 deletions

diff --git a/llvm/include/llvm/Analysis/LoopInfo.h b/llvm/include/llvm/Analysis/LoopInfo.h
index 30add2789f8..5012f68b3eb 100644
--- a/llvm/include/llvm/Analysis/LoopInfo.h
+++ b/llvm/include/llvm/Analysis/LoopInfo.h
@@ -756,6 +756,13 @@ public:
   /// - guarded by a loop guard branch.
   bool isGuarded() const { return (getLoopGuardBranch() != nullptr); }
 
+  /// Return true if the loop is rotated
+  bool isRotated() const {
+    assert(!isInvalid() && "Loop not in a valid state!");
+    BasicBlock *Latch = getLoopLatch();
+    return Latch && isLoopExiting(Latch);
+  }
+
   /// Return true if the loop induction variable starts at zero and increments
   /// by one each time through the loop.
   bool isCanonical(ScalarEvolution &SE) const;
diff --git a/llvm/lib/Analysis/LoopInfo.cpp b/llvm/lib/Analysis/LoopInfo.cpp
index 3e3303cbb02..e67e1ae0875 100644
--- a/llvm/lib/Analysis/LoopInfo.cpp
+++ b/llvm/lib/Analysis/LoopInfo.cpp
@@ -371,7 +371,7 @@ BranchInst *Loop::getLoopGuardBranch() const {
          "Expecting a loop with valid preheader and latch");
 
   // Loop should be in rotate form.
-  if (!isLoopExiting(Latch))
+  if (!isRotated())
     return nullptr;
 
   // Disallow loops with more than one unique exit block, as we do not verify
diff --git a/llvm/unittests/Analysis/LoopInfoTest.cpp b/llvm/unittests/Analysis/LoopInfoTest.cpp
index 5504ac11240..8873684879e 100644
--- a/llvm/unittests/Analysis/LoopInfoTest.cpp
+++ b/llvm/unittests/Analysis/LoopInfoTest.cpp
@@ -285,6 +285,7 @@ TEST(LoopInfoTest, CanonicalLoop) {
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
@@ -343,6 +344,7 @@ TEST(LoopInfoTest, LoopWithInverseGuardSuccs) {
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
@@ -401,6 +403,7 @@ TEST(LoopInfoTest, LoopWithSwappedGuardCmp) {
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
@@ -459,6 +462,7 @@ TEST(LoopInfoTest, LoopWithInverseLatchSuccs) {
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
@@ -517,6 +521,7 @@ TEST(LoopInfoTest, LoopWithLatchCmpNE) {
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
@@ -576,6 +581,7 @@ TEST(LoopInfoTest, LoopWithGuardCmpSLE) {
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
@@ -631,6 +637,7 @@ TEST(LoopInfoTest, LoopNonConstantStep) {
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
@@ -689,6 +696,7 @@ TEST(LoopInfoTest, LoopUnsignedBounds) {
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
@@ -747,6 +755,7 @@ TEST(LoopInfoTest, DecreasingLoop) {
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
@@ -804,6 +813,7 @@ TEST(LoopInfoTest, CannotFindDirection) {
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
@@ -865,6 +875,7 @@ TEST(LoopInfoTest, ZextIndVar) {
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "indvars.iv");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
@@ -1037,6 +1048,7 @@ TEST(LoopInfoTest, UnguardedLoop) {
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), nullptr);
         EXPECT_FALSE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
@@ -1094,6 +1106,7 @@ TEST(LoopInfoTest, UnguardedLoopWithControlFlow) {
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
@@ -1164,6 +1177,7 @@ TEST(LoopInfoTest, LoopNest) {
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "j");
         EXPECT_EQ(L->getLoopGuardBranch(), OuterGuard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
 
         // Next two basic blocks are for.outer and for.inner.preheader - skip
         // them.
@@ -1188,6 +1202,7 @@ TEST(LoopInfoTest, LoopNest) {
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), InnerGuard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
@@ -1269,6 +1284,7 @@ TEST(LoopInfoTest, AuxiliaryIV) {
             L->isAuxiliaryInductionVariable(Instruction_mulopcode, SE));
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
@@ -1445,3 +1461,42 @@ TEST(LoopInfoTest, LoopNonLatchUniqueExitBlocks) {
     EXPECT_TRUE(Exits.size() == 1);
   });
 }
+
+// Test that a pointer-chasing loop is not rotated.
+TEST(LoopInfoTest, LoopNotRotated) {
+  const char *ModuleStr =
+      "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
+      "define void @foo(i32* %elem) {\n"
+      "entry:\n"
+      "  br label %while.cond\n"
+      "while.cond:\n"
+      "  %elem.addr.0 = phi i32* [ %elem, %entry ], [ %incdec.ptr, %while.body "
+      "]\n"
+      "  %tobool = icmp eq i32* %elem.addr.0, null\n"
+      "  br i1 %tobool, label %while.end, label %while.body\n"
+      "while.body:\n"
+      "  %incdec.ptr = getelementptr inbounds i32, i32* %elem.addr.0, i64 1\n"
+      "  br label %while.cond\n"
+      "while.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() == "while.cond");
+    Loop *L = LI.getLoopFor(Header);
+    EXPECT_NE(L, nullptr);
+
+    // This loop is in simplified form.
+    EXPECT_TRUE(L->isLoopSimplifyForm());
+
+    // This loop is not rotated.
+    EXPECT_FALSE(L->isRotated());
+  });
+}