[tree-ssa] Improve handling of call-clobbered variables [patch]

Diego Novillo dnovillo@redhat.com
Sun Mar 23 18:05:00 GMT 2003


On Sat, 22 Mar 2003, Diego Novillo wrote:

> Right now, I think it's better to leave things as they are with
> one chang: GLOBAL_VAR should only be allowed to alias
> call-clobbered variables.  This will avoid having a huge unique
> alias set when we use type-based aliasing.
> 
This patch implements the above.  It exposed a bug in the hashing
functions for redundant expressions.  avail_expr_eq was not
comparing VUSE operands and was returning true for two statements
that seemed identical but had VUSE operands.

We were allowing alias sets with only one element.  Which caused
the SSA pass not to rename variables that were considered alias
with themselves.

I also kept the fixes to CCP (volatile variables were being
constant propagated) and aliasing (structure aliasing).

Bootstrapped and tested x86, ppc and x86-64.


Diego.

	* Makefile.in (gtype-desc.o): Add dependency on $(TREE_FLOW_H).

	* tree-dfa.c (struct alias_set_d): Add field 'num_elements'.
	(struct walk_state): Move declaration earlier in the file.
	(create_global_var): New local function.
	(num_referenced_vars, num_aliased_objects): Change type to
	'size_t'.  Update all users.
	(aliased_objects, aliased_objects_base, aliased_objects_aliase_set):
	Mark for garbage collection.
	(num_call_clobbered_vars, call_clobbered_vars): New global
	variable.
	(get_expr_operands): For CALL_EXPRs, add a VUSE or VDEF reference
	for every pointer argument.  If the call may clobber, add a VDEF,
	otherwise add a VUSE.
	If the call may clobber, add VDEF for GLOBAL_VAR.
	(dump_variable): Show whether the variable is call clobbered.
	(dump_dfa_stats): Show call clobbered variables.
	(compute_may_aliases): Minor formatting changes.
	(compute_alias_sets): If the function makes clobbering calls, add
	GLOBAL_VAR as an alias to every call-clobbered variable.
	Remove alias sets that have exactly one element.
	(register_alias_set): Set 'num_elements' to zero for every newly
	created alias set.
	(find_alias_for): Don't make a second call to add_may_alias to make
	alias tags alias themselves.  It's redundant.
	Increment 'num_elements' when adding a new alias to an alias set.
	(may_alias_p): Don't handle GLOBAL_VAR.
	Check for structure aliasing when either PTR or VAR are a
	structure.  Don't do it only when both are structures.
	(dump_alias_info): Show all aliases of each variable.
	(find_vars_r): When processing a CALL_EXPR node, set
	walk_state->is_store if the function may clobber and create a
	reference to GLOBAL_VAR.
	(add_indirect_ref_var): Change type of second argument from 'void *'
	to 'struct walk_state *'.  Update all users.
	(add_referenced_var): Likewise.  If a potentially aliased variabe
	is not declared 'const', add it to the list of call clobbered
	variables.

	* tree-flow.h (struct var_ann_d): Add field 'is_call_clobbered'.
	Change type of field 'uid' to size_t.  Update all users.
	(stmt_ann_d): Add field 'makes_clobbering_call'.
	(next_tree_ref_id): Remove unused variable.
	(call_clobbered_vars): Declare.
	(num_call_clobbered_vars): Declare.
	(call_clobbered_var): New inline function.

	* tree-ssa-ccp.c (visit_phi_node): If the LHS of a PHI node is
	volatile, mark the PHI node VARYING without checking its arguments.
	(visit_assignment): Likewise.
	(set_value): Remove.  Update all users.
	(likely_value): If the statement makes aliased loads or has
	volatile operands, consider it VARYING.
	(get_default_value): If a variable is volatile, consider it
	VARYING.

	* tree-ssa.c (init_tree_ssa): Initialize num_call_clobbered_vars
	and call_clobbered_vars.
	Do not create GLOBAL_VAR.  Set it to NULL_TREE.
	Increase initial size for various hash tables.
	(delete_tree_ssa): Reset num_call_clobbered_vars and
	call_clobbered_vars.
	(get_reaching_def): Rename from currdef_for.  Update all users.
	Always create default definitions for variables that need them.
	Callers that use to call currdef_for with the second argument set
	to false now call get_value_for.
	(htab_statistics): New function.
	(dump_tree_ssa): Call it.
	(avail_expr_eq): Also compare VUSE operands.

Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.79
diff -d -u -p -r1.903.2.79 Makefile.in
--- Makefile.in	10 Mar 2003 20:26:25 -0000	1.903.2.79
+++ Makefile.in	23 Mar 2003 04:15:27 -0000
@@ -1396,7 +1396,7 @@ version.o: version.c version.h
 gtype-desc.o: gtype-desc.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) varray.h \
 	$(HASHTAB_H) $(TREE_H) $(RTL_H) function.h insn-config.h $(EXPR_H) $(OPTABS_H) \
 	libfuncs.h debug.h $(GGC_H) bitmap.h $(BASIC_BLOCK_H) hard-reg-set.h \
-	ssa.h cselib.h insn-addr.h
+	ssa.h cselib.h insn-addr.h $(TREE_FLOW_H)
 
 ggc-common.o: ggc-common.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(GGC_H) \
 	$(HASHTAB_H) toplev.h $(PARAMS_H)
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.90
diff -d -u -p -r1.1.4.90 tree-dfa.c
--- tree-dfa.c	21 Mar 2003 23:00:27 -0000	1.1.4.90
+++ tree-dfa.c	23 Mar 2003 04:15:28 -0000
@@ -77,10 +77,19 @@ struct alias_set_d
   tree tag_sym;
   HOST_WIDE_INT tag_set;
   HOST_WIDE_INT tag_sym_set;
+  size_t num_elements;
 };
 
 static varray_type alias_sets;
 
+/* State information for find_vars_r.  */
+struct walk_state
+{
+  htab_t vars_found;
+  htab_t aliased_objects_found;
+  int is_store;
+};
+
 
 /* Flags to describe operand properties in get_stmt_operands and helpers.  */
 static const int opf_none	= 0;
@@ -120,25 +129,27 @@ static void add_stmt_operand		PARAMS ((t
       						 voperands_t));
 static void add_immediate_use		PARAMS ((tree, tree));
 static tree find_vars_r			PARAMS ((tree *, int *, void *));
-static void add_referenced_var		PARAMS ((tree, tree, void *));
-static void add_indirect_ref_var	PARAMS ((tree, void *));
+static void add_referenced_var		PARAMS ((tree, tree,
+						 struct walk_state *));
+static void add_indirect_ref_var	PARAMS ((tree, struct walk_state *));
 static void compute_immediate_uses_for	PARAMS ((tree, int));
 static void add_may_alias		PARAMS ((tree, tree, tree, tree));
 static bool call_may_clobber		PARAMS ((tree));
 static void find_vla_decls		PARAMS ((tree));
 static tree find_vla_decls_r		PARAMS ((tree *, int *, void *));
+static void create_global_var		PARAMS ((void));
 
 
 /* Global declarations.  */
 
 /* The total number of referenced variables in the function.  */
