[LOOPGUARD] Disable loop with multiple loop exiting blocks.

[Whitney]

Summary

As discussed in the loop group meeting. With the current definition of loop guard, we should not allow multiple loop exiting blocks. For loops that has multiple loop exiting blocks, we can simply unable to find the loop guard.

When getUniqueExitBlock() obtains a vector size not equals to one, that means there is either no exit blocks or there exists more than one unique block the loop exit to.
If we don't disallow loop with multiple loop exit blocks, then with our current implementation, there can exist exit blocks don't post dominated by the non pre-header successor of the guard block.

[fhahn]

This needs a test with loops with multiple exit blocks.

[Whitney]

Add a test case with multiple loop exiting blocks.

[Whitney]

ping

[Whitney]

ping

[kbarton]

I don't remember why exactly this was necessary.
Looking at the current definition in LoopInfo.h, it's not immediately obvious to me either.
Could you either update the definition of getLoopGuardBranch in LoopInfo.h to state this case is not handled (and why). Or, if it's something obvious that I'm not seeing, expand the description here to make it clear?

Thanks.

[Meinersbur]

Any reason not to use Loop::getExitBlock()? The behavior is different when there are are multiple exiting edges to the same block, but does it matter? Maybe we should change Loop::getExitBlock() to only return nullptr if two different exit blocks exist, as e.g. getLoopPredecessor() already does.

llvm/lib/Analysis/LoopInfo.cpp

378 ↗

(On Diff #221750)

I think that getUniqueExitBlocks never adds nullptr elements anyway. However, asserts don't hurt.

[Whitney]

Any reason not to use Loop::getExitBlock()? The behavior is different when there are are multiple exiting edges to the same block, but does it matter? Maybe we should change Loop::getExitBlock() to only return nullptr if two different exit blocks exist, as e.g. getLoopPredecessor() already does.

Originally I used getExitBlock(), and found that the new test case MultiExitingLoop failed to find the loop guard, as getExitBlock() returns nullptr if there are more than one exiting block, even if all exiting blocks go to the same exit block. As the reason we want to add an early exit is because we don't check post dominations for all exit blocks, we don't need to exit early if there is only one unique exit block. I don't know if it matters, but more loops can find their guard in this way.

[Meinersbur]

LGTM

[kbarton]

LGTM.
Thanks for adding the comment.

[Meinersbur]

llvm/lib/Analysis/LoopInfo.cpp

372–375 ↗

(On Diff #221750)

There actually is a LoopBase::getUniqueExitBlock() with this code inside. Could you use that one?

[Whitney]

llvm/lib/Analysis/LoopInfo.cpp

372–375 ↗

(On Diff #221750)

Thanks for letting me know. Not sure how I could missed it.

llvm/trunk/lib/Analysis/LoopInfo.cpp

bool Loop::isAuxiliaryInductionVariable(PHINode &AuxIndVar,
 
   // Incremented by a loop invariant step for each loop iteration
   return SE.isLoopInvariant(IndDesc.getStep(), this);
 }
 
 BranchInst *Loop::getLoopGuardBranch() const {
   assert(isLoopSimplifyForm() && "Only valid for loop in simplify form");
   BasicBlock *Preheader = getLoopPreheader();
-  BasicBlock *Latch = getLoopLatch();
-  assert(Preheader && Latch &&
+  assert(Preheader && getLoopLatch() &&
          "Expecting a loop with valid preheader and latch");
-  assert(isLoopExiting(Latch) && "Only valid for rotated loop");
+  assert(isLoopExiting(getLoopLatch()) && "Only valid for rotated loop");
 
-  Instruction *LatchTI = Latch->getTerminator();
-  if (!LatchTI || LatchTI->getNumSuccessors() != 2)
+  // 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;
 
-  BasicBlock *ExitFromLatch = (LatchTI->getSuccessor(0) == getHeader())
-                                  ? LatchTI->getSuccessor(1)
-                                  : LatchTI->getSuccessor(0);
   BasicBlock *ExitFromLatchSucc = ExitFromLatch->getUniqueSuccessor();
   if (!ExitFromLatchSucc)
     return nullptr;
 
   BasicBlock *GuardBB = Preheader->getUniquePredecessor();
   if (!GuardBB)
     return nullptr;
 

llvm/trunk/unittests/Analysis/LoopInfoTest.cpp

runWithLoopInfoPlus(
         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());
       });
 }
 
+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"
+      "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
+      "for.preheader:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body.1 ]\n"
+      "  br i1 %cond, label %for.body.1, label %for.exit\n"
+      "for.body.1:\n"
+      "  %idxprom = sext i32 %i to i64\n"
+      "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
+      "  store i32 %i, i32* %arrayidx, align 4\n"
+      "  %inc = add nsw i32 %i, 1\n"
+      "  %cmp = icmp slt i32 %inc, %ub\n"
+      "  br i1 %cmp, label %for.body, label %for.exit\n"
+      "for.exit:\n"
+      "  br label %for.end\n"
+      "for.end:\n"
+      "  ret void\n"
+      "}\n";
+
+  // Parse the module.
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
+
+  runWithLoopInfoPlus(
+      *M, "foo",
+      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+        Function::iterator FI = F.begin();
+        BasicBlock *Entry = &*(FI);
+        BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
+        // First two basic block are entry and for.preheader - skip them.
+        ++FI;
+        BasicBlock *Header = &*(++FI);
+        assert(Header->getName() == "for.body");
+        Loop *L = LI.getLoopFor(Header);
+        EXPECT_NE(L, nullptr);
+
+        Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
+        EXPECT_NE(Bounds, None);
+        ConstantInt *InitialIVValue =
+            dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
+        EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
+        EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
+        ConstantInt *StepValue =
+            dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
+        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());
+      });
+}
+
+TEST(LoopInfoTest, MultiExitLoop) {
+  const char *ModuleStr =
+      "define void @foo(i32* %A, i32 %ub, i1 %cond) {\n"
+      "entry:\n"
+      "  %guardcmp = icmp slt i32 0, %ub\n"
+      "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
+      "for.preheader:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body.1 ]\n"
+      "  br i1 %cond, label %for.body.1, label %for.exit\n"
+      "for.body.1:\n"
+      "  %idxprom = sext i32 %i to i64\n"
+      "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
+      "  store i32 %i, i32* %arrayidx, align 4\n"
+      "  %inc = add nsw i32 %i, 1\n"
+      "  %cmp = icmp slt i32 %inc, %ub\n"
+      "  br i1 %cmp, label %for.body, label %for.exit.1\n"
+      "for.exit:\n"
+      "  br label %for.end\n"
+      "for.exit.1:\n"
+      "  br label %for.end\n"
+      "for.end:\n"
+      "  ret void\n"
+      "}\n";
+
+  // Parse the module.
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
+
+  runWithLoopInfoPlus(
+      *M, "foo",
+      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+        Function::iterator FI = F.begin();
+        // First two basic block are entry and for.preheader - skip them.
+        ++FI;
+        BasicBlock *Header = &*(++FI);
+        assert(Header->getName() == "for.body");
+        Loop *L = LI.getLoopFor(Header);
+        EXPECT_NE(L, nullptr);
+
+        Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
+        EXPECT_NE(Bounds, None);
+        ConstantInt *InitialIVValue =
+            dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
+        EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
+        EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
+        ConstantInt *StepValue =
+            dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
+        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());
+      });
+}
+
 TEST(LoopInfoTest, UnguardedLoop) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  br label %for.body\n"
       "for.body:\n"
       "  %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]\n"
       "  %idxprom = sext i32 %i to i64\n"