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

On Oct 15, 2:07 am, "Mohamed Shafi" <shafi...@gmail.com> wrote:
> 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.


I'm sorry the thesis was unclear.


> 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?


During the all iterations, we attempt to color without spilling. If
spilling is required, the attempted coloring is abandoned (that is,
the instructions are not rewritten). Instead, spill code is inserted
and we start again.


> 2. Is there any need to consider any target details in coalescing
> other than pre-colouring?


I pay attention to things like 2-address instructions.


> 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?


It's the number of register-to-register copy instructions that mention
the live range "r".


> 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?


Not exactly. A live range with infinite spill cost and low degree
should be placed in set "low", where they will be removed from the
graph and pushed on the stack early.


If you just follow the description, things will end up in the right
place; you don't have to add any more special cases.


Preston

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