<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=http://email.email.llvm.org/c/eJzNVsuS2jgU_RqzUZmyRfNasIBmuiqLmVkki9mlZFtuNJEljyRDk6-fc2UD7g6dpCqzGIoCS_d97tGVC1udN4_WeFVJx8JBeslm7HPdmTIoa4TWZyb_6dRRaGnCZ3YR-GS2TbJ9km2TRTZ85zstCqmT2f4lme976dGqitXWJnylTGAm4Y-ssl2hJUv4ljnpg1NlYNv3BLuEr1my3PXu2EinDS5nCAbb2X0xj-LdSFxbx4ZUVBTmEMbHR-SGx4Qj4E69CUofCocSFUqLluSf1mlOxV5CjC1uuYSmvdjko2wubm_-vpH1JcB-JEqWA7i3hxvWhXD_Gda_gNadNkFtQeU8sS1-t7Ev7F0b_sZmF222d4H-udb8ALiX89ev5_8BdKqOhig8j8JRndtxkbt7FTImNU7w2Gg3Ntr-JCzXMz1C6dE2rULdJxUOd05_v-QPrNTCPLP0zxmrxLRkqWxUSLU-Niz9a5BVygtAGHfTVngvPUs_shTalqy0vrmzbei3WFoIr8pUCJY2suFOwpMyPpS2KZSRLNXWtqlXTatVfR6WzgYRIKtgJTDPzl-xkCaGN_KUtg1wyb5T9qcD8FxkcIBfaninQ9_eRUaDDZvq3jSMy4-uJNqio_MsNkBbUQ0EulGJmAQN4Zw4q-qFBEKrZ8NW9JjwPBQoGv8PLE2T2W9s70N064N18sbHefauT_4dp9fZKdgVIWasgY_8blWngyoPqJqdnDXP5K6QpehAPMJFHqVhuC86NNXWBJMiSwq6yF4fzQioqDxdPL0JXKoQ4ECZuNk6eVS280wF6QTdPFP26SACYQ6PUAEAyESwWtsTq2QrTSVNKadvezh0DroIG6tD9EveW62E31LxHgpOhs4Zz_6wcX84zPM4yYSphucI6RWK0jonMQiGvL00cBtipsOOaOStCrJFDgQQhA1rLUYFcLDknDq3uno2VlAWNAwoOPmyVPegvHulLLS3IwsKo-QURpbSOUGG9jgW5a8g2l-Ru8IQyUBH84qqwkKUzvpRP_wlKydrYuNJ4ajiSLYCC5xT686wKWU85LWzDatUXUObRuPVyZR9mCLPC8qIjrcOoYca430Qbd_hxLiSD1BS5suganEWGnahSWzInVIb8QXZET6R0gwjqWvavrxoM8yYiumer4OiH2h1GwD59DWZEr68KjGCBDTHbTOg2B4UulVJ3xtzIrfEHY5mRUagVchOmaNwSpjIJbySMZps_gfds4aITq8D4LmXskE0NEE1ygdVxhe7gbM9F0m7vwOhT9hdGE0HK-FPCK9G56svppIBKrKaTqrNrFrP1mIiOpDNbX6XgMv5onOTzunNIYQ2gsSf8H3GFdIVU4CKBV0Cw1-Kfv0dM3pS6ABg4U_z2fqBTw6bTGa8WM2XCz6b1XUuxHxdy2Wd1_hf5Hk1iS-ffoPpknBedJhLvJ90nODCNaIa2prvJ7-ejtrwjOObrzP88PW0WOV5XZWZWD3UvJgvk4dMNkLpKfmZWvc8cZvoEol5CDW64G9C8A2jWcqYPTIMKui4-LaxdJVHeqIFr4kysASzbxLT3cRc_wU6-JWQ>53942</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [DependenceAnalysis] assumes base pointer invariance.
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            bug,
            loopoptim
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          Meinersbur
      </td>
    </tr>
</table>

<pre>
    Consider these 3 _functionally equivalent_ functions:
```[label=x]
void foo(int n, double * restrict A, double * restrict B) {
  double *ptr1 = A;
  double *ptr2 = B;
  for (int i = 1; i < n; ++i) {
      ptr1[i] = ptr2[i-1];

      double *tmp = ptr1;
      ptr1 = ptr2;
      ptr2 = tmp;
  }
}

void bar(int n, double * restrict A, double * restrict B) {
  for (int i = 1; i < n; ++i) {
      double *ptr1 = i&2 ? A : B; 
      double *ptr2 = i&2 ? B : A;

      ptr1[i] = ptr2[i-1];
  }
}

void xyzzy(int n, double * restrict A, double * restrict B) {
  for (int i = 1; i < n; ++i) {
     if (i&1) 
      A[i] = B[i-1];
    else 
      B[i] = A[i-1];
  }
}
```

Compile with:
```
$ clang -O3 da.c -emit-llvm -Xclang -disable-llvm-passes -S -c -o da.ll
$ opt da.ll -basic-aa -mem2reg -instcombine -loop-simplify -loop-rotate -da -analyze -enable-new-pm=0
```

