IRA improvements 1/4

[Jeff Law]

  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?

In allocnos_have_intersected_live_ranges_p, if the two allocnos are the 
same you return false.  Shouldn't it return true?

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.

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.

There'll be more...

jeff