1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt < %s -passes=loop-interchange -cache-line-size=64 -verify-dom-info -verify-loop-info -verify-scev -verify-loop-lcssa -S | FileCheck %s
3
4@b = common dso_local local_unnamed_addr global [200 x [200 x i32]] zeroinitializer, align 4
5@a = common dso_local local_unnamed_addr global i32 0, align 4
6
7;; int a, c, d, e;
8;; int b[200][200];
9;; void fn1() {
10;;   for (c = 0; c < 100; c++) {
11;;     for (d = 5, e = 5; d > 0, e > 0; d--, e--)
12;;       a |= b[d][c + 9];
13;;   }
14;; }
15;
16; There are multiple inner loop indvars and only one
17; of them is used in the loop exit condition at the
18; inner loop latch.
19;
20define void @test1() {
21; CHECK-LABEL: @test1(
22; CHECK-NEXT:  entry:
23; CHECK-NEXT:    [[A:%.*]] = load i32, ptr @a, align 4
24; CHECK-NEXT:    br label [[FOR_BODY3_PREHEADER:%.*]]
25; CHECK:       for.body.preheader:
26; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
27; CHECK:       for.body:
28; CHECK-NEXT:    [[INDVARS_OUTER:%.*]] = phi i64 [ [[INDVARS_OUTER_NEXT:%.*]], [[FOR_INC7:%.*]] ], [ 0, [[FOR_BODY_PREHEADER:%.*]] ]
29; CHECK-NEXT:    [[OR_REDUCTION_INNER:%.*]] = phi i32 [ [[OR:%.*]], [[FOR_INC7]] ], [ [[OR_REDUCTION_OUTER:%.*]], [[FOR_BODY_PREHEADER]] ]
30; CHECK-NEXT:    [[INDEX:%.*]] = add nsw i64 [[INDVARS_OUTER]], 9
31; CHECK-NEXT:    br label [[FOR_BODY3_SPLIT1:%.*]]
32; CHECK:       for.body3.preheader:
33; CHECK-NEXT:    br label [[FOR_BODY3:%.*]]
34; CHECK:       for.body3:
35; CHECK-NEXT:    [[INDVAR0:%.*]] = phi i64 [ [[TMP0:%.*]], [[FOR_BODY3_SPLIT:%.*]] ], [ 5, [[FOR_BODY3_PREHEADER]] ]
36; CHECK-NEXT:    [[INDVAR1:%.*]] = phi i32 [ [[TMP1:%.*]], [[FOR_BODY3_SPLIT]] ], [ 5, [[FOR_BODY3_PREHEADER]] ]
37; CHECK-NEXT:    [[OR_REDUCTION_OUTER]] = phi i32 [ [[OR_LCSSA:%.*]], [[FOR_BODY3_SPLIT]] ], [ [[A]], [[FOR_BODY3_PREHEADER]] ]
38; CHECK-NEXT:    br label [[FOR_BODY_PREHEADER]]
39; CHECK:       for.body3.split1:
40; CHECK-NEXT:    [[ARRAYIDX5:%.*]] = getelementptr inbounds [200 x [200 x i32]], ptr @b, i64 0, i64 [[INDVAR0]], i64 [[INDEX]]
41; CHECK-NEXT:    [[LOAD_VAL:%.*]] = load i32, ptr [[ARRAYIDX5]], align 4
42; CHECK-NEXT:    [[OR]] = or i32 [[OR_REDUCTION_INNER]], [[LOAD_VAL]]
43; CHECK-NEXT:    [[INDVAR0_NEXT:%.*]] = add nsw i64 [[INDVAR0]], -1
44; CHECK-NEXT:    [[INDVAR1_NEXT:%.*]] = add nsw i32 [[INDVAR1]], -1
45; CHECK-NEXT:    [[TOBOOL2:%.*]] = icmp eq i32 [[INDVAR1_NEXT]], 0
46; CHECK-NEXT:    br label [[FOR_INC7]]
47; CHECK:       for.body3.split:
48; CHECK-NEXT:    [[OR_LCSSA]] = phi i32 [ [[OR]], [[FOR_INC7]] ]
49; CHECK-NEXT:    [[TMP0]] = add nsw i64 [[INDVAR0]], -1
50; CHECK-NEXT:    [[TMP1]] = add nsw i32 [[INDVAR1]], -1
51; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 0
52; CHECK-NEXT:    br i1 [[TMP2]], label [[FOR_COND_FOR_END8_CRIT_EDGE:%.*]], label [[FOR_BODY3]]
53; CHECK:       for.inc7:
54; CHECK-NEXT:    [[INDVARS_OUTER_NEXT]] = add nsw i64 [[INDVARS_OUTER]], 1
55; CHECK-NEXT:    [[INDVARS_OUTER_NEXT_TRUNC:%.*]] = trunc i64 [[INDVARS_OUTER_NEXT]] to i32
56; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[INDVARS_OUTER_NEXT_TRUNC]], 100
57; CHECK-NEXT:    br i1 [[TOBOOL]], label [[FOR_BODY3_SPLIT]], label [[FOR_BODY]]
58; CHECK:       for.cond.for.end8_crit_edge:
59; CHECK-NEXT:    [[OR_LCSSA_LCSSA:%.*]] = phi i32 [ [[OR_LCSSA]], [[FOR_BODY3_SPLIT]] ]
60; CHECK-NEXT:    store i32 [[OR_LCSSA_LCSSA]], ptr @a, align 4
61; CHECK-NEXT:    br label [[FOR_END8:%.*]]
62; CHECK:       for.end8:
63; CHECK-NEXT:    ret void
64;
65
66entry:
67  %a = load i32, ptr @a
68  br label %for.body
69
70for.body:                                         ; preds = %for.body.lr.ph, %for.inc7
71  %indvars.outer = phi i64 [ 0, %entry ], [ %indvars.outer.next, %for.inc7 ]
72  %or.reduction.outer = phi i32 [ %a, %entry ], [ %or.lcssa, %for.inc7 ]
73  %index = add nsw i64 %indvars.outer, 9
74  br label %for.body3
75
76for.body3:                                        ; preds = %for.body, %for.body3
77  %or.reduction.inner = phi i32 [ %or.reduction.outer, %for.body ], [ %or, %for.body3 ]
78  %indvar0 = phi i64 [ 5, %for.body ], [ %indvar0.next, %for.body3 ]
79  %indvar1 = phi i32 [ 5, %for.body ], [ %indvar1.next, %for.body3 ]
80  %arrayidx5 = getelementptr inbounds [200 x [200 x i32]], ptr @b, i64 0, i64 %indvar0, i64 %index
81  %load.val = load i32, ptr %arrayidx5, align 4
82  %or = or i32 %or.reduction.inner, %load.val
83  %indvar0.next = add nsw i64 %indvar0, -1
84  %indvar1.next = add nsw i32 %indvar1, -1
85  %tobool2 = icmp eq i32 %indvar1.next, 0
86  br i1 %tobool2, label %for.inc7, label %for.body3
87
88for.inc7:                                         ; preds = %for.body3
89  %or.lcssa = phi i32 [ %or, %for.body3 ]
90  %indvars.outer.next = add nsw i64 %indvars.outer, 1
91  %indvars.outer.next.trunc = trunc i64 %indvars.outer.next to i32
92  %tobool = icmp eq i32 %indvars.outer.next.trunc, 100
93  br i1 %tobool, label %for.cond.for.end8_crit_edge, label %for.body
94
95for.cond.for.end8_crit_edge:                      ; preds = %for.inc7
96  %or.lcssa.lcssa = phi i32 [ %or.lcssa, %for.inc7 ]
97  store i32 %or.lcssa.lcssa, ptr @a
98  br label %for.end8
99
100for.end8:                                         ; preds = %for.cond.for.end8_crit_edge, %entry
101  ret void
102}
103
104;; int a, c, d, e;
105;; int b[200][200];
106;; void fn1() {
107;;   for (c = 0 ; c < 100; c++) {
108;;     for (d = 5, e = 6; d + e > 0; d--, e = e - 2)
109;;       a |= b[d][c + 9];
110;;   }
111;; }
112;
113; All inner loop indvars are used in the inner latch.
114;
115define void @test2() {
116; CHECK-LABEL: @test2(
117; CHECK-NEXT:  entry:
118; CHECK-NEXT:    [[A:%.*]] = load i32, ptr @a, align 4
119; CHECK-NEXT:    br label [[FOR_BODY3_PREHEADER:%.*]]
120; CHECK:       for.body.preheader:
121; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
122; CHECK:       for.body:
123; CHECK-NEXT:    [[INDVARS_OUTER:%.*]] = phi i64 [ [[INDVARS_OUTER_NEXT:%.*]], [[FOR_INC7:%.*]] ], [ 0, [[FOR_BODY_PREHEADER:%.*]] ]
124; CHECK-NEXT:    [[OR_REDUCTION_INNER:%.*]] = phi i32 [ [[OR:%.*]], [[FOR_INC7]] ], [ [[OR_REDUCTION_OUTER:%.*]], [[FOR_BODY_PREHEADER]] ]
125; CHECK-NEXT:    [[INDEX:%.*]] = add nsw i64 [[INDVARS_OUTER]], 9
126; CHECK-NEXT:    br label [[FOR_BODY3_SPLIT1:%.*]]
127; CHECK:       for.body3.preheader:
128; CHECK-NEXT:    br label [[FOR_BODY3:%.*]]
129; CHECK:       for.body3:
130; CHECK-NEXT:    [[INDVAR0:%.*]] = phi i64 [ [[TMP2:%.*]], [[FOR_BODY3_SPLIT:%.*]] ], [ 5, [[FOR_BODY3_PREHEADER]] ]
131; CHECK-NEXT:    [[INDVAR1:%.*]] = phi i32 [ [[TMP0:%.*]], [[FOR_BODY3_SPLIT]] ], [ 6, [[FOR_BODY3_PREHEADER]] ]
132; CHECK-NEXT:    [[OR_REDUCTION_OUTER]] = phi i32 [ [[OR_LCSSA:%.*]], [[FOR_BODY3_SPLIT]] ], [ [[A]], [[FOR_BODY3_PREHEADER]] ]
133; CHECK-NEXT:    br label [[FOR_BODY_PREHEADER]]
134; CHECK:       for.body3.split1:
135; CHECK-NEXT:    [[ARRAYIDX5:%.*]] = getelementptr inbounds [200 x [200 x i32]], ptr @b, i64 0, i64 [[INDVAR0]], i64 [[INDEX]]
136; CHECK-NEXT:    [[LOAD_VAL:%.*]] = load i32, ptr [[ARRAYIDX5]], align 4
137; CHECK-NEXT:    [[OR]] = or i32 [[OR_REDUCTION_INNER]], [[LOAD_VAL]]
138; CHECK-NEXT:    [[INDVAR0_NEXT:%.*]] = add nsw i64 [[INDVAR0]], -1
139; CHECK-NEXT:    [[INDVAR1_NEXT:%.*]] = add nsw i32 [[INDVAR1]], -2
140; CHECK-NEXT:    [[INDVAR1_NEXT_EXT:%.*]] = sext i32 [[INDVAR1_NEXT]] to i64
141; CHECK-NEXT:    [[INDVARS_ADD:%.*]] = add nsw i64 [[INDVAR0_NEXT]], [[INDVAR1_NEXT_EXT]]
142; CHECK-NEXT:    [[TOBOOL2:%.*]] = icmp sle i64 [[INDVARS_ADD]], 0
143; CHECK-NEXT:    br label [[FOR_INC7]]
144; CHECK:       for.body3.split:
145; CHECK-NEXT:    [[OR_LCSSA]] = phi i32 [ [[OR]], [[FOR_INC7]] ]
146; CHECK-NEXT:    [[TMP0]] = add nsw i32 [[INDVAR1]], -2
147; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[TMP0]] to i64
148; CHECK-NEXT:    [[TMP2]] = add nsw i64 [[INDVAR0]], -1
149; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i64 [[TMP2]], [[TMP1]]
150; CHECK-NEXT:    [[TMP4:%.*]] = icmp sle i64 [[TMP3]], 0
151; CHECK-NEXT:    br i1 [[TMP4]], label [[FOR_COND_FOR_END8_CRIT_EDGE:%.*]], label [[FOR_BODY3]]
152; CHECK:       for.inc7:
153; CHECK-NEXT:    [[INDVARS_OUTER_NEXT]] = add nsw i64 [[INDVARS_OUTER]], 1
154; CHECK-NEXT:    [[INDVARS_OUTER_NEXT_TRUNC:%.*]] = trunc i64 [[INDVARS_OUTER_NEXT]] to i32
155; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[INDVARS_OUTER_NEXT_TRUNC]], 100
156; CHECK-NEXT:    br i1 [[TOBOOL]], label [[FOR_BODY3_SPLIT]], label [[FOR_BODY]]
157; CHECK:       for.cond.for.end8_crit_edge:
158; CHECK-NEXT:    [[OR_LCSSA_LCSSA:%.*]] = phi i32 [ [[OR_LCSSA]], [[FOR_BODY3_SPLIT]] ]
159; CHECK-NEXT:    store i32 [[OR_LCSSA_LCSSA]], ptr @a, align 4
160; CHECK-NEXT:    br label [[FOR_END8:%.*]]
161; CHECK:       for.end8:
162; CHECK-NEXT:    ret void
163;
164entry:
165  %a = load i32, ptr @a
166  br label %for.body
167
168for.body:                                         ; preds = %for.body.lr.ph, %for.inc7
169  %indvars.outer = phi i64 [ 0, %entry ], [ %indvars.outer.next, %for.inc7 ]
170  %or.reduction.outer = phi i32 [ %a, %entry ], [ %or.lcssa, %for.inc7 ]
171  %index = add nsw i64 %indvars.outer, 9
172  br label %for.body3
173
174for.body3:                                        ; preds = %for.body, %for.body3
175  %or.reduction.inner = phi i32 [ %or.reduction.outer, %for.body ], [ %or, %for.body3 ]
176  %indvar0 = phi i64 [ 5, %for.body ], [ %indvar0.next, %for.body3 ]
177  %indvar1 = phi i32 [ 6, %for.body ], [ %indvar1.next, %for.body3 ]
178  %arrayidx5 = getelementptr inbounds [200 x [200 x i32]], ptr @b, i64 0, i64 %indvar0, i64 %index
179  %load.val = load i32, ptr %arrayidx5, align 4
180  %or = or i32 %or.reduction.inner, %load.val
181  %indvar0.next = add nsw i64 %indvar0, -1
182  %indvar1.next = add nsw i32 %indvar1, -2
183  %indvar1.next.ext = sext i32 %indvar1.next to i64
184  %indvars.add = add nsw i64 %indvar0.next, %indvar1.next.ext
185  %tobool2 = icmp sle i64 %indvars.add, 0
186  br i1 %tobool2, label %for.inc7, label %for.body3
187
188for.inc7:                                         ; preds = %for.body3
189  %or.lcssa = phi i32 [ %or, %for.body3 ]
190  %indvars.outer.next = add nsw i64 %indvars.outer, 1
191  %indvars.outer.next.trunc = trunc i64 %indvars.outer.next to i32
192  %tobool = icmp eq i32 %indvars.outer.next.trunc, 100
193  br i1 %tobool, label %for.cond.for.end8_crit_edge, label %for.body
194
195for.cond.for.end8_crit_edge:                      ; preds = %for.inc7
196  %or.lcssa.lcssa = phi i32 [ %or.lcssa, %for.inc7 ]
197  store i32 %or.lcssa.lcssa, ptr @a
198  br label %for.end8
199
200for.end8:                                         ; preds = %for.cond.for.end8_crit_edge, %entry
201  ret void
202}
203
204;; int a, c, d, e;
205;; int b[200][200];
206;; void fn1() {
207;;   for (c = 0 ; c < 100; c++) {
208;;     d = 5;
209;;     e = 49;
210;;     for (; d != e; d++, e--)
211;;       a |= b[d][c + 9];
212;;   }
213;; }
214;
215; Two inner loop indvars are involved in the inner loop exit
216; condition as LHS and RHS.
217define void @test3() {
218; CHECK-LABEL: @test3(
219; CHECK-NEXT:  entry:
220; CHECK-NEXT:    [[A:%.*]] = load i32, ptr @a, align 4
221; CHECK-NEXT:    br label [[FOR_BODY3_PREHEADER:%.*]]
222; CHECK:       for.body.preheader:
223; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
224; CHECK:       for.body:
225; CHECK-NEXT:    [[INDVARS_OUTER:%.*]] = phi i64 [ [[INDVARS_OUTER_NEXT:%.*]], [[FOR_INC7:%.*]] ], [ 0, [[FOR_BODY_PREHEADER:%.*]] ]
226; CHECK-NEXT:    [[OR_REDUCTION_INNER:%.*]] = phi i32 [ [[OR:%.*]], [[FOR_INC7]] ], [ [[OR_REDUCTION_OUTER:%.*]], [[FOR_BODY_PREHEADER]] ]
227; CHECK-NEXT:    [[INDEX:%.*]] = add nsw i64 [[INDVARS_OUTER]], 9
228; CHECK-NEXT:    br label [[FOR_BODY3_SPLIT1:%.*]]
229; CHECK:       for.body3.preheader:
230; CHECK-NEXT:    br label [[FOR_BODY3:%.*]]
231; CHECK:       for.body3:
232; CHECK-NEXT:    [[INDVAR0:%.*]] = phi i32 [ [[TMP1:%.*]], [[FOR_BODY3_SPLIT:%.*]] ], [ 5, [[FOR_BODY3_PREHEADER]] ]
233; CHECK-NEXT:    [[INDVAR1:%.*]] = phi i32 [ [[TMP0:%.*]], [[FOR_BODY3_SPLIT]] ], [ 49, [[FOR_BODY3_PREHEADER]] ]
234; CHECK-NEXT:    [[OR_REDUCTION_OUTER]] = phi i32 [ [[OR_LCSSA:%.*]], [[FOR_BODY3_SPLIT]] ], [ [[A]], [[FOR_BODY3_PREHEADER]] ]
235; CHECK-NEXT:    br label [[FOR_BODY_PREHEADER]]
236; CHECK:       for.body3.split1:
237; CHECK-NEXT:    [[ARRAYIDX5:%.*]] = getelementptr inbounds [200 x [200 x i32]], ptr @b, i64 0, i32 [[INDVAR0]], i64 [[INDEX]]
238; CHECK-NEXT:    [[LOAD_VAL:%.*]] = load i32, ptr [[ARRAYIDX5]], align 4
239; CHECK-NEXT:    [[OR]] = or i32 [[OR_REDUCTION_INNER]], [[LOAD_VAL]]
240; CHECK-NEXT:    [[INDVAR0_NEXT:%.*]] = add nsw i32 [[INDVAR0]], 1
241; CHECK-NEXT:    [[INDVAR1_NEXT:%.*]] = add nsw i32 [[INDVAR1]], -1
242; CHECK-NEXT:    [[TOBOOL2:%.*]] = icmp eq i32 [[INDVAR0_NEXT]], [[INDVAR1_NEXT]]
243; CHECK-NEXT:    br label [[FOR_INC7]]
244; CHECK:       for.body3.split:
245; CHECK-NEXT:    [[OR_LCSSA]] = phi i32 [ [[OR]], [[FOR_INC7]] ]
246; CHECK-NEXT:    [[TMP0]] = add nsw i32 [[INDVAR1]], -1
247; CHECK-NEXT:    [[TMP1]] = add nsw i32 [[INDVAR0]], 1
248; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], [[TMP0]]
249; CHECK-NEXT:    br i1 [[TMP2]], label [[FOR_COND_FOR_END8_CRIT_EDGE:%.*]], label [[FOR_BODY3]]
250; CHECK:       for.inc7:
251; CHECK-NEXT:    [[INDVARS_OUTER_NEXT]] = add nsw i64 [[INDVARS_OUTER]], 1
252; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[INDVARS_OUTER_NEXT]], 100
253; CHECK-NEXT:    br i1 [[TOBOOL]], label [[FOR_BODY3_SPLIT]], label [[FOR_BODY]]
254; CHECK:       for.cond.for.end8_crit_edge:
255; CHECK-NEXT:    [[OR_LCSSA_LCSSA:%.*]] = phi i32 [ [[OR_LCSSA]], [[FOR_BODY3_SPLIT]] ]
256; CHECK-NEXT:    store i32 [[OR_LCSSA_LCSSA]], ptr @a, align 4
257; CHECK-NEXT:    br label [[FOR_END8:%.*]]
258; CHECK:       for.end8:
259; CHECK-NEXT:    ret void
260;
261
262entry:
263  %a = load i32, ptr @a
264  br label %for.body
265
266for.body:                                         ; preds = %for.body.lr.ph, %for.inc7
267  %indvars.outer = phi i64 [ 0, %entry ], [ %indvars.outer.next, %for.inc7 ]
268  %or.reduction.outer = phi i32 [ %a, %entry ], [ %or.lcssa, %for.inc7 ]
269  %index = add nsw i64 %indvars.outer, 9
270  br label %for.body3
271
272for.body3:                                        ; preds = %for.body, %for.body3
273  %or.reduction.inner = phi i32 [ %or.reduction.outer, %for.body ], [ %or, %for.body3 ]
274  %indvar0 = phi i32 [ 5, %for.body ], [ %indvar0.next, %for.body3 ]
275  %indvar1 = phi i32 [ 49, %for.body ], [ %indvar1.next, %for.body3 ]
276  %arrayidx5 = getelementptr inbounds [200 x [200 x i32]], ptr @b, i64 0, i32 %indvar0, i64 %index
277  %load.val = load i32, ptr %arrayidx5, align 4
278  %or = or i32 %or.reduction.inner, %load.val
279  %indvar0.next = add nsw i32 %indvar0, 1
280  %indvar1.next = add nsw i32 %indvar1, -1
281  %tobool2 = icmp eq i32 %indvar0.next, %indvar1.next
282  br i1 %tobool2, label %for.inc7, label %for.body3
283
284for.inc7:                                         ; preds = %for.body3
285  %or.lcssa = phi i32 [ %or, %for.body3 ]
286  %indvars.outer.next = add nsw i64 %indvars.outer, 1
287  %tobool = icmp eq i64 %indvars.outer.next, 100
288  br i1 %tobool, label %for.cond.for.end8_crit_edge, label %for.body
289
290for.cond.for.end8_crit_edge:                      ; preds = %for.inc7
291  %or.lcssa.lcssa = phi i32 [ %or.lcssa, %for.inc7 ]
292  store i32 %or.lcssa.lcssa, ptr @a
293  br label %for.end8
294
295for.end8:                                         ; preds = %for.cond.for.end8_crit_edge, %entry
296  ret void
297}
298