I would suggest to revise the summary and/or the title to describe that this patch now also addresses the endless interchange problem, in addition to correction in isProfitableForVectorization().

Hi @bmahjour and @Meinersbur , would you like to take a look on the patch?

According to the discussion at the LoopOptWG, I will land the patch to fix the miscompile for now. Will look into how to fully support such reduction scenarios as the next steps.

Just one more question on the summary: when combining the two dependencies [<,=] and [=,<] that generated [<=,<=], I think we could still interchange the combined dependency? [<=,<=] is non-negative and swapping the two elements <= and <= gives a non-negative dependency. Thus we are not converting a positive dependency to a negative dependency, hence not violating the dependency rules for a valid interchange. Perhaps with the current validDepInterchange() we cannot interchange [<=,<=], but like I mentioned in the past meetings I'm rewriting validDepInterchange() to make the legality decisions be purely based on the signs of the dependence vectors before/after interchange. With the rewritten validDepInterchange() I think we can interchange [<=,<=].

In D134930#3867354, @Meinersbur wrote:

LGTM. Thank you.

The additional check make sense.

In D135808#3861367, @ram-NK wrote:

If outer loop dependency direction "=" and Inner loop dependency direction is "S" and "I" then, loop interchange is considered as profitable. Only two cases of dependency is profitable. But for vectorization, ">" and "<" dependency in outer loop is more profitable when interchanged. After patch [=,<] and [=,>] will be interchanged for vectorization.

In D132055#3814831, @uabelho wrote:

Hello @congzhe ,

I think I'm seeing a miscompile with this patch:

opt "-passes=function(loop(loop-interchange))" bbi-74005_x86.ll -S -o -

Now I don't know how this is supposed to work but it looks to me that in the input code we read

%arrayidx14.promoted.i = load i32, ptr %arrayidx14.i, align 1

then do 512 rounds of the inner loop and add the read elements, and then we store what we have so far:

%18 = tail call i32 @llvm.vector.reduce.add.v4i32(<4 x i32> %16)
store i32 %18, ptr %arrayidx14.i, align 1

But after loop-interchange we load, then add, but then we dont do the store, but do the load and execute the inner loop again? So it looks like we throw away the calculated addition and just read the same values again?
Or am I missing something here?

bbi-74005_x86.ll2 KBDownload

In D132055#3814831, @uabelho wrote:

Hello @congzhe ,

I think I'm seeing a miscompile with this patch:

opt "-passes=function(loop(loop-interchange))" bbi-74005_x86.ll -S -o -

Now I don't know how this is supposed to work but it looks to me that in the input code we read

%arrayidx14.promoted.i = load i32, ptr %arrayidx14.i, align 1

then do 512 rounds of the inner loop and add the read elements, and then we store what we have so far:

%18 = tail call i32 @llvm.vector.reduce.add.v4i32(<4 x i32> %16)
store i32 %18, ptr %arrayidx14.i, align 1

But after loop-interchange we load, then add, but then we dont do the store, but do the load and execute the inner loop again? So it looks like we throw away the calculated addition and just read the same values again?
Or am I missing something here?

bbi-74005_x86.ll2 KBDownload

In D132199#3796658, @aeubanks wrote:

thanks, lgtm with one nit
sorry for the long back and forth

I do think that the loop nest infrastructure in general needs some work and doesn't fit in with the rest of the new pass manager infrastructure very well. there should have been an RFC (unless I missed it)

LGTM but I'd suggest to wait a couple of days to see if people have other comments. @fhahn would you like to comment on this patch?

In D132055#3734791, @uabelho wrote:

I have no idea if this is the right fix, but I've verified that it solves the problem that I reported in pr 57148.
Thanks!

However, that was a reduced version of the problem, and if I try the original non-reduced version (unfortunately for an out-of-tree target) I get another failure with this patch.
So it might be a step in the right direction, but there are more problems lurking.

A reduced version of the new problem is

opt -passes="loop-interchange" bbi-72571_2.ll -o /dev/null

which results in

Instruction does not dominate all uses!
  %i.166.lcssa = phi i16 [ %3, %vector.body85.split ]
  %arrayidx60 = getelementptr inbounds [2 x [4 x i32]], ptr @c, i16 0, i16 %i.166.lcssa, i16 %j.165
LLVM ERROR: Broken module found, compilation aborted!

bbi-72571_2.ll1 KBDownload

In D132199#3792795, @aeubanks wrote:

I think I'm ok with this sort of patch being a temporary workaround
could you add a FIXME pointing to the discussion here?

