<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/56275>56275</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [LoopInterchange] Wrong direction vector analysis in LoopInterchange?
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            loopoptim,
            llvm:optimizations,
            missed-optimization
      </td>
    </tr>

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

    <tr>
      <th>Reporter</th>
      <td>
          kawashima-fj
      </td>
    </tr>
</table>

<pre>
    I found a simple missed-optimization in LoopInterchange and tried to fix. However, I'm confused in the current implementation.

# Problem

The following loops can be interchanged theoretically because they only have a flow dependence with a direction vector `(<, =)` from (X) to (Y).

`fail1.ll`:

```llvm
target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
target triple = "aarch64-unknown-linux-gnu"

define dso_local void @foo(ptr noalias noundef %a, ptr noalias noundef %b, ptr noalias noundef %c) {
entry:
  br label %loop1.header

loop1.header:
  %i2 = phi i64 [ 1, %entry ], [ %i2.inc, %loop1.latch ]
  %i2.st = add i64 %i2, 1
  %i2.ld = add i64 %i2, 0
  br label %loop2.header

loop2.header:
  %i1 = phi i64 [ 1, %loop1.header ], [ %i1.inc, %loop2.header ]
  %i1.st = add i64 %i1, 0
  %i1.ld = add i64 %i1, 0
  %a.st = getelementptr inbounds [64 x i32], ptr %a, i64 %i1.st, i64 %i2.st
  %a.ld = getelementptr inbounds [64 x i32], ptr %a, i64 %i1.ld, i64 %i2.ld
  %b.ld = getelementptr inbounds [64 x i32], ptr %b, i64 %i1, i64 %i2
  %c.st = getelementptr inbounds [64 x i32], ptr %c, i64 %i1, i64 %i2
  %b.val = load i32, ptr %b.ld, align 4
  store i32 %b.val, ptr %a.st, align 4  ; (X) store to a[i1][i2+1]
  %a.val = load i32, ptr %a.ld, align 4 ; (Y) load from a[i1][i2]
  store i32 %a.val, ptr %c.st, align 4
  %i1.inc = add nuw nsw i64 %i1, 1
  %loop2.exitcond.not = icmp eq i64 %i1.inc, 63
  br i1 %loop2.exitcond.not, label %loop1.latch, label %loop2.header

loop1.latch:
  %i2.inc = add nuw nsw i64 %i2, 1
  %loop1.exitcond.not = icmp eq i64 %i2.inc, 63
  br i1 %loop1.exitcond.not, label %exit, label %loop1.header

exit:
  ret void
}
```

This IR corresponds to the following C program.

`fail1.c`:

```c
#define N1 64
#define N2 64

void foo(unsigned a[restrict N1][N2],
         unsigned b[restrict N1][N2],
         unsigned c[restrict N1][N2]) {
  for (unsigned long i2 = 1; i2 < N2-1; i2++) {
    for (unsigned long i1 = 1; i1 < N1-1; i1++) {
      a[i1][i2+1] = b[i1][i2];
      c[i1][i2] = a[i1][i2];
    }
  }
}
```

However, they aren't interchanged.

```
$ opt -S -passes=loop-interchange -cache-line-size=64 -debug-only=loop-interchange -o /dev/null fail1.ll
Processing LoopList of size = 2
Found 4 Loads and Stores to analyze
Found flow dependency between Src and Dst
 Src:  store i32 %b.val, ptr %a.st, align 4
 Dst:  %a.val = load i32, ptr %a.ld, align 4
Dependence before interchange
> = 
Processing InnerLoopId = 1 and OuterLoopId = 0
Failed interchange InnerLoopId = 1 and OuterLoopId = 0 due to dependence
Not interchanging loops. Cannot prove legality.
```

On the other hand, the following loops are successfully interchanged. The only difference from `fail1.ll` is the the order of (X) and (Y).

`pass1.ll`:

```llvm
target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
target triple = "aarch64-unknown-linux-gnu"

define dso_local void @foo(ptr noalias noundef %a, ptr noalias noundef %b, ptr noalias noundef %c) {
entry:
  br label %loop1.header

loop1.header:
  %i2 = phi i64 [ 1, %entry ], [ %i2.inc, %loop1.latch ]
  %i2.st = add i64 %i2, 1
  %i2.ld = add i64 %i2, 0
  br label %loop2.header

loop2.header:
  %i1 = phi i64 [ 1, %loop1.header ], [ %i1.inc, %loop2.header ]
  %i1.st = add i64 %i1, 0
  %i1.ld = add i64 %i1, 0
  %a.st = getelementptr inbounds [64 x i32], ptr %a, i64 %i1.st, i64 %i2.st
  %a.ld = getelementptr inbounds [64 x i32], ptr %a, i64 %i1.ld, i64 %i2.ld
  %b.ld = getelementptr inbounds [64 x i32], ptr %b, i64 %i1, i64 %i2
  %c.st = getelementptr inbounds [64 x i32], ptr %c, i64 %i1, i64 %i2
  %b.val = load i32, ptr %b.ld, align 4
  %a.val = load i32, ptr %a.ld, align 4 ; (Y) load from a[i1][i2]
  store i32 %b.val, ptr %a.st, align 4  ; (X) store to a[i1][i2+1]
  store i32 %a.val, ptr %c.st, align 4
  %i1.inc = add nuw nsw i64 %i1, 1
  %loop2.exitcond.not = icmp eq i64 %i1.inc, 63
  br i1 %loop2.exitcond.not, label %loop1.latch, label %loop2.header

loop1.latch:
  %i2.inc = add nuw nsw i64 %i2, 1
  %loop1.exitcond.not = icmp eq i64 %i2.inc, 63
  br i1 %loop1.exitcond.not, label %exit, label %loop1.header

exit:
  ret void
}
```

```
$ opt -S -passes=loop-interchange -cache-line-size=64 -debug-only=loop-interchange -o /dev/null pass1.ll
Processing LoopList of size = 2
Found 4 Loads and Stores to analyze
Found anti dependency between Src and Dst
 Src:  %a.val = load i32, ptr %a.ld, align 4
 Dst:  store i32 %b.val, ptr %a.st, align 4
Dependence before interchange
< = 
Processing InnerLoopId = 1 and OuterLoopId = 0
Checking if loops are tightly nested
Checking instructions in Loop header and Loop latch
Loops are perfectly nested
Loops are legal to interchange
InnerIndex = 0, OuterIndex = 1
Splitting the inner loop latch
splitting InnerLoopHeader done
adjustLoopBranches called
Loops interchanged.
Dependence after interchange
= < 
```

# Environment

Latest `main` branch (commit b941857b40)

