New out of ssa Coalescer.

2006-12-10  Andrew MacLeod  <amacleod@redhat.com>

	* common.opt (-ftree-lrs): Remove live range splitting option.
	* makefile.in: Add tree-ssa-coalesce.o and reduce header dependancies.
	* opts.c (decode_options): Remove flag_tree_live_range_split.
	* tree-flow.h (struct var_ann_d): Rename fields from root_ to base_.
	* tree-flow-inline.h (single_imm_use_p): New.  Check for single use.
	* tree-outof-ssa.c: Remove header files which aren't needed.
	(SSANORM_*): Remove flags.
	(print_exprs_edge, coalesce_abnormal_edges, coalesce_phi_operands, 
	coalesce_result_decls_and_copies, coalesce_asm_operands): Remove.
	(coalesce_ssa_name): Move to tree-ssa-coalesce.c.
	(assign_vars): Use Basevar instead of root_var structure.
	(replace_def_variable): Dont do anything if def is replaceable.
	(remove_ssa_form): Integrate functional changes.
	(rewrite_out_of_ssa): Remove live-range_split option.
	* tree-ssa-coalesce.c: New File for ssa-name coalescing.
	(coalesce_cost): Calculate the cost of a coalesce.
	(coalesce_cost_bb): Calculate the coalesce cost within a BB.
	(coalesce_cost_edge): Calculate the coalesce cost on an edge.
	(pop_cost_one_pair): Remove the best coalesce with cost 1 from the list.
	(pop_best_coalesce): Remove the best coalesce from the list.
	(coalesce_pair_map_hash): Calculate coalesce pair hash.
	(coalesce_pair_map_eq): Compare 2 coalesce pairs for hash function.
	(create_coalesce_list): Create a coalesce list object.
	(delete_coalesce_list): Free a coalesce list object.
	(find_coalesce_pair): Find matching pair in the coalesce list.
	(add_cost_one_coalesce): Add a coalesce to the "cost one" list.
	(add_coalesce): Add a coalesce to the coalesce list.
	(compare_pairs): Comparision function to determine pair sorted order.
	(num_coalesce_pairs): Number of coalesced pairs.
	(first_coalesce_pair, end_coalesce_pair_p, next_coalesce_pair):
	Coalesce pair iterator functions.
	(sort_coalesce_list): Sort coalesce pairs in order of expense.
	(dump_coalesce_list): Show coalesce list.
	(ssa_conflicts_new): Create an SSA conflict graph.
	(ssa_conflicts_delete): Delete an SSA conflict graph.
	(ssa_conflicts_test_p): Test for conflicts.
	(ssa_conflicts_add_one): Add a single conflict.
	(ssa_conflicts_add): Add a conflict pair.
	(ssa_conflicts_merge): Merge conflicts.
	(struct live_track_d): Struct for tracking live partitions.
	(new_live_track): Create new live_track object.
	(delete_live_track): Delete a live_track object.
	(live_track_remove_partition): Remove a partition from the live list.
	(live_track_add_partition): Add a partition from the live list.
	(live_track_clear_var): Take VAR from the live list.
	(live_track_live_p): Is var live?
	(live_track_process_use): Make var come alive.
	(live_track_process_def): Make var go dead, add conflicts.
	(live_track_init): Initialize to a live on exit set.
	(live_track_clear_base_vars): Clear live partitions.
	(build_ssa_conflict_graph): Build a conflict graph.
	(print_exprs): Common debug output routine.
	(abnormal_corrupt): Output info about a failed coalesce across an
	abnormal edge.
	(fail_abnormal_edge_coalesce): Output info about a failed MUST_COALESCE.
	(create_outofssa_var_map): Create a var map and coalesce list.
	(attempt_coalesce): Coalesce a pair.
	(coalesce_partitions): Coalesce all pairs in a coalesce list.
	(coalesce_ssa_name): Entry point.  Determine what ssa_names to coalesce.
	* tree-ssa-live.c: Remove header files which aren't needed.
	(var_map_base_init): New.  Initialize a basevar list.
	(var_map_base_fini): New.  Finish a basevar list.
	(init_var_map): Initialize new fields.
	(delete_var_map): Free new fields.
	(var_union): Use renamed fields.
	(compact_var_map): Remove.
	(partition_to_view_init): Use renamed fields, change order of an if.
	(partition_view_fini): Use renamed fields.
	(partition_view_normal): Create basevar list if requested.
	(partition_view_bitmap): Create a view based on a bitmap of partitions.
	(change_partition_var): Use renamed fields.
	(create_ssa_var_map): Remove.
	(tpa_init, tpa_remove_partition, tpa_delete, tpa_compact,
	root_var_init): Remove.
	(partition_pair_map_hash, partition_pair_map_eq, create_coalesce_list,
	delete_coalesce_list, find_partition_pair, coalesce_cost, add_coalesce,
	compare_pairs, num_coalesce_pairs, first_partition_pair,
	end_partition_pair_p, next_partition_pair, sort_coalesce_list,
	pop_best_coalesce, add_conflicts_if_valid, set_if_valid,
	build_tree_conflict_graph, coalesce_tpa_members, dump_coalesce_list,
	tpa_dump): Moved to tree-ssa-coalesce.c and/or renamed there.
	(dump_var_map): Use renamed fields.
	* tree-ssa-live.h (struct  _var_map): Modify fields.
	(partition_to_var, version_to_var, var_to_partition): Use renamed 
	fields.
	(basevar_index): New.  Index of the base variable of a partition.
	(num_basevars): New.  Number of unique base variables in partition map.
	(register_ssa_partition): Use renamed fields.
	(struct tree_partition_associator_d): Remove.
	(tpa_num_trees, tpa_tree, tpa_first_partition, tpa_next_partition,
	tpa_find_tree, tpa_decompact, root_var_init, root_var_num,
	root_var, root_var_first_partition, root_var_next_partition,
	root_var_dump, root_var_delete, root_var_remove_partition, 
	root_var_find, root_var_compact, root_var_decompact): Remove.
	(struct partition_pair, struct coalesce_list_d): Moved to 
	tree-ssa-coalesce.c
	* tree-ssa-ter.c: Remove header files which aren't needed.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@119711 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 85 insertions, 310 deletions

