Reapply [LVI] Normalize pointer behavior

nikic · nikic · commit 885a05f48a5d · 2019-11-08T20:13:55.000+01:00
Fix cache invalidation by not guarding the dereferenced pointer cache erasure by SeenBlocks. SeenBlocks is only populated when actually caching a value in the block, which doesn't necessarily have to happen just because dereferenced pointers were calculated. ----- 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. Differential Revision: https://reviews.llvm.org/D69914
diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp
@@ -151,6 +151,11 @@ namespace {
   /// This is the cache kept by LazyValueInfo which
   /// maintains information about queries across the clients' queries.
   class LazyValueInfoCache {
+  public:
+    typedef DenseMap<PoisoningVH<BasicBlock>, SmallPtrSet<Value *, 4>>
+        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,18 +167,19 @@ namespace {
       SmallDenseMap<PoisoningVH<BasicBlock>, 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<PoisoningVH<BasicBlock>, SmallPtrSet<Value *, 4>>
-        OverDefinedCacheTy;
     /// Keep track of all blocks that we have ever seen, so we
     /// don't spend time removing unused blocks from our caches.
     DenseSet<PoisoningVH<BasicBlock> > SeenBlocks;
 
     /// This is all of the cached information for all values,
     /// mapped from Value* to key information.
     DenseMap<Value *, std::unique_ptr<ValueCacheEntryTy>> 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 @@ namespace {
       return BBI->second;
     }
 
+    std::pair<PerBlockValueCacheTy::iterator, bool>
+    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 @@ namespace {
   };
 }
 
-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<Value *> &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);
 }
 
@@ -273,15 +290,17 @@ void LVIValueHandle::deleted() {
 }
 
 void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
+  // The SeenBlocks shortcut applies only to the value caches,
+  // always clear the dereferenced pointer cache.
+  DereferencedPointerCache.erase(BB);
+
   // Shortcut if we have never seen this block.
   DenseSet<PoisoningVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
   if (I == SeenBlocks.end())
     return;
   SeenBlocks.erase(I);
 
-  auto ODI = OverDefinedCache.find(BB);
-  if (ODI != OverDefinedCache.end())
-    OverDefinedCache.erase(ODI);
+  OverDefinedCache.erase(BB);
 
   for (auto &I : ValueCache)
     I.second->BlockVals.erase(BB);
@@ -438,6 +457,7 @@ namespace {
                                 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 +639,6 @@ bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
 
 bool LazyValueInfoImpl::solveBlockValueImpl(ValueLatticeElement &Res,
                                             Value *Val, BasicBlock *BB) {
-
-  Instruction *BBI = dyn_cast<Instruction>(Val);
-  if (!BBI || BBI->getParent() != BB)
-    return solveBlockValueNonLocal(Res, Val, BB);
-
-  if (PHINode *PN = dyn_cast<PHINode>(BBI))
-    return solveBlockValuePHINode(Res, PN, BB);
-
-  if (auto *SI = dyn_cast<SelectInst>(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 +648,22 @@ bool LazyValueInfoImpl::solveBlockValueImpl(ValueLatticeElement &Res,
   // 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)) {
     Res = ValueLatticeElement::getNot(ConstantPointerNull::get(PT));
     return true;
   }
+
+  Instruction *BBI = dyn_cast<Instruction>(Val);
+  if (!BBI || BBI->getParent() != BB)
+    return solveBlockValueNonLocal(Res, Val, BB);
+
+  if (PHINode *PN = dyn_cast<PHINode>(BBI))
+    return solveBlockValuePHINode(Res, PN, BB);
+
+  if (auto *SI = dyn_cast<SelectInst>(BBI))
+    return solveBlockValueSelect(Res, SI, BB);
+
   if (BBI->getType()->isIntegerTy()) {
     if (auto *CI = dyn_cast<CastInst>(BBI))
       return solveBlockValueCast(Res, CI, BB);
@@ -664,75 +684,63 @@ bool LazyValueInfoImpl::solveBlockValueImpl(ValueLatticeElement &Res,
   return true;
 }
 
-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;
+static void AddDereferencedPointer(
+    Value *Ptr, SmallPtrSet<Value *, 4> &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<StoreInst>(I)) {
-    return S->getPointerAddressSpace() == 0 &&
-           GetUnderlyingObject(S->getPointerOperand(),
-                               S->getModule()->getDataLayout()) == Ptr;
-  }
-  if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
-    if (MI->isVolatile()) return false;
+}
+
+static void AddPointersDereferencedByInstruction(
+    Instruction *I, SmallPtrSet<Value *, 4> &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);
+
+  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<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())))) {
-      Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy));
-    } else {
-      Result = ValueLatticeElement::getOverdefined();
-    }
-    BBLV = Result;
+    BBLV = ValueLatticeElement::getOverdefined();
     return true;
   }
 
@@ -758,14 +766,6 @@ bool LazyValueInfoImpl::solveBlockValueNonLocal(ValueLatticeElement &BBLV,
     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));
-      }
-
       BBLV = Result;
       return true;
     }
@@ -838,16 +838,24 @@ void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
   // 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<Intrinsic::experimental_guard>(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<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 && 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
@@ -108,7 +108,7 @@ d2:
 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 @@ ret2:
   ret void
 }
 
+@p = external global i32
 
 !0 = !{}
