[SimplifyCFG] FoldTwoEntryPHINode(): consider *total* speculation cost, not per-BB cost

[lebedev.ri]

Summary

Previously, if the threshold was 2, we were willing to speculatively
execute 2 cheap instructions in both basic blocks (thus we were willing
to speculatively execute cost = 4), but weren't willing to speculate
when one BB had 3 instructions and other one had no instructions,
even thought that would have total cost of 3.

This looks inconsistent to me.
I don't think cmov-like instructions will start executing
until both of it's inputs are available: https://godbolt.org/z/zgHePf
So i don't see why the existing behavior is the correct one.

Also, let's add it's own cl::opt for this threshold.

This is an alternative solution to D65148:
This fix is mainly motivated by signbit-like-value-extension.ll test.
That pattern comes up in JPEG decoding, see e.g.
Figure F.12 – Extending the sign bit of a decoded value in V
of ITU T.81 (JPEG specification).
That branch is not predictable, and it is within the innermost loop,
so the fact that that pattern ends up being stuck with a branch
instead of select (i.e. CMOV for x86) is unlikely to be beneficial.

This has great results on the final assembly (vanilla test-suite + RawSpeed): (metric pass - D67240)

metric	old	new	delta	%
x86-mi-counting.NumMachineFunctions	37720	37721	1	0.00%
x86-mi-counting.NumMachineBasicBlocks	773545	771181	-2364	-0.31%
x86-mi-counting.NumMachineInstructions	7488843	7486442	-2401	-0.03%
x86-mi-counting.NumUncondBR	135770	135543	-227	-0.17%
x86-mi-counting.NumCondBR	423753	422187	-1566	-0.37%
x86-mi-counting.NumCMOV	24815	25731	916	3.69%
x86-mi-counting.NumVecBlend	17	17	0	0.00%

We significantly decrease basic block count, notably decrease instruction count,
significantly decrease branch count and very significantly increase cmov count.

Performance-wise, unsurprisingly, this has great effect on
target RawSpeed benchmark. I'm seeing 5 major improvements:

Benchmark                                                                                             Time             CPU      Time Old      Time New       CPU Old       CPU New
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Samsung/NX3000/_3184416.SRW/threads:8/process_time/real_time_pvalue                                 0.0000          0.0000      U Test, Repetitions: 49 vs 49
Samsung/NX3000/_3184416.SRW/threads:8/process_time/real_time_mean                                  -0.3064         -0.3064      226.9913      157.4452      226.9800      157.4384
Samsung/NX3000/_3184416.SRW/threads:8/process_time/real_time_median                                -0.3057         -0.3057      226.8407      157.4926      226.8282      157.4828
Samsung/NX3000/_3184416.SRW/threads:8/process_time/real_time_stddev                                -0.4985         -0.4954        0.3051        0.1530        0.3040        0.1534
Kodak/DCS760C/86L57188.DCR/threads:8/process_time/real_time_pvalue                                  0.0000          0.0000      U Test, Repetitions: 49 vs 49
Kodak/DCS760C/86L57188.DCR/threads:8/process_time/real_time_mean                                   -0.1747         -0.1747       80.4787       66.4227       80.4771       66.4146
Kodak/DCS760C/86L57188.DCR/threads:8/process_time/real_time_median                                 -0.1742         -0.1743       80.4686       66.4542       80.4690       66.4436
Kodak/DCS760C/86L57188.DCR/threads:8/process_time/real_time_stddev                                 +0.6089         +0.5797        0.0670        0.1078        0.0673        0.1062
Sony/DSLR-A230/DSC08026.ARW/threads:8/process_time/real_time_pvalue                                 0.0000          0.0000      U Test, Repetitions: 49 vs 49
Sony/DSLR-A230/DSC08026.ARW/threads:8/process_time/real_time_mean                                  -0.1598         -0.1598      171.6996      144.2575      171.6915      144.2538
Sony/DSLR-A230/DSC08026.ARW/threads:8/process_time/real_time_median                                -0.1598         -0.1597      171.7109      144.2755      171.7018      144.2766
Sony/DSLR-A230/DSC08026.ARW/threads:8/process_time/real_time_stddev                                +0.4024         +0.3850        0.0847        0.1187        0.0848        0.1175
Canon/EOS 77D/IMG_4049.CR2/threads:8/process_time/real_time_pvalue                                  0.0000          0.0000      U Test, Repetitions: 49 vs 49
Canon/EOS 77D/IMG_4049.CR2/threads:8/process_time/real_time_mean                                   -0.0550         -0.0551      280.3046      264.8800      280.3017      264.8559
Canon/EOS 77D/IMG_4049.CR2/threads:8/process_time/real_time_median                                 -0.0554         -0.0554      280.2628      264.7360      280.2574      264.7297
Canon/EOS 77D/IMG_4049.CR2/threads:8/process_time/real_time_stddev                                 +0.7005         +0.7041        0.2779        0.4725        0.2775        0.4729
Canon/EOS 5DS/2K4A9929.CR2/threads:8/process_time/real_time_pvalue                                  0.0000          0.0000      U Test, Repetitions: 49 vs 49
Canon/EOS 5DS/2K4A9929.CR2/threads:8/process_time/real_time_mean                                   -0.0354         -0.0355      316.7396      305.5208      316.7342      305.4890
Canon/EOS 5DS/2K4A9929.CR2/threads:8/process_time/real_time_median                                 -0.0354         -0.0356      316.6969      305.4798      316.6917      305.4324
Canon/EOS 5DS/2K4A9929.CR2/threads:8/process_time/real_time_stddev                                 +0.0493         +0.0330        0.3562        0.3737        0.3563        0.3681

[xbolva00]

4 major improvements

and no regressions? Please also provide test suite numbers.

[lebedev.ri]

In D67318#1662148, @xbolva00 wrote:

4 major improvements

Note that those numbers are for D65148;

In D67318#1662148, @xbolva00 wrote:

and no regressions?

See https://reviews.llvm.org/D65148#1602979 for that disscussion.

I have not rerun any of the measurements that were done
in that patch here as of yet, but the results may or may not
be better since this actually speculates less instructions.

In D67318#1662148, @xbolva00 wrote:

Please also provide test suite numbers.

As i have stated previously, that is not feasible for me,
i have tried and the results are always too noisy,
the tooling there is just too clumsy for me.
If you have working setup please feel free to post noise-less actionable the numbers.

[xbolva00]

I dont have such setup, but some folks could run SPEC for you. Maybe send a RFC about this patch to llvm-dev? :)

I think we really need proper benchmark data before any “LGTM”.

[lebedev.ri]

D67240 numbers for RawSpeed: (rL371316 vs. these two patches)

metric	old	new	delta	% change
x86-mi-counting.NumMachineFunctions	10513	10513	0	0.00%
x86-mi-counting.NumMachineBasicBlocks	200350	200178	-172	-0.09%
x86-mi-counting.NumMachineInstructions	3307866	3305737	-2129	-0.06%
x86-mi-counting.NumUncondBR	33479	33463	-16	-0.05%
x86-mi-counting.NumCondBR	91062	90925	-137	-0.15%
x86-mi-counting.NumCMOV	4195	4276	81	1.93%
x86-mi-counting.NumVecBlend	17	17	0	0.00%

rawspeed-x86-mi-count-0-old.json359 KBDownload

rawspeed-x86-mi-count-1-new.json359 KBDownload

This is pretty in-line with what we had in

In D65148#1660471, @lebedev.ri wrote:

Numbers for RawSpeed:

metric	old	new	delta	% change
x86-mi-counting.NumMachineFunctions	10513	10513	0	0.00%
x86-mi-counting.NumMachineBasicBlocks	200350	200163	-187	-0.09%
x86-mi-counting.NumMachineInstructions	3307866	3305504	-2362	-0.07%
x86-mi-counting.NumUncondBR	33479	33465	-14	-0.04%
x86-mi-counting.NumCondBR	91062	90908	-154	-0.17%
x86-mi-counting.NumCMOV	4195	4284	89	2.12%
x86-mi-counting.NumVecBlend	17	17	0	0.00%

results-old.json359 KBDownload

results-new.json359 KBDownload

[lebedev.ri]

@efriedma

D67240 numbers for vanilla (no externals, no rawspeed) test-suite: (rL371316 vs. these two patches)

metric	old	new	delta	% change
x86-mi-counting.NumMachineFunctions	27207	27208	1	0.00%
x86-mi-counting.NumMachineBasicBlocks	573195	571003	-2192	-0.38%
x86-mi-counting.NumMachineInstructions	4180977	4180705	-272	-0.01%
x86-mi-counting.NumUncondBR	102291	102080	-211	-0.21%
x86-mi-counting.NumCondBR	332691	331262	-1429	-0.43%
x86-mi-counting.NumCMOV	20620	21455	835	4.05%
x86-mi-counting.NumVecBlend	0	0	0	0.00%

llvm-test-suite-x86-mi-count-0-old.json4 MBDownload

llvm-test-suite-x86-mi-count-1-new.json4 MBDownload

Which is actually extremely better than what we had in D65148,
we now produce more cmov's (good), and even further decrease everything else including instruction count (good).

In D65148#1660558, @lebedev.ri wrote:

metric	old	new	delta	% change
x86-mi-counting.NumMachineFunctions	27189	27189	0	0.00%
x86-mi-counting.NumMachineBasicBlocks	573079	571509	-1570	-0.27%
x86-mi-counting.NumMachineInstructions	4180244	4180750	506	0.01%
x86-mi-counting.NumUncondBR	102271	102115	-156	-0.15%
x86-mi-counting.NumCondBR	332645	331669	-976	-0.29%
x86-mi-counting.NumCMOV	20620	21134	514	2.49%
x86-mi-counting.NumVecBlend	0	0	0	0.00%

results-testsuite-old.json4 MBDownload

results-testsuite-new.json4 MBDownload

