This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[tree-ssa] Aliasing fix and ADDR_EXPR fix


This patch fixes a number of failures in the libstdc++ testsuite when
we run it through the tree-ssa optimizers.  There are two distinct bugs
worth mentioning.

First get_expr_operands completely ignored ADDR_EXPR expressions.  That
is wrong as we could have something like &(p->q) which obviously
references "p".    From my reading of tree-simple.c it became clear
that a similar situation may also exist for &array[index].  Anyway
failure to note operands in these expressions were used caused DCE
to delete necessary code in libstdc++.

The second problem was a serious flaw in the aliasing code.  Given three
alias sets, call them A, B & C, the aliasing code assumed that if 
A aliased B and A aliased C, then A carried *all* the aliases that B & C
might have.  Ouch.  This caused mis-compilations of hunks of libstdc++
as well as the libstdc++ testsuite itself.

Along the way I plugged a memory leak in the aliasing code and removed
a field in a structure that was set, but never used.

Bootstrapped, regression tested (including C++/libstdc++ with tree-ssa
opts enabled :-)

	* tree-dfa.c (struct alias_set_d, field tag_sym_set): Remove
	unused field.
	(register_alias_set): Rework to avoid incorrect coalescing of
	entries.  Fix memory leak.  No longer set field tag_sym_set.
	(get_expr_operands): ADDR_EXPR expressions may have interesting
	operands in some cases.

Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.95
diff -c -3 -p -r1.1.4.95 tree-dfa.c
*** tree-dfa.c	7 Apr 2003 01:07:57 -0000	1.1.4.95
--- tree-dfa.c	14 Apr 2003 15:42:13 -0000
*************** struct alias_set_d
*** 76,82 ****
    tree tag;
    tree tag_sym;
    HOST_WIDE_INT tag_set;
-   HOST_WIDE_INT tag_sym_set;
    size_t num_elements;
  };
  
--- 76,81 ----
*************** get_expr_operands (stmt, expr_p, flags, 
*** 323,334 ****
    if (class == 'c'
        || class == 't'
        || class == 'b'
-       || code == ADDR_EXPR
        || code == FUNCTION_DECL
        || code == EXC_PTR_EXPR
        || code == LABEL_DECL)
      return;
  
    /* If this reference is associated with a non SIMPLE expression, then we
       mark the statement non GIMPLE and recursively clobber every
       variable referenced by STMT.  FIXME: TREE_NOT_GIMPLE must die.  */
--- 322,352 ----
    if (class == 'c'
        || class == 't'
        || class == 'b'
        || code == FUNCTION_DECL
        || code == EXC_PTR_EXPR
        || code == LABEL_DECL)
      return;
  
+   /* We could have the address of a component, array member, etc which
+      has interesting variable references.  */
+   if (code == ADDR_EXPR)
+     {
+       enum tree_code subcode = TREE_CODE (TREE_OPERAND (expr, 0));
+ 
+       /* Only a few specific types of ADDR_EXPR expressions are
+        	 of interest.  */
+       if (subcode != COMPONENT_REF
+ 	  && subcode != INDIRECT_REF
+ 	  && subcode != ARRAY_REF)
+ 	return;
+ 
+       /* Avoid recursion.  */
+       code = subcode;
+       class = TREE_CODE_CLASS (code);
+       expr_p = &TREE_OPERAND (expr, 0);
+       expr = *expr_p;
+     }
+ 
    /* If this reference is associated with a non SIMPLE expression, then we
       mark the statement non GIMPLE and recursively clobber every
       variable referenced by STMT.  FIXME: TREE_NOT_GIMPLE must die.  */
*************** compute_alias_sets ()
*** 1785,1794 ****
  }
  
  
! /* 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.  */
  
  static void
  register_alias_set (deref, deref_sym)
--- 1803,1813 ----
  }
  
  
! /* Potentially add DEREF as a new alias tag in ALIAS_SETS.  DEREF_SYM
!    is the base symbol of DEREF. 
! 
!    Note that if DEREF == DEREF_SYM, then we know implicitly that
!    DEREF is an addressable DECL.  */
  
  static void
  register_alias_set (deref, deref_sym)
