Re: [PATCH] Add a two value VR comparison to two consecutive PHI args optimization (PR tree-optimization/88676, take 2)

[Richard Biener <rguenther@suse.de>]

On Sat, 5 Jan 2019, Jakub Jelinek wrote:

> On Sat, Jan 05, 2019 at 09:51:31AM +0100, Richard Biener wrote:
> > >+  if (TYPE_PRECISION (TREE_TYPE (lhs)) == TYPE_PRECISION (TREE_TYPE
> > >(arg0)))
> > >+    {
> > >+      if (TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE
> > >+	  || !TYPE_OVERFLOW_WRAPS (TREE_TYPE (arg0)))
> > >+	type = TREE_TYPE (lhs);
> > >+      else
> > >+	type = TREE_TYPE (arg0);
> > 
> > This misses some comments. Presumably you want to avoid arithmetic with bool types (or generally non-mode precision types!?).
> 
> Just for bool because the weird semantics it has.  And do as few conversions
> as possible.
> 
> > >+    }
> > >+  else if (TYPE_PRECISION (TREE_TYPE (lhs)) > TYPE_PRECISION
> > >(TREE_TYPE (arg0)))
> > >+    type = TREE_TYPE (lhs);
> > >+  else
> > >+    type = TREE_TYPE (arg0);
> > >+  if (!TYPE_OVERFLOW_WRAPS (type))
> > >+    type = unsigned_type_for (type);
> > 
> > Would doing this unconditionally simplify things? I think "optimizing" the - fwrapv case isn't worth it. 
> 
> I've originally meant to do it only if really needed but then got lazy.
> 
> > >+  tree m = fold_convert (type, wide_int_to_tree (TREE_TYPE (lhs),
> > >min));
> > >+  enum tree_code code;
> > >+  if (tree_int_cst_lt (arg0, arg1))
> > >+    {
> > >+      code = PLUS_EXPR;
> > >+      m = int_const_binop (MINUS_EXPR, fold_convert (type, arg0), m);
> > >+    }
> > >+  else
> > >+    {
> > >+      code = MINUS_EXPR;
> > >+      m = int_const_binop (PLUS_EXPR, fold_convert (type, arg0), m);
> > >+    }
> > 
> > Delay wide-int to tree conversion until here. 
> 
> But by doing these computations on wide-int properly it appears it isn't
> that hard to do.
> 
> Essentially, after conversion to type, lhs is known to be in [min, min+1]
> range and we either want to perform lhs + a or a - lhs.
> If it is in signed type, we need to verify it doesn't overflow, so if
> a is non-negative, make sure (min+1) + a doesn't overflow and if a
> is negative, make sure min + a doesn't overflow.  Similarly, for
> a - lhs case, if min (and min+1) are non-negative, make sure a - (min+1)
> doesn't overflow, and if min is negative (min+1 in that case could be
> negative or 0), make sure a - min doesn't overflow.
> 
> Ok for trunk if it passes bootstrap/regtest?

OK.

Thanks,
Richard.

