On Fri, Oct 09, 2026 at 12:03:03PM +0200, Richard Biener wrote: > On Fri, 9 Oct 2026, Aldy Hernandez wrote: > > > On Fri, Oct 09, 2026 at 11:17:54AM +0200, Richard Biener wrote: > > > On Fri, 9 Oct 2026, Aldy Hernandez wrote: > > > > > > > On Fri, Oct 09, 2026 at 09:51:01AM +0200, Richard Biener wrote: > > > > > On Thu, 8 Oct 2026, Aldy Hernandez wrote:
> > Sounds reasonable? > > Yes. Attached. OK? Aldy
>From d0bc7f531a67ea2f6ee9b28919c2f426cb9c0624 Mon Sep 17 00:00:00 2001 From: Aldy Hernandez <[email protected]> Date: Fri, 9 Oct 2026 09:46:01 +0000 Subject: [PATCH] sccvn: add a driver object for the value numbering walk [PR126904] SCC VN is driven through various free functions (do_rpo_vn_1 walks, run_rpo_vn, etc). Encapsulate this into vn_driver, so we can later implement jump threading from within FRE, where the value numbers have to outlive the walk. The general plan is: class path_vn : public vn_driver { public: bool reset_path (const vec<basic_block> &path); void clear_path (); tree valnum (tree name); }; // And then in FRE path_vn vn (fun, iterate_p, !iterate_p); threader.search (vn); todo = vn.finalize (); todo |= threader.apply (); No functional change: the assembly is identical over a corpus of .ii files from a stage1 bootstrap. PR tree-optimization/126904 gcc/ChangeLog: * tree-ssa-sccvn.h (class vn_driver): 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): Make static. (run_rpo_vn): Rename to ... (assign_value_ids): ... this, static and without the walk. (free_rpo_vn): Make static. (do_rpo_vn_1): Take the walker and the RPO map from the caller. (vn_driver::vn_driver, vn_driver::~vn_driver) (vn_driver::finalize): New. (do_rpo_vn, pass_fre::execute): Use a vn_driver. * tree-ssa-pre.cc (pass_pre::execute): Same. --- gcc/tree-ssa-pre.cc | 6 +-- gcc/tree-ssa-sccvn.cc | 98 ++++++++++++++++++++++++++++++++++--------- gcc/tree-ssa-sccvn.h | 26 ++++++++++-- 3 files changed, 103 insertions(+), 27 deletions(-) diff --git a/gcc/tree-ssa-pre.cc b/gcc/tree-ssa-pre.cc index f1bd8950983..d2f0a93858c 100644 --- a/gcc/tree-ssa-pre.cc +++ b/gcc/tree-ssa-pre.cc @@ -4693,7 +4693,7 @@ pass_pre::execute (function *fun) scev_initialize (); calculate_dominance_info (CDI_DOMINATORS); - run_rpo_vn (VN_WALK); + vn_driver *vn = new vn_driver (fun, true, false, true, VN_WALK); init_pre (); @@ -4727,7 +4727,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->finalize (inserted_exprs); vn_valueize = NULL; @@ -4761,7 +4761,7 @@ pass_pre::execute (function *fun) - mark TODO_cleanup_cfg when necessary. */ todo |= tail_merge_optimize (need_crit_edge_split); - free_rpo_vn (); + delete vn; /* Tail merging invalidates the virtual SSA web, together with cfg-cleanup opportunities exposed by PRE this will wreck the diff --git a/gcc/tree-ssa-sccvn.cc b/gcc/tree-ssa-sccvn.cc index 7ff14cec119..63d7110d35c 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; @@ -8054,7 +8054,7 @@ eliminate_dom_walker::eliminate_cleanup (bool region_p) /* Eliminate fully redundant computations. */ -unsigned +static unsigned eliminate_with_rpo_vn (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) +static void +assign_value_ids () { - 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); @@ -8884,12 +8879,13 @@ do_unwind (unwind_state *to, rpo_elim &avail) 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. */ + is true then force PHI nodes in ENTRY->dest to VARYING. AVAIL and + BB_TO_RPO belong to the caller, which can keep them past the walk. */ 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) + vn_lookup_kind kind, rpo_elim &avail, int *bb_to_rpo) { unsigned todo = 0; default_vn_walk_kind = kind; @@ -8935,14 +8931,12 @@ 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)); 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_avail = &avail; /* Verify we have no extra entries into the region. */ @@ -9291,7 +9285,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,9 +9307,70 @@ 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); + + /* We don't support elimination in region-based iteration. */ + gcc_assert (!entry || !iterate || !eliminate); + /* When iterating, finalize does the elimination; otherwise the + constructor's walk does. */ + vn_driver vn (fn, entry, exit_bbs, iterate, eliminate && !iterate, + skip_entry_phis, kind); + return eliminate ? vn.finalize () : vn.todo (); +} + +vn_driver::vn_driver (function *fn, bool iterate, bool eliminate, + bool want_value_ids, vn_lookup_kind kind) + : vn_driver (fn, NULL, NULL, iterate, eliminate, false, kind) +{ + if (want_value_ids) + assign_value_ids (); +} + +/* Value-number the region ENTRY leads into, which exits to EXIT_BBS, or all of + FN if ENTRY is NULL. */ + +vn_driver::vn_driver (function *fn, edge entry, bitmap exit_bbs, + bool iterate, bool eliminate, bool skip_entry_phis, + vn_lookup_kind kind) + : m_eliminate (eliminate) +{ + 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)); + m_todo = do_rpo_vn_1 (fn, entry, exit_bbs, iterate, eliminate, + skip_entry_phis, kind, *m_avail, m_bb_to_rpo); +} + +vn_driver::~vn_driver () +{ free_rpo_vn (); + XDELETEVEC (m_bb_to_rpo); + delete m_avail; +} + +/* Finish elimination and return the TODO flags. */ + +unsigned +vn_driver::finalize (bitmap inserted_exprs) +{ + /* If ELIMINATE was passed to the constructor, finish the elimination. */ + if (m_eliminate) + return m_todo; + + /* PRE eliminates after its insertions, when the RPO map no longer + describes the IL. Return only its flags, as PRE always has, to avoid + an extra CFG cleanup. */ + if (inserted_exprs) + return eliminate_with_rpo_vn (inserted_exprs); + + /* Otherwise do full elimination. */ + rpo_avail = m_avail; + vn_bb_to_rpo = m_bb_to_rpo; + vn_valueize = rpo_vn_valueize; + unsigned todo = m_todo | eliminate_with_rpo_vn (NULL); + vn_valueize = NULL; + rpo_avail = NULL; + vn_bb_to_rpo = NULL; return todo; } @@ -9371,8 +9425,12 @@ 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 (); + { + /* When iterating, finalize below does the elimination; otherwise the + constructor's walk does. */ + vn_driver vn (fun, iterate_p, !iterate_p); + todo = vn.finalize (); + } if (iterate_p) loop_optimizer_finalize (); diff --git a/gcc/tree-ssa-sccvn.h b/gcc/tree-ssa-sccvn.h index 78729fbec64..cc0b36df27c 100644 --- a/gcc/tree-ssa-sccvn.h +++ b/gcc/tree-ssa-sccvn.h @@ -309,10 +309,28 @@ 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); +/* Value-numbers a function or a region. */ + +class vn_driver +{ +public: + vn_driver (function *, bool iterate, bool eliminate, + bool want_value_ids = false, vn_lookup_kind = VN_WALKREWRITE); + vn_driver (function *, edge entry, bitmap exit_bbs, bool iterate, + bool eliminate, bool skip_entry_phis, vn_lookup_kind); + ~vn_driver (); + unsigned finalize (bitmap inserted_exprs = NULL); + /* The TODO flags of the walk, for a caller that does not eliminate. */ + unsigned todo () const { return m_todo; } + +private: + DISABLE_COPY_AND_ASSIGN (vn_driver); + class rpo_elim *m_avail; + int *m_bb_to_rpo; + unsigned m_todo; + /* Whether the walk eliminated. */ + bool m_eliminate; +}; /* Valueize NAME if it is an SSA name, otherwise just return it. This hook is initialized by run_scc_vn. */ -- 2.53.0
