[InstCombine] Canonicalize icmp instructions based on dominating conditions.

Summary:
    This patch canonicalizes conditions based on the constant range information
    of the dominating branch condition.
    For example:

      %cmp = icmp slt i64 %a, 0
      br i1 %cmp, label %land.lhs.true, label %lor.rhs
      lor.rhs:
        %cmp2 = icmp sgt i64 %a, 0

    Would now be canonicalized into:

      %cmp = icmp slt i64 %a, 0
      br i1 %cmp, label %land.lhs.true, label %lor.rhs
      lor.rhs:
        %cmp2 = icmp ne i64 %a, 0

Reviewers: mcrosier, gberry, t.p.northover, llvm-commits, reames, hfinkel, sanjoy, majnemer

Subscribers: MatzeB, majnemer, mcrosier

Differential Revision: http://reviews.llvm.org/D18841

llvm-svn: 268521

1 files changed, 118 insertions, 0 deletions

diff --git a/llvm/test/Transforms/InstCombine/icmp.ll b/llvm/test/Transforms/InstCombine/icmp.ll
index 2937e46cb8a..24a539be2b6 100644
--- a/llvm/test/Transforms/InstCombine/icmp.ll
+++ b/llvm/test/Transforms/InstCombine/icmp.ll
@@ -1979,3 +1979,121 @@ define i1 @cmp_inverse_mask_bits_set_ne(i32 %x) {
   ret i1 %cmp
 }
 
+; CHECK-LABEL: @idom_sign_bit_check_edge_dominates
+define void @idom_sign_bit_check_edge_dominates(i64 %a) {
+entry:
+  %cmp = icmp slt i64 %a, 0
+  br i1 %cmp, label %land.lhs.true, label %lor.rhs
+
+land.lhs.true:                                    ; preds = %entry
+  br label %lor.end
+
+; CHECK-LABEL: lor.rhs:
+; CHECK-NOT: icmp sgt i64 %a, 0
+; CHECK: icmp eq i64 %a, 0
+lor.rhs:                                          ; preds = %entry
+  %cmp2 = icmp sgt i64 %a, 0
+  br i1 %cmp2, label %land.rhs, label %lor.end
+
+land.rhs:                                         ; preds = %lor.rhs
+  br label %lor.end
+
+lor.end:                                          ; preds = %land.rhs, %lor.rhs, %land.lhs.true
+  ret void
+}
+
+; CHECK-LABEL: @idom_sign_bit_check_edge_not_dominates
+define void @idom_sign_bit_check_edge_not_dominates(i64 %a) {
+entry:
+  %cmp = icmp slt i64 %a, 0
+  br i1 %cmp, label %land.lhs.true, label %lor.rhs
+
+land.lhs.true:                                    ; preds = %entry
+  br i1 undef, label %lor.end, label %lor.rhs
+
+; CHECK-LABEL: lor.rhs:
+; CHECK: icmp sgt i64 %a, 0
+; CHECK-NOT: icmp eq i64 %a, 0
+lor.rhs:                                          ; preds = %land.lhs.true, %entry
+  %cmp2 = icmp sgt i64 %a, 0
+  br i1 %cmp2, label %land.rhs, label %lor.end
+
+land.rhs:                                         ; preds = %lor.rhs
+  br label %lor.end
+
+lor.end:                                          ; preds = %land.rhs, %lor.rhs, %land.lhs.true
+  ret void
+}
+
+; CHECK-LABEL: @idom_sign_bit_check_edge_dominates_select
+define void @idom_sign_bit_check_edge_dominates_select(i64 %a, i64 %b) {
+entry:
+  %cmp = icmp slt i64 %a, 5
+  br i1 %cmp, label %land.lhs.true, label %lor.rhs
+
+land.lhs.true:                                    ; preds = %entry
+  br label %lor.end
+
+; CHECK-LABEL: lor.rhs:
+; CHECK-NOT: [[B:%.*]] = icmp sgt i64 %a, 5
+; CHECK: [[C:%.*]] = icmp eq i64 %a, %b
+; CHECK-NOT: [[D:%.*]] = select i1 [[B]], i64 %a, i64 5
+; CHECK-NOT: icmp ne i64 [[D]], %b
+; CHECK-NEXT: br i1 [[C]], label %lor.end, label %land.rhs
+lor.rhs:                                          ; preds = %entry
+  %cmp2 = icmp sgt i64 %a, 5
+  %select = select i1 %cmp2, i64 %a, i64 5
+  %cmp3 = icmp ne i64 %select, %b
+  br i1 %cmp3, label %land.rhs, label %lor.end
+
+land.rhs:                                         ; preds = %lor.rhs
+  br label %lor.end
+
+lor.end:                                          ; preds = %land.rhs, %lor.rhs, %land.lhs.true
+  ret void
+}
+
+; CHECK-LABEL: @idom_zbranch
+define void @idom_zbranch(i64 %a) {
+entry:
+  %cmp = icmp sgt i64 %a, 0
+  br i1 %cmp, label %lor.end, label %lor.rhs
+
+; CHECK-LABEL: lor.rhs:
+; CHECK: icmp slt i64 %a, 0
+; CHECK-NOT: icmp eq i64 %a, 0
+lor.rhs:                                          ; preds = %entry
+  %cmp2 = icmp slt i64 %a, 0
+  br i1 %cmp2, label %land.rhs, label %lor.end
+
+land.rhs:                                         ; preds = %lor.rhs
+  br label %lor.end
+
+lor.end:                                          ; preds = %land.rhs, %lor.rhs
+  ret void
+}
+
+; CHECK-LABEL: @idom_not_zbranch
+define void @idom_not_zbranch(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp sgt i32 %a, 0
+  br i1 %cmp, label %return, label %if.end
+
+; CHECK-LABEL: if.end:
+; CHECK-NOT: [[B:%.*]] = icmp slt i32 %a, 0
+; CHECK: [[C:%.*]] = icmp eq i32 %a, %b
+; CHECK-NOT: [[D:%.*]] = select i1 [[B]], i32 %a, i32 0
+; CHECK-NOT: icmp ne i32 [[D]], %b
+; CHECK-NEXT: br i1 [[C]], label %return, label %if.then3
+if.end:                                           ; preds = %entry
+  %cmp1 = icmp slt i32 %a, 0
+  %a. = select i1 %cmp1, i32 %a, i32 0
+  %cmp2 = icmp ne i32 %a., %b
+  br i1 %cmp2, label %if.then3, label %return
+
+if.then3:                                         ; preds = %if.end
+  br label %return
+
+return:                                           ; preds = %if.end, %entry, %if.then3
+  ret void
+}