> I guess I should add more testcases that test these corner cases,
> the boundary cases of overflowing/not overflowing and different precisions
> of the two types.
> 
> 2019-01-05  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR tree-optimization/88676
> 	* tree-ssa-phiopt.c (two_value_replacement): New function.
> 	(tree_ssa_phiopt_worker): Call it.
> 
> 	* gcc.dg/tree-ssa/pr88676.c: New test.
> 	* gcc.dg/pr88676.c: New test.
> 	* gcc.dg/tree-ssa/pr15826.c: Just verify there is no goto,
> 	allow &.
> 
> --- gcc/tree-ssa-phiopt.c.jj	2019-01-04 18:53:11.315322371 +0100
> +++ gcc/tree-ssa-phiopt.c	2019-01-05 13:04:38.185082743 +0100
> @@ -48,6 +48,8 @@ along with GCC; see the file COPYING3.
>  #include "case-cfn-macros.h"
>  
>  static unsigned int tree_ssa_phiopt_worker (bool, bool, bool);
> +static bool two_value_replacement (basic_block, basic_block, edge, gphi *,
> +				   tree, tree);
>  static bool conditional_replacement (basic_block, basic_block,
>  				     edge, edge, gphi *, tree, tree);
>  static gphi *factor_out_conditional_conversion (edge, edge, gphi *, tree, tree,
> @@ -332,8 +334,11 @@ tree_ssa_phiopt_worker (bool do_store_el
>  	    }
>  
>  	  /* Do the replacement of conditional if it can be done.  */
> -	  if (!early_p
> -	      && conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
> +	  if (two_value_replacement (bb, bb1, e2, phi, arg0, arg1))
> +	    cfgchanged = true;
> +	  else if (!early_p
> +		   && conditional_replacement (bb, bb1, e1, e2, phi,
> +					       arg0, arg1))
>  	    cfgchanged = true;
>  	  else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
>  	    cfgchanged = true;
> @@ -572,6 +577,142 @@ factor_out_conditional_conversion (edge
>    return newphi;
>  }
>  
> +/* Optimize
> +   # x_5 in range [cst1, cst2] where cst2 = cst1 + 1
> +   if (x_5 op cstN) # where op is == or != and N is 1 or 2
> +     goto bb3;
> +   else
> +     goto bb4;
> +   bb3:
> +   bb4:
> +   # r_6 = PHI<cst3(2), cst4(3)> # where cst3 == cst4 + 1 or cst4 == cst3 + 1
> +
> +   to r_6 = x_5 + (min (cst3, cst4) - cst1) or
> +   r_6 = (min (cst3, cst4) + cst1) - x_5 depending on op, N and which
> +   of cst3 and cst4 is smaller.  */
> +
> +static bool
> +two_value_replacement (basic_block cond_bb, basic_block middle_bb,
> +		       edge e1, gphi *phi, tree arg0, tree arg1)
> +{
> +  /* Only look for adjacent integer constants.  */
> +  if (!INTEGRAL_TYPE_P (TREE_TYPE (arg0))
> +      || !INTEGRAL_TYPE_P (TREE_TYPE (arg1))
> +      || TREE_CODE (arg0) != INTEGER_CST
> +      || TREE_CODE (arg1) != INTEGER_CST
> +      || (tree_int_cst_lt (arg0, arg1)
> +	  ? wi::to_widest (arg0) + 1 != wi::to_widest (arg1)
> +	  : wi::to_widest (arg1) + 1 != wi::to_widest (arg1)))
> +    return false;
> +
> +  if (!empty_block_p (middle_bb))
> +    return false;
> +
> +  gimple *stmt = last_stmt (cond_bb);
> +  tree lhs = gimple_cond_lhs (stmt);
> +  tree rhs = gimple_cond_rhs (stmt);
> +
> +  if (TREE_CODE (lhs) != SSA_NAME
> +      || !INTEGRAL_TYPE_P (TREE_TYPE (lhs))
> +      || TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE
> +      || TREE_CODE (rhs) != INTEGER_CST)
> +    return false;
> +
> +  switch (gimple_cond_code (stmt))
> +    {
> +    case EQ_EXPR:
> +    case NE_EXPR:
> +      break;
> +    default:
> +      return false;
> +    }
> +
> +  wide_int min, max;
> +  if (get_range_info (lhs, &min, &max) != VR_RANGE
> +      || min + 1 != max
> +      || (wi::to_wide (rhs) != min
> +	  && wi::to_wide (rhs) != max))
> +    return false;
> +
> +  /* We need to know which is the true edge and which is the false
> +     edge so that we know when to invert the condition below.  */
> +  edge true_edge, false_edge;
> +  extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
> +  if ((gimple_cond_code (stmt) == EQ_EXPR)
> +      ^ (wi::to_wide (rhs) == max)
> +      ^ (e1 == false_edge))
> +    std::swap (arg0, arg1);
> +
> +  tree type;
> +  if (TYPE_PRECISION (TREE_TYPE (lhs)) == TYPE_PRECISION (TREE_TYPE (arg0)))
> +    {
> +      /* Avoid performing the arithmetics in bool type which has different
> +	 semantics, otherwise prefer unsigned types from the two with
> +	 the same precision.  */
> +      if (TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE
> +	  || !TYPE_UNSIGNED (TREE_TYPE (arg0)))
> +	type = TREE_TYPE (lhs);
> +      else
> +	type = TREE_TYPE (arg0);
> +    }
> +  else if (TYPE_PRECISION (TREE_TYPE (lhs)) > TYPE_PRECISION (TREE_TYPE (arg0)))
> +    type = TREE_TYPE (lhs);
> +  else
> +    type = TREE_TYPE (arg0);
> +
> +  min = wide_int::from (min, TYPE_PRECISION (type),
> +			TYPE_SIGN (TREE_TYPE (lhs)));
> +  wide_int a = wide_int::from (wi::to_wide (arg0), TYPE_PRECISION (type),
> +			       TYPE_SIGN (TREE_TYPE (arg0)));
> +  enum tree_code code;
> +  wi::overflow_type ovf;
> +  if (tree_int_cst_lt (arg0, arg1))
> +    {
> +      code = PLUS_EXPR;
> +      a -= min;
> +      if (!TYPE_UNSIGNED (type))
> +	{
> +	  /* lhs is known to be in range [min, min+1] and we want to add a
> +	     to it.  Check if that operation can overflow for those 2 values
> +	     and if yes, force unsigned type.  */
> +	  wi::add (min + (wi::neg_p (a) ? 0 : 1), a, SIGNED, &ovf);
> +	  if (ovf)
> +	    type = unsigned_type_for (type);
> +	}
> +    }
> +  else
> +    {
> +      code = MINUS_EXPR;
> +      a += min;
> +      if (!TYPE_UNSIGNED (type))
> +	{
> +	  /* lhs is known to be in range [min, min+1] and we want to subtract
> +	     it from a.  Check if that operation can overflow for those 2
> +	     values and if yes, force unsigned type.  */
> +	  wi::sub (a, min + (wi::neg_p (min) ? 0 : 1), SIGNED, &ovf);
> +	  if (ovf)
> +	    type = unsigned_type_for (type);
> +	}
> +    }
> +
> +  tree arg = wide_int_to_tree (type, a);
> +  gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
> +  if (!useless_type_conversion_p (type, TREE_TYPE (lhs)))
> +    lhs = gimplify_build1 (&gsi, NOP_EXPR, type, lhs);
> +  tree new_rhs;
> +  if (code == PLUS_EXPR)
> +    new_rhs = gimplify_build2 (&gsi, PLUS_EXPR, type, lhs, arg);
> +  else
> +    new_rhs = gimplify_build2 (&gsi, MINUS_EXPR, type, arg, lhs);
> +  if (!useless_type_conversion_p (TREE_TYPE (arg0), type))
> +    new_rhs = gimplify_build1 (&gsi, NOP_EXPR, TREE_TYPE (arg0), new_rhs);
> +
> +  replace_phi_edge_with_variable (cond_bb, e1, phi, new_rhs);
> +
> +  /* Note that we optimized this PHI.  */
> +  return true;
> +}
> +
>  /*  The function conditional_replacement does the main work of doing the
>      conditional replacement.  Return true if the replacement is done.
>      Otherwise return false.
> --- gcc/testsuite/gcc.dg/tree-ssa/pr88676.c.jj	2019-01-05 12:25:32.463958539 +0100
> +++ gcc/testsuite/gcc.dg/tree-ssa/pr88676.c	2019-01-05 12:25:32.463958539 +0100
> @@ -0,0 +1,133 @@
> +/* PR tree-optimization/88676 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +/* { dg-final { scan-tree-dump-not " = PHI <" "optimized" } } */
> +
> +void bar (int, int, int);
> +
> +__attribute__((noipa)) int
> +f1 (unsigned x)
> +{
> +  int r;
> +  if (x >= 2)
> +    __builtin_unreachable ();
> +  switch (x)
> +    {
> +    case 0:
> +      r = 1;
> +      break;
> +    case 1:
> +      r = 2;
> +      break;
> +    default:
> +      r = 0;
> +      break;
> +    }
> +  return r;
> +}
> +
> +__attribute__((noipa)) void
> +f2 (int x)
> +{
> +  int y;
> +  x = (x & 1) + 98;
> +  if (x != 98)
> +    y = 115;
> +  else
> +    y = 116;
> +  bar (x, y, 116);
> +}
> +
> +__attribute__((noipa)) void
> +f3 (int x)
> +{
> +  int y;
> +  x = (x & 1) + 98;
> +  if (x == 98)
> +    y = 115;
> +  else
> +    y = 116;
> +  bar (x, y, 115);
> +}
> +
> +__attribute__((noipa)) void
> +f4 (int x)
> +{
> +  int y;
> +  x = (x & 1) + 98;
> +  if (x != 99)
> +    y = 115;
> +  else
> +    y = 116;
> +  bar (x, y, 115);
> +}
> +
> +__attribute__((noipa)) void
> +f5 (int x)
> +{
> +  int y;
> +  x = (x & 1) + 98;
> +  if (x == 99)
> +    y = 115;
> +  else
> +    y = 116;
> +  bar (x, y, 116);
> +}
> +
> +__attribute__((noipa)) void
> +f6 (int x)
> +{
> +  int y;
> +  x = (x & 1) + 98;
> +  if (x != 98)
> +    y = 116;
> +  else
> +    y = 115;
> +  bar (x, y, 115);
> +}
> +
> +__attribute__((noipa)) void
> +f7 (int x)
> +{
> +  int y;
> +  x = (x & 1) + 98;
> +  if (x == 98)
> +    y = 116;
> +  else
> +    y = 115;
> +  bar (x, y, 116);
> +}
> +
> +__attribute__((noipa)) void
> +f8 (int x)
> +{
> +  int y;
> +  x = (x & 1) + 98;
> +  if (x != 99)
> +    y = 116;
> +  else
> +    y = 115;
> +  bar (x, y, 116);
> +}
> +
> +__attribute__((noipa)) void
> +f9 (int x)
> +{
> +  int y;
> +  x = (x & 1) + 98;
> +  if (x == 99)
> +    y = 116;
> +  else
> +    y = 115;
> +  bar (x, y, 115);
> +}
> +
> +__attribute__((noipa)) int
> +f10 (int x)
> +{
> +  x = (x & 1) + 36;
> +  if (x == 36)
> +    return 85;
> +  else
> +    return 84;
> +}
> --- gcc/testsuite/gcc.dg/pr88676.c.jj	2019-01-05 12:25:32.463958539 +0100
> +++ gcc/testsuite/gcc.dg/pr88676.c	2019-01-05 12:25:32.463958539 +0100
> @@ -0,0 +1,48 @@
> +/* PR tree-optimization/88676 */
> +/* { dg-do run } */
> +/* { dg-options "-O2" } */
> +
> +#include "tree-ssa/pr88676.c"
> +
> +__attribute__((noipa)) void
> +bar (int x, int y, int z)
> +{
> +  if (z != 115 && z != 116)
> +    __builtin_abort ();
> +  if (x == 98)
> +    {
> +      if (y != z)
> +	__builtin_abort ();
> +    }
> +  else if (x != 99)
> +    __builtin_abort ();
> +  else if (z == 115)
> +    {
> +      if (y != 116)
> +	__builtin_abort ();
> +    }
> +  else if (y != 115)
> +    __builtin_abort ();
> +}
> +
> +int
> +main ()
> +{
> +  if (f1 (0) != 1 || f1 (1) != 2)
> +    __builtin_abort ();
> +  int i;
> +  for (i = -12; i < 12; i++)
> +    {
> +      f2 (i);
> +      f3 (i);
> +      f4 (i);
> +      f5 (i);
> +      f6 (i);
> +      f7 (i);
> +      f8 (i);
> +      f9 (i);
> +      if (f10 (i) != ((i & 1) ? 84 : 85))
> +	__builtin_abort ();
> +    }
> +  return 0;
> +}
> --- gcc/testsuite/gcc.dg/tree-ssa/pr15826.c.jj	2016-02-27 07:41:54.377920386 +0100
> +++ gcc/testsuite/gcc.dg/tree-ssa/pr15826.c	2019-01-05 12:25:32.463958539 +0100
> @@ -33,4 +33,4 @@ andrew (struct s *p)
>    return i;
>  }
>  
> -/* { dg-final { scan-tree-dump-times " & | goto " 0 "optimized" } } */
> +/* { dg-final { scan-tree-dump-not "goto " "optimized" } } */
> 
> 
> 	Jakub
> 
> 

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