https://gcc.gnu.org/g:b8cfa0613cfb6de68eba575c7d613b340665a257
commit r17-5027-gb8cfa0613cfb6de68eba575c7d613b340665a257 Author: Kyrylo Tkachov <[email protected]> Date: Wed Sep 30 08:38:59 2026 +0200 tree-into-ssa: Prune the IDF of old virtual names by liveness [PR127661] The jump threaders copy blocks with gimple_duplicate_bb, which records each virtual definition in a copy as a replacement of the old virtual name. update_ssa then computes, in insert_updated_phi_nodes_for, the iterated dominance frontier (IDF) of the definition blocks of each old name. In a long chain of conditions this IDF covers the rest of the chain, so the cost is quadratic. In the testcase of the PR at N=2048, thread1 and thread2 give about 10k old virtual names with 27M IDF blocks in total, for 18 new PHI nodes. insert_phi_nodes_for removes the IDF blocks where the name is not live on entry. This patch computes these live-in blocks first for an old virtual name: its livein_blocks and, transitively, their predecessors that do not define it. compute_idf gets an optional bitmap and only adds and follows the blocks in it. The restricted IDF is the IDF intersected with the live-in blocks, so the PHI nodes do not change. At most one virtual name is live at any point, so the live-in blocks of the old virtual names do not overlap and the total cost is linear in the size of the CFG. Real names can have overlapping live ranges and keep the full IDF. LLVM's IDFCalculator uses the same restriction. For the testcase at -O2 on Grace, the time in "tree SSA incremental" drops by 99% at N=2048 and N=4096. The whole compilation executes 63% fewer instructions at N=2048 and 75% fewer at N=4096. The generated code does not change for the testcase, for 10 large GCC sources and for gcc.c-torture at -O2 and -O3. A temporary check that compared the PHI blocks from the full and the restricted IDF of each old virtual name found no difference on these inputs. Bootstrapped and tested on aarch64-linux-gnu and x86_64-linux-gnu. PR rtl-optimization/127661 gcc/ChangeLog: * cfganal.h (compute_idf): Add a bitmap argument, NULL by default. * cfganal.cc (compute_idf): Add the LIVE argument. If it is not NULL, only add and follow the blocks in it. * tree-into-ssa.cc (prune_unused_phi_nodes): Update the comment about computing liveness. (compute_livein_region): New function. (insert_updated_phi_nodes_for): Use it to restrict the IDF of old virtual names. Signed-off-by: Kyrylo Tkachov <[email protected]> Diff: --- gcc/cfganal.cc | 12 ++++++++--- gcc/cfganal.h | 2 +- gcc/tree-into-ssa.cc | 58 ++++++++++++++++++++++++++++++++++++++++++++++------ 3 files changed, 62 insertions(+), 10 deletions(-) diff --git a/gcc/cfganal.cc b/gcc/cfganal.cc index dedd9b648c54..ce3c72843cbf 100644 --- a/gcc/cfganal.cc +++ b/gcc/cfganal.cc @@ -1671,13 +1671,17 @@ compute_dominance_frontiers (bitmap_head *frontiers) return a bitmap with all the blocks in the iterated dominance frontier of the blocks in DEF_BLOCKS. DFS contains dominance frontier information as returned by compute_dominance_frontiers. + If LIVE is not NULL, only the blocks in LIVE are added to the result + and have their dominance frontier followed. If LIVE is the set of + blocks where the variable is live on entry, the result is the + iterated dominance frontier restricted to LIVE. The resulting set of blocks are the potential sites where PHI nodes are needed. The caller is responsible for freeing the memory allocated for the return value. */ bitmap -compute_idf (bitmap def_blocks, bitmap_head *dfs) +compute_idf (bitmap def_blocks, bitmap_head *dfs, bitmap live) { bitmap_iterator bi, bi2; unsigned bb_index, i; @@ -1704,7 +1708,8 @@ compute_idf (bitmap def_blocks, bitmap_head *dfs) as well. That makes iterating over the DFS bitmap preferential to whole bitmap operations involving also phi_insertion_points. */ EXECUTE_IF_SET_IN_BITMAP (&dfs[bb_index], 0, i, bi) - bitmap_set_bit (phi_insertion_points, i); + if (!live || bitmap_bit_p (live, i)) + bitmap_set_bit (phi_insertion_points, i); } /* Seed the work set with the initial phi_insertion_points. */ @@ -1723,7 +1728,8 @@ compute_idf (bitmap def_blocks, bitmap_head *dfs) gcc_checking_assert (bb_index < (unsigned) last_basic_block_for_fn (cfun)); EXECUTE_IF_SET_IN_BITMAP (&dfs[bb_index], 0, i, bi) - if (bitmap_set_bit (phi_insertion_points, i)) + if ((!live || bitmap_bit_p (live, i)) + && bitmap_set_bit (phi_insertion_points, i)) work_set.quick_push (i); } diff --git a/gcc/cfganal.h b/gcc/cfganal.h index 2ff41f1850ba..f293ae9777d1 100644 --- a/gcc/cfganal.h +++ b/gcc/cfganal.h @@ -78,7 +78,7 @@ extern int dfs_enumerate_from (basic_block, int, bool (*)(const_basic_block, const void *), basic_block *, int, const void *); extern void compute_dominance_frontiers (class bitmap_head *); -extern bitmap compute_idf (bitmap, class bitmap_head *); +extern bitmap compute_idf (bitmap, class bitmap_head *, bitmap = NULL); extern void bitmap_intersection_of_succs (sbitmap, sbitmap *, basic_block); extern void bitmap_intersection_of_preds (sbitmap, sbitmap *, basic_block); extern void bitmap_union_of_succs (sbitmap, sbitmap *, basic_block); diff --git a/gcc/tree-into-ssa.cc b/gcc/tree-into-ssa.cc index f0ef5afb188a..f7e2a0c59b6c 100644 --- a/gcc/tree-into-ssa.cc +++ b/gcc/tree-into-ssa.cc @@ -772,10 +772,13 @@ prune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses) return; } - /* We want to remove the unnecessary phi nodes, but we do not want to compute - liveness information, as that may be linear in the size of CFG, and if - there are lot of different variables to rewrite, this may lead to quadratic - behavior. + /* We want to remove the unnecessary phi nodes without computing the + liveness of each variable here. That takes time linear in the size of + the CFG for each variable, which is quadratic when many variables with + overlapping live ranges are rewritten. Virtual operands do not have + overlapping live ranges, so for old virtual names + insert_updated_phi_nodes_for computes the blocks where they are live on + entry, and restricts their IDF to them, before this function runs. Instead, we basically emulate standard dce. We put all uses to worklist, then for each of them find the nearest def that dominates them. If this @@ -3170,6 +3173,36 @@ release_ssa_name_after_update_ssa (tree name) } +/* Set LIVE to the blocks where the variable described by DB is live on + entry. These are the blocks in DB->LIVEIN_BLOCKS and, transitively, + their predecessors that do not define the variable. */ + +static void +compute_livein_region (def_blocks *db, bitmap live) +{ + auto_vec<int, 64> worklist; + bitmap_iterator bi; + unsigned i; + + bitmap_copy (live, db->livein_blocks); + EXECUTE_IF_SET_IN_BITMAP (live, 0, i, bi) + worklist.safe_push (i); + + while (!worklist.is_empty ()) + { + basic_block bb = BASIC_BLOCK_FOR_FN (cfun, worklist.pop ()); + edge e; + edge_iterator ei; + + FOR_EACH_EDGE (e, ei, bb->preds) + if (e->src->index >= NUM_FIXED_BLOCKS + && !bitmap_bit_p (db->def_blocks, e->src->index) + && bitmap_set_bit (live, e->src->index)) + worklist.safe_push (e->src->index); + } +} + + /* Insert new PHI nodes to replace VAR. DFS contains dominance frontier information. @@ -3215,8 +3248,21 @@ insert_updated_phi_nodes_for (tree var, bitmap_head *dfs, if (db == NULL || bitmap_empty_p (db->def_blocks)) return; - /* Compute the initial iterated dominance frontier. */ - pruned_idf = compute_idf (db->def_blocks, dfs); + /* Compute the initial iterated dominance frontier. For an old + virtual name, restrict it to the blocks where the name is live on + entry. insert_phi_nodes_for removes the other blocks anyway. At + most one virtual name is live at any point, so the live-in regions + of the old virtual names do not overlap and computing them is + linear in the size of the CFG in total. This is not true for real + names. */ + auto_bitmap region; + bitmap live = NULL; + if (TREE_CODE (var) == SSA_NAME && virtual_operand_p (var)) + { + compute_livein_region (db, region); + live = region; + } + pruned_idf = compute_idf (db->def_blocks, dfs, live); if (TREE_CODE (var) == SSA_NAME) {
