[RFC] Re: [RFC] operand_equal_p with valueization

[Martin Liška]

Hi.

It's quite some time the discussion has started. Now is time for me to refresh 
IPA ICF
and I would like integrate operand_equal_p with what I currently have in ICF 
(::compare_operand).
I like the idea of a class that will provide both operand_equal_valueize and 
hash_operand_valueize.
These will be implemented in func_checker and can provide basically the same 
what Honza suggested.

Reading the thread, I noticed Richi would prefer to use something like:

template 
int
operand_equal_p_1 (const_tree arg0, const_tree arg1, unsigned int flags,
   tree (*valueize)(tree))
{
#define VALUEIZE(op) (with_valueize && valueize) ? valueize (op) : op 
...
}

To be honest, it looks to me only as an optimization which will fold call
to valueize in current operand_equal_p.

I'm sending a slightly tested pair of patches which does the abstraction
factoring and ICF adaptation.

I would expect a feedback before I'll prepare a proper fix.
Thanks,
Martin
>From b864e44e14a86e9cc7ba494b7af687a0a3e74896 Mon Sep 17 00:00:00 2001
From: Martin Liska 
Date: Mon, 10 Jun 2019 14:34:15 +0200
Subject: [PATCH 2/2] Integrate that for IPA ICF.

---
 gcc/ipa-icf-gimple.c | 224 +--
 gcc/ipa-icf-gimple.h |   8 +-
 gcc/ipa-icf.c|   7 +-
 3 files changed, 79 insertions(+), 160 deletions(-)

diff --git a/gcc/ipa-icf-gimple.c b/gcc/ipa-icf-gimple.c
index 0713e125898..6da3e19e317 100644
--- a/gcc/ipa-icf-gimple.c
+++ b/gcc/ipa-icf-gimple.c
@@ -324,6 +324,28 @@ func_checker::compare_memory_operand (tree t1, tree t2)
 /* Function compare for equality given trees T1 and T2 which
can be either a constant or a declaration type.  */
 
+bool
+func_checker::hash_operand_valueize (const_tree arg, inchash::hash ,
+ unsigned int flags)
+{
+  switch (TREE_CODE (arg))
+{
+case FUNCTION_DECL:
+case VAR_DECL:
+case LABEL_DECL:
+case PARM_DECL:
+case RESULT_DECL:
+case CONST_DECL:
+case SSA_NAME:
+  return true;
+
+default:
+  break;
+}
+
+  return false;
+}
+
 bool
 func_checker::compare_cst_or_decl (tree t1, tree t2)
 {
@@ -347,19 +369,6 @@ func_checker::compare_cst_or_decl (tree t1, tree t2)
   return true;
 case VAR_DECL:
   return return_with_debug (compare_variable_decl (t1, t2));
-case FIELD_DECL:
-  {
-	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 (offset1, offset2)
-	  && compare_operand (bit_offset1, bit_offset2);
-
-	return return_with_debug (ret);
-  }
 case LABEL_DECL:
   {
 	if (t1 == t2)
@@ -383,165 +392,66 @@ func_checker::compare_cst_or_decl (tree t1, tree t2)
 }
 }
 
