Add new RegionInfo pass.

The RegionInfo pass detects single entry single exit regions in a function,
where a region is defined as any subgraph that is connected to the remaining
graph at only two spots.
Furthermore an hierarchical region tree is built.
Use it by calling "opt -regions analyze" or "opt -view-regions".

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

22 files changed, 886 insertions, 0 deletions

diff --git a/test/Analysis/RegionInfo/block_sort.ll b/test/Analysis/RegionInfo/block_sort.ll
new file mode 100644
index 0000000000..faec45a911
--- /dev/null
+++ b/test/Analysis/RegionInfo/block_sort.ll
@@ -0,0 +1,42 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats -analyze < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @BZ2_blockSort() nounwind {
+start:
+  br label %while
+
+while:
+  br label %while.body134.i.i
+
+while.body134.i.i:
+  br i1 1, label %end, label %w
+
+w:
+  br label %if.end140.i.i
+
+if.end140.i.i:
+  br i1 1, label %while.end186.i.i, label %if.end183.i.i
+
+if.end183.i.i:
+  br label %while.body134.i.i
+
+while.end186.i.i:
+  br label %while
+
+end:
+  ret void
+}
+; CHECK-NOT: =>
+; CHECK: [0] start => <Function Return>
+; CHECK: [1] while => end
+
+; STAT: 2 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: start, while, while.body134.i.i, end, w, if.end140.i.i, while.end186.i.i, if.end183.i.i,
+; BBIT: while, while.body134.i.i, w, if.end140.i.i, while.end186.i.i, if.end183.i.i,
+
+; RNIT: start, while => end, end,
+; RNIT: while, while.body134.i.i, w, if.end140.i.i, while.end186.i.i, if.end183.i.i,
diff --git a/test/Analysis/RegionInfo/cond_loop.ll b/test/Analysis/RegionInfo/cond_loop.ll
new file mode 100644
index 0000000000..2ce57c3c5f
--- /dev/null
+++ b/test/Analysis/RegionInfo/cond_loop.ll
@@ -0,0 +1,33 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @normal_condition() nounwind {
+5:
+        br label %"0"
+
+0:
+	br label %"1"
+1:
+	br i1 1, label %"2", label %"3"
+2:
+	ret void
+3:
+	br i1 1, label %"1", label %"4"
+4:
+        br label %"0"
+}
+
+; CHECK-NOT: =>
+; CHECK: [0] 5 => <Function Return>
+; CHECK: [1] 0 => 2
+
+; STAT: 2 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: 5, 0, 1, 2, 3, 4,
+; BBIT: 0, 1, 3, 4,
+
+; RNIT: 5, 0 => 2, 2,
+; RNIT: 0, 1, 3, 4,
diff --git a/test/Analysis/RegionInfo/condition_complicated.ll b/test/Analysis/RegionInfo/condition_complicated.ll
new file mode 100644
index 0000000000..7ca5c7c7b5
--- /dev/null
+++ b/test/Analysis/RegionInfo/condition_complicated.ll
@@ -0,0 +1,60 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define internal fastcc zeroext i8 @handle_compress() nounwind {
+end165:
+  br i1 1, label %false239, label %true181
+
+true181:
+  br i1 1, label %then187, label %else232
+
+then187:
+  br label %end265
+
+else232:
+  br i1 1, label %false239, label %then245
+
+false239:
+  br i1 1, label %then245, label %else259
+
+then245:
+  br i1 1, label %then251, label %end253
+
+then251:
+  br label %end253
+
+end253:
+  br label %end265
+
+else259:
+  br label %end265
+
+end265:
+  br i1 1, label %then291, label %end298
+
+then291:
+  br label %end298
+
+end298:
+  ret i8 1
+}
+
+; CHECK-NOT: =>
+; CHECK: [0] end165 => <Function Return>
+; CHECK-NEXT: [1] end165 => end265
+; CHECK-NEXT: [2] then245 => end253
+; CHECK-NEXT: [1] end265 => end298
+
+; STAT: 4 region - The # of regions
+
+; BBIT: end165, false239, then245, then251, end253, end265, then291, end298, else259, true181, then187, else232,
+; BBIT: end165, false239, then245, then251, end253, else259, true181, then187, else232,
+; BBIT: then245, then251,
+; BBIT: end265, then291,
+
+; RNIT: end165 => end265, end265 => end298, end298,
+; RNIT: end165, false239, then245 => end253, end253, else259, true181, then187, else232,
+; RNIT: then245, then251,
+; RNIT: end265, then291,
diff --git a/test/Analysis/RegionInfo/condition_complicated_2.ll b/test/Analysis/RegionInfo/condition_complicated_2.ll
new file mode 100644
index 0000000000..5fa940a61e
--- /dev/null
+++ b/test/Analysis/RegionInfo/condition_complicated_2.ll
@@ -0,0 +1,44 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define internal fastcc void @compress() nounwind {
+end33:
+  br i1 1, label %end124, label %lor.lhs.false95
+
+lor.lhs.false95:
+  br i1 1, label %then107, label %end172
+
+then107:
+  br i1 1, label %end124, label %then113
+
+then113:
+  br label %end124
+
+end124:
+  br label %exit
+
+end172:
+  br label %exit
+
+
+exit:
+  unreachable
+
+
+}
+; CHECK-NOT: =>
+; CHECK: [0] end33 => <Function Return>
+; CHECK-NEXT:      [1] end33 => exit
+; CHECK-NEXT:   [2] then107 => end124
+
+; STAT: 3 region - The # of regions
+
+; BBIT: end33, end124, exit, lor.lhs.false95, then107, then113, end172,
+; BBIT: end33, end124, lor.lhs.false95, then107, then113, end172,
+; BBIT: then107, then113,
+
+; RNIT: end33 => exit, exit,
+; RNIT: end33, end124, lor.lhs.false95, then107 => end124, end172,
+; RNIT: then107, then113,
diff --git a/test/Analysis/RegionInfo/condition_forward_edge.ll b/test/Analysis/RegionInfo/condition_forward_edge.ll
new file mode 100644
index 0000000000..098c9b6b46
--- /dev/null
+++ b/test/Analysis/RegionInfo/condition_forward_edge.ll
@@ -0,0 +1,26 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @normal_condition() nounwind {
+0:
+	br label %"1"
+1:
+	br i1 1, label %"2", label %"3"
+2:
+	br label %"3"
+3:
+	ret void
+}
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK: [1] 1 => 3
+
+; STAT: 2 region - The # of regions
+
+; BBIT: 0, 1, 2, 3,
+; BBIT: 1, 2,
+
+; RNIT: 0, 1 => 3, 3,
+; RNIT: 1, 2,
diff --git a/test/Analysis/RegionInfo/condition_same_exit.ll b/test/Analysis/RegionInfo/condition_same_exit.ll
new file mode 100644
index 0000000000..1b88596c0f
--- /dev/null
+++ b/test/Analysis/RegionInfo/condition_same_exit.ll
@@ -0,0 +1,31 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @normal_condition() nounwind {
+0:
+	br i1 1, label %"1", label %"4"
+
+1:
+	br i1 1, label %"2", label %"3"
+2:
+	br label %"4"
+3:
+	br label %"4"
+4:
+	ret void
+}
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK-NEXT: [1] 0 => 4
+; CHECK-NEXT:   [2] 1 => 4
+; STAT: 3 region - The # of regions
+
+; BBIT: 0, 1, 2, 4, 3,
+; BBIT: 0, 1, 2, 3,
+; BBIT: 1, 2, 3,
+
+; RNIT: 0 => 4, 4,
+; RNIT: 0, 1 => 4,
+; RNIT: 1, 2, 3,
diff --git a/test/Analysis/RegionInfo/condition_simple.ll b/test/Analysis/RegionInfo/condition_simple.ll
new file mode 100644
index 0000000000..19b154b647
--- /dev/null
+++ b/test/Analysis/RegionInfo/condition_simple.ll
@@ -0,0 +1,28 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @normal_condition() nounwind {
+0:
+	br label %"1"
+1:
+	br i1 1, label %"2", label %"3"
+2:
+	br label %"4"
+3:
+	br label %"4"
+4:
+	ret void
+}
+
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK-NEXT: [1] 1 => 4
+; STAT: 2 region - The # of regions
+
+; BBIT: 0, 1, 2, 4, 3,
+; BBIT: 1, 2, 3,
+
+; RNIT: 0, 1 => 4, 4,
+; RNIT: 1, 2, 3,
diff --git a/test/Analysis/RegionInfo/dg.exp b/test/Analysis/RegionInfo/dg.exp
new file mode 100644
index 0000000000..f2005891a5
--- /dev/null
+++ b/test/Analysis/RegionInfo/dg.exp
@@ -0,0 +1,3 @@
+load_lib llvm.exp
+
+RunLLVMTests [lsort [glob -nocomplain $srcdir/$subdir/*.{ll,c,cpp}]]
diff --git a/test/Analysis/RegionInfo/exit_in_condition.ll b/test/Analysis/RegionInfo/exit_in_condition.ll
new file mode 100644
index 0000000000..3b152d2f56
--- /dev/null
+++ b/test/Analysis/RegionInfo/exit_in_condition.ll
@@ -0,0 +1,38 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define internal fastcc zeroext i8 @handle_compress() nounwind {
+entry:
+  br label %outer
+
+outer:
+  br label %body
+
+body:
+  br i1 1, label %body.i, label %if.end
+
+body.i:
+  br i1 1, label %end, label %if.end
+
+if.end:
+  br label %if.then64
+
+if.then64:
+  br label %outer
+
+end:
+  ret i8 1
+}
+; CHECK-NOT: =>
+; CHECK: [0] entry => <Function Return>
+; CHECK-NEXT: [1] outer => end
+; STAT: 2 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: entry, outer, body, body.i, end, if.end, if.then64,
+; BBIT: outer, body, body.i, if.end, if.then64,
+
+; RNIT: entry, outer => end, end,
+; RNIT: outer, body, body.i, if.end, if.then64,
diff --git a/test/Analysis/RegionInfo/infinite_loop.ll b/test/Analysis/RegionInfo/infinite_loop.ll
new file mode 100644
index 0000000000..59cead4926
--- /dev/null
+++ b/test/Analysis/RegionInfo/infinite_loop.ll
@@ -0,0 +1,20 @@
+; RUN: opt -regions -analyze < %s 
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+
+define void @normal_condition() nounwind {
+0:
+	br label %"1"
+1:
+	br i1 1, label %"2", label %"3"
+2:
+	br label %"2"
+3:
+	br label %"4"
+4:
+	ret void
+}
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK: [1] 1 => 4
+; STAT: 2 region - The # of regions
+; STAT: 1 region - The # of simple regions
diff --git a/test/Analysis/RegionInfo/infinite_loop_2.ll b/test/Analysis/RegionInfo/infinite_loop_2.ll
new file mode 100644
index 0000000000..80c69b7ab2
--- /dev/null
+++ b/test/Analysis/RegionInfo/infinite_loop_2.ll
@@ -0,0 +1,36 @@
+; RUN: opt -regions -analyze < %s 
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @normal_condition() nounwind {
+0:
+	br label %"1"
+1:
+	br i1 1, label %"2", label %"3"
+2:
+	br label %"5"
+5:
+	br i1 1, label %"11", label %"12"
+11:
+        br label %"6"
+12:
+        br label %"6"
+6:
+        br label %"2"
+3:
+	br label %"4"
+4:
+	ret void
+}
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK: [1] 1 => 3
+; STAT: 2 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: 0, 1, 2, 5, 11, 6, 12, 3, 4,
+; BBIT: 1, 2, 5, 11, 6, 12,
+
+; RNIT: 0, 1 => 3, 3, 4,
+; RNIT: 1, 2, 5, 11, 6, 12,
diff --git a/test/Analysis/RegionInfo/infinite_loop_3.ll b/test/Analysis/RegionInfo/infinite_loop_3.ll
new file mode 100644
index 0000000000..74ceafb849
--- /dev/null
+++ b/test/Analysis/RegionInfo/infinite_loop_3.ll
@@ -0,0 +1,52 @@
+; RUN: opt -regions -analyze < %s 
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @normal_condition() nounwind {
+0:
+	br label %"7"
+7:
+	br i1 1, label %"1", label %"8"
+1:
+	br i1 1, label %"2", label %"3"
+2:
+	br label %"5"
+5:
+	br i1 1, label %"11", label %"12"
+11:
+        br label %"6"
+12:
+        br label %"6"
+6:
+        br label %"2"
+8:
+	br label %"9"
+9:
+	br i1 1, label %"13", label %"14"
+13:
+        br label %"10"
+14:
+        br label %"10"
+10:
+        br label %"8"
+3:
+	br label %"4"
+4:
+	ret void
+}
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK-NEXT: [1] 1 => 3
+; CHECK-NEXT: [1] 7 => 1
+; STAT: 3 region - The # of regions
+; STAT: 2 region - The # of simple regions
+
+; BBIT: 0, 7, 1, 2, 5, 11, 6, 12, 3, 4, 8, 9, 13, 10, 14,
+; BBIT: 7, 8, 9, 13, 10, 14,
+; BBIT: 1, 2, 5, 11, 6, 12,
+
+; RNIT: 0, 7 => 1, 1 => 3, 3, 4,
+; RNIT: 7, 8, 9, 13, 10, 14,
+; RNIT: 1, 2, 5, 11, 6, 12,
diff --git a/test/Analysis/RegionInfo/infinite_loop_4.ll b/test/Analysis/RegionInfo/infinite_loop_4.ll
new file mode 100644
index 0000000000..fd56af1d3b
--- /dev/null
+++ b/test/Analysis/RegionInfo/infinite_loop_4.ll
@@ -0,0 +1,48 @@
+; RUN: opt -regions -analyze < %s 
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @normal_condition() nounwind {
+0:
+	br label %"7"
+7:
+	br i1 1, label %"1", label %"8"
+1:
+	br i1 1, label %"2", label %"3"
+2:
+	br label %"5"
+5:
+	br i1 1, label %"11", label %"12"
+11:
+        br label %"6"
+12:
+        br label %"6"
+6:
+	br i1 1, label %"2", label %"10"
+8:
+	br label %"9"
+9:
+	br i1 1, label %"13", label %"14"
+13:
+        br label %"10"
+14:
+        br label %"10"
+10:
+        br label %"8"
+3:
+	br label %"4"
+4:
+	ret void
+}
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK-NEXT: [1] 7 => 3
+; STAT: 2 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: 0, 7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12, 3, 4,
+; BBIT: 7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12,
+
+; RNIT: 0, 7 => 3, 3, 4,
+; RNIT: 7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12,
diff --git a/test/Analysis/RegionInfo/loop_with_condition.ll b/test/Analysis/RegionInfo/loop_with_condition.ll
new file mode 100644
index 0000000000..d1d68982ee
--- /dev/null
+++ b/test/Analysis/RegionInfo/loop_with_condition.ll
@@ -0,0 +1,46 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @normal_condition() nounwind {
+0:
+        br label %"1"
+1:
+	br i1 1, label %"6", label %"2"
+2:
+	br i1 1, label %"3", label %"4"
+3:
+	br label %"5"
+4:
+	br label %"5"
+5:
+        br label %"8"
+8:
+        br i1 1, label %"7", label %"9"
+9:
+        br label %"2"
+7:
+        br label %"6"
+6:
+	ret void
+}
+
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK-NEXT: [1] 1 => 6
+; CHECK-NEXT:   [2] 2 => 7
+; CHECK-NEXT:     [3] 2 => 5
+; STAT: 4 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: 0, 1, 6, 2, 3, 5, 8, 7, 9, 4,
+; BBIT: 1, 2, 3, 5, 8, 7, 9, 4,
+; BBIT: 2, 3, 5, 8, 9, 4,
+; BBIT: 2, 3, 4,
+
+; RNIT: 0, 1 => 6, 6,
+; RNIT: 1, 2 => 7, 7,
+; RNIT: 2 => 5, 5, 8, 9,
+; RNIT: 2, 3, 4,
diff --git a/test/Analysis/RegionInfo/loops_1.ll b/test/Analysis/RegionInfo/loops_1.ll
new file mode 100644
index 0000000000..d4bf3cc501
--- /dev/null
+++ b/test/Analysis/RegionInfo/loops_1.ll
@@ -0,0 +1,40 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define internal fastcc zeroext i8 @loops_1() nounwind {
+entry:
+  br i1 1, label %outer , label %a
+
+a:
+  br label %body
+
+outer:
+  br label %body
+
+body:
+  br i1 1, label %land, label %if
+
+land:
+  br i1 1, label %exit, label %end
+
+exit:
+  br i1 1, label %if, label %end
+
+if:
+  br label %outer
+
+end:
+  ret i8 1
+}
+; CHECK-NOT: =>
+; CHECK: [0] entry => <Function Return>
+; CHECK-NEXT: [1] entry => end
+; STAT: 2 region - The # of regions
+
+; BBIT: entry, outer, body, land, exit, if, end, a,
+; BBIT: entry, outer, body, land, exit, if, a,
+
+; RNIT: entry => end, end,
+; RNIT: entry, outer, body, land, exit, if, a,
diff --git a/test/Analysis/RegionInfo/loops_2.ll b/test/Analysis/RegionInfo/loops_2.ll
new file mode 100644
index 0000000000..07aa7c3110
--- /dev/null
+++ b/test/Analysis/RegionInfo/loops_2.ll
@@ -0,0 +1,49 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @meread_() nounwind {
+entry:
+  br label %bb23
+
+bb23:
+  br label %bb.i
+
+bb.i:                                             ; preds = %bb.i, %bb54
+  br label %pflini_.exit
+
+pflini_.exit:                                     ; preds = %bb.i
+  br label %bb58thread-split
+
+bb58thread-split:                                 ; preds = %bb64, %bb61, %pflini_.exit
+  br label %bb58
+
+bb58:                                             ; preds = %bb60, %bb58thread-split
+  br i1 1, label %bb59, label %bb23
+
+bb59:                                             ; preds = %bb58
+  switch i32 1, label %bb60 [
+    i32 1, label %l98
+  ]
+
+bb60:                                             ; preds = %bb59
+  br i1 1, label %bb61, label %bb58
+
+bb61:                                             ; preds = %bb60
+  br label %bb58thread-split
+
+l98:                                   ; preds = %bb69, %bb59
+  ret void
+}
+; CHECK-NOT: =>
+; CHECK: [0] entry => <Function Return>
+; CHECK: [1] bb23 => l98
+; STAT: 2 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: entry, bb23, bb.i, pflini_.exit, bb58thread-split, bb58, bb59, bb60, bb61, l98,
+; BBIT: bb23, bb.i, pflini_.exit, bb58thread-split, bb58, bb59, bb60, bb61,
+
+; RNIT: entry, bb23 => l98, l98,
+; RNIT: bb23, bb.i, pflini_.exit, bb58thread-split, bb58, bb59, bb60, bb61,
diff --git a/test/Analysis/RegionInfo/mix_1.ll b/test/Analysis/RegionInfo/mix_1.ll
new file mode 100644
index 0000000000..829c157c2c
--- /dev/null
+++ b/test/Analysis/RegionInfo/mix_1.ll
@@ -0,0 +1,69 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @a_linear_impl_fig_1() nounwind {
+0:
+
+	br i1 1, label %"1", label %"15"
+1:
+ 	switch i32 0, label %"2" [ i32 0, label %"3"
+                                  i32 1, label %"7"]
+2:
+	br label %"4"
+3:
+	br label %"5"
+4:
+	br label %"6"
+5:
+	br label %"6"
+6:
+	br label %"7"
+7:
+	br label %"15"
+15:
+	br label %"8"
+8:
+	br label %"16"
+16:
+        br label %"9"
+9:
+	br i1 1, label %"10", label %"11"
+11:
+	br i1 1, label %"13", label %"12"
+13:
+	br label %"14"
+12:
+	br label %"14"
+14:
+	br label %"8"
+10:
+        br label %"17"
+17:
+        br label %"18"
+18:
+        ret void
+}
+
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK-NEXT: [1] 0 => 15
+; CHECK-NEXT:  [2] 1 => 7
+; CHECK-NEXT: [1] 8 => 10
+; CHECK-NEXT:  [2] 11 => 14
+; STAT: 5 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: 0, 1, 2, 4, 6, 7, 15, 8, 16, 9, 10, 17, 18, 11, 13, 14, 12, 3, 5,
+; BBIT: 0, 1, 2, 4, 6, 7, 3, 5,
+; BBIT: 1, 2, 4, 6, 3, 5,
+; BBIT: 8, 16, 9, 11, 13, 14, 12,
+; BBIT: 11, 13, 12,
+
+; RNIT: 0 => 15, 15, 8 => 10, 10, 17, 18,
+; RNIT: 0, 1 => 7, 7,
+; RNIT: 1, 2, 4, 6, 3, 5,
+; RNIT: 8, 16, 9, 11 => 14, 14,
+; RNIT: 11, 13, 12,
diff --git a/test/Analysis/RegionInfo/multiple_exiting_edge.ll b/test/Analysis/RegionInfo/multiple_exiting_edge.ll
new file mode 100644
index 0000000000..7bc0e4607d
--- /dev/null
+++ b/test/Analysis/RegionInfo/multiple_exiting_edge.ll
@@ -0,0 +1,38 @@
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @normal_condition_0() nounwind {
+bb38:                                             ; preds = %bb34, %bb34, %bb37
+  switch i32 undef, label %bb42 [
+    i32 67, label %bb42
+    i32 90, label %bb41
+  ]
+bb41:                                             ; preds = %bb38
+  br label %bb42
+bb42:                                             ; preds = %bb38, %bb38, %bb41
+  ret void
+}
+
+; BBIT: bb38, bb42, bb41,
+; BBIT: bb38, bb41,
+
+; RNIT: bb38 => bb42, bb42,
+; RNIT: bb38, bb41,
+
+define void @normal_condition_1() nounwind {
+bb38:                                             ; preds = %bb34, %bb34, %bb37
+  switch i32 undef, label %bb41 [
+    i32 67, label %bb42
+    i32 90, label %bb42
+  ]
+bb41:                                             ; preds = %bb38
+  br label %bb42
+bb42:                                             ; preds = %bb38, %bb38, %bb41
+  ret void
+}
+
+; BBIT: bb38, bb41, bb42,
+; BBIT: bb38, bb41,
+
+; RNIT: bb38 => bb42, bb42,
+; RNIT: bb38, bb41,
diff --git a/test/Analysis/RegionInfo/nested_loops.ll b/test/Analysis/RegionInfo/nested_loops.ll
new file mode 100644
index 0000000000..9d8c4558f0
--- /dev/null
+++ b/test/Analysis/RegionInfo/nested_loops.ll
@@ -0,0 +1,33 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define internal fastcc zeroext i8 @handle_compress() nounwind {
+entry:
+  br label %outer
+
+outer:
+  br label %body
+
+body:
+  br i1 1, label %exit172, label %end
+
+exit172:
+  br i1 1, label %end, label %outer
+
+end:
+  ret i8 1
+}
+; CHECK-NOT: =>
+; CHECK: [0] entry => <Function Return>
+; CHECK-NEXT: [1] outer => end
+
+; STAT: 2 region - The # of regions
+
+; BBIT: entry, outer, body, exit172, end,
+; BBIT: outer, body, exit172,
+
+; RNIT: entry, outer => end, end,
+; RNIT: outer, body, exit172,
diff --git a/test/Analysis/RegionInfo/next.ll b/test/Analysis/RegionInfo/next.ll
new file mode 100644
index 0000000000..d986387099
--- /dev/null
+++ b/test/Analysis/RegionInfo/next.ll
@@ -0,0 +1,49 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @MAIN__() nounwind {
+entry:
+  br label %__label_002001.outer
+
+__label_002001.outer:                             ; preds = %bb236, %bb92
+  br label %__label_002001
+
+__label_002001:                                   ; preds = %bb229, %__label_002001.outer
+  br i1  1, label %bb93, label %__label_000020
+
+bb93:                                             ; preds = %__label_002001
+  br i1  1, label %__label_000020, label %bb197
+
+bb197:                                            ; preds = %bb193
+  br i1  1, label %bb229, label %bb224
+
+bb224:                                            ; preds = %bb223, %bb227
+  br i1  1, label %bb229, label %bb224
+
+bb229:                                            ; preds = %bb227, %bb223
+  br i1  1, label %__label_002001, label %__label_002001.outer
+
+__label_000020:                                   ; preds = %__label_002001, %bb194
+  ret void
+}
+
+; CHECK-NOT: =>
+; CHECK: [0] entry => <Function Return>
+; CHECK-NEXT:  [1] __label_002001.outer => __label_000020
+; CHECK-NEXT;      [2] bb197 => bb229
+; CHECK-NEXT;            [3] bb224 => bb229
+
+; STAT: 4 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: entry, __label_002001.outer, __label_002001, bb93, __label_000020, bb197, bb229, bb224,
+; BBIT: __label_002001.outer, __label_002001, bb93, bb197, bb229, bb224,
+; BBIT: bb197, bb224,
+; BBIT: bb224,
+
+; RNIT: entry, __label_002001.outer => __label_000020, __label_000020,
+; RNIT: __label_002001.outer, __label_002001, bb93, bb197 => bb229, bb229,
+; RNIT: bb197, bb224 => bb229,
+; RNIT: bb224,
diff --git a/test/Analysis/RegionInfo/paper.ll b/test/Analysis/RegionInfo/paper.ll
new file mode 100644
index 0000000000..00b544bc69
--- /dev/null
+++ b/test/Analysis/RegionInfo/paper.ll
@@ -0,0 +1,55 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @a_linear_impl_fig_1() nounwind {
+0:
+        br label %"1"
+1:
+	br label %"2"
+2:
+	br label %"3"
+3:
+	br i1 1, label %"13", label %"4"
+4:
+	br i1 1, label %"5", label %"1"
+5:
+	br i1 1, label %"8", label %"6"
+6:
+	br i1 1, label %"7", label %"4"
+7:
+	ret void
+8:
+	br i1 1, label %"9", label %"1"
+9:
+	br label %"10"
+10:
+	br i1 1, label %"12", label %"11"
+11:
+	br i1 1, label %"9", label %"8"
+13:
+	br i1 1, label %"2", label %"1"
+12:
+ 	switch i32 0, label %"1" [ i32 0, label %"9"
+                                  i32 1, label %"8"]
+}
+
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK-NEXT: [1] 1 => 7
+; CHECK-NEXT:   [2] 1 => 4
+; CHECK-NEXT:   [2] 8 => 1
+
+; STAT: 4 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: 0, 1, 2, 3, 13, 4, 5, 8, 9, 10, 12, 11, 6, 7,
+; BBIT: 1, 2, 3, 13, 4, 5, 8, 9, 10, 12, 11, 6,
+; BBIT: 1, 2, 3, 13,
+; BBIT: 8, 9, 10, 12, 11,
+
+; RNIT: 0, 1 => 7, 7,
+; RNIT: 1 => 4, 4, 5, 8 => 1, 6,
+; RNIT: 1, 2, 3, 13,
+; RNIT: 8, 9, 10, 12, 11,
diff --git a/test/Analysis/RegionInfo/two_loops_same_header.ll b/test/Analysis/RegionInfo/two_loops_same_header.ll
new file mode 100644
index 0000000000..a97182b81a
--- /dev/null
+++ b/test/Analysis/RegionInfo/two_loops_same_header.ll
@@ -0,0 +1,46 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define internal fastcc zeroext i8 @handle_compress() nounwind {
+entry:
+  br label %outer
+
+outer:
+  br label %body
+
+body:
+  br i1 1, label %else, label %true77
+
+true77:
+  br i1 1, label %then83, label %else
+
+then83:
+  br label %outer
+
+else:
+  br label %else106
+
+else106:
+  br i1 1, label %end, label %outer
+
+end:
+  ret i8 1
+}
+
+; CHECK-NOT: =>
+; CHECK: [0] entry => <Function Return>
+; CHECK-NEXT: [1] outer => end
+; CHECK-NEXT:   [2] outer => else
+
+; STAT: 3 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: entry, outer, body, else, else106, end, true77, then83,
+; BBIT: outer, body, else, else106, true77, then83,
+; BBIT: outer, body, true77, then83,
+
+; RNIT: entry, outer => end, end,
+; RNIT: outer => else, else, else106,
+; RNIT: outer, body, true77, then83,