re PR tree-optimization/64058 (Performance degradation after r216304)

	PR tree-optimization/64058
	* tree-ssa-coalesce.c (struct coalesce_pair): Add new field
	CONFLICT_COUNT.
	(struct ssa_conflicts): Move up earlier in the file.
	(conflicts_, var_map_): New static variables.
	(initialize_conflict_count): New function to initialize the
	CONFLICT_COUNT field for each conflict pair.
	(compare_pairs): Lazily initialize the conflict count and use it
	as the first tie-breaker.
	(sort_coalesce_list): Add new arguments conflicts, map.  Initialize
	and wipe conflicts_ and map_ around the call to qsort.  Remove
	special case for 2 coalesce pairs.
	* bitmap.c (bitmap_count_unique_bits): New function.
	(bitmap_count_bits_in_word): New function, extracted from
	bitmap_count_bits.
	(bitmap_count_bits): Use bitmap_count_bits_in_word.
	* bitmap.h (bitmap_count_unique_bits): Declare it.

From-SVN: r234425

1 files changed, 54 insertions, 9 deletions

diff --git a/gcc/bitmap.c b/gcc/bitmap.c
index ac20ae5830f..0c05512b666 100644
--- a/gcc/bitmap.c
+++ b/gcc/bitmap.c
@@ -662,6 +662,26 @@ bitmap_popcount (BITMAP_WORD a)
   return ret;
 }
 #endif
+
+/* Count and return the number of bits set in the bitmap word BITS.  */
+static unsigned long
+bitmap_count_bits_in_word (const BITMAP_WORD *bits)
+{
+  unsigned long count = 0;
+
+  for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
+    {
+#if GCC_VERSION >= 3400
+      /* Note that popcountl matches BITMAP_WORD in type, so the actual size
+	 of BITMAP_WORD is not material.  */
+      count += __builtin_popcountl (bits[ix]);
+#else
+      count += bitmap_popcount (bits[ix]);
+#endif
+    }
+  return count;
+}
+
 /* Count the number of bits set in the bitmap, and return it.  */
 
 unsigned long
@@ -669,19 +689,44 @@ bitmap_count_bits (const_bitmap a)
 {
   unsigned long count = 0;
   const bitmap_element *elt;
-  unsigned ix;
 
   for (elt = a->first; elt; elt = elt->next)
+    count += bitmap_count_bits_in_word (elt->bits);
+
+  return count;
+}
+
+/* Count the number of unique bits set in A and B and return it.  */
+
+unsigned long
+bitmap_count_unique_bits (const_bitmap a, const_bitmap b)
+{
+  unsigned long count = 0;
+  const bitmap_element *elt_a, *elt_b;
+
+  for (elt_a = a->first, elt_b = b->first; elt_a && elt_b; )
     {
-      for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
+      /* If we're at different indices, then count all the bits
+	 in the lower element.  If we're at the same index, then
+	 count the bits in the IOR of the two elements.  */
+      if (elt_a->indx < elt_b->indx)
 	{
-#if GCC_VERSION >= 3400
- 	  /* Note that popcountl matches BITMAP_WORD in type, so the actual size
-	 of BITMAP_WORD is not material.  */
-	  count += __builtin_popcountl (elt->bits[ix]);
-#else
-	  count += bitmap_popcount (elt->bits[ix]);
-#endif
+	  count += bitmap_count_bits_in_word (elt_a->bits);
+	  elt_a = elt_a->next;
+	}
+      else if (elt_b->indx < elt_a->indx)
+	{
+	  count += bitmap_count_bits_in_word (elt_b->bits);
+	  elt_b = elt_b->next;
+	}
+      else
+	{
+	  BITMAP_WORD bits[BITMAP_ELEMENT_WORDS];
+	  for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
+	    bits[ix] = elt_a->bits[ix] | elt_b->bits[ix];
+	  count += bitmap_count_bits_in_word (bits);
+	  elt_a = elt_a->next;
+	  elt_b = elt_b->next;
 	}
     }
   return count;