For now we are failing one test case in LICM: Transforms/LICM/lnicm.ll. The reason is as follows. Looking at the source code:

@bmahjour I updated the patch to an NFC patch with test case updates only. I'd appreciate it if you could take a look :)

Hi Bardia @bmahjour, after some thoughts I think regarding this patch we would chase a longer-term solution. For now I think I could rework and change this patch (both title and content) to an NFC patch that only updates the test cases, i.e., from using CHECK to CHECK-NEXT, since we really want to make sure that the output is ordered and the order is correct. I'm wondering how you think about it?

In D124926#3529179, @eopXD wrote:

There's some changes to lit tests. Most of them are minor. One change that applies to all tests is that I changed the target triple from "x86_64" to "aarch64" and added "-mcpu=tsv110" in the RUN lines.

IIUC, this means that IndexInner = CostMap.find(InnerLoop)->second = IndexOuter = CostMap.find(OuterLoop)->second = 0 here, right?

Thanks for the comment!

@Meinersbur Hi Michael, I'm wondering if you have further comments? I'd appreciate it if you could let me know your thoughts on my most recent update.

In D124984#3516334, @bmahjour wrote:

Although the problem reported in PR55233 is worsened by D123400, the underlying issue existed even before that (as illustrated by the example in PR55233), so this patch won't completely solve the overflow problem, although it would make it a bit less likely to occur. I think a proper solution to PR55233 would need to address the overflow problem itself (eg by increasing the range of values that the cost model can represent).

I had thought about this approach when working on D123400, and while I agree it will make the cost values smaller, I have some reservations about its accuracy.

One observation is that with this patch, the cost values for non-consecutive accesses in deep nests become smaller, but also their relative differences reduce as well. For example in single-store.ll, the cost difference between for.k and for.j is in the orders of magnitude, while the cost difference between for.j and for.i is much smaller. I worry that this dilution of cost difference might make it harder to find the right order in loop nests that contain multiple reference groups. I think this approach slightly diverges from the concepts presented in the paper, inasmuch as, the unit of measurement for the cost value is meant to be number of cache lines, but with the multiplication by the "depth" factor the value will no longer be estimating number of cache lines.

Addressed reviewers' comments.

Thanks for the comments, I've updated the patch accordingly.

@bmahjour Hi Bardia, I've updated this patch to a pure NFC patch with the motivating test case only. Looking forward to your comment :)

In D123400#3486341, @bmahjour wrote:

Sorry for the delay, as I didn't get a chance to commit this before I went on vacation.

I just noticed that after fixed-size delinearization commit went in, this patch needed to be re-based and new values needed to be generated for the newly added LoopnestFixedSize.ll. I also noticed that this test exposes an issue with the analysis producing large cost values that can overflow the underlying int64_t type. This problem is not specific to this patch, as described in https://github.com/llvm/llvm-project/issues/55233. I think the overflow problem should be dealt with as a separate issue and will add it to the agenda for the next LoopOptWG call. In the mean time I've changed LoopnestFixedSize.ll to use smaller trip counts. @congzhe please let me know if you are ok with this change. We should recreate a test with large sizes as part of fixing 55233.

Thanks for the comments, I've updated this patch accordingly.

Addressed Florian's comment, will land it shortly.

In D122857#3483912, @fhahn wrote:

In D122857#3483652, @congzhe wrote:

In D122857#3483562, @congzhe wrote:

In D122857#3483554, @jyknight wrote:

The test case added here appears to sometimes fail due to output ordering differences. E.g. https://lab.llvm.org/buildbot/#/builders/16/builds/28225

That failure is blamed on my revert commit -- but in my local build, the test isn't failing. Perhaps there's some nondeterminism in processing order? I might switch these to CHECK-DAG, though I don't know if that's just covering up some other underlying bug...

Thanks James, I've noticed that as well - In my local build it does pass. But I should have used CHECK-DAG. Let me commit a small patch that does this.

Fixed in https://github.com/llvm/llvm-project/commit/97b8a54b25f326cac8324e0ee3adde271799951c

CHECK-DAG works around the non-determinism. The analysis should probably be fixed to print results in a deterministic fashion.

In D122857#3483562, @congzhe wrote:

In D122857#3483554, @jyknight wrote:

The test case added here appears to sometimes fail due to output ordering differences. E.g. https://lab.llvm.org/buildbot/#/builders/16/builds/28225

That failure is blamed on my revert commit -- but in my local build, the test isn't failing. Perhaps there's some nondeterminism in processing order? I might switch these to CHECK-DAG, though I don't know if that's just covering up some other underlying bug...

Thanks James, I've noticed that as well - In my local build it does pass. But I should have used CHECK-DAG. Let me commit a small patch that does this.

In D122857#3483554, @jyknight wrote:

The test case added here appears to sometimes fail due to output ordering differences. E.g. https://lab.llvm.org/buildbot/#/builders/16/builds/28225

