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.
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 
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.
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 
31  APInt AD = D.abs();
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))
39  APInt::udivrem(SignedMin, AD, Q2, 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(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;
52  R2 -= AD;
53  }
54  // Delta = AD - R2
55  Delta = AD;
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.
74 UnsignedDivisionByConstantInfo::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 = APInt::getAllOnes(D.getBitWidth()).lshr(LeadingZeros);
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))
110  Retval.IsAdd = true;
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))
120  Retval.IsAdd = true;
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[0] && AllowEvenDivisorOptimization) {
135  unsigned PreShift = D.countTrailingZeros();
136  APInt ShiftedD = D.lshr(PreShift);
137  Retval =
138  UnsignedDivisionByConstantInfo::get(ShiftedD, LeadingZeros + PreShift);
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.
148  if (Retval.IsAdd) {
149  assert(Retval.PostShift > 0 && "Unexpected shift");
150  Retval.PostShift -= 1;
151  }
152  Retval.PreShift = 0;
153  return Retval;
154 }
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::APInt::udivrem
static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Dual division/remainder interface.
Definition: APInt.cpp:1756
DivisionByConstantInfo.h
T
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::UnsignedDivisionByConstantInfo::get
static 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
llvm::APInt::getSignedMaxValue
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:189
llvm::APInt::lshr
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:839
llvm::APInt::uge
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1199
R2
#define R2(n)
llvm::APInt::isZero
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition: APInt.h:366
llvm::APInt::getAllOnes
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:214
llvm::UnsignedDivisionByConstantInfo::Magic
APInt Magic
magic number
Definition: DivisionByConstantInfo.h:32
llvm::UnsignedDivisionByConstantInfo::PreShift
unsigned PreShift
pre-shift amount
Definition: DivisionByConstantInfo.h:35
llvm::SignedDivisionByConstantInfo::ShiftAmount
unsigned ShiftAmount
shift amount
Definition: DivisionByConstantInfo.h:24
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::SignedDivisionByConstantInfo::get
static 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
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::APInt::negate
void negate()
Negate this APInt in place.
Definition: APInt.h:1421
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::UnsignedDivisionByConstantInfo::PostShift
unsigned PostShift
post-shift amount
Definition: DivisionByConstantInfo.h:34
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::UnsignedDivisionByConstantInfo::IsAdd
bool IsAdd
add indicator
Definition: DivisionByConstantInfo.h:33
llvm::UnsignedDivisionByConstantInfo
Magic data for optimising unsigned division by a constant.
Definition: DivisionByConstantInfo.h:28
llvm::APInt::ult
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1089
NC
#define NC
Definition: regutils.h:42
llvm::APInt::getSignedMinValue
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:199
llvm::SignedDivisionByConstantInfo::Magic
APInt Magic
magic number
Definition: DivisionByConstantInfo.h:23
llvm::SignedDivisionByConstantInfo
Magic data for optimising signed division by a constant.
Definition: DivisionByConstantInfo.h:21