[LVI] Normalize pointer behavior

[nikic]

Summary

Related to D69686. As noted there, LVI currently behaves differently for integer and pointer values: For integers, the block value is always valid inside the basic block, while for pointers it is only valid at the end of the basic block. I believe the integer behavior is the correct one, and CVP relies on it via its getConstantRange() uses.

The reason for the special pointer behavior is that LVI checks whether a pointer is dereferenced in a given basic block and marks it as non-null in that case. Of course, this information is valid only after the dereferencing instruction, or in conservative approximation, at the end of the block.

This patch changes the treatment of dereferencability: Instead of including it inside the block value, we instead treat it as something similar to an assume (it essentially is a non-nullness assume) and incorporate this information in intersectAssumeOrGuardBlockValueConstantRange() if the context instruction is the terminator of the basic block. This happens either when determining an edge-value internally in LVI, or when a terminator was explicitly passed to getValueAt(). The latter case makes this change not fully NFC, because we can now fold terminator icmps based on the dereferencability information in the same block. This is the reason why I changed one JumpThreading test (it would optimize the condition away without the change).

Of course, we do not want to recompute dereferencability on each intersectAssume call, so we need a new cache for this. The dereferencability analysis requires walking the entire basic block and computing underlying objects of all memory operands. This was previously done separately for each queried pointer value. In the new implementation (both because this makes the caching simpler, and because it is faster), I instead only walk the full BB once and cache all the dereferenced pointers. So the traversal is now performed only once per BB, instead of once per queried pointer value.

I think the overall model now makes more sense than before, and there will be no more pitfalls due to differing integer/pointer behavior.

[reames]

This is definitely heading in the right direction. Nicely done overall, see suggestions as inline comments.

llvm/lib/Analysis/LazyValueInfo.cpp

260–261

Minor: I think this can become a free function as opposed to a member function. It doesn't appear to be using member state.

630

Please add a todo about using address space property (i.e. null is defined) instead of the raw AS==0 check here.

790

Ok, I don't think this placement quite works. The challenge is that your changing the point of the block scan from the furthest reached block during the backwards walk (entry, or point of overdefine) to instead scan the query source block.

I'd suggest adjusting the two call sites you remove to use the new caching logic, and then only do the scan if a) context is terminator, or b) context is not in same block (i.e. full block case)

[nikic]

llvm/lib/Analysis/LazyValueInfo.cpp

790

The challenge is that your changing the point of the block scan from the furthest reached block during the backwards walk (entry, or point of overdefine) to instead scan the query source block.

I believe the behavior of the scan essentially stays the same: intersectAssume() is not only used to calculate the final result of the query, it is also invoked internally by LVI when computing edge values. So if you query a pointer in BB2 with incoming edge from BB1, then the first thing we do is calculate the edge value BB1 -> BB2, at which point we will intersectAssume() with the terminator of BB1.

I'd suggest adjusting the two call sites you remove to use the new caching logic, and then only do the scan if a) context is terminator, or b) context is not in same block (i.e. full block case)

We'd have to insert checks into getEdgeValue() (always) and getValueAt() / getValueInBlock() (if context is terminator), which are exactly the places where we already use intersectAssume().

[nikic]

Make eraseValueFromPerBlockValueCache a free function, add todo.

[reames]

LGTM. Very nice cleanup, thank you for doing this.

llvm/lib/Analysis/LazyValueInfo.cpp

790

You are correct. I'd misremembered the code and hadn't checked the callers before commenting. Objection withdrawn.

[nikic]

Reopening as this has been reverted in rG7a3ad48d6de0e79a92361252a815b894565b9a0f.

[lebedev.ri]

Just marking as "changes needed" to denote the revert until there's more info.
@echristo any progress on reproducer?

[nikic]

