Re: Help: Looking for optimization algorithms

tvalesky@site.gmu.edu (Thomas B Valesky (CS)) writes:
|> Can anyone point me to fairly detailed pseudocode for global common
|> subexpression elimination and/or loop-invariant detection and code
|> motion?


One technique for common subexpression elimination is called value numbering.
A good paper on this is:


@inproceedings{alpern:88,
    title="Detecting Equality of Variables in Programs",
    author="Bowen Alpern and Mark N. Wegman and F. Kenneth Zadeck",
    booktitle=popl15,
    address="San Diego, California",
    year=1988,
    month=jan,
    pages="1--11"
}


My implementation of this algorithm is available via anonymous ftp at:
          ftp://cs.rice.edu/public/preston/optimizer/gval.ps.gz


The implementation is in the form of a web, which combines the code
with a great deal of explanation.


Preston Briggs, Keith Cooper, and I have written a paper comparing
several forms of value numbering. It hasn't been published yet, but
it is available via anonymous ftp at:
          http://www.cs.rice.edu/~lts/valnum.ps.gz




Morel and Renvoise described a technique called partial redundancy
elimination that combines common subexpression elimination with loop
invariant code motion. Partially redundant computations are
redundant along some, but not necessarily all, execution paths.


@article{morel:79,
    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",
    file=68
}


Drechsler and Stadel modified their technique.


@article{drechsler:88,
    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
}


A good implementation of this algorithm was written by Preston Briggs
and Rob Shillingsburg. The implementation is also in the form of a
web. It is available via anonymous ftp at:


          ftp://cs.rice.edu/public/preston/optimizer/partial.ps.gz


There are also some descendants of this technique that you might be
interested in. In particular:


@article{knoop:92,
    title="Lazy Code Motion",
    author="Jens Knoop and Oliver {R\"uthing} and Bernhard Steffen",
    pages="224--234",
    journal=sigplan,
    year=1992,
    month=jul,
    volume=27,
    number=7,
    note=pldi92
}


and


@article{drechsler:93,
    title="A Variation of {Knoop}, {R\"uthing}, and {Steffen}'s
    ``Lazy Code Motion''",
    author="Karl-Heinz Drechsler and Manfred P. Stadel",
    pages="29--38",
    journal="SIGPLAN Notices",
    year=1993,
    month=may,
    volume=28,
    number=5
}


My thesis is to unify the approaches of value numbering and code
motion. I have two papers that have been submitted for publication
that you can get via anonymous ftp at:


        http://www.cs.rice.edu/~lts/scc.ps
        http://www.cs.rice.edu/~lts/vdcm.ps


The first one describes a value numbering algorithm that is an
improvement over the existing ones, and the second is an improvement
to the code motion algorithms.


Taylor Simpson
Massively Scalar Compiler Project
Rice University


--
lts.cs.rice.edu
--

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