This is an archive of the discontinued LLVM Phabricator instance.

[Polly][NewPM][WIP] Add a ScopPassManager
ClosedPublic

Authored by philip.pfaffe on Apr 26 2017, 7:32 AM.

Details

Summary

This patch adds both a ScopAnalysisManager and a ScopPassManager.

The ScopAnalysisManager is itself a Function-Analysis, and manages analyses on Scops. The ScopPassManager takes care of building Scop pass pipelines.

This patch is marked WIP because I've left two FIXMEs which I need to think about some more. Both of these deal with invalidation:

  • Deferred invalidation is currently not implemented. Deferred invalidation deals with analyses which cache references to other analysis results. If these results are invalidated, invalidation needs to be propagated into the caching analyses.
  • The ScopPassManager as implemented assumes that ScopPasses do not affect other Scops in any way. There has been some discussion about this on other patch threads, however it makes sense to reiterate this for this specific patch.

I'm uploading this patch even though it's incomplete to encourage discussion and give you an impression of how this is going to work.

Diff Detail

Event Timeline

philip.pfaffe created this revision.Apr 26 2017, 7:32 AM
Meinersbur edited edge metadata.Apr 27 2017, 7:38 AM

I don't feel confident enough to evaluate the design. I don't know the new pass manager well enough nor its design pattern. so atm I can only give a very peripheral review.

ScopAnalysisManagerFunctionProxy and FunctionToScopPassAdaptor made me think about Java for some reason :). It feels like over-engineering, but I cannot claim that it isn't the way it is supposed to be done.

include/polly/ScopInfo.h
2129

There is already getNameStr. Why the need for another one?

include/polly/ScopPass.h
9–10

double //?

36

Is it necessary to have this in the llvm namespace? Normally we should stay in our Polly namespace.

If it is necessary, doesn't it mean this should be moved to LLVM (respectively that the new pass manager is not designed for extensibility)?

lib/Analysis/ScopInfo.cpp
3216

This is more a description than a name.

lib/Analysis/ScopPass.cpp
17

Independent of what makes more sense: We use quotes to inlcude llvm headers everwhere else.

philip.pfaffe marked 3 inline comments as done.
  • Fix minor nits.
include/polly/ScopInfo.h
2129

The PassManager expects IR-Units to provide a getName() function. Constructing and returning a std::string (instead of StringRef) from this seems wasteful.

Assuming the the information used in getNameStr() to build the name doesn't change over the lifetime of the Scop, does it make sense to drop getNameStr(), store the name in the Scop itself and return that from getName()?

include/polly/ScopPass.h
36

Stylistically I agree with your concern.

However, I'm specializing members here (the run() method and the Result member class). This must happen in an enclosing namespace of the template definition.

Rebased and fixed a few small template issues.

I've added a prototype for a unittest. Right now it doesn't really test anything, but it shows how the pass manager is expected to be used. A real unittest for the invalidation paths will be complete soon.

Sorry that my updates are so slow right now, I've got zero spare time...

grosser edited edge metadata.May 8 2017, 12:39 PM

Hi Philip,

this already looks very good. I am pleased to see the overall structure written out. I understand that there are still pieces missing, but as this is nicely independent of everything else I believe we can gradually build this up in LLVM. Hence, I believe committing this already soon makes sense such that people can play and experiment with it.

Now, what would be really useful is:

  1. The ability to actually run (and test) individual passes with 'opt'
  1. The ability to run polly in -O3

I assume 2) is only possible after your patch has been accepted by Chandler. As mentioned earlier, Polly-specific #ifdefs might be a good idea to early on establish a full flow.

I am not clear what is missing for 1).

Best,
Tobias

include/polly/ScopInfo.h
1531

Newline before comment??

2129

If you believe getNameStr() could be implemented more efficiently, then we can do this. However, I would assume getName[Str]() is only called when actually dumping a scop. So eagerly constructing the name string might even have a negative effect performance wise.

I personally do not have a strong opinion if we have getNameStr or getName or if we create the name eagerly or not, until this becomes significant in any profile I see. So if you prefer one over the other I am OK with this.

However, from my perspective I would ignore likely minimal performance effects for now and just include what is needed for this patch without introducing redundancies.

include/polly/ScopPass.h
9–10

This just seems a reformatting of the original comment, without any actual changes. Can you just leave the original format and keep this part unchanged?

lib/Analysis/ScopPass.cpp
63

All passes that just work on 'Scop' should not affect other scops. However, the code generation passes have indeed the potential to affect other scops.

An option that is potentially the most savest option is add more logic into the scoppassmanager. This manager could construct one scopinfo at a time, run all scop passes (except code generation), and then does code generation itself. It then constructs the next scopingo, runs all passes, and does code generation.

This however is possibly unnecessary complicated. So my feeling is that we should ignore this for now, assume everything is safe, get test cases, and build up the flow. After we got something working, we can get test coverage and failing cases and then look into how to handle them best. My feeling is that the general structure should not change, but might just become slightly more complex. As this is independent to everything else in Polly and unlikely to regress anything, I believe we can develop this in-tree.

92

allPreserved

  1. The ability to actually run (and test) individual passes with 'opt'
  1. The ability to run polly in -O3

