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