Re: [Predicated Ins vs Branches] O3 and PGO result in 2x performance drop relative to O2

[Changbin Du <changbin.du@huawei.com>]

On Mon, Jul 31, 2023 at 03:53:26PM +0200, Richard Biener wrote:
[snip]
> > The main difference in the compilation output about code around the miss-prediction
> > branch is:
> >   o In O2: predicated instruction (cmov here) is selected to eliminate above
> >     branch. cmov is true better than branch here.
> >   o In O3/PGO: bitout() is inlined into encode_file(), and branch instruction
> >     is selected. But this branch is obviously *unpredictable* and the compiler
> >     doesn't know it. This why O3/PGO are are so bad for this program.
> >
> > Gcc doesn't support __builtin_unpredictable() which has been introduced by llvm.
> > Then I tried to see if __builtin_expect_with_probability(e,x, 0.5) can serve the
> > same purpose. The result is negative.
> 
> But does it appear to be predictable with your profiling data?
>
I profiled the branch-misses event on a kabylake machine. 99% of the
mis-prediction blames to encode_file() function.

$ sudo perf record -e branch-instructions:pp,branch-misses:pp -c 1000 -- taskset -c 0 ./huffman.O3 test.data

Samples: 197K of event 'branch-misses:pp', Event count (approx.): 197618000
Overhead  Command     Shared Object     Symbol
  99.58%  huffman.O3  huffman.O3        [.] encode_file
   0.12%  huffman.O3  [kernel.vmlinux]  [k] __x86_indirect_thunk_array
   0.11%  huffman.O3  libc-2.31.so      [.] _IO_getc
   0.01%  huffman.O3  [kernel.vmlinux]  [k] common_file_perm

Then annotate encode_file() function:

Samples: 197K of event 'branch-misses:pp', 1000 Hz, Event count (approx.): 197618000
encode_file  /work/myWork/linux/pgo/huffman.O3 [Percent: local period]
Percent│     ↑ je      38
       │     bitout():
       │     current_byte <<= 1;
       │ 70:   add     %edi,%edi
       │     if (b == '1') current_byte |= 1;
 48.70 │    ┌──cmp     $0x31,%dl
 47.11 │    ├──jne     7a
       │    │  or      $0x1,%edi
       │    │nbits++;  
       │ 7a:└─→inc     %eax
       │     if (b == '1') current_byte |= 1;
       │       mov     %edi,current_byte
       │     nbits++;
       │       mov     %eax,nbits
       │     if (nbits == 8) {
  1.16 │       cmp     $0x8,%eax
  3.03 │     ↓ je      a0
       │     encode_file():
       │     for (s=codes[ch]; *s; s++) bitout (outfile, *s);
       │       movzbl  0x1(%r13),%edx
       │       inc     %r13
       │       test    %dl,%dl
       │     ↑ jne     70
       │     ↑ jmp     38
       │       nop

-- 
Cheers,
Changbin Du