[Bug rtl-optimization/56965] New: nonoverlapping_component_refs_p is bogus

[Bug rtl-optimization/56965] New: nonoverlapping_component_refs_p is bogus

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56965

             Bug #: 56965
           Summary: nonoverlapping_component_refs_p is bogus
    Classification: Unclassified
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Keywords: wrong-code
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: rguenth@gcc.gnu.org


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 *p = (int *)__builtin_alloca (sizeof (int) * 3);
  p[1] = 0;
  if (foo ((struct U *)(p + 1), (struct U *)p) != 1)
    __builtin_abort ();
  return 0;
}

fails on x86_64 with -O2 -fschedule-insns because scheduling exchanges
the store and the load.

[Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56965

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-02-11
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Another testcase, doesn't require scheduling:

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;
}

[Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56965

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ebotcazou at gcc dot gnu.org

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Besides that nonoverlapping_component_refs_p is O(3) in the size of the refs
involved.

It also seems to ignore inner VIEW_CONVERT_EXPRs which means that doing the
struct X vs. struct Y dance with a VIEW_CONVERT_EXPR exposes a similar issue
(insert suitable Ada testcase here).

In the end I'd like to get rid of nonoverlapping_component_refs_p by moving
it to the tree oracle (where there is a similar but less aggressive
aliasing_component_refs_p).

It appears to me that nonoverlapping_component_refs_p could avoid its O(3)
complexity by doing sth like

  ... search for innermost VIEW_CONVERT_EXPR and start at its base ...
  vec<pair<tree, tree>> comprefs1;
  while (handled_component_ref_p (ref))
    {
      if (TREE_CODE (ref) == COMPONENT_REF)
        comprefs.safe_push (pair (ref, TYPE_MAIN_VARIANT (TYPE_CONTEXT
(TREE_OPERAND (ref, 1)))));
      ref = TREE_OPERAND (ref, 0);
    }

same for the other ref.  Then sort the two vectors after the context type
(using TYPE_UID as key for example) and then comparing the two vectors
in lock-step.

 -> O (n * log (n))

(and we can skip over non-component-handled-components as in the code above).

[Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus

[ebotcazou at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56965

--- Comment #3 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
> In the end I'd like to get rid of nonoverlapping_component_refs_p by moving
> it to the tree oracle (where there is a similar but less aggressive
> aliasing_component_refs_p).

No fundamental disagreement here, I already sort of initiated the process by
adding nonoverlapping_component_refs_of_decl_p to tree-ssa-alias.c.

[Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56965

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 32105
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32105&action=edit
patch to make nonoverlapping_component_refs_p O (n log n)

Address O(3) complexity like the attached (otherwise should behave identically
other than search & find order).

The function is somewhat crippled since we no longer strip ARRAY_REFs from
mem-attrs MEM_EXPR, so testing coverage is probably low.  Still going to test
it,
despite the possibly non-trivial overhead for qsort of small N (N == 1 is
optimized already).  insn-recog.c on x86_64 is a big contender on this
function with -O2 --param max-gcse-memory=404857600

[Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus and slow

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56965

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #32105|0                           |1
        is obsolete|                            |

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 32106
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32106&action=edit
/suse/rguenther/p

Somewhat micro-optimized patch as otherwise it slows down the common cases too
much it seems (testing on insn-recog).  It's still slower than the non-sorting
version (but if we make it stronger by collecting more relevant FIELD_DECLs
we'll hit the trade-off limit faster ...).

Some statistics on insn-recog, fieldsx vs. fieldsy length:

184 rtl pre "ncr-1-1 == 1" 6192389
185 hoist "ncr-1-1 == 1" 252507
201 dse1 "ncr-1-1 == 1" 6743
227 dse2 "ncr-1-1 == 1" 6743
239 sched2 "ncr-1-1 == 1" 6743

which is interesting ;)  The most common case is just one.  Very easy to
very micro-optimize but still shows non-noise regression of about 1%
for the pathological case above.

We can also optimize the length 1 vs. arbitrary length case and avoid
sorting the 2nd vector (not done yet).

[Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus and slow

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56965

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Mine.

[Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus and slow

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56965

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Tue Apr 15 16:04:11 2014
New Revision: 209423

URL: http://gcc.gnu.org/viewcvs?rev=209423&root=gcc&view=rev
Log:
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.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr56965-1.c
    trunk/gcc/testsuite/gcc.dg/torture/pr56965-2.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/alias.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-alias.c

[Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus and slow

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56965

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED
   Target Milestone|---                         |4.10.0

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk.