This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] Tree-level fix for PR 69526


As described in https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69526, we
currently fail to simplify cases like

(unsigned long)(a - 1) + 1

to

(unsigned long)a

when VRP knows that (a - 1) does not overflow.

This patch introduces a match.pd pattern as well as a helper function
that checks for overflow in a binary operation using VRP information and
simplifies when no overflow is present.

Some effort was put in to stay in the inner type in cases like this

(unsigned long)(a + CST1) - CST2
->
(unsigned long)(a + CST3) rather than
(unsigned long)a + CST3

where abs(CST3) = abs(CST1 - CST) <= abs(CST1). I wonder if this is
warranted, i.e. if it is always advantageous or if the evaluation should
rather involve a cost estimation - e.g. distinguish between costs for
operations in int vs. in long.

Absence of signed overflow is also exploited:

(long)(a + 2) - 1
->
(long)(a + 1)

Bootstrapped and regression tested on s390x and x86_64.

Regards
 Robin
diff --git a/gcc/match.pd b/gcc/match.pd
index b24bfb4..87925e0 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1119,6 +1119,124 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
    (minus @0 (minus @0 @1))
    @1)
 
+  /* ((T)(A +- CST)) +- CST -> (T)(A +- CST)  */
+#if GIMPLE
+   (for outer_op (plus minus)
+     (for inner_op (plus minus)
+       (simplify
+	 (outer_op (convert (inner_op@3 @0 INTEGER_CST@1)) INTEGER_CST@2)
+	   (with
+	    {
+	   /* If the inner operation is wrapped inside a conversion, we have to
+	      check it overflows/underflows and can only then perform the
+	      simplification, i.e. add the second constant to the first
+	      (wrapped) and convert afterwards.  This fixes
+	      https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69526 */
+
+	    bool inner_ovf = false;
+	    bool combined_ovf = false;
+	    bool combined_ovf2 = false;
+	    bool need_outer = false;
+	    tree cst = NULL_TREE;
+	    tree cst_inner = NULL_TREE;
+	    bool combine_constants = false;
+
+	    tree inner_type = TREE_TYPE (@3);
+	    // check overflow in wrapped binop?
+	    bool check_inner_ovf = !TYPE_OVERFLOW_UNDEFINED (inner_type);
+	    // check overflow when combining constants
+	    bool check_combine_ovf = TYPE_OVERFLOW_UNDEFINED (inner_type)
+				    || TYPE_OVERFLOW_UNDEFINED (type);
+
+	    if (check_inner_ovf)
+	      {
+	        // check if the inner binop does not overflow i.e. we have VRP
+	        // information and can prove prove it
+	        inner_ovf = binop_overflow (inner_op, @0, @1, inner_type);
+	      }
+
+	    // check for overflow in combined operation
+	    wide_int combined_cst = wi::add (@1, @2,
+					     TYPE_SIGN (type),
+					     &combined_ovf);
+	    wide_int w1 = @2;
+	    unsigned int prec = w1.get_precision();
+	    unsigned HOST_WIDE_INT tm = 0;
+	    if (tree_fits_uhwi_p (TYPE_MAX_VALUE (inner_type)))
+	      tree_to_uhwi (TYPE_MAX_VALUE (inner_type));
+	    wide_int w2 = wi::uhwi (tm, prec);
+	    if (wi::gtu_p (wi::abs (w1), w2))
+	      combined_ovf = true;
+
+	    wide_int combined_cst_outer = wi::add (@2, @1,
+						   TYPE_SIGN (type),
+						   &combined_ovf2);
+
+	    // the combined constant is ok if its type does not have an
+	    // undefined overflow or one of the combination options does not
+	    // overflow
+	    bool combined_cst_ok = !check_combine_ovf
+	      || !(combined_ovf && combined_ovf2);
+
+	    if (check_inner_ovf ? !inner_ovf && combined_cst_ok :
+		combined_cst_ok)
+	      combine_constants = true;
+
+	    if (combine_constants)
+	      {
+		cst_inner = wide_int_to_tree (inner_type, combined_cst);
+		cst = wide_int_to_tree (type, combined_cst_outer);
+
+		int s1 = tree_int_cst_sgn (@1);
+		int s2 = tree_int_cst_sgn (cst_inner);
+
+		bool not_larger_abs = wi::leu_p (wi::abs (cst_inner),
+						 wi::abs (@1));
+
+		// check for an inner overflow with the combined constant
+		bool inner_ovf2 = binop_overflow (inner_op, @0, cst_inner,
+						  inner_type);
+
+		if (check_inner_ovf ? !inner_ovf2 : not_larger_abs &&
+		    !combined_ovf)
+		  {
+		    cst = cst_inner;
+		  }
+		else
+		  {
+		    // we need the outer type if the signs
+		    // differ i.e. if we had an (a - 2) before and have an
+		    // (a + 1) afterwards since the proved non-overflow
+		    // would not necessarily hold
+		    need_outer = true;
+
+		    // if we overflow in the inner type (with non-undefined
+		    // type) we need to zero-extend the overflowed result
+		    // in the outer type
+		    if (check_inner_ovf && combined_ovf
+			&& tree_fits_uhwi_p (cst_inner))
+		      {
+			HOST_WIDE_INT hw = tree_to_uhwi (cst_inner);
+			wide_int ww = wi::uhwi (hw, TYPE_PRECISION (type));
+			cst = wide_int_to_tree (type, ww);
+		      }
+
+		    // if we need the outer type but the operation overflows
+		    // we cannot do anything
+		    if (combined_ovf2)
+		      combine_constants = false;
+		  }
+	     }
+	  }
+	(if (combine_constants && cst && @0)
+	  (switch
+	   (if (!need_outer)
+	    (convert (outer_op { @0; } { cst; })))
+	   (if (need_outer)
+	    (outer_op (convert { @0; }) { cst; }))
+	   ))))))
+#endif
+
   /* (A +- CST) +- CST -> A + CST  */
   (for outer_op (plus minus)
    (for inner_op (plus minus)
diff --git a/gcc/testsuite/gcc.dg/wrapped-binop-simplify.c b/gcc/testsuite/gcc.dg/wrapped-binop-simplify.c
new file mode 100644
index 0000000..25ffcb5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/wrapped-binop-simplify.c
@@ -0,0 +1,151 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-forwprop1-details -fdump-tree-vrp1-details" } */
+/* { dg-final { scan-tree-dump-times "gimple_simplified to" 11 "forwprop1" } } */
+/* { dg-final { scan-tree-dump-times "gimple_simplified to" 5 "vrp1" } } */
+
+#include <limits.h>
+
+// should simplify, ignore possible signed overflow in (a - 2) and combine
+// constants
+long foo(int a)
+{
+  return (long)(a - 2) + 1;
+}
+
+// should simplify
+long bar(int a)
+{
+  return (long)(a + 3) - 1;
+}
+
+// should simplify with combined constant in outer type
+long baz(int a)
+{
+  return (long)(a - 1) + 2;
+}
+
+// should simplify
+long baf(int a)
+{
+  return (long)(a + 1) - 2;
+}
+
+// should simplify (same as above)
+long bak(int a)
+{
+  return (long)(a + 1) + 3;
+}
+
+// should simplify (same)
+long bal(int a)
+{
+  return (long)(a - 7) - 4;
+}
+
+// should simplify with combined constant in inner type, no overflow in
+// combined constant in inner type (1 - INT_MAX) although it looks like it :)
+long bam(int a)
+{
+  return (long)(a - 1) - INT_MAX;
+}
+
+// should simplify with combined constant in outer type, overflow in
+// combined constant in inner type
+long bam2(int a)
+{
+  return (long)(a + 1) + INT_MAX;
+}
+
+// should simplify with combined constant in outer type, overflow in
+// combined constant in inner type
+long ban(int a)
+{
+  return (long)(a - 1) + INT_MIN;
+}
+
+// should simplify with combined constant in outer type, overflow in
+// combined constant in inner type
+long ban2(int a)
+{
+  return (long)(a + 1) - INT_MIN;
+}
+
+// should not simplify, LONG_MAX doesn't fit in int and combined constant
+// overflows in long
+long bao(int a)
+{
+  return (long)(a + 2) + LONG_MAX;
+}
+
+// should not simplify although at first looks like foo on tree level,
+// but a is promoted to long
+long bas(int a)
+{
+  return (long)(a + UINT_MAX) + 1;
+}
+
+// should not simplify although at first looks like baz on tree level
+unsigned long bat(unsigned int a)
+{
+  return (unsigned long)(a + UINT_MAX) + 2;
+}
+
+// should not simplify (except if (a - 1) does not overflow (via VRP))
+// overflow in combined constant in outer type but type wraps
+unsigned long foo2(unsigned int a)
+{
+  return (unsigned long)(a - 1) + 1;
+}
+
+// should not simplify
+unsigned long bar2(unsigned int a)
+{
+  return (unsigned long)(a + 1) - 1;
+}
+
+// should simplify (same as above with VRP)
+unsigned long oof2(unsigned int a)
+{
+  if (a > 3 && a < INT_MAX - 100)
+    return (unsigned long)(a - 1) + 1;
+}
+
+// same
+unsigned long bap(unsigned int a)
+{
+  if (a > 3 && a < INT_MAX - 100)
+    return (unsigned long)(a + 1) + ULONG_MAX;
+}
+
+// should simplify
+unsigned long bar3(unsigned int a)
+{
+  if (a > 3 && a < INT_MAX - 100)
+    return (unsigned long)(a + 1) - 5;
+}
+
+// should simplify in outer type as we cannot prove non-overflow
+unsigned long bar4(unsigned int a)
+{
+  if (a > 3 && a < INT_MAX - 100)
+    return (unsigned long)(a + 1) - 6;
+}
+
+// should simplify
+unsigned long baq(int a)
+{
+  return (unsigned long)(a - 2) + 1;
+}
+
+// should not simplify
+long baq2(unsigned int a)
+{
+  return (long)(a - 1) + 1;
+}
+
+// should simplify
+long baq3(unsigned int a)
+{
+  if (a > 3 && a < INT_MAX - 100)
+    return (long)(a - 1) + 1;
+}
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 4333d60..b31f848 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -8906,6 +8906,34 @@ simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
   return true;
 }
 
+/* Simplify ((type) (b +- CST1)) + CST2 to (type) b + (CST1 + CST2)
+   if (b +- CST1) does not underflow.  */
+
+static bool
+simplify_plus_or_minus_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
+{
+  enum tree_code code = gimple_assign_rhs_code (stmt);
+  tree op0 = gimple_assign_rhs1 (stmt);
+  tree op1 = gimple_assign_rhs2 (stmt);
+
+  if ((code == PLUS_EXPR || code == MINUS_EXPR) &&
+      op0 != NULL && op1 != NULL)
+    {
+      gimple *stmt1 = SSA_NAME_DEF_STMT (op0);
+      if (gassign *def = dyn_cast <gassign *> (stmt1))
+	{
+	  if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def))
+	      && TREE_CODE (op1) == INTEGER_CST)
+	    {
+	      if (fold_stmt (gsi, follow_single_use_edges))
+		return true;
+	    }
+	}
+    }
+
+  return false;
+}
+
 /* Simplify a division or modulo operator to a right shift or
    bitwise and if the first operand is unsigned or is greater
    than zero and the second operand is an exact power of two.
@@ -9905,6 +9933,12 @@ simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
 	  return simplify_min_or_max_using_ranges (stmt);
 	  break;
 
+	case MINUS_EXPR:
+	case PLUS_EXPR:
+	  if (TREE_CODE (rhs1) == SSA_NAME)
+	    return simplify_plus_or_minus_using_ranges (gsi, stmt);
+	  break;
+
 	default:
 	  break;
 	}
diff --git a/gcc/tree.c b/gcc/tree.c
index 2295111..bc477fa 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -1358,6 +1358,108 @@ force_fit_type (tree type, const wide_int_ref &cst,
   return wide_int_to_tree (type, cst);
 }
 
+bool binop_overflow (enum tree_code op, tree t1, tree t2, tree type)
+{
+  if (t1 == NULL_TREE || t2 == NULL_TREE || type == NULL_TREE)
+    return true;
+
+  if (TYPE_OVERFLOW_UNDEFINED (type))
+    return false;
+
+  if (!INTEGRAL_TYPE_P (type))
+    return true;
+
+  if (TREE_CODE (t1) != SSA_NAME)
+    return true;
+
+  if (op != PLUS_EXPR && op != MINUS_EXPR)
+    return true;
+
+  wide_int min1;
+  wide_int max1;
+
+  if (TREE_CODE (t1) != INTEGER_CST)
+    {
+      enum value_range_type vrtype1 = get_range_info (t1, &min1, &max1);
+
+      if (!vrtype1 || (vrtype1 != VR_RANGE && vrtype1 != VR_ANTI_RANGE))
+	return true;
+
+      if (vrtype1 == VR_ANTI_RANGE)
+	{
+	  bool ovf;
+	  wide_int tmpmin = wi::add (min1, 1, TYPE_SIGN (TREE_TYPE (t1)), &ovf);
+	  if (ovf)
+	    return true;
+	  wide_int tmpmax = wi::sub (max1, 1, TYPE_SIGN (TREE_TYPE (t1)), &ovf);
+	  if (ovf)
+	    return true;
+	  min1 = tmpmin;
+	  max1 = tmpmax;
+	}
+    }
+  else
+    {
+      min1 = t1;
+      max1 = t1;
+    }
+
+  wide_int min2;
+  wide_int max2;
+
+  if (TREE_CODE (t2) != INTEGER_CST)
+    {
+      enum value_range_type vrtype2 = get_range_info (t2, &min2, &max2);
+
+      if (!vrtype2 || (vrtype2 != VR_RANGE && vrtype2 != VR_ANTI_RANGE))
+	return true;
+
+      if (vrtype2 == VR_ANTI_RANGE)
+	{
+	  bool ovf;
+	  wide_int tmpmin = wi::add (min2, 1, TYPE_SIGN (TREE_TYPE (t2)), &ovf);
+	  if (ovf)
+	    return true;
+	  wide_int tmpmax = wi::sub (max2, 1, TYPE_SIGN (TREE_TYPE (t2)), &ovf);
+	  if (ovf)
+	    return true;
+	  min2 = tmpmin;
+	  max2 = tmpmax;
+	}
+    }
+  else
+    {
+      min2 = t2;
+      max2 = t2;
+    }
+
+  wide_int wmin, wmax;
+
+  bool ovf;
+  signop sgned = TYPE_SIGN (TREE_TYPE (t1)) == SIGNED
+    || TYPE_SIGN (TREE_TYPE (t2)) == SIGNED ? SIGNED : UNSIGNED;
+  if (op == MINUS_EXPR)
+    {
+      wmin = wi::sub (min1, min2, sgned, &ovf);
+      if (ovf)
+	return true;
+      wmax = wi::sub (max1, max2, sgned, &ovf);
+      if (ovf)
+	return true;
+    }
+  else
+    {
+      wmin = wi::add (min1, min2, sgned, &ovf);
+      if (ovf)
+	return true;
+      wmax = wi::add (max1, max2, sgned, &ovf);
+      if (ovf)
+	return true;
+    }
+
+  return wi::gt_p (wmin, wmax, TYPE_SIGN (TREE_TYPE (t1)));
+}
+
 /* These are the hash table functions for the hash table of INTEGER_CST
    nodes of a sizetype.  */
 
diff --git a/gcc/tree.h b/gcc/tree.h
index 99ed8ff..641be00 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -5482,4 +5482,7 @@ desired_pro_or_demotion_p (const_tree to_type, const_tree from_type)
   return to_type_precision <= TYPE_PRECISION (from_type);
 }
 
+extern bool
+binop_overflow (enum tree_code op, tree t1, tree t2, tree type);
+
 #endif  /* GCC_TREE_H  */

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]