-unsigned long num_referenced_vars;
+size_t num_referenced_vars;
 
 /* Array of all variables referenced in the function.  */
 varray_type referenced_vars;
 
 /* The total number of unique aliased objects in the function.  */
-static unsigned long num_aliased_objects;
+static size_t num_aliased_objects;
 
 /* Arrays for all the potentially aliased memory objects in the 
    function.
@@ -155,16 +166,22 @@ static unsigned long num_aliased_objects
    ALIASED_OBJECTS contains the object 
    ALIASED_OBJECTS_BASE contains the base symbol for those objects
    ALIASED_OBJECTS_ALIAS_SET contains the alias set for those objects.  */
+static GTY(()) varray_type aliased_objects;
+static GTY(()) varray_type aliased_objects_base;
+static GTY(()) varray_type aliased_objects_alias_set;
 
-static varray_type aliased_objects;
-static varray_type aliased_objects_base;
-static varray_type aliased_objects_alias_set;
+/* The total number of unique call clobbered variables in the function.  */
+size_t num_call_clobbered_vars;
+
+/* Arrays for all the call clobbered variables in the function.  */
+varray_type call_clobbered_vars;
 
 /* Artificial variable used to model the effects of function calls on every
    variable that they may use and define.  Calls to non-const and non-pure
    functions are assumed to use and clobber this variable.
 
-   Aliased loads and stores will be considered aliased with this variable.  */
+   Loads and stores to call clobbered variables will be considered aliased
+   with this variable.  */
 tree global_var;
 
 /* Get the operands of statement STMT.  Note that repeated calls to
@@ -374,29 +391,23 @@ get_expr_operands (stmt, expr_p, flags, 
     }
 
   /* Function calls.  Add every argument to USES.  If the callee is
-     neither pure nor const, create a use and clobbering definition of
-     *GLOBAL_VAR (See find_vars_r).  */
+     neither pure nor const, create a VDEF reference for GLOBAL_VAR
+     (See find_vars_r).  */
   if (code == CALL_EXPR)
     {
+      int flags;
       tree op;
       bool may_clobber = call_may_clobber (expr);
 
       /* Find uses in the called function.  */
       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), opf_none, prev_vops);
 
-      if (may_clobber)
-	{
-	  /* If the called function is neither pure nor const, we create a
-	     clobbering definition of *GLOBAL_VAR.  */
-	  tree v = indirect_ref (global_var);
-	  add_stmt_operand (&v, stmt, opf_is_def|opf_force_vop, prev_vops);
-	}
-
-      /* Add all the arguments to the function.  If the function will not
-	 clobber any local variable, check if it may dereference a local
-	 pointer.  If so, add a VUSE for the dereferenced pointer.  This is
-	 to address the following problem: Suppose that function 'foo' is
-	 constant but receives a pointer to a local variable:
+      /* Add all the arguments to the function.  For every pointer argument
+	 to the function, add a VUSE for its dereferenced pointer (if the
+	 function is pure or const) or a VDEF for its dereferenced pointer
+	 (if the function may clobber).  This is to address the following
+	 problem: Suppose that function 'foo' receives a pointer to a local
+	 variable:
 
 	    int foo (int *x)
 	    {
@@ -415,26 +426,41 @@ get_expr_operands (stmt, expr_p, flags, 
 	 to kill the assignment to 'i' because it's never used in bar().
 	 To address this problem, we add a VUSE<*p> at the call site of
 	 foo().  */
+      flags = opf_force_vop | opf_ignore_bp;
+      if (may_clobber)
+	flags |= opf_is_def;
+
       for (op = TREE_OPERAND (expr, 1); op; op = TREE_CHAIN (op))
 	{
 	  tree arg = TREE_VALUE (op);
 
 	  add_stmt_operand (&TREE_VALUE (op), stmt, opf_none, prev_vops);
 
-	  /* If the function may not clobber locals, add a VUSE<*p> for
-	     every pointer p passed in the argument list (see note above).  */
-	  if (!may_clobber
-	      && SSA_DECL_P (arg)
+	  /* Add a VUSE<*p> or VDEF<*p> for every pointer p passed in the
+	     argument list (see note above).  */
+	  if (SSA_DECL_P (arg)
 	      && POINTER_TYPE_P (TREE_TYPE (arg)))
 	    {
 	      tree deref = indirect_ref (arg);
-	      /* We have already added a real USE for the pointer.  We
-		 don't need to add a VUSE for it as well.  */
-	      add_stmt_operand (&deref, stmt, opf_force_vop|opf_ignore_bp,
-				prev_vops);
+
+	      /* By default, adding a reference to an INDIRECT_REF
+		 variable, adds a VUSE of the base pointer.  Since we have
+		 already added a real USE for the pointer, we don't need to
+		 add a VUSE for it as well.  */
+	      add_stmt_operand (&deref, stmt, flags, prev_vops);
 	    }
 	}
 
+      /* If the called function is neither pure nor const, we create a
+	 definition of GLOBAL_VAR and mark the statement as a clobbering
+	 statement.  */
+      if (may_clobber)
+	{
+	  stmt_ann (stmt)->makes_clobbering_call = may_clobber;
+	  add_stmt_operand (&global_var, stmt, opf_is_def|opf_force_vop,
+			    prev_vops);
+	}
+
       return;
     }
 
@@ -1121,10 +1147,10 @@ void
 dump_referenced_vars (file)
      FILE *file;
 {
-  unsigned long i;
+  size_t i;
 
-  fprintf (file, "\nReferenced variables in %s: %lu\n\n", 
-	   get_name (current_function_decl), num_referenced_vars);
+  fprintf (file, "\nReferenced variables in %s: %u\n\n", 
+	   get_name (current_function_decl), (unsigned) num_referenced_vars);
 
   for (i = 0; i < num_referenced_vars; i++)
     {
@@ -1184,6 +1210,9 @@ dump_variable (file, var)
   if (may_point_to_global_mem_p (var))
     fprintf (file, ", may point to global memory");
 
+  if (var_ann (var)->is_call_clobbered)
+    fprintf (file, ", call clobbered");
+
   fprintf (file, "\n");
 }
 
@@ -1301,7 +1330,12 @@ dump_dfa_stats (file)
 
   size = num_aliased_objects * sizeof (tree);
   total += size;
-  fprintf (file, fmt_str_1, "Aliased objects", num_aliased_objects, 
+  fprintf (file, fmt_str_1, "Aliased variables", num_aliased_objects, 
+	   SCALE (size), LABEL (size));
+
+  size = num_call_clobbered_vars * sizeof (tree);
+  total += size;
+  fprintf (file, fmt_str_1, "Call clobbered variables", num_call_clobbered_vars,
 	   SCALE (size), LABEL (size));
 
   size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
@@ -1484,14 +1518,6 @@ clobber_vars_r (tp, walk_subtrees, data)
 /*---------------------------------------------------------------------------
 				    Aliasing
 ---------------------------------------------------------------------------*/
-
-struct walk_state
-{
-  htab_t vars_found;
-  htab_t aliased_objects_found;
-  int is_store;
-};
-
 /* Compute may-alias information for every variable referenced in the
    program.  Note that in the absence of points-to analysis
    (-ftree-points-to), this may compute a much bigger set than necessary.  */
@@ -1523,7 +1549,7 @@ compute_may_aliases ()
 
   /* Hash table of all the unique aliased objects found.  */
   aliased_objects_found = htab_create (50, htab_hash_pointer, htab_eq_pointer,
-				     NULL);
+				       NULL);
 
   walk_state.vars_found = vars_found;
   walk_state.aliased_objects_found = aliased_objects_found;
@@ -1554,9 +1580,9 @@ compute_may_aliases ()
     }
 
   num_aliased_objects = 0;
