public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [RFC] operand_equal_p with valueization
@ 2015-05-22 12:50 Jan Hubicka
  2015-05-22 13:40 ` Richard Biener
  0 siblings, 1 reply; 59+ messages in thread
From: Jan Hubicka @ 2015-05-22 12:50 UTC (permalink / raw)
  To: gcc-patches, rguenther

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.

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");
 

^ permalink raw reply	[flat|nested] 59+ messages in thread

end of thread, other threads:[~2019-10-30 11:54 UTC | newest]

Thread overview: 59+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-05-22 12:50 [RFC] operand_equal_p with valueization Jan Hubicka
2015-05-22 13:40 ` Richard Biener
2015-05-22 14:12   ` Jan Hubicka
2015-05-26  8:18     ` Richard Biener
2015-05-26 19:09       ` Jan Hubicka
2015-05-27  8:49         ` Richard Biener
2019-06-18 11:10           ` [RFC] " Martin Liška
2019-08-06 15:44             ` [PATCH 0/9] IPA ICF overhaul Martin Liska
2019-08-06 15:43               ` [PATCH 1/9] Replace int with boolean in predicate functions Martin Liska
2019-08-07 12:38                 ` Richard Biener
2019-08-06 15:43               ` [PATCH 2/9] operand_equal_p: add support for FIELD_DECL Martin Liska
2019-08-07 12:21                 ` Richard Biener
2019-08-15 14:19                   ` Jan Hubicka
2019-08-16  9:28                     ` Richard Biener
2019-08-16 12:17                       ` Jan Hubicka
2019-09-11 12:58                         ` Martin Liška
2019-08-06 15:43               ` [PATCH 4/9] Strengthen alias_ptr_types_compatible_p in LTO mode Martin Liska
2019-08-07 12:05                 ` Richard Biener
2019-08-08 12:09                   ` Martin Liška
2019-08-09 11:20                     ` Richard Biener
2019-08-06 15:43               ` [PATCH 8/9] Remove comparison for polymorphic types Martin Liska
2019-08-06 15:43               ` [PATCH 7/9] IPA ICF: remove dead code Martin Liska
2019-08-08 14:44                 ` Jeff Law
2019-08-06 15:43               ` [PATCH 6/9] Integrate that for IPA ICF Martin Liska
2019-08-16 11:10                 ` Martin Liška
2019-08-06 15:43               ` [PATCH 5/9] Come up with an abstraction Martin Liska
2019-08-08 16:29                 ` Michael Matz
2019-08-12 11:49                   ` Martin Liška
2019-08-12 12:27                     ` Richard Biener
2019-08-12 12:43                       ` Martin Liška
2019-08-12 13:26                         ` Richard Biener
2019-08-12 14:48                           ` Martin Liška
2019-08-14 13:17                             ` Richard Biener
2019-08-14 13:50                               ` Martin Liška
2019-08-14 14:38                                 ` Richard Biener
2019-08-16 11:06                                   ` Martin Liška
2019-09-18  7:56                                     ` Martin Liška
2019-09-19 11:30                                       ` Richard Biener
2019-08-12 13:40                     ` Michael Matz
2019-08-09 11:48                 ` Richard Biener
2019-08-06 15:43               ` [PATCH 9/9] Remove alias set comparison Martin Liska
2019-08-07 15:58                 ` Martin Sebor
2019-08-08  8:43                   ` Martin Liška
2019-08-08 15:21                     ` Martin Sebor
2019-08-08 14:44                 ` Jeff Law
2019-08-06 15:55               ` [PATCH 3/9] operand_equal_p: add support for OBJ_TYPE_REF Martin Liska
2019-08-07 12:09                 ` Richard Biener
2019-08-15 15:44                   ` Jan Hubicka
2019-08-16  9:25                     ` Richard Biener
2019-08-16 12:11                       ` Jan Hubicka
2019-08-19 14:03                         ` Richard Biener
2019-08-19 15:12                           ` Jan Hubicka
2019-08-20 14:29                             ` Richard Biener
2019-08-20 14:42                               ` Jan Hubicka
2019-09-13 12:30                               ` Martin Liška
2019-09-16  6:45                                 ` Richard Biener
2019-08-16 11:53               ` [PATCH 10/N] Use const_tree more in IPA ICF Martin Liška
2019-08-19 13:57                 ` Richard Biener
2019-10-30 11:54               ` [PATCH 0/9] IPA ICF overhaul Martin Liška

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).