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.
get(const APInt & D)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
get(const APInt & D,unsigned LeadingZeros,bool AllowEvenDivisorOptimization)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 = 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.countr_zero();
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