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,simplifycfg)' -S | FileCheck %s
   3
   4 declare void @foo()
   5 declare void @bar()
   6
   7 ; Simple case.
   8 ; Roughly,
   9 ; t0 = *i
  10 ; if ((t0 & 1) != 0) // Likely true
  11 ;   foo()
  12 ; if ((t0 & 2) != 0) // Likely true
  13 ;   foo()
  14 ; ->
  15 ; t0 = *i
  16 ; if ((t0 & 3) != 0) { // Likely true
  17 ;   foo()
  18 ;   foo()
  19 ; } else {
  20 ;   if ((t0 & 1) != 0)
  21 ;     foo()
  22 ;   if ((t0 & 2) != 0)
  23 ;     foo()
  24 ; }
  25 define void @test_chr_1(ptr %i) !prof !14 {
  26 ; CHECK-LABEL: @test_chr_1(
  27 ; CHECK-NEXT:  entry:
  28 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4
  29 ; CHECK-NEXT:    [[DOTFR1:%.*]] = freeze i32 [[TMP0]]
  30 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[DOTFR1]], 3
  31 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 3
  32 ; CHECK-NEXT:    br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15:![0-9]+]]
  33 ; CHECK:       bb0:
  34 ; CHECK-NEXT:    call void @foo()
  35 ; CHECK-NEXT:    call void @foo()
  36 ; CHECK-NEXT:    br label [[BB3:%.*]]
  37 ; CHECK:       entry.split.nonchr:
  38 ; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[DOTFR1]], 1
  39 ; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i32 [[TMP3]], 0
  40 ; CHECK-NEXT:    br i1 [[DOTNOT]], label [[BB1_NONCHR:%.*]], label [[BB0_NONCHR:%.*]], !prof [[PROF16:![0-9]+]]
  41 ; CHECK:       bb0.nonchr:
  42 ; CHECK-NEXT:    call void @foo()
  43 ; CHECK-NEXT:    br label [[BB1_NONCHR]]
  44 ; CHECK:       bb1.nonchr:
  45 ; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[DOTFR1]], 2
  46 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[TMP4]], 0
  47 ; CHECK-NEXT:    br i1 [[TMP5]], label [[BB3]], label [[BB2_NONCHR:%.*]], !prof [[PROF16]]
  48 ; CHECK:       bb2.nonchr:
  49 ; CHECK-NEXT:    call void @foo()
  50 ; CHECK-NEXT:    br label [[BB3]]
  51 ; CHECK:       bb3:
  52 ; CHECK-NEXT:    ret void
  53 ;
  54 entry:
  55   %0 = load i32, ptr %i
  56   %1 = and i32 %0, 1
  57   %2 = icmp eq i32 %1, 0
  58   br i1 %2, label %bb1, label %bb0, !prof !15
  59
  60 bb0:
  61   call void @foo()
  62   br label %bb1
  63
  64 bb1:
  65   %3 = and i32 %0, 2
  66   %4 = icmp eq i32 %3, 0
  67   br i1 %4, label %bb3, label %bb2, !prof !15
  68
  69 bb2:
  70   call void @foo()
  71   br label %bb3
  72
  73 bb3:
  74   ret void
  75 }
  76
  77 ; Simple case with a cold block.
  78 ; Roughly,
  79 ; t0 = *i
  80 ; if ((t0 & 1) != 0) // Likely true
  81 ;   foo()
  82 ; if ((t0 & 2) == 0) // Likely false
  83 ;   bar()
  84 ; if ((t0 & 4) != 0) // Likely true
  85 ;   foo()
  86 ; ->
  87 ; t0 = *i
  88 ; if ((t0 & 7) == 7) { // Likely true
  89 ;   foo()
  90 ;   foo()
  91 ; } else {
  92 ;   if ((t0 & 1) != 0)
  93 ;     foo()
  94 ;   if ((t0 & 2) == 0)
  95 ;     bar()
  96 ;   if ((t0 & 4) != 0)
  97 ;     foo()
  98 ; }
  99 define void @test_chr_1_1(ptr %i) !prof !14 {
 100 ; CHECK-LABEL: @test_chr_1_1(
 101 ; CHECK-NEXT:  entry:
 102 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4
 103 ; CHECK-NEXT:    [[DOTFR1:%.*]] = freeze i32 [[TMP0]]
 104 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[DOTFR1]], 7
 105 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 7
 106 ; CHECK-NEXT:    br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
 107 ; CHECK:       bb0:
 108 ; CHECK-NEXT:    call void @foo()
 109 ; CHECK-NEXT:    call void @foo()
 110 ; CHECK-NEXT:    br label [[BB5:%.*]]
 111 ; CHECK:       entry.split.nonchr:
 112 ; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[DOTFR1]], 1
 113 ; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i32 [[TMP3]], 0
 114 ; CHECK-NEXT:    br i1 [[DOTNOT]], label [[BB1_NONCHR:%.*]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]]
 115 ; CHECK:       bb0.nonchr:
 116 ; CHECK-NEXT:    call void @foo()
 117 ; CHECK-NEXT:    br label [[BB1_NONCHR]]
 118 ; CHECK:       bb1.nonchr:
 119 ; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[DOTFR1]], 2
 120 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[TMP4]], 0
 121 ; CHECK-NEXT:    br i1 [[TMP5]], label [[BB2_NONCHR:%.*]], label [[BB3_NONCHR:%.*]], !prof [[PROF16]]
 122 ; CHECK:       bb2.nonchr:
 123 ; CHECK-NEXT:    call void @bar()
 124 ; CHECK-NEXT:    br label [[BB3_NONCHR]]
 125 ; CHECK:       bb3.nonchr:
 126 ; CHECK-NEXT:    [[TMP6:%.*]] = and i32 [[DOTFR1]], 4
 127 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i32 [[TMP6]], 0
 128 ; CHECK-NEXT:    br i1 [[TMP7]], label [[BB5]], label [[BB4_NONCHR:%.*]], !prof [[PROF16]]
 129 ; CHECK:       bb4.nonchr:
 130 ; CHECK-NEXT:    call void @foo()
 131 ; CHECK-NEXT:    br label [[BB5]]
 132 ; CHECK:       bb5:
 133 ; CHECK-NEXT:    ret void
 134 ;
 135 entry:
 136   %0 = load i32, ptr %i
 137   %1 = and i32 %0, 1
 138   %2 = icmp eq i32 %1, 0
 139   br i1 %2, label %bb1, label %bb0, !prof !15
 140
 141 bb0:
 142   call void @foo()
 143   br label %bb1
 144
 145 bb1:
 146   %3 = and i32 %0, 2
 147   %4 = icmp eq i32 %3, 0
 148   br i1 %4, label %bb2, label %bb3, !prof !15
 149
 150 bb2:
 151   call void @bar()
 152   br label %bb3
 153
 154 bb3:
 155   %5 = and i32 %0, 4
 156   %6 = icmp eq i32 %5, 0
 157   br i1 %6, label %bb5, label %bb4, !prof !15
 158
 159 bb4:
 160   call void @foo()
 161   br label %bb5
 162
 163 bb5:
 164   ret void
 165 }
 166
 167 ; With an aggregate bit check.
 168 ; Roughly,
 169 ; t0 = *i
 170 ; if ((t0 & 255) != 0) // Likely true
 171 ;   if ((t0 & 1) != 0) // Likely true
 172 ;     foo()
 173 ;   if ((t0 & 2) != 0) // Likely true
 174 ;     foo()
 175 ; ->
 176 ; t0 = *i
 177 ; if ((t0 & 3) != 0) { // Likely true
 178 ;   foo()
 179 ;   foo()
 180 ; } else if ((t0 & 255) != 0)
 181 ;   if ((t0 & 1) != 0)
 182 ;     foo()
 183 ;   if ((t0 & 2) != 0)
 184 ;     foo()
 185 ; }
 186 define void @test_chr_2(ptr %i) !prof !14 {
 187 ; CHECK-LABEL: @test_chr_2(
 188 ; CHECK-NEXT:  entry:
 189 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4
 190 ; CHECK-NEXT:    [[DOTFR1:%.*]] = freeze i32 [[TMP0]]
 191 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[DOTFR1]], 3
 192 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 3
 193 ; CHECK-NEXT:    br i1 [[TMP2]], label [[BB1:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
 194 ; CHECK:       bb1:
 195 ; CHECK-NEXT:    call void @foo()
 196 ; CHECK-NEXT:    call void @foo()
 197 ; CHECK-NEXT:    br label [[BB4:%.*]]
 198 ; CHECK:       entry.split.nonchr:
 199 ; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[DOTFR1]], 255
 200 ; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i32 [[TMP3]], 0
 201 ; CHECK-NEXT:    br i1 [[DOTNOT]], label [[BB4]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]]
 202 ; CHECK:       bb0.nonchr:
 203 ; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[DOTFR1]], 1
 204 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[TMP4]], 0
 205 ; CHECK-NEXT:    br i1 [[TMP5]], label [[BB2_NONCHR:%.*]], label [[BB1_NONCHR:%.*]], !prof [[PROF16]]
 206 ; CHECK:       bb2.nonchr:
 207 ; CHECK-NEXT:    [[TMP6:%.*]] = and i32 [[DOTFR1]], 2
 208 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i32 [[TMP6]], 0
 209 ; CHECK-NEXT:    br i1 [[TMP7]], label [[BB4]], label [[BB3_NONCHR:%.*]], !prof [[PROF16]]
 210 ; CHECK:       bb3.nonchr:
 211 ; CHECK-NEXT:    call void @foo()
 212 ; CHECK-NEXT:    br label [[BB4]]
 213 ; CHECK:       bb1.nonchr:
 214 ; CHECK-NEXT:    call void @foo()
 215 ; CHECK-NEXT:    br label [[BB2_NONCHR]]
 216 ; CHECK:       bb4:
 217 ; CHECK-NEXT:    ret void
 218 ;
 219 entry:
 220   %0 = load i32, ptr %i
 221   %1 = and i32 %0, 255
 222   %2 = icmp eq i32 %1, 0
 223   br i1 %2, label %bb4, label %bb0, !prof !15
 224
 225 bb0:
 226   %3 = and i32 %0, 1
 227   %4 = icmp eq i32 %3, 0
 228   br i1 %4, label %bb2, label %bb1, !prof !15
 229
 230 bb1:
 231   call void @foo()
 232   br label %bb2
 233
 234 bb2:
 235   %5 = and i32 %0, 2
 236   %6 = icmp eq i32 %5, 0
 237   br i1 %6, label %bb4, label %bb3, !prof !15
 238
 239 bb3:
 240   call void @foo()
 241   br label %bb4
 242
 243 bb4:
 244   ret void
 245 }
 246
 247 ; Split case.
 248 ; Roughly,
 249 ; t1 = *i
 250 ; if ((t1 & 1) != 0) // Likely true
 251 ;   foo()
 252 ; if ((t1 & 2) != 0) // Likely true
 253 ;   foo()
 254 ; t2 = *i
 255 ; if ((t2 & 4) != 0) // Likely true
 256 ;   foo()
 257 ; if ((t2 & 8) != 0) // Likely true
 258 ;   foo()
 259 ; ->
 260 ; t1 = *i
 261 ; if ((t1 & 3) != 0) { // Likely true
 262 ;   foo()
 263 ;   foo()
 264 ; } else {
 265 ;   if ((t1 & 1) != 0)
 266 ;     foo()
 267 ;   if ((t1 & 2) != 0)
 268 ;     foo()
 269 ; }
 270 ; t2 = *i
 271 ; if ((t2 & 12) != 0) { // Likely true
 272 ;   foo()
 273 ;   foo()
 274 ; } else {
 275 ;   if ((t2 & 4) != 0)
 276 ;     foo()
 277 ;   if ((t2 & 8) != 0)
 278 ;     foo()
 279 ; }
 280 define void @test_chr_3(ptr %i) !prof !14 {
 281 ; CHECK-LABEL: @test_chr_3(
 282 ; CHECK-NEXT:  entry:
 283 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4
 284 ; CHECK-NEXT:    [[DOTFR1:%.*]] = freeze i32 [[TMP0]]
 285 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[DOTFR1]], 3
 286 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 3
 287 ; CHECK-NEXT:    br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
 288 ; CHECK:       bb0:
 289 ; CHECK-NEXT:    call void @foo()
 290 ; CHECK-NEXT:    call void @foo()
 291 ; CHECK-NEXT:    br label [[BB3:%.*]]
 292 ; CHECK:       entry.split.nonchr:
 293 ; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[DOTFR1]], 1
 294 ; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i32 [[TMP3]], 0
 295 ; CHECK-NEXT:    br i1 [[DOTNOT]], label [[BB1_NONCHR:%.*]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]]
 296 ; CHECK:       bb0.nonchr:
 297 ; CHECK-NEXT:    call void @foo()
 298 ; CHECK-NEXT:    br label [[BB1_NONCHR]]
 299 ; CHECK:       bb1.nonchr:
 300 ; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[DOTFR1]], 2
 301 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[TMP4]], 0
 302 ; CHECK-NEXT:    br i1 [[TMP5]], label [[BB3]], label [[BB2_NONCHR:%.*]], !prof [[PROF16]]
 303 ; CHECK:       bb2.nonchr:
 304 ; CHECK-NEXT:    call void @foo()
 305 ; CHECK-NEXT:    br label [[BB3]]
 306 ; CHECK:       bb3:
 307 ; CHECK-NEXT:    [[TMP6:%.*]] = load i32, ptr [[I]], align 4
 308 ; CHECK-NEXT:    [[DOTFR2:%.*]] = freeze i32 [[TMP6]]
 309 ; CHECK-NEXT:    [[TMP7:%.*]] = and i32 [[DOTFR2]], 12
 310 ; CHECK-NEXT:    [[TMP8:%.*]] = icmp eq i32 [[TMP7]], 12
 311 ; CHECK-NEXT:    br i1 [[TMP8]], label [[BB4:%.*]], label [[BB3_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
 312 ; CHECK:       bb4:
 313 ; CHECK-NEXT:    call void @foo()
 314 ; CHECK-NEXT:    call void @foo()
 315 ; CHECK-NEXT:    br label [[BB7:%.*]]
 316 ; CHECK:       bb3.split.nonchr:
 317 ; CHECK-NEXT:    [[TMP9:%.*]] = and i32 [[DOTFR2]], 4
 318 ; CHECK-NEXT:    [[DOTNOT3:%.*]] = icmp eq i32 [[TMP9]], 0
 319 ; CHECK-NEXT:    br i1 [[DOTNOT3]], label [[BB5_NONCHR:%.*]], label [[BB4_NONCHR:%.*]], !prof [[PROF16]]
 320 ; CHECK:       bb4.nonchr:
 321 ; CHECK-NEXT:    call void @foo()
 322 ; CHECK-NEXT:    br label [[BB5_NONCHR]]
 323 ; CHECK:       bb5.nonchr:
 324 ; CHECK-NEXT:    [[TMP10:%.*]] = and i32 [[DOTFR2]], 8
 325 ; CHECK-NEXT:    [[TMP11:%.*]] = icmp eq i32 [[TMP10]], 0
 326 ; CHECK-NEXT:    br i1 [[TMP11]], label [[BB7]], label [[BB6_NONCHR:%.*]], !prof [[PROF16]]
 327 ; CHECK:       bb6.nonchr:
 328 ; CHECK-NEXT:    call void @foo()
 329 ; CHECK-NEXT:    br label [[BB7]]
 330 ; CHECK:       bb7:
 331 ; CHECK-NEXT:    ret void
 332 ;
 333 entry:
 334   %0 = load i32, ptr %i
 335   %1 = and i32 %0, 1
 336   %2 = icmp eq i32 %1, 0
 337   br i1 %2, label %bb1, label %bb0, !prof !15
 338
 339 bb0:
 340   call void @foo()
 341   br label %bb1
 342
 343 bb1:
 344   %3 = and i32 %0, 2
 345   %4 = icmp eq i32 %3, 0
 346   br i1 %4, label %bb3, label %bb2, !prof !15
 347
 348 bb2:
 349   call void @foo()
 350   br label %bb3
 351
 352 bb3:
 353   %5 = load i32, ptr %i
 354   %6 = and i32 %5, 4
 355   %7 = icmp eq i32 %6, 0
 356   br i1 %7, label %bb5, label %bb4, !prof !15
 357
 358 bb4:
 359   call void @foo()
 360   br label %bb5
 361
 362 bb5:
 363   %8 = and i32 %5, 8
 364   %9 = icmp eq i32 %8, 0
 365   br i1 %9, label %bb7, label %bb6, !prof !15
 366
 367 bb6:
 368   call void @foo()
 369   br label %bb7
 370
 371 bb7:
 372   ret void
 373 }
 374
 375 ; Selects.
 376 ; Roughly,
 377 ; t0 = *i
 378 ; sum1 = (t0 & 1) ? sum0 : (sum0 + 42) // Likely false
 379 ; sum2 = (t0 & 2) ? sum1 : (sum1 + 43) // Likely false
 380 ; return sum2
 381 ; ->
 382 ; t0 = *i
 383 ; if ((t0 & 3) == 3)
 384 ;   return sum0 + 85
 385 ; else {
 386 ;   sum1 = (t0 & 1) ? sum0 : (sum0 + 42)
 387 ;   sum2 = (t0 & 2) ? sum1 : (sum1 + 43)
 388 ;   return sum2
 389 ; }
 390 define i32 @test_chr_4(ptr %i, i32 %sum0) !prof !14 {
 391 ; CHECK-LABEL: @test_chr_4(
 392 ; CHECK-NEXT:  entry:
 393 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4
 394 ; CHECK-NEXT:    [[DOTFR1:%.*]] = freeze i32 [[TMP0]]
 395 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[DOTFR1]], 3
 396 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 3
 397 ; CHECK-NEXT:    br i1 [[TMP2]], label [[ENTRY_SPLIT:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
 398 ; CHECK:       common.ret:
 399 ; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[TMP3:%.*]], [[ENTRY_SPLIT]] ], [ [[SUM2_NONCHR:%.*]], [[ENTRY_SPLIT_NONCHR]] ]
 400 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
 401 ; CHECK:       entry.split:
 402 ; CHECK-NEXT:    [[TMP3]] = add i32 [[SUM0:%.*]], 85
 403 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 404 ; CHECK:       entry.split.nonchr:
 405 ; CHECK-NEXT:    [[TMP4:%.*]] = add i32 [[SUM0]], 42
 406 ; CHECK-NEXT:    [[TMP5:%.*]] = and i32 [[DOTFR1]], 1
 407 ; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i32 [[TMP5]], 0
 408 ; CHECK-NEXT:    [[SUM1_NONCHR:%.*]] = select i1 [[DOTNOT]], i32 [[SUM0]], i32 [[TMP4]], !prof [[PROF16]]
 409 ; CHECK-NEXT:    [[TMP6:%.*]] = and i32 [[DOTFR1]], 2
 410 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i32 [[TMP6]], 0
 411 ; CHECK-NEXT:    [[TMP8:%.*]] = add i32 [[SUM1_NONCHR]], 43
 412 ; CHECK-NEXT:    [[SUM2_NONCHR]] = select i1 [[TMP7]], i32 [[SUM1_NONCHR]], i32 [[TMP8]], !prof [[PROF16]]
 413 ; CHECK-NEXT:    br label [[COMMON_RET]]
 414 ;
 415 entry:
 416   %0 = load i32, ptr %i
 417   %1 = and i32 %0, 1
 418   %2 = icmp eq i32 %1, 0
 419   %3 = add i32 %sum0, 42
 420   %sum1 = select i1 %2, i32 %sum0, i32 %3, !prof !15
 421   %4 = and i32 %0, 2
 422   %5 = icmp eq i32 %4, 0
 423   %6 = add i32 %sum1, 43
 424   %sum2 = select i1 %5, i32 %sum1, i32 %6, !prof !15
 425   ret i32 %sum2
 426 }
 427
 428 ; Selects + Brs
 429 ; Roughly,
 430 ; t0 = *i
 431 ; if ((t0 & 255) != 0) { // Likely true
 432 ;   sum = (t0 & 1) ? sum0 : (sum0 + 42) // Likely false
 433 ;   sum = (t0 & 2) ? sum : (sum + 43) // Likely false
 434 ;   if ((t0 & 4) != 0) { // Likely true
 435 ;     sum3 = sum + 44
 436 ;     sum = (t0 & 8) ? sum3 : (sum3 + 44) // Likely false
 437 ;   }
 438 ; }
 439 ; return sum
 440 ; ->
 441 ; t0 = *i
 442 ; if ((t0 & 15) != 15) { // Likely true
 443 ;   sum = sum0 + 173
 444 ; } else if ((t0 & 255) != 0) {
 445 ;   sum = (t0 & 1) ? sum0 : (sum0 + 42)
 446 ;   sum = (t0 & 2) ? sum : (sum + 43)
 447 ;   if ((t0 & 4) != 0) {
 448 ;     sum3 = sum + 44
 449 ;     sum = (t0 & 8) ? sum3 : (sum3 + 44)
 450 ;   }
 451 ; }
 452 ; return sum
 453 define i32 @test_chr_5(ptr %i, i32 %sum0) !prof !14 {
 454 ; CHECK-LABEL: @test_chr_5(
 455 ; CHECK-NEXT:  entry:
 456 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4
 457 ; CHECK-NEXT:    [[DOTFR1:%.*]] = freeze i32 [[TMP0]]
 458 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[DOTFR1]], 15
 459 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 15
 460 ; CHECK-NEXT:    br i1 [[TMP2]], label [[BB1:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
 461 ; CHECK:       bb1:
 462 ; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[SUM0:%.*]], 173
 463 ; CHECK-NEXT:    br label [[BB3:%.*]]
 464 ; CHECK:       entry.split.nonchr:
 465 ; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[DOTFR1]], 255
 466 ; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i32 [[TMP4]], 0
 467 ; CHECK-NEXT:    br i1 [[DOTNOT]], label [[BB3]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]]
 468 ; CHECK:       bb0.nonchr:
 469 ; CHECK-NEXT:    [[TMP5:%.*]] = and i32 [[DOTFR1]], 1
 470 ; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i32 [[TMP5]], 0
 471 ; CHECK-NEXT:    [[TMP7:%.*]] = add i32 [[SUM0]], 42
 472 ; CHECK-NEXT:    [[SUM1_NONCHR:%.*]] = select i1 [[TMP6]], i32 [[SUM0]], i32 [[TMP7]], !prof [[PROF16]]
 473 ; CHECK-NEXT:    [[TMP8:%.*]] = and i32 [[DOTFR1]], 2
 474 ; CHECK-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[TMP8]], 0
 475 ; CHECK-NEXT:    [[TMP10:%.*]] = add i32 [[SUM1_NONCHR]], 43
 476 ; CHECK-NEXT:    [[SUM2_NONCHR:%.*]] = select i1 [[TMP9]], i32 [[SUM1_NONCHR]], i32 [[TMP10]], !prof [[PROF16]]
 477 ; CHECK-NEXT:    [[TMP11:%.*]] = and i32 [[DOTFR1]], 4
 478 ; CHECK-NEXT:    [[TMP12:%.*]] = icmp eq i32 [[TMP11]], 0
 479 ; CHECK-NEXT:    [[TMP13:%.*]] = and i32 [[DOTFR1]], 8
 480 ; CHECK-NEXT:    [[TMP14:%.*]] = icmp eq i32 [[TMP13]], 0
 481 ; CHECK-NEXT:    [[SUM4_NONCHR_V:%.*]] = select i1 [[TMP14]], i32 44, i32 88
 482 ; CHECK-NEXT:    [[SUM4_NONCHR:%.*]] = add i32 [[SUM2_NONCHR]], [[SUM4_NONCHR_V]]
 483 ; CHECK-NEXT:    [[SUM5_NONCHR:%.*]] = select i1 [[TMP12]], i32 [[SUM2_NONCHR]], i32 [[SUM4_NONCHR]], !prof [[PROF16]]
 484 ; CHECK-NEXT:    br label [[BB3]]
 485 ; CHECK:       bb3:
 486 ; CHECK-NEXT:    [[SUM6:%.*]] = phi i32 [ [[TMP3]], [[BB1]] ], [ [[SUM0]], [[ENTRY_SPLIT_NONCHR]] ], [ [[SUM5_NONCHR]], [[BB0_NONCHR]] ]
 487 ; CHECK-NEXT:    ret i32 [[SUM6]]
 488 ;
 489 entry:
 490   %0 = load i32, ptr %i
 491   %1 = and i32 %0, 255
 492   %2 = icmp eq i32 %1, 0
 493   br i1 %2, label %bb3, label %bb0, !prof !15
 494
 495 bb0:
 496   %3 = and i32 %0, 1
 497   %4 = icmp eq i32 %3, 0
 498   %5 = add i32 %sum0, 42
 499   %sum1 = select i1 %4, i32 %sum0, i32 %5, !prof !15
 500   %6 = and i32 %0, 2
 501   %7 = icmp eq i32 %6, 0
 502   %8 = add i32 %sum1, 43
 503   %sum2 = select i1 %7, i32 %sum1, i32 %8, !prof !15
 504   %9 = and i32 %0, 4
 505   %10 = icmp eq i32 %9, 0
 506   br i1 %10, label %bb2, label %bb1, !prof !15
 507
 508 bb1:
 509   %sum3 = add i32 %sum2, 44
 510   %11 = and i32 %0, 8
 511   %12 = icmp eq i32 %11, 0
 512   %13 = add i32 %sum3, 44
 513   %sum4 = select i1 %12, i32 %sum3, i32 %13, !prof !15
 514   br label %bb2
 515
 516 bb2:
 517   %sum5 = phi i32 [ %sum2, %bb0 ], [ %sum4, %bb1 ]
 518   br label %bb3
 519
 520 bb3:
 521   %sum6 = phi i32 [ %sum0, %entry ], [ %sum5, %bb2 ]
 522   ret i32 %sum6
 523 }
 524
 525 ; Selects + Brs with a scope split in the middle
 526 ; Roughly,
 527 ; t0 = *i
 528 ; if ((t0 & 255) != 0) { // Likely true
 529 ;   sum = (t0 & 1) ? sum0 : (sum0 + 42) // Likely false
 530 ;   sum = (t0 & 2) ? sum : (sum + 43) // Likely false
 531 ;   if ((sum0 & 4) != 0) { // Likely true. The condition doesn't use v.
 532 ;     sum3 = sum + 44
 533 ;     sum = (t0 & 8) ? sum3 : (sum3 + 44) // Likely false
 534 ;   }
 535 ; }
 536 ; return sum
 537 ; ->
 538 ; t0 = *i
 539 ; if ((sum0 & 4) != 0 & (t0 & 11) != 11) { // Likely true
 540 ;   sum = sum0 + 173
 541 ; } else if ((t0 & 255) != 0) {
 542 ;   sum = (t0 & 1) ? sum0 : (sum0 + 42)
 543 ;   sum = (t0 & 2) ? sum : (sum + 43)
 544 ;   if ((sum0 & 4) != 0) {
 545 ;     sum3 = sum + 44
 546 ;     sum = (t0 & 8) ? sum3 : (sum3 + 44)
 547 ;   }
 548 ; }
 549 ; return sum
 550 define i32 @test_chr_5_1(ptr %i, i32 %sum0) !prof !14 {
 551 ; CHECK-LABEL: @test_chr_5_1(
 552 ; CHECK-NEXT:  entry:
 553 ; CHECK-NEXT:    [[SUM0_FR:%.*]] = freeze i32 [[SUM0:%.*]]
 554 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4
 555 ; CHECK-NEXT:    [[DOTFR1:%.*]] = freeze i32 [[TMP0]]
 556 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[SUM0_FR]], 4
 557 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[TMP1]], 0
 558 ; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[DOTFR1]], 11
 559 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 11
 560 ; CHECK-NEXT:    [[TMP5:%.*]] = and i1 [[TMP4]], [[TMP2]]
 561 ; CHECK-NEXT:    br i1 [[TMP5]], label [[BB1:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
 562 ; CHECK:       bb1:
 563 ; CHECK-NEXT:    [[TMP6:%.*]] = add i32 [[SUM0_FR]], 173
 564 ; CHECK-NEXT:    br label [[BB3:%.*]]
 565 ; CHECK:       entry.split.nonchr:
 566 ; CHECK-NEXT:    [[TMP7:%.*]] = and i32 [[DOTFR1]], 255
 567 ; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i32 [[TMP7]], 0
 568 ; CHECK-NEXT:    br i1 [[DOTNOT]], label [[BB3]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]]
 569 ; CHECK:       bb0.nonchr:
 570 ; CHECK-NEXT:    [[TMP8:%.*]] = and i32 [[DOTFR1]], 1
 571 ; CHECK-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[TMP8]], 0
 572 ; CHECK-NEXT:    [[TMP10:%.*]] = add i32 [[SUM0_FR]], 42
 573 ; CHECK-NEXT:    [[SUM1_NONCHR:%.*]] = select i1 [[TMP9]], i32 [[SUM0_FR]], i32 [[TMP10]], !prof [[PROF16]]
 574 ; CHECK-NEXT:    [[TMP11:%.*]] = and i32 [[DOTFR1]], 2
 575 ; CHECK-NEXT:    [[TMP12:%.*]] = icmp eq i32 [[TMP11]], 0
 576 ; CHECK-NEXT:    [[TMP13:%.*]] = add i32 [[SUM1_NONCHR]], 43
 577 ; CHECK-NEXT:    [[SUM2_NONCHR:%.*]] = select i1 [[TMP12]], i32 [[SUM1_NONCHR]], i32 [[TMP13]], !prof [[PROF16]]
 578 ; CHECK-NEXT:    [[TMP14:%.*]] = and i32 [[SUM0_FR]], 4
 579 ; CHECK-NEXT:    [[TMP15:%.*]] = icmp eq i32 [[TMP14]], 0
 580 ; CHECK-NEXT:    [[TMP16:%.*]] = and i32 [[DOTFR1]], 8
 581 ; CHECK-NEXT:    [[TMP17:%.*]] = icmp eq i32 [[TMP16]], 0
 582 ; CHECK-NEXT:    [[SUM4_NONCHR_V:%.*]] = select i1 [[TMP17]], i32 44, i32 88
 583 ; CHECK-NEXT:    [[SUM4_NONCHR:%.*]] = add i32 [[SUM2_NONCHR]], [[SUM4_NONCHR_V]]
 584 ; CHECK-NEXT:    [[SUM5_NONCHR:%.*]] = select i1 [[TMP15]], i32 [[SUM2_NONCHR]], i32 [[SUM4_NONCHR]], !prof [[PROF16]]
 585 ; CHECK-NEXT:    br label [[BB3]]
 586 ; CHECK:       bb3:
 587 ; CHECK-NEXT:    [[SUM6:%.*]] = phi i32 [ [[TMP6]], [[BB1]] ], [ [[SUM0_FR]], [[ENTRY_SPLIT_NONCHR]] ], [ [[SUM5_NONCHR]], [[BB0_NONCHR]] ]
 588 ; CHECK-NEXT:    ret i32 [[SUM6]]
 589 ;
 590 entry:
 591   %0 = load i32, ptr %i
 592   %1 = and i32 %0, 255
 593   %2 = icmp eq i32 %1, 0
 594   br i1 %2, label %bb3, label %bb0, !prof !15
 595
 596 bb0:
 597   %3 = and i32 %0, 1
 598   %4 = icmp eq i32 %3, 0
 599   %5 = add i32 %sum0, 42
 600   %sum1 = select i1 %4, i32 %sum0, i32 %5, !prof !15
 601   %6 = and i32 %0, 2
 602   %7 = icmp eq i32 %6, 0
 603   %8 = add i32 %sum1, 43
 604   %sum2 = select i1 %7, i32 %sum1, i32 %8, !prof !15
 605   %9 = and i32 %sum0, 4                              ; Split
 606   %10 = icmp eq i32 %9, 0
 607   br i1 %10, label %bb2, label %bb1, !prof !15
 608
 609 bb1:
 610   %sum3 = add i32 %sum2, 44
 611   %11 = and i32 %0, 8
 612   %12 = icmp eq i32 %11, 0
 613   %13 = add i32 %sum3, 44
 614   %sum4 = select i1 %12, i32 %sum3, i32 %13, !prof !15
 615   br label %bb2
 616
 617 bb2:
 618   %sum5 = phi i32 [ %sum2, %bb0 ], [ %sum4, %bb1 ]
 619   br label %bb3
 620
 621 bb3:
 622   %sum6 = phi i32 [ %sum0, %entry ], [ %sum5, %bb2 ]
 623   ret i32 %sum6
 624 }
 625
 626 ; Selects + Brs, non-matching bases
 627 ; Roughly,
 628 ; i0 = *i
 629 ; j0 = *j
 630 ; if ((i0 & 255) != 0) { // Likely true
 631 ;   sum = (i0 & 2) ? sum0 : (sum0 + 43) // Likely false
 632 ;   if ((j0 & 4) != 0) { // Likely true. The condition uses j0, not i0.
 633 ;     sum3 = sum + 44
 634 ;     sum = (i0 & 8) ? sum3 : (sum3 + 44) // Likely false
 635 ;   }
 636 ; }
 637 ; return sum
 638 ; ->
 639 ; i0 = *i
 640 ; j0 = *j
 641 ; if ((j0 & 4) != 0 & (i0 & 10) != 10) { // Likely true
 642 ;   sum = sum0 + 131
 643 ; } else if ((i0 & 255) != 0) {
 644 ;   sum = (i0 & 2) ? sum0 : (sum0 + 43)
 645 ;   if ((j0 & 4) != 0) {
 646 ;     sum3 = sum + 44
 647 ;     sum = (i0 & 8) ? sum3 : (sum3 + 44)
 648 ;   }
 649 ; }
 650 ; return sum
 651 define i32 @test_chr_6(ptr %i, ptr %j, i32 %sum0) !prof !14 {
 652 ; CHECK-LABEL: @test_chr_6(
 653 ; CHECK-NEXT:  entry:
 654 ; CHECK-NEXT:    [[I0:%.*]] = load i32, ptr [[I:%.*]], align 4
 655 ; CHECK-NEXT:    [[I0_FR:%.*]] = freeze i32 [[I0]]
 656 ; CHECK-NEXT:    [[J0:%.*]] = load i32, ptr [[J:%.*]], align 4
 657 ; CHECK-NEXT:    [[J0_FR:%.*]] = freeze i32 [[J0]]
 658 ; CHECK-NEXT:    [[V9:%.*]] = and i32 [[J0_FR]], 4
 659 ; CHECK-NEXT:    [[V10:%.*]] = icmp ne i32 [[V9]], 0
 660 ; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[I0_FR]], 10
 661 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 10
 662 ; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[TMP1]], [[V10]]
 663 ; CHECK-NEXT:    br i1 [[TMP2]], label [[BB1:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
 664 ; CHECK:       bb1:
 665 ; CHECK-NEXT:    [[V13:%.*]] = add i32 [[SUM0:%.*]], 131
 666 ; CHECK-NEXT:    br label [[BB3:%.*]]
 667 ; CHECK:       entry.split.nonchr:
 668 ; CHECK-NEXT:    [[V1:%.*]] = and i32 [[I0_FR]], 255
 669 ; CHECK-NEXT:    [[V2_NOT:%.*]] = icmp eq i32 [[V1]], 0
 670 ; CHECK-NEXT:    br i1 [[V2_NOT]], label [[BB3]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]]
 671 ; CHECK:       bb0.nonchr:
 672 ; CHECK-NEXT:    [[V3_NONCHR:%.*]] = and i32 [[I0_FR]], 2
 673 ; CHECK-NEXT:    [[V4_NONCHR:%.*]] = icmp eq i32 [[V3_NONCHR]], 0
 674 ; CHECK-NEXT:    [[V8_NONCHR:%.*]] = add i32 [[SUM0]], 43
 675 ; CHECK-NEXT:    [[SUM2_NONCHR:%.*]] = select i1 [[V4_NONCHR]], i32 [[SUM0]], i32 [[V8_NONCHR]], !prof [[PROF16]]
 676 ; CHECK-NEXT:    [[V9_NONCHR:%.*]] = and i32 [[J0_FR]], 4
 677 ; CHECK-NEXT:    [[V10_NONCHR:%.*]] = icmp eq i32 [[V9_NONCHR]], 0
 678 ; CHECK-NEXT:    [[V11_NONCHR:%.*]] = and i32 [[I0_FR]], 8
 679 ; CHECK-NEXT:    [[V12_NONCHR:%.*]] = icmp eq i32 [[V11_NONCHR]], 0
 680 ; CHECK-NEXT:    [[SUM4_NONCHR_V:%.*]] = select i1 [[V12_NONCHR]], i32 44, i32 88
 681 ; CHECK-NEXT:    [[SUM4_NONCHR:%.*]] = add i32 [[SUM2_NONCHR]], [[SUM4_NONCHR_V]]
 682 ; CHECK-NEXT:    [[SUM5_NONCHR:%.*]] = select i1 [[V10_NONCHR]], i32 [[SUM2_NONCHR]], i32 [[SUM4_NONCHR]], !prof [[PROF16]]
 683 ; CHECK-NEXT:    br label [[BB3]]
 684 ; CHECK:       bb3:
 685 ; CHECK-NEXT:    [[SUM6:%.*]] = phi i32 [ [[V13]], [[BB1]] ], [ [[SUM0]], [[ENTRY_SPLIT_NONCHR]] ], [ [[SUM5_NONCHR]], [[BB0_NONCHR]] ]
 686 ; CHECK-NEXT:    ret i32 [[SUM6]]
 687 ;
 688 entry:
 689   %i0 = load i32, ptr %i
 690   %j0 = load i32, ptr %j
 691   %v1 = and i32 %i0, 255
 692   %v2 = icmp eq i32 %v1, 0
 693   br i1 %v2, label %bb3, label %bb0, !prof !15
 694
 695 bb0:
 696   %v3 = and i32 %i0, 2
 697   %v4 = icmp eq i32 %v3, 0
 698   %v8 = add i32 %sum0, 43
 699   %sum2 = select i1 %v4, i32 %sum0, i32 %v8, !prof !15
 700   %v9 = and i32 %j0, 4
 701   %v10 = icmp eq i32 %v9, 0
 702   br i1 %v10, label %bb2, label %bb1, !prof !15
 703
 704 bb1:
 705   %sum3 = add i32 %sum2, 44
 706   %v11 = and i32 %i0, 8
 707   %v12 = icmp eq i32 %v11, 0
 708   %v13 = add i32 %sum3, 44
 709   %sum4 = select i1 %v12, i32 %sum3, i32 %v13, !prof !15
 710   br label %bb2
 711
 712 bb2:
 713   %sum5 = phi i32 [ %sum2, %bb0 ], [ %sum4, %bb1 ]
 714   br label %bb3
 715
 716 bb3:
 717   %sum6 = phi i32 [ %sum0, %entry ], [ %sum5, %bb2 ]
 718   ret i32 %sum6
 719 }
 720
 721 ; Selects + Brs, the branch condition can't be hoisted to be merged with a
 722 ; select. No CHR happens.
 723 ; Roughly,
 724 ; i0 = *i
 725 ; sum = ((i0 & 2) == 0) ? sum0 : (sum0 + 43)  // Likely false
 726 ; foo();
 727 ; j0 = *j
 728 ; if ((j0 & 4) != 0) { // Likely true
 729 ;   foo();
 730 ;   sum = sum + 44
 731 ; }
 732 ; return sum
 733 ; ->
 734 ; (no change)
 735 define i32 @test_chr_7(ptr %i, ptr %j, i32 %sum0) !prof !14 {
 736 ; CHECK-LABEL: @test_chr_7(
 737 ; CHECK-NEXT:  entry:
 738 ; CHECK-NEXT:    [[I0:%.*]] = load i32, ptr [[I:%.*]], align 4
 739 ; CHECK-NEXT:    [[V3:%.*]] = and i32 [[I0]], 2
 740 ; CHECK-NEXT:    [[V4:%.*]] = icmp eq i32 [[V3]], 0
 741 ; CHECK-NEXT:    [[V8:%.*]] = add i32 [[SUM0:%.*]], 43
 742 ; CHECK-NEXT:    [[SUM2:%.*]] = select i1 [[V4]], i32 [[SUM0]], i32 [[V8]], !prof [[PROF16]]
 743 ; CHECK-NEXT:    call void @foo()
 744 ; CHECK-NEXT:    [[J0:%.*]] = load i32, ptr [[J:%.*]], align 4
 745 ; CHECK-NEXT:    [[V9:%.*]] = and i32 [[J0]], 4
 746 ; CHECK-NEXT:    [[V10:%.*]] = icmp eq i32 [[V9]], 0
 747 ; CHECK-NEXT:    br i1 [[V10]], label [[BB2:%.*]], label [[BB1:%.*]], !prof [[PROF16]]
 748 ; CHECK:       bb1:
 749 ; CHECK-NEXT:    call void @foo()
 750 ; CHECK-NEXT:    [[SUM4:%.*]] = add i32 [[SUM2]], 44
 751 ; CHECK-NEXT:    br label [[BB2]]
 752 ; CHECK:       bb2:
 753 ; CHECK-NEXT:    [[SUM5:%.*]] = phi i32 [ [[SUM2]], [[ENTRY:%.*]] ], [ [[SUM4]], [[BB1]] ]
 754 ; CHECK-NEXT:    ret i32 [[SUM5]]
 755 ;
 756 entry:
 757   %i0 = load i32, ptr %i
 758   %v3 = and i32 %i0, 2
 759   %v4 = icmp eq i32 %v3, 0
 760   %v8 = add i32 %sum0, 43
 761   %sum2 = select i1 %v4, i32 %sum0, i32 %v8, !prof !15
 762   call void @foo()
 763   %j0 = load i32, ptr %j
 764   %v9 = and i32 %j0, 4
 765   %v10 = icmp eq i32 %v9, 0
 766   br i1 %v10, label %bb2, label %bb1, !prof !15    ; %v10 can't be hoisted above the above select
 767
 768 bb1:
 769   call void @foo()
 770   %sum4 = add i32 %sum2, 44
 771   br label %bb2
 772
 773 bb2:
 774   %sum5 = phi i32 [ %sum2, %entry ], [ %sum4, %bb1 ]
 775   ret i32 %sum5
 776 }
 777
 778 ; Selects + Brs, the branch condition can't be hoisted to be merged with the
 779 ; selects. Dropping the select.
 780 ; Roughly,
 781 ; i0 = *i
 782 ; sum = ((i0 & 2) == 0) ? sum0 : (sum0 + 43)  // Likely false
 783 ; foo();
 784 ; j0 = *j
 785 ; if ((j0 & 4) != 0) // Likely true
 786 ;   foo()
 787 ; if ((j0 & 8) != 0) // Likely true
 788 ;   foo()
 789 ; return sum
 790 ; ->
 791 ; i0 = *i
 792 ; sum = ((i0 & 2) == 0) ? sum0 : (sum0 + 43)  // Likely false
 793 ; foo();
 794 ; j0 = *j
 795 ; if ((j0 & 12) != 12) { // Likely true
 796 ;   foo()
 797 ;   foo()
 798 ; } else {
 799 ;   if ((j0 & 4) != 0)
 800 ;     foo()
 801 ;   if ((j0 & 8) != 0)
 802 ;     foo()
 803 ; }
 804 ; return sum
 805 define i32 @test_chr_7_1(ptr %i, ptr %j, i32 %sum0) !prof !14 {
 806 ; CHECK-LABEL: @test_chr_7_1(
 807 ; CHECK-NEXT:  entry:
 808 ; CHECK-NEXT:    [[I0:%.*]] = load i32, ptr [[I:%.*]], align 4
 809 ; CHECK-NEXT:    call void @foo()
 810 ; CHECK-NEXT:    [[J0:%.*]] = load i32, ptr [[J:%.*]], align 4
 811 ; CHECK-NEXT:    [[J0_FR:%.*]] = freeze i32 [[J0]]
 812 ; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[J0_FR]], 12
 813 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 12
 814 ; CHECK-NEXT:    br i1 [[TMP1]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
 815 ; CHECK:       bb0:
 816 ; CHECK-NEXT:    call void @foo()
 817 ; CHECK-NEXT:    call void @foo()
 818 ; CHECK-NEXT:    br label [[BB3:%.*]]
 819 ; CHECK:       entry.split.nonchr:
 820 ; CHECK-NEXT:    [[V9:%.*]] = and i32 [[J0_FR]], 4
 821 ; CHECK-NEXT:    [[V10_NOT:%.*]] = icmp eq i32 [[V9]], 0
 822 ; CHECK-NEXT:    br i1 [[V10_NOT]], label [[BB1_NONCHR:%.*]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]]
 823 ; CHECK:       bb0.nonchr:
 824 ; CHECK-NEXT:    call void @foo()
 825 ; CHECK-NEXT:    br label [[BB1_NONCHR]]
 826 ; CHECK:       bb1.nonchr:
 827 ; CHECK-NEXT:    [[V11_NONCHR:%.*]] = and i32 [[J0_FR]], 8
 828 ; CHECK-NEXT:    [[V12_NONCHR:%.*]] = icmp eq i32 [[V11_NONCHR]], 0
 829 ; CHECK-NEXT:    br i1 [[V12_NONCHR]], label [[BB3]], label [[BB2_NONCHR:%.*]], !prof [[PROF16]]
 830 ; CHECK:       bb2.nonchr:
 831 ; CHECK-NEXT:    call void @foo()
 832 ; CHECK-NEXT:    br label [[BB3]]
 833 ; CHECK:       bb3:
 834 ; CHECK-NEXT:    [[V3:%.*]] = and i32 [[I0]], 2
 835 ; CHECK-NEXT:    [[V4:%.*]] = icmp eq i32 [[V3]], 0
 836 ; CHECK-NEXT:    [[V8:%.*]] = add i32 [[SUM0:%.*]], 43
 837 ; CHECK-NEXT:    [[SUM2:%.*]] = select i1 [[V4]], i32 [[SUM0]], i32 [[V8]], !prof [[PROF16]]
 838 ; CHECK-NEXT:    ret i32 [[SUM2]]
 839 ;
 840 entry:
 841   %i0 = load i32, ptr %i
 842   %v3 = and i32 %i0, 2
 843   %v4 = icmp eq i32 %v3, 0
 844   %v8 = add i32 %sum0, 43
 845   %sum2 = select i1 %v4, i32 %sum0, i32 %v8, !prof !15
 846   call void @foo()
 847   %j0 = load i32, ptr %j
 848   %v9 = and i32 %j0, 4
 849   %v10 = icmp eq i32 %v9, 0
 850   br i1 %v10, label %bb1, label %bb0, !prof !15    ; %v10 can't be hoisted above the above select
 851
 852 bb0:
 853   call void @foo()
 854   br label %bb1
 855
 856 bb1:
 857   %v11 = and i32 %j0, 8
 858   %v12 = icmp eq i32 %v11, 0
 859   br i1 %v12, label %bb3, label %bb2, !prof !15
 860
 861 bb2:
 862   call void @foo()
 863   br label %bb3
 864
 865 bb3:
 866   ret i32 %sum2
 867 }
 868
 869 ; Branches aren't biased enough. No CHR happens.
 870 ; Roughly,
 871 ; t0 = *i
 872 ; if ((t0 & 1) != 0) // Not biased
 873 ;   foo()
 874 ; if ((t0 & 2) != 0) // Not biased
 875 ;   foo()
 876 ; ->
 877 ; (no change)
 878 define void @test_chr_8(ptr %i) !prof !14 {
 879 ; CHECK-LABEL: @test_chr_8(
 880 ; CHECK-NEXT:  entry:
 881 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4
 882 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[TMP0]], 1
 883 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 0
 884 ; CHECK-NEXT:    br i1 [[TMP2]], label [[BB1:%.*]], label [[BB0:%.*]], !prof [[PROF17:![0-9]+]]
 885 ; CHECK:       bb0:
 886 ; CHECK-NEXT:    call void @foo()
 887 ; CHECK-NEXT:    br label [[BB1]]
 888 ; CHECK:       bb1:
 889 ; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP0]], 2
 890 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 0
 891 ; CHECK-NEXT:    br i1 [[TMP4]], label [[BB3:%.*]], label [[BB2:%.*]], !prof [[PROF17]]
 892 ; CHECK:       bb2:
 893 ; CHECK-NEXT:    call void @foo()
 894 ; CHECK-NEXT:    br label [[BB3]]
 895 ; CHECK:       bb3:
 896 ; CHECK-NEXT:    ret void
 897 ;
 898 entry:
 899   %0 = load i32, ptr %i
 900   %1 = and i32 %0, 1
 901   %2 = icmp eq i32 %1, 0
 902   br i1 %2, label %bb1, label %bb0, !prof !16
 903
 904 bb0:
 905   call void @foo()
 906   br label %bb1
 907
 908 bb1:
 909   %3 = and i32 %0, 2
 910   %4 = icmp eq i32 %3, 0
 911   br i1 %4, label %bb3, label %bb2, !prof !16
 912
 913 bb2:
 914   call void @foo()
 915   br label %bb3
 916
 917 bb3:
 918   ret void
 919 }
 920
 921 ; With an existing phi at the exit.
 922 ; Roughly,
 923 ; t = *i
 924 ; if ((t0 & 1) != 0) // Likely true
 925 ;   foo()
 926 ; if ((t0 & 2) != 0) { // Likely true
 927 ;   t = *j
 928 ;   foo()
 929 ; }
 930 ; // There's a phi for t here.
 931 ; return t
 932 ; ->
 933 ; t = *i
 934 ; if ((t & 3) == 3) { // Likely true
 935 ;   foo()
 936 ;   t = *j
 937 ;   foo()
 938 ; } else {
 939 ;   if ((t & 1) != 0)
 940 ;     foo()
 941 ;   if ((t & 2) != 0) {
 942 ;     t = *j
 943 ;     foo()
 944 ;   }
 945 ; }
 946 ; // There's a phi for t here.
 947 ; return t
 948 define i32 @test_chr_9(ptr %i, ptr %j) !prof !14 {
 949 ; CHECK-LABEL: @test_chr_9(
 950 ; CHECK-NEXT:  entry:
 951 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4
 952 ; CHECK-NEXT:    [[DOTFR1:%.*]] = freeze i32 [[TMP0]]
 953 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[DOTFR1]], 3
 954 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 3
 955 ; CHECK-NEXT:    br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
 956 ; CHECK:       bb0:
 957 ; CHECK-NEXT:    call void @foo()
 958 ; CHECK-NEXT:    [[TMP3:%.*]] = load i32, ptr [[J:%.*]], align 4
 959 ; CHECK-NEXT:    call void @foo()
 960 ; CHECK-NEXT:    br label [[BB3:%.*]]
 961 ; CHECK:       entry.split.nonchr:
 962 ; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[DOTFR1]], 1
 963 ; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i32 [[TMP4]], 0
 964 ; CHECK-NEXT:    br i1 [[DOTNOT]], label [[BB1_NONCHR:%.*]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]]
 965 ; CHECK:       bb0.nonchr:
 966 ; CHECK-NEXT:    call void @foo()
 967 ; CHECK-NEXT:    br label [[BB1_NONCHR]]
 968 ; CHECK:       bb1.nonchr:
 969 ; CHECK-NEXT:    [[TMP5:%.*]] = and i32 [[DOTFR1]], 2
 970 ; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i32 [[TMP5]], 0
 971 ; CHECK-NEXT:    br i1 [[TMP6]], label [[BB3]], label [[BB2_NONCHR:%.*]], !prof [[PROF16]]
 972 ; CHECK:       bb2.nonchr:
 973 ; CHECK-NEXT:    [[TMP7:%.*]] = load i32, ptr [[J]], align 4
 974 ; CHECK-NEXT:    call void @foo()
 975 ; CHECK-NEXT:    br label [[BB3]]
 976 ; CHECK:       bb3:
 977 ; CHECK-NEXT:    [[TMP8:%.*]] = phi i32 [ [[TMP3]], [[BB0]] ], [ [[DOTFR1]], [[BB1_NONCHR]] ], [ [[TMP7]], [[BB2_NONCHR]] ]
 978 ; CHECK-NEXT:    ret i32 [[TMP8]]
 979 ;
 980 entry:
 981   %0 = load i32, ptr %i
 982   %1 = and i32 %0, 1
 983   %2 = icmp eq i32 %1, 0
 984   br i1 %2, label %bb1, label %bb0, !prof !15
 985
 986 bb0:
 987   call void @foo()
 988   br label %bb1
 989
 990 bb1:
 991   %3 = and i32 %0, 2
 992   %4 = icmp eq i32 %3, 0
 993   br i1 %4, label %bb3, label %bb2, !prof !15
 994
 995 bb2:
 996   %5 = load i32, ptr %j
 997   call void @foo()
 998   br label %bb3
 999
