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

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