LCOV - code coverage report
Current view: top level - include/llvm/IR - ConstantRange.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 14 15 93.3 %
Date: 2018-10-20 13:21:21 Functions: 3 3 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      888316 : 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             :   /// 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
     100             :   /// fourth example, "(-2) + 1" is both nsw and nuw (so the "X" could be -2),
     101             :   /// but (-2) 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             :   ///  MGNR(Sub, [i8 1, 2), OBO::NoSignedWrap) == [-127, 128)
     113             :   ///  MGNR(Sub, [i8 1, 2), OBO::NoUnsignedWrap) == [1, 0)
     114             :   ///  MGNR(Sub, [i8 1, 2), OBO::NoUnsignedWrap | OBO::NoSignedWrap)
     115             :   ///    == [1,INT_MAX)
     116             :   static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
     117             :                                                   const ConstantRange &Other,
     118             :                                                   unsigned NoWrapKind);
     119             : 
     120             :   /// Set up \p Pred and \p RHS such that
     121             :   /// ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.  Return true if
     122             :   /// successful.
     123             :   bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const;
     124             : 
     125             :   /// Return the lower value for this range.
     126     3528233 :   const APInt &getLower() const { return Lower; }
     127             : 
     128             :   /// Return the upper value for this range.
     129     6010380 :   const APInt &getUpper() const { return Upper; }
     130             : 
     131             :   /// Get the bit width of this ConstantRange.
     132    13888823 :   uint32_t getBitWidth() const { return Lower.getBitWidth(); }
     133             : 
     134             :   /// Return true if this set contains all of the elements possible
     135             :   /// for this data-type.
     136             :   bool isFullSet() const;
     137             : 
     138             :   /// Return true if this set contains no members.
     139             :   bool isEmptySet() const;
     140             : 
     141             :   /// Return true if this set wraps around the top of the range.
     142             :   /// For example: [100, 8).
     143             :   bool isWrappedSet() const;
     144             : 
     145             :   /// Return true if this set wraps around the INT_MIN of
     146             :   /// its bitwidth. For example: i8 [120, 140).
     147             :   bool isSignWrappedSet() const;
     148             : 
     149             :   /// Return true if the specified value is in the set.
     150             :   bool contains(const APInt &Val) const;
     151             : 
     152             :   /// Return true if the other range is a subset of this one.
     153             :   bool contains(const ConstantRange &CR) const;
     154             : 
     155             :   /// If this set contains a single element, return it, otherwise return null.
     156     3922489 :   const APInt *getSingleElement() const {
     157    11767467 :     if (Upper == Lower + 1)
     158     3617019 :       return &Lower;
     159             :     return nullptr;
     160             :   }
     161             : 
     162             :   /// If this set contains all but a single element, return it, otherwise return
     163             :   /// null.
     164      141925 :   const APInt *getSingleMissingElement() const {
     165      425775 :     if (Lower == Upper + 1)
     166       26584 :       return &Upper;
     167             :     return nullptr;
     168             :   }
     169             : 
     170             :   /// Return true if this set contains exactly one member.
     171      274620 :   bool isSingleElement() const { return getSingleElement() != nullptr; }
     172             : 
     173             :   /// Return the number of elements in this set.
     174             :   APInt getSetSize() const;
     175             : 
     176             :   /// Compare set size of this range with the range CR.
     177             :   bool isSizeStrictlySmallerThan(const ConstantRange &CR) const;
     178             : 
     179             :   // Compare set size of this range with Value.
     180             :   bool isSizeLargerThan(uint64_t MaxSize) const;
     181             : 
     182             :   /// Return the largest unsigned value contained in the ConstantRange.
     183             :   APInt getUnsignedMax() const;
     184             : 
     185             :   /// Return the smallest unsigned value contained in the ConstantRange.
     186             :   APInt getUnsignedMin() const;
     187             : 
     188             :   /// Return the largest signed value contained in the ConstantRange.
     189             :   APInt getSignedMax() const;
     190             : 
     191             :   /// Return the smallest signed value contained in the ConstantRange.
     192             :   APInt getSignedMin() const;
     193             : 
     194             :   /// Return true if this range is equal to another range.
     195       54380 :   bool operator==(const ConstantRange &CR) const {
     196      159515 :     return Lower == CR.Lower && Upper == CR.Upper;
     197             :   }
     198             :   bool operator!=(const ConstantRange &CR) const {
     199        1838 :     return !operator==(CR);
     200             :   }
     201             : 
     202             :   /// Subtract the specified constant from the endpoints of this constant range.
     203             :   ConstantRange subtract(const APInt &CI) const;
     204             : 
     205             :   /// Subtract the specified range from this range (aka relative complement of
     206             :   /// the sets).
     207             :   ConstantRange difference(const ConstantRange &CR) const;
     208             : 
     209             :   /// Return the range that results from the intersection of
     210             :   /// this range with another range.  The resultant range is guaranteed to
     211             :   /// include all elements contained in both input ranges, and to have the
     212             :   /// smallest possible set size that does so.  Because there may be two
     213             :   /// intersections with the same set size, A.intersectWith(B) might not
     214             :   /// be equal to B.intersectWith(A).
     215             :   ConstantRange intersectWith(const ConstantRange &CR) const;
     216             : 
     217             :   /// Return the range that results from the union of this range
     218             :   /// with another range.  The resultant range is guaranteed to include the
     219             :   /// elements of both sets, but may contain more.  For example, [3, 9) union
     220             :   /// [12,15) is [3, 15), which includes 9, 10, and 11, which were not included
     221             :   /// in either set before.
     222             :   ConstantRange unionWith(const ConstantRange &CR) const;
     223             : 
     224             :   /// Return a new range representing the possible values resulting
     225             :   /// from an application of the specified cast operator to this range. \p
     226             :   /// BitWidth is the target bitwidth of the cast.  For casts which don't
     227             :   /// change bitwidth, it must be the same as the source bitwidth.  For casts
     228             :   /// which do change bitwidth, the bitwidth must be consistent with the
     229             :   /// requested cast and source bitwidth.
     230             :   ConstantRange castOp(Instruction::CastOps CastOp,
     231             :                        uint32_t BitWidth) const;
     232             : 
     233             :   /// Return a new range in the specified integer type, which must
     234             :   /// be strictly larger than the current type.  The returned range will
     235             :   /// correspond to the possible range of values if the source range had been
     236             :   /// zero extended to BitWidth.
     237             :   ConstantRange zeroExtend(uint32_t BitWidth) const;
     238             : 
     239             :   /// Return a new range in the specified integer type, which must
     240             :   /// be strictly larger than the current type.  The returned range will
     241             :   /// correspond to the possible range of values if the source range had been
     242             :   /// sign extended to BitWidth.
     243             :   ConstantRange signExtend(uint32_t BitWidth) const;
     244             : 
     245             :   /// Return a new range in the specified integer type, which must be
     246             :   /// strictly smaller than the current type.  The returned range will
     247             :   /// correspond to the possible range of values if the source range had been
     248             :   /// truncated to the specified type.
     249             :   ConstantRange truncate(uint32_t BitWidth) const;
     250             : 
     251             :   /// Make this range have the bit width given by \p BitWidth. The
     252             :   /// value is zero extended, truncated, or left alone to make it that width.
     253             :   ConstantRange zextOrTrunc(uint32_t BitWidth) const;
     254             : 
     255             :   /// Make this range have the bit width given by \p BitWidth. The
     256             :   /// value is sign extended, truncated, or left alone to make it that width.
     257             :   ConstantRange sextOrTrunc(uint32_t BitWidth) const;
     258             : 
     259             :   /// Return a new range representing the possible values resulting
     260             :   /// from an application of the specified binary operator to an left hand side
     261             :   /// of this range and a right hand side of \p Other.
     262             :   ConstantRange binaryOp(Instruction::BinaryOps BinOp,
     263             :                          const ConstantRange &Other) const;
     264             : 
     265             :   /// Return a new range representing the possible values resulting
     266             :   /// from an addition of a value in this range and a value in \p Other.
     267             :   ConstantRange add(const ConstantRange &Other) const;
     268             : 
     269             :   /// Return a new range representing the possible values resulting from a
     270             :   /// known NSW addition of a value in this range and \p Other constant.
     271             :   ConstantRange addWithNoSignedWrap(const APInt &Other) const;
     272             : 
     273             :   /// Return a new range representing the possible values resulting
     274             :   /// from a subtraction of a value in this range and a value in \p Other.
     275             :   ConstantRange sub(const ConstantRange &Other) const;
     276             : 
     277             :   /// Return a new range representing the possible values resulting
     278             :   /// from a multiplication of a value in this range and a value in \p Other,
     279             :   /// treating both this and \p Other as unsigned ranges.
     280             :   ConstantRange multiply(const ConstantRange &Other) const;
     281             : 
     282             :   /// Return a new range representing the possible values resulting
     283             :   /// from a signed maximum of a value in this range and a value in \p Other.
     284             :   ConstantRange smax(const ConstantRange &Other) const;
     285             : 
     286             :   /// Return a new range representing the possible values resulting
     287             :   /// from an unsigned maximum of a value in this range and a value in \p Other.
     288             :   ConstantRange umax(const ConstantRange &Other) const;
     289             : 
     290             :   /// Return a new range representing the possible values resulting
     291             :   /// from a signed minimum of a value in this range and a value in \p Other.
     292             :   ConstantRange smin(const ConstantRange &Other) const;
     293             : 
     294             :   /// Return a new range representing the possible values resulting
     295             :   /// from an unsigned minimum of a value in this range and a value in \p Other.
     296             :   ConstantRange umin(const ConstantRange &Other) const;
     297             : 
     298             :   /// Return a new range representing the possible values resulting
     299             :   /// from an unsigned division of a value in this range and a value in
     300             :   /// \p Other.
     301             :   ConstantRange udiv(const ConstantRange &Other) const;
     302             : 
     303             :   /// Return a new range representing the possible values resulting
     304             :   /// from a binary-and of a value in this range by a value in \p Other.
     305             :   ConstantRange binaryAnd(const ConstantRange &Other) const;
     306             : 
     307             :   /// Return a new range representing the possible values resulting
     308             :   /// from a binary-or of a value in this range by a value in \p Other.
     309             :   ConstantRange binaryOr(const ConstantRange &Other) const;
     310             : 
     311             :   /// Return a new range representing the possible values resulting
     312             :   /// from a left shift of a value in this range by a value in \p Other.
     313             :   /// TODO: This isn't fully implemented yet.
     314             :   ConstantRange shl(const ConstantRange &Other) const;
     315             : 
     316             :   /// Return a new range representing the possible values resulting from a
     317             :   /// logical right shift of a value in this range and a value in \p Other.
     318             :   ConstantRange lshr(const ConstantRange &Other) const;
     319             : 
     320             :   /// Return a new range representing the possible values resulting from a
     321             :   /// arithmetic right shift of a value in this range and a value in \p Other.
     322             :   ConstantRange ashr(const ConstantRange &Other) const;
     323             : 
     324             :   /// Return a new range that is the logical not of the current set.
     325             :   ConstantRange inverse() const;
     326             : 
     327             :   /// Print out the bounds to a stream.
     328             :   void print(raw_ostream &OS) const;
     329             : 
     330             :   /// Allow printing from a debugger easily.
     331             :   void dump() const;
     332             : };
     333             : 
     334             : inline raw_ostream &operator<<(raw_ostream &OS, const ConstantRange &CR) {
     335           0 :   CR.print(OS);
     336             :   return OS;
     337             : }
     338             : 
     339             : /// Parse out a conservative ConstantRange from !range metadata.
     340             : ///
     341             : /// E.g. if RangeMD is !{i32 0, i32 10, i32 15, i32 20} then return [0, 20).
     342             : ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD);
     343             : 
     344             : } // end namespace llvm
     345             : 
     346             : #endif // LLVM_IR_CONSTANTRANGE_H

Generated by: LCOV version 1.13