[IfConversion] Maintain the CFG when predicating/merging blocks in IfConvert*

Summary:
This fixes PR32721 in IfConvertTriangle and possible similar problems in
IfConvertSimple, IfConvertDiamond and IfConvertForkedDiamond.

In PR32721 we had a triangle

   EBB
   | \
   |  |
   | TBB
   |  /
   FBB

where FBB didn't have any successors at all since it ended with an
unconditional return. Then TBB and FBB were be merged into EBB, but EBB
would still keep its successors, and the use of analyzeBranch and
CorrectExtraCFGEdges wouldn't help to remove them since the return
instruction is not analyzable (at least not on ARM).

The edge updating code and branch probability updating code is now pushed
into MergeBlocks() which allows us to share the same update logic between
more callsites. This lets us remove several dependencies on analyzeBranch
and completely eliminate RemoveExtraEdges.

One thing that showed up with this patch was that IfConversion sometimes
left a successor with 0% probability even if there was no branch or
fallthrough to the successor.

One such example from the test case ifcvt_bad_zero_prob_succ.mir. The
indirect branch tBRIND can only jump to bb.1, but without the patch we
got:

  bb.0:
    successors: %bb.1(0x80000000)

  bb.1:
    successors: %bb.1(0x80000000), %bb.2(0x00000000)
    tBRIND %r1, 1, %cpsr
    B %bb.1

  bb.2:

There is no way to jump from bb.1 to bb2, but still there is a 0% edge
from bb.1 to bb.2.

With the patch applied we instead get the expected:

  bb.0:
    successors: %bb.1(0x80000000)

  bb.1:
    successors: %bb.1(0x80000000)
    tBRIND %r1, 1, %cpsr
    B %bb.1

Since bb.2 had no predecessor at all, it was removed.

Several testcases had to be updated due to this since the removed
successor made the "Branch Probability Basic Block Placement" pass
sometimes place blocks in a different order.

Finally added a couple of new test cases:

* PR32721_ifcvt_triangle_unanalyzable.mir:
  Regression test for the original problem dexcribed in PR 32721.

* ifcvt_triangleWoCvtToNextEdge.mir:
  Regression test for problem that caused a revert of my first attempt
  to solve PR 32721.

* ifcvt_simple_bad_zero_prob_succ.mir:
  Test case showing the problem where a wrong successor with 0% probability
  was previously left.

* ifcvt_[diamond|forked_diamond|simple]_unanalyzable.mir
  Very simple test cases for the simple and (forked) diamond cases
  involving unanalyzable branches that can be nice to have as a base if
  wanting to write more complicated tests.

Reviewers: iteratee, MatzeB, grosser, kparzysz

Reviewed By: kparzysz

Subscribers: kbarton, davide, aemerson, nemanjai, javed.absar, kristof.beyls, llvm-commits

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

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

2 files changed, 60 insertions, 41 deletions

diff --git a/test/CodeGen/SystemZ/atomicrmw-minmax-03.ll b/test/CodeGen/SystemZ/atomicrmw-minmax-03.ll
index b53633a5e06..362a4f4ec49 100644
--- a/test/CodeGen/SystemZ/atomicrmw-minmax-03.ll
+++ b/test/CodeGen/SystemZ/atomicrmw-minmax-03.ll
@@ -7,13 +7,15 @@
 define i32 @f1(i32 %dummy, i32 *%src, i32 %b) {
 ; CHECK-LABEL: f1:
 ; CHECK: l %r2, 0(%r3)
-; CHECK: [[LOOP:\.[^:]*]]:
-; CHECK: lr [[NEW:%r[0-9]+]], %r2
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: cs %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
+; CHECK: [[LOOP]]:
+; CHECK: lr [[NEW]], %r2
 ; CHECK: crjle %r2, %r4, [[KEEP:\..*]]
 ; CHECK: lr [[NEW]], %r4
-; CHECK: cs %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw min i32 *%src, i32 %b seq_cst
   ret i32 %res
 }
