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 AC130385734E for ; Thu, 7 Jul 2022 07:05:38 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org AC130385734E Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 6ECBD1F9E3 for ; Thu, 7 Jul 2022 07:05:37 +0000 (UTC) Received: from [10.168.4.163] (unknown [10.168.4.163]) (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 67C0D2C141 for ; Thu, 7 Jul 2022 07:05:37 +0000 (UTC) Date: Thu, 7 Jul 2022 09:05:37 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] Speed up LC SSA rewrite 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 07:05:40 -0000 Message-ID: <20220707070537.CM2AqLaqsigRvMZDSfdq0VccxIgx58Tkbt-u3u7_7II@z> The following avoids collecting all loops exit blocks into bitmaps and computing the union of those up the loop tree possibly repeatedly. Instead we make sure to do this only once for each loop with a definition possibly requiring a LC phi node plus make sure to leverage recorded exits to avoid the intermediate bitmap allocation. Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed. * tree-ssa-loop-manip.cc (compute_live_loop_exits): Take the def loop exit block bitmap as argument instead of re-computing it here. (add_exit_phis_var): Adjust. (loop_name_cmp): New function. (add_exit_phis): Sort variables to insert LC PHI nodes after definition loop, for each definition loop compute the exit block bitmap once. (get_loops_exit): Remove. (rewrite_into_loop_closed_ssa_1): Do not pre-record all loop exit blocks into bitmaps. Record loop exits if required. --- gcc/tree-ssa-loop-manip.cc | 95 ++++++++++++++++++++++---------------- 1 file changed, 56 insertions(+), 39 deletions(-) diff --git a/gcc/tree-ssa-loop-manip.cc b/gcc/tree-ssa-loop-manip.cc index 9f3b62652ea..0324ff60a0f 100644 --- a/gcc/tree-ssa-loop-manip.cc +++ b/gcc/tree-ssa-loop-manip.cc @@ -183,12 +183,14 @@ find_sibling_superloop (class loop *use_loop, class loop *def_loop) /* DEF_BB is a basic block containing a DEF that needs rewriting into loop-closed SSA form. USE_BLOCKS is the set of basic blocks containing uses of DEF that "escape" from the loop containing DEF_BB (i.e. blocks in - USE_BLOCKS are dominated by DEF_BB but not in the loop father of DEF_B). + USE_BLOCKS are dominated by DEF_BB but not in the loop father of DEF_BB). ALL_EXITS[I] is the set of all basic blocks that exit loop I. + DEF_LOOP_EXITS is a bitmap of loop exit blocks that exit the loop + containing DEF_BB or its outer loops. - Compute the subset of LOOP_EXITS that exit the loop containing DEF_BB - or one of its loop fathers, in which DEF is live. This set is returned - in the bitmap LIVE_EXITS. + Compute the subset of loop exit destinations that exit the loop + containing DEF_BB or one of its loop fathers, in which DEF is live. + This set is returned in the bitmap LIVE_EXITS. Instead of computing the complete livein set of the def, we use the loop nesting tree as a form of poor man's structure analysis. This greatly @@ -197,18 +199,17 @@ find_sibling_superloop (class loop *use_loop, class loop *def_loop) static void compute_live_loop_exits (bitmap live_exits, bitmap use_blocks, - bitmap *loop_exits, basic_block def_bb) + basic_block def_bb, bitmap def_loop_exits) { unsigned i; bitmap_iterator bi; class loop *def_loop = def_bb->loop_father; unsigned def_loop_depth = loop_depth (def_loop); - bitmap def_loop_exits; /* Normally the work list size is bounded by the number of basic blocks in the largest loop. We don't know this number, but we can be fairly sure that it will be relatively small. */ - auto_vec worklist (MAX (8, n_basic_blocks_for_fn (cfun) / 128)); + auto_vec worklist (MAX (8, n_basic_blocks_for_fn (cfun) / 128)); EXECUTE_IF_SET_IN_BITMAP (use_blocks, 0, i, bi) { @@ -272,13 +273,7 @@ compute_live_loop_exits (bitmap live_exits, bitmap use_blocks, } } - def_loop_exits = BITMAP_ALLOC (&loop_renamer_obstack); - for (class loop *loop = def_loop; - loop != current_loops->tree_root; - loop = loop_outer (loop)) - bitmap_ior_into (def_loop_exits, loop_exits[loop->num]); bitmap_and_into (live_exits, def_loop_exits); - BITMAP_FREE (def_loop_exits); } /* Add a loop-closing PHI for VAR in basic block EXIT. */ @@ -322,23 +317,33 @@ add_exit_phi (basic_block exit, tree var) Exits of the loops are stored in LOOP_EXITS. */ static void -add_exit_phis_var (tree var, bitmap use_blocks, bitmap *loop_exits) +add_exit_phis_var (tree var, bitmap use_blocks, bitmap def_loop_exits) { unsigned index; bitmap_iterator bi; basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var)); - bitmap live_exits = BITMAP_ALLOC (&loop_renamer_obstack); gcc_checking_assert (! bitmap_bit_p (use_blocks, def_bb->index)); - compute_live_loop_exits (live_exits, use_blocks, loop_exits, def_bb); + auto_bitmap live_exits (&loop_renamer_obstack); + compute_live_loop_exits (live_exits, use_blocks, def_bb, def_loop_exits); EXECUTE_IF_SET_IN_BITMAP (live_exits, 0, index, bi) { add_exit_phi (BASIC_BLOCK_FOR_FN (cfun, index), var); } +} - BITMAP_FREE (live_exits); +static int +loop_name_cmp (const void *p1, const void *p2) +{ + auto l1 = (const std::pair *)p1; + auto l2 = (const std::pair *)p2; + if (l1->first < l2->first) + return -1; + else if (l1->first > l2->first) + return 1; + return 0; } /* Add exit phis for the names marked in NAMES_TO_RENAME. @@ -346,31 +351,38 @@ add_exit_phis_var (tree var, bitmap use_blocks, bitmap *loop_exits) names are used are stored in USE_BLOCKS. */ static void -add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap *loop_exits) +add_exit_phis (bitmap names_to_rename, bitmap *use_blocks) { unsigned i; bitmap_iterator bi; + /* Sort names_to_rename after definition loop so we can avoid re-computing + def_loop_exits. */ + auto_vec > names (bitmap_count_bits (names_to_rename)); EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi) { - add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits); + tree name = ssa_name (i); + loop_p def_loop = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father; + names.quick_push (std::make_pair (def_loop->num, i)); } -} + names.qsort (loop_name_cmp); -/* Fill the array of bitmaps LOOP_EXITS with all loop exit edge targets. */ - -static void -get_loops_exits (bitmap *loop_exits) -{ - unsigned j; - edge e; - - for (auto loop : loops_list (cfun, 0)) + auto_bitmap def_loop_exits (&loop_renamer_obstack); + loop_p last_def_loop = NULL; + for (auto p : names) { - auto_vec exit_edges = get_loop_exit_edges (loop); - loop_exits[loop->num] = BITMAP_ALLOC (&loop_renamer_obstack); - FOR_EACH_VEC_ELT (exit_edges, j, e) - bitmap_set_bit (loop_exits[loop->num], e->dest->index); + loop_p def_loop = get_loop (cfun, p.first); + if (def_loop != last_def_loop) + { + bitmap_clear (def_loop_exits); + last_def_loop = def_loop; + for (class loop *loop = def_loop; loop != current_loops->tree_root; + loop = loop_outer (loop)) + for (auto exit = loop->exits->next; exit->e; exit = exit->next) + bitmap_set_bit (def_loop_exits, exit->e->dest->index); + } + add_exit_phis_var (ssa_name (p.second), use_blocks[p.second], + def_loop_exits); } } @@ -566,16 +578,21 @@ rewrite_into_loop_closed_ssa_1 (bitmap changed_bbs, unsigned update_flag, if (!bitmap_empty_p (names_to_rename)) { - /* An array of bitmaps where LOOP_EXITS[I] is the set of basic blocks - that are the destination of an edge exiting loop number I. */ - bitmap *loop_exits = XNEWVEC (bitmap, number_of_loops (cfun)); - get_loops_exits (loop_exits); + bool release_recorded_exits_p = false; + if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) + { + /* Doing one scan over the whole function is cheaper than + traversing the loop tree and gathering BBs of each loop. */ + record_loop_exits (); + release_recorded_exits_p = true; + } /* Add the PHI nodes on exits of the loops for the names we need to rewrite. */ - add_exit_phis (names_to_rename, use_blocks, loop_exits); + add_exit_phis (names_to_rename, use_blocks); - free (loop_exits); + if (release_recorded_exits_p) + release_recorded_exits (cfun); /* Fix up all the names found to be used outside their original loops. */ -- 2.35.3