This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] updating PHI nodes and DCE improvement
- From: law at redhat dot com
- To: gcc-patches at gcc dot gnu dot org
- Date: Thu, 20 Feb 2003 20:43:27 -0700
- Subject: [tree-ssa] updating PHI nodes and DCE improvement
- Reply-to: law at redhat dot com
I decided to do a quick review of the DCE code for any low-hanging fruit.
Yes I realize DCE is reasonably quick. This was mostly meant to be a quick
check that it wasn't doing anything terribly silly.
>From my reading I was pretty sure DCE is marking a whole lot more stuff
as being necessary prematurely. This is due to the implementation of
mark_necessary. It marks every instruction in every control parent
as necessary. Ugh. Also note that this means we have to walk every
statement in all of those blocks just to put them on the worklist.
Double-ugh. And finally, some of those statements it prematurely
marks may in fact not be necessary. Triple-ugh.
During my investigation I also found that after CCP has completed, we
have PHI nodes with bogus arguments. Specifically we have PHI nodes
with arguments for edges which have been removed from the CFG.
While this does not currently cause us any significant grief, it's rather
silly. It causes every pass after CCP to work harder than is really
necessary. There'll be a time where those bogus alternatives will actually
get in the way, so I'm correcting the problem now :-)
Anyway, fixing these issues cuts about 20% off DCE's time, in real terms
it's pretty minor (a second off my components of cc1 test). I didn't
take the time to measure secondary effects of having fewer statements
for the tree->rtl translator to deal with (though I did clearly see more
statements deleted after my change -- something like 200 on i386.c).
Bootstrapped and regression tested.
* tree-cfg.c (remove_bb): Update PHI nodes as edges are removed.
(cleanup_cond_expr_graph): Likewise.
(cleanup_switch_expr_graph): Likewise.
(disconnect_unreachable_case_labels): Likewise.
* tree-ssa-dce.c (mark_control_parent_necessary): Be much more
selective about what statements in the control parents are marked
as necessary.
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.55
diff -c -3 -p -r1.1.4.55 tree-cfg.c
*** tree-cfg.c 6 Feb 2003 04:41:05 -0000 1.1.4.55
--- tree-cfg.c 21 Feb 2003 03:36:56 -0000
*************** remove_bb (bb, remove_stmts)
*** 926,935 ****
/* Remove the edges into and out of this block. */
while (bb->pred != NULL)
! remove_edge (bb->pred);
while (bb->succ != NULL)
! remove_edge (bb->succ);
bb->pred = NULL;
bb->succ = NULL;
--- 926,958 ----
/* Remove the edges into and out of this block. */
while (bb->pred != NULL)
! {
! tree phi;
!
! /* Since this block is no longer reachable, we can just delete all
! of its PHI nodes. */
! phi = phi_nodes (bb);
! while (phi)
! {
! tree next = TREE_CHAIN (phi);
! remove_phi_node (phi, NULL_TREE, bb);
! phi = next;
! }
!
! remove_edge (bb->pred);
! }
while (bb->succ != NULL)
! {
! tree phi;
!
! /* PHI nodes in successors of this block now have one less
! alternative. */
! for (phi = phi_nodes (bb->succ->dest); phi; phi = TREE_CHAIN (phi))
! remove_phi_arg (phi, bb);
! remove_edge (bb->succ);
! }
!
bb->pred = NULL;
bb->succ = NULL;
*************** cleanup_cond_expr_graph (bb)
*** 1172,1178 ****
{
next = e->succ_next;
if (e != taken_edge)
! remove_edge (e);
}
}
}
--- 1195,1209 ----
{
next = e->succ_next;
if (e != taken_edge)
! {
! tree phi;
!
! /* Remove the appropriate PHI alternative in the
! target block for each unexecutable edge. */
! for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
! remove_phi_arg (phi, e->dest);
! remove_edge (e);
! }
}
}
}
*************** cleanup_switch_expr_graph (switch_bb)
*** 1211,1217 ****
basic_block chain_bb = successor_block (switch_bb);
edge e = find_edge (switch_bb, chain_bb);
if (e)
! remove_edge (e);
break;
}
}
--- 1242,1256 ----
basic_block chain_bb = successor_block (switch_bb);
edge e = find_edge (switch_bb, chain_bb);
if (e)
! {
! tree phi;
!
! /* Remove the appropriate PHI alternative in the
! target block for each unexecutable edge. */
! for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
! remove_phi_arg (phi, e->src);
! remove_edge (e);
! }
break;
}
}
*************** disconnect_unreachable_case_labels (bb)
*** 1256,1262 ****
to create this silly edge to begin with (see FIXME
note in make_ctrl_stmt_edges). */
&& label_stmt != switch_body)
! remove_edge (e);
}
}
}
--- 1295,1309 ----
to create this silly edge to begin with (see FIXME
note in make_ctrl_stmt_edges). */
&& label_stmt != switch_body)
! {
! tree phi;
!
! /* Remove the appropriate PHI alternative in the
! target block for each unexecutable edge. */
! for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
! remove_phi_arg (phi, e->src);
! remove_edge (e);
! }
}
}
}
Index: tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dce.c,v
retrieving revision 1.1.2.27
diff -c -3 -p -r1.1.2.27 tree-ssa-dce.c
*** tree-ssa-dce.c 10 Feb 2003 12:27:03 -0000 1.1.2.27
--- tree-ssa-dce.c 21 Feb 2003 03:36:56 -0000
*************** mark_necessary (t)
*** 144,177 ****
{
if (mark_tree_necessary (t))
{
! /* Mark all statements in control parent blocks as necessary. */
if (bb_for_stmt (t))
mark_control_parent_necessary (parent_block (bb_for_stmt (t)));
}
}
! /* Mark all statements in all nested control parent block as necessary
! statements. */
static void
mark_control_parent_necessary (bb)
basic_block bb;
{
- block_stmt_iterator i;
tree t;
! /* Loops through the stmts in this block, marking them as necessary. */
while (bb != NULL && bb->index != INVALID_BLOCK)
{
! for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
! {
! /* Avoid needless calls back to this routine by directly calling
! mark_tree since we know we are going to cycle through all parent
! blocks and their statements. */
! t = bsi_stmt (i);
! mark_tree_necessary (t);
! }
bb = parent_block (bb);
}
}
--- 144,186 ----
{
if (mark_tree_necessary (t))
{
! /* Mark control statements in control parent blocks as necessary. */
if (bb_for_stmt (t))
mark_control_parent_necessary (parent_block (bb_for_stmt (t)));
}
}
! /* Mark control statements in the control parent blocks as necessary.
!
! Right now this also includes BIND_EXPRs, but one day that should not
! be necessary. */
static void
mark_control_parent_necessary (bb)
basic_block bb;
{
tree t;
! /* Iterate through each of the control parents. */
while (bb != NULL && bb->index != INVALID_BLOCK)
{
! /* The first statement may be interesting (it could be a LOOP_EXPR
! or BIND_EXPR. */
! t = *(bb->head_tree_p);
! if (TREE_CODE (t) == COMPOUND_EXPR)
! t = TREE_OPERAND (t, 0);
! if (is_ctrl_stmt (t) || TREE_CODE (t) == BIND_EXPR)
! mark_tree_necessary (t);
!
! /* The last statement in the block may also be interesting such
! as a COND_EXPR or SWITCH_EXPR. */
! t = *(bb->end_tree_p);
! if (TREE_CODE (t) == COMPOUND_EXPR)
! t = TREE_OPERAND (t, 0);
! if (is_ctrl_stmt (t) || TREE_CODE (t) == BIND_EXPR)
! mark_tree_necessary (t);
!
bb = parent_block (bb);
}
}