coming up with this greedy, scanning version of the graph-coloring algorithm
debugging
I think the most interesting part is handling caller-callee saved registers. The latter is easier, we can scan the final assembly at the end, and insert spill/restore at prologue/epilogue. The former is weird, theoretically it's like "the caller-saved registers" are written to in any "call" instruction, but the register allocator's job is to figure out which temp maps to those physical registers! It's like a tail chasing scenario. What I did is to inform register allocator which regs are caller/callee-saved, and let it pre-color all temps that live across a call instruction to callee-saved regs (else it must be spilled).
Anyway, I hope this is well documented and written with reasonable clarity.
This is non-trivial. I spent many hours
I think the most interesting part is handling caller-callee saved registers. The latter is easier, we can scan the final assembly at the end, and insert spill/restore at prologue/epilogue. The former is weird, theoretically it's like "the caller-saved registers" are written to in any "call" instruction, but the register allocator's job is to figure out which temp maps to those physical registers! It's like a tail chasing scenario. What I did is to inform register allocator which regs are caller/callee-saved, and let it pre-color all temps that live across a call instruction to callee-saved regs (else it must be spilled).
Anyway, I hope this is well documented and written with reasonable clarity.