[PATCH] Fix PR85574

[PATCH] Fix PR85574

[Richard Biener]

The following rectifies a change during hash-map intruction which
changed the uncprop operand_equal_p based hash to a pointer-based
hash_map.  That assumes pointer equality between constants which
does not hold since different (but compatible) typed constants
can appear in the IL.  For SSA names the equivalence holds, of course.

Fixing this should increase the number of eliminated const-copies
on edges during out-of-SSA.  It also happens to fix the LTO
bootstrap miscompare of cc1 and friends, but I can't really
explain that.

[LTO] bootstrapped and tested on x86_64-unknown-linux-gnu, applied
to trunk.

Richard.

2019-01-03  Jan Hubicka  <hubicka@ucw.cz>

	PR tree-optimization/85574
	* tree-ssa-uncprop.c (struct equiv_hash_elt): Remove unused
	structure.
	(struct ssa_equip_hash_traits): Declare.
	(val_ssa_equiv): Use custom hash traits using operand_equal_p.

Index: gcc/tree-ssa-uncprop.c
===================================================================
--- gcc/tree-ssa-uncprop.c	(revision 267549)
+++ gcc/tree-ssa-uncprop.c	(working copy)
@@ -268,21 +268,24 @@ associate_equivalences_with_edges (void)
    so with each value we have a list of SSA_NAMEs that have the
    same value.  */
 
