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 @@ -150,15 +150,21 @@ } // end anonymous namespace namespace { + using NonNullPointerSet = SmallDenseSet, 2>; + /// This is the cache kept by LazyValueInfo which /// maintains information about queries across the clients' queries. 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 BlockCacheEntry { SmallDenseMap, ValueLatticeElement, 4> LatticeElements; SmallDenseSet, 4> OverDefined; + // None indicates that the nonnull pointers for this basic block + // block have not been computed yet. + Optional NonNullPointers; }; /// Cached information per basic block. @@ -220,6 +226,19 @@ return LatticeIt->second; } + bool isNonNullAtEndOfBlock( + Value *V, BasicBlock *BB, + function_ref InitFn) { + BlockCacheEntry *Entry = getOrCreateBlockEntry(BB); + if (!Entry->NonNullPointers) { + Entry->NonNullPointers = InitFn(BB); + for (Value *V : *Entry->NonNullPointers) + addValueHandle(V); + } + + return Entry->NonNullPointers->count(V); + } + /// clear - Empty the cache. void clear() { BlockCache.clear(); @@ -244,6 +263,8 @@ for (auto &Pair : BlockCache) { Pair.second->LatticeElements.erase(V); Pair.second->OverDefined.erase(V); + if (Pair.second->NonNullPointers) + Pair.second->NonNullPointers->erase(V); } auto HandleIt = ValueHandles.find_as(V); @@ -404,6 +425,7 @@ BasicBlock *BB); Optional solveBlockValueExtractValue( ExtractValueInst *EVI, BasicBlock *BB); + bool isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB); void intersectAssumeOrGuardBlockValueConstantRange(Value *Val, ValueLatticeElement &BBLV, Instruction *BBI); @@ -603,48 +625,43 @@ return getFromRangeMetadata(BBI); } -static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) { +static void AddNonNullPointer(Value *Ptr, NonNullPointerSet &PtrSet) { + // TODO: Use NullPointerIsDefined instead. + if (Ptr->getType()->getPointerAddressSpace() == 0) + PtrSet.insert(getUnderlyingObject(Ptr)); +} + +static void AddNonNullPointersByInstruction( + Instruction *I, NonNullPointerSet &PtrSet) { if (LoadInst *L = dyn_cast(I)) { - return L->getPointerAddressSpace() == 0 && - getUnderlyingObject(L->getPointerOperand()) == Ptr; - } - if (StoreInst *S = dyn_cast(I)) { - return S->getPointerAddressSpace() == 0 && - getUnderlyingObject(S->getPointerOperand()) == Ptr; - } - if (MemIntrinsic *MI = dyn_cast(I)) { - if (MI->isVolatile()) return false; + AddNonNullPointer(L->getPointerOperand(), PtrSet); + } else if (StoreInst *S = dyn_cast(I)) { + AddNonNullPointer(S->getPointerOperand(), PtrSet); + } 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()) == Ptr) - return true; + AddNonNullPointer(MI->getRawDest(), PtrSet); if (MemTransferInst *MTI = dyn_cast(MI)) - if (MTI->getSourceAddressSpace() == 0) - if (getUnderlyingObject(MTI->getRawSource()) == Ptr) - return true; + AddNonNullPointer(MTI->getRawSource(), PtrSet); } - 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::isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB) { + if (NullPointerIsDefined(BB->getParent(), + Val->getType()->getPointerAddressSpace())) + return false; - Value *UnderlyingVal = getUnderlyingObject(Val); - // If 'getUnderlyingObject' didn't converge, skip it. It won't converge - // inside InstructionDereferencesPointer either. - if (UnderlyingVal == getUnderlyingObject(UnderlyingVal, 1)) + Val = getUnderlyingObject(Val); + return TheCache.isNonNullAtEndOfBlock(Val, BB, [this](BasicBlock *BB) { + NonNullPointerSet NonNullPointers; for (Instruction &I : *BB) - if (InstructionDereferencesPointer(&I, UnderlyingVal)) - return true; - return false; + AddNonNullPointersByInstruction(&I, NonNullPointers); + return NonNullPointers; + }); } Optional LazyValueInfoImpl::solveBlockValueNonLocal( @@ -655,16 +672,7 @@ // 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())))) - return ValueLatticeElement::getNot(ConstantPointerNull::get(PTy)); - else - return ValueLatticeElement::getOverdefined(); + return ValueLatticeElement::getOverdefined(); } // Loop over all of our predecessors, merging what we know from them into @@ -689,14 +697,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)); - } - return Result; } } @@ -769,16 +769,23 @@ } // If guards are not used in the module, don't spend time looking for them - if (!GuardDecl || GuardDecl->use_empty()) - return; + if (GuardDecl && !GuardDecl->use_empty() && + BBI->getIterator() != BB->begin()) { + for (Instruction &I : make_range(std::next(BBI->getIterator().getReverse()), + BB->rend())) { + Value *Cond = nullptr; + if (match(&I, m_Intrinsic(m_Value(Cond)))) + BBLV = intersect(BBLV, getValueFromCondition(Val, Cond)); + } + } - if (BBI->getIterator() == BB->begin()) - return; - for (Instruction &I : make_range(std::next(BBI->getIterator().getReverse()), - BB->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 && BB->getTerminator() == BBI && + isNonNullAtEndOfBlock(Val, BB)) + BBLV = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy)); } } diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/non-null.ll b/llvm/test/Transforms/CorrelatedValuePropagation/non-null.ll --- a/llvm/test/Transforms/CorrelatedValuePropagation/non-null.ll +++ b/llvm/test/Transforms/CorrelatedValuePropagation/non-null.ll @@ -337,7 +337,7 @@ ; CHECK-LABEL: @test_store_same_block( ; CHECK-NEXT: store i8 0, i8* [[ARG:%.*]], align 1 ; CHECK-NEXT: [[CMP:%.*]] = icmp ne i8* [[ARG]], null -; CHECK-NEXT: ret i1 [[CMP]] +; CHECK-NEXT: ret i1 true ; store i8 0, i8* %arg %cmp = icmp ne i8* %arg, null