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

"Steven Bosscher" <>
Sat, 31 May 2008 13:48:29 +0200

          From comp.compilers

Related articles
Copy propagation on factored def-use chains, without overlapping live (Steven Bosscher) (2008-05-31)
| List of all articles for this month |

From: "Steven Bosscher" <>
Newsgroups: comp.compilers
Date: Sat, 31 May 2008 13:48:29 +0200
Organization: Compilers Central
Keywords: analysis, optimize, question
Posted-Date: 31 May 2008 15:23:32 EDT


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

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

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,


Post a followup to this message

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