1 //===- FixedPoint.cpp - Fixed point constant handling -----------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
10 /// Defines the implementation for the fixed point number interface.
12 //===----------------------------------------------------------------------===//
14 #include "clang/Basic/FixedPoint.h"
18 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();
28 NewVal = NewVal.extend(NewVal.getBitWidth() + DstScale - getScale());
29 NewVal <<= (DstScale - getScale());
31 NewVal >>= (getScale() - DstScale);
34 auto Mask = llvm::APInt::getBitsSetFrom(
36 std::min(DstScale + DstSema.getIntegralBits(), NewVal.getBitWidth()));
37 llvm::APInt Masked(NewVal & Mask);
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;
48 // If the dst semantics are unsigned, but our value is signed and negative, we
50 if (!DstSema.isSigned() && NewVal.isSigned() && NewVal.isNegative()) {
51 // Found negative overflow for unsigned result
52 if (DstSema.isSaturated())
58 NewVal = NewVal.extOrTrunc(DstWidth);
59 NewVal.setIsSigned(DstSema.isSigned());
60 return APFixedPoint(NewVal, DstSema);
63 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();
71 unsigned CommonWidth = std::max(Val.getBitWidth(), OtherWidth);
73 // Prevent overflow in the event the widths are the same but the scales differ
74 CommonWidth += getScale() >= OtherScale ? getScale() - OtherScale
75 : OtherScale - getScale();
77 ThisVal = ThisVal.extOrTrunc(CommonWidth);
78 OtherVal = OtherVal.extOrTrunc(CommonWidth);
80 unsigned CommonScale = std::max(getScale(), OtherScale);
81 ThisVal = ThisVal.shl(CommonScale - getScale());
82 OtherVal = OtherVal.shl(CommonScale - OtherScale);
84 if (ThisSigned && OtherSigned) {
85 if (ThisVal.sgt(OtherVal))
87 else if (ThisVal.slt(OtherVal))
89 } else if (!ThisSigned && !OtherSigned) {
90 if (ThisVal.ugt(OtherVal))
92 else if (ThisVal.ult(OtherVal))
94 } else if (ThisSigned && !OtherSigned) {
95 if (ThisVal.isSignBitSet())
97 else if (ThisVal.ugt(OtherVal))
99 else if (ThisVal.ult(OtherVal))
102 // !ThisSigned && OtherSigned
103 if (OtherVal.isSignBitSet())
105 else if (ThisVal.ugt(OtherVal))
107 else if (ThisVal.ult(OtherVal))
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())
119 return APFixedPoint(Val, Sema);
122 APFixedPoint APFixedPoint::getMin(const FixedPointSemantics &Sema) {
123 auto Val = llvm::APSInt::getMinValue(Sema.getWidth(), !Sema.isSigned());
124 return APFixedPoint(Val, Sema);
127 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;
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;
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)
148 return FixedPointSemantics(CommonWidth, CommonScale, ResultIsSigned,
149 ResultIsSaturated, ResultHasUnsignedPadding);
152 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;
162 if (CommonFXSema.isSaturated()) {
163 Result = CommonFXSema.isSigned() ? ThisVal.sadd_sat(OtherVal)
164 : ThisVal.uadd_sat(OtherVal);
166 Result = ThisVal.isSigned() ? ThisVal.sadd_ov(OtherVal, Overflowed)
167 : ThisVal.uadd_ov(OtherVal, Overflowed);
171 *Overflow = Overflowed;
173 return APFixedPoint(Result, CommonFXSema);
176 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;
186 if (CommonFXSema.isSaturated()) {
187 Result = CommonFXSema.isSigned() ? ThisVal.ssub_sat(OtherVal)
188 : ThisVal.usub_sat(OtherVal);
190 Result = ThisVal.isSigned() ? ThisVal.ssub_ov(OtherVal, Overflowed)
191 : ThisVal.usub_ov(OtherVal, Overflowed);
195 *Overflow = Overflowed;
197 return APFixedPoint(Result, CommonFXSema);
200 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;
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);
215 ThisVal = ThisVal.zextOrSelf(Wide);
216 OtherVal = OtherVal.zextOrSelf(Wide);
219 // Perform the full multiplication and downscale to get the same scale.
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
227 if (CommonFXSema.isSigned())
228 Result = ThisVal.smul_ov(OtherVal, Overflowed)
229 .ashr(CommonFXSema.getScale());
231 Result = ThisVal.umul_ov(OtherVal, Overflowed)
232 .lshr(CommonFXSema.getScale());
233 assert(!Overflowed && "Full multiplication cannot overflow!");
234 Result.setIsSigned(CommonFXSema.isSigned());
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()
240 llvm::APSInt Min = APFixedPoint::getMin(CommonFXSema).getValue()
242 if (CommonFXSema.isSaturated()) {
245 else if (Result > Max)
248 Overflowed = Result < Min || Result > Max;
251 *Overflow = Overflowed;
253 return APFixedPoint(Result.sextOrTrunc(CommonFXSema.getWidth()),
257 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;
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);
272 ThisVal = ThisVal.zextOrSelf(Wide);
273 OtherVal = OtherVal.zextOrSelf(Wide);
276 // Upscale to compensate for the loss of precision from division, and
277 // perform the full division.
278 ThisVal = ThisVal.shl(CommonFXSema.getScale());
280 if (CommonFXSema.isSigned()) {
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())
288 Result = ThisVal.udiv(OtherVal);
289 Result.setIsSigned(CommonFXSema.isSigned());
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()
295 llvm::APSInt Min = APFixedPoint::getMin(CommonFXSema).getValue()
297 if (CommonFXSema.isSaturated()) {
300 else if (Result > Max)
303 Overflowed = Result < Min || Result > Max;
306 *Overflow = Overflowed;
308 return APFixedPoint(Result.sextOrTrunc(CommonFXSema.getWidth()),
312 void APFixedPoint::toString(llvm::SmallVectorImpl<char> &Str) const {
313 llvm::APSInt Val = getValue();
314 unsigned Scale = getScale();
316 if (Val.isSigned() && Val.isNegative() && Val != -Val) {
321 llvm::APSInt IntPart = Val >> Scale;
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);
329 IntPart.toString(Str, /*Radix=*/10);
332 (FractPart * RadixInt)
334 .toString(Str, /*Radix=*/10, Val.isSigned());
335 FractPart = (FractPart * RadixInt) & FractPartMask;
336 } while (FractPart != 0);
339 APFixedPoint APFixedPoint::negate(bool *Overflow) const {
340 if (!isSaturated()) {
343 (!isSigned() && Val != 0) || (isSigned() && Val.isMinSignedValue());
344 return APFixedPoint(-Val, Sema);
347 // We never overflow for saturation
352 return Val.isMinSignedValue() ? getMax(Sema) : APFixedPoint(-Val, Sema);
354 return APFixedPoint(Sema);
357 llvm::APSInt APFixedPoint::convertToInt(unsigned DstWidth, bool DstSign,
358 bool *Overflow) const {
359 llvm::APSInt Result = getIntPart();
360 unsigned SrcWidth = getWidth();
362 llvm::APSInt DstMin = llvm::APSInt::getMinValue(DstWidth, !DstSign);
363 llvm::APSInt DstMax = llvm::APSInt::getMaxValue(DstWidth, !DstSign);
365 if (SrcWidth < DstWidth) {
366 Result = Result.extend(DstWidth);
367 } else if (SrcWidth > DstWidth) {
368 DstMin = DstMin.extend(SrcWidth);
369 DstMax = DstMax.extend(SrcWidth);
373 if (Result.isSigned() && !DstSign) {
374 *Overflow = Result.isNegative() || Result.ugt(DstMax);
375 } else if (Result.isUnsigned() && DstSign) {
376 *Overflow = Result.ugt(DstMax);
378 *Overflow = Result < DstMin || Result > DstMax;
382 Result.setIsSigned(DstSign);
383 return Result.extOrTrunc(DstWidth);
386 APFixedPoint APFixedPoint::getFromIntValue(const llvm::APSInt &Value,
387 const FixedPointSemantics &DstFXSema,
389 FixedPointSemantics IntFXSema = FixedPointSemantics::GetIntegerSemantics(
390 Value.getBitWidth(), Value.isSigned());
391 return APFixedPoint(Value, IntFXSema).convert(DstFXSema, Overflow);