llvm/test/Transforms/LoopDeletion/zero-btc.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -passes=loop-deletion -S | FileCheck %s
   3
   4 @G = external global i32
   5
   6 define void @test_trivial() {
   7 ; CHECK-LABEL: @test_trivial(
   8 ; CHECK-NEXT:  entry:
   9 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  10 ; CHECK:       loop:
  11 ; CHECK-NEXT:    store i32 0, ptr @G, align 4
  12 ; CHECK-NEXT:    br label [[EXIT:%.*]]
  13 ; CHECK:       exit:
  14 ; CHECK-NEXT:    ret void
  15 ;
  16 entry:
  17   br label %loop
  18
  19 loop:
  20   store i32 0, ptr @G
  21   br i1 false, label %loop, label %exit
  22
  23 exit:
  24   ret void
  25 }
  26
  27
  28 define void @test_bottom_tested() {
  29 ; CHECK-LABEL: @test_bottom_tested(
  30 ; CHECK-NEXT:  entry:
  31 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  32 ; CHECK:       loop:
  33 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
  34 ; CHECK-NEXT:    store i32 0, ptr @G, align 4
  35 ; CHECK-NEXT:    [[IV_INC:%.*]] = add i32 [[IV]], 1
  36 ; CHECK-NEXT:    [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 1
  37 ; CHECK-NEXT:    br label [[EXIT:%.*]]
  38 ; CHECK:       exit:
  39 ; CHECK-NEXT:    ret void
  40 ;
  41 entry:
  42   br label %loop
  43
  44 loop:
  45   %iv = phi i32 [ 0, %entry], [ %iv.inc, %loop ]
  46   store i32 0, ptr @G
  47   %iv.inc = add i32 %iv, 1
  48   %be_taken = icmp ne i32 %iv.inc, 1
  49   br i1 %be_taken, label %loop, label %exit
  50
  51 exit:
  52   ret void
  53 }
  54
  55 define void @test_early_exit() {
  56 ; CHECK-LABEL: @test_early_exit(
  57 ; CHECK-NEXT:  entry:
  58 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  59 ; CHECK:       loop:
  60 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
  61 ; CHECK-NEXT:    store i32 0, ptr @G, align 4
  62 ; CHECK-NEXT:    [[IV_INC:%.*]] = add i32 [[IV]], 1
  63 ; CHECK-NEXT:    [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 1
  64 ; CHECK-NEXT:    br i1 [[BE_TAKEN]], label [[LATCH:%.*]], label [[EXIT:%.*]]
  65 ; CHECK:       latch:
  66 ; CHECK-NEXT:    unreachable
  67 ; CHECK:       exit:
  68 ; CHECK-NEXT:    ret void
  69 ;
  70 entry:
  71   br label %loop
  72
  73 loop:
  74   %iv = phi i32 [ 0, %entry], [ %iv.inc, %latch ]
  75   store i32 0, ptr @G
  76   %iv.inc = add i32 %iv, 1
  77   %be_taken = icmp ne i32 %iv.inc, 1
  78   br i1 %be_taken, label %latch, label %exit
  79 latch:
  80   br label %loop
  81
  82 exit:
  83   ret void
  84 }
  85
  86 define void @test_multi_exit1() {
  87 ; CHECK-LABEL: @test_multi_exit1(
  88 ; CHECK-NEXT:  entry:
  89 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  90 ; CHECK:       loop:
  91 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
  92 ; CHECK-NEXT:    store i32 0, ptr @G, align 4
  93 ; CHECK-NEXT:    [[IV_INC:%.*]] = add i32 [[IV]], 1
  94 ; CHECK-NEXT:    [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 1
  95 ; CHECK-NEXT:    br i1 [[BE_TAKEN]], label [[LATCH:%.*]], label [[EXIT:%.*]]
  96 ; CHECK:       latch:
  97 ; CHECK-NEXT:    store i32 1, ptr @G, align 4
  98 ; CHECK-NEXT:    [[COND2:%.*]] = icmp ult i32 [[IV_INC]], 30
  99 ; CHECK-NEXT:    br label [[EXIT]]
 100 ; CHECK:       exit:
 101 ; CHECK-NEXT:    ret void
 102 ;
 103 entry:
 104   br label %loop
 105
 106 loop:
 107   %iv = phi i32 [ 0, %entry], [ %iv.inc, %latch ]
 108   store i32 0, ptr @G
 109   %iv.inc = add i32 %iv, 1
 110   %be_taken = icmp ne i32 %iv.inc, 1
 111   br i1 %be_taken, label %latch, label %exit
 112 latch:
 113   store i32 1, ptr @G
 114   %cond2 = icmp ult i32 %iv.inc, 30
 115   br i1 %cond2, label %loop, label %exit
 116
 117 exit:
 118   ret void
 119 }
 120
 121 define void @test_multi_exit2() {
 122 ; CHECK-LABEL: @test_multi_exit2(
 123 ; CHECK-NEXT:  entry:
 124 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 125 ; CHECK:       loop:
 126 ; CHECK-NEXT:    store i32 0, ptr @G, align 4
 127 ; CHECK-NEXT:    br i1 true, label [[LATCH:%.*]], label [[EXIT:%.*]]
 128 ; CHECK:       latch:
 129 ; CHECK-NEXT:    store i32 1, ptr @G, align 4
 130 ; CHECK-NEXT:    br label [[EXIT]]
 131 ; CHECK:       exit:
 132 ; CHECK-NEXT:    ret void
 133 ;
 134 entry:
 135   br label %loop
 136
 137 loop:
 138   store i32 0, ptr @G
 139   br i1 true, label %latch, label %exit
 140 latch:
 141   store i32 1, ptr @G
 142   br i1 false, label %loop, label %exit
 143
 144 exit:
 145   ret void
 146 }
 147
 148 define void @test_multi_exit3(i1 %cond1) {
 149 ; CHECK-LABEL: @test_multi_exit3(
 150 ; CHECK-NEXT:  entry:
 151 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 152 ; CHECK:       loop:
 153 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
 154 ; CHECK-NEXT:    store i32 0, ptr @G, align 4
 155 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LATCH:%.*]], label [[EXIT:%.*]]
 156 ; CHECK:       latch:
 157 ; CHECK-NEXT:    store i32 1, ptr @G, align 4
 158 ; CHECK-NEXT:    [[IV_INC:%.*]] = add i32 [[IV]], 1
 159 ; CHECK-NEXT:    [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 1
 160 ; CHECK-NEXT:    br label [[EXIT]]
 161 ; CHECK:       exit:
 162 ; CHECK-NEXT:    ret void
 163 ;
 164 entry:
 165   br label %loop
 166
 167 loop:
 168   %iv = phi i32 [ 0, %entry], [ %iv.inc, %latch ]
 169   store i32 0, ptr @G
 170   br i1 %cond1, label %latch, label %exit
 171 latch:
 172   store i32 1, ptr @G
 173   %iv.inc = add i32 %iv, 1
 174   %be_taken = icmp ne i32 %iv.inc, 1
 175   br i1 %be_taken, label %loop, label %exit
 176
 177 exit:
 178   ret void
 179 }
 180
 181 ; Subtle - This is either zero btc, or infinite, thus, can't break
 182 ; backedge
 183 define void @test_multi_exit4(i1 %cond1, i1 %cond2) {
 184 ; CHECK-LABEL: @test_multi_exit4(
 185 ; CHECK-NEXT:  entry:
 186 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 187 ; CHECK:       loop:
 188 ; CHECK-NEXT:    store i32 0, ptr @G, align 4
 189 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LATCH:%.*]], label [[EXIT:%.*]]
 190 ; CHECK:       latch:
 191 ; CHECK-NEXT:    store i32 1, ptr @G, align 4
 192 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP]], label [[EXIT]]
 193 ; CHECK:       exit:
 194 ; CHECK-NEXT:    ret void
 195 ;
 196 entry:
 197   br label %loop
 198
 199 loop:
 200   store i32 0, ptr @G
 201   br i1 %cond1, label %latch, label %exit
 202 latch:
 203   store i32 1, ptr @G
 204   br i1 %cond2, label %loop, label %exit
 205
 206 exit:
 207   ret void
 208 }
 209
 210 ; A simple case with multiple exit blocks
 211 define void @test_multi_exit5() {
 212 ; CHECK-LABEL: @test_multi_exit5(
 213 ; CHECK-NEXT:  entry:
 214 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 215 ; CHECK:       loop:
 216 ; CHECK-NEXT:    store i32 0, ptr @G, align 4
 217 ; CHECK-NEXT:    br i1 true, label [[LATCH:%.*]], label [[EXIT1:%.*]]
 218 ; CHECK:       latch:
 219 ; CHECK-NEXT:    store i32 1, ptr @G, align 4
 220 ; CHECK-NEXT:    br label [[EXIT2:%.*]]
 221 ; CHECK:       exit1:
 222 ; CHECK-NEXT:    ret void
 223 ; CHECK:       exit2:
 224 ; CHECK-NEXT:    ret void
 225 ;
 226 entry:
 227   br label %loop
 228
 229 loop:
 230   store i32 0, ptr @G
 231   br i1 true, label %latch, label %exit1
 232 latch:
 233   store i32 1, ptr @G
 234   br i1 false, label %loop, label %exit2
 235
 236 exit1:
 237   ret void
 238 exit2:
 239   ret void
 240 }
 241
 242 declare i1 @unknown()
 243
 244 ; We can't compute an exit count for the latch, but we know the upper
 245 ; bound on the trip count is zero anyways.
 246 define void @test_dead_latch1() {
 247 ; CHECK-LABEL: @test_dead_latch1(
 248 ; CHECK-NEXT:  entry:
 249 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 250 ; CHECK:       loop:
 251 ; CHECK-NEXT:    store i32 0, ptr @G, align 4
 252 ; CHECK-NEXT:    br i1 false, label [[LATCH:%.*]], label [[EXIT1:%.*]]
 253 ; CHECK:       latch:
 254 ; CHECK-NEXT:    [[LATCHCOND:%.*]] = call i1 @unknown()
 255 ; CHECK-NEXT:    br label [[EXIT2:%.*]]
 256 ; CHECK:       exit1:
 257 ; CHECK-NEXT:    ret void
 258 ; CHECK:       exit2:
 259 ; CHECK-NEXT:    ret void
 260 ;
 261 entry:
 262   br label %loop
 263
 264 loop:
 265   store i32 0, ptr @G
 266   br i1 false, label %latch, label %exit1
 267 latch:
 268   %latchcond = call i1 @unknown()
 269   br i1 %latchcond, label %loop, label %exit2
 270
 271 exit1:
 272   ret void
 273 exit2:
 274   ret void
 275 }
 276
 277
 278 define void @test_live_inner() {
 279 ; CHECK-LABEL: @test_live_inner(
 280 ; CHECK-NEXT:  entry:
 281 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 282 ; CHECK:       loop:
 283 ; CHECK-NEXT:    store i32 0, ptr @G, align 4
 284 ; CHECK-NEXT:    br label [[INNER:%.*]]
 285 ; CHECK:       inner:
 286 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[LOOP]] ], [ [[IV_INC:%.*]], [[INNER]] ]
 287 ; CHECK-NEXT:    store i32 [[IV]], ptr @G, align 4
 288 ; CHECK-NEXT:    [[IV_INC]] = add i32 [[IV]], 1
 289 ; CHECK-NEXT:    [[CND:%.*]] = icmp ult i32 [[IV_INC]], 200
 290 ; CHECK-NEXT:    br i1 [[CND]], label [[INNER]], label [[LATCH:%.*]]
 291 ; CHECK:       latch:
 292 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 293 ; CHECK:       exit:
 294 ; CHECK-NEXT:    ret void
 295 ;
 296 entry:
 297   br label %loop
 298
 299 loop:
 300   store i32 0, ptr @G
 301   br label %inner
 302
 303 inner:
 304   %iv = phi i32 [0, %loop], [%iv.inc, %inner]
 305   store i32 %iv, ptr @G
 306   %iv.inc = add i32 %iv, 1
 307   %cnd = icmp ult i32 %iv.inc, 200
 308   br i1 %cnd, label %inner, label %latch
 309
 310 latch:
 311   br i1 false, label %loop, label %exit
 312
 313 exit:
 314   ret void
 315 }
 316
 317 define void @test_live_outer() {
 318 ; CHECK-LABEL: @test_live_outer(
 319 ; CHECK-NEXT:  entry:
 320 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 321 ; CHECK:       loop:
 322 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_INC:%.*]], [[LATCH:%.*]] ]
 323 ; CHECK-NEXT:    br label [[INNER:%.*]]
 324 ; CHECK:       inner:
 325 ; CHECK-NEXT:    store i32 0, ptr @G, align 4
 326 ; CHECK-NEXT:    br label [[LATCH]]
 327 ; CHECK:       latch:
 328 ; CHECK-NEXT:    store i32 [[IV]], ptr @G, align 4
 329 ; CHECK-NEXT:    [[IV_INC]] = add i32 [[IV]], 1
 330 ; CHECK-NEXT:    [[CND:%.*]] = icmp ult i32 [[IV_INC]], 200
 331 ; CHECK-NEXT:    br i1 [[CND]], label [[LOOP]], label [[EXIT:%.*]]
 332 ; CHECK:       exit:
 333 ; CHECK-NEXT:    ret void
 334 ;
 335 entry:
 336   br label %loop
 337
 338 loop:
 339   %iv = phi i32 [0, %entry], [%iv.inc, %latch]
 340   br label %inner
 341
 342 inner:
 343   store i32 0, ptr @G
 344   br i1 false, label %inner, label %latch
 345
 346 latch:
 347   store i32 %iv, ptr @G
 348   %iv.inc = add i32 %iv, 1
 349   %cnd = icmp ult i32 %iv.inc, 200
 350   br i1 %cnd, label %loop, label %exit
 351
 352 exit:
 353   ret void
 354 }
 355
 356 ; Key point is that inner_latch drops out of the outer loop when
 357 ; the inner loop is deleted, and thus the lcssa phi needs to be
 358 ; in the inner_latch block to preserve LCSSA.  We either have to
 359 ; insert the LCSSA phi, or not break the inner backedge.
 360 define void @loop_nest_lcssa() {
 361 ; CHECK-LABEL: @loop_nest_lcssa(
 362 ; CHECK-NEXT:  entry:
 363 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 1, 2
 364 ; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
 365 ; CHECK:       outer_header:
 366 ; CHECK-NEXT:    br label [[INNER_HEADER:%.*]]
 367 ; CHECK:       inner_header:
 368 ; CHECK-NEXT:    br i1 false, label [[INNER_LATCH:%.*]], label [[OUTER_LATCH:%.*]]
 369 ; CHECK:       inner_latch:
 370 ; CHECK-NEXT:    [[DOTLCSSA:%.*]] = phi i32 [ [[TMP0]], [[INNER_HEADER]] ]
 371 ; CHECK-NEXT:    br label [[LOOPEXIT:%.*]]
 372 ; CHECK:       outer_latch:
 373 ; CHECK-NEXT:    br label [[OUTER_HEADER]]
 374 ; CHECK:       loopexit:
 375 ; CHECK-NEXT:    [[DOTLCSSA32:%.*]] = phi i32 [ [[DOTLCSSA]], [[INNER_LATCH]] ]
 376 ; CHECK-NEXT:    unreachable
 377 ;
 378 entry:
 379   br label %outer_header
 380
 381 outer_header:
 382   %0 = add i32 1, 2
 383   br label %inner_header
 384
 385 inner_header:
 386   br i1 false, label %inner_latch, label %outer_latch
 387
 388 inner_latch:
 389   br i1 false, label %inner_header, label %loopexit
 390
 391 outer_latch:
 392   br label %outer_header
 393
 394 loopexit:
 395   %.lcssa32 = phi i32 [ %0, %inner_latch ]
 396   unreachable
 397 }