[PATCH 3/5] IPA ICF pass
Martin Liška
mliska@suse.cz
Thu Jun 26 11:18:00 GMT 2014
On 06/20/2014 09:31 AM, Trevor Saunders wrote:
> On Fri, Jun 13, 2014 at 12:44:22PM +0200, mliska wrote:
>> Hello,
>> this is core of IPA ICF patchset. It adds new pass and registers all needed stuff related to a newly introduced interprocedural optimization.
>>
>> Algorithm description:
>> In LGEN, we visit all read-only variables and functions. For each symbol, a hash value based on e.g. number of arguments,
>> number of BB, GIMPLE CODES is computed (similar hash is computed for read-only variables). This kind of information is streamed
>> for LTO.
>>
>> In WPA, we build congruence classes for all symbols having a same hash value. For functions, these classes are subdivided in WPA by argument type comparison. Each reference (a call or a variable reference) to another semantic item candidate is marked and stored for further congruence class reduction (similar algorithm as Value Numbering: www.cs.ucr.edu/~gupta/teaching/553-07/Papers/value.pdf).
>>
>> For every congruence class of functions with more than one semantic function, we load function body. Having this information, we can
>> process complete semantic function equality and subdivide such congruence class. Read-only variable class members are also deeply compared.
>>
>> After that, we process Value numbering algorithm to do a final subdivision. Finally, all items belonging to a congruence class with more than one
>> item are merged.
>>
>> Martin
>>
>> Changelog:
>>
>> 2014-06-13 Martin Liska <mliska@suse.cz>
>> Jan Hubicka <hubicka@ucw.cz>
>>
>> * Makefile.in: New pass object file added.
>> * common.opt: New -fipa-icf flag introduced.
>> * doc/invoke.texi: Documentation enhanced for the pass.
>> * lto-section-in.c: New LTO section for a summary created by IPA-ICF.
>> * lto-streamer.h: New section name introduced.
>> * opts.c: Optimization is added to -O2.
>> * passes.def: New pass added.
>> * timevar.def: New time var for IPA-ICF.
>> * tree-pass.h: Pass construction function.
>> * ipa-icf.h: New pass header file added.
>> * ipa-icf.c: New pass source file added.
>>
>> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
>> index 5587b75..4b59418 100644
>> --- a/gcc/Makefile.in
>> +++ b/gcc/Makefile.in
>> @@ -1276,6 +1276,7 @@ OBJS = \
>> ipa-profile.o \
>> ipa-prop.o \
>> ipa-pure-const.o \
>> + ipa-icf.o \
>> ipa-reference.o \
>> ipa-ref.o \
>> ipa-utils.o \
>> diff --git a/gcc/common.opt b/gcc/common.opt
>> index 7f05092..3661dcc 100644
>> --- a/gcc/common.opt
>> +++ b/gcc/common.opt
>> @@ -1409,6 +1409,10 @@ fipa-pure-const
>> Common Report Var(flag_ipa_pure_const) Init(0) Optimization
>> Discover pure and const functions
>>
>> +fipa-icf
>> +Common Report Var(flag_ipa_icf) Optimization
>> +Perform Identical Code Folding for functions and read-only variables
>> +
>> fipa-reference
>> Common Report Var(flag_ipa_reference) Init(0) Optimization
>> Discover readonly and non addressable static variables
>> diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
>> index 3c02341..b2bbe69 100644
>> --- a/gcc/doc/invoke.texi
>> +++ b/gcc/doc/invoke.texi
>> @@ -377,7 +377,7 @@ Objective-C and Objective-C++ Dialects}.
>> -fif-conversion2 -findirect-inlining @gol
>> -finline-functions -finline-functions-called-once -finline-limit=@var{n} @gol
>> -finline-small-functions -fipa-cp -fipa-cp-clone @gol
>> --fipa-pta -fipa-profile -fipa-pure-const -fipa-reference @gol
>> +-fipa-pta -fipa-profile -fipa-pure-const -fipa-reference -fipa-icf @gol
>> -fira-algorithm=@var{algorithm} @gol
>> -fira-region=@var{region} -fira-hoist-pressure @gol
>> -fira-loop-pressure -fno-ira-share-save-slots @gol
>> @@ -6947,6 +6947,7 @@ also turns on the following optimization flags:
>> -finline-small-functions @gol
>> -findirect-inlining @gol
>> -fipa-sra @gol
>> +-fipa-icf @gol
>> -fisolate-erroneous-paths-dereference @gol
>> -foptimize-sibling-calls @gol
>> -fpartial-inlining @gol
>> @@ -7862,6 +7863,14 @@ it may significantly increase code size
>> (see @option{--param ipcp-unit-growth=@var{value}}).
>> This flag is enabled by default at @option{-O3}.
>>
>> +@item -fipa-icf
>> +@opindex fipa-icf
>> +Perform Identical Code Folding for functions and read-only variables.
>> +Behavior is similar to Gold Linker ICF optimization. Symbols proved
>> +as semantically equivalent are redirected to corresponding symbol. The pass
>> +sensitively decides for usage of alias, thunk or local redirection.
>> +This flag is enabled by default at @option{-O2}.
>> +
>> @item -fisolate-erroneous-paths-dereference
>> Detect paths which trigger erroneous or undefined behaviour due to
>> dereferencing a NULL pointer. Isolate those paths from the main control
>> diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c
>> new file mode 100644
>> index 0000000..628d257
>> --- /dev/null
>> +++ b/gcc/ipa-icf.c
>> @@ -0,0 +1,3247 @@
>> +/* Interprocedural Identical Code Folding pass
>> + Copyright (C) 2014 Free Software Foundation, Inc.
>> +
>> + Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
>> +
>> +This file is part of GCC.
>> +
>> +GCC is free software; you can redistribute it and/or modify it under
>> +the terms of the GNU General Public License as published by the Free
>> +Software Foundation; either version 3, or (at your option) any later
>> +version.
>> +
>> +GCC is distributed in the hope that it will be useful, but WITHOUT ANY
>> +WARRANTY; without even the implied warranty of MERCHANTABILITY or
>> +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
>> +for more details.
>> +
>> +You should have received a copy of the GNU General Public License
>> +along with GCC; see the file COPYING3. If not see
>> +<http://www.gnu.org/licenses/>. */
>> +
>> +/* Interprocedural Identical Code Folding for functions and
>> + read-only variables.
>> +
>> + The goal of this transformation is to discover functions and read-only
>> + variables which do have exactly the same semantics.
>> +
>> + In case of functions,
>> + we could either create a virtual clone or do a simple function wrapper
>> + that will call equivalent function. If the function is just locally visible,
>> + all function calls can be redirected. For read-only variables, we create
>> + aliases if possible.
Hello Trevor,
thank you for your time spent with review.
> In theory you don't actually need the alias, you could change all the
> references to point at the merged data right? Can that automatically
> happen for hidden visibility alias?
>
>> +
>> + Optimization pass arranges as follows:
>> + 1) All functions and read-only variables are visited and internal
>> + data structure, either sem_function or sem_variables is created.
>> + 2) For every symbol from the previoues step, VAR_DECL and FUNCTION_DECL are
> previous
>
>> + saved and matched to corresponding sem_items.
>> + 3) These declaration are ignored for equality check and are solved
>> + by Value Numbering algorithm published by Alpert, Zadeck in 1992.
>> + 4) We compute hash value for each symbol.
>> + 5) Congruence classes are created based on hash value. If hash value are
>> + equal, equals function is called and symbols are deeply compared.
>> + We must prove that all SSA names, declarations and other items
>> + correspond.
>> + 6) Value Numbering is executed for these classes. At the end of the process
>> + all symbol members in remaining classes can be mrged.
> merged
>
>> + 7) Merge operation creates alias in case of read-only variables. For
>> + callgraph node, we must decide if we can redirect local calls,
>> + create an alias or a thunk.
>> +
>> +*/
>> +
>> +#include "config.h"
>> +#include "system.h"
>> +#include "coretypes.h"
>> +#include "tree.h"
>> +#include "basic-block.h"
>> +#include "tree-ssa-alias.h"
>> +#include "internal-fn.h"
>> +#include "gimple-expr.h"
>> +#include "is-a.h"
>> +#include "gimple.h"
>> +#include "expr.h"
>> +#include "gimple-iterator.h"
>> +#include "gimple-ssa.h"
>> +#include "tree-cfg.h"
>> +#include "tree-phinodes.h"
>> +#include "stringpool.h"
>> +#include "tree-ssanames.h"
>> +#include "tree-dfa.h"
>> +#include "tree-pass.h"
>> +#include "gimple-pretty-print.h"
>> +#include "ipa-inline.h"
>> +#include "cfgloop.h"
>> +#include "except.h"
>> +#include "hash-table.h"
>> +#include "coverage.h"
>> +#include "pointer-set.h"
>> +#include "attribs.h"
>> +#include "print-tree.h"
>> +#include "lto-streamer.h"
>> +#include "data-streamer.h"
>> +#include "ipa-utils.h"
>> +#include "ipa-icf.h"
>> +
>> +namespace {
>> +
>> +func_checker::func_checker (): initialized (false)
>> +{
>> +}
> that style seems weird I'd expect
>
> function_checker::function_checker () :
> initialized (false)
> {
> }
>
> but really why isn't that inline in the class, it seems really short.
>
>> +
>> +/* Itializes internal structures according to given number of
> initializes
You are right, I'll put it to header file.
>
>> + source and target SSA names. The number of source names is SSA_SOURCE,
>> + respectively SSA_TARGET. */
>> +
>> +void
>> +func_checker::initialize (unsigned ssa_source, unsigned ssa_target)
>> +{
>> + release ();
>> + initialized = true;
>> +
>> + source_ssa_names.create (ssa_source);
>> + target_ssa_names.create (ssa_target);
>> +
>> + for (unsigned int i = 0; i < ssa_source; i++)
>> + source_ssa_names.safe_push (-1);
>> +
>> + for (unsigned int i = 0; i < ssa_target; i++)
>> + target_ssa_names.safe_push (-1);
>> +
>> + edge_map = new pointer_map <edge> ();
>> +
>> + decl_map = new pointer_map <tree> ();
>> +}
> So, if its infallible why do you need a seperate init function?
Sure.
>
>> +
>> +/* Memory release routine. */
>> +
>> +void
>> +func_checker::release (void)
>> +{
>> + if (!initialized)
>> + return;
>> +
>> + delete edge_map;
>> + delete decl_map;
>> + source_ssa_names.release();
>> + target_ssa_names.release();
>> +}
> obligatory why isn't this a dtor?
Yes.
>
>> +
>> +/* Verifies that trees T1 and T2 do correspond. */
>> +
>> +bool
>> +func_checker::compare_ssa_name (tree t1, tree t2)
>> +{
>> + unsigned i1 = SSA_NAME_VERSION (t1);
>> + unsigned i2 = SSA_NAME_VERSION (t2);
>> +
>> + if (source_ssa_names[i1] == -1)
>> + source_ssa_names[i1] = i2;
>> + else if (source_ssa_names[i1] != (int) i2)
>> + return false;
>> +
>> + if(target_ssa_names[i2] == -1)
>> + target_ssa_names[i2] = i1;
>> + else if (target_ssa_names[i2] != (int) i1)
>> + return false;
>> +
>> + return true;
>> +}
>> +
>> +/* Verification function for edges E1 and E2. */
>> +
>> +bool
>> +func_checker::compare_edge (edge e1, edge e2)
>> +{
>> + if (e1->flags != e2->flags)
>> + return false;
>> +
>> + edge *slot = edge_map->contains (e1);
>> + if (slot)
>> + {
>> + SE_EXIT_DEBUG (*slot == e2);
>> + }
>> + else
>> + {
>> + slot = edge_map->insert (e1);
>> + *slot = e2;
>> + }
> it'd be more efficient to just call insert and pass &existed to check if
> the element was previously there. It'd always be 1 hash lookup not
> sometimes 2.
Thanks, good point.
>
>> +/* Verification function for declaration trees T1 and T2 that
> its more comparison than verification right?
>
>> +func_checker::compare_decl (tree t1, tree t2, tree func1, tree func2)
>> +{
>> + if (!auto_var_in_fn_p (t1, func1) || !auto_var_in_fn_p (t2, func2))
>> + SE_EXIT_DEBUG (t1 == t2);
>> +
>> + if (!types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2)))
>> + SE_EXIT_FALSE ();
>> +
>> + tree *slot = decl_map->contains (t1);
>> + if (slot)
>> + {
>> + SE_EXIT_DEBUG (*slot == t2);
>> + }
>> + else
>> + {
>> + slot = decl_map->insert (t1);
>> + *slot = t2;
>> + }
> same
>
>> +congruence_class::congruence_class (unsigned int _id): id(_id)
>> +{
>> + members.create (2);
> hrm, we should probably add a specialization of auto_vec<T, 0> so you
> can use that for things like this and lose the weird .create () stuff.
It would make sense such a specialization.
>
>> +}
>> +
>> +/* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
>> +
>> +sem_usage_pair::sem_usage_pair (sem_item *_item, unsigned int _index):
>> + item (_item), index (_index)
> we've been naming members m_foo which should solve the shadowing problem
> here as well as making code more readable.
I globally renamed all my private members to start with m_.
>
>> +sem_item::~sem_item ()
>> +{
>> + if (tree_refs_set)
>> + pointer_set_destroy (tree_refs_set);
>> +
>> + for (unsigned i = 0; i < usages.length (); i++)
>> + delete usages[i];
> what about the vectors themselves? who owns them? I know this bit of
> vec<> is horrible :(
Yeah, the leak is reported by -fmem-report too.
>
>> +/* Compare two types if are same aliases in case of strict aliasing
>> + is enabled. */
> nit, bad grammer
>
>> +bool
>> +sem_item::compare_for_aliasing (tree t1, tree t2)
>> +{
>> + if (flag_strict_aliasing)
>> + {
>> + alias_set_type s1 = get_deref_alias_set (TREE_TYPE (t1));
>> + alias_set_type s2 = get_deref_alias_set (TREE_TYPE (t2));
>> +
>> + return s1 == s2;
>> + }
>> +
>> + return true;
>> +}
>> +
>> +/* Semantic function constructor that uses STACK as bitmap memory stack. */
>> +
>> +sem_function::sem_function (bitmap_obstack *stack): sem_item (FUNC, stack),
>> + compared_func (NULL)
>> +{
>> + arg_types.create (0);
>> +}
>> +
>> +/* Constructor based on callgraph node _NODE with computed hash _HASH.
>> + Bitmap STACK is used for memory allocation. */
>> +sem_function::sem_function (cgraph_node *node, hashval_t hash,
>> + bitmap_obstack *stack):
>> + sem_item (FUNC, node, hash, stack), bb_sorted (NULL), compared_func (NULL)
>> +{
>> + arg_types.create (0);
>> +}
>> +
>> +sem_function::~sem_function ()
>> +{
>> + if (!bb_sorted)
>> + return;
>> +
>> + for (unsigned i = 0; i < bb_count; i++)
>> + free (bb_sorted[i]);
>> +
>> + free (bb_sizes);
>> + free (bb_sorted);
>> +}
> who owns arg_types? it doesn't seem to be us
Fixed.
>
>> +sem_function::get_hash (void)
>> +{
>> + if(!hash)
>> + {
>> + hash = 177454; /* Random number for function type. */
>> +
>> + hash = iterative_hash_object (arg_count, hash);
>> + hash = iterative_hash_object (bb_count, hash);
>> + hash = iterative_hash_object (edge_count, hash);
>> + hash = iterative_hash_object (cfg_checksum, hash);
>> + hash = iterative_hash_object (gcode_hash, hash);
>> +
>> + for (unsigned i = 0; i < bb_count; i++)
>> + hash = iterative_hash_object (hash, get_bb_hash (bb_sorted[i]));
>> +
>> + for (unsigned i = 0; i < bb_count; i++)
>> + hash = iterative_hash_object (bb_sizes[i], hash);
>> + }
>> +
>> + return hash;
>> +}
> I have to say I've always wondered if our hash functions try too hard to
> be perfect hashes at the expensive of speed, but of course its hard to
> know without lots of data.
>
>> +
>> +/* Fast equality function based on knowledge known in WPA. */
>> +
>> +bool
>> +sem_function::equals_wpa (sem_item *item)
>> +{
>> + if (item->type != FUNC)
>> + return false;
> should this just be an assert? When we're creating the congruence
> classes in the first place we can keep functions and variables in
> different classes right?
You are right, I guarantee that a function and a variable cannot be in a same group.
>
>> +/* Returns true if the item equals to ITEM given as arguemnt. */
> argument
>
>> +sem_function::equals_private (sem_item *item)
>> +{
>> + if (item->type != FUNC)
>> + return false;
> assert?
>
>> +
>> + basic_block bb1, bb2;
>> + edge e1, e2;
>> + edge_iterator ei1, ei2;
>> + int *bb_dict = NULL;
>> + bool result = true;
>> + tree arg1, arg2;
>> +
>> + compared_func = static_cast<sem_function *> (item);
>> +
>> + gcc_assert (decl != item->decl);
>> +
>> + if (arg_count != compared_func->arg_count
>> + || bb_count != compared_func->bb_count
>> + || edge_count != compared_func->edge_count
>> + || cfg_checksum != compared_func->cfg_checksum)
>> + SE_EXIT_FALSE();
>> +
>> + if (!equals_wpa (item))
> isn't this redundant with a bunch of the checks above it? could you
> remove them?
>
>> + return false;
>> +
>> + /* Checking function arguments. */
>> + tree decl1 = DECL_ATTRIBUTES (decl);
>> + tree decl2 = DECL_ATTRIBUTES (compared_func->decl);
>> +
>> + while (decl1)
>> + {
>> + if (decl2 == NULL)
>> + SE_EXIT_FALSE();
> are attributes always in the same order?
They can be in a different order, I will enhance this part.
>
>> +
>> + if (get_attribute_name (decl1) != get_attribute_name (decl2))
>> + SE_EXIT_FALSE();
>> +
>> + tree attr_value1 = TREE_VALUE (decl1);
>> + tree attr_value2 = TREE_VALUE (decl2);
>> +
>> + if (attr_value1 && attr_value2)
>> + {
>> + bool ret = compare_operand (TREE_VALUE (attr_value1),
>> + TREE_VALUE (attr_value2), decl,
>> + compared_func->decl);
>> + if (!ret)
>> + SE_EXIT_FALSE_WITH_MSG ("attribute values are different")
>> + }
>> + else if (!attr_value1 && !attr_value2)
>> + {}
>> + else
>> + SE_EXIT_FALSE ();
>> +
>> + decl1 = TREE_CHAIN (decl1);
>> + decl2 = TREE_CHAIN (decl2);
>> + }
>> +
>> + if (decl1 != decl2)
>> + SE_EXIT_FALSE();
>> +
>> + checker.initialize (ssa_names_size, compared_func->ssa_names_size);
>> +
>> + for (arg1 = DECL_ARGUMENTS (decl), arg2 = DECL_ARGUMENTS (compared_func->decl);
>> + arg1; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2))
>> + checker.compare_decl (arg1, arg2, decl, compared_func->decl);
>> +
>> + /* Exception handling regions comparison. */
>> + if (!compare_eh_region (region_tree, compared_func->region_tree, decl,
>> + compared_func->decl))
>> + SE_EXIT_FALSE();
>> +
>> + /* Checking all basic blocks. */
>> + for (unsigned i = 0; i < bb_count; ++i)
>> + if(!compare_bb (bb_sorted[i], compared_func->bb_sorted[i], decl,
>> + compared_func->decl))
>> + SE_EXIT_FALSE();
>> +
>> + SE_DUMP_MESSAGE ("All BBs are equal\n");
>> +
>> + /* Basic block edges check. */
>> + for (unsigned i = 0; i < bb_count; ++i)
>> + {
>> + bb_dict = XNEWVEC (int, bb_count + 2);
>> + memset (bb_dict, -1, (bb_count + 2) * sizeof (int));
>> +
>> + bb1 = bb_sorted[i]->bb;
>> + bb2 = compared_func->bb_sorted[i]->bb;
>> +
>> + ei2 = ei_start (bb2->preds);
>> +
>> + for (ei1 = ei_start (bb1->preds); ei_cond (ei1, &e1); ei_next (&ei1))
>> + {
>> + ei_cond (ei2, &e2);
>> +
>> + if (!bb_dict_test (bb_dict, e1->src->index, e2->src->index))
>> + SE_EXIT_FALSE_WITH_MSG("edge comparison returns false");
>> +
>> + if (!bb_dict_test (bb_dict, e1->dest->index, e2->dest->index))
>> + SE_EXIT_FALSE_WITH_MSG("BB comparison returns false");
>> +
>> + if (e1->flags != e2->flags)
>> + SE_EXIT_FALSE_WITH_MSG("flags comparison returns false");
> check this condition before the previous two since I guess its faster?
Sure.
>
>> +sem_function::init_refs_for_tree (tree t)
>> +{
>> + switch (TREE_CODE (t))
>> + {
>> + case VAR_DECL:
>> + case FUNCTION_DECL:
>> + tree_refs.safe_push (t);
>> + break;
>> + case MEM_REF:
>> + case ADDR_EXPR:
>> + case OBJ_TYPE_REF:
>> + init_refs_for_tree (TREE_OPERAND (t, 0));
>> + break;
>> + case FIELD_DECL:
>> + init_refs_for_tree (DECL_FCONTEXT (t));
>> + break;
>> + default:
>> + break;
>> + }
>> +}
>> +
>> +/* Initializes references to another sem_item for gimple STMT of type assign. */
>> +
>> +void
>> +sem_function::init_refs_for_assign (gimple stmt)
>> +{
>> + if (gimple_num_ops (stmt) != 2)
>> + return;
>> +
>> + tree rhs = gimple_op (stmt, 1);
>> +
>> + init_refs_for_tree (rhs);
>> +}
>> +
>> +/* Initializes references to other semantic functions/variables. */
>> +
>> +void
>> +sem_function::init_refs (void)
>> +{
>> + for (unsigned i = 0; i < bb_count; i++)
>> + {
>> + basic_block bb = bb_sorted[i]->bb;
>> +
>> + for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
>> + gsi_next (&gsi))
>> + {
>> + gimple stmt = gsi_stmt (gsi);
>> + hashval_t code = (hashval_t) gimple_code (stmt);
>> +
>> + switch (code)
>> + {
>> + case GIMPLE_CALL:
>> + {
>> + tree funcdecl = gimple_call_fndecl (stmt);
>> +
>> + /* Function pointer variables are not support yet. */
> supported
>
>> + if (funcdecl)
>> + tree_refs.safe_push (funcdecl);
>> +
>> + break;
>> + }
>> + case GIMPLE_ASSIGN:
>> + init_refs_for_assign (stmt);
>> + break;
>> + default:
>> + break;
>> + }
>> + }
>> + }
>> +}
>> +
>> +/* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
>> + be applied. */
>> +bool
>> +sem_function::merge (sem_item *alias_item)
>> +{
>> + gcc_assert (alias_item->type == FUNC);
>> +
>> + sem_function *alias_func = static_cast<sem_function *> (alias_item);
>> +
>> + struct cgraph_node *original = get_node ();
>> + struct cgraph_node *local_original = original;
>> + struct cgraph_node *alias = alias_func->get_node ();
>> + bool original_address_matters;
>> + bool alias_address_matters;
>> +
>> + bool create_thunk = false;
>> + bool create_alias = false;
>> + bool redirect_callers = false;
>> + bool original_discardable = false;
>> +
>> + /* Do not attempt to mix functions from different user sections;
>> + we do not know what user intends with those. */
>> + if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
>> + || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
>> + && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
>> + {
>> + if (dump_file)
>> + fprintf (dump_file,
>> + "Not unifying; original and alias are in different sections.\n\n");
>> + return false;
>> + }
>> +
>> + /* See if original is in a section that can be discarded if the main
>> + symbol is not used. */
>> + if (DECL_EXTERNAL (original->decl))
>> + original_discardable = true;
>> + if (original->resolution == LDPR_PREEMPTED_REG
>> + || original->resolution == LDPR_PREEMPTED_IR)
>> + original_discardable = true;
>> + if (symtab_can_be_discarded (original))
>> + original_discardable = true;
> shouldn't this last check handle the previous ones?
>
>> +
>> + /* See if original and/or alias address can be compared for equality. */
>> + original_address_matters
>> + = (!DECL_VIRTUAL_P (original->decl)
>> + && (original->externally_visible
>> + || address_taken_from_non_vtable_p (original)));
>> + alias_address_matters
>> + = (!DECL_VIRTUAL_P (alias->decl)
>> + && (alias->externally_visible
>> + || address_taken_from_non_vtable_p (alias)));
>> +
>> + /* If alias and original can be compared for address equality, we need
>> + to create a thunk. Also we can not create extra aliases into discardable
>> + section (or we risk link failures when section is discarded). */
>> + if ((original_address_matters
>> + && alias_address_matters)
>> + || original_discardable)
>> + {
>> + create_thunk = !stdarg_p (TREE_TYPE (alias->decl));
>> + create_alias = false;
>> + /* When both alias and original are not overwritable, we can save
>> + the extra thunk wrapper for direct calls. */
>> + redirect_callers
>> + = (!original_discardable
>> + && cgraph_function_body_availability (alias) > AVAIL_OVERWRITABLE
>> + && cgraph_function_body_availability (original) > AVAIL_OVERWRITABLE);
>> + }
>> + else
>> + {
>> + create_alias = true;
>> + create_thunk = false;
>> + redirect_callers = false;
>> + }
>> +
>> + if (create_alias && DECL_COMDAT_GROUP (alias->decl))
>> + {
>> + create_alias = false;
>> + create_thunk = true;
>> + }
>> +
>> + /* We want thunk to always jump to the local function body
>> + unless the body is comdat and may be optimized out. */
>> + if ((create_thunk || redirect_callers)
>> + && (!original_discardable
>> + || (DECL_COMDAT_GROUP (original->decl)
>> + && (DECL_COMDAT_GROUP (original->decl)
>> + == DECL_COMDAT_GROUP (alias->decl)))))
>> + local_original
>> + = cgraph (symtab_nonoverwritable_alias (original));
>> +
>> + if (redirect_callers)
>> + {
>> + /* If alias is non-overwritable then
>> + all direct calls are safe to be redirected to the original. */
>> + bool redirected = false;
>> + while (alias->callers)
>> + {
>> + struct cgraph_edge *e = alias->callers;
>> + cgraph_redirect_edge_callee (e, local_original);
>> + push_cfun (DECL_STRUCT_FUNCTION (e->caller->decl));
>> +
>> + if (e->call_stmt)
>> + cgraph_redirect_edge_call_stmt_to_callee (e);
>> +
>> + pop_cfun ();
>> + redirected = true;
>> + }
>> +
>> + /* The alias function is removed just if symbol address
> s/just//
>
>> + does not matters. */
> s/matters/matter/
>
>> +sem_function *
>> +sem_function::parse (struct cgraph_node *node, bitmap_obstack *stack)
>> +{
>> + tree fndecl = node->decl;
>> + struct function *func = DECL_STRUCT_FUNCTION (fndecl);
>> +
>> + if (!func || !cgraph_function_with_gimple_body_p (node))
>> + return NULL;
>> +
>> + if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node->decl)) != NULL)
>> + return NULL;
>> +
>> + sem_function *f = new sem_function (node, 0, stack);
>> +
>> + f->init ();
>> +
>> + return f;
>> +}
>> +
>> +/* Parses function arguments and result type. */
>> +
>> +void
>> +sem_function::parse_tree_args (void)
>> +{
>> + tree result;
>> + arg_types.create (4);
>> + tree fnargs = DECL_ARGUMENTS (decl);
>> +
>> + for (tree parm = fnargs; parm; parm = DECL_CHAIN (parm))
>> + arg_types.safe_push (TYPE_CANONICAL (DECL_ARG_TYPE (parm)));
>> +
>> + /* Function result type. */
>> + result = DECL_RESULT (decl);
>> + result_type = result ? TYPE_CANONICAL (TREE_TYPE (result)) : NULL;
>> +
>> + /* During WPA, we can get arguments by following method. */
>> + if (!fnargs)
>> + {
>> + tree type = TYPE_ARG_TYPES (TREE_TYPE (decl));
>> + for (tree parm = type; parm; parm = TREE_CHAIN (parm))
>> + arg_types.safe_push (TYPE_CANONICAL (TREE_VALUE (parm)));
>> +
>> + result_type = TREE_TYPE (TREE_TYPE (decl));
>> + }
>> +
>> + arg_count = arg_types.length ();
> So, is it really worth the extra memory to save a memory access when you
> need the number of arguments? especially considering you'll probably
> want the vector elements next.
Actually in LGEN phase, I just need the number of arguments (arg_count). In WPA I would just use arg_types vector and corresponding length () method.
>
>> +/* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
>> + true value is returned if phi nodes are sematically
> semantically
>
>> + equivalent in these blocks . */
> perhaps return true if .... ?
>
>> +sem_function::gsi_next_nondebug_stmt (gimple_stmt_iterator &gsi)
> I'd say a pointer makes it clearler the callie will modify the argument.
>
>> +{
>> + gimple s;
>> +
>> + s = gsi_stmt (gsi);
>> +
>> + while (gimple_code (s) == GIMPLE_DEBUG)
>> + {
>> + gsi_next (&gsi);
>> + gcc_assert (!gsi_end_p (gsi));
>> +
>> + s = gsi_stmt (gsi);
>> + }
>> +}
> really, shouldn't this be part of the gsi interface not something you
> hand roll here?
You are right, similar function can be seen in gimple-iterator.h. I'll use it.
>
>> +
>> +/* Iterates GSI statement iterator to the next non-virtual statement. */
>> +
>> +void
>> +sem_function::gsi_next_nonvirtual_phi (gimple_stmt_iterator &it)
> same
This function will be moved to gimple-iterator.h
>
>> +sem_function::icf_handled_component_p (tree t)
>> +{
>> + enum tree_code tc = TREE_CODE (t);
>> +
>> + return ((handled_component_p (t) && handled_component_p (t))
> it must be too late, or are you calling the same function twice with the
> same args?
>
>> + || tc == ADDR_EXPR || tc == MEM_REF || tc == REALPART_EXPR
>> + || tc == IMAGPART_EXPR || tc == OBJ_TYPE_REF);
>> +}
>> +/* Returns true if the item equals to ITEM given as arguemnt. */
> argument
>
> Its nice to see someone trying this and better it works ;) I wonder if
> in the future it'll be worth looking at congruity of chunks of functions
> and then sharing those too.
>
> anyway I've had it for tonight hopefully I can finish looking at this
> soon.
>
> Trev
I'm going to apply suggestions observed by Jeff and after that I'm going to send a new version of patchset.
Thanks,
Martin
>
>> +sem_item_optimizer::write_summary (void)
>> +{
>> + unsigned int count = 0;
>> +
>> + struct output_block *ob = create_output_block (LTO_section_ipa_icf);
>> + lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
>> + ob->cgraph_node = NULL;
>> +
>> + /* Calculate number of symbols to be serialized. */
>> + for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
>> + !lsei_end_p (lsei);
>> + lsei_next_in_partition (&lsei))
>> + {
>> + struct symtab_node *node = lsei_node (lsei);
>> +
>> + if (symtab_node_map.contains (node))
>> + count++;
>> + }
>> +
>> + streamer_write_uhwi (ob, count);
>> +
>> + /* Process all of the symbols. */
>> + for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
>> + !lsei_end_p (lsei);
>> + lsei_next_in_partition (&lsei))
>> + {
>> + struct symtab_node *node = lsei_node (lsei);
>> +
>> + sem_item **item = symtab_node_map.contains (node);
>> +
>> + if (item && *item)
>> + {
>> + int node_ref = lto_symtab_encoder_encode (encoder, node);
>> + streamer_write_uhwi_stream (ob->main_stream, node_ref);
>> +
>> + streamer_write_uhwi (ob, (*item)->get_hash ());
>> + }
>> + }
>> +
>> + streamer_write_char_stream (ob->main_stream, 0);
>> + produce_asm (ob, NULL);
>> + destroy_output_block (ob);
>> +}
>> +
>> +/* Reads a section from LTO stream file FILE_DATA. Input block for DATA
>> + contains LEN bytes. */
>> +
>> +void
>> +sem_item_optimizer::read_section (struct lto_file_decl_data *file_data,
>> + const char *data, size_t len)
>> +{
>> + const struct lto_function_header *header =
>> + (const struct lto_function_header *) data;
>> + const int cfg_offset = sizeof (struct lto_function_header);
>> + const int main_offset = cfg_offset + header->cfg_size;
>> + const int string_offset = main_offset + header->main_size;
>> + struct data_in *data_in;
>> + struct lto_input_block ib_main;
>> + unsigned int i;
>> + unsigned int count;
>> +
>> + LTO_INIT_INPUT_BLOCK (ib_main, (const char *) data + main_offset, 0,
>> + header->main_size);
>> +
>> + data_in =
>> + lto_data_in_create (file_data, (const char *) data + string_offset,
>> + header->string_size, vNULL);
>> +
>> + count = streamer_read_uhwi (&ib_main);
>> +
>> + for (i = 0; i < count; i++)
>> + {
>> + unsigned int index;
>> + struct symtab_node *node;
>> + lto_symtab_encoder_t encoder;
>> +
>> + index = streamer_read_uhwi (&ib_main);
>> + encoder = file_data->symtab_node_encoder;
>> + node = lto_symtab_encoder_deref (encoder, index);
>> +
>> + hashval_t hash = streamer_read_uhwi (&ib_main);
>> +
>> + gcc_assert (node->definition);
>> +
>> + if (dump_file)
>> + fprintf (dump_file, "Symbol added:%s (tree: %p, uid:%u)\n", node->asm_name (),
>> + (void *) node->decl, node->order);
>> +
>> + if (is_a_helper<cgraph_node *>::test (node))
>> + {
>> + cgraph_node *cnode = cgraph (node);
>> +
>> + items.safe_push (new sem_function (cnode, hash, &bmstack));
>> + }
>> + else
>> + {
>> + varpool_node *vnode = varpool (node);
>> +
>> + items.safe_push (new sem_variable (vnode, hash, &bmstack));
>> + }
>> + }
>> +
>> + lto_free_section_data (file_data, LTO_section_ipa_icf, NULL, data,
>> + len);
>> + lto_data_in_delete (data_in);
>> +}
>> +
>> +/* Read IPA IPA ICF summary for symbols. */
>> +
>> +void
>> +sem_item_optimizer::read_summary (void)
>> +{
>> + struct lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
>> + struct lto_file_decl_data *file_data;
>> + unsigned int j = 0;
>> +
>> + while ((file_data = file_data_vec[j++]))
>> + {
>> + size_t len;
>> + const char *data = lto_get_section_data (file_data,
>> + LTO_section_ipa_icf, NULL, &len);
>> +
>> + if (data)
>> + read_section (file_data, data, len);
>> + }
>> +}
>> +
>> +/* Register callgraph and varpool hooks. */
>> +
>> +void
>> +sem_item_optimizer::register_hooks (void)
>> +{
>> + cgraph_node_hooks = cgraph_add_node_removal_hook (
>> + &sem_item_optimizer::cgraph_removal_hook, this);
>> +
>> + varpool_node_hooks = varpool_add_node_removal_hook (
>> + &sem_item_optimizer::varpool_removal_hook, this);
>> +}
>> +
>> +/* Unregister callgraph and varpool hooks. */
>> +
>> +void
>> +sem_item_optimizer::unregister_hooks (void)
>> +{
>> + if (cgraph_node_hooks)
>> + cgraph_remove_node_removal_hook (cgraph_node_hooks);
>> +
>> + if (varpool_node_hooks)
>> + varpool_remove_node_removal_hook (varpool_node_hooks);
>> +}
>> +
>> +/* Adds a CLS to hashtable associated by hash value. */
>> +
>> +void
>> +sem_item_optimizer::add_class (congruence_class *cls)
>> +{
>> + gcc_assert (cls->members.length ());
>> +
>> + congruence_class_group_t *group = get_group_by_hash (
>> + cls->members[0]->get_hash ());
>> + group->classes.safe_push (cls);
>> +}
>> +
>> +/* Gets a congruence class group based on given HASH value. */
>> +
>> +congruence_class_group_t *
>> +sem_item_optimizer::get_group_by_hash (hashval_t hash)
>> +{
>> + congruence_class_group_t *item = XNEW (congruence_class_group_t);
>> + item->hash = hash;
>> +
>> + congruence_class_group **slot = classes.find_slot (item, INSERT);
>> +
>> + if (*slot)
>> + free (item);
>> + else
>> + {
>> + item->classes.create (1);
>> + *slot = item;
>> + }
>> +
>> + return *slot;
>> +}
>> +
>> +/* Callgraph removal hook called for a NODE with a custom DATA. */
>> +
>> +void
>> +sem_item_optimizer::cgraph_removal_hook (struct cgraph_node *node, void *data)
>> +{
>> + sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
>> + optimizer->remove_symtab_node (node);
>> +}
>> +
>> +/* Varpool removal hook called for a NODE with a custom DATA. */
>> +
>> +void
>> +sem_item_optimizer::varpool_removal_hook (struct varpool_node *node, void *data)
>> +{
>> + sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
>> + optimizer->remove_symtab_node (node);
>> +}
>> +
>> +/* Remove symtab NODE triggered by symtab removal hooks. */
>> +
>> +void
>> +sem_item_optimizer::remove_symtab_node (struct symtab_node *node)
>> +{
>> + gcc_assert (!classes.elements());
>> +
>> + pointer_set_insert (removed_items_set, node);
>> +}
>> +
>> +/* Removes all callgraph and varpool nodes that are marked by symtab
>> + as deleted. */
>> +
>> +void
>> +sem_item_optimizer::filter_removed_items (void)
>> +{
>> + vec <sem_item *> filtered;
>> + filtered.create (items.length());
>> +
>> + for (unsigned int i = 0; i < items.length(); i++)
>> + {
>> + sem_item *item = items[i];
>> +
>> + bool no_body_function = false;
>> +
>> + if (item->type == FUNC)
>> + {
>> + struct cgraph_node *cnode = static_cast <sem_function *>(item)->get_node ();
>> +
>> + no_body_function = in_lto_p && (cnode->alias || cnode->body_removed);
>> + }
>> +
>> + if(!pointer_set_contains (removed_items_set, items[i]->node)
>> + && !no_body_function)
>> + filtered.safe_push (items[i]);
>> + }
>> + items.release ();
>> +
>> + for (unsigned int i = 0; i < filtered.length(); i++)
>> + items.safe_push (filtered[i]);
>> +}
>> +
>> +/* Optimizer entry point. */
>> +
>> +void
>> +sem_item_optimizer::execute (void)
>> +{
>> + filter_removed_items ();
>> + build_hash_based_classes ();
>> +
>> + if (dump_file)
>> + fprintf (dump_file, "Dump after hash based groups\n");
>> + dump_cong_classes ();
>> +
>> + for (unsigned int i = 0; i < items.length(); i++)
>> + items[i]->init_wpa ();
>> +
>> + subdivide_classes_by_equality (true);
>> +
>> + if (dump_file)
>> + fprintf (dump_file, "Dump after WPA based types groups\n");
>> + dump_cong_classes ();
>> +
>> + parse_nonsingleton_classes ();
>> + subdivide_classes_by_equality ();
>> +
>> + if (dump_file)
>> + fprintf (dump_file, "Dump after full equality comparison of groups\n");
>> +
>> + dump_cong_classes ();
>> +
>> + unsigned int prev_class_count = classes_count;
>> +
>> + process_cong_reduction ();
>> + dump_cong_classes ();
>> + merge_classes (prev_class_count);
>> +
>> + if (dump_file && (dump_flags & TDF_DETAILS))
>> + dump_symtab (dump_file);
>> +}
>> +
>> +/* Function responsible for visiting all potential functions and
>> + read-only variables that can be merged. */
>> +
>> +void
>> +sem_item_optimizer::parse_funcs_and_vars (void)
>> +{
>> + struct cgraph_node *cnode;
>> + sem_item **slot;
>> +
>> + FOR_EACH_DEFINED_FUNCTION (cnode)
>> + {
>> + sem_function *f = sem_function::parse (cnode, &bmstack);
>> + if (f)
>> + {
>> + items.safe_push (f);
>> + slot = symtab_node_map.insert (cnode);
>> + *slot = f;
>> +
>> + if (dump_file)
>> + fprintf (dump_file, "Parsed function:%s\n", f->asm_name ());
>> +
>> + if (dump_file && (dump_flags & TDF_DETAILS))
>> + f->dump_to_file (dump_file);
>> + }
>> + else if (dump_file)
>> + fprintf (dump_file, "Not parsed function:%s\n", cnode->asm_name ());
>> + }
>> +
>> + varpool_node *vnode;
>> +
>> + FOR_EACH_DEFINED_VARIABLE (vnode)
>> + {
>> + sem_variable *v = sem_variable::parse (vnode, &bmstack);
>> +
>> + if (v)
>> + {
>> + items.safe_push (v);
>> + slot = symtab_node_map.insert (vnode);
>> + *slot = v;
>> + }
>> + }
>> +}
>> +
>> +/* Makes pairing between a congruence class CLS and semantic ITEM. */
>> +
>> +void
>> +sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
>> +{
>> + item->index_in_class = cls->members.length ();
>> + cls->members.safe_push (item);
>> + item->cls = cls;
>> +}
>> +
>> +/* Congruence classes are built by hash value. */
>> +
>> +void
>> +sem_item_optimizer::build_hash_based_classes (void)
>> +{
>> + for (unsigned i = 0; i < items.length (); i++)
>> + {
>> + sem_item *item = items[i];
>> +
>> + congruence_class_group_t *group = get_group_by_hash (item->get_hash ());
>> +
>> + if (!group->classes.length ())
>> + {
>> + classes_count++;
>> + group->classes.safe_push (new congruence_class (class_id++));
>> + }
>> +
>> + add_item_to_class (group->classes[0], item);
>> + }
>> +}
>> +
>> +/* Semantic items in classes having more than one element and initialized.
>> + In case of WPA, we load function body. */
>> +
>> +void
>> +sem_item_optimizer::parse_nonsingleton_classes (void)
>> +{
>> + for (hash_table <congruence_class_group_hash>::iterator it = classes.begin ();
>> + it != classes.end (); ++it)
>> + {
>> + for (unsigned i = 0; i < (*it).classes.length (); i++)
>> + {
>> + congruence_class *c = (*it).classes [i];
>> +
>> + if (c->members.length() > 1)
>> + for (unsigned j = 0; j < c->members.length (); j++)
>> + {
>> + sem_item *item = c->members[j];
>> + sem_item **slot;
>> +
>> + slot = decl_map.insert (item->decl);
>> + *slot = item;
>> +
>> + }
>> + }
>> + }
>> +
>> + unsigned int init_called_count = 0;
>> +
>> + for (hash_table <congruence_class_group_hash>::iterator it = classes.begin ();
>> + it != classes.end (); ++it)
>> + {
>> + /* We fill in all declarations for sem_items. */
>> + for (unsigned i = 0; i < (*it).classes.length (); i++)
>> + {
>> + congruence_class *c = (*it).classes [i];
>> +
>> + if (c->members.length() > 1)
>> + for (unsigned j = 0; j < c->members.length (); j++)
>> + {
>> + sem_item *item = c->members[j];
>> +
>> + item->init ();
>> + item->init_refs ();
>> + init_called_count++;
>> +
>> + for (unsigned j = 0; j < item->tree_refs.length (); j++)
>> + {
>> + sem_item **result = decl_map.contains (item->tree_refs[j]);
>> +
>> + if(result)
>> + {
>> + sem_item *target = *result;
>> + item->refs.safe_push (target);
>> +
>> + unsigned index = item->refs.length ();
>> + target->usages.safe_push (new sem_usage_pair(item, index));
>> + bitmap_set_bit (target->usage_index_bitmap, index);
>> + pointer_set_insert (item->tree_refs_set, item->tree_refs[j]);
>> + }
>> + }
>> + }
>> + }
>> + }
>> +
>> + if (dump_file)
>> + fprintf (dump_file, "Init called for %u items (%.2f%%).\n", init_called_count,
>> + 100.0f * init_called_count / items.length ());
>> +}
>> +
>> +/* Equality function for semantic items is used to subdivide existing
>> + classes. If IN_WPA, fast equality function is invoked. */
>> +
>> +void
>> +sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa)
>> +{
>> + for (hash_table <congruence_class_group_hash>::iterator it = classes.begin ();
>> + it != classes.end (); ++it)
>> + {
>> + unsigned int class_count = (*it).classes.length ();
>> +
>> + for (unsigned i = 0; i < class_count; i++)
>> + {
>> + congruence_class *c = (*it).classes [i];
>> +
>> + if (c->members.length() > 1)
>> + {
>> + vec <sem_item *> new_vector;
>> + new_vector.create (c->members.length ());
>> +
>> + sem_item *first = c->members[0];
>> + new_vector.safe_push (first);
>> +
>> + unsigned class_split_first = (*it).classes.length ();
>> +
>> + for (unsigned j = 1; j < c->members.length (); j++)
>> + {
>> + sem_item *item = c->members[j];
>> +
>> + bool equals = in_wpa ? first->equals_wpa (item) : first->equals (item);
>> +
>> + if (equals)
>> + new_vector.safe_push (item);
>> + else
>> + {
>> + bool integrated = false;
>> +
>> + for (unsigned k = class_split_first; k < (*it).classes.length (); k++)
>> + {
>> + sem_item *x = (*it).classes[k]->members[0];
>> + bool equals = in_wpa ? x->equals_wpa (item) : x->equals (item);
>> +
>> + if (equals)
>> + {
>> + integrated = true;
>> + add_item_to_class ((*it).classes[k], item);
>> +
>> + break;
>> + }
>> + }
>> +
>> + if (!integrated)
>> + {
>> + congruence_class *c = new congruence_class (class_id++);
>> + classes_count++;
>> + add_item_to_class (c, item);
>> +
>> + (*it).classes.safe_push (c);
>> + }
>> + }
>> + }
>> +
>> + // we replace newly created new_vector for the class we've just splitted
>> + c->members.release ();
>> + c->members.create (new_vector.length ());
>> +
>> + for (unsigned int j = 0; j < new_vector.length (); j++)
>> + add_item_to_class (c, new_vector[j]);
>> + }
>> + }
>> + }
>> +
>> + verify_classes ();
>> +}
>> +
>> +/* Verify congruence classes if checking is enabled. */
>> +
>> +void
>> +sem_item_optimizer::verify_classes (void)
>> +{
>> +#if ENABLE_CHECKING
>> + for (hash_table <congruence_class_group_hash>::iterator it = classes.begin ();
>> + it != classes.end (); ++it)
>> + {
>> + for (unsigned int i = 0; i < (*it).classes.length (); i++)
>> + {
>> + congruence_class *cls = (*it).classes[i];
>> +
>> + gcc_checking_assert (cls);
>> + gcc_checking_assert (cls->members.length () > 0);
>> +
>> + for (unsigned int j = 0; j < cls->members.length (); j++)
>> + {
>> + sem_item *item = cls->members[j];
>> +
>> + gcc_checking_assert (item);
>> +
>> + for (unsigned k = 0; k < item->usages.length (); k++)
>> + {
>> + sem_usage_pair *usage = item->usages[k];
>> + gcc_checking_assert (usage->item->index_in_class <
>> + usage->item->cls->members.length ());
>> + }
>> + }
>> + }
>> + }
>> +#endif
>> +}
>> +
>> +/* Disposes split map traverse function. CLS_PTR is pointer to congruence
>> + class, BSLOT is bitmap slot we want to release. DATA is mandatory,
>> + but unused argument. */
>> +
>> +bool
>> +sem_item_optimizer::release_split_map (__attribute__((__unused__)) const void
>> + *cls_ptr,
>> + __attribute__((__unused__)) bitmap *bslot,
>> + __attribute__((__unused__)) void *data)
>> +{
>> + bitmap b = *bslot;
>> +
>> + BITMAP_FREE (b);
>> +
>> + return true;
>> +}
>> +
>> +/* Process split operation for a class given as pointer CLS_PTR,
>> + where bitmap B splits congruence class members. DATA is used
>> + as argument of split pair. */
>> +
>> +bool
>> +sem_item_optimizer::traverse_congruence_split (const void *cls_ptr,
>> + bitmap *bslot, void *data)
>> +{
>> + const congruence_class *cls = (const congruence_class *) cls_ptr;
>> + bitmap b = *bslot;
>> +
>> + traverse_split_pair *pair = (traverse_split_pair *) data;
>> + sem_item_optimizer *optimizer = pair->optimizer;
>> + const congruence_class *splitter_cls = pair->cls;
>> +
>> + /* If counted bits are greater than zero and less than the number of members
>> + a group will be splitted. */
>> + unsigned popcount = bitmap_count_bits (b);
>> +
>> + if (popcount > 0 && popcount < cls->members.length ())
>> + {
>> + congruence_class* newclasses[2] = { new congruence_class (class_id++), new congruence_class (class_id++) };
>> +
>> + for (unsigned int i = 0; i < cls->members.length (); i++)
>> + {
>> + int target = bitmap_bit_p (b, i);
>> + congruence_class *tc = newclasses[target];
>> +
>> + add_item_to_class (tc, cls->members[i]);
>> + }
>> +
>> +#ifdef ENABLE_CHECKING
>> + for (unsigned int i = 0; i < 2; i++)
>> + gcc_checking_assert (newclasses[i]->members.length ());
>> +#endif
>> +
>> + if (splitter_cls == cls)
>> + optimizer->splitter_class_removed = true;
>> +
>> + /* Remove old class from worklist if presented. */
>> + bool in_work_list = optimizer->worklist_contains (cls);
>> +
>> + if (in_work_list)
>> + optimizer->worklist_remove (cls);
>> +
>> + for (hash_table <congruence_class_group_hash>::iterator it =
>> + optimizer->classes.begin (); it != optimizer->classes.end (); ++it)
>> + {
>> + for (unsigned int i = 0; i < (*it).classes.length (); i++)
>> + if ((*it).classes[i] == cls)
>> + {
>> + (*it).classes.ordered_remove (i);
>> + break;
>> + }
>> + }
>> + /* New class will be inserted and integrated to work list. */
>> + for (unsigned int i = 0; i < 2; i++)
>> + optimizer->add_class (newclasses[i]);
>> +
>> + /* Two classes replace one, so that increment just by one. */
>> + optimizer->classes_count++;
>> +
>> + /* If OLD class was presented in the worklist, we remove the class
>> + are replace it will both newly created classes. */
>> + if (in_work_list)
>> + for (unsigned int i = 0; i < 2; i++)
>> + optimizer->worklist_push (newclasses[i]);
>> + else /* Just smaller class is inserted. */
>> + {
>> + unsigned int smaller_index = newclasses[0]->members.length () <
>> + newclasses[1]->members.length () ?
>> + 0 : 1;
>> + optimizer->worklist_push (newclasses[smaller_index]);
>> + }
>> +
>> + if (dump_file && (dump_flags & TDF_DETAILS))
>> + {
>> + fprintf (dump_file, " congruence class splitted:\n");
>> + cls->dump (dump_file, 4);
>> +
>> + fprintf (dump_file, " newly created groups:\n");
>> + for (unsigned int i = 0; i < 2; i++)
>> + newclasses[i]->dump (dump_file, 4);
>> + }
>> +
>> + delete cls;
>> + }
>> +
>> +
>> + return true;
>> +}
>> +
>> +/* Tests if a class CLS used as INDEXth splits any congruence classes.
>> + Bitmap stack BMSTACK is used for bitmap allocation. */
>> +
>> +void
>> +sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls,
>> + unsigned int index)
>> +{
>> + /* Split map reset */
>> + if (split_map != NULL)
>> + delete split_map;
>> +
>> + pointer_map <bitmap> *split_map = new pointer_map <bitmap> ();
>> +
>> + for (unsigned int i = 0; i < cls->members.length (); i++)
>> + {
>> + sem_item *item = cls->members[i];
>> +
>> + /* Iterate all usages that have INDEX as usage of the item. */
>> + for (unsigned int j = 0; j < item->usages.length (); j++)
>> + {
>> + sem_usage_pair *usage = item->usages[j];
>> +
>> + if (usage->index != index)
>> + continue;
>> +
>> + bitmap *slot = split_map->contains (usage->item->cls);
>> +
>> + if(!slot)
>> + {
>> + slot = split_map->insert (usage->item->cls);
>> + *slot = BITMAP_ALLOC (&bmstack);
>> + }
>> +
>> + bitmap b = *slot;
>> +
>> +#if ENABLE_CHECKING
>> + gcc_checking_assert (usage->item->cls);
>> + gcc_checking_assert (usage->item->index_in_class <
>> + usage->item->cls->members.length ());
>> +#endif
>> +
>> + bitmap_set_bit (b, usage->item->index_in_class);
>> + }
>> + }
>> +
>> + traverse_split_pair pair;
>> + pair.optimizer = this;
>> + pair.cls = cls;
>> +
>> + splitter_class_removed = false;
>> + split_map->traverse (&sem_item_optimizer::traverse_congruence_split, &pair);
>> +
>> + /* Bitmap clean-up. */
>> + split_map->traverse (&sem_item_optimizer::release_split_map, NULL);
>> +}
>> +
>> +/* Every usage of a congruence class CLS is a candidate that can split the
>> + collection of classes. Bitmap stack BMSTACK is used for bitmap
>> + allocation. */
>> +
>> +void
>> +sem_item_optimizer::do_congruence_step (congruence_class *cls)
>> +{
>> + bitmap_iterator bi;
>> + unsigned int i;
>> +
>> + bitmap usage = BITMAP_ALLOC (&bmstack);
>> +
>> + for (unsigned int i = 0; i < cls->members.length (); i++)
>> + bitmap_ior_into (usage, cls->members[i]->usage_index_bitmap);
>> +
>> + EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi)
>> + {
>> + if (dump_file && (dump_flags & TDF_DETAILS))
>> + fprintf (dump_file, " processing congruece step for class: %u, index: %u\n",
>> + cls->id, i);
>> +
>> + do_congruence_step_for_index (cls, i);
>> +
>> + if (splitter_class_removed)
>> + break;
>> + }
>> +
>> + BITMAP_FREE (usage);
>> +}
>> +
>> +/* Adds a newly created congruence class CLS to worklist. */
>> +
>> +void
>> +sem_item_optimizer::worklist_push (congruence_class *cls)
>> +{
>> + congruence_class **slot = worklist.find_slot (cls, INSERT);
>> +
>> + if (*slot)
>> + return;
>> +
>> + *slot = cls;
>> +}
>> +
>> +/* Pops a class from worklist. */
>> +
>> +congruence_class *
>> +sem_item_optimizer::worklist_pop (void)
>> +{
>> + gcc_assert (worklist.elements ());
>> +
>> + congruence_class *cls = &(*worklist.begin ());
>> + worklist.remove_elt (cls);
>> +
>> + return cls;
>> +}
>> +
>> +/* Returns true if a congruence class CLS is presented in worklist. */
>> +
>> +bool
>> +sem_item_optimizer::worklist_contains (const congruence_class *cls)
>> +{
>> + return worklist.find (cls);
>> +}
>> +
>> +/* Removes given congruence class CLS from worklist. */
>> +
>> +void
>> +sem_item_optimizer::worklist_remove (const congruence_class *cls)
>> +{
>> + worklist.remove_elt (cls);
>> +}
>> +
>> +/* Iterative congruence reduction function. */
>> +
>> +void
>> +sem_item_optimizer::process_cong_reduction (void)
>> +{
>> + for (hash_table<congruence_class_group_hash>::iterator it = classes.begin ();
>> + it != classes.end (); ++it)
>> + for (unsigned i = 0; i < (*it).classes.length (); i++)
>> + if ((*it).classes[i]->is_class_used ())
>> + worklist_push ((*it).classes[i]);
>> +
>> + if (dump_file)
>> + fprintf (dump_file, "Worklist has been filled with: %lu\n",
>> + worklist.elements ());
>> +
>> + if (dump_file && (dump_flags & TDF_DETAILS))
>> + fprintf (dump_file, "Congruence class reduction\n");
>> +
>> + while (worklist.elements ())
>> + {
>> + congruence_class *cls = worklist_pop ();
>> + do_congruence_step (cls);
>> + }
>> +}
>> +
>> +/* Debug function prints all informations about congruence classes. */
>> +
>> +void
>> +sem_item_optimizer::dump_cong_classes (void)
>> +{
>> + if (!dump_file)
>> + return;
>> +
>> + fprintf (dump_file,
>> + "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
>> + classes_count, classes.elements(), items.length ());
>> +
>> + /* Histogram calculation. */
>> + unsigned int max_index = 0;
>> + unsigned int* histogram = XCNEWVEC (unsigned int, items.length ());
>> +
>> + for (hash_table<congruence_class_group_hash>::iterator it = classes.begin ();
>> + it != classes.end (); ++it)
>> +
>> + for (unsigned i = 0; i < (*it).classes.length (); i++)
>> + {
>> + unsigned int c = (*it).classes[i]->members.length ();
>> + histogram[c]++;
>> +
>> + if (c > max_index)
>> + max_index = c;
>> + }
>> +
>> + fprintf (dump_file,
>> + "Class size histogram [num of members]: number of classe number of classess\n");
>> +
>> + for (unsigned int i = 0; i <= max_index; i++)
>> + if (histogram[i])
>> + fprintf (dump_file, "[%u]: %u classes\n", i, histogram[i]);
>> +
>> + fprintf (dump_file, "\n\n");
>> +
>> +
>> + if (dump_flags & TDF_DETAILS)
>> + for (hash_table<congruence_class_group_hash>::iterator it = classes.begin ();
>> + it != classes.end (); ++it)
>> + {
>> + fprintf (dump_file, " group: with %u classes:\n", (*it).classes.length ());
>> +
>> + for (unsigned i = 0; i < (*it).classes.length (); i++)
>> + {
>> + (*it).classes[i]->dump (dump_file, 4);
>> +
>> + if(i < (*it).classes.length () - 1)
>> + fprintf (dump_file, " ");
>> + }
>> + }
>> +
>> + free (histogram);
>> +}
>> +
>> +/* After reduction is done, we can declare all items in a group
>> + to be equal. PREV_CLASS_COUNT is start number of classes
>> + before reduction. */
>> +
>> +void
>> +sem_item_optimizer::merge_classes (unsigned int prev_class_count)
>> +{
>> + unsigned int item_count = items.length ();
>> + unsigned int class_count = classes_count;
>> + unsigned int equal_items = item_count - class_count;
>> +
>> + if (dump_file)
>> + {
>> + fprintf (dump_file, "\nItem count: %u\n", item_count);
>> + fprintf (dump_file, "Congruent classes before: %u, after: %u\n",
>> + prev_class_count, class_count);
>> + fprintf (dump_file, "Average class size before: %.2f, after: %.2f\n",
>> + 1.0f * item_count / prev_class_count,
>> + 1.0f * item_count / class_count);
>> + fprintf (dump_file, "Equal symbols: %u\n", equal_items);
>> + fprintf (dump_file, "Fraction of visited symbols: %.2f%%\n\n",
>> + 100.0f * equal_items / item_count);
>> + }
>> +
>> + for (hash_table<congruence_class_group_hash>::iterator it = classes.begin ();
>> + it != classes.end (); ++it)
>> + for (unsigned int i = 0; i < (*it).classes.length (); i++)
>> + {
>> + congruence_class *c = (*it).classes[i];
>> +
>> + if (c->members.length () == 1)
>> + continue;
>> +
>> + gcc_assert (c->members.length ());
>> +
>> + sem_item *source = c->members[0];
>> +
>> + for (unsigned int j = 1; j < c->members.length (); j++)
>> + {
>> + sem_item *alias = c->members[j];
>> +
>> + if (dump_file)
>> + {
>> + fprintf (dump_file, "Semantic equality hit:%s->%s\n",
>> + source->name (), alias->name ());
>> + fprintf (dump_file, "Assembler symbol names:%s->%s\n",
>> + source->asm_name (), alias->asm_name ());
>> + }
>> +
>> + if (dump_file && (dump_flags & TDF_DETAILS))
>> + {
>> + source->dump_to_file (dump_file);
>> + alias->dump_to_file (dump_file);
>> + }
>> +
>> + source->merge (alias);
>> + }
>> + }
>> +}
>> +
>> +/* Dump function prints all class members to a FILE with an INDENT. */
>> +
>> +void
>> +congruence_class::dump (FILE *file, unsigned int indent) const
>> +{
>> + FPRINTF_SPACES (file, indent, "class with id: %u, hash: %u, items: %u\n",
>> + id, members[0]->get_hash (), members.length ());
>> +
>> + FPUTS_SPACES (file, indent + 2, "");
>> + for (unsigned i = 0; i < members.length (); i++)
>> + fprintf (file, "%s(%p/%u)", members[i]->asm_name (), (void *) members[i]->decl,
>> + members[i]->node->order);
>> +
>> + fprintf (file, "\n");
>> +}
>> +
>> +/* Returns true if there's a member that is used from another group. */
>> +
>> +bool
>> +congruence_class::is_class_used (void)
>> +{
>> + for (unsigned int i = 0; i < members.length (); i++)
>> + if (members[i]->usages.length ())
>> + return true;
>> +
>> + return false;
>> +}
>> +
>> +/* Initialization and computation of symtab node hash, there data
>> + are propagated later on. */
>> +
>> +static sem_item_optimizer optimizer;
>> +
>> +/* Generate pass summary for IPA ICF pass. */
>> +
>> +static void
>> +ipa_icf_generate_summary (void)
>> +{
>> + optimizer.parse_funcs_and_vars ();
>> +}
>> +
>> +/* Write pass summary for IPA ICF pass. */
>> +
>> +static void
>> +ipa_icf_write_summary (void)
>> +{
>> + optimizer.write_summary ();
>> +}
>> +
>> +/* Read pass summary for IPA ICF pass. */
>> +
>> +static void
>> +ipa_icf_read_summary (void)
>> +{
>> + optimizer.read_summary ();
>> + optimizer.register_hooks ();
>> +}
>> +
>> +/* Semantic equality exection function. */
>> +
>> +static unsigned int
>> +ipa_icf_driver (void)
>> +{
>> + optimizer.execute ();
>> + optimizer.unregister_hooks ();
>> +
>> + return 0;
>> +}
>> +
>> +const pass_data pass_data_ipa_icf =
>> +{
>> + IPA_PASS, /* type */
>> + "icf", /* name */
>> + OPTGROUP_IPA, /* optinfo_flags */
>> + true, /* has_execute */
>> + TV_IPA_ICF, /* tv_id */
>> + 0, /* properties_required */
>> + 0, /* properties_provided */
>> + 0, /* properties_destroyed */
>> + 0, /* todo_flags_start */
>> + 0, /* todo_flags_finish */
>> +};
>> +
>> +class pass_ipa_icf : public ipa_opt_pass_d
>> +{
>> +public:
>> + pass_ipa_icf (gcc::context *ctxt)
>> + : ipa_opt_pass_d (pass_data_ipa_icf, ctxt,
>> + ipa_icf_generate_summary, /* generate_summary */
>> + ipa_icf_write_summary, /* write_summary */
>> + ipa_icf_read_summary, /* read_summary */
>> + NULL, /*
>> + write_optimization_summary */
>> + NULL, /*
>> + read_optimization_summary */
>> + NULL, /* stmt_fixup */
>> + 0, /* function_transform_todo_flags_start */
>> + NULL, /* function_transform */
>> + NULL) /* variable_transform */
>> + {}
>> +
>> + /* opt_pass methods: */
>> + virtual bool gate (function *)
>> + {
>> + return flag_ipa_icf;
>> + }
>> +
>> + virtual unsigned int execute (function *)
>> + {
>> + return ipa_icf_driver();
>> + }
>> +}; // class pass_ipa_icf
>> +
>> +} // anon namespace
>> +
>> +ipa_opt_pass_d *
>> +make_pass_ipa_icf (gcc::context *ctxt)
>> +{
>> + return new pass_ipa_icf (ctxt);
>> +}
>> diff --git a/gcc/ipa-icf.h b/gcc/ipa-icf.h
>> new file mode 100644
>> index 0000000..dc5e971
>> --- /dev/null
>> +++ b/gcc/ipa-icf.h
>> @@ -0,0 +1,687 @@
>> +/* Interprocedural semantic function equality pass
>> + Copyright (C) 2014 Free Software Foundation, Inc.
>> +
>> + Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
>> +
>> +This file is part of GCC.
>> +
>> +GCC is free software; you can redistribute it and/or modify it under
>> +the terms of the GNU General Public License as published by the Free
>> +Software Foundation; either version 3, or (at your option) any later
>> +version.
>> +
>> +GCC is distributed in the hope that it will be useful, but WITHOUT ANY
>> +WARRANTY; without even the implied warranty of MERCHANTABILITY or
>> +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
>> +for more details.
>> +
>> +You should have received a copy of the GNU General Public License
>> +along with GCC; see the file COPYING3. If not see
>> +<http://www.gnu.org/licenses/>. */
>> +
>> +/* Prints string STRING to a FILE with a given number of SPACE_COUNT. */
>> +#define FPUTS_SPACES(file, space_count, string) \
>> + do \
>> + { \
>> + fprintf (file, "%*s" string, space_count, " "); \
>> + } \
>> + while (false);
>> +
>> +/* fprintf function wrapper that transforms given FORMAT to follow given
>> + number for SPACE_COUNT and call fprintf for a FILE. */
>> +#define FPRINTF_SPACES(file, space_count, format, ...) \
>> + fprintf (file, "%*s" format, space_count, " ", ##__VA_ARGS__);
>> +
>> +/* Prints a MESSAGE to dump_file if exists. */
>> +#define SE_DUMP_MESSAGE(message) \
>> + do \
>> + { \
>> + if (dump_file && (dump_flags & TDF_DETAILS)) \
>> + fprintf (dump_file, " debug message: %s (%s:%u)\n", message, __func__, __LINE__); \
>> + } \
>> + while (false);
>> +
>> +/* Logs a MESSAGE to dump_file if exists and returns false. */
>> +#define SE_EXIT_FALSE_WITH_MSG(message) \
>> + do \
>> + { \
>> + if (dump_file && (dump_flags & TDF_DETAILS)) \
>> + fprintf (dump_file, " false returned: '%s' (%s:%u)\n", message, __func__, __LINE__); \
>> + return false; \
>> + } \
>> + while (false);
>> +
>> +/* Return false and log that false value is returned. */
>> +#define SE_EXIT_FALSE() \
>> + SE_EXIT_FALSE_WITH_MSG("")
>> +
>> +/* Logs return value if RESULT is false. */
>> +#define SE_EXIT_DEBUG(result) \
>> + do \
>> + { \
>> + if (!(result) && dump_file && (dump_flags & TDF_DETAILS)) \
>> + fprintf (dump_file, " false returned (%s:%u)\n", __func__, __LINE__); \
>> + return result; \
>> + } \
>> + while (false);
>> +
>> +/* Verbose logging function logging statements S1 and S2 of a CODE. */
>> +#define SE_DIFF_STATEMENT(s1, s2, code) \
>> + do \
>> + { \
>> + if (dump_file && (dump_flags & TDF_DETAILS)) \
>> + { \
>> + fprintf (dump_file, " different statement for code: %s:\n", code); \
>> + print_gimple_stmt (dump_file, s1, 3, TDF_DETAILS); \
>> + print_gimple_stmt (dump_file, s2, 3, TDF_DETAILS); \
>> + } \
>> + return false; \
>> + } \
>> + while (false);
>> +
>> +namespace {
>> +
>> +/* Forward declaration for sem_func class. */
>> +class sem_item;
>> +
>> +/* A class aggregating all connections and semantic equivalents
>> + for a given pair of semantic function candidates. */
>> +class func_checker
>> +{
>> +public:
>> + func_checker ();
>> +
>> + /* Initializes internal structures according to given number of
>> + source and target SSA names. The number of source names is SSA_SOURCE,
>> + respectively SSA_TARGET. */
>> + void initialize (unsigned ssa_source, unsigned sss_target);
>> +
>> + /* Memory release routine. */
>> + void release (void);
>> +
>> + /* Verifies that trees T1 and T2 do correspond. */
>> + bool compare_ssa_name (tree t1, tree t2);
>> +
>> + /* Verification function for edges E1 and E2. */
>> + bool compare_edge (edge e1, edge e2);
>> +
>> + /* Verification function for declaration trees T1 and T2 that
>> + come from functions FUNC1 and FUNC2. */
>> + bool compare_decl (tree t1, tree t2, tree func1, tree func2);
>> +
>> +private:
>> + /* Vector mapping source SSA names to target ones. */
>> + vec <int> source_ssa_names;
>> +
>> + /* Vector mapping target SSA names to source ones. */
>> + vec <int> target_ssa_names;
>> +
>> + /* Source to target edge map. */
>> + pointer_map <edge> *edge_map;
>> +
>> + /* Source to target declaration map. */
>> + pointer_map <tree> *decl_map;
>> +
>> + /* Flag that indicates if the checker is initialize. */
>> + bool initialized;
>> +};
>> +
>> +/* Congruence class encompasses a collection of either functions or
>> + read-only variables. These items are considered to be equivalent
>> + if not proved the oposite. */
>> +class congruence_class
>> +{
>> +public:
>> + /* Congruence class constructor for a new class with _ID. */
>> + congruence_class (unsigned int _id);
>> +
>> + /* Dump function prints all class members to a FILE with an INDENT. */
>> + void dump (FILE *file, unsigned int indent = 0) const;
>> +
>> + /* Returns true if there's a member that is used from another group. */
>> + bool is_class_used (void);
>> +
>> + /* Vector of all group members. */
>> + vec <sem_item *> members;
>> +
>> + /* Global unique class identifier. */
>> + unsigned int id;
>> +};
>> +
>> +/* Semantic item type enum. */
>> +enum sem_item_type
>> +{
>> + FUNC,
>> + VAR
>> +};
>> +
>> +/* Semantic item usage pair. */
>> +class sem_usage_pair
>> +{
>> +public:
>> + /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
>> + sem_usage_pair (sem_item *_item, unsigned int _index);
>> +
>> + /* Target semantic item where an item is used. */
>> + sem_item *item;
>> +
>> + /* Index of usage of such an item. */
>> + unsigned int index;
>> +};
>> +
>> +/* Basic block struct for sematic equality pass. */
>> +typedef struct sem_bb
>> +{
>> + /* Basic block the structure belongs to. */
>> + basic_block bb;
>> +
>> + /* Number of non-debug statements in the basic block. */
>> + unsigned nondbg_stmt_count;
>> +
>> + /* Number of edges connected to the block. */
>> + unsigned edge_count;
>> +} sem_bb_t;
>> +
>> +/* Semantic item is a base class that encapsulates all shared functionality
>> + for both semantic function and variable items. */
>> +class sem_item
>> +{
>> +public:
>> + /* Semantic item constructor for a node of _TYPE, where STACK is used
>> + for bitmap memory allocation. */
>> + sem_item (enum sem_item_type _type, bitmap_obstack *stack);
>> +
>> + /* Semantic item constructor for a node of _TYPE, where STACK is used
>> + for bitmap memory allocation. The item is based on symtab node _NODE
>> + with computed _HASH. */
>> + sem_item (enum sem_item_type _type, struct symtab_node *_node, hashval_t _hash,
>> + bitmap_obstack *stack);
>> +
>> + virtual ~sem_item ();
>> +
>> + /* Dump function for debugging purpose. */
>> + DEBUG_FUNCTION void dump (void);
>> +
>> + /* Initialize semantic item by info reachable during LTO WPA phase. */
>> + virtual void init_wpa (void) = 0;
>> +
>> + /* Semantic item initialization function. */
>> + virtual void init (void) = 0;
>> +
>> + /* Gets symbol name of the item. */
>> + virtual const char *name (void) = 0;
>> +
>> + /* Gets assembler name of the item. */
>> + virtual const char *asm_name (void) = 0;
>> +
>> + /* Initializes references to other semantic functions/variables. */
>> + virtual void init_refs () = 0;
>> +
>> + /* Fast equality function based on knowledge known in WPA. */
>> + virtual bool equals_wpa (sem_item *item) = 0;
>> +
>> + /* Returns true if the item equals to ITEM given as arguemnt. */
>> + virtual bool equals (sem_item *item) = 0;
>> +
>> + /* References independent hash function. */
>> + virtual hashval_t get_hash (void) = 0;
>> +
>> + /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
>> + be applied. */
>> + virtual bool merge (sem_item *alias_item) = 0;
>> +
>> + /* Dump symbol to FILE. */
>> + virtual void dump_to_file (FILE *file) = 0;
>> +
>> + /* Compare two types if are same aliases in case of strict aliasing
>> + is enabled. */
>> + static bool compare_for_aliasing (tree t1, tree t2);
>> +
>> + /* Item type. */
>> + enum sem_item_type type;
>> +
>> + /* Global unique function index. */
>> + unsigned int index;
>> +
>> + /* Symtab node. */
>> + struct symtab_node *node;
>> +
>> + /* Declaration tree node. */
>> + tree decl;
>> +
>> + /* Semantic references used that generate congruence groups. */
>> + vec <sem_item *> refs;
>> +
>> + /* Pointer to a congruence class the item belongs to. */
>> + congruence_class *cls;
>> +
>> + /* Index of the item in a class belonging to. */
>> + unsigned int index_in_class;
>> +
>> + /* List of semantic items where the instance is used. */
>> + vec <sem_usage_pair *> usages;
>> +
>> + /* A bitmap with indices of all classes referencing this item. */
>> + bitmap usage_index_bitmap;
>> +
>> + /* List of tree references (either FUNC_DECL or VAR_DECL). */
>> + vec <tree> tree_refs;
>> +
>> + /* A set with tree references (either FUNC_DECL or VAR_DECL). */
>> + pointer_set_t *tree_refs_set;
>> +
>> +protected:
>> + /* Cached, once calculated hash for the item. */
>> + hashval_t hash;
>> +
>> +private:
>> + /* Initialize internal data structures. Bitmap STACK is used for
>> + bitmap memory allocation process. */
>> + void setup (bitmap_obstack *stack);
>> +}; // class sem_item
>> +
>> +class sem_function: public sem_item
>> +{
>> +public:
>> + /* Semantic function constructor that uses STACK as bitmap memory stack. */
>> + sem_function (bitmap_obstack *stack);
>> +
>> + /* Constructor based on callgraph node _NODE with computed hash _HASH.
>> + Bitmap STACK is used for memory allocation. */
>> + sem_function (cgraph_node *_node, hashval_t _hash, bitmap_obstack *stack);
>> +
>> + ~sem_function ();
>> +
>> + virtual void init_wpa (void);
>> + virtual void init (void);
>> + virtual const char *name (void);
>> + virtual const char *asm_name (void);
>> + virtual hashval_t get_hash (void);
>> + virtual bool equals_wpa (sem_item *item);
>> + virtual bool equals (sem_item *item);
>> + virtual void init_refs ();
>> + virtual bool merge (sem_item *alias_item);
>> + virtual void dump_to_file (FILE *file);
>> +
>> + /* Parses function arguments and result type. */
>> + void parse_tree_args (void);
>> +
>> + /* Returns cgraph_node. */
>> + struct cgraph_node *get_node (void);
>> +
>> + /* For a given call graph NODE, the function constructs new
>> + semantic function item. */
>> + static sem_function *parse (struct cgraph_node *node, bitmap_obstack *stack);
>> +
>> + /* Exception handling region tree. */
>> + eh_region region_tree;
>> +
>> + /* Result type tree node. */
>> + tree result_type;
>> +
>> + /* Array of argument tree types. */
>> + vec <tree> arg_types;
>> +
>> + /* Number of function arguments. */
>> + unsigned int arg_count;
>> +
>> + /* Basic block count. */
>> + unsigned int bb_count;
>> +
>> + /* Total amount of edges in the function. */
>> + unsigned int edge_count;
>> +
>> + /* Array of sizes of all basic blocks. */
>> + unsigned int *bb_sizes;
>> +
>> + /* Control flow graph checksum. */
>> + hashval_t cfg_checksum;
>> +
>> + /* GIMPLE codes hash value. */
>> + hashval_t gcode_hash;
>> +
>> + /* Total number of SSA names used in the function. */
>> + unsigned ssa_names_size;
>> +
>> + /* Array of structures for all basic blocks. */
>> + sem_bb_t **bb_sorted;
>> +
>> +private:
>> + /* Calculates hash value based on a BASIC_BLOCK. */
>> + hashval_t get_bb_hash (const sem_bb_t *basic_block);
>> +
>> + /* Basic block equivalence comparison function that returns true if
>> + basic blocks BB1 and BB2 (from functions FUNC1 and FUNC2) correspond. */
>> + bool compare_bb (sem_bb_t *bb1, sem_bb_t *bb2, tree func1, tree func2);
>> +
>> + /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
>> + true value is returned if phi nodes are sematically
>> + equivalent in these blocks . */
>> + bool compare_phi_node (basic_block bb1, basic_block bb2, tree func1,
>> + tree func2);
>> +
>> + /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
>> + true value is returned if exception handling regions are equivalent
>> + in these blocks. */
>> + bool compare_eh_region (eh_region r1, eh_region r2, tree func1, tree func2);
>> +
>> + /* Iterates GSI statement iterator to the next non-debug statement. */
>> + void gsi_next_nondebug_stmt (gimple_stmt_iterator &gsi);
>> +
>> + /* Iterates GSI statement iterator to the next non-virtual statement. */
>> + void gsi_next_nonvirtual_phi (gimple_stmt_iterator &it);
>> +
>> + /* Verifies that trees T1 and T2 do correspond. */
>> + bool compare_function_decl (tree t1, tree t2);
>> +
>> + /* Verifies that trees T1 and T2 do correspond. */
>> + bool compare_variable_decl (tree t1, tree t2, tree func1, tree func2);
>> +
>> + /* Verifies for given GIMPLEs S1 and S2 (from function FUNC1, resp. FUNC2) that
>> + call statements are semantically equivalent. */
>> + bool compare_gimple_call (gimple s1, gimple s2,
>> + tree func1, tree func2);
>> +
>> + /* Verifies for given GIMPLEs S1 and S2 (from function FUNC1, resp. FUNC2) that
>> + assignment statements are semantically equivalent. */
>> + bool compare_gimple_assign (gimple s1, gimple s2, tree func1, tree func2);
>> +
>> + /* Verifies for given GIMPLEs S1 and S2 (from function FUNC1, resp. FUNC2) that
>> + condition statements are semantically equivalent. */
>> + bool compare_gimple_cond (gimple s1, gimple s2, tree func1, tree func2);
>> +
>> + /* Verifies for given GIMPLEs S1 and S2 (from function FUNC1, resp. FUNC2) that
>> + label statements are semantically equivalent. */
>> + bool compare_gimple_label (gimple s1, gimple s2, tree func1, tree func2);
>> +
>> + /* Verifies for given GIMPLEs S1 and S2 (from function FUNC1, resp. FUNC2) that
>> + switch statements are semantically equivalent. */
>> + bool compare_gimple_switch (gimple s1, gimple s2, tree func1, tree func2);
>> +
>> + /* Verifies for given GIMPLEs S1 and S2 (from function FUNC1, resp. FUNC2) that
>> + return statements are semantically equivalent. */
>> + bool compare_gimple_return (gimple s1, gimple s2, tree func1, tree func2);
>> +
>> + /* Verifies for given GIMPLEs S1 and S2 (from function FUNC1, resp. FUNC2) that
>> + goto statements are semantically equivalent. */
>> + bool compare_gimple_goto (gimple s1, gimple s2, tree func1, tree func2);
>> +
>> + /* Verifies for given GIMPLEs S1 and S2 (from function FUNC1, resp. FUNC2) that
>> + resx statements are semantically equivalent. */
>> + bool compare_gimple_resx (gimple s1, gimple s2);
>> +
>> + /* Verifies for given GIMPLEs S1 and S2 that ASM statements are equivalent.
>> + For the beginning, the pass only supports equality for
>> + '__asm__ __volatile__ ("", "", "", "memory")'. */
>> + bool compare_gimple_asm (gimple s1, gimple s2);
>> +
>> + /* Verifies that tree labels T1 and T2 correspond in FUNC1 and FUNC2. */
>> + bool compare_tree_ssa_label (tree t1, tree t2, tree func1, tree func2);
>> +
>> + /* Function compares two operands T1 and T2 and returns true if these
>> + two trees from FUNC1 (respectively FUNC2) are semantically equivalent. */
>> + bool compare_operand (tree t1, tree t2, tree func1, tree func2);
>> +
>> + /* If T1 and T2 are SSA names, dictionary comparison is processed. Otherwise,
>> + declaration comparasion is executed. */
>> + bool compare_ssa_name (tree t1, tree t2, tree func1, tree func2);
>> +
>> + /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
>> + corresponds to TARGET. */
>> + bool bb_dict_test (int* bb_dict, int source, int target);
>> +
>> + /* Iterates all tree types in T1 and T2 and returns true if all types
>> + are compatible. */
>> + bool compare_type_list (tree t1, tree t2);
>> +
>> + /* Processes function equality comparison. */
>> + bool equals_private (sem_item *item);
>> +
>> + /* Initializes references to another sem_item for gimple STMT of type assign. */
>> + void init_refs_for_assign (gimple stmt);
>> +
>> + /* Initializes references to another sem_item for tree T. */
>> + void init_refs_for_tree (tree t);
>> +
>> + /* Returns true if tree T can be compared as a handled component. */
>> + static bool icf_handled_component_p (tree t);
>> +
>> + /* Function checker stores binding between functions. */
>> + func_checker checker;
>> +
>> + /* COMPARED_FUNC is a function that we compare to. */
>> + sem_function *compared_func;
>> +}; // class sem_function
>> +
>> +class sem_variable: public sem_item
>> +{
>> +public:
>> + /* Semantic variable constructor that uses STACK as bitmap memory stack. */
>> + sem_variable (bitmap_obstack *stack);
>> +
>> + /* Constructor based on callgraph node _NODE with computed hash _HASH.
>> + Bitmap STACK is used for memory allocation. */
>> +
>> + sem_variable (varpool_node *_node, hashval_t _hash, bitmap_obstack *stack);
>> +
>> + virtual void init_wpa (void);
>> + virtual void init (void);
>> + virtual const char *name (void);
>> + virtual const char *asm_name (void);
>> + virtual void init_refs ();
>> + virtual hashval_t get_hash (void);
>> + virtual bool merge (sem_item *alias_item);
>> + virtual void dump_to_file (FILE *file);
>> + virtual bool equals_wpa (sem_item *item);
>> + virtual bool equals (sem_item *item);
>> +
>> + /* Returns varpool_node. */
>> + struct varpool_node *get_node (void);
>> +
>> + /* Parser function that visits a varpool NODE. */
>> + static sem_variable *parse (struct varpool_node *node, bitmap_obstack *stack);
>> +
>> + /* Variable constructor. */
>> + tree ctor;
>> +
>> +private:
>> + /* Iterates though a constructor and identifies tree references
>> + we are interested in semantic function equality. */
>> + void parse_tree_refs (tree t);
>> +
>> + /* Compares trees T1 and T2 for semantic equality. */
>> + static bool equals (tree t1, tree t2);
>> +
>> +}; // class sem_variable
>> +
>> +class sem_item_optimizer;
>> +
>> +/* Congruence class set structure. */
>> +struct congruence_class_var_hash: typed_noop_remove <congruence_class>
>> +{
>> + typedef congruence_class value_type;
>> + typedef congruence_class compare_type;
>> + static inline hashval_t hash (const value_type *);
>> + static inline int equal (const value_type *, const compare_type *);
>> +};
>> +
>> +typedef struct congruence_class_group
>> +{
>> + hashval_t hash;
>> + vec <congruence_class *> classes;
>> +} congruence_class_group_t;
>> +
>> +/* Congruence class set structure. */
>> +struct congruence_class_group_hash: typed_noop_remove <congruence_class_group_t>
>> +{
>> + typedef congruence_class_group value_type;
>> + typedef congruence_class_group compare_type;
>> + static inline hashval_t hash (const value_type *);
>> + static inline int equal (const value_type *, const compare_type *);
>> +};
>> +
>> +struct traverse_split_pair
>> +{
>> + sem_item_optimizer *optimizer;
>> + class congruence_class *cls;
>> +};
>> +
>> +/* Semantic item optimizer includes all top-level logic
>> + related to semantic equality comparison. */
>> +class sem_item_optimizer
>> +{
>> +public:
>> + sem_item_optimizer ();
>> + ~sem_item_optimizer ();
>> +
>> + /* Function responsible for visiting all potential functions and
>> + read-only variables that can be merged. */
>> + void parse_funcs_and_vars (void);
>> +
>> + /* Optimizer entry point. */
>> + void execute (void);
>> +
>> + /* Dump function. */
>> + void dump (void);
>> +
>> + /* Verify congruence classes if checking is enabled. */
>> + void verify_classes (void);
>> +
>> + /* Write IPA ICF summary for symbols. */
>> + void write_summary (void);
>> +
>> + /* Read IPA IPA ICF summary for symbols. */
>> + void read_summary (void);
>> +
>> + /* Callgraph removal hook called for a NODE with a custom DATA. */
>> + static void cgraph_removal_hook (struct cgraph_node *node, void *data);
>> +
>> + /* Varpool removal hook called for a NODE with a custom DATA. */
>> + static void varpool_removal_hook (struct varpool_node *node, void *data);
>> +
>> + /* Worklist of congruence classes that can potentially
>> + refine classes of congruence. */
>> + hash_table <congruence_class_var_hash> worklist;
>> +
>> + /* Remove symtab NODE triggered by symtab removal hooks. */
>> + void remove_symtab_node (struct symtab_node *node);
>> +
>> + /* Register callgraph and varpool hooks. */
>> + void register_hooks (void);
>> +
>> + /* Unregister callgraph and varpool hooks. */
>> + void unregister_hooks (void);
>> +
>> + /* Adds a CLS to hashtable associated by hash value. */
>> + void add_class (congruence_class *cls);
>> +
>> + /* Gets a congruence class group based on given HASH value. */
>> + congruence_class_group_t *get_group_by_hash (hashval_t hash);
>> +
>> +private:
>> +
>> + /* Congruence classes are built by hash value. */
>> + void build_hash_based_classes (void);
>> +
>> + /* Semantic items in classes having more than one element and initialized.
>> + In case of WPA, we load function body. */
>> + void parse_nonsingleton_classes (void);
>> +
>> + /* Equality function for semantic items is used to subdivide existing
>> + classes. If IN_WPA, fast equality function is invoked. */
>> + void subdivide_classes_by_equality (bool in_wpa = false);
>> +
>> + /* Debug function prints all informations about congruence classes. */
>> + void dump_cong_classes (void);
>> +
>> + /* Iterative congruence reduction function. */
>> + void process_cong_reduction (void);
>> +
>> + /* After reduction is done, we can declare all items in a group
>> + to be equal. PREV_CLASS_COUNT is start number of classes
>> + before reduction. */
>> + void merge_classes (unsigned int prev_class_count);
>> +
>> + /* Adds a newly created congruence class CLS to worklist. */
>> + void worklist_push (congruence_class *cls);
>> +
>> + /* Pops a class from worklist. */
>> + congruence_class *worklist_pop ();
>> +
>> + /* Returns true if a congruence class CLS is presented in worklist. */
>> + bool worklist_contains (const congruence_class *cls);
>> +
>> + /* Removes given congruence class CLS from worklist. */
>> + void worklist_remove (const congruence_class *cls);
>> +
>> + /* Every usage of a congruence class CLS is a candidate that can split the
>> + collection of classes. Bitmap stack BMSTACK is used for bitmap
>> + allocation. */
>> + void do_congruence_step (congruence_class *cls);
>> +
>> + /* Tests if a class CLS used as INDEXth splits any congruence classes.
>> + Bitmap stack BMSTACK is used for bitmap allocation. */
>> + void do_congruence_step_for_index (congruence_class *cls, unsigned int index);
>> +
>> + /* Makes pairing between a congruence class CLS and semantic ITEM. */
>> + static void add_item_to_class (congruence_class *cls, sem_item *item);
>> +
>> + /* Disposes split map traverse function. CLS_PTR is pointer to congruence
>> + class, BSLOT is bitmap slot we want to release. DATA is mandatory,
>> + but unused argument. */
>> + static bool release_split_map (const void *cls_ptr, bitmap *bslot, void *data);
>> +
>> + /* Process split operation for a class given as pointer CLS_PTR,
>> + where bitmap B splits congruence class members. DATA is used
>> + as argument of split pair. */
>> + static bool traverse_congruence_split (const void *cls_ptr, bitmap *b,
>> + void *data);
>> +
>> + /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
>> + contains LEN bytes. */
>> + void read_section (struct lto_file_decl_data *file_data, const char *data,
>> + size_t len);
>> +
>> + /* Removes all callgraph and varpool nodes that are marked by symtab
>> + as deleted. */
>> + void filter_removed_items (void);
>> +
>> + /* Vector of semantic items. */
>> + vec <sem_item *> items;
>> +
>> + /* A set containing all items removed by hooks. */
>> + pointer_set_t *removed_items_set;
>> +
>> + /* Hashtable of congruence classes */
>> + hash_table <congruence_class_group_hash> classes;
>> +
>> + /* Count of congruence classes. */
>> + unsigned int classes_count;
>> +
>> + /* Map data structure maps trees to semantic items. */
>> + pointer_map <sem_item *> decl_map;
>> +
>> + /* Map data structure maps symtab nodes to semantic items. */
>> + pointer_map <sem_item *> symtab_node_map;
>> +
>> + /* For all congruence classes, we indicate partial mapping
>> + during reduction. */
>> + pointer_map <bitmap> *split_map;
>> +
>> + /* Set to true if a splitter class is removed. */
>> + bool splitter_class_removed;
>> +
>> + /* Global unique class id counter. */
>> + static unsigned int class_id;
>> +
>> + /* Callgraph node removal hook holder. */
>> + struct cgraph_node_hook_list *cgraph_node_hooks;
>> +
>> + /* Varpool node removal hook holder. */
>> + struct varpool_node_hook_list *varpool_node_hooks;
>> +
>> + /* Bitmap stack. */
>> + bitmap_obstack bmstack;
>> +}; // class sem_item_optimizer
>> +
>> +}
>> diff --git a/gcc/lto-section-in.c b/gcc/lto-section-in.c
>> index d887763..f9587cf 100644
>> --- a/gcc/lto-section-in.c
>> +++ b/gcc/lto-section-in.c
>> @@ -60,7 +60,8 @@ const char *lto_section_name[LTO_N_SECTION_TYPES] =
>> "opts",
>> "cgraphopt",
>> "inline",
>> - "ipcp_trans"
>> + "ipcp_trans",
>> + "icf"
>> };
>>
>>
>> diff --git a/gcc/lto-streamer.h b/gcc/lto-streamer.h
>> index 521d78d..3207d08 100644
>> --- a/gcc/lto-streamer.h
>> +++ b/gcc/lto-streamer.h
>> @@ -247,6 +247,7 @@ enum lto_section_type
>> LTO_section_cgraph_opt_sum,
>> LTO_section_inline_summary,
>> LTO_section_ipcp_transform,
>> + LTO_section_ipa_icf,
>> LTO_N_SECTION_TYPES /* Must be last. */
>> };
>>
>> diff --git a/gcc/opts.c b/gcc/opts.c
>> index 2b1280a..b5a58a5 100644
>> --- a/gcc/opts.c
>> +++ b/gcc/opts.c
>> @@ -496,6 +496,7 @@ static const struct default_options default_options_table[] =
>> { OPT_LEVELS_2_PLUS, OPT_fvect_cost_model_, NULL, VECT_COST_MODEL_CHEAP },
>> { OPT_LEVELS_2_PLUS_SPEED_ONLY, OPT_foptimize_strlen, NULL, 1 },
>> { OPT_LEVELS_2_PLUS, OPT_fhoist_adjacent_loads, NULL, 1 },
>> + { OPT_LEVELS_2_PLUS, OPT_fipa_icf, NULL, 1 },
>> { OPT_LEVELS_2_PLUS, OPT_fisolate_erroneous_paths_dereference, NULL, 1 },
>> { OPT_LEVELS_2_PLUS, OPT_fuse_caller_save, NULL, 1 },
>>
>> diff --git a/gcc/passes.def b/gcc/passes.def
>> index f9e0b2a..e629a1d 100644
>> --- a/gcc/passes.def
>> +++ b/gcc/passes.def
>> @@ -105,6 +105,7 @@ along with GCC; see the file COPYING3. If not see
>> NEXT_PASS (pass_ipa_whole_program_visibility);
>> NEXT_PASS (pass_ipa_profile);
>> NEXT_PASS (pass_ipa_devirt);
>> + NEXT_PASS (pass_ipa_icf);
>> NEXT_PASS (pass_ipa_cp);
>> NEXT_PASS (pass_ipa_cdtor_merge);
>> NEXT_PASS (pass_ipa_inline);
>> diff --git a/gcc/timevar.def b/gcc/timevar.def
>> index cbb64d5..c1d09eb 100644
>> --- a/gcc/timevar.def
>> +++ b/gcc/timevar.def
>> @@ -89,6 +89,7 @@ DEFTIMEVAR (TV_WHOPR_LTRANS , "whopr ltrans")
>> DEFTIMEVAR (TV_IPA_REFERENCE , "ipa reference")
>> DEFTIMEVAR (TV_IPA_PROFILE , "ipa profile")
>> DEFTIMEVAR (TV_IPA_PURE_CONST , "ipa pure const")
>> +DEFTIMEVAR (TV_IPA_ICF , "ipa icf")
>> DEFTIMEVAR (TV_IPA_PTA , "ipa points-to")
>> DEFTIMEVAR (TV_IPA_SRA , "ipa SRA")
>> DEFTIMEVAR (TV_IPA_FREE_LANG_DATA , "ipa free lang data")
>> diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
>> index 3888bb6..d55d7b8 100644
>> --- a/gcc/tree-pass.h
>> +++ b/gcc/tree-pass.h
>> @@ -464,6 +464,7 @@ extern simple_ipa_opt_pass *make_pass_ipa_free_lang_data (gcc::context *ctxt);
>> extern simple_ipa_opt_pass *make_pass_ipa_free_inline_summary (gcc::context
>> *ctxt);
>> extern ipa_opt_pass_d *make_pass_ipa_cp (gcc::context *ctxt);
>> +extern ipa_opt_pass_d *make_pass_ipa_icf (gcc::context *ctxt);
>> extern ipa_opt_pass_d *make_pass_ipa_devirt (gcc::context *ctxt);
>> extern ipa_opt_pass_d *make_pass_ipa_reference (gcc::context *ctxt);
>> extern ipa_opt_pass_d *make_pass_ipa_pure_const (gcc::context *ctxt);
>> --
>> 1.8.4.5
>>
>>
More information about the Gcc-patches
mailing list