LLVM 19.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 Res.markConstant(C);
206 return Res;
207 }
210 assert(!isa<UndefValue>(C) && "!= undef is not supported");
211 Res.markNotConstant(C);
212 return Res;
213 }
215 bool MayIncludeUndef = false) {
216 if (CR.isFullSet())
217 return getOverdefined();
218
219 if (CR.isEmptySet()) {
221 if (MayIncludeUndef)
222 Res.markUndef();
223 return Res;
224 }
225
227 Res.markConstantRange(std::move(CR),
228 MergeOptions().setMayIncludeUndef(MayIncludeUndef));
229 return Res;
230 }
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; }
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
256 assert(isConstant() && "Cannot get the constant of a non-constant!");
257 return ConstVal;
258 }
259
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>(getConstant())) {
277 return cast<ConstantInt>(getConstant())->getValue();
278 } else if (isConstantRange() && getConstantRange().isSingleElement()) {
280 }
281 return std::nullopt;
282 }
283
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>(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>(V))
311 return markConstantRange(
312 ConstantRange(CI->getValue()),
313 MergeOptions().setMayIncludeUndef(MayIncludeUndef));
314
315 assert(isUnknown() || isUndef());
316 Tag = constant;
317 ConstVal = V;
318 return true;
319 }
320
322 assert(V && "Marking constant with NULL");
323 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
324 return markConstantRange(
325 ConstantRange(CI->getValue() + 1, CI->getValue()));
326
327 if (isa<UndefValue>(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.
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
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.
386 MergeOptions Opts = MergeOptions()) {
387 if (RHS.isUnknown() || isOverdefined())
388 return false;
389 if (RHS.isOverdefined()) {
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(RHS.getConstant(), true);
400 if (RHS.isConstantRange())
401 return markConstantRange(RHS.getConstantRange(true),
402 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;
418 return true;
419 }
420
421 if (isNotConstant()) {
422 if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant())
423 return false;
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.
439 return true;
440 }
441
442 ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange());
443 return markConstantRange(
444 std::move(NewR),
445 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.
453 const DataLayout &DL) const;
454
455 unsigned getNumRangeExtensions() const { return NumRangeExtensions; }
456 void setNumRangeExtensions(unsigned N) { NumRangeExtensions = N; }
457};
458
459static_assert(sizeof(ValueLatticeElement) <= 40,
460 "size of ValueLatticeElement changed unexpectedly");
461
462raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);
463} // end namespace llvm
464#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:993
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
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:321
static ValueLatticeElement getRange(ConstantRange CR, bool MayIncludeUndef=false)
Definition: ValueLattice.h:214
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:242
ValueLatticeElement(const ValueLatticeElement &Other)
Definition: ValueLattice.h:152
static ValueLatticeElement getNot(Constant *C)
Definition: ValueLattice.h:208
std::optional< APInt > asConstantInteger() const
Definition: ValueLattice.h:275
ValueLatticeElement & operator=(const ValueLatticeElement &Other)
Definition: ValueLattice.h:191
ValueLatticeElement(ValueLatticeElement &&Other)
Definition: ValueLattice.h:171
void setNumRangeExtensions(unsigned N)
Definition: ValueLattice.h:456
const ConstantRange & getConstantRange(bool UndefAllowed=true) const
Returns the constant range for this value.
Definition: ValueLattice.h:269
bool isConstantRange(bool UndefAllowed=true) const
Returns true if this value is a constant range.
Definition: ValueLattice.h:249
static ValueLatticeElement get(Constant *C)
Definition: ValueLattice.h:203
unsigned getNumRangeExtensions() const
Definition: ValueLattice.h:455
Constant * getNotConstant() const
Definition: ValueLattice.h:260
bool isUnknownOrUndef() const
Definition: ValueLattice.h:239
Constant * getConstant() const
Definition: ValueLattice.h:255
bool mergeIn(const ValueLatticeElement &RHS, MergeOptions Opts=MergeOptions())
Updates this object to approximate both this object and RHS.
Definition: ValueLattice.h:385
ValueLatticeElement & operator=(ValueLatticeElement &&Other)
Definition: ValueLattice.h:197
bool markConstant(Constant *V, bool MayIncludeUndef=false)
Definition: ValueLattice.h:301
static ValueLatticeElement getOverdefined()
Definition: ValueLattice.h:231
bool markConstantRange(ConstantRange NewR, MergeOptions Opts=MergeOptions())
Mark the object as constant range with NewR.
Definition: ValueLattice.h:347
@ 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:293
#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