This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: [tree-ssa] reaching def. question
- From: David Edelsohn <dje at watson dot ibm dot com>
- To: law at redhat dot com
- Cc: gcc at gcc dot gnu dot org
- Date: Wed, 17 Mar 2004 17:18:04 -0500
- Subject: Re: [tree-ssa] reaching def. question
- References: <200403172210.i2HMAfFb011100@speedy.slc.redhat.com>
I have been discussing the SSA rewriting issues with a colleague
and friend of mine, Kenny Zadeck. He asked me to forward the appended
comments to this discussion.
David
----- Begin Forwarded Message -----
Date: Wed, 17 Mar 2004 15:22:37 -0500
From: Kenneth Zadeck <zadeck@naturalbridge.com>
To: "Edelsohn, David" <dje@watson.ibm.com>
Subject: Re: [tree-ssa] reaching def. question
There are many differences between coming out of ssa form and leaving it
ssa form for ever:
"Coming out" of SSA form has some costs as well as some benefits. We
(at NaturalBridge) go into SSA form early and never come out. In the
compilers I have worked on (both here and at IBM), we left it in SSA
form for ever.
By not coming out, I am assuming that the program is broken in SSA
form and each SSA variable has a pointer to the original source
program variable for debugging, but not much else. By coming out of
SSA form, I am assuming that you are first breaking source variables
into independent def-use chain webs (in IBM parlance solving the
"right number of names problem" and that each of these webs becomes
a real variable that the ssa variable map back to.
the benefits of coming out of SSA form:
1) compatibility with later phases that will not understand this.
2) easier to implement debugger if there are no overlapping ranges.
3) space, there are a much smaller number of webs than ssa variables.
the benefits of never coming out (or at least deferring it as long as
possible):
1) overlapping names are the norm rather than a special case in SSA
form. The only transformations that do not create overlapping names
are the ones that simply delete code (for example constant
propagation and dead code elimination). Any transformation that can
move code around (for example partial redundancy elimination and
loop invariant code motion) will create a potentially large number
of overlapping names; the more aggressive forms of these
transformations that you implement the more overlapping names you
will create.
Shortly after we developed SSA form, we noticed that many of the
good optimizations had the property that they created overlapping
live ranges. (Our invariant code motion algorithm generates
zillions of overlapping live ranges.) At first we thought this was a
problem but then we decided that unless you did this, you were
closing off a huge number of profitable transformations. This
meshed well with the notion that machines would soon have as John
Cocke put it "as many registers as you would ever need, say 32".
In particular, loop optimizations such as unrolling, create many
opportunities for the moving transformations to create many
overlapping live ranges since a lot of code from one iteration will
be redundant with the previous iteration.
As you seem to have discovered, even something as simple as if
conversion with the right transformations can cause overlapping
ranges. However, as you start doing the really aggressive stuff,
this will be the norm and not the exception.
2) Lots of names in general means better optimization. At the
admitted cost of extra space and time, the smaller granularity of
treating the SSA variables as first class variables will in general
lead to better packing of registers and a smaller number of copy
statements. In the coming out world, there is an implicit
assumption that all of the ssa variables associated with the web
will be treated the same way.
Later, if you implement good profile directed compiling coming out
of SSA form will turn out to be a bad assumption because the smaller
granularity of the SSA variables will allow you to get stellar code
on the fast path and do a poorer job on the off path code that is
represented in the other SSA variables. The webs will have too much
code in them.
"Going out" of ssa form may be necessary to interface the compiler
with the current debugger, code generator, and register allocator
which may not be designed to handle the load of the large number of
variables and the potential large number of copy statements that are
now necessary to glue this together. However, when you do this, there
is little (beyond the debugging info) to be gained by using the
original naming as the guide.
Kenneth Zadeck
zadeck@naturalbridge.com
----- End Forwarded Message -----