--- internals/register_allocator.mdwn 2007/09/27 17:55:09 1.1 +++ internals/register_allocator.mdwn 2007/09/27 18:03:29 1.2 @@ -20,3 +20,49 @@ Both these scenarios only occurred if there were very few registers available, in the i386 case when dealing with long longs. Because there are only 6 registers and I treat them as 3 concatenated registers, if there is also a function call involved (claiming three regs) only 1 1/2 register is left. That's why newfs/dumplfs failed to compile. +# COLORMAP + +The COLORMAP is one of the more central parts of the register allocator. +Its purpose is to tell whether a temporary is trivially colorable or not. + +A "traditional" graph-coloring register allocator can only handle one +register class. Its colorability is checked by "degree < K", which means that it +should have fewer than K registers live at the same time. K is the +total number of registers available. + +When I expanded the allocator to handle multiple register classes, one of +the things were to check the colorability by finding out the "worst-case" +affecting the temporary, when taking in account all neighbors classes. + +Here is some examples of the x86 implementation: + +There are: + + 6 16/32-bit registers (CLASSA) + 8 8-bit regs (CLASSB) + 8 floating regs and (CLASSD) + 15 64-bit regs (!). (CLASSC) + Those are handled as pairs of 32-bit regs. + +So, for CLASSA the check looks like this: + + case CLASSA: + num = r[CLASSB] > 4 ? 4 : r[CLASSB]; + num += 2*r[CLASSC]; + num += r[CLASSA]; + return num < 6; + +It means that there can be max 5 CLASSA neighbors, 2 CLASSC neighbors or +an infinite number of CLASSB regs if all neighbors are of CLASSB. +Then they are just added to see the total number. + +The CLASSB stuff is because even if all 8-bit regs are used edi/esi will +still be available. + +So, if we are guaranteed to have a free register, return true, otherwise +false. + +The colormap could be an auto-generated array of size NCLASS, but I +haven't written the code to generate it yet. The information is +available in the ROVERLAP macro in macdefs, which tells which registers +overlap with each other. \ No newline at end of file
Powered by rcshistory.cgi 0.3