This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Aliasing fix and ADDR_EXPR fix
- From: law at redhat dot com
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 14 Apr 2003 11:50:50 -0600
- Subject: [tree-ssa] Aliasing fix and ADDR_EXPR fix
- Reply-to: law at redhat dot com
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);
}