Re: Simple register allocation for assembly

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!

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