The following patch speeds LRA up more on PR54146. Below times for
compilation of the test on gcc17.fsffrance.org (an AMD machine):
Before:
real=1214.71 user=1192.05 system=22.48
After:
real=1144.37 user=1124.31 system=20.11
The patch should not change the generated code. About 2/3 of speed up
is achieved by insertion of live ranges of pseudos only interesting for
assignment in the start point chains.
1/3 is achieved by switching iterations through a bitmap instead of
sparseset at the end of function process_bb_lives.
The patch was successfully bootstrapped on x86/x86-64.
Committed as rev. 192183.
2012-10-07 Vladimir Makarov <vmaka...@redhat.com>
* lra-int.h (struct lra_live_range): Remove finish_next.
(lra_start_point_ranges, lra_finish_point_ranges): Remove.
* lra-lives.c (lra_start_point_ranges, lra_finish_point_ranges):
Remove.
(process_bb_lives): Change start regno in
EXECUTE_IF_SET_IN_BITMAP. Iterate on DF_LR_IN (bb) instead of
pseudos_live_through_calls.
(create_start_finish_chains, rebuild_start_finish_chains): Remove.
(compress_live_ranges): Don't call rebuild_start_finish_chains.
(lra_create_live_ranges): Don't call create_start_finish_chains.
(lra_clear_live_ranges): Remove code freeing
lra_start_point_ranges and lra_finish_point_ranges.
* lra-assigns.c (start_point_ranges, not_in_chain_mark): New.
(create_live_range_start_chains): Ditto.
(insert_in_live_range_start_chain): Ditto.
(finish_live_range_start_chains): Ditto.
(update_lives, assign_temporarily): Call
insert_in_live_range_start_chain.
(find_hard_regno_for, spill_for): Rename lra_start_point_ranges to
start_point_ranges.
(setup_live_pseudos_and_spill_after_risky): Ditto.
(lra_assign): Call create_live_range_start_chains and
finish_live_range_start_chains.
Index: lra-lives.c
===================================================================
--- lra-lives.c (revision 192169)
+++ lra-lives.c (working copy)
@@ -54,10 +54,6 @@ along with GCC; see the file COPYING3. I
correspond to places where output operands are born. */
int lra_live_max_point;
-/* Arrays of size LRA_LIVE_MAX_POINT mapping a program point to the
- pseudo live ranges with given start/finish point. */
-lra_live_range_t *lra_start_point_ranges, *lra_finish_point_ranges;
-
/* Accumulated execution frequency of all references for each hard
register. */
int lra_hard_reg_usage[FIRST_PSEUDO_REGISTER];
@@ -529,9 +525,8 @@ process_bb_lives (basic_block bb)
REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
AND_COMPL_HARD_REG_SET (hard_regs_live, lra_no_alloc_regs);
- EXECUTE_IF_SET_IN_BITMAP (reg_live_out, 0, j, bi)
- if (j >= FIRST_PSEUDO_REGISTER)
- mark_pseudo_live (j);
+ EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
+ mark_pseudo_live (j);
freq = REG_FREQ_FROM_BB (bb);
@@ -755,47 +750,13 @@ process_bb_lives (basic_block bb)
EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
mark_pseudo_dead (i);
- EXECUTE_IF_SET_IN_SPARSESET (pseudos_live_through_calls, i)
- if (bitmap_bit_p (DF_LR_IN (bb), i))
- check_pseudos_live_through_calls (i);
+ EXECUTE_IF_SET_IN_BITMAP (DF_LR_IN (bb), FIRST_PSEUDO_REGISTER, j, bi)
+ if (sparseset_bit_p (pseudos_live_through_calls, j))
+ check_pseudos_live_through_calls (j);
incr_curr_point (freq);
}
-/* Create and set up LRA_START_POINT_RANGES and
- LRA_FINISH_POINT_RANGES. */
-static void
-create_start_finish_chains (void)
-{
- int i, max_regno;
- lra_live_range_t r;
-
- lra_start_point_ranges = XCNEWVEC (lra_live_range_t, lra_live_max_point);
- lra_finish_point_ranges = XCNEWVEC (lra_live_range_t, lra_live_max_point);
- max_regno = max_reg_num ();
- for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
- {
- for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
- {
- r->start_next = lra_start_point_ranges[r->start];
- lra_start_point_ranges[r->start] = r;
- r->finish_next = lra_finish_point_ranges[r->finish];
- lra_finish_point_ranges[r->finish] = r;
- }
- }
-}
-
-/* Rebuild LRA_START_POINT_RANGES and LRA_FINISH_POINT_RANGES after
- new live ranges and program points were added as a result of new
- insn generation. */
-static void
-rebuild_start_finish_chains (void)
-{
- free (lra_finish_point_ranges);
- free (lra_start_point_ranges);
- create_start_finish_chains ();
-}
-
/* Compress pseudo live ranges by removing program points where
nothing happens. Complexity of many algorithms in LRA is linear
function of program points number. To speed up the code we try to
@@ -934,7 +895,6 @@ static void
compress_live_ranges (void)
{
remove_some_program_points_and_update_live_ranges ();
- rebuild_start_finish_chains ();
if (lra_dump_file != NULL)
{
fprintf (lra_dump_file, "Ranges after the compression:\n");
@@ -997,7 +957,6 @@ lra_create_live_ranges (bool all_p)
FOR_EACH_BB (bb)
process_bb_lives (bb);
lra_live_max_point = curr_point;
- create_start_finish_chains ();
if (lra_dump_file != NULL)
print_live_ranges (lra_dump_file);
/* Clean up. */
@@ -1018,16 +977,6 @@ lra_clear_live_ranges (void)
{
int i;
- if (lra_finish_point_ranges != NULL)
- {
- free (lra_finish_point_ranges);
- lra_finish_point_ranges = NULL;
- }
- if (lra_start_point_ranges != NULL)
- {
- free (lra_start_point_ranges);
- lra_start_point_ranges = NULL;
- }
for (i = 0; i < max_reg_num (); i++)
free_live_range_list (lra_reg_info[i].live_ranges);
VEC_free (int, heap, point_freq_vec);
Index: lra-assigns.c
===================================================================
--- lra-assigns.c (revision 192169)
+++ lra-assigns.c (working copy)
@@ -213,6 +213,66 @@ pseudo_compare_func (const void *v1p, co
return r1 - r2;
}
+/* Arrays of size LRA_LIVE_MAX_POINT mapping a program point to the
+ pseudo live ranges with given start point. We insert only live
+ ranges of pseudos interesting for assignment purposes. They are
+ reload pseudos and pseudos assigned to hard registers. */
+static lra_live_range_t *start_point_ranges;
+
+/* Used as a flag that a live range is not inserted in the start point
+ chain. */
+static struct lra_live_range not_in_chain_mark;
+
+/* Create and set up START_POINT_RANGES. */
+static void
+create_live_range_start_chains (void)
+{
+ int i, max_regno;
+ lra_live_range_t r;
+
+ start_point_ranges = XCNEWVEC (lra_live_range_t, lra_live_max_point);
+ max_regno = max_reg_num ();
+ for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
+ if (i >= lra_constraint_new_regno_start || reg_renumber[i] >= 0)
+ {
+ for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
+ {
+ r->start_next = start_point_ranges[r->start];
+ start_point_ranges[r->start] = r;
+ }
+ }
+ else
+ {
+ for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
+ r->start_next = ¬_in_chain_mark;
+ }
+}
+
+/* Insert live ranges of pseudo REGNO into start chains if they are
+ not there yet. */
+static void
+insert_in_live_range_start_chain (int regno)
+{
+ lra_live_range_t r = lra_reg_info[regno].live_ranges;
+
+ if (r->start_next != ¬_in_chain_mark)
+ return;
+ for (; r != NULL; r = r->next)
+ {
+ r->start_next = start_point_ranges[r->start];
+ start_point_ranges[r->start] = r;
+ }
+}
+
+/* Free START_POINT_RANGES. */
+static void
+finish_live_range_start_chains (void)
+{
+ gcc_assert (start_point_ranges != NULL);
+ free (start_point_ranges);
+ start_point_ranges = NULL;
+}
+
/* Map: program point -> bitmap of all pseudos living at the point and
assigned to hard registers. */
static bitmap_head *live_hard_reg_pseudos;
@@ -279,7 +339,10 @@ update_lives (int regno, bool free_p)
if (free_p)
bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
else
- bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
+ {
+ bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
+ insert_in_live_range_start_chain (regno);
+ }
}
}
@@ -378,7 +441,7 @@ find_hard_regno_for (int regno, int *cos
{
lra_live_range_t r2;
- for (r2 = lra_start_point_ranges[p];
+ for (r2 = start_point_ranges[p];
r2 != NULL;
r2 = r2->start_next)
{
@@ -697,7 +760,10 @@ assign_temporarily (int regno, int hard_
if (hard_regno < 0)
bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
else
- bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
+ {
+ bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
+ insert_in_live_range_start_chain (regno);
+ }
}
live_pseudos_reg_renumber[regno] = hard_regno;
}
@@ -794,7 +860,7 @@ spill_for (int regno, bitmap spilled_pse
{
lra_live_range_t r2;
- for (r2 = lra_start_point_ranges[p];
+ for (r2 = start_point_ranges[p];
r2 != NULL;
r2 = r2->start_next)
if (r2->regno >= lra_constraint_new_regno_start)
@@ -968,7 +1034,7 @@ setup_live_pseudos_and_spill_after_risky
{
lra_live_range_t r2;
- for (r2 = lra_start_point_ranges[p];
+ for (r2 = start_point_ranges[p];
r2 != NULL;
r2 = r2->start_next)
if (live_pseudos_reg_renumber[r2->regno] >= 0)
@@ -1267,6 +1333,7 @@ lra_assign (void)
regno_allocno_class_array[i] = lra_get_allocno_class (i);
init_regno_assign_info ();
bitmap_initialize (&all_spilled_pseudos, ®_obstack);
+ create_live_range_start_chains ();
setup_live_pseudos_and_spill_after_risky_transforms (&all_spilled_pseudos);
#ifdef ENABLE_CHECKING
for (i = FIRST_PSEUDO_REGISTER; i < max_reg_num (); i++)
@@ -1292,6 +1359,7 @@ lra_assign (void)
no_spills_p = false;
break;
}
+ finish_live_range_start_chains ();
bitmap_clear (&all_spilled_pseudos);
bitmap_initialize (&insns_to_process, ®_obstack);
EXECUTE_IF_SET_IN_BITMAP (&changed_pseudo_bitmap, 0, u, bi)
Index: lra-int.h
===================================================================
--- lra-int.h (revision 192169)
+++ lra-int.h (working copy)
@@ -62,8 +62,8 @@ struct lra_live_range
/* Next structure describing program points where the pseudo
lives. */
lra_live_range_t next;
- /* Pointers to structures with the same start/finish. */
- lra_live_range_t start_next, finish_next;
+ /* Pointer to structures with the same start. */
+ lra_live_range_t start_next;
};
typedef struct lra_copy *lra_copy_t;
@@ -315,7 +315,6 @@ extern bool lra_undo_inheritance (void);
/* lra-lives.c: */
extern int lra_live_max_point;
-extern lra_live_range_t *lra_start_point_ranges, *lra_finish_point_ranges;
extern int *lra_point_freq;
extern int lra_hard_reg_usage[FIRST_PSEUDO_REGISTER];
