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 {
26 class ValueLatticeElement {
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     unknown,
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     /// This Value is an UndefValue constant or produces undef. Undefined values
51     /// can be merged with constants (or single element constant ranges),
52     /// assuming all uses of the result will be replaced.
53     undef
54   };
55 
56   ValueLatticeElementTy Tag;
57 
58   /// The union either stores a pointer to a constant or a constant range,
59   /// associated to the lattice element. We have to ensure that Range is
60   /// initialized or destroyed when changing state to or from constantrange.
61   union {
62     Constant *ConstVal;
63     ConstantRange Range;
64   };
65 
66 public:
67   // Const and Range are initialized on-demand.
68   ValueLatticeElement() : Tag(unknown) {}
69 
70   /// Custom destructor to ensure Range is properly destroyed, when the object
71   /// is deallocated.
72   ~ValueLatticeElement() {
73     switch (Tag) {
74     case overdefined:
75     case unknown:
76     case undef:
77     case constant:
78     case notconstant:
79       break;
80     case constantrange:
81       Range.~ConstantRange();
82       break;
83     };
84   }
85 
86   /// Custom copy constructor, to ensure Range gets initialized when
87   /// copying a constant range lattice element.
88   ValueLatticeElement(const ValueLatticeElement &Other) : Tag(unknown) {
89     *this = Other;
90   }
91 
92   /// Custom assignment operator, to ensure Range gets initialized when
93   /// assigning a constant range lattice element.
94   ValueLatticeElement &operator=(const ValueLatticeElement &Other) {
95     // If we change the state of this from constant range to non constant range,
96     // destroy Range.
97     if (isConstantRange() && !Other.isConstantRange())
98       Range.~ConstantRange();
99 
100     // If we change the state of this from a valid ConstVal to another a state
101     // without a valid ConstVal, zero the pointer.
102     if ((isConstant() || isNotConstant()) && !Other.isConstant() &&
103         !Other.isNotConstant())
104       ConstVal = nullptr;
105 
106     switch (Other.Tag) {
107     case constantrange:
108       if (!isConstantRange())
109         new (&Range) ConstantRange(Other.Range);
110       else
111         Range = Other.Range;
112       break;
113     case constant:
114     case notconstant:
115       ConstVal = Other.ConstVal;
116       break;
117     case overdefined:
118     case unknown:
119     case undef:
120       break;
121     }
122     Tag = Other.Tag;
123     return *this;
124   }
125 
126   static ValueLatticeElement get(Constant *C) {
127     ValueLatticeElement Res;
128     if (isa<UndefValue>(C))
129       Res.markUndef();
130     else
131       Res.markConstant(C);
132     return Res;
133   }
134   static ValueLatticeElement getNot(Constant *C) {
135     ValueLatticeElement Res;
136     assert(!isa<UndefValue>(C) && "!= undef is not supported");
137     Res.markNotConstant(C);
138     return Res;
139   }
140   static ValueLatticeElement getRange(ConstantRange CR) {
141     ValueLatticeElement Res;
142     Res.markConstantRange(std::move(CR));
143     return Res;
144   }
145   static ValueLatticeElement getOverdefined() {
146     ValueLatticeElement Res;
147     Res.markOverdefined();
148     return Res;
149   }
150 
151   bool isUndef() const { return Tag == undef; }
152   bool isUnknown() const { return Tag == unknown; }
153   bool isUnknownOrUndef() const { return Tag == unknown || Tag == undef; }
154   bool isUndefined() const { return isUnknownOrUndef(); }
155   bool isConstant() const { return Tag == constant; }
156   bool isNotConstant() const { return Tag == notconstant; }
157   bool isConstantRange() const { return Tag == constantrange; }
158   bool isOverdefined() const { return Tag == overdefined; }
159 
160   Constant *getConstant() const {
161     assert(isConstant() && "Cannot get the constant of a non-constant!");
162     return ConstVal;
163   }
164 
165   Constant *getNotConstant() const {
166     assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
167     return ConstVal;
168   }
169 
170   const ConstantRange &getConstantRange() const {
171     assert(isConstantRange() &&
172            "Cannot get the constant-range of a non-constant-range!");
173     return Range;
174   }
175 
176   Optional<APInt> asConstantInteger() const {
177     if (isConstant() && isa<ConstantInt>(getConstant())) {
178       return cast<ConstantInt>(getConstant())->getValue();
179     } else if (isConstantRange() && getConstantRange().isSingleElement()) {
180       return *getConstantRange().getSingleElement();
181     }
182     return None;
183   }
184 
185   bool markOverdefined() {
186     if (isOverdefined())
187       return false;
188     if (isConstant() || isNotConstant())
189       ConstVal = nullptr;
190     if (isConstantRange())
191       Range.~ConstantRange();
192     Tag = overdefined;
193     return true;
194   }
195 
196   bool markUndef() {
197     if (isUndef())
198       return false;
199 
200     assert(isUnknown());
201     Tag = undef;
202     return true;
203   }
204 
205   bool markConstant(Constant *V) {
206     if (isa<UndefValue>(V))
207       return markUndef();
208 
209     if (isConstant()) {
210       assert(getConstant() == V && "Marking constant with different value");
211       return false;
212     }
213 
214     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
215       return markConstantRange(ConstantRange(CI->getValue()));
216 
217     assert(isUnknown() || isUndef());
218     Tag = constant;
219     ConstVal = V;
220     return true;
221   }
222 
223   bool markNotConstant(Constant *V) {
224     assert(V && "Marking constant with NULL");
225     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
226       return markConstantRange(
227           ConstantRange(CI->getValue() + 1, CI->getValue()));
228 
229     if (isa<UndefValue>(V))
230       return false;
231 
232     if (isNotConstant()) {
233       assert(getNotConstant() == V && "Marking !constant with different value");
234       return false;
235     }
236 
237     assert(isUnknown());
238     Tag = notconstant;
239     ConstVal = V;
240     return true;
241   }
242 
243   /// Mark the object as constant range with \p NewR. If the object is already a
244   /// constant range, nothing changes if the existing range is equal to \p
245   /// NewR. Otherwise \p NewR must be a superset of the existing range or the
246   /// object must be undef.
247   bool markConstantRange(ConstantRange NewR) {
248     if (isConstantRange()) {
249       if (getConstantRange() == NewR)
250         return false;
251 
252       if (NewR.isEmptySet())
253         return markOverdefined();
254 
255       assert(NewR.contains(getConstantRange()) &&
256              "Existing range must be a subset of NewR");
257       Range = std::move(NewR);
258       return true;
259     }
260 
261     assert(isUnknown() || isUndef());
262     if (NewR.isEmptySet())
263       return markOverdefined();
264 
265     Tag = constantrange;
266     new (&Range) ConstantRange(std::move(NewR));
267     return true;
268   }
269 
270   /// Updates this object to approximate both this object and RHS. Returns
271   /// true if this object has been changed.
272   bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
273     if (RHS.isUnknown() || isOverdefined())
274       return false;
275     if (RHS.isOverdefined()) {
276       markOverdefined();
277       return true;
278     }
279 
280     if (isUndef()) {
281       assert(!RHS.isUnknown());
282       if (RHS.isUndef())
283         return false;
284       if (RHS.isConstant())
285         return markConstant(RHS.getConstant());
286       if (RHS.isConstantRange() && RHS.getConstantRange().isSingleElement())
287         return markConstantRange(RHS.getConstantRange());
288       return markOverdefined();
289     }
290 
291     if (isUnknown()) {
292       assert(!RHS.isUnknown() && "Unknow RHS should be handled earlier");
293       *this = RHS;
294       return true;
295     }
296 
297     if (isConstant()) {
298       if (RHS.isConstant() && getConstant() == RHS.getConstant())
299         return false;
300       if (RHS.isUndef())
301         return false;
302       markOverdefined();
303       return true;
304     }
305 
306     if (isNotConstant()) {
307       if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant())
308         return false;
309       markOverdefined();
310       return true;
311     }
312 
313     assert(isConstantRange() && "New ValueLattice type?");
314     if (RHS.isUndef() && getConstantRange().isSingleElement())
315       return false;
316 
317     if (!RHS.isConstantRange()) {
318       // We can get here if we've encountered a constantexpr of integer type
319       // and merge it with a constantrange.
320       markOverdefined();
321       return true;
322     }
323     ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange());
324     if (NewR.isFullSet())
325       return markOverdefined();
326     else if (NewR == getConstantRange())
327       return false;
328     else
329       return markConstantRange(std::move(NewR));
330   }
331 
332   /// Compares this symbolic value with Other using Pred and returns either
333   /// true, false or undef constants, or nullptr if the comparison cannot be
334   /// evaluated.
335   Constant *getCompare(CmpInst::Predicate Pred, Type *Ty,
336                        const ValueLatticeElement &Other) const {
337     if (isUnknownOrUndef() || Other.isUnknownOrUndef())
338       return UndefValue::get(Ty);
339 
340     if (isConstant() && Other.isConstant())
341       return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant());
342 
343     // Integer constants are represented as ConstantRanges with single
344     // elements.
345     if (!isConstantRange() || !Other.isConstantRange())
346       return nullptr;
347 
348     const auto &CR = getConstantRange();
349     const auto &OtherCR = Other.getConstantRange();
350     if (ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR))
351       return ConstantInt::getTrue(Ty);
352     if (ConstantRange::makeSatisfyingICmpRegion(
353             CmpInst::getInversePredicate(Pred), OtherCR)
354             .contains(CR))
355       return ConstantInt::getFalse(Ty);
356 
357     return nullptr;
358   }
359 };
360 
361 raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);
362 
363 } // end namespace llvm
364 #endif
365