Implement support for globally associating abbrevs with block IDs, which

relieves us from having to emit the abbrevs into each instance of the block.
This shrinks kc.bit from 3368K to 3333K, but will be a more significant win
once instructions are abbreviated.

The VST went from:

  Block ID #14 (VALUE_SYMTAB):
      Num Instances: 2345
         Total Size: 1.29508e+07b/1.61885e+06B/404713W
       Average Size: 5522.73b/690.342B/172.585W
          % of file: 48.0645
  Tot/Avg SubBlocks: 0/0
    Tot/Avg Abbrevs: 7035/3
    Tot/Avg Records: 120924/51.5667
      % Abbrev Recs: 100

to:

  Block ID #14 (VALUE_SYMTAB):
      Num Instances: 2345
         Total Size: 1.26713e+07b/1.58391e+06B/395978W
       Average Size: 5403.53b/675.442B/168.86W
          % of file: 47.5198
  Tot/Avg SubBlocks: 0/0
    Tot/Avg Abbrevs: 0/0
    Tot/Avg Records: 120924/51.5667
      % Abbrev Recs: 100

because we didn't emit the same 3 abbrevs 2345 times :)


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

3 files changed, 213 insertions, 12 deletions

diff --git a/include/llvm/Bitcode/BitCodes.h b/include/llvm/Bitcode/BitCodes.h
index d9a5874966..2cf8b7b723 100644
--- a/include/llvm/Bitcode/BitCodes.h
+++ b/include/llvm/Bitcode/BitCodes.h
@@ -66,8 +66,9 @@ namespace bitc {
   /// BlockInfoCodes - The blockinfo block contains metadata about user-defined
   /// blocks.
   enum BlockInfoCodes {
-    BLOCKINFO_CODE_SETBID = 1,  // SETBID: [blockid#]
-    BLOCKINFO_CODE_ABBREV = 2   // ABBREV: [standard abbrev encoding]
+    BLOCKINFO_CODE_SETBID = 1  // SETBID: [blockid#]
+    // DEFINE_ABBREV has magic semantics here, applying to the current SETBID'd
+    // block, instead of the BlockInfo block.
     // BLOCKNAME: give string name to block, if desired.
   };
   
diff --git a/include/llvm/Bitcode/BitstreamReader.h b/include/llvm/Bitcode/BitstreamReader.h
index 2a3e412f78..c15c0864e6 100644
--- a/include/llvm/Bitcode/BitstreamReader.h
+++ b/include/llvm/Bitcode/BitstreamReader.h
@@ -48,6 +48,14 @@ class BitstreamReader {
   /// BlockScope - This tracks the codesize of parent blocks.
   SmallVector<Block, 8> BlockScope;
 
+  /// BlockInfo - This contains information emitted to BLOCKINFO_BLOCK blocks.
+  /// These describe abbreviations that all blocks of the specified ID inherit.
+  struct BlockInfo {
+    unsigned BlockID;
+    std::vector<BitCodeAbbrev*> Abbrevs;
+  };
+  std::vector<BlockInfo> BlockInfoRecords;
+  
   /// FirstChar - This remembers the first byte of the stream.
   const unsigned char *FirstChar;
 public:
@@ -82,6 +90,15 @@ public:
       for (unsigned i = 0, e = Abbrevs.size(); i != e; ++i)
         Abbrevs[i]->dropRef();
     }
+    
+    // Free the BlockInfoRecords.
+    while (!BlockInfoRecords.empty()) {
+      BlockInfo &Info = BlockInfoRecords.back();
+      // Free blockinfo abbrev info.
+      for (unsigned i = 0, e = Info.Abbrevs.size(); i != e; ++i)
+        Info.Abbrevs[i]->dropRef();
+      BlockInfoRecords.pop_back();
+    }
   }
   
   bool AtEndOfStream() const { return NextChar == LastChar; }
@@ -206,6 +223,22 @@ public:
   // Block Manipulation
   //===--------------------------------------------------------------------===//
   
