Copy propagation on factored def-use chains, without overlapping live ranges

Hi,


Suppose you have an intermediate representation (IR) with FUD chains.
I want to perform copy propagation, but I must avoid propagations that
introduce overlapping live ranges. This is basically the same issue
that GCC ran into in the early days of GCC4 development
(http://gcc.gnu.org/ml/gcc-patches/2003-03/msg00003.html).


Consider the following case, for example:
===================
S1: r1 = r2; { DEF r1_1 }{ USE r2_2 }


S2: if (...)
S3: r2 = ... { DEF r2_3 }


                PHI { DEF r2_4 }{ USE r2_2, r2_3 }
S4: r3 = r1; { DEF r3_5 = r1_1 }
===================


Traditional SSA copy propagation will simply follow the USE-DEF chains
and replace the USE of r1_1 in S4 with r2_2 from the copy statement
S1. That would change S4 to "r3 = r2", which is fine if the registers
have explicitly been renamed (r2 in S2 would have been renamed) . But
with FUD chains "on the side" this transformation would of course be
wrong.


So a simple SSA copy propagation using USE-DEF chains won't work for me.


Does anyone know about / have a pointer to a sparse copy propagation
algorithm that works on this kind of representation?


Many thanks,


Gr.
Steven

Return to the comp.compilers page.
Search the comp.compilers archives again.