[Bug tree-optimization/69452] [6 Regression] gcc ICE at -O3 on x86_64-linux-gnu in with verify_ssa failed

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69452

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jeffrey A. Law from comment #2)
> This looks like a latent bug in tree-ssa-loop-im.c introduced by Richi a few
> years ago when he added handling of invariant PHIs.
> 
> It appears that the code assumes that a dominator walk is sufficient to
> order invariant statements moved.  However, consider a diamond CFG
> 
>     a
>    / \
>   b   c
>    \ /
>     d
> 
> a dominates b, c & d.  
> 
> Valid dominator walk orders would be
> 
> a, b, c, d
> a, b, d, c
> a, c, b, d
> a, c, d, b
> a, d, b, c
> a, d, c, b
> 
> Note carefully that we could visit d before b or c.  So a pass which assumes
> that we always visit b & c before d for correctness is fundamentally flawed.
> 
> The move_computations::before_dom_children call back is visited by the dom
> walker and just inserts instructions on the appropriate edge.  Each
> instruction is inserted on the edge *when it's appropriate block is
> visited*.  So if we have an invariant in d which depends on invariants in b
> & c, a domwalk can not be relied upon to order those statements.
> 
> The obviously question is how can that happen in SSA?  There can't be a
> statement in d that depends on something in b & c because b & c don't
> dominate d.  But wait...  PHI nodes.  A PHI can be defined in d which has
> arguments defined in b & c.
> 
> That's precisely what's happening with this BZ.  We have a PHI in block d
> which is fed by values in blocks c & b.  However, the order of visitation in
> the domwalk is b, d, c resulting in something like this:
> 
> _71 = (char) pretmp_85;
> c_lsm.17_116 = r_75 != 0 ? _93 : _71;
> _93 = (char) pretmp_85;
> 
> Which is obviously invalid SSA (ignore that _71 and _93 have the same value).
> 
> What's key to remember here is that a domwalk will not guarantee that blocks
> defining arguments in a PHI will be visited before the PHI itself -- even in
> loop-free code.
> 
> If we're going to keep the current design of the invariant-motion code, then
> we probably need to do something like a topological sort of the statements
> on the edges before we commit the edge insertions.
> 
> We could also consider sorting the blocks for the dominator walk.  There's
> been a few cases through the years where that would be helpful, but not in a
> really significant way, just minor stuff we'd catch earlier in the optimizer
> pipeline if we had a better visitation order.

domwalk already does that though, but it seems to be not enough if you consider

   C
  / \
 B   D-E
 |   |
 |   F
  \ /  
   A

where children of C are B, A and D (but not F!).  The simple diamond is dealt
with with

              default:
                qsort (&worklist[saved_sp], sp - saved_sp,
                       sizeof (basic_block), cmp_bb_postorder);

which sorts children in rpo order.

The issue is latent - I'll think of sth not too invasive to fix it.