[LoopInterchange] Try to achieve the most optimal access pattern after interchange
authorCongzhe Cao <congzhe.cao@huawei.com>
Wed, 6 Apr 2022 19:15:37 +0000 (15:15 -0400)
committerCongzheUalberta <congzhecao@gmail.com>
Wed, 6 Apr 2022 19:31:56 +0000 (15:31 -0400)
commiteac34875109898ac01985f4afa937eec30c1c387
tree767ced63c893aa9060d4a753a977034aabed2b33
parent375d93465b3e6f342e0554cfaee308a45a523969
[LoopInterchange] Try to achieve the most optimal access pattern after interchange

Motivated by pr43326 (https://bugs.llvm.org/show_bug.cgi?id=43326), where a slightly
modified case is as follows.

 void f(int e[10][10][10], int f[10][10][10]) {
   for (int a = 0; a < 10; a++)
     for (int b = 0; b < 10; b++)
       for (int c = 0; c < 10; c++)
         f[c][b][a] = e[c][b][a];
 }

The ideal optimal access pattern after running interchange is supposed to be the following

 void f(int e[10][10][10], int f[10][10][10]) {
   for (int c = 0;  c < 10; c++)
     for (int b = 0; b < 10; b++)
       for (int a = 0; a < 10; a++)
         f[c][b][a] = e[c][b][a];
 }

Currently loop interchange is limited to picking up the innermost loop and finding an order
that is locally optimal for it. However, the pass failed to produce the globally optimal
loop access order. For more complex examples what we get could be quite far from the
globally optimal ordering.

What is proposed in this patch is to do a "bubble-sort" fashion when doing interchange.
By comparing neighbors in `LoopList` in each iteration, we would be able to move each loop
onto a most appropriate place, hence this is an approach that tries to achieve the
globally optimal ordering.

The motivating example above is added as a test case.

Reviewed By: Meinersbur

Differential Revision: https://reviews.llvm.org/D120386
llvm/lib/Transforms/Scalar/LoopInterchange.cpp
llvm/test/Transforms/LoopInterchange/phi-ordering.ll
llvm/test/Transforms/LoopInterchange/pr43326-ideal-access-pattern.ll [new file with mode: 0644]