I had a look at the costs issues in this PR. I think I've found a fair
number of bugs, but fixing those alone doesn't solve the issue; one
additional tweak is needed.
As for the bugs, they are primarily in the mechanism of recording cost
updates and restoring them. When adjusting costs for preferences and
copies, we create records of the adjustments we made. At the end of
assign_hard_reg, when we have assigned a hard register, we try to undo
these changes (through restore_costs_from_copies), and then call
update_costs_from_copies again with the real assigned hard register
number so that future allocations take that into account.
The issues I can see are:
1. restore_costs_from_copies passes true for decr_p, which means costs
aren't restored, but doubled instead.
2. update_costs_from_allocno records a cost update not just for the
initial allocno, but for each of the visited ones. I can sort of see an
argument for doing that (let's say if you assign an allocno in the
middle of a copy chain you'd want the tail end of the chain to be
reset), but in practice I don't think the present algorithm can work at
all. In the case of an allocno in the middle of a copy chain the restore
would progress in both directions, and in any case it looks like this
approach can end up double-counting things when restoring costs.
3. As far as I can tell, in update_costs_from_prefs, we adjust costs for
all allocnos connected to the one with the pref, but not for the initial
one.
The patch below corrects these. Issue #2 has no clearly best solution;
in this patch I've just moved the recording of the cost out of the loop
so it's done only for the initial allocno. The code is a little
convoluted so as to prevent skipping restorations if allocnos in a copy
chain have already been allocated. I have an alternative patch that more
directly records actual cost updates caused to other allocnos for a
given one. That variant is a little more clear, but consumes a bit more
memory. I can post that as well if desired.
As for the cost tweak, Vlad mentioned the effect of copies for
commutative operands in the PR. I ended up dividing the frequency of
such copies by two. (Another way to solve the PR is to reduce the
initial divisor for preference updates, but that seems a little more
hackish).
The overall effect of this patch seems to be fairly minimal in practice,
which is slightly disappointing. On the whole, it seems to be a very
slight net positive, with few instances where we generate additional
instructions.
Ok (in full or in parts, now or for stage1)?
Bernd
* ira-color.c (record_update_cost): New function, replacing...
(get_update_cost_record): ... this, removed.
(update_allocno_cost): Return false if allocno has been assigned.
(update_costs_from_allocno): Call record_udpate_cost once for
the initial allocno. Don't record update costs for allocnos
found while following copies.
(update_costs_from_prefs): Adjust costs of the initial allocno.
(restore_costs_from_copies): Fix call to update_costs_from_allocno
to undo previous changes.
* ira-conflicts.c (add_insn_allocno_copies): Divide freq by two
for commutative operands.
Index: gcc/ira-color.c
===================================================================
--- gcc/ira-color.c (revision 233451)
+++ gcc/ira-color.c (working copy)
@@ -1146,18 +1146,17 @@ setup_profitable_hard_regs (void)
static object_allocator<update_cost_record> update_cost_record_pool
("update cost records");
-/* Return new update cost record with given params. */
-static struct update_cost_record *
-get_update_cost_record (int hard_regno, int divisor,
- struct update_cost_record *next)
+/* Create a new update cost record in DATA with given params. */
+static void
+record_update_cost (allocno_color_data_t data, int hard_regno, int divisor)
{
struct update_cost_record *record;
record = update_cost_record_pool.allocate ();
record->hard_regno = hard_regno;
record->divisor = divisor;
- record->next = next;
- return record;
+ record->next = data->update_cost_records;
+ data->update_cost_records = record;
}
/* Free memory for all records in LIST. */
@@ -1305,6 +1304,9 @@ static bool
update_allocno_cost (ira_allocno_t allocno, int hard_regno,
int update_cost, int update_conflict_cost)
{
+ if (ALLOCNO_ASSIGNED_P (allocno))
+ return false;
+
int i;
enum reg_class aclass = ALLOCNO_CLASS (allocno);
@@ -1337,6 +1339,9 @@ update_costs_from_allocno (ira_allocno_t
ira_allocno_t another_allocno, from = NULL;
ira_copy_t cp, next_cp;
+ if (record_p && ALLOCNO_COLOR_DATA (allocno) != NULL)
+ record_update_cost (ALLOCNO_COLOR_DATA (allocno), hard_regno, divisor);
+
rclass = REGNO_REG_CLASS (hard_regno);
do
{
@@ -1361,9 +1366,11 @@ update_costs_from_allocno (ira_allocno_t
continue;
aclass = ALLOCNO_CLASS (another_allocno);
- if (! TEST_HARD_REG_BIT (reg_class_contents[aclass],
- hard_regno)
- || ALLOCNO_ASSIGNED_P (another_allocno))
+ if (!TEST_HARD_REG_BIT (reg_class_contents[aclass], hard_regno)
+ || (ALLOCNO_ASSIGNED_P (another_allocno)
+ /* When restoring, don't let assigned allocnos block us
+ from undoing the entire set of changes. */
+ && decr_p))
continue;
cost = (cp->second == allocno
@@ -1384,15 +1391,16 @@ update_costs_from_allocno (ira_allocno_t
if (update_cost == 0)
continue;
- if (! update_allocno_cost (another_allocno, hard_regno,
- update_cost, update_conflict_cost))
+ /* Update the cost, stopping at this point if that fails.
+ As above, don't stop if incrementing for restoring costs,
+ thus we want to keep going if the allocno was already
+ assigned and we're incrementing costs. */
+ if (!update_allocno_cost (another_allocno, hard_regno,
+ update_cost, update_conflict_cost)
+ && !(ALLOCNO_ASSIGNED_P (another_allocno) && !decr_p))
continue;
- queue_update_cost (another_allocno, allocno, divisor * COST_HOP_DIVISOR);
- if (record_p && ALLOCNO_COLOR_DATA (another_allocno) != NULL)
- ALLOCNO_COLOR_DATA (another_allocno)->update_cost_records
- = get_update_cost_record (hard_regno, divisor,
- ALLOCNO_COLOR_DATA (another_allocno)
- ->update_cost_records);
+ queue_update_cost (another_allocno, allocno,
+ divisor * COST_HOP_DIVISOR);
}
}
while (get_next_update_cost (&allocno, &from, &divisor));
@@ -1407,8 +1415,16 @@ update_costs_from_prefs (ira_allocno_t a
start_update_cost ();
for (pref = ALLOCNO_PREFS (allocno); pref != NULL; pref = pref->next_pref)
- update_costs_from_allocno (allocno, pref->hard_regno,
- COST_HOP_DIVISOR, true, true);
+ {
+ reg_class rclass = REGNO_REG_CLASS (pref->hard_regno);
+ reg_class aclass = ALLOCNO_CLASS (allocno);
+ machine_mode mode = ALLOCNO_MODE (allocno);
+ int cost = ira_register_move_cost[mode][rclass][aclass];
+ cost *= pref->freq * -1;
+ if (update_allocno_cost (allocno, pref->hard_regno, cost, true))
+ update_costs_from_allocno (allocno, pref->hard_regno, COST_HOP_DIVISOR,
+ true, true);
+ }
}
/* Update (decrease if DECR_P) the cost of allocnos connected to
@@ -1443,7 +1459,7 @@ restore_costs_from_copies (ira_allocno_t
start_update_cost ();
for (curr = records; curr != NULL; curr = curr->next)
update_costs_from_allocno (allocno, curr->hard_regno,
- curr->divisor, true, false);
+ curr->divisor, false, false);
free_update_cost_record_list (records);
ALLOCNO_COLOR_DATA (allocno)->update_cost_records = NULL;
}
Index: gcc/ira-conflicts.c
===================================================================
--- gcc/ira-conflicts.c (revision 233451)
+++ gcc/ira-conflicts.c (working copy)
@@ -383,6 +383,9 @@ add_insn_allocno_copies (rtx_insn *insn)
operand = recog_data.operand[i];
if (! REG_SUBREG_P (operand))
continue;
+ int adj_freq = freq;
+ if (recog_data.constraints[i][0] == '%')
+ adj_freq /= 2;
if ((n = ira_get_dup_out_num (i, alts)) >= 0)
{
bound_p[n] = true;
@@ -393,7 +396,7 @@ add_insn_allocno_copies (rtx_insn *insn)
? operand
: SUBREG_REG (operand)) != NULL_RTX)
process_regs_for_copy (operand, dup, true, NULL,
- freq);
+ adj_freq);
}
}
for (i = 0; i < recog_data.n_operands; i++)
