[clang] Introduce paged vector (PR #66430)

[via cfe-commits]

llvmbot wrote:


<!--LLVM PR SUMMARY COMMENT-->

@llvm/pr-subscribers-clang-modules
            
<details>
<summary>Changes</summary>
None
--
Full diff: https://github.com/llvm/llvm-project/pull/66430.diff

5 Files Affected:

- (modified) clang/include/clang/Basic/SourceManager.h (+2-1) 
- (modified) clang/include/clang/Serialization/ASTReader.h (+3-2) 
- (modified) clang/lib/Basic/SourceManager.cpp (+6-6) 
- (modified) clang/lib/Serialization/ASTReader.cpp (+5-4) 
- (added) llvm/include/llvm/ADT/PagedVector.h (+96) 


<pre>
diff --git a/clang/include/clang/Basic/SourceManager.h 
b/clang/include/clang/Basic/SourceManager.h
index 2f846502d6f3327..b1942a3d86afc37 100644
--- a/clang/include/clang/Basic/SourceManager.h
+++ b/clang/include/clang/Basic/SourceManager.h
@@ -43,6 +43,7 @@
 #include &amp;quot;llvm/ADT/DenseMap.h&amp;quot;
 #include &amp;quot;llvm/ADT/DenseSet.h&amp;quot;
 #include &amp;quot;llvm/ADT/IntrusiveRefCntPtr.h&amp;quot;
+#include &amp;quot;llvm/ADT/PagedVector.h&amp;quot;
 #include &amp;quot;llvm/ADT/PointerIntPair.h&amp;quot;
 #include &amp;quot;llvm/ADT/SmallVector.h&amp;quot;
 #include &amp;quot;llvm/ADT/StringRef.h&amp;quot;
@@ -699,7 +700,7 @@ class SourceManager : public 
RefCountedBase&amp;lt;SourceManager&amp;gt; {
   ///
   /// Negative FileIDs are indexes into this table. To get from ID to an index,
   /// use (-ID - 2).
-  SmallVector&amp;lt;SrcMgr::SLocEntry, 0&amp;gt; LoadedSLocEntryTable;
+  PagedVector&amp;lt;SrcMgr::SLocEntry&amp;gt; LoadedSLocEntryTable;
 
   /// The starting offset of the next local SLocEntry.
   ///
diff --git a/clang/include/clang/Serialization/ASTReader.h 
b/clang/include/clang/Serialization/ASTReader.h
index dc1eb21c27801fe..567aecc8246e761 100644
--- a/clang/include/clang/Serialization/ASTReader.h
+++ b/clang/include/clang/Serialization/ASTReader.h
@@ -38,6 +38,7 @@
 #include &amp;quot;llvm/ADT/DenseSet.h&amp;quot;
 #include &amp;quot;llvm/ADT/IntrusiveRefCntPtr.h&amp;quot;
 #include &amp;quot;llvm/ADT/MapVector.h&amp;quot;
+#include &amp;quot;llvm/ADT/PagedVector.h&amp;quot;
 #include &amp;quot;llvm/ADT/STLExtras.h&amp;quot;
 #include &amp;quot;llvm/ADT/SetVector.h&amp;quot;
 #include &amp;quot;llvm/ADT/SmallPtrSet.h&amp;quot;
@@ -487,7 +488,7 @@ class ASTReader
   ///
   /// When the pointer at index I is non-NULL, the type with
   /// ID = (I + 1) &amp;lt;&amp;lt; FastQual::Width has already been loaded
-  std::vector&amp;lt;QualType&amp;gt; TypesLoaded;
+  PagedVector&amp;lt;QualType&amp;gt; TypesLoaded;
 
   using GlobalTypeMapType =
       ContinuousRangeMap&amp;lt;serialization::TypeID, ModuleFile *, 4&amp;gt;;
@@ -501,7 +502,7 @@ class ASTReader
   ///
   /// When the pointer at index I is non-NULL, the declaration with ID
   /// = I + 1 has already been loaded.
-  std::vector&amp;lt;Decl *&amp;gt; DeclsLoaded;
+  PagedVector&amp;lt;Decl *&amp;gt; DeclsLoaded;
 
   using GlobalDeclMapType =
       ContinuousRangeMap&amp;lt;serialization::DeclID, ModuleFile *, 4&amp;gt;;
diff --git a/clang/lib/Basic/SourceManager.cpp 
b/clang/lib/Basic/SourceManager.cpp
index 0521ac7b30339ab..c028afe63ac85ad 100644
--- a/clang/lib/Basic/SourceManager.cpp
+++ b/clang/lib/Basic/SourceManager.cpp
@@ -458,7 +458,7 @@ SourceManager::AllocateLoadedSLocEntries(unsigned 
NumSLocEntries,
       CurrentLoadedOffset - TotalSize &amp;lt; NextLocalOffset) {
     return std::make_pair(0, 0);
   }
-  LoadedSLocEntryTable.resize(LoadedSLocEntryTable.size() + NumSLocEntries);
+  LoadedSLocEntryTable.expand(LoadedSLocEntryTable.size() + NumSLocEntries);
   SLocEntryLoaded.resize(LoadedSLocEntryTable.size());
   CurrentLoadedOffset -= TotalSize;
   int ID = LoadedSLocEntryTable.size();
@@ -2344,11 +2344,11 @@ SourceManager::MemoryBufferSizes 
SourceManager::getMemoryBufferSizes() const {
 }
 
 size_t SourceManager::getDataStructureSizes() const {
-  size_t size = llvm::capacity_in_bytes(MemBufferInfos)
-    + llvm::capacity_in_bytes(LocalSLocEntryTable)
-    + llvm::capacity_in_bytes(LoadedSLocEntryTable)
-    + llvm::capacity_in_bytes(SLocEntryLoaded)
-    + llvm::capacity_in_bytes(FileInfos);
+  size_t size = llvm::capacity_in_bytes(MemBufferInfos) +
+                llvm::capacity_in_bytes(LocalSLocEntryTable) +
+                llvm::capacity_in_bytes(LoadedSLocEntryTable.materialised()) +
+                llvm::capacity_in_bytes(SLocEntryLoaded) +
+                llvm::capacity_in_bytes(FileInfos);
 
   if (OverriddenFilesInfo)
     size += 
llvm::capacity_in_bytes(OverriddenFilesInfo-&amp;gt;OverriddenFiles);
diff --git a/clang/lib/Serialization/ASTReader.cpp 
b/clang/lib/Serialization/ASTReader.cpp
index 0952244d037a77c..18b1a9a2480a73e 100644
--- a/clang/lib/Serialization/ASTReader.cpp
+++ b/clang/lib/Serialization/ASTReader.cpp
@@ -3260,7 +3260,7 @@ llvm::Error ASTReader::ReadASTBlock(ModuleFile &amp;amp;F,
           std::make_pair(LocalBaseTypeIndex,
                          F.BaseTypeIndex - LocalBaseTypeIndex));
 
-        TypesLoaded.resize(TypesLoaded.size() + F.LocalNumTypes);
+        TypesLoaded.expand(TypesLoaded.size() + F.LocalNumTypes);
       }
       break;
     }
@@ -3290,7 +3290,7 @@ llvm::Error ASTReader::ReadASTBlock(ModuleFile &amp;amp;F,
         // module.
         F.GlobalToLocalDeclIDs[&amp;amp;F] = LocalBaseDeclID;
 
-        DeclsLoaded.resize(DeclsLoaded.size() + F.LocalNumDecls);
+        DeclsLoaded.expand(DeclsLoaded.size() + F.LocalNumDecls);
       }
       break;
     }
