This is an archive of the discontinued LLVM Phabricator instance.

[LoopInterchange] Refactor and rewrite validDepInterchange()
ClosedPublic

Authored by Narutoworld on Nov 4 2022, 1:16 PM.

Details

Summary

The current code of validDepInterchange() enumerates cases that are legal for interchange.
This could be simplified by checking lexicographically order of the swapped direction matrix.
It is pure refactoring and rewriting, the new code aligns with the logic within validInterchange()

Diff Detail

Event Timeline

Narutoworld created this revision.Nov 4 2022, 1:16 PM
Herald added a project: Restricted Project. · View Herald TranscriptNov 4 2022, 1:16 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
Narutoworld requested review of this revision.Nov 4 2022, 1:16 PM
Narutoworld retitled this revision from [LoopInterchange] rewrite validDepInterchange() to ensure Lexicographically Order to [LoopInterchange] Refactor and rewrite validDepInterchange().Nov 8 2022, 11:16 AM
Narutoworld edited the summary of this revision. (Show Details)
Narutoworld edited the summary of this revision. (Show Details)Nov 8 2022, 11:20 AM
Narutoworld added reviewers: Meinersbur, bmahjour.
congzhe accepted this revision.Nov 11 2022, 7:42 AM

LGTM.

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

This revision is now accepted and ready to land.Nov 11 2022, 7:42 AM
Meinersbur accepted this revision.Nov 11 2022, 2:39 PM

This involves a deep copy of the entire DepMatrix. I still find that acceptable to gain a much more logical dependency checking.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp
210–213

I think this logic here is also superseded by the new logic.

215

[typo]

Narutoworld marked an inline comment as done.Nov 14 2022, 11:33 AM
Narutoworld added inline comments.
llvm/lib/Transforms/Scalar/LoopInterchange.cpp
210–213

Hi @Meinersbur, Thanks for your comment.

The logic says if any dependency vector of InnerLoop or OuterLoop is unknown, it is not legal to do interchange.
And the function isLexicographicallyPositive() only checked the direction vector after potential interchage.

Suppose we have a dependency direction vector (*, <, =) for 3 layers loop, i, j, k. and we want to check if we can interchange loop i, j.

The original code will prohibit interchange since i-Dep is *.

However, with isLexicographicallyPositive(), the temp dependency direction vector is (<,*,=), which makes it a valid interchange candidate.
Although I can add more codes to force the same logic, (checking the interchanged position has a * ), it contains logic beyond checking Lexicographical Order only.

That is the reason why I would like to keep the original code.

Narutoworld marked an inline comment as not done.

Fix typo

Hi @Meinersbur, would you like to take a second look?

This is definitely an improvement and I'm glad to see this change, but please see my inline comments.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp
190

Here we only check if direction is either < or >, but it could be S, which is a non-"=" direction. I think we should return false if we encounter an S in this loop, or only iterate if it's not = or I.

210–213

I prefer having isLexicographicallyPositive() handle all kinds of possible directions including S and *, this way it stands up to its name. We can check that a direction vector is positive before we swap two columns. If the direction vector is not positive to begin with, that means we couldn't correct it even with the normalization applied, so it must be treated as unsafe to interchange. If it passes the first test, we can then check if the direction vector is positive after doing the swap. This makes the logic simpler as it's all about whether an entry is isLexicographicallyPositive() or not, albeit we need to call the function twice for each row.

bmahjour added inline comments.Nov 15 2022, 2:15 PM
llvm/lib/Transforms/Scalar/LoopInterchange.cpp
190

correction: "...or only iterate if it *is* = or I"

