LLVM  mainline
ConstantRange.h
Go to the documentation of this file.
00001 //===- ConstantRange.h - Represent a range ----------------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // Represent a range of possible values that may occur when the program is run
00011 // for an integral value.  This keeps track of a lower and upper bound for the
00012 // constant, which MAY wrap around the end of the numeric range.  To do this, it
00013 // keeps track of a [lower, upper) bound, which specifies an interval just like
00014 // STL iterators.  When used with boolean values, the following are important
00015 // ranges: :
00016 //
00017 //  [F, F) = {}     = Empty set
00018 //  [T, F) = {T}
00019 //  [F, T) = {F}
00020 //  [T, T) = {F, T} = Full set
00021 //
00022 // The other integral ranges use min/max values for special range values. For
00023 // example, for 8-bit types, it uses:
00024 // [0, 0)     = {}       = Empty set
00025 // [255, 255) = {0..255} = Full Set
00026 //
00027 // Note that ConstantRange can be used to represent either signed or
00028 // unsigned ranges.
00029 //
00030 //===----------------------------------------------------------------------===//
00031 
00032 #ifndef LLVM_IR_CONSTANTRANGE_H
00033 #define LLVM_IR_CONSTANTRANGE_H
00034 
00035 #include "llvm/ADT/APInt.h"
00036 #include "llvm/IR/InstrTypes.h"
00037 #include "llvm/Support/DataTypes.h"
00038 
00039 namespace llvm {
00040 
00041 /// This class represents a range of values.
00042 ///
00043 class ConstantRange {
00044   APInt Lower, Upper;
00045 
00046   // If we have move semantics, pass APInts by value and move them into place.
00047   typedef APInt APIntMoveTy;
00048 
00049 public:
00050   /// Initialize a full (the default) or empty set for the specified bit width.
00051   ///
00052   explicit ConstantRange(uint32_t BitWidth, bool isFullSet = true);
00053 
00054   /// Initialize a range to hold the single specified value.
00055   ///
00056   ConstantRange(APIntMoveTy Value);
00057 
00058   /// @brief Initialize a range of values explicitly. This will assert out if
00059   /// Lower==Upper and Lower != Min or Max value for its type. It will also
00060   /// assert out if the two APInt's are not the same bit width.
00061   ConstantRange(APIntMoveTy Lower, APIntMoveTy Upper);
00062 
00063   /// Produce the smallest range such that all values that may satisfy the given
00064   /// predicate with any value contained within Other is contained in the
00065   /// returned range.  Formally, this returns a superset of
00066   /// 'union over all y in Other . { x : icmp op x y is true }'.  If the exact
00067   /// answer is not representable as a ConstantRange, the return value will be a
00068   /// proper superset of the above.
00069   ///
00070   /// Example: Pred = ult and Other = i8 [2, 5) returns Result = [0, 4)
00071   static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred,
00072                                              const ConstantRange &Other);
00073 
00074   /// Produce the largest range such that all values in the returned range
00075   /// satisfy the given predicate with all values contained within Other.
00076   /// Formally, this returns a subset of
00077   /// 'intersection over all y in Other . { x : icmp op x y is true }'.  If the
00078   /// exact answer is not representable as a ConstantRange, the return value
00079   /// will be a proper subset of the above.
00080   ///
00081   /// Example: Pred = ult and Other = i8 [2, 5) returns [0, 2)
00082   static ConstantRange makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
00083                                                 const ConstantRange &Other);
00084 
00085   /// Return the lower value for this range.
00086   ///
00087   const APInt &getLower() const { return Lower; }
00088 
00089   /// Return the upper value for this range.
00090   ///
00091   const APInt &getUpper() const { return Upper; }
00092 
00093   /// Get the bit width of this ConstantRange.
00094   ///
00095   uint32_t getBitWidth() const { return Lower.getBitWidth(); }
00096 
00097   /// Return true if this set contains all of the elements possible
00098   /// for this data-type.
00099   ///
00100   bool isFullSet() const;
00101 
00102   /// Return true if this set contains no members.
00103   ///
00104   bool isEmptySet() const;
00105 
00106   /// Return true if this set wraps around the top of the range.
00107   /// For example: [100, 8).
00108   ///
00109   bool isWrappedSet() const;
00110 
00111   /// Return true if this set wraps around the INT_MIN of
00112   /// its bitwidth. For example: i8 [120, 140).
00113   ///
00114   bool isSignWrappedSet() const;
00115 
00116   /// Return true if the specified value is in the set.
00117   ///
00118   bool contains(const APInt &Val) const;
00119 
00120   /// Return true if the other range is a subset of this one.
00121   ///
00122   bool contains(const ConstantRange &CR) const;
00123 
00124   /// If this set contains a single element, return it, otherwise return null.
00125   ///
00126   const APInt *getSingleElement() const {
00127     if (Upper == Lower + 1)
00128       return &Lower;
00129     return nullptr;
00130   }
00131 
00132   /// Return true if this set contains exactly one member.
00133   ///
00134   bool isSingleElement() const { return getSingleElement() != nullptr; }
00135 
00136   /// Return the number of elements in this set.
00137   ///
00138   APInt getSetSize() const;
00139 
00140   /// Return the largest unsigned value contained in the ConstantRange.
00141   ///
00142   APInt getUnsignedMax() const;
00143 
00144   /// Return the smallest unsigned value contained in the ConstantRange.
00145   ///
00146   APInt getUnsignedMin() const;
00147 
00148   /// Return the largest signed value contained in the ConstantRange.
00149   ///
00150   APInt getSignedMax() const;
00151 
00152   /// Return the smallest signed value contained in the ConstantRange.
00153   ///
00154   APInt getSignedMin() const;
00155 
00156   /// Return true if this range is equal to another range.
00157   ///
00158   bool operator==(const ConstantRange &CR) const {
00159     return Lower == CR.Lower && Upper == CR.Upper;
00160   }
00161   bool operator!=(const ConstantRange &CR) const {
00162     return !operator==(CR);
00163   }
00164 
00165   /// Subtract the specified constant from the endpoints of this constant range.
00166   ConstantRange subtract(const APInt &CI) const;
00167 
00168   /// \brief Subtract the specified range from this range (aka relative
00169   /// complement of the sets).
00170   ConstantRange difference(const ConstantRange &CR) const;
00171 
00172   /// Return the range that results from the intersection of
00173   /// this range with another range.  The resultant range is guaranteed to
00174   /// include all elements contained in both input ranges, and to have the
00175   /// smallest possible set size that does so.  Because there may be two
00176   /// intersections with the same set size, A.intersectWith(B) might not
00177   /// be equal to B.intersectWith(A).
00178   ///
00179   ConstantRange intersectWith(const ConstantRange &CR) const;
00180 
00181   /// Return the range that results from the union of this range
00182   /// with another range.  The resultant range is guaranteed to include the
00183   /// elements of both sets, but may contain more.  For example, [3, 9) union
00184   /// [12,15) is [3, 15), which includes 9, 10, and 11, which were not included
00185   /// in either set before.
00186   ///
00187   ConstantRange unionWith(const ConstantRange &CR) const;
00188 
00189   /// Return a new range in the specified integer type, which must
00190   /// be strictly larger than the current type.  The returned range will
00191   /// correspond to the possible range of values if the source range had been
00192   /// zero extended to BitWidth.
00193   ConstantRange zeroExtend(uint32_t BitWidth) const;
00194 
00195   /// Return a new range in the specified integer type, which must
00196   /// be strictly larger than the current type.  The returned range will
00197   /// correspond to the possible range of values if the source range had been
00198   /// sign extended to BitWidth.
00199   ConstantRange signExtend(uint32_t BitWidth) const;
00200 
00201   /// Return a new range in the specified integer type, which must be
00202   /// strictly smaller than the current type.  The returned range will
00203   /// correspond to the possible range of values if the source range had been
00204   /// truncated to the specified type.
00205   ConstantRange truncate(uint32_t BitWidth) const;
00206 
00207   /// Make this range have the bit width given by \p BitWidth. The
00208   /// value is zero extended, truncated, or left alone to make it that width.
00209   ConstantRange zextOrTrunc(uint32_t BitWidth) const;
00210   
00211   /// Make this range have the bit width given by \p BitWidth. The
00212   /// value is sign extended, truncated, or left alone to make it that width.
00213   ConstantRange sextOrTrunc(uint32_t BitWidth) const;
00214 
00215   /// Return a new range representing the possible values resulting
00216   /// from an addition of a value in this range and a value in \p Other.
00217   ConstantRange add(const ConstantRange &Other) const;
00218 
00219   /// Return a new range representing the possible values resulting
00220   /// from a subtraction of a value in this range and a value in \p Other.
00221   ConstantRange sub(const ConstantRange &Other) const;
00222 
00223   /// Return a new range representing the possible values resulting
00224   /// from a multiplication of a value in this range and a value in \p Other,
00225   /// treating both this and \p Other as unsigned ranges.
00226   ConstantRange multiply(const ConstantRange &Other) const;
00227 
00228   /// Return a new range representing the possible values resulting
00229   /// from a signed maximum of a value in this range and a value in \p Other.
00230   ConstantRange smax(const ConstantRange &Other) const;
00231 
00232   /// Return a new range representing the possible values resulting
00233   /// from an unsigned maximum of a value in this range and a value in \p Other.
00234   ConstantRange umax(const ConstantRange &Other) const;
00235 
00236   /// Return a new range representing the possible values resulting
00237   /// from an unsigned division of a value in this range and a value in
00238   /// \p Other.
00239   ConstantRange udiv(const ConstantRange &Other) const;
00240 
00241   /// Return a new range representing the possible values resulting
00242   /// from a binary-and of a value in this range by a value in \p Other.
00243   ConstantRange binaryAnd(const ConstantRange &Other) const;
00244 
00245   /// Return a new range representing the possible values resulting
00246   /// from a binary-or of a value in this range by a value in \p Other.
00247   ConstantRange binaryOr(const ConstantRange &Other) const;
00248 
00249   /// Return a new range representing the possible values resulting
00250   /// from a left shift of a value in this range by a value in \p Other.
00251   /// TODO: This isn't fully implemented yet.
00252   ConstantRange shl(const ConstantRange &Other) const;
00253 
00254   /// Return a new range representing the possible values resulting from a
00255   /// logical right shift of a value in this range and a value in \p Other.
00256   ConstantRange lshr(const ConstantRange &Other) const;
00257 
00258   /// Return a new range that is the logical not of the current set.
00259   ///
00260   ConstantRange inverse() const;
00261   
00262   /// Print out the bounds to a stream.
00263   ///
00264   void print(raw_ostream &OS) const;
00265 
00266   /// Allow printing from a debugger easily.
00267   ///
00268   void dump() const;
00269 };
00270 
00271 inline raw_ostream &operator<<(raw_ostream &OS, const ConstantRange &CR) {
00272   CR.print(OS);
00273   return OS;
00274 }
00275 
00276 } // End llvm namespace
00277 
00278 #endif