I'll rebase this over D70376 once that lands, which should hopefully fix the python compilation issue. To provide some context, we were not properly invalidating elements in the overdefined value cache if they are deleted, which might result in incorrect "overdefined" result if something later happens to be allocated at the same location. This just causes non-determinism, because "overdefined" is a conservative assumption. However, this patch introduces a second cache that uses the same structure as the overdefined cache, and here missing the invalidation may result in a miscompile instead.

I'm traveling right now, so will probably only get around to this next week.

[nikic]

Rebase over D70376, fixing cache invalidation.

[nikic]

Would be good if someone could take another quick look at it, as the caching part changed significantly. The fact that the LVI caching happens in a separate class from LVI (why?) makes things slightly awkward.

[nikic]

Ping for re-review.

[reames]

llvm/lib/Analysis/LazyValueInfo.cpp

163

Can you add a note to the comment about the None state being used to represent a block whose dereferenceability hasn't yet been memoized?

672

This function signature and usage seems needlessly complicated here. Can I suggest something along the lines of the following:
if (None == TheCache[BB].DereferenceablePointers) {

// populate cache

}

return TheCache[BB].DereferenceablePointers->count(V);

You could hide the population inside an ensureDereferenceabilityCached or getDereferenceablePointers interface if you wanted.

[nikic]

llvm/lib/Analysis/LazyValueInfo.cpp

672

The somewhat awkward API here is used to keep all the members of LazyValueInfoCache private -- I'd have to make parts of it public to allow directly populating the cache directly here.

[nikic]

llvm/lib/Analysis/LazyValueInfo.cpp

672

Or is the suggestion here to just move the population of the cache itself into LazyValueInfoCache as well? That would certainly be easiest.

[nikic]

Improve cache interface: Use a single isPointerDereferenceInBlock() method which accepts a callback to initialize the cache. I think that gives a reasonable balance between hiding cache details and having natural control flow. What do you think?

[reames]

LGTM again.

[nikic]

Reopening this, as it was reverted (quite a while ago) as part of rG02a6b0bc3b54571f890a531e8c16b4c1173c55d0.

[nikic]

Rebase.

Unfortunately I found that the compile-time impact of this change is a bit hit and miss: https://llvm-compile-time-tracker.com/compare.php?from=f87b785abee0da8939fdd5900a982311b4c25409&to=f3490beadb768e921e531fd61450a7c5bfa84f2d&stat=instructions Some benchmarks improve, some regress. The reason is that the new implementation performs only a single scan to find dereferenced pointers, but performs a GetUnderlyingObject() call on every query, which is quite expensive. It's probably necessary to cache underlying objects as well.

Furthermore this change seems to have a larger impact on optimization than I expected, with larger code-size changes for some benchmarks: https://llvm-compile-time-tracker.com/compare.php?from=f87b785abee0da8939fdd5900a982311b4c25409&to=f3490beadb768e921e531fd61450a7c5bfa84f2d&stat=size-text Apparently being able to eliminate a null branch at the end of the block where the pointer is dereferenced is quite valuable.

[fhahn]

In D69914#2105255, @nikic wrote:

Furthermore this change seems to have a larger impact on optimization than I expected, with larger code-size changes for some benchmarks: https://llvm-compile-time-tracker.com/compare.php?from=f87b785abee0da8939fdd5900a982311b4c25409&to=f3490beadb768e921e531fd61450a7c5bfa84f2d&stat=size-text Apparently being able to eliminate a null branch at the end of the block where the pointer is dereferenced is quite valuable.

Interesting! I am wondering if it might be worth to handle simplifications based on dereferenceability in a separate pass, rather than making the caching more complicated. I am not sure how much benefit we get from other places in LVI knowing that a ptr is not null, but I would expect it not too be too much.

I've put up a simple prototype that just keeps track of dereferenced objects based on dominance D82299 and eliminates null checks in a single traversal of a sorted list of dereferences/compares.

[nikic]

Simplify the patch a bit, in particular remove the movement of isKnownNonZero that really has nothing to do with this patch. Also rename everything to use nonnull rather than dereferencable terminology, to make this more amenable to future extension.

