[ADCE] Add code to remove dead branches

Summary:
This is last in of a series of patches to evolve ADCE.cpp to support
removing of unnecessary control flow.

This patch adds the code to update the control and data flow graphs
to remove the dead control flow.

Also update unit tests to test the capability to remove dead,
may-be-infinite loop which is enabled by the switch
-adce-remove-loops.

Previous patches:

D23824 [ADCE] Add handling of PHI nodes when removing control flow
D23559 [ADCE] Add control dependence computation
D23225 [ADCE] Modify data structures to support removing control flow
D23065 [ADCE] Refactor anticipating new functionality (NFC)
D23102 [ADCE] Refactoring for new functionality (NFC)

Reviewers: dberlin, majnemer, nadav, mehdi_amini

Subscribers: llvm-commits, david2050, freik, twoh

Differential Revision: https://reviews.llvm.org/D24918

llvm-svn: 289548

17 files changed, 101 insertions, 7 deletions

diff --git a/llvm/test/Transforms/ADCE/2002-05-23-ZeroArgPHITest.ll b/llvm/test/Transforms/ADCE/2002-05-23-ZeroArgPHITest.ll
index 8d1beec8ed3..a9da9c70380 100644
--- a/llvm/test/Transforms/ADCE/2002-05-23-ZeroArgPHITest.ll
+++ b/llvm/test/Transforms/ADCE/2002-05-23-ZeroArgPHITest.ll
@@ -4,7 +4,8 @@
 ; removed even though there were uses still around.  Now the uses are filled
 ; in with a dummy value before the PHI is deleted.
 ;
-; RUN: opt < %s -adce
+; RUN: opt < %s -S -adce | grep bb1
+; RUN: opt < %s -S -adce -adce-remove-loops | FileCheck %s
 	
         %node_t = type { double*, %node_t*, %node_t**, double**, double*, i32, i32 }
 
@@ -17,6 +18,7 @@ bb0:
 bb1:            ; preds = %bb0
         %reg107 = load %node_t*, %node_t** %nodelist.upgrd.1              ; <%node_t*> [#uses=2]
         %cond211 = icmp eq %node_t* %reg107, null               ; <i1> [#uses=1]
+; CHECK: br label %bb3
         br i1 %cond211, label %bb3, label %bb2
 
 bb2:            ; preds = %bb2, %bb1
@@ -24,6 +26,7 @@ bb2:            ; preds = %bb2, %bb1
         %reg212 = getelementptr %node_t, %node_t* %reg109, i64 0, i32 1          ; <%node_t**> [#uses=1]
         %reg110 = load %node_t*, %node_t** %reg212                ; <%node_t*> [#uses=2]
         %cond213 = icmp ne %node_t* %reg110, null               ; <i1> [#uses=1]
+; CHECK: br label %bb3
         br i1 %cond213, label %bb2, label %bb3
 
 bb3:            ; preds = %bb2, %bb1
diff --git a/llvm/test/Transforms/ADCE/2002-05-28-Crash-distilled.ll b/llvm/test/Transforms/ADCE/2002-05-28-Crash-distilled.ll
index 337be9f4fa4..2fefd0a5f98 100644
--- a/llvm/test/Transforms/ADCE/2002-05-28-Crash-distilled.ll
+++ b/llvm/test/Transforms/ADCE/2002-05-28-Crash-distilled.ll
@@ -1,6 +1,7 @@
 ; This testcase is a distilled form of: 2002-05-28-Crash.ll
 
 ; RUN: opt < %s -adce 
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
 
 define float @test(i32 %i) {
         %F = sitofp i32 %i to float             ; <float> [#uses=1]
@@ -9,6 +10,7 @@ define float @test(i32 %i) {
 
 Loop:           ; preds = %Loop, %0
         %B = icmp ne i32 %I, 0          ; <i1> [#uses=1]
+; CHECK:   br label %Out
         br i1 %B, label %Out, label %Loop
 
 Out:            ; preds = %Loop
diff --git a/llvm/test/Transforms/ADCE/2002-05-28-Crash.ll b/llvm/test/Transforms/ADCE/2002-05-28-Crash.ll
index d88580afad0..3090792a55a 100644
--- a/llvm/test/Transforms/ADCE/2002-05-28-Crash.ll
+++ b/llvm/test/Transforms/ADCE/2002-05-28-Crash.ll
@@ -12,6 +12,7 @@
 ;}
 ;
 ; RUN: opt < %s -adce
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
 
 define i32 @rx_bitset_empty(i32 %size, i32* %set) {
 bb1:
@@ -28,6 +29,7 @@ bb1:
         %reg124 = getelementptr i32, i32* %set, i64 %reg114-idxcast-offset.upgrd.1           ; <i32*> [#uses=1]
         %reg125 = load i32, i32* %reg124             ; <i32> [#uses=1]
         %cond232 = icmp ne i32 %reg125, 0               ; <i1> [#uses=1]
+; CHECK: br label %bb3
         br i1 %cond232, label %bb3, label %bb2
 
 bb2:            ; preds = %bb2, %bb1
diff --git a/llvm/test/Transforms/ADCE/2002-07-17-AssertionFailure.ll b/llvm/test/Transforms/ADCE/2002-07-17-AssertionFailure.ll
index ff8bdb3fd3b..a83d856e9d7 100644
--- a/llvm/test/Transforms/ADCE/2002-07-17-AssertionFailure.ll
+++ b/llvm/test/Transforms/ADCE/2002-07-17-AssertionFailure.ll
@@ -3,11 +3,12 @@
 ; block in this function, it would work fine, but that would be the part we 
 ; have to fix now, wouldn't it....
 ;
-; RUN: opt < %s -adce
+; RUN: opt < %s -adce -S | FileCheck %s
 
 define void @foo(i8* %reg5481) {
         %cast611 = bitcast i8* %reg5481 to i8**         ; <i8**> [#uses=1]
         %reg162 = load i8*, i8** %cast611            ; <i8*> [#uses=1]
+; CHECK-NOT: ptrtoint
         ptrtoint i8* %reg162 to i32             ; <i32>:1 [#uses=0]
         ret void
 }
diff --git a/llvm/test/Transforms/ADCE/2002-07-17-PHIAssertion.ll b/llvm/test/Transforms/ADCE/2002-07-17-PHIAssertion.ll
index 1bf79e8ec6c..bb8ef26c61c 100644
--- a/llvm/test/Transforms/ADCE/2002-07-17-PHIAssertion.ll
+++ b/llvm/test/Transforms/ADCE/2002-07-17-PHIAssertion.ll
@@ -1,6 +1,6 @@
 ; This testcase was extracted from the gzip SPEC benchmark
 ;
-; RUN: opt < %s -adce
+; RUN: opt < %s -adce | FileCheck %s
 
 @bk = external global i32               ; <i32*> [#uses=2]
 @hufts = external global i32            ; <i32*> [#uses=1]
@@ -16,6 +16,8 @@ bb2:            ; preds = %bb6, %bb0
 bb3:            ; preds = %bb2
         br label %UnifiedExitNode
 
+; CHECK-NOT: bb4:
+; CHECK-NOT: bb5:
 bb4:            ; preds = %bb2
         %reg117 = load i32, i32* @hufts              ; <i32> [#uses=2]
         %cond241 = icmp ule i32 %reg117, %reg128                ; <i1> [#uses=1]
diff --git a/llvm/test/Transforms/ADCE/2002-07-29-Segfault.ll b/llvm/test/Transforms/ADCE/2002-07-29-Segfault.ll
index 1c8e6e8adf0..6745555a406 100644
--- a/llvm/test/Transforms/ADCE/2002-07-29-Segfault.ll
+++ b/llvm/test/Transforms/ADCE/2002-07-29-Segfault.ll
@@ -1,4 +1,5 @@
 ; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -disable-output -adce-remove-loops
 
 define void @test() {
         br label %BB3
diff --git a/llvm/test/Transforms/ADCE/2003-01-22-PredecessorProblem.ll b/llvm/test/Transforms/ADCE/2003-01-22-PredecessorProblem.ll
index 17003be9fb1..ac395de6d41 100644
--- a/llvm/test/Transforms/ADCE/2003-01-22-PredecessorProblem.ll
+++ b/llvm/test/Transforms/ADCE/2003-01-22-PredecessorProblem.ll
@@ -1,5 +1,6 @@
 ; Testcase reduced from 197.parser by bugpoint
 ; RUN: opt < %s -adce 
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
 
 define void @conjunction_prune() {
 ; <label>:0
@@ -7,16 +8,20 @@ define void @conjunction_prune() {
 
 bb19:           ; preds = %bb23, %bb22, %0
         %reg205 = phi i8* [ null, %bb22 ], [ null, %bb23 ], [ null, %0 ]                ; <i8*> [#uses=1]
+; CHECK: br label %bb22
         br i1 false, label %bb21, label %bb22
 
 bb21:           ; preds = %bb19
         %cast455 = bitcast i8* %reg205 to i8**          ; <i8**> [#uses=0]
+; CHECK: br label %bb22
         br label %bb22
 
 bb22:           ; preds = %bb21, %bb19
+; CHECK: br label %bb23
         br i1 false, label %bb19, label %bb23
 
 bb23:           ; preds = %bb22
+; CHECK: br label %bb28
         br i1 false, label %bb19, label %bb28
 
 bb28:           ; preds = %bb23
diff --git a/llvm/test/Transforms/ADCE/2003-04-25-PHIPostDominateProblem.ll b/llvm/test/Transforms/ADCE/2003-04-25-PHIPostDominateProblem.ll
index d30df19fc7c..37adba599cd 100644
--- a/llvm/test/Transforms/ADCE/2003-04-25-PHIPostDominateProblem.ll
+++ b/llvm/test/Transforms/ADCE/2003-04-25-PHIPostDominateProblem.ll
@@ -2,7 +2,8 @@
 ; entries for it's postdominator.  But I think this can only happen when the 
 ; PHI node is dead, so we just avoid patching up dead PHI nodes.
 
-; RUN: opt < %s -adce
+; RUN: opt < %s -adce                    -S | FileCheck %s
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
 
 target datalayout = "e-p:32:32"
 
@@ -15,6 +16,7 @@ loopentry:              ; preds = %endif, %entry
         br i1 false, label %no_exit, label %return
 
 no_exit:                ; preds = %loopentry
+; CHECK: br label %then
         br i1 false, label %then, label %else
 
 then:           ; preds = %no_exit
diff --git a/llvm/test/Transforms/ADCE/2003-06-11-InvalidCFG.ll b/llvm/test/Transforms/ADCE/2003-06-11-InvalidCFG.ll
index 7c7e238f9d9..8ff98b7e7b3 100644
--- a/llvm/test/Transforms/ADCE/2003-06-11-InvalidCFG.ll
+++ b/llvm/test/Transforms/ADCE/2003-06-11-InvalidCFG.ll
@@ -1,4 +1,5 @@
 ; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -adce-remove-loops -disable-output
 
 @G = external global i32*               ; <i32**> [#uses=1]
 
diff --git a/llvm/test/Transforms/ADCE/2003-06-24-BadSuccessor.ll b/llvm/test/Transforms/ADCE/2003-06-24-BadSuccessor.ll
index 707e14aad0d..48513654f8d 100644
--- a/llvm/test/Transforms/ADCE/2003-06-24-BadSuccessor.ll
+++ b/llvm/test/Transforms/ADCE/2003-06-24-BadSuccessor.ll
@@ -1,4 +1,6 @@
 ; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -adce-remove-loops=true -disable-output
+
 target datalayout = "e-p:32:32"
 	%struct..CppObjTypeDesc = type { i32, i16, i16 }
 	%struct..TypeToken = type { i32, i16, i16 }
@@ -30,6 +32,7 @@ loopentry.1:		; preds = %then.53, %endif.14
 	br i1 false, label %no_exit.1, label %loopentry.0
 
 no_exit.1:		; preds = %loopentry.1
+; CHECK: switch
 	switch i32 0, label %label.17 [
 		 i32 2, label %label.11
 		 i32 19, label %label.10
diff --git a/llvm/test/Transforms/ADCE/2003-06-24-BasicFunctionality.ll b/llvm/test/Transforms/ADCE/2003-06-24-BasicFunctionality.ll
index f0de4316436..ac2a30d40b9 100644
--- a/llvm/test/Transforms/ADCE/2003-06-24-BasicFunctionality.ll
+++ b/llvm/test/Transforms/ADCE/2003-06-24-BasicFunctionality.ll
@@ -1,4 +1,5 @@
-; RUN: opt < %s -adce -simplifycfg -S | not grep then:
+; RUN: opt < %s -adce -S | FileCheck %s
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
 
 define void @dead_test8(i32* %data.1, i32 %idx.1) {
 entry:
@@ -17,7 +18,9 @@ no_exit:                ; preds = %endif, %no_exit.preheader
         %i.0 = phi i32 [ %inc.1, %endif ], [ 0, %no_exit.preheader ]            ; <i32> [#uses=1]
         %tmp.12 = load i32, i32* %tmp.11             ; <i32> [#uses=1]
         %tmp.14 = sub i32 0, %tmp.12            ; <i32> [#uses=1]
+; CHECK-NOT: %tmp.161
         %tmp.161 = icmp ne i32 %k.1, %tmp.14            ; <i1> [#uses=1]
+; CHECK: br label %then
         br i1 %tmp.161, label %then, label %else
 
 then:           ; preds = %no_exit
diff --git a/llvm/test/Transforms/ADCE/2003-09-15-InfLoopCrash.ll b/llvm/test/Transforms/ADCE/2003-09-15-InfLoopCrash.ll
index 499ac515e44..458045a086f 100644
--- a/llvm/test/Transforms/ADCE/2003-09-15-InfLoopCrash.ll
+++ b/llvm/test/Transforms/ADCE/2003-09-15-InfLoopCrash.ll
@@ -1,4 +1,5 @@
 ; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -adce-remove-loops -disable-output
 
 define i32 @main() {
         br label %loop
diff --git a/llvm/test/Transforms/ADCE/2003-11-16-MissingPostDominanceInfo.ll b/llvm/test/Transforms/ADCE/2003-11-16-MissingPostDominanceInfo.ll
index 5ba1a2eadfc..f60469a6163 100644
--- a/llvm/test/Transforms/ADCE/2003-11-16-MissingPostDominanceInfo.ll
+++ b/llvm/test/Transforms/ADCE/2003-11-16-MissingPostDominanceInfo.ll
@@ -1,4 +1,6 @@
 ; RUN: opt < %s -adce -simplifycfg -S | grep call
+; RUN: opt < %s -adce -adce-remove-loops -simplifycfg -S | grep call
+
 declare void @exit(i32)
 
 define i32 @main(i32 %argc) {
diff --git a/llvm/test/Transforms/ADCE/2004-05-04-UnreachableBlock.ll b/llvm/test/Transforms/ADCE/2004-05-04-UnreachableBlock.ll
index 7ee0f468af0..123b6832f0f 100644
--- a/llvm/test/Transforms/ADCE/2004-05-04-UnreachableBlock.ll
+++ b/llvm/test/Transforms/ADCE/2004-05-04-UnreachableBlock.ll
@@ -1,4 +1,5 @@
 ; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -adce-remove-loops -disable-output
 
 define void @test() {
 entry:
diff --git a/llvm/test/Transforms/ADCE/2016-09-06.ll b/llvm/test/Transforms/ADCE/2016-09-06.ll
new file mode 100644
index 00000000000..82c333bb45e
--- /dev/null
+++ b/llvm/test/Transforms/ADCE/2016-09-06.ll
@@ -0,0 +1,55 @@
+; RUN: opt < %s -sroa -adce -adce-remove-loops -S | FileCheck %s
+; ModuleID = 'test1.bc'
+source_filename = "test1.c"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind uwtable
+define i32 @foo(i32, i32, i32) #0 {
+  %4 = alloca i32, align 4
+  %5 = alloca i32, align 4
+  %6 = alloca i32, align 4
+  %7 = alloca i32, align 4
+  %8 = alloca i32, align 4
+  store i32 %0, i32* %4, align 4
+  store i32 %1, i32* %5, align 4
+  store i32 %2, i32* %6, align 4
+  store i32 0, i32* %7, align 4
+  %9 = load i32, i32* %5, align 4
+  %I10 = icmp ne i32 %9, 0
+  br i1 %I10, label %B11, label %B21
+
+B11: 
+  store i32 0, i32* %8, align 4
+  br label %B12
+
+B12:
+  %I13 = load i32, i32* %8, align 4
+  %I14 = load i32, i32* %6, align 4
+  %I15 = icmp slt i32 %I13, %I14
+; CHECK: br label %B20
+  br i1 %I15, label %B16, label %B20
+
+B16: 
+  br label %B17
+
+B17: 
+  %I18 = load i32, i32* %8, align 4
+  %I19 = add nsw i32 %I18, 1
+  store i32 %I19, i32* %8, align 4
+  br label %B12
+
+B20:
+  store i32 1, i32* %7, align 4
+  br label %B21
+
+B21: 
+  %I22 = load i32, i32* %7, align 4
+  ret i32 %I22
+}
+
+attributes #0 = { nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 4.0.0 (http://llvm.org/git/clang.git 5864a13abf4490e76ae2eb0896198e1305927df2)"}
diff --git a/llvm/test/Transforms/ADCE/basictest1.ll b/llvm/test/Transforms/ADCE/basictest1.ll
index 4d0d386384b..76bb5cabf66 100644
--- a/llvm/test/Transforms/ADCE/basictest1.ll
+++ b/llvm/test/Transforms/ADCE/basictest1.ll
@@ -1,4 +1,6 @@
-; RUN: opt < %s -adce -simplifycfg | llvm-dis	
+; RUN: opt < %s -adce -S | FileCheck %s
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
+
 %FILE = type { i32, i8*, i8*, i8, i8, i32, i32, i32 }
 	%spec_fd_t = type { i32, i32, i32, i8* }
 @__iob = external global [20 x %FILE]		; <[20 x %FILE]*> [#uses=1]
@@ -24,6 +26,7 @@ declare void @perror(i8*)
 define i32 @spec_getc(i32 %fd) {
 	%reg109 = load i32, i32* @dbglvl		; <i32> [#uses=1]
 	%cond266 = icmp sle i32 %reg109, 4		; <i1> [#uses=1]
+; CHECKL br label %bb3
 	br i1 %cond266, label %bb3, label %bb2
 
 bb2:		; preds = %0
@@ -55,6 +58,7 @@ bb5:		; preds = %bb3
 bb6:		; preds = %bb5
 	%reg134 = load i32, i32* @dbglvl		; <i32> [#uses=1]
 	%cond271 = icmp sle i32 %reg134, 4		; <i1> [#uses=1]
+; CHECK: br label %bb8
 	br i1 %cond271, label %bb8, label %bb7
 
 bb7:		; preds = %bb6
@@ -77,6 +81,7 @@ bb9:		; preds = %bb5
 	store i32 %reg157, i32* %idx5
 	%reg163 = load i32, i32* @dbglvl		; <i32> [#uses=1]
 	%cond272 = icmp sle i32 %reg163, 4		; <i1> [#uses=1]
+; CHECK: br label %bb11
 	br i1 %cond272, label %bb11, label %bb10
 
 bb10:		; preds = %bb9
diff --git a/llvm/test/Transforms/ADCE/basictest2.ll b/llvm/test/Transforms/ADCE/basictest2.ll
index 26b2e85cccb..50336e18705 100644
--- a/llvm/test/Transforms/ADCE/basictest2.ll
+++ b/llvm/test/Transforms/ADCE/basictest2.ll
@@ -1,4 +1,6 @@
-; RUN: opt < %s -adce -simplifycfg | llvm-dis
+; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
+
 	%FILE = type { i32, i8*, i8*, i8, i8, i32, i32, i32 }
 	%spec_fd_t = type { i32, i32, i32, i8* }
 @__iob = external global [20 x %FILE]		; <[20 x %FILE]*> [#uses=1]
@@ -24,6 +26,7 @@ declare void @perror(i8*)
 define i32 @spec_getc(i32 %fd) {
 	%reg109 = load i32, i32* @dbglvl		; <i32> [#uses=1]
 	%cond266 = icmp sle i32 %reg109, 4		; <i1> [#uses=1]
+; CHECK: br label %bb3
 	br i1 %cond266, label %bb3, label %bb2
 
 bb2:		; preds = %0
@@ -55,6 +58,7 @@ bb5:		; preds = %bb3
 bb6:		; preds = %bb5
 	%reg134 = load i32, i32* @dbglvl		; <i32> [#uses=1]
 	%cond271 = icmp sle i32 %reg134, 4		; <i1> [#uses=1]
+; CHECK: br label %bb8
 	br i1 %cond271, label %bb8, label %bb7
 
 bb7:		; preds = %bb6
@@ -77,6 +81,7 @@ bb9:		; preds = %bb5
 	store i32 %reg157, i32* %idx5
 	%reg163 = load i32, i32* @dbglvl		; <i32> [#uses=1]
 	%cond272 = icmp sle i32 %reg163, 4		; <i1> [#uses=1]
+; CHECK: br label %bb11
 	br i1 %cond272, label %bb11, label %bb10
 
 bb10:		; preds = %bb9