-  aliased_objects = 0;
-  aliased_objects_base = 0;
-  aliased_objects_alias_set = 0;
+  aliased_objects = NULL;
+  aliased_objects_base = NULL;
+  aliased_objects_alias_set = NULL;
 
   timevar_pop (TV_TREE_MAY_ALIAS);
 }
@@ -1584,40 +1610,19 @@ static void
 compute_alias_sets ()
 {
   size_t i;
-  tree var, sym, deref_gv;
+  tree var, sym;
 
   VARRAY_GENERIC_PTR_INIT (alias_sets, 20, "alias_sets");
 
   /* For each object that is stored in the program, compute its alias set
      and register it in ALIAS_SETS.  If P's alias set does not conflict
      with any entry in ALIAS_SETS, or if it conflicts with more than one
-     entry, create a new entry for P.
-
-     We need to treat GLOBAL_VAR separately.  Since GLOBAL_VAR aliases
-     variables that might have been otherwise unaliased, we register it
-     first so that we make sure that if GLOBAL_VAR is needed for this
-     function, it is always an alias tag.  Otherwise we will miss the
-     following case:  Suppose that *P and Q are two variables that don't
-     alias each other:
-
-	foo (*P)
-	{
-	  *P = ...;
-	  bar (&Q);
-	}
-
-     If *P is added to ALIAS_SETS first, then we will build an alias set
-     tagged with *P which contains *P and GLOBAL_VAR.  However, since Q
-     does not conflict with *P, it will never be added to the set.  */
-  deref_gv = indirect_ref (global_var);
-  if (deref_gv)
-    register_alias_set (deref_gv, global_var);
-
+     entry, create a new entry for P.  */
   for (i = 0; i < num_aliased_objects; i++)
     {
       var = VARRAY_TREE (aliased_objects, i);
       sym = VARRAY_TREE (aliased_objects_base, i);
-      if (var_ann (var)->is_stored && var != deref_gv)
+      if (var_ann (var)->is_stored)
 	register_alias_set (var, sym);
     }
 
@@ -1631,6 +1636,45 @@ compute_alias_sets ()
       find_alias_for (var, sym);
     }
 
+  /* Alias sets with exactly one entry are for variables that are not found
+     to alias anything else but themselves.  This is not necessary, so we
+     remove these sets.  */
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (alias_sets); i++)
+    {
+      struct alias_set_d *as;
+      size_t num_sets;
+
+      as = (struct alias_set_d *) VARRAY_GENERIC_PTR (alias_sets, i);
+      if (as->num_elements == 1)
+	{
+	  var_ann_t ann = var_ann (as->tag);
+	  ann->may_alias_global_mem = 0;
+	  ann->may_aliases = NULL;
+
+	  /* Remove the alias set by swapping the current and the last
+	     element, and popping the array.  */
+	  num_sets = VARRAY_ACTIVE_SIZE (alias_sets);
+	  if (i < num_sets - 1)
+	    {
+	      VARRAY_GENERIC_PTR (alias_sets, i) =
+		  VARRAY_GENERIC_PTR (alias_sets, num_sets - 1);
+	      i--;	/* Reset the iterator to avoid missing the entry we
+			   just swapped.  */
+	    }
+	  VARRAY_POP (alias_sets);
+	}
+    }
+
+  /* If the function has calls to clobbering functions, make GLOBAL_VAR alias
+     all call-clobbered variables.  */
+  if (global_var)
+    for (i = 0; i < num_call_clobbered_vars; i++)
+      {
+	var = call_clobbered_var (i);
+	sym = get_base_symbol (var);
+	add_may_alias (var, sym, global_var, global_var);
+      }
+
   /* Debugging dumps.  */
   if (tree_ssa_dump_file && tree_ssa_dump_flags & TDF_ALIAS)
     {
@@ -1650,7 +1694,7 @@ compute_alias_sets ()
 }
 
 
-/* Try to add DEREF as a new new alias tag in ALIAS_SETS.  If a conflicting
+/* Try to add DEREF as a new alias tag in ALIAS_SETS.  If a conflicting
    tag is already present, then instead of adding a new entry, DEREF is
    marked as an alias of the existing entry.  DEREF_SYM is the base symbol
    of DEREF.  */
@@ -1754,6 +1798,7 @@ register_alias_set (deref, deref_sym)
       curr->tag_set = deref_set;
       curr->tag_sym = deref_sym;
       curr->tag_sym_set = deref_sym_set;
+      curr->num_elements = 0;
       VARRAY_PUSH_GENERIC_PTR (alias_sets, (void *) curr);
     }
 }
@@ -1790,29 +1835,7 @@ find_alias_for (var, sym)
 	{
 	  /* Set the tag to be the alias for VAR.  */
 	  add_may_alias (var, sym, as->tag, as->tag_sym);
-
-	  if (may_aliases (as->tag) == NULL)
-	    {
-	      /* Force the alias tag to alias itself.  This avoids problems
-		 when the program is accessing the alias tag directly.  For
-		 instance, suppose that '*p' is the alias tag for 'i' and
-		 'j':
-
-			1  i = ...
-			2  *p = ...
-			3  ... = i
-
-		If '*p' is not made an alias of itself, then the assignment
-		at line 2 will be considered a killing definition of '*p'.
-		This would make the assignment to 'i' at line 1 appear dead
-		because the use of 'i' at line 3 is now reached by the
-		assignment to '*p' at line 2.
-
-		If '*p' does not alias 'i' at runtime, the compiler
-		would've generated wrong code.  This fixes the regression
-		of gcc.c-torture/execute/950929-1.c.  */
-	      add_may_alias (as->tag, as->tag_sym, as->tag, as->tag_sym);
-	    }
+	  as->num_elements++;
 	}
     }
 }
