[PATCH] Fix PR69983

[PATCH] Fix PR69983

[Richard Biener]

I am testing the following patch to fix PR69983 - SCEV was confused
by a PRE inserted PHI node where it checks for equality of the
evolution of all edges.  After my SCEV fix these have conversions
which are not handled by eq_evolutions_p.

I've noticed the function misses any type compatibility check
and operand_equal_p on INTEGER_CSTs will ignore types.

Also it will give up on SSA names or ADDR_EXPRs which can
occur in both the evolution and init part of SCEVs.  So simply
fall back to operand_equal_p for all bits where we don't expect
any further embeded CHRECs (operand_equal_p does no handle
TREE_CHREC currently).

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

Richard.

2016-03-01  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/69983
	* tree-chrec.c (eq_evolutions_p): Handle conversions, compare
	types and fall back to operand_equal_p.

Index: gcc/tree-chrec.c
===================================================================
*** gcc/tree-chrec.c	(revision 233840)
--- gcc/tree-chrec.c	(working copy)
*************** eq_evolutions_p (const_tree chrec0, cons
*** 1468,1478 ****
    if (chrec0 == chrec1)
      return true;
  
    switch (TREE_CODE (chrec0))
      {
-     case INTEGER_CST:
-       return operand_equal_p (chrec0, chrec1, 0);
- 
      case POLYNOMIAL_CHREC:
        return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
  	      && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
--- 1468,1478 ----
    if (chrec0 == chrec1)
      return true;
  
+   if (! types_compatible_p (TREE_TYPE (chrec0), TREE_TYPE (chrec1)))
+     return false;
+ 
    switch (TREE_CODE (chrec0))
      {
      case POLYNOMIAL_CHREC:
        return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
  	      && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
*************** eq_evolutions_p (const_tree chrec0, cons
*** 1487,1494 ****
  	  && eq_evolutions_p (TREE_OPERAND (chrec0, 1),
  			      TREE_OPERAND (chrec1, 1));
  
      default:
!       return false;
      }
  }
  
--- 1487,1498 ----
  	  && eq_evolutions_p (TREE_OPERAND (chrec0, 1),
  			      TREE_OPERAND (chrec1, 1));
  
+     CASE_CONVERT:
+       return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
+ 			      TREE_OPERAND (chrec1, 0));
+ 
      default:
!       return operand_equal_p (chrec0, chrec1, 0);
      }
  }
  

Re: [PATCH] Fix PR69983

[Richard Biener]

On Mon, 29 Feb 2016, Jakub Jelinek wrote:

