LLVM  7.0.0svn
ValueLattice.h
Go to the documentation of this file.
1 //===- ValueLattice.h - Value constraint analysis ---------------*- 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 #ifndef LLVM_ANALYSIS_VALUELATTICE_H
11 #define LLVM_ANALYSIS_VALUELATTICE_H
12 
13 #include "llvm/IR/ConstantRange.h"
14 #include "llvm/IR/Constants.h"
15 //
16 //===----------------------------------------------------------------------===//
17 // ValueLatticeElement
18 //===----------------------------------------------------------------------===//
19 
20 /// This class represents lattice values for constants.
21 ///
22 /// FIXME: This is basically just for bringup, this can be made a lot more rich
23 /// in the future.
24 ///
25 
26 namespace llvm {
28  enum ValueLatticeElementTy {
29  /// This Value has no known value yet. As a result, this implies the
30  /// producing instruction is dead. Caution: We use this as the starting
31  /// state in our local meet rules. In this usage, it's taken to mean
32  /// "nothing known yet".
33  undefined,
34 
35  /// This Value has a specific constant value. (For constant integers,
36  /// constantrange is used instead. Integer typed constantexprs can appear
37  /// as constant.)
38  constant,
39 
40  /// This Value is known to not have the specified value. (For constant
41  /// integers, constantrange is used instead. As above, integer typed
42  /// constantexprs can appear here.)
43  notconstant,
44 
45  /// The Value falls within this range. (Used only for integer typed values.)
46  constantrange,
47 
48  /// We can not precisely model the dynamic values this value might take.
49  overdefined
50  };
51 
52  ValueLatticeElementTy Tag;
53 
54  /// The union either stores a pointer to a constant or a constant range,
55  /// associated to the lattice element. We have to ensure that Range is
56  /// initialized or destroyed when changing state to or from constantrange.
57  union {
60  };
61 
62 public:
63  // Const and Range are initialized on-demand.
64  ValueLatticeElement() : Tag(undefined) {}
65 
66  /// Custom destructor to ensure Range is properly destroyed, when the object
67  /// is deallocated.
69  switch (Tag) {
70  case overdefined:
71  case undefined:
72  case constant:
73  case notconstant:
74  break;
75  case constantrange:
76  Range.~ConstantRange();
77  break;
78  };
79  }
80 
81  /// Custom copy constructor, to ensure Range gets initialized when
82  /// copying a constant range lattice element.
83  ValueLatticeElement(const ValueLatticeElement &Other) : Tag(undefined) {
84  *this = Other;
85  }
86 
87  /// Custom assignment operator, to ensure Range gets initialized when
88  /// assigning a constant range lattice element.
90  // If we change the state of this from constant range to non constant range,
91  // destroy Range.
92  if (isConstantRange() && !Other.isConstantRange())
93  Range.~ConstantRange();
94 
95  // If we change the state of this from a valid ConstVal to another a state
96  // without a valid ConstVal, zero the pointer.
97  if ((isConstant() || isNotConstant()) && !Other.isConstant() &&
98  !Other.isNotConstant())
99  ConstVal = nullptr;
100 
101  switch (Other.Tag) {
102  case constantrange:
103  if (!isConstantRange())
104  new (&Range) ConstantRange(Other.Range);
105  else
106  Range = Other.Range;
107  break;
108  case constant:
109  case notconstant:
110  ConstVal = Other.ConstVal;
111  break;
112  case overdefined:
113  case undefined:
114  break;
115  }
116  Tag = Other.Tag;
117  return *this;
118  }
119 
122  if (!isa<UndefValue>(C))
123  Res.markConstant(C);
124  return Res;
125  }
128  if (!isa<UndefValue>(C))
129  Res.markNotConstant(C);
130  return Res;
131  }
134  Res.markConstantRange(std::move(CR));
135  return Res;
136  }
139  Res.markOverdefined();
140  return Res;
141  }
142 
143  bool isUndefined() const { return Tag == undefined; }
144  bool isConstant() const { return Tag == constant; }
145  bool isNotConstant() const { return Tag == notconstant; }
146  bool isConstantRange() const { return Tag == constantrange; }
147  bool isOverdefined() const { return Tag == overdefined; }
148 
150  assert(isConstant() && "Cannot get the constant of a non-constant!");
151  return ConstVal;
152  }
153 
155  assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
156  return ConstVal;
157  }
158 
161  "Cannot get the constant-range of a non-constant-range!");
162  return Range;
163  }
164 
166  if (isConstant() && isa<ConstantInt>(getConstant())) {
167  return cast<ConstantInt>(getConstant())->getValue();
168  } else if (isConstantRange() && getConstantRange().isSingleElement()) {
170  }
171  return None;
172  }
173 
174 private:
175  void markOverdefined() {
176  if (isOverdefined())
177  return;
178  if (isConstant() || isNotConstant())
179  ConstVal = nullptr;
180  if (isConstantRange())
181  Range.~ConstantRange();
182  Tag = overdefined;
183  }
184 
185  void markConstant(Constant *V) {
186  assert(V && "Marking constant with NULL");
187  if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
188  markConstantRange(ConstantRange(CI->getValue()));
189  return;
190  }
191  if (isa<UndefValue>(V))
192  return;
193 
194  assert((!isConstant() || getConstant() == V) &&
195  "Marking constant with different value");
196  assert(isUndefined());
197  Tag = constant;
198  ConstVal = V;
199  }
200 
201  void markNotConstant(Constant *V) {
202  assert(V && "Marking constant with NULL");
203  if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
204  markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()));
205  return;
206  }
207  if (isa<UndefValue>(V))
208  return;
209 
210  assert((!isConstant() || getConstant() != V) &&
211  "Marking constant !constant with same value");
212  assert((!isNotConstant() || getNotConstant() == V) &&
213  "Marking !constant with different value");
214  assert(isUndefined() || isConstant());
215  Tag = notconstant;
216  ConstVal = V;
217  }
218 
219  void markConstantRange(ConstantRange NewR) {
220  if (isConstantRange()) {
221  if (NewR.isEmptySet())
222  markOverdefined();
223  else {
224  Range = std::move(NewR);
225  }
226  return;
227  }
228 
229  assert(isUndefined());
230  if (NewR.isEmptySet())
231  markOverdefined();
232  else {
233  Tag = constantrange;
234  new (&Range) ConstantRange(std::move(NewR));
235  }
236  }
237 
238 public:
239  /// Updates this object to approximate both this object and RHS. Returns
240  /// true if this object has been changed.
241  bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
242  if (RHS.isUndefined() || isOverdefined())
243  return false;
244  if (RHS.isOverdefined()) {
245  markOverdefined();
246  return true;
247  }
248 
249  if (isUndefined()) {
250  *this = RHS;
251  return !RHS.isUndefined();
252  }
253 
254  if (isConstant()) {
255  if (RHS.isConstant() && getConstant() == RHS.getConstant())
256  return false;
257  markOverdefined();
258  return true;
259  }
260 
261  if (isNotConstant()) {
262  if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant())
263  return false;
264  markOverdefined();
265  return true;
266  }
267 
268  assert(isConstantRange() && "New ValueLattice type?");
269  if (!RHS.isConstantRange()) {
270  // We can get here if we've encountered a constantexpr of integer type
271  // and merge it with a constantrange.
272  markOverdefined();
273  return true;
274  }
276  if (NewR.isFullSet())
277  markOverdefined();
278  else
279  markConstantRange(std::move(NewR));
280  return true;
281  }
282 
284  assert(isConstant() && isa<ConstantInt>(getConstant()) &&
285  "No integer constant");
286  return cast<ConstantInt>(getConstant());
287  }
288 
290  const ValueLatticeElement &Other) const {
291  // TODO: share with LVI getPredicateResult.
292 
293  if (isUndefined() || Other.isUndefined())
294  return true;
295 
296  if (isConstant() && Other.isConstant() && Pred == CmpInst::FCMP_OEQ)
297  return getConstant() == Other.getConstant();
298 
299  // Integer constants are represented as ConstantRanges with single
300  // elements.
301  if (!isConstantRange() || !Other.isConstantRange())
302  return false;
303 
304  const auto &CR = getConstantRange();
305  const auto &OtherCR = Other.getConstantRange();
306  return ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR);
307  }
308 };
309 
311 
312 } // end namespace llvm
313 #endif
uint64_t CallInst * C
ConstantInt * getConstantInt() const
Definition: ValueLattice.h:283
Optional< APInt > asConstantInteger() const
Definition: ValueLattice.h:165
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
ConstantRange unionWith(const ConstantRange &CR) const
Return the range that results from the union of this range with another range.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
ValueLatticeElement(const ValueLatticeElement &Other)
Custom copy constructor, to ensure Range gets initialized when copying a constant range lattice eleme...
Definition: ValueLattice.h:83
bool satisfiesPredicate(CmpInst::Predicate Pred, const ValueLatticeElement &Other) const
Definition: ValueLattice.h:289
static ValueLatticeElement getNot(Constant *C)
Definition: ValueLattice.h:126
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
~ValueLatticeElement()
Custom destructor to ensure Range is properly destroyed, when the object is deallocated.
Definition: ValueLattice.h:68
const ConstantRange & getConstantRange() const
Definition: ValueLattice.h:159
static ConstantRange makeSatisfyingICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)
Produce the largest range such that all values in the returned range satisfy the given predicate with...
This is an important base class in LLVM.
Definition: Constant.h:42
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:853
bool isConstantRange() const
Definition: ValueLattice.h:146
bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type. ...
static ValueLatticeElement getRange(ConstantRange CR)
Definition: ValueLattice.h:132
Constant * getConstant() const
Definition: ValueLattice.h:149
Constant * getNotConstant() const
Definition: ValueLattice.h:154
bool isEmptySet() const
Return true if this set contains no members.
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
This class represents a range of values.
Definition: ConstantRange.h:47
bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL)
Updates this object to approximate both this object and RHS.
Definition: ValueLattice.h:241
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2018
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
ValueLatticeElement & operator=(const ValueLatticeElement &Other)
Custom assignment operator, to ensure Range gets initialized when assigning a constant range lattice ...
Definition: ValueLattice.h:89
0 0 0 1 True if ordered and equal
Definition: InstrTypes.h:856
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
static ValueLatticeElement getOverdefined()
Definition: ValueLattice.h:137