Graph register allocator

Question

For my compiler course, I am creating a register allocator based on graph coloring for the MIPS architecture. I follow the Muchnick procedure for my implementation.

Muchnick was a bit fuzzy about how to consider function arguments in these allocators.

I made several assumptions and thought that I would clarify the same.

• This step can be converted to low-level IR from mid-level IR. Nested function calls are not processed. My idea is to scan the function call from right to left and set the IR for the innermost outside calls. Thus, I can use the MIPS calling convention to assign the first few arguments to the argument registers, and the remaining ones with the minimum number of spills (only 1).
• The registration of coalescence in the book is not intuitive for me, since it does not take into account how the LIR code of moving function arguments is processed for fixed argument registers. After much deliberation, I came to the conclusion that I did not need to register a coalition to pass arguments.

Feedback / thoughts on these assumptions are greatly appreciated.

Answer 1

I think that you do not want the register to coalesce to pass arguments from the virtual register to the register of arguments relative to the actual arguments of the function (or for formal arguments of the function, copied back to the function record) before the distribution of the register.

However, when you see such a move, you can mark the hint for the dispenser that the preferred choice is to move the register of target arguments. When the preferred choice does not intervene appropriately *, you can use it for distribution, as a result, after highlighting you will have move rx,rx , which you can easily eliminate later.

(Of course, you can find more than one such hint, so you can use the most suitable one, most (and often all) of them will be excluded from other hindrances: the same register is transferred to several calls; loop, etc.)

(* Correspondingly, it means that the register of the argument (real) is otherwise not used or broken during the life of the virtual register, for example, by a nested function call or some other. (Identifying this can be as simple as checking the interference of the virtual register.))