[PATCH 1/3] tree-ssa-tail-merge: add IPA ICF infrastructure.
Martin Liška
mliska@suse.cz
Thu Jul 16 11:25:00 GMT 2015
On 07/09/2015 06:24 PM, Jeff Law wrote:
> 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?
Hello.
I would say that STRICT is a bit generic mechanism that was introduced some time before. It's e.g. used for checking of THIS arguments for methods and make checking
more sensitive in situations that are somehow special.
The newly added state is orthogonal to the previous one.
>
>
>>
>> -/* 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/
Thanks.
>
> 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"?
I tried to explain it more deeply what's the purpose of this function.
>
>
>
>
>> @@ -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 :-)
Yes, the function is not called from tail-merge pass.
>
>
>> /* 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.
I've just grepped errors and it's more than 20 occurrences, so I hope it clarifies
the usage of implicit value of the function.
>
>>
>> /* 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?
Sure.
>
>> +
>> +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.
I must agree with you, as I've started using both namespaces in tree-tail merge pass,
it makes not much sense anymore. I suggest to come up with a namespace that will
encapsulate 'identical code folding'-related stuff. What about:
namespace icf
?
>
>
>>
>> /* 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
>
>
I decided to come up with a single patch, mainly because Richi pointed out that we should create a new tree pass and
it makes sense to do it in a single commit. In last patch of the previous series, I modified some UBSAN tests, but proper
fix would be to ignore merging of UBSAN_* calls (as suggested in corresponding emails).
Following patch can survive bootstrap on x86_64-linux-pc and ppc64le-linux-pc and regression tests.
There are sizes of binaries before and after the patch:
INKSCAPE:
before: 15626296 B
after: 15622200 B
Firefox:
before: 130390352 B
after: 130379744 B
diff: 10608 B
Thanks,
Martin
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-tree-ssa-tail-merge-replace-engine-with-IPA-ICF-infr.patch
Type: text/x-patch
Size: 44020 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20150716/eb0dd8ce/attachment.bin>
More information about the Gcc-patches
mailing list