[GlobalISel] Add sdiv exact (X, constant) -> mul combine.

[aemerson]

Summary

This port of the SDAG optimization is only for exact sdiv case.

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

4956–4959

This greatly depends on the target handling of division and probably should be attached to the tablegen addition

[tschuett]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

5016

Is this cuter as an if-statement to get rid of the (void)?

[aemerson]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

4956–4959

Not sure what you mean by "tablegen addition"?

5016

I don't think so, (void) is the common idiom for silencing unused variable warnings.

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

4956–4959

I mean GICombineRules should have predicate fields, analogous to PatFags

[aemerson]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

4956–4959

Is there a patch to do that already?

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

4956–4959

No, not that I'm aware of

[aemerson]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

4956–4959

Implementing the infrastructure for that seems a separate issue though? This kind of minsize check is mirroring the same check done for SelectionDAG.

[foad]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

4964

Just return C && !C->isNullValue()?

5005

Use APInt::multiplicativeInverse instead?

5022

Is this a way of testing whether the divisor is not a splat? It seems a bit hacky. If the divisor is a splat then we could have saved some work above by only computing the multiplicative inverse once.

5026

How does this work? It seems like it would use a scalar shift amount for a vector shift, which is not allowed by MachineVerifier.

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

4956–4959

Yes. I didn't notice that check; I should probably look into finding a way to disable it there too

[aemerson]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

5022

No, it's just checking if it's a vector type. You're right if it's a splat we can do better here.

5026

As I said this else is actually just handling the scalar case.

[aemerson]

Address comments, add test for non-splat and splat vector cases.

Fix a needed util function not having the right symbol name.

[aemerson]

Add missing change.

[foad]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

5038

Comment is misleading. You're shifting the dividend based on trailing zeros in the divisor, so we don't know that the value is even before shifting, and we don't know the LSB is one after shifting.

[aemerson]

Remove misleading comment.

[aemerson]

ping

[foad]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

4945

This seems redundant given the call to matchUnaryPredicate below. (I don't think it's significantly cheaper than matchUnaryPredicate is it?)

5005

Ping. Is there a reason not to use it?

5014

Is zero extending really correct here? It feels dubious for a signed division but I'm not sure of the maths at this point.

[aemerson]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

4945

Yeah I think you're right.

5005

I did below?

5014

This is also getting beyond the realms on my expertise, but the documentation for it says that the inverse should always fit into the bit width, so extending and truncating shouldn’t affect the result in anyway.

[aemerson]

Remove redundant constant operand check.

[tschuett]

Nit: in the first two asserts the explaining string is missing.

[aemerson]

In D130517#3705782, @tschuett wrote:

Nit: in the first two asserts the explaining string is missing.

Sure I can add one before commit.

[aemerson]

ping

llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h

public:
   /// Given an G_UDIV \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".
   MachineInstr *buildUDivUsingMul(MachineInstr &MI);
   /// Combine G_UDIV by constant into a multiply by magic constant.
   bool matchUDivByConst(MachineInstr &MI);
   void applyUDivByConst(MachineInstr &MI);
 
+  /// Given an G_SDIV \p MI expressing a signed 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".
+  MachineInstr *buildSDivUsingMul(MachineInstr &MI);
+  bool matchSDivByConst(MachineInstr &MI);
+  void applySDivByConst(MachineInstr &MI);
+
   // G_UMULH x, (1 << c)) -> x >> (bitwidth - c)
   bool matchUMulHToLShr(MachineInstr &MI);
   void applyUMulHToLShr(MachineInstr &MI);
 
   /// Try to transform \p MI by using all of the above
   /// combine functions. Returns true if changed.
   bool tryCombine(MachineInstr &MI);
 

llvm/include/llvm/Target/GlobalISel/Combine.td

