/// LazyValueInfoCache - This is the cache kept by LazyValueInfo which
/// maintains information about queries across the clients' queries.
class LazyValueInfoCache {
- public:
+ private:
/// BlockCacheEntryTy - This is a computed lattice value at the end of the
/// specified basic block for a Value* that depends on context.
typedef std::pair<BasicBlock*, LVILatticeVal> BlockCacheEntryTy;
/// entries, allowing us to do a lookup with a binary search.
typedef DenseMap<BasicBlock*, LVILatticeVal> ValueCacheEntryTy;
- private:
/// ValueCache - This is all of the cached information for all values,
/// mapped from Value* to key information.
DenseMap<Value*, ValueCacheEntryTy> ValueCache;
/// values that are over-defined at the end of that block. This is required
/// for cache updating.
DenseSet<std::pair<BasicBlock*, Value*> > OverDefinedCache;
+
+ LVILatticeVal getBlockValue(ValueCacheEntryTy &Cache, BasicBlock *BB);
+ LVILatticeVal getEdgeValue(ValueCacheEntryTy &Cache,
+ BasicBlock *Pred, BasicBlock *Succ);
+ LVILatticeVal &getCachedEntryForBlock(ValueCacheEntryTy &Cache,
+ BasicBlock *BB);
+
+ /************* Begin Per-Query State *************/
+ /// This is the current value being queried for.
+ Value *Val;
+
+ /// This is all of the cached information about this value.
+ //ValueCacheEntryTy *Cache;
+
+ /// NewBlocks - This is a mapping of the new BasicBlocks which have been
+ /// added to cache but that are not in sorted order.
+ DenseSet<BasicBlock*> NewBlockInfo;
+
+ /// QuerySetup - An RAII helper to construct and tear-down per-query
+ /// temporary state.
+ struct QuerySetup {
+ LazyValueInfoCache &Owner;
+ QuerySetup(LazyValueInfoCache &O, Value* Val) : Owner(O) {
+ assert(!Owner.Val && "Per-query info not cleared?");
+ Owner.Val = Val;
+ assert(Owner.NewBlockInfo.empty() && "Leaked block info!");
+ }
+
+ ~QuerySetup() {
+ // When the query is done, insert the newly discovered facts into the
+ // cache in sorted order.
+ LazyValueInfoCache::ValueCacheEntryTy Cache =
+ Owner.ValueCache[Owner.Val];
+ for (DenseSet<BasicBlock*>::iterator I = Owner.NewBlockInfo.begin(),
+ E = Owner.NewBlockInfo.end(); I != E; ++I) {
+ if (Cache[*I].isOverdefined())
+ Owner.OverDefinedCache.insert(std::make_pair(*I, Owner.Val));
+ }
+
+ // Reset Per-Query State
+ Owner.Val = 0;
+ Owner.NewBlockInfo.clear();
+ }
+ };
+ /************* End Per-Query State *************/
+
public:
+ LazyValueInfoCache() : Val(0) { }
/// getValueInBlock - This is the query interface to determine the lattice
/// value for the specified Value* at the end of the specified block.
};
} // end anonymous namespace
-namespace {
- struct BlockCacheEntryComparator {
- static int Compare(const void *LHSv, const void *RHSv) {
- const LazyValueInfoCache::BlockCacheEntryTy *LHS =
- static_cast<const LazyValueInfoCache::BlockCacheEntryTy *>(LHSv);
- const LazyValueInfoCache::BlockCacheEntryTy *RHS =
- static_cast<const LazyValueInfoCache::BlockCacheEntryTy *>(RHSv);
- if (LHS->first < RHS->first)
- return -1;
- if (LHS->first > RHS->first)
- return 1;
- return 0;
- }
-
- bool operator()(const LazyValueInfoCache::BlockCacheEntryTy &LHS,
- const LazyValueInfoCache::BlockCacheEntryTy &RHS) const {
- return LHS.first < RHS.first;
- }
- };
-}
-
-//===----------------------------------------------------------------------===//
-// LVIQuery Impl
-//===----------------------------------------------------------------------===//
-
-namespace {
- /// LVIQuery - This is a transient object that exists while a query is
- /// being performed.
- ///
- /// TODO: Reuse LVIQuery instead of recreating it for every query, this avoids
- /// reallocation of the densemap on every query.
- class LVIQuery {
- typedef LazyValueInfoCache::BlockCacheEntryTy BlockCacheEntryTy;
- typedef LazyValueInfoCache::ValueCacheEntryTy ValueCacheEntryTy;
-
- /// This is the current value being queried for.
- Value *Val;
-
- /// This is all of the cached information about this value.
- ValueCacheEntryTy &Cache;
-
- /// This tracks, for each block, what values are overdefined.
- DenseSet<std::pair<BasicBlock*, Value*> > &OverDefinedCache;
-
- /// NewBlocks - This is a mapping of the new BasicBlocks which have been
- /// added to cache but that are not in sorted order.
- DenseSet<BasicBlock*> NewBlockInfo;
- public:
-
- LVIQuery(Value *V, ValueCacheEntryTy &VC,
- DenseSet<std::pair<BasicBlock*, Value*> > &ODC)
- : Val(V), Cache(VC), OverDefinedCache(ODC) {
- }
-
- ~LVIQuery() {
- // When the query is done, insert the newly discovered facts into the
- // cache in sorted order.
- if (NewBlockInfo.empty()) return;
-
- for (DenseSet<BasicBlock*>::iterator I = NewBlockInfo.begin(),
- E = NewBlockInfo.end(); I != E; ++I) {
- if (Cache[*I].isOverdefined())
- OverDefinedCache.insert(std::make_pair(*I, Val));
- }
- }
-
- LVILatticeVal getBlockValue(BasicBlock *BB);
- LVILatticeVal getEdgeValue(BasicBlock *FromBB, BasicBlock *ToBB);
-
- private:
- LVILatticeVal &getCachedEntryForBlock(BasicBlock *BB);
- };
-} // end anonymous namespace
/// getCachedEntryForBlock - See if we already have a value for this block. If
/// so, return it, otherwise create a new entry in the Cache map to use.
-LVILatticeVal &LVIQuery::getCachedEntryForBlock(BasicBlock *BB) {
+LVILatticeVal&
+LazyValueInfoCache::getCachedEntryForBlock(ValueCacheEntryTy &Cache,
+ BasicBlock *BB) {
NewBlockInfo.insert(BB);
return Cache[BB];
}
-LVILatticeVal LVIQuery::getBlockValue(BasicBlock *BB) {
+LVILatticeVal
+LazyValueInfoCache::getBlockValue(ValueCacheEntryTy &Cache, BasicBlock *BB) {
// See if we already have a value for this block.
- LVILatticeVal &BBLV = getCachedEntryForBlock(BB);
+ LVILatticeVal &BBLV = getCachedEntryForBlock(Cache, BB);
// If we've already computed this block's value, return it.
if (!BBLV.isUndefined()) {
// Loop over all of our predecessors, merging what we know from them into
// result.
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
- Result.mergeIn(getEdgeValue(*PI, BB));
+ Result.mergeIn(getEdgeValue(Cache, *PI, BB));
// If we hit overdefined, exit early. The BlockVals entry is already set
// to overdefined.
// Return the merged value, which is more precise than 'overdefined'.
assert(!Result.isOverdefined());
- return getCachedEntryForBlock(BB) = Result;
+ return getCachedEntryForBlock(Cache, BB) = Result;
}
// If this value is defined by an instruction in this block, we have to
LVILatticeVal Result;
Result.markOverdefined();
- return getCachedEntryForBlock(BB) = Result;
+ return getCachedEntryForBlock(Cache, BB) = Result;
}
/// getEdgeValue - This method attempts to infer more complex
-LVILatticeVal LVIQuery::getEdgeValue(BasicBlock *BBFrom, BasicBlock *BBTo) {
+LVILatticeVal LazyValueInfoCache::getEdgeValue(ValueCacheEntryTy &Cache,
+ BasicBlock *BBFrom, BasicBlock *BBTo) {
// TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
// know that v != 0.
if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
}
// Otherwise see if the value is known in the block.
- return getBlockValue(BBFrom);
+ return getBlockValue(Cache, BBFrom);
}
-
-//===----------------------------------------------------------------------===//
-// LazyValueInfoCache Impl
-//===----------------------------------------------------------------------===//
-
LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB) {
// If already a constant, there is nothing to compute.
if (Constant *VC = dyn_cast<Constant>(V))
DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
<< BB->getName() << "'\n");
- LVILatticeVal Result = LVIQuery(V, ValueCache[V],
- OverDefinedCache).getBlockValue(BB);
+ QuerySetup QS(*this, V);
+ ValueCacheEntryTy &Cache = ValueCache[V];
+ LVILatticeVal Result = getBlockValue(Cache, BB);
DEBUG(dbgs() << " Result = " << Result << "\n");
return Result;
DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
<< FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
- LVILatticeVal Result =
- LVIQuery(V, ValueCache[V],
- OverDefinedCache).getEdgeValue(FromBB, ToBB);
+ QuerySetup QS(*this, V);
+ ValueCacheEntryTy &Cache = ValueCache[V];
+ LVILatticeVal Result = getEdgeValue(Cache, FromBB, ToBB);
DEBUG(dbgs() << " Result = " << Result << "\n");
projects / oota-llvm.git / commitdiff