519 lines · plain
1; RUN: opt -loop-reduce -disable-output -debug-only=loop-reduce < %s 2>&1 | FileCheck %s2; REQUIRES: asserts3;4; PR13361: LSR + SCEV "hangs" on reasonably sized test with sequence of loops5;6; Without limits on CollectSubexpr, we have thousands of formulae for7; the use that crosses loops. With limits we have five.8; CHECK: LSR on loop %bb221:9; CHECK: After generating reuse formulae:10; CHECK: LSR is examining the following uses:11; CHECK: LSR Use: Kind=Special12; CHECK: {{.*reg\(\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{}}13; CHECK: {{.*reg\(\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{}}14; CHECK: {{.*reg\(\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{}}15; CHECK: {{.*reg\(\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{}}16; CHECK: {{.*reg\(\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{.*\{}}17; CHECK-NOT:reg18; CHECK: Filtering for use19 20; Provide legal integer types.21target datalayout = "n8:16:32:64"22 23 24%struct.snork = type { %struct.fuga, i32, i32, i32, i32, i32, i32 }25%struct.fuga = type { %struct.gork, i64 }26%struct.gork = type { ptr, i32, i32, ptr }27%struct.noot = type opaque28%struct.jim = type { [5120 x i8], i32, i32, [2048 x i8], i32, [256 x i8] }29 30@global = external global %struct.snork, align 831@global1 = external hidden unnamed_addr constant [52 x i8], align 132@global2 = external hidden unnamed_addr constant [18 x i8], align 133@global3 = external hidden global %struct.jim, align 3234@global4 = external hidden unnamed_addr constant [40 x i8], align 135 36declare void @snork(...) nounwind37 38declare fastcc void @blarg() nounwind uwtable readonly39 40define hidden fastcc void @boogle() nounwind uwtable {41bb:42 %tmp = trunc i64 0 to i3243 %tmp1 = icmp slt i32 %tmp, 204744 %tmp2 = add i32 0, -145 %tmp3 = icmp ult i32 %tmp2, 25546 %tmp4 = and i1 %tmp1, %tmp347 br i1 %tmp4, label %bb6, label %bb548 49bb5: ; preds = %bb50 tail call void (...) @snork(ptr @global1, i32 2021) nounwind51 tail call void (...) @snork(ptr getelementptr inbounds (%struct.jim, ptr @global3, i64 0, i32 3, i64 1), i32 -2146631418) nounwind52 unreachable53 54bb6: ; preds = %bb55 tail call void @zot(ptr getelementptr inbounds (%struct.jim, ptr @global3, i64 0, i32 5, i64 0), ptr getelementptr inbounds (%struct.jim, ptr @global3, i64 0, i32 3, i64 1), i64 undef, i32 1, i1 false) nounwind56 %tmp7 = getelementptr inbounds %struct.jim, ptr @global3, i64 0, i32 5, i64 undef57 store i8 0, ptr %tmp7, align 158 %tmp8 = add nsw i32 0, 159 %tmp9 = sext i32 %tmp8 to i6460 %tmp10 = add i64 %tmp9, 161 %tmp11 = getelementptr inbounds %struct.jim, ptr @global3, i64 0, i32 3, i64 %tmp1062 %tmp12 = sub i64 2047, %tmp963 %tmp13 = icmp eq i32 undef, 164 br i1 %tmp13, label %bb14, label %bb1565 66bb14: ; preds = %bb667 tail call fastcc void @blarg()68 unreachable69 70bb15: ; preds = %bb671 %tmp16 = trunc i64 %tmp12 to i3272 br label %bb1773 74bb17: ; preds = %bb26, %bb1575 %tmp18 = phi i64 [ %tmp28, %bb26 ], [ 0, %bb15 ]76 %tmp19 = phi i32 [ %tmp29, %bb26 ], [ 0, %bb15 ]77 %tmp20 = trunc i64 %tmp18 to i3278 %tmp21 = icmp slt i32 %tmp20, %tmp1679 br i1 %tmp21, label %bb22, label %bb3280 81bb22: ; preds = %bb1782 %tmp23 = getelementptr inbounds %struct.jim, ptr @global3, i64 0, i32 3, i64 083 %tmp24 = load i8, ptr %tmp23, align 184 %tmp25 = icmp eq i8 %tmp24, 5885 br i1 %tmp25, label %bb30, label %bb2686 87bb26: ; preds = %bb2288 %tmp27 = icmp eq i8 %tmp24, 089 %tmp28 = add i64 %tmp18, 190 %tmp29 = add nsw i32 %tmp19, 191 br i1 %tmp27, label %bb32, label %bb1792 93bb30: ; preds = %bb2294 %tmp31 = icmp ult i32 undef, 25595 br i1 %tmp31, label %bb33, label %bb3296 97bb32: ; preds = %bb30, %bb26, %bb1798 tail call void (...) @snork(ptr @global1, i32 2038) nounwind99 tail call void (...) @snork(ptr %tmp11, i32 -2146631418) nounwind100 unreachable101 102bb33: ; preds = %bb30103 tail call void @zot(ptr getelementptr inbounds (%struct.jim, ptr @global3, i64 0, i32 5, i64 0), ptr %tmp11, i64 undef, i32 1, i1 false) nounwind104 %tmp34 = getelementptr inbounds %struct.jim, ptr @global3, i64 0, i32 5, i64 undef105 store i8 0, ptr %tmp34, align 1106 %tmp35 = add nsw i32 %tmp19, 1107 %tmp36 = sext i32 %tmp35 to i64108 %tmp37 = add i64 %tmp36, %tmp10109 %tmp38 = getelementptr inbounds %struct.jim, ptr @global3, i64 0, i32 3, i64 %tmp37110 %tmp39 = sub i64 %tmp12, %tmp36111 br i1 false, label %bb40, label %bb41112 113bb40: ; preds = %bb33114 br label %bb41115 116bb41: ; preds = %bb40, %bb33117 %tmp42 = trunc i64 %tmp39 to i32118 br label %bb43119 120bb43: ; preds = %bb52, %bb41121 %tmp44 = phi i64 [ %tmp53, %bb52 ], [ 0, %bb41 ]122 %tmp45 = phi i32 [ %tmp54, %bb52 ], [ 0, %bb41 ]123 %tmp46 = trunc i64 %tmp44 to i32124 %tmp47 = icmp slt i32 %tmp46, %tmp42125 br i1 %tmp47, label %bb48, label %bb58126 127bb48: ; preds = %bb43128 %tmp49 = add i64 %tmp44, %tmp37129 %tmp50 = load i8, ptr undef, align 1130 %tmp51 = icmp eq i8 %tmp50, 58131 br i1 %tmp51, label %bb55, label %bb52132 133bb52: ; preds = %bb48134 %tmp53 = add i64 %tmp44, 1135 %tmp54 = add nsw i32 %tmp45, 1136 br i1 undef, label %bb58, label %bb43137 138bb55: ; preds = %bb48139 %tmp56 = add i32 %tmp45, -1140 %tmp57 = icmp ult i32 %tmp56, 255141 br i1 %tmp57, label %bb59, label %bb58142 143bb58: ; preds = %bb55, %bb52, %bb43144 tail call void (...) @snork(ptr @global1, i32 2055) nounwind145 tail call void (...) @snork(ptr %tmp38, i32 -2146631418) nounwind146 br label %bb247147 148bb59: ; preds = %bb55149 %tmp60 = sext i32 %tmp45 to i64150 tail call void @zot(ptr getelementptr inbounds (%struct.jim, ptr @global3, i64 0, i32 5, i64 0), ptr %tmp38, i64 %tmp60, i32 1, i1 false) nounwind151 %tmp61 = getelementptr inbounds %struct.jim, ptr @global3, i64 0, i32 5, i64 %tmp60152 store i8 0, ptr %tmp61, align 1153 %tmp62 = add nsw i32 %tmp45, 1154 %tmp63 = sext i32 %tmp62 to i64155 %tmp64 = add i64 %tmp63, %tmp37156 %tmp65 = sub i64 %tmp39, %tmp63157 %tmp66 = icmp eq i32 undef, 2158 br i1 %tmp66, label %bb67, label %bb68159 160bb67: ; preds = %bb59161 tail call fastcc void @blarg()162 unreachable163 164bb68: ; preds = %bb59165 switch i32 undef, label %bb71 [166 i32 0, label %bb74167 i32 -1, label %bb69168 ]169 170bb69: ; preds = %bb68171 tail call void (...) @snork(ptr @global1, i32 2071) nounwind172 %tmp70 = load i32, ptr getelementptr inbounds (%struct.snork, ptr @global, i64 0, i32 2), align 4173 unreachable174 175bb71: ; preds = %bb68176 %tmp72 = load i32, ptr getelementptr inbounds (%struct.snork, ptr @global, i64 0, i32 4), align 4177 %tmp73 = icmp eq i32 undef, 0178 br i1 %tmp73, label %bb247, label %bb74179 180bb74: ; preds = %bb71, %bb68181 %tmp75 = trunc i64 %tmp65 to i32182 br label %bb76183 184bb76: ; preds = %bb82, %bb74185 %tmp77 = phi i64 [ %tmp84, %bb82 ], [ 0, %bb74 ]186 %tmp78 = phi i32 [ %tmp85, %bb82 ], [ 0, %bb74 ]187 %tmp79 = trunc i64 %tmp77 to i32188 %tmp80 = icmp slt i32 %tmp79, %tmp75189 br i1 %tmp80, label %bb81, label %bb87190 191bb81: ; preds = %bb76192 br i1 false, label %bb86, label %bb82193 194bb82: ; preds = %bb81195 %tmp83 = icmp eq i8 0, 0196 %tmp84 = add i64 %tmp77, 1197 %tmp85 = add nsw i32 %tmp78, 1198 br i1 %tmp83, label %bb87, label %bb76199 200bb86: ; preds = %bb81201 br i1 undef, label %bb88, label %bb87202 203bb87: ; preds = %bb86, %bb82, %bb76204 unreachable205 206bb88: ; preds = %bb86207 %tmp89 = add nsw i32 %tmp78, 1208 %tmp90 = sext i32 %tmp89 to i64209 %tmp91 = add i64 %tmp90, %tmp64210 %tmp92 = sub i64 %tmp65, %tmp90211 br i1 false, label %bb93, label %bb94212 213bb93: ; preds = %bb88214 unreachable215 216bb94: ; preds = %bb88217 %tmp95 = trunc i64 %tmp92 to i32218 br label %bb96219 220bb96: ; preds = %bb102, %bb94221 %tmp97 = phi i64 [ %tmp103, %bb102 ], [ 0, %bb94 ]222 %tmp98 = phi i32 [ %tmp104, %bb102 ], [ 0, %bb94 ]223 %tmp99 = trunc i64 %tmp97 to i32224 %tmp100 = icmp slt i32 %tmp99, %tmp95225 br i1 %tmp100, label %bb101, label %bb106226 227bb101: ; preds = %bb96228 br i1 undef, label %bb105, label %bb102229 230bb102: ; preds = %bb101231 %tmp103 = add i64 %tmp97, 1232 %tmp104 = add nsw i32 %tmp98, 1233 br i1 false, label %bb106, label %bb96234 235bb105: ; preds = %bb101236 br i1 undef, label %bb107, label %bb106237 238bb106: ; preds = %bb105, %bb102, %bb96239 br label %bb247240 241bb107: ; preds = %bb105242 %tmp108 = add nsw i32 %tmp98, 1243 %tmp109 = sext i32 %tmp108 to i64244 %tmp110 = add i64 %tmp109, %tmp91245 %tmp111 = sub i64 %tmp92, %tmp109246 br i1 false, label %bb112, label %bb113247 248bb112: ; preds = %bb107249 unreachable250 251bb113: ; preds = %bb107252 %tmp114 = trunc i64 %tmp111 to i32253 br label %bb115254 255bb115: ; preds = %bb121, %bb113256 %tmp116 = phi i64 [ %tmp122, %bb121 ], [ 0, %bb113 ]257 %tmp117 = phi i32 [ %tmp123, %bb121 ], [ 0, %bb113 ]258 %tmp118 = trunc i64 %tmp116 to i32259 %tmp119 = icmp slt i32 %tmp118, %tmp114260 br i1 %tmp119, label %bb120, label %bb125261 262bb120: ; preds = %bb115263 br i1 undef, label %bb124, label %bb121264 265bb121: ; preds = %bb120266 %tmp122 = add i64 %tmp116, 1267 %tmp123 = add nsw i32 %tmp117, 1268 br i1 false, label %bb125, label %bb115269 270bb124: ; preds = %bb120271 br i1 false, label %bb126, label %bb125272 273bb125: ; preds = %bb124, %bb121, %bb115274 unreachable275 276bb126: ; preds = %bb124277 %tmp127 = add nsw i32 %tmp117, 1278 %tmp128 = sext i32 %tmp127 to i64279 %tmp129 = add i64 %tmp128, %tmp110280 %tmp130 = sub i64 %tmp111, %tmp128281 tail call fastcc void @blarg()282 br i1 false, label %bb132, label %bb131283 284bb131: ; preds = %bb126285 unreachable286 287bb132: ; preds = %bb126288 %tmp133 = trunc i64 %tmp130 to i32289 br label %bb134290 291bb134: ; preds = %bb140, %bb132292 %tmp135 = phi i64 [ %tmp141, %bb140 ], [ 0, %bb132 ]293 %tmp136 = phi i32 [ %tmp142, %bb140 ], [ 0, %bb132 ]294 %tmp137 = trunc i64 %tmp135 to i32295 %tmp138 = icmp slt i32 %tmp137, %tmp133296 br i1 %tmp138, label %bb139, label %bb144297 298bb139: ; preds = %bb134299 br i1 false, label %bb143, label %bb140300 301bb140: ; preds = %bb139302 %tmp141 = add i64 %tmp135, 1303 %tmp142 = add nsw i32 %tmp136, 1304 br i1 false, label %bb144, label %bb134305 306bb143: ; preds = %bb139307 br i1 false, label %bb145, label %bb144308 309bb144: ; preds = %bb143, %bb140, %bb134310 br label %bb247311 312bb145: ; preds = %bb143313 %tmp146 = add nsw i32 %tmp136, 1314 %tmp147 = sext i32 %tmp146 to i64315 %tmp148 = add i64 %tmp147, %tmp129316 %tmp149 = sub i64 %tmp130, %tmp147317 switch i32 0, label %bb152 [318 i32 0, label %bb150319 i32 16, label %bb150320 i32 32, label %bb150321 i32 48, label %bb150322 i32 64, label %bb150323 i32 256, label %bb150324 i32 4096, label %bb150325 ]326 327bb150: ; preds = %bb145, %bb145, %bb145, %bb145, %bb145, %bb145, %bb145328 %tmp151 = trunc i64 %tmp149 to i32329 br label %bb153330 331bb152: ; preds = %bb145332 unreachable333 334bb153: ; preds = %bb160, %bb150335 %tmp154 = phi i64 [ %tmp161, %bb160 ], [ 0, %bb150 ]336 %tmp155 = phi i32 [ %tmp162, %bb160 ], [ 0, %bb150 ]337 %tmp156 = trunc i64 %tmp154 to i32338 %tmp157 = icmp slt i32 %tmp156, %tmp151339 br i1 %tmp157, label %bb158, label %bb166340 341bb158: ; preds = %bb153342 %tmp159 = add i64 %tmp154, %tmp148343 br i1 false, label %bb163, label %bb160344 345bb160: ; preds = %bb158346 %tmp161 = add i64 %tmp154, 1347 %tmp162 = add nsw i32 %tmp155, 1348 br i1 false, label %bb166, label %bb153349 350bb163: ; preds = %bb158351 %tmp164 = add i32 %tmp155, -1352 %tmp165 = icmp ult i32 %tmp164, 255353 br i1 %tmp165, label %bb167, label %bb166354 355bb166: ; preds = %bb163, %bb160, %bb153356 unreachable357 358bb167: ; preds = %bb163359 %tmp168 = add nsw i32 %tmp155, 1360 %tmp169 = sext i32 %tmp168 to i64361 %tmp170 = add i64 %tmp169, %tmp148362 %tmp171 = sub i64 %tmp149, %tmp169363 br i1 false, label %bb173, label %bb172364 365bb172: ; preds = %bb167366 unreachable367 368bb173: ; preds = %bb167369 %tmp174 = trunc i64 %tmp171 to i32370 br label %bb175371 372bb175: ; preds = %bb181, %bb173373 %tmp176 = phi i64 [ %tmp183, %bb181 ], [ 0, %bb173 ]374 %tmp177 = phi i32 [ %tmp184, %bb181 ], [ 0, %bb173 ]375 %tmp178 = trunc i64 %tmp176 to i32376 %tmp179 = icmp slt i32 %tmp178, %tmp174377 br i1 %tmp179, label %bb180, label %bb186378 379bb180: ; preds = %bb175380 br i1 false, label %bb185, label %bb181381 382bb181: ; preds = %bb180383 %tmp182 = icmp eq i8 0, 0384 %tmp183 = add i64 %tmp176, 1385 %tmp184 = add nsw i32 %tmp177, 1386 br i1 %tmp182, label %bb186, label %bb175387 388bb185: ; preds = %bb180389 br i1 false, label %bb187, label %bb186390 391bb186: ; preds = %bb185, %bb181, %bb175392 unreachable393 394bb187: ; preds = %bb185395 %tmp188 = add nsw i32 %tmp177, 1396 %tmp189 = sext i32 %tmp188 to i64397 %tmp190 = sub i64 %tmp171, %tmp189398 br i1 false, label %bb192, label %bb191399 400bb191: ; preds = %bb187401 unreachable402 403bb192: ; preds = %bb187404 %tmp193 = trunc i64 %tmp190 to i32405 br label %bb194406 407bb194: ; preds = %bb200, %bb192408 %tmp195 = phi i64 [ %tmp201, %bb200 ], [ 0, %bb192 ]409 %tmp196 = phi i32 [ %tmp202, %bb200 ], [ 0, %bb192 ]410 %tmp197 = trunc i64 %tmp195 to i32411 %tmp198 = icmp slt i32 %tmp197, %tmp193412 br i1 %tmp198, label %bb199, label %bb204413 414bb199: ; preds = %bb194415 br i1 false, label %bb203, label %bb200416 417bb200: ; preds = %bb199418 %tmp201 = add i64 %tmp195, 1419 %tmp202 = add nsw i32 %tmp196, 1420 br i1 false, label %bb204, label %bb194421 422bb203: ; preds = %bb199423 br i1 undef, label %bb205, label %bb204424 425bb204: ; preds = %bb203, %bb200, %bb194426 unreachable427 428bb205: ; preds = %bb203429 %tmp206 = add nsw i32 %tmp196, 1430 %tmp207 = sext i32 %tmp206 to i64431 %tmp208 = add i64 %tmp207, 0432 %tmp209 = sub i64 %tmp190, %tmp207433 br i1 %tmp13, label %bb210, label %bb211434 435bb210: ; preds = %bb205436 unreachable437 438bb211: ; preds = %bb205439 %tmp212 = trunc i64 %tmp209 to i32440 %tmp213 = icmp slt i32 0, %tmp212441 br i1 false, label %bb215, label %bb214442 443bb214: ; preds = %bb211444 unreachable445 446bb215: ; preds = %bb211447 %tmp216 = add i64 undef, %tmp208448 %tmp217 = sub i64 %tmp209, undef449 br i1 false, label %bb218, label %bb219450 451bb218: ; preds = %bb215452 br label %bb219453 454bb219: ; preds = %bb218, %bb215455 %tmp220 = trunc i64 %tmp217 to i32456 br label %bb221457 458bb221: ; preds = %bb230, %bb219459 %tmp222 = phi i64 [ %tmp231, %bb230 ], [ 0, %bb219 ]460 %tmp223 = phi i32 [ %tmp232, %bb230 ], [ 0, %bb219 ]461 %tmp224 = trunc i64 %tmp222 to i32462 %tmp225 = icmp slt i32 %tmp224, %tmp220463 br i1 %tmp225, label %bb226, label %bb234464 465bb226: ; preds = %bb221466 %tmp227 = add i64 %tmp222, %tmp216467 %tmp228 = getelementptr inbounds %struct.jim, ptr @global3, i64 0, i32 3, i64 %tmp227468 %tmp229 = load i8, ptr %tmp228, align 1469 br i1 false, label %bb233, label %bb230470 471bb230: ; preds = %bb226472 %tmp231 = add i64 %tmp222, 1473 %tmp232 = add nsw i32 %tmp223, 1474 br i1 undef, label %bb234, label %bb221475 476bb233: ; preds = %bb226477 br i1 undef, label %bb235, label %bb234478 479bb234: ; preds = %bb233, %bb230, %bb221480 br label %bb247481 482bb235: ; preds = %bb233483 %tmp236 = add nsw i32 %tmp223, 1484 %tmp237 = sext i32 %tmp236 to i64485 %tmp238 = sub i64 %tmp217, %tmp237486 br i1 %tmp66, label %bb239, label %bb240487 488bb239: ; preds = %bb235489 unreachable490 491bb240: ; preds = %bb235492 switch i32 0, label %bb244 [493 i32 0, label %bb241494 i32 1, label %bb241495 i32 4, label %bb241496 i32 6, label %bb241497 i32 9, label %bb241498 ]499 500bb241: ; preds = %bb240, %bb240, %bb240, %bb240, %bb240501 %tmp242 = trunc i64 %tmp238 to i32502 %tmp243 = icmp slt i32 0, %tmp242503 br i1 false, label %bb246, label %bb245504 505bb244: ; preds = %bb240506 unreachable507 508bb245: ; preds = %bb241509 unreachable510 511bb246: ; preds = %bb241512 unreachable513 514bb247: ; preds = %bb234, %bb144, %bb106, %bb71, %bb58515 ret void516}517 518declare void @zot(ptr nocapture, ptr nocapture, i64, i32, i1) nounwind519