Page MenuHomePhabricator

Create LoopNestPass
Needs ReviewPublic

Authored by TaWeiTu on Jul 29 2020, 12:39 PM.

Details

Summary

Per http://llvm.org/OpenProjects.html#llvm_loopnest, the goal of this patch is to create facilities that allow implementing loop nest passes that run on top-level loop nests for the New Pass Manager.

Under the design, the loop nest passes will have a run method with the following signature:

PreservedAnalyses run(LoopNest &LN, LoopNestAnalysisManager &AM, LoopStandardAnalysisResults &AR, LNPMUpdater &U);

LNPMUpdater (short for loop nest pass manager updater) supports invalidating loop nests (markLoopNestAsDeleted), re-visiting the current loop nest (revisitCurrentLoopNest) and adding new top-level loop nests to the function (addNewLoopNests).

The loop nest passes can be grouped together by LoopNestPassManager, and then embedded into an FPM via FunctionToLoopNestPassAdaptor. Since both FunctionToLoopNestPassAdaptor and FunctionToLoopPassAdaptor require loop canonicalization passes to be run first, the LoopNestToLoopPassAdaptor is also introduced in the patch.
The intended usage of the adaptor is to group the loop passes together into an LPM first, and then embed the LPM into LoopNestPassManager. With this, the loop canonicalization phase will be run only once for both loop and loop nest passes. One example is as follows:

LoopPassManager LPM;
LPM.addPass(SomeLoopPass());
LoopNestPassManager LNPM;
LNPM.addPass(SomeLoopNestPass());
LNPM.addPass(createLoopNestToLoopPassAdaptor(std::move(LPM)));
FunctionPassManager FPM;
FPM.addPass(createFunctionToLoopNestPassAdaptor(std::move(LNPM)));

Note that the loop nest pass should explicitly preserve the LoopNestAnalysis (or just returns PreservedAnalyses::all()) if it does not modify the loop structures. Otherwise, the LoopNest object will be re-built every time a loop nest gets revisited.

Currently, the LoopNestAnalysisManager is nothing but a wrapper around LoopAnalysisManager (the former holds a reference to the latter) that provides the APIs on LoopNest and forwards the requests to the internal LPM. That is, the loop nest analyses should still be implemented as loop analyses, and the run method of the analysis receives the root loop of the corresponding loop nest.
The reason behind the design is that we do not support updating the LoopNest object dynamically yet. That means the LoopNest object will be constantly invalidated by the loop nest passes and loop passes, and invalidating a LoopNest structure means that we have to invalidate all analyses associated with it. This is quite inefficient since the analyses might have the ability to be maintained online.

There is no LoopAnalysisManagerLoopNestProxy since the two analysis managers are essentially the same thing. However, LoopNestAnalysisManager still provides a getter getLoopAnalysisManager() to extract the internal LAM. The invalidate() method of LoopNestAnalysisManager comprises two steps: firstly, the "loop analyses" of loops in the subtree are invalidated (one can preserve all analyses on Loop to avoid this), and secondly, the loop analyses and loop nest analyses of the root loop are invalidated. This is similar to what the inner proxies offer.

Other facilities like parsing the pipeline, the proxies between analysis managers, are also implemented in this patch. The PassBuilderCallbacksTest has also been applied to loop-nest-related infrastructures. The actual functionalities of the components, however, are not tested yet. Still, embedding loop passes into LNPM seems to be working as I've modified some existing loop-pass related tests to verify the results. Also, all the existing unit-tests and regression-tests work, so at least this is not breaking anything now.

Though we definitely need more testing on the functionalities, I would like the submit the diff earlier to see what you think about the patch and the design. Fine-grained tests will be added later.

Please kindly provide feedback and comments on the patch. Thank you very much!

Diff Detail

Event Timeline

TaWeiTu created this revision.Jul 29 2020, 12:39 PM
Herald added projects: Restricted Project, Restricted Project. · View Herald TranscriptJul 29 2020, 12:39 PM
TaWeiTu requested review of this revision.Jul 29 2020, 12:39 PM
ychen added a subscriber: ychen.Jul 29 2020, 12:46 PM
fhahn added a subscriber: fhahn.Jul 29 2020, 2:53 PM
TaWeiTu updated this revision to Diff 281881.Jul 30 2020, 4:54 AM

