Re: "Experimental" features in releases

[Daniel Berlin <dberlin at dberlin dot org>]

[apologies that this will come out threaded slightly wrong, none of my
handy mail clients feel like letting edit the references and in-reply-to
header, apparently it's not cool anymore]

> Dale Johannesen wrote:
> 
> > I wasn't aware that it was supposed to be experimental either, and it
> > wasn't explained that way when it went in (Sep 2004).  (Incomplete or
> > buggy would not be surprising, but it sounds now like we're talking
> > about fatally flawed design, which is different.)
> 

So let me clarify here by explaining how tree-loop-linear works, and
what is broken.

It's a bunch of parts, but can generally be broken into (in order):
1.Converting loops to perfect nests (convert_loop_to_perfect_nest/can_convert_loop_to_perfect_nest)
2.Verification that a loop is a perfect nest
3.gcc loop information -> iteration space info converter (gcc_loop_to_lambda_loop)
4.iteration space info manipulator transformer (lambda_*)
5.iteration space info -> gcc loop code generator (lambda_loop_to_gcc_loop)

The vast majority of the code is in the last 3 pieces, and it may have some bugs
and ICEs, but is algorithmically sound and these are just regular bugs[1].

For example, we have one ICE caused by the 6, due to an assert
for something i never had a chance to implement.  This is not a major deal
to implement (a week), i just haven't had the motivation because it doesn't 
hit that often.

There are a bunch of bugs, wrong code generation, and ICE's, caused by the first two pieces.
This is because 
1. The transformation it makes is not always legal

but

2. It doesn't verify the all the actually necessary safety conditions before transforming the loop
to a perfect nest (single exits, verifying the place it moves it to executes under
the same conditions, etc)

and

3. It doesn't always update the newly created loop correctly anyway.

Thus, it is algorithmically unsound in it's current form :)
Again, this is *only* the piece that attempts to convert loops 
to perfect nests.
This is in fact, not terribly surprising, since the algorithm used was the result of
Sebastian and I sitting at my whiteboard for 30 minutes trying to figure out
what we'd need to do to make swim happy :).

At one point, the only thing it would interchange was incredibly simple loops,
which worked out okay, and some simple perfect nests (which is where swim falls into).
Everything was more or less happy.

As our optimizers got better at cleaning up code, it seems to have started
to transform more and more perfect nests that violate the safety conditions,
but it doesn't know about it because the analysis necessary to see this is
just not there.  

It could be made sound by implementing these analysis, but doing so is
just as much work as implementing something that isn't a complete hack,
like loop distribution.  At that point, you may as well just do that (and in fact, the
analysis you need to implement is the basis of one of the common loop
distribution algorithms).

As there have been rumblings and people who said they were working on 
loop distribution at the last summit, I have simply bided my time (ie
making sure all the bugs noted are really the same bugs i know about,
etc), in the hopes that marking it experimental (which i distinctly
remember it being, but apparently is not, to my surprise) until loop
distribution was implemented would suffice, since nobody really wants
to drop our spec scores by that much,etc.

This evil plan has not worked out, because
1. nobody has implemented loop distribution
2. Mark marked one of the bugs about perfect nest conversion as P1.

Since nobody has stepped forward to do #1 in the time since the summit,
and it has reached the point where these bugs are piling up, I told Mark
in(i don't remember whether this part was mentioned),
that my fix for the PR in question, which is a 4.2 P1, would be to
remove perfect nest conversion portion.

This would leave -ftree-loop-linear in 4.2, but make it not useful for increasing
SPEC scores.  It would be useful for interchanging perfectly nested loops.
> 
> My understanding from clarifications from others is that this loop nest
> bit is somehow not quite right, but that most of it is solid.  So, I
> think that I may have read more into Dan's mail than he intended.  We
> shouldn't just to drastic conclusions, but there certainly is something
> to be clarified here.
> 
I apologize that the mail was shorter than this one is, and may have
been a bit confusing.  This is simply a side-effect of having written
it while in the middle of simultaneously moving and starting a new job.
It is only now that i have had time to sit down and write a detailed
description.
> -- 
> Mark Mitchell
> CodeSourcery
> mark@codesourcery.com
> (650) 331-3385 x713
> 
> 
[1] Note that before anyone asks, doing iteration space code generation on loops that
are not perfect nests is possible, but is a much more computationally expensive idea
Plus, in the general case, it requires generation of tons of guard statements,
which may make the transformed loop more expensive than the original.  This is a *hard*
problem, and actively researched.