[SelectionDAG] Add computeOverflowForSignedMul / computeOverflowForUnsignedMul overflow handlers

[elhewaty]

Summary

Support signed multiplication
Support unsigned multiplication

[RKSimon]

Now the tricky bit - hooking this into DAGCombiner and adding suitable testing.

visitMULO already has some specific case overflow detection code, so we can start by replacing it with a willNotOverflowMul test, similar to what visitADDO/visitSUBO do.

Make sure you create your diff with context: git diff HEAD~1 -U999999 > mypatch.patch

[elhewaty]

This comment was removed by elhewaty.

[elhewaty]

This comment was removed by elhewaty.

[elhewaty]

I used git blame on SelectionDAG.cpp and DAGCombiner.cpp and found that tests are in llvm/test/CodeGen/X86/xaluo.ll does this mean that I should modify xaluo.ll and xmulo.ll? am I even on the right track?
Why after the modification and before adding tests make check-llvm-codegen fails in or-with-overflow.ll and vec_smulo.ll
I discovered I should modify xmulo.ll, vec_smulo.ll and xaluo.ll.

[elhewaty]

@RKSimon I noticed that people add tests before code changes, why?
Can you help me with the tests? I really worked hard to understand how to write one, but no results.

[RKSimon]

I'd recommend starting with removing the existing code at the bottom of visitMULO that handles SMULO/UMULO -> MUL conversion and replacing it with a willNotOverflowMul check.

[elhewaty]

I already did this.

[RKSimon]

Please can you update the diff?

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5442

This i1 fold needs adding back?

[RKSimon]

regarding test coverage - its ok to add tests in the patch to show the new coverage, once the patch is close to being accepted a reviewer might ask that the tests be pushed first so that the patch shows the codegen improvement.

Alternatively you can create a parent-child relationship between patches, but since LLVM is moving to github PRs this month I'd possibly recommend you just create a stacked PR instead

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

4055

remove this and put it in its own patch with test coverage

4093

remove this and put it in its own patch with test coverage

4103

remove this and put it in its own patch with test coverage

[elhewaty]

I will update the patch and upload it now

[elhewaty]

As I am a complete beginner with LLVM how can write tests? Is there any tutorial or example?

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

4058

leading zeros -> sign bits.

4060

leading zeros -> sign bits.

[RKSimon]

As I am a complete beginner with LLVM how can write tests? Is there any tutorial or example?

In this case the best reference tests are probably in combine-mulo.ll and xmulo.ll in the llvm-project/llvm/test/CodeGen/X86/ folder

I think you're only missing test coverage for the computeOverflowForSignedMul "SignBits == BitWidth + 1" knownbits cases.

You could investigate how InstCombine handles these cases - look inside llvm-project\llvm\test\Transforms\InstCombine for smul.overflow tests - you could try disabling the "SignBits == BitWidth + 1" handling in ValueTracking.cpp and then see which tests change/fail with ninja check-llvm-transforms-instcombine - you might then be able to convert some of those to combine-mulo.ll / xmulo.ll

[elhewaty]

In D159406#4637304, @RKSimon wrote:

As I am a complete beginner with LLVM how can write tests? Is there any tutorial or example?

In this case the best reference tests are probably in combine-mulo.ll and xmulo.ll in the llvm-project/llvm/test/CodeGen/X86/ folder

I think you're only missing test coverage for the computeOverflowForSignedMul "SignBits == BitWidth + 1" knownbits cases.

What about the test coverage for the rest of the functions?

You could investigate how InstCombine handles these cases - look inside llvm-project\llvm\test\Transforms\InstCombine for smul.overflow tests - you could try disabling the "SignBits == BitWidth + 1" handling in ValueTracking.cpp and then see which tests change/fail with ninja check-llvm-transforms-instcombine - you might then be able to convert some of those to combine-mulo.ll / xmulo.ll

I think I will try this now

[elhewaty]

@RKSimon Hi I don't fully understand the testing infrastructure. I think I need some help.
for the following test:

%t = call { i16, i1 } @llvm.smul.with.overflow.i16(i16 -256, i16 -128)
  %val = extractvalue {i16, i1} %t, 0
  %obit = extractvalue {i16, i1} %t, 1
  ret i1 %obit

This should be handled with "SignBits == BitWidth + 1", right?
how should I write this?

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5441

Isn't this a wrong formatting it becomes this every time I use git clang-format

[RKSimon]

I've found an InstCombine patch which should handle the new smulo case and committed to the DAG codegen tests - please can you rebase on e086e0aeef6b and run ninja check-llvm-codegen-x86

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5441

It doesn't that pretty, you could refactor it slightly:

if (IsSigned && VT.getScalarSizeInBits() == 1) {
    SDValue And = DAG.getNode(ISD::AND, DL, VT, N0, N1);
    SDValue Cmp = DAG.getSetCC(DL, CarryVT, And, DAG.getConstant(0, DL, VT), ISD::SETNE);
    return CombineTo(N, And, Cmp);
  }

[elhewaty]

In fact, I found these tests in with_overflow.ll the first test. and I added it but I don't know why the code failed. even after rebasing the tests fail. and the tests pass if I remove the conditions.

I am sorry for bothering you, I know this is too much.
Maybe I should abandon the patch.

[RKSimon]

You're almost there - if you run ninja check-llvm-codegen you should only see 1 failure:

Failed Tests (1):
  LLVM :: CodeGen/X86/combine-mulo.ll

You can then regenerate that test file with the llvm-project\llvm\utils\update_llc_test_checks.py script:

cd llvm/test/CodeGen/X86
<pathto>\update_llc_test_checks.py --llc-binary=<pathto>\llc combine-mulo.ll

(replacing the pathto bits)

[RKSimon]

LGTM cheers - if you send me your full name / email address I'll commit it for you

[elhewaty]

Mohamed Atef <[e-mail] >

[RKSimon]

Thanks @elhewaty - are you intending to add the additional sub overflow tests and handling as well?

[elhewaty]

Yes, But I am working on the InstCombine patch as you know.
I don't mind working on as many patches as possible. I want to understand LLVM internals.
But I have some personal problems these days, but I can still work. If you don't mind I can work on
bugs at my own pace assign me to a bug and I will work on it.

[RKSimon]

Thanks @elhewaty - also please can you submit any future patches as github PRs?

[elhewaty]

Ok, I will.

llvm/include/llvm/CodeGen/SelectionDAG.h

return IsSigned ? computeOverflowForSignedSub(N0, N1)
                     : computeOverflowForUnsignedSub(N0, N1);
   }
 
   /// Determine if the result of the sub of 2 nodes can never overflow.
   bool willNotOverflowSub(bool IsSigned, SDValue N0, SDValue N1) const {
     return computeOverflowForSub(IsSigned, N0, N1) == OFK_Never;
   }
 
+  /// Determine if the result of the signed mul of 2 nodes can overflow.
+  OverflowKind computeOverflowForSignedMul(SDValue N0, SDValue N1) const;
+
+  /// Determine if the result of the unsigned mul of 2 nodes can overflow.
+  OverflowKind computeOverflowForUnsignedMul(SDValue N0, SDValue N1) const;
+
+  /// Determine if the result of the mul of 2 nodes can overflow.
+  OverflowKind computeOverflowForMul(bool IsSigned, SDValue N0,
+                                     SDValue N1) const {
+    return IsSigned ? computeOverflowForSignedMul(N0, N1)
+                    : computeOverflowForUnsignedMul(N0, N1);
+  }
+
+  /// Determine if the result of the mul of 2 nodes can never overflow.
+  bool willNotOverflowMul(bool IsSigned, SDValue N0, SDValue N1) const {
+    return computeOverflowForMul(IsSigned, N0, N1) == OFK_Never;
+  }
+
   /// Test if the given value is known to have exactly one bit set. This differs
   /// from computeKnownBits in that it doesn't necessarily determine which bit
   /// is set.
   bool isKnownToBeAPowerOfTwo(SDValue Val, unsigned Depth = 0) const;
 
   /// Return the number of times the sign bit of the register is replicated into
   /// the other bits. We know that at least 1 bit is always equal to the sign
   /// bit (itself), but other cases can give us information. For example,

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitMULO(SDNode *N) {
 
   // (mulo x, 2) -> (addo x, x)
   // FIXME: This needs a freeze.
   if (N1C && N1C->getAPIntValue() == 2 &&
       (!IsSigned || VT.getScalarSizeInBits() > 2))
     return DAG.getNode(IsSigned ? ISD::SADDO : ISD::UADDO, DL,
                        N->getVTList(), N0, N0);
 
-  if (IsSigned) {
-    // A 1 bit SMULO overflows if both inputs are 1.
-    if (VT.getScalarSizeInBits() == 1) {
-      SDValue And = DAG.getNode(ISD::AND, DL, VT, N0, N1);
-      return CombineTo(N, And,
-                       DAG.getSetCC(DL, CarryVT, And,
-                                    DAG.getConstant(0, DL, VT), ISD::SETNE));
-    }
+  if (IsSigned && VT.getScalarSizeInBits() == 1) {
+    SDValue Cmp = DAG.getSetCC(DL, CarryVT, And,
+                               DAG.getConstant(0, DL, VT), ISD::SETNE);
+    return CombineTo(N, And, Cmp);
 
-    // Multiplying n * m significant bits yields a result of n + m significant
-    // bits. If the total number of significant bits does not exceed the
-    // result bit width (minus 1), there is no overflow.
-    unsigned SignBits = DAG.ComputeNumSignBits(N0);
-    if (SignBits > 1)
-      SignBits += DAG.ComputeNumSignBits(N1);
-    if (SignBits > VT.getScalarSizeInBits() + 1)
-      return CombineTo(N, DAG.getNode(ISD::MUL, DL, VT, N0, N1),
-                       DAG.getConstant(0, DL, CarryVT));
-  } else {
-    KnownBits N1Known = DAG.computeKnownBits(N1);
-    KnownBits N0Known = DAG.computeKnownBits(N0);
-    bool Overflow;
-    (void)N0Known.getMaxValue().umul_ov(N1Known.getMaxValue(), Overflow);
-    if (!Overflow)
-      return CombineTo(N, DAG.getNode(ISD::MUL, DL, VT, N0, N1),
-                       DAG.getConstant(0, DL, CarryVT));
-  }
-
+  // If it cannot overflow, transform into a mul.
+  if (DAG.willNotOverflowMul(IsSigned, N0, N1))
   return SDValue();
 }
 
 // Function to calculate whether the Min/Max pair of SDNodes (potentially
 // swapped around) make a signed saturate pattern, clamping to between a signed
 // saturate of -2^(BW-1) and 2^(BW-1)-1, or an unsigned saturate of 0 and 2^BW.
 // Returns the node being clamped and the bitwidth of the clamp in BW. Should
 // work with both SMIN/SMAX nodes and setcc/select combo. The operands are the

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

SelectionDAG::computeOverflowForSignedAdd(SDValue N0, SDValue N1) const {
   if (ComputeNumSignBits(N0) > 1 && ComputeNumSignBits(N1) > 1)
     return OFK_Never;
 
   // TODO: Add ConstantRange::signedAddMayOverflow handling.
   return OFK_Sometime;
 }
 
 SelectionDAG::OverflowKind
 SelectionDAG::computeOverflowForUnsignedAdd(SDValue N0, SDValue N1) const {
   // X + 0 never overflow
   if (isNullConstant(N1))
     return OFK_Never;
 
   // mulhi + 1 never overflow
   KnownBits N1Known = computeKnownBits(N1);
   if (N0.getOpcode() == ISD::UMUL_LOHI && N0.getResNo() == 1 &&
       N1Known.getMaxValue().ult(2))
     return OFK_Never;
 
   KnownBits N0Known = computeKnownBits(N0);
   if (N1.getOpcode() == ISD::UMUL_LOHI && N1.getResNo() == 1 &&
       N0Known.getMaxValue().ult(2))
SelectionDAG::computeOverflowForSignedSub(SDValue N0, SDValue N1) const {
   if (ComputeNumSignBits(N0) > 1 && ComputeNumSignBits(N1) > 1)
     return OFK_Never;
 
   // TODO: Add ConstantRange::signedSubMayOverflow handling.
   return OFK_Sometime;
 }
 
 SelectionDAG::OverflowKind
 SelectionDAG::computeOverflowForUnsignedSub(SDValue N0, SDValue N1) const {
   // X - 0 never overflow
   if (isNullConstant(N1))
     return OFK_Never;
 
   // TODO: Add ConstantRange::unsignedSubMayOverflow handling.
   return OFK_Sometime;
 }
 
+SelectionDAG::OverflowKind
+SelectionDAG::computeOverflowForUnsignedMul(SDValue N0, SDValue N1) const {
+  // X * 0 and X * 1 never overflow.
+  if (isNullConstant(N1) || isOneConstant(N1))
+    return OFK_Never;
+
+  KnownBits N0Known = computeKnownBits(N0);
+  KnownBits N1Known = computeKnownBits(N1);
+  ConstantRange N0Range = ConstantRange::fromKnownBits(N0Known, false);
+  ConstantRange N1Range = ConstantRange::fromKnownBits(N1Known, false);
+  return mapOverflowResult(N0Range.unsignedMulMayOverflow(N1Range));
+}
+
+SelectionDAG::OverflowKind
+SelectionDAG::computeOverflowForSignedMul(SDValue N0, SDValue N1) const {
+  // X * 0 and X * 1 never overflow.
+  if (isNullConstant(N1) || isOneConstant(N1))
+    return OFK_Never;
+
+  // Get the size of the result.
+  unsigned BitWidth = N0.getScalarValueSizeInBits();
+
+  // Sum of the sign bits.
+  unsigned SignBits = ComputeNumSignBits(N0) + ComputeNumSignBits(N1);
+
+  // If we have enough sign bits, then there's no overflow.
+  if (SignBits > BitWidth + 1)
+    return OFK_Never;
+
+  if (SignBits == BitWidth + 1) {
+    // The overflow occurs when the true multiplication of the
+    // the operands is the minimum negative number.
+    KnownBits N0Known = computeKnownBits(N0);
+    KnownBits N1Known = computeKnownBits(N1);
+    // If one of the operands is non-negative, then there's no
+    // overflow.
+    if (N0Known.isNonNegative() || N1Known.isNonNegative())
+      return OFK_Never;
+  }
+
+  return OFK_Sometime;
+}
+
 bool SelectionDAG::isKnownToBeAPowerOfTwo(SDValue Val, unsigned Depth) const {
   if (Depth >= MaxRecursionDepth)
     return false; // Limit search depth.
 
   EVT OpVT = Val.getValueType();
   unsigned BitWidth = OpVT.getScalarSizeInBits();
 
   // Is the constant a known power of 2?

llvm/test/CodeGen/X86/combine-mulo.ll

 
 define { i32, i1 } @combine_smul_nsw(i32 %a, i32 %b) {
 ; CHECK-LABEL: combine_smul_nsw:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movl %esi, %eax
 ; CHECK-NEXT:    andl $4095, %edi # imm = 0xFFF
 ; CHECK-NEXT:    andl $524287, %eax # imm = 0x7FFFF
 ; CHECK-NEXT:    imull %edi, %eax
-; CHECK-NEXT:    seto %dl
+; CHECK-NEXT:    xorl %edx, %edx
 ; CHECK-NEXT:    retq
   %aa = and i32 %a, 4095 ; 0xfff
   %bb = and i32 %b, 524287; 0x7ffff
   %x = call { i32, i1 } @llvm.smul.with.overflow.i32(i32 %aa, i32 %bb)
   ret { i32, i1 } %x
 }
 
 define { <4 x i32>, <4 x i1> } @combine_vec_smul_nsw(<4 x i32> %a, <4 x i32> %b) {
 ; SSE-LABEL: combine_vec_smul_nsw:
 ; SSE:       # %bb.0:
 ; SSE-NEXT:    pand {{\.?LCPI[0-9]+_[0-9]+}}(%rip), %xmm0
 ; SSE-NEXT:    pand {{\.?LCPI[0-9]+_[0-9]+}}(%rip), %xmm1
-; SSE-NEXT:    pshufd {{.*#+}} xmm2 = xmm1[1,1,3,3]
-; SSE-NEXT:    pshufd {{.*#+}} xmm3 = xmm0[1,1,3,3]
-; SSE-NEXT:    pmuldq %xmm2, %xmm3
-; SSE-NEXT:    movdqa %xmm0, %xmm2
-; SSE-NEXT:    pmuldq %xmm1, %xmm2
-; SSE-NEXT:    pshufd {{.*#+}} xmm2 = xmm2[1,1,3,3]
-; SSE-NEXT:    pblendw {{.*#+}} xmm2 = xmm2[0,1],xmm3[2,3],xmm2[4,5],xmm3[6,7]
-; SSE-NEXT:    pxor %xmm3, %xmm3
-; SSE-NEXT:    pcmpeqd %xmm2, %xmm3
-; SSE-NEXT:    pcmpeqd %xmm2, %xmm2
-; SSE-NEXT:    pxor %xmm3, %xmm2
 ; SSE-NEXT:    pmulld %xmm1, %xmm0
-; SSE-NEXT:    movdqa %xmm2, %xmm1
+; SSE-NEXT:    pxor %xmm1, %xmm1
 ; SSE-NEXT:    retq
 ;
 ; AVX-LABEL: combine_vec_smul_nsw:
 ; AVX:       # %bb.0:
 ; AVX-NEXT:    vpbroadcastd {{.*#+}} xmm2 = [4095,4095,4095,4095]
 ; AVX-NEXT:    vpand %xmm2, %xmm0, %xmm0
 ; AVX-NEXT:    vpbroadcastd {{.*#+}} xmm2 = [524287,524287,524287,524287]
-; AVX-NEXT:    vpand %xmm2, %xmm1, %xmm2
-; AVX-NEXT:    vpshufd {{.*#+}} xmm1 = xmm2[1,1,3,3]
-; AVX-NEXT:    vpshufd {{.*#+}} xmm3 = xmm0[1,1,3,3]
-; AVX-NEXT:    vpmuldq %xmm1, %xmm3, %xmm1
-; AVX-NEXT:    vpmuldq %xmm2, %xmm0, %xmm3
-; AVX-NEXT:    vpshufd {{.*#+}} xmm3 = xmm3[1,1,3,3]
-; AVX-NEXT:    vpblendd {{.*#+}} xmm1 = xmm3[0],xmm1[1],xmm3[2],xmm1[3]
-; AVX-NEXT:    vpxor %xmm3, %xmm3, %xmm3
-; AVX-NEXT:    vpcmpeqd %xmm3, %xmm1, %xmm1
-; AVX-NEXT:    vpcmpeqd %xmm3, %xmm3, %xmm3
-; AVX-NEXT:    vpxor %xmm3, %xmm1, %xmm1
-; AVX-NEXT:    vpmulld %xmm2, %xmm0, %xmm0
+; AVX-NEXT:    vpand %xmm2, %xmm1, %xmm1
+; AVX-NEXT:    vpmulld %xmm1, %xmm0, %xmm0
+; AVX-NEXT:    vpxor %xmm1, %xmm1, %xmm1
 ; AVX-NEXT:    retq
   %aa = and <4 x i32> %a, <i32 4095, i32 4095, i32 4095, i32 4095>
   %bb = and <4 x i32> %b, <i32 524287, i32 524287, i32 524287, i32 524287>
   %x = call { <4 x i32>, <4 x i1> } @llvm.smul.with.overflow.v4i32(<4 x i32> %aa, <4 x i32> %bb)
   ret { <4 x i32>, <4 x i1> } %x
 }