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 = constant [200 x [100 x i32]] zeroinitializer, align 4
5@a = constant i32 0, align 4
6
7; // Loop wth two outer indvars.
8; int a, c, d, e;
9; int b[200][100];
10; void test1() {
11;  for (c = 0, e = 1; c < 100 && e < 150; c++, e++) {
12;    d = 5;
13;    for (; d; d--)
14;      a |= b[d][c + 9];
15;   }
16; }
17define void @test1() {
18; CHECK-LABEL: @test1(
19; CHECK-NEXT:  entry:
20; CHECK-NEXT:    [[A:%.*]] = load i32, ptr @a, align 4
21; CHECK-NEXT:    br label [[FOR_BODY4_PREHEADER:%.*]]
22; CHECK:       for.cond2.preheader.preheader:
23; CHECK-NEXT:    br label [[FOR_COND2_PREHEADER:%.*]]
24; CHECK:       for.cond2.preheader:
25; CHECK-NEXT:    [[INDVAR0:%.*]] = phi i64 [ [[INDVAR0_NEXT:%.*]], [[FOR_INC7:%.*]] ], [ 0, [[FOR_COND2_PREHEADER_PREHEADER:%.*]] ]
26; CHECK-NEXT:    [[INDVAR1:%.*]] = phi i32 [ [[INDVAR1_NEXT:%.*]], [[FOR_INC7]] ], [ 1, [[FOR_COND2_PREHEADER_PREHEADER]] ]
27; CHECK-NEXT:    [[OR13:%.*]] = phi i32 [ [[OR:%.*]], [[FOR_INC7]] ], [ [[OR_REDUCTION:%.*]], [[FOR_COND2_PREHEADER_PREHEADER]] ]
28; CHECK-NEXT:    [[INDEX:%.*]] = add nsw i64 [[INDVAR0]], 9
29; CHECK-NEXT:    br label [[FOR_BODY4_SPLIT1:%.*]]
30; CHECK:       for.body4.preheader:
31; CHECK-NEXT:    br label [[FOR_BODY4:%.*]]
32; CHECK:       for.body4:
33; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[TMP0:%.*]], [[FOR_BODY4_SPLIT:%.*]] ], [ 5, [[FOR_BODY4_PREHEADER]] ]
34; CHECK-NEXT:    [[OR_REDUCTION]] = phi i32 [ [[OR_LCSSA:%.*]], [[FOR_BODY4_SPLIT]] ], [ [[A]], [[FOR_BODY4_PREHEADER]] ]
35; CHECK-NEXT:    br label [[FOR_COND2_PREHEADER_PREHEADER]]
36; CHECK:       for.body4.split1:
37; CHECK-NEXT:    [[ARRAYIDX6:%.*]] = getelementptr inbounds [200 x [100 x i32]], ptr @b, i64 0, i64 [[INDVARS_IV]], i64 [[INDEX]]
38; CHECK-NEXT:    [[LOAD_VAL:%.*]] = load i32, ptr [[ARRAYIDX6]], align 4
39; CHECK-NEXT:    [[OR]] = or i32 [[OR13]], [[LOAD_VAL]]
40; CHECK-NEXT:    [[INDVARS_IV_NEXT:%.*]] = add nsw i64 [[INDVARS_IV]], -1
41; CHECK-NEXT:    [[TOBOOL3:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 0
42; CHECK-NEXT:    br label [[FOR_INC7]]
43; CHECK:       for.body4.split:
44; CHECK-NEXT:    [[OR_LCSSA]] = phi i32 [ [[OR]], [[FOR_INC7]] ]
45; CHECK-NEXT:    [[TMP0]] = add nsw i64 [[INDVARS_IV]], -1
46; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[TMP0]], 0
47; CHECK-NEXT:    br i1 [[TMP1]], label [[FOR_COND_FOR_END9_CRIT_EDGE:%.*]], label [[FOR_BODY4]]
48; CHECK:       for.inc7:
49; CHECK-NEXT:    [[INDVAR0_NEXT]] = add nsw i64 [[INDVAR0]], 1
50; CHECK-NEXT:    [[INDVAR1_NEXT]] = add nsw i32 [[INDVAR1]], 1
51; CHECK-NEXT:    [[INDVAR0_NEXT_TRUNC:%.*]] = trunc i64 [[INDVAR0_NEXT]] to i32
52; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i32 [[INDVAR0_NEXT_TRUNC]], 100
53; CHECK-NEXT:    [[TOBOOL1:%.*]] = icmp ne i32 [[INDVAR1_NEXT]], 150
54; CHECK-NEXT:    [[OUTER_COND:%.*]] = and i1 [[TOBOOL]], [[TOBOOL1]]
55; CHECK-NEXT:    br i1 [[OUTER_COND]], label [[FOR_COND2_PREHEADER]], label [[FOR_BODY4_SPLIT]]
56; CHECK:       for.cond.for.end9_crit_edge:
57; CHECK-NEXT:    [[OR_LCSSA_LCSSA:%.*]] = phi i32 [ [[OR_LCSSA]], [[FOR_BODY4_SPLIT]] ]
58; CHECK-NEXT:    store i32 [[OR_LCSSA_LCSSA]], ptr @a, align 4
59; CHECK-NEXT:    br label [[FOR_END9:%.*]]
60; CHECK:       for.end9:
61; CHECK-NEXT:    ret void
62;
63
64
65entry:
66  %a = load i32, ptr @a, align 4
67  br label %for.cond2.preheader
68
69for.cond2.preheader:                              ; preds = %entry, %for.inc7
70  %indvar0 = phi i64 [ 0, %entry ], [ %indvar0.next, %for.inc7 ]
71  %or.reduction = phi i32 [ %a, %entry ], [ %or.lcssa, %for.inc7 ]
72  %indvar1 = phi i32 [ 1, %entry ], [ %indvar1.next, %for.inc7 ]
73  %index = add nsw i64 %indvar0, 9
74  br label %for.body4
75
76for.body4:                                        ; preds = %for.cond2.preheader, %for.body4
77  %indvars.iv = phi i64 [ 5, %for.cond2.preheader ], [ %indvars.iv.next, %for.body4 ]
78  %or13 = phi i32 [ %or.reduction, %for.cond2.preheader ], [ %or, %for.body4 ]
79  %arrayidx6 = getelementptr inbounds [200 x [100 x i32]], ptr @b, i64 0, i64 %indvars.iv, i64 %index
80  %load.val = load i32, ptr %arrayidx6, align 4
81  %or = or i32 %or13, %load.val
82  %indvars.iv.next = add nsw i64 %indvars.iv, -1
83  %tobool3 = icmp eq i64 %indvars.iv.next, 0
84  br i1 %tobool3, label %for.inc7, label %for.body4
85
86for.inc7:                                         ; preds = %for.body4
87  %or.lcssa = phi i32 [ %or, %for.body4 ]
88  %indvar0.next = add nsw i64 %indvar0, 1
89  %indvar1.next = add nsw i32 %indvar1, 1
90  %indvar0.next.trunc = trunc i64 %indvar0.next to i32
91  %tobool = icmp ne i32 %indvar0.next.trunc, 100
92  %tobool1 = icmp ne i32 %indvar1.next, 150
93  %outer.cond = and i1 %tobool, %tobool1
94  br i1 %outer.cond, label %for.cond2.preheader, label %for.cond.for.end9_crit_edge
95
96for.cond.for.end9_crit_edge:                      ; preds = %for.inc7
97  %or.lcssa.lcssa = phi i32 [ %or.lcssa, %for.inc7 ]
98  store i32 %or.lcssa.lcssa, ptr @a, align 4
99  br label %for.end9
100
101for.end9:                                         ; preds = %for.cond.for.end9_crit_edge, %entry
102  ret void
103}
104
105; // Both two outer indvars are involved in array accesses
106; // inside the inner loop.
107; int a, c, d, e;
108; int b[200][100];
109; void test2() {
110;  for (c = 0, e = 1; c < 100 && e < 150; c++, e++) {
111;     d = 5;
112;     for (; d; d--)
113;       a |= b[d + e][c + 9];
114;   }
115; }
116
117define void @test2() {
118; CHECK-LABEL: @test2(
119; CHECK-NEXT:  entry:
120; CHECK-NEXT:    [[A:%.*]] = load i32, ptr @a, align 4
121; CHECK-NEXT:    br label [[FOR_BODY4_PREHEADER:%.*]]
122; CHECK:       for.cond2.preheader.preheader:
123; CHECK-NEXT:    br label [[FOR_COND2_PREHEADER:%.*]]
124; CHECK:       for.cond2.preheader:
125; CHECK-NEXT:    [[INDVAR0:%.*]] = phi i64 [ [[INDVAR0_NEXT:%.*]], [[FOR_INC7:%.*]] ], [ 0, [[FOR_COND2_PREHEADER_PREHEADER:%.*]] ]
126; CHECK-NEXT:    [[INDVAR1:%.*]] = phi i64 [ [[INDVAR1_NEXT:%.*]], [[FOR_INC7]] ], [ 1, [[FOR_COND2_PREHEADER_PREHEADER]] ]
127; CHECK-NEXT:    [[OR13:%.*]] = phi i32 [ [[OR:%.*]], [[FOR_INC7]] ], [ [[OR_REDUCTION:%.*]], [[FOR_COND2_PREHEADER_PREHEADER]] ]
128; CHECK-NEXT:    [[INDEX0:%.*]] = add nsw i64 [[INDVAR0]], 9
129; CHECK-NEXT:    br label [[FOR_BODY4_SPLIT1:%.*]]
130; CHECK:       for.body4.preheader:
131; CHECK-NEXT:    br label [[FOR_BODY4:%.*]]
132; CHECK:       for.body4:
133; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[TMP0:%.*]], [[FOR_BODY4_SPLIT:%.*]] ], [ 5, [[FOR_BODY4_PREHEADER]] ]
134; CHECK-NEXT:    [[OR_REDUCTION]] = phi i32 [ [[OR_LCSSA:%.*]], [[FOR_BODY4_SPLIT]] ], [ [[A]], [[FOR_BODY4_PREHEADER]] ]
135; CHECK-NEXT:    br label [[FOR_COND2_PREHEADER_PREHEADER]]
136; CHECK:       for.body4.split1:
137; CHECK-NEXT:    [[INDEX1:%.*]] = add nsw i64 [[INDVARS_IV]], [[INDVAR1]]
138; CHECK-NEXT:    [[ARRAYIDX6:%.*]] = getelementptr inbounds [200 x [100 x i32]], ptr @b, i64 0, i64 [[INDEX1]], i64 [[INDEX0]]
139; CHECK-NEXT:    [[LOAD_VAL:%.*]] = load i32, ptr [[ARRAYIDX6]], align 4
140; CHECK-NEXT:    [[OR]] = or i32 [[OR13]], [[LOAD_VAL]]
141; CHECK-NEXT:    [[INDVARS_IV_NEXT:%.*]] = add nsw i64 [[INDVARS_IV]], -1
142; CHECK-NEXT:    [[TOBOOL3:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 0
143; CHECK-NEXT:    br label [[FOR_INC7]]
144; CHECK:       for.body4.split:
145; CHECK-NEXT:    [[OR_LCSSA]] = phi i32 [ [[OR]], [[FOR_INC7]] ]
146; CHECK-NEXT:    [[TMP0]] = add nsw i64 [[INDVARS_IV]], -1
147; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[TMP0]], 0
148; CHECK-NEXT:    br i1 [[TMP1]], label [[FOR_COND_FOR_END9_CRIT_EDGE:%.*]], label [[FOR_BODY4]]
149; CHECK:       for.inc7:
150; CHECK-NEXT:    [[INDVAR0_NEXT]] = add nsw i64 [[INDVAR0]], 1
151; CHECK-NEXT:    [[INDVAR1_NEXT]] = add nsw i64 [[INDVAR1]], 1
152; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i64 [[INDVAR0_NEXT]], 100
153; CHECK-NEXT:    [[TOBOOL1:%.*]] = icmp ne i64 [[INDVAR1_NEXT]], 150
154; CHECK-NEXT:    [[OUTER_COND:%.*]] = and i1 [[TOBOOL]], [[TOBOOL1]]
155; CHECK-NEXT:    br i1 [[OUTER_COND]], label [[FOR_COND2_PREHEADER]], label [[FOR_BODY4_SPLIT]]
156; CHECK:       for.cond.for.end9_crit_edge:
157; CHECK-NEXT:    [[OR_LCSSA_LCSSA:%.*]] = phi i32 [ [[OR_LCSSA]], [[FOR_BODY4_SPLIT]] ]
158; CHECK-NEXT:    store i32 [[OR_LCSSA_LCSSA]], ptr @a, align 4
159; CHECK-NEXT:    br label [[FOR_END9:%.*]]
160; CHECK:       for.end9:
161; CHECK-NEXT:    ret void
162;
163entry:
164  %a = load i32, ptr @a, align 4
165  br label %for.cond2.preheader
166
167for.cond2.preheader:                              ; preds = %entry, %for.inc7
168  %indvar0 = phi i64 [ 0, %entry ], [ %indvar0.next, %for.inc7 ]
169  %or.reduction = phi i32 [ %a, %entry ], [ %or.lcssa, %for.inc7 ]
170  %indvar1 = phi i64 [ 1, %entry ], [ %indvar1.next, %for.inc7 ]
171  %index0 = add nsw i64 %indvar0, 9
172  br label %for.body4
173
174for.body4:                                        ; preds = %for.cond2.preheader, %for.body4
175  %indvars.iv = phi i64 [ 5, %for.cond2.preheader ], [ %indvars.iv.next, %for.body4 ]
176  %or13 = phi i32 [ %or.reduction, %for.cond2.preheader ], [ %or, %for.body4 ]
177  %index1 = add nsw i64 %indvars.iv, %indvar1
178  %arrayidx6 = getelementptr inbounds [200 x [100 x i32]], ptr @b, i64 0, i64 %index1, i64 %index0
179  %load.val = load i32, ptr %arrayidx6, align 4
180  %or = or i32 %or13, %load.val
181  %indvars.iv.next = add nsw i64 %indvars.iv, -1
182  %tobool3 = icmp eq i64 %indvars.iv.next, 0
183  br i1 %tobool3, label %for.inc7, label %for.body4
184
185for.inc7:                                         ; preds = %for.body4
186  %or.lcssa = phi i32 [ %or, %for.body4 ]
187  %indvar0.next = add nsw i64 %indvar0, 1
188  %indvar1.next = add nsw i64 %indvar1, 1
189  %tobool = icmp ne i64 %indvar0.next, 100
190  %tobool1 = icmp ne i64 %indvar1.next, 150
191  %outer.cond = and i1 %tobool, %tobool1
192  br i1 %outer.cond, label %for.cond2.preheader, label %for.cond.for.end9_crit_edge
193
194for.cond.for.end9_crit_edge:                      ; preds = %for.inc7
195  %or.lcssa.lcssa = phi i32 [ %or.lcssa, %for.inc7 ]
196  store i32 %or.lcssa.lcssa, ptr @a, align 4
197  br label %for.end9
198
199for.end9:                                         ; preds = %for.cond.for.end9_crit_edge, %entry
200  ret void
201}
202
203
204; // Both two outer indvars are involved in a single
205; // outer loop exit condition.
206; int a, c, d, e;
207; int b[200][100];
208; void test3() {
209;  for (c = 0, e = 1; c + e < 150; c++, e++) {
210;     d = 5;
211;     for (; d; d--)
212;       a |= b[d + e][c + 9];
213;   }
214; }
215
216define void @test3() {
217; CHECK-LABEL: @test3(
218; CHECK-NEXT:  entry:
219; CHECK-NEXT:    [[A:%.*]] = load i32, ptr @a, align 4
220; CHECK-NEXT:    br label [[FOR_BODY4_PREHEADER:%.*]]
221; CHECK:       for.cond2.preheader.preheader:
222; CHECK-NEXT:    br label [[FOR_COND2_PREHEADER:%.*]]
223; CHECK:       for.cond2.preheader:
224; CHECK-NEXT:    [[INDVAR0:%.*]] = phi i64 [ [[INDVAR0_NEXT:%.*]], [[FOR_INC7:%.*]] ], [ 0, [[FOR_COND2_PREHEADER_PREHEADER:%.*]] ]
225; CHECK-NEXT:    [[INDVAR1:%.*]] = phi i64 [ [[INDVAR1_NEXT:%.*]], [[FOR_INC7]] ], [ 1, [[FOR_COND2_PREHEADER_PREHEADER]] ]
226; CHECK-NEXT:    [[OR13:%.*]] = phi i32 [ [[OR:%.*]], [[FOR_INC7]] ], [ [[OR_REDUCTION:%.*]], [[FOR_COND2_PREHEADER_PREHEADER]] ]
227; CHECK-NEXT:    [[INDEX0:%.*]] = add nsw i64 [[INDVAR0]], 9
228; CHECK-NEXT:    br label [[FOR_BODY4_SPLIT1:%.*]]
229; CHECK:       for.body4.preheader:
230; CHECK-NEXT:    br label [[FOR_BODY4:%.*]]
231; CHECK:       for.body4:
232; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[TMP0:%.*]], [[FOR_BODY4_SPLIT:%.*]] ], [ 5, [[FOR_BODY4_PREHEADER]] ]
233; CHECK-NEXT:    [[OR_REDUCTION]] = phi i32 [ [[OR_LCSSA:%.*]], [[FOR_BODY4_SPLIT]] ], [ [[A]], [[FOR_BODY4_PREHEADER]] ]
234; CHECK-NEXT:    br label [[FOR_COND2_PREHEADER_PREHEADER]]
235; CHECK:       for.body4.split1:
236; CHECK-NEXT:    [[INDEX1:%.*]] = add nsw i64 [[INDVARS_IV]], [[INDVAR1]]
237; CHECK-NEXT:    [[ARRAYIDX6:%.*]] = getelementptr inbounds [200 x [100 x i32]], ptr @b, i64 0, i64 [[INDEX1]], i64 [[INDEX0]]
238; CHECK-NEXT:    [[LOAD_VAL:%.*]] = load i32, ptr [[ARRAYIDX6]], align 4
239; CHECK-NEXT:    [[OR]] = or i32 [[OR13]], [[LOAD_VAL]]
240; CHECK-NEXT:    [[INDVARS_IV_NEXT:%.*]] = add nsw i64 [[INDVARS_IV]], -1
241; CHECK-NEXT:    [[TOBOOL3:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 0
242; CHECK-NEXT:    br label [[FOR_INC7]]
243; CHECK:       for.body4.split:
244; CHECK-NEXT:    [[OR_LCSSA]] = phi i32 [ [[OR]], [[FOR_INC7]] ]
245; CHECK-NEXT:    [[TMP0]] = add nsw i64 [[INDVARS_IV]], -1
246; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[TMP0]], 0
247; CHECK-NEXT:    br i1 [[TMP1]], label [[FOR_COND_FOR_END9_CRIT_EDGE:%.*]], label [[FOR_BODY4]]
248; CHECK:       for.inc7:
249; CHECK-NEXT:    [[INDVAR0_NEXT]] = add nsw i64 [[INDVAR0]], 1
250; CHECK-NEXT:    [[INDVAR1_NEXT]] = add nsw i64 [[INDVAR1]], 1
251; CHECK-NEXT:    [[OUTER_INDVAR_ADD:%.*]] = add nsw i64 [[INDVAR0_NEXT]], [[INDVAR1_NEXT]]
252; CHECK-NEXT:    [[OUTER_COND:%.*]] = icmp slt i64 [[OUTER_INDVAR_ADD]], 150
253; CHECK-NEXT:    br i1 [[OUTER_COND]], label [[FOR_COND2_PREHEADER]], label [[FOR_BODY4_SPLIT]]
254; CHECK:       for.cond.for.end9_crit_edge:
255; CHECK-NEXT:    [[OR_LCSSA_LCSSA:%.*]] = phi i32 [ [[OR_LCSSA]], [[FOR_BODY4_SPLIT]] ]
256; CHECK-NEXT:    store i32 [[OR_LCSSA_LCSSA]], ptr @a, align 4
257; CHECK-NEXT:    br label [[FOR_END9:%.*]]
258; CHECK:       for.end9:
259; CHECK-NEXT:    ret void
260;
261entry:
262  %a = load i32, ptr @a, align 4
263  br label %for.cond2.preheader
264
265for.cond2.preheader:                              ; preds = %entry, %for.inc7
266  %indvar0 = phi i64 [ 0, %entry ], [ %indvar0.next, %for.inc7 ]
267  %or.reduction = phi i32 [ %a, %entry ], [ %or.lcssa, %for.inc7 ]
268  %indvar1 = phi i64 [ 1, %entry ], [ %indvar1.next, %for.inc7 ]
269  %index0 = add nsw i64 %indvar0, 9
270  br label %for.body4
271
272for.body4:                                        ; preds = %for.cond2.preheader, %for.body4
273  %indvars.iv = phi i64 [ 5, %for.cond2.preheader ], [ %indvars.iv.next, %for.body4 ]
274  %or13 = phi i32 [ %or.reduction, %for.cond2.preheader ], [ %or, %for.body4 ]
275  %index1 = add nsw i64 %indvars.iv, %indvar1
276  %arrayidx6 = getelementptr inbounds [200 x [100 x i32]], ptr @b, i64 0, i64 %index1, i64 %index0
277  %load.val = load i32, ptr %arrayidx6, align 4
278  %or = or i32 %or13, %load.val
279  %indvars.iv.next = add nsw i64 %indvars.iv, -1
280  %tobool3 = icmp eq i64 %indvars.iv.next, 0
281  br i1 %tobool3, label %for.inc7, label %for.body4
282
283for.inc7:                                         ; preds = %for.body4
284  %or.lcssa = phi i32 [ %or, %for.body4 ]
285  %indvar0.next = add nsw i64 %indvar0, 1
286  %indvar1.next = add nsw i64 %indvar1, 1
287  %outer.indvar.add = add nsw i64 %indvar0.next, %indvar1.next
288  %outer.cond = icmp slt i64 %outer.indvar.add, 150
289  br i1 %outer.cond, label %for.cond2.preheader, label %for.cond.for.end9_crit_edge
290
291for.cond.for.end9_crit_edge:                      ; preds = %for.inc7
292  %or.lcssa.lcssa = phi i32 [ %or.lcssa, %for.inc7 ]
293  store i32 %or.lcssa.lcssa, ptr @a, align 4
294  br label %for.end9
295
296for.end9:                                         ; preds = %for.cond.for.end9_crit_edge, %entry
297  ret void
298}
299