LLVM  6.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  /// Val: This stores the current lattice value along with the Constant* for
53  /// the constant if this is a 'constant' or 'notconstant' value.
54  ValueLatticeElementTy Tag;
55  Constant *Val;
56  ConstantRange Range;
57 
58 public:
59  ValueLatticeElement() : Tag(undefined), Val(nullptr), Range(1, true) {}
60 
63  if (!isa<UndefValue>(C))
64  Res.markConstant(C);
65  return Res;
66  }
69  if (!isa<UndefValue>(C))
70  Res.markNotConstant(C);
71  return Res;
72  }
75  Res.markConstantRange(std::move(CR));
76  return Res;
77  }
80  Res.markOverdefined();
81  return Res;
82  }
83 
84  bool isUndefined() const { return Tag == undefined; }
85  bool isConstant() const { return Tag == constant; }
86  bool isNotConstant() const { return Tag == notconstant; }
87  bool isConstantRange() const { return Tag == constantrange; }
88  bool isOverdefined() const { return Tag == overdefined; }
89 
90  Constant *getConstant() const {
91  assert(isConstant() && "Cannot get the constant of a non-constant!");
92  return Val;
93  }
94 
96  assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
97  return Val;
98  }
99 
102  "Cannot get the constant-range of a non-constant-range!");
103  return Range;
104  }
105 
107  if (isConstant() && isa<ConstantInt>(Val)) {
108  return cast<ConstantInt>(Val)->getValue();
109  } else if (isConstantRange() && Range.isSingleElement()) {
110  return *Range.getSingleElement();
111  }
112  return None;
113  }
114 
115 private:
116  void markOverdefined() {
117  if (isOverdefined())
118  return;
119  Tag = overdefined;
120  }
121 
122  void markConstant(Constant *V) {
123  assert(V && "Marking constant with NULL");
124  if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
125  markConstantRange(ConstantRange(CI->getValue()));
126  return;
127  }
128  if (isa<UndefValue>(V))
129  return;
130 
131  assert((!isConstant() || getConstant() == V) &&
132  "Marking constant with different value");
133  assert(isUndefined());
134  Tag = constant;
135  Val = V;
136  }
137 
138  void markNotConstant(Constant *V) {
139  assert(V && "Marking constant with NULL");
140  if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
141  markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()));
142  return;
143  }
144  if (isa<UndefValue>(V))
145  return;
146 
147  assert((!isConstant() || getConstant() != V) &&
148  "Marking constant !constant with same value");
149  assert((!isNotConstant() || getNotConstant() == V) &&
150  "Marking !constant with different value");
151  assert(isUndefined() || isConstant());
152  Tag = notconstant;
153  Val = V;
154  }
155 
156  void markConstantRange(ConstantRange NewR) {
157  if (isConstantRange()) {
158  if (NewR.isEmptySet())
159  markOverdefined();
160  else {
161  Range = std::move(NewR);
162  }
163  return;
164  }
165 
166  assert(isUndefined());
167  if (NewR.isEmptySet())
168  markOverdefined();
169  else {
170  Tag = constantrange;
171  Range = std::move(NewR);
172  }
173  }
174 
175 public:
176  /// Updates this object to approximate both this object and RHS. Returns
177  /// true if this object has been changed.
178  bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
179  if (RHS.isUndefined() || isOverdefined())
180  return false;
181  if (RHS.isOverdefined()) {
182  markOverdefined();
183  return true;
184  }
185 
186  if (isUndefined()) {
187  *this = RHS;
188  return !RHS.isUndefined();
189  }
190 
191  if (isConstant()) {
192  if (RHS.isConstant() && Val == RHS.Val)
193  return false;
194  markOverdefined();
195  return true;
196  }
197 
198  if (isNotConstant()) {
199  if (RHS.isNotConstant() && Val == RHS.Val)
200  return false;
201  markOverdefined();
202  return true;
203  }
204 
205  assert(isConstantRange() && "New ValueLattice type?");
206  if (!RHS.isConstantRange()) {
207  // We can get here if we've encountered a constantexpr of integer type
208  // and merge it with a constantrange.
209  markOverdefined();
210  return true;
211  }
212  ConstantRange NewR = Range.unionWith(RHS.getConstantRange());
213  if (NewR.isFullSet())
214  markOverdefined();
215  else
216  markConstantRange(std::move(NewR));
217  return true;
218  }
219 
221  assert(isConstant() && isa<ConstantInt>(getConstant()) &&
222  "No integer constant");
223  return cast<ConstantInt>(getConstant());
224  }
225 
227  const ValueLatticeElement &Other) const {
228  // TODO: share with LVI getPredicateResult.
229 
230  if (isUndefined() || Other.isUndefined())
231  return true;
232 
233  if (isConstant() && Other.isConstant() && Pred == CmpInst::FCMP_OEQ)
234  return getConstant() == Other.getConstant();
235 
236  // Integer constants are represented as ConstantRanges with single
237  // elements.
238  if (!isConstantRange() || !Other.isConstantRange())
239  return false;
240 
241  const auto &CR = getConstantRange();
242  const auto &OtherCR = Other.getConstantRange();
243  return ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR);
244  }
245 };
246 
248 
249 } // end namespace llvm
250 #endif
uint64_t CallInst * C
ConstantInt * getConstantInt() const
Definition: ValueLattice.h:220
Optional< APInt > asConstantInteger() const
Definition: ValueLattice.h:106
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
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.
bool satisfiesPredicate(CmpInst::Predicate Pred, const ValueLatticeElement &Other) const
Definition: ValueLattice.h:226
static ValueLatticeElement getNot(Constant *C)
Definition: ValueLattice.h:67
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
const ConstantRange & getConstantRange() const
Definition: ValueLattice.h:100
bool isOverdefined() const
Definition: ValueLattice.h:88
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...
bool isNotConstant() const
Definition: ValueLattice.h:86
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:853
bool isConstantRange() const
Definition: ValueLattice.h:87
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:73
Constant * getConstant() const
Definition: ValueLattice.h:90
Constant * getNotConstant() const
Definition: ValueLattice.h:95
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
Basic Alias true
bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL)
Updates this object to approximate both this object and RHS.
Definition: ValueLattice.h:178
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2018
bool isSingleElement() const
Return true if this set contains exactly one member.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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:78