1 //===- ValueLattice.h - Value constraint analysis ---------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef LLVM_ANALYSIS_VALUELATTICE_H
11 #define LLVM_ANALYSIS_VALUELATTICE_H
13 #include "llvm/IR/ConstantRange.h"
14 #include "llvm/IR/Constants.h"
16 //===----------------------------------------------------------------------===//
17 // ValueLatticeElement
18 //===----------------------------------------------------------------------===//
20 /// This class represents lattice values for constants.
22 /// FIXME: This is basically just for bringup, this can be made a lot more rich
27 class 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".
35 /// This Value has a specific constant value. (For constant integers,
36 /// constantrange is used instead. Integer typed constantexprs can appear
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.)
45 /// The Value falls within this range. (Used only for integer typed values.)
48 /// We can not precisely model the dynamic values this value might take.
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;
59 ValueLatticeElement() : Tag(undefined), Val(nullptr), Range(1, true) {}
61 static ValueLatticeElement get(Constant *C) {
62 ValueLatticeElement Res;
63 if (!isa<UndefValue>(C))
67 static ValueLatticeElement getNot(Constant *C) {
68 ValueLatticeElement Res;
69 if (!isa<UndefValue>(C))
70 Res.markNotConstant(C);
73 static ValueLatticeElement getRange(ConstantRange CR) {
74 ValueLatticeElement Res;
75 Res.markConstantRange(std::move(CR));
78 static ValueLatticeElement getOverdefined() {
79 ValueLatticeElement Res;
80 Res.markOverdefined();
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; }
90 Constant *getConstant() const {
91 assert(isConstant() && "Cannot get the constant of a non-constant!");
95 Constant *getNotConstant() const {
96 assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
100 const ConstantRange &getConstantRange() const {
101 assert(isConstantRange() &&
102 "Cannot get the constant-range of a non-constant-range!");
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();
116 void markOverdefined() {
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()));
128 if (isa<UndefValue>(V))
131 assert((!isConstant() || getConstant() == V) &&
132 "Marking constant with different value");
133 assert(isUndefined());
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()));
144 if (isa<UndefValue>(V))
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());
156 void markConstantRange(ConstantRange NewR) {
157 if (isConstantRange()) {
158 if (NewR.isEmptySet())
161 Range = std::move(NewR);
166 assert(isUndefined());
167 if (NewR.isEmptySet())
171 Range = std::move(NewR);
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())
181 if (RHS.isOverdefined()) {
188 return !RHS.isUndefined();
192 if (RHS.isConstant() && Val == RHS.Val)
198 if (isNotConstant()) {
199 if (RHS.isNotConstant() && Val == RHS.Val)
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.
212 ConstantRange NewR = Range.unionWith(RHS.getConstantRange());
213 if (NewR.isFullSet())
216 markConstantRange(std::move(NewR));
220 ConstantInt *getConstantInt() const {
221 assert(isConstant() && isa<ConstantInt>(getConstant()) &&
222 "No integer constant");
223 return cast<ConstantInt>(getConstant());
226 bool satisfiesPredicate(CmpInst::Predicate Pred,
227 const ValueLatticeElement &Other) const {
228 // TODO: share with LVI getPredicateResult.
230 if (isUndefined() || Other.isUndefined())
233 if (isConstant() && Other.isConstant() && Pred == CmpInst::FCMP_OEQ)
234 return getConstant() == Other.getConstant();
236 // Integer constants are represented as ConstantRanges with single
238 if (!isConstantRange() || !Other.isConstantRange())
241 const auto &CR = getConstantRange();
242 const auto &OtherCR = Other.getConstantRange();
243 return ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR);
247 raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);
249 } // end namespace llvm