[llvm-dev] RFC: Reducing Instr PGO size overhead

[Xinliang David Li via llvm-dev]

LLVM Profile instrumentation incurs very large size (memory, storage)
overhead. For instance, the following is the binary size comparison of
the Clang binaries built  (-O2 -DNDEBUG) with different
configurations:


1) 60.9M  (built with Clang itself)
2) 280.4M (same as 1, but added -fprofile-instr-generate)
3) 54.9M (built with GCC 4.8)
4) 156.5M (same as 3, but added -fprofile-generate)

In other words, Clang's instrumentation increases binary size by 4.6X,
while GCC's instrumentation overhead is only  2.8X.

The profile data size from Clang instrumented binary is also much
larger. The following is a comparison:

1) 114.5M (raw profile data emitted by Clang instrumented by Clang)
2) 63.7M (indexed profile data emitted by Clang instrumented by Clang)
3) 33.1M (total size of GCDA files emitted by Clang instrumented by GCC).

Large size of overhead can limit the usability of PGO greatly:
a) devices with small system partition does not have much room left --
greatly bloated image due to instrumentation can prevent it from being
installed
b) Linker can be highly stressed when linking very large C++
applications -- large size increase due to instrumentation can prevent
those apps from being successfully linked
c) Large raw profile dumps may also cause problems, e.g. running out
of space. It can also profile bootstrap build really slow.


Looking at various sources of size increase caused by instrumentation,
it is clear that the biggest contributor is the __llvm_prf_names
section. The current PGO implementation uses function  assembly names
as the lookup keys in the indexed format so it needs to be emitted in
both rodata of the binary and in the raw/indexed profiles.

On the other hand, LLVM's indexed format also supports 'key collision'
-- it allows functions with the same key share the same entry in the
hash table. Function's structural hash values will be used as a
secondary key to find a real match.

The above feature allows us to use a different key other than function
assembly names and this can reduce binary/profile data size
significantly.  Function name's MD5 hash is a good candidate, and I
have a patch (3 parts: runtime, reader/writer, clang) that does just
that. The results are very promising. With this change, the clang
instrumented binary size is now 216M (down from 280M); the raw profile
size is only 40.1M (a 2.85X size reduction); and the indexed profile
size is only 29.5M (a 2.2X size reduction).

With the change, the indexed format size is smaller than GCC's (but
the latter has value profile data).  The binary size is still much
larger than GCC's, but with the late instrumentation, we will have
more size reduction.

A couple of more details of the patch:

1) When -fcoverage-mapping is specified, the llvm_prf_names will be
emitted to the binary, but they won't be dumped into the profile data.
In other words, with -fcoverage-mapping, only profile data will be
shrinked.   The reason is that llvm-cov tool reads function names from
the section (referenced from covmap) to support name based filtering
(including regular expression) when dumping line coverage report
2) The change is backward compatible such that old version of both raw
and index formats  can still be read by the new profile reader (and
therefore clients such as clang, llvm-profdata, llvm-cov tools)


I plan to submit the patch for review after some cleanups.

Thoughts, concerns?

thanks,

David