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