Re: Simple register allocation for assembly

tmk@netvision.net.il (Michael Tiomkin)
25 Jan 2003 01:09:54 -0500

          From comp.compilers

Related articles
Simple register allocation for assembly falk.hueffner@student.uni-tuebingen.de (Falk Hueffner) (2003-01-07)
Re: Simple register allocation for assembly journeyman@compilerguru.com (2003-01-12)
Re: Simple register allocation for assembly christian.bau@cbau.freeserve.co.uk (Christian Bau) (2003-01-17)
Re: Simple register allocation for assembly robert.thorpe@antenova.com (Rob Thorpe) (2003-01-17)
Re: Simple register allocation for assembly tmk@netvision.net.il (2003-01-25)
Re: Simple register allocation for assembly housel@cox.net (2003-01-27)
| List of all articles for this month |

From: tmk@netvision.net.il (Michael Tiomkin)
Newsgroups: comp.compilers
Date: 25 Jan 2003 01:09:54 -0500
Organization: http://groups.google.com/
References: 03-01-031 03-01-074
Keywords: registers
Posted-Date: 25 Jan 2003 01:09:54 EST

Rob Thorpe <robert.thorpe@antenova.com> wrote in message news:03-01-074...
  ....
> If you want an algorithm with no spilling you will have to deal with
> live ranges, there is no other way. Since spills will abort this is
> quite simple on a basic-block basis.
> 1. Calculate live ranges.


    Well, for assembler it's a bit more complicated than for a higher
kevel language. You need some established calling conventions -
live/dead registers on entry/exit from a function and during function
calls, and branch targets for every branch instruction where the
target is in a register. Recall that an assembler program can easily
have multiple entries, be an interrupt handler etc. etc.


    In a register allocator that I did 4 years ago I used annotations in
assembler (#pragma-like statements) in order to pass this information
to allocator.


    Another problem: when a live range contains a function call, you
cannot assign a scratch reg to its virtual register. You can spill a
saved register on entry and restore it on exit, and use it for
allocations, or you can spill/restore a scratch reg before/after a
call.


    Don't be afraid to spill/restore, you can just declare the spill
area on the stack and pass this info to assembler, using trial and
error to determine the size.


> 2. Starting at the beginning give the first variables register if there
> are enough.
> 3. Keep a note of used and unused registers, when a range ends return a
> register to the pool.
> 4. Whenever a new range begins allocate a spare register to it. If you
> run out abort.
>
> The elaborate parts of real allocators are in deciding where to spill.
>
> BTW There maybe problems with either of the above, I haven't checked them.


    Recently I was told that IBM's patent on register coloring had
expired, so you can easily use register coloring instead this first
come first allocated method.


    Good luck!


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.