[LLVMdev] A question about StrongPhiElimination

[Yuan Lin]

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