Add formal SSA_NAME table
Diego Novillo
dnovillo@redhat.com
Fri Jun 11 01:17:00 GMT 2004
Second clean-up patch before the reorganization of DOM and propagation
engine. This adds a new table of SSA_NAME objects indexed by
SSA_NAME_VERSION.
It adds a new global varray ssa_names and two accessor macros
num_ssa_names and ssa_name to access the table in a similar manner to
the global referenced_vars.
The only non-mechanical change is the removal of the temporary ssa_name
table built by the PHI optimizer. I just replaced it with references to
the new table.
Bootstrapped and tested on x86. I had to revert this patch to be able
to compile libstdc++, though:
PR c++/15227
* parser.c (cp_parser_direct_declarator): Robustify.
Diego.
* Makefile.in (tree-ssanames.o): Depend on TREE_FLOW_H.
* tree-flow.h (ssa_names, num_ssa_names, ssa_name): Declare.
(highest_ssa_version): Remove.
* tree-outof-ssa.c (new_temp_expr_table): Replace
highest_ssa_version with num_ssa_names.
(dump_replaceable_exprs): Likewise.
(rewrite_vars_out_of_ssa): Likewise.
* tree-ssa-ccp.c (initialize): Likewise
* tree-ssa-copyrename.c (rename_ssa_copies): Likewise.
* tree-ssa-dce.c (tree_dce_init): Likewise.
* tree-ssa-dom.c (tree_ssa_dominator_optimize): Likewise.
* tree-ssa-live.c (create_ssa_var_map): Likewise.
(dump_var_map): Likewise.
* tree-ssa.c (verify_ssa): Likewise.
(kill_redundant_phi_nodes): Likewise.
Do not build a local array of SSA_NAMEs. Use the ssa_names table.
* tree-ssanames.c: Include tree-flow.h
(ssa_names): New varray.
(init_ssa_names): Initialize ssa_names.
Reserve the first slot of the ssa_names table.
(make_ssa_name): Push the newly created SSA_NAME into ssa_names.
Assign version numbers using num_ssa_names.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1295
diff -d -c -p -d -u -p -r1.1295 Makefile.in
--- Makefile.in 10 Jun 2004 15:00:56 -0000 1.1295
+++ Makefile.in 10 Jun 2004 22:32:06 -0000
@@ -1615,7 +1615,7 @@ tree-ssa-dom.o : tree-ssa-dom.c $(TREE_F
errors.h function.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
$(BASIC_BLOCK_H) domwalk.h real.h tree-pass.h flags.h langhooks.h
tree-ssanames.o : tree-ssanames.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
- $(TM_H) $(TREE_H) varray.h $(GGC_H) gt-tree-ssanames.h
+ $(TM_H) $(TREE_H) varray.h $(GGC_H) gt-tree-ssanames.h $(TREE_FLOW_H)
tree-phinodes.o : tree-phinodes.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
$(TM_H) $(TREE_H) varray.h $(GGC_H) $(BASIC_BLOCK_H) $(TREE_FLOW_H) \
gt-tree-phinodes.h $(RTL_H)
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.6
diff -d -c -p -d -u -p -r2.6 tree-flow.h
--- tree-flow.h 10 Jun 2004 21:41:06 -0000 2.6
+++ tree-flow.h 10 Jun 2004 22:32:06 -0000
@@ -348,6 +348,12 @@ extern GTY(()) varray_type referenced_va
#define num_referenced_vars VARRAY_ACTIVE_SIZE (referenced_vars)
#define referenced_var(i) VARRAY_TREE (referenced_vars, i)
+/* Array of all SSA_NAMEs used in the function. */
+extern GTY(()) varray_type ssa_names;
+
+#define num_ssa_names VARRAY_ACTIVE_SIZE (ssa_names)
+#define ssa_name(i) VARRAY_TREE (ssa_names, i)
+
/* Artificial variable used to model the effects of function calls. */
extern GTY(()) tree global_var;
@@ -529,8 +535,6 @@ extern void walk_use_def_chains (tree, w
/* In tree-into-ssa.c */
extern void rewrite_into_ssa (void);
-extern unsigned int highest_ssa_version;
-
/* In tree-ssa-pre.c */
extern void tree_perform_ssapre (tree, enum tree_dump_index);
Index: tree-outof-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-outof-ssa.c,v
retrieving revision 2.5
diff -d -c -p -d -u -p -r2.5 tree-outof-ssa.c
--- tree-outof-ssa.c 10 Jun 2004 21:41:06 -0000 2.5
+++ tree-outof-ssa.c 10 Jun 2004 22:32:06 -0000
@@ -1205,7 +1205,7 @@ new_temp_expr_table (var_map map)
t = (temp_expr_table_p) xmalloc (sizeof (struct temp_expr_table_d));
t->map = map;
- t->version_info = xcalloc (highest_ssa_version + 1, sizeof (void *));
+ t->version_info = xcalloc (num_ssa_names + 1, sizeof (void *));
t->partition_dep_list = xcalloc (num_var_partitions (map) + 1,
sizeof (value_expr_p));
@@ -1700,7 +1700,7 @@ dump_replaceable_exprs (FILE *f, tree *e
tree stmt, var;
int x;
fprintf (f, "\nReplacing Expressions\n");
- for (x = 0; x < (int)highest_ssa_version + 1; x++)
+ for (x = 0; x < (int)num_ssa_names + 1; x++)
if (expr[x])
{
stmt = expr[x];
@@ -2089,7 +2089,7 @@ rewrite_vars_out_of_ssa (bitmap vars)
/* Now register partitions for all instances of the variables we
are taking out of SSA form. */
- map = init_var_map (highest_ssa_version + 1);
+ map = init_var_map (num_ssa_names + 1);
register_ssa_partitions_for_vars (vars, map);
/* Now that we have all the partitions registered, translate the
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-ccp.c,v
retrieving revision 2.7
diff -d -c -p -d -u -p -r2.7 tree-ssa-ccp.c
--- tree-ssa-ccp.c 10 Jun 2004 21:41:07 -0000 2.7
+++ tree-ssa-ccp.c 10 Jun 2004 22:32:07 -0000
@@ -1120,11 +1120,11 @@ initialize (void)
bb_in_list = sbitmap_alloc (last_basic_block);
sbitmap_zero (bb_in_list);
- value_vector = (value *) xmalloc (highest_ssa_version * sizeof (value));
- memset (value_vector, 0, highest_ssa_version * sizeof (value));
+ value_vector = (value *) xmalloc (num_ssa_names * sizeof (value));
+ memset (value_vector, 0, num_ssa_names * sizeof (value));
/* 1 if ssa variable is used in a virtual variable context. */
- virtual_var = sbitmap_alloc (highest_ssa_version);
+ virtual_var = sbitmap_alloc (num_ssa_names);
sbitmap_zero (virtual_var);
/* Initialize default values and simulation flags for PHI nodes, statements
Index: tree-ssa-copyrename.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-copyrename.c,v
retrieving revision 2.3
diff -d -c -p -d -u -p -r2.3 tree-ssa-copyrename.c
--- tree-ssa-copyrename.c 7 Jun 2004 17:53:02 -0000 2.3
+++ tree-ssa-copyrename.c 10 Jun 2004 22:32:07 -0000
@@ -296,7 +296,7 @@ rename_ssa_copies (void)
else
debug = NULL;
- map = init_var_map (highest_ssa_version + 1);
+ map = init_var_map (num_ssa_names + 1);
FOR_EACH_BB (bb)
{
@@ -346,7 +346,7 @@ rename_ssa_copies (void)
/* Now one more pass to make all elements of a partition share the same
root variable. */
- for (x = 1; x <= highest_ssa_version; x++)
+ for (x = 1; x <= num_ssa_names; x++)
{
part_var = partition_to_var (map, x);
if (!part_var)
Index: tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dce.c,v
retrieving revision 2.4
diff -d -c -p -d -u -p -r2.4 tree-ssa-dce.c
--- tree-ssa-dce.c 10 Jun 2004 21:41:07 -0000 2.4
+++ tree-ssa-dce.c 10 Jun 2004 22:32:07 -0000
@@ -791,7 +791,7 @@ tree_dce_init (bool aggressive)
sbitmap_zero (last_stmt_necessary);
}
- processed = sbitmap_alloc (highest_ssa_version + 1);
+ processed = sbitmap_alloc (num_ssa_names + 1);
sbitmap_zero (processed);
VARRAY_TREE_INIT (worklist, 64, "work list");
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dom.c,v
retrieving revision 2.9
diff -d -c -p -d -u -p -r2.9 tree-ssa-dom.c
--- tree-ssa-dom.c 10 Jun 2004 21:41:07 -0000 2.9
+++ tree-ssa-dom.c 10 Jun 2004 22:32:07 -0000
@@ -553,10 +553,10 @@ tree_ssa_dominator_optimize (void)
/* Create our hash tables. */
avail_exprs = htab_create (1024, avail_expr_hash, avail_expr_eq, free);
- VARRAY_TREE_INIT (const_and_copies, highest_ssa_version, "const_and_copies");
+ VARRAY_TREE_INIT (const_and_copies, num_ssa_names, "const_and_copies");
nonzero_vars = BITMAP_XMALLOC ();
VARRAY_EDGE_INIT (redirection_edges, 20, "redirection_edges");
- VARRAY_GENERIC_PTR_INIT (vrp_data, highest_ssa_version, "vrp_data");
+ VARRAY_GENERIC_PTR_INIT (vrp_data, num_ssa_names, "vrp_data");
/* Setup callbacks for the generic dominator tree walker. */
walk_data.walk_stmts_backward = false;
@@ -625,8 +625,8 @@ tree_ssa_dominator_optimize (void)
/* The into SSA translation may have created new SSA_NAMES whic
affect the size of CONST_AND_COPIES and VRP_DATA. */
- VARRAY_GROW (const_and_copies, highest_ssa_version);
- VARRAY_GROW (vrp_data, highest_ssa_version);
+ VARRAY_GROW (const_and_copies, num_ssa_names);
+ VARRAY_GROW (vrp_data, num_ssa_names);
}
/* Reinitialize the various tables. */
Index: tree-ssa-live.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-live.c,v
retrieving revision 2.7
diff -d -c -p -d -u -p -r2.7 tree-ssa-live.c
--- tree-ssa-live.c 10 Jun 2004 21:41:07 -0000 2.7
+++ tree-ssa-live.c 10 Jun 2004 22:32:08 -0000
@@ -309,7 +309,7 @@ create_ssa_var_map (int flags)
sbitmap used_in_virtual_ops;
#endif
- map = init_var_map (highest_ssa_version + 1);
+ map = init_var_map (num_ssa_names + 1);
#if defined ENABLE_CHECKING
used_in_real_ops = sbitmap_alloc (num_referenced_vars);
@@ -322,8 +322,8 @@ create_ssa_var_map (int flags)
if (flags & SSA_VAR_MAP_REF_COUNT)
{
map->ref_count
- = (int *)xmalloc (((highest_ssa_version + 1) * sizeof (int)));
- memset (map->ref_count, 0, (highest_ssa_version + 1) * sizeof (int));
+ = (int *)xmalloc (((num_ssa_names + 1) * sizeof (int)));
+ memset (map->ref_count, 0, (num_ssa_names + 1) * sizeof (int));
}
FOR_EACH_BB (bb)
@@ -1743,7 +1743,7 @@ dump_var_map (FILE *f, var_map map)
continue;
t = 0;
- for (y = 1; y < highest_ssa_version; y++)
+ for (y = 1; y < num_ssa_names; y++)
{
p = partition_find (map->var_partition, y);
if (map->partition_to_compact)
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa.c,v
retrieving revision 2.6
diff -d -c -p -d -u -p -r2.6 tree-ssa.c
--- tree-ssa.c 10 Jun 2004 21:41:06 -0000 2.6
+++ tree-ssa.c 10 Jun 2004 22:32:08 -0000
@@ -292,8 +292,7 @@ verify_ssa (void)
{
bool err = false;
basic_block bb;
- basic_block *definition_block = xcalloc (highest_ssa_version,
- sizeof (basic_block));
+ basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block));
timevar_push (TV_TREE_SSA_VERIFY);
@@ -850,8 +849,8 @@ raise_value (tree phi, tree val, tree *e
static void
kill_redundant_phi_nodes (void)
{
- tree *eq_to, *ssa_names;
- unsigned i, ver, aver;
+ tree *eq_to;
+ unsigned i;
basic_block bb;
tree phi, t, stmt, var;
@@ -871,15 +870,7 @@ kill_redundant_phi_nodes (void)
The remaining phi nodes have their uses replaced with their value
in the lattice and the phi node itself is removed. */
- eq_to = xcalloc (highest_ssa_version, sizeof (tree));
-
- /* The SSA_NAMES array holds each SSA_NAME node we encounter
- in a PHI node (indexed by ssa version number).
-
- One could argue that the SSA_NAME manager ought to provide a
- generic interface to get at the SSA_NAME node for a given
- ssa version number. */
- ssa_names = xcalloc (highest_ssa_version, sizeof (tree));
+ eq_to = xcalloc (num_ssa_names, sizeof (tree));
/* We have had cases where computing immediate uses takes a
significant amount of compile time. If we run into such
@@ -893,8 +884,6 @@ kill_redundant_phi_nodes (void)
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
{
var = PHI_RESULT (phi);
- ver = SSA_NAME_VERSION (var);
- ssa_names[ver] = var;
for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
{
@@ -907,8 +896,6 @@ kill_redundant_phi_nodes (void)
}
stmt = SSA_NAME_DEF_STMT (t);
- aver = SSA_NAME_VERSION (t);
- ssa_names[aver] = t;
/* If the defining statement for this argument is not a
phi node or the argument is associated with an abnormal
@@ -917,7 +904,7 @@ kill_redundant_phi_nodes (void)
if (TREE_CODE (stmt) != PHI_NODE
|| SSA_NAME_OCCURS_IN_ABNORMAL_PHI (t))
{
- eq_to[aver] = t;
+ eq_to[SSA_NAME_VERSION (t)] = t;
raise_value (phi, t, eq_to);
}
}
@@ -925,23 +912,22 @@ kill_redundant_phi_nodes (void)
}
/* Now propagate the values. */
- for (i = 0; i < highest_ssa_version; i++)
+ for (i = 0; i < num_ssa_names; i++)
if (eq_to[i]
- && eq_to[i] != ssa_names[i])
- replace_immediate_uses (ssa_names[i], eq_to[i]);
+ && eq_to[i] != ssa_name (i))
+ replace_immediate_uses (ssa_name (i), eq_to[i]);
/* And remove the dead phis. */
- for (i = 0; i < highest_ssa_version; i++)
+ for (i = 0; i < num_ssa_names; i++)
if (eq_to[i]
- && eq_to[i] != ssa_names[i])
+ && eq_to[i] != ssa_name (i))
{
- stmt = SSA_NAME_DEF_STMT (ssa_names[i]);
+ stmt = SSA_NAME_DEF_STMT (ssa_name (i));
remove_phi_node (stmt, 0, bb_for_stmt (stmt));
}
free_df ();
free (eq_to);
- free (ssa_names);
}
struct tree_opt_pass pass_redundant_phi =
Index: tree-ssanames.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssanames.c,v
retrieving revision 2.1
diff -d -c -p -d -u -p -r2.1 tree-ssanames.c
--- tree-ssanames.c 13 May 2004 06:39:50 -0000 2.1
+++ tree-ssanames.c 10 Jun 2004 22:32:08 -0000
@@ -25,6 +25,7 @@ Boston, MA 02111-1307, USA. */
#include "tree.h"
#include "varray.h"
#include "ggc.h"
+#include "tree-flow.h"
/* Rewriting a function into SSA form can create a huge number of SSA_NAMEs,
many of which may be thrown away shortly after their creation if jumps
@@ -57,8 +58,8 @@ Boston, MA 02111-1307, USA. */
a very well defined lifetime. If someone wants to experiment with that
this is the place to try it. */
-/* Next SSA version number to be allocated. */
-unsigned int highest_ssa_version;
+/* Array of all SSA_NAMEs used in the function. */
+varray_type ssa_names;
/* Free list of SSA_NAMEs. This list is wiped at the end of each function
after we leave SSA form. */
@@ -78,7 +79,13 @@ unsigned int ssa_name_nodes_created;
void
init_ssanames (void)
{
- highest_ssa_version = UNUSED_NAME_VERSION + 1;
+ VARRAY_TREE_INIT (ssa_names, 50, "ssa_names table");
+
+ /* Version 0 is special, so reserve the first slot in the table. Though
+ currently unused, we may use version 0 in alias analysis as part of
+ the heuristics used to group aliases when the alias sets are too
+ large. */
+ VARRAY_PUSH_TREE (ssa_names, NULL_TREE);
free_ssanames = NULL;
}
@@ -142,7 +149,8 @@ make_ssa_name (tree var, tree stmt)
else
{
t = make_node (SSA_NAME);
- SSA_NAME_VERSION (t) = highest_ssa_version++;
+ SSA_NAME_VERSION (t) = num_ssa_names;
+ VARRAY_PUSH_TREE (ssa_names, t);
#ifdef GATHER_STATISTICS
ssa_name_nodes_created++;
#endif
@@ -151,10 +159,12 @@ make_ssa_name (tree var, tree stmt)
TREE_TYPE (t) = TREE_TYPE (var);
SSA_NAME_VAR (t) = var;
SSA_NAME_DEF_STMT (t) = stmt;
+ SSA_NAME_PTR_INFO (t) = NULL;
return t;
}
+
/* We no longer need the SSA_NAME expression VAR, release it so that
it may be reused.
More information about the Gcc-patches
mailing list