[LoopFusion] Move instructions from FC0.Latch to FC1.Latch.

Summary:This PR move instructions from FC0.Latch bottom up to the
beginning of FC1.Latch as long as they are proven safe.

To illustrate why this is beneficial, let's consider the following
example:
Before Fusion:
header1:
  br header2
header2:
  br header2, latch1
latch1:
  br header1, preheader3
preheader3:
  br header3
header3:
  br header4
header4:
  br header4, latch3
latch3:
  br header3, exit3

After Fusion (before this PR):
header1:
  br header2
header2:
  br header2, latch1
latch1:
  br header3
header3:
  br header4
header4:
  br header4, latch3
latch3:
  br header1, exit3

Note that preheader3 is removed during fusion before this PR.
Notice that we cannot fuse loop2 with loop4 as there exists block latch1
in between.
This PR move instructions from latch1 to beginning of latch3, and remove
block latch1. LoopFusion is now able to fuse loop nest recursively.

After Fusion (after this PR):
header1:
  br header2
header2:
  br header3
header3:
  br header4
header4:
  br header2, latch3
latch3:
  br header1, exit3

Reviewer: kbarton, jdoerfert, Meinersbur, dmgreen, fhahn, hfinkel,
bmahjour, etiotto
Reviewed By: kbarton, Meinersbur
Subscribers: hiraditya, llvm-commits
Tag: LLVM
Differential Revision: https://reviews.llvm.org/D71165

1 files changed, 5 insertions, 11 deletions

diff --git a/llvm/test/Transforms/LoopFusion/four_loops.ll b/llvm/test/Transforms/LoopFusion/four_loops.ll
index 771e92813f6..8f3822b8a94 100644
--- a/llvm/test/Transforms/LoopFusion/four_loops.ll
+++ b/llvm/test/Transforms/LoopFusion/four_loops.ll
@@ -9,20 +9,14 @@
 ; CHECK-NEXT: bb:
 ; CHECK-NEXT: br label %[[LOOP1HEADER:bb[0-9]+]]
 ; CHECK: [[LOOP1HEADER]]
-; CHECK: br label %[[LOOP1LATCH:bb[0-9]+]]
-; CHECK: [[LOOP1LATCH]]
-; CHECK: br i1 %{{.*}}, label %[[LOOP2BODY:bb[0-9]+]], label %[[LOOP2BODY]]
+; CHECK: br label %[[LOOP2BODY:bb[0-9]+]]
 ; CHECK: [[LOOP2BODY]]
-; CHECK: br label %[[LOOP2LATCH:bb[0-9]+]]
-; CHECK: [[LOOP2LATCH]]
-; CHECK: br i1 %{{.*}}, label %[[LOOP3BODY:bb[0-9]+]], label %[[LOOP3BODY]]
+; CHECK: br label %[[LOOP3BODY:bb[0-9]+]]
 ; CHECK: [[LOOP3BODY]]
-; CHECK: br label %[[LOOP3LATCH:bb[0-9]+]]
-; CHECK: [[LOOP3LATCH]]
-; CHECK: br i1 %{{.*}}, label %[[LOOP4BODY:bb[0-9]+]], label %[[LOOP4BODY]]
+; CHECK: br label %[[LOOP4BODY:bb[0-9]+]]
 ; CHECK: [[LOOP4BODY]]
-; CHECK: br label %[[LOOP4LATCH:bb[0-9]+]]
-; CHECK: [[LOOP4LATCH]]
+; CHECK: br label %[[LOOP1LATCH:bb[0-9]+]]
+; CHECK: [[LOOP1LATCH]]
 ; CHECK: br i1 %{{.*}}, label %[[LOOP1HEADER]], label %[[LOOPEXIT:bb[0-9]+]]
 ; CHECK: ret void
 define void @dep_free() {