426 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt < %s -passes=loop-deletion -verify-dom-info -S | FileCheck %s3 4target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64"5 6%pair_t = type { i64, i64 }7 8; The loop %inner cannot be removed, because it has outgoing values. But the9; outer loop is a no-op and can be removed.10define void @test1(i64 %N, i64 %M, ptr %ptr) willreturn {11; CHECK-LABEL: @test1(12; CHECK-NEXT: entry:13; CHECK-NEXT: br label [[EXIT:%.*]]14; CHECK: exit:15; CHECK-NEXT: ret void16;17entry:18 br label %outer.header19 20outer.header:21 %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]22 23 br label %inner24 25inner:26 %inner.iv = phi i64 [ 0, %outer.header ], [ %inner.iv.next, %inner ]27 %gep = getelementptr %pair_t, ptr %ptr, i64 %inner.iv28 %p = load %pair_t, ptr %gep29 %v.0 = extractvalue %pair_t %p, 030 %v.1 = extractvalue %pair_t %p, 131 %inner.ec = icmp ult i64 %v.0, %v.132 %inner.iv.next = add i64 %inner.iv, 133 br i1 %inner.ec, label %outer.latch, label %inner34 35outer.latch:36 %lcssa = phi i64 [ %v.1, %inner ]37 %outer.ec = icmp ult i64 %outer.iv, %lcssa38 %outer.iv.next = add i64 %outer.iv, 139 br i1 %outer.ec, label %exit, label %outer.header40 41exit:42 ret void43}44 45declare void @sideeffect()46 47; Same as @test1, but with a call in the outer loop. Nothing can be deleted.48define void @test2_sideeffect_in_outer(i64 %N, i64 %M, ptr %ptr) willreturn {49; CHECK-LABEL: @test2_sideeffect_in_outer(50; CHECK-NEXT: entry:51; CHECK-NEXT: br label [[OUTER_HEADER:%.*]]52; CHECK: outer.header:53; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_IV_NEXT:%.*]], [[OUTER_LATCH:%.*]] ]54; CHECK-NEXT: br label [[INNER:%.*]]55; CHECK: inner:56; CHECK-NEXT: [[INNER_IV:%.*]] = phi i64 [ 0, [[OUTER_HEADER]] ], [ [[INNER_IV_NEXT:%.*]], [[INNER]] ]57; CHECK-NEXT: [[GEP:%.*]] = getelementptr [[PAIR_T:%.*]], ptr [[PTR:%.*]], i64 [[INNER_IV]]58; CHECK-NEXT: [[P:%.*]] = load [[PAIR_T]], ptr [[GEP]], align 459; CHECK-NEXT: [[V_0:%.*]] = extractvalue [[PAIR_T]] [[P]], 060; CHECK-NEXT: [[V_1:%.*]] = extractvalue [[PAIR_T]] [[P]], 161; CHECK-NEXT: [[INNER_EC:%.*]] = icmp ult i64 [[V_0]], [[V_1]]62; CHECK-NEXT: [[INNER_IV_NEXT]] = add i64 [[INNER_IV]], 163; CHECK-NEXT: br i1 [[INNER_EC]], label [[OUTER_LATCH]], label [[INNER]]64; CHECK: outer.latch:65; CHECK-NEXT: [[LCSSA:%.*]] = phi i64 [ [[V_1]], [[INNER]] ]66; CHECK-NEXT: [[OUTER_EC:%.*]] = icmp ult i64 [[OUTER_IV]], [[LCSSA]]67; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 168; CHECK-NEXT: call void @sideeffect()69; CHECK-NEXT: br i1 [[OUTER_EC]], label [[EXIT:%.*]], label [[OUTER_HEADER]]70; CHECK: exit:71; CHECK-NEXT: ret void72;73entry:74 br label %outer.header75 76outer.header:77 %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]78 79 br label %inner80 81inner:82 %inner.iv = phi i64 [ 0, %outer.header ], [ %inner.iv.next, %inner ]83 %gep = getelementptr %pair_t, ptr %ptr, i64 %inner.iv84 %p = load %pair_t, ptr %gep85 %v.0 = extractvalue %pair_t %p, 086 %v.1 = extractvalue %pair_t %p, 187 %inner.ec = icmp ult i64 %v.0, %v.188 %inner.iv.next = add i64 %inner.iv, 189 br i1 %inner.ec, label %outer.latch, label %inner90 91outer.latch:92 %lcssa = phi i64 [ %v.1, %inner ]93 %outer.ec = icmp ult i64 %outer.iv, %lcssa94 %outer.iv.next = add i64 %outer.iv, 195 call void @sideeffect()96 br i1 %outer.ec, label %exit, label %outer.header97 98exit:99 ret void100}101 102; Same as @test1, but with a call in the inner loop. Nothing can be deleted.103define void @test3_sideeffect_in_inner(i64 %N, i64 %M, ptr %ptr) willreturn {104; CHECK-LABEL: @test3_sideeffect_in_inner(105; CHECK-NEXT: entry:106; CHECK-NEXT: br label [[OUTER_HEADER:%.*]]107; CHECK: outer.header:108; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_IV_NEXT:%.*]], [[OUTER_LATCH:%.*]] ]109; CHECK-NEXT: br label [[INNER:%.*]]110; CHECK: inner:111; CHECK-NEXT: [[INNER_IV:%.*]] = phi i64 [ 0, [[OUTER_HEADER]] ], [ [[INNER_IV_NEXT:%.*]], [[INNER]] ]112; CHECK-NEXT: [[GEP:%.*]] = getelementptr [[PAIR_T:%.*]], ptr [[PTR:%.*]], i64 [[INNER_IV]]113; CHECK-NEXT: [[P:%.*]] = load [[PAIR_T]], ptr [[GEP]], align 4114; CHECK-NEXT: [[V_0:%.*]] = extractvalue [[PAIR_T]] [[P]], 0115; CHECK-NEXT: [[V_1:%.*]] = extractvalue [[PAIR_T]] [[P]], 1116; CHECK-NEXT: [[INNER_EC:%.*]] = icmp ult i64 [[V_0]], [[V_1]]117; CHECK-NEXT: [[INNER_IV_NEXT]] = add i64 [[INNER_IV]], 1118; CHECK-NEXT: call void @sideeffect()119; CHECK-NEXT: br i1 [[INNER_EC]], label [[OUTER_LATCH]], label [[INNER]]120; CHECK: outer.latch:121; CHECK-NEXT: [[LCSSA:%.*]] = phi i64 [ [[V_1]], [[INNER]] ]122; CHECK-NEXT: [[OUTER_EC:%.*]] = icmp ult i64 [[OUTER_IV]], [[LCSSA]]123; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1124; CHECK-NEXT: br i1 [[OUTER_EC]], label [[EXIT:%.*]], label [[OUTER_HEADER]]125; CHECK: exit:126; CHECK-NEXT: ret void127;128entry:129 br label %outer.header130 131outer.header:132 %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]133 134 br label %inner135 136inner:137 %inner.iv = phi i64 [ 0, %outer.header ], [ %inner.iv.next, %inner ]138 %gep = getelementptr %pair_t, ptr %ptr, i64 %inner.iv139 %p = load %pair_t, ptr %gep140 %v.0 = extractvalue %pair_t %p, 0141 %v.1 = extractvalue %pair_t %p, 1142 %inner.ec = icmp ult i64 %v.0, %v.1143 %inner.iv.next = add i64 %inner.iv, 1144 call void @sideeffect()145 br i1 %inner.ec, label %outer.latch, label %inner146 147outer.latch:148 %lcssa = phi i64 [ %v.1, %inner ]149 %outer.ec = icmp ult i64 %outer.iv, %lcssa150 %outer.iv.next = add i64 %outer.iv, 1151 br i1 %outer.ec, label %exit, label %outer.header152 153exit:154 ret void155}156 157; The inner loop may not terminate, so we cannot remove it, unless the158; function/loop is mustprogress. Test case from PR50511.159define void @inner_loop_may_be_infinite(i1 %c1, i1 %c2) {160; CHECK-LABEL: @inner_loop_may_be_infinite(161; CHECK-NEXT: br label [[LOOP1:%.*]]162; CHECK: loop1:163; CHECK-NEXT: br i1 [[C1:%.*]], label [[LOOP1_LATCH:%.*]], label [[LOOP2_PREHEADER:%.*]]164; CHECK: loop2.preheader:165; CHECK-NEXT: br label [[LOOP2:%.*]]166; CHECK: loop2:167; CHECK-NEXT: br i1 [[C2:%.*]], label [[LOOP1_LATCH_LOOPEXIT:%.*]], label [[LOOP2]]168; CHECK: loop1.latch.loopexit:169; CHECK-NEXT: br label [[LOOP1_LATCH]]170; CHECK: loop1.latch:171; CHECK-NEXT: br label [[EXIT:%.*]]172; CHECK: exit:173; CHECK-NEXT: ret void174;175 br label %loop1176 177loop1:178 br i1 %c1, label %loop1.latch, label %loop2179 180loop2:181 br i1 %c2, label %loop1.latch, label %loop2182 183loop1.latch:184 br i1 false, label %loop1, label %exit185 186exit:187 ret void188}189 190; Similar to @inner_loop_may_be_infinite, but the function is marked as191; mustprogress. The loops can be removed.192define void @inner_loop_may_be_infinite_but_fn_mustprogress(i1 %c1, i1 %c2) mustprogress {193; CHECK-LABEL: @inner_loop_may_be_infinite_but_fn_mustprogress(194; CHECK-NEXT: br label [[EXIT:%.*]]195; CHECK: exit:196; CHECK-NEXT: ret void197;198 br label %loop1199 200loop1:201 br i1 %c1, label %loop1.latch, label %loop2202 203loop2:204 br i1 %c2, label %loop1.latch, label %loop2205 206loop1.latch:207 br i1 false, label %loop1, label %exit208 209exit:210 ret void211}212 213; Similar to @inner_loop_may_be_infinite, but the parent loop loop1 is marked214; as mustprogress. The loops can be removed.215define void @inner_loop_may_be_infinite_but_top_loop_mustprogress(i1 %c1, i1 %c2) {216; CHECK-LABEL: @inner_loop_may_be_infinite_but_top_loop_mustprogress(217; CHECK-NEXT: br label [[EXIT:%.*]]218; CHECK: exit:219; CHECK-NEXT: ret void220;221 br label %loop1222 223loop1:224 br i1 %c1, label %loop1.latch, label %loop2225 226loop2:227 br i1 %c2, label %loop1.latch, label %loop2228 229loop1.latch:230 br i1 false, label %loop1, label %exit, !llvm.loop !3231 232exit:233 ret void234}235 236; loop3 and loop1 are not marked as mustprogress, but loop2 (parent of loop3)237; is. The loops can be removed.238define void @loop2_mustprogress_but_not_child_loop_loop3(i1 %c1, i1 %c2, i1 %c3) {239; CHECK-LABEL: @loop2_mustprogress_but_not_child_loop_loop3(240; CHECK-NEXT: br label [[EXIT:%.*]]241; CHECK: exit:242; CHECK-NEXT: ret void243;244 br label %loop1245 246loop1:247 br i1 %c1, label %loop1.latch, label %loop2248 249loop2:250 br label %loop3251 252loop3:253 br i1 %c2, label %loop2.latch, label %loop3254 255loop2.latch:256 br i1 %c3, label %loop1.latch, label %loop2, !llvm.loop !3257 258loop1.latch:259 br i1 false, label %loop1, label %exit260 261exit:262 ret void263}264 265; Cannot remove loop3 or loop1, as they are not mustprogress. loop2 is266; mustprogress and can be removed.267define void @loop2_mustprogress_but_not_sibling_loop(i1 %c1, i1 %c2, i1 %c3) {268; CHECK-LABEL: @loop2_mustprogress_but_not_sibling_loop(269; CHECK-NEXT: br label [[LOOP1:%.*]]270; CHECK: loop1:271; CHECK-NEXT: br i1 [[C1:%.*]], label [[LOOP1_LATCH:%.*]], label [[LOOP2_PREHEADER:%.*]]272; CHECK: loop2.preheader:273; CHECK-NEXT: br label [[LOOP3_PREHEADER:%.*]]274; CHECK: loop3.preheader:275; CHECK-NEXT: br label [[LOOP3:%.*]]276; CHECK: loop3:277; CHECK-NEXT: br i1 [[C3:%.*]], label [[LOOP1_LATCH_LOOPEXIT:%.*]], label [[LOOP3]]278; CHECK: loop1.latch.loopexit:279; CHECK-NEXT: br label [[LOOP1_LATCH]]280; CHECK: loop1.latch:281; CHECK-NEXT: br label [[EXIT:%.*]]282; CHECK: exit:283; CHECK-NEXT: ret void284;285 br label %loop1286 287loop1:288 br i1 %c1, label %loop1.latch, label %loop2289 290loop2:291 br i1 %c2, label %loop3, label %loop2, !llvm.loop !4292 293loop3:294 br i1 %c3, label %loop1.latch, label %loop3295 296loop1.latch:297 br i1 false, label %loop1, label %exit298 299exit:300 ret void301}302 303define void @loop2_finite_but_child_is_not(i1 %c1, i1 %c2, i1 %c3) {304; CHECK-LABEL: @loop2_finite_but_child_is_not(305; CHECK-NEXT: entry:306; CHECK-NEXT: br label [[LOOP1:%.*]]307; CHECK: loop1:308; CHECK-NEXT: [[IV1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV1_NEXT:%.*]], [[LOOP1_LATCH:%.*]] ]309; CHECK-NEXT: br i1 [[C1:%.*]], label [[LOOP1_LATCH]], label [[LOOP2_PREHEADER:%.*]]310; CHECK: loop2.preheader:311; CHECK-NEXT: br label [[LOOP2:%.*]]312; CHECK: loop2:313; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[LOOP2_LATCH:%.*]] ], [ 0, [[LOOP2_PREHEADER]] ]314; CHECK-NEXT: br label [[LOOP3:%.*]]315; CHECK: loop3:316; CHECK-NEXT: br i1 [[C2:%.*]], label [[LOOP2_LATCH]], label [[LOOP3]]317; CHECK: loop2.latch:318; CHECK-NEXT: [[IV_NEXT]] = add nuw i32 [[IV]], 1319; CHECK-NEXT: [[C:%.*]] = icmp ugt i32 [[IV]], 200320; CHECK-NEXT: br i1 [[C]], label [[LOOP1_LATCH_LOOPEXIT:%.*]], label [[LOOP2]]321; CHECK: loop1.latch.loopexit:322; CHECK-NEXT: br label [[LOOP1_LATCH]]323; CHECK: loop1.latch:324; CHECK-NEXT: [[IV1_NEXT]] = add nuw i32 [[IV1]], 1325; CHECK-NEXT: [[C4:%.*]] = icmp ult i32 [[IV1_NEXT]], 200326; CHECK-NEXT: br i1 [[C4]], label [[LOOP1]], label [[EXIT:%.*]]327; CHECK: exit:328; CHECK-NEXT: ret void329;330entry:331 br label %loop1332 333loop1:334 %iv1 = phi i32 [ 0, %entry ], [ %iv1.next, %loop1.latch ]335 br i1 %c1, label %loop1.latch, label %loop2336 337loop2:338 %iv = phi i32 [ 0, %loop1 ], [ %iv.next, %loop2.latch ]339 br label %loop3340 341loop3:342 br i1 %c2, label %loop2.latch, label %loop3343 344loop2.latch:345 %iv.next = add nuw i32 %iv, 1346 %c = icmp ugt i32 %iv, 200347 br i1 %c, label %loop1.latch, label %loop2348 349loop1.latch:350 %iv1.next = add nuw i32 %iv1, 1351 %c4 = icmp ult i32 %iv1.next, 200352 br i1 %c4, label %loop1, label %exit353 354exit:355 ret void356}357 358define void @loop2_finite_and_child_is_mustprogress(i1 %c1, i1 %c2, i1 %c3) {359; CHECK-LABEL: @loop2_finite_and_child_is_mustprogress(360; CHECK-NEXT: entry:361; CHECK-NEXT: br label [[EXIT:%.*]]362; CHECK: exit:363; CHECK-NEXT: ret void364;365entry:366 br label %loop1367 368loop1:369 %iv1 = phi i32 [ 0, %entry ], [ %iv1.next, %loop1.latch ]370 br i1 %c1, label %loop1.latch, label %loop2371 372loop2:373 %iv = phi i32 [ 0, %loop1 ], [ %iv.next, %loop2.latch ]374 br label %loop3375 376loop3:377 br i1 %c2, label %loop2.latch, label %loop3, !llvm.loop !5378 379loop2.latch:380 %iv.next = add nuw i32 %iv, 1381 %c = icmp ugt i32 %iv, 200382 br i1 %c, label %loop1.latch, label %loop2383 384loop1.latch:385 %iv1.next = add nuw i32 %iv1, 1386 %c4 = icmp ult i32 %iv1.next, 200387 br i1 %c4, label %loop1, label %exit388 389exit:390 ret void391}392 393; Inner infinite loop hidden behind a call.394define void @not_willreturn() {395; CHECK-LABEL: @not_willreturn(396; CHECK-NEXT: entry:397; CHECK-NEXT: br label [[LOOP:%.*]]398; CHECK: loop:399; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]400; CHECK-NEXT: call void @sideeffect() #[[ATTR2:[0-9]+]]401; CHECK-NEXT: [[IV_NEXT]] = add nuw i32 [[IV]], 1402; CHECK-NEXT: [[C:%.*]] = icmp ult i32 [[IV]], 100403; CHECK-NEXT: br i1 [[C]], label [[LOOP]], label [[EXIT:%.*]]404; CHECK: exit:405; CHECK-NEXT: ret void406;407entry:408 br label %loop409 410loop:411 %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]412 call void @sideeffect() nounwind readonly413 %iv.next = add nuw i32 %iv, 1414 %c = icmp ult i32 %iv, 100415 br i1 %c, label %loop, label %exit416 417exit:418 ret void419}420 421!1 = !{!"llvm.loop.mustprogress"}422!2 = distinct !{!2, !1}423!3 = distinct !{!3, !1}424!4 = distinct !{!4, !1}425!5 = distinct !{!5, !1}426