[nikic]

Thanks to D82261 GetUnderlyingObject() is now cheap enough than caching is not worth the bother. Most of the remaining cost there will be addressed by D81867. New compile-time numbers: http://llvm-compile-time-tracker.com/compare.php?from=37d3030711cc30564fb142154e4e8cabdc91724e&to=e518ba98b7fb90f2645b91edd8cdeae40ad6f4df&stat=instructions I profiled the sqlite case and found that while LVI cost does increase a bit, the main contribution are second-order effects. As such I'm happy enough with performance to reapply this.

In D69914#2106549, @fhahn wrote:

In D69914#2105255, @nikic wrote:

Furthermore this change seems to have a larger impact on optimization than I expected, with larger code-size changes for some benchmarks: https://llvm-compile-time-tracker.com/compare.php?from=f87b785abee0da8939fdd5900a982311b4c25409&to=f3490beadb768e921e531fd61450a7c5bfa84f2d&stat=size-text Apparently being able to eliminate a null branch at the end of the block where the pointer is dereferenced is quite valuable.

Interesting! I am wondering if it might be worth to handle simplifications based on dereferenceability in a separate pass, rather than making the caching more complicated. I am not sure how much benefit we get from other places in LVI knowing that a ptr is not null, but I would expect it not too be too much.

I've put up a simple prototype that just keeps track of dereferenced objects based on dominance D82299 and eliminates null checks in a single traversal of a sorted list of dereferences/compares.

Thanks for looking into this! Some thoughts on the tradeoff between a separate pass and having this in LVI:

• LVI gets nonnull information from three sources: isKnownNonZero for basic cases, pointer dereferences, and pointer comparisons. One important aspect here is that this information is combined, and not limited to dominating cases only. For example, if you have two incoming edges and the pointer is dereferenced in both predecessor blocks, LVI knows that is is non-null (even though neither dereference is dominating). Similarly, if the pointer is dereferenced in one predecessor, but the other one is guarded by a !== null check, we still get the same result.
• CVP uses LVI nonnull information both for compares and for call nonnull attributes. Handling those two in a separate pass is easy.
• JumpThreading is unfortunately outside my area of familiarity, but I believe this is the part where having nonnull-reasoning inside LVI rather than separately is important. Jump threading does a lot of reasoning about predicates on edges and queries LVI to do so. Dropping this functionality from LVI would probably make threading of !== null less effective.

[nikic]

Any further input here? I'd like to reapply this, to unblock D69686.

[fhahn]

In D69914#2107451, @nikic wrote:

Thanks to D82261 GetUnderlyingObject() is now cheap enough than caching is not worth the bother. Most of the remaining cost there will be addressed by D81867. New compile-time numbers: http://llvm-compile-time-tracker.com/compare.php?from=37d3030711cc30564fb142154e4e8cabdc91724e&to=e518ba98b7fb90f2645b91edd8cdeae40ad6f4df&stat=instructions I profiled the sqlite case and found that while LVI cost does increase a bit, the main contribution are second-order effects. As such I'm happy enough with performance to reapply this.

In D69914#2106549, @fhahn wrote:

In D69914#2105255, @nikic wrote:

Furthermore this change seems to have a larger impact on optimization than I expected, with larger code-size changes for some benchmarks: https://llvm-compile-time-tracker.com/compare.php?from=f87b785abee0da8939fdd5900a982311b4c25409&to=f3490beadb768e921e531fd61450a7c5bfa84f2d&stat=size-text Apparently being able to eliminate a null branch at the end of the block where the pointer is dereferenced is quite valuable.

Interesting! I am wondering if it might be worth to handle simplifications based on dereferenceability in a separate pass, rather than making the caching more complicated. I am not sure how much benefit we get from other places in LVI knowing that a ptr is not null, but I would expect it not too be too much.

