Rat's Register Allocator

(hexrat.cc)

31 points | by mpweiher 1 day ago

1 comments

tonfa 2 hours ago
> 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).
https://compilers.cs.uni-saarland.de/projects/ssara/
[-]
- zarakshR 2 hours ago
  Not quite, SSA form makes only the colouring pass polynomial time, optimal choice of spilling and coalescing is still NP-complete. cf. https://hal-lara.archives-ouvertes.fr/hal-02102286v1/documen...