Re: IRA improvements 1/4

[Vladimir Makarov <vmakarov@redhat.com>]

  On 08/02/2010 03:21 PM, Jeff Law wrote:
>  On 07/07/10 07:31, Vladimir Makarov wrote:
>>  This patch removes cover classes.  The cover classes were introduced
>> because classical graph coloring algorithms work on on intersected
>> registers classes.  As our experience shows defining cover classes can
>> create a lot of performance problems for some targets and as
>> consequence few targets have to use less powerful priority coloring
>> algorithm instead of Preston-Briggs graph coloring algorithm.
>>
>>  So removing cover classes makes GCC more portable.  But the major
>> idea for the patch is to not only make GCC profitable but to improve
>> performance too.
>>
>>  Irregular register file architectures (like x86) force to use
>> smaller register classes (not just GENERAL_REGS) because other
>> registers might be not profitable.  Taking this requirement into
>> account in more adequate way (than just available register number)
>> could improve quality of graph coloring RA.  Regular register file
>> architectures also need this because some registers are not available
>> in some parts of the code (e.g. registers used for argument passing)
>> or not profitable (e.g. call clobbered registers).
>>
>>  The patch makes graph coloring works on dynamically calculated classes
>> (which is just a hard reg set) of registers profitable for given
>> allocno.  More correctly, the approximation of such classes used which
>> forms a tree of such classes.  Here is a simple x86 example to get the
>> idea of the change.  Let pseudo P conflicts with 7 other pseudos
>> P1-P7.  P and P7 can use any general register (it means that they are
>> profitable too), P1-P6 can use only AX.  In the old version of IRA P is
>> not trivially colorable.  With this patch, P is trivially colorable
>> because the algorithm can easily figure out that the impact of P1-P6
>> on P is just 1 registers (not 6 as IRA before the patch).
>>
>>  The patch also permits to use registers from different old cover
>> classes.  For example, if we have pseudo which is only used for moving
>> value from one memory location to another one, we could use general or
>> floating point registers on most architectures.  In the previous
>> version of IRA, only general registers were used for such case because
>> general and floating registers usually belonged to different cover
>> classes.
>>
>>  The patch removes -fira-coalesce because it is really hard to
>> implement it with the new dynamically calculated allocno classes.
>> The patch uses also new spilling algorithms because of the same reason.
>> Removing -fira-coalesce is not a big deal because it is not used and
>> its most functionality is implemented by IRA preferencing technique.
>>
>>  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.
>>
>> Is the patch ok to commit the patch to the trunk?
>>
> I'm not through the entire patch, but thought I'd go ahead and pass 
> along a few questions/comments.
>
>
> I notice that you removed the splay tree code in push_allocno_to_stack 
> and friends, presumably the compile-time problems we had when there 
> was a huge number of uncolorable allocnos isn't a problem anymore?
>
Yes, there will be no problem with a huge number of uncolorable 
allocnos.  Spilling priorities will be static.  Allocnos will be 
reordered just once.
> In allocnos_have_intersected_live_ranges_p, if the two allocnos are 
> the same you return false.  Shouldn't it return true?
>
No.  This name (and pseudos_have_intersected_live_ranges_p) has a 
misleading name.  It probably should be called as 
allocnos_conflict_by_live_ranges_p.  I'll change the names.
> You might consider submitting removal of -fira-coalesce and the CB 
> coloring support separately.  The former is clearly on its way out and 
> I believe the latter out to be as well.
>
Ok.
> ira_remove_allocno_copy_from_list can probably be eliminated as a 
> separate patch as I don't think it's used at all on the trunk.
>
Ok.  I overlooked to remove the function when I rewrote IRA IR 
flattening for gcc 4.4.  Since then it is not used.