[MustExecute] Fix algorithmic bug in isGuaranteedToExecute. PR38514

[mkazantsev]

Summary

The description of isGuaranteedToExecute does not correspond to its implementation.
According to description, it should return true if an instruction is executed under the
assumption that its loop is *entered*. However there is a sophisticated alrogithm inside
that tries to prove that the instruction is executed if the loop is *exited*, which is not the
same thing for infinite loops. There is an attempt to protect from dealing with infinite loops
by prohibiting loops without exit blocks, however an infinite loop can have exit blocks.

As result of that, MustExecute can falsely consider some blocks that are never entered as
mustexec, and LICM can hoist dangerous instructions out of them basing on this fact.
This may introduce UB to programs which did not contain it initially.

This patch removes the problematic algorithm and replaced it with a one which tries to
prove what is required in description.

[reames]

Max, let's discuss offline. The approach taken here would work, but I'm worried about the change in algorithmic complexity. I think we can probably find a narrower fix here.

Separately from the bug fix, using an approach like this might be interesting for better opt quality.

[mkazantsev]

We can easily avoid complexity growth by caching transitive predecessors of each block. It takes O(N^2) memory, but makes collection of preds an amortized O(N) operation. We can as well cache the returned values, making the entire algorithm amortized O(N^2).

I just don't think it's a really good idea to consume that much memory for a task like that. But off course, let's discuss offline.

[mkazantsev]

BTW, after giving it some more thought, the complexity of the old algorithm is O(Exiting blocks in loop), and the new one is O(Predecessors of a block). I'm not sure if it is a growth at all, not clear which number is bigger on average.

[mkazantsev]

Actually I've checked getExitBlocks and it simply iterates through all loop blocks and checks its successors. So the complexity of the old algorithm is O(NumAllBlocks+ NumSuccessorsOfAllBlocks). The new algorithm collects transitive predecessors of a block and checks their successors, so its complexity is O(NumPredecessors+ NumSuccessorsOfPredecessors). Which is strictly not greater than the old algorithm. So this patch reduces complexity, not increases it. :)

[skatkov]

lib/Analysis/MustExecute.cpp

197

I would say this comment is a bit messy. Instead, I would suggest to update the comment before the first loop which is pretty clear to add an info that we could also handle not only exit blocks but also loop blocks but CanProveNotTakenFirstIteration is written to support only exit blocks. Another to do might be to support not only 1st iteration but others as well. But it will significantly increase the complexity of your algorithm.

[mkazantsev]

Rebased.

[reames]

Max convinced me that there's no algorithmic complexity change implied here. Given the getLoopExits code walks all edges leaving blocks in the loop, both the old and new code is O(outbound edges of blocks in loop).

I've added a bunch of code comments, but I am anticipating approving this once those details are fixed.

lib/Analysis/MustExecute.cpp

118

Separate and land please.

167

Add to the end of your comment: This set will be a subset of the blocks within the loop.

170

What you have here is fine, but it might be cleaner to write this as:
Worklist.push_back(BB);
do {
} while (!Worklist.empty())

172

I think you meant push_back(Pred) here.

177

Add to comment: and don't want to leave the loop.

180

Minor: One slightly non-obvious piece is that there can be cycles *within* a loop. Either sub-loops or non-loop cycles. The code does appear to handle that case, but might be worth a comment/test.

201

There's a subtlety here that may justify a comment or code structure change. Specifically, we don't know that this particular path (out of the possible paths we identified) is taken on the first iteration. So why is discharging the condition on that particular path on the first iterations sufficient? Answer: because it implies that either a) this path is taken on the first iteration (and thus the exit isn't) or be another path is taken by the first iteration and by the time we execute this path, the instruction of interest has already executed.

[mkazantsev]

lib/Analysis/MustExecute.cpp

172

Errr, yes. Thanks for pointing out!

[mkazantsev]

Addressed comments, added one more test.

lib/Analysis/MustExecute.cpp

201

I tried to elaborate the comment, hope it expresses the same idea.

[reames]

LGTM

Thinking about it, I think it may be worth introducing a separate isGuaranteedToExecuteBeforeLoopExit with the old logic. While LICM's hoisting logic needs the "must execute if loop entered" property, load store promotion actually only needs "store executes before any taken exits" property. (We do need one "must execute" dereferencing instruction, but it doesn't have to be the store.)

