This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] Speed up cleanup_tree_cfg() - Part 3
- From: Kazu Hirata <kazu at cs dot umass dot edu>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sun, 03 Oct 2004 09:05:03 -0400 (EDT)
- Subject: [patch] Speed up cleanup_tree_cfg() - Part 3
Hi,
Attached is a patch to further speed up cleanup_tree_cfg().
It turns out that with a minor tweak to thread_jumps(), we can
establish a property that it never leaves unreachable blocks provided
that it starts out with no unreachable blocks. It's actually easy to
do so. Without the patch, thread_jumps() removes unreachable blocks
only when the dominator info is valid. All we have to do is to have
it always remove unreachable blocks as they appear as a result of jump
threading.
The new property in turn allows us to dramatically simplify the while
loop in cleanup_tree_cfg() because thread_jumps() no longer leaves
unreachable blocks.
Here is the timing for 10 runs of "cc1 -O2 -o /dev/null fold-const.i".
original patched
real: 183.359 183.034 (0.177% down)
user: 180.814 180.809 (0.002% down)
ctc: 869 869
ccf: 1152 1152
dub: 1397 1152 (17.537% down)
tj: 1114 1114
ctc: the number of calls to cleanup_tree_cfg
ccf: the number of calls to cleanup_control_flow from ctc
dub: the number of calls to delete_unreachable_blocks from ctc
tj: the number of calls to thread_jumps from ctc
Note that we have "gcc_assert (!delete_unreachable_blocks())"
immediately after the while loop, so when I tested my patch, the
gcc_assert acted as an evidence (but not a proof) that thread_jumps()
never leaves unreachable blocks.
I tested the attached patch on top of
http://gcc.gnu.org/ml/gcc-patches/2004-10/msg00169.html
Tested on i686-pc-linux-gnu. OK to apply?
p.s.
Admittedly, this speed up is very small, but my next patch will remove
the while loop and will bring a bigger speed up, so stay tuned.
Kazu Hirata
2004-10-03 Kazu Hirata <kazu@cs.umass.edu>
* tree-cfg.c (cleanup_tree_cfg): Don't call
delete_unreachable_blosk() after thread_jumps().
(thread_jumps): Always remove basic blocks as they become
unreachable.
diff -u tree-cfg.c tree-cfg.c
*** tree-cfg.c 2 Oct 2004 13:06:20 -0000
--- tree-cfg.c 2 Oct 2004 02:03:34 -0000
***************
*** 723,734 ****
opportunities for itself, so iterate on it until nothing
changes. */
while (thread_jumps ())
! {
! /* delete_unreachable_blocks() does its job only when
! thread_jumps() produces more unreachable blocks. */
! delete_unreachable_blocks ();
! retval = true;
! }
#ifdef ENABLE_CHECKING
if (retval)
--- 723,729 ----
opportunities for itself, so iterate on it until nothing
changes. */
while (thread_jumps ())
! retval = true;
#ifdef ENABLE_CHECKING
if (retval)
***************
*** 3969,3990 ****
}
}
! /* Update the dominators. */
! if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
{
! /* Remove the unreachable blocks (observe that if all blocks
! were reachable before, only those in the path we threaded
! over and did not have any predecessor outside of the path
! become unreachable). */
! for (; old_dest != dest; old_dest = tmp)
! {
! tmp = EDGE_SUCC (old_dest, 0)->dest;
! if (EDGE_COUNT (old_dest->preds) > 0)
! break;
! delete_basic_block (old_dest);
! }
/* If the dominator of the destination was in the path, set its
dominator to the start of the redirected edge. */
if (get_immediate_dominator (CDI_DOMINATORS, old_dest) == NULL)
--- 3964,3986 ----
}
}
! /* Remove the unreachable blocks (observe that if all blocks
! were reachable before, only those in the path we threaded
! over and did not have any predecessor outside of the path
! become unreachable). */
! for (; old_dest != dest; old_dest = tmp)
{
! tmp = EDGE_SUCC (old_dest, 0)->dest;
! if (EDGE_COUNT (old_dest->preds) > 0)
! break;
! delete_basic_block (old_dest);
! }
!
! /* Update the dominators. */
! if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
! {
/* If the dominator of the destination was in the path, set its
dominator to the start of the redirected edge. */
if (get_immediate_dominator (CDI_DOMINATORS, old_dest) == NULL)