def form_bitfield_extract : GICombineGroup<[bitfield_extract_from_sext_inreg,
                                             bitfield_extract_from_shr_and]>;
 
 def udiv_by_const : GICombineRule<
   (defs root:$root),
   (match (wip_match_opcode G_UDIV):$root,
    [{ return Helper.matchUDivByConst(*${root}); }]),
   (apply [{ Helper.applyUDivByConst(*${root}); }])>;
 
-def intdiv_combines : GICombineGroup<[udiv_by_const]>;
+def sdiv_by_const : GICombineRule<
+  (defs root:$root),
+  (match (wip_match_opcode G_SDIV):$root,
+   [{ return Helper.matchSDivByConst(*${root}); }]),
+  (apply [{ Helper.applySDivByConst(*${root}); }])>;
+
+def intdiv_combines : GICombineGroup<[udiv_by_const, sdiv_by_const]>;
 
 def reassoc_ptradd : GICombineRule<
   (defs root:$root, build_fn_matchinfo:$matchinfo),
   (match (wip_match_opcode G_PTR_ADD):$root,
     [{ return Helper.matchReassocPtrAdd(*${root}, ${matchinfo}); }]),
   (apply [{ Helper.applyBuildFnNoErase(*${root}, ${matchinfo}); }])>;
 
 def reassocs : GICombineGroup<[reassoc_ptradd]>;

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

bool CombinerHelper::matchUDivByConst(MachineInstr &MI) {
   return matchUnaryPredicate(MRI, RHS, CheckEltValue);
 }
 
 void CombinerHelper::applyUDivByConst(MachineInstr &MI) {
   auto *NewMI = buildUDivUsingMul(MI);
   replaceSingleDefInstWithReg(MI, NewMI->getOperand(0).getReg());
 }
 
