[RISCV] Optimize or/xor with immediate in Zbs extension

[benshi001]

Summary

This patch optimize or/xor with immediate to a pair of BSETI/BINVI
if the immediate has exactly two set bits.

[luismarques]

We need to optimize integer materialization, both in general and to take advantage of bitmanip. I suppose that the baseline test would be less bad if we had done that, but that this optimization would still be worth it?

llvm/lib/Target/RISCV/RISCVISelDAGToDAG.cpp

1293 ↗

(On Diff #345141)

The code already seems self-explanatory. Remove?

1299 ↗

(On Diff #345141)

"The immediate must have exactly two bits set."

llvm/lib/Target/RISCV/RISCVInstrInfoB.td

90

"only two set bits" -> "two set bits", otherwise it seems it's "up to two bits"

[MaskRay]

Can this be moved into RISCVTargetLowering::targetShrinkDemandedConstant? aarch64 has a great optimizeLogicalImm which may give some inspiration.

[benshi001]

In D102398#2758657, @MaskRay wrote:

Can this be moved into RISCVTargetLowering::targetShrinkDemandedConstant? aarch64 has a great optimizeLogicalImm which may give some inspiration.

Thanks. I have investigated AArch64's targetShrinkDemandedConstant and optimizeLogicalImm, but do not think my optimization is suitable to be there.

AArch64's optimizeLogicalImm does optimize the immediate operand but does not change the operator.

While my optimization changes the operator from or/xor to bseti/binvi.

[benshi001]

In D102398#2758054, @luismarques wrote:

We need to optimize integer materialization, both in general and to take advantage of bitmanip. I suppose that the baseline test would be less bad if we had done that, but that this optimization would still be worth it?

Thanks for your suggestion. I will check if integer materialization can be optimized by bitmanip. But I still think my optimization is worthy to do. Snice it saves an unnecessary or/xor instr.

[craig.topper]

Please write a description of the patch so that it will go in the git log when it's committed. It would be good if you could mention Zbs in the title.

llvm/lib/Target/RISCV/RISCVInstrInfoB.td

91

Why does this need to be a ComplexPattern? Can't we do it with an ImmLeaf?

93

Btis->Bits

99

Btis->Bits

[craig.topper]

llvm/lib/Target/RISCV/RISCVInstrInfoB.td

91

Maybe we can't check one use from ImmLeaf?

[craig.topper]

llvm/lib/Target/RISCV/RISCVInstrInfoB.td

91

But we can use PatLeaf<(imm), [{ }]> I think that's the way to go. I'll post a patch to do the same to AddiPair.

[benshi001]

In D102398#2759893, @craig.topper wrote:

Please write a description of the patch so that it will go in the git log when it's committed. It would be good if you could mention Zbs in the title.

Thanks for your comments. I have write a brief description.

[craig.topper]

LGTM. Do you plan to do this for BCLR as well?

Can we use ORI+BSETI if there is one bit set in bits 63:11 and multiple bits in bits 10:0?

[benshi001]

In D102398#2762194, @craig.topper wrote:

LGTM. Do you plan to do this for BCLR as well?

Can we use ORI+BSETI if there is one bit set in bits 63:11 and multiple bits in bits 10:0?

Thanks for your suggestion. I will do them in other patches. BTW, could you please also approve https://reviews.llvm.org/D102396 ?

Current patch depends on it.

[benshi001]

sorry, I pushed a wrong revision， it seems my description "This patch optimize or/xor with immediate to a pair of BSETI/BINVI
if the immediate has exactly two set bits."

is not included in my commit message.

I will pay attention to that in my future patches/commits.

And the pushed code is the exactly what Craig has approved.

llvm/lib/Target/RISCV/RISCVInstrInfoB.td

 
 // Checks if this mask has a single 1 bit and cannot be used with ORI/XORI.
 def BSETINVMask : ImmLeaf<XLenVT, [{
   if (Subtarget->is64Bit())
     return !isInt<12>(Imm) && isPowerOf2_64(Imm);
   return !isInt<12>(Imm) && isPowerOf2_32(Imm);
 }], BSETINVXForm>;
 
+// Check if (or r, i) can be optimized to (BSETI (BSETI r, i0), i1),
+// in which i = (1 << i0) | (1 << i1).
+def BSETINVTwoBitsMask : PatLeaf<(imm), [{
+   if (!N->hasOneUse())
+     return false;
+   // The immediate should not be a simm12.
+   if (isInt<12>(N->getSExtValue()))
+     return false;
+   // The immediate must have exactly two bits set.
+   return countPopulation(N->getZExtValue()) == 2;
+}]>;
+
+def BSETINVTwoBitsMaskLow : SDNodeXForm<imm, [{
+  uint64_t I = N->getZExtValue();
+  return CurDAG->getTargetConstant(countTrailingZeros(I), SDLoc(N),
+                                   N->getValueType(0));
+}]>;
+
+def BSETINVTwoBitsMaskHigh : SDNodeXForm<imm, [{
+  uint64_t I = N->getZExtValue();
+  return CurDAG->getTargetConstant(63 - countLeadingZeros(I), SDLoc(N),
+                                   N->getValueType(0));
+}]>;
+
 //===----------------------------------------------------------------------===//
 // Instruction class templates
 //===----------------------------------------------------------------------===//
 
 // Some of these templates should be moved to RISCVInstrFormats.td once the B
 // extension has been ratified.
 
 let hasSideEffects = 0, mayLoad = 0, mayStore = 0 in
def : Pat<(and GPR:$rs1, BCLRMask:$mask),
           (BCLRI GPR:$rs1, BCLRMask:$mask)>;
 def : Pat<(or GPR:$rs1, BSETINVMask:$mask),
           (BSETI GPR:$rs1, BSETINVMask:$mask)>;
 def : Pat<(xor GPR:$rs1, BSETINVMask:$mask),
           (BINVI GPR:$rs1, BSETINVMask:$mask)>;
 
 def : Pat<(and (srl GPR:$rs1, uimmlog2xlen:$shamt), (XLenVT 1)),
           (BEXTI GPR:$rs1, uimmlog2xlen:$shamt)>;
+
+def : Pat<(or GPR:$r, BSETINVTwoBitsMask:$i),
+          (BSETI (BSETI GPR:$r, (BSETINVTwoBitsMaskLow BSETINVTwoBitsMask:$i)),
+                 (BSETINVTwoBitsMaskHigh BSETINVTwoBitsMask:$i))>;
+def : Pat<(xor GPR:$r, BSETINVTwoBitsMask:$i),
+          (BINVI (BINVI GPR:$r, (BSETINVTwoBitsMaskLow BSETINVTwoBitsMask:$i)),
+                 (BSETINVTwoBitsMaskHigh BSETINVTwoBitsMask:$i))>;
 }
 
 // There's no encoding for roli in the the 'B' extension as it can be
 // implemented with rori by negating the immediate.
 let Predicates = [HasStdExtZbbOrZbp] in {
 def : PatGprImm<rotr, RORI, uimmlog2xlen>;
 def : Pat<(rotl GPR:$rs1, uimmlog2xlen:$shamt),
           (RORI GPR:$rs1, (ImmSubFromXLen uimmlog2xlen:$shamt))>;

llvm/test/CodeGen/RISCV/rv32zbs.ll

 ; RV32I:       # %bb.0:
 ; RV32I-NEXT:    lui a1, 1
 ; RV32I-NEXT:    addi a1, a1, 2
 ; RV32I-NEXT:    xor a0, a0, a1
 ; RV32I-NEXT:    ret
 ;
 ; RV32IB-LABEL: xor_i32_4098:
 ; RV32IB:       # %bb.0:
-; RV32IB-NEXT:    lui a1, 1
-; RV32IB-NEXT:    addi a1, a1, 2
-; RV32IB-NEXT:    xor a0, a0, a1
+; RV32IB-NEXT:    binvi a0, a0, 1
+; RV32IB-NEXT:    binvi a0, a0, 12
 ; RV32IB-NEXT:    ret
 ;
 ; RV32IBS-LABEL: xor_i32_4098:
 ; RV32IBS:       # %bb.0:
-; RV32IBS-NEXT:    lui a1, 1
-; RV32IBS-NEXT:    addi a1, a1, 2
-; RV32IBS-NEXT:    xor a0, a0, a1
+; RV32IBS-NEXT:    binvi a0, a0, 1
+; RV32IBS-NEXT:    binvi a0, a0, 12
 ; RV32IBS-NEXT:    ret
   %xor = xor i32 %a, 4098
   ret i32 %xor
 }
 
 define i32 @xor_i32_4099(i32 %a) nounwind {
 ; RV32I-LABEL: xor_i32_4099:
 ; RV32I:       # %bb.0:

 ; RV32I:       # %bb.0:
 ; RV32I-NEXT:    lui a1, 1
 ; RV32I-NEXT:    addi a1, a1, 2
 ; RV32I-NEXT:    or a0, a0, a1
 ; RV32I-NEXT:    ret
 ;
 ; RV32IB-LABEL: or_i32_4098:
 ; RV32IB:       # %bb.0:
-; RV32IB-NEXT:    lui a1, 1
-; RV32IB-NEXT:    addi a1, a1, 2
-; RV32IB-NEXT:    or a0, a0, a1
+; RV32IB-NEXT:    bseti a0, a0, 1
+; RV32IB-NEXT:    bseti a0, a0, 12
 ; RV32IB-NEXT:    ret
 ;
 ; RV32IBS-LABEL: or_i32_4098:
 ; RV32IBS:       # %bb.0:
-; RV32IBS-NEXT:    lui a1, 1
-; RV32IBS-NEXT:    addi a1, a1, 2
-; RV32IBS-NEXT:    or a0, a0, a1
+; RV32IBS-NEXT:    bseti a0, a0, 1
+; RV32IBS-NEXT:    bseti a0, a0, 12
 ; RV32IBS-NEXT:    ret
   %or = or i32 %a, 4098
   ret i32 %or
 }
 
 define i32 @or_i32_4099(i32 %a) nounwind {
 ; RV32I-LABEL: or_i32_4099:
 ; RV32I:       # %bb.0:

llvm/test/CodeGen/RISCV/rv64zbs.ll

 ; RV64I-NEXT:    addi a1, zero, 1
 ; RV64I-NEXT:    slli a1, a1, 32
 ; RV64I-NEXT:    addi a1, a1, 1
 ; RV64I-NEXT:    xor a0, a0, a1
 ; RV64I-NEXT:    ret
 ;
 ; RV64IB-LABEL: xor_i64_large:
 ; RV64IB:       # %bb.0:
-; RV64IB-NEXT:    addi a1, zero, 1
-; RV64IB-NEXT:    slli a1, a1, 32
-; RV64IB-NEXT:    addi a1, a1, 1
-; RV64IB-NEXT:    xor a0, a0, a1
+; RV64IB-NEXT:    binvi a0, a0, 0
+; RV64IB-NEXT:    binvi a0, a0, 32
 ; RV64IB-NEXT:    ret
 ;
 ; RV64IBS-LABEL: xor_i64_large:
 ; RV64IBS:       # %bb.0:
-; RV64IBS-NEXT:    addi a1, zero, 1
-; RV64IBS-NEXT:    slli a1, a1, 32
-; RV64IBS-NEXT:    addi a1, a1, 1
-; RV64IBS-NEXT:    xor a0, a0, a1
+; RV64IBS-NEXT:    binvi a0, a0, 0
+; RV64IBS-NEXT:    binvi a0, a0, 32
 ; RV64IBS-NEXT:    ret
   %xor = xor i64 %a, 4294967297
   ret i64 %xor
 }
 
 define i64 @xor_i64_4099(i64 %a) nounwind {
 ; RV64I-LABEL: xor_i64_4099:
 ; RV64I:       # %bb.0:

 ; RV64I-NEXT:    addi a1, zero, 1
 ; RV64I-NEXT:    slli a1, a1, 32
 ; RV64I-NEXT:    addi a1, a1, 1
 ; RV64I-NEXT:    or a0, a0, a1
 ; RV64I-NEXT:    ret
 ;
 ; RV64IB-LABEL: or_i64_large:
 ; RV64IB:       # %bb.0:
-; RV64IB-NEXT:    addi a1, zero, 1
-; RV64IB-NEXT:    slli a1, a1, 32
-; RV64IB-NEXT:    addi a1, a1, 1
-; RV64IB-NEXT:    or a0, a0, a1
+; RV64IB-NEXT:    bseti a0, a0, 0
+; RV64IB-NEXT:    bseti a0, a0, 32
 ; RV64IB-NEXT:    ret
 ;
 ; RV64IBS-LABEL: or_i64_large:
 ; RV64IBS:       # %bb.0:
-; RV64IBS-NEXT:    addi a1, zero, 1
-; RV64IBS-NEXT:    slli a1, a1, 32
-; RV64IBS-NEXT:    addi a1, a1, 1
-; RV64IBS-NEXT:    or a0, a0, a1
+; RV64IBS-NEXT:    bseti a0, a0, 0
+; RV64IBS-NEXT:    bseti a0, a0, 32
 ; RV64IBS-NEXT:    ret
   %or = or i64 %a, 4294967297
   ret i64 %or
 }
 
 define i64 @or_i64_4099(i64 %a) nounwind {
 ; RV64I-LABEL: or_i64_4099:
 ; RV64I:       # %bb.0: