Hello, I've encountered a problem similar to 'lost-copy' when using
the StrongPhiElimination and wonder whether it is a incompatibility
issue between the two different algorithms used in
StrongPhiElimination.cpp. The StrongPhiElimination is mostly based on
the algorithm in Zoran Budimilic et al's "Fast Copy Coalescing and
Live-Range Identification" ([1]), while the 'Copy Insertion' part is
from Preston Briggs et al's "Practical Improvements to the
Construction and Destruction of Static Single Assignment Form" ([2]).

The test case I have is as follows,

Block 1
r1 = ...
if (...) goto Block 2
else goto Block 3

Block 2
r2 = ...
goto Block 4

Block 3
r3 = phi(r1, r4)
r4 = ...
if (...) goto Block 3
else goto Block 4

Block 4
r5 = phi(r2, r3)
... = r5

Since the live range of r2, r3, and r5 do not interference,
StrongPhiElimination decides, before InsertCopies(), to rename both r2
and r3 to r5 based onthe algorithm in [1]

During InsertCopies(), because 'r3' is live after Block 3 and this is
the typical case where 'lost-copy' could happen, StrongPhiEilimination
inserts a copy from r3 to a temp register r99 based on the algorithm
in [2]. Block 3 then becomes

Block 3
r3 = phi(r1, r4)
r99 = r3
r4 = ...
r3 = r4
if (...) goto Block 3
else (...) goto Block 4

The Insert-copy algorithm in [2] would normally rename r3 in Block 4
to r99. But StrongPhiEliminination decides unify 'r5', 'r2' and 'r3'
instead of inserting copies for 'r5=phi(r2, r3)' in Block 4, therefore
the 'waiting' set for Block 4 is empty. 'r3' is not renamed to 'r99'
in StrongPhiElimination.

Then StrongPhiElimination proceeds to the renaming phase and rename
both r2 and r3 to r5. The final code becomes

Block 1
r1 = ...
r5 = r1
if (...) goto Block 2
else goto Block 3

Block 2
r5 = ...
goto Block 4

Block 3
r99 = r5
r4 = ...
r5 = r4
if (...) goto Block 3
else (...) goto Block 4

Block 4
... = r5

The value of r5 in Block 4 is wrong when the path Block 1->Block
3->Block 4 is taken.

I must say I still do not fully understand the implementation in
StrongPhiElimination, especially the live range checking and updating
code. The above is just based my understand from reading the code,
[1], [2], the incorrect result I get and he output from my debug
session.

Is this a real problem? What am I missing?

Thanks!

-- Yuan