Loop optimiser upgrade (Was RFC: BB duplication code)

[Michael Hayes <m dot hayes at elec dot canterbury dot ac dot nz>]

Jan Hubicka writes:

 > > I'd say strip the loop notes.  You don't really lose any information,
 > > in that correct information can always be obtained from the shape of
 > > the CFG, via flow_loop_nodes_find.
 > Agreed - anyway an loop optimizer is still an barrier for my effort.
 > Until it is converted to use CFG, we can't make flow info survive.

I agree that the loop notes should be weeded out.  The one useful loop
note is the VTOP note that indicates if the loop exit code has been
duplicated.  When this loop exists and we know that the loop body will
be executed at least once if the loop header is entered.  I'm not sure
of an easy means to determine this from the CFG.

 > Converting whole loop optimizer at once can be huge task. Additionally some
 > pieces should be already obsoletted (as code hoisting).

Yes, I agree.  Before I got snowed under with my real job I had a big
hack at converting the old loop optimiser to use the CFG.  The problem
was ensuring that I did not break anything.  I think a better approach
is to write another loop optimiser that can run after the current loop
optimiser and then one day replace it completely.  After the current
loop optimiser has run, I'd say that we should strip the loop notes
completely (or at least regenerate them from the CFG) and rely totally
on the CFG.

 > So I think that in mid term, we can make the BIV/GIV discovery code idedendent
 > on loop notes (it should not be that dificult) and start work on new loop
 > unroller done as separate pass.

Yes, this could be done standalone.  However, it would need loop
invariant discovery code first.  This is one of the reasons I wrote
the dataflow code that Dan Berlin has marvellously souped up for the
new register allocator.  It is also the reason I added routines to
loop.c for sinking and hoisting insns so that I could track the
changes to the dataflow.

What started to stump me was an efficient way to update the dataflow
information incrementally after each loop optimisation.  To mitigate
the dataflow computation needed, I structured the loop optimiser to
optimise all the innermost loops first, then all the next level loops,
and so on.  This way the loops could be optimised independently
without having to always recompute the dataflow information.

I've attached the basic structure of the data flow based loop
optimiser that I was working on.

Michael

loop-df.c