Implemented optimization for BatchEmitOwnedPtrs that we only emit one complete

SerializedPtrID, followed by the *differences* in IDs. The big idea is that
most IDs will be just be 1 off from the previous (either that or NULL, which
we encode as a difference if 0), so this will greatly reduce the encoding
space for extra IDs to just 1 bit per pointer.

So far this optimization reduces serialization of Carbon.h by only 1%, but
we aren't using any abbreviations now in the Bitcode file to properly take
advantage of this optimization.


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

1 files changed, 48 insertions, 21 deletions

diff --git a/include/llvm/Bitcode/Serialize.h b/include/llvm/Bitcode/Serialize.h
index 60d9cb2c99..8db377946c 100644
--- a/include/llvm/Bitcode/Serialize.h
+++ b/include/llvm/Bitcode/Serialize.h
@@ -45,6 +45,27 @@ public:
   void EmitCStr(const char* cstr);
   
   void EmitPtr(const void* ptr) { EmitInt(getPtrId(ptr)); }
+
+  SerializedPtrID EmitPtr(const void* ptr,bool) {
+    SerializedPtrID ptr_id = getPtrId(ptr);
+    EmitInt(ptr_id);
+    return ptr_id;
+  }
+  
+  SerializedPtrID EmitDiffPtrID(const void* ptr, SerializedPtrID PrevID) {
+    assert (!isRegistered(ptr));
+    SerializedPtrID ptr_id = getPtrId(ptr);
+
+    if (ptr_id == 0)
+      EmitInt(0);
+    else {
+      assert (ptr_id > PrevID);
+      EmitInt(ptr_id-PrevID);
+    }
+    
+    return ptr_id;    
+  }    
+    
   
   template <typename T>
   void EmitRef(const T& ref) { EmitPtr(&ref); }
@@ -57,17 +78,21 @@ public:
   
   template <typename T1, typename T2>
   void BatchEmitOwnedPtrs(T1* p1, T2* p2) {
-    EmitPtr(p1);
-    EmitPtr(p2);
+    // Optimization: Only emit the differences between the IDs.  Most of
+    // the time this difference will be "1", thus resulting in fewer bits.
+    assert (!isRegistered(p1));
+    assert (!isRegistered(p2));
+    
+    EmitDiffPtrID(p2,EmitPtr(p1,true));
+
     if (p1) SerializeTrait<T1>::Emit(*this,*p1);
     if (p2) SerializeTrait<T2>::Emit(*this,*p2);    
   }
 
   template <typename T1, typename T2, typename T3>
   void BatchEmitOwnedPtrs(T1* p1, T2* p2, T3* p3) {
-    EmitPtr(p1);
-    EmitPtr(p2);
-    EmitPtr(p3);
+    EmitDiffPtrID(p3,EmitDiffPtrID(p2,EmitPtr(p1)));
+
     if (p1) SerializeTrait<T1>::Emit(*this,*p1);
     if (p2) SerializeTrait<T2>::Emit(*this,*p2);
     if (p3) SerializeTrait<T3>::Emit(*this,*p3);
@@ -75,10 +100,8 @@ public:
   
   template <typename T1, typename T2, typename T3, typename T4>
   void BatchEmitOwnedPtrs(T1* p1, T2* p2, T3* p3, T4& p4) {
-    EmitPtr(p1);
-    EmitPtr(p2);
-    EmitPtr(p3);
-    EmitPtr(p4);
+    EmitDiffPtrID(p4,EmitDiffPtrID(p3,EmitDiffPtrID(p2,EmitPtr(p1))));
+
     if (p1) SerializeTrait<T1>::Emit(*this,*p1);
     if (p2) SerializeTrait<T2>::Emit(*this,*p2);
     if (p3) SerializeTrait<T3>::Emit(*this,*p3);
@@ -87,8 +110,12 @@ public:
 
   template <typename T>
   void BatchEmitOwnedPtrs(unsigned NumPtrs, T* const * Ptrs) {
-    for (unsigned i = 0; i < NumPtrs; ++i)
-      EmitPtr(Ptrs[i]);
+    SerializedPtrID ID;
+    
+    for (unsigned i = 0; i < NumPtrs; ++i) {
+      if (i == 0) ID = EmitPtr(Ptrs[i],true);
+      else ID = EmitDiffPtrID(Ptrs[i],ID);
+    }
 
     for (unsigned i = 0; i < NumPtrs; ++i)
       if (Ptrs[i]) SerializeTrait<T>::Emit(*this,*Ptrs[i]);
@@ -97,32 +124,32 @@ public:
   template <typename T1, typename T2>
   void BatchEmitOwnedPtrs(unsigned NumT1Ptrs, T1* const * Ptrs, T2* p2) {
     
+    SerializedPtrID ID = EmitPtr(p2,true);
+
     for (unsigned i = 0; i < NumT1Ptrs; ++i)
-      EmitPtr(Ptrs[i]);
+      ID = EmitDiffPtrID(Ptrs[i],ID);
     
-    EmitPtr(p2);
+    if (p2) SerializeTrait<T2>::Emit(*this,*p2);
     
     for (unsigned i = 0; i < NumT1Ptrs; ++i)
-      if (Ptrs[i]) SerializeTrait<T1>::Emit(*this,*Ptrs[i]);
-    
-    if (p2) SerializeTrait<T2>::Emit(*this,*p2);
+      if (Ptrs[i]) SerializeTrait<T1>::Emit(*this,*Ptrs[i]);    
   }
   
   template <typename T1, typename T2, typename T3>
   void BatchEmitOwnedPtrs(unsigned NumT1Ptrs, T1* const * Ptrs,
                           T2* p2, T3* p3) {
     
+    SerializedPtrID TempID = EmitDiffPtrID(p3,EmitPtr(p2,true));
+    
     for (unsigned i = 0; i < NumT1Ptrs; ++i)
-      EmitPtr(Ptrs[i]);
+      TempID = EmitDiffPtrID(Ptrs[i],TempID);
     
-    EmitPtr(p2);
-    EmitPtr(p3);
+    if (p2) SerializeTrait<T2>::Emit(*this,*p2);
+    if (p3) SerializeTrait<T3>::Emit(*this,*p3);
     
     for (unsigned i = 0; i < NumT1Ptrs; ++i)
       if (Ptrs[i]) SerializeTrait<T1>::Emit(*this,*Ptrs[i]);
     
-    if (p2) SerializeTrait<T2>::Emit(*this,*p2);
-    if (p3) SerializeTrait<T3>::Emit(*this,*p3);
   }
     
   bool isRegistered(const void* p) const;