diff mbox

IRA improvements 2/4

Message ID 4C3481AF.10503@redhat.com
State New
Headers show

Commit Message

Vladimir Makarov July 7, 2010, 1:31 p.m. UTC 
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.

Comments

Jeff Law July 7, 2010, 3:44 p.m. UTC | #1 
On 07/07/10 07:31, Vladimir Makarov wrote:
>  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.
OK.

Presumably you switched to use sbitmaps because typical map density of 
points where something is either born or dies makes them more efficient 
than bitmaps?

Jeff
Vladimir Makarov July 7, 2010, 3:51 p.m. UTC | #2 
Jeff Law wrote:
> On 07/07/10 07:31, Vladimir Makarov wrote:
>>  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.
> OK.
>
Thanks.
> Presumably you switched to use sbitmaps because typical map density of 
> points where something is either born or dies makes them more 
> efficient than bitmaps?
Right, they are very dense.  Therefore I use sbitmaps.
diff mbox

Patch

--- 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);