test/Transforms/LoopUnroll/unloop.ll

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