diff options
author | Bevin Hansson <bevin.hansson@ericsson.com> | 2020-07-16 13:56:07 +0200 |
---|---|---|
committer | Bevin Hansson <bevin.hansson@ericsson.com> | 2020-08-20 10:29:45 +0200 |
commit | 1a995a0af3c4e97c1135b6c9c3a243072ee0463c (patch) | |
tree | 9d817215e1ce1080c4aaeb1705b4de0a421ca162 /llvm/lib/Support/APFixedPoint.cpp | |
parent | 1e7ec4842c1a8b0c686e5674e215012867938a8d (diff) | |
download | llvm-1a995a0af3c4e97c1135b6c9c3a243072ee0463c.zip llvm-1a995a0af3c4e97c1135b6c9c3a243072ee0463c.tar.gz llvm-1a995a0af3c4e97c1135b6c9c3a243072ee0463c.tar.bz2 |
[ADT] Move FixedPoint.h from Clang to LLVM.
This patch moves FixedPointSemantics and APFixedPoint
from Clang to LLVM ADT.
This will make it easier to use the fixed-point
classes in LLVM for constructing an IR builder for
fixed-point and for reusing the APFixedPoint class
for constant evaluation purposes.
RFC: http://lists.llvm.org/pipermail/llvm-dev/2020-August/144025.html
Reviewed By: leonardchan, rjmccall
Differential Revision: https://reviews.llvm.org/D85312
Diffstat (limited to 'llvm/lib/Support/APFixedPoint.cpp')
-rw-r--r-- | llvm/lib/Support/APFixedPoint.cpp | 428 |
1 files changed, 428 insertions, 0 deletions
diff --git a/llvm/lib/Support/APFixedPoint.cpp b/llvm/lib/Support/APFixedPoint.cpp new file mode 100644 index 0000000..ebb4342 --- /dev/null +++ b/llvm/lib/Support/APFixedPoint.cpp @@ -0,0 +1,428 @@ +//===- 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" + +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); +} + +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); +} + +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); +} + +} // namespace clang |