[tree-ssa] SSA->normal memory consumption fix [patch]
Diego Novillo
dnovillo@redhat.com
Sat Apr 26 00:02:00 GMT 2003
This the patch that Andrew sent me earlier today to fix the
memory consumption problem for the SSA->normal pass. It changes
a couple of bitmaps in the elimination graph to use sparse
bitmaps.
It also fixes a bug in the processing of pointer arguments to
function calls. Whenever we pass a pointer 'p' to a function
call, a new virtual operand for '*p' is added to model the fact
that the call may dereference 'p'. If '*p' is read-only, we
should not assume that the call may clobber it, but we were
testing read-only on 'p', not '*p'.
The final fix is a kludge that I'm not very happy with. Up until
now we had been renaming global variables as well as locals. But
now we are going to start allowing overlapping live ranges for
different versions of the same variable.
This allows more freedom to code motion passes when moving code
around, but it also complicates our SSA->normal pass. Before we
were just dropping the version numbers and removing PHI nodes.
But now, coming out of SSA is a more elaborate process.
This also means that it is possible for different versions of a
global variable to not be coalesced into the same root var. This
means that at every exposed point of the function we would have
to emit copy-in/copy-out operations to all the global variables.
This may have a large negative impact that we will need to
measure.
For now, I'm just punting on this problem until the SSA->normal
pass is stable (and we determine whether the pain of allowing
overlapping ranges is really worth it, but that's another
discussion which I'm not ready to tackle yet :)
Bootstrapped and tested on ppc and x86.
Diego.
2003-04-25 Andrew MacLeod <amacleod@redhat.com>
* tree-ssa.c (struct _elim_graph): Change type of fields
'pred' and 'succ' to be bitmaps instead of sbitmaps.
Update all uses.
2003-04-25 Diego Novillo <dnovillo@redhat.com>
* tree-cfg.c (linearize_cond_expr): Reformat.
* tree-dfa.c (get_expr_operands): Check for read-only
status the dereferenced argument pointer, not the pointer
itself.
(add_stmt_operand): Always consider global variables as
virtual operands.
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.76
diff -d -u -p -r1.1.4.76 tree-cfg.c
--- tree-cfg.c 21 Apr 2003 23:01:22 -0000 1.1.4.76
+++ tree-cfg.c 25 Apr 2003 19:50:24 -0000
@@ -2167,7 +2167,7 @@ linearize_cond_expr (tree *entry_p, basi
/* Linearize 'if (1)'. */
if (simple_cst_equal (pred, integer_one_node) == 1
- && body_is_empty (else_clause))
+ && body_is_empty (else_clause))
{
/* If there is no THEN_CLAUSE, remove the conditional. */
if (body_is_empty (then_clause))
@@ -2180,7 +2180,7 @@ linearize_cond_expr (tree *entry_p, basi
/* Linearize 'if (0)'. */
if (simple_cst_equal (pred, integer_zero_node) == 1
- && body_is_empty (then_clause))
+ && body_is_empty (then_clause))
{
/* If there is no ELSE_CLAUSE, remove the conditional. */
if (body_is_empty (else_clause))
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.99
diff -d -u -p -r1.1.4.99 tree-dfa.c
--- tree-dfa.c 24 Apr 2003 17:11:17 -0000 1.1.4.99
+++ tree-dfa.c 25 Apr 2003 19:50:24 -0000
@@ -463,8 +463,8 @@ get_expr_operands (stmt, expr_p, flags,
if (SSA_DECL_P (arg)
&& POINTER_TYPE_P (TREE_TYPE (arg)))
{
- int clobber_arg = (may_clobber && !TREE_READONLY (arg));
tree deref = indirect_ref (arg);
+ int clobber_arg = (may_clobber && !TREE_READONLY (deref));
/* By default, adding a reference to an INDIRECT_REF
variable, adds a VUSE of the base pointer. Since we have
@@ -587,6 +587,14 @@ add_stmt_operand (var_p, stmt, flags, pr
/* If VAR is not a variable, do nothing. */
if (var == NULL_TREE || !SSA_VAR_P (var))
return;
+
+ /* FIXME: Currently, global variables are always treated as virtual
+ operands. Otherwise, we would have to insert copy-in/copy-out
+ operations at escape points in the function (e.g., at call sites and
+ return points). The additional overhead of inserting these copies may
+ negate the optimizations enabled by renaming globals. */
+ if (decl_function_context (!DECL_P (var) ? get_base_symbol (var) : var) == 0)
+ flags |= opf_force_vop;
ann = stmt_ann (stmt);
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.67
diff -d -u -p -r1.1.4.67 tree-ssa.c
--- tree-ssa.c 24 Apr 2003 16:59:28 -0000 1.1.4.67
+++ tree-ssa.c 25 Apr 2003 19:50:25 -0000
@@ -126,8 +126,8 @@ typedef struct _elim_graph
/* The actual nodes in the elimination graph. */
tree *nodes;
/* The predecessor and successor list. */
- sbitmap *pred;
- sbitmap *succ;
+ bitmap *pred;
+ bitmap *succ;
/* Visited vector. */
sbitmap visited;
@@ -932,11 +932,19 @@ static elim_graph
new_elim_graph (size)
int size;
{
+ int x;
elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
+
g->size = size;
g->nodes = (tree *) xmalloc (sizeof (tree) * size);
- g->pred = sbitmap_vector_alloc (size, size);
- g->succ= sbitmap_vector_alloc (size, size);
+
+ g->pred = (bitmap *) xmalloc (sizeof (bitmap) * size);
+ g->succ= (bitmap *) xmalloc (sizeof (bitmap) * size);
+ for (x = 0; x < size; x++)
+ {
+ g->pred[x] = BITMAP_XMALLOC ();
+ g->succ[x] = BITMAP_XMALLOC ();
+ }
g->visited = sbitmap_alloc (size);
g->stack = (int *) xmalloc (sizeof (int) * size);
@@ -947,11 +955,16 @@ static void
clear_elim_graph (g)
elim_graph g;
{
+ int x;
int size = g->size;
+
g->num_nodes = 0;
memset (g->nodes, 0, sizeof (tree) * size);
- sbitmap_vector_zero (g->pred, size);
- sbitmap_vector_zero (g->succ, size);
+ for (x = 0; x < size; x++)
+ {
+ bitmap_clear (g->pred[x]);
+ bitmap_clear (g->succ[x]);
+ }
}
/* Delete an elimination graph. */
@@ -959,10 +972,18 @@ static void
delete_elim_graph (g)
elim_graph g;
{
+ int x;
free (g->stack);
sbitmap_free (g->visited);
- sbitmap_free (g->succ);
- sbitmap_free (g->pred);
+
+ for (x = g->size - 1; x >= 0 ; x--)
+ {
+ BITMAP_XFREE (g->succ[x]);
+ BITMAP_XFREE (g->pred[x]);
+ }
+ free (g->succ);
+ free (g->pred);
+
free (g->nodes);
free (g);
}
@@ -1019,8 +1040,8 @@ eliminate_build (g, B, i)
eliminate_name (g, Ti);
p0 = var_to_partition (g->map, T0);
pi = var_to_partition (g->map, Ti);
- SET_BIT (g->pred[pi], p0);
- SET_BIT (g->succ[p0], pi);
+ bitmap_set_bit (g->pred[pi], p0);
+ bitmap_set_bit (g->succ[p0], pi);
edges++;
}
}
@@ -1036,7 +1057,7 @@ elim_forward (g, T)
{
int S;
SET_BIT (g->visited, T);
- EXECUTE_IF_SET_IN_SBITMAP (g->succ[T], 0, S,
+ EXECUTE_IF_SET_IN_BITMAP (g->succ[T], 0, S,
{
if (!TEST_BIT (g->visited, S))
elim_forward (g, S);
@@ -1054,7 +1075,7 @@ elim_unvisited_predecessor (g, T)
int T;
{
int P;
- EXECUTE_IF_SET_IN_SBITMAP (g->pred[T], 0, P,
+ EXECUTE_IF_SET_IN_BITMAP (g->pred[T], 0, P,
{
if (!TEST_BIT (g->visited, P))
return 1;
@@ -1071,7 +1092,7 @@ elim_backward (g, T)
{
int P;
SET_BIT (g->visited, T);
- EXECUTE_IF_SET_IN_SBITMAP (g->pred[T], 0, P,
+ EXECUTE_IF_SET_IN_BITMAP (g->pred[T], 0, P,
{
if (!TEST_BIT (g->visited, P))
elim_backward (g, P);
@@ -1097,7 +1118,7 @@ elim_create (g, T)
{
U = create_temp (partition_to_var (g->map, T));
insert_copy_on_edge (g->e, U, partition_to_var (g->map, T));
- EXECUTE_IF_SET_IN_SBITMAP (g->pred[T], 0, P,
+ EXECUTE_IF_SET_IN_BITMAP (g->pred[T], 0, P,
{
if (!TEST_BIT (g->visited, P))
{
@@ -1108,10 +1129,10 @@ elim_create (g, T)
}
else
{
- EXECUTE_IF_SET_IN_SBITMAP (g->succ[T], 0, S,
+ EXECUTE_IF_SET_IN_BITMAP (g->succ[T], 0, S,
{
SET_BIT (g->visited, T);
- RESET_BIT (g->succ[T], S);
+ bitmap_clear_bit(g->succ[T], S);
insert_copy_on_edge (g->e,
partition_to_var (g->map, T),
partition_to_var (g->map, S));
More information about the Gcc-patches
mailing list