Draft:Interference graph
![]() | Review waiting, please be patient.
This may take 3 months or more, since drafts are reviewed in no specific order. There are 1,643 pending submissions waiting for review.
Where to get help
How to improve a draft
You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Editor resources
Reviewer tools
|
![]() | This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
|
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.
Description
[edit]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.[1]
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,[2] 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.[3]
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.[4] For instance, consider this pseudo-code that performs an increment:[5]
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.[5]
These usage patterns can become quite difficult to understand. Consider a more complex code example:[6]
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.[6]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/90/Petersen_graph_3-coloring.svg/220px-Petersen_graph_3-coloring.svg.png)
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.[7] 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.[6]
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.[8]
References
[edit]Citations
[edit]- ^ Chattopadhyay 2022, p. 144.
- ^ Chattopadhyay 2022, pp. 148–149.
- ^ Austin, p. 12.1.
- ^ Campanoni.
- ^ a b Fegaras, p. 2.
- ^ a b c Fegaras, p. 10.
- ^ Chattopadhyay 2022, p. 150.
- ^ Muchnick 1997, p. 494.
Bibliography
[edit]- Fegaras, Leonidas. "Register Allocation Using the Interference Graph" (PDF). University of Texas, Arlington.
- "Register Allocation Using the Interference Graph". 2014.
- Campanoni, Simone. "Compiler construction: Interference graph" (PDF). Northwestern University.
- Hack, Sebastian (2005). "Interference Graphs of Programs in SSA-form" (PDF). Universit ̈at Karlsruhe.
- Muchnick, Steven (1997). Advanced Compiler Design Implementation. Morgan Kaufmann. pp. 485–499.
- Chattopadhyay, Santanu (2022). "Register Interference Graph Construction". Compiler Design. PHI Learning. pp. 148–155. ISBN 978-93-91818-76-0.
This page needs additional or more specific categories. (December 2023) |