What is Register Allocation?
Register
allocation deals with various strategies for deciding what values in a program
should reside in registers
Why is Register Allocation Important?
Generally, the
instructions involving only register operands are faster than those involving
memory operands. So, efficient utilization of available registers is important
in generating good code, and register allocation plays a vital role in
optimization.
When is Register Allocation Done?
It can be done
in intermediate language prior to the machine code generation, or it can be
done in the machine language
In the latter
case, the machine code uses symbolic names for registers, and the register
allocation turns into register numbers
Register allocation
in the intermediate language has the advantage that the same register allocator
can be used for several target machines
What are the approaches for Register Allocation?
There are two
approaches, which are
Local allocators: These are
based on usage counts
Global or intraproceduaral
allocators: These are based on the concept of graph coloring
Local Allocators:
These allocators
weigh inner loops more heavily than outer ones, and are heavier than code not
contained in loops, basing on the principle that most programs spend most of
their time executing loops
The idea is to
determine the allocation benefits of various allocatable quantities
The allocation
benefit is generally estimated by multiplying the savings that result from
allocating a variable to a register by a factor based on its loop nesting
depth. It is usually 10depth for depth loops.
Finding allocation benefits of
allocating variable v to a register in a loop L
Before computing
the benefit, the following quantities must be defined:
ldcost – the execution time cost
of a load instruction in the target machine
stcost – the cost of a store
instruction
mvcost – the cost of a register
to register move instruction
usesave – the savings for each
use of a variable that resides in a register rather than a memory location
defsave – the saving for each
assignment to a variable that resides in a register rather than a memory
location
The net saving
in execution time for a particular variable v each time basic block Bi
is executed is netsave (v, i). It is defined as follows.
netsave (v, i) = u. usesave +
d.defsave – l.ldcost – s.stocost
Where u and d
are the number of uses and definitions of vaiable v in block i, and l and s = 0
or 1, counting whether a load of v at the beginning of the block or a store at
the end respectively, is needed
Thus, if l is a
loop and i ranges over the basic blocks
in it, then
10depth.∑i€blocks(L) netsave(v,i)
is a reasonable
estimate of the benefit of allocating variable v to a register in loop L
Overall Strategy:
These allocators
work as described below:
Let R be the number of registers
available
Compute the allocation benefits
or estimates for each loop
Allocate R objects with greatest
estimated benefit to registers in loop or loop nest
After register allocation for
the loop nests, allocation is done for code outside loops using the same
benefit measure
Global Allocators:
The idea is
based on the fact that two quantities must be in registers, and at the same
time these quantities are excluded from being in the same register
The method is
also very simple and involves two passes:
- In the first pass, the target machine instructions or
intermediate code instructions are selected as though there are infinite
number of symbolic registers
- In the second pass, for each procedure, a register inference
graph is constructed in which the nodes are symbolic registers and an edge
connects to nodes if one is live at a point where the other is defined,
i.e., if both are live at the same time
Now, an attempt
is made to color the graph using k colors, where k is the number of available
registers. We know that a graph is said to be colored if each node has been
assigned a color in such a way that no two adjacent nodes have the same color
Once the
coloring is over, register allocation can be made
Is Coloring a Graph Easy?
Determining
whether a graph is k-colorable or not is NP-complete. Generally, the following
strategy is followed to color a graph quickly:
- Step 1: if a node n in the graph has less than k neighbors, n
and its edges from the graph G are removed to obtain a graph G’
- Step 2: now if G’ is k-coloring of G’ can be extended to a
k-coloring of G by assigning n a color not assigned to any register
Step 1 &
Step 2 are repeated (if G’ is not k-colorable) using G’ as G, until
- An empty graph is obtained, in which a k-coloring of the
original graph can be produced by coloring the nodes in the reverse order
un which they were removed
- A graph in which each node has k or more adjacent node is
obtained. In this case k-coloring is not possible. At this point a node is
spilled by introducing code to store and reload the register
