Re: Higher level RTL issues

[law at redhat dot com]

  In message <CCB1DD56-BD35-11D5-867A-0030657B5340@cgsoftware.com>you write:
  > 
  > On Tuesday, October 9, 2001, at 10:48  PM, law@redhat.com wrote:
  > 
  > >
  > > I know folks have heard me mention the idea of a higher level RTL from
  > > time to time.  I must apologize for not posting this earlier -- oh well,
  > > life goes on.  I must also apologize as this isn't 100% complete, but
  > > given that I haven't posted anything about it already and the fact that
  > > I'm going on vacation tomorrow, I figured I'd at least get this info out
  > > and let folks chew on it while I'm gone.
  > >
  > > I don't think there's any significant disagreement that a higher level
  > > IL would be useful.
  > >  What is a subject of debate is whether we have
  > > a lower tree form, higher RTL form or some other form.  I think if we
  > > look at the set of problems we want to solve we can get a good feel for
  > > which of the 3 choices makes the most sense.
  > >
  > >
  > > I'm looking at the new IL as a way to enable an SSA optimization path.
  > Okey dokey.
  > 
  > >  On
  > > that optimization path I'm initially looking at the following 
  > > optimizations:
  > >
  > > 	* Sparse conditional constant propagation (ssa-ccp.c)
  > >
  > > 	* Traditional dead code elimination (ssa-dce.c)
  > >
  > > 	* Aggressive dead code elimination (ssa-dce.c)
  > >
  > > 	* Register coalescing and renaming (ssa.c)
  > >
  > > 	* Dominator based value numbering (will eventually be in ssa.c)
  > >
  > > Certainly there will be more optimizations in the future, but I think 
  > > this
  > > set gives us a good idea of the kinds of optimization problems I want to
  > > solve.
  > I don't think that these are representative of the type of problems we 
  > *should* be looking to solve.
  > These are pretty basic ssa optimizations, not something to look at when 
  > determining the type of IL you need.
I disagree strongly.  One of the goals of moving towards an SSA optimization
path is to slowly, but surely build an optimization path that is stronger,
more efficient and more understandable than the mess we have now (particularly
cse.c and loop.c).  The first step in that direction is to build a path which
can perform the same things that the old path can perform and show that the
new path is better across the various axis mentioned above.

By not means should the list I mentioned above be considered exhaustive, I
very much want to build a path that can be used to solve more interesting
problems than the ones mentioned above.

By attacking the problems noted above I believe we can incrementally build
a new optimizer path in GCC without completely rewriting the compiler from
the ground up (meaning there's actually a remote chance we'll do it).

  > If we only use these as the things to base requirements on, you'll never 
  > get much improvement in performance.
  > At least, as they exist now.
  > Why?
  > Because the main optimizations needed right now relate to memory and 
  > loops.
  > You can perform very interesting loop and memory optimizations in SSA 
  > form.
  > However, having simply a higher level RTL would not help them 
  > significantly (>5%, i'd guesstimate), unless you tackle the issues of 
  > array indices and memory.
  > So to not take this into account at all when designing an IR better for 
  > SSA (whether it be a higher level RTL or whatever), would be a shame.
The class of problems in this space is going to require major rethinking
at both the tree level and the RTL level.  It should be sufficient to say that
I have had extensive discussions with folks about what we need to do to
one day be able to do these kinds of optimizations.

  > Sorry, this isn't correrct.
  > Factored use-def chains are more powerful than traditional SSA form, 
  > it's an extended variant of SSA, because it can handle backwards 
  > problems as well.
  > To get the equivalent, you'd need to take traditional SSA form,and give 
  > unique names to uses as well.
  > Anything you can do in traditional SSA, you can do with fud chains. You 
  > can link defs->uses just as well as you can link the uses->defs.
  > It's absolutely trivial.
  > The point of FUD is to allow not doing phyiscal renaming (saving 
  > memory), and to give use-def chains as well, without the cost of the 
  > renaming, so you can solve backwards dataflow problems, as demand driven 
  > optimizations often require.
  > I.E. It allows you to do things like demand-driven constant propagation.
  > http://www.acm.org/pubs/articles/proceedings/sac/326619/p400-stoltz/p400-st
  > oltz.
I'll have to show you an example where you do need renaming to perform 
relatively simple redundancy elimination problems that are found by any
reasonable value numbering scheme.

jeff