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>' 12declare i1 @foo() 13 14declare i1 @bar(i32) 15 16define i32 @test(i1 %a) { 17Q: 18 br i1 %a, label %N, label %M 19N: ; preds = %Q 20 br label %M 21M: ; 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. 31define i8 @testundef(i32 %u) { 32R: 33 switch i32 %u, label %U [ 34 i32 0, label %S 35 i32 1, label %T 36 i32 2, label %T 37 ] 38 39S: ; preds = %R 40 br label %U 41 42T: ; preds = %R, %R 43 br label %U 44 45U: ; 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. 56define i8 @testundef2(i32 %u, i32* %A) { 57V: 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 65W: ; preds = %V 66 br label %U 67 68Z: 69 store i32 0, i32* %A, align 4 70 br label %X 71 72X: ; preds = %V, %V, %Z 73 br label %U 74 75U: ; 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 85define i8 @testmergesome(i32 %u, i32* %A) { 86V: 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 94W: ; preds = %V 95 store i32 1, i32* %A, align 4 96 br label %Y 97 98Z: 99 store i32 0, i32* %A, align 4 100 br label %X 101 102X: ; preds = %V, %Z 103 br label %Y 104 105Y: ; 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 113define i8 @testmergesome2(i32 %u, i32* %A) { 114V: 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 122W: ; preds = %V 123 store i32 1, i32* %A, align 4 124 br label %Y 125 126X: ; preds = %V, %Z 127 br label %Y 128 129Y: ; 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 136define void @a() { 137entry: 138 br label %BB.nomerge 139 140BB.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 146Succ: ; 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 151Common: ; preds = %Succ 152 %cond = call i1 @foo( ) ; <i1> [#uses=1] 153 br i1 %cond, label %BB.nomerge, label %Succ 154 155Exit: ; preds = %Succ 156 ret void 157} 158 159; This function can't be merged 160define void @b() { 161entry: 162 br label %BB.nomerge 163 164BB.nomerge: ; preds = %Common, %entry 165 br label %Succ 166 167Succ: ; 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 174Common: ; preds = %Succ 175 %cond = call i1 @foo( ) ; <i1> [#uses=1] 176 br i1 %cond, label %BB.nomerge, label %Succ 177 178Exit: ; preds = %Succ 179 ret void 180} 181 182; This function can't be merged (for keeping canonical loop structures) 183define void @c() { 184entry: 185 br label %BB.nomerge 186 187BB.nomerge: ; preds = %Common, %entry 188 br label %Succ 189 190Succ: ; 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 197Common: ; preds = %Succ 198 %cond = call i1 @foo( ) ; <i1> [#uses=1] 199 br i1 %cond, label %BB.nomerge, label %Succ 200 201Pre-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 207Exit: ; preds = %Pre-Exit 208 ret void 209} 210 211; This function can't be merged (for keeping canonical loop structures) 212define void @d() { 213entry: 214 br label %BB.nomerge 215 216BB.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 222Succ: ; 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 227Common: ; preds = %Succ 228 %cond = call i1 @foo( ) ; <i1> [#uses=1] 229 br i1 %cond, label %BB.nomerge, label %Succ 230 231Exit: ; preds = %Succ 232 ret void 233} 234 235; This function can be merged 236define void @e() { 237entry: 238 br label %Succ 239 240Succ: ; 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 246BB.tomerge: ; preds = %Succ 247 %conde = call i1 @foo( ) ; <i1> [#uses=1] 248 br i1 %conde, label %Use, label %Exit 249 250Use: ; preds = %Succ 251 %cond = call i1 @bar( i32 %a ) ; <i1> [#uses=1] 252 br i1 %cond, label %Succ, label %Exit 253 254Exit: ; preds = %Use, %Succ 255 ret void 256} 257