rtl-optimization/116002 - cselib hash is bad

Message ID 20240719142351.A93A4132CB@imap1.dmz-prg2.suse.org
State New
Headers
Series rtl-optimization/116002 - cselib hash is bad |

Checks

Context Check Description
linaro-tcwg-bot/tcwg_gcc_build--master-arm success Build passed
linaro-tcwg-bot/tcwg_gcc_build--master-aarch64 success Build passed
linaro-tcwg-bot/tcwg_gcc_check--master-arm success Test passed
linaro-tcwg-bot/tcwg_gcc_check--master-aarch64 success Test passed

Commit Message

Richard Biener July 19, 2024, 2:23 p.m. UTC
  The following addresses the bad hash function of cselib which uses
integer plus for merging.  This causes a huge number of collisions
for the testcase in the PR and thus very large compile-time.

The following rewrites it to use inchash, eliding duplicate mixing
of RTX code and mode in some cases and more consistently avoiding
a return value of zero as well as treating zero as fatal.

For cselib_hash_plus_const_int this removes the apparent attempt
of making sure to hash the same as a PLUS as cselib_hash_rtx makes
sure to dispatch to cselib_hash_plus_const_int consistently.

This reduces compile-time for the testcase in the PR from unknown
to 22s and for a reduced testcase from 73s to 9s.  There's another
pending patchset to improve the speed of inchash mixing, but it's
not in the profile for this testcase (PTA pops up now).

The generated code is equal.

Bootstrap and regtest running on x86_64-unknown-linux-gnu.

Any objections?

	PR rtl-optimization/116002
	* cselib.cc (cselib_hash_rtx): Use inchash to get proper mixing.
	Consistently avoid a zero return value when hashing successfully.
	Consistently treat a zero hash value from recursing as fatal.
	(cselib_hash_plus_const_int): Likewise.
---
 gcc/cselib.cc | 195 ++++++++++++++++++++++++++------------------------
 1 file changed, 101 insertions(+), 94 deletions(-)
  

Patch

diff --git a/gcc/cselib.cc b/gcc/cselib.cc
index cbaab7d515c..6b4cdf266f8 100644
--- a/gcc/cselib.cc
+++ b/gcc/cselib.cc
@@ -1266,14 +1266,13 @@  cselib_hash_plus_const_int (rtx x, HOST_WIDE_INT c, int create,
   if (c == 0)
     return e->hash;
 
-  unsigned hash = (unsigned) PLUS + (unsigned) GET_MODE (x);
-  hash += e->hash;
-  unsigned int tem_hash = (unsigned) CONST_INT + (unsigned) VOIDmode;
-  tem_hash += ((unsigned) CONST_INT << 7) + (unsigned HOST_WIDE_INT) c;
-  if (tem_hash == 0)
-    tem_hash = (unsigned int) CONST_INT;
-  hash += tem_hash;
-  return hash ? hash : 1 + (unsigned int) PLUS;
+  inchash::hash hash;
+  hash.add_int (PLUS);
+  hash.add_int (GET_MODE (x));
+  hash.merge_hash (e->hash);
+  hash.add_hwi (c);
+
+  return hash.end () ? hash.end () : 1 + (unsigned int) PLUS;
 }
 
 /* Hash an rtx.  Return 0 if we couldn't hash the rtx.
@@ -1306,10 +1305,11 @@  cselib_hash_rtx (rtx x, int create, machine_mode memmode)
   int i, j;
   enum rtx_code code;
   const char *fmt;
-  unsigned int hash = 0;
+  inchash::hash hash;
 
   code = GET_CODE (x);
-  hash += (unsigned) code + (unsigned) GET_MODE (x);
+  hash.add_int (code);
+  hash.add_int (GET_MODE (x));
 
   switch (code)
     {
@@ -1326,19 +1326,16 @@  cselib_hash_rtx (rtx x, int create, machine_mode memmode)
       return e->hash;
 
     case DEBUG_EXPR:
-      hash += ((unsigned) DEBUG_EXPR << 7)
-	      + DEBUG_TEMP_UID (DEBUG_EXPR_TREE_DECL (x));
-      return hash ? hash : (unsigned int) DEBUG_EXPR;
+      hash.add_int (DEBUG_TEMP_UID (DEBUG_EXPR_TREE_DECL (x)));
+      return hash.end () ? hash.end() : (unsigned int) DEBUG_EXPR;
 
     case DEBUG_IMPLICIT_PTR:
-      hash += ((unsigned) DEBUG_IMPLICIT_PTR << 7)
-	      + DECL_UID (DEBUG_IMPLICIT_PTR_DECL (x));
-      return hash ? hash : (unsigned int) DEBUG_IMPLICIT_PTR;
+      hash.add_int (DECL_UID (DEBUG_IMPLICIT_PTR_DECL (x)));
+      return hash.end () ? hash.end () : (unsigned int) DEBUG_IMPLICIT_PTR;
 
     case DEBUG_PARAMETER_REF:
-      hash += ((unsigned) DEBUG_PARAMETER_REF << 7)
-	      + DECL_UID (DEBUG_PARAMETER_REF_DECL (x));
-      return hash ? hash : (unsigned int) DEBUG_PARAMETER_REF;
+      hash.add_int (DECL_UID (DEBUG_PARAMETER_REF_DECL (x)));
+      return hash.end () ? hash.end () : (unsigned int) DEBUG_PARAMETER_REF;
 
     case ENTRY_VALUE:
       /* ENTRY_VALUEs are function invariant, thus try to avoid
@@ -1347,51 +1344,49 @@  cselib_hash_rtx (rtx x, int create, machine_mode memmode)
 	 ENTRY_VALUE hash would depend on the current value
 	 in some register or memory.  */
       if (REG_P (ENTRY_VALUE_EXP (x)))
