Back to wiki

RCS History

/ TOP / internals / register_allocator.mdwn

Differences for revision 1.2 from 1.1


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