That failure is blamed on my revert commit -- but in my local build, the test isn't failing. Perhaps there's some nondeterminism in processing order? I might switch these to CHECK-DAG, though I don't know if that's just covering up some other underlying bug...

Landed this patch, will work on the refactoring in the next patch.

Hi Bardia @bmahjour , my apologies that I did not clearly remember the discussion during the loopopt meeting -- was it like you would like me to commit this patch for you, or was it like you would like me to keep an eye on it after you commit it?

In D122857#3465404, @Meinersbur wrote:

In D122857#3464913, @congzhe wrote:

I wonder if you could clarify what you meant by "continue with this patch"? I would certainly like to continue with the current patch if possible, but due to opaque pointers it seems that the current approach in this patch become fragile and not viable?

I would not block this based only on a possible future development, taking into account that there are already uses of getIndexExpressionsFromGEP (e.g. by DA) and there is a possible workaround.

In D122857#3463093, @Meinersbur wrote:

@congzhe Could you write here what your plans are? Continue with this patch? Improve the SCEV-based algorithm? Introduce array size hint metadata?

In D110972#3463438, @Meinersbur wrote:

I think the correct fix is to handle AddRecExpr from a loop outside LoopNest like other non-AddRec expressions. At the moment this means "non-linear" (like D110973) unless it is completely loop-invariant. This is a limitation of the current checkSubscript that does not look into other kinds of SCEV expressions. In @test1/@test2 this is all we can do because %c.1.lcssa (which has the value of %add27 when the loop exists) has an undefined value because with the backedge branch on undef, %c.1.lcssa is undefined which usually is not considered "linear".

DependenceInfo::depends should actually call getSCEVAtScope instead of just getScev (like tryDelinearize already does), because if ScalarEvolution can understand the backedge taken count, the SCEVAddRecExpr will be simplified to that result.

In D123400#3460157, @bmahjour wrote:

The current loop cache analysis outputs the loops in the correct order by luck (because it maintains the original breath-first order and that order just happens to be the optimal order), but it outputs the same cost value for the two outer loops, which is the root problem! By ensuring that the correct and distinguishable cost is associated with each loop we also ensure that the optimal order is maintained. I do see your point in wanting to make sure that the sort order is correct, but if that's the case we probably want to use CHECK-NEXT instead of CHECK-DAG for your test.

In D123400#3457537, @bmahjour wrote:

What I did is to take the stride into account as a second component, and for each loop take the maximum stride of all reference groups to get the final stride, which presumably could resolve the motivating problem too.

Treating stride as a secondary component is what I respectfully objected to, and explained earlier. Not sure if taking the maximum stride would give us what we need. For example consider

for (i)
  for (j)
    for (k)
       ... A[i][j][k]
       ... B[i][k][j]
       ... C[i][k][j]

the maximum stride will be the same for both i-j-k and i-k-j configurations (despite the second one being more profitable) bringing us back to the original problem.

Addressed comments from Michael @Meinersbur and Bardia @bmahjour.

In D123400#3443913, @bmahjour wrote:

In D123400#3442881, @amehsan wrote:

1. Boiling down various parameters to one final "cost" value has a disadvantage. In fact we discussed this with @congzhe as the first solution, but we discarded it because essentially you lose some informaiton when you boil everything down to one number. The reason that Congzhe decided to go with a two component cost was that extra detail, carries more useful information and helps to make more accurate decision. Now this was a theoretical concern and I am not sure if in practice it holds or not. But that is the background on congzhe's work.

The cost returned by the analysis must consider the impact of outer dimension strides incurred by each reference group, otherwise it will not be accurate. If, for whatever reason, we need extra details in future we could provide extra interfaces to the analysis to query those details.

1. Wouldn't it be more appropriate to continue discussion on congzhe's patch rather than posting a parallel patch to address the same problem? I think that will be more constructive given congzhe has already identified the problem, investigated some solutions and developed a patch? I suggest we continue the discussion, as review comments on his patch. Once there is an agreement on the cost function, Congzhe can update the patch (assuming it is needed) to reflect the agreed upon solution.

I explained my reasoning for needing a different approach in D122776. I just figured it would be a lot easier to show what I mean by posting a new patch instead of trying to describe it as a change request on top of D122776. I'm happy to continue further discussion on this wherever seems more appropriate to you or other reviewers.

Thanks for the comments! I modified the wording a bit for the title and summary, addressed the comment from Michael @Meinersbur and added test cases correspondingly, thus addressed the comment from @fhahn.

Minor update to address the last comment, I'll land it shortly.

Thanks a lot for the comments @Meinersbur! I've updated the patch accordingly.

In D118102#3370252, @bmahjour wrote:

With the recent updates we are no longer losing test coverage. Per discussion in the Loop Opt WG call, I'll approve to get this in as a small incremental improvement. I'll look into https://github.com/llvm/llvm-project/issues/54176 and follow up with more patches.