@@ -1840,9 +1863,9 @@ may_alias_p (v1, v1_base, v1_alias_set, 
   if (v1 == v2)
     return true;
 
-  /* One of the two variables needs to be an INDIRECT_REF or GLOBAL_VAR,
-     otherwise they can't possibly alias each other.  */
-  if (TREE_CODE (v1) == INDIRECT_REF || v1 == global_var)
+  /* One of the two variables needs to be an INDIRECT_REF, otherwise they
+     can't possibly alias each other.  */
+  if (TREE_CODE (v1) == INDIRECT_REF)
     {
       ptr = v1;
       ptr_sym = v1_base;
@@ -1851,7 +1874,7 @@ may_alias_p (v1, v1_base, v1_alias_set, 
       var_sym = v2_base;
       var_alias_set = v2_alias_set;
     }
-  else if (TREE_CODE (v2) == INDIRECT_REF || v2 == global_var)
+  else if (TREE_CODE (v2) == INDIRECT_REF)
     {
       ptr = v2;
       ptr_sym = v2_base;
@@ -1863,38 +1886,10 @@ may_alias_p (v1, v1_base, v1_alias_set, 
   else
     return false;
 
-  /* GLOBAL_VAR aliases every global variable, pointer dereference and
-     locals that have had their address taken, unless points-to analysis is
-     done.  This is because points-to is supposed to handle this case, and
-     thus, can give a more accurate answer.   */
-  if (ptr_sym == global_var
-      && (TREE_ADDRESSABLE (var_sym)
-	  || TREE_CODE (var) == INDIRECT_REF
-	  || decl_function_context (var_sym) == NULL))
-    {
-      if (flag_tree_points_to == PTA_NONE)	 
-	return true;
-      else
-	{
-	  /* Right now, it's just not worth the time/space to make
-	     points-to handle the global variables seperately (in
-	     intraprocedural mode, anyway).  */	     
-	  if (decl_function_context (var_sym) == NULL)
-	    return true;
-	  
-	  /* For GLOBAL_VAR, we want to see if the variable aliases
-	     GLOBAL_VAR, not if GLOBAL_VAR aliases the variable (since
-	     the points-to sets are possibly directional, and
-	     GLOBAL_VAR never gets assigned to, only assigned from). */ 
-	  if (ptr_may_alias_var (var_sym, ptr_sym))
-	    return true;  
-	}
-    }
-
   /* If the alias sets don't conflict then PTR cannot alias VAR.  */
   if (!alias_sets_conflict_p (ptr_alias_set, var_alias_set))
     {
-      /* Handle aliases to structure fields.  If both VAR and PTR are
+      /* Handle aliases to structure fields.  If either VAR or PTR are
 	 aggregate types, they may not have conflicting types, but one of
 	 the structures could contain a pointer to the other one.
 
@@ -1912,12 +1907,28 @@ may_alias_p (v1, v1_base, v1_alias_set, 
 	 or 'struct Q' aliases 'struct P *'.  Notice, that since GIMPLE
 	 does not have more than one-level pointers, we don't need to
 	 recurse into the structures.  */
-      if (TREE_CODE (var) == INDIRECT_REF
-	  && AGGREGATE_TYPE_P (TREE_TYPE (ptr))
-	  && AGGREGATE_TYPE_P (TREE_TYPE (var))
-	  && (alias_sets_conflict_p (ptr_alias_set, get_alias_set (var_sym))
-	     || alias_sets_conflict_p (var_alias_set, get_alias_set (ptr_sym))))
-	return true;
+      if (AGGREGATE_TYPE_P (TREE_TYPE (ptr))
+	  || AGGREGATE_TYPE_P (TREE_TYPE (var)))
+	{
+	  tree ptr_to_var;
+
+	  /* If VAR is not an INDIRECT_REF, we use the canonical pointer-to
+	     VAR's type.  */
+	  if (TREE_CODE (var) == INDIRECT_REF)
+	    ptr_to_var = var_sym;
+	  else
+	    {
+	      ptr_to_var = TYPE_POINTER_TO (TREE_TYPE (var));
+	      /* If no pointer-to VAR exists, then PTR can't possibly alias
+		  VAR.  */
+	      if (ptr_to_var == NULL_TREE)
+		return false;
+	    }
+
+	return 
+	  alias_sets_conflict_p (ptr_alias_set, get_alias_set (ptr_to_var))
+	  || alias_sets_conflict_p (var_alias_set, get_alias_set (ptr_sym));
+	}
       else
 	return false;
     }
@@ -1979,7 +1990,7 @@ void
 dump_alias_info (file)
      FILE *file;
 {
-  unsigned long i, j;
+  size_t i, j, k;
 
   if (alias_sets == NULL)
     return;
@@ -1993,7 +2004,7 @@ dump_alias_info (file)
 
       as = (struct alias_set_d *) VARRAY_GENERIC_PTR (alias_sets, i);
 
-      fprintf (file, "Alias set #%ld:\n", i);
+      fprintf (file, "Alias set #%u:\n", (unsigned) i);
       fprintf (file, "  Tag: ");
       dump_variable (file, as->tag);
       fprintf (file, "  Aliases objects: { ");
@@ -2002,11 +2013,12 @@ dump_alias_info (file)
 	{
 	  tree var = VARRAY_TREE (aliased_objects, j);
 	  varray_type aliases = may_aliases (var);
-	  if (aliases && VARRAY_TREE (aliases, 0) == as->tag)
-	    {
-	      print_generic_expr (file, var, 0);
-	      fprintf (file, " ");
-	    }
+	  for (k = 0; aliases && k < VARRAY_ACTIVE_SIZE (aliases); k++)
+	    if (VARRAY_TREE (aliases, k) == as->tag)
+	      {
+		print_generic_expr (file, var, 0);
+		fprintf (file, " ");
+	      }
 	}
       fprintf (file, "}\n\n");
     }
@@ -2199,47 +2211,39 @@ find_vars_r (tp, walk_subtrees, data)
 	    set_indirect_ref (sym, var);
 	}
 
-      add_referenced_var (var, sym, data);
+      add_referenced_var (var, sym, walk_state);
 
       return NULL_TREE;
     }
 
-
-  /* Function calls.  Consider them a reference for an artificial variable
-     called GLOBAL_VAR.  This variable is a pointer that will alias every
-     global variable and locals that have had their address taken.  The
-     exception to this rule are functions marked pure, const or if they are
-     known to not return.
-
-     Stores to *GLOBAL_VAR will reach uses of every call clobbered variable
-     in the function.  Uses of *GLOBAL_VAR will be reached by definitions
-     of call clobbered variables.
-
-     This is used to model the effects that the called function may have on
-     local and global variables that might be visible to it.  */
+  /* A function call that receives pointer arguments may dereference them.
+     For every pointer 'p' add '*p' to the list of referenced variables.
+     See the handler for CALL_EXPR nodes in get_expr_operands for details.  */
   if (TREE_CODE (*tp) == CALL_EXPR)
     {
-      if (call_may_clobber (*tp))
+      tree op;
+      bool may_clobber = call_may_clobber (*tp);
+
+      if (may_clobber)
+	walk_state->is_store = 1;
+
+      for (op = TREE_OPERAND (*tp, 1); op; op = TREE_CHAIN (op))
 	{
-          walk_state->is_store = 1;
-	  add_indirect_ref_var (global_var, data);
+	  tree arg = TREE_VALUE (op);
+	  if (SSA_DECL_P (arg)
+	      && POINTER_TYPE_P (TREE_TYPE (arg)))
+	    add_indirect_ref_var (arg, walk_state);
 	}
-      else
-	{
-	  tree op;
 
-          walk_state->is_store = 0;
-	  /* If the function does not clobber locals, it still may
-	     dereference them.  Scan its operands to see if it receives any
-	     pointers.  For every pointer 'p' add '*p' to the list of
-	     referenced variables.  */
-	  for (op = TREE_OPERAND (*tp, 1); op; op = TREE_CHAIN (op))
-	    {
-	      tree arg = TREE_VALUE (op);
-	      if (SSA_DECL_P (arg) && POINTER_TYPE_P (TREE_TYPE (arg)))
-		add_indirect_ref_var (arg, data);
-	    }
+      /* If the function may clobber globals and addressable locals, add a
+	 reference to GLOBAL_VAR.  */
+      if (may_clobber)
+	{
+	  if (global_var == NULL_TREE)
+	    create_global_var ();
+	  add_referenced_var (global_var, global_var, walk_state);
 	}
+
       walk_state->is_store = saved_is_store;
     }
 
@@ -2252,29 +2256,35 @@ find_vars_r (tp, walk_subtrees, data)
    same tree.
    
    Also add VAR to the ALIASED_OBJECTS set of varrays that are needed for
-   alias analysis.  DATA is an array with two hash tables used to avoid
-   adding the same variable more than once to its corresponding set as
-   well as a bit indicating if we're processing a load or store.  Note
-   that this function assumes that VAR is a valid SSA variable.  */
+   alias analysis.
+   
+   WALK_STATE is an array with two hash tables used to avoid adding the
+   same variable more than once to its corresponding set as well as a bit
+   indicating if we're processing a load or store.  Note that this function
+   assumes that VAR is a valid SSA variable.  */
 
 static void
-add_referenced_var (var, sym, data)
+add_referenced_var (var, sym, walk_state)
      tree var;
      tree sym;
-     void *data;
+     struct walk_state *walk_state;
 {
   void **slot;
-  struct walk_state *walk_state = (struct walk_state *)data;
   htab_t vars_found = walk_state->vars_found;
   htab_t aliased_objects_found = walk_state->aliased_objects_found;
   int is_store = walk_state->is_store;
 
-  /* First handle aliasing information.  */
+  /* First handle aliasing information.  INDIRECT_REF, global and
+     addressable local variables are all potentially aliased and call
+     clobbered.  */
   if (TREE_CODE (var) == INDIRECT_REF
       || TREE_ADDRESSABLE (sym)
       || decl_function_context (sym) == NULL)
     {
-      var_ann_t ann;
+      var_ann_t ann = var_ann (var);
+      if (! ann)
+	ann = create_var_ann (var);
+
       slot = htab_find_slot (aliased_objects_found, (void *) var, INSERT);
       if (*slot == NULL)
 	{
@@ -2284,12 +2294,18 @@ add_referenced_var (var, sym, data)
 	  VARRAY_PUSH_TREE (aliased_objects_base, sym);
 	  VARRAY_PUSH_INT (aliased_objects_alias_set, get_alias_set (var));
 	  num_aliased_objects++;
+
+	  /* If the variable is not read-only, it may also be clobbered by
+	     function calls.  */
+	  if (!TREE_READONLY (var))
+	    {
+	      VARRAY_PUSH_TREE (call_clobbered_vars, var);
+	      num_call_clobbered_vars++;
+	      ann->is_call_clobbered = 1;
+	    }
 	}
 
       /* Note if this object was loaded or stored.  */
-      ann = var_ann (var);
-      if (! ann)
-	ann = create_var_ann (var);
       if (is_store)
 	ann->is_stored = 1;
       else
@@ -2334,14 +2350,14 @@ add_referenced_var (var, sym, data)
 
 
 /* Add a reference to the INDIRECT_REF node of variable VAR.  If VAR has
-   not been dereferenced yet, create a new INDIRECT_REF node for it.  DATA
-   is as in add_referenced_var.  Note that VAR is assumed to be a valid
-   pointer decl.  */
+   not been dereferenced yet, create a new INDIRECT_REF node for it.
+   WALK_STATE is as in add_referenced_var.  Note that VAR is assumed to be
+   a valid pointer decl.  */
 
 static void
-add_indirect_ref_var (ptr, data)
+add_indirect_ref_var (ptr, walk_state)
      tree ptr;
-     void *data;
+     struct walk_state *walk_state;
 {
   tree deref = indirect_ref (ptr);
   if (deref == NULL_TREE)
@@ -2350,7 +2366,7 @@ add_indirect_ref_var (ptr, data)
       set_indirect_ref (ptr, deref);
     }
 
-  add_referenced_var (deref, ptr, data);
+  add_referenced_var (deref, ptr, walk_state);
 }
 
 
@@ -2450,4 +2466,26 @@ find_vla_decls_r (tp, walk_subtrees, dat
     set_vla_decl (*tp);
 
   return NULL_TREE;
+}
+
+
+/* Create GLOBAL_VAR, an artificial global variable to act as a
+   representative of all the variables that may be clobbered by function
+   calls.  Also create GLOBAL_CLOBBER_EXPR, an artificial expression that
+   is used as the originating definition of all clobbered SSA variables in
+   the program.  */
+
+static void
+create_global_var ()
+{
+  global_var = build_decl (VAR_DECL, get_identifier (".GLOBAL_VAR"),
+                           size_type_node);
+  DECL_ARTIFICIAL (global_var) = 1;
+  TREE_READONLY (global_var) = 1;
+  DECL_EXTERNAL (global_var) = 0;
+  TREE_STATIC (global_var) = 1;
+  TREE_USED (global_var) = 1;
+  DECL_CONTEXT (global_var) = current_function_decl;
+  TREE_THIS_VOLATILE (global_var) = 1;
+  TREE_ADDRESSABLE (global_var) = 0;
 }
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.63
diff -d -u -p -r1.1.4.63 tree-flow.h
--- tree-flow.h	18 Mar 2003 14:52:25 -0000	1.1.4.63
+++ tree-flow.h	23 Mar 2003 04:15:28 -0000
@@ -68,16 +68,19 @@ struct var_ann_d GTY(())
      
      Note this only applies to objects which are subject to
      alias analysis.  */
-  unsigned int is_stored: 1;
+  unsigned is_stored : 1;
 
   /* Nonzero if this variable was loaded/read in this function.
 
      Note this only applies to objects which are subject to
      alias analysis.  */
-  unsigned int is_loaded: 1;
+  unsigned is_loaded : 1;
+
+  /* Nonzero if the variable may be modified by function calls.  */
+  unsigned is_call_clobbered : 1;
 
   /* Unused bits.  */
-  unsigned int unused: 27;
+  unsigned unused : 26;
 
   /* An INDIRECT_REF expression representing all the dereferences of this
      pointer.  Used to store aliasing information for pointer dereferences
@@ -88,7 +91,7 @@ struct var_ann_d GTY(())
   varray_type may_aliases;
   
   /* Unique ID of this variable.  */
-  int uid;
+  size_t uid;
 };
 
 
@@ -106,10 +109,10 @@ typedef struct operands_d *operands_t;
 
 struct voperands_d GTY(())
 {
-  /* List of V_DEF references in this statement.  */
+  /* List of VDEF references in this statement.  */
   varray_type vdef_ops;
 
-  /* List of V_USE references in this statement.  */
+  /* List of VUSE references in this statement.  */
   varray_type GTY ((skip (""))) vuse_ops;
 };
 
@@ -175,6 +178,10 @@ struct stmt_ann_d GTY(())
   /* Nonzero if the statement makes references to volatile storage.  */
   unsigned has_volatile_ops : 1;
 
+  /* Nonzero if the statement makes a function call that may clobber global
+     and local addressable variables.  */
+  unsigned makes_clobbering_call : 1;
+
   /* Basic block that contains this statement.  */
   basic_block GTY ((skip (""))) bb;
 
@@ -325,14 +332,11 @@ extern int tree_warn_uninitialized;
 /* Array of all variables referenced in the function.  */
 extern GTY(()) varray_type referenced_vars;
 
-/* Next unique reference ID to be assigned by create_ref().  */
-extern unsigned long next_tree_ref_id;
-
 /* Artificial variable used to model the effects of function calls.  */
 extern GTY(()) tree global_var;
 
 /* Accessors for the referenced_vars array.  */
-extern unsigned long num_referenced_vars;
+extern size_t num_referenced_vars;
 
 static inline tree referenced_var PARAMS ((size_t));
 static inline tree
@@ -340,6 +344,20 @@ referenced_var (i)
      size_t i;
 {
   return VARRAY_TREE (referenced_vars, i);
+}
+
+/* Array of all variables that are call clobbered in the function.  */
+extern GTY(()) varray_type call_clobbered_vars;
+
+/* The total number of unique call clobbered variables in the function.  */
+extern size_t num_call_clobbered_vars;
+
+static inline tree call_clobbered_var PARAMS ((size_t));
+static inline tree
+call_clobbered_var (i)
+     size_t i;
+{
+  return VARRAY_TREE (call_clobbered_vars, i);
 }
 
 /* Macros for showing usage statistics.  */
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-ccp.c,v
retrieving revision 1.1.2.63
diff -d -u -p -r1.1.2.63 tree-ssa-ccp.c
--- tree-ssa-ccp.c	6 Mar 2003 20:52:54 -0000	1.1.2.63
+++ tree-ssa-ccp.c	23 Mar 2003 04:15:28 -0000
@@ -121,7 +121,6 @@ static latticevalue likely_value	PARAMS 
 static void fold_stmt			PARAMS ((tree));
 static tree get_rhs			PARAMS ((tree));
 static void set_rhs			PARAMS ((tree, tree));
-static void set_value			PARAMS ((tree, latticevalue, tree));
 static value *get_value			PARAMS ((tree));
 static value get_default_value		PARAMS ((tree));
 static hashval_t value_map_hash		PARAMS ((const void *));
@@ -344,7 +343,10 @@ visit_phi_node (phi)
   phi_val.lattice_val = UNDEFINED;
   phi_val.const_val = NULL_TREE;
 
-  if (!TREE_THIS_VOLATILE (SSA_NAME_VAR (PHI_RESULT (phi))))
+  /* If the variable is volatile, consider it VARYING.  */
+  if (TREE_THIS_VOLATILE (SSA_NAME_VAR (PHI_RESULT (phi))))
+    phi_val.lattice_val = VARYING;
+  else
     for (i = 0; i < PHI_NUM_ARGS (phi); i++)
       {
 	/* Compute the meet operator over all the PHI arguments. */
@@ -362,27 +364,15 @@ visit_phi_node (phi)
 	if (e->flags & EDGE_EXECUTABLE)
 	  {
 	    tree rdef = PHI_ARG_DEF (phi, i);
+	    value *rdef_val = get_value (rdef);
+	    phi_val = cp_lattice_meet (phi_val, *rdef_val);
 
-	    if (!TREE_THIS_VOLATILE (SSA_NAME_VAR (rdef)))
-	      {
-		value *rdef_val = get_value (rdef);
-		phi_val = cp_lattice_meet (phi_val, *rdef_val);
-
-		if (dump_file && (dump_flags & TDF_DETAILS))
-		  {
-		    fprintf (dump_file, "\t");
-		    print_generic_expr (dump_file, rdef, 0);
-		    dump_lattice_value (dump_file, "\tValue: ", *rdef_val);
-		    fprintf (dump_file, "\n");
-		  }
-	      }
-	    else
+	    if (dump_file && (dump_flags & TDF_DETAILS))
 	      {
-		/* If the variable is volatile, we cannot assume anything
-		   about this PHI's node value.  In that case, set its
-		   value to VARYING.  */
-		phi_val.lattice_val = VARYING;
-		phi_val.const_val = NULL_TREE;
+		fprintf (dump_file, "\t");
+		print_generic_expr (dump_file, rdef, 0);
+		dump_lattice_value (dump_file, "\tValue: ", *rdef_val);
+		fprintf (dump_file, "\n");
 	      }
 
 	    if (phi_val.lattice_val == VARYING)
@@ -502,7 +492,7 @@ visit_stmt (stmt)
   /* Mark all VDEF operands VARYING.  */
   ops = vdef_ops (stmt);
   for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
-    set_value (VDEF_RESULT (VARRAY_TREE (ops, i)), VARYING, NULL_TREE);
+    def_to_varying (VDEF_RESULT (VARRAY_TREE (ops, i)));
 }
 
 
@@ -514,19 +504,26 @@ visit_assignment (stmt)
      tree stmt;
 {
   value val;
+  tree lhs, rhs;
 
 #if defined ENABLE_CHECKING
   if (!def_op (stmt))
     abort ();
 #endif
 
-  if (TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
-      && TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME)
+  lhs = TREE_OPERAND (stmt, 0);
+  rhs = TREE_OPERAND (stmt, 1);
+
+  if (TREE_THIS_VOLATILE (SSA_NAME_VAR (lhs)))
     {
-      /* For a simple copy operation, we copy the lattice
-         values.  */
-      value *nval = get_value (TREE_OPERAND (stmt, 1));
-       
+      /* Volatile variables are always VARYING.  */
+      val.lattice_val = VARYING;
+      val.const_val = NULL_TREE;
+    }
+  else if (TREE_CODE (rhs) == SSA_NAME)
+    {
+      /* For a simple copy operation, we copy the lattice values.  */
+      value *nval = get_value (rhs);
       val.lattice_val = nval->lattice_val;
       val.const_val = nval->const_val;
     }
@@ -1024,7 +1021,6 @@ def_to_undefined (var)
       value->lattice_val = UNDEFINED;
       value->const_val = NULL_TREE;
     }
-
 }
 
 
@@ -1045,7 +1041,6 @@ def_to_varying (var)
       value->lattice_val = VARYING;
       value->const_val = NULL_TREE;
     }
-
 }
 
 
@@ -1150,9 +1145,16 @@ likely_value (stmt)
   varray_type uses;
   size_t i;
   int found_constant = 0;
+  stmt_ann_t ann;
 
   get_stmt_operands (stmt);
 
+  /* If the statement makes aliased loads or has volatile operands, it
+     won't fold to a constant value.  */
+  ann = stmt_ann (stmt);
+  if (ann->makes_aliased_loads || ann->has_volatile_ops)
+    return VARYING;
+
   uses = use_ops (stmt);
   for (i = 0; uses && i < VARRAY_ACTIVE_SIZE (uses); i++)
     {
@@ -1166,7 +1168,7 @@ likely_value (stmt)
 	found_constant = 1;
     }
 
-  return (found_constant || (!uses && !vuse_ops (stmt)) ? CONSTANT : VARYING);
+  return ((found_constant || !uses) ? CONSTANT : VARYING);
 }
 
 
