This is an archive of the discontinued LLVM Phabricator instance.

[LoopNest] Handle loop-nest passes in LoopPassManager
ClosedPublic

Authored by TaWeiTu on Sep 2 2020, 10:14 AM.

Details

Summary

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

This patch extends the functionality of LoopPassManager to handle loop-nest passes by specializing the definition of LoopPassManager that accepts both kinds of passes in addPass.

Only loop passes are executed if L is not a top-level one, and both kinds of passes are executed if L is top-level. Currently, loop nest passes should have the following run method:

PreservedAnalyses run(LoopNest &, LoopAnalysisManager &, LoopStandardAnalysisResults &, LPMUpdater &);

Diff Detail

Event Timeline

TaWeiTu created this revision.Sep 2 2020, 10:14 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 2 2020, 10:14 AM
TaWeiTu requested review of this revision.Sep 2 2020, 10:14 AM
TaWeiTu edited the summary of this revision. (Show Details)Sep 2 2020, 10:19 AM
TaWeiTu updated this revision to Diff 289516.Sep 2 2020, 10:59 AM
TaWeiTu edited the summary of this revision. (Show Details)Sep 2 2020, 11:03 AM
TaWeiTu updated this revision to Diff 289670.Sep 3 2020, 2:47 AM

Add unit test.

ychen added a comment.Sep 4 2020, 10:12 AM

Thank you for the patch. I'll take a look over the weekend.

TaWeiTu updated this revision to Diff 289999.Sep 4 2020, 11:15 AM
etiotto added inline comments.Sep 9 2020, 10:44 AM
llvm/include/llvm/Transforms/Scalar/LoopPassManager.h
66

Not sure if you can use an anonymous namespace

llvm/lib/Transforms/Scalar/LoopPassManager.cpp
28

Suggest:

PreservedAnalyses PA = (!L.getParentLoop() && !LoopNestPasses.empty()) 
                                       ? runWithLoopNestPasses(L, AM, AR, U)
                                       : runWithoutLoopNestPasses(L, AM, AR, U);

That way PA is initialized where it is declared.

52

assert L is the outermost loop (no parent loop).

66

This isn't that clear, perhaps use something like !isa<LoopNestPass>(Pass) ?

133

Is not immediately clear what is the type of PassPA. Could you use the explicit type Optional<PreservedAnalyses> ?

llvm/unittests/Transforms/Scalar/LoopPassManagerTest.cpp
1605

HandleLoopNestPass isn't used. How does this test work?

Whitney added inline comments.Sep 9 2020, 10:50 AM
llvm/include/llvm/Transforms/Scalar/LoopPassManager.h
160

Do you think is a good idea to rename PassCategories to IsLoopNestPass?

161

can we use llvm data structures here?

ychen added a comment.Sep 9 2020, 12:55 PM
  • How about using PreservedAnalyses run(Loop &, LoopAnalysisManager &, LoopStandardAnalysisResults &, LPMUpdater &, LoopNest &); for the interface. I think it should work better because it is still a loop pass interface.
  • Add a test case for PassInstrument?
llvm/include/llvm/Transforms/Scalar/LoopPassManager.h
68

There is is_detected in STLExtras.h that could simplify this. It is fine putting this in the PassManager itself.

TaWeiTu updated this revision to Diff 290810.Sep 9 2020, 12:58 PM

Address (some) code review comments.

TaWeiTu marked 5 inline comments as done.Sep 9 2020, 1:04 PM
TaWeiTu added inline comments.
llvm/include/llvm/Transforms/Scalar/LoopPassManager.h
161

Since this is a specialized version of PassManager and PassManager uses std::vector instead of the LLVM data structures, I'm not sure which one is better here.

llvm/unittests/Transforms/Scalar/LoopPassManagerTest.cpp
1605

I'm not sure what this means actually because I suppose this is how GoogleTest works and the test does run. Do you mean that I should add some comments to illustrate what functionality is the unittest testing?

TaWeiTu updated this revision to Diff 290820.Sep 9 2020, 1:30 PM

Replace SFINAE helper with llvm::is_detected.

TaWeiTu marked an inline comment as done.Sep 9 2020, 1:30 PM
TaWeiTu updated this revision to Diff 290961.Sep 10 2020, 6:46 AM

Add PassInstrumentation callback tests.

TaWeiTu updated this revision to Diff 290962.Sep 10 2020, 6:47 AM
  • How about using PreservedAnalyses run(Loop &, LoopAnalysisManager &, LoopStandardAnalysisResults &, LPMUpdater &, LoopNest &); for the interface. I think it should work better because it is still a loop pass interface.

