1 //===- ValueLattice.h - Value constraint analysis ---------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 #ifndef LLVM_ANALYSIS_VALUELATTICE_H
10 #define LLVM_ANALYSIS_VALUELATTICE_H
12 #include "llvm/IR/ConstantRange.h"
13 #include "llvm/IR/Constants.h"
15 //===----------------------------------------------------------------------===//
16 // ValueLatticeElement
17 //===----------------------------------------------------------------------===//
19 /// This class represents lattice values for constants.
21 /// FIXME: This is basically just for bringup, this can be made a lot more rich
26 class 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".
34 /// This Value has a specific constant value. (For constant integers,
35 /// constantrange is used instead. Integer typed constantexprs can appear
39 /// This Value is known to not have the specified value. (For constant
40 /// integers, constantrange is used instead. As above, integer typed
41 /// constantexprs can appear here.)
44 /// The Value falls within this range. (Used only for integer typed values.)
47 /// We can not precisely model the dynamic values this value might take.
51 ValueLatticeElementTy Tag;
53 /// The union either stores a pointer to a constant or a constant range,
54 /// associated to the lattice element. We have to ensure that Range is
55 /// initialized or destroyed when changing state to or from constantrange.
62 // Const and Range are initialized on-demand.
63 ValueLatticeElement() : Tag(undefined) {}
65 /// Custom destructor to ensure Range is properly destroyed, when the object
67 ~ValueLatticeElement() {
75 Range.~ConstantRange();
80 /// Custom copy constructor, to ensure Range gets initialized when
81 /// copying a constant range lattice element.
82 ValueLatticeElement(const ValueLatticeElement &Other) : Tag(undefined) {
86 /// Custom assignment operator, to ensure Range gets initialized when
87 /// assigning a constant range lattice element.
88 ValueLatticeElement &operator=(const ValueLatticeElement &Other) {
89 // If we change the state of this from constant range to non constant range,
91 if (isConstantRange() && !Other.isConstantRange())
92 Range.~ConstantRange();
94 // If we change the state of this from a valid ConstVal to another a state
95 // without a valid ConstVal, zero the pointer.
96 if ((isConstant() || isNotConstant()) && !Other.isConstant() &&
97 !Other.isNotConstant())
102 if (!isConstantRange())
103 new (&Range) ConstantRange(Other.Range);
109 ConstVal = Other.ConstVal;
119 static ValueLatticeElement get(Constant *C) {
120 ValueLatticeElement Res;
121 if (!isa<UndefValue>(C))
125 static ValueLatticeElement getNot(Constant *C) {
126 ValueLatticeElement Res;
127 if (!isa<UndefValue>(C))
128 Res.markNotConstant(C);
131 static ValueLatticeElement getRange(ConstantRange CR) {
132 ValueLatticeElement Res;
133 Res.markConstantRange(std::move(CR));
136 static ValueLatticeElement getOverdefined() {
137 ValueLatticeElement Res;
138 Res.markOverdefined();
142 bool isUndefined() const { return Tag == undefined; }
143 bool isConstant() const { return Tag == constant; }
144 bool isNotConstant() const { return Tag == notconstant; }
145 bool isConstantRange() const { return Tag == constantrange; }
146 bool isOverdefined() const { return Tag == overdefined; }
148 Constant *getConstant() const {
149 assert(isConstant() && "Cannot get the constant of a non-constant!");
153 Constant *getNotConstant() const {
154 assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
158 const ConstantRange &getConstantRange() const {
159 assert(isConstantRange() &&
160 "Cannot get the constant-range of a non-constant-range!");
164 Optional<APInt> asConstantInteger() const {
165 if (isConstant() && isa<ConstantInt>(getConstant())) {
166 return cast<ConstantInt>(getConstant())->getValue();
167 } else if (isConstantRange() && getConstantRange().isSingleElement()) {
168 return *getConstantRange().getSingleElement();
174 void markOverdefined() {
177 if (isConstant() || isNotConstant())
179 if (isConstantRange())
180 Range.~ConstantRange();
184 void markConstant(Constant *V) {
185 assert(V && "Marking constant with NULL");
186 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
187 markConstantRange(ConstantRange(CI->getValue()));
190 if (isa<UndefValue>(V))
193 assert((!isConstant() || getConstant() == V) &&
194 "Marking constant with different value");
195 assert(isUndefined());
200 void markNotConstant(Constant *V) {
201 assert(V && "Marking constant with NULL");
202 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
203 markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()));
206 if (isa<UndefValue>(V))
209 assert((!isConstant() || getConstant() != V) &&
210 "Marking constant !constant with same value");
211 assert((!isNotConstant() || getNotConstant() == V) &&
212 "Marking !constant with different value");
213 assert(isUndefined() || isConstant());
218 void markConstantRange(ConstantRange NewR) {
219 if (isConstantRange()) {
220 if (NewR.isEmptySet())
223 Range = std::move(NewR);
228 assert(isUndefined());
229 if (NewR.isEmptySet())
233 new (&Range) ConstantRange(std::move(NewR));
238 /// Updates this object to approximate both this object and RHS. Returns
239 /// true if this object has been changed.
240 bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
241 if (RHS.isUndefined() || isOverdefined())
243 if (RHS.isOverdefined()) {
250 return !RHS.isUndefined();
254 if (RHS.isConstant() && getConstant() == RHS.getConstant())
260 if (isNotConstant()) {
261 if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant())
267 assert(isConstantRange() && "New ValueLattice type?");
268 if (!RHS.isConstantRange()) {
269 // We can get here if we've encountered a constantexpr of integer type
270 // and merge it with a constantrange.
274 ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange());
275 if (NewR.isFullSet())
277 else if (NewR == getConstantRange())
280 markConstantRange(std::move(NewR));
284 ConstantInt *getConstantInt() const {
285 assert(isConstant() && isa<ConstantInt>(getConstant()) &&
286 "No integer constant");
287 return cast<ConstantInt>(getConstant());
290 /// Compares this symbolic value with Other using Pred and returns either
291 /// true, false or undef constants, or nullptr if the comparison cannot be
293 Constant *getCompare(CmpInst::Predicate Pred, Type *Ty,
294 const ValueLatticeElement &Other) const {
295 if (isUndefined() || Other.isUndefined())
296 return UndefValue::get(Ty);
298 if (isConstant() && Other.isConstant())
299 return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant());
301 // Integer constants are represented as ConstantRanges with single
303 if (!isConstantRange() || !Other.isConstantRange())
306 const auto &CR = getConstantRange();
307 const auto &OtherCR = Other.getConstantRange();
308 if (ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR))
309 return ConstantInt::getTrue(Ty);
310 if (ConstantRange::makeSatisfyingICmpRegion(
311 CmpInst::getInversePredicate(Pred), OtherCR)
313 return ConstantInt::getFalse(Ty);
319 raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);
321 } // end namespace llvm