[RFC] Attacking 79095 -- a new approach

This is an RFC on the updated work for fix 79095.  I've got to work on 
the testcases tomorrow, but wanted to give folks the option for early 
feedback.

There's been a number of ratholes and restarts, but I think where things 
are going now is significantly better than prior work.

The fundamental concept I'm working from now is to avoid rewriting tests 
in the IL and instead extract more precise range information for VRP 
as-if the tests had been rewritten in the IL.  This avoids a slew of 
problems with ADD_OVERFLOW detection.

The better propagated ranges help considerably, but will not eliminate 
the false positives in a slightly modified version of the testcase from 
79095.  Consider:

#include <vector>

void foo(std::vector<unsigned int> &v);

void vtest()
{
   std::vector<unsigned int> v;
   foo (v);
   if (v.size() > 0)
   {
     v.resize (v.size()-1);
   }
}


Note the inclusion of the v.size () > 0 check.  In the original 
testcase, if v.size () is zero, then the warning is warranted.  But with 
the check any warning is a false positive.  Ugh.

So the the key bits from the VRP dump:

;;   basic block 3, loop depth 0, count 0, freq 10000, maybe hot
;;    prev block 2, next block 4, flags: (NEW, REACHABLE, VISITED)
;;    pred:       2 [100.0%]  (FALLTHRU,EXECUTABLE)
   _9 = MEM[(unsigned int * *)&v];
   _10 = MEM[(unsigned int * *)&v + 8B];
   _6 = (long int) _10;
   _11 = (long int) _9;
   _12 = _6 - _11;
   _13 = _12 /[ex] 4;
   _14 = (long unsigned int) _13;
   if (_6 != _11)
     goto <bb 4>; [48.88%]
   else
     goto <bb 11>; [51.12%]
;;    succ:       4 [48.9%]  (TRUE_VALUE,EXECUTABLE)
;;                11 [51.1%]  (FALSE_VALUE,EXECUTABLE)

;;   basic block 4, loop depth 0, count 0, freq 4888, maybe hot
;;    prev block 3, next block 5, flags: (NEW, REACHABLE, VISITED)
;;    pred:       3 [48.9%]  (TRUE_VALUE,EXECUTABLE)
   _1 = _14 + 18446744073709551615;
   if (_1 > _14)
     goto <bb 5>; [29.56%]
   else
     goto <bb 10>; [70.44%]

The TRUE arm of the second conditional contains the code which 
ultimately triggers the warning.  Careful examination would tell us that 
if _6 != _11, then _14 can never have the value 0 which is the only 
value which would result in that second conditional being true.

We had an assert that _6 != _11, but we don't have a back-propagation 
step that would allow us to infer a range for _1 or _14 in BB4 based on 
the _6 != _11 ASSERT_EXPR.  Insert plug here for Andrew's work...


However, through a series of steps between vrp1 and vrp2 we end up with 
this at the start of vrp2:

;;   basic block 3, loop depth 0, count 0, freq 10000, maybe hot
;;    prev block 2, next block 4, flags: (NEW, REACHABLE, VISITED)
;;    pred:       2 [100.0%]  (FALLTHRU,EXECUTABLE)
   _9 = MEM[(unsigned int * *)&v];
   _10 = MEM[(unsigned int * *)&v + 8B];
   _6 = (long int) _10;
   _11 = (long int) _9;
   if (_6 != _11)
     goto <bb 4>; [48.88%]
   else
     goto <bb 10>; [51.12%]
;;    succ:       4 [48.9%]  (TRUE_VALUE,EXECUTABLE)
;;                10 [51.1%]  (FALSE_VALUE,EXECUTABLE)

;;   basic block 4, loop depth 0, count 0, freq 4888, maybe hot
;;    prev block 3, next block 5, flags: (NEW, REACHABLE, VISITED)
;;    pred:       3 [48.9%]  (TRUE_VALUE,EXECUTABLE)
   _12 = _6 - _11;
   _13 = _12 /[ex] 4;
   _14 = (long unsigned int) _13;
   _1 = _14 + 18446744073709551615;
   if (_1 > _14)
     goto <bb 5>; [29.56%]
   else
     goto <bb 9>; [70.44%]

Note how some assignments sunk down into BB4.  And recall that we'll get 
a suitable ASSERT_EXPR indicating _6 != _11 at the start of BB4.  We can 
work with that.

What we have here is the IL in a form where we don't need any 
back-propagation step to determine a more useful range for _14.  So here 
we go.

First we need to derive the range ~[0,0] for _12.  Right now we compute 
that range as VARYING, so refining to ~[0,0] is obviously a step forward.

We then want to improve the range for _14.  Right now we compute 
something like [MIN_INT/4,MAX_INT/4].  That is for all intensive 
purposes useless.  It is more useful to derive ~[0,0] for EXACT_DIV_EXPR.

*Then* we need intersect_ranges to prefer the ~[0,0] when merging the 
new range for _14 with the one found during vrp1.

