Index: llvm/lib/Analysis/LazyValueInfo.cpp =================================================================== --- llvm/lib/Analysis/LazyValueInfo.cpp +++ llvm/lib/Analysis/LazyValueInfo.cpp @@ -154,10 +154,12 @@ class LazyValueInfoCache { /// This is all of the cached information for one basic block. It contains /// the per-value lattice elements, as well as a separate set for - /// overdefined values to reduce memory usage. + /// overdefined values to reduce memory usage. Additionally pointers + /// dereferenced in the block are cached for nullability queries. struct BlockCacheEntryTy { SmallDenseMap, ValueLatticeElement, 4> LatticeElements; SmallDenseSet, 4> OverDefined; + Optional>> DereferencedPointers; }; /// Cached information per basic block. @@ -205,6 +207,27 @@ return LatticeIt->second; } + Optional isPointerDereferencedInBlock(Value *V, + BasicBlock *BB) const { + auto It = BlockCache.find(BB); + if (It == BlockCache.end() || !It->second.DereferencedPointers) + return None; + + return It->second.DereferencedPointers->count(V); + } + + void setPointersDereferencedInBlock(BasicBlock *BB, + DenseSet> Pointers) { + for (Value *V : Pointers) { + auto HandleIt = ValueHandles.find_as(V); + if (HandleIt == ValueHandles.end()) + ValueHandles.insert({ V, this }); + } + + auto &CacheEntry = BlockCache.try_emplace(BB).first->second; + CacheEntry.DereferencedPointers = std::move(Pointers); + } + /// clear - Empty the cache. void clear() { BlockCache.clear(); @@ -229,6 +252,8 @@ for (auto &Pair : BlockCache) { Pair.second.LatticeElements.erase(V); Pair.second.OverDefined.erase(V); + if (Pair.second.DereferencedPointers) + Pair.second.DereferencedPointers->erase(V); } auto HandleIt = ValueHandles.find_as(V); @@ -393,6 +418,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); @@ -574,17 +600,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, @@ -594,11 +609,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); @@ -619,75 +645,67 @@ 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, DenseSet> &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, DenseSet> &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)) - for (Instruction &I : *BB) - if (InstructionDereferencesPointer(&I, UnderlyingVal)) - return true; - return false; + Val = GetUnderlyingObject(Val, DL); + + Optional OptionalIsDereferenced = + TheCache.isPointerDereferencedInBlock(Val, BB); + if (OptionalIsDereferenced) + return *OptionalIsDereferenced; + + DenseSet> DereferencedPointers; + for (Instruction &I : *BB) + AddPointersDereferencedByInstruction(&I, DereferencedPointers, DL); + + bool IsDereferenced = DereferencedPointers.count(Val); + TheCache.setPointersDereferencedInBlock(BB, std::move(DereferencedPointers)); + return IsDereferenced; } 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; } @@ -713,14 +731,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; } @@ -793,16 +803,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)); } } Index: llvm/test/Transforms/JumpThreading/combine-metadata.ll =================================================================== --- llvm/test/Transforms/JumpThreading/combine-metadata.ll +++ 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 = !{}