[improved-aliasing]: Remove possible O(n^2) behavior in callclobbering

[Daniel Berlin <dberlin at dberlin dot org>]

Right now we do things like:

          if (pi->pt_vars)
            EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi)
              mark_call_clobbered (referenced_var (j));

mark_call_clobbered, in turn, is:


/* Mark variable VAR as being clobbered by function calls.  */
static inline void
mark_call_clobbered (tree var)
{
  bitmap_set_bit (call_clobbered_vars, DECL_UID (var));
  ssa_call_clobbered_cache_valid = false;
  ssa_ro_call_cache_valid = false;
}

Note we do a linear iteration (bitmap walk) -> hashtable lookup
(referenced var lookup) -> bit find and set (bitmap_set_bit).

All to do a bitmap union.

if we had a 

static inline void
mark_bitmap_call_clobbered (bitmap ids)
{
  bitmap_ior_into (call_clobbered_vars, ids);
  ssa_call_clobbered_cache_valid = false;
  ssa_ro_call_cache_valid = false;
}


You could then just replace it with
if (pt->pt_vars)  
  mark_bitmap_call_clobbered (pi->pt_vars)


Which is what i've done on improved-aliasing :)
One could apply the same trick to the mainline, if they felt so
inclined.

Bootstrapped and regtested on i686-pc-linux-gnu.
Applied to improved-aliasing-branch

2005-09-11  Daniel Berlin  <dberlin@dberlin.org>

	* tree-ssa-alias.c (set_initial_clobbers): Use
	mark_bitmap_call_clobbered.  
	(group_aliases): Ditto.
	* tree-flow-inline.h (mark_bitmap_call_clobbered): New function.
	* tree-flow.h: Declare mark_bitmap_call_clobbered.

Index: tree-ssa-alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-alias.c,v
retrieving revision 2.109.4.2
diff -u -p -r2.109.4.2 tree-ssa-alias.c
--- tree-ssa-alias.c	12 Sep 2005 02:16:36 -0000	2.109.4.2
+++ tree-ssa-alias.c	12 Sep 2005 02:36:27 -0000
@@ -237,11 +237,9 @@ set_initial_clobbers (struct alias_info 
   
   for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++)
     {
-      unsigned j;
       tree ptr = VARRAY_TREE (ai->processed_ptrs, i);
       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
       var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr));
-      bitmap_iterator bi;
 
       if (pi->value_escapes_p || pi->pt_anything)
 	{
@@ -254,8 +252,7 @@ set_initial_clobbers (struct alias_info 
 	    mark_call_clobbered (v_ann->type_mem_tag);
 
 	  if (pi->pt_vars)
-	    EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi)
-	      mark_call_clobbered (referenced_var (j));
+	    mark_bitmap_call_clobbered (pi->pt_vars);
 	}
       /* If the name tag is call clobbered, so is the type tag
 	 associated with the base VAR_DECL.  */
@@ -1210,24 +1207,13 @@ group_aliases (struct alias_info *ai)
 
 	      if (!is_call_clobbered (tag1) && is_call_clobbered (tag2))
 		{
-		  bitmap_iterator bi;
 		  mark_call_clobbered (tag1);
-		  EXECUTE_IF_SET_IN_BITMAP (tag1_aliases, 0, k, bi)
-		    {
-		      tree var = referenced_var (k);
-		      mark_call_clobbered (var);
-		    }
-
+		  mark_bitmap_call_clobbered (tag1_aliases);
 		}
 	      else if (is_call_clobbered (tag1) && !is_call_clobbered (tag2))
 		{
-		  bitmap_iterator bi;
 		  mark_call_clobbered (tag2);
-		  EXECUTE_IF_SET_IN_BITMAP (tag2_aliases, 0, k, bi)
-		    {
-		      tree var = referenced_var (k);
-		      mark_call_clobbered (var);
-		    }
+		  mark_bitmap_call_clobbered (tag2_aliases);
 		}
 
 	      bitmap_ior_into (tag1_aliases, tag2_aliases);
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow-inline.h,v
retrieving revision 2.56
diff -u -p -r2.56 tree-flow-inline.h
--- tree-flow-inline.h	13 Aug 2005 17:28:39 -0000	2.56
+++ tree-flow-inline.h	12 Sep 2005 02:36:27 -0000
@@ -852,4 +852,14 @@ is_call_clobbered (tree var)
 
+/* Mark the variables in IDS (which is a set of DECL_UIDs), as being
+   clobbered by function calls.   */
+static inline void
+mark_bitmap_call_clobbered (bitmap ids)
+{
+  bitmap_ior_into (call_clobbered_vars, ids);
+  ssa_call_clobbered_cache_valid = false;
+  ssa_ro_call_cache_valid = false;
+}
+  
 /* Clear the call-clobbered attribute from variable VAR.  */
 static inline void
 clear_call_clobbered (tree var)
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.132
diff -u -p -r2.132 tree-flow.h
--- tree-flow.h	13 Aug 2005 17:28:40 -0000	2.132
+++ tree-flow.h	12 Sep 2005 02:36:27 -0000
@@ -771,6 +771,7 @@ extern enum move_pos movement_possibilit
 /* In tree-flow-inline.h  */
 static inline bool is_call_clobbered (tree);
 static inline void mark_call_clobbered (tree);
+static inline void mark_bitmap_call_clobbered (bitmap);
 static inline void set_is_used (tree);
 static inline bool unmodifiable_var_p (tree);