Using PreservedAnalyses to tell the loop pass manager that the loop nest structure has changed is still IMO an abuse of it. The whole point of PreservedAnalyses is that we determine whether or not some cached analysis for a given IR unit should be invalidated. The loop nest analysis shouldn't be modeled as a loop analysis since it's not at the same IR level (that's why https://reviews.llvm.org/D132581 is wrong, caused issues, and was reverted). This is essentially adding an extra bit to the pass's return value to tell the loop pass manager to change how it behaves, which is not what PreservedAnalyses is intended to be used for. But that's exactly why LPMUpdater exists, for this sort of thing. So I'd still like to go back to the LPMUpdater version.

I also think there may be issues with loop analyses not being invalidated in regards to loop-interchange. If an inner loop has a cached analysis, right now I believe interchanging does not invalidate the (original) inner loop's analyses, but we may end up running a loop nest pass on it with its old analyses once it's the outer loop, even though the loop structure has changed. But that can be a separate patch.

In D132199#3785586, @aeubanks wrote:

Sorry, I'd meant to reply but didn't find time, I'll try to be more prompt about responding to this

This is definitely better than the previous version.

IMO it would still be best if continually rerunning a pass on some IR would reach a fixed point. For example, when loop unswitching happens, we revisit the current loop (which means restarting the entire loop pipeline), and if we end up creating a new loop, we also add that new loop to the worklist. There has been care taken to ensure that unswitching cannot run forever. If interchange did this, we'd be able to just revisit the entire loop nest again. For the interchange example, you say that loop-interchange may continually swap between L1(L2) and L2(L1), one of them must be better than the other, why can't we converge on the better nesting? I don't quite understand the "locality vs vectorization" argument, there still must be one nesting that's ultimately optimal in the end. Then we can restart the pipeline on the loop nest, or just the loops that got swapped around.

But if that doesn't make sense, then something along these lines seems ok. I think it might be worth revisiting exactly how loop nest passes work, but I haven't thought too hard about it. But then again, this seems like a loop-interchange-specific issue, not a loop nest issue.

also you'll have to rebase again since my patch was reverted
also seems like we've dropped the test?

ping @aeubanks :)
I'm wondering if you have comments on my most recent change?

Like I said I won't block the patch, I'm fine if other reviewers accept this patch.

Rebased on D132581.

Will rebase on D132581 once it is landed.

In D131606#3750026, @aaronkintel wrote:

In D131606#3747208, @congzhe wrote:

IIUC the problem you described has been addressed and handled in CodeMoverUtils already.

The function isSafeToMoveBefore() has the following signature where the last argument CheckForEntireBlock can be set to true such that previous instructions (before the current instruction that is under consideration) would be considered when checking if it is legal to move it. If I'm not mistaken, for the IR you posted we can actually move both %i1 and %i2 (by setting CheckForEntireBlock=true). You might want to check out this patch https://reviews.llvm.org/D110378, which introduced CheckForEntireBlock.

bool isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
                        DominatorTree &DT,
                        const PostDominatorTree *PDT = nullptr,
                        DependenceInfo *DI = nullptr,
                        bool CheckForEntireBlock = false);

If I'm not mistaken (please correct me if I'm wrong), I wish we could reuse CodeMoverUtils since it could simplify things.

I tried some tests with isSafeToMoveBefore(). The sink_preheader.ll test fails, since %sinkme can be sunk but then %sinkme2 cannot sink, because isSafeToMoveBefore() apparently does not ignore users in the same block like it ignores operands in the same block when hoisting. The condition CheckForEntireBlock for sinking could be added, to mirror the case with hoisting, but I foresee other issues. For example, %sinkme3 in sink_preheader.ll should not be hoisted, though the only obstacle for hoisting it (%sinkme1 ) is within the same block as %sinkme3 itself; we need to know that %sinkme1 also cannot be hoisted, and it is insufficient to just ignore variable.

In D131606#3747152, @aaronkintel wrote:

In D131606#3747037, @congzhe wrote:

The changes made in this patch, notably canHoistInst() and canSinkInst() seems to have duplicate functionality from CodeMoverUtils.cpp. I'm wondering if we can reuse the code from CodeMoverUtils.cpp? Or is there something that canHoistInst() and canSinkInst() can do but functions from CodeMoverUtils.cpp cannot do?

The difficulty I see with utilizing isSafeToMove{Before, After}() from CodeMoverUtils in this context is that when determining if an instruction in the preheader of FC1 can be sunk/hoisted, we need to take into account other instructions in the preheader of FC1 which are eligible for sinking/hoisting.

Consider this example:

define void @sink_preheader(i32 %N) {
pre1:
  br label %body1

body1:  ; preds = %pre1, %body1
  ...
  br i1 %cond, label %body1, label %pre2

pre2:
  %i1 = add i32 1, %N
  %i2 = add i32 1, %i1
  br label %body2

....
}

Both %i1 and %i2 can be hoisted, though isSafeToMoveBefore() would presumably not believe %i2 should be moved to the end of pre1. If you're seeing something I'm not, let me know and I'd be happy to simplify the code.

The changes made in this patch, notably canHoistInst() and canSinkInst() seems to have duplicate functionality from CodeMoverUtils.cpp. I'm wondering if we can reuse the code from CodeMoverUtils.cpp? Or is there something that canHoistInst() and canSinkInst() can do but functions from CodeMoverUtils.cpp cannot do?

In D132199#3740143, @Whitney wrote:

LGTM other than the comment from Bardia.

In D124926#3719876, @congzhe wrote:

In D124926#3718761, @uabelho wrote:

Hello,

