diff options
Diffstat (limited to 'include/llvm/ADT')
25 files changed, 1313 insertions, 590 deletions
diff --git a/include/llvm/ADT/APFloat.h b/include/llvm/ADT/APFloat.h index 00304230a991a..e7e5036e69307 100644 --- a/include/llvm/ADT/APFloat.h +++ b/include/llvm/ADT/APFloat.h @@ -18,9 +18,19 @@ #define LLVM_ADT_APFLOAT_H #include "llvm/ADT/APInt.h" +#include "llvm/ADT/ArrayRef.h" #include "llvm/Support/ErrorHandling.h" #include <memory> +#define APFLOAT_DISPATCH_ON_SEMANTICS(METHOD_CALL) \ + do { \ + if (usesLayout<IEEEFloat>(getSemantics())) \ + return U.IEEE.METHOD_CALL; \ + if (usesLayout<DoubleAPFloat>(getSemantics())) \ + return U.Double.METHOD_CALL; \ + llvm_unreachable("Unexpected semantics"); \ + } while (false) + namespace llvm { struct fltSemantics; @@ -42,7 +52,7 @@ enum lostFraction { // Example of truncated bits: lfMoreThanHalf // 1xxxxx x's not all zero }; -/// \brief A self-contained host- and target-independent arbitrary-precision +/// A self-contained host- and target-independent arbitrary-precision /// floating-point software implementation. /// /// APFloat uses bignum integer arithmetic as provided by static functions in @@ -130,22 +140,25 @@ enum lostFraction { // Example of truncated bits: // implementation classes. This struct should not define any non-static data // members. struct APFloatBase { + // TODO remove this and use APInt typedef directly. + typedef APInt::WordType integerPart; + /// A signed type to represent a floating point numbers unbiased exponent. typedef signed short ExponentType; /// \name Floating Point Semantics. /// @{ - static const fltSemantics &IEEEhalf(); - static const fltSemantics &IEEEsingle(); - static const fltSemantics &IEEEdouble(); - static const fltSemantics &IEEEquad(); - static const fltSemantics &PPCDoubleDouble(); - static const fltSemantics &x87DoubleExtended(); + static const fltSemantics &IEEEhalf() LLVM_READNONE; + static const fltSemantics &IEEEsingle() LLVM_READNONE; + static const fltSemantics &IEEEdouble() LLVM_READNONE; + static const fltSemantics &IEEEquad() LLVM_READNONE; + static const fltSemantics &PPCDoubleDouble() LLVM_READNONE; + static const fltSemantics &x87DoubleExtended() LLVM_READNONE; /// A Pseudo fltsemantic used to construct APFloats that cannot conflict with /// anything real. - static const fltSemantics &Bogus(); + static const fltSemantics &Bogus() LLVM_READNONE; /// @} @@ -191,7 +204,7 @@ struct APFloatBase { uninitialized }; - /// \brief Enumeration of \c ilogb error results. + /// Enumeration of \c ilogb error results. enum IlogbErrorKinds { IEK_Zero = INT_MIN + 1, IEK_NaN = INT_MIN, @@ -227,7 +240,7 @@ public: /// @} - /// \brief Returns whether this instance allocated memory. + /// Returns whether this instance allocated memory. bool needsCleanup() const { return partCount() > 1; } /// \name Convenience "constructors" @@ -235,10 +248,6 @@ public: /// @} - /// Used to insert APFloat objects, or objects that contain APFloat objects, - /// into FoldingSets. - void Profile(FoldingSetNodeID &NID) const; - /// \name Arithmetic /// @{ @@ -255,53 +264,12 @@ public: /// IEEE-754R 5.3.1: nextUp/nextDown. opStatus next(bool nextDown); - /// \brief Operator+ overload which provides the default - /// \c nmNearestTiesToEven rounding mode and *no* error checking. - IEEEFloat operator+(const IEEEFloat &RHS) const { - IEEEFloat Result = *this; - Result.add(RHS, rmNearestTiesToEven); - return Result; - } - - /// \brief Operator- overload which provides the default - /// \c nmNearestTiesToEven rounding mode and *no* error checking. - IEEEFloat operator-(const IEEEFloat &RHS) const { - IEEEFloat Result = *this; - Result.subtract(RHS, rmNearestTiesToEven); - return Result; - } - - /// \brief Operator* overload which provides the default - /// \c nmNearestTiesToEven rounding mode and *no* error checking. - IEEEFloat operator*(const IEEEFloat &RHS) const { - IEEEFloat Result = *this; - Result.multiply(RHS, rmNearestTiesToEven); - return Result; - } - - /// \brief Operator/ overload which provides the default - /// \c nmNearestTiesToEven rounding mode and *no* error checking. - IEEEFloat operator/(const IEEEFloat &RHS) const { - IEEEFloat Result = *this; - Result.divide(RHS, rmNearestTiesToEven); - return Result; - } - /// @} /// \name Sign operations. /// @{ void changeSign(); - void clearSign(); - void copySign(const IEEEFloat &); - - /// \brief A static helper to produce a copy of an APFloat value with its sign - /// copied from some other APFloat. - static IEEEFloat copySign(IEEEFloat Value, const IEEEFloat &Sign) { - Value.copySign(Sign); - return Value; - } /// @} @@ -309,9 +277,8 @@ public: /// @{ opStatus convert(const fltSemantics &, roundingMode, bool *); - opStatus convertToInteger(integerPart *, unsigned int, bool, roundingMode, - bool *) const; - opStatus convertToInteger(APSInt &, roundingMode, bool *) const; + opStatus convertToInteger(MutableArrayRef<integerPart>, unsigned int, bool, + roundingMode, bool *) const; opStatus convertFromAPInt(const APInt &, bool, roundingMode); opStatus convertFromSignExtendedInteger(const integerPart *, unsigned int, bool, roundingMode); @@ -398,7 +365,7 @@ public: /// Returns true if and only if the number has the largest possible finite /// magnitude in the current semantics. bool isLargest() const; - + /// Returns true if and only if the number is an exact integer. bool isInteger() const; @@ -407,7 +374,7 @@ public: IEEEFloat &operator=(const IEEEFloat &); IEEEFloat &operator=(IEEEFloat &&); - /// \brief Overload to compute a hash code for an APFloat value. + /// Overload to compute a hash code for an APFloat value. /// /// Note that the use of hash codes for floating point values is in general /// frought with peril. Equality is hard to define for these values. For @@ -443,9 +410,9 @@ public: /// If this value has an exact multiplicative inverse, store it in inv and /// return true. - bool getExactInverse(IEEEFloat *inv) const; + bool getExactInverse(APFloat *inv) const; - /// \brief Returns the exponent of the internal representation of the APFloat. + /// Returns the exponent of the internal representation of the APFloat. /// /// Because the radix of APFloat is 2, this is equivalent to floor(log2(x)). /// For special APFloat values, this returns special error codes: @@ -456,7 +423,7 @@ public: /// friend int ilogb(const IEEEFloat &Arg); - /// \brief Returns: X * 2^Exp for integral exponents. + /// Returns: X * 2^Exp for integral exponents. friend IEEEFloat scalbn(IEEEFloat X, int Exp, roundingMode); friend IEEEFloat frexp(const IEEEFloat &X, int &Exp, roundingMode); @@ -532,8 +499,9 @@ private: opStatus addOrSubtract(const IEEEFloat &, roundingMode, bool subtract); opStatus handleOverflow(roundingMode); bool roundAwayFromZero(roundingMode, lostFraction, unsigned int) const; - opStatus convertToSignExtendedInteger(integerPart *, unsigned int, bool, - roundingMode, bool *) const; + opStatus convertToSignExtendedInteger(MutableArrayRef<integerPart>, + unsigned int, bool, roundingMode, + bool *) const; opStatus convertFromUnsignedParts(const integerPart *, unsigned int, roundingMode); opStatus convertFromHexadecimalString(StringRef, roundingMode); @@ -636,6 +604,13 @@ public: opStatus add(const DoubleAPFloat &RHS, roundingMode RM); opStatus subtract(const DoubleAPFloat &RHS, roundingMode RM); + opStatus multiply(const DoubleAPFloat &RHS, roundingMode RM); + opStatus divide(const DoubleAPFloat &RHS, roundingMode RM); + opStatus remainder(const DoubleAPFloat &RHS); + opStatus mod(const DoubleAPFloat &RHS); + opStatus fusedMultiplyAdd(const DoubleAPFloat &Multiplicand, + const DoubleAPFloat &Addend, roundingMode RM); + opStatus roundToIntegral(roundingMode RM); void changeSign(); cmpResult compareAbsoluteValue(const DoubleAPFloat &RHS) const; @@ -643,9 +618,49 @@ public: bool isNegative() const; void makeInf(bool Neg); + void makeZero(bool Neg); + void makeLargest(bool Neg); + void makeSmallest(bool Neg); + void makeSmallestNormalized(bool Neg); void makeNaN(bool SNaN, bool Neg, const APInt *fill); + + cmpResult compare(const DoubleAPFloat &RHS) const; + bool bitwiseIsEqual(const DoubleAPFloat &RHS) const; + APInt bitcastToAPInt() const; + opStatus convertFromString(StringRef, roundingMode); + opStatus next(bool nextDown); + + opStatus convertToInteger(MutableArrayRef<integerPart> Input, + unsigned int Width, bool IsSigned, roundingMode RM, + bool *IsExact) const; + opStatus convertFromAPInt(const APInt &Input, bool IsSigned, roundingMode RM); + opStatus convertFromSignExtendedInteger(const integerPart *Input, + unsigned int InputSize, bool IsSigned, + roundingMode RM); + opStatus convertFromZeroExtendedInteger(const integerPart *Input, + unsigned int InputSize, bool IsSigned, + roundingMode RM); + unsigned int convertToHexString(char *DST, unsigned int HexDigits, + bool UpperCase, roundingMode RM) const; + + bool isDenormal() const; + bool isSmallest() const; + bool isLargest() const; + bool isInteger() const; + + void toString(SmallVectorImpl<char> &Str, unsigned FormatPrecision, + unsigned FormatMaxPadding) const; + + bool getExactInverse(APFloat *inv) const; + + friend int ilogb(const DoubleAPFloat &Arg); + friend DoubleAPFloat scalbn(DoubleAPFloat X, int Exp, roundingMode); + friend DoubleAPFloat frexp(const DoubleAPFloat &X, int &Exp, roundingMode); + friend hash_code hash_value(const DoubleAPFloat &Arg); }; +hash_code hash_value(const DoubleAPFloat &Arg); + } // End detail namespace // This is a interface class that is currently forwarding functionalities from @@ -770,26 +785,24 @@ class APFloat : public APFloatBase { llvm_unreachable("Unexpected semantics"); } - void makeZero(bool Neg) { getIEEE().makeZero(Neg); } + void makeZero(bool Neg) { APFLOAT_DISPATCH_ON_SEMANTICS(makeZero(Neg)); } - void makeInf(bool Neg) { - if (usesLayout<IEEEFloat>(*U.semantics)) - return U.IEEE.makeInf(Neg); - if (usesLayout<DoubleAPFloat>(*U.semantics)) - return U.Double.makeInf(Neg); - llvm_unreachable("Unexpected semantics"); - } + void makeInf(bool Neg) { APFLOAT_DISPATCH_ON_SEMANTICS(makeInf(Neg)); } void makeNaN(bool SNaN, bool Neg, const APInt *fill) { - getIEEE().makeNaN(SNaN, Neg, fill); + APFLOAT_DISPATCH_ON_SEMANTICS(makeNaN(SNaN, Neg, fill)); } - void makeLargest(bool Neg) { getIEEE().makeLargest(Neg); } + void makeLargest(bool Neg) { + APFLOAT_DISPATCH_ON_SEMANTICS(makeLargest(Neg)); + } - void makeSmallest(bool Neg) { getIEEE().makeSmallest(Neg); } + void makeSmallest(bool Neg) { + APFLOAT_DISPATCH_ON_SEMANTICS(makeSmallest(Neg)); + } void makeSmallestNormalized(bool Neg) { - getIEEE().makeSmallestNormalized(Neg); + APFLOAT_DISPATCH_ON_SEMANTICS(makeSmallestNormalized(Neg)); } // FIXME: This is due to clang 3.3 (or older version) always checks for the @@ -804,7 +817,8 @@ class APFloat : public APFloatBase { : U(std::move(F), S) {} cmpResult compareAbsoluteValue(const APFloat &RHS) const { - assert(&getSemantics() == &RHS.getSemantics()); + assert(&getSemantics() == &RHS.getSemantics() && + "Should only compare APFloats with the same semantics"); if (usesLayout<IEEEFloat>(getSemantics())) return U.IEEE.compareAbsoluteValue(RHS.U.IEEE); if (usesLayout<DoubleAPFloat>(getSemantics())) @@ -827,13 +841,7 @@ public: ~APFloat() = default; - bool needsCleanup() const { - if (usesLayout<IEEEFloat>(getSemantics())) - return U.IEEE.needsCleanup(); - if (usesLayout<DoubleAPFloat>(getSemantics())) - return U.Double.needsCleanup(); - llvm_unreachable("Unexpected semantics"); - } + bool needsCleanup() const { APFLOAT_DISPATCH_ON_SEMANTICS(needsCleanup()); } /// Factory for Positive and Negative Zero. /// @@ -920,9 +928,13 @@ public: /// \param isIEEE - If 128 bit number, select between PPC and IEEE static APFloat getAllOnesValue(unsigned BitWidth, bool isIEEE = false); - void Profile(FoldingSetNodeID &NID) const { getIEEE().Profile(NID); } + /// Used to insert APFloat objects, or objects that contain APFloat objects, + /// into FoldingSets. + void Profile(FoldingSetNodeID &NID) const; opStatus add(const APFloat &RHS, roundingMode RM) { + assert(&getSemantics() == &RHS.getSemantics() && + "Should only call on two APFloats with the same semantics"); if (usesLayout<IEEEFloat>(getSemantics())) return U.IEEE.add(RHS.U.IEEE, RM); if (usesLayout<DoubleAPFloat>(getSemantics())) @@ -930,6 +942,8 @@ public: llvm_unreachable("Unexpected semantics"); } opStatus subtract(const APFloat &RHS, roundingMode RM) { + assert(&getSemantics() == &RHS.getSemantics() && + "Should only call on two APFloats with the same semantics"); if (usesLayout<IEEEFloat>(getSemantics())) return U.IEEE.subtract(RHS.U.IEEE, RM); if (usesLayout<DoubleAPFloat>(getSemantics())) @@ -937,95 +951,172 @@ public: llvm_unreachable("Unexpected semantics"); } opStatus multiply(const APFloat &RHS, roundingMode RM) { - return getIEEE().multiply(RHS.getIEEE(), RM); + assert(&getSemantics() == &RHS.getSemantics() && + "Should only call on two APFloats with the same semantics"); + if (usesLayout<IEEEFloat>(getSemantics())) + return U.IEEE.multiply(RHS.U.IEEE, RM); + if (usesLayout<DoubleAPFloat>(getSemantics())) + return U.Double.multiply(RHS.U.Double, RM); + llvm_unreachable("Unexpected semantics"); } opStatus divide(const APFloat &RHS, roundingMode RM) { - return getIEEE().divide(RHS.getIEEE(), RM); + assert(&getSemantics() == &RHS.getSemantics() && + "Should only call on two APFloats with the same semantics"); + if (usesLayout<IEEEFloat>(getSemantics())) + return U.IEEE.divide(RHS.U.IEEE, RM); + if (usesLayout<DoubleAPFloat>(getSemantics())) + return U.Double.divide(RHS.U.Double, RM); + llvm_unreachable("Unexpected semantics"); } opStatus remainder(const APFloat &RHS) { - return getIEEE().remainder(RHS.getIEEE()); + assert(&getSemantics() == &RHS.getSemantics() && + "Should only call on two APFloats with the same semantics"); + if (usesLayout<IEEEFloat>(getSemantics())) + return U.IEEE.remainder(RHS.U.IEEE); + if (usesLayout<DoubleAPFloat>(getSemantics())) + return U.Double.remainder(RHS.U.Double); + llvm_unreachable("Unexpected semantics"); + } + opStatus mod(const APFloat &RHS) { + assert(&getSemantics() == &RHS.getSemantics() && + "Should only call on two APFloats with the same semantics"); + if (usesLayout<IEEEFloat>(getSemantics())) + return U.IEEE.mod(RHS.U.IEEE); + if (usesLayout<DoubleAPFloat>(getSemantics())) + return U.Double.mod(RHS.U.Double); + llvm_unreachable("Unexpected semantics"); } - opStatus mod(const APFloat &RHS) { return getIEEE().mod(RHS.getIEEE()); } opStatus fusedMultiplyAdd(const APFloat &Multiplicand, const APFloat &Addend, roundingMode RM) { - return getIEEE().fusedMultiplyAdd(Multiplicand.getIEEE(), Addend.getIEEE(), - RM); + assert(&getSemantics() == &Multiplicand.getSemantics() && + "Should only call on APFloats with the same semantics"); + assert(&getSemantics() == &Addend.getSemantics() && + "Should only call on APFloats with the same semantics"); + if (usesLayout<IEEEFloat>(getSemantics())) + return U.IEEE.fusedMultiplyAdd(Multiplicand.U.IEEE, Addend.U.IEEE, RM); + if (usesLayout<DoubleAPFloat>(getSemantics())) + return U.Double.fusedMultiplyAdd(Multiplicand.U.Double, Addend.U.Double, + RM); + llvm_unreachable("Unexpected semantics"); } opStatus roundToIntegral(roundingMode RM) { - return getIEEE().roundToIntegral(RM); + APFLOAT_DISPATCH_ON_SEMANTICS(roundToIntegral(RM)); + } + + // TODO: bool parameters are not readable and a source of bugs. + // Do something. + opStatus next(bool nextDown) { + APFLOAT_DISPATCH_ON_SEMANTICS(next(nextDown)); } - opStatus next(bool nextDown) { return getIEEE().next(nextDown); } + /// Add two APFloats, rounding ties to the nearest even. + /// No error checking. APFloat operator+(const APFloat &RHS) const { - return APFloat(getIEEE() + RHS.getIEEE(), getSemantics()); + APFloat Result(*this); + (void)Result.add(RHS, rmNearestTiesToEven); + return Result; } + /// Subtract two APFloats, rounding ties to the nearest even. + /// No error checking. APFloat operator-(const APFloat &RHS) const { - return APFloat(getIEEE() - RHS.getIEEE(), getSemantics()); + APFloat Result(*this); + (void)Result.subtract(RHS, rmNearestTiesToEven); + return Result; } + /// Multiply two APFloats, rounding ties to the nearest even. + /// No error checking. APFloat operator*(const APFloat &RHS) const { - return APFloat(getIEEE() * RHS.getIEEE(), getSemantics()); + APFloat Result(*this); + (void)Result.multiply(RHS, rmNearestTiesToEven); + return Result; } + /// Divide the first APFloat by the second, rounding ties to the nearest even. + /// No error checking. APFloat operator/(const APFloat &RHS) const { - return APFloat(getIEEE() / RHS.getIEEE(), getSemantics()); + APFloat Result(*this); + (void)Result.divide(RHS, rmNearestTiesToEven); + return Result; } - void changeSign() { getIEEE().changeSign(); } - void clearSign() { getIEEE().clearSign(); } - void copySign(const APFloat &RHS) { getIEEE().copySign(RHS.getIEEE()); } + void changeSign() { APFLOAT_DISPATCH_ON_SEMANTICS(changeSign()); } + void clearSign() { + if (isNegative()) + changeSign(); + } + void copySign(const APFloat &RHS) { + if (isNegative() != RHS.isNegative()) + changeSign(); + } + /// A static helper to produce a copy of an APFloat value with its sign + /// copied from some other APFloat. static APFloat copySign(APFloat Value, const APFloat &Sign) { - return APFloat(IEEEFloat::copySign(Value.getIEEE(), Sign.getIEEE()), - Value.getSemantics()); + Value.copySign(Sign); + return Value; } opStatus convert(const fltSemantics &ToSemantics, roundingMode RM, bool *losesInfo); - opStatus convertToInteger(integerPart *Input, unsigned int Width, - bool IsSigned, roundingMode RM, + opStatus convertToInteger(MutableArrayRef<integerPart> Input, + unsigned int Width, bool IsSigned, roundingMode RM, bool *IsExact) const { - return getIEEE().convertToInteger(Input, Width, IsSigned, RM, IsExact); + APFLOAT_DISPATCH_ON_SEMANTICS( + convertToInteger(Input, Width, IsSigned, RM, IsExact)); } opStatus convertToInteger(APSInt &Result, roundingMode RM, - bool *IsExact) const { - return getIEEE().convertToInteger(Result, RM, IsExact); - } + bool *IsExact) const; opStatus convertFromAPInt(const APInt &Input, bool IsSigned, roundingMode RM) { - return getIEEE().convertFromAPInt(Input, IsSigned, RM); + APFLOAT_DISPATCH_ON_SEMANTICS(convertFromAPInt(Input, IsSigned, RM)); } opStatus convertFromSignExtendedInteger(const integerPart *Input, unsigned int InputSize, bool IsSigned, roundingMode RM) { - return getIEEE().convertFromSignExtendedInteger(Input, InputSize, IsSigned, - RM); + APFLOAT_DISPATCH_ON_SEMANTICS( + convertFromSignExtendedInteger(Input, InputSize, IsSigned, RM)); } opStatus convertFromZeroExtendedInteger(const integerPart *Input, unsigned int InputSize, bool IsSigned, roundingMode RM) { - return getIEEE().convertFromZeroExtendedInteger(Input, InputSize, IsSigned, - RM); + APFLOAT_DISPATCH_ON_SEMANTICS( + convertFromZeroExtendedInteger(Input, InputSize, IsSigned, RM)); } opStatus convertFromString(StringRef, roundingMode); - APInt bitcastToAPInt() const { return getIEEE().bitcastToAPInt(); } + APInt bitcastToAPInt() const { + APFLOAT_DISPATCH_ON_SEMANTICS(bitcastToAPInt()); + } double convertToDouble() const { return getIEEE().convertToDouble(); } float convertToFloat() const { return getIEEE().convertToFloat(); } bool operator==(const APFloat &) const = delete; cmpResult compare(const APFloat &RHS) const { - return getIEEE().compare(RHS.getIEEE()); + assert(&getSemantics() == &RHS.getSemantics() && + "Should only compare APFloats with the same semantics"); + if (usesLayout<IEEEFloat>(getSemantics())) + return U.IEEE.compare(RHS.U.IEEE); + if (usesLayout<DoubleAPFloat>(getSemantics())) + return U.Double.compare(RHS.U.Double); + llvm_unreachable("Unexpected semantics"); } bool bitwiseIsEqual(const APFloat &RHS) const { - return getIEEE().bitwiseIsEqual(RHS.getIEEE()); + if (&getSemantics() != &RHS.getSemantics()) + return false; + if (usesLayout<IEEEFloat>(getSemantics())) + return U.IEEE.bitwiseIsEqual(RHS.U.IEEE); + if (usesLayout<DoubleAPFloat>(getSemantics())) + return U.Double.bitwiseIsEqual(RHS.U.Double); + llvm_unreachable("Unexpected semantics"); } unsigned int convertToHexString(char *DST, unsigned int HexDigits, bool UpperCase, roundingMode RM) const { - return getIEEE().convertToHexString(DST, HexDigits, UpperCase, RM); + APFLOAT_DISPATCH_ON_SEMANTICS( + convertToHexString(DST, HexDigits, UpperCase, RM)); } bool isZero() const { return getCategory() == fcZero; } @@ -1033,7 +1124,7 @@ public: bool isNaN() const { return getCategory() == fcNaN; } bool isNegative() const { return getIEEE().isNegative(); } - bool isDenormal() const { return getIEEE().isDenormal(); } + bool isDenormal() const { APFLOAT_DISPATCH_ON_SEMANTICS(isDenormal()); } bool isSignaling() const { return getIEEE().isSignaling(); } bool isNormal() const { return !isDenormal() && isFiniteNonZero(); } @@ -1045,30 +1136,24 @@ public: bool isFiniteNonZero() const { return isFinite() && !isZero(); } bool isPosZero() const { return isZero() && !isNegative(); } bool isNegZero() const { return isZero() && isNegative(); } - bool isSmallest() const { return getIEEE().isSmallest(); } - bool isLargest() const { return getIEEE().isLargest(); } - bool isInteger() const { return getIEEE().isInteger(); } + bool isSmallest() const { APFLOAT_DISPATCH_ON_SEMANTICS(isSmallest()); } + bool isLargest() const { APFLOAT_DISPATCH_ON_SEMANTICS(isLargest()); } + bool isInteger() const { APFLOAT_DISPATCH_ON_SEMANTICS(isInteger()); } APFloat &operator=(const APFloat &RHS) = default; APFloat &operator=(APFloat &&RHS) = default; void toString(SmallVectorImpl<char> &Str, unsigned FormatPrecision = 0, unsigned FormatMaxPadding = 3) const { - return getIEEE().toString(Str, FormatPrecision, FormatMaxPadding); + APFLOAT_DISPATCH_ON_SEMANTICS( + toString(Str, FormatPrecision, FormatMaxPadding)); } void print(raw_ostream &) const; void dump() const; bool getExactInverse(APFloat *inv) const { - return getIEEE().getExactInverse(inv ? &inv->getIEEE() : nullptr); - } - - // This is for internal test only. - // TODO: Remove it after the PPCDoubleDouble transition. - const APFloat &getSecondFloat() const { - assert(&getSemantics() == &PPCDoubleDouble()); - return U.Double.getSecond(); + APFLOAT_DISPATCH_ON_SEMANTICS(getExactInverse(inv)); } friend hash_code hash_value(const APFloat &Arg); @@ -1085,22 +1170,36 @@ public: /// xlC compiler. hash_code hash_value(const APFloat &Arg); inline APFloat scalbn(APFloat X, int Exp, APFloat::roundingMode RM) { - return APFloat(scalbn(X.getIEEE(), Exp, RM), X.getSemantics()); + if (APFloat::usesLayout<detail::IEEEFloat>(X.getSemantics())) + return APFloat(scalbn(X.U.IEEE, Exp, RM), X.getSemantics()); + if (APFloat::usesLayout<detail::DoubleAPFloat>(X.getSemantics())) + return APFloat(scalbn(X.U.Double, Exp, RM), X.getSemantics()); + llvm_unreachable("Unexpected semantics"); } -/// \brief Equivalent of C standard library function. +/// Equivalent of C standard library function. /// /// While the C standard says Exp is an unspecified value for infinity and nan, /// this returns INT_MAX for infinities, and INT_MIN for NaNs. inline APFloat frexp(const APFloat &X, int &Exp, APFloat::roundingMode RM) { - return APFloat(frexp(X.getIEEE(), Exp, RM), X.getSemantics()); + if (APFloat::usesLayout<detail::IEEEFloat>(X.getSemantics())) + return APFloat(frexp(X.U.IEEE, Exp, RM), X.getSemantics()); + if (APFloat::usesLayout<detail::DoubleAPFloat>(X.getSemantics())) + return APFloat(frexp(X.U.Double, Exp, RM), X.getSemantics()); + llvm_unreachable("Unexpected semantics"); } -/// \brief Returns the absolute value of the argument. +/// Returns the absolute value of the argument. inline APFloat abs(APFloat X) { X.clearSign(); return X; } +/// \brief Returns the negated value of the argument. +inline APFloat neg(APFloat X) { + X.changeSign(); + return X; +} + /// Implements IEEE minNum semantics. Returns the smaller of the 2 arguments if /// both are not NaN. If either argument is a NaN, returns the other argument. LLVM_READONLY @@ -1125,4 +1224,5 @@ inline APFloat maxnum(const APFloat &A, const APFloat &B) { } // namespace llvm +#undef APFLOAT_DISPATCH_ON_SEMANTICS #endif // LLVM_ADT_APFLOAT_H diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h index 2c0713da256cd..ab23130b137d8 100644 --- a/include/llvm/ADT/APInt.h +++ b/include/llvm/ADT/APInt.h @@ -32,14 +32,6 @@ class raw_ostream; template <typename T> class SmallVectorImpl; template <typename T> class ArrayRef; -// An unsigned host type used as a single part of a multi-part -// bignum. -typedef uint64_t integerPart; - -const unsigned int host_char_bit = 8; -const unsigned int integerPartWidth = - host_char_bit * static_cast<unsigned int>(sizeof(integerPart)); - class APInt; inline APInt operator-(APInt); @@ -75,8 +67,18 @@ inline APInt operator-(APInt); /// uses in its IR. This simplifies its use for LLVM. /// class LLVM_NODISCARD APInt { - unsigned BitWidth; ///< The number of bits in this APInt. +public: + typedef uint64_t WordType; + /// This enum is used to hold the constants we needed for APInt. + enum : unsigned { + /// Byte size of a word. + APINT_WORD_SIZE = sizeof(WordType), + /// Bits in a word. + APINT_BITS_PER_WORD = APINT_WORD_SIZE * CHAR_BIT + }; + +private: /// This union is used to store the integer value. When the /// integer bit-width <= 64, it uses VAL, otherwise it uses pVal. union { @@ -84,14 +86,7 @@ class LLVM_NODISCARD APInt { uint64_t *pVal; ///< Used to store the >64 bits integer value. }; - /// This enum is used to hold the constants we needed for APInt. - enum { - /// Bits in a word - APINT_BITS_PER_WORD = - static_cast<unsigned int>(sizeof(uint64_t)) * CHAR_BIT, - /// Byte size of a word - APINT_WORD_SIZE = static_cast<unsigned int>(sizeof(uint64_t)) - }; + unsigned BitWidth; ///< The number of bits in this APInt. friend struct DenseMapAPIntKeyInfo; @@ -99,7 +94,7 @@ class LLVM_NODISCARD APInt { /// /// This constructor is used only internally for speed of construction of /// temporaries. It is unsafe for general use so it is not public. - APInt(uint64_t *val, unsigned bits) : BitWidth(bits), pVal(val) {} + APInt(uint64_t *val, unsigned bits) : pVal(val), BitWidth(bits) {} /// \brief Determine if this APInt just has one word to store value. /// @@ -147,7 +142,7 @@ class LLVM_NODISCARD APInt { return *this; // Mask out the high bits. - uint64_t mask = ~uint64_t(0ULL) >> (APINT_BITS_PER_WORD - wordBits); + uint64_t mask = UINT64_MAX >> (APINT_BITS_PER_WORD - wordBits); if (isSingleWord()) VAL &= mask; else @@ -196,32 +191,38 @@ class LLVM_NODISCARD APInt { /// out-of-line slow case for shl APInt shlSlowCase(unsigned shiftAmt) const; - /// out-of-line slow case for operator& - APInt AndSlowCase(const APInt &RHS) const; - - /// out-of-line slow case for operator| - APInt OrSlowCase(const APInt &RHS) const; - - /// out-of-line slow case for operator^ - APInt XorSlowCase(const APInt &RHS) const; - /// out-of-line slow case for operator= APInt &AssignSlowCase(const APInt &RHS); /// out-of-line slow case for operator== - bool EqualSlowCase(const APInt &RHS) const; + bool EqualSlowCase(const APInt &RHS) const LLVM_READONLY; /// out-of-line slow case for operator== - bool EqualSlowCase(uint64_t Val) const; + bool EqualSlowCase(uint64_t Val) const LLVM_READONLY; /// out-of-line slow case for countLeadingZeros - unsigned countLeadingZerosSlowCase() const; + unsigned countLeadingZerosSlowCase() const LLVM_READONLY; /// out-of-line slow case for countTrailingOnes - unsigned countTrailingOnesSlowCase() const; + unsigned countTrailingOnesSlowCase() const LLVM_READONLY; /// out-of-line slow case for countPopulation - unsigned countPopulationSlowCase() const; + unsigned countPopulationSlowCase() const LLVM_READONLY; + + /// out-of-line slow case for setBits. + void setBitsSlowCase(unsigned loBit, unsigned hiBit); + + /// out-of-line slow case for flipAllBits. + void flipAllBitsSlowCase(); + + /// out-of-line slow case for operator&=. + APInt& AndAssignSlowCase(const APInt& RHS); + + /// out-of-line slow case for operator|=. + APInt& OrAssignSlowCase(const APInt& RHS); + + /// out-of-line slow case for operator^=. + APInt& XorAssignSlowCase(const APInt& RHS); public: /// \name Constructors @@ -238,13 +239,14 @@ public: /// \param val the initial value of the APInt /// \param isSigned how to treat signedness of val APInt(unsigned numBits, uint64_t val, bool isSigned = false) - : BitWidth(numBits), VAL(0) { + : BitWidth(numBits) { assert(BitWidth && "bitwidth too small"); - if (isSingleWord()) + if (isSingleWord()) { VAL = val; - else + clearUnusedBits(); + } else { initSlowCase(val, isSigned); - clearUnusedBits(); + } } /// \brief Construct an APInt of numBits width, initialized as bigVal[]. @@ -280,7 +282,7 @@ public: /// Simply makes *this a copy of that. /// @brief Copy Constructor. - APInt(const APInt &that) : BitWidth(that.BitWidth), VAL(0) { + APInt(const APInt &that) : BitWidth(that.BitWidth) { if (isSingleWord()) VAL = that.VAL; else @@ -288,7 +290,7 @@ public: } /// \brief Move Constructor. - APInt(APInt &&that) : BitWidth(that.BitWidth), VAL(that.VAL) { + APInt(APInt &&that) : VAL(that.VAL), BitWidth(that.BitWidth) { that.BitWidth = 0; } @@ -303,7 +305,7 @@ public: /// /// This is useful for object deserialization (pair this with the static /// method Read). - explicit APInt() : BitWidth(1), VAL(0) {} + explicit APInt() : VAL(0), BitWidth(1) {} /// \brief Returns whether this instance allocated memory. bool needsCleanup() const { return !isSingleWord(); } @@ -341,7 +343,7 @@ public: /// This checks to see if the value has all bits of the APInt are set or not. bool isAllOnesValue() const { if (isSingleWord()) - return VAL == ~integerPart(0) >> (APINT_BITS_PER_WORD - BitWidth); + return VAL == UINT64_MAX >> (APINT_BITS_PER_WORD - BitWidth); return countPopulationSlowCase() == BitWidth; } @@ -406,7 +408,7 @@ public: /// If this value is smaller than the specified limit, return it, otherwise /// return the limit value. This causes the value to saturate to the limit. - uint64_t getLimitedValue(uint64_t Limit = ~0ULL) const { + uint64_t getLimitedValue(uint64_t Limit = UINT64_MAX) const { return (getActiveBits() > 64 || getZExtValue() > Limit) ? Limit : getZExtValue(); } @@ -418,6 +420,36 @@ public: /// width without remainder. bool isSplat(unsigned SplatSizeInBits) const; + /// \returns true if this APInt value is a sequence of \param numBits ones + /// starting at the least significant bit with the remainder zero. + bool isMask(unsigned numBits) const { + assert(numBits != 0 && "numBits must be non-zero"); + assert(numBits <= BitWidth && "numBits out of range"); + if (isSingleWord()) + return VAL == (UINT64_MAX >> (APINT_BITS_PER_WORD - numBits)); + unsigned Ones = countTrailingOnes(); + return (numBits == Ones) && ((Ones + countLeadingZeros()) == BitWidth); + } + + /// \returns true if this APInt is a non-empty sequence of ones starting at + /// the least significant bit with the remainder zero. + /// Ex. isMask(0x0000FFFFU) == true. + bool isMask() const { + if (isSingleWord()) + return isMask_64(VAL); + unsigned Ones = countTrailingOnes(); + return (Ones > 0) && ((Ones + countLeadingZeros()) == BitWidth); + } + + /// \brief Return true if this APInt value contains a sequence of ones with + /// the remainder zero. + bool isShiftedMask() const { + if (isSingleWord()) + return isShiftedMask_64(VAL); + unsigned Ones = countPopulation(); + return (Ones + countTrailingZeros() + countLeadingZeros()) == BitWidth; + } + /// @} /// \name Value Generators /// @{ @@ -501,12 +533,26 @@ public: /// /// \returns An APInt value with the requested bits set. static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit) { - assert(hiBit <= numBits && "hiBit out of range"); - assert(loBit < numBits && "loBit out of range"); - if (hiBit < loBit) - return getLowBitsSet(numBits, hiBit) | - getHighBitsSet(numBits, numBits - loBit); - return getLowBitsSet(numBits, hiBit - loBit).shl(loBit); + APInt Res(numBits, 0); + Res.setBits(loBit, hiBit); + return Res; + } + + /// \brief Get a value with upper bits starting at loBit set. + /// + /// Constructs an APInt value that has a contiguous range of bits set. The + /// bits from loBit (inclusive) to numBits (exclusive) will be set. All other + /// bits will be zero. For example, with parameters(32, 12) you would get + /// 0xFFFFF000. + /// + /// \param numBits the intended bit width of the result + /// \param loBit the index of the lowest bit to set. + /// + /// \returns An APInt value with the requested bits set. + static APInt getBitsSetFrom(unsigned numBits, unsigned loBit) { + APInt Res(numBits, 0); + Res.setBitsFrom(loBit); + return Res; } /// \brief Get a value with high bits set @@ -516,15 +562,9 @@ public: /// \param numBits the bitwidth of the result /// \param hiBitsSet the number of high-order bits set in the result. static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet) { - assert(hiBitsSet <= numBits && "Too many bits to set!"); - // Handle a degenerate case, to avoid shifting by word size - if (hiBitsSet == 0) - return APInt(numBits, 0); - unsigned shiftAmt = numBits - hiBitsSet; - // For small values, return quickly - if (numBits <= APINT_BITS_PER_WORD) - return APInt(numBits, ~0ULL << shiftAmt); - return getAllOnesValue(numBits).shl(shiftAmt); + APInt Res(numBits, 0); + Res.setHighBits(hiBitsSet); + return Res; } /// \brief Get a value with low bits set @@ -534,16 +574,9 @@ public: /// \param numBits the bitwidth of the result /// \param loBitsSet the number of low-order bits set in the result. static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet) { - assert(loBitsSet <= numBits && "Too many bits to set!"); - // Handle a degenerate case, to avoid shifting by word size - if (loBitsSet == 0) - return APInt(numBits, 0); - if (loBitsSet == APINT_BITS_PER_WORD) - return APInt(numBits, UINT64_MAX); - // For small values, return quickly. - if (loBitsSet <= APINT_BITS_PER_WORD) - return APInt(numBits, UINT64_MAX >> (APINT_BITS_PER_WORD - loBitsSet)); - return getAllOnesValue(numBits).lshr(numBits - loBitsSet); + APInt Res(numBits, 0); + Res.setLowBits(loBitsSet); + return Res; } /// \brief Return a value containing V broadcasted over NewLen bits. @@ -587,7 +620,9 @@ public: /// \brief Postfix increment operator. /// - /// \returns a new APInt value representing *this incremented by one + /// Increments *this by 1. + /// + /// \returns a new APInt value representing the original value of *this. const APInt operator++(int) { APInt API(*this); ++(*this); @@ -601,7 +636,9 @@ public: /// \brief Postfix decrement operator. /// - /// \returns a new APInt representing *this decremented by one. + /// Decrements *this by 1. + /// + /// \returns a new APInt value representing the original value of *this. const APInt operator--(int) { APInt API(*this); --(*this); @@ -613,30 +650,13 @@ public: /// \returns *this decremented by one. APInt &operator--(); - /// \brief Unary bitwise complement operator. - /// - /// Performs a bitwise complement operation on this APInt. - /// - /// \returns an APInt that is the bitwise complement of *this - APInt operator~() const { - APInt Result(*this); - Result.flipAllBits(); - return Result; - } - /// \brief Logical negation operator. /// /// Performs logical negation operation on this APInt. /// /// \returns true if *this is zero, false otherwise. bool operator!() const { - if (isSingleWord()) - return !VAL; - - for (unsigned i = 0; i != getNumWords(); ++i) - if (pVal[i]) - return false; - return true; + return *this == 0; } /// @} @@ -688,7 +708,16 @@ public: /// than 64, the value is zero filled in the unspecified high order bits. /// /// \returns *this after assignment of RHS value. - APInt &operator=(uint64_t RHS); + APInt &operator=(uint64_t RHS) { + if (isSingleWord()) { + VAL = RHS; + clearUnusedBits(); + } else { + pVal[0] = RHS; + memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); + } + return *this; + } /// \brief Bitwise AND assignment operator. /// @@ -696,7 +725,29 @@ public: /// assigned to *this. /// /// \returns *this after ANDing with RHS. - APInt &operator&=(const APInt &RHS); + APInt &operator&=(const APInt &RHS) { + assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); + if (isSingleWord()) { + VAL &= RHS.VAL; + return *this; + } + return AndAssignSlowCase(RHS); + } + + /// \brief Bitwise AND assignment operator. + /// + /// Performs a bitwise AND operation on this APInt and RHS. RHS is + /// logically zero-extended or truncated to match the bit-width of + /// the LHS. + APInt &operator&=(uint64_t RHS) { + if (isSingleWord()) { + VAL &= RHS; + return *this; + } + pVal[0] &= RHS; + memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); + return *this; + } /// \brief Bitwise OR assignment operator. /// @@ -704,7 +755,14 @@ public: /// assigned *this; /// /// \returns *this after ORing with RHS. - APInt &operator|=(const APInt &RHS); + APInt &operator|=(const APInt &RHS) { + assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); + if (isSingleWord()) { + VAL |= RHS.VAL; + return *this; + } + return OrAssignSlowCase(RHS); + } /// \brief Bitwise OR assignment operator. /// @@ -727,7 +785,29 @@ public: /// assigned to *this. /// /// \returns *this after XORing with RHS. - APInt &operator^=(const APInt &RHS); + APInt &operator^=(const APInt &RHS) { + assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); + if (isSingleWord()) { + VAL ^= RHS.VAL; + return *this; + } + return XorAssignSlowCase(RHS); + } + + /// \brief Bitwise XOR assignment operator. + /// + /// Performs a bitwise XOR operation on this APInt and RHS. RHS is + /// logically zero-extended or truncated to match the bit-width of + /// the LHS. + APInt &operator^=(uint64_t RHS) { + if (isSingleWord()) { + VAL ^= RHS; + clearUnusedBits(); + } else { + pVal[0] ^= RHS; + } + return *this; + } /// \brief Multiplication assignment operator. /// @@ -766,59 +846,6 @@ public: /// \name Binary Operators /// @{ - /// \brief Bitwise AND operator. - /// - /// Performs a bitwise AND operation on *this and RHS. - /// - /// \returns An APInt value representing the bitwise AND of *this and RHS. - APInt operator&(const APInt &RHS) const { - assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); - if (isSingleWord()) - return APInt(getBitWidth(), VAL & RHS.VAL); - return AndSlowCase(RHS); - } - APInt And(const APInt &RHS) const { return this->operator&(RHS); } - - /// \brief Bitwise OR operator. - /// - /// Performs a bitwise OR operation on *this and RHS. - /// - /// \returns An APInt value representing the bitwise OR of *this and RHS. - APInt operator|(const APInt &RHS) const { - assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); - if (isSingleWord()) - return APInt(getBitWidth(), VAL | RHS.VAL); - return OrSlowCase(RHS); - } - - /// \brief Bitwise OR function. - /// - /// Performs a bitwise or on *this and RHS. This is implemented by simply - /// calling operator|. - /// - /// \returns An APInt value representing the bitwise OR of *this and RHS. - APInt Or(const APInt &RHS) const { return this->operator|(RHS); } - - /// \brief Bitwise XOR operator. - /// - /// Performs a bitwise XOR operation on *this and RHS. - /// - /// \returns An APInt value representing the bitwise XOR of *this and RHS. - APInt operator^(const APInt &RHS) const { - assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); - if (isSingleWord()) - return APInt(BitWidth, VAL ^ RHS.VAL); - return XorSlowCase(RHS); - } - - /// \brief Bitwise XOR function. - /// - /// Performs a bitwise XOR operation on *this and RHS. This is implemented - /// through the usage of operator^. - /// - /// \returns An APInt value representing the bitwise XOR of *this and RHS. - APInt Xor(const APInt &RHS) const { return this->operator^(RHS); } - /// \brief Multiplication operator. /// /// Multiplies this APInt by RHS and returns the result. @@ -842,7 +869,14 @@ public: /// \brief Logical right-shift function. /// /// Logical right-shift this APInt by shiftAmt. - APInt lshr(unsigned shiftAmt) const; + APInt lshr(unsigned shiftAmt) const { + APInt R(*this); + R.lshrInPlace(shiftAmt); + return R; + } + + /// Logical right-shift this APInt by shiftAmt in place. + void lshrInPlace(unsigned shiftAmt); /// \brief Left-shift function. /// @@ -1012,7 +1046,7 @@ public: /// the validity of the less-than relationship. /// /// \returns true if *this < RHS when both are considered unsigned. - bool ult(const APInt &RHS) const; + bool ult(const APInt &RHS) const LLVM_READONLY; /// \brief Unsigned less than comparison /// @@ -1030,7 +1064,7 @@ public: /// validity of the less-than relationship. /// /// \returns true if *this < RHS when both are considered signed. - bool slt(const APInt &RHS) const; + bool slt(const APInt &RHS) const LLVM_READONLY; /// \brief Signed less than comparison /// @@ -1144,7 +1178,11 @@ public: /// This operation tests if there are any pairs of corresponding bits /// between this APInt and RHS that are both set. - bool intersects(const APInt &RHS) const { return (*this & RHS) != 0; } + bool intersects(const APInt &RHS) const { + APInt temp(*this); + temp &= RHS; + return temp != 0; + } /// @} /// \name Resizing Operators @@ -1203,11 +1241,9 @@ public: void setAllBits() { if (isSingleWord()) VAL = UINT64_MAX; - else { + else // Set all the bits in all the words. - for (unsigned i = 0; i < getNumWords(); ++i) - pVal[i] = UINT64_MAX; - } + memset(pVal, -1, getNumWords() * APINT_WORD_SIZE); // Clear the unused ones clearUnusedBits(); } @@ -1217,6 +1253,49 @@ public: /// Set the given bit to 1 whose position is given as "bitPosition". void setBit(unsigned bitPosition); + /// Set the sign bit to 1. + void setSignBit() { + setBit(BitWidth - 1); + } + + /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1. + void setBits(unsigned loBit, unsigned hiBit) { + assert(hiBit <= BitWidth && "hiBit out of range"); + assert(loBit <= BitWidth && "loBit out of range"); + if (loBit == hiBit) + return; + if (loBit > hiBit) { + setLowBits(hiBit); + setHighBits(BitWidth - loBit); + return; + } + if (loBit < APINT_BITS_PER_WORD && hiBit <= APINT_BITS_PER_WORD) { + uint64_t mask = UINT64_MAX >> (APINT_BITS_PER_WORD - (hiBit - loBit)); + mask <<= loBit; + if (isSingleWord()) + VAL |= mask; + else + pVal[0] |= mask; + } else { + setBitsSlowCase(loBit, hiBit); + } + } + + /// Set the top bits starting from loBit. + void setBitsFrom(unsigned loBit) { + return setBits(loBit, BitWidth); + } + + /// Set the bottom loBits bits. + void setLowBits(unsigned loBits) { + return setBits(0, loBits); + } + + /// Set the top hiBits bits. + void setHighBits(unsigned hiBits) { + return setBits(BitWidth - hiBits, BitWidth); + } + /// \brief Set every bit to 0. void clearAllBits() { if (isSingleWord()) @@ -1232,13 +1311,12 @@ public: /// \brief Toggle every bit to its opposite value. void flipAllBits() { - if (isSingleWord()) + if (isSingleWord()) { VAL ^= UINT64_MAX; - else { - for (unsigned i = 0; i < getNumWords(); ++i) - pVal[i] ^= UINT64_MAX; + clearUnusedBits(); + } else { + flipAllBitsSlowCase(); } - clearUnusedBits(); } /// \brief Toggles a given bit to its opposite value. @@ -1247,6 +1325,12 @@ public: /// as "bitPosition". void flipBit(unsigned bitPosition); + /// Insert the bits from a smaller APInt starting at bitPosition. + void insertBits(const APInt &SubBits, unsigned bitPosition); + + /// Return an APInt with the extracted bits [bitPosition,bitPosition+numBits). + APInt extractBits(unsigned numBits, unsigned bitPosition) const; + /// @} /// \name Value Characterization Functions /// @{ @@ -1356,7 +1440,7 @@ public: /// /// \returns 0 if the high order bit is not set, otherwise returns the number /// of 1 bits from the most significant to the least - unsigned countLeadingOnes() const; + unsigned countLeadingOnes() const LLVM_READONLY; /// Computes the number of leading bits of this APInt that are equal to its /// sign bit. @@ -1372,7 +1456,7 @@ public: /// /// \returns BitWidth if the value is zero, otherwise returns the number of /// zeros from the least significant bit to the first one bit. - unsigned countTrailingZeros() const; + unsigned countTrailingZeros() const LLVM_READONLY; /// \brief Count the number of trailing one bits. /// @@ -1589,46 +1673,50 @@ public: /// Sets the least significant part of a bignum to the input value, and zeroes /// out higher parts. - static void tcSet(integerPart *, integerPart, unsigned int); + static void tcSet(WordType *, WordType, unsigned); /// Assign one bignum to another. - static void tcAssign(integerPart *, const integerPart *, unsigned int); + static void tcAssign(WordType *, const WordType *, unsigned); /// Returns true if a bignum is zero, false otherwise. - static bool tcIsZero(const integerPart *, unsigned int); + static bool tcIsZero(const WordType *, unsigned); /// Extract the given bit of a bignum; returns 0 or 1. Zero-based. - static int tcExtractBit(const integerPart *, unsigned int bit); + static int tcExtractBit(const WordType *, unsigned bit); /// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to /// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least /// significant bit of DST. All high bits above srcBITS in DST are /// zero-filled. - static void tcExtract(integerPart *, unsigned int dstCount, - const integerPart *, unsigned int srcBits, - unsigned int srcLSB); + static void tcExtract(WordType *, unsigned dstCount, + const WordType *, unsigned srcBits, + unsigned srcLSB); /// Set the given bit of a bignum. Zero-based. - static void tcSetBit(integerPart *, unsigned int bit); + static void tcSetBit(WordType *, unsigned bit); /// Clear the given bit of a bignum. Zero-based. - static void tcClearBit(integerPart *, unsigned int bit); + static void tcClearBit(WordType *, unsigned bit); /// Returns the bit number of the least or most significant set bit of a /// number. If the input number has no bits set -1U is returned. - static unsigned int tcLSB(const integerPart *, unsigned int); - static unsigned int tcMSB(const integerPart *parts, unsigned int n); + static unsigned tcLSB(const WordType *, unsigned n); + static unsigned tcMSB(const WordType *parts, unsigned n); /// Negate a bignum in-place. - static void tcNegate(integerPart *, unsigned int); + static void tcNegate(WordType *, unsigned); /// DST += RHS + CARRY where CARRY is zero or one. Returns the carry flag. - static integerPart tcAdd(integerPart *, const integerPart *, - integerPart carry, unsigned); + static WordType tcAdd(WordType *, const WordType *, + WordType carry, unsigned); + /// DST += RHS. Returns the carry flag. + static WordType tcAddPart(WordType *, WordType, unsigned); /// DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag. - static integerPart tcSubtract(integerPart *, const integerPart *, - integerPart carry, unsigned); + static WordType tcSubtract(WordType *, const WordType *, + WordType carry, unsigned); + /// DST -= RHS. Returns the carry flag. + static WordType tcSubtractPart(WordType *, WordType, unsigned); /// DST += SRC * MULTIPLIER + PART if add is true /// DST = SRC * MULTIPLIER + PART if add is false @@ -1640,23 +1728,23 @@ public: /// Otherwise DST is filled with the least significant DSTPARTS parts of the /// result, and if all of the omitted higher parts were zero return zero, /// otherwise overflow occurred and return one. - static int tcMultiplyPart(integerPart *dst, const integerPart *src, - integerPart multiplier, integerPart carry, - unsigned int srcParts, unsigned int dstParts, + static int tcMultiplyPart(WordType *dst, const WordType *src, + WordType multiplier, WordType carry, + unsigned srcParts, unsigned dstParts, bool add); /// DST = LHS * RHS, where DST has the same width as the operands and is /// filled with the least significant parts of the result. Returns one if /// overflow occurred, otherwise zero. DST must be disjoint from both /// operands. - static int tcMultiply(integerPart *, const integerPart *, const integerPart *, + static int tcMultiply(WordType *, const WordType *, const WordType *, unsigned); /// DST = LHS * RHS, where DST has width the sum of the widths of the /// operands. No overflow occurs. DST must be disjoint from both /// operands. Returns the number of parts required to hold the result. - static unsigned int tcFullMultiply(integerPart *, const integerPart *, - const integerPart *, unsigned, unsigned); + static unsigned tcFullMultiply(WordType *, const WordType *, + const WordType *, unsigned, unsigned); /// If RHS is zero LHS and REMAINDER are left unchanged, return one. /// Otherwise set LHS to LHS / RHS with the fractional part discarded, set @@ -1667,38 +1755,39 @@ public: /// SCRATCH is a bignum of the same size as the operands and result for use by /// the routine; its contents need not be initialized and are destroyed. LHS, /// REMAINDER and SCRATCH must be distinct. - static int tcDivide(integerPart *lhs, const integerPart *rhs, - integerPart *remainder, integerPart *scratch, - unsigned int parts); + static int tcDivide(WordType *lhs, const WordType *rhs, + WordType *remainder, WordType *scratch, + unsigned parts); /// Shift a bignum left COUNT bits. Shifted in bits are zero. There are no /// restrictions on COUNT. - static void tcShiftLeft(integerPart *, unsigned int parts, - unsigned int count); + static void tcShiftLeft(WordType *, unsigned parts, unsigned count); /// Shift a bignum right COUNT bits. Shifted in bits are zero. There are no /// restrictions on COUNT. - static void tcShiftRight(integerPart *, unsigned int parts, - unsigned int count); + static void tcShiftRight(WordType *, unsigned parts, unsigned count); /// The obvious AND, OR and XOR and complement operations. - static void tcAnd(integerPart *, const integerPart *, unsigned int); - static void tcOr(integerPart *, const integerPart *, unsigned int); - static void tcXor(integerPart *, const integerPart *, unsigned int); - static void tcComplement(integerPart *, unsigned int); + static void tcAnd(WordType *, const WordType *, unsigned); + static void tcOr(WordType *, const WordType *, unsigned); + static void tcXor(WordType *, const WordType *, unsigned); + static void tcComplement(WordType *, unsigned); /// Comparison (unsigned) of two bignums. - static int tcCompare(const integerPart *, const integerPart *, unsigned int); + static int tcCompare(const WordType *, const WordType *, unsigned); /// Increment a bignum in-place. Return the carry flag. - static integerPart tcIncrement(integerPart *, unsigned int); + static WordType tcIncrement(WordType *dst, unsigned parts) { + return tcAddPart(dst, 1, parts); + } /// Decrement a bignum in-place. Return the borrow flag. - static integerPart tcDecrement(integerPart *, unsigned int); + static WordType tcDecrement(WordType *dst, unsigned parts) { + return tcSubtractPart(dst, 1, parts); + } /// Set the least significant BITS and clear the rest. - static void tcSetLeastSignificantBits(integerPart *, unsigned int, - unsigned int bits); + static void tcSetLeastSignificantBits(WordType *, unsigned, unsigned bits); /// \brief debug method void dump() const; @@ -1723,6 +1812,74 @@ inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; } inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; } +/// \brief Unary bitwise complement operator. +/// +/// \returns an APInt that is the bitwise complement of \p v. +inline APInt operator~(APInt v) { + v.flipAllBits(); + return v; +} + +inline APInt operator&(APInt a, const APInt &b) { + a &= b; + return a; +} + +inline APInt operator&(const APInt &a, APInt &&b) { + b &= a; + return std::move(b); +} + +inline APInt operator&(APInt a, uint64_t RHS) { + a &= RHS; + return a; +} + +inline APInt operator&(uint64_t LHS, APInt b) { + b &= LHS; + return b; +} + +inline APInt operator|(APInt a, const APInt &b) { + a |= b; + return a; +} + +inline APInt operator|(const APInt &a, APInt &&b) { + b |= a; + return std::move(b); +} + +inline APInt operator|(APInt a, uint64_t RHS) { + a |= RHS; + return a; +} + +inline APInt operator|(uint64_t LHS, APInt b) { + b |= LHS; + return b; +} + +inline APInt operator^(APInt a, const APInt &b) { + a ^= b; + return a; +} + +inline APInt operator^(const APInt &a, APInt &&b) { + b ^= a; + return std::move(b); +} + +inline APInt operator^(APInt a, uint64_t RHS) { + a ^= RHS; + return a; +} + +inline APInt operator^(uint64_t LHS, APInt b) { + b ^= LHS; + return b; +} + inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) { I.print(OS, true); return OS; @@ -1799,47 +1956,13 @@ inline const APInt &umax(const APInt &A, const APInt &B) { return A.ugt(B) ? A : B; } -/// \brief Check if the specified APInt has a N-bits unsigned integer value. -inline bool isIntN(unsigned N, const APInt &APIVal) { return APIVal.isIntN(N); } - -/// \brief Check if the specified APInt has a N-bits signed integer value. -inline bool isSignedIntN(unsigned N, const APInt &APIVal) { - return APIVal.isSignedIntN(N); -} - -/// \returns true if the argument APInt value is a sequence of ones starting at -/// the least significant bit with the remainder zero. -inline bool isMask(unsigned numBits, const APInt &APIVal) { - return numBits <= APIVal.getBitWidth() && - APIVal == APInt::getLowBitsSet(APIVal.getBitWidth(), numBits); -} - -/// \returns true if the argument is a non-empty sequence of ones starting at -/// the least significant bit with the remainder zero (32 bit version). -/// Ex. isMask(0x0000FFFFU) == true. -inline bool isMask(const APInt &Value) { - return (Value != 0) && ((Value + 1) & Value) == 0; -} - -/// \brief Return true if the argument APInt value contains a sequence of ones -/// with the remainder zero. -inline bool isShiftedMask(unsigned numBits, const APInt &APIVal) { - return isMask(numBits, (APIVal - APInt(numBits, 1)) | APIVal); -} - -/// \brief Returns a byte-swapped representation of the specified APInt Value. -inline APInt byteSwap(const APInt &APIVal) { return APIVal.byteSwap(); } - -/// \brief Returns the floor log base 2 of the specified APInt value. -inline unsigned logBase2(const APInt &APIVal) { return APIVal.logBase2(); } - -/// \brief Compute GCD of two APInt values. +/// \brief Compute GCD of two unsigned APInt values. /// /// This function returns the greatest common divisor of the two APInt values /// using Euclid's algorithm. /// -/// \returns the greatest common divisor of Val1 and Val2 -APInt GreatestCommonDivisor(const APInt &Val1, const APInt &Val2); +/// \returns the greatest common divisor of A and B. +APInt GreatestCommonDivisor(APInt A, APInt B); /// \brief Converts the given APInt to a double value. /// @@ -1879,83 +2002,6 @@ inline APInt RoundFloatToAPInt(float Float, unsigned width) { return RoundDoubleToAPInt(double(Float), width); } -/// \brief Arithmetic right-shift function. -/// -/// Arithmetic right-shift the APInt by shiftAmt. -inline APInt ashr(const APInt &LHS, unsigned shiftAmt) { - return LHS.ashr(shiftAmt); -} - -/// \brief Logical right-shift function. -/// -/// Logical right-shift the APInt by shiftAmt. -inline APInt lshr(const APInt &LHS, unsigned shiftAmt) { - return LHS.lshr(shiftAmt); -} - -/// \brief Left-shift function. -/// -/// Left-shift the APInt by shiftAmt. -inline APInt shl(const APInt &LHS, unsigned shiftAmt) { - return LHS.shl(shiftAmt); -} - -/// \brief Signed division function for APInt. -/// -/// Signed divide APInt LHS by APInt RHS. -inline APInt sdiv(const APInt &LHS, const APInt &RHS) { return LHS.sdiv(RHS); } - -/// \brief Unsigned division function for APInt. -/// -/// Unsigned divide APInt LHS by APInt RHS. -inline APInt udiv(const APInt &LHS, const APInt &RHS) { return LHS.udiv(RHS); } - -/// \brief Function for signed remainder operation. -/// -/// Signed remainder operation on APInt. -inline APInt srem(const APInt &LHS, const APInt &RHS) { return LHS.srem(RHS); } - -/// \brief Function for unsigned remainder operation. -/// -/// Unsigned remainder operation on APInt. -inline APInt urem(const APInt &LHS, const APInt &RHS) { return LHS.urem(RHS); } - -/// \brief Function for multiplication operation. -/// -/// Performs multiplication on APInt values. -inline APInt mul(const APInt &LHS, const APInt &RHS) { return LHS * RHS; } - -/// \brief Function for addition operation. -/// -/// Performs addition on APInt values. -inline APInt add(const APInt &LHS, const APInt &RHS) { return LHS + RHS; } - -/// \brief Function for subtraction operation. -/// -/// Performs subtraction on APInt values. -inline APInt sub(const APInt &LHS, const APInt &RHS) { return LHS - RHS; } - -/// \brief Bitwise AND function for APInt. -/// -/// Performs bitwise AND operation on APInt LHS and -/// APInt RHS. -inline APInt And(const APInt &LHS, const APInt &RHS) { return LHS & RHS; } - -/// \brief Bitwise OR function for APInt. -/// -/// Performs bitwise OR operation on APInt LHS and APInt RHS. -inline APInt Or(const APInt &LHS, const APInt &RHS) { return LHS | RHS; } - -/// \brief Bitwise XOR function for APInt. -/// -/// Performs bitwise XOR operation on APInt. -inline APInt Xor(const APInt &LHS, const APInt &RHS) { return LHS ^ RHS; } - -/// \brief Bitwise complement function. -/// -/// Performs a bitwise complement operation on APInt. -inline APInt Not(const APInt &APIVal) { return ~APIVal; } - } // End of APIntOps namespace // See friend declaration above. This additional declaration is required in diff --git a/include/llvm/ADT/APSInt.h b/include/llvm/ADT/APSInt.h index 813b3686d6b1a..5b6dfa4a4b64e 100644 --- a/include/llvm/ADT/APSInt.h +++ b/include/llvm/ADT/APSInt.h @@ -235,19 +235,16 @@ public: assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!"); return APSInt(static_cast<const APInt&>(*this) & RHS, IsUnsigned); } - APSInt And(const APSInt &RHS) const { return this->operator&(RHS); } APSInt operator|(const APSInt& RHS) const { assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!"); return APSInt(static_cast<const APInt&>(*this) | RHS, IsUnsigned); } - APSInt Or(const APSInt &RHS) const { return this->operator|(RHS); } APSInt operator^(const APSInt &RHS) const { assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!"); return APSInt(static_cast<const APInt&>(*this) ^ RHS, IsUnsigned); } - APSInt Xor(const APSInt &RHS) const { return this->operator^(RHS); } APSInt operator*(const APSInt& RHS) const { assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!"); diff --git a/include/llvm/ADT/ArrayRef.h b/include/llvm/ADT/ArrayRef.h index b3fe31f4a806d..6b35d0aec8b2b 100644 --- a/include/llvm/ADT/ArrayRef.h +++ b/include/llvm/ADT/ArrayRef.h @@ -487,6 +487,18 @@ namespace llvm { return ArrayRef<T>(Arr); } + /// Construct a MutableArrayRef from a single element. + template<typename T> + MutableArrayRef<T> makeMutableArrayRef(T &OneElt) { + return OneElt; + } + + /// Construct a MutableArrayRef from a pointer and length. + template<typename T> + MutableArrayRef<T> makeMutableArrayRef(T *data, size_t length) { + return MutableArrayRef<T>(data, length); + } + /// @} /// @name ArrayRef Comparison Operators /// @{ diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h index cf3756d0d9c1f..8240d01ae977c 100644 --- a/include/llvm/ADT/BitVector.h +++ b/include/llvm/ADT/BitVector.h @@ -161,6 +161,17 @@ public: return -1; } + /// find_first_unset - Returns the index of the first unset bit, -1 if all + /// of the bits are set. + int find_first_unset() const { + for (unsigned i = 0; i < NumBitWords(size()); ++i) + if (Bits[i] != ~0UL) { + unsigned Result = i * BITWORD_SIZE + countTrailingOnes(Bits[i]); + return Result < size() ? Result : -1; + } + return -1; + } + /// find_next - Returns the index of the next set bit following the /// "Prev" bit. Returns -1 if the next set bit is not found. int find_next(unsigned Prev) const { @@ -184,6 +195,30 @@ public: return -1; } + /// find_next_unset - Returns the index of the next usnet bit following the + /// "Prev" bit. Returns -1 if all remaining bits are set. + int find_next_unset(unsigned Prev) const { + ++Prev; + if (Prev >= Size) + return -1; + + unsigned WordPos = Prev / BITWORD_SIZE; + unsigned BitPos = Prev % BITWORD_SIZE; + BitWord Copy = Bits[WordPos]; + // Mask in previous bits. + BitWord Mask = (1 << BitPos) - 1; + Copy |= Mask; + + if (Copy != ~0UL) + return next_unset_in_word(WordPos, Copy); + + // Check subsequent words. + for (unsigned i = WordPos + 1; i < NumBitWords(size()); ++i) + if (Bits[i] != ~0UL) + return next_unset_in_word(i, Bits[i]); + return -1; + } + /// clear - Clear all bits. void clear() { Size = 0; @@ -503,6 +538,11 @@ public: } private: + int next_unset_in_word(int WordIndex, BitWord Word) const { + unsigned Result = WordIndex * BITWORD_SIZE + countTrailingOnes(Word); + return Result < size() ? Result : -1; + } + unsigned NumBitWords(unsigned S) const { return (S + BITWORD_SIZE-1) / BITWORD_SIZE; } @@ -539,7 +579,8 @@ private: } void init_words(BitWord *B, unsigned NumWords, bool t) { - memset(B, 0 - (int)t, NumWords*sizeof(BitWord)); + if (NumWords > 0) + memset(B, 0 - (int)t, NumWords*sizeof(BitWord)); } template<bool AddBits, bool InvertMask> diff --git a/include/llvm/ADT/BreadthFirstIterator.h b/include/llvm/ADT/BreadthFirstIterator.h new file mode 100644 index 0000000000000..eaeecb6e057ff --- /dev/null +++ b/include/llvm/ADT/BreadthFirstIterator.h @@ -0,0 +1,164 @@ +//===- llvm/ADT/BreadthFirstIterator.h - Breadth First iterator -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file builds on the ADT/GraphTraits.h file to build a generic breadth +// first graph iterator. This file exposes the following functions/types: +// +// bf_begin/bf_end/bf_iterator +// * Normal breadth-first iteration - visit a graph level-by-level. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_BREADTHFIRSTITERATOR_H +#define LLVM_ADT_BREADTHFIRSTITERATOR_H + +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/None.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/iterator_range.h" +#include <iterator> +#include <queue> +#include <set> +#include <utility> + +namespace llvm { + +// bf_iterator_storage - A private class which is used to figure out where to +// store the visited set. We only provide a non-external variant for now. +template <class SetType> class bf_iterator_storage { +public: + SetType Visited; +}; + +// The visited state for the iteration is a simple set. +template <typename NodeRef, unsigned SmallSize = 8> +using bf_iterator_default_set = SmallPtrSet<NodeRef, SmallSize>; + +// Generic Breadth first search iterator. +template <class GraphT, + class SetType = + bf_iterator_default_set<typename GraphTraits<GraphT>::NodeRef>, + class GT = GraphTraits<GraphT>> +class bf_iterator + : public std::iterator<std::forward_iterator_tag, typename GT::NodeRef>, + public bf_iterator_storage<SetType> { + typedef std::iterator<std::forward_iterator_tag, typename GT::NodeRef> super; + + typedef typename GT::NodeRef NodeRef; + typedef typename GT::ChildIteratorType ChildItTy; + + // First element is the node reference, second is the next child to visit. + typedef std::pair<NodeRef, Optional<ChildItTy>> QueueElement; + + // Visit queue - used to maintain BFS ordering. + // Optional<> because we need markers for levels. + std::queue<Optional<QueueElement>> VisitQueue; + + // Current level. + unsigned Level; + +private: + inline bf_iterator(NodeRef Node) { + this->Visited.insert(Node); + Level = 0; + + // Also, insert a dummy node as marker. + VisitQueue.push(QueueElement(Node, None)); + VisitQueue.push(None); + } + + inline bf_iterator() = default; + + inline void toNext() { + Optional<QueueElement> Head = VisitQueue.front(); + QueueElement H = Head.getValue(); + NodeRef Node = H.first; + Optional<ChildItTy> &ChildIt = H.second; + + if (!ChildIt) + ChildIt.emplace(GT::child_begin(Node)); + while (*ChildIt != GT::child_end(Node)) { + NodeRef Next = *(*ChildIt)++; + + // Already visited? + if (this->Visited.insert(Next).second) + VisitQueue.push(QueueElement(Next, None)); + } + VisitQueue.pop(); + + // Go to the next element skipping markers if needed. + if (!VisitQueue.empty()) { + Head = VisitQueue.front(); + if (Head != None) + return; + Level += 1; + VisitQueue.pop(); + + // Don't push another marker if this is the last + // element. + if (!VisitQueue.empty()) + VisitQueue.push(None); + } + } + +public: + typedef typename super::pointer pointer; + + // Provide static begin and end methods as our public "constructors" + static bf_iterator begin(const GraphT &G) { + return bf_iterator(GT::getEntryNode(G)); + } + + static bf_iterator end(const GraphT &G) { return bf_iterator(); } + + bool operator==(const bf_iterator &RHS) const { + return VisitQueue == RHS.VisitQueue; + } + + bool operator!=(const bf_iterator &RHS) const { return !(*this == RHS); } + + const NodeRef &operator*() const { return VisitQueue.front()->first; } + + // This is a nonstandard operator-> that dereferenfces the pointer an extra + // time so that you can actually call methods on the node, because the + // contained type is a pointer. + NodeRef operator->() const { return **this; } + + bf_iterator &operator++() { // Pre-increment + toNext(); + return *this; + } + + bf_iterator operator++(int) { // Post-increment + bf_iterator ItCopy = *this; + ++*this; + return ItCopy; + } + + unsigned getLevel() const { return Level; } +}; + +// Provide global constructors that automatically figure out correct types. +template <class T> bf_iterator<T> bf_begin(const T &G) { + return bf_iterator<T>::begin(G); +} + +template <class T> bf_iterator<T> bf_end(const T &G) { + return bf_iterator<T>::end(G); +} + +// Provide an accessor method to use them in range-based patterns. +template <class T> iterator_range<bf_iterator<T>> breadth_first(const T &G) { + return make_range(bf_begin(G), bf_end(G)); +} + +} // end namespace llvm + +#endif // LLVM_ADT_BREADTHFIRSTITERATOR_H diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index 0b4b09d4b7330..fd8d3bf368a88 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -53,6 +53,9 @@ class DenseMapIterator; template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT, typename BucketT> class DenseMapBase : public DebugEpochBase { + template <typename T> + using const_arg_type_t = typename const_pointer_or_const_ref<T>::type; + public: typedef unsigned size_type; typedef KeyT key_type; @@ -119,18 +122,18 @@ public: } /// Return 1 if the specified key is in the map, 0 otherwise. - size_type count(const KeyT &Val) const { + size_type count(const_arg_type_t<KeyT> Val) const { const BucketT *TheBucket; return LookupBucketFor(Val, TheBucket) ? 1 : 0; } - iterator find(const KeyT &Val) { + iterator find(const_arg_type_t<KeyT> Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) return iterator(TheBucket, getBucketsEnd(), *this, true); return end(); } - const_iterator find(const KeyT &Val) const { + const_iterator find(const_arg_type_t<KeyT> Val) const { const BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) return const_iterator(TheBucket, getBucketsEnd(), *this, true); @@ -159,7 +162,7 @@ public: /// lookup - Return the entry for the specified key, or a default /// constructed value if no such entry exists. - ValueT lookup(const KeyT &Val) const { + ValueT lookup(const_arg_type_t<KeyT> Val) const { const BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) return TheBucket->getSecond(); @@ -389,6 +392,8 @@ protected: return KeyInfoT::getHashValue(Val); } static const KeyT getEmptyKey() { + static_assert(std::is_base_of<DenseMapBase, DerivedT>::value, + "Must pass the derived type to this template!"); return KeyInfoT::getEmptyKey(); } static const KeyT getTombstoneKey() { diff --git a/include/llvm/ADT/DenseMapInfo.h b/include/llvm/ADT/DenseMapInfo.h index a844ebcccf5b8..bb973ac650634 100644 --- a/include/llvm/ADT/DenseMapInfo.h +++ b/include/llvm/ADT/DenseMapInfo.h @@ -60,6 +60,16 @@ template<> struct DenseMapInfo<char> { } }; +// Provide DenseMapInfo for unsigned shorts. +template <> struct DenseMapInfo<unsigned short> { + static inline unsigned short getEmptyKey() { return 0xFFFF; } + static inline unsigned short getTombstoneKey() { return 0xFFFF - 1; } + static unsigned getHashValue(const unsigned short &Val) { return Val * 37U; } + static bool isEqual(const unsigned short &LHS, const unsigned short &RHS) { + return LHS == RHS; + } +}; + // Provide DenseMapInfo for unsigned ints. template<> struct DenseMapInfo<unsigned> { static inline unsigned getEmptyKey() { return ~0U; } @@ -95,6 +105,14 @@ template<> struct DenseMapInfo<unsigned long long> { } }; +// Provide DenseMapInfo for shorts. +template <> struct DenseMapInfo<short> { + static inline short getEmptyKey() { return 0x7FFF; } + static inline short getTombstoneKey() { return -0x7FFF - 1; } + static unsigned getHashValue(const short &Val) { return Val * 37U; } + static bool isEqual(const short &LHS, const short &RHS) { return LHS == RHS; } +}; + // Provide DenseMapInfo for ints. template<> struct DenseMapInfo<int> { static inline int getEmptyKey() { return 0x7fffffff; } diff --git a/include/llvm/ADT/DenseSet.h b/include/llvm/ADT/DenseSet.h index b25d3b7cba6f4..fcf304c3ecc41 100644 --- a/include/llvm/ADT/DenseSet.h +++ b/include/llvm/ADT/DenseSet.h @@ -48,6 +48,8 @@ class DenseSetImpl { static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT), "DenseMap buckets unexpectedly large!"); MapTy TheMap; + template <typename T> + using const_arg_type_t = typename const_pointer_or_const_ref<T>::type; public: typedef ValueT key_type; @@ -78,7 +80,7 @@ public: } /// Return 1 if the specified key is in the set, 0 otherwise. - size_type count(const ValueT &V) const { + size_type count(const_arg_type_t<ValueT> V) const { return TheMap.count(V); } @@ -90,9 +92,12 @@ public: // Iterators. + class ConstIterator; + class Iterator { typename MapTy::iterator I; friend class DenseSetImpl; + friend class ConstIterator; public: typedef typename MapTy::iterator::difference_type difference_type; @@ -101,20 +106,24 @@ public: typedef value_type &reference; typedef std::forward_iterator_tag iterator_category; + Iterator() = default; Iterator(const typename MapTy::iterator &i) : I(i) {} ValueT &operator*() { return I->getFirst(); } + const ValueT &operator*() const { return I->getFirst(); } ValueT *operator->() { return &I->getFirst(); } + const ValueT *operator->() const { return &I->getFirst(); } Iterator& operator++() { ++I; return *this; } Iterator operator++(int) { auto T = *this; ++I; return T; } - bool operator==(const Iterator& X) const { return I == X.I; } - bool operator!=(const Iterator& X) const { return I != X.I; } + bool operator==(const ConstIterator& X) const { return I == X.I; } + bool operator!=(const ConstIterator& X) const { return I != X.I; } }; class ConstIterator { typename MapTy::const_iterator I; friend class DenseSet; + friend class Iterator; public: typedef typename MapTy::const_iterator::difference_type difference_type; @@ -123,10 +132,14 @@ public: typedef value_type &reference; typedef std::forward_iterator_tag iterator_category; + ConstIterator(const Iterator &B) : I(B.I) {} + + ConstIterator() = default; + ConstIterator(const typename MapTy::const_iterator &i) : I(i) {} - const ValueT &operator*() { return I->getFirst(); } - const ValueT *operator->() { return &I->getFirst(); } + const ValueT &operator*() const { return I->getFirst(); } + const ValueT *operator->() const { return &I->getFirst(); } ConstIterator& operator++() { ++I; return *this; } ConstIterator operator++(int) { auto T = *this; ++I; return T; } @@ -143,8 +156,8 @@ public: const_iterator begin() const { return ConstIterator(TheMap.begin()); } const_iterator end() const { return ConstIterator(TheMap.end()); } - iterator find(const ValueT &V) { return Iterator(TheMap.find(V)); } - const_iterator find(const ValueT &V) const { + iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(V)); } + const_iterator find(const_arg_type_t<ValueT> V) const { return ConstIterator(TheMap.find(V)); } diff --git a/include/llvm/ADT/DepthFirstIterator.h b/include/llvm/ADT/DepthFirstIterator.h index c54573204588e..b020d48cb3f08 100644 --- a/include/llvm/ADT/DepthFirstIterator.h +++ b/include/llvm/ADT/DepthFirstIterator.h @@ -135,7 +135,7 @@ private: } } this->Visited.completed(Node); - + // Oops, ran out of successors... go up a level on the stack. VisitStack.pop_back(); } while (!VisitStack.empty()); diff --git a/include/llvm/ADT/GraphTraits.h b/include/llvm/ADT/GraphTraits.h index 29bbcb010eeef..2c88c4271b489 100644 --- a/include/llvm/ADT/GraphTraits.h +++ b/include/llvm/ADT/GraphTraits.h @@ -18,6 +18,8 @@ #ifndef LLVM_ADT_GRAPHTRAITS_H #define LLVM_ADT_GRAPHTRAITS_H +#include "llvm/ADT/iterator_range.h" + namespace llvm { // GraphTraits - This class should be specialized by different graph types... @@ -86,6 +88,33 @@ struct Inverse { // inverse falls back to the original graph. template <class T> struct GraphTraits<Inverse<Inverse<T>>> : GraphTraits<T> {}; +// Provide iterator ranges for the graph traits nodes and children +template <class GraphType> +iterator_range<typename GraphTraits<GraphType>::nodes_iterator> +nodes(const GraphType &G) { + return make_range(GraphTraits<GraphType>::nodes_begin(G), + GraphTraits<GraphType>::nodes_end(G)); +} +template <class GraphType> +iterator_range<typename GraphTraits<Inverse<GraphType>>::nodes_iterator> +inverse_nodes(const GraphType &G) { + return make_range(GraphTraits<Inverse<GraphType>>::nodes_begin(G), + GraphTraits<Inverse<GraphType>>::nodes_end(G)); +} + +template <class GraphType> +iterator_range<typename GraphTraits<GraphType>::ChildIteratorType> +children(const typename GraphTraits<GraphType>::NodeRef &G) { + return make_range(GraphTraits<GraphType>::child_begin(G), + GraphTraits<GraphType>::child_end(G)); +} + +template <class GraphType> +iterator_range<typename GraphTraits<Inverse<GraphType>>::ChildIteratorType> +inverse_children(const typename GraphTraits<GraphType>::NodeRef &G) { + return make_range(GraphTraits<Inverse<GraphType>>::child_begin(G), + GraphTraits<Inverse<GraphType>>::child_end(G)); +} } // End llvm namespace #endif diff --git a/include/llvm/ADT/None.h b/include/llvm/ADT/None.h index d69ec17c15f91..c7a99c61994ec 100644 --- a/include/llvm/ADT/None.h +++ b/include/llvm/ADT/None.h @@ -19,8 +19,9 @@ namespace llvm { /// \brief A simple null object to allow implicit construction of Optional<T> /// and similar types without having to spell out the specialization's name. -enum class NoneType { None }; -const NoneType None = None; +// (constant value 1 in an attempt to workaround MSVC build issue... ) +enum class NoneType { None = 1 }; +const NoneType None = NoneType::None; } #endif diff --git a/include/llvm/ADT/PointerUnion.h b/include/llvm/ADT/PointerUnion.h index a8ac18645f3ab..9eb15524c0f30 100644 --- a/include/llvm/ADT/PointerUnion.h +++ b/include/llvm/ADT/PointerUnion.h @@ -31,7 +31,7 @@ template <typename T> struct PointerUnionTypeSelectorReturn { /// Get a type based on whether two types are the same or not. /// /// For: -/// +/// /// \code /// typedef typename PointerUnionTypeSelector<T1, T2, EQ, NE>::Return Ret; /// \endcode @@ -190,17 +190,17 @@ public: }; template <typename PT1, typename PT2> -static bool operator==(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) { +bool operator==(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) { return lhs.getOpaqueValue() == rhs.getOpaqueValue(); } template <typename PT1, typename PT2> -static bool operator!=(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) { +bool operator!=(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) { return lhs.getOpaqueValue() != rhs.getOpaqueValue(); } template <typename PT1, typename PT2> -static bool operator<(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) { +bool operator<(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) { return lhs.getOpaqueValue() < rhs.getOpaqueValue(); } diff --git a/include/llvm/ADT/PostOrderIterator.h b/include/llvm/ADT/PostOrderIterator.h index e519b5c07964a..8fc08eb252eb2 100644 --- a/include/llvm/ADT/PostOrderIterator.h +++ b/include/llvm/ADT/PostOrderIterator.h @@ -268,6 +268,10 @@ inverse_post_order_ext(const T &G, SetType &S) { // with a postorder iterator to build the data structures). The moral of this // story is: Don't create more ReversePostOrderTraversal classes than necessary. // +// Because it does the traversal in its constructor, it won't invalidate when +// BasicBlocks are removed, *but* it may contain erased blocks. Some places +// rely on this behavior (i.e. GVN). +// // This class should be used like this: // { // ReversePostOrderTraversal<Function*> RPOT(FuncPtr); // Expensive to create diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h index ec121e0d55cd4..15945adbe589a 100644 --- a/include/llvm/ADT/STLExtras.h +++ b/include/llvm/ADT/STLExtras.h @@ -23,11 +23,13 @@ #include <cstdlib> // for qsort #include <functional> #include <iterator> +#include <limits> #include <memory> #include <tuple> #include <utility> // for std::pair #include "llvm/ADT/Optional.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/iterator.h" #include "llvm/ADT/iterator_range.h" #include "llvm/Support/Compiler.h" @@ -44,6 +46,10 @@ namespace detail { template <typename RangeT> using IterOfRange = decltype(std::begin(std::declval<RangeT &>())); +template <typename RangeT> +using ValueOfRange = typename std::remove_reference<decltype( + *std::begin(std::declval<RangeT &>()))>::type; + } // End detail namespace //===----------------------------------------------------------------------===// @@ -123,7 +129,7 @@ inline void deleter(T *Ptr) { //===----------------------------------------------------------------------===// // mapped_iterator - This is a simple iterator adapter that causes a function to -// be dereferenced whenever operator* is invoked on the iterator. +// be applied whenever operator* is invoked on the iterator. // template <class RootIt, class UnaryFunc> class mapped_iterator { @@ -134,9 +140,8 @@ public: iterator_category; typedef typename std::iterator_traits<RootIt>::difference_type difference_type; - typedef typename std::result_of< - UnaryFunc(decltype(*std::declval<RootIt>()))> - ::type value_type; + typedef decltype(std::declval<UnaryFunc>()(*std::declval<RootIt>())) + value_type; typedef void pointer; //typedef typename UnaryFunc::result_type *pointer; @@ -356,65 +361,126 @@ template <size_t... I> struct index_sequence; template <class... Ts> struct index_sequence_for; namespace detail { -template <typename... Iters> class zip_first { -public: - typedef std::input_iterator_tag iterator_category; - typedef std::tuple<decltype(*std::declval<Iters>())...> value_type; +using std::declval; + +// We have to alias this since inlining the actual type at the usage site +// in the parameter list of iterator_facade_base<> below ICEs MSVC 2017. +template<typename... Iters> struct ZipTupleType { + typedef std::tuple<decltype(*declval<Iters>())...> type; +}; + +template <typename ZipType, typename... Iters> +using zip_traits = iterator_facade_base< + ZipType, typename std::common_type<std::bidirectional_iterator_tag, + typename std::iterator_traits< + Iters>::iterator_category...>::type, + // ^ TODO: Implement random access methods. + typename ZipTupleType<Iters...>::type, + typename std::iterator_traits<typename std::tuple_element< + 0, std::tuple<Iters...>>::type>::difference_type, + // ^ FIXME: This follows boost::make_zip_iterator's assumption that all + // inner iterators have the same difference_type. It would fail if, for + // instance, the second field's difference_type were non-numeric while the + // first is. + typename ZipTupleType<Iters...>::type *, + typename ZipTupleType<Iters...>::type>; + +template <typename ZipType, typename... Iters> +struct zip_common : public zip_traits<ZipType, Iters...> { + using Base = zip_traits<ZipType, Iters...>; + using value_type = typename Base::value_type; + std::tuple<Iters...> iterators; -private: - template <size_t... Ns> value_type deres(index_sequence<Ns...>) { +protected: + template <size_t... Ns> value_type deref(index_sequence<Ns...>) const { return value_type(*std::get<Ns>(iterators)...); } - template <size_t... Ns> decltype(iterators) tup_inc(index_sequence<Ns...>) { + template <size_t... Ns> + decltype(iterators) tup_inc(index_sequence<Ns...>) const { return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...); } + template <size_t... Ns> + decltype(iterators) tup_dec(index_sequence<Ns...>) const { + return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...); + } + public: - value_type operator*() { return deres(index_sequence_for<Iters...>{}); } + zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {} + + value_type operator*() { return deref(index_sequence_for<Iters...>{}); } - void operator++() { iterators = tup_inc(index_sequence_for<Iters...>{}); } + const value_type operator*() const { + return deref(index_sequence_for<Iters...>{}); + } - bool operator!=(const zip_first<Iters...> &other) const { - return std::get<0>(iterators) != std::get<0>(other.iterators); + ZipType &operator++() { + iterators = tup_inc(index_sequence_for<Iters...>{}); + return *reinterpret_cast<ZipType *>(this); } - zip_first(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {} + + ZipType &operator--() { + static_assert(Base::IsBidirectional, + "All inner iterators must be at least bidirectional."); + iterators = tup_dec(index_sequence_for<Iters...>{}); + return *reinterpret_cast<ZipType *>(this); + } +}; + +template <typename... Iters> +struct zip_first : public zip_common<zip_first<Iters...>, Iters...> { + using Base = zip_common<zip_first<Iters...>, Iters...>; + + bool operator==(const zip_first<Iters...> &other) const { + return std::get<0>(this->iterators) == std::get<0>(other.iterators); + } + + zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {} }; -template <typename... Iters> class zip_shortest : public zip_first<Iters...> { +template <typename... Iters> +class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> { template <size_t... Ns> - bool test(const zip_first<Iters...> &other, index_sequence<Ns...>) const { + bool test(const zip_shortest<Iters...> &other, index_sequence<Ns...>) const { return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) != std::get<Ns>(other.iterators)...}, identity<bool>{}); } public: - bool operator!=(const zip_first<Iters...> &other) const { - return test(other, index_sequence_for<Iters...>{}); + using Base = zip_common<zip_shortest<Iters...>, Iters...>; + + bool operator==(const zip_shortest<Iters...> &other) const { + return !test(other, index_sequence_for<Iters...>{}); } - zip_shortest(Iters &&... ts) - : zip_first<Iters...>(std::forward<Iters>(ts)...) {} + + zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {} }; template <template <typename...> class ItType, typename... Args> class zippy { public: - typedef ItType<decltype(std::begin(std::declval<Args>()))...> iterator; + using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>; + using iterator_category = typename iterator::iterator_category; + using value_type = typename iterator::value_type; + using difference_type = typename iterator::difference_type; + using pointer = typename iterator::pointer; + using reference = typename iterator::reference; private: std::tuple<Args...> ts; - template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) { + template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const { return iterator(std::begin(std::get<Ns>(ts))...); } - template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) { + template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const { return iterator(std::end(std::get<Ns>(ts))...); } public: - iterator begin() { return begin_impl(index_sequence_for<Args...>{}); } - iterator end() { return end_impl(index_sequence_for<Args...>{}); } + iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); } + iterator end() const { return end_impl(index_sequence_for<Args...>{}); } zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {} }; } // End detail namespace @@ -777,6 +843,13 @@ auto remove_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) { return std::remove_if(std::begin(Range), std::end(Range), P); } +/// Provide wrappers to std::copy_if which take ranges instead of having to +/// pass begin/end explicitly. +template <typename R, typename OutputIt, typename UnaryPredicate> +OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) { + return std::copy_if(std::begin(Range), std::end(Range), Out, P); +} + /// Wrapper function around std::find to detect if an element exists /// in a container. template <typename R, typename E> @@ -815,6 +888,15 @@ auto partition(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) { return std::partition(std::begin(Range), std::end(Range), P); } +/// \brief Given a range of type R, iterate the entire range and return a +/// SmallVector with elements of the vector. This is useful, for example, +/// when you want to iterate a range and then sort the results. +template <unsigned Size, typename R> +SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size> +to_vector(R &&Range) { + return {std::begin(Range), std::end(Range)}; +} + /// Provide a container algorithm similar to C++ Library Fundamentals v2's /// `erase_if` which is equivalent to: /// @@ -909,47 +991,85 @@ template <typename T> struct deref { }; namespace detail { -template <typename R> class enumerator_impl { -public: - template <typename X> struct result_pair { - result_pair(std::size_t Index, X Value) : Index(Index), Value(Value) {} +template <typename R> class enumerator_iter; - const std::size_t Index; - X Value; - }; +template <typename R> struct result_pair { + friend class enumerator_iter<R>; + + result_pair() : Index(-1) {} + result_pair(std::size_t Index, IterOfRange<R> Iter) + : Index(Index), Iter(Iter) {} - class iterator { - typedef - typename std::iterator_traits<IterOfRange<R>>::reference iter_reference; - typedef result_pair<iter_reference> result_type; + result_pair<R> &operator=(const result_pair<R> &Other) { + Index = Other.Index; + Iter = Other.Iter; + return *this; + } - public: - iterator(IterOfRange<R> &&Iter, std::size_t Index) - : Iter(Iter), Index(Index) {} + std::size_t index() const { return Index; } + const ValueOfRange<R> &value() const { return *Iter; } + ValueOfRange<R> &value() { return *Iter; } - result_type operator*() const { return result_type(Index, *Iter); } +private: + std::size_t Index; + IterOfRange<R> Iter; +}; - iterator &operator++() { - ++Iter; - ++Index; - return *this; - } +template <typename R> +class enumerator_iter + : public iterator_facade_base< + enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>, + typename std::iterator_traits<IterOfRange<R>>::difference_type, + typename std::iterator_traits<IterOfRange<R>>::pointer, + typename std::iterator_traits<IterOfRange<R>>::reference> { + using result_type = result_pair<R>; - bool operator!=(const iterator &RHS) const { return Iter != RHS.Iter; } +public: + explicit enumerator_iter(IterOfRange<R> EndIter) + : Result(std::numeric_limits<size_t>::max(), EndIter) { } - private: - IterOfRange<R> Iter; - std::size_t Index; - }; + enumerator_iter(std::size_t Index, IterOfRange<R> Iter) + : Result(Index, Iter) {} + + result_type &operator*() { return Result; } + const result_type &operator*() const { return Result; } + enumerator_iter<R> &operator++() { + assert(Result.Index != std::numeric_limits<size_t>::max()); + ++Result.Iter; + ++Result.Index; + return *this; + } + + bool operator==(const enumerator_iter<R> &RHS) const { + // Don't compare indices here, only iterators. It's possible for an end + // iterator to have different indices depending on whether it was created + // by calling std::end() versus incrementing a valid iterator. + return Result.Iter == RHS.Result.Iter; + } + + enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) { + Result = Other.Result; + return *this; + } + +private: + result_type Result; +}; + +template <typename R> class enumerator { public: - explicit enumerator_impl(R &&Range) : Range(std::forward<R>(Range)) {} + explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {} - iterator begin() { return iterator(std::begin(Range), 0); } - iterator end() { return iterator(std::end(Range), std::size_t(-1)); } + enumerator_iter<R> begin() { + return enumerator_iter<R>(0, std::begin(TheRange)); + } + enumerator_iter<R> end() { + return enumerator_iter<R>(std::end(TheRange)); + } private: - R Range; + R TheRange; }; } @@ -968,8 +1088,8 @@ private: /// Item 2 - C /// Item 3 - D /// -template <typename R> detail::enumerator_impl<R> enumerate(R &&Range) { - return detail::enumerator_impl<R>(std::forward<R>(Range)); +template <typename R> detail::enumerator<R> enumerate(R &&TheRange) { + return detail::enumerator<R>(std::forward<R>(TheRange)); } namespace detail { diff --git a/include/llvm/ADT/ScopedHashTable.h b/include/llvm/ADT/ScopedHashTable.h index ad805b0991c14..d52128e294a32 100644 --- a/include/llvm/ADT/ScopedHashTable.h +++ b/include/llvm/ADT/ScopedHashTable.h @@ -182,8 +182,8 @@ public: return TopLevelMap.count(Key); } - V lookup(const K &Key) { - typename DenseMap<K, ValTy*, KInfo>::iterator I = TopLevelMap.find(Key); + V lookup(const K &Key) const { + auto I = TopLevelMap.find(Key); if (I != TopLevelMap.end()) return I->second->getValue(); diff --git a/include/llvm/ADT/SetVector.h b/include/llvm/ADT/SetVector.h index 4dc18bc52178f..13378aa3a04ef 100644 --- a/include/llvm/ADT/SetVector.h +++ b/include/llvm/ADT/SetVector.h @@ -119,6 +119,12 @@ public: return vector_.rend(); } + /// \brief Return the first element of the SetVector. + const T &front() const { + assert(!empty() && "Cannot call front() on empty SetVector!"); + return vector_.front(); + } + /// \brief Return the last element of the SetVector. const T &back() const { assert(!empty() && "Cannot call back() on empty SetVector!"); @@ -232,7 +238,7 @@ public: bool operator!=(const SetVector &that) const { return vector_ != that.vector_; } - + /// \brief Compute This := This u S, return whether 'This' changed. /// TODO: We should be able to use set_union from SetOperations.h, but /// SetVector interface is inconsistent with DenseSet. diff --git a/include/llvm/ADT/SmallBitVector.h b/include/llvm/ADT/SmallBitVector.h index bb99e0cf221f7..edb37da38da1b 100644 --- a/include/llvm/ADT/SmallBitVector.h +++ b/include/llvm/ADT/SmallBitVector.h @@ -216,6 +216,18 @@ public: return getPointer()->find_first(); } + /// Returns the index of the first unset bit, -1 if all of the bits are set. + int find_first_unset() const { + if (isSmall()) { + if (count() == getSmallSize()) + return -1; + + uintptr_t Bits = getSmallBits(); + return countTrailingOnes(Bits); + } + return getPointer()->find_first_unset(); + } + /// Returns the index of the next set bit following the "Prev" bit. /// Returns -1 if the next set bit is not found. int find_next(unsigned Prev) const { @@ -230,6 +242,23 @@ public: return getPointer()->find_next(Prev); } + /// Returns the index of the next unset bit following the "Prev" bit. + /// Returns -1 if the next unset bit is not found. + int find_next_unset(unsigned Prev) const { + if (isSmall()) { + ++Prev; + uintptr_t Bits = getSmallBits(); + // Mask in previous bits. + uintptr_t Mask = (1 << Prev) - 1; + Bits |= Mask; + + if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize()) + return -1; + return countTrailingOnes(Bits); + } + return getPointer()->find_next_unset(Prev); + } + /// Clear all bits. void clear() { if (!isSmall()) diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index 49feb9da897a2..196ab6338047c 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -18,6 +18,7 @@ #include "llvm/Config/abi-breaking.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/PointerLikeTypeTraits.h" +#include "llvm/Support/type_traits.h" #include <cassert> #include <cstddef> #include <cstring> @@ -166,8 +167,8 @@ protected: const void *const *P = find_imp(Ptr); if (P == EndPointer()) return false; - - const void ** Loc = const_cast<const void **>(P); + + const void **Loc = const_cast<const void **>(P); assert(*Loc == Ptr && "broken find!"); *Loc = getTombstoneMarker(); NumTombstones++; @@ -193,7 +194,7 @@ protected: return Bucket; return EndPointer(); } - + private: bool isSmall() const { return CurArray == SmallArray; } @@ -259,11 +260,10 @@ protected: } #if LLVM_ENABLE_ABI_BREAKING_CHECKS void RetreatIfNotValid() { - --Bucket; - assert(Bucket <= End); + assert(Bucket >= End); while (Bucket != End && - (*Bucket == SmallPtrSetImplBase::getEmptyMarker() || - *Bucket == SmallPtrSetImplBase::getTombstoneMarker())) { + (Bucket[-1] == SmallPtrSetImplBase::getEmptyMarker() || + Bucket[-1] == SmallPtrSetImplBase::getTombstoneMarker())) { --Bucket; } } @@ -288,6 +288,12 @@ public: // Most methods provided by baseclass. const PtrTy operator*() const { +#if LLVM_ENABLE_ABI_BREAKING_CHECKS + if (ReverseIterate<bool>::value) { + assert(Bucket > End); + return PtrTraits::getFromVoidPointer(const_cast<void *>(Bucket[-1])); + } +#endif assert(Bucket < End); return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket)); } @@ -295,6 +301,7 @@ public: inline SmallPtrSetIterator& operator++() { // Preincrement #if LLVM_ENABLE_ABI_BREAKING_CHECKS if (ReverseIterate<bool>::value) { + --Bucket; RetreatIfNotValid(); return *this; } @@ -343,7 +350,9 @@ struct RoundUpToPowerOfTwo { /// to avoid encoding a particular small size in the interface boundary. template <typename PtrType> class SmallPtrSetImpl : public SmallPtrSetImplBase { + using ConstPtrType = typename add_const_past_pointer<PtrType>::type; typedef PointerLikeTypeTraits<PtrType> PtrTraits; + typedef PointerLikeTypeTraits<ConstPtrType> ConstPtrTraits; protected: // Constructors that forward to the base. @@ -367,7 +376,7 @@ public: /// the element equal to Ptr. std::pair<iterator, bool> insert(PtrType Ptr) { auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr)); - return std::make_pair(iterator(p.first, EndPointer()), p.second); + return std::make_pair(makeIterator(p.first), p.second); } /// erase - If the set contains the specified pointer, remove it and return @@ -375,14 +384,10 @@ public: bool erase(PtrType Ptr) { return erase_imp(PtrTraits::getAsVoidPointer(Ptr)); } - /// count - Return 1 if the specified pointer is in the set, 0 otherwise. - size_type count(PtrType Ptr) const { - return find(Ptr) != endPtr() ? 1 : 0; - } - iterator find(PtrType Ptr) const { - auto *P = find_imp(PtrTraits::getAsVoidPointer(Ptr)); - return iterator(P, EndPointer()); + size_type count(ConstPtrType Ptr) const { return find(Ptr) != end() ? 1 : 0; } + iterator find(ConstPtrType Ptr) const { + return makeIterator(find_imp(ConstPtrTraits::getAsVoidPointer(Ptr))); } template <typename IterT> @@ -395,25 +400,23 @@ public: insert(IL.begin(), IL.end()); } - inline iterator begin() const { + iterator begin() const { #if LLVM_ENABLE_ABI_BREAKING_CHECKS if (ReverseIterate<bool>::value) - return endPtr(); + return makeIterator(EndPointer() - 1); #endif - return iterator(CurArray, EndPointer()); + return makeIterator(CurArray); } - inline iterator end() const { + iterator end() const { return makeIterator(EndPointer()); } + +private: + /// Create an iterator that dereferences to same place as the given pointer. + iterator makeIterator(const void *const *P) const { #if LLVM_ENABLE_ABI_BREAKING_CHECKS if (ReverseIterate<bool>::value) - return iterator(CurArray, CurArray); + return iterator(P == EndPointer() ? CurArray : P + 1, CurArray); #endif - return endPtr(); - } - -private: - inline iterator endPtr() const { - const void *const *End = EndPointer(); - return iterator(End, End); + return iterator(P, EndPointer()); } }; diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h index e2822c46e2667..a82cef6028f94 100644 --- a/include/llvm/ADT/SparseBitVector.h +++ b/include/llvm/ADT/SparseBitVector.h @@ -132,6 +132,17 @@ public: llvm_unreachable("Illegal empty element"); } + /// find_last - Returns the index of the last set bit. + int find_last() const { + for (unsigned I = 0; I < BITWORDS_PER_ELEMENT; ++I) { + unsigned Idx = BITWORDS_PER_ELEMENT - I - 1; + if (Bits[Idx] != 0) + return Idx * BITWORD_SIZE + BITWORD_SIZE - + countLeadingZeros(Bits[Idx]) - 1; + } + llvm_unreachable("Illegal empty element"); + } + /// find_next - Returns the index of the next set bit starting from the /// "Curr" bit. Returns -1 if the next set bit is not found. int find_next(unsigned Curr) const { @@ -768,6 +779,14 @@ public: return (First.index() * ElementSize) + First.find_first(); } + // Return the last set bit in the bitmap. Return -1 if no bits are set. + int find_last() const { + if (Elements.empty()) + return -1; + const SparseBitVectorElement<ElementSize> &Last = *(Elements.rbegin()); + return (Last.index() * ElementSize) + Last.find_last(); + } + // Return true if the SparseBitVector is empty bool empty() const { return Elements.empty(); diff --git a/include/llvm/ADT/StringExtras.h b/include/llvm/ADT/StringExtras.h index 488748a5f6054..8214782bfe800 100644 --- a/include/llvm/ADT/StringExtras.h +++ b/include/llvm/ADT/StringExtras.h @@ -234,6 +234,13 @@ inline std::string join(IteratorT Begin, IteratorT End, StringRef Separator) { return detail::join_impl(Begin, End, Separator, tag()); } +/// Joins the strings in the range [R.begin(), R.end()), adding Separator +/// between the elements. +template <typename Range> +inline std::string join(Range &&R, StringRef Separator) { + return join(R.begin(), R.end(), Separator); +} + /// Joins the strings in the parameter pack \p Items, adding \p Separator /// between the elements. All arguments must be implicitly convertible to /// std::string, or there should be an overload of std::string::operator+=() diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h index 24e3ecf71b135..c36fda7d69065 100644 --- a/include/llvm/ADT/StringMap.h +++ b/include/llvm/ADT/StringMap.h @@ -15,13 +15,13 @@ #define LLVM_ADT_STRINGMAP_H #include "llvm/ADT/StringRef.h" +#include "llvm/ADT/iterator.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/PointerLikeTypeTraits.h" #include <cassert> #include <cstdint> #include <cstdlib> #include <cstring> -#include <utility> #include <initializer_list> #include <new> #include <utility> @@ -32,6 +32,7 @@ namespace llvm { class StringMapConstIterator; template<typename ValueT> class StringMapIterator; + template <typename ValueT> class StringMapKeyIterator; template<typename ValueTy> class StringMapEntry; @@ -312,6 +313,11 @@ public: return const_iterator(TheTable+NumBuckets, true); } + llvm::iterator_range<StringMapKeyIterator<ValueTy>> keys() const { + return make_range(StringMapKeyIterator<ValueTy>(begin()), + StringMapKeyIterator<ValueTy>(end())); + } + iterator find(StringRef Key) { int Bucket = FindKey(Key); if (Bucket == -1) return end(); @@ -444,42 +450,39 @@ public: } }; -template <typename ValueTy> class StringMapConstIterator { +template <typename DerivedTy, typename ValueTy> +class StringMapIterBase + : public iterator_facade_base<DerivedTy, std::forward_iterator_tag, + ValueTy> { protected: StringMapEntryBase **Ptr = nullptr; public: - typedef StringMapEntry<ValueTy> value_type; - - StringMapConstIterator() = default; + StringMapIterBase() = default; - explicit StringMapConstIterator(StringMapEntryBase **Bucket, - bool NoAdvance = false) - : Ptr(Bucket) { + explicit StringMapIterBase(StringMapEntryBase **Bucket, + bool NoAdvance = false) + : Ptr(Bucket) { if (!NoAdvance) AdvancePastEmptyBuckets(); } - const value_type &operator*() const { - return *static_cast<StringMapEntry<ValueTy>*>(*Ptr); - } - const value_type *operator->() const { - return static_cast<StringMapEntry<ValueTy>*>(*Ptr); + DerivedTy &operator=(const DerivedTy &Other) { + Ptr = Other.Ptr; + return static_cast<DerivedTy &>(*this); } - bool operator==(const StringMapConstIterator &RHS) const { - return Ptr == RHS.Ptr; - } - bool operator!=(const StringMapConstIterator &RHS) const { - return Ptr != RHS.Ptr; - } + bool operator==(const DerivedTy &RHS) const { return Ptr == RHS.Ptr; } - inline StringMapConstIterator& operator++() { // Preincrement + DerivedTy &operator++() { // Preincrement ++Ptr; AdvancePastEmptyBuckets(); - return *this; + return static_cast<DerivedTy &>(*this); } - StringMapConstIterator operator++(int) { // Postincrement - StringMapConstIterator tmp = *this; ++*this; return tmp; + + DerivedTy operator++(int) { // Post-increment + DerivedTy Tmp(Ptr); + ++*this; + return Tmp; } private: @@ -489,22 +492,67 @@ private: } }; -template<typename ValueTy> -class StringMapIterator : public StringMapConstIterator<ValueTy> { +template <typename ValueTy> +class StringMapConstIterator + : public StringMapIterBase<StringMapConstIterator<ValueTy>, + const StringMapEntry<ValueTy>> { + using base = StringMapIterBase<StringMapConstIterator<ValueTy>, + const StringMapEntry<ValueTy>>; + public: - StringMapIterator() = default; + StringMapConstIterator() = default; + explicit StringMapConstIterator(StringMapEntryBase **Bucket, + bool NoAdvance = false) + : base(Bucket, NoAdvance) {} + + const StringMapEntry<ValueTy> &operator*() const { + return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr); + } +}; + +template <typename ValueTy> +class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>, + StringMapEntry<ValueTy>> { + using base = + StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>; +public: + StringMapIterator() = default; explicit StringMapIterator(StringMapEntryBase **Bucket, bool NoAdvance = false) - : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) { - } + : base(Bucket, NoAdvance) {} StringMapEntry<ValueTy> &operator*() const { - return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); + return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr); + } + + operator StringMapConstIterator<ValueTy>() const { + return StringMapConstIterator<ValueTy>(this->Ptr, true); } - StringMapEntry<ValueTy> *operator->() const { - return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); +}; + +template <typename ValueTy> +class StringMapKeyIterator + : public iterator_adaptor_base<StringMapKeyIterator<ValueTy>, + StringMapConstIterator<ValueTy>, + std::forward_iterator_tag, StringRef> { + using base = iterator_adaptor_base<StringMapKeyIterator<ValueTy>, + StringMapConstIterator<ValueTy>, + std::forward_iterator_tag, StringRef>; + +public: + StringMapKeyIterator() = default; + + explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter) + : base(std::move(Iter)) {} + + StringRef &operator*() { + Key = this->wrapped()->getKey(); + return Key; } + +private: + StringRef Key; }; } // end namespace llvm diff --git a/include/llvm/ADT/StringRef.h b/include/llvm/ADT/StringRef.h index d80a848c44a13..ce48f6d3bad32 100644 --- a/include/llvm/ADT/StringRef.h +++ b/include/llvm/ADT/StringRef.h @@ -557,6 +557,14 @@ namespace llvm { /// string is well-formed in the given radix. bool getAsInteger(unsigned Radix, APInt &Result) const; + /// Parse the current string as an IEEE double-precision floating + /// point value. The string must be a well-formed double. + /// + /// If \p AllowInexact is false, the function will fail if the string + /// cannot be represented exactly. Otherwise, the function only fails + /// in case of an overflow or underflow. + bool getAsDouble(double &Result, bool AllowInexact = true) const; + /// @} /// @name String Operations /// @{ @@ -600,7 +608,7 @@ namespace llvm { return drop_back(size() - N); } - /// Return a StringRef equal to 'this' but with only the first \p N + /// Return a StringRef equal to 'this' but with only the last \p N /// elements remaining. If \p N is greater than the length of the /// string, the entire string is returned. LLVM_NODISCARD diff --git a/include/llvm/ADT/Triple.h b/include/llvm/ADT/Triple.h index d4130e1e85ae5..e271075b7e2ad 100644 --- a/include/llvm/ADT/Triple.h +++ b/include/llvm/ADT/Triple.h @@ -110,6 +110,7 @@ public: ARMSubArch_v7m, ARMSubArch_v7s, ARMSubArch_v7k, + ARMSubArch_v7ve, ARMSubArch_v6, ARMSubArch_v6m, ARMSubArch_v6k, @@ -206,6 +207,7 @@ public: COFF, ELF, MachO, + Wasm, }; private: @@ -558,7 +560,8 @@ public: /// Tests whether the OS uses glibc. bool isOSGlibc() const { - return getOS() == Triple::Linux || getOS() == Triple::KFreeBSD; + return (getOS() == Triple::Linux || getOS() == Triple::KFreeBSD) && + !isAndroid(); } /// Tests whether the OS uses the ELF binary format. @@ -576,6 +579,11 @@ public: return getObjectFormat() == Triple::MachO; } + /// Tests whether the OS uses the Wasm binary format. + bool isOSBinFormatWasm() const { + return getObjectFormat() == Triple::Wasm; + } + /// Tests whether the target is the PS4 CPU bool isPS4CPU() const { return getArch() == Triple::x86_64 && @@ -592,6 +600,19 @@ public: /// Tests whether the target is Android bool isAndroid() const { return getEnvironment() == Triple::Android; } + bool isAndroidVersionLT(unsigned Major) const { + assert(isAndroid() && "Not an Android triple!"); + + unsigned Env[3]; + getEnvironmentVersion(Env[0], Env[1], Env[2]); + + // 64-bit targets did not exist before API level 21 (Lollipop). + if (isArch64Bit() && Env[0] < 21) + Env[0] = 21; + + return Env[0] < Major; + } + /// Tests whether the environment is musl-libc bool isMusl() const { return getEnvironment() == Triple::Musl || diff --git a/include/llvm/ADT/iterator.h b/include/llvm/ADT/iterator.h index 6470e09db86cc..28dcdf9613ef2 100644 --- a/include/llvm/ADT/iterator.h +++ b/include/llvm/ADT/iterator.h @@ -10,6 +10,7 @@ #ifndef LLVM_ADT_ITERATOR_H #define LLVM_ADT_ITERATOR_H +#include "llvm/ADT/iterator_range.h" #include <cstddef> #include <iterator> #include <type_traits> @@ -91,6 +92,8 @@ protected: public: DerivedT operator+(DifferenceTypeT n) const { + static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value, + "Must pass the derived type to this template!"); static_assert( IsRandomAccess, "The '+' operator is only defined for random access iterators."); @@ -114,6 +117,8 @@ public: } DerivedT &operator++() { + static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value, + "Must pass the derived type to this template!"); return static_cast<DerivedT *>(this)->operator+=(1); } DerivedT operator++(int) { @@ -160,9 +165,15 @@ public: return !static_cast<const DerivedT *>(this)->operator<(RHS); } + PointerT operator->() { return &static_cast<DerivedT *>(this)->operator*(); } PointerT operator->() const { return &static_cast<const DerivedT *>(this)->operator*(); } + ReferenceProxy operator[](DifferenceTypeT n) { + static_assert(IsRandomAccess, + "Subscripting is only defined for random access iterators."); + return ReferenceProxy(static_cast<DerivedT *>(this)->operator+(n)); + } ReferenceProxy operator[](DifferenceTypeT n) const { static_assert(IsRandomAccess, "Subscripting is only defined for random access iterators."); @@ -202,7 +213,10 @@ protected: iterator_adaptor_base() = default; - explicit iterator_adaptor_base(WrappedIteratorT u) : I(std::move(u)) {} + explicit iterator_adaptor_base(WrappedIteratorT u) : I(std::move(u)) { + static_assert(std::is_base_of<iterator_adaptor_base, DerivedT>::value, + "Must pass the derived type to this template!"); + } const WrappedIteratorT &wrapped() const { return I; } @@ -283,6 +297,15 @@ struct pointee_iterator T &operator*() const { return **this->I; } }; +template <typename RangeT, typename WrappedIteratorT = + decltype(std::begin(std::declval<RangeT>()))> +iterator_range<pointee_iterator<WrappedIteratorT>> +make_pointee_range(RangeT &&Range) { + using PointeeIteratorT = pointee_iterator<WrappedIteratorT>; + return make_range(PointeeIteratorT(std::begin(std::forward<RangeT>(Range))), + PointeeIteratorT(std::end(std::forward<RangeT>(Range)))); +} + template <typename WrappedIteratorT, typename T = decltype(&*std::declval<WrappedIteratorT>())> class pointer_iterator @@ -300,6 +323,15 @@ public: const T &operator*() const { return Ptr = &*this->I; } }; +template <typename RangeT, typename WrappedIteratorT = + decltype(std::begin(std::declval<RangeT>()))> +iterator_range<pointer_iterator<WrappedIteratorT>> +make_pointer_range(RangeT &&Range) { + using PointerIteratorT = pointer_iterator<WrappedIteratorT>; + return make_range(PointerIteratorT(std::begin(std::forward<RangeT>(Range))), + PointerIteratorT(std::end(std::forward<RangeT>(Range)))); +} + } // end namespace llvm #endif // LLVM_ADT_ITERATOR_H |