[PhiValues] Use callback value handles to invalidate deleted values

The way that PhiValues is integrated with BasicAA it is possible for a pass
which uses BasicAA to pick up an instance of BasicAA that uses PhiValues without
intending to, and then delete values from a function in a way that causes
PhiValues to return dangling pointers to these deleted values. Fix this by
having a set of callback value handles to invalidate values when they're
deleted.

llvm-svn: 340613

3 files changed, 67 insertions, 4 deletions

diff --git a/llvm/include/llvm/Analysis/PhiValues.h b/llvm/include/llvm/Analysis/PhiValues.h
index 6607b329c04..76204ac1bc6 100644
--- a/llvm/include/llvm/Analysis/PhiValues.h
+++ b/llvm/include/llvm/Analysis/PhiValues.h
@@ -88,6 +88,22 @@ private:
   /// All values reachable from each component.
   DenseMap<unsigned int, ConstValueSet> ReachableMap;
 
+  /// A CallbackVH to notify PhiValues when a value is deleted or replaced, so
+  /// that the cached information for that value can be cleared to avoid
+  /// dangling pointers to invalid values.
+  class PhiValuesCallbackVH final : public CallbackVH {
+    PhiValues *PV;
+    void deleted() override;
+    void allUsesReplacedWith(Value *New) override;
+
+  public:
+    PhiValuesCallbackVH(Value *V, PhiValues *PV = nullptr)
+        : CallbackVH(V), PV(PV) {}
+  };
+
+  /// A set of callbacks to the values that processPhi has seen.
+  DenseSet<PhiValuesCallbackVH, DenseMapInfo<Value *>> TrackedValues;
+
   /// The function that the PhiValues is for.
   const Function &F;
 
diff --git a/llvm/lib/Analysis/PhiValues.cpp b/llvm/lib/Analysis/PhiValues.cpp
index ef121815d2c..729227c8669 100644
--- a/llvm/lib/Analysis/PhiValues.cpp
+++ b/llvm/lib/Analysis/PhiValues.cpp
@@ -14,6 +14,16 @@
 
 using namespace llvm;
 
