llvm/lib/Support/APFixedPoint.cpp - llvm-project - Git at Google

 //===- APFixedPoint.cpp - Fixed point constant handling ---------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 /// \file
 /// Defines the implementation for the fixed point number interface.
 //
 //===----------------------------------------------------------------------===//

 #include "llvm/ADT/APFixedPoint.h"
 #include "llvm/ADT/APFloat.h"

 namespace llvm {

 APFixedPoint APFixedPoint::convert(const FixedPointSemantics &DstSema,
                                    bool *Overflow) const {
   APSInt NewVal = Val;
   unsigned DstWidth = DstSema.getWidth();
   unsigned DstScale = DstSema.getScale();
   bool Upscaling = DstScale > getScale();
   if (Overflow)
     *Overflow = false;

   if (Upscaling) {
     NewVal = NewVal.extend(NewVal.getBitWidth() + DstScale - getScale());
     NewVal <<= (DstScale - getScale());
   } else {
     NewVal >>= (getScale() - DstScale);
   }

   auto Mask = APInt::getBitsSetFrom(
       NewVal.getBitWidth(),
       std::min(DstScale + DstSema.getIntegralBits(), NewVal.getBitWidth()));
   APInt Masked(NewVal & Mask);

   // Change in the bits above the sign
   if (!(Masked == Mask || Masked == 0)) {
     // Found overflow in the bits above the sign
     if (DstSema.isSaturated())
       NewVal = NewVal.isNegative() ? Mask : ~Mask;
     else if (Overflow)
       *Overflow = true;
   }

   // If the dst semantics are unsigned, but our value is signed and negative, we
   // clamp to zero.
   if (!DstSema.isSigned() && NewVal.isSigned() && NewVal.isNegative()) {
     // Found negative overflow for unsigned result
     if (DstSema.isSaturated())
       NewVal = 0;
     else if (Overflow)
       *Overflow = true;
   }

   NewVal = NewVal.extOrTrunc(DstWidth);
   NewVal.setIsSigned(DstSema.isSigned());
   return APFixedPoint(NewVal, DstSema);
 }

 int APFixedPoint::compare(const APFixedPoint &Other) const {
   APSInt ThisVal = getValue();
   APSInt OtherVal = Other.getValue();
   bool ThisSigned = Val.isSigned();
   bool OtherSigned = OtherVal.isSigned();
   unsigned OtherScale = Other.getScale();
   unsigned OtherWidth = OtherVal.getBitWidth();

   unsigned CommonWidth = std::max(Val.getBitWidth(), OtherWidth);

   // Prevent overflow in the event the widths are the same but the scales differ
   CommonWidth += getScale() >= OtherScale ? getScale() - OtherScale
                                           : OtherScale - getScale();

   ThisVal = ThisVal.extOrTrunc(CommonWidth);
   OtherVal = OtherVal.extOrTrunc(CommonWidth);

   unsigned CommonScale = std::max(getScale(), OtherScale);
   ThisVal = ThisVal.shl(CommonScale - getScale());
   OtherVal = OtherVal.shl(CommonScale - OtherScale);

   if (ThisSigned && OtherSigned) {
     if (ThisVal.sgt(OtherVal))
       return 1;
     else if (ThisVal.slt(OtherVal))
       return -1;
   } else if (!ThisSigned && !OtherSigned) {
     if (ThisVal.ugt(OtherVal))
       return 1;
     else if (ThisVal.ult(OtherVal))
       return -1;
   } else if (ThisSigned && !OtherSigned) {
     if (ThisVal.isSignBitSet())
       return -1;
     else if (ThisVal.ugt(OtherVal))
       return 1;
     else if (ThisVal.ult(OtherVal))
       return -1;
   } else {
     // !ThisSigned && OtherSigned
     if (OtherVal.isSignBitSet())
       return 1;
     else if (ThisVal.ugt(OtherVal))
       return 1;
     else if (ThisVal.ult(OtherVal))
       return -1;
   }

   return 0;
 }

 APFixedPoint APFixedPoint::getMax(const FixedPointSemantics &Sema) {
   bool IsUnsigned = !Sema.isSigned();
   auto Val = APSInt::getMaxValue(Sema.getWidth(), IsUnsigned);
   if (IsUnsigned && Sema.hasUnsignedPadding())
     Val = Val.lshr(1);
   return APFixedPoint(Val, Sema);
 }

 APFixedPoint APFixedPoint::getMin(const FixedPointSemantics &Sema) {
   auto Val = APSInt::getMinValue(Sema.getWidth(), !Sema.isSigned());
   return APFixedPoint(Val, Sema);
 }

 bool FixedPointSemantics::fitsInFloatSemantics(
     const fltSemantics &FloatSema) const {
   // A fixed point semantic fits in a floating point semantic if the maximum
   // and minimum values as integers of the fixed point semantic can fit in the
   // floating point semantic.

   // If these values do not fit, then a floating point rescaling of the true
   // maximum/minimum value will not fit either, so the floating point semantic
   // cannot be used to perform such a rescaling.

   APSInt MaxInt = APFixedPoint::getMax(*this).getValue();
   APFloat F(FloatSema);
   APFloat::opStatus Status = F.convertFromAPInt(MaxInt, MaxInt.isSigned(),
                                                 APFloat::rmNearestTiesToAway);
   if ((Status & APFloat::opOverflow) || !isSigned())
     return !(Status & APFloat::opOverflow);

   APSInt MinInt = APFixedPoint::getMin(*this).getValue();
   Status = F.convertFromAPInt(MinInt, MinInt.isSigned(),
                               APFloat::rmNearestTiesToAway);
   return !(Status & APFloat::opOverflow);
 }

 FixedPointSemantics FixedPointSemantics::getCommonSemantics(
     const FixedPointSemantics &Other) const {
   unsigned CommonScale = std::max(getScale(), Other.getScale());
   unsigned CommonWidth =
       std::max(getIntegralBits(), Other.getIntegralBits()) + CommonScale;

   bool ResultIsSigned = isSigned() || Other.isSigned();
   bool ResultIsSaturated = isSaturated() || Other.isSaturated();
   bool ResultHasUnsignedPadding = false;
   if (!ResultIsSigned) {
     // Both are unsigned.
     ResultHasUnsignedPadding = hasUnsignedPadding() &&
                                Other.hasUnsignedPadding() && !ResultIsSaturated;
   }

   // If the result is signed, add an extra bit for the sign. Otherwise, if it is
   // unsigned and has unsigned padding, we only need to add the extra padding
   // bit back if we are not saturating.
   if (ResultIsSigned || ResultHasUnsignedPadding)
     CommonWidth++;

   return FixedPointSemantics(CommonWidth, CommonScale, ResultIsSigned,
                              ResultIsSaturated, ResultHasUnsignedPadding);
 }

 APFixedPoint APFixedPoint::add(const APFixedPoint &Other,
                                bool *Overflow) const {
   auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
   APFixedPoint ConvertedThis = convert(CommonFXSema);
   APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
   APSInt ThisVal = ConvertedThis.getValue();
   APSInt OtherVal = ConvertedOther.getValue();
   bool Overflowed = false;

   APSInt Result;
   if (CommonFXSema.isSaturated()) {
     Result = CommonFXSema.isSigned() ? ThisVal.sadd_sat(OtherVal)
                                      : ThisVal.uadd_sat(OtherVal);
   } else {
     Result = ThisVal.isSigned() ? ThisVal.sadd_ov(OtherVal, Overflowed)
                                 : ThisVal.uadd_ov(OtherVal, Overflowed);
   }

   if (Overflow)
     *Overflow = Overflowed;

   return APFixedPoint(Result, CommonFXSema);
 }

 APFixedPoint APFixedPoint::sub(const APFixedPoint &Other,
                                bool *Overflow) const {
   auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
   APFixedPoint ConvertedThis = convert(CommonFXSema);
   APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
   APSInt ThisVal = ConvertedThis.getValue();
   APSInt OtherVal = ConvertedOther.getValue();
   bool Overflowed = false;

   APSInt Result;
   if (CommonFXSema.isSaturated()) {
     Result = CommonFXSema.isSigned() ? ThisVal.ssub_sat(OtherVal)
                                      : ThisVal.usub_sat(OtherVal);
   } else {
     Result = ThisVal.isSigned() ? ThisVal.ssub_ov(OtherVal, Overflowed)
                                 : ThisVal.usub_ov(OtherVal, Overflowed);
   }

   if (Overflow)
     *Overflow = Overflowed;

   return APFixedPoint(Result, CommonFXSema);
 }

 APFixedPoint APFixedPoint::mul(const APFixedPoint &Other,
                                bool *Overflow) const {
   auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
   APFixedPoint ConvertedThis = convert(CommonFXSema);
   APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
   APSInt ThisVal = ConvertedThis.getValue();
   APSInt OtherVal = ConvertedOther.getValue();
   bool Overflowed = false;

   // Widen the LHS and RHS so we can perform a full multiplication.
   unsigned Wide = CommonFXSema.getWidth() * 2;
   if (CommonFXSema.isSigned()) {
     ThisVal = ThisVal.sextOrSelf(Wide);
     OtherVal = OtherVal.sextOrSelf(Wide);
   } else {
     ThisVal = ThisVal.zextOrSelf(Wide);
     OtherVal = OtherVal.zextOrSelf(Wide);
   }

   // Perform the full multiplication and downscale to get the same scale.
   //
   // Note that the right shifts here perform an implicit downwards rounding.
   // This rounding could discard bits that would technically place the result
   // outside the representable range. We interpret the spec as allowing us to
   // perform the rounding step first, avoiding the overflow case that would
   // arise.
   APSInt Result;
   if (CommonFXSema.isSigned())
     Result = ThisVal.smul_ov(OtherVal, Overflowed)
                     .ashr(CommonFXSema.getScale());
   else
     Result = ThisVal.umul_ov(OtherVal, Overflowed)
                     .lshr(CommonFXSema.getScale());
   assert(!Overflowed && "Full multiplication cannot overflow!");
   Result.setIsSigned(CommonFXSema.isSigned());

   // If our result lies outside of the representative range of the common
   // semantic, we either have overflow or saturation.
   APSInt Max = APFixedPoint::getMax(CommonFXSema).getValue()
                                                  .extOrTrunc(Wide);
   APSInt Min = APFixedPoint::getMin(CommonFXSema).getValue()
                                                  .extOrTrunc(Wide);
   if (CommonFXSema.isSaturated()) {
     if (Result < Min)
       Result = Min;
     else if (Result > Max)
       Result = Max;
   } else
     Overflowed = Result < Min || Result > Max;

   if (Overflow)
     *Overflow = Overflowed;

   return APFixedPoint(Result.sextOrTrunc(CommonFXSema.getWidth()),
                       CommonFXSema);
 }

 APFixedPoint APFixedPoint::div(const APFixedPoint &Other,
                                bool *Overflow) const {
   auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
   APFixedPoint ConvertedThis = convert(CommonFXSema);
   APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
   APSInt ThisVal = ConvertedThis.getValue();
   APSInt OtherVal = ConvertedOther.getValue();
   bool Overflowed = false;

   // Widen the LHS and RHS so we can perform a full division.
   unsigned Wide = CommonFXSema.getWidth() * 2;
   if (CommonFXSema.isSigned()) {
     ThisVal = ThisVal.sextOrSelf(Wide);
     OtherVal = OtherVal.sextOrSelf(Wide);
   } else {
     ThisVal = ThisVal.zextOrSelf(Wide);
     OtherVal = OtherVal.zextOrSelf(Wide);
   }

   // Upscale to compensate for the loss of precision from division, and
   // perform the full division.
   ThisVal = ThisVal.shl(CommonFXSema.getScale());
   APSInt Result;
   if (CommonFXSema.isSigned()) {
     APInt Rem;
     APInt::sdivrem(ThisVal, OtherVal, Result, Rem);
     // If the quotient is negative and the remainder is nonzero, round
     // towards negative infinity by subtracting epsilon from the result.
     if (ThisVal.isNegative() != OtherVal.isNegative() && !Rem.isZero())
       Result = Result - 1;
   } else
     Result = ThisVal.udiv(OtherVal);
   Result.setIsSigned(CommonFXSema.isSigned());

   // If our result lies outside of the representative range of the common
   // semantic, we either have overflow or saturation.
   APSInt Max = APFixedPoint::getMax(CommonFXSema).getValue()
                                                  .extOrTrunc(Wide);
   APSInt Min = APFixedPoint::getMin(CommonFXSema).getValue()
                                                  .extOrTrunc(Wide);
   if (CommonFXSema.isSaturated()) {
     if (Result < Min)
       Result = Min;
     else if (Result > Max)
       Result = Max;
   } else
     Overflowed = Result < Min || Result > Max;

   if (Overflow)
     *Overflow = Overflowed;

   return APFixedPoint(Result.sextOrTrunc(CommonFXSema.getWidth()),
                       CommonFXSema);
 }

 APFixedPoint APFixedPoint::shl(unsigned Amt, bool *Overflow) const {
   APSInt ThisVal = Val;
   bool Overflowed = false;

   // Widen the LHS.
   unsigned Wide = Sema.getWidth() * 2;
   if (Sema.isSigned())
     ThisVal = ThisVal.sextOrSelf(Wide);
   else
     ThisVal = ThisVal.zextOrSelf(Wide);

   // Clamp the shift amount at the original width, and perform the shift.
   Amt = std::min(Amt, ThisVal.getBitWidth());
   APSInt Result = ThisVal << Amt;
   Result.setIsSigned(Sema.isSigned());

   // If our result lies outside of the representative range of the
   // semantic, we either have overflow or saturation.
   APSInt Max = APFixedPoint::getMax(Sema).getValue().extOrTrunc(Wide);
   APSInt Min = APFixedPoint::getMin(Sema).getValue().extOrTrunc(Wide);
   if (Sema.isSaturated()) {
     if (Result < Min)
       Result = Min;
     else if (Result > Max)
       Result = Max;
   } else
     Overflowed = Result < Min || Result > Max;

   if (Overflow)
     *Overflow = Overflowed;

   return APFixedPoint(Result.sextOrTrunc(Sema.getWidth()), Sema);
 }

 void APFixedPoint::toString(SmallVectorImpl<char> &Str) const {
   APSInt Val = getValue();
   unsigned Scale = getScale();

   if (Val.isSigned() && Val.isNegative() && Val != -Val) {
     Val = -Val;
     Str.push_back('-');
   }

   APSInt IntPart = Val >> Scale;

   // Add 4 digits to hold the value after multiplying 10 (the radix)
   unsigned Width = Val.getBitWidth() + 4;
   APInt FractPart = Val.zextOrTrunc(Scale).zext(Width);
   APInt FractPartMask = APInt::getAllOnes(Scale).zext(Width);
   APInt RadixInt = APInt(Width, 10);

   IntPart.toString(Str, /*Radix=*/10);
   Str.push_back('.');
   do {
     (FractPart * RadixInt)
         .lshr(Scale)
         .toString(Str, /*Radix=*/10, Val.isSigned());
     FractPart = (FractPart * RadixInt) & FractPartMask;
   } while (FractPart != 0);
 }

 APFixedPoint APFixedPoint::negate(bool *Overflow) const {
   if (!isSaturated()) {
     if (Overflow)
       *Overflow =
           (!isSigned() && Val != 0) || (isSigned() && Val.isMinSignedValue());
     return APFixedPoint(-Val, Sema);
   }

   // We never overflow for saturation
   if (Overflow)
     *Overflow = false;

   if (isSigned())
     return Val.isMinSignedValue() ? getMax(Sema) : APFixedPoint(-Val, Sema);
   else
     return APFixedPoint(Sema);
 }

 APSInt APFixedPoint::convertToInt(unsigned DstWidth, bool DstSign,
                                   bool *Overflow) const {
   APSInt Result = getIntPart();
   unsigned SrcWidth = getWidth();

   APSInt DstMin = APSInt::getMinValue(DstWidth, !DstSign);
   APSInt DstMax = APSInt::getMaxValue(DstWidth, !DstSign);

   if (SrcWidth < DstWidth) {
     Result = Result.extend(DstWidth);
   } else if (SrcWidth > DstWidth) {
     DstMin = DstMin.extend(SrcWidth);
     DstMax = DstMax.extend(SrcWidth);
   }

   if (Overflow) {
     if (Result.isSigned() && !DstSign) {
       *Overflow = Result.isNegative() || Result.ugt(DstMax);
     } else if (Result.isUnsigned() && DstSign) {
       *Overflow = Result.ugt(DstMax);
     } else {
       *Overflow = Result < DstMin || Result > DstMax;
     }
   }

   Result.setIsSigned(DstSign);
   return Result.extOrTrunc(DstWidth);
 }

 const fltSemantics *APFixedPoint::promoteFloatSemantics(const fltSemantics *S) {
   if (S == &APFloat::BFloat())
     return &APFloat::IEEEdouble();
   else if (S == &APFloat::IEEEhalf())
     return &APFloat::IEEEsingle();
   else if (S == &APFloat::IEEEsingle())
     return &APFloat::IEEEdouble();
   else if (S == &APFloat::IEEEdouble())
     return &APFloat::IEEEquad();
   llvm_unreachable("Could not promote float type!");
 }

 APFloat APFixedPoint::convertToFloat(const fltSemantics &FloatSema) const {
   // For some operations, rounding mode has an effect on the result, while
   // other operations are lossless and should never result in rounding.
   // To signify which these operations are, we define two rounding modes here.
   APFloat::roundingMode RM = APFloat::rmNearestTiesToEven;
   APFloat::roundingMode LosslessRM = APFloat::rmTowardZero;

   // Make sure that we are operating in a type that works with this fixed-point
   // semantic.
   const fltSemantics *OpSema = &FloatSema;
   while (!Sema.fitsInFloatSemantics(*OpSema))
     OpSema = promoteFloatSemantics(OpSema);

   // Convert the fixed point value bits as an integer. If the floating point
   // value does not have the required precision, we will round according to the
   // given mode.
   APFloat Flt(*OpSema);
   APFloat::opStatus S = Flt.convertFromAPInt(Val, Sema.isSigned(), RM);

   // If we cared about checking for precision loss, we could look at this
   // status.
   (void)S;

   // Scale down the integer value in the float to match the correct scaling
   // factor.
   APFloat ScaleFactor(std::pow(2, -(int)Sema.getScale()));
   bool Ignored;
   ScaleFactor.convert(*OpSema, LosslessRM, &Ignored);
   Flt.multiply(ScaleFactor, LosslessRM);

   if (OpSema != &FloatSema)
     Flt.convert(FloatSema, RM, &Ignored);

   return Flt;
 }

 APFixedPoint APFixedPoint::getFromIntValue(const APSInt &Value,
                                            const FixedPointSemantics &DstFXSema,
                                            bool *Overflow) {
   FixedPointSemantics IntFXSema = FixedPointSemantics::GetIntegerSemantics(
       Value.getBitWidth(), Value.isSigned());
   return APFixedPoint(Value, IntFXSema).convert(DstFXSema, Overflow);
 }

 APFixedPoint
 APFixedPoint::getFromFloatValue(const APFloat &Value,
                                 const FixedPointSemantics &DstFXSema,
                                 bool *Overflow) {
   // For some operations, rounding mode has an effect on the result, while
   // other operations are lossless and should never result in rounding.
   // To signify which these operations are, we define two rounding modes here,
   // even though they are the same mode.
   APFloat::roundingMode RM = APFloat::rmTowardZero;
   APFloat::roundingMode LosslessRM = APFloat::rmTowardZero;

   const fltSemantics &FloatSema = Value.getSemantics();

   if (Value.isNaN()) {
     // Handle NaN immediately.
     if (Overflow)
       *Overflow = true;
     return APFixedPoint(DstFXSema);
   }

   // Make sure that we are operating in a type that works with this fixed-point
   // semantic.
   const fltSemantics *OpSema = &FloatSema;
   while (!DstFXSema.fitsInFloatSemantics(*OpSema))
     OpSema = promoteFloatSemantics(OpSema);

   APFloat Val = Value;

   bool Ignored;
   if (&FloatSema != OpSema)
     Val.convert(*OpSema, LosslessRM, &Ignored);

   // Scale up the float so that the 'fractional' part of the mantissa ends up in
   // the integer range instead. Rounding mode is irrelevant here.
   // It is fine if this overflows to infinity even for saturating types,
   // since we will use floating point comparisons to check for saturation.
   APFloat ScaleFactor(std::pow(2, DstFXSema.getScale()));
   ScaleFactor.convert(*OpSema, LosslessRM, &Ignored);
   Val.multiply(ScaleFactor, LosslessRM);

   // Convert to the integral representation of the value. This rounding mode
   // is significant.
   APSInt Res(DstFXSema.getWidth(), !DstFXSema.isSigned());
   Val.convertToInteger(Res, RM, &Ignored);

   // Round the integral value and scale back. This makes the
   // overflow calculations below work properly. If we do not round here,
   // we risk checking for overflow with a value that is outside the
   // representable range of the fixed-point semantic even though no overflow
   // would occur had we rounded first.
   ScaleFactor = APFloat(std::pow(2, -(int)DstFXSema.getScale()));
   ScaleFactor.convert(*OpSema, LosslessRM, &Ignored);
   Val.roundToIntegral(RM);
   Val.multiply(ScaleFactor, LosslessRM);

   // Check for overflow/saturation by checking if the floating point value
   // is outside the range representable by the fixed-point value.
   APFloat FloatMax = getMax(DstFXSema).convertToFloat(*OpSema);
   APFloat FloatMin = getMin(DstFXSema).convertToFloat(*OpSema);
   bool Overflowed = false;
   if (DstFXSema.isSaturated()) {
     if (Val > FloatMax)
       Res = getMax(DstFXSema).getValue();
     else if (Val < FloatMin)
       Res = getMin(DstFXSema).getValue();
   } else
     Overflowed = Val > FloatMax || Val < FloatMin;

   if (Overflow)
     *Overflow = Overflowed;

   return APFixedPoint(Res, DstFXSema);
 }

 } // namespace llvm
	//===- APFixedPoint.cpp - Fixed point constant handling ---------- C++ --===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//
	//
	/// \file
	/// Defines the implementation for the fixed point number interface.
	//
	//===----------------------------------------------------------------------===//

	#include "llvm/ADT/APFixedPoint.h"
	#include "llvm/ADT/APFloat.h"

	namespace llvm {

	APFixedPoint APFixedPoint::convert(const FixedPointSemantics &DstSema,
	bool *Overflow) const {
	APSInt NewVal = Val;
	unsigned DstWidth = DstSema.getWidth();
	unsigned DstScale = DstSema.getScale();
	bool Upscaling = DstScale > getScale();
	if (Overflow)
	*Overflow = false;

	if (Upscaling) {
	NewVal = NewVal.extend(NewVal.getBitWidth() + DstScale - getScale());
	NewVal <<= (DstScale - getScale());
	} else {
	NewVal >>= (getScale() - DstScale);
	}

	auto Mask = APInt::getBitsSetFrom(
	NewVal.getBitWidth(),
	std::min(DstScale + DstSema.getIntegralBits(), NewVal.getBitWidth()));
	APInt Masked(NewVal & Mask);

	// Change in the bits above the sign
	if (!(Masked == Mask \|\| Masked == 0)) {
	// Found overflow in the bits above the sign
	if (DstSema.isSaturated())
	NewVal = NewVal.isNegative() ? Mask : ~Mask;
	else if (Overflow)
	*Overflow = true;
	}

	// If the dst semantics are unsigned, but our value is signed and negative, we
	// clamp to zero.
	if (!DstSema.isSigned() && NewVal.isSigned() && NewVal.isNegative()) {
	// Found negative overflow for unsigned result
	if (DstSema.isSaturated())
	NewVal = 0;
	else if (Overflow)
	*Overflow = true;
	}

	NewVal = NewVal.extOrTrunc(DstWidth);
	NewVal.setIsSigned(DstSema.isSigned());
	return APFixedPoint(NewVal, DstSema);
	}

	int APFixedPoint::compare(const APFixedPoint &Other) const {
	APSInt ThisVal = getValue();
	APSInt OtherVal = Other.getValue();
	bool ThisSigned = Val.isSigned();
	bool OtherSigned = OtherVal.isSigned();
	unsigned OtherScale = Other.getScale();
	unsigned OtherWidth = OtherVal.getBitWidth();

	unsigned CommonWidth = std::max(Val.getBitWidth(), OtherWidth);

	// Prevent overflow in the event the widths are the same but the scales differ
	CommonWidth += getScale() >= OtherScale ? getScale() - OtherScale
	: OtherScale - getScale();

	ThisVal = ThisVal.extOrTrunc(CommonWidth);
	OtherVal = OtherVal.extOrTrunc(CommonWidth);

	unsigned CommonScale = std::max(getScale(), OtherScale);
	ThisVal = ThisVal.shl(CommonScale - getScale());
	OtherVal = OtherVal.shl(CommonScale - OtherScale);

	if (ThisSigned && OtherSigned) {
	if (ThisVal.sgt(OtherVal))
	return 1;
	else if (ThisVal.slt(OtherVal))
	return -1;
	} else if (!ThisSigned && !OtherSigned) {
	if (ThisVal.ugt(OtherVal))
	return 1;
	else if (ThisVal.ult(OtherVal))
	return -1;
	} else if (ThisSigned && !OtherSigned) {
	if (ThisVal.isSignBitSet())
	return -1;
	else if (ThisVal.ugt(OtherVal))
	return 1;
	else if (ThisVal.ult(OtherVal))
	return -1;
	} else {
	// !ThisSigned && OtherSigned
	if (OtherVal.isSignBitSet())
	return 1;
	else if (ThisVal.ugt(OtherVal))
	return 1;
	else if (ThisVal.ult(OtherVal))
	return -1;
	}

	return 0;
	}

	APFixedPoint APFixedPoint::getMax(const FixedPointSemantics &Sema) {
	bool IsUnsigned = !Sema.isSigned();
	auto Val = APSInt::getMaxValue(Sema.getWidth(), IsUnsigned);
	if (IsUnsigned && Sema.hasUnsignedPadding())
	Val = Val.lshr(1);
	return APFixedPoint(Val, Sema);
	}

	APFixedPoint APFixedPoint::getMin(const FixedPointSemantics &Sema) {
	auto Val = APSInt::getMinValue(Sema.getWidth(), !Sema.isSigned());
	return APFixedPoint(Val, Sema);
	}

	bool FixedPointSemantics::fitsInFloatSemantics(
	const fltSemantics &FloatSema) const {
	// A fixed point semantic fits in a floating point semantic if the maximum
	// and minimum values as integers of the fixed point semantic can fit in the
	// floating point semantic.

	// If these values do not fit, then a floating point rescaling of the true
	// maximum/minimum value will not fit either, so the floating point semantic
	// cannot be used to perform such a rescaling.

	APSInt MaxInt = APFixedPoint::getMax(*this).getValue();
	APFloat F(FloatSema);
	APFloat::opStatus Status = F.convertFromAPInt(MaxInt, MaxInt.isSigned(),
	APFloat::rmNearestTiesToAway);
	if ((Status & APFloat::opOverflow) \|\| !isSigned())
	return !(Status & APFloat::opOverflow);

	APSInt MinInt = APFixedPoint::getMin(*this).getValue();
	Status = F.convertFromAPInt(MinInt, MinInt.isSigned(),
	APFloat::rmNearestTiesToAway);
	return !(Status & APFloat::opOverflow);
	}

	FixedPointSemantics FixedPointSemantics::getCommonSemantics(
	const FixedPointSemantics &Other) const {
	unsigned CommonScale = std::max(getScale(), Other.getScale());
	unsigned CommonWidth =
	std::max(getIntegralBits(), Other.getIntegralBits()) + CommonScale;

	bool ResultIsSigned = isSigned() \|\| Other.isSigned();
	bool ResultIsSaturated = isSaturated() \|\| Other.isSaturated();
	bool ResultHasUnsignedPadding = false;
	if (!ResultIsSigned) {
	// Both are unsigned.
	ResultHasUnsignedPadding = hasUnsignedPadding() &&
	Other.hasUnsignedPadding() && !ResultIsSaturated;
	}

	// If the result is signed, add an extra bit for the sign. Otherwise, if it is
	// unsigned and has unsigned padding, we only need to add the extra padding
	// bit back if we are not saturating.
	if (ResultIsSigned \|\| ResultHasUnsignedPadding)
	CommonWidth++;

	return FixedPointSemantics(CommonWidth, CommonScale, ResultIsSigned,
	ResultIsSaturated, ResultHasUnsignedPadding);
	}

	APFixedPoint APFixedPoint::add(const APFixedPoint &Other,
	bool *Overflow) const {
	auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
	APFixedPoint ConvertedThis = convert(CommonFXSema);
	APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
	APSInt ThisVal = ConvertedThis.getValue();
	APSInt OtherVal = ConvertedOther.getValue();
	bool Overflowed = false;

	APSInt Result;
	if (CommonFXSema.isSaturated()) {
	Result = CommonFXSema.isSigned() ? ThisVal.sadd_sat(OtherVal)
	: ThisVal.uadd_sat(OtherVal);
	} else {
	Result = ThisVal.isSigned() ? ThisVal.sadd_ov(OtherVal, Overflowed)
	: ThisVal.uadd_ov(OtherVal, Overflowed);
	}

	if (Overflow)
	*Overflow = Overflowed;

	return APFixedPoint(Result, CommonFXSema);
	}

	APFixedPoint APFixedPoint::sub(const APFixedPoint &Other,
	bool *Overflow) const {
	auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
	APFixedPoint ConvertedThis = convert(CommonFXSema);
	APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
	APSInt ThisVal = ConvertedThis.getValue();
	APSInt OtherVal = ConvertedOther.getValue();
	bool Overflowed = false;

	APSInt Result;
	if (CommonFXSema.isSaturated()) {
	Result = CommonFXSema.isSigned() ? ThisVal.ssub_sat(OtherVal)
	: ThisVal.usub_sat(OtherVal);
	} else {
	Result = ThisVal.isSigned() ? ThisVal.ssub_ov(OtherVal, Overflowed)
	: ThisVal.usub_ov(OtherVal, Overflowed);
	}

	if (Overflow)
	*Overflow = Overflowed;

	return APFixedPoint(Result, CommonFXSema);
	}

	APFixedPoint APFixedPoint::mul(const APFixedPoint &Other,
	bool *Overflow) const {
	auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
	APFixedPoint ConvertedThis = convert(CommonFXSema);
	APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
	APSInt ThisVal = ConvertedThis.getValue();
	APSInt OtherVal = ConvertedOther.getValue();
	bool Overflowed = false;

	// Widen the LHS and RHS so we can perform a full multiplication.
	unsigned Wide = CommonFXSema.getWidth() * 2;
	if (CommonFXSema.isSigned()) {
	ThisVal = ThisVal.sextOrSelf(Wide);
	OtherVal = OtherVal.sextOrSelf(Wide);
	} else {
	ThisVal = ThisVal.zextOrSelf(Wide);
	OtherVal = OtherVal.zextOrSelf(Wide);
	}

	// Perform the full multiplication and downscale to get the same scale.
	//
	// Note that the right shifts here perform an implicit downwards rounding.
	// This rounding could discard bits that would technically place the result
	// outside the representable range. We interpret the spec as allowing us to
	// perform the rounding step first, avoiding the overflow case that would
	// arise.
	APSInt Result;
	if (CommonFXSema.isSigned())
	Result = ThisVal.smul_ov(OtherVal, Overflowed)
	.ashr(CommonFXSema.getScale());
	else
	Result = ThisVal.umul_ov(OtherVal, Overflowed)
	.lshr(CommonFXSema.getScale());
	assert(!Overflowed && "Full multiplication cannot overflow!");
	Result.setIsSigned(CommonFXSema.isSigned());

	// If our result lies outside of the representative range of the common
	// semantic, we either have overflow or saturation.
	APSInt Max = APFixedPoint::getMax(CommonFXSema).getValue()
	.extOrTrunc(Wide);
	APSInt Min = APFixedPoint::getMin(CommonFXSema).getValue()
	.extOrTrunc(Wide);
	if (CommonFXSema.isSaturated()) {
	if (Result < Min)
	Result = Min;
	else if (Result > Max)
	Result = Max;
	} else
	Overflowed = Result < Min \|\| Result > Max;

	if (Overflow)
	*Overflow = Overflowed;

	return APFixedPoint(Result.sextOrTrunc(CommonFXSema.getWidth()),
	CommonFXSema);
	}

	APFixedPoint APFixedPoint::div(const APFixedPoint &Other,
	bool *Overflow) const {
	auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
	APFixedPoint ConvertedThis = convert(CommonFXSema);
	APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
	APSInt ThisVal = ConvertedThis.getValue();
	APSInt OtherVal = ConvertedOther.getValue();
	bool Overflowed = false;

	// Widen the LHS and RHS so we can perform a full division.
	unsigned Wide = CommonFXSema.getWidth() * 2;
	if (CommonFXSema.isSigned()) {
	ThisVal = ThisVal.sextOrSelf(Wide);
	OtherVal = OtherVal.sextOrSelf(Wide);
	} else {
	ThisVal = ThisVal.zextOrSelf(Wide);
	OtherVal = OtherVal.zextOrSelf(Wide);
	}

	// Upscale to compensate for the loss of precision from division, and
	// perform the full division.
	ThisVal = ThisVal.shl(CommonFXSema.getScale());
	APSInt Result;
	if (CommonFXSema.isSigned()) {
	APInt Rem;
	APInt::sdivrem(ThisVal, OtherVal, Result, Rem);
	// If the quotient is negative and the remainder is nonzero, round
	// towards negative infinity by subtracting epsilon from the result.
	if (ThisVal.isNegative() != OtherVal.isNegative() && !Rem.isZero())
	Result = Result - 1;
	} else
	Result = ThisVal.udiv(OtherVal);
	Result.setIsSigned(CommonFXSema.isSigned());

	// If our result lies outside of the representative range of the common
	// semantic, we either have overflow or saturation.
	APSInt Max = APFixedPoint::getMax(CommonFXSema).getValue()
	.extOrTrunc(Wide);
	APSInt Min = APFixedPoint::getMin(CommonFXSema).getValue()
	.extOrTrunc(Wide);
	if (CommonFXSema.isSaturated()) {
	if (Result < Min)
	Result = Min;
	else if (Result > Max)
	Result = Max;
	} else
	Overflowed = Result < Min \|\| Result > Max;

	if (Overflow)
	*Overflow = Overflowed;

	return APFixedPoint(Result.sextOrTrunc(CommonFXSema.getWidth()),
	CommonFXSema);
	}

	APFixedPoint APFixedPoint::shl(unsigned Amt, bool *Overflow) const {
	APSInt ThisVal = Val;
	bool Overflowed = false;

	// Widen the LHS.
	unsigned Wide = Sema.getWidth() * 2;
	if (Sema.isSigned())
	ThisVal = ThisVal.sextOrSelf(Wide);
	else
	ThisVal = ThisVal.zextOrSelf(Wide);

	// Clamp the shift amount at the original width, and perform the shift.
	Amt = std::min(Amt, ThisVal.getBitWidth());
	APSInt Result = ThisVal << Amt;
	Result.setIsSigned(Sema.isSigned());

	// If our result lies outside of the representative range of the
	// semantic, we either have overflow or saturation.
	APSInt Max = APFixedPoint::getMax(Sema).getValue().extOrTrunc(Wide);
	APSInt Min = APFixedPoint::getMin(Sema).getValue().extOrTrunc(Wide);
	if (Sema.isSaturated()) {
	if (Result < Min)
	Result = Min;
	else if (Result > Max)
	Result = Max;
	} else
	Overflowed = Result < Min \|\| Result > Max;

	if (Overflow)
	*Overflow = Overflowed;

	return APFixedPoint(Result.sextOrTrunc(Sema.getWidth()), Sema);
	}

	void APFixedPoint::toString(SmallVectorImpl<char> &Str) const {
	APSInt Val = getValue();
	unsigned Scale = getScale();

	if (Val.isSigned() && Val.isNegative() && Val != -Val) {
	Val = -Val;
	Str.push_back('-');
	}

	APSInt IntPart = Val >> Scale;

	// Add 4 digits to hold the value after multiplying 10 (the radix)
	unsigned Width = Val.getBitWidth() + 4;
	APInt FractPart = Val.zextOrTrunc(Scale).zext(Width);
	APInt FractPartMask = APInt::getAllOnes(Scale).zext(Width);
	APInt RadixInt = APInt(Width, 10);

	IntPart.toString(Str, /Radix=/10);
	Str.push_back('.');
	do {
	(FractPart * RadixInt)
	.lshr(Scale)
	.toString(Str, /Radix=/10, Val.isSigned());
	FractPart = (FractPart * RadixInt) & FractPartMask;
	} while (FractPart != 0);
	}

	APFixedPoint APFixedPoint::negate(bool *Overflow) const {
	if (!isSaturated()) {
	if (Overflow)
	*Overflow =
	(!isSigned() && Val != 0) \|\| (isSigned() && Val.isMinSignedValue());
	return APFixedPoint(-Val, Sema);
	}

	// We never overflow for saturation
	if (Overflow)
	*Overflow = false;

	if (isSigned())
	return Val.isMinSignedValue() ? getMax(Sema) : APFixedPoint(-Val, Sema);
	else
	return APFixedPoint(Sema);
	}

	APSInt APFixedPoint::convertToInt(unsigned DstWidth, bool DstSign,
	bool *Overflow) const {
	APSInt Result = getIntPart();
	unsigned SrcWidth = getWidth();

	APSInt DstMin = APSInt::getMinValue(DstWidth, !DstSign);
	APSInt DstMax = APSInt::getMaxValue(DstWidth, !DstSign);

	if (SrcWidth < DstWidth) {
	Result = Result.extend(DstWidth);
	} else if (SrcWidth > DstWidth) {
	DstMin = DstMin.extend(SrcWidth);
	DstMax = DstMax.extend(SrcWidth);
	}

	if (Overflow) {
	if (Result.isSigned() && !DstSign) {
	*Overflow = Result.isNegative() \|\| Result.ugt(DstMax);
	} else if (Result.isUnsigned() && DstSign) {
	*Overflow = Result.ugt(DstMax);
	} else {
	*Overflow = Result < DstMin \|\| Result > DstMax;
	}
	}

	Result.setIsSigned(DstSign);
	return Result.extOrTrunc(DstWidth);
	}

	const fltSemantics APFixedPoint::promoteFloatSemantics(const fltSemantics S) {
	if (S == &APFloat::BFloat())
	return &APFloat::IEEEdouble();
	else if (S == &APFloat::IEEEhalf())
	return &APFloat::IEEEsingle();
	else if (S == &APFloat::IEEEsingle())
	return &APFloat::IEEEdouble();
	else if (S == &APFloat::IEEEdouble())
	return &APFloat::IEEEquad();
	llvm_unreachable("Could not promote float type!");
	}

	APFloat APFixedPoint::convertToFloat(const fltSemantics &FloatSema) const {
	// For some operations, rounding mode has an effect on the result, while
	// other operations are lossless and should never result in rounding.
	// To signify which these operations are, we define two rounding modes here.
	APFloat::roundingMode RM = APFloat::rmNearestTiesToEven;
	APFloat::roundingMode LosslessRM = APFloat::rmTowardZero;

	// Make sure that we are operating in a type that works with this fixed-point
	// semantic.
	const fltSemantics *OpSema = &FloatSema;
	while (!Sema.fitsInFloatSemantics(*OpSema))
	OpSema = promoteFloatSemantics(OpSema);

	// Convert the fixed point value bits as an integer. If the floating point
	// value does not have the required precision, we will round according to the
	// given mode.
	APFloat Flt(*OpSema);
	APFloat::opStatus S = Flt.convertFromAPInt(Val, Sema.isSigned(), RM);

	// If we cared about checking for precision loss, we could look at this
	// status.
	(void)S;

	// Scale down the integer value in the float to match the correct scaling
	// factor.
	APFloat ScaleFactor(std::pow(2, -(int)Sema.getScale()));
	bool Ignored;
	ScaleFactor.convert(*OpSema, LosslessRM, &Ignored);
	Flt.multiply(ScaleFactor, LosslessRM);

	if (OpSema != &FloatSema)
	Flt.convert(FloatSema, RM, &Ignored);

	return Flt;
	}

	APFixedPoint APFixedPoint::getFromIntValue(const APSInt &Value,
	const FixedPointSemantics &DstFXSema,
	bool *Overflow) {
	FixedPointSemantics IntFXSema = FixedPointSemantics::GetIntegerSemantics(
	Value.getBitWidth(), Value.isSigned());
	return APFixedPoint(Value, IntFXSema).convert(DstFXSema, Overflow);
	}

	APFixedPoint
	APFixedPoint::getFromFloatValue(const APFloat &Value,
	const FixedPointSemantics &DstFXSema,
	bool *Overflow) {
	// For some operations, rounding mode has an effect on the result, while
	// other operations are lossless and should never result in rounding.
	// To signify which these operations are, we define two rounding modes here,
	// even though they are the same mode.
	APFloat::roundingMode RM = APFloat::rmTowardZero;
	APFloat::roundingMode LosslessRM = APFloat::rmTowardZero;

	const fltSemantics &FloatSema = Value.getSemantics();

	if (Value.isNaN()) {
	// Handle NaN immediately.
	if (Overflow)
	*Overflow = true;
	return APFixedPoint(DstFXSema);
	}

	// Make sure that we are operating in a type that works with this fixed-point
	// semantic.
	const fltSemantics *OpSema = &FloatSema;
	while (!DstFXSema.fitsInFloatSemantics(*OpSema))
	OpSema = promoteFloatSemantics(OpSema);

	APFloat Val = Value;

	bool Ignored;
	if (&FloatSema != OpSema)
	Val.convert(*OpSema, LosslessRM, &Ignored);

	// Scale up the float so that the 'fractional' part of the mantissa ends up in
	// the integer range instead. Rounding mode is irrelevant here.
	// It is fine if this overflows to infinity even for saturating types,
	// since we will use floating point comparisons to check for saturation.
	APFloat ScaleFactor(std::pow(2, DstFXSema.getScale()));
	ScaleFactor.convert(*OpSema, LosslessRM, &Ignored);
	Val.multiply(ScaleFactor, LosslessRM);

	// Convert to the integral representation of the value. This rounding mode
	// is significant.
	APSInt Res(DstFXSema.getWidth(), !DstFXSema.isSigned());
	Val.convertToInteger(Res, RM, &Ignored);

	// Round the integral value and scale back. This makes the
	// overflow calculations below work properly. If we do not round here,
	// we risk checking for overflow with a value that is outside the
	// representable range of the fixed-point semantic even though no overflow
	// would occur had we rounded first.
	ScaleFactor = APFloat(std::pow(2, -(int)DstFXSema.getScale()));
	ScaleFactor.convert(*OpSema, LosslessRM, &Ignored);
	Val.roundToIntegral(RM);
	Val.multiply(ScaleFactor, LosslessRM);

	// Check for overflow/saturation by checking if the floating point value
	// is outside the range representable by the fixed-point value.
	APFloat FloatMax = getMax(DstFXSema).convertToFloat(*OpSema);
	APFloat FloatMin = getMin(DstFXSema).convertToFloat(*OpSema);
	bool Overflowed = false;
	if (DstFXSema.isSaturated()) {
	if (Val > FloatMax)
	Res = getMax(DstFXSema).getValue();
	else if (Val < FloatMin)
	Res = getMin(DstFXSema).getValue();
	} else
	Overflowed = Val > FloatMax \|\| Val < FloatMin;

	if (Overflow)
	*Overflow = Overflowed;

	return APFixedPoint(Res, DstFXSema);
	}

	} // namespace llvm