This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: IRA improvements 1/4

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

 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...


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]