https://gcc.gnu.org/bugzilla/show_bug.cgi?id=126904
--- Comment #8 from aldy at quesejoda dot com ---
On Mon, Oct 05, 2026 at 07:06:05AM +0000, rguenth at gcc dot gnu.org wrote:
> --- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
> I wonder if it then makes sense to integrate the threader with FRE
> (much like DOM was with the forward threader)? When FRE is run, at its end,
> but before it winds down data structures (but after it performed
> elimination?),
> do VN-enabled backward threading. This should get you the whole-function
> value-numbering "for free" at the expense of constraining threading/FRE
> pass placement.
>
> The early uninit pass runs whole-function VN (but without elimination and
> without iteration, just to get (un-)executable edges marked), you can
> get VN cost down by disabling iteration and tuning down the
> sccvn-max-alias-queries-per-access parameter.
This definitely looks promising. I've played with putting a backward
threader inside FRE (cleanly, no hooks), and turning off DOM
threading, and here's what we have.
Over my usual .ii files from a stage1 bootstrap, with DOM's threader
off and FRE threading in the two FRE instances that run right before
threadfull1 and thread2, we get 4.7% more threads for 1.6% more
compile time (DOM itself gets 39% cheaper). Nothing changes at -O1,
where FRE does not thread; DOM's threader stays on there.
Pretty much everything DOM used to thread moves to FRE (yay!), except
what DOM gets at -O1 (where FRE doesn't run). We have some cost model
regressions, but I assume those are easy to tackle, and then 8 proper
regressions at -O2 which I have yet to investigate:
gcc.dg/tree-ssa/dom-jump-threading-2.c
gcc.dg/tree-ssa/ssa-dom-thread-15.c
gcc.dg/tree-ssa/pr68619-4.c
gcc.dg/uninit-pr61409.c
g++.dg/warn/Wuninitialized-6.C
g++.dg/tree-ssa/pr114589.C
g++.dg/tree-ssa/pr117123.C (-Os)
gcc.dg/harden-cfr-pr111943.c (-Ofast)
Before I start posting stuff, I'd like some buy in on the general
idea, since there are some inevitable cleanups and restructuring.
Today we have 4 free functions (do_rpo_vn_1, run_rpo_vn,
eliminate_with_rpo_vn, free_rpo_vn), the walker, some mappings and
hooks, which I'd make into an object:
class vn
{
public:
vn (function *, edge entry = NULL, bitmap exit_bbs = NULL);
virtual ~vn ();
unsigned walk (bool iterate, bool eliminate, ...); // do_rpo_vn_1
unsigned eliminate_finish (); // releases names, EH cleanup;
// the value numbers are usable
// until this
// PRE's two calls
void enumerate_values ();
unsigned eliminate (bitmap inserted_exprs);
};
class path_vn : public vn
{
public:
bool reset_path (const vec<basic_block> &path);
void clear_path ();
tree valnum (tree name);
};
I tried not to go too crazy with moving everything to a class, just
what we'd need to do it cleanly, without continuing adding free
functions to the VN interface.
The tables stay global (it's not like we need multiple VN's to run at
once :)), do_rpo_vn stays as a one-call wrapper, etc. PRE holds a vn
for its pass, and FRE becomes:
path_vn vn (fun);
todo = vn.walk (iterate_p, true);
threader.search (vn);
todo |= vn.eliminate_finish ();
todo |= threader.apply ();
The backward threader's search is unchanged; its path solver just
gets the path_vn, and for each candidate path:
vn.reset_path (path);
...
if (tree val = vn.valnum (name))
{
// Use the path oracle to record the equivalence.
register VREL_EQ (name, val);
// Use val's range for name from here on.
}
How does this sound?
