11.6.2 Register Allocation Schemes

A good code generator will generate code that minimizes accesses to main memory; it will try to keep as much currently active data (values of variables and expressions) in registers as possible.

There are two general approaches to register allocation. The first divides the registers to be allocated into two classes. The first class is those globally allocated: those to be allocated for the whole program or for a whole subprogram or perhaps a loop, and the second class is those used for temporary values and computations within a straight-line (no branches from IF's or loops) sequence of code.

The second method is to do all allocation on a global basis, without dividing the registers into two classes.

Simple global register allocation allocates registers for variables in inner loops first since that is generally where a program spends a lot of its time. Of course, this same register should be used for the variables if it also appears in an outer loop. After registers have been allocated globally, at least one (and often more) register is kept free for holding temporary results.