[SelectionDAG] Enable division-by-constant optimization for wide types

[nhaehnle]

Summary

This relies on previous support for expanding MULH[US] / [US]MUL_LOHI. Instead
of doing division-by-constant only when those instructions are legal, targets
should now use isIntDivCheap to signal that they do not want this expansion.

This change allows 64-bit division-by-constant to use the more efficient
multiply and shift lowering on AMDGPU.

This also affects a lowering on SPARC in a way that may or may not be more
efficient, see the change in the corresponding test case for the effect. I'd
appreciate some feedback on that.

The vector case is not enabled yet even though it should be correct and will
likely allow better overall code generation eventually. Enabling it gives some
regressions in X86 tests, mostly due to what looks like insufficient
peep-holing when vNi64 multiplies are scalarized.

[nhaehnle]

The reason for excluding the vector case is that it hits another problem with MULHU in some X86 vector div tests, and affects additional X86 test cases. I'd prefer to keep things simple for this change.

[efriedma]

test/CodeGen/SPARC/rem.ll

62

This is generating 8 multiply instructions; something is going wrong in your algorithm. (It should only take four multiply instructions to perform a double-width multiply.)

[nhaehnle]

I looked a bit more closely, and the issue with the Sparc test is that the code uses isOperationLegalOrCustom(ISD::UMUL_LOHI, MVT::i32) to check - this is taken unchanged from expandMUL - but UMUL_LOHI is Expand. When I force my code in expandUMUL_LOHI to use the smaller size UMUL_LOHI, I get only 4 multiplies.

I don't see a clear picture of how multiplication legalization is supposed to work. Currently, MULHU can become UMUL_LOHI in LegalizeDAG::ExpandNode, and UMUL_LOHI can convert to a MUL in a wider type in the DAGCombiner, or to a MUL + MULHU, but only if one of the resulting ops can be combined further. Each of these steps only happen when the resulting operations are LegalOrCustom.