We stumbled upon a case where loop-interchange seems to start hanging and consume more and more memory until it cannot do that any longer with this patch:

opt -passes="loop(loop-interchange,loop-interchange)" bbi-72548.ll -o /dev/null

bbi-72548.ll1 KBDownload

Hi Mikael, thanks for this. I've quickly looked at it and the problem can be avoided by running opt -passes="loop(loop-interchange),loop(loop-interchange))" bbi-72548.ll -o /dev/null using the new pass manager, or opt -loop-interchange -loop-interchange" bbi-72548.ll -o /dev/null using the legacy pass manager.

My impression is that the root cause is not within this patch but I suspect it is a problem with the loopnest pass pipeline within the new pass manager. This IR is a triply-nested loop, after the first interchange pass, it should still be a triply-nested loop. However, when running opt -passes="loop(loop-interchange,loop-interchange), what is populated into the loopnest data structure in the LoopInterchangePass::run() function at the beginning of the 2nd interchange pass is a 2-level (doubly-nested) loop. This is incorrect and caused the trouble (infinitely looping over the following code in LoopInterchange.cpp).

while (Dep.size() != Level) {
  Dep.push_back('I');
}

Seems like the loopnest pass pipeline does not get the loop correct, when the loop is modified during the pipeline.

When running opt -passes="loop(loop-interchange),loop(loop-interchange))" bbi-72548.ll -o /dev/null or opt -loop-interchange -loop-interchange" bbi-72548.ll -o /dev/null, what is populated into the loopnest data structure in the LoopInterchangePass::run() function at the beginning of the 2nd interchange pass is a 3-level (triply-nested) loop, which is correct.

I'll do more investigations and post updates here.

In D124926#3722578, @uabelho wrote:

I wrote an issue about a failed assertion we started seeing with this patch:
https://github.com/llvm/llvm-project/issues/57148

Note: Both the hanging and the new crash have popped up during fuzz testing with nonstandard pipelines.

In D124926#3718761, @uabelho wrote:

Hello,

We stumbled upon a case where loop-interchange seems to start hanging and consume more and more memory until it cannot do that any longer with this patch:

opt -passes="loop(loop-interchange,loop-interchange)" bbi-72548.ll -o /dev/null

bbi-72548.ll1 KBDownload

Updated to take the bool return value of normalize() into account, will land soon.

Addressed comments, will land soon.

Updated the patch according to the most recent update in D130188

Hi @bmahjour @Meinersbur, I've updated the patch such that normalize() changes the Dependence object in place, and I've also leveraged the capability of the NPM to parse pass options instead of using cl::opt. I'd appreciate it if you could take a look at this version, thanks a lot!

Thanks @bmahjour, I've tried to address all your comments in the updated version.

In D130188#3669842, @bmahjour wrote:

Since the normalize() function is conceptually an operation that applies to the result (as opposed to the analysis itself), it makes more sense for it to be a member of the Dependence class. Client code, such as loop interchange, would then do something like this:

if (auto D = DI->depends(Src, Dst, true).normalize()) {
   ...

This way the analysis can be done once, but the results can be interpreted differently if the need arises.

Thanks Michael for your suggestion, I've updated the patch accordingly.

Updated the patch according to the discussion in the loopopt meeting. @Meinersbur I would appreciate it if you could take a second look, thanks a lot!

Hi folks, my apologies for the delay, and thanks for the input. I do agree with you that we need to treat this scev expansion more carefully, although for some places where getNoopOrAnyExtend() is called (like the piece of code that Bjorn posted above), both Stride and TripCount are positive so it might be straightforward to use SE.getNoopOrZeroExtend(), or maybe just SE.getNoopOrAnyExtend() as how it is used now.

In D128877#3622951, @Meinersbur wrote:

In D128877#3621209, @congzhe wrote:

Regarding Michael's question that whether SE.getNoopOrAnyExtend() is signed extension or unsigned extension: it is actually well handled in ScalarEvolution::getAnyExtendExpr() where it could do either signed or unsigned extension depending on the actual SCEV type of the value we want to extend. I'm wondering if it answers your question? @Meinersbur

Whether to use sext or zext can make a semantic difference. Say we have an element size of i16 4 and a stride of -1 (going backwards) in 8-bit precision. That represented as i8 255. zero-extension of that is i16 255, and multiplying both gives i16 1020 which should be -4 (i16 0xFFFC).

getNoopOrAnyExtend() seems to prefer zero-extension over sign-extension.

In rGb941857b40edd7f3f3a9ec2ec85a26db24739774#1100859, @congzhe wrote:

In rGb941857b40edd7f3f3a9ec2ec85a26db24739774#1100802, @congzhe wrote:

In rGb941857b40edd7f3f3a9ec2ec85a26db24739774#1100675, @bjope wrote:

Notice that the assert is hit also when using -passes='print<loop-cache-cost>' instead of running loop-interchange.
So I do not think the problem is in this patch, but rather that perhaps LoopCacheAnalysis is broken in some way?

Thanks for letting me know! Looking into it now.

Will post a patch for loop cache analysis to fix it.