1; RUN: opt < %s -loop-interchange -loop-interchange-threshold=-100 -verify-loop-lcssa -S | FileCheck %s
2
3; Test case for PR41725. The induction variables in the latches escape the
4; loops and we must move some PHIs around.
5
6target triple = "powerpc64le-unknown-linux-gnu"
7@a = common dso_local global i64 0, align 4
8@b = common dso_local global i64 0, align 4
9@c = common dso_local global [10 x [10 x i32 ]] zeroinitializer, align 16
10
11
12define void @test_lcssa_indvars1()  {
13; CHECK-LABEL: @test_lcssa_indvars1()
14; CHECK-LABEL: inner.body:
15; CHECK-NEXT:    %iv.inner = phi i64 [ %[[IVNEXT:[0-9]+]], %inner.body.split ], [ 5, %inner.body.preheader ]
16
17; CHECK-LABEL: inner.body.split:
18; CHECK-NEXT:    %0 = phi i64 [ %iv.outer.next, %outer.latch ]
19; CHECK-NEXT:    %[[IVNEXT]] = add nsw i64 %iv.inner, -1
20; CHECK-NEXT:    %[[COND:[0-9]+]] = icmp eq i64 %iv.inner, 0
21; CHECK-NEXT:    br i1 %[[COND]], label %exit, label %inner.body
22
23; CHECK-LABEL: exit:
24; CHECK-NEXT:    %v4.lcssa = phi i64 [ %0, %inner.body.split ]
25; CHECK-NEXT:    %v8.lcssa.lcssa = phi i64 [ %[[IVNEXT]], %inner.body.split ]
26; CHECK-NEXT:    store i64 %v8.lcssa.lcssa, i64* @b, align 4
27; CHECK-NEXT:    store i64 %v4.lcssa, i64* @a, align 4
28
29entry:
30  br label %outer.header
31
32outer.header:                                     ; preds = %outer.latch, %entry
33  %iv.outer = phi i64 [ 0, %entry ], [ %iv.outer.next, %outer.latch ]
34  br label %inner.body
35
36inner.body:                                       ; preds = %inner.body, %outer.header
37  %iv.inner = phi i64 [ 5, %outer.header ], [ %iv.inner.next, %inner.body ]
38  %v7 = getelementptr inbounds [10 x [10 x i32]], [10 x [10 x i32]]* @c, i64 0, i64 %iv.inner, i64 %iv.outer
39  store i32 0, i32* %v7, align 4
40  %iv.inner.next = add nsw i64 %iv.inner, -1
41  %v9 = icmp eq i64 %iv.inner, 0
42  br i1 %v9, label %outer.latch, label %inner.body
43
44outer.latch:                                      ; preds = %inner.body
45  %v8.lcssa = phi i64 [ %iv.inner.next, %inner.body ]
46  %iv.outer.next = add nuw nsw i64 %iv.outer, 1
47  %v5 = icmp ult i64 %iv.outer, 2
48  br i1 %v5, label %outer.header, label %exit
49
50exit:                                             ; preds = %outer.latch
51  %v4.lcssa = phi i64 [ %iv.outer.next, %outer.latch ]
52  %v8.lcssa.lcssa = phi i64 [ %v8.lcssa, %outer.latch ]
53  store i64 %v8.lcssa.lcssa, i64* @b, align 4
54  store i64 %v4.lcssa, i64* @a, align 4
55  ret void
56}
57
58
59define void @test_lcssa_indvars2()  {
60; CHECK-LABEL: @test_lcssa_indvars2()
61; CHECK-LABEL: inner.body:
62; CHECK-NEXT:    %iv.inner = phi i64 [ %[[IVNEXT:[0-9]+]], %inner.body.split ], [ 5, %inner.body.preheader ]
63
64; CHECK-LABEL: inner.body.split:
65; CHECK-NEXT:    %0 = phi i64 [ %iv.outer, %outer.latch ]
66; CHECK-NEXT:    %[[IVNEXT]] = add nsw i64 %iv.inner, -1
67; CHECK-NEXT:    %[[COND:[0-9]+]] = icmp eq i64 %[[IVNEXT]], 0
68; CHECK-NEXT:    br i1 %[[COND]], label %exit, label %inner.body
69
70; CHECK-LABEL: exit:
71; CHECK-NEXT:    %v4.lcssa = phi i64 [ %0, %inner.body.split ]
72; CHECK-NEXT:    %v8.lcssa.lcssa = phi i64 [ %iv.inner, %inner.body.split ]
73; CHECK-NEXT:    store i64 %v8.lcssa.lcssa, i64* @b, align 4
74; CHECK-NEXT:    store i64 %v4.lcssa, i64* @a, align 4
75
76entry:
77  br label %outer.header
78
79outer.header:                                     ; preds = %outer.latch, %entry
80  %iv.outer = phi i64 [ 0, %entry ], [ %iv.outer.next, %outer.latch ]
81  br label %inner.body
82
83inner.body:                                       ; preds = %inner.body, %outer.header
84  %iv.inner = phi i64 [ 5, %outer.header ], [ %iv.inner.next, %inner.body ]
85  %v7 = getelementptr inbounds [10 x [10 x i32]], [10 x [10 x i32]]* @c, i64 0, i64 %iv.inner, i64 %iv.outer
86  store i32 0, i32* %v7, align 4
87  %iv.inner.next = add nsw i64 %iv.inner, -1
88  %v9 = icmp eq i64 %iv.inner.next, 0
89  br i1 %v9, label %outer.latch, label %inner.body
90
91outer.latch:                                      ; preds = %inner.body
92  %v8.lcssa = phi i64 [ %iv.inner, %inner.body ]
93  %iv.outer.next = add nuw nsw i64 %iv.outer, 1
94  %v5 = icmp ult i64 %iv.outer.next, 2
95  br i1 %v5, label %outer.header, label %exit
96
97exit:                                             ; preds = %outer.latch
98  %v4.lcssa = phi i64 [ %iv.outer, %outer.latch ]
99  %v8.lcssa.lcssa = phi i64 [ %v8.lcssa, %outer.latch ]
100  store i64 %v8.lcssa.lcssa, i64* @b, align 4
101  store i64 %v4.lcssa, i64* @a, align 4
102  ret void
103}
104
105define void @test_lcssa_indvars3()  {
106; CHECK-LABEL: @test_lcssa_indvars3()
107; CHECK-LABEL: inner.body:
108; CHECK-NEXT:    %iv.inner = phi i64 [ %[[IVNEXT:[0-9]+]], %inner.body.split ], [ 5, %inner.body.preheader ]
109
110; CHECK-LABEL: inner.body.split:
111; CHECK-NEXT:    %0 = phi i64 [ %iv.outer.next, %outer.latch ]
112; CHECK-NEXT:    %[[IVNEXT]] = add nsw i64 %iv.inner, -1
113; CHECK-NEXT:    %[[COND:[0-9]+]] = icmp eq i64 %iv.inner, 0
114; CHECK-NEXT:    br i1 %[[COND]], label %exit, label %inner.body
115
116; CHECK-LABEL: exit:
117; CHECK-NEXT:    %v4.lcssa = phi i64 [ %0, %inner.body.split ]
118; CHECK-NEXT:    %v8.lcssa.lcssa = phi i64 [ %[[IVNEXT]], %inner.body.split ]
119; CHECK-NEXT:    %v8.lcssa.lcssa.2 = phi i64 [ %[[IVNEXT]], %inner.body.split ]
120; CHECK-NEXT:    %r1 = add i64 %v8.lcssa.lcssa, %v8.lcssa.lcssa.2
121; CHECK-NEXT:    store i64 %r1, i64* @b, align 4
122; CHECK-NEXT:    store i64 %v4.lcssa, i64* @a, align 4
123
124
125entry:
126  br label %outer.header
127
128outer.header:                                     ; preds = %outer.latch, %entry
129  %iv.outer = phi i64 [ 0, %entry ], [ %iv.outer.next, %outer.latch ]
130  br label %inner.body
131
132inner.body:                                       ; preds = %inner.body, %outer.header
133  %iv.inner = phi i64 [ 5, %outer.header ], [ %iv.inner.next, %inner.body ]
134  %v7 = getelementptr inbounds [10 x [10 x i32]], [10 x [10 x i32]]* @c, i64 0, i64 %iv.inner, i64 %iv.outer
135  store i32 0, i32* %v7, align 4
136  %iv.inner.next = add nsw i64 %iv.inner, -1
137  %v9 = icmp eq i64 %iv.inner, 0
138  br i1 %v9, label %outer.latch, label %inner.body
139
140outer.latch:                                      ; preds = %inner.body
141  %v8.lcssa = phi i64 [ %iv.inner.next, %inner.body ]
142  ;%const.lcssa = phi i64 [ 111, %inner.body ]
143  %iv.outer.next = add nuw nsw i64 %iv.outer, 1
144  %v5 = icmp ult i64 %iv.outer, 2
145  br i1 %v5, label %outer.header, label %exit
146
147exit:                                             ; preds = %outer.latch
148  %v4.lcssa = phi i64 [ %iv.outer.next, %outer.latch ]
149  %v8.lcssa.lcssa = phi i64 [ %v8.lcssa, %outer.latch ]
150  %v8.lcssa.lcssa.2 = phi i64 [ %v8.lcssa, %outer.latch ]
151  %r1 = add i64 %v8.lcssa.lcssa, %v8.lcssa.lcssa.2
152  store i64 %r1, i64* @b, align 4
153  store i64 %v4.lcssa, i64* @a, align 4
154  ret void
155}
156
157
158; Make sure we do not crash for loops without reachable exits.
159define void @no_reachable_exits() {
160; Check we interchanged.
161; CHECK-LABEL: @no_reachable_exits()
162; CHECK-NEXT:  bb:
163; CHECK-NEXT:    br label %inner.ph
164; CHECK-LABEL: outer.ph:
165; CHECK-NEXT:    br label %outer.header
166; CHECK-LABEL: inner.ph:
167; CHECK-NEXT:    br label %inner.body
168; CHECK-LABEL: inner.body:
169; CHECK-NEXT:    %tmp31 = phi i32 [ 0, %inner.ph ], [ %[[IVNEXT:[0-9]]], %inner.body.split ]
170; CHECK-NEXT:    br label %outer.ph
171; CHECK-LABEL: inner.body.split:
172; CHECK-NEXT:    %[[IVNEXT]] = add nsw i32 %tmp31, 1
173; CHECK-NEXT:    br i1 false, label %inner.body, label %exit
174
175
176bb:
177  br label %outer.ph
178
179outer.ph:                              ; preds = %bb
180  br label %outer.header
181
182outer.header:                                    ; preds = %outer.ph, %outer.latch
183  %tmp2 = phi i32 [ 0, %outer.ph ], [ %tmp8, %outer.latch ]
184  br i1 undef, label %inner.ph, label %outer.latch
185
186inner.ph:                                        ; preds = %outer.header
187  br label %inner.body
188
189inner.body:                                              ; preds = %inner.ph, %inner.body
190  %tmp31 = phi i32 [ 0, %inner.ph ], [ %tmp6, %inner.body]
191  %tmp5 = load i32*, i32** undef, align 8
192  %tmp6 = add nsw i32 %tmp31, 1
193  br i1 undef, label %inner.body, label %outer.latch
194
195outer.latch:                                              ; preds = %inner.body, %outer.header
196  %tmp8 = add nsw i32 %tmp2, 1
197  br i1 undef, label %outer.header, label %exit
198
199exit:                                              ; preds = %outer.latch
200  unreachable
201}
202