[DAGCombiner] try to form test+set out of shift+mask patterns

The motivating bugs are:
https://bugs.llvm.org/show_bug.cgi?id=41340
https://bugs.llvm.org/show_bug.cgi?id=42697

As discussed there, we could view this as a failure of IR canonicalization,
but then we would need to implement a backend fixup with target overrides
to get this right in all cases. Instead, we can just view this as a codegen
opportunity. It's not even clear for x86 exactly when we should favor
test+set; some CPUs have better theoretical throughput for the ALU ops than
bt/test.

This patch is made more complicated than I expected because there's an early
DAGCombine for 'and' that can change types of the intermediate ops via
trunc+anyext.

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

llvm-svn: 370668

2 files changed, 52 insertions, 32 deletions

diff --git a/llvm/test/CodeGen/Hexagon/tstbit.ll b/llvm/test/CodeGen/Hexagon/tstbit.ll
index a21ad8d9a1f..7c80fcb91ab 100644
--- a/llvm/test/CodeGen/Hexagon/tstbit.ll
+++ b/llvm/test/CodeGen/Hexagon/tstbit.ll
@@ -20,15 +20,25 @@ b0:
   ret i32 %v3
 }
 
+; TODO: Match to tstbit?
+
 define i64 @is_upper_bit_clear_i64(i64 %x) #0 {
 ; CHECK-LABEL: is_upper_bit_clear_i64:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    {
-; CHECK-NEXT:     p0 = tstbit(r1,#5)
-; CHECK-NEXT:     r1 = #0
+; CHECK-NEXT:     r4 = #0
+; CHECK-NEXT:     r2 = #32
+; CHECK-NEXT:     r7:6 = combine(#0,#0)
+; CHECK-NEXT:    }
+; CHECK-NEXT:    {
+; CHECK-NEXT:     r5 = and(r1,r2)
+; CHECK-NEXT:     r1 = r4
 ; CHECK-NEXT:    }
 ; CHECK-NEXT:    {
-; CHECK-NEXT:     r0 = mux(p0,#0,#1)
+; CHECK-NEXT:     p0 = cmp.eq(r5:4,r7:6)
+; CHECK-NEXT:    }
+; CHECK-NEXT:    {
+; CHECK-NEXT:     r0 = mux(p0,#1,#0)
 ; CHECK-NEXT:     jumpr r31
 ; CHECK-NEXT:    }
   %sh = lshr i64 %x, 37
@@ -37,15 +47,24 @@ define i64 @is_upper_bit_clear_i64(i64 %x) #0 {
   ret i64 %r
 }
 
+; TODO: Match to tstbit?
+
 define i64 @is_lower_bit_clear_i64(i64 %x) #0 {
 ; CHECK-LABEL: is_lower_bit_clear_i64:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    {
-; CHECK-NEXT:     p0 = tstbit(r0,#27)
+; CHECK-NEXT:     r5:4 = combine(#0,#0)
+; CHECK-NEXT:     r2 = ##134217728
 ; CHECK-NEXT:     r1 = #0
 ; CHECK-NEXT:    }
 ; CHECK-NEXT:    {
-; CHECK-NEXT:     r0 = mux(p0,#0,#1)
+; CHECK-NEXT:     r0 = and(r0,r2)
+; CHECK-NEXT:    }
+; CHECK-NEXT:    {
+; CHECK-NEXT:     p0 = cmp.eq(r1:0,r5:4)
+; CHECK-NEXT:    }
+; CHECK-NEXT:    {
+; CHECK-NEXT:     r0 = mux(p0,#1,#0)
 ; CHECK-NEXT:     jumpr r31
 ; CHECK-NEXT:    }
   %sh = lshr i64 %x, 27
@@ -54,14 +73,16 @@ define i64 @is_lower_bit_clear_i64(i64 %x) #0 {
   ret i64 %r
 }
 
+; TODO: Match to tstbit?
+
 define i32 @is_bit_clear_i32(i32 %x) #0 {
 ; CHECK-LABEL: is_bit_clear_i32:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    {
-; CHECK-NEXT:     p0 = tstbit(r0,#27)
+; CHECK-NEXT:     r0 = and(r0,##134217728)
 ; CHECK-NEXT:    }
 ; CHECK-NEXT:    {
-; CHECK-NEXT:     r0 = mux(p0,#0,#1)
+; CHECK-NEXT:     r0 = cmp.eq(r0,#0)
 ; CHECK-NEXT:     jumpr r31
 ; CHECK-NEXT:    }
   %sh = lshr i32 %x, 27
@@ -70,14 +91,16 @@ define i32 @is_bit_clear_i32(i32 %x) #0 {
   ret i32 %r
 }
 
+; TODO: Match to tstbit?
+
 define i16 @is_bit_clear_i16(i16 %x) #0 {
 ; CHECK-LABEL: is_bit_clear_i16:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    {
-; CHECK-NEXT:     p0 = tstbit(r0,#7)
+; CHECK-NEXT:     r0 = and(r0,#128)
 ; CHECK-NEXT:    }
 ; CHECK-NEXT:    {
-; CHECK-NEXT:     r0 = mux(p0,#0,#1)
+; CHECK-NEXT:     r0 = cmp.eq(r0,#0)
 ; CHECK-NEXT:     jumpr r31
 ; CHECK-NEXT:    }
   %sh = lshr i16 %x, 7
@@ -86,14 +109,16 @@ define i16 @is_bit_clear_i16(i16 %x) #0 {
   ret i16 %r
 }
 
+; TODO: Match to tstbit?
+
 define i8 @is_bit_clear_i8(i8 %x) #0 {
 ; CHECK-LABEL: is_bit_clear_i8:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    {
-; CHECK-NEXT:     p0 = tstbit(r0,#3)
+; CHECK-NEXT:     r0 = and(r0,#8)
 ; CHECK-NEXT:    }
 ; CHECK-NEXT:    {
-; CHECK-NEXT:     r0 = mux(p0,#0,#1)
+; CHECK-NEXT:     r0 = cmp.eq(r0,#0)
 ; CHECK-NEXT:     jumpr r31
 ; CHECK-NEXT:    }
   %sh = lshr i8 %x, 3
diff --git a/llvm/test/CodeGen/X86/test-vs-bittest.ll b/llvm/test/CodeGen/X86/test-vs-bittest.ll
index 8873a1cc543..2f93ad58ad3 100644
--- a/llvm/test/CodeGen/X86/test-vs-bittest.ll
+++ b/llvm/test/CodeGen/X86/test-vs-bittest.ll
@@ -393,10 +393,9 @@ no:
 define i64 @is_upper_bit_clear_i64(i64 %x) {
 ; CHECK-LABEL: is_upper_bit_clear_i64:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movq %rdi, %rax
-; CHECK-NEXT:    shrq $37, %rax
-; CHECK-NEXT:    notl %eax
-; CHECK-NEXT:    andl $1, %eax
+; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    btq $37, %rdi
+; CHECK-NEXT:    setae %al
 ; CHECK-NEXT:    retq
   %sh = lshr i64 %x, 37
   %m = and i64 %sh, 1
@@ -407,10 +406,9 @@ define i64 @is_upper_bit_clear_i64(i64 %x) {
 define i64 @is_lower_bit_clear_i64(i64 %x) {
 ; CHECK-LABEL: is_lower_bit_clear_i64:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movq %rdi, %rax
-; CHECK-NEXT:    shrl $27, %eax
-; CHECK-NEXT:    notl %eax
-; CHECK-NEXT:    andl $1, %eax
+; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    testl $134217728, %edi # imm = 0x8000000
+; CHECK-NEXT:    sete %al
 ; CHECK-NEXT:    retq
   %sh = lshr i64 %x, 27
   %m = and i64 %sh, 1
@@ -421,10 +419,9 @@ define i64 @is_lower_bit_clear_i64(i64 %x) {
 define i32 @is_bit_clear_i32(i32 %x) {
 ; CHECK-LABEL: is_bit_clear_i32:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movl %edi, %eax
-; CHECK-NEXT:    shrl $27, %eax
-; CHECK-NEXT:    notl %eax
-; CHECK-NEXT:    andl $1, %eax
+; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    testl $134217728, %edi # imm = 0x8000000
+; CHECK-NEXT:    sete %al
 ; CHECK-NEXT:    retq
   %sh = lshr i32 %x, 27
   %n = xor i32 %sh, -1
@@ -435,10 +432,9 @@ define i32 @is_bit_clear_i32(i32 %x) {
 define i16 @is_bit_clear_i16(i16 %x) {
 ; CHECK-LABEL: is_bit_clear_i16:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movzwl %di, %eax
-; CHECK-NEXT:    shrl $7, %eax
-; CHECK-NEXT:    notl %eax
-; CHECK-NEXT:    andl $1, %eax
+; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    testb $-128, %dil
+; CHECK-NEXT:    sete %al
 ; CHECK-NEXT:    # kill: def $ax killed $ax killed $eax
 ; CHECK-NEXT:    retq
   %sh = lshr i16 %x, 7
@@ -450,11 +446,8 @@ define i16 @is_bit_clear_i16(i16 %x) {
 define i8 @is_bit_clear_i8(i8 %x) {
 ; CHECK-LABEL: is_bit_clear_i8:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movl %edi, %eax
-; CHECK-NEXT:    shrb $3, %al
-; CHECK-NEXT:    notb %al
-; CHECK-NEXT:    andb $1, %al
-; CHECK-NEXT:    # kill: def $al killed $al killed $eax
+; CHECK-NEXT:    testb $8, %dil
+; CHECK-NEXT:    sete %al
 ; CHECK-NEXT:    retq
   %sh = lshr i8 %x, 3
   %m = and i8 %sh, 1
@@ -462,6 +455,8 @@ define i8 @is_bit_clear_i8(i8 %x) {
   ret i8 %r
 }
 
+; TODO: We could use bt/test on the 64-bit value.
+
 define i8 @overshift(i64 %x) {
 ; CHECK-LABEL: overshift:
 ; CHECK:       # %bb.0: