RE: Understanding IRA

["Ian Bolton" <bolton@IceraSemi.com>]

Yesterday, I wrote:
> BTW, today I have achieved some good results with existing IRA by doing
> the following:
> 
> 1) Changed the REG_ALLOC_ORDER so that TOP_CREGS are given out before
> BOTTOM_REGS.  My previous hacked version worked by increasing the
> priority of those that wanted BOTTOM_REGS, so they got first pick; this
> new version makes them wait their turn, but ensures those with higher
> priority take TOP_CREGS before BOTTOM_REGS.
> 
> The analogy, I think, is of giving out meals on an airplane.  Most
> people will eat meat or vegetarian meals, whereas vegetarians only
> want vegetarian meals.  My hacked version was effectively allowing
> the vegetarians to push to the front of the queue and get their meals;
> this new version works by encouraging the meat eaters to eat the meaty
> meals first, leaving more suitable meals for the vegetarians further
> down the plane.
> 
> 2) I have forced propagation of allocnos to parent regions with the
> following hack in find_allocno_class_costs():
> 
> {
>   /* Propagate costs to upper levels in the region
>      tree.  */
>   parent_a_num = ALLOCNO_NUM (parent_a);
>   for (k = 0; k < cost_classes_num; k++)
>     COSTS_OF_ALLOCNO (total_costs, parent_a_num)->cost[k]
>       += COSTS_OF_ALLOCNO (total_costs, a_num)->cost[k];
>   COSTS_OF_ALLOCNO (total_costs, parent_a_num)->mem_cost
>     += COSTS_OF_ALLOCNO (total_costs, a_num)->mem_cost;
>   /* BEGIN IGB-IRA CHANGE 2 */
>   /* Force total_costs to propagate upwards, by setting
>      allocno_costs to be total_costs */
>   for (k = 0; k < cost_classes_num; k++)
>     COSTS_OF_ALLOCNO (allocno_costs, parent_a_num)->cost[k]
>       = COSTS_OF_ALLOCNO (total_costs, parent_a_num)->cost[k];
>     COSTS_OF_ALLOCNO (allocno_costs, parent_a_num)->mem_cost
>       = COSTS_OF_ALLOCNO (total_costs, parent_a_num)->mem_cost;
>   /* END IGB-IRA CHANGE 2 */
> }
> 
> I don't know why propagation isn't happening normally, but
> this total_costs hack achieves the same thing for me at the
> moment.  Is there any information I could provide to help
> someone tell me why propagation isn't happening?

Good news!  I have been able to remove my "total_costs" hack
above by instead commenting out the following line from ira_build()
in ira-build.c:

  remove_unnecessary_regions (false);

For my situation at least, this function is preventing the
propagation of useful allocno information from region 1 to
region 0.  Without my change, the allocation for a pseudo in
region 0 is not aware of how that pseudo will be used inside
a loop in region 1; the real impact of this is that we need
to then do a register move *inside the loop* into a valid
register class for the instruction in region 1.

I do not believe this will impact anyone with a regular
register set, but for any architecture where some instructions
can only use a subset of the register bank, I believe that
all regions are always necessary, since cost information
for each allocno is relevant and important.

I still need to do some more testing in regards this "fix",
but I wanted to put my findings out there as soon as possible
for comment from the experts.