This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] COND_EXPR lowering preview
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org, law at redhat dot com, gcc at gcc dot gnu dot org
- Cc: dnovillo at redhat dot com
- Date: Tue, 26 Aug 2003 20:53:29 +0200
- Subject: [tree-ssa] COND_EXPR lowering preview
Hello,
here is the patch; since it is just preview and I am lazy, it includes
some parts that should be separated, most imporatantly tree-ssa-dom fixes.
The patch bootstraps and passes regtesting.
It disables control structures removal in dce; this also has to be
handled separately.
It removes linearization from cfg cleanup, since the half of it
is redundant with the patch and the rest contains several
serious bugs (the most important one being that it uses merge_blocks; this
function contains more bugs than correct code :-(
Some possibly useful cleanups were removed from
remove_useless_stmts_and_vars; this function is not suitable for
work over unstructured code.
COND_EXPR lowering is being done in gimplification; if you like/dislike
it, cry -- I personally have no opinion whether it should be done there
or somewhere later.
Zdenek
* gimplify.c (build_and_jump): Export.
(gimplify_cond_expr): Lower the COND_EXPR.
* tree-cfg.c (make_cond_expr_blocks): Removed.
(remove_unreachable_blocks): Export.
(linearize_control_structures, linearize_cond_expr): Removed.
(merge_tree_blocks, phi_alternatives_equal): Mark as unused.
(enum find_location_action): EDGE_INSERT_LOCATION_NEW_ELSE removed.
(make_blocks): Don't call make_cond_expr_blocks.
(set_parent_stmt): Prevent COND_EXPRs from being parent statements.
(find_contained_blocks): Don't handle COND_EXPRs.
(make_cond_expr_edges): Modified.
(cleanup_tree_cfg): Don't call linearize_control_structures. Add
verify_flow_info call.
(remove_useless_stmts_and_vars): Don't handle COND_EXPRs.
(remove_unreachable_blocks): Export. Make it work with uncompacted
blocks. Return true if something has changed.
(remove_unreachable_block, bsi_insert_before): Don't handle COND_EXPRs.
(cleanup_cond_expr_graph): Also replace the cond_expr with goto.
(find_taken_edge_cond_expr, dump_tree_bb, find_insert_location,
remove_bb, bsi_insert_on_edge_immediate): Handle new form of COND_EXPRs.
(tree_verify_flow_info): Check that the COND_EXPRs are kept lowered.
(debug_tree_bb_n): New.
* tree-flow.h (debug_tree_bb_n, remove_unreachable_blocks): Declare.
* tree-simple.h (build_and_jump): Declare.
* tree-ssa-dce.c (remove_conditional, stmt_useful_p, process_worklist,
remove_dead_stmts, remove_dead_phis, remove_dead_stmt,
remove_conditional): Disable control structures removal.
* tree-ssa-dom.c (edges_to_redirect, redirection_targets): New
variables.
(thread_edge): New.
(optimize_block, optimize_stmt): Record whether cfg has changed.
Just record opportunities for jump threading.
(tree_ssa_dominator_optimize): Recompute dominator tree if cfg has
changed. Execute scheduled edge redirections.
Index: gimplify.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/gimplify.c,v
retrieving revision 1.1.2.73
diff -c -3 -p -r1.1.2.73 gimplify.c
*** gimplify.c 25 Aug 2003 20:52:18 -0000 1.1.2.73
--- gimplify.c 26 Aug 2003 18:15:36 -0000
*************** static hashval_t gimple_tree_hash (const
*** 83,89 ****
static int gimple_tree_eq (const void *, const void *);
static tree lookup_tmp_var (tree, bool);
static tree internal_get_tmp_var (tree, tree *, bool);
- static tree build_and_jump (tree *);
static tree shortcut_cond_expr (tree);
static tree gimple_boolify (tree);
static void gimplify_conversion (tree *);
--- 83,88 ----
*************** gimplify_exit_block_expr (tree *expr_p)
*** 1084,1090 ****
/* Build a GOTO to the LABEL_DECL pointed to by LABEL_P, building it first
if necessary. */
! static tree
build_and_jump (tree *label_p)
{
if (label_p == NULL)
--- 1083,1089 ----
/* Build a GOTO to the LABEL_DECL pointed to by LABEL_P, building it first
if necessary. */
! tree
build_and_jump (tree *label_p)
{
if (label_p == NULL)
*************** shortcut_cond_expr (tree expr)
*** 1838,1850 ****
/* Convert the conditional expression pointed by EXPR_P '(p) ? a : b;'
into
! if (p) if (p)
! t1 = a; a;
! else or else
! t1 = b; b;
t1;
! The second form is used when *EXPR_P is of type void.
PRE_P points to the list where side effects that must happen before
*EXPR_P should be stored. */
--- 1837,1872 ----
/* Convert the conditional expression pointed by EXPR_P '(p) ? a : b;'
into
! if (p)
! goto then_label;
! else
! goto else_label;
!
! then_label:
! t1 = a;
! goto end_label;
!
! else_label:
! t1 = b;
!
! end_label:
t1;
! or (when *EXPR_P is of type void):
!
! if (p)
! goto then_label;
! else
! goto else_label;
!
! then_label:
! a;
! goto end_label;
!
! else_label:
! b;
!
! end_label:
PRE_P points to the list where side effects that must happen before
*EXPR_P should be stored. */
*************** shortcut_cond_expr (tree expr)
*** 1852,1859 ****
static void
gimplify_cond_expr (tree *expr_p, tree *pre_p, tree target)
{
! tree expr = *expr_p;
tree tmp;
/* If this COND_EXPR has a value, copy the values into a temporary within
the arms. */
--- 1874,1883 ----
static void
gimplify_cond_expr (tree *expr_p, tree *pre_p, tree target)
{
! tree expr = *expr_p, then_label, else_label, end_label;
! tree then_branch, else_branch;
tree tmp;
+ int then_is_goto, else_is_goto;
/* If this COND_EXPR has a value, copy the values into a temporary within
the arms. */
*************** gimplify_cond_expr (tree *expr_p, tree *
*** 1921,1942 ****
gimple_pop_condition (pre_p);
! if (TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 1)))
! /* OK */;
! else if (TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 2)))
! /* Rewrite "if (a); else b" to "if (!a) b" */
! {
! TREE_OPERAND (expr, 0) = invert_truthvalue (TREE_OPERAND (expr, 0));
! gimplify_expr (&TREE_OPERAND (expr, 0), pre_p, NULL,
! is_gimple_condexpr, fb_rvalue);
!
! tmp = TREE_OPERAND (expr, 1);
! TREE_OPERAND (expr, 1) = TREE_OPERAND (expr, 2);
! TREE_OPERAND (expr, 2) = tmp;
}
else
! /* Both arms are empty; replace the COND_EXPR with its predicate. */
! *expr_p = TREE_OPERAND (expr, 0);
*expr_p = expr;
}
--- 1945,2017 ----
gimple_pop_condition (pre_p);
! if (!TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 1))
! && !TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 2)))
! {
! /* Both arms are empty; replace the COND_EXPR with its predicate. */
! *expr_p = TREE_OPERAND (expr, 0);
! return;
! }
!
! tmp = COND_EXPR_THEN (expr);
! then_is_goto = (TREE_CODE (tmp) == GOTO_EXPR
! && TREE_CODE (GOTO_DESTINATION (tmp)) == LABEL_DECL
! && ! NONLOCAL_LABEL (GOTO_DESTINATION (tmp))
! && (decl_function_context (GOTO_DESTINATION (tmp))
! == current_function_decl));
! tmp = COND_EXPR_ELSE (expr);
! else_is_goto = (TREE_CODE (tmp) == GOTO_EXPR
! && TREE_CODE (GOTO_DESTINATION (tmp)) == LABEL_DECL
! && ! NONLOCAL_LABEL (GOTO_DESTINATION (tmp))
! && (decl_function_context (GOTO_DESTINATION (tmp))
! == current_function_decl));
!
! if (then_is_goto && else_is_goto)
! {
! *expr_p = expr;
! return;
! }
!
! /* Replace the cond_expr with explicit gotos. */
! then_branch = COND_EXPR_THEN (expr);
! else_branch = COND_EXPR_ELSE (expr);
! if (!then_is_goto)
! {
! then_label = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
! COND_EXPR_THEN (expr) = build_and_jump (&LABEL_EXPR_LABEL (then_label));
! }
! else
! then_label = NULL_TREE;
!
! if (!else_is_goto)
! {
! else_label = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
! COND_EXPR_ELSE (expr) = build_and_jump (&LABEL_EXPR_LABEL (else_label));
}
else
! else_label = NULL_TREE;
!
! end_label = NULL_TREE;
! if (then_label)
! {
! add_tree (then_label, &expr);
! add_tree (then_branch, &expr);
!
! if (else_label)
! {
! end_label = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
! add_tree (build_and_jump (&LABEL_EXPR_LABEL (end_label)), &expr);
! }
! }
!
! if (else_label)
! {
! add_tree (else_label, &expr);
! add_tree (else_branch, &expr);
! }
!
! if (end_label)
! add_tree (end_label, &expr);
*expr_p = expr;
}
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.155
diff -c -3 -p -r1.1.4.155 tree-cfg.c
*** tree-cfg.c 24 Aug 2003 03:04:40 -0000 1.1.4.155
--- tree-cfg.c 26 Aug 2003 18:15:41 -0000
*************** static void free_blocks_annotations (voi
*** 86,92 ****
static void clear_blocks_annotations (void);
static basic_block make_blocks (tree *, tree, tree, basic_block, tree);
static void make_loop_expr_blocks (tree *, basic_block, tree);
- static void make_cond_expr_blocks (tree *, tree, basic_block, tree);
static void make_catch_expr_blocks (tree *, tree, basic_block, tree);
static void make_eh_filter_expr_blocks (tree *, tree, basic_block, tree);
static void make_try_expr_blocks (tree *, tree, basic_block, tree);
--- 86,91 ----
*************** static void tree_loop_optimizer_finalize
*** 130,136 ****
#define REMOVE_NON_CONTROL_STMTS 0x1
#define REMOVE_CONTROL_STMTS 0x2
- static void remove_unreachable_blocks (void);
static void remove_unreachable_block (basic_block);
static void remove_bb (basic_block, int);
static void remove_stmt (tree *, bool);
--- 129,134 ----
*************** static void disconnect_unreachable_case_
*** 144,154 ****
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 *);
- static void linearize_control_structures (void);
- static bool linearize_cond_expr (tree *, basic_block);
static void replace_stmt (tree *, tree *);
static void move_outgoing_edges (basic_block, basic_block);
! static void merge_tree_blocks (basic_block, basic_block);
static bool remap_stmts (basic_block, basic_block, tree *);
static tree *handle_switch_split (basic_block, basic_block);
static tree *handle_switch_fallthru (tree, basic_block, basic_block);
--- 142,152 ----
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 *);
static void replace_stmt (tree *, tree *);
static void move_outgoing_edges (basic_block, basic_block);
! static void merge_tree_blocks (basic_block, basic_block) ATTRIBUTE_UNUSED;
! static int phi_alternatives_equal (tree phi, basic_block, basic_block)
! ATTRIBUTE_UNUSED;
static bool remap_stmts (basic_block, basic_block, tree *);
static tree *handle_switch_split (basic_block, basic_block);
static tree *handle_switch_fallthru (tree, basic_block, basic_block);
*************** enum find_location_action {
*** 169,175 ****
EDGE_INSERT_LOCATION_AFTER,
EDGE_INSERT_LOCATION_THEN,
EDGE_INSERT_LOCATION_ELSE,
- EDGE_INSERT_LOCATION_NEW_ELSE,
EDGE_INSERT_LOCATION_BSI_AFTER };
static tree_stmt_iterator find_insert_location
--- 167,172 ----
*************** make_blocks (tree *first_p, tree next_bl
*** 436,445 ****
append_stmt_to_bb (stmt_p, bb, parent_stmt);
get_stmt_ann (stmt)->scope = scope;
! if (code == LOOP_EXPR)
make_loop_expr_blocks (stmt_p, bb, scope);
- else if (code == COND_EXPR)
- make_cond_expr_blocks (stmt_p, next_block_link, bb, scope);
else if (code == SWITCH_EXPR)
make_switch_expr_blocks (stmt_p, next_block_link, bb, scope);
else if (code == CATCH_EXPR)
--- 433,442 ----
append_stmt_to_bb (stmt_p, bb, parent_stmt);
get_stmt_ann (stmt)->scope = scope;
! if (code == COND_EXPR)
! bb->flags |= BB_CONTROL_EXPR;
! else if (code == LOOP_EXPR)
make_loop_expr_blocks (stmt_p, bb, scope);
else if (code == SWITCH_EXPR)
make_switch_expr_blocks (stmt_p, next_block_link, bb, scope);
else if (code == CATCH_EXPR)
*************** make_loop_expr_blocks (tree *loop_p, bas
*** 599,640 ****
make_blocks (&LOOP_EXPR_BODY (loop), next_block_link, loop, NULL, scope);
}
-
- /* Create the blocks for the COND_EXPR node pointed by COND_P.
-
- NEXT_BLOCK_LINK is the first statement of the successor basic block for
- the block holding *COND_P. If *COND_P is the last statement inside a
- lexical scope, this will be the statement that comes after COND_P's
- container (see the documentation for NEXT_BLOCK_LINK).
-
- ENTRY is the block whose last statement is *COND_P.
-
- SCOPE is the BIND_EXPR node holding *COND_P. */
-
- static void
- make_cond_expr_blocks (tree *cond_p, tree next_block_link,
- basic_block entry, tree scope)
- {
- tree_stmt_iterator si;
- tree cond = *cond_p;
- entry->flags |= BB_CONTROL_EXPR;
-
- /* Determine NEXT_BLOCK_LINK for statements inside the COND_EXPR body. */
- si = tsi_start (cond_p);
- tsi_next (&si);
-
- /* Ignore any empty statements at the tail of this tree. */
- while (!tsi_end_p (si) && tsi_stmt (si) == NULL)
- tsi_next (&si);
-
- if (!tsi_end_p (si) && tsi_stmt (si) != NULL_TREE)
- next_block_link = *(tsi_container (si));
-
- STRIP_CONTAINERS (cond);
- make_blocks (&COND_EXPR_THEN (cond), next_block_link, cond, NULL, scope);
- make_blocks (&COND_EXPR_ELSE (cond), next_block_link, cond, NULL, scope);
- }
-
/* Derive an exception handling region type from STMT. */
static enum eh_region_type
--- 596,601 ----
*************** set_parent_stmt (tree *stmt_p, tree pare
*** 846,851 ****
--- 807,816 ----
{
tree t;
+ if (parent_stmt
+ && TREE_CODE (parent_stmt) == COND_EXPR)
+ abort ();
+
/* Associate *STMT_P (and the trees it contains) to its control parent. */
t = *stmt_p;
do
*************** find_contained_blocks (tree *stmt_p, bit
*** 1118,1128 ****
{
find_contained_blocks (&LOOP_EXPR_BODY (stmt), my_blocks, last_p);
}
- else if (code == COND_EXPR)
- {
- find_contained_blocks (&COND_EXPR_THEN (stmt), my_blocks, last_p);
- find_contained_blocks (&COND_EXPR_ELSE (stmt), my_blocks, last_p);
- }
else if (code == CATCH_EXPR)
{
find_contained_blocks (&CATCH_BODY (stmt), my_blocks, last_p);
--- 1083,1088 ----
*************** static void
*** 1392,1398 ****
make_cond_expr_edges (basic_block bb)
{
tree entry = last_stmt (bb);
! basic_block successor_bb, then_bb, else_bb;
#if defined ENABLE_CHECKING
if (entry == NULL_TREE || TREE_CODE (entry) != COND_EXPR)
--- 1352,1359 ----
make_cond_expr_edges (basic_block bb)
{
tree entry = last_stmt (bb);
! basic_block then_bb, else_bb;
! tree then_label, else_label;
#if defined ENABLE_CHECKING
if (entry == NULL_TREE || TREE_CODE (entry) != COND_EXPR)
*************** make_cond_expr_edges (basic_block bb)
*** 1400,1419 ****
#endif
/* Entry basic blocks for each component. */
! then_bb = bb_for_stmt (COND_EXPR_THEN (entry));
! else_bb = bb_for_stmt (COND_EXPR_ELSE (entry));
! successor_bb = successor_block (bb);
!
! if (then_bb)
! make_edge (bb, then_bb, EDGE_TRUE_VALUE);
!
! if (else_bb)
! make_edge (bb, else_bb, EDGE_FALSE_VALUE);
!
! /* If conditional is missing one of the clauses, make an edge between the
! entry block and the first block outside the conditional. */
! if (!then_bb || !else_bb)
! make_edge (bb, successor_bb, 0);
}
--- 1361,1373 ----
#endif
/* Entry basic blocks for each component. */
! then_label = GOTO_DESTINATION (COND_EXPR_THEN (entry));
! else_label = GOTO_DESTINATION (COND_EXPR_ELSE (entry));
! then_bb = VARRAY_BB (label_to_block_map, LABEL_DECL_INDEX (then_label));
! else_bb = VARRAY_BB (label_to_block_map, LABEL_DECL_INDEX (else_label));
!
! make_edge (bb, then_bb, EDGE_TRUE_VALUE);
! make_edge (bb, else_bb, EDGE_FALSE_VALUE);
}
*************** cleanup_tree_cfg (void)
*** 1521,1527 ****
cleanup_control_flow ();
remove_unreachable_blocks ();
- linearize_control_structures ();
if (pdom_info != NULL)
{
free_dominance_info (pdom_info);
--- 1480,1485 ----
*************** cleanup_tree_cfg (void)
*** 1539,1544 ****
--- 1497,1505 ----
clear_dom_children (BASIC_BLOCK (i));
}
+ #ifdef ENABLE_CHECKING
+ verify_flow_info ();
+ #endif
timevar_pop (TV_TREE_CLEANUP_CFG);
}
*************** remove_useless_stmts_and_vars (tree *fir
*** 1590,1660 ****
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);
- cond = COND_EXPR_COND (*stmt_p);
-
- /* We may not have been able to completely optimize away
- the condition previously due to the existence of a
- label in one arm. If the label has since become unreachable
- then we may be able to zap the entire conditional here.
-
- If so, replace the COND_EXPR and set up to repeat this
- optimization pass. */
- if (integer_nonzerop (cond) && IS_EMPTY_STMT (else_clause))
- {
- *stmt_p = then_clause;
- repeat = 1;
- }
- else if (integer_zerop (cond) && IS_EMPTY_STMT (then_clause))
- {
- *stmt_p = else_clause;
- repeat = 1;
- }
- else if (TREE_CODE (then_clause) == GOTO_EXPR
- && TREE_CODE (else_clause) == GOTO_EXPR
- && (GOTO_DESTINATION (then_clause)
- == GOTO_DESTINATION (else_clause)))
- {
- *stmt_p = then_clause;
- repeat = 1;
- }
- /* If the THEN/ELSE clause merely assigns a value to
- a variable/parameter which is already known to contain
- that value, then remove the useless THEN/ELSE clause. */
- else if (TREE_CODE (cond) == VAR_DECL
- || TREE_CODE (cond) == PARM_DECL)
- {
- if (TREE_CODE (else_clause) == MODIFY_EXPR
- && TREE_OPERAND (else_clause, 0) == cond
- && integer_zerop (TREE_OPERAND (else_clause, 1)))
- COND_EXPR_ELSE (*stmt_p) = build_empty_stmt ();
- }
- else if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
- && (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
- || TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL)
- && TREE_CONSTANT (TREE_OPERAND (cond, 1)))
- {
- tree clause = (TREE_CODE (cond) == EQ_EXPR
- ? then_clause : else_clause);
- tree *location = (TREE_CODE (cond) == EQ_EXPR
- ? &COND_EXPR_THEN (*stmt_p)
- : &COND_EXPR_ELSE (*stmt_p));
-
- if (TREE_CODE (clause) == MODIFY_EXPR
- && TREE_OPERAND (clause, 0) == TREE_OPERAND (cond, 0)
- && TREE_OPERAND (clause, 1) == TREE_OPERAND (cond, 1))
- *location = build_empty_stmt ();
- }
- }
else if (code == SWITCH_EXPR)
repeat |= remove_useless_stmts_and_vars (&SWITCH_BODY (*stmt_p),
remove_unused_vars);
--- 1551,1556 ----
*************** remove_useless_stmts_and_vars (tree *fir
*** 1849,1864 ****
/* Delete all unreachable basic blocks. */
! 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);
--- 1745,1761 ----
/* Delete all unreachable basic blocks. */
! bool
remove_unreachable_blocks (void)
{
int i;
+ int ret = false;
find_unreachable_blocks ();
/* Remove unreachable blocks in reverse. That will expose more unnecessary
COMPOUND_EXPRs that we can remove. */
! for (i = last_basic_block - 1; i >= 0; i--)
{
basic_block bb = BASIC_BLOCK (i);
*************** remove_unreachable_blocks (void)
*** 1868,1875 ****
continue;
if (!(bb->flags & BB_REACHABLE))
! remove_unreachable_block (bb);
}
}
--- 1765,1777 ----
continue;
if (!(bb->flags & BB_REACHABLE))
! {
! remove_unreachable_block (bb);
! ret = true;
! }
}
+
+ return ret;
}
*************** remove_unreachable_block (basic_block bb
*** 1917,1925 ****
So cleanup any variable references in toplevel control
structures. This may or may not be sufficient. */
! if (TREE_CODE (*last_p) == COND_EXPR)
! COND_EXPR_COND (*last_p) = integer_zero_node;
! else if (TREE_CODE (*last_p) == SWITCH_EXPR)
SWITCH_COND (*last_p) = integer_zero_node;
remove_bb (bb, REMOVE_NON_CONTROL_STMTS);
}
--- 1819,1825 ----
So cleanup any variable references in toplevel control
structures. This may or may not be sufficient. */
! if (TREE_CODE (*last_p) == SWITCH_EXPR)
SWITCH_COND (*last_p) = integer_zero_node;
remove_bb (bb, REMOVE_NON_CONTROL_STMTS);
}
*************** remove_bb (basic_block bb, int remove_st
*** 1994,2000 ****
set_bb_for_stmt (stmt, NULL);
if (remove_stmt_flags)
{
! int ctrl_stmt = is_ctrl_stmt (stmt);
loc.file = get_filename (stmt);
loc.line = get_lineno (stmt);
--- 1894,1901 ----
set_bb_for_stmt (stmt, NULL);
if (remove_stmt_flags)
{
! int ctrl_stmt = (is_ctrl_stmt (stmt)
! && TREE_CODE (stmt) != COND_EXPR);
loc.file = get_filename (stmt);
loc.line = get_lineno (stmt);
*************** bsi_replace (block_stmt_iterator bsi, tr
*** 2192,2199 ****
modify_stmt (bsi_stmt (bsi));
}
-
-
/* Remove statement *STMT_P.
Update all references associated with it. Note that this function will
--- 2093,2098 ----
*************** cleanup_cond_expr_graph (basic_block bb)
*** 2346,2351 ****
--- 2245,2251 ----
tree cond_expr = last_stmt (bb);
tree val;
edge taken_edge;
+ block_stmt_iterator bsi;
#if defined ENABLE_CHECKING
if (cond_expr == NULL_TREE || TREE_CODE (cond_expr) != COND_EXPR)
*************** cleanup_cond_expr_graph (basic_block bb)
*** 2365,2371 ****
--- 2265,2280 ----
if (e != taken_edge)
ssa_remove_edge (e);
}
+
+ bsi = bsi_last (bb);
+ if (taken_edge->flags & EDGE_TRUE_VALUE)
+ bsi_replace (bsi, COND_EXPR_THEN (cond_expr));
+ else if (taken_edge->flags & EDGE_FALSE_VALUE)
+ bsi_replace (bsi, COND_EXPR_ELSE (cond_expr));
+ else
+ abort ();
}
+
}
*************** find_taken_edge_cond_expr (basic_block b
*** 2507,2515 ****
|| ((e->flags & EDGE_FALSE_VALUE) && always_false))
return e;
! /* If E is not going to the THEN nor the ELSE clause, then it's
! the fallthru edge to the successor block of the if() block. */
! return find_edge (bb, successor_block (bb));
}
--- 2416,2422 ----
|| ((e->flags & EDGE_FALSE_VALUE) && always_false))
return e;
! return NULL;
}
*************** value_matches_some_label (edge dest_edge
*** 2583,2616 ****
return false;
}
-
- /* Convert control structures into linear code whenever possible. */
-
- static void
- linearize_control_structures (void)
- {
- basic_block bb;
-
- FOR_EACH_BB (bb)
- {
- tree *entry_p;
-
- if (!(bb->flags & BB_CONTROL_EXPR))
- continue;
-
- /* After converting the current COND_EXPR into straight line code it
- may happen that the block that was merged into BB also ends in a
- COND_EXPR (nested conditionals). Therefore, we need to iterate
- until we either fail to linearize the conditional or BB ends in
- something other than a conditional. */
- entry_p = last_stmt_ptr (bb);
- while (entry_p
- && TREE_CODE (*entry_p) == COND_EXPR
- && linearize_cond_expr (entry_p, bb))
- entry_p = last_stmt_ptr (bb);
- }
- }
-
/* 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. */
--- 2490,2495 ----
*************** phi_alternatives_equal (tree phi, basic_
*** 2648,2760 ****
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
- check. Return true if the conditional was modified. */
-
- static bool
- linearize_cond_expr (tree *entry_p, basic_block bb)
- {
- basic_block pdom_bb;
- tree entry = *entry_p;
- tree pred = COND_EXPR_COND (entry);
- tree then_clause = COND_EXPR_THEN (entry);
- tree else_clause = COND_EXPR_ELSE (entry);
- basic_block then_block = bb_for_stmt (then_clause);
- basic_block else_block = bb_for_stmt (else_clause);
- int always_true = (simple_cst_equal (pred, integer_one_node) == 1);
- int always_false = (simple_cst_equal (pred, integer_zero_node) == 1);
-
- /* Remove the conditional if both branches have been removed. */
- if (body_is_empty (then_clause) && body_is_empty (else_clause))
- {
- /* Calculate dominance info, if it hasn't been computed yet. */
- 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
- as the backedge in a loop, or exception handling related
- edges (the common characteristic is they are edges implied
- by control structures which are not explicitly represented
- in the IL). */
- if ((always_true || ! always_false) && then_block)
- move_outgoing_edges (bb, then_block);
-
- if ((always_false || ! always_true) && else_block)
- move_outgoing_edges (bb, else_block);
-
- /* Now that we've moved all the edges, go ahead and remove
- the disconnected blocks. Note this will remove any edges
- from BB to the disconnected blocks. */
- if (then_block)
- remove_bb (then_block, REMOVE_NO_STMTS);
- if (else_block)
- remove_bb (else_block, REMOVE_NO_STMTS);
-
- /* And finally remove the useless statement. */
- remove_stmt (entry_p, true);
- return true;
- }
- }
-
- /* There should be no other entry edges into the branches, otherwise
- merging the blocks would be an error. */
- if ((then_block && then_block->pred->pred_next)
- || (else_block && else_block->pred->pred_next))
- return false;
-
- /* Linearize 'if (1)'. */
- if (always_true && body_is_empty (else_clause))
- {
- /* If there is no THEN_CLAUSE, remove the conditional. */
- if (body_is_empty (then_clause))
- {
- if (then_block)
- {
- move_outgoing_edges (bb, then_block);
- remove_bb (then_block, REMOVE_NO_STMTS);
- }
- remove_stmt (entry_p, true);
- }
- else
- merge_tree_blocks (bb, bb_for_stmt (then_clause));
-
- return true;
- }
-
- /* Linearize 'if (0)'. */
- if (always_false && body_is_empty (then_clause))
- {
- /* If there is no ELSE_CLAUSE, remove the conditional. */
- if (body_is_empty (else_clause))
- {
- if (else_block)
- {
- move_outgoing_edges (bb, else_block);
- remove_bb (else_block, REMOVE_NO_STMTS);
- }
- remove_stmt (entry_p, true);
- }
- else
- merge_tree_blocks (bb, bb_for_stmt (else_clause));
-
- return true;
- }
-
- return false;
- }
-
-
/*---------------------------------------------------------------------------
Code insertion and replacement
---------------------------------------------------------------------------*/
--- 2527,2532 ----
*************** dump_tree_bb (FILE *outf, const char *pr
*** 2844,2850 ****
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
fprintf (outf, "%s%s%d ", s_indent, prefix, get_lineno (bsi_stmt (si)));
! print_generic_stmt (outf, bsi_stmt (si), TDF_SLIM);
fprintf (outf, "\n");
}
}
--- 2616,2625 ----
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
fprintf (outf, "%s%s%d ", s_indent, prefix, get_lineno (bsi_stmt (si)));
! if (TREE_CODE (bsi_stmt (si)) == COND_EXPR)
! print_generic_stmt (outf, bsi_stmt (si), 0);
! else
! print_generic_stmt (outf, bsi_stmt (si), TDF_SLIM);
fprintf (outf, "\n");
}
}
*************** debug_tree_bb (basic_block bb)
*** 2858,2863 ****
--- 2633,2647 ----
dump_tree_bb (stderr, "", bb, 0);
}
+ /* Dump a basic block N on stderr. */
+
+ basic_block
+ debug_tree_bb_n (int n)
+ {
+ debug_tree_bb (BASIC_BLOCK (n));
+
+ return BASIC_BLOCK (n);
+ }
/* Dump the CFG on stderr.
*************** bsi_insert_before (block_stmt_iterator *
*** 3962,3975 ****
tree insert_container = *tsi_container (inserted_tsi);
switch (TREE_CODE (parent))
{
- case COND_EXPR:
- if (bb_for_stmt (COND_EXPR_THEN (parent)) == curr_bb)
- COND_EXPR_THEN (parent) = insert_container;
- else
- if (bb_for_stmt (COND_EXPR_ELSE (parent)) == curr_bb)
- COND_EXPR_ELSE (parent) = insert_container;
- break;
-
case LOOP_EXPR:
if (bb_for_stmt (LOOP_EXPR_BODY (parent)) == curr_bb)
LOOP_EXPR_BODY (parent) = insert_container;
--- 3746,3751 ----
*************** find_insert_location (basic_block src, b
*** 4238,4243 ****
--- 4014,4020 ----
{
block_stmt_iterator bsi;
tree *ret, stmt;
+ edge e;
*location = EDGE_INSERT_LOCATION_BEFORE;
bsi = bsi_last (src);
*************** find_insert_location (basic_block src, b
*** 4247,4277 ****
switch (TREE_CODE (stmt))
{
case COND_EXPR:
! /* If the ELSE block is non-existant, and this is an edge from the
! COND_EXPR to a block other than the THEN block, then we create
! a new ELSE clause. */
! if (bb_for_stmt (COND_EXPR_ELSE (stmt)) == NULL)
! if (bb_for_stmt (COND_EXPR_THEN (stmt)) != dest)
! {
! ret = &COND_EXPR_ELSE (stmt);
! *location = EDGE_INSERT_LOCATION_NEW_ELSE;
! break;
! }
! /* It must be an edge from the COND_EXPR to either the THEN or
! ELSE block. We will need to insert a new stmt in front of the
! first stmt in the block, *and* update the pointer to the
! THEN or ELSE clause. */
! if (bb_for_stmt (COND_EXPR_THEN (stmt)) == dest)
! {
! ret = &COND_EXPR_THEN (stmt);
! *location = EDGE_INSERT_LOCATION_THEN;
! }
else
! {
! ret = &COND_EXPR_ELSE (stmt);
! *location = EDGE_INSERT_LOCATION_ELSE;
! }
break;
--- 4024,4040 ----
switch (TREE_CODE (stmt))
{
case COND_EXPR:
! e = find_edge (src, new_block);
! if (!e)
! abort ();
! ret = src->end_tree_p;
! if (e->flags & EDGE_TRUE_VALUE)
! *location = EDGE_INSERT_LOCATION_THEN;
! else if (e->flags & EDGE_FALSE_VALUE)
! *location = EDGE_INSERT_LOCATION_ELSE;
else
! abort ();
break;
*************** bsi_insert_on_edge_immediate (edge e, tr
*** 4335,4341 ****
tree_stmt_iterator tsi;
int num_exit, num_entry;
enum find_location_action location;
! tree first, last, inserted_stmt, parent;
bb_ann_t ann;
edge e2;
--- 4098,4104 ----
tree_stmt_iterator tsi;
int num_exit, num_entry;
enum find_location_action location;
! tree first, last, inserted_stmt, parent, label, gto, old_gto;
bb_ann_t ann;
edge e2;
*************** bsi_insert_on_edge_immediate (edge e, tr
*** 4486,4495 ****
switch (location)
{
case EDGE_INSERT_LOCATION_BEFORE:
case EDGE_INSERT_LOCATION_THEN:
case EDGE_INSERT_LOCATION_ELSE:
! case EDGE_INSERT_LOCATION_NEW_ELSE:
! tsi_link_before (&tsi, stmt, TSI_NEW_STMT);
break;
case EDGE_INSERT_LOCATION_AFTER:
--- 4249,4275 ----
switch (location)
{
case EDGE_INSERT_LOCATION_BEFORE:
+ tsi_link_before (&tsi, stmt, TSI_NEW_STMT);
+ break;
+
case EDGE_INSERT_LOCATION_THEN:
case EDGE_INSERT_LOCATION_ELSE:
! label = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
! gto = build_and_jump (&LABEL_EXPR_LABEL (label));
! if (location == EDGE_INSERT_LOCATION_THEN)
! {
! old_gto = COND_EXPR_THEN (tsi_stmt (tsi));
! COND_EXPR_THEN (tsi_stmt (tsi)) = gto;
! }
! else
! {
! old_gto = COND_EXPR_ELSE (tsi_stmt (tsi));
! COND_EXPR_ELSE (tsi_stmt (tsi)) = gto;
! }
! tsi_link_after (&tsi, label, TSI_NEW_STMT);
! append_stmt_to_bb (tsi_container (tsi), new_bb, parent);
! tsi_link_after (&tsi, stmt, TSI_NEW_STMT);
! tsi_link_after (&tsi, old_gto, TSI_SAME_STMT);
break;
case EDGE_INSERT_LOCATION_AFTER:
*************** bsi_insert_on_edge_immediate (edge e, tr
*** 4514,4525 ****
{
case EDGE_INSERT_LOCATION_THEN:
case EDGE_INSERT_LOCATION_ELSE:
! stmt = last_stmt (src);
! if (location == EDGE_INSERT_LOCATION_THEN)
! COND_EXPR_THEN (stmt) = *tsi_container (tsi);
! else
! COND_EXPR_ELSE (stmt) = *tsi_container (tsi);
! /* Fallthru. */
case EDGE_INSERT_LOCATION_BEFORE:
case EDGE_INSERT_LOCATION_AFTER:
--- 4294,4300 ----
{
case EDGE_INSERT_LOCATION_THEN:
case EDGE_INSERT_LOCATION_ELSE:
! break;
case EDGE_INSERT_LOCATION_BEFORE:
case EDGE_INSERT_LOCATION_AFTER:
*************** bsi_insert_on_edge_immediate (edge e, tr
*** 4534,4550 ****
}
break;
- case EDGE_INSERT_LOCATION_NEW_ELSE:
- /* This causes a new stmt chain to be formed, and the ELSE clause needs
- to be set. Set the block number for the empty stmt which might
- follow this stmt as well. */
- stmt = last_stmt (src);
- COND_EXPR_ELSE (stmt) = inserted_stmt;
- tsi_next (&tsi);
- if (tsi_container (tsi))
- append_stmt_to_bb (tsi_container (tsi), new_bb, parent);
- break;
-
case EDGE_INSERT_LOCATION_BSI_AFTER:
break;
}
--- 4309,4314 ----
*************** tree_split_edge (edge edge_in)
*** 5051,5057 ****
static int
tree_verify_flow_info (void)
{
! return 0;
}
--- 4815,4854 ----
static int
tree_verify_flow_info (void)
{
! int err = 0;
! basic_block bb;
! block_stmt_iterator bsi;
! tree stmt;
!
! FOR_EACH_BB (bb)
! {
! bsi = bsi_last (bb);
! if (bsi_end_p (bsi))
! continue;
!
! stmt = bsi_stmt (bsi);
! switch (TREE_CODE (stmt))
! {
! case COND_EXPR:
! if (TREE_CODE (COND_EXPR_THEN (stmt)) != GOTO_EXPR
! || TREE_CODE (COND_EXPR_ELSE (stmt)) != GOTO_EXPR)
! {
! fprintf (stderr, "Structured COND_EXPR at end of bb %d\n",
! bb->index);
! err = 1;
! }
! if (!(bb->flags & BB_CONTROL_EXPR))
! {
! fprintf (stderr, "COND_EXPR in non-BB_CONTROL_EXPR bb %d\n",
! bb->index);
! err = 1;
! }
! break;
! default: ;
! }
! }
!
! return err;
}
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.106
diff -c -3 -p -r1.1.4.106 tree-flow.h
*** tree-flow.h 25 Aug 2003 02:44:23 -0000 1.1.4.106
--- tree-flow.h 26 Aug 2003 18:15:42 -0000
*************** extern tree loop_body (tree);
*** 416,421 ****
--- 416,422 ----
extern void set_loop_body (tree, tree);
extern void dump_tree_bb (FILE *, const char *, basic_block, int);
extern void debug_tree_bb (basic_block);
+ extern basic_block debug_tree_bb_n (int);
extern void dump_tree_cfg (FILE *, int);
extern void debug_tree_cfg (int);
extern void dump_cfg_stats (FILE *);
*************** extern void debug_cfg_stats (void);
*** 423,428 ****
--- 424,430 ----
extern void tree_cfg2dot (FILE *);
extern void insert_bb_before (basic_block, basic_block);
extern void cleanup_tree_cfg (void);
+ extern bool remove_unreachable_blocks (void);
extern void remove_phi_nodes_and_edges_for_unreachable_block (basic_block);
extern tree first_stmt (basic_block);
extern tree last_stmt (basic_block);
Index: tree-simple.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-simple.h,v
retrieving revision 1.1.4.29
diff -c -3 -p -r1.1.4.29 tree-simple.h
*** tree-simple.h 25 Aug 2003 20:52:18 -0000 1.1.4.29
--- tree-simple.h 26 Aug 2003 18:15:42 -0000
*************** void unshare_all_trees (tree);
*** 102,107 ****
--- 102,108 ----
tree voidify_wrapper_expr (tree);
tree gimple_build_eh_filter (tree, tree, tree);
tree maybe_protect_cleanup (tree);
+ tree build_and_jump (tree *);
#endif /* _TREE_SIMPLE_H */
Index: tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dce.c,v
retrieving revision 1.1.2.52
diff -c -3 -p -r1.1.2.52 tree-ssa-dce.c
*** tree-ssa-dce.c 8 Aug 2003 00:27:10 -0000 1.1.2.52
--- tree-ssa-dce.c 26 Aug 2003 18:15:43 -0000
*************** static FILE *dump_file;
*** 69,76 ****
--- 69,78 ----
static int dump_flags;
static varray_type worklist;
+ #if 0
static dominance_info dom_info = NULL;
static dominance_info pdom_info = NULL;
+ #endif
static struct stmt_stats
{
*************** static void process_worklist (void);
*** 94,100 ****
--- 96,104 ----
static void remove_dead_stmts (void);
static void remove_dead_stmt (block_stmt_iterator *, basic_block);
static void remove_dead_phis (basic_block);
+ #if 0
static void remove_conditional (basic_block);
+ #endif
/* Is a tree necessary? */
*************** stmt_useful_p (tree stmt)
*** 259,265 ****
|| (TREE_CODE (stmt) == TRY_CATCH_EXPR)
|| (TREE_CODE (stmt) == TRY_FINALLY_EXPR)
|| (TREE_CODE (stmt) == EH_FILTER_EXPR)
! || (TREE_CODE (stmt) == CATCH_EXPR))
return true;
/* GOTO_EXPR nodes to nonlocal labels need to be kept (This fixes
--- 263,273 ----
|| (TREE_CODE (stmt) == TRY_CATCH_EXPR)
|| (TREE_CODE (stmt) == TRY_FINALLY_EXPR)
|| (TREE_CODE (stmt) == EH_FILTER_EXPR)
! || (TREE_CODE (stmt) == CATCH_EXPR)
! /* Preserve control flow statements for now. */
! || (TREE_CODE (stmt) == GOTO_EXPR)
! || (TREE_CODE (stmt) == COND_EXPR)
! || (TREE_CODE (stmt) == SWITCH_EXPR))
return true;
/* GOTO_EXPR nodes to nonlocal labels need to be kept (This fixes
*************** stmt_useful_p (tree stmt)
*** 305,317 ****
static void
process_worklist (void)
{
basic_block bb;
! tree i, j;
edge e;
bitmap cond_checked, goto_checked;
cond_checked = BITMAP_XMALLOC ();
goto_checked = BITMAP_XMALLOC ();
while (VARRAY_ACTIVE_SIZE (worklist) > 0)
{
--- 313,328 ----
static void
process_worklist (void)
{
+ tree i;
+ #if 0
basic_block bb;
! tree j;
edge e;
bitmap cond_checked, goto_checked;
cond_checked = BITMAP_XMALLOC ();
goto_checked = BITMAP_XMALLOC ();
+ #endif
while (VARRAY_ACTIVE_SIZE (worklist) > 0)
{
*************** process_worklist (void)
*** 326,331 ****
--- 337,343 ----
fprintf (dump_file, "\n");
}
+ #if 0
/* Find any predecessor which 'goto's this block, and mark the goto
as necessary since it is control flow. A block's predecessors only
need to be checked once. */
*************** process_worklist (void)
*** 344,349 ****
--- 356,362 ----
mark_necessary (j);
}
}
+ #endif
if (TREE_CODE (i) == PHI_NODE)
{
*************** process_worklist (void)
*** 358,363 ****
--- 371,377 ----
mark_necessary (SSA_NAME_DEF_STMT (PHI_ARG_DEF (i, k)));
}
+ #if 0
/* Look at all the predecessors, and if this PHI is being fed
from a conditional expression, mark that conditional
as necessary. Copies may be needed on an edge later.
*************** process_worklist (void)
*** 387,392 ****
--- 401,407 ----
}
}
}
+ #endif
}
else
{
*************** process_worklist (void)
*** 423,430 ****
--- 438,447 ----
}
}
}
+ #if 0
BITMAP_XFREE (cond_checked);
BITMAP_XFREE (goto_checked);
+ #endif
}
*************** remove_dead_stmts (void)
*** 438,445 ****
--- 455,464 ----
tree t;
block_stmt_iterator i;
+ #if 0
dom_info = NULL;
pdom_info = NULL;
+ #endif
FOR_EACH_BB_REVERSE (bb)
{
*************** remove_dead_stmts (void)
*** 459,470 ****
--- 478,491 ----
}
}
+ #if 0
/* If we needed the dominance info, free it now. */
if (dom_info != NULL)
free_dominance_info (dom_info);
if (pdom_info != NULL)
free_dominance_info (pdom_info);
+ #endif
}
*************** remove_dead_phis (basic_block bb)
*** 508,514 ****
/* Remove dead statement pointed by iterator I from block BB. */
static void
! remove_dead_stmt (block_stmt_iterator *i, basic_block bb)
{
tree t;
--- 529,535 ----
/* Remove dead statement pointed by iterator I from block BB. */
static void
! remove_dead_stmt (block_stmt_iterator *i, basic_block bb ATTRIBUTE_UNUSED)
{
tree t;
*************** remove_dead_stmt (block_stmt_iterator *i
*** 523,528 ****
--- 544,550 ----
stats.removed++;
+ #if 0
/* If we have determined that a conditional branch statement contributes
nothing to the program, then we not only remove it, but change the
flowgraph so that the block points directly to the immediate
*************** remove_dead_stmt (block_stmt_iterator *i
*** 541,546 ****
--- 563,569 ----
if (parent == NULL_TREE || necessary_p (parent))
remove_conditional (bb);
}
+ #endif
bsi_remove (i);
}
*************** tree_ssa_dce (tree fndecl)
*** 594,599 ****
--- 617,623 ----
}
+ #if 0
/* Remove the conditional statement starting at block BB. */
static void
*************** remove_conditional (basic_block bb)
*** 601,606 ****
--- 625,631 ----
{
basic_block pdom_bb;
edge e;
+ block_stmt_iterator bsi;
/* Calculate dominance info, if it hasn't been computed yet. */
if (pdom_info == NULL)
*************** remove_conditional (basic_block bb)
*** 646,651 ****
}
#endif
/* Add an edge to BB's post dominator. */
! make_edge (bb, pdom_bb, EDGE_FALLTHRU);
}
--- 671,682 ----
}
#endif
+ bsi = bsi_last (bb);
+ if (bsi_stmt (bsi)
+ && TREE_CODE (bsi_stmt (bsi)) == COND_EXPR)
+ bsi_remove (&bsi);
+
/* Add an edge to BB's post dominator. */
! make_edge (bb, pdom_bb, EDGE_FALLTHRU);
}
+ #endif
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.31
diff -c -3 -p -r1.1.2.31 tree-ssa-dom.c
*** tree-ssa-dom.c 25 Aug 2003 22:24:10 -0000 1.1.2.31
--- tree-ssa-dom.c 26 Aug 2003 18:15:45 -0000
*************** struct opt_stats_d
*** 81,89 ****
static struct opt_stats_d opt_stats;
/* Local functions. */
! static void optimize_block (basic_block, tree, int, sbitmap);
! static bool optimize_stmt (block_stmt_iterator, varray_type *);
static tree get_value_for (tree, htab_t);
static void set_value_for (tree, tree, htab_t);
static hashval_t var_value_hash (const void *);
--- 81,93 ----
static struct opt_stats_d opt_stats;
+ /* Redirections scheduled by jump threading. */
+ static varray_type edges_to_redirect;
+ static varray_type redirection_targets;
+
/* Local functions. */
! static bool optimize_block (basic_block, tree, int, sbitmap);
! static bool optimize_stmt (block_stmt_iterator, varray_type *, bool *);
static tree get_value_for (tree, htab_t);
static void set_value_for (tree, tree, htab_t);
static hashval_t var_value_hash (const void *);
*************** static int avail_expr_eq (const void *,
*** 95,100 ****
--- 99,105 ----
static void htab_statistics (FILE *, htab_t);
static void record_cond_is_false (tree, varray_type *, htab_t);
static void record_cond_is_true (tree, varray_type *, htab_t);
+ static void thread_edge (edge, basic_block);
static void find_new_vars_to_rename (tree, sbitmap);
/* Optimize function FNDECL based on the dominator tree. This does
*************** static void find_new_vars_to_rename (tre
*** 108,116 ****
void
tree_ssa_dominator_optimize (tree fndecl, sbitmap vars_to_rename)
{
! bool found_unreachable;
edge e;
- bitmap unreachable_bitmap = BITMAP_XMALLOC ();
timevar_push (TV_TREE_SSA_DOMINATOR_OPTS);
--- 113,120 ----
void
tree_ssa_dominator_optimize (tree fndecl, sbitmap vars_to_rename)
{
! bool cfg_altered;
edge e;
timevar_push (TV_TREE_SSA_DOMINATOR_OPTS);
*************** tree_ssa_dominator_optimize (tree fndecl
*** 141,147 ****
build_dominator_tree (idom);
free_dominance_info (idom);
}
!
/* If we prove certain blocks are unreachable, then we want to
repeat the dominator optimization process as PHI nodes may
have turned into copies which allows better propagation of
--- 145,154 ----
build_dominator_tree (idom);
free_dominance_info (idom);
}
!
! VARRAY_EDGE_INIT (edges_to_redirect, 20, "edges_to_redirect");
! VARRAY_BB_INIT (redirection_targets, 20, "redirection_targets");
!
/* If we prove certain blocks are unreachable, then we want to
repeat the dominator optimization process as PHI nodes may
have turned into copies which allows better propagation of
*************** tree_ssa_dominator_optimize (tree fndecl
*** 149,192 ****
blocks. */
do
{
- int i;
-
/* Optimize the dominator tree. */
! optimize_block (ENTRY_BLOCK_PTR, NULL, 0, vars_to_rename);
/* Wipe the hash tables. */
htab_empty (const_and_copies);
htab_empty (avail_exprs);
! /* We may have made some basic blocks unreachable. We do not
! want to call tree_cleanup_cfg here as it renumbers the blocks
! which makes dom_children invalid.
!
! Instead we simplify identify the unreachable blocks and
! remove their edges and PHI nodes. After rewriting we will
! complete removal of the unreachable blocks. */
! find_unreachable_blocks ();
!
! found_unreachable = false;
!
! for (i = 0; i < n_basic_blocks; i++)
{
! basic_block bb = BASIC_BLOCK (i);
! if (! (bb->flags & BB_REACHABLE))
{
! /* If a previous iteration determined this block was
! unreachable, then just ignore the block. */
! if (bitmap_bit_p (unreachable_bitmap, bb->index))
! continue;
! found_unreachable = true;
! bitmap_set_bit (unreachable_bitmap, bb->index);
! remove_phi_nodes_and_edges_for_unreachable_block (bb);
}
}
}
! while (found_unreachable);
/* Debugging dumps. */
if (dump_file)
--- 156,203 ----
blocks. */
do
{
/* Optimize the dominator tree. */
! cfg_altered = optimize_block (ENTRY_BLOCK_PTR, NULL, 0, vars_to_rename);
/* Wipe the hash tables. */
htab_empty (const_and_copies);
htab_empty (avail_exprs);
! /* If some edges were threaded, perform the redirections, recompute
! dominators and try again. */
! if (VARRAY_ACTIVE_SIZE (edges_to_redirect) > 0)
{
! basic_block tgt;
! while (VARRAY_ACTIVE_SIZE (edges_to_redirect) > 0)
{
! e = VARRAY_TOP_EDGE (edges_to_redirect);
! tgt = VARRAY_TOP_BB (redirection_targets);
! VARRAY_POP (edges_to_redirect);
! VARRAY_POP (redirection_targets);
! thread_edge (e, tgt);
}
+
+ cfg_altered = true;
+ }
+
+ /* We may have made some basic blocks unreachable; remove them. */
+ cfg_altered |= remove_unreachable_blocks ();
+
+ /* If jumps were threaded the dominator tree could have changed
+ significantly, so we must recompute it. If there were unreachable
+ blocks or edges, the dominator tree could have changed, so recomputing
+ it may yield better results, but it is not strictly neccesary (it
+ would be enough to prune removed blocks from dom_children). */
+ if (cfg_altered)
+ {
+ dominance_info idom = calculate_dominance_info (CDI_DOMINATORS);
+ build_dominator_tree (idom);
+ free_dominance_info (idom);
}
}
! while (cfg_altered);
/* Debugging dumps. */
if (dump_file)
*************** tree_ssa_dominator_optimize (tree fndecl
*** 199,209 ****
htab_delete (const_and_copies);
htab_delete (avail_exprs);
! BITMAP_XFREE (unreachable_bitmap);
timevar_pop (TV_TREE_SSA_DOMINATOR_OPTS);
}
/* Perform a depth-first traversal of the dominator tree looking for
redundant expressions and copy/constant propagation opportunities.
--- 210,285 ----
htab_delete (const_and_copies);
htab_delete (avail_exprs);
!
! VARRAY_FREE (edges_to_redirect);
! VARRAY_FREE (redirection_targets);
timevar_pop (TV_TREE_SSA_DOMINATOR_OPTS);
}
+ /* Redirects edge E to basic block DEST. */
+ static void
+ thread_edge (edge e, basic_block dest)
+ {
+ block_stmt_iterator dest_iterator = bsi_start (dest);
+ tree dest_stmt = first_stmt (dest);
+ tree label, goto_stmt, stmt;
+ basic_block bb = e->src;
+ int flags;
+
+ if (e != bb->succ
+ || bb->succ->succ_next)
+ abort ();
+
+ /* We need a label at our final destination. If it does not already exist,
+ create it. */
+ if (!dest_stmt
+ || TREE_CODE (dest_stmt) != LABEL_EXPR)
+ {
+ label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
+ DECL_CONTEXT (label) = current_function_decl;
+ dest_stmt = build1 (LABEL_EXPR, void_type_node, label);
+ bsi_insert_before (&dest_iterator, dest_stmt, BSI_NEW_STMT);
+ }
+ else
+ label = LABEL_EXPR_LABEL (dest_stmt);
+
+ /* If our block does not end with a GOTO, then create one. Otherwise redirect
+ the existing GOTO_EXPR to LABEL. */
+ stmt = last_stmt (bb);
+ if (stmt && TREE_CODE (stmt) == COND_EXPR)
+ {
+ stmt = (e->flags & EDGE_TRUE_VALUE
+ ? COND_EXPR_THEN (stmt)
+ : COND_EXPR_ELSE (stmt));
+ flags = e->flags;
+ if (TREE_CODE (stmt) != GOTO_EXPR)
+ abort ();
+ }
+ else
+ flags = 0;
+
+ if (!stmt || TREE_CODE (stmt) != GOTO_EXPR)
+ {
+ basic_block tmp_bb;
+
+ goto_stmt = build1 (GOTO_EXPR, void_type_node, label);
+ bsi_insert_on_edge_immediate (e, goto_stmt, NULL, &tmp_bb);
+ }
+ else
+ GOTO_DESTINATION (stmt) = label;
+
+ /* 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 %d --> %d to %d\n",
+ e->src->index, e->dest->index, dest->index);
+
+ ssa_remove_edge (e);
+ make_edge (bb, dest, flags);
+ }
+
/* Perform a depth-first traversal of the dominator tree looking for
redundant expressions and copy/constant propagation opportunities.
*************** tree_ssa_dominator_optimize (tree fndecl
*** 229,235 ****
VARS_TO_RENAME is a bitmap representing variables that will need to be
renamed into SSA after dominator optimization. */
! static void
optimize_block (basic_block bb, tree parent_block_last_stmt, int edge_flags,
sbitmap vars_to_rename)
{
--- 305,311 ----
VARS_TO_RENAME is a bitmap representing variables that will need to be
renamed into SSA after dominator optimization. */
! static bool
optimize_block (basic_block bb, tree parent_block_last_stmt, int edge_flags,
sbitmap vars_to_rename)
{
*************** optimize_block (basic_block bb, tree par
*** 242,247 ****
--- 318,324 ----
tree eq_expr_value = NULL_TREE;
edge e;
tree phi;
+ bool cfg_altered = false;
/* Initialize the local stacks.
*************** optimize_block (basic_block bb, tree par
*** 395,401 ****
because that would change the statement's value number. If the
statement had been added to AVAIL_EXPRS, we would not be able to
find it again. */
! if (optimize_stmt (si, &block_avail_exprs))
VARRAY_PUSH_TREE (stmts_to_rescan, bsi_stmt (si));
}
--- 472,478 ----
because that would change the statement's value number. If the
statement had been added to AVAIL_EXPRS, we would not be able to
find it again. */
! if (optimize_stmt (si, &block_avail_exprs, &cfg_altered))
VARRAY_PUSH_TREE (stmts_to_rescan, bsi_stmt (si));
}
*************** optimize_block (basic_block bb, tree par
*** 449,458 ****
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,
! vars_to_rename);
else
! optimize_block (dest, NULL_TREE, 0, vars_to_rename);
}
});
}
--- 526,537 ----
block. The fact that we have exactly one predecessor
also ensures that the predecessor is BB. */
if (!dest->pred->pred_next)
! cfg_altered |= optimize_block (dest, last,
! dest->pred->flags,
! vars_to_rename);
else
! cfg_altered |= optimize_block (dest, NULL_TREE, 0,
! vars_to_rename);
}
});
}
*************** optimize_block (basic_block bb, tree par
*** 465,471 ****
/* The destination block may have become unreachable, in
which case there's no point in optimizing it. */
if (dest->pred)
! optimize_block (dest, NULL_TREE, 0, vars_to_rename);
});
}
}
--- 544,551 ----
/* The destination block may have become unreachable, in
which case there's no point in optimizing it. */
if (dest->pred)
! cfg_altered |= optimize_block (dest, NULL_TREE, 0,
! vars_to_rename);
});
}
}
*************** optimize_block (basic_block bb, tree par
*** 505,559 ****
bypass the conditional at our original destination. */
if (dest && ! phi_nodes (dest))
{
! block_stmt_iterator dest_iterator = bsi_start (dest);
! tree dest_stmt = first_stmt (dest);
! tree label, goto_stmt;
!
! /* We need a label at our final destination. If it does
! not already exist, create it. */
! if (!dest_stmt
! || TREE_CODE (dest_stmt) != LABEL_EXPR)
! {
! label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
! DECL_CONTEXT (label) = current_function_decl;
! dest_stmt = build1 (LABEL_EXPR, void_type_node, label);
! bsi_insert_before (&dest_iterator,
! dest_stmt,
! BSI_NEW_STMT);
! }
! else
! label = LABEL_EXPR_LABEL (dest_stmt);
!
!
! /* If our block does not end with a GOTO, then create
! one. Otherwise redirect the existing GOTO_EXPR to
! LABEL. */
! stmt = last_stmt (bb);
! if (!stmt || TREE_CODE (stmt) != GOTO_EXPR)
! {
! basic_block tmp_bb;
!
! goto_stmt = build1 (GOTO_EXPR, void_type_node, label);
! bsi_insert_on_edge_immediate (bb->succ, goto_stmt,
! NULL, &tmp_bb);
!
! #ifdef ENABLE_CHECKING
! if (tmp_bb)
! abort ();
! #endif
! }
! else
! GOTO_DESTINATION (stmt) = label;
!
! /* 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);
}
}
}
--- 585,592 ----
bypass the conditional at our original destination. */
if (dest && ! phi_nodes (dest))
{
! VARRAY_PUSH_EDGE (edges_to_redirect, bb->succ);
! VARRAY_PUSH_BB (redirection_targets, dest);
}
}
}
*************** optimize_block (basic_block bb, tree par
*** 586,591 ****
--- 619,626 ----
VARRAY_POP (stmts_to_rescan);
find_new_vars_to_rename (stmt, vars_to_rename);
}
+
+ return cfg_altered;
}
/* Dump SSA statistics on FILE. */
*************** record_cond_is_false (tree cond,
*** 694,700 ****
the variable in the LHS in the CONST_AND_COPIES table. */
static bool
! optimize_stmt (block_stmt_iterator si, varray_type *block_avail_exprs_p)
{
size_t i;
stmt_ann_t ann;
--- 729,736 ----
the variable in the LHS in the CONST_AND_COPIES table. */
static bool
! optimize_stmt (block_stmt_iterator si, varray_type *block_avail_exprs_p,
! bool *cfg_altered)
{
size_t i;
stmt_ann_t ann;
*************** optimize_stmt (block_stmt_iterator si, v
*** 1160,1166 ****
{
next = e->succ_next;
if (e != taken_edge)
! ssa_remove_edge (e);
}
}
}
--- 1196,1205 ----
{
next = e->succ_next;
if (e != taken_edge)
! {
! ssa_remove_edge (e);
! *cfg_altered = true;
! }
}
}
}