[PATCH, PR51005] Fix slow down of compilation of 20001226-1.c by -ftree-tail-merge
Richard Guenther
richard.guenther@gmail.com
Mon Nov 14 21:08:00 GMT 2011
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.
>
More information about the Gcc-patches
mailing list