This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Global CSE and constant/copy propagation
- To: egcs at cygnus dot com, gcc2 at cygnus dot com
- Subject: Global CSE and constant/copy propagation
- From: Jeffrey A Law <law at cygnus dot com>
- Date: Wed, 20 May 1998 01:42:55 -0600
- Reply-To: law at cygnus dot com
Global CSE/Partial Redundancy Elimination
May 18, 1998
We are pleased to announce that Cygnus has donated a global
optimization framework and new optimizers based on that framework to
the EGCS project.
An extra special thanks to Doug Evans who wrote much of this code as
his last GCC project. Thanks for the many contributions over the
years!
The global optimization framework provides:
* Functions for breaking a program into basic blocks.
* Functions to build successor/predecessor lists for each basic
block.
* Functions for building and manipulating simple bitmaps, including
the ability to compute the union/intersection of all the bitmaps
for a block's predecessors/successors.
This infrastructure provides EGCS with the capability to solve
traditional uni-directional dataflow problems which arise in most
global optimizers.
New optimizers
* Global constant and copy propagation.
* Global common subexpression elimination.
EGCS has two implementations of global common subexpression
elimination. The first is based on the classic algorithm found in most
compiler texts and is generally referred to as GCSE or classic GCSE.
The second implementation is commonly known as partial redundancy
elimination (PRE). PRE is a more powerful scheme for eliminating
redundant computations throughout a function. Our PRE optimizer is
currently based on Fred Chow's thesis.
The difference between GCSE and PRE is best illustrated with an
example flow graph (please forgive the poor graphics, I'm no HTML or
graphics guru).
[ PRE example figure not available in text announcement, but it is
available on the egcs web site. ]
This example has a computation of "exp1" in blocks B2, B3 and B6.
Assume that the remaining blocks to not effect the evaluation of
"exp1".
Classic GCSE will only eliminate the computation of "exp1" found in
block B3 since the evaluation in block B6 can be reached via a path
which does not have an earlier computation of "exp1" (entry, B1, B7,
B8, B5, B6).
PRE will eliminate the evaluations of "exp1" in blocks B3 and B6; to
make the evaluation in B6 redundant, PRE will insert an evaluation of
"exp1" in block B8.
While PRE is a more powerful optimization, it will tend to increase
code size to improve runtime performance. Therefore, then optimizing
for code size, the compiler will run the classic GCSE optimizer
instead of the PRE optimizer.
Global constant/copy propagation and global common subexpression
elimination are enabled by default with the -O2 optimization flag.
They can also be enabled with the -fgcse flag.
_________________________________________________________________
Last modified on May 18, 1998.
This announcement can be found in HTML form on the egcs project's
home page:
http://www.cygnus.com/egcs