[gcc r15-3818] tree-optimization/114855 - high update_ssa time

[Richard Biener via Gcc-cvs]

https://gcc.gnu.org/g:f9dfe8dea31bf5c56aa7798a0905707faf9e7ec4

commit r15-3818-gf9dfe8dea31bf5c56aa7798a0905707faf9e7ec4
Author: Richard Biener <rguent...@suse.de>
Date:   Mon Sep 23 15:41:14 2024 +0200

    tree-optimization/114855 - high update_ssa time
    
    Part of the problem in PR114855 is high update_ssa time.  When one fixes
    the backward jump threading issue tree SSA incremental is at
    439.91s ( 26%), mostly doing bitmap element searches for
    blocks_with_phis_to_rewrite.  The following turns that bitmap to tree
    view noticing the two-dimensional vector of PHIs it guards is excessive
    compared to what we actually save with it - walking all PHI nodes
    in a block, something we already do once to initialize stmt flags.
    So instead of optimizing that walk we use the stmt flag, saving
    allocations and global state that lives throughout the whole
    compilation.
    
    This reduces the tree SSA incremental time to 203.13 ( 14%)
    
    The array was added in r0-74758-g2ce798794df8e1 when we still possibly
    had gazillion virtual operands for PR26830, I checked the testcase
    still behaves OK.
    
            PR tree-optimization/114855
            * tree-into-ssa.cc (phis_to_rewrite): Remove global var.
            (mark_phi_for_rewrite): Simplify.
            (rewrite_update_phi_arguments): Walk all PHIs, process
            those satisfying rewrite_uses_p.
            (delete_update_ssa): Simplify.
            (update_ssa): Likewise.  Switch blocks_with_phis_to_rewrite
            to tree view.

Diff:
---
 gcc/tree-into-ssa.cc | 44 ++++++++------------------------------------
 1 file changed, 8 insertions(+), 36 deletions(-)

diff --git a/gcc/tree-into-ssa.cc b/gcc/tree-into-ssa.cc
index 5b367c358125..1cce9d628090 100644
--- a/gcc/tree-into-ssa.cc
+++ b/gcc/tree-into-ssa.cc
@@ -101,12 +101,7 @@ static sbitmap interesting_blocks;
    released after we finish updating the SSA web.  */
 bitmap names_to_release;
 
-/* vec of vec of PHIs to rewrite in a basic block.  Element I corresponds
-   the to basic block with index I.  Allocated once per compilation, *not*
-   released between different functions.  */
-static vec< vec<gphi *> > phis_to_rewrite;
-
-/* The bitmap of non-NULL elements of PHIS_TO_REWRITE.  */
+/* The bitmap of blocks with PHIs to rewrite.  */
 static bitmap blocks_with_phis_to_rewrite;
 
 /* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES.  These sets need
@@ -942,9 +937,6 @@ find_def_blocks_for (tree var)
 static void
 mark_phi_for_rewrite (basic_block bb, gphi *phi)
 {
-  vec<gphi *> phis;
-  unsigned n, idx = bb->index;
-
   if (rewrite_uses_p (phi))
     return;
 
@@ -953,21 +945,7 @@ mark_phi_for_rewrite (basic_block bb, gphi *phi)
   if (!blocks_with_phis_to_rewrite)
     return;
 
-  if (bitmap_set_bit (blocks_with_phis_to_rewrite, idx))
-    {
-      n = (unsigned) last_basic_block_for_fn (cfun) + 1;
-      if (phis_to_rewrite.length () < n)
-       phis_to_rewrite.safe_grow_cleared (n, true);
-
-      phis = phis_to_rewrite[idx];
-      gcc_assert (!phis.exists ());
-      phis.create (10);
-    }
-  else
-    phis = phis_to_rewrite[idx];
-
-  phis.safe_push (phi);
-  phis_to_rewrite[idx] = phis;
+  bitmap_set_bit (blocks_with_phis_to_rewrite, bb->index);
 }
 
 /* Insert PHI nodes for variable VAR using the iterated dominance
@@ -2097,18 +2075,17 @@ rewrite_update_phi_arguments (basic_block bb)
 
   FOR_EACH_EDGE (e, ei, bb->succs)
     {
-      vec<gphi *> phis;
-
       if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
        continue;
 
-      phis = phis_to_rewrite[e->dest->index];
-      for (gphi *phi : phis)
+      for (auto gsi = gsi_start_phis (e->dest);
+          !gsi_end_p (gsi); gsi_next(&gsi))
        {
          tree arg, lhs_sym, reaching_def = NULL;
          use_operand_p arg_p;
-
-         gcc_checking_assert (rewrite_uses_p (phi));
+         gphi *phi = *gsi;
+         if (!rewrite_uses_p (*gsi))
+           continue;
 
          arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
          arg = USE_FROM_PTR (arg_p);
@@ -3060,10 +3037,6 @@ delete_update_ssa (void)
 
   fini_ssa_renamer ();
 
-  if (blocks_with_phis_to_rewrite)
-    EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
-      phis_to_rewrite[i].release ();
-
   BITMAP_FREE (blocks_with_phis_to_rewrite);
   BITMAP_FREE (blocks_to_update);
 
@@ -3470,8 +3443,7 @@ update_ssa (unsigned update_flags)
   gcc_assert (update_ssa_initialized_fn == cfun);
 
   blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
-  if (!phis_to_rewrite.exists ())
-    phis_to_rewrite.create (last_basic_block_for_fn (cfun) + 1);
+  bitmap_tree_view (blocks_with_phis_to_rewrite);
   blocks_to_update = BITMAP_ALLOC (NULL);
 
   insert_phi_p = (update_flags != TODO_update_ssa_no_phi);