by This articles discusses Register Allocation by Graph Coloration which is a very important topic in Computer Science. We would begin the discussion by considering Memory Hierarchy Management.
Memory Hierarchy Managment
Programs in the Computer are written as if there are only two kinds of memory namely:
- Main Memory
- Disk
The computer programmer is responsible for data transfer between the disk and the memory (e.g file I/O)
The hardware is responsible for moving data between memory and cache
The Compiler is responsible for moving data between the memory and the registers and that is what register allocation is concerned with
Trends in Memory Management Hierarchy
Cache and register sizes are growing slowly
Processor speed improves faster than memory speed and disk speed
The Cost of cache miss continuously growing
The widening gap is bridged with more cache
Therefore it is very important to:
Manage registers properly
Manage caches properly
While the computer hardware manages the data in the cache, compilers are good at managing registers and there is need for an efficient technique in managing registers
Overview of Register Allocation
The programmer makes use of variables (e.g. a, b, c, x1, x2 ) in writing high-level program codes. At some point in time, the compiler would have to replace this variables using registers. This happens in the code-generation phase of the compilation process
While the programmer does not have a limit to the number of variables he can use, the hardware on the other hand have a limited amount of memory. So the challenge is how limited number of registers in the CPU can be allocated to indefinite number of variables used by the programmer.
Register Allocation process handles this and is the process of determining which values should be placed into which registers and at what times during the execution of the program.
Register Allocation Techniques
There have been a number of techniques developed to perform register allocation at a variety of levels. Four of these techniques are examined in this section, namely:
Local Register Allocation
Global Register Allocation
Inter procedural Register Allocation
Allocation by Graph Coloration
Local Register Allocation: This technique refers to allocation within a very small piece of code, typically a basic block. Outside the block, the register can be reused for other variables
Global Register Allocation: This technique assigns registers within an entire function and the register remains active throughout the life of the program or procedure
Interprocedural Register Allocation: This technique assigns registers across function calls and module boundaries.
The first two techniques are commonplace, with global register allocation implemented most times in every production compiler with inter procedural register allocation is rarely used in modern compilers.
But the technique we would discuss is Register Allocation by Graph Coloration
How Register Allocation By Graph Coloration Works
Register allocation by graph coloration technique was first used the a computer scientist named G.J. Chaitin and his colleagues around 1980. This was while he was working in the PL-8 Compiler for IBM-801 RISK prototype.
But before then in 1971, the technique has already been proposed by another Computer Scientist named John Cocke. He outlined that there is a close relationship between register allocation and mathematical problem of graph coloring. Today almost every commercial compiler uses graph coloring for global register allocation.
When formulated as a coloring problem, each node in the graph represents the live range of a particular value. A live range is defined as a write to a register followed by all the uses of that register until the next write. An edge between two nodes indicates that those two live ranges interfere with each other because their lifetimes overlap.
In other words, they are both simultaneously active at some point in time, so they must be assigned to different registers.
The resulting graph is thus called Register Interference Graph
Example of Register Allocation by Graph Coloration in Part 2