@@ -22,13 +24,15 @@ define i32 @f1(i32 %dummy, i32 *%src, i32 %b) {
 define i32 @f2(i32 %dummy, i32 *%src, i32 %b) {
 ; CHECK-LABEL: f2:
 ; CHECK: l %r2, 0(%r3)
-; CHECK: [[LOOP:\.[^:]*]]:
-; CHECK: lr [[NEW:%r[0-9]+]], %r2
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: cs %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
+; CHECK: [[LOOP]]:
+; CHECK: lr [[NEW]], %r2
 ; CHECK: crjhe %r2, %r4, [[KEEP:\..*]]
 ; CHECK: lr [[NEW]], %r4
-; CHECK: cs %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw max i32 *%src, i32 %b seq_cst
   ret i32 %res
 }
@@ -37,13 +41,15 @@ define i32 @f2(i32 %dummy, i32 *%src, i32 %b) {
 define i32 @f3(i32 %dummy, i32 *%src, i32 %b) {
 ; CHECK-LABEL: f3:
 ; CHECK: l %r2, 0(%r3)
-; CHECK: [[LOOP:\.[^:]*]]:
-; CHECK: lr [[NEW:%r[0-9]+]], %r2
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: cs %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
+; CHECK: [[LOOP]]:
+; CHECK: lr [[NEW]], %r2
 ; CHECK: clrjle %r2, %r4, [[KEEP:\..*]]
 ; CHECK: lr [[NEW]], %r4
-; CHECK: cs %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw umin i32 *%src, i32 %b seq_cst
   ret i32 %res
 }
@@ -52,13 +58,15 @@ define i32 @f3(i32 %dummy, i32 *%src, i32 %b) {
 define i32 @f4(i32 %dummy, i32 *%src, i32 %b) {
 ; CHECK-LABEL: f4:
 ; CHECK: l %r2, 0(%r3)
-; CHECK: [[LOOP:\.[^:]*]]:
-; CHECK: lr [[NEW:%r[0-9]+]], %r2
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: cs %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
+; CHECK: [[LOOP]]:
+; CHECK: lr [[NEW]], %r2
 ; CHECK: clrjhe %r2, %r4, [[KEEP:\..*]]
 ; CHECK: lr [[NEW]], %r4
-; CHECK: cs %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw umax i32 *%src, i32 %b seq_cst
   ret i32 %res
 }
@@ -159,14 +167,15 @@ define i32 @f12(i32 %dummy, i64 %base, i64 %index, i32 %b) {
 define i32 @f13(i32 %dummy, i32 *%ptr) {
 ; CHECK-LABEL: f13:
 ; CHECK: lhi [[LIMIT:%r[0-9]+]], 42
-; CHECK: l %r2, 0(%r3)
-; CHECK: [[LOOP:\.[^:]*]]:
-; CHECK: lr [[NEW:%r[0-9]+]], %r2
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: cs %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
+; CHECK: [[LOOP]]:
+; CHECK: lr [[NEW]], %r2
 ; CHECK: crjle %r2, [[LIMIT]], [[KEEP:\..*]]
 ; CHECK: lhi [[NEW]], 42
-; CHECK: cs %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw min i32 *%ptr, i32 42 seq_cst
   ret i32 %res
 }
diff --git a/test/CodeGen/SystemZ/atomicrmw-minmax-04.ll b/test/CodeGen/SystemZ/atomicrmw-minmax-04.ll
index 444dc915c0f..5e43edf21bc 100644
--- a/test/CodeGen/SystemZ/atomicrmw-minmax-04.ll
+++ b/test/CodeGen/SystemZ/atomicrmw-minmax-04.ll
@@ -7,13 +7,15 @@
 define i64 @f1(i64 %dummy, i64 *%src, i64 %b) {
 ; CHECK-LABEL: f1:
 ; CHECK: lg %r2, 0(%r3)
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: csg %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
 ; CHECK: [[LOOP:\.[^:]*]]:
 ; CHECK: lgr [[NEW:%r[0-9]+]], %r2
 ; CHECK: cgrjle %r2, %r4, [[KEEP:\..*]]
 ; CHECK: lgr [[NEW]], %r4
-; CHECK: csg %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw min i64 *%src, i64 %b seq_cst
   ret i64 %res
 }
@@ -22,13 +24,15 @@ define i64 @f1(i64 %dummy, i64 *%src, i64 %b) {
 define i64 @f2(i64 %dummy, i64 *%src, i64 %b) {
 ; CHECK-LABEL: f2:
 ; CHECK: lg %r2, 0(%r3)
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: csg %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
 ; CHECK: [[LOOP:\.[^:]*]]:
 ; CHECK: lgr [[NEW:%r[0-9]+]], %r2
 ; CHECK: cgrjhe %r2, %r4, [[KEEP:\..*]]
 ; CHECK: lgr [[NEW]], %r4
-; CHECK: csg %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw max i64 *%src, i64 %b seq_cst
   ret i64 %res
 }
@@ -37,13 +41,15 @@ define i64 @f2(i64 %dummy, i64 *%src, i64 %b) {
 define i64 @f3(i64 %dummy, i64 *%src, i64 %b) {
 ; CHECK-LABEL: f3:
 ; CHECK: lg %r2, 0(%r3)
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: csg %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
 ; CHECK: [[LOOP:\.[^:]*]]:
 ; CHECK: lgr [[NEW:%r[0-9]+]], %r2
 ; CHECK: clgrjle %r2, %r4, [[KEEP:\..*]]
 ; CHECK: lgr [[NEW]], %r4
-; CHECK: csg %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw umin i64 *%src, i64 %b seq_cst
   ret i64 %res
 }
@@ -52,13 +58,15 @@ define i64 @f3(i64 %dummy, i64 *%src, i64 %b) {
 define i64 @f4(i64 %dummy, i64 *%src, i64 %b) {
 ; CHECK-LABEL: f4:
 ; CHECK: lg %r2, 0(%r3)
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: csg %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
 ; CHECK: [[LOOP:\.[^:]*]]:
 ; CHECK: lgr [[NEW:%r[0-9]+]], %r2
 ; CHECK: clgrjhe %r2, %r4, [[KEEP:\..*]]
 ; CHECK: lgr [[NEW]], %r4
-; CHECK: csg %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw umax i64 *%src, i64 %b seq_cst
   ret i64 %res
 }
@@ -127,13 +135,15 @@ define i64 @f10(i64 %dummy, i64 *%ptr) {
 ; CHECK-LABEL: f10:
 ; CHECK: lghi [[LIMIT:%r[0-9]+]], 42
 ; CHECK: lg %r2, 0(%r3)
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: csg %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
 ; CHECK: [[LOOP:\.[^:]*]]:
 ; CHECK: lgr [[NEW:%r[0-9]+]], %r2
 ; CHECK: cgrjle %r2, [[LIMIT]], [[KEEP:\..*]]
 ; CHECK: lghi [[NEW]], 42
-; CHECK: csg %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw min i64 *%ptr, i64 42 seq_cst
   ret i64 %res
 }