[LoopGuard] Instructions in loop preheader and loop exit must be safe to execute speculatively.

[Whitney]

Summary

Disallow loops with preheader or exit block which contains instructions that are not safe to execute speculatively to be considered as guarded loop.

[fhahn]

I think this restriction needs to be at least documented. But what's the reason for this restriction? Unless I am missing something, even if the instructions between the guard and the loop are not safe to speculate, the guard condition still applies to the loop, right?

[Whitney]

Added comments to explain why the preheader and exit block should not contain instructions which are not safe to execute speculatively.

[Whitney]

I think this restriction needs to be at least documented. But what's the reason for this restriction? Unless I am missing something, even if the instructions between the guard and the loop are not safe to speculate, the guard condition still applies to the loop, right?

Good point, it should be documented, changed the description in the .h file. Added a comment in the code to explain the reason. Right, the guard condition still applies to the loop, but let say in the preheader there exists an instruction which throw, then the loop is not executed even if it entered the guarded region.

If I understand correctly, this is what people agreed upon in the loop group meeting. People want to start with a restricted definition and loose it as time goes by. I should have restrict the instructions allowed in preheader and exit block when I first introduce the loop guard, accidentally did not. People also agreed to allow basic blocks without control flow and without unsafe instructions in between GuardBB and Preheader, and between ExitFromLatch and GuardOtherSucc, which I will implement in the later PR. I am open to re-discuss the definition of a loop guard in the loop group meeting if that's required.

[Whitney]

clarify the comment.

[reames]

This doesn't make sense to me. I don't see why we need the speculation restriction here. The discussion mentions concern about side exits, but if so, that's a different property. (i.e. isGuaranteedToTransferToSuccessor)

This also needs more background as to motivation. Motivating use case? Link to a review would be ideal.

[Whitney]

This doesn't make sense to me. I don't see why we need the speculation restriction here. The discussion mentions concern about side exits, but if so, that's a different property. (i.e. isGuaranteedToTransferToSuccessor)

You are right, I should use isGuaranteedToTransferExecutionToSuccessor instead of IsSafeToSpeculativelyExecute.

This also needs more background as to motivation. Motivating use case? Link to a review would be ideal.

The reason I am doing this PR is because I noticed that I forgot about this restriction in my original implementation (is my mistake). This PR is making the definition of loop guard more restricted, which means less loops would be considered as guarded. The previous review is https://reviews.llvm.org/D63885, but the decision of the definition of loop guard is made in the loop group meeting. I am ok to leave the definition of loop guard as is (before this patch) if that's what everyone preferred.

[Whitney]

use isGuaranteedToTransferExecutionToSuccessor instead of IsSafeToSpeculativelyExecute

[Meinersbur]

llvm/lib/Analysis/LoopInfo.cpp

402–405

This applies to the preheader, but if an instruction throws in ExitFromLatch, the loop has been executed.

I am not arguing that ExitFromLatch should allow side-effect instructions, but we should correctly justify why not.

llvm/unittests/Analysis/LoopInfoTest.cpp

1504

[typo] "becuase"

1505

[style] indention

[Whitney]

[NFC] Update comment and fix typos.

[Meinersbur]

I am ok with this patch. @fhahn what do you think?

[fhahn]

In D71383#1784566, @Meinersbur wrote:

I am ok with this patch. @fhahn what do you think?

I think the patch still misses a description of the motivation for the restriction in getLoopGuardBranch. I see why the restriction would be helpful for LoopFusion, but it seems like there could be other uses cases that do not require that restriction (e.g. if one wants to use the guard for reasoning about values in the loop).

[Whitney]

I did a test with a loop that has a call which may throw inside, and SCEV is able to calculate the trip count, add recurrence of the induction variable, etc. Maybe we can keep getLoopGuardBranch() as is, and not worry about instructions which not guaranteed to transfer execution to successors? What do you think @Meinersbur?

[Meinersbur]

In D71383#1786225, @Whitney wrote:

I did a test with a loop that has a call which may throw inside, and SCEV is able to calculate the trip count, add recurrence of the induction variable, etc. Maybe we can keep getLoopGuardBranch() as is, and not worry about instructions which not guaranteed to transfer execution to successors? What do you think @Meinersbur?

I was assuming you need this change for your use case. If getLoopGuardBranch already fits your use case, I indeed do not see a reason to change it?

llvm/lib/Analysis/LoopInfo.cpp

402–405

Btw, nothing guarantees that the loop itself is exiting, hence ExitFromLatchSucc may still not be executed.

[Whitney]

I was assuming you need this change for your use case. If getLoopGuardBranch already fits your use case, I indeed do not see a reason to change it?

I actually don't need this change. My motivation is only to make it closer to what we discussed in the loop opt meeting.
If I don't see any objection, I will cancel this patch and keep getLoopGuardBranch as is. Thanks everyone for spending the time to review it.

llvm/include/llvm/Analysis/LoopInfo.h

public:
   ///  ...
   ///   br Latch
   /// Latch:
   ///   br cond2, Header, ExitBlock
   /// ExitBlock:
   ///   br ExitSucc
   /// ExitSucc:
   /// \endcode
+  /// where Preheader and ExitBlock do not contain instructions which are not
+  /// guaranteed to transfer execution to successors.
   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