+void PhiValues::PhiValuesCallbackVH::deleted() {
+  PV->invalidateValue(getValPtr());
+}
+
+void PhiValues::PhiValuesCallbackVH::allUsesReplacedWith(Value *) {
+  // We could potentially update the cached values we have with the new value,
+  // but it's simpler to just treat the old value as invalidated.
+  PV->invalidateValue(getValPtr());
+}
+
 bool PhiValues::invalidate(Function &, const PreservedAnalyses &PA,
                            FunctionAnalysisManager::Invalidator &) {
   // PhiValues is invalidated if it isn't preserved.
@@ -46,6 +56,7 @@ void PhiValues::processPhi(const PHINode *Phi,
   DepthMap[Phi] = DepthNumber;
 
   // Recursively process the incoming phis of this phi.
+  TrackedValues.insert(PhiValuesCallbackVH(const_cast<PHINode *>(Phi), this));
   for (Value *PhiOp : Phi->incoming_values()) {
     if (PHINode *PhiPhiOp = dyn_cast<PHINode>(PhiOp)) {
       // Recurse if the phi has not yet been visited.
@@ -56,6 +67,8 @@ void PhiValues::processPhi(const PHINode *Phi,
       // phi are part of the same component, so adjust the depth number.
       if (!ReachableMap.count(DepthMap[PhiPhiOp]))
         DepthMap[Phi] = std::min(DepthMap[Phi], DepthMap[PhiPhiOp]);
+    } else {
+      TrackedValues.insert(PhiValuesCallbackVH(PhiOp, this));
     }
   }
 
@@ -122,6 +135,10 @@ void PhiValues::invalidateValue(const Value *V) {
     NonPhiReachableMap.erase(N);
     ReachableMap.erase(N);
   }
+  // This value is no longer tracked
+  auto It = TrackedValues.find_as(V);
+  if (It != TrackedValues.end())
+    TrackedValues.erase(It);
 }
 
 void PhiValues::releaseMemory() {
diff --git a/llvm/test/Analysis/BasicAA/phi-values-usage.ll b/llvm/test/Analysis/BasicAA/phi-values-usage.ll
index c5120a31f43..22743881e93 100644
--- a/llvm/test/Analysis/BasicAA/phi-values-usage.ll
+++ b/llvm/test/Analysis/BasicAA/phi-values-usage.ll
@@ -1,4 +1,5 @@
-; RUN: opt -debug-pass=Executions -phi-values -memcpyopt -instcombine -disable-output < %s 2>&1 | FileCheck %s
+; RUN: opt -debug-pass=Executions -phi-values -memcpyopt -instcombine -disable-output < %s 2>&1 | FileCheck %s -check-prefix=CHECK -check-prefix=CHECK-MEMCPY
+; RUN: opt -debug-pass=Executions -memdep -instcombine -disable-output < %s 2>&1 | FileCheck %s -check-prefix=CHECK
 
 ; Check that phi values is not run when it's not already available, and that
 ; basicaa is freed after a pass that preserves CFG.
@@ -6,17 +7,21 @@
 ; CHECK: Executing Pass 'Phi Values Analysis'
 ; CHECK: Executing Pass 'Basic Alias Analysis (stateless AA impl)'
 ; CHECK: Executing Pass 'Memory Dependence Analysis'
-; CHECK: Executing Pass 'MemCpy Optimization'
-; CHECK-DAG: Freeing Pass 'MemCpy Optimization'
+; CHECK-MEMCPY: Executing Pass 'MemCpy Optimization'
+; CHECK-MEMCPY-DAG: Freeing Pass 'MemCpy Optimization'
 ; CHECK-DAG: Freeing Pass 'Phi Values Analysis'
 ; CHECK-DAG: Freeing Pass 'Memory Dependence Analysis'
 ; CHECK-DAG: Freeing Pass 'Basic Alias Analysis (stateless AA impl)'
 ; CHECK-NOT: Executing Pass 'Phi Values Analysis'
-; CHECK: Executing Pass 'Basic Alias Analysis (stateless AA impl)'
+; CHECK-MEMCPY: Executing Pass 'Basic Alias Analysis (stateless AA impl)'
 ; CHECK: Executing Pass 'Combine redundant instructions'
 
+target datalayout = "p:8:8-n8"
+
 declare void @otherfn([4 x i8]*)
 declare i32 @__gxx_personality_v0(...)
+declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture)
+@c = external global i8*, align 1
 
 ; This function is one where if we didn't free basicaa after memcpyopt then the
 ; usage of basicaa in instcombine would cause a segfault due to stale phi-values
@@ -48,3 +53,28 @@ lpad:
   call void @otherfn([4 x i8]* nonnull %arr)
   unreachable
 }
+
+; When running instcombine after memdep, the basicaa used by instcombine uses
+; the phivalues that memdep used. This would then cause a segfault due to
+; instcombine deleting a phi whose values had been cached.
+define void @fn2() {
+entry:
+  %a = alloca i8, align 1
+  %0 = load i8*, i8** @c, align 1
+  %1 = bitcast i8* %0 to i8**
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  %d.0 = phi i8** [ %1, %entry ], [ null, %for.body ]
+  br i1 undef, label %for.body, label %for.cond.cleanup
+
+for.body:                                         ; preds = %for.cond
+  store volatile i8 undef, i8* %a, align 1
+  br label %for.cond
+
+for.cond.cleanup:                                 ; preds = %for.cond
+  call void @llvm.lifetime.end.p0i8(i64 1, i8* %a)
+  %2 = load i8*, i8** %d.0, align 1
+  store i8* %2, i8** @c, align 1
+  ret void
+}