Memory carried dependencies cannot be detected

[travisdowns]

Consider the following loop:

add [rdx], 1

I imagine OSACA will report it has having no loop carried dependencies. However, the actual iteration time of such a loop is 4-6 cycles, since there is a dependency through the memory location [rdx], which isn't detected by OSACA which only knows about register dependencies (I think).

Obviously, real world examples are more complicated, but the basic idea is the same: some subsequent iteration (not necessarily exactly the succeeding one, it could be later) may read a value from memory written by a the same or a previous iteration, forming a dependency.

[travisdowns]

I don't think this is an easy problem to solve within the confines of OSACA. Unlike register dependencies, memory deps are data dependent. Since you do static analysis of a loop w/o knowing the inputs, I think the best you can hope for is to prove that some loads must alias previous stores, but this isn't sufficient, you could have other store-load pairs that alias depending on the inputs, or sometimes alias, etc, e.g.:

mov [rdx], rax
mov rbx, [rcx]
add rcx, 8
add rdx, 8

Depending on the initial values of rdx and rcx, the load and store here may never alias, or they may alias within the same iteration (i.e., the load depends on the immediate preceding store in the same iteration) if rdx == rcx initially, or there may be aliasing only from some previous iterations, if rdx - rcx == some smallish positive integer.

So I don't think you can hope to solve this problem in general. Perhaps you could allow the user to annotate which loads are known to depend on which stores, which would allow much better analysis if the user understood the aliasing relationships.