[RISCV] Override TargetLowering::BuildSDIVPow2 to generate SELECT

[• pcwang-thead]

Summary

When Zbt is enabled, we can generate SELECT for division by power
of 2, so that there is no data dependency.

[craig.topper]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

10095

Capitalize 'only'

10105

Is i64 correct here for RV32? I don't see a test case.

10106

Use APInt::isNegatedPowerOf2

llvm/test/CodeGen/RISCV/rv32zbt-div-pow2.ll

1

Can you add test cases for dividing by 2 and -2 as well? X86 does not use BuildSDIVPow2 for those cases so we should check those.

[luismarques]

This should probably be disabled for minsize.

[jrtc27]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

10096

Should say *why*, ie need conditional move

10100

X86 prioritises isIntDivCheap over a lack of conditional move; what's the justification for doing it the other way round?

10106

X86 asserts it's one of the two, so this check seems bogus given the function name...

llvm/test/CodeGen/RISCV/rv32zbt-div-pow2.ll

7

No positive power of 2 tests, and no tests for isIntDivCheap being true?

llvm/test/CodeGen/RISCV/rv64zbt-div-pow2.ll

8

Don't duplicate tests, just add rv64 check lines to your existing rv32-only test

31

And we should test we don't do stupid things for i64 on RV32

[craig.topper]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

10100

I agree with @jrtc27. The isIntDivCheap check should be at the top.

10106

I think AArch64 explicitly checks it. I wrote X86 later and used an assert.

llvm/test/CodeGen/RISCV/rv32zbt-div-pow2.ll

7

isIntDivCheap is never true for RISCV today.

We should also add a test for dividing by 4096 or larger for RV32 and RV64. And probably something larger than 2^32 for RV64. The constant materialization will add additional instructions not seen in the 1024 case.

[craig.topper]

In D114856#3179772, @luismarques wrote:

This should probably be disabled for minsize.

That's what several targets use isIntDivCheap for. I don't think RISCV does. The patch here doesn't make that situation worse.

[• pcwang-thead]

• Address comments.
• Only apply to divisors whose absolute value is less than 2^12.

[jrtc27]

Some of the i32 ones look like they might not be profitable on RV64 unless you have a wide out-of-order processor; 50% more instructions in some cases

[• pcwang-thead]

In D114856#3188850, @jrtc27 wrote:

Some of the i32 ones look like they might not be profitable on RV64 unless you have a wide out-of-order processor; 50% more instructions in some cases

For i32 on RV64, sign extension is needed, so there are sext.w. And the only case with 50% more instructions is when divisor is 2.
Maybe we should skip these divisors, any ideas?

llvm/test/CodeGen/RISCV/rv32zbt-div-pow2.ll

7

isIntDivCheap is never true for RISCV today.

We should also add a test for dividing by 4096 or larger for RV32 and RV64. And probably something larger than 2^32 for RV64. The constant materialization will add additional instructions not seen in the 1024 case.

7

Thanks.

I added tests divided by n (|n| ≥ 2^12) and two materialization instructions were generated. So it may be non-profitable when absolute values of divisors are larger than 2^12.

[craig.topper]

llvm/test/CodeGen/RISCV/div-pow2.ll

14 ↗