diff --git a/gcc/tree-ssa-live.h b/gcc/tree-ssa-live.h
index 19c708922e8..bddd4ba77c6 100644
--- a/gcc/tree-ssa-live.h
+++ b/gcc/tree-ssa-live.h
@@ -26,56 +26,83 @@ Boston, MA 02110-1301, USA.  */
 #include "partition.h"
 #include "vecprim.h"
 
-/* Used to create the variable mapping when we go out of SSA form.  */
+
+
+/* Used to create the variable mapping when we go out of SSA form.  
+
+   Mapping from an ssa_name to a partition number is maintained, as well as
+   partition number to back to ssa_name. A parition can also be represented
+   by a non-ssa_name variable.  This allows ssa_names and thier partition to 
+   be coalesced with live on entry compiler variables, as well as eventually
+   having real compiler variables assigned to each partition as part of the 
+   final stage of going of of ssa.  
+
+   Non-ssa_names maintain their partition index in the variable annotation.
+
+   This data structure also supports "views", which work on a subset of all
+   partitions.  This allows the coalescer to decide what partitions are 
+   interesting to it, and only work with those partitions.  Whenever the view
+   is changed, the partition numbers change, but none of the partition groupings
+   change. (ie, it is truly a view since it doesnt change anything)
+
+   The final component of the data structure is the basevar map.  This provides
+   a list of all the different base variables which occue in a partition view,
+   and a unique index for each one. Routines are provided to quickly produce
+   the base variable of a partition.
+
+   Note that members of a partition MUST all have the same base variable.  */
+
 typedef struct _var_map
 {
-  /* The partition of all variables.  */
+  /* The partition manager of all variables.  */
   partition var_partition;
 
-  /* Vector for compacting partitions.  */
-  int *partition_to_compact;
-  int *compact_to_partition;
+  /* Vector for managing partitions views.  */
+  int *partition_to_view;
+  int *view_to_partition;
 
-  /* Mapping of partition numbers to vars.  */
+  /* Mapping of partition numbers to variables.  */
   tree *partition_to_var;
 
-  /* Current number of partitions.  */
+  /* Current number of partitions in var_map based on the current view.  */
   unsigned int num_partitions;
 
-  /* Original partition size.  */
+  /* Original full partition size.  */
   unsigned int partition_size;
+
+  /* Number of base variables in the base var list.  */
+  int num_basevars;
+
+  /* Map of partitions numbers to base variable table indexes.  */
+  int *partition_to_base_index;
+
+  /* Table of base variable's.  */
+  VEC (tree, heap) *basevars;
 } *var_map;
 
