#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
+#include "llvm/IntrinsicInst.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Support/CFG.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLExtras.h"
#include <map>
-#include <set>
#include <stack>
using namespace llvm;
} // 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";
//===----------------------------------------------------------------------===//
namespace {
+ /// LVIValueHandle - A callback value handle update the cache when
+ /// values are erased.
+ class LazyValueInfoCache;
+ struct LVIValueHandle : public CallbackVH {
+ LazyValueInfoCache *Parent;
+
+ LVIValueHandle(Value *V, LazyValueInfoCache *P)
+ : CallbackVH(V), Parent(P) { }
+
+ void deleted();
+ void allUsesReplacedWith(Value *V) {
+ deleted();
+ }
+ };
+}
+
+namespace llvm {
+ template<>
+ struct DenseMapInfo<LVIValueHandle> {
+ typedef DenseMapInfo<Value*> PointerInfo;
+ static inline LVIValueHandle getEmptyKey() {
+ return LVIValueHandle(PointerInfo::getEmptyKey(),
+ static_cast<LazyValueInfoCache*>(0));
+ }
+ static inline LVIValueHandle getTombstoneKey() {
+ return LVIValueHandle(PointerInfo::getTombstoneKey(),
+ static_cast<LazyValueInfoCache*>(0));
+ }
+ static unsigned getHashValue(const LVIValueHandle &Val) {
+ return PointerInfo::getHashValue(Val);
+ }
+ static bool isEqual(const LVIValueHandle &LHS, const LVIValueHandle &RHS) {
+ return LHS == RHS;
+ }
+ };
+
+ template<>
+ struct DenseMapInfo<std::pair<AssertingVH<BasicBlock>, Value*> > {
+ typedef std::pair<AssertingVH<BasicBlock>, Value*> PairTy;
+ typedef DenseMapInfo<AssertingVH<BasicBlock> > APointerInfo;
+ typedef DenseMapInfo<Value*> BPointerInfo;
+ static inline PairTy getEmptyKey() {
+ return std::make_pair(APointerInfo::getEmptyKey(),
+ BPointerInfo::getEmptyKey());
+ }
+ static inline PairTy getTombstoneKey() {
+ return std::make_pair(APointerInfo::getTombstoneKey(),
+ BPointerInfo::getTombstoneKey());
+ }
+ static unsigned getHashValue( const PairTy &Val) {
+ return APointerInfo::getHashValue(Val.first) ^
+ BPointerInfo::getHashValue(Val.second);
+ }
+ static bool isEqual(const PairTy &LHS, const PairTy &RHS) {
+ return APointerInfo::isEqual(LHS.first, RHS.first) &&
+ BPointerInfo::isEqual(LHS.second, RHS.second);
+ }
+ };
+}
+
+namespace {
/// LazyValueInfoCache - This is the cache kept by LazyValueInfo which
/// maintains information about queries across the clients' queries.
class LazyValueInfoCache {
- public:
/// ValueCacheEntryTy - 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.
typedef std::map<AssertingVH<BasicBlock>, LVILatticeVal> ValueCacheEntryTy;
- private:
- /// LVIValueHandle - A callback value handle update the cache when
- /// values are erased.
- struct LVIValueHandle : public CallbackVH {
- LazyValueInfoCache *Parent;
-
- LVIValueHandle(Value *V, LazyValueInfoCache *P)
- : CallbackVH(V), Parent(P) { }
-
- void deleted();
- void allUsesReplacedWith(Value *V) {
- deleted();
- }
- };
-
/// ValueCache - This is all of the cached information for all values,
/// mapped from Value* to key information.
- std::map<LVIValueHandle, ValueCacheEntryTy> ValueCache;
+ DenseMap<LVIValueHandle, ValueCacheEntryTy> ValueCache;
/// OverDefinedCache - This tracks, on a per-block basis, the set of
/// values that are over-defined at the end of that block. This is required
/// for cache updating.
- std::set<std::pair<AssertingVH<BasicBlock>, Value*> > OverDefinedCache;
+ typedef std::pair<AssertingVH<BasicBlock>, Value*> OverDefinedPairTy;
+ DenseSet<OverDefinedPairTy> OverDefinedCache;
+
+ /// BlockValueStack - 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;
+
+ friend struct LVIValueHandle;
+
+ /// OverDefinedCacheUpdater - A helper object that ensures that the
+ /// OverDefinedCache is updated whenever solveBlockValue returns.
+ struct OverDefinedCacheUpdater {
+ LazyValueInfoCache *Parent;
+ Value *Val;
+ BasicBlock *BB;
+ LVILatticeVal &BBLV;
+
+ OverDefinedCacheUpdater(Value *V, BasicBlock *B, LVILatticeVal &LV,
+ LazyValueInfoCache *P)
+ : Parent(P), Val(V), BB(B), BBLV(LV) { }
+
+ bool markResult(bool changed) {
+ if (changed && BBLV.isOverdefined())
+ Parent->OverDefinedCache.insert(std::make_pair(BB, Val));
+ return changed;
+ }
+ };
+
+
LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
// 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 solveBlockValueNonLocal(Value *Val, BasicBlock *BB);
- bool solveBlockValuePHINode(PHINode *PN, BasicBlock *BB);
- bool solveBlockValueConstantRange(Instruction *BBI, BasicBlock *BB);
+ bool solveBlockValueNonLocal(LVILatticeVal &BBLV,
+ Value *Val, BasicBlock *BB);
+ bool solveBlockValuePHINode(LVILatticeVal &BBLV,
+ PHINode *PN, BasicBlock *BB);
+ bool solveBlockValueConstantRange(LVILatticeVal &BBLV,
+ Instruction *BBI, BasicBlock *BB);
void solve();
ValueCacheEntryTy &lookup(Value *V) {
return ValueCache[LVIValueHandle(V, this)];
}
-
- LVILatticeVal setBlockValue(Value *V, BasicBlock *BB, LVILatticeVal L,
- ValueCacheEntryTy &Cache) {
- if (L.isOverdefined()) OverDefinedCache.insert(std::make_pair(BB, V));
- return Cache[BB] = L;
- }
- LVILatticeVal setBlockValue(Value *V, BasicBlock *BB, LVILatticeVal L) {
- return setBlockValue(V, BB, L, lookup(V));
- }
-
- struct BlockStackEntry {
- BlockStackEntry(Value *Val, BasicBlock *BB) : Val(Val), BB(BB) {}
- Value *Val;
- BasicBlock *BB;
- };
- std::stack<BlockStackEntry> block_value_stack;
public:
/// getValueInBlock - This is the query interface to determine the lattice
};
} // end anonymous namespace
-void LazyValueInfoCache::LVIValueHandle::deleted() {
- for (std::set<std::pair<AssertingVH<BasicBlock>, Value*> >::iterator
+void LVIValueHandle::deleted() {
+ typedef std::pair<AssertingVH<BasicBlock>, Value*> OverDefinedPairTy;
+
+ SmallVector<OverDefinedPairTy, 4> ToErase;
+ for (DenseSet<OverDefinedPairTy>::iterator
I = Parent->OverDefinedCache.begin(),
E = Parent->OverDefinedCache.end();
- I != E; ) {
- std::set<std::pair<AssertingVH<BasicBlock>, Value*> >::iterator tmp = I;
- ++I;
- if (tmp->second == getValPtr())
- Parent->OverDefinedCache.erase(tmp);
+ I != E; ++I) {
+ if (I->second == getValPtr())
+ ToErase.push_back(*I);
}
+ for (SmallVector<OverDefinedPairTy, 4>::iterator I = ToErase.begin(),
+ E = ToErase.end(); I != E; ++I)
+ Parent->OverDefinedCache.erase(*I);
+
// This erasure deallocates *this, so it MUST happen after we're done
// using any and all members of *this.
Parent->ValueCache.erase(*this);
}
void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
- for (std::set<std::pair<AssertingVH<BasicBlock>, Value*> >::iterator
- I = OverDefinedCache.begin(), E = OverDefinedCache.end(); I != E; ) {
- std::set<std::pair<AssertingVH<BasicBlock>, Value*> >::iterator tmp = I;
- ++I;
- if (tmp->first == BB)
- OverDefinedCache.erase(tmp);
+ SmallVector<OverDefinedPairTy, 4> ToErase;
+ for (DenseSet<OverDefinedPairTy>::iterator I = OverDefinedCache.begin(),
+ E = OverDefinedCache.end(); I != E; ++I) {
+ if (I->first == BB)
+ ToErase.push_back(*I);
}
+
+ for (SmallVector<OverDefinedPairTy, 4>::iterator I = ToErase.begin(),
+ E = ToErase.end(); I != E; ++I)
+ OverDefinedCache.erase(*I);
- for (std::map<LVIValueHandle, ValueCacheEntryTy>::iterator
+ for (DenseMap<LVIValueHandle, ValueCacheEntryTy>::iterator
I = ValueCache.begin(), E = ValueCache.end(); I != E; ++I)
I->second.erase(BB);
}
void LazyValueInfoCache::solve() {
- while (!block_value_stack.empty()) {
- BlockStackEntry &e = block_value_stack.top();
- if (solveBlockValue(e.Val, e.BB))
- block_value_stack.pop();
+ while (!BlockValueStack.empty()) {
+ std::pair<BasicBlock*, Value*> &e = BlockValueStack.top();
+ if (solveBlockValue(e.second, e.first))
+ BlockValueStack.pop();
}
}
if (isa<Constant>(Val))
return true;
- return lookup(Val).count(BB);
+ LVIValueHandle ValHandle(Val, this);
+ if (!ValueCache.count(ValHandle)) return false;
+ return ValueCache[ValHandle].count(BB);
}
LVILatticeVal LazyValueInfoCache::getBlockValue(Value *Val, BasicBlock *BB) {
ValueCacheEntryTy &Cache = lookup(Val);
LVILatticeVal &BBLV = Cache[BB];
+
+ // OverDefinedCacheUpdater is a helper object that will update
+ // the OverDefinedCache for us when this method exits. Make sure to
+ // call markResult on it as we exist, passing a bool to indicate if the
+ // cache needs updating, i.e. if we have solve a new value or not.
+ OverDefinedCacheUpdater ODCacheUpdater(Val, BB, BBLV, this);
// If we've already computed this block's value, return it.
if (!BBLV.isUndefined()) {
DEBUG(dbgs() << " reuse BB '" << BB->getName() << "' val=" << BBLV <<'\n');
+
+ // Since we're reusing a cached value here, we don't need to update the
+ // OverDefinedCahce. The cache will have been properly updated
+ // whenever the cached value was inserted.
+ ODCacheUpdater.markResult(false);
return true;
}
Instruction *BBI = dyn_cast<Instruction>(Val);
if (BBI == 0 || BBI->getParent() != BB) {
- return solveBlockValueNonLocal(Val, BB);
+ return ODCacheUpdater.markResult(solveBlockValueNonLocal(BBLV, Val, BB));
}
if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
- return solveBlockValuePHINode(PN, BB);
+ return ODCacheUpdater.markResult(solveBlockValuePHINode(BBLV, PN, BB));
+ }
+
+ if (AllocaInst *AI = dyn_cast<AllocaInst>(BBI)) {
+ BBLV = LVILatticeVal::getNot(ConstantPointerNull::get(AI->getType()));
+ return ODCacheUpdater.markResult(true);
}
// We can only analyze the definitions of certain classes of instructions
!BBI->getType()->isIntegerTy()) {
DEBUG(dbgs() << " compute BB '" << BB->getName()
<< "' - overdefined because inst def found.\n");
- Result.markOverdefined();
- setBlockValue(Val, BB, Result, Cache);
- return true;
+ BBLV.markOverdefined();
+ return ODCacheUpdater.markResult(true);
}
// FIXME: We're currently limited to binops with a constant RHS. This should
DEBUG(dbgs() << " compute BB '" << BB->getName()
<< "' - overdefined because inst def found.\n");
- Result.markOverdefined();
- setBlockValue(Val, BB, Result, Cache);
- return true;
+ BBLV.markOverdefined();
+ return ODCacheUpdater.markResult(true);
}
- return solveBlockValueConstantRange(BBI, BB);
+ return ODCacheUpdater.markResult(solveBlockValueConstantRange(BBLV, BBI, BB));
}
static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
GetUnderlyingObject(S->getPointerOperand()) ==
GetUnderlyingObject(Ptr);
}
- // FIXME: llvm.memset, etc.
+ if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
+ if (MI->isVolatile()) return false;
+
+ // FIXME: check whether it has a valuerange that excludes zero?
+ ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
+ if (!Len || Len->isZero()) return false;
+
+ if (MI->getDestAddressSpace() == 0)
+ if (MI->getRawDest() == Ptr || MI->getDest() == Ptr)
+ return true;
+ if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
+ if (MTI->getSourceAddressSpace() == 0)
+ if (MTI->getRawSource() == Ptr || MTI->getSource() == Ptr)
+ return true;
+ }
return false;
}
-bool LazyValueInfoCache::solveBlockValueNonLocal(Value *Val, BasicBlock *BB) {
+bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV,
+ Value *Val, BasicBlock *BB) {
LVILatticeVal Result; // Start Undefined.
// If this is a pointer, and there's a load from that pointer in this BB,
// then we know that the pointer can't be NULL.
bool NotNull = false;
if (Val->getType()->isPointerTy()) {
- for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();BI != BE;++BI){
- if (InstructionDereferencesPointer(BI, Val)) {
- NotNull = true;
- break;
+ if (isa<AllocaInst>(Val)) {
+ NotNull = true;
+ } else {
+ for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();BI != BE;++BI){
+ if (InstructionDereferencesPointer(BI, Val)) {
+ NotNull = true;
+ break;
+ }
}
}
}
if (BB == &BB->getParent()->getEntryBlock()) {
assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
if (NotNull) {
-
const PointerType *PTy = cast<PointerType>(Val->getType());
+ PointerType *PTy = cast<PointerType>(Val->getType());
Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
} else {
Result.markOverdefined();
}
- setBlockValue(Val, BB, Result);
+ BBLV = Result;
return true;
}
// If we previously determined that this is a pointer that can't be null
// then return that rather than giving up entirely.
if (NotNull) {
-
const PointerType *PTy = cast<PointerType>(Val->getType());
+ PointerType *PTy = cast<PointerType>(Val->getType());
Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
}
- setBlockValue(Val, BB, Result);
+
+ BBLV = Result;
return true;
}
}
// Return the merged value, which is more precise than 'overdefined'.
assert(!Result.isOverdefined());
- setBlockValue(Val, BB, Result);
+ BBLV = Result;
return true;
}
-bool LazyValueInfoCache::solveBlockValuePHINode(PHINode *PN, BasicBlock *BB) {
+bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV,
+ PHINode *PN, BasicBlock *BB) {
LVILatticeVal Result; // Start Undefined.
// Loop over all of our predecessors, merging what we know from them into
if (Result.isOverdefined()) {
DEBUG(dbgs() << " compute BB '" << BB->getName()
<< "' - overdefined because of pred.\n");
- setBlockValue(PN, BB, Result);
+
+ BBLV = Result;
return true;
}
}
// Return the merged value, which is more precise than 'overdefined'.
assert(!Result.isOverdefined() && "Possible PHI in entry block?");
- setBlockValue(PN, BB, Result);
+ BBLV = Result;
return true;
}
-bool LazyValueInfoCache::solveBlockValueConstantRange(Instruction *BBI,
+bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
+ Instruction *BBI,
BasicBlock *BB) {
// Figure out the range of the LHS. If that fails, bail.
if (!hasBlockValue(BBI->getOperand(0), BB)) {
- block_value_stack.push(BlockStackEntry(BBI->getOperand(0), BB));
+ BlockValueStack.push(std::make_pair(BB, BBI->getOperand(0)));
return false;
}
- LVILatticeVal Result;
LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
if (!LHSVal.isConstantRange()) {
- Result.markOverdefined();
- setBlockValue(BBI, BB, Result);
+ BBLV.markOverdefined();
return true;
}
ConstantRange LHSRange = LHSVal.getConstantRange();
ConstantRange RHSRange(1);
- const IntegerType *ResultTy = cast<IntegerType>(BBI->getType());
+ IntegerType *ResultTy = cast<IntegerType>(BBI->getType());
if (isa<BinaryOperator>(BBI)) {
if (ConstantInt *RHS = dyn_cast<ConstantInt>(BBI->getOperand(1))) {
RHSRange = ConstantRange(RHS->getValue());
} else {
- Result.markOverdefined();
- setBlockValue(BBI, BB, Result);
+ BBLV.markOverdefined();
return true;
}
}
// 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.
+ LVILatticeVal Result;
switch (BBI->getOpcode()) {
case Instruction::Add:
Result.markConstantRange(LHSRange.add(RHSRange));
break;
}
- setBlockValue(BBI, BB, Result);
+ BBLV = Result;
return true;
}
if (!isTrueDest) TrueValues = TrueValues.inverse();
// Figure out the possible values of the query BEFORE this branch.
+ if (!hasBlockValue(Val, BBFrom)) {
+ BlockValueStack.push(std::make_pair(BBFrom, Val));
+ return false;
+ }
+
LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
if (!InBlock.isConstantRange()) {
Result = LVILatticeVal::getRange(TrueValues);
Result = getBlockValue(Val, BBFrom);
return true;
}
- block_value_stack.push(BlockStackEntry(Val, BBFrom));
+ BlockValueStack.push(std::make_pair(BBFrom, Val));
return false;
}
DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
<< BB->getName() << "'\n");
- block_value_stack.push(BlockStackEntry(V, BB));
+ BlockValueStack.push(std::make_pair(BB, V));
solve();
LVILatticeVal Result = getBlockValue(V, BB);
worklist.push_back(OldSucc);
DenseSet<Value*> ClearSet;
- for (std::set<std::pair<AssertingVH<BasicBlock>, Value*> >::iterator
- I = OverDefinedCache.begin(), E = OverDefinedCache.end(); I != E; ++I) {
+ for (DenseSet<OverDefinedPairTy>::iterator I = OverDefinedCache.begin(),
+ E = OverDefinedCache.end(); I != E; ++I) {
if (I->first == OldSucc)
ClearSet.insert(I->second);
}
for (DenseSet<Value*>::iterator I = ClearSet.begin(), E = ClearSet.end();
I != E; ++I) {
// If a value was marked overdefined in OldSucc, and is here too...
- std::set<std::pair<AssertingVH<BasicBlock>, Value*> >::iterator OI =
+ DenseSet<OverDefinedPairTy>::iterator OI =
OverDefinedCache.find(std::make_pair(ToUpdate, *I));
if (OI == OverDefinedCache.end()) continue;
projects / oota-llvm.git / blobdiff