Common subexpression analysis (summary)

Earlier this month I asked a question regarding the state of the art in
common subexpression elimination; this is a summary of the responses to my
query, except those of Preston Briggs and Michael Sharp, which have
already appeared in this newsgroup. (My apologies for my delay in posting
this; I'm having trouble typing due to RSI.)


Research on CSE in the last decade and a half has been very sporadic.
Many people said that the problem is NP-complete; this has been proved in
two important special cases. Most respondants said that the effort
involved in doing anything more complicated than the two standard
techniques (value-numbering to determine when operands are equivalent to
some encountered earlier in the basic block, and checks for lexical
identity when the operands have not been modified since the operation was
last performed) would be more effort than it was worth.


My question about reassociation evoked more response; again, most people
said it was unlikely to be worthwhile. I've run across several references
in the literature to compilers that reassociate, but they don't provide
any more details than a paragraph. The Convex Fortran compiler does this,
for instance; the PL.8 and Id compilers do rearrangement in the
code-hoisting module, where expression are small and the largest speedups
can be obtained. Cocke and Markstein say that a variant of rearrangement
provides 50% speedup in some real inner loops, but at that point they had
not yet implemented their technique.
-Michael Ernst
mernst@theory.lcs.mit.edu


--

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