[gcc r17-2921] sched-deps: reuse reg_last arrays across regions

https://gcc.gnu.org/g:789d24cd259e0e1e8e5af512565fa59daae5307d

commit r17-2921-g789d24cd259e0e1e8e5af512565fa59daae5307d
Author: Kyrylo Tkachov <[email protected]>
Date:   Mon Jul 27 20:04:29 2026 +0200

    sched-deps: reuse reg_last arrays across regions
    
    The region scheduler initializes one deps_desc for each basic block in a
    region.  Each initialization allocates and zeroes max_reg deps_reg entries.
    The total allocation and zeroing work is
    
      O (max_reg * sum (RGN_NR_BLOCKS (region))).
    
    Before reload, max_reg is max_reg_num ().  This work can therefore grow
    quadratically with function size.
    
    free_deps now empties each entry that was written.  Keep these all-zero
    arrays in a pool keyed by max_reg and reuse them in later regions.  Reset
    the list length fields before returning an array.  Under -fchecking=2,
    verify that every field is zero.  Drain the pool in sched_deps_finish.
    Selective scheduling does not return arrays to the pool because
    remove_from_deps can leave an untracked control-use list.
    
    Add a selftest that fills every list field and both length fields.  It
    verifies that free_deps returns the same array through the pool with all
    fields cleared.  Also add a compile test that drives a debug-only use
    through pool release and reuse under -fchecking=2.  Disabling the pool makes
    the selftest fail.  Dropping the reg_last_dirty recording from patch 2 makes
    the compile test ICE.
    
    On an aarch64 system, I saw a ~1.5% improvement in compile speed of
    gimple-match-6 at -O3.
    Generated assembly doesn't change.
    
    Bootstrapped and tested on aarch64-none-linux-gnu and x86_64-linux.
    
    gcc/ChangeLog:
    
            * sched-deps.cc (reg_last_pool, reg_last_pool_max_reg): New.
            (alloc_reg_last, release_reg_last): New.
            (init_deps, init_deps_reg_last): Use alloc_reg_last.
            (free_deps): Reset the list length fields and release reg_last to the
            pool.
            (sched_deps_finish): Release the pooled arrays.
            (selftest::test_reg_last_pool): New.
            (selftest::sched_deps_cc_tests): Run it.
    
    gcc/testsuite/ChangeLog:
    
            * gcc.dg/sched-deps-debug-1.c: New test.
    
    Signed-off-by: Kyrylo Tkachov <[email protected]>

Diff:
---
 gcc/sched-deps.cc                         | 129 +++++++++++++++++++++++++++++-
 gcc/testsuite/gcc.dg/sched-deps-debug-1.c |  27 +++++++
 2 files changed, 153 insertions(+), 3 deletions(-)

diff --git a/gcc/sched-deps.cc b/gcc/sched-deps.cc
index 3a170d87b7e1..4911b65bba19 100644
--- a/gcc/sched-deps.cc
+++ b/gcc/sched-deps.cc
@@ -3930,6 +3930,61 @@ sched_free_deps (rtx_insn *head, rtx_insn *tail, bool resolved_p)
       }
 }
 
