[tree-ssa]: Get points-to bootstrapping again

Daniel Berlin dberlin@dberlin.org
Sun Oct 12 22:44:00 GMT 2003


This patch does 2 things
1. It gets PTA bootstrapping and passing all regression tests again
2. Removes doxygen markers from tree-alias-common.c

It also handles each global var individually, which causes us a ~10% speed
loss in PTA speed (because so many things end up with global vars in their
points-to chain, not because of the number of global variables).

No worries though, we'll make it back in volume :)


On a related note, i've got patches for PTA that i've not submitted yet
that make it fully field based.

IE it can tell whether two component_ref's alias or not.

I've not submitted it because we don't query PTA about component_refs in
the current alias set creation code, and thus, only load PRE currently
uses it (which also has not been submitted).

I figured i'd submit it when i submit load PRE, though i'm happy to do it
earlier if someone else wants to be able to determine if two
component_ref's alias.

--Dan
2003-10-12  Daniel Berlin  <dberlin@dberlin.org>

	* tree-alias-ander.c (throwaway_global): Delete.
	(andersen_same_ponts_to_set): We handle all globals individually
	now.
	* tree-alias-common.c:  Remove doxygen markers.
	(get_alias_var_decl): Always create an alias var for globals now.
	Assign the global alias vars to GLOBAL_VAR, too.
	(intra_function_call): Fix logic, do a bit of pre-filtering to
	avoid useless global aliasing.
	(get_values_from_constructor): It's the same for field based and
	not field based.
	(create_alias_vars): Remove special global var handling.
	(same_points_to_set): Ditto.
	(ptr_may_alias_var): Ditto.
Index: tree-alias-ander.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-alias-ander.c,v
retrieving revision 1.1.2.18
diff -u -3 -p -w -B -b -r1.1.2.18 tree-alias-ander.c
--- tree-alias-ander.c	26 Sep 2003 00:44:35 -0000	1.1.2.18
+++ tree-alias-ander.c	12 Oct 2003 22:27:28 -0000
@@ -832,32 +832,6 @@ simple_cmp (const aterm a, const aterm b
   return (int *)a - (int *)b;
 }

-/* All this global var hackiness is because global_var is overloaded
-   in meaning. It's used for both call clobbering, and determining if
-   the global variable is aliased.  In order not to break call
-   clobbering, we delete global var when we are done, if we created
-   it.
-   We also ignore global_var aliasing in that case, but we still
-   have to go through the motions because something like this can
-   happen (IE global var still participates in aliasing relationships):
-   global_var = &a;
-   b = global_var;  */
-extern bool we_created_global_var;
-extern tree old_global_var;
-
-/* Simple function that returns false if the aterm is the global
-   variable's aterm, and true otherwise.  */
-
-static bool
-throwaway_global (const aterm a)
-{
-  if (DECL_PTA_TYPEVAR (old_global_var))
-    {
-      if (a == ALIAS_TVAR_ATERM (DECL_PTA_TYPEVAR (old_global_var)))
-	return false;
-    }
-  return true;
-}

 /* Determine if two aterm's have the same points-to set.
    When we didn't create global_var, we can just get the two points-to
@@ -888,22 +862,15 @@ andersen_same_points_to_set (struct tree
       ALIAS_TVAR_PTSET (vartv) = ptset2;
     }

-  if (!we_created_global_var)
-    {
       if (aterm_list_length (ptset1) != aterm_list_length (ptset2))
 	return false;
-    }
+
   if (ptset1 == ptset2)
     return true;

   ptset1 = aterm_list_copy (scratch_rgn, ptset1);
   ptset2 = aterm_list_copy (scratch_rgn, ptset2);

-  if (we_created_global_var)
-    {
-      ptset1 = aterm_list_filter (scratch_rgn, ptset1, throwaway_global);
-      ptset2 = aterm_list_filter (scratch_rgn, ptset2, throwaway_global);
-    }
   if (aterm_list_length (ptset1) != aterm_list_length (ptset2))
     return false;

Index: tree-alias-common.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-alias-common.c,v
retrieving revision 1.1.2.38
diff -u -3 -p -w -B -b -r1.1.2.38 tree-alias-common.c
--- tree-alias-common.c	4 Sep 2003 20:31:08 -0000	1.1.2.38
+++ tree-alias-common.c	12 Oct 2003 22:27:28 -0000
@@ -49,9 +49,7 @@ Foundation, Inc., 59 Temple Place, Suite
 #include "hashtab.h"
 #include "splay-tree.h"

-/**
-   @file tree-alias-common.c
-   This file contains the implementation of the common parts of the
+/*  This file contains the implementation of the common parts of the
    tree points-to analysis infrastructure.

    Overview:
@@ -65,26 +63,19 @@ Foundation, Inc., 59 Temple Place, Suite

    In order to speed up PTA queries, the PTA specific data is stored
    in the tree for *_DECL's, in DECL_PTA_TYPEVAR.  This way, we only
-   need to use the hash table for non-DECL's.
-
-*/
+    need to use the hash table for non-DECL's.  */
 #define FIELD_BASED 0

