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 unsigned P;
23 APInt AD, ANC, Delta, Q1, R1, Q2, R2, T;
24 APInt SignedMin = APInt::getSignedMinValue(D.getBitWidth());
25 struct SignedDivisionByConstantInfo Retval;
26
27 AD = D.abs();
28 T = SignedMin + (D.lshr(D.getBitWidth() - 1));
29 ANC = T - 1 - T.urem(AD); // absolute value of NC
30 P = D.getBitWidth() - 1; // initialize P
31 Q1 = SignedMin.udiv(ANC); // initialize Q1 = 2P/abs(NC)
32 R1 = SignedMin - Q1 * ANC; // initialize R1 = rem(2P,abs(NC))
33 Q2 = SignedMin.udiv(AD); // initialize Q2 = 2P/abs(D)
34 R2 = SignedMin - Q2 * AD; // initialize R2 = rem(2P,abs(D))
35 do {
36 P = P + 1;
37 Q1 = Q1 << 1; // update Q1 = 2P/abs(NC)
38 R1 = R1 << 1; // update R1 = rem(2P/abs(NC))
39 if (R1.uge(ANC)) { // must be unsigned comparison
40 Q1 = Q1 + 1;
41 R1 = R1 - ANC;
42 }
43 Q2 = Q2 << 1; // update Q2 = 2P/abs(D)
44 R2 = R2 << 1; // update R2 = rem(2P/abs(D))
45 if (R2.uge(AD)) { // must be unsigned comparison
46 Q2 = Q2 + 1;
47 R2 = R2 - AD;
48 }
49 Delta = AD - R2;
50 } while (Q1.ult(Delta) || (Q1 == Delta && R1 == 0));
51
52 Retval.Magic = Q2 + 1;
53 if (D.isNegative())
54 Retval.Magic = -Retval.Magic; // resulting magic number
55 Retval.ShiftAmount = P - D.getBitWidth(); // resulting shift
56 return Retval;
57 }
58
59 /// Calculate the magic numbers required to implement an unsigned integer
60 /// division by a constant as a sequence of multiplies, adds and shifts.
61 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
62 /// S. Warren, Jr., chapter 10.
63 /// LeadingZeros can be used to simplify the calculation if the upper bits
64 /// of the divided value are known zero.
65 UnsignedDivisionByConstantInfo
get(const APInt & D,unsigned LeadingZeros)66 UnsignedDivisionByConstantInfo::get(const APInt &D, unsigned LeadingZeros) {
67 unsigned P;
68 APInt NC, Delta, Q1, R1, Q2, R2;
69 struct UnsignedDivisionByConstantInfo Retval;
70 Retval.IsAdd = false; // initialize "add" indicator
71 APInt AllOnes = APInt::getAllOnes(D.getBitWidth()).lshr(LeadingZeros);
72 APInt SignedMin = APInt::getSignedMinValue(D.getBitWidth());
73 APInt SignedMax = APInt::getSignedMaxValue(D.getBitWidth());
74
75 NC = AllOnes - (AllOnes - D).urem(D);
76 P = D.getBitWidth() - 1; // initialize P
77 Q1 = SignedMin.udiv(NC); // initialize Q1 = 2P/NC
78 R1 = SignedMin - Q1 * NC; // initialize R1 = rem(2P,NC)
79 Q2 = SignedMax.udiv(D); // initialize Q2 = (2P-1)/D
80 R2 = SignedMax - Q2 * D; // initialize R2 = rem((2P-1),D)
81 do {
82 P = P + 1;
83 if (R1.uge(NC - R1)) {
84 Q1 = Q1 + Q1 + 1; // update Q1
85 R1 = R1 + R1 - NC; // update R1
86 } else {
87 Q1 = Q1 + Q1; // update Q1
88 R1 = R1 + R1; // update R1
89 }
90 if ((R2 + 1).uge(D - R2)) {
91 if (Q2.uge(SignedMax))
92 Retval.IsAdd = true;
93 Q2 = Q2 + Q2 + 1; // update Q2
94 R2 = R2 + R2 + 1 - D; // update R2
95 } else {
96 if (Q2.uge(SignedMin))
97 Retval.IsAdd = true;
98 Q2 = Q2 + Q2; // update Q2
99 R2 = R2 + R2 + 1; // update R2
100 }
101 Delta = D - 1 - R2;
102 } while (P < D.getBitWidth() * 2 &&
103 (Q1.ult(Delta) || (Q1 == Delta && R1 == 0)));
104 Retval.Magic = Q2 + 1; // resulting magic number
105 Retval.ShiftAmount = P - D.getBitWidth(); // resulting shift
106 return Retval;
107 }
108