1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt < %s -passes=loop-deletion -verify-dom-info -S | FileCheck %s 3 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 the 9; 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 void 16; 17entry: 18 br label %outer.header 19 20outer.header: 21 %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ] 22 23 br label %inner 24 25inner: 26 %inner.iv = phi i64 [ 0, %outer.header ], [ %inner.iv.next, %inner ] 27 %gep = getelementptr %pair_t, ptr %ptr, i64 %inner.iv 28 %p = load %pair_t, ptr %gep 29 %v.0 = extractvalue %pair_t %p, 0 30 %v.1 = extractvalue %pair_t %p, 1 31 %inner.ec = icmp ult i64 %v.0, %v.1 32 %inner.iv.next = add i64 %inner.iv, 1 33 br i1 %inner.ec, label %outer.latch, label %inner 34 35outer.latch: 36 %lcssa = phi i64 [ %v.1, %inner ] 37 %outer.ec = icmp ult i64 %outer.iv, %lcssa 38 %outer.iv.next = add i64 %outer.iv, 1 39 br i1 %outer.ec, label %exit, label %outer.header 40 41exit: 42 ret void 43} 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 4 59; CHECK-NEXT: [[V_0:%.*]] = extractvalue [[PAIR_T]] [[P]], 0 60; CHECK-NEXT: [[V_1:%.*]] = extractvalue [[PAIR_T]] [[P]], 1 61; CHECK-NEXT: [[INNER_EC:%.*]] = icmp ult i64 [[V_0]], [[V_1]] 62; CHECK-NEXT: [[INNER_IV_NEXT]] = add i64 [[INNER_IV]], 1 63; 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]], 1 68; CHECK-NEXT: call void @sideeffect() 69; CHECK-NEXT: br i1 [[OUTER_EC]], label [[EXIT:%.*]], label [[OUTER_HEADER]] 70; CHECK: exit: 71; CHECK-NEXT: ret void 72; 73entry: 74 br label %outer.header 75 76outer.header: 77 %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ] 78 79 br label %inner 80 81inner: 82 %inner.iv = phi i64 [ 0, %outer.header ], [ %inner.iv.next, %inner ] 83 %gep = getelementptr %pair_t, ptr %ptr, i64 %inner.iv 84 %p = load %pair_t, ptr %gep 85 %v.0 = extractvalue %pair_t %p, 0 86 %v.1 = extractvalue %pair_t %p, 1 87 %inner.ec = icmp ult i64 %v.0, %v.1 88 %inner.iv.next = add i64 %inner.iv, 1 89 br i1 %inner.ec, label %outer.latch, label %inner 90 91outer.latch: 92 %lcssa = phi i64 [ %v.1, %inner ] 93 %outer.ec = icmp ult i64 %outer.iv, %lcssa 94 %outer.iv.next = add i64 %outer.iv, 1 95 call void @sideeffect() 96 br i1 %outer.ec, label %exit, label %outer.header 97 98exit: 99 ret void 100} 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 4 114; CHECK-NEXT: [[V_0:%.*]] = extractvalue [[PAIR_T]] [[P]], 0 115; CHECK-NEXT: [[V_1:%.*]] = extractvalue [[PAIR_T]] [[P]], 1 116; CHECK-NEXT: [[INNER_EC:%.*]] = icmp ult i64 [[V_0]], [[V_1]] 117; CHECK-NEXT: [[INNER_IV_NEXT]] = add i64 [[INNER_IV]], 1 118; 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]], 1 124; CHECK-NEXT: br i1 [[OUTER_EC]], label [[EXIT:%.*]], label [[OUTER_HEADER]] 125; CHECK: exit: 126; CHECK-NEXT: ret void 127; 128entry: 129 br label %outer.header 130 131outer.header: 132 %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ] 133 134 br label %inner 135 136inner: 137 %inner.iv = phi i64 [ 0, %outer.header ], [ %inner.iv.next, %inner ] 138 %gep = getelementptr %pair_t, ptr %ptr, i64 %inner.iv 139 %p = load %pair_t, ptr %gep 140 %v.0 = extractvalue %pair_t %p, 0 141 %v.1 = extractvalue %pair_t %p, 1 142 %inner.ec = icmp ult i64 %v.0, %v.1 143 %inner.iv.next = add i64 %inner.iv, 1 144 call void @sideeffect() 145 br i1 %inner.ec, label %outer.latch, label %inner 146 147outer.latch: 148 %lcssa = phi i64 [ %v.1, %inner ] 149 %outer.ec = icmp ult i64 %outer.iv, %lcssa 150 %outer.iv.next = add i64 %outer.iv, 1 151 br i1 %outer.ec, label %exit, label %outer.header 152 153exit: 154 ret void 155} 156 157; The inner loop may not terminate, so we cannot remove it, unless the 158; 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 void 174; 175 br label %loop1 176 177loop1: 178 br i1 %c1, label %loop1.latch, label %loop2 179 180loop2: 181 br i1 %c2, label %loop1.latch, label %loop2 182 183loop1.latch: 184 br i1 false, label %loop1, label %exit 185 186exit: 187 ret void 188} 189 190; Similar to @inner_loop_may_be_infinite, but the function is marked as 191; 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 void 197; 198 br label %loop1 199 200loop1: 201 br i1 %c1, label %loop1.latch, label %loop2 202 203loop2: 204 br i1 %c2, label %loop1.latch, label %loop2 205 206loop1.latch: 207 br i1 false, label %loop1, label %exit 208 209exit: 210 ret void 211} 212 213; Similar to @inner_loop_may_be_infinite, but the parent loop loop1 is marked 214; 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 void 220; 221 br label %loop1 222 223loop1: 224 br i1 %c1, label %loop1.latch, label %loop2 225 226loop2: 227 br i1 %c2, label %loop1.latch, label %loop2 228 229loop1.latch: 230 br i1 false, label %loop1, label %exit, !llvm.loop !3 231 232exit: 233 ret void 234} 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 void 243; 244 br label %loop1 245 246loop1: 247 br i1 %c1, label %loop1.latch, label %loop2 248 249loop2: 250 br label %loop3 251 252loop3: 253 br i1 %c2, label %loop2.latch, label %loop3 254 255loop2.latch: 256 br i1 %c3, label %loop1.latch, label %loop2, !llvm.loop !3 257 258loop1.latch: 259 br i1 false, label %loop1, label %exit 260 261exit: 262 ret void 263} 264 265; Cannot remove loop3 or loop1, as they are not mustprogress. loop2 is 266; 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 void 284; 285 br label %loop1 286 287loop1: 288 br i1 %c1, label %loop1.latch, label %loop2 289 290loop2: 291 br i1 %c2, label %loop3, label %loop2, !llvm.loop !4 292 293loop3: 294 br i1 %c3, label %loop1.latch, label %loop3 295 296loop1.latch: 297 br i1 false, label %loop1, label %exit 298 299exit: 300 ret void 301} 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]], 1 319; CHECK-NEXT: [[C:%.*]] = icmp ugt i32 [[IV]], 200 320; 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]], 1 325; CHECK-NEXT: [[C4:%.*]] = icmp ult i32 [[IV1_NEXT]], 200 326; CHECK-NEXT: br i1 [[C4]], label [[LOOP1]], label [[EXIT:%.*]] 327; CHECK: exit: 328; CHECK-NEXT: ret void 329; 330entry: 331 br label %loop1 332 333loop1: 334 %iv1 = phi i32 [ 0, %entry ], [ %iv1.next, %loop1.latch ] 335 br i1 %c1, label %loop1.latch, label %loop2 336 337loop2: 338 %iv = phi i32 [ 0, %loop1 ], [ %iv.next, %loop2.latch ] 339 br label %loop3 340 341loop3: 342 br i1 %c2, label %loop2.latch, label %loop3 343 344loop2.latch: 345 %iv.next = add nuw i32 %iv, 1 346 %c = icmp ugt i32 %iv, 200 347 br i1 %c, label %loop1.latch, label %loop2 348 349loop1.latch: 350 %iv1.next = add nuw i32 %iv1, 1 351 %c4 = icmp ult i32 %iv1.next, 200 352 br i1 %c4, label %loop1, label %exit 353 354exit: 355 ret void 356} 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 void 364; 365entry: 366 br label %loop1 367 368loop1: 369 %iv1 = phi i32 [ 0, %entry ], [ %iv1.next, %loop1.latch ] 370 br i1 %c1, label %loop1.latch, label %loop2 371 372loop2: 373 %iv = phi i32 [ 0, %loop1 ], [ %iv.next, %loop2.latch ] 374 br label %loop3 375 376loop3: 377 br i1 %c2, label %loop2.latch, label %loop3, !llvm.loop !5 378 379loop2.latch: 380 %iv.next = add nuw i32 %iv, 1 381 %c = icmp ugt i32 %iv, 200 382 br i1 %c, label %loop1.latch, label %loop2 383 384loop1.latch: 385 %iv1.next = add nuw i32 %iv1, 1 386 %c4 = icmp ult i32 %iv1.next, 200 387 br i1 %c4, label %loop1, label %exit 388 389exit: 390 ret void 391} 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]], 1 402; CHECK-NEXT: [[C:%.*]] = icmp ult i32 [[IV]], 100 403; CHECK-NEXT: br i1 [[C]], label [[LOOP]], label [[EXIT:%.*]] 404; CHECK: exit: 405; CHECK-NEXT: ret void 406; 407entry: 408 br label %loop 409 410loop: 411 %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ] 412 call void @sideeffect() nounwind readonly 413 %iv.next = add nuw i32 %iv, 1 414 %c = icmp ult i32 %iv, 100 415 br i1 %c, label %loop, label %exit 416 417exit: 418 ret void 419} 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