#293 A better register allocator

closed
z80 port (30)
6
2011-07-09
2010-09-05
No

The Z80 port currently uses a rather simple register allocator. While fast it is far from optimal.

An optimal register allocator should be implemented for the Z80 port. For all practically occouring programs it should run in polynomial time.

Philipp

Discussion

  • Philipp Klaus Krause

    Since this is a bigger project, I shall divide it into multiple stages and report on progress here:

    1) Prove the existence of such a register allocator (current stage).
    2) Find out how it could be integrated into sdcc
    3) First protoype implementation, minimizing spill costs, ignoring registers preferences, coalescing, etc. Assigning registers b, c, d, e only.
    4) Combine first prototype allcocator with preprocessing based on current allocator, which packs variables into hl, a and iy.
    5) Second prototype implementation, capable of handling spill cost, register preferences, coalescing, etc.
    6) Combine first prototype allcocator with preprocessing based on current allocator, which packs variables into hl, a and iy.
    7) Extend second prototype implementation to handle h, l, a and iy as well.

    With some further tweaks, this should rsult in code generation wuality on par with hand-written asm (unless prevented by problems in other parts of sdcc, such as current handling of aggregate types).

    The allocator shall be easy to adapt to other architectures common in embedded systems and be able to handle their quirks.

    Philipp

     
  • Philipp Klaus Krause

    • priority: 5 --> 6
     
  • Philipp Klaus Krause

    An early prototype has been implemented in sdcc 3.0.1 #6105 in the Z80 port.

    It is much better than the previous allocator, but not yet optimal, due to use of a simplistic cost function.

    Philipp

     
  • Bodo Wenzel

    Bodo Wenzel - 2011-01-14

    It would be nice if the allocator could be controlled which registers it uses. I'm with a bunch of fans of the cute ZX81 who like to have a better system than z88dk... And the ZX81 reserves IX, IY, and the second register set for the display system.

     
  • Philipp Klaus Krause

    The new register allocator currently only uses bc and de, the other registers are still allocated the old way.

    The second register set is not used by sdcc.
    The use of IY can be disabled by --reserve-regs-iy.
    The use of IY, can AFAIR, be disabled by --fomit-frame-pointer.

    Philipp

    Philipp

     
  • Philipp Klaus Krause

    The prototype can be found in the optralloc branch. Checkout using e.g.

    svn co https://sdcc.svn.sourceforge.net/svnroot/sdcc/branches/optralloc/sdcc sdcc-or

    It minimizes spill costs, and handles coalescing, but ignores the finer points. It assigns registers bc, de only (a, hl, ix and iy are handled the old way).

    Philipp

     
  • Philipp Klaus Krause

    • status: open --> closed
     
  • Philipp Klaus Krause

    The new allocator has been merged some time ago. While there is still room for improvement in speed, spillocation compaction and honoring of the register keyword most of the work is done.

    Philipp

     

Log in to post a comment.

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks