[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
diff --git a/llvm/test/Transforms/ADCE/2002-05-23-ZeroArgPHITest.ll b/llvm/test/Transforms/ADCE/2002-05-23-ZeroArgPHITest.ll
index 8d1beec..a9da9c7 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 @@
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 @@
%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 337be9f..2fefd0a 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 @@
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 d88580a..3090792 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 @@
%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 ff8bdb3..a83d856 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 1bf79e8..bb8ef26 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 @@
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 1c8e6e8..6745555 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 17003be..ac395de 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 @@
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 d30df19..37adba5 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 @@
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 7c7e238..8ff98b7 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 707e14a..4851365 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 @@
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 f0de431..ac2a30d 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 @@
%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 499ac51..458045a 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 5ba1a2e..f60469a 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 7ee0f46..123b683 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 0000000..82c333b
--- /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 4d0d386..76bb5cabf6 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 @@
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 @@
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 @@
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 26b2e85..50336e1 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 @@
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 @@
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 @@
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