19 /// the divisor not be 0, 1, or -1.  Taken from "Hacker's Delight", Henry S.
21 SignedDivisionByConstantInfo SignedDivisionByConstantInfo::get(const APInt &D) {  in get()  argument
22   assert(!D.isZero() && "Precondition violation.");  in get()
24   // We'd be endlessly stuck in the loop.  in get()
25   assert(D.getBitWidth() >= 3 && "Does not work at smaller bitwidths.");  in get()
28   APInt SignedMin = APInt::getSignedMinValue(D.getBitWidth());  in get()
31   APInt AD = D.abs();  in get()
32   APInt T = SignedMin + (D.lshr(D.getBitWidth() - 1));  in get()
33   APInt ANC = T - 1 - T.urem(AD);   // absolute value of NC  in get()
34   unsigned P = D.getBitWidth() - 1; // initialize P  in get()
38   // initialize Q2 = 2P/abs(D); R2 = rem(2P,abs(D))  in get()
41     P = P + 1;  in get()
42     Q1 <<= 1;      // update Q1 = 2P/abs(NC)  in get()
43     R1 <<= 1;      // update R1 = rem(2P/abs(NC))  in get()
48     Q2 <<= 1;     // update Q2 = 2P/abs(D)  in get()
49     R2 <<= 1;     // update R2 = rem(2P/abs(D))  in get()
61   if (D.isNegative())  in get()
63   Retval.ShiftAmount = P - D.getBitWidth(); // resulting shift  in get()
74 UnsignedDivisionByConstantInfo::get(const APInt &D, unsigned LeadingZeros,  in get()  argument
76   assert(!D.isZero() && !D.isOne() && "Precondition violation.");  in get()
77   assert(D.getBitWidth() > 1 && "Does not work at smaller bitwidths.");  in get()
83       APInt::getLowBitsSet(D.getBitWidth(), D.getBitWidth() - LeadingZeros);  in get()
84   APInt SignedMin = APInt::getSignedMinValue(D.getBitWidth());  in get()
85   APInt SignedMax = APInt::getSignedMaxValue(D.getBitWidth());  in get()
87   // Calculate NC, the largest dividend such that NC.urem(D) == D-1.  in get()
88   APInt NC = AllOnes - (AllOnes + 1 - D).urem(D);  in get()
89   assert(NC.urem(D) == D - 1 && "Unexpected NC value");  in get()
90   unsigned P = D.getBitWidth() - 1; // initialize P  in get()
94   // initialize Q2 = (2P-1)/D; R2 = rem((2P-1),D)  in get()
95   APInt::udivrem(SignedMax, D, Q2, R2);  in get()
97     P = P + 1;  in get()
100       Q1 <<= 1;  in get()
103       R1 <<= 1;  in get()
106       Q1 <<= 1; // update Q1  in get()
107       R1 <<= 1; // update R1  in get()
109     if ((R2 + 1).uge(D - R2)) {  in get()
113       Q2 <<= 1;  in get()
116       R2 <<= 1;  in get()
118       R2 -= D;  in get()
123       Q2 <<= 1;  in get()
125       R2 <<= 1;  in get()
128     // Delta = D - 1 - R2  in get()
129     Delta = D;  in get()
132   } while (P < D.getBitWidth() * 2 &&  in get()
135   if (Retval.IsAdd && !D[0] && AllowEvenDivisorOptimization) {  in get()
136     unsigned PreShift = D.countr_zero();  in get()
137     APInt ShiftedD = D.lshr(PreShift);  in get()
147   Retval.PostShift = P - D.getBitWidth(); // resulting shift  in get()
151     Retval.PostShift -= 1;  in get()