llvm/test/Transforms/SimplifyCFG/EqualPHIEdgeBlockMerge.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; Test merging of blocks with phi nodes.
   3 ;
   4 ; RUN: opt < %s -passes=simplifycfg -simplifycfg-require-and-preserve-domtree=1 -switch-range-to-icmp -S | FileCheck %s
   5 ;
   6
   7 ; ModuleID = '<stdin>'
   8 declare i1 @foo()
   9
  10 declare i1 @bar(i32)
  11
  12 define i32 @test(i1 %a) {
  13 ; CHECK-LABEL: @test(
  14 ; CHECK-NEXT:  Q:
  15 ; CHECK-NEXT:    [[R:%.*]] = add i32 2, 1
  16 ; CHECK-NEXT:    ret i32 [[R]]
  17 ;
  18 Q:
  19   br i1 %a, label %N, label %M
  20 N:              ; preds = %Q
  21   br label %M
  22 M:              ; preds = %N, %Q
  23   ; It's ok to merge N and M because the incoming values for W are the
  24   ; same for both cases...
  25   %W = phi i32 [ 2, %N ], [ 2, %Q ]               ; <i32> [#uses=1]
  26   %R = add i32 %W, 1              ; <i32> [#uses=1]
  27   ret i32 %R
  28 }
  29
  30 ; Test merging of blocks with phi nodes where at least one incoming value
  31 ; in the successor is undef.
  32 define i8 @testundef(i32 %u) {
  33 ; CHECK-LABEL: @testundef(
  34 ; CHECK-NEXT:  R:
  35 ; CHECK-NEXT:    [[U_OFF:%.*]] = add i32 [[U:%.*]], -1
  36 ; CHECK-NEXT:    [[SWITCH:%.*]] = icmp ult i32 [[U_OFF]], 2
  37 ; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[SWITCH]], i8 1, i8 0
  38 ; CHECK-NEXT:    ret i8 [[SPEC_SELECT]]
  39 ;
  40 R:
  41   switch i32 %u, label %U [
  42   i32 0, label %S
  43   i32 1, label %T
  44   i32 2, label %T
  45   ]
  46
  47 S:                                            ; preds = %R
  48   br label %U
  49
  50 T:                                           ; preds = %R, %R
  51   br label %U
  52
  53 U:                                        ; preds = %T, %S, %R
  54   ; We should be able to merge either the S or T block into U by rewriting
  55   ; R's incoming value with the incoming value of that predecessor since
  56   ; R's incoming value is undef and both of those predecessors are simple
  57   ; unconditional branches.
  58   %val.0 = phi i8 [ undef, %R ], [ 1, %T ], [ 0, %S ]
  59   ret i8 %val.0
  60 }
  61
  62 ; Test merging of blocks with phi nodes where at least one incoming value
  63 ; in the successor is undef.
  64 define i8 @testundef2(i32 %u, ptr %A) {
  65 ; CHECK-LABEL: @testundef2(
  66 ; CHECK-NEXT:  V:
  67 ; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[U:%.*]], 3
  68 ; CHECK-NEXT:    br i1 [[COND]], label [[Z:%.*]], label [[U:%.*]]
  69 ; CHECK:       Z:
  70 ; CHECK-NEXT:    store i32 0, ptr [[A:%.*]], align 4
  71 ; CHECK-NEXT:    br label [[U]]
  72 ; CHECK:       U:
  73 ; CHECK-NEXT:    ret i8 1
  74 ;
  75 V:
  76   switch i32 %u, label %U [
  77   i32 0, label %W
  78   i32 1, label %X
  79   i32 2, label %X
  80   i32 3, label %Z
  81   ]
  82
  83 W:                                            ; preds = %V
  84   br label %U
  85
  86 Z:
  87   store i32 0, ptr %A, align 4
  88   br label %X
  89
  90 X:                                           ; preds = %V, %V, %Z
  91   br label %U
  92
  93 U:                                        ; preds = %X, %W, %V
  94   ; We should be able to merge either the W or X block into U by rewriting
  95   ; V's incoming value with the incoming value of that predecessor since
  96   ; V's incoming value is undef and both of those predecessors are simple
  97   ; unconditional branches. Note that X has predecessors beyond
  98   ; the direct predecessors of U.
  99   %val.0 = phi i8 [ undef, %V ], [ 1, %X ], [ 1, %W ]
 100   ret i8 %val.0
 101 }
 102
 103 define i8 @testmergesome(i32 %u, ptr %A) {
 104 ; CHECK-LABEL: @testmergesome(
 105 ; CHECK-NEXT:  V:
 106 ; CHECK-NEXT:    switch i32 [[U:%.*]], label [[Y:%.*]] [
 107 ; CHECK-NEXT:    i32 0, label [[W:%.*]]
 108 ; CHECK-NEXT:    i32 3, label [[Z:%.*]]
 109 ; CHECK-NEXT:    ]
 110 ; CHECK:       W:
 111 ; CHECK-NEXT:    store i32 1, ptr [[A:%.*]], align 4
 112 ; CHECK-NEXT:    br label [[Y]]
 113 ; CHECK:       Z:
 114 ; CHECK-NEXT:    store i32 0, ptr [[A]], align 4
 115 ; CHECK-NEXT:    br label [[Y]]
 116 ; CHECK:       Y:
 117 ; CHECK-NEXT:    [[VAL_0:%.*]] = phi i8 [ 2, [[W]] ], [ 1, [[Z]] ], [ 1, [[V:%.*]] ]
 118 ; CHECK-NEXT:    ret i8 [[VAL_0]]
 119 ;
 120 V:
 121   switch i32 %u, label %Y [
 122   i32 0, label %W
 123   i32 1, label %X
 124   i32 2, label %X
 125   i32 3, label %Z
 126   ]
 127
 128 W:                                            ; preds = %V
 129   store i32 1, ptr %A, align 4
 130   br label %Y
 131
 132 Z:
 133   store i32 0, ptr %A, align 4
 134   br label %X
 135
 136 X:                                           ; preds = %V, %Z
 137   br label %Y
 138
 139 Y:                                        ; preds = %X, %W, %V
 140   ; After merging X into Y, we should have 5 predecessors
 141   ; and thus 5 incoming values to the phi.
 142   %val.0 = phi i8 [ 1, %V ], [ 1, %X ], [ 2, %W ]
 143   ret i8 %val.0
 144 }
 145
 146
 147 define i8 @testmergesome2(i32 %u, ptr %A) {
 148 ; CHECK-LABEL: @testmergesome2(
 149 ; CHECK-NEXT:  V:
 150 ; CHECK-NEXT:    switch i32 [[U:%.*]], label [[W:%.*]] [
 151 ; CHECK-NEXT:    i32 4, label [[Y:%.*]]
 152 ; CHECK-NEXT:    i32 1, label [[Y]]
 153 ; CHECK-NEXT:    i32 2, label [[Y]]
 154 ; CHECK-NEXT:    ]
 155 ; CHECK:       W:
 156 ; CHECK-NEXT:    store i32 1, ptr [[A:%.*]], align 4
 157 ; CHECK-NEXT:    br label [[Y]]
 158 ; CHECK:       Y:
 159 ; CHECK-NEXT:    [[VAL_0:%.*]] = phi i8 [ 1, [[V:%.*]] ], [ 2, [[W]] ], [ 1, [[V]] ], [ 1, [[V]] ]
 160 ; CHECK-NEXT:    ret i8 [[VAL_0]]
 161 ;
 162 V:
 163   switch i32 %u, label %W [
 164   i32 0, label %W
 165   i32 1, label %Y
 166   i32 2, label %X
 167   i32 4, label %Y
 168   ]
 169
 170 W:                                            ; preds = %V
 171   store i32 1, ptr %A, align 4
 172   br label %Y
 173
 174 X:                                           ; preds = %V, %Z
 175   br label %Y
 176
 177 Y:                                        ; preds = %X, %W, %V
 178   ; Ensure that we deal with both undef inputs for V when we merge in X.
 179   %val.0 = phi i8 [ undef, %V ], [ 1, %X ], [ 2, %W ], [ undef, %V ]
 180   ret i8 %val.0
 181 }
 182
 183 ; This function can't be merged
 184 define void @a() {
 185 ; CHECK-LABEL: @a(
 186 ; CHECK-NEXT:  entry:
 187 ; CHECK-NEXT:    br label [[BB_NOMERGE:%.*]]
 188 ; CHECK:       BB.nomerge:
 189 ; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ 0, [[COMMON:%.*]] ]
 190 ; CHECK-NEXT:    br label [[SUCC:%.*]]
 191 ; CHECK:       Succ:
 192 ; CHECK-NEXT:    [[B:%.*]] = phi i32 [ [[A]], [[BB_NOMERGE]] ], [ 2, [[COMMON]] ]
 193 ; CHECK-NEXT:    [[CONDE:%.*]] = call i1 @foo()
 194 ; CHECK-NEXT:    br i1 [[CONDE]], label [[COMMON]], label [[EXIT:%.*]]
 195 ; CHECK:       Common:
 196 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @foo()
 197 ; CHECK-NEXT:    br i1 [[COND]], label [[BB_NOMERGE]], label [[SUCC]]
 198 ; CHECK:       Exit:
 199 ; CHECK-NEXT:    ret void
 200 ;
 201 entry:
 202   br label %BB.nomerge
 203
 204 BB.nomerge:             ; preds = %Common, %entry
 205   ; This phi has a conflicting value (0) with below phi (2), so blocks
 206   ; can't be merged.
 207   %a = phi i32 [ 1, %entry ], [ 0, %Common ]            ; <i32> [#uses=1]
 208   br label %Succ
 209
 210 Succ:           ; preds = %Common, %BB.nomerge
 211   %b = phi i32 [ %a, %BB.nomerge ], [ 2, %Common ]              ; <i32> [#uses=0]
 212   %conde = call i1 @foo( )              ; <i1> [#uses=1]
 213   br i1 %conde, label %Common, label %Exit
 214
 215 Common:         ; preds = %Succ
 216   %cond = call i1 @foo( )               ; <i1> [#uses=1]
 217   br i1 %cond, label %BB.nomerge, label %Succ
 218
 219 Exit:           ; preds = %Succ
 220   ret void
 221 }
 222
 223 ; This function can't be merged
 224 define void @b() {
 225 ; CHECK-LABEL: @b(
 226 ; CHECK-NEXT:  entry:
 227 ; CHECK-NEXT:    br label [[BB_NOMERGE:%.*]]
 228 ; CHECK:       BB.nomerge:
 229 ; CHECK-NEXT:    br label [[SUCC:%.*]]
 230 ; CHECK:       Succ:
 231 ; CHECK-NEXT:    [[B:%.*]] = phi i32 [ 1, [[BB_NOMERGE]] ], [ 2, [[COMMON:%.*]] ]
 232 ; CHECK-NEXT:    [[CONDE:%.*]] = call i1 @foo()
 233 ; CHECK-NEXT:    br i1 [[CONDE]], label [[COMMON]], label [[EXIT:%.*]]
 234 ; CHECK:       Common:
 235 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @foo()
 236 ; CHECK-NEXT:    br i1 [[COND]], label [[BB_NOMERGE]], label [[SUCC]]
 237 ; CHECK:       Exit:
 238 ; CHECK-NEXT:    ret void
 239 ;
 240 entry:
 241   br label %BB.nomerge
 242
 243 BB.nomerge:             ; preds = %Common, %entry
 244   br label %Succ
 245
 246 Succ:           ; preds = %Common, %BB.nomerge
 247   ; This phi has confliction values for Common and (through BB) Common,
 248   ; blocks can't be merged
 249   %b = phi i32 [ 1, %BB.nomerge ], [ 2, %Common ]               ; <i32> [#uses=0]
 250   %conde = call i1 @foo( )              ; <i1> [#uses=1]
 251   br i1 %conde, label %Common, label %Exit
 252
 253 Common:         ; preds = %Succ
 254   %cond = call i1 @foo( )               ; <i1> [#uses=1]
 255   br i1 %cond, label %BB.nomerge, label %Succ
 256
 257 Exit:           ; preds = %Succ
 258   ret void
 259 }
 260
 261 ; This function can't be merged (for keeping canonical loop structures)
 262 define void @c() {
 263 ; CHECK-LABEL: @c(
 264 ; CHECK-NEXT:  entry:
 265 ; CHECK-NEXT:    br label [[BB_NOMERGE:%.*]]
 266 ; CHECK:       BB.nomerge:
 267 ; CHECK-NEXT:    br label [[SUCC:%.*]]
 268 ; CHECK:       Succ:
 269 ; CHECK-NEXT:    [[B:%.*]] = phi i32 [ 1, [[BB_NOMERGE]] ], [ 1, [[COMMON:%.*]] ], [ 2, [[PRE_EXIT:%.*]] ]
 270 ; CHECK-NEXT:    [[CONDE:%.*]] = call i1 @foo()
 271 ; CHECK-NEXT:    br i1 [[CONDE]], label [[COMMON]], label [[PRE_EXIT]]
 272 ; CHECK:       Common:
 273 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @foo()
 274 ; CHECK-NEXT:    br i1 [[COND]], label [[BB_NOMERGE]], label [[SUCC]]
 275 ; CHECK:       Pre-Exit:
 276 ; CHECK-NEXT:    [[COND2:%.*]] = call i1 @foo()
 277 ; CHECK-NEXT:    br i1 [[COND2]], label [[SUCC]], label [[EXIT:%.*]]
 278 ; CHECK:       Exit:
 279 ; CHECK-NEXT:    ret void
 280 ;
 281 entry:
 282   br label %BB.nomerge
 283
 284 BB.nomerge:             ; preds = %Common, %entry
 285   br label %Succ
 286
 287 Succ:           ; preds = %Common, %BB.tomerge, %Pre-Exit
 288   ; This phi has identical values for Common and (through BB) Common,
 289   ; blocks can't be merged
 290   %b = phi i32 [ 1, %BB.nomerge ], [ 1, %Common ], [ 2, %Pre-Exit ]
 291   %conde = call i1 @foo( )              ; <i1> [#uses=1]
 292   br i1 %conde, label %Common, label %Pre-Exit
 293
 294 Common:         ; preds = %Succ
 295   %cond = call i1 @foo( )               ; <i1> [#uses=1]
 296   br i1 %cond, label %BB.nomerge, label %Succ
 297
 298 Pre-Exit:       ; preds = %Succ
 299   ; This adds a backedge, so the %b phi node gets a third branch and is
 300   ; not completely trivial
 301   %cond2 = call i1 @foo( )              ; <i1> [#uses=1]
 302   br i1 %cond2, label %Succ, label %Exit
 303
 304 Exit:           ; preds = %Pre-Exit
 305   ret void
 306 }
 307
 308 ; This function can't be merged (for keeping canonical loop structures)
 309 define void @d() {
 310 ; CHECK-LABEL: @d(
 311 ; CHECK-NEXT:  entry:
 312 ; CHECK-NEXT:    br label [[BB_NOMERGE:%.*]]
 313 ; CHECK:       BB.nomerge:
 314 ; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ 0, [[COMMON:%.*]] ]
 315 ; CHECK-NEXT:    br label [[SUCC:%.*]]
 316 ; CHECK:       Succ:
 317 ; CHECK-NEXT:    [[B:%.*]] = phi i32 [ [[A]], [[BB_NOMERGE]] ], [ 0, [[COMMON]] ]
 318 ; CHECK-NEXT:    [[CONDE:%.*]] = call i1 @foo()
 319 ; CHECK-NEXT:    br i1 [[CONDE]], label [[COMMON]], label [[EXIT:%.*]]
 320 ; CHECK:       Common:
 321 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @foo()
 322 ; CHECK-NEXT:    br i1 [[COND]], label [[BB_NOMERGE]], label [[SUCC]]
 323 ; CHECK:       Exit:
 324 ; CHECK-NEXT:    ret void
 325 ;
 326 entry:
 327   br label %BB.nomerge
 328
 329 BB.nomerge:             ; preds = %Common, %entry
 330   ; This phi has a matching value (0) with below phi (0), so blocks
 331   ; can be merged.
 332   %a = phi i32 [ 1, %entry ], [ 0, %Common ]            ; <i32> [#uses=1]
 333   br label %Succ
 334
 335 Succ:           ; preds = %Common, %BB.tomerge
 336   %b = phi i32 [ %a, %BB.nomerge ], [ 0, %Common ]              ; <i32> [#uses=0]
 337   %conde = call i1 @foo( )              ; <i1> [#uses=1]
 338   br i1 %conde, label %Common, label %Exit
 339
 340 Common:         ; preds = %Succ
 341   %cond = call i1 @foo( )               ; <i1> [#uses=1]
 342   br i1 %cond, label %BB.nomerge, label %Succ
 343
 344 Exit:           ; preds = %Succ
 345   ret void
 346 }
 347
 348 ; This function can be merged
 349 define void @e() {
 350 ; CHECK-LABEL: @e(
 351 ; CHECK-NEXT:  entry:
 352 ; CHECK-NEXT:    br label [[SUCC:%.*]]
 353 ; CHECK:       Succ:
 354 ; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ 0, [[USE:%.*]] ]
 355 ; CHECK-NEXT:    [[CONDE:%.*]] = call i1 @foo()
 356 ; CHECK-NEXT:    br i1 [[CONDE]], label [[USE]], label [[EXIT:%.*]]
 357 ; CHECK:       Use:
 358 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @bar(i32 [[A]])
 359 ; CHECK-NEXT:    br i1 [[COND]], label [[SUCC]], label [[EXIT]]
 360 ; CHECK:       Exit:
 361 ; CHECK-NEXT:    ret void
 362 ;
 363 entry:
 364   br label %Succ
 365
 366 Succ:           ; preds = %Use, %entry
 367   ; This phi is used somewhere else than Succ, but this should not prevent
 368   ; merging this block
 369   %a = phi i32 [ 1, %entry ], [ 0, %Use ]               ; <i32> [#uses=1]
 370   br label %BB.tomerge
 371
 372 BB.tomerge:             ; preds = %Succ
 373   %conde = call i1 @foo( )              ; <i1> [#uses=1]
 374   br i1 %conde, label %Use, label %Exit
 375
 376 Use:            ; preds = %Succ
 377   %cond = call i1 @bar( i32 %a )                ; <i1> [#uses=1]
 378   br i1 %cond, label %Succ, label %Exit
 379
 380 Exit:           ; preds = %Use, %Succ
 381   ret void
 382 }