[X86ISelLowering] Replace uint64_t with APInt to prevent overflow

[• chenli]

Summary

This is a prerequisite patch for http://reviews.llvm.org/D14603

[RKSimon]

Just to be clear - APInt operators don't prevent or assert on overflow, it just provides *_ov methods that make it easier to recognise when overflow occurs. Please can you confirm that this approach will work for D14603?

[• chenli]

In D15315#304816, @RKSimon wrote:

Just to be clear - APInt operators don't prevent or assert on overflow, it just provides *_ov methods that make it easier to recognise when overflow occurs. Please can you confirm that this approach will work for D14603?

No, it doesn't prevent overflow. But APInt makes it easy to add checks of MulAmt + 1 and MulAmt - 1 in D14603 as you mentioned.
What do you mean by confirming this works for D14603? I think I need to modify D14603 once this get checked in and add new test cases to show overflow doesn't happen.

[RKSimon]

In D15315#305248, @chenli wrote:

In D15315#304816, @RKSimon wrote:

Just to be clear - APInt operators don't prevent or assert on overflow, it just provides *_ov methods that make it easier to recognise when overflow occurs. Please can you confirm that this approach will work for D14603?

No, it doesn't prevent overflow. But APInt makes it easy to add checks of MulAmt + 1 and MulAmt - 1 in D14603 as you mentioned.
What do you mean by confirming this works for D14603? I think I need to modify D14603 once this get checked in and add new test cases to show overflow doesn't happen.

I just want to make sure that you've been able to use this patch locally with a suitably updated D14603 to deal with the overflow test cases that we discussed.

[• chenli]

I applied the patch locally and it worked with 0xFFFFFFFF. However, in practice, neither 0xFFFFFFFF nor 0 will flow into this function because llvm handles them with special cases. For 0, it returns a 0 directly, and for 0xFFFFFFFF, it returns 0 - (the other operand). I've hacked to bypass the special cases in order to test the overflow case could be handled correctly by this code.

[RKSimon]

In D15315#306841, @chenli wrote:

I applied the patch locally and it worked with 0xFFFFFFFF. However, in practice, neither 0xFFFFFFFF nor 0 will flow into this function because llvm handles them with special cases. For 0, it returns a 0 directly, and for 0xFFFFFFFF, it returns 0 - (the other operand). I've hacked to bypass the special cases in order to test the overflow case could be handled correctly by this code.

If that is true - might it be better just to add suitable asserts / early returns to D14603 that check for cases that would overflow. In which case, I feel rather guilty as the APInt conversion work is probably unnecessary.....

[• chenli]

I applied the patch locally and it worked with 0xFFFFFFFF. However, in practice, neither 0xFFFFFFFF nor 0 will flow into this function because llvm handles them with special cases. For 0, it returns a 0 directly, and for 0xFFFFFFFF, it returns 0 - (the other operand). I've hacked to bypass the special cases in order to test the overflow case could be handled correctly by this code.

In D15315#307134, @RKSimon wrote:

In D15315#306841, @chenli wrote:

I applied the patch locally and it worked with 0xFFFFFFFF. However, in practice, neither 0xFFFFFFFF nor 0 will flow into this function because llvm handles them with special cases. For 0, it returns a 0 directly, and for 0xFFFFFFFF, it returns 0 - (the other operand). I've hacked to bypass the special cases in order to test the overflow case could be handled correctly by this code.

If that is true - might it be better just to add suitable asserts / early returns to D14603 that check for cases that would overflow. In which case, I feel rather guilty as the APInt conversion work is probably unnecessary.....

Sure. I will discard this patch and update D14603.

lib/Target/X86/X86ISelLowering.cpp

static SDValue PerformMulCombine(SDNode *N, SelectionDAG &DAG,
 
   EVT VT = N->getValueType(0);
   if (VT != MVT::i64 && VT != MVT::i32)
     return SDValue();
 
   ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
   if (!C)
     return SDValue();
-  uint64_t MulAmt = C->getZExtValue();
-  if (isPowerOf2_64(MulAmt) || MulAmt == 3 || MulAmt == 5 || MulAmt == 9)
+  APInt MulAmt = C->getAPIntValue();
+  if (MulAmt.isPowerOf2() || MulAmt == 3 || MulAmt == 5 || MulAmt == 9)
     return SDValue();
 
-  uint64_t MulAmt1 = 0;
-  uint64_t MulAmt2 = 0;
-  if ((MulAmt % 9) == 0) {
-    MulAmt1 = 9;
-    MulAmt2 = MulAmt / 9;
-  } else if ((MulAmt % 5) == 0) {
-    MulAmt1 = 5;
-    MulAmt2 = MulAmt / 5;
-  } else if ((MulAmt % 3) == 0) {
-    MulAmt1 = 3;
-    MulAmt2 = MulAmt / 3;
+  unsigned BitWidth = MulAmt.getBitWidth();
+  APInt KnownZero = APInt(BitWidth, 0);
+  APInt KnownThree = APInt(BitWidth, 3);
+  APInt KnownFive = APInt(BitWidth, 5);
+  APInt KnownNine = APInt(BitWidth, 9);
+
+  APInt MulAmt1 = KnownZero;
+  APInt MulAmt2 = KnownZero;
+  if (MulAmt.urem(KnownNine) == 0) {
+    MulAmt1 = KnownNine;
+    MulAmt2 = MulAmt.udiv(KnownNine);
+  } else if (MulAmt.urem(KnownFive) == 0) {
+    MulAmt1 = KnownFive;
+    MulAmt2 = MulAmt.udiv(KnownFive);
+  } else if (MulAmt.urem(KnownThree) == 0) {
+    MulAmt1 = KnownThree;
+    MulAmt2 = MulAmt.udiv(KnownThree);
   }
-  if (MulAmt2 &&
-      (isPowerOf2_64(MulAmt2) || MulAmt2 == 3 || MulAmt2 == 5 || MulAmt2 == 9)){
+  if (MulAmt2 != 0 &&
+      (MulAmt2.isPowerOf2() || MulAmt2 == 3 || MulAmt2 == 5 || MulAmt2 == 9)){
     SDLoc DL(N);
 
-    if (isPowerOf2_64(MulAmt2) &&
+    if (MulAmt2.isPowerOf2() &&
         !(N->hasOneUse() && N->use_begin()->getOpcode() == ISD::ADD))
       // If second multiplifer is pow2, issue it first. We want the multiply by
       // 3, 5, or 9 to be folded into the addressing mode unless the lone use
       // is an add.
       std::swap(MulAmt1, MulAmt2);
 
     SDValue NewMul;
-    if (isPowerOf2_64(MulAmt1))
+    if (MulAmt1.isPowerOf2())
       NewMul = DAG.getNode(ISD::SHL, DL, VT, N->getOperand(0),
-                           DAG.getConstant(Log2_64(MulAmt1), DL, MVT::i8));
+                           DAG.getConstant(MulAmt1.logBase2(), DL, MVT::i8));
     else
       NewMul = DAG.getNode(X86ISD::MUL_IMM, DL, VT, N->getOperand(0),
                            DAG.getConstant(MulAmt1, DL, VT));
 
-    if (isPowerOf2_64(MulAmt2))
+    if (MulAmt2.isPowerOf2())
       NewMul = DAG.getNode(ISD::SHL, DL, VT, NewMul,
-                           DAG.getConstant(Log2_64(MulAmt2), DL, MVT::i8));
+                           DAG.getConstant(MulAmt2.logBase2(), DL, MVT::i8));
     else
       NewMul = DAG.getNode(X86ISD::MUL_IMM, DL, VT, NewMul,
                            DAG.getConstant(MulAmt2, DL, VT));
 
     // Do not add new nodes to DAG combiner worklist.
     DCI.CombineTo(N, NewMul, false);
   }
   return SDValue();