[LoopPeeling] Get rid of Phis that become invariant after N steps

This patch is a generalization of the improvement introduced in rL296898.
Previously, we were able to peel one iteration of a loop to get rid of a Phi that becomes
an invariant on the 2nd iteration. In more general case, if a Phi becomes invariant after
N iterations, we can peel N times and turn it into invariant.
In order to do this, we for every Phi in loop's header we define the Invariant Depth value
which is calculated as follows:

Given %x = phi <Inputs from above the loop>, ..., [%y, %back.edge].

If %y is a loop invariant, then Depth(%x) = 1.
If %y is a Phi from the loop header, Depth(%x) = Depth(%y) + 1.
Otherwise, Depth(%x) is infinite.
Notice that if we peel a loop, all Phis with Depth = 1 become invariants,
and all other Phis with finite depth decrease the depth by 1.
Thus, peeling N first iterations allows us to turn all Phis with Depth <= N
into invariants.

Reviewers: reames, apilipenko, mkuper, skatkov, anna, sanjoy

Reviewed By: sanjoy

Subscribers: llvm-commits

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

llvm-svn: 300446

1 files changed, 146 insertions, 3 deletions

diff --git a/llvm/test/Transforms/LoopUnroll/peel-loop-not-forced.ll b/llvm/test/Transforms/LoopUnroll/peel-loop-not-forced.ll
index c3cbbf1ca0c..8691481acc1 100644
--- a/llvm/test/Transforms/LoopUnroll/peel-loop-not-forced.ll
+++ b/llvm/test/Transforms/LoopUnroll/peel-loop-not-forced.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -S -loop-unroll -unroll-threshold=8 | FileCheck %s
+; RUN: opt < %s -S -loop-unroll -unroll-threshold=30 | FileCheck %s
 
 define i32 @invariant_backedge_1(i32 %a, i32 %b) {
 ; CHECK-LABEL: @invariant_backedge_1
@@ -25,10 +25,112 @@ exit:
   ret i32 %sum
 }
 
