Bitcode streaming

include/llvm/Bitcode/BitstreamReader.h

 //===- BitstreamReader.h - Low-level bitstream reader interface -*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This header defines the BitstreamReader class.  This class can be used to
 // read an arbitrary bitstream, regardless of its contents.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef BITSTREAM_READER_H
 #define BITSTREAM_READER_H
 
+#include "llvm/ADT/OwningPtr.h"
 #include "llvm/Bitcode/BitCodes.h"
+#include "llvm/Bitcode/BitcodeStream.h"
 #include <climits>
 #include <string>
 #include <vector>
 
 namespace llvm {
 
   class Deserializer;
 
+class BitstreamVector {

[nlewycky, 2011/11/05 00:45:06]

This interface doesn't act much like a std::vector. "getEndPos()" is really just
vector::size. Maybe we should just rename it "BitstreamBytes"?

+public:
+  BitstreamVector() { }
+
+  virtual ~BitstreamVector() { }
+
+  // Is Pos the ending file position (one byte past the last valid byte).

[nlewycky, 2011/11/05 00:45:06]

"Is Pos the ending file position (one byte past the last valid byte)."

Huh? Did you mean "Determine whether Pos is the ending file position"?

[(google.com) Derek Schuff, 2011/11/08 00:53:23]

Done.

+  // May block until Pos bytes have been read, or EOF is reached.
+  virtual bool isEndPos(size_t Pos) = 0;
+
+  // Returns the ending file position (one byte past the last valid byte).
+  // May block until EOF is reached.
+  virtual size_t getEndPos()  = 0;

[nlewycky, 2011/11/05 00:45:06]

Extra space in "()  = 0".

[(google.com) Derek Schuff, 2011/11/08 00:53:23]

Done.

+
+  // Returns true if seeking to Pos is within the file or one past the end.
+  // May block until Pos bytes have been read, or EOF is reached.
+  virtual bool canSkipToPos(size_t Pos) = 0;
+
+  // Returns the in memory address of Pos from the beginning of the file.
+  // May block until Pos bytes have been read, or EOF is reached.
+  // Note that the first byte past the end may be skipped to, but may not have
+  // its address taken.
+  virtual const unsigned char* addressOf(size_t Pos) = 0;
+
+  // Returns the character at Pos from the beginning of the file.
+  // May block until Pos bytes have been read, or EOF is reached.
+  virtual unsigned char operator[](size_t Pos) = 0;
+
+private:
+  BitstreamVector(const BitstreamVector&);  // NOT IMPLEMENTED
+  void operator=(const BitstreamVector&);  // NOT IMPLEMENTED
+};
+
+class MemoryBitstreamVector : public BitstreamVector {
+public:
+  MemoryBitstreamVector() { }
+
+  MemoryBitstreamVector(const unsigned char* Start, const unsigned char* End)
+      : FirstChar(Start), LastChar(End) {
+  }
+
+  virtual ~MemoryBitstreamVector() { }
+
+  virtual bool isEndPos(size_t Pos) {
+    return Pos == static_cast<size_t>(LastChar-FirstChar);
+  }
+
+  virtual size_t getEndPos() {
+    return static_cast<size_t>(LastChar-FirstChar);
+  }
+
+  virtual bool canSkipToPos(size_t Pos) {
+    return Pos <= static_cast<size_t>(LastChar-FirstChar);
+  }
+
+  virtual const unsigned char* addressOf(size_t Pos) {
+    assert(canSkipToPos(Pos) && Pos != static_cast<size_t>(LastChar-FirstChar)
+           && "taking address outside of buffer");
+    return FirstChar + Pos;
+  }
+
+  virtual unsigned char operator [](size_t Pos) {

[nlewycky, 2011/11/05 00:45:06]

This is confusing. Should it instead be returning a reference? Or should the
method be const?

[(google.com) Derek Schuff, 2011/11/08 00:53:23]

This container isn't supposed to be mutable. also, any of these functions can
require the streaming version to fetch more bytes.
On 2011/11/05 00:45:06, nlewycky wrote:
Done.

+    assert(canSkipToPos(Pos) && Pos != static_cast<size_t>(LastChar-FirstChar)
+               && "indexing outside of buffer");

[nlewycky, 2011/11/05 00:45:06]

Bad indent. (Can the && go on the previous line? Would it fit? Same as in
addressOf).

[(google.com) Derek Schuff, 2011/11/08 00:53:23]

Done.

+    return *(FirstChar + Pos);
+  }
+
+private:
+  const unsigned char* FirstChar;
+  const unsigned char* LastChar;
+
+  MemoryBitstreamVector(const MemoryBitstreamVector&);  // NOT IMPLEMENTED
+  void operator=(const MemoryBitstreamVector&);  // NOT IMPLEMENTED
+};
+
+class LazyBitstreamVector : public BitstreamVector {
+public:
+  LazyBitstreamVector(BitcodeStreamer* streamer) : Bytes(kChunkSize),

[nlewycky, 2011/11/05 00:45:06]

Please most the constructor list to starting on the following line.

[(google.com) Derek Schuff, 2011/11/08 00:53:23]

Done.

+    Streamer(streamer), BytesRead(0), BytesSkipped(0), BitcodeSize(0),
+    EOFReached(false) {
+    BytesRead = streamer->GetBytes(&Bytes[0], kChunkSize);
+  }
+
+  virtual ~LazyBitstreamVector() {}
+
+  virtual bool isEndPos(size_t Pos) {
+    if (BitcodeSize) return Pos == BitcodeSize;
+    fetchToPos(Pos);
+    return Pos == BytesRead;
+  }
+
+  virtual size_t getEndPos() {
+    if (BitcodeSize) return BitcodeSize;
+    size_t pos = BytesRead + kChunkSize;
+    // keep fetching until we run out of bytes
+    while(fetchToPos(pos)) pos += kChunkSize;
+    return BitcodeSize;
+  }
+
+  // If the bitcode has a header, then its size is known, and we don't have to
+  // block until we actually want to read it.
+  virtual bool canSkipToPos(size_t Pos) {
+    if (BitcodeSize && Pos <= BitcodeSize) return true;
+    return fetchToPos(Pos) || Pos == BitcodeSize;
+  }
+
+  virtual const unsigned char* addressOf(size_t Pos) {
+    assert(0 && "addressOf inside streaming vectors not allowed");
+    return NULL;
+  }
+
+  virtual unsigned char operator [](size_t Pos) {
+    fetchToPos(Pos);
+    assert(Pos < BytesRead && "indexing outside of buffer");
+    return Bytes[Pos + BytesSkipped];
+  }
+
+  // Drop s bytes from the front of the vector, pushing the positions of the
+  // remaining bytes down by s. This is used to skip past the bitcode header,
+  // since we don't know a priori if it's present, and we can't put bytes
+  // back into the stream once we've read them.
+  bool dropLeadingBytes(size_t s) {
+    if (BytesRead < s) return true;
+    BytesSkipped = s;
+    BytesRead -= s;
+    return false;
+  }
+
+  void setKnownBitcodeSize(size_t size) {
+    BitcodeSize = size;
+  }
+
+private:
+  const static uint32_t kChunkSize = 4096;
+  std::vector<unsigned char> Bytes;
+  OwningPtr<BitcodeStreamer> Streamer;
+  size_t BytesRead;   // Bytes read from stream
+  size_t BytesSkipped;// Bytes skipped at start of stream (e.g. wrapper/header)
+  size_t BitcodeSize; // 0 if unknown, set if wrapper was seen or EOF reached
+  bool EOFReached;
+
+  // fetch enough bytes such that Pos can be read or EOF is reached
+  // (i.e. BytesRead > Pos). Return true if Pos can be read.
+  // Unlike most of the functions in BitcodeReader, returns true on success
+  bool fetchToPos(size_t Pos) {
+    if (EOFReached) return Pos < BitcodeSize;
+    while (Pos >= BytesRead) {
+      Bytes.resize(BytesRead + kChunkSize);
+      size_t bytes = Streamer->GetBytes(&Bytes[BytesRead + BytesSkipped],
+                                        kChunkSize);
+      BytesRead += bytes;
+      if (bytes < kChunkSize) {
+        if (BitcodeSize && BytesRead < Pos)
+          assert(0 && "Unexpected short read fetching bitcode");
+        if (BytesRead <= Pos) { // reached EOF/ran out of bytes
+          BitcodeSize = BytesRead;
+          EOFReached = true;
+          return false;
+        }
+      }
+    }
+    return true;
+  }
+
+  LazyBitstreamVector(const LazyBitstreamVector&);  // NOT IMPLEMENTED
+  void operator=(const LazyBitstreamVector&);  // NOT IMPLEMENTED
+};
+
 class BitstreamReader {
 public:
   /// 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::string Name;
     
     std::vector<std::pair<unsigned, std::string> > RecordNames;
   };
 private:
-  /// FirstChar/LastChar - This remembers the first and last bytes of the
-  /// stream.
-  const unsigned char *FirstChar, *LastChar;
+  OwningPtr<BitstreamVector> BSV;
   
   std::vector<BlockInfo> BlockInfoRecords;
 
   /// IgnoreBlockInfoNames - This is set to true if we don't care about the
   /// block/record name information in the BlockInfo block. Only llvm-bcanalyzer
   /// uses this.
   bool IgnoreBlockInfoNames;
   
   BitstreamReader(const BitstreamReader&);  // NOT IMPLEMENTED
   void operator=(const BitstreamReader&);  // NOT IMPLEMENTED
 public:
-  BitstreamReader() : FirstChar(0), LastChar(0), IgnoreBlockInfoNames(true) {
+  BitstreamReader() : IgnoreBlockInfoNames(true) {
   }
 
   BitstreamReader(const unsigned char *Start, const unsigned char *End) {
     IgnoreBlockInfoNames = true;
     init(Start, End);
   }
 
+  BitstreamReader(BitstreamVector* bsv) {

[nlewycky, 2011/11/05 00:45:06]

* on the right

[(google.com) Derek Schuff, 2011/11/08 00:53:23]

Done.

+    BSV.reset(bsv);
+  }
+
   void init(const unsigned char *Start, const unsigned char *End) {
-    FirstChar = Start;
-    LastChar = End;
     assert(((End-Start) & 3) == 0 &&"Bitcode stream not a multiple of 4 bytes");
+    BSV.reset(new MemoryBitstreamVector(Start, End));
   }
 
+  BitstreamVector& getBSV() { return *BSV; }

[nlewycky, 2011/11/05 00:45:06]

& on the right.

[(google.com) Derek Schuff, 2011/11/08 00:53:23]

Done.

+
   ~BitstreamReader() {
     // Free the BlockInfoRecords.
     while (!BlockInfoRecords.empty()) {
       BlockInfo &Info = BlockInfoRecords.back();
       // Free blockinfo abbrev info.
       for (unsigned i = 0, e = static_cast<unsigned>(Info.Abbrevs.size());
            i != e; ++i)
         Info.Abbrevs[i]->dropRef();
       BlockInfoRecords.pop_back();
     }
   }
   
-  const unsigned char *getFirstChar() const { return FirstChar; }
-  const unsigned char *getLastChar() const { return LastChar; }
-
   /// CollectBlockInfoNames - This is called by clients that want block/record
   /// name information.
   void CollectBlockInfoNames() { IgnoreBlockInfoNames = false; }
   bool isIgnoringBlockInfoNames() { return IgnoreBlockInfoNames; }
   
   //===--------------------------------------------------------------------===//
   // Block Manipulation
   //===--------------------------------------------------------------------===//
 
   /// hasBlockInfoRecords - Return true if we've already read and processed the
@@ skipping 23 matching lines @@
     BlockInfoRecords.push_back(BlockInfo());
     BlockInfoRecords.back().BlockID = BlockID;
     return BlockInfoRecords.back();
   }
 
 };
 
 class BitstreamCursor {
   friend class Deserializer;
   BitstreamReader *BitStream;
-  const unsigned char *NextChar;
+  size_t NextChar;
   
   /// CurWord - This is the current data we have pulled from the stream but have
   /// not returned to the client.
   uint32_t CurWord;
   
   /// BitsInCurWord - This is the number of bits in CurWord that are valid. This
   /// is always from [0...31] inclusive.
   unsigned BitsInCurWord;
   
   // CurCodeSize - This is the declared size of code values used for the current
@@ skipping 13 matching lines @@
   SmallVector<Block, 8> BlockScope;
   
 public:
   BitstreamCursor() : BitStream(0), NextChar(0) {
   }
   BitstreamCursor(const BitstreamCursor &RHS) : BitStream(0), NextChar(0) {
     operator=(RHS);
   }
   
   explicit BitstreamCursor(BitstreamReader &R) : BitStream(&R) {
-    NextChar = R.getFirstChar();
-    assert(NextChar && "Bitstream not initialized yet");
+    NextChar = 0;
     CurWord = 0;
     BitsInCurWord = 0;
     CurCodeSize = 2;
   }
   
   void init(BitstreamReader &R) {
     freeState();
     
     BitStream = &R;
-    NextChar = R.getFirstChar();
-    assert(NextChar && "Bitstream not initialized yet");
+    NextChar = 0;
     CurWord = 0;
     BitsInCurWord = 0;
     CurCodeSize = 2;
   }
   
   ~BitstreamCursor() {
     freeState();
   }
   
   void operator=(const BitstreamCursor &RHS) {
@@ skipping 37 matching lines @@
            i != e; ++i)
         Abbrevs[i]->dropRef();
     }
     BlockScope.clear();
   }
   
   /// GetAbbrevIDWidth - Return the number of bits used to encode an abbrev #.
   unsigned GetAbbrevIDWidth() const { return CurCodeSize; }
   
   bool AtEndOfStream() const {
-    return NextChar == BitStream->getLastChar() && BitsInCurWord == 0;
+    return BitStream->getBSV().isEndPos(NextChar) && BitsInCurWord == 0;
   }
   
   /// GetCurrentBitNo - Return the bit # of the bit we are reading.
   uint64_t GetCurrentBitNo() const {
-    return (NextChar-BitStream->getFirstChar())*CHAR_BIT - BitsInCurWord;
+    return NextChar*CHAR_BIT - BitsInCurWord;
   }
   
   BitstreamReader *getBitStreamReader() {
     return BitStream;
   }
   const BitstreamReader *getBitStreamReader() const {
     return BitStream;
   }
   
   
   /// JumpToBit - Reset the stream to the specified bit number.
   void JumpToBit(uint64_t BitNo) {
     uintptr_t ByteNo = uintptr_t(BitNo/8) & ~3;
     uintptr_t WordBitNo = uintptr_t(BitNo) & 31;
-    assert(ByteNo <= (uintptr_t)(BitStream->getLastChar()-
-                                 BitStream->getFirstChar()) &&
-           "Invalid location");
+    assert(BitStream->getBSV().canSkipToPos(ByteNo) && "Invalid location");
     
     // Move the cursor to the right word.
-    NextChar = BitStream->getFirstChar()+ByteNo;
+    NextChar = ByteNo;
     BitsInCurWord = 0;
     CurWord = 0;
     
     // Skip over any bits that are already consumed.
     if (WordBitNo)
       Read(static_cast<unsigned>(WordBitNo));
   }
   
   
   uint32_t Read(unsigned NumBits) {
     assert(NumBits <= 32 && "Cannot return more than 32 bits!");
     // If the field is fully contained by CurWord, return it quickly.
     if (BitsInCurWord >= NumBits) {
       uint32_t R = CurWord & ((1U << NumBits)-1);
       CurWord >>= NumBits;
       BitsInCurWord -= NumBits;
       return R;
     }
 
     // If we run out of data, stop at the end of the stream.
-    if (NextChar == BitStream->getLastChar()) {
+    if (BitStream->getBSV().isEndPos(NextChar)) {
       CurWord = 0;
       BitsInCurWord = 0;
       return 0;
     }
 
     unsigned R = CurWord;
 
     // Read the next word from the stream.
-    CurWord = (NextChar[0] <<  0) | (NextChar[1] << 8) |
-              (NextChar[2] << 16) | (NextChar[3] << 24);
+    CurWord = (BitStream->getBSV()[NextChar+0] <<  0) |

[nlewycky, 2011/11/05 00:45:06]

Extra space in "<<  0"

[(google.com) Derek Schuff, 2011/11/08 00:53:23]

Done.

+              (BitStream->getBSV()[NextChar+1] << 8) |
+              (BitStream->getBSV()[NextChar+2] << 16) |
+              (BitStream->getBSV()[NextChar+3] << 24);
     NextChar += 4;
 
     // Extract NumBits-BitsInCurWord from what we just read.
     unsigned BitsLeft = NumBits-BitsInCurWord;
 
     // Be careful here, BitsLeft is in the range [1..32] inclusive.
     R |= (CurWord & (~0U >> (32-BitsLeft))) << BitsInCurWord;
 
     // BitsLeft bits have just been used up from CurWord.
     if (BitsLeft != 32)
@@ skipping 73 matching lines @@
   /// true.
   bool SkipBlock() {
     // Read and ignore the codelen value.  Since we are skipping this block, we
     // don't care what code widths are used inside of it.
     ReadVBR(bitc::CodeLenWidth);
     SkipToWord();
     unsigned NumWords = Read(bitc::BlockSizeWidth);
 
     // Check that the block wasn't partially defined, and that the offset isn't
     // bogus.
-    const unsigned char *const SkipTo = NextChar + NumWords*4;
-    if (AtEndOfStream() || SkipTo > BitStream->getLastChar() ||
-                           SkipTo < BitStream->getFirstChar())
+    size_t SkipTo = NextChar + NumWords*4;
+    if (AtEndOfStream() || !BitStream->getBSV().canSkipToPos(SkipTo))
       return true;
 
     NextChar = SkipTo;
     return false;
   }
 
   /// EnterSubBlock - Having read the ENTER_SUBBLOCK abbrevid, enter
   /// the block, and return true if the block is valid.
   bool EnterSubBlock(unsigned BlockID, unsigned *NumWordsP = 0) {
     // Save the current block's state on BlockScope.
@@ skipping 10 matching lines @@
       }
     }
 
     // Get the codesize of this block.
     CurCodeSize = ReadVBR(bitc::CodeLenWidth);
     SkipToWord();
     unsigned NumWords = Read(bitc::BlockSizeWidth);
     if (NumWordsP) *NumWordsP = NumWords;
 
     // Validate that this block is sane.
-    if (CurCodeSize == 0 || AtEndOfStream() ||
-        NextChar+NumWords*4 > BitStream->getLastChar())
+    if (CurCodeSize == 0 || AtEndOfStream() || 0)

[nlewycky, 2011/11/05 00:45:06]

|| 0?

[(google.com) Derek Schuff, 2011/11/08 00:53:23]

Done.

+      //        !BitStream->getBSV().canSkipToPos(NextChar+NumWords*4))

[nlewycky, 2011/11/05 00:45:06]

Delete commented out code.

[(google.com) Derek Schuff, 2011/11/08 00:53:23]

Done.

       return true;
 
     return false;
   }
 
   bool ReadBlockEnd() {
     if (BlockScope.empty()) return true;
 
     // Block tail:
     //    [END_BLOCK, <align4bytes>]
@@ skipping 81 matching lines @@
 
         // Read all the elements.
         for (; NumElts; --NumElts)
           ReadAbbreviatedField(EltEnc, Vals);
       } else if (Op.getEncoding() == BitCodeAbbrevOp::Blob) {
         // Blob case.  Read the number of bytes as a vbr6.
         unsigned NumElts = ReadVBR(6);
         SkipToWord();  // 32-bit alignment
 
         // Figure out where the end of this blob will be including tail padding.
-        const unsigned char *NewEnd = NextChar+((NumElts+3)&~3);
+        size_t NewEnd = NextChar+((NumElts+3)&~3);
         
         // If this would read off the end of the bitcode file, just set the
         // record to empty and return.
-        if (NewEnd > BitStream->getLastChar()) {
+        if (!BitStream->getBSV().canSkipToPos(NewEnd)) {
           Vals.append(NumElts, 0);
-          NextChar = BitStream->getLastChar();
+          NextChar = BitStream->getBSV().getEndPos();
           break;
         }
         
         // Otherwise, read the number of bytes.  If we can return a reference to
         // the data, do so to avoid copying it.
         if (BlobStart) {
-          *BlobStart = (const char*)NextChar;
+          *BlobStart = (const char*)BitStream->getBSV().addressOf(NextChar);
           *BlobLen = NumElts;
         } else {
           for (; NumElts; ++NextChar, --NumElts)
-            Vals.push_back(*NextChar);
+            Vals.push_back(BitStream->getBSV()[NextChar]);
         }
         // Skip over tail padding.
         NextChar = NewEnd;
       } else {
         ReadAbbreviatedField(Op, Vals);
       }
     }
 
     unsigned Code = (unsigned)Vals[0];
     Vals.erase(Vals.begin());
@@ skipping 93 matching lines @@
         break;
       }
       }
     }
   }
 };
   
 } // End llvm namespace
 
 #endif