-	hash += (unsigned int) REG
-		+ (unsigned int) GET_MODE (ENTRY_VALUE_EXP (x))
-		+ (unsigned int) REGNO (ENTRY_VALUE_EXP (x));
+	hash.add_int ((unsigned int) REG
+		      + (unsigned int) GET_MODE (ENTRY_VALUE_EXP (x))
+		      + (unsigned int) REGNO (ENTRY_VALUE_EXP (x)));
       else if (MEM_P (ENTRY_VALUE_EXP (x))
 	       && REG_P (XEXP (ENTRY_VALUE_EXP (x), 0)))
-	hash += (unsigned int) MEM
-		+ (unsigned int) GET_MODE (XEXP (ENTRY_VALUE_EXP (x), 0))
-		+ (unsigned int) REGNO (XEXP (ENTRY_VALUE_EXP (x), 0));
+	hash.add_int ((unsigned int) MEM
+		      + (unsigned int) GET_MODE (XEXP (ENTRY_VALUE_EXP (x), 0))
+		      + (unsigned int) REGNO (XEXP (ENTRY_VALUE_EXP (x), 0)));
       else
-	hash += cselib_hash_rtx (ENTRY_VALUE_EXP (x), create, memmode);
-      return hash ? hash : (unsigned int) ENTRY_VALUE;
+	hash.add_int (cselib_hash_rtx (ENTRY_VALUE_EXP (x), create, memmode));
+      return hash.end () ? hash.end () : (unsigned int) ENTRY_VALUE;
 
     case CONST_INT:
-      hash += ((unsigned) CONST_INT << 7) + UINTVAL (x);
-      return hash ? hash : (unsigned int) CONST_INT;
+      hash.add_hwi (UINTVAL (x));
+      return hash.end () ? hash.end () : (unsigned int) CONST_INT;
 
     case CONST_WIDE_INT:
       for (i = 0; i < CONST_WIDE_INT_NUNITS (x); i++)
-	hash += CONST_WIDE_INT_ELT (x, i);
-      return hash;
+	hash.add_hwi (CONST_WIDE_INT_ELT (x, i));
+      return hash.end () ? hash.end () : (unsigned int) CONST_WIDE_INT;
 
     case CONST_POLY_INT:
       {
-	inchash::hash h;
-	h.add_int (hash);
 	for (unsigned int i = 0; i < NUM_POLY_INT_COEFFS; ++i)
-	  h.add_wide_int (CONST_POLY_INT_COEFFS (x)[i]);
-	return h.end ();
+	  hash.add_wide_int (CONST_POLY_INT_COEFFS (x)[i]);
+	return hash.end () ? hash.end () : (unsigned int) CONST_POLY_INT;
       }
 
     case CONST_DOUBLE:
       /* This is like the general case, except that it only counts
 	 the integers representing the constant.  */
-      hash += (unsigned) code + (unsigned) GET_MODE (x);
       if (TARGET_SUPPORTS_WIDE_INT == 0 && GET_MODE (x) == VOIDmode)