@@ -1287,66 +1289,34 @@ get_default_value (var)
      tree var;
 {
   value val;
+  tree sym;
 
-  if (!DECL_P (var))
-    var = get_base_symbol (var);
+  sym = (!DECL_P (var)) ? get_base_symbol (var) : var;
 
   val.lattice_val = UNDEFINED;
   val.const_val = NULL_TREE;
 
-  if (TREE_CODE (var) == PARM_DECL)
+  if (TREE_CODE (sym) == PARM_DECL || TREE_THIS_VOLATILE (sym))
     {
-      /* Function arguments are considered VARYING.  */
+      /* Function arguments and volatile variables are considered VARYING.  */
       val.lattice_val = VARYING;
     }
-  else if (decl_function_context (var) == NULL_TREE || TREE_STATIC (var))
+  else if (decl_function_context (sym) == NULL_TREE || TREE_STATIC (sym))
     {
-      /* Globals and static variables are considered VARYING.  */
+      /* Globals and static variables are considered VARYING, unless they
+	 are declared 'const'.  */
       val.lattice_val = VARYING;
 
-      /* Except if they are declared 'const'.  */
-      if (TREE_READONLY (var)
-	  && DECL_INITIAL (var)
-	  && really_constant_p (DECL_INITIAL (var)))
+      if (TREE_READONLY (sym)
+	  && DECL_INITIAL (sym)
+	  && really_constant_p (DECL_INITIAL (sym)))
 	{
 	  val.lattice_val = CONSTANT;
-	  val.const_val = DECL_INITIAL (var);
+	  val.const_val = DECL_INITIAL (sym);
 	}
     }
 
   return val;
-}
-
-
-/* Set the value for variable VAR to <LATTICE_VAL, CONST_VAL>.  */
-
-static void
-set_value (var, lattice_val, const_val)
-     tree var;
-     latticevalue lattice_val;
-     tree const_val;
-{
-  void **slot;
-  struct value_map_d *vm_p, vm;
-
-#if defined ENABLE_CHECKING
-  if (TREE_CODE (var) != SSA_NAME)
-    abort ();
-#endif
-
-  vm.var = var;
-  slot = htab_find_slot (const_values, (void *) &vm, INSERT);
-  if (*slot == NULL)
-    {
-      vm_p = xmalloc (sizeof (*vm_p));
-      vm_p->var = var;
-      *slot = (void *) vm_p;
-    }
-  else
-    vm_p = (struct value_map_d *) *slot;
-
-  vm_p->val.lattice_val = lattice_val;
-  vm_p->val.const_val = const_val;
 }
 
 
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.57
diff -d -u -p -r1.1.4.57 tree-ssa.c
--- tree-ssa.c	11 Mar 2003 16:34:53 -0000	1.1.4.57
+++ tree-ssa.c	23 Mar 2003 04:15:29 -0000
@@ -149,7 +149,7 @@ static void update_indirect_ref_vuses	PA
 static void update_pointer_vuses	PARAMS ((tree, tree, varray_type));
 static void insert_phi_nodes_for	PARAMS ((tree, bitmap *));
 static tree remove_annotations_r	PARAMS ((tree *, int *, void *));
