phiopt: Improve minmax optimization [PR95699]

Message ID 20200618093620.GP8462@tucnak
State New
Headers show
Series
  • phiopt: Improve minmax optimization [PR95699]
Related show

Commit Message

Jakub Jelinek via Gcc-patches June 18, 2020, 9:36 a.m.
Hi!

As discussed in the PR, the
x < 0x80000000U to (int) x >= 0
optimization stands in the way of minmax_replacement optimization,
so for comparisons with most of the constants it works well, but when the
above mentioned optimization triggers, it is unable to do it.
The match.pd (cond (cmp (convert? x) c1) (op x c2) c3) -> (op (minmax x c1) c2)
optimization is able to look through that and this patch
teaches minmax_replacement about it too.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

2020-06-18  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/95699
	* tree-ssa-phiopt.c (minmax_replacement): Treat (signed int)x < 0
	as x > INT_MAX and (signed int)x >= 0 as x <= INT_MAX.  Move variable
	declarations to the statements that set them where possible.

	* gcc.dg/tree-ssa/pr95699.c: New test.


	Jakub

Comments

Richard Biener June 18, 2020, 9:59 a.m. | #1
On Thu, 18 Jun 2020, Jakub Jelinek wrote:

> Hi!

> 

> As discussed in the PR, the

> x < 0x80000000U to (int) x >= 0

> optimization stands in the way of minmax_replacement optimization,

> so for comparisons with most of the constants it works well, but when the

> above mentioned optimization triggers, it is unable to do it.

> The match.pd (cond (cmp (convert? x) c1) (op x c2) c3) -> (op (minmax x c1) c2)

> optimization is able to look through that and this patch

> teaches minmax_replacement about it too.

> 

> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?


OK.

I wonder if we can leverage gimple_build or gimple_match_op::resimplify
to move the actual pattern matching to match.pd completely in at least
part of phiopt?  We'd feed a COND_EXPR to the matcher and similar
to maybe_fold_comparisons_from_match_pd we'd need one "on stack"
GIMPLE stmt for the comparison to avoid building it as GENERIC tree
(which for COND_EXPR would of course also work up to now).

Thanks,
Richard.

> 2020-06-18  Jakub Jelinek  <jakub@redhat.com>

> 

> 	PR tree-optimization/95699

> 	* tree-ssa-phiopt.c (minmax_replacement): Treat (signed int)x < 0

> 	as x > INT_MAX and (signed int)x >= 0 as x <= INT_MAX.  Move variable

> 	declarations to the statements that set them where possible.

> 

> 	* gcc.dg/tree-ssa/pr95699.c: New test.

> 

> --- gcc/tree-ssa-phiopt.c.jj	2020-06-05 10:42:40.792893013 +0200

> +++ gcc/tree-ssa-phiopt.c	2020-06-17 13:36:20.600659487 +0200

> @@ -1363,22 +1363,21 @@ minmax_replacement (basic_block cond_bb,

>  		    edge e0, edge e1, gimple *phi,

>  		    tree arg0, tree arg1)

