Re: Loop optimization

[Jeffrey A Law <law at hurl dot cygnus dot com>]

  In message <13976.21255.754611.85053@ongaonga.elec.canterbury.ac.nz>you write
:
  > So at what stage do you envisage that we first build a CFG?
We can build a cfg anytime it is convienent after rtl generation is complete.

I believe the first one egcs builds is during the gcse pass (which is before
loop).  Internally at Cygnus we've got a pass that uses cfg data that runs
immediately after the jump optimizer (block merger).

One could even argue that much of the jump optimizer should be looked at from
a cfg viewpoint instead of a stream of insns viewpoint.

Richard has been playing around with building and maintaining a cfg much
earlier in the compiler and changing various passes to use the cfg data instead
groping around for jumps themselves.  I don't know how far along he is.


  > Certainly
  > having this information could help to improve the hoisting of
  > invariant blocks out of loops.  
Yes.  The way to do this is to use natural loop analysis to find the blocks
which are actually part of the loop, then rip out any blocks that are
physically in the loop, but are only executed on a path which unconditionally
exits the loop.

That'd allow us to rip out a hunk of grody code in loop.c which performs this
transformation for a few simple cases.

  > Is the CFG likely to use a list of block succs/preds or edges?
We use both, it depends on the optimizer.  Most use pred/succ lists, but
haifa for example uses an edge table.

I'm going to be experimenting with a new lcm implementation which uses an
edge table.  It would allow us to solve a couple of interesting problems with
abnormal critical edges and critical edge splitting.


  > I suppose the next question is whether we recalculate the CFG after each
  > optimisation pass or modify the CFG on the fly?
Right now we recalculate.  Being able to modify it on the fly is a long term
goal too.

jeff