Fix several pre-merge checks.

TaWeiTu updated this revision to Diff 281907.Jul 30 2020, 6:18 AM

Fix LOOP_NEST_ANALYSIS macro, clang-tidy warnings. Rebase.

TaWeiTu updated this revision to Diff 281954.Jul 30 2020, 9:15 AM

Fix loop deletion and rotation tests.

TaWeiTu updated this revision to Diff 281980.Jul 30 2020, 10:49 AM
This comment was removed by TaWeiTu.
Herald added a reviewer: sstefan1. · View Herald Transcript
Herald added a reviewer: aartbik. · View Herald Transcript
Herald added a reviewer: ftynse. · View Herald Transcript
Herald added a reviewer: baziotis. · View Herald Transcript
Herald added projects: Restricted Project, Restricted Project, Restricted Project, Restricted Project, Restricted Project, Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript
TaWeiTu updated this revision to Diff 281985.Jul 30 2020, 10:53 AM
TaWeiTu removed reviewers: jdoerfert, sstefan1, DavidTruby, aartbik, ftynse, baziotis, Restricted Project.
TaWeiTu removed projects: Restricted Project, Restricted Project, Restricted Project, Restricted Project, Restricted Project, Restricted Project.

Propagate the requirement of MemorySSA from loop passes to loop nest passes.

TaWeiTu updated this revision to Diff 282145.Jul 30 2020, 11:45 PM

Fix LoopRotate/pr35210.ll (sync with commit b36c39260edcded47436f344e48f78cfbedac494).

ychen added a comment.Aug 2 2020, 10:45 PM

I think this needs unit tests like LoopPassManagerTest.cpp (in that file or a similarly named file) to demonstrate the expected behavior: the expected usage comparing with LoopPass/LoopAnalysisPass, how the adaptor is used and the invalidation interaction within its pass manager and other pass managers.

TaWeiTu updated this revision to Diff 282567.EditedAug 3 2020, 3:43 AM

Add basic unit-tests to test and demonstrate the functionality of loop-nest-pass-related infrastructure (LoopNestPassManagerTest.cpp). Still working on more tests.

I've also updated the description of the patch that contains the intended usage and more details about the implemented components.

TaWeiTu edited the summary of this revision. (Show Details)Aug 3 2020, 4:14 AM
TaWeiTu updated this revision to Diff 282706.Aug 3 2020, 1:20 PM

Add tests about invalidating the analysis results and clearing the result cache.

TaWeiTu updated this revision to Diff 282905.Aug 4 2020, 6:56 AM

Fix bug of holding dangling LoopNest references.

TaWeiTu updated this revision to Diff 284139.Aug 8 2020, 11:27 AM

Test the functionality of addNewLoopNests().
Fix LoopNestAnalysis invalidation bugs.

TaWeiTu updated this revision to Diff 284185.Aug 9 2020, 4:02 AM

Ping.

@ychen Thank you for your comment! I've added some unittests. Please let me know if there's anything unclear about the intended usage.

Hello, sorry for the late reply. I have some high-level questions

  • What are existing and future loop passes/analyses that could benefit from using LoopNestPass?
  • I'd feel more comfortable if existing loop pass/analysis managers could be extended to handle LoopNestPass, rather than have separate full-fledged managers. Implementation aside, this models the idea that loopnest is just a special kind of loop, not a fundamental different IR unit. Have you thought about the alternative design of adding new adaptors or extending existing loop managers to run/query/invalidate loopnest passes?
  • I'm not sure how common loopnest analyses are or will be? What's your opinion?

