Re: Loop optimiser upgrade (Was RFC: BB duplication code)

[Jan Hubicka <jh at suse dot cz>]

> 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.
It should be possible to tie this into branch prediction scheme, as I do
currently with the knowledge of iteration count. Overall I believe that future
loop optimizer should be able to do loop peeling (and header duplication as
special case), instead letting previous passes doing it.  This way we will
probably not need to preserve the information too long.
> 
>  > 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
It would be excellent to see your code.
> 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
100% agreed - actually I was suggesting that in separate email.
I am thinking about doing that at CFG branch.  I think we should follow
> 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.
Looks your plan is compatible.
I planned steps
1) create an "loop module" able to analuze loop and get invariants
2) create an BIV/GIV module
3) rewrite strength reduction and loop unrolling on top of it.
We should be able to drop invariant/memory hoisting code as it is
redundant with PRE/load/store motion.
> 
> 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.
You mean the DU/DF chains?
Thats problem - how it is handled by other compilers? Can't we get them
updated incrementaly?
> 
> I've attached the basic structure of the data flow based loop
> optimiser that I was working on.
Great.  It is probably time to start the CFG branch and get your work
into it.

Honza
> 
> Michael
>