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

[Richard Biener <rguenther at suse dot de>]

On Wed, 27 Apr 2016, Jakub Jelinek wrote:

> On Tue, Apr 26, 2016 at 03:02:38PM +0200, Jakub Jelinek wrote:
> > 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?
> 
> With the checking patch I've just posted, I've found two additional issues.
> 
> One is that the patch treated all tcc_comparison class codes by
> canonicalizing them to the lower of the two codes and perhaps swapping the
> arguments.  That is fine for most of the codes, but not for the commutative
> comparisons, because operand_equal_p will return true e.g. for x != y and
> y != y.  So, we need to treat those as commutative.
> 
> And the second issue is in hashing INTEGER_CSTs.  E.g. on
> builtin-arith-overflow-10.c, operand_equal_p returns non-zero for
> DImode 0x8000000000000000 and TImode of the same value, but they weren't
> hashing the same, the former has TREE_INT_CST_NUNITS == 1, the latter
> == 2 (but both have TREE_INT_CST_EXT_NUNITS == 2).
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

Ok.

Thanks,
Richard.

> 2016-04-27  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 23:00:12.238080960 +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:
> -      for (i = 0; i < TREE_INT_CST_NUNITS (t); i++)
> +      gcc_checking_assert (!(flags & OEP_ADDRESS_OF));
> +      for (i = 0; i < TREE_INT_CST_EXT_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 && !commutative_tree_code (code))
> +	{
> +	  /* 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
> 
> 

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