[PATCH] bb-reorder: Improve compgotos pass (PR71785)
Richard Biener
richard.guenther@gmail.com
Wed Nov 2 09:02:00 GMT 2016
On Mon, Oct 31, 2016 at 4:35 PM, Segher Boessenkool
<segher@kernel.crashing.org> 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:
>> > This patch solves this problem by simply running the duplicate_computed_gotos
>> > pass again, as long as it does any work. The patch looks much bigger than
>> > it is, because I factored out two routines to simplify the control flow.
>>
>> It's made the patch a bit difficult to read. Condensing it a bit...
>
> Well, it would have a goto crossing a loop, or two gotos crossing each
> other, otherwise. I should have done it as two patches I guess (first
> factor, then change).
>
>> > + for (;;)
>> > {
>> > + if (n_basic_blocks_for_fn (fun) <= NUM_FIXED_BLOCKS + 1)
>> > + return 0;
>>
>> This test should not be needed in the loop. This pass can never
>> collapse the function to a single basic block.
>
> Yeah maybe, but that relies on quite a few assumptions. This is strictly
> an optimisation anyway, will move it outside the loop.
>
>> > + basic_block bb;
>> > + FOR_EACH_BB_FN (bb, fun)
>> > + {
>> > + /* Build the reorder chain for the original order of blocks. */
>> > + if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
>> > + bb->aux = bb->next_bb;
>> > + }
>> >
>> > + duplicate_computed_gotos_find_candidates (fun, candidates, max_size);
>> >
>> > + bool changed = false;
>> > + if (!bitmap_empty_p (candidates))
>> > + changed = duplicate_computed_gotos_do_duplicate (fun, candidates);
>> >
>> > + if (changed)
>> > + fixup_partitions ();
>> > +
>> > + 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 fear this is quadratic
complexity in the number of edges to the compgoto block (and the size of the
function). Can't the unfactoring perform the "cleanup" we rely on here?
>> > /* Merge the duplicated blocks into predecessors, when possible. */
>> > + if (changed)
>> > + cleanup_cfg (0);
>> > + else
>> > + break;
>> > }
>>
>> Maybe a gcc_assert that the loop doesn't iterate more often than num_edges?
>
> Good plan (num blocks even).
>
> Thanks,
>
>
> Segher
More information about the Gcc-patches
mailing list