From 5133f6fc61d9ff0dea461c8875ac53c113334355 Mon Sep 17 00:00:00 2001 From: Florian Hahn Date: Thu, 28 Sep 2017 11:09:22 +0000 Subject: [PATCH] [LVI] Move LVILatticeVal class to separate header file (NFC). Summary: This allows sharing the lattice value code between LVI and SCCP (D36656). It also adds a `satisfiesPredicate` function, used by D36656. Reviewers: davide, sanjoy, efriedma Reviewed By: sanjoy Subscribers: mgorny, llvm-commits Differential Revision: https://reviews.llvm.org/D37591 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@314411 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/ValueLattice.h | 250 +++++++++++++++++ lib/Analysis/CMakeLists.txt | 1 + lib/Analysis/LazyValueInfo.cpp | 480 +++++++++----------------------- lib/Analysis/ValueLattice.cpp | 26 ++ unittests/Analysis/CMakeLists.txt | 1 + unittests/Analysis/ValueLatticeTest.cpp | 148 ++++++++++ 6 files changed, 559 insertions(+), 347 deletions(-) create mode 100644 include/llvm/Analysis/ValueLattice.h create mode 100644 lib/Analysis/ValueLattice.cpp create mode 100644 unittests/Analysis/ValueLatticeTest.cpp diff --git a/include/llvm/Analysis/ValueLattice.h b/include/llvm/Analysis/ValueLattice.h new file mode 100644 index 00000000000..18a43aafa8c --- /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(C)) + Res.markConstant(C); + return Res; + } + static ValueLatticeElement getNot(Constant *C) { + ValueLatticeElement Res; + if (!isa(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 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: + /// 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(getConstant()) && + "No integer constant"); + return cast(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 diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt index 45268dd5c76..1b2de163d65 100644 --- a/lib/Analysis/CMakeLists.txt +++ b/lib/Analysis/CMakeLists.txt @@ -81,6 +81,7 @@ add_llvm_library(LLVMAnalysis TypeBasedAliasAnalysis.cpp TypeMetadataUtils.cpp ScopedNoAliasAA.cpp + ValueLattice.cpp ValueTracking.cpp VectorUtils.cpp diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp index 31f1d44653d..3a9dac5783f 100644 --- a/lib/Analysis/LazyValueInfo.cpp +++ b/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,234 +61,10 @@ namespace llvm { 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. -static bool hasSingleValue(const LVILatticeVal &Val) { +static bool hasSingleValue(const ValueLatticeElement &Val) { if (Val.isConstantRange() && Val.getConstantRange().isSingleElement()) // Integer constants are single element ranges @@ -312,7 +89,8 @@ static bool hasSingleValue(const LVILatticeVal &Val) { /// contradictory. If this happens, we return some valid lattice value so as /// not confuse the rest of LVI. Ideally, we'd always return Undefined, but /// we do not make this guarantee. TODO: This would be a useful enhancement. -static LVILatticeVal intersect(const LVILatticeVal &A, const LVILatticeVal &B) { +static ValueLatticeElement intersect(const ValueLatticeElement &A, + const ValueLatticeElement &B) { // Undefined is the strongest state. It means the value is known to be along // an unreachable path. if (A.isUndefined()) @@ -344,7 +122,7 @@ static LVILatticeVal intersect(const LVILatticeVal &A, const LVILatticeVal &B) { // Note: An empty range is implicitly converted to overdefined internally. // TODO: We could instead use Undefined here since we've proven a conflict // and thus know this path must be unreachable. - return LVILatticeVal::getRange(std::move(Range)); + return ValueLatticeElement::getRange(std::move(Range)); } //===----------------------------------------------------------------------===// @@ -382,7 +160,7 @@ namespace { struct ValueCacheEntryTy { ValueCacheEntryTy(Value *V, LazyValueInfoCache *P) : Handle(V, P) {} LVIValueHandle Handle; - SmallDenseMap, LVILatticeVal, 4> BlockVals; + SmallDenseMap, ValueLatticeElement, 4> BlockVals; }; /// This tracks, on a per-block basis, the set of values that are @@ -400,7 +178,8 @@ namespace { public: - void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) { + void insertResult(Value *Val, BasicBlock *BB, + const ValueLatticeElement &Result) { SeenBlocks.insert(BB); // Insert over-defined values into their own cache to reduce memory @@ -438,16 +217,16 @@ namespace { return I->second->BlockVals.count(BB); } - LVILatticeVal getCachedValueInfo(Value *V, BasicBlock *BB) const { + ValueLatticeElement getCachedValueInfo(Value *V, BasicBlock *BB) const { if (isOverdefined(V, BB)) - return LVILatticeVal::getOverdefined(); + return ValueLatticeElement::getOverdefined(); auto I = ValueCache.find_as(V); if (I == ValueCache.end()) - return LVILatticeVal(); + return ValueLatticeElement(); auto BBI = I->second->BlockVals.find(BB); if (BBI == I->second->BlockVals.end()) - return LVILatticeVal(); + return ValueLatticeElement(); return BBI->second; } @@ -624,26 +403,29 @@ namespace { const DataLayout &DL; ///< A mandatory DataLayout DominatorTree *DT; ///< An optional DT pointer. - LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB); + ValueLatticeElement getBlockValue(Value *Val, BasicBlock *BB); bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T, - LVILatticeVal &Result, Instruction *CxtI = nullptr); + ValueLatticeElement &Result, Instruction *CxtI = nullptr); bool hasBlockValue(Value *Val, BasicBlock *BB); // These methods process one work item and may add more. A false value // returned means that the work item was not completely processed and must // be revisited after going through the new items. bool solveBlockValue(Value *Val, BasicBlock *BB); - bool solveBlockValueImpl(LVILatticeVal &Res, Value *Val, BasicBlock *BB); - bool solveBlockValueNonLocal(LVILatticeVal &BBLV, Value *Val, BasicBlock *BB); - bool solveBlockValuePHINode(LVILatticeVal &BBLV, PHINode *PN, BasicBlock *BB); - bool solveBlockValueSelect(LVILatticeVal &BBLV, SelectInst *S, + bool solveBlockValueImpl(ValueLatticeElement &Res, Value *Val, + BasicBlock *BB); + bool solveBlockValueNonLocal(ValueLatticeElement &BBLV, Value *Val, + BasicBlock *BB); + bool solveBlockValuePHINode(ValueLatticeElement &BBLV, PHINode *PN, + BasicBlock *BB); + bool solveBlockValueSelect(ValueLatticeElement &BBLV, SelectInst *S, BasicBlock *BB); - bool solveBlockValueBinaryOp(LVILatticeVal &BBLV, BinaryOperator *BBI, + bool solveBlockValueBinaryOp(ValueLatticeElement &BBLV, BinaryOperator *BBI, BasicBlock *BB); - bool solveBlockValueCast(LVILatticeVal &BBLV, CastInst *CI, + bool solveBlockValueCast(ValueLatticeElement &BBLV, CastInst *CI, BasicBlock *BB); void intersectAssumeOrGuardBlockValueConstantRange(Value *Val, - LVILatticeVal &BBLV, + ValueLatticeElement &BBLV, Instruction *BBI); void solve(); @@ -651,18 +433,19 @@ namespace { public: /// This is the query interface to determine the lattice /// value for the specified Value* at the end of the specified block. - LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB, - Instruction *CxtI = nullptr); + ValueLatticeElement getValueInBlock(Value *V, BasicBlock *BB, + Instruction *CxtI = nullptr); /// This is the query interface to determine the lattice /// value for the specified Value* at the specified instruction (generally /// from an assume intrinsic). - LVILatticeVal getValueAt(Value *V, Instruction *CxtI); + ValueLatticeElement getValueAt(Value *V, Instruction *CxtI); /// This is the query interface to determine the lattice /// value for the specified Value* that is true on the specified edge. - LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB, - Instruction *CxtI = nullptr); + ValueLatticeElement getValueOnEdge(Value *V, BasicBlock *FromBB, + BasicBlock *ToBB, + Instruction *CxtI = nullptr); /// Complete flush all previously computed values void clear() { @@ -713,7 +496,7 @@ void LazyValueInfoImpl::solve() { while (!StartingStack.empty()) { std::pair &e = StartingStack.back(); TheCache.insertResult(e.second, e.first, - LVILatticeVal::getOverdefined()); + ValueLatticeElement::getOverdefined()); StartingStack.pop_back(); } BlockValueSet.clear(); @@ -749,15 +532,16 @@ bool LazyValueInfoImpl::hasBlockValue(Value *Val, BasicBlock *BB) { return TheCache.hasCachedValueInfo(Val, BB); } -LVILatticeVal LazyValueInfoImpl::getBlockValue(Value *Val, BasicBlock *BB) { +ValueLatticeElement LazyValueInfoImpl::getBlockValue(Value *Val, + BasicBlock *BB) { // If already a constant, there is nothing to compute. if (Constant *VC = dyn_cast(Val)) - return LVILatticeVal::get(VC); + return ValueLatticeElement::get(VC); return TheCache.getCachedValueInfo(Val, BB); } -static LVILatticeVal getFromRangeMetadata(Instruction *BBI) { +static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) { switch (BBI->getOpcode()) { default: break; case Instruction::Load: @@ -765,12 +549,13 @@ static LVILatticeVal getFromRangeMetadata(Instruction *BBI) { case Instruction::Invoke: if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range)) if (isa(BBI->getType())) { - return LVILatticeVal::getRange(getConstantRangeFromMetadata(*Ranges)); + return ValueLatticeElement::getRange( + getConstantRangeFromMetadata(*Ranges)); } break; }; // Nothing known - will be intersected with other facts - return LVILatticeVal::getOverdefined(); + return ValueLatticeElement::getOverdefined(); } bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) { @@ -790,7 +575,7 @@ bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) { // Hold off inserting this value into the Cache in case we have to return // false and come back later. - LVILatticeVal Res; + ValueLatticeElement Res; if (!solveBlockValueImpl(Res, Val, BB)) // Work pushed, will revisit return false; @@ -799,7 +584,7 @@ bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) { return true; } -bool LazyValueInfoImpl::solveBlockValueImpl(LVILatticeVal &Res, +bool LazyValueInfoImpl::solveBlockValueImpl(ValueLatticeElement &Res, Value *Val, BasicBlock *BB) { Instruction *BBI = dyn_cast(Val); @@ -823,7 +608,7 @@ bool LazyValueInfoImpl::solveBlockValueImpl(LVILatticeVal &Res, // That is unfortunate. PointerType *PT = dyn_cast(BBI->getType()); if (PT && isKnownNonZero(BBI, DL)) { - Res = LVILatticeVal::getNot(ConstantPointerNull::get(PT)); + Res = ValueLatticeElement::getNot(ConstantPointerNull::get(PT)); return true; } if (BBI->getType()->isIntegerTy()) { @@ -890,9 +675,9 @@ static bool isObjectDereferencedInBlock(Value *Val, BasicBlock *BB) { return false; } -bool LazyValueInfoImpl::solveBlockValueNonLocal(LVILatticeVal &BBLV, +bool LazyValueInfoImpl::solveBlockValueNonLocal(ValueLatticeElement &BBLV, Value *Val, BasicBlock *BB) { - LVILatticeVal Result; // Start Undefined. + ValueLatticeElement Result; // Start Undefined. // If this is the entry block, we must be asking about an argument. The // value is overdefined. @@ -903,9 +688,9 @@ bool LazyValueInfoImpl::solveBlockValueNonLocal(LVILatticeVal &BBLV, if (Val->getType()->isPointerTy() && (isKnownNonZero(Val, DL) || isObjectDereferencedInBlock(Val, BB))) { PointerType *PTy = cast(Val->getType()); - Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy)); + Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy)); } else { - Result = LVILatticeVal::getOverdefined(); + Result = ValueLatticeElement::getOverdefined(); } BBLV = Result; return true; @@ -921,7 +706,7 @@ bool LazyValueInfoImpl::solveBlockValueNonLocal(LVILatticeVal &BBLV, // canonicalizing to make this true rather than relying on this happy // accident. for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { - LVILatticeVal EdgeResult; + ValueLatticeElement EdgeResult; if (!getEdgeValue(Val, *PI, BB, EdgeResult)) // Explore that input, then return here return false; @@ -938,7 +723,7 @@ bool LazyValueInfoImpl::solveBlockValueNonLocal(LVILatticeVal &BBLV, if (Val->getType()->isPointerTy() && isObjectDereferencedInBlock(Val, BB)) { PointerType *PTy = cast(Val->getType()); - Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy)); + Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy)); } BBLV = Result; @@ -952,9 +737,9 @@ bool LazyValueInfoImpl::solveBlockValueNonLocal(LVILatticeVal &BBLV, return true; } -bool LazyValueInfoImpl::solveBlockValuePHINode(LVILatticeVal &BBLV, - PHINode *PN, BasicBlock *BB) { - LVILatticeVal Result; // Start Undefined. +bool LazyValueInfoImpl::solveBlockValuePHINode(ValueLatticeElement &BBLV, + PHINode *PN, BasicBlock *BB) { + ValueLatticeElement Result; // Start Undefined. // Loop over all of our predecessors, merging what we know from them into // result. See the comment about the chosen traversal order in @@ -962,7 +747,7 @@ bool LazyValueInfoImpl::solveBlockValuePHINode(LVILatticeVal &BBLV, for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { BasicBlock *PhiBB = PN->getIncomingBlock(i); Value *PhiVal = PN->getIncomingValue(i); - LVILatticeVal EdgeResult; + ValueLatticeElement EdgeResult; // Note that we can provide PN as the context value to getEdgeValue, even // though the results will be cached, because PN is the value being used as // the cache key in the caller. @@ -989,13 +774,13 @@ bool LazyValueInfoImpl::solveBlockValuePHINode(LVILatticeVal &BBLV, return true; } -static LVILatticeVal getValueFromCondition(Value *Val, Value *Cond, - bool isTrueDest = true); +static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, + bool isTrueDest = true); // If we can determine a constraint on the value given conditions assumed by // the program, intersect those constraints with BBLV void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange( - Value *Val, LVILatticeVal &BBLV, Instruction *BBI) { + Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) { BBI = BBI ? BBI : dyn_cast(Val); if (!BBI) return; @@ -1024,35 +809,35 @@ void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange( } } -bool LazyValueInfoImpl::solveBlockValueSelect(LVILatticeVal &BBLV, - SelectInst *SI, BasicBlock *BB) { +bool LazyValueInfoImpl::solveBlockValueSelect(ValueLatticeElement &BBLV, + SelectInst *SI, BasicBlock *BB) { // Recurse on our inputs if needed if (!hasBlockValue(SI->getTrueValue(), BB)) { if (pushBlockValue(std::make_pair(BB, SI->getTrueValue()))) return false; - BBLV = LVILatticeVal::getOverdefined(); + BBLV = ValueLatticeElement::getOverdefined(); return true; } - LVILatticeVal TrueVal = getBlockValue(SI->getTrueValue(), BB); + ValueLatticeElement TrueVal = getBlockValue(SI->getTrueValue(), BB); // If we hit overdefined, don't ask more queries. We want to avoid poisoning // extra slots in the table if we can. if (TrueVal.isOverdefined()) { - BBLV = LVILatticeVal::getOverdefined(); + BBLV = ValueLatticeElement::getOverdefined(); return true; } if (!hasBlockValue(SI->getFalseValue(), BB)) { if (pushBlockValue(std::make_pair(BB, SI->getFalseValue()))) return false; - BBLV = LVILatticeVal::getOverdefined(); + BBLV = ValueLatticeElement::getOverdefined(); return true; } - LVILatticeVal FalseVal = getBlockValue(SI->getFalseValue(), BB); + ValueLatticeElement FalseVal = getBlockValue(SI->getFalseValue(), BB); // If we hit overdefined, don't ask more queries. We want to avoid poisoning // extra slots in the table if we can. if (FalseVal.isOverdefined()) { - BBLV = LVILatticeVal::getOverdefined(); + BBLV = ValueLatticeElement::getOverdefined(); return true; } @@ -1080,7 +865,7 @@ bool LazyValueInfoImpl::solveBlockValueSelect(LVILatticeVal &BBLV, return TrueCR.umax(FalseCR); }; }(); - BBLV = LVILatticeVal::getRange(ResultCR); + BBLV = ValueLatticeElement::getRange(ResultCR); return true; } @@ -1123,7 +908,7 @@ bool LazyValueInfoImpl::solveBlockValueSelect(LVILatticeVal &BBLV, m_ConstantInt(CIAdded)))) { auto ResNot = addConstants(CIBase, CIAdded); FalseVal = intersect(FalseVal, - LVILatticeVal::getNot(ResNot)); + ValueLatticeElement::getNot(ResNot)); } break; case ICmpInst::ICMP_NE: @@ -1131,27 +916,27 @@ bool LazyValueInfoImpl::solveBlockValueSelect(LVILatticeVal &BBLV, m_ConstantInt(CIAdded)))) { auto ResNot = addConstants(CIBase, CIAdded); TrueVal = intersect(TrueVal, - LVILatticeVal::getNot(ResNot)); + ValueLatticeElement::getNot(ResNot)); } break; }; } } - LVILatticeVal Result; // Start Undefined. + ValueLatticeElement Result; // Start Undefined. Result.mergeIn(TrueVal, DL); Result.mergeIn(FalseVal, DL); BBLV = Result; return true; } -bool LazyValueInfoImpl::solveBlockValueCast(LVILatticeVal &BBLV, +bool LazyValueInfoImpl::solveBlockValueCast(ValueLatticeElement &BBLV, CastInst *CI, BasicBlock *BB) { if (!CI->getOperand(0)->getType()->isSized()) { // Without knowing how wide the input is, we can't analyze it in any useful // way. - BBLV = LVILatticeVal::getOverdefined(); + BBLV = ValueLatticeElement::getOverdefined(); return true; } @@ -1168,7 +953,7 @@ bool LazyValueInfoImpl::solveBlockValueCast(LVILatticeVal &BBLV, // Unhandled instructions are overdefined. DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - overdefined (unknown cast).\n"); - BBLV = LVILatticeVal::getOverdefined(); + BBLV = ValueLatticeElement::getOverdefined(); return true; } @@ -1184,7 +969,7 @@ bool LazyValueInfoImpl::solveBlockValueCast(LVILatticeVal &BBLV, DL.getTypeSizeInBits(CI->getOperand(0)->getType()); ConstantRange LHSRange = ConstantRange(OperandBitWidth); if (hasBlockValue(CI->getOperand(0), BB)) { - LVILatticeVal LHSVal = getBlockValue(CI->getOperand(0), BB); + ValueLatticeElement LHSVal = getBlockValue(CI->getOperand(0), BB); intersectAssumeOrGuardBlockValueConstantRange(CI->getOperand(0), LHSVal, CI); if (LHSVal.isConstantRange()) @@ -1196,14 +981,14 @@ bool LazyValueInfoImpl::solveBlockValueCast(LVILatticeVal &BBLV, // NOTE: We're currently limited by the set of operations that ConstantRange // can evaluate symbolically. Enhancing that set will allows us to analyze // more definitions. - BBLV = LVILatticeVal::getRange(LHSRange.castOp(CI->getOpcode(), - ResultBitWidth)); + BBLV = ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(), + ResultBitWidth)); return true; } -bool LazyValueInfoImpl::solveBlockValueBinaryOp(LVILatticeVal &BBLV, - BinaryOperator *BO, - BasicBlock *BB) { +bool LazyValueInfoImpl::solveBlockValueBinaryOp(ValueLatticeElement &BBLV, + BinaryOperator *BO, + BasicBlock *BB) { assert(BO->getOperand(0)->getType()->isSized() && "all operands to binary operators are sized"); @@ -1226,7 +1011,7 @@ bool LazyValueInfoImpl::solveBlockValueBinaryOp(LVILatticeVal &BBLV, // Unhandled instructions are overdefined. DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - overdefined (unknown binary operator).\n"); - BBLV = LVILatticeVal::getOverdefined(); + BBLV = ValueLatticeElement::getOverdefined(); return true; }; @@ -1242,7 +1027,7 @@ bool LazyValueInfoImpl::solveBlockValueBinaryOp(LVILatticeVal &BBLV, DL.getTypeSizeInBits(BO->getOperand(0)->getType()); ConstantRange LHSRange = ConstantRange(OperandBitWidth); if (hasBlockValue(BO->getOperand(0), BB)) { - LVILatticeVal LHSVal = getBlockValue(BO->getOperand(0), BB); + ValueLatticeElement LHSVal = getBlockValue(BO->getOperand(0), BB); intersectAssumeOrGuardBlockValueConstantRange(BO->getOperand(0), LHSVal, BO); if (LHSVal.isConstantRange()) @@ -1256,12 +1041,12 @@ bool LazyValueInfoImpl::solveBlockValueBinaryOp(LVILatticeVal &BBLV, // can evaluate symbolically. Enhancing that set will allows us to analyze // more definitions. Instruction::BinaryOps BinOp = BO->getOpcode(); - BBLV = LVILatticeVal::getRange(LHSRange.binaryOp(BinOp, RHSRange)); + BBLV = ValueLatticeElement::getRange(LHSRange.binaryOp(BinOp, RHSRange)); return true; } -static LVILatticeVal getValueFromICmpCondition(Value *Val, ICmpInst *ICI, - bool isTrueDest) { +static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI, + bool isTrueDest) { Value *LHS = ICI->getOperand(0); Value *RHS = ICI->getOperand(1); CmpInst::Predicate Predicate = ICI->getPredicate(); @@ -1271,14 +1056,14 @@ static LVILatticeVal getValueFromICmpCondition(Value *Val, ICmpInst *ICI, // We know that V has the RHS constant if this is a true SETEQ or // false SETNE. if (isTrueDest == (Predicate == ICmpInst::ICMP_EQ)) - return LVILatticeVal::get(cast(RHS)); + return ValueLatticeElement::get(cast(RHS)); else - return LVILatticeVal::getNot(cast(RHS)); + return ValueLatticeElement::getNot(cast(RHS)); } } if (!Val->getType()->isIntegerTy()) - return LVILatticeVal::getOverdefined(); + return ValueLatticeElement::getOverdefined(); // Use ConstantRange::makeAllowedICmpRegion in order to determine the possible // range of Val guaranteed by the condition. Recognize comparisons in the from @@ -1317,19 +1102,19 @@ static LVILatticeVal getValueFromICmpCondition(Value *Val, ICmpInst *ICI, if (Offset) // Apply the offset from above. TrueValues = TrueValues.subtract(Offset->getValue()); - return LVILatticeVal::getRange(std::move(TrueValues)); + return ValueLatticeElement::getRange(std::move(TrueValues)); } - return LVILatticeVal::getOverdefined(); + return ValueLatticeElement::getOverdefined(); } -static LVILatticeVal +static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest, - DenseMap &Visited); + DenseMap &Visited); -static LVILatticeVal +static ValueLatticeElement getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, - DenseMap &Visited) { + DenseMap &Visited) { if (ICmpInst *ICI = dyn_cast(Cond)) return getValueFromICmpCondition(Val, ICI, isTrueDest); @@ -1340,16 +1125,16 @@ getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, BinaryOperator *BO = dyn_cast(Cond); if (!BO || (isTrueDest && BO->getOpcode() != BinaryOperator::And) || (!isTrueDest && BO->getOpcode() != BinaryOperator::Or)) - return LVILatticeVal::getOverdefined(); + return ValueLatticeElement::getOverdefined(); auto RHS = getValueFromCondition(Val, BO->getOperand(0), isTrueDest, Visited); auto LHS = getValueFromCondition(Val, BO->getOperand(1), isTrueDest, Visited); return intersect(RHS, LHS); } -static LVILatticeVal +static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest, - DenseMap &Visited) { + DenseMap &Visited) { auto I = Visited.find(Cond); if (I != Visited.end()) return I->second; @@ -1359,9 +1144,10 @@ getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest, return Result; } -LVILatticeVal getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest) { +ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, + bool isTrueDest) { assert(Cond && "precondition"); - DenseMap Visited; + DenseMap Visited; return getValueFromCondition(Val, Cond, isTrueDest, Visited); } @@ -1382,9 +1168,9 @@ static bool isOperationFoldable(User *Usr) { // of its operands Op is an integer constant OpConstVal. If so, return it as an // lattice value range with a single element or otherwise return an overdefined // lattice value. -static LVILatticeVal constantFoldUser(User *Usr, Value *Op, - const APInt &OpConstVal, - const DataLayout &DL) { +static ValueLatticeElement constantFoldUser(User *Usr, Value *Op, + const APInt &OpConstVal, + const DataLayout &DL) { assert(isOperationFoldable(Usr) && "Precondition"); Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal); // Check if Usr can be simplified to a constant. @@ -1393,7 +1179,7 @@ static LVILatticeVal constantFoldUser(User *Usr, Value *Op, if (auto *C = dyn_cast_or_null( SimplifyCastInst(CI->getOpcode(), OpConst, CI->getDestTy(), DL))) { - return LVILatticeVal::getRange(ConstantRange(C->getValue())); + return ValueLatticeElement::getRange(ConstantRange(C->getValue())); } } else if (auto *BO = dyn_cast(Usr)) { bool Op0Match = BO->getOperand(0) == Op; @@ -1404,17 +1190,17 @@ static LVILatticeVal constantFoldUser(User *Usr, Value *Op, Value *RHS = Op1Match ? OpConst : BO->getOperand(1); if (auto *C = dyn_cast_or_null( SimplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) { - return LVILatticeVal::getRange(ConstantRange(C->getValue())); + return ValueLatticeElement::getRange(ConstantRange(C->getValue())); } } - return LVILatticeVal::getOverdefined(); + return ValueLatticeElement::getOverdefined(); } /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if /// Val is not constrained on the edge. Result is unspecified if return value /// is false. static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, - BasicBlock *BBTo, LVILatticeVal &Result) { + BasicBlock *BBTo, ValueLatticeElement &Result) { // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we // know that v != 0. if (BranchInst *BI = dyn_cast(BBFrom->getTerminator())) { @@ -1430,7 +1216,7 @@ static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, // If V is the condition of the branch itself, then we know exactly what // it is. if (Condition == Val) { - Result = LVILatticeVal::get(ConstantInt::get( + Result = ValueLatticeElement::get(ConstantInt::get( Type::getInt1Ty(Val->getContext()), isTrueDest)); return true; } @@ -1468,7 +1254,7 @@ static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, // br i1 %Condition, label %then, label %else for (unsigned i = 0; i < Usr->getNumOperands(); ++i) { Value *Op = Usr->getOperand(i); - LVILatticeVal OpLatticeVal = + ValueLatticeElement OpLatticeVal = getValueFromCondition(Op, Condition, isTrueDest); if (Optional OpConst = OpLatticeVal.asConstantInteger()) { Result = constantFoldUser(Usr, Op, OpConst.getValue(), DL); @@ -1511,7 +1297,7 @@ static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, if (ValUsesConditionAndMayBeFoldable) { User *Usr = cast(Val); const DataLayout &DL = BBTo->getModule()->getDataLayout(); - LVILatticeVal EdgeLatticeVal = + ValueLatticeElement EdgeLatticeVal = constantFoldUser(Usr, Condition, CaseValue, DL); if (EdgeLatticeVal.isOverdefined()) return false; @@ -1529,7 +1315,7 @@ static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, } else if (Case.getCaseSuccessor() == BBTo) EdgesVals = EdgesVals.unionWith(EdgeVal); } - Result = LVILatticeVal::getRange(std::move(EdgesVals)); + Result = ValueLatticeElement::getRange(std::move(EdgesVals)); return true; } return false; @@ -1538,19 +1324,20 @@ static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, /// \brief Compute the value of Val on the edge BBFrom -> BBTo or the value at /// the basic block if the edge does not constrain Val. bool LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom, - BasicBlock *BBTo, LVILatticeVal &Result, + BasicBlock *BBTo, + ValueLatticeElement &Result, Instruction *CxtI) { // If already a constant, there is nothing to compute. if (Constant *VC = dyn_cast(Val)) { - Result = LVILatticeVal::get(VC); + Result = ValueLatticeElement::get(VC); return true; } - LVILatticeVal LocalResult; + ValueLatticeElement LocalResult; if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult)) // If we couldn't constrain the value on the edge, LocalResult doesn't // provide any information. - LocalResult = LVILatticeVal::getOverdefined(); + LocalResult = ValueLatticeElement::getOverdefined(); if (hasSingleValue(LocalResult)) { // Can't get any more precise here @@ -1567,7 +1354,7 @@ bool LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom, } // Try to intersect ranges of the BB and the constraint on the edge. - LVILatticeVal InBlock = getBlockValue(Val, BBFrom); + ValueLatticeElement InBlock = getBlockValue(Val, BBFrom); intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, BBFrom->getTerminator()); // We can use the context instruction (generically the ultimate instruction @@ -1584,8 +1371,8 @@ bool LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom, return true; } -LVILatticeVal LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB, - Instruction *CxtI) { +ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB, + Instruction *CxtI) { DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '" << BB->getName() << "'\n"); @@ -1594,21 +1381,21 @@ LVILatticeVal LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB, pushBlockValue(std::make_pair(BB, V)); solve(); } - LVILatticeVal Result = getBlockValue(V, BB); + ValueLatticeElement Result = getBlockValue(V, BB); intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI); DEBUG(dbgs() << " Result = " << Result << "\n"); return Result; } -LVILatticeVal LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) { +ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) { DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName() << "'\n"); if (auto *C = dyn_cast(V)) - return LVILatticeVal::get(C); + return ValueLatticeElement::get(C); - LVILatticeVal Result = LVILatticeVal::getOverdefined(); + ValueLatticeElement Result = ValueLatticeElement::getOverdefined(); if (auto *I = dyn_cast(V)) Result = getFromRangeMetadata(I); intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI); @@ -1617,13 +1404,13 @@ LVILatticeVal LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) { return Result; } -LVILatticeVal LazyValueInfoImpl:: +ValueLatticeElement LazyValueInfoImpl:: getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI) { DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '" << FromBB->getName() << "' to '" << ToBB->getName() << "'\n"); - LVILatticeVal Result; + ValueLatticeElement Result; if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) { solve(); bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI); @@ -1703,7 +1490,8 @@ bool LazyValueInfo::invalidate(Function &F, const PreservedAnalyses &PA, void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); } -LazyValueInfo LazyValueAnalysis::run(Function &F, FunctionAnalysisManager &FAM) { +LazyValueInfo LazyValueAnalysis::run(Function &F, + FunctionAnalysisManager &FAM) { auto &AC = FAM.getResult(F); auto &TLI = FAM.getResult(F); auto *DT = FAM.getCachedResult(F); @@ -1732,7 +1520,7 @@ Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB, return nullptr; const DataLayout &DL = BB->getModule()->getDataLayout(); - LVILatticeVal Result = + ValueLatticeElement Result = getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI); if (Result.isConstant()) @@ -1750,7 +1538,7 @@ ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB, assert(V->getType()->isIntegerTy()); unsigned Width = V->getType()->getIntegerBitWidth(); const DataLayout &DL = BB->getModule()->getDataLayout(); - LVILatticeVal Result = + ValueLatticeElement Result = getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI); if (Result.isUndefined()) return ConstantRange(Width, /*isFullSet=*/false); @@ -1769,7 +1557,7 @@ Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI) { const DataLayout &DL = FromBB->getModule()->getDataLayout(); - LVILatticeVal Result = + ValueLatticeElement Result = getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI); if (Result.isConstant()) @@ -1788,7 +1576,7 @@ ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V, Instruction *CxtI) { unsigned Width = V->getType()->getIntegerBitWidth(); const DataLayout &DL = FromBB->getModule()->getDataLayout(); - LVILatticeVal Result = + ValueLatticeElement Result = getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI); if (Result.isUndefined()) @@ -1802,11 +1590,9 @@ ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V, return ConstantRange(Width, /*isFullSet=*/true); } -static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C, - const LVILatticeVal &Val, - const DataLayout &DL, - TargetLibraryInfo *TLI) { - +static LazyValueInfo::Tristate +getPredicateResult(unsigned Pred, Constant *C, const ValueLatticeElement &Val, + const DataLayout &DL, TargetLibraryInfo *TLI) { // If we know the value is a constant, evaluate the conditional. Constant *Res = nullptr; if (Val.isConstant()) { @@ -1876,7 +1662,7 @@ LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI) { const DataLayout &DL = FromBB->getModule()->getDataLayout(); - LVILatticeVal Result = + ValueLatticeElement Result = getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI); return getPredicateResult(Pred, C, Result, DL, TLI); @@ -1897,7 +1683,7 @@ LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C, else if (Pred == ICmpInst::ICMP_NE) return LazyValueInfo::True; } - LVILatticeVal Result = getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI); + ValueLatticeElement Result = getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI); Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI); if (Ret != Unknown) return Ret; @@ -2011,7 +1797,7 @@ void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot( // Find if there are latticevalues defined for arguments of the function. auto *F = BB->getParent(); for (auto &Arg : F->args()) { - LVILatticeVal Result = LVIImpl->getValueInBlock( + ValueLatticeElement Result = LVIImpl->getValueInBlock( const_cast(&Arg), const_cast(BB)); if (Result.isUndefined()) continue; @@ -2036,7 +1822,7 @@ void LazyValueInfoAnnotatedWriter::emitInstructionAnnot( auto printResult = [&](const BasicBlock *BB) { if (!BlocksContainingLVI.insert(BB).second) return; - LVILatticeVal Result = LVIImpl->getValueInBlock( + ValueLatticeElement Result = LVIImpl->getValueInBlock( const_cast(I), const_cast(BB)); OS << "; LatticeVal for: '" << *I << "' in BB: '"; BB->printAsOperand(OS, false); diff --git a/lib/Analysis/ValueLattice.cpp b/lib/Analysis/ValueLattice.cpp new file mode 100644 index 00000000000..7de437ca480 --- /dev/null +++ b/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 ValueLatticeElement &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 diff --git a/unittests/Analysis/CMakeLists.txt b/unittests/Analysis/CMakeLists.txt index ed10ff8a9b0..fabef12126c 100644 --- a/unittests/Analysis/CMakeLists.txt +++ b/unittests/Analysis/CMakeLists.txt @@ -14,6 +14,7 @@ add_llvm_unittest(AnalysisTests CFGTest.cpp CGSCCPassManagerTest.cpp GlobalsModRefTest.cpp + ValueLatticeTest.cpp LazyCallGraphTest.cpp LoopInfoTest.cpp MemoryBuiltinsTest.cpp diff --git a/unittests/Analysis/ValueLatticeTest.cpp b/unittests/Analysis/ValueLatticeTest.cpp new file mode 100644 index 00000000000..3e410256414 --- /dev/null +++ b/unittests/Analysis/ValueLatticeTest.cpp @@ -0,0 +1,148 @@ +//===- ValueLatticeTest.cpp - ScalarEvolution unit tests --------------===// +// +// 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" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/ConstantRange.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Module.h" +#include "gtest/gtest.h" + +namespace llvm { +namespace { + +// We use this fixture to ensure that we clean up ScalarEvolution before +// deleting the PassManager. +class ValueLatticeTest : public testing::Test { +protected: + LLVMContext Context; + Module M; + + ValueLatticeTest() : M("", Context) {} +}; + +TEST_F(ValueLatticeTest, ValueLatticeGetters) { + auto I32Ty = IntegerType::get(Context, 32); + auto *C1 = ConstantInt::get(I32Ty, 1); + + EXPECT_TRUE(ValueLatticeElement::get(C1).isConstantRange()); + EXPECT_TRUE( + ValueLatticeElement::getRange({C1->getValue()}).isConstantRange()); + EXPECT_TRUE(ValueLatticeElement::getOverdefined().isOverdefined()); + + auto FloatTy = Type::getFloatTy(Context); + auto *C2 = ConstantFP::get(FloatTy, 1.1); + EXPECT_TRUE(ValueLatticeElement::get(C2).isConstant()); + EXPECT_TRUE(ValueLatticeElement::getNot(C2).isNotConstant()); +} + +TEST_F(ValueLatticeTest, MergeIn) { + auto I32Ty = IntegerType::get(Context, 32); + auto *C1 = ConstantInt::get(I32Ty, 1); + + // Merge to lattice values with equal integer constant. + auto LV1 = ValueLatticeElement::get(C1); + LV1.mergeIn(ValueLatticeElement::get(C1), M.getDataLayout()); + EXPECT_TRUE(LV1.isConstantRange()); + EXPECT_EQ(LV1.asConstantInteger().getValue().getLimitedValue(), 1U); + + // Merge LV1 with different integer constant. + LV1.mergeIn(ValueLatticeElement::get(ConstantInt::get(I32Ty, 99)), + M.getDataLayout()); + EXPECT_TRUE(LV1.isConstantRange()); + EXPECT_EQ(LV1.getConstantRange().getLower().getLimitedValue(), 1U); + EXPECT_EQ(LV1.getConstantRange().getUpper().getLimitedValue(), 100U); + + // Merge LV1 in undefined value. + ValueLatticeElement LV2; + LV2.mergeIn(LV1, M.getDataLayout()); + EXPECT_TRUE(LV1.isConstantRange()); + EXPECT_EQ(LV1.getConstantRange().getLower().getLimitedValue(), 1U); + EXPECT_EQ(LV1.getConstantRange().getUpper().getLimitedValue(), 100U); + EXPECT_TRUE(LV2.isConstantRange()); + EXPECT_EQ(LV2.getConstantRange().getLower().getLimitedValue(), 1U); + EXPECT_EQ(LV2.getConstantRange().getUpper().getLimitedValue(), 100U); + + // Merge with overdefined. + LV1.mergeIn(ValueLatticeElement::getOverdefined(), M.getDataLayout()); + EXPECT_TRUE(LV1.isOverdefined()); +} + +TEST_F(ValueLatticeTest, satisfiesPredicateIntegers) { + auto I32Ty = IntegerType::get(Context, 32); + auto *C1 = ConstantInt::get(I32Ty, 1); + auto LV1 = ValueLatticeElement::get(C1); + + // Check satisfiesPredicate for equal integer constants. + EXPECT_TRUE(LV1.satisfiesPredicate(CmpInst::ICMP_EQ, LV1)); + EXPECT_TRUE(LV1.satisfiesPredicate(CmpInst::ICMP_SGE, LV1)); + EXPECT_TRUE(LV1.satisfiesPredicate(CmpInst::ICMP_SLE, LV1)); + EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::ICMP_NE, LV1)); + EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::ICMP_SLT, LV1)); + EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::ICMP_SGT, LV1)); + + auto LV2 = + ValueLatticeElement::getRange({APInt(32, 10, true), APInt(32, 20, true)}); + // Check satisfiesPredicate with distinct integer ranges. + EXPECT_TRUE(LV1.satisfiesPredicate(CmpInst::ICMP_SLT, LV2)); + EXPECT_TRUE(LV1.satisfiesPredicate(CmpInst::ICMP_SLE, LV2)); + EXPECT_TRUE(LV1.satisfiesPredicate(CmpInst::ICMP_NE, LV2)); + EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::ICMP_EQ, LV2)); + EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::ICMP_SGE, LV2)); + EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::ICMP_SGT, LV2)); + + auto LV3 = + ValueLatticeElement::getRange({APInt(32, 15, true), APInt(32, 19, true)}); + // Check satisfiesPredicate with a subset integer ranges. + EXPECT_FALSE(LV2.satisfiesPredicate(CmpInst::ICMP_SLT, LV3)); + EXPECT_FALSE(LV2.satisfiesPredicate(CmpInst::ICMP_SLE, LV3)); + EXPECT_FALSE(LV2.satisfiesPredicate(CmpInst::ICMP_NE, LV3)); + EXPECT_FALSE(LV2.satisfiesPredicate(CmpInst::ICMP_EQ, LV3)); + EXPECT_FALSE(LV2.satisfiesPredicate(CmpInst::ICMP_SGE, LV3)); + EXPECT_FALSE(LV2.satisfiesPredicate(CmpInst::ICMP_SGT, LV3)); + + auto LV4 = + ValueLatticeElement::getRange({APInt(32, 15, true), APInt(32, 25, true)}); + // Check satisfiesPredicate with overlapping integer ranges. + EXPECT_FALSE(LV3.satisfiesPredicate(CmpInst::ICMP_SLT, LV4)); + EXPECT_FALSE(LV3.satisfiesPredicate(CmpInst::ICMP_SLE, LV4)); + EXPECT_FALSE(LV3.satisfiesPredicate(CmpInst::ICMP_NE, LV4)); + EXPECT_FALSE(LV3.satisfiesPredicate(CmpInst::ICMP_EQ, LV4)); + EXPECT_FALSE(LV3.satisfiesPredicate(CmpInst::ICMP_SGE, LV4)); + EXPECT_FALSE(LV3.satisfiesPredicate(CmpInst::ICMP_SGT, LV4)); +} + +TEST_F(ValueLatticeTest, satisfiesPredicateFloat) { + auto FloatTy = IntegerType::getFloatTy(Context); + auto *C1 = ConstantFP::get(FloatTy, 1.0); + auto LV1 = ValueLatticeElement::get(C1); + auto LV2 = ValueLatticeElement::get(C1); + + // Check satisfiesPredicate for equal floating point constants. + EXPECT_TRUE(LV1.satisfiesPredicate(CmpInst::FCMP_OEQ, LV2)); + EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OGE, LV2)); + EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OLE, LV2)); + EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_ONE, LV2)); + EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OLT, LV2)); + EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OGT, LV2)); + + LV1.mergeIn(ValueLatticeElement::get(ConstantFP::get(FloatTy, 2.2)), + M.getDataLayout()); + EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OEQ, LV2)); + EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OGE, LV2)); + EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OLE, LV2)); + EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_ONE, LV2)); + EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OLT, LV2)); + EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OGT, LV2)); +} + +} // end anonymous namespace +} // end namespace llvm -- 2.11.0