Optimal Linear Time Colouring for Register Allocation within Static-Single-Assignment Programs
Navid Azizi
register forElectrical and Computer Engineering
University of Toronto
Problem
Prove or Disprove:
For any static-single-assignment (SSA) program, the interference graph for register allocation can be coloured optimally in linear time.
1  Introduction
This paper prooves that for SSA programs the interference graph can be coloured optimally in linear time.  The proof will proceed as follows: Section 2 presents some properties of SSA graphs, and the  operation’s effect on creating the interference graph.  Section 3 will show that &
the interference graph for SSA programs are chordal graphs.  Section 4 will present an algorithm that can colour chordal graphs in linear time.  Section 5 will conclude the paper by using the results of section 3 and 4 to show that SSA programs can be colored optimally in linear time.
2  SSA Program and  Operation Properties
&
SSA programs have the property that no variable may be assigned more than once in the static code.  This property ensures, in straight line code, that the liveness of a variable is not disjoint; stated in another way that once a variable leaves the live-set it can never return to it.
Theorem 2.1In SSA code during the creation of the interference graph, once a variable i is removed from the live-set it can never reenter the live-set again, unless during the period which i is not present, all variables j that enter the live-set, exit the live-set before the live-set includes all variables that were in the live-set when i was last in the live-set.
Proof: In straight-line SSA code each variable can be assigned at most once.  When a variable is removed from the live-set the only assignment for that variable has been reached.  For a variable to r
eenter the live-set it must be used as a source of an instruction previous to the instruction that is currently being evaluated.  Since the code is assumed to be valid, the variable must be initialized previous to it’s use, but that implies a second assignment which cannot occur in SSA form.
Before Theorem 2.1 can be proved further for loops and branches, some properties of the
live-analysis and  operation will be presented.
&
When the live-analysis goes through basic blocks, the live-set entering the basic block is the union of all live-sets of its successor blocks.  For loops within the code, which have a successor whose live-set has not been calculated, the live-set analysis has to be performed twice to be sure that all variables have been initialized correctly.  Note, however, that the interference graph is only updated through the second pass of the live-set analysis.
While this method will correctly create the interference graph for normal programs, special
&&
provisions have to be taken for the  operation in SSA programs.  The  operation has the following properties:
&
1.All  operations within a block occur at the beginning of the block
&
2.All  operations within a block occur in tandem
&
3.The sources of the  operation are mutually exclusive (i.e. only one can be live at a
time)
These properties allow the following statements to be made:
&
1.The sources of a particular  operation can not have an interference edge between them
in the graph.  This is because the sources are mutually exclusive and come from
different control branches.
&
2.The live-analysis through the  operations in a block cannot be the cause of
&& interference edges between the targets of  operations and sources of all  operations
&
within the same block.  This is because all  operations occur in tandem and the target &&
of the  operations become live, while the sources of the  operations die at the same
moment.
&
A further consequence of using the  operation is that second step of the live-analysis (add the source
s of the instruction into the live-set) cannot be performed blindly.  The presence of the  & operation indicates that there is a merge point and that there are many predecessors to a block. Therefore different live-sets have to be kept for each predecessor, with only one of the sources &
from the  operation existing in each live-set.  Take as an example the scenario in Figure 1; The initial live-set for block 1 will include A1 and B1, but not A2 or B2, and the live-set for block 2 will include A2 and B2, but not A1 or B1.
For loops special consideration has to be also taken when creating the live-sets.  During the first
&
pass through the loop the live-set is created by only adding sources of the  operation to the
live-set, which were created during the loop.  On the second pass through the loop, only sources &
of the  operation which were created outside the loop are added.
This last proviso, ensures the same property of straight-line SSA code, that during the
live-analysis of the code when the interference graph is being updated, when a variable leaves the live-set, it can never reenter thus showing Theorem 2.1 is true for loops.
It will now be shown that Theorem 2.1 is true for branches.  The live-set analysis of branch blocks does not occur simultaneously, but sequentially.  For example, in Figure 1, block 1 would be analyzed before block 2. Because of this lack of concurrency, which is implicit in the program execution, the properties of the live-set in SSA programs during branches must be looked at more closely.
If a variable is assigned during one of the branch blocks then it can not be live outside of the
&
branch block.  This is because there will definitely be a  instruction to merge the different values of the variable back together.  Thus Theorem 2.1 is still true for this case.  For local variables used within each block of a branch statement it appears as if they are within
straight-line code and Theorem 2.1 is valid for them as well.  For variables that are live through the branch (i.e. they are live before and after the branch) the branch appears as straight-line code in terms of the live-set, and again Theorem 2.1 holds.
The final case is when a variable is live before the branch, and then dies in all paths before the program merges.  In this case, because the branch blocks are performed sequentially, it seams that the variable is removed from the live-set, and then reenters, and thus the first portion of Theorem 2.1 does not hold, but now the second portion holds.  The interval for which a variable i exits the live-set and reenters it, is the time when a subsequent branch block has started to be analyzed before i is used in that block.  During this time the only variables that can enter the
live-set are local variables to that branch block, and they all leave at the end of the branch block, before the live-set is unioned with the live-set from all other branch blocks thus including all variables that where in the live-set when i was last in the live-set, thus proving Theorem 2.1.»3  Interference Graph for SSA Programs is Chordal
In this section it will be proved that SSA programs have chordal interference graphs.  The proof is organized as follows: first it will be proved that the during the construction of the interference graph, every node that is added is simplicial.  It will then be proved that the complete interference graph has a simplicial elimination ordering, and finally that the graph is chordal. First a couple definitions:
Definition 3.1A graph is said to be chordal if every cycle with more than three edges possesses
a chord, an edge joining two nonconsecutive vertices in the cycle.  A chordal graph is also
said to be triangulated.  For a graph to be non-chordal, there must exist at least one cycle of
4 nodes or more where there are no chords.
Definition 3.2A vertex of G is simplicial if its neighborhood in G induces a clique.
Definition 3.3A simplicial elimination ordering is an ordering v n,...,v1 for deletion of vertices so that each vertex v i is a simplicial vertex of the remaining graph.
For the proof to be completed a couple lemmas are needed:
Lemma 3.4 Edges between two nodes exists iff both nodes where in the live-set concurrently at one time.
Proof: For an edge to exist in an interference graph the adjacent nodes must interfere with each other.  For nodes to interfere in register allocation they must not be able to share the same register, and thus be live concurrently for at least one moment.  Thus they must be in the live-set together at one moment.Furthermore, if two nodes are in the live-set together they interfere with each other and thus have an edge between them.»
Lemma 3.5Vertices which are in the live-set together at any time in the live-set analysis form a clique in the interference graph.
Proof: Variables that are in a live-set together are all live and must all exist at the same time. Therefore no pair within the live-set can share a register, and therefore every pair within the
live-set must have an edge between them inducing a clique.»
Lemma 3.6If a variable leaves the live-set and never returns, it’s degree cannot change after it leaves the live set.
Proof: By Lemma 3.4 edges are only created by nodes which are in the live-set at the same time. If a variable leaves and never returns to the live-set there are no more possibilities for it to gain edges, and thus its degree remains constant after it leaves the live-set.  »
Lemma 3.7When a node is added to the live-set, it is simplicial.
Proof:  When a node enters the live-set it an edge is added between itself and every other node in the live-set.  Furthermore by Lemma 3.5 are vertices in the live-set form a clique.  Therefore by adding a node to the live-set that node forms a clique with all it’s neighbors and is thus simplicial.»
Given the above lemmas, we will now prove that that the interference graph of an SSA program has a simplicial elimination ordering.
Theorem 3.8The interference graph of an SSA program, that does not contain branches, has a simplicial elimination ordering.
Proof:  Given that by Lemma 3.7 a node is simplicial when it is added to the live-set and by Theorem 2.1 and Lemma 3.6 that a variable from an SSA program, which has no branches, cannot have anything connect to it once it leaves the live-set, then the reverse ordering of nodes entering the live-
set is the simplicial elimination ordering.  Specifically, Theorem 2.1 and Lemma 3.6 show that new edges cannot be created thus disallowing edges that would make a node non-simplicial if the nodes that enter the live-set after it, are removed from the interference graph (by the reverse ordering obtained). »
Lemma 3.9The exit and reentry of nodes in the live-set because of branches in SSA code do not disturb the simplicial ordering.
Proof: By Theorem 3.8 it has been shown that an SSA program without branches has a simplcial ordering.  By Theorem 2.1 variables j that enter the live-set ,during the interval of disjointness of liveness in another variable i, must leave the live set before the live-set becomes a superset of the original live-set when i left.  Because of this, the edges created by j do not cause the simplicialness of i to be removed, because all nodes in j, and accompanying edges, will be removed previous to i being removed since they were added to the live-set after i. (In easier
words, all edges connected to a variable making it non simplicial will be removed before it is reached in the order thus making it simplicial again).»
Theorem 3.9 An SSA program has a chordal interference graph.
Proof:Since the interference graph of an SSA program has a simplicial elimination ordering by Theorem 3.8 and Lemma 3.9 and it is shown in [1] that “A simple graph has a simplicial elimination ordering if and only if it is a chordal graph,” then the interference graph of an SSA program must be chordal.»
4  Optimal Coloring for Chordal Graphs in Linear Time
This section will show that chordal graphs can be colored in linear time.  The proof will start
O(V+E)
with two algorithms that compute the perfect elimination ordering in .  It is then
O(V+E)
showed that a greedy algorithm runs in  .  Finally it is shown than the perfect elimination ordering given to the greedy algorithm performs the coloring optimally.
In [2] the following two algorithms are given that find the perfect elimination ordering in a O(V+E)
chordal graph in  time.
Maximum Cardinality Search
For i = 1,...,n
"
Let v i be the vertex such that v i{v1,v2,...,v i-1} and
v i has the most neighbors in {v1,v2,...,v i-1}
Lexicographical BFS
For i = n,...,1
"
Let v i be the vertex such that vi{v n,v n-1,...v i+1} and
v i has the lexicographically largest label L(v i)
For all neighbors v of v i, set L(v) = L(v)i)
A greedy algorithm for coloring is the following VERTEX_COLOR which can be found in [3]: VERTEX_COLOR(G(V,E)) {
V
For (i=1 to ) {
c = 1;
¤
while ( a vertex adjacent to v i with color c ) do {
c = c + 1;
}
Label v i with color c;
}
}
Finally in [4] it is presented that such a greedy algorithm with a perfect elimination ordering provides the optimal coloring.  Thus it has been proved that chordal graphs can be colored optimally in linear time. »
5 Conclusion
Given the results from section 3, and specifically Theorem 3.10, that shows that SSA programs have chordal interference graphs and the results from section 4 that shows that chordal graphs have perfect elimination orderings, which can be found in linear time, that provide optimal colorings, then we have that SSA programs can be colored in optimally in linear time.
One could also recognize that the simplicial orderings that SSA programs have, and shown in Theorem 3.9, are perfect elimination orderings and thus can be used to color the graph optimally given the proof from [4].  The simplicial ordering of the SSA would be determined by the order with which variables entered the live-set, and this can be linearly found by going through the specific SSA code. »
Bibliography
[1] D.B. West, Introduction to Graph Theory, 2nd ed., Upper Saddle River, NJ.  Prentice Hall,
2001.
[2] P. Tilker, “CS762: Graph-Theoretic Algorithms. Lecture 5: Perfect Elimination Orders,”
[Online document], 2002 Jan 16, [cited 2002 April 18], Available HTTP:
compgeo.math.uwaterloo.ca/~biedl/teach/cs762/lecture5/lecture.ps
[3] G. De Micheli,  Synthesis and Optimization of Digital Circuits, New York, McGraw-Hill,
1994.
[4] E. Dahlhaus, “Generalized strongly chordal graphs,” Technical Report, University of Sydney,
Number TR-93-458, 1993.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。