This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Improve COND_EXPR linearization, statement removal, etc
- From: law at redhat dot com
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 05 Aug 2003 10:11:53 -0600
- Subject: [tree-ssa] Improve COND_EXPR linearization, statement removal, etc
- Reply-to: law at redhat dot com
This patch has 3 small improvements to our tree-ssa optimizers which
individually and as a group allow us to linearize more COND_EXPRs.
First, we call remove_useless_stmts_and_vars before building the flow
graph and running the optimizers. This removes a lot of unnecessary
crud that sometimes gets in the way of things like COND_EXPR linearization.
Second, when removing blocks, we remove them in reverse order now. This
exposes more opportunities for COND_EXPR linearization by making it more
likely the two arms of the COND_EXPR are empty.
Finally, we previously would not linearize a COND_EXPR if the postdominator
of its arms had a PHI node. This patch allows linearization if the PHI
alternatives resulting from the two arms of the COND_EXPR are equivalent.
Bootstrapped and regression tested (of course).
* tree-ssa-optimize.c (optimize_function_tree): Call
remove_useless_stmts_and_vars before building the flow graph.
* tree-cfg.c (remove_useless_stmts_and_vars): Rename argument from
first_iteration to remove_unused_vars.
* tree-cfg.c (remove_unreachable_blocks): Remove blocks in reverse
order.
(remove_bb): Remove unwanted call to bsi_next.
(bsi_remove): Refine code which removes useless COMPOUND_EXPRs to allow
removal if one of the arms is not associated with a basic block.
(remove_stmt): Improve check for testing when a basic block head/end
pointer needs to be updated when removing a COMPOUND_EXPR.
* tree-cfg.c (phi_alternatives_equal): New function.
(linearize_cond_expr): Allow linearization if the PHI nodes at the
target have equivalent arguments for the incoming edges from the THEN and
ELSE clauses.
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.139
diff -c -3 -p -r1.1.4.139 tree-cfg.c
*** tree-cfg.c 4 Aug 2003 18:44:02 -0000 1.1.4.139
--- tree-cfg.c 5 Aug 2003 15:58:24 -0000
*************** cleanup_tree_cfg (void)
*** 1521,1527 ****
to ensure we eliminate all the useless code. */
int
! remove_useless_stmts_and_vars (tree *first_p, int first_iteration)
{
tree_stmt_iterator i;
int repeat = 0;
--- 1521,1527 ----
to ensure we eliminate all the useless code. */
int
! remove_useless_stmts_and_vars (tree *first_p, int remove_unused_vars)
{
tree_stmt_iterator i;
int repeat = 0;
*************** remove_useless_stmts_and_vars (tree *fir
*** 1549,1562 ****
code = TREE_CODE (*stmt_p);
if (code == LOOP_EXPR)
repeat |= remove_useless_stmts_and_vars (&LOOP_EXPR_BODY (*stmt_p),
! first_iteration);
else if (code == COND_EXPR)
{
tree then_clause, else_clause, cond;
repeat |= remove_useless_stmts_and_vars (&COND_EXPR_THEN (*stmt_p),
! first_iteration);
repeat |= remove_useless_stmts_and_vars (&COND_EXPR_ELSE (*stmt_p),
! first_iteration);
then_clause = COND_EXPR_THEN (*stmt_p);
else_clause = COND_EXPR_ELSE (*stmt_p);
--- 1549,1562 ----
code = TREE_CODE (*stmt_p);
if (code == LOOP_EXPR)
repeat |= remove_useless_stmts_and_vars (&LOOP_EXPR_BODY (*stmt_p),
! remove_unused_vars);
else if (code == COND_EXPR)
{
tree then_clause, else_clause, cond;
repeat |= remove_useless_stmts_and_vars (&COND_EXPR_THEN (*stmt_p),
! remove_unused_vars);
repeat |= remove_useless_stmts_and_vars (&COND_EXPR_ELSE (*stmt_p),
! remove_unused_vars);
then_clause = COND_EXPR_THEN (*stmt_p);
else_clause = COND_EXPR_ELSE (*stmt_p);
*************** remove_useless_stmts_and_vars (tree *fir
*** 1590,1608 ****
}
else if (code == SWITCH_EXPR)
repeat |= remove_useless_stmts_and_vars (&SWITCH_BODY (*stmt_p),
! first_iteration);
else if (code == CATCH_EXPR)
repeat |= remove_useless_stmts_and_vars (&CATCH_BODY (*stmt_p),
! first_iteration);
else if (code == EH_FILTER_EXPR)
repeat |= remove_useless_stmts_and_vars (&EH_FILTER_FAILURE (*stmt_p),
! first_iteration);
else if (code == TRY_CATCH_EXPR || code == TRY_FINALLY_EXPR)
{
repeat |= remove_useless_stmts_and_vars (&TREE_OPERAND (*stmt_p, 0),
! first_iteration);
repeat |= remove_useless_stmts_and_vars (&TREE_OPERAND (*stmt_p, 1),
! first_iteration);
/* If the handler of a TRY_CATCH or TRY_FINALLY is empty, then
we can emit the TRY block without the enclosing TRY_CATCH_EXPR
--- 1590,1608 ----
}
else if (code == SWITCH_EXPR)
repeat |= remove_useless_stmts_and_vars (&SWITCH_BODY (*stmt_p),
! remove_unused_vars);
else if (code == CATCH_EXPR)
repeat |= remove_useless_stmts_and_vars (&CATCH_BODY (*stmt_p),
! remove_unused_vars);
else if (code == EH_FILTER_EXPR)
repeat |= remove_useless_stmts_and_vars (&EH_FILTER_FAILURE (*stmt_p),
! remove_unused_vars);
else if (code == TRY_CATCH_EXPR || code == TRY_FINALLY_EXPR)
{
repeat |= remove_useless_stmts_and_vars (&TREE_OPERAND (*stmt_p, 0),
! remove_unused_vars);
repeat |= remove_useless_stmts_and_vars (&TREE_OPERAND (*stmt_p, 1),
! remove_unused_vars);
/* If the handler of a TRY_CATCH or TRY_FINALLY is empty, then
we can emit the TRY block without the enclosing TRY_CATCH_EXPR
*************** remove_useless_stmts_and_vars (tree *fir
*** 1637,1643 ****
tree block;
/* First remove anything underneath the BIND_EXPR. */
repeat |= remove_useless_stmts_and_vars (&BIND_EXPR_BODY (*stmt_p),
! first_iteration);
/* If the BIND_EXPR has no variables, then we can pull everything
up one level and remove the BIND_EXPR, unless this is the
--- 1637,1643 ----
tree block;
/* First remove anything underneath the BIND_EXPR. */
repeat |= remove_useless_stmts_and_vars (&BIND_EXPR_BODY (*stmt_p),
! remove_unused_vars);
/* If the BIND_EXPR has no variables, then we can pull everything
up one level and remove the BIND_EXPR, unless this is the
*************** remove_useless_stmts_and_vars (tree *fir
*** 1657,1663 ****
*stmt_p = BIND_EXPR_BODY (*stmt_p);
repeat = 1;
}
! else if (first_iteration)
{
/* If we were unable to completely eliminate the BIND_EXPR,
go ahead and prune out any unused variables. We do not
--- 1657,1663 ----
*stmt_p = BIND_EXPR_BODY (*stmt_p);
repeat = 1;
}
! else if (remove_unused_vars)
{
/* If we were unable to completely eliminate the BIND_EXPR,
go ahead and prune out any unused variables. We do not
*************** remove_useless_stmts_and_vars (tree *fir
*** 1785,1798 ****
static void
remove_unreachable_blocks (void)
{
! int i, n;
find_unreachable_blocks ();
! /* n_basic_blocks will change constantly as we delete blocks, so get a
! copy first. */
! n = n_basic_blocks;
! for (i = 0; i < n; i++)
{
basic_block bb = BASIC_BLOCK (i);
--- 1785,1797 ----
static void
remove_unreachable_blocks (void)
{
! int i;
find_unreachable_blocks ();
! /* Remove unreachable blocks in reverse. That will expose more unnecessary
! COMPOUND_EXPRs that we can remove. */
! for (i = n_basic_blocks - 1; i >= 0; i--)
{
basic_block bb = BASIC_BLOCK (i);
*************** remove_bb (basic_block bb, int remove_st
*** 1915,1922 ****
loc.line = get_lineno (stmt);
bsi_remove (&i);
}
- else
- bsi_next (&i);
}
/* If requested, give a warning that the first statement in the
--- 1914,1919 ----
*************** bsi_remove (block_stmt_iterator *i)
*** 2055,2068 ****
{
if (TREE_CODE (t) == COMPOUND_EXPR)
{
! basic_block bb = bb_for_stmt (TREE_OPERAND (t, 0));
remove_stmt (&TREE_OPERAND (t, 0));
! /* If both operands are empty and they belong to the same basic
! block, then delete the whole COMPOUND_EXPR. */
if (IS_EMPTY_STMT (TREE_OPERAND (t, 1))
! && bb == bb_for_stmt (TREE_OPERAND (t, 1)))
remove_stmt (i->tp);
}
else
--- 2052,2069 ----
{
if (TREE_CODE (t) == COMPOUND_EXPR)
{
! basic_block op0_bb = bb_for_stmt (TREE_OPERAND (t, 0));
! basic_block op1_bb = bb_for_stmt (TREE_OPERAND (t, 1));
remove_stmt (&TREE_OPERAND (t, 0));
! /* If both operands are empty and they are not associated
! with different basic blocks, then delete the whole
! COMPOUND_EXPR. */
if (IS_EMPTY_STMT (TREE_OPERAND (t, 1))
! && (op0_bb == NULL
! || op1_bb == NULL
! || op0_bb == op1_bb))
remove_stmt (i->tp);
}
else
*************** remove_stmt (tree *stmt_p)
*** 2163,2174 ****
head/tail pointers which point into operands of the COMPOUND_EXPR. */
if (TREE_CODE (stmt) == COMPOUND_EXPR)
{
! if (&TREE_OPERAND (stmt, 0) == bb->head_tree_p
! || &TREE_OPERAND (stmt, 1) == bb->head_tree_p)
update_head = 1;
! if (&TREE_OPERAND (stmt, 0) == bb->end_tree_p
! || &TREE_OPERAND (stmt, 1) == bb->end_tree_p)
update_end = 1;
}
--- 2164,2190 ----
head/tail pointers which point into operands of the COMPOUND_EXPR. */
if (TREE_CODE (stmt) == COMPOUND_EXPR)
{
! basic_block op0_bb = bb_for_stmt (TREE_OPERAND (stmt, 0));
! basic_block op1_bb = bb_for_stmt (TREE_OPERAND (stmt, 1));
!
! #ifdef ENABLE_CHECKING
! if (op0_bb && op1_bb && op0_bb != op1_bb)
! abort ();
! #endif
!
! if (op0_bb)
! bb = op0_bb;
! else
! bb = op1_bb;
!
! if (bb
! && (&TREE_OPERAND (stmt, 0) == bb->head_tree_p
! || &TREE_OPERAND (stmt, 1) == bb->head_tree_p))
update_head = 1;
! if (bb
! && (&TREE_OPERAND (stmt, 0) == bb->end_tree_p
! || &TREE_OPERAND (stmt, 1) == bb->end_tree_p))
update_end = 1;
}
*************** linearize_control_structures (void)
*** 2485,2490 ****
--- 2501,2542 ----
}
}
+ /* If all the phi nodes in PHI have alternatives for BB1 and BB2 and
+ those alterantives are equal in each of the PHI nodes, then return
+ nonzero, else return zero. */
+
+ static int
+ phi_alternatives_equal (tree phi, basic_block bb1, basic_block bb2)
+ {
+ /* Walk through each PHI nodes on the chain. */
+ for ( ; phi ; phi = TREE_CHAIN (phi))
+ {
+ int i;
+ tree val1 = NULL;
+ tree val2 = NULL;
+
+ /* Find the alterantive associated with BB1 and BB2. Quit when we
+ have found both or we exhaust the alternatives. */
+ for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ {
+ if (PHI_ARG_EDGE (phi, i)->src == bb1)
+ val1 = PHI_ARG_DEF (phi, i);
+ if (PHI_ARG_EDGE (phi, i)->src == bb2)
+ val2 = PHI_ARG_DEF (phi, i);
+
+ if (val1 && val2)
+ break;
+ }
+
+ /* If we exhaused the alternatives or the alternatives found are
+ not equal, then return false. */
+ if (i == PHI_NUM_ARGS (phi)
+ || ! operand_equal_p (val1, val2, 0))
+ return false;
+ }
+
+ return true;
+ }
/* Convert conditional expressions of the form 'if (1)' and 'if (0)' into
straight line code. ENTRY_P is a pointer to the COND_EXPR statement to
*************** linearize_cond_expr (tree *entry_p, basi
*** 2510,2516 ****
if (pdom_info == NULL)
pdom_info = calculate_dominance_info (CDI_POST_DOMINATORS);
pdom_bb = get_immediate_dominator (pdom_info, bb);
! if (!pdom_bb || !phi_nodes (pdom_bb))
{
/* While neither arm of the conditional has any code, there
may still be important edges attached to those arms such
--- 2562,2575 ----
if (pdom_info == NULL)
pdom_info = calculate_dominance_info (CDI_POST_DOMINATORS);
pdom_bb = get_immediate_dominator (pdom_info, bb);
!
! /* If there is no post dominator, or the post dominator has no
! PHI nodes, or the PHI node alternatives are equal, then we
! can eliminate this conditional. */
! if (!pdom_bb
! || !phi_nodes (pdom_bb)
! || phi_alternatives_equal (phi_nodes (pdom_bb),
! then_block, else_block))
{
/* While neither arm of the conditional has any code, there
may still be important edges attached to those arms such
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-optimize.c,v
retrieving revision 1.1.4.41
diff -c -3 -p -r1.1.4.41 tree-optimize.c
*** tree-optimize.c 15 Jul 2003 05:53:16 -0000 1.1.4.41
--- tree-optimize.c 5 Aug 2003 15:58:24 -0000
*************** optimize_function_tree (tree fndecl)
*** 56,61 ****
--- 56,66 ----
/* Build the flowgraph. */
init_flow ();
+
+ /* Run a pass over the statements deleting any obviously useless
+ statements before we build the CFG. */
+ remove_useless_stmts_and_vars (&DECL_SAVED_TREE (fndecl), 0);
+
build_tree_cfg (fnbody);
/* Begin analysis and optimization passes. */