Register Allocation
The run-time performance of any program is greatly dependent on
how effectively it uses the target machine's registers. This is
because accessing a data value from a register is many times
faster than accessing it from memory. Also, certain operations
are available for register operands which are not avoilable for
memory operands.
The number of registers on a machine is fixed and hence the
problem of register allocation arises.
Unfortunately, like many other problems in the area of
compilers, the problem of optimal register allocation is an
NP-Complete problem. So the aim of research in this field is
towards devoloping heuristics. Since the step of register
allocation is very important for compilation, even an
improvement of 1 or 2% in the execution time of a program is
considered significant.
This problem can be broken down into two conceptual steps :
- Register Assignment which determines
which variables should be register resident at various program
points and where loads and stores should be placed so that the
values are available in registers. This step is performed
assuming an unlimited number of registers.
- Register Allocation which maps the
unlimited number of registers to the limited number of
registers available on the machine.