|Copy Propagation refs? firstname.lastname@example.org (V.C. SREEDHAR) (1996-02-09)|
|Re: Copy Propagation refs? email@example.com (1996-02-13)|
|From:||firstname.lastname@example.org (Cliff Click)|
|Date:||13 Feb 1996 00:31:17 -0500|
"V.C. SREEDHAR" <email@example.com> writes:
> Are there any papers or TRs that discusses copy propagation
> (sometimes also called as coalescing or subsumptions) based on
> SSA representation?
Sure, I'll take a stab at this one.
It's too simple to deserve a paper, so there isn't one. In SSA form,
everything has a unique name. The result of the COPY is, by SSA
definition, another unique name. To remove the COPY, change the COPY
destination name to match the COPY source name. The COPY becomes
trivially redundant, so remove it. ALL copies get removed. Problem
The real problem is coming OUT of SSA form, where you have to
re-insert some copies. This gets ugly if you have 1-block cycles and
"critical" or "control dependent" edges - imagine trying to correctly
insert copies when the CFG is a clique.
In my particular (SSA based) IR, copy propagation occurs whilst I
parse my input (along with a host of other optimizations).
"Coalescing" is generally used in reference to graph-coloring register
allocators. There the program is explicitly NOT in SSA form. The
goal is to remove as many copies as you can (as opposed to SSA form,
where ALL copies get trivally removed). This is a harder problem.
Check out Preston Brigg's thesis and the 1996 POPL on a paper by
George and Appel (sorry no better reference; my proceedings are out on
Cliff Click, Ph.D. Compiler Researcher & Designer
RISC Software, Motorola PowerPC Compilers
firstname.lastname@example.org (512) 891-7240
Return to the
Search the comp.compilers archives again.