Improve LegacyPassManager API to correctly report modified status

[serge-sans-paille]

Summary

Related to https://reviews.llvm.org/D80916

When calling on-the-fly passes from the legacy pass manager, the modification status is not reported, which is a problem in case we depend on an acutal transformation pass, and not only analyse.

Update the Legacy PM API to optionally report the changed status, assert if a change is detected but this change is lost.

Use that API for LoopExtractor where it's mandatory to pass the validation.

[ekatz]

There seems to be a more profound bug underneath.
Is this how every pass that use LoopInfo handle it?
It seems like the real issue is with LoopInfo - an analysis shouldn't do a transformation.

[jdoerfert]

In D81236#2075905, @ekatz wrote:

It seems like the real issue is with LoopInfo - an analysis shouldn't do a transformation.

Agreed. I tried to find out where LoopInfoWrapperPass would do this but I didn't spot it right away. @serge-sans-paille do you know where the modification happens or do you happen to have the reproducer?

[serge-sans-paille]

Agreed. I tried to find out where LoopInfoWrapperPass would do this but I didn't spot it right away. @serge-sans-paille do you know where the modification happens or do you happen to have the reproducer?

I investigated, and BreakCriticalEdges is a dependency of LoopExtractor, and it's the pass that triggers the change. I supsect LoopSimplify, another analysis dep, has the same impact.
I don't understand where passes marked as dependency register their change status...

[serge-sans-paille]

It looks like a limitation of the PM to me, I wonder what's the best approach there... Maybe just a big inline comment, that's gonna be removed once LegacyPM goes out?

[ekatz]

In D81236#2082487, @serge-sans-paille wrote:

I investigated, and BreakCriticalEdges is a dependency of LoopExtractor, and it's the pass that triggers the change.

This makes more sense. Every pass (in our case - BreakCriticalEdges) is responsible for reporting to the PM about the preserved (and non preserved) analyses.
I am not sure, what bug are you trying to tackle?
In case the LoopExtractor does nothing, it will report that all analyses are preserved, but the preceding call to BreakCriticalEdges will (and if it doesn't - it should) already report the non preserved analyses.
I guess, what you didn't expect is the fact that running the LoopExtractor will trigger BreakCriticalEdges, but although it may be a strange/ugly behavior, it is still valid.

Maybe a better implementation will be - calling BreakCriticalEdges as a utility from inside LoopExtractor. Consider what should be done to adapt this pass to the new PM?

[jdoerfert]

In case the LoopExtractor does nothing, it will report that all analyses are preserved, but the preceding call to BreakCriticalEdges will (and if it doesn't - it should) already report the non preserved analyses.

This is the critical part. Does BreakCriticalEdges report a modification, if so the PM should be aware and it might be a PM bug, if not it is a BreakCriticalEdges bug. The user, here LoopExtractor, doesn't modify, so it should not check if a requirement did (as that is in general impossible).

[serge-sans-paille]

Try another approach and fix the fact that the return status of a lazy transformation is simply ignored.

[serge-sans-paille]

The legacy pass manager on-the-fly computation isn't meant to report status, which is the origin of the error this patch is trying to fix. Make that more explicit through member function renaming.

[foad]

Makes sense to me, but I don't understand what the implications might be. For example, this pass will now unconditionally run a LoopSimplify pass. Previously could it have relied on an earlier LoopSimplify run, if all the intervening passes "preserved" LoopSimplify?

To put it another way: does this patch slow down the compiler? And/or does it add more passes to the list reported by -debug-pass=Structure, for a typical compile?

[serge-sans-paille]

Improve the approach by updating the pass manager API to allow to get the pass return status when computing a Lazy analysis.

[serge-sans-paille]

In D81236#2101504, @serge-sans-paille wrote:

Improve the approach by updating the pass manager API to allow to get the pass return status when computing a Lazy analysis.

@foad / @jdoerfert if the approach looks fine, I'll update other passes that have the same issue.

[jdoerfert]

LGTM. Thanks for this general solution to the problem :)

[fhahn]

It would be good to explain the pass manager changes in the description (or maybe even better to submit separately)

[ekatz]

This change should be split into 2.
One for the PM changes and the other for the LoopExtractor (that depend on the previous change).
Regardless, the changes in the PM should be reviewed by more people...

[jdoerfert]

In D81236#2101822, @ekatz wrote:

This change should be split into 2.
One for the PM changes and the other for the LoopExtractor (that depend on the previous change).

Fair.

Regardless, the changes in the PM should be reviewed by more people...

Do you have someone in mind? Or would you just want to wait?

[ekatz]

In D81236#2101924, @jdoerfert wrote:

Do you have someone in mind? Or would you just want to wait?

Not sure if waiting would help much, if we don't add new reviewers. Perhaps add @chandlerc , @rnk , @lattner , @mehdi_amini, @asbirlea, and maybe others who worked on these files (if needed).

[jdoerfert]

In D81236#2102491, @ekatz wrote:

In D81236#2101924, @jdoerfert wrote:

Do you have someone in mind? Or would you just want to wait?

Not sure if waiting would help much, if we don't add new reviewers.

That was the reason I asked ;)

