On Thu, 8 Oct 2026, Aldy Hernandez wrote:
> RPO VN is driven through a couple free functions that we can abstract
> out to a class to make things a bit tidier, and to make it easier to
> call the back threader from within FRE to get value numbering for
> free.
>
> Make it an object that we can later sub-class into a path aware VN
> object.
>
> OK for trunk?
Hmm. I think .walk () should be part of constructing (it's a bad
name anyway), that makes it obvious it's a single-shot thing.
Overall it feels a bit of a half-way transition, merely covering
parts of the API, so I don't think it's much of an improvement.
As it is more like a "VN driver" class, maybe naming it accordingly
and _not_ move functions into it as member functions, just encapsulate
the toplevel flow, construct (with value-number), (optional) eliminate,
destruction.
So I think this patch goes too far and too little.
Not knowing how you'd use it exactly doesn't help making a constructive
suggestion, of course ;)
Richard.
> gcc/ChangeLog:
>
> * tree-ssa-sccvn.h (class vn): New.
> (run_rpo_vn, eliminate_with_rpo_vn, free_rpo_vn): Remove.
> * tree-ssa-sccvn.cc (class eliminate_dom_walker): Make the
> destructor virtual.
> (eliminate_with_rpo_vn): Rename to ...
> (vn::eliminate): ... this.
> (run_rpo_vn): Rename to ...
> (vn::enumerate_values): ... this, without the walk.
> (free_rpo_vn): Make static.
> (vn::vn): New, for the whole function and for a region, which
> says whether to skip its entry PHIs.
> (vn::~vn): New.
> (do_rpo_vn_1): Rename to ...
> (vn::walk): ... this, on the object's region and walker.
> (do_rpo_vn, pass_fre::execute): Use a vn.
> * tree-ssa-pre.cc (pass_pre::execute): Same.
> ---
> gcc/tree-ssa-pre.cc | 8 ++---
> gcc/tree-ssa-sccvn.cc | 76 ++++++++++++++++++++++++++++---------------
> gcc/tree-ssa-sccvn.h | 27 ++++++++++++---
> 3 files changed, 77 insertions(+), 34 deletions(-)
>
> diff --git a/gcc/tree-ssa-pre.cc b/gcc/tree-ssa-pre.cc
> index f1bd8950983..8527eae1f9c 100644
> --- a/gcc/tree-ssa-pre.cc
> +++ b/gcc/tree-ssa-pre.cc
> @@ -4693,7 +4693,9 @@ pass_pre::execute (function *fun)
> scev_initialize ();
> calculate_dominance_info (CDI_DOMINATORS);
>
> - run_rpo_vn (VN_WALK);
> + vn vn (fun);
> + vn.walk (true, false, VN_WALK);
> + vn.enumerate_values ();
>
> init_pre ();
>
> @@ -4727,7 +4729,7 @@ pass_pre::execute (function *fun)
> statistics_counter_event (fun, "HOIST inserted", pre_stats.hoist_insert);
> statistics_counter_event (fun, "New PHIs", pre_stats.phis);
>
> - todo |= eliminate_with_rpo_vn (inserted_exprs);
> + todo |= vn.eliminate (inserted_exprs);
>
> vn_valueize = NULL;
>
> @@ -4761,8 +4763,6 @@ pass_pre::execute (function *fun)
> - mark TODO_cleanup_cfg when necessary. */
> todo |= tail_merge_optimize (need_crit_edge_split);
>
> - free_rpo_vn ();
> -
> /* Tail merging invalidates the virtual SSA web, together with
> cfg-cleanup opportunities exposed by PRE this will wreck the
> SSA updating machinery. So make sure to run update-ssa
> diff --git a/gcc/tree-ssa-sccvn.cc b/gcc/tree-ssa-sccvn.cc
> index 7ff14cec119..fc4725972c5 100644
> --- a/gcc/tree-ssa-sccvn.cc
> +++ b/gcc/tree-ssa-sccvn.cc
> @@ -2693,7 +2693,7 @@ class eliminate_dom_walker : public dom_walker
> {
> public:
> eliminate_dom_walker (cdi_direction, bitmap);
> - ~eliminate_dom_walker ();
> + virtual ~eliminate_dom_walker ();
>
> edge before_dom_children (basic_block) final override;
> void after_dom_children (basic_block) final override;
> @@ -8055,7 +8055,7 @@ eliminate_dom_walker::eliminate_cleanup (bool region_p)
> /* Eliminate fully redundant computations. */
>
> unsigned
> -eliminate_with_rpo_vn (bitmap inserted_exprs)
> +vn::eliminate (bitmap inserted_exprs)
> {
> eliminate_dom_walker walker (CDI_DOMINATORS, inserted_exprs);
>
> @@ -8067,16 +8067,11 @@ eliminate_with_rpo_vn (bitmap inserted_exprs)
> return walker.eliminate_cleanup ();
> }
>
> -static unsigned
> -do_rpo_vn_1 (function *fn, edge entry, bitmap exit_bbs,
> - bool iterate, bool eliminate, bool skip_entry_phis,
> - vn_lookup_kind kind);
> +/* Give every value a value id, for PRE. */
>
> void
> -run_rpo_vn (vn_lookup_kind kind)
> +vn::enumerate_values ()
> {
> - do_rpo_vn_1 (cfun, NULL, NULL, true, false, false, kind);
> -
> /* ??? Prune requirement of these. */
> constant_to_value_id = new hash_table<vn_constant_hasher> (23);
>
> @@ -8127,7 +8122,7 @@ run_rpo_vn (vn_lookup_kind kind)
>
> /* Free VN associated data structures. */
>
> -void
> +static void
> free_rpo_vn (void)
> {
> free_vn_table (valid_info);
> @@ -8880,19 +8875,49 @@ do_unwind (unwind_state *to, rpo_elim &avail)
> }
> }
>
> +vn::vn (function *fn)
> + : vn (fn, NULL, NULL, false)
> +{
> +}
> +
> +/* A value numbering of the region ENTRY leads into, which exits to EXIT_BBS,
> + or all of FN if ENTRY is NULL. If SKIP_ENTRY_PHIS is set, force PHI nodes
> + in ENTRY->dest to VARYING. */
> +
> +vn::vn (function *fn, edge entry, bitmap exit_bbs, bool skip_entry_phis)
> + : m_fn (fn), m_entry (entry), m_exit_bbs (exit_bbs),
> + m_skip_entry_phis (skip_entry_phis), m_walked (false)
> +{
> + basic_block entry_bb
> + = entry ? entry->dest : single_succ (ENTRY_BLOCK_PTR_FOR_FN (fn));
> + m_avail = new rpo_elim (entry_bb);
> + m_bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (fn));
> +}
> +
> +vn::~vn ()
> +{
> + if (m_walked)
> + free_rpo_vn ();
> + XDELETEVEC (m_bb_to_rpo);
> + delete m_avail;
> +}
> +
> /* Do VN on a SEME region specified by ENTRY and EXIT_BBS in FN.
> If ITERATE is true then treat backedges optimistically as not
> executed and iterate. If ELIMINATE is true then perform
> - elimination, otherwise leave that to the caller. If SKIP_ENTRY_PHIS
> - is true then force PHI nodes in ENTRY->dest to VARYING. */
> + elimination, otherwise leave that to the caller. */
>
> -static unsigned
> -do_rpo_vn_1 (function *fn, edge entry, bitmap exit_bbs,
> - bool iterate, bool eliminate, bool skip_entry_phis,
> - vn_lookup_kind kind)
> +unsigned
> +vn::walk (bool iterate, bool eliminate, vn_lookup_kind kind)
> {
> + function *fn = m_fn;
> + edge entry = m_entry;
> + bitmap exit_bbs = m_exit_bbs;
> + bool skip_entry_phis = m_skip_entry_phis;
> unsigned todo = 0;
> default_vn_walk_kind = kind;
> + gcc_checking_assert (!m_walked);
> + m_walked = true;
>
> /* We currently do not support region-based iteration when
> elimination is requested. */
> @@ -8935,14 +8960,14 @@ do_rpo_vn_1 (function *fn, edge entry, bitmap
> exit_bbs,
> "the entry block, skipping its PHIs.\n");
> skip_entry_phis |= e != NULL;
>
> - int *bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (fn));
> + int *bb_to_rpo = m_bb_to_rpo;
> for (int i = 0; i < n; ++i)
> bb_to_rpo[rpo[i]] = i;
> vn_bb_to_rpo = bb_to_rpo;
>
> unwind_state *rpo_state = XNEWVEC (unwind_state, n);
>
> - rpo_elim avail (entry->dest);
> + rpo_elim &avail = *m_avail;
> rpo_avail = &avail;
>
> /* Verify we have no extra entries into the region. */
> @@ -9281,7 +9306,7 @@ do_rpo_vn_1 (function *fn, edge entry, bitmap exit_bbs,
> /* Note we can't use avail.walk here because that gets confused
> by the existing availability and it will be less efficient
> as well. */
> - todo |= eliminate_with_rpo_vn (NULL);
> + todo |= this->eliminate (NULL);
> }
> else
> todo |= avail.eliminate_cleanup (do_region);
> @@ -9291,7 +9316,6 @@ do_rpo_vn_1 (function *fn, edge entry, bitmap exit_bbs,
> rpo_avail = NULL;
> vn_bb_to_rpo = NULL;
>
> - XDELETEVEC (bb_to_rpo);
> XDELETEVEC (rpo);
> XDELETEVEC (rpo_state);
>
> @@ -9314,10 +9338,8 @@ do_rpo_vn (function *fn, edge entry, bitmap exit_bbs,
> vn_lookup_kind kind)
> {
> auto_timevar tv (TV_TREE_RPO_VN);
> - unsigned todo = do_rpo_vn_1 (fn, entry, exit_bbs, iterate, eliminate,
> - skip_entry_phis, kind);
> - free_rpo_vn ();
> - return todo;
> + vn vn (fn, entry, exit_bbs, skip_entry_phis);
> + return vn.walk (iterate, eliminate, kind);
> }
>
>
> @@ -9371,8 +9393,10 @@ pass_fre::execute (function *fun)
> if (iterate_p)
> loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
>
> - todo = do_rpo_vn_1 (fun, NULL, NULL, iterate_p, true, false,
> VN_WALKREWRITE);
> - free_rpo_vn ();
> + {
> + vn vn (fun);
> + todo = vn.walk (iterate_p, true);
> + }
>
> if (iterate_p)
> loop_optimizer_finalize ();
> diff --git a/gcc/tree-ssa-sccvn.h b/gcc/tree-ssa-sccvn.h
> index 78729fbec64..92a4c657c1f 100644
> --- a/gcc/tree-ssa-sccvn.h
> +++ b/gcc/tree-ssa-sccvn.h
> @@ -309,10 +309,29 @@ unsigned do_rpo_vn (function *, edge, bitmap,
> /* skip_entry_phis */ bool = false,
> vn_lookup_kind = VN_WALKREWRITE);
>
> -/* Private interface for PRE. */
> -void run_rpo_vn (vn_lookup_kind);
> -unsigned eliminate_with_rpo_vn (bitmap);
> -void free_rpo_vn (void);
> +/* An RPO value numbering of a function. */
> +
> +class vn
> +{
> +public:
> + vn (function *);
> + vn (function *, edge entry, bitmap exit_bbs, bool skip_entry_phis);
> + virtual ~vn ();
> + unsigned walk (bool iterate, bool eliminate,
> + vn_lookup_kind = VN_WALKREWRITE);
> + void enumerate_values ();
> + unsigned eliminate (bitmap inserted_exprs);
> +
> +private:
> + DISABLE_COPY_AND_ASSIGN (vn);
> + function *m_fn;
> + edge m_entry;
> + bitmap m_exit_bbs;
> + bool m_skip_entry_phis;
> + class rpo_elim *m_avail;
> + int *m_bb_to_rpo;
> + bool m_walked;
> +};
>
> /* Valueize NAME if it is an SSA name, otherwise just return it. This hook
> is initialized by run_scc_vn. */
>
--
Richard Biener <[email protected]>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Stefan Gaiser, Jochen Jaser, Abhinav Puri; (HRB 36809, AG Nuernberg)