@@ -7944,9 +7944,10 @@ void ASTReader::PrintStats() {
   std::fprintf(stderr, &amp;quot;*** AST File Statistics:\n&amp;quot;);
 
   unsigned NumTypesLoaded =
-      TypesLoaded.size() - llvm::count(TypesLoaded, QualType());
+      TypesLoaded.size() - llvm::count(TypesLoaded.materialised(), QualType());
   unsigned NumDeclsLoaded =
-      DeclsLoaded.size() - llvm::count(DeclsLoaded, (Decl *)nullptr);
+      DeclsLoaded.size() -
+      llvm::count(DeclsLoaded.materialised(), (Decl *)nullptr);
   unsigned NumIdentifiersLoaded =
       IdentifiersLoaded.size() -
       llvm::count(IdentifiersLoaded, (IdentifierInfo *)nullptr);
diff --git a/llvm/include/llvm/ADT/PagedVector.h 
b/llvm/include/llvm/ADT/PagedVector.h
new file mode 100644
index 000000000000000..dab0d249aa706e4
--- /dev/null
+++ b/llvm/include/llvm/ADT/PagedVector.h
@@ -0,0 +1,96 @@
+//===- llvm/ADT/PagedVector.h - &amp;#x27;Lazyly allocated&amp;#x27; vectors 
--------*- C++
+//-*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM 
Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the PagedVector class.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_ADT_PAGEDVECTOR_H
+#define LLVM_ADT_PAGEDVECTOR_H
+
+#include &amp;lt;vector&amp;gt;
+
+// Notice that this does not have iterators, because if you
+// have iterators it probably means you are going to touch
+// all the memory in any case, so better use a std::vector in
+// the first place.
+template &amp;lt;typename T, int PAGE_SIZE = 1024 / sizeof(T)&amp;gt; class 
PagedVector {
+  size_t Size = 0;
+  // Index of where to find a given page in the data
+  mutable std::vector&amp;lt;int&amp;gt; Lookup;
+  // Actual data
+  mutable std::vector&amp;lt;T&amp;gt; Data;
+
+public:
+  // Add a range to the vector.
+  // When vector is accessed, it will call the callback to fill the range
+  // with data.
+
+  // Lookup an element at position i.
+  // If the given range is not filled, it will be filled.
+  // If the given range is filled, return the element.
+  T &amp;amp;operator[](int Index) const { return at(Index); }
+
+  T &amp;amp;at(int Index) const {
+    auto &amp;amp;PageId = Lookup[Index / PAGE_SIZE];
+    // If the range is not filled, fill it
+    if (PageId == -1) {
+      int OldSize = Data.size();
+      PageId = OldSize / PAGE_SIZE;
+      // Allocate the memory
+      Data.resize(OldSize + PAGE_SIZE);
+      // Fill the whole capacity with empty elements
+      for (int I = 0; I &amp;lt; PAGE_SIZE; ++I) {
+        Data[I + OldSize] = T();
+      }
+    }
+    // Return the element
+    return Data[Index % PAGE_SIZE + PAGE_SIZE * PageId];
+  }
+
+  // Return the size of the vector
+  size_t capacity() const { return Lookup.size() * PAGE_SIZE; }
+
+  size_t size() const { return Size; }
+
+  // Expands the vector to the given size.
+  // If the vector is already bigger, does nothing.
+  void expand(size_t NewSize) {
+    // You cannot shrink the vector, otherwise
+    // you would have to invalidate
+    assert(NewSize &amp;gt;= Size);
+    if (NewSize &amp;lt;= Size) {
+      return;
+    }
+    if (NewSize &amp;lt;= capacity()) {
+      Size = NewSize;
+      return;
+    }
+    auto Pages = NewSize / PAGE_SIZE;
+    auto Remainder = NewSize % PAGE_SIZE;
+    if (Remainder) {
+      Pages += 1;
+    }
+    assert(Pages &amp;gt; Lookup.size());
+    Lookup.resize(Pages, -1);
+    Size = NewSize;
+  }
+
+  // Return true if the vector is empty
+  bool empty() const { return Size == 0; }
+  /// Clear the vector
+  void clear() {
+    Size = 0;
+    Lookup.clear();
+    Data.clear();
+  }
+
+  std::vector&amp;lt;T&amp;gt; const &amp;amp;materialised() const { return 
Data; }
+};
+
+#endif // LLVM_ADT_PAGEDVECTOR_H
</pre>
</details>


https://github.com/llvm/llvm-project/pull/66430
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits