Hacker News — vinext + Cloudflare Workers

63 points by mpweiher 2 days ago | 3 comments

tonfa 1 days 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).

zarakshR 1 days 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...

ndesaulniers 18 hours ago [-]

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.

Rendered at 12:46:46 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.