[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