switch SourceManager from using an std::map and std::list of

ContentCache objects to using a densemap and list, and allocating
the ContentCache objects from a bump pointer.  This does not speed
up or slow down things substantially, but gives us control over 
their alignment.


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

3 files changed, 60 insertions, 54 deletions

diff --git a/Driver/CacheTokens.cpp b/Driver/CacheTokens.cpp
index c64797ec38..51f5027243 100644
--- a/Driver/CacheTokens.cpp
+++ b/Driver/CacheTokens.cpp
@@ -433,7 +433,7 @@ void PTHWriter::GeneratePTH() {
   
   for (SourceManager::fileinfo_iterator I = SM.fileinfo_begin(),
        E = SM.fileinfo_end(); I != E; ++I) {
-    const SrcMgr::ContentCache &C = *I;
+    const SrcMgr::ContentCache &C = *I->second;
     const FileEntry *FE = C.Entry;
     
     // FIXME: Handle files with non-absolute paths.
diff --git a/include/clang/Basic/SourceManager.h b/include/clang/Basic/SourceManager.h
index 7dbf0ccf61..c21c221b5c 100644
--- a/include/clang/Basic/SourceManager.h
+++ b/include/clang/Basic/SourceManager.h
@@ -16,10 +16,10 @@
 
 #include "clang/Basic/SourceLocation.h"
 #include "llvm/Bitcode/SerializationFwd.h"
+#include "llvm/Support/Allocator.h"
 #include "llvm/Support/DataTypes.h"
+#include "llvm/ADT/DenseMap.h"
 #include <vector>
-#include <set>
-#include <list>
 #include <cassert>
 
 namespace llvm {
@@ -61,8 +61,9 @@ namespace SrcMgr {
     /// the ContentCache encapsulates an imaginary text buffer.
     const FileEntry *Entry;
     
-    /// SourceLineCache - A new[]'d array of offsets for each source line.  This
-    /// is lazily computed.  This is owned by the ContentCache object.
+    /// SourceLineCache - A bump pointer allocated array of offsets for each
+    /// source line.  This is lazily computed.  This is owned by the
+    /// SourceManager BumpPointerAllocator object.
     unsigned *SourceLineCache;
     
     /// NumLines - The number of lines in this ContentCache.  This is only valid
@@ -88,18 +89,18 @@ namespace SrcMgr {
       Buffer = B;
     }
         
-    ContentCache(const FileEntry *e = NULL)
-      : Buffer(NULL), Entry(e), SourceLineCache(NULL), NumLines(0) {}
+    ContentCache(const FileEntry *Ent = 0)
+      : Buffer(0), Entry(Ent), SourceLineCache(0), NumLines(0) {}
 
     ~ContentCache();
     
     /// The copy ctor does not allow copies where source object has either
     ///  a non-NULL Buffer or SourceLineCache.  Ownership of allocated memory
     ///  is not transfered, so this is a logical error.
-    ContentCache(const ContentCache &RHS) : Buffer(NULL),SourceLineCache(NULL) {
+    ContentCache(const ContentCache &RHS) : Buffer(0), SourceLineCache(0) {
       Entry = RHS.Entry;
 
-      assert (RHS.Buffer == NULL && RHS.SourceLineCache == NULL
+      assert (RHS.Buffer == 0 && RHS.SourceLineCache == 0
               && "Passed ContentCache object cannot own a buffer.");
               
       NumLines = RHS.NumLines;      
@@ -227,18 +228,6 @@ namespace SrcMgr {
     }
   };
 }  // end SrcMgr namespace.
-} // end clang namespace
-
-namespace std {
-template <> struct less<clang::SrcMgr::ContentCache> {
-  inline bool operator()(const clang::SrcMgr::ContentCache& L,
-                         const clang::SrcMgr::ContentCache& R) const {
-    return L.Entry < R.Entry;
-  }
-};
-} // end std namespace
-
-namespace clang {
   
 /// SourceManager - This file handles loading and caching of source files into
 /// memory.  This object owns the MemoryBuffer objects for all of the loaded
@@ -252,17 +241,18 @@ namespace clang {
 /// location indicates where the expanded token came from and the instantiation
 /// location specifies where it was expanded.
 class SourceManager {
+  mutable llvm::BumpPtrAllocator ContentCacheAlloc;
+  
   /// FileInfos - Memoized information about all of the files tracked by this
   /// SourceManager.  This set allows us to merge ContentCache entries based
   /// on their FileEntry*.  All ContentCache objects will thus have unique,
   /// non-null, FileEntry pointers.  
-  std::set<SrcMgr::ContentCache> FileInfos;
+  llvm::DenseMap<const FileEntry*, SrcMgr::ContentCache*> FileInfos;
   
   /// MemBufferInfos - Information about various memory buffers that we have
-  /// read in.  This is a list, instead of a vector, because we need pointers to
-  /// the ContentCache objects to be stable.  All FileEntry* within the
-  /// stored ContentCache objects are NULL, as they do not refer to a file.
-  std::list<SrcMgr::ContentCache> MemBufferInfos;
+  /// read in.  All FileEntry* within the stored ContentCache objects are NULL,
+  /// as they do not refer to a file.
+  std::vector<SrcMgr::ContentCache*> MemBufferInfos;
   
   /// SLocEntryTable - This is an array of SLocEntry's that we have created.
   /// FileID is an index into this vector.  This array is sorted by the offset.
@@ -552,7 +542,8 @@ public:
   //===--------------------------------------------------------------------===//
   
   // Iterators over FileInfos.
-  typedef std::set<SrcMgr::ContentCache>::const_iterator fileinfo_iterator;
+  typedef llvm::DenseMap<const FileEntry*, SrcMgr::ContentCache*>
+      ::const_iterator fileinfo_iterator;
   fileinfo_iterator fileinfo_begin() const { return FileInfos.begin(); }
   fileinfo_iterator fileinfo_end() const { return FileInfos.end(); }
 
diff --git a/lib/Basic/SourceManager.cpp b/lib/Basic/SourceManager.cpp
index 88292cd42b..191b6155f0 100644
--- a/lib/Basic/SourceManager.cpp
+++ b/lib/Basic/SourceManager.cpp
@@ -30,7 +30,6 @@ using llvm::MemoryBuffer;
 
 ContentCache::~ContentCache() {
   delete Buffer;
-  delete [] SourceLineCache;
 }
 
 /// getSizeBytesMapped - Returns the number of bytes actually mapped for
@@ -121,6 +120,19 @@ unsigned SourceManager::getLineTableFilenameID(const char *Ptr, unsigned Len) {
 
 SourceManager::~SourceManager() {
   delete LineTable;
+  
+  // Delete FileEntry objects corresponding to content caches.  Since the actual
+  // content cache objects are bump pointer allocated, we just have to run the
+  // dtors, but we call the deallocate method for completeness.
+  for (unsigned i = 0, e = MemBufferInfos.size(); i != e; ++i) {
+    MemBufferInfos[i]->~ContentCache();
+    ContentCacheAlloc.Deallocate(MemBufferInfos[i]);
+  }
+  for (llvm::DenseMap<const FileEntry*, SrcMgr::ContentCache*>::iterator
+       I = FileInfos.begin(), E = FileInfos.end(); I != E; ++I) {
+    I->second->~ContentCache();
+    ContentCacheAlloc.Deallocate(I->second);
+  }
 }
 
 void SourceManager::clearIDTables() {
@@ -145,17 +157,13 @@ SourceManager::getOrCreateContentCache(const FileEntry *FileEnt) {
   assert(FileEnt && "Didn't specify a file entry to use?");
   
   // Do we already have information about this file?
-  std::set<ContentCache>::iterator I = 
-    FileInfos.lower_bound(ContentCache(FileEnt));
-  
-  if (I != FileInfos.end() && I->Entry == FileEnt)
-    return &*I;
+  ContentCache *&Entry = FileInfos[FileEnt];
+  if (Entry) return Entry;
   
   // Nope, create a new Cache entry.
-  ContentCache& Entry = const_cast<ContentCache&>(*FileInfos.insert(I,FileEnt));
-  Entry.SourceLineCache = 0;
-  Entry.NumLines = 0;
-  return &Entry;
+  Entry = ContentCacheAlloc.Allocate<ContentCache>();
+  new (Entry) ContentCache(FileEnt);
+  return Entry;
 }
 
 
@@ -167,10 +175,11 @@ SourceManager::createMemBufferContentCache(const MemoryBuffer *Buffer) {
   // must default construct the object first that the instance actually
   // stored within MemBufferInfos actually owns the Buffer, and not any
   // temporary we would use in the call to "push_back".
-  MemBufferInfos.push_back(ContentCache());
-  ContentCache& Entry = const_cast<ContentCache&>(MemBufferInfos.back());
-  Entry.setBuffer(Buffer);
-  return &Entry;
+  ContentCache *Entry = ContentCacheAlloc.Allocate<ContentCache>();
+  new (Entry) ContentCache();
+  MemBufferInfos.push_back(Entry);
+  Entry->setBuffer(Buffer);
+  return Entry;
 }
 
 //===----------------------------------------------------------------------===//
@@ -413,8 +422,9 @@ unsigned SourceManager::getColumnNumber(SourceLocation Loc) const {
   return FilePos-LineStart+1;
 }
 
-static void ComputeLineNumbers(ContentCache* FI) DISABLE_INLINE;
-static void ComputeLineNumbers(ContentCache* FI) {  
+static void ComputeLineNumbers(ContentCache* FI,
+                               llvm::BumpPtrAllocator &Alloc) DISABLE_INLINE;
+static void ComputeLineNumbers(ContentCache* FI, llvm::BumpPtrAllocator &Alloc){ 
   // Note that calling 'getBuffer()' may lazily page in the file.
   const MemoryBuffer *Buffer = FI->getBuffer();
   
@@ -454,7 +464,7 @@ static void ComputeLineNumbers(ContentCache* FI) {
   
   // Copy the offsets into the FileInfo structure.
   FI->NumLines = LineOffsets.size();
-  FI->SourceLineCache = new unsigned[LineOffsets.size()];
+  FI->SourceLineCache = Alloc.Allocate<unsigned>(LineOffsets.size());
   std::copy(LineOffsets.begin(), LineOffsets.end(), FI->SourceLineCache);
 }
 
@@ -478,7 +488,7 @@ unsigned SourceManager::getLineNumber(SourceLocation Loc) const {
   // If this is the first use of line information for this buffer, compute the
   /// SourceLineCache for it on demand.
   if (Content->SourceLineCache == 0)
-    ComputeLineNumbers(Content);
+    ComputeLineNumbers(Content, ContentCacheAlloc);
 
   // Okay, we know we have a line number table.  Do a binary search to find the
   // line number that this character position lands on.
@@ -595,10 +605,9 @@ void SourceManager::PrintStats() const {
     
   unsigned NumLineNumsComputed = 0;
   unsigned NumFileBytesMapped = 0;
-  for (std::set<ContentCache>::const_iterator I = 
-       FileInfos.begin(), E = FileInfos.end(); I != E; ++I) {
-    NumLineNumsComputed += I->SourceLineCache != 0;
-    NumFileBytesMapped  += I->getSizeBytesMapped();
+  for (fileinfo_iterator I = fileinfo_begin(), E = fileinfo_end(); I != E; ++I){
+    NumLineNumsComputed += I->second->SourceLineCache != 0;
+    NumFileBytesMapped  += I->second->getSizeBytesMapped();
   }
   
   llvm::cerr << NumFileBytesMapped << " bytes of files mapped, "
@@ -665,8 +674,10 @@ void ContentCache::ReadToSourceManager(llvm::Deserializer& D,
   }
   
   // Register the ContextCache object with the deserializer.
+  /* FIXME:
+  ContentCache *Entry
   SMgr.MemBufferInfos.push_back(ContentCache());
-  ContentCache& Entry = const_cast<ContentCache&>(SMgr.MemBufferInfos.back());
+   = const_cast<ContentCache&>(SMgr.MemBufferInfos.back());
   D.RegisterPtr(&Entry);
   
   // Create the buffer.
@@ -677,6 +688,7 @@ void ContentCache::ReadToSourceManager(llvm::Deserializer& D,
   char* p = const_cast<char*>(Entry.Buffer->getBufferStart());
   for (unsigned i = 0; i < Size ; ++i)
     p[i] = D.ReadInt();    
+   */
 }
 
 void SourceManager::Emit(llvm::Serializer& S) const {
@@ -687,16 +699,19 @@ void SourceManager::Emit(llvm::Serializer& S) const {
   // Emit: FileInfos.  Just emit the file name.
   S.EnterBlock();    
 
-  std::for_each(FileInfos.begin(),FileInfos.end(),
-                S.MakeEmitter<ContentCache>());
+  // FIXME: Emit FileInfos.
+  //std::for_each(FileInfos.begin(), FileInfos.end(),
+  //              S.MakeEmitter<ContentCache>());
   
   S.ExitBlock();
   
   // Emit: MemBufferInfos
   S.EnterBlock();
 
+  /* FIXME: EMIT.
   std::for_each(MemBufferInfos.begin(), MemBufferInfos.end(),
                 S.MakeEmitter<ContentCache>());
+   */
   
   S.ExitBlock();
   
@@ -715,11 +730,11 @@ SourceManager::CreateAndRegister(llvm::Deserializer& D, FileManager& FMgr){
   
   std::vector<char> Buf;
     
-  { // Read: FileInfos.
+  /*{ // FIXME Read: FileInfos.
     llvm::Deserializer::Location BLoc = D.getCurrentBlockLocation();
     while (!D.FinishedBlock(BLoc))
     ContentCache::ReadToSourceManager(D,*M,&FMgr,Buf);
-  }
+  }*/
     
   { // Read: MemBufferInfos.
     llvm::Deserializer::Location BLoc = D.getCurrentBlockLocation();