The ModuleLevel vector is often quite sparse. Switch it to a DenseMap. This

speeds up bcwriting of 447.dealII by 40%, from 4.63s to 3.32s.


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

2 files changed, 24 insertions, 18 deletions

diff --git a/lib/Bytecode/Writer/SlotCalculator.cpp b/lib/Bytecode/Writer/SlotCalculator.cpp
index 8e22a18..5ad6564 100644
--- a/lib/Bytecode/Writer/SlotCalculator.cpp
+++ b/lib/Bytecode/Writer/SlotCalculator.cpp
@@ -179,11 +179,9 @@ void SlotCalculator::processModule() {
         ++FirstNonValueTypeID;
       }
   }
-
-    
-  // Initialize the ModuleLevel entries.
-  ModuleLevel.resize(getNumPlanes(), -1);
     
+  NumModuleTypes = getNumPlanes();
+
   SC_DEBUG("end processModule!\n");
 }
 
@@ -300,27 +298,26 @@ void SlotCalculator::incorporateFunction(const Function *F) {
 }
 
 void SlotCalculator::purgeFunction() {
-  unsigned NumModuleTypes = ModuleLevel.size();
-  
   SC_DEBUG("begin purgeFunction!\n");
   
   // Next, remove values from existing type planes
-  for (unsigned i = 0; i != NumModuleTypes; ++i) {
-    // If this type is not used by this function, ignore it.
-    int ModuleLev = ModuleLevel[i];
-    if (ModuleLev == -1) continue;
+  for (DenseMap<unsigned,unsigned,
+          ModuleLevelDenseMapKeyInfo>::iterator I = ModuleLevel.begin(),
+       E = ModuleLevel.end(); I != E; ++I) {
+    unsigned PlaneNo = I->first;
+    unsigned ModuleLev = I->second;
     
-    ModuleLevel[i] = -1;  // Reset for next function.
-
     // Pop all function-local values in this type-plane off of Table.
-    TypePlane &Plane = getPlane(i);
+    TypePlane &Plane = getPlane(PlaneNo);
     assert(ModuleLev < Plane.size() && "module levels higher than elements?");
     for (unsigned i = ModuleLev, e = Plane.size(); i != e; ++i) {
       NodeMap.erase(Plane.back());       // Erase from nodemap
       Plane.pop_back();                  // Shrink plane
     }
   }
-  
+
+  ModuleLevel.clear();
+
   // Finally, remove any type planes defined by the function...
   while (Table.size() > NumModuleTypes) {
     TypePlane &Plane = Table.back();
@@ -349,8 +346,8 @@ void SlotCalculator::CreateFunctionValueSlot(const Value *V) {
   // If this is the first value noticed of this type within this function,
   // remember the module level for this type plane in ModuleLevel.  This reminds
   // us to remove the values in purgeFunction and tells us how many to remove.
-  if (TyPlane < ModuleLevel.size() && ModuleLevel[TyPlane] == -1)
-    ModuleLevel[TyPlane] = Table[TyPlane].size();
+  if (TyPlane < NumModuleTypes)
+    ModuleLevel.insert(std::make_pair(TyPlane, Table[TyPlane].size()));
   
   // If this is the first value to get inserted into the type plane, make sure
   // to insert the implicit null value.
diff --git a/lib/Bytecode/Writer/SlotCalculator.h b/lib/Bytecode/Writer/SlotCalculator.h
index d39635b..e20bc62 100644
--- a/lib/Bytecode/Writer/SlotCalculator.h
+++ b/lib/Bytecode/Writer/SlotCalculator.h
@@ -20,6 +20,7 @@
 #ifndef LLVM_ANALYSIS_SLOTCALCULATOR_H
 #define LLVM_ANALYSIS_SLOTCALCULATOR_H
 
+#include "llvm/ADT/DenseMap.h"
 #include <vector>
 #include <map>
 
@@ -34,6 +35,14 @@ class TypeSymbolTable;
 class ValueSymbolTable;
 class ConstantArray;
 
+struct ModuleLevelDenseMapKeyInfo {
+  static inline unsigned getEmptyKey() { return ~0U; }
+  static inline unsigned getTombstoneKey() { return ~1U; }
+  static unsigned getHashValue(unsigned Val) { return Val ^ Val >> 4; }
+  static bool isPod() { return true; }
+};
+
+
 class SlotCalculator {
   const Module *TheModule;
 
@@ -54,8 +63,8 @@ class SlotCalculator {
   /// ModuleLevel - Used to keep track of which values belong to the module,
   /// and which values belong to the currently incorporated function.
   ///
-  std::vector<int> ModuleLevel;
-  unsigned ModuleTypeLevel;
+  DenseMap<unsigned,unsigned,ModuleLevelDenseMapKeyInfo> ModuleLevel;
+  unsigned NumModuleTypes;
 
   SlotCalculator(const SlotCalculator &);  // DO NOT IMPLEMENT
   void operator=(const SlotCalculator &);  // DO NOT IMPLEMENT