test/Transforms/SimplifyCFG/EqualPHIEdgeBlockMerge.ll

   1 ; Test merging of blocks with phi nodes.
   2 ;
   3 ; RUN: opt < %s -simplifycfg -S > %t
   4 ; RUN: not grep N: %t
   5 ; RUN: not grep X: %t
   6 ; RUN: not grep 'switch i32[^U]+%U' %t
   7 ; RUN: not grep "^BB.tomerge" %t
   8 ; RUN: grep "^BB.nomerge" %t | count 4
   9 ;
  10
  11 ; ModuleID = '<stdin>'
  12 declare i1 @foo()
  13
  14 declare i1 @bar(i32)
  15
  16 define i32 @test(i1 %a) {
  17 Q:
  18         br i1 %a, label %N, label %M
  19 N:              ; preds = %Q
  20         br label %M
  21 M:              ; preds = %N, %Q
  22         ; It's ok to merge N and M because the incoming values for W are the
  23         ; same for both cases...
  24         %W = phi i32 [ 2, %N ], [ 2, %Q ]               ; <i32> [#uses=1]
  25         %R = add i32 %W, 1              ; <i32> [#uses=1]
  26         ret i32 %R
  27 }
  28
  29 ; Test merging of blocks with phi nodes where at least one incoming value
  30 ; in the successor is undef.
  31 define i8 @testundef(i32 %u) {
  32 R:
  33   switch i32 %u, label %U [
  34     i32 0, label %S
  35     i32 1, label %T
  36     i32 2, label %T
  37   ]
  38
  39 S:                                            ; preds = %R
  40   br label %U
  41
  42 T:                                           ; preds = %R, %R
  43   br label %U
  44
  45 U:                                        ; preds = %T, %S, %R
  46   ; We should be able to merge either the S or T block into U by rewriting
  47   ; R's incoming value with the incoming value of that predecessor since
  48   ; R's incoming value is undef and both of those predecessors are simple
  49   ; unconditional branches.
  50   %val.0 = phi i8 [ undef, %R ], [ 1, %T ], [ 0, %S ]
  51   ret i8 %val.0
  52 }
  53
  54 ; Test merging of blocks with phi nodes where at least one incoming value
  55 ; in the successor is undef.
  56 define i8 @testundef2(i32 %u, i32* %A) {
  57 V:
  58   switch i32 %u, label %U [
  59     i32 0, label %W
  60     i32 1, label %X
  61     i32 2, label %X
  62     i32 3, label %Z
  63   ]
  64
  65 W:                                            ; preds = %V
  66   br label %U
  67
  68 Z:
  69   store i32 0, i32* %A, align 4
  70   br label %X
  71
  72 X:                                           ; preds = %V, %V, %Z
  73   br label %U
  74
  75 U:                                        ; preds = %X, %W, %V
  76   ; We should be able to merge either the W or X block into U by rewriting
  77   ; V's incoming value with the incoming value of that predecessor since
  78   ; V's incoming value is undef and both of those predecessors are simple
  79   ; unconditional branches. Note that X has predecessors beyond
  80   ; the direct predecessors of U.
  81   %val.0 = phi i8 [ undef, %V ], [ 1, %X ], [ 1, %W ]
  82   ret i8 %val.0
  83 }
  84
  85 define i8 @testmergesome(i32 %u, i32* %A) {
  86 V:
  87   switch i32 %u, label %Y [
  88     i32 0, label %W
  89     i32 1, label %X
  90     i32 2, label %X
  91     i32 3, label %Z
  92   ]
  93
  94 W:                                            ; preds = %V
  95   store i32 1, i32* %A, align 4
  96   br label %Y
  97
  98 Z:
  99   store i32 0, i32* %A, align 4
 100   br label %X
 101
 102 X:                                           ; preds = %V, %Z
 103   br label %Y
 104
 105 Y:                                        ; preds = %X, %W, %V
 106   ; After merging X into Y, we should have 5 predecessors
 107   ; and thus 5 incoming values to the phi.
 108   %val.0 = phi i8 [ 1, %V ], [ 1, %X ], [ 2, %W ]
 109   ret i8 %val.0
 110 }
 111
 112
 113 define i8 @testmergesome2(i32 %u, i32* %A) {
 114 V:
 115   switch i32 %u, label %W [
 116     i32 0, label %W
 117     i32 1, label %Y
 118     i32 2, label %X
 119     i32 4, label %Y
 120   ]
 121
 122 W:                                            ; preds = %V
 123   store i32 1, i32* %A, align 4
 124   br label %Y
 125
 126 X:                                           ; preds = %V, %Z
 127   br label %Y
 128
 129 Y:                                        ; preds = %X, %W, %V
 130   ; Ensure that we deal with both undef inputs for V when we merge in X.
 131   %val.0 = phi i8 [ undef, %V ], [ 1, %X ], [ 2, %W ], [ undef, %V ]
 132   ret i8 %val.0
 133 }
 134
 135 ; This function can't be merged
 136 define void @a() {
 137 entry:
 138         br label %BB.nomerge
 139
 140 BB.nomerge:             ; preds = %Common, %entry
 141         ; This phi has a conflicting value (0) with below phi (2), so blocks
 142         ; can't be merged.
 143         %a = phi i32 [ 1, %entry ], [ 0, %Common ]              ; <i32> [#uses=1]
 144         br label %Succ
 145
 146 Succ:           ; preds = %Common, %BB.nomerge
 147         %b = phi i32 [ %a, %BB.nomerge ], [ 2, %Common ]                ; <i32> [#uses=0]
 148         %conde = call i1 @foo( )                ; <i1> [#uses=1]
 149         br i1 %conde, label %Common, label %Exit
 150
 151 Common:         ; preds = %Succ
 152         %cond = call i1 @foo( )         ; <i1> [#uses=1]
 153         br i1 %cond, label %BB.nomerge, label %Succ
 154
 155 Exit:           ; preds = %Succ
 156         ret void
 157 }
 158
 159 ; This function can't be merged
 160 define void @b() {
 161 entry:
 162         br label %BB.nomerge
 163
 164 BB.nomerge:             ; preds = %Common, %entry
 165         br label %Succ
 166
 167 Succ:           ; preds = %Common, %BB.nomerge
 168         ; This phi has confliction values for Common and (through BB) Common,
 169         ; blocks can't be merged
 170         %b = phi i32 [ 1, %BB.nomerge ], [ 2, %Common ]         ; <i32> [#uses=0]
 171         %conde = call i1 @foo( )                ; <i1> [#uses=1]
 172         br i1 %conde, label %Common, label %Exit
 173
 174 Common:         ; preds = %Succ
 175         %cond = call i1 @foo( )         ; <i1> [#uses=1]
 176         br i1 %cond, label %BB.nomerge, label %Succ
 177
 178 Exit:           ; preds = %Succ
 179         ret void
 180 }
 181
 182 ; This function can't be merged (for keeping canonical loop structures)
 183 define void @c() {
 184 entry:
 185         br label %BB.nomerge
 186
 187 BB.nomerge:             ; preds = %Common, %entry
 188         br label %Succ
 189
 190 Succ:           ; preds = %Common, %BB.tomerge, %Pre-Exit
 191         ; This phi has identical values for Common and (through BB) Common,
 192         ; blocks can't be merged
 193         %b = phi i32 [ 1, %BB.nomerge ], [ 1, %Common ], [ 2, %Pre-Exit ]
 194         %conde = call i1 @foo( )                ; <i1> [#uses=1]
 195         br i1 %conde, label %Common, label %Pre-Exit
 196
 197 Common:         ; preds = %Succ
 198         %cond = call i1 @foo( )         ; <i1> [#uses=1]
 199         br i1 %cond, label %BB.nomerge, label %Succ
 200
 201 Pre-Exit:       ; preds = %Succ
 202         ; This adds a backedge, so the %b phi node gets a third branch and is
 203         ; not completely trivial
 204         %cond2 = call i1 @foo( )                ; <i1> [#uses=1]
 205         br i1 %cond2, label %Succ, label %Exit
 206
 207 Exit:           ; preds = %Pre-Exit
 208         ret void
 209 }
 210
 211 ; This function can't be merged (for keeping canonical loop structures)
 212 define void @d() {
 213 entry:
 214         br label %BB.nomerge
 215
 216 BB.nomerge:             ; preds = %Common, %entry
 217         ; This phi has a matching value (0) with below phi (0), so blocks
 218         ; can be merged.
 219         %a = phi i32 [ 1, %entry ], [ 0, %Common ]              ; <i32> [#uses=1]
 220         br label %Succ
 221
 222 Succ:           ; preds = %Common, %BB.tomerge
 223         %b = phi i32 [ %a, %BB.nomerge ], [ 0, %Common ]                ; <i32> [#uses=0]
 224         %conde = call i1 @foo( )                ; <i1> [#uses=1]
 225         br i1 %conde, label %Common, label %Exit
 226
 227 Common:         ; preds = %Succ
 228         %cond = call i1 @foo( )         ; <i1> [#uses=1]
 229         br i1 %cond, label %BB.nomerge, label %Succ
 230
 231 Exit:           ; preds = %Succ
 232         ret void
 233 }
 234
 235 ; This function can be merged
 236 define void @e() {
 237 entry:
 238         br label %Succ
 239
 240 Succ:           ; preds = %Use, %entry
 241         ; This phi is used somewhere else than Succ, but this should not prevent
 242         ; merging this block
 243         %a = phi i32 [ 1, %entry ], [ 0, %Use ]         ; <i32> [#uses=1]
 244         br label %BB.tomerge
 245
 246 BB.tomerge:             ; preds = %Succ
 247         %conde = call i1 @foo( )                ; <i1> [#uses=1]
 248         br i1 %conde, label %Use, label %Exit
 249
 250 Use:            ; preds = %Succ
 251         %cond = call i1 @bar( i32 %a )          ; <i1> [#uses=1]
 252         br i1 %cond, label %Succ, label %Exit
 253
 254 Exit:           ; preds = %Use, %Succ
 255         ret void
 256 }