LLVM 17.0.0git
DivisionByConstantInfo.cpp
Go to the documentation of this file.
1//===----- DivisionByConstantInfo.cpp - division by constant -*- C++ -*----===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
6//
7//===----------------------------------------------------------------------===//
8///
9/// This file implements support for optimizing divisions by a constant
10///
11//===----------------------------------------------------------------------===//
12
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.
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
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))
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;
53 }
54 // Delta = AD - R2
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.
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;
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))
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))
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 && AllowEvenDivisorOptimization) {
135 unsigned PreShift = D.countr_zero();
136 APInt ShiftedD = D.lshr(PreShift);
137 Retval =
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.
149 assert(Retval.PostShift > 0 && "Unexpected shift");
150 Retval.PostShift -= 1;
151 }
152 Retval.PreShift = 0;
153 return Retval;
154}
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
#define R2(n)
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Class for arbitrary precision integers.
Definition: APInt.h:75
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:214
static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Dual division/remainder interface.
Definition: APInt.cpp:1755
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition: APInt.h:366
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1093
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:189
void negate()
Negate this APInt in place.
Definition: APInt.h:1425
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:199
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:839
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1203
This is an optimization pass for GlobalISel generic memory operations.