llvm/test/Transforms/FixIrreducible/nested.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -fix-irreducible -S | FileCheck %s -check-prefix=CHECK
   3
   4 define void @nested_irr_top_level(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5) {
   5 ; CHECK-LABEL: @nested_irr_top_level(
   6 ; CHECK-NEXT:  entry:
   7 ; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
   8 ; CHECK:       A1:
   9 ; CHECK-NEXT:    br label [[IRR_GUARD1:%.*]]
  10 ; CHECK:       B1:
  11 ; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD1]], label [[A3:%.*]]
  12 ; CHECK:       B2:
  13 ; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[IRR_GUARD1]], label [[A3]]
  14 ; CHECK:       A3:
  15 ; CHECK-NEXT:    br i1 [[PRED4:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
  16 ; CHECK:       A2:
  17 ; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[IRR_GUARD]], label [[EXIT]]
  18 ; CHECK:       exit:
  19 ; CHECK-NEXT:    ret void
  20 ; CHECK:       irr.guard:
  21 ; CHECK-NEXT:    [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED0:%.*]], [[ENTRY:%.*]] ], [ false, [[A3]] ]
  22 ; CHECK-NEXT:    br i1 [[GUARD_A1]], label [[A1:%.*]], label [[A2]]
  23 ; CHECK:       irr.guard1:
  24 ; CHECK-NEXT:    [[GUARD_B1:%.*]] = phi i1 [ true, [[B2:%.*]] ], [ [[PRED1:%.*]], [[A1]] ], [ false, [[B1:%.*]] ]
  25 ; CHECK-NEXT:    br i1 [[GUARD_B1]], label [[B1]], label [[B2]]
  26 ;
  27 entry:
  28   br i1 %Pred0, label %A1, label %A2
  29
  30 A1:
  31   br i1 %Pred1, label %B1, label %B2
  32
  33 B1:
  34   br i1 %Pred2, label %B2, label %A3
  35
  36 B2:
  37   br i1 %Pred3, label %B1, label %A3
  38
  39 A3:
  40   br i1 %Pred4, label %A2, label %exit
  41
  42 A2:
  43   br i1 %Pred5, label %A1, label %exit
  44
  45 exit:
  46   ret void
  47 }
  48
  49 define void @nested_irr_in_loop(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6) {
  50 ; CHECK-LABEL: @nested_irr_in_loop(
  51 ; CHECK-NEXT:  entry:
  52 ; CHECK-NEXT:    br label [[H1:%.*]]
  53 ; CHECK:       H1:
  54 ; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
  55 ; CHECK:       A1:
  56 ; CHECK-NEXT:    br label [[IRR_GUARD1:%.*]]
  57 ; CHECK:       B1:
  58 ; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD1]], label [[A3:%.*]]
  59 ; CHECK:       B2:
  60 ; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[IRR_GUARD1]], label [[A3]]
  61 ; CHECK:       A3:
  62 ; CHECK-NEXT:    br i1 [[PRED4:%.*]], label [[IRR_GUARD]], label [[L1:%.*]]
  63 ; CHECK:       A2:
  64 ; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[IRR_GUARD]], label [[L1]]
  65 ; CHECK:       L1:
  66 ; CHECK-NEXT:    br i1 [[PRED6:%.*]], label [[EXIT:%.*]], label [[H1]]
  67 ; CHECK:       exit:
  68 ; CHECK-NEXT:    ret void
  69 ; CHECK:       irr.guard:
  70 ; CHECK-NEXT:    [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED0:%.*]], [[H1]] ], [ false, [[A3]] ]
  71 ; CHECK-NEXT:    br i1 [[GUARD_A1]], label [[A1:%.*]], label [[A2]]
  72 ; CHECK:       irr.guard1:
  73 ; CHECK-NEXT:    [[GUARD_B1:%.*]] = phi i1 [ true, [[B2:%.*]] ], [ [[PRED1:%.*]], [[A1]] ], [ false, [[B1:%.*]] ]
  74 ; CHECK-NEXT:    br i1 [[GUARD_B1]], label [[B1]], label [[B2]]
  75 ;
  76 entry:
  77   br label %H1
  78
  79 H1:
  80   br i1 %Pred0, label %A1, label %A2
  81
  82 A1:
  83   br i1 %Pred1, label %B1, label %B2
  84
  85 B1:
  86   br i1 %Pred2, label %B2, label %A3
  87
  88 B2:
  89   br i1 %Pred3, label %B1, label %A3
  90
  91 A3:
  92   br i1 %Pred4, label %A2, label %L1
  93
  94 A2:
  95   br i1 %Pred5, label %A1, label %L1
  96
  97 L1:
  98   br i1 %Pred6, label %exit, label %H1
  99
 100 exit:
 101   ret void
 102 }
 103
 104 define void @loop_in_irr(i1 %Pred0, i1 %Pred1, i1 %Pred2) {
 105 ; CHECK-LABEL: @loop_in_irr(
 106 ; CHECK-NEXT:  entry:
 107 ; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
 108 ; CHECK:       A1:
 109 ; CHECK-NEXT:    br label [[H1:%.*]]
 110 ; CHECK:       H1:
 111 ; CHECK-NEXT:    br label [[L1:%.*]]
 112 ; CHECK:       L1:
 113 ; CHECK-NEXT:    br i1 [[PRED1:%.*]], label [[H1]], label [[A3:%.*]]
 114 ; CHECK:       A3:
 115 ; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
 116 ; CHECK:       A2:
 117 ; CHECK-NEXT:    br label [[IRR_GUARD]]
 118 ; CHECK:       exit:
 119 ; CHECK-NEXT:    ret void
 120 ; CHECK:       irr.guard:
 121 ; CHECK-NEXT:    [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED0:%.*]], [[ENTRY:%.*]] ], [ false, [[A3]] ]
 122 ; CHECK-NEXT:    br i1 [[GUARD_A1]], label [[A1:%.*]], label [[A2]]
 123 ;
 124 entry:
 125   br i1 %Pred0, label %A1, label %A2
 126
 127 A1:
 128   br label %H1
 129
 130 H1:
 131   br label %L1
 132
 133 L1:
 134   br i1 %Pred1, label %H1, label %A3
 135
 136 A3:
 137   br i1 %Pred2, label %A2, label %exit
 138
 139 A2:
 140   br label %A1
 141
 142 exit:
 143   ret void
 144 }
 145
 146 define void @loop_in_irr_shared_header(i1 %Pred0, i1 %Pred1, i1 %Pred2) {
 147 ; CHECK-LABEL: @loop_in_irr_shared_header(
 148 ; CHECK-NEXT:  entry:
 149 ; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
 150 ; CHECK:       H1:
 151 ; CHECK-NEXT:    br label [[L1:%.*]]
 152 ; CHECK:       L1:
 153 ; CHECK-NEXT:    br i1 [[PRED1:%.*]], label [[IRR_GUARD]], label [[A3:%.*]]
 154 ; CHECK:       A3:
 155 ; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
 156 ; CHECK:       A2:
 157 ; CHECK-NEXT:    br label [[IRR_GUARD]]
 158 ; CHECK:       exit:
 159 ; CHECK-NEXT:    ret void
 160 ; CHECK:       irr.guard:
 161 ; CHECK-NEXT:    [[GUARD_H1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ true, [[L1]] ], [ [[PRED0:%.*]], [[ENTRY:%.*]] ], [ false, [[A3]] ]
 162 ; CHECK-NEXT:    br i1 [[GUARD_H1]], label [[H1:%.*]], label [[A2]]
 163 ;
 164 entry:
 165   br i1 %Pred0, label %H1, label %A2
 166
 167 H1:
 168   br label %L1
 169
 170 L1:
 171   br i1 %Pred1, label %H1, label %A3
 172
 173 A3:
 174   br i1 %Pred2, label %A2, label %exit
 175
 176 A2:
 177   br label %H1
 178
 179 exit:
 180   ret void
 181 }
 182
 183 define void @siblings_top_level(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6) {
 184 ; CHECK-LABEL: @siblings_top_level(
 185 ; CHECK-NEXT:  entry:
 186 ; CHECK-NEXT:    br i1 [[PRED0:%.*]], label [[H1:%.*]], label [[FORK1:%.*]]
 187 ; CHECK:       H1:
 188 ; CHECK-NEXT:    br label [[IRR_GUARD1:%.*]]
 189 ; CHECK:       A1:
 190 ; CHECK-NEXT:    br label [[IRR_GUARD1]]
 191 ; CHECK:       A2:
 192 ; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD1]], label [[L1:%.*]]
 193 ; CHECK:       L1:
 194 ; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[H1]], label [[EXIT:%.*]]
 195 ; CHECK:       fork1:
 196 ; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
 197 ; CHECK:       B1:
 198 ; CHECK-NEXT:    br label [[H2:%.*]]
 199 ; CHECK:       H2:
 200 ; CHECK-NEXT:    br label [[L2:%.*]]
 201 ; CHECK:       L2:
 202 ; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[H2]], label [[IRR_GUARD]]
 203 ; CHECK:       B2:
 204 ; CHECK-NEXT:    br i1 [[PRED6:%.*]], label [[IRR_GUARD]], label [[EXIT]]
 205 ; CHECK:       exit:
 206 ; CHECK-NEXT:    ret void
 207 ; CHECK:       irr.guard:
 208 ; CHECK-NEXT:    [[GUARD_B1:%.*]] = phi i1 [ true, [[B2:%.*]] ], [ [[PRED4:%.*]], [[FORK1]] ], [ false, [[L2]] ]
 209 ; CHECK-NEXT:    br i1 [[GUARD_B1]], label [[B1:%.*]], label [[B2]]
 210 ; CHECK:       irr.guard1:
 211 ; CHECK-NEXT:    [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED1:%.*]], [[H1]] ], [ false, [[A1:%.*]] ]
 212 ; CHECK-NEXT:    br i1 [[GUARD_A1]], label [[A1]], label [[A2]]
 213 ;
 214 entry:
 215   br i1 %Pred0, label %H1, label %fork1
 216
 217 H1:
 218   br i1 %Pred1, label %A1, label %A2
 219
 220 A1:
 221   br label %A2
 222
 223 A2:
 224   br i1 %Pred2, label %A1, label %L1
 225
 226 L1:
 227   br i1 %Pred3, label %H1, label %exit
 228
 229 fork1:
 230   br i1 %Pred4, label %B1, label %B2
 231
 232 B1:
 233   br label %H2
 234
 235 H2:
 236   br label %L2
 237
 238 L2:
 239   br i1 %Pred5, label %H2, label %B2
 240
 241 B2:
 242   br i1 %Pred6, label %B1, label %exit
 243
 244 exit:
 245   ret void
 246 }
 247
 248 define void @siblings_in_loop(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6, i1 %Pred7) {
 249 ; CHECK-LABEL: @siblings_in_loop(
 250 ; CHECK-NEXT:  entry:
 251 ; CHECK-NEXT:    br label [[H0:%.*]]
 252 ; CHECK:       H0:
 253 ; CHECK-NEXT:    br i1 [[PRED0:%.*]], label [[H1:%.*]], label [[FORK1:%.*]]
 254 ; CHECK:       H1:
 255 ; CHECK-NEXT:    br label [[IRR_GUARD1:%.*]]
 256 ; CHECK:       A1:
 257 ; CHECK-NEXT:    br label [[IRR_GUARD1]]
 258 ; CHECK:       A2:
 259 ; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD1]], label [[L1:%.*]]
 260 ; CHECK:       L1:
 261 ; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[H1]], label [[L0:%.*]]
 262 ; CHECK:       fork1:
 263 ; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
 264 ; CHECK:       B1:
 265 ; CHECK-NEXT:    br label [[H2:%.*]]
 266 ; CHECK:       H2:
 267 ; CHECK-NEXT:    br label [[L2:%.*]]
 268 ; CHECK:       L2:
 269 ; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[H2]], label [[IRR_GUARD]]
 270 ; CHECK:       B2:
 271 ; CHECK-NEXT:    br i1 [[PRED6:%.*]], label [[IRR_GUARD]], label [[L0]]
 272 ; CHECK:       L0:
 273 ; CHECK-NEXT:    br i1 [[PRED7:%.*]], label [[EXIT:%.*]], label [[H0]]
 274 ; CHECK:       exit:
 275 ; CHECK-NEXT:    ret void
 276 ; CHECK:       irr.guard:
 277 ; CHECK-NEXT:    [[GUARD_B1:%.*]] = phi i1 [ true, [[B2:%.*]] ], [ [[PRED4:%.*]], [[FORK1]] ], [ false, [[L2]] ]
 278 ; CHECK-NEXT:    br i1 [[GUARD_B1]], label [[B1:%.*]], label [[B2]]
 279 ; CHECK:       irr.guard1:
 280 ; CHECK-NEXT:    [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED1:%.*]], [[H1]] ], [ false, [[A1:%.*]] ]
 281 ; CHECK-NEXT:    br i1 [[GUARD_A1]], label [[A1]], label [[A2]]
 282 ;
 283 entry:
 284   br label %H0
 285
 286 H0:
 287   br i1 %Pred0, label %H1, label %fork1
 288
 289 H1:
 290   br i1 %Pred1, label %A1, label %A2
 291
 292 A1:
 293   br label %A2
 294
 295 A2:
 296   br i1 %Pred2, label %A1, label %L1
 297
 298 L1:
 299   br i1 %Pred3, label %H1, label %L0
 300
 301 fork1:
 302   br i1 %Pred4, label %B1, label %B2
 303
 304 B1:
 305   br label %H2
 306
 307 H2:
 308   br label %L2
 309
 310 L2:
 311   br i1 %Pred5, label %H2, label %B2
 312
 313 B2:
 314   br i1 %Pred6, label %B1, label %L0
 315
 316 L0:
 317   br i1 %Pred7, label %exit, label %H0
 318
 319 exit:
 320   ret void
 321 }
 322
 323 define void @irreducible_mountain_bug(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6, i1 %Pred7, i1 %Pred8, i1 %Pred9, i1 %Pred10, i1 %Pred11, i1 %Pred12, i1 %Pred13) {
 324 ; CHECK-LABEL: @irreducible_mountain_bug(
 325 ; CHECK-NEXT:  entry:
 326 ; CHECK-NEXT:    br i1 [[PRED0:%.*]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
 327 ; CHECK:       if.end:
 328 ; CHECK-NEXT:    br i1 [[PRED1:%.*]], label [[IF_THEN7:%.*]], label [[IF_ELSE:%.*]]
 329 ; CHECK:       if.then7:
 330 ; CHECK-NEXT:    br label [[IF_END16:%.*]]
 331 ; CHECK:       if.else:
 332 ; CHECK-NEXT:    br label [[IF_END16]]
 333 ; CHECK:       if.end16:
 334 ; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[WHILE_COND_PREHEADER:%.*]], label [[IF_THEN39:%.*]]
 335 ; CHECK:       while.cond.preheader:
 336 ; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
 337 ; CHECK:       while.cond:
 338 ; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[IRR_GUARD:%.*]], label [[LOR_RHS:%.*]]
 339 ; CHECK:       cond.true49:
 340 ; CHECK-NEXT:    br i1 [[PRED4:%.*]], label [[IF_THEN69:%.*]], label [[WHILE_BODY63:%.*]]
 341 ; CHECK:       while.body63:
 342 ; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[EXIT:%.*]], label [[WHILE_COND47:%.*]]
 343 ; CHECK:       while.cond47:
 344 ; CHECK-NEXT:    br label [[IRR_GUARD]]
 345 ; CHECK:       cond.end61:
 346 ; CHECK-NEXT:    br i1 [[PRED7:%.*]], label [[WHILE_BODY63]], label [[WHILE_COND]]
 347 ; CHECK:       if.then69:
 348 ; CHECK-NEXT:    br i1 [[PRED8:%.*]], label [[EXIT]], label [[WHILE_COND]]
 349 ; CHECK:       lor.rhs:
 350 ; CHECK-NEXT:    br i1 [[PRED9:%.*]], label [[IRR_GUARD]], label [[WHILE_END76:%.*]]
 351 ; CHECK:       while.end76:
 352 ; CHECK-NEXT:    br label [[EXIT]]
 353 ; CHECK:       if.then39:
 354 ; CHECK-NEXT:    br i1 [[PRED10:%.*]], label [[EXIT]], label [[IF_END_I145:%.*]]
 355 ; CHECK:       if.end.i145:
 356 ; CHECK-NEXT:    br i1 [[PRED11:%.*]], label [[EXIT]], label [[IF_END8_I149:%.*]]
 357 ; CHECK:       if.end8.i149:
 358 ; CHECK-NEXT:    br label [[EXIT]]
 359 ; CHECK:       if.then:
 360 ; CHECK-NEXT:    br i1 [[PRED12:%.*]], label [[EXIT]], label [[IF_END_I:%.*]]
 361 ; CHECK:       if.end.i:
 362 ; CHECK-NEXT:    br i1 [[PRED13:%.*]], label [[EXIT]], label [[IF_END8_I:%.*]]
 363 ; CHECK:       if.end8.i:
 364 ; CHECK-NEXT:    br label [[EXIT]]
 365 ; CHECK:       exit:
 366 ; CHECK-NEXT:    ret void
 367 ; CHECK:       irr.guard:
 368 ; CHECK-NEXT:    [[GUARD_COND_TRUE49:%.*]] = phi i1 [ [[PRED6:%.*]], [[WHILE_COND47]] ], [ true, [[WHILE_COND]] ], [ false, [[LOR_RHS]] ]
 369 ; CHECK-NEXT:    br i1 [[GUARD_COND_TRUE49]], label [[COND_TRUE49:%.*]], label [[COND_END61:%.*]]
 370 ;
 371 entry:
 372   br i1 %Pred0, label %if.end, label %if.then
 373
 374 if.end:
 375   br i1 %Pred1, label %if.then7, label %if.else
 376
 377 if.then7:
 378   br label %if.end16
 379
 380 if.else:
 381   br label %if.end16
 382
 383 if.end16:
 384   br i1 %Pred2, label %while.cond.preheader, label %if.then39
 385
 386 while.cond.preheader:
 387   br label %while.cond
 388
 389 while.cond:
 390   br i1 %Pred3, label %cond.true49, label %lor.rhs
 391
 392 cond.true49:
 393   br i1 %Pred4, label %if.then69, label %while.body63
 394
 395 while.body63:
 396   br i1 %Pred5, label %exit, label %while.cond47
 397
 398 while.cond47:
 399   br i1 %Pred6, label %cond.true49, label %cond.end61
 400
 401 cond.end61:
 402   br i1 %Pred7, label %while.body63, label %while.cond
 403
 404 if.then69:
 405   br i1 %Pred8, label %exit, label %while.cond
 406
 407 lor.rhs:
 408   br i1 %Pred9, label %cond.end61, label %while.end76
 409
 410 while.end76:
 411   br label %exit
 412
 413 if.then39:
 414   br i1 %Pred10, label %exit, label %if.end.i145
 415
 416 if.end.i145:
 417   br i1 %Pred11, label %exit, label %if.end8.i149
 418
 419 if.end8.i149:
 420   br label %exit
 421
 422 if.then:
 423   br i1 %Pred12, label %exit, label %if.end.i
 424
 425 if.end.i:
 426   br i1 %Pred13, label %exit, label %if.end8.i
 427
 428 if.end8.i:
 429   br label %exit
 430
 431 exit:
 432   ret void
 433 }