[dubiousconst281]

It seems that the exact opposite problem (phi elimination / translating out of SSA form) is rarely discussed in depth, especially in introductory material.

From what I've seen, most compilers rely on the register allocator to deal with this problem (which makes total sense), or just don't bother at all and instead keep SSA in "conventional" form.

But the problem isn't really that difficult. In Sreedhar/Boissinot et al.'s paper (which btw has a typo in the copy sequentialization algorithm), the idea is quite simple: create copies for each phi argument, plus an additional copy for the phi result, then coalesce those copies to the same variable if their live-ranges don't intersect. The devil is on the details of course, and it just takes a lot more effort to implement compared to the text book construction algorithm.

[slavapestov]

I remember reading this paper, implementing the algorithm in Factor and finding the typo some 13 years ago… http://hal.archives-ouvertes.fr/docs/00/34/99/25/PDF/OutSSA-...