Re: Copy Propagation refs?

"V.C. SREEDHAR" <sreedhar@bluebeard.cs.mcgill.ca> 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
solved.


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
loan).


Cliff


--
Cliff Click, Ph.D. Compiler Researcher & Designer
RISC Software, Motorola PowerPC Compilers
cliffc@risc.sps.mot.com (512) 891-7240
http://members.aol.com/mjclick1
--

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