Re: [PATCH] bb-reorder: Improve compgotos pass (PR71785)

[Segher Boessenkool <segher at kernel dot crashing dot org>]

On Wed, Nov 02, 2016 at 11:39:20AM +0100, Steven Bosscher wrote:
>  On Wed, Nov 2, 2016 at 10:02 AM, Richard Biener
> <richard.guenther@gmail.com> wrote:
> > On Mon, Oct 31, 2016 at 4:35 PM, Segher Boessenkool wrote:
> >> On Mon, Oct 31, 2016 at 04:09:48PM +0100, Steven Bosscher wrote:
> >>> On Sun, Oct 30, 2016 at 8:10 PM, Segher Boessenkool wrote:
> >>> > +      cfg_layout_finalize ();
> >>>
> >>> I don't think you have to go into/out-of cfglayout mode for each iteration.
> >>
> >> Yeah probably.  I was too lazy :-)  It needs the cleanup_cfg every
> >> iteration though, I was afraid that interacts.
> >
> > Ick.  Why would it need a cfg-cleanup every iteration?
> 
> I don't believe it needs a cleanup on every iteration. One cleanup at
> the end should work fine.

But as the comment there says:

      /* Merge the duplicated blocks into predecessors, when possible.  */
      cleanup_cfg (0);

(this is not a new comment), and without merging blocks this whole
patch does zilch.

There is no need to create new basic blocks at all (can replace the
final branch in a block with a copy of the whole block it jumps to,
instead); and then it is painfully obvious that switching to layout
mode here is pointless, too.

Do you want me to do that?

Btw, this isn't quadratic anyway; it is a constant number (the maximal
length allowed of the block to copy) linear.  Unless there are unboundedly
many forwarder blocks, which there shouldn't be, but I cannot prove that.

And on a testcase with 2000 cases (instead of the 4 in the testcase in
the PR) this pass takes less than 1% of the compiler runtime; and in
the normal cases (no computed gotos to unfactor) it does the same as
before.


Segher