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(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(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(std::move(CR),
228                          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>(getConstant())) {
277      return cast<ConstantInt>(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>(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
321  bool markNotConstant(Constant *V) {
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.
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(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;
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(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.
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