Index: include/llvm/Analysis/ValueLattice.h =================================================================== --- /dev/null +++ include/llvm/Analysis/ValueLattice.h @@ -0,0 +1,254 @@ +//===- 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" +// +//===----------------------------------------------------------------------===// +// LVILatticeVal +//===----------------------------------------------------------------------===// + +/// 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 LVILatticeVal { + enum LVILatticeValueTy { + /// 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. + LVILatticeValueTy Tag; + Constant *Val; + ConstantRange Range; + +public: + LVILatticeVal() : Tag(undefined), Val(nullptr), Range(1, true) {} + + static LVILatticeVal get(Constant *C) { + LVILatticeVal Res; + if (!isa(C)) + Res.markConstant(C); + return Res; + } + static LVILatticeVal getNot(Constant *C) { + LVILatticeVal Res; + if (!isa(C)) + Res.markNotConstant(C); + return Res; + } + static LVILatticeVal getRange(ConstantRange CR) { + LVILatticeVal Res; + Res.markConstantRange(std::move(CR)); + return Res; + } + static LVILatticeVal getOverdefined() { + LVILatticeVal 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 asConstantInteger() const { + if (isConstant() && isa(Val)) { + return cast(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(V)) { + markConstantRange(ConstantRange(CI->getValue())); + return; + } + if (isa(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(V)) { + markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue())); + return; + } + if (isa(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: + + /// Merge the specified lattice value into this one, updating this + /// one and returning true if anything changed. + bool mergeIn(const LVILatticeVal &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 LVILattice 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(getConstant()) && + "No integer constant"); + return cast(getConstant()); + } + + bool satisfiesPredicate(CmpInst::Predicate Pred, + const LVILatticeVal &Other) const { + // TODO: share with LVI getPredicateResult. + + // Integer constants are represented as ConstantRanges with single + // elements. + if (!isConstantRange() || !Other.isConstantRange()) + return false; + + const auto &CR = getConstantRange(); + const auto &OtherCR = Other.getConstantRange(); + switch (Pred) { + case CmpInst::ICMP_NE: + return CR.intersectWith(OtherCR).isEmptySet(); + case CmpInst::ICMP_EQ: + return CR.isSingleElement() && OtherCR.isSingleElement() && + CR == OtherCR; + default: + return ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR) + .contains(CR); + } + } +}; + +raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) + LLVM_ATTRIBUTE_USED; +} // end namespace llvm +#endif Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -81,6 +81,7 @@ TypeBasedAliasAnalysis.cpp TypeMetadataUtils.cpp ScopedNoAliasAA.cpp + ValueLattice.cpp ValueTracking.cpp VectorUtils.cpp Index: lib/Analysis/LazyValueInfo.cpp =================================================================== --- lib/Analysis/LazyValueInfo.cpp +++ lib/Analysis/LazyValueInfo.cpp @@ -20,6 +20,7 @@ #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/ValueTracking.h" +#include "llvm/Analysis/ValueLattice.h" #include "llvm/IR/AssemblyAnnotationWriter.h" #include "llvm/IR/CFG.h" #include "llvm/IR/ConstantRange.h" @@ -60,230 +61,6 @@ AnalysisKey LazyValueAnalysis::Key; -//===----------------------------------------------------------------------===// -// LVILatticeVal -//===----------------------------------------------------------------------===// - -/// This is the information tracked by LazyValueInfo for each value. -/// -/// FIXME: This is basically just for bringup, this can be made a lot more rich -/// in the future. -/// -namespace { -class LVILatticeVal { - enum LatticeValueTy { - /// 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. - LatticeValueTy Tag; - Constant *Val; - ConstantRange Range; - -public: - LVILatticeVal() : Tag(undefined), Val(nullptr), Range(1, true) {} - - static LVILatticeVal get(Constant *C) { - LVILatticeVal Res; - if (!isa(C)) - Res.markConstant(C); - return Res; - } - static LVILatticeVal getNot(Constant *C) { - LVILatticeVal Res; - if (!isa(C)) - Res.markNotConstant(C); - return Res; - } - static LVILatticeVal getRange(ConstantRange CR) { - LVILatticeVal Res; - Res.markConstantRange(std::move(CR)); - return Res; - } - static LVILatticeVal getOverdefined() { - LVILatticeVal 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 asConstantInteger() const { - if (isConstant() && isa(Val)) { - return cast(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(V)) { - markConstantRange(ConstantRange(CI->getValue())); - return; - } - if (isa(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(V)) { - markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue())); - return; - } - if (isa(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: - - /// Merge the specified lattice value into this one, updating this - /// one and returning true if anything changed. - void mergeIn(const LVILatticeVal &RHS, const DataLayout &DL) { - if (RHS.isUndefined() || isOverdefined()) - return; - if (RHS.isOverdefined()) { - markOverdefined(); - return; - } - - if (isUndefined()) { - *this = RHS; - return; - } - - if (isConstant()) { - if (RHS.isConstant() && Val == RHS.Val) - return; - markOverdefined(); - return; - } - - if (isNotConstant()) { - if (RHS.isNotConstant() && Val == RHS.Val) - return; - markOverdefined(); - return; - } - - assert(isConstantRange() && "New LVILattice 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; - } - ConstantRange NewR = Range.unionWith(RHS.getConstantRange()); - if (NewR.isFullSet()) - markOverdefined(); - else - markConstantRange(std::move(NewR)); - } -}; - -} // end anonymous namespace. - -namespace llvm { -raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) - LLVM_ATTRIBUTE_USED; -raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) { - if (Val.isUndefined()) - return OS << "undefined"; - if (Val.isOverdefined()) - return OS << "overdefined"; - - if (Val.isNotConstant()) - return OS << "notconstant<" << *Val.getNotConstant() << '>'; - if (Val.isConstantRange()) - return OS << "constantrange<" << Val.getConstantRange().getLower() << ", " - << Val.getConstantRange().getUpper() << '>'; - return OS << "constant<" << *Val.getConstant() << '>'; -} -} - /// Returns true if this lattice value represents at most one possible value. /// This is as precise as any lattice value can get while still representing /// reachable code. Index: lib/Analysis/ValueLattice.cpp =================================================================== --- /dev/null +++ lib/Analysis/ValueLattice.cpp @@ -0,0 +1,26 @@ +//===- ValueLattice.cpp - 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. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/ValueLattice.h" + +namespace llvm { +raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) { + if (Val.isUndefined()) + return OS << "undefined"; + if (Val.isOverdefined()) + return OS << "overdefined"; + + if (Val.isNotConstant()) + return OS << "notconstant<" << *Val.getNotConstant() << ">"; + if (Val.isConstantRange()) + return OS << "constantrange<" << Val.getConstantRange().getLower() << ", " + << Val.getConstantRange().getUpper() << ">"; + return OS << "constant<" << *Val.getConstant() << ">"; +} +} // end namespace llvm