This is the mail archive of the
mailing list for the GCC project.
Re: IRA improvements 1/4
- From: Jeff Law <law at redhat dot com>
- To: Vladimir Makarov <vmakarov at redhat dot com>
- Cc: gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Mon, 02 Aug 2010 13:21:56 -0600
- Subject: Re: IRA improvements 1/4
- References: <4C34819D.email@example.com>
On 07/07/10 07:31, Vladimir Makarov wrote:
I'm not through the entire patch, but thought I'd go ahead and pass
along a few questions/comments.
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
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 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...