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