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]



Thanks for for the explanation.


Paulo Matos

On 23/03/12 16:08, Vladimir Makarov wrote:
On 03/23/2012 11:04 AM, Paulo J. Matos wrote:

I am trying to find exactly what happened to IRA_COVER_CLASSES in
gcc47. From what I have seen it seems that it was simply removed. Does
the register allocator now automatically computes the cover classes?

No. Before gcc4.7 we use coloring on non-intersected classes (so called
cover classes). That was a classical approach with well known
disadvantages for irregular register class architectures.

Since 4.7 we use more sophisticated trivial coloring criteria which work
well even on intersected register classes. To be more accurate, we
calculate an approximation of an profitable hard regs for each pseudo.
These approximations form a tree. The tree is used for find trivial
colorability of the pseudos. It was a surprise that such approach is
profitable even for architectures with regular register files like ppc.
Here is an excerpt from comments on the top ira.c file:

We also use a modification of Chaitin-Briggs algorithm which works for intersected register classes of allocnos. To figure out trivial colorability of allocnos, the mentioned above tree of hard register sets is used. To get an idea how the algorithm works in i386 example, let us consider an allocno to which any general hard register can be assigned. If the allocno conflicts with eight allocnos to which only EAX register can be assigned, given allocno is still trivially colorable because all conflicting allocnos might be assigned only to EAX and all other general hard registers are still free.

To get an idea of the used trivial colorability criterion, it
is also useful to read article "Graph-Coloring Register
Allocation for Irregular Architectures" by Michael D. Smith
and Glen Holloway. Major difference between the article
approach and approach used in IRA is that Smith's approach
takes register classes only from machine description and IRA
calculate register classes from intermediate code too
(e.g. an explicit usage of hard registers in RTL code for
parameter passing can result in creation of additional
register classes which contain or exclude the hard
registers). That makes IRA approach useful for improving
coloring even for architectures with regular register files
and in fact some benchmarking shows the improvement for
regular class architectures is even bigger than for irregular
ones. Another difference is that Smith's approach chooses
intersection of classes of all insn operands in which a given
pseudo occurs. IRA can use bigger classes if it is still
more profitable than memory usage.


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