[gsnedders]

> IIRC it started with programs in SSA form and has dropped that requirement more recently.

No, it's only SSA form that has optimal register allocation in polynomial time, otherwise someone would've proved that P=NP (as its proven to NP-Hard). :)

That said, finding minimal SSA from arbitrary SSA is NP-Hard.

> Modern GCC uses SSA form and I think LLVM might too.

LLVM has always used SSA (this is relatively unsurprising given its origins in research and so much research of the period being on SSA).