llvm/test/Transforms/FixIrreducible/basic.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -fix-irreducible --verify-loop-info -S | FileCheck %s
   3 ; RUN: opt < %s -passes='fix-irreducible,verify<loops>' -S | FileCheck %s
   4 ; RUN: opt < %s -passes='verify<loops>,fix-irreducible,verify<loops>' -S | FileCheck %s
   5
   6 define i32 @basic(i1 %PredEntry, i1 %PredLeft, i1 %PredRight, i32 %X, i32 %Y) {
   7 ; CHECK-LABEL: @basic(
   8 ; CHECK-NEXT:  entry:
   9 ; CHECK-NEXT:    [[PREDENTRY_INV:%.*]] = xor i1 [[PREDENTRY:%.*]], true
  10 ; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
  11 ; CHECK:       left:
  12 ; CHECK-NEXT:    [[L_PHI:%.*]] = phi i32 [ [[R_PHI_MOVED:%.*]], [[RIGHT:%.*]] ], [ [[L_PHI_MOVED:%.*]], [[IRR_GUARD]] ]
  13 ; CHECK-NEXT:    [[L:%.*]] = add i32 [[L_PHI]], 1
  14 ; CHECK-NEXT:    br i1 [[PREDLEFT:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
  15 ; CHECK:       right:
  16 ; CHECK-NEXT:    br i1 [[PREDRIGHT:%.*]], label [[LEFT:%.*]], label [[EXIT]]
  17 ; CHECK:       exit:
  18 ; CHECK-NEXT:    [[Z:%.*]] = phi i32 [ [[L]], [[LEFT]] ], [ [[R_PHI_MOVED]], [[RIGHT]] ]
  19 ; CHECK-NEXT:    ret i32 [[Z]]
  20 ; CHECK:       irr.guard:
  21 ; CHECK-NEXT:    [[L_PHI_MOVED]] = phi i32 [ [[L_PHI_MOVED]], [[LEFT]] ], [ [[X:%.*]], [[ENTRY:%.*]] ]
  22 ; CHECK-NEXT:    [[R_PHI_MOVED]] = phi i32 [ [[L]], [[LEFT]] ], [ [[Y:%.*]], [[ENTRY]] ]
  23 ; CHECK-NEXT:    [[GUARD_RIGHT:%.*]] = phi i1 [ true, [[LEFT]] ], [ [[PREDENTRY_INV]], [[ENTRY]] ]
  24 ; CHECK-NEXT:    br i1 [[GUARD_RIGHT]], label [[RIGHT]], label [[LEFT]]
  25 ;
  26 entry:
  27   br i1 %PredEntry, label %left, label %right
  28
  29 left:
  30   %L.phi = phi i32 [%X, %entry], [%R.phi, %right]
  31   %L = add i32 %L.phi, 1
  32   br i1 %PredLeft, label %right, label %exit
  33
  34 right:
  35   %R.phi = phi i32 [%Y, %entry], [%L, %left]
  36   br i1 %PredRight, label %left, label %exit
  37
  38 exit:
  39   %Z = phi i32 [%L, %left], [%R.phi, %right]
  40   ret i32 %Z
  41 }
  42
  43 define i32 @feedback_loop(i1 %PredEntry, i1 %PredLeft, i1 %PredRight, i32 %X, i32 %Y) {
  44 ; CHECK-LABEL: @feedback_loop(
  45 ; CHECK-NEXT:  entry:
  46 ; CHECK-NEXT:    [[PREDENTRY_INV:%.*]] = xor i1 [[PREDENTRY:%.*]], true
  47 ; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
  48 ; CHECK:       left:
  49 ; CHECK-NEXT:    [[L_PHI:%.*]] = phi i32 [ [[R_PHI_MOVED:%.*]], [[RIGHT:%.*]] ], [ [[L_PHI_MOVED:%.*]], [[IRR_GUARD]] ]
  50 ; CHECK-NEXT:    br i1 [[PREDLEFT:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
  51 ; CHECK:       right:
  52 ; CHECK-NEXT:    br i1 [[PREDRIGHT:%.*]], label [[LEFT:%.*]], label [[EXIT]]
  53 ; CHECK:       exit:
  54 ; CHECK-NEXT:    [[Z:%.*]] = phi i32 [ [[L_PHI]], [[LEFT]] ], [ [[R_PHI_MOVED]], [[RIGHT]] ]
  55 ; CHECK-NEXT:    ret i32 [[Z]]
  56 ; CHECK:       irr.guard:
  57 ; CHECK-NEXT:    [[L_PHI_MOVED]] = phi i32 [ [[L_PHI_MOVED]], [[LEFT]] ], [ [[X:%.*]], [[ENTRY:%.*]] ]
  58 ; CHECK-NEXT:    [[R_PHI_MOVED]] = phi i32 [ [[L_PHI]], [[LEFT]] ], [ [[Y:%.*]], [[ENTRY]] ]
  59 ; CHECK-NEXT:    [[GUARD_RIGHT:%.*]] = phi i1 [ true, [[LEFT]] ], [ [[PREDENTRY_INV]], [[ENTRY]] ]
  60 ; CHECK-NEXT:    br i1 [[GUARD_RIGHT]], label [[RIGHT]], label [[LEFT]]
  61 ;
  62 entry:
  63   br i1 %PredEntry, label %left, label %right
  64
  65 left:
  66   %L.phi = phi i32 [%X, %entry], [%R.phi, %right]
  67   br i1 %PredLeft, label %right, label %exit
  68
  69 right:
  70   %R.phi = phi i32 [%Y, %entry], [%L.phi, %left]
  71   br i1 %PredRight, label %left, label %exit
  72
  73 exit:
  74   %Z = phi i32 [%L.phi, %left], [%R.phi, %right]
  75   ret i32 %Z
  76 }
  77
  78 define i32 @multiple_predecessors(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) {
  79 ; CHECK-LABEL: @multiple_predecessors(
  80 ; CHECK-NEXT:  entry:
  81 ; CHECK-NEXT:    [[PREDB_INV:%.*]] = xor i1 [[PREDB:%.*]], true
  82 ; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[B:%.*]]
  83 ; CHECK:       A:
  84 ; CHECK-NEXT:    [[A_INC:%.*]] = add i32 [[X:%.*]], 1
  85 ; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
  86 ; CHECK:       B:
  87 ; CHECK-NEXT:    br label [[IRR_GUARD]]
  88 ; CHECK:       C:
  89 ; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[D:%.*]], label [[EXIT:%.*]]
  90 ; CHECK:       D:
  91 ; CHECK-NEXT:    [[D_PHI:%.*]] = phi i32 [ [[C_PHI_MOVED:%.*]], [[C:%.*]] ], [ [[D_PHI_MOVED:%.*]], [[IRR_GUARD]] ]
  92 ; CHECK-NEXT:    [[D_INC:%.*]] = add i32 [[D_PHI]], 1
  93 ; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT]], label [[IRR_GUARD]]
  94 ; CHECK:       exit:
  95 ; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[C_PHI_MOVED]], [[C]] ], [ [[D_INC]], [[D]] ]
  96 ; CHECK-NEXT:    ret i32 [[RET]]
  97 ; CHECK:       irr.guard:
  98 ; CHECK-NEXT:    [[D_PHI_MOVED]] = phi i32 [ [[D_PHI_MOVED]], [[D]] ], [ [[Y:%.*]], [[B]] ], [ [[A_INC]], [[A]] ]
  99 ; CHECK-NEXT:    [[C_PHI_MOVED]] = phi i32 [ [[D_INC]], [[D]] ], [ [[Y]], [[B]] ], [ [[X]], [[A]] ]
 100 ; CHECK-NEXT:    [[GUARD_C:%.*]] = phi i1 [ true, [[D]] ], [ [[PREDB_INV]], [[B]] ], [ [[PREDA:%.*]], [[A]] ]
 101 ; CHECK-NEXT:    br i1 [[GUARD_C]], label [[C]], label [[D]]
 102 ;
 103 entry:
 104   br i1 %PredEntry, label %A, label %B
 105
 106 A:
 107   %A.inc = add i32 %X, 1
 108   br i1 %PredA, label %C, label %D
 109
 110 B:
 111   br i1 %PredB, label %D, label %C
 112
 113 C:
 114   %C.phi = phi i32 [%X, %A], [%Y, %B], [%D.inc, %D]
 115   br i1 %PredC, label %D, label %exit
 116
 117 D:
 118   %D.phi = phi i32 [%A.inc, %A], [%Y, %B], [%C.phi, %C]
 119   %D.inc = add i32 %D.phi, 1
 120   br i1 %PredD, label %exit, label %C
 121
 122 exit:
 123   %ret = phi i32 [%C.phi, %C], [%D.inc, %D]
 124   ret i32 %ret
 125 }
 126
 127 define i32 @separate_predecessors(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) {
 128 ; CHECK-LABEL: @separate_predecessors(
 129 ; CHECK-NEXT:  entry:
 130 ; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[B:%.*]]
 131 ; CHECK:       A:
 132 ; CHECK-NEXT:    [[A_INC:%.*]] = add i32 [[X:%.*]], 1
 133 ; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
 134 ; CHECK:       B:
 135 ; CHECK-NEXT:    br label [[IRR_GUARD]]
 136 ; CHECK:       C:
 137 ; CHECK-NEXT:    [[C_PHI:%.*]] = phi i32 [ [[D_INC:%.*]], [[D:%.*]] ], [ [[C_PHI_MOVED:%.*]], [[IRR_GUARD]] ]
 138 ; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[EXIT:%.*]], label [[IRR_GUARD]]
 139 ; CHECK:       D:
 140 ; CHECK-NEXT:    [[D_INC]] = add i32 [[D_PHI_MOVED:%.*]], 1
 141 ; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT]], label [[C:%.*]]
 142 ; CHECK:       exit:
 143 ; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[C_PHI]], [[C]] ], [ [[D_INC]], [[D]] ]
 144 ; CHECK-NEXT:    ret i32 [[RET]]
 145 ; CHECK:       irr.guard:
 146 ; CHECK-NEXT:    [[C_PHI_MOVED]] = phi i32 [ [[C_PHI_MOVED]], [[C]] ], [ poison, [[B]] ], [ [[X]], [[A]] ]
 147 ; CHECK-NEXT:    [[D_PHI_MOVED]] = phi i32 [ [[C_PHI]], [[C]] ], [ [[Y:%.*]], [[B]] ], [ poison, [[A]] ]
 148 ; CHECK-NEXT:    [[GUARD_D:%.*]] = phi i1 [ true, [[C]] ], [ true, [[B]] ], [ false, [[A]] ]
 149 ; CHECK-NEXT:    br i1 [[GUARD_D]], label [[D]], label [[C]]
 150 ;
 151 entry:
 152   br i1 %PredEntry, label %A, label %B
 153
 154 A:
 155   %A.inc = add i32 %X, 1
 156   br label %C
 157
 158 B:
 159   br label %D
 160
 161 C:
 162   %C.phi = phi i32 [%X, %A], [%D.inc, %D]
 163   br i1 %PredC, label %exit, label %D
 164
 165 D:
 166   %D.phi = phi i32 [%Y, %B], [%C.phi, %C]
 167   %D.inc = add i32 %D.phi, 1
 168   br i1 %PredD, label %exit, label %C
 169
 170 exit:
 171   %ret = phi i32 [%C.phi, %C], [%D.inc, %D]
 172   ret i32 %ret
 173 }
 174
 175 define void @four_headers(i1 %PredEntry, i1 %PredX, i1  %PredY, i1 %PredD) {
 176 ; CHECK-LABEL: @four_headers(
 177 ; CHECK-NEXT:  entry:
 178 ; CHECK-NEXT:    [[PREDY_INV:%.*]] = xor i1 [[PREDY:%.*]], true
 179 ; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[X:%.*]], label [[Y:%.*]]
 180 ; CHECK:       X:
 181 ; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
 182 ; CHECK:       Y:
 183 ; CHECK-NEXT:    br label [[IRR_GUARD]]
 184 ; CHECK:       A:
 185 ; CHECK-NEXT:    br label [[B:%.*]]
 186 ; CHECK:       B:
 187 ; CHECK-NEXT:    br label [[C:%.*]]
 188 ; CHECK:       C:
 189 ; CHECK-NEXT:    br label [[IRR_GUARD]]
 190 ; CHECK:       D:
 191 ; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT:%.*]], label [[A:%.*]]
 192 ; CHECK:       exit:
 193 ; CHECK-NEXT:    ret void
 194 ; CHECK:       irr.guard:
 195 ; CHECK-NEXT:    [[GUARD_D:%.*]] = phi i1 [ true, [[C]] ], [ [[PREDY_INV]], [[Y]] ], [ false, [[X]] ]
 196 ; CHECK-NEXT:    [[GUARD_C:%.*]] = phi i1 [ false, [[C]] ], [ true, [[Y]] ], [ false, [[X]] ]
 197 ; CHECK-NEXT:    [[GUARD_A:%.*]] = phi i1 [ false, [[C]] ], [ false, [[Y]] ], [ [[PREDX:%.*]], [[X]] ]
 198 ; CHECK-NEXT:    br i1 [[GUARD_D]], label [[D:%.*]], label [[IRR_GUARD1:%.*]]
 199 ; CHECK:       irr.guard1:
 200 ; CHECK-NEXT:    br i1 [[GUARD_C]], label [[C]], label [[IRR_GUARD2:%.*]]
 201 ; CHECK:       irr.guard2:
 202 ; CHECK-NEXT:    br i1 [[GUARD_A]], label [[A]], label [[B]]
 203 ;
 204 entry:
 205   br i1 %PredEntry, label %X, label %Y
 206
 207 X:
 208   br i1 %PredX, label %A, label %B
 209
 210 Y:
 211   br i1 %PredY, label %C, label %D
 212
 213 A:
 214   br label %B
 215
 216 B:
 217   br label %C
 218
 219 C:
 220   br label %D
 221
 222 D:
 223   br i1 %PredD, label %exit, label %A
 224
 225 exit:
 226   ret void
 227 }
 228
 229 define i32 @hidden_nodes(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) {
 230 ; CHECK-LABEL: @hidden_nodes(
 231 ; CHECK-NEXT:  entry:
 232 ; CHECK-NEXT:    [[PREDENTRY_INV:%.*]] = xor i1 [[PREDENTRY:%.*]], true
 233 ; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
 234 ; CHECK:       A:
 235 ; CHECK-NEXT:    [[A_PHI:%.*]] = phi i32 [ [[C_INC:%.*]], [[E:%.*]] ], [ [[A_PHI_MOVED:%.*]], [[IRR_GUARD]] ]
 236 ; CHECK-NEXT:    [[A_INC:%.*]] = add i32 [[A_PHI]], 1
 237 ; CHECK-NEXT:    br label [[IRR_GUARD]]
 238 ; CHECK:       B:
 239 ; CHECK-NEXT:    br label [[C:%.*]]
 240 ; CHECK:       C:
 241 ; CHECK-NEXT:    [[C_INC]] = add i32 [[B_PHI_MOVED:%.*]], 1
 242 ; CHECK-NEXT:    br label [[D:%.*]]
 243 ; CHECK:       D:
 244 ; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT:%.*]], label [[E]]
 245 ; CHECK:       E:
 246 ; CHECK-NEXT:    br label [[A:%.*]]
 247 ; CHECK:       exit:
 248 ; CHECK-NEXT:    ret i32 [[B_PHI_MOVED]]
 249 ; CHECK:       irr.guard:
 250 ; CHECK-NEXT:    [[A_PHI_MOVED]] = phi i32 [ [[A_PHI_MOVED]], [[A]] ], [ [[X:%.*]], [[ENTRY:%.*]] ]
 251 ; CHECK-NEXT:    [[B_PHI_MOVED]] = phi i32 [ [[A_INC]], [[A]] ], [ [[Y:%.*]], [[ENTRY]] ]
 252 ; CHECK-NEXT:    [[GUARD_B:%.*]] = phi i1 [ true, [[A]] ], [ [[PREDENTRY_INV]], [[ENTRY]] ]
 253 ; CHECK-NEXT:    br i1 [[GUARD_B]], label [[B:%.*]], label [[A]]
 254 ;
 255 entry:
 256   br i1 %PredEntry, label %A, label %B
 257
 258 A:
 259   %A.phi = phi i32 [%X, %entry], [%C.inc, %E]
 260   %A.inc = add i32 %A.phi, 1
 261   br label %B
 262
 263 B:
 264   %B.phi = phi i32 [%A.inc, %A], [%Y, %entry]
 265   br label %C
 266
 267 C:
 268   %C.inc = add i32 %B.phi, 1
 269   br label %D
 270
 271 D:
 272   br i1 %PredD, label %exit, label %E
 273
 274 E:
 275   br label %A
 276
 277 exit:
 278   ret i32 %B.phi
 279 }