With those pieces in place we then derive the range ~[0,0] for _14, and 
the new code knows that for the conditional in question to be true that 
_14 must have the value zero.  So VRP determines that the conditional is 
always false, which in turn allows removing the block with the problem 
memset.

So there's a few conceptual pieces to this patchkit.

First, deriving a range for A - B when we know that A != B, deriving a 
better range for EXACT_DIV_EXPR when the numerator has the range ~[0,0]. 
  And finally not losing the range when merging them in intersect_ranges.

The second conceptual pieces is the check for the overflow comparison. 
The only real interesting stuff here is the conditional walking of the 
ASSERT_EXPR chains.  Often an ASSERT_EXPR will get in the way of 
detecting A + CST CMP A expressions.   When following the ASSERT_EXPR 
chains, we follow the chain for OP1 looking for a defining statement 
with an RHS of A + CST.   Then we look at OP0 and its chain to see if it 
matches A in the A+CST expression we found in OP1's chain. I saw cases 
where no walking of OP0 was desirable, cases where walking all of the 
ASSERT_EXPRs for OP0 was desirable and cases in-between.  Hence the 
search rather than walking or not walking.

Anyway, that gives us a reasonably good overflow test detector.

The last conceptual change is using the overflow test detector.  We use 
it in register_edge_assert_for_2 to register additional, often more 
useful, ranges than we were before.  We also use the detector in 
vrp_evaluate_conditional_warnv_with_ops when we can collapse the test 
into a EQ/NEQ test.  This collapses some conditionals during propagation 
and others post-propagation.  We don't follow ASSERT_EXPR chains during 
propagation, but do post-propagation.


Anyway, that's where things stand right now.  Comments welcomed.

Jeff

diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index b429217..f239821 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -5158,6 +5189,95 @@ masked_increment (const wide_int &val_in, const wide_int &mask,
   return val ^ sgnbit;
 }
 
+/* OP0 CODE OP1 is a comparison.  Examine the comparison and potentially
+   OP1's defining statement to see if it ultimately has the form
+   OP0 CODE (OP0 PLUS INTEGER_CST)
+
+   If so, return TRUE indicating this is an overflow test and store into
+   *NEW_CST an updated constant that can be used in a narrowed range test.
+
+   REVERSED indicates if the comparison was originally:
+
+   OP1 CODE' OP0.
+
+   This affects how we build the updated constant.  */
+
+static bool
+overflow_comparison_p (enum tree_code code, tree op0, tree op1,
+		       bool follow_assert_exprs, bool reversed, tree *new_cst)
+{
+  return false;
+  /* See if this is a relational operation between two SSA_NAMES with
+     unsigned, overflow wrapping values.  If so, check it more deeply.  */
+  if ((code == LT_EXPR || code == LE_EXPR
+       || code == GE_EXPR || code == GT_EXPR)
+      && TREE_CODE (op0) == SSA_NAME
+      && TREE_CODE (op1) == SSA_NAME
+      && INTEGRAL_TYPE_P (TREE_TYPE (op0))
+      && TYPE_UNSIGNED (TREE_TYPE (op0))
+      && TYPE_OVERFLOW_WRAPS (TREE_TYPE (op0)))
+    {
+      gimple *op1_def = SSA_NAME_DEF_STMT (op1);
+
+      /* If requested, follow any ASSERT_EXPRs backwards for OP1.  */
+      if (follow_assert_exprs)
+	{
+	  while (gimple_assign_single_p (op1_def)
+		 && TREE_CODE (gimple_assign_rhs1 (op1_def)) == ASSERT_EXPR)
+	    {
+	      op1 = TREE_OPERAND (gimple_assign_rhs1 (op1_def), 0);
+	      if (TREE_CODE (op1) != SSA_NAME)
+		break;
+	      op1_def = SSA_NAME_DEF_STMT (op1);
+	    }
+	}
+
+      /* Now look at the defining statement of OP1 to see if it adds
+	 or subtracts a nonzero constant from another operand.  */
+      if (op1_def
+	  && is_gimple_assign (op1_def)
+	  && gimple_assign_rhs_code (op1_def) == PLUS_EXPR
+	  && TREE_CODE (gimple_assign_rhs2 (op1_def)) == INTEGER_CST
+	  && wi::ne_p (gimple_assign_rhs2 (op1_def), 0))
+	{
+	  tree target = gimple_assign_rhs1 (op1_def);
+
+	  /* If requested, follow ASSERT_EXPRs backwards for op0 looking
+	     for one where TARGET appears on the RHS.  */
+	  if (follow_assert_exprs)
+	    {
+	      /* Now see if that "other operand" is op0, following the chain
+		 of ASSERT_EXPRs if necessary.  */
+	      gimple *op0_def = SSA_NAME_DEF_STMT (op0);
+	      while (op0 != target
+		     && gimple_assign_single_p (op0_def)
+		     && TREE_CODE (gimple_assign_rhs1 (op0_def)) == ASSERT_EXPR)
+		{
+		  op0 = TREE_OPERAND (gimple_assign_rhs1 (op0_def), 0);
+		  if (TREE_CODE (op0) != SSA_NAME)
+		    break;
+		  op0_def = SSA_NAME_DEF_STMT (op0);
+		}
+	    }
+
+	  /* If we did not find our target SSA_NAME, then this is not
+	     an overflow test.  */
+	  if (op0 != target)
+	    return false;
+
+	  tree type = TREE_TYPE (op0);
+	  wide_int max = wi::max_value (TYPE_PRECISION (type), UNSIGNED);
+	  HOST_WIDE_INT inc = TREE_INT_CST_LOW (gimple_assign_rhs2 (op1_def));
+	  if (reversed)
+	    *new_cst = wide_int_to_tree (type, max + inc);
+	  else
+	    *new_cst = wide_int_to_tree (type, max - inc);
+	  return true;
+	}
+    }
+  return false;
+}
+
 /* 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.
    Invert the condition COND if INVERT is true.  */
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index b429217..f239821 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -5179,7 +5299,19 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
   /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
      reachable from E.  */
   if (live_on_edge (e, name))
