This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Improve optimization of SWITCH_EXPRs
- From: law at redhat dot com
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 14 Oct 2003 08:37:45 -0600
- Subject: [tree-ssa] Improve optimization of SWITCH_EXPRs
- Reply-to: law at redhat dot com
This is something that's been sitting in my tree for a while. I wanted to
flush it out before the upcoming changes to the dominator code to separate
out the optimizations from the dominator walk.
All this patch does is allow us to optimize switch statements better. Namely
we recognize that if we collapse the switch condition down to a constant
that we're ultimately going to modify the CFG. Additionally, we can now
optimize away casts which appear on SWITCH_COND if we've already computed
the value into some other temporary.
This patch also changes the dominator optimizer to use
cleanup_{switch,cond}_expr_graph from tree-cfg.c instead of having its
own variant and cleans up access to the condition inside COND_EXPRs and
SWITCH_EXPRs so that they use the proper accessor macros instead of
relying on knowing the condition is at TREE_OPERAND (blah, 0).
* tree-cfg.c (cleanup_control_flow): Pass last statement down to
cleanup_cond_expr_graph and cleanup_switch_expr_graph.
(cleanup_cond_expr_graph): Accept statement from caller and
use it. Return nonzero if the predicate was constant. No longer
static.
(cleanup_switch_expr_graph): Similarly.
(disconnect_unreachable_case_labels): Similarly, except that it
is still static.
* tree-flow.h (cleanup_cond_expr_graph): Prototype.
(cleanup_switch_expr_graph): Similarly.
* tree-ssa-dom.c (optimize_stmt): Also optimize the condition
in a SWITCH_EXPR. Use COND_EXPR_COND and SWITCH_COND to get
conditions instead of relying upon known operand positions.
Use cleanup_cond_expr_graph and cleanup_switch_expr_graph rather
than open coding equivalents.
(lookup_avail_expr): Handle SWITCH_EXPRs. Use COND_EXPR_COND and
SWITCH_COND to get conditions instead of relying upon known
operand positions.
(avail_expr_hash, avail_expr_eq): Similarly.
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.174
diff -c -3 -p -r1.1.4.174 tree-cfg.c
*** tree-cfg.c 13 Oct 2003 15:35:55 -0000 1.1.4.174
--- tree-cfg.c 14 Oct 2003 14:28:35 -0000
*************** static void remove_stmt (tree *, bool);
*** 124,132 ****
static bool blocks_unreachable_p (bitmap);
static void remove_blocks (bitmap);
static void cleanup_control_flow (void);
! static void cleanup_cond_expr_graph (basic_block);
! static void cleanup_switch_expr_graph (basic_block);
! static void disconnect_unreachable_case_labels (basic_block);
static edge find_taken_edge_cond_expr (basic_block, tree);
static edge find_taken_edge_switch_expr (basic_block, tree);
static bool value_matches_some_label (edge, tree, edge *);
--- 124,130 ----
static bool blocks_unreachable_p (bitmap);
static void remove_blocks (bitmap);
static void cleanup_control_flow (void);
! static bool disconnect_unreachable_case_labels (basic_block, tree);
static edge find_taken_edge_cond_expr (basic_block, tree);
static edge find_taken_edge_switch_expr (basic_block, tree);
static bool value_matches_some_label (edge, tree, edge *);
*************** cleanup_control_flow (void)
*** 2016,2024 ****
{
enum tree_code code = TREE_CODE (last);
if (code == COND_EXPR)
! cleanup_cond_expr_graph (bb);
else if (code == SWITCH_EXPR)
! cleanup_switch_expr_graph (bb);
}
}
}
--- 2014,2022 ----
{
enum tree_code code = TREE_CODE (last);
if (code == COND_EXPR)
! cleanup_cond_expr_graph (bb, last);
else if (code == SWITCH_EXPR)
! cleanup_switch_expr_graph (bb, last);
}
}
}
*************** cleanup_control_flow (void)
*** 2030,2041 ****
If the predicate of the COND_EXPR node in block BB is constant,
disconnect the subgraph that contains the clause that is never executed.
*/
! static void
! cleanup_cond_expr_graph (basic_block bb)
{
- tree cond_expr = last_stmt (bb);
tree val;
edge taken_edge;
#if defined ENABLE_CHECKING
if (cond_expr == NULL_TREE || TREE_CODE (cond_expr) != COND_EXPR)
--- 2028,2039 ----
If the predicate of the COND_EXPR node in block BB is constant,
disconnect the subgraph that contains the clause that is never executed.
*/
! bool
! cleanup_cond_expr_graph (basic_block bb, tree cond_expr)
{
tree val;
edge taken_edge;
+ bool retval = false;
#if defined ENABLE_CHECKING
if (cond_expr == NULL_TREE || TREE_CODE (cond_expr) != COND_EXPR)
*************** cleanup_cond_expr_graph (basic_block bb)
*** 2053,2061 ****
{
next = e->succ_next;
if (e != taken_edge)
! ssa_remove_edge (e);
}
}
}
--- 2051,2063 ----
{
next = e->succ_next;
if (e != taken_edge)
! {
! ssa_remove_edge (e);
! retval = true;
! }
}
}
+ return retval;
}
*************** cleanup_cond_expr_graph (basic_block bb)
*** 2066,2086 ****
constant, disconnect all the subgraphs for all the case labels that will
never be taken. */
! static void
! cleanup_switch_expr_graph (basic_block switch_bb)
{
int found = 0;
- #if defined ENABLE_CHECKING
- tree switch_expr = last_stmt (switch_bb);
- #endif
edge e;
#if defined ENABLE_CHECKING
if (switch_expr == NULL_TREE || TREE_CODE (switch_expr) != SWITCH_EXPR)
abort ();
#endif
! disconnect_unreachable_case_labels (switch_bb);
/* If the switch() has a default label, remove the fallthru edge that was
created when we processed the entry block for the switch() statement.
*/
--- 2068,2086 ----
constant, disconnect all the subgraphs for all the case labels that will
never be taken. */
! bool
! cleanup_switch_expr_graph (basic_block switch_bb, tree switch_expr)
{
int found = 0;
edge e;
+ bool retval;
#if defined ENABLE_CHECKING
if (switch_expr == NULL_TREE || TREE_CODE (switch_expr) != SWITCH_EXPR)
abort ();
#endif
! retval = disconnect_unreachable_case_labels (switch_bb, switch_expr);
/* If the switch() has a default label, remove the fallthru edge that was
created when we processed the entry block for the switch() statement.
*/
*************** cleanup_switch_expr_graph (basic_block s
*** 2097,2108 ****
basic_block chain_bb = successor_block (switch_bb);
edge e = find_edge (switch_bb, chain_bb);
if (e)
! ssa_remove_edge (e);
found = 1;
break;
}
}
}
}
--- 2097,2112 ----
basic_block chain_bb = successor_block (switch_bb);
edge e = find_edge (switch_bb, chain_bb);
if (e)
! {
! ssa_remove_edge (e);
! retval = true;
! }
found = 1;
break;
}
}
}
+ return retval;
}
*************** cleanup_switch_expr_graph (basic_block s
*** 2111,2125 ****
If the switch() statement starting at basic block BB has a constant
condition, disconnect all the unreachable case labels. */
! static void
! disconnect_unreachable_case_labels (basic_block bb)
{
edge taken_edge;
tree switch_val;
! tree t = last_stmt (bb);
if (t == NULL_TREE)
! return;
switch_val = SWITCH_COND (t);
taken_edge = find_taken_edge (bb, switch_val);
--- 2115,2129 ----
If the switch() statement starting at basic block BB has a constant
condition, disconnect all the unreachable case labels. */
! static bool
! disconnect_unreachable_case_labels (basic_block bb, tree t)
{
edge taken_edge;
tree switch_val;
! bool retval = false;
if (t == NULL_TREE)
! return retval;
switch_val = SWITCH_COND (t);
taken_edge = find_taken_edge (bb, switch_val);
*************** disconnect_unreachable_case_labels (basi
*** 2133,2141 ****
{
next = e->succ_next;
if (e != taken_edge)
! ssa_remove_edge (e);
}
}
}
--- 2137,2149 ----
{
next = e->succ_next;
if (e != taken_edge)
! {
! ssa_remove_edge (e);
! retval = true;
! }
}
}
+ return retval;
}
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.126
diff -c -3 -p -r1.1.4.126 tree-flow.h
*** tree-flow.h 13 Oct 2003 15:35:58 -0000 1.1.4.126
--- tree-flow.h 14 Oct 2003 14:28:35 -0000
*************** extern void bsi_move_before (block_stmt_
*** 434,439 ****
--- 434,441 ----
extern void bsi_move_after (block_stmt_iterator, block_stmt_iterator);
extern void bsi_move_to_bb_end (block_stmt_iterator, basic_block);
extern basic_block label_to_block (tree);
+ extern bool cleanup_cond_expr_graph (basic_block, tree);
+ extern bool cleanup_switch_expr_graph (basic_block, tree);
/* In tree-dfa.c */
void find_referenced_vars (tree);
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.55
diff -c -3 -p -r1.1.2.55 tree-ssa-dom.c
*** tree-ssa-dom.c 13 Oct 2003 15:36:02 -0000 1.1.2.55
--- tree-ssa-dom.c 14 Oct 2003 14:28:39 -0000
*************** static tree simplify_cond_and_lookup_ava
*** 155,161 ****
static tree find_equivalent_equality_comparison (tree);
static void record_range (tree, basic_block, varray_type);
static bool extract_range_from_cond (tree, tree *, tree *, int *);
! static bool cprop_into_stmt (tree );
/* Optimize function FNDECL based on the dominator tree. This does
simple const/copy propagation and redundant expression elimination using
--- 155,161 ----
static tree find_equivalent_equality_comparison (tree);
static void record_range (tree, basic_block, varray_type);
static bool extract_range_from_cond (tree, tree *, tree *, int *);
! static bool cprop_into_stmt (tree);
/* Optimize function FNDECL based on the dominator tree. This does
simple const/copy propagation and redundant expression elimination using
*************** optimize_stmt (block_stmt_iterator si, v
*** 1527,1533 ****
(TREE_OPERAND (TREE_OPERAND (stmt, 0), 1))))
|| (TREE_CODE (stmt) == MODIFY_EXPR
&& ! TREE_SIDE_EFFECTS (TREE_OPERAND (stmt, 1)))
! || TREE_CODE (stmt) == COND_EXPR));
if (may_optimize_p)
{
--- 1527,1534 ----
(TREE_OPERAND (TREE_OPERAND (stmt, 0), 1))))
|| (TREE_CODE (stmt) == MODIFY_EXPR
&& ! TREE_SIDE_EFFECTS (TREE_OPERAND (stmt, 1)))
! || TREE_CODE (stmt) == COND_EXPR
! || TREE_CODE (stmt) == SWITCH_EXPR));
if (may_optimize_p)
{
*************** optimize_stmt (block_stmt_iterator si, v
*** 1573,1579 ****
opt_stats.num_exprs_considered++;
if (TREE_CODE (stmt) == COND_EXPR)
! expr_p = &TREE_OPERAND (stmt, 0);
else if (TREE_CODE (stmt) == RETURN_EXPR && TREE_OPERAND (stmt, 0))
expr_p = &TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
else
--- 1574,1582 ----
opt_stats.num_exprs_considered++;
if (TREE_CODE (stmt) == COND_EXPR)
! expr_p = &COND_EXPR_COND (stmt);
! else if (TREE_CODE (stmt) == SWITCH_EXPR)
! expr_p = &SWITCH_COND (stmt);
else if (TREE_CODE (stmt) == RETURN_EXPR && TREE_OPERAND (stmt, 0))
expr_p = &TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
else
*************** optimize_stmt (block_stmt_iterator si, v
*** 1766,1793 ****
where it goes. In which case we can remove some edges, simplify
some PHI nodes, maybe even avoid optimizing some blocks completely,
etc. */
! if (TREE_CODE (stmt) == COND_EXPR && ann->modified)
{
! basic_block bb = bb_for_stmt (stmt);
! edge taken_edge = find_taken_edge (bb, TREE_OPERAND (stmt, 0));
! if (taken_edge)
! {
! edge e, next;
! /* The other edges leaving this block are not executable
! and can be removed. */
! for (e = bb_for_stmt (stmt)->succ; e; e = next)
! {
! next = e->succ_next;
! if (e != taken_edge)
! {
! ssa_remove_edge (e);
! *cfg_altered = true;
! }
! }
! }
}
!
return may_have_exposed_new_symbols;
}
--- 1769,1783 ----
where it goes. In which case we can remove some edges, simplify
some PHI nodes, maybe even avoid optimizing some blocks completely,
etc. */
! if (ann->modified)
{
! if (TREE_CODE (stmt) == COND_EXPR)
! *cfg_altered |= cleanup_cond_expr_graph (bb_for_stmt (stmt), stmt);
! if (TREE_CODE (stmt) == SWITCH_EXPR)
! *cfg_altered |= cleanup_switch_expr_graph (bb_for_stmt (stmt), stmt);
}
!
return may_have_exposed_new_symbols;
}
*************** lookup_avail_expr (tree stmt,
*** 1901,1914 ****
tree lhs;
tree temp;
! /* For a COND_EXPR, the expression we care about is in operand 0, not
! operand 1. Also note that for a COND_EXPR, we merely want to see if
! we have the expression in the hash table, we do not want to create
! a new entry in the hash table. */
if (TREE_CODE (stmt) == COND_EXPR)
! rhs = TREE_OPERAND (stmt, 0);
! /* For RETURN_EXPR, we want the RHS of the MODIFY_EXPR in operand 0
! of the RETURN_EXPR. */
else if (TREE_CODE (stmt) == RETURN_EXPR
&& TREE_OPERAND (stmt, 0))
rhs = TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
--- 1891,1903 ----
tree lhs;
tree temp;
! /* Find the location of the expression we care about. Unfortunately,
! its location differs depending on the type of statement we are
! examining. */
if (TREE_CODE (stmt) == COND_EXPR)
! rhs = COND_EXPR_COND (stmt);
! else if (TREE_CODE (stmt) == SWITCH_EXPR)
! rhs = SWITCH_COND (stmt);
else if (TREE_CODE (stmt) == RETURN_EXPR
&& TREE_OPERAND (stmt, 0))
rhs = TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
*************** get_eq_expr_value (tree if_stmt, int tru
*** 2075,2081 ****
cond = COND_EXPR_COND (if_stmt);
value = NULL;
-
/* If the conditional is a single variable 'X', return 'X = 1' for
the true arm and 'X = 0' on the false arm. */
if (TREE_CODE (cond) == SSA_NAME)
--- 2064,2069 ----
*************** avail_expr_hash (const void *p)
*** 2153,2164 ****
varray_type ops;
tree stmt = (tree) p;
! /* If we're hashing a COND_EXPR, the expression we care about is
! in operand position 0, not position 1. */
if (TREE_CODE (stmt) == COND_EXPR)
! rhs = TREE_OPERAND (stmt, 0);
! /* If we're hasing a RETURN_EXPR, the expression we care about
! is position 1 of the MODIFY_EXPR at position 0 in the RETURN_EXPR. */
else if (TREE_CODE (stmt) == RETURN_EXPR && TREE_OPERAND (stmt, 0))
rhs = TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
else
--- 2141,2153 ----
varray_type ops;
tree stmt = (tree) p;
! /* Find the location of the expression we care about. Unfortunately,
! its location differs depending on the type of statement we are
! examining. */
if (TREE_CODE (stmt) == COND_EXPR)
! rhs = COND_EXPR_COND (stmt);
! else if (TREE_CODE (stmt) == SWITCH_EXPR)
! rhs = SWITCH_COND (stmt);
else if (TREE_CODE (stmt) == RETURN_EXPR && TREE_OPERAND (stmt, 0))
rhs = TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
else
*************** avail_expr_eq (const void *p1, const voi
*** 2188,2194 ****
s1 = (tree) p1;
if (TREE_CODE (s1) == COND_EXPR)
! rhs1 = TREE_OPERAND (s1, 0);
else if (TREE_CODE (s1) == RETURN_EXPR && TREE_OPERAND (s1, 0))
rhs1 = TREE_OPERAND (TREE_OPERAND (s1, 0), 1);
else
--- 2177,2185 ----
s1 = (tree) p1;
if (TREE_CODE (s1) == COND_EXPR)
! rhs1 = COND_EXPR_COND (s1);
! else if (TREE_CODE (s1) == SWITCH_EXPR)
! rhs1 = SWITCH_COND (s1);
else if (TREE_CODE (s1) == RETURN_EXPR && TREE_OPERAND (s1, 0))
rhs1 = TREE_OPERAND (TREE_OPERAND (s1, 0), 1);
else
*************** avail_expr_eq (const void *p1, const voi
*** 2196,2202 ****
s2 = (tree) p2;
if (TREE_CODE (s2) == COND_EXPR)
! rhs2 = TREE_OPERAND (s2, 0);
else if (TREE_CODE (s2) == RETURN_EXPR && TREE_OPERAND (s2, 0))
rhs2 = TREE_OPERAND (TREE_OPERAND (s2, 0), 1);
else
--- 2187,2195 ----
s2 = (tree) p2;
if (TREE_CODE (s2) == COND_EXPR)
! rhs2 = COND_EXPR_COND (s2);
! else if (TREE_CODE (s2) == SWITCH_EXPR)
! rhs2 = SWITCH_COND (s2);
else if (TREE_CODE (s2) == RETURN_EXPR && TREE_OPERAND (s2, 0))
rhs2 = TREE_OPERAND (TREE_OPERAND (s2, 0), 1);
else