Register Allocation and Assignment

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 10^depth 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 B_iis 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

                                10^depth.∑_{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

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.