Draft:Interference graph

An interference graph is an algorithm used in compiler construction that helps assign local variables to processor registers for a given instruction set architecture (ISA). It is based on the general concept known as "liveness analysis", in which the code is examined to determine which variables are "live" at any given time.

In most compiled languages, like C or Java, code is organized into blocks that perform a given function. Temporary calculations and values are stored in local variables, normally with no limit imposed on the number or their type. Blocks also optionally pass information back out of the code, the results of their internal calculations, as well as take in information from other blocks, their parameters.

Internally, central processing units (CPUs) attempt to hold these temporary values in processor registers wherever possible. These are the fastest types of computer memory to access and the overall performance of the program is strongly affected by register use. General purpose registers are generally limited to a small number, often 16 or 32 in modern processors, and even fewer in older designs like x86. As a number of these registers serve other purposes, like passing parameters or holding internal state like the stack pointer or program counter, these are a limited resource, and it may not be possible to hold all local variables in registers. Those that cannot are said to spill.

The goal of the interference graph is to examine local variable usage in the code and map their usage over time such that more than one variable can be stored in a single register as they are used at different points in the code. For instance, consider this pseudo-code that performs an increment:

   1.     a := 0
   2. L1: b := a+1
   3.     c := c+b
   4.     a := b*2
   5.     if a<10 goto L1
   6.     return c

In this example, there are three local variables, a, b and C. However, only two of these are "active" at the same time, as b is produced by a, and then a is produced by b. At no point in this code are the values of a and b needed in a single calculation. This means that a and b can both be assigned to the same processor register.

These usage patterns can become quite difficult to understand. Consider a more complex code example:

   1.     v := 1	 	 	 	 	 	 
   2.     z := v+1
   3.     x := z * v
   4.     y := x * 2	 	 
   5.     w := x+z * y	 	 
   6.     u := z+2 
   7.     v := u+w+y
   8.     return v * u

In this example, the value of x on line 3 is constructed from v and z, and z is constructed from v. Therefore, in line 3, only two different values are active, z and v. x is used to calculate the value y on line 4, and then to calculate w on line 5, and is not used after that point. Thus, x is live only for three lines, during which time the values of y and z are also being used. The value v is no longer used at this point and does not appear elsewhere in the program.

The Peterson graph is a complex example of a ten variable block with many interactions. It can be solved using three colors, indicating that only three registers would be needed to store the ten different variables.

The interference graph provides a way to store the question of which values are active at any given time and thus should be stored in registers if possible. This is accomplished by constructing a graph with the variables as the nodes and the edges connecting nodes that are active at the same time. So for the x node, it has edges to y and z. It does not have a line to v, as x is not yet assigned on line 2, and is not live.

The interference graph does not solve the register allocation by itself, it simply provides a framework to store the information. Assigning the values to registers is typically performed using Chaitin's algorithm, which uses graph coloring to assign a "color" to each of the nodes such that no directly connected nodes have the same color.

References

• "Register Allocation Using the Interference Graph". University of Texas, Arlington.
• Campanoni, Simone. "Compiler construction: Interference graph" (PDF). Northwestern University.

This page will be placed in the following categories if it is moved to the article namespace.

Categories:

• Compiler theory