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