LCOV - code coverage report
Current view: top level - include/llvm/IR - ConstantRange.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 14 14 100.0 %
Date: 2017-09-14 15:23:50 Functions: 6 6 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- ConstantRange.h - Represent a range ----------------------*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // Represent a range of possible values that may occur when the program is run
      11             : // for an integral value.  This keeps track of a lower and upper bound for the
      12             : // constant, which MAY wrap around the end of the numeric range.  To do this, it
      13             : // keeps track of a [lower, upper) bound, which specifies an interval just like
      14             : // STL iterators.  When used with boolean values, the following are important
      15             : // ranges: :
      16             : //
      17             : //  [F, F) = {}     = Empty set
      18             : //  [T, F) = {T}
      19             : //  [F, T) = {F}
      20             : //  [T, T) = {F, T} = Full set
      21             : //
      22             : // The other integral ranges use min/max values for special range values. For
      23             : // example, for 8-bit types, it uses:
      24             : // [0, 0)     = {}       = Empty set
      25             : // [255, 255) = {0..255} = Full Set
      26             : //
      27             : // Note that ConstantRange can be used to represent either signed or
      28             : // unsigned ranges.
      29             : //
      30             : //===----------------------------------------------------------------------===//
      31             : 
      32             : #ifndef LLVM_IR_CONSTANTRANGE_H
      33             : #define LLVM_IR_CONSTANTRANGE_H
      34             : 
      35             : #include "llvm/ADT/APInt.h"
      36             : #include "llvm/IR/InstrTypes.h"
      37             : #include "llvm/IR/Instruction.h"
      38             : #include "llvm/Support/Compiler.h"
      39             : #include <cstdint>
      40             : 
      41             : namespace llvm {
      42             : 
      43             : class MDNode;
      44             : class raw_ostream;
      45             : 
      46             : /// This class represents a range of values.
      47   136849635 : class LLVM_NODISCARD ConstantRange {
      48             :   APInt Lower, Upper;
      49             : 
      50             : public:
      51             :   /// Initialize a full (the default) or empty set for the specified bit width.
      52             :   explicit ConstantRange(uint32_t BitWidth, bool isFullSet = true);
      53             : 
      54             :   /// Initialize a range to hold the single specified value.
      55             :   ConstantRange(APInt Value);
      56             : 
      57             :   /// @brief Initialize a range of values explicitly. This will assert out if
      58             :   /// Lower==Upper and Lower != Min or Max value for its type. It will also
      59             :   /// assert out if the two APInt's are not the same bit width.
      60             :   ConstantRange(APInt Lower, APInt Upper);
      61             : 
      62             :   /// Produce the smallest range such that all values that may satisfy the given
      63             :   /// predicate with any value contained within Other is contained in the
      64             :   /// returned range.  Formally, this returns a superset of
      65             :   /// 'union over all y in Other . { x : icmp op x y is true }'.  If the exact
      66             :   /// answer is not representable as a ConstantRange, the return value will be a
      67             :   /// proper superset of the above.
      68             :   ///
      69             :   /// Example: Pred = ult and Other = i8 [2, 5) returns Result = [0, 4)
      70             :   static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred,
      71             :                                              const ConstantRange &Other);
      72             : 
      73             :   /// Produce the largest range such that all values in the returned range
      74             :   /// satisfy the given predicate with all values contained within Other.
      75             :   /// Formally, this returns a subset of
      76             :   /// 'intersection over all y in Other . { x : icmp op x y is true }'.  If the
      77             :   /// exact answer is not representable as a ConstantRange, the return value
      78             :   /// will be a proper subset of the above.
      79             :   ///
      80             :   /// Example: Pred = ult and Other = i8 [2, 5) returns [0, 2)
      81             :   static ConstantRange makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
      82             :                                                 const ConstantRange &Other);
      83             : 
      84             :   /// Produce the exact range such that all values in the returned range satisfy
      85             :   /// the given predicate with any value contained within Other. Formally, this
      86             :   /// returns the exact answer when the superset of 'union over all y in Other
      87             :   /// is exactly same as the subset of intersection over all y in Other.
      88             :   /// { x : icmp op x y is true}'.
      89             :   ///
      90             :   /// Example: Pred = ult and Other = i8 3 returns [0, 3)
      91             :   static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred,
      92             :                                            const APInt &Other);
      93             : 
      94             :   /// Return the largest range containing all X such that "X BinOpC Y" is
      95             :   /// guaranteed not to wrap (overflow) for all Y in Other.
      96             :   ///
      97             :   /// NB! The returned set does *not* contain **all** possible values of X for
      98             :   /// which "X BinOpC Y" does not wrap -- some viable values of X may be
      99             :   /// missing, so you cannot use this to constrain X's range.  E.g. in the last
     100             :   /// example, "(-2) + 1" is both nsw and nuw (so the "X" could be -2), but (-2)
     101             :   /// is not in the set returned.
     102             :   ///
     103             :   /// Examples:
     104             :   ///  typedef OverflowingBinaryOperator OBO;
     105             :   ///  #define MGNR makeGuaranteedNoWrapRegion
     106             :   ///  MGNR(Add, [i8 1, 2), OBO::NoSignedWrap) == [-128, 127)
     107             :   ///  MGNR(Add, [i8 1, 2), OBO::NoUnsignedWrap) == [0, -1)
     108             :   ///  MGNR(Add, [i8 0, 1), OBO::NoUnsignedWrap) == Full Set
     109             :   ///  MGNR(Add, [i8 1, 2), OBO::NoUnsignedWrap | OBO::NoSignedWrap)
     110             :   ///    == [0,INT_MAX)
     111             :   ///  MGNR(Add, [i8 -1, 6), OBO::NoSignedWrap) == [INT_MIN+1, INT_MAX-4)
     112             :   static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
     113             :                                                   const ConstantRange &Other,
     114             :                                                   unsigned NoWrapKind);
     115             : 
     116             :   /// Set up \p Pred and \p RHS such that
     117             :   /// ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.  Return true if
     118             :   /// successful.
     119             :   bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const;
     120             : 
     121             :   /// Return the lower value for this range.
     122     1766228 :   const APInt &getLower() const { return Lower; }
     123             : 
     124             :   /// Return the upper value for this range.
     125     3083950 :   const APInt &getUpper() const { return Upper; }
     126             : 
     127             :   /// Get the bit width of this ConstantRange.
     128     6015324 :   uint32_t getBitWidth() const { return Lower.getBitWidth(); }
     129             : 
     130             :   /// Return true if this set contains all of the elements possible
     131             :   /// for this data-type.
     132             :   bool isFullSet() const;
     133             : 
     134             :   /// Return true if this set contains no members.
     135             :   bool isEmptySet() const;
     136             : 
     137             :   /// Return true if this set wraps around the top of the range.
     138             :   /// For example: [100, 8).
     139             :   bool isWrappedSet() const;
     140             : 
     141             :   /// Return true if this set wraps around the INT_MIN of
     142             :   /// its bitwidth. For example: i8 [120, 140).
     143             :   bool isSignWrappedSet() const;
     144             : 
     145             :   /// Return true if the specified value is in the set.
     146             :   bool contains(const APInt &Val) const;
     147             : 
     148             :   /// Return true if the other range is a subset of this one.
     149             :   bool contains(const ConstantRange &CR) const;
     150             : 
     151             :   /// If this set contains a single element, return it, otherwise return null.
     152     2590915 :   const APInt *getSingleElement() const {
     153    15545490 :     if (Upper == Lower + 1)
     154     2391343 :       return &Lower;
     155             :     return nullptr;
     156             :   }
     157             : 
     158             :   /// If this set contains all but a single element, return it, otherwise return
     159             :   /// null.
     160       94343 :   const APInt *getSingleMissingElement() const {
     161      566058 :     if (Lower == Upper + 1)
     162       18572 :       return &Upper;
     163             :     return nullptr;
     164             :   }
     165             : 
     166             :   /// Return true if this set contains exactly one member.
     167      192980 :   bool isSingleElement() const { return getSingleElement() != nullptr; }
     168             : 
     169             :   /// Return the number of elements in this set.
     170             :   APInt getSetSize() const;
     171             : 
     172             :   /// Compare set size of this range with the range CR.
     173             :   bool isSizeStrictlySmallerThan(const ConstantRange &CR) const;
     174             : 
     175             :   // Compare set size of this range with Value.
     176             :   bool isSizeLargerThan(uint64_t MaxSize) const;
     177             : 
     178             :   /// Return the largest unsigned value contained in the ConstantRange.
     179             :   APInt getUnsignedMax() const;
     180             : 
     181             :   /// Return the smallest unsigned value contained in the ConstantRange.
     182             :   APInt getUnsignedMin() const;
     183             : 
     184             :   /// Return the largest signed value contained in the ConstantRange.
     185             :   APInt getSignedMax() const;
     186             : 
     187             :   /// Return the smallest signed value contained in the ConstantRange.
     188             :   APInt getSignedMin() const;
     189             : 
     190             :   /// Return true if this range is equal to another range.
     191         977 :   bool operator==(const ConstantRange &CR) const {
     192        2491 :     return Lower == CR.Lower && Upper == CR.Upper;
     193             :   }
     194             :   bool operator!=(const ConstantRange &CR) const {
     195         719 :     return !operator==(CR);
     196             :   }
     197             : 
     198             :   /// Subtract the specified constant from the endpoints of this constant range.
     199             :   ConstantRange subtract(const APInt &CI) const;
     200             : 
     201             :   /// Subtract the specified range from this range (aka relative complement of
     202             :   /// the sets).
     203             :   ConstantRange difference(const ConstantRange &CR) const;
     204             : 
     205             :   /// Return the range that results from the intersection of
     206             :   /// this range with another range.  The resultant range is guaranteed to
     207             :   /// include all elements contained in both input ranges, and to have the
     208             :   /// smallest possible set size that does so.  Because there may be two
     209             :   /// intersections with the same set size, A.intersectWith(B) might not
     210             :   /// be equal to B.intersectWith(A).
     211             :   ConstantRange intersectWith(const ConstantRange &CR) const;
     212             : 
     213             :   /// Return the range that results from the union of this range
     214             :   /// with another range.  The resultant range is guaranteed to include the
     215             :   /// elements of both sets, but may contain more.  For example, [3, 9) union
     216             :   /// [12,15) is [3, 15), which includes 9, 10, and 11, which were not included
     217             :   /// in either set before.
     218             :   ConstantRange unionWith(const ConstantRange &CR) const;
     219             : 
     220             :   /// Return a new range representing the possible values resulting
     221             :   /// from an application of the specified cast operator to this range. \p
     222             :   /// BitWidth is the target bitwidth of the cast.  For casts which don't
     223             :   /// change bitwidth, it must be the same as the source bitwidth.  For casts
     224             :   /// which do change bitwidth, the bitwidth must be consistent with the
     225             :   /// requested cast and source bitwidth.
     226             :   ConstantRange castOp(Instruction::CastOps CastOp,
     227             :                        uint32_t BitWidth) const;
     228             : 
     229             :   /// Return a new range in the specified integer type, which must
     230             :   /// be strictly larger than the current type.  The returned range will
     231             :   /// correspond to the possible range of values if the source range had been
     232             :   /// zero extended to BitWidth.
     233             :   ConstantRange zeroExtend(uint32_t BitWidth) const;
     234             : 
     235             :   /// Return a new range in the specified integer type, which must
     236             :   /// be strictly larger than the current type.  The returned range will
     237             :   /// correspond to the possible range of values if the source range had been
     238             :   /// sign extended to BitWidth.
     239             :   ConstantRange signExtend(uint32_t BitWidth) const;
     240             : 
     241             :   /// Return a new range in the specified integer type, which must be
     242             :   /// strictly smaller than the current type.  The returned range will
     243             :   /// correspond to the possible range of values if the source range had been
     244             :   /// truncated to the specified type.
     245             :   ConstantRange truncate(uint32_t BitWidth) const;
     246             : 
     247             :   /// Make this range have the bit width given by \p BitWidth. The
     248             :   /// value is zero extended, truncated, or left alone to make it that width.
     249             :   ConstantRange zextOrTrunc(uint32_t BitWidth) const;
     250             : 
     251             :   /// Make this range have the bit width given by \p BitWidth. The
     252             :   /// value is sign extended, truncated, or left alone to make it that width.
     253             :   ConstantRange sextOrTrunc(uint32_t BitWidth) const;
     254             : 
     255             :   /// Return a new range representing the possible values resulting
     256             :   /// from an application of the specified binary operator to an left hand side
     257             :   /// of this range and a right hand side of \p Other.
     258             :   ConstantRange binaryOp(Instruction::BinaryOps BinOp,
     259             :                          const ConstantRange &Other) const;
     260             : 
     261             :   /// Return a new range representing the possible values resulting
     262             :   /// from an addition of a value in this range and a value in \p Other.
     263             :   ConstantRange add(const ConstantRange &Other) const;
     264             : 
     265             :   /// Return a new range representing the possible values resulting from a
     266             :   /// known NSW addition of a value in this range and \p Other constant.
     267             :   ConstantRange addWithNoSignedWrap(const APInt &Other) const;
     268             : 
     269             :   /// Return a new range representing the possible values resulting
     270             :   /// from a subtraction of a value in this range and a value in \p Other.
     271             :   ConstantRange sub(const ConstantRange &Other) const;
     272             : 
     273             :   /// Return a new range representing the possible values resulting
     274             :   /// from a multiplication of a value in this range and a value in \p Other,
     275             :   /// treating both this and \p Other as unsigned ranges.
     276             :   ConstantRange multiply(const ConstantRange &Other) const;
     277             : 
     278             :   /// Return a new range representing the possible values resulting
     279             :   /// from a signed maximum of a value in this range and a value in \p Other.
     280             :   ConstantRange smax(const ConstantRange &Other) const;
     281             : 
     282             :   /// Return a new range representing the possible values resulting
     283             :   /// from an unsigned maximum of a value in this range and a value in \p Other.
     284             :   ConstantRange umax(const ConstantRange &Other) const;
     285             : 
     286             :   /// Return a new range representing the possible values resulting
     287             :   /// from a signed minimum of a value in this range and a value in \p Other.
     288             :   ConstantRange smin(const ConstantRange &Other) const;
     289             : 
     290             :   /// Return a new range representing the possible values resulting
     291             :   /// from an unsigned minimum of a value in this range and a value in \p Other.
     292             :   ConstantRange umin(const ConstantRange &Other) const;
     293             : 
     294             :   /// Return a new range representing the possible values resulting
     295             :   /// from an unsigned division of a value in this range and a value in
     296             :   /// \p Other.
     297             :   ConstantRange udiv(const ConstantRange &Other) const;
     298             : 
     299             :   /// Return a new range representing the possible values resulting
     300             :   /// from a binary-and of a value in this range by a value in \p Other.
     301             :   ConstantRange binaryAnd(const ConstantRange &Other) const;
     302             : 
     303             :   /// Return a new range representing the possible values resulting
     304             :   /// from a binary-or of a value in this range by a value in \p Other.
     305             :   ConstantRange binaryOr(const ConstantRange &Other) const;
     306             : 
     307             :   /// Return a new range representing the possible values resulting
     308             :   /// from a left shift of a value in this range by a value in \p Other.
     309             :   /// TODO: This isn't fully implemented yet.
     310             :   ConstantRange shl(const ConstantRange &Other) const;
     311             : 
     312             :   /// Return a new range representing the possible values resulting from a
     313             :   /// logical right shift of a value in this range and a value in \p Other.
     314             :   ConstantRange lshr(const ConstantRange &Other) const;
     315             : 
     316             :   /// Return a new range that is the logical not of the current set.
     317             :   ConstantRange inverse() const;
     318             : 
     319             :   /// Print out the bounds to a stream.
     320             :   void print(raw_ostream &OS) const;
     321             : 
     322             :   /// Allow printing from a debugger easily.
     323             :   void dump() const;
     324             : };
     325             : 
     326             : inline raw_ostream &operator<<(raw_ostream &OS, const ConstantRange &CR) {
     327             :   CR.print(OS);
     328             :   return OS;
     329             : }
     330             : 
     331             : /// Parse out a conservative ConstantRange from !range metadata.
     332             : ///
     333             : /// E.g. if RangeMD is !{i32 0, i32 10, i32 15, i32 20} then return [0, 20).
     334             : ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD);
     335             : 
     336             : } // end namespace llvm
     337             : 
     338             : #endif // LLVM_IR_CONSTANTRANGE_H

Generated by: LCOV version 1.13