1; RUN: opt < %s -loop-deletion -verify-dom-info --pass-remarks-output=%t --pass-remarks-filter=loop-delete -S | FileCheck %s 2; RUN: cat %t | FileCheck %s --check-prefix=REMARKS 3 4; Checking that we can delete loops that are never executed. 5; We do not change the constant conditional branch statement (where the not-taken target 6; is the loop) to an unconditional one. 7 8; delete the infinite loop because it is never executed. 9define void @test1(i64 %n, i64 %m) nounwind { 10; CHECK-LABEL: test1 11; CHECK-LABEL: entry: 12; CHECK-NEXT: br i1 true, label %return, label %bb.preheader 13; CHECK-NOT: bb: 14; REMARKS-LABEL: Function: test1 15; REMARKS: Loop deleted because it never executes 16entry: 17 br i1 true, label %return, label %bb 18 19bb: 20 %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb ] 21 %t0 = add i64 %x.0, 1 22 %t1 = icmp slt i64 %x.0, %n 23 %t3 = icmp sgt i64 %x.0, %m 24 %t4 = and i1 %t1, %t3 25 br i1 true, label %bb, label %return 26 27return: 28 ret void 29} 30 31; FIXME: We can delete this infinite loop. Currently we do not, 32; because the infinite loop has no exit block. 33define void @test2(i64 %n, i64 %m) nounwind { 34; CHECK-LABEL: test2 35; CHECK-LABEL: entry: 36; CHECK-NEXT: br i1 true, label %return, label %bb.preheader 37; CHECK-LABEL: bb: 38; CHECK: br label %bb 39entry: 40 br i1 true, label %return, label %bb 41 42bb: 43 %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb ] 44 %t0 = add i64 %x.0, 1 45 %t1 = icmp slt i64 %x.0, %n 46 %t3 = icmp sgt i64 %x.0, %m 47 %t4 = and i1 %t1, %t3 48 br label %bb 49 50return: 51 ret void 52} 53 54; There are multiple exiting blocks and a single exit block. 55; Since it is a never executed loop, we do not care about the values 56; from different exiting paths and we can 57; delete the loop. 58define i64 @test3(i64 %n, i64 %m, i64 %maybe_zero) nounwind { 59 60; CHECK-NOT: bb: 61; CHECK-NOT: bb2: 62; CHECK-NOT: bb3: 63; CHECK-LABEL: return.loopexit: 64; CHECK-NEXT: %x.lcssa.ph = phi i64 [ undef, %bb.preheader ] 65; CHECK-NEXT: br label %return 66; CHECK-LABEL: return: 67; CHECK-NEXT: %x.lcssa = phi i64 [ 20, %entry ], [ %x.lcssa.ph, %return.loopexit ] 68; CHECK-NEXT: ret i64 %x.lcssa 69; REMARKS-LABEL: Function: test3 70; REMARKS: Loop deleted because it never executes 71entry: 72 br i1 false, label %bb, label %return 73 74bb: 75 %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb3 ] 76 %t0 = add i64 %x.0, 1 77 %t1 = icmp slt i64 %x.0, %n 78 br i1 %t1, label %bb2, label %return 79 80bb2: 81 %t2 = icmp slt i64 %x.0, %m 82 %unused1 = udiv i64 42, %maybe_zero 83 br i1 %t2, label %bb3, label %return 84 85bb3: 86 %t3 = icmp slt i64 %x.0, %m 87 %unused2 = sdiv i64 42, %maybe_zero 88 br i1 %t3, label %bb, label %return 89 90return: 91; the only valid value fo x.lcssa is 20. 92 %x.lcssa = phi i64 [ 12, %bb ], [ 14, %bb2 ], [ 16, %bb3 ], [20, %entry ] 93 ret i64 %x.lcssa 94} 95 96; Cannot delete the loop, since it may be executed at runtime. 97define void @test4(i64 %n, i64 %m, i1 %cond) { 98; CHECK-LABEL: test4 99; CHECK-LABEL: bb: 100entry: 101 br i1 %cond, label %looppred1, label %looppred2 102 103looppred1: 104 br i1 true, label %return, label %bb 105 106looppred2: 107 br i1 false, label %return, label %bb 108 109bb: 110 %x.0 = phi i64 [ 0, %looppred1 ], [ 1, %looppred2 ], [ %t0, %bb ] 111 %t0 = add i64 %x.0, 1 112 %t1 = icmp slt i64 %x.0, %n 113 %t3 = icmp sgt i64 %x.0, %m 114 %t4 = and i1 %t1, %t3 115 br i1 true, label %bb, label %return 116 117return: 118 ret void 119} 120 121; multiple constant conditional branches with loop not-taken in all cases. 122define void @test5(i64 %n, i64 %m, i1 %cond) nounwind { 123; CHECK-LABEL: test5 124; CHECK-LABEL: looppred1: 125; CHECK-NEXT: br i1 true, label %return, label %bb.preheader 126; CHECK-LABEL: looppred2: 127; CHECK-NEXT: br i1 true, label %return, label %bb.preheader 128; CHECK-NOT: bb: 129; REMARKS-LABEL: Function: test5 130; REMARKS: Loop deleted because it never executes 131entry: 132 br i1 %cond, label %looppred1, label %looppred2 133 134looppred1: 135 br i1 true, label %return, label %bb 136 137looppred2: 138 br i1 true, label %return, label %bb 139 140bb: 141 %x.0 = phi i64 [ 0, %looppred1 ], [ 1, %looppred2 ], [ %t0, %bb ] 142 %t0 = add i64 %x.0, 1 143 %t1 = icmp slt i64 %x.0, %n 144 %t3 = icmp sgt i64 %x.0, %m 145 %t4 = and i1 %t1, %t3 146 br i1 true, label %bb, label %return 147 148return: 149 ret void 150} 151 152; Don't delete this infinite loop because the loop 153; is executable at runtime. 154define void @test6(i64 %n, i64 %m) nounwind { 155; CHECK-LABEL: test6 156; CHECK-LABEL: entry: 157; CHECK-NEXT: br i1 true, label %bb.preheader, label %bb.preheader 158; CHECK: bb: 159entry: 160 br i1 true, label %bb, label %bb 161 162bb: 163 %x.0 = phi i64 [ 0, %entry ], [ 0, %entry ], [ %t0, %bb ] 164 %t0 = add i64 %x.0, 1 165 %t1 = icmp slt i64 %x.0, %n 166 %t3 = icmp sgt i64 %x.0, %m 167 %t4 = and i1 %t1, %t3 168 br i1 true, label %bb, label %return 169 170return: 171 ret void 172} 173 174declare i64 @foo(i64) 175; The loop L2 is never executed and is a subloop, with an 176; exit block that branches back to parent loop. 177; Here we can delete loop L2, while L1 still exists. 178define i64 @test7(i64 %n) { 179; CHECK-LABEL: test7 180; CHECK-LABEL: L1: 181; CHECK: br i1 true, label %L1Latch, label %L2.preheader 182; CHECK-LABEL: L2.preheader: 183; CHECK-NEXT: br label %L1Latch.loopexit 184; CHECK-LABEL: L1Latch.loopexit: 185; CHECK: br label %L1Latch 186; CHECK-LABEL: L1Latch: 187; CHECK-NEXT: %y = phi i64 [ %y.next, %L1 ], [ %y.L2.lcssa, %L1Latch.loopexit ] 188; CHECK: br i1 %cond2, label %exit, label %L1 189; REMARKS-LABEL: Function: test7 190; REMARKS: Loop deleted because it never executes 191entry: 192 br label %L1 193 194L1: 195 %y.next = phi i64 [ 0, %entry ], [ %y.add, %L1Latch ] 196 br i1 true, label %L1Latch, label %L2 197 198L2: 199 %x = phi i64 [ 0, %L1 ], [ %x.next, %L2 ] 200 %x.next = add i64 %x, 1 201 %y.L2 = call i64 @foo(i64 %x.next) 202 %cond = icmp slt i64 %x.next, %n 203 br i1 %cond, label %L2, label %L1Latch 204 205L1Latch: 206 %y = phi i64 [ %y.next, %L1 ], [ %y.L2, %L2 ] 207 %y.add = add i64 %y, %n 208 %cond2 = icmp eq i64 %y.add, 42 209 br i1 %cond2, label %exit, label %L1 210 211exit: 212 ret i64 %y.add 213} 214 215 216; Show recursive deletion of loops. Since we start with subloops and progress outward 217; to parent loop, we first delete the loop L2. Now loop L1 becomes a non-loop since it's backedge 218; from L2's preheader to L1's exit block is never taken. So, L1 gets deleted as well. 219define void @test8(i64 %n) { 220; CHECK-LABEL: test8 221; CHECK-LABEL: entry: 222; CHECK-NEXT: br label %exit 223; CHECK-LABEL: exit: 224; CHECK-NEXT: ret void 225; REMARKS-LABEL: Function: test8 226; REMARKS: Loop deleted because it never executes 227entry: 228 br label %L1 229 230L1: 231 br i1 true, label %exit, label %L2 232 233L2: 234 %x = phi i64 [ 0, %L1 ], [ %x.next, %L2 ] 235 %x.next = add i64 %x, 1 236 %y.L2 = call i64 @foo(i64 %x.next) 237 %cond = icmp slt i64 %x.next, %n 238 br i1 %cond, label %L2, label %L1 239 240exit: 241 ret void 242} 243 244 245; Delete a loop (L2) which has subloop (L3). 246; Here we delete loop L2, but leave L3 as is. 247; FIXME: Can delete L3 as well, by iteratively going backward through the single 248; predecessor of L3 until we reach L1's block that guarantees L3 is never 249; executed. 250define void @test9(i64 %n) { 251; CHECK-LABEL: test9 252; CHECK-LABEL: L2.preheader: 253; CHECK-NEXT: br label %L3.preheader 254; CHECK-NOT: L2: 255; CHECK-LABEL: L3.preheader: 256; CHECK-NEXT: %y.L2.lcssa = phi i64 [ undef, %L2.preheader ] 257; CHECK-NEXT: br label %L3 258; CHECK-LABEL: L3: 259; CHECK: br i1 %cond2, label %L3, label %L1.loopexit 260; REMARKS-LABEL: Function: test9 261; REMARKS: Loop deleted because it never executes 262entry: 263 br label %L1 264 265L1: 266 br i1 true, label %exit, label %L2 267 268L2: 269 %x = phi i64 [ 0, %L1 ], [ %x.next, %L2 ] 270 %x.next = add i64 %x, 1 271 %y.L2 = call i64 @foo(i64 %x.next) 272 %cond = icmp slt i64 %x.next, %n 273 br i1 %cond, label %L2, label %L3 274 275L3: 276 %cond2 = icmp slt i64 %y.L2, %n 277 br i1 %cond2, label %L3, label %L1 278 279exit: 280 ret void 281} 282 283; We cannot delete L3 because of call within it. 284; Since L3 is not deleted, and entirely contained within L2, L2 is also not 285; deleted. 286; FIXME: We can delete unexecutable loops having 287; subloops contained entirely within them. 288define void @test10(i64 %n) { 289; CHECK-LABEL: test10 290; CHECK: L2: 291; CHECK: L3: 292entry: 293 br label %L1 294 295L1: 296 br i1 true, label %exit, label %L2 297 298L2: 299 %x = phi i64 [ 0, %L1 ], [ %x.next, %L3 ] 300 %x.next = add i64 %x, 1 301 %y.L2 = call i64 @foo(i64 %x.next) 302 %cond = icmp slt i64 %x.next, %n 303 br i1 %cond, label %L1, label %L3 304 305L3: 306 %y.L3 = phi i64 [ %y.L2, %L2 ], [ %y.L3.next, %L3 ] 307 %y.L3.next = add i64 %y.L3, 1 308 %dummy = call i64 @foo(i64 %y.L3.next) 309 %cond2 = icmp slt i64 %y.L3, %n 310 br i1 %cond2, label %L3, label %L2 311 312exit: 313 ret void 314} 315 316; same as test10, but L3 does not contain call. 317; So, in the first iteration, all statements of L3 are made invariant, and L3 is 318; deleted. 319; In the next iteration, since L2 is never executed and has no subloops, we delete 320; L2 as well. Finally, the outermost loop L1 is deleted. 321define void @test11(i64 %n) { 322; CHECK-LABEL: test11 323; CHECK-LABEL: entry: 324; CHECK-NEXT: br label %exit 325; CHECK-LABEL: exit: 326; CHECK-NEXT: ret void 327; REMARKS-LABEL: Function: test11 328; REMARKS: Loop deleted because it is invariant 329; REMARKS-LABEL: Function: test11 330; REMARKS: Loop deleted because it never executes 331; REMARKS-LABEL: Function: test11 332; REMARKS: Loop deleted because it is invariant 333entry: 334 br label %L1 335 336L1: 337 br i1 true, label %exit, label %L2 338 339L2: 340 %x = phi i64 [ 0, %L1 ], [ %x.next, %L3 ] 341 %x.next = add i64 %x, 1 342 %y.L2 = call i64 @foo(i64 %x.next) 343 %cond = icmp slt i64 %x.next, %n 344 br i1 %cond, label %L1, label %L3 345 346L3: 347 %y.L3 = phi i64 [ %y.L2, %L2 ], [ %y.L3.next, %L3 ] 348 %y.L3.next = add i64 %y.L3, 1 349 %cond2 = icmp slt i64 %y.L3, %n 350 br i1 %cond2, label %L3, label %L2 351 352exit: 353 ret void 354} 355 356 357; 2 edges from a single exiting block to the exit block. 358define i64 @test12(i64 %n){ 359;CHECK-LABEL: @test12 360; CHECK-NOT: L1: 361; CHECK-NOT: L1Latch: 362; CHECK-LABEL: L1.preheader: 363; CHECK-NEXT: br label %exit 364; CHECK-LABEL: exit: 365; CHECK-NEXT: %y.phi = phi i64 [ undef, %L1.preheader ] 366; CHECK-NEXT: ret i64 %y.phi 367; REMARKS-LABEL: Function: test12 368; REMARKS: Loop deleted because it never executes 369 370entry: 371 br i1 true, label %exit1, label %L1 372 373exit1: 374 ret i64 42 375 376L1: ; preds = %L1Latch, %entry 377 %y.next = phi i64 [ 0, %entry ], [ %y.add, %L1Latch ] 378 br i1 true, label %L1Latch, label %exit 379 380L1Latch: ; preds = %L1 381 %y = phi i64 [ %y.next, %L1 ] 382 %y.add = add i64 %y, %n 383 %cond2 = icmp eq i64 %y.add, 42 384 switch i64 %n, label %L1 [ 385 i64 10, label %exit 386 i64 20, label %exit 387 ] 388 389exit: ; preds = %L1Latch, %L1Latch 390 %y.phi = phi i64 [ 10, %L1Latch ], [ 10, %L1Latch ], [ %y.next, %L1] 391 ret i64 %y.phi 392} 393 394; multiple edges to exit block from the same exiting blocks 395define i64 @test13(i64 %n) { 396; CHECK-LABEL: @test13 397; CHECK-NOT: L1: 398; CHECK-NOT: L1Latch: 399; CHECK-LABEL: L1.preheader: 400; CHECK-NEXT: br label %exit 401; CHECK-LABEL: exit: 402; CHECK-NEXT: %y.phi = phi i64 [ undef, %L1.preheader ] 403; CHECK-NEXT: ret i64 %y.phi 404; REMARKS-LABEL: Function: test13 405; REMARKS: Loop deleted because it never executes 406 407entry: 408 br i1 true, label %exit1, label %L1 409 410exit1: 411 ret i64 42 412 413L1: ; preds = %L1Latch, %entry 414 %y.next = phi i64 [ 0, %entry ], [ %y.add, %L1Latch ] 415 br i1 true, label %L1Block, label %exit 416 417L1Block: ; preds = %L1 418 %y = phi i64 [ %y.next, %L1 ] 419 %y.add = add i64 %y, %n 420 %cond2 = icmp eq i64 %y.add, 42 421 switch i64 %n, label %L1Latch [ 422 i64 10, label %exit 423 i64 20, label %exit 424 ] 425 426L1Latch: 427 switch i64 %n, label %L1 [ 428 i64 30, label %exit 429 i64 40, label %exit 430 ] 431 432exit: ; preds = %L1Block, %L1, %L1Latch 433 %y.phi = phi i64 [ 10, %L1Block ], [ 10, %L1Block ], [ %y.next, %L1 ], [ 30, %L1Latch ], [ 30, %L1Latch ] 434 ret i64 %y.phi 435} 436