[LPM] A targeted but somewhat horrible fix to the legacy pass manager's querying of the pass registry.

[chandlerc]

Summary

The pass manager relies on the static registry of PassInfo objects to
perform all manner of its functionality. I don't understand why it does
much of this. My very vague understanding is that this registry is
touched both during static initialization *and* while each pass is being
constructed. As a consequence it is hard to make accessing it not
require a acquiring some lock. This lock ends up in the hot path of
setting up, tearing down, and invaliditing analyses in the legacy pass
manager.

On most systems you can observe this as a non-trivial % of the time
spent in 'ninja check-llvm'. However, I haven't really seen it be more
than 1% in extreme cases of compiling more real-world software,
including LTO.

Unfortunately, some of the GPU JITs are seeing this taking essentially
all of their time because they have very small IR running through
a small pass pipeline very many times (at least, this is the vague
understanding I have of it).

This patch tries to minimize the cost of looking up PassInfo objects by
leveraging the fact that the objects themselves are immutable and they
are allocated separately on the heap and so don't have their address
change. It also requires a change I made the last time I tried to debug
this problem which removed the ability to de-register a pass from the
registry. This patch creates a single access path to these objects
inside the PMTopLevelManager which memoizes the result of querying the
registry. This is somewhat gross as I don't really know if
PMTopLevelManager is the *right* place to put it, and I dislike using
a mutable member to memoize things, but it seems to work.

For long-lived pass managers this should completely eliminate
the cost of acquiring locks to look into the pass registry once the
memoized cache is warm. For 'ninja check' I measured about 10% reduction
in CPU time, and about a 1% reduction in total time on a machine with 32
hardware threads. For normal compilation, I don't know how much this
will help, sadly. We will still pay the cost while we populate the
memoized cache. I don't think it will hurt though, and for LTO or
compiles with many small functions it should still be a win.

[resistor]

Hi Chandler,

In my measurements, this captures about half of the regression, i.e. the regression goes from ~20% to ~10%. While the reader/writer locks are gone from the profile, several other PassManager related pieces of code have jumped up to take their place:

—Owen

• ThreadProfile2.png80 KBDownload

[chandlerc]

To summarize the discussion on IRC:

This hot code path doesn't really seem to be due to my patch. If it is, I
can't explain why. I definitely can't explain why without some steps to
reproduce.

This patch essentially erases all the performance hits I can find any way
to measure of the pthread locks, so I'll wait for more information from you
or the others that have measured more significant issues here. Let me know
what you'd like me to do next.

llvm/trunk/include/llvm/IR/LegacyPassManagers.h

public:
   /// Collect passes whose last user is P
   void collectLastUses(SmallVectorImpl<Pass *> &LastUses, Pass *P);
 
   /// Find the pass that implements Analysis AID. Search immutable
   /// passes and all pass managers. If desired pass is not found
   /// then return NULL.
   Pass *findAnalysisPass(AnalysisID AID);
 
+  /// Retrieve the PassInfo for an analysis.
+  const PassInfo *findAnalysisPassInfo(AnalysisID AID) const;
+
   /// Find analysis usage information for the pass P.
   AnalysisUsage *findAnalysisUsage(Pass *P);
 
   virtual ~PMTopLevelManager();
 
   /// Add immutable pass and initialize it.
   inline void addImmutablePass(ImmutablePass *P) {
     P->initializePass();
private:
   // This inverse map is initialized at PM->run() based on
   // LastUser map.
   DenseMap<Pass *, SmallPtrSet<Pass *, 8> > InversedLastUser;
 
   /// Immutable passes are managed by top level manager.
   SmallVector<ImmutablePass *, 16> ImmutablePasses;
 
   DenseMap<Pass *, AnalysisUsage *> AnUsageMap;
+
+  /// Collection of PassInfo objects found via analysis IDs and in this top
+  /// level manager. This is used to memoize queries to the pass registry.
+  /// FIXME: This is an egregious hack because querying the pass registry is
+  /// either slow or racy.
+  mutable DenseMap<AnalysisID, const PassInfo *> AnalysisPassInfos;
 };
 
 
 
 //===----------------------------------------------------------------------===//
 // PMDataManager
 
 /// PMDataManager provides the common place to manage the analysis data

llvm/trunk/lib/IR/LegacyPassManager.cpp

