test/Transforms/LoopDeletion/unreachable-loops.ll

   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 }