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/Support/DataTypes.h"
38 
39 namespace llvm {
40 
41 /// This class represents a range of values.
42 ///
43 class ConstantRange {
44   APInt Lower, Upper;
45 
46   // If we have move semantics, pass APInts by value and move them into place.
47   typedef APInt APIntMoveTy;
48 
49 public:
50   /// Initialize a full (the default) or empty set for the specified bit width.
51   ///
52   explicit ConstantRange(uint32_t BitWidth, bool isFullSet = true);
53 
54   /// Initialize a range to hold the single specified value.
55   ///
56   ConstantRange(APIntMoveTy Value);
57 
58   /// @brief Initialize a range of values explicitly. This will assert out if
59   /// Lower==Upper and Lower != Min or Max value for its type. It will also
60   /// assert out if the two APInt's are not the same bit width.
61   ConstantRange(APIntMoveTy Lower, APIntMoveTy Upper);
62 
63   /// Produce the smallest range such that all values that may satisfy the given
64   /// predicate with any value contained within Other is contained in the
65   /// returned range.  Formally, this returns a superset of
66   /// 'union over all y in Other . { x : icmp op x y is true }'.  If the exact
67   /// answer is not representable as a ConstantRange, the return value will be a
68   /// proper superset of the above.
69   ///
70   /// Example: Pred = ult and Other = i8 [2, 5) returns Result = [0, 4)
71   static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred,
72                                              const ConstantRange &Other);
73 
74   /// Produce the largest range such that all values in the returned range
75   /// satisfy the given predicate with all values contained within Other.
76   /// Formally, this returns a subset of
77   /// 'intersection over all y in Other . { x : icmp op x y is true }'.  If the
78   /// exact answer is not representable as a ConstantRange, the return value
79   /// will be a proper subset of the above.
80   ///
81   /// Example: Pred = ult and Other = i8 [2, 5) returns [0, 2)
82   static ConstantRange makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
83                                                 const ConstantRange &Other);
84 
85   /// Return the lower value for this range.
86   ///
getLower()87   const APInt &getLower() const { return Lower; }
88 
89   /// Return the upper value for this range.
90   ///
getUpper()91   const APInt &getUpper() const { return Upper; }
92 
93   /// Get the bit width of this ConstantRange.
94   ///
getBitWidth()95   uint32_t getBitWidth() const { return Lower.getBitWidth(); }
96 
97   /// Return true if this set contains all of the elements possible
98   /// for this data-type.
99   ///
100   bool isFullSet() const;
101 
102   /// Return true if this set contains no members.
103   ///
104   bool isEmptySet() const;
105 
106   /// Return true if this set wraps around the top of the range.
107   /// For example: [100, 8).
108   ///
109   bool isWrappedSet() const;
110 
111   /// Return true if this set wraps around the INT_MIN of
112   /// its bitwidth. For example: i8 [120, 140).
113   ///
114   bool isSignWrappedSet() const;
115 
116   /// Return true if the specified value is in the set.
117   ///
118   bool contains(const APInt &Val) const;
119 
120   /// Return true if the other range is a subset of this one.
121   ///
122   bool contains(const ConstantRange &CR) const;
123 
124   /// If this set contains a single element, return it, otherwise return null.
125   ///
getSingleElement()126   const APInt *getSingleElement() const {
127     if (Upper == Lower + 1)
128       return &Lower;
129     return nullptr;
130   }
131 
132   /// Return true if this set contains exactly one member.
133   ///
isSingleElement()134   bool isSingleElement() const { return getSingleElement() != nullptr; }
135 
136   /// Return the number of elements in this set.
137   ///
138   APInt getSetSize() const;
139 
140   /// Return the largest unsigned value contained in the ConstantRange.
141   ///
142   APInt getUnsignedMax() const;
143 
144   /// Return the smallest unsigned value contained in the ConstantRange.
145   ///
146   APInt getUnsignedMin() const;
147 
148   /// Return the largest signed value contained in the ConstantRange.
149   ///
150   APInt getSignedMax() const;
151 
152   /// Return the smallest signed value contained in the ConstantRange.
153   ///
154   APInt getSignedMin() const;
155 
156   /// Return true if this range is equal to another range.
157   ///
158   bool operator==(const ConstantRange &CR) const {
159     return Lower == CR.Lower && Upper == CR.Upper;
160   }
161   bool operator!=(const ConstantRange &CR) const {
162     return !operator==(CR);
163   }
164 
165   /// Subtract the specified constant from the endpoints of this constant range.
166   ConstantRange subtract(const APInt &CI) const;
167 
168   /// \brief Subtract the specified range from this range (aka relative
169   /// complement of the sets).
170   ConstantRange difference(const ConstantRange &CR) const;
171 
172   /// Return the range that results from the intersection of
173   /// this range with another range.  The resultant range is guaranteed to
174   /// include all elements contained in both input ranges, and to have the
175   /// smallest possible set size that does so.  Because there may be two
176   /// intersections with the same set size, A.intersectWith(B) might not
177   /// be equal to B.intersectWith(A).
178   ///
179   ConstantRange intersectWith(const ConstantRange &CR) const;
180 
181   /// Return the range that results from the union of this range
182   /// with another range.  The resultant range is guaranteed to include the
183   /// elements of both sets, but may contain more.  For example, [3, 9) union
184   /// [12,15) is [3, 15), which includes 9, 10, and 11, which were not included
185   /// in either set before.
186   ///
187   ConstantRange unionWith(const ConstantRange &CR) const;
188 
189   /// Return a new range in the specified integer type, which must
190   /// be strictly larger than the current type.  The returned range will
191   /// correspond to the possible range of values if the source range had been
192   /// zero extended to BitWidth.
193   ConstantRange zeroExtend(uint32_t BitWidth) const;
194 
195   /// Return a new range in the specified integer type, which must
196   /// be strictly larger than the current type.  The returned range will
197   /// correspond to the possible range of values if the source range had been
198   /// sign extended to BitWidth.
199   ConstantRange signExtend(uint32_t BitWidth) const;
200 
201   /// Return a new range in the specified integer type, which must be
202   /// strictly smaller than the current type.  The returned range will
203   /// correspond to the possible range of values if the source range had been
204   /// truncated to the specified type.
205   ConstantRange truncate(uint32_t BitWidth) const;
206 
207   /// Make this range have the bit width given by \p BitWidth. The
208   /// value is zero extended, truncated, or left alone to make it that width.
209   ConstantRange zextOrTrunc(uint32_t BitWidth) const;
210 
211   /// Make this range have the bit width given by \p BitWidth. The
212   /// value is sign extended, truncated, or left alone to make it that width.
213   ConstantRange sextOrTrunc(uint32_t BitWidth) const;
214 
215   /// Return a new range representing the possible values resulting
216   /// from an addition of a value in this range and a value in \p Other.
217   ConstantRange add(const ConstantRange &Other) const;
218 
219   /// Return a new range representing the possible values resulting
220   /// from a subtraction of a value in this range and a value in \p Other.
221   ConstantRange sub(const ConstantRange &Other) const;
222 
223   /// Return a new range representing the possible values resulting
224   /// from a multiplication of a value in this range and a value in \p Other,
225   /// treating both this and \p Other as unsigned ranges.
226   ConstantRange multiply(const ConstantRange &Other) const;
227 
228   /// Return a new range representing the possible values resulting
229   /// from a signed maximum of a value in this range and a value in \p Other.
230   ConstantRange smax(const ConstantRange &Other) const;
231 
232   /// Return a new range representing the possible values resulting
233   /// from an unsigned maximum of a value in this range and a value in \p Other.
234   ConstantRange umax(const ConstantRange &Other) const;
235 
236   /// Return a new range representing the possible values resulting
237   /// from an unsigned division of a value in this range and a value in
238   /// \p Other.
239   ConstantRange udiv(const ConstantRange &Other) const;
240 
241   /// Return a new range representing the possible values resulting
242   /// from a binary-and of a value in this range by a value in \p Other.
243   ConstantRange binaryAnd(const ConstantRange &Other) const;
244 
245   /// Return a new range representing the possible values resulting
246   /// from a binary-or of a value in this range by a value in \p Other.
247   ConstantRange binaryOr(const ConstantRange &Other) const;
248 
249   /// Return a new range representing the possible values resulting
250   /// from a left shift of a value in this range by a value in \p Other.
251   /// TODO: This isn't fully implemented yet.
252   ConstantRange shl(const ConstantRange &Other) const;
253 
254   /// Return a new range representing the possible values resulting from a
255   /// logical right shift of a value in this range and a value in \p Other.
256   ConstantRange lshr(const ConstantRange &Other) const;
257 
258   /// Return a new range that is the logical not of the current set.
259   ///
260   ConstantRange inverse() const;
261 
262   /// Print out the bounds to a stream.
263   ///
264   void print(raw_ostream &OS) const;
265 
266   /// Allow printing from a debugger easily.
267   ///
268   void dump() const;
269 };
270 
271 inline raw_ostream &operator<<(raw_ostream &OS, const ConstantRange &CR) {
272   CR.print(OS);
273   return OS;
274 }
275 
276 } // End llvm namespace
277 
278 #endif
279