[LICM] Use ICFLoopSafetyInfo in LICM

This patch makes LICM use `ICFLoopSafetyInfo` that is a smarter version
of LoopSafetyInfo that leverages power of Implicit Control Flow Tracking
to keep track of throwing instructions and give less pessimistic answers
to queries related to throws.

The ICFLoopSafetyInfo itself has been introduced in rL344601. This patch
enables it in LICM only.

Differential Revision: https://reviews.llvm.org/D50377
Reviewed By: apilipenko

llvm-svn: 346201

5 files changed, 199 insertions, 6 deletions

diff --git a/llvm/test/CodeGen/AMDGPU/build-vector-insert-elt-infloop.ll b/llvm/test/CodeGen/AMDGPU/build-vector-insert-elt-infloop.ll
index 865dccb2791..fd81c0438d6 100644
--- a/llvm/test/CodeGen/AMDGPU/build-vector-insert-elt-infloop.ll
+++ b/llvm/test/CodeGen/AMDGPU/build-vector-insert-elt-infloop.ll
@@ -18,7 +18,7 @@ bb1:
   %tmp4 = bitcast half %tmp3 to i16
   %tmp5 = insertelement <2 x i16> <i16 0, i16 undef>, i16 %tmp4, i32 1
   %tmp6 = bitcast i16* %arg to half*
-  store half %tmp2, half* %tmp6, align 2
+  store volatile half %tmp2, half* %tmp6, align 2
   %tmp7 = bitcast <2 x i16> %tmp to <2 x half>
   %tmp8 = extractelement <2 x half> %tmp7, i32 0
   br label %bb1
diff --git a/llvm/test/Transforms/LICM/guards.ll b/llvm/test/Transforms/LICM/guards.ll
index b2f672104f8..b37c4189284 100644
--- a/llvm/test/Transforms/LICM/guards.ll
+++ b/llvm/test/Transforms/LICM/guards.ll
@@ -85,15 +85,15 @@ loop:
 }
 
 
