This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] un-ssa - part 1
- From: Andrew MacLeod <amacleod at redhat dot com>
- To: gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: 31 Mar 2003 22:15:16 -0500
- Subject: [tree-ssa] un-ssa - part 1
This patch takes a first crack at the un-ssa pass. It implements a basic
partitioner which doesn't do anything different than we have today (ie, it
puts all versions of a variable into the same partition, so we still
aren't taking care of overlapping live ranges.).
It also implements the un-ssa algorithm out of Morgans book. Since everything
is in the same partition, it doesn't really do a lot of work just yet :-).
I'm working on a coalescing partitioner which will take care of the
overlapping live ranges, and that will exercise the implementation
of the algorithm a lot better.
I've also changed the implementation of bsi_insert_on_edge() so that it no
longer performs the insert immediately. Instead the stmts are queued up on
edges, and are all performed at once via a call to bsi_commit_edge_inserts().
This is the way the rtl optimizer handles it, and turns out to have less
side effects. Ie,
FOR_EACH_BB (bb)
{
...
f(bb)
...
}
if f() inserts something on an edge which causes a new basic block to be
created, the the FOR_EACH_BB() loop is going to also have an iteration for the
new basic block. *MAYBE*. It depends on where the new block is inserted.
That convinced me that we should probably queue them up. That and a lot of
algorithms aren't expecting new BB's to appear, especially if they
have allocated vectors over the BB indexes.
When the coalescing partitioner is ready, a few of these things will
change or get relocated, but I dont want too much stuff hanging around my
directory, especially if it doesnt need to be. This seems like a good time to
do a dump.
After the coalescing partition is ready, I'll work on optimizing it so
that this pass is faster than it is today.
This bootstraps and appears to cause no new failures. Is it OK to check in?
Oh, well, I think 20001226-1.c fails again at -O0 due to a time out. Shock of
shocks. If anyone thinks thats an issue, I can undo the changes to
rewrite_out_of_ssa() so that we don't actally call most of this code yet.
Andrew
2003-03-31 Andrew MacLeod <amacleod at redhat dot com>
* tree-cfg.c (PENDING_STMT, SET_PENDING_STMT): New Macros.
(bsi_insert_on_edge): Rename to bsi_commit_first_edge_insert. Add an
empty annotation record to the new basic_block.
(bsi_commit_edge_inserts): New. Commit all pending edge inserts.
(bsi_insert_on_edge): New. Add stmt to edge's pending insert list.
* tree-flow-inline.h (phi_arg_from_edge): Return PHI index for an edge.
(phi_element_for_edge): Return PHI elemnt for an edge.
* tree-flow.h (struct var_ann_d): Add auxiallary field and new
bit 'processed_out_of_ssa'.
* tree-ssa.c (_var_map): Structure for variable parition map.
(struct _elim_graph): Elimination graph for out-of-ssa pass.
(create_var_map): Create a new var_map.
(delete_var_map): Delete a var_map.
(var_from_parition): Return var for a specified partition.
(get_var_partition): Return partition a var belongs to.
(mapped_var_from_ref): Get root var for a var's partition.
(compress_var_map): Re-map the partitions to make the list dense.
(dump_var_parition): Print var_map.
(set_partition_for_var): Associate a real var with a partition.
(set_var_mapping): Associate an SSA version var with a real var.
(create_var_partition): Create a partition for processing.
(create_temp): Create a new temp variable for a partition.
(insert_copy_on_edge): Insert a copy between variables on an edge.
(new_elim_graph): Create a new elimination graph.
(delete_elim_graph): Delete an elimination graph.
(eliminate_name, eliminate_build, elim_forward,
elim_unvisited_predecessor, elim_backward, elim_create,
eliminate_phi): Routines to implement Morgans PHI elimination algorithm.
(eliminate_extraneous_phis): Eliminate PHI nodes which will never
generate code.
(rewrite_out_of_ssa): Use partitions and PHI elimination algorithm.
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.65
diff -c -p -r1.1.4.65 tree-cfg.c
*** tree-cfg.c 28 Mar 2003 21:46:50 -0000 1.1.4.65
--- tree-cfg.c 1 Apr 2003 00:04:19 -0000
*************** static bool value_matches_some_label PAR
*** 118,123 ****
--- 118,130 ----
static block_stmt_iterator bsi_init PARAMS ((tree *, basic_block));
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));
+
+ /* Location to track pending stmt for edge insertion. */
+ #define PENDING_STMT(e) ((tree)(e->insns))
+
+ /* Set the pending stmt field. */
+ #define SET_PENDING_STMT(e, t) ((e->insns) = (rtx)t)
/* Remove any COMPOUND_EXPR container from NODE. */
*************** bsi_insert_before (curr_bsi, t, mode)
*** 2798,2807 ****
/* 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
! stmt is added to the new block. */
! block_stmt_iterator
! bsi_insert_on_edge (e, stmt)
edge e;
tree stmt;
{
--- 2805,2814 ----
/* 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
! stmt is added to the new block. An iterator to the new stmt is returned. */
! static block_stmt_iterator
! bsi_commit_first_edge_insert (e, stmt)
edge e;
tree stmt;
{
*************** bsi_insert_on_edge (e, stmt)
*** 2810,2815 ****
--- 2817,2823 ----
tree_stmt_iterator tsi;
int single_exit, single_entry;
tree first, last, inserted_stmt;
+ bb_ann_t bb_ann;
first = last = NULL_TREE;
src = e->src;
*************** bsi_insert_on_edge (e, stmt)
*** 2902,2907 ****
--- 2910,2921 ----
redirect_edge_succ (e, new_bb);
make_edge (new_bb, dest, EDGE_FALLTHRU);
+ bb_ann = (bb_ann_t) xmalloc (sizeof (struct bb_ann_d));
+ new_bb->aux = bb_ann;
+ bb_ann->phi_nodes = NULL_TREE;
+ 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.
*************** bsi_insert_on_edge (e, stmt)
*** 2933,2935 ****
--- 2947,3026 ----
return bsi;
}
+
+ /* This routine will commit all pending edge insertions, creating any new
+ basic blocks which are necessary. The number of edges which were inserted
+ is returned. If the flag update_annotations is true, then new bitmaps are
+ created for the dominator children, and they are updated. If specified,
+ new_blocks returned a count of the number of new basic blocks which were
+ created. */
+ int
+ bsi_commit_edge_inserts (update_annotations, new_blocks)
+ int update_annotations;
+ int *new_blocks;
+ {
+ basic_block bb;
+ block_stmt_iterator bsi, ret;
+ edge e;
+ tree stmt, next_stmt;
+ int blocks, count = 0;
+
+ blocks = n_basic_blocks;
+
+ FOR_EACH_BB (bb)
+ {
+ for (e = bb->succ; e; e = e->succ_next)
+ if (PENDING_STMT (e))
+ {
+ stmt = PENDING_STMT (e);
+ SET_PENDING_STMT (e, NULL_TREE);
+ next_stmt = TREE_CHAIN (stmt);
+ /* The first insert will create a new basic block if needed. */
+ ret = bsi = bsi_commit_first_edge_insert (e, stmt);
+ count++;
+ stmt = next_stmt;
+ for ( ; stmt; stmt = next_stmt)
+ {
+ /* All further inserts can simply follow the first one. */
+ next_stmt = TREE_CHAIN (stmt);
+ bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
+ count++;
+ }
+
+ }
+ }
+
+ if (new_blocks)
+ *new_blocks = blocks - n_basic_blocks;
+
+ /* Expand arrays if we created new blocks and need to update them. */
+ if (update_annotations && blocks != n_basic_blocks)
+ {
+ /* TODO. Unimplemented at the moment. */
+ }
+
+ return count;
+ }
+
+ /* This routine adds a stmt to the pending list on an edge. No actual
+ insertion is made until a call to bsi_commit_edge_inserts () is made. */
+
+ void
+ bsi_insert_on_edge (e, stmt)
+ edge e;
+ tree stmt;
+ {
+ tree t;
+
+ t = PENDING_STMT (e);
+ if (!t)
+ SET_PENDING_STMT (e, stmt);
+ else
+ {
+ for ( ; TREE_CHAIN (t); t = TREE_CHAIN (t))
+ continue;
+ TREE_CHAIN (t) = stmt;
+ TREE_CHAIN (stmt) = NULL_TREE;
+ }
+
+ }
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow-inline.h,v
retrieving revision 1.1.2.30
diff -c -p -r1.1.2.30 tree-flow-inline.h
*** tree-flow-inline.h 18 Mar 2003 14:52:25 -0000 1.1.2.30
--- tree-flow-inline.h 1 Apr 2003 00:04:20 -0000
*************** phi_nodes (bb)
*** 316,321 ****
--- 316,357 ----
return bb_ann (bb)->phi_nodes;
}
+
+ /* Return the phi index number for an edge. */
+ static inline int
+ phi_arg_from_edge (phi, e)
+ tree phi;
+ edge e;
+ {
+ int i;
+ #if defined ENABLE_CHECKING
+ if (!phi || TREE_CODE (phi) != PHI_NODE)
+ abort();
+ #endif
+
+ for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ if (PHI_ARG_EDGE (phi, i) == e)
+ return i;
+
+ return -1;
+ }
+
+
+ /* Return the phi argument number for an edge. */
+ static inline struct phi_arg_d *
+ phi_element_for_edge (phi, e)
+ tree phi;
+ edge e;
+ {
+ int i;
+
+ i = phi_arg_from_edge (phi, e);
+ if (i != -1)
+ return &(PHI_ARG_ELT (phi, i));
+ else
+ return (struct phi_arg_d *)NULL;
+ }
+
static inline void
add_dom_child (bb, child_bb)
basic_block bb;
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.65
diff -c -p -r1.1.4.65 tree-flow.h
*** tree-flow.h 24 Mar 2003 20:27:57 -0000 1.1.4.65
--- tree-flow.h 1 Apr 2003 00:04:20 -0000
*************** struct var_ann_d GTY(())
*** 79,86 ****
/* Nonzero if the variable may be modified by function calls. */
unsigned is_call_clobbered : 1;
/* Unused bits. */
! unsigned unused : 26;
/* An INDIRECT_REF expression representing all the dereferences of this
pointer. Used to store aliasing information for pointer dereferences
--- 79,90 ----
/* Nonzero if the variable may be modified by function calls. */
unsigned is_call_clobbered : 1;
+ /* Used by the out of SSA pass to determine whether this var has been
+ seen yet or not. */
+ unsigned processed_out_of_ssa : 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
*************** struct var_ann_d GTY(())
*** 92,97 ****
--- 96,106 ----
/* Unique ID of this variable. */
size_t uid;
+
+ /* Other uses.
+ - Used when going out of SSA form to indicate which partition this
+ variable represents storage for. */
+ unsigned aux;
};
*************** enum bsi_iterator_update
*** 313,319 ****
extern void bsi_insert_before PARAMS ((block_stmt_iterator *, tree, enum bsi_iterator_update));
extern void bsi_insert_after PARAMS ((block_stmt_iterator *, tree, enum bsi_iterator_update));
! extern block_stmt_iterator bsi_insert_on_edge PARAMS ((edge, tree));
/* Stmt list insertion routines. */
--- 322,329 ----
extern void bsi_insert_before PARAMS ((block_stmt_iterator *, tree, enum bsi_iterator_update));
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 *));
/* Stmt list insertion routines. */
*************** void tree_ssa_dce PARAMS ((tree));
*** 462,467 ****
--- 472,480 ----
/* In tree-ssa-copyprop.c */
void tree_ssa_copyprop PARAMS ((tree));
+
+ static inline int phi_arg_from_edge PARAMS ((tree, edge));
+ static inline struct phi_arg_d *phi_element_for_edge PARAMS ((tree, edge));
#include "tree-flow-inline.h"
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.60
diff -c -p -r1.1.4.60 tree-ssa.c
*** tree-ssa.c 29 Mar 2003 03:42:32 -0000 1.1.4.60
--- tree-ssa.c 1 Apr 2003 00:04:22 -0000
*************** static htab_t avail_exprs;
*** 112,117 ****
--- 112,157 ----
propagation). */
static htab_t const_and_copies;
+ /* Used to create the variable mapping when we go out of SSA form. */
+ typedef struct _var_map
+ {
+ /* The partition of all ssa names. */
+ partition var_partition;
+
+ /* Compressed partition map */
+ int *compression;
+
+ /* Mapping of partition to vars. */
+ tree *partition_to_var;
+
+ unsigned int num_partitions;
+ } *var_map;
+
+ #define VAR_ANN_PARTITION(ann) (ann->aux)
+
+ /* Used to hold all the components requires to do SSA PHI elimination. */
+
+ typedef struct _elim_graph
+ {
+ /* Number of nodes in the elimination graph. */
+ int num_nodes;
+ /* The actual nodes in the elimination graph. */
+ tree *nodes;
+ /* The predecessor and successor list. */
+ sbitmap *pred;
+ sbitmap *succ;
+
+ /* Visited vector. */
+ sbitmap visited;
+ /* Stack for visited nodes. */
+ int *stack;
+ int top_of_stack;
+
+ /* The variable partition map. */
+ var_map map;
+ /* edge being eliminated by this graph. */
+ edge e;
+ } *elim_graph;
/* Statistics for dominator optimizations. */
struct ssa_stats_d
*************** static int avail_expr_eq PARAMS ((const
*** 165,170 ****
--- 205,234 ----
static struct def_blocks_d *get_def_blocks_for PARAMS ((tree));
static void htab_statistics PARAMS ((FILE *, htab_t));
+ static var_map create_var_map PARAMS ((int));
+ static void set_var_mapping PARAMS ((var_map, tree, sbitmap));
+ static var_map create_var_partition PARAMS ((void));
+ static inline tree mapped_var_from_ref PARAMS ((var_map, tree));
+ static void delete_var_map PARAMS ((var_map));
+ static int get_var_partition PARAMS ((var_map, tree));
+ static void set_partition_for_var PARAMS ((var_map, tree, int));
+ void dump_tree_partition PARAMS ((FILE *, var_map, int));
+ static void compress_var_map PARAMS ((var_map));
+ static inline tree var_from_partition PARAMS ((var_map, int));
+
+ static tree create_temp PARAMS ((tree));
+ static void insert_copy_on_edge PARAMS ((edge, tree, tree));
+ static elim_graph new_elim_graph PARAMS ((int));
+ static void delete_elim_graph PARAMS ((elim_graph));
+ static void eliminate_name PARAMS ((elim_graph, tree));
+ static void eliminate_build PARAMS ((elim_graph, basic_block, int));
+ static void elim_forward PARAMS ((elim_graph, int));
+ static int elim_unvisited_predecessor PARAMS ((elim_graph, int));
+ static void elim_backward PARAMS ((elim_graph, int));
+ static void elim_create PARAMS ((elim_graph, int));
+ static void eliminate_phi PARAMS ((edge, int, var_map));
+ static void eliminate_extraneous_phis PARAMS ((void));
+
/* FIXME: [UNSSA] Remove once the real unSSA pass is implemented. */
#if 1
static bool var_is_live PARAMS ((tree, basic_block));
*************** rewrite_block (bb, eq_expr_value)
*** 763,768 ****
--- 827,1481 ----
}
+
+ /* This is where the mapping from SSA version number to real storage variable
+ is tracked.
+
+ All SSA versions of the same variable may not ultimately be mapped back to
+ the same real variable. In that instance, we need to detect the live
+ range overlap, and give one of the variable new storage. The vector
+ 'partition_to_var' tracks which partition maps to whicvh variable.
+
+ Given a VAR, it is sometimes desirable to know which partition that VAR
+ represents. There is an additional field in the variable annotation to
+ track that information. */
+
+ /* Create the variable partition and initialize it. */
+
+ static var_map
+ create_var_map (size)
+ int size;
+ {
+ var_map map;
+
+ map = (var_map) xmalloc (sizeof (struct _var_map));
+ map->var_partition = partition_new (size);
+ map->partition_to_var
+ = (tree *)xmalloc (size * sizeof (tree));
+ memset (map->partition_to_var, 0, size * sizeof (tree));
+
+ map->compression = NULL;
+ map->num_partitions = size;
+ return map;
+ }
+
+ /* Free memory associated with a var_map. */
+
+ static void
+ delete_var_map (map)
+ var_map map;
+ {
+ free (map->partition_to_var);
+ partition_delete (map->var_partition);
+ if (map->compression)
+ free (map->compression);
+ free (map);
+ }
+
+
+ /* Given a partition number, return the variable which represents that
+ partition. */
+
+ static inline tree
+ var_from_partition (map, i)
+ var_map map;
+ int i;
+ {
+ return map->partition_to_var [i];
+ }
+
+ /* Given a variable, return the partition number which contains it. */
+
+ static int
+ get_var_partition (map, var)
+ var_map map;
+ tree var;
+ {
+ var_ann_t ann;
+ int part;
+
+ if (TREE_CODE (var) == SSA_NAME)
+ {
+ part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
+ if (map->compression)
+ part = map->compression[part];
+ }
+ else
+ {
+ ann = var_ann (var);
+ part = VAR_ANN_PARTITION (ann);
+ }
+ return part;
+ }
+
+ /* Given a variable, return the variable which represents the entire partition
+ the specified one is a member of. */
+
+ static inline tree
+ mapped_var_from_ref (map, var)
+ var_map map;
+ tree var;
+ {
+ int part;
+
+ part = get_var_partition (map, var);
+ return var_from_partition (map, part);
+ }
+
+ /* Compress the partition numbers such that they fall in the range
+ 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. */
+
+ static void
+ compress_var_map (map)
+ var_map map;
+ {
+ sbitmap used;
+ int x, limit, count, tmp;
+
+ limit = map->num_partitions;
+ used = sbitmap_alloc (limit);
+ sbitmap_zero (used);
+
+ map->compression = (int *)xmalloc (limit * sizeof (int));
+
+ /* Find out which partitions are actually referenced. */
+ count = 0;
+ for (x = 0; x < limit; x++)
+ {
+ map->compression[x] = x;
+ tmp = partition_find (map->var_partition, x);
+ if (!TEST_BIT (used, tmp) && map->partition_to_var[tmp] != NULL_TREE)
+ {
+ SET_BIT (used, tmp);
+ count++;
+ }
+ }
+
+ /* Build a compressed partitioning. */
+ if (count != limit)
+ {
+ count = 0;
+ /* SSA renaming begins at 1, so skip 0 when compressing. */
+ EXECUTE_IF_SET_IN_SBITMAP (used, 1, x,
+ {
+ map->compression[x] = count;
+ set_partition_for_var (map, map->partition_to_var[x], count);
+ count++;
+ });
+ }
+ else
+ {
+ free (map->compression);
+ map->compression = NULL;
+ }
+
+ map->num_partitions = count;
+ sbitmap_free (used);
+ }
+
+
+ /* For debuging. Output a partition. */
+
+ void
+ dump_tree_partition (f, map, dump_flags)
+ FILE *f;
+ var_map map;
+ int dump_flags;
+ {
+ int t;
+ unsigned x, y, 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->compression)
+ p = map->compression[p];
+ fprintf (f, "ver %3d -> partition %3d (", x, p);
+ print_generic_expr (f, var_from_partition (map, p), TDF_SLIM);
+ fprintf (f, ")\n");
+ }
+ fprintf (f, "\n\n");
+ }
+
+ for (x = 0; x < map->num_partitions; x++)
+ {
+ if (map->partition_to_var[x] == NULL_TREE)
+ continue;
+ t = 0;
+ for (y = 1; y < next_ssa_version; y++)
+ {
+ p = partition_find (map->var_partition, y);
+ if (map->compression)
+ p = map->compression[p];
+ if (p == x)
+ {
+ if (t++ == 0)
+ {
+ fprintf(stderr, "Partition %d (", x);
+ print_generic_expr (f, var_from_partition (map, p), TDF_SLIM);
+ fprintf (stderr, " - ");
+ }
+ fprintf (stderr, "%d ", y);
+ }
+ }
+ if (t != 0)
+ fprintf (stderr, ")\n");
+ }
+ fprintf (f, "\n");
+ }
+
+ /* Set the partition mapping fields for a var. Eventually, this routine
+ needs to recognize overlapping live ranges, and assign different variables
+ for overlapping ranges. Right now, we just stupidly always use the
+ root variable. */
+
+ static void
+ set_partition_for_var (map, var, part)
+ var_map map;
+ tree var;
+ int part;
+ {
+ var_ann_t ann;
+
+ ann = var_ann (var);
+ ann->processed_out_of_ssa = 1;
+ VAR_ANN_PARTITION (ann) = part;
+ map->partition_to_var[part] = var;
+ }
+
+ /* Used to map an ssa versioned var to a real var. */
+
+ static void
+ set_var_mapping (map, ssa_var, visited)
+ var_map map;
+ tree ssa_var;
+ sbitmap visited;
+ {
+ var_ann_t ann;
+ tree var;
+ int version;
+
+ var = SSA_NAME_VAR (ssa_var);
+ ann = var_ann (var);
+ version = SSA_NAME_VERSION (ssa_var);
+ if (TEST_BIT (visited, version))
+ return;
+ SET_BIT (visited, version);
+ if (!ann->processed_out_of_ssa)
+ {
+ /* First time var is processed, give it this partition. */
+ set_partition_for_var (map, var, version);
+ }
+ else
+ {
+ /* Dummy version. Make all versions refer to the root
+ version for that variable. Ultimately, we need to
+ look for overlapping live ranges and create new
+ variables for those instead of this. */
+ VAR_ANN_PARTITION (ann)
+ = partition_union (map->var_partition,
+ VAR_ANN_PARTITION (ann),
+ version);
+ map->partition_to_var[VAR_ANN_PARTITION (ann)] = var;
+ }
+ }
+
+
+ /* This looks through the function to determine what SSA versioned variables
+ need to have entries in the partition table. Partitions are created, and
+ variables are asigned to represents partitions.
+
+ *TODO* Currently, we simply make all versioned versions of a variable map to
+ that variable. This will create incorrect code when there are overlapping
+ live ranges. The correct fix to this is coming, it will be different version
+ of this function which puts overlapping live ranges into different
+ partitions. */
+
+ static var_map
+ create_var_partition ()
+ {
+ block_stmt_iterator bsi;
+ basic_block bb;
+ tree *dest;
+ tree stmt;
+ varray_type ops;
+ unsigned x;
+ int i;
+ var_map map;
+ tree phi;
+ sbitmap visited;
+
+ map = create_var_map (next_ssa_version + 1);
+
+ visited = sbitmap_alloc (next_ssa_version + 1);
+ sbitmap_zero (visited);
+
+ FOR_EACH_BB (bb)
+ {
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ stmt = bsi_stmt (bsi);
+ get_stmt_operands (stmt);
+
+ ops = use_ops (stmt);
+ for (x = 0; ops && x < VARRAY_ACTIVE_SIZE (ops); x++)
+ {
+ tree *use = VARRAY_GENERIC_PTR (ops, x);
+ set_var_mapping (map, *use, visited);
+ }
+
+ dest = def_op (stmt);
+ if (dest)
+ set_var_mapping (map, *dest, visited);
+
+ }
+
+ for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ {
+ set_var_mapping (map, PHI_RESULT (phi), visited);
+ for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ set_var_mapping (map, PHI_ARG_DEF (phi, i), visited);
+
+ }
+ }
+
+ sbitmap_free (visited);
+ return map;
+ }
+
+
+ /* This function will create a temporary for a partition based on the
+ type of the variable which already represents a partition. */
+
+ static tree
+ create_temp (t)
+ tree t;
+ {
+ tree tmp;
+ const char *name = NULL;
+ tree type;
+
+ if (TREE_CODE (t) != VAR_DECL
+ && TREE_CODE (t) != PARM_DECL
+ && TREE_CODE (t) != INDIRECT_REF)
+ abort ();
+
+ if (TREE_CODE (t) == INDIRECT_REF)
+ {
+ if (TREE_CODE (TREE_OPERAND (t, 0)) != VAR_DECL
+ && TREE_CODE (TREE_OPERAND (t, 0)) != PARM_DECL)
+ abort ();
+ type = TREE_TYPE (TREE_OPERAND (t,0));
+ tmp = DECL_NAME (TREE_OPERAND(t, 0));
+ if (tmp)
+ name = IDENTIFIER_POINTER (tmp);
+ }
+ else
+ {
+ type = TREE_TYPE (t);
+ tmp = DECL_NAME (t);
+ if (tmp)
+ name = IDENTIFIER_POINTER (tmp);
+ }
+
+ if (name == NULL)
+ name = "temp";
+ tmp = create_tmp_var (type, name);
+ create_var_ann (tmp);
+ return tmp;
+ }
+
+
+ /* This helper function fill insert a copy from one variable to another
+ on the specified edge. */
+
+ static void
+ insert_copy_on_edge (e, dest, src)
+ edge e;
+ tree dest, src;
+ {
+ tree copy;
+
+ copy = build (MODIFY_EXPR, TREE_TYPE (dest), dest, src);
+ bsi_insert_on_edge (e, copy);
+ }
+
+ /* --------------------------------------------------------------------- */
+ /* Create an elimination graph and associated data structures. */
+
+ static elim_graph
+ new_elim_graph (size)
+ int size;
+ {
+ elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
+ g->num_nodes = 0;
+ g->nodes = (tree *) xmalloc (sizeof (tree) * size);
+ memset (g->nodes, 0, sizeof (tree) * size);
+ g->pred = sbitmap_vector_alloc (size, size);
+ g->succ= sbitmap_vector_alloc (size, size);
+ sbitmap_vector_zero (g->pred, size);
+ sbitmap_vector_zero (g->succ, size);
+
+ return g;
+ }
+
+ /* Delete an elimination graph. */
+ static void
+ delete_elim_graph (g)
+ elim_graph g;
+ {
+ sbitmap_free (g->succ);
+ sbitmap_free (g->pred);
+ free (g->nodes);
+ free (g);
+ }
+
+ /* The following procedures implement the out of SSA algorithm detailed in
+ the Morgan Book pages 176-186. */
+
+
+ /* Add T to the elimination graph. */
+
+ static void
+ eliminate_name (g, T)
+ elim_graph g;
+ tree T;
+ {
+ int version = get_var_partition (g->map, T);
+ if (g->nodes[version] == NULL)
+ {
+ g->nodes[version] = T;
+ g->num_nodes++;
+ }
+ }
+
+ /* Build the auxillary graph. */
+
+ static void
+ eliminate_build (g, B, i)
+ elim_graph g;
+ basic_block B;
+ int i;
+ {
+ tree phi;
+ tree T0, Ti;
+ int p0, pi;
+
+ for (phi = phi_nodes (B); phi; phi = TREE_CHAIN (phi))
+ {
+ T0 = mapped_var_from_ref (g->map, PHI_RESULT (phi));
+ Ti = mapped_var_from_ref (g->map, PHI_ARG_DEF (phi, i));
+ if (T0 != Ti)
+ {
+ eliminate_name (g, T0);
+ eliminate_name (g, Ti);
+ p0 = get_var_partition (g->map, T0);
+ pi = get_var_partition (g->map, Ti);
+ SET_BIT (g->pred[pi], p0);
+ SET_BIT (g->succ[p0], pi);
+ }
+ }
+ }
+
+ /* Push successors onto the stack depth first. */
+
+ static void
+ elim_forward (g, T)
+ elim_graph g;
+ int T;
+ {
+ int S;
+ SET_BIT (g->visited, T);
+ EXECUTE_IF_SET_IN_SBITMAP (g->succ[T], 0, S,
+ {
+ if (!TEST_BIT (g->visited, S))
+ elim_forward (g, S);
+ });
+ g->stack[g->top_of_stack] = T;
+ g->top_of_stack++;
+ }
+
+
+ /* Are there unvisited predecessors? */
+
+ static int
+ elim_unvisited_predecessor (g, T)
+ elim_graph g;
+ int T;
+ {
+ int P;
+ EXECUTE_IF_SET_IN_SBITMAP (g->pred[T], 0, P,
+ {
+ if (!TEST_BIT (g->visited, P))
+ return 1;
+ });
+ return 0;
+ }
+
+ /* Process predecessors first, and insert a copy. */
+
+ static void
+ elim_backward (g, T)
+ elim_graph g;
+ int T;
+ {
+ int P;
+ SET_BIT (g->visited, T);
+ EXECUTE_IF_SET_IN_SBITMAP (g->pred[T], 0, P,
+ {
+ if (!TEST_BIT (g->visited, P))
+ elim_backward (g, P);
+ insert_copy_on_edge (g->e,
+ var_from_partition (g->map, P),
+ var_from_partition (g->map, T));
+ });
+ }
+
+ /* Check for a SCR, and create a temporary if there is one, and break
+ the cycle. Then issue the copies. Otherwise, simply insert the
+ required copies. */
+
+ static void
+ elim_create (g, T)
+ elim_graph g;
+ int T;
+ {
+ tree U;
+ int P, S;
+
+ if (elim_unvisited_predecessor (g, T))
+ {
+ U = create_temp (var_from_partition (g->map, T));
+ insert_copy_on_edge (g->e, U, var_from_partition (g->map, T));
+ EXECUTE_IF_SET_IN_SBITMAP (g->pred[T], 0, P,
+ {
+ if (!TEST_BIT (g->visited, P))
+ {
+ elim_backward (g, P);
+ insert_copy_on_edge (g->e, var_from_partition (g->map, P), U);
+ }
+ });
+ }
+ else
+ {
+ EXECUTE_IF_SET_IN_SBITMAP (g->succ[T], 0, S,
+ {
+ SET_BIT (g->visited, T);
+ RESET_BIT (g->succ[T], S);
+ insert_copy_on_edge (g->e,
+ var_from_partition (g->map, T),
+ var_from_partition (g->map, S));
+ });
+ }
+
+ }
+
+ /* Eliminate all the phi nodes on this edge. */
+
+ static void
+ eliminate_phi (e, i, map)
+ edge e;
+ int i;
+ var_map map;
+ {
+ tree phi;
+ int num_phi = 0;
+ int num_nodes = 0;
+ elim_graph g;
+ int x, limit;
+ basic_block B = e->dest;
+
+ /* TODO. Sometimes edges are removed and the PHI nodes are not updated.
+ This results in an out of date PHI entry, and we should'd process these
+ yet. This should never happen.... eventually. */
+ if (i == -1)
+ return;
+
+ for (phi = phi_nodes (B); phi; phi = TREE_CHAIN (phi))
+ {
+ num_phi++;
+ }
+
+ num_nodes = map->num_partitions;
+ g = new_elim_graph (num_nodes);
+
+ g->e = e;
+ g->map = map;
+
+ eliminate_build (g, B, i);
+
+ if (g->num_nodes == 0)
+ {
+ delete_elim_graph (g);
+ return;
+ }
+
+ g->visited = sbitmap_alloc (num_nodes);
+ sbitmap_zero (g->visited);
+ g->stack = (int *) xmalloc (sizeof (int) * num_nodes);
+ g->top_of_stack = 0;
+
+ limit = g->num_nodes;
+ for (x = 0; limit; x++)
+ if (g->nodes[x])
+ {
+ limit--;
+ if (!TEST_BIT (g->visited, x))
+ elim_forward (g, x);
+ }
+
+ sbitmap_zero (g->visited);
+ while (g->top_of_stack > 0)
+ {
+ x = g->stack[--(g->top_of_stack)];
+ if (!TEST_BIT (g->visited, x))
+ elim_create (g, x);
+ }
+ }
+
+
+ /* Eliminate any PHI nodes which were for aliasing or other uses which
+ do not generate real code. This reduces the number of variables in
+ the partition. */
+
+ static void
+ eliminate_extraneous_phis ()
+ {
+ tree phi, result, last;
+ basic_block bb;
+ int code;
+
+ FOR_EACH_BB (bb)
+ {
+ phi = phi_nodes (bb);
+ for (last = NULL; phi; )
+ {
+ result = PHI_RESULT (phi);
+ code = TREE_CODE (TREE_TYPE (result));
+ if (code == ARRAY_TYPE
+ || code == RECORD_TYPE
+ || code == UNION_TYPE
+ || may_aliases (result)
+ || result == global_var)
+ {
+ phi = TREE_CHAIN (phi);
+ remove_phi_node (result, last, bb);
+ }
+ else
+ {
+ last = phi;
+ phi = TREE_CHAIN (phi);
+ }
+ }
+ }
+ }
+
/* Take function FNDECL out of SSA form.
FIXME: Need to support overlapping live ranges for different versions of
*************** rewrite_out_of_ssa (fndecl)
*** 779,813 ****
{
basic_block bb;
block_stmt_iterator si;
timevar_push (TV_TREE_SSA_TO_NORMAL);
FOR_EACH_BB (bb)
! for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
! {
! size_t i;
! varray_type ops;
! tree stmt = bsi_stmt (si);
! STRIP_NOPS (stmt);
!
! get_stmt_operands (stmt);
!
! if (def_op (stmt))
! {
! tree *def_p = def_op (stmt);
! *def_p = SSA_NAME_VAR (*def_p);
! }
!
! ops = use_ops (stmt);
! for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
! {
! tree *use_p = VARRAY_GENERIC_PTR (ops, i);
! *use_p = SSA_NAME_VAR (*use_p);
! }
! }
/* Flush out flow graph and SSA data. */
delete_tree_ssa (fndecl);
delete_tree_cfg ();
timevar_pop (TV_TREE_SSA_TO_NORMAL);
}
--- 1492,1561 ----
{
basic_block bb;
block_stmt_iterator si;
+ edge e;
+ var_map map;
+ tree phi;
+
+ eliminate_extraneous_phis ();
+ map = create_var_partition ();
+ compress_var_map (map);
timevar_push (TV_TREE_SSA_TO_NORMAL);
FOR_EACH_BB (bb)
! {
! for (si = bsi_start (bb); !bsi_end_p (si); )
! {
! size_t i, num_ops;
! varray_type ops;
! tree stmt = bsi_stmt (si);
! tree *use_p = NULL;
! int remove = 0, is_copy = 0;
!
! STRIP_NOPS (stmt);
! get_stmt_operands (stmt);
!
! if (TREE_CODE (stmt) == MODIFY_EXPR
! && (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME))
! is_copy = 1;
!
! ops = use_ops (stmt);
! num_ops = ((ops) ? VARRAY_ACTIVE_SIZE (ops) : 0);
!
! for (i = 0; i < num_ops; i++)
! {
! use_p = VARRAY_GENERIC_PTR (ops, i);
! *use_p = mapped_var_from_ref (map, *use_p);
! }
!
! if (def_op (stmt))
! {
! tree *def_p = def_op (stmt);
! *def_p = mapped_var_from_ref (map, *def_p);
!
! if (is_copy && num_ops == 1 && use_p && (*def_p == *use_p))
! remove = 1;
! }
!
! /* Remove copies of the form 'var = var'. */
! if (remove)
! bsi_remove (&si);
! else
! bsi_next (&si);
! }
!
! phi = phi_nodes (bb);
! if (phi)
! for (e = bb->pred; e; e = e->pred_next)
! eliminate_phi (e, phi_arg_from_edge (phi, e), map);
! }
!
! /* If any copies were inserted on edges, actualyl insert them now. */
! bsi_commit_edge_inserts (0, NULL);
/* Flush out flow graph and SSA data. */
delete_tree_ssa (fndecl);
delete_tree_cfg ();
+ delete_var_map (map);
timevar_pop (TV_TREE_SSA_TO_NORMAL);
}