This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH 3/5] IPA ICF pass
- From: Jan Hubicka <hubicka at ucw dot cz>
- To: Martin Liška <mliska at suse dot cz>
- Cc: gcc-patches at gcc dot gnu dot org, Jan Hubicka <hubicka at ucw dot cz>
- Date: Sat, 27 Sep 2014 00:27:30 +0200
- Subject: Re: [PATCH 3/5] IPA ICF pass
- Authentication-results: sourceware.org; auth=none
- References: <c5c2463c07186b4ba35b10f3063ecdd8f8d46d63 dot 1402913001 dot git dot mliska at suse dot cz> <ac1da49f0ee78643bc4521580862fa92e1051764 dot 1402913001 dot git dot mliska at suse dot cz> <20140620073156 dot GC12633 at tsaunders-iceball dot corp dot tor1 dot mozilla dot com> <alpine dot LSU dot 2 dot 11 dot 1407052337210 dot 30120 at tuna dot site> <20140705225351 dot GK16837 at kam dot mff dot cuni dot cz> <53C7E626 dot 8080400 at suse dot cz> <54255A09 dot 1090305 at suse dot cz>
> diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c
> new file mode 100644
> index 0000000..f3472fe
> --- /dev/null
> +++ b/gcc/ipa-icf.c
> @@ -0,0 +1,2841 @@
> +/* 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.
(or value)
> +
> + 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.
> +
> + Optimization pass arranges as follows:
The optimization pass is arranged as follows: (I guess)
I also wonder if the gimple equality code should be in ipa_icf namespace, it is intended
to be shared with tail merging pass, so what about just calling it gimple_sem_equality?
> +/* Verification function for edges E1 and E2. */
> +
> +bool
> +func_checker::compare_edge (edge e1, edge e2)
> +{
> + if (e1->flags != e2->flags)
> + return false;
In future we may want to experiment with checking that edge probabilities with
profile feedback match and refuse to merge BBs with different outgoing probabilities
(i.e. +-5%).
Just add it as TODO there, please.
> +
> +/* Return true if types are compatible from perspective of ICF. */
> +bool func_checker::types_are_compatible_p (tree t1, tree t2,
Perhaps dropping _are_ would make sense, so we do not have two names
for essentially same thing.
> + bool compare_polymorphic,
> + bool first_argument)
> +{
> + if (TREE_CODE (t1) != TREE_CODE (t2))
> + return RETURN_FALSE_WITH_MSG ("different tree types");
> +
> + if (!types_compatible_p (t1, t2))
> + return RETURN_FALSE_WITH_MSG ("types are not compatible");
> +
> + if (get_alias_set (t1) != get_alias_set (t2))
> + return RETURN_FALSE_WITH_MSG ("alias sets are different");
You do not need to compare alias sets except for memory operations IMO.
> +
> + /* We call contains_polymorphic_type_p with this pointer type. */
> + if (first_argument && TREE_CODE (t1) == POINTER_TYPE)
> + {
> + t1 = TREE_TYPE (t1);
> + t2 = TREE_TYPE (t2);
> + }
> +
> + if (compare_polymorphic
> + && (contains_polymorphic_type_p (t1) || contains_polymorphic_type_p (t2)))
> + {
> + if (!contains_polymorphic_type_p (t1) || !contains_polymorphic_type_p (t2))
> + return RETURN_FALSE_WITH_MSG ("one type is not polymorphic");
> +
> + if (TYPE_MAIN_VARIANT (t1) != TYPE_MAIN_VARIANT (t2))
> + return RETURN_FALSE_WITH_MSG ("type variants are different for "
> + "polymorphic type");
I added types_must_be_same_for_odr (t1,t2) for you here.
> +/* Fast equality function based on knowledge known in WPA. */
> +
> +bool
> +sem_function::equals_wpa (sem_item *item)
> +{
> + gcc_assert (item->type == FUNC);
> +
> + m_compared_func = static_cast<sem_function *> (item);
> +
> + if (arg_types.length () != m_compared_func->arg_types.length ())
> + return RETURN_FALSE_WITH_MSG ("different number of arguments");
> +
> + /* Checking types of arguments. */
> + for (unsigned i = 0; i < arg_types.length (); i++)
> + {
> + /* This guard is here for function pointer with attributes (pr59927.c). */
> + if (!arg_types[i] || !m_compared_func->arg_types[i])
> + return RETURN_FALSE_WITH_MSG ("NULL argument type");
> +
> + if (!func_checker::types_are_compatible_p (arg_types[i],
> + m_compared_func->arg_types[i],
> + true, i == 0))
> + return RETURN_FALSE_WITH_MSG ("argument type is different");
> + }
> +
> + /* Result type checking. */
> + if (!func_checker::types_are_compatible_p (result_type,
> + m_compared_func->result_type))
> + return RETURN_FALSE_WITH_MSG ("result types are different");
You may want to compare ECF flags, such as nothrow/const/pure. We do not
want to merge non-pure function into pure as it may not be pure in the context
it is used.
Do you compare attributes? I think optimize attribute needs to be matched.
> + /* Checking function arguments. */
attributes.
> + tree decl1 = DECL_ATTRIBUTES (decl);
> + tree decl2 = DECL_ATTRIBUTES (m_compared_func->decl);
> +
> + m_checker = new func_checker (decl, m_compared_func->decl,
> + compare_polymorphic_p (),
> + false,
> + &tree_refs_set,
> + &m_compared_func->tree_refs_set);
> + while (decl1)
> + {
> + if (decl2 == NULL)
> + return RETURN_FALSE ();
> +
> + if (get_attribute_name (decl1) != get_attribute_name (decl2))
> + return RETURN_FALSE ();
> +
> + tree attr_value1 = TREE_VALUE (decl1);
> + tree attr_value2 = TREE_VALUE (decl2);
> +
> + if (attr_value1 && attr_value2)
> + {
> + bool ret = m_checker->compare_operand (TREE_VALUE (attr_value1),
> + TREE_VALUE (attr_value2));
> + if (!ret)
> + return RETURN_FALSE_WITH_MSG ("attribute values are different");
> + }
> + else if (!attr_value1 && !attr_value2)
> + {}
> + else
> + return RETURN_FALSE ();
> +
> + decl1 = TREE_CHAIN (decl1);
> + decl2 = TREE_CHAIN (decl2);
> + }
> +
> + if (decl1 != decl2)
> + return RETURN_FALSE();
> +
> +
> + for (arg1 = DECL_ARGUMENTS (decl),
> + arg2 = DECL_ARGUMENTS (m_compared_func->decl);
> + arg1; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2))
> + if (!m_checker->compare_decl (arg1, arg2))
> + return RETURN_FALSE ();
I think you want to compare PARM_DECL flags, such as DECL_BY_REFERENCE
> +
> +/* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
> +
> +void
> +sem_function::improve_hash (inchash::hash *hstate, gimple stmt)
Hehe, I think simple hash_stmt would be easier to read - it took me some time
to figure out what you mean by improving.
> +{
> + enum gimple_code code = gimple_code (stmt);
> +
> + hstate->add_int (code);
> +
> + if (code == GIMPLE_CALL)
> + {
> + /* Checking of argument. */
> + for (unsigned i = 0; i < gimple_call_num_args (stmt); ++i)
> + {
> + tree argument = gimple_call_arg (stmt, i);
> +
> + switch (TREE_CODE (argument))
> + {
> + case INTEGER_CST:
> + if (tree_fits_shwi_p (argument))
> + hstate->add_wide_int (tree_to_shwi (argument));
> + else if (tree_fits_uhwi_p (argument))
> + hstate->add_wide_int (tree_to_uhwi (argument));
> + break;
> + case ADDR_EXPR:
> + {
> + tree addr_operand = TREE_OPERAND (argument, 0);
> +
> + if (TREE_CODE (addr_operand) == STRING_CST)
> + hstate->add (TREE_STRING_POINTER (addr_operand),
> + TREE_STRING_LENGTH (addr_operand));
It may be nice to reuse some of the hash_tree code, but yep, i guess
this is good first cut. Perhaps adding also REAL_CST
> +
> +/* Return true if polymorphic comparison must be processed. */
> +
> +bool
> +sem_function::compare_polymorphic_p (void)
> +{
> + return get_node ()->callees != NULL
> + || m_compared_func->get_node ()->callees != NULL;
This is somewhat kludgy, but probably OK for start. I do not see how
local declaration can leak out after inlining.
You also want to check for no indirect calls.
> +
> + if (!func || !node->has_gimple_body_p ())
> + return NULL;
Do you somewhere handle thunks and aliases?
(again someting that can be done later, but TODO would be nice.)
> + case INTEGER_CST:
> + {
> + ret = types_are_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2))
> + && wi::to_offset (t1) == wi::to_offset (t2);
tree_int_cst_equal
> + case FIELD_DECL:
> + {
> + tree fctx1 = DECL_FCONTEXT (t1);
> + tree fctx2 = DECL_FCONTEXT (t2);
DECL_FCONTEXT has no semantic meaning; so you can skip comparing it.
> +
> + tree offset1 = DECL_FIELD_OFFSET (t1);
> + tree offset2 = DECL_FIELD_OFFSET (t2);
> +
> + tree bit_offset1 = DECL_FIELD_BIT_OFFSET (t1);
> + tree bit_offset2 = DECL_FIELD_BIT_OFFSET (t2);
> +
> + ret = compare_operand (fctx1, fctx2)
> + && compare_operand (offset1, offset2)
> + && compare_operand (bit_offset1, bit_offset2);
You probably want to compare type here?
> + case CONSTRUCTOR:
> + {
> + unsigned len1 = vec_safe_length (CONSTRUCTOR_ELTS (t1));
> + unsigned len2 = vec_safe_length (CONSTRUCTOR_ELTS (t2));
> +
> + if (len1 != len2)
> + return false;
> +
> + for (unsigned i = 0; i < len1; i++)
> + if (!sem_variable::equals (CONSTRUCTOR_ELT (t1, i)->value,
> + CONSTRUCTOR_ELT (t2, i)->value))
> + return false;
You want to compare ->index, too.
> + case INTEGER_CST:
> + return func_checker::types_are_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2),
> + true)
> + && wi::to_offset (t1) == wi::to_offset (t2);
again ;)
This is where I stopped for now. Generally the patch seems OK to me with few of these
details fixed.
Honza