Re: Simple register allocation for assembly

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

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