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.

From-SVN: r119711

1 files changed, 1355 insertions, 0 deletions

diff --git a/gcc/tree-ssa-coalesce.c b/gcc/tree-ssa-coalesce.c
new file mode 100644
index 0000000..0079361
--- /dev/null
+++ b/gcc/tree-ssa-coalesce.c
@@ -0,0 +1,1355 @@
+/* Coalesce SSA_NAMES together for the out-of-ssa pass.
+   Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc.
+   Contributed by Andrew MacLeod <amacleod@redhat.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to
+the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+Boston, MA 02110-1301, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "tree.h"
+#include "flags.h"
+#include "diagnostic.h"
+#include "bitmap.h"
+#include "tree-flow.h"
+#include "hashtab.h"
+#include "tree-dump.h"
+#include "tree-ssa-live.h"
+#include "toplev.h"
+
+
+/* This set of routines implements a coalesce_list.  This is an object which
+   is used to track pairs of ssa_names which are desirable to coalesce
+   together to avoid copies.  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 coalesce_pair
+{
+  int first_element;
+  int second_element;
+  int cost;
+} * coalesce_pair_p;
+
+typedef struct cost_one_pair_d
+{
+  int first_element;
+  int second_element;
+  struct cost_one_pair_d *next;
+} * cost_one_pair_p;
+
+/* This structure maintains the list of coalesce pairs.  */
+
+typedef struct coalesce_list_d 
+{
+  htab_t list;			/* Hash table.  */
+  coalesce_pair_p *sorted;	/* List when sorted.  */
+  int num_sorted;		/* Number in the sorted list.  */
+  cost_one_pair_p cost_one_list;/* Single use coalesces with cost 1.  */
+} *coalesce_list_p;
+
+#define NO_BEST_COALESCE	-1
+#define MUST_COALESCE_COST	INT_MAX
+
+
+/* Return cost of execution of copy instruction with FREQUENCY
+   possibly on CRITICAL edge and in HOT basic block.  */
+
+static inline int
+coalesce_cost (int frequency, bool hot, bool critical)
+{
+  /* Base costs on BB frequencies bounded by 1.  */
+  int cost = frequency;
+
+  if (!cost)
+    cost = 1;
+
+  if (optimize_size)
+    cost = 1;
+  else
+    /* It is more important to coalesce in HOT blocks.  */
+    if (hot)
+      cost *= 2;
+
+  /* Inserting copy on critical edge costs more than inserting it elsewhere.  */
+  if (critical)
+    cost *= 2;
+  return cost;
+}
+
+
+/* Return the cost of executing a copy instruction in basic block BB.  */
+
+static inline int 
+coalesce_cost_bb (basic_block bb)
+{
+  return coalesce_cost (bb->frequency, maybe_hot_bb_p (bb), false);
+}
+
+
+/* Return the cost of executing a copy instruction on edge E.  */
+
+static inline int 
+coalesce_cost_edge (edge e)
+{
+  if (e->flags & EDGE_ABNORMAL)
+    return MUST_COALESCE_COST;
+
+  return coalesce_cost (EDGE_FREQUENCY (e), 
+			maybe_hot_bb_p (e->src), 
+			EDGE_CRITICAL_P (e));
+}
+
+
+/* Retrieve a pair to coalesce from the cost_one_list in CL.  Returns the 
+   2 elements via P1 and P2.  1 is returned by the function if there is a pair,
+   NO_BEST_COALESCE is returned if there aren't any.  */
+
+static inline int
+pop_cost_one_pair (coalesce_list_p cl, int *p1, int *p2)
+{
+  cost_one_pair_p ptr;
+
+  ptr = cl->cost_one_list;
+  if (!ptr)
+    return NO_BEST_COALESCE;
+
+  *p1 = ptr->first_element;
+  *p2 = ptr->second_element;
+  cl->cost_one_list = ptr->next;
+
+  free (ptr);
+
+  return 1;
+}
+
+/* Retrieve the most expensive remaining pair to coalesce from CL.  Returns the 
+   2 elements via P1 and P2.  Their calculated cost is returned by the function.
+   NO_BEST_COALESCE is returned if the coalesce list is empty.  */
+
+static inline int
+pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2)
+{
+  coalesce_pair_p node;
+  int ret;
+
+  if (cl->sorted == NULL)
+    return pop_cost_one_pair (cl, p1, p2);
+
+  if (cl->num_sorted == 0)
+    return pop_cost_one_pair (cl, p1, p2);
+
+  node = cl->sorted[--(cl->num_sorted)];
+  *p1 = node->first_element;
+  *p2 = node->second_element;
+  ret = node->cost;
+  free (node);
+
+  return ret;
+}
+
+
+#define COALESCE_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1))
+
+/* Hash function for coalesce list.  Calculate hash for PAIR.   */
+
+static unsigned int 
+coalesce_pair_map_hash (const void *pair)
+{
+  hashval_t a = (hashval_t)(((coalesce_pair_p)pair)->first_element);
+  hashval_t b = (hashval_t)(((coalesce_pair_p)pair)->second_element);
+
+  return COALESCE_HASH_FN (a,b);
+}
+
+
+/* Equality function for coalesce list hash table.  Compare PAIR1 and PAIR2,
+   returning TRUE if the two pairs are equivilent. */
+
+static int 
+coalesce_pair_map_eq (const void *pair1, const void *pair2)
+{
+  coalesce_pair_p p1 = (coalesce_pair_p) pair1;
+  coalesce_pair_p p2 = (coalesce_pair_p) pair2;
+
+  return (p1->first_element == p2->first_element
+	  && p1->second_element == p2->second_element);
+}
+
+
+/* Create a new empty coalesce list object and return it.  */
+
+static inline coalesce_list_p 
+create_coalesce_list (void)
+{
+  coalesce_list_p list;
+  unsigned size = num_ssa_names * 3;
+
+  if (size < 40) 
+    size = 40;
+
+  list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d));
+  list->list = htab_create (size, coalesce_pair_map_hash,
+  			    coalesce_pair_map_eq, NULL);
+  list->sorted = NULL;
+  list->num_sorted = 0;
+  list->cost_one_list = NULL;
+  return list;
+}
+
+
+/* Delete coalesce list CL.  */
+
+static inline void 
+delete_coalesce_list (coalesce_list_p cl)
+{
+  gcc_assert (cl->cost_one_list == NULL);
+  htab_delete (cl->list);
+  if (cl->sorted)
+    free (cl->sorted);
+  gcc_assert (cl->num_sorted == 0);
+  free (cl);
+}
+
+
+/* Find a matching coalesce pair object in CL for the pair P1 and P2.  If 
+   one isn't found, return NULL if CREATE is false, otherwise create a new 
+   coalesce pair object and return it.  */
+
+static coalesce_pair_p
+find_coalesce_pair (coalesce_list_p cl, int p1, int p2, bool create)
+{
+  struct coalesce_pair p, *pair;
+  void **slot;
+  unsigned int hash;
+    
+  /* Normalize so that p1 is the smaller value.  */
+  if (p2 < p1)
+    {
+      p.first_element = p2;
+      p.second_element = p1;
+    }
+  else
+    {
+      p.first_element = p1;
+      p.second_element = p2;
+    }
+  
+  
+  hash = coalesce_pair_map_hash (&p);
+  pair = (struct coalesce_pair *) htab_find_with_hash (cl->list, &p, hash);
+
+  if (create && !pair)
+    {
+      gcc_assert (cl->sorted == NULL);
+      pair = xmalloc (sizeof (struct coalesce_pair));
+      pair->first_element = p.first_element;
+      pair->second_element = p.second_element;
+      pair->cost = 0;
+      slot = htab_find_slot_with_hash (cl->list, pair, hash, INSERT);
+      *(struct coalesce_pair **)slot = pair;
+    }
+
+  return pair;
+}
+
+static inline void
+add_cost_one_coalesce (coalesce_list_p cl, int p1, int p2)
+{
+  cost_one_pair_p pair;
+
+  pair = xmalloc (sizeof (struct cost_one_pair_d));
+  pair->first_element = p1;
+  pair->second_element = p2;
+  pair->next = cl->cost_one_list;
+  cl->cost_one_list = pair;
+}
+
+
+/* Add a coalesce between P1 and P2 in list CL with a cost of VALUE.  */
+
+static inline void 
+add_coalesce (coalesce_list_p cl, int p1, int p2,
+	      int value)
+{
+  coalesce_pair_p node;
+
+  gcc_assert (cl->sorted == NULL);
+  if (p1 == p2)
+    return;
+
+  node = find_coalesce_pair (cl, p1, p2, true);
+
+  /* Once the value is MUST_COALESCE_COST, leave it that way.  */
+  if (node->cost != MUST_COALESCE_COST)
+    {
+      if (value == MUST_COALESCE_COST)
+	node->cost = value;
+      else
+	node->cost += value;
+    }
+}
+
+
+/* Comparison function to allow qsort to sort P1 and P2 in Ascendiong order.  */
+
+static int 
+compare_pairs (const void *p1, const void *p2)
+{
+  return (*(coalesce_pair_p *)p1)->cost - (*(coalesce_pair_p *)p2)->cost;
+}
+
+
+/* Return the number of unique coalesce pairs in CL.  */
+
+static inline int
+num_coalesce_pairs (coalesce_list_p cl)
+{
+  return htab_elements (cl->list);
+}
+
+
+/* Iterator over hash table pairs.  */
+typedef struct
+{
+  htab_iterator hti;
+} coalesce_pair_iterator;
+
+
+/* Return first partition pair from list CL, initializing iterator ITER.  */
+
+static inline coalesce_pair_p
+first_coalesce_pair (coalesce_list_p cl, coalesce_pair_iterator *iter)
+{
+  coalesce_pair_p pair;
+
+  pair = (coalesce_pair_p) first_htab_element (&(iter->hti), cl->list);
+  return pair;
+}
+
+
+/* Return TRUE if there are no more partitions in for ITER to process.  */
+
+static inline bool
+end_coalesce_pair_p (coalesce_pair_iterator *iter)
+{
+  return end_htab_p (&(iter->hti));
+}
+
+
+/* Return the next parttition pair to be visited by ITER.  */
+
+static inline coalesce_pair_p
+next_coalesce_pair (coalesce_pair_iterator *iter)
+{
+  coalesce_pair_p pair;
+
+  pair = (coalesce_pair_p) next_htab_element (&(iter->hti));
+  return pair;
+}
+
+
+/* Iterate over CL using ITER, returning values in PAIR.  */
+
+#define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL)		\
+  for ((PAIR) = first_coalesce_pair ((CL), &(ITER));	\
+       !end_coalesce_pair_p (&(ITER));			\
+       (PAIR) = next_coalesce_pair (&(ITER)))
+
+
+/* Prepare CL for removal of preferred pairs.  When finished they are sorted
+   in order from most important coalesce to least important.  */
+
+static void
+sort_coalesce_list (coalesce_list_p cl)
+{
+  unsigned x, num;
+  coalesce_pair_p p;
+  coalesce_pair_iterator ppi;
+
+  gcc_assert (cl->sorted == NULL);
+
+  num = num_coalesce_pairs (cl);
+  cl->num_sorted = num;
+  if (num == 0)
+    return;
+
+  /* Allocate a vector for the pair pointers.  */
+  cl->sorted = XNEWVEC (coalesce_pair_p, num);
+
+  /* Populate the vector with pointers to the pairs.  */
+  x = 0;
+  FOR_EACH_PARTITION_PAIR (p, ppi, cl)
+    cl->sorted[x++] = p;
+  gcc_assert (x == num);
+
+  /* Already sorted.  */
+  if (num == 1)
+    return;
+
+  /* If there are only 2, just pick swap them if the order isn't correct.  */
+  if (num == 2)
+    {
+      if (cl->sorted[0]->cost > cl->sorted[1]->cost)
+        {
+	  p = cl->sorted[0];
+	  cl->sorted[0] = cl->sorted[1];
+	  cl->sorted[1] = p;
+	}
+      return;
+    }
+
+  /* Only call qsort if there are more than 2 items.  */
+  if (num > 2)
+      qsort (cl->sorted, num, sizeof (coalesce_pair_p), compare_pairs);
+}
+
+
+/* Send debug info for coalesce list CL to file F.  */
+
+static void 
+dump_coalesce_list (FILE *f, coalesce_list_p cl)
+{
+  coalesce_pair_p node;
+  coalesce_pair_iterator ppi;
+  int x;
+  tree var;
+
+  if (cl->sorted == NULL)
+    {
+      fprintf (f, "Coalesce List:\n");
+      FOR_EACH_PARTITION_PAIR (node, ppi, cl)
+        {
+	  tree var1 = ssa_name (node->first_element);
+	  tree var2 = ssa_name (node->second_element);
+	  print_generic_expr (f, var1, TDF_SLIM);
+	  fprintf (f, " <-> ");
+	  print_generic_expr (f, var2, TDF_SLIM);
+	  fprintf (f, "  (%1d), ", node->cost);
+	  fprintf (f, "\n");
+	}
+    }
+  else
+    {
+      fprintf (f, "Sorted Coalesce list:\n");
+      for (x = cl->num_sorted - 1 ; x >=0; x--)
+        {
+	  node = cl->sorted[x];
+	  fprintf (f, "(%d) ", node->cost);
+	  var = ssa_name (node->first_element);
+	  print_generic_expr (f, var, TDF_SLIM);
+	  fprintf (f, " <-> ");
+	  var = ssa_name (node->second_element);
+	  print_generic_expr (f, var, TDF_SLIM);
+	  fprintf (f, "\n");
+	}
+    }
+}
+
+
+/* This represents a conflict graph.  Implemented as an array of bitmaps.  
+   A full matrix isused for conflicts rather than just upper triangular form.
+   this make sit much simpler and faster to perform conflict merges.  */
+
+typedef struct ssa_conflicts_d
+{
+  unsigned size;
+  bitmap *conflicts;
+} * ssa_conflicts_p;
+
+
+/* Return a empty new conflict graph for SIZE elements.  */
+
+static inline ssa_conflicts_p
+ssa_conflicts_new (unsigned size)
+{
+  ssa_conflicts_p ptr;
+
+  ptr = XNEW (struct ssa_conflicts_d);
+  ptr->conflicts = XCNEWVEC (bitmap, size);
+  ptr->size = size;
+  return ptr;
+}
+
+
+/* Free storage for conflict graph PTR.  */
+
+static inline void
+ssa_conflicts_delete (ssa_conflicts_p ptr)
+{
+  unsigned x;
+  for (x = 0; x < ptr->size; x++)
+    if (ptr->conflicts[x])
+      BITMAP_FREE (ptr->conflicts[x]);
+
+  free (ptr->conflicts);
+  free (ptr);
+}
+
+
+/* Test if elements X and Y conflict in graph PTR.  */
+
+static inline bool
+ssa_conflicts_test_p (ssa_conflicts_p ptr, unsigned x, unsigned y)
+{
+  bitmap b;
+
+#ifdef ENABLE_CHECKING
+  gcc_assert (x < ptr->size);
+  gcc_assert (y < ptr->size);
+  gcc_assert (x != y);
+#endif
+
+  b = ptr->conflicts[x];
+  if (b)
+    /* Avoid the lookup if Y has no conflicts.  */
+    return ptr->conflicts[y] ? bitmap_bit_p (b, y) : false;
+  else
+    return false;
+}
+
+
+/* Add a conflict with Y to the bitmap for X in graph PTR.  */
+
+static inline void
+ssa_conflicts_add_one (ssa_conflicts_p ptr, unsigned x, unsigned y)
+{
+  /* If there are no conflicts yet, allocate the bitmap and set bit.  */
+  if (!ptr->conflicts[x])
+    ptr->conflicts[x] = BITMAP_ALLOC (NULL);
+  bitmap_set_bit (ptr->conflicts[x], y);
+}
+
+
+/* Add conflicts between X and Y in graph PTR.  */
+
+static inline void
+ssa_conflicts_add (ssa_conflicts_p ptr, unsigned x, unsigned y)
+{
+#ifdef ENABLE_CHECKING
+  gcc_assert (x < ptr->size);
+  gcc_assert (y < ptr->size);
+  gcc_assert (x != y);
+#endif
+  ssa_conflicts_add_one (ptr, x, y);
+  ssa_conflicts_add_one (ptr, y, x);
+}
+
+
+/* Merge all Y's conflict into X in graph PTR.  */
+
+static inline void
+ssa_conflicts_merge (ssa_conflicts_p ptr, unsigned x, unsigned y)
+{
+  unsigned z;
+  bitmap_iterator bi;
+
+  gcc_assert (x != y);
+  if (!(ptr->conflicts[y]))
+    return;
+
+  /* Add a conflict between X and every one Y has.  If the bitmap doesn't
+     exist, then it has already been coalesced, and we dont need to add a 
+     conflict.  */
+  EXECUTE_IF_SET_IN_BITMAP (ptr->conflicts[y], 0, z, bi)
+    if (ptr->conflicts[z])
+      bitmap_set_bit (ptr->conflicts[z], x);
+
+  if (ptr->conflicts[x])
+    {
+      /* If X has conflicts, add Y's to X.  */
+      bitmap_ior_into (ptr->conflicts[x], ptr->conflicts[y]);
+      BITMAP_FREE (ptr->conflicts[y]);
+    }
+  else
+    {
+      /* If X has no conflicts, simply use Y's.  */
+      ptr->conflicts[x] = ptr->conflicts[y];
+      ptr->conflicts[y] = NULL;
+    }
+}
+
+
+/* This structure is used to efficiently record the current status of live 
+   SSA_NAMES when building a conflict graph.  
+   LIVE_BASE_VAR has a bit set for each base variable which has at least one
+   ssa version live.
+   LIVE_BASE_PARTITIONS is an array of bitmaps using the basevar table as an 
+   index, and is used to track what partitions of each base variable are 
+   live.  This makes it easy to add conflicts between just live partitions 
+   with the same base variable.  
+   The values in LIVE_BASE_PARTITIONS are only valid if the base variable is 
+   marked as being live.  This delays clearing of these bitmaps until
+   they are actually needed again.  */
+
+typedef struct live_track_d
+{
+  bitmap live_base_var;		/* Indicates if a basevar is live.  */
+  bitmap *live_base_partitions;	/* Live partitions for each basevar.  */
+  var_map map;			/* Var_map being used for partition mapping.  */
+} * live_track_p;
+
+
+/* This routine will create a new live track structure based on the partitions
+   in MAP.  */
+
+static live_track_p
+new_live_track (var_map map)
+{
+  live_track_p ptr;
+  int lim, x;
+
+  /* Make sure there is a partition view in place.  */
+  gcc_assert (map->partition_to_base_index != NULL);
+
+  ptr = (live_track_p) xmalloc (sizeof (struct live_track_d));
+  ptr->map = map;
+  lim = num_basevars (map);
+  ptr->live_base_partitions = (bitmap *) xmalloc(sizeof (bitmap *) * lim);
+  ptr->live_base_var = BITMAP_ALLOC (NULL);
+  for (x = 0; x < lim; x++)
+    ptr->live_base_partitions[x] = BITMAP_ALLOC (NULL);
+  return ptr;
+}
+
+
+/* This routine will free the memory associated with PTR.  */
+
+static void
+delete_live_track (live_track_p ptr)
+{
+  int x, lim;
+
+  lim = num_basevars (ptr->map);
+  for (x = 0; x < lim; x++)
+    BITMAP_FREE (ptr->live_base_partitions[x]);
+  BITMAP_FREE (ptr->live_base_var);
+  free (ptr->live_base_partitions);
+  free (ptr);
+}
+
+
+/* This function will remove PARTITION from the live list in PTR.  */
+
+static inline void
+live_track_remove_partition (live_track_p ptr, int partition)
+{
+  int root;
+
+  root = basevar_index (ptr->map, partition);
+  bitmap_clear_bit (ptr->live_base_partitions[root], partition);
+  /* If the element list is empty, make the base variable not live either.  */
+  if (bitmap_empty_p (ptr->live_base_partitions[root]))
+    bitmap_clear_bit (ptr->live_base_var, root);
+}
+
+
+/* This function will adds PARTITION to the live list in PTR.  */
+
+static inline void
+live_track_add_partition (live_track_p ptr, int partition)
+{
+  int root;
+
+  root = basevar_index (ptr->map, partition);
+  /* If this base var wasn't live before, it is now.  Clear the element list 
+     since it was delayed until needed.  */
+  if (!bitmap_bit_p (ptr->live_base_var, root))
+    {
+      bitmap_set_bit (ptr->live_base_var, root);
+      bitmap_clear (ptr->live_base_partitions[root]);
+    }
+  bitmap_set_bit (ptr->live_base_partitions[root], partition);
+    
+}
+
+
+/* Clear the live bit for VAR in PTR.  */
+
+static inline void
+live_track_clear_var (live_track_p ptr, tree var)
+{
+  int p;
+
+  p = var_to_partition (ptr->map, var);
+  if (p != NO_PARTITION)
+    live_track_remove_partition (ptr, p);
+}
+
+
+/* Return TRUE if VAR is live in PTR.  */
+
+static inline bool
+live_track_live_p (live_track_p ptr, tree var)
+{
+  int p, root;
+
+  p = var_to_partition (ptr->map, var);
+  if (p != NO_PARTITION)
+    {
+      root = basevar_index (ptr->map, p);
+      if (bitmap_bit_p (ptr->live_base_var, root))
+	return bitmap_bit_p (ptr->live_base_partitions[root], p);
+    }
+  return false;
+}
+
+
+/* This routine will add USE to PTR.  USE will be marked as live in both the 
+   ssa live map and the live bitmap for the root of USE.  */
+
+static inline void
+live_track_process_use (live_track_p ptr, tree use)
+{
+  int p;
+
+  p = var_to_partition (ptr->map, use);
+  if (p == NO_PARTITION)
+    return;
+
+  /* Mark as live in the appropriate live list.  */
+  live_track_add_partition (ptr, p);
+}
+
+
+/* This routine will process a DEF in PTR.  DEF will be removed from the live
+   lists, and if there are any other live partitions with the same base 
+   variable, conflicts will be added to GRAPH.  */
+
+static inline void
+live_track_process_def (live_track_p ptr, tree def, ssa_conflicts_p graph)
+{
+  int p, root;
+  bitmap b;
+  unsigned x;
+  bitmap_iterator bi;
+
+  p = var_to_partition (ptr->map, def);
+  if (p == NO_PARTITION)
+    return;
+
+  /* Clear the liveness bit.  */
+  live_track_remove_partition (ptr, p);
+
+  /* If the bitmap isn't empty now, conflicts need to be added.  */
+  root = basevar_index (ptr->map, p);
+  if (bitmap_bit_p (ptr->live_base_var, root))
+    {
+      b = ptr->live_base_partitions[root];
+      EXECUTE_IF_SET_IN_BITMAP (b, 0, x, bi)
+        ssa_conflicts_add (graph, p, x);
+    }
+}
+
+
+/* Initialize PTR with the partitions set in INIT.  */
+
+static inline void
+live_track_init (live_track_p ptr, bitmap init)
+{
+  unsigned p;
+  bitmap_iterator bi;
+
+  /* Mark all live on exit partitions.  */
+  EXECUTE_IF_SET_IN_BITMAP (init, 0, p, bi)
+    live_track_add_partition (ptr, p);
+}
+
+
+/* This routine will clear all live partitions in PTR.   */
+
+static inline void
+live_track_clear_base_vars (live_track_p ptr)
+{
+  /* Simply clear the live base list.  Anything marked as live in the element
+     lists will be cleared later if/when the base variable ever comes alive
+     again.  */
+  bitmap_clear (ptr->live_base_var);
+}
+
+
+/* Build a conflict graph based on LIVEINFO.  Any partitions which are in the
+   partition view of the var_map liveinfo is based on get entires in the 
+   conflict graph.  Only conflicts between ssa_name partitions with the same 
+   base variableare added.  */
+
+static ssa_conflicts_p
+build_ssa_conflict_graph (tree_live_info_p liveinfo)
+{
+  ssa_conflicts_p graph;
+  var_map map;
+  basic_block bb;
+  ssa_op_iter iter;
+  live_track_p live;
+
+  map = live_var_map (liveinfo);
+  graph = ssa_conflicts_new (num_var_partitions (map));
+
+  live = new_live_track (map);
+
+  FOR_EACH_BB (bb)
+    {
+      block_stmt_iterator bsi;
+      tree phi;
+
+      /* Start with live on exit temporaries.  */
+      live_track_init (live, live_on_exit (liveinfo, bb));
+
+      for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
+        {
+	  tree var;
+	  tree stmt = bsi_stmt (bsi);
+
+	  /* A copy between 2 partitions does not introduce an interference 
+	     by itself.  If they did, you would never be able to coalesce 
+	     two things which are copied.  If the two variables really do 
+	     conflict, they will conflict elsewhere in the program.  
+	     
+	     This is handled by simply removing the SRC of the copy from the 
+	     live list, and processing the stmt normally.  */
+	  if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
+	    {
+	      tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
+	      tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
+	      if (TREE_CODE (lhs) == SSA_NAME && TREE_CODE (rhs) == SSA_NAME)
+		live_track_clear_var (live, rhs);
+	    }
+
+	  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
+	    live_track_process_def (live, var, graph);
+
+	  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
+	    live_track_process_use (live, var);
+	}
+
+      /* If result of a PHI is unused, looping over the statements will not 
+	 record any conflicts since the def was never live.  Since the PHI node
+	 is going to be translated out of SSA form, it will insert a copy.
+	 There must be a conflict recorded between the result of the PHI and 
+	 any variables that are live.  Otherwise the out-of-ssa translation 
+	 may create incorrect code.  */
+      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+	{
+	  tree result = PHI_RESULT (phi);
+	  if (live_track_live_p (live, result))
+	    live_track_process_def (live, result, graph);
+	}
+
+     live_track_clear_base_vars (live);
+    }
+
+  delete_live_track (live);
+  return graph;
+}
+
+
+/* Shortcut routine to print messages to file F of the form:
+   "STR1 EXPR1 STR2 EXPR2 STR3."  */
+
+static inline void
+print_exprs (FILE *f, const char *str1, tree expr1, const char *str2,
+	     tree expr2, const char *str3)
+{
+  fprintf (f, "%s", str1);
+  print_generic_expr (f, expr1, TDF_SLIM);
+  fprintf (f, "%s", str2);
+  print_generic_expr (f, expr2, TDF_SLIM);
+  fprintf (f, "%s", str3);
+}
+
+
+/* Called if a coalesce across and abnormal edge cannot be performed.  PHI is
+   the phi node at fault, I is the argument index at fault.  A message is 
+   printed and compilation is then terminated.  */
+
+static inline void
+abnormal_corrupt (tree phi, int i)
+{
+  edge e = PHI_ARG_EDGE (phi, i);
+  tree res = PHI_RESULT (phi);
+  tree arg = PHI_ARG_DEF (phi, i);
+
+  fprintf (stderr, " Corrupt SSA across abnormal edge BB%d->BB%d\n",
+	   e->src->index, e->dest->index);
+  fprintf (stderr, "Argument %d (", i);
+  print_generic_expr (stderr, arg, TDF_SLIM);
+  if (TREE_CODE (arg) != SSA_NAME)
+    fprintf (stderr, ") is not an SSA_NAME.\n");
+  else
+    {
+      gcc_assert (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg));
+      fprintf (stderr, ") does not have the same base variable as the result ");
+      print_generic_stmt (stderr, res, TDF_SLIM);
+    }
+
+  internal_error ("SSA corruption");
+}
+
+
+/* Print a failure to coalesce a MUST_COALESCE pair X and Y.  */
+
+static inline void
+fail_abnormal_edge_coalesce (int x, int y)
+{
+  fprintf (stderr, "\nUnable to coalesce ssa_names %d  and %d ",x, y);
+  fprintf (stderr, " which are marked as MUST COALESCE.\n");
+  print_generic_expr (stderr, ssa_name (x), TDF_SLIM);
+  fprintf (stderr, " and  ");
+  print_generic_stmt (stderr, ssa_name (y), TDF_SLIM);
+
+  internal_error ("SSA corruption");
+}
+
+
+/* This function creates a var_map for the current function as well as creating
+   a coalesce list for use later in the out of ssa process.  */
+
+static var_map
+create_outofssa_var_map (coalesce_list_p cl, bitmap used_in_copy)
+{
+  block_stmt_iterator bsi;
+  basic_block bb;
+  tree var;
+  tree stmt;
+  tree first;
+  var_map map;
+  ssa_op_iter iter;
+  int v1, v2, cost;
+  unsigned i;
+
+#ifdef ENABLE_CHECKING
+  bitmap used_in_real_ops;
+  bitmap used_in_virtual_ops;
+
+  used_in_real_ops = BITMAP_ALLOC (NULL);
+  used_in_virtual_ops = BITMAP_ALLOC (NULL);
+#endif
+
+  map = init_var_map (num_ssa_names + 1);
+
+  FOR_EACH_BB (bb)
+    {
+      tree phi, arg;
+
+      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+	{
+	  int i;
+	  int ver;
+	  tree res;
+	  bool saw_copy = false;
+
+	  res = PHI_RESULT (phi);
+	  ver = SSA_NAME_VERSION (res);
+	  register_ssa_partition (map, res);
+
+	  /* Register ssa_names and coalesces between the args and the result 
+	     of all PHI.  */
+	  for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+	    {
+	      edge e = PHI_ARG_EDGE (phi, i);
+	      arg = PHI_ARG_DEF (phi, i);
+	      if (TREE_CODE (arg) == SSA_NAME)
+		register_ssa_partition (map, arg);
+	      if (TREE_CODE (arg) == SSA_NAME 
+		  && SSA_NAME_VAR (arg) == SSA_NAME_VAR (res))
+	        {
+		  saw_copy = true;
+		  bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (arg));
+		  if ((e->flags & EDGE_ABNORMAL) == 0)
+		    {
+		      int cost = coalesce_cost_edge (e);
+		      if (cost == 1 && single_imm_use_p (arg))
+		        add_cost_one_coalesce (cl, ver, SSA_NAME_VERSION (arg));
+		      else
+			add_coalesce (cl, ver, SSA_NAME_VERSION (arg), cost);
+		    }
+		}
+	      else
+	        if (e->flags & EDGE_ABNORMAL)
+		  abnormal_corrupt (phi, i);
+	    }
+	  if (saw_copy)
+	    bitmap_set_bit (used_in_copy, ver);
+	}
+
+      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+        {
+	  stmt = bsi_stmt (bsi);
+
+	  /* Register USE and DEF operands in each statement.  */
+	  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE))
+	    register_ssa_partition (map, var);
+
+	  /* Check for copy coalesces.  */
+	  switch (TREE_CODE (stmt))
+	    {
+	    case GIMPLE_MODIFY_STMT:
+	      {
+		tree op1 = GIMPLE_STMT_OPERAND (stmt, 0);
+		tree op2 = GIMPLE_STMT_OPERAND (stmt, 1);
+		if (TREE_CODE (op1) == SSA_NAME 
+		    && TREE_CODE (op2) == SSA_NAME
+		    && SSA_NAME_VAR (op1) == SSA_NAME_VAR (op2))
+		  {
+		    v1 = SSA_NAME_VERSION (op1);
+		    v2 = SSA_NAME_VERSION (op2);
+		    cost = coalesce_cost_bb (bb);
+		    add_coalesce (cl, v1, v2, cost);
+		    bitmap_set_bit (used_in_copy, v1);
+		    bitmap_set_bit (used_in_copy, v2);
+		  }
+	      }
+	      break;
+
+	    case ASM_EXPR:
+	      {
+		unsigned long noutputs, i;
+		tree *outputs, link;
+		noutputs = list_length (ASM_OUTPUTS (stmt));
+		outputs = (tree *) alloca (noutputs * sizeof (tree));
+		for (i = 0, link = ASM_OUTPUTS (stmt); link;
+		     ++i, link = TREE_CHAIN (link))
+		  outputs[i] = TREE_VALUE (link);
+
+		for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link))
+		  {
+		    const char *constraint
+		      = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
+		    tree input = TREE_VALUE (link);
+		    char *end;
+		    unsigned long match;
+
+		    if (TREE_CODE (input) != SSA_NAME && !DECL_P (input))
+		      continue;
+
+		    match = strtoul (constraint, &end, 10);
+		    if (match >= noutputs || end == constraint)
+		      continue;
+
+		    if (TREE_CODE (outputs[match]) != SSA_NAME)
+		      continue;
+
+		    v1 = SSA_NAME_VERSION (outputs[match]);
+		    v2 = SSA_NAME_VERSION (input);
+
+		    if (SSA_NAME_VAR (outputs[match]) == SSA_NAME_VAR (input))
+		      {
+			cost = coalesce_cost (REG_BR_PROB_BASE, 
+					      maybe_hot_bb_p (bb),
+					      false);
+			add_coalesce (cl, v1, v2, cost);
+			bitmap_set_bit (used_in_copy, v1);
+			bitmap_set_bit (used_in_copy, v2);
+		      }
+		  }
+		break;
+	      }
+
+	    default:
+	      break;
+	    }
+	    
+#ifdef ENABLE_CHECKING
+	  /* Mark real uses and defs.  */
+	  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE))
+	    bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (var)));
+
+	  /* Validate that virtual ops don't get used in funny ways.  */
+	  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, 
+				     SSA_OP_VIRTUAL_USES | SSA_OP_VMUSTDEF)
+	    {
+	      bitmap_set_bit (used_in_virtual_ops, 
+			      DECL_UID (SSA_NAME_VAR (var)));
+	    }
+
+#endif /* ENABLE_CHECKING */
+	}
+    }
+
+  /* Now process result decls and live on entry variables for entry into
+     the coalesce list.  */
+  first = NULL_TREE;
+  for (i = 1; i < num_ssa_names; i++)
+    {
+      var = map->partition_to_var[i];
+      if (var != NULL_TREE)
+        {
+	  /* Add coalesces between all the result decls.  */
+	  if (TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL)
+	    {
+	      if (first == NULL_TREE)
+		first = var;
+	      else
+		{
+		  gcc_assert (SSA_NAME_VAR (var) == SSA_NAME_VAR (first));
+		  v1 = SSA_NAME_VERSION (first);
+		  v2 = SSA_NAME_VERSION (var);
+		  bitmap_set_bit (used_in_copy, v1);
+		  bitmap_set_bit (used_in_copy, v2);
+		  cost = coalesce_cost_bb (EXIT_BLOCK_PTR);
+		  add_coalesce (cl, v1, v2, cost);
+		}
+	    }
+	  /* Mark any default_def variables as being in the coalesce list
+	     since they will have to be coalesced with the base variable.  If
+	     not marked as present, they won't be in the coalesce view. */
+	  if (gimple_default_def (cfun, SSA_NAME_VAR (var)) == var)
+	    bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
+	}
+    }
+
+#if defined ENABLE_CHECKING
+  {
+    unsigned i;
+    bitmap both = BITMAP_ALLOC (NULL);
+    bitmap_and (both, used_in_real_ops, used_in_virtual_ops);
+    if (!bitmap_empty_p (both))
+      {
+	bitmap_iterator bi;
+
+	EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi)
+	  fprintf (stderr, "Variable %s used in real and virtual operands\n",
+		   get_name (referenced_var (i)));
+	internal_error ("SSA corruption");
+      }
+
+    BITMAP_FREE (used_in_real_ops);
+    BITMAP_FREE (used_in_virtual_ops);
+    BITMAP_FREE (both);
+  }
+#endif
+
+  return map;
+}
+
+
+/* Attempt to coalesce ssa verisons X and Y together using the partition
+   mapping in MAP and checking conflicts in GRAPH.  Output any debug info to
+   DEBUG, if it is nun-NULL.  */
+
+static inline bool
+attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y,
+		  FILE *debug)
+{
+  int z;
+  tree var1, var2;
+  int p1, p2;
+
+  p1 = var_to_partition (map, ssa_name (x));
+  p2 = var_to_partition (map, ssa_name (y));
+
+  if (debug)
+    {
+      fprintf (debug, "(%d)", x);
+      print_generic_expr (debug, partition_to_var (map, p1), TDF_SLIM);
+      fprintf (debug, " & (%d)", y);
+      print_generic_expr (debug, partition_to_var (map, p2), TDF_SLIM);
+    }
+
+  if (p1 == p2) 
+    {
+      if (debug)
+	fprintf (debug, ": Already Coalesced.\n");
+      return true;
+    }
+
+  if (debug)
+    fprintf (debug, " [map: %d, %d] ", p1, p2);
+
+
+  if (!ssa_conflicts_test_p (graph, p1, p2))
+    {
+      var1 = partition_to_var (map, p1);
+      var2 = partition_to_var (map, p2);
+      z = var_union (map, var1, var2);
+      if (z == NO_PARTITION)
+	{
+	  if (debug)
+	    fprintf (debug, ": Unable to perform partition union.\n");
+	  return false;
+	}
+
+      /* z is the new combined partition.  Remove the other partition from 
+	 the list, and merge the conflicts.  */
+      if (z == p1)
+	ssa_conflicts_merge (graph, p1, p2);
+      else
+	ssa_conflicts_merge (graph, p2, p1);
+
+      if (debug)
+	fprintf (debug, ": Success -> %d\n", z);
+      return true;
+    }
+
+  if (debug)
+    fprintf (debug, ": Fail due to conflict\n");
+
+  return false;
+}
+
+
+/* Attempt to Coalesce partitions in MAP which occur in the list CL using 
+   GRAPH.  Debug output is sent to DEBUG if it is non-NULL.  */
+
+static void
+coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl, 
+		     FILE *debug)
+{
+  int x = 0, y = 0;
+  tree var1, var2, phi;
+  int cost;
+  basic_block bb;
+  edge e;
+  edge_iterator ei;
+
+  /* First, coalece all the copie across abnormal edges.  These are not placed
+     in the coalesce list becase they do not need to be sorted, and simply 
+     consume extra memory/compilation time in large programs.  */
+
+  FOR_EACH_BB (bb)
+    {
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	if (e->flags & EDGE_ABNORMAL)
+	  {
+	    for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+	      {
+		tree res = PHI_RESULT (phi);
+	        tree arg = PHI_ARG_DEF (phi, e->dest_idx);
+		int v1 = SSA_NAME_VERSION (res);
+		int v2 = SSA_NAME_VERSION (arg);
+
+		if (SSA_NAME_VAR (arg) != SSA_NAME_VAR (res))
+		  abnormal_corrupt (phi, e->dest_idx);
+
+		if (debug)
+		  fprintf (debug, "Abnormal coalesce: ");
+
+		if (!attempt_coalesce (map, graph, v1, v2, debug))
+		  fail_abnormal_edge_coalesce (v1, v2);
+	      }
+	  }
+    }
+
+  /* Now process the items in the coalesce list.  */
+
+  while ((cost = pop_best_coalesce (cl, &x, &y)) != NO_BEST_COALESCE)
+    {
+      var1 = ssa_name (x);
+      var2 = ssa_name (y);
+
+      /* Assert the coalesces have the same base variable.  */
+      gcc_assert (SSA_NAME_VAR (var1) == SSA_NAME_VAR (var2));
+
+      if (debug)
+	fprintf (debug, "Coalesce list: ");
+      attempt_coalesce (map, graph, x, y, debug);
+    }
+}
+
+
+/* Reduce the number of copies by coalescing variables in the function.  Return
+   a partition map with the resulting coalesces.  */
+
+extern var_map
+coalesce_ssa_name (void)
+{
+  unsigned num, x;
+  tree_live_info_p liveinfo;
+  ssa_conflicts_p graph;
+  coalesce_list_p cl;
+  bitmap used_in_copies = BITMAP_ALLOC (NULL);
+  var_map map;
+
+  cl = create_coalesce_list ();
+  map = create_outofssa_var_map (cl, used_in_copies);
+
+  /* Don't calculate live ranges for variables not in the coalesce list.  */
+  partition_view_bitmap (map, used_in_copies, true);
+  BITMAP_FREE (used_in_copies);
+
+  if (num_var_partitions (map) <= 1)
+    {
+      delete_coalesce_list (cl);
+      return map;
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    dump_var_map (dump_file, map);
+
+  liveinfo = calculate_live_ranges (map);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY);
+
+  /* Build a conflict graph.  */
+  graph = build_ssa_conflict_graph (liveinfo);
+  delete_tree_live_info (liveinfo);
+
+  sort_coalesce_list (cl);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "\nAfter sorting:\n");
+      dump_coalesce_list (dump_file, cl);
+    }
+
+  /* First, coalesce all live on entry variables to their base variable. 
+     This will ensure the first use is coming from the correct location.  */
+
+  num = num_var_partitions (map);
+  for (x = 0 ; x < num; x++)
+    {
+      tree var = partition_to_var (map, x);
+      tree root;
+
+      if (TREE_CODE (var) != SSA_NAME)
+	continue;
+
+      root = SSA_NAME_VAR (var);
+      if (gimple_default_def (cfun, root) == var)
+        {
+	  /* This root variable should have not already been assigned
+	     to another partition which is not coalesced with this one.  */
+	  gcc_assert (!var_ann (root)->out_of_ssa_tag);
+
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      print_exprs (dump_file, "Must coalesce ", var,
+			   " with the root variable ", root, ".\n");
+	    }
+	  change_partition_var (map, root, x);
+	}
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    dump_var_map (dump_file, map);
+
+  /* Now coalesce everything in the list.  */
+  coalesce_partitions (map, graph, cl, 
+		       ((dump_flags & TDF_DETAILS) ? dump_file
+						   : NULL));
+
+  delete_coalesce_list (cl);
+  ssa_conflicts_delete (graph);
+
+  return map;
+}
+