On Wed, Sep 09, 2026 at 01:02:59PM +0200, Richard Biener wrote: > 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;
Ooooo, I like it. OK as attached pending tests? Aldy
>From 5e9705f58f040073fa07833f278d8a725e6a7a3d Mon Sep 17 00:00:00 2001 From: Aldy Hernandez <[email protected]> Date: Mon, 7 Sep 2026 16:55:37 +0000 Subject: [PATCH] backthreader: use a BB flag for the visited-block set 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 BB flag is cleaner and needs no allocation at all. The function find_paths_to_names clears the flag it set on every exit path so the per-block reset in maybe_thread_block is redundant, and so every block is clear again before the auto_bb_flag releases the bit. gcc/ChangeLog: * tree-ssa-threadbackward.cc (back_threader::m_visited_bbs): Replace with... (back_threader::m_visited_flag): ...this. (back_threader::back_threader): Initialize it. (back_threader::find_paths_to_names): Adjust. (back_threader::maybe_thread_block): Drop the reset. --- gcc/tree-ssa-threadbackward.cc | 13 +++++++------ 1 file changed, 7 insertions(+), 6 deletions(-) diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc index 4173f9c9e8c..f3f01ae7d83 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; + // Flag to mark visited BBs while analyzing a path. + auto_bb_flag m_visited_flag; // The set of SSA names, any of which could potentially change the // value of the final conditional in a path. auto_bitmap m_imports; @@ -149,7 +149,7 @@ private: const edge back_threader::UNREACHABLE_EDGE = (edge) -1; back_threader::back_threader (function *fun, unsigned flags, bool first) - : m_first (first) + : m_visited_flag (fun), m_first (first) { if (flags & BT_SPEED) loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES); @@ -386,9 +386,11 @@ 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 (bb->flags & m_visited_flag) return; + bb->flags |= m_visited_flag; + m_path.safe_push (bb); // Try to resolve the path without looking back. Avoid resolving paths @@ -527,7 +529,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); + bb->flags &= ~m_visited_flag; } // Search backwards from BB looking for paths where the final @@ -551,7 +553,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 -- 2.53.0
