From b29f7b83bb290ebc42d28cbb05836f043b507aab Mon Sep 17 00:00:00 2001
From: Chandler Carruth <chandlerc@gmail.com>
Date: Thu, 10 Sep 2015 02:31:42 +0000
Subject: [PATCH] [LPM] Use a map from analysis ID to immutable passes in the
 legacy pass manager to avoid a slow linear scan of every immutable pass and
 on every attempt to find an analysis pass.

This speeds up 'check-llvm' on an unoptimized build for me by 15%, YMMV.
It should also help (a tiny bit) other folks that are really
bottlenecked on repeated runs of tiny pass pipelines across small IR
files.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@247240 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/IR/LegacyPassManagers.h |  8 +++---
 lib/IR/LegacyPassManager.cpp         | 42 ++++++++++++++++------------
 2 files changed, 28 insertions(+), 22 deletions(-)

diff --git a/include/llvm/IR/LegacyPassManagers.h b/include/llvm/IR/LegacyPassManagers.h
index 2bb534057f4..ab2e2280f9a 100644
--- a/include/llvm/IR/LegacyPassManagers.h
+++ b/include/llvm/IR/LegacyPassManagers.h
@@ -204,10 +204,7 @@ public:
   virtual ~PMTopLevelManager();
 
   /// Add immutable pass and initialize it.
-  inline void addImmutablePass(ImmutablePass *P) {
-    P->initializePass();
-    ImmutablePasses.push_back(P);
-  }
+  void addImmutablePass(ImmutablePass *P);
 
   inline SmallVectorImpl<ImmutablePass *>& getImmutablePasses() {
     return ImmutablePasses;
@@ -253,6 +250,9 @@ private:
   /// Immutable passes are managed by top level manager.
   SmallVector<ImmutablePass *, 16> ImmutablePasses;
 
+  /// Map from ID to immutable passes.
+  SmallDenseMap<AnalysisID, ImmutablePass *, 8> ImmutablePassMap;
+
   DenseMap<Pass *, AnalysisUsage *> AnUsageMap;
 
   /// Collection of PassInfo objects found via analysis IDs and in this top
diff --git a/lib/IR/LegacyPassManager.cpp b/lib/IR/LegacyPassManager.cpp
index 5483da1c5e5..a3e83fd5279 100644
--- a/lib/IR/LegacyPassManager.cpp
+++ b/lib/IR/LegacyPassManager.cpp
@@ -686,6 +686,10 @@ void PMTopLevelManager::schedulePass(Pass *P) {
 /// passes and all pass managers. If desired pass is not found
 /// then return NULL.
 Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) {
+  // For immutable passes we have a direct mapping from ID to pass, so check
+  // that first.
+  if (Pass *P = ImmutablePassMap.lookup(AID))
+    return P;
 
   // Check pass managers
   for (PMDataManager *PassManager : PassManagers)
@@ -697,24 +701,6 @@ Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) {
     if (Pass *P = IndirectPassManager->findAnalysisPass(AID, false))
       return P;
 
-  // Check the immutable passes. Iterate in reverse order so that we find
-  // the most recently registered passes first.
-  for (auto 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 = findAnalysisPassInfo(PI);
-    assert(PassInf && "Expected all immutable passes to be initialized");
-    const std::vector<const PassInfo*> &ImmPI =
-      PassInf->getInterfacesImplemented();
-    for (const PassInfo *PI : ImmPI)
-      if (PI->getTypeInfo() == AID)
-        return *I;
-  }
-
   return nullptr;
 }
 
@@ -729,6 +715,26 @@ const PassInfo *PMTopLevelManager::findAnalysisPassInfo(AnalysisID AID) const {
   return PI;
 }
 
+void PMTopLevelManager::addImmutablePass(ImmutablePass *P) {
+  P->initializePass();
+  ImmutablePasses.push_back(P);
+
+  // Add this pass to the map from its analysis ID. We clobber any prior runs
+  // of the pass in the map so that the last one added is the one found when
+  // doing lookups.
+  AnalysisID AID = P->getPassID();
+  ImmutablePassMap[AID] = P;
+
+  // Also add any interfaces implemented by the immutable pass to the map for
+  // fast lookup.
+  const PassInfo *PassInf = findAnalysisPassInfo(AID);
+  assert(PassInf && "Expected all immutable passes to be initialized");
+  const std::vector<const PassInfo*> &ImmPI =
+    PassInf->getInterfacesImplemented();
+  for (const PassInfo *ImmPI : ImmPI)
+    ImmutablePassMap[ImmPI->getTypeInfo()] = P;
+}
+
 // Print passes managed by this top level manager.
 void PMTopLevelManager::dumpPasses() const {
 
-- 
2.34.1