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.
> 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
(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.
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.
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