------- Comment #20 from rakdver at gcc dot gnu dot org 2006-11-09 11:16
-------
> I am playing with some ideas how to fix this, unless I come up with
something
> soon, I will revert the patch (except for the testcase that I would like to
> remain in the testsuite).
The best I was able to do is the following patch. Virtual operand prunning
removes all the symbols that the SMTs have in common, which causes this PR.
The patch adds artificial "conflict" symbols to all pairs of aliasing SMTs, to
avoid this. Just looking at the dump of the testcase for this PR, it appears
quite expensive (there are a lot of new virtual operands); I will check what
the memory behavior is on larger testcases.
Index: tree-dump.c
===================================================================
*** tree-dump.c (revision 118619)
--- tree-dump.c (working copy)
*************** dequeue_and_dump (dump_info_p di)
*** 495,500 ****
--- 495,501 ----
case SYMBOL_MEMORY_TAG:
case NAME_MEMORY_TAG:
case STRUCT_FIELD_TAG:
+ case CONFLICT_TAG:
break;
case VAR_DECL:
Index: tree-pretty-print.c
===================================================================
*** tree-pretty-print.c (revision 118619)
--- tree-pretty-print.c (working copy)
*************** dump_generic_node (pretty_printer *buffe
*** 849,854 ****
--- 849,855 ----
break;
case SYMBOL_MEMORY_TAG:
+ case CONFLICT_TAG:
case NAME_MEMORY_TAG:
case STRUCT_FIELD_TAG:
case VAR_DECL:
Index: tree.c
===================================================================
*** tree.c (revision 118619)
--- tree.c (working copy)
*************** init_ttree (void)
*** 270,279 ****
--- 270,281 ----
tree_contains_struct[STRUCT_FIELD_TAG][TS_DECL_MINIMAL] = 1;
tree_contains_struct[NAME_MEMORY_TAG][TS_DECL_MINIMAL] = 1;
tree_contains_struct[SYMBOL_MEMORY_TAG][TS_DECL_MINIMAL] = 1;
+ tree_contains_struct[CONFLICT_TAG][TS_DECL_MINIMAL] = 1;
tree_contains_struct[STRUCT_FIELD_TAG][TS_MEMORY_TAG] = 1;
tree_contains_struct[NAME_MEMORY_TAG][TS_MEMORY_TAG] = 1;
tree_contains_struct[SYMBOL_MEMORY_TAG][TS_MEMORY_TAG] = 1;
+ tree_contains_struct[CONFLICT_TAG][TS_MEMORY_TAG] = 1;
tree_contains_struct[STRUCT_FIELD_TAG][TS_STRUCT_FIELD_TAG] = 1;
*************** tree_code_size (enum tree_code code)
*** 336,341 ****
--- 338,344 ----
return sizeof (struct tree_function_decl);
case NAME_MEMORY_TAG:
case SYMBOL_MEMORY_TAG:
+ case CONFLICT_TAG:
return sizeof (struct tree_memory_tag);
case STRUCT_FIELD_TAG:
return sizeof (struct tree_struct_field_tag);
*************** tree_node_structure (tree t)
*** 2119,2124 ****
--- 2122,2128 ----
case SYMBOL_MEMORY_TAG:
case NAME_MEMORY_TAG:
case STRUCT_FIELD_TAG:
+ case CONFLICT_TAG:
return TS_MEMORY_TAG;
default:
return TS_DECL_NON_COMMON;
Index: tree.h
===================================================================
*** tree.h (revision 118619)
--- tree.h (working copy)
*************** extern const enum tree_code_class tree_c
*** 106,112 ****
#define MTAG_P(CODE) \
(TREE_CODE (CODE) == STRUCT_FIELD_TAG \
|| TREE_CODE (CODE) == NAME_MEMORY_TAG \
! || TREE_CODE (CODE) == SYMBOL_MEMORY_TAG)
/* Nonzero if DECL represents a VAR_DECL or FUNCTION_DECL. */
--- 106,113 ----
#define MTAG_P(CODE) \
(TREE_CODE (CODE) == STRUCT_FIELD_TAG \
|| TREE_CODE (CODE) == NAME_MEMORY_TAG \
! || TREE_CODE (CODE) == SYMBOL_MEMORY_TAG \
! || TREE_CODE (CODE) == CONFLICT_TAG)
/* Nonzero if DECL represents a VAR_DECL or FUNCTION_DECL. */
Index: tree-ssa-alias.c
===================================================================
*** tree-ssa-alias.c (revision 118619)
--- tree-ssa-alias.c (working copy)
*************** init_alias_info (void)
*** 915,920 ****
--- 915,925 ----
|| TREE_CODE (var) == SYMBOL_MEMORY_TAG
|| !is_global_var (var))
clear_call_clobbered (var);
+
+ /* Mark all old conflict symbols for renaming, so that they go
+ away. */
+ if (TREE_CODE (var) == CONFLICT_TAG)
+ mark_sym_for_renaming (var);
}
/* Clear flow-sensitive points-to information from each SSA name. */
*************** compute_flow_sensitive_aliasing (struct
*** 1149,1154 ****
--- 1154,1265 ----
}
}
+ /* Element of the conflicts hashtable. */
+
+ typedef struct
+ {
+ hashval_t hash;
+ tree smt1, smt2;
+ } smt_pair;
+
+ typedef smt_pair *smt_pair_p;
+
+ /* Return true if the smt pairs are equal. */
+
+ static int
+ smt_pair_eq (const void *va, const void *vb)
+ {
+ const smt_pair_p a = (const smt_pair_p) va;
+ const smt_pair_p b = (const smt_pair_p) vb;
+ return (a->smt1 == b->smt1 && a->smt2 == b->smt2);
+ }
+
+ /* Hash for a smt pair. */
+
+ static unsigned int
+ smt_pair_hash (const void *item)
+ {
+ return ((const smt_pair_p) item)->hash;
+ }
+
+ /* Adds conflict between SMT1 and SMT2 to the CONFLICTS table. */
+
+ static void
+ add_conflict (htab_t conflicts, tree smt1, tree smt2)
+ {
+ unsigned key[2];
+ hashval_t hash;
+ void **slot;
+ smt_pair cmpelt;
+ smt_pair_p newelt;
+
+ if (DECL_UID (smt1) > DECL_UID (smt2))
+ {
+ tree tmp = smt1;
+ smt1 = smt2;
+ smt2 = tmp;
+ }
+
+ key[0] = DECL_UID (smt1);
+ key[1] = DECL_UID (smt2);
+ hash = iterative_hash (key, sizeof (key), 0);
+
+ cmpelt.hash = hash;
+ cmpelt.smt1 = smt1;
+ cmpelt.smt2 = smt2;
+
+ slot = htab_find_slot (conflicts, &cmpelt, INSERT);
+ if (*slot)
+ return;
+
+ newelt = XNEW (smt_pair);
+ *newelt = cmpelt;
+ *slot = newelt;
+ }
+
+ /* Create a new memory tag of type TYPE.
+ Does NOT push it into the current binding. */
+
+ static tree
+ create_tag_raw (enum tree_code code, tree type, const char *prefix)
+ {
+ tree tmp_var;
+ tree new_type;
+
+ /* Make the type of the variable writable. */
+ new_type = build_type_variant (type, 0, 0);
+ TYPE_ATTRIBUTES (new_type) = TYPE_ATTRIBUTES (type);
+
+ tmp_var = build_decl (code, create_tmp_var_name (prefix),
+ type);
+ /* Make the variable writable. */
+ TREE_READONLY (tmp_var) = 0;
+
+ /* It doesn't start out global. */
+ MTAG_GLOBAL (tmp_var) = 0;
+ TREE_STATIC (tmp_var) = 0;
+ TREE_USED (tmp_var) = 1;
+
+ return tmp_var;
+ }
+
+ /* Create a new conflict tag. */
+
+ static tree
+ create_conflict_tag (void)
+ {
+ var_ann_t ann;
+ tree tag = create_tag_raw (CONFLICT_TAG, void_type_node, "CONFLICT");
+
+ DECL_CONTEXT (tag) = current_function_decl;
+ TREE_ADDRESSABLE (tag) = 1;
+
+ ann = get_var_ann (tag);
+ ann->symbol_mem_tag = NULL_TREE;
+ add_referenced_var (tag);
+
+ return tag;
+ }
/* Compute type-based alias sets. Traverse all the pointers and
addressable variables found in setup_pointers_and_addressables.
*************** static void
*** 1163,1168 ****
--- 1274,1283 ----
compute_flow_insensitive_aliasing (struct alias_info *ai)
{
size_t i;
+ htab_t conflicts;
+ htab_iterator hi;
+ smt_pair_p conflict;
+ tree confsym;
/* Initialize counter for the total number of virtual operands that
aliasing will introduce. When AI->TOTAL_ALIAS_VOPS goes beyond the
*************** compute_flow_insensitive_aliasing (struc
*** 1254,1282 ****
/* Since this analysis is based exclusively on symbols, it fails to
handle cases where two pointers P and Q have different memory
tags with conflicting alias set numbers but no aliased symbols in
! common.
!
! For example, suppose that we have two memory tags SMT.1 and SMT.2
! such that
!
! may-aliases (SMT.1) = { a }
! may-aliases (SMT.2) = { b }
!
! and the alias set number of SMT.1 conflicts with that of SMT.2.
! Since they don't have symbols in common, loads and stores from
! SMT.1 and SMT.2 will seem independent of each other, which will
! lead to the optimizers making invalid transformations (see
! testsuite/gcc.c-torture/execute/pr15262-[12].c).
!
! To avoid this problem, we do a final traversal of AI->POINTERS
! looking for pairs of pointers that have no aliased symbols in
! common and yet have conflicting alias set numbers. */
for (i = 0; i < ai->num_pointers; i++)
{
size_t j;
struct alias_map_d *p_map1 = ai->pointers[i];
tree tag1 = var_ann (p_map1->var)->symbol_mem_tag;
- bitmap may_aliases1 = p_map1->may_aliases;
if (PTR_IS_REF_ALL (p_map1->var))
continue;
--- 1369,1387 ----
/* Since this analysis is based exclusively on symbols, it fails to
handle cases where two pointers P and Q have different memory
tags with conflicting alias set numbers but no aliased symbols in
! common. Given that we prune the sets of virtual operands based
! on the actual shape of the memory reference in tree-ssa-operands,
! we have no easy way how to verify that the sets of symbols will
! always intersect. To avoid problems, we insert artificial
! NONLOCAL_CONFLICT symbol in all pairs of SMTs that conflict.
! If there are too many such pairs, we insert just one NONLOCAL_CONFLICT
! symbol in each of them, which pessimizes results, but saves memory. */
! conflicts = htab_create (10, smt_pair_hash, smt_pair_eq, free);
for (i = 0; i < ai->num_pointers; i++)
{
size_t j;
struct alias_map_d *p_map1 = ai->pointers[i];
tree tag1 = var_ann (p_map1->var)->symbol_mem_tag;
if (PTR_IS_REF_ALL (p_map1->var))
continue;
*************** compute_flow_insensitive_aliasing (struc
*** 1285,1324 ****
{
struct alias_map_d *p_map2 = ai->pointers[j];
tree tag2 = var_ann (p_map2->var)->symbol_mem_tag;
- bitmap may_aliases2 = p_map2->may_aliases;
! if (PTR_IS_REF_ALL (p_map2->var))
continue;
! /* If the pointers may not point to each other, do nothing. */
! if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set, true))
! continue;
! /* The two pointers may alias each other. If they already have
! symbols in common, do nothing. */
! if (bitmap_intersect_p (may_aliases1, may_aliases2))
! continue;
! if (!bitmap_empty_p (may_aliases2))
! {
! unsigned int k;
! bitmap_iterator bi;
! /* Add all the aliases for TAG2 into TAG1's alias set.
! FIXME, update grouping heuristic counters. */
! EXECUTE_IF_SET_IN_BITMAP (may_aliases2, 0, k, bi)
! add_may_alias (tag1, referenced_var (k));
! bitmap_ior_into (may_aliases1, may_aliases2);
! }
! else
! {
! /* Since TAG2 does not have any aliases of its own, add
! TAG2 itself to the alias set of TAG1. */
! add_may_alias (tag1, tag2);
! bitmap_set_bit (may_aliases1, DECL_UID (tag2));
! }
}
}
if (dump_file)
fprintf (dump_file, "\n%s: Total number of aliased vops: %ld\n",
--- 1390,1434 ----
{
struct alias_map_d *p_map2 = ai->pointers[j];
tree tag2 = var_ann (p_map2->var)->symbol_mem_tag;
! if (PTR_IS_REF_ALL (p_map2->var) || tag1 == tag2)
continue;
! if (may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set, true))
! add_conflict (conflicts, tag1, tag2);
! }
! }
! if (htab_elements (conflicts) < (unsigned) MAX_ALIASED_VOPS)
! {
! FOR_EACH_HTAB_ELEMENT (conflicts, conflict, smt_pair_p, hi)
! {
! confsym = create_conflict_tag ();
! add_may_alias (conflict->smt1, confsym);
! add_may_alias (conflict->smt2, confsym);
! }
! }
! else
! {
! bitmap csmts = BITMAP_ALLOC (NULL);
! bitmap_iterator bi;
! unsigned uid;
! confsym = create_conflict_tag ();
! FOR_EACH_HTAB_ELEMENT (conflicts, conflict, smt_pair_p, hi)
! {
! bitmap_set_bit (csmts, DECL_UID (conflict->smt1));
! bitmap_set_bit (csmts, DECL_UID (conflict->smt2));
! }
!
! EXECUTE_IF_SET_IN_BITMAP (csmts, 0, uid, bi)
! {
! add_may_alias (referenced_var (uid), confsym);
}
+ BITMAP_FREE (csmts);
}
+ htab_delete (conflicts);
if (dump_file)
fprintf (dump_file, "\n%s: Total number of aliased vops: %ld\n",
*************** is_escape_site (tree stmt)
*** 2173,2204 ****
return NO_ESCAPE;
}
- /* Create a new memory tag of type TYPE.
- Does NOT push it into the current binding. */
-
- static tree
- create_tag_raw (enum tree_code code, tree type, const char *prefix)
- {
- tree tmp_var;
- tree new_type;
-
- /* Make the type of the variable writable. */
- new_type = build_type_variant (type, 0, 0);
- TYPE_ATTRIBUTES (new_type) = TYPE_ATTRIBUTES (type);
-
- tmp_var = build_decl (code, create_tmp_var_name (prefix),
- type);
- /* Make the variable writable. */
- TREE_READONLY (tmp_var) = 0;
-
- /* It doesn't start out global. */
- MTAG_GLOBAL (tmp_var) = 0;
- TREE_STATIC (tmp_var) = 0;
- TREE_USED (tmp_var) = 1;
-
- return tmp_var;
- }
-
/* Create a new memory tag of type TYPE. If IS_TYPE_TAG is true, the tag
is considered to represent all the pointers whose pointed-to types are
in the same alias set class. Otherwise, the tag represents a single
--- 2283,2288 ----
*************** create_memory_tag (tree type, bool is_ty
*** 2227,2233 ****
return tag;
}
-
/* Create a name memory tag to represent a specific SSA_NAME pointer P_i.
This is used if P_i has been found to point to a specific set of
variables or to a non-aliased memory location like the address returned
--- 2311,2316 ----
Index: tree.def
===================================================================
*** tree.def (revision 118619)
--- tree.def (working copy)
*************** DEFTREECODE (RESULT_DECL, "result_decl",
*** 359,364 ****
--- 359,365 ----
DEFTREECODE (STRUCT_FIELD_TAG, "struct_field_tag", tcc_declaration, 0)
DEFTREECODE (NAME_MEMORY_TAG, "name_memory_tag", tcc_declaration, 0)
DEFTREECODE (SYMBOL_MEMORY_TAG, "symbol_memory_tag", tcc_declaration, 0)
+ DEFTREECODE (CONFLICT_TAG, "conflict_tag", tcc_declaration, 0)
/* A namespace declaration. Namespaces appear in DECL_CONTEXT of other
_DECLs, providing a hierarchy of names. */
Index: tree-ssa-operands.c
===================================================================
*** tree-ssa-operands.c (revision 118619)
--- tree-ssa-operands.c (working copy)
*************** get_expr_operands (tree stmt, tree *expr
*** 1873,1878 ****
--- 1873,1879 ----
case STRUCT_FIELD_TAG:
case SYMBOL_MEMORY_TAG:
case NAME_MEMORY_TAG:
+ case CONFLICT_TAG:
add_stmt_operand (expr_p, s_ann, flags);
return;
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29680
