llvm/lib/Support/DivisionByConstantInfo.cpp

   1 //===----- DivisionByConstantInfo.cpp - division by constant -*- C++ -*----===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 ///
   9 /// This file implements support for optimizing divisions by a constant
  10 ///
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/Support/DivisionByConstantInfo.h"
  14
  15 using namespace llvm;
  16
  17 /// Calculate the magic numbers required to implement a signed integer division
  18 /// by a constant as a sequence of multiplies, adds and shifts.  Requires that
  19 /// the divisor not be 0, 1, or -1.  Taken from "Hacker's Delight", Henry S.
  20 /// Warren, Jr., Chapter 10.
  21 SignedDivisionByConstantInfo SignedDivisionByConstantInfo::get(const APInt &D) {
  22   assert(!D.isZero() && "Precondition violation.");
  23
  24   // We'd be endlessly stuck in the loop.
  25   assert(D.getBitWidth() >= 3 && "Does not work at smaller bitwidths.");
  26
  27   APInt Delta;
  28   APInt SignedMin = APInt::getSignedMinValue(D.getBitWidth());
  29   struct SignedDivisionByConstantInfo Retval;
  30
  31   APInt AD = D.abs();
  32   APInt T = SignedMin + (D.lshr(D.getBitWidth() - 1));
  33   APInt ANC = T - 1 - T.urem(AD);   // absolute value of NC
  34   unsigned P = D.getBitWidth() - 1; // initialize P
  35   APInt Q1, R1, Q2, R2;
  36   // initialize Q1 = 2P/abs(NC); R1 = rem(2P,abs(NC))
  37   APInt::udivrem(SignedMin, ANC, Q1, R1);
  38   // initialize Q2 = 2P/abs(D); R2 = rem(2P,abs(D))
  39   APInt::udivrem(SignedMin, AD, Q2, R2);
  40   do {
  41     P = P + 1;
  42     Q1 <<= 1;      // update Q1 = 2P/abs(NC)
  43     R1 <<= 1;      // update R1 = rem(2P/abs(NC))
  44     if (R1.uge(ANC)) { // must be unsigned comparison
  45       ++Q1;
  46       R1 -= ANC;
  47     }
  48     Q2 <<= 1;     // update Q2 = 2P/abs(D)
  49     R2 <<= 1;     // update R2 = rem(2P/abs(D))
  50     if (R2.uge(AD)) { // must be unsigned comparison
  51       ++Q2;
  52       R2 -= AD;
  53     }
  54     // Delta = AD - R2
  55     Delta = AD;
  56     Delta -= R2;
  57   } while (Q1.ult(Delta) || (Q1 == Delta && R1.isZero()));
  58
  59   Retval.Magic = std::move(Q2);
  60   ++Retval.Magic;
  61   if (D.isNegative())
  62     Retval.Magic.negate();                  // resulting magic number
  63   Retval.ShiftAmount = P - D.getBitWidth(); // resulting shift
  64   return Retval;
  65 }
  66
  67 /// Calculate the magic numbers required to implement an unsigned integer
  68 /// division by a constant as a sequence of multiplies, adds and shifts.
  69 /// Requires that the divisor not be 0.  Taken from "Hacker's Delight", Henry
  70 /// S. Warren, Jr., chapter 10.
  71 /// LeadingZeros can be used to simplify the calculation if the upper bits
  72 /// of the divided value are known zero.
  73 UnsignedDivisionByConstantInfo
  74 UnsignedDivisionByConstantInfo::get(const APInt &D, unsigned LeadingZeros,
  75                                     bool AllowEvenDivisorOptimization) {
  76   assert(!D.isZero() && !D.isOne() && "Precondition violation.");
  77   assert(D.getBitWidth() > 1 && "Does not work at smaller bitwidths.");
  78
  79   APInt Delta;
  80   struct UnsignedDivisionByConstantInfo Retval;
  81   Retval.IsAdd = false; // initialize "add" indicator
  82   APInt AllOnes =
  83       APInt::getLowBitsSet(D.getBitWidth(), D.getBitWidth() - LeadingZeros);
  84   APInt SignedMin = APInt::getSignedMinValue(D.getBitWidth());
  85   APInt SignedMax = APInt::getSignedMaxValue(D.getBitWidth());
  86
  87   // Calculate NC, the largest dividend such that NC.urem(D) == D-1.
  88   APInt NC = AllOnes - (AllOnes + 1 - D).urem(D);
  89   assert(NC.urem(D) == D - 1 && "Unexpected NC value");
  90   unsigned P = D.getBitWidth() - 1; // initialize P
  91   APInt Q1, R1, Q2, R2;
  92   // initialize Q1 = 2P/NC; R1 = rem(2P,NC)
  93   APInt::udivrem(SignedMin, NC, Q1, R1);
  94   // initialize Q2 = (2P-1)/D; R2 = rem((2P-1),D)
  95   APInt::udivrem(SignedMax, D, Q2, R2);
  96   do {
  97     P = P + 1;
  98     if (R1.uge(NC - R1)) {
  99       // update Q1
 100       Q1 <<= 1;
 101       ++Q1;
 102       // update R1
 103       R1 <<= 1;
 104       R1 -= NC;
 105     } else {
 106       Q1 <<= 1; // update Q1
 107       R1 <<= 1; // update R1
 108     }
 109     if ((R2 + 1).uge(D - R2)) {
 110       if (Q2.uge(SignedMax))
 111         Retval.IsAdd = true;
 112       // update Q2
 113       Q2 <<= 1;
 114       ++Q2;
 115       // update R2
 116       R2 <<= 1;
 117       ++R2;
 118       R2 -= D;
 119     } else {
 120       if (Q2.uge(SignedMin))
 121         Retval.IsAdd = true;
 122       // update Q2
 123       Q2 <<= 1;
 124       // update R2
 125       R2 <<= 1;
 126       ++R2;
 127     }
 128     // Delta = D - 1 - R2
 129     Delta = D;
 130     --Delta;
 131     Delta -= R2;
 132   } while (P < D.getBitWidth() * 2 &&
 133            (Q1.ult(Delta) || (Q1 == Delta && R1.isZero())));
 134
 135   if (Retval.IsAdd && !D[0] && AllowEvenDivisorOptimization) {
 136     unsigned PreShift = D.countr_zero();
 137     APInt ShiftedD = D.lshr(PreShift);
 138     Retval =
 139         UnsignedDivisionByConstantInfo::get(ShiftedD, LeadingZeros + PreShift);
 140     assert(Retval.IsAdd == 0 && Retval.PreShift == 0);
 141     Retval.PreShift = PreShift;
 142     return Retval;
 143   }
 144
 145   Retval.Magic = std::move(Q2);             // resulting magic number
 146   ++Retval.Magic;
 147   Retval.PostShift = P - D.getBitWidth(); // resulting shift
 148   // Reduce shift amount for IsAdd.
 149   if (Retval.IsAdd) {
 150     assert(Retval.PostShift > 0 && "Unexpected shift");
 151     Retval.PostShift -= 1;
 152   }
 153   Retval.PreShift = 0;
 154   return Retval;
 155 }