[DependenceAnalysis] Missing dependency detection for instructions accessing same memory location on different iterations

[1997alireza]

Dependence analysis is capable of checking the dependency of an instruction with itself but there is a bug there; If the dependency occurs by an instruction through accessing the same memory location in different loop iterations, DA is not able to detect the dependency. For example, the expression A[i - j] where i = j = 0 and i = j = 1 accesses the same memory location at different iterations, but the current analysis fails to detect this dependency, which will lead to incorrect analysis in some optimization passes such as loop-interchange.
Consider the following code:

int main() {
    const int N = 21;
    int A[N] = {0};
    int *B = &A[10];

    for (int i = 1; i <= 10; i++)
        for (int j = 10; j >= 1; j--)
            B[i - j] = 2 * i - j;

    return 0;
}

This example can pass the legality check in loop interchange pass based on the information provided by DA, which would give incorrect results if loop interchange was performed. In the original code, the final value is stored in B[0] when i = j = 10, so B[0] is set to 10. After loop interchange, the last access to B[0] happens at i = j = 1, which incorrectly sets B[0] to 1.
The issue arises from an incorrect reasoning in the depends() API. There are two variables in the depends() API that are involved in this issue. First one is PossiblyLoopIndependent which will be set to false if the src and dst cannot have loop-independent dependency. Another variable is AllEqual that is computed within the API and is set to true if the dependency vector elements are all Equals.
For our case, when we analyse the dependency of the B[i-j] store instruction with itself, PossiblyLoopIndependent is set to false, and AllEqual is true. According to the API if AllEqual == True and PossiblyLoopIndependent == false, DA concludes there is no dependency, which is not correct and has caused the bug.

Additionally, by modifying a test case in DA, we can expose the same bug. In this test case, storing to A[11*i - j] has no dependency with itself. By modifying the subscript to A[10*i - j], the memory location A[0] is accessed in iterations i = j = 0 and i = 1, j = 10. Still, DA does not detect any dependency.

+ In addition to this bug, it seems that the PossiblyLoopIndependent variable has lost its intended purpose. This flag is always set to true in all cases when depends() is called, hence we may want to reconsider the utility of this variable and possibly remove it from the function signature entirely. We can post a patch for that.