This is an archive of the discontinued LLVM Phabricator instance.

[LoopInterchange][PR56275] Fix legality in dependence vectors
ClosedPublic

Authored by congzhe on Jul 20 2022, 11:11 AM.

Details

Summary

This is the 2nd patch of the two-patch series that fix PR56275 (https://github.com/llvm/llvm-project/issues/56275): D130188 D130189.

Following up on the dependence analysis (DA) patch D130188, in this patch we query DA with NeedsNormalize=true in loop interchange, such that the DA results queried by loop interchange are normalized. With a minor fix w.r.t. how loop interchange interpret dependence distances, all tests in PR56275 can get interchanged.

I've added the tests in PR56275 in lit test pr56275.ll for more details.

Diff Detail

Event Timeline

congzhe created this revision.Jul 20 2022, 11:11 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 20 2022, 11:11 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
congzhe requested review of this revision.Jul 20 2022, 11:11 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 20 2022, 11:11 AM
congzhe edited the summary of this revision. (Show Details)Jul 20 2022, 12:02 PM
congzhe added reviewers: kawashima-fj, bmahjour, Meinersbur, Restricted Project.Jul 20 2022, 12:04 PM
congzhe set the repository for this revision to rG LLVM Github Monorepo.
congzhe added a project: Restricted Project.
kawashima-fj accepted this revision.Jul 21 2022, 5:33 AM

Thanks @congzhe . LGTM.

This revision is now accepted and ready to land.Jul 21 2022, 5:33 AM

As mentioned in https://github.com/llvm/llvm-project/issues/56275#issuecomment-1183363002, I think both directions need to be considered. < or > of the Dependence object mingels relation between the Src/Dst argument. Here, it is interpreted as the direction of the loop.

However, with normalizing this could be correct, but only when we bail out with any bidirectional dependencies. See my inline comment. Such subtly should be worth a source comment somewhere.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp
140–141

[serious] A SCEV can be neither isPositive(), isZero(), nor isNegative(). This is for instance that case when it depend on a variable which can be either one of them at runtime. This code implicitly assumes that such a distance is "negative". It should be '*'.

congzhe updated this revision to Diff 447154.Jul 24 2022, 4:15 PM
congzhe added inline comments.
llvm/lib/Transforms/Scalar/LoopInterchange.cpp
140–141

Thanks for the comment. Thinking about this piece of code more carefully, I think the entire if (SCEVConst) block can be deleted. This code block is merely a subset of the the else block where we could just leverage Dir = D->getDirection(II) to construct Dep. Another benefit is that the else block explicitly addresses your concern - if the direction is bidirectional, it would be a "*".

Meinersbur added inline comments.Jul 25 2022, 2:36 PM
llvm/lib/Transforms/Scalar/LoopInterchange.cpp
132

Before I can accept the patch, I would like to see D130188 to treat a Dependence object as immutable (modifying global state is incompatible with pass manager analysis caching)

140–141

I think you are correct. If the distance is positive/negative, the direction be </> anyway.

congzhe updated this revision to Diff 447783.Jul 26 2022, 11:47 AM
congzhe added inline comments.
llvm/lib/Transforms/Scalar/LoopInterchange.cpp
132

Thanks for the comment, I've updated D130188 such that Dependence::normalize() does not change this object but just returns a new Depenence object.

congzhe updated this revision to Diff 448724.Jul 29 2022, 2:56 PM

Updated the patch according to the most recent update in D130188

Meinersbur accepted this revision.Aug 2 2022, 11:24 AM

LGTM, thank you

bmahjour accepted this revision.Aug 3 2022, 7:08 AM
congzhe updated this revision to Diff 449826.Aug 3 2022, 4:36 PM

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

This revision was landed with ongoing or failed builds.Aug 3 2022, 5:00 PM
This revision was automatically updated to reflect the committed changes.