Switch ValueSymbolTable to use StringMap<Value*> instead of std::map<std::string, Value*>

as its main datastructure.  There are many improvements yet to be made, but
this speeds up opt --std-compile-opts on 447.dealII by 7.3%.


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

11 files changed, 143 insertions, 96 deletions

diff --git a/lib/Bytecode/Writer/SlotCalculator.cpp b/lib/Bytecode/Writer/SlotCalculator.cpp
index 0c8ba48be7..43ad922e2b 100644
--- a/lib/Bytecode/Writer/SlotCalculator.cpp
+++ b/lib/Bytecode/Writer/SlotCalculator.cpp
@@ -199,7 +199,7 @@ void SlotCalculator::processTypeSymbolTable(const TypeSymbolTable *TST) {
 void SlotCalculator::processValueSymbolTable(const ValueSymbolTable *VST) {
   for (ValueSymbolTable::const_iterator VI = VST->begin(), VE = VST->end(); 
        VI != VE; ++VI)
-    CreateSlotIfNeeded(VI->second);
+    CreateSlotIfNeeded(VI->getValue());
 }
 
 void SlotCalculator::CreateSlotIfNeeded(const Value *V) {
diff --git a/lib/Bytecode/Writer/Writer.cpp b/lib/Bytecode/Writer/Writer.cpp
index b98604bf71..434703f92e 100644
--- a/lib/Bytecode/Writer/Writer.cpp
+++ b/lib/Bytecode/Writer/Writer.cpp
@@ -132,10 +132,9 @@ inline void BytecodeWriter::output_vbr(int i) {
     output_vbr((unsigned)i << 1);          // Low order bit is clear.
 }
 
-inline void BytecodeWriter::output(const std::string &s) {
-  unsigned Len = s.length();
+inline void BytecodeWriter::output_str(const char *Str, unsigned Len) {
   output_vbr(Len);             // Strings may have an arbitrary length.
-  Out.insert(Out.end(), s.begin(), s.end());
+  Out.insert(Out.end(), Str, Str+Len);
 }
 
 inline void BytecodeWriter::output_data(const void *Ptr, const void *End) {
@@ -1088,14 +1087,12 @@ void BytecodeWriter::outputValueSymbolTable(const ValueSymbolTable &VST) {
                             true/*ElideIfEmpty*/);
 
   // Organize the symbol table by type
-  typedef std::pair<const std::string*, const Value*> PlaneMapEntry;
-  typedef SmallVector<PlaneMapEntry, 8> PlaneMapVector;
+  typedef SmallVector<const ValueName*, 8> PlaneMapVector;
   typedef DenseMap<const Type*, PlaneMapVector > PlaneMap;
   PlaneMap Planes;
   for (ValueSymbolTable::const_iterator SI = VST.begin(), SE = VST.end();
        SI != SE; ++SI) 
-    Planes[SI->second->getType()]
-      .push_back(std::make_pair(&SI->first, SI->second));
+    Planes[SI->getValue()->getType()].push_back(&*SI);
 
   for (PlaneMap::iterator PI = Planes.begin(), PE = Planes.end();
        PI != PE; ++PI) {
@@ -1113,8 +1110,8 @@ void BytecodeWriter::outputValueSymbolTable(const ValueSymbolTable &VST) {
     // Write each of the values in this plane
     for (; I != End; ++I) {
       // Symtab entry: [def slot #][name]
-      output_vbr(Table.getSlot(I->second));
-      output(*I->first);
+      output_vbr(Table.getSlot((*I)->getValue()));
+      output_str((*I)->getKeyData(), (*I)->getKeyLength());
     }
   }
 }
diff --git a/lib/Bytecode/Writer/WriterInternals.h b/lib/Bytecode/Writer/WriterInternals.h
index 6a036d804a..747ad8ef06 100644
--- a/lib/Bytecode/Writer/WriterInternals.h
+++ b/lib/Bytecode/Writer/WriterInternals.h
@@ -85,7 +85,10 @@ private:
   /// @brief Signed 32-bit variable bit rate output primitive.
   inline void output_vbr(int i);
 
-  inline void output(const std::string &s);
+  inline void output_str(const char *Str, unsigned Len);
+  inline void output(const std::string &s) {
+    output_str(&s[0], s.size());
+  }
 
   inline void output_data(const void *Ptr, const void *End);
 
diff --git a/lib/Transforms/IPO/StripSymbols.cpp b/lib/Transforms/IPO/StripSymbols.cpp
index 58b7b71467..2a5e830929 100644
--- a/lib/Transforms/IPO/StripSymbols.cpp
+++ b/lib/Transforms/IPO/StripSymbols.cpp
@@ -77,7 +77,7 @@ static void RemoveDeadConstant(Constant *C) {
 //
 static void StripSymtab(ValueSymbolTable &ST) {
   for (ValueSymbolTable::iterator VI = ST.begin(), VE = ST.end(); VI != VE; ) {
-    Value *V = VI->second;
+    Value *V = VI->getValue();
     ++VI;
     if (!isa<GlobalValue>(V) || cast<GlobalValue>(V)->hasInternalLinkage()) {
       // Set name to "", removing from symbol table!
diff --git a/lib/VMCore/BasicBlock.cpp b/lib/VMCore/BasicBlock.cpp
index afdd79e6aa..2e3b426e2b 100644
--- a/lib/VMCore/BasicBlock.cpp
+++ b/lib/VMCore/BasicBlock.cpp
@@ -62,7 +62,7 @@ template class SymbolTableListTraits<Instruction, BasicBlock, Function>;
 
 BasicBlock::BasicBlock(const std::string &Name, Function *Parent,
                        BasicBlock *InsertBefore)
-  : Value(Type::LabelTy, Value::BasicBlockVal, Name) {
+  : Value(Type::LabelTy, Value::BasicBlockVal) {
   // Initialize the instlist...
   InstList.setItemParent(this);
 
@@ -76,6 +76,8 @@ BasicBlock::BasicBlock(const std::string &Name, Function *Parent,
   } else if (Parent) {
     Parent->getBasicBlockList().push_back(this);
   }
+  
+  setName(Name);
 }
 
 
diff --git a/lib/VMCore/Function.cpp b/lib/VMCore/Function.cpp
index 72237eb440..fcbf73f9cf 100644
--- a/lib/VMCore/Function.cpp
+++ b/lib/VMCore/Function.cpp
@@ -51,7 +51,7 @@ template class SymbolTableListTraits<BasicBlock, Function, Function>;
 //===----------------------------------------------------------------------===//
 
 Argument::Argument(const Type *Ty, const std::string &Name, Function *Par)
-  : Value(Ty, Value::ArgumentVal, Name) {
+  : Value(Ty, Value::ArgumentVal) {
   Parent = 0;
 
   // Make sure that we get added to a function
@@ -59,6 +59,7 @@ Argument::Argument(const Type *Ty, const std::string &Name, Function *Par)
 
   if (Par)
     Par->getArgumentList().push_back(this);
+  setName(Name);
 }
 
 void Argument::setParent(Function *parent) {
diff --git a/lib/VMCore/Instruction.cpp b/lib/VMCore/Instruction.cpp
index 6b2babaecc..d4c44741e5 100644
--- a/lib/VMCore/Instruction.cpp
+++ b/lib/VMCore/Instruction.cpp
@@ -19,7 +19,7 @@ using namespace llvm;
 
 Instruction::Instruction(const Type *ty, unsigned it, Use *Ops, unsigned NumOps,
                          const std::string &Name, Instruction *InsertBefore)
-  : User(ty, Value::InstructionVal + it, Ops, NumOps, Name), Parent(0) {
+  : User(ty, Value::InstructionVal + it, Ops, NumOps), Parent(0) {
   // Make sure that we get added to a basicblock
   LeakDetector::addGarbageObject(this);
 
@@ -29,17 +29,19 @@ Instruction::Instruction(const Type *ty, unsigned it, Use *Ops, unsigned NumOps,
            "Instruction to insert before is not in a basic block!");
     InsertBefore->getParent()->getInstList().insert(InsertBefore, this);
   }
+  setName(Name);
 }
 
 Instruction::Instruction(const Type *ty, unsigned it, Use *Ops, unsigned NumOps,
                          const std::string &Name, BasicBlock *InsertAtEnd)
-  : User(ty, Value::InstructionVal + it, Ops, NumOps, Name), Parent(0) {
+  : User(ty, Value::InstructionVal + it, Ops, NumOps), Parent(0) {
   // Make sure that we get added to a basicblock
   LeakDetector::addGarbageObject(this);
 
   // append this instruction into the basic block
   assert(InsertAtEnd && "Basic block to append to may not be NULL!");
   InsertAtEnd->getInstList().push_back(this);
+  setName(Name);
 }
 
 // Out of line virtual method, so the vtable, etc has a home.
diff --git a/lib/VMCore/SymbolTableListTraitsImpl.h b/lib/VMCore/SymbolTableListTraitsImpl.h
index f4ee13f108..9c3d2525cf 100644
--- a/lib/VMCore/SymbolTableListTraitsImpl.h
+++ b/lib/VMCore/SymbolTableListTraitsImpl.h
@@ -32,7 +32,7 @@ void SymbolTableListTraits<ValueSubClass,ItemParentClass,SymTabClass,SubClass>
     ValueSymbolTable &SymTab = SymTabObject->getValueSymbolTable();
     for (typename iplist<ValueSubClass>::iterator I = List.begin();
          I != List.end(); ++I)
-      if (I->hasName()) SymTab.remove(I);
+      if (I->hasName()) SymTab.removeValueName(I->getValueName());
   }
 
   SymTabObject = STO;
@@ -42,7 +42,7 @@ void SymbolTableListTraits<ValueSubClass,ItemParentClass,SymTabClass,SubClass>
     ValueSymbolTable &SymTab = SymTabObject->getValueSymbolTable();
     for (typename iplist<ValueSubClass>::iterator I = List.begin();
          I != List.end(); ++I)
-      if (I->hasName()) SymTab.insert(I);
+      if (I->hasName()) SymTab.reinsertValue(I);
   }
 }
 
@@ -53,7 +53,7 @@ void SymbolTableListTraits<ValueSubClass,ItemParentClass,SymTabClass,SubClass>
   assert(V->getParent() == 0 && "Value already in a container!!");
   V->setParent(ItemParent);
   if (V->hasName() && SymTabObject)
-    SymTabObject->getValueSymbolTable().insert(V);
+    SymTabObject->getValueSymbolTable().reinsertValue(V);
 }
 
 template<typename ValueSubClass, typename ItemParentClass, typename SymTabClass,
@@ -62,7 +62,7 @@ void SymbolTableListTraits<ValueSubClass,ItemParentClass,SymTabClass,SubClass>
 ::removeNodeFromList(ValueSubClass *V) {
   V->setParent(0);
   if (V->hasName() && SymTabObject)
-    SymTabObject->getValueSymbolTable().remove(V);
+    SymTabObject->getValueSymbolTable().removeValueName(V->getValueName());
 }
 
 template<typename ValueSubClass, typename ItemParentClass, typename SymTabClass,
@@ -83,10 +83,10 @@ void SymbolTableListTraits<ValueSubClass,ItemParentClass,SymTabClass,SubClass>
       ValueSubClass &V = *first;
       bool HasName = V.hasName();
       if (OldSTO && HasName)
-        OldSTO->getValueSymbolTable().remove(&V);
+        OldSTO->getValueSymbolTable().removeValueName(V.getValueName());
       V.setParent(NewIP);
       if (NewSTO && HasName)
-        NewSTO->getValueSymbolTable().insert(&V);
+        NewSTO->getValueSymbolTable().reinsertValue(&V);
     }
   } else {
     // Just transferring between blocks in the same function, simply update the
diff --git a/lib/VMCore/Value.cpp b/lib/VMCore/Value.cpp
index 17610f9bc7..109994efb7 100644
--- a/lib/VMCore/Value.cpp
+++ b/lib/VMCore/Value.cpp
@@ -30,15 +30,13 @@ static inline const Type *checkType(const Type *Ty) {
   return Ty;
 }
 
-Value::Value(const Type *ty, unsigned scid, const std::string &name)
+Value::Value(const Type *ty, unsigned scid)
   : SubclassID(scid), SubclassData(0), Ty(checkType(ty)),
-    UseList(0), Name(name) {
+    UseList(0), Name(0) {
   if (!isa<Constant>(this) && !isa<BasicBlock>(this))
     assert((Ty->isFirstClassType() || Ty == Type::VoidTy ||
            isa<OpaqueType>(ty)) &&
            "Cannot create non-first-class values except for constants!");
-  if (ty == Type::VoidTy)
-    assert(name.empty() && "Cannot have named void values!");
 }
 
 Value::~Value() {
@@ -114,29 +112,62 @@ static bool getSymTab(Value *V, ValueSymbolTable *&ST) {
   return false;
 }
 
-void Value::setName(const std::string &name) {
-  if (Name == name) return;   // Name is already set.
+std::string Value::getName() const {
+  if (Name == 0) return "";
+  return std::string(Name->getKeyData(),
+                     Name->getKeyData()+Name->getKeyLength());
+}
 
+void Value::setName(const std::string &name) {
+  if (name.empty() && !hasName()) return;
+  if (getType() != Type::VoidTy && "Cannot assign a name to void values!");
+  
+  
   // Get the symbol table to update for this object.
   ValueSymbolTable *ST;
   if (getSymTab(this, ST))
     return;  // Cannot set a name on this value (e.g. constant).
 
-  if (!ST)  // No symbol table to update?  Just do the change.
-    Name = name;
-  else if (hasName()) {
-    if (!name.empty()) {    // Replacing name.
-      ST->remove(this);
-      Name = name;
-      ST->insert(this);
-    } else {                // Transitioning from hasName -> noname.
-      ST->remove(this);
-      Name.clear();
+  if (!ST) { // No symbol table to update?  Just do the change.
+    if (name.empty()) {
+      // Free the name for this value.
+      Name->Destroy();
+      Name = 0;
+    } else {
+      if (Name) {
+        // Name isn't changing.
+        if (name.size() == Name->getKeyLength() &&
+            !memcmp(Name->getKeyData(), &name[0], name.size()))
+          return;
+        Name->Destroy();
+      }
+      
+      // Create the new name.
+      Name = ValueName::Create(&name[0], &name[name.size()]);
+      Name->setValue(this);
     }
-  } else {                  // Transitioning from noname -> hasName.
-    Name = name;
-    ST->insert(this);
+    return;
   }
+  
+  // NOTE: Could optimize for the case the name is shrinking to not deallocate
+  // then reallocated.
+  if (hasName()) {
+    // Name isn't changing?
+    if (name.size() == Name->getKeyLength() &&
+        !memcmp(Name->getKeyData(), &name[0], name.size()))
+      return;
+
+    // Remove old name.
+    ST->removeValueName(Name);
+    Name->Destroy();
+    Name = 0;
+
+    if (name.empty())
+       return;
+  }
+
+  // Name is changing to something new.
+  Name = ST->createValueName(&name[0], name.size(), this);
 }
 
 /// takeName - transfer the name from V to this value, setting V's name to
diff --git a/lib/VMCore/ValueSymbolTable.cpp b/lib/VMCore/ValueSymbolTable.cpp
index 2f55e490df..e31410c29c 100644
--- a/lib/VMCore/ValueSymbolTable.cpp
+++ b/lib/VMCore/ValueSymbolTable.cpp
@@ -17,7 +17,6 @@
 #include "llvm/ValueSymbolTable.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/Debug.h"
-#include <algorithm>
 using namespace llvm;
 
 // Class destructor
@@ -25,8 +24,8 @@ ValueSymbolTable::~ValueSymbolTable() {
 #ifndef NDEBUG   // Only do this in -g mode...
   for (iterator VI = vmap.begin(), VE = vmap.end(); VI != VE; ++VI)
     DEBUG(DOUT << "Value still in symbol table! Type = '"
-               << VI->second->getType()->getDescription() << "' Name = '"
-               << VI->first << "'\n");
+               << VI->getValue()->getType()->getDescription() << "' Name = '"
+               << VI->getKeyData() << "'\n");
   assert(vmap.empty() && "Values remain in symbol table!");
 #endif
 }
@@ -37,11 +36,11 @@ ValueSymbolTable::~ValueSymbolTable() {
 //
 std::string ValueSymbolTable::getUniqueName(const std::string &BaseName) const {
   std::string TryName = BaseName;
-  const_iterator End = vmap.end();
 
   // See if the name exists
-  while (vmap.find(TryName) != End)            // Loop until we find a free
-    TryName = BaseName + utostr(++LastUnique); // name in the symbol table
+  while (vmap.find(&TryName[0], &TryName[TryName.size()]) != vmap.end())
+    // Loop until we find a free name in the symbol table.
+    TryName = BaseName + utostr(++LastUnique);
   return TryName;
 }
 
@@ -49,62 +48,95 @@ std::string ValueSymbolTable::getUniqueName(const std::string &BaseName) const {
 // lookup a value - Returns null on failure...
 //
 Value *ValueSymbolTable::lookup(const std::string &Name) const {
-  const_iterator VI = vmap.find(Name);
+  const_iterator VI = vmap.find(&Name[0], &Name[Name.size()]);
   if (VI != vmap.end())                   // We found the symbol
-    return const_cast<Value*>(VI->second);
+    return VI->getValue();
   return 0;
 }
 
 // Insert a value into the symbol table with the specified name...
 //
-void ValueSymbolTable::insert(Value* V) {
-  assert(V && "Can't insert null Value into symbol table!");
+void ValueSymbolTable::reinsertValue(Value* V) {
   assert(V->hasName() && "Can't insert nameless Value into symbol table");
 
   // Try inserting the name, assuming it won't conflict.
-  if (vmap.insert(make_pair(V->Name, V)).second) {
+  if (vmap.insert(V->Name)) {
     DOUT << " Inserted value: " << V->Name << ": " << *V << "\n";
     return;
   }
   
+  // FIXME: this could be much more efficient.
+  
   // Otherwise, there is a naming conflict.  Rename this value.
   std::string UniqueName = V->getName();
+  
+  V->Name->Destroy();
+  
   unsigned BaseSize = UniqueName.size();
-  do {
+  while (1) {
     // Trim any suffix off.
     UniqueName.resize(BaseSize);
     UniqueName += utostr(++LastUnique);
     // Try insert the vmap entry with this suffix.
-  } while (!vmap.insert(make_pair(UniqueName, V)).second);
-
-  V->Name = UniqueName;
-  
-  DEBUG(DOUT << " Inserted value: " << UniqueName << ": " << *V << "\n");
+    ValueName &NewName = vmap.GetOrCreateValue(&UniqueName[0],
+                                               &UniqueName[UniqueName.size()]);
+    if (NewName.getValue() == 0) {
+      // Newly inserted name.  Success!
+      NewName.setValue(V);
+      V->Name = &NewName;
+      DEBUG(DOUT << " Inserted value: " << UniqueName << ": " << *V << "\n");
+      return;
+    }
+  }
 }
 
-// Remove a value
-void ValueSymbolTable::remove(Value *V) {
-  assert(V->hasName() && "Value doesn't have name!");
-  iterator Entry = vmap.find(V->getName());
-  assert(Entry != vmap.end() && "Entry was not in the symtab!");
-
-  DEBUG(DOUT << " Removing Value: " << Entry->second->getName() << "\n");
-
-  // Remove the value from the plane...
-  vmap.erase(Entry);
+void ValueSymbolTable::removeValueName(ValueName *V) {
+  DEBUG(DOUT << " Removing Value: " << V->getKeyData() << "\n");
+  // Remove the value from the plane.
+  vmap.remove(V);
 }
 
-// DumpVal - a std::for_each function for dumping a value
-//
-static void DumpVal(const std::pair<const std::string, Value *> &V) {
-  DOUT << "  '" << V.first << "' = ";
-  V.second->dump();
-  DOUT << "\n";
+/// createValueName - This method attempts to create a value name and insert
+/// it into the symbol table with the specified name.  If it conflicts, it
+/// auto-renames the name and returns that instead.
+ValueName *ValueSymbolTable::createValueName(const char *NameStart,
+                                             unsigned NameLen, Value *V) {
+  ValueName &Entry = vmap.GetOrCreateValue(NameStart, NameStart+NameLen);
+  if (Entry.getValue() == 0) {
+    Entry.setValue(V);
+    DEBUG(DOUT << " Inserted value: " << Entry.getKeyData() << ": "
+               << *V << "\n");
+    return &Entry;
+  }
+  
+  // FIXME: this could be much more efficient.
+  
+  // Otherwise, there is a naming conflict.  Rename this value.
+  std::string UniqueName(NameStart, NameStart+NameLen);
+  while (1) {
+    // Trim any suffix off.
+    UniqueName.resize(NameLen);
+    UniqueName += utostr(++LastUnique);
+    // Try insert the vmap entry with this suffix.
+    ValueName &NewName = vmap.GetOrCreateValue(&UniqueName[0],
+                                               &UniqueName[UniqueName.size()]);
+    if (NewName.getValue() == 0) {
+      // Newly inserted name.  Success!
+      NewName.setValue(V);
+      DEBUG(DOUT << " Inserted value: " << UniqueName << ": " << *V << "\n");
+      return &NewName;
+    }
+  }
 }
 
+
 // dump - print out the symbol table
 //
 void ValueSymbolTable::dump() const {
   DOUT << "ValueSymbolTable:\n";
-  for_each(vmap.begin(), vmap.end(), DumpVal);
+  for (const_iterator I = begin(), E = end(); I != E; ++I) {
+    DOUT << "  '" << I->getKeyData() << "' = ";
+    I->getValue()->dump();
+    DOUT << "\n";
+  }
 }
diff --git a/lib/VMCore/Verifier.cpp b/lib/VMCore/Verifier.cpp
index 5488131289..91dd419865 100644
--- a/lib/VMCore/Verifier.cpp
+++ b/lib/VMCore/Verifier.cpp
@@ -51,7 +51,6 @@
 #include "llvm/Instructions.h"
 #include "llvm/Intrinsics.h"
 #include "llvm/PassManager.h"
-#include "llvm/ValueSymbolTable.h"
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/Support/CFG.h"
 #include "llvm/Support/InstVisitor.h"
@@ -102,7 +101,6 @@ namespace {  // Anonymous namespace for class
     bool doInitialization(Module &M) {
       Mod = &M;
       verifyTypeSymbolTable(M.getTypeSymbolTable());
-      verifyValueSymbolTable(M.getValueSymbolTable());
 
       // If this is a real pass, in a pass manager, we must abort before
       // returning back to the pass manager, or else the pass manager may try to
@@ -177,7 +175,6 @@ namespace {  // Anonymous namespace for class
 
     // Verification methods...
     void verifyTypeSymbolTable(TypeSymbolTable &ST);
-    void verifyValueSymbolTable(ValueSymbolTable &ST);
     void visitGlobalValue(GlobalValue &GV);
     void visitGlobalVariable(GlobalVariable &GV);
     void visitFunction(Function &F);
@@ -307,22 +304,6 @@ void Verifier::visitGlobalVariable(GlobalVariable &GV) {
 void Verifier::verifyTypeSymbolTable(TypeSymbolTable &ST) {
 }
 
-// verifySymbolTable - Verify that a function or module symbol table is ok
-//
-void Verifier::verifyValueSymbolTable(ValueSymbolTable &ST) {
-
-  // Loop over all of the values in the symbol table.
-  for (ValueSymbolTable::const_iterator VI = ST.begin(), VE = ST.end(); 
-       VI != VE; ++VI) {
-    Value *V = VI->second;
-    // Check that there are no void typed values in the symbol table.  Values
-    // with a void type cannot be put into symbol tables because they cannot
-    // have names!
-    Assert1(V->getType() != Type::VoidTy,
-      "Values with void type are not allowed to have names!", V);
-  }
-}
-
 // visitFunction - Verify that a function is ok.
 //
 void Verifier::visitFunction(Function &F) {
@@ -375,8 +356,6 @@ void Verifier::visitFunction(Function &F) {
       Assert1(F.getName().substr(0, 5) != "llvm.",
               "llvm intrinsics cannot be defined!", &F);
     
-    verifyValueSymbolTable(F.getValueSymbolTable());
-
     // Check the entry node
     BasicBlock *Entry = &F.getEntryBlock();
     Assert1(pred_begin(Entry) == pred_end(Entry),