RFA: Tweak traversal order when updating IRA copy costs

[Richard Sandiford <rdsandiford at googlemail dot com>]

To summarise the current situtation: when allocno A has been allocated,
update_copy_costs visits each allocno reachable from A in the copy graph.
It handles each reachable allocno once.  When handling an allocno that
has been reached by a copy path of length N, it divides the copy cost
by COST_HOP_DIVISOR**N.

That all seems reasonable enough.  However, update_copy_costs uses
a _depth-first_ traversal.  This means that, if there are copy paths
of two different lengths connecting A and A', we can't be sure which
path length will be used when updating the costs relating to A'.

I think it makes more sense to use a breath-first traversal, so that
we always use the shortest path.  This isn't going to make a big
difference to performance, but it should make the results a little
more predictable.  I'm essentially asking for this to be accepted
on those grounds.

Also, update_copy_costs_1 has the following code:

      ira_allocate_and_set_or_copy_costs
	(&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno), cover_class,
	 ALLOCNO_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),
	 cover_class, 0,
	 ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
      update_cost = cp->freq * cost / divisor;
      ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno)[i] += update_cost;
      ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno)[i]
	+= update_cost;
      if (update_cost != 0)
	update_copy_costs_1 (another_allocno, hard_regno,
			     decr_p, divisor * 4);

It seemed more natural to guard all this code with update_cost != 0,
rather than just the recursive call (or, after the patch, queueing).

I don't have access to SPEC, but I tried running CSiBE at -Os on
x86_64-linux-gnu and saw a very small reduction in size (49 bytes!)
Hardly significant.

Tested on x86_64-linux-gnu.  OK to install?

The full patch is a little hard to read due to reindendation,
so I've attached a -b version as well.  That makes it much clearer
what's really changing.  The patch applies on top of Vlad's fix
for PR 37333.

Richard


gcc/
	* ira-color.c (conflict_allocno_vec): Delete.
	(update_cost_queue_elem): New structure.
	(update_cost_queue): New variable.
	(update_cost_queue_tail): Likewise.
	(update_cost_queue_elems): Likewise.
	(allocno_update_cost_check): Delete.
	(initiate_cost_update): Allocate update_cost_queue_elems
	instead of allocno_update_cost_check.
	(finish_cost_update): Update the free()s accordingly.
	(start_update_cost): New function.
	(queue_update_cost): Likewise.
	(get_next_update_cost): Likewise.
	(update_copy_costs_1): Inline into...
	(update_copy_costs): ...here.  Use a queue instead of recursive calls.
	Use cover_class instead of ALLOCNO_COVER_CLASS (another_allocno),
	once we've established they are equal.  Don't allocate update
	costs if there is nothing to add to them.
	(update_conflict_hard_regno_costs): Remove ALLOCNO and
	DIVISOR arguments.  Use a queue instead of recursive calls;
	process all the allocnos in the initial queue, rather than
	a single allocno.
	(assign_hard_reg): Use queue_update_cost instead of
	conflict_allocno_vec.  Queue coalesced allocnos instead
	of calling update_conflict_hard_regno_costs for each one.
	Just call update_conflict_hard_regno_costs once for the
	entire queue.
	(ira_color): Remove conflict_allocno_vec handling.

Attachment: bfs-update-cost.diff
Description: Text document

Attachment: bfs-update-cost-b.diff
Description: Text document