[optimize3/3] VRP min/max exprs

[optimize3/3] VRP min/max exprs

[Nathan Sidwell]

[-- Attachment #1: Type: text/plain, Size: 524 bytes --]

Richard.
this is the patch for the min/max optimization I was trying to implement before 
getting sidetracked with the phi bug and cleaning the vrp abs optimization.

This patch checks both min and max where both operands have a determined range, 
and the case where the second op is a constant.  When we determine the operand 
values are disjoint (modulo a possible single overlapping value) we replace the 
min or max with the appropriate operand.

booted and tested with the other two patches I just posted.

ok?

nathan

[-- Attachment #2: vrp-min-max.patch --]
[-- Type: text/x-patch, Size: 4150 bytes --]

2015-08-10  Nathan Sidwell  <nathan@acm.org>

	* tree-vrp.c (simplify_min_or_max_using_ranges): New.
	(simplify_stmt_using_ranges): Simplify MIN and MAX exprs.

	testsuite/
	* gcc.dg/vrp-min-max-1.c: New.
	* gcc.dg/vrp-min-max-2.c: New.

Index: tree-vrp.c
===================================================================
--- tree-vrp.c	(revision 226749)
+++ tree-vrp.c	(working copy)
@@ -9145,6 +9145,69 @@ simplify_div_or_mod_using_ranges (gimple
   return false;
 }
 
+/* Simplify a min or max if the ranges of the two operands are
+   disjoint.   Return true if we do simplify.  */
+
+static bool
+simplify_min_or_max_using_ranges (gimple stmt)
+{
+  tree op0 = gimple_assign_rhs1 (stmt);
+  tree op1 = gimple_assign_rhs2 (stmt);
+  bool sop = false;
+  tree val;
+  value_range_t *vr0 = get_value_range (op0);
+
+  if (TREE_CODE (op1) == SSA_NAME)
+    {
+      /* SSA_NAME MIN/MAX SSA_NAME.  Compare ranges.  */
+      value_range_t *vr1 = get_value_range (op1);
+
+      val = compare_ranges (LE_EXPR, vr0, vr1, &sop);
+      if (!val)
+	{
+	  sop = false;
+	  val = compare_ranges (LT_EXPR, vr0, vr1, &sop);
+	}
+    }
+  else
+    {
+      /* SSA_NAME MIN/MAX CONST.  Compare range to value.  */
+      val = compare_range_with_value (LE_EXPR, vr0, op1, &sop);
+      if (!val)
+	{
+	  sop = false;
+	  val = compare_range_with_value (LT_EXPR, vr0, op1, &sop);
+	}
+    }
+
+  if (val)
+    {
+      if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
+	{
+	  location_t location;
+
+	  if (!gimple_has_location (stmt))
+	    location = input_location;
+	  else
+	    location = gimple_location (stmt);
+	  warning_at (location, OPT_Wstrict_overflow,
+		      "assuming signed overflow does not occur when "
+		      "simplifying %<min/max (X,Y)%> to %<X%> or %<Y%>");
+	}
+
+      /* VAL == TRUE -> OP0 < or <= op1
+	 VAL == FALSE -> OP0 > or >= op1.  */
+      tree res = ((gimple_assign_rhs_code (stmt) == MAX_EXPR)
+		  == integer_zerop (val)) ? op0 : op1;
+      gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
+      gimple_assign_set_rhs_from_tree (&gsi, res);
+      update_stmt (stmt);
+      return true;
+    }
+
+  return false;
+}
+
 /* If the operand to an ABS_EXPR is >= 0, then eliminate the
    ABS_EXPR.  If the operand is <= 0, then simplify the
    ABS_EXPR into a NEGATE_EXPR.  */
@@ -9999,6 +10050,13 @@ simplify_stmt_using_ranges (gimple_stmt_
 	    return simplify_float_conversion_using_ranges (gsi, stmt);
 	  break;
 
+	case MIN_EXPR:
+	case MAX_EXPR:
+	  if (TREE_CODE (rhs1) == SSA_NAME
+	      && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
+	    return simplify_min_or_max_using_ranges (stmt);
+	  break;
+
 	default:
 	  break;
 	}
Index: testsuite/gcc.dg/vrp-min-max-1.c
===================================================================
--- testsuite/gcc.dg/vrp-min-max-1.c	(revision 0)
+++ testsuite/gcc.dg/vrp-min-max-1.c	(working copy)
@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp1 -fdump-tree-mergephi2" } */
+
+int bar (void);
+
+int foo1 (int x, int y)
+{
+  if (y < 10) return bar ();
+  if (x > 9) return bar ();
+
+  return x < y ? x : y;
+}
+
+int foo2 (int x, int y)
+{
+  if (y < 10) return bar ();
+  if (x > 9) return bar ();
+
+  return x > y ? x : y;
+}
+
+/* We expect to optimiz min/max in VRP*/
+
+/* { dg-final { scan-tree-dump-times "MIN_EXPR" 1 "mergephi2" } } */
+/* { dg-final { scan-tree-dump-times "MAX_EXPR" 1 "mergephi2" } } */
+/* { dg-final { scan-tree-dump-not "MIN_EXPR" "vrp1" } } */
+/* { dg-final { scan-tree-dump-not "MAX_EXPR" "vrp1" } } */
Index: testsuite/gcc.dg/vrp-min-max-2.c
===================================================================
--- testsuite/gcc.dg/vrp-min-max-2.c	(revision 0)
+++ testsuite/gcc.dg/vrp-min-max-2.c	(working copy)
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp2" } */
+
+int Foo (int X)
+{
+  if (X < 0)
+    X = 0;
+  if (X > 191)
+    X = 191;
+
+  return X << 23;
+}
+
+/* We expect this min/max pair to survive.  */
+
+/* { dg-final { scan-tree-dump-times "MIN_EXPR" 1 "vrp2" } } */
+/* { dg-final { scan-tree-dump-times "MAX_EXPR" 1 "vrp2" } } */

Re: [optimize3/3] VRP min/max exprs

[Richard Biener]

On Mon, 10 Aug 2015, Nathan Sidwell wrote:

> Richard.
> this is the patch for the min/max optimization I was trying to implement
> before getting sidetracked with the phi bug and cleaning the vrp abs
> optimization.
> 
> This patch checks both min and max where both operands have a determined
> range, and the case where the second op is a constant.  When we determine the
> operand values are disjoint (modulo a possible single overlapping value) we
> replace the min or max with the appropriate operand.
> 
> booted and tested with the other two patches I just posted.
> 
> ok?

The patch looks good.  Note that with SSA name operands it can be
still profitable to do compare_range_with_value, esp. if the other
operand has a symbolical range.  See
vrp_evaluate_conditional_warnv_with_ops_using_ranges which actually
implements a nice helper for evaluating comparisons for code-gen
transforms.

So I'd prefer that you'd simply call that instead of deciding for
yourself on SSA name vs. non-SSA name.

Thanks,
Richard.

Re: [optimize3/3] VRP min/max exprs

[Nathan Sidwell]

[-- Attachment #1: Type: text/plain, Size: 441 bytes --]

On 08/11/15 07:41, Richard Biener wrote:

> The patch looks good.  Note that with SSA name operands it can be
> still profitable to do compare_range_with_value, esp. if the other
> operand has a symbolical range.  See
> vrp_evaluate_conditional_warnv_with_ops_using_ranges which actually
> implements a nice helper for evaluating comparisons for code-gen
> transforms.

Ok, like this?  Thanks for your help!

tested on x86_64-linux.

nathan

[-- Attachment #2: vrp-min-max-2.patch --]
[-- Type: text/x-patch, Size: 4019 bytes --]

2015-08-10  Nathan Sidwell  <nathan@acm.org>

	* tree-vrp.c (simplify_min_or_max_using_ranges): New.
	(simplify_stmt_using_ranges): Simplify MIN and MAX exprs.

	testsuite/
	* gcc.dg/vrp-min-max-1.c: New.
	* gcc.dg/vrp-min-max-2.c: New.

Index: tree-vrp.c
===================================================================
--- tree-vrp.c	(revision 226779)
+++ tree-vrp.c	(working copy)
@@ -7466,7 +7466,8 @@ compare_names (enum tree_code comp, tree
   return NULL_TREE;
 }
 
-/* Helper function for vrp_evaluate_conditional_warnv.  */
+/* Helper function for vrp_evaluate_conditional_warnv & other
+   optimizers.  */
 
 static tree
 vrp_evaluate_conditional_warnv_with_ops_using_ranges (enum tree_code code,
@@ -9145,6 +9146,54 @@ simplify_div_or_mod_using_ranges (gimple
   return false;
 }
 
+/* Simplify a min or max if the ranges of the two operands are
+   disjoint.   Return true if we do simplify.  */
+
+static bool
+simplify_min_or_max_using_ranges (gimple stmt)
+{
+  tree op0 = gimple_assign_rhs1 (stmt);
+  tree op1 = gimple_assign_rhs2 (stmt);
+  bool sop = false;
+  tree val;
+
+  val = (vrp_evaluate_conditional_warnv_with_ops_using_ranges
+	 (LE_EXPR, op0, op1, &sop));
+  if (!val)
+    {
+      sop = false;
+      val = (vrp_evaluate_conditional_warnv_with_ops_using_ranges
+	     (LT_EXPR, op0, op1, &sop));
+    }
+
+  if (val)
+    {
+      if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
+	{
+	  location_t location;
+
+	  if (!gimple_has_location (stmt))
+	    location = input_location;
+	  else
+	    location = gimple_location (stmt);
+	  warning_at (location, OPT_Wstrict_overflow,
+		      "assuming signed overflow does not occur when "
+		      "simplifying %<min/max (X,Y)%> to %<X%> or %<Y%>");
+	}
+
+      /* VAL == TRUE -> OP0 < or <= op1
+	 VAL == FALSE -> OP0 > or >= op1.  */
+      tree res = ((gimple_assign_rhs_code (stmt) == MAX_EXPR)
+		  == integer_zerop (val)) ? op0 : op1;
+      gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
+      gimple_assign_set_rhs_from_tree (&gsi, res);
+      update_stmt (stmt);
+      return true;
+    }
+
+  return false;
+}
+
 /* If the operand to an ABS_EXPR is >= 0, then eliminate the
    ABS_EXPR.  If the operand is <= 0, then simplify the
    ABS_EXPR into a NEGATE_EXPR.  */
@@ -9987,6 +10036,11 @@ simplify_stmt_using_ranges (gimple_stmt_
 	    return simplify_float_conversion_using_ranges (gsi, stmt);
 	  break;
 
+	case MIN_EXPR:
+	case MAX_EXPR:
+	  return simplify_min_or_max_using_ranges (stmt);
+	  break;
+
 	default:
 	  break;
 	}
Index: testsuite/gcc.dg/vrp-min-max-1.c
===================================================================
--- testsuite/gcc.dg/vrp-min-max-1.c	(revision 0)
+++ testsuite/gcc.dg/vrp-min-max-1.c	(working copy)
@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp1 -fdump-tree-mergephi2" } */
+
+int bar (void);
+
+int foo1 (int x, int y)
+{
+  if (y < 10) return bar ();
+  if (x > 9) return bar ();
+
+  return x < y ? x : y;
+}
+
+int foo2 (int x, int y)
+{
+  if (y < 10) return bar ();
+  if (x > 9) return bar ();
+
+  return x > y ? x : y;
+}
+
+/* We expect to optimiz min/max in VRP*/
+
+/* { dg-final { scan-tree-dump-times "MIN_EXPR" 1 "mergephi2" } } */
+/* { dg-final { scan-tree-dump-times "MAX_EXPR" 1 "mergephi2" } } */
+/* { dg-final { scan-tree-dump-not "MIN_EXPR" "vrp1" } } */
+/* { dg-final { scan-tree-dump-not "MAX_EXPR" "vrp1" } } */
Index: testsuite/gcc.dg/vrp-min-max-2.c
===================================================================
--- testsuite/gcc.dg/vrp-min-max-2.c	(revision 0)
+++ testsuite/gcc.dg/vrp-min-max-2.c	(working copy)
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp2" } */
+
+int Foo (int X)
+{
+  if (X < 0)
+    X = 0;
+  if (X > 191)
+    X = 191;
+
+  return X << 23;
+}
+
+/* We expect this min/max pair to survive.  */
+
+/* { dg-final { scan-tree-dump-times "MIN_EXPR" 1 "vrp2" } } */
+/* { dg-final { scan-tree-dump-times "MAX_EXPR" 1 "vrp2" } } */

Re: [optimize3/3] VRP min/max exprs

[Richard Biener]

On Tue, 11 Aug 2015, Nathan Sidwell wrote:

> On 08/11/15 07:41, Richard Biener wrote:
> 
> > The patch looks good.  Note that with SSA name operands it can be
> > still profitable to do compare_range_with_value, esp. if the other
> > operand has a symbolical range.  See
> > vrp_evaluate_conditional_warnv_with_ops_using_ranges which actually
> > implements a nice helper for evaluating comparisons for code-gen
> > transforms.
> 
> Ok, like this?  Thanks for your help!
> 
> tested on x86_64-linux.

Ok.

Thanks,
Richard.