-#define VAR_ANN_PARTITION(ann) (ann->partition)
-#define VAR_ANN_ROOT_INDEX(ann) (ann->root_index)
 
-#define NO_PARTITION		-1
+/* Partition number of a  non ssa-name variable.  */
+#define VAR_ANN_PARTITION(ann) (ann->partition)
+/* Index iot the basevar table of a non ssa-name variable.  */
+#define VAR_ANN_BASE_INDEX(ann) (ann->base_index)
 
-/* Flags to pass to compact_var_map  */
 
-#define VARMAP_NORMAL		0
-#define VARMAP_NO_SINGLE_DEFS	1
+/* Value used to represent no partition number.  */
+#define NO_PARTITION		-1
 
 extern var_map init_var_map (int);
 extern void delete_var_map (var_map);
 extern void dump_var_map (FILE *, var_map);
 extern int var_union (var_map, tree, tree);
 extern void change_partition_var (var_map, tree, int);
-extern void compact_var_map (var_map, int);
+extern void partition_view_normal (var_map, bool);
+extern void partition_view_bitmap (var_map, bitmap, bool);
 #ifdef ENABLE_CHECKING
 extern void register_ssa_partition_check (tree ssa_var);
 #endif
 
-static inline unsigned num_var_partitions (var_map);
-static inline tree var_to_partition_to_var (var_map, tree);
-static inline tree partition_to_var (var_map, int);
-static inline int var_to_partition (var_map, tree);
-static inline tree version_to_var (var_map, int);
-static inline void register_ssa_partition (var_map, tree);
 
-extern var_map create_ssa_var_map (void);
-
-/* Number of partitions in MAP.  */
+/* Return number of partitions in MAP.  */
 
 static inline unsigned
 num_var_partitions (var_map map)
@@ -90,8 +117,8 @@ num_var_partitions (var_map map)
 static inline tree
 partition_to_var (var_map map, int i)
 {
-  if (map->compact_to_partition)
-    i = map->compact_to_partition[i];
+  if (map->view_to_partition)
+    i = map->view_to_partition[i];
   i = partition_find (map->var_partition, i);
   return map->partition_to_var[i];
 }
@@ -100,12 +127,13 @@ partition_to_var (var_map map, int i)
 /* Given ssa_name VERSION, if it has a partition in MAP,  return the var it 
    is associated with.  Otherwise return NULL.  */
 
-static inline tree version_to_var (var_map map, int version)
+static inline tree 
+version_to_var (var_map map, int version)
 {
   int part;
   part = partition_find (map->var_partition, version);
-  if (map->partition_to_compact)
-    part = map->partition_to_compact[part];
+  if (map->partition_to_view)
+    part = map->partition_to_view[part];
   if (part == NO_PARTITION)
     return NULL_TREE;
   
@@ -125,8 +153,8 @@ var_to_partition (var_map map, tree var)
   if (TREE_CODE (var) == SSA_NAME)
     {
       part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
-      if (map->partition_to_compact)
-	part = map->partition_to_compact[part];
+      if (map->partition_to_view)
+	part = map->partition_to_view[part];
     }
   else
     {
@@ -155,9 +183,29 @@ var_to_partition_to_var (var_map map, tree var)
 }
 
 
-/* This routine registers a partition for SSA_VAR with MAP.  IS_USE is used 
-   to count references.  Any unregistered partitions may be compacted out 
-   later.  */ 
+/* Return the index into the basevar table for PARTITION's base in MAP.  */
+
+static inline int
+basevar_index (var_map map, int partition)
+{
+  gcc_assert (partition >= 0 
+	      && partition <= (int) num_var_partitions (map));
+  return map->partition_to_base_index[partition];
+}
+
+
+/* Return the number of different base variables in MAP.  */
+
+static inline int
+num_basevars (var_map map)
+{
+  return map->num_basevars;
+}
+
+
+
+/* This routine registers a partition for SSA_VAR with MAP.  Any unregistered 
+   partitions may be filtered out by a view later.  */ 
 
 static inline void
 register_ssa_partition (var_map map, tree ssa_var)
@@ -170,7 +218,7 @@ register_ssa_partition (var_map map, tree ssa_var)
 
   version = SSA_NAME_VERSION (ssa_var);
   if (map->partition_to_var[version] == NULL_TREE)
-    map->partition_to_var[SSA_NAME_VERSION (ssa_var)] = ssa_var;
+    map->partition_to_var[version] = ssa_var;
 }
 
 