I've put up a simple prototype that just keeps track of dereferenced objects based on dominance D82299 and eliminates null checks in a single traversal of a sorted list of dereferences/compares.

Thanks for looking into this! Some thoughts on the tradeoff between a separate pass and having this in LVI:

• LVI gets nonnull information from three sources: isKnownNonZero for basic cases, pointer dereferences, and pointer comparisons. One important aspect here is that this information is combined, and not limited to dominating cases only. For example, if you have two incoming edges and the pointer is dereferenced in both predecessor blocks, LVI knows that is is non-null (even though neither dereference is dominating). Similarly, if the pointer is dereferenced in one predecessor, but the other one is guarded by a !== null check, we still get the same result.
• CVP uses LVI nonnull information both for compares and for call nonnull attributes. Handling those two in a separate pass is easy.
• JumpThreading is unfortunately outside my area of familiarity, but I believe this is the part where having nonnull-reasoning inside LVI rather than separately is important. Jump threading does a lot of reasoning about predicates on edges and queries LVI to do so. Dropping this functionality from LVI would probably make threading of !== null less effective.

The last point can indeed not really be solved by a separate patch unfortunately. I also won't have much time to look into the separate patch in the near future, so I don't think we should wait with this patch until then.

llvm/lib/Analysis/LazyValueInfo.cpp

 } // end anonymous namespace
 
 namespace {
   /// 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<AssertingVH<Value>, ValueLatticeElement, 4> LatticeElements;
       SmallDenseSet<AssertingVH<Value>, 4> OverDefined;
+      // None indicates that the dereferenced pointers for this basic block
+      // block have not been computed yet.
+      Optional<DenseSet<AssertingVH<Value>>> DereferencedPointers;
     };
 
     /// Cached information per basic block.
     DenseMap<PoisoningVH<BasicBlock>, std::unique_ptr<BlockCacheEntry>>
         BlockCache;
     /// Set of value handles used to erase values from the cache on deletion.
     DenseSet<LVIValueHandle, DenseMapInfo<Value *>> ValueHandles;
 
Optional<ValueLatticeElement> getCachedValueInfo(Value *V,
 
       auto LatticeIt = Entry->LatticeElements.find_as(V);
       if (LatticeIt == Entry->LatticeElements.end())
         return None;
 
       return LatticeIt->second;
     }
 
