From patchwork Wed Jul  7 13:31:27 2010
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: IRA improvements 2/4
From: Vladimir Makarov <vmakarov@redhat.com>
X-Patchwork-Id: 58119
Message-Id: <4C3481AF.10503@redhat.com>
To: gcc-patches <gcc-patches@gcc.gnu.org>
Cc: Jeffrey Law <law@redhat.com>
Date: Wed, 07 Jul 2010 09:31:27 -0400

The following patch speeds up some IRA code by compressing live
ranges even more.  The idea that if we have several subsequent deaths
(or births) and there are no births (or deaths) between them, we can
use one point for all these deaths (or births).

Is the patch ok to commit the patch to the trunk?

2010-07-07  Vladimir Makarov  <vmakarov@redhat.com>

    * ira-live.c: Include sbitmap.h.
    (remove_some_program_points_and_update_live_ranges): Use sbitmaps.
    Compress live ranges even more.


--- ira-lives.c	2010-07-06 11:37:23.000000000 -0400
+++ /home/cygnus/vmakarov/build1/ira-improv/gcc/gcc/ira-lives.c	2010-07-01 13:45:14.000000000 -0400
@@ -36,6 +36,7 @@ along with GCC; see the file COPYING3.  
 #include "toplev.h"
 #include "params.h"
 #include "df.h"
+#include "sbitmap.h"
 #include "sparseset.h"
 #include "ira-int.h"
 
@@ -1203,26 +1204,44 @@ remove_some_program_points_and_update_li
   ira_allocno_t a;
   ira_allocno_iterator ai;
   live_range_t r;
-  bitmap born_or_died;
-  bitmap_iterator bi;
-
-  born_or_died = ira_allocate_bitmap ();
+  sbitmap born_or_dead, born, dead;
+  sbitmap_iterator sbi;
+  bool born_p, dead_p, prev_born_p, prev_dead_p;
+
+  born = sbitmap_alloc (ira_max_point);
+  dead = sbitmap_alloc (ira_max_point);
+  sbitmap_zero (born);
+  sbitmap_zero (dead);
   FOR_EACH_ALLOCNO (a, ai)
     {
       for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
 	{
 	  ira_assert (r->start <= r->finish);
-	  bitmap_set_bit (born_or_died, r->start);
-	  bitmap_set_bit (born_or_died, r->finish);
+	  SET_BIT (born, r->start);
+	  SET_BIT (dead, r->finish);
 	}
     }
+  born_or_dead = sbitmap_alloc (ira_max_point);
+  sbitmap_a_or_b (born_or_dead, born, dead);
   map = (int *) ira_allocate (sizeof (int) * ira_max_point);
-  n = 0;
-  EXECUTE_IF_SET_IN_BITMAP(born_or_died, 0, i, bi)
+  n = -1;
+  prev_born_p = prev_dead_p = false;
+  EXECUTE_IF_SET_IN_SBITMAP (born_or_dead, 0, i, sbi)
     {
-      map[i] = n++;
+      born_p = TEST_BIT (born, i);
+      dead_p = TEST_BIT (dead, i);
+      if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
+	  || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
+	map[i] = n;
+      else
+	map[i] = ++n;
+      prev_born_p = born_p;
+      prev_dead_p = dead_p;
     }
-  ira_free_bitmap (born_or_died);
+  sbitmap_free (born_or_dead);
+  sbitmap_free (born);
+  sbitmap_free (dead);
+  n++;
   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
     fprintf (ira_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
 	     ira_max_point, n, 100 * n / ira_max_point);