Re: Extend ipa-inline-analysis to recognize functoin/loop invariant parameters

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

On Fri, Sep 23, 2011 at 10:34 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
> Hi,
> this patch extends inliner's predicate infrastructure to track optimization
> oppurtunities that depends on properties of call site parameters that are
> not readilly available (and do not belong to) jump functions.
>
> For this new inline_param_summary is introduced that is filled in
> estimate_function_body_sizes used at predicate evaulation time and maintained
> over inlining and cloning.
>
> I now use it to track probability that parameter will change. ?Probability
> of 0 means invaraint values, while probabilities in range 1...REG_BR_PROB_BASE
> means that parameter will be recomputed in between function calls with
> the known probability.
>
> The motivation for it comes from testcases like c-ray raytracer, where function
> raysphere has two parameters (ray and sphere). It is called from loop that for
> given ray iterates across all spheres in the scene.
> Large benefits from inlining raysphere are due to fact that good portion of the
> function is loop invariant and thus it is subsequentely lifted out of the loop
> by PRE.
>
> The patch splits NOT_CONSTANT predicate into NOT_CONSTANT and CHANGED.
> NOT_CONSTANT is true always when parameters is not a know IP invaraint (in
> sense of jump functions), while CHANGED is true when parameter change
> probaiblity is >= 1 (i.e. it is not function level invariant). NOT_CONSTANT is
> used when evaulating builtin_constant_p that is never true for loop invariant.
> CHANGED is used when deciding whether given statment will be executed per
> invocation of the particula rfunction call. ?Moreover predicates can now be
> evaulated into execution probablity that correspond to the probability of
> parameter change.
>
> As implemented now, the patch is good enough to analyze c-ray and work out that
> raysphere is cool to inline, it however won't inline it because of the hard
> size limits.
>
> Some guesswork is obviously needed. Most magic is in param_change_prob and the
> way it handles non-SSA parameters where it is quite non-obvious how much of code
> motion will be possible after inlining. ?Also predicate_probability can really
> only evaulate simple predicated like (op0 changed) into op0's change probability.
> It makes simple estiamtes so (op0 changed || op1 changed) is maximum of op0 and op1
> change probability while (op0 changed && op1 changed) is minimum.
> The second is quite rare, so this should work relatively well in practice.
>
> There are other simple things I would like to add incrementally. I.e. tracking
> whether parameter is address of automatic variable (and thus inlining likely
> enables SRA). ?This should help C++ inlining and move us closer to be able to
> analyze fortran testcases. ?Fortran is particularly difficult because most of
> stuff is passed by reference and we will probably need to introduce jump functions
> for values passed in aggregates and values passed by reference to understand
> things like array descriptors.
>
> The patch has little effect on spec2000 or our C++ benchmark suite at least
> with current inline limits. Most tests are small enough so we usully do all
> inlining allowed and thus saner priority queue makes little difference. ?It
> however helps some of Mozilla inner loops and increase amount of inlining done
> there by about 8% while keeping same code size.
>
> Bootstrapped/regtsted x86_64-linux.
>
> Honza
>
> ? ? ? ?* gcc.dg/ipa/inline-1.c: new testcase.
> ? ? ? ?* gcc.dg/ipa/inline-2.c: new testcase.
> ? ? ? ?* gcc.dg/ipa/inline-3.c: new testcase.
> ? ? ? ?* gcc.dg/ipa/inline-4.c: new testcase.
>
> ? ? ? ?* ipa-inline-transform.c (inline_call): Add comment.
> ? ? ? ?* ipa-inline.h (inline_param_summary): New structure and vector.
> ? ? ? ?(struct inline_edge_summary): Add param field.
> ? ? ? ?* ipa-inline-analysis.c (CHANGED): New constant.
> ? ? ? ?(add_clause): Handle CHANGED and NOT_CONSTANT.
> ? ? ? ?(predicate_probability): New function.
> ? ? ? ?(dump_condition): Dump CHANGED predicate.
> ? ? ? ?(evaluate_conditions_for_known_args): Handle ERROR_MARK as marker
> ? ? ? ?of unknown function wide invariant.
> ? ? ? ?(evaluate_conditions_for_edge): Handle change probabilities.
> ? ? ? ?(inline_edge_duplication_hook): Copy param summaries.
> ? ? ? ?(inline_edge_removal_hook): Free param summaries.
> ? ? ? ?(dump_inline_edge_summary): Fix dumping of indirect edges and callee sizes;
> ? ? ? ?dump param summaries.
> ? ? ? ?(will_be_nonconstant_predicate): Use CHANGED predicate.
> ? ? ? ?(record_modified_bb_info): New structure.
> ? ? ? ?(record_modified): New function.
> ? ? ? ?(param_change_prob): New function.
> ? ? ? ?(estimate_function_body_sizes): Compute param summaries.
> ? ? ? ?(estimate_edge_size_and_time): Add probability argument.
> ? ? ? ?(estimate_node_size_and_time): Add inline_param_summary argument;
> ? ? ? ?handle predicate probabilities.
> ? ? ? ?(remap_predicate): Fix formating.
> ? ? ? ?(remap_edge_change_prob): New function.
> ? ? ? ?(remap_edge_summaries): Rename from ...; use remap_edge_change_prob.
> ? ? ? ?(remap_edge_predicates): ... this one.
> ? ? ? ?(inline_merge_summary): Remap edge summaries; handle predicate probabilities;
> ? ? ? ?remove param summaries after we are done.
> ? ? ? ?(do_estimate_edge_time): Update.
> ? ? ? ?(do_estimate_edge_growth): Update.
> ? ? ? ?(read_inline_edge_summary): Read param info.
> ? ? ? ?(inline_read_summary): Fix formating.
> ? ? ? ?(write_inline_edge_summary): Write param summaries.

This caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50528

-- 
H.J.