IdentifierInfo:

- IdentifierInfo can now (optionally) have its string data not be
  co-located with itself.  This is for use with PTH.  This aspect is a
  little gross, as getName() and getLength() now make assumptions
  about a possible alternate representation of IdentifierInfo.
  Perhaps we should make IdentifierInfo have virtual methods?

IdentifierTable:
- Added class "IdentifierInfoLookup" that can be used by
  IdentifierTable to perform "string -> IdentifierInfo" lookups using
  an auxilliary data structure.  This is used by PTH.
- Perform tests show that IdentifierTable::get() does not slow down
  because of the extra check for the IdentiferInfoLookup object (the
  regular StringMap lookup does enough work to mitigate the impact of
  an extra null pointer check).
- The upshot is that now that some IdentifierInfo objects might be
  owned by the IdentiferInfoLookup object.  This should be reviewed.

PTH:
- Modified PTHManager::GetIdentifierInfo to *not* insert entries in
  IdentifierTable's string map, and instead create IdentifierInfo
  objects on the fly when mapping from persistent IDs to
  IdentifierInfos.  This saves a ton of work with string copies,
  hashing, and StringMap lookup and resizing.  This change was
  motivated because when processing source files in the PTH cache we
  don't need to do any string -> IdentifierInfo lookups.
- PTHManager now subclasses IdentifierInfoLookup, allowing clients of
  IdentifierTable to transparently use IdentifierInfo objects managed
  by the PTH file.  PTHManager resolves "string -> IdentifierInfo"
  queries by doing a binary search over a sorted table of identifier
  strings in the PTH file (the exact algorithm we use can be changed
  as needed).

These changes lead to the following performance changes when using PTH on Cocoa.h:
- fsyntax-only: 10% performance improvement
- Eonly: 30% performance improvement


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

1 files changed, 49 insertions, 3 deletions

diff --git a/include/clang/Basic/IdentifierTable.h b/include/clang/Basic/IdentifierTable.h
index a0fac27657..7a4db7c02a 100644
--- a/include/clang/Basic/IdentifierTable.h
+++ b/include/clang/Basic/IdentifierTable.h
@@ -19,6 +19,7 @@
 #include "clang/Basic/TokenKinds.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/OwningPtr.h"
 #include "llvm/Bitcode/SerializationFwd.h"
 #include <string> 
 #include <cassert> 
@@ -55,12 +56,13 @@ class IdentifierInfo {
   bool IsExtension            : 1; // True if identifier is a lang extension.
   bool IsPoisoned             : 1; // True if identifier is poisoned.
   bool IsCPPOperatorKeyword   : 1; // True if ident is a C++ operator keyword.
-  // 10 bits left in 32-bit word.
+  bool IndirectString         : 1; // True if the string is stored indirectly.
+  // 9 bits left in 32-bit word.
   void *FETokenInfo;               // Managed by the language front-end.
   IdentifierInfo(const IdentifierInfo&);  // NONCOPYABLE.
   void operator=(const IdentifierInfo&);  // NONASSIGNABLE.
 public:
-  IdentifierInfo();
+  IdentifierInfo(bool usesIndirectString = false);
 
   /// isStr - Return true if this is the identifier for the specified string.
   /// This is intended to be used for string literals only: II->isStr("foo").
@@ -73,6 +75,13 @@ public:
   /// string is properly null terminated.
   ///
   const char *getName() const {
+    if (IndirectString) {
+      // The 'this' pointer really points to a 
+      // std::pair<IdentifierInfo, const char*>, where internal pointer
+      // points to the external string data.
+      return ((std::pair<IdentifierInfo, const char*>*) this)->second + 4;
+    }
+
     // We know that this is embedded into a StringMapEntry, and it knows how to
     // efficiently find the string.
     return llvm::StringMapEntry<IdentifierInfo>::
@@ -82,6 +91,17 @@ public:
   /// getLength - Efficiently return the length of this identifier info.
   ///
   unsigned getLength() const {
+    if (IndirectString) {
+      // The 'this' pointer really points to a 
+      // std::pair<IdentifierInfo, const char*>, where internal pointer
+      // points to the external string data.
+      const char* p = ((std::pair<IdentifierInfo, const char*>*) this)->second;
+      return ((unsigned) p[0])
+        | (((unsigned) p[1]) << 8)
+        | (((unsigned) p[2]) << 16)
+        | (((unsigned) p[3]) << 24);      
+    }
+    
     return llvm::StringMapEntry<IdentifierInfo>::
                     GetStringMapEntryFromValue(*this).getKeyLength();
   }
@@ -161,6 +181,20 @@ public:
   void Read(llvm::Deserializer& D);  
 };
 
+/// IdentifierInfoLookup - An abstract class used by IdentifierTable that
+///  provides an interface for for performing lookups from strings
+/// (const char *) to IdentiferInfo objects.
+class IdentifierInfoLookup {
+public:
+  virtual ~IdentifierInfoLookup();
+  
+  /// get - Return the identifier token info for the specified named identifier.
+  ///  Unlike the version in IdentifierTable, this returns a pointer instead
+  ///  of a reference.  If the pointer is NULL then the IdentifierInfo cannot
+  ///  be found.
+  virtual IdentifierInfo* get(const char *NameStart, const char *NameEnd) = 0;
+};  
+  
 /// IdentifierTable - This table implements an efficient mapping from strings to
 /// IdentifierInfo nodes.  It has no other purpose, but this is an
 /// extremely performance-critical piece of the code, as each occurrance of
@@ -170,15 +204,27 @@ class IdentifierTable {
   // BumpPtrAllocator!
   typedef llvm::StringMap<IdentifierInfo, llvm::BumpPtrAllocator> HashTableTy;
   HashTableTy HashTable;
+  
+  IdentifierInfoLookup* ExternalLookup;
 
 public:
   /// IdentifierTable ctor - Create the identifier table, populating it with
   /// info about the language keywords for the language specified by LangOpts.
-  IdentifierTable(const LangOptions &LangOpts);
+  IdentifierTable(const LangOptions &LangOpts,
+                  IdentifierInfoLookup* externalLookup = 0);
+  
+  llvm::BumpPtrAllocator& getAllocator() {
+    return HashTable.getAllocator();
+  }
   
   /// get - Return the identifier token info for the specified named identifier.
   ///
   IdentifierInfo &get(const char *NameStart, const char *NameEnd) {
+    if (ExternalLookup) {
+      IdentifierInfo* II = ExternalLookup->get(NameStart, NameEnd);
+      if (II) return *II;
+    }
+
     return HashTable.GetOrCreateValue(NameStart, NameEnd).getValue();
   }