The two changes (Direction == '*' and checking the dep vector before doing the interchange) may add safety, but also cause tests to fail. @bmahjour suggested we could mark those as XFAIL and fix in a followup-patch, if not directly handled in this patch. Thing that I think are two strict:

  1. I don't think the check before the interchange is necessary. Dependency vectors in the original code are in forward direction by definition.
  2. The surrounding loops do not matter if the interchanged loops can still preserve any dependency. That is, the two innermost loop in a dependency vector (* < <) can be interchanged. Same argument that true dependency must have been forward in the original code. Think of the * being in another function that calls a function containing the < < loops. In that case, DependenceAnalysis would not even see that surrounding loops and would not have mattered. On the other side, the case (< * *) could still be interchanged because the dependency is known to be already carried by that surrounding loops and the two inner loops don't need to care.
llvm/lib/Transforms/Scalar/LoopInterchange.cpp
147–152

<= and >= are handled the same way as < and > respectively. I think this is incorrect.

Consider the loops i,j,k and the the dependency vector (<,*,<=). i and k cannot be interchanged as it would yield (<=,*,< ): <= is not guaranteed to carry all the dependencies before hitting *. This code here handles is the same as (<,*,<) where i and k can be interchanged.
Alternatively, to have just neighboring loops, consider (*,<=) assuming we do not need to check the before-state that was suggested by @bmahjour .

194

A dependency vector with a leading * (and maybe S as @bmahjour suggests) (such as (* <), (= * <), (= = * <) etc) would not be known to be lexicographically positive. Even if this would change the semantics, I think we should change this so match what is expected from a function called isLexicographicallyPositive.

I think this was missing to supersede the * logic below.

210–213

I do think interchanging the loop that results in a (<, *, =) vector is perfectly fine. This is because the original dependency will always be lexicographic positive because .. the instruction cannot have dependendent on another instruction that is executed in the future. The confused * state comes from the limitation from being represented in a dependence vector or limitations of DependenceAnalysis not understanding the dependency.

With moving < to the outer position, we know that dependence will be carried by that loop and the inner position dependency becomes irrelevant.

At the LoopWG call we discussed that we still could call isLexicographicallyPositive before the interchange to check that the dependency is understood before risting breaking things. I don't think it's necessary, but I don't mind.

216

[suggestion] Consider moving the std::vector<char> declaration out of the loop so it does not need to be reallocated each time, and/or SmallVector

Update patch based on comments

Update comments

Think of the * being in another function that calls a function containing the < < loops.

I agree we can think of it that way in the case of S dependencies (eg. where the outer loop IVs are not used in the subscripts of the memory access), but I'd worry about the possibility that confused direction in the outermost level might have been caused by use of outer loop IVs in combination with inner loop IVs. For example, in the following scenario we cannot think of the two inner loops being in another function unless we pass in the IV of the outer loop as parameter to that function. That will almost certainly change the way DA computes dependencies and will likely result in different direction entries for the two inner loops.

for (i)
  for (j)
   for (k)
    ... A[i, j, k+i]

The two changes (Direction == '*' and checking the dep vector before doing the interchange) may add safety, but also cause tests to fail.

@Narutoworld your latest patch calls isLexicographicallyPositive once before the swap and once afterwards, and I don't see any XFAILed tests in your update. Have you check to see if all LIT tests pass?

The two changes (Direction == '*' and checking the dep vector before doing the interchange) may add safety, but also cause tests to fail.

@Narutoworld your latest patch calls isLexicographicallyPositive once before the swap and once afterwards, and I don't see any XFAILed tests in your update. Have you check to see if all LIT tests pass?

Hi @bmahjour
I have run the whole LIT tests with ninja check-all. No failed tests found.

bmahjour accepted this revision.Nov 16 2022, 12:04 PM

The two changes (Direction == '*' and checking the dep vector before doing the interchange) may add safety, but also cause tests to fail.

@Narutoworld your latest patch calls isLexicographicallyPositive once before the swap and once afterwards, and I don't see any XFAILed tests in your update. Have you check to see if all LIT tests pass?

Hi @bmahjour
I have run the whole LIT tests with ninja check-all. No failed tests found.

Thanks. LGTM then.

rerun git clang-fomat and remove a white space

This revision was automatically updated to reflect the committed changes.