+bool CombinerHelper::matchSDivByConst(MachineInstr &MI) {
+  assert(MI.getOpcode() == TargetOpcode::G_SDIV);
+  Register Dst = MI.getOperand(0).getReg();
+  Register RHS = MI.getOperand(2).getReg();
+  LLT DstTy = MRI.getType(Dst);
+  auto *RHSDef = MRI.getVRegDef(RHS);
+  if (!isConstantOrConstantVector(*RHSDef, MRI))
+    return false;
+
+  auto &MF = *MI.getMF();
+  AttributeList Attr = MF.getFunction().getAttributes();
+  const auto &TLI = getTargetLowering();
+  LLVMContext &Ctx = MF.getFunction().getContext();
+  auto &DL = MF.getDataLayout();
+  if (TLI.isIntDivCheap(getApproximateEVTForLLT(DstTy, DL, Ctx), Attr))
+    return false;
+
+  // Don't do this for minsize because the instruction sequence is usually
+  // larger.
+  if (MF.getFunction().hasMinSize())
+    return false;
+
+  // If the sdiv has an 'exact' flag we can use a simpler lowering.
+  if (MI.getFlag(MachineInstr::MIFlag::IsExact)) {
+    auto CheckEltValue = [&](const Constant *C) {
+      if (auto *CI = dyn_cast_or_null<ConstantInt>(C))
+        return !CI->isZero();
+      return false;
+    };
+    return matchUnaryPredicate(MRI, RHS, CheckEltValue);
+  }
+
+  // Don't support the general case for now.
+  return false;
+}
+
+void CombinerHelper::applySDivByConst(MachineInstr &MI) {
+  auto *NewMI = buildSDivUsingMul(MI);
+  replaceSingleDefInstWithReg(MI, NewMI->getOperand(0).getReg());
+}
+
+MachineInstr *CombinerHelper::buildSDivUsingMul(MachineInstr &MI) {
+  assert(MI.getOpcode() == TargetOpcode::G_SDIV);
+  auto &SDiv = cast<GenericMachineInstr>(MI);
+  Register Dst = SDiv.getReg(0);
+  Register LHS = SDiv.getReg(1);
+  Register RHS = SDiv.getReg(2);
+  LLT Ty = MRI.getType(Dst);
+  LLT ScalarTy = Ty.getScalarType();
+  LLT ShiftAmtTy = getTargetLowering().getPreferredShiftAmountTy(Ty);
+  LLT ScalarShiftAmtTy = ShiftAmtTy.getScalarType();
+  auto &MIB = Builder;
+  MIB.setInstrAndDebugLoc(MI);
+
+  bool UseSRA = false;
+  SmallVector<Register, 16> Shifts, Factors;
+
+  auto BuildSDIVPattern = [&](const Constant *C) {
+    auto *CI = cast<ConstantInt>(C);
+    APInt Divisor = CI->getValue();
+    unsigned Shift = Divisor.countTrailingZeros();
+    if (Shift) {
+      Divisor.ashrInPlace(Shift);
+      UseSRA = true;
+    }
+
+    // Calculate the multiplicative inverse, using Newton's method.
+    APInt t;
+    APInt Factor = Divisor;
+    while ((t = Divisor * Factor) != 1)
+      Factor *= APInt(Divisor.getBitWidth(), 2) - t;
+    Shifts.push_back(MIB.buildConstant(ScalarShiftAmtTy, Shift).getReg(0));
+    Factors.push_back(MIB.buildConstant(ScalarTy, Factor).getReg(0));
+    return true;
+  };
+
+  // Collect all magic values from the build vector.
+  bool Matched = matchUnaryPredicate(MRI, RHS, BuildSDIVPattern);
+  (void)Matched;
+  assert(Matched && "Expected unary predicate match to succeed");
+
+  Register Shift, Factor;
+  auto *RHSDef = cast<GenericMachineInstr>(getDefIgnoringCopies(RHS, MRI));
+  if (isa<GBuildVector>(RHSDef)) {
+    Shift = MIB.buildBuildVector(ShiftAmtTy, Shifts).getReg(0);
+    Factor = MIB.buildBuildVector(Ty, Factors).getReg(0);
+  } else {
+    Shift = Shifts[0];
+    Factor = Factors[0];
+  }
+
+  Register Res = LHS;
+
+  // Shift the value upfront if it is even, so the LSB is one.
+  if (UseSRA)
+    Res = MIB.buildAShr(Ty, Res, Shift, MachineInstr::IsExact).getReg(0);
+
+  return MIB.buildMul(Ty, Res, Factor);
+}
+
 bool CombinerHelper::matchUMulHToLShr(MachineInstr &MI) {
   assert(MI.getOpcode() == TargetOpcode::G_UMULH);
   Register RHS = MI.getOperand(2).getReg();
   Register Dst = MI.getOperand(0).getReg();
   LLT Ty = MRI.getType(Dst);
   LLT ShiftAmtTy = getTargetLowering().getPreferredShiftAmountTy(Ty);
   auto MatchPow2ExceptOne = [&](const Constant *C) {
     if (auto *CI = dyn_cast<ConstantInt>(C))

llvm/test/CodeGen/AArch64/GlobalISel/combine-sdiv.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -o - -mtriple=aarch64-unknown-unknown -run-pass=aarch64-prelegalizer-combiner -verify-machineinstrs %s | FileCheck %s
+--- |
+  target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+
+  define void @sdiv_exact() { ret void }
+  define void @sdiv_noexact() { ret void }
+  define void @sdiv_exact_minsize() #0 { ret void }
+  define void @div_v4s32() { ret void }
+
+  attributes #0 = { minsize }
+
+...
+---
+name:            sdiv_exact
+body:             |
+  bb.1:
+    liveins: $w0
+
+    ; CHECK-LABEL: name: sdiv_exact
+    ; CHECK: liveins: $w0
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s32) = COPY $w0
+    ; CHECK-NEXT: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 3
+    ; CHECK-NEXT: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 -991146299
+    ; CHECK-NEXT: [[ASHR:%[0-9]+]]:_(s32) = exact G_ASHR [[COPY]], [[C]](s32)
+    ; CHECK-NEXT: [[MUL:%[0-9]+]]:_(s32) = G_MUL [[ASHR]], [[C1]]
+    ; CHECK-NEXT: $w0 = COPY [[MUL]](s32)
+    ; CHECK-NEXT: RET_ReallyLR implicit $w0
+    %0:_(s32) = COPY $w0
+    %1:_(s32) = G_CONSTANT i32 104
+    %2:_(s32) = exact G_SDIV %0, %1
+    $w0 = COPY %2(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            sdiv_noexact
+body:             |
+  bb.1:
+    liveins: $w0
+
+    ; CHECK-LABEL: name: sdiv_noexact
+    ; CHECK: liveins: $w0
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s32) = COPY $w0
+    ; CHECK-NEXT: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 104
+    ; CHECK-NEXT: [[SDIV:%[0-9]+]]:_(s32) = G_SDIV [[COPY]], [[C]]
+    ; CHECK-NEXT: $w0 = COPY [[SDIV]](s32)
+    ; CHECK-NEXT: RET_ReallyLR implicit $w0
+    %0:_(s32) = COPY $w0
+    %1:_(s32) = G_CONSTANT i32 104
+    %2:_(s32) = G_SDIV %0, %1
+    $w0 = COPY %2(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            sdiv_exact_minsize
+body:             |
+  bb.1:
+    liveins: $w0
+
+    ; CHECK-LABEL: name: sdiv_exact_minsize
+    ; CHECK: liveins: $w0
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s32) = COPY $w0
+    ; CHECK-NEXT: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 104
+    ; CHECK-NEXT: [[SDIV:%[0-9]+]]:_(s32) = exact G_SDIV [[COPY]], [[C]]
+    ; CHECK-NEXT: $w0 = COPY [[SDIV]](s32)
+    ; CHECK-NEXT: RET_ReallyLR implicit $w0
+    %0:_(s32) = COPY $w0
+    %1:_(s32) = G_CONSTANT i32 104
+    %2:_(s32) = exact G_SDIV %0, %1
+    $w0 = COPY %2(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            div_v4s32
+body:             |
+  bb.1:
+    liveins: $q0
+
+    ; CHECK-LABEL: name: div_v4s32
+    ; CHECK: liveins: $q0
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(<4 x s32>) = COPY $q0
+    ; CHECK-NEXT: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 3
+    ; CHECK-NEXT: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 -991146299
+    ; CHECK-NEXT: [[BUILD_VECTOR:%[0-9]+]]:_(<4 x s32>) = G_BUILD_VECTOR [[C]](s32), [[C]](s32), [[C]](s32), [[C]](s32)
+    ; CHECK-NEXT: [[BUILD_VECTOR1:%[0-9]+]]:_(<4 x s32>) = G_BUILD_VECTOR [[C1]](s32), [[C1]](s32), [[C1]](s32), [[C1]](s32)
+    ; CHECK-NEXT: [[ASHR:%[0-9]+]]:_(<4 x s32>) = exact G_ASHR [[COPY]], [[BUILD_VECTOR]](<4 x s32>)
+    ; CHECK-NEXT: [[MUL:%[0-9]+]]:_(<4 x s32>) = G_MUL [[ASHR]], [[BUILD_VECTOR1]]
+    ; CHECK-NEXT: $q0 = COPY [[MUL]](<4 x s32>)
+    ; CHECK-NEXT: RET_ReallyLR implicit $q0
+    %0:_(<4 x s32>) = COPY $q0
+    %2:_(s32) = G_CONSTANT i32 104
+    %1:_(<4 x s32>) = G_BUILD_VECTOR %2(s32), %2(s32), %2(s32), %2(s32)
+    %3:_(<4 x s32>) = exact G_SDIV %0, %1
+    $q0 = COPY %3(<4 x s32>)
+    RET_ReallyLR implicit $q0
+
+...