-; TODO: We can also hoist this load and guard from mustexec non-header block.
+; TODO: We can also hoist this guard from mustexec non-header block.
 define void @test4(i1 %c, i32* %p) {
 
 ; CHECK-LABEL: @test4(
 ; CHECK-LABEL: entry:
-; CHECK-LABEL: loop:
-; CHECK-LABEL: backedge:
 ; CHECK:       %a = load i32, i32* %p
 ; CHECK:       %invariant_cond = icmp ne i32 %a, 100
+; CHECK-LABEL: loop:
+; CHECK-LABEL: backedge:
 ; CHECK:       call void (i1, ...) @llvm.experimental.guard(i1 %invariant_cond)
 
 entry:
diff --git a/llvm/test/Transforms/LICM/hoist-mustexec.ll b/llvm/test/Transforms/LICM/hoist-mustexec.ll
index 5bce1fbce1c..53f78e88f72 100644
--- a/llvm/test/Transforms/LICM/hoist-mustexec.ll
+++ b/llvm/test/Transforms/LICM/hoist-mustexec.ll
@@ -456,3 +456,150 @@ backedge:
 exit:
   ret void
 }
+
+; Check that we can hoist a mustexecute load from backedge even if something
+; throws after it.
+define void @test_hoist_from_backedge_01(i32* %p, i32 %n) {
+
+; CHECK-LABEL: @test_hoist_from_backedge_01(
+; CHECK:       entry:
+; CHECK-NEXT:  %load = load i32, i32* %p
+; CHECK-NOT:   load i32
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
+  %cond = icmp slt i32 %iv, %n
+  br i1 %cond, label %if.true, label %if.false
+
+if.true:
+  %a = add i32 %iv, %iv
+  br label %backedge
+
+if.false:
+  %b = mul i32 %iv, %iv
+  br label %backedge
+
+backedge:
+  %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
+  %iv.next = add i32 %iv, %merge
+  %load = load i32, i32* %p
+  call void @may_throw()
+  %loop.cond = icmp ult i32 %iv.next, %load
+  br i1 %loop.cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Check that we don't hoist the load if something before it can throw.
+define void @test_hoist_from_backedge_02(i32* %p, i32 %n) {
+
+; CHECK-LABEL: @test_hoist_from_backedge_02(
+; CHECK:       entry:
+; CHECK:       loop:
+; CHECK:       %load = load i32, i32* %p
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
+  %cond = icmp slt i32 %iv, %n
+  br i1 %cond, label %if.true, label %if.false
+
+if.true:
+  %a = add i32 %iv, %iv
+  br label %backedge
+
+if.false:
+  %b = mul i32 %iv, %iv
+  br label %backedge
+
+backedge:
+  %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
+  %iv.next = add i32 %iv, %merge
+  call void @may_throw()
+  %load = load i32, i32* %p
+  %loop.cond = icmp ult i32 %iv.next, %load
+  br i1 %loop.cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @test_hoist_from_backedge_03(i32* %p, i32 %n) {
+
+; CHECK-LABEL: @test_hoist_from_backedge_03(
+; CHECK:       entry:
+; CHECK:       loop:
+; CHECK:       %load = load i32, i32* %p
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
+  %cond = icmp slt i32 %iv, %n
+  br i1 %cond, label %if.true, label %if.false
+
+if.true:
+  %a = add i32 %iv, %iv
+  br label %backedge
+
+if.false:
+  %b = mul i32 %iv, %iv
+  call void @may_throw()
+  br label %backedge
+
+backedge:
+  %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
+  %iv.next = add i32 %iv, %merge
+  %load = load i32, i32* %p
+  %loop.cond = icmp ult i32 %iv.next, %load
+  br i1 %loop.cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @test_hoist_from_backedge_04(i32* %p, i32 %n) {
+
+; CHECK-LABEL: @test_hoist_from_backedge_04(
+; CHECK:       entry:
+; CHECK:       loop:
+; CHECK:       %load = load i32, i32* %p
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
+  call void @may_throw()
+  %cond = icmp slt i32 %iv, %n
+  br i1 %cond, label %if.true, label %if.false
+
+if.true:
+  %a = add i32 %iv, %iv
+  br label %backedge
+
+if.false:
+  %b = mul i32 %iv, %iv
+  br label %backedge
+
+backedge:
+  %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
+  %iv.next = add i32 %iv, %merge
+  %load = load i32, i32* %p
+  %loop.cond = icmp ult i32 %iv.next, %load
+  br i1 %loop.cond, label %loop, label %exit
+
+exit:
+  ret void
+}
diff --git a/llvm/test/Transforms/LICM/hoist-nounwind.ll b/llvm/test/Transforms/LICM/hoist-nounwind.ll
index 9fc4903b830..d53e4043af1 100644
--- a/llvm/test/Transforms/LICM/hoist-nounwind.ll
+++ b/llvm/test/Transforms/LICM/hoist-nounwind.ll
@@ -49,14 +49,16 @@ for.cond.cleanup:
   ret i32 0
 }
 
-; Don't hoist load past volatile load.
+; Hoist a non-volatile load past volatile load.
 define i32 @test3(i32* noalias nocapture readonly %a, i32* %v) nounwind uwtable {
 ; CHECK-LABEL: @test3(
 entry:
   br label %for.body
 
+; CHECK: load i32
+; CHECK: for.body:
 ; CHECK: load volatile i32
-; CHECK-NEXT: load i32
+; CHECK-NOT: load
 for.body:
   %i.06 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   %x.05 = phi i32 [ 0, %entry ], [ %add, %for.body ]
@@ -70,3 +72,26 @@ for.body:
 for.cond.cleanup:
   ret i32 %add
 }
+
+; Don't a volatile load past volatile load.
+define i32 @test4(i32* noalias nocapture readonly %a, i32* %v) nounwind uwtable {
+; CHECK-LABEL: @test4(
+entry:
+  br label %for.body
+
+; CHECK: for.body:
+; CHECK: load volatile i32
+; CHECK-NEXT: load volatile i32
+for.body:
+  %i.06 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %x.05 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %xxx = load volatile i32, i32* %v, align 4
+  %i1 = load volatile i32, i32* %a, align 4
+  %add = add nsw i32 %i1, %x.05
+  %inc = add nuw nsw i32 %i.06, 1
+  %exitcond = icmp eq i32 %inc, 1000
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup:
+  ret i32 %add
+}
\ No newline at end of file
diff --git a/llvm/test/Transforms/LICM/preheader-safe.ll b/llvm/test/Transforms/LICM/preheader-safe.ll
index 0bfe123862c..03a7258df11 100644
--- a/llvm/test/Transforms/LICM/preheader-safe.ll
+++ b/llvm/test/Transforms/LICM/preheader-safe.ll
@@ -112,11 +112,31 @@ loop-if:
 exit:
   ret void
 }
+
+; Positive test - can hoist something that happens before 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 - can't move out of throwing block
 define void @nothrow_header_neg(i64 %x, i64 %y, i1 %cond) {
 ; CHECK-LABEL: nothrow_header_neg
 ; CHECK-LABEL: entry
 ; CHECK-LABEL: loop
+; CHECK: call void @maythrow()
 ; CHECK: %div = udiv i64 %x, %y
 ; CHECK: call void @use(i64 %div)
 entry:
@@ -124,6 +144,7 @@ entry:
 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