I assume 2) is only possible after your patch has been accepted by Chandler. As mentioned earlier, Polly-specific #ifdefs might be a good idea to early on establish a full flow.

I am not clear what is missing for 1).

  1. is tied very closely to PassBuilders ability to accept injected plugin passes, yes.

On the other hand, while it would be technically possible to forward declare the polly passes in PassBuilder (and the PassRegistry.def), that would pose a severe violation of layering, because we'd need to make lib/Passes depend on polly, both logically as well as in a build-system sense. This dependency doesn't currently exist: LLVM_LINK_POLLY_INTO_TOOLS (which would be the flag we'd #ifdef on), only affects tools. Forward declaring Polly in the PassBuilder would however pull polly dependencies into the PassBuilder.

The good news is I've talked to Chandler about this some more, and there will be progress on the Plugins patch soon!

include/polly/ScopInfo.h
2129

I'm completely in favor of lazily building the name.

That would mean initializing the name member on the first call of getName(). I didn't dare to rename getNameStr() (or, in other words, return std::string from getName()), because I can't guarantee that this function won't be called in a context where a StringRef is expected, thus creating a dangling reference to a termporary.

lib/Analysis/ScopPass.cpp
63

There is actually a rather clean way to implement this, and it's very similar to what the LoopPassManager does today. We can pass an Updater along the Scop pipeline down into CodeGeneration. Using that we can propagate ScopInfo invalidations into the ScopPassManager which can then skip now-invalid Scops. This works under two conditions:

  1. Invalidation occurs only for Scops that haven't been transformed yet. If I understand the current implementation correctly, that's condition holds.
  2. CodeGeneration actually knows which potential Scops it breaks. From the previous discussions I'm under the impression that there are only a handful of ways it does that, so it sounds like it's easily checkable. Worst case I assume the Updater would need to verify all remaining Scops.

I expect this to be a an uninvasive change. Most of the work would need to go into CodeGeneration in figuring out which Scops to skip.

  • Fix minor nits

Sorry, I should just stop using arc ...

philip.pfaffe marked 3 inline comments as done.May 11 2017, 9:22 AM

I've added an update mechanism for the Scop worklist. As discussed inline, the ScopPassManager passes a small Updater object down through the Scop pipeline. Transformation passes such as CodeGen may use this updater to inform the PM about Scops that are to be skipped because they aren't valid anymore. It is up to those passes now to figure out the correct Scops to skip.

This takes care of the remaining FIXME.

  1. The ability to actually run (and test) individual passes with 'opt'
  1. The ability to run polly in -O3

I assume 2) is only possible after your patch has been accepted by Chandler. As mentioned earlier, Polly-specific #ifdefs might be a good idea to early on establish a full flow.

I am not clear what is missing for 1).

  1. is tied very closely to PassBuilders ability to accept injected plugin passes, yes.

On the other hand, while it would be technically possible to forward declare the polly passes in PassBuilder (and the PassRegistry.def), that would pose a severe violation of layering, because we'd need to make lib/Passes depend on polly, both logically as well as in a build-system sense. This dependency doesn't currently exist: LLVM_LINK_POLLY_INTO_TOOLS (which would be the flag we'd #ifdef on), only affects tools. Forward declaring Polly in the PassBuilder would however pull polly dependencies into the PassBuilder.

The good news is I've talked to Chandler about this some more, and there will be progress on the Plugins patch soon!

I see.

I think that patch looks good to me so far. (Similar to the other two). They certainly go into the right direction and they are almost 100% independent of Polly. I think it makes sense to commit them to Polly already today facilitate further testing. After this has happened, you could already work on a patch that registers the Polly passes (using the new pass manager plugin). If we happen to have time, we could then already run Polly once with the new pass manager on the LLVM test suite and possibly even discuss the results next week. ;)

include/polly/ScopInfo.h
2129

Ah, OK. I now realize that returning a std::string is not only wasteful, but might indeed result in memory corruption. In this case, let's just use the approach you propose. No need to over-optimize with lazy initialization.

lib/Analysis/ScopInfo.cpp
3216

I agree with Michael here. Can we drop the "Scop for region "?

lib/Analysis/ScopPass.cpp
63

I am not certain it will be easy to know which scops have been invalidate. Anyway, the best will likely be to just commit this baseline implementation, run the LLVM test suite and see if or what is failing, if at all.

  • Fixed the updater (Analyses don't care)
  • Clean up the testcase a bit (i.e., made it compile based on the patch)
  • Removed sugar from the Scop name
philip.pfaffe marked 2 inline comments as done.May 12 2017, 8:32 AM
grosser accepted this revision.May 13 2017, 2:43 AM
This revision is now accepted and ready to land.May 13 2017, 2:43 AM

It seems you forgot to commit the unit tests. Also, please update the commit message in the future.

Yes, I noticed that. I fixed it in rL303064. I saw your rL303066, was that to appease the buildbots and we hit a race condition? Or was that to fix the failing build in http://lab.llvm.org:8011/builders/polly-amd64-linux/builds/6821/ ?

Sorry about the noise!

I tried to fix the buildbots. Can you fix it if I broke something?

You didn't break anything, it's a CMake issue (looks like I missed adding an LLVM library dependency). Will fix.