The key here is to make sure we never RAUW a constant that's used by other constants. Since Constants form a DAG, this is just a matter of constructing the replacements and RAUW'ing the constants in the right order. Most of the complexity here is computing that order.
One thing that's a bit unfortunate about this algorithm is that it creates a couple DenseMaps which have only entry per replaced constant. So it uses significantly more memory than the previous algorithm. It might be possible to optimize this to some extent, but hopefully this doesn't matter in practice.