[MustExecute] Fix algorithmic bug in isGuaranteedToExecute. PR38514

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.

Differential Revision: https://reviews.llvm.org/D50558
Reviewed By: reames

llvm-svn: 339984

3 files changed, 49 insertions, 20 deletions

diff --git a/llvm/test/Analysis/MustExecute/infinite_loops.ll b/llvm/test/Analysis/MustExecute/infinite_loops.ll
index 1dc5372920a..b8158e10204 100644
--- a/llvm/test/Analysis/MustExecute/infinite_loops.ll
+++ b/llvm/test/Analysis/MustExecute/infinite_loops.ll
@@ -2,7 +2,7 @@
 ; 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:
@@ -10,17 +10,13 @@ define void @test_no_exit_block(i1 %cond, i32 %a, i32 %b) {
 ; 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
@@ -75,7 +71,7 @@ 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:
@@ -84,13 +80,10 @@ define void @test_impossible_exit_in_untaken_block(i1 %cond, i32 %a, i32 %b, i32
 ; 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)
diff --git a/llvm/test/Analysis/MustExecute/loop-header.ll b/llvm/test/Analysis/MustExecute/loop-header.ll
index 3e729993d42..d0ec5fa6872 100644
--- a/llvm/test/Analysis/MustExecute/loop-header.ll
+++ b/llvm/test/Analysis/MustExecute/loop-header.ll
@@ -83,6 +83,43 @@ exit:
   ret i1 false
 }
 
+; FIXME: everything in inner loop header should be must execute
+; for outer as well
+define i1 @nested_no_throw(i32* noalias %p, i32 %high) {
+; CHECK-LABEL: @nested_no_throw
+; 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: 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-LABEL: next:
+; CHECK:         %iv.next = add nuw nsw i32 %iv, 1 ; (mustexec in: loop)
+; CHECK:         %exit.test = icmp slt i32 %iv, %high ; (mustexec in: loop)
+; CHECK:         br i1 %exit.test, label %exit, label %loop ; (mustexec in: loop)
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [0, %entry], [%iv.next, %next]
+  br label %inner_loop
+
+inner_loop:
+  %v = load i32, i32* %p
+  %inner.test = icmp eq i32 %v, 0
+  br i1 %inner.test, label %inner_loop, label %next
+
+next:
+  %iv.next = add nsw nuw i32 %iv, 1
+  %exit.test = icmp slt i32 %iv, %high
+  br i1 %exit.test, label %exit, label %loop
+
+exit:
+  ret i1 false
+}
+
 ; Since all the instructions in the loop dominate the only exit
 ; and there's no implicit control flow in the loop, all must execute
 ; FIXME: handled by loop safety info, test it
diff --git a/llvm/test/Transforms/LICM/infinite_loops.ll b/llvm/test/Transforms/LICM/infinite_loops.ll
index 07238c396b8..6189bdb1a97 100644
--- a/llvm/test/Transforms/LICM/infinite_loops.ll
+++ b/llvm/test/Transforms/LICM/infinite_loops.ll
@@ -2,23 +2,22 @@
 ; 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: