Implement a register allocation pass
Closed this issue · 0 comments
dubiousconst282 commented
Having a register allocation pass would improve the situation around having one temp variable for each expression, and it could also avoid the need of a full blown SSA destruction pass.
I think a linear scan algorithm would be sufficient, but we could look into graph coloring algorithms exploiting SSA form. It shouldn't be too complicated since we don't need to handle spilling nor other complications.
Resources:
- "Linear Scan Register Allocation on SSA Form" - http://www.christianwimmer.at/Publications/Wimmer10a/Wimmer10a.pdf
- "Efficient global register allocation" - https://arxiv.org/pdf/2011.05608
- https://cfallin.org/blog/2022/06/09/cranelift-regalloc2/
- https://www.reddit.com/r/Compilers/comments/xvsrdb/the_solidstate_register_allocator/
- https://www.reddit.com/r/ProgrammingLanguages/comments/b42g6n/reverse_linear_scan_allocation_is_probably_a_good/