This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: IRA accumulated costs
- From: Vladimir Makarov <vmakarov at redhat dot com>
- To: gcc at gcc dot gnu dot org, rdsandiford at googlemail dot com
- Date: Wed, 01 Oct 2008 10:12:48 -0400
- Subject: Re: IRA accumulated costs
- References: <87prmpzup4.fsf@firetop.home> <48E14521.4030100@redhat.com>
Hi, Richard. Returning to accurate cost accumulation issue you found
recently. Here is the patch fixing it. You could try, if you want, how
MIPS will behave with it. The patch also more accurately calculates
ALLOCNO_CALL_FREQ which affects decision to spill allocno in
assign_hard_reg if it is more profitable.
2008-10-01 Vladimir Makarov <vmakarov@redhat.com>
* ira-int.h (ira_allocno): Add member updated_cover_class_cost.
(ALLOCNO_UPDATED_COVER_CLASS_COST): New.
(ira_fast_allocation): Remove the prototype.
* ira-color.c (update_copy_costs, allocno_cost_compare_func,
assign_hard_reg, calculate_allocno_spill_cost): Use updated costs.
(color_pass): Modify the updated costs.
(ira_color): Rename to color. Make it static.
(ira_fast_allocation): Rename to fast_allocation. Make it static.
(ira_color): New function.
* ira-conflicts.c (process_regs_for_copy): Propagate hard reg cost
change.
* ira-lives.c (last_call_num, allocno_saved_at_call): New
variables.
(set_allocno_live, clear_allocno_live, mark_ref_live,
mark_ref_dead): Invalidate corresponding element of
allocno_saved_at_call.
(process_bb_node_lives): Increment last_call_num. Setup
allocno_saved_at_call. Don't increase ALLOCNO_CALL_FREQ if the
allocno was already saved.
(ira_create_allocno_live_ranges): Initiate last_call_num and
allocno_saved_at_call.
* ira-build.c (ira_create_allocno): Initiate
ALLOCNO_UPDATED_COVER_CLASS_COST.
(create_cap_allocno, propagate_allocno_info,
remove_unnecessary_allocnos): Remove setting updated costs.
(ira_flattening): Set up ALLOCNO_UPDATED_COVER_CLASS_COST.
* ira.c (ira): Don't call ira_fast_allocation.
* ira-costs.c (setup_allocno_cover_class_and_costs): Don't set up
updated costs.
Index: ira-conflicts.c
===================================================================
--- ira-conflicts.c (revision 140793)
+++ ira-conflicts.c (working copy)
@@ -337,6 +337,7 @@ process_regs_for_copy (rtx reg1, rtx reg
enum reg_class rclass, cover_class;
enum machine_mode mode;
ira_copy_t cp;
+ ira_loop_tree_node_t parent;
gcc_assert (REG_SUBREG_P (reg1) && REG_SUBREG_P (reg2));
only_regs_p = REG_P (reg1) && REG_P (reg2);
@@ -388,13 +389,23 @@ process_regs_for_copy (rtx reg1, rtx reg
cost = ira_register_move_cost[mode][cover_class][rclass] * freq;
else
cost = ira_register_move_cost[mode][rclass][cover_class] * freq;
- ira_allocate_and_set_costs
- (&ALLOCNO_HARD_REG_COSTS (a), cover_class,
- ALLOCNO_COVER_CLASS_COST (a));
- ira_allocate_and_set_costs
- (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), cover_class, 0);
- ALLOCNO_HARD_REG_COSTS (a)[index] -= cost;
- ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= cost;
+ for (;;)
+ {
+ ira_allocate_and_set_costs
+ (&ALLOCNO_HARD_REG_COSTS (a), cover_class,
+ ALLOCNO_COVER_CLASS_COST (a));
+ ira_allocate_and_set_costs
+ (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), cover_class, 0);
+ ALLOCNO_HARD_REG_COSTS (a)[index] -= cost;
+ ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= cost;
+ if (ALLOCNO_HARD_REG_COSTS (a)[index] < ALLOCNO_COVER_CLASS_COST (a))
+ ALLOCNO_COVER_CLASS_COST (a) = ALLOCNO_HARD_REG_COSTS (a)[index];
+ if (ALLOCNO_CAP (a) != NULL)
+ a = ALLOCNO_CAP (a);
+ else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
+ || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
+ break;
+ }
return true;
}
Index: ira-int.h
===================================================================
--- ira-int.h (revision 140793)
+++ ira-int.h (working copy)
@@ -258,9 +258,9 @@ struct ira_allocno
/* Register class which should be used for allocation for given
allocno. NO_REGS means that we should use memory. */
enum reg_class cover_class;
- /* Minimal accumulated cost of usage register of the cover class for
- the allocno. */
- int cover_class_cost;
+ /* Minimal accumulated and updated costs of usage register of the
+ cover class for the allocno. */
+ int cover_class_cost, updated_cover_class_cost;
/* Minimal accumulated, and updated costs of memory for the allocno.
At the allocation start, the original and updated costs are
equal. The updated cost may be changed after finishing
@@ -451,6 +451,7 @@ struct ira_allocno
#define ALLOCNO_LEFT_CONFLICTS_NUM(A) ((A)->left_conflicts_num)
#define ALLOCNO_COVER_CLASS(A) ((A)->cover_class)
#define ALLOCNO_COVER_CLASS_COST(A) ((A)->cover_class_cost)
+#define ALLOCNO_UPDATED_COVER_CLASS_COST(A) ((A)->updated_cover_class_cost)
#define ALLOCNO_MEMORY_COST(A) ((A)->memory_cost)
#define ALLOCNO_UPDATED_MEMORY_COST(A) ((A)->updated_memory_cost)
#define ALLOCNO_EXCESS_PRESSURE_POINTS_NUM(A) ((A)->excess_pressure_points_num)
@@ -897,7 +898,6 @@ extern void ira_reassign_conflict_allocn
extern void ira_initiate_assign (void);
extern void ira_finish_assign (void);
extern void ira_color (void);
-extern void ira_fast_allocation (void);
/* ira-emit.c */
extern void ira_emit (bool);
Index: ira-color.c
===================================================================
--- ira-color.c (revision 140793)
+++ ira-color.c (working copy)
@@ -252,7 +252,7 @@ update_copy_costs (ira_allocno_t allocno
ira_allocate_and_set_or_copy_costs
(&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno), cover_class,
- ALLOCNO_COVER_CLASS_COST (another_allocno),
+ ALLOCNO_UPDATED_COVER_CLASS_COST (another_allocno),
ALLOCNO_HARD_REG_COSTS (another_allocno));
ira_allocate_and_set_or_copy_costs
(&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
@@ -348,8 +348,8 @@ allocno_cost_compare_func (const void *v
ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
int c1, c2;
- c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_COVER_CLASS_COST (p1);
- c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_COVER_CLASS_COST (p2);
+ c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_COVER_CLASS_COST (p1);
+ c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_COVER_CLASS_COST (p2);
if (c1 - c2)
return c1 - c2;
@@ -426,7 +426,9 @@ assign_hard_reg (ira_allocno_t allocno,
#ifdef STACK_REGS
no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
#endif
- for (cost = ALLOCNO_COVER_CLASS_COST (a), i = 0; i < class_size; i++)
+ for (cost = ALLOCNO_UPDATED_COVER_CLASS_COST (a), i = 0;
+ i < class_size;
+ i++)
if (a_costs != NULL)
{
costs[i] += a_costs[i];
@@ -959,7 +961,7 @@ calculate_allocno_spill_cost (ira_allocn
ira_loop_tree_node_t parent_node, loop_node;
regno = ALLOCNO_REGNO (a);
- cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a);
+ cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_COVER_CLASS_COST (a);
if (ALLOCNO_CAP (a) != NULL)
return cost;
loop_node = ALLOCNO_LOOP_TREE_NODE (a);
@@ -1821,24 +1823,26 @@ color_pass (ira_loop_tree_node_t loop_tr
else
{
cover_class = ALLOCNO_COVER_CLASS (subloop_allocno);
- ira_allocate_and_set_costs
- (&ALLOCNO_HARD_REG_COSTS (subloop_allocno), cover_class,
- ALLOCNO_COVER_CLASS_COST (subloop_allocno));
- ira_allocate_and_set_costs
- (&ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno),
- cover_class, 0);
cost = (ira_register_move_cost[mode][rclass][rclass]
* (exit_freq + enter_freq));
- ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
- ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
+ ira_allocate_and_set_or_copy_costs
+ (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), cover_class,
+ ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno),
+ ALLOCNO_HARD_REG_COSTS (subloop_allocno));
+ ira_allocate_and_set_or_copy_costs
+ (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
+ cover_class, 0,
+ ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
+ ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
+ ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
-= cost;
+ if (ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno)
+ > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
+ ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno)
+ = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
+= (ira_memory_move_cost[mode][rclass][0] * enter_freq
+ ira_memory_move_cost[mode][rclass][1] * exit_freq);
- if (ALLOCNO_COVER_CLASS_COST (subloop_allocno)
- > ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index])
- ALLOCNO_COVER_CLASS_COST (subloop_allocno)
- = ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index];
}
}
}
@@ -3054,8 +3058,8 @@ ira_finish_assign (void)
/* Entry function doing color-based register allocation. */
-void
-ira_color (void)
+static void
+color (void)
{
allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
removed_splay_allocno_vec
@@ -3077,8 +3081,8 @@ ira_color (void)
/* Do register allocation by not using allocno conflicts. It uses
only allocno live ranges. The algorithm is close to Chow's
priority coloring. */
-void
-ira_fast_allocation (void)
+static void
+fast_allocation (void)
{
int i, j, k, num, class_size, hard_regno;
#ifdef STACK_REGS
@@ -3148,3 +3152,24 @@ ira_fast_allocation (void)
if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
ira_print_disposition (ira_dump_file);
}
+
+
+
+/* Entry function doing coloring. */
+void
+ira_color (void)
+{
+ ira_allocno_t a;
+ ira_allocno_iterator ai;
+
+ /* Setup updated costs. */
+ FOR_EACH_ALLOCNO (a, ai)
+ {
+ ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
+ ALLOCNO_UPDATED_COVER_CLASS_COST (a) = ALLOCNO_COVER_CLASS_COST (a);
+ }
+ if (optimize)
+ color ();
+ else
+ fast_allocation ();
+}
Index: ira-lives.c
===================================================================
--- ira-lives.c (revision 140793)
+++ ira-lives.c (working copy)
@@ -75,6 +75,11 @@ static HARD_REG_SET hard_regs_live;
/* The loop tree node corresponding to the current basic block. */
static ira_loop_tree_node_t curr_bb_node;
+/* The number of the last processed call. */
+static int last_call_num;
+/* The number of last call at which given allocno was saved. */
+static int *allocno_saved_at_call;
+
/* The function processing birth of register REGNO. It updates living
hard regs and conflict hard regs for living allocnos or starts a
new live range for the allocno corresponding to REGNO if it is
@@ -163,6 +168,8 @@ set_allocno_live (ira_allocno_t a)
int nregs;
enum reg_class cover_class;
+ /* Invalidate because it is referenced. */
+ allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
if (sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
return;
sparseset_set_bit (allocnos_live, ALLOCNO_NUM (a));
@@ -189,6 +196,8 @@ clear_allocno_live (ira_allocno_t a)
unsigned int i;
enum reg_class cover_class;
+ /* Invalidate because it is referenced. */
+ allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
if (sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
{
cover_class = ALLOCNO_COVER_CLASS (a);
@@ -233,7 +242,11 @@ mark_ref_live (struct df_ref *ref)
if (a != NULL)
{
if (sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
- return;
+ {
+ /* Invalidate because it is referenced. */
+ allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
+ return;
+ }
set_allocno_live (a);
}
make_regno_born (regno);
@@ -305,7 +318,11 @@ mark_ref_dead (struct df_ref *def)
if (a != NULL)
{
if (! sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
- return;
+ {
+ /* Invalidate because it is referenced. */
+ allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
+ return;
+ }
clear_allocno_live (a);
}
make_regno_dead (regno);
@@ -627,6 +644,9 @@ process_bb_node_lives (ira_loop_tree_nod
if (freq == 0)
freq = 1;
+ /* Invalidate all allocno_saved_at_call entries. */
+ last_call_num++;
+
/* Scan the code of this basic block, noting which allocnos and
hard regs are born or die.
@@ -707,12 +727,21 @@ process_bb_node_lives (ira_loop_tree_nod
if (call_p)
{
+ last_call_num++;
/* The current set of live allocnos are live across the call. */
EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
{
ira_allocno_t a = ira_allocnos[i];
- ALLOCNO_CALL_FREQ (a) += freq;
+ if (allocno_saved_at_call[i] != last_call_num)
+ /* Here we are mimicking caller-save.c behaviour
+ which does not save hard register at a call if
+ it was saved on previous call in the same basic
+ block and the hard register was not mentioned
+ between the two calls. */
+ ALLOCNO_CALL_FREQ (a) += freq;
+ /* Mark it as saved at the next call. */
+ allocno_saved_at_call[i] = last_call_num + 1;
ALLOCNO_CALLS_CROSSED_NUM (a)++;
/* Don't allocate allocnos that cross setjmps or any
call, if this function receives a nonlocal
@@ -946,6 +975,10 @@ ira_create_allocno_live_ranges (void)
{
allocnos_live = sparseset_alloc (ira_allocnos_num);
curr_point = 0;
+ last_call_num = 0;
+ allocno_saved_at_call
+ = (int *) ira_allocate (ira_allocnos_num * sizeof (int));
+ memset (allocno_saved_at_call, 0, ira_allocnos_num * sizeof (int));
ira_traverse_loop_tree (true, ira_loop_tree_root, NULL,
process_bb_node_lives);
ira_max_point = curr_point;
@@ -953,6 +986,7 @@ ira_create_allocno_live_ranges (void)
if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
print_live_ranges (ira_dump_file);
/* Clean up. */
+ ira_free (allocno_saved_at_call);
sparseset_free (allocnos_live);
}
Index: ira-build.c
===================================================================
--- ira-build.c (revision 140793)
+++ ira-build.c (working copy)
@@ -469,6 +469,7 @@ ira_create_allocno (int regno, bool cap_
ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
ALLOCNO_LEFT_CONFLICTS_NUM (a) = -1;
ALLOCNO_COVER_CLASS (a) = NO_REGS;
+ ALLOCNO_UPDATED_COVER_CLASS_COST (a) = 0;
ALLOCNO_COVER_CLASS_COST (a) = 0;
ALLOCNO_MEMORY_COST (a) = 0;
ALLOCNO_UPDATED_MEMORY_COST (a) = 0;
@@ -769,7 +770,6 @@ create_cap_allocno (ira_allocno_t a)
ALLOCNO_CAP (a) = cap;
ALLOCNO_COVER_CLASS_COST (cap) = ALLOCNO_COVER_CLASS_COST (a);
ALLOCNO_MEMORY_COST (cap) = ALLOCNO_MEMORY_COST (a);
- ALLOCNO_UPDATED_MEMORY_COST (cap) = ALLOCNO_UPDATED_MEMORY_COST (a);
ira_allocate_and_copy_costs
(&ALLOCNO_HARD_REG_COSTS (cap), cover_class, ALLOCNO_HARD_REG_COSTS (a));
ira_allocate_and_copy_costs
@@ -1509,8 +1509,6 @@ propagate_allocno_info (void)
ALLOCNO_COVER_CLASS_COST (parent_a)
+= ALLOCNO_COVER_CLASS_COST (a);
ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
- ALLOCNO_UPDATED_MEMORY_COST (parent_a)
- += ALLOCNO_UPDATED_MEMORY_COST (a);
}
}
@@ -1789,8 +1787,6 @@ remove_unnecessary_allocnos (void)
ALLOCNO_COVER_CLASS_COST (parent_a)
+= ALLOCNO_COVER_CLASS_COST (a);
ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
- ALLOCNO_UPDATED_MEMORY_COST (parent_a)
- += ALLOCNO_UPDATED_MEMORY_COST (a);
finish_allocno (a);
}
}
@@ -2349,7 +2345,9 @@ ira_flattening (int max_regno_before_emi
ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
ALLOCNO_REGNO (a) = REGNO (ALLOCNO_REG (a));
ALLOCNO_CAP (a) = NULL;
+ /* Restore updated costs for assignments from reload. */
ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
+ ALLOCNO_UPDATED_COVER_CLASS_COST (a) = ALLOCNO_COVER_CLASS_COST (a);
if (! ALLOCNO_ASSIGNED_P (a))
ira_free_allocno_updated_costs (a);
ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
Index: ira.c
===================================================================
--- ira.c (revision 140793)
+++ ira.c (working copy)
@@ -1761,10 +1761,7 @@ ira (FILE *f)
loops_p = ira_build (optimize
&& (flag_ira_algorithm == IRA_ALGORITHM_REGIONAL
|| flag_ira_algorithm == IRA_ALGORITHM_MIXED));
- if (optimize)
- ira_color ();
- else
- ira_fast_allocation ();
+ ira_color ();
ira_max_point_before_emit = ira_max_point;
Index: ira-costs.c
===================================================================
--- ira-costs.c (revision 140793)
+++ ira-costs.c (working copy)
@@ -1405,15 +1405,13 @@ setup_allocno_cover_class_and_costs (voi
mode = ALLOCNO_MODE (a);
cover_class = ira_class_translate[allocno_pref[i]];
ira_assert (allocno_pref[i] == NO_REGS || cover_class != NO_REGS);
- ALLOCNO_MEMORY_COST (a) = ALLOCNO_UPDATED_MEMORY_COST (a)
- = COSTS_OF_ALLOCNO (allocno_costs, i)->mem_cost;
+ ALLOCNO_MEMORY_COST (a) = COSTS_OF_ALLOCNO (allocno_costs, i)->mem_cost;
ira_set_allocno_cover_class (a, cover_class);
if (cover_class == NO_REGS)
continue;
ALLOCNO_AVAILABLE_REGS_NUM (a) = ira_available_class_regs[cover_class];
- ALLOCNO_COVER_CLASS_COST (a)
- = (COSTS_OF_ALLOCNO (allocno_costs, i)
- ->cost[cost_class_nums[allocno_pref[i]]]);
+ ALLOCNO_COVER_CLASS_COST (a) = (COSTS_OF_ALLOCNO (allocno_costs, i)
+ ->cost[cost_class_nums[allocno_pref[i]]]);
if (optimize && ALLOCNO_COVER_CLASS (a) != allocno_pref[i])
{
n = ira_class_hard_regs_num[cover_class];