This is the mail archive of the gcc@gcc.gnu.org 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_COVER_CLASSES In gcc47


On 03/23/2012 11:04 AM, Paulo J. Matos wrote:
Hello,

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]