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