llvm/test/Transforms/PGOProfile/chr.ll

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