> On Mon, Feb 29, 2016 at 04:26:12PM +0100, Richard Biener wrote:
> > *************** get_unary_op (tree name, enum tree_code
> > *** 621,626 ****
> > --- 641,680 ----
> >     return NULL_TREE;
> >   }
> >   
> > + /* Return true if OP1 and OP2 have the same value if casted to either type.  */
> > + 
> > + static bool
> > + ops_equal_values_p (tree op1, tree op2)
> > + {
> > +   if (op1 == op2)
> > +     return true;
> > + 
> > +   if (TREE_CODE (op1) == SSA_NAME)
> > +     {
> > +       gimple *stmt = SSA_NAME_DEF_STMT (op1);
> > +       if (gimple_nop_conversion_p (stmt))
> > + 	{
> > + 	  op1 = gimple_assign_rhs1 (stmt);
> > + 	  if (op1 == op2)
> > + 	    return true;
> > + 	}
> > +     }
> > + 
> > +   if (TREE_CODE (op2) == SSA_NAME)
> > +     {
> > +       gimple *stmt = SSA_NAME_DEF_STMT (op2);
> > +       if (gimple_nop_conversion_p (stmt))
> > + 	{
> > + 	  op2 = gimple_assign_rhs1 (stmt);
> > + 	  if (op1 == op2)
> > + 	    return true;
> > + 	}
> > +     }
> 
> This will not work if you have:
>   x_1 = (nop) x_0;
>   x_2 = (nop) x_1;
> and op1 is x_1 and op2 is x_2 (but will work
> if op1 is x_2 and op1 is x_1).

Hmm, I expected CSE / nop combining to always simplify the above
but yes, given we want to catch IVOPTs introduced expressions here
and no CSE / forwprop between it and the reassoc it makes sense
to catch that as well.

> Wouldn't it be better to also remember the original
> tree orig_op1 = op1;
> at the beginning and in the last comparison do
> if (op1 == op2 || orig_op1 == op2)
> ?

Will do as followup now.

Thanks,
Richard.

Re: [PATCH] Fix PR69983

[Jakub Jelinek]

On Mon, Feb 29, 2016 at 04:26:12PM +0100, Richard Biener wrote:
> *************** get_unary_op (tree name, enum tree_code
> *** 621,626 ****
> --- 641,680 ----
>     return NULL_TREE;
>   }
>   
> + /* Return true if OP1 and OP2 have the same value if casted to either type.  */
> + 
> + static bool
> + ops_equal_values_p (tree op1, tree op2)
> + {
> +   if (op1 == op2)
> +     return true;
> + 
> +   if (TREE_CODE (op1) == SSA_NAME)
> +     {
> +       gimple *stmt = SSA_NAME_DEF_STMT (op1);
> +       if (gimple_nop_conversion_p (stmt))
> + 	{
> + 	  op1 = gimple_assign_rhs1 (stmt);
> + 	  if (op1 == op2)
> + 	    return true;
> + 	}
> +     }
> + 
> +   if (TREE_CODE (op2) == SSA_NAME)
> +     {
> +       gimple *stmt = SSA_NAME_DEF_STMT (op2);
> +       if (gimple_nop_conversion_p (stmt))
> + 	{
> + 	  op2 = gimple_assign_rhs1 (stmt);
> + 	  if (op1 == op2)
> + 	    return true;
> + 	}
> +     }

This will not work if you have:
  x_1 = (nop) x_0;
  x_2 = (nop) x_1;
and op1 is x_1 and op2 is x_2 (but will work
if op1 is x_2 and op1 is x_1).
Wouldn't it be better to also remember the original
tree orig_op1 = op1;
at the beginning and in the last comparison do
if (op1 == op2 || orig_op1 == op2)
?

	Jakub

[PATCH] Fix PR69983

[Richard Biener]

This fixes fallout of my SCEV correctness change where reassoc no longer
sees the ~A + A simplification opportunity due to casts that are in the 
way.

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

Richard.

2016-02-29  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/69994
	* tree-ssa-reassoc.c (gimple_nop_conversion_p): New function.
	(get_unary_op): Look through nop conversions.
	(ops_equal_values_p): New function, look for equality diregarding
	nop conversions.
	(eliminate_plus_minus_pair): Use ops_equal_values_p
	(repropagate_negates): Do not use get_unary_op here.

Index: gcc/tree-ssa-reassoc.c
===================================================================
*** gcc/tree-ssa-reassoc.c	(revision 233803)
--- gcc/tree-ssa-reassoc.c	(working copy)
*************** is_reassociable_op (gimple *stmt, enum t
*** 605,610 ****
--- 605,625 ----
  }
  
  
+ /* Return true if STMT is a nop-conversion.  */
+ 
+ static bool
+ gimple_nop_conversion_p (gimple *stmt)
+ {
+   if (gassign *ass = dyn_cast <gassign *> (stmt))
+     {
+       if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (ass))
+ 	  && tree_nop_conversion_p (TREE_TYPE (gimple_assign_lhs (ass)),
+ 				    TREE_TYPE (gimple_assign_rhs1 (ass))))
+ 	return true;
+     }
+   return false;
+ }
+ 
  /* Given NAME, if NAME is defined by a unary operation OPCODE, return the
     operand of the negate operation.  Otherwise, return NULL.  */
  
