Tree-level fix for PR 69526
diff mbox

Message ID CAFiYyc2XVcJA4ZsS5LSLfRD-V3U9tDRpbeU_FRwoNa2w8Z4cGw@mail.gmail.com
State New
Headers show

Commit Message

Richard Biener July 21, 2016, 11:27 a.m. UTC
On Thu, Jul 21, 2016 at 12:42 PM, Robin Dapp <rdapp@linux.vnet.ibm.com> wrote:
> 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.

I find this a bit hard to follow (looking at the match.pd pattern).

+           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);
+             }

if !inner_ovf (just set that to false if !check_inner_ovf to simplify
checks please).
you know it's valid to transform the op to (T)@0 innerop (T)@1 outerop @2
(if T is wider than the inner type which I think you should check and
which should
simplify things).

You can then combine (T)@1 and @2 where I think you fail to handle mixed
MINUS_EXPR/PLUS_EXPR (practically you'll see only PLUS_EXPRs for integers).

So you have (T)@0 + combined-in-T which you then can either emit or
check whether
combined-in-T fits in the inner type and @0 + combined-in-T does not overflow in
which case (T)(@0 + combined-in-T) is safe.

I believe that for simplicity we want to split this transform into two
- one doing
(T)(a + CST) - CST -> (T)a + CST' and one doing (T)a + CST -> (T)(a + CST).

The testcase is rather unspecific as to what testcases shoudl fold and what not
given your very simple scan and mixing should/should-not simplify cases.  Please
consider splitting it up and make it a run test that verifies the
bogus transforms
do not take place.

Doing

+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;

causes such stmts to be folded twice as substitute_and_fold does

      /* Some statements may be simplified using propagator
         specific information.  Do this before propagating
         into the stmt to not disturb pass specific information.  */
      if (fold_fn
          && (*fold_fn)(&i))
        {
          did_replace = true;
          prop_stats.num_stmts_folded++;
          stmt = gsi_stmt (i);
          update_stmt (stmt);
        }

      /* Replace real uses in the statement.  */
      did_replace |= replace_uses_in (stmt, get_value_fn);

      /* If we made a replacement, fold the statement.  */
      if (did_replace)
        {
          fold_stmt (&i, follow_single_use_edges);
          stmt = gsi_stmt (i);

which is less than ideal.  I think that given we have fold_stmt following
SSA edges and thus not only stmts we propagated into are possibly
interesting to fold (but also their single-uses, recursively), we should
evaluate the compile-time cost of doing the fold_stmt unconditionally.

Comments

Robin Dapp Aug. 23, 2016, 7:11 a.m. UTC | #1
gah, this

+  return true;
+  if (TREE_CODE (t1) != SSA_NAME)

should of course be like this

+  if (TREE_CODE (t1) != SSA_NAME)
+  return true;

in the last patch.

Patch
diff mbox

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)
+{

tree.c doesn't look like the best fit.  I think putting it into
tree-vrp.c is better
and I think that extract_range_from_binary_expr_1 itself should compute what we
want here as additional output.  Conservative handling for all but plus/minus is
ok with me.

+  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;

note that we'll ICE if you call TYPE_OVERFLOW_UNDEFINED on a type
that is not ANY_INTEGRAL_TYPE_P, so better re-order the checks.

Thanks,
Richard.


> Regards
>  Robin