Re: [RFC] operand_equal_p with valueization

[Richard Biener <rguenther@suse.de>]

On Fri, 22 May 2015, Jan Hubicka wrote:

> Hi,
> with aliasing sanity checks I got burnt again with ipa-icf-gimple's
> compare_operand doing alias set checks on all types it ever trips across.
> 
> I always tought that we do not need two equality testers - operand_equal_p and
> compare_operand and given that it turns out to be non-trivial to fix issues in
> compare_operand I decided to go ahead with plan to unify them.
> I think operand_equal_p is better code base to start from since it is more
> tested and knows more special cases.
> 
> The basic idea is to add valeize hook similar way as other folders do that
> allows to do magic inside the recursive comparsion. I.e. declare two trees
> equal if they are not (i.e. SSA_NAMES from differen functions).  I think it
> should be useful for GVN/VRP/CCP too to improve folding of conditionals.
> 
> After trying out the hook and figuring out that ipa-icf does not have
> global context to hold its tables, I dedcided that maybe more C++ way
> is to have comparsion class that can be derived an adjusted for other
> needs.
> 
> The following patch is a first step.  If it is considered sane, I will
> continue by moving the code to one place - ipa-icf-gimple or special
> ipa-icf-op.c. I will also recover Martin's diagnostics that is useful
> to debug why things are considered different.
> 
> Also the code should be C++ized, for example it should use true/false
> instead 0/1.
> 
> I think also the iterative hashing should be together with operand_equal_p
> implementation because these two must match as I found with merging the two
> cases that ipa-icf-gimple gets right and fold-const wrong - OBJ_TYPE_REF,
> CONSTRUCTOR and PARM_DECL.
> 
> Finally I think we want compare_gimple class that does the same for
> gimple and is independent of rest of the ipa-icf that may be better
> suitable for stuff like tail merging.
> 
> The patch bootstraps/regtests ppc64-linux, but I think it is not quite
> mainline ready as it noticeably reduces number of equivalences found. 
> I will need to debug why that happens, but I am sending it as an RFC for
> the basic concept and interfaces.

I think for the case of IPA ICF it would be better to address the
issue that it cannot do merging of functions with TBAA conflicts.
That is, drop that TBAA code from IPA ICF and arrange for the
IPA inliner to inline original unmerged copies.  We were talking
about making the original nodes "inline clones" of the node that
eventually prevails, much similar to speculative inlining ones
(if I remember that suggestion from Martin correctly).

And no, I'm hesitant to change operand_equal_p too much.  It's
very much deep-rooted into GENERIC.

Richard.