>  {

> -  tree result, type, rhs;

> -  gcond *cond;

> +  tree result;

>    edge true_edge, false_edge;

> -  enum tree_code cmp, minmax, ass_code;

> -  tree smaller, alt_smaller, larger, alt_larger, arg_true, arg_false;

> +  enum tree_code minmax, ass_code;

> +  tree smaller, larger, arg_true, arg_false;

>    gimple_stmt_iterator gsi, gsi_from;

>  

> -  type = TREE_TYPE (PHI_RESULT (phi));

> +  tree type = TREE_TYPE (PHI_RESULT (phi));

>  

>    /* The optimization may be unsafe due to NaNs.  */

>    if (HONOR_NANS (type) || HONOR_SIGNED_ZEROS (type))

>      return false;

>  

> -  cond = as_a <gcond *> (last_stmt (cond_bb));

> -  cmp = gimple_cond_code (cond);

> -  rhs = gimple_cond_rhs (cond);

> +  gcond *cond = as_a <gcond *> (last_stmt (cond_bb));

> +  enum tree_code cmp = gimple_cond_code (cond);

> +  tree rhs = gimple_cond_rhs (cond);

>  

>    /* Turn EQ/NE of extreme values to order comparisons.  */

>    if ((cmp == NE_EXPR || cmp == EQ_EXPR)

> @@ -1401,8 +1400,8 @@ minmax_replacement (basic_block cond_bb,

>  

>    /* This transformation is only valid for order comparisons.  Record which

>       operand is smaller/larger if the result of the comparison is true.  */

> -  alt_smaller = NULL_TREE;

> -  alt_larger = NULL_TREE;

> +  tree alt_smaller = NULL_TREE;

> +  tree alt_larger = NULL_TREE;

>    if (cmp == LT_EXPR || cmp == LE_EXPR)

>      {

>        smaller = gimple_cond_lhs (cond);

> @@ -1463,6 +1462,50 @@ minmax_replacement (basic_block cond_bb,

>    else

>      return false;

>  

> +  /* Handle the special case of (signed_type)x < 0 being equivalent

> +     to x > MAX_VAL(signed_type) and (signed_type)x >= 0 equivalent

> +     to x <= MAX_VAL(signed_type).  */

> +  if ((cmp == GE_EXPR || cmp == LT_EXPR)

> +      && INTEGRAL_TYPE_P (type)

> +      && TYPE_UNSIGNED (type)

> +      && integer_zerop (rhs))

> +    {

> +      tree op = gimple_cond_lhs (cond);

> +      if (TREE_CODE (op) == SSA_NAME

> +	  && INTEGRAL_TYPE_P (TREE_TYPE (op))

> +	  && !TYPE_UNSIGNED (TREE_TYPE (op)))

> +	{

> +	  gimple *def_stmt = SSA_NAME_DEF_STMT (op);

> +	  if (gimple_assign_cast_p (def_stmt))

> +	    {

> +	      tree op1 = gimple_assign_rhs1 (def_stmt);

> +	      if (INTEGRAL_TYPE_P (TREE_TYPE (op1))

> +		  && TYPE_UNSIGNED (TREE_TYPE (op1))

> +		  && (TYPE_PRECISION (TREE_TYPE (op))

> +		      == TYPE_PRECISION (TREE_TYPE (op1)))

> +		  && useless_type_conversion_p (type, TREE_TYPE (op1)))

> +		{

> +		  wide_int w1 = wi::max_value (TREE_TYPE (op));

> +		  wide_int w2 = wi::add (w1, 1);

> +		  if (cmp == LT_EXPR)

> +		    {

> +		      larger = op1;

> +		      smaller = wide_int_to_tree (TREE_TYPE (op1), w1);

> +		      alt_smaller = wide_int_to_tree (TREE_TYPE (op1), w2);

> +		      alt_larger = NULL_TREE;

> +		    }

> +		  else

> +		    {

> +		      smaller = op1;

> +		      larger = wide_int_to_tree (TREE_TYPE (op1), w1);

> +		      alt_larger = wide_int_to_tree (TREE_TYPE (op1), w2);

> +		      alt_smaller = NULL_TREE;

> +		    }

> +		}

> +	    }

> +	}

> +    }

> +

>    /* We need to know which is the true edge and which is the false

>        edge so that we know if have abs or negative abs.  */

>    extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);

> --- gcc/testsuite/gcc.dg/tree-ssa/pr95699.c.jj	2020-06-17 13:45:31.308686080 +0200

> +++ gcc/testsuite/gcc.dg/tree-ssa/pr95699.c	2020-06-17 13:44:29.715577853 +0200

> @@ -0,0 +1,39 @@

> +/* PR tree-optimization/95699 */

> +/* { dg-do compile } */

> +/* { dg-options "-O2 -fdump-tree-optimized" } */

> +/* { dg-final { scan-tree-dump "MAX_EXPR <\[^>\n\r]*9223372036854775807\[^>\n\r]*>" "optimized" } } */

> +/* { dg-final { scan-tree-dump "MAX_EXPR <\[^>\n\r]*9223372036854775808\[^>\n\r]*>" "optimized" } } */

> +/* { dg-final { scan-tree-dump "MIN_EXPR <\[^>\n\r]*9223372036854775807\[^>\n\r]*>" "optimized" } } */

> +/* { dg-final { scan-tree-dump "MIN_EXPR <\[^>\n\r]*9223372036854775808\[^>\n\r]*>" "optimized" } } */

> +

> +unsigned long long

> +f1 (unsigned long long x)

> +{

> +  if (x < 0x7fffffffffffffffULL)

> +    x = 0x7fffffffffffffffULL;

> +  return x;

> +}

> +

> +unsigned long long

> +f2 (unsigned long long x)

> +{

> +  if (x < 0x8000000000000000ULL)

> +    x = 0x8000000000000000ULL;

> +  return x;

> +}

> +

> +unsigned long long

> +f3 (unsigned long long x)

> +{

> +  if (x >= 0x7fffffffffffffffULL)

> +    x = 0x7fffffffffffffffULL;

> +  return x;

> +}

> +

> +unsigned long long

> +f4 (unsigned long long x)

> +{

> +  if (x >= 0x8000000000000000ULL)

> +    x = 0x8000000000000000ULL;

> +  return x;

> +}

> 

> 	Jakub

> 

> 


-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)

Patch

--- gcc/tree-ssa-phiopt.c.jj	2020-06-05 10:42:40.792893013 +0200
+++ gcc/tree-ssa-phiopt.c	2020-06-17 13:36:20.600659487 +0200
@@ -1363,22 +1363,21 @@  minmax_replacement (basic_block cond_bb,
 		    edge e0, edge e1, gimple *phi,
 		    tree arg0, tree arg1)
 {
-  tree result, type, rhs;
-  gcond *cond;
+  tree result;
   edge true_edge, false_edge;
-  enum tree_code cmp, minmax, ass_code;
-  tree smaller, alt_smaller, larger, alt_larger, arg_true, arg_false;
+  enum tree_code minmax, ass_code;
+  tree smaller, larger, arg_true, arg_false;
   gimple_stmt_iterator gsi, gsi_from;
 
-  type = TREE_TYPE (PHI_RESULT (phi));
+  tree type = TREE_TYPE (PHI_RESULT (phi));
 
   /* The optimization may be unsafe due to NaNs.  */
   if (HONOR_NANS (type) || HONOR_SIGNED_ZEROS (type))
     return false;
 
-  cond = as_a <gcond *> (last_stmt (cond_bb));
-  cmp = gimple_cond_code (cond);
-  rhs = gimple_cond_rhs (cond);
+  gcond *cond = as_a <gcond *> (last_stmt (cond_bb));
+  enum tree_code cmp = gimple_cond_code (cond);
+  tree rhs = gimple_cond_rhs (cond);
 
   /* Turn EQ/NE of extreme values to order comparisons.  */
   if ((cmp == NE_EXPR || cmp == EQ_EXPR)
@@ -1401,8 +1400,8 @@  minmax_replacement (basic_block cond_bb,
 
   /* This transformation is only valid for order comparisons.  Record which
      operand is smaller/larger if the result of the comparison is true.  */
-  alt_smaller = NULL_TREE;
-  alt_larger = NULL_TREE;
+  tree alt_smaller = NULL_TREE;
+  tree alt_larger = NULL_TREE;
   if (cmp == LT_EXPR || cmp == LE_EXPR)
     {
       smaller = gimple_cond_lhs (cond);
@@ -1463,6 +1462,50 @@  minmax_replacement (basic_block cond_bb,
   else
     return false;
 
+  /* Handle the special case of (signed_type)x < 0 being equivalent
+     to x > MAX_VAL(signed_type) and (signed_type)x >= 0 equivalent
+     to x <= MAX_VAL(signed_type).  */
+  if ((cmp == GE_EXPR || cmp == LT_EXPR)
+      && INTEGRAL_TYPE_P (type)
+      && TYPE_UNSIGNED (type)
+      && integer_zerop (rhs))
+    {
+      tree op = gimple_cond_lhs (cond);
+      if (TREE_CODE (op) == SSA_NAME
+	  && INTEGRAL_TYPE_P (TREE_TYPE (op))
+	  && !TYPE_UNSIGNED (TREE_TYPE (op)))
+	{
+	  gimple *def_stmt = SSA_NAME_DEF_STMT (op);
+	  if (gimple_assign_cast_p (def_stmt))
+	    {
+	      tree op1 = gimple_assign_rhs1 (def_stmt);
+	      if (INTEGRAL_TYPE_P (TREE_TYPE (op1))
+		  && TYPE_UNSIGNED (TREE_TYPE (op1))
+		  && (TYPE_PRECISION (TREE_TYPE (op))
+		      == TYPE_PRECISION (TREE_TYPE (op1)))
+		  && useless_type_conversion_p (type, TREE_TYPE (op1)))
+		{
+		  wide_int w1 = wi::max_value (TREE_TYPE (op));
+		  wide_int w2 = wi::add (w1, 1);
+		  if (cmp == LT_EXPR)
+		    {
+		      larger = op1;
+		      smaller = wide_int_to_tree (TREE_TYPE (op1), w1);
+		      alt_smaller = wide_int_to_tree (TREE_TYPE (op1), w2);
+		      alt_larger = NULL_TREE;
+		    }
+		  else
+		    {
+		      smaller = op1;
+		      larger = wide_int_to_tree (TREE_TYPE (op1), w1);
+		      alt_larger = wide_int_to_tree (TREE_TYPE (op1), w2);
+		      alt_smaller = NULL_TREE;
+		    }
+		}
+	    }
+	}
+    }
+
   /* We need to know which is the true edge and which is the false
       edge so that we know if have abs or negative abs.  */
   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
--- gcc/testsuite/gcc.dg/tree-ssa/pr95699.c.jj	2020-06-17 13:45:31.308686080 +0200
+++ gcc/testsuite/gcc.dg/tree-ssa/pr95699.c	2020-06-17 13:44:29.715577853 +0200
@@ -0,0 +1,39 @@ 
+/* PR tree-optimization/95699 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* { dg-final { scan-tree-dump "MAX_EXPR <\[^>\n\r]*9223372036854775807\[^>\n\r]*>" "optimized" } } */
+/* { dg-final { scan-tree-dump "MAX_EXPR <\[^>\n\r]*9223372036854775808\[^>\n\r]*>" "optimized" } } */
+/* { dg-final { scan-tree-dump "MIN_EXPR <\[^>\n\r]*9223372036854775807\[^>\n\r]*>" "optimized" } } */
+/* { dg-final { scan-tree-dump "MIN_EXPR <\[^>\n\r]*9223372036854775808\[^>\n\r]*>" "optimized" } } */
+
+unsigned long long
+f1 (unsigned long long x)
+{
+  if (x < 0x7fffffffffffffffULL)
+    x = 0x7fffffffffffffffULL;
+  return x;
+}
+
+unsigned long long
+f2 (unsigned long long x)
+{
+  if (x < 0x8000000000000000ULL)
+    x = 0x8000000000000000ULL;
+  return x;
+}
+
+unsigned long long
+f3 (unsigned long long x)
+{
+  if (x >= 0x7fffffffffffffffULL)
+    x = 0x7fffffffffffffffULL;
+  return x;
+}
+
+unsigned long long
+f4 (unsigned long long x)
+{
+  if (x >= 0x8000000000000000ULL)
+    x = 0x8000000000000000ULL;
+  return x;
+}