Re: [PATCH, PR51005] Fix slow down of compilation of 20001226-1.c by -ftree-tail-merge

[Richard Guenther <richard dot guenther at gmail dot com>]

On Mon, Nov 14, 2011 at 2:02 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> Richard,
>
> This patch fixes the slow down in the compilation of 20001226-1.c caused by
> -ftree-tail-merge.
>
> -ftree-tree-tail-merge removes half of the 16000 basic blocks, but increases
> compilation time with a factor 2.4 from 34 seconds to 80 seconds (not counting
> the further increase of 46 seconds by verify_dominators ifdef ENABLE_CHECKING).
>
> The compilation time is due to recalculating the dominator information after
> each basic block removal. That dominator information is needed to update the
> vops after each basic block removal, if this will not be done by
> TODO_update_ssa_only_virtuals. To update the dominator info,
> iterate_fix_dominators is called, which takes a lot of time.
>
> The patch fixes this by delegating the updating of the vops to
> TODO_update_ssa_only_virtuals, and recalculating dominator info once per iteration.
>
> I have attached another patch to the PR:
> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25816 , which also delegates the
> updating of the vops to TODO_update_ssa_only_virtuals, but updates dominator
> info after each cluster.
> That patch (25816) has a better best-case time than this patch, but also a worse
> worst-case time.
>
> I think we can make a hybrid solution that chooses which approach to take
> dynamically, and take advantage of both approaches. But with the maximum number
> of iterations defaulting to 2, the amount of run-time won by a hybrid approach
> will be limited, and IMHO does not justify the extra complexity.
> If we try to dynamically limit the amount of iterations, based on the amount of
> time spent in computing dominator info, the hybrid solution starts to make
> sense. But getting this right will require quite some tuning.
> So for now I propose this simple solution.
>
> bootstrapped on and reg-tested on x86_64 and i686. Build and reg-tested on MIPS
> and ARM.
>
> ok for trunk?

Ok.

Thanks,
Richard.

> Thanks,
> - Tom
>
> 2011-11-08 ?Tom de Vries ?<tom@codesourcery.com>
>
> ? ? ? ?PR tree-optimization/51005
> ? ? ? ?* tree-ssa-tail-merge (delete_basic_block_same_succ): Rename to
> ? ? ? ?mark_basic_block_deleted.
> ? ? ? ?(update_worklist): Inline purge_bbs.
> ? ? ? ?(purge_bbs, unlink_virtual_phi, update_vuses, vop_at_entry)
> ? ? ? ?(delete_block_update_dominator_info): Remove.
> ? ? ? ?(replace_block_by): Remove update_vops parameter. ?Partially evaluate
> ? ? ? ?for update_vops == false.
> ? ? ? ?(apply_clusters): Remove update_vops parameter. ?Remove update_vops
> ? ? ? ?argument in replace_block_by call.
> ? ? ? ?(update_debug_stmts): Remove MAY_HAVE_DEBUG_STMTS test.
> ? ? ? ?(tail_merge_optimize): Remove update_vops argument to apply_clusters.
> ? ? ? ?Remove call to purge_bbs. ?Add calls to calculate_dominance_info and
> ? ? ? ?free_dominance_info. ?Add MAY_HAVE_DEBUG_STMTS ?before calling
> ? ? ? ?update_debug_stmts. ?Mark vop var for renaming, if necessary.
>