-static tree currdef_for			PARAMS ((tree, int));
+static tree get_reaching_def		PARAMS ((tree));
 static tree get_value_for		PARAMS ((tree, htab_t));
 static void set_value_for		PARAMS ((tree, tree, htab_t));
 static hashval_t def_blocks_hash	PARAMS ((const void *));
@@ -162,6 +162,7 @@ static tree lookup_avail_expr		PARAMS ((
 static hashval_t avail_expr_hash	PARAMS ((const void *));
 static int avail_expr_eq		PARAMS ((const void *, const void *));
 static struct def_blocks_d *get_def_blocks_for PARAMS ((tree));
+static void htab_statistics		PARAMS ((FILE *, htab_t));
 
 /* FIXME: [UNSSA] Remove once the real unSSA pass is implemented.  */
 #if 1
@@ -424,7 +425,7 @@ mark_def_sites (idom, globals)
 	  for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
 	    {
 	      tree *use = VARRAY_GENERIC_PTR (ops, i);
-	      int uid = var_ann (*use)->uid;
+	      size_t uid = var_ann (*use)->uid;
 
 	      if (! TEST_BIT (kills, uid))
 		{
@@ -438,7 +439,7 @@ mark_def_sites (idom, globals)
 	  for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
 	    {
 	      tree use = VARRAY_TREE (ops, i);
-	      int uid = var_ann (use)->uid;
+	      size_t uid = var_ann (use)->uid;
 
 	      if (! TEST_BIT (kills, uid))
 	        {
@@ -457,7 +458,7 @@ mark_def_sites (idom, globals)
 	    {
 	      tree vdef = VARRAY_TREE (ops, i);
 	      tree vdef_op = VDEF_OP (vdef);
-	      int uid = var_ann (vdef_op)->uid;
+	      size_t uid = var_ann (vdef_op)->uid;
 
 	      set_def_block (VDEF_RESULT (vdef), bb);
 	      if (!TEST_BIT (kills, uid))
@@ -465,7 +466,6 @@ mark_def_sites (idom, globals)
 		  SET_BIT (globals, uid);
 	          set_livein_block (vdef_op, bb);
 		}
-
 	    }
 
 	  /* Now process the definition made by this statement.  */
@@ -475,7 +475,6 @@ mark_def_sites (idom, globals)
 	      set_def_block (*dest, bb);
 	      SET_BIT (kills, var_ann (*dest)->uid);
 	    }
-
 	}
     }
 
@@ -665,7 +664,7 @@ rewrite_block (bb)
 	{
 	  /* FIXME.  [UNSSA] After fixing the SSA->normal pass, allow
 	     constants and copies to be propagated into PHI arguments.  */
-	  tree currdef = currdef_for (SSA_NAME_VAR (PHI_RESULT (phi)), true);
+	  tree currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
 	  add_phi_arg (phi, currdef, e);
 	}
     }
@@ -895,6 +894,20 @@ dump_tree_ssa_stats (file)
 	   tmp, PERCENT (tmp, n_exprs));
 #endif
 
