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