-/**
-   @brief Array of all created alias_typevars.
-
-   @note Should contain all the alias_typevars we wanted marked
-   during GC.
-*/
+/*  Array of all created alias_typevars.
+    Note that this should contain all the alias_typevars we wanted
+    marked during GC.  */
 static GTY((param_is (union alias_typevar_def))) varray_type alias_vars = NULL;
 struct tree_alias_ops *current_alias_ops;
-/**
-   @brief  Array of local alias_typevars.

-   @note Should contain all the alias_typevars that are local to
-   this function.  We delete these from alias_vars before
-   collection.
-*/
+/*  Array of local (to a function) alias_typevars.
+    Note that this should contain all the alias_typevars that are
+    local to this function.  We delete these from alias_vars before
+    collection.  */
 static varray_type local_alias_vars;
 static varray_type local_alias_varnums;

@@ -103,9 +94,9 @@ static hashval_t annot_hash (const PTR);
 static int annot_eq (const PTR, const PTR);
 static void get_values_from_constructor (tree, varray_type *);
 static bool call_may_clobber (tree);
-bool we_created_global_var = false;

 /* Return true if a EXPR, which is a CALL_EXPR, may clobber variables.  */
+
 static bool
 call_may_clobber (tree expr)
 {
@@ -121,24 +112,20 @@ call_may_clobber (tree expr)
 }


-/**
-   @brief Alias annotation hash table entry.
-
+/*  Alias annotation hash table entry.
    Used in the annotation hash table to map trees to their
-   alias_typevar's.
-*/
+    alias_typevar's.  */
+
 struct alias_annot_entry GTY(())
 {
   tree key;
   alias_typevar value;
 };

-/**
-   @brief Alias annotation equality.
-   @param pentry Entry in the hash table.
-   @param pdata  Entry we gave the function calling this.
-   @return 1 if \a pentry is equal to \a pdata, 0 if not.
-*/
+/*  Alias annotation equality function. PENTRY is the hash table
+    entry, PDATA is the entry we gave the function calling this.
+    Return 1 if PENTRY is equal to PDATA.  */
+
 static int
 annot_eq (const PTR pentry, const PTR pdata)
 {
@@ -148,11 +135,8 @@ annot_eq (const PTR pentry, const PTR pd
   return entry->key == data->key;
 }

-/**
-   @brief Alias annotation hash function.
-   @param pentry Entry to hash.
-   @return Hash value of \a pentry.
-*/
+/*  Alias annotation hash function.  Hash PENTRY and return a value.  */
+
 static hashval_t
 annot_hash (const PTR pentry)
 {
@@ -160,21 +144,14 @@ annot_hash (const PTR pentry)
   return htab_hash_pointer (entry->key);
 }

-/**
-   @brief Alias annotation hash table.
+/*  Alias annotation hash table.  Maps vars to alias_typevars.  */

-   Maps vars to alias_typevars.
-*/
 static GTY ((param_is (struct alias_annot_entry))) htab_t alias_annot;

-/**
-   @brief Get the alias_type for a *_DECL.
-   @param decl *_DECL to get the alias_typevar for.
-   @return The alias_typevar for \a decl.
-
-   @note Creates the alias_typevar if it does not exist already. Also
-   handles FUNCTION_DECL properly.
-*/
+/*  Get the alias_typevar for DECL.
+    Creates the alias_typevar if it does not exist already. Also
+    handles FUNCTION_DECL properly.  */
+
 static alias_typevar
 get_alias_var_decl (tree decl)
 {
@@ -191,11 +168,13 @@ get_alias_var_decl (tree decl)
     newvar = create_fun_alias_var  (decl, 0);
   else
     {
+      newvar = create_alias_var (decl);
+      /* Assign globals to global var for purposes of intraprocedural
+	 analyses. */
       if ((DECL_CONTEXT (decl) == NULL || TREE_PUBLIC (decl)
 	   || decl_function_context (decl) == NULL) && decl != global_var)
-	return get_alias_var (global_var);
-      else
-	newvar = create_alias_var (decl);
+	current_alias_ops->addr_assign (current_alias_ops,
+					get_alias_var (global_var), newvar);
     }

   if (!current_alias_ops->ip)
@@ -212,13 +191,10 @@ get_alias_var_decl (tree decl)
   return newvar;
 }

-/**
-   @brief Get the alias_typevar for an expression.
-   @param expr Expression we want the alias_typevar of.
-   @return The alias_typevar for \a expr.
+/* Get the alias_typevar for an expression EXPR.
+   Note that this function expects to only be handed a RHS or LHS, not
+   a MODIFY_EXPR.  */

-   @note Expects to only be handed a RHS or LHS, not a MODIFY_EXPR.
-*/
 static alias_typevar
 get_alias_var (tree expr)
 {
@@ -307,13 +283,10 @@ get_alias_var (tree expr)
     }
 }

-/**
-   @param args Arguments that were passed to the function call.
+/*  Perform conservative aliasing for an intraprocedural mode function
+    call.  ARGS are the arguments that were passed to that function
+    call.  */

-   Handles function calls in intra-procedural mode, by making
-   conservative assumptions about what happens to arguments to the
-   call.
-*/
 static void
 intra_function_call (varray_type args)
 {
@@ -332,14 +305,10 @@ intra_function_call (varray_type args)
       if (!TYPE_RESTRICT (TREE_TYPE (ALIAS_TVAR_DECL (argav)))
 	  || !TYPE_RESTRICT (TREE_TYPE (ALIAS_TVAR_DECL (av))))
 	{
-	  alias_typevar tempvar;
-	  tree temp = create_tmp_alias_var (void_type_node, "aliastmp");
-	  tempvar = current_alias_ops->add_var (current_alias_ops, temp);
 	  /* Arguments can alias globals, and whatever they point to
 	     can point to a global as well. */
-	  current_alias_ops->addr_assign (current_alias_ops, argav, av);
-	  current_alias_ops->addr_assign (current_alias_ops, tempvar, av);
-	  current_alias_ops->assign_ptr (current_alias_ops, argav, tempvar);
+	  if (!TREE_READONLY (ALIAS_TVAR_DECL (argav)))
+	    current_alias_ops->simple_assign (current_alias_ops, argav, av);
 	}
     }
   /* We assume assignments among the actual parameters. */
