[Bug middle-end/23411] New: [data deps] Distance on outer loops for self output deps

[Bug middle-end/23411] New: [data deps] Distance on outer loops for self output deps

[sebastian dot pop at cri dot ensmp dot fr]

The most frequent case that shows up when bootstrapping autovect branch 
with BOOT_CFLAGS="-O2 -fcheck-data-deps" is the following:

Dist vectors from the first dependence analyzer:
   1    0 
Omega dist vectors are not the same:
   0    0 
Data dependence relation is:
(Data Dep: 
  access_fn_A: {0, +, 1}_3
  access_fn_B: {0, +, 1}_3

 (subscript 
  iterations_that_access_an_element_twice_in_A: 0
  last_conflict: scev_not_known;
  iterations_that_access_an_element_twice_in_B: 0
  last_conflict: scev_not_known;
  (Subscript distance: 0
  )
 )
  distance_vect:      0    0 
  direction_vect:     =    =
)

This is caused by a loop containing a data ref like the following:
loop_2
  loop_3
    A[{0, +, 1}_3] = ...
  endloop_3
endloop_2

For this pattern, tree-data-ref.c says the following:

  /* There is a distance of 1 on all the outer loops: 
     
     Example: there is a dependence of distance 1 on loop_1 for the array A.
     | loop_1
     |   A[5] = ...
     | endloop
  */

But now that Omega says that dist is (0, 0) I'm not sure anymore whether
this is the standard meaning of distance vectors.

Allen&Kennedy book states:
Definition 2.9. Suppose that there is a dependence from statement
S1 on iteration i of a loop nest and statement S2 on iteration j, then
the dependence distance vector d(i,j) is defined as a vector of
length n such that d(i,j) = j - i.

-- 
           Summary: [data deps] Distance on outer loops for self output deps
           Product: gcc
           Version: 4.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: sebastian dot pop at cri dot ensmp dot fr
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug middle-end/23411] [data deps] Distance on outer loops for self output deps

[sebastian dot pop at cri dot ensmp dot fr]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
OtherBugsDependingO|                            |23409
              nThis|                            |


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

[Bug middle-end/23411] [data deps] Distance on outer loops for self output deps

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-08-17 12:24 -------
Confirmed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-08-17 12:24:11
               date|                            |


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

[Bug middle-end/23411] [data deps] Distance on outer loops for self output deps

[sebastian dot pop at cri dot ensmp dot fr]

------- Additional Comments From sebastian dot pop at cri dot ensmp dot fr  2005-09-14 12:38 -------
Subject: Re:  [data deps] Distance on outer loops for self output deps

In this case neither implementation got the dependece right: there are
bugs in both implementations.  For the following nested loop:

loop_1
  loop_2
    A[5] = ...
  end_loop_2
end_loop_1

BAD would answer: (1, 1), that would mean that for getting the same
access we'd have to run loop_1 once *and* loop_2 once: this is false.

BOP would answer: (0, 0), that would mean that neither loop_1 nor
loop_2 carry dependences, in other words, both loops are parallel:
this is false.

The right answer is a set of distance vectors: (0, 1) and (1, 0).  For
getting to the same element in the array we have to run loop_1 once
*or* loop_2 has to run once.



-- 


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

[Bug middle-end/23411] [data deps] Distance on outer loops for self output deps

[sebastian dot pop at cri dot ensmp dot fr]

------- Comment #3 from sebastian dot pop at cri dot ensmp dot fr  2006-03-29 20:39 -------
Fixed by the recent changes.


-- 

sebastian dot pop at cri dot ensmp dot fr changed:

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


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