Re: [PATCH][PR tree-optimization/67816] Fix jump threading when DOM removes conditionals in jump threading path

[Richard Biener <richard dot guenther at gmail dot com>]

On Thu, Dec 3, 2015 at 9:29 PM, Jeff Law <law@redhat.com> wrote:
> On 12/02/2015 08:35 AM, Richard Biener wrote:
>
>>>
>>> The most interesting side effect, and one I haven't fully analyzed yet is
>>> an
>>> unexpected jump thread -- which I've traced back to differences in what
>>> the
>>> alias oracle is able to find when we walk unaliased vuses. Which makes
>>> totally no sense that it's unable to find the unaliased vuse in the
>>> simplified CFG, but finds it when we don't remove the unexecutable edge.
>>> As
>>> I said, it makes no sense to me yet and I'm still digging.
>>
>>
>> The walking of PHI nodes is quite simplistic to avoid doing too much work
>> so
>> an extra (not executable) edge may confuse it enough.  So this might be
>> "expected".  Adding a flag on whether EDGE_EXECUTABLE is to be
>> trusted would be an option (also helping SCCVN).
>
> Found it.  In the CFG with the unexectuable edges _not_ removed there is a
> PHI associated with that edge which provides a dominating unaliased vuse.
> Once that edge is removed, the PHI arg gets removed and thus we can't easily
> see the unaliased vuse.
>
> So all is working as expected.  It wasn't ever a big issue, I just wanted to
> make sure I thoroughly understood the somewhat counter-intuitive result.

Good.  Btw, I remembered that with the unreachable tracking in SCCVN I
ran into cases where it didn't correctly track all unreachable blocks due
to the way the dominator walk works (which doesn't ensure we've visited
all predecessors).  Like for

  <unreachable>
   |                 |
   |               <bb3>
   |                 / \
 <bb2>          /   \                /
    \       <bb4>      <reachable>
     \      /
    <bb5>

DOM order visits <unreachable>, <bb2>, <bb3>, <bb5> and then
the DOM children like <bb4>.  So we fail to detect bb5 as unreachable
(didn't visit bb4 to mark outgoing edges unreachable yet).

The fix is easy (in testing right now).  Simply track if the current block
was unreachable when visiting DOM children.

Didn't manage to produce a missed-optimization testcase (but only
tried for a few minutes), the cases I've seen it were involving
unreachable loops, but I don't have them anymore.

Sorry if that makes extracting the machinery harder ;)

Richard.

2015-12-04  Richard Biener  <rguenther@suse.de>

        * tree-ssa-sccvn.c (sccvn_dom_walker): Add unreachable_dom
        member and initialize it.
        (sccvn_dom_walker::after_dom_children): Reset unreachable_dom
        if necessary.
        (sccvn_dom_walker::before_dom_children): If unreachable_dom
        is set BB is not reachable either.  Set unreachable_dom
        if not set and BB is unreachable.



> Jeff

Attachment: p
Description: Binary data