[JumpThreading] Thread through guards

Summary:
This patch allows JumpThreading also thread through guards.
Virtually, guard(cond) is equivalent to the following construction:

  if (cond) { do something } else {deoptimize}

Yet it is not explicitly converted into IFs before lowering.
This patch enables early threading through guards in simple cases.
Currently it covers the following situation:

  if (cond1) {
    // code A
  } else {
    // code B
  }
  // code C
  guard(cond2)
  // code D

If there is implication cond1 => cond2 or !cond1 => cond2, we can transform
this construction into the following:

  if (cond1) {
    // code A
    // code C
  } else {
    // code B
    // code C
    guard(cond2)
  }
  // code D

Thus, removing the guard from one of execution branches.

Patch by Max Kazantsev!

Reviewers: reames, apilipenko, igor-laevsky, anna, sanjoy

Reviewed By: sanjoy

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D29620

llvm-svn: 294617

1 files changed, 132 insertions, 0 deletions

diff --git a/llvm/test/Transforms/JumpThreading/guards.ll b/llvm/test/Transforms/JumpThreading/guards.ll
new file mode 100644
index 00000000000..a22dcf2262a
--- /dev/null
+++ b/llvm/test/Transforms/JumpThreading/guards.ll
@@ -0,0 +1,132 @@
+; RUN: opt < %s -jump-threading -dce -S | FileCheck %s
+
+declare void @llvm.experimental.guard(i1, ...)
+
+declare i32 @f1()
+declare i32 @f2()
+
+define i32 @branch_implies_guard(i32 %a) {
+; CHECK-LABEL: @branch_implies_guard(
+  %cond = icmp slt i32 %a, 10
+  br i1 %cond, label %T1, label %F1
+
+T1:
+; CHECK:       T1.split
+; CHECK:         %v1 = call i32 @f1()
+; CHECK-NEXT:    %retVal
+; CHECK-NEXT:    br label %Merge
+  %v1 = call i32 @f1()
+  br label %Merge
+
+F1:
+; CHECK:       F1.split
+; CHECK:         %v2 = call i32 @f2()
+; CHECK-NEXT:    %retVal
+; CHECK-NEXT:    %condGuard
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %condGuard
+; CHECK-NEXT:    br label %Merge
+  %v2 = call i32 @f2()
+  br label %Merge
+
+Merge:
+; CHECK:       Merge
+; CHECK-NOT:     call void(i1, ...) @llvm.experimental.guard(
+  %retPhi = phi i32 [ %v1, %T1 ], [ %v2, %F1 ]
+  %retVal = add i32 %retPhi, 10
+  %condGuard = icmp slt i32 %a, 20
+  call void(i1, ...) @llvm.experimental.guard( i1 %condGuard )[ "deopt"() ]
+  ret i32 %retVal
+}
+
+define i32 @not_branch_implies_guard(i32 %a) {
+; CHECK-LABEL: @not_branch_implies_guard(
+  %cond = icmp slt i32 %a, 20
+  br i1 %cond, label %T1, label %F1
+
+T1:
+; CHECK:       T1.split:
+; CHECK-NEXT:    %v1 = call i32 @f1()
+; CHECK-NEXT:    %retVal
+; CHECK-NEXT:    %condGuard
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %condGuard
+; CHECK-NEXT:    br label %Merge
+  %v1 = call i32 @f1()
+  br label %Merge
+
+F1:
+; CHECK:       F1.split:
+; CHECK-NEXT:   %v2 = call i32 @f2()
+; CHECK-NEXT:   %retVal
+; CHECK-NEXT:   br label %Merge
+  %v2 = call i32 @f2()
+  br label %Merge
+
+Merge:
+; CHECK:       Merge
+; CHECK-NOT:     call void(i1, ...) @llvm.experimental.guard(
+  %retPhi = phi i32 [ %v1, %T1 ], [ %v2, %F1 ]
+  %retVal = add i32 %retPhi, 10
+  %condGuard = icmp sgt i32 %a, 10
+  call void(i1, ...) @llvm.experimental.guard( i1 %condGuard )[ "deopt"() ]
+  ret i32 %retVal
+}
+
+define i32 @branch_overlaps_guard(i32 %a) {
+; CHECK-LABEL: @branch_overlaps_guard(
+  %cond = icmp slt i32 %a, 20
+  br i1 %cond, label %T1, label %F1
+
+T1:
+; CHECK:        T1:
+; CHECK-NEXT:      %v1 = call i32 @f1()
+; CHECK-NEXT:      br label %Merge
+  %v1 = call i32 @f1()
+  br label %Merge
+
+F1:
+; CHECK:        F1:
+; CHECK-NEXT:     %v2 = call i32 @f2()
+; CHECK-NEXT:     br label %Merge
+  %v2 = call i32 @f2()
+  br label %Merge
+
+Merge:
+; CHECK:       Merge
+; CHECK:         %condGuard = icmp slt i32 %a, 10
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %condGuard) [ "deopt"() ]
+  %retPhi = phi i32 [ %v1, %T1 ], [ %v2, %F1 ]
+  %retVal = add i32 %retPhi, 10
+  %condGuard = icmp slt i32 %a, 10
+  call void(i1, ...) @llvm.experimental.guard( i1 %condGuard )[ "deopt"() ]
+  ret i32 %retVal
+}
+
+define i32 @branch_doesnt_overlap_guard(i32 %a) {
+; CHECK-LABEL: @branch_doesnt_overlap_guard(
+  %cond = icmp slt i32 %a, 10
+  br i1 %cond, label %T1, label %F1
+
+T1:
+; CHECK:        T1:
+; CHECK-NEXT:      %v1 = call i32 @f1()
+; CHECK-NEXT:      br label %Merge
+  %v1 = call i32 @f1()
+  br label %Merge
+
+F1:
+; CHECK:        F1:
+; CHECK-NEXT:     %v2 = call i32 @f2()
+; CHECK-NEXT:     br label %Merge
+  %v2 = call i32 @f2()
+  br label %Merge
+
+Merge:
+; CHECK:       Merge
+; CHECK:         %condGuard = icmp sgt i32 %a, 20
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %condGuard) [ "deopt"() ]
+  %retPhi = phi i32 [ %v1, %T1 ], [ %v2, %F1 ]
+  %retVal = add i32 %retPhi, 10
+  %condGuard = icmp sgt i32 %a, 20
+  call void(i1, ...) @llvm.experimental.guard( i1 %condGuard )[ "deopt"() ]
+  ret i32 %retVal
+}