Problem 6 - Compilation

Consider the following pseudo-code (C) and (C'), where the pseudo-code (C') is a code obtained from (C) by deleting the 5th to 7th lines. mem[x] is a data at address x of memory, call is a procedure call, ri (i=0,1,2) is a register, and other variables are temporary variables. Suppose that live variables in the beginning of the code are k and j, and live variables at the end of the code are d and j. Caller-save registers are r0, r1, r2.

Pseudo-code (C)	Pseudo-code (C')
1: g <- mem[j+12]	1: g <- mem[j+12]
2: h <- k - 1	2: h <- k - 1
3: f <- g * h	3: f <- g * h
4: e <- mem[j+8]	4: e <- mem[j+8]
5: r0 <- mem[j+16]	8: b <- mem[f]
6: call proc1	9: j <- e + b
7: d <- r0
8: b <- mem[f]
9: j <- e + b

1.

Concerning the code (C'), construct an undirected graph with nodes corresponding to variables (in the following a variable and its corresponding node are identified) which satisfies the following condition:

Nodes x and y are adjacent $\Leftrightarrow$ the interval while x is live and the interval while y is live intersect.

2.

The $k$-coloring problem of a graph is to color each node by using at most $k$ colors so that adjacent nodes are colored differently, and, when the graph has such a coloring, it is called $k$-colorable. If the graph constructed in the above question is $k$-colorable, the code (C') can be computed using $k$ resgiters. Explain this fact.

3.

Construct a graph so that the code (C) can be computed using $k$ registers if $k$-colorable. The definition of nodes may be extended if necessary.

1.

At the very begining, $k$ and $j$ are live. When $g$ is defined, it is made live while $k$ and $j$ are still live. But, when $h$ is defined, $k$ is not live any more. Only $j$ and $g$ are live. $g$ and $h$ are used in the determination of $f$ which is made live while $j$ is still live. $g$ and $h$ can be dropped out since they are not used afterwards. The liveness of $j$ stops when it is used to determine $e$. $f$ is made dead when $b$ is defined. $e$ and $b$ are live together when $j$ is finally assigned at the last instruction.

$$\includegraphics{c-prime-coloring.ps}$$

2.

Let us assume that we have colored the graph with $k$ colors. Let $x$ be a variable or its corresponding node in the graph. When $x$ is live, it should be located inside a register. The set of adjacent vertices of $x$ are the variables susceptible to be in a register while $x$ itself is in a register. But not necessarily all the neighbors of $x$ and $x$ will be in registers at the same time. If $x$ is connected to $y$, then $x$ and $y$ have to share the registers. If $x$ is connected to $y$ and $z$, then $x$, $y$, and $z$ have to share the registers at the same time if and only if $y$ and $z$ are also connected to each other. In the latter situation, we see that the coloring of the graph whose set of vertices if $\{x,y,z\}$ needs three different colors, but if $y$ and $z$ are not connected, then two colors are enough. In similar way, when all the vertices are live at the same time, three registers should be allocated, instead of only two, when only two of them are live at the same time. If we associate with each color a register, then the coloring of the graph tells us how many registers we should use so that at any time all the live variables can be in registers.

3.

We extend the definition of a node in the following way. A node is either a variable or a register. A register is said to be 'live' during the time the value that has been affected to him has not been withdrawn. Once the graph has been constructed, it is colored in such a way that register nodes will first be affected the demanded color, i.e., the one that corresponds the the register named.

$$\includegraphics{c-coloring.ps}$$