LLVM: lib/Support/DivisionByConstantInfo.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
14
15using namespace llvm;
16
17
18
19
20
22 assert(.isZero() && "Precondition violation.");
23
24
25 assert(D.getBitWidth() >= 3 && "Does not work at smaller bitwidths.");
26
30
32 APInt T = SignedMin + (D.lshr(D.getBitWidth() - 1));
33 APInt ANC = T - 1 - T.urem(AD);
34 unsigned P = D.getBitWidth() - 1;
36
38
40 do {
42 Q1 <<= 1;
43 R1 <<= 1;
44 if (R1.uge(ANC)) {
45 ++Q1;
46 R1 -= ANC;
47 }
48 Q2 <<= 1;
49 R2 <<= 1;
50 if (R2.uge(AD)) {
51 ++Q2;
52 R2 -= AD;
53 }
54
55 Delta = AD;
56 Delta -= R2;
57 } while (Q1.ult(Delta) || (Q1 == Delta && R1.isZero()));
58
59 Retval.Magic = std::move(Q2);
61 if (D.isNegative())
63 Retval.ShiftAmount = P - D.getBitWidth();
64 return Retval;
65}
66
67
68
69
70
71
72
75 bool AllowEvenDivisorOptimization) {
76 assert(.isZero() &&
.isOne() && "Precondition violation.");
77 assert(D.getBitWidth() > 1 && "Does not work at smaller bitwidths.");
78
81 Retval.IsAdd = false;
86
87
89 assert(NC.urem(D) == D - 1 && "Unexpected NC value");
90 unsigned P = D.getBitWidth() - 1;
92
94
96 do {
99
100 Q1 <<= 1;
101 ++Q1;
102
103 R1 <<= 1;
104 R1 -= NC;
105 } else {
106 Q1 <<= 1;
107 R1 <<= 1;
108 }
109 if ((R2 + 1).uge(D - R2)) {
110 if (Q2.uge(SignedMax))
111 Retval.IsAdd = true;
112
113 Q2 <<= 1;
114 ++Q2;
115
116 R2 <<= 1;
117 ++R2;
119 } else {
120 if (Q2.uge(SignedMin))
121 Retval.IsAdd = true;
122
123 Q2 <<= 1;
124
125 R2 <<= 1;
126 ++R2;
127 }
128
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 && [0] && AllowEvenDivisorOptimization) {
136 unsigned PreShift = D.countr_zero();
138 Retval =
142 return Retval;
143 }
144
145 Retval.Magic = std::move(Q2);
147 Retval.PostShift = P - D.getBitWidth();
148
149 if (Retval.IsAdd) {
152 }
154 return Retval;
155}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
Class for arbitrary precision integers.
static LLVM_ABI void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Dual division/remainder interface.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
void negate()
Negate this APInt in place.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
This is an optimization pass for GlobalISel generic memory operations.
Magic data for optimising signed division by a constant.
unsigned ShiftAmount
shift amount
static LLVM_ABI SignedDivisionByConstantInfo get(const APInt &D)
Calculate the magic numbers required to implement a signed integer division by a constant as a sequen...
Definition DivisionByConstantInfo.cpp:21
Magic data for optimising unsigned division by a constant.
unsigned PreShift
pre-shift amount
static LLVM_ABI UnsignedDivisionByConstantInfo get(const APInt &D, unsigned LeadingZeros=0, bool AllowEvenDivisorOptimization=true)
Calculate the magic numbers required to implement an unsigned integer division by a constant as a seq...
Definition DivisionByConstantInfo.cpp:74
unsigned PostShift
post-shift amount