[PATCH 3/5] IPA ICF pass

Jan Hubicka hubicka@ucw.cz
Fri Sep 26 22:27:00 GMT 2014


> 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



More information about the Gcc-patches mailing list