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
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
10 ;; for (c = 0; c < 100; c++) {
11 ;; for (d = 5, e = 5; d > 0, e > 0; d--, e--)
16 ; There are multiple inner loop indvars and only one
17 ; of them is used in the loop exit condition at the
20 define void @test1() {
21 ; CHECK-LABEL: @test1(
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:%.*]]
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:%.*]]
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]]
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:%.*]]
63 ; CHECK-NEXT: ret void
70 for.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
76 for.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
88 for.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
95 for.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
100 for.end8: ; preds = %for.cond.for.end8_crit_edge, %entry
107 ;; for (c = 0 ; c < 100; c++) {
108 ;; for (d = 5, e = 6; d + e > 0; d--, e = e - 2)
113 ; All inner loop indvars are used in the inner latch.
115 define void @test2() {
116 ; CHECK-LABEL: @test2(
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:%.*]]
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:%.*]]
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]]
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:%.*]]
162 ; CHECK-NEXT: ret void
165 %a = load i32, ptr @a
168 for.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
174 for.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
188 for.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
195 for.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
200 for.end8: ; preds = %for.cond.for.end8_crit_edge, %entry
207 ;; for (c = 0 ; c < 100; c++) {
210 ;; for (; d != e; d++, e--)
215 ; Two inner loop indvars are involved in the inner loop exit
216 ; condition as LHS and RHS.
217 define void @test3() {
218 ; CHECK-LABEL: @test3(
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:%.*]]
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:%.*]]
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]]
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:%.*]]
259 ; CHECK-NEXT: ret void
263 %a = load i32, ptr @a
266 for.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
272 for.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
284 for.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
290 for.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
295 for.end8: ; preds = %for.cond.for.end8_crit_edge, %entry