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

[Richard Biener]

On Wed, Nov 2, 2016 at 4:27 PM, Segher Boessenkool
<segher@kernel.crashing.org> wrote:
> On Wed, Nov 02, 2016 at 02:51:41PM +0100, Richard Biener wrote:
>> >> 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.
>>
>> Well, you iterate calling functions (find candidates, merge, cleanup-cfg) that
>> walk the whole function.  So unless the number of iterations is bound
>> with a constant I call this quadratic (in function size).
>
> It is bounded (with that caveat above): new candidates will be bigger than
> the block merged into it, so there won't be more than
> PARAM_MAX_GOTO_DUPLICATION_INSNS passes.
>
> But I can make it all work simpler, in non-layout mode, if you prefer.

Iteration is fine but we should restrict where we look for new
candidates.  Likewise
block merging opportunities should be easier to exploit than by
running cfg-cleanup...

I'm just thinking of those gigantic machine-generated state machines where we
ATM do quite well (at least at -O1 ...) with respect to compile-time.

Richard.

>
> Segher