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] Clean up and extend VRP edge-assertion code


Hi,

This patch refactors the VRP edge-assertion code to make it
unconditionally traverse SSA-name definitions in order to find suitable
edge assertions to insert.  Currently SSA-name definitions get traversed
only when the orginal conditional is a bitwise AND or OR operation,
which is a strange restriction.

At the same time, I made a few of the tests for detecting suitable edge
assertions more generic.  Conditionals from which new edge assertions
are deduced include:

    if ((x & y) == C) // edge assertions: x != 0, y != 0

    if (~x == C) // edge assertion: x == ~C

    char y;
    ...
    int x = y;
    if (x == C) // edge assertion: y == (char)C

    int y;
    char x = y;
    if (x != C) // edge assertion: y != (int)C

    unsigned y;
    ...
    unsigned long x = y;
    if (x >= C) // edge assertion: y >= (unsigned)C

    int y;
    ...
    unsigned int x = y;
    if (x == C) // edge assertion: y == (int)C

    int p = q >= r;
    if (!p) // edge assertion: q < r

... and any arbitrary combination of such patterns.

I also added the original testcase that motivated me to extend and
ultimately rewrite this code.

I bootstrapped and regtested an earlier version of this patch on
x86_64-unknown-linux-gnu though I will do so again tonight to make sure.

2014-05-03  Patrick Palka  <patrick@parcs.ath.cx>

	* tree-vrp.c (extract_code_and_val_from_cond_with_ops): Add
	sanity test.
	(register_edge_assert_for, register_edge_assert_for_1,
	register_edge_assert_for_2): Refactor and consolidate
	edge-assertion logic into ...
	(register_edge_assert_for_2): ... here.  Add LIMIT parameter.
	Rename to ...
	(register_edge_assert_for_1): ... this.
---
 gcc/testsuite/gcc.dg/vrp-1.c |  21 ++++
 gcc/tree-vrp.c               | 252 +++++++++++++++++++------------------------
 2 files changed, 134 insertions(+), 139 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/vrp-1.c

diff --git a/gcc/testsuite/gcc.dg/vrp-1.c b/gcc/testsuite/gcc.dg/vrp-1.c
new file mode 100644
index 0000000..6e1c2f1
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vrp-1.c
@@ -0,0 +1,21 @@
+// { dg-options "-O2" }
+
+void runtime_error (void) __attribute__ ((noreturn));
+void compiletime_error (void) __attribute__ ((noreturn, error ("")));
+
+static void
+check_equals (int *x, int y)
+{
+  int __p = *x != y;
+  if (__builtin_constant_p (__p) && __p)
+    compiletime_error (); // { dg-error "call to" }
+  if (__p)
+    runtime_error ();
+}
+
+void
+foo (int *x)
+{
+  check_equals (x, 5);
+  check_equals (x, 10);
+}
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 806221c..0d18b42 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -4721,13 +4721,15 @@ extract_code_and_val_from_cond_with_ops (tree name, enum tree_code cond_code,
       comp_code = swap_tree_comparison (cond_code);
       val = cond_op0;
     }
-  else
+  else if (name == cond_op0)
     {
       /* The comparison is of the form NAME COMP VAL, so the
 	 comparison code remains unchanged.  */
       comp_code = cond_code;
       val = cond_op1;
     }
+  else
+    gcc_unreachable ();
 
   /* Invert the comparison code as necessary.  */
   if (invert)
@@ -4791,19 +4793,33 @@ masked_increment (double_int val, double_int mask, double_int sgnbit,
 }
 
 /* Try to register an edge assertion for SSA name NAME on edge E for
-   the condition COND contributing to the conditional jump pointed to by BSI.
+   the condition COND (composed of COND_CODE, COND_OP0 and COND_OP1)
+   contributing to the conditional jump pointed to by BSI.
+
+   Further, try to recursively register edge assertions for the SSA names in
+   the defining statements of COND's operands.  This recursion is limited by
+   LIMIT.
+
    Invert the condition COND if INVERT is true.
-   Return true if an assertion for NAME could be registered.  */
+   Return true if an assertion is registered.  */
 
 static bool
