1 //===- FixedPoint.cpp - Fixed point constant handling -----------*- 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 /// \file
10 /// Defines the implementation for the fixed point number interface.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "clang/Basic/FixedPoint.h"
15
16 namespace clang {
17
convert(const FixedPointSemantics & DstSema,bool * Overflow) const18 APFixedPoint APFixedPoint::convert(const FixedPointSemantics &DstSema,
19 bool *Overflow) const {
20 llvm::APSInt NewVal = Val;
21 unsigned DstWidth = DstSema.getWidth();
22 unsigned DstScale = DstSema.getScale();
23 bool Upscaling = DstScale > getScale();
24 if (Overflow)
25 *Overflow = false;
26
27 if (Upscaling) {
28 NewVal = NewVal.extend(NewVal.getBitWidth() + DstScale - getScale());
29 NewVal <<= (DstScale - getScale());
30 } else {
31 NewVal >>= (getScale() - DstScale);
32 }
33
34 auto Mask = llvm::APInt::getBitsSetFrom(
35 NewVal.getBitWidth(),
36 std::min(DstScale + DstSema.getIntegralBits(), NewVal.getBitWidth()));
37 llvm::APInt Masked(NewVal & Mask);
38
39 // Change in the bits above the sign
40 if (!(Masked == Mask || Masked == 0)) {
41 // Found overflow in the bits above the sign
42 if (DstSema.isSaturated())
43 NewVal = NewVal.isNegative() ? Mask : ~Mask;
44 else if (Overflow)
45 *Overflow = true;
46 }
47
48 // If the dst semantics are unsigned, but our value is signed and negative, we
49 // clamp to zero.
50 if (!DstSema.isSigned() && NewVal.isSigned() && NewVal.isNegative()) {
51 // Found negative overflow for unsigned result
52 if (DstSema.isSaturated())
53 NewVal = 0;
54 else if (Overflow)
55 *Overflow = true;
56 }
57
58 NewVal = NewVal.extOrTrunc(DstWidth);
59 NewVal.setIsSigned(DstSema.isSigned());
60 return APFixedPoint(NewVal, DstSema);
61 }
62
compare(const APFixedPoint & Other) const63 int APFixedPoint::compare(const APFixedPoint &Other) const {
64 llvm::APSInt ThisVal = getValue();
65 llvm::APSInt OtherVal = Other.getValue();
66 bool ThisSigned = Val.isSigned();
67 bool OtherSigned = OtherVal.isSigned();
68 unsigned OtherScale = Other.getScale();
69 unsigned OtherWidth = OtherVal.getBitWidth();
70
71 unsigned CommonWidth = std::max(Val.getBitWidth(), OtherWidth);
72
73 // Prevent overflow in the event the widths are the same but the scales differ
74 CommonWidth += getScale() >= OtherScale ? getScale() - OtherScale
75 : OtherScale - getScale();
76
77 ThisVal = ThisVal.extOrTrunc(CommonWidth);
78 OtherVal = OtherVal.extOrTrunc(CommonWidth);
79
80 unsigned CommonScale = std::max(getScale(), OtherScale);
81 ThisVal = ThisVal.shl(CommonScale - getScale());
82 OtherVal = OtherVal.shl(CommonScale - OtherScale);
83
84 if (ThisSigned && OtherSigned) {
85 if (ThisVal.sgt(OtherVal))
86 return 1;
87 else if (ThisVal.slt(OtherVal))
88 return -1;
89 } else if (!ThisSigned && !OtherSigned) {
90 if (ThisVal.ugt(OtherVal))
91 return 1;
92 else if (ThisVal.ult(OtherVal))
93 return -1;
94 } else if (ThisSigned && !OtherSigned) {
95 if (ThisVal.isSignBitSet())
96 return -1;
97 else if (ThisVal.ugt(OtherVal))
98 return 1;
99 else if (ThisVal.ult(OtherVal))
100 return -1;
101 } else {
102 // !ThisSigned && OtherSigned
103 if (OtherVal.isSignBitSet())
104 return 1;
105 else if (ThisVal.ugt(OtherVal))
106 return 1;
107 else if (ThisVal.ult(OtherVal))
108 return -1;
109 }
110
111 return 0;
112 }
113
getMax(const FixedPointSemantics & Sema)114 APFixedPoint APFixedPoint::getMax(const FixedPointSemantics &Sema) {
115 bool IsUnsigned = !Sema.isSigned();
116 auto Val = llvm::APSInt::getMaxValue(Sema.getWidth(), IsUnsigned);
117 if (IsUnsigned && Sema.hasUnsignedPadding())
118 Val = Val.lshr(1);
119 return APFixedPoint(Val, Sema);
120 }
121
getMin(const FixedPointSemantics & Sema)122 APFixedPoint APFixedPoint::getMin(const FixedPointSemantics &Sema) {
123 auto Val = llvm::APSInt::getMinValue(Sema.getWidth(), !Sema.isSigned());
124 return APFixedPoint(Val, Sema);
125 }
126
getCommonSemantics(const FixedPointSemantics & Other) const127 FixedPointSemantics FixedPointSemantics::getCommonSemantics(
128 const FixedPointSemantics &Other) const {
129 unsigned CommonScale = std::max(getScale(), Other.getScale());
130 unsigned CommonWidth =
131 std::max(getIntegralBits(), Other.getIntegralBits()) + CommonScale;
132
133 bool ResultIsSigned = isSigned() || Other.isSigned();
134 bool ResultIsSaturated = isSaturated() || Other.isSaturated();
135 bool ResultHasUnsignedPadding = false;
136 if (!ResultIsSigned) {
137 // Both are unsigned.
138 ResultHasUnsignedPadding = hasUnsignedPadding() &&
139 Other.hasUnsignedPadding() && !ResultIsSaturated;
140 }
141
142 // If the result is signed, add an extra bit for the sign. Otherwise, if it is
143 // unsigned and has unsigned padding, we only need to add the extra padding
144 // bit back if we are not saturating.
145 if (ResultIsSigned || ResultHasUnsignedPadding)
146 CommonWidth++;
147
148 return FixedPointSemantics(CommonWidth, CommonScale, ResultIsSigned,
149 ResultIsSaturated, ResultHasUnsignedPadding);
150 }
151
add(const APFixedPoint & Other,bool * Overflow) const152 APFixedPoint APFixedPoint::add(const APFixedPoint &Other,
153 bool *Overflow) const {
154 auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
155 APFixedPoint ConvertedThis = convert(CommonFXSema);
156 APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
157 llvm::APSInt ThisVal = ConvertedThis.getValue();
158 llvm::APSInt OtherVal = ConvertedOther.getValue();
159 bool Overflowed = false;
160
161 llvm::APSInt Result;
162 if (CommonFXSema.isSaturated()) {
163 Result = CommonFXSema.isSigned() ? ThisVal.sadd_sat(OtherVal)
164 : ThisVal.uadd_sat(OtherVal);
165 } else {
166 Result = ThisVal.isSigned() ? ThisVal.sadd_ov(OtherVal, Overflowed)
167 : ThisVal.uadd_ov(OtherVal, Overflowed);
168 }
169
170 if (Overflow)
171 *Overflow = Overflowed;
172
173 return APFixedPoint(Result, CommonFXSema);
174 }
175
sub(const APFixedPoint & Other,bool * Overflow) const176 APFixedPoint APFixedPoint::sub(const APFixedPoint &Other,
177 bool *Overflow) const {
178 auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
179 APFixedPoint ConvertedThis = convert(CommonFXSema);
180 APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
181 llvm::APSInt ThisVal = ConvertedThis.getValue();
182 llvm::APSInt OtherVal = ConvertedOther.getValue();
183 bool Overflowed = false;
184
185 llvm::APSInt Result;
186 if (CommonFXSema.isSaturated()) {
187 Result = CommonFXSema.isSigned() ? ThisVal.ssub_sat(OtherVal)
188 : ThisVal.usub_sat(OtherVal);
189 } else {
190 Result = ThisVal.isSigned() ? ThisVal.ssub_ov(OtherVal, Overflowed)
191 : ThisVal.usub_ov(OtherVal, Overflowed);
192 }
193
194 if (Overflow)
195 *Overflow = Overflowed;
196
197 return APFixedPoint(Result, CommonFXSema);
198 }
199
mul(const APFixedPoint & Other,bool * Overflow) const200 APFixedPoint APFixedPoint::mul(const APFixedPoint &Other,
201 bool *Overflow) const {
202 auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
203 APFixedPoint ConvertedThis = convert(CommonFXSema);
204 APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
205 llvm::APSInt ThisVal = ConvertedThis.getValue();
206 llvm::APSInt OtherVal = ConvertedOther.getValue();
207 bool Overflowed = false;
208
209 // Widen the LHS and RHS so we can perform a full multiplication.
210 unsigned Wide = CommonFXSema.getWidth() * 2;
211 if (CommonFXSema.isSigned()) {
212 ThisVal = ThisVal.sextOrSelf(Wide);
213 OtherVal = OtherVal.sextOrSelf(Wide);
214 } else {
215 ThisVal = ThisVal.zextOrSelf(Wide);
216 OtherVal = OtherVal.zextOrSelf(Wide);
217 }
218
219 // Perform the full multiplication and downscale to get the same scale.
220 //
221 // Note that the right shifts here perform an implicit downwards rounding.
222 // This rounding could discard bits that would technically place the result
223 // outside the representable range. We interpret the spec as allowing us to
224 // perform the rounding step first, avoiding the overflow case that would
225 // arise.
226 llvm::APSInt Result;
227 if (CommonFXSema.isSigned())
228 Result = ThisVal.smul_ov(OtherVal, Overflowed)
229 .ashr(CommonFXSema.getScale());
230 else
231 Result = ThisVal.umul_ov(OtherVal, Overflowed)
232 .lshr(CommonFXSema.getScale());
233 assert(!Overflowed && "Full multiplication cannot overflow!");
234 Result.setIsSigned(CommonFXSema.isSigned());
235
236 // If our result lies outside of the representative range of the common
237 // semantic, we either have overflow or saturation.
238 llvm::APSInt Max = APFixedPoint::getMax(CommonFXSema).getValue()
239 .extOrTrunc(Wide);
240 llvm::APSInt Min = APFixedPoint::getMin(CommonFXSema).getValue()
241 .extOrTrunc(Wide);
242 if (CommonFXSema.isSaturated()) {
243 if (Result < Min)
244 Result = Min;
245 else if (Result > Max)
246 Result = Max;
247 } else
248 Overflowed = Result < Min || Result > Max;
249
250 if (Overflow)
251 *Overflow = Overflowed;
252
253 return APFixedPoint(Result.sextOrTrunc(CommonFXSema.getWidth()),
254 CommonFXSema);
255 }
256
div(const APFixedPoint & Other,bool * Overflow) const257 APFixedPoint APFixedPoint::div(const APFixedPoint &Other,
258 bool *Overflow) const {
259 auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
260 APFixedPoint ConvertedThis = convert(CommonFXSema);
261 APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
262 llvm::APSInt ThisVal = ConvertedThis.getValue();
263 llvm::APSInt OtherVal = ConvertedOther.getValue();
264 bool Overflowed = false;
265
266 // Widen the LHS and RHS so we can perform a full division.
267 unsigned Wide = CommonFXSema.getWidth() * 2;
268 if (CommonFXSema.isSigned()) {
269 ThisVal = ThisVal.sextOrSelf(Wide);
270 OtherVal = OtherVal.sextOrSelf(Wide);
271 } else {
272 ThisVal = ThisVal.zextOrSelf(Wide);
273 OtherVal = OtherVal.zextOrSelf(Wide);
274 }
275
276 // Upscale to compensate for the loss of precision from division, and
277 // perform the full division.
278 ThisVal = ThisVal.shl(CommonFXSema.getScale());
279 llvm::APSInt Result;
280 if (CommonFXSema.isSigned()) {
281 llvm::APInt Rem;
282 llvm::APInt::sdivrem(ThisVal, OtherVal, Result, Rem);
283 // If the quotient is negative and the remainder is nonzero, round
284 // towards negative infinity by subtracting epsilon from the result.
285 if (ThisVal.isNegative() != OtherVal.isNegative() && !Rem.isNullValue())
286 Result = Result - 1;
287 } else
288 Result = ThisVal.udiv(OtherVal);
289 Result.setIsSigned(CommonFXSema.isSigned());
290
291 // If our result lies outside of the representative range of the common
292 // semantic, we either have overflow or saturation.
293 llvm::APSInt Max = APFixedPoint::getMax(CommonFXSema).getValue()
294 .extOrTrunc(Wide);
295 llvm::APSInt Min = APFixedPoint::getMin(CommonFXSema).getValue()
296 .extOrTrunc(Wide);
297 if (CommonFXSema.isSaturated()) {
298 if (Result < Min)
299 Result = Min;
300 else if (Result > Max)
301 Result = Max;
302 } else
303 Overflowed = Result < Min || Result > Max;
304
305 if (Overflow)
306 *Overflow = Overflowed;
307
308 return APFixedPoint(Result.sextOrTrunc(CommonFXSema.getWidth()),
309 CommonFXSema);
310 }
311
toString(llvm::SmallVectorImpl<char> & Str) const312 void APFixedPoint::toString(llvm::SmallVectorImpl<char> &Str) const {
313 llvm::APSInt Val = getValue();
314 unsigned Scale = getScale();
315
316 if (Val.isSigned() && Val.isNegative() && Val != -Val) {
317 Val = -Val;
318 Str.push_back('-');
319 }
320
321 llvm::APSInt IntPart = Val >> Scale;
322
323 // Add 4 digits to hold the value after multiplying 10 (the radix)
324 unsigned Width = Val.getBitWidth() + 4;
325 llvm::APInt FractPart = Val.zextOrTrunc(Scale).zext(Width);
326 llvm::APInt FractPartMask = llvm::APInt::getAllOnesValue(Scale).zext(Width);
327 llvm::APInt RadixInt = llvm::APInt(Width, 10);
328
329 IntPart.toString(Str, /*Radix=*/10);
330 Str.push_back('.');
331 do {
332 (FractPart * RadixInt)
333 .lshr(Scale)
334 .toString(Str, /*Radix=*/10, Val.isSigned());
335 FractPart = (FractPart * RadixInt) & FractPartMask;
336 } while (FractPart != 0);
337 }
338
negate(bool * Overflow) const339 APFixedPoint APFixedPoint::negate(bool *Overflow) const {
340 if (!isSaturated()) {
341 if (Overflow)
342 *Overflow =
343 (!isSigned() && Val != 0) || (isSigned() && Val.isMinSignedValue());
344 return APFixedPoint(-Val, Sema);
345 }
346
347 // We never overflow for saturation
348 if (Overflow)
349 *Overflow = false;
350
351 if (isSigned())
352 return Val.isMinSignedValue() ? getMax(Sema) : APFixedPoint(-Val, Sema);
353 else
354 return APFixedPoint(Sema);
355 }
356
convertToInt(unsigned DstWidth,bool DstSign,bool * Overflow) const357 llvm::APSInt APFixedPoint::convertToInt(unsigned DstWidth, bool DstSign,
358 bool *Overflow) const {
359 llvm::APSInt Result = getIntPart();
360 unsigned SrcWidth = getWidth();
361
362 llvm::APSInt DstMin = llvm::APSInt::getMinValue(DstWidth, !DstSign);
363 llvm::APSInt DstMax = llvm::APSInt::getMaxValue(DstWidth, !DstSign);
364
365 if (SrcWidth < DstWidth) {
366 Result = Result.extend(DstWidth);
367 } else if (SrcWidth > DstWidth) {
368 DstMin = DstMin.extend(SrcWidth);
369 DstMax = DstMax.extend(SrcWidth);
370 }
371
372 if (Overflow) {
373 if (Result.isSigned() && !DstSign) {
374 *Overflow = Result.isNegative() || Result.ugt(DstMax);
375 } else if (Result.isUnsigned() && DstSign) {
376 *Overflow = Result.ugt(DstMax);
377 } else {
378 *Overflow = Result < DstMin || Result > DstMax;
379 }
380 }
381
382 Result.setIsSigned(DstSign);
383 return Result.extOrTrunc(DstWidth);
384 }
385
getFromIntValue(const llvm::APSInt & Value,const FixedPointSemantics & DstFXSema,bool * Overflow)386 APFixedPoint APFixedPoint::getFromIntValue(const llvm::APSInt &Value,
387 const FixedPointSemantics &DstFXSema,
388 bool *Overflow) {
389 FixedPointSemantics IntFXSema = FixedPointSemantics::GetIntegerSemantics(
390 Value.getBitWidth(), Value.isSigned());
391 return APFixedPoint(Value, IntFXSema).convert(DstFXSema, Overflow);
392 }
393
394 } // namespace clang
395