> 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. > + > + /* 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