Join the discussion
Write your take first — we'll ask for email only when you're ready to publish.
- Hacker News
- This is a great high level overview of some the techniques and problems encountered with developing a register allocator!
LLVM 's FastRegAlloc also uses linear scan.
by ndesaulniers - > The best assignment is NP-hard to find, so all practical allocators use heuristics.
That said if you do the register allocation while the program is still in SSA form, it becomes polynomial (interference graph is a chordal graph).
by tonfa