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: @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   %wbucond = call zeroext i1 @check()
  25   br i1 %wbucond, 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: @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 ; CHECK: @unloopDeepNested
 130 ; Inner-inner loop control.
 131 ; CHECK: while.cond.us.i:
 132 ; CHECK: br i1 %cmp.us.i, label %next_data.exit, label %while.body.us.i
 133 ; CHECK: if.then.us.i:
 134 ; CHECK: br label %while.cond.us.i
 135 ; Inner loop tail.
 136 ; CHECK: if.else.i:
 137 ; CHECK: br label %while.cond.outer.i
 138 ; Middle loop control (removed).
 139 ; CHECK: valid_data.exit:
 140 ; CHECK-NOT: br
 141 ; CHECK: %cmp = call zeroext i1 @check()
 142 ; Outer loop control.
 143 ; CHECK: copy_data.exit:
 144 ; CHECK: br i1 %cmp38, label %if.then39, label %while.cond.outer
 145 ; Outer-outer loop tail.
 146 ; CHECK: while.cond.outer.outer.backedge:
 147 ; CHECK: br label %while.cond.outer.outer
 148 define void @unloopDeepNested() nounwind {
 149 for.cond8.preheader.i:
 150   %cmp113.i = call zeroext i1 @check()
 151   br i1 %cmp113.i, label %make_data.exit, label %for.body13.lr.ph.i
 152
 153 for.body13.lr.ph.i:
 154   br label %make_data.exit
 155
 156 make_data.exit:
 157   br label %while.cond.outer.outer
 158
 159 while.cond.outer.outer:
 160   br label %while.cond.outer
 161
 162 while.cond.outer:
 163   br label %while.cond
 164
 165 while.cond:
 166   br label %while.cond.outer.i
 167
 168 while.cond.outer.i:
 169   %tmp192.ph.i = call zeroext i1 @check()
 170   br i1 %tmp192.ph.i, label %while.cond.outer.split.us.i, label %while.body.loopexit
 171
 172 while.cond.outer.split.us.i:
 173   br label %while.cond.us.i
 174
 175 while.cond.us.i:
 176   %cmp.us.i = call zeroext i1 @check()
 177   br i1 %cmp.us.i, label %next_data.exit, label %while.body.us.i
 178
 179 while.body.us.i:
 180   %cmp7.us.i = call zeroext i1 @check()
 181   br i1 %cmp7.us.i, label %if.then.us.i, label %if.else.i
 182
 183 if.then.us.i:
 184   br label %while.cond.us.i
 185
 186 if.else.i:
 187   br label %while.cond.outer.i
 188
 189 next_data.exit:
 190   %tmp192.ph.i.lcssa28 = call zeroext i1 @check()
 191   br i1 %tmp192.ph.i.lcssa28, label %while.end, label %while.body
 192
 193 while.body.loopexit:
 194   br label %while.body
 195
 196 while.body:
 197   br label %while.cond.i
 198
 199 while.cond.i:
 200   %cmp.i = call zeroext i1 @check()
 201   br i1 %cmp.i, label %valid_data.exit, label %while.body.i
 202
 203 while.body.i:
 204   %cmp7.i = call zeroext i1 @check()
 205   br i1 %cmp7.i, label %valid_data.exit, label %if.end.i
 206
 207 if.end.i:
 208   br label %while.cond.i
 209
 210 valid_data.exit:
 211   br i1 true, label %if.then, label %while.cond
 212
 213 if.then:
 214   %cmp = call zeroext i1 @check()
 215   br i1 %cmp, label %if.then12, label %if.end
 216
 217 if.then12:
 218   br label %if.end
 219
 220 if.end:
 221   %tobool3.i = call zeroext i1 @check()
 222   br i1 %tobool3.i, label %copy_data.exit, label %while.body.lr.ph.i
 223
 224 while.body.lr.ph.i:
 225   br label %copy_data.exit
 226
 227 copy_data.exit:
 228   %cmp38 = call zeroext i1 @check()
 229   br i1 %cmp38, label %if.then39, label %while.cond.outer
 230
 231 if.then39:
 232   %cmp5.i = call zeroext i1 @check()
 233   br i1 %cmp5.i, label %while.cond.outer.outer.backedge, label %for.cond8.preheader.i8.thread
 234
 235 for.cond8.preheader.i8.thread:
 236   br label %while.cond.outer.outer.backedge
 237
 238 while.cond.outer.outer.backedge:
 239   br label %while.cond.outer.outer
 240
 241 while.end:
 242   ret void
 243 }
 244
 245 ; Remove a nested loop with irreducible control flow.
 246 ; Ensure that only the middle loop is removed and rely on verify-loopinfo to
 247 ; check soundness.
 248 ;
 249 ; CHECK: @unloopIrreducible
 250 ; Irreducible loop.
 251 ; CHECK: for.inc117:
 252 ; CHECK: br label %for.cond103t
 253 ; Nested loop (removed).
 254 ; CHECK: for.inc159:
 255 ; CHECK: br label %for.inc163
 256 define void @unloopIrreducible() nounwind {
 257
 258 entry:
 259   br label %for.body
 260
 261 for.body:
 262   %cmp2113 = call zeroext i1 @check()
 263   br i1 %cmp2113, label %for.body22.lr.ph, label %for.inc163
 264
 265 for.body22.lr.ph:
 266   br label %for.body22
 267
 268 for.body22:
 269   br label %for.body33
 270
 271 for.body33:
 272   br label %for.end
 273
 274 for.end:
 275   %cmp424 = call zeroext i1 @check()
 276   br i1 %cmp424, label %for.body43.lr.ph, label %for.end93
 277
 278 for.body43.lr.ph:
 279   br label %for.end93
 280
 281 for.end93:
 282   %cmp96 = call zeroext i1 @check()
 283   br i1 %cmp96, label %if.then97, label %for.cond103
 284
 285 if.then97:
 286   br label %for.cond103t
 287
 288 for.cond103t:
 289   br label %for.cond103
 290
 291 for.cond103:
 292   %cmp105 = call zeroext i1 @check()
 293   br i1 %cmp105, label %for.body106, label %for.end120
 294
 295 for.body106:
 296   %cmp108 = call zeroext i1 @check()
 297   br i1 %cmp108, label %if.then109, label %for.inc117
 298
 299 if.then109:
 300   br label %for.inc117
 301
 302 for.inc117:
 303   br label %for.cond103t
 304
 305 for.end120:
 306   br label %for.inc159
 307
 308 for.inc159:
 309   br i1 false, label %for.body22, label %for.cond15.for.inc163_crit_edge
 310
 311 for.cond15.for.inc163_crit_edge:
 312   br label %for.inc163
 313
 314 for.inc163:
 315   %cmp12 = call zeroext i1 @check()
 316   br i1 %cmp12, label %for.body, label %for.end166
 317
 318 for.end166:
 319   ret void
 320
 321 }
 322
 323 ; Remove a loop whose exit branches into a sibling loop.
 324 ; Ensure that only the loop is removed and rely on verify-loopinfo to
 325 ; check soundness.
 326 ;
 327 ; CHECK: @unloopCriticalEdge
 328 ; CHECK: while.cond.outer.i.loopexit.split:
 329 ; CHECK: br label %while.body
 330 ; CHECK: while.body:
 331 ; CHECK: br label %for.end78
 332 define void @unloopCriticalEdge() nounwind {
 333 entry:
 334   br label %for.cond31
 335
 336 for.cond31:
 337   br i1 undef, label %for.body35, label %for.end94
 338
 339 for.body35:
 340   br label %while.cond.i.preheader
 341
 342 while.cond.i.preheader:
 343   br i1 undef, label %while.cond.i.preheader.split, label %while.cond.outer.i.loopexit.split
 344
 345 while.cond.i.preheader.split:
 346   br label %while.cond.i
 347
 348 while.cond.i:
 349   br i1 true, label %while.cond.i, label %while.cond.outer.i.loopexit
 350
 351 while.cond.outer.i.loopexit:
 352   br label %while.cond.outer.i.loopexit.split
 353
 354 while.cond.outer.i.loopexit.split:
 355   br i1 false, label %while.cond.i.preheader, label %Func2.exit
 356
 357 Func2.exit:
 358   br label %while.body
 359
 360 while.body:
 361   br i1 false, label %while.body, label %while.end
 362
 363 while.end:
 364   br label %for.end78
 365
 366 for.end78:
 367   br i1 undef, label %Proc2.exit, label %for.cond.i.preheader
 368
 369 for.cond.i.preheader:
 370   br label %for.cond.i
 371
 372 for.cond.i:
 373   br label %for.cond.i
 374
 375 Proc2.exit:
 376   br label %for.cond31
 377
 378 for.end94:
 379   ret void
 380 }
 381
 382 ; Test UnloopUpdater::removeBlocksFromAncestors.
 383 ;
 384 ; Check that the loop backedge is removed from the middle loop 1699,
 385 ; but not the inner loop 1676.
 386 ; CHECK: while.body1694:
 387 ; CHECK:   br label %while.cond1676
 388 ; CHECK: while.end1699:
 389 ; CHECK:   br label %sw.default1711
 390 define void @removeSubloopBlocks() nounwind {
 391 entry:
 392   br label %tryagain.outer
 393
 394 tryagain.outer:                                   ; preds = %sw.bb304, %entry
 395   br label %tryagain
 396
 397 tryagain:                                         ; preds = %while.end1699, %tryagain.outer
 398   br i1 undef, label %sw.bb1669, label %sw.bb304
 399
 400 sw.bb304:                                         ; preds = %tryagain
 401   br i1 undef, label %return, label %tryagain.outer
 402
 403 sw.bb1669:                                        ; preds = %tryagain
 404   br i1 undef, label %sw.default1711, label %while.cond1676
 405
 406 while.cond1676:                                   ; preds = %while.body1694, %sw.bb1669
 407   br i1 undef, label %while.end1699, label %while.body1694
 408
 409 while.body1694:                                   ; preds = %while.cond1676
 410   br label %while.cond1676
 411
 412 while.end1699:                                    ; preds = %while.cond1676
 413   br i1 false, label %tryagain, label %sw.default1711
 414
 415 sw.default1711:                                   ; preds = %while.end1699, %sw.bb1669, %tryagain
 416   br label %defchar
 417
 418 defchar:                                          ; preds = %sw.default1711, %sw.bb376
 419   br i1 undef, label %if.end2413, label %if.then2368
 420
 421 if.then2368:                                      ; preds = %defchar
 422   unreachable
 423
 424 if.end2413:                                       ; preds = %defchar
 425   unreachable
 426
 427 return:                                           ; preds = %sw.bb304
 428   ret void
 429 }
 430
 431 ; PR11335: the most deeply nested block should be removed from the outer loop.
 432 ; CHECK: @removeSubloopBlocks2
 433 ; CHECK: for.cond3:
 434 ; CHECK-NOT: br
 435 ; CHECK: ret void
 436 define void @removeSubloopBlocks2() nounwind {
 437 entry:
 438   %tobool.i = icmp ne i32 undef, 0
 439   br label %lbl_616
 440
 441 lbl_616.loopexit:                                 ; preds = %for.cond
 442   br label %lbl_616
 443
 444 lbl_616:                                          ; preds = %lbl_616.loopexit, %entry
 445   br label %for.cond
 446
 447 for.cond:                                         ; preds = %for.cond3, %lbl_616
 448   br i1 false, label %for.cond1.preheader, label %lbl_616.loopexit
 449
 450 for.cond1.preheader:                              ; preds = %for.cond
 451   br label %for.cond1
 452
 453 for.cond1.loopexit:                               ; preds = %for.cond.i
 454   br label %for.cond1
 455
 456 for.cond1:                                        ; preds = %for.cond1.loopexit, %for.cond1.preheader
 457   br i1 false, label %for.body2, label %for.cond3
 458
 459 for.body2:                                        ; preds = %for.cond1
 460   br label %for.cond.i
 461
 462 for.cond.i:                                       ; preds = %for.cond.i, %for.body2
 463   br i1 %tobool.i, label %for.cond.i, label %for.cond1.loopexit
 464
 465 for.cond3:                                        ; preds = %for.cond1
 466   br i1 false, label %for.cond, label %if.end
 467
 468 if.end:                                           ; preds = %for.cond3
 469   ret void
 470 }