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