[PATCH 4/5] tree-into-ssa: Prune the IDF of old virtual names by liveness [PR127661]
Richard Biener
richard.guenther@gmail.com
Sun Oct 11 14:56:51 GMT 2026
On Fri, Oct 9, 2026 at 3:20 PM Kyrylo Tkachov <ktkachov@nvidia.com> wrote:
>
>
>
> > On 9 Oct 2026, at 14:38, Richard Biener <richard.guenther@gmail.com> wrote:
> >
> > On Fri, Oct 9, 2026 at 11:42 AM Kyrylo Tkachov <ktkachov@nvidia.com> wrote:
> >>
> >> Hi Richard,
> >>
> >>> On 6 Oct 2026, at 12:09, Richard Biener <richard.guenther@gmail.com> wrote:
> >>>
> >>> On Tue, Oct 6, 2026 at 11:36 AM <ktkachov@nvidia.com> wrote:
> >>>>
> >>>> From: Kyrylo Tkachov <ktkachov@nvidia.com>
> >>>>
> >>>> 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.
> >>>>
> >>>> Bootstrapped and tested as a series on aarch64-linux-gnu and
> >>>> x86_64-linux-gnu.
> >>>>
> >>>> Ok for trunk?
> >>>
> >>> I fiddled a lot with compute_idf in the past and the problem is that
> >>> such "optimizations" make most other cases slower. So can you at
> >>> least go back and see which PRs past changes were done for and
> >>> re-benchmark their testcases as well?
> >>>
> >>
> >> From what I can find these are PR26854, PR26830, PR28071, PR54146, PR11480, PR114855.
> >> In all these cases this patch reduces the compile time by <1% (largest reduction -O.31% on PR114480) and doesn’t increase anything.
> >
> > Thanks for checking. The comment in prune_unused_phi_nodes warns
> > about computing liveness, can you please update that so it's not misleading?
> >
> > Otherwise OK.
>
> Thanks, I propose to commit this version with the comment updated
> Kyrill
LGTM
>
> >
> > Thanks,
> > Richard.
> >
> >> Thanks,
> >> Kyrill
> >>
> >>> IMO artificial testcases shouldn't be the ones we optimize - important
> >>> are real-word cases of auto-generated code that GCC compiles.
> >>>
> >>> Folding in part of the pruning we do on the IDF after-the-fact proved
> >>> difficult.
> >>>
> >>> In particular jump threading should only need to insert PHI nodes at
> >>> the exit block (if at all). So I wonder if we can introduce a "limited"
> >>> TODO_update_ssa_no_phi aka TODO_update_ssa_phi_blocks_specified
> >>> and explicitly register those blocks?
> >>>
> >>> The vectorizer uses hand-crafted update-ssa for some of its transforms,
> >>> doing that for jump threading might be another possibility to solve the
> >>> issue. Updating the SSA form should be mostly trivial as the path to
> >>> update is linear.
> >>>
> >>> Richard.
> >>>
> >>>> Thanks,
> >>>> Kyrill
> >>>>
> >>>> Cc: Jeff Law <jeffrey.law@oss.qualcomm.com>
> >>>>
> >>>> gcc/ChangeLog:
> >>>>
> >>>> PR rtl-optimization/127661
> >>>> * 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 (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 <ktkachov@nvidia.com>
> >>>> ---
> >>>> gcc/cfganal.cc | 12 ++++++++---
> >>>> gcc/cfganal.h | 2 +-
> >>>> gcc/tree-into-ssa.cc | 47 ++++++++++++++++++++++++++++++++++++++++++--
> >>>> 3 files changed, 55 insertions(+), 6 deletions(-)
> >>>>
> >>>> diff --git a/gcc/cfganal.cc b/gcc/cfganal.cc
> >>>> index dedd9b648c5..ce3c72843cb 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 2ff41f1850b..f293ae9777d 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 f0ef5afb188..808ba982ecc 100644
> >>>> --- a/gcc/tree-into-ssa.cc
> >>>> +++ b/gcc/tree-into-ssa.cc
> >>>> @@ -3170,6 +3170,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 +3245,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)
> >>>> {
> >>>> --
> >>>> 2.50.1 (Apple Git-155)
>
>
More information about the Gcc-patches
mailing list