+  fprintf (file, "\nHash table statistics:\n");
+
+  fprintf (file, "    def_blocks: ");
+  htab_statistics (file, def_blocks);
+
+  fprintf (file, "    currdefs: ");
+  htab_statistics (file, currdefs);
+
+  fprintf (file, "    avail_exprs: ");
+  htab_statistics (file, avail_exprs);
+
+  fprintf (file, "    const_and_copies: ");
+  htab_statistics (file, const_and_copies);
+
   fprintf (file, "\n");
 }
 
@@ -908,6 +921,19 @@ debug_tree_ssa_stats ()
 }
 
 
+/* Dump statistics for the hash table HTAB.  */
+
+static void
+htab_statistics (file, htab)
+     FILE *file;
+     htab_t htab;
+{
+  fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
+	   (long) htab_size (htab),
+	   (long) htab_elements (htab),
+	   htab_collisions (htab));
+}
+
 
 /*---------------------------------------------------------------------------
 		  Helpers for the main SSA building functions
@@ -1277,7 +1303,7 @@ static inline void
 rewrite_operand (op_p)
      tree *op_p;
 {
-  tree op, currdef;
+  tree op;
 
 #if defined ENABLE_CHECKING
   if (TREE_CODE (*op_p) == SSA_NAME)
@@ -1302,13 +1328,12 @@ rewrite_operand (op_p)
   op = *op_p;
   if (TREE_CODE (op) == INDIRECT_REF)
     {
-      tree base = currdef_for (TREE_OPERAND (op, 0), false);
+      tree base = get_value_for (TREE_OPERAND (op, 0), currdefs);
       if (base && SSA_NAME_VAR (base) != TREE_OPERAND (op, 0))
 	op = indirect_ref (base);
     }
 
-  currdef = currdef_for (op, true);
-  *op_p = currdef;
+  *op_p = get_reaching_def (op);
 }
 
 
@@ -1321,7 +1346,7 @@ register_new_def (var, def, block_defs_p
      tree def;
      varray_type *block_defs_p;
 {
-  tree currdef = currdef_for (var, false);
+  tree currdef = get_value_for (var, currdefs);
 
   /* If the current reaching definition is NULL or a constant, push the
      variable itself so that rewrite_blocks knows what variable is
@@ -1412,20 +1437,10 @@ init_tree_ssa ()
   next_ssa_version = 1;
   num_referenced_vars = 0;
   VARRAY_TREE_INIT (referenced_vars, 20, "referenced_vars");
+  num_call_clobbered_vars = 0;
+  VARRAY_TREE_INIT (call_clobbered_vars, 20, "call_clobbered_vars");
   memset ((void *) &ssa_stats, 0, sizeof (ssa_stats));
-
-  /* Declare an artificial global variable to act as a representative of
-     all the variables that may be clobbered by function calls.  */
-  global_var = build_decl (VAR_DECL, get_identifier (".GLOBAL_VAR"),
-                           ptr_type_node);
-  DECL_ARTIFICIAL (global_var) = 1;
-  TREE_READONLY (global_var) = 0;
-  DECL_EXTERNAL (global_var) = 0;
-  TREE_STATIC (global_var) = 0;
-  TREE_USED (global_var) = 1;
-  DECL_CONTEXT (global_var) = NULL_TREE;
-  TREE_THIS_VOLATILE (global_var) = 1;
-  TREE_ADDRESSABLE (global_var) = 1;
+  global_var = NULL_TREE;
 
   /* Allocate memory for the DEF_BLOCKS hash table.  */
   def_blocks = htab_create (num_referenced_vars, def_blocks_hash,
@@ -1436,10 +1451,10 @@ init_tree_ssa ()
 			  free);
 
   /* Allocate memory for the AVAIL_EXPRS hash table.  */