Sounds like a good idea to me. Let' see what @Whitney and @etiotto think about the new interface first, and I'll update the patch later if they agree on that. Thanks!

Whitney added inline comments.Sep 10 2020, 7:02 AM
llvm/include/llvm/Transforms/Scalar/LoopPassManager.h
161

In that case, I agree not to change.

TaWeiTu updated this revision to Diff 291012.Sep 10 2020, 10:07 AM
TaWeiTu updated this revision to Diff 291044.Sep 10 2020, 11:48 AM
TaWeiTu added inline comments.Sep 15 2020, 6:02 AM
llvm/lib/Transforms/Scalar/LoopPassManager.cpp
66

Hi, thanks for the suggestion! Do you think it's clear enough now after renaming it to IsLoopNestPass?

Gentle ping to @Whitney and @etiotto on the opinion about the new interface for loop-nest pass suggested above. Thanks!

  • How about using PreservedAnalyses run(Loop &, LoopAnalysisManager &, LoopStandardAnalysisResults &, LPMUpdater &, LoopNest &); for the interface. I think it should work better because it is still a loop pass interface.

Sounds like a good idea to me. Let' see what @Whitney and @etiotto think about the new interface first, and I'll update the patch later if they agree on that. Thanks!

I am not strongly against it, however is not clear to me what the extra argument Loop & provide, as we can get the loop from LoopNest & by LN.getOutermostLoop().

TaWeiTu added a comment.EditedSep 15 2020, 7:34 AM
  • How about using PreservedAnalyses run(Loop &, LoopAnalysisManager &, LoopStandardAnalysisResults &, LPMUpdater &, LoopNest &); for the interface. I think it should work better because it is still a loop pass interface.

Sounds like a good idea to me. Let' see what @Whitney and @etiotto think about the new interface first, and I'll update the patch later if they agree on that. Thanks!

I am not strongly against it, however is not clear to me what the extra argument Loop & provide, as we can get the loop from LoopNest & by LN.getOutermostLoop().

Thanks for your comment!
I think the benefit of the new interface is that it shows that the loop-nest pass is just a special case of loop pass that provides an additional LoopNest object.
However, I think your concern about passing redundant parameters to the function is also valid.
Both interfaces seem equally good for me actually, and I don't have any preference for either of them.

I think maybe we can stick to the current interface for now (unless @ychen has a strong preference for the other one) and update it in the future if necessary.
Any thoughts?

By the way, is there any other concern regarding this patch other than the interface now?

Thanks again for all your review and time.

Gentle ping.

Whitney accepted this revision.Sep 29 2020, 9:20 AM

Thanks for working on it! Are you planning to change one of the LoopPass to a LoopNestPass next?

This revision is now accepted and ready to land.Sep 29 2020, 9:20 AM

Thanks for working on it! Are you planning to change one of the LoopPass to a LoopNestPass next?

Sure! I'm planning to port LoopInterchange to NPM as a LoopNestPass first in the future.

From http://llvm.org/OpenProjects.html#llvm_loopnest, it was mentioned that
"If you decide to write it as a loop pass, then you are wasting compile time to traverse to your pass and return right away when the given loop is not the outermost loop."

Taking another look at the overall approach of this patch: currently for all loops (top-level or nested) in a function, when encountering a loop nest pass in LPM, a LoopNest is calculated and the loop nest pass is called with the computed LoopNest. Does this help compile-time in practice? It feels like it is essentially a loop pass that got passed a LoopNest as an incoming parameter that could be equally implemented (without this patch) with a normal loop pass that computes LoopNest by itself? This seems does not solve the problem quoted above.

To achieve that, I think we need to change FunctionToLoopPassAdaptor to dispatch top-level loops (aside from to regular loops and LPMs) to a LoopNestPassManager managing only loop nest passes or a loop nest pass directly.

From http://llvm.org/OpenProjects.html#llvm_loopnest, it was mentioned that
"If you decide to write it as a loop pass, then you are wasting compile time to traverse to your pass and return right away when the given loop is not the outermost loop."

Taking another look at the overall approach of this patch: currently for all loops (top-level or nested) in a function, when encountering a loop nest pass in LPM, a LoopNest is calculated and the loop nest pass is called with the computed LoopNest. Does this help compile-time in practice? It feels like it is essentially a loop pass that got passed a LoopNest as an incoming parameter that could be equally implemented (without this patch) with a normal loop pass that computes LoopNest by itself? This seems does not solve the problem quoted above.

