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?
> + auto_vec<unwind_state, 20> m_unwind;
> };
>
> back_threader_profitability::back_threader_profitability (bool speed_p,
> @@ -92,15 +108,19 @@ 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. */
>
> -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 +137,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 +156,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 +496,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 +633,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 +743,10 @@ back_threader_profitability::possibly_profitable_path_p
> if (m_path.length () <= 1)
> return false;
>
> - loop_p loop = m_path[0]->loop_father;
> -
> - // 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 ();
> + loop_p loop = m_loop;
>
> - /* 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))
> {
> @@ -736,7 +762,7 @@ back_threader_profitability::possibly_profitable_path_p
> /* 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;
> + m_n_insns = m_stats.n_insns - m_exit_jump_benefit;
>
> if (dump_file && (dump_flags & TDF_DETAILS))
> fprintf (dump_file, "\n Control statement insns: %i\n"
>
--
Richard Biener <[email protected]>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Jochen Jaser, Andrew McDonald, Abhinav Puri; (HRB 36809, AG Nuernberg)
