From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1666) id 0C2003858412; Mon, 11 Jul 2022 10:06:01 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 0C2003858412 MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Richard Biener To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-1602] More update-ssa speedup X-Act-Checkin: gcc X-Git-Author: Richard Biener X-Git-Refname: refs/heads/master X-Git-Oldrev: 06b2a2abe26554c6f9365676683d67368cbba206 X-Git-Newrev: 74526710f7f78914e51d4748527cda2d30bbac5c Message-Id: <20220711100601.0C2003858412@sourceware.org> Date: Mon, 11 Jul 2022 10:06:01 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 11 Jul 2022 10:06:01 -0000 https://gcc.gnu.org/g:74526710f7f78914e51d4748527cda2d30bbac5c commit r13-1602-g74526710f7f78914e51d4748527cda2d30bbac5c Author: Richard Biener Date: Thu Jul 7 15:23:28 2022 +0200 More update-ssa speedup When we do TODO_update_ssa_no_phi we already avoid computing dominance frontiers for all blocks - it is worth to also avoid walking all dominated blocks in the update domwalk and restrict the walk to the SEME region with the affected blocks. We can do that by walking the CFG in reverse from blocks_to_update to the common immediate dominator, marking blocks in the region and telling the domwalk to STOP when leaving it. For an artificial testcase with N adjacent loops with one unswitching opportunity that takes the incremental SSA updating off the -ftime-report radar: tree loop unswitching : 11.25 ( 3%) 0.09 ( 5%) 11.53 ( 3%) 36M ( 9%) `- tree SSA incremental : 35.74 ( 9%) 0.07 ( 4%) 36.65 ( 9%) 2734k ( 1%) improves to tree loop unswitching : 10.21 ( 3%) 0.05 ( 3%) 11.50 ( 3%) 36M ( 9%) `- tree SSA incremental : 0.66 ( 0%) 0.02 ( 1%) 0.49 ( 0%) 2734k ( 1%) for less localized updates the SEME region isn't likely constrained enough so I've restricted the extra work to TODO_update_ssa_no_phi callers. * tree-into-ssa.cc (rewrite_mode::REWRITE_UPDATE_REGION): New. (rewrite_update_dom_walker::rewrite_update_dom_walker): Update. (rewrite_update_dom_walker::m_in_region_flag): New. (rewrite_update_dom_walker::before_dom_children): If the region to update is marked, STOP at exits. (rewrite_blocks): For REWRITE_UPDATE_REGION mark the region to be updated. (dump_update_ssa): Use bitmap_empty_p. (update_ssa): Likewise. Use REWRITE_UPDATE_REGION when TODO_update_ssa_no_phi. * tree-cfgcleanup.cc (cleanup_tree_cfg_noloop): Account pending update_ssa to the caller. Diff: --- gcc/tree-cfgcleanup.cc | 6 +++- gcc/tree-into-ssa.cc | 97 +++++++++++++++++++++++++++++++++++++++++++------- 2 files changed, 90 insertions(+), 13 deletions(-) diff --git a/gcc/tree-cfgcleanup.cc b/gcc/tree-cfgcleanup.cc index b9ff6896ce6..3535a7e28a4 100644 --- a/gcc/tree-cfgcleanup.cc +++ b/gcc/tree-cfgcleanup.cc @@ -1095,7 +1095,11 @@ cleanup_tree_cfg_noloop (unsigned ssa_update_flags) /* After doing the above SSA form should be valid (or an update SSA should be required). */ if (ssa_update_flags) - update_ssa (ssa_update_flags); + { + timevar_pop (TV_TREE_CLEANUP_CFG); + update_ssa (ssa_update_flags); + timevar_push (TV_TREE_CLEANUP_CFG); + } /* Compute dominator info which we need for the iterative process below. */ if (!dom_info_available_p (CDI_DOMINATORS)) diff --git a/gcc/tree-into-ssa.cc b/gcc/tree-into-ssa.cc index 9f45e62c6d0..be71b629f97 100644 --- a/gcc/tree-into-ssa.cc +++ b/gcc/tree-into-ssa.cc @@ -240,7 +240,8 @@ enum rewrite_mode { /* Incrementally update the SSA web by replacing existing SSA names with new ones. See update_ssa for details. */ - REWRITE_UPDATE + REWRITE_UPDATE, + REWRITE_UPDATE_REGION }; /* The set of symbols we ought to re-write into SSA form in update_ssa. */ @@ -2155,11 +2156,14 @@ rewrite_update_phi_arguments (basic_block bb) class rewrite_update_dom_walker : public dom_walker { public: - rewrite_update_dom_walker (cdi_direction direction) - : dom_walker (direction, ALL_BLOCKS, (int *)(uintptr_t)-1) {} + rewrite_update_dom_walker (cdi_direction direction, int in_region_flag = -1) + : dom_walker (direction, ALL_BLOCKS, (int *)(uintptr_t)-1), + m_in_region_flag (in_region_flag) {} edge before_dom_children (basic_block) final override; void after_dom_children (basic_block) final override; + + int m_in_region_flag; }; /* Initialization of block data structures for the incremental SSA @@ -2179,6 +2183,10 @@ rewrite_update_dom_walker::before_dom_children (basic_block bb) /* Mark the unwind point for this block. */ block_defs_stack.safe_push (NULL_TREE); + if (m_in_region_flag != -1 + && !(bb->flags & m_in_region_flag)) + return STOP; + if (!bitmap_bit_p (blocks_to_update, bb->index)) return NULL; @@ -2270,8 +2278,8 @@ rewrite_update_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED) WHAT indicates what actions will be taken by the renamer (see enum rewrite_mode). - BLOCKS are the set of interesting blocks for the dominator walker - to process. If this set is NULL, then all the nodes dominated + REGION is a SEME region of interesting blocks for the dominator walker + to process. If this set is invalid, then all the nodes dominated by ENTRY are walked. Otherwise, blocks dominated by ENTRY that are not present in BLOCKS are ignored. */ @@ -2283,9 +2291,71 @@ rewrite_blocks (basic_block entry, enum rewrite_mode what) /* Recursively walk the dominator tree rewriting each statement in each basic block. */ if (what == REWRITE_ALL) - rewrite_dom_walker (CDI_DOMINATORS).walk (entry); + rewrite_dom_walker (CDI_DOMINATORS).walk (entry); else if (what == REWRITE_UPDATE) - rewrite_update_dom_walker (CDI_DOMINATORS).walk (entry); + rewrite_update_dom_walker (CDI_DOMINATORS).walk (entry); + else if (what == REWRITE_UPDATE_REGION) + { + /* First mark all blocks in the SEME region dominated by + entry and exited by blocks not backwards reachable from + blocks_to_update. Optimize for dense blocks_to_update + so instead of seeding the worklist with a copy of + blocks_to_update treat those blocks explicit. */ + auto_bb_flag in_region (cfun); + auto_vec extra_rgn; + bitmap_iterator bi; + unsigned int idx; + EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, idx, bi) + { + basic_block bb = BASIC_BLOCK_FOR_FN (cfun, idx); + bb->flags |= in_region; + } + auto_bitmap worklist; + EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, idx, bi) + { + basic_block bb = BASIC_BLOCK_FOR_FN (cfun, idx); + if (bb != entry) + { + edge_iterator ei; + edge e; + FOR_EACH_EDGE (e, ei, bb->preds) + { + if ((e->src->flags & in_region) + || dominated_by_p (CDI_DOMINATORS, e->src, bb)) + continue; + bitmap_set_bit (worklist, e->src->index); + } + } + } + while (!bitmap_empty_p (worklist)) + { + int idx = bitmap_first_set_bit (worklist); + bitmap_clear_bit (worklist, idx); + basic_block bb = BASIC_BLOCK_FOR_FN (cfun, idx); + bb->flags |= in_region; + extra_rgn.safe_push (bb); + if (bb != entry) + { + edge_iterator ei; + edge e; + FOR_EACH_EDGE (e, ei, bb->preds) + { + if ((e->src->flags & in_region) + || dominated_by_p (CDI_DOMINATORS, e->src, bb)) + continue; + bitmap_set_bit (worklist, e->src->index); + } + } + } + rewrite_update_dom_walker (CDI_DOMINATORS, in_region).walk (entry); + EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, idx, bi) + { + basic_block bb = BASIC_BLOCK_FOR_FN (cfun, idx); + bb->flags &= ~in_region; + } + for (auto bb : extra_rgn) + bb->flags &= ~in_region; + } else gcc_unreachable (); @@ -2879,7 +2949,7 @@ dump_update_ssa (FILE *file) if (!need_ssa_update_p (cfun)) return; - if (new_ssa_names && bitmap_first_set_bit (new_ssa_names) >= 0) + if (new_ssa_names && !bitmap_empty_p (new_ssa_names)) { sbitmap_iterator sbi; @@ -3389,7 +3459,7 @@ update_ssa (unsigned update_flags) /* If there are names defined in the replacement table, prepare definition and use sites for all the names in NEW_SSA_NAMES and OLD_SSA_NAMES. */ - if (bitmap_first_set_bit (new_ssa_names) >= 0) + if (!bitmap_empty_p (new_ssa_names)) { statistics_counter_event (cfun, "Incremental SSA update", 1); @@ -3398,7 +3468,7 @@ update_ssa (unsigned update_flags) /* If all the names in NEW_SSA_NAMES had been marked for removal, and there are no symbols to rename, then there's nothing else to do. */ - if (bitmap_first_set_bit (new_ssa_names) < 0 + if (bitmap_empty_p (new_ssa_names) && !cfun->gimple_df->ssa_renaming_needed) goto done; } @@ -3503,8 +3573,11 @@ update_ssa (unsigned update_flags) FOR_EACH_VEC_ELT (symbols_to_rename, i, sym) get_var_info (sym)->info.current_def = NULL_TREE; - /* Now start the renaming process at START_BB. */ - rewrite_blocks (start_bb, REWRITE_UPDATE); + /* Now start the renaming process at START_BB. When not inserting PHIs + and thus we are avoiding work on all blocks, try to confine the + rewriting domwalk to the affected region, otherwise it's not worth it. */ + rewrite_blocks (start_bb, + insert_phi_p ? REWRITE_UPDATE : REWRITE_UPDATE_REGION); /* Debugging dumps. */ if (dump_file)