On 6/12/2013, at 4:25 am, Michael Matz <m...@suse.de> wrote: > Hi, > > On Thu, 5 Dec 2013, Maxim Kuvyrkov wrote: > >> Output dependency is the right type (write after write). Anti >> dependency is write after read, and true dependency is read after write. >> >> Dependency type plays a role for estimating costs and latencies between >> instructions (which affects performance), but using wrong or imprecise >> dependency type does not affect correctness. > > In the context of GCC and the middle ends memory model this statement is > not correct. For some dependency types we're using type based aliasing to > disambiguate, i.e ignore that dependency, which for others we don't. In > particular a read-after-write memory-access dependency can be ignored if > type info says they can't alias (because a program where both _would_ > access the same memory would be invalid according to our mem model), but > for write-after-read or write-after-write we cannot do that disambiguation > (because the last write overrides the dynamic type of the memory cell even > if it was incompatible with the one before).
Yes, this is correct for dependencies between memory locations in the general context of GCC. [Below clarifications are for Paolo's benefit and anyone else's who wants to find out how GCC scheduling works.] Scheduler dependency analysis is a user of the aforementioned alias analysis and it simply won't create a dependency between instructions if alias analysis tells it that it is OK to do so. In the context of scheduler, the dependencies (and their types) are between instructions, not individual registers or memory locations. The mere fact of two instructions having a dependency of any kind will make the scheduler produce correct code. The difference between two instructions having true vs anti vs output dependency will manifest itself in how close the 2nd instruction will be issued to the 1st one. Furthermore, when two instructions have dependencies on several items (e.g., both on register and on memory location), the resulting dependency type is set to the greater of dependency types of all dependent items: true-dependency having most weight, followed by anti-dependency, followed by output-dependency. Consider instructions [r1] = r2 r1 = [r2] The scheduler dependency analysis will find an anti-dependency on r1 and true-dependency on memory locations (assuming [r1] and [r2] may alias). The resulting dependency between instructions will be true-dependency and the instructions will be scheduled several cycles apart. However, one might argue that [r1] and [r2] are unlikely to alias and scheduling these instructions back-to-back (downgrading dependency type from true to anti) would produce better code on average. This is one of countless improvements that could be made to GCC scheduler. -- Maxim Kuvyrkov www.kugelworks.com
