[gcc r14-1561] tree-optimization/109143 - improve PTA compile time

[gcc r14-1561] tree-optimization/109143 - improve PTA compile time

[Richard Biener]

https://gcc.gnu.org/g:21bf2b2fd99d7a94049610fc2f82db77f725d025

commit r14-1561-g21bf2b2fd99d7a94049610fc2f82db77f725d025
Author: Richard Biener <rguenther@suse.de>
Date:   Wed May 31 14:28:37 2023 +0200

    tree-optimization/109143 - improve PTA compile time
    
    The following improves solution_set_expand to require one less
    iteration over the bitmap and avoid changing the bitmap we iterate
    over.  Plus we handle adjacent subvars in the ID space (the common case)
    and use bitmap_set_range.  This cuts a bit less than 10% off the PTA
    time from the testcase in the PR.
    
            PR tree-optimization/109143
            * tree-ssa-structalias.cc (solution_set_expand): Avoid
            one bitmap iteration and optimize bit range setting.

Diff:
---
 gcc/tree-ssa-structalias.cc | 38 +++++++++++++++++++++++++-------------
 1 file changed, 25 insertions(+), 13 deletions(-)

diff --git a/gcc/tree-ssa-structalias.cc b/gcc/tree-ssa-structalias.cc
index 8db99a42565..ee9313c59ca 100644
--- a/gcc/tree-ssa-structalias.cc
+++ b/gcc/tree-ssa-structalias.cc
@@ -966,28 +966,40 @@ solution_set_expand (bitmap set, bitmap *expanded)
 
   *expanded = BITMAP_ALLOC (&iteration_obstack);
 
-  /* In a first pass expand to the head of the variables we need to
-     add all sub-fields off.  This avoids quadratic behavior.  */
+  /* In a first pass expand variables, once for each head to avoid
+     quadratic behavior, to include all sub-fields.  */
+  unsigned prev_head = 0;
   EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
     {
       varinfo_t v = get_varinfo (j);
       if (v->is_artificial_var
 	  || v->is_full_var)
 	continue;
-      bitmap_set_bit (*expanded, v->head);
-    }
+      if (v->head != prev_head)
+	{
+	  varinfo_t head = get_varinfo (v->head);
+	  unsigned num = 1;
+	  for (varinfo_t n = vi_next (head); n != NULL; n = vi_next (n))
+	    {
+	      if (n->id != head->id + num)
+		{
+		  /* Usually sub variables are adjacent but since we
+		     create pointed-to restrict representatives there
+		     can be gaps as well.  */
+		  bitmap_set_range (*expanded, head->id, num);
+		  head = n;
+		  num = 1;
+		}
+	      else
+		num++;
+	    }
 
-  /* In the second pass now expand all head variables with subfields.  */
-  EXECUTE_IF_SET_IN_BITMAP (*expanded, 0, j, bi)
-    {
-      varinfo_t v = get_varinfo (j);
-      if (v->head != j)
-	continue;
-      for (v = vi_next (v); v != NULL; v = vi_next (v))
-	bitmap_set_bit (*expanded, v->id);
+	  bitmap_set_range (*expanded, head->id, num);
+	  prev_head = v->head;
+	}
     }
 
-  /* And finally set the rest of the bits from SET.  */
+  /* And finally set the rest of the bits from SET in an efficient way.  */
   bitmap_ior_into (*expanded, set);
 
   return *expanded;