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

[law at redhat dot com]

In message <20030823224047.GA14558@atrey.karlin.mff.cuni.cz>, Zdenek Dvorak wri
tes:
 >Hello,
 >
 >this patch fixes a small problem in tree-ssa-dom -- we should not take
 >condition on edge coming into block into account if there are other
 >predecessors, as then the condition does not have to hold if we arrive
 >from the other edge.
Testcase please?  In general, if you're proposing a bugfix you should
really include a testcase with the patch.  A little more detail on 
the bug would be helpful too.

Presumably this happens if we have a COND_EXPR in which one (or both) of
the arms start with a label (possibly created by conditinoal thread jumping).
Right?


 >It also adds a debug dump of jump threading actions.
Definitely a good thing.


 >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.

This is probably worth documenting in tree-ssa-dom.c.  I'll take care of
that.


 >Changelog:
 >	* tree-ssa-dom.c (optimize_block):  Handle case when dominance
 >	tree children have also other sucessors.  Add dump to jump
 >	threading.
Seems reasonable to me.

jeff