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>' 8declare i1 @foo() 9 10declare i1 @bar(i32) 11 12define 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; 18Q: 19 br i1 %a, label %N, label %M 20N: ; preds = %Q 21 br label %M 22M: ; 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. 32define 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; 40R: 41 switch i32 %u, label %U [ 42 i32 0, label %S 43 i32 1, label %T 44 i32 2, label %T 45 ] 46 47S: ; preds = %R 48 br label %U 49 50T: ; preds = %R, %R 51 br label %U 52 53U: ; 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. 64define 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; 75V: 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 83W: ; preds = %V 84 br label %U 85 86Z: 87 store i32 0, ptr %A, align 4 88 br label %X 89 90X: ; preds = %V, %V, %Z 91 br label %U 92 93U: ; 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 103define 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; 120V: 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 128W: ; preds = %V 129 store i32 1, ptr %A, align 4 130 br label %Y 131 132Z: 133 store i32 0, ptr %A, align 4 134 br label %X 135 136X: ; preds = %V, %Z 137 br label %Y 138 139Y: ; 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 147define 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; 162V: 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 170W: ; preds = %V 171 store i32 1, ptr %A, align 4 172 br label %Y 173 174X: ; preds = %V, %Z 175 br label %Y 176 177Y: ; 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 184define 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; 201entry: 202 br label %BB.nomerge 203 204BB.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 210Succ: ; 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 215Common: ; preds = %Succ 216 %cond = call i1 @foo( ) ; <i1> [#uses=1] 217 br i1 %cond, label %BB.nomerge, label %Succ 218 219Exit: ; preds = %Succ 220 ret void 221} 222 223; This function can't be merged 224define 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; 240entry: 241 br label %BB.nomerge 242 243BB.nomerge: ; preds = %Common, %entry 244 br label %Succ 245 246Succ: ; 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 253Common: ; preds = %Succ 254 %cond = call i1 @foo( ) ; <i1> [#uses=1] 255 br i1 %cond, label %BB.nomerge, label %Succ 256 257Exit: ; preds = %Succ 258 ret void 259} 260 261; This function can't be merged (for keeping canonical loop structures) 262define 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; 281entry: 282 br label %BB.nomerge 283 284BB.nomerge: ; preds = %Common, %entry 285 br label %Succ 286 287Succ: ; 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 294Common: ; preds = %Succ 295 %cond = call i1 @foo( ) ; <i1> [#uses=1] 296 br i1 %cond, label %BB.nomerge, label %Succ 297 298Pre-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 304Exit: ; preds = %Pre-Exit 305 ret void 306} 307 308; This function can't be merged (for keeping canonical loop structures) 309define 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; 326entry: 327 br label %BB.nomerge 328 329BB.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 335Succ: ; 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 340Common: ; preds = %Succ 341 %cond = call i1 @foo( ) ; <i1> [#uses=1] 342 br i1 %cond, label %BB.nomerge, label %Succ 343 344Exit: ; preds = %Succ 345 ret void 346} 347 348; This function can be merged 349define 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; 363entry: 364 br label %Succ 365 366Succ: ; 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 372BB.tomerge: ; preds = %Succ 373 %conde = call i1 @foo( ) ; <i1> [#uses=1] 374 br i1 %conde, label %Use, label %Exit 375 376Use: ; preds = %Succ 377 %cond = call i1 @bar( i32 %a ) ; <i1> [#uses=1] 378 br i1 %cond, label %Succ, label %Exit 379 380Exit: ; preds = %Use, %Succ 381 ret void 382} 383