[gcc r13-1550] Speed up LC SSA rewrite

[gcc r13-1550] Speed up LC SSA rewrite

[Richard Biener]

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

commit r13-1550-ge5a9d60317852a7323e46109fa366e630b8b5bae
Author: Richard Biener <rguenther@suse.de>
Date:   Thu Jul 7 09:00:00 2022 +0200

    Speed up LC SSA rewrite
    
    The following avoids collecting all loops exit blocks into bitmaps
    and computing the union of those up the loop tree possibly repeatedly.
    Instead we make sure to do this only once for each loop with a
    definition possibly requiring a LC phi node plus make sure to
    leverage recorded exits to avoid the intermediate bitmap allocation.
    
            * tree-ssa-loop-manip.cc (compute_live_loop_exits): Take
            the def loop exit block bitmap as argument instead of
            re-computing it here.
            (add_exit_phis_var): Adjust.
            (loop_name_cmp): New function.
            (add_exit_phis): Sort variables to insert LC PHI nodes
            after definition loop, for each definition loop compute
            the exit block bitmap once.
            (get_loops_exit): Remove.
            (rewrite_into_loop_closed_ssa_1): Do not pre-record
            all loop exit blocks into bitmaps.  Record loop exits
            if required.

Diff:
---
 gcc/tree-ssa-loop-manip.cc | 95 +++++++++++++++++++++++++++-------------------
 1 file changed, 56 insertions(+), 39 deletions(-)

diff --git a/gcc/tree-ssa-loop-manip.cc b/gcc/tree-ssa-loop-manip.cc
index 9f3b62652ea..0324ff60a0f 100644
--- a/gcc/tree-ssa-loop-manip.cc
+++ b/gcc/tree-ssa-loop-manip.cc
@@ -183,12 +183,14 @@ find_sibling_superloop (class loop *use_loop, class loop *def_loop)
 /* DEF_BB is a basic block containing a DEF that needs rewriting into
    loop-closed SSA form.  USE_BLOCKS is the set of basic blocks containing
    uses of DEF that "escape" from the loop containing DEF_BB (i.e. blocks in
-   USE_BLOCKS are dominated by DEF_BB but not in the loop father of DEF_B).
+   USE_BLOCKS are dominated by DEF_BB but not in the loop father of DEF_BB).
    ALL_EXITS[I] is the set of all basic blocks that exit loop I.
+   DEF_LOOP_EXITS is a bitmap of loop exit blocks that exit the loop
+   containing DEF_BB or its outer loops.
 
-   Compute the subset of LOOP_EXITS that exit the loop containing DEF_BB
-   or one of its loop fathers, in which DEF is live.  This set is returned
-   in the bitmap LIVE_EXITS.
+   Compute the subset of loop exit destinations that exit the loop
+   containing DEF_BB or one of its loop fathers, in which DEF is live.
+   This set is returned in the bitmap LIVE_EXITS.
 
    Instead of computing the complete livein set of the def, we use the loop
    nesting tree as a form of poor man's structure analysis.  This greatly
@@ -197,18 +199,17 @@ find_sibling_superloop (class loop *use_loop, class loop *def_loop)
 
 static void
 compute_live_loop_exits (bitmap live_exits, bitmap use_blocks,
-			 bitmap *loop_exits, basic_block def_bb)
+			 basic_block def_bb, bitmap def_loop_exits)
 {
   unsigned i;
   bitmap_iterator bi;
   class loop *def_loop = def_bb->loop_father;
   unsigned def_loop_depth = loop_depth (def_loop);
-  bitmap def_loop_exits;
 
   /* Normally the work list size is bounded by the number of basic
      blocks in the largest loop.  We don't know this number, but we
      can be fairly sure that it will be relatively small.  */
-  auto_vec<basic_block> worklist (MAX (8, n_basic_blocks_for_fn (cfun) / 128));
+  auto_vec<basic_block, 8> worklist (MAX (8, n_basic_blocks_for_fn (cfun) / 128));
 
   EXECUTE_IF_SET_IN_BITMAP (use_blocks, 0, i, bi)
     {
@@ -272,13 +273,7 @@ compute_live_loop_exits (bitmap live_exits, bitmap use_blocks,
 	}
     }
 
-  def_loop_exits = BITMAP_ALLOC (&loop_renamer_obstack);
-  for (class loop *loop = def_loop;
-       loop != current_loops->tree_root;
-       loop = loop_outer (loop))
-    bitmap_ior_into (def_loop_exits, loop_exits[loop->num]);
   bitmap_and_into (live_exits, def_loop_exits);
-  BITMAP_FREE (def_loop_exits);
 }
 
 /* Add a loop-closing PHI for VAR in basic block EXIT.  */
@@ -322,23 +317,33 @@ add_exit_phi (basic_block exit, tree var)
    Exits of the loops are stored in LOOP_EXITS.  */
 
 static void
