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

Hello all,


I am trying to implement a register allocator via graph colouring
based on the thesis written by Preston Briggs, and i have got a few
doubts regarding that.


1. In all the register allocation that i have seen the program flow is
such that if spilling is required in graph colouring, after inserting
the spill code the whole process, starting from the live range
analysis is repeated again. During the first iteration itself the
allocator will be colouring all the live ranges with or without
spilling. If this is so whats the need of subsequent iterations?


2. Is there any need to consider any target details in coalescing
other than pre-colouring?
3. While calculating the spill cost, in the thesis Briggs has written
the following
for (r = k; r < ranges; r++) {
......
......
range[r].cost - = range[r].copies;
}


What is the function of the variable range[r].copies ? i.e what
exactly is this variable?


4. In the simplify phase Briggs has mentioned the following :
"In preparation for simplify, we classfiy each node based on its
degree and its spill cost. All the nodes of degree < k are placed in a
set 'low'. Nodes of degree >= k and finite spill cost are placed in a
set 'high'. nodes of the high degree and infinite spill cost are not
included in either set."
Position of the live ranges in the stack after they are pushed during
the simplify phase does play a important role in picking a colour.
Since the live ranges with infinite spill cost has to get a register,
they should be pushed on to the stack at the end so that they get a
register in the beginning itself. Am i right?


Any help would be appreciated.


Regards,
Shafi

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