public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug rtl-optimization/56965] New: nonoverlapping_component_refs_p is bogus
@ 2013-04-15 12:46 rguenth at gcc dot gnu.org
2014-02-11 14:17 ` [Bug rtl-optimization/56965] " rguenth at gcc dot gnu.org
` (7 more replies)
0 siblings, 8 replies; 9+ messages in thread
From: rguenth at gcc dot gnu.org @ 2013-04-15 12:46 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus
2013-04-15 12:46 [Bug rtl-optimization/56965] New: nonoverlapping_component_refs_p is bogus rguenth at gcc dot gnu.org
@ 2014-02-11 14:17 ` rguenth at gcc dot gnu.org
2014-02-11 14:29 ` rguenth at gcc dot gnu.org
` (6 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: rguenth at gcc dot gnu.org @ 2014-02-11 14:17 UTC (permalink / raw)
To: gcc-bugs
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;
}
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus
2013-04-15 12:46 [Bug rtl-optimization/56965] New: nonoverlapping_component_refs_p is bogus rguenth at gcc dot gnu.org
2014-02-11 14:17 ` [Bug rtl-optimization/56965] " rguenth at gcc dot gnu.org
@ 2014-02-11 14:29 ` rguenth at gcc dot gnu.org
2014-02-11 14:41 ` ebotcazou at gcc dot gnu.org
` (5 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: rguenth at gcc dot gnu.org @ 2014-02-11 14:29 UTC (permalink / raw)
To: gcc-bugs
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).
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus
2013-04-15 12:46 [Bug rtl-optimization/56965] New: nonoverlapping_component_refs_p is bogus rguenth at gcc dot gnu.org
2014-02-11 14:17 ` [Bug rtl-optimization/56965] " rguenth at gcc dot gnu.org
2014-02-11 14:29 ` rguenth at gcc dot gnu.org
@ 2014-02-11 14:41 ` ebotcazou at gcc dot gnu.org
2014-02-11 14:59 ` rguenth at gcc dot gnu.org
` (4 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: ebotcazou at gcc dot gnu.org @ 2014-02-11 14:41 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus
2013-04-15 12:46 [Bug rtl-optimization/56965] New: nonoverlapping_component_refs_p is bogus rguenth at gcc dot gnu.org
` (2 preceding siblings ...)
2014-02-11 14:41 ` ebotcazou at gcc dot gnu.org
@ 2014-02-11 14:59 ` rguenth at gcc dot gnu.org
2014-02-11 15:59 ` [Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus and slow rguenth at gcc dot gnu.org
` (3 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: rguenth at gcc dot gnu.org @ 2014-02-11 14:59 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus and slow
2013-04-15 12:46 [Bug rtl-optimization/56965] New: nonoverlapping_component_refs_p is bogus rguenth at gcc dot gnu.org
` (3 preceding siblings ...)
2014-02-11 14:59 ` rguenth at gcc dot gnu.org
@ 2014-02-11 15:59 ` rguenth at gcc dot gnu.org
2014-02-12 16:02 ` rguenth at gcc dot gnu.org
` (2 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: rguenth at gcc dot gnu.org @ 2014-02-11 15:59 UTC (permalink / raw)
To: gcc-bugs
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).
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus and slow
2013-04-15 12:46 [Bug rtl-optimization/56965] New: nonoverlapping_component_refs_p is bogus rguenth at gcc dot gnu.org
` (4 preceding siblings ...)
2014-02-11 15:59 ` [Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus and slow rguenth at gcc dot gnu.org
@ 2014-02-12 16:02 ` rguenth at gcc dot gnu.org
2014-04-15 16:04 ` rguenth at gcc dot gnu.org
2014-04-15 16:04 ` rguenth at gcc dot gnu.org
7 siblings, 0 replies; 9+ messages in thread
From: rguenth at gcc dot gnu.org @ 2014-02-12 16:02 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus and slow
2013-04-15 12:46 [Bug rtl-optimization/56965] New: nonoverlapping_component_refs_p is bogus rguenth at gcc dot gnu.org
` (5 preceding siblings ...)
2014-02-12 16:02 ` rguenth at gcc dot gnu.org
@ 2014-04-15 16:04 ` rguenth at gcc dot gnu.org
2014-04-15 16:04 ` rguenth at gcc dot gnu.org
7 siblings, 0 replies; 9+ messages in thread
From: rguenth at gcc dot gnu.org @ 2014-04-15 16:04 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus and slow
2013-04-15 12:46 [Bug rtl-optimization/56965] New: nonoverlapping_component_refs_p is bogus rguenth at gcc dot gnu.org
` (6 preceding siblings ...)
2014-04-15 16:04 ` rguenth at gcc dot gnu.org
@ 2014-04-15 16:04 ` rguenth at gcc dot gnu.org
7 siblings, 0 replies; 9+ messages in thread
From: rguenth at gcc dot gnu.org @ 2014-04-15 16:04 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2014-04-15 16:04 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-04-15 12:46 [Bug rtl-optimization/56965] New: nonoverlapping_component_refs_p is bogus rguenth at gcc dot gnu.org
2014-02-11 14:17 ` [Bug rtl-optimization/56965] " rguenth at gcc dot gnu.org
2014-02-11 14:29 ` rguenth at gcc dot gnu.org
2014-02-11 14:41 ` ebotcazou at gcc dot gnu.org
2014-02-11 14:59 ` rguenth at gcc dot gnu.org
2014-02-11 15:59 ` [Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus and slow rguenth at gcc dot gnu.org
2014-02-12 16:02 ` rguenth at gcc dot gnu.org
2014-04-15 16:04 ` rguenth at gcc dot gnu.org
2014-04-15 16:04 ` rguenth at gcc dot gnu.org
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).