The renaming algorithm is based on "Practical Improvements to the Construction and Destruction of Static Single Assignment Form".
We construct pruned SSA without computing live sets, by building a dependency graph for phi instructions, marking the transitive closure of a vertex as live if it is referenced by some non-phi instruction. Thanks to Cameron Zwarich for the trick.