*************** get_unary_op (tree name, enum tree_code
*** 613,618 ****
--- 628,638 ----
  {
    gimple *stmt = SSA_NAME_DEF_STMT (name);
  
+   /* Look through nop conversions (sign changes).  */
+   if (gimple_nop_conversion_p (stmt)
+       && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
+     stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
+ 
    if (!is_gimple_assign (stmt))
      return NULL_TREE;
  
*************** get_unary_op (tree name, enum tree_code
*** 621,626 ****
--- 641,680 ----
    return NULL_TREE;
  }
  
+ /* Return true if OP1 and OP2 have the same value if casted to either type.  */
+ 
+ static bool
+ ops_equal_values_p (tree op1, tree op2)
+ {
+   if (op1 == op2)
+     return true;
+ 
+   if (TREE_CODE (op1) == SSA_NAME)
+     {
+       gimple *stmt = SSA_NAME_DEF_STMT (op1);
+       if (gimple_nop_conversion_p (stmt))
+ 	{
+ 	  op1 = gimple_assign_rhs1 (stmt);
+ 	  if (op1 == op2)
+ 	    return true;
+ 	}
+     }
+ 
+   if (TREE_CODE (op2) == SSA_NAME)
+     {
+       gimple *stmt = SSA_NAME_DEF_STMT (op2);
+       if (gimple_nop_conversion_p (stmt))
+ 	{
+ 	  op2 = gimple_assign_rhs1 (stmt);
+ 	  if (op1 == op2)
+ 	    return true;
+ 	}
+     }
+ 
+   return false;
+ }
+ 
+ 
  /* If CURR and LAST are a pair of ops that OPCODE allows us to
     eliminate through equivalences, do so, remove them from OPS, and
     return true.  Otherwise, return false.  */
*************** eliminate_plus_minus_pair (enum tree_cod
*** 731,739 ****
         && oe->rank >= curr->rank - 1 ;
         i++)
      {
!       if (oe->op == negateop)
  	{
- 
  	  if (dump_file && (dump_flags & TDF_DETAILS))
  	    {
  	      fprintf (dump_file, "Equivalence: ");
--- 785,793 ----
         && oe->rank >= curr->rank - 1 ;
         i++)
      {
!       if (negateop
! 	  && ops_equal_values_p (oe->op, negateop))
  	{
  	  if (dump_file && (dump_flags & TDF_DETAILS))
  	    {
  	      fprintf (dump_file, "Equivalence: ");
*************** eliminate_plus_minus_pair (enum tree_cod
*** 750,756 ****
  
  	  return true;
  	}
!       else if (oe->op == notop)
  	{
  	  tree op_type = TREE_TYPE (oe->op);
  
--- 804,811 ----
  
  	  return true;
  	}
!       else if (notop
! 	       && ops_equal_values_p (oe->op, notop))
  	{
  	  tree op_type = TREE_TYPE (oe->op);
  
*************** eliminate_plus_minus_pair (enum tree_cod
*** 772,780 ****
  	}
      }
  
!   /* CURR->OP is a negate expr in a plus expr: save it for later
!      inspection in repropagate_negates().  */
!   if (negateop != NULL_TREE)
      plus_negates.safe_push (curr->op);
  
    return false;
--- 827,836 ----
  	}
      }
  
!   /* If CURR->OP is a negate expr without nop conversion in a plus expr:
!      save it for later inspection in repropagate_negates().  */
!   if (negateop != NULL_TREE
!       && gimple_assign_rhs_code (SSA_NAME_DEF_STMT (curr->op)) == NEGATE_EXPR)
      plus_negates.safe_push (curr->op);
  
    return false;
*************** repropagate_negates (void)
*** 4211,4217 ****
  	  if (gimple_assign_rhs2 (user) == negate)
  	    {
  	      tree rhs1 = gimple_assign_rhs1 (user);
! 	      tree rhs2 = get_unary_op (negate, NEGATE_EXPR);
  	      gimple_stmt_iterator gsi = gsi_for_stmt (user);
  	      gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, rhs1, rhs2);
  	      update_stmt (user);
--- 4267,4273 ----
  	  if (gimple_assign_rhs2 (user) == negate)
  	    {
  	      tree rhs1 = gimple_assign_rhs1 (user);
! 	      tree rhs2 = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (negate));
  	      gimple_stmt_iterator gsi = gsi_for_stmt (user);
  	      gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, rhs1, rhs2);
  	      update_stmt (user);