Use inverted map to speedup collectLastUses().

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34364 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 16 insertions, 4 deletions

diff --git a/lib/VMCore/PassManager.cpp b/lib/VMCore/PassManager.cpp
index bc85967ee1..6c1f2360d8 100644
--- a/lib/VMCore/PassManager.cpp
+++ b/lib/VMCore/PassManager.cpp
@@ -362,13 +362,19 @@ void PMTopLevelManager::setLastUser(std::vector<Pass *> &AnalysisPasses,
   }
 }
 
+// Walk LastUser map and create inverted map. This should be done
+// after all passes are added and before running first pass.
+void PMTopLevelManager::collectInvertedLU() {
+   for (std::map<Pass *, Pass *>::iterator LUI = LastUser.begin(),
+          LUE = LastUser.end(); LUI != LUE; ++LUI)
+     InvertedLU[LUI->second].push_back(LUI->first);
+}
+
 /// Collect passes whose last user is P
 void PMTopLevelManager::collectLastUses(std::vector<Pass *> &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);
+   std::vector<Pass *>&LU = InvertedLU[P]; 
+   LastUses.insert(LastUses.end(), LU.begin(), LU.end());
 }
 
 /// Schedule pass P for execution. Make sure that passes required by
@@ -938,6 +944,9 @@ bool FunctionPassManagerImpl::run(Function &F) {
   dumpArguments();
   dumpPasses();
 
+  // Collect inverted map of LastUsers. This improves speed of
+  // collectLastUses().
+  TPM->collectInvertedLU();
   initializeAllAnalysisInfo();
   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {  
     FPPassManager *FP = getContainedManager(Index);
@@ -1086,6 +1095,9 @@ bool PassManagerImpl::run(Module &M) {
   dumpArguments();
   dumpPasses();
 
+  // Collect inverted map of LastUsers. This improves speed of
+  // collectLastUses().
+  TPM->collectInvertedLU();
   initializeAllAnalysisInfo();
   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {  
     MPPassManager *MP = getContainedManager(Index);