diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp --- a/llvm/lib/Analysis/LazyValueInfo.cpp +++ b/llvm/lib/Analysis/LazyValueInfo.cpp @@ -151,6 +151,11 @@ /// This is the cache kept by LazyValueInfo which /// maintains information about queries across the clients' queries. class LazyValueInfoCache { + public: + typedef DenseMap, SmallPtrSet> + PerBlockValueCacheTy; + + private: /// 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. @@ -162,10 +167,6 @@ SmallDenseMap, ValueLatticeElement, 4> BlockVals; }; - /// This tracks, on a per-block basis, the set of values that are - /// over-defined at the end of that block. - typedef DenseMap, SmallPtrSet> - OverDefinedCacheTy; /// Keep track of all blocks that we have ever seen, so we /// don't spend time removing unused blocks from our caches. DenseSet > SeenBlocks; @@ -173,7 +174,12 @@ /// This is all of the cached information for all values, /// mapped from Value* to key information. DenseMap> ValueCache; - OverDefinedCacheTy OverDefinedCache; + /// This tracks, on a per-block basis, the set of values that are + /// over-defined at the end of that block. + PerBlockValueCacheTy OverDefinedCache; + /// This tracks, on a per-block basis, the set of pointers that are + /// dereferenced in the block (and thus non-null at the end of the block). + PerBlockValueCacheTy DereferencedPointerCache; public: @@ -229,11 +235,17 @@ return BBI->second; } + std::pair + getOrInitDereferencedPointers(BasicBlock *BB) { + return DereferencedPointerCache.try_emplace(BB); + } + /// clear - Empty the cache. void clear() { SeenBlocks.clear(); ValueCache.clear(); OverDefinedCache.clear(); + DereferencedPointerCache.clear(); } /// Inform the cache that a given value has been deleted. @@ -252,17 +264,22 @@ }; } -void LazyValueInfoCache::eraseValue(Value *V) { - for (auto I = OverDefinedCache.begin(), E = OverDefinedCache.end(); I != E;) { +static void eraseValueFromPerBlockValueCache( + Value *V, LazyValueInfoCache::PerBlockValueCacheTy &Cache) { + for (auto I = Cache.begin(), E = Cache.end(); I != E;) { // Copy and increment the iterator immediately so we can erase behind // ourselves. auto Iter = I++; SmallPtrSetImpl &ValueSet = Iter->second; ValueSet.erase(V); if (ValueSet.empty()) - OverDefinedCache.erase(Iter); + Cache.erase(Iter); } +} +void LazyValueInfoCache::eraseValue(Value *V) { + eraseValueFromPerBlockValueCache(V, OverDefinedCache); + eraseValueFromPerBlockValueCache(V, DereferencedPointerCache); ValueCache.erase(V); } @@ -279,9 +296,8 @@ return; SeenBlocks.erase(I); - auto ODI = OverDefinedCache.find(BB); - if (ODI != OverDefinedCache.end()) - OverDefinedCache.erase(ODI); + OverDefinedCache.erase(BB); + DereferencedPointerCache.erase(BB); for (auto &I : ValueCache) I.second->BlockVals.erase(BB); @@ -438,6 +454,7 @@ BasicBlock *BB); bool solveBlockValueExtractValue(ValueLatticeElement &BBLV, ExtractValueInst *EVI, BasicBlock *BB); + bool isNonNullDueToDereferenceInBlock(Value *Val, BasicBlock *BB); void intersectAssumeOrGuardBlockValueConstantRange(Value *Val, ValueLatticeElement &BBLV, Instruction *BBI); @@ -619,17 +636,6 @@ bool LazyValueInfoImpl::solveBlockValueImpl(ValueLatticeElement &Res, Value *Val, BasicBlock *BB) { - - Instruction *BBI = dyn_cast(Val); - if (!BBI || BBI->getParent() != BB) - return solveBlockValueNonLocal(Res, Val, BB); - - if (PHINode *PN = dyn_cast(BBI)) - return solveBlockValuePHINode(Res, PN, BB); - - if (auto *SI = dyn_cast(BBI)) - return solveBlockValueSelect(Res, SI, BB); - // If this value is a nonnull pointer, record it's range and bailout. Note // that for all other pointer typed values, we terminate the search at the // definition. We could easily extend this to look through geps, bitcasts, @@ -639,11 +645,22 @@ // This does mean that we have a sensitivity to where the defining // instruction is placed, even if it could legally be hoisted much higher. // That is unfortunate. - PointerType *PT = dyn_cast(BBI->getType()); - if (PT && isKnownNonZero(BBI, DL)) { + PointerType *PT = dyn_cast(Val->getType()); + if (PT && isKnownNonZero(Val, DL)) { Res = ValueLatticeElement::getNot(ConstantPointerNull::get(PT)); return true; } + + Instruction *BBI = dyn_cast(Val); + if (!BBI || BBI->getParent() != BB) + return solveBlockValueNonLocal(Res, Val, BB); + + if (PHINode *PN = dyn_cast(BBI)) + return solveBlockValuePHINode(Res, PN, BB); + + if (auto *SI = dyn_cast(BBI)) + return solveBlockValueSelect(Res, SI, BB); + if (BBI->getType()->isIntegerTy()) { if (auto *CI = dyn_cast(BBI)) return solveBlockValueCast(Res, CI, BB); @@ -664,75 +681,63 @@ return true; } -static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) { - if (LoadInst *L = dyn_cast(I)) { - return L->getPointerAddressSpace() == 0 && - GetUnderlyingObject(L->getPointerOperand(), - L->getModule()->getDataLayout()) == Ptr; +static void AddDereferencedPointer( + Value *Ptr, SmallPtrSet &PtrSet, const DataLayout &DL) { + // TODO: Use NullPointerIsDefined instead. + if (Ptr->getType()->getPointerAddressSpace() == 0) { + Ptr = GetUnderlyingObject(Ptr, DL); + PtrSet.insert(Ptr); } - if (StoreInst *S = dyn_cast(I)) { - return S->getPointerAddressSpace() == 0 && - GetUnderlyingObject(S->getPointerOperand(), - S->getModule()->getDataLayout()) == Ptr; - } - if (MemIntrinsic *MI = dyn_cast(I)) { - if (MI->isVolatile()) return false; +} + +static void AddPointersDereferencedByInstruction( + Instruction *I, SmallPtrSet &PtrSet, const DataLayout &DL) { + if (LoadInst *L = dyn_cast(I)) { + AddDereferencedPointer(L->getPointerOperand(), PtrSet, DL); + } else if (StoreInst *S = dyn_cast(I)) { + AddDereferencedPointer(S->getPointerOperand(), PtrSet, DL); + } else if (MemIntrinsic *MI = dyn_cast(I)) { + if (MI->isVolatile()) return; // FIXME: check whether it has a valuerange that excludes zero? ConstantInt *Len = dyn_cast(MI->getLength()); - if (!Len || Len->isZero()) return false; + if (!Len || Len->isZero()) return; - if (MI->getDestAddressSpace() == 0) - if (GetUnderlyingObject(MI->getRawDest(), - MI->getModule()->getDataLayout()) == Ptr) - return true; + AddDereferencedPointer(MI->getRawDest(), PtrSet, DL); if (MemTransferInst *MTI = dyn_cast(MI)) - if (MTI->getSourceAddressSpace() == 0) - if (GetUnderlyingObject(MTI->getRawSource(), - MTI->getModule()->getDataLayout()) == Ptr) - return true; + AddDereferencedPointer(MTI->getRawSource(), PtrSet, DL); } - return false; } -/// Return true if the allocation associated with Val is ever dereferenced -/// within the given basic block. This establishes the fact Val is not null, -/// but does not imply that the memory at Val is dereferenceable. (Val may -/// point off the end of the dereferenceable part of the object.) -static bool isObjectDereferencedInBlock(Value *Val, BasicBlock *BB) { - assert(Val->getType()->isPointerTy()); +bool LazyValueInfoImpl::isNonNullDueToDereferenceInBlock( + Value *Val, BasicBlock *BB) { + if (NullPointerIsDefined(BB->getParent(), + Val->getType()->getPointerAddressSpace())) + return false; const DataLayout &DL = BB->getModule()->getDataLayout(); - Value *UnderlyingVal = GetUnderlyingObject(Val, DL); - // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge - // inside InstructionDereferencesPointer either. - if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1)) + Val = GetUnderlyingObject(Val, DL); + + LazyValueInfoCache::PerBlockValueCacheTy::iterator It; + bool NeedsInit; + std::tie(It, NeedsInit) = TheCache.getOrInitDereferencedPointers(BB); + + if (NeedsInit) for (Instruction &I : *BB) - if (InstructionDereferencesPointer(&I, UnderlyingVal)) - return true; - return false; + AddPointersDereferencedByInstruction(&I, It->second, DL); + + return It->second.count(Val); } bool LazyValueInfoImpl::solveBlockValueNonLocal(ValueLatticeElement &BBLV, - Value *Val, BasicBlock *BB) { + Value *Val, BasicBlock *BB) { ValueLatticeElement Result; // Start Undefined. // If this is the entry block, we must be asking about an argument. The // value is overdefined. if (BB == &BB->getParent()->getEntryBlock()) { assert(isa(Val) && "Unknown live-in to the entry block"); - // Before giving up, see if we can prove the pointer non-null local to - // this particular block. - PointerType *PTy = dyn_cast(Val->getType()); - if (PTy && - (isKnownNonZero(Val, DL) || - (isObjectDereferencedInBlock(Val, BB) && - !NullPointerIsDefined(BB->getParent(), PTy->getAddressSpace())))) { - Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy)); - } else { - Result = ValueLatticeElement::getOverdefined(); - } - BBLV = Result; + BBLV = ValueLatticeElement::getOverdefined(); return true; } @@ -758,14 +763,6 @@ if (Result.isOverdefined()) { LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - overdefined because of pred (non local).\n"); - // Before giving up, see if we can prove the pointer non-null local to - // this particular block. - PointerType *PTy = dyn_cast(Val->getType()); - if (PTy && isObjectDereferencedInBlock(Val, BB) && - !NullPointerIsDefined(BB->getParent(), PTy->getAddressSpace())) { - Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy)); - } - BBLV = Result; return true; } @@ -838,16 +835,24 @@ // If guards are not used in the module, don't spend time looking for them auto *GuardDecl = BBI->getModule()->getFunction( Intrinsic::getName(Intrinsic::experimental_guard)); - if (!GuardDecl || GuardDecl->use_empty()) - return; + if (GuardDecl && !GuardDecl->use_empty()) { + if (BBI->getIterator() == BBI->getParent()->begin()) + return; + for (Instruction &I : make_range(std::next(BBI->getIterator().getReverse()), + BBI->getParent()->rend())) { + Value *Cond = nullptr; + if (match(&I, m_Intrinsic(m_Value(Cond)))) + BBLV = intersect(BBLV, getValueFromCondition(Val, Cond)); + } + } - if (BBI->getIterator() == BBI->getParent()->begin()) - return; - for (Instruction &I : make_range(std::next(BBI->getIterator().getReverse()), - BBI->getParent()->rend())) { - Value *Cond = nullptr; - if (match(&I, m_Intrinsic(m_Value(Cond)))) - BBLV = intersect(BBLV, getValueFromCondition(Val, Cond)); + if (BBLV.isOverdefined()) { + // Check whether we're checking at the terminator, and the pointer has + // been dereferenced in this block. + PointerType *PTy = dyn_cast(Val->getType()); + if (PTy && BBI->getParent()->getTerminator() == BBI && + isNonNullDueToDereferenceInBlock(Val, BBI->getParent())) + BBLV = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy)); } } diff --git a/llvm/test/Transforms/JumpThreading/combine-metadata.ll b/llvm/test/Transforms/JumpThreading/combine-metadata.ll --- a/llvm/test/Transforms/JumpThreading/combine-metadata.ll +++ b/llvm/test/Transforms/JumpThreading/combine-metadata.ll @@ -108,7 +108,7 @@ d3: %y = load i32*, i32** %ptr store i32 1, i32* %y - %c2 = icmp eq i32* %y, null + %c2 = icmp eq i32* %y, @p br i1 %c2, label %ret1, label %ret2 ret1: @@ -118,5 +118,6 @@ ret void } +@p = external global i32 !0 = !{}