[SelectionDAG][GlobalISel] Move even divisor optimization for division by constant into UnsignedDivideUsingMagic implementation. NFC

[craig.topper]

Summary

I've added a bool to UnsignedDivideUsingMagic so we can continue
testing it in the unit test with and without this optimization in
the unit test.

This is a step towards supporting "uncooperative" odd divisors.
See https://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html

[lebedev.ri]

Nice cleanup!
Looks good to me.
Thanks.

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

4965

While we are around, can we perhaps give NPQ a more understandable name, or at least a comment somewhere as to what it stands for?

llvm/include/llvm/Support/DivisionByConstantInfo.h

 struct SignedDivisionByConstantInfo {
   static SignedDivisionByConstantInfo get(const APInt &D);
   APInt Magic;          ///< magic number
   unsigned ShiftAmount; ///< shift amount
 };
 
 /// Magic data for optimising unsigned division by a constant.
 struct UnsignedDivisionByConstantInfo {
-  static UnsignedDivisionByConstantInfo get(const APInt &D,
-                                            unsigned LeadingZeros = 0);
+  static UnsignedDivisionByConstantInfo
+  get(const APInt &D, unsigned LeadingZeros = 0,
+      bool AllowEvenDivisorOptimization = true);
   APInt Magic;          ///< magic number
   bool IsAdd;           ///< add indicator
   unsigned ShiftAmount; ///< shift amount
+  unsigned PreShift;    ///< pre-shift amount
 };
 
 } // namespace llvm
 
 #endif

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