-register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
-			    enum tree_code cond_code,
+register_edge_assert_for_1 (tree name, edge e, gimple_stmt_iterator bsi,
+			    unsigned int limit, enum tree_code cond_code,
 			    tree cond_op0, tree cond_op1, bool invert)
 {
   tree val;
-  enum tree_code comp_code;
+  enum tree_code comp_code, def_rhs_code;
+  gimple def_stmt;
   bool retval = false;
 
+  if (limit == 0)
+    return false;
+
+  /* We only care about SSA_NAMEs.  */
+  if (TREE_CODE (name) != SSA_NAME)
+    return false;
+
   if (!extract_code_and_val_from_cond_with_ops (name, cond_code,
 						cond_op0,
 						cond_op1,
@@ -5348,99 +5364,110 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
 	}
     }
 
-  return retval;
-}
+  /* If COND is effectively an equality test of an SSA_NAME against
+     the value zero or one, then we may be able to assert values
+     for SSA_NAMEs which flow into COND.  */
 
-/* OP is an operand of a truth value expression which is known to have
-   a particular value.  Register any asserts for OP and for any
-   operands in OP's defining statement.
-
-   If CODE is EQ_EXPR, then we want to register OP is zero (false),
-   if CODE is NE_EXPR, then we want to register OP is nonzero (true).   */
-
-static bool
-register_edge_assert_for_1 (tree op, enum tree_code code,
-			    edge e, gimple_stmt_iterator bsi)
-{
-  bool retval = false;
-  gimple op_def;
-  tree val;
-  enum tree_code rhs_code;
-
-  /* We only care about SSA_NAMEs.  */
-  if (TREE_CODE (op) != SSA_NAME)
-    return false;
-
-  /* We know that OP will have a zero or nonzero value.  If OP is used
-     more than once go ahead and register an assert for OP.  */
-  if (live_on_edge (e, op)
-      && !has_single_use (op))
-    {
-      val = build_int_cst (TREE_TYPE (op), 0);
-      register_new_assert_for (op, op, code, val, NULL, e, bsi);
-      retval = true;
-    }
-
-  /* Now look at how OP is set.  If it's set from a comparison,
-     a truth operation or some bit operations, then we may be able
-     to register information about the operands of that assignment.  */
-  op_def = SSA_NAME_DEF_STMT (op);
-  if (gimple_code (op_def) != GIMPLE_ASSIGN)
+  def_stmt = SSA_NAME_DEF_STMT (name);
+  if (!is_gimple_assign (def_stmt))
     return retval;
 
-  rhs_code = gimple_assign_rhs_code (op_def);
+  def_rhs_code = gimple_assign_rhs_code (def_stmt);
 
-  if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
+  /* In the case of NAME == C != 0 or NAME != 0, for BIT_AND_EXPR defining
+     statement of NAME we can assert that both operands of the BIT_AND_EXPR
+     have nonzero value.  */
+  if (def_rhs_code == BIT_AND_EXPR
+      && ((comp_code == NE_EXPR && integer_zerop (val))
+	  || (comp_code == EQ_EXPR && TREE_CODE (val) == INTEGER_CST
+	      && integer_nonzerop (val))))
     {
-      bool invert = (code == EQ_EXPR ? true : false);
-      tree op0 = gimple_assign_rhs1 (op_def);
-      tree op1 = gimple_assign_rhs2 (op_def);
+      tree op0 = gimple_assign_rhs1 (def_stmt);
+      tree op1 = gimple_assign_rhs2 (def_stmt);
+      tree zero = build_zero_cst (TREE_TYPE (val));
+      retval |= register_edge_assert_for_1 (op0, e, bsi, limit - 1,
+					    NE_EXPR, op0, zero, false);
+      retval |= register_edge_assert_for_1 (op1, e, bsi, limit - 1,
+					    NE_EXPR, op1, zero, false);
+    }
 
-      if (TREE_CODE (op0) == SSA_NAME)
-        retval |= register_edge_assert_for_2 (op0, e, bsi, rhs_code, op0, op1,
-					      invert);
-      if (TREE_CODE (op1) == SSA_NAME)
-        retval |= register_edge_assert_for_2 (op1, e, bsi, rhs_code, op0, op1,
-					      invert);
+  /* In the case of NAME == 0 or NAME != 1, for BIT_IOR_EXPR defining
+     statement of NAME we can assert that both operands of the BIT_IOR_EXPR
+     have zero value.  */
+  if (def_rhs_code == BIT_IOR_EXPR
+      && ((comp_code == EQ_EXPR && integer_zerop (val))
+	  || (comp_code == NE_EXPR && integer_onep (val)
+	      && TYPE_PRECISION (TREE_TYPE (name)) == 1)))
+    {
+      /* For BIT_IOR_EXPR only if NAME == 0 both operands have
+	 necessarily zero value, or if type-precision is one.  */
+      tree op0 = gimple_assign_rhs1 (def_stmt);
+      tree op1 = gimple_assign_rhs2 (def_stmt);
+      tree zero = build_zero_cst (TREE_TYPE (val));
+      retval |= register_edge_assert_for_1 (op0, e, bsi, limit - 1,
+					    EQ_EXPR, op0, zero, false);
+      retval |= register_edge_assert_for_1 (op1, e, bsi, limit - 1,
+					    EQ_EXPR, op1, zero, false);
     }
-  else if ((code == NE_EXPR
-	    && gimple_assign_rhs_code (op_def) == BIT_AND_EXPR)
-	   || (code == EQ_EXPR
-	       && gimple_assign_rhs_code (op_def) == BIT_IOR_EXPR))
+
+  if (def_rhs_code == BIT_NOT_EXPR
+      && (comp_code == EQ_EXPR || comp_code == NE_EXPR)
+      && TREE_CODE (val) == INTEGER_CST)
     {
-      /* Recurse on each operand.  */
-      tree op0 = gimple_assign_rhs1 (op_def);
-      tree op1 = gimple_assign_rhs2 (op_def);
-      if (TREE_CODE (op0) == SSA_NAME
-	  && has_single_use (op0))
-	retval |= register_edge_assert_for_1 (op0, code, e, bsi);
-      if (TREE_CODE (op1) == SSA_NAME
-	  && has_single_use (op1))
-	retval |= register_edge_assert_for_1 (op1, code, e, bsi);
+      /* Recurse, inverting VAL.  */
+      tree rhs = gimple_assign_rhs1 (def_stmt);
+      tree new_val = fold_build1 (BIT_NOT_EXPR, TREE_TYPE (val), val);
+      retval |= register_edge_assert_for_1 (rhs, e, bsi, limit - 1,
+					    comp_code, rhs, new_val, false);
     }
-  else if (gimple_assign_rhs_code (op_def) == BIT_NOT_EXPR
-	   && TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (op_def))) == 1)
+
+  /* In the case of NAME == [01] or NAME != [01], if NAME's defining statement
+     is a TCC_COMPARISON then we can assert the comparison or its negation.  */
+  if (TREE_CODE_CLASS (def_rhs_code) == tcc_comparison
+      && (comp_code == EQ_EXPR || comp_code == NE_EXPR)
+      && (integer_zerop (val) || integer_onep (val)))
     {
-      /* Recurse, flipping CODE.  */
-      code = invert_tree_comparison (code, false);
-      retval |= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def),
-					    code, e, bsi);
+      tree op0 = gimple_assign_rhs1 (def_stmt);
+      tree op1 = gimple_assign_rhs2 (def_stmt);
+      bool invert = false;
+
+      if ((comp_code == EQ_EXPR && integer_zerop (val))
+	  || (comp_code == NE_EXPR && integer_onep (val)))
+	invert = true;
+      retval |= register_edge_assert_for_1 (op0, e, bsi, limit - 1,
+					    def_rhs_code, op0, op1, invert);
+      retval |= register_edge_assert_for_1 (op1, e, bsi, limit - 1,
+					    def_rhs_code, op0, op1, invert);
     }