-	hash += ((unsigned) CONST_DOUBLE_LOW (x)
-		 + (unsigned) CONST_DOUBLE_HIGH (x));
+	{
+	  hash.add_hwi (CONST_DOUBLE_LOW (x));
+	  hash.add_hwi (CONST_DOUBLE_HIGH (x));
+	}
       else
-	hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
-      return hash ? hash : (unsigned int) CONST_DOUBLE;
+	hash.merge_hash (real_hash (CONST_DOUBLE_REAL_VALUE (x)));
+      return hash.end () ? hash.end () : (unsigned int) CONST_DOUBLE;
 
     case CONST_FIXED:
-      hash += (unsigned int) code + (unsigned int) GET_MODE (x);
-      hash += fixed_hash (CONST_FIXED_VALUE (x));
-      return hash ? hash : (unsigned int) CONST_FIXED;
+      hash.merge_hash (fixed_hash (CONST_FIXED_VALUE (x)));
+      return hash.end () ? hash.end () : (unsigned int) CONST_FIXED;
 
     case CONST_VECTOR:
       {
@@ -1403,19 +1398,18 @@  cselib_hash_rtx (rtx x, int create, machine_mode memmode)
 	for (i = 0; i < units; ++i)
 	  {
 	    elt = CONST_VECTOR_ENCODED_ELT (x, i);
-	    hash += cselib_hash_rtx (elt, 0, memmode);
+	    hash.merge_hash (cselib_hash_rtx (elt, 0, memmode));
 	  }
 
-	return hash;
+	return hash.end () ? hash.end () : (unsigned int) CONST_VECTOR;
       }
 
       /* Assume there is only one rtx object for any given label.  */
     case LABEL_REF:
       /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
 	 differences and differences between each stage's debugging dumps.  */
-      hash += (((unsigned int) LABEL_REF << 7)
-	       + CODE_LABEL_NUMBER (label_ref_label (x)));
-      return hash ? hash : (unsigned int) LABEL_REF;
+      hash.add_int (CODE_LABEL_NUMBER (label_ref_label (x)));
+      return hash.end () ? hash.end () : (unsigned int) LABEL_REF;
 
     case SYMBOL_REF:
       {
@@ -1424,51 +1418,69 @@  cselib_hash_rtx (rtx x, int create, machine_mode memmode)
 	   different orders and thus different registers to be used in the
 	   final assembler.  This also avoids differences in the dump files
 	   between various stages.  */
-	unsigned int h = 0;
-	const unsigned char *p = (const unsigned char *) XSTR (x, 0);
+	const char *p = (const char *) XSTR (x, 0);
 
-	while (*p)
-	  h += (h << 7) + *p++; /* ??? revisit */
+	if (*p)
+	  hash.add (p, strlen (p));
 
-	hash += ((unsigned int) SYMBOL_REF << 7) + h;
-	return hash ? hash : (unsigned int) SYMBOL_REF;
+	return hash.end () ? hash.end () : (unsigned int) SYMBOL_REF;
       }
 
     case PRE_DEC:
     case PRE_INC:
-      /* We can't compute these without knowing the MEM mode.  */
-      gcc_assert (memmode != VOIDmode);
-      offset = GET_MODE_SIZE (memmode);
-      if (code == PRE_DEC)
-	offset = -offset;
-      /* Adjust the hash so that (mem:MEMMODE (pre_* (reg))) hashes
-	 like (mem:MEMMODE (plus (reg) (const_int I))).  */
-      if (GET_MODE (x) == Pmode
-	  && (REG_P (XEXP (x, 0))
-	      || MEM_P (XEXP (x, 0))
-	      || GET_CODE (XEXP (x, 0)) == VALUE))
-	{
-	  HOST_WIDE_INT c;
-	  if (offset.is_constant (&c))
-	    return cselib_hash_plus_const_int (XEXP (x, 0),
-					       trunc_int_for_mode (c, Pmode),
-					       create, memmode);
-	}
-      hash = ((unsigned) PLUS + (unsigned) GET_MODE (x)
-	      + cselib_hash_rtx (XEXP (x, 0), create, memmode)
-	      + cselib_hash_rtx (gen_int_mode (offset, GET_MODE (x)),
-				 create, memmode));
-      return hash ? hash : 1 + (unsigned) PLUS;
+      {
+	/* We can't compute these without knowing the MEM mode.  */
+	gcc_assert (memmode != VOIDmode);
+	offset = GET_MODE_SIZE (memmode);
+	if (code == PRE_DEC)
+	  offset = -offset;
+	/* Adjust the hash so that (mem:MEMMODE (pre_* (reg))) hashes
+	   like (mem:MEMMODE (plus (reg) (const_int I))).  */
+	if (GET_MODE (x) == Pmode
+	    && (REG_P (XEXP (x, 0))
+		|| MEM_P (XEXP (x, 0))
+		|| GET_CODE (XEXP (x, 0)) == VALUE))
+	  {
+	    HOST_WIDE_INT c;
+	    if (offset.is_constant (&c))
+	      return cselib_hash_plus_const_int (XEXP (x, 0),
+						 trunc_int_for_mode (c, Pmode),
+						 create, memmode);
+	  }
+
+	unsigned tem_hash = cselib_hash_rtx (XEXP (x, 0), create, memmode);
+	if (tem_hash == 0)
+	  return 0;
+	hash.merge_hash (tem_hash);
+	tem_hash = cselib_hash_rtx (gen_int_mode (offset, GET_MODE (x)),
+				    create, memmode);
+	if (tem_hash == 0)
+	  return 0;
+	hash.merge_hash (tem_hash);
+	return hash.end () ? hash.end () : 1 + (unsigned) PLUS;
+      }
 
     case PRE_MODIFY:
