Re: Re: LOOP_HEADER tree code?

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

> On Thu, 2006-10-26 at 00:45 +0200, Zdenek Dvorak wrote:
> 
> > actually, that will be trivial once jump threading updates loop properly
> > (I have a patch for that).
> I'd like to see that.
> 
> I recall poking at having threading update things like loop exit
> points and gave up.  The problem is you could thread to a loop 
> exit, which in turn might move the loop exit edge to a new
> point in the CFG.  Furthermore, all the statements dominated
> by the new loop exit edge are no longer in the loop (when they
> previously were part of the loop).
> 
> It's possible these problems could be solved by querying the
> dominator structures, but IIRC they aren't accurate at this
> point.

what my patch does is keeping the loops up-to-date.
To do that, I had to disable some of the threadings (mostly those
that made us create new subloops of the existing loops); on the other
hand, some other threadings that are now forbidden turned out to be
valid, and overall I think none of the important cases is affected.

I will update and submit the patch sometime later this week.

> Your updates may be simpler/easier since you're updating
> something different.
> 
> [ This was a couple years ago, so if I've got details wrong,
>   please forgive me. ] 
> 
> 
> > Which is IMHO good, as it will at least ensure that they preserve loops,
> > in case it is really relevant for them -- just now, I do not see how
> > code motion could affect loop structures (unless it changes CFG) -- do
> > you have some concrete example of transformation that might be made
> > more problematic by the existence of LOOP_HEADER node?
> It wasn't a matter of changing the loop structure -- the RTL loop
> optimizer had 3 or 4 notes IIRC and the location of each note
> in relation to code labels and other insns was important.  Code
> motion would sometimes place an insn between the note and a
> label.  That in turn caused the loop optimizer to barf.  There
> were also problems with edge splitting doing similar kinds of
> things.

Main source of these problems with the loop notes was that their
validity was never verified (only in the loop optimizer itself);
so you did not know you made something wrong with them, until
some problem in the loop optimizer surfaced.  This should not be
the case with LOOP_HEADER statements, as their validity would be
verified (in verify_flow_info or verify_loop_structures).

What made the problems with loop notes worse was that loop discovery
itself was based on them.  This meant that it was quite easy to get
the loop optimizer confused if you changed the positions of the notes.
Since nowadays the loop discovery is based purely on CFG, this would not
be a problem.

For these reasons, I do not think that making the optimizers keep LOOP_HEADER
statements and loops in sync would be too difficult (at least not more
difficult than making the optimizers to keep CFG and loop structures in
sync).

Zdenek