From 77d76b7ef7fba0cf694977ef5abbdea28e600833 Mon Sep 17 00:00:00 2001
From: Owen Anderson <resistor@mac.com>
Date: Wed, 2 Jul 2008 18:05:19 +0000
Subject: [PATCH] Add support to ADCE for pruning unreachable blocks.  This
 addresses the final part of PR2509.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53038 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Scalar/ADCE.cpp                | 44 ++++++++++++++++++-
 .../Transforms/ADCE/2008-07-02-Unreachable.ll | 37 ++++++++++++++++
 2 files changed, 80 insertions(+), 1 deletion(-)
 create mode 100644 test/Transforms/ADCE/2008-07-02-Unreachable.ll

diff --git a/lib/Transforms/Scalar/ADCE.cpp b/lib/Transforms/Scalar/ADCE.cpp
index b9b828dde09..f7035e576b3 100644
--- a/lib/Transforms/Scalar/ADCE.cpp
+++ b/lib/Transforms/Scalar/ADCE.cpp
@@ -16,12 +16,15 @@
 
 #define DEBUG_TYPE "adce"
 #include "llvm/Transforms/Scalar.h"
+#include "llvm/BasicBlock.h"
 #include "llvm/Instructions.h"
 #include "llvm/Pass.h"
+#include "llvm/Support/CFG.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/InstIterator.h"
-#include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/SmallVector.h"
 
 using namespace llvm;
@@ -36,6 +39,9 @@ namespace {
     DenseSet<Instruction*> alive;
     SmallVector<Instruction*, 1024> worklist;
     
+    DenseSet<BasicBlock*> reachable;
+    SmallVector<BasicBlock*, 1024> unreachable;
+    
     virtual bool runOnFunction(Function& F);
     
     virtual void getAnalysisUsage(AnalysisUsage& AU) const {
@@ -51,6 +57,42 @@ static RegisterPass<ADCE> X("adce", "Aggressive Dead Code Elimination");
 bool ADCE::runOnFunction(Function& F) {
   alive.clear();
   worklist.clear();
+  reachable.clear();
+  unreachable.clear();
+  
+  // First, collect the set of reachable blocks ...
+  for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()),
+       DE = df_end(&F.getEntryBlock()); DI != DE; ++DI)
+    reachable.insert(*DI);
+  
+  // ... and then invert it into the list of unreachable ones.  These
+  // blocks will be removed from the function.
+  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
+    if (!reachable.count(FI))
+      unreachable.push_back(FI);
+  
+  // Prepare to remove blocks by removing the PHI node entries for those blocks
+  // in their successors, and remove them from reference counting.
+  for (SmallVector<BasicBlock*, 1024>::iterator UI = unreachable.begin(),
+       UE = unreachable.end(); UI != UE; ++UI) {
+    BasicBlock* BB = *UI;
+    for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
+         SI != SE; ++SI) {
+      BasicBlock* succ = *SI;
+      BasicBlock::iterator succ_inst = succ->begin();
+      while (PHINode* P = dyn_cast<PHINode>(succ_inst)) {
+        P->removeIncomingValue(BB);
+        ++succ_inst;
+      }
+    }
+    
+    BB->dropAllReferences();
+  }
+  
+  // Finally, erase the unreachable blocks.
+  for (SmallVector<BasicBlock*, 1024>::iterator UI = unreachable.begin(),
+       UE = unreachable.end(); UI != UE; ++UI)
+    (*UI)->eraseFromParent();
   
   // Collect the set of "root" instructions that are known live.
   for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
diff --git a/test/Transforms/ADCE/2008-07-02-Unreachable.ll b/test/Transforms/ADCE/2008-07-02-Unreachable.ll
new file mode 100644
index 00000000000..60f0020cd15
--- /dev/null
+++ b/test/Transforms/ADCE/2008-07-02-Unreachable.ll
@@ -0,0 +1,37 @@
+; RUN: llvm-as < %s | opt -adce -simplifycfg | llvm-dis | not grep forcond
+; PR2509
+
+target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
+target triple = "i686-apple-darwin9.3.0"
+@g_3 = external global i8		; <i8*> [#uses=2]
+
+define i32 @func_1() nounwind  {
+entry:
+	br i1 false, label %ifelse, label %ifthen
+
+ifthen:		; preds = %entry
+	br label %ifend
+
+ifelse:		; preds = %entry
+	%tmp3 = load i8* @g_3		; <i8> [#uses=0]
+	br label %forcond.thread
+
+forcond.thread:		; preds = %ifelse
+	br label %afterfor
+
+forcond:		; preds = %forinc
+	br i1 false, label %afterfor, label %forbody
+
+forbody:		; preds = %forcond
+	br label %forinc
+
+forinc:		; preds = %forbody
+	br label %forcond
+
+afterfor:		; preds = %forcond, %forcond.thread
+	%tmp10 = load i8* @g_3		; <i8> [#uses=0]
+	br label %ifend
+
+ifend:		; preds = %afterfor, %ifthen
+	ret i32 0
+}
-- 
2.34.1