-  else if (gimple_assign_rhs_code (op_def) == SSA_NAME)
+
+  if (def_rhs_code == SSA_NAME)
     {
       /* Recurse through the copy.  */
-      retval |= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def),
-					    code, e, bsi);
+      tree rhs = gimple_assign_rhs1 (def_stmt);
+      retval |= register_edge_assert_for_1 (rhs, e, bsi, limit - 1,
+					    comp_code, rhs, val, false);
     }
-  else if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (op_def)))
+
+  if (CONVERT_EXPR_CODE_P (def_rhs_code)
+      && TREE_CODE (val) == INTEGER_CST)
     {
-      /* Recurse through the type conversion, unless it is a narrowing
-	 conversion or conversion from non-integral type.  */
-      tree rhs = gimple_assign_rhs1 (op_def);
+      /* Recurse through the type conversion if sensible.  */
+      tree rhs = gimple_assign_rhs1 (def_stmt);
       if (INTEGRAL_TYPE_P (TREE_TYPE (rhs))
-	  && (TYPE_PRECISION (TREE_TYPE (rhs))
-	      <= TYPE_PRECISION (TREE_TYPE (op))))
-	retval |= register_edge_assert_for_1 (rhs, code, e, bsi);
+	  && ((comp_code == EQ_EXPR
+	       && TYPE_PRECISION (TREE_TYPE (name))
+		  >= TYPE_PRECISION (TREE_TYPE (rhs)))
+	      || (comp_code == NE_EXPR
+		  && TYPE_PRECISION (TREE_TYPE (name))
+		     <= TYPE_PRECISION (TREE_TYPE (rhs)))
+	      || ((comp_code == GT_EXPR || comp_code == GE_EXPR)
+		  && TYPE_UNSIGNED (TREE_TYPE (rhs))
+		  && TYPE_UNSIGNED (TREE_TYPE (val)))))
+	{
+	  tree new_val = fold_build1 (CONVERT_EXPR, TREE_TYPE (rhs), val);
+	  retval |= register_edge_assert_for_1 (rhs, e, bsi, limit - 1,
+						comp_code, rhs, new_val, false);
+	}
     }
 
   return retval;
