> On Fri, Aug 9, 2013 at 1:24 PM, Jan Hubicka <hubi...@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