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
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.
21SignedDivisionByConstantInfo 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(numBits: D.getBitWidth());
29 struct SignedDivisionByConstantInfo Retval;
30
31 APInt AD = D.abs();
32 APInt T = SignedMin + (D.lshr(shiftAmt: D.getBitWidth() - 1));
33 APInt ANC = T - 1 - T.urem(RHS: 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(LHS: SignedMin, RHS: ANC, Quotient&: Q1, Remainder&: R1);
38 // initialize Q2 = 2P/abs(D); R2 = rem(2P,abs(D))
39 APInt::udivrem(LHS: SignedMin, RHS: AD, Quotient&: Q2, Remainder&: 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(RHS: 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(RHS: 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(RHS: 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.
73UnsignedDivisionByConstantInfo
74UnsignedDivisionByConstantInfo::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 =
83 APInt::getLowBitsSet(numBits: D.getBitWidth(), loBitsSet: D.getBitWidth() - LeadingZeros);
84 APInt SignedMin = APInt::getSignedMinValue(numBits: D.getBitWidth());
85 APInt SignedMax = APInt::getSignedMaxValue(numBits: D.getBitWidth());
86
87 // Calculate NC, the largest dividend such that NC.urem(D) == D-1.
88 APInt NC = AllOnes - (AllOnes + 1 - D).urem(RHS: D);
89 assert(NC.urem(D) == D - 1 && "Unexpected NC value");
90 unsigned P = D.getBitWidth() - 1; // initialize P
91 APInt Q1, R1, Q2, R2;
92 // initialize Q1 = 2P/NC; R1 = rem(2P,NC)
93 APInt::udivrem(LHS: SignedMin, RHS: NC, Quotient&: Q1, Remainder&: R1);
94 // initialize Q2 = (2P-1)/D; R2 = rem((2P-1),D)
95 APInt::udivrem(LHS: SignedMax, RHS: D, Quotient&: Q2, Remainder&: R2);
96 do {
97 P = P + 1;
98 if (R1.uge(RHS: NC - R1)) {
99 // update Q1
100 Q1 <<= 1;
101 ++Q1;
102 // update R1
103 R1 <<= 1;
104 R1 -= NC;
105 } else {
106 Q1 <<= 1; // update Q1
107 R1 <<= 1; // update R1
108 }
109 if ((R2 + 1).uge(RHS: D - R2)) {
110 if (Q2.uge(RHS: SignedMax))
111 Retval.IsAdd = true;
112 // update Q2
113 Q2 <<= 1;
114 ++Q2;
115 // update R2
116 R2 <<= 1;
117 ++R2;
118 R2 -= D;
119 } else {
120 if (Q2.uge(RHS: SignedMin))
121 Retval.IsAdd = true;
122 // update Q2
123 Q2 <<= 1;
124 // update R2
125 R2 <<= 1;
126 ++R2;
127 }
128 // Delta = D - 1 - R2
129 Delta = D;
130 --Delta;
131 Delta -= R2;
132 } while (P < D.getBitWidth() * 2 &&
133 (Q1.ult(RHS: Delta) || (Q1 == Delta && R1.isZero())));
134
135 if (Retval.IsAdd && !D[0] && AllowEvenDivisorOptimization) {
136 unsigned PreShift = D.countr_zero();
137 APInt ShiftedD = D.lshr(shiftAmt: PreShift);
138 Retval =
139 UnsignedDivisionByConstantInfo::get(D: ShiftedD, LeadingZeros: LeadingZeros + PreShift);
140 assert(Retval.IsAdd == 0 && Retval.PreShift == 0);
141 Retval.PreShift = PreShift;
142 return Retval;
143 }
144
145 Retval.Magic = std::move(Q2); // resulting magic number
146 ++Retval.Magic;
147 Retval.PostShift = P - D.getBitWidth(); // resulting shift
148 // Reduce shift amount for IsAdd.
149 if (Retval.IsAdd) {
150 assert(Retval.PostShift > 0 && "Unexpected shift");
151 Retval.PostShift -= 1;
152 }
153 Retval.PreShift = 0;
154 return Retval;
155}
156