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
15using 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.
21SignedDivisionByConstantInfo 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.
73UnsignedDivisionByConstantInfo
74UnsignedDivisionByConstantInfo::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 = APInt::getAllOnes(D.getBitWidth()).lshr(LeadingZeros);
83  APInt SignedMin = APInt::getSignedMinValue(D.getBitWidth());
84  APInt SignedMax = APInt::getSignedMaxValue(D.getBitWidth());
85
86  // Calculate NC, the largest dividend such that NC.urem(D) == D-1.
87  APInt NC = AllOnes - (AllOnes + 1 - D).urem(D);
88  assert(NC.urem(D) == D - 1 && "Unexpected NC value");
89  unsigned P = D.getBitWidth() - 1; // initialize P
90  APInt Q1, R1, Q2, R2;
91  // initialize Q1 = 2P/NC; R1 = rem(2P,NC)
92  APInt::udivrem(SignedMin, NC, Q1, R1);
93  // initialize Q2 = (2P-1)/D; R2 = rem((2P-1),D)
94  APInt::udivrem(SignedMax, D, Q2, R2);
95  do {
96    P = P + 1;
97    if (R1.uge(NC - R1)) {
98      // update Q1
99      Q1 <<= 1;
100      ++Q1;
101      // update R1
102      R1 <<= 1;
103      R1 -= NC;
104    } else {
105      Q1 <<= 1; // update Q1
106      R1 <<= 1; // update R1
107    }
108    if ((R2 + 1).uge(D - R2)) {
109      if (Q2.uge(SignedMax))
110        Retval.IsAdd = true;
111      // update Q2
112      Q2 <<= 1;
113      ++Q2;
114      // update R2
115      R2 <<= 1;
116      ++R2;
117      R2 -= D;
118    } else {
119      if (Q2.uge(SignedMin))
120        Retval.IsAdd = true;
121      // update Q2
122      Q2 <<= 1;
123      // update R2
124      R2 <<= 1;
125      ++R2;
126    }
127    // Delta = D - 1 - R2
128    Delta = D;
129    --Delta;
130    Delta -= R2;
131  } while (P < D.getBitWidth() * 2 &&
132           (Q1.ult(Delta) || (Q1 == Delta && R1.isZero())));
133
134  if (Retval.IsAdd && !D[0] && AllowEvenDivisorOptimization) {
135    unsigned PreShift = D.countTrailingZeros();
136    APInt ShiftedD = D.lshr(PreShift);
137    Retval =
138        UnsignedDivisionByConstantInfo::get(ShiftedD, LeadingZeros + PreShift);
139    assert(Retval.IsAdd == 0 && Retval.PreShift == 0);
140    Retval.PreShift = PreShift;
141    return Retval;
142  }
143
144  Retval.Magic = std::move(Q2);             // resulting magic number
145  ++Retval.Magic;
146  Retval.PostShift = P - D.getBitWidth(); // resulting shift
147  // Reduce shift amount for IsAdd.
148  if (Retval.IsAdd) {
149    assert(Retval.PostShift > 0 && "Unexpected shift");
150    Retval.PostShift -= 1;
151  }
152  Retval.PreShift = 0;
153  return Retval;
154}
155