Perhaps add @chandlerc , @rnk , @lattner , @mehdi_amini, @asbirlea, and maybe others who worked on these files (if needed).

[serge-sans-paille]

@ekatz I've updated the review title description to better reflect what it actually does. I've kept the review as a single bug to better showcase the usage, but once accepted I'll split it in two commits.

@mehdi_amini any thoughts on that one?

[mehdi_amini]

llvm/include/llvm/Pass.h

216 ↗

(On Diff #271749)

Can you document these added arguments?
It isn't clear to me what are these about: I wouldn't expect an analysis to change the IR for example.

[serge-sans-paille]

Update docstring

[serge-sans-paille]

llvm/include/llvm/Pass.h

216 ↗

(On Diff #271749)

Will do. That's all the salt of this review: an analysis may trigger, as part of its dependencies, a pass that modifies the IR. This modification is currently ignored when computing on-the-fly passes.

[mehdi_amini]

llvm/include/llvm/Pass.h

216 ↗

(On Diff #271749)

Do you have examples of it? (if so maybe add them to the comment)

[serge-sans-paille]

llvm/include/llvm/Pass.h

216 ↗

(On Diff #271749)

Yeah, LoopExtractor depends on BreakCriticalEdges. I'll add that to the comment.

[serge-sans-paille]

Update docstring according to reviews

[nikic]

llvm/include/llvm/IR/LegacyPassManagers.h

333 ↗

(On Diff #272011)

Just wondering, why std::tuple rather than std::pair?

[serge-sans-paille]

llvm/include/llvm/IR/LegacyPassManagers.h

333 ↗

(On Diff #272011)

Because I find std::get<bool>(PassStatus) easier to read than std::get<1>(PassStatus) or PassStatus.second. No strong opinion here though :-)

[mehdi_amini]

llvm/include/llvm/Pass.h

216 ↗

(On Diff #271749)

Is this intended to work though? What about the new pass manager? Do we support analysis depending on IR transformations?

[jdoerfert]

llvm/include/llvm/Pass.h

216 ↗

(On Diff #271749)

LoopExtractor is not an analysis but a transformation. In lib/Analysis there is no occurrence of addRequiredID, in lib/Transforms there are 11 files. This is the common way to depend on IR transformations (I'd argue it is intended to work). The need in the new PM is reduced as most of these things depend on loop-simplify and lcssa, both provided implicitly by the new PM loop wrapper pass (I think). The other uses cases seem to not have a new PM implementation yet.

[serge-sans-paille]

llvm/include/llvm/Pass.h

216 ↗

(On Diff #271749)

+1 @jdoerfert It's even explicitly mentioned in https://github.com/llvm/llvm-project/blob/master/llvm/include/llvm/Transforms/Utils.h#L68

[serge-sans-paille]

Up? This looks in pretty good shape to me.

[foad]

If we're happy that getAnalysis can cause changes, and we don't want to update all callers of getAnalysis to expect a std::pair<AnalysisType &, bool> result, then your changes look good to me.

llvm/include/llvm/PassAnalysisSupport.h

265 ↗

(On Diff #272011)

How about std::tie(Pass, Changed) = findImplPass(...) to avoid the use of std::get ?

271 ↗

(On Diff #272011)

I'd find else assert(!std::get<bool>(PassStatus) && "...") easier to understand.

[serge-sans-paille]

Address @foad remarks

[jdoerfert]

In D81236#2108372, @foad wrote:

If we're happy that getAnalysis can cause changes,

I think this is the existing behavior and I'm reluctant to define it after years to be invalid without a really good reason (and it's the old PM so it might not be worth it).

and we don't want to update all callers of getAnalysis to expect a std::pair<AnalysisType &, bool> result, then your changes look good to me.

If we assume >95% not using the ID version to get a transformation, I think this is less churn for upstream and downstream users.

[serge-sans-paille]

I think this is the existing behavior and I'm reluctant to define it after years to be invalid without a really good reason (and it's the old PM so it might not be worth it).

It is the existing behavior and it's actively used.

and we don't want to update all callers of getAnalysis to expect a std::pair<AnalysisType &, bool> result, then your changes look good to me.

If we assume >95% not using the ID version to get a transformation, I think this is less churn for upstream and downstream users.

That was my initial idea.

[serge-sans-paille]

@ekatz any thoughts on this version?

[ekatz]

llvm/lib/Transforms/IPO/LoopExtractor.cpp

136

Maybe I am missing something, but isn't LoopExtractor dependent on BreakCriticalEdges? I mean, what are the transformations that the LoopInfo analysis depends on?

[jdoerfert]

llvm/lib/Transforms/IPO/LoopExtractor.cpp

136

what are the transformations that the LoopInfo analysis depends on?

No transformations:

void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {                                                                                                                                              
  AU.setPreservesAll();
  AU.addRequiredTransitive<DominatorTreeWrapperPass>();
}

[ekatz]

llvm/lib/Transforms/IPO/LoopExtractor.cpp

136

So why would the Changed ever be set to true?

[serge-sans-paille]

llvm/lib/Transforms/IPO/LoopExtractor.cpp

136

It's set to True because of the on the fly pass evaluation: asking for LoopInfo triggers the whole dependencies, including BreakCriticalEdges. That's why the API change I propose only impacts on the fly passes.

[ekatz]

I admit, I don't like this change. This is a work around a design flaw in the old PM. However, it seems like the right decision to handle it, right now.
I think we should post a RFC for a new - *cough* - PM... ;)

LGTM, but please separate the patch into two: the PM related; and the LoopExtractor.

llvm/lib/Transforms/IPO/LoopExtractor.cpp

136

I see.

[mehdi_amini]

llvm/include/llvm/Pass.h

216 ↗

(On Diff #271749)

. This is the common way to depend on IR transformations (I'd argue it is intended to work)

Right, so my memory of the old pass manager is that you indeed declare dependencies ahead of time, like the comment Serge is pointing at:

AU.addRequiredID(BreakCriticalEdgesID);

However what we have here is that after a transformation started (LoopExtractor::runOnModule(Module &M)) we need an *analysis* and we call getAnalysis.

It seems strange to me that a call to getAnalysis is *transforming* the IR in the middle of the pass here.

[mehdi_amini]

llvm/lib/Transforms/IPO/LoopExtractor.cpp

136

What is "on the fl pass evaluation" in this context? I'm missing why BreakCriticalEdges isn't triggered before LoopExtractor::runOnFunction invocation?

[jdoerfert]

llvm/include/llvm/Pass.h

216 ↗

(On Diff #271749)

It seems strange to me that a call to getAnalysis is *transforming* the IR in the middle of the pass here.

I'm not saying it is particularly sane. TBH, I *really hope* this is a temporary fix for an end-of-life part of the code base. Requiring major changes to the old-PM seems both unreasonable and dangerous too me. Just ignoring this is also not a great option. This patch gives us a reasonable way to deal with this "feature" of the old-PM.

[ekatz]

llvm/lib/Transforms/IPO/LoopExtractor.cpp

136

To add to your question, just to make sure I understand it correctly- if getAnalysis was never called, then BreakCriticalEdges wasn't either?

[serge-sans-paille]

llvm/lib/Transforms/IPO/LoopExtractor.cpp

136

That's what I observed, yes.

[Meinersbur]

llvm/lib/Transforms/IPO/LoopExtractor.cpp

136

@mehdi_amini "On the fly" is a workaround for the legacy pass manager where coarser grain passes (here: ModulePass) cannot depend on finer-grain passes (here: FunctionPass).

Usually, the legacy pass manager would call all dependency passes before the pass itself, such that dependency pass'es runOnFunction is called be the PassManager, and receives the Changed status of that dependency.
When a ModulePass requests a FunctionPass analysis, the PassManager will not have called it in advance, but it will call it during getAnalsysis(). If that analysis modifies the IR, the changed status was not propagated up the PassManager stack, in this case the MPPassManager.

Since the getOnTheFlyPass is actually a method of MPPassManager, Changed in MPPassManager::runOnModule could also me made a field which getOnTheFlyPass sets to true if FPP->run(F) returns and we would not have to propagate the Changes status though method arguments.

@serge-sans-paille Did you actually consider such an alternative design?

[serge-sans-paille]

llvm/lib/Transforms/IPO/LoopExtractor.cpp

136

@Meinersbur the whole *Changed* stuff is not state-based, so I naturally choose that path. And I'd favor it anyway, as it's more explicit. But that's not a strong opinion.

[jdoerfert]

FWIW, I prefer this strongly over a "state" approach if everything else is equal.

[plotfi]

Just an FYI, PassAnalysisSupport.h is missing an #include <tuple>. Landed the addition in https://github.com/llvm/llvm-project/commit/c918c1a91a03f612c1b1e81b82460fbf80fc592a

[mehdi_amini]

llvm/lib/Transforms/IPO/LoopExtractor.cpp

136

Thanks @Meinersbur ; this is great explanation!
@serge-sans-paille can you capture this in the comment describing the getAnalysis() interface you changed? (or point to a doc if this is documented somewhere)

Also it wasn't obvious to me that this was a module pass (the method is called runOnFunction here, and I didn't check the declaration in the class to see that it wasn't an override).

llvm/lib/Transforms/IPO/LoopExtractor.cpp

 bool LoopExtractor::runOnFunction(Function &F) {
   // Do not modify `optnone` functions.
   if (F.hasOptNone())
     return false;
 
   if (F.empty())
     return false;
 
+  unsigned BBCount = F.size();
   LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>(F).getLoopInfo();
 
+  // This is only needed because of a violation of the analysis contract:
+  // LoopInfoWrapperPass normalizes the loop which may lead to code change
+  bool Modified = BBCount != F.size();
+
   // If there are no loops in the function.
   if (LI.empty())
-    return false;
+    return Modified;
 
   DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
 
   // If there is more than one top-level loop in this function, extract all of
   // the loops.
   if (std::next(LI.begin()) != LI.end())
-    return extractLoops(LI.begin(), LI.end(), LI, DT);
+    return Modified | extractLoops(LI.begin(), LI.end(), LI, DT);
+
 
   // Otherwise there is exactly one top-level loop.
   Loop *TLL = *LI.begin();
 
   // If the loop is in LoopSimplify form, then extract it only if this function
   // is more than a minimal wrapper around the loop.
   if (TLL->isLoopSimplifyForm()) {
     bool ShouldExtractLoop = false;
if (!isa<BranchInst>(EntryTI) ||
       for (auto *ExitBlock : ExitBlocks)
         if (!isa<ReturnInst>(ExitBlock->getTerminator())) {
           ShouldExtractLoop = true;
           break;
         }
     }
 
     if (ShouldExtractLoop)
-      return extractLoop(TLL, LI, DT);
+      return Modified | extractLoop(TLL, LI, DT);
   }
 
   // Okay, this function is a minimal container around the specified loop.
   // If we extract the loop, we will continue to just keep extracting it
   // infinitely... so don't extract it. However, if the loop contains any
   // sub-loops, extract them.
-  return extractLoops(TLL->begin(), TLL->end(), LI, DT);
+  return Modified | extractLoops(TLL->begin(), TLL->end(), LI, DT);
 }
 
 bool LoopExtractor::extractLoops(Loop::iterator From, Loop::iterator To,
                                  LoopInfo &LI, DominatorTree &DT) {
   bool Changed = false;
   SmallVector<Loop *, 8> Loops;
 
   // Save the list of loops, as it may change.