void PMTopLevelManager::schedulePass(Pass *P) {
   // may be inserted into previous function manager
 
   // Give pass a chance to prepare the stage.
   P->preparePassManager(activeStack);
 
   // If P is an analysis pass and it is available then do not
   // generate the analysis again. Stale analysis info should not be
   // available at this point.
-  const PassInfo *PI =
-    PassRegistry::getPassRegistry()->getPassInfo(P->getPassID());
+  const PassInfo *PI = findAnalysisPassInfo(P->getPassID());
   if (PI && PI->isAnalysis() && findAnalysisPass(P->getPassID())) {
     delete P;
     return;
   }
 
   AnalysisUsage *AnUsage = findAnalysisUsage(P);
 
   bool checkAnalysis = true;
   while (checkAnalysis) {
     checkAnalysis = false;
 
     const AnalysisUsage::VectorType &RequiredSet = AnUsage->getRequiredSet();
     for (AnalysisUsage::VectorType::const_iterator I = RequiredSet.begin(),
            E = RequiredSet.end(); I != E; ++I) {
 
       Pass *AnalysisPass = findAnalysisPass(*I);
       if (!AnalysisPass) {
-        const PassInfo *PI = PassRegistry::getPassRegistry()->getPassInfo(*I);
+        const PassInfo *PI = findAnalysisPassInfo(*I);
 
         if (!PI) {
           // Pass P is not in the global PassRegistry
           dbgs() << "Pass '"  << P->getPassName() << "' is not initialized." << "\n";
           dbgs() << "Verify if there is a pass dependency cycle." << "\n";
           dbgs() << "Required Passes:" << "\n";
           for (AnalysisUsage::VectorType::const_iterator I2 = RequiredSet.begin(),
                  E = RequiredSet.end(); I2 != E && I2 != I; ++I2) {
Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) {
   // the most recently registered passes first.
   for (SmallVectorImpl<ImmutablePass *>::reverse_iterator I =
        ImmutablePasses.rbegin(), E = ImmutablePasses.rend(); I != E; ++I) {
     AnalysisID PI = (*I)->getPassID();
     if (PI == AID)
       return *I;
 
     // If Pass not found then check the interfaces implemented by Immutable Pass
-    const PassInfo *PassInf =
-      PassRegistry::getPassRegistry()->getPassInfo(PI);
+    const PassInfo *PassInf = findAnalysisPassInfo(PI);
     assert(PassInf && "Expected all immutable passes to be initialized");
     const std::vector<const PassInfo*> &ImmPI =
       PassInf->getInterfacesImplemented();
     for (std::vector<const PassInfo*>::const_iterator II = ImmPI.begin(),
          EE = ImmPI.end(); II != EE; ++II) {
       if ((*II)->getTypeInfo() == AID)
         return *I;
     }
   }
 
   return nullptr;
 }
 
+const PassInfo *PMTopLevelManager::findAnalysisPassInfo(AnalysisID AID) const {
+  const PassInfo *&PI = AnalysisPassInfos[AID];
+  if (!PI)
+    PI = PassRegistry::getPassRegistry()->getPassInfo(AID);
+  else
+    assert(PI == PassRegistry::getPassRegistry()->getPassInfo(AID) &&
+           "The pass info pointer changed for an analysis ID!");
+
+  return PI;
+}
+
 // Print passes managed by this top level manager.
 void PMTopLevelManager::dumpPasses() const {
 
   if (PassDebugging < Structure)
     return;
 
   // Print out the immutable passes
   for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) {

 void PMTopLevelManager::dumpArguments() const {
 
   if (PassDebugging < Arguments)
     return;
 
   dbgs() << "Pass Arguments: ";
   for (SmallVectorImpl<ImmutablePass *>::const_iterator I =
        ImmutablePasses.begin(), E = ImmutablePasses.end(); I != E; ++I)
-    if (const PassInfo *PI =
-        PassRegistry::getPassRegistry()->getPassInfo((*I)->getPassID())) {
+    if (const PassInfo *PI = findAnalysisPassInfo((*I)->getPassID())) {
       assert(PI && "Expected all immutable passes to be initialized");
       if (!PI->isAnalysisGroup())
         dbgs() << " -" << PI->getPassArgument();
     }
   for (SmallVectorImpl<PMDataManager *>::const_iterator I =
        PassManagers.begin(), E = PassManagers.end(); I != E; ++I)
     (*I)->dumpPassArguments();
   dbgs() << "\n";
void PMDataManager::recordAvailableAnalysis(Pass *P) {
   AnalysisID PI = P->getPassID();
 
   AvailableAnalysis[PI] = P;
 
   assert(!AvailableAnalysis.empty());
 
   // This pass is the current implementation of all of the interfaces it
   // implements as well.
-  const PassInfo *PInf = PassRegistry::getPassRegistry()->getPassInfo(PI);
+  const PassInfo *PInf = TPM->findAnalysisPassInfo(PI);
   if (!PInf) return;
   const std::vector<const PassInfo*> &II = PInf->getInterfacesImplemented();
   for (unsigned i = 0, e = II.size(); i != e; ++i)
     AvailableAnalysis[II[i]->getTypeInfo()] = P;
 }
 
 // Return true if P preserves high level analysis used by other
 // passes managed by this manager
dumpPassInfo(P, FREEING_MSG, DBG_STR, Msg);
     // If the pass crashes releasing memory, remember this.
     PassManagerPrettyStackEntry X(P);
     TimeRegion PassTimer(getPassTimer(P));
 
     P->releaseMemory();
   }
 
   AnalysisID PI = P->getPassID();
-  if (const PassInfo *PInf = PassRegistry::getPassRegistry()->getPassInfo(PI)) {
+  if (const PassInfo *PInf = TPM->findAnalysisPassInfo(PI)) {
     // Remove the pass itself (if it is not already removed).
     AvailableAnalysis.erase(PI);
 
     // Remove all interfaces this pass implements, for which it is also
     // listed as the available implementation.
     const std::vector<const PassInfo*> &II = PInf->getInterfacesImplemented();
     for (unsigned i = 0, e = II.size(); i != e; ++i) {
       DenseMap<AnalysisID, Pass*>::iterator Pos =
if (!TransferLastUses.empty()) {
     TPM->setLastUser(TransferLastUses, My_PM);
     TransferLastUses.clear();
   }
 
   // Now, take care of required analyses that are not available.
   for (SmallVectorImpl<AnalysisID>::iterator
          I = ReqAnalysisNotAvailable.begin(),
          E = ReqAnalysisNotAvailable.end() ;I != E; ++I) {
-    const PassInfo *PI = PassRegistry::getPassRegistry()->getPassInfo(*I);
+    const PassInfo *PI = TPM->findAnalysisPassInfo(*I);
     Pass *AnalysisPass = PI->createPass();
     this->addLowerLevelRequiredPass(P, AnalysisPass);
   }
 
   // Take a note of analysis required and made available by this pass.
   // Remove the analysis not preserved by this pass
   removeNotPreservedAnalysis(P);
   recordAvailableAnalysis(P);

 
 void PMDataManager::dumpPassArguments() const {
   for (SmallVectorImpl<Pass *>::const_iterator I = PassVector.begin(),
         E = PassVector.end(); I != E; ++I) {
     if (PMDataManager *PMD = (*I)->getAsPMDataManager())
       PMD->dumpPassArguments();
     else
       if (const PassInfo *PI =
-            PassRegistry::getPassRegistry()->getPassInfo((*I)->getPassID()))
+            TPM->findAnalysisPassInfo((*I)->getPassID()))
         if (!PI->isAnalysisGroup())
           dbgs() << " -" << PI->getPassArgument();
   }
 }
 
 void PMDataManager::dumpPassInfo(Pass *P, enum PassDebuggingString S1,
                                  enum PassDebuggingString S2,
                                  StringRef Msg) {

 void PMDataManager::dumpAnalysisUsage(StringRef Msg, const Pass *P,
                                    const AnalysisUsage::VectorType &Set) const {
   assert(PassDebugging >= Details);
   if (Set.empty())
     return;
   dbgs() << (const void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:";
   for (unsigned i = 0; i != Set.size(); ++i) {
     if (i) dbgs() << ',';
-    const PassInfo *PInf = PassRegistry::getPassRegistry()->getPassInfo(Set[i]);
+    const PassInfo *PInf = TPM->findAnalysisPassInfo(Set[i]);
     if (!PInf) {
       // Some preserved passes, such as AliasAnalysis, may not be initialized by
       // all drivers.
       dbgs() << " Uninitialized Pass";
       continue;
     }
     dbgs() << ' ' << PInf->getPassName();
   }
void MPPassManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
   FunctionPassManagerImpl *FPP = OnTheFlyManagers[P];
   if (!FPP) {
     FPP = new FunctionPassManagerImpl();
     // FPP is the top level manager.
     FPP->setTopLevelManager(FPP);
 
     OnTheFlyManagers[P] = FPP;
   }
-  const PassInfo * RequiredPassPI =
-    PassRegistry::getPassRegistry()->getPassInfo(RequiredPass->getPassID());
+  const PassInfo *RequiredPassPI =
+      TPM->findAnalysisPassInfo(RequiredPass->getPassID());
 
   Pass *FoundPass = nullptr;
   if (RequiredPassPI && RequiredPassPI->isAnalysis()) {
     FoundPass =
       ((PMTopLevelManager*)FPP)->findAnalysisPass(RequiredPass->getPassID());
   }
   if (!FoundPass) {
     FoundPass = RequiredPass;