summaryrefslogtreecommitdiff
path: root/include/llvm/ADT
diff options
context:
space:
mode:
Diffstat (limited to 'include/llvm/ADT')
-rw-r--r--include/llvm/ADT/APFloat.h370
-rw-r--r--include/llvm/ADT/APInt.h668
-rw-r--r--include/llvm/ADT/APSInt.h3
-rw-r--r--include/llvm/ADT/ArrayRef.h12
-rw-r--r--include/llvm/ADT/BitVector.h43
-rw-r--r--include/llvm/ADT/BreadthFirstIterator.h164
-rw-r--r--include/llvm/ADT/DenseMap.h13
-rw-r--r--include/llvm/ADT/DenseMapInfo.h18
-rw-r--r--include/llvm/ADT/DenseSet.h27
-rw-r--r--include/llvm/ADT/DepthFirstIterator.h2
-rw-r--r--include/llvm/ADT/GraphTraits.h29
-rw-r--r--include/llvm/ADT/None.h5
-rw-r--r--include/llvm/ADT/PointerUnion.h8
-rw-r--r--include/llvm/ADT/PostOrderIterator.h4
-rw-r--r--include/llvm/ADT/STLExtras.h236
-rw-r--r--include/llvm/ADT/ScopedHashTable.h4
-rw-r--r--include/llvm/ADT/SetVector.h8
-rw-r--r--include/llvm/ADT/SmallBitVector.h29
-rw-r--r--include/llvm/ADT/SmallPtrSet.h57
-rw-r--r--include/llvm/ADT/SparseBitVector.h19
-rw-r--r--include/llvm/ADT/StringExtras.h7
-rw-r--r--include/llvm/ADT/StringMap.h110
-rw-r--r--include/llvm/ADT/StringRef.h10
-rw-r--r--include/llvm/ADT/Triple.h23
-rw-r--r--include/llvm/ADT/iterator.h34
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