(@CongzheUalberta's recent cost model commit is not relevant; the problem occurs both before the commit and after the commit)

# Analysis

The debug output for `fail1.ll` is:

```
$ opt -S -passes=loop-interchange -cache-line-size=64 -debug-only=loop-interchange -o /dev/null fail1.ll
Processing LoopList of size = 2
Found 4 Loads and Stores to analyze
Found flow dependency between Src and Dst
 Src:  store i32 %b.val, ptr %a.st, align 4
 Dst:  %a.val = load i32, ptr %a.ld, align 4
Dependence before interchange
> = 
(snip)
```

It's incorrect. The correct direction vector is `(<, =)`, not `(>, =)`

The interchange is rejected by [the `isOuterMostDepPositive` function](https://github.com/llvm/llvm-project/blob/b941857b40/llvm/lib/Transforms/Scalar/LoopInterchange.cpp#L191).

I think the cause is in [the `populateDependencyMatrix` function](https://github.com/llvm/llvm-project/blob/b941857b40/llvm/lib/Transforms/Scalar/LoopInterchange.cpp#L117).

```c++
  for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) {
    for (J = I, JE = MemInstr.end(); J != JE; ++J) {     // (C)
      std::vector<char> Dep;
      Instruction *Src = cast<Instruction>(*I);
      Instruction *Dst = cast<Instruction>(*J);
      // Ignore Input dependencies.
      if (isa<LoadInst>(Src) && isa<LoadInst>(Dst))
        continue;
      // Track Output, Flow, and Anti dependencies.
      if (auto D = DI->depends(Src, Dst, true)) {
        assert(D->isOrdered() && "Expected an output, flow or anti dep.");
        LLVM_DEBUG(StringRef DepType =
                       D->isFlow() ? "flow" : D->isAnti() ? "anti" : "output";
                   dbgs() << "Found " << DepType
                          << " dependency between Src and Dst\n"
                          << " Src:" << *Src << "\n Dst:" << *Dst << '\n');
        unsigned Levels = D->getLevels();
        char Direction;
        for (unsigned II = 1; II <= Levels; ++II) {
          const SCEV *Distance = D->getDistance(II);
          const SCEVConstant *SCEVConst =
              dyn_cast_or_null<SCEVConstant>(Distance);
          if (SCEVConst) {
            const ConstantInt *CI = SCEVConst->getValue();
            if (CI->isNegative())                        // (A)
              Direction = '<';
            else if (CI->isZero())
              Direction = '=';
            else
              Direction = '>';
            Dep.push_back(Direction);
          } else if (D->isScalar(II)) {
            Direction = 'S';
            Dep.push_back(Direction);
          } else {
            unsigned Dir = D->getDirection(II);
            if (Dir == Dependence::DVEntry::LT ||        // (B)
                Dir == Dependence::DVEntry::LE)
              Direction = '<';
            else if (Dir == Dependence::DVEntry::GT ||
                     Dir == Dependence::DVEntry::GE)
              Direction = '>';
            else if (Dir == Dependence::DVEntry::EQ)
              Direction = '=';
            else
              Direction = '*';
            Dep.push_back(Direction);
          }
        }
        // (snip)
      }
    }
```

At (A), `CI->isNegative()` gives a distance, not a direction. So I think the direction should be `>` for `CI->isNegative()` and `<` for `CI->isPositive()`. Changing so will be consistent with (B) because `Dir == Dependence::DVEntry::LT` when `CI->isPositive()`.

However, another problem arises. Changing so will prevent interchange of `pass1.ll` above. Before the change, the debug output for `pass.ll` is:

```
$ opt -S -passes=loop-interchange -cache-line-size=64 -debug-only=loop-interchange -o /dev/null pass1.ll
Processing LoopList of size = 2
Found 4 Loads and Stores to analyze
Found anti dependency between Src and Dst
 Src:  %a.val = load i32, ptr %a.ld, align 4
 Dst:  store i32 %b.val, ptr %a.st, align 4
Dependence before interchange
< = 
(snip)
Loops interchanged.
(snip)
```

After the change, the debug output for `pass.ll` is:

```
$ opt -S -passes=loop-interchange -cache-line-size=64 -debug-only=loop-interchange -o /dev/null pass1.ll
Processing LoopList of size = 2
Found 4 Loads and Stores to analyze
Found anti dependency between Src and Dst
 Src:  %a.val = load i32, ptr %a.ld, align 4
 Dst:  store i32 %b.val, ptr %a.st, align 4
Dependence before interchange
> = 
(snip)
Not interchanging loops. Cannot prove legality.
```

The correct dependence is same as `fail1.ll` (flow dependence form `store` to `load` with a direction vector `(<, =)`). A dependence form `store` to `load` is not analyzed because the analysis loop is triangle at (C).

I'm confused by:

- Why DependenceAnalysis returns anti-dependence from `load` to `store`?
- Why the analysis loop is triangle at (C)?

I suspect DependenceAnalysis also returns a destination-to-source (not only source-to-destination) dependence information with a reverse distance vector (and direction vector). If so, we must address the *reverse* case.

# Question

1. My change for `fail1.ll` (`>` for `CI->isNegative()` and `<` for `CI->isPositive()`) is correct?
2. The current behavior of DependenceAnalysis for `pass1.ll` is correct?

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJztG9t24jjya8iLDhxsEwgPeSBAz9An3XNJT8_uvvSRbQGaNhJr2ST0129VSb5imKS3Z3Z2TnII2LqUqkp1lx3q-Hi7Ymudq5hxZuRunwi2k8aIuK_3mdzJLzyTWjGp2L3W-5XKRBptudoIxmFOlkoB35qt5dOAfa8fxUGkPX_OVj1_smORVuscYOH0bCtYlKepUBmjdXZwRcAHveGiN5y5bz9gP6Y6hP568weYvdZJoh-l2rAEUDEs4oqFAmCXOMW4ik5FJiOeJEfojTisj61HphW0bPkBMGdrAMRisRcqFioS7FFmW2iOZSoiovcAvzplvfGw59_0gjnS1AsWPX8KTWyd6h2Djn_APVIPl_-EyyYh4-Gay8QbJAlCCWatTvtJkoOjM-PpRmQs5hlP-FHnGa4HkH3R38Fs0ZeAxwz_A78vvTFc0BfejUdwMR5BMyI7g---Cnzb9oBtvt9YBLYNN9otwDmwD0bm6rPSj6qfSJU_9TcqL6fZ71ispRIsNvpTooHB7KBlzHqj4Vpr4MA-S5nSPJHcwC9IlFgD9GuOrDvTF17oi5C3vcmdXRtkJT2WTGQsTFnCQ5HgSJQGb7AVPAbZq-HbaK-mwgzpE-37rWTAO9a7vmMe7bB_TQtBy4LuoYOGD6SK3AALNeFZtKVhdagDY3eNx7EFjI04z2sOS-LuYcNz5PlnyPO7yfPOklfnSZtKr0WlXx9Xh95FptfA3w7rIPNkGC-AgVwKaxRQIKQKURQMIgdTn5gEebboYnchVyVYgFK_x51oLOJQ-S8XSeLmInBfLRJ-7SJhY5HGCjXw0dcyKnoW-HBwAI1G-InmMUGpYegoByXdKDYqphkwkQKHlgDqrHNb4ubAIsFdaTPtTLCcHNAGpABh-IUl77ymsPFLaPEmWsUKaIrtcLLTrSUq8A30eQv9qIl-U7BBT0rJVvkjU-axyeG6vltVEk8yA3cYD5S22yij3Z6Jf9eky2nfOKhZAVTlLhA4sGUAySSdtJ-zHMX4ll28SNqJKbOAfpc0_3dI886Thh0dtJ7SRAMrYiAGIPfkhkwWLb_bjC2kYaufIVqB6MTsNWoTiGbWCDlAMFK9Sfmu28lHF3x8VEY2zoO-99h4dNLoV430Td7VutZcGZBCCG9QlgFH8N9RBmCsUL93Cl_Q7v7KSeHXTIouTKr5ZQYYor5UKCYauOUcrIcaSddzoK_vbkHL6dMAcw6QVwPkWUCeA-SdAcS6rQoBCk-MQdCYGbX7rTJcnFVKV-3yssTVAmUKTTlExRAwZ41Yti1oDTD-iEF8zvoPrL_nEK4bQBNVo1-DwPoRj7YC4znRN_KLgDGgkf1YhPmmj-Fw5yQMZ9_E4gDfKk8SVkaxtDLE5pEwBlUCE4J7CV5JrxmCJ1Y5n_KGUooRjOGgTZgqPKC1JcXiiidHwKY2sBmPY-CePQqh2EMa0eRF6c6hBfTsZb7HTUUgwcvdip29qJKFUKxp7YppblOCpQ2p24xaKSVSSp9sgOARTT_kWaPVbe0bYDdlTNWWPHM-i3PyqVVeYyG-13XBKvOnAZtzhSYbDBskRYnYAMHZcXBBbn-waZyGrxRSKRU7CT5JzUCgmckjZMA6x0ysIdgMszlKx2K5XouUuGpzqkbSxMAuI3RaM8VIVK_LEAJZcCbvQo14zbte867XvOs17_o75l1_Zl70B6R1r3nXa971P45pywjhD4xpucrky2LarwpMy7D25RHxs2La-TeIaedbEX3GWXJdCxAzudlmEAQqSDNF3B6pIPfMqRhvitMH5vwirkT3VpVo4n0Jdi_StYjagKt-CnRxz06IJZpWwJEnhzwwjCiq2pwWPuwhVM4QT4xNJc4jwuoYmXJMyavvLf6xVm5FHv-Wmwy77lKuQLDxVCNJmkh3JIW1neNr6O3auAVly5f0zw_YUh1kqhV6tXrXPc8Eur3xcMelwlA8JPzQ0kd6t5MZC6cj7-Z6Eo6GeCjSAHsDsekcsvcvW_ELT0KRZuDPJwaMQ4SnP5EG0Dsdg2FxsCRGoBn0J-IAaoMuBfm6t-dATEdRnhoWQt5RCCqdJtnJKA2WCVXjCUoBm6GGGmmalR8Iq9FyMIj79xD6r-2ZTzMHOZdDvKbi_yepOEikUXJfCUWXNqwyklHwmFgGjDKbpbqb05NBENnuw0G8IYfsepfN3pb01bdboob8BuCxZoe50B0KNEyShqzQO9AboP1HbWQmD4IOInNFWFHkebPNsj1Jq_8GPhuZbfNwAAoBN5Tv2p8-qBWuArdhokP8qalyOVJizwfQegMs3hm4eQDTxFO4aJ0ED6I98Da496ZeOxlfgU5K9dlqJh3FSrLmFW17vc_BaIpyU4_vOKTJT3896rxJR6mhqPDaSmSzJLoiEXwndiv0ZYNQbMCUYlFgSifky2a3wGoKdYL1g6m-h92rpY2vEfzqXMn0LUFaIdS3l6C-LaC-rUF966BS-dPyFmHOS22xhVGTxcj7YGblH6Qe2JOinsHOtYqoq8p3A6gZWg5cNeKo9fNaL2kHYDdbWQwvAFm4LOwCkLenQBw9q41CM7FSaONL2yaFGdQHSyouScMBPhpLXMMCR0uHXPLH8GFdI9Cg4b42eMbwAQiIAHLRjRbIX_QZIwxACzfvDZhesnZgZmeN6LEbVZ6DCbcV6sWqD4jY8abAeE52Fkt0KaBA6LUr5Yyhy0ozJAEhgKnBQptwUlOQ3PP95dPemiaunLdEyOQtdFoGuwOsXZ1sA2P39x_ffVos7375DpEDBVebn8UaZefDcU_uqjm-9edwswyyiAUopv6aWrCsNCsGIeeagzi12EHwW2Dvn2BZ-4vDjSmhzCmS8n3rIS0oanP4X8Qd97uE8Hue9Xquyurfs-BZJ1xDqVS4YgjCdA63OcyqlLub2KUnXZtXHsnci4NIjBU4ZPZGZLaptDEt8QcTwRaF6zzpbp_4rFbVYQ9dz_HWrVCZwVM76FaDVCFjD_PlR6IOwiGOMUId26IRrXOHzWlCmeMVyA6xtLg_J6rxUX1C2_RJp58wVgPk6zCclSiX71rZKnU56wyVBYYF5JVFcG55V852BH_kCap-5-5Ua85XVnXeQ2pEoYXzUtOzAlj6idmJzbN_5a67aveE4qRJJxKwvaKFyb9Eqkssngl_cQn-M2Esz8EATR_sc7P9FILNpq0spLqTs73Jok6WM01FjOGE79wGn-D18K2x6ly21EOA0tKaEupZtSlEyc2l6dU5FEUOi4_L4jQhmN1_ACTm8DkVqbszW87Ys4Evv61UPnfd7wqiLhjwZ8N6AQ1npfYraFj-9KdqnD_7drLdbDptKCWskQ12jL5ct5xlpeHD1G48PGM-IYPZwJ2hB0sLw2-Tw9qjpgP2oFk9T6pSTbPVeRLjM650krmknMhWKM4vSeeiOHzeMbzMHYvhAzYvDoWNZo8ySXA59DCAMRZr6MlYp5Tl87Qw8fl6jmg8biHOuYhHncG1xyO4sofNRSmIp9II04H1PoUpqvEEBZ0WN06DGQ_1QQzYXa2IZKsG7hy7qxiE8_-CtaDXEvZXlbDb2n-2xPqsotGsqju-ytHfXo4u1RS_3UM2jbJjhZY0zPCdgHy9XaEGVNrvM2BRC4cRI3AMvqQwHiIjyRy_6HUHLHux2QvAu3K-E4S4_hqGbQTnYo9L8AGfVALDEujJirpTs4TYfJMkPLZUp89-3R5rPqio8-NRZJ4qQ8LXryPvHjQqsLW4F6T0gjd1uM9FuZxW1D1NbrBe0oUYT8BpldgBX00mFb0J08903-g8xazVv0Ee0lNStgk7a2PRH9fFQ-Gm2Jd13PaiR0yNKIOPcpf9G1S69u7TNq9A1zXu_qNguxyUn8cx6LV9DguCNQcTrrASJ05e3fkpRwwBu1q7N2Dvjs5Adp2woMj9UfENcglY7vSp3CXfVffd-0ih2PKD1PR8WceG1Qx47cm0Nsyr-DaIp8GUX2UyS8Rt7_quVUrGx0l_TfGx1hPNK2Xs9EUrWOAqT5PbF9e_pTGwG3BxPfYn11fb26k3nUaj6ziKgiAGpZzcBONoNPWCgIeTURxf0Wm_Qcx7vo_STu-AUUmPSkm0TjCrvxlmqt6O98ao_LS4krf-0PeHY386HHqjwB-IaciH4ia64eEYcBn3RkOxA5EY4AoDnW6u0luiBlyZgc4ERNhUnbARmKkSjxE-z7OtTm8_80dutnLH--vfroj6WyL9P3VwwuE">