Re: Few Doubts about register allocation via Graph colouring [Briggs thesis]

On Oct 18, 6:20 am, shafi <shafi...@gmail.com> wrote:
> I was asking about live ranges with infinite spill cost and "high"
> degree. The pseudo code the follows the above description in your
> thesis doesn't mention about such live ranges. But still they have to
> be pushed. So again since they have to get a register should they be
> pushed on to the stack at the end?


In the English description associated with the pseudocode
(2nd paragraph of section 8.8, near the bottom of page 110),
it says: "Nodes of high degree and infinite spill cost [...] are not
included in either set."


At the top of page 111, I note: "To remove a node m from the graph, we
visit each neighbor n [...] and decrement its degree. If the new
degree of n is k - 1, then n is removed from high and added to low."


This last sentence is key. Perhaps I should have written it like
this: "If the new degree of n is k - 1, then n is added to low and, if
it is present in high, it is removed."


You see, the set high is used to hold nodes we'll want to search
through for spill candidates. Nodes of infinite spill cost are not
spill candidates, so they don't ever get added to high. But any node
whose degree is eventually reduced to less than k is added to the set
low (the only nodes that are never members of low are nodes that are
chosen as spill candidates).


Every node eventually appears on the stack.


Probably my choice of names for "low" and "high" was poor. The
important thing is to remember that the two sets do not partition all
the nodes in the graph. Instead, each of the two sets serves a
particular purpose. Low holds nodes that can be immediately removed
from the graph. High holds nodes that we will search among for spill
candidates.


Hope this helps,
Preston

Return to the comp.compilers page.
Search the comp.compilers archives again.