Update to LLVM 3.5a.

Change-Id: Ifadecab779f128e62e430c2b4f6ddd84953ed617

4 files changed, 172 insertions, 22 deletions

diff --git a/test/Transforms/LICM/lcssa-ssa-promoter.ll b/test/Transforms/LICM/lcssa-ssa-promoter.ll
new file mode 100644
index 0000000..5df3ef1
--- /dev/null
+++ b/test/Transforms/LICM/lcssa-ssa-promoter.ll
@@ -0,0 +1,76 @@
+; RUN: opt -S -basicaa -licm < %s | FileCheck %s
+;
+; Manually validate LCSSA form is preserved even after SSAUpdater is used to
+; promote things in the loop bodies.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@x = common global i32 0, align 4
+@y = common global i32 0, align 4
+
+define void @PR18688() {
+; CHECK-LABEL: @PR18688(
+
+entry:
+  br i1 undef, label %return, label %outer.preheader
+
+outer.preheader:
+  br label %outer.header
+; CHECK: outer.preheader:
+; CHECK: br label %outer.header
+
+outer.header:
+  store i32 0, i32* @x, align 4
+  br i1 undef, label %outer.latch, label %inner.preheader
+; CHECK: outer.header:
+; CHECK-NEXT: br i1 undef, label %outer.latch, label %inner.preheader
+
+inner.preheader:
+  br label %inner.header
+; CHECK: inner.preheader:
+; CHECK-NEXT: br label %inner.header
+
+inner.header:
+  br i1 undef, label %inner.body.rhs, label %inner.latch
+; CHECK: inner.header:
+; CHECK-NEXT: %[[PHI0:[^,]+]] = phi i32 [ %{{[^,]+}}, %inner.latch ], [ 0, %inner.preheader ]
+; CHECK-NEXT: br i1 undef, label %inner.body.rhs, label %inner.latch
+
+inner.body.rhs:
+  store i32 0, i32* @x, align 4
+  br label %inner.latch
+; CHECK: inner.body.rhs:
+; CHECK-NEXT: br label %inner.latch
+
+inner.latch:
+  %y_val = load i32* @y, align 4
+  %icmp = icmp eq i32 %y_val, 0
+  br i1 %icmp, label %inner.exit, label %inner.header
+; CHECK: inner.latch:
+; CHECK-NEXT: %[[PHI1:[^,]+]] = phi i32 [ 0, %inner.body.rhs ], [ %[[PHI0]], %inner.header ]
+; CHECK-NEXT: br i1 %{{[^,]+}}, label %inner.exit, label %inner.header
+
+inner.exit:
+  br label %outer.latch
+; CHECK: inner.exit:
+; CHECK-NEXT: %[[INNER_LCSSA:[^,]+]] = phi i32 [ %[[PHI1]], %inner.latch ]
+; CHECK-NEXT: br label %outer.latch
+
+outer.latch:
+  br i1 undef, label %outer.exit, label %outer.header
+; CHECK: outer.latch:
+; CHECK-NEXT: %[[PHI2:[^,]+]] = phi i32 [ %[[INNER_LCSSA]], %inner.exit ], [ 0, %outer.header ]
+; CHECK-NEXT: br i1 {{.*}}, label %outer.exit, label %outer.header
+
+outer.exit:
+  br label %return
+; CHECK: outer.exit:
+; CHECK-NEXT: %[[OUTER_LCSSA:[^,]+]] = phi i32 [ %[[PHI2]], %outer.latch ]
+; CHECK-NEXT: store i32 %[[OUTER_LCSSA]]
+; CHECK-NEXT: br label %return
+
+return:
+  ret void
+}
+
diff --git a/test/Transforms/LICM/scalar_promote.ll b/test/Transforms/LICM/scalar_promote.ll
index 92ef155..d7e7c6e 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 b503f96..ccc9186 100644
--- a/test/Transforms/LICM/sinking.ll
+++ b/test/Transforms/LICM/sinking.ll
@@ -53,7 +53,7 @@ Exit:
         
 ; CHECK-LABEL: @test3(
 ; CHECK:     Exit.loopexit:
-; CHECK-NEXT:  %X = add i32 0, 1
+; CHECK-NEXT:  %X.le = add i32 0, 1
 ; CHECK-NEXT:  br label %Exit
 
 }
@@ -76,8 +76,9 @@ Out:		; preds = %Loop
 	ret i32 %tmp.7
 ; CHECK-LABEL: @test4(
 ; CHECK:     Out:
-; CHECK-NEXT:  mul i32 %N, %N_addr.0.pn
-; CHECK-NEXT:  sub i32 %tmp.6, %N
+; 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 i32
 }
 
@@ -100,8 +101,8 @@ Out:		; preds = %Loop
 	ret i32 %tmp.6
 ; CHECK-LABEL: @test5(
 ; CHECK:     Out:
-; CHECK-NEXT:  %tmp.6 = load i32* @X
-; CHECK-NEXT:  ret i32 %tmp.6
+; CHECK-NEXT:  %tmp.6.le = load i32* @X
+; CHECK-NEXT:  ret i32 %tmp.6.le
 }
 
 
@@ -124,9 +125,9 @@ Out:		; preds = %Loop
 	ret i32 %sunk2
 ; CHECK-LABEL: @test6(
 ; CHECK:     Out:
-; CHECK-NEXT:  %dead = getelementptr %Ty* @X2, i64 0, i32 0
-; CHECK-NEXT:  %sunk2 = load i32* %dead
-; CHECK-NEXT:  ret i32 %sunk2
+; CHECK-NEXT:  %dead.le = getelementptr %Ty* @X2, i64 0, i32 0
+; CHECK-NEXT:  %sunk2.le = load i32* %dead.le
+; CHECK-NEXT:  ret i32 %sunk2.le
 }
 
 
@@ -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:  sub i32 %tmp.6, %N
+; 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
 ; 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.le4, %N
 ; CHECK-NEXT:  ret
 }
 
