Sat, 31 May 2008 13:48:29 +0200

Related articles |
---|

Copy propagation on factored def-use chains, without overlapping live stevenb.gcc@gmail.com (Steven Bosscher) (2008-05-31) |

From: | "Steven Bosscher" <stevenb.gcc@gmail.com> |

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 |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.