[LPM] Make LCSSA a utility with a FunctionPass that applies it to all

the loops in a function, and teach LICM to work in the presance of
LCSSA.

Previously, LCSSA was a loop pass. That made passes requiring it also be
loop passes and unable to depend on function analysis passes easily. It
also caused outer loops to have a different "canonical" form from inner
loops during analysis. Instead, we go into LCSSA form and preserve it
through the loop pass manager run.

Note that this has the same problem as LoopSimplify that prevents
enabling its verification -- loop passes which run at the end of the loop
pass manager and don't preserve these are valid, but the subsequent loop
pass runs of outer loops that do preserve this pass trigger too much
verification and fail because the inner loop no longer verifies.

The other problem this exposed is that LICM was completely unable to
handle LCSSA form. It didn't preserve it and it actually would give up
on moving instructions in many cases when they were used by an LCSSA phi
node. I've taught LICM to support detecting LCSSA-form PHI nodes and to
hoist and sink around them. This may actually let LICM fire
significantly more because we put everything into LCSSA form to rotate
the loop before running LICM. =/ Now LICM should handle that fine and
preserve it correctly. The down side is that LICM has to require LCSSA
in order to preserve it. This is just a fact of life for LCSSA. It's
entirely possible we should completely remove LCSSA from the optimizer.

The test updates are essentially accomodating LCSSA phi nodes in the
output of LICM, and the fact that we now completely sink every
instruction in ashr-crash below the loop bodies prior to unrolling.

With this change, LCSSA is computed only three times in the pass
pipeline. One of them could be removed (and potentially a SCEV run and
a separate LoopPassManager entirely!) if we had a LoopPass variant of
InstCombine that ran InstCombine on the loop body but refused to combine
away LCSSA PHI nodes. Currently, this also prevents loop unrolling from
being in the same loop pass manager is rotate, LICM, and unswitch.

There is one thing that I *really* don't like -- preserving LCSSA in
LICM is quite expensive. We end up having to re-run LCSSA twice for some
loops after LICM runs because LICM can undo LCSSA both in the current
loop and the parent loop. I don't really see good solutions to this
other than to completely move away from LCSSA and using tools like
SSAUpdater instead.

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

3 files changed, 23 insertions, 14 deletions

diff --git a/test/Transforms/LICM/scalar_promote.ll b/test/Transforms/LICM/scalar_promote.ll
index 92ef15581c..d7e7c6e9a3 100644
--- a/test/Transforms/LICM/scalar_promote.ll
+++ b/test/Transforms/LICM/scalar_promote.ll
@@ -24,7 +24,8 @@ Loop:   ; preds = %Loop, %0
 Out:
   ret void
 ; CHECK: Out:
-; CHECK-NEXT:   store i32 %x2, i32* @X
+; CHECK-NEXT:   %[[LCSSAPHI:.*]] = phi i32 [ %x2
+; CHECK-NEXT:   store i32 %[[LCSSAPHI]], i32* @X
 ; CHECK-NEXT:   ret void
 
 }
@@ -48,7 +49,8 @@ Loop:   ; preds = %Loop, %0
 Exit:   ; preds = %Loop
   ret void
 ; CHECK: Exit:
-; CHECK-NEXT:   store i32 %V, i32* getelementptr inbounds (i32* @X, i64 1)
+; CHECK-NEXT:   %[[LCSSAPHI:.*]] = phi i32 [ %V
+; CHECK-NEXT:   store i32 %[[LCSSAPHI]], i32* getelementptr inbounds (i32* @X, i64 1)
 ; CHECK-NEXT:   ret void
 }
 
@@ -142,7 +144,8 @@ Loop:   ; preds = %Loop, %0
 Out:
   ret void
 ; CHECK: Out:
-; CHECK-NEXT:   store i32 %x2, i32* @X
+; CHECK-NEXT:   %[[LCSSAPHI:.*]] = phi i32 [ %x2
+; CHECK-NEXT:   store i32 %[[LCSSAPHI]], i32* @X
 ; CHECK-NEXT:   ret void
 
 }
@@ -178,7 +181,8 @@ for.end:                                          ; preds = %for.cond.for.end_cr
 ; CHECK: for.body.lr.ph:
 ; CHECK-NEXT:  %gi.promoted = load i32* %gi, align 4, !tbaa !0
 ; CHECK: for.cond.for.end_crit_edge:
