• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 {
27 class ValueLatticeElement {
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 {
58     Constant *ConstVal;
59     ConstantRange Range;
60   };
61 
62 public:
63   // Const and Range are initialized on-demand.
ValueLatticeElement()64   ValueLatticeElement() : Tag(undefined) {}
65 
66   /// Custom destructor to ensure Range is properly destroyed, when the object
67   /// is deallocated.
~ValueLatticeElement()68   ~ValueLatticeElement() {
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.
ValueLatticeElement(const ValueLatticeElement & Other)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.
89   ValueLatticeElement &operator=(const ValueLatticeElement &Other) {
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 
get(Constant * C)120   static ValueLatticeElement get(Constant *C) {
121     ValueLatticeElement Res;
122     if (!isa<UndefValue>(C))
123       Res.markConstant(C);
124     return Res;
125   }
getNot(Constant * C)126   static ValueLatticeElement getNot(Constant *C) {
127     ValueLatticeElement Res;
128     if (!isa<UndefValue>(C))
129       Res.markNotConstant(C);
130     return Res;
131   }
getRange(ConstantRange CR)132   static ValueLatticeElement getRange(ConstantRange CR) {
133     ValueLatticeElement Res;
134     Res.markConstantRange(std::move(CR));
135     return Res;
136   }
getOverdefined()137   static ValueLatticeElement getOverdefined() {
138     ValueLatticeElement Res;
139     Res.markOverdefined();
140     return Res;
141   }
142 
isUndefined()143   bool isUndefined() const { return Tag == undefined; }
isConstant()144   bool isConstant() const { return Tag == constant; }
isNotConstant()145   bool isNotConstant() const { return Tag == notconstant; }
isConstantRange()146   bool isConstantRange() const { return Tag == constantrange; }
isOverdefined()147   bool isOverdefined() const { return Tag == overdefined; }
148 
getConstant()149   Constant *getConstant() const {
150     assert(isConstant() && "Cannot get the constant of a non-constant!");
151     return ConstVal;
152   }
153 
getNotConstant()154   Constant *getNotConstant() const {
155     assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
156     return ConstVal;
157   }
158 
getConstantRange()159   const ConstantRange &getConstantRange() const {
160     assert(isConstantRange() &&
161            "Cannot get the constant-range of a non-constant-range!");
162     return Range;
163   }
164 
asConstantInteger()165   Optional<APInt> asConstantInteger() const {
166     if (isConstant() && isa<ConstantInt>(getConstant())) {
167       return cast<ConstantInt>(getConstant())->getValue();
168     } else if (isConstantRange() && getConstantRange().isSingleElement()) {
169       return *getConstantRange().getSingleElement();
170     }
171     return None;
172   }
173 
174 private:
markOverdefined()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 
markConstant(Constant * V)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 
markNotConstant(Constant * V)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 
markConstantRange(ConstantRange NewR)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.
mergeIn(const ValueLatticeElement & RHS,const DataLayout & DL)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     }
275     ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange());
276     if (NewR.isFullSet())
277       markOverdefined();
278     else if (NewR == getConstantRange())
279       return false;
280     else
281       markConstantRange(std::move(NewR));
282     return true;
283   }
284 
getConstantInt()285   ConstantInt *getConstantInt() const {
286     assert(isConstant() && isa<ConstantInt>(getConstant()) &&
287            "No integer constant");
288     return cast<ConstantInt>(getConstant());
289   }
290 
291   /// Compares this symbolic value with Other using Pred and returns either
292   /// true, false or undef constants, or nullptr if the comparison cannot be
293   /// evaluated.
getCompare(CmpInst::Predicate Pred,Type * Ty,const ValueLatticeElement & Other)294   Constant *getCompare(CmpInst::Predicate Pred, Type *Ty,
295                        const ValueLatticeElement &Other) const {
296     if (isUndefined() || Other.isUndefined())
297       return UndefValue::get(Ty);
298 
299     if (isConstant() && Other.isConstant())
300       return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant());
301 
302     // Integer constants are represented as ConstantRanges with single
303     // elements.
304     if (!isConstantRange() || !Other.isConstantRange())
305       return nullptr;
306 
307     const auto &CR = getConstantRange();
308     const auto &OtherCR = Other.getConstantRange();
309     if (ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR))
310       return ConstantInt::getTrue(Ty);
311     if (ConstantRange::makeSatisfyingICmpRegion(
312             CmpInst::getInversePredicate(Pred), OtherCR)
313             .contains(CR))
314       return ConstantInt::getFalse(Ty);
315 
316     return nullptr;
317   }
318 };
319 
320 raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);
321 
322 } // end namespace llvm
323 #endif
324