[NFC] Restore magic and magicu to a globally visible location

[ctetreau]

Summary

While these functions are only used in one location in upstream,
it has been reused in multiple downstreams. Restore this file to
a globally visibile location (outside of APInt.h) to eliminate
donwstream breakage and enable potential future reuse.

Additionally, this patch renames types and cleans up
clang-tidy issues.

[dsanders]

LGTM

[ctetreau]

I decided to create a new file in llvm/Support rather than take one of the suggestions in Chris's diff thread because:

• MathExtras.h - I didn't want to add a #include to APInt.h where there wasn't one already. Plus, that file is already pretty big, and most users of it don't need this.
• somewhere in lib/CodeGen - our usage in my downstream is in lib/Target, which I think demonstrates that this functionality is more broadly useful.

Given this, I think a new file in lib/Support is appropriate.

[bogner]

LGTM with a nitpick

llvm/include/llvm/Support/DivisionMagic.h

12 ↗

(On Diff #375973)

Please use the usual include guards (LLVM_SUPPORT_DIVISIONMAGIC_H etc)

[ctetreau]

llvm/include/llvm/Support/DivisionMagic.h

12 ↗

(On Diff #375973)

OMG, It's like I've never written C++ before! How embarrasing :(

[ctetreau]

add include guard

[lattner]

Cool, thank you for pulling this back, I'm sorry for the breakage. I think that adding this to its own header makes a lot of sense. While you're here, please rename the structs and functions. this shouldn't be called llvm::magic, the names should reference division by a constant somehow. Thanks!

[ctetreau]

address code review issues; clean up the interface

[craig.topper]

llvm/lib/Support/DivisionByConstantInfo.cpp

26

With the struct being renamed, a variable called mag no longer makes sense. It's not an obvious abbreviation for "magic" if "magic" doesn't appear anywhere.

70

Same here

[craig.topper]

llvm/include/llvm/Support/DivisionByConstantInfo.h

14

This doesn't match the file name.

[ctetreau]

address code review issues:

• fix include guard
• rename mag to Retval
• also, make all the variables PascalCase to silence clang-tidy

[lattner]

I love it, thank you!

[foad]

llvm/include/llvm/Support/DivisionByConstantInfo.h

1

Just a nit: do we need "Info" in the name? It seems odd in the filename, and I'm not even sure we need it in the struct names either.

[ctetreau]

llvm/include/llvm/Support/DivisionByConstantInfo.h

1

It's a bit verbose I agree, but I think it's a (barring abbreviations) minimally descriptive name. It's information about a division by a constant, not a division by a constant.

llvm/include/llvm/Support/DivisionByConstantInfo.h

+//== llvm/Support/DivisonByConstantInfo.h - division by constant -*- C++ -*-==//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+///
+/// This file implements support for optimizing divisions by a constant
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_DIVISON_BY_CONSTANT_INFO_H
+#define LLVM_SUPPORT_DIVISON_BY_CONSTANT_INFO_H
+
+#include "llvm/ADT/APInt.h"
+
+namespace llvm {
+
+/// Magic data for optimising signed division by a constant.
+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 UnsignedDivisonByConstantInfo {
+  static UnsignedDivisonByConstantInfo get(const APInt &D,
+                                           unsigned LeadingZeros = 0);
+  APInt Magic;          ///< magic number
+  bool IsAdd;           ///< add indicator
+  unsigned ShiftAmount; ///< shift amount
+};
+
+} // namespace llvm
+
+#endif

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

 //===-- TargetLowering.cpp - Implement the TargetLowering class -----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //

 #include "llvm/CodeGen/TargetRegisterInfo.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCExpr.h"
+#include "llvm/Support/DivisionByConstantInfo.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/KnownBits.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Target/TargetLoweringObjectFile.h"
 #include "llvm/Target/TargetMachine.h"
 #include <cctype>
 using namespace llvm;
 
SDValue TargetLowering::BuildSDIVPow2(SDNode *N, const APInt &Divisor,
                               SmallVectorImpl<SDNode *> &Created) const {
   AttributeList Attr = DAG.getMachineFunction().getFunction().getAttributes();
   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
   if (TLI.isIntDivCheap(N->getValueType(0), Attr))
     return SDValue(N, 0); // Lower SDIV as SDIV
   return SDValue();
 }
 
-namespace {
-/// Magic data for optimising signed division by a constant.
-struct ms {
-  APInt m;    ///< magic number
-  unsigned s; ///< shift amount
-};
-
-/// Magic data for optimising unsigned division by a constant.
-struct mu {
-  APInt m;    ///< magic number
-  bool a;     ///< add indicator
-  unsigned s; ///< shift amount
-};
-} // namespace
-
-/// 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.
-static mu magicu(const APInt &d, unsigned LeadingZeros = 0) {
-  unsigned p;
-  APInt nc, delta, q1, r1, q2, r2;
-  struct mu magu;
-  magu.a = 0; // initialize "add" indicator
-  APInt allOnes = APInt::getAllOnes(d.getBitWidth()).lshr(LeadingZeros);
-  APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
-  APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
-
-  nc = allOnes - (allOnes - d).urem(d);
-  p = d.getBitWidth() - 1;  // initialize p
-  q1 = signedMin.udiv(nc);  // initialize q1 = 2p/nc
-  r1 = signedMin - q1 * nc; // initialize r1 = rem(2p,nc)
-  q2 = signedMax.udiv(d);   // initialize q2 = (2p-1)/d
-  r2 = signedMax - q2 * d;  // initialize r2 = rem((2p-1),d)
-  do {
-    p = p + 1;
-    if (r1.uge(nc - r1)) {
-      q1 = q1 + q1 + 1;  // update q1
-      r1 = r1 + r1 - nc; // update r1
-    } else {
-      q1 = q1 + q1; // update q1
-      r1 = r1 + r1; // update r1
-    }
-    if ((r2 + 1).uge(d - r2)) {
-      if (q2.uge(signedMax))
-        magu.a = 1;
-      q2 = q2 + q2 + 1;     // update q2
-      r2 = r2 + r2 + 1 - d; // update r2
-    } else {
-      if (q2.uge(signedMin))
-        magu.a = 1;
-      q2 = q2 + q2;     // update q2
-      r2 = r2 + r2 + 1; // update r2
-    }
-    delta = d - 1 - r2;
-  } while (p < d.getBitWidth() * 2 &&
-           (q1.ult(delta) || (q1 == delta && r1 == 0)));
-  magu.m = q2 + 1;              // resulting magic number
-  magu.s = p - d.getBitWidth(); // resulting shift
-  return magu;
-}
-
-/// Calculate the magic numbers required to implement a signed integer division
-/// by a constant as a sequence of multiplies, adds and shifts.  Requires that
-/// the divisor not be 0, 1, or -1.  Taken from "Hacker's Delight", Henry S.
-/// Warren, Jr., Chapter 10.
-static ms magic(const APInt &d) {
-  unsigned p;
-  APInt ad, anc, delta, q1, r1, q2, r2, t;
-  APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
-  struct ms mag;
-
-  ad = d.abs();
-  t = signedMin + (d.lshr(d.getBitWidth() - 1));
-  anc = t - 1 - t.urem(ad);  // absolute value of nc
-  p = d.getBitWidth() - 1;   // initialize p
-  q1 = signedMin.udiv(anc);  // initialize q1 = 2p/abs(nc)
-  r1 = signedMin - q1 * anc; // initialize r1 = rem(2p,abs(nc))
-  q2 = signedMin.udiv(ad);   // initialize q2 = 2p/abs(d)
-  r2 = signedMin - q2 * ad;  // initialize r2 = rem(2p,abs(d))
-  do {
-    p = p + 1;
-    q1 = q1 << 1;      // update q1 = 2p/abs(nc)
-    r1 = r1 << 1;      // update r1 = rem(2p/abs(nc))
-    if (r1.uge(anc)) { // must be unsigned comparison
-      q1 = q1 + 1;
-      r1 = r1 - anc;
-    }
-    q2 = q2 << 1;     // update q2 = 2p/abs(d)
-    r2 = r2 << 1;     // update r2 = rem(2p/abs(d))
-    if (r2.uge(ad)) { // must be unsigned comparison
-      q2 = q2 + 1;
-      r2 = r2 - ad;
-    }
-    delta = ad - r2;
-  } while (q1.ult(delta) || (q1 == delta && r1 == 0));
-
-  mag.m = q2 + 1;
-  if (d.isNegative())
-    mag.m = -mag.m;            // resulting magic number
-  mag.s = p - d.getBitWidth(); // resulting shift
-  return mag;
-}
-
 /// Given an ISD::SDIV node expressing a divide by constant,
 /// return a DAG expression to select that will generate the same value by
 /// multiplying by a magic number.
 /// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide".
 SDValue TargetLowering::BuildSDIV(SDNode *N, SelectionDAG &DAG,
                                   bool IsAfterLegalization,
                                   SmallVectorImpl<SDNode *> &Created) const {
   SDLoc dl(N);
SDValue TargetLowering::BuildSDIV(SDNode *N, SelectionDAG &DAG,
 
   SmallVector<SDValue, 16> MagicFactors, Factors, Shifts, ShiftMasks;
 
   auto BuildSDIVPattern = [&](ConstantSDNode *C) {
     if (C->isZero())
       return false;
 
     const APInt &Divisor = C->getAPIntValue();
-    ms magics = magic(Divisor);
+    SignedDivisionByConstantInfo magics = SignedDivisionByConstantInfo::get(Divisor);
     int NumeratorFactor = 0;
     int ShiftMask = -1;
 
     if (Divisor.isOneValue() || Divisor.isAllOnes()) {
       // If d is +1/-1, we just multiply the numerator by +1/-1.
       NumeratorFactor = Divisor.getSExtValue();
-      magics.m = 0;
-      magics.s = 0;
+      magics.Magic = 0;
+      magics.ShiftAmount = 0;
       ShiftMask = 0;
-    } else if (Divisor.isStrictlyPositive() && magics.m.isNegative()) {
+    } else if (Divisor.isStrictlyPositive() && magics.Magic.isNegative()) {
       // If d > 0 and m < 0, add the numerator.
       NumeratorFactor = 1;
-    } else if (Divisor.isNegative() && magics.m.isStrictlyPositive()) {
+    } else if (Divisor.isNegative() && magics.Magic.isStrictlyPositive()) {
       // If d < 0 and m > 0, subtract the numerator.
       NumeratorFactor = -1;
     }
 
-    MagicFactors.push_back(DAG.getConstant(magics.m, dl, SVT));
+    MagicFactors.push_back(DAG.getConstant(magics.Magic, dl, SVT));
     Factors.push_back(DAG.getConstant(NumeratorFactor, dl, SVT));
-    Shifts.push_back(DAG.getConstant(magics.s, dl, ShSVT));
+    Shifts.push_back(DAG.getConstant(magics.ShiftAmount, dl, ShSVT));
     ShiftMasks.push_back(DAG.getConstant(ShiftMask, dl, SVT));
     return true;
   };
 
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
 
   // Collect the shifts / magic values from each element.
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();
-    mu magics = magicu(Divisor);
+    UnsignedDivisonByConstantInfo magics = UnsignedDivisonByConstantInfo::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.a != 0 && !Divisor[0]) {
+    if (magics.IsAdd != 0 && !Divisor[0]) {
       PreShift = Divisor.countTrailingZeros();
       // Get magic number for the shifted divisor.
-      magics = magicu(Divisor.lshr(PreShift), PreShift);
-      assert(magics.a == 0 && "Should use cheap fixup now");
+      magics = UnsignedDivisonByConstantInfo::get(Divisor.lshr(PreShift), PreShift);
+      assert(magics.IsAdd == 0 && "Should use cheap fixup now");
     }
 
-    APInt Magic = magics.m;
+    APInt Magic = magics.Magic;
 
     unsigned SelNPQ;
-    if (magics.a == 0 || Divisor.isOneValue()) {
-      assert(magics.s < Divisor.getBitWidth() &&
+    if (magics.IsAdd == 0 || Divisor.isOneValue()) {
+      assert(magics.ShiftAmount < Divisor.getBitWidth() &&
              "We shouldn't generate an undefined shift!");
-      PostShift = magics.s;
+      PostShift = magics.ShiftAmount;
       SelNPQ = false;
     } else {
-      PostShift = magics.s - 1;
+      PostShift = magics.ShiftAmount - 1;
       SelNPQ = true;
     }
 
     PreShifts.push_back(DAG.getConstant(PreShift, dl, ShSVT));
     MagicFactors.push_back(DAG.getConstant(Magic, dl, SVT));
     NPQFactors.push_back(
         DAG.getConstant(SelNPQ ? APInt::getOneBitSet(EltBits, EltBits - 1)
                                : APInt::getZero(EltBits),

llvm/lib/Support/CMakeLists.txt

add_llvm_component_library(LLVMSupport
   CRC.cpp
   ConvertUTF.cpp
   ConvertUTFWrapper.cpp
   CrashRecoveryContext.cpp
   DataExtractor.cpp
   Debug.cpp
   DebugCounter.cpp
   DeltaAlgorithm.cpp
+  DivisionByConstantInfo.cpp
   DAGDeltaAlgorithm.cpp
   DJB.cpp
   ELFAttributeParser.cpp
   ELFAttributes.cpp
   Error.cpp
   ErrorHandling.cpp
   ExtensibleRTTI.cpp
   FileCollector.cpp

llvm/lib/Support/DivisionByConstantInfo.cpp

+//===----- DivisonByConstantInfo.cpp - division by constant -*- C++ -*-----===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+///
+/// This file implements support for optimizing divisions by a constant
+///
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/DivisionByConstantInfo.h"
+
+using namespace llvm;
+
+/// Calculate the magic numbers required to implement a signed integer division
+/// by a constant as a sequence of multiplies, adds and shifts.  Requires that
+/// the divisor not be 0, 1, or -1.  Taken from "Hacker's Delight", Henry S.
+/// Warren, Jr., Chapter 10.
+SignedDivisionByConstantInfo SignedDivisionByConstantInfo::get(const APInt &D) {
+  unsigned P;
+  APInt AD, ANC, Delta, Q1, R1, Q2, R2, T;
+  APInt SignedMin = APInt::getSignedMinValue(D.getBitWidth());
+  struct SignedDivisionByConstantInfo Retval;
+
+  AD = D.abs();
+  T = SignedMin + (D.lshr(D.getBitWidth() - 1));
+  ANC = T - 1 - T.urem(AD);  // absolute value of NC
+  P = D.getBitWidth() - 1;   // initialize P
+  Q1 = SignedMin.udiv(ANC);  // initialize Q1 = 2P/abs(NC)
+  R1 = SignedMin - Q1 * ANC; // initialize R1 = rem(2P,abs(NC))
+  Q2 = SignedMin.udiv(AD);   // initialize Q2 = 2P/abs(D)
+  R2 = SignedMin - Q2 * AD;  // initialize R2 = rem(2P,abs(D))
+  do {
+    P = P + 1;
+    Q1 = Q1 << 1;      // update Q1 = 2P/abs(NC)
+    R1 = R1 << 1;      // update R1 = rem(2P/abs(NC))
+    if (R1.uge(ANC)) { // must be unsigned comparison
+      Q1 = Q1 + 1;
+      R1 = R1 - ANC;
+    }
+    Q2 = Q2 << 1;     // update Q2 = 2P/abs(D)
+    R2 = R2 << 1;     // update R2 = rem(2P/abs(D))
+    if (R2.uge(AD)) { // must be unsigned comparison
+      Q2 = Q2 + 1;
+      R2 = R2 - AD;
+    }
+    Delta = AD - R2;
+  } while (Q1.ult(Delta) || (Q1 == Delta && R1 == 0));
+
+  Retval.Magic = Q2 + 1;
+  if (D.isNegative())
+    Retval.Magic = -Retval.Magic;              // resulting magic number
+  Retval.ShiftAmount = P - D.getBitWidth(); // resulting shift
+  return Retval;
+}
+
+/// 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.
+UnsignedDivisonByConstantInfo
+UnsignedDivisonByConstantInfo::get(const APInt &D, unsigned LeadingZeros = 0) {
+  unsigned P;
+  APInt NC, Delta, Q1, R1, Q2, R2;
+  struct UnsignedDivisonByConstantInfo Retval;
+  Retval.IsAdd = 0; // initialize "add" indicator
+  APInt AllOnes = APInt::getAllOnes(D.getBitWidth()).lshr(LeadingZeros);
+  APInt SignedMin = APInt::getSignedMinValue(D.getBitWidth());
+  APInt SignedMax = APInt::getSignedMaxValue(D.getBitWidth());
+
+  NC = AllOnes - (AllOnes - D).urem(D);
+  P = D.getBitWidth() - 1;  // initialize P
+  Q1 = SignedMin.udiv(NC);  // initialize Q1 = 2P/NC
+  R1 = SignedMin - Q1 * NC; // initialize R1 = rem(2P,NC)
+  Q2 = SignedMax.udiv(D);   // initialize Q2 = (2P-1)/D
+  R2 = SignedMax - Q2 * D;  // initialize R2 = rem((2P-1),D)
+  do {
+    P = P + 1;
+    if (R1.uge(NC - R1)) {
+      Q1 = Q1 + Q1 + 1;  // update Q1
+      R1 = R1 + R1 - NC; // update R1
+    } else {
+      Q1 = Q1 + Q1; // update Q1
+      R1 = R1 + R1; // update R1
+    }
+    if ((R2 + 1).uge(D - R2)) {
+      if (Q2.uge(SignedMax))
+        Retval.IsAdd = 1;
+      Q2 = Q2 + Q2 + 1;     // update Q2
+      R2 = R2 + R2 + 1 - D; // update R2
+    } else {
+      if (Q2.uge(SignedMin))
+        Retval.IsAdd = 1;
+      Q2 = Q2 + Q2;     // update Q2
+      R2 = R2 + R2 + 1; // update R2
+    }
+    Delta = D - 1 - R2;
+  } while (P < D.getBitWidth() * 2 &&
+           (Q1.ult(Delta) || (Q1 == Delta && R1 == 0)));
+  Retval.Magic = Q2 + 1;                    // resulting magic number
+  Retval.ShiftAmount = P - D.getBitWidth(); // resulting shift
+  return Retval;
+}