The `-da` result for `foo` is:
```
Src:  %0 = load double, double* %arrayidx, align 8, !tbaa !4 --> Dst:  store double %0, double* %arrayidx2, align 8, !tbaa !4
  da analyze - none!
```
which is wrong, because for even values of `i`, `ptr2[i-1]` reads the value written in the previous iteration. That is, there is a flow dependence.

The result is `none` because AliasAnalysis returns NoAlias for %ptr1 and %ptr2, which is correct in the sense that in the same iteration, one of them points to %A (which is noalias) and the other to %B (which is also noalias), ie. those two never alias.

DependenceAnalysis analyses dependencies across iterations and therefore will compare memory accesses from different iterations. I.e. %ptr1 is equal to %ptr2 from the previous iteration.

I think the problem here is that DependenceAnalysis makes two wrong assumptions that combined leads to wrongs results:
1. AliasAnalysis's results are valid across phi nodes
2. The base pointer is invariant in all loops

DependenceAnalysis on `bar` seems pessimistically correct, on `xyzzy` the correct flow/anti dependences are detected.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzNVsuO2zYU_Rp5Q8iQ6PfCC3vcAbJou0gW3QWURI3ZUKRKUuNxvr7nUrKtmXiSAOmihmGLvA_ec-6DKmx13j5Y41UlHQtH6SWbsc91Z8qgrBFan5n8p1PPQksTPrOLwCezXZIdkmyXLLPhu9hrUUidzA4vyeLQS5-tqlhtbcLXygRmEv7AKtsVWrKE75iTPjhVBrZ7T7BP-IYlq33vjo102uByhsNgO7sv5lG8H4lr69gQiorCHML4-IDY8JhwHLhXbw6lDx0HiArQoiX5p3WaE9jLEWOLWyyhaS82-Siai9ubv29kPQTYj0TJaiD39nDjuhDuP-P6F9i6kyaoLQnOI9vhdxfzwt614W9s9tFmd5fon0vND4h7OX_9ev4fUKfqaAjgeRSOcO7GIPf3EDImNTp4bLQfG-1-kpZrT49YerBNq4D7pMLxTvf3Sz5npRbmiaV_zlglpiVLZaNCqvVzw9K_BlmlvACFcTdthffSs_QjS6FtyUrrmzvbhn6LpYXwqkyFYGkjG-4kPCnjQ2mbQhnJUm1tm3rVtFrV52HpbBABsgpWAvPs_BULaeLxRp7StgEv2XdgfzqCz2UGB_ilhHc69OldZjTYsKnuTcO4_OhKKltkdJHFBGgrqqGAbqVElQQN4Zw4q-qFBEKrJ8PW9JjwPBQAjf85S9Nk9hs7-BDd-mCdvNXjInvXJ_-O0-vsFOzKEDPWwEd-F9XpqMojULOTs-aJ3BWyFB0Kj3iRz9Iw3BcdkmprokmRJR26zF63ZiRUVJ4unt4ELlUIcKBM3GydfFa280wF6QTdPFP26SgCcQ6PUAEBiESwWtsTq2QrTSVNKadvczhkDro4NqLD6Ze4d1oJvyPwHgpOhs4Zz_6wcX9o5kWcZMJUw3Ok9EpFaZ2TGARD3F4auA0x0mFHNPKGgmwRAxEEYcNai1EBHiw5p8ytr56NFRQFDQM6nHxZwj0o718pC-3tyIKOUXIKI0vhnCBDehyL8lcUHa7MXWmIxUCteWVVYSFKZ_0oH_4SlZM1VeNJoVXRkq3AAn1q3Rk2pYxNXjvbsErVNbRpNF6dTNmHKeK8sIzT8dYh9IAx3gfR9p2aGCP5ACVlvgyqFr3QsEuZxITcgdqIL4iO-IklzTCSuqbt4UWbYcZUTPf1Oij6oaxuAyCfvi6mhK-uSowoQZnjthlYbI8K2aqk7405FbfEHY5kxYpAqhCdMs_CKWFiLeGVjNFk8z_InjVU6PQ6gDr3UjY4DUlQjfJBlfHFbqjZvhZJu78DoU_cXSqaGivhjzhejfqrB1PJABVZTSfVdlZtZhsxCSpouUWPfxsT3UKRWVi_xjgARNtOOqe3xxDaSCl_xPcJF05XTJECLOjKGP5SZPfvGP-jgleQyB8Xs82cT47b1WI-m5frTTXLy8VCrPLVsqpXm8VSZuu82GST-KrqKc6E86LDFOP9XORELi4d1dDW4jBRW55xfPNNhh--mRbrPK-rMhPrec2LxSqZZ7IRSk8pqKl1TxO3jfHBrYdQg3F_E4IBjGEZOSL_okN3uu3vEvXlfNG5SUSzjVD-BThQf2c">