Back to wiki

RCS History

/ TOP / internals / register_allocator.mdwn

Revision 1.1

The problem was that the register allocator ran too many loops over a function while trying to allocate registers for the temporaries.  In theory it should never need to loop over it more that three times, but in reality it may need to do it more times.  I have set a limit of 20, that should be sufficient.

Consider a parse tree like this:

       /   \
      /     \3
    MEM    PLUS
          /  \
        1/    \2
       TREE   TREE

Three temporary registers, 1, 2 and 3 are allocated to evaluate this tree.

Fix 1)  Assume that PLUS generates a 2-op instruction (add to left) and after Sethi-Ullman the left subtree would be evaluated first, then an implicit move 1 -> 3 would be generated before the right subtree is evaluated, causing all interference edges to be against 3.  Then if the register allocator finds
out that 3 must be spilled, the instruction generator would only find out that a new "3" were needed and hence no improvement.  The fix is to spill subtree 1 instead in this case.

Fix 2)  If the subtree below 1 is only a memory reference, the spill selection code might spill 1 which has a very short live-range and has to be replaced by a similar instruction, given no improvement of colorability.  The fix was to avoid these short-range instructions if possible.

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.

Powered by rcshistory.cgi 0.3