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 516