+private:
+  /// getBlockInfo - If there is block info for the specified ID, return it,
+  /// otherwise return null.
+  BlockInfo *getBlockInfo(unsigned BlockID) {
+    // Common case, the most recent entry matches BlockID.
+    if (!BlockInfoRecords.empty() && BlockInfoRecords.back().BlockID == BlockID)
+      return &BlockInfoRecords.back();
+    
+    for (unsigned i = 0, e = BlockInfoRecords.size(); i != e; ++i)
+      if (BlockInfoRecords[i].BlockID == BlockID)
+        return &BlockInfoRecords[i];
+    return 0;
+  }
+public:
+  
+  
   // Block header:
   //    [ENTER_SUBBLOCK, blockid, newcodelen, <align4bytes>, blocklen]
 
@@ -236,10 +269,19 @@ public:
   
   /// EnterSubBlock - Having read the ENTER_SUBBLOCK abbrevid, read and enter
   /// the block, returning the BlockID of the block we just entered.
-  bool EnterSubBlock(unsigned *NumWordsP = 0) {
+  bool EnterSubBlock(unsigned BlockID, unsigned *NumWordsP = 0) {
+    // Save the current block's state on BlockScope.
     BlockScope.push_back(Block(CurCodeSize));
     BlockScope.back().PrevAbbrevs.swap(CurAbbrevs);
     
+    // Add the abbrevs specific to this block to the CurAbbrevs list.
+    if (BlockInfo *Info = getBlockInfo(BlockID)) {
+      for (unsigned i = 0, e = Info->Abbrevs.size(); i != e; ++i) {
+        CurAbbrevs.push_back(Info->Abbrevs[i]);
+        CurAbbrevs.back()->addRef();
+      }
+    }
+    
     // Get the codesize of this block.
     CurCodeSize = ReadVBR(bitc::CodeLenWidth);
     SkipToWord();
@@ -352,6 +394,64 @@ public:
     }
     CurAbbrevs.push_back(Abbv);
   }
+  
+  //===--------------------------------------------------------------------===//
+  // BlockInfo Block Reading
+  //===--------------------------------------------------------------------===//
+  
+private:  
+  BlockInfo &getOrCreateBlockInfo(unsigned BlockID) {
+    if (BlockInfo *BI = getBlockInfo(BlockID))
+      return *BI;
+    
+    // Otherwise, add a new record.
+    BlockInfoRecords.push_back(BlockInfo());
+    BlockInfoRecords.back().BlockID = BlockID;
+    return BlockInfoRecords.back();
+  }
+  
+public:
+    
+  bool ReadBlockInfoBlock() {
+    if (EnterSubBlock(bitc::BLOCKINFO_BLOCK_ID)) return true;
+
+    SmallVector<uint64_t, 64> Record;
+    BlockInfo *CurBlockInfo = 0;
+    
+    // Read all the records for this module.
+    while (1) {
+      unsigned Code = ReadCode();
+      if (Code == bitc::END_BLOCK)
+        return ReadBlockEnd();
+      if (Code == bitc::ENTER_SUBBLOCK) {
+        ReadSubBlockID();
+        if (SkipBlock()) return true;
+        continue;
+      }
+
+      // Read abbrev records, associate them with CurBID.
+      if (Code == bitc::DEFINE_ABBREV) {
+        if (!CurBlockInfo) return true;
+        ReadAbbrevRecord();
+        
+        // ReadAbbrevRecord installs the abbrev in CurAbbrevs.  Move it to the
+        // appropriate BlockInfo.
+        BitCodeAbbrev *Abbv = CurAbbrevs.back();
+        CurAbbrevs.pop_back();
+        CurBlockInfo->Abbrevs.push_back(Abbv);
+        continue;
+      }
+
+      // Read a record.
+      switch (ReadRecord(Code, Record)) {
+      default: break;  // Default behavior, ignore unknown content.
+      case bitc::BLOCKINFO_CODE_SETBID:
+        if (Record.size() < 1) return true;
+        CurBlockInfo = &getOrCreateBlockInfo(Record[0]);
+        break;
+      }
+    }      
+  }
 };
 
 } // End llvm namespace
