[MustExecute/LICM] Special case first instruction in throwing header

We currently have a hard to solve analysis problem around the order of instructions within a potentially throwing block.  We can't cheaply determine whether a given instruction is before the first potential throw in the block.  While we're working on that in the background, special case the first instruction within the header.

why this particular special case?  Well, headers are guaranteed to execute if the loop does, and it turns out we tend to produce this form in practice.

In a follow on patch, I tend to extend LICM with an alternate approach which works for any instruction in the header before the first throw, but this is the best I can come up with other users of the analysis (such as store promotion.)

Note: I can't show the difference in the analysis result since we're ORing in the expensive instruction walk used by SCEV.  Using the full walk is not suitable for a general solution.
llvm-svn: 331079

2 files changed, 45 insertions, 5 deletions

diff --git a/llvm/lib/Analysis/MustExecute.cpp b/llvm/lib/Analysis/MustExecute.cpp
index ece4a1695cf..1e922fd44c4 100644
--- a/llvm/lib/Analysis/MustExecute.cpp
+++ b/llvm/lib/Analysis/MustExecute.cpp
@@ -109,8 +109,11 @@ bool llvm::isGuaranteedToExecute(const Instruction &Inst,
   // 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.
-    return !SafetyInfo->HeaderMayThrow;
+    // 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->HeaderMayThrow ||
+      Inst.getParent()->getFirstNonPHI() == &Inst;
 
   // Somewhere in this loop there is an instruction which may throw and make us
   // exit the loop.
diff --git a/llvm/test/Transforms/LICM/preheader-safe.ll b/llvm/test/Transforms/LICM/preheader-safe.ll
index 8f82d1c68bb..9aa8e00bcfa 100644
--- a/llvm/test/Transforms/LICM/preheader-safe.ll
+++ b/llvm/test/Transforms/LICM/preheader-safe.ll
@@ -3,6 +3,7 @@
 
 declare void @use_nothrow(i64 %a) nounwind
 declare void @use(i64 %a)
+declare void @maythrow()
 
 define void @nothrow(i64 %x, i64 %y, i1* %cond) {
 ; CHECK-LABEL: nothrow
@@ -21,9 +22,44 @@ loop2:
   call void @use_nothrow(i64 %div)
   br label %loop
 }
+
+; The udiv is guarantee to execute if the loop is
+define void @throw_header_after(i64 %x, i64 %y, i1* %cond) {
+; CHECK-LABEL: throw_header_after
+; CHECK: %div = udiv i64 %x, %y
+; CHECK-LABEL: loop
+; CHECK: call void @use(i64 %div)
+entry:
+  br label %loop
+
+loop:                                         ; preds = %entry, %for.inc
+  %div = udiv i64 %x, %y
+  call void @use(i64 %div)
+  br label %loop
+}
+define void @throw_header_after_rec(i64* %xp, i64* %yp, i1* %cond) {
+; CHECK-LABEL: throw_header_after_rec
+; CHECK: %x = load i64, i64* %xp
+; CHECK: %y = load i64, i64* %yp
+; CHECK: %div = udiv i64 %x, %y
+; CHECK-LABEL: loop
+; CHECK: call void @use(i64 %div)
+entry:
+  br label %loop
+
+loop:                                         ; preds = %entry, %for.inc
+  %x = load i64, i64* %xp
+  %y = load i64, i64* %yp
+  %div = udiv i64 %x, %y
+  call void @use(i64 %div) readonly
+  br label %loop
+}
+
+
+
 ; Negative test
-define void @throw_header(i64 %x, i64 %y, i1* %cond) {
-; CHECK-LABEL: throw_header
+define void @throw_header_before(i64 %x, i64 %y, i1* %cond) {
+; CHECK-LABEL: throw_header_before
 ; CHECK-LABEL: loop
 ; CHECK: %div = udiv i64 %x, %y
 ; CHECK: call void @use(i64 %div)
@@ -31,6 +67,7 @@ entry:
   br label %loop
 
 loop:                                         ; preds = %entry, %for.inc
+  call void @maythrow()
   %div = udiv i64 %x, %y
   call void @use(i64 %div)
   br label %loop
@@ -43,7 +80,7 @@ define void @nothrow_header(i64 %x, i64 %y, i1 %cond) {
 ; CHECK-LABEL: entry
 ; CHECK: %div = udiv i64 %x, %y
 ; CHECK-LABEL: loop
-; CHECK: call void @use(i64 %div)
+  ; CHECK: call void @use(i64 %div)
 entry:
   br label %loop
 loop:                                         ; preds = %entry, %for.inc