MachineInstr *CombinerHelper::buildUDivUsingMul(MachineInstr &MI) {
 
   auto BuildUDIVPattern = [&](const Constant *C) {
     auto *CI = cast<ConstantInt>(C);
     const APInt &Divisor = CI->getValue();
     UnsignedDivisionByConstantInfo magics =
         UnsignedDivisionByConstantInfo::get(Divisor);
     unsigned PreShift = 0, PostShift = 0;
 
-    // If the divisor is even, we can avoid using the expensive fixup by
-    // shifting the divided value upfront.
-    if (magics.IsAdd && !Divisor[0]) {
-      PreShift = Divisor.countTrailingZeros();
-      // Get magic number for the shifted divisor.
-      magics =
-          UnsignedDivisionByConstantInfo::get(Divisor.lshr(PreShift), PreShift);
-      assert(!magics.IsAdd && "Should use cheap fixup now");
-    }
-
     unsigned SelNPQ;
     if (!magics.IsAdd || Divisor.isOneValue()) {
       assert(magics.ShiftAmount < Divisor.getBitWidth() &&
              "We shouldn't generate an undefined shift!");
       PostShift = magics.ShiftAmount;
+      PreShift = magics.PreShift;
       SelNPQ = false;
     } else {
+      assert(magics.PreShift == 0 && "Unexpected pre-shift");
       PostShift = magics.ShiftAmount - 1;
       SelNPQ = true;
     }
 
     PreShifts.push_back(
         MIB.buildConstant(ScalarShiftAmtTy, PreShift).getReg(0));
     MagicFactors.push_back(MIB.buildConstant(ScalarTy, magics.Magic).getReg(0));
     NPQFactors.push_back(

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

if (C->isZero())
       return false;
     // FIXME: We should use a narrower constant when the upper
     // bits are known to be zero.
     const APInt& Divisor = C->getAPIntValue();
     UnsignedDivisionByConstantInfo magics =
         UnsignedDivisionByConstantInfo::get(Divisor, LeadingZeros);
     unsigned PreShift = 0, PostShift = 0;
 
-    // If the divisor is even, we can avoid using the expensive fixup by
-    // shifting the divided value upfront.
-    if (magics.IsAdd && !Divisor[0]) {
-      PreShift = Divisor.countTrailingZeros();
-      // Get magic number for the shifted divisor.
-      magics = UnsignedDivisionByConstantInfo::get(Divisor.lshr(PreShift),
-                                                   PreShift + LeadingZeros);
-      assert(!magics.IsAdd && "Should use cheap fixup now");
-    }
-
     unsigned SelNPQ;
     if (!magics.IsAdd || Divisor.isOne()) {
       assert(magics.ShiftAmount < Divisor.getBitWidth() &&
              "We shouldn't generate an undefined shift!");
       PostShift = magics.ShiftAmount;
+      PreShift = magics.PreShift;
       SelNPQ = false;
     } else {
+      assert(magics.PreShift == 0 && "Unexpected pre-shift");
       PostShift = magics.ShiftAmount - 1;
       SelNPQ = true;
     }
 
     PreShifts.push_back(DAG.getConstant(PreShift, dl, ShSVT));
     MagicFactors.push_back(DAG.getConstant(magics.Magic, dl, SVT));
     NPQFactors.push_back(
         DAG.getConstant(SelNPQ ? APInt::getOneBitSet(EltBits, EltBits - 1)

llvm/lib/Support/DivisionByConstantInfo.cpp

 
 /// Calculate the magic numbers required to implement an unsigned integer
 /// division by a constant as a sequence of multiplies, adds and shifts.
 /// Requires that the divisor not be 0.  Taken from "Hacker's Delight", Henry
 /// S. Warren, Jr., chapter 10.
 /// LeadingZeros can be used to simplify the calculation if the upper bits
 /// of the divided value are known zero.
 UnsignedDivisionByConstantInfo
-UnsignedDivisionByConstantInfo::get(const APInt &D, unsigned LeadingZeros) {
+UnsignedDivisionByConstantInfo::get(const APInt &D, unsigned LeadingZeros,
+                                    bool AllowEvenDivisorOptimization) {
   assert(!D.isZero() && "Precondition violation.");
   assert(D.getBitWidth() > 1 && "Does not work at smaller bitwidths.");
 
   APInt Delta;
   struct UnsignedDivisionByConstantInfo Retval;
   Retval.IsAdd = false; // initialize "add" indicator
   APInt AllOnes = APInt::getAllOnes(D.getBitWidth()).lshr(LeadingZeros);
   APInt SignedMin = APInt::getSignedMinValue(D.getBitWidth());
if ((R2 + 1).uge(D - R2)) {
       ++R2;
     }
     // Delta = D - 1 - R2
     Delta = D;
     --Delta;
     Delta -= R2;
   } while (P < D.getBitWidth() * 2 &&
            (Q1.ult(Delta) || (Q1 == Delta && R1.isZero())));
+
+  if (Retval.IsAdd && !D[0] && AllowEvenDivisorOptimization) {
+    unsigned PreShift = D.countTrailingZeros();
+    APInt ShiftedD = D.lshr(PreShift);
+    Retval =
+        UnsignedDivisionByConstantInfo::get(ShiftedD, LeadingZeros + PreShift);
+    assert(Retval.IsAdd == 0 && Retval.PreShift == 0);
+    Retval.PreShift = PreShift;
+    return Retval;
+  }
+
   Retval.Magic = std::move(Q2);             // resulting magic number
   ++Retval.Magic;
   Retval.ShiftAmount = P - D.getBitWidth(); // resulting shift
+  Retval.PreShift = 0;
   return Retval;
 }

llvm/unittests/Support/DivisionByConstantTest.cpp

APInt UnsignedDivideUsingMagic(const APInt &Numerator, const APInt &Divisor,
                                UnsignedDivisionByConstantInfo Magics) {
   unsigned Bits = Numerator.getBitWidth();
 
   if (LZOptimization && !Divisor.isOne()) {
     unsigned LeadingZeros = Numerator.countLeadingZeros();
     // Clip to the number of leading zeros in the divisor.
     LeadingZeros = std::min(LeadingZeros, Divisor.countLeadingZeros());
     if (LeadingZeros > 0) {
-      Magics = UnsignedDivisionByConstantInfo::get(Divisor, LeadingZeros);
+      Magics = UnsignedDivisionByConstantInfo::get(
+          Divisor, LeadingZeros, AllowEvenDivisorOptimization);
       assert(!Magics.IsAdd && "Should use cheap fixup now");
     }
   }
 
   unsigned PreShift = 0;
-  if (AllowEvenDivisorOptimization) {
-    // If the divisor is even, we can avoid using the expensive fixup by
-    // shifting the divided value upfront.
-    if (Magics.IsAdd && !Divisor[0]) {
-      PreShift = Divisor.countTrailingZeros();
-      // Get magic number for the shifted divisor.
-      Magics =
-          UnsignedDivisionByConstantInfo::get(Divisor.lshr(PreShift), PreShift);
-      assert(!Magics.IsAdd && "Should use cheap fixup now");
-    }
-  }
-
   unsigned PostShift = 0;
   bool UseNPQ = false;
   if (!Magics.IsAdd || Divisor.isOne()) {
     assert(Magics.ShiftAmount < Divisor.getBitWidth() &&
            "We shouldn't generate an undefined shift!");
+    PreShift = Magics.PreShift;
     PostShift = Magics.ShiftAmount;
     UseNPQ = false;
   } else {
+    assert(Magics.PreShift == 0 && "Unexpected pre-shift");
     PostShift = Magics.ShiftAmount - 1;
     assert(PostShift < Divisor.getBitWidth() &&
            "We shouldn't generate an undefined shift!");
     UseNPQ = true;
   }
 
   APInt NPQFactor =
       UseNPQ ? APInt::getSignedMinValue(Bits) : APInt::getZero(Bits);