*************** register_alias_set (deref, deref_sym)
*** 1796,1894 ****
       tree deref_sym;
  {
    size_t i, num_sets;
!   struct alias_set_d *curr, *prev;
!   HOST_WIDE_INT deref_set, deref_sym_set;
!   long last_found;
  
    deref_set = get_alias_set (deref);
-   deref_sym_set = get_alias_set (deref_sym);
  
    /* FIXME: ALIAS_SETS will usually be small (<< 10 entries).  If it becomes
       a performance problem, try with a splay tree.  */
!   last_found = -1;
!   prev = NULL;
    for (i = 0; i < VARRAY_ACTIVE_SIZE (alias_sets); i++)
      {
        curr = (struct alias_set_d *) VARRAY_GENERIC_PTR (alias_sets, i);
  
!       if (may_alias_p (deref, deref_sym, deref_set,
! 	               curr->tag, curr->tag_sym, curr->tag_set))
! 	{
! 	  /* If this is the first time we find a conflict, mark the entry
! 	     index where the conflict was found and continue.  */
! 	  if (last_found == -1)
! 	    {
! 	      last_found = i;
! 	      continue;
! 	    }
  
! 	  /* We had found a conflict before, this means that DEREF may
! 	     alias variables that are in different alias sets.  If this
! 	     happens, we need to aggregate the two alias sets into a new
! 	     one with DEREF as its tag.
! 
! 	     Replace the tag for the previous entry with DEREF and remove
! 	     the current entry by swapping it with the last element in the
! 	     ALIAS_SETS array.  */
! 	  prev = (struct alias_set_d *) VARRAY_GENERIC_PTR (alias_sets,
! 							    last_found);
  
! 	  /* We only need to update the previous tag once.  */
! 	  if (prev->tag != deref)
  	    {
! 	      prev->tag = deref;
! 	      prev->tag_sym = deref_sym;
! 	      prev->tag_set = deref_set;
! 	      prev->tag_sym_set = deref_sym_set;
  	    }
  
! 	  /* Swap the current and the last element, and pop 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 DEREF aliased precisely one entry, then we may want to
!      record DEREF as the alias set leader rather than the existing
!      entry.  For example, if *p conflicted with q, we want to
!      have *p be the alias leader.
! 
!      By doing this we can continue to not consider VAR_DECLs with the
!      same alias set as not aliasing each other in may_alias_p.  */
!   if (prev == NULL && last_found != -1)
!     {
!       prev
! 	= (struct alias_set_d *) VARRAY_GENERIC_PTR (alias_sets, last_found);
! 
!       /* If the existing entry was not an INDIRECT_REF and the current
!          object is an INDIRECT_REF, then replace the existing entry with
! 	 the current entry.  */
!       if (TREE_CODE (prev->tag) != INDIRECT_REF
! 	  && TREE_CODE (deref) == INDIRECT_REF)
! 	{
! 	  prev->tag = deref;
! 	  prev->tag_sym = deref_sym;
! 	  prev->tag_set = deref_set;
! 	  prev->tag_sym_set = deref_sym_set;
! 	}
      }
  
!   /* If we didn't find an existing set that conflicts with SET.  Add it.  */
!   if (last_found == -1)
      {
        curr = xmalloc (sizeof (*curr));
        curr->tag = deref;
        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);
      }
--- 1815,1903 ----
       tree deref_sym;
  {
    size_t i, num_sets;
!   struct alias_set_d *curr;
!   HOST_WIDE_INT deref_set;
!   int replaced, found;
  
    deref_set = get_alias_set (deref);
  
+   /* Search the alias_sets list for entries which match DEREF_SET.
+ 
+      If we find a matching entry that is an INDIRECT_REF, then stop
+      the loop as the existing entry carries all the required aliases.
+ 
+      Else if we find a matching entry and DEREF is an INDIRECT_REF,
+      then replace the existing entry with DEREF and remove all other
+      matching entries.
+ 
+      Else add DEREF to the list and quit.  */
    /* FIXME: ALIAS_SETS will usually be small (<< 10 entries).  If it becomes
       a performance problem, try with a splay tree.  */
!   replaced = 0;
!   found = 0;
    for (i = 0; i < VARRAY_ACTIVE_SIZE (alias_sets); i++)
      {
        curr = (struct alias_set_d *) VARRAY_GENERIC_PTR (alias_sets, i);
  
!       /* See if we have any entries with the same alias set.  */
!       if (curr->tag_set == deref_set)
!         {
! 	  found = 1;
  
! 	  /* We found an INDIRECT_REF in ALIAS_SETS, it carries all
! 	     our aliases.  */
! 	  if (curr->tag != curr->tag_sym)
! 	    break;
  
! 	  /* We have a VAR_DECL and we found a VAR_DECL in ALIAS_SETS.
! 	     Just add a new entry entry to the list and quit.  */
! 	  if (deref == deref_sym)
  	    {
! 	      curr = xmalloc (sizeof (*curr));
! 	      curr->tag = deref;
! 	      curr->tag_set = deref_set;
! 	      curr->tag_sym = deref_sym;
! 	      curr->num_elements = 0;
! 	      VARRAY_PUSH_GENERIC_PTR (alias_sets, (void *) curr);
! 	      break;
  	    }
  
! 	  /* We have an INDIRECT_REF and ALIAS_SETS contains VAR_DECLs.
! 	     We need to replace the first entry with our INDIRECT_REF
! 	     and delete the VAR_DECLs.  */
! 	  if (replaced == 0)
  	    {
! 	      curr->tag = deref;
! 	      curr->tag_sym = deref_sym;
! 	      curr->tag_set = deref_set;
! 	      replaced = 1;
! 	    }
! 	  else
! 	    {
! 	      /* Swap the current and the last element, and pop the array. 
! 	         Don't forget to free the element we are deleting!  */
! 	      curr = VARRAY_GENERIC_PTR (alias_sets, i);
! 	      free (curr);
! 	      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--;
! 		}
! 	      VARRAY_POP (alias_sets);
  	    }
!         }
      }
  
!   /* If we did not find an entry in ALIAS_SETS with a matching
!      alias set, create a new entry.  */
!   if (! found)
      {
        curr = xmalloc (sizeof (*curr));
        curr->tag = deref;
        curr->tag_set = deref_set;
        curr->tag_sym = deref_sym;
        curr->num_elements = 0;
        VARRAY_PUSH_GENERIC_PTR (alias_sets, (void *) curr);
      }









Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]