Re: [PATCH 2/n] [PR tree-optimization/78496] Simplify ASSERT_EXPRs to facilitate jump threading

["Richard Biener via gcc-patches" <gcc-patches at gcc dot gnu dot org>]

On Sat, May 6, 2017 at 5:03 PM, Jeff Law <law@redhat.com> wrote:
> This is the 2nd of 3-5 patches to address pr78496.
>
> Jump threading will examine ASSERT_EXPRs as it walks the IL and record
> information from those ASSERT_EXPRs into the available expression and
> const/copies tables where they're later used to simplify conditionals.
>
> We're missing a couple things though.
>
> First an ASSERT_EXPR with an EQ test creates an equality we can enter into
> the const/copy tables.  We were failing to do that.  This is most
> interesting when the RHS of the condition in the ASSERT_EXPR is a constant,
> obviously.  This has a secondary benefit of doing less work to get better
> optimization.
>
> Second, some ASSERT_EXPRs may start off as a relational test such as x <= 0,
> but after range extraction and propagation they could be simplified into an
> equality comparison.  We already do this with conditionals and generalizing
> that code to handle ASSERT_EXPRs is pretty easy.  This gives us more chances
> to extract simple equivalences from the condition in ASSERT_EXPRs.
>
> This patch fixes those 2 problems.  I don't think it directly helps pr78496
> right now as we're unable to pick up the newly exposed jump threads until
> VRP2.   But that's a short term limitation that I've already addressed
> locally :-)
>
> Bootstrapped, regression tested and installed on the trunk.
>
> jeff
>
>
> ps. An astute observer might note that improving the effectiveness of VRP
> jump threading seems counterproductive since I've stated I want to remove
> VRP jump threading.  These improvements don't significantly change how I was
> planning to do that or the infrastructure we're going to rely upon to make
> that change.  All that changes is where we get the information from --
> ASSERT_EXPRs vs querying a new API that generates the same information as
> needed.

That API is already there.  It's called register_edge_assert_for (it might need
a wrapper to be most useful and also needs to be exported / moved from VRP
to somewhere else).  Both VRP and EVRP use it to "compute" ASSERT_EXPRs.

So I'm not sure if changing VRP with your patches is a good thing when you
could have used the new API in the first place ...

Richard.

