Patchwork IRA improvements 2/4

login
register
mail settings
Submitter Vladimir Makarov
Date July 7, 2010, 1:31 p.m.
Message ID <4C3481AF.10503@redhat.com>
Download mbox | patch
Permalink /patch/58119/
State New
Headers show

Comments

Vladimir Makarov - July 7, 2010, 1:31 p.m.
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.
Jeff Law - July 7, 2010, 3:44 p.m.
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.
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.

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