Furthermore, UMUL_LOHI is marked as Expand in the targets that I've looked at, but there isn't actually any code for it in LegalizeDAG::ExpandNode. It all seems a bit messy :(

In part I get the impression that the LegalizeAction just doesn't contain enough information. If a target sets UMUL_LOHI to Expand, should that be a sequence of multiplies of the half-sized integer type, or should it be a single multiply in a larger type? Perhaps Promote should be used to indicate the second option?

[nhaehnle]

In D24822#550503, @nhaehnle wrote:

In part I get the impression that the LegalizeAction just doesn't contain enough information. If a target sets UMUL_LOHI to Expand, should that be a sequence of multiplies of the half-sized integer type, or should it be a single multiply in a larger type? Perhaps Promote should be used to indicate the second option?

It's even worse because at least AMDGPU would want to legalize UMUL_LOHI on MVT::i32 to MUL + MULHU. So there are at least three plausible ways of handling a non-legal UMUL_LOHI. Perhaps this should be made explicit with an enum that the TargetLowering can choose from.

[efriedma]

Using Promote to indicate that a larger multiply should be used seems reasonable.

Not sure it really makes sense to say that there are three ways to perform the operation; UMUL_LOHI and MULHU are essentially the same operation, in the same way that DIV and DIVREM are the same operation.

[nhaehnle]

Move the bulk of the multiplication changes to D24956.

[nhaehnle]

+ BPF test changes because the sdiv lowering fails later now.

[ast]

test/CodeGen/BPF/sdiv_error.ll

3

'cannot select' is unreadable to C programmer comparing to 'Unsupported signed div'.
Usability of BPF is the hardest problem we're facing, so we don't want to lose those error messages. Hence similar to the SDIV error, can you please add the same error for SMUL_LOHI in BPFDAGToDAGISel::Select() ?
Also keeping the same hint "Please convert to unsigned div/mod".
Thanks

[nhaehnle]

test/CodeGen/BPF/sdiv_error.ll

3

Hmm, relying on backend error messages for usability is maybe not the best idea...

Not sure how to change this. Perhaps adding an isSigned parameter to isIntDivCheap?

[ast]

test/CodeGen/BPF/sdiv_error.ll

3

it's not the matter of optimization. There is no sdiv instruction. So please keep the backend error.

[nhaehnle]

I still think it's pretty misguided to rely on errors from the backend,
given that this would be trivial to catch in the frontend where you have
more context for useful error messages anyway, but whatever.

I'm going to take the isIntDivCheap route because yes, it does have to do
with optimizations: you're relying on no optimizations being applied to
sdiv.

[ast]

lgtm
there are different front-ends and we cannot control them all, so backend has to have end-user understandable errors, though it's not pretty.

[nhaehnle]

Rebase on latest version of D24956.

[efriedma]

What happened to this patch?

[RKSimon]

@nhaehnle If you could rebase this and enable vector idiv to show the x86 regressions I may be able to help

lib/CodeGen/SelectionDAG/TargetLowering.cpp

SDValue TargetLowering::BuildSDIV(SDNode *N, const APInt &Divisor,
 
   // If the sdiv has an 'exact' bit we can use a simpler lowering.
   if (cast<BinaryWithFlagsSDNode>(N)->Flags.hasExact())
     return BuildExactSDIV(*this, N->getOperand(0), Divisor, dl, DAG, *Created);
 
   APInt::ms magics = Divisor.magic();
 
   // Multiply the numerator (operand 0) by the magic value
-  // FIXME: We should support doing a MUL in a wider type
+  // FIXME: expand using MULHS for vector types after addressing possible
+  // regressions in X86 backend.
+  unsigned Opcode;
+  if (IsAfterLegalization ? isOperationLegal(ISD::MULHS, VT)
+                          : isOperationLegalOrCustom(ISD::MULHS, VT))
+    Opcode = ISD::MULHS;
+  else if (IsAfterLegalization ? isOperationLegal(ISD::SMUL_LOHI, VT)
+                               : isOperationLegalOrCustom(ISD::SMUL_LOHI, VT))
+    Opcode = ISD::SMUL_LOHI;
+  else if (!IsAfterLegalization && !VT.isVector())
+    Opcode = ISD::MULHS;
+  else
+    return SDValue();
+
   SDValue Q;
-  if (IsAfterLegalization ? isOperationLegal(ISD::MULHS, VT) :
-                            isOperationLegalOrCustom(ISD::MULHS, VT))
+  if (Opcode == ISD::MULHS)
     Q = DAG.getNode(ISD::MULHS, dl, VT, N->getOperand(0),
                     DAG.getConstant(magics.m, dl, VT));
-  else if (IsAfterLegalization ? isOperationLegal(ISD::SMUL_LOHI, VT) :
-                                 isOperationLegalOrCustom(ISD::SMUL_LOHI, VT))
+  else
     Q = SDValue(DAG.getNode(ISD::SMUL_LOHI, dl, DAG.getVTList(VT, VT),
                               N->getOperand(0),
                               DAG.getConstant(magics.m, dl, VT)).getNode(), 1);
-  else
-    return SDValue();       // No mulhs or equvialent
+
   // If d > 0 and m < 0, add the numerator
   if (Divisor.isStrictlyPositive() && magics.m.isNegative()) {
     Q = DAG.getNode(ISD::ADD, dl, VT, Q, N->getOperand(0));
     Created->push_back(Q.getNode());
   }
   // If d < 0 and m > 0, subtract the numerator.
   if (Divisor.isNegative() && magics.m.isStrictlyPositive()) {
     Q = DAG.getNode(ISD::SUB, dl, VT, Q, N->getOperand(0));
if (magics.a != 0 && !Divisor[0]) {
     Created->push_back(Q.getNode());
 
     // Get magic number for the shifted divisor.
     magics = Divisor.lshr(Shift).magicu(Shift);
     assert(magics.a == 0 && "Should use cheap fixup now");
   }
 
   // Multiply the numerator (operand 0) by the magic value
-  // FIXME: We should support doing a MUL in a wider type
-  if (IsAfterLegalization ? isOperationLegal(ISD::MULHU, VT) :
-                            isOperationLegalOrCustom(ISD::MULHU, VT))
+  // FIXME: expand using MULHU for vector types after addressing possible
+  // regressions in X86 backend.
+  unsigned Opcode;
+  if (IsAfterLegalization ? isOperationLegal(ISD::MULHU, VT)
+                          : isOperationLegalOrCustom(ISD::MULHU, VT))
+    Opcode = ISD::MULHU;
+  else if (IsAfterLegalization ? isOperationLegal(ISD::UMUL_LOHI, VT)
+                               : isOperationLegalOrCustom(ISD::UMUL_LOHI, VT))
+    Opcode = ISD::UMUL_LOHI;
+  else if (!IsAfterLegalization && !VT.isVector())
+    Opcode = ISD::MULHU;
+  else
+    return SDValue();
+
+  if (Opcode == ISD::MULHU)
     Q = DAG.getNode(ISD::MULHU, dl, VT, Q, DAG.getConstant(magics.m, dl, VT));
-  else if (IsAfterLegalization ? isOperationLegal(ISD::UMUL_LOHI, VT) :
-                                 isOperationLegalOrCustom(ISD::UMUL_LOHI, VT))
+  else
     Q = SDValue(DAG.getNode(ISD::UMUL_LOHI, dl, DAG.getVTList(VT, VT), Q,
                             DAG.getConstant(magics.m, dl, VT)).getNode(), 1);
-  else
-    return SDValue();       // No mulhu or equvialent
 
   Created->push_back(Q.getNode());
 
   if (magics.a == 0) {
     assert(magics.s < Divisor.getBitWidth() &&
            "We shouldn't generate an undefined shift!");
     return DAG.getNode(
         ISD::SRL, dl, VT, Q,

lib/Target/AMDGPU/SOPInstructions.td

 
 // V_ADD_I32_e32/S_ADD_U32 produces carry in VCC/SCC. For the vector
 // case, the sgpr-copies pass will fix this to use the vector version.
 def : Pat <
   (i32 (addc i32:$src0, i32:$src1)),
   (S_ADD_U32 $src0, $src1)
 >;
 
+// Similarly for V_SUB_I32/S_SUB_U32.
+def : Pat <
+  (i32 (subc i32:$src0, i32:$src1)),
+  (S_SUB_U32 $src0, $src1)
+>;
+
 //===----------------------------------------------------------------------===//
 // SOPP Patterns
 //===----------------------------------------------------------------------===//
 
 def : Pat <
   (int_amdgcn_s_waitcnt i32:$simm16),
   (S_WAITCNT (as_i16imm $simm16))
 >;

test/CodeGen/AMDGPU/sdiv.ll

define void @v_sdiv_i25(i32 addrspace(1)* %out, i25 addrspace(1)* %in) {
   %num = load i25, i25 addrspace(1) * %in
   %den = load i25, i25 addrspace(1) * %den_ptr
   %result = sdiv i25 %num, %den
   %result.ext = sext i25 %result to i32
   store i32 %result.ext, i32 addrspace(1)* %out
   ret void
 }
 
+; FUNC-LABEL: {{^}}sdiv_i32_const:
+; SI: v_mov_b32_e32 [[MAGIC:v[0-9]+]], 0x92492493
+; SI-NOT: v_rcp
+define void @sdiv_i32_const(i32 addrspace(1)* %out, i32 addrspace(1)* %in) {
+  %num = load i32, i32 addrspace(1)* %in
+  %result = sdiv i32 %num, 7
+  store i32 %result, i32 addrspace(1)* %out
+  ret void
+}
+
+; FUNC-LABEL: {{^}}sdiv_i64_const:
+; SI-DAG: s_mov_b32 [[MAGIC_LO:s[0-9]+]], 0x24924925
+; SI-DAG: s_mov_b32 [[MAGIC_HI:s[0-9]+]], 0x49249249
+; SI-NOT: v_rcp
+define void @sdiv_i64_const(i64 addrspace(1)* %out, i64 addrspace(1)* %in) {
+  %num = load i64, i64 addrspace(1)* %in
+  %result = sdiv i64 %num, 7
+  store i64 %result, i64 addrspace(1)* %out
+  ret void
+}
+
 ; Tests for 64-bit divide bypass.
 ; define void @test_get_quotient(i64 addrspace(1)* %out, i64 %a, i64 %b) nounwind {
 ;   %result = sdiv i64 %a, %b
 ;   store i64 %result, i64 addrspace(1)* %out, align 8
 ;   ret void
 ; }
 
 ; define void @test_get_remainder(i64 addrspace(1)* %out, i64 %a, i64 %b) nounwind {

test/CodeGen/AMDGPU/udiv.ll

define void @v_udiv_i24(i32 addrspace(1)* %out, i24 addrspace(1)* %in) {
   %den_ptr = getelementptr i24, i24 addrspace(1)* %in, i24 1
   %num = load i24, i24 addrspace(1) * %in
   %den = load i24, i24 addrspace(1) * %den_ptr
   %result = udiv i24 %num, %den
   %result.ext = zext i24 %result to i32
   store i32 %result.ext, i32 addrspace(1)* %out
   ret void
 }
+
+; FUNC-LABEL: {{^}}udiv_i32_const:
+; SI: v_mov_b32_e32 [[MAGIC:v[0-9]+]], 0x24924925
+; SI-NOT: v_rcp
+define void @udiv_i32_const(i32 addrspace(1)* %out, i32 addrspace(1)* %in) {
+  %num = load i32, i32 addrspace(1)* %in
+  %result = udiv i32 %num, 7
+  store i32 %result, i32 addrspace(1)* %out
+  ret void
+}
+
+; FUNC-LABEL: {{^}}udiv_i64_const:
+; SI-DAG: s_mov_b32 [[MAGIC_HI:s[0-9]+]], 0x24924924
+; SI-DAG: s_mov_b32 [[MAGIC_LO:s[0-9]+]], 0x92492493
+; SI-NOT: v_rcp
+define void @udiv_i64_const(i64 addrspace(1)* %out, i64 addrspace(1)* %in) {
+  %num = load i64, i64 addrspace(1)* %in
+  %result = udiv i64 %num, 7
+  store i64 %result, i64 addrspace(1)* %out
+  ret void
+}

test/CodeGen/BPF/sdiv_error.ll

 ; RUN: not llc -march=bpf < %s 2> %t1
 ; RUN: FileCheck %s < %t1
-; CHECK: Unsupport signed division
+; CHECK: Cannot select: t27: i64,i64 = smul_lohi
 
 ; Function Attrs: norecurse nounwind readnone
 define i32 @test(i32 %len) #0 {
   %1 = srem i32 %len, 15
   ret i32 %1
 }

test/CodeGen/SPARC/rem.ll

 
 define i64 @test2(i64 %X, i64 %Y) {
         %tmp1 = urem i64 %X, %Y
         ret i64 %tmp1
 }
 
 ; PR18150
 ; CHECK-LABEL: test3
-; CHECK:       sethi 2545, [[R0:%[gilo][0-7]]]
-; CHECK:       or    [[R0]], 379, [[R1:%[gilo][0-7]]]
-; CHECK:       mulx  %o0, [[R1]], [[R2:%[gilo][0-7]]]
-; CHECK:       udivx [[R2]], 1021, [[R3:%[gilo][0-7]]]
-; CHECK:       mulx  [[R3]], 1021, [[R4:%[gilo][0-7]]]
-; CHECK:       sub   [[R2]], [[R4]], %o0
+; CHECK:        sethi 2545, %o1
+; CHECK-NEXT:   or %o1, 379, %o1
+; CHECK-NEXT:   mulx %o0, %o1, %o0
+; CHECK-NEXT:   srl %o0, 0, %o1
+; CHECK-NEXT:   sethi 12324, %o2
+; CHECK-NEXT:   or %o2, 108, %o2
+; CHECK-NEXT:   mulx %o1, %o2, %o3
+; CHECK-NEXT:   sethi 1331003, %o4
+; CHECK-NEXT:   or %o4, 435, %o4
+; CHECK-NEXT:   mulx %o1, %o4, %o1
+; CHECK-NEXT:   srlx %o1, 32, %o1
+; CHECK-NEXT:   srlx %o0, 32, %o5
+; CHECK-NEXT:   mulx %o5, %o4, %o4
+; CHECK-NEXT:   srlx %o4, 32, %g2
+; CHECK-NEXT:   srlx %o3, 32, %g3
+; CHECK-NEXT:   mulx %o5, %o2, %o2
+; CHECK-NEXT:   srlx %o2, 32, %o5
+; CHECK-NEXT:   addcc %o1, %o3, %o1
+; CHECK-NEXT:   addxcc %g3, %g2, %o3
+; CHECK-NEXT:   addxcc %o5, 0, %o5
+; CHECK-NEXT:   addcc %o1, %o4, %o1
+; CHECK-NEXT:   addxcc %o3, %o2, %o1
+; CHECK-NEXT:   addxcc %o5, 0, %o2
+; CHECK-NEXT:   srl %o1, 0, %o1
+; CHECK-NEXT:   sllx %o2, 32, %o2
+; CHECK-NEXT:   or %o1, %o2, %o1
+; CHECK-NEXT:   sub %o0, %o1, %o2
+; CHECK-NEXT:   srlx %o2, 1, %o2
+; CHECK-NEXT:   add %o2, %o1, %o1
+; CHECK-NEXT:   srlx %o1, 9, %o1
+; CHECK-NEXT:   mulx %o1, 1021, %o1
+; CHECK-NEXT:   retl
 
 define i64 @test3(i64 %b) {
 entry:
   %mul = mul i64 %b, 2606459
   %rem = urem i64 %mul, 1021
   ret i64 %rem
 }