Lazy Code Motion Optimizer Framework
March 10, 1999
We are pleased to announce that Cygnus has donated a lazy code motion
optimizer framework (LCM).
LCM is a general technique for performing global optimizations such
as global cse and partial redundancy elimination.
LCM is an improvement over other global redundancy elimination algorithms
because it can typically find more redundancies and minimize register lifetimes.
In fact, in a 100% complete implementation LCM can be shown to be
computationally optimal.
The LCM algorithm Cygnus has donated is based on the lazy code motion
algorithms found in Steven Muchnick's book, Advanced Compiler Design and
Implementation (pages 407-415). LCM optimizers are provided which work
on both the forward and the reverse flow graphs.
The basic concept behind LCM is to initially move all expressions as
far up in the flowgraph as possible. This exposes the maximum number of
redundancies. Then expressions are then pushed as far down in the flow
graph as possible, which minimizes register lifetimes.
This implementation is missing one key feature which prevents it from
being computationally optimal, specifically critical edge splitting. While the
optimizer works and will perform better than most global optimizers, the
lack of critical edge splitting prevents the resulting code from being
computationally optimal.
We will be shortly reworking the global cse optimizer to use the lazy
code motion framework. We expect other optimizations using the lazy code
motion framework to be added to the compiler in the future. For example,
the lazy code motion framework can be used to implement spill code motion.
Please send FSF & GNU inquiries & questions to
gnu@gnu.org.
There are also other ways
to contact the FSF.
These pages are maintained by
the GCC team.
For questions related to the use of GCC, please consult these web
pages and the GCC manuals. If
that fails, the gcc-help@gcc.gnu.org
mailing list might help.
Please send comments on these web pages and the development of GCC to our
developer mailing list at gcc@gnu.org
or gcc@gcc.gnu.org. All of our lists
have public archives.
Copyright (C) Free Software Foundation, Inc.,
51 Franklin St, Fifth Floor, Boston, MA 02110, USA.
Verbatim copying and distribution of this entire article is
permitted in any medium, provided this notice is preserved.
|
Last modified 2006-06-21
|
|