-
-/* Main structure for recording equivalences into our hash table.  */
-struct equiv_hash_elt
-{
-  /* The value/key of this entry.  */
-  tree value;
-
-  /* List of SSA_NAMEs which have the same value/key.  */
-  vec<tree> equivalences;
+/* Traits for the hash_map to record the value to SSA name equivalences
+   mapping.  */
+struct ssa_equip_hash_traits : default_hash_traits <tree>
+{
+  static inline hashval_t hash (value_type value)
+    { return iterative_hash_expr (value, 0); }
+  static inline bool equal (value_type existing, value_type candidate)
+    { return operand_equal_p (existing, candidate, 0); }
 };
 
+typedef hash_map<tree, auto_vec<tree>,
+		 simple_hashmap_traits <ssa_equip_hash_traits,
+					auto_vec <tree> > > val_ssa_equiv_t;
+
 /* Global hash table implementing a mapping from invariant values
    to a list of SSA_NAMEs which have the same value.  We might be
    able to reuse tree-vn for this code.  */
-static hash_map<tree, auto_vec<tree> > *val_ssa_equiv;
+val_ssa_equiv_t *val_ssa_equiv;
 
 static void uncprop_into_successor_phis (basic_block);
 
@@ -476,7 +479,7 @@ pass_uncprop::execute (function *fun)
   associate_equivalences_with_edges ();
 
   /* Create our global data structures.  */
-  val_ssa_equiv = new hash_map<tree, auto_vec<tree> > (1024);
+  val_ssa_equiv = new val_ssa_equiv_t (1024);
 
   /* We're going to do a dominator walk, so ensure that we have
      dominance information.  */

Re: [PATCH] Fix PR85574

[Richard Sandiford]

Richard Biener <rguenther@suse.de> writes:
> The following rectifies a change during hash-map intruction which
> changed the uncprop operand_equal_p based hash to a pointer-based
> hash_map.  That assumes pointer equality between constants which
> does not hold since different (but compatible) typed constants
> can appear in the IL.  For SSA names the equivalence holds, of course.
>
> Fixing this should increase the number of eliminated const-copies
> on edges during out-of-SSA.  It also happens to fix the LTO
> bootstrap miscompare of cc1 and friends, but I can't really
> explain that.
>
> [LTO] bootstrapped and tested on x86_64-unknown-linux-gnu, applied
> to trunk.
>
> Richard.
>
> 2019-01-03  Jan Hubicka  <hubicka@ucw.cz>
>
> 	PR tree-optimization/85574
> 	* tree-ssa-uncprop.c (struct equiv_hash_elt): Remove unused
> 	structure.
> 	(struct ssa_equip_hash_traits): Declare.
> 	(val_ssa_equiv): Use custom hash traits using operand_equal_p.
>
> Index: gcc/tree-ssa-uncprop.c
> ===================================================================
> --- gcc/tree-ssa-uncprop.c	(revision 267549)
> +++ gcc/tree-ssa-uncprop.c	(working copy)
> @@ -268,21 +268,24 @@ associate_equivalences_with_edges (void)
>     so with each value we have a list of SSA_NAMEs that have the
>     same value.  */
>  
> -
> -/* Main structure for recording equivalences into our hash table.  */
> -struct equiv_hash_elt
> -{
> -  /* The value/key of this entry.  */
> -  tree value;
> -
> -  /* List of SSA_NAMEs which have the same value/key.  */
> -  vec<tree> equivalences;
> +/* Traits for the hash_map to record the value to SSA name equivalences
> +   mapping.  */
> +struct ssa_equip_hash_traits : default_hash_traits <tree>
> +{
> +  static inline hashval_t hash (value_type value)
> +    { return iterative_hash_expr (value, 0); }
> +  static inline bool equal (value_type existing, value_type candidate)
> +    { return operand_equal_p (existing, candidate, 0); }
>  };

FWIW, this is a dup of tree_operand_hash.

Thanks,
Richard

> +typedef hash_map<tree, auto_vec<tree>,
> +		 simple_hashmap_traits <ssa_equip_hash_traits,
> +					auto_vec <tree> > > val_ssa_equiv_t;
> +
>  /* Global hash table implementing a mapping from invariant values
>     to a list of SSA_NAMEs which have the same value.  We might be
>     able to reuse tree-vn for this code.  */
> -static hash_map<tree, auto_vec<tree> > *val_ssa_equiv;
> +val_ssa_equiv_t *val_ssa_equiv;
>  
>  static void uncprop_into_successor_phis (basic_block);
>  
> @@ -476,7 +479,7 @@ pass_uncprop::execute (function *fun)
>    associate_equivalences_with_edges ();
>  
>    /* Create our global data structures.  */
> -  val_ssa_equiv = new hash_map<tree, auto_vec<tree> > (1024);
> +  val_ssa_equiv = new val_ssa_equiv_t (1024);
>  
>    /* We're going to do a dominator walk, so ensure that we have
>       dominance information.  */

Re: [PATCH] Fix PR85574

[Richard Biener]

On Thu, 3 Jan 2019, Richard Sandiford wrote:

> Richard Biener <rguenther@suse.de> writes:
> > The following rectifies a change during hash-map intruction which
> > changed the uncprop operand_equal_p based hash to a pointer-based
> > hash_map.  That assumes pointer equality between constants which
> > does not hold since different (but compatible) typed constants
> > can appear in the IL.  For SSA names the equivalence holds, of course.
> >
> > Fixing this should increase the number of eliminated const-copies
> > on edges during out-of-SSA.  It also happens to fix the LTO
> > bootstrap miscompare of cc1 and friends, but I can't really
> > explain that.
> >
> > [LTO] bootstrapped and tested on x86_64-unknown-linux-gnu, applied
> > to trunk.
> >
> > Richard.
> >
> > 2019-01-03  Jan Hubicka  <hubicka@ucw.cz>
> >
> > 	PR tree-optimization/85574
> > 	* tree-ssa-uncprop.c (struct equiv_hash_elt): Remove unused
> > 	structure.
> > 	(struct ssa_equip_hash_traits): Declare.
> > 	(val_ssa_equiv): Use custom hash traits using operand_equal_p.
> >
> > Index: gcc/tree-ssa-uncprop.c
> > ===================================================================
> > --- gcc/tree-ssa-uncprop.c	(revision 267549)
> > +++ gcc/tree-ssa-uncprop.c	(working copy)
> > @@ -268,21 +268,24 @@ associate_equivalences_with_edges (void)
> >     so with each value we have a list of SSA_NAMEs that have the
> >     same value.  */
> >  
> > -
> > -/* Main structure for recording equivalences into our hash table.  */
> > -struct equiv_hash_elt
> > -{
> > -  /* The value/key of this entry.  */
> > -  tree value;
> > -
> > -  /* List of SSA_NAMEs which have the same value/key.  */
> > -  vec<tree> equivalences;
> > +/* Traits for the hash_map to record the value to SSA name equivalences
> > +   mapping.  */
> > +struct ssa_equip_hash_traits : default_hash_traits <tree>
> > +{
> > +  static inline hashval_t hash (value_type value)
> > +    { return iterative_hash_expr (value, 0); }
> > +  static inline bool equal (value_type existing, value_type candidate)
> > +    { return operand_equal_p (existing, candidate, 0); }
> >  };
> 
> FWIW, this is a dup of tree_operand_hash.

Indeed.  Testing patch to do the obvious replacement.

Richard.

> Thanks,
> Richard
> 
> > +typedef hash_map<tree, auto_vec<tree>,
> > +		 simple_hashmap_traits <ssa_equip_hash_traits,
> > +					auto_vec <tree> > > val_ssa_equiv_t;
> > +
> >  /* Global hash table implementing a mapping from invariant values
> >     to a list of SSA_NAMEs which have the same value.  We might be
> >     able to reuse tree-vn for this code.  */
> > -static hash_map<tree, auto_vec<tree> > *val_ssa_equiv;
> > +val_ssa_equiv_t *val_ssa_equiv;
> >  
> >  static void uncprop_into_successor_phis (basic_block);
> >  
> > @@ -476,7 +479,7 @@ pass_uncprop::execute (function *fun)
> >    associate_equivalences_with_edges ();
> >  
> >    /* Create our global data structures.  */
> > -  val_ssa_equiv = new hash_map<tree, auto_vec<tree> > (1024);
> > +  val_ssa_equiv = new val_ssa_equiv_t (1024);
> >  
> >    /* We're going to do a dominator walk, so ensure that we have
> >       dominance information.  */
> 
> 

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

Re: [PATCH] Fix PR85574

[Richard Biener]

On Thu, 3 Jan 2019, Richard Biener wrote:

> On Thu, 3 Jan 2019, Richard Sandiford wrote:
> 
> > Richard Biener <rguenther@suse.de> writes:
> > > The following rectifies a change during hash-map intruction which
> > > changed the uncprop operand_equal_p based hash to a pointer-based
> > > hash_map.  That assumes pointer equality between constants which
> > > does not hold since different (but compatible) typed constants
> > > can appear in the IL.  For SSA names the equivalence holds, of course.
> > >
> > > Fixing this should increase the number of eliminated const-copies
> > > on edges during out-of-SSA.  It also happens to fix the LTO
> > > bootstrap miscompare of cc1 and friends, but I can't really
> > > explain that.
> > >
> > > [LTO] bootstrapped and tested on x86_64-unknown-linux-gnu, applied
> > > to trunk.
> > >
> > > Richard.
> > >
> > > 2019-01-03  Jan Hubicka  <hubicka@ucw.cz>
> > >
> > > 	PR tree-optimization/85574
> > > 	* tree-ssa-uncprop.c (struct equiv_hash_elt): Remove unused
> > > 	structure.
> > > 	(struct ssa_equip_hash_traits): Declare.
> > > 	(val_ssa_equiv): Use custom hash traits using operand_equal_p.
> > >
> > > Index: gcc/tree-ssa-uncprop.c
> > > ===================================================================
> > > --- gcc/tree-ssa-uncprop.c	(revision 267549)
> > > +++ gcc/tree-ssa-uncprop.c	(working copy)
> > > @@ -268,21 +268,24 @@ associate_equivalences_with_edges (void)
> > >     so with each value we have a list of SSA_NAMEs that have the
> > >     same value.  */
> > >  
> > > -
> > > -/* Main structure for recording equivalences into our hash table.  */
> > > -struct equiv_hash_elt
> > > -{
> > > -  /* The value/key of this entry.  */
> > > -  tree value;
> > > -
> > > -  /* List of SSA_NAMEs which have the same value/key.  */
> > > -  vec<tree> equivalences;
> > > +/* Traits for the hash_map to record the value to SSA name equivalences
> > > +   mapping.  */
> > > +struct ssa_equip_hash_traits : default_hash_traits <tree>
> > > +{
> > > +  static inline hashval_t hash (value_type value)
> > > +    { return iterative_hash_expr (value, 0); }
> > > +  static inline bool equal (value_type existing, value_type candidate)
> > > +    { return operand_equal_p (existing, candidate, 0); }
> > >  };
> > 
> > FWIW, this is a dup of tree_operand_hash.
> 
> Indeed.  Testing patch to do the obvious replacement.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

Richard.

2019-01-07  Richard Biener  <rguenther@suse.de>

	* tree-ssa-uncprop.c (ssa_equip_hash_traits): Remove in favor
	of tree_operand_hash.

Index: gcc/tree-ssa-uncprop.c
===================================================================
--- gcc/tree-ssa-uncprop.c	(revision 267553)
+++ gcc/tree-ssa-uncprop.c	(working copy)
@@ -268,19 +268,7 @@ associate_equivalences_with_edges (void)
    so with each value we have a list of SSA_NAMEs that have the
    same value.  */
 
-/* Traits for the hash_map to record the value to SSA name equivalences
-   mapping.  */
-struct ssa_equip_hash_traits : default_hash_traits <tree>
-{
-  static inline hashval_t hash (value_type value)
-    { return iterative_hash_expr (value, 0); }
-  static inline bool equal (value_type existing, value_type candidate)
-    { return operand_equal_p (existing, candidate, 0); }
-};
-
-typedef hash_map<tree, auto_vec<tree>,
-		 simple_hashmap_traits <ssa_equip_hash_traits,
-					auto_vec <tree> > > val_ssa_equiv_t;
+typedef hash_map<tree_operand_hash, auto_vec<tree> > val_ssa_equiv_t;
 
 /* Global hash table implementing a mapping from invariant values
    to a list of SSA_NAMEs which have the same value.  We might be

[PATCH] Fix PR85574

[Richard Biener]

The PR correctly notices that we cannot transform -((a-b)/c) to
(b-a)/c if a-b == b-a == INT_MIN because we are then changing
the results sign if c != 1.  Thus the following patch restricts
this transform/predicate further.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.

Richard.

2018-05-04  Richard Biener  <rguenther@suse.de>

	PR middle-end/85574
	* fold-const.c (negate_expr_p): Restrict negation of operand
	zero of a division to when we know that can happen without
	overflow.
	(fold_negate_expr_1): Likewise.

	* gcc.dg/torture/pr85574.c: New testcase.
	* gcc.dg/torture/pr57656.c: Use dg-additional-options.

Index: gcc/testsuite/gcc.dg/torture/pr85574.c
===================================================================
--- gcc/testsuite/gcc.dg/torture/pr85574.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/torture/pr85574.c	(working copy)
@@ -0,0 +1,4 @@
+/* { dg-do run } */
+/* { dg-additional-options "-fwrapv" } */
+
+#include "pr57656.c"
Index: gcc/testsuite/gcc.dg/torture/pr57656.c
===================================================================
--- gcc/testsuite/gcc.dg/torture/pr57656.c	(revision 259879)
+++ gcc/testsuite/gcc.dg/torture/pr57656.c	(working copy)
@@ -1,5 +1,5 @@
 /* { dg-do run } */
-/* { dg-options "-fstrict-overflow" } */
+/* { dg-additional-options "-fstrict-overflow" } */
 
 int main (void)
 {
Index: gcc/fold-const.c
===================================================================
--- gcc/fold-const.c	(revision 259879)
+++ gcc/fold-const.c	(working copy)
@@ -474,12 +474,15 @@ negate_expr_p (tree t)
     case EXACT_DIV_EXPR:
       if (TYPE_UNSIGNED (type))
 	break;
-      if (negate_expr_p (TREE_OPERAND (t, 0)))
+      /* In general we can't negate A in A / B, because if A is INT_MIN and
+         B is not 1 we change the sign of the result.  */
+      if (TREE_CODE (TREE_OPERAND (t, 0)) == INTEGER_CST
+	  && negate_expr_p (TREE_OPERAND (t, 0)))
 	return true;
       /* In general we can't negate B in A / B, because if A is INT_MIN and
 	 B is 1, we may turn this into INT_MIN / -1 which is undefined
 	 and actually traps on some architectures.  */
-      if (! INTEGRAL_TYPE_P (TREE_TYPE (t))
+      if (! ANY_INTEGRAL_TYPE_P (TREE_TYPE (t))
 	  || TYPE_OVERFLOW_WRAPS (TREE_TYPE (t))
 	  || (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST
 	      && ! integer_onep (TREE_OPERAND (t, 1))))
@@ -652,14 +655,17 @@ fold_negate_expr_1 (location_t loc, tree
     case EXACT_DIV_EXPR:
       if (TYPE_UNSIGNED (type))
 	break;
-      if (negate_expr_p (TREE_OPERAND (t, 0)))
+      /* In general we can't negate A in A / B, because if A is INT_MIN and
+	 B is not 1 we change the sign of the result.  */
+      if (TREE_CODE (TREE_OPERAND (t, 0)) == INTEGER_CST
+	  && negate_expr_p (TREE_OPERAND (t, 0)))
 	return fold_build2_loc (loc, TREE_CODE (t), type,
 				negate_expr (TREE_OPERAND (t, 0)),
 				TREE_OPERAND (t, 1));
       /* In general we can't negate B in A / B, because if A is INT_MIN and
 	 B is 1, we may turn this into INT_MIN / -1 which is undefined
 	 and actually traps on some architectures.  */
-      if ((! INTEGRAL_TYPE_P (TREE_TYPE (t))
+      if ((! ANY_INTEGRAL_TYPE_P (TREE_TYPE (t))
 	   || TYPE_OVERFLOW_WRAPS (TREE_TYPE (t))
 	   || (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST
 	       && ! integer_onep (TREE_OPERAND (t, 1))))