[SelectionDAG][GlobalISel] Don't use UnsignedDivisionByConstantInfo for divisor of 1.

[craig.topper]

Summary

The magic algorithm returns IsAdd indication for division by constant
that we were ignoring.

I considered folding the ignore into UnsignedDivisionByConstantInfo,
but we only allow 1 for vectors of mixed visiors. And really what we
want to end up with is undef. Currently, we get to undef via
DemandedElts optimizations using the select instruction. We could
directly emit undef.

[lebedev.ri]

LG

llvm/unittests/Support/DivisionByConstantTest.cpp

172

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

MachineInstr *CombinerHelper::buildUDivUsingMul(MachineInstr &MI) {
   MIB.setInstrAndDebugLoc(MI);
 
   bool UseNPQ = false;
   SmallVector<Register, 16> PreShifts, PostShifts, MagicFactors, NPQFactors;
 
   auto BuildUDIVPattern = [&](const Constant *C) {
     auto *CI = cast<ConstantInt>(C);
     const APInt &Divisor = CI->getValue();
+
+    bool SelNPQ = false;
+    APInt Magic(Divisor.getBitWidth(), 0);
+    unsigned PreShift = 0, PostShift = 0;
+
+    // Magic algorithm doesn't work for division by 1. We need to emit a select
+    // at the end.
+    // TODO: Use undef values for divisor of 1.
+    if (!Divisor.isOneValue()) {
       UnsignedDivisionByConstantInfo magics =
           UnsignedDivisionByConstantInfo::get(Divisor);
-    unsigned PreShift = 0, PostShift = 0;
 
-    unsigned SelNPQ;
-    if (!magics.IsAdd || Divisor.isOneValue()) {
+      Magic = std::move(magics.Magic);
+
+      if (!magics.IsAdd) {
         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));
+    MagicFactors.push_back(MIB.buildConstant(ScalarTy, Magic).getReg(0));
     NPQFactors.push_back(
         MIB.buildConstant(ScalarTy,
                           SelNPQ ? APInt::getOneBitSet(EltBits, EltBits - 1)
                                  : APInt::getZero(EltBits))
             .getReg(0));
     PostShifts.push_back(
         MIB.buildConstant(ScalarShiftAmtTy, PostShift).getReg(0));
     UseNPQ |= SelNPQ;

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

SDValue TargetLowering::BuildUDIV(SDNode *N, SelectionDAG &DAG,
   SmallVector<SDValue, 16> PreShifts, PostShifts, MagicFactors, NPQFactors;
 
   auto BuildUDIVPattern = [&](ConstantSDNode *C) {
     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();
+
+    bool SelNPQ = false;
+    APInt Magic(Divisor.getBitWidth(), 0);
+    unsigned PreShift = 0, PostShift = 0;
+
+    // Magic algorithm doesn't work for division by 1. We need to emit a select
+    // at the end.
+    // TODO: Use undef values for divisor of 1.
+    if (!Divisor.isOne()) {
       UnsignedDivisionByConstantInfo magics =
           UnsignedDivisionByConstantInfo::get(Divisor, LeadingZeros);
-    unsigned PreShift = 0, PostShift = 0;
 
-    unsigned SelNPQ;
-    if (!magics.IsAdd || Divisor.isOne()) {
+      Magic = std::move(magics.Magic);
+
+      if (!magics.IsAdd) {
         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));
+    MagicFactors.push_back(DAG.getConstant(Magic, dl, SVT));
     NPQFactors.push_back(
         DAG.getConstant(SelNPQ ? APInt::getOneBitSet(EltBits, EltBits - 1)
                                : APInt::getZero(EltBits),
                         dl, SVT));
     PostShifts.push_back(DAG.getConstant(PostShift, dl, ShSVT));
     UseNPQ |= SelNPQ;
     return true;
   };

llvm/lib/Support/DivisionByConstantInfo.cpp

 /// 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,
                                     bool AllowEvenDivisorOptimization) {
-  assert(!D.isZero() && "Precondition violation.");
+  assert(!D.isZero() && !D.isOne() && "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());
   APInt SignedMax = APInt::getSignedMaxValue(D.getBitWidth());

llvm/unittests/Support/DivisionByConstantTest.cpp

APInt MULHU(APInt X, APInt Y) {
   unsigned WideBits = 2 * Bits;
   return (X.zext(WideBits) * Y.zext(WideBits)).lshr(Bits).trunc(Bits);
 }
 
 APInt UnsignedDivideUsingMagic(const APInt &Numerator, const APInt &Divisor,
                                bool LZOptimization,
                                bool AllowEvenDivisorOptimization, bool ForceNPQ,
                                UnsignedDivisionByConstantInfo Magics) {
+  assert(!Divisor.isOne() && "Division by 1 is not supported using Magic.");
+
   unsigned Bits = Numerator.getBitWidth();
 
-  if (LZOptimization && !Divisor.isOne()) {
+  if (LZOptimization) {
     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, AllowEvenDivisorOptimization);
       assert(!Magics.IsAdd && "Should use cheap fixup now");
     }
   }
 
   unsigned PreShift = 0;
   unsigned PostShift = 0;
   bool UseNPQ = false;
-  if (!Magics.IsAdd || Divisor.isOne()) {
+  if (!Magics.IsAdd) {
     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;
if (UseNPQ || ForceNPQ) {
     NPQ = MULHU(NPQ, NPQFactor);
     assert(!UseNPQ || NPQ == NPQ_Scalar);
 
     Q = NPQ + Q;
   }
 
   Q = Q.lshr(PostShift);
 
-  return Divisor.isOne() ? Numerator : Q;
+  return Q;
 }
 
 TEST(UnsignedDivisionByConstantTest, Test) {
   for (unsigned Bits = 1; Bits <= 32; ++Bits) {
     if (Bits < 2)
       continue; // Not supported by `UnsignedDivisionByConstantInfo::get()`.
     if (Bits > 10)
       continue; // Unreasonably slow.
     EnumerateAPInts(Bits, [Bits](const APInt &Divisor) {
       if (Divisor.isZero())
         return; // Division by zero is undefined behavior.
+      if (Divisor.isOne())
+        return; // Division by one is the numerator.
+
       const UnsignedDivisionByConstantInfo Magics =
           UnsignedDivisionByConstantInfo::get(Divisor);
       EnumerateAPInts(Bits, [Divisor, Magics, Bits](const APInt &Numerator) {
         APInt NativeResult = Numerator.udiv(Divisor);
         for (bool LZOptimization : {true, false}) {
           for (bool AllowEvenDivisorOptimization : {true, false}) {
             for (bool ForceNPQ : {false, true}) {
               APInt MagicResult = UnsignedDivideUsingMagic(