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

[Daniel Berlin <dan at cgsoftware dot com>]

Michael Hayes <m.hayes@elec.canterbury.ac.nz> writes:

> 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.

Loop invariant discovery as it stands right now isn't doing all it
could, as i'm sure everyone knows.
Without a fixed store motion i'm about to send off to Andreas for some
more bootstraps (It passes bootstrap and make check on rs6000 and x86,
after a few more fixes tonight), for the following simple dead stores
in loop code:

int global;
        float r;
void f()
{
        int q;
        int i;
        r=6;
        for (q = 0; q < 50; q++)
        {
                i = 1;
                global = 1;
                global = 2;
                r = 4;
                r=global;
        }
        return;
        global = 3;
}

We get:
   .file   "dse.c"
        .text
        .align 2
        .p2align 4,,15
.globl f
        .type   f,@function
f:
        pushl   %ebp
        movl    $0x40000000, %edx
        movl    %esp, %ebp
        movl    $0x40c00000, r
        movl    $49, %eax
        .p2align 4,,15
.L5:
        movl    %edx, r
        decl    %eax
        jns     .L5
        popl    %ebp
        movl    $2, %eax
        movl    %eax, global
        ret

Which completely misses the fact that r is loop invariant, for some
reason.

However, a working store motion turns it into:

.globl f
        .type   f,@function
f:
        pushl   %ebp
        movl    %esp, %ebp
        movl    $49, %eax
        .p2align 4,,15
.L5:
        decl    %eax
        jns     .L5
        popl    %ebp
        movl    $2, %eax
        movl    %eax, global
        movl    $0x40000000, %eax
        movl    %eax, r
        ret

Load motion isn't as good as store motion yet, and leaves one r/o reg
for loop to hoist.

However, i'm curious as to why we don't notice that r was invariant in
the current loop code. 
Any ideas?

>
> 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
>
>

-- 
"My girlfriend asked me how long I was going to be gone on this
tour.  I said, "the whole time."
"-Steven Wright