Re: Common subexpression analysis

mernst@theory.lcs.mit.edu (Michael Ernst) writes:


>Is the topic of common subexpression analysis considered a mature field?
>A search through the ACM and INSPEC collections revealed almost no work in
>recent years; the topic seems to have died off after the mid-70s. Much of
>the work is architecture-specific or discusses computing available
>expressions rather than identification of common subexpressions per se.
>Or am I missing something? Is there literature on computing common
>subexpressions on three-address machines with a finite, non-unity number
>of registers?


There are two broad catagories of CSE elimination techniques: partial
redundancy elimination and value numbering. Since they tend to find
different classes of improvements, many optimizing compilers perform both
(e.g., the PL.8 compiler, the MIPS compiler, ...)


Partial redundancy elimination works globally (throughout a procedure)
with lexically identical expressions. Literature includes


    title="Global Optimization by Suppression of Partial Redundancies",
    author="Etienne Morel and Claude Renvoise",
    journal=cacm,
    year=1979,
    volume=22,
    number=2,
    month=feb,
    pages="96--103"


    title="A Solution to a Problem with {Morel} and {Renvoise's}
                                  ``{Global} Optimization by Suppression of Partial
                                  Redundancies''",
    author="Karl-Heinz Drechsler and Manfred P. Stadel",
    pages="635--640",
    journal=toplas,
    year=1988,
    month=oct,
    volume=10,
    number=4


    title="Some Comments on ``{A} Solution to a Problem with {Morel} and
                                  {Renvoise's} `{Global} Optimization by Suppression of
                                  Partial Redundancies'\,''",
    author="Arthur Sorkin",
    pages="666--668",
    journal=toplas,
    year=1989,
    month=oct,
    volume=11,
    number=4


    A Usually Linear Algorithm for Register Assignment Using Edge
Placement of Load and Store Instructions
    D. M. Dhamdhere
    Computer Languages 15(2), 1990


        There are several other papers by Joshi and/or Dhamdhere
        included in the bibliography.




There's also Fred Chow's thesis, from Stanford, December 1983.




Usually these schemes don't consider the possibility of reordering
expressions. Instead, they work with expressions available in 3-address
code. They are very nice though, accomplishing an aggressive form of
global CSE elimination and loop-invariant code motion.


Value numbering accomplishes a form of symbolic execution and is capable
of finding a much larger class of redundancies. In this case, arbitrary
amounts of expression reordering are possible. Note however, that the
problem of obtaining optimal results (even if restricted to basic blocks)
is NP-complete. Nevertheless, many real compilers do some forms of
reassociation to expose more CSE's. The PL.8 compiler (and others) also
performs reassociation of loop-invariants to increase the effectiveness of
loop-invariant code motion. Older work on value numbering includes


Programming Languages and Their Compilers
Preliminary Notes
John Cocke and Jacob T. Schwartz
April 1970
Courant Institute, NYU


Kennedy's chapter in
Program Flow Analysis: Theory and Applications
Muchnick and Jones
Prentice Hall, 1981


There's also a couple of papers by Schwartz in old issues of
Computer Languages that would be relevant, the Dragon Book and
many SETL newsletters.


Traditional forms run over basic blocks and extended basic blocks. More
recently, theres has been some work on global forms of value numbering,
attempting to combine the advantages of partial redundancy elimination and
values numbering. Two important papers include


    title="Detecting Equality of Variables in Programs",
    author="Bowen Alpern and Mark N. Wegman and F. Kenneth Zadeck",
    booktitle=popl15, year=1988,
    month=jan


    title="Global Value Numbers and Redundant Compuations",
    author="Barry K. Rosen and Mark N. Wegman and F. Kenneth Zadeck",
    booktitle=popl15,
    year=1988,
    month=jan


>Is there literature on computing common subexpressions on
>three-address machines with a finite, non-unity number of registers?


Not much in terms of global CSE elimination. Most optimizers proceed
optimistically, assuming there will be enough registers. I believe this
is one of the important simplifications made possible by modern
architectures with their large register sets.


Preston Briggs




--

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