> Honza
> 
> 	* fold-const.c (operand_equal_p): Reorg to wrapper for
> 	(operand_compare::operand_equal_p): This function; add
> 	support for valueization, add missing type matching for
> 	OBJ_TYPE_REF, CONSTRUCTOR; relax matching of PARM_DECL.
> 	(operand_compare::operand_equal_valueize): New.
> 	* fold-const.h (operand_equal_p): Update prototype.
> 	(class operand_compare): New class.
> 	* ipa-icf-gimple.c (func_checker::operand_equal_valueize): Break
> 	ipa-icf specific bits out from ...
> 	(func_checker::compare_operand): ... here; remove most of generic
> 	handling and use operand_compare class.
> 	* ipa-icf-gimple.h (operand_compare): New.
> 	* ipa-icf.c (sem_function::equals_private): Arrange CFUN to be up to
> 	date so we operand_equal_p works well for flag_devirtualize.
> Index: fold-const.c
> ===================================================================
> --- fold-const.c	(revision 223500)
> +++ fold-const.c	(working copy)
> @@ -2716,8 +2730,9 @@ combine_comparisons (location_t loc,
>     are considered the same.  It is used when the caller has other ways
>     to ensure that global memory is unchanged in between.  */
>  
> -int
> -operand_equal_p (const_tree arg0, const_tree arg1, unsigned int flags)
> +bool
> +operand_compare::operand_equal_p (const_tree arg0, const_tree arg1,
> +				  unsigned int flags)
>  {
>    /* If either is ERROR_MARK, they aren't equal.  */
>    if (TREE_CODE (arg0) == ERROR_MARK || TREE_CODE (arg1) == ERROR_MARK
> @@ -2868,6 +2883,12 @@ operand_equal_p (const_tree arg0, const_
>    if (flags & OEP_ONLY_CONST)
>      return 0;
>  
> +  int val = operand_equal_valueize (arg0, arg1, flags);
> +  if (val == 1)
> +    return 1;
> +  if (val == 0)
> +    return 0;
> +
>  /* Define macros to test an operand from arg0 and arg1 for equality and a
>     variant that allows null and views null as being different from any
>     non-null value.  In the latter case, if either is null, the both
> @@ -3104,12 +3174,50 @@ operand_equal_p (const_tree arg0, const_
>  	      && DECL_FUNCTION_CODE (arg0) == DECL_FUNCTION_CODE (arg1));
>  
>      default:
>        return 0;
>      }
>  
>  #undef OP_SAME
>  #undef OP_SAME_WITH_NULL
>  }
> +
> +/* Valueizer is a virtual method that allows to introduce extra equalities
> +   that are not directly visible from the operand.
> +   N1 means values are known to be equal, 0 means values are known to be different
> +   -1 means that operand_equal_p should continue processing.  */
> +int
> +operand_compare::operand_equal_valueize (const_tree, const_tree, unsigned int)
> +{
> +  return -1;
> +}
> +
> +/* Conveinece wrapper around operand_compare class because usually we do
> +   not need to play with the valueizer.  */
> +bool
> +operand_equal_p (const_tree arg0, const_tree arg1, unsigned int flags)
> +{
> +  static operand_compare default_compare_instance;
> +  return default_compare_instance.operand_equal_p (arg0, arg1, flags);
> +}
>  \f
>  /* Similar to operand_equal_p, but see if ARG0 might have been made by
>     shorten_compare from ARG1 when ARG1 was being compared with OTHER.
> Index: fold-const.h
> ===================================================================
> --- fold-const.h	(revision 223500)
> +++ fold-const.h	(working copy)
> @@ -85,7 +85,7 @@ extern void fold_defer_overflow_warnings
>  extern void fold_undefer_overflow_warnings (bool, const_gimple, int);
>  extern void fold_undefer_and_ignore_overflow_warnings (void);
>  extern bool fold_deferring_overflow_warnings_p (void);
> -extern int operand_equal_p (const_tree, const_tree, unsigned int);
> +extern bool operand_equal_p (const_tree, const_tree, unsigned int flags = 0);
>  extern int multiple_of_p (tree, const_tree, const_tree);
>  #define omit_one_operand(T1,T2,T3)\
>     omit_one_operand_loc (UNKNOWN_LOCATION, T1, T2, T3)
> @@ -189,4 +189,20 @@ extern tree fold_build_pointer_plus_hwi_
>  
>  #define fold_build_pointer_plus_hwi(p,o) \
>  	fold_build_pointer_plus_hwi_loc (UNKNOWN_LOCATION, p, o)
> +
> +/* Class used to compare gimple operands.  */
> +
> +class operand_compare
> +{
> +public:
> +  /* Return true if two operands are equal.  THe flags fields can be used
> +     to specify OEP flags described above.   */
> +  bool operand_equal_p (const_tree, const_tree, unsigned int flags = 0);
> +private:
> +  /* Valueizer can be used to make non-trivial equalities for expressions
> +     that do not look same in isolation.
> +     1 means values are known to be equal, 0 means values are known to be
> +     different -1 means that operand_equal_p should continue processing.  */
> +  virtual int operand_equal_valueize (const_tree, const_tree, unsigned int);
> +};
>  #endif // GCC_FOLD_CONST_H
> Index: ipa-icf-gimple.c
> ===================================================================
> --- ipa-icf-gimple.c	(revision 223500)
> +++ ipa-icf-gimple.c	(working copy)
> @@ -412,165 +428,57 @@ func_checker::compare_cst_or_decl (tree
>      }
>  }
>  
> -/* Function responsible for comparison of various operands T1 and T2.
> -   If these components, from functions FUNC1 and FUNC2, are equal, true
> -   is returned.  */
> -
> -bool
> -func_checker::compare_operand (tree t1, tree t2)
> +int
> +func_checker::operand_equal_valueize (const_tree ct1, const_tree ct2, unsigned int)
>  {
> -  tree x1, x2, y1, y2, z1, z2;
> +  tree t1 = const_cast <tree> (ct1);
> +  tree t2 = const_cast <tree> (ct2);
>    bool ret;
>  
> -  if (!t1 && !t2)
> -    return true;
> -  else if (!t1 || !t2)
> -    return false;
> -
> -  tree tt1 = TREE_TYPE (t1);
> -  tree tt2 = TREE_TYPE (t2);
> -
> -  if (!func_checker::compatible_types_p (tt1, tt2))
> -    return false;
> -
> -  if (TREE_CODE (t1) != TREE_CODE (t2))
> -    return return_false ();
> -
>    switch (TREE_CODE (t1))
>      {
> -    case CONSTRUCTOR:
> -      {
> -	unsigned length1 = vec_safe_length (CONSTRUCTOR_ELTS (t1));
> -	unsigned length2 = vec_safe_length (CONSTRUCTOR_ELTS (t2));
> -
> -	if (length1 != length2)
> -	  return return_false ();
> -
> -	for (unsigned i = 0; i < length1; i++)
> -	  if (!compare_operand (CONSTRUCTOR_ELT (t1, i)->value,
> -				CONSTRUCTOR_ELT (t2, i)->value))
> -	    return return_false();
> -
> -	return true;
> -      }
> -    case ARRAY_REF:
> -    case ARRAY_RANGE_REF:
> -      /* First argument is the array, second is the index.  */
> -      x1 = TREE_OPERAND (t1, 0);
> -      x2 = TREE_OPERAND (t2, 0);
> -      y1 = TREE_OPERAND (t1, 1);
> -      y2 = TREE_OPERAND (t2, 1);
> -
> -      if (!compare_operand (array_ref_low_bound (t1),
> -			    array_ref_low_bound (t2)))
> -	return return_false_with_msg ("");
> -      if (!compare_operand (array_ref_element_size (t1),
> -			    array_ref_element_size (t2)))
> -	return return_false_with_msg ("");
> -
> -      if (!compare_operand (x1, x2))
> -	return return_false_with_msg ("");
> -      return compare_operand (y1, y2);
> -    case MEM_REF:
> -      {
> -	x1 = TREE_OPERAND (t1, 0);
> -	x2 = TREE_OPERAND (t2, 0);
> -	y1 = TREE_OPERAND (t1, 1);
> -	y2 = TREE_OPERAND (t2, 1);
> -
> -	/* See if operand is an memory access (the test originate from
> -	 gimple_load_p).
> -
> -	In this case the alias set of the function being replaced must
> -	be subset of the alias set of the other function.  At the moment
> -	we seek for equivalency classes, so simply require inclussion in
> -	both directions.  */
> -
> -	if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2)))
> -	  return return_false ();
> -
> -	if (!compare_operand (x1, x2))
> -	  return return_false_with_msg ("");
> -
> -	/* Type of the offset on MEM_REF does not matter.  */
> -	return wi::to_offset  (y1) == wi::to_offset  (y2);
> -      }
> -    case COMPONENT_REF:
> -      {
> -	x1 = TREE_OPERAND (t1, 0);
> -	x2 = TREE_OPERAND (t2, 0);
> -	y1 = TREE_OPERAND (t1, 1);
> -	y2 = TREE_OPERAND (t2, 1);
> -
> -	ret = compare_operand (x1, x2)
> -	      && compare_cst_or_decl (y1, y2);
> -
> -	return return_with_debug (ret);
> -      }
> -    /* Virtual table call.  */
> -    case OBJ_TYPE_REF:
> -      {
> -	if (!compare_ssa_name (OBJ_TYPE_REF_EXPR (t1), OBJ_TYPE_REF_EXPR (t2)))
> -	  return return_false ();
> -	if (opt_for_fn (m_source_func_decl, flag_devirtualize)
> -	    && virtual_method_call_p (t1))
> -	  {
> -	    if (tree_to_uhwi (OBJ_TYPE_REF_TOKEN (t1))
> -		!= tree_to_uhwi (OBJ_TYPE_REF_TOKEN (t2)))
> -	      return return_false_with_msg ("OBJ_TYPE_REF token mismatch");
> -	    if (!types_same_for_odr (obj_type_ref_class (t1),
> -				     obj_type_ref_class (t2)))
> -	      return return_false_with_msg ("OBJ_TYPE_REF OTR type mismatch");
> -	    if (!compare_operand (OBJ_TYPE_REF_OBJECT (t1),
> -				  OBJ_TYPE_REF_OBJECT (t2)))
> -	      return return_false_with_msg ("OBJ_TYPE_REF object mismatch");
> -	  }
> -
> -	return return_with_debug (true);
> -      }
> -    case IMAGPART_EXPR:
> -    case REALPART_EXPR:
> -    case ADDR_EXPR:
> +    case FUNCTION_DECL:
> +      /* All function decls are in the symbol table and known to match
> +	 before we start comparing bodies.  */
> +      return true;
> +    case VAR_DECL:
> +      return return_with_debug (compare_variable_decl (t1, t2));
> +    case LABEL_DECL:
>        {
> -	x1 = TREE_OPERAND (t1, 0);
> -	x2 = TREE_OPERAND (t2, 0);
> +	int *bb1 = m_label_bb_map.get (t1);
> +	int *bb2 = m_label_bb_map.get (t2);
>  
> -	ret = compare_operand (x1, x2);
> -	return return_with_debug (ret);
> +	return return_with_debug (*bb1 == *bb2);
>        }
> -    case BIT_FIELD_REF:
> +    case PARM_DECL:
> +    case RESULT_DECL:
> +    case CONST_DECL:
>        {
> -	x1 = TREE_OPERAND (t1, 0);
> -	x2 = TREE_OPERAND (t2, 0);
> -	y1 = TREE_OPERAND (t1, 1);
> -	y2 = TREE_OPERAND (t2, 1);
> -	z1 = TREE_OPERAND (t1, 2);
> -	z2 = TREE_OPERAND (t2, 2);
> -
> -	ret = compare_operand (x1, x2)
> -	      && compare_cst_or_decl (y1, y2)
> -	      && compare_cst_or_decl (z1, z2);
> -
> +	ret = compare_decl (t1, t2);
>  	return return_with_debug (ret);
>        }
>      case SSA_NAME:
> -	return compare_ssa_name (t1, t2);
> -    case INTEGER_CST:
> -    case COMPLEX_CST:
> -    case VECTOR_CST:
> -    case STRING_CST:
> -    case REAL_CST:
> -    case FUNCTION_DECL:
> -    case VAR_DECL:
> -    case FIELD_DECL:
> -    case LABEL_DECL:
> -    case PARM_DECL:
> -    case RESULT_DECL:
> -    case CONST_DECL:
> -      return compare_cst_or_decl (t1, t2);
> +      return compare_ssa_name (t1, t2);
>      default:
> -      return return_false_with_msg ("Unknown TREE code reached");
> +      break;
>      }
> +  return -1;
> +}
> +
> +/* Function responsible for comparison of various operands T1 and T2.
> +   If these components, from functions FUNC1 and FUNC2, are equal, true
> +   is returned.  */
> +
> +bool
> +func_checker::compare_operand (tree t1, tree t2)
> +{
> +  if (!t1 && !t2)
> +    return true;
> +  else if (!t1 || !t2)
> +    return false;
> +  if (operand_equal_p (t1, t2, 0))
> +    return true;
> +  return return_false_with_msg ("operand_equal_p failed");
>  }
>  
>  /* Compares two tree list operands T1 and T2 and returns true if these
> Index: ipa-icf-gimple.h
> ===================================================================
> --- ipa-icf-gimple.h	(revision 223500)
> +++ ipa-icf-gimple.h	(working copy)
> @@ -127,7 +127,7 @@ public:
>  
>  /* A class aggregating all connections and semantic equivalents
>     for a given pair of semantic function candidates.  */
> -class func_checker
> +class func_checker : operand_compare
>  {
>  public:
>    /* Initialize internal structures for a given SOURCE_FUNC_DECL and
> @@ -143,7 +143,7 @@ public:
>  		hash_set<symtab_node *> *ignored_target_nodes = NULL);
>  
>    /* Memory release routine.  */
> -  ~func_checker();
> +  virtual ~func_checker();
>  
>    /* Function visits all gimple labels and creates corresponding
>       mapping between basic blocks and labels.  */
> @@ -273,6 +273,8 @@ private:
>  
>    /* Flag if ignore labels in comparison.  */
>    bool m_ignore_labels;
> +
> +  virtual int operand_equal_valueize (const_tree, const_tree, unsigned int);
>  };
>  
>  } // ipa_icf_gimple namespace
> Index: ipa-icf.c
> ===================================================================
> --- ipa-icf.c	(revision 223500)
> +++ ipa-icf.c	(working copy)
> @@ -953,9 +953,14 @@ sem_function::equals_private (sem_item *
>      }
>  
>    /* Checking all basic blocks.  */
> +  push_cfun (DECL_STRUCT_FUNCTION (decl));
>    for (unsigned i = 0; i < bb_sorted.length (); ++i)
>      if(!m_checker->compare_bb (bb_sorted[i], m_compared_func->bb_sorted[i]))
> -      return return_false();
> +      {
> +	pop_cfun ();
> +        return return_false();
> +      }
> +  pop_cfun ();
>  
>    dump_message ("All BBs are equal\n");
>  
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Dilip Upmanyu, Graham Norton, HRB 21284 (AG Nuernberg)