llvm/test/Transforms/PGOProfile/chr.ll

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