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