[Examples] Add IRTransformations directory to examples.

This patch adds a new IRTransformations directory to llvm/examples/. This is
intended to serve as a new home for example transformations/analysis
code used by various tutorials.

If LLVM_BUILD_EXAMPLES is enabled, the ExamplesIRTransforms library is
linked into the opt binary and the example passes become available.

To start off with, it contains the CFG simplifications used in the IR
part of the 'Getting Started With LLVM: Basics' tutorial at the US LLVM
Developers Meeting 2019.

Reviewers: paquette, jfb, meikeb, lhames, kbarton

Reviewed By: paquette

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

7 files changed, 479 insertions, 0 deletions

diff --git a/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg-blockaddress.ll b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg-blockaddress.ll
new file mode 100644
index 00000000000..faf60f3acdb
--- /dev/null
+++ b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg-blockaddress.ll
@@ -0,0 +1,23 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v1 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v2 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v3 -S < %s | FileCheck %s
+
+define i8* @simp1(i32 %x) {
+; CHECK-LABEL: @simp1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 42
+; CHECK-NEXT:    [[ADDR:%.*]] = select i1 [[CMP]], i8* inttoptr (i32 1 to i8*), i8* inttoptr (i32 1 to i8*)
+; CHECK-NEXT:    ret i8* [[ADDR]]
+;
+entry:
+  %cmp = icmp slt i32 %x, 42
+  %addr = select i1 %cmp, i8* blockaddress(@simp1, %bb1), i8* blockaddress(@simp1, %bb2)
+  ret i8* %addr
+
+bb1:
+  ret i8* null
+
+bb2:
+  ret i8* null
+}
diff --git a/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg1.ll b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg1.ll
new file mode 100644
index 00000000000..cb0f82e3757
--- /dev/null
+++ b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg1.ll
@@ -0,0 +1,90 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v1 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v2 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v3 -S < %s | FileCheck %s
+
+define i32 @simp1() {
+; CHECK-LABEL: @simp1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 10
+;
+entry:
+  br i1 true, label %if.then, label %if.else
+
+if.then:
+  ret i32 10
+
+if.else:
+  ret i32 12
+}
+
+define i32 @simp2() {
+; CHECK-LABEL: @simp2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 200
+;
+entry:
+  br i1 false, label %if.then, label %if.else
+
+if.then:
+  ret i32 99
+
+if.else:
+  ret i32 200
+}
+
+declare void @foo(i64)
+
+define i64 @merge_into_predecessor(i64 %a, i64 %b) {
+; CHECK-LABEL: @merge_into_predecessor(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[R:%.*]] = add i64 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    call void @foo(i64 [[R]])
+; CHECK-NEXT:    call void @foo(i64 [[A]])
+; CHECK-NEXT:    ret i64 [[R]]
+;
+entry:
+  br label %bb.next
+
+bb.next:
+  %r = add i64 %a, %b
+  call void @foo(i64 %r)
+  call void @foo(i64 %a)
+  br label %bb.next.next
+
+bb.next.next:
+  ret i64 %r
+}
+
+define i64 @merge_into_predecessor_with_phi(i64 %a, i64 %b, i1 %c) {
+; CHECK-LABEL: @merge_into_predecessor_with_phi(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void @foo(i64 [[B:%.*]])
+; CHECK-NEXT:    [[R:%.*]] = add i64 [[A:%.*]], [[B]]
+; CHECK-NEXT:    call void @foo(i64 [[R]])
+; CHECK-NEXT:    call void @foo(i64 [[A]])
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB_NEXT_NEXT:%.*]], label [[BB_EXIT:%.*]]
+; CHECK:       bb.next.next:
+; CHECK-NEXT:    br label [[BB_EXIT]]
+; CHECK:       bb.exit:
+; CHECK-NEXT:    [[RET:%.*]] = phi i64 [ [[R]], [[ENTRY:%.*]] ], [ 10, [[BB_NEXT_NEXT]] ]
+; CHECK-NEXT:    ret i64 [[RET]]
+;
+entry:
+  call void @foo(i64 %b)
+  br label %bb.next
+
+bb.next:
+  %r = add i64 %a, %b
+  call void @foo(i64 %r)
+  call void @foo(i64 %a)
+  br i1 %c, label %bb.next.next, label %bb.exit
+
+bb.next.next:
+  br label %bb.exit
+
+bb.exit:
+  %ret = phi i64 [ %r, %bb.next], [ 10, %bb.next.next]
+  ret i64 %ret
+
+}
diff --git a/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg2-dead-block-order.ll b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg2-dead-block-order.ll
new file mode 100644
index 00000000000..11b70fa5267
--- /dev/null
+++ b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg2-dead-block-order.ll
@@ -0,0 +1,109 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v1 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v2 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v3 -S < %s | FileCheck %s
+
+define i32 @remove_dead_blocks() {
+; CHECK-LABEL: @remove_dead_blocks(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 1
+; CHECK-NEXT:  }
+;
+entry:
+  ret i32 1
+
+bb.1:
+  ret i32 2
+
+bb.2:
+  ret i32 3
+}
+
+define i32 @simp1() {
+; CHECK-LABEL: @simp1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 1
+; CHECK:       bb.1:
+; CHECK-NEXT:    ret i32 2
+; CHECK-NEXT:  }
+;
+entry:
+  ret i32 1
+
+bb.1:
+  ret i32 2
+
+bb.2:
+  br i1 undef, label %bb.1, label %bb.3
+
+bb.3:
+  ret i32 3
+}
+
+define i32 @remove_dead_block_with_phi() {
+; CHECK-LABEL: @remove_dead_block_with_phi(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[BB_2:%.*]]
+; CHECK:       bb.2:
+; CHECK-NEXT:    ret i32 1
+; CHECK-NEXT:  }
+;
+entry:
+  br label %bb.2
+
+bb.1:
+  br label %bb.2
+
+bb.2:
+  %rv = phi i32 [ 1, %entry ], [ 2, %bb.1 ]
+  ret i32 %rv
+}
+
+define i32 @remove_dead_blocks_remaining_uses(i32 %a) {
+; CHECK-LABEL: @remove_dead_blocks_remaining_uses(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 1
+; CHECK-NEXT:  }
+;
+entry:
+  ret i32 1
+
+bb.2:
+  ret i32 %res
+
+bb.1:
+  %res = add i32 %a, 10
+  br label %bb.2
+}
+
+define i32 @remove_dead_blocks_remaining_uses2(i32 %a, i1 %cond) {
+; CHECK-LABEL: @remove_dead_blocks_remaining_uses2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 1
+; CHECK:       bb.2:
+; CHECK-NEXT:    [[RES2:%.*]] = add i32 undef, 10
+; CHECK-NEXT:    [[RES3:%.*]] = mul i32 [[RES2]], undef
+; CHECK-NEXT:    ret i32 [[RES3]]
+; CHECK:       bb.3:
+; CHECK-NEXT:    ret i32 undef
+; CHECK-NEXT:  }
+;
+entry:
+  ret i32 1
+
+bb.2:
+  %res2 = add i32 %res, 10
+  %res3 = mul i32 %res2, %res
+  ret i32 %res3
+
+bb.3:
+  br label %bb.4
+
+bb.4:
+  ret i32 %res
+
+bb.1:
+  %res = add i32 %a, 10
+  br i1 %cond, label %bb.2, label %bb.3
+  br label %bb.2
+}
diff --git a/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg3-phis.ll b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg3-phis.ll
new file mode 100644
index 00000000000..76db503faeb
--- /dev/null
+++ b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg3-phis.ll
@@ -0,0 +1,70 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v1 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v2 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v3 -S < %s | FileCheck %s
+
+define i32 @phi_cond_branch_eliminated() {
+; CHECK-LABEL: @phi_cond_branch_eliminated(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 20
+;
+entry:
+  br i1 true, label %bb.2, label %bb.3
+
+bb.2:
+  br label %bb.3
+
+bb.3:
+  %ret = phi i32 [ 10, %entry ], [ 20, %bb.2 ]
+  ret i32 %ret
+}
+
+define i32 @phi_removed() {
+; CHECK-LABEL: @phi_removed(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[BB_3:%.*]]
+; CHECK:       bb.3:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  br i1 false, label %bb.2, label %bb.3
+
+bb.2:
+  %pv = phi i32 [ 10, %entry ]
+  br label %bb.3
+
+bb.3:
+  ret i32 0
+}
+
+define i32 @phi_in_dead_region() {
+; CHECK-LABEL: @phi_in_dead_region(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 1
+;
+entry:
+  ret i32 1
+
+bb.1:
+  br i1 true, label %bb.2, label %bb.3
+
+bb.2:
+  br label %bb.3
+
+bb.3:
+  %ret = phi i32 [ 10, %bb.1 ], [ 20, %bb.2 ]
+  ret i32 %ret
+}
+
+define i32 @phi_in_mergable_blocks() {
+; CHECK-LABEL: @phi_in_mergable_blocks(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 10
+;
+entry:
+  br label %bb.1
+
+bb.1:
+  %pv = phi i32 [ 10, %entry ]
+  ret i32 %pv
+}
diff --git a/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg4-multiple-duplicate-cfg-updates.ll b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg4-multiple-duplicate-cfg-updates.ll
new file mode 100644
index 00000000000..82a0e0dac23
--- /dev/null
+++ b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg4-multiple-duplicate-cfg-updates.ll
@@ -0,0 +1,40 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v1 < %s -S -verify-dom-info | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v2 < %s -S -verify-dom-info | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v3 < %s -S -verify-dom-info | FileCheck %s
+
+; Check that we do not crash when we remove edges multiple times in
+; the DomTreeUpdater.
+define void @test() {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    switch i8 undef, label [[IF_THEN_EPIL:%.*]] [
+; CHECK-NEXT:    i8 32, label [[FOR_INC_EPIL:%.*]]
+; CHECK-NEXT:    i8 46, label [[FOR_INC_EPIL]]
+; CHECK-NEXT:    i8 95, label [[FOR_INC_EPIL]]
+; CHECK-NEXT:    i8 45, label [[FOR_INC_EPIL]]
+; CHECK-NEXT:    i8 126, label [[FOR_INC_EPIL]]
+; CHECK-NEXT:    ]
+; CHECK:       if.then.epil:
+; CHECK-NEXT:    unreachable
+; CHECK:       for.inc.epil:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for.body.epil
+
+for.body.epil:                                    ; preds = %entry
+  switch i8 undef, label %if.then.epil [
+  i8 32, label %for.inc.epil
+  i8 46, label %for.inc.epil
+  i8 95, label %for.inc.epil
+  i8 45, label %for.inc.epil
+  i8 126, label %for.inc.epil
+  ]
+
+if.then.epil:                                     ; preds = %for.body.epil
+  unreachable
+
+for.inc.epil:                                     ; preds = %for.body.epil, %for.body.epil, %for.body.epil, %for.body.epil, %for.body.epil
+  ret void
+}
diff --git a/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg5-del-phis-for-dead-block.ll b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg5-del-phis-for-dead-block.ll
new file mode 100644
index 00000000000..b3edd1aa505
--- /dev/null
+++ b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg5-del-phis-for-dead-block.ll
@@ -0,0 +1,122 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v1 < %s -S -verify-dom-info | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v2 < %s -S -verify-dom-info | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v3 < %s -S -verify-dom-info | FileCheck %s
+
+define void @test() {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    switch i32 undef, label [[SW_DEFAULT23:%.*]] [
+; CHECK-NEXT:    i32 129, label [[SW_BB:%.*]]
+; CHECK-NEXT:    i32 215, label [[SW_BB1:%.*]]
+; CHECK-NEXT:    i32 117, label [[SW_BB1]]
+; CHECK-NEXT:    i32 207, label [[SW_BB1]]
+; CHECK-NEXT:    i32 158, label [[SW_BB1]]
+; CHECK-NEXT:    i32 94, label [[SW_BB1]]
+; CHECK-NEXT:    i32 219, label [[SW_BB1]]
+; CHECK-NEXT:    i32 88, label [[SW_BB1]]
+; CHECK-NEXT:    i32 168, label [[SW_BB1]]
+; CHECK-NEXT:    i32 295, label [[SW_BB1]]
+; CHECK-NEXT:    i32 294, label [[SW_BB1]]
+; CHECK-NEXT:    i32 296, label [[SW_BB1]]
+; CHECK-NEXT:    i32 67, label [[SW_BB1]]
+; CHECK-NEXT:    i32 293, label [[SW_BB1]]
+; CHECK-NEXT:    i32 382, label [[SW_BB1]]
+; CHECK-NEXT:    i32 335, label [[SW_BB1]]
+; CHECK-NEXT:    i32 393, label [[SW_BB1]]
+; CHECK-NEXT:    i32 415, label [[SW_BB1]]
+; CHECK-NEXT:    i32 400, label [[SW_BB1]]
+; CHECK-NEXT:    i32 383, label [[SW_BB1]]
+; CHECK-NEXT:    i32 421, label [[SW_BB1]]
+; CHECK-NEXT:    i32 422, label [[SW_BB1]]
+; CHECK-NEXT:    i32 302, label [[SW_BB1]]
+; CHECK-NEXT:    i32 303, label [[SW_BB1]]
+; CHECK-NEXT:    i32 304, label [[SW_BB1]]
+; CHECK-NEXT:    i32 420, label [[SW_BB1]]
+; CHECK-NEXT:    i32 401, label [[SW_EPILOG24:%.*]]
+; CHECK-NEXT:    i32 53, label [[SW_BB12:%.*]]
+; CHECK-NEXT:    i32 44, label [[SW_BB12]]
+; CHECK-NEXT:    ]
+; CHECK:       sw.bb:
+; CHECK-NEXT:    unreachable
+; CHECK:       sw.bb1:
+; CHECK-NEXT:    br label [[SW_EPILOG24]]
+; CHECK:       sw.bb12:
+; CHECK-NEXT:    switch i32 undef, label [[SW_DEFAULT:%.*]] [
+; CHECK-NEXT:    i32 47, label [[SW_BB13:%.*]]
+; CHECK-NEXT:    i32 8, label [[SW_BB13]]
+; CHECK-NEXT:    ]
+; CHECK:       sw.bb13:
+; CHECK-NEXT:    unreachable
+; CHECK:       sw.default:
+; CHECK-NEXT:    unreachable
+; CHECK:       sw.default23:
+; CHECK-NEXT:    unreachable
+; CHECK:       sw.epilog24:
+; CHECK-NEXT:    [[PREVIOUS_3:%.*]] = phi i32 [ undef, [[SW_BB1]] ], [ 401, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    unreachable
+;
+entry:
+  br label %while.body
+
+while.body:                                       ; preds = %entry
+  switch i32 undef, label %sw.default23 [
+  i32 129, label %sw.bb
+  i32 215, label %sw.bb1
+  i32 117, label %sw.bb1
+  i32 207, label %sw.bb1
+  i32 158, label %sw.bb1
+  i32 94, label %sw.bb1
+  i32 219, label %sw.bb1
+  i32 88, label %sw.bb1
+  i32 168, label %sw.bb1
+  i32 295, label %sw.bb1
+  i32 294, label %sw.bb1
+  i32 296, label %sw.bb1
+  i32 67, label %sw.bb1
+  i32 293, label %sw.bb1
+  i32 382, label %sw.bb1
+  i32 335, label %sw.bb1
+  i32 393, label %sw.bb1
+  i32 415, label %sw.bb1
+  i32 400, label %sw.bb1
+  i32 383, label %sw.bb1
+  i32 421, label %sw.bb1
+  i32 422, label %sw.bb1
+  i32 302, label %sw.bb1
+  i32 303, label %sw.bb1
+  i32 304, label %sw.bb1
+  i32 420, label %sw.bb1
+  i32 401, label %sw.epilog24
+  i32 53, label %sw.bb12
+  i32 44, label %sw.bb12
+  ]
+
+sw.bb:                                            ; preds = %while.body
+  unreachable
+
+sw.bb1:                                           ; preds = %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body
+  br i1 false, label %land.lhs.true, label %sw.epilog24
+
+land.lhs.true:                                    ; preds = %sw.bb1
+  br label %sw.epilog24
+
+sw.bb12:                                          ; preds = %while.body, %while.body
+  switch i32 undef, label %sw.default [
+  i32 47, label %sw.bb13
+  i32 8, label %sw.bb13
+  ]
+
+sw.bb13:                                          ; preds = %sw.bb12, %sw.bb12
+  unreachable
+
+sw.default:                                       ; preds = %sw.bb12
+  unreachable
+
+sw.default23:                                     ; preds = %while.body
+  unreachable
+
+sw.epilog24:                                      ; preds = %land.lhs.true, %sw.bb1, %while.body
+  %Previous.3 = phi i32 [ undef, %land.lhs.true ], [ undef, %sw.bb1 ], [ 401, %while.body ]
+  unreachable
+}
diff --git a/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg6-dead-self-loop.ll b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg6-dead-self-loop.ll
new file mode 100644
index 00000000000..f9705a6948b
--- /dev/null
+++ b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg6-dead-self-loop.ll
@@ -0,0 +1,25 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v1 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v2 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v3 -S < %s | FileCheck %s
+
+define i32 @simp1() {
+; CHECK-LABEL: @simp1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 1
+; CHECK:       bb.1:
+; CHECK-NEXT:    br label [[BB_1:%.*]]
+; CHECK:       bb.2:
+; CHECK-NEXT:    [[P:%.*]] = phi i32 [ 0, [[BB_2:%.*]] ]
+; CHECK-NEXT:    br label [[BB_2]]
+;
+entry:
+  ret i32 1
+
+bb.1:
+  br label %bb.1
+
+bb.2:
+  %p = phi i32 [ 0, %bb.2]
+  br label %bb.2
+}