@@ -238,13 +286,6 @@ extern void delete_tree_live_info (tree_live_info_p);
 #define LIVEDUMP_ALL	(LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
 extern void dump_live_info (FILE *, tree_live_info_p, int);
 
-static inline int partition_is_global (tree_live_info_p, int);
-static inline bitmap live_on_entry (tree_live_info_p, basic_block);
-static inline bitmap live_on_exit (tree_live_info_p, basic_block);
-static inline var_map live_var_map (tree_live_info_p);
-static inline void live_merge_and_clear (tree_live_info_p, int, int);
-static inline void make_live_on_entry (tree_live_info_p, basic_block, int);
-
 
 /*  Return TRUE if P is marked as a global in LIVE.  */
 
@@ -316,275 +357,9 @@ make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
 }
 
 
-/* A tree_partition_associator (TPA)object is a base structure which allows
-   partitions to be associated with a tree object.
-
-   A varray of tree elements represent each distinct tree item.
-   A parallel int array represents the first partition number associated with 
-   the tree.
-   This partition number is then used as in index into the next_partition
-   array, which returns the index of the next partition which is associated
-   with the tree. TPA_NONE indicates the end of the list.  
-   A varray paralleling the partition list 'partition_to_tree_map' is used
-   to indicate which tree index the partition is in.  */
-
-typedef struct tree_partition_associator_d
-{
-  VEC(tree,heap) *trees;
-  VEC(int,heap) *first_partition;
-  int *next_partition;
-  int *partition_to_tree_map;
-  int num_trees;
-  int uncompressed_num;
-  var_map map;
-} *tpa_p;
-
-/* Value returned when there are no more partitions associated with a tree.  */
-#define TPA_NONE		-1
-
-static inline tree tpa_tree (tpa_p, int);
-static inline int tpa_first_partition (tpa_p, int);
-static inline int tpa_next_partition (tpa_p, int);
-static inline int tpa_num_trees (tpa_p);
-static inline int tpa_find_tree (tpa_p, int);
-static inline void tpa_decompact (tpa_p);
-extern void tpa_delete (tpa_p);
-extern void tpa_dump (FILE *, tpa_p);
-extern void tpa_remove_partition (tpa_p, int, int);
-extern int tpa_compact (tpa_p);
-
-
-/* Return the number of distinct tree nodes in TPA.  */
-
-static inline int
-tpa_num_trees (tpa_p tpa)
-{
-  return tpa->num_trees;
-}
-
-
-/* Return the tree node for index I in TPA.  */
-
-static inline tree
-tpa_tree (tpa_p tpa, int i)
-{
-  return VEC_index (tree, tpa->trees, i);
-}
-
-
-/* Return the first partition associated with tree list I in TPA.  */
-
-static inline int
-tpa_first_partition (tpa_p tpa, int i)
-{
-  return VEC_index (int, tpa->first_partition, i);
-}
-
-
-/* Return the next partition after partition I in TPA's list.  */
-
-static inline int
-tpa_next_partition (tpa_p tpa, int i)
-{
-  return tpa->next_partition[i];
-}
-
-
-/* Return the tree index from TPA whose list contains partition I.  
-   TPA_NONE is returned if I is not associated with any list.  */
-
-static inline int 
-tpa_find_tree (tpa_p tpa, int i)
-{
-  int index;
-
-  index = tpa->partition_to_tree_map[i];
-  /* When compressed, any index higher than the number of tree elements is 
-     a compressed element, so return TPA_NONE.  */
-  if (index != TPA_NONE && index >= tpa_num_trees (tpa))
-    {
-      gcc_assert (tpa->uncompressed_num != -1);
-      index = TPA_NONE;
-    }
-
-  return index;
-}
-
-
-/* This function removes any compaction which was performed on TPA.  */
-
-static inline void 
-tpa_decompact(tpa_p tpa)
-{
-  gcc_assert (tpa->uncompressed_num != -1);
-  tpa->num_trees = tpa->uncompressed_num;
-}
-
-
-/* Once a var_map has been created and compressed, a complementary root_var
-   object can be built.  This creates a list of all the root variables from
-   which ssa version names are derived.  Each root variable has a list of 
-   which partitions are versions of that root.  
-
-   This is implemented using the tree_partition_associator.
-
-   The tree vector is used to represent the root variable.
-   The list of partitions represent SSA versions of the root variable.  */
-
-typedef tpa_p root_var_p;
-
-static inline tree root_var (root_var_p, int);
-static inline int root_var_first_partition (root_var_p, int);
-static inline int root_var_next_partition (root_var_p, int);
-static inline int root_var_num (root_var_p);
-static inline void root_var_dump (FILE *, root_var_p);
-static inline void root_var_remove_partition (root_var_p, int, int);
-static inline void root_var_delete (root_var_p);
-static inline int root_var_find (root_var_p, int);
-static inline int root_var_compact (root_var_p);
-static inline void root_var_decompact (tpa_p);
-
-extern root_var_p root_var_init (var_map);
-
-/* Value returned when there are no more partitions associated with a root
-   variable.  */
-#define ROOT_VAR_NONE		TPA_NONE
-
-
-/* Return the number of distinct root variables in RV.  */
-
-static inline int 
-root_var_num (root_var_p rv)
-{
-  return tpa_num_trees (rv);
-}
-
-
-/* Return root variable I from RV.  */
-
-static inline tree
-root_var (root_var_p rv, int i)
-{
-  return tpa_tree (rv, i);
-}
-
-
-/* Return the first partition in RV belonging to root variable list I.  */
-
-static inline int
-root_var_first_partition (root_var_p rv, int i)
-{
-  return tpa_first_partition (rv, i);
-}
-
-
-/* Return the next partition after partition I in a root list from RV.  */
-
-static inline int
-root_var_next_partition (root_var_p rv, int i)
-{
-  return tpa_next_partition (rv, i);
-}
-
-
-/* Send debug info for root_var list RV to file F.  */
-
-static inline void
-root_var_dump (FILE *f, root_var_p rv)
-{
-  fprintf (f, "\nRoot Var dump\n");
-  tpa_dump (f, rv);
-  fprintf (f, "\n");
-}
-
+/* From tree-ssa-coalesce.c  */
+extern var_map coalesce_ssa_name (void);
 
