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/ConstantRange.h"
13#include "llvm/IR/Constants.h"
14//
15//===----------------------------------------------------------------------===//
16//                               ValueLatticeElement
17//===----------------------------------------------------------------------===//
18
19/// This class represents lattice values for constants.
20///
21/// FIXME: This is basically just for bringup, this can be made a lot more rich
22/// in the future.
23///
24
25namespace llvm {
26class ValueLatticeElement {
27  enum ValueLatticeElementTy {
28    /// This Value has no known value yet.  As a result, this implies the
29    /// producing instruction is dead.  Caution: We use this as the starting
30    /// state in our local meet rules.  In this usage, it's taken to mean
31    /// "nothing known yet".
32    /// Transition to any other state allowed.
33    unknown,
34
35    /// This Value is an UndefValue constant or produces undef. Undefined values
36    /// can be merged with constants (or single element constant ranges),
37    /// assuming all uses of the result will be replaced.
38    /// Transition allowed to the following states:
39    ///  constant
40    ///  constantrange_including_undef
41    ///  overdefined
42    undef,
43
44    /// This Value has a specific constant value.  The constant cannot be undef.
45    /// (For constant integers, constantrange is used instead. Integer typed
46    /// constantexprs can appear as constant.) Note that the constant state
47    /// can be reached by merging undef & constant states.
48    /// Transition allowed to the following states:
49    ///  overdefined
50    constant,
51
52    /// This Value is known to not have the specified value. (For constant
53    /// integers, constantrange is used instead.  As above, integer typed
54    /// constantexprs can appear here.)
55    /// Transition allowed to the following states:
56    ///  overdefined
57    notconstant,
58
59    /// The Value falls within this range. (Used only for integer typed values.)
60    /// Transition allowed to the following states:
61    ///  constantrange (new range must be a superset of the existing range)
62    ///  constantrange_including_undef
63    ///  overdefined
64    constantrange,
65
66    /// This Value falls within this range, but also may be undef.
67    /// Merging it with other constant ranges results in
68    /// constantrange_including_undef.
69    /// Transition allowed to the following states:
70    ///  overdefined
71    constantrange_including_undef,
72
73    /// We can not precisely model the dynamic values this value might take.
74    /// No transitions are allowed after reaching overdefined.
75    overdefined,
76  };
77
78  ValueLatticeElementTy Tag : 8;
79  /// Number of times a constant range has been extended with widening enabled.
80  unsigned NumRangeExtensions : 8;
81
82  /// The union either stores a pointer to a constant or a constant range,
83  /// associated to the lattice element. We have to ensure that Range is
84  /// initialized or destroyed when changing state to or from constantrange.
85  union {
86    Constant *ConstVal;
87    ConstantRange Range;
88  };
89
90  /// Destroy contents of lattice value, without destructing the object.
91  void destroy() {
92    switch (Tag) {
93    case overdefined:
94    case unknown:
95    case undef:
96    case constant:
97    case notconstant:
98      break;
99    case constantrange_including_undef:
100    case constantrange:
101      Range.~ConstantRange();
102      break;
103    };
104  }
105
106public:
107  /// Struct to control some aspects related to merging constant ranges.
108  struct MergeOptions {
109    /// The merge value may include undef.
110    bool MayIncludeUndef;
111
112    /// Handle repeatedly extending a range by going to overdefined after a
113    /// number of steps.
114    bool CheckWiden;
115
116    /// The number of allowed widening steps (including setting the range
117    /// initially).
118    unsigned MaxWidenSteps;
119
120    MergeOptions() : MergeOptions(false, false) {}
121
122    MergeOptions(bool MayIncludeUndef, bool CheckWiden,
123                 unsigned MaxWidenSteps = 1)
124        : MayIncludeUndef(MayIncludeUndef), CheckWiden(CheckWiden),
125          MaxWidenSteps(MaxWidenSteps) {}
126
127    MergeOptions &setMayIncludeUndef(bool V = true) {
128      MayIncludeUndef = V;
129      return *this;
130    }
131
132    MergeOptions &setCheckWiden(bool V = true) {
133      CheckWiden = V;
134      return *this;
135    }
136
137    MergeOptions &setMaxWidenSteps(unsigned Steps = 1) {
138      CheckWiden = true;
139      MaxWidenSteps = Steps;
140      return *this;
141    }
142  };
143
144  // ConstVal and Range are initialized on-demand.
145  ValueLatticeElement() : Tag(unknown), NumRangeExtensions(0) {}
146
147  ~ValueLatticeElement() { destroy(); }
148
149  ValueLatticeElement(const ValueLatticeElement &Other)
150      : Tag(Other.Tag), NumRangeExtensions(0) {
151    switch (Other.Tag) {
152    case constantrange:
153    case constantrange_including_undef:
154      new (&Range) ConstantRange(Other.Range);
155      NumRangeExtensions = Other.NumRangeExtensions;
156      break;
157    case constant:
158    case notconstant:
159      ConstVal = Other.ConstVal;
160      break;
161    case overdefined:
162    case unknown:
163    case undef:
164      break;
165    }
166  }
167
168  ValueLatticeElement(ValueLatticeElement &&Other)
169      : Tag(Other.Tag), NumRangeExtensions(0) {
170    switch (Other.Tag) {
171    case constantrange:
172    case constantrange_including_undef:
173      new (&Range) ConstantRange(std::move(Other.Range));
174      NumRangeExtensions = Other.NumRangeExtensions;
175      break;
176    case constant:
177    case notconstant:
178      ConstVal = Other.ConstVal;
179      break;
180    case overdefined:
181    case unknown:
182    case undef:
183      break;
184    }
185    Other.Tag = unknown;
186  }
187
188  ValueLatticeElement &operator=(const ValueLatticeElement &Other) {
189    destroy();
190    new (this) ValueLatticeElement(Other);
191    return *this;
192  }
193
194  ValueLatticeElement &operator=(ValueLatticeElement &&Other) {
195    destroy();
196    new (this) ValueLatticeElement(std::move(Other));
197    return *this;
198  }
199
200  static ValueLatticeElement get(Constant *C) {
201    ValueLatticeElement Res;
202    if (isa<UndefValue>(C))
203      Res.markUndef();
204    else
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  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 None;
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) const {
453    if (isUnknownOrUndef() || Other.isUnknownOrUndef())
454      return UndefValue::get(Ty);
455
456    if (isConstant() && Other.isConstant())
457      return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant());
458
459    // Integer constants are represented as ConstantRanges with single
460    // elements.
461    if (!isConstantRange() || !Other.isConstantRange())
462      return nullptr;
463
464    const auto &CR = getConstantRange();
465    const auto &OtherCR = Other.getConstantRange();
466    if (ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR))
467      return ConstantInt::getTrue(Ty);
468    if (ConstantRange::makeSatisfyingICmpRegion(
469            CmpInst::getInversePredicate(Pred), OtherCR)
470            .contains(CR))
471      return ConstantInt::getFalse(Ty);
472
473    return nullptr;
474  }
475
476  unsigned getNumRangeExtensions() const { return NumRangeExtensions; }
477  void setNumRangeExtensions(unsigned N) { NumRangeExtensions = N; }
478};
479
480static_assert(sizeof(ValueLatticeElement) <= 40,
481              "size of ValueLatticeElement changed unexpectedly");
482
483raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);
484} // end namespace llvm
485#endif
486