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