[Bug tree-optimization/41118] New: Wrong dependence analysis in graphite for unrestricted pointers

[Bug tree-optimization/41118] New: Wrong dependence analysis in graphite for unrestricted pointers

[amonakov at gcc dot gnu dot org]

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

[Bug tree-optimization/41118] Wrong dependence analysis in graphite for unrestricted pointers

[spop at gcc dot gnu dot org]

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

[Bug tree-optimization/41118] Wrong dependence analysis in graphite for unrestricted pointers

[amonakov at gcc dot gnu dot org]

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

[Bug tree-optimization/41118] Wrong dependence analysis in graphite for unrestricted pointers

[lifeng at gcc dot gnu dot org]

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

[Bug tree-optimization/41118] Wrong dependence analysis in graphite for unrestricted pointers

[spop at gcc dot gnu dot org]

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