[PATCH] Fix PR56965, move nonoverlapping_component_refs_p
Richard Biener
rguenther@suse.de
Tue Apr 15 12:19:00 GMT 2014
This moves nonoverlapping_component_refs_p (now that I committed the
patch to make it O (n log n) instead of O (n^3)) to the tree
alias oracle (which is dispatched to from the RTL oracle). This
fixes the wrong-code part of the bug by moving the call to
nonoverlapping_component_refs_p at a place where we verified that
we are not presented with weird may_alias or type-punned
(via VIEW_CONVERT_EXPR) accesses.
I didn't yet relax some of its restrictions (we can safely
skip real/imag-part and array[-range?]-refs - we don't have
to stop at them. There is also the question whether
aliasing_component_refs_p still does sth useful after this
(if those restrictions are removed).
Bootstrap / regtest pending on x86_64-unknown-linux-gnu.
Eric, does this look reasonable?
Thanks,
Richard.
2014-04-15 Richard Biener <rguenther@suse.de>
PR rtl-optimization/56965
* alias.c (ncr_compar, nonoverlapping_component_refs_p): Move ...
* tree-ssa-alias.c (ncr_compar, nonoverlapping_component_refs_p):
... here.
* alias.c (true_dependence_1): Do not call
nonoverlapping_component_refs_p.
* tree-ssa-alias.c (indirect_ref_may_alias_decl_p): Call
nonoverlapping_component_refs_p.
(indirect_refs_may_alias_p): Likewise.
* gcc.dg/torture/pr56965-1.c: New testcase.
* gcc.dg/torture/pr56965-2.c: Likewise.
Index: gcc/alias.c
===================================================================
*** gcc/alias.c (revision 209415)
--- gcc/alias.c (working copy)
*************** read_dependence (const_rtx mem, const_rt
*** 2248,2373 ****
return false;
}
- /* qsort compare function to sort FIELD_DECLs after their
- DECL_FIELD_CONTEXT TYPE_UID. */
-
- static inline int
- ncr_compar (const void *field1_, const void *field2_)
- {
- const_tree field1 = *(const_tree *) const_cast <void *>(field1_);
- const_tree field2 = *(const_tree *) const_cast <void *>(field2_);
- unsigned int uid1
- = TYPE_UID (TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (field1)));
- unsigned int uid2
- = TYPE_UID (TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (field2)));
- if (uid1 < uid2)
- return -1;
- else if (uid1 > uid2)
- return 1;
- return 0;
- }
-
- /* Return true if we can determine that the fields referenced cannot
- overlap for any pair of objects. */
-
- static bool
- nonoverlapping_component_refs_p (const_rtx rtlx, const_rtx rtly)
- {
- const_tree x = MEM_EXPR (rtlx), y = MEM_EXPR (rtly);
-
- if (!flag_strict_aliasing
- || !x || !y
- || TREE_CODE (x) != COMPONENT_REF
- || TREE_CODE (y) != COMPONENT_REF)
- return false;
-
- auto_vec<const_tree, 16> fieldsx;
- while (TREE_CODE (x) == COMPONENT_REF)
- {
- tree field = TREE_OPERAND (x, 1);
- tree type = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (field));
- if (TREE_CODE (type) == RECORD_TYPE)
- fieldsx.safe_push (field);
- x = TREE_OPERAND (x, 0);
- }
- if (fieldsx.length () == 0)
- return false;
- auto_vec<const_tree, 16> fieldsy;
- while (TREE_CODE (y) == COMPONENT_REF)
- {
- tree field = TREE_OPERAND (y, 1);
- tree type = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (field));
- if (TREE_CODE (type) == RECORD_TYPE)
- fieldsy.safe_push (TREE_OPERAND (y, 1));
- y = TREE_OPERAND (y, 0);
- }
- if (fieldsy.length () == 0)
- return false;
-
- /* Most common case first. */
- if (fieldsx.length () == 1
- && fieldsy.length () == 1)
- return ((TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldsx[0]))
- == TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldsy[0])))
- && fieldsx[0] != fieldsy[0]
- && !(DECL_BIT_FIELD (fieldsx[0]) && DECL_BIT_FIELD (fieldsy[0])));
-
- if (fieldsx.length () == 2)
- {
- if (ncr_compar (&fieldsx[0], &fieldsx[1]) == 1)
- {
- const_tree tem = fieldsx[0];
- fieldsx[0] = fieldsx[1];
- fieldsx[1] = tem;
- }
- }
- else
- fieldsx.qsort (ncr_compar);
-
- if (fieldsy.length () == 2)
- {
- if (ncr_compar (&fieldsy[0], &fieldsy[1]) == 1)
- {
- const_tree tem = fieldsy[0];
- fieldsy[0] = fieldsy[1];
- fieldsy[1] = tem;
- }
- }
- else
- fieldsy.qsort (ncr_compar);
-
- unsigned i = 0, j = 0;
- do
- {
- const_tree fieldx = fieldsx[i];
- const_tree fieldy = fieldsy[j];
- tree typex = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldx));
- tree typey = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldy));
- if (typex == typey)
- {
- /* We're left with accessing different fields of a structure,
- no possible overlap, unless they are both bitfields. */
- if (fieldx != fieldy)
- return !(DECL_BIT_FIELD (fieldx) && DECL_BIT_FIELD (fieldy));
- }
- if (TYPE_UID (typex) < TYPE_UID (typey))
- {
- i++;
- if (i == fieldsx.length ())
- break;
- }
- else
- {
- j++;
- if (j == fieldsy.length ())
- break;
- }
- }
- while (1);
-
- return false;
- }
-
/* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
static tree
--- 2248,2253 ----
*************** true_dependence_1 (const_rtx mem, enum m
*** 2643,2651 ****
if (nonoverlapping_memrefs_p (mem, x, false))
return 0;
- if (nonoverlapping_component_refs_p (mem, x))
- return 0;
-
return rtx_refs_may_alias_p (x, mem, true);
}
--- 2523,2528 ----
Index: gcc/tree-ssa-alias.c
===================================================================
*** gcc/tree-ssa-alias.c (revision 209415)
--- gcc/tree-ssa-alias.c (working copy)
*************** may_overlap:
*** 858,863 ****
--- 858,982 ----
return false;
}
+ /* qsort compare function to sort FIELD_DECLs after their
+ DECL_FIELD_CONTEXT TYPE_UID. */
+
+ static inline int
+ ncr_compar (const void *field1_, const void *field2_)
+ {
+ const_tree field1 = *(const_tree *) const_cast <void *>(field1_);
+ const_tree field2 = *(const_tree *) const_cast <void *>(field2_);
+ unsigned int uid1
+ = TYPE_UID (TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (field1)));
+ unsigned int uid2
+ = TYPE_UID (TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (field2)));
+ if (uid1 < uid2)
+ return -1;
+ else if (uid1 > uid2)
+ return 1;
+ return 0;
+ }
+
+ /* Return true if we can determine that the fields referenced cannot
+ overlap for any pair of objects. */
+
+ static bool
+ nonoverlapping_component_refs_p (const_tree x, const_tree y)
+ {
+ if (!flag_strict_aliasing
+ || !x || !y
+ || TREE_CODE (x) != COMPONENT_REF
+ || TREE_CODE (y) != COMPONENT_REF)
+ return false;
+
+ auto_vec<const_tree, 16> fieldsx;
+ while (TREE_CODE (x) == COMPONENT_REF)
+ {
+ tree field = TREE_OPERAND (x, 1);
+ tree type = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (field));
+ if (TREE_CODE (type) == RECORD_TYPE)
+ fieldsx.safe_push (field);
+ x = TREE_OPERAND (x, 0);
+ }
+ if (fieldsx.length () == 0)
+ return false;
+ auto_vec<const_tree, 16> fieldsy;
+ while (TREE_CODE (y) == COMPONENT_REF)
+ {
+ tree field = TREE_OPERAND (y, 1);
+ tree type = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (field));
+ if (TREE_CODE (type) == RECORD_TYPE)
+ fieldsy.safe_push (TREE_OPERAND (y, 1));
+ y = TREE_OPERAND (y, 0);
+ }
+ if (fieldsy.length () == 0)
+ return false;
+
+ /* Most common case first. */
+ if (fieldsx.length () == 1
+ && fieldsy.length () == 1)
+ return ((TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldsx[0]))
+ == TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldsy[0])))
+ && fieldsx[0] != fieldsy[0]
+ && !(DECL_BIT_FIELD (fieldsx[0]) && DECL_BIT_FIELD (fieldsy[0])));
+
+ if (fieldsx.length () == 2)
+ {
+ if (ncr_compar (&fieldsx[0], &fieldsx[1]) == 1)
+ {
+ const_tree tem = fieldsx[0];
+ fieldsx[0] = fieldsx[1];
+ fieldsx[1] = tem;
+ }
+ }
+ else
+ fieldsx.qsort (ncr_compar);
+
+ if (fieldsy.length () == 2)
+ {
+ if (ncr_compar (&fieldsy[0], &fieldsy[1]) == 1)
+ {
+ const_tree tem = fieldsy[0];
+ fieldsy[0] = fieldsy[1];
+ fieldsy[1] = tem;
+ }
+ }
+ else
+ fieldsy.qsort (ncr_compar);
+
+ unsigned i = 0, j = 0;
+ do
+ {
+ const_tree fieldx = fieldsx[i];
+ const_tree fieldy = fieldsy[j];
+ tree typex = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldx));
+ tree typey = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldy));
+ if (typex == typey)
+ {
+ /* We're left with accessing different fields of a structure,
+ no possible overlap, unless they are both bitfields. */
+ if (fieldx != fieldy)
+ return !(DECL_BIT_FIELD (fieldx) && DECL_BIT_FIELD (fieldy));
+ }
+ if (TYPE_UID (typex) < TYPE_UID (typey))
+ {
+ i++;
+ if (i == fieldsx.length ())
+ break;
+ }
+ else
+ {
+ j++;
+ if (j == fieldsy.length ())
+ break;
+ }
+ }
+ while (1);
+
+ return false;
+ }
+
+
/* Return true if two memory references based on the variables BASE1
and BASE2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
[OFFSET2, OFFSET2 + MAX_SIZE2) may alias. REF1 and REF2
*************** indirect_ref_may_alias_decl_p (tree ref1
*** 1023,1028 ****
--- 1142,1151 ----
&& same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (dbase2)) == 1)
return ranges_overlap_p (doffset1, max_size1, doffset2, max_size2);
+ if (ref1 && ref2
+ && nonoverlapping_component_refs_p (ref1, ref2))
+ return false;
+
/* Do access-path based disambiguation. */
if (ref1 && ref2
&& (handled_component_p (ref1) || handled_component_p (ref2)))
*************** indirect_refs_may_alias_p (tree ref1 ATT
*** 1144,1154 ****
&& !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
return false;
/* Do access-path based disambiguation. */
if (ref1 && ref2
! && (handled_component_p (ref1) || handled_component_p (ref2))
! && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) == 1
! && same_type_for_tbaa (TREE_TYPE (base2), TREE_TYPE (ptrtype2)) == 1)
return aliasing_component_refs_p (ref1,
ref1_alias_set, base1_alias_set,
offset1, max_size1,
--- 1267,1284 ----
&& !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
return false;
+ /* If either reference is view-converted, give up now. */
+ if (same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) != 1
+ || same_type_for_tbaa (TREE_TYPE (base2), TREE_TYPE (ptrtype2)) != 1)
+ return true;
+
+ if (ref1 && ref2
+ && nonoverlapping_component_refs_p (ref1, ref2))
+ return false;
+
/* Do access-path based disambiguation. */
if (ref1 && ref2
! && (handled_component_p (ref1) || handled_component_p (ref2)))
return aliasing_component_refs_p (ref1,
ref1_alias_set, base1_alias_set,
offset1, max_size1,
Index: gcc/testsuite/gcc.dg/torture/pr56965-1.c
===================================================================
*** gcc/testsuite/gcc.dg/torture/pr56965-1.c (revision 0)
--- gcc/testsuite/gcc.dg/torture/pr56965-1.c (working copy)
***************
*** 0 ****
--- 1,32 ----
+ /* { dg-do run } */
+ /* { dg-options "-fschedule-insns" { target scheduling } } */
+
+ extern void abort (void);
+
+ struct S {
+ int i;
+ int j;
+ };
+
+ struct U {
+ struct S s;
+ } __attribute__((may_alias));
+
+ int __attribute__((noinline,noclone))
+ foo (struct U *p, struct U *q)
+ {
+ int i;
+ q->s.j = 1;
+ i = p->s.i;
+ return i;
+ }
+
+ int main()
+ {
+ int a[3];
+ int *p = a;
+ p[1] = 0;
+ if (foo ((struct U *)(p + 1), (struct U *)p) != 1)
+ abort ();
+ return 0;
+ }
Index: gcc/testsuite/gcc.dg/torture/pr56965-2.c
===================================================================
*** gcc/testsuite/gcc.dg/torture/pr56965-2.c (revision 0)
--- gcc/testsuite/gcc.dg/torture/pr56965-2.c (working copy)
***************
*** 0 ****
--- 1,34 ----
+ extern void abort (void);
+
+ struct S { int i; int j; };
+ struct X { struct S s; int k; };
+ struct Y { int k; struct S s; };
+ union U { struct X x; struct Y y; } __attribute__((may_alias));
+
+ int __attribute__((noinline))
+ foo (union U *p, union U *q)
+ {
+ p->x.s.j = 1;
+ q->y.s.i = 0;
+ return p->x.s.j;
+ }
+
+ struct R { int i; int j; } __attribute__((may_alias));
+
+ int __attribute__((noinline))
+ bar (struct R *p, struct R *q)
+ {
+ p->i = 1;
+ q->j = 0;
+ return p->i;
+ }
+
+ int main()
+ {
+ int a[3];
+ if (foo ((union U *)&a[0], (union U *)&a[0]) != 0)
+ abort ();
+ if (bar ((struct R *)&a[1], (struct R *)&a[0]) != 0)
+ abort ();
+ return 0;
+ }
More information about the Gcc-patches
mailing list