(the NumMachineFunctions changed because i did D65148#1660558 without xray tests...)

[xbolva00]

Nice, these new results look very good!

[lebedev.ri]

And got perf numbers. No particular differences from what i have seen in D65148, ~5 major improvements, no notable regressions.
TLDR: On average on used benchmarks this results in -~3% speedup.

rawspeed-benchmark-0-old.json1 MBDownload

rawspeed-benchmark-1-new.json1 MBDownload

$ /usr/src/googlebenchmark/tools/compare.py -a benchmarks rawspeed-benchmark-0-old.json rawspeed-benchmark-1-new.json 
Comparing rawspeed-benchmark-0-old.json to rawspeed-benchmark-1-new.json
Benchmark                                                                                             Time             CPU      Time Old      Time New       CPU Old       CPU New
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Canon/EOS 5D Mark II/09.canon.sraw1.cr2/threads:8/process_time/real_time_pvalue                     0.0000          0.0000      U Test, Repetitions: 49 vs 49
Canon/EOS 5D Mark II/09.canon.sraw1.cr2/threads:8/process_time/real_time_mean                      -0.0236         -0.0236      222.5219      217.2595      222.4980      217.2369
Canon/EOS 5D Mark II/09.canon.sraw1.cr2/threads:8/process_time/real_time_median                    -0.0236         -0.0236      222.4776      217.2206      222.4307      217.1793
Canon/EOS 5D Mark II/09.canon.sraw1.cr2/threads:8/process_time/real_time_stddev                    -0.1381         -0.1389        0.5084        0.4382        0.5057        0.4354
Canon/EOS 5D Mark II/10.canon.sraw2.cr2/threads:8/process_time/real_time_pvalue                     0.0000          0.0000      U Test, Repetitions: 49 vs 49
Canon/EOS 5D Mark II/10.canon.sraw2.cr2/threads:8/process_time/real_time_mean                      -0.0153         -0.0153      129.8367      127.8563      129.8264      127.8442
Canon/EOS 5D Mark II/10.canon.sraw2.cr2/threads:8/process_time/real_time_median                    -0.0153         -0.0152      129.7890      127.8042      129.7693      127.7967
Canon/EOS 5D Mark II/10.canon.sraw2.cr2/threads:8/process_time/real_time_stddev                    -0.6448         -0.6457        0.6080        0.2159        0.6068        0.2150
Canon/EOS 5DS/2K4A9927.CR2/threads:8/process_time/real_time_pvalue                                  0.0000          0.0000      U Test, Repetitions: 49 vs 49
Canon/EOS 5DS/2K4A9927.CR2/threads:8/process_time/real_time_mean                                   -0.0181         -0.0181      444.5168      436.4534      444.4694      436.4027
Canon/EOS 5DS/2K4A9927.CR2/threads:8/process_time/real_time_median                                 -0.0181         -0.0181      444.5686      436.5023      444.5210      436.4561
Canon/EOS 5DS/2K4A9927.CR2/threads:8/process_time/real_time_stddev                                 +0.1821         +0.1897        0.5460        0.6454        0.5439        0.6471
Canon/EOS 5DS/2K4A9928.CR2/threads:8/process_time/real_time_pvalue                                  0.0000          0.0000      U Test, Repetitions: 49 vs 49
Canon/EOS 5DS/2K4A9928.CR2/threads:8/process_time/real_time_mean                                   -0.0229         -0.0229      567.6662      554.6384      567.6017      554.5808
Canon/EOS 5DS/2K4A9928.CR2/threads:8/process_time/real_time_median                                 -0.0232         -0.0232      567.7452      554.5751      567.6885      554.5071
Canon/EOS 5DS/2K4A9928.CR2/threads:8/process_time/real_time_stddev                                 +0.4212         +0.4445        0.7544        1.0721        0.7371        1.0648
Canon/EOS 5DS/2K4A9929.CR2/threads:8/process_time/real_time_pvalue                                  0.0000          0.0000      U Test, Repetitions: 49 vs 49
Canon/EOS 5DS/2K4A9929.CR2/threads:8/process_time/real_time_mean                                   -0.0354         -0.0355      316.7396      305.5208      316.7342      305.4890
Canon/EOS 5DS/2K4A9929.CR2/threads:8/process_time/real_time_median                                 -0.0354         -0.0356      316.6969      305.4798      316.6917      305.4324
Canon/EOS 5DS/2K4A9929.CR2/threads:8/process_time/real_time_stddev                                 +0.0493         +0.0330        0.3562        0.3737        0.3563        0.3681
Canon/EOS 40D/_MG_0154.CR2/threads:8/process_time/real_time_pvalue                                  0.0000          0.0000      U Test, Repetitions: 49 vs 49
Canon/EOS 40D/_MG_0154.CR2/threads:8/process_time/real_time_mean                                   -0.0076         -0.0077       56.9675       56.5326       56.9671       56.5273
Canon/EOS 40D/_MG_0154.CR2/threads:8/process_time/real_time_median                                 -0.0079         -0.0080       56.9662       56.5175       56.9664       56.5097
Canon/EOS 40D/_MG_0154.CR2/threads:8/process_time/real_time_stddev                                 -0.4629         -0.4702        0.1688        0.0907        0.1684        0.0892
Canon/EOS 77D/IMG_4049.CR2/threads:8/process_time/real_time_pvalue                                  0.0000          0.0000      U Test, Repetitions: 49 vs 49
Canon/EOS 77D/IMG_4049.CR2/threads:8/process_time/real_time_mean                                   -0.0550         -0.0551      280.3046      264.8800      280.3017      264.8559
Canon/EOS 77D/IMG_4049.CR2/threads:8/process_time/real_time_median                                 -0.0554         -0.0554      280.2628      264.7360      280.2574      264.7297
Canon/EOS 77D/IMG_4049.CR2/threads:8/process_time/real_time_stddev                                 +0.7005         +0.7041        0.2779        0.4725        0.2775        0.4729
Canon/EOS D30/CRW_2444.CRW/threads:8/process_time/real_time_pvalue                                  0.0000          0.0000      U Test, Repetitions: 49 vs 49
Canon/EOS D30/CRW_2444.CRW/threads:8/process_time/real_time_mean                                   +0.0042         +0.0041       62.7856       63.0503       62.7856       63.0448
Canon/EOS D30/CRW_2444.CRW/threads:8/process_time/real_time_median                                 +0.0041         +0.0040       62.7851       63.0413       62.7854       63.0344
Canon/EOS D30/CRW_2444.CRW/threads:8/process_time/real_time_stddev                                 -0.1853         -0.2144        0.0556        0.0453        0.0551        0.0433
Canon/PowerShot G1/crw_1693.crw/threads:8/process_time/real_time_pvalue                             0.0000          0.0000      U Test, Repetitions: 49 vs 49
Canon/PowerShot G1/crw_1693.crw/threads:8/process_time/real_time_mean                              +0.0046         +0.0045       63.7451       64.0406       63.7450       64.0343
Canon/PowerShot G1/crw_1693.crw/threads:8/process_time/real_time_median                            +0.0045         +0.0045       63.7339       64.0213       63.7321       64.0207
Canon/PowerShot G1/crw_1693.crw/threads:8/process_time/real_time_stddev                            +0.4642         +0.4343        0.0484        0.0709        0.0479        0.0687
Fujifilm/GFX 50S/20170525_0037TEST.RAF/threads:8/process_time/real_time_pvalue                      0.0000          0.0000      U Test, Repetitions: 49 vs 49
Fujifilm/GFX 50S/20170525_0037TEST.RAF/threads:8/process_time/real_time_mean                       -0.0086         -0.0038      486.1760      481.9715     3598.8707     3585.2633
Fujifilm/GFX 50S/20170525_0037TEST.RAF/threads:8/process_time/real_time_median                     -0.0112         -0.0057      487.3562      481.8991     3604.8764     3584.3669
Fujifilm/GFX 50S/20170525_0037TEST.RAF/threads:8/process_time/real_time_stddev                     -0.8226         -0.5578        2.1500        0.3815       10.4607        4.6256
Fujifilm/X-Pro2/_DSF3051.RAF/threads:8/process_time/real_time_pvalue                                0.2217          0.0239      U Test, Repetitions: 49 vs 49
Fujifilm/X-Pro2/_DSF3051.RAF/threads:8/process_time/real_time_mean                                 -0.0031         -0.0029      185.9799      185.3941     1483.9142     1479.5656
Fujifilm/X-Pro2/_DSF3051.RAF/threads:8/process_time/real_time_median                               -0.0000         -0.0005      185.7836      185.7747     1482.7799     1482.0870
Fujifilm/X-Pro2/_DSF3051.RAF/threads:8/process_time/real_time_stddev                               +0.0014         -0.0133        1.0597        1.0611        7.0797        6.9857
GoPro/HERO6 Black/GOPR9172.GPR/threads:8/process_time/real_time_pvalue                              0.0647          0.0271      U Test, Repetitions: 49 vs 49
GoPro/HERO6 Black/GOPR9172.GPR/threads:8/process_time/real_time_mean                               +0.0016         +0.0017       38.8542       38.9182      309.6872      310.2127
GoPro/HERO6 Black/GOPR9172.GPR/threads:8/process_time/real_time_median                             +0.0021         +0.0028       38.7812       38.8636      308.9483      309.8222
GoPro/HERO6 Black/GOPR9172.GPR/threads:8/process_time/real_time_stddev                             -0.3860         -0.3828        0.5640        0.3463        3.6906        2.2780
Kodak/DCS760C/86L57188.DCR/threads:8/process_time/real_time_pvalue                                  0.0000          0.0000      U Test, Repetitions: 49 vs 49
Kodak/DCS760C/86L57188.DCR/threads:8/process_time/real_time_mean                                   -0.1747         -0.1747       80.4787       66.4227       80.4771       66.4146
Kodak/DCS760C/86L57188.DCR/threads:8/process_time/real_time_median                                 -0.1742         -0.1743       80.4686       66.4542       80.4690       66.4436
Kodak/DCS760C/86L57188.DCR/threads:8/process_time/real_time_stddev                                 +0.6089         +0.5797        0.0670        0.1078        0.0673        0.1062
Nikon/D5600/2018-01-20_01-14_0792.NEF/threads:8/process_time/real_time_pvalue                       0.0048          0.0024      U Test, Repetitions: 49 vs 49
Nikon/D5600/2018-01-20_01-14_0792.NEF/threads:8/process_time/real_time_mean                        -0.0006         -0.0007      375.4644      375.2458      375.4502      375.1952
Nikon/D5600/2018-01-20_01-14_0792.NEF/threads:8/process_time/real_time_median                      -0.0013         -0.0014      376.6812      376.2053      376.6632      376.1458
Nikon/D5600/2018-01-20_01-14_0792.NEF/threads:8/process_time/real_time_stddev                      -0.1310         -0.1324        1.8502        1.6079        1.8492        1.6045
Nikon/D5600/2018-01-20_01-14_0793.NEF/threads:8/process_time/real_time_pvalue                       0.7546          0.5649      U Test, Repetitions: 49 vs 49
Nikon/D5600/2018-01-20_01-14_0793.NEF/threads:8/process_time/real_time_mean                        -0.0025         -0.0026      430.4334      429.3462      430.4185      429.2971
Nikon/D5600/2018-01-20_01-14_0793.NEF/threads:8/process_time/real_time_median                      -0.0000         -0.0001      429.2898      429.2758      429.2598      429.2311
Nikon/D5600/2018-01-20_01-14_0793.NEF/threads:8/process_time/real_time_stddev                      -0.7837         -0.7873        2.3148        0.5008        2.3167        0.4928
Nikon/D7200/DSC_0977.NEF/threads:8/process_time/real_time_pvalue                                    0.0001          0.0001      U Test, Repetitions: 49 vs 49
Nikon/D7200/DSC_0977.NEF/threads:8/process_time/real_time_mean                                     -0.0017         -0.0017      254.5381      254.1162      254.5281      254.0925
Nikon/D7200/DSC_0977.NEF/threads:8/process_time/real_time_median                                   -0.0011         -0.0012      254.4295      254.1423      254.4156      254.1112
Nikon/D7200/DSC_0977.NEF/threads:8/process_time/real_time_stddev                                   +0.2642         +0.2611        0.4071        0.5146        0.4063        0.5123
Nikon/D7200/DSC_0978.NEF/threads:8/process_time/real_time_pvalue                                    0.0000          0.0000      U Test, Repetitions: 49 vs 49
Nikon/D7200/DSC_0978.NEF/threads:8/process_time/real_time_mean                                     +0.0086         +0.0085      247.1756      249.3010      247.1651      249.2767
Nikon/D7200/DSC_0978.NEF/threads:8/process_time/real_time_median                                   +0.0081         +0.0081      247.1551      249.1528      247.1444      249.1472
Nikon/D7200/DSC_0978.NEF/threads:8/process_time/real_time_stddev                                   +1.1420         +1.1485        0.2862        0.6131        0.2854        0.6132
Nikon/D7200/DSC_0979.NEF/threads:8/process_time/real_time_pvalue                                    0.1231          0.1574      U Test, Repetitions: 49 vs 49
Nikon/D7200/DSC_0979.NEF/threads:8/process_time/real_time_mean                                     +0.0011         +0.0009      234.2886      234.5454      234.2788      234.4844
Nikon/D7200/DSC_0979.NEF/threads:8/process_time/real_time_median                                   +0.0008         +0.0007      234.2195      234.4022      234.2126      234.3658
Nikon/D7200/DSC_0979.NEF/threads:8/process_time/real_time_stddev                                   +1.7501         +1.3553        0.2661        0.7319        0.2653        0.6249
Nikon/D7200/DSC_0982.NEF/threads:8/process_time/real_time_pvalue                                    0.0000          0.0000      U Test, Repetitions: 49 vs 49
Nikon/D7200/DSC_0982.NEF/threads:8/process_time/real_time_mean                                     +0.0054         +0.0052      235.1888      236.4484      235.1830      236.4139
Nikon/D7200/DSC_0982.NEF/threads:8/process_time/real_time_median                                   +0.0050         +0.0049      235.1839      236.3490      235.1782      236.3416
Nikon/D7200/DSC_0982.NEF/threads:8/process_time/real_time_stddev                                   +1.5848         +1.5295        0.2262        0.5846        0.2256        0.5706
Olympus/XZ-1/p1319978.orf/threads:8/process_time/real_time_pvalue                                   0.0021          0.0010      U Test, Repetitions: 49 vs 49
Olympus/XZ-1/p1319978.orf/threads:8/process_time/real_time_mean                                    +0.0004         +0.0004      219.0685      219.1491      219.0624      219.1499
Olympus/XZ-1/p1319978.orf/threads:8/process_time/real_time_median                                  +0.0004         +0.0005      219.0479      219.1360      219.0389      219.1375
Olympus/XZ-1/p1319978.orf/threads:8/process_time/real_time_stddev                                  -0.2462         -0.2431        0.1743        0.1314        0.1730        0.1309
Panasonic/DC-G9/P1000476.RW2/threads:8/process_time/real_time_pvalue                                0.0000          0.0000      U Test, Repetitions: 49 vs 49
Panasonic/DC-G9/P1000476.RW2/threads:8/process_time/real_time_mean                                 -0.0300         -0.0322       14.1339       13.7092      112.5427      108.9215
Panasonic/DC-G9/P1000476.RW2/threads:8/process_time/real_time_median                               -0.0289         -0.0335       14.1253       13.7178      112.7482      108.9693
Panasonic/DC-G9/P1000476.RW2/threads:8/process_time/real_time_stddev                               -0.2187         -0.3065        0.2117        0.1654        1.5642        1.0847
Panasonic/DC-GH5/_T012014.RW2/threads:8/process_time/real_time_pvalue                               0.0000          0.0000      U Test, Repetitions: 49 vs 49
Panasonic/DC-GH5/_T012014.RW2/threads:8/process_time/real_time_mean                                +0.0103         +0.0104       27.0501       27.3287      215.7217      217.9707
Panasonic/DC-GH5/_T012014.RW2/threads:8/process_time/real_time_median                              +0.0103         +0.0104       27.0693       27.3475      215.8385      218.0814
Panasonic/DC-GH5/_T012014.RW2/threads:8/process_time/real_time_stddev                              +0.0838         +0.1371        0.2002        0.2170        1.2856        1.4619
Panasonic/DC-GH5S/P1022085.RW2/threads:8/process_time/real_time_pvalue                              0.0000          0.0000      U Test, Repetitions: 49 vs 49
Panasonic/DC-GH5S/P1022085.RW2/threads:8/process_time/real_time_mean                               +0.0533         +0.0531        5.0627        5.3324       40.3521       42.4956
Panasonic/DC-GH5S/P1022085.RW2/threads:8/process_time/real_time_median                             +0.0560         +0.0551        5.0707        5.3547       40.4043       42.6317
Panasonic/DC-GH5S/P1022085.RW2/threads:8/process_time/real_time_stddev                             +0.0148         +0.0363        0.0547        0.0555        0.3523        0.3651
Pentax/K10D/_IGP7284.PEF/threads:8/process_time/real_time_pvalue                                    0.0000          0.0000      U Test, Repetitions: 49 vs 49
Pentax/K10D/_IGP7284.PEF/threads:8/process_time/real_time_mean                                     -0.0167         -0.0158       72.0108       70.8091       73.8282       72.6596
Pentax/K10D/_IGP7284.PEF/threads:8/process_time/real_time_median                                   -0.0165         -0.0165       71.9825       70.7949       71.9808       70.7963
Pentax/K10D/_IGP7284.PEF/threads:8/process_time/real_time_stddev                                   -0.0501         +0.0156        0.1501        0.1426       12.8755       13.0763
Phase One/P65/CF027310.IIQ/threads:8/process_time/real_time_pvalue                                  0.2646          0.2468      U Test, Repetitions: 49 vs 49
Phase One/P65/CF027310.IIQ/threads:8/process_time/real_time_mean                                   +0.0025         +0.0024       79.2134       79.4154      631.2580      632.7601
Phase One/P65/CF027310.IIQ/threads:8/process_time/real_time_median                                 +0.0003         +0.0000       79.3581       79.3834      632.1152      632.1352
Phase One/P65/CF027310.IIQ/threads:8/process_time/real_time_stddev                                 +0.2383         +0.3005        0.8326        1.0310        5.2849        6.8731
Samsung/NX1/2016-07-23-142101_sam_9364.srw/threads:8/process_time/real_time_pvalue                  0.0000          0.0000      U Test, Repetitions: 49 vs 49
Samsung/NX1/2016-07-23-142101_sam_9364.srw/threads:8/process_time/real_time_mean                   +0.0179         +0.0179      328.3829      334.2514      328.3690      334.2385
Samsung/NX1/2016-07-23-142101_sam_9364.srw/threads:8/process_time/real_time_median                 +0.0182         +0.0183      328.3175      334.3054      328.2931      334.2921
Samsung/NX1/2016-07-23-142101_sam_9364.srw/threads:8/process_time/real_time_stddev                 +0.8651         +0.8392        0.3049        0.5687        0.3085        0.5674
Samsung/NX30/2015-03-07-163604_sam_7204.srw/threads:8/process_time/real_time_pvalue                 0.0000          0.0000      U Test, Repetitions: 49 vs 49
Samsung/NX30/2015-03-07-163604_sam_7204.srw/threads:8/process_time/real_time_mean                  -0.0092         -0.0092      129.0806      127.8978      129.0735      127.8921
Samsung/NX30/2015-03-07-163604_sam_7204.srw/threads:8/process_time/real_time_median                -0.0085         -0.0086      129.0611      127.9581      129.0593      127.9545
Samsung/NX30/2015-03-07-163604_sam_7204.srw/threads:8/process_time/real_time_stddev                +0.2651         +0.2716        0.1436        0.1816        0.1439        0.1830
Samsung/NX3000/_3184416.SRW/threads:8/process_time/real_time_pvalue                                 0.0000          0.0000      U Test, Repetitions: 49 vs 49
Samsung/NX3000/_3184416.SRW/threads:8/process_time/real_time_mean                                  -0.3064         -0.3064      226.9913      157.4452      226.9800      157.4384
Samsung/NX3000/_3184416.SRW/threads:8/process_time/real_time_median                                -0.3057         -0.3057      226.8407      157.4926      226.8282      157.4828
Samsung/NX3000/_3184416.SRW/threads:8/process_time/real_time_stddev                                -0.4985         -0.4954        0.3051        0.1530        0.3040        0.1534
Sony/DSLR-A230/DSC08026.ARW/threads:8/process_time/real_time_pvalue                                 0.0000          0.0000      U Test, Repetitions: 49 vs 49
Sony/DSLR-A230/DSC08026.ARW/threads:8/process_time/real_time_mean                                  -0.1598         -0.1598      171.6996      144.2575      171.6915      144.2538
Sony/DSLR-A230/DSC08026.ARW/threads:8/process_time/real_time_median                                -0.1598         -0.1597      171.7109      144.2755      171.7018      144.2766
Sony/DSLR-A230/DSC08026.ARW/threads:8/process_time/real_time_stddev                                +0.4024         +0.3850        0.0847        0.1187        0.0848        0.1175
Sony/ILCE-7S/DSC04126.ARW/threads:8/process_time/real_time_pvalue                                   0.0023          0.0014      U Test, Repetitions: 49 vs 49
Sony/ILCE-7S/DSC04126.ARW/threads:8/process_time/real_time_mean                                    +0.0052         +0.0055        8.1308        8.1728       64.8663       65.2246
Sony/ILCE-7S/DSC04126.ARW/threads:8/process_time/real_time_median                                  +0.0154         +0.0131        8.0814        8.2058       64.5718       65.4151
Sony/ILCE-7S/DSC04126.ARW/threads:8/process_time/real_time_stddev                                  -0.3637         -0.3469        0.1846        0.1175        1.2931        0.8445

5 biggest improvements:

Benchmark                                                                                             Time             CPU      Time Old      Time New       CPU Old       CPU New
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Samsung/NX3000/_3184416.SRW/threads:8/process_time/real_time_pvalue                                 0.0000          0.0000      U Test, Repetitions: 49 vs 49
Samsung/NX3000/_3184416.SRW/threads:8/process_time/real_time_mean                                  -0.3064         -0.3064      226.9913      157.4452      226.9800      157.4384
Samsung/NX3000/_3184416.SRW/threads:8/process_time/real_time_median                                -0.3057         -0.3057      226.8407      157.4926      226.8282      157.4828
Samsung/NX3000/_3184416.SRW/threads:8/process_time/real_time_stddev                                -0.4985         -0.4954        0.3051        0.1530        0.3040        0.1534
Kodak/DCS760C/86L57188.DCR/threads:8/process_time/real_time_pvalue                                  0.0000          0.0000      U Test, Repetitions: 49 vs 49
Kodak/DCS760C/86L57188.DCR/threads:8/process_time/real_time_mean                                   -0.1747         -0.1747       80.4787       66.4227       80.4771       66.4146
Kodak/DCS760C/86L57188.DCR/threads:8/process_time/real_time_median                                 -0.1742         -0.1743       80.4686       66.4542       80.4690       66.4436
Kodak/DCS760C/86L57188.DCR/threads:8/process_time/real_time_stddev                                 +0.6089         +0.5797        0.0670        0.1078        0.0673        0.1062
Sony/DSLR-A230/DSC08026.ARW/threads:8/process_time/real_time_pvalue                                 0.0000          0.0000      U Test, Repetitions: 49 vs 49
Sony/DSLR-A230/DSC08026.ARW/threads:8/process_time/real_time_mean                                  -0.1598         -0.1598      171.6996      144.2575      171.6915      144.2538
Sony/DSLR-A230/DSC08026.ARW/threads:8/process_time/real_time_median                                -0.1598         -0.1597      171.7109      144.2755      171.7018      144.2766
Sony/DSLR-A230/DSC08026.ARW/threads:8/process_time/real_time_stddev                                +0.4024         +0.3850        0.0847        0.1187        0.0848        0.1175
Canon/EOS 77D/IMG_4049.CR2/threads:8/process_time/real_time_pvalue                                  0.0000          0.0000      U Test, Repetitions: 49 vs 49
Canon/EOS 77D/IMG_4049.CR2/threads:8/process_time/real_time_mean                                   -0.0550         -0.0551      280.3046      264.8800      280.3017      264.8559
Canon/EOS 77D/IMG_4049.CR2/threads:8/process_time/real_time_median                                 -0.0554         -0.0554      280.2628      264.7360      280.2574      264.7297
Canon/EOS 77D/IMG_4049.CR2/threads:8/process_time/real_time_stddev                                 +0.7005         +0.7041        0.2779        0.4725        0.2775        0.4729
Canon/EOS 5DS/2K4A9929.CR2/threads:8/process_time/real_time_pvalue                                  0.0000          0.0000      U Test, Repetitions: 49 vs 49
Canon/EOS 5DS/2K4A9929.CR2/threads:8/process_time/real_time_mean                                   -0.0354         -0.0355      316.7396      305.5208      316.7342      305.4890
Canon/EOS 5DS/2K4A9929.CR2/threads:8/process_time/real_time_median                                 -0.0354         -0.0356      316.6969      305.4798      316.6917      305.4324
Canon/EOS 5DS/2K4A9929.CR2/threads:8/process_time/real_time_stddev                                 +0.0493         +0.0330        0.3562        0.3737        0.3563        0.3681

1 biggest regression:

Benchmark                                                                                             Time             CPU      Time Old      Time New       CPU Old       CPU New
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Panasonic/DC-GH5S/P1022085.RW2/threads:8/process_time/real_time_pvalue                              0.0000          0.0000      U Test, Repetitions: 49 vs 49
Panasonic/DC-GH5S/P1022085.RW2/threads:8/process_time/real_time_mean                               +0.0533         +0.0531        5.0627        5.3324       40.3521       42.4956
Panasonic/DC-GH5S/P1022085.RW2/threads:8/process_time/real_time_median                             +0.0560         +0.0551        5.0707        5.3547       40.4043       42.6317
Panasonic/DC-GH5S/P1022085.RW2/threads:8/process_time/real_time_stddev                             +0.0148         +0.0363        0.0547        0.0555        0.3523        0.3651

... and that regression is noise, i re-benchmarked it.

[lebedev.ri]

@efriedma ping

[jmolloy]

I can think of a rationale for the current behaviour. A lopsided if-triangle could indicate it might be better to emit a branch than speculate. Especially as this transform is context-free, input code that contains the same pattern many times can cause an explosion in code size and the transform was likely designed to be conservative.

Also note that there exist targets that don't use conditional moves to perform predication (most VLIW targets have a dedicated predicate register file) so that changes the behaviour somewhat.

I don't think there's a right answer for SimplifyCFG. Whatever we do is wrong, but sometimes it is useful. I think your approach here has been great; you have a bunch of performance data showing improvements and no regressions. I also like your renaming from "Cost" to "Budget". That's annoyed me for a while.

LGTM.

[lebedev.ri]

In D67318#1670962, @jmolloy wrote:

I can think of a rationale for the current behaviour. A lopsided if-triangle could indicate it might be better to emit a branch than speculate. Especially as this transform is context-free, input code that contains the same pattern many times can cause an explosion in code size and the transform was likely designed to be conservative.

I don't think there's a right answer for SimplifyCFG. Whatever we do is wrong, but sometimes it is useful. I think your approach here has been great; you have a bunch of performance data showing improvements

Right.

and no regressions.

To be noted, on the benchmarks run.
I will be very surprised if this does not cause any regressions at all.

I also like your renaming from "Cost" to "Budget". That's annoyed me for a while.

Yeah, that one looked really weird to me too.

Also note that there exist targets that don't use conditional moves to perform predication (most VLIW targets have a dedicated predicate register file) so that changes the behaviour somewhat.

LGTM.

@jmolloy thank you for the review.
@efriedma / others - any comments? Not sure if i should wait a bit more or proceed to commit here.

[jmolloy]

I will be very surprised if this does not cause any regressions at all.

There is no avoiding that, the best we can do is best-effort here.

[xbolva00]

Just commit it, there is LNT so we should just watch perf bots after your commit if new changes are acceptable.

[xbolva00]

Seems pretty ok: http://lnt.llvm.org/db_default/v4/nts/129108

except "MultiSource/Benchmarks/FreeBench/fourinarow/fourinarow" really big perf/code size regression. Roman, can you look at it?

[lebedev.ri]

In D67318#1671524, @xbolva00 wrote:

Seems pretty ok: http://lnt.llvm.org/db_default/v4/nts/129108

except "MultiSource/Benchmarks/FreeBench/fourinarow/fourinarow" really big perf/code size regression. Roman, can you look at it?

Hmm yeah, not surprised at all that it regressed.

fourinarow.c16 KBDownload

old.processed.ll307 KBDownload

new.processed.ll261 KBDownload

The patch did what it was supposed to do, and got rid of all the branching in @value.
And in that case it's bad because we end up with a wall (~1500 lines) of basically

%tmp519 = and i64 %tmp62, %tmp233
%tmp520 = icmp eq i64 %tmp519, %tmp62
%tmp521 = sitofp i32 %tmp518 to float
%tmp522 = fadd float %tmp236, %tmp521
%tmp523 = fptosi float %tmp522 to i32
%tmp524 = select i1 %tmp520, i32 %tmp523, i32 %tmp518

That test is really perfect storm for this. And i really don't like those int-float-int translations;
if i get rid of them (obviously not the fix), the regression goes away - even though in IR the flattening
still happens, in the asm we again get branches. So i suppose this may be a bug in undo transform in backend.

[xbolva00]

Just curious, did you try threshold 5 or 6 for your rawspeed benchmark?

[lebedev.ri]

In D67318#1671803, @xbolva00 wrote:

Just curious, did you try threshold 5 or 6 for your rawspeed benchmark?

No, i have not tried any other thresholds here.
I'm personally not aware of any patterns that would benefit from those thresholds, although i did not look.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

 // a select, so the "clamp" idiom (of a min followed by a max) will be caught.
 // To catch this, we need to fold a compare and a select, hence '2' being the
 // minimum reasonable default.
 static cl::opt<unsigned> PHINodeFoldingThreshold(
     "phi-node-folding-threshold", cl::Hidden, cl::init(2),
     cl::desc(
         "Control the amount of phi node folding to perform (default = 2)"));
 
+static cl::opt<unsigned> TwoEntryPHINodeFoldingThreshold(
+    "two-entry-phi-node-folding-threshold", cl::Hidden, cl::init(4),
+    cl::desc("Control the maximal total instruction cost that we are willing "
+             "to speculatively execute to fold a 2-entry PHI node into a "
+             "select (default = 4)"));
+
 static cl::opt<bool> DupRet(
     "simplifycfg-dup-ret", cl::Hidden, cl::init(false),
     cl::desc("Duplicate return instructions into unconditional branches"));
 
 static cl::opt<bool>
     SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true),
                cl::desc("Sink common instructions down to the end block"));
 

 /// The cost for most non-trapping instructions is defined as 1 except for
 /// Select whose cost is 2.
 ///
 /// After this function returns, CostRemaining is decreased by the cost of
 /// V plus its non-dominating operands.  If that cost is greater than
 /// CostRemaining, false is returned and CostRemaining is undefined.
 static bool DominatesMergePoint(Value *V, BasicBlock *BB,
                                 SmallPtrSetImpl<Instruction *> &AggressiveInsts,
-                                unsigned &CostRemaining,
+                                int &BudgetRemaining,
                                 const TargetTransformInfo &TTI,
                                 unsigned Depth = 0) {
   // It is possible to hit a zero-cost cycle (phi/gep instructions for example),
   // so limit the recursion depth.
   // TODO: While this recursion limit does prevent pathological behavior, it
   // would be better to track visited instructions to avoid cycles.
   if (Depth == MaxSpeculationDepth)
     return false;
if (AggressiveInsts.count(I))
     return true;
 
   // Okay, it looks like the instruction IS in the "condition".  Check to
   // see if it's a cheap instruction to unconditionally compute, and if it
   // only uses stuff defined outside of the condition.  If so, hoist it out.
   if (!isSafeToSpeculativelyExecute(I))
     return false;
 
-  unsigned Cost = ComputeSpeculationCost(I, TTI);
+  BudgetRemaining -= ComputeSpeculationCost(I, TTI);
 
   // Allow exactly one instruction to be speculated regardless of its cost
   // (as long as it is safe to do so).
   // This is intended to flatten the CFG even if the instruction is a division
   // or other expensive operation. The speculation of an expensive instruction
   // is expected to be undone in CodeGenPrepare if the speculation has not
   // enabled further IR optimizations.
-  if (Cost > CostRemaining &&
+  if (BudgetRemaining < 0 &&
       (!SpeculateOneExpensiveInst || !AggressiveInsts.empty() || Depth > 0))
     return false;
 
-  // Avoid unsigned wrap.
-  CostRemaining = (Cost > CostRemaining) ? 0 : CostRemaining - Cost;
-
   // Okay, we can only really hoist these out if their operands do
   // not take us over the cost threshold.
   for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i)
-    if (!DominatesMergePoint(*i, BB, AggressiveInsts, CostRemaining, TTI,
+    if (!DominatesMergePoint(*i, BB, AggressiveInsts, BudgetRemaining, TTI,
                              Depth + 1))
       return false;
   // Okay, it's safe to do this!  Remember this instruction.
   AggressiveInsts.insert(I);
   return true;
 }
 
 /// Extract ConstantInt from value, looking through IntToPtr
static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI,
   for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++NumPhis, ++I)
     if (NumPhis > 2)
       return false;
 
   // Loop over the PHI's seeing if we can promote them all to select
   // instructions.  While we are at it, keep track of the instructions
   // that need to be moved to the dominating block.
   SmallPtrSet<Instruction *, 4> AggressiveInsts;
-  unsigned MaxCostVal0 = PHINodeFoldingThreshold,
-           MaxCostVal1 = PHINodeFoldingThreshold;
-  MaxCostVal0 *= TargetTransformInfo::TCC_Basic;
-  MaxCostVal1 *= TargetTransformInfo::TCC_Basic;
+  int BudgetRemaining =
+      TwoEntryPHINodeFoldingThreshold * TargetTransformInfo::TCC_Basic;
 
   for (BasicBlock::iterator II = BB->begin(); isa<PHINode>(II);) {
     PHINode *PN = cast<PHINode>(II++);
     if (Value *V = SimplifyInstruction(PN, {DL, PN})) {
       PN->replaceAllUsesWith(V);
       PN->eraseFromParent();
       continue;
     }
 
     if (!DominatesMergePoint(PN->getIncomingValue(0), BB, AggressiveInsts,
-                             MaxCostVal0, TTI) ||
+                             BudgetRemaining, TTI) ||
         !DominatesMergePoint(PN->getIncomingValue(1), BB, AggressiveInsts,
-                             MaxCostVal1, TTI))
+                             BudgetRemaining, TTI))
       return false;
   }
 
   // If we folded the first phi, PN dangles at this point.  Refresh it.  If
   // we ran out of PHIs then we simplified them all.
   PN = dyn_cast<PHINode>(BB->begin());
   if (!PN)
     return true;

