On Mon, Nov 14, 2011 at 2:02 PM, Tom de Vries <tom_devr...@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 <t...@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. >
