Re: [0/4] Modulo scheduling with haifa-sched for C6X

[Richard Sandiford <richard dot sandiford at linaro dot org>]

Bernd Schmidt <bernds_cb1@t-online.de> writes:
> On 10/03/11 16:21, Richard Sandiford wrote:
>> so inter-iteration dependencies aren't a problem.  Whereas I thought your
>> modulo instruction did:
>> 
>>   A1
>>   B1  A2
>>   C1  B2  A3
>>   D1  C2  B3
>>       D2  C3
>>           D3
>> 
>> so if D1 writes to memory that A2 (but not A1) _might_ load, then the
>> loop doesn't behave the same way.
>
> But sched-deps will have found a dependence between D1 and A2 so the
> schedule won't look like this.

OK, bad example, sorry.  So the fundamental assumption is that
if you have a loop:

Loop 1:
  A
  B
  C
  D

that you can unroll 4 times and schedule as:

Loop 2:
  A
  B A
  C B A
  D C B A
    D C B
      D C
        D

then 2 iterations of that loop:

  A
  B A
  C B A
  D C B A
    D C B
      D C
        D
  A
  B A
  C B A
  D C B A
    D C B
      D C
        D

are necessarily equivalent to:

Loop 3:
  A
  B A
  C B A
  D C B A
  A D C B
  B A D C
  C B A D
  D C B A
    D C B
      D C
        D

Is that right?  So if D from iteration N*4 of loop 1 doesn't alias A
from iteration N*4+1 of loop 1 (meaning loop 2 is correct) then it
follows that the D from any iteration M doesn't alias A from M+1
(meaning loop 3 is correct?  I'm still not convinced that follows
for sufficiently clever alias analysis.

Reason for asking is that (AIUI) SMS used to use stronger memory
disambiguation, but had to pull back to something more conservative
for similar reasons.

Richard