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. 8 define 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: 13 entry: 14 br i1 true, label %return, label %bb 15 16 bb: 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 24 return: 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. 30 define 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 36 entry: 37 br i1 true, label %return, label %bb 38 39 bb: 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 47 return: 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. 55 define 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 66 entry: 67 br i1 false, label %bb, label %return 68 69 bb: 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 75 bb2: 76 %t2 = icmp slt i64 %x.0, %m 77 %unused1 = udiv i64 42, %maybe_zero 78 br i1 %t2, label %bb3, label %return 79 80 bb3: 81 %t3 = icmp slt i64 %x.0, %m 82 %unused2 = sdiv i64 42, %maybe_zero 83 br i1 %t3, label %bb, label %return 84 85 return: 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. 92 define void @test4(i64 %n, i64 %m, i1 %cond) { 93 ; CHECK-LABEL: test4 94 ; CHECK-LABEL: bb: 95 entry: 96 br i1 %cond, label %looppred1, label %looppred2 97 98 looppred1: 99 br i1 true, label %return, label %bb 100 101 looppred2: 102 br i1 false, label %return, label %bb 103 104 bb: 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 112 return: 113 ret void 114 } 115 116 ; multiple constant conditional branches with loop not-taken in all cases. 117 define 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: 124 entry: 125 br i1 %cond, label %looppred1, label %looppred2 126 127 looppred1: 128 br i1 true, label %return, label %bb 129 130 looppred2: 131 br i1 true, label %return, label %bb 132 133 bb: 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 141 return: 142 ret void 143 } 144 145 ; Don't delete this infinite loop because the loop 146 ; is executable at runtime. 147 define 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: 152 entry: 153 br i1 true, label %bb, label %bb 154 155 bb: 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 163 return: 164 ret void 165 } 166 167 declare 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. 171 define 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 182 entry: 183 br label %L1 184 185 L1: 186 %y.next = phi i64 [ 0, %entry ], [ %y.add, %L1Latch ] 187 br i1 true, label %L1Latch, label %L2 188 189 L2: 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 196 L1Latch: 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 202 exit: 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. 210 define 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 216 entry: 217 br label %L1 218 219 L1: 220 br i1 true, label %exit, label %L2 221 222 L2: 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 229 exit: 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. 239 define 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 249 entry: 250 br label %L1 251 252 L1: 253 br i1 true, label %exit, label %L2 254 255 L2: 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 262 L3: 263 %cond2 = icmp slt i64 %y.L2, %n 264 br i1 %cond2, label %L3, label %L1 265 266 exit: 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. 275 define void @test10(i64 %n) { 276 ; CHECK-LABEL: test10 277 ; CHECK: L2: 278 ; CHECK: L3: 279 entry: 280 br label %L1 281 282 L1: 283 br i1 true, label %exit, label %L2 284 285 L2: 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 292 L3: 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 299 exit: 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. 308 define 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 314 entry: 315 br label %L1 316 317 L1: 318 br i1 true, label %exit, label %L2 319 320 L2: 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 327 L3: 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 333 exit: 334 ret void 335 } 336 337 338 ; 2 edges from a single exiting block to the exit block. 339 define 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 349 entry: 350 br i1 true, label %exit1, label %L1 351 352 exit1: 353 ret i64 42 354 355 L1: ; preds = %L1Latch, %entry 356 %y.next = phi i64 [ 0, %entry ], [ %y.add, %L1Latch ] 357 br i1 true, label %L1Latch, label %exit 358 359 L1Latch: ; 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 368 exit: ; 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 374 define 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 384 entry: 385 br i1 true, label %exit1, label %L1 386 387 exit1: 388 ret i64 42 389 390 L1: ; preds = %L1Latch, %entry 391 %y.next = phi i64 [ 0, %entry ], [ %y.add, %L1Latch ] 392 br i1 true, label %L1Block, label %exit 393 394 L1Block: ; 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 403 L1Latch: 404 switch i64 %n, label %L1 [ 405 i64 30, label %exit 406 i64 40, label %exit 407 ] 408 409 exit: ; 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
