| Message ID | 398814b6afe28679f16c5d4b9879accb7984b76b.1415911038.git.mliska@suse.cz |
|---|---|
| State | New |
| Headers | show |
> Hello. > > Following patch set introduces new template class for fibonacci heap > that is mainly utilized by IPA inliner. Apart from that, I also enhanced > existing sreal implementation so that it can also handle negative numbers. > > I was primary motivated by Honza, because current heap implementation > in ipa-inline.c suffers from round off problems. > > I was able to run WPA phase which was by about ~3% slower than current > implementation. > > All patches can bootstrap and no regression was seen on x86_64-linux-pc. > > I welcome any remarks connected to the patch set. > > Thanks, > Martin > > (please ignore following ChangeLog diff) I do :) To give bit of context into this, the inliner is basically a greedy algorithm making inline decisions in the increasing badness order. The badness is (in simplified view) a ration of size growth over expected speedup with several other factors added. Given that both size and expected speedup do not have any good upper bound, it is very hard to compute those as fixed point 32bit value required for current fibheap keys. In some cases we need to watch overflows when badness get really high (especially now when we inline functions ignoring the size bounds in cases we know the inlining will bring considerable benefits) and there are cases where we have too much of roundoff to 0. This happens in tramp3d that has tens of thousdands inline candidates all with expected growth <5 instructions that still needs to be ordered. I changed the fixed point few times, but now again we hit case where tramp3d inlining exhaust the queue with badness of 0 (and thus making kind of random decisions) so I think going into floating point badness would be significant improvement. It needs to be done curefully though to avoid performance impact with LTO where fibheap maintenance is important % of compile time. Honza
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index d418c82..7ff6e3b 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,4 @@ + 2014-11-13 Eric Botcazou <ebotcazou@adacore.com> * doc/tm.texi.in (SELECT_CC_MODE): Update example.