-add_exit_phis_var (tree var, bitmap use_blocks, bitmap *loop_exits)
+add_exit_phis_var (tree var, bitmap use_blocks, bitmap def_loop_exits)
 {
   unsigned index;
   bitmap_iterator bi;
   basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
-  bitmap live_exits = BITMAP_ALLOC (&loop_renamer_obstack);
 
   gcc_checking_assert (! bitmap_bit_p (use_blocks, def_bb->index));
 
-  compute_live_loop_exits (live_exits, use_blocks, loop_exits, def_bb);
+  auto_bitmap live_exits (&loop_renamer_obstack);
+  compute_live_loop_exits (live_exits, use_blocks, def_bb, def_loop_exits);
 
   EXECUTE_IF_SET_IN_BITMAP (live_exits, 0, index, bi)
     {
       add_exit_phi (BASIC_BLOCK_FOR_FN (cfun, index), var);
     }
+}
 
-  BITMAP_FREE (live_exits);
+static int
+loop_name_cmp (const void *p1, const void *p2)
+{
+  auto l1 = (const std::pair<int, int> *)p1;
+  auto l2 = (const std::pair<int, int> *)p2;
+  if (l1->first < l2->first)
+    return -1;
+  else if (l1->first > l2->first)
+    return 1;
+  return 0;
 }
 
 /* Add exit phis for the names marked in NAMES_TO_RENAME.
@@ -346,31 +351,38 @@ add_exit_phis_var (tree var, bitmap use_blocks, bitmap *loop_exits)
    names are used are stored in USE_BLOCKS.  */
 
 static void
-add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap *loop_exits)
+add_exit_phis (bitmap names_to_rename, bitmap *use_blocks)
 {
   unsigned i;
   bitmap_iterator bi;
 
+  /* Sort names_to_rename after definition loop so we can avoid re-computing
+     def_loop_exits.  */
+  auto_vec<std::pair<int, int> > names (bitmap_count_bits (names_to_rename));
   EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
     {
-      add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
+      tree name = ssa_name (i);
+      loop_p def_loop = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father;
+      names.quick_push (std::make_pair (def_loop->num, i));
     }
-}
+  names.qsort (loop_name_cmp);
 
-/* Fill the array of bitmaps LOOP_EXITS with all loop exit edge targets.  */
-
-static void
-get_loops_exits (bitmap *loop_exits)
-{
-  unsigned j;
-  edge e;
-
-  for (auto loop : loops_list (cfun, 0))
+  auto_bitmap def_loop_exits (&loop_renamer_obstack);
+  loop_p last_def_loop = NULL;
+  for (auto p : names)
     {
-      auto_vec<edge> exit_edges = get_loop_exit_edges (loop);
-      loop_exits[loop->num] = BITMAP_ALLOC (&loop_renamer_obstack);
-      FOR_EACH_VEC_ELT (exit_edges, j, e)
-        bitmap_set_bit (loop_exits[loop->num], e->dest->index);
+      loop_p def_loop = get_loop (cfun, p.first);
+      if (def_loop != last_def_loop)
+	{
+	  bitmap_clear (def_loop_exits);
+	  last_def_loop = def_loop;
+	  for (class loop *loop = def_loop; loop != current_loops->tree_root;
+	       loop = loop_outer (loop))
+	    for (auto exit = loop->exits->next; exit->e; exit = exit->next)
+	      bitmap_set_bit (def_loop_exits, exit->e->dest->index);
+	}
+      add_exit_phis_var (ssa_name (p.second), use_blocks[p.second],
+			 def_loop_exits);
     }
 }
 
@@ -566,16 +578,21 @@ rewrite_into_loop_closed_ssa_1 (bitmap changed_bbs, unsigned update_flag,
 
   if (!bitmap_empty_p (names_to_rename))
     {
-      /* An array of bitmaps where LOOP_EXITS[I] is the set of basic blocks
-	 that are the destination of an edge exiting loop number I.  */
-      bitmap *loop_exits = XNEWVEC (bitmap, number_of_loops (cfun));
-      get_loops_exits (loop_exits);
+      bool release_recorded_exits_p = false;
+      if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
+	{
+	  /* Doing one scan over the whole function is cheaper than
+	     traversing the loop tree and gathering BBs of each loop.  */
+	  record_loop_exits ();
+	  release_recorded_exits_p = true;
+	}
 
       /* Add the PHI nodes on exits of the loops for the names we need to
 	 rewrite.  */
-      add_exit_phis (names_to_rename, use_blocks, loop_exits);
+      add_exit_phis (names_to_rename, use_blocks);
 
-      free (loop_exits);
+      if (release_recorded_exits_p)
+	release_recorded_exits (cfun);
 
       /* Fix up all the names found to be used outside their original
 	 loops.  */