Chaitin published his stuff in the early 80s. Presumably the implementation is a bit older. But the idea of doing register allocation via graph coloring goes back to the late 60s and the idea of using graph coloring to minimize storage requirements generally goes back to around '63.
The interprocedural problem is mostly engineering - how to manage libraries, make files, etc., in a way that programmer will use it.
So I'll add graph coloring to the list of great things that happened in the 1960's that still kick arse today. Burroughs architecture, graph coloring, Dijkstra's methods... quite a few.
The interprocedural problem is mostly engineering - how to manage libraries, make files, etc., in a way that programmer will use it.