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

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

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

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

[serge-sans-paille]

llvm/include/llvm/Pass.h

216

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–334

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

[serge-sans-paille]

llvm/include/llvm/IR/LegacyPassManagers.h

333–334

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

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

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

+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

266–269

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

273

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

135 ↗

(On Diff #272705)

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

135 ↗

(On Diff #272705)

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

135 ↗

(On Diff #272705)

So why would the Changed ever be set to true?

[serge-sans-paille]

llvm/lib/Transforms/IPO/LoopExtractor.cpp

135 ↗

(On Diff #272705)

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

135 ↗

(On Diff #272705)

I see.

[mehdi_amini]

llvm/include/llvm/Pass.h

216

. 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

135 ↗

(On Diff #272705)

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

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

135 ↗

(On Diff #272705)

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

135 ↗

(On Diff #272705)

That's what I observed, yes.

[Meinersbur]

llvm/lib/Transforms/IPO/LoopExtractor.cpp

135 ↗

(On Diff #272705)

@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

135 ↗

(On Diff #272705)

@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

135 ↗

(On Diff #272705)

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/include/llvm/IR/LegacyPassManagers.h

public:
   /// AvailableAnalysis appropriately if ProcessAnalysis is true.
   void add(Pass *P, bool ProcessAnalysis = true);
 
   /// Add RequiredPass into list of lower level passes required by pass P.
   /// RequiredPass is run on the fly by Pass Manager when P requests it
   /// through getAnalysis interface.
   virtual void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass);
 
-  virtual Pass *getOnTheFlyPass(Pass *P, AnalysisID PI, Function &F);
+  virtual std::tuple<Pass *, bool> getOnTheFlyPass(Pass *P, AnalysisID PI,
+                                                   Function &F);
 
   /// Initialize available analysis information.
   void initializeAnalysisInfo() {
     AvailableAnalysis.clear();
     for (unsigned i = 0; i < PMT_Last; ++i)
       InheritedAnalysis[i] = nullptr;
   }
 

llvm/include/llvm/Pass.h

public:
   bool mustPreserveAnalysisID(char &AID) const;
 
   /// getAnalysis<AnalysisType>() - This function is used by subclasses to get
   /// to the analysis information that they claim to use by overriding the
   /// getAnalysisUsage function.
   template<typename AnalysisType>
   AnalysisType &getAnalysis() const; // Defined in PassAnalysisSupport.h
 
-  template<typename AnalysisType>
-  AnalysisType &getAnalysis(Function &F); // Defined in PassAnalysisSupport.h
+  template <typename AnalysisType>
+  AnalysisType &
+  getAnalysis(Function &F,
+              bool *Changed = nullptr); // Defined in PassAnalysisSupport.h
 
   template<typename AnalysisType>
   AnalysisType &getAnalysisID(AnalysisID PI) const;
 
-  template<typename AnalysisType>
-  AnalysisType &getAnalysisID(AnalysisID PI, Function &F);
+  template <typename AnalysisType>
+  AnalysisType &getAnalysisID(AnalysisID PI, Function &F,
+                              bool *Changed = nullptr);
 };
 
 //===----------------------------------------------------------------------===//
 /// ModulePass class - This class is used to implement unstructured
 /// interprocedural optimizations and analyses.  ModulePasses may do anything
 /// they want to the program.
 ///
 class ModulePass : public Pass {

llvm/include/llvm/PassAnalysisSupport.h

for (const auto &AnalysisImpl : AnalysisImpls) {
         ResultPass = AnalysisImpl.second;
         break;
       }
     }
     return ResultPass;
   }
 
   /// Find pass that is implementing PI. Initialize pass for Function F.
-  Pass *findImplPass(Pass *P, AnalysisID PI, Function &F);
+  std::tuple<Pass *, bool> findImplPass(Pass *P, AnalysisID PI, Function &F);
 
   void addAnalysisImplsPair(AnalysisID PI, Pass *P) {
     if (findImplPass(PI) == P)
       return;
     std::pair<AnalysisID, Pass*> pir = std::make_pair(PI,P);
     AnalysisImpls.push_back(pir);
   }
 
AnalysisType &Pass::getAnalysisID(AnalysisID PI) const {
   // AnalysisGroups), we use getAdjustedAnalysisPointer here to potentially
   // adjust the return pointer (because the class may multiply inherit, once
   // from pass, once from AnalysisType).
   return *(AnalysisType*)ResultPass->getAdjustedAnalysisPointer(PI);
 }
 
 /// getAnalysis<AnalysisType>() - This function is used by subclasses to get
 /// to the analysis information that they claim to use by overriding the
-/// getAnalysisUsage function.
-template<typename AnalysisType>
-AnalysisType &Pass::getAnalysis(Function &F) {
+/// getAnalysisUsage function. If as part of the dependencies, an IR
+/// transformation is triggered (e.g. because the analysis requires
+/// BreakCriticalEdges), and Changed is non null, *Changed is updated.
+template <typename AnalysisType>
+AnalysisType &Pass::getAnalysis(Function &F, bool *Changed) {
   assert(Resolver &&"Pass has not been inserted into a PassManager object!");
 
-  return getAnalysisID<AnalysisType>(&AnalysisType::ID, F);
+  return getAnalysisID<AnalysisType>(&AnalysisType::ID, F, Changed);
 }
 
-template<typename AnalysisType>
-AnalysisType &Pass::getAnalysisID(AnalysisID PI, Function &F) {
+template <typename AnalysisType>
+AnalysisType &Pass::getAnalysisID(AnalysisID PI, Function &F, bool *Changed) {
   assert(PI && "getAnalysis for unregistered pass!");
   assert(Resolver && "Pass has not been inserted into a PassManager object!");
   // PI *must* appear in AnalysisImpls.  Because the number of passes used
   // should be a small number, we just do a linear search over a (dense)
   // vector.
-  Pass *ResultPass = Resolver->findImplPass(this, PI, F);
+  Pass *ResultPass;
+  bool LocalChanged;
+  std::tie(ResultPass, LocalChanged) = Resolver->findImplPass(this, PI, F);
+
   assert(ResultPass && "Unable to find requested analysis info");
+  if (Changed)
+    *Changed |= LocalChanged;
 
   // Because the AnalysisType may not be a subclass of pass (for
   // AnalysisGroups), we use getAdjustedAnalysisPointer here to potentially
   // adjust the return pointer (because the class may multiply inherit, once
   // from pass, once from AnalysisType).
   return *(AnalysisType*)ResultPass->getAdjustedAnalysisPointer(PI);
 }
 
 } // end namespace llvm
 
 #endif // LLVM_PASSANALYSISSUPPORT_H

llvm/lib/IR/LegacyPassManager.cpp

public:
   /// Add RequiredPass into list of lower level passes required by pass P.
   /// RequiredPass is run on the fly by Pass Manager when P requests it
   /// through getAnalysis interface.
   void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) override;
 
   /// Return function pass corresponding to PassInfo PI, that is
   /// required by module pass MP. Instantiate analysis pass, by using
   /// its runOnFunction() for function F.
-  Pass* getOnTheFlyPass(Pass *MP, AnalysisID PI, Function &F) override;
+  std::tuple<Pass *, bool> getOnTheFlyPass(Pass *MP, AnalysisID PI,
+                                           Function &F) override;
 
   StringRef getPassName() const override { return "Module Pass Manager"; }
 
   PMDataManager *getAsPMDataManager() override { return this; }
   Pass *getAsPass() override { return this; }
 
   // Print passes managed by this manager
   void dumpPassStructure(unsigned Offset) override {
void PMDataManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
   // analysis info on demand or not.
 #ifndef NDEBUG
   dbgs() << "Unable to schedule '" << RequiredPass->getPassName();
   dbgs() << "' required by '" << P->getPassName() << "'\n";
 #endif
   llvm_unreachable("Unable to schedule pass");
 }
 
-Pass *PMDataManager::getOnTheFlyPass(Pass *P, AnalysisID PI, Function &F) {
+std::tuple<Pass *, bool> PMDataManager::getOnTheFlyPass(Pass *P, AnalysisID PI,
+                                                        Function &F) {
   llvm_unreachable("Unable to find on the fly pass");
 }
 
 // Destructor
 PMDataManager::~PMDataManager() {
   for (Pass *P : PassVector)
     delete P;
 }
 
 //===----------------------------------------------------------------------===//
 // NOTE: Is this the right place to define this method ?
 // getAnalysisIfAvailable - Return analysis result or null if it doesn't exist.
 Pass *AnalysisResolver::getAnalysisIfAvailable(AnalysisID ID, bool dir) const {
   return PM.findAnalysisPass(ID, dir);
 }
 
-Pass *AnalysisResolver::findImplPass(Pass *P, AnalysisID AnalysisPI,
-                                     Function &F) {
+std::tuple<Pass *, bool>
+AnalysisResolver::findImplPass(Pass *P, AnalysisID AnalysisPI, Function &F) {
   return PM.getOnTheFlyPass(P, AnalysisPI, F);
 }
 
 //===----------------------------------------------------------------------===//
 // FunctionPassManager implementation
 
 /// Create new Function pass manager
 FunctionPassManager::FunctionPassManager(Module *m) : M(m) {
void MPPassManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
   SmallVector<Pass *, 1> LU;
   LU.push_back(FoundPass);
   FPP->setLastUser(LU,  P);
 }
 
 /// Return function pass corresponding to PassInfo PI, that is
 /// required by module pass MP. Instantiate analysis pass, by using
 /// its runOnFunction() for function F.
-Pass* MPPassManager::getOnTheFlyPass(Pass *MP, AnalysisID PI, Function &F){
+std::tuple<Pass *, bool> MPPassManager::getOnTheFlyPass(Pass *MP, AnalysisID PI,
+                                                        Function &F) {
   FunctionPassManagerImpl *FPP = OnTheFlyManagers[MP];
   assert(FPP && "Unable to find on the fly pass");
 
   FPP->releaseMemoryOnTheFly();
-  FPP->run(F);
-  return ((PMTopLevelManager*)FPP)->findAnalysisPass(PI);
+  bool Changed = FPP->run(F);
+  return std::make_tuple(((PMTopLevelManager *)FPP)->findAnalysisPass(PI),
+                         Changed);
 }
 
-
 //===----------------------------------------------------------------------===//
 // PassManagerImpl implementation
 
 //
 /// run - Execute all of the passes scheduled for execution.  Keep track of
 /// whether any of the passes modifies the module, and if so, return true.
 bool PassManagerImpl::run(Module &M) {
   bool Changed = false;