On Fri, Aug 9, 2013 at 4:21 PM, Jan Hubicka <hubi...@ucw.cz> wrote: >> 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.
Ok. Rong, can you help rip the TOPN profiler part from google branch and submit to trunk? TopN profiler can be used in other scenarios other than indirect call profiling. thanks, David > > Thanks, > Honza
