[Loop] Add isRotated method to Loop class.

[kbarton]

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.

[Meinersbur]

llvm/include/llvm/Analysis/LoopInfo.h

763

I think it would be simpler if the function would return false if there are multiple latches with the meaning that the loop is not in loop-rotated normal form.

Note that there might still be multiple exiting edges, e.g. if the latch's terminator is a switch.

I can also think a definition for rotated with multiple latches: All latches' outgoing edges that are not backedges are existing (so the property is orthogonal to simplified form), but this would probably not be useful for anything.

llvm/unittests/Analysis/LoopInfoTest.cpp

1419

[suggestion] EXPECT_FALSE(L->isRotated()) to have a negative test as well.

[kbarton]

llvm/include/llvm/Analysis/LoopInfo.h

763

I agree - I think this makes sense.

llvm/unittests/Analysis/LoopInfoTest.cpp

1419

Added LoopNotRotated test.

[kbarton]

• Return false if no latch block exists, instead of assert (based on suggestion from Meinersbur)
• Add negative test case for loop that is not rotated.

[Meinersbur]

LGTM

llvm/include/llvm/Analysis/LoopInfo.h

public:
   /// \endcode
   BranchInst *getLoopGuardBranch() const;
 
   /// Return true iff the loop is
   /// - in simplify rotated form, and
   /// - 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;
 
   /// Return true if the Loop is in LCSSA form.
   bool isLCSSAForm(DominatorTree &DT) const;
 
   /// Return true if this Loop and all inner subloops are in LCSSA form.

llvm/lib/Analysis/LoopInfo.cpp

if (!isLoopSimplifyForm())
     return nullptr;
 
   BasicBlock *Preheader = getLoopPreheader();
   BasicBlock *Latch = getLoopLatch();
   assert(Preheader && Latch &&
          "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
   // that GuardOtherSucc post dominates all exit blocks.
   BasicBlock *ExitFromLatch = getUniqueExitBlock();
   if (!ExitFromLatch)
     return nullptr;
 

llvm/unittests/Analysis/LoopInfoTest.cpp

runWithLoopInfoPlus(
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
 TEST(LoopInfoTest, LoopWithInverseGuardSuccs) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %guardcmp = icmp sge i32 0, %ub\n"
runWithLoopInfoPlus(
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
 TEST(LoopInfoTest, LoopWithSwappedGuardCmp) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %guardcmp = icmp sgt i32 %ub, 0\n"
runWithLoopInfoPlus(
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
 TEST(LoopInfoTest, LoopWithInverseLatchSuccs) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %guardcmp = icmp slt i32 0, %ub\n"
runWithLoopInfoPlus(
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
 TEST(LoopInfoTest, LoopWithLatchCmpNE) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %guardcmp = icmp slt i32 0, %ub\n"
runWithLoopInfoPlus(
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
 TEST(LoopInfoTest, LoopWithGuardCmpSLE) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %ubPlusOne = add i32 %ub, 1\n"
runWithLoopInfoPlus(
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ubPlusOne");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
 TEST(LoopInfoTest, LoopNonConstantStep) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub, i32 %step) {\n"
       "entry:\n"
       "  %guardcmp = icmp slt i32 0, %ub\n"
runWithLoopInfoPlus(
         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
         EXPECT_EQ(Bounds->getStepValue()->getName(), "step");
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Unknown);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
 TEST(LoopInfoTest, LoopUnsignedBounds) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %guardcmp = icmp ult i32 0, %ub\n"
runWithLoopInfoPlus(
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_ULT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
 TEST(LoopInfoTest, DecreasingLoop) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %guardcmp = icmp slt i32 0, %ub\n"
runWithLoopInfoPlus(
             dyn_cast<ConstantInt>(&Bounds->getFinalIVValue());
         EXPECT_TRUE(FinalIVValue && FinalIVValue->isZero());
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SGT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Decreasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
 TEST(LoopInfoTest, CannotFindDirection) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub, i32 %step) {\n"
       "entry:\n"
       "  %guardcmp = icmp slt i32 0, %ub\n"
runWithLoopInfoPlus(
         EXPECT_EQ(Bounds->getStepValue()->getName(), "step");
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(),
                   ICmpInst::BAD_ICMP_PREDICATE);
         EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Unknown);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
 TEST(LoopInfoTest, ZextIndVar) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %guardcmp = icmp slt i32 0, %ub\n"
runWithLoopInfoPlus(
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "wide.trip.count");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_NE);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "indvars.iv");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
 TEST(LoopInfoTest, MultiExitingLoop) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub, i1 %cond) {\n"
       "entry:\n"
       "  %guardcmp = icmp slt i32 0, %ub\n"
runWithLoopInfoPlus(
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), nullptr);
         EXPECT_FALSE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
 TEST(LoopInfoTest, UnguardedLoopWithControlFlow) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub, i1 %cond) {\n"
       "entry:\n"
       "  br i1 %cond, label %for.preheader, label %for.end\n"
runWithLoopInfoPlus(
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
 TEST(LoopInfoTest, LoopNest) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %guardcmp = icmp slt i32 0, %ub\n"
runWithLoopInfoPlus(
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         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.
         ++FI;
         Header = &*(++FI);
         assert(Header->getName() == "for.inner");
         L = LI.getLoopFor(Header);
         EXPECT_NE(L, nullptr);
 
         Optional<Loop::LoopBounds> InnerBounds = L->getBounds(SE);
         EXPECT_NE(InnerBounds, None);
         InitialIVValue =
             dyn_cast<ConstantInt>(&InnerBounds->getInitialIVValue());
         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
         EXPECT_EQ(InnerBounds->getStepInst().getName(), "inc");
         StepValue = dyn_cast_or_null<ConstantInt>(InnerBounds->getStepValue());
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(InnerBounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(InnerBounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(InnerBounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
         EXPECT_EQ(L->getLoopGuardBranch(), InnerGuard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
 TEST(LoopInfoTest, AuxiliaryIV) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %guardcmp = icmp slt i32 0, %ub\n"
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));
         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
         EXPECT_TRUE(L->isGuarded());
+        EXPECT_TRUE(L->isRotated());
       });
 }
 
 TEST(LoopInfoTest, LoopNotInSimplifyForm) {
   const char *ModuleStr =
       "define void @foo(i32 %n) {\n"
       "entry:\n"
       "  %guard.cmp = icmp sgt i32 %n, 0\n"
runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
     SmallVector<BasicBlock *, 2> Exits;
     // This loop has 2 unique exits.
     L->getUniqueExitBlocks(Exits);
     EXPECT_TRUE(Exits.size() == 2);
     // And one unique non latch exit.
     Exits.clear();
     L->getUniqueNonLatchExitBlocks(Exits);
     EXPECT_TRUE(Exits.size() == 1);
   });
 }
 
 // Regression test for  getUniqueNonLatchExitBlocks functions.
 // It should detect the exit if it comes from both latch and non-latch blocks.
 TEST(LoopInfoTest, LoopNonLatchUniqueExitBlocks) {
   const char *ModuleStr =
       "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
       "define void @foo(i32 %n, i1 %cond) {\n"
runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
     L->getUniqueExitBlocks(Exits);
     EXPECT_TRUE(Exits.size() == 1);
     // And one unique non latch exit.
     Exits.clear();
     L->getUniqueNonLatchExitBlocks(Exits);
     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());
+  });
+}