llvm/test/Transforms/SimplifyCFG/PhiEliminate3.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -S -phi-node-folding-threshold=1 | FileCheck %s --check-prefix=ALL --check-prefix=CHECK-ONE
 ; RUN: opt < %s -simplifycfg -S -phi-node-folding-threshold=2 | FileCheck %s --check-prefix=ALL --check-prefix=CHECK-TWO
 ; RUN: opt < %s -simplifycfg -S -phi-node-folding-threshold=7 | FileCheck %s --check-prefix=ALL --check-prefix=CHECK-SEVEN
 
 ; Test merging of blocks containing complex expressions,
 ; with various folding thresholds
 
 define i32 @test(i1 %a, i1 %b, i32 %i, i32 %j, i32 %k) {
-; CHECK-ONE-LABEL: @test(
-; CHECK-ONE-NEXT:  entry:
-; CHECK-ONE-NEXT:    br i1 [[A:%.*]], label [[M:%.*]], label [[O:%.*]]
-; CHECK-ONE:       O:
-; CHECK-ONE-NEXT:    br i1 [[B:%.*]], label [[P:%.*]], label [[Q:%.*]]
-; CHECK-ONE:       P:
-; CHECK-ONE-NEXT:    [[IAJ:%.*]] = add i32 [[I:%.*]], [[J:%.*]]
-; CHECK-ONE-NEXT:    [[IAJAK:%.*]] = add i32 [[IAJ]], [[K:%.*]]
-; CHECK-ONE-NEXT:    br label [[N:%.*]]
-; CHECK-ONE:       Q:
-; CHECK-ONE-NEXT:    [[IXJ:%.*]] = xor i32 [[I]], [[J]]
-; CHECK-ONE-NEXT:    [[IXJXK:%.*]] = xor i32 [[IXJ]], [[K]]
-; CHECK-ONE-NEXT:    br label [[N]]
-; CHECK-ONE:       N:
-; CHECK-ONE-NEXT:    [[WP:%.*]] = phi i32 [ [[IAJAK]], [[P]] ], [ [[IXJXK]], [[Q]] ]
-; CHECK-ONE-NEXT:    [[WP2:%.*]] = add i32 [[WP]], [[WP]]
-; CHECK-ONE-NEXT:    br label [[M]]
-; CHECK-ONE:       M:
-; CHECK-ONE-NEXT:    [[W:%.*]] = phi i32 [ [[WP2]], [[N]] ], [ 2, [[ENTRY:%.*]] ]
-; CHECK-ONE-NEXT:    [[R:%.*]] = add i32 [[W]], 1
-; CHECK-ONE-NEXT:    ret i32 [[R]]
-;
-; CHECK-TWO-LABEL: @test(
-; CHECK-TWO-NEXT:  entry:
-; CHECK-TWO-NEXT:    br i1 [[A:%.*]], label [[M:%.*]], label [[O:%.*]]
-; CHECK-TWO:       O:
-; CHECK-TWO-NEXT:    [[IAJ:%.*]] = add i32 [[I:%.*]], [[J:%.*]]
-; CHECK-TWO-NEXT:    [[IAJAK:%.*]] = add i32 [[IAJ]], [[K:%.*]]
-; CHECK-TWO-NEXT:    [[IXJ:%.*]] = xor i32 [[I]], [[J]]
-; CHECK-TWO-NEXT:    [[IXJXK:%.*]] = xor i32 [[IXJ]], [[K]]
-; CHECK-TWO-NEXT:    [[WP:%.*]] = select i1 [[B:%.*]], i32 [[IAJAK]], i32 [[IXJXK]]
-; CHECK-TWO-NEXT:    [[WP2:%.*]] = add i32 [[WP]], [[WP]]
-; CHECK-TWO-NEXT:    br label [[M]]
-; CHECK-TWO:       M:
-; CHECK-TWO-NEXT:    [[W:%.*]] = phi i32 [ [[WP2]], [[O]] ], [ 2, [[ENTRY:%.*]] ]
-; CHECK-TWO-NEXT:    [[R:%.*]] = add i32 [[W]], 1
-; CHECK-TWO-NEXT:    ret i32 [[R]]
-;
-; CHECK-SEVEN-LABEL: @test(
-; CHECK-SEVEN-NEXT:  entry:
-; CHECK-SEVEN-NEXT:    [[IAJ:%.*]] = add i32 [[I:%.*]], [[J:%.*]]
-; CHECK-SEVEN-NEXT:    [[IAJAK:%.*]] = add i32 [[IAJ]], [[K:%.*]]
-; CHECK-SEVEN-NEXT:    [[IXJ:%.*]] = xor i32 [[I]], [[J]]
-; CHECK-SEVEN-NEXT:    [[IXJXK:%.*]] = xor i32 [[IXJ]], [[K]]
-; CHECK-SEVEN-NEXT:    [[WP:%.*]] = select i1 [[B:%.*]], i32 [[IAJAK]], i32 [[IXJXK]]
-; CHECK-SEVEN-NEXT:    [[WP2:%.*]] = add i32 [[WP]], [[WP]]
-; CHECK-SEVEN-NEXT:    [[W:%.*]] = select i1 [[A:%.*]], i32 2, i32 [[WP2]]
-; CHECK-SEVEN-NEXT:    [[R:%.*]] = add i32 [[W]], 1
-; CHECK-SEVEN-NEXT:    ret i32 [[R]]
+; ALL-LABEL: @test(
+; ALL-NEXT:  entry:
+; ALL-NEXT:    br i1 [[A:%.*]], label [[M:%.*]], label [[O:%.*]]
+; ALL:       O:
+; ALL-NEXT:    [[IAJ:%.*]] = add i32 [[I:%.*]], [[J:%.*]]
+; ALL-NEXT:    [[IAJAK:%.*]] = add i32 [[IAJ]], [[K:%.*]]
+; ALL-NEXT:    [[IXJ:%.*]] = xor i32 [[I]], [[J]]
+; ALL-NEXT:    [[IXJXK:%.*]] = xor i32 [[IXJ]], [[K]]
+; ALL-NEXT:    [[WP:%.*]] = select i1 [[B:%.*]], i32 [[IAJAK]], i32 [[IXJXK]]
+; ALL-NEXT:    [[WP2:%.*]] = add i32 [[WP]], [[WP]]
+; ALL-NEXT:    br label [[M]]
+; ALL:       M:
+; ALL-NEXT:    [[W:%.*]] = phi i32 [ [[WP2]], [[O]] ], [ 2, [[ENTRY:%.*]] ]
+; ALL-NEXT:    [[R:%.*]] = add i32 [[W]], 1
+; ALL-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %a, label %M, label %O
 O:
   br i1 %b, label %P, label %Q
 P:
   %iaj = add i32 %i, %j
   %iajak = add i32 %iaj, %k

llvm/test/Transforms/SimplifyCFG/SpeculativeExec.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -phi-node-folding-threshold=2 -S | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define i32 @test1(i32 %a, i32 %b, i32 %c) nounwind  {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[B:%.*]], 0
-; CHECK-NEXT:    br i1 [[TMP1]], label [[BB1:%.*]], label [[BB3:%.*]]
-; CHECK:       bb1:
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i32 [[C:%.*]], 1
 ; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[A:%.*]], 1
 ; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[TMP2]], i32 [[TMP3]], i32 [[A]]
-; CHECK-NEXT:    br label [[BB3]]
-; CHECK:       bb3:
-; CHECK-NEXT:    [[TMP4:%.*]] = phi i32 [ [[B]], [[ENTRY:%.*]] ], [ [[SPEC_SELECT]], [[BB1]] ]
+; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP1]], i32 [[SPEC_SELECT]], i32 [[B]]
 ; CHECK-NEXT:    [[TMP5:%.*]] = sub i32 [[TMP4]], 1
 ; CHECK-NEXT:    ret i32 [[TMP5]]
 ;
 entry:
   %tmp1 = icmp eq i32 %b, 0
   br i1 %tmp1, label %bb1, label %bb3
 
 bb1:            ; preds = %entry

llvm/test/Transforms/SimplifyCFG/X86/speculate-cttz-ctlz.ll

cond.end:                                         ; preds = %entry, %cond.true
   ret i16 %cond
 }
 
 ; The following tests verify that calls to cttz/ctlz are speculated even if
 ; basic block %cond.true has an extra zero extend/truncate which is "free"
 ; for the target.
 
 define i64 @test1e(i32 %x) {
-; BMI-LABEL: @test1e(
-; BMI-NEXT:  entry:
-; BMI-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[X:%.*]], 0
-; BMI-NEXT:    [[TMP0:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[X]], i1 true)
-; BMI-NEXT:    [[PHITMP2:%.*]] = zext i32 [[TMP0]] to i64
-; BMI-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i64 32, i64 [[PHITMP2]]
-; BMI-NEXT:    ret i64 [[COND]]
-;
-; LZCNT-LABEL: @test1e(
-; LZCNT-NEXT:  entry:
-; LZCNT-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[X:%.*]], 0
-; LZCNT-NEXT:    br i1 [[TOBOOL]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
-; LZCNT:       cond.true:
-; LZCNT-NEXT:    [[TMP0:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[X]], i1 true)
-; LZCNT-NEXT:    [[PHITMP2:%.*]] = zext i32 [[TMP0]] to i64
-; LZCNT-NEXT:    br label [[COND_END]]
-; LZCNT:       cond.end:
-; LZCNT-NEXT:    [[COND:%.*]] = phi i64 [ [[PHITMP2]], [[COND_TRUE]] ], [ 32, [[ENTRY:%.*]] ]
-; LZCNT-NEXT:    ret i64 [[COND]]
-;
-; GENERIC-LABEL: @test1e(
-; GENERIC-NEXT:  entry:
-; GENERIC-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[X:%.*]], 0
-; GENERIC-NEXT:    br i1 [[TOBOOL]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
-; GENERIC:       cond.true:
-; GENERIC-NEXT:    [[TMP0:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[X]], i1 true)
-; GENERIC-NEXT:    [[PHITMP2:%.*]] = zext i32 [[TMP0]] to i64
-; GENERIC-NEXT:    br label [[COND_END]]
-; GENERIC:       cond.end:
-; GENERIC-NEXT:    [[COND:%.*]] = phi i64 [ [[PHITMP2]], [[COND_TRUE]] ], [ 32, [[ENTRY:%.*]] ]
-; GENERIC-NEXT:    ret i64 [[COND]]
+; ALL-LABEL: @test1e(
+; ALL-NEXT:  entry:
+; ALL-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[X:%.*]], 0
+; ALL-NEXT:    [[TMP0:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[X]], i1 true)
+; ALL-NEXT:    [[PHITMP2:%.*]] = zext i32 [[TMP0]] to i64
+; ALL-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i64 32, i64 [[PHITMP2]]
+; ALL-NEXT:    ret i64 [[COND]]
 ;
 entry:
   %tobool = icmp eq i32 %x, 0
   br i1 %tobool, label %cond.end, label %cond.true
 
 cond.true:                                        ; preds = %entry
   %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
   %phitmp2 = zext i32 %0 to i64
   br label %cond.end
 
 cond.end:                                         ; preds = %entry, %cond.true
   %cond = phi i64 [ %phitmp2, %cond.true ], [ 32, %entry ]
   ret i64 %cond
 }
 
 define i32 @test2e(i64 %x) {
-; BMI-LABEL: @test2e(
-; BMI-NEXT:  entry:
-; BMI-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[X:%.*]], 0
-; BMI-NEXT:    [[TMP0:%.*]] = tail call i64 @llvm.cttz.i64(i64 [[X]], i1 true)
-; BMI-NEXT:    [[CAST:%.*]] = trunc i64 [[TMP0]] to i32
-; BMI-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i32 64, i32 [[CAST]]
-; BMI-NEXT:    ret i32 [[COND]]
-;
-; LZCNT-LABEL: @test2e(
-; LZCNT-NEXT:  entry:
-; LZCNT-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[X:%.*]], 0
-; LZCNT-NEXT:    br i1 [[TOBOOL]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
-; LZCNT:       cond.true:
-; LZCNT-NEXT:    [[TMP0:%.*]] = tail call i64 @llvm.cttz.i64(i64 [[X]], i1 true)
-; LZCNT-NEXT:    [[CAST:%.*]] = trunc i64 [[TMP0]] to i32
-; LZCNT-NEXT:    br label [[COND_END]]
-; LZCNT:       cond.end:
-; LZCNT-NEXT:    [[COND:%.*]] = phi i32 [ [[CAST]], [[COND_TRUE]] ], [ 64, [[ENTRY:%.*]] ]
-; LZCNT-NEXT:    ret i32 [[COND]]
-;
-; GENERIC-LABEL: @test2e(
-; GENERIC-NEXT:  entry:
-; GENERIC-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[X:%.*]], 0
-; GENERIC-NEXT:    br i1 [[TOBOOL]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
-; GENERIC:       cond.true:
-; GENERIC-NEXT:    [[TMP0:%.*]] = tail call i64 @llvm.cttz.i64(i64 [[X]], i1 true)
-; GENERIC-NEXT:    [[CAST:%.*]] = trunc i64 [[TMP0]] to i32
-; GENERIC-NEXT:    br label [[COND_END]]
-; GENERIC:       cond.end:
-; GENERIC-NEXT:    [[COND:%.*]] = phi i32 [ [[CAST]], [[COND_TRUE]] ], [ 64, [[ENTRY:%.*]] ]
-; GENERIC-NEXT:    ret i32 [[COND]]
+; ALL-LABEL: @test2e(
+; ALL-NEXT:  entry:
+; ALL-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[X:%.*]], 0
+; ALL-NEXT:    [[TMP0:%.*]] = tail call i64 @llvm.cttz.i64(i64 [[X]], i1 true)
+; ALL-NEXT:    [[CAST:%.*]] = trunc i64 [[TMP0]] to i32
+; ALL-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i32 64, i32 [[CAST]]
+; ALL-NEXT:    ret i32 [[COND]]
 ;
 entry:
   %tobool = icmp eq i64 %x, 0
   br i1 %tobool, label %cond.end, label %cond.true
 
 cond.true:                                        ; preds = %entry
   %0 = tail call i64 @llvm.cttz.i64(i64 %x, i1 true)
   %cast = trunc i64 %0 to i32
   br label %cond.end
 
 cond.end:                                         ; preds = %entry, %cond.true
   %cond = phi i32 [ %cast, %cond.true ], [ 64, %entry ]
   ret i32 %cond
 }
 
 define i64 @test3e(i32 %x) {
-; BMI-LABEL: @test3e(
-; BMI-NEXT:  entry:
-; BMI-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[X:%.*]], 0
-; BMI-NEXT:    br i1 [[TOBOOL]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
-; BMI:       cond.true:
-; BMI-NEXT:    [[TMP0:%.*]] = tail call i32 @llvm.ctlz.i32(i32 [[X]], i1 true)
-; BMI-NEXT:    [[PHITMP2:%.*]] = zext i32 [[TMP0]] to i64
-; BMI-NEXT:    br label [[COND_END]]
-; BMI:       cond.end:
-; BMI-NEXT:    [[COND:%.*]] = phi i64 [ [[PHITMP2]], [[COND_TRUE]] ], [ 32, [[ENTRY:%.*]] ]
-; BMI-NEXT:    ret i64 [[COND]]
-;
-; LZCNT-LABEL: @test3e(
-; LZCNT-NEXT:  entry:
-; LZCNT-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[X:%.*]], 0
-; LZCNT-NEXT:    [[TMP0:%.*]] = tail call i32 @llvm.ctlz.i32(i32 [[X]], i1 true)
-; LZCNT-NEXT:    [[PHITMP2:%.*]] = zext i32 [[TMP0]] to i64
-; LZCNT-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i64 32, i64 [[PHITMP2]]
-; LZCNT-NEXT:    ret i64 [[COND]]
-;
-; GENERIC-LABEL: @test3e(
-; GENERIC-NEXT:  entry:
-; GENERIC-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[X:%.*]], 0
-; GENERIC-NEXT:    br i1 [[TOBOOL]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
-; GENERIC:       cond.true:
-; GENERIC-NEXT:    [[TMP0:%.*]] = tail call i32 @llvm.ctlz.i32(i32 [[X]], i1 true)
-; GENERIC-NEXT:    [[PHITMP2:%.*]] = zext i32 [[TMP0]] to i64
-; GENERIC-NEXT:    br label [[COND_END]]
-; GENERIC:       cond.end:
-; GENERIC-NEXT:    [[COND:%.*]] = phi i64 [ [[PHITMP2]], [[COND_TRUE]] ], [ 32, [[ENTRY:%.*]] ]
-; GENERIC-NEXT:    ret i64 [[COND]]
+; ALL-LABEL: @test3e(
+; ALL-NEXT:  entry:
+; ALL-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[X:%.*]], 0
+; ALL-NEXT:    [[TMP0:%.*]] = tail call i32 @llvm.ctlz.i32(i32 [[X]], i1 true)
+; ALL-NEXT:    [[PHITMP2:%.*]] = zext i32 [[TMP0]] to i64
+; ALL-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i64 32, i64 [[PHITMP2]]
+; ALL-NEXT:    ret i64 [[COND]]
 ;
 entry:
   %tobool = icmp eq i32 %x, 0
   br i1 %tobool, label %cond.end, label %cond.true
 
 cond.true:                                        ; preds = %entry
   %0 = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)
   %phitmp2 = zext i32 %0 to i64
   br label %cond.end
 
 cond.end:                                         ; preds = %entry, %cond.true
   %cond = phi i64 [ %phitmp2, %cond.true ], [ 32, %entry ]
   ret i64 %cond
 }
 
 define i32 @test4e(i64 %x) {
-; BMI-LABEL: @test4e(
-; BMI-NEXT:  entry:
-; BMI-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[X:%.*]], 0
-; BMI-NEXT:    br i1 [[TOBOOL]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
-; BMI:       cond.true:
-; BMI-NEXT:    [[TMP0:%.*]] = tail call i64 @llvm.ctlz.i64(i64 [[X]], i1 true)
-; BMI-NEXT:    [[CAST:%.*]] = trunc i64 [[TMP0]] to i32
-; BMI-NEXT:    br label [[COND_END]]
-; BMI:       cond.end:
-; BMI-NEXT:    [[COND:%.*]] = phi i32 [ [[CAST]], [[COND_TRUE]] ], [ 64, [[ENTRY:%.*]] ]
-; BMI-NEXT:    ret i32 [[COND]]
-;
-; LZCNT-LABEL: @test4e(
-; LZCNT-NEXT:  entry:
-; LZCNT-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[X:%.*]], 0
-; LZCNT-NEXT:    [[TMP0:%.*]] = tail call i64 @llvm.ctlz.i64(i64 [[X]], i1 true)
-; LZCNT-NEXT:    [[CAST:%.*]] = trunc i64 [[TMP0]] to i32
-; LZCNT-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i32 64, i32 [[CAST]]
-; LZCNT-NEXT:    ret i32 [[COND]]
-;
-; GENERIC-LABEL: @test4e(
-; GENERIC-NEXT:  entry:
-; GENERIC-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[X:%.*]], 0
-; GENERIC-NEXT:    br i1 [[TOBOOL]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
-; GENERIC:       cond.true:
-; GENERIC-NEXT:    [[TMP0:%.*]] = tail call i64 @llvm.ctlz.i64(i64 [[X]], i1 true)
-; GENERIC-NEXT:    [[CAST:%.*]] = trunc i64 [[TMP0]] to i32
-; GENERIC-NEXT:    br label [[COND_END]]
-; GENERIC:       cond.end:
-; GENERIC-NEXT:    [[COND:%.*]] = phi i32 [ [[CAST]], [[COND_TRUE]] ], [ 64, [[ENTRY:%.*]] ]
-; GENERIC-NEXT:    ret i32 [[COND]]
+; ALL-LABEL: @test4e(
+; ALL-NEXT:  entry:
+; ALL-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[X:%.*]], 0
+; ALL-NEXT:    [[TMP0:%.*]] = tail call i64 @llvm.ctlz.i64(i64 [[X]], i1 true)
+; ALL-NEXT:    [[CAST:%.*]] = trunc i64 [[TMP0]] to i32
+; ALL-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i32 64, i32 [[CAST]]
+; ALL-NEXT:    ret i32 [[COND]]
 ;
 entry:
   %tobool = icmp eq i64 %x, 0
   br i1 %tobool, label %cond.end, label %cond.true
 
 cond.true:                                        ; preds = %entry
   %0 = tail call i64 @llvm.ctlz.i64(i64 %x, i1 true)
   %cast = trunc i64 %0 to i32
   br label %cond.end
 
 cond.end:                                         ; preds = %entry, %cond.true
   %cond = phi i32 [ %cast, %cond.true ], [ 64, %entry ]
   ret i32 %cond
 }
 
 define i16 @test5e(i64 %x) {
-; BMI-LABEL: @test5e(
-; BMI-NEXT:  entry:
-; BMI-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[X:%.*]], 0
-; BMI-NEXT:    br i1 [[TOBOOL]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
-; BMI:       cond.true:
-; BMI-NEXT:    [[TMP0:%.*]] = tail call i64 @llvm.ctlz.i64(i64 [[X]], i1 true)
-; BMI-NEXT:    [[CAST:%.*]] = trunc i64 [[TMP0]] to i16
-; BMI-NEXT:    br label [[COND_END]]
-; BMI:       cond.end:
-; BMI-NEXT:    [[COND:%.*]] = phi i16 [ [[CAST]], [[COND_TRUE]] ], [ 64, [[ENTRY:%.*]] ]
-; BMI-NEXT:    ret i16 [[COND]]
-;
-; LZCNT-LABEL: @test5e(
-; LZCNT-NEXT:  entry:
-; LZCNT-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[X:%.*]], 0
-; LZCNT-NEXT:    [[TMP0:%.*]] = tail call i64 @llvm.ctlz.i64(i64 [[X]], i1 true)
-; LZCNT-NEXT:    [[CAST:%.*]] = trunc i64 [[TMP0]] to i16
-; LZCNT-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i16 64, i16 [[CAST]]
-; LZCNT-NEXT:    ret i16 [[COND]]
-;
-; GENERIC-LABEL: @test5e(
-; GENERIC-NEXT:  entry:
-; GENERIC-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[X:%.*]], 0
-; GENERIC-NEXT:    br i1 [[TOBOOL]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
-; GENERIC:       cond.true:
-; GENERIC-NEXT:    [[TMP0:%.*]] = tail call i64 @llvm.ctlz.i64(i64 [[X]], i1 true)
-; GENERIC-NEXT:    [[CAST:%.*]] = trunc i64 [[TMP0]] to i16
-; GENERIC-NEXT:    br label [[COND_END]]
-; GENERIC:       cond.end:
-; GENERIC-NEXT:    [[COND:%.*]] = phi i16 [ [[CAST]], [[COND_TRUE]] ], [ 64, [[ENTRY:%.*]] ]
-; GENERIC-NEXT:    ret i16 [[COND]]
+; ALL-LABEL: @test5e(
+; ALL-NEXT:  entry:
+; ALL-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[X:%.*]], 0
+; ALL-NEXT:    [[TMP0:%.*]] = tail call i64 @llvm.ctlz.i64(i64 [[X]], i1 true)
+; ALL-NEXT:    [[CAST:%.*]] = trunc i64 [[TMP0]] to i16
+; ALL-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i16 64, i16 [[CAST]]
+; ALL-NEXT:    ret i16 [[COND]]
 ;
 entry:
   %tobool = icmp eq i64 %x, 0
   br i1 %tobool, label %cond.end, label %cond.true
 
 cond.true:                                        ; preds = %entry
   %0 = tail call i64 @llvm.ctlz.i64(i64 %x, i1 true)
   %cast = trunc i64 %0 to i16
   br label %cond.end
 
 cond.end:                                         ; preds = %entry, %cond.true
   %cond = phi i16 [ %cast, %cond.true ], [ 64, %entry ]
   ret i16 %cond
 }
 
 define i16 @test6e(i32 %x) {
-; BMI-LABEL: @test6e(
-; BMI-NEXT:  entry:
-; BMI-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[X:%.*]], 0
-; BMI-NEXT:    br i1 [[TOBOOL]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
-; BMI:       cond.true:
-; BMI-NEXT:    [[TMP0:%.*]] = tail call i32 @llvm.ctlz.i32(i32 [[X]], i1 true)
-; BMI-NEXT:    [[CAST:%.*]] = trunc i32 [[TMP0]] to i16
-; BMI-NEXT:    br label [[COND_END]]
-; BMI:       cond.end:
-; BMI-NEXT:    [[COND:%.*]] = phi i16 [ [[CAST]], [[COND_TRUE]] ], [ 32, [[ENTRY:%.*]] ]
-; BMI-NEXT:    ret i16 [[COND]]
-;
-; LZCNT-LABEL: @test6e(
-; LZCNT-NEXT:  entry:
-; LZCNT-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[X:%.*]], 0
-; LZCNT-NEXT:    [[TMP0:%.*]] = tail call i32 @llvm.ctlz.i32(i32 [[X]], i1 true)
-; LZCNT-NEXT:    [[CAST:%.*]] = trunc i32 [[TMP0]] to i16
-; LZCNT-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i16 32, i16 [[CAST]]
-; LZCNT-NEXT:    ret i16 [[COND]]
-;
-; GENERIC-LABEL: @test6e(
-; GENERIC-NEXT:  entry:
-; GENERIC-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[X:%.*]], 0
-; GENERIC-NEXT:    br i1 [[TOBOOL]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
-; GENERIC:       cond.true:
-; GENERIC-NEXT:    [[TMP0:%.*]] = tail call i32 @llvm.ctlz.i32(i32 [[X]], i1 true)
-; GENERIC-NEXT:    [[CAST:%.*]] = trunc i32 [[TMP0]] to i16
-; GENERIC-NEXT:    br label [[COND_END]]
-; GENERIC:       cond.end:
-; GENERIC-NEXT:    [[COND:%.*]] = phi i16 [ [[CAST]], [[COND_TRUE]] ], [ 32, [[ENTRY:%.*]] ]
-; GENERIC-NEXT:    ret i16 [[COND]]
+; ALL-LABEL: @test6e(
+; ALL-NEXT:  entry:
+; ALL-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[X:%.*]], 0
+; ALL-NEXT:    [[TMP0:%.*]] = tail call i32 @llvm.ctlz.i32(i32 [[X]], i1 true)
+; ALL-NEXT:    [[CAST:%.*]] = trunc i32 [[TMP0]] to i16
+; ALL-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i16 32, i16 [[CAST]]
+; ALL-NEXT:    ret i16 [[COND]]
 ;
 entry:
   %tobool = icmp eq i32 %x, 0
   br i1 %tobool, label %cond.end, label %cond.true
 
 cond.true:                                        ; preds = %entry
   %0 = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)
   %cast = trunc i32 %0 to i16
   br label %cond.end
 
 cond.end:                                         ; preds = %entry, %cond.true
   %cond = phi i16 [ %cast, %cond.true ], [ 32, %entry ]
   ret i16 %cond
 }
 
 define i16 @test7e(i64 %x) {
-; BMI-LABEL: @test7e(
-; BMI-NEXT:  entry:
-; BMI-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[X:%.*]], 0
-; BMI-NEXT:    [[TMP0:%.*]] = tail call i64 @llvm.cttz.i64(i64 [[X]], i1 true)
-; BMI-NEXT:    [[CAST:%.*]] = trunc i64 [[TMP0]] to i16
-; BMI-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i16 64, i16 [[CAST]]
-; BMI-NEXT:    ret i16 [[COND]]
-;
-; LZCNT-LABEL: @test7e(
-; LZCNT-NEXT:  entry:
-; LZCNT-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[X:%.*]], 0
-; LZCNT-NEXT:    br i1 [[TOBOOL]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
-; LZCNT:       cond.true:
-; LZCNT-NEXT:    [[TMP0:%.*]] = tail call i64 @llvm.cttz.i64(i64 [[X]], i1 true)
-; LZCNT-NEXT:    [[CAST:%.*]] = trunc i64 [[TMP0]] to i16
-; LZCNT-NEXT:    br label [[COND_END]]
-; LZCNT:       cond.end:
-; LZCNT-NEXT:    [[COND:%.*]] = phi i16 [ [[CAST]], [[COND_TRUE]] ], [ 64, [[ENTRY:%.*]] ]
-; LZCNT-NEXT:    ret i16 [[COND]]
-;
-; GENERIC-LABEL: @test7e(
-; GENERIC-NEXT:  entry:
-; GENERIC-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[X:%.*]], 0
-; GENERIC-NEXT:    br i1 [[TOBOOL]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
-; GENERIC:       cond.true:
-; GENERIC-NEXT:    [[TMP0:%.*]] = tail call i64 @llvm.cttz.i64(i64 [[X]], i1 true)
-; GENERIC-NEXT:    [[CAST:%.*]] = trunc i64 [[TMP0]] to i16
-; GENERIC-NEXT:    br label [[COND_END]]
-; GENERIC:       cond.end:
-; GENERIC-NEXT:    [[COND:%.*]] = phi i16 [ [[CAST]], [[COND_TRUE]] ], [ 64, [[ENTRY:%.*]] ]
-; GENERIC-NEXT:    ret i16 [[COND]]
+; ALL-LABEL: @test7e(
+; ALL-NEXT:  entry:
+; ALL-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[X:%.*]], 0
+; ALL-NEXT:    [[TMP0:%.*]] = tail call i64 @llvm.cttz.i64(i64 [[X]], i1 true)
+; ALL-NEXT:    [[CAST:%.*]] = trunc i64 [[TMP0]] to i16
+; ALL-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i16 64, i16 [[CAST]]
+; ALL-NEXT:    ret i16 [[COND]]
 ;
 entry:
   %tobool = icmp eq i64 %x, 0
   br i1 %tobool, label %cond.end, label %cond.true
 
 cond.true:                                        ; preds = %entry
   %0 = tail call i64 @llvm.cttz.i64(i64 %x, i1 true)
   %cast = trunc i64 %0 to i16
   br label %cond.end
 
 cond.end:                                         ; preds = %entry, %cond.true
   %cond = phi i16 [ %cast, %cond.true ], [ 64, %entry ]
   ret i16 %cond
 }
 
 define i16 @test8e(i32 %x) {
-; BMI-LABEL: @test8e(
-; BMI-NEXT:  entry:
-; BMI-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[X:%.*]], 0
-; BMI-NEXT:    [[TMP0:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[X]], i1 true)
-; BMI-NEXT:    [[CAST:%.*]] = trunc i32 [[TMP0]] to i16
-; BMI-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i16 32, i16 [[CAST]]
-; BMI-NEXT:    ret i16 [[COND]]
-;
-; LZCNT-LABEL: @test8e(
-; LZCNT-NEXT:  entry:
-; LZCNT-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[X:%.*]], 0
-; LZCNT-NEXT:    br i1 [[TOBOOL]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
-; LZCNT:       cond.true:
-; LZCNT-NEXT:    [[TMP0:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[X]], i1 true)
-; LZCNT-NEXT:    [[CAST:%.*]] = trunc i32 [[TMP0]] to i16
-; LZCNT-NEXT:    br label [[COND_END]]
-; LZCNT:       cond.end:
-; LZCNT-NEXT:    [[COND:%.*]] = phi i16 [ [[CAST]], [[COND_TRUE]] ], [ 32, [[ENTRY:%.*]] ]
-; LZCNT-NEXT:    ret i16 [[COND]]
-;
-; GENERIC-LABEL: @test8e(
-; GENERIC-NEXT:  entry:
-; GENERIC-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[X:%.*]], 0
-; GENERIC-NEXT:    br i1 [[TOBOOL]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
-; GENERIC:       cond.true:
-; GENERIC-NEXT:    [[TMP0:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[X]], i1 true)
-; GENERIC-NEXT:    [[CAST:%.*]] = trunc i32 [[TMP0]] to i16
-; GENERIC-NEXT:    br label [[COND_END]]
-; GENERIC:       cond.end:
-; GENERIC-NEXT:    [[COND:%.*]] = phi i16 [ [[CAST]], [[COND_TRUE]] ], [ 32, [[ENTRY:%.*]] ]
-; GENERIC-NEXT:    ret i16 [[COND]]
+; ALL-LABEL: @test8e(
+; ALL-NEXT:  entry:
+; ALL-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[X:%.*]], 0
+; ALL-NEXT:    [[TMP0:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[X]], i1 true)
+; ALL-NEXT:    [[CAST:%.*]] = trunc i32 [[TMP0]] to i16
+; ALL-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i16 32, i16 [[CAST]]
+; ALL-NEXT:    ret i16 [[COND]]
 ;
 entry:
   %tobool = icmp eq i32 %x, 0
   br i1 %tobool, label %cond.end, label %cond.true
 
 cond.true:                                        ; preds = %entry
   %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
   %cast = trunc i32 %0 to i16

llvm/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll

 }
 
 ; Cannot reuse the table range compare, because the phi at the switch merge
 ; point is not dominated by the switch.
 define i32 @no_reuse_cmp2(i32 %x, i32 %y) {
 ; CHECK-LABEL: @no_reuse_cmp2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[EC:%.*]] = icmp ne i32 [[Y:%.*]], 0
-; CHECK-NEXT:    br i1 [[EC]], label [[SWITCH_ENTRY:%.*]], label [[SW_EPILOG:%.*]]
-; CHECK:       switch.entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 4
 ; CHECK-NEXT:    [[SWITCH_OFFSET:%.*]] = add i32 [[X]], 10
 ; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[TMP0]], i32 [[SWITCH_OFFSET]], i32 0
-; CHECK-NEXT:    br label [[SW_EPILOG]]
-; CHECK:       sw.epilog:
-; CHECK-NEXT:    [[R_0:%.*]] = phi i32 [ 100, [[ENTRY:%.*]] ], [ [[SPEC_SELECT]], [[SWITCH_ENTRY]] ]
+; CHECK-NEXT:    [[R_0:%.*]] = select i1 [[EC]], i32 [[SPEC_SELECT]], i32 100
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[R_0]], 0
 ; CHECK-NEXT:    [[DOTR_0:%.*]] = select i1 [[CMP]], i32 100, i32 [[R_0]]
 ; CHECK-NEXT:    ret i32 [[DOTR_0]]
 ;
 entry:
   %ec = icmp ne i32 %y, 0
   br i1 %ec, label %switch.entry, label %sw.epilog
 switch.entry:

llvm/test/Transforms/SimplifyCFG/safe-abs.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -S | FileCheck %s
 
 ; Reduced from arm_abs_q31() from CMSIS DSP suite.
 ; https://reviews.llvm.org/D65148#1629010
 
 define i32 @abs_with_clamp(i32 %arg) {
 ; CHECK-LABEL: @abs_with_clamp(
 ; CHECK-NEXT:  begin:
 ; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[ARG:%.*]], 0
-; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[END:%.*]], label [[NEGATIVE:%.*]]
-; CHECK:       negative:
 ; CHECK-NEXT:    [[IS_INT_MIN:%.*]] = icmp eq i32 [[ARG]], -2147483648
 ; CHECK-NEXT:    [[NEGATED:%.*]] = sub nsw i32 0, [[ARG]]
 ; CHECK-NEXT:    [[ABS:%.*]] = select i1 [[IS_INT_MIN]], i32 2147483647, i32 [[NEGATED]]
-; CHECK-NEXT:    br label [[END]]
-; CHECK:       end:
-; CHECK-NEXT:    [[TMP6:%.*]] = phi i32 [ [[ARG]], [[BEGIN:%.*]] ], [ [[ABS]], [[NEGATIVE]] ]
+; CHECK-NEXT:    [[TMP6:%.*]] = select i1 [[IS_POSITIVE]], i32 [[ARG]], i32 [[ABS]]
 ; CHECK-NEXT:    ret i32 [[TMP6]]
 ;
 begin:
   %is_positive = icmp sgt i32 %arg, 0
   br i1 %is_positive, label %end, label %negative
 
 negative: ; preds = %begin
   %is_int_min = icmp eq i32 %arg, -2147483648
   %negated = sub nsw i32 0, %arg
   %abs = select i1 %is_int_min, i32 2147483647, i32 %negated
   br label %end
 
 end:      ; preds = %negative, %begin
   %tmp6 = phi i32 [ %arg, %begin ], [ %abs, %negative ]
   ret i32 %tmp6
 }

llvm/test/Transforms/SimplifyCFG/safe-low-bit-extract.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -S | FileCheck %s
 
 ; This is the naive implementation of x86 BZHI/BEXTR instruction:
 ; it takes input and bit count, and extracts low nbits up to bit width.
 ; I.e. unlike shift it does not have any UB when nbits >= bitwidth.
 ; Which means we don't need a while PHI here, simple select will do.
 define i32 @extract_low_bits(i32 %input, i32 %nbits) {
 ; CHECK-LABEL: @extract_low_bits(
 ; CHECK-NEXT:  begin:
 ; CHECK-NEXT:    [[SHOULD_MASK:%.*]] = icmp ult i32 [[NBITS:%.*]], 32
-; CHECK-NEXT:    br i1 [[SHOULD_MASK]], label [[PERFORM_MASKING:%.*]], label [[END:%.*]]
-; CHECK:       perform_masking:
 ; CHECK-NEXT:    [[MASK_NOT:%.*]] = shl nsw i32 -1, [[NBITS]]
 ; CHECK-NEXT:    [[MASK:%.*]] = xor i32 [[MASK_NOT]], -1
 ; CHECK-NEXT:    [[MASKED:%.*]] = and i32 [[MASK]], [[INPUT:%.*]]
-; CHECK-NEXT:    br label [[END]]
-; CHECK:       end:
-; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[MASKED]], [[PERFORM_MASKING]] ], [ [[INPUT]], [[BEGIN:%.*]] ]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[SHOULD_MASK]], i32 [[MASKED]], i32 [[INPUT]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
 begin:
   %should_mask = icmp ult i32 %nbits, 32
   br i1 %should_mask, label %perform_masking, label %end
 
 perform_masking: ; preds = %begin
   %mask.not = shl nsw i32 -1, %nbits
   %mask = xor i32 %mask.not, -1
   %masked = and i32 %mask, %input
   br label %end
 
 end:             ; preds = %perform_masking, %begin
   %res = phi i32 [ %masked, %perform_masking ], [ %input, %begin ]
   ret i32 %res
 }

llvm/test/Transforms/SimplifyCFG/signbit-like-value-extension.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -S | FileCheck %s
 
 ; This looks like a normal sign extension, but it's not.
 ; This comes up in JPEG decoding. This check is really unpredictable,
 ; so it is likely beneficial to avoid the branch.
 
 define i32 @extend_value(i32 %storage, i32 %nbits) {
 ; CHECK-LABEL: @extend_value(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[SKIPNBITS:%.*]] = sub i32 32, [[NBITS:%.*]]
 ; CHECK-NEXT:    [[VALUE:%.*]] = lshr i32 [[STORAGE:%.*]], [[SKIPNBITS]]
 ; CHECK-NEXT:    [[SHOULDEXTEND:%.*]] = icmp sgt i32 [[STORAGE]], -1
-; CHECK-NEXT:    br i1 [[SHOULDEXTEND]], label [[EXTEND:%.*]], label [[END:%.*]]
-; CHECK:       extend:
 ; CHECK-NEXT:    [[HIGHBITMASK:%.*]] = shl nsw i32 -1, [[NBITS]]
 ; CHECK-NEXT:    [[HIGHBITMASKPLUSONE:%.*]] = add nsw i32 [[HIGHBITMASK]], 1
 ; CHECK-NEXT:    [[EXTENDED:%.*]] = add i32 [[HIGHBITMASKPLUSONE]], [[VALUE]]
-; CHECK-NEXT:    br label [[END]]
-; CHECK:       end:
-; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[EXTENDED]], [[EXTEND]] ], [ [[VALUE]], [[BB:%.*]] ]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[SHOULDEXTEND]], i32 [[EXTENDED]], i32 [[VALUE]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
 bb:
   %skipnbits = sub i32 32, %nbits
   %value = lshr i32 %storage, %skipnbits
   %shouldextend = icmp sgt i32 %storage, -1
   br i1 %shouldextend, label %extend, label %end
 

llvm/test/Transforms/SimplifyCFG/speculate-math.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -simplifycfg < %s | FileCheck %s --check-prefix=ALL --check-prefix=EXPENSIVE
 ; RUN: opt -S -simplifycfg -speculate-one-expensive-inst=false < %s | FileCheck %s --check-prefix=ALL --check-prefix=CHEAP
 
 declare float @llvm.sqrt.f32(float) nounwind readonly
 declare float @llvm.fma.f32(float, float, float) nounwind readonly
 declare float @llvm.fmuladd.f32(float, float, float) nounwind readonly
 declare float @llvm.fabs.f32(float) nounwind readonly
 declare float @llvm.minnum.f32(float, float) nounwind readonly
 declare float @llvm.maxnum.f32(float, float) nounwind readonly
 declare float @llvm.minimum.f32(float, float) nounwind readonly
 declare float @llvm.maximum.f32(float, float) nounwind readonly
 
 define double @fdiv_test(double %a, double %b) {
-; EXPENSIVE-LABEL: @fdiv_test(
-; EXPENSIVE-NEXT:  entry:
-; EXPENSIVE-NEXT:    [[CMP:%.*]] = fcmp ogt double [[A:%.*]], 0.000000e+00
-; EXPENSIVE-NEXT:    [[DIV:%.*]] = fdiv double [[B:%.*]], [[A]]
-; EXPENSIVE-NEXT:    [[COND:%.*]] = select i1 [[CMP]], double [[DIV]], double 0.000000e+00
-; EXPENSIVE-NEXT:    ret double [[COND]]
-;
-; CHEAP-LABEL: @fdiv_test(
-; CHEAP-NEXT:  entry:
-; CHEAP-NEXT:    [[CMP:%.*]] = fcmp ogt double [[A:%.*]], 0.000000e+00
-; CHEAP-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
-; CHEAP:       cond.true:
-; CHEAP-NEXT:    [[DIV:%.*]] = fdiv double [[B:%.*]], [[A]]
-; CHEAP-NEXT:    br label [[COND_END]]
-; CHEAP:       cond.end:
-; CHEAP-NEXT:    [[COND:%.*]] = phi double [ [[DIV]], [[COND_TRUE]] ], [ 0.000000e+00, [[ENTRY:%.*]] ]
-; CHEAP-NEXT:    ret double [[COND]]
+; ALL-LABEL: @fdiv_test(
+; ALL-NEXT:  entry:
+; ALL-NEXT:    [[CMP:%.*]] = fcmp ogt double [[A:%.*]], 0.000000e+00
+; ALL-NEXT:    [[DIV:%.*]] = fdiv double [[B:%.*]], [[A]]
+; ALL-NEXT:    [[COND:%.*]] = select i1 [[CMP]], double [[DIV]], double 0.000000e+00
+; ALL-NEXT:    ret double [[COND]]
 ;
 entry:
   %cmp = fcmp ogt double %a, 0.0
   br i1 %cmp, label %cond.true, label %cond.end
 
 cond.true:
   %div = fdiv double %b, %a
   br label %cond.end