public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug tree-optimization/41118] New: Wrong dependence analysis in graphite for unrestricted pointers
@ 2009-08-19 12:07 amonakov at gcc dot gnu dot org
2009-08-19 16:02 ` [Bug tree-optimization/41118] " spop at gcc dot gnu dot org
` (3 more replies)
0 siblings, 4 replies; 5+ messages in thread
From: amonakov at gcc dot gnu dot org @ 2009-08-19 12:07 UTC (permalink / raw)
To: gcc-bugs
Consider this example:
cat > pr41118.c <<EOF
void foo(int n, int *a, int *b)
{
int i;
for (i = 0; i < n; i++)
a[i] = b[i];
}
EOF
gcc -S -O2 pr41118.c -floop-parallelize-all -ftree-parallelize-loops=2
grep GOMP 41118.s
GCC considers the loop parallel, even though arrays pointed to by arguments may
arbitrarily overlap. This is because dependency analysis in graphite treats
p[i] as global_mem[alias_set_for_p][i]. In this example, since both a and b
have
alias set 0, a[0][i0] and b[0][i1] are considered independent for i0 != i1.
--
Summary: Wrong dependence analysis in graphite for unrestricted
pointers
Product: gcc
Version: 4.5.0
Status: UNCONFIRMED
Keywords: wrong-code
Severity: normal
Priority: P3
Component: tree-optimization
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: amonakov at gcc dot gnu dot org
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41118
^ permalink raw reply [flat|nested] 5+ messages in thread
* [Bug tree-optimization/41118] Wrong dependence analysis in graphite for unrestricted pointers
2009-08-19 12:07 [Bug tree-optimization/41118] New: Wrong dependence analysis in graphite for unrestricted pointers amonakov at gcc dot gnu dot org
@ 2009-08-19 16:02 ` spop at gcc dot gnu dot org
2009-08-19 16:27 ` amonakov at gcc dot gnu dot org
` (2 subsequent siblings)
3 siblings, 0 replies; 5+ messages in thread
From: spop at gcc dot gnu dot org @ 2009-08-19 16:02 UTC (permalink / raw)
To: gcc-bugs
------- Comment #1 from spop at gcc dot gnu dot org 2009-08-19 16:02 -------
> since both a and b have alias set 0,
> a[0][i0] and b[0][i1] are considered independent for i0 != i1.
You mean mem[0][i0] and mem[0][i1], and in your example
for (i = 0; i < n; i++)
mem[0][i] = mem[0][i];
that would be a read and a write in the same location: that means
that there is no dependence carried by the loop, and thus the loop
is considered parallel. Yes this is a bug in the data dependence
analysis.
I wonder why the alias analysis improvements by Li do not assign
different alias sets for "a" and "b" in this case. I will have to try
to reproduce this bug first.
Sebastian
--
spop at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
AssignedTo|unassigned at gcc dot gnu |spop at gcc dot gnu dot org
|dot org |
Status|UNCONFIRMED |ASSIGNED
Ever Confirmed|0 |1
Last reconfirmed|0000-00-00 00:00:00 |2009-08-19 16:02:20
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41118
^ permalink raw reply [flat|nested] 5+ messages in thread
* [Bug tree-optimization/41118] Wrong dependence analysis in graphite for unrestricted pointers
2009-08-19 12:07 [Bug tree-optimization/41118] New: Wrong dependence analysis in graphite for unrestricted pointers amonakov at gcc dot gnu dot org
2009-08-19 16:02 ` [Bug tree-optimization/41118] " spop at gcc dot gnu dot org
@ 2009-08-19 16:27 ` amonakov at gcc dot gnu dot org
2009-09-20 10:47 ` lifeng at gcc dot gnu dot org
2009-11-25 4:49 ` spop at gcc dot gnu dot org
3 siblings, 0 replies; 5+ messages in thread
From: amonakov at gcc dot gnu dot org @ 2009-08-19 16:27 UTC (permalink / raw)
To: gcc-bugs
------- Comment #2 from amonakov at gcc dot gnu dot org 2009-08-19 16:26 -------
(In reply to comment #1)
> I wonder why the alias analysis improvements by Li do not assign
> different alias sets for "a" and "b" in this case. I will have to try
> to reproduce this bug first.
Assigning different alias sets would mean that a[i] and b[j] do not alias for
all i and j, which is not desirable either.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41118
^ permalink raw reply [flat|nested] 5+ messages in thread
* [Bug tree-optimization/41118] Wrong dependence analysis in graphite for unrestricted pointers
2009-08-19 12:07 [Bug tree-optimization/41118] New: Wrong dependence analysis in graphite for unrestricted pointers amonakov at gcc dot gnu dot org
2009-08-19 16:02 ` [Bug tree-optimization/41118] " spop at gcc dot gnu dot org
2009-08-19 16:27 ` amonakov at gcc dot gnu dot org
@ 2009-09-20 10:47 ` lifeng at gcc dot gnu dot org
2009-11-25 4:49 ` spop at gcc dot gnu dot org
3 siblings, 0 replies; 5+ messages in thread
From: lifeng at gcc dot gnu dot org @ 2009-09-20 10:47 UTC (permalink / raw)
To: gcc-bugs
------- Comment #3 from lifeng at gcc dot gnu dot org 2009-09-20 10:47 -------
We should check if 2 data reference are with the same base object before
checking dependency.
This bug has been fix. Now has committed to Graphite branch.
http://gcc.gnu.org/viewcvs?view=revision&revision=151801
* graphite-dependences.c (poly_drs_may_alias_p): Adjust definition.
(pddr_original_scattering): Make sure 2 pdr2 in the same base object
set.
(graphite_carried_dependence_level_k): Ditto.
* graphite-poly.c (new_poly_dr): Add init of PDR_BASE_OBJECT_SET.
* graphite-poly.h (struct poly_dr): Add member dr_base_object_set.
(new_poly_dr): Adjust declaration.
* graphite-sese-to-poly.c (free_data_refs_aux): New.
(free_gimple_bb): Added free_data_refs_aux.
(build_poly_dr): Add dr_base_object_set.
(partition_drs_to_sets): New.
(dr_same_base_object_p): New.
(build_alias_set_for_drs): New.
(build_base_object_set_for_drs): New.
(build_scop_drs): Add build_base_obj_set_for_drs.
* graphite-sese-to-poly.h: Added #define for alias set number index
and base object set index.
* libgomp/testsuite/libgomp.graphite/force-parallel-6.c: Refine
tests.
* libgomp/testsuite/libgomp.graphite/pr4118.c: New.
--
lifeng at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |lifeng at gcc dot gnu dot
| |org
Status|ASSIGNED |RESOLVED
Resolution| |FIXED
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41118
^ permalink raw reply [flat|nested] 5+ messages in thread
* [Bug tree-optimization/41118] Wrong dependence analysis in graphite for unrestricted pointers
2009-08-19 12:07 [Bug tree-optimization/41118] New: Wrong dependence analysis in graphite for unrestricted pointers amonakov at gcc dot gnu dot org
` (2 preceding siblings ...)
2009-09-20 10:47 ` lifeng at gcc dot gnu dot org
@ 2009-11-25 4:49 ` spop at gcc dot gnu dot org
3 siblings, 0 replies; 5+ messages in thread
From: spop at gcc dot gnu dot org @ 2009-11-25 4:49 UTC (permalink / raw)
To: gcc-bugs
------- Comment #4 from spop at gcc dot gnu dot org 2009-11-25 04:49 -------
Subject: Bug 41118
Author: spop
Date: Wed Nov 25 04:48:51 2009
New Revision: 154549
URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=154549
Log:
2009-09-17 Li Feng <nemokingdom@gmail.com>
PR middle-end/41118
* graphite-dependences.c (poly_drs_may_alias_p): Adjust definition.
(pddr_original_scattering): Make sure 2 pdr2 in the same base object
set.
(graphite_carried_dependence_level_k): Ditto.
* graphite-poly.c (new_poly_dr): Add init of PDR_BASE_OBJECT_SET.
* graphite-poly.h (struct poly_dr): Add member dr_base_object_set.
(new_poly_dr): Adjust declaration.
* graphite-sese-to-poly.c (free_data_refs_aux): New.
(free_gimple_bb): Added free_data_refs_aux.
(build_poly_dr): Add dr_base_object_set.
(partition_drs_to_sets): New.
(dr_same_base_object_p): New.
(build_alias_set_for_drs): New.
(build_base_object_set_for_drs): New.
(build_scop_drs): Add build_base_obj_set_for_drs.
* graphite-sese-to-poly.h: Added #define for alias set number index and
base object set index.
* libgomp/testsuite/libgomp.graphite/force-parallel-6.c: Refine tests.
* libgomp/testsuite/libgomp.graphite/pr4118.c: New.
Modified:
trunk/gcc/ChangeLog.graphite
trunk/gcc/graphite-dependences.c
trunk/gcc/graphite-poly.c
trunk/gcc/graphite-poly.h
trunk/gcc/graphite-sese-to-poly.c
trunk/gcc/graphite-sese-to-poly.h
trunk/libgomp/testsuite/libgomp.graphite/force-parallel-6.c
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41118
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2009-11-25 4:49 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2009-08-19 12:07 [Bug tree-optimization/41118] New: Wrong dependence analysis in graphite for unrestricted pointers amonakov at gcc dot gnu dot org
2009-08-19 16:02 ` [Bug tree-optimization/41118] " spop at gcc dot gnu dot org
2009-08-19 16:27 ` amonakov at gcc dot gnu dot org
2009-09-20 10:47 ` lifeng at gcc dot gnu dot org
2009-11-25 4:49 ` spop at gcc dot gnu dot 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).