1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt < %s -passes='require<profile-summary>,function(chr,instcombine,simplifycfg)' -S | FileCheck %s 3 4declare void @foo() 5declare void @bar() 6 7; Simple case. 8; Roughly, 9; t0 = *i 10; if ((t0 & 1) != 0) // Likely true 11; foo() 12; if ((t0 & 2) != 0) // Likely true 13; foo() 14; -> 15; t0 = *i 16; if ((t0 & 3) != 0) { // Likely true 17; foo() 18; foo() 19; } else { 20; if ((t0 & 1) != 0) 21; foo() 22; if ((t0 & 2) != 0) 23; foo() 24; } 25define void @test_chr_1(ptr %i) !prof !14 { 26; CHECK-LABEL: @test_chr_1( 27; CHECK-NEXT: entry: 28; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4 29; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[TMP0]], 3 30; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 3 31; CHECK-NEXT: br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15:![0-9]+]] 32; CHECK: bb0: 33; CHECK-NEXT: call void @foo() 34; CHECK-NEXT: call void @foo() 35; CHECK-NEXT: br label [[BB3:%.*]] 36; CHECK: entry.split.nonchr: 37; CHECK-NEXT: [[TMP3:%.*]] = and i32 [[TMP0]], 1 38; CHECK-NEXT: [[DOTNOT:%.*]] = icmp eq i32 [[TMP3]], 0 39; CHECK-NEXT: br i1 [[DOTNOT]], label [[BB1_NONCHR:%.*]], label [[BB0_NONCHR:%.*]], !prof [[PROF16:![0-9]+]] 40; CHECK: bb0.nonchr: 41; CHECK-NEXT: call void @foo() 42; CHECK-NEXT: br label [[BB1_NONCHR]] 43; CHECK: bb1.nonchr: 44; CHECK-NEXT: [[TMP4:%.*]] = and i32 [[TMP0]], 2 45; CHECK-NEXT: [[TMP5:%.*]] = icmp eq i32 [[TMP4]], 0 46; CHECK-NEXT: br i1 [[TMP5]], label [[BB3]], label [[BB2_NONCHR:%.*]], !prof [[PROF16]] 47; CHECK: bb2.nonchr: 48; CHECK-NEXT: call void @foo() 49; CHECK-NEXT: br label [[BB3]] 50; CHECK: bb3: 51; CHECK-NEXT: ret void 52; 53entry: 54 %0 = load i32, ptr %i 55 %1 = and i32 %0, 1 56 %2 = icmp eq i32 %1, 0 57 br i1 %2, label %bb1, label %bb0, !prof !15 58 59bb0: 60 call void @foo() 61 br label %bb1 62 63bb1: 64 %3 = and i32 %0, 2 65 %4 = icmp eq i32 %3, 0 66 br i1 %4, label %bb3, label %bb2, !prof !15 67 68bb2: 69 call void @foo() 70 br label %bb3 71 72bb3: 73 ret void 74} 75 76; Simple case with a cold block. 77; Roughly, 78; t0 = *i 79; if ((t0 & 1) != 0) // Likely true 80; foo() 81; if ((t0 & 2) == 0) // Likely false 82; bar() 83; if ((t0 & 4) != 0) // Likely true 84; foo() 85; -> 86; t0 = *i 87; if ((t0 & 7) == 7) { // Likely true 88; foo() 89; foo() 90; } else { 91; if ((t0 & 1) != 0) 92; foo() 93; if ((t0 & 2) == 0) 94; bar() 95; if ((t0 & 4) != 0) 96; foo() 97; } 98define void @test_chr_1_1(ptr %i) !prof !14 { 99; CHECK-LABEL: @test_chr_1_1( 100; CHECK-NEXT: entry: 101; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4 102; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[TMP0]], 7 103; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 7 104; CHECK-NEXT: br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 105; CHECK: bb0: 106; CHECK-NEXT: call void @foo() 107; CHECK-NEXT: call void @foo() 108; CHECK-NEXT: br label [[BB5:%.*]] 109; CHECK: entry.split.nonchr: 110; CHECK-NEXT: [[TMP3:%.*]] = and i32 [[TMP0]], 1 111; CHECK-NEXT: [[DOTNOT:%.*]] = icmp eq i32 [[TMP3]], 0 112; CHECK-NEXT: br i1 [[DOTNOT]], label [[BB1_NONCHR:%.*]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]] 113; CHECK: bb0.nonchr: 114; CHECK-NEXT: call void @foo() 115; CHECK-NEXT: br label [[BB1_NONCHR]] 116; CHECK: bb1.nonchr: 117; CHECK-NEXT: [[TMP4:%.*]] = and i32 [[TMP0]], 2 118; CHECK-NEXT: [[TMP5:%.*]] = icmp eq i32 [[TMP4]], 0 119; CHECK-NEXT: br i1 [[TMP5]], label [[BB2_NONCHR:%.*]], label [[BB3_NONCHR:%.*]], !prof [[PROF16]] 120; CHECK: bb2.nonchr: 121; CHECK-NEXT: call void @bar() 122; CHECK-NEXT: br label [[BB3_NONCHR]] 123; CHECK: bb3.nonchr: 124; CHECK-NEXT: [[TMP6:%.*]] = and i32 [[TMP0]], 4 125; CHECK-NEXT: [[TMP7:%.*]] = icmp eq i32 [[TMP6]], 0 126; CHECK-NEXT: br i1 [[TMP7]], label [[BB5]], label [[BB4_NONCHR:%.*]], !prof [[PROF16]] 127; CHECK: bb4.nonchr: 128; CHECK-NEXT: call void @foo() 129; CHECK-NEXT: br label [[BB5]] 130; CHECK: bb5: 131; CHECK-NEXT: ret void 132; 133entry: 134 %0 = load i32, ptr %i 135 %1 = and i32 %0, 1 136 %2 = icmp eq i32 %1, 0 137 br i1 %2, label %bb1, label %bb0, !prof !15 138 139bb0: 140 call void @foo() 141 br label %bb1 142 143bb1: 144 %3 = and i32 %0, 2 145 %4 = icmp eq i32 %3, 0 146 br i1 %4, label %bb2, label %bb3, !prof !15 147 148bb2: 149 call void @bar() 150 br label %bb3 151 152bb3: 153 %5 = and i32 %0, 4 154 %6 = icmp eq i32 %5, 0 155 br i1 %6, label %bb5, label %bb4, !prof !15 156 157bb4: 158 call void @foo() 159 br label %bb5 160 161bb5: 162 ret void 163} 164 165; With an aggregate bit check. 166; Roughly, 167; t0 = *i 168; if ((t0 & 255) != 0) // Likely true 169; if ((t0 & 1) != 0) // Likely true 170; foo() 171; if ((t0 & 2) != 0) // Likely true 172; foo() 173; -> 174; t0 = *i 175; if ((t0 & 3) != 0) { // Likely true 176; foo() 177; foo() 178; } else if ((t0 & 255) != 0) 179; if ((t0 & 1) != 0) 180; foo() 181; if ((t0 & 2) != 0) 182; foo() 183; } 184define void @test_chr_2(ptr %i) !prof !14 { 185; CHECK-LABEL: @test_chr_2( 186; CHECK-NEXT: entry: 187; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4 188; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[TMP0]], 3 189; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 3 190; CHECK-NEXT: br i1 [[TMP2]], label [[BB1:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 191; CHECK: bb1: 192; CHECK-NEXT: call void @foo() 193; CHECK-NEXT: call void @foo() 194; CHECK-NEXT: br label [[BB4:%.*]] 195; CHECK: entry.split.nonchr: 196; CHECK-NEXT: [[TMP3:%.*]] = and i32 [[TMP0]], 255 197; CHECK-NEXT: [[DOTNOT:%.*]] = icmp eq i32 [[TMP3]], 0 198; CHECK-NEXT: br i1 [[DOTNOT]], label [[BB4]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]] 199; CHECK: bb0.nonchr: 200; CHECK-NEXT: [[TMP4:%.*]] = and i32 [[TMP0]], 1 201; CHECK-NEXT: [[TMP5:%.*]] = icmp eq i32 [[TMP4]], 0 202; CHECK-NEXT: br i1 [[TMP5]], label [[BB2_NONCHR:%.*]], label [[BB1_NONCHR:%.*]], !prof [[PROF16]] 203; CHECK: bb2.nonchr: 204; CHECK-NEXT: [[TMP6:%.*]] = and i32 [[TMP0]], 2 205; CHECK-NEXT: [[TMP7:%.*]] = icmp eq i32 [[TMP6]], 0 206; CHECK-NEXT: br i1 [[TMP7]], label [[BB4]], label [[BB3_NONCHR:%.*]], !prof [[PROF16]] 207; CHECK: bb3.nonchr: 208; CHECK-NEXT: call void @foo() 209; CHECK-NEXT: br label [[BB4]] 210; CHECK: bb1.nonchr: 211; CHECK-NEXT: call void @foo() 212; CHECK-NEXT: br label [[BB2_NONCHR]] 213; CHECK: bb4: 214; CHECK-NEXT: ret void 215; 216entry: 217 %0 = load i32, ptr %i 218 %1 = and i32 %0, 255 219 %2 = icmp eq i32 %1, 0 220 br i1 %2, label %bb4, label %bb0, !prof !15 221 222bb0: 223 %3 = and i32 %0, 1 224 %4 = icmp eq i32 %3, 0 225 br i1 %4, label %bb2, label %bb1, !prof !15 226 227bb1: 228 call void @foo() 229 br label %bb2 230 231bb2: 232 %5 = and i32 %0, 2 233 %6 = icmp eq i32 %5, 0 234 br i1 %6, label %bb4, label %bb3, !prof !15 235 236bb3: 237 call void @foo() 238 br label %bb4 239 240bb4: 241 ret void 242} 243 244; Split case. 245; Roughly, 246; t1 = *i 247; if ((t1 & 1) != 0) // Likely true 248; foo() 249; if ((t1 & 2) != 0) // Likely true 250; foo() 251; t2 = *i 252; if ((t2 & 4) != 0) // Likely true 253; foo() 254; if ((t2 & 8) != 0) // Likely true 255; foo() 256; -> 257; t1 = *i 258; if ((t1 & 3) != 0) { // Likely true 259; foo() 260; foo() 261; } else { 262; if ((t1 & 1) != 0) 263; foo() 264; if ((t1 & 2) != 0) 265; foo() 266; } 267; t2 = *i 268; if ((t2 & 12) != 0) { // Likely true 269; foo() 270; foo() 271; } else { 272; if ((t2 & 4) != 0) 273; foo() 274; if ((t2 & 8) != 0) 275; foo() 276; } 277define void @test_chr_3(ptr %i) !prof !14 { 278; CHECK-LABEL: @test_chr_3( 279; CHECK-NEXT: entry: 280; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4 281; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[TMP0]], 3 282; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 3 283; CHECK-NEXT: br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 284; CHECK: bb0: 285; CHECK-NEXT: call void @foo() 286; CHECK-NEXT: call void @foo() 287; CHECK-NEXT: br label [[BB3:%.*]] 288; CHECK: entry.split.nonchr: 289; CHECK-NEXT: [[TMP3:%.*]] = and i32 [[TMP0]], 1 290; CHECK-NEXT: [[DOTNOT:%.*]] = icmp eq i32 [[TMP3]], 0 291; CHECK-NEXT: br i1 [[DOTNOT]], label [[BB1_NONCHR:%.*]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]] 292; CHECK: bb0.nonchr: 293; CHECK-NEXT: call void @foo() 294; CHECK-NEXT: br label [[BB1_NONCHR]] 295; CHECK: bb1.nonchr: 296; CHECK-NEXT: [[TMP4:%.*]] = and i32 [[TMP0]], 2 297; CHECK-NEXT: [[TMP5:%.*]] = icmp eq i32 [[TMP4]], 0 298; CHECK-NEXT: br i1 [[TMP5]], label [[BB3]], label [[BB2_NONCHR:%.*]], !prof [[PROF16]] 299; CHECK: bb2.nonchr: 300; CHECK-NEXT: call void @foo() 301; CHECK-NEXT: br label [[BB3]] 302; CHECK: bb3: 303; CHECK-NEXT: [[TMP6:%.*]] = load i32, ptr [[I]], align 4 304; CHECK-NEXT: [[TMP7:%.*]] = and i32 [[TMP6]], 12 305; CHECK-NEXT: [[TMP8:%.*]] = icmp eq i32 [[TMP7]], 12 306; CHECK-NEXT: br i1 [[TMP8]], label [[BB4:%.*]], label [[BB3_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 307; CHECK: bb4: 308; CHECK-NEXT: call void @foo() 309; CHECK-NEXT: call void @foo() 310; CHECK-NEXT: br label [[BB7:%.*]] 311; CHECK: bb3.split.nonchr: 312; CHECK-NEXT: [[TMP9:%.*]] = and i32 [[TMP6]], 4 313; CHECK-NEXT: [[DOTNOT1:%.*]] = icmp eq i32 [[TMP9]], 0 314; CHECK-NEXT: br i1 [[DOTNOT1]], label [[BB5_NONCHR:%.*]], label [[BB4_NONCHR:%.*]], !prof [[PROF16]] 315; CHECK: bb4.nonchr: 316; CHECK-NEXT: call void @foo() 317; CHECK-NEXT: br label [[BB5_NONCHR]] 318; CHECK: bb5.nonchr: 319; CHECK-NEXT: [[TMP10:%.*]] = and i32 [[TMP6]], 8 320; CHECK-NEXT: [[TMP11:%.*]] = icmp eq i32 [[TMP10]], 0 321; CHECK-NEXT: br i1 [[TMP11]], label [[BB7]], label [[BB6_NONCHR:%.*]], !prof [[PROF16]] 322; CHECK: bb6.nonchr: 323; CHECK-NEXT: call void @foo() 324; CHECK-NEXT: br label [[BB7]] 325; CHECK: bb7: 326; CHECK-NEXT: ret void 327; 328entry: 329 %0 = load i32, ptr %i 330 %1 = and i32 %0, 1 331 %2 = icmp eq i32 %1, 0 332 br i1 %2, label %bb1, label %bb0, !prof !15 333 334bb0: 335 call void @foo() 336 br label %bb1 337 338bb1: 339 %3 = and i32 %0, 2 340 %4 = icmp eq i32 %3, 0 341 br i1 %4, label %bb3, label %bb2, !prof !15 342 343bb2: 344 call void @foo() 345 br label %bb3 346 347bb3: 348 %5 = load i32, ptr %i 349 %6 = and i32 %5, 4 350 %7 = icmp eq i32 %6, 0 351 br i1 %7, label %bb5, label %bb4, !prof !15 352 353bb4: 354 call void @foo() 355 br label %bb5 356 357bb5: 358 %8 = and i32 %5, 8 359 %9 = icmp eq i32 %8, 0 360 br i1 %9, label %bb7, label %bb6, !prof !15 361 362bb6: 363 call void @foo() 364 br label %bb7 365 366bb7: 367 ret void 368} 369 370; Selects. 371; Roughly, 372; t0 = *i 373; sum1 = (t0 & 1) ? sum0 : (sum0 + 42) // Likely false 374; sum2 = (t0 & 2) ? sum1 : (sum1 + 43) // Likely false 375; return sum2 376; -> 377; t0 = *i 378; if ((t0 & 3) == 3) 379; return sum0 + 85 380; else { 381; sum1 = (t0 & 1) ? sum0 : (sum0 + 42) 382; sum2 = (t0 & 2) ? sum1 : (sum1 + 43) 383; return sum2 384; } 385define i32 @test_chr_4(ptr %i, i32 %sum0) !prof !14 { 386; CHECK-LABEL: @test_chr_4( 387; CHECK-NEXT: entry: 388; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4 389; CHECK-NEXT: [[DOTFR1:%.*]] = freeze i32 [[TMP0]] 390; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[DOTFR1]], 3 391; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 3 392; CHECK-NEXT: br i1 [[TMP2]], label [[ENTRY_SPLIT:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 393; CHECK: common.ret: 394; CHECK-NEXT: [[COMMON_RET_OP:%.*]] = phi i32 [ [[TMP3:%.*]], [[ENTRY_SPLIT]] ], [ [[SUM2_NONCHR:%.*]], [[ENTRY_SPLIT_NONCHR]] ] 395; CHECK-NEXT: ret i32 [[COMMON_RET_OP]] 396; CHECK: entry.split: 397; CHECK-NEXT: [[TMP3]] = add i32 [[SUM0:%.*]], 85 398; CHECK-NEXT: br label [[COMMON_RET:%.*]] 399; CHECK: entry.split.nonchr: 400; CHECK-NEXT: [[TMP4:%.*]] = add i32 [[SUM0]], 42 401; CHECK-NEXT: [[TMP5:%.*]] = and i32 [[DOTFR1]], 1 402; CHECK-NEXT: [[DOTNOT:%.*]] = icmp eq i32 [[TMP5]], 0 403; CHECK-NEXT: [[SUM1_NONCHR:%.*]] = select i1 [[DOTNOT]], i32 [[SUM0]], i32 [[TMP4]], !prof [[PROF16]] 404; CHECK-NEXT: [[TMP6:%.*]] = and i32 [[DOTFR1]], 2 405; CHECK-NEXT: [[TMP7:%.*]] = icmp eq i32 [[TMP6]], 0 406; CHECK-NEXT: [[TMP8:%.*]] = add i32 [[SUM1_NONCHR]], 43 407; CHECK-NEXT: [[SUM2_NONCHR]] = select i1 [[TMP7]], i32 [[SUM1_NONCHR]], i32 [[TMP8]], !prof [[PROF16]] 408; CHECK-NEXT: br label [[COMMON_RET]] 409; 410entry: 411 %0 = load i32, ptr %i 412 %1 = and i32 %0, 1 413 %2 = icmp eq i32 %1, 0 414 %3 = add i32 %sum0, 42 415 %sum1 = select i1 %2, i32 %sum0, i32 %3, !prof !15 416 %4 = and i32 %0, 2 417 %5 = icmp eq i32 %4, 0 418 %6 = add i32 %sum1, 43 419 %sum2 = select i1 %5, i32 %sum1, i32 %6, !prof !15 420 ret i32 %sum2 421} 422 423; Selects + Brs 424; Roughly, 425; t0 = *i 426; if ((t0 & 255) != 0) { // Likely true 427; sum = (t0 & 1) ? sum0 : (sum0 + 42) // Likely false 428; sum = (t0 & 2) ? sum : (sum + 43) // Likely false 429; if ((t0 & 4) != 0) { // Likely true 430; sum3 = sum + 44 431; sum = (t0 & 8) ? sum3 : (sum3 + 44) // Likely false 432; } 433; } 434; return sum 435; -> 436; t0 = *i 437; if ((t0 & 15) != 15) { // Likely true 438; sum = sum0 + 173 439; } else if ((t0 & 255) != 0) { 440; sum = (t0 & 1) ? sum0 : (sum0 + 42) 441; sum = (t0 & 2) ? sum : (sum + 43) 442; if ((t0 & 4) != 0) { 443; sum3 = sum + 44 444; sum = (t0 & 8) ? sum3 : (sum3 + 44) 445; } 446; } 447; return sum 448define i32 @test_chr_5(ptr %i, i32 %sum0) !prof !14 { 449; CHECK-LABEL: @test_chr_5( 450; CHECK-NEXT: entry: 451; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4 452; CHECK-NEXT: [[DOTFR1:%.*]] = freeze i32 [[TMP0]] 453; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[DOTFR1]], 15 454; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 15 455; CHECK-NEXT: br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 456; CHECK: bb0: 457; CHECK-NEXT: [[TMP3:%.*]] = add i32 [[SUM0:%.*]], 85 458; CHECK-NEXT: [[TMP4:%.*]] = add i32 [[SUM0]], 173 459; CHECK-NEXT: br label [[BB3:%.*]] 460; CHECK: entry.split.nonchr: 461; CHECK-NEXT: [[TMP5:%.*]] = and i32 [[DOTFR1]], 255 462; CHECK-NEXT: [[DOTNOT:%.*]] = icmp eq i32 [[TMP5]], 0 463; CHECK-NEXT: br i1 [[DOTNOT]], label [[BB3]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]] 464; CHECK: bb0.nonchr: 465; CHECK-NEXT: [[TMP6:%.*]] = and i32 [[DOTFR1]], 1 466; CHECK-NEXT: [[TMP7:%.*]] = icmp eq i32 [[TMP6]], 0 467; CHECK-NEXT: [[TMP8:%.*]] = add i32 [[SUM0]], 42 468; CHECK-NEXT: [[SUM1_NONCHR:%.*]] = select i1 [[TMP7]], i32 [[SUM0]], i32 [[TMP8]], !prof [[PROF16]] 469; CHECK-NEXT: [[TMP9:%.*]] = and i32 [[DOTFR1]], 2 470; CHECK-NEXT: [[TMP10:%.*]] = icmp eq i32 [[TMP9]], 0 471; CHECK-NEXT: [[TMP11:%.*]] = add i32 [[SUM1_NONCHR]], 43 472; CHECK-NEXT: [[SUM2_NONCHR:%.*]] = select i1 [[TMP10]], i32 [[SUM1_NONCHR]], i32 [[TMP11]], !prof [[PROF16]] 473; CHECK-NEXT: [[TMP12:%.*]] = and i32 [[DOTFR1]], 4 474; CHECK-NEXT: [[TMP13:%.*]] = icmp eq i32 [[TMP12]], 0 475; CHECK-NEXT: [[TMP14:%.*]] = and i32 [[DOTFR1]], 8 476; CHECK-NEXT: [[TMP15:%.*]] = icmp eq i32 [[TMP14]], 0 477; CHECK-NEXT: [[SUM4_NONCHR_V:%.*]] = select i1 [[TMP15]], i32 44, i32 88 478; CHECK-NEXT: [[SUM4_NONCHR:%.*]] = add i32 [[SUM2_NONCHR]], [[SUM4_NONCHR_V]] 479; CHECK-NEXT: [[SUM5_NONCHR:%.*]] = select i1 [[TMP13]], i32 [[SUM2_NONCHR]], i32 [[SUM4_NONCHR]], !prof [[PROF16]] 480; CHECK-NEXT: br label [[BB3]] 481; CHECK: bb3: 482; CHECK-NEXT: [[SUM6:%.*]] = phi i32 [ [[TMP4]], [[BB0]] ], [ [[SUM0]], [[ENTRY_SPLIT_NONCHR]] ], [ [[SUM5_NONCHR]], [[BB0_NONCHR]] ] 483; CHECK-NEXT: ret i32 [[SUM6]] 484; 485entry: 486 %0 = load i32, ptr %i 487 %1 = and i32 %0, 255 488 %2 = icmp eq i32 %1, 0 489 br i1 %2, label %bb3, label %bb0, !prof !15 490 491bb0: 492 %3 = and i32 %0, 1 493 %4 = icmp eq i32 %3, 0 494 %5 = add i32 %sum0, 42 495 %sum1 = select i1 %4, i32 %sum0, i32 %5, !prof !15 496 %6 = and i32 %0, 2 497 %7 = icmp eq i32 %6, 0 498 %8 = add i32 %sum1, 43 499 %sum2 = select i1 %7, i32 %sum1, i32 %8, !prof !15 500 %9 = and i32 %0, 4 501 %10 = icmp eq i32 %9, 0 502 br i1 %10, label %bb2, label %bb1, !prof !15 503 504bb1: 505 %sum3 = add i32 %sum2, 44 506 %11 = and i32 %0, 8 507 %12 = icmp eq i32 %11, 0 508 %13 = add i32 %sum3, 44 509 %sum4 = select i1 %12, i32 %sum3, i32 %13, !prof !15 510 br label %bb2 511 512bb2: 513 %sum5 = phi i32 [ %sum2, %bb0 ], [ %sum4, %bb1 ] 514 br label %bb3 515 516bb3: 517 %sum6 = phi i32 [ %sum0, %entry ], [ %sum5, %bb2 ] 518 ret i32 %sum6 519} 520 521; Selects + Brs with a scope split in the middle 522; Roughly, 523; t0 = *i 524; if ((t0 & 255) != 0) { // Likely true 525; sum = (t0 & 1) ? sum0 : (sum0 + 42) // Likely false 526; sum = (t0 & 2) ? sum : (sum + 43) // Likely false 527; if ((sum0 & 4) != 0) { // Likely true. The condition doesn't use v. 528; sum3 = sum + 44 529; sum = (t0 & 8) ? sum3 : (sum3 + 44) // Likely false 530; } 531; } 532; return sum 533; -> 534; t0 = *i 535; if ((sum0 & 4) != 0 & (t0 & 11) != 11) { // Likely true 536; sum = sum0 + 173 537; } else if ((t0 & 255) != 0) { 538; sum = (t0 & 1) ? sum0 : (sum0 + 42) 539; sum = (t0 & 2) ? sum : (sum + 43) 540; if ((sum0 & 4) != 0) { 541; sum3 = sum + 44 542; sum = (t0 & 8) ? sum3 : (sum3 + 44) 543; } 544; } 545; return sum 546define i32 @test_chr_5_1(ptr %i, i32 %sum0) !prof !14 { 547; CHECK-LABEL: @test_chr_5_1( 548; CHECK-NEXT: entry: 549; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4 550; CHECK-NEXT: [[DOTFR1:%.*]] = freeze i32 [[TMP0]] 551; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[SUM0:%.*]], 4 552; CHECK-NEXT: [[TMP2:%.*]] = icmp ne i32 [[TMP1]], 0 553; CHECK-NEXT: [[TMP3:%.*]] = and i32 [[DOTFR1]], 11 554; CHECK-NEXT: [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 11 555; CHECK-NEXT: [[TMP5:%.*]] = select i1 [[TMP4]], i1 [[TMP2]], i1 false 556; CHECK-NEXT: br i1 [[TMP5]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 557; CHECK: bb0: 558; CHECK-NEXT: [[TMP6:%.*]] = add i32 [[SUM0]], 85 559; CHECK-NEXT: [[TMP7:%.*]] = add i32 [[SUM0]], 173 560; CHECK-NEXT: br label [[BB3:%.*]] 561; CHECK: entry.split.nonchr: 562; CHECK-NEXT: [[TMP8:%.*]] = and i32 [[DOTFR1]], 255 563; CHECK-NEXT: [[DOTNOT:%.*]] = icmp eq i32 [[TMP8]], 0 564; CHECK-NEXT: br i1 [[DOTNOT]], label [[BB3]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]] 565; CHECK: bb0.nonchr: 566; CHECK-NEXT: [[TMP9:%.*]] = and i32 [[DOTFR1]], 1 567; CHECK-NEXT: [[TMP10:%.*]] = icmp eq i32 [[TMP9]], 0 568; CHECK-NEXT: [[TMP11:%.*]] = add i32 [[SUM0]], 42 569; CHECK-NEXT: [[SUM1_NONCHR:%.*]] = select i1 [[TMP10]], i32 [[SUM0]], i32 [[TMP11]], !prof [[PROF16]] 570; CHECK-NEXT: [[TMP12:%.*]] = and i32 [[DOTFR1]], 2 571; CHECK-NEXT: [[TMP13:%.*]] = icmp eq i32 [[TMP12]], 0 572; CHECK-NEXT: [[TMP14:%.*]] = add i32 [[SUM1_NONCHR]], 43 573; CHECK-NEXT: [[SUM2_NONCHR:%.*]] = select i1 [[TMP13]], i32 [[SUM1_NONCHR]], i32 [[TMP14]], !prof [[PROF16]] 574; CHECK-NEXT: [[TMP15:%.*]] = and i32 [[SUM0]], 4 575; CHECK-NEXT: [[TMP16:%.*]] = icmp eq i32 [[TMP15]], 0 576; CHECK-NEXT: [[TMP17:%.*]] = and i32 [[DOTFR1]], 8 577; CHECK-NEXT: [[TMP18:%.*]] = icmp eq i32 [[TMP17]], 0 578; CHECK-NEXT: [[SUM4_NONCHR_V:%.*]] = select i1 [[TMP18]], i32 44, i32 88 579; CHECK-NEXT: [[SUM4_NONCHR:%.*]] = add i32 [[SUM2_NONCHR]], [[SUM4_NONCHR_V]] 580; CHECK-NEXT: [[SUM5_NONCHR:%.*]] = select i1 [[TMP16]], i32 [[SUM2_NONCHR]], i32 [[SUM4_NONCHR]], !prof [[PROF16]] 581; CHECK-NEXT: br label [[BB3]] 582; CHECK: bb3: 583; CHECK-NEXT: [[SUM6:%.*]] = phi i32 [ [[TMP7]], [[BB0]] ], [ [[SUM0]], [[ENTRY_SPLIT_NONCHR]] ], [ [[SUM5_NONCHR]], [[BB0_NONCHR]] ] 584; CHECK-NEXT: ret i32 [[SUM6]] 585; 586entry: 587 %0 = load i32, ptr %i 588 %1 = and i32 %0, 255 589 %2 = icmp eq i32 %1, 0 590 br i1 %2, label %bb3, label %bb0, !prof !15 591 592bb0: 593 %3 = and i32 %0, 1 594 %4 = icmp eq i32 %3, 0 595 %5 = add i32 %sum0, 42 596 %sum1 = select i1 %4, i32 %sum0, i32 %5, !prof !15 597 %6 = and i32 %0, 2 598 %7 = icmp eq i32 %6, 0 599 %8 = add i32 %sum1, 43 600 %sum2 = select i1 %7, i32 %sum1, i32 %8, !prof !15 601 %9 = and i32 %sum0, 4 ; Split 602 %10 = icmp eq i32 %9, 0 603 br i1 %10, label %bb2, label %bb1, !prof !15 604 605bb1: 606 %sum3 = add i32 %sum2, 44 607 %11 = and i32 %0, 8 608 %12 = icmp eq i32 %11, 0 609 %13 = add i32 %sum3, 44 610 %sum4 = select i1 %12, i32 %sum3, i32 %13, !prof !15 611 br label %bb2 612 613bb2: 614 %sum5 = phi i32 [ %sum2, %bb0 ], [ %sum4, %bb1 ] 615 br label %bb3 616 617bb3: 618 %sum6 = phi i32 [ %sum0, %entry ], [ %sum5, %bb2 ] 619 ret i32 %sum6 620} 621 622; Selects + Brs, non-matching bases 623; Roughly, 624; i0 = *i 625; j0 = *j 626; if ((i0 & 255) != 0) { // Likely true 627; sum = (i0 & 2) ? sum0 : (sum0 + 43) // Likely false 628; if ((j0 & 4) != 0) { // Likely true. The condition uses j0, not i0. 629; sum3 = sum + 44 630; sum = (i0 & 8) ? sum3 : (sum3 + 44) // Likely false 631; } 632; } 633; return sum 634; -> 635; i0 = *i 636; j0 = *j 637; if ((j0 & 4) != 0 & (i0 & 10) != 10) { // Likely true 638; sum = sum0 + 131 639; } else if ((i0 & 255) != 0) { 640; sum = (i0 & 2) ? sum0 : (sum0 + 43) 641; if ((j0 & 4) != 0) { 642; sum3 = sum + 44 643; sum = (i0 & 8) ? sum3 : (sum3 + 44) 644; } 645; } 646; return sum 647define i32 @test_chr_6(ptr %i, ptr %j, i32 %sum0) !prof !14 { 648; CHECK-LABEL: @test_chr_6( 649; CHECK-NEXT: entry: 650; CHECK-NEXT: [[I0:%.*]] = load i32, ptr [[I:%.*]], align 4 651; CHECK-NEXT: [[I0_FR:%.*]] = freeze i32 [[I0]] 652; CHECK-NEXT: [[J0:%.*]] = load i32, ptr [[J:%.*]], align 4 653; CHECK-NEXT: [[V9:%.*]] = and i32 [[J0]], 4 654; CHECK-NEXT: [[V10:%.*]] = icmp ne i32 [[V9]], 0 655; CHECK-NEXT: [[TMP0:%.*]] = and i32 [[I0_FR]], 10 656; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 10 657; CHECK-NEXT: [[TMP2:%.*]] = select i1 [[TMP1]], i1 [[V10]], i1 false 658; CHECK-NEXT: br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 659; CHECK: bb0: 660; CHECK-NEXT: [[V8:%.*]] = add i32 [[SUM0:%.*]], 43 661; CHECK-NEXT: [[V13:%.*]] = add i32 [[SUM0]], 131 662; CHECK-NEXT: br label [[BB3:%.*]] 663; CHECK: entry.split.nonchr: 664; CHECK-NEXT: [[V1:%.*]] = and i32 [[I0_FR]], 255 665; CHECK-NEXT: [[V2_NOT:%.*]] = icmp eq i32 [[V1]], 0 666; CHECK-NEXT: br i1 [[V2_NOT]], label [[BB3]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]] 667; CHECK: bb0.nonchr: 668; CHECK-NEXT: [[V3_NONCHR:%.*]] = and i32 [[I0_FR]], 2 669; CHECK-NEXT: [[V4_NONCHR:%.*]] = icmp eq i32 [[V3_NONCHR]], 0 670; CHECK-NEXT: [[V8_NONCHR:%.*]] = add i32 [[SUM0]], 43 671; CHECK-NEXT: [[SUM2_NONCHR:%.*]] = select i1 [[V4_NONCHR]], i32 [[SUM0]], i32 [[V8_NONCHR]], !prof [[PROF16]] 672; CHECK-NEXT: [[V9_NONCHR:%.*]] = and i32 [[J0]], 4 673; CHECK-NEXT: [[V10_NONCHR:%.*]] = icmp eq i32 [[V9_NONCHR]], 0 674; CHECK-NEXT: [[V11_NONCHR:%.*]] = and i32 [[I0_FR]], 8 675; CHECK-NEXT: [[V12_NONCHR:%.*]] = icmp eq i32 [[V11_NONCHR]], 0 676; CHECK-NEXT: [[SUM4_NONCHR_V:%.*]] = select i1 [[V12_NONCHR]], i32 44, i32 88 677; CHECK-NEXT: [[SUM4_NONCHR:%.*]] = add i32 [[SUM2_NONCHR]], [[SUM4_NONCHR_V]] 678; CHECK-NEXT: [[SUM5_NONCHR:%.*]] = select i1 [[V10_NONCHR]], i32 [[SUM2_NONCHR]], i32 [[SUM4_NONCHR]], !prof [[PROF16]] 679; CHECK-NEXT: br label [[BB3]] 680; CHECK: bb3: 681; CHECK-NEXT: [[SUM6:%.*]] = phi i32 [ [[V13]], [[BB0]] ], [ [[SUM0]], [[ENTRY_SPLIT_NONCHR]] ], [ [[SUM5_NONCHR]], [[BB0_NONCHR]] ] 682; CHECK-NEXT: ret i32 [[SUM6]] 683; 684entry: 685 %i0 = load i32, ptr %i 686 %j0 = load i32, ptr %j 687 %v1 = and i32 %i0, 255 688 %v2 = icmp eq i32 %v1, 0 689 br i1 %v2, label %bb3, label %bb0, !prof !15 690 691bb0: 692 %v3 = and i32 %i0, 2 693 %v4 = icmp eq i32 %v3, 0 694 %v8 = add i32 %sum0, 43 695 %sum2 = select i1 %v4, i32 %sum0, i32 %v8, !prof !15 696 %v9 = and i32 %j0, 4 697 %v10 = icmp eq i32 %v9, 0 698 br i1 %v10, label %bb2, label %bb1, !prof !15 699 700bb1: 701 %sum3 = add i32 %sum2, 44 702 %v11 = and i32 %i0, 8 703 %v12 = icmp eq i32 %v11, 0 704 %v13 = add i32 %sum3, 44 705 %sum4 = select i1 %v12, i32 %sum3, i32 %v13, !prof !15 706 br label %bb2 707 708bb2: 709 %sum5 = phi i32 [ %sum2, %bb0 ], [ %sum4, %bb1 ] 710 br label %bb3 711 712bb3: 713 %sum6 = phi i32 [ %sum0, %entry ], [ %sum5, %bb2 ] 714 ret i32 %sum6 715} 716 717; Selects + Brs, the branch condition can't be hoisted to be merged with a 718; select. No CHR happens. 719; Roughly, 720; i0 = *i 721; sum = ((i0 & 2) == 0) ? sum0 : (sum0 + 43) // Likely false 722; foo(); 723; j0 = *j 724; if ((j0 & 4) != 0) { // Likely true 725; foo(); 726; sum = sum + 44 727; } 728; return sum 729; -> 730; (no change) 731define i32 @test_chr_7(ptr %i, ptr %j, i32 %sum0) !prof !14 { 732; CHECK-LABEL: @test_chr_7( 733; CHECK-NEXT: entry: 734; CHECK-NEXT: [[I0:%.*]] = load i32, ptr [[I:%.*]], align 4 735; CHECK-NEXT: [[V3:%.*]] = and i32 [[I0]], 2 736; CHECK-NEXT: [[V4:%.*]] = icmp eq i32 [[V3]], 0 737; CHECK-NEXT: [[V8:%.*]] = add i32 [[SUM0:%.*]], 43 738; CHECK-NEXT: [[SUM2:%.*]] = select i1 [[V4]], i32 [[SUM0]], i32 [[V8]], !prof [[PROF16]] 739; CHECK-NEXT: call void @foo() 740; CHECK-NEXT: [[J0:%.*]] = load i32, ptr [[J:%.*]], align 4 741; CHECK-NEXT: [[V9:%.*]] = and i32 [[J0]], 4 742; CHECK-NEXT: [[V10:%.*]] = icmp eq i32 [[V9]], 0 743; CHECK-NEXT: br i1 [[V10]], label [[BB2:%.*]], label [[BB1:%.*]], !prof [[PROF16]] 744; CHECK: bb1: 745; CHECK-NEXT: call void @foo() 746; CHECK-NEXT: [[SUM4:%.*]] = add i32 [[SUM2]], 44 747; CHECK-NEXT: br label [[BB2]] 748; CHECK: bb2: 749; CHECK-NEXT: [[SUM5:%.*]] = phi i32 [ [[SUM2]], [[ENTRY:%.*]] ], [ [[SUM4]], [[BB1]] ] 750; CHECK-NEXT: ret i32 [[SUM5]] 751; 752entry: 753 %i0 = load i32, ptr %i 754 %v3 = and i32 %i0, 2 755 %v4 = icmp eq i32 %v3, 0 756 %v8 = add i32 %sum0, 43 757 %sum2 = select i1 %v4, i32 %sum0, i32 %v8, !prof !15 758 call void @foo() 759 %j0 = load i32, ptr %j 760 %v9 = and i32 %j0, 4 761 %v10 = icmp eq i32 %v9, 0 762 br i1 %v10, label %bb2, label %bb1, !prof !15 ; %v10 can't be hoisted above the above select 763 764bb1: 765 call void @foo() 766 %sum4 = add i32 %sum2, 44 767 br label %bb2 768 769bb2: 770 %sum5 = phi i32 [ %sum2, %entry ], [ %sum4, %bb1 ] 771 ret i32 %sum5 772} 773 774; Selects + Brs, the branch condition can't be hoisted to be merged with the 775; selects. Dropping the select. 776; Roughly, 777; i0 = *i 778; sum = ((i0 & 2) == 0) ? sum0 : (sum0 + 43) // Likely false 779; foo(); 780; j0 = *j 781; if ((j0 & 4) != 0) // Likely true 782; foo() 783; if ((j0 & 8) != 0) // Likely true 784; foo() 785; return sum 786; -> 787; i0 = *i 788; sum = ((i0 & 2) == 0) ? sum0 : (sum0 + 43) // Likely false 789; foo(); 790; j0 = *j 791; if ((j0 & 12) != 12) { // Likely true 792; foo() 793; foo() 794; } else { 795; if ((j0 & 4) != 0) 796; foo() 797; if ((j0 & 8) != 0) 798; foo() 799; } 800; return sum 801define i32 @test_chr_7_1(ptr %i, ptr %j, i32 %sum0) !prof !14 { 802; CHECK-LABEL: @test_chr_7_1( 803; CHECK-NEXT: entry: 804; CHECK-NEXT: [[I0:%.*]] = load i32, ptr [[I:%.*]], align 4 805; CHECK-NEXT: call void @foo() 806; CHECK-NEXT: [[J0:%.*]] = load i32, ptr [[J:%.*]], align 4 807; CHECK-NEXT: [[TMP0:%.*]] = and i32 [[J0]], 12 808; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 12 809; CHECK-NEXT: br i1 [[TMP1]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 810; CHECK: bb0: 811; CHECK-NEXT: call void @foo() 812; CHECK-NEXT: call void @foo() 813; CHECK-NEXT: br label [[BB3:%.*]] 814; CHECK: entry.split.nonchr: 815; CHECK-NEXT: [[V9:%.*]] = and i32 [[J0]], 4 816; CHECK-NEXT: [[V10_NOT:%.*]] = icmp eq i32 [[V9]], 0 817; CHECK-NEXT: br i1 [[V10_NOT]], label [[BB1_NONCHR:%.*]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]] 818; CHECK: bb0.nonchr: 819; CHECK-NEXT: call void @foo() 820; CHECK-NEXT: br label [[BB1_NONCHR]] 821; CHECK: bb1.nonchr: 822; CHECK-NEXT: [[V11_NONCHR:%.*]] = and i32 [[J0]], 8 823; CHECK-NEXT: [[V12_NONCHR:%.*]] = icmp eq i32 [[V11_NONCHR]], 0 824; CHECK-NEXT: br i1 [[V12_NONCHR]], label [[BB3]], label [[BB2_NONCHR:%.*]], !prof [[PROF16]] 825; CHECK: bb2.nonchr: 826; CHECK-NEXT: call void @foo() 827; CHECK-NEXT: br label [[BB3]] 828; CHECK: bb3: 829; CHECK-NEXT: [[V3:%.*]] = and i32 [[I0]], 2 830; CHECK-NEXT: [[V4:%.*]] = icmp eq i32 [[V3]], 0 831; CHECK-NEXT: [[V8:%.*]] = add i32 [[SUM0:%.*]], 43 832; CHECK-NEXT: [[SUM2:%.*]] = select i1 [[V4]], i32 [[SUM0]], i32 [[V8]], !prof [[PROF16]] 833; CHECK-NEXT: ret i32 [[SUM2]] 834; 835entry: 836 %i0 = load i32, ptr %i 837 %v3 = and i32 %i0, 2 838 %v4 = icmp eq i32 %v3, 0 839 %v8 = add i32 %sum0, 43 840 %sum2 = select i1 %v4, i32 %sum0, i32 %v8, !prof !15 841 call void @foo() 842 %j0 = load i32, ptr %j 843 %v9 = and i32 %j0, 4 844 %v10 = icmp eq i32 %v9, 0 845 br i1 %v10, label %bb1, label %bb0, !prof !15 ; %v10 can't be hoisted above the above select 846 847bb0: 848 call void @foo() 849 br label %bb1 850 851bb1: 852 %v11 = and i32 %j0, 8 853 %v12 = icmp eq i32 %v11, 0 854 br i1 %v12, label %bb3, label %bb2, !prof !15 855 856bb2: 857 call void @foo() 858 br label %bb3 859 860bb3: 861 ret i32 %sum2 862} 863 864; Branches aren't biased enough. No CHR happens. 865; Roughly, 866; t0 = *i 867; if ((t0 & 1) != 0) // Not biased 868; foo() 869; if ((t0 & 2) != 0) // Not biased 870; foo() 871; -> 872; (no change) 873define void @test_chr_8(ptr %i) !prof !14 { 874; CHECK-LABEL: @test_chr_8( 875; CHECK-NEXT: entry: 876; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4 877; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[TMP0]], 1 878; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 0 879; CHECK-NEXT: br i1 [[TMP2]], label [[BB1:%.*]], label [[BB0:%.*]], !prof [[PROF17:![0-9]+]] 880; CHECK: bb0: 881; CHECK-NEXT: call void @foo() 882; CHECK-NEXT: br label [[BB1]] 883; CHECK: bb1: 884; CHECK-NEXT: [[TMP3:%.*]] = and i32 [[TMP0]], 2 885; CHECK-NEXT: [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 0 886; CHECK-NEXT: br i1 [[TMP4]], label [[BB3:%.*]], label [[BB2:%.*]], !prof [[PROF17]] 887; CHECK: bb2: 888; CHECK-NEXT: call void @foo() 889; CHECK-NEXT: br label [[BB3]] 890; CHECK: bb3: 891; CHECK-NEXT: ret void 892; 893entry: 894 %0 = load i32, ptr %i 895 %1 = and i32 %0, 1 896 %2 = icmp eq i32 %1, 0 897 br i1 %2, label %bb1, label %bb0, !prof !16 898 899bb0: 900 call void @foo() 901 br label %bb1 902 903bb1: 904 %3 = and i32 %0, 2 905 %4 = icmp eq i32 %3, 0 906 br i1 %4, label %bb3, label %bb2, !prof !16 907 908bb2: 909 call void @foo() 910 br label %bb3 911 912bb3: 913 ret void 914} 915 916; With an existing phi at the exit. 917; Roughly, 918; t = *i 919; if ((t0 & 1) != 0) // Likely true 920; foo() 921; if ((t0 & 2) != 0) { // Likely true 922; t = *j 923; foo() 924; } 925; // There's a phi for t here. 926; return t 927; -> 928; t = *i 929; if ((t & 3) == 3) { // Likely true 930; foo() 931; t = *j 932; foo() 933; } else { 934; if ((t & 1) != 0) 935; foo() 936; if ((t & 2) != 0) { 937; t = *j 938; foo() 939; } 940; } 941; // There's a phi for t here. 942; return t 943define i32 @test_chr_9(ptr %i, ptr %j) !prof !14 { 944; CHECK-LABEL: @test_chr_9( 945; CHECK-NEXT: entry: 946; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4 947; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[TMP0]], 3 948; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 3 949; CHECK-NEXT: br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 950; CHECK: bb0: 951; CHECK-NEXT: call void @foo() 952; CHECK-NEXT: [[TMP3:%.*]] = load i32, ptr [[J:%.*]], align 4 953; CHECK-NEXT: call void @foo() 954; CHECK-NEXT: br label [[BB3:%.*]] 955; CHECK: entry.split.nonchr: 956; CHECK-NEXT: [[TMP4:%.*]] = and i32 [[TMP0]], 1 957; CHECK-NEXT: [[DOTNOT:%.*]] = icmp eq i32 [[TMP4]], 0 958; CHECK-NEXT: br i1 [[DOTNOT]], label [[BB1_NONCHR:%.*]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]] 959; CHECK: bb0.nonchr: 960; CHECK-NEXT: call void @foo() 961; CHECK-NEXT: br label [[BB1_NONCHR]] 962; CHECK: bb1.nonchr: 963; CHECK-NEXT: [[TMP5:%.*]] = and i32 [[TMP0]], 2 964; CHECK-NEXT: [[TMP6:%.*]] = icmp eq i32 [[TMP5]], 0 965; CHECK-NEXT: br i1 [[TMP6]], label [[BB3]], label [[BB2_NONCHR:%.*]], !prof [[PROF16]] 966; CHECK: bb2.nonchr: 967; CHECK-NEXT: [[TMP7:%.*]] = load i32, ptr [[J]], align 4 968; CHECK-NEXT: call void @foo() 969; CHECK-NEXT: br label [[BB3]] 970; CHECK: bb3: 971; CHECK-NEXT: [[TMP8:%.*]] = phi i32 [ [[TMP3]], [[BB0]] ], [ [[TMP0]], [[BB1_NONCHR]] ], [ [[TMP7]], [[BB2_NONCHR]] ] 972; CHECK-NEXT: ret i32 [[TMP8]] 973; 974entry: 975 %0 = load i32, ptr %i 976 %1 = and i32 %0, 1 977 %2 = icmp eq i32 %1, 0 978 br i1 %2, label %bb1, label %bb0, !prof !15 979 980bb0: 981 call void @foo() 982 br label %bb1 983 984bb1: 985 %3 = and i32 %0, 2 986 %4 = icmp eq i32 %3, 0 987 br i1 %4, label %bb3, label %bb2, !prof !15 988 989bb2: 990 %5 = load i32, ptr %j 991 call void @foo() 992 br label %bb3 993 994bb3: 995 %6 = phi i32 [ %0, %bb1 ], [ %5, %bb2 ] 996 ret i32 %6 997} 998 999; With no phi at the exit, but the exit needs a phi inserted after CHR. 1000; Roughly, 1001; t0 = *i 1002; if ((t0 & 1) != 0) // Likely true 1003; foo() 1004; t1 = *j 1005; if ((t1 & 2) != 0) // Likely true 1006; foo() 1007; return (t1 * 42) - (t1 - 99) 1008; -> 1009; t0 = *i 1010; if ((t0 & 3) == 3) { // Likely true 1011; foo() 1012; t1 = *j 1013; foo() 1014; } else { 1015; if ((t0 & 1) != 0) 1016; foo() 1017; if ((t0 & 2) != 0) { 1018; t1 = *j 1019; foo() 1020; } 1021; } 1022; // A new phi for t1 is inserted here. 1023; return (t1 * 42) - (t1 - 99) 1024define i32 @test_chr_10(ptr %i, ptr %j) !prof !14 { 1025; CHECK-LABEL: @test_chr_10( 1026; CHECK-NEXT: entry: 1027; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4 1028; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[TMP0]], 3 1029; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 3 1030; CHECK-NEXT: br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 1031; CHECK: bb0: 1032; CHECK-NEXT: call void @foo() 1033; CHECK-NEXT: [[TMP3:%.*]] = load i32, ptr [[J:%.*]], align 4 1034; CHECK-NEXT: call void @foo() 1035; CHECK-NEXT: br label [[BB3:%.*]] 1036; CHECK: entry.split.nonchr: 1037; CHECK-NEXT: [[TMP4:%.*]] = and i32 [[TMP0]], 1 1038; CHECK-NEXT: [[DOTNOT:%.*]] = icmp eq i32 [[TMP4]], 0 1039; CHECK-NEXT: br i1 [[DOTNOT]], label [[BB1_NONCHR:%.*]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]] 1040; CHECK: bb0.nonchr: 1041; CHECK-NEXT: call void @foo() 1042; CHECK-NEXT: br label [[BB1_NONCHR]] 1043; CHECK: bb1.nonchr: 1044; CHECK-NEXT: [[TMP5:%.*]] = load i32, ptr [[J]], align 4 1045; CHECK-NEXT: [[TMP6:%.*]] = and i32 [[TMP0]], 2 1046; CHECK-NEXT: [[TMP7:%.*]] = icmp eq i32 [[TMP6]], 0 1047; CHECK-NEXT: br i1 [[TMP7]], label [[BB3]], label [[BB2_NONCHR:%.*]], !prof [[PROF16]] 1048; CHECK: bb2.nonchr: 1049; CHECK-NEXT: call void @foo() 1050; CHECK-NEXT: br label [[BB3]] 1051; CHECK: bb3: 1052; CHECK-NEXT: [[TMP8:%.*]] = phi i32 [ [[TMP3]], [[BB0]] ], [ [[TMP5]], [[BB2_NONCHR]] ], [ [[TMP5]], [[BB1_NONCHR]] ] 1053; CHECK-NEXT: [[TMP9:%.*]] = mul i32 [[TMP8]], 42 1054; CHECK-NEXT: [[TMP10:%.*]] = add i32 [[TMP8]], -99 1055; CHECK-NEXT: [[TMP11:%.*]] = add i32 [[TMP9]], [[TMP10]] 1056; CHECK-NEXT: ret i32 [[TMP11]] 1057; 1058entry: 1059 %0 = load i32, ptr %i 1060 %1 = and i32 %0, 1 1061 %2 = icmp eq i32 %1, 0 1062 br i1 %2, label %bb1, label %bb0, !prof !15 1063 1064bb0: 1065 call void @foo() 1066 br label %bb1 1067 1068bb1: 1069 %3 = load i32, ptr %j 1070 %4 = and i32 %0, 2 1071 %5 = icmp eq i32 %4, 0 1072 br i1 %5, label %bb3, label %bb2, !prof !15 1073 1074bb2: 1075 call void @foo() 1076 br label %bb3 1077 1078bb3: 1079 %6 = mul i32 %3, 42 1080 %7 = sub i32 %3, 99 1081 %8 = add i32 %6, %7 1082 ret i32 %8 1083} 1084 1085; Test a case where there are two use-def chain paths to the same value (t0) 1086; from the branch condition. This is a regression test for an old bug that 1087; caused a bad hoisting that moves (hoists) a value (%conv) twice to the end of 1088; the %entry block (once for %div and once for %mul16) and put a use ahead of 1089; its definition like: 1090; %entry: 1091; ... 1092; %div = fdiv double 1.000000e+00, %conv 1093; %conv = sitofp i32 %0 to double 1094; %mul16 = fmul double %div, %conv 1095; 1096; Roughly, 1097; t0 = *i 1098; if ((t0 & 1) != 0) // Likely true 1099; foo() 1100; // there are two use-def paths from the branch condition to t0. 1101; if ((1.0 / t0) * t0 < 1) // Likely true 1102; foo() 1103; -> 1104; t0 = *i 1105; if ((t0 & 1) != 0 & (1.0 / t0) * t0 > 0) { // Likely true 1106; foo() 1107; foo() 1108; } else { 1109; if ((t0 & 1) != 0) 1110; foo() 1111; if ((1.0 / t0) * t0 < 1) // Likely true 1112; foo() 1113; } 1114define void @test_chr_11(ptr %i, i32 %x) !prof !14 { 1115; CHECK-LABEL: @test_chr_11( 1116; CHECK-NEXT: entry: 1117; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4 1118; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[TMP0]], 1 1119; CHECK-NEXT: [[TMP2:%.*]] = icmp ne i32 [[TMP1]], 0 1120; CHECK-NEXT: [[CONV:%.*]] = sitofp i32 [[TMP0]] to double 1121; CHECK-NEXT: [[DIV:%.*]] = fdiv double 1.000000e+00, [[CONV]] 1122; CHECK-NEXT: [[MUL16:%.*]] = fmul double [[DIV]], [[CONV]] 1123; CHECK-NEXT: [[CONV717:%.*]] = fptosi double [[MUL16]] to i32 1124; CHECK-NEXT: [[CMP18:%.*]] = icmp sgt i32 [[CONV717]], 0 1125; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[TMP2]], i1 [[CMP18]], i1 false 1126; CHECK-NEXT: br i1 [[TMP3]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 1127; CHECK: bb0: 1128; CHECK-NEXT: call void @foo() 1129; CHECK-NEXT: call void @foo() 1130; CHECK-NEXT: br label [[BB3:%.*]] 1131; CHECK: entry.split.nonchr: 1132; CHECK-NEXT: br i1 [[TMP2]], label [[BB0_NONCHR:%.*]], label [[BB1_NONCHR:%.*]], !prof [[PROF18:![0-9]+]] 1133; CHECK: bb0.nonchr: 1134; CHECK-NEXT: call void @foo() 1135; CHECK-NEXT: br label [[BB1_NONCHR]] 1136; CHECK: bb1.nonchr: 1137; CHECK-NEXT: [[CONV_NONCHR:%.*]] = sitofp i32 [[TMP0]] to double 1138; CHECK-NEXT: [[DIV_NONCHR:%.*]] = fdiv double 1.000000e+00, [[CONV_NONCHR]] 1139; CHECK-NEXT: [[MUL16_NONCHR:%.*]] = fmul double [[DIV_NONCHR]], [[CONV_NONCHR]] 1140; CHECK-NEXT: [[CONV717_NONCHR:%.*]] = fptosi double [[MUL16_NONCHR]] to i32 1141; CHECK-NEXT: [[CMP18_NONCHR:%.*]] = icmp slt i32 [[CONV717_NONCHR]], 1 1142; CHECK-NEXT: br i1 [[CMP18_NONCHR]], label [[BB3]], label [[BB2_NONCHR:%.*]], !prof [[PROF16]] 1143; CHECK: bb2.nonchr: 1144; CHECK-NEXT: call void @foo() 1145; CHECK-NEXT: br label [[BB3]] 1146; CHECK: bb3: 1147; CHECK-NEXT: ret void 1148; 1149entry: 1150 %0 = load i32, ptr %i 1151 %1 = and i32 %0, 1 1152 %2 = icmp eq i32 %1, 0 1153 br i1 %2, label %bb1, label %bb0, !prof !15 1154 1155bb0: 1156 call void @foo() 1157 br label %bb1 1158 1159bb1: 1160 %conv = sitofp i32 %0 to double 1161 %div = fdiv double 1.000000e+00, %conv 1162 %mul16 = fmul double %div, %conv 1163 %conv717 = fptosi double %mul16 to i32 1164 %cmp18 = icmp slt i32 %conv717, 1 1165 br i1 %cmp18, label %bb3, label %bb2, !prof !15 1166 1167bb2: 1168 call void @foo() 1169 br label %bb3 1170 1171bb3: 1172 ret void 1173} 1174 1175; Selects + unrelated br only 1176define i32 @test_chr_12(ptr %i, i32 %sum0) !prof !14 { 1177; CHECK-LABEL: @test_chr_12( 1178; CHECK-NEXT: entry: 1179; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4 1180; CHECK-NEXT: [[DOTFR1:%.*]] = freeze i32 [[TMP0]] 1181; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[DOTFR1]], 255 1182; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 0 1183; CHECK-NEXT: br i1 [[TMP2]], label [[BB3:%.*]], label [[BB0:%.*]], !prof [[PROF16]] 1184; CHECK: bb0: 1185; CHECK-NEXT: [[TMP3:%.*]] = and i32 [[DOTFR1]], 1 1186; CHECK-NEXT: [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 0 1187; CHECK-NEXT: [[TMP5:%.*]] = add i32 [[SUM0:%.*]], 42 1188; CHECK-NEXT: [[SUM1:%.*]] = select i1 [[TMP4]], i32 [[SUM0]], i32 [[TMP5]], !prof [[PROF16]] 1189; CHECK-NEXT: [[TMP6:%.*]] = and i32 [[DOTFR1]], 2 1190; CHECK-NEXT: [[TMP7:%.*]] = icmp eq i32 [[TMP6]], 0 1191; CHECK-NEXT: [[TMP8:%.*]] = add i32 [[SUM1]], 43 1192; CHECK-NEXT: [[SUM2:%.*]] = select i1 [[TMP7]], i32 [[SUM1]], i32 [[TMP8]], !prof [[PROF16]] 1193; CHECK-NEXT: [[TMP9:%.*]] = load i32, ptr [[I]], align 4 1194; CHECK-NEXT: [[TMP10:%.*]] = icmp ne i32 [[TMP9]], 0 1195; CHECK-NEXT: [[TMP11:%.*]] = and i32 [[DOTFR1]], 8 1196; CHECK-NEXT: [[TMP12:%.*]] = icmp ne i32 [[TMP11]], 0 1197; CHECK-NEXT: [[TMP13:%.*]] = and i1 [[TMP10]], [[TMP12]] 1198; CHECK-NEXT: br i1 [[TMP13]], label [[BB1:%.*]], label [[BB0_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 1199; CHECK: bb1: 1200; CHECK-NEXT: [[TMP14:%.*]] = add i32 [[SUM2]], 88 1201; CHECK-NEXT: br label [[BB3]] 1202; CHECK: bb0.split.nonchr: 1203; CHECK-NEXT: br i1 [[TMP10]], label [[BB1_NONCHR:%.*]], label [[BB3]], !prof [[PROF18]] 1204; CHECK: bb1.nonchr: 1205; CHECK-NEXT: [[TMP15:%.*]] = and i32 [[DOTFR1]], 8 1206; CHECK-NEXT: [[TMP16:%.*]] = icmp eq i32 [[TMP15]], 0 1207; CHECK-NEXT: [[SUM4_NONCHR_V:%.*]] = select i1 [[TMP16]], i32 44, i32 88, !prof [[PROF16]] 1208; CHECK-NEXT: [[SUM4_NONCHR:%.*]] = add i32 [[SUM2]], [[SUM4_NONCHR_V]] 1209; CHECK-NEXT: br label [[BB3]] 1210; CHECK: bb3: 1211; CHECK-NEXT: [[SUM6:%.*]] = phi i32 [ [[SUM0]], [[ENTRY:%.*]] ], [ [[TMP14]], [[BB1]] ], [ [[SUM2]], [[BB0_SPLIT_NONCHR]] ], [ [[SUM4_NONCHR]], [[BB1_NONCHR]] ] 1212; CHECK-NEXT: ret i32 [[SUM6]] 1213; 1214entry: 1215 %0 = load i32, ptr %i 1216 %1 = and i32 %0, 255 1217 %2 = icmp eq i32 %1, 0 1218 br i1 %2, label %bb3, label %bb0, !prof !15 1219 1220bb0: 1221 %3 = and i32 %0, 1 1222 %4 = icmp eq i32 %3, 0 1223 %5 = add i32 %sum0, 42 1224 %sum1 = select i1 %4, i32 %sum0, i32 %5, !prof !15 1225 %6 = and i32 %0, 2 1226 %7 = icmp eq i32 %6, 0 1227 %8 = add i32 %sum1, 43 1228 %sum2 = select i1 %7, i32 %sum1, i32 %8, !prof !15 1229 %9 = load i32, ptr %i 1230 %10 = icmp eq i32 %9, 0 1231 br i1 %10, label %bb2, label %bb1, !prof !15 1232 1233bb1: 1234 %sum3 = add i32 %sum2, 44 1235 %11 = and i32 %0, 8 1236 %12 = icmp eq i32 %11, 0 1237 %13 = add i32 %sum3, 44 1238 %sum4 = select i1 %12, i32 %sum3, i32 %13, !prof !15 1239 br label %bb2 1240 1241bb2: 1242 %sum5 = phi i32 [ %sum2, %bb0 ], [ %sum4, %bb1 ] 1243 br label %bb3 1244 1245bb3: 1246 %sum6 = phi i32 [ %sum0, %entry ], [ %sum5, %bb2 ] 1247 ret i32 %sum6 1248} 1249 1250; In the second CHR, a condition value depends on a trivial phi that's inserted 1251; by the first CHR. 1252; Roughly, 1253; i0 = *i 1254; v2 = (z != 1) ? pred : true // Likely false 1255; if (z == 0 & pred) // Likely false 1256; foo() 1257; j0 = *j 1258; sum2 = ((i0 & 2) == j0) ? sum0 : (sum0 + 43) // Likely false 1259; sum3 = ((i0 == j0) ? sum0 : (sum0 + 43) // Likely false 1260; foo() 1261; if ((i0 & 4) == 0) // Unbiased 1262; foo() 1263; return i0 + sum3 1264; -> 1265; i0 = *i 1266; if (z != 1 & (z == 0 & pred)) // First CHR 1267; foo() 1268; // A trivial phi for i0 is inserted here by the first CHR (which gets removed 1269; // later) and the subsequent branch condition (for the second CHR) uses it. 1270; j0 = *j 1271; if ((i0 & 2) != j0 & i0 != j0) { // Second CHR 1272; sum3 = sum0 + 43 1273; foo() 1274; if (i0 & 4) == 0) 1275; foo() 1276; } else { 1277; sum3 = (i0 == j0) ? sum0 : (sum0 + 43) 1278; foo() 1279; if (i0 & 4) == 0) 1280; foo() 1281; } 1282; return i0 + sum3 1283define i32 @test_chr_14(ptr %i, ptr %j, i32 %sum0, i1 %pred, i32 %z) !prof !14 { 1284; CHECK-LABEL: @test_chr_14( 1285; CHECK-NEXT: entry: 1286; CHECK-NEXT: [[Z_FR:%.*]] = freeze i32 [[Z:%.*]] 1287; CHECK-NEXT: [[I0:%.*]] = load i32, ptr [[I:%.*]], align 4 1288; CHECK-NEXT: [[V1:%.*]] = icmp eq i32 [[Z_FR]], 1 1289; CHECK-NEXT: br i1 [[V1]], label [[BB1:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 1290; CHECK: entry.split.nonchr: 1291; CHECK-NEXT: [[V0:%.*]] = icmp eq i32 [[Z_FR]], 0 1292; CHECK-NEXT: [[V3_NONCHR:%.*]] = and i1 [[V0]], [[PRED:%.*]] 1293; CHECK-NEXT: br i1 [[V3_NONCHR]], label [[BB0_NONCHR:%.*]], label [[BB1]], !prof [[PROF16]] 1294; CHECK: bb0.nonchr: 1295; CHECK-NEXT: call void @foo() 1296; CHECK-NEXT: br label [[BB1]] 1297; CHECK: bb1: 1298; CHECK-NEXT: [[J0:%.*]] = load i32, ptr [[J:%.*]], align 4 1299; CHECK-NEXT: [[V6:%.*]] = and i32 [[I0]], 2 1300; CHECK-NEXT: [[V4:%.*]] = icmp ne i32 [[V6]], [[J0]] 1301; CHECK-NEXT: [[V8:%.*]] = add i32 [[SUM0:%.*]], 43 1302; CHECK-NEXT: [[V5:%.*]] = icmp ne i32 [[I0]], [[J0]] 1303; CHECK-NEXT: [[TMP0:%.*]] = freeze i1 [[V4]] 1304; CHECK-NEXT: [[TMP1:%.*]] = freeze i1 [[V5]] 1305; CHECK-NEXT: [[TMP2:%.*]] = and i1 [[TMP0]], [[TMP1]] 1306; CHECK-NEXT: br i1 [[TMP2]], label [[BB1_SPLIT:%.*]], label [[BB1_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 1307; CHECK: bb1.split: 1308; CHECK-NEXT: call void @foo() 1309; CHECK-NEXT: [[V9:%.*]] = and i32 [[I0]], 4 1310; CHECK-NEXT: [[V10:%.*]] = icmp eq i32 [[V9]], 0 1311; CHECK-NEXT: br i1 [[V10]], label [[BB3:%.*]], label [[BB2:%.*]] 1312; CHECK: bb2: 1313; CHECK-NEXT: call void @foo() 1314; CHECK-NEXT: br label [[BB3]] 1315; CHECK: bb1.split.nonchr: 1316; CHECK-NEXT: [[V5_NONCHR:%.*]] = icmp eq i32 [[I0]], [[J0]] 1317; CHECK-NEXT: [[SUM3_NONCHR:%.*]] = select i1 [[V5_NONCHR]], i32 [[SUM0]], i32 [[V8]], !prof [[PROF16]] 1318; CHECK-NEXT: call void @foo() 1319; CHECK-NEXT: [[V9_NONCHR:%.*]] = and i32 [[I0]], 4 1320; CHECK-NEXT: [[V10_NONCHR:%.*]] = icmp eq i32 [[V9_NONCHR]], 0 1321; CHECK-NEXT: br i1 [[V10_NONCHR]], label [[BB3]], label [[BB2_NONCHR:%.*]] 1322; CHECK: bb2.nonchr: 1323; CHECK-NEXT: call void @foo() 1324; CHECK-NEXT: br label [[BB3]] 1325; CHECK: bb3: 1326; CHECK-NEXT: [[TMP3:%.*]] = phi i32 [ [[V8]], [[BB2]] ], [ [[V8]], [[BB1_SPLIT]] ], [ [[SUM3_NONCHR]], [[BB2_NONCHR]] ], [ [[SUM3_NONCHR]], [[BB1_SPLIT_NONCHR]] ] 1327; CHECK-NEXT: [[V11:%.*]] = add i32 [[I0]], [[TMP3]] 1328; CHECK-NEXT: ret i32 [[V11]] 1329; 1330entry: 1331 %i0 = load i32, ptr %i 1332 %v0 = icmp eq i32 %z, 0 1333 %v1 = icmp ne i32 %z, 1 1334 %v2 = select i1 %v1, i1 %pred, i1 true, !prof !15 1335 %v3 = and i1 %v0, %pred 1336 br i1 %v3, label %bb0, label %bb1, !prof !15 1337 1338bb0: 1339 call void @foo() 1340 br label %bb1 1341 1342bb1: 1343 %j0 = load i32, ptr %j 1344 %v6 = and i32 %i0, 2 1345 %v4 = icmp eq i32 %v6, %j0 1346 %v8 = add i32 %sum0, 43 1347 %sum2 = select i1 %v4, i32 %sum0, i32 %v8, !prof !15 1348 %v5 = icmp eq i32 %i0, %j0 1349 %sum3 = select i1 %v5, i32 %sum0, i32 %v8, !prof !15 1350 call void @foo() 1351 %v9 = and i32 %i0, 4 1352 %v10 = icmp eq i32 %v9, 0 1353 br i1 %v10, label %bb3, label %bb2 1354 1355bb2: 1356 call void @foo() 1357 br label %bb3 1358 1359bb3: 1360 %v11 = add i32 %i0, %sum3 1361 ret i32 %v11 1362} 1363 1364; Branch or selects depends on another select. No CHR happens. 1365; Roughly, 1366; i0 = *i 1367; if (z == 0 & ((z != 1) ? pred : true)) { // Likely false 1368; foo() 1369; j0 = *j 1370; sum2 = ((i0 & 2) == j0) ? sum0 : (sum0 + 43) // Likely false 1371; sum3 = (i0 == sum2) ? sum2 : (sum0 + 43) // Likely false. This depends on the 1372; // previous select. 1373; foo() 1374; if ((i0 & 4) == 0) // Unbiased 1375; foo() 1376; return i0 + sum3 1377; -> 1378; (no change) 1379define i32 @test_chr_15(ptr %i, ptr %j, i32 %sum0, i1 %pred, i32 %z) !prof !14 { 1380; CHECK-LABEL: @test_chr_15( 1381; CHECK-NEXT: entry: 1382; CHECK-NEXT: [[I0:%.*]] = load i32, ptr [[I:%.*]], align 4 1383; CHECK-NEXT: [[V0:%.*]] = icmp eq i32 [[Z:%.*]], 0 1384; CHECK-NEXT: [[V3:%.*]] = select i1 [[V0]], i1 [[PRED:%.*]], i1 false 1385; CHECK-NEXT: br i1 [[V3]], label [[BB0:%.*]], label [[BB1:%.*]], !prof [[PROF16]] 1386; CHECK: bb0: 1387; CHECK-NEXT: call void @foo() 1388; CHECK-NEXT: br label [[BB1]] 1389; CHECK: bb1: 1390; CHECK-NEXT: [[J0:%.*]] = load i32, ptr [[J:%.*]], align 4 1391; CHECK-NEXT: call void @foo() 1392; CHECK-NEXT: [[V9:%.*]] = and i32 [[I0]], 4 1393; CHECK-NEXT: [[V10:%.*]] = icmp eq i32 [[V9]], 0 1394; CHECK-NEXT: br i1 [[V10]], label [[BB3:%.*]], label [[BB2:%.*]] 1395; CHECK: bb2: 1396; CHECK-NEXT: call void @foo() 1397; CHECK-NEXT: br label [[BB3]] 1398; CHECK: bb3: 1399; CHECK-NEXT: [[V6:%.*]] = and i32 [[I0]], 2 1400; CHECK-NEXT: [[V4:%.*]] = icmp eq i32 [[V6]], [[J0]] 1401; CHECK-NEXT: [[V8:%.*]] = add i32 [[SUM0:%.*]], 43 1402; CHECK-NEXT: [[SUM2:%.*]] = select i1 [[V4]], i32 [[SUM0]], i32 [[V8]], !prof [[PROF16]] 1403; CHECK-NEXT: [[V5:%.*]] = icmp eq i32 [[I0]], [[SUM2]] 1404; CHECK-NEXT: [[SUM3:%.*]] = select i1 [[V5]], i32 [[SUM2]], i32 [[V8]], !prof [[PROF16]] 1405; CHECK-NEXT: [[V11:%.*]] = add i32 [[I0]], [[SUM3]] 1406; CHECK-NEXT: ret i32 [[V11]] 1407; 1408entry: 1409 %i0 = load i32, ptr %i 1410 %v0 = icmp eq i32 %z, 0 1411 %v1 = icmp ne i32 %z, 1 1412 %v2 = select i1 %v1, i1 %pred, i1 true, !prof !15 1413 %v3 = and i1 %v0, %v2 1414 br i1 %v3, label %bb0, label %bb1, !prof !15 1415 1416bb0: 1417 call void @foo() 1418 br label %bb1 1419 1420bb1: 1421 %j0 = load i32, ptr %j 1422 %v6 = and i32 %i0, 2 1423 %v4 = icmp eq i32 %v6, %j0 1424 %v8 = add i32 %sum0, 43 1425 %sum2 = select i1 %v4, i32 %sum0, i32 %v8, !prof !15 1426 %v5 = icmp eq i32 %i0, %sum2 1427 %sum3 = select i1 %v5, i32 %sum2, i32 %v8, !prof !15 1428 call void @foo() 1429 %v9 = and i32 %i0, 4 1430 %v10 = icmp eq i32 %v9, 0 1431 br i1 %v10, label %bb3, label %bb2 1432 1433bb2: 1434 call void @foo() 1435 br label %bb3 1436 1437bb3: 1438 %v11 = add i32 %i0, %sum3 1439 ret i32 %v11 1440} 1441 1442; With an existing phi at the exit but a value (%v40) is both alive and is an 1443; operand to a phi at the exit block. 1444; Roughly, 1445; t0 = *i 1446; if ((t0 & 1) != 0) // Likely true 1447; foo() 1448; v40 = t0 + 44 1449; if ((t0 & 2) != 0) // Likely true 1450; v41 = t0 + 99 1451; foo() 1452; } 1453; v42 = phi v40, v41 1454; return v42 + v40 1455; -> 1456; t0 = *i 1457; if ((t0 & 3) == 3) // Likely true 1458; foo() 1459; v40 = t0 + 44 1460; v41 = t0 + 99 1461; foo() 1462; } else { 1463; if ((t0 & 1) != 0) // Likely true 1464; foo() 1465; v40_nc = t0 + 44 1466; if ((t0 & 2) != 0) // Likely true 1467; v41_nc = t0 + 99 1468; foo() 1469; } 1470; } 1471; t7 = phi v40, v40_nc 1472; v42 = phi v41, v41_nc 1473; v43 = v42 + t7 1474; return v43 1475define i32 @test_chr_16(ptr %i) !prof !14 { 1476; CHECK-LABEL: @test_chr_16( 1477; CHECK-NEXT: entry: 1478; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4 1479; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[TMP0]], 3 1480; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 3 1481; CHECK-NEXT: br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 1482; CHECK: bb0: 1483; CHECK-NEXT: call void @foo() 1484; CHECK-NEXT: [[V40:%.*]] = add i32 [[TMP0]], 44 1485; CHECK-NEXT: [[V41:%.*]] = add i32 [[TMP0]], 99 1486; CHECK-NEXT: call void @foo() 1487; CHECK-NEXT: br label [[BB3:%.*]] 1488; CHECK: entry.split.nonchr: 1489; CHECK-NEXT: [[TMP3:%.*]] = and i32 [[TMP0]], 1 1490; CHECK-NEXT: [[DOTNOT:%.*]] = icmp eq i32 [[TMP3]], 0 1491; CHECK-NEXT: br i1 [[DOTNOT]], label [[BB1_NONCHR:%.*]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]] 1492; CHECK: bb0.nonchr: 1493; CHECK-NEXT: call void @foo() 1494; CHECK-NEXT: br label [[BB1_NONCHR]] 1495; CHECK: bb1.nonchr: 1496; CHECK-NEXT: [[V40_NONCHR:%.*]] = add i32 [[TMP0]], 44 1497; CHECK-NEXT: [[TMP4:%.*]] = and i32 [[TMP0]], 2 1498; CHECK-NEXT: [[TMP5:%.*]] = icmp eq i32 [[TMP4]], 0 1499; CHECK-NEXT: br i1 [[TMP5]], label [[BB3]], label [[BB2_NONCHR:%.*]], !prof [[PROF16]] 1500; CHECK: bb2.nonchr: 1501; CHECK-NEXT: [[V41_NONCHR:%.*]] = add i32 [[TMP0]], 99 1502; CHECK-NEXT: call void @foo() 1503; CHECK-NEXT: br label [[BB3]] 1504; CHECK: bb3: 1505; CHECK-NEXT: [[TMP6:%.*]] = phi i32 [ [[V40]], [[BB0]] ], [ [[V40_NONCHR]], [[BB2_NONCHR]] ], [ [[V40_NONCHR]], [[BB1_NONCHR]] ] 1506; CHECK-NEXT: [[V42:%.*]] = phi i32 [ [[V41]], [[BB0]] ], [ [[V41_NONCHR]], [[BB2_NONCHR]] ], [ [[V40_NONCHR]], [[BB1_NONCHR]] ] 1507; CHECK-NEXT: [[V43:%.*]] = add i32 [[V42]], [[TMP6]] 1508; CHECK-NEXT: ret i32 [[V43]] 1509; 1510entry: 1511 %0 = load i32, ptr %i 1512 %1 = and i32 %0, 1 1513 %2 = icmp eq i32 %1, 0 1514 br i1 %2, label %bb1, label %bb0, !prof !15 1515 1516bb0: 1517 call void @foo() 1518 br label %bb1 1519 1520bb1: 1521 %v40 = add i32 %0, 44 1522 %3 = and i32 %0, 2 1523 %4 = icmp eq i32 %3, 0 1524 br i1 %4, label %bb3, label %bb2, !prof !15 1525 1526bb2: 1527 %v41 = add i32 %0, 99 1528 call void @foo() 1529 br label %bb3 1530 1531bb3: 1532 %v42 = phi i32 [ %v41, %bb2 ], [ %v40, %bb1 ] 1533 %v43 = add i32 %v42, %v40 1534 ret i32 %v43 1535} 1536 1537; Two consecutive regions have an entry in the middle of them. No CHR happens. 1538; Roughly, 1539; if ((i & 4) == 0) { 1540; if (!j) 1541; goto bb1 1542; } else { 1543; t0 = (i & 1) 1544; if (t0 != 0) // Likely true 1545; foo() 1546; s = (i & 1) + i 1547; } 1548; bb1: 1549; p = phi i, t0, s 1550; if ((i & 2) != 0) // Likely true 1551; foo() 1552; q = p + 2 1553; } 1554; r = phi p, q, i 1555; return r 1556; -> 1557; (no change) 1558define i32 @test_chr_17(i32 %i, i1 %j) !prof !14 { 1559; CHECK-LABEL: @test_chr_17( 1560; CHECK-NEXT: entry: 1561; CHECK-NEXT: [[V0:%.*]] = and i32 [[I:%.*]], 4 1562; CHECK-NEXT: [[V1:%.*]] = icmp eq i32 [[V0]], 0 1563; CHECK-NEXT: br i1 [[V1]], label [[BBE:%.*]], label [[BBQ:%.*]] 1564; CHECK: bbq: 1565; CHECK-NEXT: br i1 [[J:%.*]], label [[BB3:%.*]], label [[BB1:%.*]] 1566; CHECK: bbe: 1567; CHECK-NEXT: [[TMP0:%.*]] = and i32 [[I]], 1 1568; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 0 1569; CHECK-NEXT: br i1 [[TMP1]], label [[BB1]], label [[BB0:%.*]], !prof [[PROF16]] 1570; CHECK: bb0: 1571; CHECK-NEXT: call void @foo() 1572; CHECK-NEXT: [[S:%.*]] = add i32 [[TMP0]], [[I]] 1573; CHECK-NEXT: br label [[BB1]] 1574; CHECK: bb1: 1575; CHECK-NEXT: [[P:%.*]] = phi i32 [ [[I]], [[BBQ]] ], [ [[TMP0]], [[BBE]] ], [ [[S]], [[BB0]] ] 1576; CHECK-NEXT: [[TMP2:%.*]] = and i32 [[I]], 2 1577; CHECK-NEXT: [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 0 1578; CHECK-NEXT: br i1 [[TMP3]], label [[BB3]], label [[BB2:%.*]], !prof [[PROF16]] 1579; CHECK: bb2: 1580; CHECK-NEXT: call void @foo() 1581; CHECK-NEXT: [[Q:%.*]] = add i32 [[P]], [[TMP2]] 1582; CHECK-NEXT: br label [[BB3]] 1583; CHECK: bb3: 1584; CHECK-NEXT: [[R:%.*]] = phi i32 [ [[P]], [[BB1]] ], [ [[Q]], [[BB2]] ], [ [[I]], [[BBQ]] ] 1585; CHECK-NEXT: ret i32 [[R]] 1586; 1587entry: 1588 %v0 = and i32 %i, 4 1589 %v1 = icmp eq i32 %v0, 0 1590 br i1 %v1, label %bbe, label %bbq 1591 1592bbq: 1593 br i1 %j, label %bb3, label %bb1 1594 1595bbe: 1596 %0 = and i32 %i, 1 1597 %1 = icmp eq i32 %0, 0 1598 br i1 %1, label %bb1, label %bb0, !prof !15 1599 1600bb0: 1601 call void @foo() 1602 %s = add i32 %0, %i 1603 br label %bb1 1604 1605bb1: 1606 %p = phi i32 [ %i, %bbq ], [ %0, %bbe ], [ %s, %bb0 ] 1607 %2 = and i32 %i, 2 1608 %3 = icmp eq i32 %2, 0 1609 br i1 %3, label %bb3, label %bb2, !prof !15 1610 1611bb2: 1612 call void @foo() 1613 %q = add i32 %p, %2 1614 br label %bb3 1615 1616bb3: 1617 %r = phi i32 [ %p, %bb1 ], [ %q, %bb2 ], [ %i, %bbq ] 1618 ret i32 %r 1619} 1620 1621; Select + br, there's a loop and we need to update the user of an inserted phi 1622; at the entry block. This is a regression test for a bug that's fixed. 1623; Roughly, 1624; do { 1625; inc1 = phi inc2, 0 1626; li = *i 1627; sum1 = sum0 + 42 1628; sum2 = ((li & 1) == 0) ? sum0 : sum1 // Likely false 1629; inc2 = inc1 + 1 1630; if ((li & 4) != 0) // Likely true 1631; sum3 = sum2 + 44 1632; sum4 = phi sum1, sum3 1633; } while (inc2 != 100) // Likely true (loop back) 1634; return sum4 1635; -> 1636; do { 1637; inc1 = phi tmp2, 0 // The first operand needed to be updated 1638; li = *i 1639; sum1 = sum0 + 42 1640; if ((li & 5) == 5) { // Likely true 1641; inc2 = inc1 + 1 1642; sum3 = sum0 + 86 1643; } else { 1644; inc2_nc = inc1 + 1 1645; if ((li & 4) == 0) 1646; sum2_nc = ((li & 1) == 0) ? sum0 : sum1 1647; sum3_nc = sum2_nc + 44 1648; } 1649; tmp2 = phi inc2, in2c_nc 1650; sum4 = phi sum3, sum3_nc, sum1 1651; } while (tmp2 != 100) 1652; return sum4 1653define i32 @test_chr_18(ptr %i, i32 %sum0) !prof !14 { 1654; CHECK-LABEL: @test_chr_18( 1655; CHECK-NEXT: entry: 1656; CHECK-NEXT: br label [[BB0:%.*]] 1657; CHECK: bb0: 1658; CHECK-NEXT: [[INC1:%.*]] = phi i32 [ [[TMP2:%.*]], [[BB2:%.*]] ], [ 0, [[ENTRY:%.*]] ] 1659; CHECK-NEXT: [[LI:%.*]] = load i32, ptr [[I:%.*]], align 4 1660; CHECK-NEXT: [[LI_FR:%.*]] = freeze i32 [[LI]] 1661; CHECK-NEXT: [[SUM1:%.*]] = add i32 [[SUM0:%.*]], 42 1662; CHECK-NEXT: [[TMP0:%.*]] = and i32 [[LI_FR]], 5 1663; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 5 1664; CHECK-NEXT: br i1 [[TMP1]], label [[BB1:%.*]], label [[BB0_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 1665; CHECK: bb1: 1666; CHECK-NEXT: [[SUM3:%.*]] = add i32 [[SUM0]], 86 1667; CHECK-NEXT: br label [[BB2]] 1668; CHECK: bb0.split.nonchr: 1669; CHECK-NEXT: [[A4_NONCHR:%.*]] = and i32 [[LI_FR]], 4 1670; CHECK-NEXT: [[CMP4_NONCHR:%.*]] = icmp eq i32 [[A4_NONCHR]], 0 1671; CHECK-NEXT: br i1 [[CMP4_NONCHR]], label [[BB2]], label [[BB1_NONCHR:%.*]], !prof [[PROF16]] 1672; CHECK: bb1.nonchr: 1673; CHECK-NEXT: [[A1:%.*]] = and i32 [[LI_FR]], 1 1674; CHECK-NEXT: [[CMP1_NOT:%.*]] = icmp eq i32 [[A1]], 0 1675; CHECK-NEXT: [[SUM2_NONCHR:%.*]] = select i1 [[CMP1_NOT]], i32 [[SUM0]], i32 [[SUM1]], !prof [[PROF16]] 1676; CHECK-NEXT: [[SUM3_NONCHR:%.*]] = add i32 [[SUM2_NONCHR]], 44 1677; CHECK-NEXT: br label [[BB2]] 1678; CHECK: bb2: 1679; CHECK-NEXT: [[SUM4:%.*]] = phi i32 [ [[SUM3]], [[BB1]] ], [ [[SUM1]], [[BB0_SPLIT_NONCHR]] ], [ [[SUM3_NONCHR]], [[BB1_NONCHR]] ] 1680; CHECK-NEXT: [[TMP2]] = add i32 [[INC1]], 1 1681; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[TMP2]], 100 1682; CHECK-NEXT: br i1 [[CMP]], label [[BB3:%.*]], label [[BB0]], !prof [[PROF16]] 1683; CHECK: bb3: 1684; CHECK-NEXT: ret i32 [[SUM4]] 1685; 1686entry: 1687 br label %bb0 1688 1689bb0: 1690 %inc1 = phi i32 [ %inc2, %bb2 ], [ 0, %entry ] 1691 %li = load i32, ptr %i 1692 %a1 = and i32 %li, 1 1693 %cmp1 = icmp eq i32 %a1, 0 1694 %sum1 = add i32 %sum0, 42 1695 %sum2 = select i1 %cmp1, i32 %sum0, i32 %sum1, !prof !15 1696 %a4 = and i32 %li, 4 1697 %cmp4 = icmp eq i32 %a4, 0 1698 %inc2 = add i32 %inc1, 1 1699 br i1 %cmp4, label %bb2, label %bb1, !prof !15 1700 1701bb1: 1702 %sum3 = add i32 %sum2, 44 1703 br label %bb2 1704 1705bb2: 1706 %sum4 = phi i32 [ %sum1, %bb0 ], [ %sum3, %bb1 ] 1707 %cmp = icmp eq i32 %inc2, 100 1708 br i1 %cmp, label %bb3, label %bb0, !prof !15 1709 1710bb3: 1711 ret i32 %sum4 1712} 1713 1714 1715; Selects + Brs. Those share the condition value, which causes the 1716; targets/operands of the branch/select to be flipped. 1717; Roughly, 1718; t0 = *i 1719; if ((t0 & 255) != 0) { // Likely true 1720; sum1 = ((t0 & 1) == 0) ? sum0 : (sum0 + 42) // Likely false 1721; sum2 = ((t0 & 1) == 0) ? sum1 : (sum1 + 42) // Likely false 1722; if ((t0 & 1) != 0) { // Likely true 1723; sum3 = sum2 + 44 1724; sum4 = ((t0 & 8) == 0) ? sum3 : (sum3 + 44) // Likely false 1725; } 1726; sum5 = phi sum2, sum4 1727; } 1728; sum6 = phi sum0, sum5 1729; return sum6 1730; -> 1731; t0 = *i 1732; if ((t0 & 9) == 9) { // Likely true 1733; tmp3 = sum0 + 85 // Dead 1734; tmp4 = sum0 + 173 1735; } else { 1736; if ((t0 & 255) != 0) { 1737; sum2_nc = ((t0 & 1) == 0) ? sum0 : (sum0 + 85) 1738; sum4_nc_v = ((t0 & 8) == 0) ? 44 : 88 1739; sum4_nc = add sum2_nc + sum4_nc_v 1740; } 1741; } 1742; sum6 = phi tmp4, sum0, sum2_nc, sum4_nc 1743; return sum6 1744define i32 @test_chr_19(ptr %i, i32 %sum0) !prof !14 { 1745; CHECK-LABEL: @test_chr_19( 1746; CHECK-NEXT: entry: 1747; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4 1748; CHECK-NEXT: [[DOTFR1:%.*]] = freeze i32 [[TMP0]] 1749; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[DOTFR1]], 9 1750; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 9 1751; CHECK-NEXT: br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 1752; CHECK: bb0: 1753; CHECK-NEXT: [[TMP3:%.*]] = add i32 [[SUM0:%.*]], 85 1754; CHECK-NEXT: [[TMP4:%.*]] = add i32 [[SUM0]], 173 1755; CHECK-NEXT: br label [[BB3:%.*]] 1756; CHECK: entry.split.nonchr: 1757; CHECK-NEXT: [[TMP5:%.*]] = and i32 [[DOTFR1]], 255 1758; CHECK-NEXT: [[DOTNOT:%.*]] = icmp eq i32 [[TMP5]], 0 1759; CHECK-NEXT: br i1 [[DOTNOT]], label [[BB3]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]] 1760; CHECK: bb0.nonchr: 1761; CHECK-NEXT: [[TMP6:%.*]] = and i32 [[DOTFR1]], 1 1762; CHECK-NEXT: [[TMP7:%.*]] = icmp eq i32 [[TMP6]], 0 1763; CHECK-NEXT: [[TMP8:%.*]] = add i32 [[SUM0]], 85 1764; CHECK-NEXT: [[SUM2_NONCHR:%.*]] = select i1 [[TMP7]], i32 [[SUM0]], i32 [[TMP8]], !prof [[PROF16]] 1765; CHECK-NEXT: [[TMP9:%.*]] = and i32 [[DOTFR1]], 8 1766; CHECK-NEXT: [[TMP10:%.*]] = icmp eq i32 [[TMP9]], 0 1767; CHECK-NEXT: [[SUM4_NONCHR_V:%.*]] = select i1 [[TMP10]], i32 44, i32 88 1768; CHECK-NEXT: [[SUM4_NONCHR:%.*]] = add i32 [[SUM2_NONCHR]], [[SUM4_NONCHR_V]] 1769; CHECK-NEXT: [[SUM5_NONCHR:%.*]] = select i1 [[TMP7]], i32 [[SUM2_NONCHR]], i32 [[SUM4_NONCHR]], !prof [[PROF16]] 1770; CHECK-NEXT: br label [[BB3]] 1771; CHECK: bb3: 1772; CHECK-NEXT: [[SUM6:%.*]] = phi i32 [ [[TMP4]], [[BB0]] ], [ [[SUM0]], [[ENTRY_SPLIT_NONCHR]] ], [ [[SUM5_NONCHR]], [[BB0_NONCHR]] ] 1773; CHECK-NEXT: ret i32 [[SUM6]] 1774; 1775entry: 1776 %0 = load i32, ptr %i 1777 %1 = and i32 %0, 255 1778 %2 = icmp eq i32 %1, 0 1779 br i1 %2, label %bb3, label %bb0, !prof !15 1780 1781bb0: 1782 %3 = and i32 %0, 1 1783 %4 = icmp eq i32 %3, 0 1784 %5 = add i32 %sum0, 42 1785 %sum1 = select i1 %4, i32 %sum0, i32 %5, !prof !15 1786 %6 = add i32 %sum1, 43 1787 %sum2 = select i1 %4, i32 %sum1, i32 %6, !prof !15 1788 br i1 %4, label %bb2, label %bb1, !prof !15 1789 1790bb1: 1791 %sum3 = add i32 %sum2, 44 1792 %7 = and i32 %0, 8 1793 %8 = icmp eq i32 %7, 0 1794 %9 = add i32 %sum3, 44 1795 %sum4 = select i1 %8, i32 %sum3, i32 %9, !prof !15 1796 br label %bb2 1797 1798bb2: 1799 %sum5 = phi i32 [ %sum2, %bb0 ], [ %sum4, %bb1 ] 1800 br label %bb3 1801 1802bb3: 1803 %sum6 = phi i32 [ %sum0, %entry ], [ %sum5, %bb2 ] 1804 ret i32 %sum6 1805} 1806 1807; Selects. The exit block, which belongs to the top-level region, has a select 1808; and causes the top-level region to be the outermost CHR scope with the 1809; subscope that includes the entry block with two selects. The outermost CHR 1810; scope doesn't see the selects in the entry block as the entry block is in the 1811; subscope and incorrectly sets the CHR hoist point to the branch rather than 1812; the first select in the entry block and causes the CHR'ed selects ("select i1 1813; false...") to incorrectly position above the CHR branch. This is testing 1814; against a quirk of how the region analysis handles the entry block. 1815; Roughly, 1816; i0 = *i 1817; sum2 = ((i0 & 2) == 0) ? sum0 : (sum0 + 43) // Likely false 1818; sum3 = ((i0 & 4) == 0) ? sum2 : (sum2 + 44) // Likely false 1819; if (j) 1820; foo() 1821; i5 = *i 1822; v13 = (i5 == 44) ? i5 : sum3 1823; return v13 1824; -> 1825; i0 = *i 1826; if ((i0 & 6) != 6) { // Likely true 1827; v9 = sum0 + 87 1828; if (j) 1829; foo() 1830; } else { 1831; sum2.nc = ((i0 & 2) == 0) ? sum0 : (sum0 + 43) 1832; sum3.nc = ((i0 & 4) == 0) ? sum2.nc : (sum2.nc + 44) 1833; if (j) 1834; foo() 1835; } 1836; t2 = phi v9, sum3.nc 1837; i5 = *i 1838; v13 = (i5 == 44) ? 44 : t2 1839; return v13 1840define i32 @test_chr_20(ptr %i, i32 %sum0, i1 %j) !prof !14 { 1841; CHECK-LABEL: @test_chr_20( 1842; CHECK-NEXT: entry: 1843; CHECK-NEXT: [[I0:%.*]] = load i32, ptr [[I:%.*]], align 4 1844; CHECK-NEXT: [[I0_FR:%.*]] = freeze i32 [[I0]] 1845; CHECK-NEXT: [[TMP0:%.*]] = and i32 [[I0_FR]], 6 1846; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 6 1847; CHECK-NEXT: br i1 [[TMP1]], label [[ENTRY_SPLIT:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 1848; CHECK: entry.split: 1849; CHECK-NEXT: [[V9:%.*]] = add i32 [[SUM0:%.*]], 87 1850; CHECK-NEXT: br i1 [[J:%.*]], label [[BB1:%.*]], label [[BB4:%.*]] 1851; CHECK: bb1: 1852; CHECK-NEXT: call void @foo() 1853; CHECK-NEXT: br label [[BB4]] 1854; CHECK: entry.split.nonchr: 1855; CHECK-NEXT: [[V8:%.*]] = add i32 [[SUM0]], 43 1856; CHECK-NEXT: [[V3:%.*]] = and i32 [[I0_FR]], 2 1857; CHECK-NEXT: [[V4_NOT:%.*]] = icmp eq i32 [[V3]], 0 1858; CHECK-NEXT: [[SUM2_NONCHR:%.*]] = select i1 [[V4_NOT]], i32 [[SUM0]], i32 [[V8]], !prof [[PROF16]] 1859; CHECK-NEXT: [[V6_NONCHR:%.*]] = and i32 [[I0_FR]], 4 1860; CHECK-NEXT: [[V5_NONCHR:%.*]] = icmp eq i32 [[V6_NONCHR]], 0 1861; CHECK-NEXT: [[V9_NONCHR:%.*]] = add i32 [[SUM2_NONCHR]], 44 1862; CHECK-NEXT: [[SUM3_NONCHR:%.*]] = select i1 [[V5_NONCHR]], i32 [[SUM2_NONCHR]], i32 [[V9_NONCHR]], !prof [[PROF16]] 1863; CHECK-NEXT: br i1 [[J]], label [[BB1_NONCHR:%.*]], label [[BB4]] 1864; CHECK: bb1.nonchr: 1865; CHECK-NEXT: call void @foo() 1866; CHECK-NEXT: br label [[BB4]] 1867; CHECK: bb4: 1868; CHECK-NEXT: [[TMP2:%.*]] = phi i32 [ [[V9]], [[BB1]] ], [ [[V9]], [[ENTRY_SPLIT]] ], [ [[SUM3_NONCHR]], [[BB1_NONCHR]] ], [ [[SUM3_NONCHR]], [[ENTRY_SPLIT_NONCHR]] ] 1869; CHECK-NEXT: [[I5:%.*]] = load i32, ptr [[I]], align 4 1870; CHECK-NEXT: [[V12:%.*]] = icmp eq i32 [[I5]], 44 1871; CHECK-NEXT: [[V13:%.*]] = select i1 [[V12]], i32 44, i32 [[TMP2]], !prof [[PROF16]] 1872; CHECK-NEXT: ret i32 [[V13]] 1873; 1874entry: 1875 %i0 = load i32, ptr %i 1876 %v3 = and i32 %i0, 2 1877 %v4 = icmp eq i32 %v3, 0 1878 %v8 = add i32 %sum0, 43 1879 %sum2 = select i1 %v4, i32 %sum0, i32 %v8, !prof !15 1880 %v6 = and i32 %i0, 4 1881 %v5 = icmp eq i32 %v6, 0 1882 %v9 = add i32 %sum2, 44 1883 %sum3 = select i1 %v5, i32 %sum2, i32 %v9, !prof !15 1884 br i1 %j, label %bb1, label %bb4 1885 1886bb1: 1887 call void @foo() 1888 br label %bb4 1889 1890bb4: 1891 %i5 = load i32, ptr %i 1892 %v12 = icmp eq i32 %i5, 44 1893 %v13 = select i1 %v12, i32 %i5, i32 %sum3, !prof !15 1894 ret i32 %v13 1895} 1896 1897; Test the case where two scopes share a common instruction to hoist (%cmp.i). 1898; Two scopes would hoist it to their hoist points, but since the outer scope 1899; hoists (entry/bb6-9) it first to its hoist point, it'd be wrong (causing bad 1900; IR) for the inner scope (bb1-4) to hoist the same instruction to its hoist 1901; point. 1902; Roughly, 1903; if (j != k) { 1904; if (i != 2) 1905; foo(); 1906; cmp.i = i == 86 1907; if (!cmp.i) 1908; foo(); 1909; if (j != i) 1910; foo(); 1911; if (!cmp.i) 1912; foo(); 1913; } 1914; return 45; 1915define i32 @test_chr_21(i64 %i, i64 %k, i64 %j) !prof !14 { 1916; CHECK-LABEL: @test_chr_21( 1917; CHECK-NEXT: entry: 1918; CHECK-NEXT: [[CMP0:%.*]] = icmp ne i64 [[J:%.*]], [[K:%.*]] 1919; CHECK-NEXT: [[CMP3:%.*]] = icmp ne i64 [[J]], [[I:%.*]] 1920; CHECK-NEXT: [[CMP_I:%.*]] = icmp ne i64 [[I]], 86 1921; CHECK-NEXT: [[TMP0:%.*]] = select i1 [[CMP0]], i1 [[CMP3]], i1 false 1922; CHECK-NEXT: [[TMP1:%.*]] = select i1 [[TMP0]], i1 [[CMP_I]], i1 false 1923; CHECK-NEXT: br i1 [[TMP1]], label [[BB1:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 1924; CHECK: bb1: 1925; CHECK-NEXT: [[CMP2:%.*]] = icmp ne i64 [[I]], 2 1926; CHECK-NEXT: switch i64 [[I]], label [[BB2:%.*]] [ 1927; CHECK-NEXT: i64 2, label [[BB3_NONCHR2:%.*]] 1928; CHECK-NEXT: i64 86, label [[BB2_NONCHR1:%.*]] 1929; CHECK-NEXT: ], !prof [[PROF19:![0-9]+]] 1930; CHECK: bb2: 1931; CHECK-NEXT: call void @foo() 1932; CHECK-NEXT: call void @foo() 1933; CHECK-NEXT: br label [[BB7:%.*]] 1934; CHECK: bb2.nonchr1: 1935; CHECK-NEXT: call void @foo() 1936; CHECK-NEXT: br label [[BB3_NONCHR2]] 1937; CHECK: bb3.nonchr2: 1938; CHECK-NEXT: br i1 [[CMP_I]], label [[BB4_NONCHR3:%.*]], label [[BB7]], !prof [[PROF18]] 1939; CHECK: bb4.nonchr3: 1940; CHECK-NEXT: call void @foo() 1941; CHECK-NEXT: br label [[BB7]] 1942; CHECK: bb7: 1943; CHECK-NEXT: call void @foo() 1944; CHECK-NEXT: call void @foo() 1945; CHECK-NEXT: br label [[BB10:%.*]] 1946; CHECK: entry.split.nonchr: 1947; CHECK-NEXT: br i1 [[CMP0]], label [[BB1_NONCHR:%.*]], label [[BB10]], !prof [[PROF18]] 1948; CHECK: bb1.nonchr: 1949; CHECK-NEXT: [[CMP2_NONCHR:%.*]] = icmp eq i64 [[I]], 2 1950; CHECK-NEXT: br i1 [[CMP2_NONCHR]], label [[BB3_NONCHR:%.*]], label [[BB2_NONCHR:%.*]], !prof [[PROF16]] 1951; CHECK: bb3.nonchr: 1952; CHECK-NEXT: [[CMP_I_NONCHR:%.*]] = icmp eq i64 [[I]], 86 1953; CHECK-NEXT: br i1 [[CMP_I_NONCHR]], label [[BB6_NONCHR:%.*]], label [[BB4_NONCHR:%.*]], !prof [[PROF16]] 1954; CHECK: bb6.nonchr: 1955; CHECK-NEXT: [[CMP3_NONCHR:%.*]] = icmp eq i64 [[J]], [[I]] 1956; CHECK-NEXT: br i1 [[CMP3_NONCHR]], label [[BB8_NONCHR:%.*]], label [[BB7_NONCHR:%.*]], !prof [[PROF16]] 1957; CHECK: bb8.nonchr: 1958; CHECK-NEXT: br i1 [[CMP_I_NONCHR]], label [[BB10]], label [[BB9_NONCHR:%.*]], !prof [[PROF16]] 1959; CHECK: bb9.nonchr: 1960; CHECK-NEXT: call void @foo() 1961; CHECK-NEXT: br label [[BB10]] 1962; CHECK: bb7.nonchr: 1963; CHECK-NEXT: call void @foo() 1964; CHECK-NEXT: br label [[BB8_NONCHR]] 1965; CHECK: bb4.nonchr: 1966; CHECK-NEXT: call void @foo() 1967; CHECK-NEXT: br label [[BB6_NONCHR]] 1968; CHECK: bb2.nonchr: 1969; CHECK-NEXT: call void @foo() 1970; CHECK-NEXT: br label [[BB3_NONCHR]] 1971; CHECK: bb10: 1972; CHECK-NEXT: ret i32 45 1973; 1974entry: 1975 %cmp0 = icmp eq i64 %j, %k 1976 br i1 %cmp0, label %bb10, label %bb1, !prof !15 1977 1978bb1: 1979 %cmp2 = icmp eq i64 %i, 2 1980 br i1 %cmp2, label %bb3, label %bb2, !prof !15 1981 1982bb2: 1983 call void @foo() 1984 br label %bb3 1985 1986bb3: 1987 %cmp.i = icmp eq i64 %i, 86 1988 br i1 %cmp.i, label %bb5, label %bb4, !prof !15 1989 1990bb4: 1991 call void @foo() 1992 br label %bb5 1993 1994bb5: 1995 br label %bb6 1996 1997bb6: 1998 %cmp3 = icmp eq i64 %j, %i 1999 br i1 %cmp3, label %bb8, label %bb7, !prof !15 2000 2001bb7: 2002 call void @foo() 2003 br label %bb8 2004 2005bb8: 2006 br i1 %cmp.i, label %bb10, label %bb9, !prof !15 2007 2008bb9: 2009 call void @foo() 2010 br label %bb10 2011 2012bb10: 2013 ret i32 45 2014} 2015 2016; Test a case with a really long use-def chains. This test checks that it's not 2017; really slow and doesn't appear to be hanging. 2018define i64 @test_chr_22(i1 %i, ptr %j, i64 %v0) !prof !14 { 2019; CHECK-LABEL: @test_chr_22( 2020; CHECK-NEXT: bb0: 2021; CHECK-NEXT: [[V0_FR:%.*]] = freeze i64 [[V0:%.*]] 2022; CHECK-NEXT: [[REASS_ADD:%.*]] = shl i64 [[V0_FR]], 1 2023; CHECK-NEXT: [[V2:%.*]] = add i64 [[REASS_ADD]], 3 2024; CHECK-NEXT: [[C1:%.*]] = icmp slt i64 [[V2]], 100 2025; CHECK-NEXT: br i1 [[C1]], label [[BB0_SPLIT:%.*]], label [[BB0_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 2026; CHECK: common.ret: 2027; CHECK-NEXT: [[COMMON_RET_OP:%.*]] = phi i64 [ 99, [[BB0_SPLIT]] ], [ 99, [[BB0_SPLIT_NONCHR]] ] 2028; CHECK-NEXT: ret i64 [[COMMON_RET_OP]] 2029; CHECK: bb0.split: 2030; CHECK-NEXT: [[V299:%.*]] = mul i64 [[V2]], 7860086430977039991 2031; CHECK-NEXT: store i64 [[V299]], ptr [[J:%.*]], align 4 2032; CHECK-NEXT: br label [[COMMON_RET:%.*]] 2033; CHECK: bb0.split.nonchr: 2034; CHECK-NEXT: [[V299_NONCHR:%.*]] = mul i64 [[V2]], 7860086430977039991 2035; CHECK-NEXT: store i64 [[V299_NONCHR]], ptr [[J]], align 4 2036; CHECK-NEXT: br label [[COMMON_RET]] 2037; 2038bb0: 2039 %v1 = add i64 %v0, 3 2040 %v2 = add i64 %v1, %v0 2041 %c1 = icmp sgt i64 %v2, 99 2042 %v3 = select i1 %c1, i64 %v1, i64 %v2, !prof !15 2043 %v4 = add i64 %v2, %v2 2044 %v5 = add i64 %v4, %v2 2045 %v6 = add i64 %v5, %v4 2046 %v7 = add i64 %v6, %v5 2047 %v8 = add i64 %v7, %v6 2048 %v9 = add i64 %v8, %v7 2049 %v10 = add i64 %v9, %v8 2050 %v11 = add i64 %v10, %v9 2051 %v12 = add i64 %v11, %v10 2052 %v13 = add i64 %v12, %v11 2053 %v14 = add i64 %v13, %v12 2054 %v15 = add i64 %v14, %v13 2055 %v16 = add i64 %v15, %v14 2056 %v17 = add i64 %v16, %v15 2057 %v18 = add i64 %v17, %v16 2058 %v19 = add i64 %v18, %v17 2059 %v20 = add i64 %v19, %v18 2060 %v21 = add i64 %v20, %v19 2061 %v22 = add i64 %v21, %v20 2062 %v23 = add i64 %v22, %v21 2063 %v24 = add i64 %v23, %v22 2064 %v25 = add i64 %v24, %v23 2065 %v26 = add i64 %v25, %v24 2066 %v27 = add i64 %v26, %v25 2067 %v28 = add i64 %v27, %v26 2068 %v29 = add i64 %v28, %v27 2069 %v30 = add i64 %v29, %v28 2070 %v31 = add i64 %v30, %v29 2071 %v32 = add i64 %v31, %v30 2072 %v33 = add i64 %v32, %v31 2073 %v34 = add i64 %v33, %v32 2074 %v35 = add i64 %v34, %v33 2075 %v36 = add i64 %v35, %v34 2076 %v37 = add i64 %v36, %v35 2077 %v38 = add i64 %v37, %v36 2078 %v39 = add i64 %v38, %v37 2079 %v40 = add i64 %v39, %v38 2080 %v41 = add i64 %v40, %v39 2081 %v42 = add i64 %v41, %v40 2082 %v43 = add i64 %v42, %v41 2083 %v44 = add i64 %v43, %v42 2084 %v45 = add i64 %v44, %v43 2085 %v46 = add i64 %v45, %v44 2086 %v47 = add i64 %v46, %v45 2087 %v48 = add i64 %v47, %v46 2088 %v49 = add i64 %v48, %v47 2089 %v50 = add i64 %v49, %v48 2090 %v51 = add i64 %v50, %v49 2091 %v52 = add i64 %v51, %v50 2092 %v53 = add i64 %v52, %v51 2093 %v54 = add i64 %v53, %v52 2094 %v55 = add i64 %v54, %v53 2095 %v56 = add i64 %v55, %v54 2096 %v57 = add i64 %v56, %v55 2097 %v58 = add i64 %v57, %v56 2098 %v59 = add i64 %v58, %v57 2099 %v60 = add i64 %v59, %v58 2100 %v61 = add i64 %v60, %v59 2101 %v62 = add i64 %v61, %v60 2102 %v63 = add i64 %v62, %v61 2103 %v64 = add i64 %v63, %v62 2104 %v65 = add i64 %v64, %v63 2105 %v66 = add i64 %v65, %v64 2106 %v67 = add i64 %v66, %v65 2107 %v68 = add i64 %v67, %v66 2108 %v69 = add i64 %v68, %v67 2109 %v70 = add i64 %v69, %v68 2110 %v71 = add i64 %v70, %v69 2111 %v72 = add i64 %v71, %v70 2112 %v73 = add i64 %v72, %v71 2113 %v74 = add i64 %v73, %v72 2114 %v75 = add i64 %v74, %v73 2115 %v76 = add i64 %v75, %v74 2116 %v77 = add i64 %v76, %v75 2117 %v78 = add i64 %v77, %v76 2118 %v79 = add i64 %v78, %v77 2119 %v80 = add i64 %v79, %v78 2120 %v81 = add i64 %v80, %v79 2121 %v82 = add i64 %v81, %v80 2122 %v83 = add i64 %v82, %v81 2123 %v84 = add i64 %v83, %v82 2124 %v85 = add i64 %v84, %v83 2125 %v86 = add i64 %v85, %v84 2126 %v87 = add i64 %v86, %v85 2127 %v88 = add i64 %v87, %v86 2128 %v89 = add i64 %v88, %v87 2129 %v90 = add i64 %v89, %v88 2130 %v91 = add i64 %v90, %v89 2131 %v92 = add i64 %v91, %v90 2132 %v93 = add i64 %v92, %v91 2133 %v94 = add i64 %v93, %v92 2134 %v95 = add i64 %v94, %v93 2135 %v96 = add i64 %v95, %v94 2136 %v97 = add i64 %v96, %v95 2137 %v98 = add i64 %v97, %v96 2138 %v99 = add i64 %v98, %v97 2139 %v100 = add i64 %v99, %v98 2140 %v101 = add i64 %v100, %v99 2141 %v102 = add i64 %v101, %v100 2142 %v103 = add i64 %v102, %v101 2143 %v104 = add i64 %v103, %v102 2144 %v105 = add i64 %v104, %v103 2145 %v106 = add i64 %v105, %v104 2146 %v107 = add i64 %v106, %v105 2147 %v108 = add i64 %v107, %v106 2148 %v109 = add i64 %v108, %v107 2149 %v110 = add i64 %v109, %v108 2150 %v111 = add i64 %v110, %v109 2151 %v112 = add i64 %v111, %v110 2152 %v113 = add i64 %v112, %v111 2153 %v114 = add i64 %v113, %v112 2154 %v115 = add i64 %v114, %v113 2155 %v116 = add i64 %v115, %v114 2156 %v117 = add i64 %v116, %v115 2157 %v118 = add i64 %v117, %v116 2158 %v119 = add i64 %v118, %v117 2159 %v120 = add i64 %v119, %v118 2160 %v121 = add i64 %v120, %v119 2161 %v122 = add i64 %v121, %v120 2162 %v123 = add i64 %v122, %v121 2163 %v124 = add i64 %v123, %v122 2164 %v125 = add i64 %v124, %v123 2165 %v126 = add i64 %v125, %v124 2166 %v127 = add i64 %v126, %v125 2167 %v128 = add i64 %v127, %v126 2168 %v129 = add i64 %v128, %v127 2169 %v130 = add i64 %v129, %v128 2170 %v131 = add i64 %v130, %v129 2171 %v132 = add i64 %v131, %v130 2172 %v133 = add i64 %v132, %v131 2173 %v134 = add i64 %v133, %v132 2174 %v135 = add i64 %v134, %v133 2175 %v136 = add i64 %v135, %v134 2176 %v137 = add i64 %v136, %v135 2177 %v138 = add i64 %v137, %v136 2178 %v139 = add i64 %v138, %v137 2179 %v140 = add i64 %v139, %v138 2180 %v141 = add i64 %v140, %v139 2181 %v142 = add i64 %v141, %v140 2182 %v143 = add i64 %v142, %v141 2183 %v144 = add i64 %v143, %v142 2184 %v145 = add i64 %v144, %v143 2185 %v146 = add i64 %v145, %v144 2186 %v147 = add i64 %v146, %v145 2187 %v148 = add i64 %v147, %v146 2188 %v149 = add i64 %v148, %v147 2189 %v150 = add i64 %v149, %v148 2190 %v151 = add i64 %v150, %v149 2191 %v152 = add i64 %v151, %v150 2192 %v153 = add i64 %v152, %v151 2193 %v154 = add i64 %v153, %v152 2194 %v155 = add i64 %v154, %v153 2195 %v156 = add i64 %v155, %v154 2196 %v157 = add i64 %v156, %v155 2197 %v158 = add i64 %v157, %v156 2198 %v159 = add i64 %v158, %v157 2199 %v160 = add i64 %v159, %v158 2200 %v161 = add i64 %v160, %v159 2201 %v162 = add i64 %v161, %v160 2202 %v163 = add i64 %v162, %v161 2203 %v164 = add i64 %v163, %v162 2204 %v165 = add i64 %v164, %v163 2205 %v166 = add i64 %v165, %v164 2206 %v167 = add i64 %v166, %v165 2207 %v168 = add i64 %v167, %v166 2208 %v169 = add i64 %v168, %v167 2209 %v170 = add i64 %v169, %v168 2210 %v171 = add i64 %v170, %v169 2211 %v172 = add i64 %v171, %v170 2212 %v173 = add i64 %v172, %v171 2213 %v174 = add i64 %v173, %v172 2214 %v175 = add i64 %v174, %v173 2215 %v176 = add i64 %v175, %v174 2216 %v177 = add i64 %v176, %v175 2217 %v178 = add i64 %v177, %v176 2218 %v179 = add i64 %v178, %v177 2219 %v180 = add i64 %v179, %v178 2220 %v181 = add i64 %v180, %v179 2221 %v182 = add i64 %v181, %v180 2222 %v183 = add i64 %v182, %v181 2223 %v184 = add i64 %v183, %v182 2224 %v185 = add i64 %v184, %v183 2225 %v186 = add i64 %v185, %v184 2226 %v187 = add i64 %v186, %v185 2227 %v188 = add i64 %v187, %v186 2228 %v189 = add i64 %v188, %v187 2229 %v190 = add i64 %v189, %v188 2230 %v191 = add i64 %v190, %v189 2231 %v192 = add i64 %v191, %v190 2232 %v193 = add i64 %v192, %v191 2233 %v194 = add i64 %v193, %v192 2234 %v195 = add i64 %v194, %v193 2235 %v196 = add i64 %v195, %v194 2236 %v197 = add i64 %v196, %v195 2237 %v198 = add i64 %v197, %v196 2238 %v199 = add i64 %v198, %v197 2239 %v200 = add i64 %v199, %v198 2240 %v201 = add i64 %v200, %v199 2241 %v202 = add i64 %v201, %v200 2242 %v203 = add i64 %v202, %v201 2243 %v204 = add i64 %v203, %v202 2244 %v205 = add i64 %v204, %v203 2245 %v206 = add i64 %v205, %v204 2246 %v207 = add i64 %v206, %v205 2247 %v208 = add i64 %v207, %v206 2248 %v209 = add i64 %v208, %v207 2249 %v210 = add i64 %v209, %v208 2250 %v211 = add i64 %v210, %v209 2251 %v212 = add i64 %v211, %v210 2252 %v213 = add i64 %v212, %v211 2253 %v214 = add i64 %v213, %v212 2254 %v215 = add i64 %v214, %v213 2255 %v216 = add i64 %v215, %v214 2256 %v217 = add i64 %v216, %v215 2257 %v218 = add i64 %v217, %v216 2258 %v219 = add i64 %v218, %v217 2259 %v220 = add i64 %v219, %v218 2260 %v221 = add i64 %v220, %v219 2261 %v222 = add i64 %v221, %v220 2262 %v223 = add i64 %v222, %v221 2263 %v224 = add i64 %v223, %v222 2264 %v225 = add i64 %v224, %v223 2265 %v226 = add i64 %v225, %v224 2266 %v227 = add i64 %v226, %v225 2267 %v228 = add i64 %v227, %v226 2268 %v229 = add i64 %v228, %v227 2269 %v230 = add i64 %v229, %v228 2270 %v231 = add i64 %v230, %v229 2271 %v232 = add i64 %v231, %v230 2272 %v233 = add i64 %v232, %v231 2273 %v234 = add i64 %v233, %v232 2274 %v235 = add i64 %v234, %v233 2275 %v236 = add i64 %v235, %v234 2276 %v237 = add i64 %v236, %v235 2277 %v238 = add i64 %v237, %v236 2278 %v239 = add i64 %v238, %v237 2279 %v240 = add i64 %v239, %v238 2280 %v241 = add i64 %v240, %v239 2281 %v242 = add i64 %v241, %v240 2282 %v243 = add i64 %v242, %v241 2283 %v244 = add i64 %v243, %v242 2284 %v245 = add i64 %v244, %v243 2285 %v246 = add i64 %v245, %v244 2286 %v247 = add i64 %v246, %v245 2287 %v248 = add i64 %v247, %v246 2288 %v249 = add i64 %v248, %v247 2289 %v250 = add i64 %v249, %v248 2290 %v251 = add i64 %v250, %v249 2291 %v252 = add i64 %v251, %v250 2292 %v253 = add i64 %v252, %v251 2293 %v254 = add i64 %v253, %v252 2294 %v255 = add i64 %v254, %v253 2295 %v256 = add i64 %v255, %v254 2296 %v257 = add i64 %v256, %v255 2297 %v258 = add i64 %v257, %v256 2298 %v259 = add i64 %v258, %v257 2299 %v260 = add i64 %v259, %v258 2300 %v261 = add i64 %v260, %v259 2301 %v262 = add i64 %v261, %v260 2302 %v263 = add i64 %v262, %v261 2303 %v264 = add i64 %v263, %v262 2304 %v265 = add i64 %v264, %v263 2305 %v266 = add i64 %v265, %v264 2306 %v267 = add i64 %v266, %v265 2307 %v268 = add i64 %v267, %v266 2308 %v269 = add i64 %v268, %v267 2309 %v270 = add i64 %v269, %v268 2310 %v271 = add i64 %v270, %v269 2311 %v272 = add i64 %v271, %v270 2312 %v273 = add i64 %v272, %v271 2313 %v274 = add i64 %v273, %v272 2314 %v275 = add i64 %v274, %v273 2315 %v276 = add i64 %v275, %v274 2316 %v277 = add i64 %v276, %v275 2317 %v278 = add i64 %v277, %v276 2318 %v279 = add i64 %v278, %v277 2319 %v280 = add i64 %v279, %v278 2320 %v281 = add i64 %v280, %v279 2321 %v282 = add i64 %v281, %v280 2322 %v283 = add i64 %v282, %v281 2323 %v284 = add i64 %v283, %v282 2324 %v285 = add i64 %v284, %v283 2325 %v286 = add i64 %v285, %v284 2326 %v287 = add i64 %v286, %v285 2327 %v288 = add i64 %v287, %v286 2328 %v289 = add i64 %v288, %v287 2329 %v290 = add i64 %v289, %v288 2330 %v291 = add i64 %v290, %v289 2331 %v292 = add i64 %v291, %v290 2332 %v293 = add i64 %v292, %v291 2333 %v294 = add i64 %v293, %v292 2334 %v295 = add i64 %v294, %v293 2335 %v296 = add i64 %v295, %v294 2336 %v297 = add i64 %v296, %v295 2337 %v298 = add i64 %v297, %v296 2338 %v299 = add i64 %v298, %v297 2339 %v300 = add i64 %v299, %v298 2340 %v301 = icmp eq i64 %v300, 100 2341 %v302 = select i1 %v301, i64 %v298, i64 %v299, !prof !15 2342 store i64 %v302, ptr %j 2343 ret i64 99 2344} 2345 2346; Test a case with a really long use-def chains. This test checks that it's not 2347; really slow and doesn't appear to be hanging. This is different from 2348; test_chr_22 in that it has nested control structures (multiple scopes) and 2349; covers additional code. 2350define i64 @test_chr_23(i64 %v0) !prof !14 { 2351; CHECK-LABEL: @test_chr_23( 2352; CHECK-NEXT: entry: 2353; CHECK-NEXT: [[TMP0:%.*]] = mul i64 [[V0:%.*]], 50 2354; CHECK-NEXT: [[V10_NOT:%.*]] = icmp eq i64 [[TMP0]], -50 2355; CHECK-NEXT: ret i64 99 2356; 2357entry: 2358 %v1 = add i64 %v0, 3 2359 %v2 = add i64 %v1, %v1 2360 %v3 = add i64 %v2, %v1 2361 %v4 = add i64 %v2, %v3 2362 %v5 = add i64 %v4, %v2 2363 %v6 = add i64 %v5, %v4 2364 %v7 = add i64 %v6, %v5 2365 %v8 = add i64 %v7, %v6 2366 %v9 = add i64 %v8, %v7 2367 %v10 = icmp eq i64 %v9, 100 2368 br i1 %v10, label %body, label %end, !prof !15 2369 2370body: 2371 %v1_0 = add i64 %v9, 3 2372 %v2_0 = add i64 %v1_0, %v1_0 2373 %v3_0 = add i64 %v2_0, %v1_0 2374 %v4_0 = add i64 %v2_0, %v3_0 2375 %v5_0 = add i64 %v4_0, %v2_0 2376 %v6_0 = add i64 %v5_0, %v4_0 2377 %v7_0 = add i64 %v6_0, %v5_0 2378 %v8_0 = add i64 %v7_0, %v6_0 2379 %v9_0 = add i64 %v8_0, %v7_0 2380 %v10_0 = icmp eq i64 %v9_0, 100 2381 br i1 %v10_0, label %body.1, label %end, !prof !15 2382 2383body.1: 2384 %v1_1 = add i64 %v9_0, 3 2385 %v2_1 = add i64 %v1_1, %v1_1 2386 %v3_1 = add i64 %v2_1, %v1_1 2387 %v4_1 = add i64 %v2_1, %v3_1 2388 %v5_1 = add i64 %v4_1, %v2_1 2389 %v6_1 = add i64 %v5_1, %v4_1 2390 %v7_1 = add i64 %v6_1, %v5_1 2391 %v8_1 = add i64 %v7_1, %v6_1 2392 %v9_1 = add i64 %v8_1, %v7_1 2393 %v10_1 = icmp eq i64 %v9_1, 100 2394 br i1 %v10_1, label %body.2, label %end, !prof !15 2395 2396body.2: 2397 %v1_2 = add i64 %v9_1, 3 2398 %v2_2 = add i64 %v1_2, %v1_2 2399 %v3_2 = add i64 %v2_2, %v1_2 2400 %v4_2 = add i64 %v2_2, %v3_2 2401 %v5_2 = add i64 %v4_2, %v2_2 2402 %v6_2 = add i64 %v5_2, %v4_2 2403 %v7_2 = add i64 %v6_2, %v5_2 2404 %v8_2 = add i64 %v7_2, %v6_2 2405 %v9_2 = add i64 %v8_2, %v7_2 2406 %v10_2 = icmp eq i64 %v9_2, 100 2407 br i1 %v10_2, label %body.3, label %end, !prof !15 2408 2409body.3: 2410 %v1_3 = add i64 %v9_2, 3 2411 %v2_3 = add i64 %v1_3, %v1_3 2412 %v3_3 = add i64 %v2_3, %v1_3 2413 %v4_3 = add i64 %v2_3, %v3_3 2414 %v5_3 = add i64 %v4_3, %v2_3 2415 %v6_3 = add i64 %v5_3, %v4_3 2416 %v7_3 = add i64 %v6_3, %v5_3 2417 %v8_3 = add i64 %v7_3, %v6_3 2418 %v9_3 = add i64 %v8_3, %v7_3 2419 %v10_3 = icmp eq i64 %v9_3, 100 2420 br i1 %v10_3, label %body.4, label %end, !prof !15 2421 2422body.4: 2423 %v1_4 = add i64 %v9_3, 3 2424 %v2_4 = add i64 %v1_4, %v1_4 2425 %v3_4 = add i64 %v2_4, %v1_4 2426 %v4_4 = add i64 %v2_4, %v3_4 2427 %v5_4 = add i64 %v4_4, %v2_4 2428 %v6_4 = add i64 %v5_4, %v4_4 2429 %v7_4 = add i64 %v6_4, %v5_4 2430 %v8_4 = add i64 %v7_4, %v6_4 2431 %v9_4 = add i64 %v8_4, %v7_4 2432 %v10_4 = icmp eq i64 %v9_4, 100 2433 br i1 %v10_4, label %body.5, label %end, !prof !15 2434 2435body.5: 2436 %v1_5 = add i64 %v9_4, 3 2437 %v2_5 = add i64 %v1_5, %v1_5 2438 %v3_5 = add i64 %v2_5, %v1_5 2439 %v4_5 = add i64 %v2_5, %v3_5 2440 %v5_5 = add i64 %v4_5, %v2_5 2441 %v6_5 = add i64 %v5_5, %v4_5 2442 %v7_5 = add i64 %v6_5, %v5_5 2443 %v8_5 = add i64 %v7_5, %v6_5 2444 %v9_5 = add i64 %v8_5, %v7_5 2445 %v10_5 = icmp eq i64 %v9_5, 100 2446 br i1 %v10_5, label %body.6, label %end, !prof !15 2447 2448body.6: 2449 %v1_6 = add i64 %v9_5, 3 2450 %v2_6 = add i64 %v1_6, %v1_6 2451 %v3_6 = add i64 %v2_6, %v1_6 2452 %v4_6 = add i64 %v2_6, %v3_6 2453 %v5_6 = add i64 %v4_6, %v2_6 2454 %v6_6 = add i64 %v5_6, %v4_6 2455 %v7_6 = add i64 %v6_6, %v5_6 2456 %v8_6 = add i64 %v7_6, %v6_6 2457 %v9_6 = add i64 %v8_6, %v7_6 2458 %v10_6 = icmp eq i64 %v9_6, 100 2459 br i1 %v10_6, label %body.7, label %end, !prof !15 2460 2461body.7: 2462 %v1_7 = add i64 %v9_6, 3 2463 %v2_7 = add i64 %v1_7, %v1_7 2464 %v3_7 = add i64 %v2_7, %v1_7 2465 %v4_7 = add i64 %v2_7, %v3_7 2466 %v5_7 = add i64 %v4_7, %v2_7 2467 %v6_7 = add i64 %v5_7, %v4_7 2468 %v7_7 = add i64 %v6_7, %v5_7 2469 %v8_7 = add i64 %v7_7, %v6_7 2470 %v9_7 = add i64 %v8_7, %v7_7 2471 %v10_7 = icmp eq i64 %v9_7, 100 2472 br i1 %v10_7, label %body.8, label %end, !prof !15 2473 2474body.8: 2475 %v1_8 = add i64 %v9_7, 3 2476 %v2_8 = add i64 %v1_8, %v1_8 2477 %v3_8 = add i64 %v2_8, %v1_8 2478 %v4_8 = add i64 %v2_8, %v3_8 2479 %v5_8 = add i64 %v4_8, %v2_8 2480 %v6_8 = add i64 %v5_8, %v4_8 2481 %v7_8 = add i64 %v6_8, %v5_8 2482 %v8_8 = add i64 %v7_8, %v6_8 2483 %v9_8 = add i64 %v8_8, %v7_8 2484 %v10_8 = icmp eq i64 %v9_8, 100 2485 br i1 %v10_8, label %body.9, label %end, !prof !15 2486 2487body.9: 2488 %v1_9 = add i64 %v9_8, 3 2489 %v2_9 = add i64 %v1_9, %v1_9 2490 %v3_9 = add i64 %v2_9, %v1_9 2491 %v4_9 = add i64 %v2_9, %v3_9 2492 %v5_9 = add i64 %v4_9, %v2_9 2493 %v6_9 = add i64 %v5_9, %v4_9 2494 %v7_9 = add i64 %v6_9, %v5_9 2495 %v8_9 = add i64 %v7_9, %v6_9 2496 %v9_9 = add i64 %v8_9, %v7_9 2497 br label %end 2498 2499end: 2500 ret i64 99 2501} 2502 2503; Test to not crash upon a 0:0 branch_weight metadata. 2504define void @test_chr_24(ptr %i) !prof !14 { 2505; CHECK-LABEL: @test_chr_24( 2506; CHECK-NEXT: entry: 2507; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4 2508; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[TMP0]], 1 2509; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 0 2510; CHECK-NEXT: br i1 [[TMP2]], label [[BB1:%.*]], label [[BB0:%.*]], !prof [[PROF20:![0-9]+]] 2511; CHECK: bb0: 2512; CHECK-NEXT: call void @foo() 2513; CHECK-NEXT: br label [[BB1]] 2514; CHECK: bb1: 2515; CHECK-NEXT: [[TMP3:%.*]] = and i32 [[TMP0]], 2 2516; CHECK-NEXT: [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 0 2517; CHECK-NEXT: br i1 [[TMP4]], label [[BB3:%.*]], label [[BB2:%.*]], !prof [[PROF20]] 2518; CHECK: bb2: 2519; CHECK-NEXT: call void @foo() 2520; CHECK-NEXT: br label [[BB3]] 2521; CHECK: bb3: 2522; CHECK-NEXT: ret void 2523; 2524entry: 2525 %0 = load i32, ptr %i 2526 %1 = and i32 %0, 1 2527 %2 = icmp eq i32 %1, 0 2528 br i1 %2, label %bb1, label %bb0, !prof !17 2529 2530bb0: 2531 call void @foo() 2532 br label %bb1 2533 2534bb1: 2535 %3 = and i32 %0, 2 2536 %4 = icmp eq i32 %3, 0 2537 br i1 %4, label %bb3, label %bb2, !prof !17 2538 2539bb2: 2540 call void @foo() 2541 br label %bb3 2542 2543bb3: 2544 ret void 2545} 2546 2547; Test that chr will skip this function when addresses are taken on basic blocks. 2548@gototable1 = weak_odr dso_local local_unnamed_addr constant [2 x ptr] [ptr blockaddress(@test_chr_with_bbs_address_taken1, %bb3), ptr blockaddress(@test_chr_with_bbs_address_taken1, %bb3)] 2549define void @test_chr_with_bbs_address_taken1(ptr %i) !prof !14 { 2550; CHECK-LABEL: @test_chr_with_bbs_address_taken1( 2551; CHECK-NEXT: entry: 2552; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4 2553; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[TMP0]], 1 2554; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 0 2555; CHECK-NEXT: br i1 [[TMP2]], label [[BB1:%.*]], label [[BB0:%.*]], !prof [[PROF16]] 2556; CHECK: bb0: 2557; CHECK-NEXT: call void @foo() 2558; CHECK-NEXT: br label [[BB1]] 2559; CHECK: bb1: 2560; CHECK-NEXT: [[TMP3:%.*]] = and i32 [[TMP0]], 2 2561; CHECK-NEXT: [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 0 2562; CHECK-NEXT: br i1 [[TMP4]], label [[BB4:%.*]], label [[BB2:%.*]], !prof [[PROF16]] 2563; CHECK: bb2: 2564; CHECK-NEXT: call void @foo() 2565; CHECK-NEXT: br label [[BB4]] 2566; CHECK: bb4: 2567; CHECK-NEXT: ret void 2568; 2569entry: 2570 %0 = load i32, ptr %i 2571 %1 = and i32 %0, 1 2572 %2 = icmp eq i32 %1, 0 2573 br i1 %2, label %bb1, label %bb0, !prof !15 2574 2575bb0: 2576 call void @foo() 2577 br label %bb1 2578 2579bb1: 2580 %3 = and i32 %0, 2 2581 %4 = icmp eq i32 %3, 0 2582 br i1 %4, label %bb4, label %bb2, !prof !15 2583 2584bb2: 2585 call void @foo() 2586 indirectbr ptr %i, [label %bb3, label %bb3] 2587 2588bb3: 2589 br label %bb4 2590 2591bb4: 2592 ret void 2593} 2594 2595; Test that chr will still optimize the first 2 regions, 2596; but will skip the last one due to basic blocks have address taken. 2597@gototable2 = weak_odr dso_local local_unnamed_addr constant [2 x ptr] [ptr blockaddress(@test_chr_with_bbs_address_taken2, %bb5), ptr blockaddress(@test_chr_with_bbs_address_taken2, %bb5)] 2598define void @test_chr_with_bbs_address_taken2(ptr %i) !prof !14 { 2599; CHECK-LABEL: @test_chr_with_bbs_address_taken2( 2600; CHECK-NEXT: entry: 2601; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4 2602; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[TMP0]], 3 2603; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 3 2604; CHECK-NEXT: br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] 2605; CHECK: bb0: 2606; CHECK-NEXT: call void @foo() 2607; CHECK-NEXT: call void @foo() 2608; CHECK-NEXT: br label [[BB6:%.*]] 2609; CHECK: entry.split.nonchr: 2610; CHECK-NEXT: [[TMP3:%.*]] = and i32 [[TMP0]], 1 2611; CHECK-NEXT: [[DOTNOT:%.*]] = icmp eq i32 [[TMP3]], 0 2612; CHECK-NEXT: br i1 [[DOTNOT]], label [[BB1_NONCHR:%.*]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]] 2613; CHECK: bb0.nonchr: 2614; CHECK-NEXT: call void @foo() 2615; CHECK-NEXT: br label [[BB1_NONCHR]] 2616; CHECK: bb1.nonchr: 2617; CHECK-NEXT: [[TMP4:%.*]] = and i32 [[TMP0]], 2 2618; CHECK-NEXT: [[TMP5:%.*]] = icmp eq i32 [[TMP4]], 0 2619; CHECK-NEXT: br i1 [[TMP5]], label [[BB6]], label [[BB2_NONCHR:%.*]], !prof [[PROF16]] 2620; CHECK: bb2.nonchr: 2621; CHECK-NEXT: call void @foo() 2622; CHECK-NEXT: br label [[BB6]] 2623; CHECK: bb6: 2624; CHECK-NEXT: ret void 2625; 2626entry: 2627 %0 = load i32, ptr %i 2628 %1 = and i32 %0, 1 2629 %2 = icmp eq i32 %1, 0 2630 br i1 %2, label %bb1, label %bb0, !prof !15 2631 2632bb0: 2633 call void @foo() 2634 br label %bb1 2635 2636bb1: 2637 %3 = and i32 %0, 2 2638 %4 = icmp eq i32 %3, 0 2639 br i1 %4, label %bb3, label %bb2, !prof !15 2640 2641bb2: 2642 call void @foo() 2643 br label %bb3 2644 2645bb3: 2646 %5 = and i32 %0, 2 2647 %6 = icmp eq i32 %5, 0 2648 br i1 %6, label %bb6, label %bb4, !prof !15 2649 2650bb4: 2651 indirectbr ptr %i, [label %bb5, label %bb5] 2652 2653bb5: 2654 br label %bb6 2655 2656bb6: 2657 ret void 2658} 2659 2660 2661!llvm.module.flags = !{!0} 2662!0 = !{i32 1, !"ProfileSummary", !1} 2663!1 = !{!2, !3, !4, !5, !6, !7, !8, !9} 2664!2 = !{!"ProfileFormat", !"InstrProf"} 2665!3 = !{!"TotalCount", i64 10000} 2666!4 = !{!"MaxCount", i64 10} 2667!5 = !{!"MaxInternalCount", i64 1} 2668!6 = !{!"MaxFunctionCount", i64 1000} 2669!7 = !{!"NumCounts", i64 3} 2670!8 = !{!"NumFunctions", i64 3} 2671!9 = !{!"DetailedSummary", !10} 2672!10 = !{!11, !12, !13} 2673!11 = !{i32 10000, i64 100, i32 1} 2674!12 = !{i32 999000, i64 100, i32 1} 2675!13 = !{i32 999999, i64 1, i32 2} 2676 2677!14 = !{!"function_entry_count", i64 100} 2678!15 = !{!"branch_weights", i32 0, i32 1} 2679!16 = !{!"branch_weights", i32 1, i32 1} 2680!17 = !{!"branch_weights", i32 0, i32 0} 2681; CHECK: !15 = !{!"branch_weights", i32 1000, i32 0} 2682; CHECK: !16 = !{!"branch_weights", i32 0, i32 1} 2683; CHECK: !17 = !{!"branch_weights", i32 1, i32 1} 2684; CHECK: !18 = !{!"branch_weights", i32 1, i32 0} 2685