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/Constants.h" |
13 | #include "llvm/IR/ConstantRange.h" |
14 | #include "llvm/IR/Instructions.h" |
15 | |
16 | //===----------------------------------------------------------------------===// |
17 | // ValueLatticeElement |
18 | //===----------------------------------------------------------------------===// |
19 | |
20 | namespace llvm { |
21 | |
22 | class Constant; |
23 | |
24 | /// This class represents lattice values for constants. |
25 | /// |
26 | /// FIXME: This is basically just for bringup, this can be made a lot more rich |
27 | /// in the future. |
28 | /// |
29 | class ValueLatticeElement { |
30 | enum ValueLatticeElementTy { |
31 | /// This Value has no known value yet. As a result, this implies the |
32 | /// producing instruction is dead. Caution: We use this as the starting |
33 | /// state in our local meet rules. In this usage, it's taken to mean |
34 | /// "nothing known yet". |
35 | /// Transition to any other state allowed. |
36 | unknown, |
37 | |
38 | /// This Value is an UndefValue constant or produces undef. Undefined values |
39 | /// can be merged with constants (or single element constant ranges), |
40 | /// assuming all uses of the result will be replaced. |
41 | /// Transition allowed to the following states: |
42 | /// constant |
43 | /// constantrange_including_undef |
44 | /// overdefined |
45 | undef, |
46 | |
47 | /// This Value has a specific constant value. The constant cannot be undef. |
48 | /// (For constant integers, constantrange is used instead. Integer typed |
49 | /// constantexprs can appear as constant.) Note that the constant state |
50 | /// can be reached by merging undef & constant states. |
51 | /// Transition allowed to the following states: |
52 | /// overdefined |
53 | constant, |
54 | |
55 | /// This Value is known to not have the specified value. (For constant |
56 | /// integers, constantrange is used instead. As above, integer typed |
57 | /// constantexprs can appear here.) |
58 | /// Transition allowed to the following states: |
59 | /// overdefined |
60 | notconstant, |
61 | |
62 | /// The Value falls within this range. (Used only for integer typed values.) |
63 | /// Transition allowed to the following states: |
64 | /// constantrange (new range must be a superset of the existing range) |
65 | /// constantrange_including_undef |
66 | /// overdefined |
67 | constantrange, |
68 | |
69 | /// This Value falls within this range, but also may be undef. |
70 | /// Merging it with other constant ranges results in |
71 | /// constantrange_including_undef. |
72 | /// Transition allowed to the following states: |
73 | /// overdefined |
74 | constantrange_including_undef, |
75 | |
76 | /// We can not precisely model the dynamic values this value might take. |
77 | /// No transitions are allowed after reaching overdefined. |
78 | overdefined, |
79 | }; |
80 | |
81 | ValueLatticeElementTy Tag : 8; |
82 | /// Number of times a constant range has been extended with widening enabled. |
83 | unsigned NumRangeExtensions : 8; |
84 | |
85 | /// The union either stores a pointer to a constant or a constant range, |
86 | /// associated to the lattice element. We have to ensure that Range is |
87 | /// initialized or destroyed when changing state to or from constantrange. |
88 | union { |
89 | Constant *ConstVal; |
90 | ConstantRange Range; |
91 | }; |
92 | |
93 | /// Destroy contents of lattice value, without destructing the object. |
94 | void destroy() { |
95 | switch (Tag) { |
96 | case overdefined: |
97 | case unknown: |
98 | case undef: |
99 | case constant: |
100 | case notconstant: |
101 | break; |
102 | case constantrange_including_undef: |
103 | case constantrange: |
104 | Range.~ConstantRange(); |
105 | break; |
106 | }; |
107 | } |
108 | |
109 | public: |
110 | /// Struct to control some aspects related to merging constant ranges. |
111 | struct MergeOptions { |
112 | /// The merge value may include undef. |
113 | bool MayIncludeUndef; |
114 | |
115 | /// Handle repeatedly extending a range by going to overdefined after a |
116 | /// number of steps. |
117 | bool CheckWiden; |
118 | |
119 | /// The number of allowed widening steps (including setting the range |
120 | /// initially). |
121 | unsigned MaxWidenSteps; |
122 | |
123 | MergeOptions() : MergeOptions(false, false) {} |
124 | |
125 | MergeOptions(bool MayIncludeUndef, bool CheckWiden, |
126 | unsigned MaxWidenSteps = 1) |
127 | : MayIncludeUndef(MayIncludeUndef), CheckWiden(CheckWiden), |
128 | MaxWidenSteps(MaxWidenSteps) {} |
129 | |
130 | MergeOptions &setMayIncludeUndef(bool V = true) { |
131 | MayIncludeUndef = V; |
132 | return *this; |
133 | } |
134 | |
135 | MergeOptions &setCheckWiden(bool V = true) { |
136 | CheckWiden = V; |
137 | return *this; |
138 | } |
139 | |
140 | MergeOptions &setMaxWidenSteps(unsigned Steps = 1) { |
141 | CheckWiden = true; |
142 | MaxWidenSteps = Steps; |
143 | return *this; |
144 | } |
145 | }; |
146 | |
147 | // ConstVal and Range are initialized on-demand. |
148 | ValueLatticeElement() : Tag(unknown), NumRangeExtensions(0) {} |
149 | |
150 | ~ValueLatticeElement() { destroy(); } |
151 | |
152 | ValueLatticeElement(const ValueLatticeElement &Other) |
153 | : Tag(Other.Tag), NumRangeExtensions(0) { |
154 | switch (Other.Tag) { |
155 | case constantrange: |
156 | case constantrange_including_undef: |
157 | new (&Range) ConstantRange(Other.Range); |
158 | NumRangeExtensions = Other.NumRangeExtensions; |
159 | break; |
160 | case constant: |
161 | case notconstant: |
162 | ConstVal = Other.ConstVal; |
163 | break; |
164 | case overdefined: |
165 | case unknown: |
166 | case undef: |
167 | break; |
168 | } |
169 | } |
170 | |
171 | ValueLatticeElement(ValueLatticeElement &&Other) |
172 | : Tag(Other.Tag), NumRangeExtensions(0) { |
173 | switch (Other.Tag) { |
174 | case constantrange: |
175 | case constantrange_including_undef: |
176 | new (&Range) ConstantRange(std::move(Other.Range)); |
177 | NumRangeExtensions = Other.NumRangeExtensions; |
178 | break; |
179 | case constant: |
180 | case notconstant: |
181 | ConstVal = Other.ConstVal; |
182 | break; |
183 | case overdefined: |
184 | case unknown: |
185 | case undef: |
186 | break; |
187 | } |
188 | Other.Tag = unknown; |
189 | } |
190 | |
191 | ValueLatticeElement &operator=(const ValueLatticeElement &Other) { |
192 | destroy(); |
193 | new (this) ValueLatticeElement(Other); |
194 | return *this; |
195 | } |
196 | |
197 | ValueLatticeElement &operator=(ValueLatticeElement &&Other) { |
198 | destroy(); |
199 | new (this) ValueLatticeElement(std::move(Other)); |
200 | return *this; |
201 | } |
202 | |
203 | static ValueLatticeElement get(Constant *C) { |
204 | ValueLatticeElement Res; |
205 | Res.markConstant(V: C); |
206 | return Res; |
207 | } |
208 | static ValueLatticeElement getNot(Constant *C) { |
209 | ValueLatticeElement Res; |
210 | assert(!isa<UndefValue>(C) && "!= undef is not supported" ); |
211 | Res.markNotConstant(V: C); |
212 | return Res; |
213 | } |
214 | static ValueLatticeElement getRange(ConstantRange CR, |
215 | bool MayIncludeUndef = false) { |
216 | if (CR.isFullSet()) |
217 | return getOverdefined(); |
218 | |
219 | if (CR.isEmptySet()) { |
220 | ValueLatticeElement Res; |
221 | if (MayIncludeUndef) |
222 | Res.markUndef(); |
223 | return Res; |
224 | } |
225 | |
226 | ValueLatticeElement Res; |
227 | Res.markConstantRange(NewR: std::move(CR), |
228 | Opts: MergeOptions().setMayIncludeUndef(MayIncludeUndef)); |
229 | return Res; |
230 | } |
231 | static ValueLatticeElement getOverdefined() { |
232 | ValueLatticeElement Res; |
233 | Res.markOverdefined(); |
234 | return Res; |
235 | } |
236 | |
237 | bool isUndef() const { return Tag == undef; } |
238 | bool isUnknown() const { return Tag == unknown; } |
239 | bool isUnknownOrUndef() const { return Tag == unknown || Tag == undef; } |
240 | bool isConstant() const { return Tag == constant; } |
241 | bool isNotConstant() const { return Tag == notconstant; } |
242 | bool isConstantRangeIncludingUndef() const { |
243 | return Tag == constantrange_including_undef; |
244 | } |
245 | /// Returns true if this value is a constant range. Use \p UndefAllowed to |
246 | /// exclude non-singleton constant ranges that may also be undef. Note that |
247 | /// this function also returns true if the range may include undef, but only |
248 | /// contains a single element. In that case, it can be replaced by a constant. |
249 | bool isConstantRange(bool UndefAllowed = true) const { |
250 | return Tag == constantrange || (Tag == constantrange_including_undef && |
251 | (UndefAllowed || Range.isSingleElement())); |
252 | } |
253 | bool isOverdefined() const { return Tag == overdefined; } |
254 | |
255 | Constant *getConstant() const { |
256 | assert(isConstant() && "Cannot get the constant of a non-constant!" ); |
257 | return ConstVal; |
258 | } |
259 | |
260 | Constant *getNotConstant() const { |
261 | assert(isNotConstant() && "Cannot get the constant of a non-notconstant!" ); |
262 | return ConstVal; |
263 | } |
264 | |
265 | /// Returns the constant range for this value. Use \p UndefAllowed to exclude |
266 | /// non-singleton constant ranges that may also be undef. Note that this |
267 | /// function also returns a range if the range may include undef, but only |
268 | /// contains a single element. In that case, it can be replaced by a constant. |
269 | const ConstantRange &getConstantRange(bool UndefAllowed = true) const { |
270 | assert(isConstantRange(UndefAllowed) && |
271 | "Cannot get the constant-range of a non-constant-range!" ); |
272 | return Range; |
273 | } |
274 | |
275 | std::optional<APInt> asConstantInteger() const { |
276 | if (isConstant() && isa<ConstantInt>(Val: getConstant())) { |
277 | return cast<ConstantInt>(Val: getConstant())->getValue(); |
278 | } else if (isConstantRange() && getConstantRange().isSingleElement()) { |
279 | return *getConstantRange().getSingleElement(); |
280 | } |
281 | return std::nullopt; |
282 | } |
283 | |
284 | bool markOverdefined() { |
285 | if (isOverdefined()) |
286 | return false; |
287 | destroy(); |
288 | Tag = overdefined; |
289 | return true; |
290 | } |
291 | |
292 | bool markUndef() { |
293 | if (isUndef()) |
294 | return false; |
295 | |
296 | assert(isUnknown()); |
297 | Tag = undef; |
298 | return true; |
299 | } |
300 | |
301 | bool markConstant(Constant *V, bool MayIncludeUndef = false) { |
302 | if (isa<UndefValue>(Val: V)) |
303 | return markUndef(); |
304 | |
305 | if (isConstant()) { |
306 | assert(getConstant() == V && "Marking constant with different value" ); |
307 | return false; |
308 | } |
309 | |
310 | if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: V)) |
311 | return markConstantRange( |
312 | NewR: ConstantRange(CI->getValue()), |
313 | Opts: MergeOptions().setMayIncludeUndef(MayIncludeUndef)); |
314 | |
315 | assert(isUnknown() || isUndef()); |
316 | Tag = constant; |
317 | ConstVal = V; |
318 | return true; |
319 | } |
320 | |
321 | bool markNotConstant(Constant *V) { |
322 | assert(V && "Marking constant with NULL" ); |
323 | if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: V)) |
324 | return markConstantRange( |
325 | NewR: ConstantRange(CI->getValue() + 1, CI->getValue())); |
326 | |
327 | if (isa<UndefValue>(Val: V)) |
328 | return false; |
329 | |
330 | if (isNotConstant()) { |
331 | assert(getNotConstant() == V && "Marking !constant with different value" ); |
332 | return false; |
333 | } |
334 | |
335 | assert(isUnknown()); |
336 | Tag = notconstant; |
337 | ConstVal = V; |
338 | return true; |
339 | } |
340 | |
341 | /// Mark the object as constant range with \p NewR. If the object is already a |
342 | /// constant range, nothing changes if the existing range is equal to \p |
343 | /// NewR and the tag. Otherwise \p NewR must be a superset of the existing |
344 | /// range or the object must be undef. The tag is set to |
345 | /// constant_range_including_undef if either the existing value or the new |
346 | /// range may include undef. |
347 | bool markConstantRange(ConstantRange NewR, |
348 | MergeOptions Opts = MergeOptions()) { |
349 | assert(!NewR.isEmptySet() && "should only be called for non-empty sets" ); |
350 | |
351 | if (NewR.isFullSet()) |
352 | return markOverdefined(); |
353 | |
354 | ValueLatticeElementTy OldTag = Tag; |
355 | ValueLatticeElementTy NewTag = |
356 | (isUndef() || isConstantRangeIncludingUndef() || Opts.MayIncludeUndef) |
357 | ? constantrange_including_undef |
358 | : constantrange; |
359 | if (isConstantRange()) { |
360 | Tag = NewTag; |
361 | if (getConstantRange() == NewR) |
362 | return Tag != OldTag; |
363 | |
364 | // Simple form of widening. If a range is extended multiple times, go to |
365 | // overdefined. |
366 | if (Opts.CheckWiden && ++NumRangeExtensions > Opts.MaxWidenSteps) |
367 | return markOverdefined(); |
368 | |
369 | assert(NewR.contains(getConstantRange()) && |
370 | "Existing range must be a subset of NewR" ); |
371 | Range = std::move(NewR); |
372 | return true; |
373 | } |
374 | |
375 | assert(isUnknown() || isUndef()); |
376 | |
377 | NumRangeExtensions = 0; |
378 | Tag = NewTag; |
379 | new (&Range) ConstantRange(std::move(NewR)); |
380 | return true; |
381 | } |
382 | |
383 | /// Updates this object to approximate both this object and RHS. Returns |
384 | /// true if this object has been changed. |
385 | bool mergeIn(const ValueLatticeElement &RHS, |
386 | MergeOptions Opts = MergeOptions()) { |
387 | if (RHS.isUnknown() || isOverdefined()) |
388 | return false; |
389 | if (RHS.isOverdefined()) { |
390 | markOverdefined(); |
391 | return true; |
392 | } |
393 | |
394 | if (isUndef()) { |
395 | assert(!RHS.isUnknown()); |
396 | if (RHS.isUndef()) |
397 | return false; |
398 | if (RHS.isConstant()) |
399 | return markConstant(V: RHS.getConstant(), MayIncludeUndef: true); |
400 | if (RHS.isConstantRange()) |
401 | return markConstantRange(NewR: RHS.getConstantRange(UndefAllowed: true), |
402 | Opts: Opts.setMayIncludeUndef()); |
403 | return markOverdefined(); |
404 | } |
405 | |
406 | if (isUnknown()) { |
407 | assert(!RHS.isUnknown() && "Unknow RHS should be handled earlier" ); |
408 | *this = RHS; |
409 | return true; |
410 | } |
411 | |
412 | if (isConstant()) { |
413 | if (RHS.isConstant() && getConstant() == RHS.getConstant()) |
414 | return false; |
415 | if (RHS.isUndef()) |
416 | return false; |
417 | markOverdefined(); |
418 | return true; |
419 | } |
420 | |
421 | if (isNotConstant()) { |
422 | if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant()) |
423 | return false; |
424 | markOverdefined(); |
425 | return true; |
426 | } |
427 | |
428 | auto OldTag = Tag; |
429 | assert(isConstantRange() && "New ValueLattice type?" ); |
430 | if (RHS.isUndef()) { |
431 | Tag = constantrange_including_undef; |
432 | return OldTag != Tag; |
433 | } |
434 | |
435 | if (!RHS.isConstantRange()) { |
436 | // We can get here if we've encountered a constantexpr of integer type |
437 | // and merge it with a constantrange. |
438 | markOverdefined(); |
439 | return true; |
440 | } |
441 | |
442 | ConstantRange NewR = getConstantRange().unionWith(CR: RHS.getConstantRange()); |
443 | return markConstantRange( |
444 | NewR: std::move(NewR), |
445 | Opts: Opts.setMayIncludeUndef(RHS.isConstantRangeIncludingUndef())); |
446 | } |
447 | |
448 | // Compares this symbolic value with Other using Pred and returns either |
449 | /// true, false or undef constants, or nullptr if the comparison cannot be |
450 | /// evaluated. |
451 | Constant *getCompare(CmpInst::Predicate Pred, Type *Ty, |
452 | const ValueLatticeElement &Other, |
453 | const DataLayout &DL) const; |
454 | |
455 | unsigned getNumRangeExtensions() const { return NumRangeExtensions; } |
456 | void setNumRangeExtensions(unsigned N) { NumRangeExtensions = N; } |
457 | }; |
458 | |
459 | static_assert(sizeof(ValueLatticeElement) <= 40, |
460 | "size of ValueLatticeElement changed unexpectedly" ); |
461 | |
462 | raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val); |
463 | } // end namespace llvm |
464 | #endif |
465 | |