Re: [tree-ssa] reaching def. question

[David Edelsohn <dje at watson dot ibm dot 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 -----