-    register_new_assert_for (name, name, comp_code, val, NULL, e, bsi);
+    {
+      tree x;
+      if (overflow_comparison_p (comp_code, name, val, false, false, &x)
+	  || overflow_comparison_p (swap_tree_comparison (comp_code), val, name,
+							  false, true, &x))
+	{
+	  enum tree_code new_code
+	    = ((comp_code == GT_EXPR || comp_code == GE_EXPR)
+	       ? GT_EXPR : LE_EXPR);
+	  register_new_assert_for (name, name, new_code, x, NULL, e, bsi);
+	}
+      register_new_assert_for (name, name, comp_code, val, NULL, e, bsi);
+    }
 
   /* In the case of NAME <= CST and NAME being defined as
      NAME = (unsigned) NAME2 + CST2 we can assert NAME2 >= -CST2
@@ -7538,6 +7670,60 @@ vrp_evaluate_conditional_warnv_with_ops (enum tree_code code, tree op0,
       && !POINTER_TYPE_P (TREE_TYPE (op0)))
     return NULL_TREE;
 
+  /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed
+     as a simple equality test, then prefer that over its current form
+     for evaluation.
+
+     An overflow test which collapses to an equality test can always be
+     expressed as a comparison of one argument against zero.  Overflow
+     occurs when the chosen argument is zero and does not occur if the
+     chosen argument is not zero.  */
+  tree x;
+  if (overflow_comparison_p (code, op0, op1, use_equiv_p, false, &x))
+    {
+      wide_int max = wi::max_value (TYPE_PRECISION (TREE_TYPE (op0)), UNSIGNED);
+      /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0)
+         B = A - 1; if (A > B) -> B = A - 1; if (A != 0) */
+      if (integer_zerop (x))
+	{
+	  op1 = x;
+	  code = (code == LT_EXPR || code == LE_EXPR) ? EQ_EXPR : NE_EXPR;
+	}
+      /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0)
+         B = A + 1; if (A < B) -> B = A + 1; if (B != 0) */
+      else if (wi::eq_p (x, max - 1))
+	{
+	  op0 = op1;
+	  op1 = wide_int_to_tree (TREE_TYPE (op0), 0);
+	  code = (code == GT_EXPR || code == GE_EXPR) ? EQ_EXPR : NE_EXPR;
+	}
+    }
+  else if (overflow_comparison_p (swap_tree_comparison (code),
+				  op1, op0, use_equiv_p, true, &x))
+    {
+      /* X holds the value if we wanted to generate an overflow check
+	 for the comparison using OP1.  But we're actually going to
+	 test against OP0 and we're always going to use an equality
+	 test, so the constants for detection below are different
+	 than the constant we pass into vrp_evaluate_... */
+      wide_int max = wi::max_value (TYPE_PRECISION (TREE_TYPE (op0)), UNSIGNED);
+      /* B = A - 1; if (B > A) -> B = A - 1; if (A == 0)
+         B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */
+      if (wi::eq_p (x, max - 1))
+	{
+	  op0 = op1;
+	  op1 = wide_int_to_tree (TREE_TYPE (op0), 0);
+	  code = (code == GT_EXPR || code == GE_EXPR) ? EQ_EXPR : NE_EXPR;
+	}
+      /* B = A + 1; if (B < A) -> B = A + 1; if (B == 0)
+         B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */
+      else if (integer_zerop (x))
+	{
+	  op1 = x;
+	  code = (code == LT_EXPR || code == LE_EXPR) ? EQ_EXPR : NE_EXPR;
+	}
+    }
+
   if ((ret = vrp_evaluate_conditional_warnv_with_ops_using_ranges
 	       (code, op0, op1, strict_overflow_p)))
     return ret;