Re: [tree-ssa] Fix tree-ssa-dom, bugs in jump threading

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

>  >here is the patch that fixes the issue described in one of previous
>  >mails (interaction between dominator optimization and jump threading).
>  >It does not work with the current branch (I have developed it to fix
>  >regressions caused by COND_EXPR lowering, and a few lines of code
>  >dependent on it have leaked in).  I just need to know whether this
>  >solution is acceptable -- it in consequence makes the dominators to be
>  >recomputed after every iteration, which may be somewhat costly.
> I'd really like to see code which triggers this problem -- I don't
> see how the dominator optimizer in its current form can cause these
> problems given that it doesn't update the dominator tree and the 
> problem blocks in your example can only contain COND_EXPRs for which
> we know their destination.  But I'm slightly biased in that I wrote the
> code and sometimes I even claim to understand how it works :-)
> 
> 
> Regardless of whether or not we have a problem in the dominator optimizer,
> your change may still be useful.  One of the aspects that I punted on
> was cascading effects of conditional jump threading.  Your patch allows us
> to capture those effects.
> 
> To go back to your earlier message if we have:
> 
> 
>           x != y --> 2  -- x != y --> 4 -- x != y --> 5
>         /            ^  \             ^ \
>  --> 0               |   \            |  \
>         \            |     x == y --> 3    x == y --> 6
>           x == y --> 1
> 
> 
> We have a dominator tree like
> 
> 
>     0
>    / \
>   1   2
>      / \
>     3   4
>        / \
>       5   6

ok, so slowly :-) :

1) 1 is processed, x == y recorded, edge 1 -> 2 redirected to 3,
   x == y removed from tables.

           x != y --> 2  -- x != y --> 4 -- x != y --> 5
         /               \             ^ \
  --> 0                   \            |  \
         \                  x == y --> 3    x == y --> 6
           x == y --> 1---------------/

2) 2 is processed, x != y recorded, edge 2 -> 3 removed
   (note that x != y stays since 2 used to dominate 3)

           x != y --> 2  -- x != y --> 4 -- x != y --> 5
         /                             ^ \
  --> 0                                |  \
         \                             3    x == y --> 6
           x == y --> 1---------------/

3) 3 is processed.  Edge 3 --> 4 redirected to 5, which is clearly
   wrong.

Zdenek