-; Peeling should fail due to method size.
 define i32 @invariant_backedge_2(i32 %a, i32 %b) {
+; This loop should be peeled twice because it has a Phi which becomes invariant
+; starting from 3rd iteration.
 ; CHECK-LABEL: @invariant_backedge_2
-; CHECK-NOT:   loop.peel:
+; CHECK:       loop.peel{{.*}}:
+; CHECK:       loop.peel{{.*}}:
+; CHECK:         %i = phi
+; CHECK:         %sum = phi
+; CHECK-NOT:     %half.inv = phi
+; CHECK-NOT:     %plus = phi
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ 0, %entry ], [ %inc, %loop ]
+  %sum = phi i32 [ 0, %entry ], [ %incsum, %loop ]
+  %half.inv = phi i32 [ %a, %entry ], [ %b, %loop ]
+  %plus = phi i32 [ %a, %entry ], [ %half.inv, %loop ]
+
+  %incsum = add i32 %sum, %plus
+  %inc = add i32 %i, 1
+  %cmp = icmp slt i32 %i, 1000
+
+  br i1 %cmp, label %loop, label %exit
+
+exit:
+  ret i32 %sum
+}
+
+define i32 @invariant_backedge_3(i32 %a, i32 %b) {
+; This loop should be peeled thrice because it has a Phi which becomes invariant
+; starting from 4th iteration.
+; CHECK-LABEL: @invariant_backedge_3
+; CHECK:       loop.peel{{.*}}:
+; CHECK:       loop.peel{{.*}}:
+; CHECK:       loop.peel{{.*}}:
+; CHECK:         %i = phi
+; CHECK:         %sum = phi
+; CHECK-NOT:     %half.inv = phi
+; CHECK-NOT:     %half.inv.2 = phi
+; CHECK-NOT:     %plus = phi
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ 0, %entry ], [ %inc, %loop ]
+  %sum = phi i32 [ 0, %entry ], [ %incsum, %loop ]
+  %half.inv = phi i32 [ %a, %entry ], [ %b, %loop ]
+  %half.inv.2 = phi i32 [ %a, %entry ], [ %half.inv, %loop ]
+  %plus = phi i32 [ %a, %entry ], [ %half.inv.2, %loop ]
+
+  %incsum = add i32 %sum, %plus
+  %inc = add i32 %i, 1
+  %cmp = icmp slt i32 %i, 1000
+
+  br i1 %cmp, label %loop, label %exit
+
+exit:
+  ret i32 %sum
+}
+
+define i32 @invariant_backedge_limited_by_size(i32 %a, i32 %b) {
+; This loop should normally be peeled thrice because it has a Phi which becomes
+; invariant starting from 4th iteration, but the size of the loop only allows
+; us to peel twice because we are restricted to 30 instructions in resulting
+; code. Thus, %plus Phi node should stay in loop even despite its backedge
+; input is an invariant.
+; CHECK-LABEL: @invariant_backedge_limited_by_size
+; CHECK:       loop.peel{{.*}}:
+; CHECK:       loop.peel{{.*}}:
+; CHECK:         %i = phi
+; CHECK:         %sum = phi
+; CHECK:         %plus = phi i32 [ %a, {{.*}} ], [ %b, %loop ]
+; CHECK-NOT:     %half.inv = phi
+; CHECK-NOT:     %half.inv.2 = phi
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ 0, %entry ], [ %inc, %loop ]
+  %sum = phi i32 [ 0, %entry ], [ %incsum, %loop ]
+  %half.inv = phi i32 [ %a, %entry ], [ %b, %loop ]
+  %half.inv.2 = phi i32 [ %a, %entry ], [ %half.inv, %loop ]
+  %plus = phi i32 [ %a, %entry ], [ %half.inv.2, %loop ]
+
+  %incsum = add i32 %sum, %plus
+  %inc = add i32 %i, 1
+  %cmp = icmp slt i32 %i, 1000
+
+  %incsum2 = add i32 %incsum, %plus
+  %incsum3 = add i32 %incsum, %plus
+  %incsum4 = add i32 %incsum, %plus
+  %incsum5 = add i32 %incsum, %plus
+  %incsum6 = add i32 %incsum, %plus
+  %incsum7 = add i32 %incsum, %plus
+
+  br i1 %cmp, label %loop, label %exit
+
+exit:
+  ret i32 %sum
+}
+
+; Peeling should fail due to method size.
+define i32 @invariant_backedge_negative(i32 %a, i32 %b) {
+; CHECK-LABEL: @invariant_backedge_negative
+; CHECK-NOT:   loop.peel{{.*}}:
 ; CHECK:       loop:
 ; CHECK:         %i = phi
 ; CHECK:         %sum = phi
@@ -43,6 +145,47 @@ loop:
 
   %incsum = add i32 %sum, %plus
   %incsum2 = add i32 %incsum, %plus
+  %incsum3 = add i32 %incsum, %plus
+  %incsum4 = add i32 %incsum, %plus
+  %incsum5 = add i32 %incsum, %plus
+  %incsum6 = add i32 %incsum, %plus
+  %incsum7 = add i32 %incsum, %plus
+  %incsum8 = add i32 %incsum, %plus
+  %incsum9 = add i32 %incsum, %plus
+  %incsum10 = add i32 %incsum, %plus
+  %incsum11 = add i32 %incsum, %plus
+  %incsum12 = add i32 %incsum, %plus
+  %incsum13 = add i32 %incsum, %plus
+  %incsum14 = add i32 %incsum, %plus
+  %incsum15 = add i32 %incsum, %plus
+  %inc = add i32 %i, 1
+  %cmp = icmp slt i32 %i, 1000
+
+  br i1 %cmp, label %loop, label %exit
+
+exit:
+  ret i32 %sum
+}
+
+define i32 @cycled_phis(i32 %a, i32 %b) {
+; Make sure that we do not crash working with cycled Phis and don't peel it.
+; TODO: Actually this loop should be partially unrolled with factor 2.
+; CHECK-LABEL: @cycled_phis
+; CHECK-NOT:   loop.peel{{.*}}:
+; CHECK:       loop:
+; CHECK:         %i = phi
+; CHECK:         %phi.a = phi
+; CHECK:         %phi.b = phi
+; CHECK:         %sum = phi
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ 0, %entry ], [ %inc, %loop ]
+  %phi.a = phi i32 [ %a, %entry ], [ %phi.b, %loop ]
+  %phi.b = phi i32 [ %b, %entry ], [ %phi.a, %loop ]
+  %sum = phi i32 [ 0, %entry], [ %incsum, %loop ]
+  %incsum = add i32 %sum, %phi.a
   %inc = add i32 %i, 1
   %cmp = icmp slt i32 %i, 1000