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

[spatel]

Summary

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 target-specific 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.

[craig.topper]

llvm/lib/Target/X86/X86ISelLowering.cpp

39006 ↗

(On Diff #216957)

How do we know the shift amount isn't bigger than the bit width?

[lebedev.ri]

I would think this should go into DAGCombiner under hasBitTest() hook.

[lebedev.ri]

llvm/lib/Target/X86/X86ISelLowering.cpp

38981 ↗

(On Diff #216957)

I'd think we should, it should just change the predicate i think?

[craig.topper]

llvm/lib/Target/X86/X86ISelLowering.cpp

38981 ↗

(On Diff #216957)

Without the not we don’t save any instructions do we? Setcc also has lower throughput on recent Intel CPUs and has a partial register update..

[spatel]

In D66687#1644003, @lebedev.ri wrote:

I would think this should go into DAGCombiner under hasBitTest() hook.

Yes, I forgot we have that hook. Hexagon has enabled it as well as x86, so I added some more tests.

llvm/lib/Target/X86/X86ISelLowering.cpp

38981 ↗

(On Diff #216957)

In all the tests I looked at, we avoid the partial reg update problem by xor'ing the reg. But yes, without the 'not' instruction, this is trading 2 instructions for 2 instructions that might have less throughput.

39006 ↗

(On Diff #216957)

Yes, good catch. I think we're safe in the basic case without trunc/ext (all oversized shifts get folded to undef), but since we're potentially truncating the input value, we either need to guard against that or add some logic to decide what width we should do the and/setcc. I'll add a bailout for now.

[spatel]

Patch updated:

1. Move the code to DAGCombiner using the hasBitTest() TLI hook.
2. Add a bailout if the shift amount exceeds a potentially narrower bitwidth.
3. Copy tests to Hexagon target and update for diffs.

[spatel]

I think the Hexagon diffs are an improvement, but I don't know what is optimal there; adding Krzysztof as reviewer.

[craig.topper]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5225 ↗

(On Diff #217058)

Is it possible for the shift to be on a type larger than 64 bits and have an absurdly out of bounds shift amount that we haven't collapsed to undef yet such that this asserts? Or for that matter a 64 bit shift amount that's larger than 0xffffffff and not been folded yet. Since we truncate a uint64_t to unsigned here.

[spatel]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5225 ↗

(On Diff #217058)

Given current limits, I don't think either of those scenarios are possible. IR types are capped well below 2^32:
http://llvm.org/docs/LangRef.html#integer-type

And we shouldn't create an overshift node in the 1st place:
SelectionDAG::simplifyShift() - https://github.com/llvm-mirror/llvm/blob/master/lib/CodeGen/SelectionDAG/SelectionDAG.cpp#L7120

If that's somehow violated, then the underlying assert in APInt should fire within SDValue::getConstantOperandVal().

But there's practically no cost for leaving the shift amount as uint64_t rather than unsigned, so I can change that.

[spatel]

Patch updated:

1. Use 'uint64_t' for shift amount instead of implicitly truncating with 'unsigned'.
2. Fix x86-specific code comment that was left over from earlier rev.

[craig.topper]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5225 ↗

(On Diff #217058)

My first scenario was just something like i128 with a shift amount greater than 1 << 64 which would assert in getConstantOperandVal. I know we try to simplify shifts when they're created. I was just worried about a scenario where the shift amount isn't constant when we created it but something folded behind the shift to make it constant and out of bounds then we visited the 'and' node without visiting the shift to simplify it. Its probably not a very realistic scenario, but I know Simon has updated some things to not use getConstantOperandVal because weird scenarios have come up.

[spatel]

Patch updated:
More protection against unexpectedly huge numbers: use getConstantOperandAPInt() rather than getConstantOperandVal().

[craig.topper]

LGTM

[spatel]

Patch updated:
Rebased after rL369947
@kparzysz - do we need to add more/different pattern-matching to form 'tstbit'?

[lebedev.ri]

Looks ok to me.

[xbolva00]

In D66687#1651582, @lebedev.ri wrote:

Looks ok to me.

But hexagon’s codegen regressed :(

[spatel]

In D66687#1652272, @xbolva00 wrote:

In D66687#1651582, @lebedev.ri wrote:

Looks ok to me.

But hexagon’s codegen regressed :(

Yes, although it only regressed after the changes from rL369947 which looks like a response to the earlier rev of this patch.
Ping @kparzysz to see if we should wait for another Hexagon update or if we can proceed and mark those tests with 'TODO'.

[xbolva00]

Yeah,

int foo_b(int a) {

return (a&1024) == 0;

}

seems to form tstbit..

but more typical case:
_Bool afoo_b(int a) {

return (a&1024) == 0;

}

forms and and cmp.eq...

if hexagon enables hasBitTest(), it is not ideal that it cannot handle this basic case - it should be fixed.

https://godbolt.org/z/gG-6j4

[xbolva00]

if hexagon enables hasBitTest(), it is not ideal that it cannot handle this basic case - it should be fixed.

..but since this is hexagon general problem (just exposed more now), it should not block this patch futher.

[spatel]

Filed a hexagon bug here, so this is not lost:
https://bugs.llvm.org/show_bug.cgi?id=43194

llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::unfoldExtremeBitClearingToShifts(SDNode *N) {
   //     tmp = x   'opposite logical shift' y
   SDValue T0 = DAG.getNode(InnerShift, DL, VT, X, Y);
   //     ret = tmp 'logical shift' y
   SDValue T1 = DAG.getNode(OuterShift, DL, VT, T0, Y);
 
   return T1;
 }
 
+/// Try to replace shift/logic that tests if a bit is clear with mask + setcc.
+/// For a target with a bit test, this is expected to become test + set and save
+/// at least 1 instruction.
+static SDValue combineShiftAnd1ToBitTest(SDNode *And, SelectionDAG &DAG) {
+  assert(And->getOpcode() == ISD::AND && "Expected an 'and' op");
+
+  // This is probably not worthwhile without a supported type.
+  EVT VT = And->getValueType(0);
+  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
+  if (!TLI.isTypeLegal(VT))
+    return SDValue();
+
+  // Look through an optional extension and find a 'not'.
+  // TODO: Should we favor test+set even without the 'not' op?
+  SDValue Not = And->getOperand(0), And1 = And->getOperand(1);
+  if (Not.getOpcode() == ISD::ANY_EXTEND)
+    Not = Not.getOperand(0);
+  if (!isBitwiseNot(Not) || !Not.hasOneUse() || !isOneConstant(And1))
+    return SDValue();
+
+  // Look though an optional truncation. The source operand may not be the same
+  // type as the original 'and', but that is ok because we are masking off
+  // everything but the low bit.
+  SDValue Srl = Not.getOperand(0);
+  if (Srl.getOpcode() == ISD::TRUNCATE)
+    Srl = Srl.getOperand(0);
+
+  // Match a shift-right by constant.
+  if (Srl.getOpcode() != ISD::SRL || !Srl.hasOneUse() ||
+      !isa<ConstantSDNode>(Srl.getOperand(1)))
+    return SDValue();
+
+  // We might have looked through casts that make this transform invalid.
+  // TODO: If the source type is wider than the result type, do the mask and
+  //       compare in the source type.
+  const APInt &ShiftAmt = Srl.getConstantOperandAPInt(1);
+  unsigned VTBitWidth = VT.getSizeInBits();
+  if (ShiftAmt.uge(VTBitWidth))
+    return SDValue();
+
+  // Turn this into a bit-test pattern using mask op + setcc:
+  // and (not (srl X, C)), 1 --> (and X, 1<<C) == 0
+  SDLoc DL(And);
+  SDValue X = DAG.getZExtOrTrunc(Srl.getOperand(0), DL, VT);
+  EVT CCVT = TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), VT);
+  SDValue Mask = DAG.getConstant(
+      APInt::getOneBitSet(VTBitWidth, ShiftAmt.getZExtValue()), DL, VT);
+  SDValue NewAnd = DAG.getNode(ISD::AND, DL, VT, X, Mask);
+  SDValue Zero = DAG.getConstant(0, DL, VT);
+  SDValue Setcc = DAG.getSetCC(DL, CCVT, NewAnd, Zero, ISD::SETEQ);
+  return DAG.getZExtOrTrunc(Setcc, DL, VT);
+}
+
 SDValue DAGCombiner::visitAND(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N1.getValueType();
 
   // x & x --> x
   if (N0 == N1)
     return N0;
if (N1C && N1C->getAPIntValue() == 0xffff && N0.getOpcode() == ISD::OR) {
     if (SDValue BSwap = MatchBSwapHWordLow(N0.getNode(), N0.getOperand(0),
                                            N0.getOperand(1), false))
       return BSwap;
   }
 
   if (SDValue Shifts = unfoldExtremeBitClearingToShifts(N))
     return Shifts;
 
+  if (TLI.hasBitTest(N0, N1))
+    if (SDValue V = combineShiftAnd1ToBitTest(N, DAG))
+      return V;
+
   return SDValue();
 }
 
 /// Match (a >> 8) | (a << 8) as (bswap a) >> 16.
 SDValue DAGCombiner::MatchBSwapHWordLow(SDNode *N, SDValue N0, SDValue N1,
                                         bool DemandHighBits) {
   if (!LegalOperations)
     return SDValue();

llvm/trunk/test/CodeGen/Hexagon/tstbit.ll

 b0:
   %v0 = shl i32 1, %a1
   %v1 = and i32 %v0, %a0
   %v2 = icmp ne i32 %v1, 0
   %v3 = zext i1 %v2 to i32
   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
   %m = and i64 %sh, 1
   %r = xor i64 %m, 1
   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
   %m = and i64 %sh, 1
   %r = xor i64 %m, 1
   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
   %n = xor i32 %sh, -1
   %r = and i32 %n, 1
   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
   %m = and i16 %sh, 1
   %r = xor i16 %m, 1
   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
   %m = and i8 %sh, 1
   %r = xor i8 %m, 1
   ret i8 %r
 }
 
 
 attributes #0 = { nounwind readnone }

llvm/trunk/test/CodeGen/X86/test-vs-bittest.ll

yes:
   ret void
 no:
   ret void
 }
 
 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
   %r = xor i64 %m, 1
   ret i64 %r
 }
 
 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
   %r = xor i64 %m, 1
   ret i64 %r
 }
 
 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
   %r = and i32 %n, 1
   ret i32 %r
 }
 
 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
   %m = and i16 %sh, 1
   %r = xor i16 %m, 1
   ret i16 %r
 }
 
 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
   %r = xor i8 %m, 1
   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:
 ; CHECK-NEXT:    movq %rdi, %rax
 ; CHECK-NEXT:    shrq $42, %rax
 ; CHECK-NEXT:    notb %al
 ; CHECK-NEXT:    andb $1, %al
 ; CHECK-NEXT:    # kill: def $al killed $al killed $rax