[gcc r13-5750] tree-optimization/26854 - slow bitmap operations

[gcc r13-5750] tree-optimization/26854 - slow bitmap operations

[Richard Biener]

https://gcc.gnu.org/g:4b19ff1b5ef684c2d9ccd4fb275aeef0a4b0b980

commit r13-5750-g4b19ff1b5ef684c2d9ccd4fb275aeef0a4b0b980
Author: Richard Biener <rguenther@suse.de>
Date:   Tue Feb 7 14:01:22 2023 +0100

    tree-optimization/26854 - slow bitmap operations
    
    With the compiler.i testcase from the PR one can see bitmap_set_bit
    very high in the profile, originating from SSA update and alias
    stmt walking.  For SSA update mark_block_for_update essentially
    performs redundant bitmap_set_bits and is called via
    insert_updated_phi_nodes_for as
    
          EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
    ...
              mark_block_for_update (bb);
              FOR_EACH_EDGE (e, ei, bb->preds)
                if (e->src->index >= 0)
                  mark_block_for_update (e->src);
    
    which is quite random in the access pattern and runs into the
    O(n) case of the linked list bitmap representation.  Switching
    blocks_to_update to tree view around insert_updated_phi_nodes_for
    improves SSA update time from
    
     tree SSA incremental               :   4.26 (  3%)
    
    to
    
     tree SSA incremental               :   2.98 (  2%)
    
    Likewise the visited bitmap allocated by the alias walker benefits
    from using the tree view in case of large CFGs and we see an
    improvement from
    
     alias stmt walking                 :  10.53 (  9%)
    
    to
    
     alias stmt walking                 :   4.05 (  4%)
    
            PR tree-optimization/26854
            * tree-into-ssa.cc (update_ssa): Turn blocks_to_update to tree
            view around insert_updated_phi_nodes_for.
            * tree-ssa-alias.cc (maybe_skip_until): Allocate visited bitmap
            in tree view.
            (walk_aliased_vdefs_1): Likewise.

Diff:
---
 gcc/tree-into-ssa.cc  |  4 ++++
 gcc/tree-ssa-alias.cc | 10 ++++++++--
 2 files changed, 12 insertions(+), 2 deletions(-)

diff --git a/gcc/tree-into-ssa.cc b/gcc/tree-into-ssa.cc
index 067d29698f9..2e322990456 100644
--- a/gcc/tree-into-ssa.cc
+++ b/gcc/tree-into-ssa.cc
@@ -3561,6 +3561,8 @@ update_ssa (unsigned update_flags)
 	bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
       compute_dominance_frontiers (dfs);
 
+      bitmap_tree_view (blocks_to_update);
+
       /* insert_update_phi_nodes_for will call add_new_name_mapping
 	 when inserting new PHI nodes, but it will not add any
 	 new members to OLD_SSA_NAMES.  */
@@ -3574,6 +3576,8 @@ update_ssa (unsigned update_flags)
       FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
 	insert_updated_phi_nodes_for (sym, dfs, update_flags);
 
+      bitmap_list_view (blocks_to_update);
+
       FOR_EACH_BB_FN (bb, cfun)
 	bitmap_clear (&dfs[bb->index]);
       free (dfs);
diff --git a/gcc/tree-ssa-alias.cc b/gcc/tree-ssa-alias.cc
index 7089e8b5bf3..81bc51ed4ad 100644
--- a/gcc/tree-ssa-alias.cc
+++ b/gcc/tree-ssa-alias.cc
@@ -3657,7 +3657,10 @@ maybe_skip_until (gimple *phi, tree &target, basic_block target_bb,
   basic_block bb = gimple_bb (phi);
 
   if (!*visited)
-    *visited = BITMAP_ALLOC (NULL);
+    {
+      *visited = BITMAP_ALLOC (NULL);
+      bitmap_tree_view (*visited);
+    }
 
   bitmap_set_bit (*visited, SSA_NAME_VERSION (PHI_RESULT (phi)));
 
@@ -3949,7 +3952,10 @@ walk_aliased_vdefs_1 (ao_ref *ref, tree vdef,
 	{
 	  unsigned i;
 	  if (!*visited)
-	    *visited = BITMAP_ALLOC (NULL);
+	    {
+	      *visited = BITMAP_ALLOC (NULL);
+	      bitmap_tree_view (*visited);
+	    }
 	  for (i = 0; i < gimple_phi_num_args (def_stmt); ++i)
 	    {
 	      int res = walk_aliased_vdefs_1 (ref,