Make SCEVUnknown a CallbackVH, so that it can be notified directly

of Value deletions and RAUWs, instead of relying on ScalarEvolution's
Scalars map being notified, as that's complicated at best, and
insufficient in general.

This means SCEVUnknown needs a non-trivial destructor, so introduce
a mechanism to allow ScalarEvolution to locate all the SCEVUnknowns.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110086 91177308-0d34-0410-b5e6-96231b3b80d8

6 files changed, 167 insertions, 56 deletions

diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index 1b27efb995..7f224203ab 100644
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -661,6 +661,11 @@ namespace llvm {
   private:
     FoldingSet<SCEV> UniqueSCEVs;
     BumpPtrAllocator SCEVAllocator;
+
+    /// FirstUnknown - The head of a linked list of all SCEVUnknown
+    /// values that have been allocated. This is used by releaseMemory
+    /// to locate them all and call their destructors.
+    SCEVUnknown *FirstUnknown;
   };
 }
 
diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h
index ec4ac071da..3e846e1be8 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpressions.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h
@@ -520,18 +520,28 @@ namespace llvm {
   /// value, and only represent it as its LLVM Value.  This is the "bottom"
   /// value for the analysis.
   ///
-  class SCEVUnknown : public SCEV {
+  class SCEVUnknown : public SCEV, private CallbackVH {
     friend class ScalarEvolution;
-    friend class ScalarEvolution::SCEVCallbackVH;
 
-    // This should be an AssertingVH, however SCEVUnknowns are allocated in a
-    // BumpPtrAllocator so their destructors are never called.
-    Value *V;
-    SCEVUnknown(const FoldingSetNodeIDRef ID, Value *v) :
-      SCEV(ID, scUnknown), V(v) {}
+    // Implement CallbackVH.
+    virtual void deleted();
+    virtual void allUsesReplacedWith(Value *New);
+
+    /// SE - The parent ScalarEvolution value. This is used to update
+    /// the parent's maps when the value associated with a SCEVUnknown
+    /// is deleted or RAUW'd.
+    ScalarEvolution *SE;
+
+    /// Next - The next pointer in the linked list of all
+    /// SCEVUnknown instances owned by a ScalarEvolution.
+    SCEVUnknown *Next;
+
+    SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V,
+                ScalarEvolution *se, SCEVUnknown *next) :
+      SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {}
 
   public:
-    Value *getValue() const { return V; }
+    Value *getValue() const { return getValPtr(); }
 
     /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special
     /// constant representing a type size, alignment, or field offset in
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index c6b7ad61d0..1dc8e83b12 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -337,12 +337,36 @@ void SCEVAddRecExpr::print(raw_ostream &OS) const {
   OS << ">";
 }
 
+void SCEVUnknown::deleted() {
+  // Clear this SCEVUnknown from ValuesAtScopes.
+  SE->ValuesAtScopes.erase(this);
+
+  // Remove this SCEVUnknown from the uniquing map.
+  SE->UniqueSCEVs.RemoveNode(this);
+
+  // Release the value.
+  setValPtr(0);
+}
+
+void SCEVUnknown::allUsesReplacedWith(Value *New) {
+  // Clear this SCEVUnknown from ValuesAtScopes.
+  SE->ValuesAtScopes.erase(this);
+
+  // Remove this SCEVUnknown from the uniquing map.
+  SE->UniqueSCEVs.RemoveNode(this);
+
+  // Update this SCEVUnknown to point to the new value. This is needed
+  // because there may still be outstanding SCEVs which still point to
+  // this SCEVUnknown.
+  setValPtr(New);
+}
+
 bool SCEVUnknown::isLoopInvariant(const Loop *L) const {
   // All non-instruction values are loop invariant.  All instructions are loop
   // invariant if they are not contained in the specified loop.
   // Instructions are never considered invariant in the function body
   // (null loop) because they are defined within the "loop".
-  if (Instruction *I = dyn_cast<Instruction>(V))
+  if (Instruction *I = dyn_cast<Instruction>(getValue()))
     return L && !L->contains(I);
   return true;
 }
@@ -360,11 +384,11 @@ bool SCEVUnknown::properlyDominates(BasicBlock *BB, DominatorTree *DT) const {
 }
 
 const Type *SCEVUnknown::getType() const {
-  return V->getType();
+  return getValue()->getType();
 }
 
 bool SCEVUnknown::isSizeOf(const Type *&AllocTy) const {
-  if (ConstantExpr *VCE = dyn_cast<ConstantExpr>(V))
+  if (ConstantExpr *VCE = dyn_cast<ConstantExpr>(getValue()))
     if (VCE->getOpcode() == Instruction::PtrToInt)
       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(VCE->getOperand(0)))
         if (CE->getOpcode() == Instruction::GetElementPtr &&
@@ -381,7 +405,7 @@ bool SCEVUnknown::isSizeOf(const Type *&AllocTy) const {
 }
 
 bool SCEVUnknown::isAlignOf(const Type *&AllocTy) const {
-  if (ConstantExpr *VCE = dyn_cast<ConstantExpr>(V))
+  if (ConstantExpr *VCE = dyn_cast<ConstantExpr>(getValue()))
     if (VCE->getOpcode() == Instruction::PtrToInt)
       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(VCE->getOperand(0)))
         if (CE->getOpcode() == Instruction::GetElementPtr &&
@@ -406,7 +430,7 @@ bool SCEVUnknown::isAlignOf(const Type *&AllocTy) const {
 }
 
 bool SCEVUnknown::isOffsetOf(const Type *&CTy, Constant *&FieldNo) const {
-  if (ConstantExpr *VCE = dyn_cast<ConstantExpr>(V))
+  if (ConstantExpr *VCE = dyn_cast<ConstantExpr>(getValue()))
     if (VCE->getOpcode() == Instruction::PtrToInt)
       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(VCE->getOperand(0)))
         if (CE->getOpcode() == Instruction::GetElementPtr &&
@@ -448,7 +472,7 @@ void SCEVUnknown::print(raw_ostream &OS) const {
   }
 
   // Otherwise just print it normally.
-  WriteAsOperand(OS, V, false);
+  WriteAsOperand(OS, getValue(), false);
 }
 
 //===----------------------------------------------------------------------===//
@@ -2350,8 +2374,14 @@ const SCEV *ScalarEvolution::getUnknown(Value *V) {
   ID.AddInteger(scUnknown);
   ID.AddPointer(V);
   void *IP = 0;
-  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
-  SCEV *S = new (SCEVAllocator) SCEVUnknown(ID.Intern(SCEVAllocator), V);
+  if (SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) {
+    assert(cast<SCEVUnknown>(S)->getValue() == V &&
+           "Stale SCEVUnknown in uniquing map!");
+    return S;
+  }
+  SCEV *S = new (SCEVAllocator) SCEVUnknown(ID.Intern(SCEVAllocator), V, this,
+                                            FirstUnknown);
+  FirstUnknown = cast<SCEVUnknown>(S);
   UniqueSCEVs.InsertNode(S, IP);
   return S;
 }
@@ -3664,26 +3694,6 @@ void ScalarEvolution::forgetLoop(const Loop *L) {
 /// changed a value in a way that may effect its value, or which may
 /// disconnect it from a def-use chain linking it to a loop.
 void ScalarEvolution::forgetValue(Value *V) {
-  // If there's a SCEVUnknown tying this value into the SCEV
-  // space, remove it from the folding set map. The SCEVUnknown
-  // object and any other SCEV objects which reference it
-  // (transitively) remain allocated, effectively leaked until
-  // the underlying BumpPtrAllocator is freed.
-  //
-  // This permits SCEV pointers to be used as keys in maps
-  // such as the ValuesAtScopes map.
-  FoldingSetNodeID ID;
-  ID.AddInteger(scUnknown);
-  ID.AddPointer(V);
-  void *IP;
-  if (SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) {
-    UniqueSCEVs.RemoveNode(S);
-
-    // This isn't necessary, but we might as well remove the
-    // value from the ValuesAtScopes map too.
-    ValuesAtScopes.erase(S);
-  }
-
   Instruction *I = dyn_cast<Instruction>(V);
   if (!I) return;
 
@@ -5693,27 +5703,10 @@ void ScalarEvolution::SCEVCallbackVH::deleted() {
 void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(Value *V) {
   assert(SE && "SCEVCallbackVH called with a null ScalarEvolution!");
 
-  Value *Old = getValPtr();
-
-  // If there's a SCEVUnknown tying this value into the SCEV
-  // space, replace the SCEVUnknown's value with the new value
-  // for the benefit of any SCEVs still referencing it, and
-  // and remove it from the folding set map so that new scevs
-  // don't reference it.
-  FoldingSetNodeID ID;
-  ID.AddInteger(scUnknown);
-  ID.AddPointer(Old);
-  void *IP;
-  if (SCEVUnknown *S = cast_or_null<SCEVUnknown>(
-        SE->UniqueSCEVs.FindNodeOrInsertPos(ID, IP))) {
-    S->V = V;
-    SE->UniqueSCEVs.RemoveNode(S);
-    SE->ValuesAtScopes.erase(S);
-  }
-
   // Forget all the expressions associated with users of the old value,
   // so that future queries will recompute the expressions using the new
   // value.
+  Value *Old = getValPtr();
   SmallVector<User *, 16> Worklist;
   SmallPtrSet<User *, 8> Visited;
   for (Value::use_iterator UI = Old->use_begin(), UE = Old->use_end();
@@ -5749,7 +5742,7 @@ ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
 //===----------------------------------------------------------------------===//
 
 ScalarEvolution::ScalarEvolution()
-  : FunctionPass(&ID) {
+  : FunctionPass(&ID), FirstUnknown(0) {
 }
 
 bool ScalarEvolution::runOnFunction(Function &F) {
@@ -5761,6 +5754,12 @@ bool ScalarEvolution::runOnFunction(Function &F) {
 }
 
 void ScalarEvolution::releaseMemory() {
+  // Iterate through all the SCEVUnknown instances and call their
+  // destructors, so that they release their references to their values.
+  for (SCEVUnknown *U = FirstUnknown; U; U = U->Next)
+    U->~SCEVUnknown();
+  FirstUnknown = 0;
+
   Scalars.clear();
   BackedgeTakenCounts.clear();
   ConstantEvolutionLoopExitValue.clear();
diff --git a/unittests/Analysis/Makefile b/unittests/Analysis/Makefile
new file mode 100644
index 0000000000..f89240ec70
--- /dev/null
+++ b/unittests/Analysis/Makefile
@@ -0,0 +1,15 @@
+##===- unittests/Analysis/Makefile -------------------------*- Makefile -*-===##
+#
+#                     The LLVM Compiler Infrastructure
+#
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+#
+##===----------------------------------------------------------------------===##
+
+LEVEL = ../..
+TESTNAME = Analysis
+LINK_COMPONENTS := core support target analysis ipa
+
+include $(LEVEL)/Makefile.config
+include $(LLVM_SRC_ROOT)/unittests/Makefile.unittest
diff --git a/unittests/Analysis/ScalarEvolutionTest.cpp b/unittests/Analysis/ScalarEvolutionTest.cpp
new file mode 100644
index 0000000000..b7341603cf
--- /dev/null
+++ b/unittests/Analysis/ScalarEvolutionTest.cpp
@@ -0,0 +1,82 @@
+//===- ScalarEvolutionsTest.cpp - ScalarEvolution unit tests --------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include <llvm/Analysis/ScalarEvolutionExpressions.h>
+#include <llvm/GlobalVariable.h>
+#include <llvm/Constants.h>
+#include <llvm/LLVMContext.h>
+#include <llvm/Module.h>
+#include <llvm/PassManager.h>
+#include "gtest/gtest.h"
+
+namespace llvm {
+namespace {
+
+TEST(ScalarEvolutionsTest, SCEVUnknownRAUW) {
+  LLVMContext Context;
+  Module M("world", Context);
+
+  const FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context),
+                                              std::vector<const Type *>(), false);
+  Function *F = cast<Function>(M.getOrInsertFunction("f", FTy));
+  BasicBlock *BB = BasicBlock::Create(Context, "entry", F);
+  ReturnInst::Create(Context, 0, BB);
+
+  const Type *Ty = Type::getInt1Ty(Context);
+  Constant *Init = Constant::getNullValue(Ty);
+  Value *V0 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V0");
+  Value *V1 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V1");
+  Value *V2 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V2");
+
+  // Create a ScalarEvolution and "run" it so that it gets initialized.
+  PassManager PM;
+  ScalarEvolution &SE = *new ScalarEvolution();
+  PM.add(&SE);
+  PM.run(M);
+
+  const SCEV *S0 = SE.getSCEV(V0);
+  const SCEV *S1 = SE.getSCEV(V1);
+  const SCEV *S2 = SE.getSCEV(V2);
+
+  const SCEV *P0 = SE.getAddExpr(S0, S0);
+  const SCEV *P1 = SE.getAddExpr(S1, S1);
+  const SCEV *P2 = SE.getAddExpr(S2, S2);
+
+  const SCEVMulExpr *M0 = cast<SCEVMulExpr>(P0);
+  const SCEVMulExpr *M1 = cast<SCEVMulExpr>(P1);
+  const SCEVMulExpr *M2 = cast<SCEVMulExpr>(P2);
+
+  EXPECT_EQ(cast<SCEVConstant>(M0->getOperand(0))->getValue()->getZExtValue(),
+            2u);
+  EXPECT_EQ(cast<SCEVConstant>(M1->getOperand(0))->getValue()->getZExtValue(),
+            2u);
+  EXPECT_EQ(cast<SCEVConstant>(M2->getOperand(0))->getValue()->getZExtValue(),
+            2u);
+
+  // Before the RAUWs, these are all pointing to separate values.
+  EXPECT_EQ(cast<SCEVUnknown>(M0->getOperand(1))->getValue(), V0);
+  EXPECT_EQ(cast<SCEVUnknown>(M1->getOperand(1))->getValue(), V1);
+  EXPECT_EQ(cast<SCEVUnknown>(M2->getOperand(1))->getValue(), V2);
+
+  // Do some RAUWs.
+  V2->replaceAllUsesWith(V1);
+  V1->replaceAllUsesWith(V0);
+
+  // After the RAUWs, these should all be pointing to V0.
+  EXPECT_EQ(cast<SCEVUnknown>(M0->getOperand(1))->getValue(), V0);
+  EXPECT_EQ(cast<SCEVUnknown>(M1->getOperand(1))->getValue(), V0);
+  EXPECT_EQ(cast<SCEVUnknown>(M2->getOperand(1))->getValue(), V0);
+
+  // Manually clean up, since we allocated new SCEV objects after the
+  // pass was finished.
+  SE.releaseMemory();
+}
+
+}  // end anonymous namespace
+}  // end namespace llvm
diff --git a/unittests/Makefile b/unittests/Makefile
index 9f377cd744..0401cd1c67 100644
--- a/unittests/Makefile
+++ b/unittests/Makefile
@@ -9,7 +9,7 @@
 
 LEVEL = ..
 
-PARALLEL_DIRS = ADT ExecutionEngine Support Transforms VMCore
+PARALLEL_DIRS = ADT ExecutionEngine Support Transforms VMCore Analysis
 
 include $(LEVEL)/Makefile.common