Re: Speculative call support in the callgraph

[Jan Hubicka <hubicka at ucw dot cz>]

> 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.

Or rather no-one, since 3 won't have high enough frequency.  The
counter was really intended to look for most common destination by
a huge margin.
(like for GCC, most devirtualizations actually have probability of 1,
so these are more missed cases of static analysis)
> 
> 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).

Ok, this seems to make sense.  Lets merge the profiling/transformation
infrastructure from LIPO and I will add support for multiple speculation
into callgraph.  I was trying to keep in mind that devirtualization may
also want to eventually do more than one target, but I tought it is
better to keep things easy at beggining.

Thanks,
Honza