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

[Andrew Pinski <pinskia at gmail dot com>]

On Sat, May 6, 2017 at 4:55 PM, Andrew Pinski <pinskia@gmail.com> wrote:
> On Sat, May 6, 2017 at 8:03 AM, 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.
>
>
> After this patch on aarch64-linux-gnu I get a bootstrap failure while
> linking lto1/cc1/cc1plus/go1 in stage2:
> godump.o: In function `go_define(unsigned int, char const*)':
> godump.c:(.text+0x36c): relocation truncated to fit:
> R_AARCH64_ADR_PREL_LO21 against `.rodata'
> godump.c:(.text+0x4b4): relocation truncated to fit:
> R_AARCH64_ADR_PREL_LO21 against `.rodata'
> collect2: error: ld returned 1 exit status
> ../../gcc/gcc/lto/Make-lang.in:81: recipe for target 'lto1' failed
> make[3]: *** [lto1] Error 1

I should mention this is even after the patch to
simplify_assert_expr_using_ranges .

Thanks,
Andrew

>
> Thanks,
> Andrew
>
>
>>
>> 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.
>>
>> 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;
>>         }
>>