This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] COND_EXPR lowering
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Cc: dnovillo at redhat dot com, law at redhat dot com
- Date: Sun, 14 Sep 2003 17:05:14 +0200
- Subject: [tree-ssa] COND_EXPR lowering
Hello,
here is the new version of the cond_expr lowering. Wrto the preview
version, lowering of cond_exprs was split out to a separate pass
and cfgcleanup jump threading pass that replaces linearize_* was added.
Bootstrapped/regtested on i686.
Zdenek
* gimple-low.c: New.
* Makefile.in (gimple-low.o): Add.
* tree-cfg.c (make_cond_expr_blocks): Remove.
(thread_jumps, tree_forwarder_block_p): New.
(linearize_control_structures, linearize_cond_expr): Removed.
(merge_tree_blocks): Marked as unused.
(phi_alternatives_equal): Take edges as parameters.
(enum find_location_action): EDGE_INSERT_LOCATION_NEW_ELSE removed.
(make_blocks): Don't handle COND_EXPR as control structure.
(make_switch_expr_blocks): Comment fixes.
(set_parent_stmt): Abort if cond_expr is set as parent.
(find_contained_blocks): Don't handle cond_exprs.
(make_cond_expr_edges): Make edges for a lowered condition.
(cleanup_tree_cfg): Don't call linearize_control_structures,
call jump threading. Call verify_flow_info.
(remove_useless_stmts_and_vars): Remove no longer useful cleanups of
cond_exprs.
(remove_unreachable_block): Don't consider COND_EXPR a control
structure.
(cleanup_control_flow): Don't test for BB_CONTROL_STRUCTURE.
(cleanup_cond_expr_graph): Remove useless cond_exprs.
(find_taken_edge): Handle lowered cond_exprs.
(dump_tree_bb): Dump whole lowered cond_exprs.
(is_ctrl_structure): COND_EXPR removed.
(is_ctrl_stmt): COND_EXPR added.
(bsi_insert_before, find_insert_location, bsi_insert_on_edge_immediate):
Handle inserts wrto lowered cond_exprs.
(tree_verify_flow_info): Added checks for lowness of cond_exprs.
(thread_edge): Moved from tree-ssa-dom.c and altered for usage in
cfgcleanup jump threading.
* tree-flow.h (thread_edge, lower_expr): Declare.
* tree-optimize.c (optimize_function_tree): Call lower_expr.
* tree-ssa-copyprop.c (fixup_var_scope): Handle non-SSA_NAME vars.
* tree-ssa-dce.c: Disable handling of control structures.
* tree-ssa-dom.c (thread_edge): Moved to tree-cfg.c.
(tree_ssa_dominator_optimize): Dumps moved out of
tree_ssa_dominator_optimize.
(optimize_block): Don't test for BB_CONTROL_STRUCTURE.
* tree-ssa.c (insert_copy_on_edge): Adjust scope for emitted sets.
gimple-low.c:
/* Tree lowering pass. Lowers GIMPLE into unstructured form.
Copyright (C) 2003 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 2, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "rtl.h"
#include "errors.h"
#include "varray.h"
#include "tree-simple.h"
#include "tree-inline.h"
#include "diagnostic.h"
#include "langhooks.h"
#include "langhooks-def.h"
#include "tree-flow.h"
#include "timevar.h"
#include "except.h"
#include "hashtab.h"
#include "flags.h"
#include "real.h"
static void lower_stmt (tree_stmt_iterator *);
static void lower_bind_expr (tree_stmt_iterator *);
static void lower_loop_expr (tree_stmt_iterator *);
static void lower_cond_expr (tree_stmt_iterator *);
static void lower_switch_expr (tree_stmt_iterator *);
static void lower_try_finally_expr (tree_stmt_iterator *);
static void lower_try_catch_expr (tree_stmt_iterator *);
static void lower_eh_filter_expr (tree_stmt_iterator *);
static void lower_catch_expr (tree_stmt_iterator *);
/* Lowers the EXPR. Unlike gimplification the statements are not relowered
when they are changed -- if this has to be done, the lowering routine must
do it explicitly. */
void
lower_expr (tree *expr)
{
tree_stmt_iterator tsi;
for (tsi = tsi_start (expr); !tsi_end_p (tsi); tsi_next (&tsi))
lower_stmt (&tsi);
}
/* Lowers statement TSI. */
static void
lower_stmt (tree_stmt_iterator *tsi)
{
switch (TREE_CODE (tsi_stmt (*tsi)))
{
case BIND_EXPR:
lower_bind_expr (tsi);
break;
case COMPOUND_EXPR:
abort ();
case NOP_EXPR:
case ASM_EXPR:
case RETURN_EXPR:
case MODIFY_EXPR:
case CALL_EXPR:
case GOTO_EXPR:
case LABEL_EXPR:
case CASE_LABEL_EXPR:
case VA_ARG_EXPR:
break;
case LOOP_EXPR:
lower_loop_expr (tsi);
break;
case COND_EXPR:
lower_cond_expr (tsi);
break;
case SWITCH_EXPR:
lower_switch_expr (tsi);
break;
case TRY_FINALLY_EXPR:
lower_try_finally_expr (tsi);
break;
case TRY_CATCH_EXPR:
lower_try_catch_expr (tsi);
break;
case EH_FILTER_EXPR:
lower_eh_filter_expr (tsi);
break;
case CATCH_EXPR:
lower_catch_expr (tsi);
break;
default:
print_node_brief (stderr, "", tsi_stmt (*tsi), 0);
abort ();
}
}
/* Lowers a bind_expr TSI. */
static void
lower_bind_expr (tree_stmt_iterator *tsi)
{
lower_expr (&BIND_EXPR_BODY (tsi_stmt (*tsi)));
}
/* Lowers a loop_expr TSI. */
static void
lower_loop_expr (tree_stmt_iterator *tsi)
{
lower_expr (&LOOP_EXPR_BODY (tsi_stmt (*tsi)));
}
/* Lowers a cond_expr TSI. */
static void
lower_cond_expr (tree_stmt_iterator *tsi)
{
tree stmt = tsi_stmt (*tsi);
bool then_is_goto, else_is_goto;
tree then_branch, else_branch, then_label, else_label, end_label;
lower_expr (&COND_EXPR_THEN (stmt));
lower_expr (&COND_EXPR_ELSE (stmt));
/* Find out whether the branches are ordinary local gotos. */
then_branch = COND_EXPR_THEN (stmt);
else_branch = COND_EXPR_ELSE (stmt);
then_is_goto = (TREE_CODE (then_branch) == GOTO_EXPR
&& TREE_CODE (GOTO_DESTINATION (then_branch)) == LABEL_DECL
&& ! NONLOCAL_LABEL (GOTO_DESTINATION (then_branch))
&& (decl_function_context (GOTO_DESTINATION (then_branch))
== current_function_decl));
else_is_goto = (TREE_CODE (else_branch) == GOTO_EXPR
&& TREE_CODE (GOTO_DESTINATION (else_branch)) == LABEL_DECL
&& ! NONLOCAL_LABEL (GOTO_DESTINATION (else_branch))
&& (decl_function_context (GOTO_DESTINATION (else_branch))
== current_function_decl));
if (then_is_goto && else_is_goto)
return;
/* Replace the cond_expr with explicit gotos. */
if (!then_is_goto)
{
then_label = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
COND_EXPR_THEN (stmt) = 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 (stmt) = build_and_jump (&LABEL_EXPR_LABEL (else_label));
}
else
else_label = NULL_TREE;
end_label = NULL_TREE;
if (then_label)
{
tsi_link_after (tsi, then_label, TSI_CHAIN_END);
tsi_link_after (tsi, then_branch, TSI_CHAIN_END);
if (else_label)
{
end_label = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
tsi_link_after (tsi, build_and_jump (&LABEL_EXPR_LABEL (end_label)),
TSI_CHAIN_END);
}
}
if (else_label)
{
tsi_link_after (tsi, else_label, TSI_CHAIN_END);
tsi_link_after (tsi, else_branch, TSI_CHAIN_END);
}
if (end_label)
tsi_link_after (tsi, end_label, TSI_CHAIN_END);
}
/* Lowers a switch_expr TSI. */
static void
lower_switch_expr (tree_stmt_iterator *tsi)
{
lower_expr (&SWITCH_BODY (tsi_stmt (*tsi)));
}
/* Lowers a try_finally_expr TSI. */
static void
lower_try_finally_expr (tree_stmt_iterator *tsi)
{
lower_expr (&TREE_OPERAND (tsi_stmt (*tsi), 0));
lower_expr (&TREE_OPERAND (tsi_stmt (*tsi), 1));
}
/* Lowers a try_catch_expr TSI. */
static void
lower_try_catch_expr (tree_stmt_iterator *tsi)
{
lower_expr (&TREE_OPERAND (tsi_stmt (*tsi), 0));
lower_expr (&TREE_OPERAND (tsi_stmt (*tsi), 1));
}
/* Lowers an eh_filter_expr TSI. */
static void
lower_eh_filter_expr (tree_stmt_iterator *tsi)
{
lower_expr (&EH_FILTER_FAILURE (tsi_stmt (*tsi)));
}
static void
lower_catch_expr (tree_stmt_iterator *tsi)
{
lower_expr (&CATCH_BODY (tsi_stmt (*tsi)));
}
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.112
diff -c -3 -p -r1.903.2.112 Makefile.in
*** Makefile.in 3 Sep 2003 19:10:20 -0000 1.903.2.112
--- Makefile.in 14 Sep 2003 14:41:30 -0000
*************** OBJS-common = \
*** 849,855 ****
tree-alias-type.o gimplify.o tree-nomudflap.o tree-pretty-print.o \
tree-alias-common.o tree-ssa-ccp.o tree-browser.o @ANDER@ tree-ssa-dce.o \
tree-ssa-pre.o tree-ssa-copyprop.o tree-ssa-live.o tree-must-alias.o \
! tree-ssa-dom.o \
alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o \
cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o \
cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o loop-unroll.o \
--- 849,855 ----
tree-alias-type.o gimplify.o tree-nomudflap.o tree-pretty-print.o \
tree-alias-common.o tree-ssa-ccp.o tree-browser.o @ANDER@ tree-ssa-dce.o \
tree-ssa-pre.o tree-ssa-copyprop.o tree-ssa-live.o tree-must-alias.o \
! tree-ssa-dom.o gimple-low.o \
alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o \
cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o \
cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o loop-unroll.o \
*************** c-simplify.o : c-simplify.c $(CONFIG_H)
*** 1566,1571 ****
--- 1566,1575 ----
langhooks.h toplev.h rtl.h $(TREE_FLOW_H) langhooks-def.h \
$(TM_H) coretypes.h $(C_PRETTY_PRINT_H)
gimplify.o : gimplify.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) errors.h \
+ diagnostic.h $(TREE_SIMPLE_H) tree-inline.h varray.h langhooks.h \
+ langhooks-def.h $(TREE_FLOW_H) $(TIMEVAR_H) $(TM_H) coretypes.h except.h \
+ flags.h $(RTL_H)
+ gimple-low.o : gimple-low.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) errors.h \
diagnostic.h $(TREE_SIMPLE_H) tree-inline.h varray.h langhooks.h \
langhooks-def.h $(TREE_FLOW_H) $(TIMEVAR_H) $(TM_H) coretypes.h except.h \
flags.h $(RTL_H)
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.163
diff -c -3 -p -r1.1.4.163 tree-cfg.c
*** tree-cfg.c 13 Sep 2003 16:58:45 -0000 1.1.4.163
--- tree-cfg.c 14 Sep 2003 14:41:36 -0000
*************** static void create_block_annotation (bas
*** 85,91 ****
static void free_blocks_annotations (void);
static void clear_blocks_annotations (void);
static basic_block make_blocks (tree *, tree, 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);
--- 85,90 ----
*************** static int tree_verify_flow_info (void);
*** 119,124 ****
--- 118,125 ----
static basic_block tree_make_forwarder_block (basic_block, int, int, edge, int);
static struct loops *tree_loop_optimizer_init (FILE *);
static void tree_loop_optimizer_finalize (struct loops *, FILE *);
+ static void thread_jumps (void);
+ static bool tree_forwarder_block_p (basic_block);
/* Flowgraph optimization and cleanup. */
*************** static void disconnect_unreachable_case_
*** 141,151 ****
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,151 ----
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 (basic_block, edge, edge);
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 {
*** 166,172 ****
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
--- 166,171 ----
*************** make_blocks (tree *first_p, tree next_bl
*** 433,441 ****
append_stmt_to_bb (stmt_p, bb, parent_stmt);
get_stmt_ann (stmt)->scope = scope;
! 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)
make_catch_expr_blocks (stmt_p, next_block_link, bb, scope);
--- 432,438 ----
append_stmt_to_bb (stmt_p, bb, parent_stmt);
get_stmt_ann (stmt)->scope = scope;
! if (code == SWITCH_EXPR)
make_switch_expr_blocks (stmt_p, next_block_link, bb, scope);
else if (code == CATCH_EXPR)
make_catch_expr_blocks (stmt_p, next_block_link, bb, scope);
*************** could_trap_p (tree expr)
*** 543,583 ****
&& (TREE_CODE (TREE_OPERAND (expr, 0)) == INDIRECT_REF)));
}
- /* 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_STRUCTURE;
-
- /* 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
--- 540,545 ----
*************** make_switch_expr_blocks (tree *switch_e_
*** 715,721 ****
tree switch_e = *switch_e_p;
entry->flags |= BB_CONTROL_STRUCTURE;
! /* Determine NEXT_BLOCK_LINK for statements inside the COND_EXPR body. */
si = tsi_start (switch_e_p);
tsi_next (&si);
--- 677,683 ----
tree switch_e = *switch_e_p;
entry->flags |= BB_CONTROL_STRUCTURE;
! /* Determine NEXT_BLOCK_LINK for statements inside the SWITCH_EXPR body. */
si = tsi_start (switch_e_p);
tsi_next (&si);
*************** set_parent_stmt (tree *stmt_p, tree pare
*** 789,794 ****
--- 751,760 ----
{
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
*** 1057,1068 ****
/* And recurse down into control structures. */
code = TREE_CODE (stmt);
! 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);
}
--- 1023,1029 ----
/* And recurse down into control structures. */
code = TREE_CODE (stmt);
! if (code == CATCH_EXPR)
{
find_contained_blocks (&CATCH_BODY (stmt), my_blocks, last_p);
}
*************** static void
*** 1293,1299 ****
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)
--- 1254,1261 ----
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)
*** 1301,1320 ****
#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);
}
--- 1263,1275 ----
#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)
*** 1421,1428 ****
pdom_info = NULL;
cleanup_control_flow ();
remove_unreachable_blocks ();
- linearize_control_structures ();
if (pdom_info != NULL)
{
free_dominance_info (pdom_info);
--- 1381,1389 ----
pdom_info = NULL;
cleanup_control_flow ();
+ thread_jumps ();
+ cleanup_control_flow ();
remove_unreachable_blocks ();
if (pdom_info != NULL)
{
free_dominance_info (pdom_info);
*************** cleanup_tree_cfg (void)
*** 1440,1445 ****
--- 1401,1409 ----
clear_dom_children (bb);
}
+ #ifdef ENABLE_CHECKING
+ verify_flow_info ();
+ #endif
timevar_pop (TV_TREE_CLEANUP_CFG);
}
*************** remove_useless_stmts_and_vars (tree *fir
*** 1488,1559 ****
/* Dive into control structures. */
stmt_p = tsi_stmt_ptr (i);
code = TREE_CODE (*stmt_p);
! 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);
else if (code == CATCH_EXPR)
--- 1452,1458 ----
/* Dive into control structures. */
stmt_p = tsi_stmt_ptr (i);
code = TREE_CODE (*stmt_p);
! if (code == SWITCH_EXPR)
repeat |= remove_useless_stmts_and_vars (&SWITCH_BODY (*stmt_p),
remove_unused_vars);
else if (code == CATCH_EXPR)
*************** remove_unreachable_block (basic_block bb
*** 1823,1831 ****
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_STRUCTS);
}
--- 1722,1728 ----
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_STRUCTS);
}
*************** bsi_replace (block_stmt_iterator bsi, tr
*** 2064,2071 ****
modify_stmt (bsi_stmt (bsi));
}
-
-
/* Remove statement *STMT_P.
Update all references associated with it. Note that this function will
--- 1961,1966 ----
*************** cleanup_control_flow (void)
*** 2187,2204 ****
basic_block bb;
FOR_EACH_BB (bb)
! if (bb->flags & BB_CONTROL_STRUCTURE)
! {
! tree last = last_stmt (bb);
! if (last)
! {
! 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);
! }
! }
}
--- 2082,2098 ----
basic_block bb;
FOR_EACH_BB (bb)
! {
! tree last = last_stmt (bb);
! if (last)
! {
! 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);
! }
! }
}
*************** cleanup_cond_expr_graph (basic_block bb)
*** 2214,2227 ****
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)
abort ();
#endif
! val = COND_EXPR_COND (cond_expr);
! taken_edge = find_taken_edge (bb, val);
if (taken_edge)
{
edge e, next;
--- 2108,2130 ----
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)
abort ();
#endif
! if (!bb->succ)
! return;
! if (bb->succ->succ_next)
! {
! val = COND_EXPR_COND (cond_expr);
! taken_edge = find_taken_edge (bb, val);
! }
! else
! taken_edge = bb->succ;
!
if (taken_edge)
{
edge e, next;
*************** cleanup_cond_expr_graph (basic_block bb)
*** 2233,2238 ****
--- 2136,2149 ----
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 (basic_block bb, tree va
*** 2329,2335 ****
stmt = last_stmt (bb);
#if defined ENABLE_CHECKING
! if (stmt == NULL_TREE || !is_ctrl_structure (stmt))
abort ();
#endif
--- 2240,2246 ----
stmt = last_stmt (bb);
#if defined ENABLE_CHECKING
! if (stmt == NULL_TREE || !is_ctrl_stmt (stmt))
abort ();
#endif
*************** find_taken_edge_cond_expr (basic_block b
*** 2374,2382 ****
|| ((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));
}
--- 2285,2291 ----
|| ((e->flags & EDGE_FALSE_VALUE) && always_false))
return e;
! return NULL;
}
*************** value_matches_some_label (edge dest_edge
*** 2458,2635 ****
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_STRUCTURE))
! 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. */
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
! 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
---------------------------------------------------------------------------*/
--- 2367,2393 ----
return false;
}
! /* If all the phi nodes in DEST have alternatives for E1 and E2 and
those alterantives are equal in each of the PHI nodes, then return
nonzero, else return zero. */
static int
! phi_alternatives_equal (basic_block dest, edge e1, edge e2)
{
! tree phi, val1, val2;
! for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
{
! val1 = PHI_ARG_DEF (phi, phi_arg_from_edge (phi, e1));
! val2 = PHI_ARG_DEF (phi, phi_arg_from_edge (phi, e2));
! if (!operand_equal_p (val1, val2, false))
! break;
}
! return !phi;
}
/*---------------------------------------------------------------------------
Code insertion and replacement
---------------------------------------------------------------------------*/
*************** dump_tree_bb (FILE *outf, const char *pr
*** 2712,2718 ****
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");
}
}
--- 2470,2479 ----
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");
}
}
*************** is_ctrl_structure (tree t)
*** 3008,3015 ****
abort ();
#endif
! return (TREE_CODE (t) == COND_EXPR
! || TREE_CODE (t) == CATCH_EXPR
|| TREE_CODE (t) == EH_FILTER_EXPR
|| TREE_CODE (t) == TRY_CATCH_EXPR
|| TREE_CODE (t) == TRY_FINALLY_EXPR
--- 2769,2775 ----
abort ();
#endif
! return (TREE_CODE (t) == CATCH_EXPR
|| TREE_CODE (t) == EH_FILTER_EXPR
|| TREE_CODE (t) == TRY_CATCH_EXPR
|| TREE_CODE (t) == TRY_FINALLY_EXPR
*************** bool
*** 3022,3027 ****
--- 2782,2788 ----
is_ctrl_stmt (tree t)
{
return (is_ctrl_structure (t)
+ || TREE_CODE (t) == COND_EXPR
|| TREE_CODE (t) == GOTO_EXPR
|| TREE_CODE (t) == RETURN_EXPR);
}
*************** bsi_insert_before (block_stmt_iterator *
*** 3800,3829 ****
tsi_link_before (&inserted_tsi, t, TSI_NEW_STMT);
add_stmt_to_bb (tsi_container (inserted_tsi), curr_bb, parent);
- if (curr_container == curr_bb->head_tree_p)
- {
- curr_bb->head_tree_p = tsi_container (inserted_tsi);
- /* If the parent block is a COND_EXPR, check if this
- is the block which they point to and update if necessary. */
- if (parent)
- {
- 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;
-
- default:
- break;
- }
- }
- }
-
same_tsi = inserted_tsi;
tsi_next (&same_tsi);
--- 3561,3566 ----
*************** find_insert_location (basic_block src, b
*** 4083,4088 ****
--- 3820,3826 ----
{
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
*** 4092,4122 ****
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;
case TRY_CATCH_EXPR:
--- 3830,3846 ----
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;
case TRY_CATCH_EXPR:
*************** bsi_insert_on_edge_immediate (edge e, tr
*** 4181,4187 ****
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;
--- 3905,3911 ----
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
*** 4325,4334 ****
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:
--- 4049,4075 ----
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
*** 4353,4364 ****
{
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:
--- 4094,4102 ----
{
case EDGE_INSERT_LOCATION_THEN:
case EDGE_INSERT_LOCATION_ELSE:
! tsi_next (&tsi);
! append_stmt_to_bb (tsi_container (tsi), new_bb, parent);
! break;
case EDGE_INSERT_LOCATION_BEFORE:
case EDGE_INSERT_LOCATION_AFTER:
*************** bsi_insert_on_edge_immediate (edge e, tr
*** 4373,4389 ****
}
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;
}
--- 4111,4116 ----
*************** tree_split_edge (edge edge_in)
*** 4889,4895 ****
static int
tree_verify_flow_info (void)
{
! return 0;
}
--- 4616,4655 ----
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_STRUCTURE)
! {
! fprintf (stderr, "COND_EXPR in BB_CONTROL_STRUCTURE bb %d\n",
! bb->index);
! err = 1;
! }
! break;
! default: ;
! }
! }
!
! return err;
}
*************** assign_vars_to_scope (tree scope)
*** 5025,5028 ****
--- 4785,4992 ----
for (var = BIND_EXPR_VARS (scope); var; var = TREE_CHAIN (var))
get_var_ann (var)->scope = scope;
+ }
+
+ /* Checks whether the basic block BB does nothing except for jump. */
+ static bool
+ tree_forwarder_block_p (basic_block bb)
+ {
+ block_stmt_iterator bsi;
+
+ if (!bb->succ
+ || bb->succ->succ_next
+ || (bb->succ->flags & EDGE_ABNORMAL)
+ || bb == ENTRY_BLOCK_PTR)
+ return false;
+
+ if (phi_nodes (bb))
+ return false;
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ switch (TREE_CODE (bsi_stmt (bsi)))
+ {
+ case LABEL_EXPR:
+ case GOTO_EXPR:
+ break;
+
+ default:
+ return false;
+ }
+
+ return true;
+ }
+
+ /* Threads jumps over empty statements. Later we may add threading over
+ obviously equivalent conditions (this of course is already handled by
+ dominator optimization, but it might be useful to clean up things created
+ later). */
+ static void
+ thread_jumps ()
+ {
+ edge e, next, last, old;
+ basic_block bb, dest, slow;
+ int set_slow;
+ tree phi, stmt;
+ int arg;
+
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ {
+ /* Don't waste time on unreachable blocks. */
+ if (!bb->pred)
+ continue;
+
+ /* Nor on forwarders. */
+ if (tree_forwarder_block_p (bb))
+ continue;
+
+ /* Due to limitations of ir, it is difficult to redirect edge except
+ in some simple cases. Given that ir is slowly getting more sane,
+ don't invest too much energy into monsters of bsi_insert_on_edge
+ type. */
+ stmt = last_stmt (bb);
+ if (stmt
+ && stmt_ends_bb_p (stmt)
+ && TREE_CODE (stmt) != GOTO_EXPR
+ && TREE_CODE (stmt) != COND_EXPR)
+ continue;
+
+ for (e = bb->succ; e; e = next)
+ {
+ next = e->succ_next;
+
+ if ((e->flags & EDGE_ABNORMAL)
+ || e->dest == EXIT_BLOCK_PTR
+ || !tree_forwarder_block_p (e->dest)
+ || e->dest->succ->dest == EXIT_BLOCK_PTR)
+ continue;
+
+ slow = e->dest;
+ set_slow = 0;
+
+ last = e->dest->succ;
+ for (dest = e->dest->succ->dest;
+ tree_forwarder_block_p (dest);
+ last = dest->succ,
+ dest = dest->succ->dest,
+ set_slow ^= 1)
+ {
+ /* Infinite loop detected. */
+ if (slow == dest)
+ break;
+ if (set_slow)
+ slow = slow->succ->dest;
+
+ if (dest->succ->dest == EXIT_BLOCK_PTR)
+ break;
+ }
+
+ if (dest == e->dest)
+ continue;
+
+ old = find_edge (bb, dest);
+ if (old)
+ {
+ /* If there already is an edge, check whether the values
+ in phi nodes differ. */
+ if (!phi_alternatives_equal (dest, last, old))
+ {
+ /* The previous block is forwarder, so there are no
+ phi nodes to update. */
+ dest = last->src;
+
+ if (dest == e->dest)
+ continue;
+ old = find_edge (bb, dest);
+ }
+ }
+
+ /* If the target starts with case label, it would be difficult to
+ do the redirection. Since we are going to lower switch_exprs
+ soon, I don't want to spend too much time on it. */
+ if (first_stmt (dest)
+ && TREE_CODE (first_stmt (dest)) == CASE_LABEL_EXPR)
+ continue;
+
+ /* Perform the redirection. */
+ e = thread_edge (e, dest);
+ if (!old)
+ {
+ /* Update phi nodes. */
+ for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
+ {
+ arg = phi_arg_from_edge (phi, last);
+ if (arg < 0)
+ abort ();
+ add_phi_arg (&phi, PHI_ARG_DEF (phi, arg), e);
+ }
+ }
+ }
+ }
+ }
+
+ /* Redirects edge E to basic block DEST. Returns the new edge to DEST. */
+ edge
+ 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, new_bb;
+ int flags;
+
+ /* 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)
+ {
+ if (dest_stmt && TREE_CODE (dest_stmt) == CASE_LABEL_EXPR)
+ abort ();
+
+ 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_SAME_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)
+ {
+ goto_stmt = build1 (GOTO_EXPR, void_type_node, label);
+ bsi_insert_on_edge_immediate (e, goto_stmt, NULL, &new_bb);
+ }
+ else
+ {
+ GOTO_DESTINATION (stmt) = label;
+ new_bb = NULL;
+ }
+
+ /* Update/insert PHI nodes as necessary. */
+
+ /* Now update the edges in the CFG. */
+ if (new_bb)
+ {
+ ssa_remove_edge (new_bb->succ);
+ return make_edge (new_bb, dest, 0);
+ }
+ else
+ {
+ ssa_remove_edge (e);
+ return make_edge (bb, dest, flags);
+ }
}
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.114
diff -c -3 -p -r1.1.4.114 tree-flow.h
*** tree-flow.h 13 Sep 2003 20:21:26 -0000 1.1.4.114
--- tree-flow.h 14 Sep 2003 14:41:36 -0000
*************** extern basic_block tree_split_edge (edge
*** 435,440 ****
--- 435,441 ----
extern void bsi_move_before (block_stmt_iterator, block_stmt_iterator);
extern void bsi_move_after (block_stmt_iterator, block_stmt_iterator);
extern void bsi_move_to_bb_end (block_stmt_iterator, basic_block);
+ extern edge thread_edge (edge, basic_block);
/* In tree-dfa.c */
void find_referenced_vars (tree);
*************** static inline bool may_propagate_copy (t
*** 523,528 ****
--- 524,532 ----
/* In tree-must-alias.c */
void tree_compute_must_alias (tree);
+
+ /* In gimple-low.c */
+ void lower_expr (tree *);
#include "tree-flow-inline.h"
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 1.1.4.46
diff -c -3 -p -r1.1.4.46 tree-optimize.c
*** tree-optimize.c 12 Sep 2003 16:15:52 -0000 1.1.4.46
--- tree-optimize.c 14 Sep 2003 14:41:37 -0000
*************** optimize_function_tree (tree fndecl)
*** 60,65 ****
--- 60,66 ----
if (errorcount || sorrycount)
return;
+ lower_expr (&DECL_SAVED_TREE (fndecl));
fnbody = DECL_SAVED_TREE (fndecl);
/* Build the flowgraph. */
Index: tree-ssa-copyprop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-copyprop.c,v
retrieving revision 1.1.2.13
diff -c -3 -p -r1.1.2.13 tree-ssa-copyprop.c
*** tree-ssa-copyprop.c 6 Sep 2003 13:39:24 -0000 1.1.2.13
--- tree-ssa-copyprop.c 14 Sep 2003 14:41:37 -0000
*************** propagate_copy (tree *op_p, tree var, tr
*** 236,242 ****
void
fixup_var_scope (tree var, tree scope)
{
! tree old_scope = var_ann (SSA_NAME_VAR (var))->scope;
/* If there is no old_scope, it is a newly created temporary, i.e. it is
in the topmost bind_expr and we have nothing to do. */
--- 236,246 ----
void
fixup_var_scope (tree var, tree scope)
{
! tree old_scope;
!
! if (TREE_CODE (var) == SSA_NAME)
! var = SSA_NAME_VAR (var);
! old_scope = var_ann (var)->scope;
/* If there is no old_scope, it is a newly created temporary, i.e. it is
in the topmost bind_expr and we have nothing to do. */
*************** fixup_var_scope (tree var, tree scope)
*** 251,257 ****
scope = stmt_ann (scope)->scope;
}
if (scope != old_scope)
! move_var_to_scope (SSA_NAME_VAR (var), old_scope,
DECL_SAVED_TREE (current_function_decl));
}
}
--- 255,261 ----
scope = stmt_ann (scope)->scope;
}
if (scope != old_scope)
! move_var_to_scope (var, old_scope,
DECL_SAVED_TREE (current_function_decl));
}
}
Index: tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dce.c,v
retrieving revision 1.1.2.53
diff -c -3 -p -r1.1.2.53 tree-ssa-dce.c
*** tree-ssa-dce.c 6 Sep 2003 13:39:24 -0000 1.1.2.53
--- tree-ssa-dce.c 14 Sep 2003 14:41:38 -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.36
diff -c -3 -p -r1.1.2.36 tree-ssa-dom.c
*** tree-ssa-dom.c 13 Sep 2003 20:21:26 -0000 1.1.2.36
--- tree-ssa-dom.c 14 Sep 2003 14:41:39 -0000
*************** static int avail_expr_eq (const void *,
*** 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 mark_new_vars_to_rename (tree, sbitmap);
/* Optimize function FNDECL based on the dominator tree. This does
--- 99,104 ----
*************** tree_ssa_dominator_optimize (tree fndecl
*** 172,183 ****
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;
--- 171,194 ----
while (VARRAY_ACTIVE_SIZE (edges_to_redirect) > 0)
{
+ basic_block src;
+
e = VARRAY_TOP_EDGE (edges_to_redirect);
tgt = VARRAY_TOP_BB (redirection_targets);
VARRAY_POP (edges_to_redirect);
VARRAY_POP (redirection_targets);
! if (dump_file && (dump_flags & TDF_DETAILS))
! fprintf (dump_file, " Threaded jump %d --> %d to %d\n",
! e->src->index, e->dest->index, tgt->index);
!
! src = e->src;
! e = thread_edge (e, tgt);
!
! if ((dump_file && (dump_flags & TDF_DETAILS))
! && e->src != src)
! fprintf (dump_file, " basic block %d created\n",
! e->src->index);
}
cfg_altered = true;
*************** tree_ssa_dominator_optimize (tree fndecl
*** 217,286 ****
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, new_bb;
- int flags = e->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) != GOTO_EXPR)
- {
- goto_stmt = build1 (GOTO_EXPR, void_type_node, label);
- bsi_insert_on_edge_immediate (e, goto_stmt, NULL, &new_bb);
- }
- else
- {
- GOTO_DESTINATION (stmt) = label;
- new_bb = NULL;
- }
-
- /* 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);
- if (new_bb)
- fprintf (dump_file, " basic block %d created\n", new_bb->index);
- }
-
- if (new_bb)
- {
- ssa_remove_edge (new_bb->succ);
- make_edge (new_bb, dest, 0);
- }
- else
- {
- 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.
--- 228,233 ----
*************** optimize_block (basic_block bb, tree par
*** 513,555 ****
children = dom_children (bb);
if (children)
{
! if (bb->flags & BB_CONTROL_STRUCTURE)
! {
! tree last = last_stmt (bb);
! EXECUTE_IF_SET_IN_BITMAP (children, 0, i,
! {
! basic_block dest = BASIC_BLOCK (i);
! /* The destination block may have become unreachable, in
! which case there's no point in optimizing it. */
! if (dest->pred)
! {
! /* Ensure that we only take the condition into account
! if there is no other way how to reach the target basic
! 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, cfg_altered);
! else
! optimize_block (dest, NULL_TREE, 0, vars_to_rename,
! cfg_altered);
! }
! });
! }
! else
{
! EXECUTE_IF_SET_IN_BITMAP (children, 0, i,
! {
! basic_block dest = BASIC_BLOCK (i);
! /* 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,
! cfg_altered);
! });
! }
}
/* If we have a single successor, then we may be able to thread
--- 460,489 ----
children = dom_children (bb);
if (children)
{
! tree last = last_stmt (bb);
! int has_control_expr = last && (TREE_CODE (last) == COND_EXPR
! || TREE_CODE (last) == SWITCH_EXPR);
! EXECUTE_IF_SET_IN_BITMAP (children, 0, i,
{
! basic_block dest = BASIC_BLOCK (i);
! /* The destination block may have become unreachable, in
! which case there's no point in optimizing it. */
! if (dest->pred)
! {
! /* Ensure that we only take the condition into account
! if there is no other way how to reach the target basic
! block. The fact that we have exactly one predecessor
! also ensures that the predecessor is BB. */
! if (has_control_expr
! && !dest->pred->pred_next)
! optimize_block (dest, last, dest->pred->flags,
! vars_to_rename, cfg_altered);
! else
! optimize_block (dest, NULL_TREE, 0, vars_to_rename, cfg_altered);
! }
! });
}
/* If we have a single successor, then we may be able to thread
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.125
diff -c -3 -p -r1.1.4.125 tree-ssa.c
*** tree-ssa.c 13 Sep 2003 02:08:59 -0000 1.1.4.125
--- tree-ssa.c 14 Sep 2003 14:41:42 -0000
*************** create_temp (tree t)
*** 895,901 ****
static void
insert_copy_on_edge (edge e, tree dest, tree src)
{
! tree copy;
copy = build (MODIFY_EXPR, TREE_TYPE (dest), dest, src);
set_is_used (dest);
--- 895,901 ----
static void
insert_copy_on_edge (edge e, tree dest, tree src)
{
! tree copy, scope, s1, s2;
copy = build (MODIFY_EXPR, TREE_TYPE (dest), dest, src);
set_is_used (dest);
*************** insert_copy_on_edge (edge e, tree dest,
*** 910,915 ****
--- 910,932 ----
print_generic_expr (dump_file, copy, dump_flags);
fprintf (dump_file, "\n");
}
+ /* If we are inserting a variable on boundaries of scopes, rather reset
+ the scope completely, since we don't know for sure where it should
+ be placed. */
+ s1 = last_stmt (e->src);
+ s2 = last_stmt (e->dest);
+ if (!s1
+ || !s2
+ || !stmt_ann (s1)->scope
+ || !stmt_ann (s2)->scope
+ || stmt_ann (s1)->scope != stmt_ann (s2)->scope)
+ scope = NULL_TREE;
+ else
+ scope = stmt_ann (s1)->scope;
+
+ if (TREE_CODE (src) == VAR_DECL)
+ fixup_var_scope (src, scope);
+ fixup_var_scope (dest, scope);
bsi_insert_on_edge (e, copy);
}