From 721e59cfb29024ffad7204f05ad75b678ae7df63 Mon Sep 17 00:00:00 2001
From: Devang Patel <dpatel@apple.com>
Date: Tue, 12 Aug 2008 00:26:16 +0000
Subject: [PATCH] Use DenseMap to keep track of last users. Use inversed map
 for faster queries.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54662 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/PassManagers.h |  8 +++++++-
 lib/VMCore/PassManager.cpp  | 34 ++++++++++++++++++++++++++++------
 2 files changed, 35 insertions(+), 7 deletions(-)

diff --git a/include/llvm/PassManagers.h b/include/llvm/PassManagers.h
index a97f4f3e1a6..ff06024ed47 100644
--- a/include/llvm/PassManagers.h
+++ b/include/llvm/PassManagers.h
@@ -13,6 +13,7 @@
 
 #include "llvm/PassManager.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/DenseMap.h"
 #include <deque>
 #include <map>
@@ -221,7 +222,12 @@ private:
 
   // Map to keep track of last user of the analysis pass.
   // LastUser->second is the last user of Lastuser->first.
-  std::map<Pass *, Pass *> LastUser;
+  DenseMap<Pass *, Pass *> LastUser;
+
+  // Map to keep track of passes that are last used by a pass.
+  // 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.
   std::vector<ImmutablePass *> ImmutablePasses;
diff --git a/lib/VMCore/PassManager.cpp b/lib/VMCore/PassManager.cpp
index d6d89f55c3f..ed0dde03a18 100644
--- a/lib/VMCore/PassManager.cpp
+++ b/lib/VMCore/PassManager.cpp
@@ -404,9 +404,11 @@ void PMTopLevelManager::setLastUser(SmallVector<Pass *, 12> &AnalysisPasses,
 
     // If AP is the last user of other passes then make P last user of
     // such passes.
-    for (std::map<Pass *, Pass *>::iterator LUI = LastUser.begin(),
+    for (DenseMap<Pass *, Pass *>::iterator LUI = LastUser.begin(),
            LUE = LastUser.end(); LUI != LUE; ++LUI) {
       if (LUI->second == AP)
+        // DenseMap iterator is not invalidated here because
+        // this is just updating exisitng entry.
         LastUser[LUI->first] = P;
     }
   }
@@ -414,11 +416,18 @@ void PMTopLevelManager::setLastUser(SmallVector<Pass *, 12> &AnalysisPasses,
 
 /// Collect passes whose last user is P
 void PMTopLevelManager::collectLastUses(SmallVector<Pass *, 12> &LastUses,
-                                            Pass *P) {
-   for (std::map<Pass *, Pass *>::iterator LUI = LastUser.begin(),
-          LUE = LastUser.end(); LUI != LUE; ++LUI)
-      if (LUI->second == P)
-        LastUses.push_back(LUI->first);
+                                        Pass *P) {
+  DenseMap<Pass *, SmallPtrSet<Pass *, 8> >::iterator DMI = 
+    InversedLastUser.find(P);
+  if (DMI == InversedLastUser.end())
+    return;
+
+  SmallPtrSet<Pass *, 8> &LU = DMI->second;
+  for (SmallPtrSet<Pass *, 8>::iterator I = LU.begin(),
+         E = LU.end(); I != E; ++I) {
+    LastUses.push_back(*I);
+  }
+
 }
 
 AnalysisUsage *PMTopLevelManager::findAnalysisUsage(Pass *P) {
@@ -557,6 +566,19 @@ void PMTopLevelManager::initializeAllAnalysisInfo() {
   for (std::vector<PMDataManager *>::iterator I = IndirectPassManagers.begin(),
          E = IndirectPassManagers.end(); I != E; ++I)
     (*I)->initializeAnalysisInfo();
+
+  for(DenseMap<Pass *, Pass *>::iterator DMI = LastUser.begin(),
+        DME = LastUser.end(); DMI != DME; ++DMI) {
+    DenseMap<Pass *, SmallPtrSet<Pass *, 8> >::iterator InvDMI = 
+      InversedLastUser.find(DMI->second);
+    if (InvDMI != InversedLastUser.end()) {
+      SmallPtrSet<Pass *, 8> &L = InvDMI->second;
+      L.insert(DMI->first);
+    } else {
+      SmallPtrSet<Pass *, 8> L; L.insert(DMI->first);
+      InversedLastUser[DMI->second] = L;
+    }
+  }
 }
 
 /// Destructor
-- 
2.34.1