-/* Destroy root_var object RV.  */
-
-static inline void
-root_var_delete (root_var_p rv)
-{
-  tpa_delete (rv);
-}
-
-
-/* Remove partition PARTITION_INDEX from root_var list ROOT_INDEX in RV.  */
-
-static inline void
-root_var_remove_partition (root_var_p rv, int root_index, int partition_index)
-{
-  tpa_remove_partition (rv, root_index, partition_index);
-}
-
-
-/* Return the root_var list index for partition I in RV.  */
-
-static inline int
-root_var_find (root_var_p rv, int i)
-{
-  return tpa_find_tree (rv, i);
-}
-
-
-/* Hide single element lists in RV.  */
-
-static inline int 
-root_var_compact (root_var_p rv)
-{
-  return tpa_compact (rv);
-}
-
-
-/* Expose the single element lists in RV.  */
-
-static inline void
-root_var_decompact (root_var_p rv)
-{
-  tpa_decompact (rv);
-}
-
-
-/* This set of routines implements a coalesce_list. This is an object which
-   is used to track pairs of partitions which are desirable to coalesce
-   together at some point.  Costs are associated with each pair, and when 
-   all desired information has been collected, the object can be used to 
-   order the pairs for processing.  */
-
-/* This structure defines a pair entry.  */
-
-typedef struct partition_pair
-{
-  int first_partition;
-  int second_partition;
-  int cost;
-} * partition_pair_p;
-
-extern unsigned int partition_pair_map_hash (const void *);
-extern int partition_pair_map_eq (const void *, const void *);
-
-/* This structure maintains the list of coalesce pairs.  */
-
-typedef struct coalesce_list_d 
-{
-  var_map map;
-  htab_t list;
-  partition_pair_p *sorted;
-  int num_sorted;
-  bool add_mode;
-} *coalesce_list_p;
-
-extern coalesce_list_p create_coalesce_list (var_map);
-extern void add_coalesce (coalesce_list_p, int, int, int);
-extern int coalesce_cost (int, bool, bool);
-extern void sort_coalesce_list (coalesce_list_p);
-extern void dump_coalesce_list (FILE *, coalesce_list_p);
-extern void delete_coalesce_list (coalesce_list_p);
-
-#define NO_BEST_COALESCE	-1
-
-extern conflict_graph build_tree_conflict_graph (tree_live_info_p, tpa_p,
-						 coalesce_list_p);
-extern void coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map,
-				  coalesce_list_p cl, FILE *);
 
 /* From tree-ssa-ter.c  */
 extern tree *find_replaceable_exprs (var_map);