llvm/lib/Analysis/LoopInfo.cpp

BranchInst *Loop::getLoopGuardBranch() const {
 
   BranchInst *GuardBI = dyn_cast<BranchInst>(GuardBB->getTerminator());
   if (!GuardBI || GuardBI->isUnconditional())
     return nullptr;
 
   BasicBlock *GuardOtherSucc = (GuardBI->getSuccessor(0) == Preheader)
                                    ? GuardBI->getSuccessor(1)
                                    : GuardBI->getSuccessor(0);
-  return (GuardOtherSucc == ExitFromLatchSucc) ? GuardBI : nullptr;
+  if (GuardOtherSucc != ExitFromLatchSucc)
+    return nullptr;
+
+  // If the loop preheader contains instructions which are not guaranteed to
+  // transfer execution to successors (e.g. instructions that throw), then loop
+  // guard doesn't guarantee the execution of the loop it is guarding.
+  // Similarly, if the loop exit block contains instructions which are not
+  // guaranteed to transfer exeution to successors, then exiting the loop
+  // doesn't guaratee to enter the block its loop guard exits to (i.e.
+  // GuardOtherSucc).
+  return (isGuaranteedToTransferExecutionToSuccessor(Preheader) &&
+          isGuaranteedToTransferExecutionToSuccessor(ExitFromLatch))
+             ? GuardBI
+             : nullptr;
 }
 
 bool Loop::isCanonical(ScalarEvolution &SE) const {
   InductionDescriptor IndDesc;
   if (!getInductionDescriptor(SE, IndDesc))
     return false;
 
   ConstantInt *Init = dyn_cast_or_null<ConstantInt>(IndDesc.getStartValue());

llvm/unittests/Analysis/LoopInfoTest.cpp

runWithLoopInfoPlus(
         BasicBlock *Header = &*(++FI);
         BasicBlock *Latch = &*(++FI);
         assert(Header && "No header");
         Loop *L = LI.getLoopFor(Header);
         EXPECT_NE(L, nullptr);
         EXPECT_TRUE(L->isLoopSimplifyForm());
         EXPECT_EQ(L->getLoopLatch(), Latch);
         EXPECT_FALSE(L->isLoopExiting(Latch));
-        // No loop guard becuase loop is not exiting on latch.
+        // No loop guard because loop is not exiting on latch.
+        EXPECT_EQ(L->getLoopGuardBranch(), nullptr);
+        EXPECT_FALSE(L->isGuarded());
+      });
+}
+
+TEST(LoopInfoTest, LoopPreheaderNotSafe) {
+  const char *ModuleStr =
+      "define void @foo(i64 %N) {\n"
+      "entry:\n"
+      "  %guard = icmp slt i64 0, %N\n"
+      "  br i1 %guard, label %for.preheader, label %for.end\n"
+      "for.preheader:\n"
+      "  call void @bar()\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %i = phi i64 [ %inc, %for.body ], [ 0, %for.preheader ]\n"
+      "  call void @bar()\n"
+      "  %inc = add nsw i64 %i, 1\n"
+      "  %cmp = icmp slt i64 %inc, %N\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"
+      "declare void @bar()\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 && "No header");
+        Loop *L = LI.getLoopFor(Header);
+        EXPECT_NE(L, nullptr);
+        EXPECT_TRUE(L->isLoopSimplifyForm());
+
+        // No loop guard because loop preheader contains instructions not safe
+        // to execute speculatively.
+        EXPECT_EQ(L->getLoopGuardBranch(), nullptr);
+        EXPECT_FALSE(L->isGuarded());
+      });
+}
+
+TEST(LoopInfoTest, LoopExitNotSafe) {
+  const char *ModuleStr =
+      "define void @foo(i64 %N) {\n"
+      "entry:\n"
+      "  %guard = icmp slt i64 0, %N\n"
+      "  br i1 %guard, label %for.preheader, label %for.end\n"
+      "for.preheader:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %i = phi i64 [ %inc, %for.body ], [ 0, %for.preheader ]\n"
+      "  call void @bar()\n"
+      "  %inc = add nsw i64 %i, 1\n"
+      "  %cmp = icmp slt i64 %inc, %N\n"
+      "  br i1 %cmp, label %for.body, label %for.exit\n"
+      "for.exit:\n"
+      "  call void @bar()\n"
+      "  br label %for.end\n"
+      "for.end:\n"
+      "  ret void\n"
+      "}\n"
+      "declare void @bar()\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 && "No header");
+        Loop *L = LI.getLoopFor(Header);
+        EXPECT_NE(L, nullptr);
+        EXPECT_TRUE(L->isLoopSimplifyForm());
+
+        // No loop guard because loop exit contains instructions not safe to
+        // execute speculatively.
         EXPECT_EQ(L->getLoopGuardBranch(), nullptr);
         EXPECT_FALSE(L->isGuarded());
       });
 }
 
 // Examine getUniqueExitBlocks/getUniqueNonLatchExitBlocks functions.
 TEST(LoopInfoTest, LoopUniqueExitBlocks) {
   const char *ModuleStr =
runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
     // First basic block is entry - skip it.
     BasicBlock *Header = &*(++FI);
     assert(Header->getName() == "for.cond");
     Loop *L = LI.getLoopFor(Header);
 
     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.