@@ -347,6 +316,8 @@ intra_function_call (varray_type args)
     {
       alias_typevar argi = VARRAY_GENERIC_PTR (args, i);
       size_t j;
+      if (!POINTER_TYPE_P (TREE_TYPE (ALIAS_TVAR_DECL (argi))))
+	continue;
       for (j = 0; j < l; j++)
 	{
 	  alias_typevar argj;
@@ -354,22 +325,26 @@ intra_function_call (varray_type args)
 	    continue;
 	  argj = VARRAY_GENERIC_PTR (args, j);

+	  /* Non pointers can't point to pointers.  */
+	  if (!POINTER_TYPE_P (TREE_TYPE (ALIAS_TVAR_DECL (argj))))
+	    continue;
 	  /* Restricted pointers can't be aliased with other
 	     restricted pointers. */
 	  if (!TYPE_RESTRICT (TREE_TYPE (ALIAS_TVAR_DECL (argi)))
 	      || !TYPE_RESTRICT (TREE_TYPE (ALIAS_TVAR_DECL (argj))))
+	    /* Do a bit of TBAA to avoid pointless assignments. */
+	    if (alias_sets_conflict_p (get_alias_set (ALIAS_TVAR_DECL (argi)),
+				       get_alias_set (ALIAS_TVAR_DECL (argj))))
 	    current_alias_ops->simple_assign (current_alias_ops, argi, argj);
 	}
     }
 }

