aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/LazyValueInfo.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Analysis/LazyValueInfo.cpp')
-rw-r--r--lib/Analysis/LazyValueInfo.cpp232
1 files changed, 189 insertions, 43 deletions
diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp
index d442310476cf..ad01f7f2f215 100644
--- a/lib/Analysis/LazyValueInfo.cpp
+++ b/lib/Analysis/LazyValueInfo.cpp
@@ -19,6 +19,7 @@
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/AssemblyAnnotationWriter.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
@@ -31,6 +32,7 @@
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/FormattedStream.h"
#include "llvm/Support/raw_ostream.h"
#include <map>
#include <stack>
@@ -39,6 +41,10 @@ using namespace PatternMatch;
#define DEBUG_TYPE "lazy-value-info"
+// This is the number of worklist items we will process to try to discover an
+// answer for a given value.
+static const unsigned MaxProcessedPerValue = 500;
+
char LazyValueInfoWrapperPass::ID = 0;
INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info",
"Lazy Value Information Analysis", false, true)
@@ -358,6 +364,7 @@ namespace {
/// This is the cache kept by LazyValueInfo which
/// maintains information about queries across the clients' queries.
class LazyValueInfoCache {
+ friend class LazyValueInfoAnnotatedWriter;
/// This is all of the cached block information for exactly one Value*.
/// The entries are sorted by the BasicBlock* of the
/// entries, allowing us to do a lookup with a binary search.
@@ -366,22 +373,23 @@ namespace {
struct ValueCacheEntryTy {
ValueCacheEntryTy(Value *V, LazyValueInfoCache *P) : Handle(V, P) {}
LVIValueHandle Handle;
- SmallDenseMap<AssertingVH<BasicBlock>, LVILatticeVal, 4> BlockVals;
+ SmallDenseMap<PoisoningVH<BasicBlock>, LVILatticeVal, 4> BlockVals;
};
- /// This is all of the cached information for all values,
- /// mapped from Value* to key information.
- DenseMap<Value *, std::unique_ptr<ValueCacheEntryTy>> ValueCache;
-
/// This tracks, on a per-block basis, the set of values that are
/// over-defined at the end of that block.
- typedef DenseMap<AssertingVH<BasicBlock>, SmallPtrSet<Value *, 4>>
+ typedef DenseMap<PoisoningVH<BasicBlock>, SmallPtrSet<Value *, 4>>
OverDefinedCacheTy;
- OverDefinedCacheTy OverDefinedCache;
-
/// Keep track of all blocks that we have ever seen, so we
/// don't spend time removing unused blocks from our caches.
- DenseSet<AssertingVH<BasicBlock> > SeenBlocks;
+ DenseSet<PoisoningVH<BasicBlock> > SeenBlocks;
+
+ protected:
+ /// This is all of the cached information for all values,
+ /// mapped from Value* to key information.
+ DenseMap<Value *, std::unique_ptr<ValueCacheEntryTy>> ValueCache;
+ OverDefinedCacheTy OverDefinedCache;
+
public:
void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) {
@@ -435,6 +443,7 @@ namespace {
return BBI->second;
}
+ void printCache(Function &F, raw_ostream &OS);
/// clear - Empty the cache.
void clear() {
SeenBlocks.clear();
@@ -458,16 +467,71 @@ namespace {
};
}
+
+namespace {
+
+ /// An assembly annotator class to print LazyValueCache information in
+ /// comments.
+ class LazyValueInfoAnnotatedWriter : public AssemblyAnnotationWriter {
+ const LazyValueInfoCache* LVICache;
+
+ public:
+ LazyValueInfoAnnotatedWriter(const LazyValueInfoCache *L) : LVICache(L) {}
+
+ virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
+ formatted_raw_ostream &OS) {
+ auto ODI = LVICache->OverDefinedCache.find(const_cast<BasicBlock*>(BB));
+ if (ODI == LVICache->OverDefinedCache.end())
+ return;
+ OS << "; OverDefined values for block are: \n";
+ for (auto *V : ODI->second)
+ OS << ";" << *V << "\n";
+
+ // Find if there are latticevalues defined for arguments of the function.
+ auto *F = const_cast<Function *>(BB->getParent());
+ for (auto &Arg : F->args()) {
+ auto VI = LVICache->ValueCache.find_as(&Arg);
+ if (VI == LVICache->ValueCache.end())
+ continue;
+ auto BBI = VI->second->BlockVals.find(const_cast<BasicBlock *>(BB));
+ if (BBI != VI->second->BlockVals.end())
+ OS << "; CachedLatticeValue for: '" << *VI->first << "' is: '"
+ << BBI->second << "'\n";
+ }
+ }
+
+ virtual void emitInstructionAnnot(const Instruction *I,
+ formatted_raw_ostream &OS) {
+
+ auto VI = LVICache->ValueCache.find_as(const_cast<Instruction *>(I));
+ if (VI == LVICache->ValueCache.end())
+ return;
+ OS << "; CachedLatticeValues for: '" << *VI->first << "'\n";
+ for (auto &BV : VI->second->BlockVals) {
+ OS << "; at beginning of BasicBlock: '";
+ BV.first->printAsOperand(OS, false);
+ OS << "' LatticeVal: '" << BV.second << "' \n";
+ }
+ }
+};
+}
+
+void LazyValueInfoCache::printCache(Function &F, raw_ostream &OS) {
+ LazyValueInfoAnnotatedWriter Writer(this);
+ F.print(OS, &Writer);
+
+}
+
void LazyValueInfoCache::eraseValue(Value *V) {
- SmallVector<AssertingVH<BasicBlock>, 4> ToErase;
- for (auto &I : OverDefinedCache) {
- SmallPtrSetImpl<Value *> &ValueSet = I.second;
+ for (auto I = OverDefinedCache.begin(), E = OverDefinedCache.end(); I != E;) {
+ // Copy and increment the iterator immediately so we can erase behind
+ // ourselves.
+ auto Iter = I++;
+ SmallPtrSetImpl<Value *> &ValueSet = Iter->second;
ValueSet.erase(V);
if (ValueSet.empty())
- ToErase.push_back(I.first);
+ OverDefinedCache.erase(Iter);
}
- for (auto &BB : ToErase)
- OverDefinedCache.erase(BB);
ValueCache.erase(V);
}
@@ -480,7 +544,7 @@ void LVIValueHandle::deleted() {
void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
// Shortcut if we have never seen this block.
- DenseSet<AssertingVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
+ DenseSet<PoisoningVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
if (I == SeenBlocks.end())
return;
SeenBlocks.erase(I);
@@ -563,7 +627,7 @@ namespace {
/// This stack holds the state of the value solver during a query.
/// It basically emulates the callstack of the naive
/// recursive value lookup process.
- std::stack<std::pair<BasicBlock*, Value*> > BlockValueStack;
+ SmallVector<std::pair<BasicBlock*, Value*>, 8> BlockValueStack;
/// Keeps track of which block-value pairs are in BlockValueStack.
DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
@@ -576,7 +640,7 @@ namespace {
DEBUG(dbgs() << "PUSH: " << *BV.second << " in " << BV.first->getName()
<< "\n");
- BlockValueStack.push(BV);
+ BlockValueStack.push_back(BV);
return true;
}
@@ -629,6 +693,11 @@ namespace {
TheCache.clear();
}
+ /// Printing the LazyValueInfoCache.
+ void printCache(Function &F, raw_ostream &OS) {
+ TheCache.printCache(F, OS);
+ }
+
/// This is part of the update interface to inform the cache
/// that a block has been deleted.
void eraseBlock(BasicBlock *BB) {
@@ -646,24 +715,50 @@ namespace {
} // end anonymous namespace
void LazyValueInfoImpl::solve() {
+ SmallVector<std::pair<BasicBlock *, Value *>, 8> StartingStack(
+ BlockValueStack.begin(), BlockValueStack.end());
+
+ unsigned processedCount = 0;
while (!BlockValueStack.empty()) {
- std::pair<BasicBlock*, Value*> &e = BlockValueStack.top();
+ processedCount++;
+ // Abort if we have to process too many values to get a result for this one.
+ // Because of the design of the overdefined cache currently being per-block
+ // to avoid naming-related issues (IE it wants to try to give different
+ // results for the same name in different blocks), overdefined results don't
+ // get cached globally, which in turn means we will often try to rediscover
+ // the same overdefined result again and again. Once something like
+ // PredicateInfo is used in LVI or CVP, we should be able to make the
+ // overdefined cache global, and remove this throttle.
+ if (processedCount > MaxProcessedPerValue) {
+ DEBUG(dbgs() << "Giving up on stack because we are getting too deep\n");
+ // Fill in the original values
+ while (!StartingStack.empty()) {
+ std::pair<BasicBlock *, Value *> &e = StartingStack.back();
+ TheCache.insertResult(e.second, e.first,
+ LVILatticeVal::getOverdefined());
+ StartingStack.pop_back();
+ }
+ BlockValueSet.clear();
+ BlockValueStack.clear();
+ return;
+ }
+ std::pair<BasicBlock *, Value *> e = BlockValueStack.back();
assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
if (solveBlockValue(e.second, e.first)) {
// The work item was completely processed.
- assert(BlockValueStack.top() == e && "Nothing should have been pushed!");
+ assert(BlockValueStack.back() == e && "Nothing should have been pushed!");
assert(TheCache.hasCachedValueInfo(e.second, e.first) &&
"Result should be in cache!");
DEBUG(dbgs() << "POP " << *e.second << " in " << e.first->getName()
<< " = " << TheCache.getCachedValueInfo(e.second, e.first) << "\n");
- BlockValueStack.pop();
+ BlockValueStack.pop_back();
BlockValueSet.erase(e);
} else {
// More work needs to be done before revisiting.
- assert(BlockValueStack.top() != e && "Stack should have been pushed!");
+ assert(BlockValueStack.back() != e && "Stack should have been pushed!");
}
}
}
@@ -839,13 +934,19 @@ bool LazyValueInfoImpl::solveBlockValueNonLocal(LVILatticeVal &BBLV,
}
// Loop over all of our predecessors, merging what we know from them into
- // result.
- bool EdgesMissing = false;
+ // result. If we encounter an unexplored predecessor, we eagerly explore it
+ // in a depth first manner. In practice, this has the effect of discovering
+ // paths we can't analyze eagerly without spending compile times analyzing
+ // other paths. This heuristic benefits from the fact that predecessors are
+ // frequently arranged such that dominating ones come first and we quickly
+ // find a path to function entry. TODO: We should consider explicitly
+ // 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;
- EdgesMissing |= !getEdgeValue(Val, *PI, BB, EdgeResult);
- if (EdgesMissing)
- continue;
+ if (!getEdgeValue(Val, *PI, BB, EdgeResult))
+ // Explore that input, then return here
+ return false;
Result.mergeIn(EdgeResult, DL);
@@ -866,8 +967,6 @@ bool LazyValueInfoImpl::solveBlockValueNonLocal(LVILatticeVal &BBLV,
return true;
}
}
- if (EdgesMissing)
- return false;
// Return the merged value, which is more precise than 'overdefined'.
assert(!Result.isOverdefined());
@@ -880,8 +979,8 @@ bool LazyValueInfoImpl::solveBlockValuePHINode(LVILatticeVal &BBLV,
LVILatticeVal Result; // Start Undefined.
// Loop over all of our predecessors, merging what we know from them into
- // result.
- bool EdgesMissing = false;
+ // result. See the comment about the chosen traversal order in
+ // solveBlockValueNonLocal; the same reasoning applies here.
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
BasicBlock *PhiBB = PN->getIncomingBlock(i);
Value *PhiVal = PN->getIncomingValue(i);
@@ -889,9 +988,9 @@ bool LazyValueInfoImpl::solveBlockValuePHINode(LVILatticeVal &BBLV,
// 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.
- EdgesMissing |= !getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN);
- if (EdgesMissing)
- continue;
+ if (!getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN))
+ // Explore that input, then return here
+ return false;
Result.mergeIn(EdgeResult, DL);
@@ -905,8 +1004,6 @@ bool LazyValueInfoImpl::solveBlockValuePHINode(LVILatticeVal &BBLV,
return true;
}
}
- if (EdgesMissing)
- return false;
// Return the merged value, which is more precise than 'overdefined'.
assert(!Result.isOverdefined() && "Possible PHI in entry block?");
@@ -1333,14 +1430,14 @@ static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
unsigned BitWidth = Val->getType()->getIntegerBitWidth();
ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
- for (SwitchInst::CaseIt i : SI->cases()) {
- ConstantRange EdgeVal(i.getCaseValue()->getValue());
+ for (auto Case : SI->cases()) {
+ ConstantRange EdgeVal(Case.getCaseValue()->getValue());
if (DefaultCase) {
// It is possible that the default destination is the destination of
// some cases. There is no need to perform difference for those cases.
- if (i.getCaseSuccessor() != BBTo)
+ if (Case.getCaseSuccessor() != BBTo)
EdgesVals = EdgesVals.difference(EdgeVal);
- } else if (i.getCaseSuccessor() == BBTo)
+ } else if (Case.getCaseSuccessor() == BBTo)
EdgesVals = EdgesVals.unionWith(EdgeVal);
}
Result = LVILatticeVal::getRange(std::move(EdgesVals));
@@ -1352,8 +1449,8 @@ 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,
- Instruction *CxtI) {
+ BasicBlock *BBTo, LVILatticeVal &Result,
+ Instruction *CxtI) {
// If already a constant, there is nothing to compute.
if (Constant *VC = dyn_cast<Constant>(Val)) {
Result = LVILatticeVal::get(VC);
@@ -1503,6 +1600,18 @@ void LazyValueInfo::releaseMemory() {
}
}
+bool LazyValueInfo::invalidate(Function &F, const PreservedAnalyses &PA,
+ FunctionAnalysisManager::Invalidator &Inv) {
+ // We need to invalidate if we have either failed to preserve this analyses
+ // result directly or if any of its dependencies have been invalidated.
+ auto PAC = PA.getChecker<LazyValueAnalysis>();
+ if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
+ (DT && Inv.invalidate<DominatorTreeAnalysis>(F, PA)))
+ return true;
+
+ return false;
+}
+
void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); }
LazyValueInfo LazyValueAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
@@ -1510,7 +1619,7 @@ LazyValueInfo LazyValueAnalysis::run(Function &F, FunctionAnalysisManager &FAM)
auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
- return LazyValueInfo(&AC, &TLI, DT);
+ return LazyValueInfo(&AC, &F.getParent()->getDataLayout(), &TLI, DT);
}
/// Returns true if we can statically tell that this value will never be a
@@ -1780,3 +1889,40 @@ void LazyValueInfo::eraseBlock(BasicBlock *BB) {
getImpl(PImpl, AC, &DL, DT).eraseBlock(BB);
}
}
+
+
+void LazyValueInfo::printCache(Function &F, raw_ostream &OS) {
+ if (PImpl) {
+ getImpl(PImpl, AC, DL, DT).printCache(F, OS);
+ }
+}
+
+namespace {
+// Printer class for LazyValueInfo results.
+class LazyValueInfoPrinter : public FunctionPass {
+public:
+ static char ID; // Pass identification, replacement for typeid
+ LazyValueInfoPrinter() : FunctionPass(ID) {
+ initializeLazyValueInfoPrinterPass(*PassRegistry::getPassRegistry());
+ }
+
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
+ AU.setPreservesAll();
+ AU.addRequired<LazyValueInfoWrapperPass>();
+ }
+
+ bool runOnFunction(Function &F) override {
+ dbgs() << "LVI for function '" << F.getName() << "':\n";
+ auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
+ LVI.printCache(F, dbgs());
+ return false;
+ }
+};
+}
+
+char LazyValueInfoPrinter::ID = 0;
+INITIALIZE_PASS_BEGIN(LazyValueInfoPrinter, "print-lazy-value-info",
+ "Lazy Value Info Printer Pass", false, false)
+INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
+INITIALIZE_PASS_END(LazyValueInfoPrinter, "print-lazy-value-info",
+ "Lazy Value Info Printer Pass", false, false)
generated by cgit v1.2.3 (git 2.25.1) at 2025-08-11 19:33:07 +0000