test/Transforms/LoopUnroll/unloop.ll

   1 ; RUN: opt < %s -S -loop-unroll -verify-loop-info | FileCheck %s
   2 ; RUN: opt < %s -S -passes='require<opt-remark-emit>,unroll,verify<loops>' | FileCheck %s
   3 ;
   4 ; Unit tests for LoopInfo::markAsRemoved.
   5
   6 declare i1 @check() nounwind
   7
   8 ; Ensure that tail->inner is removed and rely on verify-loopinfo to
   9 ; check soundness.
  10 ;
  11 ; CHECK-LABEL: @skiplevelexit(
  12 ; CHECK: tail:
  13 ; CHECK-NOT: br
  14 ; CHECK: ret void
  15 define void @skiplevelexit() nounwind {
  16 entry:
  17   br label %outer
  18
  19 outer:
  20   br label %inner
  21
  22 inner:
  23   %iv = phi i32 [ 0, %outer ], [ %inc, %tail ]
  24   %inc = add i32 %iv, 1
  25   call zeroext i1 @check()
  26   br i1 true, label %outer.backedge, label %tail
  27
  28 tail:
  29   br i1 false, label %inner, label %exit
  30
  31 outer.backedge:
  32   br label %outer
  33
  34 exit:
  35   ret void
  36 }
  37
  38 ; Remove the middle loop of a triply nested loop tree.
  39 ; Ensure that only the middle loop is removed and rely on verify-loopinfo to
  40 ; check soundness.
  41 ;
  42 ; CHECK-LABEL: @unloopNested(
  43 ; Outer loop control.
  44 ; CHECK: while.body:
  45 ; CHECK: br i1 %cmp3, label %if.then, label %if.end
  46 ; Inner loop control.
  47 ; CHECK: while.end14.i:
  48 ; CHECK: br i1 %call15.i, label %if.end.i, label %exit
  49 ; Middle loop control should no longer reach %while.cond.
  50 ; Now it is the outer loop backedge.
  51 ; CHECK: exit:
  52 ; CHECK: br label %while.cond.outer
  53 define void @unloopNested() {
  54 entry:
  55   br label %while.cond.outer
  56
  57 while.cond.outer:
  58   br label %while.cond
  59
  60 while.cond:
  61   %cmp = call zeroext i1 @check()
  62   br i1 %cmp, label %while.body, label %while.end
  63
  64 while.body:
  65   %cmp3 = call zeroext i1 @check()
  66   br i1 %cmp3, label %if.then, label %if.end
  67
  68 if.then:
  69   br label %return
  70
  71 if.end:
  72   %cmp.i48 = call zeroext i1 @check()
  73   br i1 %cmp.i48, label %if.then.i, label %if.else20.i
  74
  75 if.then.i:
  76   %cmp8.i = call zeroext i1 @check()
  77   br i1 %cmp8.i, label %merge, label %if.else.i
  78
  79 if.else.i:
  80   br label %merge
  81
  82 if.else20.i:
  83   %cmp25.i = call zeroext i1 @check()
  84   br i1 %cmp25.i, label %merge, label %if.else28.i
  85
  86 if.else28.i:
  87   br label %merge
  88
  89 merge:
  90   br label %while.cond2.i
  91
  92 while.cond2.i:
  93   %cmp.i = call zeroext i1 @check()
  94   br i1 %cmp.i, label %while.cond2.backedge.i, label %while.end.i
  95
  96 while.cond2.backedge.i:
  97   br label %while.cond2.i
  98
  99 while.end.i:
 100   %cmp1114.i = call zeroext i1 @check()
 101   br i1 %cmp1114.i, label %while.body12.lr.ph.i, label %while.end14.i
 102
 103 while.body12.lr.ph.i:
 104   br label %while.end14.i
 105
 106 while.end14.i:
 107   %call15.i = call zeroext i1 @check()
 108   br i1 %call15.i, label %if.end.i, label %exit
 109
 110 if.end.i:
 111   br label %while.cond2.backedge.i
 112
 113 exit:
 114   br i1 false, label %while.cond, label %if.else
 115
 116 if.else:
 117   br label %while.cond.outer
 118
 119 while.end:
 120   br label %return
 121
 122 return:
 123   ret void
 124 }
 125
 126 ; Remove the middle loop of a deeply nested loop tree.
 127 ; Ensure that only the middle loop is removed and rely on verify-loopinfo to
 128 ; check soundness.
 129 ;
 130 ; This test must be disabled until trip count computation can be optimized...
 131 ; rdar:14038809 [SCEV]: Optimize trip count computation for multi-exit loops.
 132 ; CHECKFIXME-LABEL: @unloopDeepNested(
 133 ; Inner-inner loop control.
 134 ; CHECKFIXME: while.cond.us.i:
 135 ; CHECKFIXME: br i1 %cmp.us.i, label %next_data.exit, label %while.body.us.i
 136 ; CHECKFIXME: if.then.us.i:
 137 ; CHECKFIXME: br label %while.cond.us.i
 138 ; Inner loop tail.
 139 ; CHECKFIXME: if.else.i:
 140 ; CHECKFIXME: br label %while.cond.outer.i
 141 ; Middle loop control (removed).
 142 ; CHECKFIXME: valid_data.exit:
 143 ; CHECKFIXME-NOT: br
 144 ; CHECKFIXME: %cmp = call zeroext i1 @check()
 145 ; Outer loop control.
 146 ; CHECKFIXME: copy_data.exit:
 147 ; CHECKFIXME: br i1 %cmp38, label %if.then39, label %while.cond.outer
 148 ; Outer-outer loop tail.
 149 ; CHECKFIXME: while.cond.outer.outer.backedge:
 150 ; CHECKFIXME: br label %while.cond.outer.outer
 151 define void @unloopDeepNested() nounwind {
 152 for.cond8.preheader.i:
 153   %cmp113.i = call zeroext i1 @check()
 154   br i1 %cmp113.i, label %make_data.exit, label %for.body13.lr.ph.i
 155
 156 for.body13.lr.ph.i:
 157   br label %make_data.exit
 158
 159 make_data.exit:
 160   br label %while.cond.outer.outer
 161
 162 while.cond.outer.outer:
 163   br label %while.cond.outer
 164
 165 while.cond.outer:
 166   br label %while.cond
 167
 168 while.cond:
 169   br label %while.cond.outer.i
 170
 171 while.cond.outer.i:
 172   %tmp192.ph.i = call zeroext i1 @check()
 173   br i1 %tmp192.ph.i, label %while.cond.outer.split.us.i, label %while.body.loopexit
 174
 175 while.cond.outer.split.us.i:
 176   br label %while.cond.us.i
 177
 178 while.cond.us.i:
 179   %cmp.us.i = call zeroext i1 @check()
 180   br i1 %cmp.us.i, label %next_data.exit, label %while.body.us.i
 181
 182 while.body.us.i:
 183   %cmp7.us.i = call zeroext i1 @check()
 184   br i1 %cmp7.us.i, label %if.then.us.i, label %if.else.i
 185
 186 if.then.us.i:
 187   br label %while.cond.us.i
 188
 189 if.else.i:
 190   br label %while.cond.outer.i
 191
 192 next_data.exit:
 193   %tmp192.ph.i.lcssa28 = call zeroext i1 @check()
 194   br i1 %tmp192.ph.i.lcssa28, label %while.end, label %while.body
 195
 196 while.body.loopexit:
 197   br label %while.body
 198
 199 while.body:
 200   br label %while.cond.i
 201
 202 while.cond.i:
 203   %cmp.i = call zeroext i1 @check()
 204   br i1 %cmp.i, label %valid_data.exit, label %while.body.i
 205
 206 while.body.i:
 207   %cmp7.i = call zeroext i1 @check()
 208   br i1 %cmp7.i, label %valid_data.exit, label %if.end.i
 209
 210 if.end.i:
 211   br label %while.cond.i
 212
 213 valid_data.exit:
 214   br i1 true, label %if.then, label %while.cond
 215
 216 if.then:
 217   %cmp = call zeroext i1 @check()
 218   br i1 %cmp, label %if.then12, label %if.end
 219
 220 if.then12:
 221   br label %if.end
 222
 223 if.end:
 224   %tobool3.i = call zeroext i1 @check()
 225   br i1 %tobool3.i, label %copy_data.exit, label %while.body.lr.ph.i
 226
 227 while.body.lr.ph.i:
 228   br label %copy_data.exit
 229
 230 copy_data.exit:
 231   %cmp38 = call zeroext i1 @check()
 232   br i1 %cmp38, label %if.then39, label %while.cond.outer
 233
 234 if.then39:
 235   %cmp5.i = call zeroext i1 @check()
 236   br i1 %cmp5.i, label %while.cond.outer.outer.backedge, label %for.cond8.preheader.i8.thread
 237
 238 for.cond8.preheader.i8.thread:
 239   br label %while.cond.outer.outer.backedge
 240
 241 while.cond.outer.outer.backedge:
 242   br label %while.cond.outer.outer
 243
 244 while.end:
 245   ret void
 246 }
 247
 248 ; Remove a nested loop with irreducible control flow.
 249 ; Ensure that only the middle loop is removed and rely on verify-loopinfo to
 250 ; check soundness.
 251 ;
 252 ; CHECK-LABEL: @unloopIrreducible(
 253 ; Irreducible loop.
 254 ; CHECK: for.inc117:
 255 ; CHECK: br label %for.cond103t
 256 ; Nested loop (removed).
 257 ; CHECK: for.inc159:
 258 ; CHECK: br label %for.inc163
 259 define void @unloopIrreducible() nounwind {
 260
 261 entry:
 262   br label %for.body
 263
 264 for.body:
 265   %cmp2113 = call zeroext i1 @check()
 266   br i1 %cmp2113, label %for.body22.lr.ph, label %for.inc163
 267
 268 for.body22.lr.ph:
 269   br label %for.body22
 270
 271 for.body22:
 272   br label %for.body33
 273
 274 for.body33:
 275   br label %for.end
 276
 277 for.end:
 278   %cmp424 = call zeroext i1 @check()
 279   br i1 %cmp424, label %for.body43.lr.ph, label %for.end93
 280
 281 for.body43.lr.ph:
 282   br label %for.end93
 283
 284 for.end93:
 285   %cmp96 = call zeroext i1 @check()
 286   br i1 %cmp96, label %if.then97, label %for.cond103
 287
 288 if.then97:
 289   br label %for.cond103t
 290
 291 for.cond103t:
 292   br label %for.cond103
 293
 294 for.cond103:
 295   %cmp105 = call zeroext i1 @check()
 296   br i1 %cmp105, label %for.body106, label %for.end120
 297
 298 for.body106:
 299   %cmp108 = call zeroext i1 @check()
 300   br i1 %cmp108, label %if.then109, label %for.inc117
 301
 302 if.then109:
 303   br label %for.inc117
 304
 305 for.inc117:
 306   br label %for.cond103t
 307
 308 for.end120:
 309   br label %for.inc159
 310
 311 for.inc159:
 312   br i1 false, label %for.body22, label %for.cond15.for.inc163_crit_edge
 313
 314 for.cond15.for.inc163_crit_edge:
 315   br label %for.inc163
 316
 317 for.inc163:
 318   %cmp12 = call zeroext i1 @check()
 319   br i1 %cmp12, label %for.body, label %for.end166
 320
 321 for.end166:
 322   ret void
 323
 324 }
 325
 326 ; Remove a loop whose exit branches into a sibling loop.
 327 ; Ensure that only the loop is removed and rely on verify-loopinfo to
 328 ; check soundness.
 329 ;
 330 ; CHECK-LABEL: @unloopCriticalEdge(
 331 ; CHECK: while.cond.outer.i.loopexit.split:
 332 ; CHECK: br label %while.body
 333 ; CHECK: while.body:
 334 ; CHECK: br label %for.end78
 335 define void @unloopCriticalEdge() nounwind {
 336 entry:
 337   br label %for.cond31
 338
 339 for.cond31:
 340   br i1 undef, label %for.body35, label %for.end94
 341
 342 for.body35:
 343   br label %while.cond.i.preheader
 344
 345 while.cond.i.preheader:
 346   br i1 undef, label %while.cond.i.preheader.split, label %while.cond.outer.i.loopexit.split
 347
 348 while.cond.i.preheader.split:
 349   br label %while.cond.i
 350
 351 while.cond.i:
 352   br i1 true, label %while.cond.i, label %while.cond.outer.i.loopexit
 353
 354 while.cond.outer.i.loopexit:
 355   br label %while.cond.outer.i.loopexit.split
 356
 357 while.cond.outer.i.loopexit.split:
 358   br i1 false, label %while.cond.i.preheader, label %Func2.exit
 359
 360 Func2.exit:
 361   br label %while.body
 362
 363 while.body:
 364   br i1 false, label %while.body, label %while.end
 365
 366 while.end:
 367   br label %for.end78
 368
 369 for.end78:
 370   br i1 undef, label %Proc2.exit, label %for.cond.i.preheader
 371
 372 for.cond.i.preheader:
 373   br label %for.cond.i
 374
 375 for.cond.i:
 376   br label %for.cond.i
 377
 378 Proc2.exit:
 379   br label %for.cond31
 380
 381 for.end94:
 382   ret void
 383 }
 384
 385 ; Test UnloopUpdater::removeBlocksFromAncestors.
 386 ;
 387 ; Check that the loop backedge is removed from the middle loop 1699,
 388 ; but not the inner loop 1676.
 389 ; CHECK: while.body1694:
 390 ; CHECK:   unreachable
 391 ; CHECK: while.end1699:
 392 ; CHECK:   br label %sw.default1711
 393 define void @removeSubloopBlocks() nounwind {
 394 entry:
 395   br label %tryagain.outer
 396
 397 tryagain.outer:                                   ; preds = %sw.bb304, %entry
 398   br label %tryagain
 399
 400 tryagain:                                         ; preds = %while.end1699, %tryagain.outer
 401   br i1 undef, label %sw.bb1669, label %sw.bb304
 402
 403 sw.bb304:                                         ; preds = %tryagain
 404   br i1 undef, label %return, label %tryagain.outer
 405
 406 sw.bb1669:                                        ; preds = %tryagain
 407   br i1 undef, label %sw.default1711, label %while.cond1676
 408
 409 while.cond1676:                                   ; preds = %while.body1694, %sw.bb1669
 410   br i1 undef, label %while.end1699, label %while.body1694
 411
 412 while.body1694:                                   ; preds = %while.cond1676
 413   br label %while.cond1676
 414
 415 while.end1699:                                    ; preds = %while.cond1676
 416   br i1 false, label %tryagain, label %sw.default1711
 417
 418 sw.default1711:                                   ; preds = %while.end1699, %sw.bb1669, %tryagain
 419   br label %defchar
 420
 421 defchar:                                          ; preds = %sw.default1711, %sw.bb376
 422   br i1 undef, label %if.end2413, label %if.then2368
 423
 424 if.then2368:                                      ; preds = %defchar
 425   unreachable
 426
 427 if.end2413:                                       ; preds = %defchar
 428   unreachable
 429
 430 return:                                           ; preds = %sw.bb304
 431   ret void
 432 }
 433
 434 ; PR11335: the most deeply nested block should be removed from the outer loop.
 435 ; CHECK-LABEL: @removeSubloopBlocks2(
 436 ; CHECK: for.cond3:
 437 ; CHECK-NOT: br
 438 ; CHECK: ret void
 439 define void @removeSubloopBlocks2() nounwind {
 440 entry:
 441   %tobool.i = icmp ne i32 undef, 0
 442   br label %lbl_616
 443
 444 lbl_616.loopexit:                                 ; preds = %for.cond
 445   br label %lbl_616
 446
 447 lbl_616:                                          ; preds = %lbl_616.loopexit, %entry
 448   br label %for.cond
 449
 450 for.cond:                                         ; preds = %for.cond3, %lbl_616
 451   br i1 false, label %for.cond1.preheader, label %lbl_616.loopexit
 452
 453 for.cond1.preheader:                              ; preds = %for.cond
 454   br label %for.cond1
 455
 456 for.cond1.loopexit:                               ; preds = %for.cond.i
 457   br label %for.cond1
 458
 459 for.cond1:                                        ; preds = %for.cond1.loopexit, %for.cond1.preheader
 460   br i1 false, label %for.body2, label %for.cond3
 461
 462 for.body2:                                        ; preds = %for.cond1
 463   br label %for.cond.i
 464
 465 for.cond.i:                                       ; preds = %for.cond.i, %for.body2
 466   br i1 %tobool.i, label %for.cond.i, label %for.cond1.loopexit
 467
 468 for.cond3:                                        ; preds = %for.cond1
 469   br i1 false, label %for.cond, label %if.end
 470
 471 if.end:                                           ; preds = %for.cond3
 472   ret void
 473 }