Re: Simple register allocation for assembly (Michael Tiomkin)
25 Jan 2003 01:09:54 -0500

          From comp.compilers

Related articles
Simple register allocation for assembly (Falk Hueffner) (2003-01-07)
Re: Simple register allocation for assembly (2003-01-12)
Re: Simple register allocation for assembly (Christian Bau) (2003-01-17)
Re: Simple register allocation for assembly (Rob Thorpe) (2003-01-17)
Re: Simple register allocation for assembly (2003-01-25)
Re: Simple register allocation for assembly (2003-01-27)
| List of all articles for this month |

From: (Michael Tiomkin)
Newsgroups: comp.compilers
Date: 25 Jan 2003 01:09:54 -0500
References: 03-01-031 03-01-074
Keywords: registers
Posted-Date: 25 Jan 2003 01:09:54 EST

Rob Thorpe <> 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

    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.