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]

Re: [PR tree-optimization/71691] Fix unswitching in presence of maybe-undef SSA_NAMEs (take 2)


On Mon, Jan 23, 2017 at 6:26 PM, Aldy Hernandez <aldyh@redhat.com> wrote:
> On 01/18/2017 10:10 AM, Richard Biener wrote:
>>
>> On Fri, Jan 13, 2017 at 7:48 PM, Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
> Hi Richard.
>
> I'd be happy to provide a patch, but could you please elaborate, as I'm
> afraid I'm not following.
>
>>> We could go back to my original, no caching version (with the other
>>> suggestions).  That solves the problem quite simply, with no regressions.
>>
>>
>> So let's go with a unswitching-local solution then.  Based on
>> tree_may_unswitch_on:
>
>
> What do you mean by unswitching-local?

Like your original patch, not adding new generic infrastructure
outside of tree-ssa-unswitch.c.

>>
>>   /* Condition must be invariant.  */
>>   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
>>     {
>>       /* Unswitching on undefined values would introduce undefined
>>          behavior that the original program might never exercise.  */
>>       if (ssa_undefined_value_p (use, true))
>>         return NULL_TREE;
>>       def = SSA_NAME_DEF_STMT (use);
>>       def_bb = gimple_bb (def);
>>       if (def_bb
>>           && flow_bb_inside_loop_p (loop, def_bb))
>>         return NULL_TREE;
>>
>> we only have to look for uses in blocks dominating the loop header block
>> (or in blocks post-dominating that loop header, but we can probably
>> implement
>> that by simply including the loop header itself with a FIXME comment).
>
>
> Look for *uses*??  Do you mean definitions?  I mean, we're trying to figure
> out whether we are going to unswitch on a use that is inside a the loop, not
> before or after. So perhaps we only care about *definitions*
> (SSA_NAME_DEF_STMT) dominating the loop header.

We're looking for stmts using the 'use's in the above loop on a path that is
always executed when the loop is entered.  So we're not introducing a
use of a possibly undefined value.

Of course we can also prove that 'use' is in fact not undefined looking at
its defs which are obviously always dominating the loop header if the
condition satisfies tree_may_unswitch_on (non-dominating defs will
have uses in PHIs dominating  the header which we have to treat
conservatively of course).

>
>>
>> Note that we only need to know whether a BB will be always executed when
>> the loop is entered -- there's "infrastructure" elsewhere that computes
>> this
>> w/o the need of post-dominance.  For example see fill_always_executed_in_1
>> tree-ssa-loop-im.c (we can't use that 1:1 I think because we already use
>> ->aux
>> via the original copy tables, but we could simplify it as we're only
>> interested in
>> the loop which preheader we put the unswitch condition on so we can use
>> a bitmap to record whether a block of the loop is always executed or not).
>
>
> I don't see any use of ->aux within loop unswitching, so perhaps no
> adjustment is needed?  I verified this by successfully bootstrapping with:
>
> diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c
> index 92599fb..774d6bf 100644
> --- a/gcc/tree-ssa-loop-unswitch.c
> +++ b/gcc/tree-ssa-loop-unswitch.c
> @@ -94,6 +94,14 @@ tree_ssa_unswitch_loops (void)
>    struct loop *loop;
>    bool changed = false;
>
> +  basic_block bb;
> +  FOR_ALL_BB_FN (bb, cfun)
> +    if (bb->aux)
> +      {
> +       gcc_unreachable ();
> +      }
>
> Furthermore, you say that we have this "infrastructure" without the need for
> post-dominance.  But we still need dominance info.  The function
> fill_always_execute_in_1 uses CDI_DOMINATORS both inside said function, and
> throughout its dependencies.  I thought the point of pre-calculating
> dominance info (or post-dominance info) originally was because we couldn't
> depend on dominance info being kept up to date between executions of
> tree_unswitch_single_loop(), which BTW, runs recursively.

dominators are kept up-to-date within cfg manipulation routines and unswitching
already uses them.

So if you just try to prove 'use' is defined you don't even need
dominators.  But
that misses cases like

int x;
foo ()
{
  for (;;)
    {
       if (x == 5)
         ...;
    }
}

where unswitching is valid because x is always used when the loop is entered.
Similar

int x, a[10];
foo (int c)
{
  foo (x);
  for (i=0;i<c;++i)
    {
       if (a[c])
         break;
       if (x == 5)
         ...;
    }
}

even though the condition is not always executed if the loop is entered.

>> Can you send a patch that does this maybe?
>
>
> Sure, when I understand what you suggest ;-).
>
> Again, thanks for your input here.
> Aldy
>


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