[tree-ssa] More overlapping live range infrastructure.
Andrew MacLeod
amacleod@redhat.com
Wed May 7 19:21:00 GMT 2003
This is the next step towards enabling overlapping live ranges. The main
holdup now an issue with pointers. I also have a minor bit of c++ work
to do I think.
The issue is that we rename *p and p thoughout the program, but we don't
actually rename occurences which store through a pointer. Instead, we
have a VUSE of the renamed pointer:
# (*p1)_284 = VDEF <(*p1)_26>;
# .GLOBAL_VAR_285 = VDEF <.GLOBAL_VAR_53>;
# VUSE <p1_11>
*p1 = 97;
if p1_11 overlaps with another instance of p1, we assign p1_11 to
another variable, like p1.285 instead of p1.
The problem is that since '*p1 = 27' hasn't be rewritten, we don't
actually do anything to this stmt. We are generating code to dereference
*p instead of *p1.285, so we are getting the wrong location.
What we really need is to make it a real use instead of a virtual use,
so something like:
# (*p1)_284 = VDEF <(*p1)_26>;
# .GLOBAL_VAR_285 = VDEF <.GLOBAL_VAR_53>;
*p1_11 = 97;
and then it will get rewritten properly to *p1.285 = 97.
I have a hack which I've been using to test code, but we're better off
with a real solution. Diego is working on this I beleive. When that is
done, we can probably enable overlapping live ranges.
- The coalescer has been modified to coalesce any partitions which are
live on entry to the function with their root variable. This is
important for parameters, and if we ever enable renaming of globals or
local statics.
- I've disabled renaming of local statics as well. As with global, you
have to be certain that the right value is in the right memory location
at function exit and all call sites. Thats more work than we are
prepared for at the moment.
- We also coalesces PHI arguments across abnormal edges.
- The insert_on_edge code has been fixed up to work properly (well,
better anyway :-). There are some other cases where we get it wrong, but
we'll fix those as we encounter them. The real problem is usually where
to put the new stmt in the tree structure.
- A bit more debugging information is now emitted as well. It gets
emitted into the *.optimized file.
- We were being a bit too hasty about removing some conditional code.
Take for example:
if (a_2 > b_2)
t_3 = a_2;
else
t_4 = b_2
# t_5 = PHI <t_3(2), t_4(3)>
return t_5
Copy propagation turns this into:
if (a_2 > b_2)
t_3 = a_2;
else
t_4 = b_2
# t_5 = PHI <a_2(2), b_2(3)>
return t_5
DCE then transforms it, in part, to:
if (a_2 > b_2)
(void *)0
else
(void *)0
# t_5 = PHI <a_2(2), b_2(3)>
return t_5
This exposed 2 bugs. The problem is that both DCE and linearization
consider the conditional to be dead, and blow away the entire if
construct. Unfortunately, it is still required. The out of SSA pass is
going to have to insert at least one copy into at least one of those
branches. If we eliminate the conditional, there is no way to choose
between the 2 PHI values.
So The changes are:
DCE - If a PHI node is marked necessary, then any conditional feeding
it is necessary as well. (ie, if the parent of the incoming edge has a
COND_EXPR or a SWITCH_EXPR as the last stmt in their blocks)
linearization - a conditional with an empty 'then' and 'else' can only
be deleted if the immediate post-dominator contains no PHI nodes.
This causes no new regression in the testsuites, and bootstraps.
Overall impact on compile time is nominal. A complete build of the gcc
source on my machine increases by a percent or so, probably due to the
dominator information being calculated in linearize_cond_expr's
sometimes.
comments? OK to check this in? It touches a few things :-)
Andrew
2003-05-02 Andrew MacLeod <amacleod@redhat.com>
* tree-cfg.c (pdom_info): New file level static.
(cleanup_tree_cfg): Free dominance info, if it was used.
(bsi_replace): New. Replace a stmt with a new one.
(linearize_cond_expr): Use post dominator info to determine is a
conditional can be safely removed.
(find_insert_location): New. Determine where to insert a new stmt that
is placed on a split edge.
(bsi_commit_first_edge_insert): Use find_insert_location to determine
where to link a stmt when splitting an edge.
(merge_tree_blocks): When deleting a basic block, remove it from the
dominance structure if it exists.
* tree-dfa.c (add_stmt_operand): Don't rename local statics. Treat
them just like globals.
* tree-flow.h (struct var_ann_d): Add root_var_processed bit and
root_index fields.
* tree-ssa-dce.c (process_worklist): Mark conditions feeding PHI's as
necessary as well.
(remove_dead_phis): Add missing debug information.
* tree-ssa-live.c (var_union): Handle combining partitions when one
has a root_variable as a representative.
(compact_var_map): Add comments and use flags.
(init_root_var): Use new root_var fields in struct var_ann_d.
(dump_root_var): Send output to specified file, not stderr.
(dump_var_map): Remove dump_flag parameter & some grotesque debug info.
* tree-ssa-live.h (VAR_ANN_ROOT_INDEX): Define.
(VARMAP_NORMAL, VARMAP_NO_SINGLE_DEFS): Define flags for compact_var_map.
(var_to_partition_to_var): Return NULL if not in a partition.
(find_root_var): Use VAR_ANN_ROOT_INDEX.
* tree-ssa.c (insert_copy_on_edge): Add listing info.
(coalesce_ssa_name): Coalesce live-on-entry variables to their root.
Coalesce partitions across abnormal edges.
(assign_vars): Remove redundant initialization code. Handle root_vars
which have already been coalesced to a partition.
(rewrite_out_of_ssa): Add debug info & remove PHI nodes when processed.
(rewrite_stmt): Don't redefine redundant expressions.
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.83
diff -c -p -r1.1.4.83 tree-cfg.c
*** tree-cfg.c 7 May 2003 02:49:49 -0000 1.1.4.83
--- tree-cfg.c 7 May 2003 18:50:00 -0000
*************** struct cfg_stats_d
*** 71,76 ****
--- 71,78 ----
long num_failed_bind_expr_merges;
};
+ static dominance_info pdom_info = NULL;
+
static struct cfg_stats_d cfg_stats;
/* Basic blocks and flowgraphs. */
*************** static block_stmt_iterator bsi_init PAR
*** 136,141 ****
--- 138,144 ----
static inline void bsi_update_from_tsi PARAMS (( block_stmt_iterator *, tree_stmt_iterator));
static tree_stmt_iterator bsi_link_after PARAMS ((tree_stmt_iterator *, tree, basic_block, tree));
static block_stmt_iterator bsi_commit_first_edge_insert PARAMS ((edge, tree));
+ static tree_stmt_iterator find_insert_location PARAMS ((basic_block, basic_block, int *));
/* Location to track pending stmt for edge insertion. */
#define PENDING_STMT(e) ((tree)(e->insns))
*************** void
*** 1361,1369 ****
--- 1364,1378 ----
cleanup_tree_cfg ()
{
timevar_push (TV_TREE_CLEANUP_CFG);
+ pdom_info = NULL;
cleanup_control_flow ();
remove_unreachable_blocks ();
linearize_control_structures ();
+ if (pdom_info != NULL)
+ {
+ free_dominance_info (pdom_info);
+ pdom_info = NULL;
+ }
compact_blocks ();
timevar_pop (TV_TREE_CLEANUP_CFG);
}
*************** bsi_remove (i)
*** 1782,1787 ****
--- 1791,1813 ----
}
+ /* Replace the contents of a stmt with another. The replacement cannot be
+ a COMPOUND_EXPR node, only a simple stmt. */
+
+ void
+ bsi_replace (bsi, stmt)
+ block_stmt_iterator bsi;
+ tree stmt;
+ {
+ if (TREE_CODE (stmt) == COMPOUND_EXPR)
+ abort ();
+
+ replace_stmt (bsi.tp, &stmt);
+ modify_stmt (bsi_stmt (bsi));
+ }
+
+
+
/* Remove statement *STMT_P.
Update all references associated with it. Note that this function will
*************** linearize_control_structures ()
*** 2167,2172 ****
--- 2193,2199 ----
static bool
linearize_cond_expr (tree *entry_p, basic_block bb)
{
+ basic_block pdom_bb;
tree entry = *entry_p;
tree pred = COND_EXPR_COND (entry);
tree then_clause = COND_EXPR_THEN (entry);
*************** linearize_cond_expr (tree *entry_p, basi
*** 2175,2182 ****
/* Remove the conditional if both branches have been removed. */
if (body_is_empty (then_clause) && body_is_empty (else_clause))
{
! remove_stmt (entry_p);
! return true;
}
/* Linearize 'if (1)'. */
--- 2202,2216 ----
/* Remove the conditional if both branches have been removed. */
if (body_is_empty (then_clause) && body_is_empty (else_clause))
{
! /* Calculate dominance info, if it hasn't been computed yet. */
! if (pdom_info == NULL)
! pdom_info = calculate_dominance_info (CDI_POST_DOMINATORS);
! pdom_bb = get_immediate_dominator (pdom_info, bb);
! if (!phi_nodes (pdom_bb))
! {
! remove_stmt (entry_p);
! return true;
! }
}
/* Linearize 'if (1)'. */
*************** bsi_insert_before (curr_bsi, t, mode)
*** 3457,3462 ****
--- 3491,3532 ----
}
+ /* Given an edge between src and dest, return a TSI representing the location
+ that any instructions on this edge should be inserted. */
+
+ static tree_stmt_iterator
+ find_insert_location (src, dest, after)
+ basic_block src;
+ basic_block dest;
+ int *after;
+ {
+ block_stmt_iterator bsi;
+ tree *ret, stmt;
+
+ *after = 0;
+ bsi = bsi_last (src);
+ if (!bsi_end_p (bsi))
+ {
+ stmt = bsi_stmt (bsi);
+ switch (TREE_CODE (stmt))
+ {
+ case COND_EXPR:
+ case LOOP_EXPR:
+ ret = src->end_tree_p;
+ *after = 1;
+ break;
+
+ default:
+ ret = dest->head_tree_p;
+ break;
+ }
+ }
+ else
+ ret = src->end_tree_p;
+
+ return tsi_start (ret);
+
+ }
/* This routine inserts a stmt on an edge. Every attempt is made to place the
stmt in an existing basic block, but sometimes that isn't possible. When
it isn't possible, a new basic block is created, edges updated, and the
*************** bsi_commit_first_edge_insert (e, stmt)
*** 3470,3477 ****
basic_block src, dest, new_bb;
block_stmt_iterator bsi, tmp;
tree_stmt_iterator tsi;
! int single_exit, single_entry;
! tree first, last, inserted_stmt;
bb_ann_t bb_ann;
first = last = NULL_TREE;
--- 3540,3547 ----
basic_block src, dest, new_bb;
block_stmt_iterator bsi, tmp;
tree_stmt_iterator tsi;
! int single_exit, single_entry, after;
! tree first, last, inserted_stmt, parent;
bb_ann_t bb_ann;
first = last = NULL_TREE;
*************** bsi_commit_first_edge_insert (e, stmt)
*** 3510,3516 ****
}
/* If the last stmt is a GOTO, the we can simply insert before it. */
! if (TREE_CODE (last) == GOTO_EXPR)
{
bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
return bsi;
--- 3580,3586 ----
}
/* If the last stmt is a GOTO, the we can simply insert before it. */
! if (TREE_CODE (last) == GOTO_EXPR || TREE_CODE (last) == LOOP_EXPR)
{
bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
return bsi;
*************** bsi_commit_first_edge_insert (e, stmt)
*** 3565,3582 ****
bb_ann->ephi_nodes = NULL_TREE;
bb_ann->dom_children = (bitmap) NULL;
! /* The new stmt needs to be linked in somewhere, link it in before
! the first statement in the destination block. This will help position
! the stmt properly if it is a child tree, as well as if it is a fallthru.
! stmt. Not to mention, this also has the least effect on other basic
! block pointers. */
!
! tsi = tsi_start (dest->head_tree_p);
! tsi_link_before (&tsi, stmt, TSI_NEW_STMT);
!
! append_stmt_to_bb (tsi_container (tsi),
! new_bb,
! parent_stmt (*dest->head_tree_p));
inserted_stmt = tsi_stmt (tsi);
bsi = bsi_from_tsi (tsi);
--- 3635,3648 ----
bb_ann->ephi_nodes = NULL_TREE;
bb_ann->dom_children = (bitmap) NULL;
! tsi = find_insert_location (src, dest, &after);
! parent = parent_stmt (tsi_stmt (tsi));
! if (after)
! tsi_link_after (&tsi, stmt, TSI_NEW_STMT);
! else
! tsi_link_before (&tsi, stmt, TSI_NEW_STMT);
!
! append_stmt_to_bb (tsi_container (tsi), new_bb, parent);
inserted_stmt = tsi_stmt (tsi);
bsi = bsi_from_tsi (tsi);
*************** merge_tree_blocks (basic_block bb1, basi
*** 3867,3872 ****
--- 3933,3940 ----
bb2->end_tree_p = NULL;
bb2->pred = NULL;
bb2->succ = NULL;
+ if (pdom_info != NULL)
+ delete_from_dominance_info (pdom_info, bb2);
remove_bb (bb2, 0);
}
}
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.107
diff -c -p -r1.1.4.107 tree-dfa.c
*** tree-dfa.c 7 May 2003 13:28:27 -0000 1.1.4.107
--- tree-dfa.c 7 May 2003 18:50:01 -0000
*************** add_stmt_operand (var_p, stmt, flags, pr
*** 595,600 ****
--- 595,603 ----
if (decl_function_context (!DECL_P (var) ? get_base_symbol (var) : var) == 0)
flags |= opf_force_vop;
+ if (TREE_STATIC ((!DECL_P (var) ? get_base_symbol (var) : var)))
+ flags |= opf_force_vop;
+
ann = stmt_ann (stmt);
aliases = may_aliases (var);
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.75
diff -c -p -r1.1.4.75 tree-flow.h
*** tree-flow.h 6 May 2003 15:31:41 -0000 1.1.4.75
--- tree-flow.h 7 May 2003 18:50:01 -0000
*************** struct var_ann_d GTY(())
*** 90,97 ****
seen yet or not. */
unsigned out_of_ssa_tag : 1;
/* Unused bits. */
! unsigned unused : 25;
/* An INDIRECT_REF expression representing all the dereferences of this
pointer. Used to store aliasing information for pointer dereferences
--- 90,100 ----
seen yet or not. */
unsigned out_of_ssa_tag : 1;
+ /* Used when building root_var structures in tree_ssa_live.[ch]. */
+ unsigned root_var_processed : 1;
+
/* Unused bits. */
! unsigned unused : 24;
/* An INDIRECT_REF expression representing all the dereferences of this
pointer. Used to store aliasing information for pointer dereferences
*************** struct var_ann_d GTY(())
*** 107,112 ****
--- 110,118 ----
/* Used when going out of SSA form to indicate which partition this
variable represents storage for. */
unsigned partition;
+
+ /* Used by the root-var object in tree-ssa-live.[ch]. */
+ unsigned root_index;
};
*************** extern void bsi_insert_before PARAMS ((b
*** 323,328 ****
--- 329,335 ----
extern void bsi_insert_after PARAMS ((block_stmt_iterator *, tree, enum bsi_iterator_update));
extern void bsi_insert_on_edge PARAMS ((edge, tree));
extern int bsi_commit_edge_inserts PARAMS ((int, int *));
+ extern void bsi_replace PARAMS ((block_stmt_iterator, tree));
/* Stmt list insertion routines. */
Index: tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dce.c,v
retrieving revision 1.1.2.35
diff -c -p -r1.1.2.35 tree-ssa-dce.c
*** tree-ssa-dce.c 2 May 2003 13:52:38 -0000 1.1.2.35
--- tree-ssa-dce.c 7 May 2003 18:50:02 -0000
*************** process_worklist ()
*** 359,365 ****
/* All the statements feeding this PHI node's arguments are
necessary. */
for (k = 0; k < PHI_NUM_ARGS (i); k++)
! mark_necessary (SSA_NAME_DEF_STMT (PHI_ARG_DEF (i, k)));
}
else
{
--- 359,390 ----
/* All the statements feeding this PHI node's arguments are
necessary. */
for (k = 0; k < PHI_NUM_ARGS (i); k++)
! {
! mark_necessary (SSA_NAME_DEF_STMT (PHI_ARG_DEF (i, k)));
!
! /* Look at all the predecessors, and if this PHI is being fed
! from a conditional expression, mark that conditional
! as necessary. Copies may be needed on an edge later. */
! for (e = bb->pred; e; e = e->pred_next)
! {
! basic_block pred, par;
! pred = e->src;
! if (pred != ENTRY_BLOCK_PTR)
! {
! par = parent_block (pred);
! if (par)
! {
! tree last = last_stmt (par);
! if (last && (TREE_CODE (last) == COND_EXPR
! || TREE_CODE (last) == SWITCH_EXPR))
! {
! mark_necessary (last);
! }
! }
! }
! }
!
! }
}
else
{
*************** remove_dead_phis (bb)
*** 457,462 ****
--- 482,495 ----
if (!necessary_p (phi))
{
tree next = TREE_CHAIN (phi);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Deleting : ");
+ print_generic_stmt (dump_file, phi, TDF_SLIM);
+ fprintf (dump_file, "\n");
+ }
+
remove_phi_node (phi, prev, bb);
stats.removed_phis++;
phi = next;
Index: tree-ssa-live.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-live.c,v
retrieving revision 1.1.2.3
diff -c -p -r1.1.2.3 tree-ssa-live.c
*** tree-ssa-live.c 26 Apr 2003 03:04:04 -0000 1.1.2.3
--- tree-ssa-live.c 7 May 2003 18:50:02 -0000
*************** var_union (map, var1, var2)
*** 117,129 ****
tree var1, var2;
{
int p1, p2, p3;
/* This is independant of partition_to_compact. If partition_to_compact is
on, then whichever one of these partitions is absorbed will never have a
dereference into the partition_to_compact array any more. */
! p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
! p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
if (p1 == p2)
p3 = p1;
--- 117,152 ----
tree var1, var2;
{
int p1, p2, p3;
+ tree root_var = NULL_TREE;
/* This is independant of partition_to_compact. If partition_to_compact is
on, then whichever one of these partitions is absorbed will never have a
dereference into the partition_to_compact array any more. */
! if (TREE_CODE (var1) == SSA_NAME)
! p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
! else
! {
! p1 = var_to_partition (map, var1);
! if (map->compact_to_partition)
! p1 = map->compact_to_partition[p1];
! root_var = var1;
! }
!
! if (TREE_CODE (var2) == SSA_NAME)
! p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
! else
! {
! p2 = var_to_partition (map, var2);
! if (map->compact_to_partition)
! p2 = map->compact_to_partition[p2];
! if (root_var != NULL_TREE)
! return -1;
! root_var = var2;
! }
!
! if (p1 == NO_PARTITION || p2 == NO_PARTITION)
! abort ();
if (p1 == p2)
p3 = p1;
*************** var_union (map, var1, var2)
*** 133,138 ****
--- 156,164 ----
if (map->partition_to_compact)
p3 = map->partition_to_compact[p3];
+ if (root_var)
+ change_partition_var (map, root_var, p3);
+
return p3;
}
*************** var_union (map, var1, var2)
*** 141,152 ****
0..(num_partitions-1) instead of whereever they turned out during
the partitioning exercise. This removes any references to unused
partitions, thereby allowing bitmaps and other vectors to be much
! denser. */
void
! compact_var_map (map, use_singles)
var_map map;
! int use_singles;
{
sbitmap used;
int x, limit, count, tmp, root, root_i;
--- 167,189 ----
0..(num_partitions-1) instead of whereever they turned out during
the partitioning exercise. This removes any references to unused
partitions, thereby allowing bitmaps and other vectors to be much
! denser.
!
! This is implemented such that compaction doesn't affect partitioning.
! That is, once partitions are created and possibly merged, running one
! or more different kind of compaction will not affect the partitions
! themselves. Their index might change, but all the same variables will
! still be members of the same partition group. This allows work on reduced
! sets, and no lose of information when a larger set is desired.
!
! In partiticular, coalescing can work on partitions which have 2 or more
! definitions, and then 'recompact' later to include all the single
! definitions for assignment to program variables. */
void
! compact_var_map (map, flags)
var_map map;
! int flags;
{
sbitmap used;
int x, limit, count, tmp, root, root_i;
*************** compact_var_map (map, use_singles)
*** 169,175 ****
map->partition_to_compact = NULL;
}
! if (use_singles)
rv = init_root_var (map);
map->partition_to_compact = (int *)xmalloc (limit * sizeof (int));
--- 206,212 ----
map->partition_to_compact = NULL;
}
! if (flags & VARMAP_NO_SINGLE_DEFS)
rv = init_root_var (map);
map->partition_to_compact = (int *)xmalloc (limit * sizeof (int));
*************** init_root_var (map)
*** 604,619 ****
if (TREE_CODE (t) == SSA_NAME)
t = SSA_NAME_VAR (t);
ann = var_ann (t);
! if (ann->out_of_ssa_tag)
{
rv->next_partition[x] = VARRAY_INT (rv->first_partition,
! VAR_ANN_PARTITION (ann));
! VARRAY_INT (rv->first_partition, VAR_ANN_PARTITION (ann)) = x;
}
else
{
! ann->out_of_ssa_tag = 1;
! VAR_ANN_PARTITION (ann) = rv->num_root_vars++;
VARRAY_PUSH_TREE (rv->root_var, t);
VARRAY_PUSH_INT (rv->first_partition, x);
}
--- 641,656 ----
if (TREE_CODE (t) == SSA_NAME)
t = SSA_NAME_VAR (t);
ann = var_ann (t);
! if (ann->root_var_processed)
{
rv->next_partition[x] = VARRAY_INT (rv->first_partition,
! VAR_ANN_ROOT_INDEX (ann));
! VARRAY_INT (rv->first_partition, VAR_ANN_ROOT_INDEX (ann)) = x;
}
else
{
! ann->root_var_processed = 1;
! VAR_ANN_ROOT_INDEX (ann) = rv->num_root_vars++;
VARRAY_PUSH_TREE (rv->root_var, t);
VARRAY_PUSH_INT (rv->first_partition, x);
}
*************** init_root_var (map)
*** 623,629 ****
for (x = 0; x < rv->num_root_vars; x++)
{
t = VARRAY_TREE (rv->root_var, x);
! var_ann (t)->out_of_ssa_tag = 0;
}
return rv;
--- 660,666 ----
for (x = 0; x < rv->num_root_vars; x++)
{
t = VARRAY_TREE (rv->root_var, x);
! var_ann (t)->root_var_processed = 0;
}
return rv;
*************** dump_root_var (f, rv)
*** 683,695 ****
fprintf (f, "Root Var dump\n");
for (x = 0; x < num_root_vars (rv); x++)
{
! print_generic_expr (stderr, root_var (rv, x), TDF_SLIM);
fprintf (f, " : (");
for (i = first_root_var_partition (rv, x);
i != ROOT_VAR_NONE;
i = next_root_var_partition (rv, i))
{
! print_generic_expr (stderr, partition_to_var (rv->map, i), TDF_SLIM);
fprintf (f, " ");
}
fprintf (f, ")\n");
--- 720,732 ----
fprintf (f, "Root Var dump\n");
for (x = 0; x < num_root_vars (rv); x++)
{
! print_generic_expr (f, root_var (rv, x), TDF_SLIM);
fprintf (f, " : (");
for (i = first_root_var_partition (rv, x);
i != ROOT_VAR_NONE;
i = next_root_var_partition (rv, i))
{
! print_generic_expr (f, partition_to_var (rv->map, i), TDF_SLIM);
fprintf (f, " ");
}
fprintf (f, ")\n");
*************** dump_root_var (f, rv)
*** 702,738 ****
/* Output a partition. */
void
! dump_var_map (f, map, dump_flags)
FILE *f;
var_map map;
- int dump_flags;
{
int t;
unsigned x, y;
int p;
fprintf (f, "\nPartition map \n\n");
- if (dump_flags & TDF_DETAILS)
- {
- for (x = 1; x <= next_ssa_version; x++)
- {
- p = partition_find (map->var_partition, x);
- if (map->partition_to_compact)
- p = map->partition_to_compact[p];
- fprintf (f, "ver %3d -> partition %3d (", x, p);
- if (p >= 0)
- {
- print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
- if (TREE_CODE (partition_to_var (map, p)) == SSA_NAME)
- {
- fprintf (f, " - \n");
- print_generic_stmt (f, SSA_NAME_DEF_STMT (partition_to_var (map, p)), TDF_SLIM);
- }
- }
- fprintf (f, ")\n");
- }
- fprintf (f, "\n\n");
- }
for (x = 0; x < map->num_partitions; x++)
{
--- 739,753 ----
/* Output a partition. */
void
! dump_var_map (f, map)
FILE *f;
var_map map;
{
int t;
unsigned x, y;
int p;
fprintf (f, "\nPartition map \n\n");
for (x = 0; x < map->num_partitions; x++)
{
*************** dump_var_map (f, map, dump_flags)
*** 743,748 ****
--- 758,764 ----
if (map->partition_to_var[p] == NULL_TREE)
continue;
+
t = 0;
for (y = 1; y < next_ssa_version; y++)
{
*************** dump_var_map (f, map, dump_flags)
*** 753,767 ****
{
if (t++ == 0)
{
! fprintf(stderr, "Partition %d (", x);
print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
! fprintf (stderr, " - ");
}
! fprintf (stderr, "%d ", y);
}
}
if (t != 0)
! fprintf (stderr, ")\n");
}
fprintf (f, "\n");
}
--- 769,783 ----
{
if (t++ == 0)
{
! fprintf(f, "Partition %d (", x);
print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
! fprintf (f, " - ");
}
! fprintf (f, "%d ", y);
}
}
if (t != 0)
! fprintf (f, ")\n");
}
fprintf (f, "\n");
}
Index: tree-ssa-live.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-live.h,v
retrieving revision 1.1.2.3
diff -c -p -r1.1.2.3 tree-ssa-live.h
*** tree-ssa-live.h 26 Apr 2003 03:04:04 -0000 1.1.2.3
--- tree-ssa-live.h 7 May 2003 18:50:02 -0000
*************** typedef struct _var_map
*** 44,55 ****
} *var_map;
#define VAR_ANN_PARTITION(ann) (ann->partition)
#define NO_PARTITION -1
extern var_map init_var_map PARAMS ((int));
extern void delete_var_map PARAMS ((var_map));
! extern void dump_var_map PARAMS ((FILE *, var_map, int));
extern int var_union PARAMS ((var_map, tree, tree));
extern void change_partition_var PARAMS ((var_map, tree, int));
extern var_map create_ssa_var_map PARAMS ((void));
--- 44,61 ----
} *var_map;
#define VAR_ANN_PARTITION(ann) (ann->partition)
+ #define VAR_ANN_ROOT_INDEX(ann) (ann->root_index)
#define NO_PARTITION -1
+ /* Flags to pass to compact_var_map */
+
+ #define VARMAP_NORMAL 0
+ #define VARMAP_NO_SINGLE_DEFS 1
+
extern var_map init_var_map PARAMS ((int));
extern void delete_var_map PARAMS ((var_map));
! extern void dump_var_map PARAMS ((FILE *, var_map));
extern int var_union PARAMS ((var_map, tree, tree));
extern void change_partition_var PARAMS ((var_map, tree, int));
extern var_map create_ssa_var_map PARAMS ((void));
*************** var_to_partition_to_var (map, var)
*** 123,128 ****
--- 129,136 ----
int part;
part = var_to_partition (map, var);
+ if (part == NO_PARTITION)
+ return NULL_TREE;
return partition_to_var (map, part);
}
*************** find_root_var (rv, i)
*** 308,314 ****
if (TREE_CODE (t) == SSA_NAME)
t = SSA_NAME_VAR (t);
ann = var_ann (t);
! return (VAR_ANN_PARTITION (ann));
}
#endif /* _TREE_SSA_LIVE_H */
--- 316,322 ----
if (TREE_CODE (t) == SSA_NAME)
t = SSA_NAME_VAR (t);
ann = var_ann (t);
! return (VAR_ANN_ROOT_INDEX (ann));
}
#endif /* _TREE_SSA_LIVE_H */
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.74
diff -c -p -r1.1.4.74 tree-ssa.c
*** tree-ssa.c 6 May 2003 15:31:41 -0000 1.1.4.74
--- tree-ssa.c 7 May 2003 18:50:03 -0000
*************** insert_copy_on_edge (e, dest, src)
*** 920,925 ****
--- 920,934 ----
tree copy;
copy = build (MODIFY_EXPR, TREE_TYPE (dest), dest, src);
+ if (tree_ssa_dump_file && (tree_ssa_dump_flags & TDF_DETAILS))
+ {
+ fprintf (tree_ssa_dump_file,
+ "Inserting a copy on edge BB%d->BB%d :",
+ e->src->index,
+ e->dest->index);
+ print_generic_expr (tree_ssa_dump_file, copy, tree_ssa_dump_flags);
+ fprintf (tree_ssa_dump_file, "\n");
+ }
bsi_insert_on_edge (e, copy);
}
*************** add_conflicts_if_valid (rv, graph, map,
*** 1231,1238 ****
}
}
! /* Reduce the number of live ranges in the var_map. We don't associate any
! actual variables with partitions yet, its still left in SSA form. */
static void
coalesce_ssa_name (map)
--- 1240,1249 ----
}
}
! /* Reduce the number of live ranges in the var_map. The only partitions
! which are associated with actual variables are those which are forced
! to be coalesced for various reason. (live on entry, live across abnormal
! edges, etc.) */
static void
coalesce_ssa_name (map)
*************** coalesce_ssa_name (map)
*** 1244,1265 ****
varray_type stmt_stack, ops;
tree stmt;
sbitmap live;
! tree *var_p, var;
root_var_p rv;
tree_live_info_p liveinfo;
if (num_var_partitions (map) <= 1)
return;
liveinfo = calculate_live_on_entry (map);
calculate_live_on_exit (liveinfo);
-
graph = conflict_graph_new (num_var_partitions (map));
-
live = sbitmap_alloc (num_var_partitions (map));
-
rv = init_root_var (map);
FOR_EACH_BB (bb)
{
/* Start with live on exit temporaries. */
--- 1255,1277 ----
varray_type stmt_stack, ops;
tree stmt;
sbitmap live;
! tree *var_p, var, tmp, phi;
root_var_p rv;
tree_live_info_p liveinfo;
+ edge e;
+ var_ann_t ann;
if (num_var_partitions (map) <= 1)
return;
liveinfo = calculate_live_on_entry (map);
calculate_live_on_exit (liveinfo);
graph = conflict_graph_new (num_var_partitions (map));
live = sbitmap_alloc (num_var_partitions (map));
rv = init_root_var (map);
+ /* Build a conflict graph. */
+
FOR_EACH_BB (bb)
{
/* Start with live on exit temporaries. */
*************** coalesce_ssa_name (map)
*** 1324,1333 ****
});
}
delete_tree_live_info (liveinfo);
sbitmap_free (live);
! VARRAY_INT_INIT (ops, num_var_partitions (map), "ops");
for (x = 0; x < num_root_vars (rv); x++)
{
while (first_root_var_partition (rv, x) != ROOT_VAR_NONE)
--- 1336,1456 ----
});
}
+ /* First, coalesce all live on entry variables to their root variable.
+ This will ensure the first use is coming from the right memory location. */
+
+ sbitmap_zero (live);
+
+ /* Set 'live' vector to indicate live on entry partitions. */
+
+ num = num_var_partitions (map);
+ for (x = 0 ; x < num; x++)
+ for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
+ if (e->dest != EXIT_BLOCK_PTR)
+ {
+ if (TEST_BIT (live_entry_blocks (liveinfo, x), e->dest->index))
+ SET_BIT (live, x);
+ }
delete_tree_live_info (liveinfo);
+
+ /* Assign root variable as partition representative for each live on entry
+ partition. */
+ EXECUTE_IF_SET_IN_SBITMAP (live, 0, x,
+ {
+ var = root_var (rv, find_root_var (rv, x));
+ ann = var_ann (var);
+ /* If these aren't already coalesced... */
+ if (partition_to_var (map, x) != var)
+ {
+ if (ann->out_of_ssa_tag)
+ {
+ /* This root variable has already been assigned to another
+ partition which is not coalesced with this one. */
+ abort ();
+ }
+
+ if (tree_ssa_dump_file && (tree_ssa_dump_flags & TDF_DETAILS))
+ {
+ fprintf (tree_ssa_dump_file, "Must coalesce ");
+ print_generic_expr (tree_ssa_dump_file,
+ partition_to_var (map, x),
+ TDF_SLIM);
+ fprintf (tree_ssa_dump_file, " with the root variable ");
+ print_generic_expr (tree_ssa_dump_file, var, TDF_SLIM);
+ fprintf (tree_ssa_dump_file, ".\n");
+ }
+
+ change_partition_var (map, var, x);
+ }
+ });
+
sbitmap_free (live);
! /* Code cannot be inserted on abnormal edges. Look for all abnormal
! edges, and coalesce any PHI results with their arguments across
! that edge. */
!
! FOR_EACH_BB (bb)
! for (e = bb->succ; e; e = e->succ_next)
! if (e->dest != EXIT_BLOCK_PTR && e->flags & EDGE_ABNORMAL)
! for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
! {
! /* Visit each PHI on the destination side of this abnormal
! edge, and attempt to coalesce the argument with the result. */
! var = PHI_RESULT (phi);
! x = var_to_partition (map, var);
! y = phi_arg_from_edge (phi, e);
! if (y == -1)
! abort ();
! tmp = PHI_ARG_DEF (phi, y);
! y = var_to_partition (map, tmp);
! if (x == NO_PARTITION || y == NO_PARTITION)
! abort ();
! if (find_root_var (rv, x) != find_root_var (rv, y))
! {
! /* FIXME. If the root variables are not the same, we
! can't coalesce the partitions, but maybe we can create
! a new version of the PHI_RESULT variable, issue
! a copy in the DEST block instead, and use it in the
! PHI node. Adding a new partition/version at this point
! is really a bad idea, so for now, PUNT!. */
! error ("Different root vars across an abnormal edge\n");
! }
!
! if (x != y)
! {
! if (!conflict_graph_conflict_p (graph, x, y))
! {
! /* NOw map the partitions back to their real variables. */
! var = partition_to_var (map, x);
! tmp = partition_to_var (map, y);
! if (tree_ssa_dump_file
! && (tree_ssa_dump_flags & TDF_DETAILS))
! {
! fprintf (tree_ssa_dump_file , "ABNORMAL: Coalescing ");
! print_generic_expr (tree_ssa_dump_file,
! var,
! TDF_SLIM);
! fprintf (tree_ssa_dump_file , " and ");
! print_generic_expr (tree_ssa_dump_file,
! tmp,
! TDF_SLIM);
! fprintf (tree_ssa_dump_file , " over abnormal edge.\n");
! }
! var_union (map, var, tmp);
! conflict_graph_merge_regs (graph, x, y);
! }
! else
! error ("Vars Conflict across an abnormal edge\n");
! }
! }
!
! if (tree_ssa_dump_file && (tree_ssa_dump_flags & TDF_DETAILS))
! {
! dump_var_map (tree_ssa_dump_file, map);
! }
!
!
for (x = 0; x < num_root_vars (rv); x++)
{
while (first_root_var_partition (rv, x) != ROOT_VAR_NONE)
*************** coalesce_ssa_name (map)
*** 1340,1351 ****
z != ROOT_VAR_NONE;
z = next_root_var_partition (rv, z))
{
! if (!conflict_graph_conflict_p (graph, y, z))
! {
! var_union (map, var, partition_to_var (map, z));
! remove_root_var_partition (rv, x, z);
! conflict_graph_merge_regs (graph, y, z);
! }
}
}
}
--- 1463,1479 ----
z != ROOT_VAR_NONE;
z = next_root_var_partition (rv, z))
{
! tmp = partition_to_var (map, z);
! /* If partitions are already merged, don't check for conflict. */
! if (tmp == var)
! remove_root_var_partition (rv, x, z);
! else
! if (!conflict_graph_conflict_p (graph, y, z))
! {
! var_union (map, var, tmp);
! remove_root_var_partition (rv, x, z);
! conflict_graph_merge_regs (graph, y, z);
! }
}
}
}
*************** coalesce_ssa_name (map)
*** 1354,1367 ****
conflict_graph_delete (graph);
}
! /* Take the ssa-name var_map, and make real variables out of each partition.
! This will be used to make each SSA-version varaiable to a real variable. */
static void
assign_vars (map)
var_map map;
{
! int x, i;
tree t, var;
var_ann_t ann;
root_var_p rv;
--- 1482,1494 ----
conflict_graph_delete (graph);
}
! /* Take the ssa-name var_map, and assign real variables to each partition. */
static void
assign_vars (map)
var_map map;
{
! int x, i, num;
tree t, var;
var_ann_t ann;
root_var_p rv;
*************** assign_vars (map)
*** 1370,1383 ****
if (!rv)
return;
! for (x = 0; x < num_root_vars (rv); x++)
{
! var = root_var (rv, x);
! ann = var_ann (var);
! ann->out_of_ssa_tag = 0;
}
! for (x = 0; x < num_root_vars (rv); x++)
{
var = root_var (rv, x);
ann = var_ann (var);
--- 1497,1528 ----
if (!rv)
return;
! /* Coalescing may already have forced some partitions to their root
! variable. Find these and tag them. */
!
! num = num_var_partitions (map);
! for (x = 0; x < num; x++)
{
! var = partition_to_var (map, x);
! if (TREE_CODE (var) != SSA_NAME)
! {
! /* Coalescing will already have verified that more than one
! partition doesn't have the same root variable. Simply marked
! the variable as assigned. */
! ann = var_ann (var);
! ann->out_of_ssa_tag = 1;
! if (tree_ssa_dump_file && (tree_ssa_dump_flags & TDF_DETAILS))
! {
! fprintf(tree_ssa_dump_file, "partition %d has variable ", x);
! print_generic_expr (tree_ssa_dump_file, var, TDF_SLIM);
! fprintf(tree_ssa_dump_file, " assigned to it.\n");
! }
!
! }
}
! num = num_root_vars (rv);
! for (x = 0; x < num; x++)
{
var = root_var (rv, x);
ann = var_ann (var);
*************** assign_vars (map)
*** 1387,1393 ****
{
t = partition_to_var (map, i);
! if (t == var)
continue;
if (!ann->out_of_ssa_tag)
--- 1532,1538 ----
{
t = partition_to_var (map, i);
! if (t == var || TREE_CODE (t) != SSA_NAME)
continue;
if (!ann->out_of_ssa_tag)
*************** assign_vars (map)
*** 1396,1410 ****
continue;
}
! /* Since we still don't have passes that create overlapping live
! ranges, the code above should've coalesced all the versions of
! the variable together. */
! abort();
! #if 0
var = create_temp (t);
change_partition_var (map, var, i);
ann = var_ann (var);
! #endif
}
}
--- 1541,1569 ----
continue;
}
! if (tree_ssa_dump_file && (tree_ssa_dump_flags & TDF_DETAILS))
! {
! fprintf (tree_ssa_dump_file, "Overlap : '");
! print_generic_expr (tree_ssa_dump_file, t, TDF_SLIM);
! fprintf (tree_ssa_dump_file, "' conflicts with '");
! print_generic_expr (tree_ssa_dump_file, var, TDF_SLIM);
! }
!
! /* FIXME. Since we still don't have passes that create overlapping
! live ranges, the code above should've coalesced all the versions of
! the variable together. */
! abort ();
!
var = create_temp (t);
change_partition_var (map, var, i);
ann = var_ann (var);
!
! if (tree_ssa_dump_file && (tree_ssa_dump_flags & TDF_DETAILS))
! {
! fprintf (tree_ssa_dump_file, "' New temp: '");
! print_generic_expr (tree_ssa_dump_file, var, TDF_SLIM);
! fprintf (tree_ssa_dump_file, "'\n");
! }
}
}
*************** rewrite_out_of_ssa (fndecl)
*** 1430,1454 ****
block_stmt_iterator si;
edge e;
var_map map;
! tree phi;
elim_graph g;
int repeat;
timevar_push (TV_TREE_SSA_TO_NORMAL);
map = create_ssa_var_map ();
/* Shrink the map to include only referenced variables. Exclude variables
which have only one SSA version since there is nothing to coalesce. */
! compact_var_map (map, 1);
coalesce_ssa_name (map);
/* This is the final var list, so assign real variables to the different
partitions. Include single reference vars this time. */
! compact_var_map (map, 0);
assign_vars (map);
g = new_elim_graph (map->num_partitions);
g->map = map;
FOR_EACH_BB (bb)
--- 1589,1631 ----
block_stmt_iterator si;
edge e;
var_map map;
! tree phi, next;
elim_graph g;
int repeat;
timevar_push (TV_TREE_SSA_TO_NORMAL);
+ tree_ssa_dump_file = dump_begin (TDI_optimized, &tree_ssa_dump_flags);
+
map = create_ssa_var_map ();
/* Shrink the map to include only referenced variables. Exclude variables
which have only one SSA version since there is nothing to coalesce. */
! compact_var_map (map, VARMAP_NO_SINGLE_DEFS);
!
! if (tree_ssa_dump_file && (tree_ssa_dump_flags & TDF_DETAILS))
! dump_var_map (tree_ssa_dump_file, map);
coalesce_ssa_name (map);
+ if (tree_ssa_dump_file && (tree_ssa_dump_flags & TDF_DETAILS))
+ {
+ fprintf(tree_ssa_dump_file, "After Coalescing:\n");
+ dump_var_map (tree_ssa_dump_file, map);
+ }
+
/* This is the final var list, so assign real variables to the different
partitions. Include single reference vars this time. */
!
! compact_var_map (map, VARMAP_NORMAL);
assign_vars (map);
+ if (tree_ssa_dump_file && (tree_ssa_dump_flags & TDF_DETAILS))
+ {
+ fprintf(tree_ssa_dump_file, "After Root variable replacement:\n");
+ dump_var_map (tree_ssa_dump_file, map);
+ }
+
g = new_elim_graph (map->num_partitions);
g->map = map;
FOR_EACH_BB (bb)
*************** rewrite_out_of_ssa (fndecl)
*** 1494,1501 ****
phi = phi_nodes (bb);
if (phi)
! for (e = bb->pred; e; e = e->pred_next)
! eliminate_phi (e, phi_arg_from_edge (phi, e), g);
}
delete_elim_graph (g);
--- 1671,1686 ----
phi = phi_nodes (bb);
if (phi)
! {
! for (e = bb->pred; e; e = e->pred_next)
! eliminate_phi (e, phi_arg_from_edge (phi, e), g);
! for ( ; phi; phi = next)
! {
! next = TREE_CHAIN (phi);
! remove_phi_node (phi, NULL_TREE, bb);
! }
! }
!
}
delete_elim_graph (g);
*************** rewrite_out_of_ssa (fndecl)
*** 1516,1521 ****
--- 1701,1709 ----
delete_tree_cfg ();
delete_var_map (map);
timevar_pop (TV_TREE_SSA_TO_NORMAL);
+
+ if (tree_ssa_dump_file)
+ dump_end (TDI_optimized, tree_ssa_dump_file);
}
*************** rewrite_stmt (si, block_defs_p, block_av
*** 2038,2047 ****
a point where more than one version of the LHS is live at the
same time. */
#if 0
- register_new_def (*def_p, cached_lhs, block_defs_p);
ssa_stats.num_re++;
! bsi_remove (si);
! return;
#else
if (var_is_live (cached_lhs, ann->bb))
{
--- 2226,2234 ----
a point where more than one version of the LHS is live at the
same time. */
#if 0
ssa_stats.num_re++;
! TREE_OPERAND (stmt, 1) = cached_lhs;
! ann->modified = 1;
#else
if (var_is_live (cached_lhs, ann->bb))
{
More information about the Gcc-patches
mailing list