This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Fix tree-ssa-dom, bugs in jump threading
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Cc: law at redhat dot com
- Date: Sun, 24 Aug 2003 00:40:47 +0200
- Subject: [tree-ssa] Fix tree-ssa-dom, bugs in jump threading
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.
It also adds a debug dump of jump threading actions.
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).
Changelog:
* tree-ssa-dom.c (optimize_block): Handle case when dominance
tree children have also other sucessors. Add dump to jump
threading.
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.29
diff -c -3 -p -r1.1.2.29 tree-ssa-dom.c
*** tree-ssa-dom.c 21 Aug 2003 19:28:12 -0000 1.1.2.29
--- tree-ssa-dom.c 23 Aug 2003 22:19:55 -0000
*************** optimize_block (basic_block bb, tree par
*** 428,434 ****
/* The destination block may have become unreachable, in
which case there's no point in optimizing it. */
if (dest->pred)
! optimize_block (dest, last, dest->pred->flags);
});
}
else
--- 428,443 ----
/* The destination block may have become unreachable, in
which case there's no point in optimizing it. */
if (dest->pred)
! {
! /* Ensure that we only take the condition into account
! if there is no other way how to reach the target basic
! block. The fact that we have exactly one predecessor
! also ensures that the predecessor is BB. */
! if (!dest->pred->pred_next)
! optimize_block (dest, last, dest->pred->flags);
! else
! optimize_block (dest, NULL_TREE, 0);
! }
});
}
else
*************** optimize_block (basic_block bb, tree par
*** 523,528 ****
--- 532,541 ----
/* Update/insert PHI nodes as necessary. */
/* Now update the edges in the CFG. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " Threaded jump from %d to %d\n",
+ bb->succ->dest->index, dest->index);
+
ssa_remove_edge (bb->succ);
make_edge (bb, dest, 0);
}