@@ -5455,9 +5482,7 @@ register_edge_assert_for (tree name, edge e, gimple_stmt_iterator si,
 			  enum tree_code cond_code, tree cond_op0,
 			  tree cond_op1)
 {
-  tree val;
-  enum tree_code comp_code;
-  bool retval = false;
+  bool retval;
   bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
 
   /* Do not attempt to infer anything in names that flow through
@@ -5465,60 +5490,9 @@ register_edge_assert_for (tree name, edge e, gimple_stmt_iterator si,
   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
     return false;
 
-  if (!extract_code_and_val_from_cond_with_ops (name, cond_code,
-						cond_op0, cond_op1,
-						is_else_edge,
-						&comp_code, &val))
-    return false;
-
   /* Register ASSERT_EXPRs for name.  */
-  retval |= register_edge_assert_for_2 (name, e, si, cond_code, cond_op0,
-					cond_op1, is_else_edge);
-
-
-  /* If COND is effectively an equality test of an SSA_NAME against
-     the value zero or one, then we may be able to assert values
-     for SSA_NAMEs which flow into COND.  */
-
-  /* In the case of NAME == 1 or NAME != 0, for BIT_AND_EXPR defining
-     statement of NAME we can assert both operands of the BIT_AND_EXPR
-     have nonzero value.  */
-  if (((comp_code == EQ_EXPR && integer_onep (val))
-       || (comp_code == NE_EXPR && integer_zerop (val))))
-    {
-      gimple def_stmt = SSA_NAME_DEF_STMT (name);
-
-      if (is_gimple_assign (def_stmt)
-	  && gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR)
-	{
-	  tree op0 = gimple_assign_rhs1 (def_stmt);
-	  tree op1 = gimple_assign_rhs2 (def_stmt);
-	  retval |= register_edge_assert_for_1 (op0, NE_EXPR, e, si);
-	  retval |= register_edge_assert_for_1 (op1, NE_EXPR, e, si);
-	}
-    }
-
-  /* In the case of NAME == 0 or NAME != 1, for BIT_IOR_EXPR defining
-     statement of NAME we can assert both operands of the BIT_IOR_EXPR
-     have zero value.  */
-  if (((comp_code == EQ_EXPR && integer_zerop (val))
-       || (comp_code == NE_EXPR && integer_onep (val))))
-    {
-      gimple def_stmt = SSA_NAME_DEF_STMT (name);
-
-      /* For BIT_IOR_EXPR only if NAME == 0 both operands have
-	 necessarily zero value, or if type-precision is one.  */
-      if (is_gimple_assign (def_stmt)
-	  && (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR
-	      && (TYPE_PRECISION (TREE_TYPE (name)) == 1
-	          || comp_code == EQ_EXPR)))
-	{
-	  tree op0 = gimple_assign_rhs1 (def_stmt);
-	  tree op1 = gimple_assign_rhs2 (def_stmt);
-	  retval |= register_edge_assert_for_1 (op0, EQ_EXPR, e, si);
-	  retval |= register_edge_assert_for_1 (op1, EQ_EXPR, e, si);
-	}
-    }
+  retval = register_edge_assert_for_1 (name, e, si, 5, cond_code,
+				       cond_op0, cond_op1, is_else_edge);
 
   return retval;
 }
-- 
1.9.2


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