Re: [PATCH] Make ipa-prop analyze BBs in DOM order

[Jan Hubicka <hubicka at ucw dot cz>]

> Hi,
> 
> the following patch deals with requested propagation in PR 53787 in
> the real benchmark (as opposed to the original simple testcase) by
> analyzing individual BBs in ipa-prop.c in dominator order.
> 
> Currently we do the analysis in two loops, in the first the order is
> given by FOR_EACH_BB_FN and in the second the order is the order of
> call graph edges (which in practice is quite bad because we tend to
> start with BBs towards the end).  When analysis determines that a
> non-SSA parameter or that data pointed to by a parameter are modified,
> this is marked into a function wide flag (describing the parameter)
> and we always consider the data clobbered from that moment on in order
> to save AA walking.
> 
> This patch changes the analysis into dominator order and data is
> considered clobbered only in dominator children of a block where it
> was determined to be possibly clobbered, not in the whole function.
> This was confirmed to help in the aforementioned PR.
> 
> The patch also, enforces a cap on the number of statements walked
> (approx. 4 times the highest I have ever seen).  On the other hand it
> gives up trying to cache the bitmap of visited memory-SSAs.  The
> per-BB information had to be put somewhere and I took this opportunity
> to cram a lot of commonly used per-function data into the same
> structure, which is then passed among various functions.  The new
> structure replaces the struct param_analysis_info.
> 
> Bootstrapped and tested on x86_64-linux, I have also LTO-built Firefox
> at -O3 with it.  OK for trunk?
> 
> Thanks,
> 
> Martin
> 
> 
> 2014-02-12  Martin Jambor  <mjambor@suse.cz>
> 
> 	PR tree-optimization/53787
> 	* params.def (PARAM_IPA_CP_LOOP_HINT_BONUS): New param.
> 	* ipa-prop.h (ipa_node_params): Rename uses_analysis_done to
> 	analysis_done, update all uses.
> 	* ipa-prop.c: Include domwalk.h
> 	(param_analysis_info): Removed.
> 	(param_aa_status): New type.
> 	(ipa_bb_info): Likewise.
> 	(func_body_info): Likewise.
> 	(ipa_get_bb_info): New function.
> 	(aa_overwalked): Likewise.
> 	(find_dominating_aa_status): Likewise.
> 	(parm_bb_aa_status_for_bb): Likewise.
> 	(parm_preserved_before_stmt_p): Changed to use new param AA info.
> 	(load_from_unmodified_param): Accept func_body_info as a parameter
> 	instead of parms_ainfo.
> 	(parm_ref_data_preserved_p): Changed to use new param AA info.
> 	(parm_ref_data_pass_through_p): Likewise.
> 	(ipa_load_from_parm_agg_1): Likewise.  Update callers.
> 	(compute_complex_assign_jump_func): Changed to use new param AA info.
> 	(compute_complex_ancestor_jump_func): Likewise.
> 	(ipa_compute_jump_functions_for_edge): Likewise.
> 	(ipa_compute_jump_functions): Removed.
> 	(ipa_compute_jump_functions_for_bb): New function.
> 	(ipa_analyze_indirect_call_uses): Likewise, moved variable
> 	declarations down.
> 	(ipa_analyze_virtual_call_uses): Accept func_body_info instead of node
> 	and info, moved variable declarations down.
> 	(ipa_analyze_call_uses): Accept and pass on func_body_info instead of
> 	node and info.
> 	(ipa_analyze_stmt_uses): Likewise.
> 	(ipa_analyze_params_uses): Removed.
> 	(ipa_analyze_params_uses_in_bb): New function.
> 	(ipa_analyze_controlled_uses): Likewise.
> 	(free_ipa_bb_info): Likewise.
> 	(analysis_dom_walker): New class.
> 	(ipa_analyze_node): Handle node-specific forbidden analysis,
> 	initialize and free func_body_info, use dominator walker.
> 	(ipcp_modif_dom_walker): New class.
> 	(ipcp_transform_function): Create and free func_body_info, use
> 	ipcp_modif_dom_walker, moved a lot of functionality there.

> 
> --- 59,111 ----
>   #include "ipa-utils.h"
>   #include "stringpool.h"
>   #include "tree-ssanames.h"
> + #include "domwalk.h"
>   
> ! /* Intermediate information that we get from AA analysis about a parameter.  */

AA is alias analysis, so I guess either "AA" (removing analysis) or "alias analysis" :)

>   
> ! struct param_aa_status
>   {
> +   /* If not true, look at the dominator parent instead.  */
> +   bool valid;

In isolation, this comment is hardly understandable.
Perhaps you can mention that this info is used for each parameter during the
dominator order propagation.


> + 
> +   /* Whether we have seen something which might have modified the data in
> +      question.  Parm is for the parameter itself, ref is for data it points to
> +      but using the alias type of individual accesses and pt is the same thing
> +      but for computing aggregate pass-through functions using a very inclusive
> +      ao_ref.  */

I guess PARM/REF/PR per coding style ;))

> ! 
> ! /* Structure with global information that is only used when looking at function
> !    body. */
> ! 
> ! struct func_body_info
> ! {
> !   /* The node that is being analyzed.  */
> !   cgraph_node *node;
> ! 
> !   /* Its info.  */
> !   struct ipa_node_params *info;
> ! 
> !   /* Information about individual BBs. */
> !   vec<ipa_bb_info> ibbis;

I would keep vector name same with accestor, it is called bb_info, so perhaps bb_infos?
ibbis is funny name (same of paas above ;)

> !   /* FIXME: FBI can be NULL if we are being called from outside
> !      ipa_node_analysis or ipcp_transform_function, which currently happens
> !      during inlining analysis.  It would be great to extend fbi's lifetime and
> !      always have it.  Currently, we are just not afraid of too much walking in
> !      that case.  */

Yep, how much info do we really test in ipa-inline?
I suppose we can hook the info into the jump functions we remember, but not stream it for LTO
since it is pointless without the function body...

> *************** parm_ref_data_pass_through_p (struct par
> *** 893,902 ****
>      reference respectively.  */

Probably you want to update comment for new params.
> Index: src/gcc/params.def
> ===================================================================
> *** src.orig/gcc/params.def
> --- src/gcc/params.def
> *************** DEFPARAM (PARAM_IPA_MAX_AGG_ITEMS,
> *** 947,952 ****
> --- 947,958 ----
>   	  "jump functions and lattices",
>   	  16, 0, 0)
>   
> + DEFPARAM (PARAM_IPA_MAX_AA_STEPS,
> + 	  "ipa-max-aa-steps",
> + 	  "Maximum number of statements that will be visited by IPA formal "
> + 	  "parameter analysis based on alias analysis in any given function",
> + 	  100000, 0, 0)
> + 
>   DEFPARAM (PARAM_IPA_CP_LOOP_HINT_BONUS,
>   	  "ipa-cp-loop-hint-bonus",
>   	  "Compile-time bonus IPA-CP assigns to candidates which make loop "

Probably you need also invoke.texi update.

OK with these changes.
Thanks,
Honza