[PATCH] Fix up inchash::add_expr to match more closely operand_equal_p (PR sanitizer/70683)

[Jakub Jelinek <jakub at redhat dot com>]

Hi!

As mentioned in the PR, the bug that has been eventually worked around
by making the C++ constexpr hash tables non-deletable is that
operand_equal_p, which is used in lots of hash tables as the equal function
(with last argument 0), may return true, i.e. a match, even for trees that
have different hash values (when iterative_hash_expr is used).

The following (included) patch changes inchash::add_expr, which is the underlying
function, to match what operand_equal_p does more closely, in particular
attempting to make sure that if operand_equal_p returns non-zero, then
the hash must be the same.

I've been using the attached hack; without this patch during x86_64-linux
and i686-linux yes,extra,rtl checking bootstraps there were 66931
notes (surprisingly only from the ivopts and gimple-ssa-strength-reduction
hash tables, no others), with the patch there are none.

Ok for trunk?

The debugging hack is too ugly and slows down the compiler (by artificially
increasing number of collisions), so it is not appropriate, but perhaps we
can add some internal only use OEP_* flag, pass it to the recursive calls
of operand_equal_p and if not set and flag_checking, verify
iterative_hash_expr equality in the outermost call).

2016-04-26  Jakub Jelinek  <jakub@redhat.com>

	PR sanitizer/70683
	* tree.h (inchash::add_expr): Add FLAGS argument.
	* tree.c (inchash::add_expr): Likewise.  If not OEP_ADDRESS_OF,
	use STRIP_NOPS first.  For INTEGER_CST assert not OEP_ADDRESS_OF.
	For REAL_CST and !HONOR_SIGNED_ZEROS (t) hash +/- 0 the same.
	Formatting fix.  Adjust recursive calls.  For tcc_comparison,
	if swap_tree_comparison (code) is smaller than code, hash that
	and arguments in the other order.  Hash CONVERT_EXPR the same
	as NOP_EXPR.  For OEP_ADDRESS_OF hash MEM_REF with 0 offset
	of ADDR_EXPR of decl as the decl itself.  Add or remove
	OEP_ADDRESS_OF from recursive flags as needed.  For
	FMA_EXPR, WIDEN_MULT_{PLUS,MINUS}_EXPR hash the first two
	operands commutatively and only the third one normally.
	For internal CALL_EXPR hash in CALL_EXPR_IFN.

