Re: [PATCH] More aggressive jump bypassing.

[Roger Sayle <roger at eyesopen dot com>]

On Mon, 17 Jun 2002, Jan Hubicka wrote:

> > Jump bypassing is now able to determine that both branches of the
> > conditional expression set i to a value that makes the loop condition
> > initially true.  Hence it redirects both edges to after the loop
> > condition, effectively turning the while() loop into a do-while loop.
> > Unfortunately, find_and_verify_loops calling mark_loop_jump determines
> > that there is more than one jump into the loop (even though all
> > entries are to the same label), and therefore marks the loop invalid
> > for the usual loop optimizations.
> >
> > Hopefully, now I've explained the problem the GCC "loop.c" experts
> > might be able to look into the issue.  I'm not sure, for example, if
> > the new loop analyzers that use the CFG on the cfg-branch can handle
> > this already.
>
> They can find any loop in the code as long as you don't create multiple
> entry points (irreducible loops).

The control flow graph in the given example is still reducible. It
has a single "entry point", but multiple entry edges to that entry
point.  Infact the entire loop contains only a single label.  Its still
possible to create a latch block (by creating a new basic block and
redirecting all non back-edges) etc...  Its just that the current GCC
code has stricter restrictions than the conventional definition of
reducibility.

I'm not saying that jump bypassing won't create irreducible CFGs,
its just that even for the example I presented, loop still gives up.


> Unfortunately there is long way to obsolete current loop optimizer,
> but what may or may not be a win is to run gcse after the loop.
> I believe that earlier loop is run, the better is chance that we
> didn't mangled up the structures.

An interesting idea.  Certainly worth benchmarking.  But it could
easily go either way, and performing data-flow analysis after
loop peeling/unrolling etc... may adversely affect compile times.

Roger
--