[PATCH] Fix PR81827

[Richard Biener <rguenther at suse dot de>]

I am currently testing the following patch to improve bitmap density
during points-to analysis.  This improves the testcase in PR81827 from

> /usr/bin/time /space/rguenther/install/gcc-7.2/bin/gfortran -S t.f90 -O 
1139.91user 1.99system 19:02.37elapsed 99%CPU (0avgtext+0avgdata 
8035048maxresident)k
40816inputs+144outputs (49major+2004165minor)pagefaults 0swaps

to (patched GCC 7 branch):

> /usr/bin/time /abuild/rguenther/obj2/gcc/f951 t.f90 -O -quiet
61.02user 0.68system 1:01.76elapsed 99%CPU (0avgtext+0avgdata 
1629172maxresident)k

note both compile-time and memory use improve significantly
(PTA still uses a lot of memory though).

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

Richard.

2017-08-17  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/81827
	* tree-ssa-structalias.c (struct variable_info): Add is_reg_var
	flag.
	(new_var_info): Initialize it conservatively.
	(get_call_vi): Mark register vars.
	(new_scalar_tmp_constraint_exp): Likewise.
	(handle_rhs_call): Likewise.
	(handle_const_call): Likewise.
	(create_function_info_for): Likewise.
	(solve_constraints): Sort varinfos to separate register from
	non-register vars to pack points-to solution bitmaps during
	iteration.

Index: gcc/tree-ssa-structalias.c
===================================================================
--- gcc/tree-ssa-structalias.c	(revision 251119)
+++ gcc/tree-ssa-structalias.c	(working copy)
@@ -257,6 +257,9 @@ struct variable_info
   /* True if this is a heap variable.  */
   unsigned int is_heap_var : 1;
 
+  /* True if this is a register variable.  */
+  unsigned int is_reg_var : 1;
+
   /* True if this field may contain pointers.  */
   unsigned int may_have_pointers : 1;
 
@@ -389,6 +392,7 @@ new_var_info (tree t, const char *name,
 			  /* We have to treat even local register variables
 			     as escape points.  */
 			  || (VAR_P (t) && DECL_HARD_REGISTER (t)));
+  ret->is_reg_var = (t && TREE_CODE (t) == SSA_NAME);
   ret->solution = BITMAP_ALLOC (&pta_obstack);
   ret->oldsolution = NULL;
   ret->next = 0;
@@ -422,12 +426,14 @@ get_call_vi (gcall *call)
   vi->size = 1;
   vi->fullsize = 2;
   vi->is_full_var = true;
+  vi->is_reg_var = true;
 
   vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED", true);
   vi2->offset = 1;
   vi2->size = 1;
   vi2->fullsize = 2;
   vi2->is_full_var = true;
+  vi2->is_reg_var = true;
 
   vi->next = vi2->id;
 
@@ -2892,6 +2898,7 @@ new_scalar_tmp_constraint_exp (const cha
   vi->size = -1;
   vi->fullsize = -1;
   vi->is_full_var = 1;
+  vi->is_reg_var = 1;
 
   tmp.var = vi->id;
   tmp.type = SCALAR;
@@ -3930,6 +3937,7 @@ handle_rhs_call (gcall *stmt, vec<ce_s>
 	{
 	  varinfo_t uses = get_call_use_vi (stmt);
 	  varinfo_t tem = new_var_info (NULL_TREE, "callarg", true);
+	  tem->is_reg_var = true;
 	  make_constraint_to (tem->id, arg);
 	  make_any_offset_constraints (tem);
 	  if (!(flags & EAF_DIRECT))
@@ -3943,6 +3951,7 @@ handle_rhs_call (gcall *stmt, vec<ce_s>
 	  varinfo_t uses = get_call_use_vi (stmt);
 	  varinfo_t clobbers = get_call_clobber_vi (stmt);
 	  varinfo_t tem = new_var_info (NULL_TREE, "callarg", true);
+	  tem->is_reg_var = true;
 	  make_constraint_to (tem->id, arg);
 	  make_any_offset_constraints (tem);
 	  if (!(flags & EAF_DIRECT))
@@ -4110,7 +4119,10 @@ handle_const_call (gcall *stmt, vec<ce_s
   /* May return offsetted arguments.  */
   varinfo_t tem = NULL;
   if (gimple_call_num_args (stmt) != 0)
-    tem = new_var_info (NULL_TREE, "callarg", true);
+    {
+      tem = new_var_info (NULL_TREE, "callarg", true);
+      tem->is_reg_var = true;
+    }
   for (k = 0; k < gimple_call_num_args (stmt); ++k)
     {
       tree arg = gimple_call_arg (stmt, k);
@@ -5712,6 +5724,7 @@ create_function_info_for (tree decl, con
       clobbervi->fullsize = vi->fullsize;
       clobbervi->is_full_var = true;
       clobbervi->is_global_var = false;
+      clobbervi->is_reg_var = true;
 
       gcc_assert (prev_vi->offset < clobbervi->offset);
       prev_vi->next = clobbervi->id;
@@ -5727,6 +5740,7 @@ create_function_info_for (tree decl, con
       usevi->fullsize = vi->fullsize;
       usevi->is_full_var = true;
       usevi->is_global_var = false;
+      usevi->is_reg_var = true;
 
       gcc_assert (prev_vi->offset < usevi->offset);
       prev_vi->next = usevi->id;
@@ -7075,6 +7089,39 @@ solve_constraints (void)
 {
   struct scc_info *si;
 
+  /* Sort varinfos so that ones that cannot be pointed to are last.
+     This makes bitmaps more efficient.  */
+  unsigned int *map = XNEWVEC (unsigned int, varmap.length ());
+  for (unsigned i = 0; i < integer_id + 1; ++i)
+    map[i] = i;
+  /* Start with non-register vars (as possibly address-taken), followed
+     by register vars as conservative set of vars never appearing in
+     the points-to solution bitmaps.  */
+  unsigned j = integer_id + 1;
+  for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
+    if (! varmap[i]->is_reg_var)
+      map[i] = j++;
+  for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
+    if (varmap[i]->is_reg_var)
+      map[i] = j++;
+  /* Shuffle varmap according to map.  */
+  for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
+    {
+      while (map[varmap[i]->id] != i)
+	std::swap (varmap[i], varmap[map[varmap[i]->id]]);
+      gcc_assert (bitmap_empty_p (varmap[i]->solution));
+      varmap[i]->id = i;
+      varmap[i]->next = map[varmap[i]->next];
+      varmap[i]->head = map[varmap[i]->head];
+    }
+  /* Finally rewrite constraints.  */
+  for (unsigned i = 0; i < constraints.length (); ++i)
+    {
+      constraints[i]->lhs.var = map[constraints[i]->lhs.var];
+      constraints[i]->rhs.var = map[constraints[i]->rhs.var];
+    }
+  free (map);
+
   if (dump_file)
     fprintf (dump_file,
 	     "\nCollapsing static cycles and doing variable "