LLVM  14.0.0git
DivisionByConstantInfo.cpp
Go to the documentation of this file.
1 //===----- DivisonByConstantInfo.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  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.
66 UnsignedDivisonByConstantInfo::get(const APInt &D, unsigned LeadingZeros) {
67  unsigned P;
68  APInt NC, Delta, Q1, R1, Q2, R2;
69  struct UnsignedDivisonByConstantInfo Retval;
70  Retval.IsAdd = 0; // 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 = 1;
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 = 1;
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 }
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
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::UnsignedDivisonByConstantInfo::IsAdd
bool IsAdd
add indicator
Definition: DivisionByConstantInfo.h:32
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:815
llvm::UnsignedDivisonByConstantInfo::get
static UnsignedDivisonByConstantInfo get(const APInt &D, unsigned LeadingZeros=0)
Calculate the magic numbers required to implement an unsigned integer division by a constant as a seq...
Definition: DivisionByConstantInfo.cpp:66
llvm::APInt::uge
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1152
R2
#define R2(n)
llvm::UnsignedDivisonByConstantInfo::ShiftAmount
unsigned ShiftAmount
shift amount
Definition: DivisionByConstantInfo.h:33
llvm::APInt::getAllOnes
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:214
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
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::APInt::ult
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1044
llvm::UnsignedDivisonByConstantInfo::Magic
APInt Magic
magic number
Definition: DivisionByConstantInfo.h:31
llvm::APInt::udiv
APInt udiv(const APInt &RHS) const
Unsigned division operation.
Definition: APInt.cpp:1565
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::UnsignedDivisonByConstantInfo
Magic data for optimising unsigned division by a constant.
Definition: DivisionByConstantInfo.h:28
llvm::SignedDivisionByConstantInfo
Magic data for optimising signed division by a constant.
Definition: DivisionByConstantInfo.h:21