X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FLazyValueInfo.cpp;h=88e18fa17918d21f17acd4556438dea3e052c950;hb=c0362d5c6e0066c741bce056a65d8b4c026de19f;hp=e770ed4251294b85d70dbd91cc7e4046ecf9c5f7;hpb=2f3ffb80fa19cea89e507ad14966ce511012f308;p=oota-llvm.git diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp index e770ed42512..88e18fa1791 100644 --- a/lib/Analysis/LazyValueInfo.cpp +++ b/lib/Analysis/LazyValueInfo.cpp @@ -26,11 +26,13 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.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(); } @@ -77,12 +79,23 @@ public: 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; } @@ -154,8 +167,6 @@ public: if (NewR.isEmptySet()) return markOverdefined(); - assert(Range.contains(NewR) && - "Marking constant range with non-subset range!"); bool changed = Range == NewR; Range = NewR; return changed; @@ -164,10 +175,6 @@ public: assert(isUndefined()); if (NewR.isEmptySet()) return markOverdefined(); - else if (NewR.isFullSet()) { - Tag = undefined; - return true; - } Tag = constantrange; Range = NewR; @@ -187,13 +194,15 @@ 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"); @@ -202,20 +211,25 @@ public: if (RHS.isConstantRange()) { if (isConstantRange()) { - ConstantRange NewR = Range.intersectWith(RHS.getConstantRange()); - if (NewR.isEmptySet()) + 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 undef, constant, or notconstant. - assert(!isConstantRange() && - "Constant and ConstantRange cannot be merged."); + // 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()); @@ -265,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 @@ -285,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, @@ -298,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: @@ -314,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 @@ -341,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) { } @@ -370,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()) { @@ -409,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) { @@ -426,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()) { @@ -441,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 @@ -466,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; + + // Unhandled instructions are overdefined. + default: + DEBUG(dbgs() << " compute BB '" << BB->getName() + << "' - overdefined because inst def found.\n"); + Result.markOverdefined(); + break; } - DEBUG(dbgs() << " compute BB '" << BB->getName() - << "' - overdefined because inst def found.\n"); - - LVILatticeVal Result; - Result.markOverdefined(); - return getCachedEntryForBlock(BB) = Result; + return Cache[BB] = Result; } @@ -498,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; @@ -553,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; @@ -594,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); @@ -615,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; @@ -642,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) @@ -655,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) { @@ -668,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; } @@ -679,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; } @@ -699,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". @@ -723,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); }