To achieve that, I think we need to change FunctionToLoopPassAdaptor to dispatch top-level loops (aside from to regular loops and LPMs) to a LoopNestPassManager managing only loop nest passes or a loop nest pass directly.

If I understood correctly, I think the follow-up patch D87531 is designed to address the issue.
Specifically, in FunctionToLoopPassAdaptor, if the input pass is a loop pass or an LPM containing both loop passes and loop-nest passes, all loops in the function have to be processed regardless if they're top-level or not.
On the other hand, if the input pass is a loop-nest pass or is an LPM containing only loop-nest passes, only top-level loops are sent to the worklist and processed.

Does this solve the problem you mentioned? Thanks!

ychen accepted this revision.Sep 29 2020, 4:53 PM

From http://llvm.org/OpenProjects.html#llvm_loopnest, it was mentioned that
"If you decide to write it as a loop pass, then you are wasting compile time to traverse to your pass and return right away when the given loop is not the outermost loop."

Taking another look at the overall approach of this patch: currently for all loops (top-level or nested) in a function, when encountering a loop nest pass in LPM, a LoopNest is calculated and the loop nest pass is called with the computed LoopNest. Does this help compile-time in practice? It feels like it is essentially a loop pass that got passed a LoopNest as an incoming parameter that could be equally implemented (without this patch) with a normal loop pass that computes LoopNest by itself? This seems does not solve the problem quoted above.

To achieve that, I think we need to change FunctionToLoopPassAdaptor to dispatch top-level loops (aside from to regular loops and LPMs) to a LoopNestPassManager managing only loop nest passes or a loop nest pass directly.

If I understood correctly, I think the follow-up patch D87531 is designed to address the issue.

ha, thanks. I missed this one.

Specifically, in FunctionToLoopPassAdaptor, if the input pass is a loop pass or an LPM containing both loop passes and loop-nest passes, all loops in the function have to be processed regardless if they're top-level or not.
On the other hand, if the input pass is a loop-nest pass or is an LPM containing only loop-nest passes, only top-level loops are sent to the worklist and processed.

Could you please add comments about this either before LPM or before FunctionToLoopPassAdaptor? It is helpful for understanding the code.

Does this solve the problem you mentioned? Thanks!

Yes, totally.

LGTM. Please hold off a bit in case @asbirlea wants to chime in.

TaWeiTu updated this revision to Diff 295164.Sep 29 2020, 8:00 PM

Rebased on top of the current master.

@Whitney, @ychen thanks for the review! Comments regarding loop/loop-nest mode and when they're used have be added to D87531.

TaWeiTu updated this revision to Diff 296122.Oct 5 2020, 2:20 AM

Hi @Whitney, @ychen, if the patches are ready to land, could you do me a favor of committing this as well as the follow-up D87531 (with --author="Ta-Wei Tu <tu.da.wei@gmail.com>)?
Thanks in advance!

The design looks good, but I'd like to see more comments documenting some of the details for future code readers.
e.g. document the Optional<PreservedAnalysis> as including the test for skipped passes in that single function call (this is new behavior vs other implementations), document the addPass specializations and populating IsLoopNestPass.

@asbirlea Sure! Thanks for the review, I will update the patch later.

TaWeiTu updated this revision to Diff 296370.Oct 6 2020, 12:11 AM

Add documentation regarding Optional<PreservedAnalyses> and the specializations of addPass.

Hi @Whitney, @ychen, if the patches are ready to land, could you do me a favor of committing this as well as the follow-up D87531 (with --author="Ta-Wei Tu <tu.da.wei@gmail.com>)?
Thanks in advance!

Sure. Let's see if @asbirlea is happy with it.

TaWeiTu updated this revision to Diff 298987.Oct 19 2020, 3:26 AM

Ping. @asbirlea is there any concern regarding this patch and the follow-up D87531 (both the code and the documentation)?
Thanks!

Ping.
If there's no objection about these patches I'll commit them in a few days.
Thanks for the reviews!

No objections.

TaWeiTu updated this revision to Diff 305661.Nov 16 2020, 10:44 PM

Rebased and fix tests

Whitney accepted this revision.Nov 18 2020, 11:59 AM

If there's no objection about these patches I'll commit them in a few days.

@TaWeiTu Are you committing this change?

This revision was landed with ongoing or failed builds.Dec 16 2020, 9:07 AM
This revision was automatically updated to reflect the committed changes.

If there's no objection about these patches I'll commit them in a few days.

@TaWeiTu Are you committing this change?

Been quite busy recently and totally forgot about it.
Thanks for committing it!

opps...forgot to deliver with --author="Ta-Wei Tu <tu.da.wei@gmail.com>.