+    bool isPointerDereferencedInBlock(
+        Value *V, BasicBlock *BB,
+        std::function<DenseSet<AssertingVH<Value>>(BasicBlock *)> InitFn) {
+      BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);
+      if (!Entry->DereferencedPointers) {
+        Entry->DereferencedPointers = InitFn(BB);
+        for (Value *V : *Entry->DereferencedPointers)
+          addValueHandle(V);
+      }
+
+      return Entry->DereferencedPointers->count(V);
+    }
+
     /// clear - Empty the cache.
     void clear() {
       BlockCache.clear();
       ValueHandles.clear();
     }
 
     /// Inform the cache that a given value has been deleted.
     void eraseValue(Value *V);
 
     /// This is part of the update interface to inform the cache
     /// that a block has been deleted.
     void eraseBlock(BasicBlock *BB);
 
     /// Updates the cache to remove any influence an overdefined value in
     /// OldSucc might have (unless also overdefined in NewSucc).  This just
     /// flushes elements from the cache and does not add any.
     void threadEdgeImpl(BasicBlock *OldSucc,BasicBlock *NewSucc);
   };
 }
 
 void LazyValueInfoCache::eraseValue(Value *V) {
   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);
   if (HandleIt != ValueHandles.end())
     ValueHandles.erase(HandleIt);
 }
 
 void LVIValueHandle::deleted() {
class LazyValueInfoImpl {
   Optional<ValueLatticeElement> solveBlockValueOverflowIntrinsic(
       WithOverflowInst *WO, BasicBlock *BB);
   Optional<ValueLatticeElement> solveBlockValueSaturatingIntrinsic(
       SaturatingInst *SI, BasicBlock *BB);
   Optional<ValueLatticeElement> solveBlockValueIntrinsic(IntrinsicInst *II,
                                                          BasicBlock *BB);
   Optional<ValueLatticeElement> solveBlockValueExtractValue(
       ExtractValueInst *EVI, BasicBlock *BB);
+  bool isNonNullDueToDereferenceInBlock(Value *Val, BasicBlock *BB);
   void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
                                                      ValueLatticeElement &BBLV,
                                                      Instruction *BBI);
 
   void solve();
 
 public:
   /// This is the query interface to determine the lattice
if (!Res)
     return false;
 
   TheCache.insertResult(Val, BB, *Res);
   return true;
 }
 
 Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueImpl(
     Value *Val, BasicBlock *BB) {
-  Instruction *BBI = dyn_cast<Instruction>(Val);
-  if (!BBI || BBI->getParent() != BB)
-    return solveBlockValueNonLocal(Val, BB);
-
-  if (PHINode *PN = dyn_cast<PHINode>(BBI))
-    return solveBlockValuePHINode(PN, BB);
-
-  if (auto *SI = dyn_cast<SelectInst>(BBI))
-    return solveBlockValueSelect(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,
   // and the like to prove non-nullness, but it's not clear that's worth it
   // compile time wise.  The context-insensitive value walk done inside
   // isKnownNonZero gets most of the profitable cases at much less expense.
   // 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<PointerType>(BBI->getType());
-  if (PT && isKnownNonZero(BBI, DL))
+  PointerType *PT = dyn_cast<PointerType>(Val->getType());
+  if (PT && isKnownNonZero(Val, DL))
     return ValueLatticeElement::getNot(ConstantPointerNull::get(PT));
 
+  Instruction *BBI = dyn_cast<Instruction>(Val);
+  if (!BBI || BBI->getParent() != BB)
+    return solveBlockValueNonLocal(Val, BB);
+
+  if (PHINode *PN = dyn_cast<PHINode>(BBI))
+    return solveBlockValuePHINode(PN, BB);
+
+  if (auto *SI = dyn_cast<SelectInst>(BBI))
+    return solveBlockValueSelect(SI, BB);
+
   if (BBI->getType()->isIntegerTy()) {
     if (auto *CI = dyn_cast<CastInst>(BBI))
       return solveBlockValueCast(CI, BB);
 
     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI))
       return solveBlockValueBinaryOp(BO, BB);
 
     if (auto *EVI = dyn_cast<ExtractValueInst>(BBI))
       return solveBlockValueExtractValue(EVI, BB);
 
     if (auto *II = dyn_cast<IntrinsicInst>(BBI))
       return solveBlockValueIntrinsic(II, BB);
   }
 
   LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
                     << "' - unknown inst def found.\n");
   return getFromRangeMetadata(BBI);
 }
 
