Re: [PATCH 1/3] tree-ssa-tail-merge: add IPA ICF infrastructure.

[Jeff Law <law@redhat.com>]

On 07/09/2015 07:56 AM, mliska wrote:
> gcc/ChangeLog:
>
> 2015-07-09  Martin Liska  <mliska@suse.cz>
>
> 	* dbgcnt.def: Add new debug counter.
> 	* ipa-icf-gimple.c (func_checker::compare_ssa_name): Add flag
> 	for strict mode.
> 	(func_checker::compare_memory_operand): Likewise.
> 	(func_checker::compare_cst_or_decl): Handle if we are in
> 	tail_merge_mode.
> 	(func_checker::compare_operand): Pass strict flag properly.
> 	(func_checker::stmt_local_def): New function.
> 	(func_checker::compare_phi_node): Move from sem_function class.
> 	(func_checker::compare_bb_tail_merge): New function.
> 	(func_checker::compare_bb): Improve STMT iteration.
> 	(func_checker::compare_gimple_call): Pass strict flag.
> 	(func_checker::compare_gimple_assign): Likewise.
> 	(func_checker::compare_gimple_label): Remove unused flag.
> 	(ssa_names_set): New class.
> 	(ssa_names_set::build): New function.
> 	* ipa-icf-gimple.h (func_checker::gsi_next_nonlocal): New
> 	function.
> 	(ssa_names_set::contains): New function.
> 	(ssa_names_set::add): Likewise.
> 	* ipa-icf.c (sem_function::equals_private): Use transformed
> 	function.
> 	(sem_function::compare_phi_node): Move to func_checker class.
> 	* ipa-icf.h: Add new declarations.
> 	* tree-ssa-tail-merge.c (check_edges_correspondence): New
> 	function.
> 	(find_duplicate): Add usage of IPA ICF gimple infrastructure.
> 	(find_clusters_1): Pass new sem_function argument.
> 	(find_clusters): Likewise.
> 	(tail_merge_optimize): Call IPA ICF comparison machinery.
So a general question.  We're passing in STRICT to several routines, 
which is fine.  But then we're also checking M_TAIL_MERGE_MODE.  What's 
the difference between the two?  Can they be unified?


>
> -/* Verifies that trees T1 and T2 are equivalent from perspective of ICF.  */
> +/* Verifies that trees T1 and T2 are equivalent from perspective of ICF.
> +   If STRICT flag is true, versions must match strictly.  */
>
>   bool
> -func_checker::compare_ssa_name (tree t1, tree t2)
> +func_checker::compare_ssa_name (tree t1, tree t2, bool strict)
This (and other) functions would seem to be used more than just ICF at 
this point.  A pass over the comments to update them as appropriate 
would be appreciated.

> @@ -626,6 +648,136 @@ func_checker::parse_labels (sem_bb *bb)
>       }
>   }
>
> +/* Return true if gimple STMT is just a local difinition in a
> +   basic block.  Used SSA names are contained in SSA_NAMES_SET.  */
s/difinition/definition/

I didn't find this comment particularly useful in understanding what 
this function does.  AFAICT the function looks as the uses of the LHS of 
STMT and verifies they're all in the same block as STMT, right?

It also verifies that the none of the operands within STMT are part of 
SSA_NAMES_SET.

What role do those properties play in the meaning of "local definition"?




> @@ -1037,4 +1205,60 @@ func_checker::compare_gimple_asm (const gasm *g1, const gasm *g2)
>     return true;
>   }
>
> +void
> +ssa_names_set::build (basic_block bb)
Needs a function comment.  What are the "important" names we're 
collecting here?

Is a single forward and backward pass really sufficient to find all the 
important names?

In the backward pass, do you have to consider things like ASMs?  I guess 
it's difficult to understand what you need to look at because it's not 
entirely clear the set of SSA_NAMEs you're building.



> @@ -149,12 +153,20 @@ public:
>        mapping between basic blocks and labels.  */
>     void parse_labels (sem_bb *bb);
>
> +  /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
> +     true value is returned if phi nodes are semantically
> +     equivalent in these blocks.  */
> +  bool compare_phi_node (sem_bb *sem_bb1, sem_bb *sem_bb2);
Presumably in the case of tail merging, FUNC1 and FUNC will be the same :-)


>     /* Verifies that trees T1 and T2 are equivalent from perspective of ICF.  */
> -  bool compare_ssa_name (tree t1, tree t2);
> +  bool compare_ssa_name (tree t1, tree t2, bool strict = true);
>
>     /* Verification function for edges E1 and E2.  */
>     bool compare_edge (edge e1, edge e2);
> @@ -204,7 +216,7 @@ public:
>     bool compare_tree_ssa_label (tree t1, tree t2);
>
>     /* Function compare for equality given memory operands T1 and T2.  */
> -  bool compare_memory_operand (tree t1, tree t2);
> +  bool compare_memory_operand (tree t1, tree t2, bool strict = true);
>
>     /* Function compare for equality given trees T1 and T2 which
>        can be either a constant or a declaration type.  */
> @@ -213,7 +225,7 @@ public:
>     /* Function responsible for comparison of various operands T1 and T2.
>        If these components, from functions FUNC1 and FUNC2, are equal, true
>        is returned.  */
> -  bool compare_operand (tree t1, tree t2);
> +  bool compare_operand (tree t1, tree t2, bool strict = false);
Is the default value for the parameter really needed in these methods? 
Why not go ahead and update the callers, I don't think we have that many 
right now.

>
>     /* Compares two tree list operands T1 and T2 and returns true if these
>        two trees are semantically equivalent.  */
> @@ -237,6 +249,13 @@ public:
>        first parameter of a function.  */
>     static bool compatible_types_p (tree t1, tree t2);
>
> +  /* Return true if gimple STMT is just a local difinition in a
> +     basic block.  Used SSA names are contained in SSA_NAMES_SET.  */
> +  static bool stmt_local_def (gimple stmt, ssa_names_set *ssa_names_set);
s/difinition/definition/
As with the implementation, I think the comment needs some clarification.

>  +/* SSA NAMES set.  */
> +class ssa_names_set
So what names are in this set?  Ie, what is the ::build method searching 
for?


> diff --git a/gcc/tree-ssa-tail-merge.c b/gcc/tree-ssa-tail-merge.c
> index 018a966..b8632d7 100644
> --- a/gcc/tree-ssa-tail-merge.c
> +++ b/gcc/tree-ssa-tail-merge.c
> @@ -187,6 +187,7 @@ along with GCC; see the file COPYING3.  If not see
>
>   #include "config.h"
>   #include "system.h"
> +#include <list>
>   #include "coretypes.h"
>   #include "backend.h"
>   #include "tree.h"
I think Andrew has defined an ordering for the initial include files. 
I think you've #included <list> in the wrong place.  Can it be moved down?

> +
> +using namespace ipa_icf;
> +using namespace ipa_icf_gimple;
Is this wise?  Does it significantly help with conciseness within the 
tail merging pass where it wants things ipa-icf and ipa-icf-gimple?

I'm not objecting at this point, I want to hear your thoughts.


>
>   /* Describes a group of bbs with the same successors.  The successor bbs are
>      cached in succs, and the successor edge flags are cached in succ_flags.
> @@ -1220,17 +1231,48 @@ gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse,
>       }
>   }
>
> +static bool
> +check_edges_correspondence (basic_block bb1, basic_block bb2)
Needs a function comment.


> +{
> +  edge e1, e2;
> +  edge_iterator ei2 = ei_start (bb2->succs);
> +
> +  for (edge_iterator ei1 = ei_start (bb1->succs); ei_cond (ei1, &e1);
> +       ei_next (&ei1))
> +    {
> +      ei_cond (ei2, &e2);
> +
> +      if (e1->dest->index != e2->dest->index ||
> +	  (e1->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
> +	  != (e2->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
> +	return false;
Formatting looks wrong in that conditional.

> @@ -1265,11 +1307,29 @@ find_duplicate (same_succ same_succ, basic_block bb1, basic_block bb2)
>     if (vuse_escaped && vuse1 != vuse2)
>       return;
>
> -  if (dump_file)
> -    fprintf (dump_file, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
> +  if (!icf_result && dump_file)
> +    fprintf (dump_file,
> +	     "missed merge optimization: <bb %d> duplicate of <bb %d>\n",
>   	     bb1->index, bb2->index);
So I realize this goes away in the #2 patch.  But I'm curious how often 
it triggered and if there were any interesting patterns when the old 
tail merging triggered by the version utilizing ICF didn't or vice-versa.

You mentioned posting some before/after results, but I haven't seen them 
yet.

I'd like to do another pass over these changes, so if you could repost 
after the cleanups noted above, it'd be appreciated.

Jeff