-/* 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;
-  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 ();
+  tree t1 = const_cast  (ct1);
+  tree t2 = const_cast  (ct2);
 
   switch (TREE_CODE (t1))
 {
-case CONSTRUCTOR:
+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:
   {
-	unsigned length1 = CONSTRUCTOR_NELTS (t1);
-	unsigned length2 = CONSTRUCTOR_NELTS (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;
+	int *bb1 = m_label_bb_map.get (t1);
+	int *bb2 = m_label_bb_map.get (t2);
+	return return_with_debug (*bb1 == *bb2);
   }
-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);
-	

Re: [RFC] operand_equal_p with valueization

[Richard Biener]

On Tue, 26 May 2015, Jan Hubicka wrote:

  On Fri, 22 May 2015, Jan Hubicka wrote:
  

And no, I'm hesitant to change operand_equal_p too much.  It's
very much deep-rooted into GENERIC.
   
   OK, as another option, i can bring relevant logic from operand_equal_p
   to ipa-icf and separate it into the compare_operand class like I did.
   Use it in ipa-icf-gimple now and we can slowly turn other uses of
   operand_equal into the compare_operand users in middle end.
   
   I agree that operand_equal is bit crazy code and it does not handle quite 
   few
   things we could do at gimple.  I have nothing against going this 
   direction.
   (after all I do not like touching fold-const much becuase it works on 
   generic,
   gimple and FE non-generic and it is not well specified what it should do)
  
  Yes, I've played with the idea of a GIMPLE specific operand_equal_p 
  multiple times but then the changes required to operand_equal_p were
  small all the times.  And having one piece of code that does sth is
  always good ...
  
  We might turn operand_equal_p to a worker (template?) that
 
 Hmm, OK that is precisely what I was shooting for by this patch.  I went by
 wrapping it to a class with valueize helper.  It can be template, too, just it
 semed that having the single valueize function lets me do everything I need
 without actually needing to duplicate the code.
 
 I can get around templatizing it.  Do you have some outline what interface
 would seem more fit

I was thinking about

template bool with_valueize
int
operand_equal_p_1 (const_tree arg0, const_tree arg1, unsigned int flags,
   tree (*valueize)(tree))
{
#define VALUEIZE(op) (with_valueize  valueize) ? valueize (op) : op 
...
}

and

extern template 
int operand_equal_p_1false (const_tree arg0, const_tree arg1, 
unsigned int flags,
   tree (*valueize)(tree));
extern template 
int operand_equal_p_1true (const_tree arg0, const_tree arg1,
unsigned int flags,
   tree (*valueize)(tree));

int
operand_equal_p (const_tree arg0, const_tree arg1, unsigned int flags)
{
  return operand_equal_p_1false (arg0, arg1, flags, NULL);
}

we don't want to make 'valueize' a template parameter (that is,
we don't want to put operand_equal_p_1 to fold-const.h).

Same with an eventual 'gimple_p' template parameter (which eventually
could simply be the same as the with_valueize one).

I'm playing with the idea to make match-and-simplify similar,
providing explicit specializations for common valueize callbacks.
As it always has a valueize callback I'd do it like

template tree (*fixed_valueize)(tree)
bool
gimple_simplify (code_helper *res_code, tree *res_ops,
 gimple_seq *seq, tree (*valueize)(tree),
 code_helper code, tree type, tree op0)
{
#define do_valueize(op) \
  fixed_valueize != (void *)-1 \
  ? (fixed_valueize ? fixed_valueize (op) : op) \
  : (valueize ? valueize (op) : op)
...
}

Richard.

  operand_equal_p and gimple_operand_equal_p can share (with an extra
  flag whether to turn on GIMPLE stuff and/or valueization).  And
  then simply provide explicit instantiations for the original
  operand_equal_p and a new gimple_operand_equal_p.
  
  Of course we'll only know if we like that when seeing a patch that
  does this ;0)
  
  Richard.
 
 

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

Re: [RFC] operand_equal_p with valueization

[Richard Biener]

On Fri, 22 May 2015, Jan Hubicka wrote:

  
  And no, I'm hesitant to change operand_equal_p too much.  It's
  very much deep-rooted into GENERIC.
 
 OK, as another option, i can bring relevant logic from operand_equal_p
 to ipa-icf and separate it into the compare_operand class like I did.
 Use it in ipa-icf-gimple now and we can slowly turn other uses of
 operand_equal into the compare_operand users in middle end.
 
 I agree that operand_equal is bit crazy code and it does not handle quite few
 things we could do at gimple.  I have nothing against going this direction.
 (after all I do not like touching fold-const much becuase it works on generic,
 gimple and FE non-generic and it is not well specified what it should do)

Yes, I've played with the idea of a GIMPLE specific operand_equal_p 
multiple times but then the changes required to operand_equal_p were
small all the times.  And having one piece of code that does sth is
always good ...

We might turn operand_equal_p to a worker (template?) that
operand_equal_p and gimple_operand_equal_p can share (with an extra
flag whether to turn on GIMPLE stuff and/or valueization).  And
then simply provide explicit instantiations for the original
operand_equal_p and a new gimple_operand_equal_p.

Of course we'll only know if we like that when seeing a patch that
does this ;0)

Richard.

Re: [RFC] operand_equal_p with valueization

[Jan Hubicka]

 On Fri, 22 May 2015, Jan Hubicka wrote:
 
   
   And no, I'm hesitant to change operand_equal_p too much.  It's
   very much deep-rooted into GENERIC.
  
  OK, as another option, i can bring relevant logic from operand_equal_p
  to ipa-icf and separate it into the compare_operand class like I did.
  Use it in ipa-icf-gimple now and we can slowly turn other uses of
  operand_equal into the compare_operand users in middle end.
  
  I agree that operand_equal is bit crazy code and it does not handle quite 
  few
  things we could do at gimple.  I have nothing against going this direction.
  (after all I do not like touching fold-const much becuase it works on 
  generic,
  gimple and FE non-generic and it is not well specified what it should do)
 
 Yes, I've played with the idea of a GIMPLE specific operand_equal_p 
 multiple times but then the changes required to operand_equal_p were
 small all the times.  And having one piece of code that does sth is
 always good ...
 
 We might turn operand_equal_p to a worker (template?) that

Hmm, OK that is precisely what I was shooting for by this patch.  I went by
wrapping it to a class with valueize helper.  It can be template, too, just it
semed that having the single valueize function lets me do everything I need
without actually needing to duplicate the code.

I can get around templatizing it.  Do you have some outline what interface
would seem more fit

 operand_equal_p and gimple_operand_equal_p can share (with an extra
 flag whether to turn on GIMPLE stuff and/or valueization).  And
 then simply provide explicit instantiations for the original
 operand_equal_p and a new gimple_operand_equal_p.
 
 Of course we'll only know if we like that when seeing a patch that
 does this ;0)
 
 Richard.

Re: [RFC] operand_equal_p with valueization

[Richard Biener]

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 

Re: [RFC] operand_equal_p with valueization

[Jan Hubicka]

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

OK, as another option, i can bring relevant logic from operand_equal_p
to ipa-icf and separate it into the compare_operand class like I did.
Use it in ipa-icf-gimple now and we can slowly turn other uses of
operand_equal into the compare_operand users in middle end.

I agree that operand_equal is bit crazy code and it does not handle quite few
things we could do at gimple.  I have nothing against going this direction.
(after all I do not like touching fold-const much becuase it works on generic,
gimple and FE non-generic and it is not well specified what it should do)

Honza