https://gcc.gnu.org/bugzilla/show_bug.cgi?id=127661
--- Comment #6 from GCC Commits <cvs-commit at gcc dot gnu.org> --- The master branch has been updated by Kyrylo Tkachov <[email protected]>: 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]>
