This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[ast-optimizer-branch] Use variable arrays [patch]
- To: gcc-patches at gcc dot gnu dot org
- Subject: [ast-optimizer-branch] Use variable arrays [patch]
- From: Diego Novillo <dnovillo at redhat dot com>
- Date: Fri, 14 Sep 2001 01:22:17 -0400
- Organization: Red Hat Canada
This patch is clean-up needed for new functions to compute
reaching definition and reached uses (I didn't want to mix two
different things in the same patch).
This removes redundant code to manage lists of variable
references. We now use variable arrays instead.
Bootstrapped on x86.
Diego.
2001-09-14 Diego Novillo <dnovillo@redhat.com>
* tree-cfg.c (tree_find_basic_blocks): Remove call to
mark_critical_edges.
(create_maximal_bb): Do not create annotations for non-executable
statements.
(map_stmt_to_bb): Rename basic_block_ann with bb_ann.
(delete_cfg): Ditto.
(is_exec_stmt): Reformat.
(create_bb_ann): New function.
* tree-dfa.c (create_node): Remove.
(ref_symbols_list): Remove.
(create_tree_ann): Declare.
(referenced_symbols): Declare.
(tree_find_varrefs): Replace usage of linked lists with variable
arrays.
(create_varref): Remove second argument from call to
add_ref_symbol.
Update comments.
(add_ref_to_sym): Replace usage of linked lists with variable
arrays.
Declare static.
(add_ref_to_bb): Ditto.
(add_ref_symbol): Ditto.
(dump_varref_list): Ditto.
(debug_varref_list): Ditto.
(create_varref_list): Remove.
(push_ref): Remove.
(create_node): Remove.
(delete_varref_list): Remove.
(get_tree_ann): Call create_tree_ann if the tree doesn't have an
annotation already.
(create_tree_ann): New function.
* tree-flow.h (varref_list_def): Remove.
(vardef): Change type of field 'imm_uses' to 'varray_type'.
(varphi): Change type of field 'phi_chain' to 'varray_type'.
(varref_node_def): Remove.
(varref_node): Remove.
(VARREF_NODE_ELEM): Remove.
(VARREF_NODE_NEXT): Remove.
(VARREF_NODE_PREV): Remove.
(varref_list_def): Remove.
(varref_list): Remove.
(VARREF_LIST_FIRST): Remove.
(VARREF_LIST_LAST): Remove.
(tree_ann_def): Change type of field 'refs' to 'varray_type'.
(basic_block_ann_def): Rename to 'bb_ann_def'.
Change type of field 'refs' to 'varray_type'.
(basic_block_ann): Rename to 'bb_ann'.
(ref_symbols_list): Remove.
(referenced_symbols): Declare.
(add_ref_to_sym): Remove.
(add_ref_to_bb): Remove.
(add_ref_symbol): Remove.
(remove_ann_from_sym): Remove.
(create_varref_list): Remove.
(push_ref): Remove.
(delete_varref_list): Remove.
(debug_varref_list): Update argument type to be 'varray_type'.
(dump_varref_list): Ditto.
* tree-optimize.c: Include 'basic-block.h'.
(optimize_tree): Replace references to 'ref_symbols_list' with
'referenced_symbols'.
Remove call to delete_varref_list.
* tree-ssa.c (insert_phi_terms): Rename 'work_list' to
'work_stack'.
Use VARRAY_PUSH and VARRAY_TOP to access 'work_stack' instead of
maintaining the stack pointer in 'work_list_top'.
Remove code to grow 'work_stack'.
Remove references to 'work_list_top'.
Replace references to 'ref_symbols_list' with 'referenced_symbols'.
(build_fud_chains): Replace references to 'ref_symbols_list' with
'referenced_symbols'.
(search_fud_chains): If there are no variable references in the
basic block, return early.
Change usage of linked lists with variable arrays.
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.2.6
diff -d -p -d -u -p -r1.1.2.6 tree-cfg.c
--- tree-cfg.c 2001/09/07 18:09:53 1.1.2.6
+++ tree-cfg.c 2001/09/14 05:03:59
@@ -76,6 +76,7 @@ static void make_return_stmt_edges PARAM
/* Various helpers. */
static basic_block successor_block PARAMS ((basic_block));
static int block_invalidates_loop PARAMS ((basic_block, struct loop *));
+static void create_bb_ann PARAMS ((basic_block));
/* }}} */
@@ -108,8 +109,6 @@ tree_find_basic_blocks (t)
/* Create the edges of the flowgraph. */
make_edges ();
- mark_critical_edges ();
-
/* Write the flowgraph to a GraphViz file. */
if (dot_dump_file)
tree_cfg2dot (dot_dump_file);
@@ -338,16 +337,15 @@ create_maximal_bb (t, control_parent, co
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;
- }
+ {
+ get_tree_ann (last)->compound_stmt = compound_stmt;
+ map_stmt_to_bb (last, bb);
+ bb->end_tree = last;
+ }
if (stmt_ends_bb_p (last))
- break;
+ break;
last = TREE_CHAIN (last);
}
@@ -428,21 +426,30 @@ map_stmt_to_bb (t, bb)
Get the annotation for the given block. Create a new one if
necessary. */
-basic_block_ann
+bb_ann
get_bb_ann (bb)
basic_block bb;
{
- basic_block_ann ann = BB_ANN (bb);
+ if (BB_ANN (bb) == NULL)
+ create_bb_ann (bb);
- if (ann == NULL)
- {
- ann = (basic_block_ann) ggc_alloc (sizeof (*ann));
- memset ((void *) ann, 0, sizeof (*ann));
+ return BB_ANN (bb);
+}
- bb->aux = (void *) ann;
- }
+/* }}} */
- return ann;
+/* {{{ create_bb_ann()
+
+ Create a new annotation for basic block BB. */
+
+static void
+create_bb_ann (bb)
+ basic_block bb;
+{
+ bb_ann ann = (bb_ann) ggc_alloc (sizeof (*ann));
+ memset ((void *) ann, 0, sizeof (*ann));
+ VARRAY_GENERIC_PTR_INIT (ann->refs, 10, "bb_refs");
+ bb->aux = (void *) ann;
}
/* }}} */
@@ -1252,7 +1259,7 @@ delete_cfg ()
for (i = 0; i < n_basic_blocks; i++)
{
- basic_block_ann ann = BB_ANN (BASIC_BLOCK (i));
+ bb_ann ann = BB_ANN (BASIC_BLOCK (i));
ann->parent = NULL;
ann->refs = NULL;
BASIC_BLOCK (i)->aux = NULL;
@@ -1376,11 +1383,11 @@ first_exec_stmt (t)
int
is_exec_stmt (t)
- tree t;
+ tree t;
{
return (t
- && statement_code_p (TREE_CODE (t))
- && TREE_CODE (t) != COMPOUND_STMT && TREE_CODE (t) != SCOPE_STMT);
+ && statement_code_p (TREE_CODE (t))
+ && TREE_CODE (t) != COMPOUND_STMT && TREE_CODE (t) != SCOPE_STMT);
}
/* }}} */
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.2.6
diff -d -p -d -u -p -r1.1.2.6 tree-dfa.c
--- tree-dfa.c 2001/09/06 22:57:15 1.1.2.6
+++ tree-dfa.c 2001/09/14 05:03:59
@@ -40,21 +40,23 @@ Boston, MA 02111-1307, USA. */
static FILE *dump_file;
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 varref_node create_node PARAMS ((varref));
+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 symbols. */
+/* {{{ Global declarations. */
-/* List of all symbols referenced in the function. */
+/* Array of all symbols referenced in the function. */
-tree ref_symbols_list;
+varray_type referenced_symbols;
/* }}} */
@@ -97,16 +99,16 @@ tree_find_varrefs ()
/* Debugging dumps. */
if (dump_file && (dump_flags & TDF_REFS))
{
- tree sym_n;
+ int i;
- fprintf (dump_file, ";; Function %s\n\n",
+ fprintf (dump_file, ";; Function %s\n\n",
IDENTIFIER_POINTER (DECL_NAME (current_function_decl)));
fprintf (dump_file, "Symbols referenced:\n");
- for (sym_n = ref_symbols_list; sym_n; sym_n = TREE_CHAIN (sym_n))
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (referenced_symbols); i++)
{
- tree sym = TREE_VALUE (sym_n);
+ tree sym = VARRAY_TREE (referenced_symbols, i);
print_node_brief (dump_file, "\t", sym, 0);
fputc ('\n', dump_file);
dump_varref_list (dump_file, "\t", TREE_REFS (sym), 4, 1);
@@ -472,13 +474,11 @@ create_varref (sym, ref_type, bb, parent
VARREF_BB (ref) = bb;
VARREF_EXPR (ref) = parent_expr;
- /* Add the symbol to the global list of referenced symbols. On
- return, IS_NEW will be 1 if this is the first time we see this
- symbol. */
- is_new = add_ref_symbol (sym, &ref_symbols_list);
+ /* 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, is_new);
+ add_ref_to_sym (ref, sym);
/* Add this reference to the list of references for the basic block. */
add_ref_to_bb (ref, bb);
@@ -493,32 +493,12 @@ create_varref (sym, ref_type, bb, parent
Adds reference REF to the list of references made to symbol SYM. */
void
-add_ref_to_sym (ref, sym, is_new)
+add_ref_to_sym (ref, sym)
varref ref;
tree sym;
- int is_new;
{
- tree_ann ann = TREE_ANN (sym);
- varref_list ref_list = TREE_REFS (sym);
-
- if (ann && ref_list)
- {
- /* Sanity check. If the symbol has annotations but we think
- it's new, then something is wrong. */
- if (is_new)
- abort ();
-
- push_ref (ref_list, ref);
- }
- else
- {
- /* Similar sanity check. If the symbol has no annotations nor
- references, there is something wrong. */
- if (!is_new && TREE_ANN (sym) == NULL)
- abort ();
-
- get_tree_ann (sym)->refs = create_varref_list (ref);
- }
+ tree_ann ann = get_tree_ann (sym);
+ VARRAY_PUSH_GENERIC_PTR (ann->refs, ref);
}
/* }}} */
@@ -532,193 +512,66 @@ add_ref_to_bb (ref, bb)
varref ref;
basic_block bb;
{
- if (BB_ANN (bb) && BB_REFS (bb))
- push_ref (BB_REFS (bb), ref);
- else
- get_bb_ann (bb)->refs = create_varref_list (ref);
+ 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 symbols LISTP. */
+ Adds a unique copy of symbol SYM to the list of referenced symbols. */
-int
-add_ref_symbol (sym, listp)
+static void
+add_ref_symbol (sym)
tree sym;
- tree *listp;
{
- int is_new = 0;
- tree node = build_tree_list (NULL_TREE, sym);
-
- if (*listp == NULL_TREE)
- {
- *listp = node;
- is_new = 1;
- }
- else
- {
- tree last;
- tree list = *listp;
-
- if (!chain_member_value (sym, list))
- {
- /* Add a new symbol to the list. */
- last = tree_last (list);
- TREE_CHAIN (last) = node;
- is_new = 1;
- }
- }
-
- return is_new;
-}
-
-/* }}} */
-
-/* {{{ remove_ann_from_sym()
-
- Clear the annotations made to symbol SYM. */
+ int i;
-void
-remove_ann_from_sym (sym)
- tree sym;
-{
- tree_ann ann = TREE_ANN (sym);
+ /* 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)
+ return;
- if (ann)
- {
- ann->bb = NULL;
- ann->refs = NULL;
- ann->currdef = NULL;
- sym->common.aux = NULL;
- }
+ /* 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);
+ create_tree_ann (sym);
}
/* }}} */
-/* Manage annotations and lists of references. */
+/* Manage annotations. */
/* {{{ get_tree_ann()
- Get the annotation for the given tree. Create a new one if necessary. */
+ Get the annotation for the given tree. Create a new one if necessary. */
tree_ann
get_tree_ann (t)
tree t;
-{
- tree_ann ann = TREE_ANN (t);
-
- if (ann == NULL)
- {
- ann = (tree_ann) ggc_alloc (sizeof (*ann));
- memset ((void *) ann, 0, sizeof (*ann));
- t->common.aux = (void *) ann;
- }
-
- return ann;
-}
-
-/* }}} */
-
-/* {{{ create_varref_list()
-
- Create a new list of variable references. */
-
-varref_list
-create_varref_list (ref)
- varref ref;
-{
- varref_list list;
- varref_node node;
-
- if (ref == NULL)
- abort ();
-
- list = (varref_list) ggc_alloc (sizeof (*list));
- memset ((void *) list, 0, sizeof (*list));
-
- node = create_node (ref);
-
- list->first = node;
- list->last = node;
-
- return list;
-}
-
-/* }}} */
-
-/* {{{ push_ref()
-
- Push a variable reference to the end of the list. */
-
-void
-push_ref (list, ref)
- varref_list list;
- varref ref;
-{
- varref_node node, last;
-
- if (ref == NULL || list == NULL)
- abort ();
-
- node = create_node (ref);
-
- last = VARREF_LIST_LAST (list);
- last->next = node;
- node->prev = last;
- list->last = node;
-}
-
-/* }}} */
-
-/* {{{ create_node()
-
- Create a node holder for a varref object. */
-
-static varref_node
-create_node (ref)
- varref ref;
{
- varref_node node;
-
- if (ref == NULL)
- abort ();
-
- node = (varref_node) ggc_alloc (sizeof (*node));
- memset ((void *) node, 0, sizeof (*node));
-
- node->elem = ref;
+ if (TREE_ANN (t) == NULL)
+ create_tree_ann (t);
- return node;
+ return TREE_ANN (t);
}
/* }}} */
-/* {{{ delete_varref_list()
+/* {{{ create_tree_ann()
- Delete all the references to the symbols in *SYMLIST_P. */
+ Create a new annotation for tree T. */
-void
-delete_varref_list (symlist_p)
- tree *symlist_p;
+static void
+create_tree_ann (t)
+ tree t;
{
- tree sym_n;
- tree symlist;
-
- if (symlist_p == NULL)
- abort ();
-
- symlist = *symlist_p;
-
- for (sym_n = symlist; sym_n; sym_n = TREE_CHAIN (sym_n))
- {
- tree sym = TREE_VALUE (sym_n);
- remove_ann_from_sym (sym);
- }
-
- *symlist_p = NULL;
+ tree_ann ann = (tree_ann) ggc_alloc (sizeof (*ann));
+ memset ((void *) ann, 0, sizeof (*ann));
+ VARRAY_GENERIC_PTR_INIT (ann->refs, 10, "symbol_refs");
+ t->common.aux = (void *) ann;
}
/* }}} */
@@ -821,14 +674,15 @@ void
dump_varref_list (outf, prefix, reflist, indent, details)
FILE *outf;
const char *prefix;
- varref_list reflist;
+ varray_type reflist;
int indent;
int details;
{
- varref_node v;
+ int i;
- for (v = VARREF_LIST_FIRST (reflist); v; v = VARREF_NODE_NEXT (v))
- dump_varref (outf, prefix, VARREF_NODE_ELEM (v), indent, details);
+ for (i = 0; reflist && i < VARRAY_ACTIVE_SIZE (reflist); i++)
+ dump_varref (outf, prefix, VARRAY_GENERIC_PTR (reflist, i),
+ indent, details);
}
/* }}} */
@@ -839,7 +693,7 @@ dump_varref_list (outf, prefix, reflist,
void
debug_varref_list (reflist)
- varref_list reflist;
+ varray_type reflist;
{
dump_varref_list (stderr, "", reflist, 0, 1);
}
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.2.7
diff -d -p -d -u -p -r1.1.2.7 tree-flow.h
--- tree-flow.h 2001/09/07 18:09:53 1.1.2.7
+++ tree-flow.h 2001/09/14 05:03:59
@@ -26,10 +26,8 @@ Boston, MA 02111-1307, USA. */
/* {{{ Types of references. */
-enum varref_type
-{ VARDEF, VARUSE, VARPHI };
+enum varref_type { VARDEF, VARUSE, VARPHI };
-struct varref_list_def;
union varref_def;
/* }}} */
@@ -63,7 +61,7 @@ struct vardef
struct varref_common common;
/* Immediate uses for this definition. */
- struct varref_list_def *imm_uses;
+ varray_type imm_uses;
/* Saved definition chain. */
union varref_def *save_chain;
@@ -95,7 +93,7 @@ struct varphi
struct varref_common common;
/* PHI arguments. */
- struct varref_list_def *phi_chain;
+ varray_type phi_chain;
};
#define VARPHI_CHAIN(r) (r)->phi.phi_chain
@@ -122,35 +120,6 @@ typedef union varref_def *varref;
/* }}} */
-/* {{{ Container types for variable references. */
-
-struct varref_node_def
-{
- varref elem;
- struct varref_node_def *next;
- struct varref_node_def *prev;
-};
-
-typedef struct varref_node_def *varref_node;
-
-#define VARREF_NODE_ELEM(n) ((n) ? (n)->elem : NULL)
-#define VARREF_NODE_NEXT(n) ((n) ? (n)->next : NULL)
-#define VARREF_NODE_PREV(n) ((n) ? (n)->prev : NULL)
-
-
-struct varref_list_def
-{
- varref_node first;
- varref_node last;
-};
-
-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)
-
-/* }}} */
-
/* {{{ Tree annotations stored in tree_common.aux. */
struct tree_ann_def
@@ -159,7 +128,7 @@ struct tree_ann_def
basic_block bb;
/* For _DECL trees, list of references made to this variable. */
- varref_list refs;
+ varray_type refs;
/* Most recent definition for this symbol. Used when placing FUD
chains. */
@@ -190,19 +159,19 @@ typedef struct tree_ann_def *tree_ann;
/* {{{ Block annotations stored in basic_block.aux. */
-struct basic_block_ann_def
+struct bb_ann_def
{
/* Control flow parent. */
basic_block parent;
/* List of references made in this block. */
- varref_list refs;
+ varray_type refs;
};
-typedef struct basic_block_ann_def *basic_block_ann;
+typedef struct bb_ann_def *bb_ann;
#define BB_ANN(BLOCK) \
- ((basic_block_ann)((BLOCK)->aux))
+ ((bb_ann)((BLOCK)->aux))
#define BB_PARENT(BLOCK) \
((BB_ANN (BLOCK)) ? BB_ANN (BLOCK)->parent : NULL)
@@ -212,11 +181,11 @@ typedef struct basic_block_ann_def *basi
/* }}} */
-/* {{{ Global symbols. */
+/* {{{ Global declarations. */
-/* List of all symbols referenced in the function. */
+/* Array of all symbols referenced in the function. */
-extern tree ref_symbols_list;
+extern varray_type referenced_symbols;
/* Nonzero to warn about code which is never reached. */
@@ -235,7 +204,7 @@ extern int is_loop_stmt PARAMS ((tree));
extern int stmt_ends_bb_p PARAMS ((tree));
extern int stmt_starts_bb_p PARAMS ((tree));
extern void delete_cfg PARAMS ((void));
-extern basic_block_ann get_bb_ann PARAMS ((basic_block));
+extern bb_ann get_bb_ann PARAMS ((basic_block));
extern void tree_dump_bb PARAMS ((FILE *, const char *, basic_block, int));
extern void tree_debug_bb PARAMS ((basic_block));
extern void tree_dump_cfg PARAMS ((FILE *));
@@ -253,20 +222,13 @@ extern void validate_loops PARAMS ((stru
/* {{{ 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 *));
-extern void remove_ann_from_sym PARAMS ((tree));
extern tree_ann get_tree_ann PARAMS ((tree));
extern varref create_varref PARAMS ((tree, enum varref_type,
basic_block, tree, tree));
-extern varref_list create_varref_list PARAMS ((varref));
-extern void push_ref PARAMS ((varref_list, varref));
-extern void delete_varref_list PARAMS ((tree *));
extern void debug_varref PARAMS ((varref));
extern void dump_varref PARAMS ((FILE *, const char *, varref, int, int));
-extern void debug_varref_list PARAMS ((varref_list));
-extern void dump_varref_list PARAMS ((FILE *, const char *, varref_list, int,
+extern void debug_varref_list PARAMS ((varray_type));
+extern void dump_varref_list PARAMS ((FILE *, const char *, varray_type, int,
int));
/* }}} */
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-optimize.c,v
retrieving revision 1.1.2.1
diff -d -p -d -u -p -r1.1.2.1 tree-optimize.c
--- tree-optimize.c 2001/08/27 15:52:13 1.1.2.1
+++ tree-optimize.c 2001/09/14 05:03:59
@@ -30,6 +30,7 @@ Boston, MA 02111-1307, USA. */
#include "expr.h"
#include "c-common.h"
#include "diagnostic.h"
+#include "basic-block.h"
#include "tree-optimize.h"
#include "tree-flow.h"
@@ -42,7 +43,7 @@ optimize_tree (t)
tree t;
{
/* Flush out existing data. */
- ref_symbols_list = NULL;
+ VARRAY_TREE_INIT (referenced_symbols, 20, "function_symbols");
tree_find_basic_blocks (t);
@@ -53,7 +54,7 @@ optimize_tree (t)
}
/* Flush out DFA and SSA data. */
- delete_varref_list (&ref_symbols_list);
+ referenced_symbols = NULL;
delete_cfg ();
}
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.2.5
diff -d -p -d -u -p -r1.1.2.5 tree-ssa.c
--- tree-ssa.c 2001/08/27 15:52:13 1.1.2.5
+++ tree-ssa.c 2001/09/14 05:03:59
@@ -111,11 +111,10 @@ static void
insert_phi_terms (dfs)
sbitmap *dfs;
{
- tree m;
+ size_t i;
varray_type added;
varray_type in_work;
- varray_type work_list;
- size_t work_list_top;
+ 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
@@ -123,56 +122,49 @@ insert_phi_terms (dfs)
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
+ whether block X has already been added to WORK_STACK 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;
+ /* Array WORK_STACK is a stack of CFG blocks. Each block that contains
+ 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
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))
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (referenced_symbols); i++)
{
- varref_node i;
- tree sym = TREE_VALUE (m);
+ size_t j;
+ tree sym = VARRAY_TREE (referenced_symbols, i);
+ varray_type refs = TREE_REFS (sym);
- /* Symbols in ref_symbols_list must have at least 1 reference. */
- if (TREE_ANN (sym) == NULL)
+ /* Symbols in referenced_symbols must have at least 1 reference. */
+ if (refs == NULL)
abort ();
- for (i = VARREF_LIST_FIRST (TREE_REFS (sym)); i;
- i = VARREF_NODE_NEXT (i))
+ for (j = 0; j < VARRAY_ACTIVE_SIZE (refs); j++)
{
basic_block bb;
- varref ref = VARREF_NODE_ELEM (i);
+ varref ref = VARRAY_GENERIC_PTR (refs, j);
if (VARREF_TYPE (ref) != VARDEF)
continue;
bb = VARREF_BB (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_PUSH_BB (work_stack, bb);
VARRAY_TREE (in_work, bb->index) = sym;
}
- while (work_list_top > 0)
+ while (VARRAY_ACTIVE_SIZE (work_stack) > 0)
{
int w;
basic_block bb;
- work_list_top--;
- bb = VARRAY_BB (work_list, work_list_top);
+ bb = VARRAY_TOP_BB (work_stack);
+ VARRAY_POP (work_stack);
EXECUTE_IF_SET_IN_SBITMAP (dfs[bb->index], 0, w,
{
@@ -195,17 +187,13 @@ insert_phi_terms (dfs)
if (stmt_bb == NULL)
abort ();
- phi = create_varref (sym, VARPHI, bb, stmt_bb->head_tree, NULL);
+ phi = create_varref (sym, VARPHI, bb, stmt_bb->head_tree,
+ NULL);
VARRAY_TREE (added, w) = sym;
if (VARRAY_TREE (in_work, w) != sym)
{
- /* 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_PUSH_BB (work_stack, bb);
VARRAY_TREE (in_work, w) = sym;
}
}
@@ -215,7 +203,7 @@ insert_phi_terms (dfs)
VARRAY_FREE (added);
VARRAY_FREE (in_work);
- VARRAY_FREE (work_list);
+ VARRAY_FREE (work_stack);
}
/* }}} */
@@ -228,17 +216,17 @@ static void
build_fud_chains (idom)
int *idom;
{
- tree m;
+ size_t i;
/* Initialize the current definition for all the symbols. */
- for (m = ref_symbols_list; m; m = TREE_CHAIN (m))
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (referenced_symbols); i++)
{
- tree sym = TREE_VALUE (m);
+ 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 (TREE_ANN (sym) == NULL)
+ if (ann == NULL)
abort ();
ann->currdef = NULL;
@@ -260,28 +248,31 @@ search_fud_chains (bb, idom)
basic_block bb;
int *idom;
{
- varref_node n;
+ varray_type bb_refs;
edge e;
int i;
+ size_t r, nrefs;
- /* for each variable use or def or phi-term R in X do
- let M be the variable referenced at R
+ /* for each variable use or def or phi-term R in BB do
+ let SYM be the variable referenced at R
if R is a use then
- Chain(R) = CurrDef(M)
+ Chain(R) = CurrDef(SYM)
else if R is a def or $\phi$-term then
- SaveChain(R) = CurrDef(M)
- CurrDef(M) = R
+ SaveChain(R) = CurrDef(SYM)
+ CurrDef(SYM) = R
endif
endfor */
- for (n = VARREF_LIST_FIRST (BB_REFS (bb)); n; n = VARREF_NODE_NEXT (n))
+ bb_refs = BB_REFS (bb);
+ nrefs = (bb_refs) ? VARRAY_ACTIVE_SIZE (bb_refs) : 0;
+ for (r = 0; r < nrefs; r++)
{
varref currdef;
- varref ref = VARREF_NODE_ELEM (n);
- tree m = VARREF_SYM (ref);
+ varref ref = VARRAY_GENERIC_PTR (bb_refs, r);
+ tree sym = VARREF_SYM (ref);
/* Retrieve the current definition for the variable. */
- currdef = TREE_CURRDEF (m);
+ currdef = TREE_CURRDEF (sym);
if (VARREF_TYPE (ref) == VARUSE)
{
@@ -298,43 +289,45 @@ search_fud_chains (bb, idom)
if (currdef)
{
- if (VARDEF_IMM_USES (currdef))
- push_ref (VARDEF_IMM_USES (currdef), ref);
- else
- VARDEF_IMM_USES (currdef) = create_varref_list (ref);
+ 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);
}
}
else if (VARREF_TYPE (ref) == VARDEF || VARREF_TYPE (ref) == VARPHI)
{
- tree_ann ann;
-
VARDEF_SAVE_CHAIN (ref) = currdef;
- /* Replace the current currdef with a new one. */
- ann = get_tree_ann (m);
- ann->currdef = ref;
+ /* Replace the current reaching definition with a new one. */
+ get_tree_ann (sym)->currdef = ref;
}
}
-
- /* for Y in SUCC(X) do
- J = WhichPred(X -> Y)
+ /* for Y in SUCC(BB) do
+ J = WhichPred(BB -> Y)
for each phi-term R in Y do
- let M be the variable referenced at R
- phi-chain(R)[J] = CurrDef(M)
+ let SYM be the variable referenced at R
+ phi-chain(R)[J] = CurrDef(SYM)
endfor
endfor */
- for (e = bb->succ, i = 0; e; e = e->succ_next, i++)
+ for (e = bb->succ; e; e = e->succ_next)
{
- basic_block y = e->dest;
+ varray_type y_refs;
+ basic_block y;
- for (n = VARREF_LIST_FIRST (BB_REFS (y)); n; n = VARREF_NODE_NEXT (n))
+ y = e->dest;
+ y_refs = BB_REFS (y);
+ if (y_refs == NULL)
+ break;
+
+ for (r = 0; r < VARRAY_ACTIVE_SIZE (y_refs); r++)
{
tree sym;
varref currdef;
- varref phi = VARREF_NODE_ELEM (n);
+ varref phi = VARRAY_GENERIC_PTR (y_refs, r);
if (VARREF_TYPE (phi) != VARPHI)
continue;
@@ -344,18 +337,17 @@ search_fud_chains (bb, idom)
if (currdef)
{
- if (VARPHI_CHAIN (phi))
- push_ref (VARPHI_CHAIN (phi), currdef);
- else
- VARPHI_CHAIN (phi) = create_varref_list (currdef);
+ if (VARPHI_CHAIN (phi) == NULL)
+ VARRAY_GENERIC_PTR_INIT (VARPHI_CHAIN (phi), 2, "phi_chain");
+
+ VARRAY_PUSH_GENERIC_PTR (VARPHI_CHAIN (phi), currdef);
}
}
}
-
- /* for Y in Child(X) do <-- Child(X) is the set of dominator
- Search(Y) children of X in the dominator tree.
+ /* 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++)
@@ -365,16 +357,16 @@ search_fud_chains (bb, idom)
}
- /* for each variable use or def or phi-term R in X in reverse order do
- let M be the variable referenced at R
+ /* for each variable use or def or phi-term R in BB in reverse order do
+ let SYM be the variable referenced at R
if R is a def or a phi-term then
- CurrDef(M) = SaveChain(R)
+ CurrDef(SYM) = SaveChain(R)
endif
endfor */
- for (n = VARREF_LIST_LAST (BB_REFS (bb)); n; n = VARREF_NODE_PREV (n))
+ for (i = nrefs - 1; i >= 0; i--)
{
- varref ref = VARREF_NODE_ELEM (n);
+ varref ref = VARRAY_GENERIC_PTR (bb_refs, i);
if (VARREF_TYPE (ref) == VARDEF || VARREF_TYPE (ref) == VARPHI)
{