← Back to branch summary

~pali/+junk/llvm-toolchain-3.7

« back to all changes in this revision

Viewing changes to include/llvm/IR/ConstantRange.h

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2015-07-15 17:51:08 UTC
  • Revision ID: package-import@ubuntu.com-20150715175108-l8mynwovkx4zx697
Tags: upstream-3.7~+rc2
Import upstream version 3.7~+rc2

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/llvm/IR/ConstantRange.h
 
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
  ///
 
87
  const APInt &getLower() const { return Lower; }
 
88
 
 
89
  /// Return the upper value for this range.
 
90
  ///
 
91
  const APInt &getUpper() const { return Upper; }
 
92
 
 
93
  /// Get the bit width of this ConstantRange.
 
94
  ///
 
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
  ///
 
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
  ///
 
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