[commited] PR18419

[Steven Bosscher <stevenb at suse dot de>]

Hi,

I'm going to apply this as approved by Diego in the PR audit trail.
The test case is one of Brad Lucier's machine generated pieces, and
the patch decreases the compile time problem for me with 20% without
negative compile time effects on human crafted code.

Gr.
Steven


	* tree-ssa.c (walk_use_def_chains_1): Make the visited map a
	pointer set instead of a bitmap.
	(walk_use_def_chains): Create, pass and clean up that pointer_set.

	* tree-ssa-alias.c (struct alias_info): Make the ssa_names_visited
	field an sbitmap.
	(init_alias_info): Allocate and zero it here.
	(delete_alias_info): Delete it here.
	(collect_points_to_info_for): Use it.

Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa.c,v
retrieving revision 2.56
diff -u -3 -p -r2.56 tree-ssa.c
--- tree-ssa.c	8 Nov 2004 13:54:40 -0000	2.56
+++ tree-ssa.c	11 Nov 2004 01:05:00 -0000
@@ -36,6 +36,7 @@ Boston, MA 02111-1307, USA.  */
 #include "function.h"
 #include "diagnostic.h"
 #include "bitmap.h"
+#include "pointer-set.h"
 #include "tree-flow.h"
 #include "tree-gimple.h"
 #include "tree-inline.h"
@@ -905,8 +906,10 @@ tree_ssa_useless_type_conversion (tree e
 /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
    described in walk_use_def_chains.
    
-   VISITED is a bitmap used to mark visited SSA_NAMEs to avoid
-      infinite loops.
+   VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
+      infinite loops.  We used to have a bitmap for this to just mark
+      SSA versions we had visited.  But non-sparse bitmaps are way too
+      expensive, while sparse bitmaps may cause quadratic behavior.
 
    IS_DFS is true if the caller wants to perform a depth-first search
       when visiting PHI nodes.  A DFS will visit each PHI argument and
@@ -916,15 +919,13 @@ tree_ssa_useless_type_conversion (tree e
 
 static bool
 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
-		       bitmap visited, bool is_dfs)
+		       struct pointer_set_t *visited, bool is_dfs)
 {
   tree def_stmt;
 
-  if (bitmap_bit_p (visited, SSA_NAME_VERSION (var)))
+  if (pointer_set_insert (visited, var))
     return false;
 
-  bitmap_set_bit (visited, SSA_NAME_VERSION (var));
-
   def_stmt = SSA_NAME_DEF_STMT (var);
 
   if (TREE_CODE (def_stmt) != PHI_NODE)
@@ -1002,9 +1003,9 @@ walk_use_def_chains (tree var, walk_use_
     (*fn) (var, def_stmt, data);
   else
     {
-      bitmap visited = BITMAP_XMALLOC ();
+      struct pointer_set_t *visited = pointer_set_create ();
       walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
-      BITMAP_XFREE (visited);
+      pointer_set_destroy (visited);
     }
 }
 
Index: tree-ssa-alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-alias.c,v
retrieving revision 2.52
diff -u -3 -p -r2.52 tree-ssa-alias.c
--- tree-ssa-alias.c	5 Nov 2004 10:56:01 -0000	2.52
+++ tree-ssa-alias.c	11 Nov 2004 01:05:28 -0000
@@ -73,7 +73,7 @@ struct alias_info
   /* SSA names visited while collecting points-to information.  If bit I
      is set, it means that SSA variable with version I has already been
      visited.  */
-  bitmap ssa_names_visited;
+  sbitmap ssa_names_visited;
 
   /* Array of SSA_NAME pointers processed by the points-to collector.  */
   varray_type processed_ptrs;
@@ -368,7 +368,8 @@ init_alias_info (void)
   static bool aliases_computed_p = false;
 
   ai = xcalloc (1, sizeof (struct alias_info));
-  ai->ssa_names_visited = BITMAP_XMALLOC ();
+  ai->ssa_names_visited = sbitmap_alloc (num_ssa_names);
+  sbitmap_zero (ai->ssa_names_visited);
   VARRAY_TREE_INIT (ai->processed_ptrs, 50, "processed_ptrs");
   ai->addresses_needed = BITMAP_XMALLOC ();
   VARRAY_UINT_INIT (ai->num_references, num_referenced_vars, "num_references");
@@ -449,7 +450,7 @@ delete_alias_info (struct alias_info *ai
 {
   size_t i;
 
-  BITMAP_XFREE (ai->ssa_names_visited);
+  sbitmap_free (ai->ssa_names_visited);
   ai->processed_ptrs = NULL;
   BITMAP_XFREE (ai->addresses_needed);
 
@@ -484,9 +485,9 @@ collect_points_to_info_for (struct alias
 {
   gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr)));
 
-  if (!bitmap_bit_p (ai->ssa_names_visited, SSA_NAME_VERSION (ptr)))
+  if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (ptr)))
     {
-      bitmap_set_bit (ai->ssa_names_visited, SSA_NAME_VERSION (ptr));
+      SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (ptr));
       walk_use_def_chains (ptr, collect_points_to_info_r, ai, true);
       VARRAY_PUSH_TREE (ai->processed_ptrs, ptr);
     }