This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[ast-optimizer-branch] Reaching definitions and code generation [patch]
- To: gcc-patches at gcc dot gnu dot org
- Subject: [ast-optimizer-branch] Reaching definitions and code generation [patch]
- From: Diego Novillo <dnovillo at redhat dot com>
- Date: Sun, 30 Sep 2001 02:52:01 -0400
- Organization: Red Hat Canada
This patch adds a couple more SSA-based analyses and initial support
for inserting and replacing code:
- Reaching definitions and reached uses.
- Flow-sensitive insertion and replacement of tree nodes.
- Warnings for use of uninitialized variables.
The code has been tested with a transformation we're developing
internally. It successfully bootstraps with the transformation
enabled.
Bootstrapped and regression tested on x86. Committed to the AST
branch.
Diego.
2001-09-29 Diego Novillo <dnovillo@redhat.com>
* Makefile.in (tree-ssa.o): Update dependencies.
(tree-cfg.o): Ditto.
(tree-optimize.o): Ditto.
* basic-block.h (BB_CONTROL_EXPR): Define.
(BB_CONTROL_ENTRY): Define.
* c-common.h (TDF_RDEFS): Define.
* c-dump.c (dump_option_value_in): Add entry for TDF_RDEFS.
* tree-cfg.c: Include flags.h and c-tree.h
(binding_stack): New local variable.
(delete_block): Rename to delete_bb.
(tree_find_basic_blocks): Initialize varray 'binding_stack'.
Call make_blocks with an additional argument.
Adjust size of varray 'basic_block_info' after building CFG.
(make_blocks): Add new argument prev_chain_p.
Update all callers and callees.
Create sub-graphs for statement-expressions.
Update prev_chain_p when accessing the next tree in the chain.
(make_for_stmt_blocks): Add new argument prev_chain_p.
Update all callers and callees.
Update flags for control header blocks with BB_CONTROL_ENTRY and/or
BB_CONTROL_EXPR.
(make_while_stmt_blocks): Ditto.
(make_do_stmt_blocks): Ditto.
(make_if_stmt_blocks): Ditto.
(make_switch_stmt_blocks): Ditto.
(create_maximal_bb): Add new argument prev_chain_p.
Update all callers and callees.
(create_bb): Add new argument prev_chain_p.
Push basic block 0 the first time into the binding scope stack.
Associate the new basic block to the binding scope at the top of
the binding stack.
Push new binding scopes when a SCOPE_BEGIN statement is found.
Pop the top binding scope when a SCOPE_END statement is found.
(make_edges): Handle statement expressions.
Handle case labels preceded by scope statements in switch
statements.
(make_for_stmt_edges): Use FOR_INIT_STMT_BB, FOR_COND_BB and
FOR_EXPR_BB to access the header basic blocks.
(delete_unreachable_blocks): Call delete_bb instead of
delete_block.
(delete_block): Rename to delete_bb.
(block_invalidates_loop): Use data references to find calls to
non-pure functions.
(is_ctrl_stmt): Reformat.
(loop_body): New function.
(set_loop_body): New function.
(stmt_starts_bb_p): Statement expression trees also start a new
basic block.
(delete_cfg): Call VARRAY_FREE to delete all the references in each
basic block.
(latch_block): Use FOR_EXPR_BB, WHILE_COND_BB and DO_COND_BB to
find out the latch block for the loop.
(last_exec_stmt): New function.
(is_exec_stmt): Scope statements that begin a scope are also
considered executables.
(is_statement_expression): New function.
(first_non_decl_stmt): New function.
(first_decl_stmt): New function.
(first_non_label_in_bb): New function.
(insert_stmt_tree_before): New function.
(insert_before_ctrl_stmt): New function.
(insert_before_normal_stmt): New function.
(insert_stmt_tree_after): New function.
(insert_after_ctrl_stmt): New function.
(insert_after_normal_stmt): New function.
(insert_after_loop_body): New function.
(replace_expr_in_tree): New function.
(find_expr_in_tree): New function.
(insert_bb_before): New function.
(tree_dump_bb): Display the contents of BB_PREV_CHAIN_P.
* tree-dfa.c (tree_find_varrefs): Use accessor macros for array
'referenced_symbols'.
(find_refs_in_stmt): Do not process error_mark_node trees.
Handle statement-expression nodes as any other statement tree.
Do not call find_refs_in_stmt_expr.
(find_refs_in_stmt_expr): Remove.
(add_ref_to_sym): Remove.
(add_ref_to_bb): Remove.
(find_refs_in_expr): Do not process error_mark_node trees.
ADDR_EXPR trees are not variable references except if used in a
CALL_EXPR node.
Handle EXPR_WITH_FILE_LOCATION nodes.
(create_varref): Remove variable 'is_new'.
Initialize data-flow arrays VARDEF_IMM_USES, VARDEF_RUSES,
VARDEF_PHI_CHAIN and VARUSE_RDEFS.
Do not call add_ref_to_sym and add_ref_to_bb.
(add_ref_symbol): Use accessor macros for varray
'referenced_symbols'.
(function_may_recurse_p): New function.
(get_fcalls): New function.
(find_declaration): New function.
(dump_varref): Handle NULL values of VARREF_EXPR.
Use VARDEF_PHI_CHAIN instead of VARPHI_CHAIN.
(dump_varref_list): Check if the list is NULL before traversing it.
* tree-flow.h (struct vardef): Add fields 'ruses', 'marked' and
'phi_chain'.
(VARDEF_RUSES): Define.
(VARDEF_MARKED): Define.
(VARDEF_PHI_CHAIN): Define.
(VARPHI_CHAIN): Remove.
(struct varphi): Remove.
(struct varuse): Add field 'rdefs'.
(VARUSE_RDEFS): Define.
(union varref_def): Remove field 'phi'.
(IS_GHOST_DEF): Define.
(IS_ARTIFICIAL_REF): Define.
(struct bb_ann_def): Add fields 'prev_chain_p' and 'binding_scope'.
(BB_PREV_CHAIN_P): Define.
(BB_BINDING_SCOPE): Define.
(FOR_INIT_STMT_BB): Define.
(FOR_COND_BB): Define.
(FOR_EXPR_BB): Define.
(WHILE_COND_BB): Define.
(DO_COND_BB): Define.
(IF_COND_BB): Define.
(CASE_COND_BB): Define.
(NREF_SYMBOLS): Define.
(REF_SYMBOL): Define.
(ADD_REF_SYMBOL): Define.
(FCALL_NON_PURE): Define.
(FCALL_PURE): Define.
(FCALL_BUILT_IN): Define.
(loop_body): Declare.
(set_loop_body): Declare.
(last_exec_stmt): Declare.
(is_statement_expression): Declare.
(first_non_decl_stmt): Declare.
(first_decl_stmt): Declare.
(first_non_label_in_bb): Declare.
(insert_stmt_tree_before): Declare.
(insert_stmt_tree_after): Declare.
(replace_expr_in_tree): Declare.
(find_expr_in_tree): Declare.
(insert_bb_before): Declare.
(function_may_recurse_p): Declare.
(get_fcalls): Declare.
(find_declaration): Declare.
(tree_compute_rdefs): Declare.
(analyze_rdefs): Declare.
(is_upward_exposed): Declare.
* tree-optimize.c (optimize_tree): Update name for varray
referenced_symbols.
Free varray referenced_symbols and call delete_ssa on exit.
* tree-ssa.c: Include flags.h, diagnostic.h and toplev.h.
(tree_build_ssa): Create ghost definitions before building FUD
chains.
(insert_phi_terms): Use accessor macros for 'referenced_symbols'.
Ignore ghost definitions when placing PHI terms.
(build_fud_chains): Call get_tree_ann to create an annotation for
the symbol if it doesn't already have one.
(search_fud_chains): Reformat comments.
Do not initialize varray VARDEF_IMM_USES.
If a successor basic block does not have references, continue on to
the next one, do not stop.
Do not initialize varray VARDEF_PHI_CHAIN.
(delete_ssa): New function.
(delete_refs): New function.
(tree_compute_rdefs): New function.
(analyze_rdefs): New function.
(follow_chain): New function.
(is_upward_exposed): New function.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.701.2.4
diff -d -p -d -u -p -r1.701.2.4 Makefile.in
--- Makefile.in 2001/08/27 16:48:21 1.701.2.4
+++ Makefile.in 2001/09/30 06:11:05
@@ -1335,16 +1335,16 @@ tree.o : tree.c $(CONFIG_H) $(SYSTEM_H)
tree-ssa.o : tree-ssa.c tree-optimize.h tree-flow.h $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(BASIC_BLOCK_H) $(EXPR_H) $(C_COMMON_H) \
- $(GGC_H) output.h diagnostic.h ssa.h errors.h
+ $(GGC_H) flags.h output.h diagnostic.h ssa.h errors.h toplev.h
tree-cfg.o : tree-cfg.c tree-optimize.h tree-flow.h $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(BASIC_BLOCK_H) $(EXPR_H) $(C_COMMON_H) \
- $(GGC_H) output.h diagnostic.h errors.h
+ $(GGC_H) flags.h output.h diagnostic.h errors.h
tree-dfa.o : tree-dfa.c tree-optimize.h tree-flow.h $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(BASIC_BLOCK_H) $(EXPR_H) $(C_COMMON_H) \
$(GGC_H) output.h diagnostic.h errors.h
tree-optimize.o : tree-optimize.c tree-optimize.h tree-flow.h $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(BASIC_BLOCK_H) $(EXPR_H) \
- $(C_COMMON_H) output.h diagnostic.h errors.h
+ $(C_COMMON_H) $(GGC_H) output.h diagnostic.h ssa.h errors.h
print-tree.o : print-tree.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) $(GGC_H)
stor-layout.o : stor-layout.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) flags.h \
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.102.2.2
diff -d -p -d -u -p -r1.102.2.2 basic-block.h
--- basic-block.h 2001/08/20 15:23:51 1.102.2.2
+++ basic-block.h 2001/09/30 06:11:05
@@ -225,7 +225,18 @@ typedef struct basic_block_def {
#define BB_FREQ_MAX 10000
/* Masks for basic_block.flags. */
+
+/* Block is reachable. */
+
#define BB_REACHABLE 1
+
+/* Block contains a control flow expression. */
+
+#define BB_CONTROL_EXPR 2
+
+/* Block is the entry block to a control statement but contains no code. */
+
+#define BB_CONTROL_ENTRY 4
/* Number of basic blocks in the current function. */
Index: c-common.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/c-common.h,v
retrieving revision 1.79.2.2
diff -d -p -d -u -p -r1.79.2.2 c-common.h
--- c-common.h 2001/09/04 11:50:46 1.79.2.2
+++ c-common.h 2001/09/30 06:11:05
@@ -863,6 +863,7 @@ enum tree_dump_index
#define TDF_ADDRESS (1 << 0) /* dump node addresses */
#define TDF_SLIM (1 << 1) /* don't go wild following links */
#define TDF_REFS (1 << 0) /* dump ssa variable refs */
+#define TDF_RDEFS (1 << 1) /* dump reaching definitions */
typedef struct dump_info *dump_info_p;
Index: c-dump.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/c-dump.c,v
retrieving revision 1.5.2.2
diff -d -p -d -u -p -r1.5.2.2 c-dump.c
--- c-dump.c 2001/09/04 11:50:46 1.5.2.2
+++ c-dump.c 2001/09/30 06:11:05
@@ -823,6 +823,7 @@ static const struct dump_option_value_in
{"address", TDF_ADDRESS},
{"slim", TDF_SLIM},
{"refs", TDF_REFS},
+ {"rdefs", TDF_RDEFS},
{"all", ~0},
{NULL, 0}
};
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.2.7
diff -d -p -d -u -p -r1.1.2.7 tree-cfg.c
--- tree-cfg.c 2001/09/14 05:12:56 1.1.2.7
+++ tree-cfg.c 2001/09/30 06:11:05
@@ -28,19 +28,23 @@ Boston, MA 02111-1307, USA. */
#include "basic-block.h"
#include "output.h"
#include "errors.h"
+#include "flags.h"
#include "expr.h"
#include "c-common.h"
+#include "c-tree.h"
#include "ggc.h"
#include "diagnostic.h"
#include "tree-optimize.h"
#include "tree-flow.h"
-/* {{{ Local declarations. */
+/* Local declarations. */
/* Initial capacity for the basic block array. */
-
static const int initial_cfg_capacity = 20;
+/* Stack of binding scopes. */
+static varray_type binding_stack;
+
/* Dump files and flags. */
static FILE *cfg_dump_file;
static FILE *dot_dump_file;
@@ -48,17 +52,17 @@ static int cfg_dump_flags;
static int dot_dump_flags;
/* 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 make_blocks PARAMS ((tree, basic_block, tree, tree *));
+static void make_for_stmt_blocks PARAMS ((tree, basic_block, tree, tree *));
+static void make_if_stmt_blocks PARAMS ((tree, basic_block, tree, tree *));
+static void make_while_stmt_blocks PARAMS ((tree, basic_block, tree, tree *));
+static void make_switch_stmt_blocks PARAMS ((tree, basic_block, tree, tree *));
+static void make_do_stmt_blocks PARAMS ((tree, basic_block, tree, tree *));
+static basic_block create_bb PARAMS ((tree, tree, basic_block, tree *));
+static basic_block create_maximal_bb PARAMS ((tree, basic_block, tree, 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));
+static void delete_bb PARAMS ((basic_block));
/* Edges. */
static void make_edges PARAMS ((void));
@@ -78,8 +82,11 @@ static basic_block successor_block PARAM
static int block_invalidates_loop PARAMS ((basic_block, struct loop *));
static void create_bb_ann PARAMS ((basic_block));
-/* }}} */
-
+static void insert_before_ctrl_stmt PARAMS ((tree, tree, basic_block));
+static void insert_before_normal_stmt PARAMS ((tree, tree, basic_block));
+static void insert_after_ctrl_stmt PARAMS ((tree, tree, basic_block));
+static void insert_after_normal_stmt PARAMS ((tree, tree, basic_block));
+static void insert_after_loop_body PARAMS ((tree, basic_block));
/* Create basic blocks. */
@@ -101,11 +108,17 @@ tree_find_basic_blocks (t)
n_basic_blocks = 0;
VARRAY_BB_INIT (basic_block_info, initial_cfg_capacity, "basic_block_info");
+ /* Initialize the stack of binding scopes. */
+ VARRAY_BB_INIT (binding_stack, 5, "binding_stack");
+
/* Find the basic blocks for the flowgraph. */
- make_blocks (t, NULL, NULL);
+ make_blocks (t, NULL, NULL, NULL);
if (n_basic_blocks > 0)
{
+ /* Adjust the size of the array. */
+ VARRAY_GROW (basic_block_info, n_basic_blocks);
+
/* Create the edges of the flowgraph. */
make_edges ();
@@ -132,21 +145,26 @@ tree_find_basic_blocks (t)
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.
-
+ 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().
+ belongs. These statements are not represented in the flowgraph, but
+ are important to determine successor basic blocks in successor_block().
+
+ PREV_CHAIN_P is the address into the tree preceeding T that contains a
+ pointer to T. This is used when we need to insert statements before
+ the first tree of the block.
When creating basic blocks one important property should be maintained:
It must be possible to traverse all the trees inside a basic block by
following the TREE_CHAIN from bb->head_tree. */
static void
-make_blocks (t, control_parent, compound_stmt)
+make_blocks (t, control_parent, compound_stmt, prev_chain_p)
tree t;
basic_block control_parent;
tree compound_stmt;
+ tree *prev_chain_p;
{
/* Traverse the statement chain building basic blocks. */
while (t && t != error_mark_node)
@@ -156,41 +174,58 @@ make_blocks (t, control_parent, compound
switch (TREE_CODE (t))
{
case COMPOUND_STMT:
- make_blocks (COMPOUND_BODY (t), control_parent, t);
+ make_blocks (COMPOUND_BODY (t), control_parent, t,
+ &(COMPOUND_BODY (t)));
break;
case FOR_STMT:
- make_for_stmt_blocks (t, control_parent, compound_stmt);
+ make_for_stmt_blocks (t, control_parent, compound_stmt,
+ prev_chain_p);
break;
case IF_STMT:
- make_if_stmt_blocks (t, control_parent, compound_stmt);
+ make_if_stmt_blocks (t, control_parent, compound_stmt,
+ prev_chain_p);
break;
case WHILE_STMT:
- make_while_stmt_blocks (t, control_parent, compound_stmt);
+ make_while_stmt_blocks (t, control_parent, compound_stmt,
+ prev_chain_p);
break;
case SWITCH_STMT:
- make_switch_stmt_blocks (t, control_parent, compound_stmt);
+ make_switch_stmt_blocks (t, control_parent, compound_stmt,
+ prev_chain_p);
break;
case DO_STMT:
- make_do_stmt_blocks (t, control_parent, compound_stmt);
+ make_do_stmt_blocks (t, control_parent, compound_stmt,
+ prev_chain_p);
break;
default:
- if (is_exec_stmt (t))
+ if (is_statement_expression (t))
+ {
+ tree expr = TREE_OPERAND (t, 0);
+ basic_block bb = create_bb (t, t, control_parent, prev_chain_p);
+ make_blocks (STMT_EXPR_STMT (expr), bb, t,
+ &(STMT_EXPR_STMT (expr)));
+ }
+ else if (is_exec_stmt (t))
{
basic_block bb;
- bb = create_maximal_bb (t, control_parent, compound_stmt);
+ bb = create_maximal_bb (t, control_parent, compound_stmt,
+ prev_chain_p);
t = bb->end_tree;
}
break;
}
if (t)
- t = TREE_CHAIN (t);
+ {
+ prev_chain_p = &(TREE_CHAIN (t));
+ t = TREE_CHAIN (t);
+ }
}
}
@@ -201,12 +236,13 @@ make_blocks (t, control_parent, compound
Create the blocks for a FOR_STMT. */
static void
-make_for_stmt_blocks (t, control_parent, compound_stmt)
+make_for_stmt_blocks (t, control_parent, compound_stmt, prev_chain_p)
tree t;
basic_block control_parent;
tree compound_stmt;
+ tree *prev_chain_p;
{
- basic_block bb;
+ basic_block entry, bb;
tree expr, cond;
/* Make sure that both condition and expression blocks will be created
@@ -222,11 +258,20 @@ make_for_stmt_blocks (t, control_parent,
cond = (FOR_COND (t)) ? FOR_COND (t) : build_int_2 (1, 0);
expr = (FOR_EXPR (t)) ? FOR_EXPR (t) : build_int_2 (1, 0);
- bb = create_bb (t, t, control_parent);
- create_maximal_bb (FOR_INIT_STMT (t), bb, compound_stmt);
- create_maximal_bb (cond, bb, compound_stmt);
- create_maximal_bb (expr, bb, compound_stmt);
- make_blocks (FOR_BODY (t), bb, compound_stmt);
+ entry = create_bb (t, t, control_parent, prev_chain_p);
+ entry->flags |= BB_CONTROL_ENTRY;
+
+ bb = create_maximal_bb (FOR_INIT_STMT (t), entry, compound_stmt,
+ &(FOR_INIT_STMT (t)));
+ bb->flags |= BB_CONTROL_EXPR;
+
+ bb = create_maximal_bb (cond, entry, compound_stmt, &(FOR_COND (t)));
+ bb->flags |= BB_CONTROL_EXPR;
+
+ bb = create_maximal_bb (expr, entry, compound_stmt, &(FOR_EXPR (t)));
+ bb->flags |= BB_CONTROL_EXPR;
+
+ make_blocks (FOR_BODY (t), entry, compound_stmt, &(FOR_BODY (t)));
}
/* }}} */
@@ -236,18 +281,21 @@ make_for_stmt_blocks (t, control_parent,
Create the blocks for a WHILE_STMT. */
static void
-make_while_stmt_blocks (t, control_parent, compound_stmt)
+make_while_stmt_blocks (t, control_parent, compound_stmt, prev_chain_p)
tree t;
basic_block control_parent;
tree compound_stmt;
+ tree *prev_chain_p;
{
- basic_block bb = create_bb (t, t, control_parent);
+ basic_block bb = create_bb (t, t, control_parent, prev_chain_p);
+ bb->flags |= BB_CONTROL_ENTRY | BB_CONTROL_EXPR;
/* END_WHILE block. Needed to avoid multiple back edges that would
result in multiple natural loops instead of just one. */
- create_maximal_bb (build_int_2 (1, 0), bb, compound_stmt);
+ bb = create_maximal_bb (build_int_2 (1, 0), bb, compound_stmt, NULL);
+ bb->flags |= BB_CONTROL_ENTRY;
- make_blocks (WHILE_BODY (t), bb, compound_stmt);
+ make_blocks (WHILE_BODY (t), bb, compound_stmt, &(WHILE_BODY (t)));
}
/* }}} */
@@ -257,14 +305,19 @@ make_while_stmt_blocks (t, control_paren
Create the blocks for a DO_STMT. */
static void
-make_do_stmt_blocks (t, control_parent, compound_stmt)
+make_do_stmt_blocks (t, control_parent, compound_stmt, prev_chain_p)
tree t;
basic_block control_parent;
tree compound_stmt;
+ tree *prev_chain_p;
{
- 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);
+ basic_block bb = create_bb (t, t, control_parent, prev_chain_p);
+ bb->flags |= BB_CONTROL_ENTRY;
+
+ bb = create_maximal_bb (DO_COND (t), bb, compound_stmt, &(DO_COND (t)));
+ bb->flags |= BB_CONTROL_EXPR;
+
+ make_blocks (DO_BODY (t), bb, compound_stmt, &(DO_BODY (t)));
}
/* }}} */
@@ -274,14 +327,17 @@ make_do_stmt_blocks (t, control_parent,
Create the blocks for an IF_STMT. */
static void
-make_if_stmt_blocks (t, control_parent, compound_stmt)
+make_if_stmt_blocks (t, control_parent, compound_stmt, prev_chain_p)
tree t;
basic_block control_parent;
tree compound_stmt;
+ tree *prev_chain_p;
{
- basic_block bb = create_bb (t, t, control_parent);
- make_blocks (THEN_CLAUSE (t), bb, compound_stmt);
- make_blocks (ELSE_CLAUSE (t), bb, compound_stmt);
+ basic_block bb = create_bb (t, t, control_parent, prev_chain_p);
+ bb->flags |= BB_CONTROL_ENTRY | BB_CONTROL_EXPR;
+
+ make_blocks (THEN_CLAUSE (t), bb, compound_stmt, &(THEN_CLAUSE (t)));
+ make_blocks (ELSE_CLAUSE (t), bb, compound_stmt, &(ELSE_CLAUSE (t)));
}
/* }}} */
@@ -291,13 +347,16 @@ make_if_stmt_blocks (t, control_parent,
Create the blocks for a SWITCH_STMT. */
static void
-make_switch_stmt_blocks (t, control_parent, compound_stmt)
+make_switch_stmt_blocks (t, control_parent, compound_stmt, prev_chain_p)
tree t;
basic_block control_parent;
tree compound_stmt;
+ tree *prev_chain_p;
{
- basic_block bb = create_bb (t, SWITCH_COND (t), control_parent);
- make_blocks (SWITCH_BODY (t), bb, compound_stmt);
+ basic_block bb = create_bb (t, t, control_parent, prev_chain_p);
+ bb->flags |= BB_CONTROL_ENTRY | BB_CONTROL_EXPR;
+
+ make_blocks (SWITCH_BODY (t), bb, compound_stmt, &(SWITCH_BODY (t)));
}
/* }}} */
@@ -318,13 +377,18 @@ make_switch_stmt_blocks (t, control_pare
COMPOUND_STMT is the immediately enclosing compound statement to which
the first tree of the block belongs.
+ PREV_CHAIN_P is the address into the tree preceeding T that contains a
+ pointer to T. This is used when we need to insert statements before
+ the first tree of the block.
+
Returns the new basic block. */
static basic_block
-create_maximal_bb (t, control_parent, compound_stmt)
+create_maximal_bb (t, control_parent, compound_stmt, prev_chain_p)
tree t;
basic_block control_parent;
tree compound_stmt;
+ tree *prev_chain_p;
{
tree first, last;
basic_block bb;
@@ -333,7 +397,7 @@ create_maximal_bb (t, control_parent, co
return NULL;
first = last = t;
- bb = create_bb (first, last, control_parent);
+ bb = create_bb (first, last, control_parent, prev_chain_p);
while (last && last != error_mark_node)
{
@@ -362,13 +426,18 @@ create_maximal_bb (t, control_parent, co
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. */
+ the new block.
+
+ PREV_CHAIN_P is the address into the tree preceeding T that contains a
+ pointer to T. This is used when we need to insert statements before
+ the first tree of the block. */
static basic_block
-create_bb (head, end, control_parent)
+create_bb (head, end, control_parent, prev_chain_p)
tree head;
tree end;
basic_block control_parent;
+ tree *prev_chain_p;
{
basic_block bb;
@@ -376,11 +445,25 @@ create_bb (head, end, control_parent)
bb = (basic_block) ggc_alloc (sizeof (*bb));
memset (bb, 0, sizeof (*bb));
+ /* Initialize the binding stack with the first block. */
+ if (n_basic_blocks == 0)
+ VARRAY_PUSH_BB (binding_stack, bb);
+
bb->head_tree = head;
bb->end_tree = end;
bb->index = n_basic_blocks;
get_bb_ann (bb)->parent = control_parent;
+ get_bb_ann (bb)->prev_chain_p = prev_chain_p;
+ get_bb_ann (bb)->binding_scope = VARRAY_TOP_BB (binding_stack);
+ /* If this block starts a new scope, push it into the stack of bindings. */
+ if (TREE_CODE (bb->head_tree) == SCOPE_STMT && SCOPE_BEGIN_P (bb->head_tree))
+ VARRAY_PUSH_BB (binding_stack, bb);
+
+ /* If the block ends a scope, pop it from the stack. */
+ if (TREE_CODE (bb->end_tree) == SCOPE_STMT && SCOPE_END_P (bb->end_tree))
+ VARRAY_POP (binding_stack);
+
/* Grow the basic block array if needed. */
if ((size_t) n_basic_blocks == VARRAY_SIZE (basic_block_info))
VARRAY_GROW (basic_block_info, n_basic_blocks + (n_basic_blocks + 3) / 4);
@@ -481,6 +564,10 @@ make_edges ()
if (is_ctrl_stmt (bb->head_tree))
make_ctrl_stmt_edges (edge_cache, bb);
+ /* Edges for statement expressions. */
+ if (is_statement_expression (bb->head_tree))
+ make_edge (edge_cache, bb, BASIC_BLOCK (i + 1), 0);
+
/* Edges for control flow altering statements (goto, break,
continue, return) need an edge to the corresponding target
block. */
@@ -500,7 +587,13 @@ make_edges ()
return;
}
- make_edge (edge_cache, switch_bb, bb, 0);
+ /* If the preceding block begins a new scope, make the edge to
+ that block instead. */
+ if (bb->pred && bb->pred->src && bb->pred->src->head_tree
+ && TREE_CODE (bb->pred->src->head_tree) == SCOPE_STMT)
+ make_edge (edge_cache, switch_bb, bb->pred->src, 0);
+ else
+ make_edge (edge_cache, switch_bb, bb, 0);
}
/* Finally, if no edges were created above, this is a regular
@@ -547,7 +640,7 @@ make_ctrl_stmt_edges (edge_cache, bb)
case SWITCH_STMT:
/* Nothing to do. Each label inside the switch statement will create
- its own edge form the switch block. */
+ its own edge from the switch block. */
break;
default:
@@ -602,7 +695,6 @@ make_for_stmt_edges (edge_cache, bb)
basic_block bb;
{
tree body_t, entry = bb->head_tree;
- int ix;
basic_block init_bb, cond_bb, expr_bb, body_bb;
if (TREE_CODE (entry) != FOR_STMT)
@@ -635,15 +727,11 @@ make_for_stmt_edges (edge_cache, bb)
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 both condition and expression
blocks exist in every for loop. */
- init_bb = BASIC_BLOCK (ix++);
- cond_bb = BASIC_BLOCK (ix++);
- expr_bb = BASIC_BLOCK (ix++);
+ init_bb = FOR_INIT_STMT_BB (bb);
+ cond_bb = FOR_COND_BB (bb);
+ expr_bb = FOR_EXPR_BB (bb);
body_t = first_exec_stmt (FOR_BODY (entry));
body_bb = (body_t) ? BB_FOR_STMT (body_t) : expr_bb;
@@ -937,25 +1025,25 @@ delete_unreachable_blocks ()
/* Delete all unreachable basic blocks. Count down so that we
don't interfere with the block renumbering that happens in
- delete_block. */
+ delete_bb. */
for (i = n_basic_blocks - 1; i >= 0; --i)
{
basic_block bb = BASIC_BLOCK (i);
if (!(bb->flags & BB_REACHABLE))
- delete_block (bb);
+ delete_bb (bb);
}
}
/* }}} */
-/* {{{ delete_block()
+/* {{{ delete_bb()
Remove a block from the flowgraph. Emit a warning if -Wunreachable-code
is set. */
static void
-delete_block (bb)
+delete_bb (bb)
basic_block bb;
{
edge e, next, *q;
@@ -965,8 +1053,6 @@ delete_block (bb)
{
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
@@ -976,9 +1062,7 @@ delete_block (bb)
warning ("unreachable statement");
}
- /* Remove all the instructions in the block.
-
- FIXME - This merely unmaps the statements. We should remove them. */
+ /* Unmap all the instructions in the block. */
t = bb->head_tree;
while (t)
{
@@ -1061,7 +1145,8 @@ block_invalidates_loop (bb, loop)
basic_block bb;
struct loop *loop;
{
- tree t;
+ size_t i;
+ varray_type refs;
/* Valid loops cannot contain a return statement. */
if (TREE_CODE (bb->end_tree) == RETURN_STMT)
@@ -1073,17 +1158,17 @@ block_invalidates_loop (bb, loop)
&& ! TEST_BIT (loop->nodes, bb->succ->dest->index))
return 1;
- for (t = bb->head_tree; t; t = TREE_CHAIN (t))
+ /* If the node contains a non-pure function call, mark it invalid. */
+ refs = BB_REFS (bb);
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (refs); i++)
{
- /* Call to user function.
- FIXME: Should check that this is actually a user function. */
+ varref ref = VARRAY_GENERIC_PTR (refs, i);
+ tree fcall = VARREF_SYM (ref);
- if (TREE_CODE (t) == EXPR_STMT
- && TREE_CODE (EXPR_STMT_EXPR (t)) == CALL_EXPR)
+ if (TREE_CODE (fcall) == FUNCTION_DECL
+ && ! DECL_IS_PURE (fcall)
+ && ! DECL_BUILT_IN (fcall))
return 1;
-
- if (t == bb->end_tree)
- break;
}
return 0;
@@ -1161,7 +1246,8 @@ is_ctrl_stmt (t)
return (TREE_CODE (t) == FOR_STMT
|| TREE_CODE (t) == IF_STMT
|| TREE_CODE (t) == WHILE_STMT
- || TREE_CODE (t) == SWITCH_STMT || TREE_CODE (t) == DO_STMT);
+ || TREE_CODE (t) == SWITCH_STMT
+ || TREE_CODE (t) == DO_STMT);
}
/* }}} */
@@ -1202,6 +1288,64 @@ is_loop_stmt (t)
/* }}} */
+/* {{{ loop_body()
+
+ Return the first statement in the body of LOOP. */
+
+tree
+loop_body (loop)
+ tree loop;
+{
+ if (TREE_CODE (loop) == FOR_STMT)
+ return FOR_BODY (loop);
+ else if (TREE_CODE (loop) == WHILE_STMT)
+ return WHILE_BODY (loop);
+ else if (TREE_CODE (loop) == DO_STMT)
+ return DO_BODY (loop);
+ else
+ abort ();
+}
+
+/* }}} */
+
+/* {{{ set_loop_body()
+
+ Set the body of LOOP to be STMT. */
+
+void
+set_loop_body (loop, stmt)
+ tree loop;
+ tree stmt;
+{
+ tree *prev_chain_p;
+
+ if (TREE_CODE (loop) == FOR_STMT)
+ {
+ prev_chain_p = &(FOR_BODY (loop));
+ FOR_BODY (loop) = stmt;
+ }
+ else if (TREE_CODE (loop) == WHILE_STMT)
+ {
+ prev_chain_p = &(WHILE_BODY (loop));
+ WHILE_BODY (loop) = stmt;
+ }
+ else if (TREE_CODE (loop) == DO_STMT)
+ {
+ prev_chain_p = &(DO_BODY (loop));
+ DO_BODY (loop) = stmt;
+ }
+ else
+ abort ();
+
+ /* Create a sub-flowgraph for the new statement and re-compute edges in
+ the flowgraph. */
+ make_blocks (stmt, BB_FOR_STMT (loop), TREE_COMPOUND_STMT (loop),
+ prev_chain_p);
+ make_edges ();
+}
+
+/* }}} */
+
/* {{{ stmt_starts_bb_p()
Return 1 if the given tree should start a new basic block. */
@@ -1216,7 +1360,9 @@ stmt_starts_bb_p (t)
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));
+ || TREE_CODE (t) == COMPOUND_STMT
+ || is_statement_expression (t)
+ || is_ctrl_stmt (t));
}
/* }}} */
@@ -1261,7 +1407,9 @@ delete_cfg ()
{
bb_ann ann = BB_ANN (BASIC_BLOCK (i));
ann->parent = NULL;
- ann->refs = NULL;
+ /* There is no need to delete the arrays in each of the reference.
+ That is done by delete_ssa(). */
+ VARRAY_FREE (ann->refs);
BASIC_BLOCK (i)->aux = NULL;
}
@@ -1292,27 +1440,22 @@ loop_parent (bb)
Returns the block marking the end of the loop body. This is the block
that contains the back edge to the start of the loop (i.e., to the block
- containing DO_COND or WHILE_COND or FOR_COND).
-
- ??? Note that this relies heavily on the order in which basic blocks
- get constructed, but I couldn't find another way of dealing with
- this. */
+ containing DO_COND or WHILE_COND or FOR_COND). */
basic_block
latch_block (loop_bb)
basic_block loop_bb;
{
- int index;
enum tree_code code = TREE_CODE (loop_bb->head_tree);
if (code == FOR_STMT)
- index = loop_bb->index + 3;
- else if (code == DO_STMT || code == WHILE_STMT)
- index = loop_bb->index + 1;
+ return FOR_EXPR_BB (loop_bb);
+ else if (code == WHILE_STMT)
+ return WHILE_COND_BB (loop_bb);
+ else if (code == DO_STMT)
+ return DO_COND_BB (loop_bb);
else
abort ();
-
- return BASIC_BLOCK (index);
}
/* }}} */
@@ -1377,6 +1520,32 @@ first_exec_stmt (t)
/* }}} */
+/* {{{ last_exec_stmt (t)
+
+ Return the last executable statement starting at T. */
+
+tree
+last_exec_stmt (t)
+ tree t;
+{
+ tree prev;
+
+ if (t == NULL)
+ return NULL;
+
+ prev = NULL;
+ t = first_exec_stmt (t);
+ while (t && is_exec_stmt (t))
+ {
+ prev = t;
+ t = TREE_CHAIN (t);
+ }
+
+ return prev;
+}
+
+/* }}} */
+
/* {{{ is_exec_stmt()
Return 1 if T is an executable statement. */
@@ -1387,12 +1556,740 @@ is_exec_stmt (t)
{
return (t
&& statement_code_p (TREE_CODE (t))
- && TREE_CODE (t) != COMPOUND_STMT && TREE_CODE (t) != SCOPE_STMT);
+ && TREE_CODE (t) != COMPOUND_STMT
+ && ! (TREE_CODE (t) == SCOPE_STMT && SCOPE_END_P (t)));
+}
+
+/* }}} */
+
+/* {{{ is_statement_expression()
+
+ Return 1 if T is a statement-expression. */
+
+int
+is_statement_expression (t)
+ tree t;
+{
+ return (TREE_CODE (t) == EXPR_STMT
+ && TREE_OPERAND (t, 0)
+ && TREE_CODE (TREE_OPERAND (t, 0)) == STMT_EXPR);
+}
+
+/* }}} */
+
+/* {{{ first_non_decl_stmt()
+
+ Returns the first statement that is not a DECL_STMT or SCOPE_STMT, starting
+ with T. */
+
+tree
+first_non_decl_stmt (t)
+ tree t;
+{
+ while (t && (TREE_CODE (t) == SCOPE_STMT || TREE_CODE (t) == DECL_STMT))
+ t = TREE_CHAIN (t);
+
+ return t;
+}
+
+/* }}} */
+
+/* {{{ first_decl_stmt()
+
+ Returns the first statement that is not a DECL_STMT or SCOPE_STMT, starting
+ with T. */
+
+tree
+first_decl_stmt (t)
+ tree t;
+{
+ while (t && TREE_CODE (t) != DECL_STMT)
+ t = TREE_CHAIN (t);
+
+ return t;
+}
+
+/* }}} */
+
+/* {{{ first_non_label_in_bb()
+
+ Returns the first executable statement that is not a LABEL or CASE_LABEL
+ in basic block BB. Returns NULL if the block only contains labels. */
+
+tree
+first_non_label_in_bb (bb)
+ basic_block bb;
+{
+ tree t;
+
+ t = bb->head_tree;
+ while (t
+ && is_exec_stmt (t)
+ && t != bb->end_tree
+ && (TREE_CODE (t) == LABEL_STMT
+ || TREE_CODE (t) == CASE_LABEL))
+ t = TREE_CHAIN (t);
+
+ return ((t && t != bb->end_tree) ? t : NULL);
+}
+
+/* }}} */
+
+
+/* Code insertion and replacement. */
+
+/* {{{ insert_stmt_tree_before()
+
+ Insert statement STMT before tree WHERE in basic block BB. The
+ insertion is flow-sensitive. After insertion, statement STMT is
+ guaranteed to always execute before WHERE.
+
+ ??? Important, this code only supports the insertion of simple
+ statements. Inserting control statements will require re-computing the
+ flowgraph.
+
+ Also, insertion of expressions is not supported. The code is
+ not prepared to handle all the side-effects and look for correct
+ sequence points where to insert arbitrary expressions. */
+
+void
+insert_stmt_tree_before (stmt, where, bb)
+ tree stmt;
+ tree where;
+ basic_block bb;
+{
+ /* Make sure STMT is a statement with no existing chain. */
+ if (! statement_code_p (TREE_CODE (stmt)) || TREE_CHAIN (stmt))
+ abort ();
+
+ cfg_dump_file = dump_begin (TDI_cfg, &cfg_dump_flags);
+
+ /* If the basic block contains a control flow expression, we may need
+ to do other insertions. */
+ if (bb->flags & BB_CONTROL_EXPR)
+ insert_before_ctrl_stmt (stmt, where, bb);
+ else
+ insert_before_normal_stmt (stmt, where, bb);
+
+ if (cfg_dump_file)
+ dump_end (TDI_cfg, cfg_dump_file);
}
/* }}} */
+/* {{{ insert_before_ctrl_stmt()
+
+ Subroutine of insert_stmt_before() to handle insertions in control
+ header blocks. */
+static void
+insert_before_ctrl_stmt (stmt, where, bb)
+ tree stmt;
+ tree where;
+ basic_block bb;
+{
+ basic_block parent_bb;
+ tree parent;
+
+ /* If BB is already a control entry block (IF, WHILE, CASE), then we
+ don't need to go to its parent. */
+ parent_bb = (bb->flags & BB_CONTROL_ENTRY) ? bb : BB_PARENT (bb);
+ parent = parent_bb->head_tree;
+
+ if (cfg_dump_file)
+ {
+ fprintf (cfg_dump_file, "\nAbout to insert statement: ");
+ print_node_brief (cfg_dump_file, "", stmt, 0);
+ fprintf (cfg_dump_file, "\nBefore statement: ");
+ print_node_brief (cfg_dump_file, "", parent, 0);
+ fprintf (cfg_dump_file, " (line %d)\n", STMT_LINENO (parent));
+ fprintf (cfg_dump_file, "At basic block %d\n", bb->index);
+ }
+
+ /* If this is not a loop, do a normal insertion before the control
+ statement's entry point. */
+ if (! is_loop_stmt (parent))
+ insert_before_normal_stmt (stmt, parent, parent_bb);
+
+ /* WHILE_STMT block. Insert before the entry block and after the last
+ block in the body. */
+ else if (TREE_CODE (parent) == WHILE_STMT)
+ {
+ insert_before_normal_stmt (stmt, parent, bb);
+
+ if (first_exec_stmt (first_non_decl_stmt (WHILE_BODY (parent))) == NULL)
+ WHILE_BODY (parent) = copy_node (stmt);
+ else
+ insert_after_loop_body (copy_node (stmt), parent_bb);
+ }
+
+ /* DO_STMT block. Insert at the end of the loop body. */
+ else if (TREE_CODE (parent) == DO_STMT)
+ {
+ if (first_exec_stmt (first_non_decl_stmt (DO_BODY (parent))) == NULL)
+ DO_BODY (parent) = stmt;
+ else
+ insert_after_loop_body (stmt, parent_bb);
+ }
+
+ /* FOR_STMT block. Check which of FOR_INIT_EXPR, FOR_COND or FOR_EXPR we
+ are dealing with. */
+ else if (TREE_CODE (parent) == FOR_STMT)
+ {
+ /* FOR_INIT_STMT. Insert before its first statement. */
+ if (bb == FOR_INIT_STMT_BB (parent_bb))
+ {
+ if (first_exec_stmt (FOR_INIT_STMT (parent)) == NULL)
+ FOR_INIT_STMT (parent) = stmt;
+ else
+ insert_before_normal_stmt (stmt, where, bb);
+ }
+
+ /* FOR_COND block. Insert at the end of FOR_INIT_STMT and at the end
+ of FOR_EXPR. */
+ else if (bb == FOR_COND_BB (parent_bb))
+ {
+ tree last_stmt = last_exec_stmt (FOR_INIT_STMT (parent));
+ if (last_stmt)
+ insert_after_normal_stmt (stmt, last_stmt,
+ BB_FOR_STMT (last_stmt));
+ else
+ FOR_INIT_STMT (parent) = stmt;
+
+ last_stmt = last_exec_stmt (FOR_EXPR (parent));
+ if (last_stmt)
+ insert_after_normal_stmt (copy_node (stmt), last_stmt,
+ BB_FOR_STMT (last_stmt));
+ else
+ FOR_EXPR (parent) = copy_node (stmt);
+ }
+
+ /* FOR_EXPR block. Insert at the end of the loop body. */
+ else if (bb == FOR_EXPR_BB (parent_bb))
+ {
+ if (first_exec_stmt (first_non_decl_stmt (FOR_BODY (parent))) == NULL)
+ FOR_BODY (parent) = stmt;
+ else
+ insert_after_loop_body (stmt, parent_bb);
+ }
+ else
+ abort();
+ }
+
+ else
+ abort ();
+}
+
+/* }}} */
+
+/* {{{ insert_before_normal_stmt()
+
+ Subroutine of insert_stmt_tree_before() to handle insertions in regular
+ statements. If STMT is inserted before a block boundary, a new basic
+ block is created to hold it. */
+
+static void
+insert_before_normal_stmt (stmt, where, bb)
+ tree stmt;
+ tree where;
+ basic_block bb;
+{
+ /* If the insertion is somewhere in the middle of the block, look for
+ the insertion point starting at the head. */
+ if (where != bb->head_tree)
+ {
+ tree last, prev;
+
+ prev = NULL;
+ last = bb->head_tree;
+ while (last && last != where)
+ {
+ prev = last;
+ last = TREE_CHAIN (last);
+ }
+
+ if (prev == NULL)
+ abort ();
+
+ TREE_CHAIN (prev) = stmt;
+ TREE_CHAIN (stmt) = where;
+ map_stmt_to_bb (stmt, bb);
+
+ if (cfg_dump_file)
+ {
+ fprintf (cfg_dump_file, "\nInserted statement: ");
+ print_node_brief (cfg_dump_file, "", stmt, 0);
+ fprintf (cfg_dump_file, "\nBefore statement : ");
+ print_node_brief (cfg_dump_file, "", where, 0);
+ fprintf (cfg_dump_file, " (line %d)\n", STMT_LINENO (where));
+ fprintf (cfg_dump_file, "At basic block %d\n", bb->index);
+ }
+ }
+
+ /* Otherwise, insert the statement in the previous tree's
+ TREE_CHAIN and create a new basic block holding the statement, if
+ needed. */
+ else
+ {
+ basic_block new_bb = NULL;
+ tree *prev_chain_p = BB_PREV_CHAIN_P (bb);
+
+ *prev_chain_p = stmt;
+ TREE_CHAIN (stmt) = where;
+ if (is_ctrl_stmt (where))
+ {
+ new_bb = create_bb (stmt, stmt, BB_PARENT (bb), prev_chain_p);
+ insert_bb_before (new_bb, bb);
+ }
+ else
+ {
+ map_stmt_to_bb (stmt, bb);
+ bb->head_tree = stmt;
+ }
+
+ if (cfg_dump_file)
+ {
+ fprintf (cfg_dump_file, "\nInserted statement: ");
+ print_node_brief (cfg_dump_file, "", stmt, 0);
+ fprintf (cfg_dump_file, "\nBefore statement : ");
+ print_node_brief (cfg_dump_file, "", where, 0);
+ fprintf (cfg_dump_file, " (line %d)\n", STMT_LINENO (where));
+ if (new_bb)
+ fprintf (cfg_dump_file, "Created new basic block %d\n",
+ new_bb->index);
+ else
+ fprintf (cfg_dump_file, "At basic block %d\n", bb->index);
+ }
+ }
+}
+
+/* }}} */
+
+/* {{{ insert_stmt_tree_after()
+
+ Insert statement STMT after statement WHERE in basic block BB. The
+ insertion is flow-sensitive. After insertion, statement STMT is
+ guaranteed to always execute after WHERE.
+
+ ??? Important, this code only supports the insertion of simple
+ statements. Inserting control statements will require re-computing the
+ flowgraph.
+
+ Also, insertion of expressions is not supported. The code is
+ not prepared to handle all the side-effects and look for correct
+ sequence points where to insert arbitrary expressions. */
+
+void
+insert_stmt_tree_after (stmt, where, bb)
+ tree stmt;
+ tree where;
+ basic_block bb;
+{
+ /* Only accept statement trees. */
+ if (! statement_code_p (TREE_CODE (stmt)))
+ abort ();
+
+ cfg_dump_file = dump_begin (TDI_cfg, &cfg_dump_flags);
+
+ if (bb->flags & BB_CONTROL_EXPR)
+ insert_after_ctrl_stmt (stmt, where, bb);
+ else
+ insert_after_normal_stmt (stmt, where, bb);
+
+ if (cfg_dump_file)
+ dump_end (TDI_cfg, cfg_dump_file);
+}
+
+/* }}} */
+
+/* {{{ insert_after_ctrl_stmt()
+
+ Subroutine of insert_stmt_tree_after() to handle insertions at control
+ statement header blocks. */
+
+static void
+insert_after_ctrl_stmt (stmt, where, bb)
+ tree stmt;
+ tree where;
+ basic_block bb;
+{
+ basic_block parent_bb;
+ tree parent;
+ tree t;
+
+ /* If BB is already a control entry block (IF, WHILE, CASE), then we
+ don't need to go to its parent. */
+ parent_bb = (bb->flags & BB_CONTROL_ENTRY) ? bb : BB_PARENT (bb);
+ parent = parent_bb->head_tree;
+
+ if (cfg_dump_file)
+ {
+ fprintf (cfg_dump_file, "\nAbout to insert statement: ");
+ print_node_brief (cfg_dump_file, "", stmt, 0);
+ fprintf (cfg_dump_file, "\nAfter statement: ");
+ print_node_brief (cfg_dump_file, "", parent, 0);
+ fprintf (cfg_dump_file, " (line %d)\n", STMT_LINENO (parent));
+ fprintf (cfg_dump_file, "At basic block %d\n", bb->index);
+ }
+
+ /* IF_STMT block. Insert before THEN_CLAUSE and ELSE_CLAUSE. */
+ if (TREE_CODE (parent) == IF_STMT)
+ {
+ t = first_exec_stmt (first_non_decl_stmt (THEN_CLAUSE (parent)));
+ if (t == NULL)
+ THEN_CLAUSE (parent) = stmt;
+ else
+ insert_before_normal_stmt (stmt, t, BB_FOR_STMT (t));
+
+ t = first_exec_stmt (first_non_decl_stmt (ELSE_CLAUSE (parent)));
+ if (t == NULL)
+ ELSE_CLAUSE (parent) = copy_node (stmt);
+ else
+ insert_before_normal_stmt (copy_node (stmt), t, BB_FOR_STMT (t));
+ }
+
+ /* SWITCH_STMT block. Insert before each case block (after the label). */
+ else if (TREE_CODE (parent) == SWITCH_STMT)
+ {
+ edge e;
+
+ for (e = parent_bb->succ; e; e = e->succ_next)
+ {
+ basic_block succ_bb = e->dest;
+ t = first_non_label_in_bb (succ_bb);
+ if (t)
+ insert_before_normal_stmt (copy_node (stmt), t, succ_bb);
+ }
+ }
+
+ /* WHILE_STMT block. Insert before the first statement in the body. */
+ else if (TREE_CODE (parent) == WHILE_STMT)
+ {
+ t = first_exec_stmt (first_non_decl_stmt (WHILE_BODY (parent)));
+ if (t == NULL)
+ WHILE_BODY (parent) = stmt;
+ else
+ insert_before_normal_stmt (stmt, t, BB_FOR_STMT (t));
+ }
+
+ /* DO_STMT block. Insert before the first statement in the body.
+ FIXME: This is wrong, we should be replacing the conditional
+ with an expression-statement. */
+ else if (TREE_CODE (parent) == DO_STMT)
+ {
+ t = first_exec_stmt (first_non_decl_stmt (DO_BODY (parent)));
+ if (t == NULL)
+ DO_BODY (parent) = stmt;
+ else
+ insert_before_normal_stmt (stmt, t, BB_FOR_STMT (t));
+ }
+
+ /* FOR_STMT block. Check which of FOR_INIT_STMT, FOR_COND or FOR_EXPR
+ we are dealing with. */
+ else if (TREE_CODE (parent) == FOR_STMT)
+ {
+ /* FOR_INIT_STMT block. Insert after the last init statement. */
+ if (bb == FOR_INIT_STMT_BB (parent_bb))
+ {
+ t = last_exec_stmt (FOR_INIT_STMT (parent));
+ if (t == NULL)
+ FOR_INIT_STMT (parent) = stmt;
+ else
+ insert_after_normal_stmt (stmt, t, bb);
+ }
+
+ /* FOR_COND block. Insert before the first statement in the body. */
+ else if (bb == FOR_COND_BB (parent_bb))
+ {
+ t = first_exec_stmt (first_non_decl_stmt (FOR_BODY (parent)));
+ if (t == NULL)
+ FOR_BODY (parent) = stmt;
+ else
+ insert_before_normal_stmt (stmt, t, BB_FOR_STMT (t));
+ }
+
+ /* FOR_EXPR block. Insert after the last expr statement. */
+ else if (bb == FOR_EXPR_BB (parent_bb))
+ {
+ t = last_exec_stmt (FOR_EXPR (parent));
+ if (t == NULL)
+ FOR_EXPR (parent) = stmt;
+ else
+ insert_after_normal_stmt (stmt, t, bb);
+ }
+
+ else
+ abort ();
+ }
+
+ else
+ abort ();
+}
+
+/* }}} */
+
+/* {{{ insert_after_normal_stmt()
+
+ Subroutine of insert_stmt_tree_after() to insert after normal
+ statements. */
+
+static void
+insert_after_normal_stmt (stmt, where, bb)
+ tree stmt;
+ tree where;
+ basic_block bb;
+{
+ /* If the statement goes at the end of the block, we need to adjust the
+ PREV_CHAIN_P pointer of each successor block that was pointing back to
+ TREE_CHAIN (where). */
+ if (where == bb->end_tree)
+ {
+ edge e;
+
+ for (e = bb->succ; e; e = e->succ_next)
+ {
+ basic_block succ_bb = e->dest;
+
+ if (BB_PREV_CHAIN_P (succ_bb) == &(TREE_CHAIN (where)))
+ get_bb_ann (succ_bb)->prev_chain_p = &(TREE_CHAIN (stmt));
+ }
+ }
+
+ /* Chain STMT after WHERE. */
+ TREE_CHAIN (stmt) = TREE_CHAIN (where);
+ TREE_CHAIN (where) = stmt;
+
+ /* Extend the basic block to contain STMT. */
+ map_stmt_to_bb (stmt, bb);
+ if (where == bb->end_tree)
+ bb->end_tree = stmt;
+
+ if (cfg_dump_file)
+ {
+ fprintf (cfg_dump_file, "\nInserted statement: ");
+ print_node_brief (cfg_dump_file, "", stmt, 0);
+ fprintf (cfg_dump_file, "\nAfter statement : ");
+ print_node_brief (cfg_dump_file, "", where, 0);
+ fprintf (cfg_dump_file, " (line %d)\n", STMT_LINENO (where));
+ fprintf (cfg_dump_file, "At basic block %d\n", bb->index);
+ }
+}
+
+/* }}} */
+
+/* {{{ insert_after_loop_body()
+
+ Inserts STMT so that it will be executed after the body of the loop
+ starting at basic block LOOP. */
+
+static void
+insert_after_loop_body (stmt, loop)
+ tree stmt;
+ basic_block loop;
+{
+ edge e;
+ tree last_stmt;
+ basic_block latch_bb;
+
+ /* For every predecessor PRED_BB of the latch block, we need to insert a
+ copy of STMT if PRED_BB ends in a CONTINUE_STMT, BREAK_STMT or if its
+ parent block is the loop header.
+
+ The last condition is to avoid inserting unnecessary copies in cases
+ like this one:
+
+ for ()
+ {
+ ....
+ if ()
+ a;
+ else
+ b;
+ }
+
+ In this case, both 'a' and 'b' are predecessors of the latch block,
+ but instead of inserting STMT twice, it's better to insert it after
+ the if() statement. */
+ latch_bb = latch_block (loop);
+ for (e = latch_bb->pred; e; e = e->pred_next)
+ {
+ basic_block pred_bb = e->src;
+ last_stmt = pred_bb->end_tree;
+
+ if (TREE_CODE (last_stmt) == CONTINUE_STMT
+ || TREE_CODE (last_stmt) == BREAK_STMT)
+ insert_before_normal_stmt (copy_node (stmt), pred_bb->end_tree,
+ pred_bb);
+ }
+
+ /* Insert STMT after the last executable statement in the loop body. */
+ last_stmt = last_exec_stmt (loop_body (loop->head_tree));
+ insert_after_normal_stmt (copy_node (stmt), last_stmt,
+ BB_FOR_STMT (last_stmt));
+}
+
+/* }}} */
+
+/* {{{ replace_expr_in_tree()
+
+ Replace expression EXPR in statement STMT with NEW_EXPR. */
+
+void
+replace_expr_in_tree (stmt, old_expr, new_expr)
+ tree stmt;
+ tree old_expr;
+ tree new_expr;
+{
+ tree *old_expr_p = find_expr_in_tree (stmt, old_expr);
+
+ cfg_dump_file = dump_begin (TDI_cfg, &cfg_dump_flags);
+ if (cfg_dump_file)
+ {
+ if (old_expr_p)
+ {
+ fprintf (cfg_dump_file, "\nRequested expression: ");
+ print_node_brief (cfg_dump_file, "", old_expr, 0);
+
+ fprintf (cfg_dump_file, "\nReplaced expression: ");
+ print_node_brief (cfg_dump_file, "", *old_expr_p, 0);
+
+ fprintf (cfg_dump_file, "\nWith expression: ");
+ print_node_brief (cfg_dump_file, "", new_expr, 0);
+ }
+ else
+ {
+ fprintf (cfg_dump_file, "\nCould not find expression: ");
+ print_node_brief (cfg_dump_file, "", old_expr, 0);
+ }
+
+ fprintf (cfg_dump_file, "\nIn statement: ");
+ print_node_brief (cfg_dump_file, "", stmt, 0);
+
+ fprintf (cfg_dump_file, "\nBasic block: ");
+ if (statement_code_p (TREE_CODE (stmt)))
+ fprintf (cfg_dump_file, "%d", BB_FOR_STMT (stmt)->index);
+ else
+ fprintf (cfg_dump_file, "-1");
+
+ fprintf (cfg_dump_file, "\nLine: ");
+ if (statement_code_p (TREE_CODE (stmt)))
+ fprintf (cfg_dump_file, "%d", STMT_LINENO (stmt));
+ else
+ fprintf (cfg_dump_file, "-1");
+
+ fprintf (cfg_dump_file, "\n");
+
+ dump_end (TDI_cfg, cfg_dump_file);
+ }
+
+ if (old_expr_p)
+ *old_expr_p = new_expr;
+}
+
+/* }}} */
+
+/* {{{ find_expr_in_tree()
+
+ Returns the location of expression EXPR in T. The search is guaranteed
+ to not go outside statement nodes, only their sub-expressions are
+ searched. */
+
+tree *
+find_expr_in_tree (t, expr)
+ tree t;
+ tree expr;
+{
+ int i;
+ tree *loc;
+
+ if (t == NULL || t == error_mark_node
+ || expr == NULL || expr == error_mark_node)
+ return NULL;
+
+ /* Deal with special trees first. */
+ switch (TREE_CODE (t))
+ {
+ case COMPLEX_CST:
+ case INTEGER_CST:
+ case LABEL_DECL:
+ case REAL_CST:
+ case RESULT_DECL:
+ case STRING_CST:
+ return NULL;
+
+ case TREE_LIST:
+ {
+ tree op;
+
+ /* Try the list elements. */
+ for (op = t; op; op = TREE_CHAIN (op))
+ if (TREE_VALUE (op) == expr)
+ return &(TREE_VALUE (op));
+
+ /* Not there? Recurse into each of the list elements. */
+ for (op = t; op; op = TREE_CHAIN (op))
+ {
+ loc = find_expr_in_tree (TREE_VALUE (op), expr);
+ if (loc)
+ return loc;
+ }
+
+ return NULL;
+ }
+
+ default:
+ break;
+ }
+
+ /* Try the immediate operands. */
+ for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (t)); i++)
+ if (TREE_OPERAND (t, i) == expr)
+ return &(TREE_OPERAND (t, i));
+
+ /* If we still haven't found it, recurse into each sub-expression of T. */
+ for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (t)); i++)
+ {
+ loc = find_expr_in_tree (TREE_OPERAND (t, i), expr);
+ if (loc)
+ return loc;
+ }
+
+ /* Finally, if T is not a statement, recurse into its chain (this limits
+ the search to a single statement). */
+ if (! statement_code_p (TREE_CODE (t)))
+ {
+ loc = find_expr_in_tree (TREE_CHAIN (t), expr);
+ if (loc)
+ return loc;
+ }
+
+ return NULL;
+}
+
+/* }}} */
+
+/* {{{ insert_bb_before()
+
+ Insert basic block NEW_BB before BB. */
+
+void
+insert_bb_before (new_bb, bb)
+ basic_block new_bb;
+ basic_block bb;
+{
+ edge e;
+
+ /* Reconnect BB's predecessors to NEW_BB. */
+ for (e = bb->pred; e; e = e->pred_next)
+ redirect_edge_succ (e, new_bb);
+
+ /* Create the edge NEW_BB -> BB. */
+ make_edge (NULL, new_bb, bb, 0);
+}
+
+/* }}} */
+
+
/* Debugging functions. */
/* {{{ tree_dump_bb
@@ -1453,6 +2350,26 @@ tree_dump_bb (outf, prefix, bb, indent)
fprintf (outf, "%d\n", BB_PARENT (bb)->index);
else
fputs ("nil\n", outf);
+
+ fprintf (outf, "%s%sPrevious stmt: ", s_indent, prefix);
+ if (BB_PREV_CHAIN_P (bb))
+ {
+ tree *t = BB_PREV_CHAIN_P (bb);
+ lineno = (*t && statement_code_p (TREE_CODE (*t)))
+ ? STMT_LINENO (*t)
+ : -1;
+ print_node_brief (outf, "", *t, 0);
+ fprintf (outf, " (line: %d)\n", lineno);
+ }
+ else
+ fputs ("nil\n", outf);
+
+ fprintf (outf, "%s%sBinding scope block: ", s_indent, prefix);
+ if (BB_BINDING_SCOPE (bb))
+ fprintf (outf, "%d\n", BB_BINDING_SCOPE (bb)->index);
+ else
+ fputs ("nil\n", outf);
+
fprintf (outf, "%s%sLoop depth: %d\n", s_indent, prefix, bb->loop_depth);
}
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.2.7
diff -d -p -d -u -p -r1.1.2.7 tree-dfa.c
--- tree-dfa.c 2001/09/14 05:12:57 1.1.2.7
+++ tree-dfa.c 2001/09/30 06:11:05
@@ -34,7 +34,7 @@ Boston, MA 02111-1307, USA. */
#include "tree-optimize.h"
#include "tree-flow.h"
-/* {{{ Local declarations. */
+/* Local declarations. */
/* Dump file and flags. */
static FILE *dump_file;
@@ -42,23 +42,18 @@ static int dump_flags;
/* Local functions. */
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 void create_tree_ann PARAMS ((tree));
-static void add_ref_to_sym PARAMS ((varref, tree));
-static void add_ref_to_bb PARAMS ((varref, basic_block));
static void add_ref_symbol PARAMS ((tree));
-/* }}} */
-/* {{{ Global declarations. */
+/* Global declarations. */
/* Array of all symbols referenced in the function. */
varray_type referenced_symbols;
-/* }}} */
/* Find variable references in the code. */
@@ -72,8 +67,6 @@ tree_find_varrefs ()
{
int i;
- dump_file = dump_begin (TDI_ssa, &dump_flags);
-
for (i = 0; i < n_basic_blocks; i++)
{
basic_block bb = BASIC_BLOCK (i);
@@ -97,27 +90,28 @@ tree_find_varrefs ()
}
/* Debugging dumps. */
+ dump_file = dump_begin (TDI_ssa, &dump_flags);
+
if (dump_file && (dump_flags & TDF_REFS))
{
- int i;
+ size_t i;
fprintf (dump_file, ";; Function %s\n\n",
IDENTIFIER_POINTER (DECL_NAME (current_function_decl)));
fprintf (dump_file, "Symbols referenced:\n");
- for (i = 0; i < VARRAY_ACTIVE_SIZE (referenced_symbols); i++)
+ for (i = 0; i < NREF_SYMBOLS; i++)
{
- tree sym = VARRAY_TREE (referenced_symbols, i);
+ tree sym = REF_SYMBOL (i);
print_node_brief (dump_file, "\t", sym, 0);
fputc ('\n', dump_file);
dump_varref_list (dump_file, "\t", TREE_REFS (sym), 4, 1);
fputc ('\n', dump_file);
}
- }
- if (dump_file)
- dump_end (TDI_ssa, dump_file);
+ dump_end (TDI_ssa, dump_file);
+ }
}
/* }}} */
@@ -134,7 +128,7 @@ find_refs_in_stmt (t, bb)
{
enum tree_code code;
- if (t == NULL)
+ if (t == NULL || t == error_mark_node)
return;
code = TREE_CODE (t);
@@ -177,13 +171,15 @@ find_refs_in_stmt (t, bb)
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);
+ 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 == STMT_EXPR)
+ find_refs_in_stmt (STMT_EXPR_STMT (t), bb);
+
else if (code == CONTINUE_STMT)
; /* Nothing to do. */
@@ -194,15 +190,10 @@ find_refs_in_stmt (t, bb)
; /* 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);
+ ; /* Nothing to do. */
else if (code == SCOPE_STMT)
- ; /* Nothing to do. FIXME - This should not
- be needed. See the note for code ==
- COMPOUND_STMT. */
+ ; /* Nothing to do. */
else
{
@@ -217,37 +208,17 @@ find_refs_in_stmt (t, bb)
}
}
-/* 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,
+ 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. */
+ trees containing EXPR. */
static void
find_refs_in_expr (expr, ref_type, bb, parent_stmt, parent_expr)
@@ -259,7 +230,7 @@ find_refs_in_expr (expr, ref_type, bb, p
{
enum tree_code code;
- if (expr == NULL)
+ if (expr == NULL || expr == error_mark_node)
return;
code = TREE_CODE (expr);
@@ -282,11 +253,11 @@ find_refs_in_expr (expr, ref_type, bb, p
case REAL_CST:
case RESULT_DECL:
case STRING_CST:
+ case ADDR_EXPR:
/* These trees make no memory references. */
break;
case ABS_EXPR:
- case ADDR_EXPR:
case CONJ_EXPR:
case CONVERT_EXPR:
case EXIT_EXPR:
@@ -403,9 +374,15 @@ find_refs_in_expr (expr, ref_type, bb, p
case CALL_EXPR:
{
tree op;
+ tree addr = TREE_OPERAND (expr, 0);
+ tree decl;
- find_refs_in_expr (TREE_OPERAND (expr, 0), VARUSE, bb, parent_stmt,
- expr);
+ if (TREE_CODE (addr) == ADDR_EXPR)
+ decl = TREE_OPERAND (addr, 0);
+ else
+ decl = addr;
+
+ find_refs_in_expr (decl, 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;
@@ -427,6 +404,11 @@ find_refs_in_expr (expr, ref_type, bb, p
find_refs_in_stmt (STMT_EXPR_STMT (expr), bb);
break;
+ /* File and line number annotations. */
+ case EXPR_WITH_FILE_LOCATION:
+ find_refs_in_stmt (TREE_OPERAND (expr, 0), bb);
+ break;
+
default:
{
prep_stmt (parent_stmt);
@@ -460,7 +442,6 @@ create_varref (sym, ref_type, bb, parent
tree parent_expr;
{
varref ref;
- int is_new;
if (bb == NULL)
abort ();
@@ -474,50 +455,31 @@ create_varref (sym, ref_type, bb, parent
VARREF_BB (ref) = bb;
VARREF_EXPR (ref) = parent_expr;
+ /* Create containers according to the type of reference. */
+ if (ref_type == VARDEF || ref_type == VARPHI)
+ {
+ VARRAY_GENERIC_PTR_INIT (VARDEF_IMM_USES (ref), 3, "imm_uses");
+ VARRAY_GENERIC_PTR_INIT (VARDEF_RUSES (ref), 5, "ruses");
+ if (ref_type == VARPHI)
+ VARRAY_GENERIC_PTR_INIT (VARDEF_PHI_CHAIN (ref), 3, "phi_chain");
+ }
+ else if (ref_type == VARUSE)
+ VARRAY_GENERIC_PTR_INIT (VARUSE_RDEFS (ref), 3, "rdefs");
+
/* Add the symbol to the list of symbols referenced in this function. */
add_ref_symbol (sym);
/* Add this reference to the list of references for the symbol. */
- add_ref_to_sym (ref, sym);
+ VARRAY_PUSH_GENERIC_PTR (get_tree_ann (sym)->refs, ref);
/* Add this reference to the list of references for the basic block. */
- add_ref_to_bb (ref, bb);
+ VARRAY_PUSH_GENERIC_PTR (get_bb_ann (bb)->refs, ref);
return ref;
}
/* }}} */
-/* {{{ add_ref_to_sym()
-
- Adds reference REF to the list of references made to symbol SYM. */
-
-void
-add_ref_to_sym (ref, sym)
- varref ref;
- tree sym;
-{
- tree_ann ann = get_tree_ann (sym);
- VARRAY_PUSH_GENERIC_PTR (ann->refs, ref);
-}
-
-/* }}} */
-
-/* {{{ add_ref_to_bb()
-
- Adds reference REF to the list of references made in basic block BB. */
-
-void
-add_ref_to_bb (ref, bb)
- varref ref;
- basic_block bb;
-{
- bb_ann ann = get_bb_ann (bb);
- VARRAY_PUSH_GENERIC_PTR (ann->refs, ref);
-}
-
-/* }}} */
-
/* {{{ add_ref_symbol()
Adds a unique copy of symbol SYM to the list of referenced symbols. */
@@ -526,16 +488,16 @@ static void
add_ref_symbol (sym)
tree sym;
{
- int i;
+ size_t i;
/* Look for the SYM in the array of symbols referenced in the function. */
- for (i = 0; i < VARRAY_ACTIVE_SIZE (referenced_symbols); i++)
- if (VARRAY_TREE (referenced_symbols, i) == sym)
+ for (i = 0; i < NREF_SYMBOLS; i++)
+ if (REF_SYMBOL (i) == sym)
return;
/* We didn't find the symbol. Add it to the list and create a new
annotation for the symbol. */
- VARRAY_PUSH_TREE (referenced_symbols, sym);
+ ADD_REF_SYMBOL (sym);
create_tree_ann (sym);
}
@@ -577,6 +539,131 @@ create_tree_ann (t)
/* }}} */
+/* Miscellaneous helpers. */
+
+/* {{{ function_may_recurse_p()
+
+ Return 1 if the function may call itself.
+
+ ??? Currently this is very limited because we do not have call-graph
+ information. */
+
+int
+function_may_recurse_p ()
+{
+ int i;
+
+ /* If we only make calls to pure and/or builtin functions, then the
+ function is not recursive. */
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ size_t j;
+ varray_type refs = BB_REFS (BASIC_BLOCK (i));
+
+ for (j = 0; j < VARRAY_ACTIVE_SIZE (refs); j++)
+ {
+ varref ref = VARRAY_GENERIC_PTR (refs, j);
+ tree fcall = VARREF_SYM (ref);
+
+ if (fcall == current_function_decl
+ || (TREE_CODE (fcall) == FUNCTION_DECL
+ && ! DECL_IS_PURE (fcall)
+ && ! DECL_BUILT_IN (fcall)))
+ return 1;
+ }
+ }
+
+ return 0;
+}
+
+/* }}} */
+
+/* {{{ get_fcalls()
+
+ Push into variable array *FCALLS_P all the function call references made
+ in this function.
+
+ WHICH is a bitmask specifying the type of function call that the caller
+ is interested in (see tree-flow.h). */
+
+void
+get_fcalls (fcalls_p, which)
+ varray_type *fcalls_p;
+ unsigned which;
+{
+ int i;
+
+ if (fcalls_p == NULL || *fcalls_p == NULL)
+ abort ();
+
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ size_t j;
+ varray_type refs = BB_REFS (BASIC_BLOCK (i));
+
+ for (j = 0; j < VARRAY_ACTIVE_SIZE (refs); j++)
+ {
+ varref ref = VARRAY_GENERIC_PTR (refs, j);
+ tree fcall = VARREF_SYM (ref);
+
+ if (TREE_CODE (fcall) == FUNCTION_DECL)
+ {
+ if ((which & FCALL_NON_PURE)
+ && ! DECL_IS_PURE (fcall)
+ && ! DECL_BUILT_IN (fcall))
+ VARRAY_PUSH_GENERIC_PTR (*fcalls_p, ref);
+
+ else if ((which & FCALL_PURE) && DECL_IS_PURE (fcall))
+ VARRAY_PUSH_GENERIC_PTR (*fcalls_p, ref);
+
+ else if ((which & FCALL_BUILT_IN) && DECL_BUILT_IN (fcall))
+ VARRAY_PUSH_GENERIC_PTR (*fcalls_p, ref);
+ }
+ }
+ }
+}
+
+/* }}} */
+
+/* {{{ find_declaration()
+
+ Returns the basic block containing the statement that declares DECL. */
+
+basic_block
+find_declaration (decl)
+ tree decl;
+{
+ int i;
+ tree t;
+ varref first_ref;
+
+ /* Start with the first reference of DECL and walk the flowgraph
+ backwards looking for a node with the scope block declaring the
+ original variable. */
+ first_ref = VARRAY_GENERIC_PTR (TREE_REFS (decl), 0);
+ t = VARREF_STMT (first_ref);
+ for (i = BB_FOR_STMT (t)->index; i >= 0; i--)
+ {
+ basic_block bb = BASIC_BLOCK (i);
+
+ if (TREE_CODE (bb->head_tree) == SCOPE_STMT
+ && SCOPE_STMT_BLOCK (bb->head_tree))
+ {
+ tree block = SCOPE_STMT_BLOCK (bb->head_tree);
+ tree var;
+
+ for (var = BLOCK_VARS (block); var; var = TREE_CHAIN (var))
+ if (var == decl)
+ return bb;
+ }
+ }
+
+ return NULL;
+}
+
+/* }}} */
+
+
/* Debugging functions. */
/* {{{ dump_varref()
@@ -619,16 +706,18 @@ dump_varref (outf, prefix, ref, indent,
fprintf (outf, "%s%s%s(%s): line %d, bb %d, ", s_indent, prefix, type,
sym, lineno, bbix);
- print_node_brief (outf, "", VARREF_EXPR (ref), 0);
+ if (VARREF_EXPR (ref))
+ print_node_brief (outf, "", VARREF_EXPR (ref), 0);
+ else
+ fprintf (outf, "<nil>");
/* Dump specific contents for the different types of references. */
-
if (details)
{
- if (VARREF_TYPE (ref) == VARPHI && VARPHI_CHAIN (ref))
+ if (VARREF_TYPE (ref) == VARPHI && VARDEF_PHI_CHAIN (ref))
{
fputs (" phi-args:\n", outf);
- dump_varref_list (outf, prefix, VARPHI_CHAIN (ref), indent + 4, 0);
+ dump_varref_list (outf, prefix, VARDEF_PHI_CHAIN (ref), indent + 4, 0);
}
else if (VARREF_TYPE (ref) == VARDEF && VARDEF_IMM_USES (ref))
{
@@ -644,8 +733,6 @@ dump_varref (outf, prefix, ref, indent,
}
fputc ('\n', outf);
- if (VARREF_EXPR (ref) == NULL)
- fputc ('\n', outf);
}
/* }}} */
@@ -678,11 +765,14 @@ dump_varref_list (outf, prefix, reflist,
int indent;
int details;
{
- int i;
+ size_t i;
- for (i = 0; reflist && i < VARRAY_ACTIVE_SIZE (reflist); i++)
+ if (reflist == NULL)
+ return;
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (reflist); i++)
dump_varref (outf, prefix, VARRAY_GENERIC_PTR (reflist, i),
- indent, details);
+ indent, details);
}
/* }}} */
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.2.8
diff -d -p -d -u -p -r1.1.2.8 tree-flow.h
--- tree-flow.h 2001/09/14 05:12:57 1.1.2.8
+++ tree-flow.h 2001/09/30 06:11:05
@@ -1,4 +1,4 @@
-/* {{{ Data and Control Flow Analysis for Trees.
+/* Data and Control Flow Analysis for Trees.
Copyright (C) 2001 Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>
@@ -19,8 +19,6 @@ along with GNU CC; see the file COPYING.
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA. */
-/* }}} */
-
#ifndef _TREE_FLOW_H
#define _TREE_FLOW_H 1
@@ -65,10 +63,22 @@ struct vardef
/* Saved definition chain. */
union varref_def *save_chain;
+
+ /* Uses reached by this definition. */
+ varray_type ruses;
+
+ /* Visited mark. Used when computing reaching definitions. */
+ union varref_def *marked;
+
+ /* PHI arguments (not used with real definitions). */
+ varray_type phi_chain;
};
#define VARDEF_IMM_USES(r) (r)->def.imm_uses
#define VARDEF_SAVE_CHAIN(r) (r)->def.save_chain
+#define VARDEF_RUSES(r) (r)->def.ruses
+#define VARDEF_MARKED(r) (r)->def.marked
+#define VARDEF_PHI_CHAIN(r) (r)->def.phi_chain
/* }}} */
@@ -80,23 +90,13 @@ struct varuse
/* Definition chain. */
union varref_def *chain;
-};
-#define VARUSE_CHAIN(r) (r)->use.chain
-
-/* }}} */
-
-/* {{{ PHI terms. */
-
-struct varphi
-{
- struct varref_common common;
-
- /* PHI arguments. */
- varray_type phi_chain;
+ /* Definitions reaching this use. */
+ varray_type rdefs;
};
-#define VARPHI_CHAIN(r) (r)->phi.phi_chain
+#define VARUSE_CHAIN(r) (r)->use.chain
+#define VARUSE_RDEFS(r) (r)->use.rdefs
/* }}} */
@@ -107,7 +107,6 @@ union varref_def
struct varref_common common;
struct vardef def;
struct varuse use;
- struct varphi phi;
};
typedef union varref_def *varref;
@@ -118,6 +117,15 @@ typedef union varref_def *varref;
#define VARREF_STMT(r) (r)->common.stmt
#define VARREF_SYM(r) (r)->common.sym
+/* Return non-zero if R is a ghost definition. */
+#define IS_GHOST_DEF(R) \
+ (R && VARREF_TYPE (R) == VARDEF && VARREF_BB (R) == ENTRY_BLOCK_PTR)
+
+/* Return non-zero if R is an artificial definition (currently, a PHI term
+ or a ghost definition). */
+#define IS_ARTIFICIAL_REF(R) \
+ (IS_GHOST_DEF (R) || VARREF_TYPE (R) == VARPHI)
+
/* }}} */
/* {{{ Tree annotations stored in tree_common.aux. */
@@ -166,19 +174,45 @@ struct bb_ann_def
/* List of references made in this block. */
varray_type refs;
+
+ /* Address into the tree preceeding bb->head_tree that contains a pointer
+ to bb->head_tree. Used when we need to insert statements before the
+ first statement of the block (see insert_stmt_tree_before). */
+ tree *prev_chain_p;
+
+ /* Block that starts the enclosing binding scope for this block. */
+ basic_block binding_scope;
};
typedef struct bb_ann_def *bb_ann;
-#define BB_ANN(BLOCK) \
+#define BB_ANN(BLOCK) \
((bb_ann)((BLOCK)->aux))
#define BB_PARENT(BLOCK) \
((BB_ANN (BLOCK)) ? BB_ANN (BLOCK)->parent : NULL)
-#define BB_REFS(BLOCK) \
+#define BB_REFS(BLOCK) \
((BB_ANN (BLOCK)) ? BB_ANN (BLOCK)->refs : NULL)
+#define BB_PREV_CHAIN_P(BLOCK) \
+ ((BB_ANN (BLOCK)) ? BB_ANN (BLOCK)->prev_chain_p : NULL)
+
+#define BB_BINDING_SCOPE(BLOCK) \
+ ((BB_ANN (BLOCK)) ? BB_ANN (BLOCK)->binding_scope : NULL)
+
+
+/* Accessors for obtaining header blocks of a control statement. */
+#define FOR_INIT_STMT_BB(BLOCK) (BASIC_BLOCK ((BLOCK)->index + 1))
+#define FOR_COND_BB(BLOCK) (BASIC_BLOCK ((BLOCK)->index + 2))
+#define FOR_EXPR_BB(BLOCK) (BASIC_BLOCK ((BLOCK)->index + 3))
+
+#define WHILE_COND_BB(BLOCK) (BASIC_BLOCK ((BLOCK)->index + 1))
+#define DO_COND_BB(BLOCK) (BASIC_BLOCK ((BLOCK)->index + 1))
+
+#define IF_COND_BB(BLOCK) (BASIC_BLOCK ((BLOCK)->index + 1))
+
+#define CASE_COND_BB(BLOCK) (BASIC_BLOCK ((BLOCK)->index + 1))
/* }}} */
/* {{{ Global declarations. */
@@ -187,10 +221,16 @@ typedef struct bb_ann_def *bb_ann;
extern varray_type referenced_symbols;
+/* Accessor macros for referenced_symbols array. */
-/* Nonzero to warn about code which is never reached. */
+#define NREF_SYMBOLS VARRAY_ACTIVE_SIZE (referenced_symbols)
+#define REF_SYMBOL(N) VARRAY_TREE (referenced_symbols, (N))
+#define ADD_REF_SYMBOL(T) VARRAY_PUSH_TREE (referenced_symbols, (T));
-extern int warn_notreached;
+/* Bitmasks to select which function calls to return in get_fcalls(). */
+#define FCALL_NON_PURE (1 << 0)
+#define FCALL_PURE (1 << 1)
+#define FCALL_BUILT_IN (1 << 2)
/* }}} */
@@ -201,6 +241,8 @@ extern void tree_find_basic_blocks PARAM
extern int is_ctrl_stmt PARAMS ((tree));
extern int is_ctrl_altering_stmt PARAMS ((tree));
extern int is_loop_stmt PARAMS ((tree));
+extern tree loop_body PARAMS ((tree));
+extern void set_loop_body PARAMS ((tree, tree));
extern int stmt_ends_bb_p PARAMS ((tree));
extern int stmt_starts_bb_p PARAMS ((tree));
extern void delete_cfg PARAMS ((void));
@@ -214,8 +256,18 @@ extern basic_block loop_parent PARAMS ((
extern basic_block latch_block PARAMS ((basic_block));
extern basic_block switch_parent PARAMS ((basic_block));
extern tree first_exec_stmt PARAMS ((tree));
+extern tree last_exec_stmt PARAMS ((tree));
extern int is_exec_stmt PARAMS ((tree));
+extern int is_statement_expression PARAMS ((tree));
extern void validate_loops PARAMS ((struct loops *));
+extern tree first_non_decl_stmt PARAMS ((tree));
+extern tree first_decl_stmt PARAMS ((tree));
+extern tree first_non_label_in_bb PARAMS ((basic_block));
+extern void insert_stmt_tree_before PARAMS ((tree, tree, basic_block));
+extern void insert_stmt_tree_after PARAMS ((tree, tree, basic_block));
+extern void replace_expr_in_tree PARAMS ((tree, tree, tree));
+extern tree *find_expr_in_tree PARAMS ((tree, tree));
+extern void insert_bb_before PARAMS ((basic_block, basic_block));
/* }}} */
@@ -230,12 +282,18 @@ extern void dump_varref PARAMS ((FILE *,
extern void debug_varref_list PARAMS ((varray_type));
extern void dump_varref_list PARAMS ((FILE *, const char *, varray_type, int,
int));
+extern int function_may_recurse_p PARAMS ((void));
+extern void get_fcalls PARAMS ((varray_type *, unsigned));
+extern basic_block find_declaration PARAMS ((tree));
/* }}} */
/* {{{ Functions in tree-ssa.c */
extern void tree_build_ssa PARAMS ((void));
+extern void tree_compute_rdefs PARAMS ((void));
+extern void analyze_rdefs PARAMS ((void));
+extern int is_upward_exposed PARAMS ((tree, sbitmap, int));
extern void delete_ssa PARAMS ((void));
/* }}} */
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-optimize.c,v
retrieving revision 1.1.2.2
diff -d -p -d -u -p -r1.1.2.2 tree-optimize.c
--- tree-optimize.c 2001/09/14 05:12:57 1.1.2.2
+++ tree-optimize.c 2001/09/30 06:11:05
@@ -43,7 +43,7 @@ optimize_tree (t)
tree t;
{
/* Flush out existing data. */
- VARRAY_TREE_INIT (referenced_symbols, 20, "function_symbols");
+ VARRAY_TREE_INIT (referenced_symbols, 20, "referenced_symbols");
tree_find_basic_blocks (t);
@@ -54,8 +54,9 @@ optimize_tree (t)
}
/* Flush out DFA and SSA data. */
- referenced_symbols = NULL;
delete_cfg ();
+ delete_ssa ();
+ VARRAY_FREE (referenced_symbols);
}
/* }}} */
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.2.6
diff -d -p -d -u -p -r1.1.2.6 tree-ssa.c
--- tree-ssa.c 2001/09/14 05:12:57 1.1.2.6
+++ tree-ssa.c 2001/09/30 06:11:05
@@ -22,6 +22,7 @@ Boston, MA 02111-1307, USA. */
#include "config.h"
#include "system.h"
#include "tree.h"
+#include "flags.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
@@ -30,11 +31,12 @@ Boston, MA 02111-1307, USA. */
#include "errors.h"
#include "expr.h"
#include "c-common.h"
+#include "diagnostic.h"
+#include "toplev.h"
#include "tree-optimize.h"
#include "tree-flow.h"
#include "ssa.h"
-/* {{{ Local declarations. */
/* Dump file and flags. */
static FILE *dump_file;
@@ -44,8 +46,9 @@ static int dump_flags;
static void insert_phi_terms PARAMS ((sbitmap *));
static void build_fud_chains PARAMS ((int *));
static void search_fud_chains PARAMS ((basic_block, int *));
+static void follow_chain PARAMS ((varref, varref));
+static void delete_refs PARAMS ((varray_type));
-/* }}} */
/* {{{ tree_build_ssa()
@@ -60,8 +63,7 @@ tree_build_ssa ()
{
sbitmap *dfs;
int *idom;
-
- dump_file = dump_begin (TDI_ssa, &dump_flags);
+ size_t i;
/* Compute immediate dominators. */
idom = (int *) xmalloc ((size_t) n_basic_blocks * sizeof (int));
@@ -72,7 +74,17 @@ tree_build_ssa ()
dfs = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
compute_dominance_frontiers (dfs, idom);
- /* Insert the PHI nodes and build FUD chains. */
+ /* Insert default definitions (a.k.a. ghost definitions) for all the
+ symbols referenced in the function. This allows the identification of
+ variables that have been used without a preceding definition.
+
+ These definitions do not affect code generation, they are associated
+ with no statement or expression (to distinguish them from actual
+ definitions). */
+ for (i = 0; i < NREF_SYMBOLS; i++)
+ create_varref (REF_SYMBOL (i), VARDEF, ENTRY_BLOCK_PTR, NULL, NULL);
+
+ /* Insert the PHI terms and build FUD chains. */
insert_phi_terms (dfs);
build_fud_chains (idom);
@@ -80,6 +92,8 @@ tree_build_ssa ()
free (idom);
/* Debugging dumps. */
+ dump_file = dump_begin (TDI_ssa, &dump_flags);
+
if (dump_file)
{
int i;
@@ -97,6 +111,8 @@ tree_build_ssa ()
dump_varref_list (dump_file, " ", BB_REFS (bb), 0, 1);
fputs ("\n\n", dump_file);
}
+
+ dump_end (TDI_ssa, dump_file);
}
}
@@ -117,7 +133,7 @@ insert_phi_terms (dfs)
varray_type work_stack;
/* Array ADDED (indexed by basic block number) is used to determine
- whether a phi term for the current variable has already been
+ whether a PHI term for the current variable has already been
inserted at block X. */
VARRAY_TREE_INIT (added, n_basic_blocks, "added");
@@ -130,15 +146,14 @@ insert_phi_terms (dfs)
an assignment or PHI term will be pushed to this stack. */
VARRAY_BB_INIT (work_stack, n_basic_blocks, "work_stack");
- /* Iterate over all referenced symbols in the function. For each
+ /* 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 (i = 0; i < VARRAY_ACTIVE_SIZE (referenced_symbols); i++)
+ for (i = 0; i < NREF_SYMBOLS; i++)
{
size_t j;
- tree sym = VARRAY_TREE (referenced_symbols, i);
+ tree sym = REF_SYMBOL (i);
varray_type refs = TREE_REFS (sym);
/* Symbols in referenced_symbols must have at least 1 reference. */
@@ -147,20 +162,20 @@ insert_phi_terms (dfs)
for (j = 0; j < VARRAY_ACTIVE_SIZE (refs); j++)
{
- basic_block bb;
varref ref = VARRAY_GENERIC_PTR (refs, j);
+ basic_block bb = VARREF_BB (ref);
- if (VARREF_TYPE (ref) != VARDEF)
+ /* Ignore ghost definitions in ENTRY_BLOCK_PTR. */
+ if (VARREF_TYPE (ref) != VARDEF || IS_GHOST_DEF (ref))
continue;
- bb = VARREF_BB (ref);
VARRAY_PUSH_BB (work_stack, bb);
VARRAY_TREE (in_work, bb->index) = sym;
}
while (VARRAY_ACTIVE_SIZE (work_stack) > 0)
{
- int w;
+ size_t w;
basic_block bb;
bb = VARRAY_TOP_BB (work_stack);
@@ -219,18 +234,8 @@ build_fud_chains (idom)
size_t i;
/* Initialize the current definition for all the symbols. */
-
- for (i = 0; i < VARRAY_ACTIVE_SIZE (referenced_symbols); i++)
- {
- tree sym = VARRAY_TREE (referenced_symbols, i);
- tree_ann ann = TREE_ANN (sym);
-
- /* Symbols in ref_symbols_list must have at least 1 reference. */
- if (ann == NULL)
- abort ();
-
- ann->currdef = NULL;
- }
+ for (i = 0; i < NREF_SYMBOLS; i++)
+ get_tree_ann (REF_SYMBOL (i))->currdef = NULL;
/* Search FUD chains starting with the entry block. */
search_fud_chains (ENTRY_BLOCK_PTR, idom);
@@ -262,7 +267,6 @@ search_fud_chains (bb, idom)
CurrDef(SYM) = R
endif
endfor */
-
bb_refs = BB_REFS (bb);
nrefs = (bb_refs) ? VARRAY_ACTIVE_SIZE (bb_refs) : 0;
for (r = 0; r < nrefs; r++)
@@ -278,22 +282,14 @@ search_fud_chains (bb, idom)
{
VARUSE_CHAIN (ref) = currdef;
- /* Besides setting a link back to our immediate control
- reaching definition (whether a PHI term or an actual
- definition), we want to link that definition to its
- immediate use.
-
- If this use (ref) has a current definition (currdef), we
- add 'ref' to the list of uses immediately reached by
- 'currdef'. */
+ /* Besides setting a link back to our immediate reaching
+ definition, we want to link that definition to its immediate
+ use.
+ If this use (ref) has a current definition (currdef), add
+ 'ref' to the list of uses immediately reached by 'currdef'. */
if (currdef)
- {
- if (VARDEF_IMM_USES (currdef) == NULL)
- VARRAY_GENERIC_PTR_INIT (VARDEF_IMM_USES (currdef),
- 10, "imm_uses");
- VARRAY_PUSH_GENERIC_PTR (VARDEF_IMM_USES (currdef), ref);
- }
+ VARRAY_PUSH_GENERIC_PTR (VARDEF_IMM_USES (currdef), ref);
}
else if (VARREF_TYPE (ref) == VARDEF || VARREF_TYPE (ref) == VARPHI)
{
@@ -312,7 +308,6 @@ search_fud_chains (bb, idom)
phi-chain(R)[J] = CurrDef(SYM)
endfor
endfor */
-
for (e = bb->succ; e; e = e->succ_next)
{
varray_type y_refs;
@@ -321,7 +316,7 @@ search_fud_chains (bb, idom)
y = e->dest;
y_refs = BB_REFS (y);
if (y_refs == NULL)
- break;
+ continue;
for (r = 0; r < VARRAY_ACTIVE_SIZE (y_refs); r++)
{
@@ -336,12 +331,7 @@ search_fud_chains (bb, idom)
currdef = TREE_CURRDEF (sym);
if (currdef)
- {
- if (VARPHI_CHAIN (phi) == NULL)
- VARRAY_GENERIC_PTR_INIT (VARPHI_CHAIN (phi), 2, "phi_chain");
-
- VARRAY_PUSH_GENERIC_PTR (VARPHI_CHAIN (phi), currdef);
- }
+ VARRAY_PUSH_GENERIC_PTR (VARDEF_PHI_CHAIN (phi), currdef);
}
}
@@ -349,7 +339,6 @@ search_fud_chains (bb, idom)
/* for Y in Child(BB) do <-- Child(BB) is the set of dominator
Search(Y) children of BB in the dominator tree.
endfor */
-
for (i = 0; i < n_basic_blocks; i++)
{
if (idom[i] == bb->index)
@@ -363,7 +352,6 @@ search_fud_chains (bb, idom)
CurrDef(SYM) = SaveChain(R)
endif
endfor */
-
for (i = nrefs - 1; i >= 0; i--)
{
varref ref = VARRAY_GENERIC_PTR (bb_refs, i);
@@ -381,6 +369,269 @@ search_fud_chains (bb, idom)
ann->currdef = VARDEF_SAVE_CHAIN (ref);
}
}
+}
+
+/* }}} */
+
+/* {{{ delete_ssa()
+
+ Deallocate memory associated with SSA data structures. */
+
+void
+delete_ssa ()
+{
+ size_t i;
+
+ for (i = 0; i < NREF_SYMBOLS; i++)
+ delete_refs (TREE_REFS (REF_SYMBOL (i)));
+}
+
+/* Deallocate memory associated with an array of references. */
+
+static void
+delete_refs (refs)
+ varray_type refs;
+{
+ size_t i;
+
+ if (refs == NULL)
+ return;
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (refs); i++)
+ {
+ varref ref = VARRAY_GENERIC_PTR (refs, i);
+
+ if (VARREF_TYPE (ref) == VARDEF)
+ {
+ VARRAY_FREE (VARDEF_IMM_USES (ref));
+ VARRAY_FREE (VARDEF_RUSES (ref));
+ VARRAY_FREE (VARDEF_PHI_CHAIN (ref));
+ }
+ else if (VARREF_TYPE (ref) == VARUSE)
+ VARRAY_FREE (VARUSE_RDEFS (ref));
+ }
+
+ VARRAY_FREE (refs);
+}
+
+/* }}} */
+
+
+/* Reaching definitions. */
+
+/* {{{ tree_compute_rdefs()
+
+ Computes reaching definitions and reached uses for all the variables
+ referenced in the current function. */
+
+void
+tree_compute_rdefs ()
+{
+ size_t i, j;
+
+ /* Initialize reaching definition and reached uses information for every
+ reference in the function. */
+ for (i = 0; i < NREF_SYMBOLS; i++)
+ {
+ tree sym = REF_SYMBOL (i);
+ varray_type refs = TREE_REFS (sym);
+
+ for (j = 0; j < VARRAY_ACTIVE_SIZE (refs); j++)
+ {
+ varref r = VARRAY_GENERIC_PTR (refs, j);
+
+ if (VARREF_TYPE (r) == VARUSE)
+ VARRAY_POP_ALL (VARUSE_RDEFS (r));
+ else if (VARREF_TYPE (r) == VARDEF)
+ VARRAY_POP_ALL (VARDEF_RUSES (r));
+ }
+ }
+
+ /* Traverse all the uses following their use-def chains looking for
+ reaching definitions and reached uses. */
+ for (i = 0; i < NREF_SYMBOLS; i++)
+ {
+ tree sym = REF_SYMBOL (i);
+ varray_type refs = TREE_REFS (sym);
+
+ for (j = 0; j < VARRAY_ACTIVE_SIZE (refs); j++)
+ {
+ varref u = VARRAY_GENERIC_PTR (refs, j);
+
+ if (VARREF_TYPE (u) == VARUSE)
+ follow_chain (VARUSE_CHAIN (u), u);
+ }
+ }
+
+
+ analyze_rdefs ();
+
+ /* Debugging dumps. */
+ dump_file = dump_begin (TDI_ssa, &dump_flags);
+
+ if (dump_file && (dump_flags & TDF_RDEFS))
+ {
+ fprintf (dump_file, ";; Function %s\n\n",
+ IDENTIFIER_POINTER (DECL_NAME (current_function_decl)));
+
+ fprintf (dump_file, "Reaching definitions:\n");
+
+ for (i = 0; i < NREF_SYMBOLS; i++)
+ {
+ tree sym = REF_SYMBOL (i);
+ varray_type refs = TREE_REFS (sym);
+
+ fprintf (dump_file, "Symbol: ");
+ print_node_brief (dump_file, "", sym, 0);
+ fprintf (dump_file, "\n");
+
+ for (j = 0; j < VARRAY_ACTIVE_SIZE (refs); j++)
+ {
+ varref u = VARRAY_GENERIC_PTR (refs, j);
+
+ if (VARREF_TYPE (u) == VARUSE)
+ {
+ dump_varref (dump_file, "", u, 4, 0);
+ dump_varref_list (dump_file, "", VARUSE_RDEFS (u), 6, 0);
+ fprintf (dump_file, "\n");
+ }
+ }
+ fprintf (dump_file, "\n");
+ }
+
+ dump_end (TDI_ssa, dump_file);
+ }
+}
+
+/* }}} */
+
+/* {{{ analyze_rdefs()
+
+ Analyze reaching definition information and warn about uses of potentially
+ uninitialized variables. */
+
+void
+analyze_rdefs ()
+{
+ size_t i;
+ sbitmap blocks;
+
+ if (warn_uninitialized == 0)
+ return;
+
+ blocks = sbitmap_alloc (n_basic_blocks);
+ sbitmap_ones (blocks);
+
+ for (i = 0; i < NREF_SYMBOLS; i++)
+ {
+ tree sym = REF_SYMBOL (i);
+
+ if (TREE_CODE (sym) == VAR_DECL
+ && DECL_CONTEXT (sym) != NULL
+ && ! TREE_STATIC (sym)
+ && is_upward_exposed (sym, blocks, 0))
+ {
+ if (! TREE_ADDRESSABLE (sym))
+ warning_with_decl (sym,
+ "`%s' is used uninitialized in this function");
+ else
+ warning_with_decl (sym,
+ "`%s' may be used uninitialized in this function");
+ }
+ }
+}
+
+/* }}} */
+
+/* {{{ follow_chain()
+
+ Follows the factored use-def links to find all possible reaching
+ definitions for U, starting with D. This also updates reached uses for
+ each reaching definition found. */
+
+static void
+follow_chain (d, u)
+ varref d;
+ varref u;
+{
+ /* Do nothing if the definition doesn't exist. */
+ if (d == NULL)
+ return;
+
+ /* Consistency check. D should be a definition or a PHI term. */
+ if (VARREF_TYPE (d) != VARDEF && VARREF_TYPE (d) != VARPHI)
+ abort ();
+
+ /* Do nothing if we've already visited this definition. */
+ if (VARDEF_MARKED (d) == u)
+ return;
+
+ VARDEF_MARKED (d) = u;
+
+ /* If D is a definition for U, add it to the list of definitions reaching
+ U. Similarly, add U to the list of reached uses of D. */
+ if (VARREF_TYPE (d) == VARDEF && VARREF_SYM (d) == VARREF_SYM (u))
+ {
+ VARRAY_PUSH_GENERIC_PTR (VARUSE_RDEFS (u), d);
+ VARRAY_PUSH_GENERIC_PTR (VARDEF_RUSES (d), u);
+ }
+
+ /* If D is a PHI term, recursively follow each of its arguments. */
+ if (VARREF_TYPE (d) == VARPHI)
+ {
+ size_t i;
+ varray_type phi_chain = VARDEF_PHI_CHAIN (d);
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (phi_chain); i++)
+ follow_chain (VARRAY_GENERIC_PTR (phi_chain, i), u);
+ }
+}
+
+/* }}} */
+
+/* {{{ is_upward_exposed()
+
+ Return 1 if one or more uses of SYM in BB_SET have reaching definitions
+ coming from blocks outside BB_SET. If EXCLUDE_INIT_DECL is non-zero,
+ the initializer expression used in the declaration of SYM will always be
+ considered external to BB_SET. */
+
+int
+is_upward_exposed (sym, bb_set, exclude_init_decl)
+ tree sym;
+ sbitmap bb_set;
+ int exclude_init_decl;
+{
+ size_t i;
+ varray_type refs = TREE_REFS (sym);
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (refs); i++)
+ {
+ varref r = VARRAY_GENERIC_PTR (refs, i);
+
+ /* If this is a use of symbol in one of the basic blocks we are
+ interested in, check its reaching definitions. */
+ if (VARREF_TYPE (r) == VARUSE
+ && TEST_BIT (bb_set, VARREF_BB (r)->index))
+ {
+ size_t j;
+ varray_type rdefs = VARUSE_RDEFS (r);
+
+ for (j = 0; j < VARRAY_ACTIVE_SIZE (rdefs); j++)
+ {
+ varref def = VARRAY_GENERIC_PTR (rdefs, j);
+ basic_block def_bb = VARREF_BB (def);
+
+ if (IS_GHOST_DEF (def)
+ || (exclude_init_decl
+ && TREE_CODE (VARREF_STMT (def)) == DECL_STMT)
+ || ! TEST_BIT (bb_set, def_bb->index))
+ return 1;
+ }
+ }
+ }
+
+ return 0;
}
/* }}} */
Index: testsuite/lib/c-torture.exp
===================================================================
RCS file: /cvs/gcc/gcc/gcc/testsuite/lib/c-torture.exp,v
retrieving revision 1.16
diff -d -p -d -u -p -r1.16 c-torture.exp
--- testsuite/lib/c-torture.exp 2000/11/19 09:35:54 1.16
+++ testsuite/lib/c-torture.exp 2001/09/30 06:11:13
@@ -33,14 +33,14 @@ if ![info exists TORTURE_OPTIONS] {
# items below, even though -O3 is also specified, because some ports may
# choose to disable inlining functions by default, even when optimizing.
set TORTURE_OPTIONS [list \
- { -O0 } \
- { -O1 } \
- { -O2 } \
- { -O3 -fomit-frame-pointer } \
- { -O3 -fomit-frame-pointer -funroll-loops } \
- { -O3 -fomit-frame-pointer -funroll-all-loops -finline-functions } \
- { -O3 -g } \
- { -Os } ]
+ { -O0 -ftree-ssa -Wunreachable-code } \
+ { -O1 -ftree-ssa -Wunreachable-code } \
+ { -O2 -ftree-ssa -Wunreachable-code } \
+ { -O3 -fomit-frame-pointer -ftree-ssa -Wunreachable-code } \
+ { -O3 -fomit-frame-pointer -funroll-loops -ftree-ssa -Wunreachable-code } \
+ { -O3 -fomit-frame-pointer -funroll-all-loops -finline-functions -ftree-ssa -Wunreachable-code } \
+ { -O3 -g -ftree-ssa -Wunreachable-code } \
+ { -Os -ftree-ssa -Wunreachable-code } ]
}