@ychen Again, thanks for your comment!

  1. Currently, LoopInterchange returns immediately if the loop is not a top-level one. The main purpose of the loop nest pass is to prevent situations like this and possibly save compiling time of uninteresting calls to run.
  2. I agree with you that it would be better if the implementation can be extended from the existing ones, and yes, I've thought about and tried to incorporate the loop nest passes into the loop pass manager. Based on the discussion with @Whitney and @etiotto on the mailing list https://lists.llvm.org/pipermail/llvm-dev/2020-July/143528.html, the loop nest passes should run on LoopNest objects. I will try to explain the necessity (in my opinion) of each component in this patch on this basis:
  • LNPMUpdater: different from LPMUpdater in what it does.
  • FunctionToLoopNestPassAdaptor: FunctionToLoopPassAdaptorwith some modifications. IMO it's less confusing to implement it separately than adding a bunch of ifs.
  • LoopNestPassManager: this one is a bit tricky. If we follow the convention that <IR>PassManager should be a <IR> pass (having the same run method that operates on the same object, LoopNest in this case), then I think it's better to implement it differently because we have to deal with the possible invalidation of LoopNest object, given the fundamental difference between LoopNest (being an analysis result) and Loop (being an IR unit). The alternative is to have it operating on Loop instead, but that will break the convention. I'm not sure whether the latter will be better, what's your opinion on that?
  • LoopNestToLoopPassAdaptor: this is to prevent loop canonicalization passes from running twice as mentioned in the patch description.

In conclusion, I think it's possible to refactor the existing components to achieve the same goal, but IMO that would probably increase the complexity and readability of these components than having a separate implementation. I'm not sure if it's the right tradeoff.

  1. The term "loop nest analyses" is just saying that they will only run on top-level loops. They are essentially the same as loop analyses. The LoopNestAnalysisManager only provides an API for getting the analysis results from the LoopNest objects. Having LOOP_NEST_ANALYSIS section in PassRegistry.def is just to distinguish between analyses that should be run on all loops and the ones that should only be run on top-level loops. I currently don't think of any loop analyses that fall into this category, though.

@ychen Again, thanks for your comment!

  1. Currently, LoopInterchange returns immediately if the loop is not a top-level one. The main purpose of the loop nest pass is to prevent situations like this and possibly save compiling time of uninteresting calls to run.

I think it would be good to convert 1 or 2 passes to use the new system and evaluate the potential benefits (reduced compile-time, better results).

Whitney added a comment.EditedAug 12 2020, 7:06 AM

Examples of existing transformations that can be benefited from LoopNestPass: LoopInterchange, LoopUnrollAndJam, LoopIdiom, LoopDistribution, ...
And their corresponding cost model analyses can be benefited from LoopNestAnalysis, e.g. LoopCacheCost.

TaWeiTu added a comment.EditedAug 18 2020, 7:27 PM

Hi @Whitney, @fhahn, @ychen, thank you all for your comments and suggestions! Sorry for the late reply.
I was trying to convert the LoopInterchange pass into a loop-nest pass. However, there seems to be no corresponding loop pass for the NPM.
Any particular reason for this?

I was trying to convert the LoopInterchange pass into a loop-nest pass. However, there seems to be no corresponding loop pass for the NPM.
Any particular reason for this?

That's true, LoopInterchange pass is not already ported to the NPM, likely because no one needed it in the NPM. Maybe you want to convert another pass to loop-nest pass as the first loop-nest pass, or you will have to port it to NPM first.

TaWeiTu updated this revision to Diff 288949.Mon, Aug 31, 8:02 AM
uenoku added a subscriber: uenoku.Mon, Aug 31, 8:21 AM
TaWeiTu added a comment.EditedWed, Sep 2, 11:20 AM

Hi, thanks for your comments and suggestions!

I've thought about the suggestion by @ychen to extend the existing LoopPassManager to handle loop-nest passes instead of having a separate LoopNestPassManager, and I've uploaded a new patch D87045 that implements the basic functionalities of running loop-nest passes in LoopPassManager.
I've also added you as reviewers to the new patch, and I will work on the follow-up patches if you think that direction is better.

Meanwhile, I'll also be working on evaluating the benefits of using loop-nest passes, as @fhahn suggested. But as far as I understand, most passes that may potentially benefit from loop-nest passes require certain algorithmic changes that incorporate the information of perfectly-nested loops provided by the LoopNest object first. So it will probably take more time to investigate those passes and convert those passes using the new facilities.