>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index b0c253b09ae..0f78f2a2ed1 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,12 @@
> +2017-05-06  Jeff Law  <law@redhat.com>
> +
> +       PR tree-optimization/78496
> +       * tree-vrp.c (simplify_assert_expr_using_ranges): New function.
> +       (simplify_stmt_using_ranges): Call it.
> +       (vrp_dom_walker::before_dom_children): Extract equivalences
> +       from an ASSERT_EXPR with an equality comparison against a
> +       constant.
> +
>  2017-05-06  Richard Sandiford  <richard.sandiford@linaro.org>
>
>         * lra-constraints.c (lra_copy_reg_equiv): New function.
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index fca5b87e798..42782a6d17c 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,3 +1,9 @@
> +2017-05-06  Jeff Law  <law@redhat.com>
> +
> +       PR tree-optimization/78496
> +       * gcc.dg/tree-ssa/ssa-thread-16.c: New test.
> +       * gcc.dg/tree-ssa/ssa-thread-17.c: New test.
> +
>  2017-05-06  Richard Sandiford  <richard.sandiford@linaro.org>
>
>         * gcc.target/aarch64/spill_1.c: New test.
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-16.c
> b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-16.c
> new file mode 100644
> index 00000000000..78c349ca14d
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-16.c
> @@ -0,0 +1,38 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-vrp1-details" } */
> +
> +/* We should thread the if (exp == 2) conditional on the
> +   the path from inside the if (x) THEN arm.  It is the only
> +   jump threading opportunity in this code.  */
> +
> +/* { dg-final { scan-tree-dump-times "Threaded" 1 "vrp1" } } */
> +
> +
> +extern void abort (void) __attribute__ ((__nothrow__, __leaf__))
> +  __attribute__ ((__noreturn__));
> +
> +int x;
> +
> +
> +int code;
> +void
> +do_jump (int exp)
> +{
> +  switch (code)
> +    {
> +    case 4:
> +      if ((exp) == 1)
> +       goto normal;
> +      if (x)
> +       {
> +         if (exp != 0)
> +           abort ();
> +       }
> +      if ((exp) == 2)
> +       goto normal;
> +    case 3:
> +       abort ();
> +    }
> +  normal:
> +      ;
> +}
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-17.c
> b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-17.c
> new file mode 100644
> index 00000000000..692658fbb4b
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-17.c
> @@ -0,0 +1,36 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-vrp1-details" } */
> +
> +/* We should simplify one ASSERT_EXPR from a relational
> +   into an equality test.  */
> +/* { dg-final { scan-tree-dump-times "Folded
> into:\[^\r\n\]*ASSERT_EXPR\*\[^\r\n\]* == 1" 1 "vrp1" } } */
> +
> +/* And simplification of the ASSERT_EXPR leads to a jump threading
> opportunity.  */
> +/* { dg-final { scan-tree-dump-times "Threaded" 1 "vrp1" } } */
> +
> +extern void abort (void) __attribute__ ((__nothrow__, __leaf__))
> +  __attribute__ ((__noreturn__));
> +
> +union gimple_statement_d;
> +typedef union gimple_statement_d *gimple;
> +
> +
> +
> +union gimple_statement_d
> +{
> +  unsigned num_ops;
> +};
> +
> +void
> +gimple_assign_set_rhs_with_ops_1 (int code, gimple stmt, unsigned
> new_rhs_ops)
> +{
> +
> +  stmt->num_ops = new_rhs_ops + 1;
> +  if (stmt->num_ops <= 1)
> +    abort ();
> +  if (new_rhs_ops > 1)
> +    if (stmt->num_ops <= 2)
> +      abort ();
> +  if (new_rhs_ops > 2)
> +      abort ();
> +}
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index cf50e908257..461a48f5c9c 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -9600,6 +9600,43 @@ range_fits_type_p (value_range *vr, unsigned
> dest_precision, signop dest_sgn)
>    return true;
>  }
>
> +/* Simplify STMT, an ASSERT_EXPR, using ranges.  This is helpful because
> jump
> +   threading looks at the ASSERT_EXPRs.  Collapsing the condition of
> +   an ASSERT_EXPR from a relational to an equality test is where most
> +   of the benefit occurrs, so that's the only thing we currently do.  */
> +
> +static bool
> +simplify_assert_expr_using_ranges (gimple *stmt)
> +{
> +  return false;
> +  tree cond = TREE_OPERAND (gimple_assign_rhs1 (stmt), 1);
> +  tree_code code = TREE_CODE (cond);
> +  tree op0 = TREE_OPERAND (cond, 0);
> +
> +  /* The condition of the ASSERT_EXPR must be a simple relational
> +     between an SSA_NAME (with a range) and a constant.  */
> +  if (TREE_CODE (op0) != SSA_NAME
> +      || !INTEGRAL_TYPE_P (TREE_TYPE (op0)))
> +    return false;
> +
> +  tree op1 = TREE_OPERAND (cond, 1);
> +  if (TREE_CODE (op1) != INTEGER_CST)
> +    return false;
> +
> +  value_range *vr = get_value_range (op0);
> +  if (!vr || vr->type != VR_RANGE)
> +    return false;
> +
> +  tree res = test_for_singularity (code, op0, op1, vr);
> +  if (res)
> +    {
> +      TREE_SET_CODE (cond, EQ_EXPR);
> +      TREE_OPERAND (cond, 1) = res;
> +      return true;
> +    }
> +  return false;
> +}
> +
>  /* Simplify a conditional using a relational operator to an equality
>     test if the range information indicates only one value can satisfy
>     the original conditional.  */
> @@ -10334,6 +10371,9 @@ simplify_stmt_using_ranges (gimple_stmt_iterator
> *gsi)
>         case MAX_EXPR:
>           return simplify_min_or_max_using_ranges (gsi, stmt);
>
> +       case ASSERT_EXPR:
> +         return simplify_assert_expr_using_ranges (stmt);
> +
>         default:
>           break;
>         }
> @@ -10598,6 +10638,18 @@ vrp_dom_walker::before_dom_children (basic_block
> bb)
>         {
>           tree rhs1 = gimple_assign_rhs1 (stmt);
>           tree cond = TREE_OPERAND (rhs1, 1);
> +         tree lhs = gimple_assign_lhs (stmt);
> +         m_const_and_copies->record_const_or_copy (lhs, TREE_OPERAND (rhs1,
> 0));
> +
> +         if (TREE_CODE (cond) == EQ_EXPR)
> +           {
> +             tree cond_op0 = TREE_OPERAND (cond, 0);
> +             tree cond_op1 = TREE_OPERAND (cond, 1);
> +             if (TREE_CODE (cond_op0) == SSA_NAME)
> +               m_const_and_copies->record_const_or_copy (cond_op0,
> cond_op1);
> +             continue;
> +           }
> +
>           tree inverted = invert_truthvalue (cond);
>           vec<cond_equivalence> p;
>           p.create (3);
> @@ -10605,9 +10657,6 @@ vrp_dom_walker::before_dom_children (basic_block bb)
>           for (unsigned int i = 0; i < p.length (); i++)
>             m_avail_exprs_stack->record_cond (&p[i]);
>
> -         tree lhs = gimple_assign_lhs (stmt);
> -         m_const_and_copies->record_const_or_copy (lhs,
> -                                                   TREE_OPERAND (rhs1, 0));
>           p.release ();
>           continue;
>         }
>