[X86] Use btc/btr/bts to implement xor/and/or that affects a single bit in the upper 32-bits of a 64-bit operation.

[craig.topper]

Summary

We can't fold a large immediate into a 64-bit operation. But if we know we're only operating on a single bit we can use the bit instructions.

[zvi]

The code change LGTM, but i'm not sure about the profitability. On recent Intel processors (not sure about AMD), 'or' can be executed at double throughput than 'bt'. Assuming the extra constant move being saved is hoisted out of a hot loop, are we gaining or losing?
For -Os this should be fine.

[craig.topper]

I can remove the change from TargetTransformInfo.cpp which would make the constants get hoisted by the ConstantHoisting pass. Would that help?

gcc and icc both use the bt instructions for at least simple single BB cases. I'll check some more complicated cases.

[spatel]

In D37418#859821, @zvi wrote:

The code change LGTM, but i'm not sure about the profitability. On recent Intel processors (not sure about AMD), 'or' can be executed at double throughput than 'bt'. Assuming the extra constant move being saved is hoisted out of a hot loop, are we gaining or losing?
For -Os this should be fine.

I suspect AMD CPUs would want the same output as Intel big cores on these. For example, Agner shows 2 uops for btc on Ryzen, so it has higher latency and less throughput than the plain logic ops. The extra uop is caused by the partial flags update of these instructions?

This is another example where we can't determine profitability in isel. So we should choose whatever we think helps the most common case there. Then, add an MI transform to alter it if we can find profit using uarch machine models and machine trace metrics. If the btc variant always reduces register pressure, that could be a good reason to choose it in isel?

[reames]

I ran into this case in a snippet of hot code just Friday, so I'm glad to see someone's working on it. :) In the case I had, the register allocator was spilling a register in a hot loop just to free up room for constant. I hadn't had a chance to actually performance test the tweaked assembly, but I'd be very surprised if the btc variant wasn't faster in that case.

In D37418#859967, @spatel wrote:

If the btc variant always reduces register pressure, that could be a good reason to choose it in isel?

Another option here would be to treat this as a register allocator rematerialization problem. We have precedent for doing that for loads which can be folded into instructions, and the "fold constant into instruction" pattern we see here seems somewhat similar in spirit.

Out of the other options, I can't see a late pattern match to convert and/constant form to btc working out very well. In particular, the spilling will have already been done and reversing that seems complicated. Starting with a btc and expanding to the constant/and pattern might be a bit better, but then I worry about missed hoisting opportunities in loops with registers live over them which could have been spill/filled outside the loop.

On a vaguely related topic, has anyone looked at the possible benefit of producing single bit constants via an 8 bit move immediate and a shift immediate? If I'm remembering correctly, it should encode smaller.

[zvi]

In D37418#859967, @spatel wrote:

This is another example where we can't determine profitability in isel. So we should choose whatever we think helps the most common case there. Then, add an MI transform to alter it if we can find profit using uarch machine models and machine trace metrics. If the btc variant always reduces register pressure, that could be a good reason to choose it in isel?

This is a good argument, but then as @reames mentioned we could also try to handle register-pressure at spill-time by letting the target try some peephole-ish tricks to avoid spilling; not sure how well will this fits in the existing regalloc infrastructure.
FWIW, we set different scheduling strategies for 32-bit and 64-bit due to the difference in register abundance:

else if (Subtarget.is64Bit())
    setSchedulingPreference(Sched::ILP);
  else
    setSchedulingPreference(Sched::RegPressure);

[craig.topper]

Remove the X86TargetTransformInfo.cpp changes and rebase.

Still need to change to -Os only

[craig.topper]

This comment was removed by craig.topper.

[craig.topper]

Qualify with optsize. Add tests with/without optsize

[craig.topper]

Once more with test file

[zvi]

LGTM

lib/Target/X86/X86ISelDAGToDAG.cpp

inline SDValue getI8Imm(unsigned Imm, const SDLoc &DL) {
       return CurDAG->getTargetConstant(Imm, DL, MVT::i8);
     }
 
     /// Return a target constant with the specified value, of type i32.
     inline SDValue getI32Imm(unsigned Imm, const SDLoc &DL) {
       return CurDAG->getTargetConstant(Imm, DL, MVT::i32);
     }
 
+    /// Return a target constant with the specified value, of type i64.
+    inline SDValue getI64Imm(uint64_t Imm, const SDLoc &DL) {
+      return CurDAG->getTargetConstant(Imm, DL, MVT::i64);
+    }
+
     SDValue getExtractVEXTRACTImmediate(SDNode *N, unsigned VecWidth,
                                         const SDLoc &DL) {
       assert((VecWidth == 128 || VecWidth == 256) && "Unexpected vector width");
       uint64_t Index = N->getConstantOperandVal(1);
       MVT VecVT = N->getOperand(0).getSimpleValueType();
       return getI8Imm((Index * VecVT.getScalarSizeInBits()) / VecWidth, DL);
     }
 

