On 09/26/2014 11:27 PM, Jan Hubicka wrote:
>> 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 <hubi...@ucw.cz> and Martin Liska
>> <mli...@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.
Hello.
Yeah, you are right. But even Richard advised me to put it to a single place.
Maybe we are a bit
more strict than it would be necessary. But I hope that's fine ;)
>> +
>> + /* 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.)
Good point. Do you mean cases like, foo (alias_foo) and bar (alias_bar). If we
prove that foo equals to bar, can we also merge aliases?
I am curious if such comparison can really save something? Are there any
interesting cases?
Martin
>> + 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
>
