Speculative call support in the callgraph

[Xinliang David Li]

On Fri, Aug 9, 2013 at 1:24 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> I have not looked at the details. One high level question: this form
>> seems to only support one indirect target case. LIPO uses TOPN
>> indirect target profiling (tracking multiple targets), which can be
>> used by LTO as well (when the topn profiling gets into trunk).
>
> Well, adding multiple direct edges for given call will need extension into
> cgraph_turn_edge_to_speculative and cgraph_speculative_call_info APIs (to allow
> multple direct edges) to indirect_info common_target datastructure, to
> profiling histograms and to the gimple_ic code.  Otherwise there is nothing
> really hard coded about single direct target.
>
> How much benefits do you see from having multiple direct targets?

It can be large depending on applications. For some apps, there are
very callsites with 2 or 3 very hot targets.

> I would
> expect them to be quite quickly disappearing as N increases...

For the large apps I see, N rarely exceeds 4. For most of the cases,
the hot targets are 2 or 3 with 2 being very common.  In LIPO, we
track 4 targets, but only use top 2.

> How the TOPN profiling counter is implemented?

Currently FDO's value profiler is one value based -- it is quite
faulty because it can not handle cases where hot targets alternates.
For instance for sequence 1, 2, 1, 2, 1, 2, 3,3, 1 -- the winner will
be 3 instead of 1.

TOPN algorithm is a LFU based --- when match is not found, the least
frequent used entry will be evicted. To avoid ping-pong effect, total
eviction count is also tracked -- when it exceeds a threshold, the
bottom counter will be clear to make room for hot entries (instead of
letting them killing each other).

thanks,

David


>
> Honza