+/* Pool of all-zero reg_last arrays.  init_deps takes one and free_deps
+   returns it, so the O (MAX_REG) zeroing is paid once per pooled array rather
+   than once per basic block of every region.  free_deps empties every entry
+   that was written, so an array coming back is already zero.  Selective
+   scheduling is excluded: its remove_from_deps can drop a reg_last_in_use bit
+   while control_uses is still live, which would return a dirty array.  */
+static vec<struct deps_reg *> reg_last_pool;
+static int reg_last_pool_max_reg;
+
+/* Return an all-zero array of MAX_REG deps_reg, from the pool if one of the
+   right size is available.  */
+
+static struct deps_reg *
+alloc_reg_last (int max_reg)
+{
+  if (max_reg != reg_last_pool_max_reg)
+    {
+      while (!reg_last_pool.is_empty ())
+	free (reg_last_pool.pop ());
+      reg_last_pool_max_reg = max_reg;
+    }
+  else if (!reg_last_pool.is_empty ())
+    return reg_last_pool.pop ();
+
+  return XCNEWVEC (struct deps_reg, max_reg);
+}
+
+/* Give REG_LAST, an array of MAX_REG deps_reg that free_deps has just
+   emptied, back to the pool.  */
+
+static void
+release_reg_last (struct deps_reg *reg_last, int max_reg)
+{
+  if (reg_last == NULL)
+    return;
+
+  if (sel_sched_p () || max_reg != reg_last_pool_max_reg)
+    {
+      free (reg_last);
+      return;
+    }
+
+  if (flag_checking > 1)
+    for (int i = 0; i < max_reg; i++)
+      gcc_assert (reg_last[i].uses == NULL
+		  && reg_last[i].sets == NULL
+		  && reg_last[i].implicit_sets == NULL
+		  && reg_last[i].control_uses == NULL
+		  && reg_last[i].clobbers == NULL
+		  && reg_last[i].uses_length == 0
+		  && reg_last[i].clobbers_length == 0);
+
+  reg_last_pool.safe_push (reg_last);
+}
+
 /* Initialize variables for region data dependence analysis.
    When LAZY_REG_LAST is true, do not allocate reg_last array
    of class deps_desc immediately.  */
@@ -3943,7 +3998,7 @@ init_deps (class deps_desc *deps, bool lazy_reg_last)
   if (lazy_reg_last)
     deps->reg_last = NULL;
   else
-    deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
+    deps->reg_last = alloc_reg_last (max_reg);
   INIT_REG_SET (&deps->reg_last_in_use);
   INIT_REG_SET (&deps->reg_last_dirty);
 
@@ -3978,7 +4033,7 @@ init_deps_reg_last (class deps_desc *deps)
   gcc_assert (deps && deps->max_reg > 0);
   gcc_assert (deps->reg_last == NULL);
 
-  deps->reg_last = XCNEWVEC (struct deps_reg, deps->max_reg);
+  deps->reg_last = alloc_reg_last (deps->max_reg);
 }
 
 
@@ -3996,6 +4051,7 @@ free_deps (class deps_desc *deps)
       gcc_assert (deps->reg_last == NULL);
       return;
     }
+  int max_reg = deps->max_reg;
   deps->max_reg = 0;
 
   free_INSN_LIST_list (&deps->pending_read_insns);
@@ -4025,13 +4081,15 @@ free_deps (class deps_desc *deps)
 	free_INSN_LIST_list (&reg_last->control_uses);
       if (reg_last->clobbers)
 	free_INSN_LIST_list (&reg_last->clobbers);
+      reg_last->uses_length = 0;
+      reg_last->clobbers_length = 0;
     }
   CLEAR_REG_SET (&deps->reg_last_in_use);
   CLEAR_REG_SET (&deps->reg_last_dirty);
 
   /* As we initialize reg_last lazily, it is possible that we didn't allocate
      it at all.  */
-  free (deps->reg_last);
+  release_reg_last (deps->reg_last, max_reg);
   deps->reg_last = NULL;
 
   deps = NULL;
@@ -4183,6 +4241,11 @@ sched_deps_finish (void)
 
   h_d_i_d.release ();
 
+  while (!reg_last_pool.is_empty ())
+    free (reg_last_pool.pop ());
+  reg_last_pool.release ();
+  reg_last_pool_max_reg = 0;
+
   if (true_dependency_cache)
     {
       int i;
@@ -5079,12 +5142,72 @@ test_dirty_reg_last_release ()
   bitmap_obstack_release (&test_obstack);
 }
 