-static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
-  if (LoadInst *L = dyn_cast<LoadInst>(I)) {
-    return L->getPointerAddressSpace() == 0 &&
-           GetUnderlyingObject(L->getPointerOperand(),
-                               L->getModule()->getDataLayout()) == Ptr;
-  }
-  if (StoreInst *S = dyn_cast<StoreInst>(I)) {
-    return S->getPointerAddressSpace() == 0 &&
-           GetUnderlyingObject(S->getPointerOperand(),
-                               S->getModule()->getDataLayout()) == Ptr;
+static void AddDereferencedPointer(
+    Value *Ptr, DenseSet<AssertingVH<Value>> &PtrSet, const DataLayout &DL) {
+  // TODO: Use NullPointerIsDefined instead.
+  if (Ptr->getType()->getPointerAddressSpace() == 0) {
+    Ptr = GetUnderlyingObject(Ptr, DL);
+    PtrSet.insert(Ptr);
   }
-  if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
-    if (MI->isVolatile()) return false;
+}
+
+static void AddPointersDereferencedByInstruction(
+    Instruction *I, DenseSet<AssertingVH<Value>> &PtrSet,
+    const DataLayout &DL) {
+  if (LoadInst *L = dyn_cast<LoadInst>(I)) {
+    AddDereferencedPointer(L->getPointerOperand(), PtrSet, DL);
+  } else if (StoreInst *S = dyn_cast<StoreInst>(I)) {
+    AddDereferencedPointer(S->getPointerOperand(), PtrSet, DL);
+  } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
+    if (MI->isVolatile()) return;
 
     // FIXME: check whether it has a valuerange that excludes zero?
     ConstantInt *Len = dyn_cast<ConstantInt>(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<MemTransferInst>(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);
+
+  return TheCache.isPointerDereferencedInBlock(Val, BB, [DL](BasicBlock *BB) {
+    DenseSet<AssertingVH<Value>> DereferencedPointers;
     for (Instruction &I : *BB)
-      if (InstructionDereferencesPointer(&I, UnderlyingVal))
-        return true;
-  return false;
+      AddPointersDereferencedByInstruction(&I, DereferencedPointers, DL);
+    return DereferencedPointers;
+  });
 }
 
 Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueNonLocal(
     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<Argument>(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<PointerType>(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();
   }
 
   // Loop over all of our predecessors, merging what we know from them into
   // result.  If we encounter an unexplored predecessor, we eagerly explore it
   // in a depth first manner.  In practice, this has the effect of discovering
   // paths we can't analyze eagerly without spending compile times analyzing
   // other paths.  This heuristic benefits from the fact that predecessors are
   // frequently arranged such that dominating ones come first and we quickly
   // find a path to function entry.  TODO: We should consider explicitly
   // canonicalizing to make this true rather than relying on this happy
   // accident.
   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
     Optional<ValueLatticeElement> EdgeResult = getEdgeValue(Val, *PI, BB);
     if (!EdgeResult)
       // Explore that input, then return here
       return None;
 
     Result.mergeIn(*EdgeResult);
 
     // If we hit overdefined, exit early.  The BlockVals entry is already set
     // to overdefined.
     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<PointerType>(Val->getType());
-      if (PTy && isObjectDereferencedInBlock(Val, BB) &&
-          !NullPointerIsDefined(BB->getParent(), PTy->getAddressSpace())) {
-        Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy));
-      }
-
       return Result;
     }
   }
 
   // Return the merged value, which is more precise than 'overdefined'.
   assert(!Result.isOverdefined());
   return Result;
 }
for (auto &AssumeVH : AC->assumptionsFor(Val)) {
     auto *I = cast<CallInst>(AssumeVH);
     if (I->getParent() != BB || !isValidAssumeForContext(I, BBI))
       continue;
 
     BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
   }
 
   // If guards are not used in the module, don't spend time looking for them
-  if (!GuardDecl || GuardDecl->use_empty())
-    return;
-
-  if (BBI->getIterator() == BB->begin())
-    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<Intrinsic::experimental_guard>(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<PointerType>(Val->getType());
+    if (PTy && BB->getTerminator() == BBI &&
+        isNonNullDueToDereferenceInBlock(Val, BB))
+      BBLV = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy));
+  }
+}
+
 Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueSelect(
     SelectInst *SI, BasicBlock *BB) {
   // Recurse on our inputs if needed
   Optional<ValueLatticeElement> OptTrueVal =
       getBlockValue(SI->getTrueValue(), BB);
   if (!OptTrueVal)
     return None;
   ValueLatticeElement &TrueVal = *OptTrueVal;

llvm/test/Transforms/CorrelatedValuePropagation/non-null.ll

merge:
   call void @test12_helper(i8* %merged_arg)
   ret void
 }
 
 define i1 @test_store_same_block(i8* %arg) {
 ; 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
   ret i1 %cmp
 }
 
 attributes #0 = { null_pointer_is_valid }