Re: Simple register allocation for assembly

Rob Thorpe <>
17 Jan 2003 20:01:17 -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: Rob Thorpe <>
Newsgroups: comp.compilers
Date: 17 Jan 2003 20:01:17 -0500
Organization: Compilers Central
References: 03-01-031
Keywords: registers
Posted-Date: 17 Jan 2003 20:01:17 EST

> There are only instructions with 0 to 3 inputs and 0 to 1 outputs,
> conditional branches, and unconditional branches. No spilling is to be
> done, if no register allocation can be done, the program should
> abort. Also, I expect very small input sizes, so resource usage is not
> very important. So at first glance this looks pretty easy, but I can't
> really come up with a simple algoritm, any hints?

The simplest register allocators give registers to the most frequently
mentioned variables. So, my suggestion is:

1. Within a given function assign a counter for every variable.
2. Increment the counter when it's used.
3. If the use is within a loop increment the counter by 10
4. If its in a loop within a loop increment by 100 etc
5. Find the variables with the highest scores and assign registers too
them. Spill the rest.

I believe something like this is used in LCC, at least in older
versions. If you can't find a way to tell what loops are ignore them
(this will of course make it a *really* bad allocator rather than just a
slightly bad allocator).

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.
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.

Post a followup to this message

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