[sanjoy]

JFYI this is somewhat of a hornet's nest -- I believe cases like test_impossible_exit_in_untaken_block are actually correct for C/C++ because infloops without side effects are UB.

[mkazantsev]

In D50558#1203581, @sanjoy wrote:

JFYI this is somewhat of a hornet's nest -- I believe cases like test_impossible_exit_in_untaken_block are actually correct for C/C++ because infloops without side effects are UB.

I will add similar tests with volatile loads in header, so that it would be a clearly defined situation in C++ and the same problem showed up.

[mkazantsev]

In D50558#1203595, @mkazantsev wrote:

In D50558#1203581, @sanjoy wrote:

JFYI this is somewhat of a hornet's nest -- I believe cases like test_impossible_exit_in_untaken_block are actually correct for C/C++ because infloops without side effects are UB.

I will add similar tests with volatile loads in header, so that it would be a clearly defined situation in C++ and the same problem showed up.

Actually this logic is accidentally correct right now because isGuaranteedToTransferExecutionToSuccessor thinks that volatile loads don't transfer execution to successors (which was under discurrion and probably needs removed) and MustExecute is super-conservative about such instructions in non-header blocks (see https://reviews.llvm.org/D50377). When MustThrow analysis becomes less restrictive, this problem becomes a real one and we hoist sdiv from such examples despite the fact that they are no longer "finite" according to C++ specification.

So the current behavior of this analysis is wrong, but due to limitations of MustThrow analysis it doesn't affect any real example. As I improve the MustThrow analysis, a lot of things like this show up.

I've added a couple of such tests as https://reviews.llvm.org/rL339983 to make sure that they won't break even in spite of improved MustThrow analysis.

[sanjoy]

In D50558#1203623, @mkazantsev wrote:

Actually this logic is accidentally correct right now because isGuaranteedToTransferExecutionToSuccessor thinks that volatile loads don't transfer execution to successors (which was under discurrion and probably needs removed) and MustExecute is super-conservative about such instructions in non-header blocks (see https://reviews.llvm.org/D50377). When MustThrow analysis becomes less restrictive, this problem becomes a real one and we hoist sdiv from such examples despite the fact that they are no longer "finite" according to C++ specification.

Sorry, I wasn't clear. I meant to say that transforming

while (true) {
  if (<unknown condition>) {
    int c = 1 / divisor;
    break;
  }
}

to

int c = 1 / divisor;
while (true) {
  if (<unknown condition>) {
    break;
  }
}

is correct for C++ (because non-side effecting infloops are UB) and that I believe your change will "regress" this optimization (since LLVM will not longer hoist the division). Though I guess if no-one complains about it in a couple of days then we're fine?? :)

What you're saying, that it would be a bug even for C++ if LLVM hoisted the divide from

while (true) {
  <volatile load>
  if (<unknown condition>) {
    int c = 1 / divisor;
    break;
  }
}

is correct, but not quite what I'm trying to say.

Also, given what you said about isGuaranteedToTransferExecutionToSuccessor, perhaps we can close llvm.org/PR24078?

[efriedma]

You don't need a volatile operation; [intro.progress] also mentions atomic operations.

[mkazantsev]

I guess we can close PR24078 now.

include/llvm/Analysis/MustExecute.h

public:
   bool mayThrow(const BasicBlock *BB);
 
   bool anyBlockMayThrow();
 
   bool mayThrowBefore(const BasicBlock *BB);
 
   bool mayThrowBefore(const Instruction *Insn);
 
+  bool allPredecessorsLeadToBlock(const BasicBlock *BB,
+                                  const DominatorTree *DT);
+
   void invalidateBlock(const BasicBlock *BB);
 
   void reset(Loop *L);
 
 private:
   // The current loop this LoopSafetyInfo is working with. It should be set via
   // constructor or via the method "reset" to a non-null value before any query
   // is done to this LoopSafetyInfo.

lib/Analysis/MustExecute.cpp

if (Fn->hasPersonalityFn())
     if (Constant *PersonalityFn = Fn->getPersonalityFn())
       if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))
         BlockColors = colorEHFunclets(*Fn);
 }
 
 /// Return true if we can prove that the given ExitBlock is not reached on the
 /// first iteration of the given loop.  That is, the backedge of the loop must
 /// be executed before the ExitBlock is executed in any dynamic execution trace.
-static bool CanProveNotTakenFirstIteration(BasicBlock *ExitBlock,
+static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
                                            const DominatorTree *DT,
                                            const Loop *CurLoop) {
   auto *CondExitBlock = ExitBlock->getSinglePredecessor();
   if (!CondExitBlock)
     // expect unique exits
     return false;
   assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
   auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
   if (!SimpleCst)
     return false;
   if (ExitBlock == BI->getSuccessor(0))
     return SimpleCst->isZeroValue();
   assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
   return SimpleCst->isAllOnesValue();
 }
 
+/// Return true if we must reach the block \p BB under assumption that the loop
+/// is entered and no instruction throws or otherwise exits abnormally.
+bool LoopSafetyInfo::allPredecessorsLeadToBlock(const BasicBlock *BB,
+                                                const DominatorTree *DT) {
+  assert(CurLoop && "Should calculate the info first!");
+  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
+
+  // Fast path: header is always reached once the loop is entered.
+  if (BB == CurLoop->getHeader())
+    return true;
+
+  // Collect all transitive predecessors of BB in the same loop.
+  SmallPtrSet<const BasicBlock *, 4> Predecessors;
+  SmallVector<const BasicBlock *, 4> WorkList;
+  for (auto *Pred : predecessors(BB)) {
+    Predecessors.insert(Pred);
+    WorkList.push_back(BB);
+  }
+  while (!WorkList.empty()) {
+    auto *Pred = WorkList.pop_back_val();
+    assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
+    // We are not interested in backedges.
+    if (Pred == CurLoop->getHeader())
+      continue;
+    for (auto *PredPred : predecessors(Pred))
+      if (Predecessors.insert(PredPred).second)
+        WorkList.push_back(PredPred);
+  }
+
+  // Make sure that all successors of all predecessors of BB are either:
+  // 1) BB,
+  // 2) Also predecessors of BB,
+  // 3) Exit blocks which are not taken on 1st iteration.
+  // Memoize blocks we've already checked.
+  SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
+  for (auto *Pred : Predecessors)
+    for (auto *Succ : successors(Pred))
+      if (CheckedSuccessors.insert(Succ).second &&
+          Succ != BB && !Predecessors.count(Succ))
+        // Okay, if the successor is neither the BB nor one of its predecessors,
+        // but if it an exit block which is not reached on the 1st iteration, we
+        // can skip it. Otherwise, conservatively return false. We could be much
+        // smarter here if we took not just the 1st iteration.
+        if (CurLoop->contains(Succ) ||
+            !CanProveNotTakenFirstIteration(Succ, DT, CurLoop))
+          return false;
+
+  // All predecessors can only lead us to BB.
+  return true;
+}
+
 /// Returns true if the instruction in a loop is guaranteed to execute at least
 /// once.
 bool llvm::isGuaranteedToExecute(const Instruction &Inst,
                                  const DominatorTree *DT, const Loop *CurLoop,
                                  LoopSafetyInfo *SafetyInfo) {
   // We have to check to make sure that the instruction dominates all
   // of the exit blocks.  If it doesn't, then there is a path out of the loop
   // which does not execute this instruction, so we can't hoist it.
 
   // If the instruction is in the header block for the loop (which is very
   // common), it is always guaranteed to dominate the exit blocks.  Since this
   // is a common case, and can save some work, check it now.
   if (Inst.getParent() == CurLoop->getHeader())
     // If there's a throw in the header block, we can't guarantee we'll reach
     // Inst unless we can prove that Inst comes before the potential implicit
     // exit.  At the moment, we use a (cheap) hack for the common case where
     // the instruction of interest is the first one in the block.
     return !SafetyInfo->mayThrow(CurLoop->getHeader()) ||
       Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
 
   // If we can throw before we reach the given instruction, return false.
   if (SafetyInfo->mayThrowBefore(&Inst))
     return false;
 
-  // Note: There are two styles of reasoning intermixed below for
-  // implementation efficiency reasons.  They are:
-  // 1) If we can prove that the instruction dominates all exit blocks, then we
-  // know the instruction must have executed on *some* iteration before we
-  // exit.  We do not prove *which* iteration the instruction must execute on.
-  // 2) If we can prove that the instruction dominates the latch and all exits
-  // which might be taken on the first iteration, we know the instruction must
-  // execute on the first iteration.  This second style allows a conditional
-  // exit before the instruction of interest which is provably not taken on the
-  // first iteration.  This is a quite common case for range check like
-  // patterns.  TODO: support loops with multiple latches.
-
-  const bool InstDominatesLatch =
-    CurLoop->getLoopLatch() != nullptr &&
-    DT->dominates(Inst.getParent(), CurLoop->getLoopLatch());
-
-  // Get the exit blocks for the current loop.
-  SmallVector<BasicBlock *, 8> ExitBlocks;
-  CurLoop->getExitBlocks(ExitBlocks);
-
-  // Verify that the block dominates each of the exit blocks of the loop.
-  for (BasicBlock *ExitBlock : ExitBlocks)
-    if (!DT->dominates(Inst.getParent(), ExitBlock))
-      if (!InstDominatesLatch ||
-          !CanProveNotTakenFirstIteration(ExitBlock, DT, CurLoop))
-        return false;
-
-  // As a degenerate case, if the loop is statically infinite then we haven't
-  // proven anything since there are no exit blocks.
-  if (ExitBlocks.empty())
-    return false;
-
-  // FIXME: In general, we have to prove that the loop isn't an infinite loop.
-  // See http::llvm.org/PR24078 .  (The "ExitBlocks.empty()" check above is
-  // just a special case of this.)
+  // If there is a way from header to exit or latch that doesn't lead to our
+  // instruction's block, return false.
+  if (!SafetyInfo->allPredecessorsLeadToBlock(Inst.getParent(), DT))
+    return false;
+
   return true;
 }
 
 
 namespace {
   struct MustExecutePrinter : public FunctionPass {
 
     static char ID; // Pass identification, replacement for typeid

test/Analysis/MustExecute/infinite_loops.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -disable-output -print-mustexecute %s 2>&1 | FileCheck %s
 
 ; Infinite loop.
-; TODO: backedge is provably mustexecute, but the analysis does not know this.
+; Make sure that the backedge is mustexec.
 define void @test_no_exit_block(i1 %cond, i32 %a, i32 %b) {
 ; CHECK-LABEL: @test_no_exit_block(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; (mustexec in: loop)
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[MAYBE_TAKEN:%.*]], label [[BACKEDGE]] ; (mustexec in: loop)
-
-; FIXME: Should be mustexec in backedge. The current analysis does not handle
-; loops without exit blocks at all.
-; CHECK-NOT:   ; (mustexec in: loop)
-
 ; CHECK:       maybe_taken:
+; CHECK-NOT:   mustexec
 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       backedge:
-; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    br label [[LOOP]]
+; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1 ; (mustexec in: loop)
+; CHECK-NEXT:    br label [[LOOP]] ; (mustexec in: loop)
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
   br i1 %cond, label %maybe_taken, label %backedge
 

 backedge:
   %iv.next = add i32 %iv, 1
   br i1 true, label %loop, label %exit
 
 exit:
   ret void
 }
 
-; FIXME: This code demonstrates a bug. %div should not be mustexec.
+; Make sure that sdiv is NOT marked as mustexec.
 define void @test_impossible_exit_in_untaken_block(i1 %cond, i32 %a, i32 %b, i32* %p) {
 ; CHECK-LABEL: @test_impossible_exit_in_untaken_block(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; (mustexec in: loop)
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[MAYBE_TAKEN:%.*]], label [[BACKEDGE]] ; (mustexec in: loop)
 ; CHECK:       maybe_taken:
-
-; FIXME: The block below is NOT always taken!!! Current this example demonstrates a
-;        bug in current mustexecute analysis.
-
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]] ; (mustexec in: loop)
-; CHECK-NEXT:    store i32 [[DIV]], i32* [[P:%.*]] ; (mustexec in: loop)
-; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[EXIT:%.*]] ; (mustexec in: loop)
+; CHECK-NOT:   mustexec
+; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    store i32 [[DIV]], i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[EXIT:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1 ; (mustexec in: loop)
 ; CHECK-NEXT:    br label [[LOOP]] ; (mustexec in: loop)
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop

test/Analysis/MustExecute/loop-header.ll

 ; FIXME: everything in inner loop header should be must execute
 ; for outer as well
 define i1 @nested(i32* noalias %p, i32 %high) {
 ; CHECK-LABEL: @nested
 ; CHECK-LABEL: loop:                                             ; preds = %next
 ; CHECK:         %iv = phi i32 [ 0, %entry ], [ %iv.next, %next ] ; (mustexec in: loop)
 ; CHECK:         br label %inner_loop ; (mustexec in: loop)
 ; CHECK-LABEL: inner_loop:
-; CHECK:         %v = load i32, i32* %p ; (mustexec in 2 loops: inner_loop, loop)
-; CHECK:         %inner.test = icmp eq i32 %v, 0  ; (mustexec in 2 loops: inner_loop, loop)
-; CHECK:         br i1 %inner.test, label %inner_loop, label %next  ; (mustexec in 2 loops: inner_loop, loop)
+; CHECK:         %v = load i32, i32* %p ; (mustexec in: inner_loop)
+; CHECK:         %inner.test = icmp eq i32 %v, 0  ; (mustexec in: inner_loop)
+; CHECK:         br i1 %inner.test, label %inner_loop, label %next  ; (mustexec in: inner_loop)
 ; CHECK:         call void @maythrow_and_use(i32 %v) ; (mustexec in: loop)
 ; CHECK-NOT: mustexec
 
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %next]

test/Transforms/LICM/infinite_loops.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -basicaa -licm < %s | FileCheck %s
 ; RUN: opt -aa-pipeline=basic-aa -passes='require<opt-remark-emit>,loop(licm)' -S %s | FileCheck %s
 
-; FIXME: This test demonstrates a bug in MustExecute analysis. We hoist sdiv
-;        which can be a division by zero from a block which is never taken.
+; Make sure we don't hoist the unsafe division to some executable block.
 define void @test_impossible_exit_in_untaken_block(i32 %a, i32 %b, i32* %p) {
 ; CHECK-LABEL: @test_impossible_exit_in_untaken_block(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br i1 false, label [[NEVER_TAKEN:%.*]], label [[BACKEDGE]]
 ; CHECK:       never_taken:
+; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    store i32 [[DIV]], i32* [[P:%.*]]
 ; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[EXIT:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br label [[LOOP]]
 ; CHECK:       exit:
-; CHECK-NEXT:    store i32 [[DIV]], i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
   br i1 false, label %never_taken, label %backedge

test/Transforms/LICM/preheader-safe.ll

loop:                                         ; preds = %entry, %for.inc
   %div = udiv i64 %x, %y
   br i1 %cond, label %loop-if, label %exit
 loop-if:
   call void @use(i64 %div)
   br label %loop
 exit:
   ret void
 }
-; Negative test - can't move out of throwing block
+; Positive test -- we can hoist udiv which is before any thrower.
+define void @nothrow_header_pos(i64 %x, i64 %y, i1 %cond) {
+; CHECK-LABEL: nothrow_header_pos
+; CHECK-LABEL: entry
+; CHECK: %div = udiv i64 %x, %y
+; CHECK-LABEL: loop
+; CHECK: call void @use(i64 %div)
+entry:
+  br label %loop
+loop:                                         ; preds = %entry, %for.inc
+  br label %loop-if
+loop-if:
+  %div = udiv i64 %x, %y
+  call void @use(i64 %div)
+  br label %loop
+}
+
+; Negative test -- we cannot hoist across a thrower.
 define void @nothrow_header_neg(i64 %x, i64 %y, i1 %cond) {
 ; CHECK-LABEL: nothrow_header_neg
 ; CHECK-LABEL: entry
+; CHECK-NOT: udiv
 ; CHECK-LABEL: loop
+; CHECK: call void @maythrow()
 ; CHECK: %div = udiv i64 %x, %y
 ; CHECK: call void @use(i64 %div)
 entry:
   br label %loop
 loop:                                         ; preds = %entry, %for.inc
   br label %loop-if
 loop-if:
+  call void @maythrow()
   %div = udiv i64 %x, %y
   call void @use(i64 %div)
   br label %loop
 }