X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FLazyValueInfo.cpp;h=88e18fa17918d21f17acd4556438dea3e052c950;hb=c0362d5c6e0066c741bce056a65d8b4c026de19f;hp=ecc1831dbe5b06ce14849361d8b2081d1ddd8e50;hpb=7f9cb744f284f23b362b010c1986d230c89d179c;p=oota-llvm.git diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp index ecc1831dbe5..88e18fa1791 100644 --- a/lib/Analysis/LazyValueInfo.cpp +++ b/lib/Analysis/LazyValueInfo.cpp @@ -19,18 +19,20 @@ #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Target/TargetData.h" #include "llvm/Support/CFG.h" +#include "llvm/Support/ConstantRange.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Support/ValueHandle.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" -#include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/STLExtras.h" +#include +#include using namespace llvm; char LazyValueInfo::ID = 0; INITIALIZE_PASS(LazyValueInfo, "lazy-value-info", - "Lazy Value Information Analysis", false, true); + "Lazy Value Information Analysis", false, true) namespace llvm { FunctionPass *createLazyValueInfoPass() { return new LazyValueInfo(); } @@ -52,12 +54,15 @@ class LVILatticeVal { enum LatticeValueTy { /// undefined - This LLVM Value has no known value yet. undefined, + /// constant - This LLVM Value has a specific constant value. constant, - /// notconstant - This LLVM value is known to not have the specified value. notconstant, + /// constantrange + constantrange, + /// overdefined - This instruction is not known to be constant, and we know /// it has a value. overdefined @@ -65,42 +70,62 @@ class LVILatticeVal { /// Val: This stores the current lattice value along with the Constant* for /// the constant if this is a 'constant' or 'notconstant' value. - PointerIntPair Val; + LatticeValueTy Tag; + Constant *Val; + ConstantRange Range; public: - LVILatticeVal() : Val(0, undefined) {} + LVILatticeVal() : Tag(undefined), Val(0), Range(1, true) {} static LVILatticeVal get(Constant *C) { LVILatticeVal Res; - Res.markConstant(C); + if (ConstantInt *CI = dyn_cast(C)) + Res.markConstantRange(ConstantRange(CI->getValue(), CI->getValue()+1)); + else if (!isa(C)) + Res.markConstant(C); return Res; } static LVILatticeVal getNot(Constant *C) { LVILatticeVal Res; - Res.markNotConstant(C); + if (ConstantInt *CI = dyn_cast(C)) + Res.markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue())); + else + Res.markNotConstant(C); + return Res; + } + static LVILatticeVal getRange(ConstantRange CR) { + LVILatticeVal Res; + Res.markConstantRange(CR); return Res; } - bool isUndefined() const { return Val.getInt() == undefined; } - bool isConstant() const { return Val.getInt() == constant; } - bool isNotConstant() const { return Val.getInt() == notconstant; } - bool isOverdefined() const { return Val.getInt() == overdefined; } + 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.getPointer(); + return Val; } Constant *getNotConstant() const { assert(isNotConstant() && "Cannot get the constant of a non-notconstant!"); - return Val.getPointer(); + return Val; + } + + ConstantRange getConstantRange() const { + assert(isConstantRange() && + "Cannot get the constant-range of a non-constant-range!"); + return Range; } /// markOverdefined - Return true if this is a change in status. bool markOverdefined() { if (isOverdefined()) return false; - Val.setInt(overdefined); + Tag = overdefined; return true; } @@ -112,9 +137,9 @@ public: } assert(isUndefined()); - Val.setInt(constant); + Tag = constant; assert(V && "Marking constant with NULL"); - Val.setPointer(V); + Val = V; return true; } @@ -130,9 +155,29 @@ public: else assert(isUndefined()); - Val.setInt(notconstant); + Tag = notconstant; assert(V && "Marking constant with NULL"); - Val.setPointer(V); + Val = V; + return true; + } + + /// markConstantRange - Return true if this is a change in status. + bool markConstantRange(const ConstantRange NewR) { + if (isConstantRange()) { + if (NewR.isEmptySet()) + return markOverdefined(); + + bool changed = Range == NewR; + Range = NewR; + return changed; + } + + assert(isUndefined()); + if (NewR.isEmptySet()) + return markOverdefined(); + + Tag = constantrange; + Range = NewR; return true; } @@ -149,20 +194,43 @@ public: isa(RHS.getNotConstant())) return markOverdefined(); return false; - } - if (isConstant()) { + } else if (isConstant()) { if (getConstant() == RHS.getNotConstant() || isa(RHS.getNotConstant()) || isa(getConstant())) return markOverdefined(); return markNotConstant(RHS.getNotConstant()); + } else if (isConstantRange()) { + // FIXME: This could be made more precise. + return markOverdefined(); } assert(isUndefined() && "Unexpected lattice"); return markNotConstant(RHS.getNotConstant()); } - // RHS must be a constant, we must be undef, constant, or notconstant. + if (RHS.isConstantRange()) { + if (isConstantRange()) { + ConstantRange NewR = Range.unionWith(RHS.getConstantRange()); + if (NewR.isFullSet()) + return markOverdefined(); + else + return markConstantRange(NewR); + } else if (!isUndefined()) { + return markOverdefined(); + } + + assert(isUndefined() && "Unexpected lattice"); + return markConstantRange(RHS.getConstantRange()); + } + + // RHS must be a constant, we must be constantrange, + // undef, constant, or notconstant. + if (isConstantRange()) { + // FIXME: This could be made more precise. + return markOverdefined(); + } + if (isUndefined()) return markConstant(RHS.getConstant()); @@ -193,6 +261,9 @@ raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) { if (Val.isNotConstant()) return OS << "notconstant<" << *Val.getNotConstant() << '>'; + else if (Val.isConstantRange()) + return OS << "constantrange<" << Val.getConstantRange().getLower() << ", " + << Val.getConstantRange().getUpper() << '>'; return OS << "constant<" << *Val.getConstant() << '>'; } } @@ -208,12 +279,12 @@ namespace { public: /// 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 BlockCacheEntryTy; + typedef std::pair, LVILatticeVal> BlockCacheEntryTy; /// 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 ValueCacheEntryTy; + typedef std::map, LVILatticeVal> ValueCacheEntryTy; private: /// LVIValueHandle - A callback value handle update the cache when @@ -228,10 +299,6 @@ namespace { void allUsesReplacedWith(Value* V) { deleted(); } - - LVIValueHandle &operator=(Value *V) { - return *this = LVIValueHandle(V, Parent); - } }; /// ValueCache - This is all of the cached information for all values, @@ -241,7 +308,7 @@ namespace { /// 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 > OverDefinedCache; + std::set, Value*> > OverDefinedCache; public: @@ -257,6 +324,16 @@ namespace { /// edge from PredBB to OldSucc has been threaded to be from PredBB to /// NewSucc. void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc); + + /// eraseBlock - This is part of the update interface to inform the cache + /// that a block has been deleted. + void eraseBlock(BasicBlock *BB); + + /// clear - Empty the cache. + void clear() { + ValueCache.clear(); + OverDefinedCache.clear(); + } }; } // end anonymous namespace @@ -284,16 +361,17 @@ namespace { ValueCacheEntryTy &Cache; /// This tracks, for each block, what values are overdefined. - std::set > &OverDefinedCache; + std::set, 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 NewBlockInfo; + public: LVIQuery(Value *V, LazyValueInfoCache &P, ValueCacheEntryTy &VC, - std::set > &ODC) + std::set, Value*> > &ODC) : Val(V), Parent(P), Cache(VC), OverDefinedCache(ODC) { } @@ -313,34 +391,50 @@ namespace { LVILatticeVal getEdgeValue(BasicBlock *FromBB, BasicBlock *ToBB); private: - LVILatticeVal &getCachedEntryForBlock(BasicBlock *BB); + LVILatticeVal getCachedEntryForBlock(BasicBlock *BB); }; } // end anonymous namespace void LazyValueInfoCache::LVIValueHandle::deleted() { - Parent->ValueCache.erase(*this); - for (std::set >::iterator + for (std::set, Value*> >::iterator I = Parent->OverDefinedCache.begin(), E = Parent->OverDefinedCache.end(); I != E; ) { - std::set >::iterator tmp = I; + std::set, Value*> >::iterator tmp = I; ++I; if (tmp->second == getValPtr()) Parent->OverDefinedCache.erase(tmp); } + + // 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, Value*> >::iterator + I = OverDefinedCache.begin(), E = OverDefinedCache.end(); I != E; ) { + std::set, Value*> >::iterator tmp = I; + ++I; + if (tmp->first == BB) + OverDefinedCache.erase(tmp); + } + + for (std::map::iterator + I = ValueCache.begin(), E = ValueCache.end(); I != E; ++I) + I->second.erase(BB); +} /// 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 LVIQuery::getCachedEntryForBlock(BasicBlock *BB) { NewBlockInfo.insert(BB); return Cache[BB]; } LVILatticeVal LVIQuery::getBlockValue(BasicBlock *BB) { // See if we already have a value for this block. - LVILatticeVal &BBLV = getCachedEntryForBlock(BB); + LVILatticeVal BBLV = getCachedEntryForBlock(BB); // If we've already computed this block's value, return it. if (!BBLV.isUndefined()) { @@ -352,13 +446,28 @@ LVILatticeVal LVIQuery::getBlockValue(BasicBlock *BB) { // lattice value to overdefined, so that cycles will terminate and be // conservatively correct. BBLV.markOverdefined(); + Cache[BB] = BBLV; - // If V is live into BB, see if our predecessors know anything about it. Instruction *BBI = dyn_cast(Val); if (BBI == 0 || BBI->getParent() != BB) { LVILatticeVal Result; // Start Undefined. - unsigned NumPreds = 0; + // 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){ + LoadInst *L = dyn_cast(BI); + if (L && L->getPointerAddressSpace() == 0 && + L->getPointerOperand()->getUnderlyingObject() == + Val->getUnderlyingObject()) { + NotNull = true; + break; + } + } + } + + unsigned NumPreds = 0; // 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) { @@ -369,11 +478,19 @@ LVILatticeVal LVIQuery::getBlockValue(BasicBlock *BB) { if (Result.isOverdefined()) { DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - overdefined because of pred.\n"); + // 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(Val->getType()); + Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy)); + } + return Result; } ++NumPreds; } + // If this is the entry block, we must be asking about an argument. The // value is overdefined. if (NumPreds == 0 && BB == &BB->getParent()->front()) { @@ -384,7 +501,7 @@ LVILatticeVal LVIQuery::getBlockValue(BasicBlock *BB) { // Return the merged value, which is more precise than 'overdefined'. assert(!Result.isOverdefined()); - return getCachedEntryForBlock(BB) = Result; + return Cache[BB] = Result; } // If this value is defined by an instruction in this block, we have to @@ -409,18 +526,104 @@ LVILatticeVal LVIQuery::getBlockValue(BasicBlock *BB) { // Return the merged value, which is more precise than 'overdefined'. assert(!Result.isOverdefined()); - return getCachedEntryForBlock(BB) = Result; + return Cache[BB] = Result; + } + + assert(Cache[BB].isOverdefined() && "Recursive query changed our cache?"); - } else { + // 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; + if ((!isa(BBI) && !isa(BBI)) || + !BBI->getType()->isIntegerTy()) { + DEBUG(dbgs() << " compute BB '" << BB->getName() + << "' - overdefined because inst def found.\n"); + Result.markOverdefined(); + return Result; + } + + // FIXME: We're currently limited to binops with a constant RHS. This should + // be improved. + BinaryOperator *BO = dyn_cast(BBI); + if (BO && !isa(BO->getOperand(1))) { + DEBUG(dbgs() << " compute BB '" << BB->getName() + << "' - overdefined because inst def found.\n"); + + Result.markOverdefined(); + return Result; + } + + // Figure out the range of the LHS. If that fails, bail. + LVILatticeVal LHSVal = Parent.getValueInBlock(BBI->getOperand(0), BB); + if (!LHSVal.isConstantRange()) { + Result.markOverdefined(); + return Result; + } + + ConstantInt *RHS = 0; + ConstantRange LHSRange = LHSVal.getConstantRange(); + ConstantRange RHSRange(1); + const IntegerType *ResultTy = cast(BBI->getType()); + if (isa(BBI)) { + RHS = dyn_cast(BBI->getOperand(1)); + if (!RHS) { + Result.markOverdefined(); + return Result; + } + RHSRange = ConstantRange(RHS->getValue(), RHS->getValue()+1); } + + // 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. + switch (BBI->getOpcode()) { + case Instruction::Add: + Result.markConstantRange(LHSRange.add(RHSRange)); + break; + case Instruction::Sub: + Result.markConstantRange(LHSRange.sub(RHSRange)); + break; + case Instruction::Mul: + Result.markConstantRange(LHSRange.multiply(RHSRange)); + break; + case Instruction::UDiv: + Result.markConstantRange(LHSRange.udiv(RHSRange)); + break; + case Instruction::Shl: + Result.markConstantRange(LHSRange.shl(RHSRange)); + break; + case Instruction::LShr: + Result.markConstantRange(LHSRange.lshr(RHSRange)); + break; + case Instruction::Trunc: + Result.markConstantRange(LHSRange.truncate(ResultTy->getBitWidth())); + break; + case Instruction::SExt: + Result.markConstantRange(LHSRange.signExtend(ResultTy->getBitWidth())); + break; + case Instruction::ZExt: + Result.markConstantRange(LHSRange.zeroExtend(ResultTy->getBitWidth())); + break; + case Instruction::BitCast: + Result.markConstantRange(LHSRange); + break; + case Instruction::And: + Result.markConstantRange(LHSRange.binaryAnd(RHSRange)); + break; + case Instruction::Or: + Result.markConstantRange(LHSRange.binaryOr(RHSRange)); + break; - DEBUG(dbgs() << " compute BB '" << BB->getName() - << "' - overdefined because inst def found.\n"); - - LVILatticeVal Result; - Result.markOverdefined(); - return getCachedEntryForBlock(BB) = Result; + // Unhandled instructions are overdefined. + default: + DEBUG(dbgs() << " compute BB '" << BB->getName() + << "' - overdefined because inst def found.\n"); + Result.markOverdefined(); + break; + } + + return Cache[BB] = Result; } @@ -441,28 +644,57 @@ LVILatticeVal LVIQuery::getEdgeValue(BasicBlock *BBFrom, BasicBlock *BBTo) { // it is. if (BI->getCondition() == Val) return LVILatticeVal::get(ConstantInt::get( - Type::getInt1Ty(Val->getContext()), isTrueDest)); + Type::getInt1Ty(Val->getContext()), isTrueDest)); // If the condition of the branch is an equality comparison, we may be // able to infer the value. - if (ICmpInst *ICI = dyn_cast(BI->getCondition())) - if (ICI->isEquality() && ICI->getOperand(0) == Val && - isa(ICI->getOperand(1))) { + ICmpInst *ICI = dyn_cast(BI->getCondition()); + if (ICI && ICI->getOperand(0) == Val && + isa(ICI->getOperand(1))) { + if (ICI->isEquality()) { // We know that V has the RHS constant if this is a true SETEQ or // false SETNE. if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ)) return LVILatticeVal::get(cast(ICI->getOperand(1))); return LVILatticeVal::getNot(cast(ICI->getOperand(1))); } + + if (ConstantInt *CI = dyn_cast(ICI->getOperand(1))) { + // Calculate the range of values that would satisfy the comparison. + ConstantRange CmpRange(CI->getValue(), CI->getValue()+1); + ConstantRange TrueValues = + ConstantRange::makeICmpRegion(ICI->getPredicate(), CmpRange); + + // If we're interested in the false dest, invert the condition. + if (!isTrueDest) TrueValues = TrueValues.inverse(); + + // Figure out the possible values of the query BEFORE this branch. + LVILatticeVal InBlock = getBlockValue(BBFrom); + if (!InBlock.isConstantRange()) + return LVILatticeVal::getRange(TrueValues); + + // Find all potential values that satisfy both the input and output + // conditions. + ConstantRange PossibleValues = + TrueValues.intersectWith(InBlock.getConstantRange()); + + return LVILatticeVal::getRange(PossibleValues); + } + } } } // If the edge was formed by a switch on the value, then we may know exactly // what it is. if (SwitchInst *SI = dyn_cast(BBFrom->getTerminator())) { - // If BBTo is the default destination of the switch, we don't know anything. - // Given a more powerful range analysis we could know stuff. - if (SI->getCondition() == Val && SI->getDefaultDest() != BBTo) { + if (SI->getCondition() == Val) { + // We don't know anything in the default case. + if (SI->getDefaultDest() == BBTo) { + LVILatticeVal Result; + Result.markOverdefined(); + return Result; + } + // We only know something if there is exactly one value that goes from // BBFrom to BBTo. unsigned NumEdges = 0; @@ -496,8 +728,8 @@ LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB) { << BB->getName() << "'\n"); LVILatticeVal Result = LVIQuery(V, *this, - ValueCache[LVIValueHandle(V, this)], - OverDefinedCache).getBlockValue(BB); + ValueCache[LVIValueHandle(V, this)], + OverDefinedCache).getBlockValue(BB); DEBUG(dbgs() << " Result = " << Result << "\n"); return Result; @@ -537,7 +769,7 @@ void LazyValueInfoCache::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, worklist.push_back(OldSucc); DenseSet ClearSet; - for (std::set >::iterator + for (std::set, Value*> >::iterator I = OverDefinedCache.begin(), E = OverDefinedCache.end(); I != E; ++I) { if (I->first == OldSucc) ClearSet.insert(I->second); @@ -558,7 +790,7 @@ void LazyValueInfoCache::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, for (DenseSet::iterator I = ClearSet.begin(),E = ClearSet.end(); I != E; ++I) { // If a value was marked overdefined in OldSucc, and is here too... - std::set >::iterator OI = + std::set, Value*> >::iterator OI = OverDefinedCache.find(std::make_pair(ToUpdate, *I)); if (OI == OverDefinedCache.end()) continue; @@ -585,12 +817,6 @@ void LazyValueInfoCache::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, // LazyValueInfo Impl //===----------------------------------------------------------------------===// -bool LazyValueInfo::runOnFunction(Function &F) { - TD = getAnalysisIfAvailable(); - // Fully lazy. - return false; -} - /// getCache - This lazily constructs the LazyValueInfoCache. static LazyValueInfoCache &getCache(void *&PImpl) { if (!PImpl) @@ -598,6 +824,15 @@ static LazyValueInfoCache &getCache(void *&PImpl) { return *static_cast(PImpl); } +bool LazyValueInfo::runOnFunction(Function &F) { + if (PImpl) + getCache(PImpl).clear(); + + TD = getAnalysisIfAvailable(); + // Fully lazy. + return false; +} + void LazyValueInfo::releaseMemory() { // If the cache was allocated, free it. if (PImpl) { @@ -611,6 +846,11 @@ Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB) { if (Result.isConstant()) return Result.getConstant(); + else if (Result.isConstantRange()) { + ConstantRange CR = Result.getConstantRange(); + if (const APInt *SingleVal = CR.getSingleElement()) + return ConstantInt::get(V->getContext(), *SingleVal); + } return 0; } @@ -622,6 +862,11 @@ Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB, if (Result.isConstant()) return Result.getConstant(); + else if (Result.isConstantRange()) { + ConstantRange CR = Result.getConstantRange(); + if (const APInt *SingleVal = CR.getSingleElement()) + return ConstantInt::get(V->getContext(), *SingleVal); + } return 0; } @@ -642,6 +887,36 @@ LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, return Unknown; } + if (Result.isConstantRange()) { + ConstantInt *CI = dyn_cast(C); + if (!CI) return Unknown; + + ConstantRange CR = Result.getConstantRange(); + if (Pred == ICmpInst::ICMP_EQ) { + if (!CR.contains(CI->getValue())) + return False; + + if (CR.isSingleElement() && CR.contains(CI->getValue())) + return True; + } else if (Pred == ICmpInst::ICMP_NE) { + if (!CR.contains(CI->getValue())) + return True; + + if (CR.isSingleElement() && CR.contains(CI->getValue())) + return False; + } + + // Handle more complex predicates. + ConstantRange RHS(CI->getValue(), CI->getValue()+1); + ConstantRange TrueValues = ConstantRange::makeICmpRegion(Pred, RHS); + if (CR.intersectWith(TrueValues).isEmptySet()) + return False; + else if (TrueValues.contains(CR)) + return True; + + return Unknown; + } + if (Result.isNotConstant()) { // If this is an equality comparison, we can try to fold it knowing that // "V != C1". @@ -666,5 +941,9 @@ LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock* NewSucc) { - getCache(PImpl).threadEdge(PredBB, OldSucc, NewSucc); + if (PImpl) getCache(PImpl).threadEdge(PredBB, OldSucc, NewSucc); +} + +void LazyValueInfo::eraseBlock(BasicBlock *BB) { + if (PImpl) getCache(PImpl).eraseBlock(BB); }