[PATCH] Speed up PTA solving

[PATCH] Speed up PTA solving

[Richard Biener]

The following patch resulted from PR81827 analysis where I was on
the wrong track initially.  It still results in a small speedup
because we avoid useless duplicate work in case nodes are unified
and reduce the number of graph edges.

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

Richard.

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

	* tree-ssa-structalias.c (solve_graph): When propagating
	to successors update the graphs succ edges and avoid duplicate work.

Index: gcc/tree-ssa-structalias.c
===================================================================
--- gcc/tree-ssa-structalias.c	(revision 251119)
+++ gcc/tree-ssa-structalias.c	(working copy)
@@ -2759,20 +2759,35 @@ solve_graph (constraint_graph_t graph)
 		  unsigned eff_escaped_id = find (escaped_id);
 
 		  /* Propagate solution to all successors.  */
+		  unsigned to_remove = ~0U;
 		  EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
 						0, j, bi)
 		    {
-		      bitmap tmp;
-		      bool flag;
-
+		      if (to_remove != ~0U)
+			{
+			  bitmap_clear_bit (graph->succs[i], to_remove);
+			  to_remove = ~0U;
+			}
 		      unsigned int to = find (j);
-		      tmp = get_varinfo (to)->solution;
-		      flag = false;
-
+		      if (to != j)
+			{
+			  /* Update the succ graph, avoiding duplicate
+			     work.  */
+			  to_remove = j;
+			  if (! bitmap_set_bit (graph->succs[i], to))
+			    continue;
+			  /* We eventually end up processing 'to' twice
+			     as it is undefined whether bitmap iteration
+			     iterates over bits set during iteration.
+			     Play safe instead of doing tricks.  */
+			}
 		      /* Don't try to propagate to ourselves.  */
 		      if (to == i)
 			continue;
 
+		      bitmap tmp = get_varinfo (to)->solution;
+		      bool flag = false;
+
 		      /* If we propagate from ESCAPED use ESCAPED as
 		         placeholder.  */
 		      if (i == eff_escaped_id)
@@ -2783,6 +2798,8 @@ solve_graph (constraint_graph_t graph)
 		      if (flag)
 			bitmap_set_bit (changed, to);
 		    }
+		  if (to_remove != ~0U)
+		    bitmap_clear_bit (graph->succs[i], to_remove);
 		}
 	    }
 	}