+/* Verify that a pooled reg_last array is empty when it is reused.  */
+
+static void
+test_reg_last_pool ()
+{
+  const int max_reg = 3;
+  ASSERT_TRUE (reg_last_pool.is_empty ());
+
+  bitmap_obstack test_obstack;
+  bitmap_obstack_initialize (&test_obstack);
+
+  deps_desc deps = {};
+  deps.max_reg = max_reg;
+  deps.reg_last = alloc_reg_last (max_reg);
+  struct deps_reg *saved_reg_last = deps.reg_last;
+  bitmap_initialize (&deps.reg_last_in_use, &test_obstack);
+  bitmap_initialize (&deps.reg_last_dirty, &test_obstack);
+
+  deps.reg_last[0].uses = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
+  deps.reg_last[0].sets = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
+  deps.reg_last[0].implicit_sets = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
+  deps.reg_last[0].clobbers = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
+  deps.reg_last[0].uses_length = 2;
+  deps.reg_last[0].clobbers_length = 3;
+  SET_REGNO_REG_SET (&deps.reg_last_in_use, 0);
+
+  deps.reg_last[1].control_uses = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
+  SET_REGNO_REG_SET (&deps.reg_last_dirty, 1);
+
+  common_sched_info_def sched_info = {};
+  sched_info.sched_pass_id = SCHED_RGN_PASS;
+  common_sched_info_def *saved_common_sched_info = common_sched_info;
+  common_sched_info = &sched_info;
+  free_deps (&deps);
+
+  ASSERT_EQ (0, deps.max_reg);
+  ASSERT_EQ (NULL, deps.reg_last);
+  ASSERT_EQ (1, reg_last_pool.length ());
+
+  struct deps_reg *reused_reg_last = alloc_reg_last (max_reg);
+  ASSERT_EQ (saved_reg_last, reused_reg_last);
+  ASSERT_TRUE (reg_last_pool.is_empty ());
+  for (int i = 0; i < max_reg; ++i)
+    {
+      ASSERT_EQ (NULL, reused_reg_last[i].uses);
+      ASSERT_EQ (NULL, reused_reg_last[i].sets);
+      ASSERT_EQ (NULL, reused_reg_last[i].implicit_sets);
+      ASSERT_EQ (NULL, reused_reg_last[i].control_uses);
+      ASSERT_EQ (NULL, reused_reg_last[i].clobbers);
+      ASSERT_EQ (0, reused_reg_last[i].uses_length);
+      ASSERT_EQ (0, reused_reg_last[i].clobbers_length);
+    }
+
+  free (reused_reg_last);
+  sched_deps_finish ();
+  common_sched_info = saved_common_sched_info;
+  bitmap_obstack_release (&test_obstack);
+}
+
 /* Run the sched-deps.cc selftests.  */
 
 void
 sched_deps_cc_tests ()
 {
   test_dirty_reg_last_release ();
+  test_reg_last_pool ();
 }
 
 } // namespace selftest
diff --git a/gcc/testsuite/gcc.dg/sched-deps-debug-1.c b/gcc/testsuite/gcc.dg/sched-deps-debug-1.c
new file mode 100644
index 000000000000..2b5cb7b7ad05
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/sched-deps-debug-1.c
@@ -0,0 +1,27 @@
+/* A debug insn records a use in a reg_last entry that reg_last_in_use does not
+   cover.  free_deps has to release those as well, or the reg_last array it
+   hands back still points at the freed region's insn lists.  -fchecking=2
+   checks an array before it is reused.  */
+
+/* { dg-do compile } */
+/* { dg-options "-O2 -g -fschedule-insns -fchecking=2" } */
+/* { dg-require-effective-target scheduling } */
+
+void f1 (double);
+void f2 (int);
+
+void
+foo (int type, double xx)
+{
+  /* On the f2 path xx is dead, so what is left of it is a debug insn.  */
+  if (type)
+    f1 (xx);
+  else
+    f2 (type);
+}
+
+void
+bar (int type)
+{
+  foo (type, 1.0);
+}