Re: IRA improvements 1/4

[Vladimir Makarov <vmakarov@redhat.com>]

  On 08/03/2010 01:00 PM, Jeff Law wrote:
>  On 07/07/10 07:31, Vladimir Makarov wrote:
>>
>>  The code for new trivial colorability test is still fast but it
>> slower than the previous one.  Code for cost calculation needs to
>> process more classes too (like FLOAT_INT_REGS).  That slows down RA
>> significantly because the test and cost calculation are critical parts
>> of IRA.  A lot of work was done to speed up other parts of IRA to
>> compensate this slow down.  The subsequent patches are devoted to
>> speeding other parts of IRA.
>>
>>
> A few more comments:
>
> Overall it looks reasonable -- I'm going to largely trust you on the 
> algorithmic & implementation issues since you know IRA better than 
> anyone else.   I haven't looked, but you probably should be listed as 
> the RA maintainer.
>
> I don't recall anything which describes the forest of allocno hard regs.
>
The general IRA overview is described at the top of ira.c.  There is a 
description of forest of allocno hard regs in a paragraph about allocno 
classes.
> In setup_allocno_and_important_classes you have this code:
>
> +      else if (i == GENERAL_REGS)
> +    /* Prefer general regs.  For i386 example, it means that
> +       we prefer GENERAL_REGS over INDEX_REGS or LEGACY_REGS
> +       (all of them consists of the same available hard
> +       registers).  */
> +    classes[j] = (enum reg_class) i;
>
> Do we really want to treat GENERAL_REGS special here?  ISTM we need 
> some kind of rule for which register class to select when presented 
> with multiple register classes with the same effective contents.  Even 
> if it doesn't make any changes in the generated code, it does affect 
> dumps.
>
GENERAL_REGS is already special register class and every target has it.  
The problem is in that target specific code for move/ld/st costs are 
usually defined for GENERAL_REGS and sometimes overlooked for other 
register classes.  What I added is probably the simplest solution.

The problem could be solved if every target specific code returns right 
costs for every possible (combination of) register classes.  Another 
solution would be yours.  I'll figure out what should be done for your 
proposal.  But in any case, I'd like to do it after the patch goes to 
the trunk.
> I don't understand why improve_allocation is necessary -- shouldn't 
> the overall algorithm already be attempting to reduce the overall 
> allocation cost?  If not a more concrete description of the situations 
> this function improves would really help.
>
IRA uses heuristic algorithms.  It is just additional heuristic to 
improve RA.  As one example when it improves the code (there are other 
situations too), let us consider such situation

...
push A1 as potential spilling
...
push A2 as potential spilling
...

pop A2 and assign hard reg (optimistic coloring)
...
pop A1 and assign memory because no available hard regs
...

A1 conflicts with more other allocnos therefore has lower priority but 
its cost (of memory usage) is bigger A2 one.  Improve_allocation can 
spill A2 in some situations and assign its register to A1 improving the 
overall allocation cost.

> I'd like to see the compile-time improvements as well as hunks I 
> identified yesterday go in first, then another looksie at the removal 
> of cover-class patch.  If that's going to create a huge amount of work 
> for you, let me know and we'll look at other ways to stage in the 
> changes.
>
>
I am still in process of the resolution of conflicts with Bernd's and 
Richard Sandiford's patches.  All your proposed changes (as other people 
who wrote me) will be added to the branch after that and I'll resubmit 
the patches again after that.

Thanks for reviewing my code, Jeff.  It is really helpful.