@@ -183,8 +186,9 @@ exit2:		; preds = %Cont
 ; CHECK:     exit1:
 ; CHECK-NEXT:  ret i32 0
 ; CHECK:     exit2:
-; CHECK-NEXT:  %V = add i32 %X, 1
-; CHECK-NEXT:  ret i32 %V
+; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %X
+; CHECK-NEXT:  %V.le = add i32 %[[LCSSAPHI]], 1
+; CHECK-NEXT:  ret i32 %V.le
 }
 
 
@@ -208,7 +212,7 @@ return.i:		; preds = %no_exit.1.i
 
 ; CHECK-LABEL: @test9(
 ; CHECK: loopentry.3.i.preheader.loopexit:
-; CHECK-NEXT:  %inc.1.i = add i32 0, 1
+; CHECK-NEXT:  %inc.1.i.le = add i32 0, 1
 ; CHECK-NEXT:  br label %loopentry.3.i.preheader
 }
 
@@ -229,8 +233,9 @@ Out:		; preds = %Loop
         
 ; CHECK-LABEL: @test10(
 ; CHECK: Out: 
-; CHECK-NEXT:  %tmp.6 = sdiv i32 %N, %N_addr.0.pn
-; CHECK-NEXT:  ret i32 %tmp.6
+; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn
+; CHECK-NEXT:  %tmp.6.le = sdiv i32 %N, %[[LCSSAPHI]]
+; CHECK-NEXT:  ret i32 %tmp.6.le
 }
 
 ; Should delete, not sink, dead instructions.
@@ -246,4 +251,69 @@ Out:
 ; CHECK-NEXT:  ret void
 }
 
+@c = common global [1 x i32] zeroinitializer, align 4
 
+; Test a *many* way nested loop with multiple exit blocks both of which exit
+; multiple loop nests. This exercises LCSSA corner cases.
+define i32 @PR18753(i1* %a, i1* %b, i1* %c, i1* %d) {
+entry:
+  br label %l1.header
+
+l1.header:
+  %iv = phi i64 [ %iv.next, %l1.latch ], [ 0, %entry ]
+  %arrayidx.i = getelementptr inbounds [1 x i32]* @c, i64 0, i64 %iv
+  br label %l2.header
+
+l2.header:
+  %x0 = load i1* %c, align 4
+  br i1 %x0, label %l1.latch, label %l3.preheader
+
+l3.preheader:
+  br label %l3.header
+
+l3.header:
+  %x1 = load i1* %d, align 4
+  br i1 %x1, label %l2.latch, label %l4.preheader
+
+l4.preheader:
+  br label %l4.header
+
+l4.header:
+  %x2 = load i1* %a
+  br i1 %x2, label %l3.latch, label %l4.body
+
+l4.body:
+  call void @f(i32* %arrayidx.i)
+  %x3 = load i1* %b
+  %l = trunc i64 %iv to i32
+  br i1 %x3, label %l4.latch, label %exit
+
+l4.latch:
+  call void @g()
+  %x4 = load i1* %b, align 4
+  br i1 %x4, label %l4.header, label %exit
+
+l3.latch:
+  br label %l3.header
+
+l2.latch:
+  br label %l2.header
+
+l1.latch:
+  %iv.next = add nsw i64 %iv, 1
+  br label %l1.header
+
+exit:
+  %lcssa = phi i32 [ %l, %l4.latch ], [ %l, %l4.body ]
+; CHECK-LABEL: @PR18753(
+; CHECK:       exit:
+; CHECK-NEXT:    %[[LCSSAPHI:.*]] = phi i64 [ %iv, %l4.latch ], [ %iv, %l4.body ]
+; CHECK-NEXT:    %l.le = trunc i64 %[[LCSSAPHI]] to i32
+; CHECK-NEXT:    ret i32 %l.le
+
+  ret i32 %lcssa
+}
+
+declare void @f(i32*)
+
+declare void @g()
diff --git a/test/Transforms/LICM/volatile-alias.ll b/test/Transforms/LICM/volatile-alias.ll
index 886d7f2..df7f0a9 100644
--- a/test/Transforms/LICM/volatile-alias.ll
+++ b/test/Transforms/LICM/volatile-alias.ll
@@ -4,7 +4,7 @@
 ; out of the loop.
 ; CHECK: load i32* %p
 ; CHECK: for.body:
-; CHECK; load volatile i32* %q
+; CHECK: load volatile i32* %q
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"