path: root/contrib/libs/llvm12/lib/Support/APFixedPoint.cpp

//===- 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.isNullValue()) 
      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::getAllOnesValue(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