[PATCH] Improve PR63155, SSA coalescing conflict merging

[Richard Biener]

A non-trivial amount of time is spent in ssa_conflicts_merge,
in particular the

  /* Add a conflict between X and every one Y has.  If the bitmap doesn't
     exist, then it has already been coalesced, and we don't need to add a
     conflict.  */
  EXECUTE_IF_SET_IN_BITMAP (by, 0, z, bi)
    {
      bitmap bz = ptr->conflicts[z];
      if (bz)
        bitmap_set_bit (bz, x);
    }

loop because it is cache unfriendly.  The observation is that while
it adds a conflict to X where a conflict to Y existed it doesn't
actually remove the no longer needed conflict to Y.

Doing that, while more work, improves compile-time on the 2nd
testcase in the PR from 46s to 22s (leaving memory use alone).
The first testcase improves from 108s to 39s (leaving memory use alone).
Memory use is still a big issue for both testcases.

The explanation is possibly that when doing a lot of coalescing into
some variable the above walks get longer and longer because we add
more conflicts overall.

Bootstrap & regtest running on x86_64-unknown-linux-gnu.

Richard.

2018-09-13  Richard Biener  <rguenther@suse.de>

	PR middle-end/63155
	* tree-ssa-coalesce.c (ssa_conflicts_merge): Remove conflict
	bits for the merged partition.

Index: gcc/tree-ssa-coalesce.c
===================================================================
--- gcc/tree-ssa-coalesce.c	(revision 264259)
+++ gcc/tree-ssa-coalesce.c	(working copy)
@@ -620,7 +620,11 @@ ssa_conflicts_merge (ssa_conflicts *ptr,
     {
       bitmap bz = ptr->conflicts[z];
       if (bz)
-	bitmap_set_bit (bz, x);
+	{
+	  bool was_there = bitmap_clear_bit (bz, y);
+	  gcc_checking_assert (was_there);
+	  bitmap_set_bit (bz, x);
+	}
     }
 
   if (bx)