LLVM 18.0.0git
ValueLattice.h
Go to the documentation of this file.
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"
15
16//===----------------------------------------------------------------------===//
17// ValueLatticeElement
18//===----------------------------------------------------------------------===//
19
20namespace llvm {
21
22class 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///
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 {
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
109public:
110 /// Struct to control some aspects related to merging constant ranges.
112 /// The merge value may include undef.
114
115 /// Handle repeatedly extending a range by going to overdefined after a
116 /// number of steps.
118
119 /// The number of allowed widening steps (including setting the range
120 /// initially).
122
124
126 unsigned MaxWidenSteps = 1)
129
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
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
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
192 destroy();
193 new (this) ValueLatticeElement(Other);
194 return *this;
195 }
196
198 destroy();
199 new (this) ValueLatticeElement(std::move(Other));
200 return *this;
201 }
202
205 if (isa<UndefValue>(C))
206 Res.markUndef();
207 else
208 Res.markConstant(C);
209 return Res;
210 }
213 assert(!isa<UndefValue>(C) && "!= undef is not supported");
214 Res.markNotConstant(C);
215 return Res;
216 }
218 bool MayIncludeUndef = false) {
219 if (CR.isFullSet())
220 return getOverdefined();
221
222 if (CR.isEmptySet()) {
224 if (MayIncludeUndef)
225 Res.markUndef();
226 return Res;
227 }
228
230 Res.markConstantRange(std::move(CR),
231 MergeOptions().setMayIncludeUndef(MayIncludeUndef));
232 return Res;
233 }
236 Res.markOverdefined();
237 return Res;
238 }
239
240 bool isUndef() const { return Tag == undef; }
241 bool isUnknown() const { return Tag == unknown; }
242 bool isUnknownOrUndef() const { return Tag == unknown || Tag == undef; }
243 bool isConstant() const { return Tag == constant; }
244 bool isNotConstant() const { return Tag == notconstant; }
246 return Tag == constantrange_including_undef;
247 }
248 /// Returns true if this value is a constant range. Use \p UndefAllowed to
249 /// exclude non-singleton constant ranges that may also be undef. Note that
250 /// this function also returns true if the range may include undef, but only
251 /// contains a single element. In that case, it can be replaced by a constant.
252 bool isConstantRange(bool UndefAllowed = true) const {
253 return Tag == constantrange || (Tag == constantrange_including_undef &&
254 (UndefAllowed || Range.isSingleElement()));
255 }
256 bool isOverdefined() const { return Tag == overdefined; }
257
259 assert(isConstant() && "Cannot get the constant of a non-constant!");
260 return ConstVal;
261 }
262
264 assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
265 return ConstVal;
266 }
267
268 /// Returns the constant range for this value. Use \p UndefAllowed to exclude
269 /// non-singleton constant ranges that may also be undef. Note that this
270 /// function also returns a range if the range may include undef, but only
271 /// contains a single element. In that case, it can be replaced by a constant.
272 const ConstantRange &getConstantRange(bool UndefAllowed = true) const {
273 assert(isConstantRange(UndefAllowed) &&
274 "Cannot get the constant-range of a non-constant-range!");
275 return Range;
276 }
277
278 std::optional<APInt> asConstantInteger() const {
279 if (isConstant() && isa<ConstantInt>(getConstant())) {
280 return cast<ConstantInt>(getConstant())->getValue();
281 } else if (isConstantRange() && getConstantRange().isSingleElement()) {
283 }
284 return std::nullopt;
285 }
286
288 if (isOverdefined())
289 return false;
290 destroy();
291 Tag = overdefined;
292 return true;
293 }
294
295 bool markUndef() {
296 if (isUndef())
297 return false;
298
299 assert(isUnknown());
300 Tag = undef;
301 return true;
302 }
303
304 bool markConstant(Constant *V, bool MayIncludeUndef = false) {
305 if (isa<UndefValue>(V))
306 return markUndef();
307
308 if (isConstant()) {
309 assert(getConstant() == V && "Marking constant with different value");
310 return false;
311 }
312
313 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
314 return markConstantRange(
315 ConstantRange(CI->getValue()),
316 MergeOptions().setMayIncludeUndef(MayIncludeUndef));
317
318 assert(isUnknown() || isUndef());
319 Tag = constant;
320 ConstVal = V;
321 return true;
322 }
323
325 assert(V && "Marking constant with NULL");
326 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
327 return markConstantRange(
328 ConstantRange(CI->getValue() + 1, CI->getValue()));
329
330 if (isa<UndefValue>(V))
331 return false;
332
333 if (isNotConstant()) {
334 assert(getNotConstant() == V && "Marking !constant with different value");
335 return false;
336 }
337
338 assert(isUnknown());
339 Tag = notconstant;
340 ConstVal = V;
341 return true;
342 }
343
344 /// Mark the object as constant range with \p NewR. If the object is already a
345 /// constant range, nothing changes if the existing range is equal to \p
346 /// NewR and the tag. Otherwise \p NewR must be a superset of the existing
347 /// range or the object must be undef. The tag is set to
348 /// constant_range_including_undef if either the existing value or the new
349 /// range may include undef.
351 MergeOptions Opts = MergeOptions()) {
352 assert(!NewR.isEmptySet() && "should only be called for non-empty sets");
353
354 if (NewR.isFullSet())
355 return markOverdefined();
356
357 ValueLatticeElementTy OldTag = Tag;
358 ValueLatticeElementTy NewTag =
359 (isUndef() || isConstantRangeIncludingUndef() || Opts.MayIncludeUndef)
360 ? constantrange_including_undef
361 : constantrange;
362 if (isConstantRange()) {
363 Tag = NewTag;
364 if (getConstantRange() == NewR)
365 return Tag != OldTag;
366
367 // Simple form of widening. If a range is extended multiple times, go to
368 // overdefined.
369 if (Opts.CheckWiden && ++NumRangeExtensions > Opts.MaxWidenSteps)
370 return markOverdefined();
371
373 "Existing range must be a subset of NewR");
374 Range = std::move(NewR);
375 return true;
376 }
377
378 assert(isUnknown() || isUndef());
379
380 NumRangeExtensions = 0;
381 Tag = NewTag;
382 new (&Range) ConstantRange(std::move(NewR));
383 return true;
384 }
385
386 /// Updates this object to approximate both this object and RHS. Returns
387 /// true if this object has been changed.
389 MergeOptions Opts = MergeOptions()) {
390 if (RHS.isUnknown() || isOverdefined())
391 return false;
392 if (RHS.isOverdefined()) {
394 return true;
395 }
396
397 if (isUndef()) {
398 assert(!RHS.isUnknown());
399 if (RHS.isUndef())
400 return false;
401 if (RHS.isConstant())
402 return markConstant(RHS.getConstant(), true);
403 if (RHS.isConstantRange())
404 return markConstantRange(RHS.getConstantRange(true),
405 Opts.setMayIncludeUndef());
406 return markOverdefined();
407 }
408
409 if (isUnknown()) {
410 assert(!RHS.isUnknown() && "Unknow RHS should be handled earlier");
411 *this = RHS;
412 return true;
413 }
414
415 if (isConstant()) {
416 if (RHS.isConstant() && getConstant() == RHS.getConstant())
417 return false;
418 if (RHS.isUndef())
419 return false;
421 return true;
422 }
423
424 if (isNotConstant()) {
425 if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant())
426 return false;
428 return true;
429 }
430
431 auto OldTag = Tag;
432 assert(isConstantRange() && "New ValueLattice type?");
433 if (RHS.isUndef()) {
434 Tag = constantrange_including_undef;
435 return OldTag != Tag;
436 }
437
438 if (!RHS.isConstantRange()) {
439 // We can get here if we've encountered a constantexpr of integer type
440 // and merge it with a constantrange.
442 return true;
443 }
444
445 ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange());
446 return markConstantRange(
447 std::move(NewR),
448 Opts.setMayIncludeUndef(RHS.isConstantRangeIncludingUndef()));
449 }
450
451 // Compares this symbolic value with Other using Pred and returns either
452 /// true, false or undef constants, or nullptr if the comparison cannot be
453 /// evaluated.
456 const DataLayout &DL) const;
457
458 unsigned getNumRangeExtensions() const { return NumRangeExtensions; }
459 void setNumRangeExtensions(unsigned N) { NumRangeExtensions = N; }
460};
461
462static_assert(sizeof(ValueLatticeElement) <= 40,
463 "size of ValueLatticeElement changed unexpectedly");
464
465raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);
466} // end namespace llvm
467#endif
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file contains the declarations for the subclasses of Constant, which represent the different fla...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
Value * RHS
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:711
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
This class represents a range of values.
Definition: ConstantRange.h:47
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
bool isEmptySet() const
Return true if this set contains no members.
bool isSingleElement() const
Return true if this set contains exactly one member.
ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
This is an important base class in LLVM.
Definition: Constant.h:41
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
This class represents lattice values for constants.
Definition: ValueLattice.h:29
bool markNotConstant(Constant *V)
Definition: ValueLattice.h:324
static ValueLatticeElement getRange(ConstantRange CR, bool MayIncludeUndef=false)
Definition: ValueLattice.h:217
Constant * getCompare(CmpInst::Predicate Pred, Type *Ty, const ValueLatticeElement &Other, const DataLayout &DL) const
true, false or undef constants, or nullptr if the comparison cannot be evaluated.
bool isConstantRangeIncludingUndef() const
Definition: ValueLattice.h:245
ValueLatticeElement(const ValueLatticeElement &Other)
Definition: ValueLattice.h:152
static ValueLatticeElement getNot(Constant *C)
Definition: ValueLattice.h:211
std::optional< APInt > asConstantInteger() const
Definition: ValueLattice.h:278
ValueLatticeElement & operator=(const ValueLatticeElement &Other)
Definition: ValueLattice.h:191
ValueLatticeElement(ValueLatticeElement &&Other)
Definition: ValueLattice.h:171
void setNumRangeExtensions(unsigned N)
Definition: ValueLattice.h:459
const ConstantRange & getConstantRange(bool UndefAllowed=true) const
Returns the constant range for this value.
Definition: ValueLattice.h:272
bool isConstantRange(bool UndefAllowed=true) const
Returns true if this value is a constant range.
Definition: ValueLattice.h:252
static ValueLatticeElement get(Constant *C)
Definition: ValueLattice.h:203
unsigned getNumRangeExtensions() const
Definition: ValueLattice.h:458
Constant * getNotConstant() const
Definition: ValueLattice.h:263
bool isUnknownOrUndef() const
Definition: ValueLattice.h:242
Constant * getConstant() const
Definition: ValueLattice.h:258
bool mergeIn(const ValueLatticeElement &RHS, MergeOptions Opts=MergeOptions())
Updates this object to approximate both this object and RHS.
Definition: ValueLattice.h:388
ValueLatticeElement & operator=(ValueLatticeElement &&Other)
Definition: ValueLattice.h:197
bool markConstant(Constant *V, bool MayIncludeUndef=false)
Definition: ValueLattice.h:304
static ValueLatticeElement getOverdefined()
Definition: ValueLattice.h:234
bool markConstantRange(ConstantRange NewR, MergeOptions Opts=MergeOptions())
Mark the object as constant range with NewR.
Definition: ValueLattice.h:350
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Other
Any other memory.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:292
#define N
Struct to control some aspects related to merging constant ranges.
Definition: ValueLattice.h:111
bool MayIncludeUndef
The merge value may include undef.
Definition: ValueLattice.h:113
MergeOptions & setMayIncludeUndef(bool V=true)
Definition: ValueLattice.h:130
bool CheckWiden
Handle repeatedly extending a range by going to overdefined after a number of steps.
Definition: ValueLattice.h:117
MergeOptions & setMaxWidenSteps(unsigned Steps=1)
Definition: ValueLattice.h:140
MergeOptions & setCheckWiden(bool V=true)
Definition: ValueLattice.h:135
MergeOptions(bool MayIncludeUndef, bool CheckWiden, unsigned MaxWidenSteps=1)
Definition: ValueLattice.h:125
unsigned MaxWidenSteps
The number of allowed widening steps (including setting the range initially).
Definition: ValueLattice.h:121