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 2 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 be merged 183 define void @c() { 184 entry: 185 br label %BB.tomerge 186 187 BB.tomerge: ; 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.tomerge ], [ 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.tomerge, 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 be merged 212 define void @d() { 213 entry: 214 br label %BB.tomerge 215 216 BB.tomerge: ; 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.tomerge ], [ 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.tomerge, 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 %BB.tomerge 239 240 BB.tomerge: ; 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 %Succ 245 246 Succ: ; preds = %BB.tomerge 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 %BB.tomerge, label %Exit 253 254 Exit: ; preds = %Use, %Succ 255 ret void 256 } 257
