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

2 files changed, 111 insertions, 46 deletions

diff --git a/include/llvm/Bitcode/Deserialize.h b/include/llvm/Bitcode/Deserialize.h
index d0ededef9f..46b111f892 100644
--- a/include/llvm/Bitcode/Deserialize.h
+++ b/include/llvm/Bitcode/Deserialize.h
@@ -137,7 +137,13 @@ public:
 
   uint64_t ReadInt();
   int64_t ReadSInt();
+  
   SerializedPtrID ReadPtrID() { return (SerializedPtrID) ReadInt(); }
+
+  SerializedPtrID ReadDiffPtrID(SerializedPtrID& PrevID) {
+    unsigned x = ReadInt();    
+    return (SerializedPtrID) (x ? (PrevID+x) : 0);
+  }
   
   
   bool ReadBool() {
@@ -183,7 +189,7 @@ public:
                           bool A1=true, bool A2=true) {
 
     SerializedPtrID ID1 = ReadPtrID();
-    SerializedPtrID ID2 = ReadPtrID();
+    SerializedPtrID ID2 = ReadDiffPtrID(ID2);
 
     P1 = (ID1) ? SerializeTrait<T1>::Create(*this) : NULL;
     if (ID1 && A1) RegisterPtr(ID1,P1);
@@ -197,8 +203,27 @@ public:
                           bool A1=true, bool A2=true, bool A3=true) {
     
     SerializedPtrID ID1 = ReadPtrID();
-    SerializedPtrID ID2 = ReadPtrID();
-    SerializedPtrID ID3 = ReadPtrID();
+    SerializedPtrID ID2 = ReadDiffPtrID(ID1);
+    SerializedPtrID ID3 = ReadDiffPtrID(ID2);
+    
+    P1 = (ID1) ? SerializeTrait<T1>::Create(*this) : NULL;
+    if (ID1 && A1) RegisterPtr(ID1,P1);    
+    
+    P2 = (ID2) ? SerializeTrait<T2>::Create(*this) : NULL;
+    if (ID2 && A2) RegisterPtr(ID2,P2);
+    
+    P3 = (ID3) ? SerializeTrait<T3>::Create(*this) : NULL;
+    if (ID3 && A3) RegisterPtr(ID3,P3);
+  }
+  
+  template <typename T1, typename T2, typename T3, typename T4>
+  void BatchReadOwnedPtrs(T1*& P1, T2*& P2, T3*& P3, T4*& P4,
+                     bool A1=true, bool A2=true, bool A3=true, bool A4=true) {
+    
+    SerializedPtrID ID1 = ReadPtrID();
+    SerializedPtrID ID2 = ReadDiffPtrID(ID1);
+    SerializedPtrID ID3 = ReadDiffPtrID(ID2);
+    SerializedPtrID ID4 = ReadDiffPtrID(ID3);
     
     P1 = (ID1) ? SerializeTrait<T1>::Create(*this) : NULL;
     if (ID1 && A1) RegisterPtr(ID1,P1);    
@@ -206,16 +231,22 @@ public:
     P2 = (ID2) ? SerializeTrait<T2>::Create(*this) : NULL;
     if (ID2 && A2) RegisterPtr(ID2,P2);
     
-    P3 = (ID3) ? SerializeTrait<T2>::Create(*this) : NULL;
+    P3 = (ID3) ? SerializeTrait<T3>::Create(*this) : NULL;
     if (ID3 && A3) RegisterPtr(ID3,P3);
+    
+    P4 = (ID4) ? SerializeTrait<T4>::Create(*this) : NULL;
+    if (ID4 && A4) RegisterPtr(ID4,P4);
   }
   
   template <typename T>
   void BatchReadOwnedPtrs(unsigned NumPtrs, T** Ptrs, bool AutoRegister=true) {
     llvm::SmallVector<SerializedPtrID,10> BatchIDVec;
+    SerializedPtrID TempPtrID;
     
-    for (unsigned i = 0; i < NumPtrs; ++i)
-      BatchIDVec.push_back(ReadPtrID());
+    for (unsigned i = 0; i < NumPtrs; ++i) {
+      TempPtrID = i ? ReadDiffPtrID(TempPtrID) : ReadPtrID();
+      BatchIDVec.push_back(TempPtrID);
+    }
     
     for (unsigned i = 0; i < NumPtrs; ++i) {
       SerializedPtrID& PtrID = BatchIDVec[i];
@@ -232,13 +263,19 @@ public:
   template <typename T1, typename T2>
   void BatchReadOwnedPtrs(unsigned NumT1Ptrs, T1** Ptrs, T2*& P2,
                           bool A1=true, bool A2=true) {
-    
-    llvm::SmallVector<SerializedPtrID,10> BatchIDVec;
 
-    for (unsigned i = 0; i < NumT1Ptrs; ++i)
-      BatchIDVec.push_back(ReadPtrID());
-    
     SerializedPtrID ID2 = ReadPtrID();
+    SerializedPtrID TempID = ID2;
+
+    llvm::SmallVector<SerializedPtrID,10> BatchIDVec;
+    
+    for (unsigned i = 0; i < NumT1Ptrs; ++i) {
+      TempID = ReadDiffPtrID(TempID);
+      BatchIDVec.push_back(TempID);
+    }
+    
+    P2 = (ID2) ? SerializeTrait<T2>::Create(*this) : NULL;
+    if (ID2 && A2) RegisterPtr(ID2,P2);    
     
     for (unsigned i = 0; i < NumT1Ptrs; ++i) {
       SerializedPtrID& PtrID = BatchIDVec[i];
@@ -249,24 +286,31 @@ public:
         RegisterPtr(PtrID,p);
       
       Ptrs[i] = p;
-    }
-    
-    P2 = (ID2) ? SerializeTrait<T2>::Create(*this) : NULL;
-    if (ID2 && A2) RegisterPtr(ID2,P2);    
+    }    
   }    
   
   template <typename T1, typename T2, typename T3>
   void BatchReadOwnedPtrs(unsigned NumT1Ptrs, T1** Ptrs, 
                           T2*& P2, T3*& P3,
                           bool A1=true, bool A2=true, bool A3=true) {
+
+    SerializedPtrID ID2 = ReadPtrID();
+    SerializedPtrID ID3 = ReadDiffPtrID(ID2);  
+    
+    SerializedPtrID TempID = ID3;
     
     llvm::SmallVector<SerializedPtrID,10> BatchIDVec;
     
-    for (unsigned i = 0; i < NumT1Ptrs; ++i)
-      BatchIDVec.push_back(ReadPtrID());
+    for (unsigned i = 0; i < NumT1Ptrs; ++i) {
+      TempID = ReadDiffPtrID(TempID);
+      BatchIDVec.push_back(TempID);
+    }
     
-    SerializedPtrID ID2 = ReadPtrID();
-    SerializedPtrID ID3 = ReadPtrID();    
+    P2 = (ID2) ? SerializeTrait<T2>::Create(*this) : NULL;
+    if (ID2 && A2) RegisterPtr(ID2,P2);
+    
+    P3 = (ID3) ? SerializeTrait<T3>::Create(*this) : NULL;
+    if (ID3 && A3) RegisterPtr(ID3,P3);  
     
     for (unsigned i = 0; i < NumT1Ptrs; ++i) {
       SerializedPtrID& PtrID = BatchIDVec[i];
@@ -278,12 +322,6 @@ public:
       
       Ptrs[i] = p;
     }
-    
-    P2 = (ID2) ? SerializeTrait<T2>::Create(*this) : NULL;
-    if (ID2 && A2) RegisterPtr(ID2,P2);
-    
-    P3 = (ID3) ? SerializeTrait<T3>::Create(*this) : NULL;
-    if (ID3 && A3) RegisterPtr(ID3,P3);    
   }    
   
   template <typename T>
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;