Re: [PATCH 3/5] IPA ICF pass

[Martin Liška <mliska at suse dot cz>]

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 <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.

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
>