lib/Target/X86/X86InstrCompiler.td

 // r & (2^8-1) ==> movz
 def : Pat<(and GR64:$src, 0xff),
           (SUBREG_TO_REG (i64 0),
                          (MOVZX32rr8 (i8 (EXTRACT_SUBREG GR64:$src, sub_8bit))),
                          sub_32bit)>;
 } // AddedComplexity = 1
 
 
+// Try to use BTS/BTR/BTC for single bit operations on the upper 32-bits.
+
+def BTRXForm : SDNodeXForm<imm, [{
+  // Transformation function: Find the lowest 0.
+  return getI64Imm((uint8_t)N->getAPIntValue().countTrailingOnes(), SDLoc(N));
+}]>;
+
+def BTCBTSXForm : SDNodeXForm<imm, [{
+  // Transformation function: Find the lowest 1.
+  return getI64Imm((uint8_t)N->getAPIntValue().countTrailingZeros(), SDLoc(N));
+}]>;
+
+def BTRMask64 : ImmLeaf<i64, [{
+  return !isUInt<32>(Imm) && !isInt<32>(Imm) && isPowerOf2_64(~Imm);
+}]>;
+
+def BTCBTSMask64 : ImmLeaf<i64, [{
+  return !isInt<32>(Imm) && isPowerOf2_64(Imm);
+}]>;
+
+// For now only do this for optsize.
+let AddedComplexity = 1, Predicates=[OptForSize] in {
+  def : Pat<(and GR64:$src1, BTRMask64:$mask),
+            (BTR64ri8 GR64:$src1, (BTRXForm imm:$mask))>;
+  def : Pat<(or GR64:$src1, BTCBTSMask64:$mask),
+            (BTS64ri8 GR64:$src1, (BTCBTSXForm imm:$mask))>;
+  def : Pat<(xor GR64:$src1, BTCBTSMask64:$mask),
+            (BTC64ri8 GR64:$src1, (BTCBTSXForm imm:$mask))>;
+}
+
+
 // sext_inreg patterns
 def : Pat<(sext_inreg GR32:$src, i16),
           (MOVSX32rr16 (EXTRACT_SUBREG GR32:$src, sub_16bit))>;
 def : Pat<(sext_inreg GR32:$src, i8),
           (MOVSX32rr8 (EXTRACT_SUBREG GR32:$src, sub_8bit))>;
 
 def : Pat<(sext_inreg GR16:$src, i8),
            (EXTRACT_SUBREG (MOVSX32rr8 (EXTRACT_SUBREG GR16:$src, sub_8bit)),

lib/Target/X86/X86InstrInfo.td

 }]>;
 
 def BEXTRMaskXForm : SDNodeXForm<imm, [{
   unsigned Length = countTrailingOnes(N->getZExtValue());
   return getI32Imm(Length << 8, SDLoc(N));
 }]>;
 
 def AndMask64 : ImmLeaf<i64, [{
-  return isMask_64(Imm) && Imm > UINT32_MAX;
+  return isMask_64(Imm) && !isUInt<32>(Imm);
 }]>;
 
 // Use BEXTR for 64-bit 'and' with large immediate 'mask'.
 let Predicates = [HasBMI, NoBMI2, NoTBM] in {
   def : Pat<(and GR64:$src, AndMask64:$mask),
             (BEXTR64rr GR64:$src,
               (SUBREG_TO_REG (i64 0),
                              (MOV32ri (BEXTRMaskXForm imm:$mask)), sub_32bit))>;

test/CodeGen/X86/x86-64-bittest-logic.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=x86_64-pc-linux | FileCheck %s
+
+define i64 @and1(i64 %x) {
+; CHECK-LABEL: and1:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movabsq $-2147483649, %rax # imm = 0xFFFFFFFF7FFFFFFF
+; CHECK-NEXT:    andq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = and i64 %x, 18446744071562067967 ; clear bit 31
+  ret i64 %a
+}
+
+define i64 @and2(i64 %x) {
+; CHECK-LABEL: and2:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movabsq $-4294967297, %rax # imm = 0xFFFFFFFEFFFFFFFF
+; CHECK-NEXT:    andq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = and i64 %x, 18446744069414584319 ; clear bit 32
+  ret i64 %a
+}
+
+define i64 @and3(i64 %x) {
+; CHECK-LABEL: and3:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movabsq $-4611686018427387905, %rax # imm = 0xBFFFFFFFFFFFFFFF
+; CHECK-NEXT:    andq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = and i64 %x, 13835058055282163711 ; clear bit 62
+  ret i64 %a
+}
+
+define i64 @and4(i64 %x) {
+; CHECK-LABEL: and4:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movabsq $9223372036854775807, %rax # imm = 0x7FFFFFFFFFFFFFFF
+; CHECK-NEXT:    andq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = and i64 %x, 9223372036854775807 ; clear bit 63
+  ret i64 %a
+}
+
+define i64 @or1(i64 %x) {
+; CHECK-LABEL: or1:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movl $2147483648, %eax # imm = 0x80000000
+; CHECK-NEXT:    orq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = or i64 %x, 2147483648 ; set bit 31
+  ret i64 %a
+}
+
+define i64 @or2(i64 %x) {
+; CHECK-LABEL: or2:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movabsq $4294967296, %rax # imm = 0x100000000
+; CHECK-NEXT:    orq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = or i64 %x, 4294967296 ; set bit 32
+  ret i64 %a
+}
+
+define i64 @or3(i64 %x) {
+; CHECK-LABEL: or3:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movabsq $4611686018427387904, %rax # imm = 0x4000000000000000
+; CHECK-NEXT:    orq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = or i64 %x, 4611686018427387904 ; set bit 62
+  ret i64 %a
+}
+
+define i64 @or4(i64 %x) {
+; CHECK-LABEL: or4:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movabsq $-9223372036854775808, %rax # imm = 0x8000000000000000
+; CHECK-NEXT:    orq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = or i64 %x, 9223372036854775808 ; set bit 63
+  ret i64 %a
+}
+
+define i64 @xor1(i64 %x) {
+; CHECK-LABEL: xor1:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movl $2147483648, %eax # imm = 0x80000000
+; CHECK-NEXT:    xorq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = xor i64 %x, 2147483648 ; toggle bit 31
+  ret i64 %a
+}
+
+define i64 @xor2(i64 %x) {
+; CHECK-LABEL: xor2:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movabsq $4294967296, %rax # imm = 0x100000000
+; CHECK-NEXT:    xorq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = xor i64 %x, 4294967296 ; toggle bit 32
+  ret i64 %a
+}
+
+define i64 @xor3(i64 %x) {
+; CHECK-LABEL: xor3:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movabsq $4611686018427387904, %rax # imm = 0x4000000000000000
+; CHECK-NEXT:    xorq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = xor i64 %x, 4611686018427387904 ; toggle bit 62
+  ret i64 %a
+}
+
+define i64 @xor4(i64 %x) {
+; CHECK-LABEL: xor4:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movabsq $-9223372036854775808, %rax # imm = 0x8000000000000000
+; CHECK-NEXT:    xorq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = xor i64 %x, 9223372036854775808 ; toggle bit 63
+  ret i64 %a
+}
+
+define i64 @and1_optsize(i64 %x) optsize {
+; CHECK-LABEL: and1_optsize:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    btrq $31, %rdi
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = and i64 %x, 18446744071562067967 ; clear bit 31
+  ret i64 %a
+}
+
+define i64 @and2_optsize(i64 %x) optsize {
+; CHECK-LABEL: and2_optsize:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    btrq $32, %rdi
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = and i64 %x, 18446744069414584319 ; clear bit 32
+  ret i64 %a
+}
+
+define i64 @and3_optsize(i64 %x) optsize {
+; CHECK-LABEL: and3_optsize:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    btrq $62, %rdi
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = and i64 %x, 13835058055282163711 ; clear bit 62
+  ret i64 %a
+}
+
+define i64 @and4_optsize(i64 %x) optsize {
+; CHECK-LABEL: and4_optsize:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    btrq $63, %rdi
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = and i64 %x, 9223372036854775807 ; clear bit 63
+  ret i64 %a
+}
+
+define i64 @or1_optsize(i64 %x) optsize {
+; CHECK-LABEL: or1_optsize:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    btsq $31, %rdi
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = or i64 %x, 2147483648 ; set bit 31
+  ret i64 %a
+}
+
+define i64 @or2_optsize(i64 %x) optsize {
+; CHECK-LABEL: or2_optsize:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    btsq $32, %rdi
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = or i64 %x, 4294967296 ; set bit 32
+  ret i64 %a
+}
+
+define i64 @or3_optsize(i64 %x) optsize {
+; CHECK-LABEL: or3_optsize:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    btsq $62, %rdi
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = or i64 %x, 4611686018427387904 ; set bit 62
+  ret i64 %a
+}
+
+define i64 @or4_optsize(i64 %x) optsize {
+; CHECK-LABEL: or4_optsize:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    btsq $63, %rdi
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = or i64 %x, 9223372036854775808 ; set bit 63
+  ret i64 %a
+}
+
+define i64 @xor1_optsize(i64 %x) optsize {
+; CHECK-LABEL: xor1_optsize:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    btcq $31, %rdi
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = xor i64 %x, 2147483648 ; toggle bit 31
+  ret i64 %a
+}
+
+define i64 @xor2_optsize(i64 %x) optsize {
+; CHECK-LABEL: xor2_optsize:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    btcq $32, %rdi
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = xor i64 %x, 4294967296 ; toggle bit 32
+  ret i64 %a
+}
+
+define i64 @xor3_optsize(i64 %x) optsize {
+; CHECK-LABEL: xor3_optsize:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    btcq $62, %rdi
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = xor i64 %x, 4611686018427387904 ; toggle bit 62
+  ret i64 %a
+}
+
+define i64 @xor4_optsize(i64 %x) optsize {
+; CHECK-LABEL: xor4_optsize:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    btcq $63, %rdi
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    retq
+  %a = xor i64 %x, 9223372036854775808 ; toggle bit 63
+  ret i64 %a
+}