-  avail_exprs = htab_create (100, avail_expr_hash, avail_expr_eq, NULL);
+  avail_exprs = htab_create (1024, avail_expr_hash, avail_expr_eq, NULL);
 
   /* Allocate memory for the CONST_AND_COPIES hash table.  */
-  const_and_copies = htab_create (50, var_value_hash, var_value_eq, free);
+  const_and_copies = htab_create (1024, var_value_hash, var_value_eq, free);
 }
 
 
@@ -1449,7 +1464,7 @@ static void
 delete_tree_ssa (fndecl)
      tree fndecl;
 {
-  unsigned long int i;
+  size_t i;
 
   /* Remove annotations from every tree in the function.  */
   walk_tree (&DECL_SAVED_TREE (fndecl), remove_annotations_r, NULL, NULL);
@@ -1461,6 +1476,8 @@ delete_tree_ssa (fndecl)
   num_referenced_vars = 0;
   referenced_vars = NULL;
   global_var = NULL_TREE;
+  num_call_clobbered_vars = 0;
+  call_clobbered_vars = NULL;
 }
 
 
@@ -1500,23 +1517,33 @@ remove_annotations_r (tp, walk_subtrees,
   return NULL_TREE;
 }
 
-/* Return the current definition for variable V.  If none is found and
-   CREATE_DEFAULT is nonzero, create a new SSA name to act as the zeroth
-   definition for V.  */
+/* Return the current definition for variable VAR.  If none is found,
+   create a new SSA name to act as the zeroth definition for VAR.  If VAR
+   is call clobbered and there exists a more recent definition of
+   GLOBAL_VAR, return the definition for GLOBAL_VAR.  This means that VAR
+   has been clobbered by a function call since its last assignment.  */
 
 static tree
-currdef_for (v, create_default)
-     tree v;
-     int create_default;
+get_reaching_def (var)
+     tree var;
 {
-  tree def = get_value_for (v, currdefs);
-  if (def == NULL_TREE && create_default)
+  tree default_def, currdef_var;
+  
+  /* Lookup the current reaching definition for VAR.  */
+  default_def = NULL_TREE;
+  currdef_var = get_value_for (var, currdefs);
+
+  /* If there is no reaching definition for VAR, create and register a
+     default definition for it.  */
+  if (currdef_var == NULL_TREE)
     {
-      def = make_ssa_name (v, empty_stmt_node);
-      set_value_for (v, def, currdefs);
+      default_def = make_ssa_name (var, empty_stmt_node);
+      set_value_for (var, default_def, currdefs);
     }
 
-  return def;
+  /* Return the current reaching definition for VAR, or the default
+     definition, if we had to create one.  */
+  return (currdef_var) ? currdef_var : default_def;
 }
 
 
@@ -1751,8 +1778,30 @@ avail_expr_eq (p1, p2)
   s2 = (tree) p2;
   rhs2 = TREE_OPERAND (s2, 1);
 
-  return (TREE_CODE (rhs1) == TREE_CODE (rhs2)
-	  && simple_cst_equal (rhs1, rhs2) == 1);
+  /* In case of a collision, both RHS have to be identical and have the
+     same VUSE operands.  */
+  if (TREE_CODE (rhs1) == TREE_CODE (rhs2)
+      && simple_cst_equal (rhs1, rhs2) == 1)
+    {
+      varray_type ops1 = vuse_ops (s1);
+      varray_type ops2 = vuse_ops (s2);
+
+      if (ops1 == NULL && ops2 == NULL)
+	return true;
+
+      if (ops1 == ops2
+	  && VARRAY_ACTIVE_SIZE (ops1) == VARRAY_ACTIVE_SIZE (ops2))
+	{
+	  size_t i;
+	  for (i = 0; i < VARRAY_ACTIVE_SIZE (ops1); i++)
+	    if (VARRAY_GENERIC_PTR (ops1, i) != VARRAY_GENERIC_PTR (ops2, i))
+	      return false;
+
+	  return true;
+	}
+    }
+
+  return false;
 }
 
 
@@ -1786,7 +1835,7 @@ var_is_live (var, bb)
   struct def_blocks_d *def_map;
   tree real_var = SSA_NAME_VAR (var);
 
-  if (currdef_for (real_var, false) != var)
+  if (get_value_for (real_var, currdefs) != var)
     {
       ssa_stats.blocked_by_life_crossing++;
       return false;



More information about the Gcc-patches mailing list