LLVM  10.0.0svn
ValueLattice.h
Go to the documentation of this file.
1 //===- ValueLattice.h - Value constraint analysis ---------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #ifndef LLVM_ANALYSIS_VALUELATTICE_H
10 #define LLVM_ANALYSIS_VALUELATTICE_H
11 
12 #include "llvm/IR/ConstantRange.h"
13 #include "llvm/IR/Constants.h"
14 //
15 //===----------------------------------------------------------------------===//
16 // ValueLatticeElement
17 //===----------------------------------------------------------------------===//
18 
19 /// This class represents lattice values for constants.
20 ///
21 /// FIXME: This is basically just for bringup, this can be made a lot more rich
22 /// in the future.
23 ///
24 
25 namespace llvm {
27  enum ValueLatticeElementTy {
28  /// This Value has no known value yet. As a result, this implies the
29  /// producing instruction is dead. Caution: We use this as the starting
30  /// state in our local meet rules. In this usage, it's taken to mean
31  /// "nothing known yet".
32  undefined,
33 
34  /// This Value has a specific constant value. (For constant integers,
35  /// constantrange is used instead. Integer typed constantexprs can appear
36  /// as constant.)
37  constant,
38 
39  /// This Value is known to not have the specified value. (For constant
40  /// integers, constantrange is used instead. As above, integer typed
41  /// constantexprs can appear here.)
42  notconstant,
43 
44  /// The Value falls within this range. (Used only for integer typed values.)
45  constantrange,
46 
47  /// We can not precisely model the dynamic values this value might take.
48  overdefined
49  };
50 
51  ValueLatticeElementTy Tag;
52 
53  /// The union either stores a pointer to a constant or a constant range,
54  /// associated to the lattice element. We have to ensure that Range is
55  /// initialized or destroyed when changing state to or from constantrange.
56  union {
59  };
60 
61 public:
62  // Const and Range are initialized on-demand.
63  ValueLatticeElement() : Tag(undefined) {}
64 
65  /// Custom destructor to ensure Range is properly destroyed, when the object
66  /// is deallocated.
68  switch (Tag) {
69  case overdefined:
70  case undefined:
71  case constant:
72  case notconstant:
73  break;
74  case constantrange:
75  Range.~ConstantRange();
76  break;
77  };
78  }
79 
80  /// Custom copy constructor, to ensure Range gets initialized when
81  /// copying a constant range lattice element.
82  ValueLatticeElement(const ValueLatticeElement &Other) : Tag(undefined) {
83  *this = Other;
84  }
85 
86  /// Custom assignment operator, to ensure Range gets initialized when
87  /// assigning a constant range lattice element.
89  // If we change the state of this from constant range to non constant range,
90  // destroy Range.
91  if (isConstantRange() && !Other.isConstantRange())
92  Range.~ConstantRange();
93 
94  // If we change the state of this from a valid ConstVal to another a state
95  // without a valid ConstVal, zero the pointer.
96  if ((isConstant() || isNotConstant()) && !Other.isConstant() &&
97  !Other.isNotConstant())
98  ConstVal = nullptr;
99 
100  switch (Other.Tag) {
101  case constantrange:
102  if (!isConstantRange())
103  new (&Range) ConstantRange(Other.Range);
104  else
105  Range = Other.Range;
106  break;
107  case constant:
108  case notconstant:
109  ConstVal = Other.ConstVal;
110  break;
111  case overdefined:
112  case undefined:
113  break;
114  }
115  Tag = Other.Tag;
116  return *this;
117  }
118 
121  if (!isa<UndefValue>(C))
122  Res.markConstant(C);
123  return Res;
124  }
127  if (!isa<UndefValue>(C))
128  Res.markNotConstant(C);
129  return Res;
130  }
133  Res.markConstantRange(std::move(CR));
134  return Res;
135  }
138  Res.markOverdefined();
139  return Res;
140  }
141 
142  bool isUndefined() const { return Tag == undefined; }
143  bool isConstant() const { return Tag == constant; }
144  bool isNotConstant() const { return Tag == notconstant; }
145  bool isConstantRange() const { return Tag == constantrange; }
146  bool isOverdefined() const { return Tag == overdefined; }
147 
149  assert(isConstant() && "Cannot get the constant of a non-constant!");
150  return ConstVal;
151  }
152 
154  assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
155  return ConstVal;
156  }
157 
160  "Cannot get the constant-range of a non-constant-range!");
161  return Range;
162  }
163 
165  if (isConstant() && isa<ConstantInt>(getConstant())) {
166  return cast<ConstantInt>(getConstant())->getValue();
167  } else if (isConstantRange() && getConstantRange().isSingleElement()) {
169  }
170  return None;
171  }
172 
173 private:
174  void markOverdefined() {
175  if (isOverdefined())
176  return;
177  if (isConstant() || isNotConstant())
178  ConstVal = nullptr;
179  if (isConstantRange())
180  Range.~ConstantRange();
181  Tag = overdefined;
182  }
183 
184  void markConstant(Constant *V) {
185  assert(V && "Marking constant with NULL");
186  if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
187  markConstantRange(ConstantRange(CI->getValue()));
188  return;
189  }
190  if (isa<UndefValue>(V))
191  return;
192 
193  assert((!isConstant() || getConstant() == V) &&
194  "Marking constant with different value");
195  assert(isUndefined());
196  Tag = constant;
197  ConstVal = V;
198  }
199 
200  void markNotConstant(Constant *V) {
201  assert(V && "Marking constant with NULL");
202  if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
203  markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()));
204  return;
205  }
206  if (isa<UndefValue>(V))
207  return;
208 
209  assert((!isConstant() || getConstant() != V) &&
210  "Marking constant !constant with same value");
211  assert((!isNotConstant() || getNotConstant() == V) &&
212  "Marking !constant with different value");
213  assert(isUndefined() || isConstant());
214  Tag = notconstant;
215  ConstVal = V;
216  }
217 
218  void markConstantRange(ConstantRange NewR) {
219  if (isConstantRange()) {
220  if (NewR.isEmptySet())
221  markOverdefined();
222  else {
223  Range = std::move(NewR);
224  }
225  return;
226  }
227 
228  assert(isUndefined());
229  if (NewR.isEmptySet())
230  markOverdefined();
231  else {
232  Tag = constantrange;
233  new (&Range) ConstantRange(std::move(NewR));
234  }
235  }
236 
237 public:
238  /// Updates this object to approximate both this object and RHS. Returns
239  /// true if this object has been changed.
240  bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
241  if (RHS.isUndefined() || isOverdefined())
242  return false;
243  if (RHS.isOverdefined()) {
244  markOverdefined();
245  return true;
246  }
247 
248  if (isUndefined()) {
249  *this = RHS;
250  return !RHS.isUndefined();
251  }
252 
253  if (isConstant()) {
254  if (RHS.isConstant() && getConstant() == RHS.getConstant())
255  return false;
256  markOverdefined();
257  return true;
258  }
259 
260  if (isNotConstant()) {
261  if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant())
262  return false;
263  markOverdefined();
264  return true;
265  }
266 
267  assert(isConstantRange() && "New ValueLattice type?");
268  if (!RHS.isConstantRange()) {
269  // We can get here if we've encountered a constantexpr of integer type
270  // and merge it with a constantrange.
271  markOverdefined();
272  return true;
273  }
275  if (NewR.isFullSet())
276  markOverdefined();
277  else if (NewR == getConstantRange())
278  return false;
279  else
280  markConstantRange(std::move(NewR));
281  return true;
282  }
283 
285  assert(isConstant() && isa<ConstantInt>(getConstant()) &&
286  "No integer constant");
287  return cast<ConstantInt>(getConstant());
288  }
289 
290  /// Compares this symbolic value with Other using Pred and returns either
291  /// true, false or undef constants, or nullptr if the comparison cannot be
292  /// evaluated.
294  const ValueLatticeElement &Other) const {
295  if (isUndefined() || Other.isUndefined())
296  return UndefValue::get(Ty);
297 
298  if (isConstant() && Other.isConstant())
299  return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant());
300 
301  // Integer constants are represented as ConstantRanges with single
302  // elements.
303  if (!isConstantRange() || !Other.isConstantRange())
304  return nullptr;
305 
306  const auto &CR = getConstantRange();
307  const auto &OtherCR = Other.getConstantRange();
308  if (ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR))
309  return ConstantInt::getTrue(Ty);
311  CmpInst::getInversePredicate(Pred), OtherCR)
312  .contains(CR))
313  return ConstantInt::getFalse(Ty);
314 
315  return nullptr;
316  }
317 };
318 
320 
321 } // end namespace llvm
322 #endif
uint64_t CallInst * C
ConstantInt * getConstantInt() const
Definition: ValueLattice.h:284
Optional< APInt > asConstantInteger() const
Definition: ValueLattice.h:164
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:616
This class represents lattice values for constants.
Definition: AllocatorList.h:23
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
static Constant * getCompare(unsigned short pred, Constant *C1, Constant *C2, bool OnlyIfReduced=false)
Return an ICmp or FCmp comparison operator constant expression.
Definition: Constants.cpp:1968
ValueLatticeElement(const ValueLatticeElement &Other)
Custom copy constructor, to ensure Range gets initialized when copying a constant range lattice eleme...
Definition: ValueLattice.h:82
return AArch64::GPR64RegClass contains(Reg)
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:831
static ValueLatticeElement getNot(Constant *C)
Definition: ValueLattice.h:125
~ValueLatticeElement()
Custom destructor to ensure Range is properly destroyed, when the object is deallocated.
Definition: ValueLattice.h:67
const ConstantRange & getConstantRange() const
Definition: ValueLattice.h:158
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...
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
This is an important base class in LLVM.
Definition: Constant.h:41
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:732
bool isConstantRange() const
Definition: ValueLattice.h:145
bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type. ...
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1446
static ValueLatticeElement getRange(ConstantRange CR)
Definition: ValueLattice.h:131
Constant * getConstant() const
Definition: ValueLattice.h:148
Constant * getNotConstant() const
Definition: ValueLattice.h:153
bool isEmptySet() const
Return true if this set contains no members.
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
Constant * getCompare(CmpInst::Predicate Pred, Type *Ty, const ValueLatticeElement &Other) const
Compares this symbolic value with Other using Pred and returns either true, false or undef constants...
Definition: ValueLattice.h:293
This class represents a range of values.
Definition: ConstantRange.h:47
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:609
bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL)
Updates this object to approximate both this object and RHS.
Definition: ValueLattice.h:240
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2045
ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
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:88
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
static ValueLatticeElement getOverdefined()
Definition: ValueLattice.h:136