Understanding IRA

[Vladimir Makarov]

Ian Bolton wrote:
> 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.
>   
The function (remove_unnecessary_regions) is used to increase RA speed 
by decreasing number of regions.  The region is removed if the register 
pressure is not high in the region in other words if the probability to 
spill pseudos on the region border to improve RA in the region is small.

But when the region is removed and correspondingly allocnos (see 
function remove_unecessary_allocnos) in the region the info including 
hard register costs is propagated to the  corresponding allocnos in the 
parent region (see function propagate_some_info_from_allocno).

I've just checked the code it looks ok to me.  Ian, it would be nice if 
you figure out why the propagation does not happen.   As Jeff wrote, 
fixing that would be important practically for any target.