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
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///
29class 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
109public:
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
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
465

source code of llvm/include/llvm/Analysis/ValueLattice.h