-/** @brief Put all pointers in a constructor in an array.  */
+/* Put all pointers in a constructor in an array.  */
+
 static void
 get_values_from_constructor (tree constructor, varray_type *vals)
 {
-#if FIELD_BASED
- #error "Don't know how to do this at the moment"
-#else
   tree elt_list;
   switch (TREE_CODE (constructor))
     {
@@ -406,21 +381,18 @@ get_values_from_constructor (tree constr
     default:
       abort();
     }
-#endif
 }
-/**
-   @brief Tree walker that is the heart of the aliasing
-   infrastructure.
-   @param tp Pointer to the current tree.
-   @param walk_subtrees Whether to continue traversing subtrees or
+
+/*  Tree walker that is the heart of the aliasing infrastructure.
+    TP is a pointer to the current tree.
+    WALK_SUBTREES specifies whether to continue traversing subtrees or
    not.
-   @param data Not used.
-   @return NULL_TREE to keep going, anything else to stop.
+    Returns NULL_TREE when we should stop.

    This function is the main part of the aliasing infrastructure. It
    walks the trees, calling the approriate alias analyzer functions to process
-   various statements.
-*/
+    various statements.  */
+
 static tree
 find_func_aliases (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
 {
@@ -715,21 +687,15 @@ find_func_decls (tree *tp, int *walk_sub
 }
 #endif

-/**
-   @brief Create the alias_typevar for a function definition.
+/*  Create the alias_typevar for a function definition DECL, it's
+    arguments, and it's return value. If FORCE is true, we force
+    creation of the alias_typevar, regardless of whether one exists already.
+
+    This includes creation of alias_typevar's for
+    - The function itself.
+    - The arguments.
+    - The return value.  */

-   Create the alias_typevar for a function definition, it's
-   arguments, and it's return value.
-   @param decl FUNCTION_DECL for the function.
-   @param force If true, we force creation of the alias_typevar,
-   regardless of whether one exists already.
-
-   @note This includes creation of alias_typevar's for
-   -# The function itself.
-   -# The arguments.
-   -# The locals.
-   -# The return value.
-*/
 static alias_typevar
 create_fun_alias_var (tree decl, int force)
 {
@@ -826,20 +792,15 @@ create_fun_alias_var (tree decl, int for
   return avar;
 }

-/**
-   @brief Create the alias_typevar for a ptf.
-
-   Create a typevar for a pointer-to-member function, it's arguments,
+/*  Create a typevar for a pointer-to-member function DECL of type TYPE, it's arguments,
    and it's return value.
-   @param decl The PTF FUNCTION_DECL.
-   @param type the PTF type
-   @return The alias_typevar for the PTF.
-
-   @note This includes creating alias_typevar's for
-   -# The function itself.
-   -# The arguments.
-   -# The return value.
-*/
+    Returns the alias_typevar for the PTF.
+
+    This includes creating alias_typevar's for
+    - The function itself.
+    - The arguments.
+    - The return value.  */
+
 static alias_typevar
 create_fun_alias_var_ptf (tree decl, tree type)
 {
@@ -891,15 +852,12 @@ create_fun_alias_var_ptf (tree decl, tre
   return avar;
 }

-/**
-   @brief Create the alias_typevar for a *_DECL node.
-   @param decl Declaration to create alias_typevar for.
-   @return The alias_typevar for \a decl.
+/*  Create the alias_typevar for a *_DECL node DECL.
+    Returns the alias_typevar for DECL.

-   Create the alias_typevar for all types of declaration node.
+    This function also handles creation of alias_typevar's for PTF
+    variables.  */

-   @note Handles creation of alias_typevar's for PTF variables.
-*/
 static alias_typevar
 create_alias_var (tree decl)
 {
@@ -943,14 +901,12 @@ create_alias_var (tree decl)

   return avar;
 }
-tree old_global_var = NULL_TREE;
-/**
-   @brief Create points-to sets for a function.
-   @param fndecl Function we are creating alias variables for.
-
-   @note fndecl might not be current_function_decl, if we are in ip
-   mode or ip'ing all statics.
-*/
+
+/* Create points-to sets for function FNDECL.
+
+   Note that fndecl might not be current_function_decl, if we are in
+   ip mode or ip'ing all statics.  */
+
 void
 create_alias_vars (tree fndecl)
 {
@@ -959,14 +915,9 @@ create_alias_vars (tree fndecl)
   tree fnbody;
 #endif
   size_t i;
-  we_created_global_var = false;
   currptadecl = fndecl;
-  if (!global_var)
-    {
-      old_global_var = NULL_TREE;
       create_global_var ();
-      we_created_global_var = true;
-    }
+
   /* If the #if block printing out the points-to sets is #if 0'd out, the
      compiler will complain i is unused. So use it. */
   i = 0;
@@ -1002,17 +953,11 @@ create_alias_vars (tree fndecl)
       find_func_decls, NULL);*/
   walk_tree_without_duplicates (&DECL_SAVED_TREE (fndecl),
 				find_func_aliases, NULL);
-  if (we_created_global_var)
-    {
-      old_global_var = global_var;
       global_var = NULL_TREE;
     }

-}
+/* Delete created points-to sets.  */

-/**
-   @brief Delete created points-to sets.
-*/
 void
 delete_alias_vars (void)
 {
@@ -1044,9 +989,8 @@ delete_alias_vars (void)
   current_alias_ops->cleanup (current_alias_ops);
 }

-/**
-   @brief Initialize points-to analysis machinery.
-*/
+/*  Initialize points-to analysis machinery.  */
+
 void
 init_alias_vars (void)
 {
@@ -1061,13 +1005,14 @@ init_alias_vars (void)
     alias_annot = htab_create_ggc (7, annot_hash, annot_eq, NULL);

 }
+
+/* Return true if PTR and VAR have the same points-to set.  */
+
 bool
 same_points_to_set (tree ptr, tree var)
 {
   struct alias_annot_entry entry, *result;
   alias_typevar ptrtv, vartv;
-  tree ptrcontext;
-  tree varcontext;

 #if !FIELD_BASED
 #else
@@ -1077,85 +1022,50 @@ same_points_to_set (tree ptr, tree var)
     var = TREE_OPERAND (var, 1);
 #endif

-  ptrcontext = DECL_CONTEXT (ptr);
-  varcontext = DECL_CONTEXT (var);
-  if (TREE_PUBLIC (ptr))
-    ptr = global_var;
-  else
-    {
-      if (ptrcontext != NULL && TREE_CODE (ptrcontext) != FUNCTION_DECL)
-	ptrcontext = decl_function_context (ptr);
-      if (ptrcontext == NULL)
-	ptr = global_var;
-    }
-  if (TREE_PUBLIC (var))
-    var = global_var;
-  else
-    {
-      if (varcontext != NULL && TREE_CODE (varcontext) != FUNCTION_DECL)
-	varcontext = decl_function_context (var);
-      if (varcontext == NULL)
-	var = global_var;
-    }
-  if (ptr == var || (ptrcontext == NULL && varcontext == NULL)
-      || (ptr == global_var))
+  if (ptr == var)
     return true;

   if (DECL_P (ptr))
     {
       ptrtv = DECL_PTA_TYPEVAR (ptr);
-      if (!ptrtv && !current_alias_ops->ip && ptr != global_var)
-	abort ();
-      else if (!ptrtv)
+      if (!ptrtv)
 	return false;
     }
   else
     {
       entry.key = ptr;
       result = htab_find (alias_annot, &entry);
-      if (!result && !current_alias_ops->ip && ptr != global_var)
-	abort ();
-      else if (!result)
+      if (!result)
 	return false;
       ptrtv = result->value;
     }
-  if (var == global_var && global_var == NULL)
-    return false;
+
   if (DECL_P (var))
     {
       vartv = DECL_PTA_TYPEVAR (var);
-      if (!vartv && !current_alias_ops->ip && var != global_var)
-	abort ();
-      else if (!vartv)
+      if (!vartv)
 	return false;
     }
   else
     {
       entry.key = var;
       result = htab_find (alias_annot, &entry);
-      if (!result && !current_alias_ops->ip && var != global_var)
-	abort ();
-      else if (!result)
+      if (!result)
 	return false;

       vartv = result->value;
     }
   return current_alias_ops->same_points_to_set (current_alias_ops, vartv, ptrtv);
 }
-/**
-   @brief Determine whether two variables may-alias.

-   @param ptr Pointer.
-   @param var Variable.
-   @return true if \a ptr may-alias \a var, false otherwise.
-*/
+/*  Determine whether two variables (PTR and VAR) may-alias.
+    Returns TRUE if PTR may-alias VAR.  */
+
 bool
 ptr_may_alias_var (tree ptr, tree var)
 {
   struct alias_annot_entry entry, *result;
   alias_typevar ptrtv, vartv;
-  tree ptrcontext;
-  tree varcontext;

 #if !FIELD_BASED
 #else
@@ -1165,65 +1075,35 @@ ptr_may_alias_var (tree ptr, tree var)
     var = TREE_OPERAND (var, 1);
 #endif

-  ptrcontext = DECL_CONTEXT (ptr);
-  varcontext = DECL_CONTEXT (var);
-  if (TREE_PUBLIC (ptr))
-    ptr = global_var;
-  else
-    {
-      if (ptrcontext != NULL && TREE_CODE (ptrcontext) != FUNCTION_DECL)
-	ptrcontext = decl_function_context (ptr);
-      if (ptrcontext == NULL)
-	ptr = global_var;
-    }
-  if (TREE_PUBLIC (var))
-    var = global_var;
-  else
-    {
-      if (varcontext != NULL && TREE_CODE (varcontext) != FUNCTION_DECL)
-	varcontext = decl_function_context (var);
-      if (varcontext == NULL)
-	var = global_var;
-    }
-  if (ptr == var || (ptrcontext == NULL && varcontext == NULL)
-      || (ptr == global_var))
+  if (ptr == var)
     return true;

   if (DECL_P (ptr))
     {
       ptrtv = DECL_PTA_TYPEVAR (ptr);
-      if (!ptrtv && !current_alias_ops->ip && ptr != global_var)
-	abort ();
-      else if (!ptrtv)
+      if (!ptrtv)
 	return false;
     }
   else
     {
       entry.key = ptr;
       result = htab_find (alias_annot, &entry);
-      if (!result && !current_alias_ops->ip && ptr != global_var)
-	abort ();
-      else if (!result)
+      if (!result)
 	return false;
       ptrtv = result->value;
     }
-  if (var == global_var && global_var == NULL)
-    return false;
+
   if (DECL_P (var))
     {
       vartv = DECL_PTA_TYPEVAR (var);
-      if (!vartv && !current_alias_ops->ip && var != global_var)
-	abort ();
-      else if (!vartv)
+      if (!vartv)
 	return false;
     }
   else
     {
       entry.key = var;
       result = htab_find (alias_annot, &entry);
-      if (!result && !current_alias_ops->ip && var != global_var)
-	abort ();
-      else if (!result)
+      if (!result)
 	return false;

       vartv = result->value;



More information about the Gcc-patches mailing list