[Bug fortran/32377] New: can't determine dependence (source/destination overlap)

[Bug fortran/32377] New: can't determine dependence (source/destination overlap)

[tprince at computer dot org]

gfortran -O2  -ftree-vectorize -ftree-vectorizer-verbose=2 -c -v s243.f
The first array assignment is vectorized.  The second, which involves overlap
between source and destination, should be no problem to vectorize as long as
the loop is not reversed.  Significant advantage should be gained by fusion.

Simplified from
http://www.netlib.org/benchmark/vectors


-- 
           Summary: can't determine dependence (source/destination overlap)
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: fortran
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: tprince at computer dot org
 GCC build triplet: x86_64-unknown-linux-gnu
  GCC host triplet: x86_64-unknown-linux-gnu
GCC target triplet: x86_64-unknown-linux-gnu


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

[Bug fortran/32377] can't determine dependence (source/destination overlap)

[tprince at computer dot org]

------- Comment #1 from tprince at computer dot org  2007-06-17 15:26 -------
Created an attachment (id=13722)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=13722&action=view)
source code test case


-- 


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

[Bug fortran/32377] can't determine dependence (source/destination overlap)

[tprince at computer dot org]

------- Comment #2 from tprince at computer dot org  2007-06-18 01:36 -------
Performance change due to complete vectorization is not significant on Core 2
Duo.  My apologies for submitting at normal priority.


-- 

tprince at computer dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |minor


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

[Bug tree-optimization/32377] can't determine dependence (source/destination overlap without more than size)

[pinskia at gcc dot gnu dot org]

------- Comment #3 from pinskia at gcc dot gnu dot org  2007-06-18 02:45 -------
t.f:10: note: not vectorized: possible dependence between data-refs
(*a_54(D))[S.13_17] and (*a_54(D))[D.1376_50]


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|minor                       |enhancement
             Status|UNCONFIRMED                 |NEW
          Component|fortran                     |tree-optimization
     Ever Confirmed|0                           |1
  GCC build triplet|x86_64-unknown-linux-gnu    |
   GCC host triplet|x86_64-unknown-linux-gnu    |
 GCC target triplet|x86_64-unknown-linux-gnu    |
           Keywords|                            |missed-optimization
   Last reconfirmed|0000-00-00 00:00:00         |2007-06-18 02:45:31
               date|                            |
            Summary|can't determine dependence  |can't determine dependence
                   |(source/destination overlap)|(source/destination overlap
                   |                            |without more than size)


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

[Bug tree-optimization/32377] can't determine dependence (source/destination overlap without more than size)

[dorit at gcc dot gnu dot org]

------- Comment #4 from dorit at gcc dot gnu dot org  2007-07-01 12:48 -------
Looks like the data-dependence analysis is doing it's job (it figures out that
the dependence distance is 1), but the vectorizer is still not willing to
vectorize. Need to look into this. 


-- 


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

[Bug tree-optimization/32377] can't determine dependence (source/destination overlap without more than size)

[irar at il dot ibm dot com]

------- Comment #5 from irar at il dot ibm dot com  2007-07-02 12:20 -------
(In reply to comment #4)
> Looks like the data-dependence analysis is doing it's job

I am not sure about that. I tried the following cases and got distance 1 (and
direction positive) in all of them for load and store to ia pair.

  for (i = 0; i < N; i++){
    ia[i+1] = ia[i] * 4;
  }

  for (i = 0; i < N; i++){
    ia[i] = ia[i+1] * 4;
  }

  for (i = 0; i < N; i++){
    ia[i+1] = 0;
    ic[i] = ia[i] * 4;
  }

  for (i = 0; i < N; i++){
    ia[i] = 0;
    ic[i] = ia[i+1] * 4;
  }

What am I missing?

Thanks,
Ira


-- 


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

[Bug tree-optimization/32377] can't determine dependence (source/destination overlap without more than size)

[spop at gcc dot gnu dot org]

------- Comment #6 from spop at gcc dot gnu dot org  2007-07-03 07:14 -------
(In reply to comment #5)
> I am not sure about that. I tried the following cases and got distance 1 (and
> direction positive) in all of them for load and store to ia pair.
> What am I missing?
> 
Distance vectors are lexicographically positive vectors, that is why you get
the 1
in all these cases.  If you want to know which one comes first, you have to
look
at the DR_IS_READ for both references in the dependence relation.


-- 


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

[Bug tree-optimization/32377] can't determine dependence (source/destination overlap without more than size)

[irar at il dot ibm dot com]

------- Comment #7 from irar at il dot ibm dot com  2007-07-03 12:57 -------
(In reply to comment #6)
> Distance vectors are lexicographically positive vectors, that is why you get
> the 1
> in all these cases.  If you want to know which one comes first, you have to
> look
> at the DR_IS_READ for both references in the dependence relation.

I am sorry, but I still don't understand.

For 
  for (i = 0; i < N; i++){
    ia[i+1] = ia[i] * 4;
  }
the ddr is {ld, st} and distance 1

and for
  for (i = 0; i < N; i++){
    ia[i] = ia[i+1] * 4;
  }
the ddr is also {ld, st} with distance 1.

How can we distinguish between these cases? 

Thanks,
Ira


-- 

irar at il dot ibm dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |irar at il dot ibm dot com


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

[Bug tree-optimization/32377] can't determine dependence (source/destination overlap without more than size)

[sebpop at gmail dot com]

------- Comment #8 from sebpop at gmail dot com  2007-07-03 13:57 -------
Subject: Re:  can't determine dependence (source/destination overlap without
more than size)

On 3 Jul 2007 12:57:33 -0000, irar at il dot ibm dot com
<gcc-bugzilla@gcc.gnu.org> wrote:
>   for (i = 0; i < N; i++){
>     ia[i+1] = ia[i] * 4;
>   }
> the ddr is {ld, st} and distance 1
>
> and for
>   for (i = 0; i < N; i++){
>     ia[i] = ia[i+1] * 4;
>   }
> the ddr is also {ld, st} with distance 1.
>
> How can we distinguish between these cases?
>

There is no way to distinguish between these two in the classical distance
vector representation, however I have seen that I only have that code in
the graphite branch:
          DDR_REVERSED_P (ddr) = true;
I'm setting this in the block of code that is tested for not being lexico
positive vectors:
      if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))