--- gcc/tree.h.jj	2016-04-22 18:21:32.000000000 +0200
+++ gcc/tree.h	2016-04-26 10:59:50.333534452 +0200
@@ -4759,7 +4759,7 @@ extern int simple_cst_equal (const_tree,
 namespace inchash
 {
 
-extern void add_expr (const_tree, hash &);
+extern void add_expr (const_tree, hash &, unsigned int = 0);
 
 }
 
--- gcc/tree.c.jj	2016-04-22 18:21:32.000000000 +0200
+++ gcc/tree.c	2016-04-26 11:20:48.795359078 +0200
@@ -7769,7 +7769,7 @@ namespace inchash
    This function is intended to produce the same hash for expressions which
    would compare equal using operand_equal_p.  */
 void
-add_expr (const_tree t, inchash::hash &hstate)
+add_expr (const_tree t, inchash::hash &hstate, unsigned int flags)
 {
   int i;
   enum tree_code code;
@@ -7781,6 +7781,9 @@ add_expr (const_tree t, inchash::hash &h
       return;
     }
 
+  if (!(flags & OEP_ADDRESS_OF))
+    STRIP_NOPS (t);
+
   code = TREE_CODE (t);
 
   switch (code)
@@ -7791,12 +7794,17 @@ add_expr (const_tree t, inchash::hash &h
       hstate.merge_hash (0);
       return;
     case INTEGER_CST:
+      gcc_checking_assert (!(flags & OEP_ADDRESS_OF));
       for (i = 0; i < TREE_INT_CST_NUNITS (t); i++)
 	hstate.add_wide_int (TREE_INT_CST_ELT (t, i));
       return;
     case REAL_CST:
       {
-	unsigned int val2 = real_hash (TREE_REAL_CST_PTR (t));
+	unsigned int val2;
+	if (!HONOR_SIGNED_ZEROS (t) && real_zerop (t))
+	  val2 = rvc_zero;
+	else
+	  val2 = real_hash (TREE_REAL_CST_PTR (t));
 	hstate.merge_hash (val2);
 	return;
       }
@@ -7807,17 +7815,18 @@ add_expr (const_tree t, inchash::hash &h
 	return;
       }
     case STRING_CST:
-      hstate.add ((const void *) TREE_STRING_POINTER (t), TREE_STRING_LENGTH (t));
+      hstate.add ((const void *) TREE_STRING_POINTER (t),
+		  TREE_STRING_LENGTH (t));
       return;
     case COMPLEX_CST:
-      inchash::add_expr (TREE_REALPART (t), hstate);
-      inchash::add_expr (TREE_IMAGPART (t), hstate);
+      inchash::add_expr (TREE_REALPART (t), hstate, flags);
+      inchash::add_expr (TREE_IMAGPART (t), hstate, flags);
       return;
     case VECTOR_CST:
       {
 	unsigned i;
 	for (i = 0; i < VECTOR_CST_NELTS (t); ++i)
-	  inchash::add_expr (VECTOR_CST_ELT (t, i), hstate);
+	  inchash::add_expr (VECTOR_CST_ELT (t, i), hstate, flags);
 	return;
       }
     case SSA_NAME:
@@ -7831,16 +7840,17 @@ add_expr (const_tree t, inchash::hash &h
       /* A list of expressions, for a CALL_EXPR or as the elements of a
 	 VECTOR_CST.  */
       for (; t; t = TREE_CHAIN (t))
-	inchash::add_expr (TREE_VALUE (t), hstate);
+	inchash::add_expr (TREE_VALUE (t), hstate, flags);
       return;
     case CONSTRUCTOR:
       {
 	unsigned HOST_WIDE_INT idx;
 	tree field, value;
+	flags &= ~OEP_ADDRESS_OF;
 	FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (t), idx, field, value)
 	  {
-	    inchash::add_expr (field, hstate);
-	    inchash::add_expr (value, hstate);
+	    inchash::add_expr (field, hstate, flags);
+	    inchash::add_expr (value, hstate, flags);
 	  }
 	return;
       }
@@ -7865,21 +7875,102 @@ add_expr (const_tree t, inchash::hash &h
 	  /* DECL's have a unique ID */
 	  hstate.add_wide_int (DECL_UID (t));
 	}
+      else if (tclass == tcc_comparison)
+	{
+	  /* For comparisons that can be swapped, use the lower
+	     tree code.  */
+	  enum tree_code ccode = swap_tree_comparison (code);
+	  if (code < ccode)
+	    ccode = code;
+	  hstate.add_object (ccode);
+	  inchash::add_expr (TREE_OPERAND (t, ccode != code), hstate, flags);
+	  inchash::add_expr (TREE_OPERAND (t, ccode == code), hstate, flags);
+	}
+      else if (CONVERT_EXPR_CODE_P (code))
+	{
+	  /* NOP_EXPR and CONVERT_EXPR are considered equal by
+	     operand_equal_p.  */
+	  enum tree_code ccode = NOP_EXPR;
+	  hstate.add_object (ccode);
+
+	  /* Don't hash the type, that can lead to having nodes which
+	     compare equal according to operand_equal_p, but which
+	     have different hash codes.  Make sure to include signedness
+	     in the hash computation.  */
+	  hstate.add_int (TYPE_UNSIGNED (TREE_TYPE (t)));
+	  inchash::add_expr (TREE_OPERAND (t, 0), hstate, flags);
+	}
+      /* For OEP_ADDRESS_OF, hash MEM_EXPR[&decl, 0] the same as decl.  */
+      else if (code == MEM_REF
+	       && (flags & OEP_ADDRESS_OF) != 0
+	       && TREE_CODE (TREE_OPERAND (t, 0)) == ADDR_EXPR
+	       && DECL_P (TREE_OPERAND (TREE_OPERAND (t, 0), 0))
+	       && integer_zerop (TREE_OPERAND (t, 1)))
+	inchash::add_expr (TREE_OPERAND (TREE_OPERAND (t, 0), 0),
+			   hstate, flags);
       else
 	{
 	  gcc_assert (IS_EXPR_CODE_CLASS (tclass));
+	  unsigned int sflags = flags;
 
 	  hstate.add_object (code);
 
+	  switch (code)
+	    {
+	    case ADDR_EXPR:
+	      gcc_checking_assert (!(flags & OEP_ADDRESS_OF));
+	      flags |= OEP_ADDRESS_OF;
+	      sflags = flags;
+	      break;
+
+	    case INDIRECT_REF:
+	    case MEM_REF:
+	    case TARGET_MEM_REF:
+	      flags &= ~OEP_ADDRESS_OF;
+	      sflags = flags;
+	      break;
+
+	    case ARRAY_REF:
+	    case ARRAY_RANGE_REF:
+	    case COMPONENT_REF:
+	    case BIT_FIELD_REF:
+	      sflags &= ~OEP_ADDRESS_OF;
+	      break;
+
+	    case COND_EXPR:
+	      flags &= ~OEP_ADDRESS_OF;
+	      break;
+
+	    case FMA_EXPR:
+	    case WIDEN_MULT_PLUS_EXPR:
+	    case WIDEN_MULT_MINUS_EXPR:
+	      {
+		/* The multiplication operands are commutative.  */
+		inchash::hash one, two;
+		inchash::add_expr (TREE_OPERAND (t, 0), one, flags);
+		inchash::add_expr (TREE_OPERAND (t, 1), two, flags);
+		hstate.add_commutative (one, two);
+		inchash::add_expr (TREE_OPERAND (t, 2), two, flags);
+		return;
+	      }
+
+	    case CALL_EXPR:
+	      if (CALL_EXPR_FN (t) == NULL_TREE)
+		hstate.add_int (CALL_EXPR_IFN (t));
+	      break;
+
+	    default:
+	      break;
+	    }
+
 	  /* Don't hash the type, that can lead to having nodes which
 	     compare equal according to operand_equal_p, but which
 	     have different hash codes.  */
-	  if (CONVERT_EXPR_CODE_P (code)
-	      || code == NON_LVALUE_EXPR)
+	  if (code == NON_LVALUE_EXPR)
 	    {
 	      /* Make sure to include signness in the hash computation.  */
 	      hstate.add_int (TYPE_UNSIGNED (TREE_TYPE (t)));
-	      inchash::add_expr (TREE_OPERAND (t, 0), hstate);
+	      inchash::add_expr (TREE_OPERAND (t, 0), hstate, flags);
 	    }
 
 	  else if (commutative_tree_code (code))
@@ -7889,13 +7980,14 @@ add_expr (const_tree t, inchash::hash &h
 		 and then rehashing based on the order of their independent
 		 hashes.  */
 	      inchash::hash one, two;
-	      inchash::add_expr (TREE_OPERAND (t, 0), one);
-	      inchash::add_expr (TREE_OPERAND (t, 1), two);
+	      inchash::add_expr (TREE_OPERAND (t, 0), one, flags);
+	      inchash::add_expr (TREE_OPERAND (t, 1), two, flags);
 	      hstate.add_commutative (one, two);
 	    }
 	  else
 	    for (i = TREE_OPERAND_LENGTH (t) - 1; i >= 0; --i)
-	      inchash::add_expr (TREE_OPERAND (t, i), hstate);
+	      inchash::add_expr (TREE_OPERAND (t, i), hstate,
+				 i == 0 ? flags : sflags);
 	}
       return;
     }

	Jakub

Attachment: 1
Description: Text document