From 8d3c076f3ddc11df418af3ac54d28a4a2d19ef3b Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Tue, 15 Apr 2014 16:04:11 +0000 Subject: [PATCH] re PR rtl-optimization/56965 (nonoverlapping_component_refs_p is bogus and slow) 2014-04-15 Richard Biener 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. From-SVN: r209423 --- gcc/ChangeLog | 12 ++ gcc/alias.c | 124 --------------------- gcc/testsuite/ChangeLog | 6 + gcc/testsuite/gcc.dg/torture/pr56965-1.c | 32 ++++++ gcc/testsuite/gcc.dg/torture/pr56965-2.c | 34 ++++++ gcc/tree-ssa-alias.c | 136 ++++++++++++++++++++++- 6 files changed, 217 insertions(+), 127 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/torture/pr56965-1.c create mode 100644 gcc/testsuite/gcc.dg/torture/pr56965-2.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 356a111503e2..de72b92c556e 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,15 @@ +2014-04-15 Richard Biener + + 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. + 2014-04-15 Teresa Johnson * cfg.c (dump_bb_info): Fix flags check. diff --git a/gcc/alias.c b/gcc/alias.c index 4b32fcb027b1..5f3740291934 100644 --- a/gcc/alias.c +++ b/gcc/alias.c @@ -157,7 +157,6 @@ static rtx find_base_value (rtx); static int mems_in_disjoint_alias_sets_p (const_rtx, const_rtx); static int insert_subset_children (splay_tree_node, void*); static alias_set_entry get_alias_set_entry (alias_set_type); -static bool nonoverlapping_component_refs_p (const_rtx, const_rtx); static tree decl_for_component_ref (tree); static int write_dependence_p (const_rtx, const_rtx, enum machine_mode, rtx, @@ -2248,126 +2247,6 @@ read_dependence (const_rtx mem, const_rtx x) 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 (field1_); - const_tree field2 = *(const_tree *) const_cast (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 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 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 @@ -2643,9 +2522,6 @@ true_dependence_1 (const_rtx mem, enum machine_mode mem_mode, rtx mem_addr, 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); } diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 6904ef6c2fb0..78c21b4e914d 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2014-04-15 Richard Biener + + PR rtl-optimization/56965 + * gcc.dg/torture/pr56965-1.c: New testcase. + * gcc.dg/torture/pr56965-2.c: Likewise. + 2014-04-15 Teresa Johnson * gcc.dg/tree-prof/update-loopch.c: Update expected output. diff --git a/gcc/testsuite/gcc.dg/torture/pr56965-1.c b/gcc/testsuite/gcc.dg/torture/pr56965-1.c new file mode 100644 index 000000000000..2512db3965dd --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/pr56965-1.c @@ -0,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; +} diff --git a/gcc/testsuite/gcc.dg/torture/pr56965-2.c b/gcc/testsuite/gcc.dg/torture/pr56965-2.c new file mode 100644 index 000000000000..04f55914e9c6 --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/pr56965-2.c @@ -0,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; +} diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c index e70627589cc6..2c57a17f53e6 100644 --- a/gcc/tree-ssa-alias.c +++ b/gcc/tree-ssa-alias.c @@ -858,6 +858,125 @@ may_overlap: 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 (field1_); + const_tree field2 = *(const_tree *) const_cast (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 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 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 @@ -1023,6 +1142,10 @@ indirect_ref_may_alias_decl_p (tree ref1 ATTRIBUTE_UNUSED, tree base1, && 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))) @@ -1144,11 +1267,18 @@ indirect_refs_may_alias_p (tree ref1 ATTRIBUTE_UNUSED, tree base1, && !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)) - && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) == 1 - && same_type_for_tbaa (TREE_TYPE (base2), TREE_TYPE (ptrtype2)) == 1) + && (handled_component_p (ref1) || handled_component_p (ref2))) return aliasing_component_refs_p (ref1, ref1_alias_set, base1_alias_set, offset1, max_size1, -- 2.47.2