[GlobalISel][LegalizeTypes] Expand UDIV/UREM by constant via chunk summation#189231
Open
xgupta wants to merge 1 commit into
Open
[GlobalISel][LegalizeTypes] Expand UDIV/UREM by constant via chunk summation#189231xgupta wants to merge 1 commit into
xgupta wants to merge 1 commit into
Conversation
…mmation This patch improves the lowering of 128-bit unsigned division and remainder by constants (UDIV/UREM) by avoiding buildUDivOrURemUsingMul or a fallback to libcall (__udivti3/uremti3) for specific divisors. When a divisor D satisfies the condition (1 << ChunkWidth) % D == 1, the 128-bit value is split into fixed-width chunks (e.g., 30-bit) and summed before applying a smaller UDIV/UREM. This transformation is based on the "remainder by summing digits" trick described in Hacker’s Delight. This is a porring of SelectionDAG TargetLowering::expandDIVREMByConstant.
Member
|
@llvm/pr-subscribers-llvm-globalisel @llvm/pr-subscribers-backend-aarch64 Author: Shivam Gupta (xgupta) ChangesThis patch improves the lowering of 128-bit unsigned division and remainder by constants (UDIV/UREM) by avoiding buildUDivOrURemUsingMul or a fallback to libcall (__udivti3/uremti3) for specific divisors. When a divisor D satisfies the condition (1 << ChunkWidth) % D == 1, the 128-bit value is split into fixed-width chunks (e.g., 30-bit) and summed before applying a smaller UDIV/UREM. This transformation is based on the "remainder by summing digits" trick described in Hacker’s Delight. This is a porting of SelectionDAG's TargetLowering::expandDIVREMByConstant. Patch is 40.66 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/189231.diff 3 Files Affected:
diff --git a/llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h b/llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h
index 365bbaacfe055..d51b9f70950b3 100644
--- a/llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h
+++ b/llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h
@@ -721,6 +721,13 @@ class CombinerHelper {
/// feeding a G_AND instruction \p MI.
bool matchNarrowBinopFeedingAnd(MachineInstr &MI, BuildFnTy &MatchInfo) const;
+ /// Given an G_UDIV \p MI or G_UREM \p MI expressing a divide by constant,
+ /// return an expression that implements chunk summation where constant Div
+ /// satisfies the condition (2^W % D)) == 1. Ref: "Hacker's Delight" or "The
+ /// PowerPC Compiler Writer's Guide", 10-19 Remainder by Summing Digite,
+ /// FIGURE 10–28, Unsigned remainder modulo 7.
+ MachineInstr *buildUDivOrRemUsingChunkSummation(MachineInstr &MI) const;
+
/// Given an G_UDIV \p MI or G_UREM \p MI expressing a divide by constant,
/// return an expression that implements it by multiplying by a magic number.
/// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide".
diff --git a/llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp b/llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
index 4d92754ae9b48..12e82d4ae2d3d 100644
--- a/llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
+++ b/llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
@@ -5575,6 +5575,229 @@ bool CombinerHelper::matchSubAddSameReg(MachineInstr &MI,
return false;
}
+static unsigned getSumOfDigitsChunkWidth(const APInt &Divisor,
+ unsigned BitWidth) {
+ if (Divisor.isZero())
+ return 0;
+
+ unsigned HBitWidth = BitWidth / 2;
+
+ // Search for a ChunkWidth (I) where (2^I) % D == 1.
+ // This allows us to use the "Sum of Digits" property in base 2^I.
+ for (unsigned I = HBitWidth, E = HBitWidth / 2; I > E; --I) {
+ APInt Mod = APInt::getOneBitSet(BitWidth, I).urem(Divisor);
+
+ if (Mod.isOne()) {
+ unsigned NumChunks = divideCeil(BitWidth, I);
+
+ // Safety check: Ensure the sum of chunks won't overflow the
+ // width of the registers we are using for the summation (HBitWidth).
+ if (I == HBitWidth || I + llvm::bit_width(NumChunks - 1) <= HBitWidth)
+ return I;
+ }
+ }
+
+ return 0;
+}
+
+// Optimize unsigned division or remainder by constants for types twice as large
+// as a legal VT.
+//
+// If (1 << (BitWidth / 2)) % Constant == 1, then the remainder
+// can be computed
+// as:
+// Sum = __builtin_uadd_overflow(Lo, High, &Sum);
+// Remainder = Sum % Constant;
+//
+// If (1 << (BitWidth / 2)) % Constant != 1, we can search for a smaller value
+// W such that W != (BitWidth / 2) and (1 << W) % Constant == 1. We can break
+// High:Low into 3 chunks of W bits and compute remainder as
+// Sum = Chunk0 + Chunk1 + Chunk2;
+// Remainder = Sum % Constant;
+//
+// This is based on "Remainder by Summing Digits" from Hacker's Delight.
+//
+// For division, we can compute the remainder using the algorithm described
+// above, subtract it from the dividend to get an exact multiple of Constant.
+// Then multiply that exact multiply by the multiplicative inverse modulo
+// (1 << (BitWidth / 2)) to get the quotient.
+
+// If Constant is even, we can shift right the dividend and the divisor by the
+// number of trailing zeros in Constant before applying the remainder algorithm.
+// If we're after the quotient, we can subtract this value from the shifted
+// dividend and multiply by the multiplicative inverse of the shifted divisor.
+// If we want the remainder, we shift the value left by the number of trailing
+// zeros and add the bits that were shifted out of the dividend.
+MachineInstr *
+CombinerHelper::buildUDivOrRemUsingChunkSummation(MachineInstr &MI) const {
+ // Only handle unsigned operations.
+ unsigned Opcode = MI.getOpcode();
+ if (Opcode == TargetOpcode::G_SREM || Opcode == TargetOpcode::G_SDIV)
+ return nullptr;
+ assert((Opcode == TargetOpcode::G_UREM || Opcode == TargetOpcode::G_UDIV) &&
+ "Unexpected opcode");
+
+ Register DivReg = MI.getOperand(2).getReg();
+ auto VRegAndVal = getIConstantVRegValWithLookThrough(DivReg, MRI);
+ if (!VRegAndVal)
+ return nullptr;
+
+ // Don't expand if optimizing for size.
+ const auto &MF = *MI.getMF();
+ if (MF.getFunction().hasMinSize() || MF.getFunction().hasOptSize())
+ return nullptr;
+
+ // Only apply to wide types (e.g., i128).
+ Register DstReg = MI.getOperand(0).getReg();
+ LLT Ty = MRI.getType(DstReg);
+ unsigned BitWidth = Ty.getSizeInBits();
+ if (BitWidth < 128)
+ return nullptr;
+
+ // Early out for 0 or 1 divisors.
+ APInt Divisor = VRegAndVal->Value;
+ if (Divisor.ule(1))
+ return nullptr;
+
+ // Divisor must be less than (1 << (BitWidth / 2)).
+ unsigned HBitWidth = BitWidth / 2;
+ if (Divisor.uge(APInt::getOneBitSet(BitWidth, HBitWidth)))
+ return nullptr;
+
+ LLT HiLoTy = LLT::scalar(HBitWidth);
+ assert(Ty.getScalarSizeInBits() == BitWidth &&
+ HiLoTy.getScalarSizeInBits() == HBitWidth && "Unexpected VTs");
+
+ // If the divisor is even, shift it until it becomes odd.
+ unsigned TZ = Divisor.countr_zero();
+ if (TZ > 0) {
+ Divisor.lshrInPlace(TZ);
+ }
+
+ // Find the best chunk width W where (2^W % D) == 1.
+ unsigned BestW = getSumOfDigitsChunkWidth(Divisor, BitWidth);
+ if (!BestW)
+ return nullptr;
+
+ Builder.setInstrAndDebugLoc(MI);
+
+ // Split input into LL and LH
+ Register SrcReg = MI.getOperand(1).getReg();
+ auto Unmerge = Builder.buildUnmerge(HiLoTy, SrcReg);
+ Register LL = Unmerge.getReg(0);
+ Register LH = Unmerge.getReg(1);
+
+ bool HasFSHR =
+ isLegalOrBeforeLegalizer({TargetOpcode::G_FSHR, {HiLoTy, HiLoTy}});
+
+ auto GetFSHR = [&](Register Lo, Register Hi, unsigned ShiftAmt) {
+ assert(ShiftAmt > 0 && ShiftAmt < HBitWidth);
+
+ if (HasFSHR) {
+ auto Amt = Builder.buildConstant(HiLoTy, ShiftAmt);
+ return Builder.buildInstr(TargetOpcode::G_FSHR, {HiLoTy}, {Hi, Lo, Amt})
+ .getReg(0);
+ }
+
+ // Fallback: (Lo >> ShiftAmt) | (Hi << (HBitWidth - ShiftAmt))
+ auto ShAmt = Builder.buildConstant(HiLoTy, ShiftAmt);
+ auto InvShAmt = Builder.buildConstant(HiLoTy, HBitWidth - ShiftAmt);
+
+ auto Part1 = Builder.buildLShr(HiLoTy, Lo, ShAmt);
+ auto Part2 = Builder.buildShl(HiLoTy, Hi, InvShAmt);
+
+ return Builder.buildOr(HiLoTy, Part1, Part2).getReg(0);
+ };
+
+ Register PartialRem = Builder.buildConstant(HiLoTy, 0).getReg(0);
+ if (TZ > 0) {
+ if (Opcode != TargetOpcode::G_UDIV) {
+ auto Mask =
+ Builder.buildConstant(HiLoTy, APInt::getLowBitsSet(HBitWidth, TZ));
+ PartialRem = Builder.buildAnd(HiLoTy, LL, Mask).getReg(0);
+ }
+ auto ShiftAmt = Builder.buildConstant(HiLoTy, TZ);
+ Register NewLL =
+ Builder.buildInstr(TargetOpcode::G_FSHR, {HiLoTy}, {LH, LL, ShiftAmt})
+ .getReg(0);
+ Register NewLH = Builder.buildLShr(HiLoTy, LH, ShiftAmt).getReg(0);
+ LL = NewLL;
+ LH = NewLH;
+ }
+
+ Register Sum = Register();
+ if (BestW == HBitWidth) {
+ // Specialized path: (1 << 64) % D == 1. Sum = LL + LH + Carry
+ auto Add = Builder.buildUAddo(HiLoTy, LLT::scalar(1), LL, LH);
+ auto Zero = Builder.buildConstant(HiLoTy, 0);
+ Sum = Builder
+ .buildUAdde(HiLoTy, LLT::scalar(1), Add.getReg(0), Zero,
+ Add.getReg(1))
+ .getReg(0);
+ } else {
+ // General path for smaller chunk widths
+ Sum = Builder.buildConstant(HiLoTy, 0).getReg(0);
+ auto Mask =
+ Builder.buildConstant(HiLoTy, APInt::getLowBitsSet(HBitWidth, BestW));
+
+ for (unsigned I = 0; I < BitWidth - TZ; I += BestW) {
+ Register Chunk;
+ if (I == 0) {
+ Chunk = LL;
+ } else if (I >= HBitWidth) {
+ auto ShiftAmt = Builder.buildConstant(HiLoTy, I - HBitWidth);
+ Chunk = Builder.buildLShr(HiLoTy, LH, ShiftAmt).getReg(0);
+ } else {
+ Chunk = GetFSHR(LL, LH, I);
+ }
+ auto Masked = Builder.buildAnd(HiLoTy, Chunk, Mask);
+ Sum = Builder.buildAdd(HiLoTy, Sum, Masked).getReg(0);
+ }
+ }
+
+ // RemL = Sum % Divisor
+ auto RemL =
+ Builder
+ .buildURem(HiLoTy, Sum,
+ Builder.buildConstant(HiLoTy, Divisor.trunc(HBitWidth)))
+ .getReg(0);
+
+ MachineInstr *Res = nullptr;
+
+ if (Opcode != TargetOpcode::G_UREM) {
+ // Quotient Calculation
+ Register ZExtLL = Builder.buildZExt(Ty, LL).getReg(0);
+ Register ZExtLH = Builder.buildZExt(Ty, LH).getReg(0);
+
+ Register ShiftedLH =
+ Builder
+ .buildShl(Ty, ZExtLH,
+ Builder.buildConstant(Ty, HBitWidth).getReg(0))
+ .getReg(0);
+
+ Register Dividend = Builder.buildOr(Ty, ZExtLL, ShiftedLH).getReg(0);
+ Register ZExtRemL = Builder.buildZExt(Ty, RemL).getReg(0);
+ Register Sub = Builder.buildSub(Ty, Dividend, ZExtRemL).getReg(0);
+
+ APInt InvVal = Divisor.multiplicativeInverse();
+ Register Inv = Builder.buildConstant(Ty, InvVal).getReg(0);
+ Res = Builder.buildMul(Ty, Sub, Inv);
+ }
+
+ if (Opcode != TargetOpcode::G_UDIV) {
+ // Remainder Calculation
+ if (TZ > 0) {
+ auto Shl =
+ Builder.buildShl(HiLoTy, RemL, Builder.buildConstant(HiLoTy, TZ));
+ RemL = Builder.buildOr(HiLoTy, Shl, PartialRem).getReg(0);
+ }
+
+ Res = Builder.buildZExt(Ty, RemL);
+ }
+
+ return Res;
+}
+
MachineInstr *CombinerHelper::buildUDivOrURemUsingMul(MachineInstr &MI) const {
unsigned Opcode = MI.getOpcode();
assert(Opcode == TargetOpcode::G_UDIV || Opcode == TargetOpcode::G_UREM);
@@ -5794,7 +6017,12 @@ bool CombinerHelper::matchUDivOrURemByConst(MachineInstr &MI) const {
}
void CombinerHelper::applyUDivOrURemByConst(MachineInstr &MI) const {
- auto *NewMI = buildUDivOrURemUsingMul(MI);
+ // Try to build UDIV/UREM by Hacker's Delight's Remainder by Summing Digits.
+ auto *NewMI = buildUDivOrRemUsingChunkSummation(MI);
+
+ // If chunk summation didn't apply, try the multiplier fallback.
+ if (!NewMI)
+ NewMI = buildUDivOrURemUsingMul(MI);
replaceSingleDefInstWithReg(MI, NewMI->getOperand(0).getReg());
}
diff --git a/llvm/test/CodeGen/AArch64/rem-by-const.ll b/llvm/test/CodeGen/AArch64/rem-by-const.ll
index 1c6b241cb8f12..8f285a3ab17df 100644
--- a/llvm/test/CodeGen/AArch64/rem-by-const.ll
+++ b/llvm/test/CodeGen/AArch64/rem-by-const.ll
@@ -518,65 +518,21 @@ define i128 @ui128_7(i128 %a, i128 %b) {
;
; CHECK-GI-LABEL: ui128_7:
; CHECK-GI: // %bb.0: // %entry
-; CHECK-GI-NEXT: mov x8, #18725 // =0x4925
-; CHECK-GI-NEXT: mov x10, #9362 // =0x2492
-; CHECK-GI-NEXT: movk x8, #9362, lsl #16
-; CHECK-GI-NEXT: movk x10, #37449, lsl #16
-; CHECK-GI-NEXT: movk x8, #37449, lsl #32
-; CHECK-GI-NEXT: movk x10, #18724, lsl #32
-; CHECK-GI-NEXT: movk x8, #18724, lsl #48
-; CHECK-GI-NEXT: movk x10, #9362, lsl #48
-; CHECK-GI-NEXT: mul x9, x1, x8
-; CHECK-GI-NEXT: mul x11, x0, x10
-; CHECK-GI-NEXT: umulh x12, x0, x8
-; CHECK-GI-NEXT: mul x13, x1, x10
-; CHECK-GI-NEXT: adds x9, x9, x11
-; CHECK-GI-NEXT: umulh x14, x1, x8
-; CHECK-GI-NEXT: cset w11, hs
-; CHECK-GI-NEXT: cmn x9, x12
-; CHECK-GI-NEXT: and x11, x11, #0x1
-; CHECK-GI-NEXT: and x12, xzr, #0x1
-; CHECK-GI-NEXT: umulh x15, x0, x10
-; CHECK-GI-NEXT: cset w9, hs
-; CHECK-GI-NEXT: and x9, x9, #0x1
-; CHECK-GI-NEXT: umulh x8, xzr, x8
-; CHECK-GI-NEXT: add x9, x11, x9
-; CHECK-GI-NEXT: and x11, xzr, #0x1
-; CHECK-GI-NEXT: adds x13, x13, x14
-; CHECK-GI-NEXT: add x11, x11, x12
-; CHECK-GI-NEXT: umulh x10, x1, x10
-; CHECK-GI-NEXT: cset w12, hs
-; CHECK-GI-NEXT: adds x13, x13, x15
-; CHECK-GI-NEXT: and x12, x12, #0x1
-; CHECK-GI-NEXT: umulh x14, x0, xzr
-; CHECK-GI-NEXT: cset w15, hs
-; CHECK-GI-NEXT: adds x9, x13, x9
-; CHECK-GI-NEXT: add x11, x11, x12
-; CHECK-GI-NEXT: and x12, x15, #0x1
-; CHECK-GI-NEXT: cset w13, hs
-; CHECK-GI-NEXT: add x11, x11, x12
-; CHECK-GI-NEXT: and x12, x13, #0x1
-; CHECK-GI-NEXT: add x8, x8, x10
-; CHECK-GI-NEXT: add x10, x11, x12
-; CHECK-GI-NEXT: add x8, x8, x14
-; CHECK-GI-NEXT: add x8, x8, x10
-; CHECK-GI-NEXT: subs x10, x0, x9
-; CHECK-GI-NEXT: sbc x11, x1, x8
-; CHECK-GI-NEXT: extr x10, x11, x10, #1
-; CHECK-GI-NEXT: lsr x11, x11, #1
-; CHECK-GI-NEXT: adds x9, x10, x9
-; CHECK-GI-NEXT: mov w10, #7 // =0x7
-; CHECK-GI-NEXT: adc x8, x11, x8
-; CHECK-GI-NEXT: extr x9, x8, x9, #2
-; CHECK-GI-NEXT: lsr x8, x8, #2
-; CHECK-GI-NEXT: umulh x10, x9, x10
-; CHECK-GI-NEXT: lsl x11, x9, #3
-; CHECK-GI-NEXT: lsl x12, x8, #3
-; CHECK-GI-NEXT: sub x9, x11, x9
-; CHECK-GI-NEXT: sub x8, x12, x8
-; CHECK-GI-NEXT: subs x0, x0, x9
-; CHECK-GI-NEXT: add x8, x8, x10
-; CHECK-GI-NEXT: sbc x1, x1, x8
+; CHECK-GI-NEXT: extr x8, x1, x0, #60
+; CHECK-GI-NEXT: and x9, x0, #0xfffffffffffffff
+; CHECK-GI-NEXT: and x8, x8, #0xfffffffffffffff
+; CHECK-GI-NEXT: add x8, x9, x8
+; CHECK-GI-NEXT: mov x9, #18725 // =0x4925
+; CHECK-GI-NEXT: movk x9, #9362, lsl #16
+; CHECK-GI-NEXT: add x8, x8, x1, lsr #56
+; CHECK-GI-NEXT: mov x1, xzr
+; CHECK-GI-NEXT: movk x9, #37449, lsl #32
+; CHECK-GI-NEXT: movk x9, #18724, lsl #48
+; CHECK-GI-NEXT: umulh x9, x8, x9
+; CHECK-GI-NEXT: lsr x9, x9, #1
+; CHECK-GI-NEXT: lsl x10, x9, #3
+; CHECK-GI-NEXT: sub x9, x10, x9
+; CHECK-GI-NEXT: sub x0, x8, x9
; CHECK-GI-NEXT: ret
entry:
%s = urem i128 %a, 7
@@ -605,14 +561,370 @@ define i128 @ui128_100(i128 %a, i128 %b) {
;
; CHECK-GI-LABEL: ui128_100:
; CHECK-GI: // %bb.0: // %entry
-; CHECK-GI-NEXT: mov x8, #23593 // =0x5c29
+; CHECK-GI-NEXT: extr x8, x1, x0, #2
+; CHECK-GI-NEXT: lsr x9, x1, #2
+; CHECK-GI-NEXT: mov w10, #25 // =0x19
+; CHECK-GI-NEXT: extr x9, x9, x8, #60
+; CHECK-GI-NEXT: and x8, x8, #0xfffffffffffffff
+; CHECK-GI-NEXT: and x9, x9, #0xfffffffffffffff
+; CHECK-GI-NEXT: add x8, x8, x9
+; CHECK-GI-NEXT: mov x9, #62915 // =0xf5c3
+; CHECK-GI-NEXT: movk x9, #23592, lsl #16
+; CHECK-GI-NEXT: add x8, x8, x1, lsr #58
+; CHECK-GI-NEXT: mov x1, xzr
+; CHECK-GI-NEXT: movk x9, #49807, lsl #32
+; CHECK-GI-NEXT: movk x9, #10485, lsl #48
+; CHECK-GI-NEXT: umulh x9, x8, x9
+; CHECK-GI-NEXT: lsr x9, x9, #2
+; CHECK-GI-NEXT: msub x8, x9, x10, x8
+; CHECK-GI-NEXT: bfi x0, x8, #2, #62
+; CHECK-GI-NEXT: ret
+entry:
+ %s = urem i128 %a, 100
+ ret i128 %s
+}
+
+define i128 @ui128_35(i128 %a, i128 %b) {
+; CHECK-LABEL: ui128_35:
+; CHECK: // %bb.0: // %entry
+; CHECK-NEXT: extr x8, x1, x0, #60
+; CHECK-NEXT: and x9, x0, #0xfffffffffffffff
+; CHECK-NEXT: mov w10, #35 // =0x23
+; CHECK-NEXT: and x8, x8, #0xfffffffffffffff
+; CHECK-NEXT: add x8, x9, x8
+; CHECK-NEXT: mov x9, #3745 // =0xea1
+; CHECK-NEXT: movk x9, #41194, lsl #16
+; CHECK-NEXT: add x8, x8, x1, lsr #56
+; CHECK-NEXT: mov x1, xzr
+; CHECK-NEXT: movk x9, #59918, lsl #32
+; CHECK-NEXT: movk x9, #3744, lsl #48
+; CHECK-NEXT: umulh x9, x8, x9
+; CHECK-NEXT: lsr x9, x9, #1
+; CHECK-NEXT: msub x0, x9, x10, x8
+; CHECK-NEXT: ret
+entry:
+ %s = urem i128 %a, 35
+ ret i128 %s
+}
+
+define i128 @ui128_14(i128 %a, i128 %b) {
+; CHECK-SD-LABEL: ui128_14:
+; CHECK-SD: // %bb.0: // %entry
+; CHECK-SD-NEXT: extr x8, x1, x0, #61
+; CHECK-SD-NEXT: ubfx x9, x0, #1, #60
+; CHECK-SD-NEXT: and x8, x8, #0xfffffffffffffff
+; CHECK-SD-NEXT: add x8, x9, x8
+; CHECK-SD-NEXT: mov x9, #18725 // =0x4925
+; CHECK-SD-NEXT: movk x9, #9362, lsl #16
+; CHECK-SD-NEXT: add x8, x8, x1, lsr #57
+; CHECK-SD-NEXT: mov x1, xzr
+; CHECK-SD-NEXT: movk x9, #37449, lsl #32
+; CHECK-SD-NEXT: movk x9, #18724, lsl #48
+; CHECK-SD-NEXT: umulh x9, x8, x9
+; CHECK-SD-NEXT: lsr x9, x9, #1
+; CHECK-SD-NEXT: sub x9, x9, x9, lsl #3
+; CHECK-SD-NEXT: add x8, x8, x9
+; CHECK-SD-NEXT: bfi x0, x8, #1, #63
+; CHECK-SD-NEXT: ret
+;
+; CHECK-GI-LABEL: ui128_14:
+; CHECK-GI: // %bb.0: // %entry
+; CHECK-GI-NEXT: extr x8, x1, x0, #1
+; CHECK-GI-NEXT: lsr x9, x1, #1
+; CHECK-GI-NEXT: extr x9, x9, x8, #60
+; CHECK-GI-NEXT: and x8, x8, #0xfffffffffffffff
+; CHECK-GI-NEXT: and x9, x9, #0xfffffffffffffff
+; CHECK-GI-NEXT: add x8, x8, x9
+; CHECK-GI-NEXT: mov x9, #18725 // =0x4925
+; CHECK-GI-NEXT: movk x9, #9362, lsl #16
+; CHECK-GI-NEXT: add x8, x8, x1, lsr #57
+; CHECK-GI-NEXT: mov x1, xzr
+; CHECK-GI-NEXT: movk x9, #37449, lsl #32
+; CHECK-GI-NEXT: movk x9, #18724, lsl #48
+; CHECK-GI-NEXT: umulh x9, x8, x9
+; CHECK-GI-NEXT: lsr x9, x9, #1
+; CHECK-GI-NEXT: lsl x10, x9, #3
+; CHECK-GI-NEXT: sub x9, x10, x9
+; CHECK-GI-NEXT: sub x8, x8, x9
+; CHECK-GI-NEXT: bfi x0, x8, #1, #63
+; CHECK-GI-NEXT: ret
+entry:
+ %s = urem i128 %a, 14
+ ret i128 %s
+}
+
+define i128 @ui128_56(i128 %a, i128 %b) {
+; CHECK-SD-LABEL: ui128_56:
+; CHECK-SD: // %bb.0: // %entry
+; CHECK-SD-NEXT: extr x8, x1, x0, #63
+; CHECK-SD-NEXT: ubfx x9, x0, #3, #60
+; CHECK-SD-NEXT: and x8, x8, #0xfffffffffffffff
+; CHECK-SD-NEXT: add x8, x9, x8
+; CHECK-SD-NEXT: mov x9, #18725 // =0x4925
+; CHECK-SD-NEXT: movk x9, #9362, lsl #16
+; CHECK-SD-NEXT: add x8, x8, x1, lsr #59
+; CHECK-SD-NEXT: mov x1, xzr
+; CHECK-SD-NEXT: movk x9, #37449, lsl #32
+; CHECK-SD-NEXT: movk x9, #18724, lsl #48
+; CHECK-SD-NEXT: umulh x9, x8, x9
+; CHECK-SD-NEXT: lsr x9, x9, #1
+; CHECK-SD-NEXT: sub x9, x9, x9, lsl #3
+; CHECK-SD-NEXT: add x8, x8, x9
+; CHECK-SD-NEXT: bfi x0, x8, #3, #61
+; CHECK-SD-NEXT: ret
+;
+; CHECK-GI-LABEL: ui128_56:
+; CHECK-GI: // %bb.0: // %entry
+; CHECK-GI-NEXT: extr x8, x1, x0, #3
+; CHECK-GI-NEXT: lsr x9, x1, #3
+; CHECK-GI-NEXT: extr x9, x9, x8, #60
+; CHECK-GI-NEXT: and x8, x8, #0xfffffffffffffff
+; CHECK-GI-NEXT: and x9, x9, #0xfffffffffffffff
+; CHECK-GI-NEXT: add x8, x8, x9
+; CHECK-GI-NEXT: mov x9, #18725 // =0x4925
+; CHECK-GI-NEXT: movk x9, #9362, lsl #16
+; CHECK-GI-NEXT: add x8, x8, x1, lsr #59
+; CHECK-GI-NEXT: mov x1, xzr
+; CHECK-GI-NEXT: movk x9, #37449, lsl #32
+; CHECK-GI-NEXT: movk x9, #18724, lsl #48
+; CHECK-GI-NEXT: umulh x9, x8, x9
+; CHECK-GI-NEXT: lsr x9, x9, #1
+; CHECK-GI-NEXT: lsl x10, x9, #3
+; CHECK-GI-NEXT: sub x9, x10, x9
+; CHECK-GI-NEXT: sub x8, x8, x9
+; CHECK-GI-NEXT: bfi x0, x8, #3, #61
+; CHECK-GI-NEXT: ret
+entry:
+ %s = urem i128 %a, 56
+ ret i128 %s
+}
+
+define i128 @udi128_7(i128 %a, i128 %b) {
+; CHECK-SD-LABEL: udi128_7:
+; CHECK-SD: // %bb.0: // %entry
+; CHECK-SD-NEXT: extr x8, x1, x0, #60
+; CHECK-SD-NEXT: and x9, x0, #0xfffffffffffffff
+; CHECK-SD-NEXT: mov x11, #46811 // =0xb6db
+; CHECK-SD-NEXT: movk x11, #56173, lsl #16
+; CHECK-SD-NEXT: and x8, x8, #0xfffffffffffffff
+; CHECK-SD-NEXT: movk x11, #28086, lsl #32
+; CHECK-SD-NEXT: add x8, x9, x8
+; CHECK-SD-NEXT: mov x9, #18725 // =0x4925
+; CHECK-SD-NEXT: movk x11, #46811, lsl #48
+; CHECK-SD-NEXT: movk x9, #9362, lsl #16
+; CHECK-SD-NEXT: add x8, x8, x1, lsr #56
+; CHECK-SD-NEXT: movk x9, #37449, lsl #32
+; CHECK-SD-NEXT: movk x9, #18724, lsl #48
+; CHECK-SD-NEXT: umulh x9, x8, x9
+; CHECK-SD-NEXT: lsr x9, x9, #1
+; CHECK-SD-NEXT: sub x9, x9, x9, lsl #3
+; CHECK-SD-NEXT: add x8, x8, x9
+; CHECK-SD-NEXT: mov x9, #28087 // =0x6db7
+; CHECK-SD-NEXT: movk x9, #46811, lsl #16
+; CHECK-SD-NEXT: subs x8, x0, x8
+; CHECK-SD-NEXT: movk x9, #56173, lsl #32
+; CHECK-SD-NEXT: movk x9, #28086, lsl #48
+; CHECK-SD-NEXT: umulh x10, x8, x9
+; CHECK-SD-NEXT: mul x0, x8, x9
+; CHECK-SD-NEXT: madd x10, x8, x11, x10
+; CHECK-SD-NEXT: sbc x11, x1, xzr
+; CHECK-SD-NEXT: madd x1, x11, x9, x10
+; CHECK-SD-NEXT: ret
+;
+; CHECK-GI-LABEL: udi128_7:
+; CHECK-GI: // %bb.0: // %entry
+; CHECK-GI-NEXT: extr x8, x1, x0, #60
+; CHECK-GI-NEXT: and x9, x0, #0xfffffffffffffff
+; CHECK-GI-NEXT: and x8, x8, #0xfffffffffffffff
+; CHECK-GI-NEXT: add x8, x9, x8
+; CHECK-GI-NEXT: mov x9, #18725 // =0x4925
+; CHECK-GI-NEXT: movk x9, #9362, lsl #16
+; CHECK-GI-NEXT: add x8, x8, x1, lsr #56
+; CHECK-GI-NEXT: movk x9, #37449, lsl #32
+; CHECK-GI-NEXT: movk x9, #18724, lsl #48
+; CHECK-GI-NEXT: umulh x9, x8, x9
+; CHECK-GI...
[truncated]
|
Contributor
Author
|
BTW last time I checked this version after rebasing there is assertion failure. I need to fix that and update this patch before asking for review. |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
This patch improves the lowering of 128-bit unsigned division and remainder by constants (UDIV/UREM) by avoiding buildUDivOrURemUsingMul or a fallback to libcall (__udivti3/uremti3) for specific divisors.
When a divisor D satisfies the condition (1 << ChunkWidth) % D == 1, the 128-bit value is split into fixed-width chunks (e.g., 30-bit) and summed before applying a smaller UDIV/UREM. This transformation is based on the "remainder by summing digits" trick described in Hacker’s Delight.
This is a porting of SelectionDAG's TargetLowering::expandDIVREMByConstant.