On Fri, Sep 23, 2011 at 10:34 AM, Jan Hubicka <hubi...@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.
