X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FSupport%2FConstantRange.h;h=90dd69fa478fe269b7ca3b8a005e3049d28c6826;hb=f5091b476c46333ecfcf095cd2e422e9748e9546;hp=cc3b23fd8ed1bc1acbc9852981fdbdb2825d2c8f;hpb=62fe9b59c1b50883b027393a183ac468d4371781;p=oota-llvm.git diff --git a/include/llvm/Support/ConstantRange.h b/include/llvm/Support/ConstantRange.h index cc3b23fd8ed..90dd69fa478 100644 --- a/include/llvm/Support/ConstantRange.h +++ b/include/llvm/Support/ConstantRange.h @@ -1,10 +1,10 @@ //===-- llvm/Support/ConstantRange.h - Represent a range --------*- C++ -*-===// -// +// // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// //===----------------------------------------------------------------------===// // // Represent a range of possible values that may occur when the program is run @@ -12,60 +12,77 @@ // constant, which MAY wrap around the end of the numeric range. To do this, it // keeps track of a [lower, upper) bound, which specifies an interval just like // STL iterators. When used with boolean values, the following are important -// ranges (other integral ranges use min/max values for special range values): +// ranges: : // // [F, F) = {} = Empty set // [T, F) = {T} // [F, T) = {F} // [T, T) = {F, T} = Full set // +// The other integral ranges use min/max values for special range values. For +// example, for 8-bit types, it uses: +// [0, 0) = {} = Empty set +// [255, 255) = {0..255} = Full Set +// +// Note that ConstantRange can be used to represent either signed or +// unsigned ranges. +// //===----------------------------------------------------------------------===// #ifndef LLVM_SUPPORT_CONSTANT_RANGE_H #define LLVM_SUPPORT_CONSTANT_RANGE_H -#include "Support/DataTypes.h" -#include +#include "llvm/ADT/APInt.h" +#include "llvm/Support/DataTypes.h" namespace llvm { -class Constant; -class ConstantIntegral; -class Type; +/// ConstantRange - This class represents an range of values. +/// class ConstantRange { - ConstantIntegral *Lower, *Upper; - public: - /// Initialize a full (the default) or empty set for the specified type. + APInt Lower, Upper; + +public: + /// Initialize a full (the default) or empty set for the specified bit width. /// - ConstantRange(const Type *Ty, bool isFullSet = true); - - /// Initialize a range of values explicitly... this will assert out if - /// Lower==Upper and Lower != Min or Max for its type, if the two constants - /// have different types, or if the constant are not integral values. + explicit ConstantRange(uint32_t BitWidth, bool isFullSet = true); + + /// Initialize a range to hold the single specified value. /// - ConstantRange(Constant *Lower, Constant *Upper); - - /// Initialize a set of values that all satisfy the condition with C. + ConstantRange(const APInt &Value); + + /// @brief Initialize a range of values explicitly. This will assert out if + /// Lower==Upper and Lower != Min or Max value for its type. It will also + /// assert out if the two APInt's are not the same bit width. + ConstantRange(const APInt &Lower, const APInt &Upper); + + /// makeICmpRegion - Produce the smallest range that contains all values that + /// might satisfy the comparison specified by Pred when compared to any value + /// contained within Other. /// - ConstantRange(unsigned SetCCOpcode, ConstantIntegral *C); + /// Solves for range X in 'for all x in X, there exists a y in Y such that + /// icmp op x, y is true'. Every value that might make the comparison true + /// is included in the resulting range. + static ConstantRange makeICmpRegion(unsigned Pred, + const ConstantRange &Other); /// getLower - Return the lower value for this range... /// - ConstantIntegral *getLower() const { return Lower; } + const APInt &getLower() const { return Lower; } /// getUpper - Return the upper value for this range... /// - ConstantIntegral *getUpper() const { return Upper; } + const APInt &getUpper() const { return Upper; } - /// getType - Return the LLVM data type of this range. + /// getBitWidth - get the bit width of this ConstantRange /// - const Type *getType() const; - + uint32_t getBitWidth() const { return Lower.getBitWidth(); } + /// isFullSet - Return true if this set contains all of the elements possible /// for this data-type /// bool isFullSet() const; - + /// isEmptySet - Return true if this set contains no members. /// bool isEmptySet() const; @@ -74,19 +91,56 @@ class ConstantRange { /// for example: [100, 8) /// bool isWrappedSet() const; - + + /// isSignWrappedSet - Return true if this set wraps around the INT_MIN of + /// its bitwidth, for example: i8 [120, 140). + /// + bool isSignWrappedSet() const; + + /// contains - Return true if the specified value is in the set. + /// + bool contains(const APInt &Val) const; + + /// contains - Return true if the other range is a subset of this one. + /// + bool contains(const ConstantRange &CR) const; + /// getSingleElement - If this set contains a single element, return it, /// otherwise return null. /// - ConstantIntegral *getSingleElement() const; - + const APInt *getSingleElement() const { + if (Upper == Lower + 1) + return &Lower; + return 0; + } + /// isSingleElement - Return true if this set contains exactly one member. /// bool isSingleElement() const { return getSingleElement() != 0; } /// getSetSize - Return the number of elements in this set. /// - uint64_t getSetSize() const; + APInt getSetSize() const; + + /// getUnsignedMax - Return the largest unsigned value contained in the + /// ConstantRange. + /// + APInt getUnsignedMax() const; + + /// getUnsignedMin - Return the smallest unsigned value contained in the + /// ConstantRange. + /// + APInt getUnsignedMin() const; + + /// getSignedMax - Return the largest signed value contained in the + /// ConstantRange. + /// + APInt getSignedMax() const; + + /// getSignedMin - Return the smallest signed value contained in the + /// ConstantRange. + /// + APInt getSignedMin() const; /// operator== - Return true if this range is equal to another range. /// @@ -97,32 +151,115 @@ class ConstantRange { return !operator==(CR); } - /// intersect - Return the range that results from the intersection of this - /// range with another range. The resultant range is pruned as much as - /// possible, but there may be cases where elements are included that are in - /// one of the sets but not the other. For example: [100, 8) intersect [3, - /// 120) yields [3, 120) + /// subtract - Subtract the specified constant from the endpoints of this + /// constant range. + ConstantRange subtract(const APInt &CI) const; + + /// \brief Subtract the specified range from this range (aka relative + /// complement of the sets). + ConstantRange difference(const ConstantRange &CR) const; + + /// intersectWith - Return the range that results from the intersection of + /// this range with another range. The resultant range is guaranteed to + /// include all elements contained in both input ranges, and to have the + /// smallest possible set size that does so. Because there may be two + /// intersections with the same set size, A.intersectWith(B) might not + /// be equal to B.intersectWith(A). /// ConstantRange intersectWith(const ConstantRange &CR) const; - /// union - Return the range that results from the union of this range with - /// another range. The resultant range is guaranteed to include the elements - /// of both sets, but may contain more. For example, [3, 9) union [12,15) is - /// [3, 15), which includes 9, 10, and 11, which were not included in either - /// set before. + /// unionWith - Return the range that results from the union of this range + /// with another range. The resultant range is guaranteed to include the + /// elements of both sets, but may contain more. For example, [3, 9) union + /// [12,15) is [3, 15), which includes 9, 10, and 11, which were not included + /// in either set before. /// ConstantRange unionWith(const ConstantRange &CR) const; + /// zeroExtend - Return a new range in the specified integer type, which must + /// be strictly larger than the current type. The returned range will + /// correspond to the possible range of values if the source range had been + /// zero extended to BitWidth. + ConstantRange zeroExtend(uint32_t BitWidth) const; + + /// signExtend - Return a new range in the specified integer type, which must + /// be strictly larger than the current type. The returned range will + /// correspond to the possible range of values if the source range had been + /// sign extended to BitWidth. + ConstantRange signExtend(uint32_t BitWidth) const; + + /// truncate - Return a new range in the specified integer type, which must be + /// strictly smaller than the current type. The returned range will + /// correspond to the possible range of values if the source range had been + /// truncated to the specified type. + ConstantRange truncate(uint32_t BitWidth) const; + + /// zextOrTrunc - make this range have the bit width given by \p BitWidth. The + /// value is zero extended, truncated, or left alone to make it that width. + ConstantRange zextOrTrunc(uint32_t BitWidth) const; + + /// sextOrTrunc - make this range have the bit width given by \p BitWidth. The + /// value is sign extended, truncated, or left alone to make it that width. + ConstantRange sextOrTrunc(uint32_t BitWidth) const; + + /// add - Return a new range representing the possible values resulting + /// from an addition of a value in this range and a value in \p Other. + ConstantRange add(const ConstantRange &Other) const; + + /// sub - Return a new range representing the possible values resulting + /// from a subtraction of a value in this range and a value in \p Other. + ConstantRange sub(const ConstantRange &Other) const; + + /// multiply - Return a new range representing the possible values resulting + /// from a multiplication of a value in this range and a value in \p Other. + /// TODO: This isn't fully implemented yet. + ConstantRange multiply(const ConstantRange &Other) const; + + /// smax - Return a new range representing the possible values resulting + /// from a signed maximum of a value in this range and a value in \p Other. + ConstantRange smax(const ConstantRange &Other) const; + + /// umax - Return a new range representing the possible values resulting + /// from an unsigned maximum of a value in this range and a value in \p Other. + ConstantRange umax(const ConstantRange &Other) const; + + /// udiv - Return a new range representing the possible values resulting + /// from an unsigned division of a value in this range and a value in + /// \p Other. + ConstantRange udiv(const ConstantRange &Other) const; + + /// binaryAnd - return a new range representing the possible values resulting + /// from a binary-and of a value in this range by a value in \p Other. + ConstantRange binaryAnd(const ConstantRange &Other) const; + + /// binaryOr - return a new range representing the possible values resulting + /// from a binary-or of a value in this range by a value in \p Other. + ConstantRange binaryOr(const ConstantRange &Other) const; + + /// shl - Return a new range representing the possible values resulting + /// from a left shift of a value in this range by a value in \p Other. + /// TODO: This isn't fully implemented yet. + ConstantRange shl(const ConstantRange &Other) const; + + /// lshr - Return a new range representing the possible values resulting + /// from a logical right shift of a value in this range and a value in + /// \p Other. + ConstantRange lshr(const ConstantRange &Other) const; + + /// inverse - Return a new range that is the logical not of the current set. + /// + ConstantRange inverse() const; + /// print - Print out the bounds to a stream... /// - void print(std::ostream &OS) const; + void print(raw_ostream &OS) const; /// dump - Allow printing from a debugger easily... /// void dump() const; }; -inline std::ostream &operator<<(std::ostream &OS, const ConstantRange &CR) { +inline raw_ostream &operator<<(raw_ostream &OS, const ConstantRange &CR) { CR.print(OS); return OS; }