diff options
Diffstat (limited to 'include/llvm/Analysis/ValueLattice.h')
| -rw-r--r-- | include/llvm/Analysis/ValueLattice.h | 250 |
1 files changed, 250 insertions, 0 deletions
diff --git a/include/llvm/Analysis/ValueLattice.h b/include/llvm/Analysis/ValueLattice.h new file mode 100644 index 000000000000..18a43aafa8ca --- /dev/null +++ b/include/llvm/Analysis/ValueLattice.h @@ -0,0 +1,250 @@ +//===- ValueLattice.h - Value constraint analysis ---------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_VALUELATTICE_H +#define LLVM_ANALYSIS_VALUELATTICE_H + +#include "llvm/IR/ConstantRange.h" +#include "llvm/IR/Constants.h" +// +//===----------------------------------------------------------------------===// +// ValueLatticeElement +//===----------------------------------------------------------------------===// + +/// This class represents lattice values for constants. +/// +/// FIXME: This is basically just for bringup, this can be made a lot more rich +/// in the future. +/// + +namespace llvm { +class ValueLatticeElement { + enum ValueLatticeElementTy { + /// This Value has no known value yet. As a result, this implies the + /// producing instruction is dead. Caution: We use this as the starting + /// state in our local meet rules. In this usage, it's taken to mean + /// "nothing known yet". + undefined, + + /// This Value has a specific constant value. (For constant integers, + /// constantrange is used instead. Integer typed constantexprs can appear + /// as constant.) + constant, + + /// This Value is known to not have the specified value. (For constant + /// integers, constantrange is used instead. As above, integer typed + /// constantexprs can appear here.) + notconstant, + + /// The Value falls within this range. (Used only for integer typed values.) + constantrange, + + /// We can not precisely model the dynamic values this value might take. + overdefined + }; + + /// Val: This stores the current lattice value along with the Constant* for + /// the constant if this is a 'constant' or 'notconstant' value. + ValueLatticeElementTy Tag; + Constant *Val; + ConstantRange Range; + +public: + ValueLatticeElement() : Tag(undefined), Val(nullptr), Range(1, true) {} + + static ValueLatticeElement get(Constant *C) { + ValueLatticeElement Res; + if (!isa<UndefValue>(C)) + Res.markConstant(C); + return Res; + } + static ValueLatticeElement getNot(Constant *C) { + ValueLatticeElement Res; + if (!isa<UndefValue>(C)) + Res.markNotConstant(C); + return Res; + } + static ValueLatticeElement getRange(ConstantRange CR) { + ValueLatticeElement Res; + Res.markConstantRange(std::move(CR)); + return Res; + } + static ValueLatticeElement getOverdefined() { + ValueLatticeElement Res; + Res.markOverdefined(); + return Res; + } + + bool isUndefined() const { return Tag == undefined; } + bool isConstant() const { return Tag == constant; } + bool isNotConstant() const { return Tag == notconstant; } + bool isConstantRange() const { return Tag == constantrange; } + bool isOverdefined() const { return Tag == overdefined; } + + Constant *getConstant() const { + assert(isConstant() && "Cannot get the constant of a non-constant!"); + return Val; + } + + Constant *getNotConstant() const { + assert(isNotConstant() && "Cannot get the constant of a non-notconstant!"); + return Val; + } + + const ConstantRange &getConstantRange() const { + assert(isConstantRange() && + "Cannot get the constant-range of a non-constant-range!"); + return Range; + } + + Optional<APInt> asConstantInteger() const { + if (isConstant() && isa<ConstantInt>(Val)) { + return cast<ConstantInt>(Val)->getValue(); + } else if (isConstantRange() && Range.isSingleElement()) { + return *Range.getSingleElement(); + } + return None; + } + +private: + void markOverdefined() { + if (isOverdefined()) + return; + Tag = overdefined; + } + + void markConstant(Constant *V) { + assert(V && "Marking constant with NULL"); + if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { + markConstantRange(ConstantRange(CI->getValue())); + return; + } + if (isa<UndefValue>(V)) + return; + + assert((!isConstant() || getConstant() == V) && + "Marking constant with different value"); + assert(isUndefined()); + Tag = constant; + Val = V; + } + + void markNotConstant(Constant *V) { + assert(V && "Marking constant with NULL"); + if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { + markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue())); + return; + } + if (isa<UndefValue>(V)) + return; + + assert((!isConstant() || getConstant() != V) && + "Marking constant !constant with same value"); + assert((!isNotConstant() || getNotConstant() == V) && + "Marking !constant with different value"); + assert(isUndefined() || isConstant()); + Tag = notconstant; + Val = V; + } + + void markConstantRange(ConstantRange NewR) { + if (isConstantRange()) { + if (NewR.isEmptySet()) + markOverdefined(); + else { + Range = std::move(NewR); + } + return; + } + + assert(isUndefined()); + if (NewR.isEmptySet()) + markOverdefined(); + else { + Tag = constantrange; + Range = std::move(NewR); + } + } + +public: + /// Updates this object to approximate both this object and RHS. Returns + /// true if this object has been changed. + bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) { + if (RHS.isUndefined() || isOverdefined()) + return false; + if (RHS.isOverdefined()) { + markOverdefined(); + return true; + } + + if (isUndefined()) { + *this = RHS; + return !RHS.isUndefined(); + } + + if (isConstant()) { + if (RHS.isConstant() && Val == RHS.Val) + return false; + markOverdefined(); + return true; + } + + if (isNotConstant()) { + if (RHS.isNotConstant() && Val == RHS.Val) + return false; + markOverdefined(); + return true; + } + + assert(isConstantRange() && "New ValueLattice type?"); + if (!RHS.isConstantRange()) { + // We can get here if we've encountered a constantexpr of integer type + // and merge it with a constantrange. + markOverdefined(); + return true; + } + ConstantRange NewR = Range.unionWith(RHS.getConstantRange()); + if (NewR.isFullSet()) + markOverdefined(); + else + markConstantRange(std::move(NewR)); + return true; + } + + ConstantInt *getConstantInt() const { + assert(isConstant() && isa<ConstantInt>(getConstant()) && + "No integer constant"); + return cast<ConstantInt>(getConstant()); + } + + bool satisfiesPredicate(CmpInst::Predicate Pred, + const ValueLatticeElement &Other) const { + // TODO: share with LVI getPredicateResult. + + if (isUndefined() || Other.isUndefined()) + return true; + + if (isConstant() && Other.isConstant() && Pred == CmpInst::FCMP_OEQ) + return getConstant() == Other.getConstant(); + + // Integer constants are represented as ConstantRanges with single + // elements. + if (!isConstantRange() || !Other.isConstantRange()) + return false; + + const auto &CR = getConstantRange(); + const auto &OtherCR = Other.getConstantRange(); + return ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR); + } +}; + +raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val); + +} // end namespace llvm +#endif |