experimental results of branch predictions 2

[Jan Hubicka <jh at suse dot cz>]

Hi
Here are updated results after fixing the BR_PROB/reversed jumps confusion
pointer out by Richard.  This has improved quality of opcode/pointer heruistics
quite a bit and other are unchanged. The no predictions heruistics no longer
works so nicely.  What is the magic connection between taken/not taken branch
and his reversed/nonreversed RTL representation is behind my understanding.

I am attaching the results from few tests I've made.  It is quite interesting
to see how does the predicability change in various programs.

Note that the overall hitrate is very high compared to the results reported
by the papers, so maybe something is wrong....

Honza

Byte benchmark:
HERUISTICS                  BRANCHES  (REL)  HITRATE/PERFECT    COVERAGE  (REL)
first match                     1316 100.0%  82.22%/ 89.17%  27335780119 100.0%
combined                        1316 100.0%  82.22%/ 89.17%  27335780119 100.0%
note (real or user defined)     1170  88.9%  87.77%/ 89.17%  27335780119 100.0%
no predictions heruistics        231  17.6%  65.89%/ 82.64%   3850130184  14.1%
loop branch                      117   8.9%  98.25%/ 98.26%   3127472619  11.4%
loop exit                        420  31.9%  92.77%/ 93.14%  11815619186  43.2%
opcode eq                        364  27.7%  63.09%/ 78.51%   5425792334  19.8%
opcode ne                        305  23.2%  94.13%/ 94.68%  10815603893  39.6%
opcode positive                   88   6.7%  66.12%/ 87.07%   1777535737   6.5%
opcode negative                   11   0.8% 100.00%/100.00%       426361   0.0%
exit block                         1   0.1%      0%/     0%            0   0.0%
pointer                            9   0.7% 100.00%/100.00%           15   0.0%

CPP results:
HERUISTICS                  BRANCHES  (REL)  HITRATE/PERFECT    COVERAGE  (REL)
opcode ne                       1013  38.7%  86.11%/ 93.49%      5615205  36.5%
first match                     2619 100.0%  81.28%/ 95.81%     15399639 100.0%
combined                        2619 100.0%  82.57%/ 95.81%     15399639 100.0%
pointer                          189   7.2%  93.22%/ 98.44%       121775   0.8%
opcode eq                       1014  38.7%  84.76%/ 96.26%      3324823  21.6%
loop exit                        976  37.3%  76.26%/ 91.14%      9968042  64.7%
no predictions heruistics        437  16.7%  56.37%/ 98.62%      2594354  16.8%
note (real or user defined)     1814  69.3%  91.73%/ 95.81%     15399639 100.0%
loop branch                      177   6.8%  90.59%/ 94.62%      1033047   6.7%
opcode positive                   27   1.0%  65.48%/ 85.36%        12744   0.1%
opcode negative                   15   0.6%  98.88%/100.00%         1432   0.0%
exit block                         5   0.2% 100.00%/100.00%         1484   0.0%

Genattrtab:
HERUISTICS                  BRANCHES  (REL)  HITRATE/PERFECT    COVERAGE  (REL)
no predictions heruistics        313  15.6%  44.85%/ 92.60%     32019002   2.9%
first match                     2009 100.0%  74.79%/ 86.63%   1121794307 100.0%
combined                        2009 100.0%  74.90%/ 86.63%   1121794307 100.0%
note (real or user defined)     1844  91.8%  82.69%/ 86.63%   1121794307 100.0%
opcode ne                        863  43.0%  74.60%/ 81.37%    581218390  51.8%
pointer                          315  15.7%  82.46%/ 82.48%    427069200  38.1%
opcode eq                        638  31.8%  76.38%/ 93.05%    485917500  43.3%
loop exit                        737  36.7%  88.51%/ 90.73%   1026844893  91.5%
loop branch                       31   1.5%  40.79%/ 64.25%      1760869   0.1%
opcode positive                   19   0.9%  45.68%/ 56.10%      2954815   0.3%
exit block                       102   5.1% 100.00%/100.00%      1369746   0.1%
opcode negative                   19   0.9%  99.52%/ 99.52%      3186083   0.3%

Genrecog:
HERUISTICS                  BRANCHES  (REL)  HITRATE/PERFECT    COVERAGE  (REL)
opcode eq                        413  47.3%  65.61%/ 86.76%       411330  39.9%
first match                      874 100.0%  72.49%/ 87.47%      1030049 100.0%
combined                         874 100.0%  67.94%/ 87.47%      1030049 100.0%
note (real or user defined)      830  95.0%  68.77%/ 87.47%      1030049 100.0%
opcode ne                        268  30.7%  64.23%/ 86.45%       343143  33.3%
no predictions heruistics        113  12.9%  54.43%/ 91.84%        97515   9.5%
loop exit                        229  26.2%  76.86%/ 85.13%       477710  46.4%
pointer                          153  17.5%  70.94%/ 88.51%       240638  23.4%
loop branch                       27   3.1%  50.93%/ 80.47%        20057   1.9%
exit block                        33   3.8% 100.00%/100.00%        46458   4.5%
opcode negative                   23   2.6%  70.09%/ 78.99%        50711   4.9%
opcode positive                    7   0.8%  49.05%/ 71.69%           53   0.0%

Gcc:
HERUISTICS                  BRANCHES  (REL)  HITRATE/PERFECT    COVERAGE  (REL)
pointer                         9907  10.1%  84.13%/ 84.21%    967408943  37.3%
opcode eq                      43329  44.2%  75.42%/ 92.50%   1106101975  42.7%
first match                    98026 100.0%  74.83%/ 87.31%   2591014086 100.0%
combined                       98026 100.0%  75.05%/ 87.31%   2591014086 100.0%
note (real or user defined)    42890  43.8%  83.13%/ 87.31%   2591014086 100.0%
opcode ne                      37918  38.7%  76.04%/ 82.48%   1287552982  49.7%
exit block                      2344   2.4% 100.00%/100.00%     20932206   0.8%
loop exit                      18045  18.4%  87.99%/ 90.60%   2177840676  84.0%
no predictions heruistics      10749  11.0%  37.34%/ 94.04%     95141296   3.7%
opcode negative                 1091   1.1%  99.17%/ 99.58%     17078652   0.7%
loop branch                     1678   1.7%  63.66%/ 77.52%      8857644   0.3%
opcode positive                 1443   1.5%  66.70%/ 71.17%     14589724   0.6%