From 720a2ed6d99d5665cc1601426353c84cc76fffbb Mon Sep 17 00:00:00 2001
From: Dan Gohman <gohman@apple.com>
Date: Fri, 12 Nov 2010 02:19:17 +0000
Subject: [PATCH] Enhance DSE to handle the case where a free call makes more
 than one store dead. This is especially noticeable in
 SingleSource/Benchmarks/Shootout/objinst.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118875 91177308-0d34-0410-b5e6-96231b3b80d8
---
 .../Scalar/DeadStoreElimination.cpp           | 36 ++++++++++++-------
 test/Transforms/DeadStoreElimination/free.ll  | 14 ++++++++
 2 files changed, 38 insertions(+), 12 deletions(-)

diff --git a/lib/Transforms/Scalar/DeadStoreElimination.cpp b/lib/Transforms/Scalar/DeadStoreElimination.cpp
index d81d302ebaf..1ea0b15e4c9 100644
--- a/lib/Transforms/Scalar/DeadStoreElimination.cpp
+++ b/lib/Transforms/Scalar/DeadStoreElimination.cpp
@@ -59,6 +59,7 @@ namespace {
     
     bool runOnBasicBlock(BasicBlock &BB);
     bool handleFreeWithNonTrivialDependency(const CallInst *F,
+                                            Instruction *Inst,
                                             MemDepResult Dep);
     bool handleEndBlock(BasicBlock &BB);
     bool RemoveUndeadPointers(Value *Ptr, uint64_t killPointerSize,
@@ -212,7 +213,7 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) {
   
     // Handle frees whose dependencies are non-trivial.
     if (const CallInst *F = isFreeCall(Inst)) {
-      MadeChange |= handleFreeWithNonTrivialDependency(F, InstDep);
+      MadeChange |= handleFreeWithNonTrivialDependency(F, Inst, InstDep);
       continue;
     }
     
@@ -298,23 +299,34 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) {
 /// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose
 /// dependency is a store to a field of that structure.
 bool DSE::handleFreeWithNonTrivialDependency(const CallInst *F,
+                                             Instruction *Inst,
                                              MemDepResult Dep) {
   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
+  MemoryDependenceAnalysis &MD = getAnalysis<MemoryDependenceAnalysis>();
   
-  Instruction *Dependency = Dep.getInst();
-  if (!Dependency || !doesClobberMemory(Dependency) || !isElidable(Dependency))
-    return false;
+  do {
+    Instruction *Dependency = Dep.getInst();
+    if (!Dependency || !doesClobberMemory(Dependency) || !isElidable(Dependency))
+      return false;
   
-  Value *DepPointer = getPointerOperand(Dependency)->getUnderlyingObject();
+    Value *DepPointer = getPointerOperand(Dependency)->getUnderlyingObject();
 
-  // Check for aliasing.
-  if (AA.alias(F->getArgOperand(0), 1, DepPointer, 1) !=
-         AliasAnalysis::MustAlias)
-    return false;
+    // Check for aliasing.
+    if (AA.alias(F->getArgOperand(0), 1, DepPointer, 1) !=
+           AliasAnalysis::MustAlias)
+      return false;
   
-  // DCE instructions only used to calculate that store
-  DeleteDeadInstruction(Dependency);
-  ++NumFastStores;
+    // DCE instructions only used to calculate that store
+    DeleteDeadInstruction(Dependency);
+    ++NumFastStores;
+
+    // Inst's old Dependency is now deleted. Compute the next dependency,
+    // which may also be dead, as in
+    //    s[0] = 0;
+    //    s[1] = 0; // This has just been deleted.
+    //    free(s);
+    Dep = MD.getDependency(Inst);
+  } while (!Dep.isNonLocal());
   return true;
 }
 
diff --git a/test/Transforms/DeadStoreElimination/free.ll b/test/Transforms/DeadStoreElimination/free.ll
index 0b44a4c00da..3c980ccac6b 100644
--- a/test/Transforms/DeadStoreElimination/free.ll
+++ b/test/Transforms/DeadStoreElimination/free.ll
@@ -24,3 +24,17 @@ define void @test2({i32, i32}* %P) {
 	ret void
 }
 
+; CHECK: @test4
+; CHECK-NOT: store
+; CHECK: ret void
+define void @test4() {
+  %m = call i8* @malloc(i64 24)
+  store i8 0, i8* %m
+  %m1 = getelementptr i8* %m, i64 1
+  store i8 1, i8* %m1
+  call void @free(i8* %m)
+  ret void
+}
+
+declare void @free(i8*)
+declare i8* @malloc(i64)
-- 
2.34.1