On Thu, 10 Sep 2026, Aldy Hernandez wrote:
> 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?
+ // accounts m_path[i - 1].
+ struct unwind_state
+ {
+ path_stats stats;
+ int bb_insns;
+ };
bb_insns should be unused now?
> Aldy
>
--
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)