I can submit a patch for merging that part of code in trunk if you need
this flag to test if you are in one or the other case.  But again in the
classical distance representation this cannot be distinguished.

Sebastian


-- 


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

[Bug tree-optimization/32377] can't determine dependence (source/destination overlap without more than size)

[irar at il dot ibm dot com]

------- Comment #9 from irar at il dot ibm dot com  2007-07-03 16:43 -------
(In reply to comment #8)
> I can submit a patch for merging that part of code in trunk if you need
> this flag to test if you are in one or the other case.  

I guess we can't vectorize the loop in this PR without it, since we have to
distinguish between the cases in comment #7 (the first loop should not be
vectorized and the second one should).

Thanks,
Ira


-- 


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

[Bug tree-optimization/32377] can't determine dependence (source/destination overlap without more than size)

[sebpop at gmail dot com]

------- Comment #10 from sebpop at gmail dot com  2007-07-04 07:21 -------
Subject: Re:  can't determine dependence (source/destination overlap without
more than size)

> > I can submit a patch for merging that part of code in trunk if you need
> > this flag to test if you are in one or the other case.
>
> I guess we can't vectorize the loop in this PR without it, since we have to
> distinguish between the cases in comment #7 (the first loop should not be
> vectorized and the second one should).
>

I have committed the attached patch to trunk.

Sebastian


------- Comment #11 from sebpop at gmail dot com  2007-07-04 07:21 -------
Created an attachment (id=13841)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=13841&action=view)


-- 


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

[Bug tree-optimization/32377] can't determine dependence (source/destination overlap without more than size)

[irar at il dot ibm dot com]

------- Comment #12 from irar at il dot ibm dot com  2007-07-04 08:34 -------
(In reply to comment #10)
> I have committed the attached patch to trunk.
> Sebastian

Thanks a lot!
Ira


-- 


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

[Bug tree-optimization/32377] can't determine dependence (source/destination overlap without more than size)

[irar at il dot ibm dot com]

------- Comment #13 from irar at il dot ibm dot com  2007-07-08 10:00 -------
Hi Sebastian,

I was going to submit the attached patch, but now the analysis fails with
"affine-affine test failed: missing iteration counts" and distance vector is
not built (so the loop in this PR cannot be vectorized even with the addition
of DDR_REVERSED_P). This was caused by your patch to PR 32457
http://gcc.gnu.org/viewcvs?view=rev&revision=126305. Is there any way to
restore the previous behaviour for this case?

Thanks,
Ira


-- 


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

[Bug tree-optimization/32377] can't determine dependence (source/destination overlap without more than size)

[irar at il dot ibm dot com]

------- Comment #14 from irar at il dot ibm dot com  2007-07-08 10:01 -------
Created an attachment (id=13869)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=13869&action=view)
patch


-- 


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

[Bug tree-optimization/32377] can't determine dependence (source/destination overlap without more than size)

[sebpop at gmail dot com]

------- Comment #15 from sebpop at gmail dot com  2007-07-09 14:19 -------
Subject: Re:  can't determine dependence (source/destination overlap without
more than size)

> I was going to submit the attached patch, but now the analysis fails with
> "affine-affine test failed: missing iteration counts" and distance vector is
> not built (so the loop in this PR cannot be vectorized even with the addition
> of DDR_REVERSED_P). This was caused by your patch to PR 32457
> http://gcc.gnu.org/viewcvs?view=rev&revision=126305. Is there any way to
> restore the previous behaviour for this case?
>

I'll try to fix this.


-- 


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

[Bug tree-optimization/32377] can't determine dependence (source/destination overlap without more than size)

[sebpop at gmail dot com]

------- Comment #16 from sebpop at gmail dot com  2007-10-31 01:13 -------
Subject: Re:  can't determine dependence (source/destination overlap without
more than size)

Testing a fix.


------- Comment #17 from sebpop at gmail dot com  2007-10-31 01:13 -------
Created an attachment (id=14445)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14445&action=view)


-- 


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

[Bug tree-optimization/32377] can't determine dependence (source/destination overlap without more than size)

[spop at gcc dot gnu dot org]

------- Comment #18 from spop at gcc dot gnu dot org  2007-10-31 13:53 -------
Subject: Bug 32377

Author: spop
Date: Wed Oct 31 13:53:03 2007
New Revision: 129797

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=129797
Log:
2007-10-31  Sebastian Pop  <sebastian.pop@amd.com>

        PR tree-optimization/32377
        * tree-data-ref.c (compute_overlap_steps_for_affine_univar): Make it
        work also for unknown number of iterations.
        (analyze_subscript_affine_affine): Clean up.  Don't fail when the 
        number of iterations is not known.

        * gfortran.dg/vect/pr32377.f90: New.



Added:
    trunk/gcc/testsuite/gfortran.dg/vect/pr32377.f90
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-data-ref.c


-- 


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

[Bug tree-optimization/32377] can't determine dependence (source/destination overlap without more than size)

[spop at gcc dot gnu dot org]

------- Comment #19 from spop at gcc dot gnu dot org  2007-10-31 13:53 -------
Fixed.


-- 

spop at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED


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