[InstSimplify] fold select with implied condition

This is an almost direct move of the functionality from InstCombine to 
InstSimplify. There's no reason not to do this in InstSimplify because 
we never create a new value with this transform.

(There's a question of whether any dominance-based transform belongs in
either of these passes, but that's a separate issue.)

I've changed 1 of the conditions for the fold (1 of the blocks for the 
branch must be the block we started with) into an assert because I'm not 
sure how that could ever be false.

We need 1 extra check to make sure that the instruction itself is in a
basic block because passes other than InstCombine may be using InstSimplify
as an analysis on values that are not wired up yet.

The 3-way compare changes show that InstCombine has some kind of 
phase-ordering hole. Otherwise, we would have already gotten the intended
final result that we now show here.

llvm-svn: 347896

1 files changed, 276 insertions, 0 deletions

diff --git a/llvm/test/Transforms/InstSimplify/select-implied.ll b/llvm/test/Transforms/InstSimplify/select-implied.ll
new file mode 100644
index 00000000000..a456e291b51
--- /dev/null
+++ b/llvm/test/Transforms/InstSimplify/select-implied.ll
@@ -0,0 +1,276 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instsimplify -S | FileCheck %s
+
+; A == B implies A >u B is false.
+
+define void @test1(i32 %a, i32 %b) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    br i1 [[CMP1]], label [[TAKEN:%.*]], label [[END:%.*]]
+; CHECK:       taken:
+; CHECK-NEXT:    call void @foo(i32 10)
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+  %cmp1 = icmp eq i32 %a, %b
+  br i1 %cmp1, label %taken, label %end
+
+taken:
+  %cmp2 = icmp ugt i32 %a, %b
+  %c = select i1 %cmp2, i32 0, i32 10
+  call void @foo(i32 %c)
+  br label %end
+
+end:
+  ret void
+}
+
+; If A == B is false then A != B is true.
+
+define void @test2(i32 %a, i32 %b) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    br i1 [[CMP1]], label [[END:%.*]], label [[TAKEN:%.*]]
+; CHECK:       taken:
+; CHECK-NEXT:    call void @foo(i32 20)
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+  %cmp1 = icmp eq i32 %a, %b
+  br i1 %cmp1, label %end, label %taken
+
+taken:
+  %cmp2 = icmp ne i32 %a, %b
+  %c = select i1 %cmp2, i32 20, i32 0
+  call void @foo(i32 %c)
+  br label %end
+
+end:
+  ret void
+}
+
+; A >u 10 implies A >u 10 is true.
+
+define void @test3(i32 %a) {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ugt i32 [[A:%.*]], 10
+; CHECK-NEXT:    br i1 [[CMP1]], label [[TAKEN:%.*]], label [[END:%.*]]
+; CHECK:       taken:
+; CHECK-NEXT:    call void @foo(i32 30)
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+  %cmp1 = icmp ugt i32 %a, 10
+  br i1 %cmp1, label %taken, label %end
+
+taken:
+  %cmp2 = icmp ugt i32 %a, 10
+  %c = select i1 %cmp2, i32 30, i32 0
+  call void @foo(i32 %c)
+  br label %end
+
+end:
+  ret void
+}
+
+define i8 @PR23333(i8 addrspace(1)* %ptr) {
+; CHECK-LABEL: @PR23333(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 addrspace(1)* [[PTR:%.*]], null
+; CHECK-NEXT:    br i1 [[CMP]], label [[TAKEN:%.*]], label [[END:%.*]]
+; CHECK:       taken:
+; CHECK-NEXT:    ret i8 1
+; CHECK:       end:
+; CHECK-NEXT:    ret i8 0
+;
+  %cmp = icmp eq i8 addrspace(1)* %ptr, null
+  br i1 %cmp, label %taken, label %end
+
+taken:
+  %cmp2 = icmp ne i8 addrspace(1)* %ptr, null
+  %res = select i1 %cmp2, i8 2, i8 1
+  ret i8 %res
+
+end:
+  ret i8 0
+}
+
+; We know the condition of the select is true based on a dominating condition.
+; Therefore, we can replace %cond with %len. 
+; TODO: len == 8 is known false in bb. This is handled by other passes, but should it be handled here? 
+
+define void @test4(i32 %len) {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = call i32 @bar(i32 [[LEN:%.*]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[LEN]], 4
+; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[B1:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    [[CMP11:%.*]] = icmp eq i32 [[LEN]], 8
+; CHECK-NEXT:    br i1 [[CMP11]], label [[B0:%.*]], label [[B1]]
+; CHECK:       b0:
+; CHECK-NEXT:    call void @foo(i32 [[LEN]])
+; CHECK-NEXT:    br label [[B1]]
+; CHECK:       b1:
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i32 [ [[LEN]], [[BB]] ], [ undef, [[B0]] ], [ [[TMP0]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    br label [[RET:%.*]]
+; CHECK:       ret:
+; CHECK-NEXT:    call void @foo(i32 [[TMP1]])
+; CHECK-NEXT:    ret void
+;
+entry:
+  %0 = call i32 @bar(i32 %len);
+  %cmp = icmp ult i32 %len, 4
+  br i1 %cmp, label %bb, label %b1
+bb:
+  %cond = select i1 %cmp, i32 %len, i32 8
+  %cmp11 = icmp eq i32 %cond, 8
+  br i1 %cmp11, label %b0, label %b1
+
+b0:
+  call void @foo(i32 %len)
+  br label %b1
+
+b1:
+  %1 = phi i32 [ %cond, %bb ], [ undef, %b0 ], [ %0, %entry ]
+  br label %ret
+
+ret:
+  call void @foo(i32 %1)
+  ret void
+}
+
+; A >u 10 implies A >u 9 is true.
+
+define void @test5(i32 %a) {
+; CHECK-LABEL: @test5(
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ugt i32 [[A:%.*]], 10
+; CHECK-NEXT:    br i1 [[CMP1]], label [[TAKEN:%.*]], label [[END:%.*]]
+; CHECK:       taken:
+; CHECK-NEXT:    call void @foo(i32 30)
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+  %cmp1 = icmp ugt i32 %a, 10
+  br i1 %cmp1, label %taken, label %end
+
+taken:
+  %cmp2 = icmp ugt i32 %a, 9
+  %c = select i1 %cmp2, i32 30, i32 0
+  call void @foo(i32 %c)
+  br label %end
+
+end:
+  ret void
+}
+
+declare void @foo(i32)
+declare i32 @bar(i32)
+
+define i32 @test_and(i32 %a, i32 %b) {
+; CHECK-LABEL: @test_and(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[A:%.*]], 0
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i32 [[B:%.*]], 0
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[CMP1]], [[CMP2]]
+; CHECK-NEXT:    br i1 [[AND]], label [[TPATH:%.*]], label [[END:%.*]]
+; CHECK:       tpath:
+; CHECK-NEXT:    ret i32 313
+; CHECK:       end:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %cmp1 = icmp ne i32 %a, 0
+  %cmp2 = icmp ne i32 %b, 0
+  %and = and i1 %cmp1, %cmp2
+  br i1 %and, label %tpath, label %end
+
+tpath:
+  %cmp3 = icmp eq i32 %a, 0 ;; <-- implied false
+  %c = select i1 %cmp3, i32 0, i32 313
+  ret i32 %c
+
+end:
+  ret i32 0
+}
+
+; cmp1 and cmp2 are false on the 'fpath' path and thus cmp3 is true.
+
+define i32 @test_or1(i32 %a, i32 %b) {
+; CHECK-LABEL: @test_or1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], 0
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[B:%.*]], 0
+; CHECK-NEXT:    [[OR:%.*]] = or i1 [[CMP1]], [[CMP2]]
+; CHECK-NEXT:    br i1 [[OR]], label [[END:%.*]], label [[FPATH:%.*]]
+; CHECK:       fpath:
+; CHECK-NEXT:    ret i32 37
+; CHECK:       end:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %cmp1 = icmp eq i32 %a, 0
+  %cmp2 = icmp eq i32 %b, 0
+  %or = or i1 %cmp1, %cmp2
+  br i1 %or, label %end, label %fpath
+
+fpath:
+  %cmp3 = icmp ne i32 %a, 0  ;; <-- implied true
+  %c = select i1 %cmp3, i32 37, i32 0
+  ret i32 %c
+
+end:
+  ret i32 0
+}
+
+; LHS ==> RHS by definition (true -> true)
+
+define void @test6(i32 %a, i32 %b) {
+; CHECK-LABEL: @test6(
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    br i1 [[CMP1]], label [[TAKEN:%.*]], label [[END:%.*]]
+; CHECK:       taken:
+; CHECK-NEXT:    call void @foo(i32 10)
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+  %cmp1 = icmp eq i32 %a, %b
+  br i1 %cmp1, label %taken, label %end
+
+taken:
+  %c = select i1 %cmp1, i32 10, i32 0
+  call void @foo(i32 %c)
+  br label %end
+
+end:
+  ret void
+}
+
+; LHS ==> RHS by definition (false -> false)
+
+define void @test7(i32 %a, i32 %b) {
+; CHECK-LABEL: @test7(
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    br i1 [[CMP1]], label [[END:%.*]], label [[TAKEN:%.*]]
+; CHECK:       taken:
+; CHECK-NEXT:    call void @foo(i32 11)
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+  %cmp1 = icmp eq i32 %a, %b
+  br i1 %cmp1, label %end, label %taken
+
+taken:
+  %c = select i1 %cmp1, i32 0, i32 11
+  call void @foo(i32 %c)
+  br label %end
+
+end:
+  ret void
+}
+