Line data Source code
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.
64 7634736 : ValueLatticeElement() : Tag(undefined) {}
65 :
66 : /// Custom destructor to ensure Range is properly destroyed, when the object
67 : /// is deallocated.
68 2413108 : ~ValueLatticeElement() {
69 14243172 : switch (Tag) {
70 : case overdefined:
71 : case undefined:
72 : case constant:
73 : case notconstant:
74 : break;
75 1059335 : case constantrange:
76 1059335 : 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 2935470 : ValueLatticeElement(const ValueLatticeElement &Other) : Tag(undefined) {
84 2935470 : *this = Other;
85 : }
86 :
87 : /// Custom assignment operator, to ensure Range gets initialized when
88 : /// assigning a constant range lattice element.
89 9532163 : ValueLatticeElement &operator=(const ValueLatticeElement &Other) {
90 : // If we change the state of this from constant range to non constant range,
91 : // destroy Range.
92 9532163 : if (isConstantRange() && !Other.isConstantRange())
93 0 : 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 9532163 : if ((isConstant() || isNotConstant()) && !Other.isConstant() &&
98 : !Other.isNotConstant())
99 0 : ConstVal = nullptr;
100 :
101 9532163 : switch (Other.Tag) {
102 887939 : case constantrange:
103 887939 : if (!isConstantRange())
104 886804 : new (&Range) ConstantRange(Other.Range);
105 : else
106 : Range = Other.Range;
107 : break;
108 2566705 : case constant:
109 : case notconstant:
110 2566705 : ConstVal = Other.ConstVal;
111 2566705 : break;
112 : case overdefined:
113 : case undefined:
114 : break;
115 : }
116 9532163 : Tag = Other.Tag;
117 9532163 : return *this;
118 : }
119 :
120 : static ValueLatticeElement get(Constant *C) {
121 : ValueLatticeElement Res;
122 275159 : if (!isa<UndefValue>(C))
123 275084 : Res.markConstant(C);
124 : return Res;
125 : }
126 : static ValueLatticeElement getNot(Constant *C) {
127 : ValueLatticeElement Res;
128 172924 : if (!isa<UndefValue>(C))
129 172924 : Res.markNotConstant(C);
130 : return Res;
131 : }
132 92006 : static ValueLatticeElement getRange(ConstantRange CR) {
133 : ValueLatticeElement Res;
134 92006 : Res.markConstantRange(std::move(CR));
135 92006 : return Res;
136 : }
137 : static ValueLatticeElement getOverdefined() {
138 : ValueLatticeElement Res;
139 4367480 : Res.markOverdefined();
140 : return Res;
141 : }
142 :
143 0 : bool isUndefined() const { return Tag == undefined; }
144 1 : bool isConstant() const { return Tag == constant; }
145 1 : bool isNotConstant() const { return Tag == notconstant; }
146 7 : bool isConstantRange() const { return Tag == constantrange; }
147 3 : bool isOverdefined() const { return Tag == overdefined; }
148 :
149 0 : Constant *getConstant() const {
150 : assert(isConstant() && "Cannot get the constant of a non-constant!");
151 0 : return ConstVal;
152 : }
153 :
154 0 : Constant *getNotConstant() const {
155 : assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
156 0 : return ConstVal;
157 : }
158 :
159 : const ConstantRange &getConstantRange() const {
160 : assert(isConstantRange() &&
161 : "Cannot get the constant-range of a non-constant-range!");
162 91535 : return Range;
163 : }
164 :
165 68552 : Optional<APInt> asConstantInteger() const {
166 68552 : if (isConstant() && isa<ConstantInt>(getConstant())) {
167 : return cast<ConstantInt>(getConstant())->getValue();
168 70044 : } else if (isConstantRange() && getConstantRange().isSingleElement()) {
169 69 : return *getConstantRange().getSingleElement();
170 : }
171 : return None;
172 : }
173 :
174 : private:
175 4756054 : void markOverdefined() {
176 4756054 : if (isOverdefined())
177 : return;
178 4756054 : if (isConstant() || isNotConstant())
179 95414 : ConstVal = nullptr;
180 4756054 : if (isConstantRange())
181 8052 : Range.~ConstantRange();
182 4756054 : Tag = overdefined;
183 : }
184 :
185 275084 : void markConstant(Constant *V) {
186 : assert(V && "Marking constant with NULL");
187 : if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
188 70225 : markConstantRange(ConstantRange(CI->getValue()));
189 70225 : return;
190 : }
191 204859 : if (isa<UndefValue>(V))
192 : return;
193 :
194 : assert((!isConstant() || getConstant() == V) &&
195 : "Marking constant with different value");
196 : assert(isUndefined());
197 204859 : Tag = constant;
198 204859 : ConstVal = V;
199 : }
200 :
201 172924 : void markNotConstant(Constant *V) {
202 : assert(V && "Marking constant with NULL");
203 : if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
204 18460 : markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()));
205 18460 : return;
206 : }
207 154464 : 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 154464 : Tag = notconstant;
216 154464 : ConstVal = V;
217 : }
218 :
219 185190 : void markConstantRange(ConstantRange NewR) {
220 185190 : if (isConstantRange()) {
221 4499 : if (NewR.isEmptySet())
222 0 : markOverdefined();
223 : else {
224 4499 : Range = std::move(NewR);
225 : }
226 4499 : return;
227 : }
228 :
229 : assert(isUndefined());
230 180691 : if (NewR.isEmptySet())
231 8 : markOverdefined();
232 : else {
233 180683 : 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 922113 : bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
242 922113 : if (RHS.isUndefined() || isOverdefined())
243 : return false;
244 880724 : if (RHS.isOverdefined()) {
245 297092 : markOverdefined();
246 297092 : return true;
247 : }
248 :
249 583632 : if (isUndefined()) {
250 398139 : *this = RHS;
251 398139 : return !RHS.isUndefined();
252 : }
253 :
254 185493 : if (isConstant()) {
255 87304 : if (RHS.isConstant() && getConstant() == RHS.getConstant())
256 : return false;
257 85980 : markOverdefined();
258 85980 : return true;
259 : }
260 :
261 98189 : if (isNotConstant()) {
262 73770 : if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant())
263 : return false;
264 415 : markOverdefined();
265 415 : return true;
266 : }
267 :
268 : assert(isConstantRange() && "New ValueLattice type?");
269 24419 : 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 0 : markOverdefined();
273 0 : return true;
274 : }
275 48838 : ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange());
276 24419 : if (NewR.isFullSet())
277 5079 : markOverdefined();
278 19340 : else if (NewR == getConstantRange())
279 : return false;
280 : else
281 4499 : markConstantRange(std::move(NewR));
282 : return true;
283 : }
284 :
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.
294 91338 : Constant *getCompare(CmpInst::Predicate Pred, Type *Ty,
295 : const ValueLatticeElement &Other) const {
296 91338 : if (isUndefined() || Other.isUndefined())
297 5683 : return UndefValue::get(Ty);
298 :
299 85655 : if (isConstant() && Other.isConstant())
300 183 : return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant());
301 :
302 : // Integer constants are represented as ConstantRanges with single
303 : // elements.
304 85472 : if (!isConstantRange() || !Other.isConstantRange())
305 : return nullptr;
306 :
307 : const auto &CR = getConstantRange();
308 : const auto &OtherCR = Other.getConstantRange();
309 4731 : if (ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR))
310 3233 : return ConstantInt::getTrue(Ty);
311 2996 : if (ConstantRange::makeSatisfyingICmpRegion(
312 : CmpInst::getInversePredicate(Pred), OtherCR)
313 1498 : .contains(CR))
314 1478 : 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
|
