#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";
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:
+ /// ValueCache - This is all of the cached information for all values,
+ /// mapped from Value* to key information.
+ 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.
+ 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
return changed;
}
};
-
- /// ValueCache - This is all of the cached information for all values,
- /// mapped from Value* to key information.
- 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;
+
LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
ValueCacheEntryTy &lookup(Value *V) {
return ValueCache[LVIValueHandle(V, this)];
}
-
- std::stack<std::pair<BasicBlock*, Value*> > block_value_stack;
public:
/// getValueInBlock - This is the query interface to determine the lattice
} // end anonymous namespace
void LVIValueHandle::deleted() {
- for (std::set<std::pair<AssertingVH<BasicBlock>, Value*> >::iterator
+ 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 (DenseMap<LVIValueHandle, ValueCacheEntryTy>::iterator
I = ValueCache.begin(), E = ValueCache.end(); I != E; ++I)
}
void LazyValueInfoCache::solve() {
- while (!block_value_stack.empty()) {
- std::pair<BasicBlock*, Value*> &e = block_value_stack.top();
+ while (!BlockValueStack.empty()) {
+ std::pair<BasicBlock*, Value*> &e = BlockValueStack.top();
if (solveBlockValue(e.second, e.first))
- block_value_stack.pop();
+ 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) {
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
// (integral binops and casts at the moment), so bail if this isn't one.
LVILatticeVal Result;
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;
}
// 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();
// 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));
}
BasicBlock *BB) {
// Figure out the range of the LHS. If that fails, bail.
if (!hasBlockValue(BBI->getOperand(0), BB)) {
- block_value_stack.push(std::make_pair(BB, BBI->getOperand(0)));
+ BlockValueStack.push(std::make_pair(BB, BBI->getOperand(0)));
return false;
}
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());
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(std::make_pair(BBFrom, Val));
+ 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(std::make_pair(BB, V));
+ 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