From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by sourceware.org (Postfix) with ESMTPS id 256A23858D32 for ; Thu, 7 Jul 2022 11:03:48 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 256A23858D32 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id ED5D01FEC7 for ; Thu, 7 Jul 2022 11:03:46 +0000 (UTC) Received: from wotan.suse.de (wotan.suse.de [10.160.0.1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id E60AC2C141 for ; Thu, 7 Jul 2022 11:03:46 +0000 (UTC) Date: Thu, 7 Jul 2022 11:03:46 +0000 (UTC) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] Speedup update-ssa some more User-Agent: Alpine 2.22 (LSU 394 2020-01-19) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-Spam-Status: No, score=-10.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, MISSING_MID, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 07 Jul 2022 11:03:51 -0000 Message-ID: <20220707110346.auFJqbrM2nbRFN09be34DBpGVgZv1cCgZ4kcA4BYg5A@z> The following avoids copying an sbitmap and one traversal by avoiding to re-allocate old_ssa_names when not necessary. In addition this actually checks what the comment before PHI insert iterating promises, that the old_ssa_names set does not grow. Bootstrapped on x86_64-unknown-linux-gnu, testing in progress. * tree-into-ssa.cc (iterating_old_ssa_names): New. (add_new_name_mapping): Grow {new,old}_ssa_names separately and only when actually needed. Assert we are not growing the old_ssa_names set when iterating over it. (update_ssa): Remove old_ssa_names copying and empty_p query, note we are iterating over it and expect no set changes. --- gcc/tree-into-ssa.cc | 36 ++++++++++++++++++++---------------- 1 file changed, 20 insertions(+), 16 deletions(-) diff --git a/gcc/tree-into-ssa.cc b/gcc/tree-into-ssa.cc index c90651c3a89..9f45e62c6d0 100644 --- a/gcc/tree-into-ssa.cc +++ b/gcc/tree-into-ssa.cc @@ -587,6 +587,8 @@ add_to_repl_tbl (tree new_tree, tree old) bitmap_set_bit (*set, SSA_NAME_VERSION (old)); } +/* Debugging aid to fence old_ssa_names changes when iterating over it. */ +static bool iterating_old_ssa_names; /* Add a new mapping NEW_TREE -> OLD REPL_TBL. Every entry N_i in REPL_TBL represents the set of names O_1 ... O_j replaced by N_i. This is @@ -602,10 +604,15 @@ add_new_name_mapping (tree new_tree, tree old) /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our caller may have created new names since the set was created. */ - if (SBITMAP_SIZE (new_ssa_names) <= num_ssa_names - 1) + if (SBITMAP_SIZE (new_ssa_names) <= SSA_NAME_VERSION (new_tree)) { unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR; new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0); + } + if (SBITMAP_SIZE (old_ssa_names) <= SSA_NAME_VERSION (old)) + { + gcc_assert (!iterating_old_ssa_names); + unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR; old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0); } @@ -619,8 +626,11 @@ add_new_name_mapping (tree new_tree, tree old) /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES, respectively. */ + if (iterating_old_ssa_names) + gcc_assert (bitmap_bit_p (old_ssa_names, SSA_NAME_VERSION (old))); + else + bitmap_set_bit (old_ssa_names, SSA_NAME_VERSION (old)); bitmap_set_bit (new_ssa_names, SSA_NAME_VERSION (new_tree)); - bitmap_set_bit (old_ssa_names, SSA_NAME_VERSION (old)); } @@ -3460,20 +3470,14 @@ update_ssa (unsigned update_flags) bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack); compute_dominance_frontiers (dfs); - if (bitmap_first_set_bit (old_ssa_names) >= 0) - { - sbitmap_iterator sbi; - - /* insert_update_phi_nodes_for will call add_new_name_mapping - when inserting new PHI nodes, so the set OLD_SSA_NAMES - will grow while we are traversing it (but it will not - gain any new members). Copy OLD_SSA_NAMES to a temporary - for traversal. */ - auto_sbitmap tmp (SBITMAP_SIZE (old_ssa_names)); - bitmap_copy (tmp, old_ssa_names); - EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, sbi) - insert_updated_phi_nodes_for (ssa_name (i), dfs, update_flags); - } + /* insert_update_phi_nodes_for will call add_new_name_mapping + when inserting new PHI nodes, but it will not add any + new members to OLD_SSA_NAMES. */ + iterating_old_ssa_names = true; + sbitmap_iterator sbi; + EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi) + insert_updated_phi_nodes_for (ssa_name (i), dfs, update_flags); + iterating_old_ssa_names = false; symbols_to_rename.qsort (insert_updated_phi_nodes_compare_uids); FOR_EACH_VEC_ELT (symbols_to_rename, i, sym) -- 2.35.3