Re: Type inheritance graph analysis & speculative devirtualization, part 7/7 (speculative devirtualizatoin)

["H.J. Lu" <hjl dot tools at gmail dot com>]

On Sun, Sep 1, 2013 at 6:57 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
> Hi,
> this patch implement speculative devirtualization.  It is a trivial pass that
> asks for targets of every polymorphic call in a program and if the list
> contains one likely target, it produces an speculative call. No context
> sensitive analysis is done at the moment.  This call may or may not survive
> into final program depending if we do somehting useful about the direct call.
>
> The pass is currently disabled for LTO because
> http://gcc.gnu.org/ml/gcc-patches/2013-08/msg01007.html is needed to properly
> build type inheritance graph.
>
> With LTO it is supposed to be effective on a premise that most types are not
> escaping LTO unit and thus we see all possible targets.  Without LTO it makes
> stronger assumption that you usually call only targets defined in current unit,
> if any.
>
> Path is suprisingly effective on Firefox:
> 105306 polymorphic calls, 0 devirtualized, 34258 speculatively devirtualized, 4056 cold
> 66875 have multiple targets, 0 overwritable, 0 already speculated (0 agree, 0 disagree), 0 not defined
>
> So about 32% of calls are devirutalized.  By random checking, these can be
> tracked to real occurences of code where virtual is used in a silly way.
> I plan to introduce warning for that (I have code for that already since it
> makes it easier to analyze what changes are really made and why).
>
> Martin Liska rebuilt with FDO based indirect call resolution.  Here we get:
> 23928 indirect calls trained.
> 12837 (53.65%) have common target.
> 342 (1.43%) targets was not found.
> 8378 (35.01%) speculations seems useless.
> 4117 (17.21%) speculations produced.
>
> I compared the overlap that is devirtualized by both techniques.  There is
> almost 100% match, except that FDO code is not dealing well with thunks and
> those 342 calls that seem to go out of libxul into plugins.  I will fix the
> thunk issue later.
>
> I also tested QT, where the numbers are smaller - only about 20% of devirtualized
> calls, but largery things seems similar.
>
> For non-LTO build, the devirtualization also seems sane, there seems to be
> about 8% of miss rate on GCC bootstrap that seems acceptable. I tracked most of
> those down into randomly included headers that do define derived types of a
> given class that are unused in the current unit.  I think we can track this by
> computing reachable functions in current unit and looking for vtables actually
> used by construction.  One of such actually triggers undefined reference in
> build of libstdc++ and therefore I added the check disabling devirtualization
> to DECL_EXTERNAL for now.  It is because the libstdc++ header seems to have
> explicit instantiation of a template that is never linked with.
>
> I currently enabled the pass by default at -O2.  Based on the experience about
> missrate, we may want to disable it for -O2 non-LTO if it shows to be too risky
> on some codebases.
>
> Bootstrapped/regtested x86_64-linux and ppc64-linux, also tested with lto bootstrap
> with the LTO ODR code and tested on Firefox and QT builds. Will commit the patch
> later today.
>
> Comments are welcome.
> Honza
>
>         * common.opt (fdevirtualize-speculatively): New function.
>         * invoke.texi (fdevirtualize-speculatively): Document.
>         * ipa-devirt.c: Include ipa-inline.h
>         (likely_target_p): New function.
>         (ipa_devirt): New function.
>         (gate_ipa_devirt): New function.
>         (pass_data_ipa_devirt): New static var.
>         (pass_ipa_devirt): Likewise.
>         (make_pass_ipa_devirt): New function.
>         * opts.c (default_options): Add OPT_fdevirtualize_speculatively.
>         (common_handle_option): Disable devirtualization when
>         value range profiling is available.
>         * passes.def (pass_ipa_devirt): Add.
>         * timever.def (TV_IPA_DEVIRT): New timevar.
>         * tree-pass.h (make_pass_ipa_devirt):
>

This triggered:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63814

H.J.