Bump version to 19.1.0-rc3
[llvm-project.git] / llvm / test / Transforms / LoopInterchange / interchangeable-outerloop-multiple-indvars.ll
blob76fc43e26e0e7250ff6fd8a20567b1da188f37a7
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 = constant [200 x [100 x i32]] zeroinitializer, align 4
5 @a = constant i32 0, align 4
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 ; }
17 define 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
65 entry:
66   %a = load i32, ptr @a, align 4
67   br label %for.cond2.preheader
69 for.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
76 for.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
86 for.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
96 for.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
101 for.end9:                                         ; preds = %for.cond.for.end9_crit_edge, %entry
102   ret void
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 ; }
117 define 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
163 entry:
164   %a = load i32, ptr @a, align 4
165   br label %for.cond2.preheader
167 for.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
174 for.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
185 for.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
194 for.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
199 for.end9:                                         ; preds = %for.cond.for.end9_crit_edge, %entry
200   ret void
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 ; }
216 define 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
261 entry:
262   %a = load i32, ptr @a, align 4
263   br label %for.cond2.preheader
265 for.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
272 for.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
283 for.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
291 for.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
296 for.end9:                                         ; preds = %for.cond.for.end9_crit_edge, %entry
297   ret void