diff --git a/include/llvm/Bitcode/BitstreamWriter.h b/include/llvm/Bitcode/BitstreamWriter.h
index b774181628..198a82e287 100644
--- a/include/llvm/Bitcode/BitstreamWriter.h
+++ b/include/llvm/Bitcode/BitstreamWriter.h
@@ -29,10 +29,14 @@ class BitstreamWriter {
   /// CurValue - The current value.  Only bits < CurBit are valid.
   uint32_t CurValue;
   
-  // CurCodeSize - This is the declared size of code values used for the current
-  // block, in bits.
+  /// CurCodeSize - This is the declared size of code values used for the
+  /// current block, in bits.
   unsigned CurCodeSize;
 
+  /// BlockInfoCurBID - When emitting a BLOCKINFO_BLOCK, this is the currently
+  /// selected BLOCK ID.
+  unsigned BlockInfoCurBID;
+  
   /// CurAbbrevs - Abbrevs installed at in this block.
   std::vector<BitCodeAbbrev*> CurAbbrevs;
 
@@ -46,6 +50,14 @@ class BitstreamWriter {
   /// BlockScope - This tracks the current blocks that we have entered.
   std::vector<Block> BlockScope;
   
+  /// BlockInfo - This contains information emitted to BLOCKINFO_BLOCK blocks.
+  /// These describe abbreviations that all blocks of the specified ID inherit.
+  struct BlockInfo {
+    unsigned BlockID;
+    std::vector<BitCodeAbbrev*> Abbrevs;
+  };
+  std::vector<BlockInfo> BlockInfoRecords;
+  
 public:
   BitstreamWriter(std::vector<unsigned char> &O) 
     : Out(O), CurBit(0), CurValue(0), CurCodeSize(2) {}
@@ -53,6 +65,15 @@ public:
   ~BitstreamWriter() {
     assert(CurBit == 0 && "Unflused data remaining");
     assert(BlockScope.empty() && CurAbbrevs.empty() && "Block imbalance");
+    
+    // Free the BlockInfoRecords.
+    while (!BlockInfoRecords.empty()) {
+      BlockInfo &Info = BlockInfoRecords.back();
+      // Free blockinfo abbrev info.
+      for (unsigned i = 0, e = Info.Abbrevs.size(); i != e; ++i)
+        Info.Abbrevs[i]->dropRef();
+      BlockInfoRecords.pop_back();
+    }
   }
   //===--------------------------------------------------------------------===//
   // Basic Primitives for emitting bits to the stream.
@@ -139,6 +160,19 @@ public:
   // Block Manipulation
   //===--------------------------------------------------------------------===//
   
+  /// getBlockInfo - If there is block info for the specified ID, return it,
+  /// otherwise return null.
+  BlockInfo *getBlockInfo(unsigned BlockID) {
+    // Common case, the most recent entry matches BlockID.
+    if (!BlockInfoRecords.empty() && BlockInfoRecords.back().BlockID == BlockID)
+      return &BlockInfoRecords.back();
+    
+    for (unsigned i = 0, e = BlockInfoRecords.size(); i != e; ++i)
+      if (BlockInfoRecords[i].BlockID == BlockID)
+        return &BlockInfoRecords[i];
+    return 0;
+  }
+  
   void EnterSubblock(unsigned BlockID, unsigned CodeLen) {
     // Block header:
     //    [ENTER_SUBBLOCK, blockid, newcodelen, <align4bytes>, blocklen]
@@ -146,13 +180,28 @@ public:
     EmitVBR(BlockID, bitc::BlockIDWidth);
     EmitVBR(CodeLen, bitc::CodeLenWidth);
     FlushToWord();
-    BlockScope.push_back(Block(CurCodeSize, Out.size()/4));
-    BlockScope.back().PrevAbbrevs.swap(CurAbbrevs);
+    
+    unsigned BlockSizeWordLoc = Out.size();
+    unsigned OldCodeSize = CurCodeSize;
     
     // Emit a placeholder, which will be replaced when the block is popped.
     Emit(0, bitc::BlockSizeWidth);
     
     CurCodeSize = CodeLen;
+    
+    // Push the outer block's abbrev set onto the stack, start out with an
+    // empty abbrev set.
+    BlockScope.push_back(Block(OldCodeSize, BlockSizeWordLoc/4));
+    BlockScope.back().PrevAbbrevs.swap(CurAbbrevs);
+
+    // If there is a blockinfo for this BlockID, add all the predefined abbrevs
+    // to the abbrev list.
+    if (BlockInfo *Info = getBlockInfo(BlockID)) {
+      for (unsigned i = 0, e = Info->Abbrevs.size(); i != e; ++i) {
+        CurAbbrevs.push_back(Info->Abbrevs[i]);
+        Info->Abbrevs[i]->addRef();
+      }
+    }
   }
   
   void ExitBlock() {
@@ -261,15 +310,14 @@ public:
         EmitVBR64(Vals[i], 6);
     }
   }
-  
+
   //===--------------------------------------------------------------------===//
   // Abbrev Emission
   //===--------------------------------------------------------------------===//
   
-  /// EmitAbbrev - This emits an abbreviation to the stream.  Note that this
-  /// method takes ownership of the specified abbrev.
-  unsigned EmitAbbrev(BitCodeAbbrev *Abbv) {
-    // Emit the abbreviation as a record.
+private:
+  // Emit the abbreviation as a DEFINE_ABBREV record.
+  void EncodeAbbrev(BitCodeAbbrev *Abbv) {
     EmitCode(bitc::DEFINE_ABBREV);
     EmitVBR(Abbv->getNumOperandInfos(), 5);
     for (unsigned i = 0, e = Abbv->getNumOperandInfos(); i != e; ++i) {
@@ -283,10 +331,62 @@ public:
           EmitVBR64(Op.getEncodingData(), 5);
       }
     }
+  }
+public:
     
+  /// EmitAbbrev - This emits an abbreviation to the stream.  Note that this
+  /// method takes ownership of the specified abbrev.
+  unsigned EmitAbbrev(BitCodeAbbrev *Abbv) {
+    // Emit the abbreviation as a record.
+    EncodeAbbrev(Abbv);
     CurAbbrevs.push_back(Abbv);
     return CurAbbrevs.size()-1+bitc::FIRST_APPLICATION_ABBREV;
   }
+  
+  //===--------------------------------------------------------------------===//
+  // BlockInfo Block Emission
+  //===--------------------------------------------------------------------===//
+  
+  /// EnterBlockInfoBlock - Start emitting the BLOCKINFO_BLOCK.
+  void EnterBlockInfoBlock(unsigned CodeWidth) {
+    EnterSubblock(bitc::BLOCKINFO_BLOCK_ID, CodeWidth);
+    BlockInfoCurBID = -1U;
+  }
+private:  
+  /// SwitchToBlockID - If we aren't already talking about the specified block
+  /// ID, emit a BLOCKINFO_CODE_SETBID record.
+  void SwitchToBlockID(unsigned BlockID) {
+    if (BlockInfoCurBID == BlockID) return;
+    SmallVector<unsigned, 2> V;
+    V.push_back(BlockID);
+    EmitRecord(bitc::BLOCKINFO_CODE_SETBID, V);
+    BlockInfoCurBID = BlockID;
+  }
+
+  BlockInfo &getOrCreateBlockInfo(unsigned BlockID) {
+    if (BlockInfo *BI = getBlockInfo(BlockID))
+      return *BI;
+    
+    // Otherwise, add a new record.
+    BlockInfoRecords.push_back(BlockInfo());
+    BlockInfoRecords.back().BlockID = BlockID;
+    return BlockInfoRecords.back();
+  }
+  
+public:
+  
+  /// EmitBlockInfoAbbrev - Emit a DEFINE_ABBREV record for the specified
+  /// BlockID.
+  unsigned EmitBlockInfoAbbrev(unsigned BlockID, BitCodeAbbrev *Abbv) {
+    SwitchToBlockID(BlockID);
+    EncodeAbbrev(Abbv);
+    
+    // Add the abbrev to the specified block record.
+    BlockInfo &Info = getOrCreateBlockInfo(BlockID);
+    Info.Abbrevs.push_back(Abbv);
+    
+    return Info.Abbrevs.size()-1+bitc::FIRST_APPLICATION_ABBREV;
+  }
 };