-; CHECK-NEXT:  store i32 %inc, i32* %gi, align 4, !tbaa !0
+; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %inc
+; CHECK-NEXT:  store i32 %[[LCSSAPHI]], i32* %gi, align 4, !tbaa !0
 }
 
 !0 = metadata !{metadata !4, metadata !4, i64 0}
diff --git a/test/Transforms/LICM/sinking.ll b/test/Transforms/LICM/sinking.ll
index b503f96e42..02d5b84154 100644
--- a/test/Transforms/LICM/sinking.ll
+++ b/test/Transforms/LICM/sinking.ll
@@ -76,7 +76,8 @@ Out:		; preds = %Loop
 	ret i32 %tmp.7
 ; CHECK-LABEL: @test4(
 ; CHECK:     Out:
-; CHECK-NEXT:  mul i32 %N, %N_addr.0.pn
+; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn
+; CHECK-NEXT:  mul i32 %N, %[[LCSSAPHI]]
 ; CHECK-NEXT:  sub i32 %tmp.6, %N
 ; CHECK-NEXT:  ret i32
 }
@@ -152,12 +153,14 @@ Out2:		; preds = %ContLoop
 	ret i32 %tmp.7
 ; CHECK-LABEL: @test7(
 ; CHECK:     Out1:
-; CHECK-NEXT:  mul i32 %N, %N_addr.0.pn
+; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn
+; CHECK-NEXT:  mul i32 %N, %[[LCSSAPHI]]
 ; CHECK-NEXT:  sub i32 %tmp.6, %N
 ; CHECK-NEXT:  ret
 ; CHECK:     Out2:
-; CHECK-NEXT:  mul i32 %N, %N_addr.0.pn
-; CHECK-NEXT:  sub i32 %tmp.6
+; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn
+; CHECK-NEXT:  mul i32 %N, %[[LCSSAPHI]]
+; CHECK-NEXT:  sub i32 %tmp.6.le, %N
 ; CHECK-NEXT:  ret
 }
 
@@ -183,7 +186,8 @@ exit2:		; preds = %Cont
 ; CHECK:     exit1:
 ; CHECK-NEXT:  ret i32 0
 ; CHECK:     exit2:
-; CHECK-NEXT:  %V = add i32 %X, 1
+; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %X
+; CHECK-NEXT:  %V = add i32 %[[LCSSAPHI]], 1
 ; CHECK-NEXT:  ret i32 %V
 }
 
@@ -229,7 +233,8 @@ Out:		; preds = %Loop
         
 ; CHECK-LABEL: @test10(
 ; CHECK: Out: 
-; CHECK-NEXT:  %tmp.6 = sdiv i32 %N, %N_addr.0.pn
+; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn
+; CHECK-NEXT:  %tmp.6 = sdiv i32 %N, %[[LCSSAPHI]]
 ; CHECK-NEXT:  ret i32 %tmp.6
 }
 
diff --git a/test/Transforms/LoopSimplify/ashr-crash.ll b/test/Transforms/LoopSimplify/ashr-crash.ll
index f736eefc9b..69d1ca69a4 100644
--- a/test/Transforms/LoopSimplify/ashr-crash.ll
+++ b/test/Transforms/LoopSimplify/ashr-crash.ll
@@ -23,15 +23,15 @@ target triple = "x86_64-apple-macosx"
 @b = common global i32 0, align 4
 
 ; Check that the def-use chain that leads to the bad SCEV is still
-; there, and part of it is hoisted to the entry block.
+; there.
 ;
 ; CHECK-LABEL: @foo
 ; CHECK-LABEL: entry:
-; CHECK: %cmp4
 ; CHECK-LABEL: for.cond1.preheader:
 ; CHECK-LABEL: for.body3:
-; CHECK: %1 = zext i1 %cmp4 to i32
-; CHECK: %xor = xor i32 %1, 1
+; CHECK: %cmp4
+; CHECK: %conv = zext i1 %cmp4 to i32
+; CHECK: %xor = xor i32 %conv6, 1
 define void @foo() {
 entry:
   br label %for.cond