On Tue, 8 Sep 2026, Aldy Hernandez wrote:
> [This is a patch series to improve the back threader performance. With
> it the threader is 12% faster.]
>
> The backwards threader marks blocks visited while walking a candidate
> path with a hash_set<basic_block>, which costs a hash lookup on both
> entry to and exit from every node. The set is only ever used to test
> membership of a block of the current function, and the CFG does not
> change during the search, so a sbitmap indexed by bb->index is
> cleaner.
>
> The function find_paths_to_names clears the bit it set on every exit
> path so the per-block reset in maybe_thread_block is redundant.
>
> Measured in perf instructions retired over our stage1 .ii corpus, this
> drops back_threader::thread_blocks() by 2.2% (pass_thread_jumps 2.4%,
> pass_thread_jumps_full 1.1%, pass_early_thread_jumps 2.2%) and the
> whole compile by 0.02% over 806 TUs.
>
> Tested on ppc64le Linux. The assembly is identical over the .ii
> files, so this is a NFC.
>
> OK?
I'll note an even cheaper way is
auto_bb_flag m_visited_flag;
and
bb->flags |= m_visited_flag;
and
bb->flags &= ~m_visited_flag;
Richard.
> gcc/ChangeLog:
>
> * tree-ssa-threadbackward.cc (back_threader::m_visited_bbs):
> Turn into an sbitmap.
> (back_threader::back_threader): Allocate it.
> (back_threader::~back_threader): Free it.
> (back_threader::find_paths_to_names): Adjust.
> (back_threader::maybe_thread_block): Drop the reset.
> ---
> gcc/tree-ssa-threadbackward.cc | 12 +++++++-----
> 1 file changed, 7 insertions(+), 5 deletions(-)
>
> diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc
> index 20bb74c507f..90691ea9612 100644
> --- a/gcc/tree-ssa-threadbackward.cc
> +++ b/gcc/tree-ssa-threadbackward.cc
> @@ -120,8 +120,8 @@ private:
>
> // Current path being analyzed.
> auto_vec<basic_block> m_path;
> - // Hash to mark visited BBs while analyzing a path.
> - hash_set<basic_block> m_visited_bbs;
> + // Bitmap to mark visited BBs while analyzing a path.
> + sbitmap m_visited_bbs;
> // The set of SSA names, any of which could potentially change the
> // value of the final conditional in a path.
> auto_bitmap m_imports;
> @@ -163,10 +163,13 @@ back_threader::back_threader (function *fun, unsigned
> flags, bool first)
> mark_dfs_back_edges ();
>
> m_ranger = new gimple_ranger;
> + m_visited_bbs = sbitmap_alloc (last_basic_block_for_fn (fun));
> + bitmap_clear (m_visited_bbs);
> }
>
> back_threader::~back_threader ()
> {
> + sbitmap_free (m_visited_bbs);
> delete m_ranger;
> loop_optimizer_finalize ();
> }
> @@ -383,7 +386,7 @@ back_threader::find_paths_to_names (basic_block bb,
> bitmap interesting,
> unsigned overall_paths,
> back_threader_profitability &profit)
> {
> - if (m_visited_bbs.add (bb))
> + if (!bitmap_set_bit (m_visited_bbs, bb->index))
> return;
>
> m_path.safe_push (bb);
> @@ -524,7 +527,7 @@ back_threader::find_paths_to_names (basic_block bb,
> bitmap interesting,
>
> // Reset things to their original state.
> m_path.pop ();
> - m_visited_bbs.remove (bb);
> + bitmap_clear_bit (m_visited_bbs, bb->index);
> }
>
> // Search backwards from BB looking for paths where the final
> @@ -548,7 +551,6 @@ back_threader::maybe_thread_block (basic_block bb)
> return;
>
> m_last_stmt = stmt;
> - m_visited_bbs.empty ();
> m_path.truncate (0);
>
> // We compute imports of the path during discovery starting
>
--
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)
