diff --git a/llvm/include/llvm/Support/DivisionByConstantInfo.h b/llvm/include/llvm/Support/DivisionByConstantInfo.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Support/DivisionByConstantInfo.h @@ -0,0 +1,38 @@ +//== 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 diff --git a/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp b/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp --- a/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp @@ -26,6 +26,7 @@ #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" @@ -5121,112 +5122,6 @@ 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. @@ -5271,27 +5166,27 @@ 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; }; @@ -5417,28 +5312,28 @@ // 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; } diff --git a/llvm/lib/Support/CMakeLists.txt b/llvm/lib/Support/CMakeLists.txt --- a/llvm/lib/Support/CMakeLists.txt +++ b/llvm/lib/Support/CMakeLists.txt @@ -137,6 +137,7 @@ Debug.cpp DebugCounter.cpp DeltaAlgorithm.cpp + DivisionByConstantInfo.cpp DAGDeltaAlgorithm.cpp DJB.cpp ELFAttributeParser.cpp diff --git a/llvm/lib/Support/DivisionByConstantInfo.cpp b/llvm/lib/Support/DivisionByConstantInfo.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Support/DivisionByConstantInfo.cpp @@ -0,0 +1,107 @@ +//===----- 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; +}