MLIR  16.0.0git
SlowMPInt.cpp
Go to the documentation of this file.
1 //===- SlowMPInt.cpp - MLIR SlowMPInt Class -------------------------------===//
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 
10 #include "llvm/Support/MathExtras.h"
11 
12 using namespace mlir;
13 using namespace presburger;
14 using namespace detail;
15 
16 SlowMPInt::SlowMPInt(int64_t val) : val(64, val, /*isSigned=*/true) {}
18 SlowMPInt::SlowMPInt(const llvm::APInt &val) : val(val) {}
19 SlowMPInt &SlowMPInt::operator=(int64_t val) { return *this = SlowMPInt(val); }
20 SlowMPInt::operator int64_t() const { return val.getSExtValue(); }
21 
22 llvm::hash_code detail::hash_value(const SlowMPInt &x) {
23  return hash_value(x.val);
24 }
25 
26 /// ---------------------------------------------------------------------------
27 /// Printing.
28 /// ---------------------------------------------------------------------------
29 void SlowMPInt::print(llvm::raw_ostream &os) const { os << val; }
30 
31 void SlowMPInt::dump() const { print(llvm::errs()); }
32 
33 llvm::raw_ostream &detail::operator<<(llvm::raw_ostream &os,
34  const SlowMPInt &x) {
35  x.print(os);
36  return os;
37 }
38 
39 /// ---------------------------------------------------------------------------
40 /// Convenience operator overloads for int64_t.
41 /// ---------------------------------------------------------------------------
43  return a += SlowMPInt(b);
44 }
46  return a -= SlowMPInt(b);
47 }
49  return a *= SlowMPInt(b);
50 }
52  return a /= SlowMPInt(b);
53 }
55  return a %= SlowMPInt(b);
56 }
57 
58 bool detail::operator==(const SlowMPInt &a, int64_t b) {
59  return a == SlowMPInt(b);
60 }
61 bool detail::operator!=(const SlowMPInt &a, int64_t b) {
62  return a != SlowMPInt(b);
63 }
64 bool detail::operator>(const SlowMPInt &a, int64_t b) {
65  return a > SlowMPInt(b);
66 }
67 bool detail::operator<(const SlowMPInt &a, int64_t b) {
68  return a < SlowMPInt(b);
69 }
70 bool detail::operator<=(const SlowMPInt &a, int64_t b) {
71  return a <= SlowMPInt(b);
72 }
73 bool detail::operator>=(const SlowMPInt &a, int64_t b) {
74  return a >= SlowMPInt(b);
75 }
76 SlowMPInt detail::operator+(const SlowMPInt &a, int64_t b) {
77  return a + SlowMPInt(b);
78 }
79 SlowMPInt detail::operator-(const SlowMPInt &a, int64_t b) {
80  return a - SlowMPInt(b);
81 }
82 SlowMPInt detail::operator*(const SlowMPInt &a, int64_t b) {
83  return a * SlowMPInt(b);
84 }
85 SlowMPInt detail::operator/(const SlowMPInt &a, int64_t b) {
86  return a / SlowMPInt(b);
87 }
88 SlowMPInt detail::operator%(const SlowMPInt &a, int64_t b) {
89  return a % SlowMPInt(b);
90 }
91 
92 bool detail::operator==(int64_t a, const SlowMPInt &b) {
93  return SlowMPInt(a) == b;
94 }
95 bool detail::operator!=(int64_t a, const SlowMPInt &b) {
96  return SlowMPInt(a) != b;
97 }
98 bool detail::operator>(int64_t a, const SlowMPInt &b) {
99  return SlowMPInt(a) > b;
100 }
101 bool detail::operator<(int64_t a, const SlowMPInt &b) {
102  return SlowMPInt(a) < b;
103 }
104 bool detail::operator<=(int64_t a, const SlowMPInt &b) {
105  return SlowMPInt(a) <= b;
106 }
107 bool detail::operator>=(int64_t a, const SlowMPInt &b) {
108  return SlowMPInt(a) >= b;
109 }
110 SlowMPInt detail::operator+(int64_t a, const SlowMPInt &b) {
111  return SlowMPInt(a) + b;
112 }
113 SlowMPInt detail::operator-(int64_t a, const SlowMPInt &b) {
114  return SlowMPInt(a) - b;
115 }
116 SlowMPInt detail::operator*(int64_t a, const SlowMPInt &b) {
117  return SlowMPInt(a) * b;
118 }
119 SlowMPInt detail::operator/(int64_t a, const SlowMPInt &b) {
120  return SlowMPInt(a) / b;
121 }
122 SlowMPInt detail::operator%(int64_t a, const SlowMPInt &b) {
123  return SlowMPInt(a) % b;
124 }
125 
126 static unsigned getMaxWidth(const APInt &a, const APInt &b) {
127  return std::max(a.getBitWidth(), b.getBitWidth());
128 }
129 
130 /// ---------------------------------------------------------------------------
131 /// Comparison operators.
132 /// ---------------------------------------------------------------------------
133 
134 // TODO: consider instead making APInt::compare available and using that.
135 bool SlowMPInt::operator==(const SlowMPInt &o) const {
136  unsigned width = getMaxWidth(val, o.val);
137  return val.sext(width) == o.val.sext(width);
138 }
139 bool SlowMPInt::operator!=(const SlowMPInt &o) const {
140  unsigned width = getMaxWidth(val, o.val);
141  return val.sext(width) != o.val.sext(width);
142 }
143 bool SlowMPInt::operator>(const SlowMPInt &o) const {
144  unsigned width = getMaxWidth(val, o.val);
145  return val.sext(width).sgt(o.val.sext(width));
146 }
147 bool SlowMPInt::operator<(const SlowMPInt &o) const {
148  unsigned width = getMaxWidth(val, o.val);
149  return val.sext(width).slt(o.val.sext(width));
150 }
151 bool SlowMPInt::operator<=(const SlowMPInt &o) const {
152  unsigned width = getMaxWidth(val, o.val);
153  return val.sext(width).sle(o.val.sext(width));
154 }
155 bool SlowMPInt::operator>=(const SlowMPInt &o) const {
156  unsigned width = getMaxWidth(val, o.val);
157  return val.sext(width).sge(o.val.sext(width));
158 }
159 
160 /// ---------------------------------------------------------------------------
161 /// Arithmetic operators.
162 /// ---------------------------------------------------------------------------
163 
164 /// Bring a and b to have the same width and then call op(a, b, overflow).
165 /// If the overflow bit becomes set, resize a and b to double the width and
166 /// call op(a, b, overflow), returning its result. The operation with double
167 /// widths should not also overflow.
169  const APInt &a, const APInt &b,
170  llvm::function_ref<APInt(const APInt &, const APInt &, bool &overflow)>
171  op) {
172  bool overflow;
173  unsigned width = getMaxWidth(a, b);
174  APInt ret = op(a.sext(width), b.sext(width), overflow);
175  if (!overflow)
176  return ret;
177 
178  width *= 2;
179  ret = op(a.sext(width), b.sext(width), overflow);
180  assert(!overflow && "double width should be sufficient to avoid overflow!");
181  return ret;
182 }
183 
185  return SlowMPInt(
186  runOpWithExpandOnOverflow(val, o.val, std::mem_fn(&APInt::sadd_ov)));
187 }
189  return SlowMPInt(
190  runOpWithExpandOnOverflow(val, o.val, std::mem_fn(&APInt::ssub_ov)));
191 }
193  return SlowMPInt(
194  runOpWithExpandOnOverflow(val, o.val, std::mem_fn(&APInt::smul_ov)));
195 }
197  return SlowMPInt(
198  runOpWithExpandOnOverflow(val, o.val, std::mem_fn(&APInt::sdiv_ov)));
199 }
200 SlowMPInt detail::abs(const SlowMPInt &x) { return x >= 0 ? x : -x; }
201 SlowMPInt detail::ceilDiv(const SlowMPInt &lhs, const SlowMPInt &rhs) {
202  if (rhs == -1)
203  return -lhs;
204  unsigned width = getMaxWidth(lhs.val, rhs.val);
205  return SlowMPInt(llvm::APIntOps::RoundingSDiv(
206  lhs.val.sext(width), rhs.val.sext(width), APInt::Rounding::UP));
207 }
209  if (rhs == -1)
210  return -lhs;
211  unsigned width = getMaxWidth(lhs.val, rhs.val);
212  return SlowMPInt(llvm::APIntOps::RoundingSDiv(
213  lhs.val.sext(width), rhs.val.sext(width), APInt::Rounding::DOWN));
214 }
215 // The RHS is always expected to be positive, and the result
216 /// is always non-negative.
217 SlowMPInt detail::mod(const SlowMPInt &lhs, const SlowMPInt &rhs) {
218  assert(rhs >= 1 && "mod is only supported for positive divisors!");
219  return lhs % rhs < 0 ? lhs % rhs + rhs : lhs % rhs;
220 }
221 
223  assert(a >= 0 && b >= 0 && "operands must be non-negative!");
224  unsigned width = getMaxWidth(a.val, b.val);
225  return SlowMPInt(llvm::APIntOps::GreatestCommonDivisor(a.val.sext(width),
226  b.val.sext(width)));
227 }
228 
229 /// Returns the least common multiple of 'a' and 'b'.
231  SlowMPInt x = abs(a);
232  SlowMPInt y = abs(b);
233  return (x * y) / gcd(x, y);
234 }
235 
236 /// This operation cannot overflow.
238  unsigned width = std::max(val.getBitWidth(), o.val.getBitWidth());
239  return SlowMPInt(val.sext(width).srem(o.val.sext(width)));
240 }
241 
243  if (val.isMinSignedValue()) {
244  /// Overflow only occurs when the value is the minimum possible value.
245  APInt ret = val.sext(2 * val.getBitWidth());
246  return SlowMPInt(-ret);
247  }
248  return SlowMPInt(-val);
249 }
250 
251 /// ---------------------------------------------------------------------------
252 /// Assignment operators, preincrement, predecrement.
253 /// ---------------------------------------------------------------------------
255  *this = *this + o;
256  return *this;
257 }
259  *this = *this - o;
260  return *this;
261 }
263  *this = *this * o;
264  return *this;
265 }
267  *this = *this / o;
268  return *this;
269 }
271  *this = *this % o;
272  return *this;
273 }
275  *this += 1;
276  return *this;
277 }
278 
280  *this -= 1;
281  return *this;
282 }
Include the generated interface declarations.
bool operator<(const SlowMPInt &o) const
Definition: SlowMPInt.cpp:147
SlowMPInt operator/(const SlowMPInt &a, int64_t b)
Definition: SlowMPInt.cpp:85
SlowMPInt & operator/=(const SlowMPInt &o)
Definition: SlowMPInt.cpp:266
SlowMPInt & operator%=(const SlowMPInt &o)
Definition: SlowMPInt.cpp:270
SlowMPInt operator+(const SlowMPInt &o) const
Definition: SlowMPInt.cpp:184
bool operator<=(const SlowMPInt &a, int64_t b)
Definition: SlowMPInt.cpp:70
SlowMPInt & operator/=(SlowMPInt &a, int64_t b)
Definition: SlowMPInt.cpp:51
SlowMPInt operator/(const SlowMPInt &o) const
Definition: SlowMPInt.cpp:196
bool operator!=(const SlowMPInt &o) const
Definition: SlowMPInt.cpp:139
SlowMPInt operator*(const SlowMPInt &o) const
Definition: SlowMPInt.cpp:192
static unsigned getMaxWidth(const APInt &a, const APInt &b)
Definition: SlowMPInt.cpp:126
SlowMPInt & operator+=(SlowMPInt &a, int64_t b)
Convenience operator overloads for int64_t.
Definition: SlowMPInt.cpp:42
SlowMPInt mod(const SlowMPInt &lhs, const SlowMPInt &rhs)
Returns the remainder of dividing LHS by RHS.
Definition: SlowMPInt.cpp:217
bool operator>(const SlowMPInt &o) const
Definition: SlowMPInt.cpp:143
SlowMPInt lcm(const SlowMPInt &a, const SlowMPInt &b)
Returns the least common multiple of &#39;a&#39; and &#39;b&#39;.
Definition: SlowMPInt.cpp:230
llvm::hash_code hash_value(const SlowMPInt &x)
Definition: SlowMPInt.cpp:22
SlowMPInt & operator*=(SlowMPInt &a, int64_t b)
Definition: SlowMPInt.cpp:48
friend llvm::hash_code hash_value(const SlowMPInt &x)
Overload to compute a hash_code for a SlowMPInt value.
bool operator>(const SlowMPInt &a, int64_t b)
Definition: SlowMPInt.cpp:64
friend SlowMPInt gcd(const SlowMPInt &a, const SlowMPInt &b)
The operands must be non-negative for gcd.
SlowMPInt operator+(const SlowMPInt &a, int64_t b)
Definition: SlowMPInt.cpp:76
SlowMPInt ceilDiv(const SlowMPInt &lhs, const SlowMPInt &rhs)
Definition: SlowMPInt.cpp:201
SlowMPInt & operator-=(const SlowMPInt &o)
Definition: SlowMPInt.cpp:258
bool operator>=(const SlowMPInt &o) const
Definition: SlowMPInt.cpp:155
SlowMPInt gcd(const SlowMPInt &a, const SlowMPInt &b)
Definition: SlowMPInt.cpp:222
APInt runOpWithExpandOnOverflow(const APInt &a, const APInt &b, llvm::function_ref< APInt(const APInt &, const APInt &, bool &overflow)> op)
Arithmetic operators.
Definition: SlowMPInt.cpp:168
bool operator!=(const SlowMPInt &a, int64_t b)
Definition: SlowMPInt.cpp:61
SlowMPInt & operator+=(const SlowMPInt &o)
Assignment operators, preincrement, predecrement.
Definition: SlowMPInt.cpp:254
void print(llvm::raw_ostream &os) const
Printing.
Definition: SlowMPInt.cpp:29
SlowMPInt operator*(const SlowMPInt &a, int64_t b)
Definition: SlowMPInt.cpp:82
SlowMPInt operator%(const SlowMPInt &o) const
This operation cannot overflow.
Definition: SlowMPInt.cpp:237
bool operator<(const SlowMPInt &a, int64_t b)
Definition: SlowMPInt.cpp:67
SlowMPInt operator-(const SlowMPInt &a, int64_t b)
Definition: SlowMPInt.cpp:79
llvm::raw_ostream & operator<<(llvm::raw_ostream &os, const SlowMPInt &x)
Definition: SlowMPInt.cpp:33
SlowMPInt & operator-=(SlowMPInt &a, int64_t b)
Definition: SlowMPInt.cpp:45
A simple class providing multi-precision arithmetic.
Definition: SlowMPInt.h:35
SlowMPInt abs(const SlowMPInt &x)
Redeclarations of friend declarations above to make it discoverable by lookups.
Definition: SlowMPInt.cpp:200
bool operator==(const SlowMPInt &o) const
Comparison operators.
Definition: SlowMPInt.cpp:135
SlowMPInt & operator=(int64_t val)
Definition: SlowMPInt.cpp:19
friend SlowMPInt abs(const SlowMPInt &x)
Redeclarations of friend declarations above to make it discoverable by lookups.
bool operator<=(const SlowMPInt &o) const
Definition: SlowMPInt.cpp:151
bool operator==(const SlowMPInt &a, int64_t b)
Definition: SlowMPInt.cpp:58
SlowMPInt & operator%=(SlowMPInt &a, int64_t b)
Definition: SlowMPInt.cpp:54
SlowMPInt operator%(const SlowMPInt &a, int64_t b)
Definition: SlowMPInt.cpp:88
bool operator>=(const SlowMPInt &a, int64_t b)
Definition: SlowMPInt.cpp:73
SlowMPInt & operator*=(const SlowMPInt &o)
Definition: SlowMPInt.cpp:262
static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)
SlowMPInt floorDiv(const SlowMPInt &lhs, const SlowMPInt &rhs)
Definition: SlowMPInt.cpp:208