On Thu, Sep 10, 2026 at 01:43:09PM +0200, Richard Biener wrote:
> On Thu, 10 Sep 2026, Aldy Hernandez wrote:
>
> > We recompute the per-path stats at every node of the search, which is
> > rather expensive it turns out. There was a note hidden in the
> > original code saying we should do this incrementally, and this commit
> > does so and gives us a 7.8% improvement in the threader.
> >
> > Tested on ppc64le Linux.
> >
> > Over a corpus of .ii files from a stage1 bootstrap the assembly is
> > identical. Also, I instrumented the compiler before and after this
> > patch, and verified that the path and stats are identical, so
> > really... a NFC.
> >
> > gcc/ChangeLog:
> >
> > * tree-ssa-threadbackward.cc (back_threader_profitability): Add
> > push_bb, pop_bb, m_loop, unwind_state and m_unwind; add n_insns
> > to path_stats.
> > (back_threader_profitability::back_threader_profitability):
> > Initialize m_loop and m_stats.
> > (back_threader_profitability::account_bb): Return the number of
> > insns in the block.
> > (back_threader_profitability::push_bb): New.
> > (back_threader_profitability::pop_bb): New.
> > (back_threader_profitability::possibly_profitable_path_p): Use
> > the accumulated stats.
> > (back_threader::find_paths_to_names): Call push_bb/pop_bb.
> > ---
> > gcc/tree-ssa-threadbackward.cc | 110 ++++++++++++++++++++-------------
> > 1 file changed, 68 insertions(+), 42 deletions(-)
> >
> > diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc
> > index 1ae32312968..03a7e1db50c 100644
> > --- a/gcc/tree-ssa-threadbackward.cc
> > +++ b/gcc/tree-ssa-threadbackward.cc
> > @@ -62,24 +62,40 @@ class back_threader_profitability
> > {
> > public:
> > back_threader_profitability (bool speed_p, gimple *stmt);
> > + void push_bb (const vec<basic_block> &);
> > + void pop_bb ();
> > bool possibly_profitable_path_p (const vec<basic_block> &, bool *);
> > bool profitable_path_p (const vec<basic_block> &,
> > edge taken, bool *irreducible_loop);
> > private:
> > - void account_bb (basic_block, bool);
> > + int account_bb (basic_block, bool);
> > const bool m_speed_p;
> > int m_exit_jump_benefit;
> > bool m_threaded_multiway_branch;
> > - // The following are computed by possibly_profitable_path_p
> > + // The loop the path starts in, i.e. m_path[0]->loop_father.
> > + class loop *m_loop;
> > + // The following are accumulated by push_bb as the path grows and
> > + // restored by pop_bb as it shrinks.
> > struct path_stats
> > {
> > + int n_insns;
> > bool threaded_through_latch;
> > bool multiway_branch_in_path;
> > bool contains_hot_bb;
> > bool unprofitable_bb;
> > };
> > path_stats m_stats;
> > + // Number of insns on the path, less the branch we get to remove.
> > int m_n_insns;
> > + // One entry per push. These are the stats as they stood before that
> > push,
> > + // and the insns of the block. Basically the entry pushed for m_path[i]
> > + // accounts m_path[i - 1].
> > + struct unwind_state
> > + {
> > + path_stats stats;
> > + int bb_insns;
> > + };
>
> the m_n_insns / path_stats.n_insins and unwind_state bb_insns thing
> is a bit confusing? Why is path_stats.n_insns not the overall
> number of insns on the path and simply pushed/popped like all
> the rest?
Ughh.. Agreed, n_insns and m_n_insns were confusing. I've removed
m_n_insns and it's now a net_insns() accessor. I think this reads
clearer.
account_bb returns the count only so push_bb can record it for the
per block "(N insns)" dump. Added a comment in the code saying so.
How's the attached version?
Aldy
>From f0225944922c2d06bad0872c854f3df2d99a2e65 Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <[email protected]>
Date: Thu, 10 Sep 2026 12:18:35 +0000
Subject: [PATCH] backthreader: compute path profitability incrementally
We recompute the per-path stats at every node of the search, which is
rather expensive it turns out. There was a note hidden in the
original code saying we should do this incrementally, and this commit
does so and gives us a 7.8% improvement in the threader.
Over a corpus of .ii files from a stage1 bootstrap the assembly is
identical. Also, I instrumented the compiler before and after this
patch, and verified that the path and stats are identical, so
really... a NFC.
gcc/ChangeLog:
* tree-ssa-threadbackward.cc (back_threader_profitability): Add
push_bb, pop_bb, m_loop, unwind_state and m_unwind; add n_insns
to path_stats; replace m_n_insns with a net_insns accessor.
(back_threader_profitability::back_threader_profitability):
Initialize m_loop and m_stats.
(back_threader_profitability::account_bb): Return the number of
insns in the block.
(back_threader_profitability::push_bb): New.
(back_threader_profitability::pop_bb): New.
(back_threader_profitability::possibly_profitable_path_p): Use
the accumulated stats.
(back_threader_profitability::profitable_path_p): Likewise.
(back_threader::find_paths_to_names): Call push_bb/pop_bb.
---
gcc/tree-ssa-threadbackward.cc | 142 +++++++++++++++++++--------------
1 file changed, 81 insertions(+), 61 deletions(-)
diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc
index 1ae32312968..449dfcd3ffe 100644
--- a/gcc/tree-ssa-threadbackward.cc
+++ b/gcc/tree-ssa-threadbackward.cc
@@ -62,24 +62,40 @@ class back_threader_profitability
{
public:
back_threader_profitability (bool speed_p, gimple *stmt);
+ void push_bb (const vec<basic_block> &);
+ void pop_bb ();
bool possibly_profitable_path_p (const vec<basic_block> &, bool *);
bool profitable_path_p (const vec<basic_block> &,
edge taken, bool *irreducible_loop);
private:
- void account_bb (basic_block, bool);
+ int account_bb (basic_block, bool);
+ // Number of insns on the path, less the branch we get to remove.
+ int net_insns () const { return m_stats.n_insns - m_exit_jump_benefit; }
const bool m_speed_p;
int m_exit_jump_benefit;
bool m_threaded_multiway_branch;
- // The following are computed by possibly_profitable_path_p
+ // The loop the path starts in, i.e. m_path[0]->loop_father.
+ class loop *m_loop;
+ // The following are accumulated by push_bb as the path grows and
+ // restored by pop_bb as it shrinks.
struct path_stats
{
+ int n_insns;
bool threaded_through_latch;
bool multiway_branch_in_path;
bool contains_hot_bb;
bool unprofitable_bb;
};
path_stats m_stats;
- int m_n_insns;
+ // One entry per push. These are the stats as they stood before that push,
+ // and the insns of the block. Basically the entry pushed for m_path[i]
+ // accounts m_path[i - 1].
+ struct unwind_state
+ {
+ path_stats stats;
+ int bb_insns;
+ };
+ auto_vec<unwind_state, 20> m_unwind;
};
back_threader_profitability::back_threader_profitability (bool speed_p,
@@ -92,15 +108,20 @@ back_threader_profitability::back_threader_profitability (bool speed_p,
// particular it estimates further DCE from eliminating the exit
// control stmt.
m_exit_jump_benefit = estimate_num_insns (last, &eni_size_weights);
+ m_loop = NULL;
+ m_stats = path_stats ();
}
/* Account for BB in the cumulative stats for the path being threaded.
CHECK_MULTIWAY is true for all blocks except the block whose branch
- we are going to eliminate. */
+ we are going to eliminate. Return the number of insns in BB, which
+ PUSH_BB records so the dump can print a per-block count. */
-void
+int
back_threader_profitability::account_bb (basic_block bb, bool check_multiway)
{
+ int n_insns = 0;
+
if (!m_stats.contains_hot_bb && m_speed_p)
m_stats.contains_hot_bb |= optimize_bb_for_speed_p (bb);
@@ -117,12 +138,12 @@ back_threader_profitability::account_bb (basic_block bb, bool check_multiway)
|| gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P))
{
m_stats.unprofitable_bb = true;
- return;
+ return n_insns;
}
/* Do not count empty statements and labels. */
if (gimple_code (stmt) != GIMPLE_NOP
&& !is_gimple_debug (stmt))
- m_n_insns += estimate_num_insns (stmt, &eni_size_weights);
+ n_insns += estimate_num_insns (stmt, &eni_size_weights);
}
/* We do not look at the block with the threaded branch in this loop.
@@ -136,6 +157,42 @@ back_threader_profitability::account_bb (basic_block bb, bool check_multiway)
|| gimple_code (last) == GIMPLE_GOTO))
m_stats.multiway_branch_in_path = true;
}
+
+ return n_insns;
+}
+
+/* Update the stats after a block has been appended to PATH. */
+
+void
+back_threader_profitability::push_bb (const vec<basic_block> &path)
+{
+ unwind_state state = { m_stats, /*bb_insns=*/0 };
+
+ unsigned n = path.length ();
+ if (n == 1)
+ m_loop = path[0]->loop_father;
+ else
+ {
+ /* Appending a block makes the previous entry block part of the copied
+ path, so that's where to account for now. */
+ unsigned copied = n - 2;
+ bool check_multiway = copied > 0;
+ state.bb_insns = account_bb (path[copied], check_multiway);
+ m_stats.n_insns += state.bb_insns;
+ }
+ m_unwind.safe_push (state);
+
+ /* Note if we thread through the latch, we will want to include the
+ last entry in the array when determining if we thread through the
+ loop latch. */
+ if (m_loop->latch == path[n - 1])
+ m_stats.threaded_through_latch = true;
+}
+
+void
+back_threader_profitability::pop_bb ()
+{
+ m_stats = m_unwind.pop ().stats;
}
// Back threader flags.
@@ -440,6 +497,7 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting,
return;
m_path.safe_push (bb);
+ profit.push_bb (m_path);
// Try to resolve the path without looking back. Avoid resolving paths
// we know are large but are not (yet) recognized as Finite State Machine.
@@ -576,6 +634,7 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting,
param_max_jump_thread_paths);
// Reset things to their original state.
+ profit.pop_bb ();
m_path.pop ();
m_visited_bbs.remove (bb);
}
@@ -685,42 +744,10 @@ back_threader_profitability::possibly_profitable_path_p
if (m_path.length () <= 1)
return false;
- loop_p loop = m_path[0]->loop_father;
+ loop_p loop = m_loop;
- // We recompute the following, when we rewrite possibly_profitable_path_p
- // to work incrementally on added BBs we have to unwind them on backtracking
- m_n_insns = 0;
- m_stats = path_stats ();
-
- /* Count the number of instructions on the path: as these instructions
- will have to be duplicated, we will not record the path if there
- are too many instructions on the path. Also check that all the
- blocks in the path belong to a single loop. */
- for (unsigned j = 0; j < m_path.length (); j++)
- {
- basic_block bb = m_path[j];
-
- /* Remember, blocks in the path are stored in opposite order in
- the PATH array. The last entry in the array represents the
- block with an outgoing edge that we will redirect to the jump
- threading path. Thus we don't care how many statements are
- in that block because it will not be copied or whether or not
- it ends in a multiway branch. */
- if (j < m_path.length () - 1)
- {
- /* The block in PATH[0] is special, it's the block were we're
- going to be able to eliminate its branch. */
- account_bb (bb, /*check_multiway=*/j > 0);
- if (m_stats.unprofitable_bb)
- return false;
- }
-
- /* Note if we thread through the latch, we will want to include
- the last entry in the array when determining if we thread
- through the loop latch. */
- if (loop->latch == bb)
- m_stats.threaded_through_latch = true;
- }
+ if (m_stats.unprofitable_bb)
+ return false;
if (dump_file && (dump_flags & TDF_DETAILS))
{
@@ -731,25 +758,18 @@ back_threader_profitability::possibly_profitable_path_p
if (loop->latch == m_path[j])
fprintf (dump_file, " (latch)");
}
+ fprintf (dump_file, "\n Control statement insns: %i\n"
+ " Overall: %i insns\n",
+ m_exit_jump_benefit, net_insns ());
}
- /* We are going to remove the control statement at the end of the
- last block in the threading path. So don't count it against our
- statement count. */
- m_n_insns -= m_exit_jump_benefit;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\n Control statement insns: %i\n"
- " Overall: %i insns\n",
- m_exit_jump_benefit, m_n_insns);
-
/* Threading is profitable if the path duplicated is hot but also
in a case we separate cold path from hot path and permit optimization
of the hot path later. Be on the aggressive side here. In some testcases,
as in PR 78407 this leads to noticeable improvements. */
if (m_speed_p)
{
- if (m_n_insns >= param_max_fsm_thread_path_insns)
+ if (net_insns () >= param_max_fsm_thread_path_insns)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " FAIL: Jump-thread path not considered: "
@@ -767,12 +787,12 @@ back_threader_profitability::possibly_profitable_path_p
return false;
}
}
- else if (m_n_insns > 1)
+ else if (net_insns () > 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " FAIL: Jump-thread path not considered: "
"duplication of %i insns is needed and optimizing for size.\n",
- m_n_insns);
+ net_insns ());
return false;
}
@@ -785,7 +805,7 @@ back_threader_profitability::possibly_profitable_path_p
if ((!m_threaded_multiway_branch
|| !loop->latch
|| loop->latch->index == EXIT_BLOCK)
- && (m_n_insns * param_fsm_scale_path_stmts
+ && (net_insns () * param_fsm_scale_path_stmts
>= param_max_jump_thread_duplication_stmts))
{
if (dump_file && (dump_flags & TDF_DETAILS))
@@ -796,7 +816,7 @@ back_threader_profitability::possibly_profitable_path_p
}
*large_non_fsm = (!(m_stats.threaded_through_latch
&& m_threaded_multiway_branch)
- && (m_n_insns * param_fsm_scale_path_stmts
+ && (net_insns () * param_fsm_scale_path_stmts
>= param_max_jump_thread_duplication_stmts));
if (dump_file && (dump_flags & TDF_DETAILS))
@@ -852,12 +872,12 @@ back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
return false;
}
}
- else if (m_n_insns > 1)
+ else if (net_insns () > 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " FAIL: Jump-thread path not considered: "
"duplication of %i insns is needed and optimizing for size.\n",
- m_n_insns);
+ net_insns ());
return false;
}
@@ -870,7 +890,7 @@ back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
if (!m_threaded_multiway_branch
&& *creates_irreducible_loop
&& (!(cfun->curr_properties & PROP_loop_opts_done)
- || (m_n_insns * param_fsm_scale_path_stmts
+ || (net_insns () * param_fsm_scale_path_stmts
>= param_max_jump_thread_duplication_stmts)))
{
if (dump_file && (dump_flags & TDF_DETAILS))
@@ -886,7 +906,7 @@ back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
case, drastically reduce the number of statements we are allowed
to copy. */
if (!(m_stats.threaded_through_latch && m_threaded_multiway_branch)
- && (m_n_insns * param_fsm_scale_path_stmts
+ && (net_insns () * param_fsm_scale_path_stmts
>= param_max_jump_thread_duplication_stmts))
{
if (dump_file && (dump_flags & TDF_DETAILS))
--
2.53.0