-      gcc_assert (memmode != VOIDmode);
-      return cselib_hash_rtx (XEXP (x, 1), create, memmode);
+      {
+	gcc_assert (memmode != VOIDmode);
+	unsigned tem_hash = cselib_hash_rtx (XEXP (x, 1), create, memmode);
+	if (tem_hash == 0)
+	  return 0;
+	hash.merge_hash (tem_hash);
+	return hash.end () ? hash.end () : 1 + (unsigned) PRE_MODIFY;
+      }
 
     case POST_DEC:
     case POST_INC:
     case POST_MODIFY:
-      gcc_assert (memmode != VOIDmode);
-      return cselib_hash_rtx (XEXP (x, 0), create, memmode);
+      {
+	gcc_assert (memmode != VOIDmode);
+	unsigned tem_hash = cselib_hash_rtx (XEXP (x, 0), create, memmode);
+	if (tem_hash == 0)
+	  return 0;
+	hash.merge_hash (tem_hash);
+	return hash.end () ? hash.end () : 1 + (unsigned) code;
+      }
 
     case PC:
     case CALL:
@@ -1505,11 +1517,9 @@  cselib_hash_rtx (rtx x, int create, machine_mode memmode)
 	  {
 	    rtx tem = XEXP (x, i);
 	    unsigned int tem_hash = cselib_hash_rtx (tem, create, memmode);
-
 	    if (tem_hash == 0)
 	      return 0;
-
-	    hash += tem_hash;
+	    hash.merge_hash (tem_hash);
 	  }
 	  break;
 	case 'E':
@@ -1517,30 +1527,27 @@  cselib_hash_rtx (rtx x, int create, machine_mode memmode)
 	    {
 	      unsigned int tem_hash
 		= cselib_hash_rtx (XVECEXP (x, i, j), create, memmode);
-
 	      if (tem_hash == 0)
 		return 0;
-
-	      hash += tem_hash;
+	      hash.merge_hash (tem_hash);
 	    }
 	  break;
 
 	case 's':
 	  {
-	    const unsigned char *p = (const unsigned char *) XSTR (x, i);
+	    const char *p = (const char *) XSTR (x, i);
 
-	    if (p)
-	      while (*p)
-		hash += *p++;
+	    if (p && *p)
+	      hash.add (p, strlen (p));
 	    break;
 	  }
 
 	case 'i':
-	  hash += XINT (x, i);
+	  hash.add_hwi (XINT (x, i));
 	  break;
 
 	case 'p':
-	  hash += constant_lower_bound (SUBREG_BYTE (x));
+	  hash.add_int (constant_lower_bound (SUBREG_BYTE (x)));
 	  break;
 
 	case '0':
@@ -1553,7 +1560,7 @@  cselib_hash_rtx (rtx x, int create, machine_mode memmode)
 	}
     }
 
-  return hash ? hash : 1 + (unsigned int) GET_CODE (x);
+  return hash.end () ? hash.end () : 1 + (unsigned int) GET_CODE (x);
 }
 
 /* Create a new value structure for VALUE and initialize it.  The mode of the