This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [tree-ssa] Fix tree-ssa-dom, bugs in jump threading
Hello,
> >More seriously, there seems to be an important problem in jump
> >threading. Consider the following cfg:
> >
> > x != y --> 2 -- x != y --> 4 -- x != y --> 5
> > / ^ \ ^ \
> > --> 0 | \ | \
> > \ | x == y --> 3 x == y --> 6
> > x == y --> 1
> >
> >processed in the order of numbers.
> >
> >Jump from 1 is threaded to 3.
> >After entering 2, x != y is recorded; edge 2 --> 3 is removed.
> >3 is entered and we believe that x != y; jump is incorrectly threaded to
> > 5 instead of 6.
> >
> >The problem is that the redirection changes the dominator tree
> >non-trivially, so when handling basic block 3, we incorrectly make
> >decions based on properties of basic block 2 that no longer dominates
> >it. I don't see an easy solution just now (except for restarting the
> >optimization when cfg is altered, which obviously is not a good thing to
> >do).
> Note very carefully that for us to thread the 1->2 edge to block #3 we
> require that block #2 start with a COND_EXPR. Also remember that we do not
> update the dominator tree inside the dominator optimizer.
>
>
> The only expression block #2 should be able to enter into the table in that
> case would be equivalences created by the COND_EXPR on each of its arms.
>
> ie, the only equivalence from block #2 that is available in block #4 would
> be 1 = (x != y), and the only equivalence from block #2 that is available in
> block #3 is 1 = (x == y). So the only properties of block #2 which
> propagate into its children are precisely those which are safe.
please try drawing pictures, together with edges redirected and
removed, perhaps it will be cleaner then.
> This is probably worth documenting in tree-ssa-dom.c. I'll take care of
> that.
nope; this bug is not a theory, it is something that really occurs with
COND_EXPR lowering patch.
Zdenek