Remove triple from this test, it makes it fail when X86 TTI is missing.
[oota-llvm.git] / test / Transforms / LoopStrengthReduce / 2012-07-18-LimitReassociate.ll
1 ; RUN: opt -loop-reduce -disable-output -debug-only=loop-reduce < %s 2> %t
2 ; RUN: FileCheck %s < %t
3 ; REQUIRES: asserts
4 ;
5 ; PR13361: LSR + SCEV "hangs" on reasonably sized test with sequence of loops
6 ;
7 ; Without limits on CollectSubexpr, we have thousands of formulae for
8 ; the use that crosses loops. With limits we have five.
9 ; CHECK: LSR on loop %bb221:
10 ; CHECK: After generating reuse formulae:
11 ; CHECK: LSR is examining the following uses:
12 ; CHECK: LSR Use: Kind=Special
13 ; CHECK: {{.*reg\(\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{}}
14 ; CHECK: {{.*reg\(\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{}}
15 ; CHECK: {{.*reg\(\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{}}
16 ; CHECK: {{.*reg\(\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{}}
17 ; CHECK: {{.*reg\(\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{}}
18 ; CHECK-NOT:reg
19 ; CHECK: Filtering for use
20
21 %struct.snork = type { %struct.fuga, i32, i32, i32, i32, i32, i32 }
22 %struct.fuga = type { %struct.gork, i64 }
23 %struct.gork = type { i8*, i32, i32, %struct.noot* }
24 %struct.noot = type opaque
25 %struct.jim = type { [5120 x i8], i32, i32, [2048 x i8], i32, [256 x i8] }
26
27 @global = external global %struct.snork, align 8
28 @global1 = external hidden unnamed_addr constant [52 x i8], align 1
29 @global2 = external hidden unnamed_addr constant [18 x i8], align 1
30 @global3 = external hidden global %struct.jim, align 32
31 @global4 = external hidden unnamed_addr constant [40 x i8], align 1
32
33 declare void @snork(...) nounwind
34
35 declare fastcc void @blarg() nounwind uwtable readonly
36
37 define hidden fastcc void @boogle() nounwind uwtable {
38 bb:
39   %tmp = trunc i64 0 to i32
40   %tmp1 = icmp slt i32 %tmp, 2047
41   %tmp2 = add i32 0, -1
42   %tmp3 = icmp ult i32 %tmp2, 255
43   %tmp4 = and i1 %tmp1, %tmp3
44   br i1 %tmp4, label %bb6, label %bb5
45
46 bb5:                                              ; preds = %bb
47   tail call void (...)* @snork(i8* getelementptr inbounds ([52 x i8]* @global1, i64 0, i64 0), i32 2021) nounwind
48   tail call void (...)* @snork(i8* getelementptr inbounds (%struct.jim* @global3, i64 0, i32 3, i64 1), i32 -2146631418) nounwind
49   unreachable
50
51 bb6:                                              ; preds = %bb
52   tail call void @zot(i8* getelementptr inbounds (%struct.jim* @global3, i64 0, i32 5, i64 0), i8* getelementptr inbounds (%struct.jim* @global3, i64 0, i32 3, i64 1), i64 undef, i32 1, i1 false) nounwind
53   %tmp7 = getelementptr inbounds %struct.jim* @global3, i64 0, i32 5, i64 undef
54   store i8 0, i8* %tmp7, align 1
55   %tmp8 = add nsw i32 0, 1
56   %tmp9 = sext i32 %tmp8 to i64
57   %tmp10 = add i64 %tmp9, 1
58   %tmp11 = getelementptr inbounds %struct.jim* @global3, i64 0, i32 3, i64 %tmp10
59   %tmp12 = sub i64 2047, %tmp9
60   %tmp13 = icmp eq i32 undef, 1
61   br i1 %tmp13, label %bb14, label %bb15
62
63 bb14:                                             ; preds = %bb6
64   tail call fastcc void @blarg()
65   unreachable
66
67 bb15:                                             ; preds = %bb6
68   %tmp16 = trunc i64 %tmp12 to i32
69   br label %bb17
70
71 bb17:                                             ; preds = %bb26, %bb15
72   %tmp18 = phi i64 [ %tmp28, %bb26 ], [ 0, %bb15 ]
73   %tmp19 = phi i32 [ %tmp29, %bb26 ], [ 0, %bb15 ]
74   %tmp20 = trunc i64 %tmp18 to i32
75   %tmp21 = icmp slt i32 %tmp20, %tmp16
76   br i1 %tmp21, label %bb22, label %bb32
77
78 bb22:                                             ; preds = %bb17
79   %tmp23 = getelementptr inbounds %struct.jim* @global3, i64 0, i32 3, i64 0
80   %tmp24 = load i8* %tmp23, align 1
81   %tmp25 = icmp eq i8 %tmp24, 58
82   br i1 %tmp25, label %bb30, label %bb26
83
84 bb26:                                             ; preds = %bb22
85   %tmp27 = icmp eq i8 %tmp24, 0
86   %tmp28 = add i64 %tmp18, 1
87   %tmp29 = add nsw i32 %tmp19, 1
88   br i1 %tmp27, label %bb32, label %bb17
89
90 bb30:                                             ; preds = %bb22
91   %tmp31 = icmp ult i32 undef, 255
92   br i1 %tmp31, label %bb33, label %bb32
93
94 bb32:                                             ; preds = %bb30, %bb26, %bb17
95   tail call void (...)* @snork(i8* getelementptr inbounds ([52 x i8]* @global1, i64 0, i64 0), i32 2038) nounwind
96   tail call void (...)* @snork(i8* %tmp11, i32 -2146631418) nounwind
97   unreachable
98
99 bb33:                                             ; preds = %bb30
100   tail call void @zot(i8* getelementptr inbounds (%struct.jim* @global3, i64 0, i32 5, i64 0), i8* %tmp11, i64 undef, i32 1, i1 false) nounwind
101   %tmp34 = getelementptr inbounds %struct.jim* @global3, i64 0, i32 5, i64 undef
102   store i8 0, i8* %tmp34, align 1
103   %tmp35 = add nsw i32 %tmp19, 1
104   %tmp36 = sext i32 %tmp35 to i64
105   %tmp37 = add i64 %tmp36, %tmp10
106   %tmp38 = getelementptr inbounds %struct.jim* @global3, i64 0, i32 3, i64 %tmp37
107   %tmp39 = sub i64 %tmp12, %tmp36
108   br i1 false, label %bb40, label %bb41
109
110 bb40:                                             ; preds = %bb33
111   br label %bb41
112
113 bb41:                                             ; preds = %bb40, %bb33
114   %tmp42 = trunc i64 %tmp39 to i32
115   br label %bb43
116
117 bb43:                                             ; preds = %bb52, %bb41
118   %tmp44 = phi i64 [ %tmp53, %bb52 ], [ 0, %bb41 ]
119   %tmp45 = phi i32 [ %tmp54, %bb52 ], [ 0, %bb41 ]
120   %tmp46 = trunc i64 %tmp44 to i32
121   %tmp47 = icmp slt i32 %tmp46, %tmp42
122   br i1 %tmp47, label %bb48, label %bb58
123
124 bb48:                                             ; preds = %bb43
125   %tmp49 = add i64 %tmp44, %tmp37
126   %tmp50 = load i8* undef, align 1
127   %tmp51 = icmp eq i8 %tmp50, 58
128   br i1 %tmp51, label %bb55, label %bb52
129
130 bb52:                                             ; preds = %bb48
131   %tmp53 = add i64 %tmp44, 1
132   %tmp54 = add nsw i32 %tmp45, 1
133   br i1 undef, label %bb58, label %bb43
134
135 bb55:                                             ; preds = %bb48
136   %tmp56 = add i32 %tmp45, -1
137   %tmp57 = icmp ult i32 %tmp56, 255
138   br i1 %tmp57, label %bb59, label %bb58
139
140 bb58:                                             ; preds = %bb55, %bb52, %bb43
141   tail call void (...)* @snork(i8* getelementptr inbounds ([52 x i8]* @global1, i64 0, i64 0), i32 2055) nounwind
142   tail call void (...)* @snork(i8* %tmp38, i32 -2146631418) nounwind
143   br label %bb247
144
145 bb59:                                             ; preds = %bb55
146   %tmp60 = sext i32 %tmp45 to i64
147   tail call void @zot(i8* getelementptr inbounds (%struct.jim* @global3, i64 0, i32 5, i64 0), i8* %tmp38, i64 %tmp60, i32 1, i1 false) nounwind
148   %tmp61 = getelementptr inbounds %struct.jim* @global3, i64 0, i32 5, i64 %tmp60
149   store i8 0, i8* %tmp61, align 1
150   %tmp62 = add nsw i32 %tmp45, 1
151   %tmp63 = sext i32 %tmp62 to i64
152   %tmp64 = add i64 %tmp63, %tmp37
153   %tmp65 = sub i64 %tmp39, %tmp63
154   %tmp66 = icmp eq i32 undef, 2
155   br i1 %tmp66, label %bb67, label %bb68
156
157 bb67:                                             ; preds = %bb59
158   tail call fastcc void @blarg()
159   unreachable
160
161 bb68:                                             ; preds = %bb59
162   switch i32 undef, label %bb71 [
163     i32 0, label %bb74
164     i32 -1, label %bb69
165   ]
166
167 bb69:                                             ; preds = %bb68
168   tail call void (...)* @snork(i8* getelementptr inbounds ([52 x i8]* @global1, i64 0, i64 0), i32 2071) nounwind
169   %tmp70 = load i32* getelementptr inbounds (%struct.snork* @global, i64 0, i32 2), align 4
170   unreachable
171
172 bb71:                                             ; preds = %bb68
173   %tmp72 = load i32* getelementptr inbounds (%struct.snork* @global, i64 0, i32 4), align 4
174   %tmp73 = icmp eq i32 undef, 0
175   br i1 %tmp73, label %bb247, label %bb74
176
177 bb74:                                             ; preds = %bb71, %bb68
178   %tmp75 = trunc i64 %tmp65 to i32
179   br label %bb76
180
181 bb76:                                             ; preds = %bb82, %bb74
182   %tmp77 = phi i64 [ %tmp84, %bb82 ], [ 0, %bb74 ]
183   %tmp78 = phi i32 [ %tmp85, %bb82 ], [ 0, %bb74 ]
184   %tmp79 = trunc i64 %tmp77 to i32
185   %tmp80 = icmp slt i32 %tmp79, %tmp75
186   br i1 %tmp80, label %bb81, label %bb87
187
188 bb81:                                             ; preds = %bb76
189   br i1 false, label %bb86, label %bb82
190
191 bb82:                                             ; preds = %bb81
192   %tmp83 = icmp eq i8 0, 0
193   %tmp84 = add i64 %tmp77, 1
194   %tmp85 = add nsw i32 %tmp78, 1
195   br i1 %tmp83, label %bb87, label %bb76
196
197 bb86:                                             ; preds = %bb81
198   br i1 undef, label %bb88, label %bb87
199
200 bb87:                                             ; preds = %bb86, %bb82, %bb76
201   unreachable
202
203 bb88:                                             ; preds = %bb86
204   %tmp89 = add nsw i32 %tmp78, 1
205   %tmp90 = sext i32 %tmp89 to i64
206   %tmp91 = add i64 %tmp90, %tmp64
207   %tmp92 = sub i64 %tmp65, %tmp90
208   br i1 false, label %bb93, label %bb94
209
210 bb93:                                             ; preds = %bb88
211   unreachable
212
213 bb94:                                             ; preds = %bb88
214   %tmp95 = trunc i64 %tmp92 to i32
215   br label %bb96
216
217 bb96:                                             ; preds = %bb102, %bb94
218   %tmp97 = phi i64 [ %tmp103, %bb102 ], [ 0, %bb94 ]
219   %tmp98 = phi i32 [ %tmp104, %bb102 ], [ 0, %bb94 ]
220   %tmp99 = trunc i64 %tmp97 to i32
221   %tmp100 = icmp slt i32 %tmp99, %tmp95
222   br i1 %tmp100, label %bb101, label %bb106
223
224 bb101:                                            ; preds = %bb96
225   br i1 undef, label %bb105, label %bb102
226
227 bb102:                                            ; preds = %bb101
228   %tmp103 = add i64 %tmp97, 1
229   %tmp104 = add nsw i32 %tmp98, 1
230   br i1 false, label %bb106, label %bb96
231
232 bb105:                                            ; preds = %bb101
233   br i1 undef, label %bb107, label %bb106
234
235 bb106:                                            ; preds = %bb105, %bb102, %bb96
236   br label %bb247
237
238 bb107:                                            ; preds = %bb105
239   %tmp108 = add nsw i32 %tmp98, 1
240   %tmp109 = sext i32 %tmp108 to i64
241   %tmp110 = add i64 %tmp109, %tmp91
242   %tmp111 = sub i64 %tmp92, %tmp109
243   br i1 false, label %bb112, label %bb113
244
245 bb112:                                            ; preds = %bb107
246   unreachable
247
248 bb113:                                            ; preds = %bb107
249   %tmp114 = trunc i64 %tmp111 to i32
250   br label %bb115
251
252 bb115:                                            ; preds = %bb121, %bb113
253   %tmp116 = phi i64 [ %tmp122, %bb121 ], [ 0, %bb113 ]
254   %tmp117 = phi i32 [ %tmp123, %bb121 ], [ 0, %bb113 ]
255   %tmp118 = trunc i64 %tmp116 to i32
256   %tmp119 = icmp slt i32 %tmp118, %tmp114
257   br i1 %tmp119, label %bb120, label %bb125
258
259 bb120:                                            ; preds = %bb115
260   br i1 undef, label %bb124, label %bb121
261
262 bb121:                                            ; preds = %bb120
263   %tmp122 = add i64 %tmp116, 1
264   %tmp123 = add nsw i32 %tmp117, 1
265   br i1 false, label %bb125, label %bb115
266
267 bb124:                                            ; preds = %bb120
268   br i1 false, label %bb126, label %bb125
269
270 bb125:                                            ; preds = %bb124, %bb121, %bb115
271   unreachable
272
273 bb126:                                            ; preds = %bb124
274   %tmp127 = add nsw i32 %tmp117, 1
275   %tmp128 = sext i32 %tmp127 to i64
276   %tmp129 = add i64 %tmp128, %tmp110
277   %tmp130 = sub i64 %tmp111, %tmp128
278   tail call fastcc void @blarg()
279   br i1 false, label %bb132, label %bb131
280
281 bb131:                                            ; preds = %bb126
282   unreachable
283
284 bb132:                                            ; preds = %bb126
285   %tmp133 = trunc i64 %tmp130 to i32
286   br label %bb134
287
288 bb134:                                            ; preds = %bb140, %bb132
289   %tmp135 = phi i64 [ %tmp141, %bb140 ], [ 0, %bb132 ]
290   %tmp136 = phi i32 [ %tmp142, %bb140 ], [ 0, %bb132 ]
291   %tmp137 = trunc i64 %tmp135 to i32
292   %tmp138 = icmp slt i32 %tmp137, %tmp133
293   br i1 %tmp138, label %bb139, label %bb144
294
295 bb139:                                            ; preds = %bb134
296   br i1 false, label %bb143, label %bb140
297
298 bb140:                                            ; preds = %bb139
299   %tmp141 = add i64 %tmp135, 1
300   %tmp142 = add nsw i32 %tmp136, 1
301   br i1 false, label %bb144, label %bb134
302
303 bb143:                                            ; preds = %bb139
304   br i1 false, label %bb145, label %bb144
305
306 bb144:                                            ; preds = %bb143, %bb140, %bb134
307   br label %bb247
308
309 bb145:                                            ; preds = %bb143
310   %tmp146 = add nsw i32 %tmp136, 1
311   %tmp147 = sext i32 %tmp146 to i64
312   %tmp148 = add i64 %tmp147, %tmp129
313   %tmp149 = sub i64 %tmp130, %tmp147
314   switch i32 0, label %bb152 [
315     i32 0, label %bb150
316     i32 16, label %bb150
317     i32 32, label %bb150
318     i32 48, label %bb150
319     i32 64, label %bb150
320     i32 256, label %bb150
321     i32 4096, label %bb150
322   ]
323
324 bb150:                                            ; preds = %bb145, %bb145, %bb145, %bb145, %bb145, %bb145, %bb145
325   %tmp151 = trunc i64 %tmp149 to i32
326   br label %bb153
327
328 bb152:                                            ; preds = %bb145
329   unreachable
330
331 bb153:                                            ; preds = %bb160, %bb150
332   %tmp154 = phi i64 [ %tmp161, %bb160 ], [ 0, %bb150 ]
333   %tmp155 = phi i32 [ %tmp162, %bb160 ], [ 0, %bb150 ]
334   %tmp156 = trunc i64 %tmp154 to i32
335   %tmp157 = icmp slt i32 %tmp156, %tmp151
336   br i1 %tmp157, label %bb158, label %bb166
337
338 bb158:                                            ; preds = %bb153
339   %tmp159 = add i64 %tmp154, %tmp148
340   br i1 false, label %bb163, label %bb160
341
342 bb160:                                            ; preds = %bb158
343   %tmp161 = add i64 %tmp154, 1
344   %tmp162 = add nsw i32 %tmp155, 1
345   br i1 false, label %bb166, label %bb153
346
347 bb163:                                            ; preds = %bb158
348   %tmp164 = add i32 %tmp155, -1
349   %tmp165 = icmp ult i32 %tmp164, 255
350   br i1 %tmp165, label %bb167, label %bb166
351
352 bb166:                                            ; preds = %bb163, %bb160, %bb153
353   unreachable
354
355 bb167:                                            ; preds = %bb163
356   %tmp168 = add nsw i32 %tmp155, 1
357   %tmp169 = sext i32 %tmp168 to i64
358   %tmp170 = add i64 %tmp169, %tmp148
359   %tmp171 = sub i64 %tmp149, %tmp169
360   br i1 false, label %bb173, label %bb172
361
362 bb172:                                            ; preds = %bb167
363   unreachable
364
365 bb173:                                            ; preds = %bb167
366   %tmp174 = trunc i64 %tmp171 to i32
367   br label %bb175
368
369 bb175:                                            ; preds = %bb181, %bb173
370   %tmp176 = phi i64 [ %tmp183, %bb181 ], [ 0, %bb173 ]
371   %tmp177 = phi i32 [ %tmp184, %bb181 ], [ 0, %bb173 ]
372   %tmp178 = trunc i64 %tmp176 to i32
373   %tmp179 = icmp slt i32 %tmp178, %tmp174
374   br i1 %tmp179, label %bb180, label %bb186
375
376 bb180:                                            ; preds = %bb175
377   br i1 false, label %bb185, label %bb181
378
379 bb181:                                            ; preds = %bb180
380   %tmp182 = icmp eq i8 0, 0
381   %tmp183 = add i64 %tmp176, 1
382   %tmp184 = add nsw i32 %tmp177, 1
383   br i1 %tmp182, label %bb186, label %bb175
384
385 bb185:                                            ; preds = %bb180
386   br i1 false, label %bb187, label %bb186
387
388 bb186:                                            ; preds = %bb185, %bb181, %bb175
389   unreachable
390
391 bb187:                                            ; preds = %bb185
392   %tmp188 = add nsw i32 %tmp177, 1
393   %tmp189 = sext i32 %tmp188 to i64
394   %tmp190 = sub i64 %tmp171, %tmp189
395   br i1 false, label %bb192, label %bb191
396
397 bb191:                                            ; preds = %bb187
398   unreachable
399
400 bb192:                                            ; preds = %bb187
401   %tmp193 = trunc i64 %tmp190 to i32
402   br label %bb194
403
404 bb194:                                            ; preds = %bb200, %bb192
405   %tmp195 = phi i64 [ %tmp201, %bb200 ], [ 0, %bb192 ]
406   %tmp196 = phi i32 [ %tmp202, %bb200 ], [ 0, %bb192 ]
407   %tmp197 = trunc i64 %tmp195 to i32
408   %tmp198 = icmp slt i32 %tmp197, %tmp193
409   br i1 %tmp198, label %bb199, label %bb204
410
411 bb199:                                            ; preds = %bb194
412   br i1 false, label %bb203, label %bb200
413
414 bb200:                                            ; preds = %bb199
415   %tmp201 = add i64 %tmp195, 1
416   %tmp202 = add nsw i32 %tmp196, 1
417   br i1 false, label %bb204, label %bb194
418
419 bb203:                                            ; preds = %bb199
420   br i1 undef, label %bb205, label %bb204
421
422 bb204:                                            ; preds = %bb203, %bb200, %bb194
423   unreachable
424
425 bb205:                                            ; preds = %bb203
426   %tmp206 = add nsw i32 %tmp196, 1
427   %tmp207 = sext i32 %tmp206 to i64
428   %tmp208 = add i64 %tmp207, 0
429   %tmp209 = sub i64 %tmp190, %tmp207
430   br i1 %tmp13, label %bb210, label %bb211
431
432 bb210:                                            ; preds = %bb205
433   unreachable
434
435 bb211:                                            ; preds = %bb205
436   %tmp212 = trunc i64 %tmp209 to i32
437   %tmp213 = icmp slt i32 0, %tmp212
438   br i1 false, label %bb215, label %bb214
439
440 bb214:                                            ; preds = %bb211
441   unreachable
442
443 bb215:                                            ; preds = %bb211
444   %tmp216 = add i64 undef, %tmp208
445   %tmp217 = sub i64 %tmp209, undef
446   br i1 false, label %bb218, label %bb219
447
448 bb218:                                            ; preds = %bb215
449   br label %bb219
450
451 bb219:                                            ; preds = %bb218, %bb215
452   %tmp220 = trunc i64 %tmp217 to i32
453   br label %bb221
454
455 bb221:                                            ; preds = %bb230, %bb219
456   %tmp222 = phi i64 [ %tmp231, %bb230 ], [ 0, %bb219 ]
457   %tmp223 = phi i32 [ %tmp232, %bb230 ], [ 0, %bb219 ]
458   %tmp224 = trunc i64 %tmp222 to i32
459   %tmp225 = icmp slt i32 %tmp224, %tmp220
460   br i1 %tmp225, label %bb226, label %bb234
461
462 bb226:                                            ; preds = %bb221
463   %tmp227 = add i64 %tmp222, %tmp216
464   %tmp228 = getelementptr inbounds %struct.jim* @global3, i64 0, i32 3, i64 %tmp227
465   %tmp229 = load i8* %tmp228, align 1
466   br i1 false, label %bb233, label %bb230
467
468 bb230:                                            ; preds = %bb226
469   %tmp231 = add i64 %tmp222, 1
470   %tmp232 = add nsw i32 %tmp223, 1
471   br i1 undef, label %bb234, label %bb221
472
473 bb233:                                            ; preds = %bb226
474   br i1 undef, label %bb235, label %bb234
475
476 bb234:                                            ; preds = %bb233, %bb230, %bb221
477   br label %bb247
478
479 bb235:                                            ; preds = %bb233
480   %tmp236 = add nsw i32 %tmp223, 1
481   %tmp237 = sext i32 %tmp236 to i64
482   %tmp238 = sub i64 %tmp217, %tmp237
483   br i1 %tmp66, label %bb239, label %bb240
484
485 bb239:                                            ; preds = %bb235
486   unreachable
487
488 bb240:                                            ; preds = %bb235
489   switch i32 0, label %bb244 [
490     i32 0, label %bb241
491     i32 1, label %bb241
492     i32 4, label %bb241
493     i32 6, label %bb241
494     i32 9, label %bb241
495   ]
496
497 bb241:                                            ; preds = %bb240, %bb240, %bb240, %bb240, %bb240
498   %tmp242 = trunc i64 %tmp238 to i32
499   %tmp243 = icmp slt i32 0, %tmp242
500   br i1 false, label %bb246, label %bb245
501
502 bb244:                                            ; preds = %bb240
503   unreachable
504
505 bb245:                                            ; preds = %bb241
506   unreachable
507
508 bb246:                                            ; preds = %bb241
509   unreachable
510
511 bb247:                                            ; preds = %bb234, %bb144, %bb106, %bb71, %bb58
512   ret void
513 }
514
515 declare void @zot(i8* nocapture, i8* nocapture, i64, i32, i1) nounwind