This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[ast-optimizer-branch]: CFG improvements [patch]
- To: gcc-patches at gcc dot gnu dot org
- Subject: [ast-optimizer-branch]: CFG improvements [patch]
- From: Diego Novillo <dnovillo at redhat dot com>
- Date: Fri, 10 Aug 2001 21:21:19 -0400
- Cc: Nathan Sidwell <nathan at codesourcery dot com>
- Organization: Red Hat Canada
This patch fixes some bugs and adds new features to the tree
CFGs. This is in preparation for a new lowering phase to add
global value numbering for trees.
- Edges for case label blocks inside compound statements are now
handled properly.
- Added a real reachability analysis pass based on the existing
framework in flow.c
- Reduced the size of the CFG by not building blocks for
COMPOUND_STMT trees. Also folded some nodes in loop
structures.
- Added new utility functions to reduce code duplication.
- Removed some unused annotations from trees and basic blocks.
Bootstrapped and regression tested on i686.
Nathan, the first part of this patch is the addition of field
'reachable' to basic_block. It still hasn't been reviewed for
the trunk, but it's necessary for the reachability analysis. I
can always back it out or update it later on.
Diego.
2001-08-10 Diego Novillo <dnovillo@redhat.com>
* basic-block.h (basic_block): Add new field 'reachable'.
(expunge_block): Declare.
* flow.c (ENTRY_BLOCK_PTR): Initialize field 'reachable'.
(EXIT_BLOCK_PTR): Ditto.
(expunge_block): Remove static declaration.
(cleanup_cfg): Clear bb->aux on every basic block.
(find_unreachable_blocks): Use field 'reachable' when computing
reachability.
(delete_unreachable_blocks): Use field 'reachable'.
* tree-cfg.c: Rename all instance of 'node' with 'block.
(get_successor_block): Rename to successor_block.
(make_compound_stmt_edges): Remove.
(make_switch_stmt_edges): Remove.
(delete_unreachable_blocks): New.
(delete_block): New.
(make_blocks): Add new argument 'compound_stmt'. Do not include
COMPOUND_STMT trees in the flowgraph.
(make_for_stmt_blocks): Include FOR_INIT_STMT in the entry block of
the loop.
If FOR_COND does not exist, create a tree holding the constant 1.
Add new argument 'compound_stmt'.
(make_while_stmt_blocks): Include WHILE_COND in the entry block of
the loop.
Add new argument 'compound_stmt'.
(make_do_stmt_blocks): Add new argument 'compound_stmt'.
(make_if_stmt_blocks): Add new argument 'compound_stmt'.
Include IF_COND in the IF header block.
(make_switch_stmt_blocks): Add new argument 'compound_stmt'.
Include SWITCH_COND in the SWITCH header block.
(create_maximal_bb): Remove argument 'is_loop_header'.
Add new argument 'compound_stmt'.
Update all callers.
Return the newly created basic block instead of its last statement.
Update comments.
Do not store control flow altering statements in bb->exit_stmt.
Only add executable statements to the block.
Annotate with 'compound_stmt' each tree added to the block.
(create_bb): Do not update annotation 'is_loop_header'.
(make_edges): Remove naive reachability analysis.
When a label node is found, add an edge from the immediately
enclosing switch statement.
Call delete_unreachable_blocks() after adding all the edges.
(make_ctrl_stmt_edges): Do not consider COMPOUND_STMT trees.
Do nothing for SWITCH_STMT trees.
(make_exit_edges): Use bb->end_tree instead of BB_EXIT_STMT.
(make_for_stmt_edges): Remove code that added edges for the block
holding FOR_INIT_STMT.
Update comments.
Do not consider the case where FOR_COND is NULL.
Call first_exec_stmt() to determine if FOR_BODY is empty.
Only create an edge from expr_bb to cond_bb if FOR_EXPR is
non-null.
(make_while_stmt_edges): Remove code that added edges for the block
holding WHILE_COND.
Update comments.
Call first_exec_stmt() to determine if WHILE_BODY is empty.
(make_do_stmt_edges): Call first_exec_stmt() to determine if
DO_BODY is empty.
(make_if_stmt_edges): Remove code that added edges for the block
holding IF_COND.
Call first_exec_stmt() to determine if THEN_CLAUSE or ELSE_CLAUSE
are empty.
(make_switch_stmt_edges): Remove.
(make_goto_stmt_edges): Use bb->end_tree instead of BB_EXIT_STMT.
(make_break_stmt_edges): Use bb->end_tree instead of BB_EXIT_STMT.
Call switch_parent() and loop_parent() to determine if the
statement is inside an appropriate control structure.
(make_continue_stmt_edges): Use bb->end_tree instead of
BB_EXIT_STMT.
(make_return_stmt_edges): Ditto.
(get_successor_block): Rename to successor_block.
Call first_exec_stmt() to find the first executable statement in
TREE_CHAIN.
(is_ctrl_stmt): Do not consider COMPOUND_STMT trees.
(stmt_starts_bb_p): Ditto.
(stmt_ends_bb_p): Reformat comments.
(delete_cfg): Reformat comments.
(find_loop_parent): Rename to loop_parent.
(get_condition_block): Rename to condition_block.
Update to use new index numbers for control structure header
blocks.
(switch_parent): New.
(first_exec_stmt): New.
(is_exec_stmt): New.
(tree_cfg2dot): Reformat comments.
* tree-dfa.c (find_refs): Remove.
(find_refs_in_stmt): New
(find_refs_in_stmt_expr): New.
(tree_find_varrefs): Look for variables doing a CFG traversal
instead of the trees. Remove both arguments.
(find_refs_in_expr): Add new argument 'bb'.
Update all recursive calls.
(create_varref): Abort if the basic block 'bb' is NULL.
(add_ref_to_sym): Reformat comments.
(add_ref_symbol): Ditto.
(delete_varref_list): Ditto.
* tree-flow.h (struct tree_ann_def): Add 'compound_stmt'.
(TREE_COMPOUND_STMT): New macro.
(struct basic_block_ann_def): Remove 'exit_stmt' and
'is_loop_header'.
(BB_EXIT_STMT): Remove.
(BB_IS_LOOP_HEADER): Remove.
* tree-opt.c (optimize_tree): Call tree_find_varrefs() with no
arguments.
Only build DFA and SSA information if n_basic_blocks is greater
than zero.
* tree-ssa.c: Rename all instances of 'node' with 'block'.
(tree_build_ssa): Reformat comments.
(insert_phi_terms): Ditto.
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.102
diff -d -p -d -c -p -r1.102 basic-block.h
*** basic-block.h 2001/07/16 20:54:42 1.102
--- basic-block.h 2001/08/11 00:01:02
*************** typedef struct basic_block_def {
*** 217,222 ****
--- 217,226 ----
/* Expected frequency. Normalized to be in range 0 to BB_FREQ_MAX. */
int frequency;
+
+ /* Reachability flag. Set to non-zero if this block is reachable from
+ the flowgraph's entry node. */
+ int reachable;
} *basic_block;
#define BB_FREQ_MAX 10000
*************** extern void debug_regset PARAMS ((regse
*** 597,602 ****
--- 601,607 ----
extern void allocate_reg_life_data PARAMS ((void));
extern void allocate_bb_life_data PARAMS ((void));
extern void find_unreachable_blocks PARAMS ((void));
+ extern void expunge_block PARAMS ((basic_block));
/* This function is always defined so it can be called from the
debugger, and it is declared extern so we don't get warnings about
Index: flow.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flow.c,v
retrieving revision 1.431
diff -d -p -d -c -p -r1.431 flow.c
*** flow.c 2001/07/21 03:05:09 1.431
--- flow.c 2001/08/11 00:01:03
*************** struct basic_block_def entry_exit_blocks
*** 208,214 ****
ENTRY_BLOCK, /* index */
0, /* loop_depth */
0, /* count */
! 0 /* frequency */
},
{
NULL, /* head */
--- 208,215 ----
ENTRY_BLOCK, /* index */
0, /* loop_depth */
0, /* count */
! 0, /* frequency */
! 0 /* reachability */
},
{
NULL, /* head */
*************** struct basic_block_def entry_exit_blocks
*** 225,231 ****
EXIT_BLOCK, /* index */
0, /* loop_depth */
0, /* count */
! 0 /* frequency */
}
};
--- 226,233 ----
EXIT_BLOCK, /* index */
0, /* loop_depth */
0, /* count */
! 0, /* frequency */
! 0 /* reachability */
}
};
*************** static void commit_one_edge_insertion PA
*** 383,389 ****
static void delete_unreachable_blocks PARAMS ((void));
static int can_delete_note_p PARAMS ((rtx));
- static void expunge_block PARAMS ((basic_block));
static int can_delete_label_p PARAMS ((rtx));
static int tail_recursion_label_p PARAMS ((rtx));
static int merge_blocks_move_predecessor_nojumps PARAMS ((basic_block,
--- 385,390 ----
*************** void
*** 1005,1010 ****
--- 1006,1013 ----
cleanup_cfg (mode)
int mode;
{
+ int i;
+
timevar_push (TV_CLEANUP_CFG);
delete_unreachable_blocks ();
if (try_optimize_cfg (mode))
*************** cleanup_cfg (mode)
*** 1015,1020 ****
--- 1018,1027 ----
free_EXPR_LIST_list (&label_value_list);
free_EXPR_LIST_list (&tail_recursion_label_list);
timevar_pop (TV_CLEANUP_CFG);
+
+ /* Clear bb->aux on all basic blocks. */
+ for (i = 0; i < n_basic_blocks; ++i)
+ BASIC_BLOCK (i)->aux = NULL;
}
/* Create a new basic block consisting of the instructions between
*************** flow_call_edges_add (blocks)
*** 2397,2404 ****
return blocks_split;
}
! /* Find unreachable blocks. An unreachable block will have NULL in
! block->aux, a non-NULL value indicates the block is reachable. */
void
find_unreachable_blocks ()
--- 2404,2411 ----
return blocks_split;
}
! /* Find unreachable blocks. An unreachable block will have 0 in
! block->reachable, a non-zero value indicates the block is reachable. */
void
find_unreachable_blocks ()
*************** find_unreachable_blocks ()
*** 2410,2419 ****
n = n_basic_blocks;
tos = worklist = (basic_block *) xmalloc (sizeof (basic_block) * n);
! /* Use basic_block->aux as a marker. Clear them all. */
for (i = 0; i < n; ++i)
! BASIC_BLOCK (i)->aux = NULL;
/* Add our starting points to the worklist. Almost always there will
be only one. It isn't inconcievable that we might one day directly
--- 2417,2426 ----
n = n_basic_blocks;
tos = worklist = (basic_block *) xmalloc (sizeof (basic_block) * n);
! /* Clear all the reachability flags. */
for (i = 0; i < n; ++i)
! BASIC_BLOCK (i)->reachable = 0;
/* Add our starting points to the worklist. Almost always there will
be only one. It isn't inconcievable that we might one day directly
*************** find_unreachable_blocks ()
*** 2424,2430 ****
*tos++ = e->dest;
/* Mark the block with a handy non-null value. */
! e->dest->aux = e;
}
/* Iterate: find everything reachable from what we've already seen. */
--- 2431,2437 ----
*tos++ = e->dest;
/* Mark the block with a handy non-null value. */
! e->dest->reachable = 1;
}
/* Iterate: find everything reachable from what we've already seen. */
*************** find_unreachable_blocks ()
*** 2434,2443 ****
basic_block b = *--tos;
for (e = b->succ; e; e = e->succ_next)
! if (!e->dest->aux)
{
*tos++ = e->dest;
! e->dest->aux = e;
}
}
--- 2441,2450 ----
basic_block b = *--tos;
for (e = b->succ; e; e = e->succ_next)
! if (!e->dest->reachable)
{
*tos++ = e->dest;
! e->dest->reachable = 1;
}
}
*************** delete_unreachable_blocks ()
*** 2460,2469 ****
{
basic_block b = BASIC_BLOCK (i);
! if (b->aux != NULL)
! /* This block was found. Tidy up the mark. */
! b->aux = NULL;
! else
flow_delete_block (b);
}
--- 2467,2473 ----
{
basic_block b = BASIC_BLOCK (i);
! if (!b->reachable)
flow_delete_block (b);
}
*************** flow_delete_block (b)
*** 2599,2605 ****
/* Remove block B from the basic block array and compact behind it. */
! static void
expunge_block (b)
basic_block b;
{
--- 2603,2609 ----
/* Remove block B from the basic block array and compact behind it. */
! void
expunge_block (b)
basic_block b;
{
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.2.2
diff -d -p -d -c -p -r1.1.2.2 tree-cfg.c
*** tree-cfg.c 2001/08/01 05:36:58 1.1.2.2
--- tree-cfg.c 2001/08/11 00:01:05
*************** static const int initial_cfg_capacity =
*** 81,114 ****
/* {{{ Local function declarations. */
/* Basic blocks and flowgraphs. */
! static void make_nodes PARAMS ((tree, basic_block));
! static void make_compound_stmt_nodes PARAMS ((tree, basic_block));
! static void make_for_stmt_nodes PARAMS ((tree, basic_block));
! static void make_if_stmt_nodes PARAMS ((tree, basic_block));
! static void make_while_stmt_nodes PARAMS ((tree, basic_block));
! static void make_switch_stmt_nodes PARAMS ((tree, basic_block));
! static void make_do_stmt_nodes PARAMS ((tree, basic_block));
! static basic_block create_bb PARAMS ((tree, tree, basic_block, int));
! static tree create_maximal_bb PARAMS ((tree, basic_block, int));
static void map_stmt_to_bb PARAMS ((tree, basic_block));
/* Edges. */
static void make_edges PARAMS ((void));
static void make_ctrl_stmt_edges PARAMS ((sbitmap *, basic_block));
static void make_exit_edges PARAMS ((sbitmap *, basic_block));
- static void make_compound_stmt_edges PARAMS ((sbitmap *, basic_block));
static void make_for_stmt_edges PARAMS ((sbitmap *, basic_block));
static void make_while_stmt_edges PARAMS ((sbitmap *, basic_block));
static void make_do_stmt_edges PARAMS ((sbitmap *, basic_block));
static void make_if_stmt_edges PARAMS ((sbitmap *, basic_block));
- static void make_switch_stmt_edges PARAMS ((sbitmap *, basic_block));
static void make_goto_stmt_edges PARAMS ((sbitmap *, basic_block));
static void make_break_stmt_edges PARAMS ((sbitmap *, basic_block));
static void make_continue_stmt_edges PARAMS ((sbitmap *, basic_block));
static void make_return_stmt_edges PARAMS ((sbitmap *, basic_block));
/* Various helpers. */
! static basic_block get_successor_block PARAMS ((basic_block));
/* }}} */
--- 81,113 ----
/* {{{ Local function declarations. */
/* Basic blocks and flowgraphs. */
! static void make_blocks PARAMS ((tree, basic_block, tree));
! static void make_for_stmt_blocks PARAMS ((tree, basic_block, tree));
! static void make_if_stmt_blocks PARAMS ((tree, basic_block, tree));
! static void make_while_stmt_blocks PARAMS ((tree, basic_block, tree));
! static void make_switch_stmt_blocks PARAMS ((tree, basic_block, tree));
! static void make_do_stmt_blocks PARAMS ((tree, basic_block, tree));
! static basic_block create_bb PARAMS ((tree, tree, basic_block));
! static basic_block create_maximal_bb PARAMS ((tree, basic_block, tree));
static void map_stmt_to_bb PARAMS ((tree, basic_block));
+ static void delete_unreachable_blocks PARAMS ((void));
+ static void delete_block PARAMS ((basic_block));
/* Edges. */
static void make_edges PARAMS ((void));
static void make_ctrl_stmt_edges PARAMS ((sbitmap *, basic_block));
static void make_exit_edges PARAMS ((sbitmap *, basic_block));
static void make_for_stmt_edges PARAMS ((sbitmap *, basic_block));
static void make_while_stmt_edges PARAMS ((sbitmap *, basic_block));
static void make_do_stmt_edges PARAMS ((sbitmap *, basic_block));
static void make_if_stmt_edges PARAMS ((sbitmap *, basic_block));
static void make_goto_stmt_edges PARAMS ((sbitmap *, basic_block));
static void make_break_stmt_edges PARAMS ((sbitmap *, basic_block));
static void make_continue_stmt_edges PARAMS ((sbitmap *, basic_block));
static void make_return_stmt_edges PARAMS ((sbitmap *, basic_block));
/* Various helpers. */
! static basic_block successor_block PARAMS ((basic_block));
/* }}} */
*************** tree_find_basic_blocks (t, nregs, file)
*** 133,205 ****
VARRAY_BB_INIT (basic_block_info, initial_cfg_capacity, "basic_block_info");
/* Find the basic blocks for the flowgraph. */
! make_nodes (t, NULL);
#ifdef DEBUG_TREE_FLOW
if (DEBUG_TREE_FLOW (2))
tree_debug_cfg ();
#endif /* DEBUG_TREE_FLOW */
! /* Create the edges of the flowgraph. */
! make_edges ();
! mark_critical_edges ();
#ifdef DEBUG_TREE_FLOW
! if (DEBUG_TREE_FLOW (1))
! {
! char name[1024];
! tree_debug_cfg ();
! sprintf (name, "%s.dot",
! IDENTIFIER_POINTER (DECL_NAME (current_function_decl)));
! tree_cfg2dot (name);
! }
#endif /* DEBUG_TREE_FLOW */
}
/* }}} */
! /* {{{ make_nodes()
! Build a flowgraph for the tree starting with T. Make CONTROL_PARENT
! the block dominating all the nodes in the new flowgraph. */
static void
! make_nodes (t, control_parent)
tree t;
basic_block control_parent;
{
/* Traverse the statement chain building basic blocks. */
while (t && t != error_mark_node)
{
switch (TREE_CODE (t))
{
case COMPOUND_STMT:
! make_compound_stmt_nodes (t, control_parent);
break;
case FOR_STMT:
! make_for_stmt_nodes (t, control_parent);
break;
case IF_STMT:
! make_if_stmt_nodes (t, control_parent);
break;
case WHILE_STMT:
! make_while_stmt_nodes (t, control_parent);
break;
case SWITCH_STMT:
! make_switch_stmt_nodes (t, control_parent);
break;
case DO_STMT:
! make_do_stmt_nodes (t, control_parent);
break;
default:
! t = create_maximal_bb (t, control_parent, 0);
break;
}
--- 132,221 ----
VARRAY_BB_INIT (basic_block_info, initial_cfg_capacity, "basic_block_info");
/* Find the basic blocks for the flowgraph. */
! make_blocks (t, NULL, NULL);
#ifdef DEBUG_TREE_FLOW
if (DEBUG_TREE_FLOW (2))
tree_debug_cfg ();
#endif /* DEBUG_TREE_FLOW */
! if (n_basic_blocks > 0)
! {
! /* Create the edges of the flowgraph. */
! make_edges ();
! mark_critical_edges ();
#ifdef DEBUG_TREE_FLOW
! if (DEBUG_TREE_FLOW (1))
! {
! char name[1024];
! tree_debug_cfg ();
! sprintf (name, "%s.dot",
! IDENTIFIER_POINTER (DECL_NAME (current_function_decl)));
! tree_cfg2dot (name);
! }
#endif /* DEBUG_TREE_FLOW */
+ }
}
/* }}} */
! /* {{{ make_blocks()
! Build a flowgraph for the tree starting with T.
!
! CONTROL_PARENT is the header block for the control structure immediately
! enclosing the new sub-graph.
!
! COMPOUND_STMT is the immediately enclosing compound statement to which T
! belongs. These statements are not represented in the flowgraph, but are
! important to determine successor basic blocks in successor_block(). */
static void
! make_blocks (t, control_parent, compound_stmt)
tree t;
basic_block control_parent;
+ tree compound_stmt;
{
/* Traverse the statement chain building basic blocks. */
while (t && t != error_mark_node)
{
+ get_tree_ann (t)->compound_stmt = compound_stmt;
+
switch (TREE_CODE (t))
{
case COMPOUND_STMT:
! make_blocks (COMPOUND_BODY (t), control_parent, t);
break;
case FOR_STMT:
! make_for_stmt_blocks (t, control_parent, compound_stmt);
break;
case IF_STMT:
! make_if_stmt_blocks (t, control_parent, compound_stmt);
break;
case WHILE_STMT:
! make_while_stmt_blocks (t, control_parent, compound_stmt);
break;
case SWITCH_STMT:
! make_switch_stmt_blocks (t, control_parent, compound_stmt);
break;
case DO_STMT:
! make_do_stmt_blocks (t, control_parent, compound_stmt);
break;
default:
! if (is_exec_stmt (t))
! {
! basic_block bb;
! bb = create_maximal_bb (t, control_parent, compound_stmt);
! t = bb->end_tree;
! }
break;
}
*************** make_nodes (t, control_parent)
*** 208,323 ****
}
}
/* }}} */
-
- /* {{{ make_compound_stmt_nodes()
! Create the nodes for a COMPOUND_STMT. */
!
! static void
! make_compound_stmt_nodes (t, control_parent)
! tree t;
! basic_block control_parent;
! {
! basic_block bb = create_bb (t, t, control_parent, 0);
! make_nodes (COMPOUND_BODY (t), bb);
! }
! /* }}} */
!
! /* {{{ make_for_stmt_nodes()
! Create the nodes for a FOR_STMT. */
static void
! make_for_stmt_nodes (t, control_parent)
tree t;
basic_block control_parent;
{
basic_block bb;
! bb = create_bb (t, t, control_parent, 1);
! create_maximal_bb (FOR_INIT_STMT (t), bb, 1);
! create_maximal_bb (FOR_COND (t), bb, 1);
! create_maximal_bb (FOR_EXPR (t), bb, 1);
! make_nodes (FOR_BODY (t), bb);
}
/* }}} */
! /* {{{ make_while_stmt_nodes ()
! Create the nodes for a WHILE_STMT. */
static void
! make_while_stmt_nodes (t, control_parent)
tree t;
basic_block control_parent;
{
! basic_block bb = create_bb (t, t, control_parent, 1);
! create_maximal_bb (WHILE_COND (t), bb, 1);
! make_nodes (WHILE_BODY (t), bb);
}
/* }}} */
! /* {{{ make_do_stmt_nodes ()
! Create the nodes for a DO_STMT. */
static void
! make_do_stmt_nodes (t, control_parent)
tree t;
basic_block control_parent;
{
! basic_block bb = create_bb (t, t, control_parent, 0);
! create_maximal_bb (DO_COND (t), bb, 1);
! make_nodes (DO_BODY (t), bb);
}
/* }}} */
! /* {{{ make_if_stmt_nodes ()
! Create the nodes for an IF_STMT. */
static void
! make_if_stmt_nodes (t, control_parent)
tree t;
basic_block control_parent;
{
! basic_block bb = create_bb (t, t, control_parent, 0);
! create_maximal_bb (IF_COND (t), bb, 0);
! make_nodes (THEN_CLAUSE (t), bb);
! make_nodes (ELSE_CLAUSE (t), bb);
}
/* }}} */
! /* {{{ make_switch_stmt_nodes ()
! Create the nodes for a SWITCH_STMT. */
static void
! make_switch_stmt_nodes (t, control_parent)
tree t;
basic_block control_parent;
{
! basic_block bb = create_bb (t, t, control_parent, 0);
! create_maximal_bb (SWITCH_COND (t), bb, 0);
! make_nodes (SWITCH_BODY (t), bb);
}
/* }}} */
/* {{{ create_maximal_bb ()
! Create a maximal basic block. A maximal basic block is a maximal
length sequence of consecutive statements that are always executed
! together. That is, if the first statement of the block is executed,
! then all the other statements will be executed in sequence until and
! including the last one in the block.
! Returns the last statement in the basic block. */
! static tree
! create_maximal_bb (t, control_parent, is_loop_header)
tree t;
basic_block control_parent;
! int is_loop_header;
{
tree first, last;
basic_block bb;
--- 224,341 ----
}
}
/* }}} */
! /* {{{ make_for_stmt_blocks()
! Create the blocks for a FOR_STMT. */
static void
! make_for_stmt_blocks (t, control_parent, compound_stmt)
tree t;
basic_block control_parent;
+ tree compound_stmt;
{
basic_block bb;
+ tree cond;
! /* Make sure that the condition block will be created even if the loop
! has no condition. This avoids a self-referencing edge into the loop
! header (which would create loop carried dependencies for the
! statements in FOR_INIT_STMT. */
! cond = (FOR_COND (t)) ? FOR_COND (t) : build_int_2 (1, 0);
!
! bb = create_bb (t, FOR_INIT_STMT (t), control_parent);
! create_maximal_bb (cond, bb, compound_stmt);
! create_maximal_bb (FOR_EXPR (t), bb, compound_stmt);
! make_blocks (FOR_BODY (t), bb, compound_stmt);
}
/* }}} */
! /* {{{ make_while_stmt_blocks ()
! Create the blocks for a WHILE_STMT. */
static void
! make_while_stmt_blocks (t, control_parent, compound_stmt)
tree t;
basic_block control_parent;
+ tree compound_stmt;
{
! basic_block bb = create_bb (t, t, control_parent);
! make_blocks (WHILE_BODY (t), bb, compound_stmt);
}
/* }}} */
! /* {{{ make_do_stmt_blocks ()
! Create the blocks for a DO_STMT. */
static void
! make_do_stmt_blocks (t, control_parent, compound_stmt)
tree t;
basic_block control_parent;
+ tree compound_stmt;
{
! basic_block bb = create_bb (t, t, control_parent);
! create_maximal_bb (DO_COND (t), bb, compound_stmt);
! make_blocks (DO_BODY (t), bb, compound_stmt);
}
/* }}} */
! /* {{{ make_if_stmt_blocks ()
! Create the blocks for an IF_STMT. */
static void
! make_if_stmt_blocks (t, control_parent, compound_stmt)
tree t;
basic_block control_parent;
+ tree compound_stmt;
{
! basic_block bb = create_bb (t, IF_COND (t), control_parent);
! make_blocks (THEN_CLAUSE (t), bb, compound_stmt);
! make_blocks (ELSE_CLAUSE (t), bb, compound_stmt);
}
/* }}} */
! /* {{{ make_switch_stmt_blocks ()
! Create the blocks for a SWITCH_STMT. */
static void
! make_switch_stmt_blocks (t, control_parent, compound_stmt)
tree t;
basic_block control_parent;
+ tree compound_stmt;
{
! basic_block bb = create_bb (t, SWITCH_COND (t), control_parent);
! make_blocks (SWITCH_BODY (t), bb, compound_stmt);
}
/* }}} */
/* {{{ create_maximal_bb ()
! Create a maximal basic block. A maximal basic block is a maximal
length sequence of consecutive statements that are always executed
! together. In other words, if the first statement of the block is
! executed, then all the other statements will be executed in sequence
! until and including the last one in the block.
! T is the first tree of the basic block.
! CONTROL_PARENT is the basic block of the innermost containing control
! structure.
!
! COMPOUND_STMT is the immediately enclosing compound statement to which
! the first tree of the block belongs.
!
! Returns the new basic block. */
!
! static basic_block
! create_maximal_bb (t, control_parent, compound_stmt)
tree t;
basic_block control_parent;
! tree compound_stmt;
{
tree first, last;
basic_block bb;
*************** create_maximal_bb (t, control_parent, is
*** 326,377 ****
return NULL;
first = last = t;
! bb = create_bb (first, last, control_parent, is_loop_header);
while (last && last != error_mark_node)
{
! map_stmt_to_bb (last, bb);
! /* If this is a control flow altering statement, store it in
! bb->exit_stmt. */
! if (is_ctrl_altering_stmt (last))
{
! /* Sanity check. Allow only one control flow altering
! statement per basic block. */
! if (BB_EXIT_STMT (bb))
! abort ();
!
! get_bb_ann (bb)->exit_stmt = last;
}
- /* If this statement is the end of the basic block, save it and
- return. */
if (stmt_ends_bb_p (last))
! {
! bb->end_tree = last;
! break;
! }
last = TREE_CHAIN (last);
}
! return last;
}
/* }}} */
/* {{{ create_bb()
! Creates and returns a new basic block. HEAD and END are the first and
! last statements in the block. CONTROL_PARENT is the entry block for
! the control structure containing the new block. Flag IS_LOOP_HEADER
! is non-zero if this block is part of a loop header. */
static basic_block
! create_bb (head, end, control_parent, is_loop_header)
tree head;
tree end;
basic_block control_parent;
- int is_loop_header;
{
basic_block bb;
--- 344,385 ----
return NULL;
first = last = t;
! bb = create_bb (first, last, control_parent);
while (last && last != error_mark_node)
{
! get_tree_ann (last)->compound_stmt = compound_stmt;
! if (is_exec_stmt (last))
{
! map_stmt_to_bb (last, bb);
! bb->end_tree = last;
}
if (stmt_ends_bb_p (last))
! break;
last = TREE_CHAIN (last);
}
! return bb;
}
/* }}} */
/* {{{ create_bb()
! Creates and returns a new basic block.
!
! HEAD and END are the first and last statements in the block.
+ CONTROL_PARENT is the entry block for the control structure containing
+ the new block. */
+
static basic_block
! create_bb (head, end, control_parent)
tree head;
tree end;
basic_block control_parent;
{
basic_block bb;
*************** create_bb (head, end, control_parent, is
*** 383,389 ****
bb->end_tree = end;
bb->index = n_basic_blocks;
get_bb_ann (bb)->parent = control_parent;
- get_bb_ann (bb)->is_loop_header = is_loop_header;
/* Grow the basic block array if needed. */
if ((size_t)n_basic_blocks == VARRAY_SIZE (basic_block_info))
--- 391,396 ----
*************** create_bb (head, end, control_parent, is
*** 399,405 ****
return bb;
}
-
/* }}} */
/* {{{ map_stmt_to_bb()
--- 406,411 ----
*************** map_stmt_to_bb (t, bb)
*** 426,432 ****
/* {{{ get_bb_ann()
! Get the annotation for the given block. Create a new one if
necessary. */
basic_block_ann
--- 432,438 ----
/* {{{ get_bb_ann()
! Get the annotation for the given block. Create a new one if
necessary. */
basic_block_ann
*************** make_edges ()
*** 477,547 ****
/* Edges for control flow altering statements (goto, break,
continue, return) need an edge to the corresponding target
block. */
! if (BB_EXIT_STMT (bb))
make_exit_edges (edge_cache, bb);
-
- /* Finally, if no edges were created above, this is a regular
- basic block that only needs a fallthru edge. */
- if (bb->succ == NULL)
- make_edge (edge_cache, bb, get_successor_block (bb), EDGE_FALLTHRU);
- }
-
-
- /* Basic reachability analysis. Add fake edges to blocks with no
- predecessors and give a warning if -Wunreachable-code is on. */
! for (i = 0; i < n_basic_blocks; i++)
! {
! basic_block bb = BASIC_BLOCK (i);
! tree head = bb->head_tree;
! if (bb->pred == NULL)
{
! basic_block parent;
!
! /* Avoid false positives for blocks that only contain a closing
! brace. e.g., in
!
! if (...)
! {
! ...
! return b;
! }
! the closing brace is never reached, but a warning in this
! case will be more annoying than useful. Create a fake edge
! from the previous basic block. */
! if (i > 0
! && bb->head_tree == bb->end_tree
! && TREE_CODE (bb->end_tree) == SCOPE_STMT
! && SCOPE_END_P (bb->end_tree))
{
! make_edge (edge_cache, BASIC_BLOCK (i - 1), bb, EDGE_FAKE);
}
- else
- {
- /* Otherwise, create a fake edge from BB's parent and give
- a warning. It doesn't really matter where we make the
- fake edge from. In the case of a closing brace, it's more
- natural to use the previous block, but these edges are
- ignored in data-flow computations anyway.
-
- FIXME - We should probably just collapse these unreachable
- nodes. */
- parent = (BB_PARENT (bb)) ? BB_PARENT (bb) : ENTRY_BLOCK_PTR;
- make_edge (edge_cache, parent, bb, EDGE_FAKE);
-
- if (warn_notreached)
- {
- while (!statement_code_p (TREE_CODE (head)))
- head = (BB_PARENT (bb))->head_tree;
! prep_stmt (head);
! warning ("unreachable statement");
! }
! }
}
}
if (edge_cache)
sbitmap_vector_free (edge_cache);
}
--- 483,516 ----
/* Edges for control flow altering statements (goto, break,
continue, return) need an edge to the corresponding target
block. */
! if (is_ctrl_altering_stmt (bb->end_tree))
make_exit_edges (edge_cache, bb);
! /* Incoming edges for label blocks in switch statements. It's easier
! to deal with these bottom-up than top-down. */
! if (TREE_CODE (bb->head_tree) == CASE_LABEL)
{
! basic_block switch_bb = switch_parent (bb);
! if (switch_bb == NULL)
{
! prep_stmt (bb->head_tree);
! error ("case label not within a switch statement");
! return;
}
! make_edge (edge_cache, switch_bb, bb, 0);
}
+
+ /* Finally, if no edges were created above, this is a regular
+ basic block that only needs a fallthru edge. */
+ if (bb->succ == NULL)
+ make_edge (edge_cache, bb, successor_block (bb), EDGE_FALLTHRU);
}
+ /* Clean up the graph and warn for unreachable code. */
+ delete_unreachable_blocks ();
+
if (edge_cache)
sbitmap_vector_free (edge_cache);
}
*************** make_ctrl_stmt_edges (edge_cache, bb)
*** 558,567 ****
{
switch (TREE_CODE (bb->head_tree))
{
- case COMPOUND_STMT:
- make_compound_stmt_edges (edge_cache, bb);
- break;
-
case FOR_STMT:
make_for_stmt_edges (edge_cache, bb);
break;
--- 527,532 ----
*************** make_ctrl_stmt_edges (edge_cache, bb)
*** 579,592 ****
break;
case SWITCH_STMT:
! make_switch_stmt_edges (edge_cache, bb);
break;
default:
abort ();
}
}
-
/* }}} */
/* {{{ make_exit_edges()
--- 544,557 ----
break;
case SWITCH_STMT:
! /* Nothing to do. Each label inside the switch statement will create
! its own edge form the switch block. */
break;
default:
abort ();
}
}
/* }}} */
/* {{{ make_exit_edges()
*************** make_exit_edges (edge_cache, bb)
*** 599,605 ****
sbitmap *edge_cache;
basic_block bb;
{
! switch (TREE_CODE (BB_EXIT_STMT (bb)))
{
case BREAK_STMT:
make_break_stmt_edges (edge_cache, bb);
--- 564,570 ----
sbitmap *edge_cache;
basic_block bb;
{
! switch (TREE_CODE (bb->end_tree))
{
case BREAK_STMT:
make_break_stmt_edges (edge_cache, bb);
*************** make_exit_edges (edge_cache, bb)
*** 621,658 ****
abort ();
}
}
-
/* }}} */
- /* {{{ make_compound_stmt_edges()
-
- Create edges for a COMPOUND_STMT structure that starts at basic block bb. */
-
- static void
- make_compound_stmt_edges (edge_cache, bb)
- sbitmap *edge_cache;
- basic_block bb;
- {
- tree entry = bb->head_tree;
- basic_block body_bb;
-
- if (TREE_CODE (entry) != COMPOUND_STMT)
- abort ();
-
- body_bb = (COMPOUND_BODY (entry)) ? BASIC_BLOCK (bb->index + 1) : NULL;
-
- /* Create the following edges.
-
- COMPOUND_STMT
- |
- v
- COMPOUND_BODY */
-
- if (body_bb)
- make_edge (edge_cache, bb, body_bb, 0);
- }
- /* }}} */
-
/* {{{ make_for_stmt_edges()
Create edges for a FOR_STMT structure that starts at basic block BB. */
--- 586,593 ----
*************** make_for_stmt_edges (edge_cache, bb)
*** 663,689 ****
basic_block bb;
{
tree entry = bb->head_tree;
! int index;
! basic_block init_bb, cond_bb, expr_bb, body_bb;
if (TREE_CODE (entry) != FOR_STMT)
abort ();
- /* Basic blocks for each component. Note that the block numbers are
- determined by make_for_stmt_nodes(). */
- index = bb->index + 1;
- init_bb = (FOR_INIT_STMT (entry)) ? BASIC_BLOCK (index++) : NULL;
- cond_bb = (FOR_COND (entry)) ? BASIC_BLOCK (index++) : NULL;
- expr_bb = (FOR_EXPR (entry)) ? BASIC_BLOCK (index++) : NULL;
- body_bb = (FOR_BODY (entry)) ? BASIC_BLOCK (index++) : NULL;
-
/* Create the following edges.
FOR_STMT
|
- v
- FOR_INIT
- |
v
+-- FOR_COND <----------+
| | |
--- 598,613 ----
basic_block bb;
{
tree entry = bb->head_tree;
! int ix;
! basic_block cond_bb, expr_bb, body_bb;
if (TREE_CODE (entry) != FOR_STMT)
abort ();
/* Create the following edges.
FOR_STMT
|
v
+-- FOR_COND <----------+
| | |
*************** make_for_stmt_edges (edge_cache, bb)
*** 693,727 ****
| FOR_BODY
|
|
! +--> EXIT
- - If the loop does not have a condition expression, edges involving
- the condition block, go to the loop header ("infinite" loops).
-
- If the loop does not have an expression block, we replace it with
the condition block.
! - Similarly, if the body is empty, we replace it with the
! expression block. Hence, loops with neither component will reduce
! to the header block with a self-referencing edge. */
!
! if (init_bb == NULL)
! init_bb = bb;
!
! if (cond_bb == NULL)
! cond_bb = init_bb;
! if (expr_bb == NULL)
! expr_bb = cond_bb;
! if (body_bb == NULL)
! body_bb = expr_bb;
! make_edge (edge_cache, bb, init_bb, 0);
! make_edge (edge_cache, init_bb, cond_bb, 0);
make_edge (edge_cache, cond_bb, body_bb, 0);
! make_edge (edge_cache, expr_bb, cond_bb, 0);
! make_edge (edge_cache, cond_bb, get_successor_block (bb), 0);
}
/* }}} */
--- 617,651 ----
| FOR_BODY
|
|
! +--> Next block
- If the loop does not have an expression block, we replace it with
the condition block.
! - Similarly, if the body is empty, we replace it with the expression
! block. Hence, loops with neither component will reduce to the
! condition block with a self-referencing edge. */
! /* Basic blocks for each component. Note that the block numbers are
! determined by make_for_stmt_blocks(). */
! ix = bb->index + 1;
! /* make_for_stmt_blocks() guarantees that the condition block is created
! even for unconditional loops. */
! cond_bb = BASIC_BLOCK (ix++);
! expr_bb = (FOR_EXPR (entry)) ? BASIC_BLOCK (ix++) : cond_bb;
! body_bb = (first_exec_stmt (FOR_BODY (entry))) ? BASIC_BLOCK (ix) : expr_bb;
! make_edge (edge_cache, bb, cond_bb, 0);
make_edge (edge_cache, cond_bb, body_bb, 0);
!
! /* Special case. Only create the edge expr_bb -> cond_bb if there really
! is a block for FOR_EXPR. Otherwise, if the loop has a body, and since
! in this case expr_bb == cond_bb, we end up with an unnecessary
! self-referencing edge in cond_bb. */
! if (FOR_EXPR (entry))
! make_edge (edge_cache, expr_bb, cond_bb, 0);
! make_edge (edge_cache, cond_bb, successor_block (bb), 0);
}
/* }}} */
*************** make_while_stmt_edges (edge_cache, bb)
*** 735,759 ****
basic_block bb;
{
tree entry = bb->head_tree;
! basic_block cond_bb, body_bb;
! int index;
if (TREE_CODE (entry) != WHILE_STMT)
abort ();
-
- /* Basic blocks for each component. Note that the block numbers are
- determined by make_for_stmt_nodes(). */
- index = bb->index + 1;
- cond_bb = (WHILE_COND (entry)) ? BASIC_BLOCK (index++) : NULL;
- body_bb = (WHILE_BODY (entry)) ? BASIC_BLOCK (index++) : NULL;
! /* Create the following edges. The other edges will be naturally created
by the main loop in create_edges().
! WHILE_STMT
! |
! v
! +- WHILE_COND
| |
| v
| WHILE_BODY
--- 659,673 ----
basic_block bb;
{
tree entry = bb->head_tree;
! basic_block body_bb;
if (TREE_CODE (entry) != WHILE_STMT)
abort ();
! /* Create the following edges. The other edges will be naturally created
by the main loop in create_edges().
! +- WHILE_STMT
| |
| v
| WHILE_BODY
*************** make_while_stmt_edges (edge_cache, bb)
*** 762,777 ****
+--> EXIT
If the body doesn't exist, we use the header instead. */
-
- if (cond_bb == NULL)
- cond_bb = bb;
! if (body_bb == NULL)
! body_bb = cond_bb;
! make_edge (edge_cache, bb, cond_bb, 0);
! make_edge (edge_cache, cond_bb, body_bb, 0);
! make_edge (edge_cache, cond_bb, get_successor_block (bb), 0);
}
/* }}} */
--- 676,690 ----
+--> EXIT
If the body doesn't exist, we use the header instead. */
! /* Basic blocks for each component. Note that the block numbers are
! determined by make_while_stmt_blocks(). */
! body_bb = (first_exec_stmt (WHILE_BODY (entry)))
! ? BASIC_BLOCK (bb->index + 1)
! : bb;
! make_edge (edge_cache, bb, body_bb, 0);
! make_edge (edge_cache, bb, successor_block (bb), 0);
}
/* }}} */
*************** make_do_stmt_edges (edge_cache, bb)
*** 786,802 ****
{
tree entry = bb->head_tree;
basic_block cond_bb, body_bb;
- int index;
if (TREE_CODE (entry) != DO_STMT)
abort ();
- /* Basic blocks for each component. Note that the block numbers are
- determined by make_for_stmt_nodes(). */
- index = bb->index + 1;
- cond_bb = (DO_COND (entry)) ? BASIC_BLOCK (index++) : NULL;
- body_bb = (DO_BODY (entry)) ? BASIC_BLOCK (index++) : NULL;
-
/* Create the following edges. The remaining edges will be added
by the main loop in make_edges().
--- 699,708 ----
*************** make_do_stmt_edges (edge_cache, bb)
*** 813,827 ****
If the body doesn't exist, we use the condition instead. */
! if (cond_bb == NULL)
! cond_bb = bb;
! if (body_bb == NULL)
! body_bb = cond_bb;
make_edge (edge_cache, bb, body_bb, 0);
make_edge (edge_cache, cond_bb, body_bb, 0);
! make_edge (edge_cache, cond_bb, get_successor_block (bb), 0);
}
/* }}} */
--- 719,735 ----
If the body doesn't exist, we use the condition instead. */
! /* Basic blocks for each component. Note that the block numbers are
! determined by make_do_stmt_blocks(). */
! cond_bb = BASIC_BLOCK (bb->index + 1); /* This block always exists. */
! body_bb = (first_exec_stmt (DO_BODY (entry)))
! ? BASIC_BLOCK (bb->index + 2)
! : cond_bb;
make_edge (edge_cache, bb, body_bb, 0);
make_edge (edge_cache, cond_bb, body_bb, 0);
! make_edge (edge_cache, cond_bb, successor_block (bb), 0);
}
/* }}} */
*************** make_if_stmt_edges (edge_cache, bb)
*** 835,932 ****
basic_block bb;
{
tree entry = bb->head_tree;
! basic_block cond_bb, then_bb, else_bb;
! int index;
if (TREE_CODE (entry) != IF_STMT)
abort ();
! /* Basic blocks for each component. */
! index = bb->index + 1;
! cond_bb = BASIC_BLOCK (bb->index + 1);
! then_bb = (THEN_CLAUSE (entry)) ? BB_FOR_STMT (THEN_CLAUSE (entry)): NULL;
! else_bb = (ELSE_CLAUSE (entry)) ? BB_FOR_STMT (ELSE_CLAUSE (entry)): NULL;
/* Create the following edges.
IF_STMT
- |
- v
- IF_COND
/ \
/ \
THEN ELSE
Either clause may be empty. */
- make_edge (edge_cache, bb, cond_bb, 0);
-
if (then_bb)
! make_edge (edge_cache, cond_bb, then_bb, 0);
if (else_bb)
! make_edge (edge_cache, cond_bb, else_bb, 0);
! /* We only need an edge to the exit block if one of the clauses is
missing. */
if (then_bb == NULL || else_bb == NULL)
! make_edge (edge_cache, cond_bb, get_successor_block (bb), 0);
! }
! /* }}} */
!
! /* {{{ make_switch_stmt_edges()
!
! Create edges for a SWITCH_STMT structure starting at block bb. */
!
! static void
! make_switch_stmt_edges (edge_cache, bb)
! sbitmap *edge_cache;
! basic_block bb;
! {
! tree t, body;
! tree entry = bb->head_tree;
! basic_block cond_bb;
!
! if (TREE_CODE (entry) != SWITCH_STMT)
! abort ();
!
! /* Create the following edges.
!
! SWITCH_STMT
! |
! v
! SWITCH_COND
! / | \
! / | \
! L1 ... Ln */
!
! cond_bb = BASIC_BLOCK (bb->index + 1);
! make_edge (edge_cache, bb, cond_bb, 0);
!
! /* Make an edge to each case label in the body. The first label is
! treated differently. Instead of creating an edge to the first
! label, create an edge to the COMPOUND_STMT containing all the
! labels. This prevents the blocks for the COMPOUND_STMT and
! SCOPE_STMT to be left disconnected from the graph. */
!
! body = SWITCH_BODY (entry);
! if (TREE_CODE (body) != COMPOUND_STMT)
! abort ();
!
! make_edge (edge_cache, cond_bb, BB_FOR_STMT (body), 0);
!
! body = COMPOUND_BODY (body);
! while (body && TREE_CODE (body) != CASE_LABEL)
! body = TREE_CHAIN (body);
!
! if (body == NULL)
! abort ();
!
! for (t = TREE_CHAIN (body); t; t = TREE_CHAIN (t))
! if (TREE_CODE (t) == CASE_LABEL)
! make_edge (edge_cache, cond_bb, BB_FOR_STMT (t), 0);
}
-
/* }}} */
/* {{{ make_goto_stmt_edges()
--- 743,781 ----
basic_block bb;
{
tree entry = bb->head_tree;
! basic_block then_bb, else_bb;
! tree then_t, else_t;
if (TREE_CODE (entry) != IF_STMT)
abort ();
! /* Entry basic blocks for each component. */
! then_t = first_exec_stmt (THEN_CLAUSE (entry));
! then_bb = (then_t) ? BB_FOR_STMT (then_t) : NULL;
+ else_t = first_exec_stmt (ELSE_CLAUSE (entry));
+ else_bb = (else_t) ? BB_FOR_STMT (else_t) : NULL;
+
/* Create the following edges.
IF_STMT
/ \
/ \
THEN ELSE
Either clause may be empty. */
if (then_bb)
! make_edge (edge_cache, bb, then_bb, 0);
if (else_bb)
! make_edge (edge_cache, bb, else_bb, 0);
! /* We only need an edge to BB's successor block if one of the clauses is
missing. */
if (then_bb == NULL || else_bb == NULL)
! make_edge (edge_cache, bb, successor_block (bb), 0);
}
/* }}} */
/* {{{ make_goto_stmt_edges()
*************** make_goto_stmt_edges (edge_cache, bb)
*** 941,954 ****
tree goto_t, dest;
int i;
! goto_t = BB_EXIT_STMT (bb);
if (goto_t == NULL || TREE_CODE (goto_t) != GOTO_STMT)
abort ();
dest = GOTO_DESTINATION (goto_t);
/* Look for the block starting with the destination label. In the
! case of a computed goto, make an edge to any label node we find
in the CFG. */
for (i = 0; i < n_basic_blocks; i++)
{
--- 790,803 ----
tree goto_t, dest;
int i;
! goto_t = bb->end_tree;
if (goto_t == NULL || TREE_CODE (goto_t) != GOTO_STMT)
abort ();
dest = GOTO_DESTINATION (goto_t);
/* Look for the block starting with the destination label. In the
! case of a computed goto, make an edge to any label block we find
in the CFG. */
for (i = 0; i < n_basic_blocks; i++)
{
*************** make_goto_stmt_edges (edge_cache, bb)
*** 965,983 ****
break;
}
! /* Computed GOTOs. Make an edge to every label node. */
else if (TREE_CODE (dest) != LABEL_DECL
&& TREE_CODE (target) == LABEL_STMT)
make_edge (edge_cache, bb, target_bb, 0);
}
}
-
/* }}} */
/* {{{ make_break_stmt_edges()
! A break statement creates an edge from the break node to the successor
! node for the break statement's control parent. */
static void
make_break_stmt_edges (edge_cache, bb)
--- 814,831 ----
break;
}
! /* Computed GOTOs. Make an edge to every label block. */
else if (TREE_CODE (dest) != LABEL_DECL
&& TREE_CODE (target) == LABEL_STMT)
make_edge (edge_cache, bb, target_bb, 0);
}
}
/* }}} */
/* {{{ make_break_stmt_edges()
! A break statement creates an edge from the break block to the successor
! block for the break statement's control parent. */
static void
make_break_stmt_edges (edge_cache, bb)
*************** make_break_stmt_edges (edge_cache, bb)
*** 987,1006 ****
tree break_t;
basic_block control_parent;
! break_t = BB_EXIT_STMT (bb);
if (break_t == NULL || TREE_CODE (break_t) != BREAK_STMT)
abort ();
! /* A break statement *must* have an enclosing control structure. */
! control_parent = BB_PARENT (bb);
if (control_parent == NULL)
! abort ();
!
! /* Look for the innermost containing WHILE, FOR, DO or SWITCH statement. */
! while (control_parent
! && !is_loop_stmt (control_parent->head_tree)
! && TREE_CODE (control_parent->head_tree) != SWITCH_STMT)
! control_parent = BB_PARENT (control_parent);
if (control_parent == NULL)
{
--- 835,848 ----
tree break_t;
basic_block control_parent;
! break_t = bb->end_tree;
if (break_t == NULL || TREE_CODE (break_t) != BREAK_STMT)
abort ();
! /* Look for the innermost containing SWITCH, WHILE, FOR or DO. */
! control_parent = switch_parent (bb);
if (control_parent == NULL)
! control_parent = loop_parent (bb);
if (control_parent == NULL)
{
*************** make_break_stmt_edges (edge_cache, bb)
*** 1009,1022 ****
return;
}
! make_edge (edge_cache, bb, get_successor_block (control_parent), 0);
}
/* }}} */
/* {{{ make_continue_stmt_edges()
! A continue statement creates an edge from the continue node to the
! control parent's expression node. */
static void
make_continue_stmt_edges (edge_cache, bb)
--- 851,864 ----
return;
}
! make_edge (edge_cache, bb, successor_block (control_parent), 0);
}
/* }}} */
/* {{{ make_continue_stmt_edges()
! A continue statement creates an edge from the continue block to the
! control parent's expression block. */
static void
make_continue_stmt_edges (edge_cache, bb)
*************** make_continue_stmt_edges (edge_cache, bb
*** 1026,1037 ****
tree continue_t;
basic_block loop_bb;
! continue_t = BB_EXIT_STMT (bb);
if (continue_t == NULL || TREE_CODE (continue_t) != CONTINUE_STMT)
abort ();
/* A continue statement *must* have an enclosing control structure. */
! loop_bb = find_loop_parent (bb);
if (loop_bb == NULL)
{
--- 868,879 ----
tree continue_t;
basic_block loop_bb;
! continue_t = bb->end_tree;
if (continue_t == NULL || TREE_CODE (continue_t) != CONTINUE_STMT)
abort ();
/* A continue statement *must* have an enclosing control structure. */
! loop_bb = loop_parent (bb);
if (loop_bb == NULL)
{
*************** make_continue_stmt_edges (edge_cache, bb
*** 1040,1048 ****
return;
}
! make_edge (edge_cache, bb, get_condition_block (loop_bb), 0);
}
-
/* }}} */
/* {{{ make_return_stmt_edges()
--- 882,889 ----
return;
}
! make_edge (edge_cache, bb, condition_block (loop_bb), 0);
}
/* }}} */
/* {{{ make_return_stmt_edges()
*************** make_return_stmt_edges (edge_cache, bb)
*** 1054,1119 ****
sbitmap *edge_cache;
basic_block bb;
{
! tree return_t = BB_EXIT_STMT (bb);
if (return_t == NULL || TREE_CODE (return_t) != RETURN_STMT)
abort ();
make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0);
}
/* }}} */
/* Helper functions and predicates. */
! /* {{{ get_successor_block()
! Return the successor block for BB. If the block has no successors we try
! the enclosing control structure until we find one. If we reached nesting
level 0, return the exit block. */
static basic_block
! get_successor_block (bb)
basic_block bb;
{
! basic_block chain_bb, parent_bb;
if (bb == NULL)
abort ();
! /* Common case. Try to return the basic block of the last statement's
! successor. */
! if (TREE_CHAIN (bb->end_tree))
! return BB_FOR_STMT (TREE_CHAIN (bb->end_tree));
!
! /* Special case. The successor to the last block in the graph (i.e.,
! the function's closing brace) is always EXIT_BLOCK_PTR. */
! if (bb->index == n_basic_blocks - 1)
! return EXIT_BLOCK_PTR;
! /* Walk up the control structure to see if our parent has a successor.
! Iterate until we find one or we reach nesting level 0. */
! chain_bb = NULL;
parent_bb = BB_PARENT (bb);
!
! while (chain_bb == NULL)
{
! if (parent_bb == NULL)
! chain_bb = EXIT_BLOCK_PTR;
!
! else if (is_loop_stmt (parent_bb->head_tree))
! chain_bb = get_condition_block (parent_bb);
! else if (TREE_CHAIN (parent_bb->head_tree))
! chain_bb = BB_FOR_STMT (TREE_CHAIN (parent_bb->head_tree));
parent_bb = BB_PARENT (parent_bb);
}
! return chain_bb;
}
-
/* }}} */
/* {{{ is_ctrl_stmt()
--- 895,1058 ----
sbitmap *edge_cache;
basic_block bb;
{
! tree return_t = bb->end_tree;
if (return_t == NULL || TREE_CODE (return_t) != RETURN_STMT)
abort ();
make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0);
}
+ /* }}} */
+
+
+ /* Flowgraph analysis. */
+
+ /* {{{ delete_unreachable_blocks()
+
+ Delete all unreachable basic blocks. */
+
+ static void
+ delete_unreachable_blocks ()
+ {
+ int i;
+
+ find_unreachable_blocks ();
+
+ /* Delete all unreachable basic blocks. Count down so that we
+ don't interfere with the block renumbering that happens in
+ delete_block. */
+ for (i = n_basic_blocks - 1; i >= 0; --i)
+ {
+ basic_block b = BASIC_BLOCK (i);
+
+ if (!b->reachable)
+ delete_block (b);
+ }
+ }
+ /* }}} */
+
+ /* {{{ delete_block()
+
+ Remove a block from the flowgraph. Emit a warning if -Wunreachable-code
+ is set. */
+
+ static void
+ delete_block (bb)
+ basic_block bb;
+ {
+ edge e, next, *q;
+ tree t;
+
+ if (warn_notreached)
+ {
+ tree stmt;
+
+ /* The only nodes whose head tree is not a statement are condition
+ nodes for DO_STMT and WHILE_STMT loops. */
+ if (statement_code_p (TREE_CODE (bb->head_tree)))
+ stmt = bb->head_tree;
+ else
+ stmt = BB_PARENT (bb)->head_tree;
+
+ prep_stmt (stmt);
+ warning ("unreachable statement");
+ }
+
+ /* Remove all the instructions in the block.
+
+ FIXME - This merely unmaps the statements. We should remove them. */
+ t = bb->head_tree;
+ while (t)
+ {
+ map_stmt_to_bb (t, NULL);
+ if (t == bb->end_tree)
+ break;
+ t = TREE_CHAIN (t);
+ }
+
+ /* Remove the edges into and out of this block. Note that there
+ may indeed be edges in, if we are removing an unreachable loop. */
+ for (e = bb->pred; e; e = next)
+ {
+ for (q = &e->src->succ; *q != e; q = &(*q)->succ_next)
+ continue;
+ *q = e->succ_next;
+ next = e->pred_next;
+ n_edges--;
+ free (e);
+ }
+
+ for (e = bb->succ; e; e = next)
+ {
+ for (q = &e->dest->pred; *q != e; q = &(*q)->pred_next)
+ continue;
+ *q = e->pred_next;
+ next = e->succ_next;
+ n_edges--;
+ free (e);
+ }
+
+ bb->pred = NULL;
+ bb->succ = NULL;
+ /* Remove the basic block from the array, and compact behind it. */
+ expunge_block (bb);
+ }
/* }}} */
/* Helper functions and predicates. */
! /* {{{ successor_block()
! Return the successor block for BB. If the block has no successors we try
! the enclosing control structure until we find one. If we reached nesting
level 0, return the exit block. */
static basic_block
! successor_block (bb)
basic_block bb;
{
! basic_block parent_bb;
! tree succ_stmt;
if (bb == NULL)
abort ();
! /* Common case. For control flow header blocks, return the successor of
! the block's first statement. For regular blocks, return the successor
! of the block's last statement. */
! succ_stmt = is_ctrl_stmt (bb->head_tree)
! ? first_exec_stmt (TREE_CHAIN (bb->head_tree))
! : first_exec_stmt (TREE_CHAIN (bb->end_tree));
! if (succ_stmt)
! return BB_FOR_STMT (succ_stmt);
!
! /* We couldn't find a successor for BB. Walk up the control structure to
! see if our parent has a successor. Iterate until we find one or we
! reach nesting level 0. */
parent_bb = BB_PARENT (bb);
! while (parent_bb)
{
! /* If BB is the last block inside a loop body, return the condition
! block for the loop structure. */
! if (is_loop_stmt (parent_bb->head_tree))
! return condition_block (parent_bb);
! /* Otherwise, If BB's control parent has a successor, return its
! block. */
! succ_stmt = first_exec_stmt (TREE_CHAIN (parent_bb->head_tree));
! if (succ_stmt)
! return BB_FOR_STMT (succ_stmt);
+ /* None of the above. Keeping going up the control parent chain. */
parent_bb = BB_PARENT (parent_bb);
}
! /* We reached nesting level 0. Return the exit block. */
! return EXIT_BLOCK_PTR;
}
/* }}} */
/* {{{ is_ctrl_stmt()
*************** is_ctrl_stmt (t)
*** 1131,1138 ****
|| TREE_CODE (t) == IF_STMT
|| TREE_CODE (t) == WHILE_STMT
|| TREE_CODE (t) == SWITCH_STMT
! || TREE_CODE (t) == DO_STMT
! || TREE_CODE (t) == COMPOUND_STMT);
}
/* }}} */
--- 1070,1076 ----
|| TREE_CODE (t) == IF_STMT
|| TREE_CODE (t) == WHILE_STMT
|| TREE_CODE (t) == SWITCH_STMT
! || TREE_CODE (t) == DO_STMT);
}
/* }}} */
*************** is_ctrl_altering_stmt (t)
*** 1153,1159 ****
|| TREE_CODE (t) == BREAK_STMT
|| TREE_CODE (t) == RETURN_STMT);
}
-
/* }}} */
/* {{{ is_loop_stmt()
--- 1091,1096 ----
*************** stmt_starts_bb_p (t)
*** 1187,1192 ****
--- 1124,1130 ----
return (TREE_CODE (t) == CASE_LABEL
|| TREE_CODE (t) == LABEL_STMT
|| TREE_CODE (t) == RETURN_STMT
+ || TREE_CODE (t) == COMPOUND_STMT
|| is_ctrl_stmt (t));
}
/* }}} */
*************** stmt_ends_bb_p (t)
*** 1201,1207 ****
tree t;
{
/* Sanity check. */
-
if (t == NULL)
abort ();
--- 1139,1144 ----
*************** stmt_ends_bb_p (t)
*** 1216,1222 ****
/* {{{ delete_cfg()
! Remove all the nodes and edges that make up the flowgraph. */
void
delete_cfg ()
--- 1153,1159 ----
/* {{{ delete_cfg()
! Remove all the blocks and edges that make up the flowgraph. */
void
delete_cfg ()
*************** delete_cfg ()
*** 1240,1252 ****
}
/* }}} */
! /* {{{ find_loop_parent()
Returns the header block for the innermost loop containing BB. It
returns NULL if BB is not inside a loop. */
basic_block
! find_loop_parent (bb)
basic_block bb;
{
do
--- 1177,1189 ----
}
/* }}} */
! /* {{{ loop_parent()
Returns the header block for the innermost loop containing BB. It
returns NULL if BB is not inside a loop. */
basic_block
! loop_parent (bb)
basic_block bb;
{
do
*************** find_loop_parent (bb)
*** 1255,1270 ****
return bb;
}
-
/* }}} */
! /* {{{ get_condition_block()
Returns the block containing the condition expression controlling the
loop starting at LOOP_BB (i.e., the block containing DO_COND or
! WHILE_COND or FOR_COND).
! Since these nodes hold expressions, not statements, we cannot use
BB_FOR_STMT() to determine their basic block. Instead, we count from
the basic block for the loop entry.
--- 1192,1206 ----
return bb;
}
/* }}} */
! /* {{{ condition_block()
Returns the block containing the condition expression controlling the
loop starting at LOOP_BB (i.e., the block containing DO_COND or
! WHILE_COND or FOR_EXPR).
! Since these blocks hold expressions, not statements, we cannot use
BB_FOR_STMT() to determine their basic block. Instead, we count from
the basic block for the loop entry.
*************** find_loop_parent (bb)
*** 1273,1308 ****
this. */
basic_block
! get_condition_block (loop_bb)
basic_block loop_bb;
{
- basic_block cond_bb;
int index;
! /* Sanity check. This is only valid on loop header nodes. */
! if (TREE_CODE (loop_bb->head_tree) != FOR_STMT
! && TREE_CODE (loop_bb->head_tree) != WHILE_STMT
! && TREE_CODE (loop_bb->head_tree) != DO_STMT)
abort ();
! index = loop_bb->index + 1;
! if (TREE_CODE (loop_bb->head_tree) == FOR_STMT)
! {
! /* Usually, the loop expression in a FOR_STMT will be the third
! node after the loop entry block. However, a FOR_STMT may be
! missing both the INIT and COND expressions. */
! if (FOR_INIT_STMT (loop_bb->head_tree))
! index++;
! if (FOR_COND (loop_bb->head_tree))
! index++;
}
! cond_bb = BASIC_BLOCK (index);
! return cond_bb;
}
/* }}} */
--- 1209,1312 ----
this. */
basic_block
! condition_block (loop_bb)
basic_block loop_bb;
{
int index;
+ enum tree_code code = TREE_CODE (loop_bb->head_tree);
! if (code == FOR_STMT)
! {
! /* Usually, the loop expression in a FOR_STMT will be the second
! block after the loop entry block. However, the FOR_EXPR block
! does not always exist. */
! if (FOR_EXPR (loop_bb->head_tree))
! index = loop_bb->index + 2;
! else
! index = loop_bb->index + 1;
! }
! else if (code == DO_STMT)
! index = loop_bb->index + 1;
! else if (code == WHILE_STMT)
! index = loop_bb->index;
! else
abort ();
! return BASIC_BLOCK (index);
! }
! /* }}} */
! /* {{{ switch_parent()
!
! Returns the header block for the innermost switch statement containing
! BB. It returns NULL if BB is not inside a switch statement. */
!
! basic_block
! switch_parent (bb)
! basic_block bb;
! {
! do
! bb = BB_PARENT (bb);
! while (bb && TREE_CODE (bb->head_tree) != SWITCH_STMT);
!
! return bb;
! }
! /* }}} */
!
! /* {{{ first_exec_stmt()
!
! Return the first executable statement starting at T. */
!
! tree
! first_exec_stmt (t)
! tree t;
! {
! tree chain;
!
! if (t == NULL)
! return NULL;
!
! /* Common case. T is already an executable statement. */
! if (is_exec_stmt (t))
! return t;
!
! /* If T is a compound statement T, try the first executable statement
! in T's body. */
! if (TREE_CODE (t) == COMPOUND_STMT)
! {
! chain = first_exec_stmt (COMPOUND_BODY (t));
! if (chain)
! return chain;
}
! /* If we still haven't found one and T is at the end of a tree chain, try
! the successor of the enclosing compound statement. */
! if (TREE_CHAIN (t) == NULL)
! {
! chain = first_exec_stmt (TREE_CHAIN (TREE_COMPOUND_STMT (t)));
! if (chain)
! return chain;
! }
! /* Finally, recursively look for the first executable statement
! starting with T's successor. */
! return first_exec_stmt (TREE_CHAIN (t));
}
+ /* }}} */
+
+ /* {{{ is_exec_stmt()
+
+ Return 1 if T is an executable statement. */
+ int
+ is_exec_stmt (t)
+ tree t;
+ {
+ return (t
+ && statement_code_p (TREE_CODE (t))
+ && TREE_CODE (t) != COMPOUND_STMT
+ && TREE_CODE (t) != SCOPE_STMT);
+ }
/* }}} */
*************** tree_cfg2dot (fname)
*** 1479,1483 ****
fputc ('}', f);
fclose (f);
}
-
/* }}} */
--- 1483,1486 ----
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.2.2
diff -d -p -d -c -p -r1.1.2.2 tree-dfa.c
*** tree-dfa.c 2001/08/01 05:36:58 1.1.2.2
--- tree-dfa.c 2001/08/11 00:01:05
*************** debug_tree_dfa (level, filename, line)
*** 70,77 ****
/* {{{ Local declarations. */
! static tree find_refs PARAMS ((tree *, int *, void *));
! static void find_refs_in_expr PARAMS ((tree, enum varref_type, tree, tree));
static varref_node create_node PARAMS ((varref));
/* }}} */
--- 70,79 ----
/* {{{ Local declarations. */
! static void find_refs_in_stmt PARAMS ((tree, basic_block));
! static tree find_refs_in_stmt_expr PARAMS ((tree *, int *, void *));
! static void find_refs_in_expr PARAMS ((tree, enum varref_type, basic_block,
! tree, tree));
static varref_node create_node PARAMS ((varref));
/* }}} */
*************** tree ref_symbols_list;
*** 88,106 ****
/* {{{ tree_find_varrefs()
! Main entry point. Walks T looking for variable references. PARENT_STMT
! is the statement that contains T (if any). This is used to handle
! expression statements, properly. Specifically, we need to keep track
! of which basic block holds the statement so that we can associate
! variable references to it. */
void
! tree_find_varrefs (t, parent_stmt)
! tree t;
! tree parent_stmt;
{
! walk_stmt_tree (&t, find_refs, (void *)parent_stmt);
#ifdef DEBUG_TREE_DFA
if (DEBUG_TREE_DFA (1))
{
--- 90,124 ----
/* {{{ tree_find_varrefs()
! Look for variable references in every block of the flowgraph. */
void
! tree_find_varrefs ()
{
! int i;
!
! for (i = 0; i < n_basic_blocks; i++)
! {
! basic_block bb = BASIC_BLOCK (i);
! tree t = bb->head_tree;
!
! while (t)
! {
! /* The only non-statements that we can have in a block are the
! expressions in control header blocks (FOR_COND, DO_COND, etc).
! Those are handled when we process the associated control
! statement. */
! if (statement_code_p (TREE_CODE (t)))
! {
! find_refs_in_stmt (t, bb);
! if (t == bb->end_tree || is_ctrl_stmt (t))
! break;
! }
+ t = TREE_CHAIN (t);
+ }
+ }
+
#ifdef DEBUG_TREE_DFA
if (DEBUG_TREE_DFA (1))
{
*************** tree_find_varrefs (t, parent_stmt)
*** 118,124 ****
print_node_brief (stderr, "\t", sym, 0);
fputc ('\n', stderr);
! for (i = VARREF_LIST_FIRST (TREE_REFS (sym)); i; i = VARREF_NODE_NEXT (i))
{
varref ref = VARREF_NODE_ELEM (i);
fputs ("\t ", stderr);
--- 136,144 ----
print_node_brief (stderr, "\t", sym, 0);
fputc ('\n', stderr);
! for (i = VARREF_LIST_FIRST (TREE_REFS (sym));
! i;
! i = VARREF_NODE_NEXT (i))
{
varref ref = VARREF_NODE_ELEM (i);
fputs ("\t ", stderr);
*************** tree_find_varrefs (t, parent_stmt)
*** 130,212 ****
}
#endif
}
-
/* }}} */
! /* {{{ find_refs()
! Callback for walk_stmt_tree(). */
! static tree
! find_refs (tp, walk_subtrees, data)
! tree *tp;
! int *walk_subtrees ATTRIBUTE_UNUSED;
! void *data;
{
enum tree_code code;
- tree t = *tp;
- /* If T is contained within another tree, then use the parent tree
- when calling find_refs_in_expr(). This is needed so that we can
- obtain the basic block associated with T. This information is
- stored in T's parent statement. */
- tree parent_stmt = (data) ? (tree)data : t;
-
if (t == NULL)
! return NULL_TREE;
code = TREE_CODE (t);
if (code == EXPR_STMT)
! find_refs_in_expr (EXPR_STMT_EXPR (t), VARUSE, parent_stmt, parent_stmt);
else if (code == IF_STMT)
! find_refs_in_expr (IF_COND (t), VARUSE, parent_stmt, parent_stmt);
else if (code == SWITCH_STMT)
! find_refs_in_expr (SWITCH_COND (t), VARUSE, parent_stmt, parent_stmt);
else if (code == FOR_STMT)
{
! find_refs_in_expr (FOR_COND (t), VARUSE, parent_stmt, parent_stmt);
! find_refs_in_expr (FOR_EXPR (t), VARUSE, parent_stmt, parent_stmt);
}
else if (code == WHILE_STMT)
! find_refs_in_expr (WHILE_COND (t), VARUSE, parent_stmt, parent_stmt);
else if (code == DO_STMT)
! find_refs_in_expr (DO_COND (t), VARUSE, parent_stmt, parent_stmt);
else if (code == ASM_STMT)
{
! find_refs_in_expr (ASM_INPUTS (t), VARUSE, parent_stmt, parent_stmt);
! find_refs_in_expr (ASM_OUTPUTS (t), VARDEF, parent_stmt, parent_stmt);
! find_refs_in_expr (ASM_CLOBBERS (t), VARDEF, parent_stmt, parent_stmt);
}
else if (code == RETURN_STMT)
! find_refs_in_expr (RETURN_EXPR (t), VARUSE, parent_stmt, parent_stmt);
else if (code == GOTO_STMT)
! find_refs_in_expr (GOTO_DESTINATION (t), VARUSE, parent_stmt, parent_stmt);
! return NULL_TREE;
}
/* }}} */
/* {{{ find_refs_in_expr()
Recursively scan the expression tree EXPR looking for variable
references. REF_TYPE indicates what type of reference should be created,
! PARENT_STMT and PARENT_EXPR are the statement and expression trees
! containing EXPR. The basic block holding EXPR is the one associated
! with PARENT_STMT. */
static void
! find_refs_in_expr (expr, ref_type, parent_stmt, parent_expr)
tree expr;
enum varref_type ref_type;
tree parent_stmt;
tree parent_expr;
{
--- 150,285 ----
}
#endif
}
/* }}} */
! /* {{{ find_refs_in_stmt()
! Walks T looking for variable references. BB is the basic block that
! contains T. */
! static void
! find_refs_in_stmt (t, bb)
! tree t;
! basic_block bb;
{
enum tree_code code;
if (t == NULL)
! return;
code = TREE_CODE (t);
if (code == EXPR_STMT)
! find_refs_in_expr (EXPR_STMT_EXPR (t), VARUSE, bb, t, t);
else if (code == IF_STMT)
! find_refs_in_expr (IF_COND (t), VARUSE, bb, t, t);
else if (code == SWITCH_STMT)
! find_refs_in_expr (SWITCH_COND (t), VARUSE, bb, t, t);
else if (code == FOR_STMT)
{
! find_refs_in_stmt (FOR_INIT_STMT (t), bb);
! find_refs_in_expr (FOR_COND (t), VARUSE, bb, t, t);
! find_refs_in_expr (FOR_EXPR (t), VARUSE, bb, t, t);
}
else if (code == WHILE_STMT)
! find_refs_in_expr (WHILE_COND (t), VARUSE, bb, t, t);
else if (code == DO_STMT)
! find_refs_in_expr (DO_COND (t), VARUSE, bb, t, t);
else if (code == ASM_STMT)
{
! find_refs_in_expr (ASM_INPUTS (t), VARUSE, bb, t, t);
! find_refs_in_expr (ASM_OUTPUTS (t), VARDEF, bb, t, t);
! find_refs_in_expr (ASM_CLOBBERS (t), VARDEF, bb, t, t);
}
else if (code == RETURN_STMT)
! find_refs_in_expr (RETURN_EXPR (t), VARUSE, bb, t, t);
else if (code == GOTO_STMT)
! find_refs_in_expr (GOTO_DESTINATION (t), VARUSE, bb, t, t);
! else if (code == DECL_STMT)
! {
! if (TREE_CODE (DECL_STMT_DECL (t)) == VAR_DECL)
! find_refs_in_expr (DECL_INITIAL (DECL_STMT_DECL (t)), VARDEF, bb, t, t);
! }
!
! else if (code == LABEL_STMT)
! find_refs_in_expr (LABEL_STMT_LABEL (t), VARUSE, bb, t, t);
!
! else if (code == CONTINUE_STMT)
! ; /* Nothing to do. */
!
! else if (code == CASE_LABEL)
! ; /* Nothing to do. */
!
! else if (code == BREAK_STMT)
! ; /* Nothing to do. */
!
! else if (code == COMPOUND_STMT)
! /* FIXME - This is needed for C/C++ statement-expressions. These
! should have their own subgraphs. We are now considering
! all these references as if they have been made inside bb. */
! walk_stmt_tree (&t, find_refs_in_stmt_expr, (void *)bb);
!
! else if (code == SCOPE_STMT)
! ; /* Nothing to do. FIXME - This should not be needed. See the note
! for code == COMPOUND_STMT. */
!
! else
! {
! prep_stmt (t);
! error ("Unhandled expression in find_refs_in_stmt():");
! fprintf (stderr, "\n");
! tree_debug_bb (bb);
! fprintf (stderr, "\n");
! debug_tree (t);
! fprintf (stderr, "\n");
! abort();
! }
}
+
+ /* Temporary hack. This should not be needed once we lower statement
+ expressions and treat them as proper sub-graphs of the main CFG. */
+
+ static tree find_refs_in_stmt_expr (tp, walk_subtrees, data)
+ tree *tp;
+ int *walk_subtrees ATTRIBUTE_UNUSED;
+ void *data;
+ {
+ basic_block bb = (basic_block) data;
+ tree t = *tp;
+
+ if (t == NULL)
+ return NULL;
+
+ if (TREE_CODE (t) == COMPOUND_STMT)
+ find_refs_in_stmt (COMPOUND_BODY (t), bb);
+ else
+ find_refs_in_stmt (t, bb);
+
+ return NULL;
+ }
/* }}} */
/* {{{ find_refs_in_expr()
Recursively scan the expression tree EXPR looking for variable
references. REF_TYPE indicates what type of reference should be created,
! BB, PARENT_STMT and PARENT_EXPR are the block, statement and expression
! trees containing EXPR. */
static void
! find_refs_in_expr (expr, ref_type, bb, parent_stmt, parent_expr)
tree expr;
enum varref_type ref_type;
+ basic_block bb;
tree parent_stmt;
tree parent_expr;
{
*************** find_refs_in_expr (expr, ref_type, paren
*** 222,229 ****
|| code == PARM_DECL
|| code == FIELD_DECL)
{
! varref ref = create_varref (expr, ref_type, BB_FOR_STMT (parent_stmt),
! parent_stmt, parent_expr);
#ifdef DEBUG_TREE_DFA
if (DEBUG_TREE_DFA (2))
--- 295,301 ----
|| code == PARM_DECL
|| code == FIELD_DECL)
{
! varref ref = create_varref (expr, ref_type, bb, parent_stmt, parent_expr);
#ifdef DEBUG_TREE_DFA
if (DEBUG_TREE_DFA (2))
*************** find_refs_in_expr (expr, ref_type, paren
*** 263,283 ****
case NOP_EXPR:
case REALPART_EXPR:
case REFERENCE_EXPR:
! find_refs_in_expr (TREE_OPERAND (expr, 0), VARUSE, parent_stmt, expr);
break;
case BIT_NOT_EXPR:
case TRUTH_NOT_EXPR:
case VA_ARG_EXPR:
! find_refs_in_expr (TREE_OPERAND (expr, 0), VARDEF, parent_stmt, expr);
break;
case POSTDECREMENT_EXPR:
case POSTINCREMENT_EXPR:
case PREDECREMENT_EXPR:
case PREINCREMENT_EXPR:
! find_refs_in_expr (TREE_OPERAND (expr, 0), VARUSE, parent_stmt, expr);
! find_refs_in_expr (TREE_OPERAND (expr, 0), VARDEF, parent_stmt, expr);
break;
--- 335,355 ----
case NOP_EXPR:
case REALPART_EXPR:
case REFERENCE_EXPR:
! find_refs_in_expr (TREE_OPERAND (expr, 0), VARUSE, bb, parent_stmt, expr);
break;
case BIT_NOT_EXPR:
case TRUTH_NOT_EXPR:
case VA_ARG_EXPR:
! find_refs_in_expr (TREE_OPERAND (expr, 0), VARDEF, bb, parent_stmt, expr);
break;
case POSTDECREMENT_EXPR:
case POSTINCREMENT_EXPR:
case PREDECREMENT_EXPR:
case PREINCREMENT_EXPR:
! find_refs_in_expr (TREE_OPERAND (expr, 0), VARUSE, bb, parent_stmt, expr);
! find_refs_in_expr (TREE_OPERAND (expr, 0), VARDEF, bb, parent_stmt, expr);
break;
*************** find_refs_in_expr (expr, ref_type, paren
*** 329,351 ****
case UNLE_EXPR:
case UNLT_EXPR:
case UNORDERED_EXPR:
! find_refs_in_expr (TREE_OPERAND (expr, 0), VARUSE, parent_stmt, expr);
! find_refs_in_expr (TREE_OPERAND (expr, 1), VARUSE, parent_stmt, expr);
break;
case INIT_EXPR:
case MODIFY_EXPR:
! find_refs_in_expr (TREE_OPERAND (expr, 0), VARDEF, parent_stmt, expr);
! find_refs_in_expr (TREE_OPERAND (expr, 1), VARUSE, parent_stmt, expr);
break;
/* Ternary operations. */
case BIT_FIELD_REF:
case SAVE_EXPR:
! find_refs_in_expr (TREE_OPERAND (expr, 0), VARUSE, parent_stmt, expr);
! find_refs_in_expr (TREE_OPERAND (expr, 1), VARUSE, parent_stmt, expr);
! find_refs_in_expr (TREE_OPERAND (expr, 2), VARUSE, parent_stmt, expr);
break;
/* N-ary operations. */
--- 401,423 ----
case UNLE_EXPR:
case UNLT_EXPR:
case UNORDERED_EXPR:
! find_refs_in_expr (TREE_OPERAND (expr, 0), VARUSE, bb, parent_stmt, expr);
! find_refs_in_expr (TREE_OPERAND (expr, 1), VARUSE, bb, parent_stmt, expr);
break;
case INIT_EXPR:
case MODIFY_EXPR:
! find_refs_in_expr (TREE_OPERAND (expr, 1), VARUSE, bb, parent_stmt, expr);
! find_refs_in_expr (TREE_OPERAND (expr, 0), VARDEF, bb, parent_stmt, expr);
break;
/* Ternary operations. */
case BIT_FIELD_REF:
case SAVE_EXPR:
! find_refs_in_expr (TREE_OPERAND (expr, 0), VARUSE, bb, parent_stmt, expr);
! find_refs_in_expr (TREE_OPERAND (expr, 1), VARUSE, bb, parent_stmt, expr);
! find_refs_in_expr (TREE_OPERAND (expr, 2), VARUSE, bb, parent_stmt, expr);
break;
/* N-ary operations. */
*************** find_refs_in_expr (expr, ref_type, paren
*** 353,361 ****
{
tree op;
! find_refs_in_expr (TREE_OPERAND (expr, 0), VARUSE, parent_stmt, expr);
for (op = TREE_OPERAND (expr, 1); op; op = TREE_CHAIN (op))
! find_refs_in_expr (TREE_VALUE (op), VARUSE, parent_stmt, expr);
break;
}
--- 425,433 ----
{
tree op;
! find_refs_in_expr (TREE_OPERAND (expr, 0), VARUSE, bb, parent_stmt, expr);
for (op = TREE_OPERAND (expr, 1); op; op = TREE_CHAIN (op))
! find_refs_in_expr (TREE_VALUE (op), VARUSE, bb, parent_stmt, expr);
break;
}
*************** find_refs_in_expr (expr, ref_type, paren
*** 364,377 ****
tree op;
for (op = expr; op; op = TREE_CHAIN (op))
! find_refs_in_expr (TREE_VALUE (op), ref_type, parent_stmt, expr);
break;
}
/* C/C++ statement-expressions. */
case STMT_EXPR:
! tree_find_varrefs (STMT_EXPR_STMT (expr), parent_stmt);
break;
default:
--- 436,449 ----
tree op;
for (op = expr; op; op = TREE_CHAIN (op))
! find_refs_in_expr (TREE_VALUE (op), ref_type, bb, parent_stmt, expr);
break;
}
/* C/C++ statement-expressions. */
case STMT_EXPR:
! find_refs_in_stmt (STMT_EXPR_STMT (expr), bb);
break;
default:
*************** create_varref (sym, ref_type, bb, parent
*** 409,427 ****
int is_new;
if (bb == NULL)
! {
! fputs ("Cannot determine basic block for variable reference:\n", stderr);
! debug_tree (sym);
!
! fputs ("\n\nReference made in expression:\n", stderr);
! debug_tree (parent_expr);
!
! fputs ("\n\nWhich is inside statement:\n", stderr);
! debug_tree (parent_stmt);
!
! fputs ("\n", stderr);
! abort ();
! }
ref = (varref) ggc_alloc (sizeof (*ref));
memset ((void *)ref, 0, sizeof (*ref));
--- 481,487 ----
int is_new;
if (bb == NULL)
! abort ();
ref = (varref) ggc_alloc (sizeof (*ref));
memset ((void *)ref, 0, sizeof (*ref));
*************** add_ref_to_sym (ref, sym, is_new)
*** 479,485 ****
get_tree_ann (sym)->refs = create_varref_list (ref);
}
}
-
/* }}} */
/* {{{ add_ref_to_bb()
--- 539,544 ----
*************** add_ref_symbol (sym, listp)
*** 531,537 ****
return is_new;
}
-
/* }}} */
/* {{{ remove_ann_from_sym()
--- 590,595 ----
*************** delete_varref_list (symlist_p)
*** 673,679 ****
*symlist_p = NULL;
}
-
/* }}} */
--- 731,736 ----
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.2.2
diff -d -p -d -c -p -r1.1.2.2 tree-flow.h
*** tree-flow.h 2001/08/01 05:36:58 1.1.2.2
--- tree-flow.h 2001/08/11 00:01:06
*************** struct varphi
*** 101,107 ****
/* }}} */
-
/* {{{ Generic variable reference structure. */
union varref_def
--- 101,106 ----
*************** struct varref_list_def
*** 148,154 ****
typedef struct varref_list_def *varref_list;
-
#define VARREF_LIST_FIRST(l) ((l) ? (l)->first : NULL)
#define VARREF_LIST_LAST(l) ((l) ? (l)->last : NULL)
--- 147,152 ----
*************** struct tree_ann_def
*** 164,172 ****
/* For _DECL trees, list of references made to this variable. */
varref_list refs;
! /* Most recent definition for this symbol. Used when placing FUD
chains. */
varref currdef;
};
typedef struct tree_ann_def *tree_ann;
--- 162,173 ----
/* For _DECL trees, list of references made to this variable. */
varref_list refs;
! /* Most recent definition for this symbol. Used when placing FUD
chains. */
varref currdef;
+
+ /* Immediately enclosing compound statement to which this tree belongs. */
+ tree compound_stmt;
};
typedef struct tree_ann_def *tree_ann;
*************** typedef struct tree_ann_def *tree_ann;
*** 183,188 ****
--- 184,192 ----
#define TREE_REFS(NODE) \
((TREE_ANN (NODE)) ? TREE_ANN (NODE)->refs : NULL)
+ #define TREE_COMPOUND_STMT(NODE)\
+ ((TREE_ANN (NODE)) ? TREE_ANN (NODE)->compound_stmt : NULL)
+
/* }}} */
/* {{{ Block annotations stored in basic_block.aux. */
*************** struct basic_block_ann_def
*** 194,225 ****
/* List of references made in this block. */
varref_list refs;
-
- /* Control flow altering statement found in the block (CONTINUE, BREAK
- RETURN, or GOTO). NOTE: there can be only one. */
- tree exit_stmt;
-
- /* Loop header flag. If set, this block belongs to the head of a loop
- construct (e.g., the block for a FOR_COND expression). */
- int is_loop_header;
};
typedef struct basic_block_ann_def *basic_block_ann;
! #define BB_ANN(NODE) \
! ((basic_block_ann)((NODE)->aux))
!
! #define BB_PARENT(NODE) \
! ((BB_ANN (NODE)) ? BB_ANN (NODE)->parent : NULL)
!
! #define BB_REFS(NODE) \
! ((BB_ANN (NODE)) ? BB_ANN (NODE)->refs : NULL)
! #define BB_EXIT_STMT(NODE) \
! ((BB_ANN (NODE)) ? BB_ANN (NODE)->exit_stmt : NULL)
! #define BB_IS_LOOP_HEADER(NODE) \
! ((BB_ANN (NODE)) ? BB_ANN (NODE)->is_loop_header : 0)
/* }}} */
--- 198,215 ----
/* List of references made in this block. */
varref_list refs;
};
typedef struct basic_block_ann_def *basic_block_ann;
! #define BB_ANN(BLOCK) \
! ((basic_block_ann)((BLOCK)->aux))
! #define BB_PARENT(BLOCK) \
! ((BB_ANN (BLOCK)) ? BB_ANN (BLOCK)->parent : NULL)
! #define BB_REFS(BLOCK) \
! ((BB_ANN (BLOCK)) ? BB_ANN (BLOCK)->refs : NULL)
/* }}} */
*************** extern void tree_dump_bb PARAMS ((FILE *
*** 251,264 ****
extern void tree_debug_bb PARAMS ((basic_block));
extern void tree_debug_cfg PARAMS ((void));
extern void tree_cfg2dot PARAMS ((char *fname));
! extern basic_block find_loop_parent PARAMS ((basic_block));
! extern basic_block get_condition_block PARAMS ((basic_block));
/* }}} */
/* {{{ Functions in tree-dfa.c */
! extern void tree_find_varrefs PARAMS ((tree, tree));
extern void add_ref_to_sym PARAMS ((varref, tree sym, int));
extern void add_ref_to_bb PARAMS ((varref, basic_block));
extern int add_ref_symbol PARAMS ((tree, tree *));
--- 241,257 ----
extern void tree_debug_bb PARAMS ((basic_block));
extern void tree_debug_cfg PARAMS ((void));
extern void tree_cfg2dot PARAMS ((char *fname));
! extern basic_block loop_parent PARAMS ((basic_block));
! extern basic_block condition_block PARAMS ((basic_block));
! extern basic_block switch_parent PARAMS ((basic_block));
! extern tree first_exec_stmt PARAMS ((tree));
! extern int is_exec_stmt PARAMS ((tree));
/* }}} */
/* {{{ Functions in tree-dfa.c */
! extern void tree_find_varrefs PARAMS ((void));
extern void add_ref_to_sym PARAMS ((varref, tree sym, int));
extern void add_ref_to_bb PARAMS ((varref, basic_block));
extern int add_ref_symbol PARAMS ((tree, tree *));
Index: tree-opt.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-opt.c,v
retrieving revision 1.1.2.2
diff -d -p -d -c -p -r1.1.2.2 tree-opt.c
*** tree-opt.c 2001/08/01 05:36:59 1.1.2.2
--- tree-opt.c 2001/08/11 00:01:06
*************** optimize_tree (t)
*** 47,57 ****
tree_find_basic_blocks (t, 0, 0);
/* Don't bother doing anything else if we found errors in the program. */
! if (errorcount)
return;
! tree_find_varrefs (t, NULL);
! tree_build_ssa ();
/* Flush out DFA and SSA data. */
delete_varref_list (&ref_symbols_list);
--- 47,60 ----
tree_find_basic_blocks (t, 0, 0);
/* Don't bother doing anything else if we found errors in the program. */
! if (errorcount > 0)
return;
! if (n_basic_blocks > 0)
! {
! tree_find_varrefs ();
! tree_build_ssa ();
! }
/* Flush out DFA and SSA data. */
delete_varref_list (&ref_symbols_list);
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.2.2
diff -d -p -d -c -p -r1.1.2.2 tree-ssa.c
*** tree-ssa.c 2001/08/01 05:36:59 1.1.2.2
--- tree-ssa.c 2001/08/11 00:01:06
*************** tree_build_ssa ()
*** 127,133 ****
}
#endif
! /* Insert the phi nodes and build FUD chains. */
insert_phi_terms (dfs);
build_fud_chains (idom);
--- 127,133 ----
}
#endif
! /* Insert the PHI nodes and build FUD chains. */
insert_phi_terms (dfs);
build_fud_chains (idom);
*************** insert_phi_terms (dfs)
*** 174,197 ****
/* Array ADDED (indexed by basic block number) is used to determine
whether a phi term for the current variable has already been
! inserted at node X. */
VARRAY_TREE_INIT (added, n_basic_blocks, "added");
/* Array IN_WORK (indexed by basic block number) is used to determine
! whether node X has already been added to WORK_LIST for the current
variable. */
VARRAY_TREE_INIT (in_work, n_basic_blocks, "in_work");
! /* Array WORK_LIST is a stack of CFG nodes. Each node that contains
! an assignment or phi term will be added to this work list. */
VARRAY_BB_INIT (work_list, n_basic_blocks, "work_list");
work_list_top = 0;
/* Iterate over all referenced symbols in the function. For each
! symbol, add to the work list all the nodes that have a definition
for the symbol. PHI terms will be added to the dominance frontier
! nodes of each definition node. */
for (m = ref_symbols_list; m; m = TREE_CHAIN (m))
{
--- 174,197 ----
/* Array ADDED (indexed by basic block number) is used to determine
whether a phi term for the current variable has already been
! inserted at block X. */
VARRAY_TREE_INIT (added, n_basic_blocks, "added");
/* Array IN_WORK (indexed by basic block number) is used to determine
! whether block X has already been added to WORK_LIST for the current
variable. */
VARRAY_TREE_INIT (in_work, n_basic_blocks, "in_work");
! /* Array WORK_LIST is a stack of CFG blocks. Each block that contains
! an assignment or PHI term will be added to this work list. */
VARRAY_BB_INIT (work_list, n_basic_blocks, "work_list");
work_list_top = 0;
/* Iterate over all referenced symbols in the function. For each
! symbol, add to the work list all the blocks that have a definition
for the symbol. PHI terms will be added to the dominance frontier
! blocks of each definition block. */
for (m = ref_symbols_list; m; m = TREE_CHAIN (m))
{
*************** insert_phi_terms (dfs)
*** 204,233 ****
for (i = VARREF_LIST_FIRST (TREE_REFS (sym)); i; i = VARREF_NODE_NEXT (i))
{
! basic_block node;
varref ref = VARREF_NODE_ELEM (i);
if (VARREF_TYPE (ref) != VARDEF)
continue;
! node = VARREF_BLOCK (ref);
/* Grow WORK_LIST by ~25%. */
if (work_list_top >= VARRAY_SIZE (work_list))
VARRAY_GROW (work_list, work_list_top + (work_list_top + 3) / 4);
! VARRAY_BB (work_list, work_list_top) = node;
work_list_top++;
! VARRAY_TREE (in_work, node->index) = sym;
}
while (work_list_top > 0)
{
int w;
! basic_block node;
work_list_top--;
! node = VARRAY_BB (work_list, work_list_top);
! EXECUTE_IF_SET_IN_SBITMAP (dfs[node->index], 0, w,
{
if (VARRAY_TREE (added, w) != sym)
{
--- 204,233 ----
for (i = VARREF_LIST_FIRST (TREE_REFS (sym)); i; i = VARREF_NODE_NEXT (i))
{
! basic_block bb;
varref ref = VARREF_NODE_ELEM (i);
if (VARREF_TYPE (ref) != VARDEF)
continue;
! bb = VARREF_BLOCK (ref);
/* Grow WORK_LIST by ~25%. */
if (work_list_top >= VARRAY_SIZE (work_list))
VARRAY_GROW (work_list, work_list_top + (work_list_top + 3) / 4);
! VARRAY_BB (work_list, work_list_top) = bb;
work_list_top++;
! VARRAY_TREE (in_work, bb->index) = sym;
}
while (work_list_top > 0)
{
int w;
! basic_block bb;
work_list_top--;
! bb = VARRAY_BB (work_list, work_list_top);
! EXECUTE_IF_SET_IN_SBITMAP (dfs[bb->index], 0, w,
{
if (VARRAY_TREE (added, w) != sym)
{