(On Diff #393864)

I think it makes sense to keep the old codegen when dividing by 2.

58 ↗

(On Diff #393864)

Original code is less instructions and has the same critical path instruction count.

355 ↗

(On Diff #393864)

Original code looks better.

406 ↗

(On Diff #393864)

Original code looks better

[• pcwang-thead]

• Address comments.

[• pcwang-thead]

ping

[jrtc27]

From the LLVM Code-Review Policy and Practices (https://llvm.org/docs/CodeReview.html):

If it is urgent, provide reasons why it is important to you to get this patch landed and ping it every couple of days. If it is not urgent, the common courtesy ping rate is one week. Remember that you’re asking for valuable time from other professional developers.

It's only been 3 days for this and other patches you've just pinged

[• pcwang-thead]

In D114856#3196325, @jrtc27 wrote:

From the LLVM Code-Review Policy and Practices (https://llvm.org/docs/CodeReview.html):

If it is urgent, provide reasons why it is important to you to get this patch landed and ping it every couple of days. If it is not urgent, the common courtesy ping rate is one week. Remember that you’re asking for valuable time from other professional developers.

It's only been 3 days for this and other patches you've just pinged

Sorry, my bad. It's not so urgent.

[craig.topper]

LGTM

llvm/lib/Target/RISCV/RISCVISelLowering.h

public:
   MVT getContainerForFixedLengthVector(MVT VT) const;
 
   bool shouldRemoveExtendFromGSIndex(EVT VT) const override;
 
   bool isLegalElementTypeForRVV(Type *ScalarTy) const;
 
   bool shouldConvertFpToSat(unsigned Op, EVT FPVT, EVT VT) const override;
 
+  SDValue BuildSDIVPow2(SDNode *N, const APInt &Divisor, SelectionDAG &DAG,
+                        SmallVectorImpl<SDNode *> &Created) const override;
+
 private:
   /// RISCVCCAssignFn - This target-specific function extends the default
   /// CCValAssign with additional information used to lower RISC-V calling
   /// conventions.
   typedef bool RISCVCCAssignFn(const DataLayout &DL, RISCVABI::ABI,
                                unsigned ValNo, MVT ValVT, MVT LocVT,
                                CCValAssign::LocInfo LocInfo,
                                ISD::ArgFlagsTy ArgFlags, CCState &State,

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

if (PartVTBitSize % ValueVTBitSize == 0) {
       if (ValueEltVT != PartEltVT)
         Val = DAG.getNode(ISD::BITCAST, DL, ValueVT, Val);
       return Val;
     }
   }
   return SDValue();
 }
 
+SDValue
+RISCVTargetLowering::BuildSDIVPow2(SDNode *N, const APInt &Divisor,
+                                   SelectionDAG &DAG,
+                                   SmallVectorImpl<SDNode *> &Created) const {
+  // only for Zbt.
+  if (!Subtarget.hasStdExtZbt())
+    return SDValue();
+
+  AttributeList Attr = DAG.getMachineFunction().getFunction().getAttributes();
+  if (isIntDivCheap(N->getValueType(0), Attr))
+    return SDValue(N, 0); // Lower SDIV as SDIV
+
+  // fold (sdiv X, pow2)
+  EVT VT = N->getValueType(0);
+  if ((VT != MVT::i32 && VT != MVT::i64) ||
+      !(Divisor.isPowerOf2() || (-Divisor).isPowerOf2()))
+    return SDValue();
+
+  SDLoc DL(N);
+  SDValue N0 = N->getOperand(0);
+  unsigned Lg2 = Divisor.countTrailingZeros();
+  SDValue Zero = DAG.getConstant(0, DL, VT);
+  SDValue Pow2MinusOne = DAG.getConstant((1ULL << Lg2) - 1, DL, VT);
+
+  // Add (N0 < 0) ? Pow2 - 1 : 0;
+  SDValue Cmp = DAG.getSetCC(DL, VT, N0, Zero, ISD::SETLT);
+  SDValue Add = DAG.getNode(ISD::ADD, DL, VT, N0, Pow2MinusOne);
+  SDValue Sel = DAG.getNode(ISD::SELECT, DL, VT, Cmp, Add, N0);
+
+  Created.push_back(Cmp.getNode());
+  Created.push_back(Add.getNode());
+  Created.push_back(Sel.getNode());
+
+  // Divide by pow2.
+  SDValue SRA =
+      DAG.getNode(ISD::SRA, DL, VT, Sel, DAG.getConstant(Lg2, DL, VT));
+
+  // If we're dividing by a positive value, we're done.  Otherwise, we must
+  // negate the result.
+  if (Divisor.isNonNegative())
+    return SRA;
+
+  Created.push_back(SRA.getNode());
+  return DAG.getNode(ISD::SUB, DL, VT, DAG.getConstant(0, DL, VT), SRA);
+}
+
 #define GET_REGISTER_MATCHER
 #include "RISCVGenAsmMatcher.inc"
 
 Register
 RISCVTargetLowering::getRegisterByName(const char *RegName, LLT VT,
                                        const MachineFunction &MF) const {
   Register Reg = MatchRegisterAltName(RegName);
   if (Reg == RISCV::NoRegister)

llvm/test/CodeGen/RISCV/rv32zbt-div-pow2.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=riscv32 -verify-machineinstrs < %s \
+; RUN:   | FileCheck %s -check-prefix=RV32I
+; RUN: llc -mtriple=riscv32 -mattr=+experimental-zbt -verify-machineinstrs < %s \
+; RUN:   | FileCheck %s -check-prefix=RV32ZBT
+
+define i32 @sdiv_pow2(i32 %a) {
+; RV32I-LABEL: sdiv_pow2:
+; RV32I:       # %bb.0: # %entry
+; RV32I-NEXT:    srai a1, a0, 31
+; RV32I-NEXT:    srli a1, a1, 22
+; RV32I-NEXT:    add a0, a0, a1
+; RV32I-NEXT:    srai a0, a0, 10
+; RV32I-NEXT:    neg a0, a0
+; RV32I-NEXT:    ret
+;
+; RV32ZBT-LABEL: sdiv_pow2:
+; RV32ZBT:       # %bb.0: # %entry
+; RV32ZBT-NEXT:    slti a1, a0, 0
+; RV32ZBT-NEXT:    addi a2, a0, 1023
+; RV32ZBT-NEXT:    cmov a0, a1, a2, a0
+; RV32ZBT-NEXT:    srai a0, a0, 10
+; RV32ZBT-NEXT:    neg a0, a0
+; RV32ZBT-NEXT:    ret
+entry:
+  %div = sdiv i32 %a, -1024
+  ret i32 %div
+}

llvm/test/CodeGen/RISCV/rv64zbt-div-pow2.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=riscv64 -verify-machineinstrs < %s \
+; RUN:   | FileCheck %s -check-prefix=RV64I
+; RUN: llc -mtriple=riscv64 -mattr=+experimental-zbt -verify-machineinstrs < %s \
+; RUN:   | FileCheck %s -check-prefix=RV64ZBT
+
+define i32 @sdiv_pow2_32(i32 %a) {
+; RV64I-LABEL: sdiv_pow2_32:
+; RV64I:       # %bb.0: # %entry
+; RV64I-NEXT:    sraiw a1, a0, 31
+; RV64I-NEXT:    srliw a1, a1, 22
+; RV64I-NEXT:    addw a0, a0, a1
+; RV64I-NEXT:    sraiw a0, a0, 10
+; RV64I-NEXT:    neg a0, a0
+; RV64I-NEXT:    ret
+;
+; RV64ZBT-LABEL: sdiv_pow2_32:
+; RV64ZBT:       # %bb.0: # %entry
+; RV64ZBT-NEXT:    sext.w a1, a0
+; RV64ZBT-NEXT:    addi a2, a0, 1023
+; RV64ZBT-NEXT:    slti a1, a1, 0
+; RV64ZBT-NEXT:    cmov a0, a1, a2, a0
+; RV64ZBT-NEXT:    sraiw a0, a0, 10
+; RV64ZBT-NEXT:    neg a0, a0
+; RV64ZBT-NEXT:    ret
+entry:
+  %div = sdiv i32 %a, -1024
+  ret i32 %div
+}
+
+define i64 @sdiv_pow2_64(i64 %a) {
+; RV64I-LABEL: sdiv_pow2_64:
+; RV64I:       # %bb.0: # %entry
+; RV64I-NEXT:    srai a1, a0, 63
+; RV64I-NEXT:    srli a1, a1, 54
+; RV64I-NEXT:    add a0, a0, a1
+; RV64I-NEXT:    srai a0, a0, 10
+; RV64I-NEXT:    neg a0, a0
+; RV64I-NEXT:    ret
+;
+; RV64ZBT-LABEL: sdiv_pow2_64:
+; RV64ZBT:       # %bb.0: # %entry
+; RV64ZBT-NEXT:    slti a1, a0, 0
+; RV64ZBT-NEXT:    addi a2, a0, 1023
+; RV64ZBT-NEXT:    cmov a0, a1, a2, a0
+; RV64ZBT-NEXT:    srai a0, a0, 10
+; RV64ZBT-NEXT:    neg a0, a0
+; RV64ZBT-NEXT:    ret
+entry:
+  %div = sdiv i64 %a, -1024
+  ret i64 %div
+}