1//===- APFixedPoint.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 "llvm/ADT/APFixedPoint.h"
15#include "llvm/ADT/APFloat.h"
16
17namespace llvm {
18
19APFixedPoint APFixedPoint::convert(const FixedPointSemantics &DstSema,
20                                   bool *Overflow) const {
21  APSInt NewVal = Val;
22  unsigned DstWidth = DstSema.getWidth();
23  unsigned DstScale = DstSema.getScale();
24  bool Upscaling = DstScale > getScale();
25  if (Overflow)
26    *Overflow = false;
27
28  if (Upscaling) {
29    NewVal = NewVal.extend(NewVal.getBitWidth() + DstScale - getScale());
30    NewVal <<= (DstScale - getScale());
31  } else {
32    NewVal >>= (getScale() - DstScale);
33  }
34
35  auto Mask = APInt::getBitsSetFrom(
36      NewVal.getBitWidth(),
37      std::min(DstScale + DstSema.getIntegralBits(), NewVal.getBitWidth()));
38  APInt Masked(NewVal & Mask);
39
40  // Change in the bits above the sign
41  if (!(Masked == Mask || Masked == 0)) {
42    // Found overflow in the bits above the sign
43    if (DstSema.isSaturated())
44      NewVal = NewVal.isNegative() ? Mask : ~Mask;
45    else if (Overflow)
46      *Overflow = true;
47  }
48
49  // If the dst semantics are unsigned, but our value is signed and negative, we
50  // clamp to zero.
51  if (!DstSema.isSigned() && NewVal.isSigned() && NewVal.isNegative()) {
52    // Found negative overflow for unsigned result
53    if (DstSema.isSaturated())
54      NewVal = 0;
55    else if (Overflow)
56      *Overflow = true;
57  }
58
59  NewVal = NewVal.extOrTrunc(DstWidth);
60  NewVal.setIsSigned(DstSema.isSigned());
61  return APFixedPoint(NewVal, DstSema);
62}
63
64int APFixedPoint::compare(const APFixedPoint &Other) const {
65  APSInt ThisVal = getValue();
66  APSInt OtherVal = Other.getValue();
67  bool ThisSigned = Val.isSigned();
68  bool OtherSigned = OtherVal.isSigned();
69  unsigned OtherScale = Other.getScale();
70  unsigned OtherWidth = OtherVal.getBitWidth();
71
72  unsigned CommonWidth = std::max(Val.getBitWidth(), OtherWidth);
73
74  // Prevent overflow in the event the widths are the same but the scales differ
75  CommonWidth += getScale() >= OtherScale ? getScale() - OtherScale
76                                          : OtherScale - getScale();
77
78  ThisVal = ThisVal.extOrTrunc(CommonWidth);
79  OtherVal = OtherVal.extOrTrunc(CommonWidth);
80
81  unsigned CommonScale = std::max(getScale(), OtherScale);
82  ThisVal = ThisVal.shl(CommonScale - getScale());
83  OtherVal = OtherVal.shl(CommonScale - OtherScale);
84
85  if (ThisSigned && OtherSigned) {
86    if (ThisVal.sgt(OtherVal))
87      return 1;
88    else if (ThisVal.slt(OtherVal))
89      return -1;
90  } else if (!ThisSigned && !OtherSigned) {
91    if (ThisVal.ugt(OtherVal))
92      return 1;
93    else if (ThisVal.ult(OtherVal))
94      return -1;
95  } else if (ThisSigned && !OtherSigned) {
96    if (ThisVal.isSignBitSet())
97      return -1;
98    else if (ThisVal.ugt(OtherVal))
99      return 1;
100    else if (ThisVal.ult(OtherVal))
101      return -1;
102  } else {
103    // !ThisSigned && OtherSigned
104    if (OtherVal.isSignBitSet())
105      return 1;
106    else if (ThisVal.ugt(OtherVal))
107      return 1;
108    else if (ThisVal.ult(OtherVal))
109      return -1;
110  }
111
112  return 0;
113}
114
115APFixedPoint APFixedPoint::getMax(const FixedPointSemantics &Sema) {
116  bool IsUnsigned = !Sema.isSigned();
117  auto Val = APSInt::getMaxValue(Sema.getWidth(), IsUnsigned);
118  if (IsUnsigned && Sema.hasUnsignedPadding())
119    Val = Val.lshr(1);
120  return APFixedPoint(Val, Sema);
121}
122
123APFixedPoint APFixedPoint::getMin(const FixedPointSemantics &Sema) {
124  auto Val = APSInt::getMinValue(Sema.getWidth(), !Sema.isSigned());
125  return APFixedPoint(Val, Sema);
126}
127
128bool FixedPointSemantics::fitsInFloatSemantics(
129    const fltSemantics &FloatSema) const {
130  // A fixed point semantic fits in a floating point semantic if the maximum
131  // and minimum values as integers of the fixed point semantic can fit in the
132  // floating point semantic.
133
134  // If these values do not fit, then a floating point rescaling of the true
135  // maximum/minimum value will not fit either, so the floating point semantic
136  // cannot be used to perform such a rescaling.
137
138  APSInt MaxInt = APFixedPoint::getMax(*this).getValue();
139  APFloat F(FloatSema);
140  APFloat::opStatus Status = F.convertFromAPInt(MaxInt, MaxInt.isSigned(),
141                                                APFloat::rmNearestTiesToAway);
142  if ((Status & APFloat::opOverflow) || !isSigned())
143    return !(Status & APFloat::opOverflow);
144
145  APSInt MinInt = APFixedPoint::getMin(*this).getValue();
146  Status = F.convertFromAPInt(MinInt, MinInt.isSigned(),
147                              APFloat::rmNearestTiesToAway);
148  return !(Status & APFloat::opOverflow);
149}
150
151FixedPointSemantics FixedPointSemantics::getCommonSemantics(
152    const FixedPointSemantics &Other) const {
153  unsigned CommonScale = std::max(getScale(), Other.getScale());
154  unsigned CommonWidth =
155      std::max(getIntegralBits(), Other.getIntegralBits()) + CommonScale;
156
157  bool ResultIsSigned = isSigned() || Other.isSigned();
158  bool ResultIsSaturated = isSaturated() || Other.isSaturated();
159  bool ResultHasUnsignedPadding = false;
160  if (!ResultIsSigned) {
161    // Both are unsigned.
162    ResultHasUnsignedPadding = hasUnsignedPadding() &&
163                               Other.hasUnsignedPadding() && !ResultIsSaturated;
164  }
165
166  // If the result is signed, add an extra bit for the sign. Otherwise, if it is
167  // unsigned and has unsigned padding, we only need to add the extra padding
168  // bit back if we are not saturating.
169  if (ResultIsSigned || ResultHasUnsignedPadding)
170    CommonWidth++;
171
172  return FixedPointSemantics(CommonWidth, CommonScale, ResultIsSigned,
173                             ResultIsSaturated, ResultHasUnsignedPadding);
174}
175
176APFixedPoint APFixedPoint::add(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  APSInt ThisVal = ConvertedThis.getValue();
182  APSInt OtherVal = ConvertedOther.getValue();
183  bool Overflowed = false;
184
185  APSInt Result;
186  if (CommonFXSema.isSaturated()) {
187    Result = CommonFXSema.isSigned() ? ThisVal.sadd_sat(OtherVal)
188                                     : ThisVal.uadd_sat(OtherVal);
189  } else {
190    Result = ThisVal.isSigned() ? ThisVal.sadd_ov(OtherVal, Overflowed)
191                                : ThisVal.uadd_ov(OtherVal, Overflowed);
192  }
193
194  if (Overflow)
195    *Overflow = Overflowed;
196
197  return APFixedPoint(Result, CommonFXSema);
198}
199
200APFixedPoint APFixedPoint::sub(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  APSInt ThisVal = ConvertedThis.getValue();
206  APSInt OtherVal = ConvertedOther.getValue();
207  bool Overflowed = false;
208
209  APSInt Result;
210  if (CommonFXSema.isSaturated()) {
211    Result = CommonFXSema.isSigned() ? ThisVal.ssub_sat(OtherVal)
212                                     : ThisVal.usub_sat(OtherVal);
213  } else {
214    Result = ThisVal.isSigned() ? ThisVal.ssub_ov(OtherVal, Overflowed)
215                                : ThisVal.usub_ov(OtherVal, Overflowed);
216  }
217
218  if (Overflow)
219    *Overflow = Overflowed;
220
221  return APFixedPoint(Result, CommonFXSema);
222}
223
224APFixedPoint APFixedPoint::mul(const APFixedPoint &Other,
225                               bool *Overflow) const {
226  auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
227  APFixedPoint ConvertedThis = convert(CommonFXSema);
228  APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
229  APSInt ThisVal = ConvertedThis.getValue();
230  APSInt OtherVal = ConvertedOther.getValue();
231  bool Overflowed = false;
232
233  // Widen the LHS and RHS so we can perform a full multiplication.
234  unsigned Wide = CommonFXSema.getWidth() * 2;
235  if (CommonFXSema.isSigned()) {
236    ThisVal = ThisVal.sextOrSelf(Wide);
237    OtherVal = OtherVal.sextOrSelf(Wide);
238  } else {
239    ThisVal = ThisVal.zextOrSelf(Wide);
240    OtherVal = OtherVal.zextOrSelf(Wide);
241  }
242
243  // Perform the full multiplication and downscale to get the same scale.
244  //
245  // Note that the right shifts here perform an implicit downwards rounding.
246  // This rounding could discard bits that would technically place the result
247  // outside the representable range. We interpret the spec as allowing us to
248  // perform the rounding step first, avoiding the overflow case that would
249  // arise.
250  APSInt Result;
251  if (CommonFXSema.isSigned())
252    Result = ThisVal.smul_ov(OtherVal, Overflowed)
253                    .ashr(CommonFXSema.getScale());
254  else
255    Result = ThisVal.umul_ov(OtherVal, Overflowed)
256                    .lshr(CommonFXSema.getScale());
257  assert(!Overflowed && "Full multiplication cannot overflow!");
258  Result.setIsSigned(CommonFXSema.isSigned());
259
260  // If our result lies outside of the representative range of the common
261  // semantic, we either have overflow or saturation.
262  APSInt Max = APFixedPoint::getMax(CommonFXSema).getValue()
263                                                 .extOrTrunc(Wide);
264  APSInt Min = APFixedPoint::getMin(CommonFXSema).getValue()
265                                                 .extOrTrunc(Wide);
266  if (CommonFXSema.isSaturated()) {
267    if (Result < Min)
268      Result = Min;
269    else if (Result > Max)
270      Result = Max;
271  } else
272    Overflowed = Result < Min || Result > Max;
273
274  if (Overflow)
275    *Overflow = Overflowed;
276
277  return APFixedPoint(Result.sextOrTrunc(CommonFXSema.getWidth()),
278                      CommonFXSema);
279}
280
281APFixedPoint APFixedPoint::div(const APFixedPoint &Other,
282                               bool *Overflow) const {
283  auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
284  APFixedPoint ConvertedThis = convert(CommonFXSema);
285  APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
286  APSInt ThisVal = ConvertedThis.getValue();
287  APSInt OtherVal = ConvertedOther.getValue();
288  bool Overflowed = false;
289
290  // Widen the LHS and RHS so we can perform a full division.
291  unsigned Wide = CommonFXSema.getWidth() * 2;
292  if (CommonFXSema.isSigned()) {
293    ThisVal = ThisVal.sextOrSelf(Wide);
294    OtherVal = OtherVal.sextOrSelf(Wide);
295  } else {
296    ThisVal = ThisVal.zextOrSelf(Wide);
297    OtherVal = OtherVal.zextOrSelf(Wide);
298  }
299
300  // Upscale to compensate for the loss of precision from division, and
301  // perform the full division.
302  ThisVal = ThisVal.shl(CommonFXSema.getScale());
303  APSInt Result;
304  if (CommonFXSema.isSigned()) {
305    APInt Rem;
306    APInt::sdivrem(ThisVal, OtherVal, Result, Rem);
307    // If the quotient is negative and the remainder is nonzero, round
308    // towards negative infinity by subtracting epsilon from the result.
309    if (ThisVal.isNegative() != OtherVal.isNegative() && !Rem.isNullValue())
310      Result = Result - 1;
311  } else
312    Result = ThisVal.udiv(OtherVal);
313  Result.setIsSigned(CommonFXSema.isSigned());
314
315  // If our result lies outside of the representative range of the common
316  // semantic, we either have overflow or saturation.
317  APSInt Max = APFixedPoint::getMax(CommonFXSema).getValue()
318                                                 .extOrTrunc(Wide);
319  APSInt Min = APFixedPoint::getMin(CommonFXSema).getValue()
320                                                 .extOrTrunc(Wide);
321  if (CommonFXSema.isSaturated()) {
322    if (Result < Min)
323      Result = Min;
324    else if (Result > Max)
325      Result = Max;
326  } else
327    Overflowed = Result < Min || Result > Max;
328
329  if (Overflow)
330    *Overflow = Overflowed;
331
332  return APFixedPoint(Result.sextOrTrunc(CommonFXSema.getWidth()),
333                      CommonFXSema);
334}
335
336APFixedPoint APFixedPoint::shl(unsigned Amt, bool *Overflow) const {
337  APSInt ThisVal = Val;
338  bool Overflowed = false;
339
340  // Widen the LHS.
341  unsigned Wide = Sema.getWidth() * 2;
342  if (Sema.isSigned())
343    ThisVal = ThisVal.sextOrSelf(Wide);
344  else
345    ThisVal = ThisVal.zextOrSelf(Wide);
346
347  // Clamp the shift amount at the original width, and perform the shift.
348  Amt = std::min(Amt, ThisVal.getBitWidth());
349  APSInt Result = ThisVal << Amt;
350  Result.setIsSigned(Sema.isSigned());
351
352  // If our result lies outside of the representative range of the
353  // semantic, we either have overflow or saturation.
354  APSInt Max = APFixedPoint::getMax(Sema).getValue().extOrTrunc(Wide);
355  APSInt Min = APFixedPoint::getMin(Sema).getValue().extOrTrunc(Wide);
356  if (Sema.isSaturated()) {
357    if (Result < Min)
358      Result = Min;
359    else if (Result > Max)
360      Result = Max;
361  } else
362    Overflowed = Result < Min || Result > Max;
363
364  if (Overflow)
365    *Overflow = Overflowed;
366
367  return APFixedPoint(Result.sextOrTrunc(Sema.getWidth()), Sema);
368}
369
370void APFixedPoint::toString(SmallVectorImpl<char> &Str) const {
371  APSInt Val = getValue();
372  unsigned Scale = getScale();
373
374  if (Val.isSigned() && Val.isNegative() && Val != -Val) {
375    Val = -Val;
376    Str.push_back('-');
377  }
378
379  APSInt IntPart = Val >> Scale;
380
381  // Add 4 digits to hold the value after multiplying 10 (the radix)
382  unsigned Width = Val.getBitWidth() + 4;
383  APInt FractPart = Val.zextOrTrunc(Scale).zext(Width);
384  APInt FractPartMask = APInt::getAllOnesValue(Scale).zext(Width);
385  APInt RadixInt = APInt(Width, 10);
386
387  IntPart.toString(Str, /*Radix=*/10);
388  Str.push_back('.');
389  do {
390    (FractPart * RadixInt)
391        .lshr(Scale)
392        .toString(Str, /*Radix=*/10, Val.isSigned());
393    FractPart = (FractPart * RadixInt) & FractPartMask;
394  } while (FractPart != 0);
395}
396
397APFixedPoint APFixedPoint::negate(bool *Overflow) const {
398  if (!isSaturated()) {
399    if (Overflow)
400      *Overflow =
401          (!isSigned() && Val != 0) || (isSigned() && Val.isMinSignedValue());
402    return APFixedPoint(-Val, Sema);
403  }
404
405  // We never overflow for saturation
406  if (Overflow)
407    *Overflow = false;
408
409  if (isSigned())
410    return Val.isMinSignedValue() ? getMax(Sema) : APFixedPoint(-Val, Sema);
411  else
412    return APFixedPoint(Sema);
413}
414
415APSInt APFixedPoint::convertToInt(unsigned DstWidth, bool DstSign,
416                                  bool *Overflow) const {
417  APSInt Result = getIntPart();
418  unsigned SrcWidth = getWidth();
419
420  APSInt DstMin = APSInt::getMinValue(DstWidth, !DstSign);
421  APSInt DstMax = APSInt::getMaxValue(DstWidth, !DstSign);
422
423  if (SrcWidth < DstWidth) {
424    Result = Result.extend(DstWidth);
425  } else if (SrcWidth > DstWidth) {
426    DstMin = DstMin.extend(SrcWidth);
427    DstMax = DstMax.extend(SrcWidth);
428  }
429
430  if (Overflow) {
431    if (Result.isSigned() && !DstSign) {
432      *Overflow = Result.isNegative() || Result.ugt(DstMax);
433    } else if (Result.isUnsigned() && DstSign) {
434      *Overflow = Result.ugt(DstMax);
435    } else {
436      *Overflow = Result < DstMin || Result > DstMax;
437    }
438  }
439
440  Result.setIsSigned(DstSign);
441  return Result.extOrTrunc(DstWidth);
442}
443
444const fltSemantics *APFixedPoint::promoteFloatSemantics(const fltSemantics *S) {
445  if (S == &APFloat::BFloat())
446    return &APFloat::IEEEdouble();
447  else if (S == &APFloat::IEEEhalf())
448    return &APFloat::IEEEsingle();
449  else if (S == &APFloat::IEEEsingle())
450    return &APFloat::IEEEdouble();
451  else if (S == &APFloat::IEEEdouble())
452    return &APFloat::IEEEquad();
453  llvm_unreachable("Could not promote float type!");
454}
455
456APFloat APFixedPoint::convertToFloat(const fltSemantics &FloatSema) const {
457  // For some operations, rounding mode has an effect on the result, while
458  // other operations are lossless and should never result in rounding.
459  // To signify which these operations are, we define two rounding modes here.
460  APFloat::roundingMode RM = APFloat::rmNearestTiesToEven;
461  APFloat::roundingMode LosslessRM = APFloat::rmTowardZero;
462
463  // Make sure that we are operating in a type that works with this fixed-point
464  // semantic.
465  const fltSemantics *OpSema = &FloatSema;
466  while (!Sema.fitsInFloatSemantics(*OpSema))
467    OpSema = promoteFloatSemantics(OpSema);
468
469  // Convert the fixed point value bits as an integer. If the floating point
470  // value does not have the required precision, we will round according to the
471  // given mode.
472  APFloat Flt(*OpSema);
473  APFloat::opStatus S = Flt.convertFromAPInt(Val, Sema.isSigned(), RM);
474
475  // If we cared about checking for precision loss, we could look at this
476  // status.
477  (void)S;
478
479  // Scale down the integer value in the float to match the correct scaling
480  // factor.
481  APFloat ScaleFactor(std::pow(2, -(int)Sema.getScale()));
482  bool Ignored;
483  ScaleFactor.convert(*OpSema, LosslessRM, &Ignored);
484  Flt.multiply(ScaleFactor, LosslessRM);
485
486  if (OpSema != &FloatSema)
487    Flt.convert(FloatSema, RM, &Ignored);
488
489  return Flt;
490}
491
492APFixedPoint APFixedPoint::getFromIntValue(const APSInt &Value,
493                                           const FixedPointSemantics &DstFXSema,
494                                           bool *Overflow) {
495  FixedPointSemantics IntFXSema = FixedPointSemantics::GetIntegerSemantics(
496      Value.getBitWidth(), Value.isSigned());
497  return APFixedPoint(Value, IntFXSema).convert(DstFXSema, Overflow);
498}
499
500APFixedPoint
501APFixedPoint::getFromFloatValue(const APFloat &Value,
502                                const FixedPointSemantics &DstFXSema,
503                                bool *Overflow) {
504  // For some operations, rounding mode has an effect on the result, while
505  // other operations are lossless and should never result in rounding.
506  // To signify which these operations are, we define two rounding modes here,
507  // even though they are the same mode.
508  APFloat::roundingMode RM = APFloat::rmTowardZero;
509  APFloat::roundingMode LosslessRM = APFloat::rmTowardZero;
510
511  const fltSemantics &FloatSema = Value.getSemantics();
512
513  if (Value.isNaN()) {
514    // Handle NaN immediately.
515    if (Overflow)
516      *Overflow = true;
517    return APFixedPoint(DstFXSema);
518  }
519
520  // Make sure that we are operating in a type that works with this fixed-point
521  // semantic.
522  const fltSemantics *OpSema = &FloatSema;
523  while (!DstFXSema.fitsInFloatSemantics(*OpSema))
524    OpSema = promoteFloatSemantics(OpSema);
525
526  APFloat Val = Value;
527
528  bool Ignored;
529  if (&FloatSema != OpSema)
530    Val.convert(*OpSema, LosslessRM, &Ignored);
531
532  // Scale up the float so that the 'fractional' part of the mantissa ends up in
533  // the integer range instead. Rounding mode is irrelevant here.
534  // It is fine if this overflows to infinity even for saturating types,
535  // since we will use floating point comparisons to check for saturation.
536  APFloat ScaleFactor(std::pow(2, DstFXSema.getScale()));
537  ScaleFactor.convert(*OpSema, LosslessRM, &Ignored);
538  Val.multiply(ScaleFactor, LosslessRM);
539
540  // Convert to the integral representation of the value. This rounding mode
541  // is significant.
542  APSInt Res(DstFXSema.getWidth(), !DstFXSema.isSigned());
543  Val.convertToInteger(Res, RM, &Ignored);
544
545  // Round the integral value and scale back. This makes the
546  // overflow calculations below work properly. If we do not round here,
547  // we risk checking for overflow with a value that is outside the
548  // representable range of the fixed-point semantic even though no overflow
549  // would occur had we rounded first.
550  ScaleFactor = APFloat(std::pow(2, -(int)DstFXSema.getScale()));
551  ScaleFactor.convert(*OpSema, LosslessRM, &Ignored);
552  Val.roundToIntegral(RM);
553  Val.multiply(ScaleFactor, LosslessRM);
554
555  // Check for overflow/saturation by checking if the floating point value
556  // is outside the range representable by the fixed-point value.
557  APFloat FloatMax = getMax(DstFXSema).convertToFloat(*OpSema);
558  APFloat FloatMin = getMin(DstFXSema).convertToFloat(*OpSema);
559  bool Overflowed = false;
560  if (DstFXSema.isSaturated()) {
561    if (Val > FloatMax)
562      Res = getMax(DstFXSema).getValue();
563    else if (Val < FloatMin)
564      Res = getMin(DstFXSema).getValue();
565  } else
566    Overflowed = Val > FloatMax || Val < FloatMin;
567
568  if (Overflow)
569    *Overflow = Overflowed;
570
571  return APFixedPoint(Res, DstFXSema);
572}
573
574} // namespace llvm
575