SSA - Copy Propagation and Phi functions

Question

I've implemented a program that converts a control flow graph to minimal ssa (and I am pretty sure it is correct (see here)). Now I am trying to implement copy propagation. I've implemented it for the most part, but I am unsure what to do when the variable we are propagating is in a phi function. Suppose I have a variable I am going to propagate:

z_0 = y_1

Also, z_0 is in a phi function:

z_1 = PHI(z_0, z_1)

Now, when propagating, what should I do to z_0 in the phi function (because after propagation is finished, I will remove the definition of z_0)? Should I propagate z_0 to the phi function? Such that the phi function looks like this?:

z_1 = PHI(y_1, z_1)

Answer 1

Yes. All uses of z0 are replaced with y1 in copy propagation. There are multiple edge cases to handle, as @rici hinted at, as copy propagation is uniquely adept at breaking phi nodes / inadvertently altering their semantics.

Some of these problems are encapsulated in the "lost copy problem" and "lost swap problem."