diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index cc91e84..f28baa2 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,18 @@
+2016-03-10  Jeff Law  <law@redhat.com>
+
+	PR tree-optimization/64058
+	* tree-ssa-coalesce.c (struct coalesce_pair): Add new fields
+	CONFLICT_COUNT and INDEX.
+	(num_coalesce_pairs): Move up earlier in the file.
+	(find_coalesce_pair): Initialize the INDEX field for each pair
+	discovered.
+	(add_conflict_counts): New function to initialize the CONFLICT_COUNT
+	field for each conflict pair.
+	(coalesce_ssa_name): Call it.
+	(compare_pairs): No longer sort on the elements of each pair.
+	Instead break ties with the conflict size and finally the index
+	of the coalesce pair.
+
 2016-03-10  Ulrich Weigand  <Ulrich.Weigand@de.ibm.com>
 
 	PR target/70168
diff --git a/gcc/tree-ssa-coalesce.c b/gcc/tree-ssa-coalesce.c
index 6624e7e..b8a2e0d 100644
--- a/gcc/tree-ssa-coalesce.c
+++ b/gcc/tree-ssa-coalesce.c
@@ -50,6 +50,19 @@ struct coalesce_pair
   int first_element;
   int second_element;
   int cost;
+
+  /* A count of the number of unique partitions this pair would conflict
+     with if coalescing was successful.  This is the secondary sort key,
+     given two pairs with equal costs, we will prefer the pair with a smaller
+     conflict set.
+
+     Note this is not updated and propagated as pairs are coalesced.  */
+  int conflict_count;
+
+  /* The order in which coalescing pairs are discovered is recorded in this
+     field, which is used as the final tie breaker when sorting coalesce
+     pairs.  */
+  int index;
 };
 
 /* Coalesce pair hashtable helpers.  */
@@ -254,6 +267,13 @@ delete_coalesce_list (coalesce_list *cl)
   free (cl);
 }
 
+/* Return the number of unique coalesce pairs in CL.  */
+
+static inline int
+num_coalesce_pairs (coalesce_list *cl)
+{
+  return cl->list->elements ();
+}
 
 /* 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
@@ -290,6 +310,7 @@ find_coalesce_pair (coalesce_list *cl, int p1, int p2, bool create)
       pair->first_element = p.first_element;
       pair->second_element = p.second_element;
       pair->cost = 0;
+      pair->index = num_coalesce_pairs (cl);
       *slot = pair;
     }
 
@@ -343,29 +364,21 @@ compare_pairs (const void *p1, const void *p2)
   int result;
 
   result = (* pp1)->cost - (* pp2)->cost;
-  /* Since qsort does not guarantee stability we use the elements
-     as a secondary key.  This provides us with independence from
-     the host's implementation of the sorting algorithm.  */
+  /* We use the size of the resulting conflict set as the secondary sort key.
+     Given two equal costing coalesce pairs, we want to prefer the pair that
+     has the smaller conflict set.  */
   if (result == 0)
     {
-      result = (* pp2)->first_element - (* pp1)->first_element;
+      result = (*pp2)->conflict_count - (*pp1)->conflict_count;
+      /* And if everything else is equal, then sort based on which
+	 coalesce pair was found first.  */
       if (result == 0)
-	result = (* pp2)->second_element - (* pp1)->second_element;
+	result = (*pp2)->index - (*pp1)->index;
     }
 
   return result;
 }
 
-
-/* Return the number of unique coalesce pairs in CL.  */
-
-static inline int
-num_coalesce_pairs (coalesce_list *cl)
-{
-  return cl->list->elements ();
-}
-
-
 /* Iterate over CL using ITER, returning values in PAIR.  */
 
 #define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL)		\
@@ -578,6 +591,42 @@ ssa_conflicts_merge (ssa_conflicts *ptr, unsigned x, unsigned y)
     }
 }
 
+/* Compute and record how many unique conflicts would exist for the
+   representative partition for each coalesce pair in CL.
+
+   CONFLICTS is the conflict graph and MAP is the current partition view.  */
+
+static void
+add_conflict_counts (ssa_conflicts *conflicts, var_map map, coalesce_list *cl)
+{
+  coalesce_pair *p;
+  coalesce_iterator_type ppi;
+  bitmap tmp = BITMAP_ALLOC (NULL);
+
+  FOR_EACH_PARTITION_PAIR (p, ppi, cl)
+    {
+      int p1 = var_to_partition (map, ssa_name (p->first_element));
+      int p2 = var_to_partition (map, ssa_name (p->second_element));
+
+      /* 4 cases.  If both P1 and P2 have conflicts, then build their
+	 union and count the members.  Else handle the degenerate cases
+	 in the obvious ways.  */
+      if (conflicts->conflicts[p1] && conflicts->conflicts[p2])
+	{
+	  bitmap_ior (tmp, conflicts->conflicts[p1], conflicts->conflicts[p2]);
+	  p->conflict_count = bitmap_count_bits (tmp);
+	  bitmap_clear (tmp);
+	}
+      else if (conflicts->conflicts[p1])
+	p->conflict_count = bitmap_count_bits (conflicts->conflicts[p1]);
+      else if (conflicts->conflicts[p2])
+	p->conflict_count = bitmap_count_bits (conflicts->conflicts[p2]);
+      else
+	p->conflict_count = 0;
+    }
+
+  BITMAP_FREE (tmp);
+}
 
 /* Dump a conflicts graph.  */
 
@@ -1802,6 +1851,7 @@ coalesce_ssa_name (void)
   if (dump_file && (dump_flags & TDF_DETAILS))
     ssa_conflicts_dump (dump_file, graph);
 
+  add_conflict_counts (graph, map, cl);
   sort_coalesce_list (cl);
 
   if (dump_file && (dump_flags & TDF_DETAILS))