1000 bb3:
1001   %6 = phi i32 [ %0, %bb1 ], [ %5, %bb2 ]
1002   ret i32 %6
1003 }
1004
1005 ; With no phi at the exit, but the exit needs a phi inserted after CHR.
1006 ; Roughly,
1007 ; t0 = *i
1008 ; if ((t0 & 1) != 0) // Likely true
1009 ;   foo()
1010 ; t1 = *j
1011 ; if ((t1 & 2) != 0) // Likely true
1012 ;   foo()
1013 ; return (t1 * 42) - (t1 - 99)
1014 ; ->
1015 ; t0 = *i
1016 ; if ((t0 & 3) == 3) { // Likely true
1017 ;   foo()
1018 ;   t1 = *j
1019 ;   foo()
1020 ; } else {
1021 ;   if ((t0 & 1) != 0)
1022 ;     foo()
1023 ;   if ((t0 & 2) != 0) {
1024 ;     t1 = *j
1025 ;     foo()
1026 ;   }
1027 ; }
1028 ; // A new phi for t1 is inserted here.
1029 ; return (t1 * 42) - (t1 - 99)
1030 define i32 @test_chr_10(ptr %i, ptr %j) !prof !14 {
1031 ; CHECK-LABEL: @test_chr_10(
1032 ; CHECK-NEXT:  entry:
1033 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4
1034 ; CHECK-NEXT:    [[DOTFR1:%.*]] = freeze i32 [[TMP0]]
1035 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[DOTFR1]], 3
1036 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 3
1037 ; CHECK-NEXT:    br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
1038 ; CHECK:       bb0:
1039 ; CHECK-NEXT:    call void @foo()
1040 ; CHECK-NEXT:    [[TMP3:%.*]] = load i32, ptr [[J:%.*]], align 4
1041 ; CHECK-NEXT:    call void @foo()
1042 ; CHECK-NEXT:    br label [[BB3:%.*]]
1043 ; CHECK:       entry.split.nonchr:
1044 ; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[DOTFR1]], 1
1045 ; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i32 [[TMP4]], 0
1046 ; CHECK-NEXT:    br i1 [[DOTNOT]], label [[BB1_NONCHR:%.*]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]]
1047 ; CHECK:       bb0.nonchr:
1048 ; CHECK-NEXT:    call void @foo()
1049 ; CHECK-NEXT:    br label [[BB1_NONCHR]]
1050 ; CHECK:       bb1.nonchr:
1051 ; CHECK-NEXT:    [[TMP5:%.*]] = load i32, ptr [[J]], align 4
1052 ; CHECK-NEXT:    [[TMP6:%.*]] = and i32 [[DOTFR1]], 2
1053 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i32 [[TMP6]], 0
1054 ; CHECK-NEXT:    br i1 [[TMP7]], label [[BB3]], label [[BB2_NONCHR:%.*]], !prof [[PROF16]]
1055 ; CHECK:       bb2.nonchr:
1056 ; CHECK-NEXT:    call void @foo()
1057 ; CHECK-NEXT:    br label [[BB3]]
1058 ; CHECK:       bb3:
1059 ; CHECK-NEXT:    [[TMP8:%.*]] = phi i32 [ [[TMP3]], [[BB0]] ], [ [[TMP5]], [[BB2_NONCHR]] ], [ [[TMP5]], [[BB1_NONCHR]] ]
1060 ; CHECK-NEXT:    [[TMP9:%.*]] = mul i32 [[TMP8]], 42
1061 ; CHECK-NEXT:    [[TMP10:%.*]] = add i32 [[TMP8]], -99
1062 ; CHECK-NEXT:    [[TMP11:%.*]] = add i32 [[TMP9]], [[TMP10]]
1063 ; CHECK-NEXT:    ret i32 [[TMP11]]
1064 ;
1065 entry:
1066   %0 = load i32, ptr %i
1067   %1 = and i32 %0, 1
1068   %2 = icmp eq i32 %1, 0
1069   br i1 %2, label %bb1, label %bb0, !prof !15
1070
1071 bb0:
1072   call void @foo()
1073   br label %bb1
1074
1075 bb1:
1076   %3 = load i32, ptr %j
1077   %4 = and i32 %0, 2
1078   %5 = icmp eq i32 %4, 0
1079   br i1 %5, label %bb3, label %bb2, !prof !15
1080
1081 bb2:
1082   call void @foo()
1083   br label %bb3
1084
1085 bb3:
1086   %6 = mul i32 %3, 42
1087   %7 = sub i32 %3, 99
1088   %8 = add i32 %6, %7
1089   ret i32 %8
1090 }
1091
1092 ; Test a case where there are two use-def chain paths to the same value (t0)
1093 ; from the branch condition. This is a regression test for an old bug that
1094 ; caused a bad hoisting that moves (hoists) a value (%conv) twice to the end of
1095 ; the %entry block (once for %div and once for %mul16) and put a use ahead of
1096 ; its definition like:
1097 ; %entry:
1098 ;   ...
1099 ;   %div = fdiv double 1.000000e+00, %conv
1100 ;   %conv = sitofp i32 %0 to double
1101 ;   %mul16 = fmul double %div, %conv
1102 ;
1103 ; Roughly,
1104 ; t0 = *i
1105 ; if ((t0 & 1) != 0) // Likely true
1106 ;   foo()
1107 ; // there are two use-def paths from the branch condition to t0.
1108 ; if ((1.0 / t0) * t0 < 1) // Likely true
1109 ;   foo()
1110 ; ->
1111 ; t0 = *i
1112 ; if ((t0 & 1) != 0 & (1.0 / t0) * t0 > 0) { // Likely true
1113 ;   foo()
1114 ;   foo()
1115 ; } else {
1116 ;   if ((t0 & 1) != 0)
1117 ;     foo()
1118 ;   if ((1.0 / t0) * t0 < 1) // Likely true
1119 ;     foo()
1120 ; }
1121 define void @test_chr_11(ptr %i, i32 %x) !prof !14 {
1122 ; CHECK-LABEL: @test_chr_11(
1123 ; CHECK-NEXT:  entry:
1124 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4
1125 ; CHECK-NEXT:    [[DOTFR1:%.*]] = freeze i32 [[TMP0]]
1126 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[DOTFR1]], 1
1127 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[TMP1]], 0
1128 ; CHECK-NEXT:    [[CONV:%.*]] = sitofp i32 [[DOTFR1]] to double
1129 ; CHECK-NEXT:    [[DIV:%.*]] = fdiv double 1.000000e+00, [[CONV]]
1130 ; CHECK-NEXT:    [[MUL16:%.*]] = fmul double [[DIV]], [[CONV]]
1131 ; CHECK-NEXT:    [[CONV717:%.*]] = fptosi double [[MUL16]] to i32
1132 ; CHECK-NEXT:    [[CONV717_FR:%.*]] = freeze i32 [[CONV717]]
1133 ; CHECK-NEXT:    [[CMP18:%.*]] = icmp sgt i32 [[CONV717_FR]], 0
1134 ; CHECK-NEXT:    [[TMP3:%.*]] = and i1 [[TMP2]], [[CMP18]]
1135 ; CHECK-NEXT:    br i1 [[TMP3]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
1136 ; CHECK:       bb0:
1137 ; CHECK-NEXT:    call void @foo()
1138 ; CHECK-NEXT:    call void @foo()
1139 ; CHECK-NEXT:    br label [[BB3:%.*]]
1140 ; CHECK:       entry.split.nonchr:
1141 ; CHECK-NEXT:    br i1 [[TMP2]], label [[BB0_NONCHR:%.*]], label [[BB1_NONCHR:%.*]], !prof [[PROF18:![0-9]+]]
1142 ; CHECK:       bb0.nonchr:
1143 ; CHECK-NEXT:    call void @foo()
1144 ; CHECK-NEXT:    br label [[BB1_NONCHR]]
1145 ; CHECK:       bb1.nonchr:
1146 ; CHECK-NEXT:    [[CONV_NONCHR:%.*]] = sitofp i32 [[DOTFR1]] to double
1147 ; CHECK-NEXT:    [[DIV_NONCHR:%.*]] = fdiv double 1.000000e+00, [[CONV_NONCHR]]
1148 ; CHECK-NEXT:    [[MUL16_NONCHR:%.*]] = fmul double [[DIV_NONCHR]], [[CONV_NONCHR]]
1149 ; CHECK-NEXT:    [[CONV717_NONCHR:%.*]] = fptosi double [[MUL16_NONCHR]] to i32
1150 ; CHECK-NEXT:    [[CMP18_NONCHR:%.*]] = icmp slt i32 [[CONV717_NONCHR]], 1
1151 ; CHECK-NEXT:    br i1 [[CMP18_NONCHR]], label [[BB3]], label [[BB2_NONCHR:%.*]], !prof [[PROF16]]
1152 ; CHECK:       bb2.nonchr:
1153 ; CHECK-NEXT:    call void @foo()
1154 ; CHECK-NEXT:    br label [[BB3]]
1155 ; CHECK:       bb3:
1156 ; CHECK-NEXT:    ret void
1157 ;
1158 entry:
1159   %0 = load i32, ptr %i
1160   %1 = and i32 %0, 1
1161   %2 = icmp eq i32 %1, 0
1162   br i1 %2, label %bb1, label %bb0, !prof !15
1163
1164 bb0:
1165   call void @foo()
1166   br label %bb1
1167
1168 bb1:
1169   %conv = sitofp i32 %0 to double
1170   %div = fdiv double 1.000000e+00, %conv
1171   %mul16 = fmul double %div, %conv
1172   %conv717 = fptosi double %mul16 to i32
1173   %cmp18 = icmp slt i32 %conv717, 1
1174   br i1 %cmp18, label %bb3, label %bb2, !prof !15
1175
1176 bb2:
1177   call void @foo()
1178   br label %bb3
1179
1180 bb3:
1181   ret void
1182 }
1183
1184 ; Selects + unrelated br only
1185 define i32 @test_chr_12(ptr %i, i32 %sum0) !prof !14 {
1186 ; CHECK-LABEL: @test_chr_12(
1187 ; CHECK-NEXT:  entry:
1188 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4
1189 ; CHECK-NEXT:    [[DOTFR2:%.*]] = freeze i32 [[TMP0]]
1190 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[DOTFR2]], 255
1191 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 0
1192 ; CHECK-NEXT:    br i1 [[TMP2]], label [[BB3:%.*]], label [[BB0:%.*]], !prof [[PROF16]]
1193 ; CHECK:       bb0:
1194 ; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[DOTFR2]], 1
1195 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 0
1196 ; CHECK-NEXT:    [[TMP5:%.*]] = add i32 [[SUM0:%.*]], 42
1197 ; CHECK-NEXT:    [[SUM1:%.*]] = select i1 [[TMP4]], i32 [[SUM0]], i32 [[TMP5]], !prof [[PROF16]]
1198 ; CHECK-NEXT:    [[TMP6:%.*]] = and i32 [[DOTFR2]], 2
1199 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i32 [[TMP6]], 0
1200 ; CHECK-NEXT:    [[TMP8:%.*]] = add i32 [[SUM1]], 43
1201 ; CHECK-NEXT:    [[SUM2:%.*]] = select i1 [[TMP7]], i32 [[SUM1]], i32 [[TMP8]], !prof [[PROF16]]
1202 ; CHECK-NEXT:    [[TMP9:%.*]] = load i32, ptr [[I]], align 4
1203 ; CHECK-NEXT:    [[DOTFR:%.*]] = freeze i32 [[TMP9]]
1204 ; CHECK-NEXT:    [[TMP10:%.*]] = icmp ne i32 [[DOTFR]], 0
1205 ; CHECK-NEXT:    [[TMP11:%.*]] = and i32 [[DOTFR2]], 8
1206 ; CHECK-NEXT:    [[TMP12:%.*]] = icmp ne i32 [[TMP11]], 0
1207 ; CHECK-NEXT:    [[TMP13:%.*]] = and i1 [[TMP10]], [[TMP12]]
1208 ; CHECK-NEXT:    br i1 [[TMP13]], label [[BB1:%.*]], label [[BB0_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
1209 ; CHECK:       bb1:
1210 ; CHECK-NEXT:    [[TMP14:%.*]] = add i32 [[SUM2]], 88
1211 ; CHECK-NEXT:    br label [[BB3]]
1212 ; CHECK:       bb0.split.nonchr:
1213 ; CHECK-NEXT:    br i1 [[TMP10]], label [[BB1_NONCHR:%.*]], label [[BB3]], !prof [[PROF18]]
1214 ; CHECK:       bb1.nonchr:
1215 ; CHECK-NEXT:    [[TMP15:%.*]] = and i32 [[DOTFR2]], 8
1216 ; CHECK-NEXT:    [[TMP16:%.*]] = icmp eq i32 [[TMP15]], 0
1217 ; CHECK-NEXT:    [[SUM4_NONCHR_V:%.*]] = select i1 [[TMP16]], i32 44, i32 88, !prof [[PROF16]]
1218 ; CHECK-NEXT:    [[SUM4_NONCHR:%.*]] = add i32 [[SUM2]], [[SUM4_NONCHR_V]]
1219 ; CHECK-NEXT:    br label [[BB3]]
1220 ; CHECK:       bb3:
1221 ; CHECK-NEXT:    [[SUM6:%.*]] = phi i32 [ [[SUM0]], [[ENTRY:%.*]] ], [ [[TMP14]], [[BB1]] ], [ [[SUM2]], [[BB0_SPLIT_NONCHR]] ], [ [[SUM4_NONCHR]], [[BB1_NONCHR]] ]
1222 ; CHECK-NEXT:    ret i32 [[SUM6]]
1223 ;
1224 entry:
1225   %0 = load i32, ptr %i
1226   %1 = and i32 %0, 255
1227   %2 = icmp eq i32 %1, 0
1228   br i1 %2, label %bb3, label %bb0, !prof !15
1229
1230 bb0:
1231   %3 = and i32 %0, 1
1232   %4 = icmp eq i32 %3, 0
1233   %5 = add i32 %sum0, 42
1234   %sum1 = select i1 %4, i32 %sum0, i32 %5, !prof !15
1235   %6 = and i32 %0, 2
1236   %7 = icmp eq i32 %6, 0
1237   %8 = add i32 %sum1, 43
1238   %sum2 = select i1 %7, i32 %sum1, i32 %8, !prof !15
1239   %9 = load i32, ptr %i
1240   %10 = icmp eq i32 %9, 0
1241   br i1 %10, label %bb2, label %bb1, !prof !15
1242
1243 bb1:
1244   %sum3 = add i32 %sum2, 44
1245   %11 = and i32 %0, 8
1246   %12 = icmp eq i32 %11, 0
1247   %13 = add i32 %sum3, 44
1248   %sum4 = select i1 %12, i32 %sum3, i32 %13, !prof !15
1249   br label %bb2
1250
1251 bb2:
1252   %sum5 = phi i32 [ %sum2, %bb0 ], [ %sum4, %bb1 ]
1253   br label %bb3
1254
1255 bb3:
1256   %sum6 = phi i32 [ %sum0, %entry ], [ %sum5, %bb2 ]
1257   ret i32 %sum6
1258 }
1259
1260 ; In the second CHR, a condition value depends on a trivial phi that's inserted
1261 ; by the first CHR.
1262 ; Roughly,
1263 ; i0 = *i
1264 ; v2 = (z != 1) ? pred : true  // Likely false
1265 ; if (z == 0 & pred)  // Likely false
1266 ;   foo()
1267 ; j0 = *j
1268 ; sum2 = ((i0 & 2) == j0) ? sum0 : (sum0 + 43) // Likely false
1269 ; sum3 = ((i0 == j0) ? sum0 : (sum0 + 43) // Likely false
1270 ; foo()
1271 ; if ((i0 & 4) == 0) // Unbiased
1272 ;   foo()
1273 ; return i0 + sum3
1274 ; ->
1275 ; i0 = *i
1276 ; if (z != 1 & (z == 0 & pred)) // First CHR
1277 ;   foo()
1278 ; // A trivial phi for i0 is inserted here by the first CHR (which gets removed
1279 ; // later) and the subsequent branch condition (for the second CHR) uses it.
1280 ; j0 = *j
1281 ; if ((i0 & 2) != j0 & i0 != j0) {  // Second CHR
1282 ;   sum3 = sum0 + 43
1283 ;   foo()
1284 ;   if (i0 & 4) == 0)
1285 ;     foo()
1286 ; } else {
1287 ;   sum3 = (i0 == j0) ? sum0 : (sum0 + 43)
1288 ;   foo()
1289 ;   if (i0 & 4) == 0)
1290 ;     foo()
1291 ; }
1292 ; return i0 + sum3
1293 define i32 @test_chr_14(ptr %i, ptr %j, i32 %sum0, i1 %pred, i32 %z) !prof !14 {
1294 ; CHECK-LABEL: @test_chr_14(
1295 ; CHECK-NEXT:  entry:
1296 ; CHECK-NEXT:    [[Z_FR:%.*]] = freeze i32 [[Z:%.*]]
1297 ; CHECK-NEXT:    [[I0:%.*]] = load i32, ptr [[I:%.*]], align 4
1298 ; CHECK-NEXT:    [[V1_NOT:%.*]] = icmp eq i32 [[Z_FR]], 1
1299 ; CHECK-NEXT:    br i1 [[V1_NOT]], label [[BB1:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
1300 ; CHECK:       entry.split.nonchr:
1301 ; CHECK-NEXT:    [[PRED_FR:%.*]] = freeze i1 [[PRED:%.*]]
1302 ; CHECK-NEXT:    [[V0:%.*]] = icmp eq i32 [[Z_FR]], 0
1303 ; CHECK-NEXT:    [[V3_NONCHR:%.*]] = and i1 [[V0]], [[PRED_FR]]
1304 ; CHECK-NEXT:    br i1 [[V3_NONCHR]], label [[BB0_NONCHR:%.*]], label [[BB1]], !prof [[PROF16]]
1305 ; CHECK:       bb0.nonchr:
1306 ; CHECK-NEXT:    call void @foo()
1307 ; CHECK-NEXT:    br label [[BB1]]
1308 ; CHECK:       bb1:
1309 ; CHECK-NEXT:    [[J0:%.*]] = load i32, ptr [[J:%.*]], align 4
1310 ; CHECK-NEXT:    [[V6:%.*]] = and i32 [[I0]], 2
1311 ; CHECK-NEXT:    [[V4:%.*]] = icmp ne i32 [[V6]], [[J0]]
1312 ; CHECK-NEXT:    [[V8:%.*]] = add i32 [[SUM0:%.*]], 43
1313 ; CHECK-NEXT:    [[V5:%.*]] = icmp ne i32 [[I0]], [[J0]]
1314 ; CHECK-NEXT:    [[TMP0:%.*]] = freeze i1 [[V4]]
1315 ; CHECK-NEXT:    [[TMP1:%.*]] = freeze i1 [[V5]]
1316 ; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[TMP0]], [[TMP1]]
1317 ; CHECK-NEXT:    br i1 [[TMP2]], label [[BB1_SPLIT:%.*]], label [[BB1_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
1318 ; CHECK:       bb1.split:
1319 ; CHECK-NEXT:    call void @foo()
1320 ; CHECK-NEXT:    [[V9:%.*]] = and i32 [[I0]], 4
1321 ; CHECK-NEXT:    [[V10:%.*]] = icmp eq i32 [[V9]], 0
1322 ; CHECK-NEXT:    br i1 [[V10]], label [[BB3:%.*]], label [[BB2:%.*]]
1323 ; CHECK:       bb2:
1324 ; CHECK-NEXT:    call void @foo()
1325 ; CHECK-NEXT:    br label [[BB3]]
1326 ; CHECK:       bb1.split.nonchr:
1327 ; CHECK-NEXT:    [[V5_NONCHR:%.*]] = icmp eq i32 [[I0]], [[J0]]
1328 ; CHECK-NEXT:    [[SUM3_NONCHR:%.*]] = select i1 [[V5_NONCHR]], i32 [[SUM0]], i32 [[V8]], !prof [[PROF16]]
1329 ; CHECK-NEXT:    call void @foo()
1330 ; CHECK-NEXT:    [[V9_NONCHR:%.*]] = and i32 [[I0]], 4
1331 ; CHECK-NEXT:    [[V10_NONCHR:%.*]] = icmp eq i32 [[V9_NONCHR]], 0
1332 ; CHECK-NEXT:    br i1 [[V10_NONCHR]], label [[BB3]], label [[BB2_NONCHR:%.*]]
1333 ; CHECK:       bb2.nonchr:
1334 ; CHECK-NEXT:    call void @foo()
1335 ; CHECK-NEXT:    br label [[BB3]]
1336 ; CHECK:       bb3:
1337 ; CHECK-NEXT:    [[TMP3:%.*]] = phi i32 [ [[V8]], [[BB2]] ], [ [[V8]], [[BB1_SPLIT]] ], [ [[SUM3_NONCHR]], [[BB2_NONCHR]] ], [ [[SUM3_NONCHR]], [[BB1_SPLIT_NONCHR]] ]
1338 ; CHECK-NEXT:    [[V11:%.*]] = add i32 [[I0]], [[TMP3]]
1339 ; CHECK-NEXT:    ret i32 [[V11]]
1340 ;
1341 entry:
1342   %i0 = load i32, ptr %i
1343   %v0 = icmp eq i32 %z, 0
1344   %v1 = icmp ne i32 %z, 1
1345   %v2 = select i1 %v1, i1 %pred, i1 true, !prof !15
1346   %v3 = and i1 %v0, %pred
1347   br i1 %v3, label %bb0, label %bb1, !prof !15
1348
1349 bb0:
1350   call void @foo()
1351   br label %bb1
1352
1353 bb1:
1354   %j0 = load i32, ptr %j
1355   %v6 = and i32 %i0, 2
1356   %v4 = icmp eq i32 %v6, %j0
1357   %v8 = add i32 %sum0, 43
1358   %sum2 = select i1 %v4, i32 %sum0, i32 %v8, !prof !15
1359   %v5 = icmp eq i32 %i0, %j0
1360   %sum3 = select i1 %v5, i32 %sum0, i32 %v8, !prof !15
1361   call void @foo()
1362   %v9 = and i32 %i0, 4
1363   %v10 = icmp eq i32 %v9, 0
1364   br i1 %v10, label %bb3, label %bb2
1365
1366 bb2:
1367   call void @foo()
1368   br label %bb3
1369
1370 bb3:
1371   %v11 = add i32 %i0, %sum3
1372   ret i32 %v11
1373 }
1374
1375 ; Branch or selects depends on another select. No CHR happens.
1376 ; Roughly,
1377 ; i0 = *i
1378 ; if (z == 0 & ((z != 1) ? pred : true)) { // Likely false
1379 ;   foo()
1380 ; j0 = *j
1381 ; sum2 = ((i0 & 2) == j0) ? sum0 : (sum0 + 43) // Likely false
1382 ; sum3 = (i0 == sum2) ? sum2 : (sum0 + 43) // Likely false. This depends on the
1383 ;                                          // previous select.
1384 ; foo()
1385 ; if ((i0 & 4) == 0) // Unbiased
1386 ;   foo()
1387 ; return i0 + sum3
1388 ; ->
1389 ; (no change)
1390 define i32 @test_chr_15(ptr %i, ptr %j, i32 %sum0, i1 %pred, i32 %z) !prof !14 {
1391 ; CHECK-LABEL: @test_chr_15(
1392 ; CHECK-NEXT:  entry:
1393 ; CHECK-NEXT:    [[I0:%.*]] = load i32, ptr [[I:%.*]], align 4
1394 ; CHECK-NEXT:    [[V0:%.*]] = icmp eq i32 [[Z:%.*]], 0
1395 ; CHECK-NEXT:    [[V3:%.*]] = select i1 [[V0]], i1 [[PRED:%.*]], i1 false
1396 ; CHECK-NEXT:    br i1 [[V3]], label [[BB0:%.*]], label [[BB1:%.*]], !prof [[PROF16]]
1397 ; CHECK:       bb0:
1398 ; CHECK-NEXT:    call void @foo()
1399 ; CHECK-NEXT:    br label [[BB1]]
1400 ; CHECK:       bb1:
1401 ; CHECK-NEXT:    [[J0:%.*]] = load i32, ptr [[J:%.*]], align 4
1402 ; CHECK-NEXT:    call void @foo()
1403 ; CHECK-NEXT:    [[V9:%.*]] = and i32 [[I0]], 4
1404 ; CHECK-NEXT:    [[V10:%.*]] = icmp eq i32 [[V9]], 0
1405 ; CHECK-NEXT:    br i1 [[V10]], label [[BB3:%.*]], label [[BB2:%.*]]
1406 ; CHECK:       bb2:
1407 ; CHECK-NEXT:    call void @foo()
1408 ; CHECK-NEXT:    br label [[BB3]]
1409 ; CHECK:       bb3:
1410 ; CHECK-NEXT:    [[V6:%.*]] = and i32 [[I0]], 2
1411 ; CHECK-NEXT:    [[V4:%.*]] = icmp eq i32 [[V6]], [[J0]]
1412 ; CHECK-NEXT:    [[V8:%.*]] = add i32 [[SUM0:%.*]], 43
1413 ; CHECK-NEXT:    [[SUM2:%.*]] = select i1 [[V4]], i32 [[SUM0]], i32 [[V8]], !prof [[PROF16]]
1414 ; CHECK-NEXT:    [[V5:%.*]] = icmp eq i32 [[I0]], [[SUM2]]
1415 ; CHECK-NEXT:    [[SUM3:%.*]] = select i1 [[V5]], i32 [[SUM2]], i32 [[V8]], !prof [[PROF16]]
1416 ; CHECK-NEXT:    [[V11:%.*]] = add i32 [[I0]], [[SUM3]]
1417 ; CHECK-NEXT:    ret i32 [[V11]]
1418 ;
1419 entry:
1420   %i0 = load i32, ptr %i
1421   %v0 = icmp eq i32 %z, 0
1422   %v1 = icmp ne i32 %z, 1
1423   %v2 = select i1 %v1, i1 %pred, i1 true, !prof !15
1424   %v3 = and i1 %v0, %v2
1425   br i1 %v3, label %bb0, label %bb1, !prof !15
1426
1427 bb0:
1428   call void @foo()
1429   br label %bb1
1430
1431 bb1:
1432   %j0 = load i32, ptr %j
1433   %v6 = and i32 %i0, 2
1434   %v4 = icmp eq i32 %v6, %j0
1435   %v8 = add i32 %sum0, 43
1436   %sum2 = select i1 %v4, i32 %sum0, i32 %v8, !prof !15
1437   %v5 = icmp eq i32 %i0, %sum2
1438   %sum3 = select i1 %v5, i32 %sum2, i32 %v8, !prof !15
1439   call void @foo()
1440   %v9 = and i32 %i0, 4
1441   %v10 = icmp eq i32 %v9, 0
1442   br i1 %v10, label %bb3, label %bb2
1443
1444 bb2:
1445   call void @foo()
1446   br label %bb3
1447
1448 bb3:
1449   %v11 = add i32 %i0, %sum3
1450   ret i32 %v11
1451 }
1452
1453 ; With an existing phi at the exit but a value (%v40) is both alive and is an
1454 ; operand to a phi at the exit block.
1455 ; Roughly,
1456 ; t0 = *i
1457 ; if ((t0 & 1) != 0) // Likely true
1458 ;   foo()
1459 ; v40 = t0 + 44
1460 ; if ((t0 & 2) != 0) // Likely true
1461 ;   v41 = t0 + 99
1462 ;   foo()
1463 ; }
1464 ; v42 = phi v40, v41
1465 ; return v42 + v40
1466 ; ->
1467 ; t0 = *i
1468 ; if ((t0 & 3) == 3) // Likely true
1469 ;   foo()
1470 ;   v40 = t0 + 44
1471 ;   v41 = t0 + 99
1472 ;   foo()
1473 ; } else {
1474 ;   if ((t0 & 1) != 0) // Likely true
1475 ;     foo()
1476 ;   v40_nc = t0 + 44
1477 ;   if ((t0 & 2) != 0) // Likely true
1478 ;     v41_nc = t0 + 99
1479 ;     foo()
1480 ;   }
1481 ; }
1482 ; t7 = phi v40, v40_nc
1483 ; v42 = phi v41, v41_nc
1484 ; v43 = v42 + t7
1485 ; return v43
1486 define i32 @test_chr_16(ptr %i) !prof !14 {
1487 ; CHECK-LABEL: @test_chr_16(
1488 ; CHECK-NEXT:  entry:
1489 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4
1490 ; CHECK-NEXT:    [[DOTFR1:%.*]] = freeze i32 [[TMP0]]
1491 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[DOTFR1]], 3
1492 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 3
1493 ; CHECK-NEXT:    br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
1494 ; CHECK:       bb0:
1495 ; CHECK-NEXT:    call void @foo()
1496 ; CHECK-NEXT:    [[V40:%.*]] = add i32 [[DOTFR1]], 44
1497 ; CHECK-NEXT:    [[V41:%.*]] = add i32 [[DOTFR1]], 99
1498 ; CHECK-NEXT:    call void @foo()
1499 ; CHECK-NEXT:    br label [[BB3:%.*]]
1500 ; CHECK:       entry.split.nonchr:
1501 ; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[DOTFR1]], 1
1502 ; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i32 [[TMP3]], 0
1503 ; CHECK-NEXT:    br i1 [[DOTNOT]], label [[BB1_NONCHR:%.*]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]]
1504 ; CHECK:       bb0.nonchr:
1505 ; CHECK-NEXT:    call void @foo()
1506 ; CHECK-NEXT:    br label [[BB1_NONCHR]]
1507 ; CHECK:       bb1.nonchr:
1508 ; CHECK-NEXT:    [[V40_NONCHR:%.*]] = add i32 [[DOTFR1]], 44
1509 ; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[DOTFR1]], 2
1510 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[TMP4]], 0
1511 ; CHECK-NEXT:    br i1 [[TMP5]], label [[BB3]], label [[BB2_NONCHR:%.*]], !prof [[PROF16]]
1512 ; CHECK:       bb2.nonchr:
1513 ; CHECK-NEXT:    [[V41_NONCHR:%.*]] = add i32 [[DOTFR1]], 99
1514 ; CHECK-NEXT:    call void @foo()
1515 ; CHECK-NEXT:    br label [[BB3]]
1516 ; CHECK:       bb3:
1517 ; CHECK-NEXT:    [[TMP6:%.*]] = phi i32 [ [[V40]], [[BB0]] ], [ [[V40_NONCHR]], [[BB2_NONCHR]] ], [ [[V40_NONCHR]], [[BB1_NONCHR]] ]
1518 ; CHECK-NEXT:    [[V42:%.*]] = phi i32 [ [[V41]], [[BB0]] ], [ [[V41_NONCHR]], [[BB2_NONCHR]] ], [ [[V40_NONCHR]], [[BB1_NONCHR]] ]
1519 ; CHECK-NEXT:    [[V43:%.*]] = add i32 [[V42]], [[TMP6]]
1520 ; CHECK-NEXT:    ret i32 [[V43]]
1521 ;
1522 entry:
1523   %0 = load i32, ptr %i
1524   %1 = and i32 %0, 1
1525   %2 = icmp eq i32 %1, 0
1526   br i1 %2, label %bb1, label %bb0, !prof !15
1527
1528 bb0:
1529   call void @foo()
1530   br label %bb1
1531
1532 bb1:
1533   %v40 = add i32 %0, 44
1534   %3 = and i32 %0, 2
1535   %4 = icmp eq i32 %3, 0
1536   br i1 %4, label %bb3, label %bb2, !prof !15
1537
1538 bb2:
1539   %v41 = add i32 %0, 99
1540   call void @foo()
1541   br label %bb3
1542
1543 bb3:
1544   %v42 = phi i32 [ %v41, %bb2 ], [ %v40, %bb1 ]
1545   %v43 = add i32 %v42, %v40
1546   ret i32 %v43
1547 }
1548
1549 ; Two consecutive regions have an entry in the middle of them. No CHR happens.
1550 ; Roughly,
1551 ; if ((i & 4) == 0) {
1552 ;   if (!j)
1553 ;     goto bb1
1554 ; } else {
1555 ;   t0 = (i & 1)
1556 ;   if (t0 != 0) // Likely true
1557 ;     foo()
1558 ;     s = (i & 1) + i
1559 ;   }
1560 ;  bb1:
1561 ;   p = phi i, t0, s
1562 ;   if ((i & 2) != 0) // Likely true
1563 ;     foo()
1564 ;     q = p + 2
1565 ; }
1566 ; r = phi p, q, i
1567 ; return r
1568 ; ->
1569 ; (no change)
1570 define i32 @test_chr_17(i32 %i, i1 %j) !prof !14 {
1571 ; CHECK-LABEL: @test_chr_17(
1572 ; CHECK-NEXT:  entry:
1573 ; CHECK-NEXT:    [[V0:%.*]] = and i32 [[I:%.*]], 4
1574 ; CHECK-NEXT:    [[V1:%.*]] = icmp eq i32 [[V0]], 0
1575 ; CHECK-NEXT:    br i1 [[V1]], label [[BBE:%.*]], label [[BBQ:%.*]]
1576 ; CHECK:       bbq:
1577 ; CHECK-NEXT:    br i1 [[J:%.*]], label [[BB3:%.*]], label [[BB1:%.*]]
1578 ; CHECK:       bbe:
1579 ; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[I]], 1
1580 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 0
1581 ; CHECK-NEXT:    br i1 [[TMP1]], label [[BB1]], label [[BB0:%.*]], !prof [[PROF16]]
1582 ; CHECK:       bb0:
1583 ; CHECK-NEXT:    call void @foo()
1584 ; CHECK-NEXT:    [[S:%.*]] = add nuw nsw i32 [[TMP0]], [[I]]
1585 ; CHECK-NEXT:    br label [[BB1]]
1586 ; CHECK:       bb1:
1587 ; CHECK-NEXT:    [[P:%.*]] = phi i32 [ [[I]], [[BBQ]] ], [ [[TMP0]], [[BBE]] ], [ [[S]], [[BB0]] ]
1588 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[I]], 2
1589 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 0
1590 ; CHECK-NEXT:    br i1 [[TMP3]], label [[BB3]], label [[BB2:%.*]], !prof [[PROF16]]
1591 ; CHECK:       bb2:
1592 ; CHECK-NEXT:    call void @foo()
1593 ; CHECK-NEXT:    [[Q:%.*]] = add i32 [[P]], [[TMP2]]
1594 ; CHECK-NEXT:    br label [[BB3]]
1595 ; CHECK:       bb3:
1596 ; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[P]], [[BB1]] ], [ [[Q]], [[BB2]] ], [ [[I]], [[BBQ]] ]
1597 ; CHECK-NEXT:    ret i32 [[R]]
1598 ;
1599 entry:
1600   %v0 = and i32 %i, 4
1601   %v1 = icmp eq i32 %v0, 0
1602   br i1 %v1, label %bbe, label %bbq
1603
1604 bbq:
1605   br i1 %j, label %bb3, label %bb1
1606
1607 bbe:
1608   %0 = and i32 %i, 1
1609   %1 = icmp eq i32 %0, 0
1610   br i1 %1, label %bb1, label %bb0, !prof !15
1611
1612 bb0:
1613   call void @foo()
1614   %s = add i32 %0, %i
1615   br label %bb1
1616
1617 bb1:
1618   %p = phi i32 [ %i, %bbq ], [ %0, %bbe ], [ %s, %bb0 ]
1619   %2 = and i32 %i, 2
1620   %3 = icmp eq i32 %2, 0
1621   br i1 %3, label %bb3, label %bb2, !prof !15
1622
1623 bb2:
1624   call void @foo()
1625   %q = add i32 %p, %2
1626   br label %bb3
1627
1628 bb3:
1629   %r = phi i32 [ %p, %bb1 ], [ %q, %bb2 ], [ %i, %bbq ]
1630   ret i32 %r
1631 }
1632
1633 ; Select + br, there's a loop and we need to update the user of an inserted phi
1634 ; at the entry block. This is a regression test for a bug that's fixed.
1635 ; Roughly,
1636 ; do {
1637 ;   inc1 = phi inc2, 0
1638 ;   li = *i
1639 ;   sum1 = sum0 + 42
1640 ;   sum2 = ((li & 1) == 0) ? sum0 : sum1  // Likely false
1641 ;   inc2 = inc1 + 1
1642 ;   if ((li & 4) != 0) // Likely true
1643 ;     sum3 = sum2 + 44
1644 ;   sum4 = phi sum1, sum3
1645 ; } while (inc2 != 100)  // Likely true (loop back)
1646 ; return sum4
1647 ; ->
1648 ; do {
1649 ;   inc1 = phi tmp2, 0  // The first operand needed to be updated
1650 ;   li = *i
1651 ;   sum1 = sum0 + 42
1652 ;   if ((li & 5) == 5) { // Likely true
1653 ;     inc2 = inc1 + 1
1654 ;     sum3 = sum0 + 86
1655 ;   } else {
1656 ;     inc2_nc = inc1 + 1
1657 ;     if ((li & 4) == 0)
1658 ;       sum2_nc = ((li & 1) == 0) ? sum0 : sum1
1659 ;       sum3_nc = sum2_nc + 44
1660 ;     }
1661 ;   tmp2 = phi inc2, in2c_nc
1662 ;   sum4 = phi sum3, sum3_nc, sum1
1663 ; } while (tmp2 != 100)
1664 ; return sum4
1665 define i32 @test_chr_18(ptr %i, i32 %sum0) !prof !14 {
1666 ; CHECK-LABEL: @test_chr_18(
1667 ; CHECK-NEXT:  entry:
1668 ; CHECK-NEXT:    br label [[BB0:%.*]]
1669 ; CHECK:       bb0:
1670 ; CHECK-NEXT:    [[INC1:%.*]] = phi i32 [ [[TMP2:%.*]], [[BB2:%.*]] ], [ 0, [[ENTRY:%.*]] ]
1671 ; CHECK-NEXT:    [[LI:%.*]] = load i32, ptr [[I:%.*]], align 4
1672 ; CHECK-NEXT:    [[LI_FR:%.*]] = freeze i32 [[LI]]
1673 ; CHECK-NEXT:    [[SUM1:%.*]] = add i32 [[SUM0:%.*]], 42
1674 ; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[LI_FR]], 5
1675 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 5
1676 ; CHECK-NEXT:    br i1 [[TMP1]], label [[BB1:%.*]], label [[BB0_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
1677 ; CHECK:       bb1:
1678 ; CHECK-NEXT:    [[INC2:%.*]] = add i32 [[INC1]], 1
1679 ; CHECK-NEXT:    [[SUM3:%.*]] = add i32 [[SUM0]], 86
1680 ; CHECK-NEXT:    br label [[BB2]]
1681 ; CHECK:       bb0.split.nonchr:
1682 ; CHECK-NEXT:    [[A4_NONCHR:%.*]] = and i32 [[LI_FR]], 4
1683 ; CHECK-NEXT:    [[CMP4_NONCHR:%.*]] = icmp eq i32 [[A4_NONCHR]], 0
1684 ; CHECK-NEXT:    [[INC2_NONCHR:%.*]] = add i32 [[INC1]], 1
1685 ; CHECK-NEXT:    br i1 [[CMP4_NONCHR]], label [[BB2]], label [[BB1_NONCHR:%.*]], !prof [[PROF16]]
1686 ; CHECK:       bb1.nonchr:
1687 ; CHECK-NEXT:    [[A1:%.*]] = and i32 [[LI_FR]], 1
1688 ; CHECK-NEXT:    [[CMP1_NOT:%.*]] = icmp eq i32 [[A1]], 0
1689 ; CHECK-NEXT:    [[SUM2_NONCHR:%.*]] = select i1 [[CMP1_NOT]], i32 [[SUM0]], i32 [[SUM1]], !prof [[PROF16]]
1690 ; CHECK-NEXT:    [[SUM3_NONCHR:%.*]] = add i32 [[SUM2_NONCHR]], 44
1691 ; CHECK-NEXT:    br label [[BB2]]
1692 ; CHECK:       bb2:
1693 ; CHECK-NEXT:    [[TMP2]] = phi i32 [ [[INC2]], [[BB1]] ], [ [[INC2_NONCHR]], [[BB1_NONCHR]] ], [ [[INC2_NONCHR]], [[BB0_SPLIT_NONCHR]] ]
1694 ; CHECK-NEXT:    [[SUM4:%.*]] = phi i32 [ [[SUM3]], [[BB1]] ], [ [[SUM3_NONCHR]], [[BB1_NONCHR]] ], [ [[SUM1]], [[BB0_SPLIT_NONCHR]] ]
1695 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP2]], 100
1696 ; CHECK-NEXT:    br i1 [[CMP]], label [[BB3:%.*]], label [[BB0]], !prof [[PROF16]]
1697 ; CHECK:       bb3:
1698 ; CHECK-NEXT:    ret i32 [[SUM4]]
1699 ;
1700 entry:
1701   br label %bb0
1702
1703 bb0:
1704   %inc1 = phi i32 [ %inc2, %bb2 ], [ 0, %entry ]
1705   %li = load i32, ptr %i
1706   %a1 = and i32 %li, 1
1707   %cmp1 = icmp eq i32 %a1, 0
1708   %sum1 = add i32 %sum0, 42
1709   %sum2 = select i1 %cmp1, i32 %sum0, i32 %sum1, !prof !15
1710   %a4 = and i32 %li, 4
1711   %cmp4 = icmp eq i32 %a4, 0
1712   %inc2 = add i32 %inc1, 1
1713   br i1 %cmp4, label %bb2, label %bb1, !prof !15
1714
1715 bb1:
1716   %sum3 = add i32 %sum2, 44
1717   br label %bb2
1718
1719 bb2:
1720   %sum4 = phi i32 [ %sum1, %bb0 ], [ %sum3, %bb1 ]
1721   %cmp = icmp eq i32 %inc2, 100
1722   br i1 %cmp, label %bb3, label %bb0, !prof !15
1723
1724 bb3:
1725   ret i32 %sum4
1726 }
1727
1728
1729 ; Selects + Brs. Those share the condition value, which causes the
1730 ; targets/operands of the branch/select to be flipped.
1731 ; Roughly,
1732 ; t0 = *i
1733 ; if ((t0 & 255) != 0) {  // Likely true
1734 ;   sum1 = ((t0 & 1) == 0) ? sum0 : (sum0 + 42)  // Likely false
1735 ;   sum2 = ((t0 & 1) == 0) ? sum1 : (sum1 + 42)  // Likely false
1736 ;   if ((t0 & 1) != 0) { // Likely true
1737 ;     sum3 = sum2 + 44
1738 ;     sum4 = ((t0 & 8) == 0) ? sum3 : (sum3 + 44) // Likely false
1739 ;   }
1740 ;   sum5 = phi sum2, sum4
1741 ; }
1742 ; sum6 = phi sum0, sum5
1743 ; return sum6
1744 ; ->
1745 ; t0 = *i
1746 ; if ((t0 & 9) == 9) { // Likely true
1747 ;   tmp3 = sum0 + 85  // Dead
1748 ;   tmp4 = sum0 + 173
1749 ; } else {
1750 ;   if ((t0 & 255) != 0) {
1751 ;     sum2_nc = ((t0 & 1) == 0) ? sum0 : (sum0 + 85)
1752 ;     sum4_nc_v = ((t0 & 8) == 0) ? 44 : 88
1753 ;     sum4_nc = add sum2_nc + sum4_nc_v
1754 ;   }
1755 ; }
1756 ; sum6 = phi tmp4, sum0, sum2_nc, sum4_nc
1757 ; return sum6
1758 define i32 @test_chr_19(ptr %i, i32 %sum0) !prof !14 {
1759 ; CHECK-LABEL: @test_chr_19(
1760 ; CHECK-NEXT:  entry:
1761 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[I:%.*]], align 4
1762 ; CHECK-NEXT:    [[DOTFR1:%.*]] = freeze i32 [[TMP0]]
1763 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[DOTFR1]], 9
1764 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 9
1765 ; CHECK-NEXT:    br i1 [[TMP2]], label [[BB1:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
1766 ; CHECK:       bb1:
1767 ; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[SUM0:%.*]], 173
1768 ; CHECK-NEXT:    br label [[BB3:%.*]]
1769 ; CHECK:       entry.split.nonchr:
1770 ; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[DOTFR1]], 255
1771 ; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i32 [[TMP4]], 0
1772 ; CHECK-NEXT:    br i1 [[DOTNOT]], label [[BB3]], label [[BB0_NONCHR:%.*]], !prof [[PROF16]]
1773 ; CHECK:       bb0.nonchr:
1774 ; CHECK-NEXT:    [[TMP5:%.*]] = and i32 [[DOTFR1]], 1
1775 ; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i32 [[TMP5]], 0
1776 ; CHECK-NEXT:    [[TMP7:%.*]] = add i32 [[SUM0]], 85
1777 ; CHECK-NEXT:    [[SUM2_NONCHR:%.*]] = select i1 [[TMP6]], i32 [[SUM0]], i32 [[TMP7]], !prof [[PROF16]]
1778 ; CHECK-NEXT:    [[TMP8:%.*]] = and i32 [[DOTFR1]], 8
1779 ; CHECK-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[TMP8]], 0
1780 ; CHECK-NEXT:    [[SUM4_NONCHR_V:%.*]] = select i1 [[TMP9]], i32 44, i32 88
1781 ; CHECK-NEXT:    [[SUM4_NONCHR:%.*]] = add i32 [[SUM2_NONCHR]], [[SUM4_NONCHR_V]]
1782 ; CHECK-NEXT:    [[SUM5_NONCHR:%.*]] = select i1 [[TMP6]], i32 [[SUM2_NONCHR]], i32 [[SUM4_NONCHR]], !prof [[PROF16]]
1783 ; CHECK-NEXT:    br label [[BB3]]
1784 ; CHECK:       bb3:
1785 ; CHECK-NEXT:    [[SUM6:%.*]] = phi i32 [ [[TMP3]], [[BB1]] ], [ [[SUM0]], [[ENTRY_SPLIT_NONCHR]] ], [ [[SUM5_NONCHR]], [[BB0_NONCHR]] ]
1786 ; CHECK-NEXT:    ret i32 [[SUM6]]
1787 ;
1788 entry:
1789   %0 = load i32, ptr %i
1790   %1 = and i32 %0, 255
1791   %2 = icmp eq i32 %1, 0
1792   br i1 %2, label %bb3, label %bb0, !prof !15
1793
1794 bb0:
1795   %3 = and i32 %0, 1
1796   %4 = icmp eq i32 %3, 0
1797   %5 = add i32 %sum0, 42
1798   %sum1 = select i1 %4, i32 %sum0, i32 %5, !prof !15
1799   %6 = add i32 %sum1, 43
1800   %sum2 = select i1 %4, i32 %sum1, i32 %6, !prof !15
1801   br i1 %4, label %bb2, label %bb1, !prof !15
1802
1803 bb1:
1804   %sum3 = add i32 %sum2, 44
1805   %7 = and i32 %0, 8
1806   %8 = icmp eq i32 %7, 0
1807   %9 = add i32 %sum3, 44
1808   %sum4 = select i1 %8, i32 %sum3, i32 %9, !prof !15
1809   br label %bb2
1810
1811 bb2:
1812   %sum5 = phi i32 [ %sum2, %bb0 ], [ %sum4, %bb1 ]
1813   br label %bb3
1814
1815 bb3:
1816   %sum6 = phi i32 [ %sum0, %entry ], [ %sum5, %bb2 ]
1817   ret i32 %sum6
1818 }
1819
1820 ; Selects. The exit block, which belongs to the top-level region, has a select
1821 ; and causes the top-level region to be the outermost CHR scope with the
1822 ; subscope that includes the entry block with two selects. The outermost CHR
1823 ; scope doesn't see the selects in the entry block as the entry block is in the
1824 ; subscope and incorrectly sets the CHR hoist point to the branch rather than
1825 ; the first select in the entry block and causes the CHR'ed selects ("select i1
1826 ; false...") to incorrectly position above the CHR branch. This is testing
1827 ; against a quirk of how the region analysis handles the entry block.
1828 ; Roughly,
1829 ; i0 = *i
1830 ; sum2 = ((i0 & 2) == 0) ? sum0 : (sum0 + 43) // Likely false
1831 ; sum3 = ((i0 & 4) == 0) ? sum2 : (sum2 + 44) // Likely false
1832 ; if (j)
1833 ;   foo()
1834 ; i5 = *i
1835 ; v13 = (i5 == 44) ? i5 : sum3
1836 ; return v13
1837 ; ->
1838 ; i0 = *i
1839 ; if ((i0 & 6) != 6) { // Likely true
1840 ;   v9 = sum0 + 87
1841 ;   if (j)
1842 ;     foo()
1843 ; } else {
1844 ;   sum2.nc = ((i0 & 2) == 0) ? sum0 : (sum0 + 43)
1845 ;   sum3.nc = ((i0 & 4) == 0) ? sum2.nc : (sum2.nc + 44)
1846 ;   if (j)
1847 ;     foo()
1848 ; }
1849 ; t2 = phi v9, sum3.nc
1850 ; i5 = *i
1851 ; v13 = (i5 == 44) ? 44 : t2
1852 ; return v13
1853 define i32 @test_chr_20(ptr %i, i32 %sum0, i1 %j) !prof !14 {
1854 ; CHECK-LABEL: @test_chr_20(
1855 ; CHECK-NEXT:  entry:
1856 ; CHECK-NEXT:    [[I0:%.*]] = load i32, ptr [[I:%.*]], align 4
1857 ; CHECK-NEXT:    [[I0_FR:%.*]] = freeze i32 [[I0]]
1858 ; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[I0_FR]], 6
1859 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 6
1860 ; CHECK-NEXT:    br i1 [[TMP1]], label [[ENTRY_SPLIT:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
1861 ; CHECK:       entry.split:
1862 ; CHECK-NEXT:    [[V9:%.*]] = add i32 [[SUM0:%.*]], 87
1863 ; CHECK-NEXT:    br i1 [[J:%.*]], label [[BB1:%.*]], label [[BB4:%.*]]
1864 ; CHECK:       bb1:
1865 ; CHECK-NEXT:    call void @foo()
1866 ; CHECK-NEXT:    br label [[BB4]]
1867 ; CHECK:       entry.split.nonchr:
1868 ; CHECK-NEXT:    [[V8:%.*]] = add i32 [[SUM0]], 43
1869 ; CHECK-NEXT:    [[V3:%.*]] = and i32 [[I0_FR]], 2
1870 ; CHECK-NEXT:    [[V4_NOT:%.*]] = icmp eq i32 [[V3]], 0
1871 ; CHECK-NEXT:    [[SUM2_NONCHR:%.*]] = select i1 [[V4_NOT]], i32 [[SUM0]], i32 [[V8]], !prof [[PROF16]]
1872 ; CHECK-NEXT:    [[V6_NONCHR:%.*]] = and i32 [[I0_FR]], 4
1873 ; CHECK-NEXT:    [[V5_NONCHR:%.*]] = icmp eq i32 [[V6_NONCHR]], 0
1874 ; CHECK-NEXT:    [[V9_NONCHR:%.*]] = add i32 [[SUM2_NONCHR]], 44
1875 ; CHECK-NEXT:    [[SUM3_NONCHR:%.*]] = select i1 [[V5_NONCHR]], i32 [[SUM2_NONCHR]], i32 [[V9_NONCHR]], !prof [[PROF16]]
1876 ; CHECK-NEXT:    br i1 [[J]], label [[BB1_NONCHR:%.*]], label [[BB4]]
1877 ; CHECK:       bb1.nonchr:
1878 ; CHECK-NEXT:    call void @foo()
1879 ; CHECK-NEXT:    br label [[BB4]]
1880 ; CHECK:       bb4:
1881 ; CHECK-NEXT:    [[TMP2:%.*]] = phi i32 [ [[V9]], [[BB1]] ], [ [[V9]], [[ENTRY_SPLIT]] ], [ [[SUM3_NONCHR]], [[BB1_NONCHR]] ], [ [[SUM3_NONCHR]], [[ENTRY_SPLIT_NONCHR]] ]
1882 ; CHECK-NEXT:    [[I5:%.*]] = load i32, ptr [[I]], align 4
1883 ; CHECK-NEXT:    [[V12:%.*]] = icmp eq i32 [[I5]], 44
1884 ; CHECK-NEXT:    [[V13:%.*]] = select i1 [[V12]], i32 44, i32 [[TMP2]], !prof [[PROF16]]
1885 ; CHECK-NEXT:    ret i32 [[V13]]
1886 ;
1887 entry:
1888   %i0 = load i32, ptr %i
1889   %v3 = and i32 %i0, 2
1890   %v4 = icmp eq i32 %v3, 0
1891   %v8 = add i32 %sum0, 43
1892   %sum2 = select i1 %v4, i32 %sum0, i32 %v8, !prof !15
1893   %v6 = and i32 %i0, 4
1894   %v5 = icmp eq i32 %v6, 0
1895   %v9 = add i32 %sum2, 44
1896   %sum3 = select i1 %v5, i32 %sum2, i32 %v9, !prof !15
1897   br i1 %j, label %bb1, label %bb4
1898
1899 bb1:
1900   call void @foo()
1901   br label %bb4
1902
1903 bb4:
1904   %i5 = load i32, ptr %i
1905   %v12 = icmp eq i32 %i5, 44
1906   %v13 = select i1 %v12, i32 %i5, i32 %sum3, !prof !15
1907   ret i32 %v13
1908 }
1909
1910 ; FIXME: This does not currently reach a fix point, because we don't make use
1911 ; of a freeze that is pushed up the instruction chain later.
1912
1913 ; Test the case where two scopes share a common instruction to hoist (%cmp.i).
1914 ; Two scopes would hoist it to their hoist points, but since the outer scope
1915 ; hoists (entry/bb6-9) it first to its hoist point, it'd be wrong (causing bad
1916 ; IR) for the inner scope (bb1-4) to hoist the same instruction to its hoist
1917 ; point.
1918 ; Roughly,
1919 ; if (j != k) {
1920 ;   if (i != 2)
1921 ;     foo();
1922 ;   cmp.i = i == 86
1923 ;   if (!cmp.i)
1924 ;     foo();
1925 ;   if (j != i)
1926 ;     foo();
1927 ;   if (!cmp.i)
1928 ;     foo();
1929 ;  }
1930 ;  return 45;
1931 define i32 @test_chr_21(i64 %i, i64 %k, i64 %j) "instcombine-no-verify-fixpoint" !prof !14 {
1932 ; CHECK-LABEL: @test_chr_21(
1933 ; CHECK-NEXT:  entry:
1934 ; CHECK-NEXT:    [[I_FR:%.*]] = freeze i64 [[I:%.*]]
1935 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ne i64 [[J:%.*]], [[K:%.*]]
1936 ; CHECK-NEXT:    [[TMP0:%.*]] = freeze i1 [[CMP0]]
1937 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp ne i64 [[J]], [[I_FR]]
1938 ; CHECK-NEXT:    [[CMP_I:%.*]] = icmp ne i64 [[I_FR]], 86
1939 ; CHECK-NEXT:    [[TMP1:%.*]] = freeze i1 [[CMP3]]
1940 ; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[TMP0]], [[TMP1]]
1941 ; CHECK-NEXT:    [[TMP3:%.*]] = and i1 [[TMP2]], [[CMP_I]]
1942 ; CHECK-NEXT:    br i1 [[TMP3]], label [[BB1:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
1943 ; CHECK:       bb1:
1944 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i64 [[I_FR]], 2
1945 ; CHECK-NEXT:    switch i64 [[I_FR]], label [[BB2:%.*]] [
1946 ; CHECK-NEXT:      i64 2, label [[BB3_NONCHR2:%.*]]
1947 ; CHECK-NEXT:      i64 86, label [[BB2_NONCHR1:%.*]]
1948 ; CHECK-NEXT:    ], !prof [[PROF19:![0-9]+]]
1949 ; CHECK:       bb2:
1950 ; CHECK-NEXT:    call void @foo()
1951 ; CHECK-NEXT:    call void @foo()
1952 ; CHECK-NEXT:    br label [[BB7:%.*]]
1953 ; CHECK:       bb2.nonchr1:
1954 ; CHECK-NEXT:    call void @foo()
1955 ; CHECK-NEXT:    br label [[BB3_NONCHR2]]
1956 ; CHECK:       bb3.nonchr2:
1957 ; CHECK-NEXT:    br i1 [[CMP_I]], label [[BB4_NONCHR3:%.*]], label [[BB7]], !prof [[PROF18]]
1958 ; CHECK:       bb4.nonchr3:
1959 ; CHECK-NEXT:    call void @foo()
1960 ; CHECK-NEXT:    br label [[BB7]]
1961 ; CHECK:       bb7:
1962 ; CHECK-NEXT:    call void @foo()
1963 ; CHECK-NEXT:    call void @foo()
1964 ; CHECK-NEXT:    br label [[BB10:%.*]]
1965 ; CHECK:       entry.split.nonchr:
1966 ; CHECK-NEXT:    br i1 [[TMP0]], label [[BB1_NONCHR:%.*]], label [[BB10]], !prof [[PROF18]]
1967 ; CHECK:       bb1.nonchr:
1968 ; CHECK-NEXT:    [[CMP2_NONCHR:%.*]] = icmp eq i64 [[I_FR]], 2
1969 ; CHECK-NEXT:    br i1 [[CMP2_NONCHR]], label [[BB3_NONCHR:%.*]], label [[BB2_NONCHR:%.*]], !prof [[PROF16]]
1970 ; CHECK:       bb3.nonchr:
1971 ; CHECK-NEXT:    [[CMP_I_NONCHR:%.*]] = icmp eq i64 [[I_FR]], 86
1972 ; CHECK-NEXT:    br i1 [[CMP_I_NONCHR]], label [[BB6_NONCHR:%.*]], label [[BB4_NONCHR:%.*]], !prof [[PROF16]]
1973 ; CHECK:       bb6.nonchr:
1974 ; CHECK-NEXT:    [[CMP3_NONCHR:%.*]] = icmp eq i64 [[J]], [[I_FR]]
1975 ; CHECK-NEXT:    br i1 [[CMP3_NONCHR]], label [[BB8_NONCHR:%.*]], label [[BB7_NONCHR:%.*]], !prof [[PROF16]]
1976 ; CHECK:       bb8.nonchr:
1977 ; CHECK-NEXT:    br i1 [[CMP_I_NONCHR]], label [[BB10]], label [[BB9_NONCHR:%.*]], !prof [[PROF16]]
1978 ; CHECK:       bb9.nonchr:
1979 ; CHECK-NEXT:    call void @foo()
1980 ; CHECK-NEXT:    br label [[BB10]]
1981 ; CHECK:       bb7.nonchr:
1982 ; CHECK-NEXT:    call void @foo()
1983 ; CHECK-NEXT:    br label [[BB8_NONCHR]]
1984 ; CHECK:       bb4.nonchr:
1985 ; CHECK-NEXT:    call void @foo()
1986 ; CHECK-NEXT:    br label [[BB6_NONCHR]]
1987 ; CHECK:       bb2.nonchr:
1988 ; CHECK-NEXT:    call void @foo()
1989 ; CHECK-NEXT:    br label [[BB3_NONCHR]]
1990 ; CHECK:       bb10:
1991 ; CHECK-NEXT:    ret i32 45
1992 ;
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}