On Tue, Sep 08, 2026 at 06:24:44PM -0700, Andrea Pinski wrote:
> On Tue, Sep 8, 2026 at 8:30 AM Aldy Hernandez <[email protected]> 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?
> >
> > 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;
>
>
> Why not use auto_sbitmap here?
>
> > // 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)
>
> And then all you need to do for the constructor is:
> back_threader::back_threader (function *fun, unsigned flags, bool
> first) : m_visited_bbs (last_basic_block_for_fn (fun))
The number of BBs in the function can grow in the constructor because
of the loop init stuff:
back_threader::back_threader (function *fun, unsigned flags, bool first)
: m_first (first)
{
if (flags & BT_SPEED)
loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
else
loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
...
and AFAICT auto_sbitmap must be initialized in the mem-initializer
list, which runs before the constructor. So we either use sbitmap as
I posted, or we hoist the loop initialization stuff into its own
helper function. Any preference?
Aldy
