1//===- ValueLattice.h - Value constraint analysis ---------------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef LLVM_ANALYSIS_VALUELATTICE_H
11#define LLVM_ANALYSIS_VALUELATTICE_H
12
13#include "llvm/IR/ConstantRange.h"
14#include "llvm/IR/Constants.h"
15//
16//===----------------------------------------------------------------------===//
17//                               ValueLatticeElement
18//===----------------------------------------------------------------------===//
19
20/// This class represents lattice values for constants.
21///
22/// FIXME: This is basically just for bringup, this can be made a lot more rich
23/// in the future.
24///
25
26namespace llvm {
27class ValueLatticeElement {
28  enum ValueLatticeElementTy {
29    /// This Value has no known value yet.  As a result, this implies the
30    /// producing instruction is dead.  Caution: We use this as the starting
31    /// state in our local meet rules.  In this usage, it's taken to mean
32    /// "nothing known yet".
33    undefined,
34
35    /// This Value has a specific constant value.  (For constant integers,
36    /// constantrange is used instead.  Integer typed constantexprs can appear
37    /// as constant.)
38    constant,
39
40    /// This Value is known to not have the specified value.  (For constant
41    /// integers, constantrange is used instead.  As above, integer typed
42    /// constantexprs can appear here.)
43    notconstant,
44
45    /// The Value falls within this range. (Used only for integer typed values.)
46    constantrange,
47
48    /// We can not precisely model the dynamic values this value might take.
49    overdefined
50  };
51
52  /// Val: This stores the current lattice value along with the Constant* for
53  /// the constant if this is a 'constant' or 'notconstant' value.
54  ValueLatticeElementTy Tag;
55  Constant *Val;
56  ConstantRange Range;
57
58public:
59  ValueLatticeElement() : Tag(undefined), Val(nullptr), Range(1, true) {}
60
61  static ValueLatticeElement get(Constant *C) {
62    ValueLatticeElement Res;
63    if (!isa<UndefValue>(C))
64      Res.markConstant(C);
65    return Res;
66  }
67  static ValueLatticeElement getNot(Constant *C) {
68    ValueLatticeElement Res;
69    if (!isa<UndefValue>(C))
70      Res.markNotConstant(C);
71    return Res;
72  }
73  static ValueLatticeElement getRange(ConstantRange CR) {
74    ValueLatticeElement Res;
75    Res.markConstantRange(std::move(CR));
76    return Res;
77  }
78  static ValueLatticeElement getOverdefined() {
79    ValueLatticeElement Res;
80    Res.markOverdefined();
81    return Res;
82  }
83
84  bool isUndefined() const { return Tag == undefined; }
85  bool isConstant() const { return Tag == constant; }
86  bool isNotConstant() const { return Tag == notconstant; }
87  bool isConstantRange() const { return Tag == constantrange; }
88  bool isOverdefined() const { return Tag == overdefined; }
89
90  Constant *getConstant() const {
91    assert(isConstant() && "Cannot get the constant of a non-constant!");
92    return Val;
93  }
94
95  Constant *getNotConstant() const {
96    assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
97    return Val;
98  }
99
100  const ConstantRange &getConstantRange() const {
101    assert(isConstantRange() &&
102           "Cannot get the constant-range of a non-constant-range!");
103    return Range;
104  }
105
106  Optional<APInt> asConstantInteger() const {
107    if (isConstant() && isa<ConstantInt>(Val)) {
108      return cast<ConstantInt>(Val)->getValue();
109    } else if (isConstantRange() && Range.isSingleElement()) {
110      return *Range.getSingleElement();
111    }
112    return None;
113  }
114
115private:
116  void markOverdefined() {
117    if (isOverdefined())
118      return;
119    Tag = overdefined;
120  }
121
122  void markConstant(Constant *V) {
123    assert(V && "Marking constant with NULL");
124    if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
125      markConstantRange(ConstantRange(CI->getValue()));
126      return;
127    }
128    if (isa<UndefValue>(V))
129      return;
130
131    assert((!isConstant() || getConstant() == V) &&
132           "Marking constant with different value");
133    assert(isUndefined());
134    Tag = constant;
135    Val = V;
136  }
137
138  void markNotConstant(Constant *V) {
139    assert(V && "Marking constant with NULL");
140    if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
141      markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()));
142      return;
143    }
144    if (isa<UndefValue>(V))
145      return;
146
147    assert((!isConstant() || getConstant() != V) &&
148           "Marking constant !constant with same value");
149    assert((!isNotConstant() || getNotConstant() == V) &&
150           "Marking !constant with different value");
151    assert(isUndefined() || isConstant());
152    Tag = notconstant;
153    Val = V;
154  }
155
156  void markConstantRange(ConstantRange NewR) {
157    if (isConstantRange()) {
158      if (NewR.isEmptySet())
159        markOverdefined();
160      else {
161        Range = std::move(NewR);
162      }
163      return;
164    }
165
166    assert(isUndefined());
167    if (NewR.isEmptySet())
168      markOverdefined();
169    else {
170      Tag = constantrange;
171      Range = std::move(NewR);
172    }
173  }
174
175public:
176  /// Updates this object to approximate both this object and RHS. Returns
177  /// true if this object has been changed.
178  bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
179    if (RHS.isUndefined() || isOverdefined())
180      return false;
181    if (RHS.isOverdefined()) {
182      markOverdefined();
183      return true;
184    }
185
186    if (isUndefined()) {
187      *this = RHS;
188      return !RHS.isUndefined();
189    }
190
191    if (isConstant()) {
192      if (RHS.isConstant() && Val == RHS.Val)
193        return false;
194      markOverdefined();
195      return true;
196    }
197
198    if (isNotConstant()) {
199      if (RHS.isNotConstant() && Val == RHS.Val)
200        return false;
201      markOverdefined();
202      return true;
203    }
204
205    assert(isConstantRange() && "New ValueLattice type?");
206    if (!RHS.isConstantRange()) {
207      // We can get here if we've encountered a constantexpr of integer type
208      // and merge it with a constantrange.
209      markOverdefined();
210      return true;
211    }
212    ConstantRange NewR = Range.unionWith(RHS.getConstantRange());
213    if (NewR.isFullSet())
214      markOverdefined();
215    else
216      markConstantRange(std::move(NewR));
217    return true;
218  }
219
220  ConstantInt *getConstantInt() const {
221    assert(isConstant() && isa<ConstantInt>(getConstant()) &&
222           "No integer constant");
223    return cast<ConstantInt>(getConstant());
224  }
225
226  bool satisfiesPredicate(CmpInst::Predicate Pred,
227                          const ValueLatticeElement &Other) const {
228    // TODO: share with LVI getPredicateResult.
229
230    if (isUndefined() || Other.isUndefined())
231      return true;
232
233    if (isConstant() && Other.isConstant() && Pred == CmpInst::FCMP_OEQ)
234      return getConstant() == Other.getConstant();
235
236    // Integer constants are represented as ConstantRanges with single
237    // elements.
238    if (!isConstantRange() || !Other.isConstantRange())
239      return false;
240
241    const auto &CR = getConstantRange();
242    const auto &OtherCR = Other.getConstantRange();
243    return ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR);
244  }
245};
246
247raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);
248
249} // end namespace llvm
250#endif
251