This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
RFA: patch to solve IRA problem for PR37488
- From: Vladimir Makarov <vmakarov at redhat dot com>
- To: gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Fri, 12 Sep 2008 15:15:20 -0400
- Subject: RFA: patch to solve IRA problem for PR37488
The following patch solves problem 37488 in IRA for -O2 mode. To
achieve decent IRA speed I rewrote coalescing spilled allocnos
analogous to code used for IRA allocno allocation in -O0 mode. It
permitted to decrease IRA work time from >1hour to 50sec on a Core2
machine. The patch also contains compression of live ranges which
permits to decrease the time to 45sec so IRA spends 23% of all
compiler time in -O2 for this pathological test. The compression
usually decreases live ranges in 3 times and should also speed up IRA
in -O0 (although IRA in -O0 is already faster than the old RA).
The patch does not change (and should not change) the generated
code. The patch was successfully bootstrapped on x86_64.
2008-09-12 Vladimir Makarov <vmakarov@redhat.com>
PR middle-end/37448
* ira-int.h (IRA_ALLOCNO_TEMP): Rename to ALLOCNO_TEMP.
(ira_compress_allocno_live_ranges): New prototype.
* ira-color.c: Rename IRA_ALLOCNO_TEMP to ALLOCNO_TEMP.
(coalesced_allocnos_living_at_program_points): New.
(coalesced_allocnos_live_at_points_p,
set_coalesced_allocnos_live_points): New functions.
(coalesce_spill_slots): Rewrite.
* ira-lives.c (remove_some_program_points_and_update_live_ranges,
ira_compress_allocno_live_ranges): New functions.
* ira-build.c (ira_flattening): Call
ira_compress_allocno_live_ranges.
(ira_build): Ditto.
Index: ira-int.h
===================================================================
--- ira-int.h (revision 140314)
+++ ira-int.h (working copy)
@@ -457,7 +457,7 @@ struct ira_allocno
#define ALLOCNO_AVAILABLE_REGS_NUM(A) ((A)->available_regs_num)
#define ALLOCNO_NEXT_BUCKET_ALLOCNO(A) ((A)->next_bucket_allocno)
#define ALLOCNO_PREV_BUCKET_ALLOCNO(A) ((A)->prev_bucket_allocno)
-#define IRA_ALLOCNO_TEMP(A) ((A)->temp)
+#define ALLOCNO_TEMP(A) ((A)->temp)
#define ALLOCNO_FIRST_COALESCED_ALLOCNO(A) ((A)->first_coalesced_allocno)
#define ALLOCNO_NEXT_COALESCED_ALLOCNO(A) ((A)->next_coalesced_allocno)
#define ALLOCNO_LIVE_RANGES(A) ((A)->live_ranges)
@@ -882,6 +882,7 @@ extern void ira_debug_live_range_list (a
extern void ira_debug_allocno_live_ranges (ira_allocno_t);
extern void ira_debug_live_ranges (void);
extern void ira_create_allocno_live_ranges (void);
+extern void ira_compress_allocno_live_ranges (void);
extern void ira_finish_allocno_live_ranges (void);
/* ira-conflicts.c */
Index: ira-color.c
===================================================================
--- ira-color.c (revision 140314)
+++ ira-color.c (working copy)
@@ -940,17 +940,17 @@ allocno_spill_priority_compare (splay_tr
int pri1, pri2, diff;
ira_allocno_t a1 = (ira_allocno_t) k1, a2 = (ira_allocno_t) k2;
- pri1 = (IRA_ALLOCNO_TEMP (a1)
+ pri1 = (ALLOCNO_TEMP (a1)
/ (ALLOCNO_LEFT_CONFLICTS_NUM (a1)
* ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a1)][ALLOCNO_MODE (a1)]
+ 1));
- pri2 = (IRA_ALLOCNO_TEMP (a2)
+ pri2 = (ALLOCNO_TEMP (a2)
/ (ALLOCNO_LEFT_CONFLICTS_NUM (a2)
* ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a2)][ALLOCNO_MODE (a2)]
+ 1));
if ((diff = pri1 - pri2) != 0)
return diff;
- if ((diff = IRA_ALLOCNO_TEMP (a1) - IRA_ALLOCNO_TEMP (a2)) != 0)
+ if ((diff = ALLOCNO_TEMP (a1) - ALLOCNO_TEMP (a2)) != 0)
return diff;
return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
}
@@ -1025,7 +1025,7 @@ push_allocnos_to_stack (void)
}
/* ??? Remove cost of copies between the coalesced
allocnos. */
- IRA_ALLOCNO_TEMP (allocno) = cost;
+ ALLOCNO_TEMP (allocno) = cost;
}
/* Define place where to put uncolorable allocnos of the same cover
class. */
@@ -1117,7 +1117,7 @@ push_allocnos_to_stack (void)
if (ALLOCNO_IN_GRAPH_P (i_allocno))
{
i++;
- if (IRA_ALLOCNO_TEMP (i_allocno) == INT_MAX)
+ if (ALLOCNO_TEMP (i_allocno) == INT_MAX)
{
ira_allocno_t a;
int cost = 0;
@@ -1131,9 +1131,9 @@ push_allocnos_to_stack (void)
}
/* ??? Remove cost of copies between the coalesced
allocnos. */
- IRA_ALLOCNO_TEMP (i_allocno) = cost;
+ ALLOCNO_TEMP (i_allocno) = cost;
}
- i_allocno_cost = IRA_ALLOCNO_TEMP (i_allocno);
+ i_allocno_cost = ALLOCNO_TEMP (i_allocno);
i_allocno_pri
= (i_allocno_cost
/ (ALLOCNO_LEFT_CONFLICTS_NUM (i_allocno)
@@ -2252,6 +2252,53 @@ collect_spilled_coalesced_allocnos (int
return num;
}
+/* Array of bitmaps of size IRA_MAX_POINT. Bitmap for given point
+ contains numbers of coalesced allocnos living at this point. */
+static regset_head *coalesced_allocnos_living_at_program_points;
+
+/* Return TRUE if coalesced allocnos represented by ALLOCNO live at
+ program points of coalesced allocnos with number N. */
+static bool
+coalesced_allocnos_live_at_points_p (ira_allocno_t allocno, int n)
+{
+ int i;
+ ira_allocno_t a;
+ allocno_live_range_t r;
+
+ for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
+ a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
+ {
+ for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
+ for (i = r->start; i <= r->finish; i++)
+ if (bitmap_bit_p (&coalesced_allocnos_living_at_program_points[i], n))
+ return true;
+ if (a == allocno)
+ break;
+ }
+ return false;
+}
+
+/* Mark program points where coalesced allocnos represented by ALLOCNO
+ live. */
+static void
+set_coalesced_allocnos_live_points (ira_allocno_t allocno)
+{
+ int i, n;
+ ira_allocno_t a;
+ allocno_live_range_t r;
+
+ n = ALLOCNO_TEMP (allocno);
+ for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
+ a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
+ {
+ for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
+ for (i = r->start; i <= r->finish; i++)
+ bitmap_set_bit (&coalesced_allocnos_living_at_program_points[i], n);
+ if (a == allocno)
+ break;
+ }
+}
+
/* We have coalesced allocnos involving in copies. Coalesce allocnos
further in order to share the same memory stack slot. Allocnos
representing sets of allocnos coalesced before the call are given
@@ -2260,10 +2307,15 @@ collect_spilled_coalesced_allocnos (int
static bool
coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
{
- int i, j;
+ int i, j, last_coalesced_allocno_num;
ira_allocno_t allocno, a;
bool merged_p = false;
+ coalesced_allocnos_living_at_program_points
+ = (regset_head *) ira_allocate (sizeof (regset_head) * ira_max_point);
+ for (i = 0; i < ira_max_point; i++)
+ INIT_REG_SET (&coalesced_allocnos_living_at_program_points[i]);
+ last_coalesced_allocno_num = 0;
/* Coalesce non-conflicting spilled allocnos preferring most
frequently used. */
for (i = 0; i < num; i++)
@@ -2277,12 +2329,23 @@ coalesce_spill_slots (ira_allocno_t *spi
for (j = 0; j < i; j++)
{
a = spilled_coalesced_allocnos[j];
- if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) != a
- || (ALLOCNO_REGNO (a) < ira_reg_equiv_len
- && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (a)]
- || ira_reg_equiv_const[ALLOCNO_REGNO (a)] != NULL_RTX))
- || coalesced_allocno_conflict_p (allocno, a, true))
- continue;
+ if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a
+ && (ALLOCNO_REGNO (a) > ira_reg_equiv_len
+ || (! ira_reg_equiv_invariant_p[ALLOCNO_REGNO (a)]
+ && ira_reg_equiv_const[ALLOCNO_REGNO (a)] == NULL_RTX))
+ && ! coalesced_allocnos_live_at_points_p (allocno,
+ ALLOCNO_TEMP (a)))
+ break;
+ }
+ if (j >= i)
+ {
+ /* No coalescing: set up number for coalesced allocnos
+ represented by ALLOCNO. */
+ ALLOCNO_TEMP (allocno) = last_coalesced_allocno_num++;
+ set_coalesced_allocnos_live_points (allocno);
+ }
+ else
+ {
allocno_coalesced_p = true;
merged_p = true;
if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
@@ -2290,10 +2353,15 @@ coalesce_spill_slots (ira_allocno_t *spi
" Coalescing spilled allocnos a%dr%d->a%dr%d\n",
ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
+ ALLOCNO_TEMP (allocno) = ALLOCNO_TEMP (a);
+ set_coalesced_allocnos_live_points (allocno);
merge_allocnos (a, allocno);
ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a);
}
}
+ for (i = 0; i < ira_max_point; i++)
+ CLEAR_REG_SET (&coalesced_allocnos_living_at_program_points[i]);
+ ira_free (coalesced_allocnos_living_at_program_points);
return merged_p;
}
Index: ira-lives.c
===================================================================
--- ira-lives.c (revision 140314)
+++ ira-lives.c (working copy)
@@ -843,6 +843,52 @@ ira_rebuild_start_finish_chains (void)
create_start_finish_chains ();
}
+/* Compress allocno live ranges by removing program points where
+ nothing happens. */
+static void
+remove_some_program_points_and_update_live_ranges (void)
+{
+ unsigned i;
+ int n;
+ int *map;
+ ira_allocno_t a;
+ ira_allocno_iterator ai;
+ allocno_live_range_t r;
+ bitmap born_or_died;
+ bitmap_iterator bi;
+
+ born_or_died = ira_allocate_bitmap ();
+ 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);
+ }
+ }
+ map = (int *) ira_allocate (sizeof (int) * ira_max_point);
+ n = 0;
+ EXECUTE_IF_SET_IN_BITMAP(born_or_died, 0, i, bi)
+ {
+ map[i] = n++;
+ }
+ ira_free_bitmap (born_or_died);
+ 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);
+ ira_max_point = n;
+ FOR_EACH_ALLOCNO (a, ai)
+ {
+ for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
+ {
+ r->start = map[r->start];
+ r->finish = map[r->finish];
+ }
+ }
+ ira_free (map);
+}
+
/* Print live ranges R to file F. */
void
ira_print_live_range_list (FILE *f, allocno_live_range_t r)
@@ -910,6 +956,19 @@ ira_create_allocno_live_ranges (void)
sparseset_free (allocnos_live);
}
+/* Compress allocno live ranges. */
+void
+ira_compress_allocno_live_ranges (void)
+{
+ remove_some_program_points_and_update_live_ranges ();
+ ira_rebuild_start_finish_chains ();
+ if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
+ {
+ fprintf (ira_dump_file, "Ranges after the compression:\n");
+ print_live_ranges (ira_dump_file);
+ }
+}
+
/* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES. */
void
ira_finish_allocno_live_ranges (void)
Index: ira-build.c
===================================================================
--- ira-build.c (revision 140314)
+++ ira-build.c (working copy)
@@ -2373,6 +2373,8 @@ ira_flattening (int max_regno_before_emi
ira_swap_allocno_copy_ends_if_necessary (cp);
}
rebuild_regno_allocno_maps ();
+ if (ira_max_point != ira_max_point_before_emit)
+ ira_compress_allocno_live_ranges ();
ira_free (regno_top_level_allocno_map);
}
@@ -2429,6 +2431,7 @@ ira_build (bool loops_p)
ira_costs ();
ira_create_allocno_live_ranges ();
remove_unnecessary_regions ();
+ ira_compress_allocno_live_ranges ();
loops_p = more_one_region_p ();
if (loops_p)
{