LLVM API Documentation

BitstreamWriter.h

Go to the documentation of this file.
00001 //===- BitstreamWriter.h - Low-level bitstream writer interface -*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This header defines the BitstreamWriter class.  This class can be used to
00011 // write an arbitrary bitstream, regardless of its contents.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #ifndef BITSTREAM_WRITER_H
00016 #define BITSTREAM_WRITER_H
00017 
00018 #include "llvm/Bitcode/BitCodes.h"
00019 #include <vector>
00020 
00021 namespace llvm {
00022 
00023 class BitstreamWriter {
00024   std::vector<unsigned char> &Out;
00025 
00026   /// CurBit - Always between 0 and 31 inclusive, specifies the next bit to use.
00027   unsigned CurBit;
00028 
00029   /// CurValue - The current value.  Only bits < CurBit are valid.
00030   uint32_t CurValue;
00031 
00032   /// CurCodeSize - This is the declared size of code values used for the
00033   /// current block, in bits.
00034   unsigned CurCodeSize;
00035 
00036   /// BlockInfoCurBID - When emitting a BLOCKINFO_BLOCK, this is the currently
00037   /// selected BLOCK ID.
00038   unsigned BlockInfoCurBID;
00039 
00040   /// CurAbbrevs - Abbrevs installed at in this block.
00041   std::vector<BitCodeAbbrev*> CurAbbrevs;
00042 
00043   struct Block {
00044     unsigned PrevCodeSize;
00045     unsigned StartSizeWord;
00046     std::vector<BitCodeAbbrev*> PrevAbbrevs;
00047     Block(unsigned PCS, unsigned SSW) : PrevCodeSize(PCS), StartSizeWord(SSW) {}
00048   };
00049 
00050   /// BlockScope - This tracks the current blocks that we have entered.
00051   std::vector<Block> BlockScope;
00052 
00053   /// BlockInfo - This contains information emitted to BLOCKINFO_BLOCK blocks.
00054   /// These describe abbreviations that all blocks of the specified ID inherit.
00055   struct BlockInfo {
00056     unsigned BlockID;
00057     std::vector<BitCodeAbbrev*> Abbrevs;
00058   };
00059   std::vector<BlockInfo> BlockInfoRecords;
00060 
00061 public:
00062   explicit BitstreamWriter(std::vector<unsigned char> &O)
00063     : Out(O), CurBit(0), CurValue(0), CurCodeSize(2) {}
00064 
00065   ~BitstreamWriter() {
00066     assert(CurBit == 0 && "Unflused data remaining");
00067     assert(BlockScope.empty() && CurAbbrevs.empty() && "Block imbalance");
00068 
00069     // Free the BlockInfoRecords.
00070     while (!BlockInfoRecords.empty()) {
00071       BlockInfo &Info = BlockInfoRecords.back();
00072       // Free blockinfo abbrev info.
00073       for (unsigned i = 0, e = static_cast<unsigned>(Info.Abbrevs.size());
00074            i != e; ++i)
00075         Info.Abbrevs[i]->dropRef();
00076       BlockInfoRecords.pop_back();
00077     }
00078   }
00079 
00080   std::vector<unsigned char> &getBuffer() { return Out; }
00081 
00082   /// \brief Retrieve the current position in the stream, in bits.
00083   uint64_t GetCurrentBitNo() const { return Out.size() * 8 + CurBit; }
00084 
00085   //===--------------------------------------------------------------------===//
00086   // Basic Primitives for emitting bits to the stream.
00087   //===--------------------------------------------------------------------===//
00088 
00089   void Emit(uint32_t Val, unsigned NumBits) {
00090     assert(NumBits <= 32 && "Invalid value size!");
00091     assert((Val & ~(~0U >> (32-NumBits))) == 0 && "High bits set!");
00092     CurValue |= Val << CurBit;
00093     if (CurBit + NumBits < 32) {
00094       CurBit += NumBits;
00095       return;
00096     }
00097 
00098     // Add the current word.
00099     unsigned V = CurValue;
00100     Out.push_back((unsigned char)(V >>  0));
00101     Out.push_back((unsigned char)(V >>  8));
00102     Out.push_back((unsigned char)(V >> 16));
00103     Out.push_back((unsigned char)(V >> 24));
00104 
00105     if (CurBit)
00106       CurValue = Val >> (32-CurBit);
00107     else
00108       CurValue = 0;
00109     CurBit = (CurBit+NumBits) & 31;
00110   }
00111 
00112   void Emit64(uint64_t Val, unsigned NumBits) {
00113     if (NumBits <= 32)
00114       Emit((uint32_t)Val, NumBits);
00115     else {
00116       Emit((uint32_t)Val, 32);
00117       Emit((uint32_t)(Val >> 32), NumBits-32);
00118     }
00119   }
00120 
00121   void FlushToWord() {
00122     if (CurBit) {
00123       unsigned V = CurValue;
00124       Out.push_back((unsigned char)(V >>  0));
00125       Out.push_back((unsigned char)(V >>  8));
00126       Out.push_back((unsigned char)(V >> 16));
00127       Out.push_back((unsigned char)(V >> 24));
00128       CurBit = 0;
00129       CurValue = 0;
00130     }
00131   }
00132 
00133   void EmitVBR(uint32_t Val, unsigned NumBits) {
00134     uint32_t Threshold = 1U << (NumBits-1);
00135 
00136     // Emit the bits with VBR encoding, NumBits-1 bits at a time.
00137     while (Val >= Threshold) {
00138       Emit((Val & ((1 << (NumBits-1))-1)) | (1 << (NumBits-1)), NumBits);
00139       Val >>= NumBits-1;
00140     }
00141 
00142     Emit(Val, NumBits);
00143   }
00144 
00145   void EmitVBR64(uint64_t Val, unsigned NumBits) {
00146     if ((uint32_t)Val == Val)
00147       return EmitVBR((uint32_t)Val, NumBits);
00148 
00149     uint64_t Threshold = 1U << (NumBits-1);
00150 
00151     // Emit the bits with VBR encoding, NumBits-1 bits at a time.
00152     while (Val >= Threshold) {
00153       Emit(((uint32_t)Val & ((1 << (NumBits-1))-1)) |
00154            (1 << (NumBits-1)), NumBits);
00155       Val >>= NumBits-1;
00156     }
00157 
00158     Emit((uint32_t)Val, NumBits);
00159   }
00160 
00161   /// EmitCode - Emit the specified code.
00162   void EmitCode(unsigned Val) {
00163     Emit(Val, CurCodeSize);
00164   }
00165 
00166   // BackpatchWord - Backpatch a 32-bit word in the output with the specified
00167   // value.
00168   void BackpatchWord(unsigned ByteNo, unsigned NewWord) {
00169     Out[ByteNo++] = (unsigned char)(NewWord >>  0);
00170     Out[ByteNo++] = (unsigned char)(NewWord >>  8);
00171     Out[ByteNo++] = (unsigned char)(NewWord >> 16);
00172     Out[ByteNo  ] = (unsigned char)(NewWord >> 24);
00173   }
00174 
00175   //===--------------------------------------------------------------------===//
00176   // Block Manipulation
00177   //===--------------------------------------------------------------------===//
00178 
00179   /// getBlockInfo - If there is block info for the specified ID, return it,
00180   /// otherwise return null.
00181   BlockInfo *getBlockInfo(unsigned BlockID) {
00182     // Common case, the most recent entry matches BlockID.
00183     if (!BlockInfoRecords.empty() && BlockInfoRecords.back().BlockID == BlockID)
00184       return &BlockInfoRecords.back();
00185 
00186     for (unsigned i = 0, e = static_cast<unsigned>(BlockInfoRecords.size());
00187          i != e; ++i)
00188       if (BlockInfoRecords[i].BlockID == BlockID)
00189         return &BlockInfoRecords[i];
00190     return 0;
00191   }
00192 
00193   void EnterSubblock(unsigned BlockID, unsigned CodeLen) {
00194     // Block header:
00195     //    [ENTER_SUBBLOCK, blockid, newcodelen, <align4bytes>, blocklen]
00196     EmitCode(bitc::ENTER_SUBBLOCK);
00197     EmitVBR(BlockID, bitc::BlockIDWidth);
00198     EmitVBR(CodeLen, bitc::CodeLenWidth);
00199     FlushToWord();
00200 
00201     unsigned BlockSizeWordLoc = static_cast<unsigned>(Out.size());
00202     unsigned OldCodeSize = CurCodeSize;
00203 
00204     // Emit a placeholder, which will be replaced when the block is popped.
00205     Emit(0, bitc::BlockSizeWidth);
00206 
00207     CurCodeSize = CodeLen;
00208 
00209     // Push the outer block's abbrev set onto the stack, start out with an
00210     // empty abbrev set.
00211     BlockScope.push_back(Block(OldCodeSize, BlockSizeWordLoc/4));
00212     BlockScope.back().PrevAbbrevs.swap(CurAbbrevs);
00213 
00214     // If there is a blockinfo for this BlockID, add all the predefined abbrevs
00215     // to the abbrev list.
00216     if (BlockInfo *Info = getBlockInfo(BlockID)) {
00217       for (unsigned i = 0, e = static_cast<unsigned>(Info->Abbrevs.size());
00218            i != e; ++i) {
00219         CurAbbrevs.push_back(Info->Abbrevs[i]);
00220         Info->Abbrevs[i]->addRef();
00221       }
00222     }
00223   }
00224 
00225   void ExitBlock() {
00226     assert(!BlockScope.empty() && "Block scope imbalance!");
00227 
00228     // Delete all abbrevs.
00229     for (unsigned i = 0, e = static_cast<unsigned>(CurAbbrevs.size());
00230          i != e; ++i)
00231       CurAbbrevs[i]->dropRef();
00232 
00233     const Block &B = BlockScope.back();
00234 
00235     // Block tail:
00236     //    [END_BLOCK, <align4bytes>]
00237     EmitCode(bitc::END_BLOCK);
00238     FlushToWord();
00239 
00240     // Compute the size of the block, in words, not counting the size field.
00241     unsigned SizeInWords= static_cast<unsigned>(Out.size())/4-B.StartSizeWord-1;
00242     unsigned ByteNo = B.StartSizeWord*4;
00243 
00244     // Update the block size field in the header of this sub-block.
00245     BackpatchWord(ByteNo, SizeInWords);
00246 
00247     // Restore the inner block's code size and abbrev table.
00248     CurCodeSize = B.PrevCodeSize;
00249     BlockScope.back().PrevAbbrevs.swap(CurAbbrevs);
00250     BlockScope.pop_back();
00251   }
00252 
00253   //===--------------------------------------------------------------------===//
00254   // Record Emission
00255   //===--------------------------------------------------------------------===//
00256 
00257 private:
00258   /// EmitAbbreviatedLiteral - Emit a literal value according to its abbrev
00259   /// record.  This is a no-op, since the abbrev specifies the literal to use. 
00260   template<typename uintty>
00261   void EmitAbbreviatedLiteral(const BitCodeAbbrevOp &Op, uintty V) {
00262     assert(Op.isLiteral() && "Not a literal");
00263     // If the abbrev specifies the literal value to use, don't emit
00264     // anything.
00265     assert(V == Op.getLiteralValue() &&
00266            "Invalid abbrev for record!");
00267   }
00268   
00269   /// EmitAbbreviatedField - Emit a single scalar field value with the specified
00270   /// encoding.
00271   template<typename uintty>
00272   void EmitAbbreviatedField(const BitCodeAbbrevOp &Op, uintty V) {
00273     assert(!Op.isLiteral() && "Literals should use EmitAbbreviatedLiteral!");
00274     
00275     // Encode the value as we are commanded.
00276     switch (Op.getEncoding()) {
00277     default: assert(0 && "Unknown encoding!");
00278     case BitCodeAbbrevOp::Fixed:
00279       Emit((unsigned)V, (unsigned)Op.getEncodingData());
00280       break;
00281     case BitCodeAbbrevOp::VBR:
00282       EmitVBR64(V, (unsigned)Op.getEncodingData());
00283       break;
00284     case BitCodeAbbrevOp::Char6:
00285       Emit(BitCodeAbbrevOp::EncodeChar6((char)V), 6);
00286       break;
00287     }
00288   }
00289   
00290   /// EmitRecordWithAbbrevImpl - This is the core implementation of the record
00291   /// emission code.  If BlobData is non-null, then it specifies an array of
00292   /// data that should be emitted as part of the Blob or Array operand that is
00293   /// known to exist at the end of the the record.
00294   template<typename uintty>
00295   void EmitRecordWithAbbrevImpl(unsigned Abbrev, SmallVectorImpl<uintty> &Vals,
00296                                 const char *BlobData, unsigned BlobLen) {
00297     unsigned AbbrevNo = Abbrev-bitc::FIRST_APPLICATION_ABBREV;
00298     assert(AbbrevNo < CurAbbrevs.size() && "Invalid abbrev #!");
00299     BitCodeAbbrev *Abbv = CurAbbrevs[AbbrevNo];
00300 
00301     EmitCode(Abbrev);
00302 
00303     unsigned RecordIdx = 0;
00304     for (unsigned i = 0, e = static_cast<unsigned>(Abbv->getNumOperandInfos());
00305          i != e; ++i) {
00306       const BitCodeAbbrevOp &Op = Abbv->getOperandInfo(i);
00307       if (Op.isLiteral()) {
00308         assert(RecordIdx < Vals.size() && "Invalid abbrev/record");
00309         EmitAbbreviatedLiteral(Op, Vals[RecordIdx]);
00310         ++RecordIdx;
00311       } else if (Op.getEncoding() == BitCodeAbbrevOp::Array) {
00312         // Array case.
00313         assert(i+2 == e && "array op not second to last?");
00314         const BitCodeAbbrevOp &EltEnc = Abbv->getOperandInfo(++i);
00315 
00316         // If this record has blob data, emit it, otherwise we must have record
00317         // entries to encode this way.
00318         if (BlobData) {
00319           assert(RecordIdx == Vals.size() &&
00320                  "Blob data and record entries specified for array!");
00321           // Emit a vbr6 to indicate the number of elements present.
00322           EmitVBR(static_cast<uint32_t>(BlobLen), 6);
00323           
00324           // Emit each field.
00325           for (unsigned i = 0; i != BlobLen; ++i)
00326             EmitAbbreviatedField(EltEnc, (unsigned char)BlobData[i]);
00327           
00328           // Know that blob data is consumed for assertion below.
00329           BlobData = 0;
00330         } else {
00331           // Emit a vbr6 to indicate the number of elements present.
00332           EmitVBR(static_cast<uint32_t>(Vals.size()-RecordIdx), 6);
00333 
00334           // Emit each field.
00335           for (unsigned e = Vals.size(); RecordIdx != e; ++RecordIdx)
00336             EmitAbbreviatedField(EltEnc, Vals[RecordIdx]);
00337         }
00338       } else if (Op.getEncoding() == BitCodeAbbrevOp::Blob) {
00339         // If this record has blob data, emit it, otherwise we must have record
00340         // entries to encode this way.
00341         
00342         // Emit a vbr6 to indicate the number of elements present.
00343         if (BlobData) {
00344           EmitVBR(static_cast<uint32_t>(BlobLen), 6);
00345           assert(RecordIdx == Vals.size() &&
00346                  "Blob data and record entries specified for blob operand!");
00347         } else {
00348           EmitVBR(static_cast<uint32_t>(Vals.size()-RecordIdx), 6);
00349         }
00350         
00351         // Flush to a 32-bit alignment boundary.
00352         FlushToWord();
00353         assert((Out.size() & 3) == 0 && "Not 32-bit aligned");
00354 
00355         // Emit each field as a literal byte.
00356         if (BlobData) {
00357           for (unsigned i = 0; i != BlobLen; ++i)
00358             Out.push_back((unsigned char)BlobData[i]);
00359           
00360           // Know that blob data is consumed for assertion below.
00361           BlobData = 0;
00362         } else {
00363           for (unsigned e = Vals.size(); RecordIdx != e; ++RecordIdx) {
00364             assert(Vals[RecordIdx] < 256 && "Value too large to emit as blob");
00365             Out.push_back((unsigned char)Vals[RecordIdx]);
00366           }
00367         }
00368         // Align end to 32-bits.
00369         while (Out.size() & 3)
00370           Out.push_back(0);
00371         
00372       } else {  // Single scalar field.
00373         assert(RecordIdx < Vals.size() && "Invalid abbrev/record");
00374         EmitAbbreviatedField(Op, Vals[RecordIdx]);
00375         ++RecordIdx;
00376       }
00377     }
00378     assert(RecordIdx == Vals.size() && "Not all record operands emitted!");
00379     assert(BlobData == 0 &&
00380            "Blob data specified for record that doesn't use it!");
00381   }
00382   
00383 public:
00384 
00385   /// EmitRecord - Emit the specified record to the stream, using an abbrev if
00386   /// we have one to compress the output.
00387   template<typename uintty>
00388   void EmitRecord(unsigned Code, SmallVectorImpl<uintty> &Vals,
00389                   unsigned Abbrev = 0) {
00390     if (!Abbrev) {
00391       // If we don't have an abbrev to use, emit this in its fully unabbreviated
00392       // form.
00393       EmitCode(bitc::UNABBREV_RECORD);
00394       EmitVBR(Code, 6);
00395       EmitVBR(static_cast<uint32_t>(Vals.size()), 6);
00396       for (unsigned i = 0, e = static_cast<unsigned>(Vals.size()); i != e; ++i)
00397         EmitVBR64(Vals[i], 6);
00398       return;
00399     }
00400 
00401     // Insert the code into Vals to treat it uniformly.
00402     Vals.insert(Vals.begin(), Code);
00403     
00404     EmitRecordWithAbbrev(Abbrev, Vals);
00405   }
00406   
00407   /// EmitRecordWithAbbrev - Emit a record with the specified abbreviation.
00408   /// Unlike EmitRecord, the code for the record should be included in Vals as
00409   /// the first entry.
00410   template<typename uintty>
00411   void EmitRecordWithAbbrev(unsigned Abbrev, SmallVectorImpl<uintty> &Vals) {
00412     EmitRecordWithAbbrevImpl(Abbrev, Vals, 0, 0);
00413   }
00414   
00415   /// EmitRecordWithBlob - Emit the specified record to the stream, using an
00416   /// abbrev that includes a blob at the end.  The blob data to emit is
00417   /// specified by the pointer and length specified at the end.  In contrast to
00418   /// EmitRecord, this routine expects that the first entry in Vals is the code
00419   /// of the record.
00420   template<typename uintty>
00421   void EmitRecordWithBlob(unsigned Abbrev, SmallVectorImpl<uintty> &Vals,
00422                           const char *BlobData, unsigned BlobLen) {
00423     EmitRecordWithAbbrevImpl(Abbrev, Vals, BlobData, BlobLen);
00424   }
00425 
00426   /// EmitRecordWithArray - Just like EmitRecordWithBlob, works with records
00427   /// that end with an array.
00428   template<typename uintty>
00429   void EmitRecordWithArray(unsigned Abbrev, SmallVectorImpl<uintty> &Vals,
00430                           const char *ArrayData, unsigned ArrayLen) {
00431     EmitRecordWithAbbrevImpl(Abbrev, Vals, ArrayData, ArrayLen);
00432   }
00433   
00434   //===--------------------------------------------------------------------===//
00435   // Abbrev Emission
00436   //===--------------------------------------------------------------------===//
00437 
00438 private:
00439   // Emit the abbreviation as a DEFINE_ABBREV record.
00440   void EncodeAbbrev(BitCodeAbbrev *Abbv) {
00441     EmitCode(bitc::DEFINE_ABBREV);
00442     EmitVBR(Abbv->getNumOperandInfos(), 5);
00443     for (unsigned i = 0, e = static_cast<unsigned>(Abbv->getNumOperandInfos());
00444          i != e; ++i) {
00445       const BitCodeAbbrevOp &Op = Abbv->getOperandInfo(i);
00446       Emit(Op.isLiteral(), 1);
00447       if (Op.isLiteral()) {
00448         EmitVBR64(Op.getLiteralValue(), 8);
00449       } else {
00450         Emit(Op.getEncoding(), 3);
00451         if (Op.hasEncodingData())
00452           EmitVBR64(Op.getEncodingData(), 5);
00453       }
00454     }
00455   }
00456 public:
00457 
00458   /// EmitAbbrev - This emits an abbreviation to the stream.  Note that this
00459   /// method takes ownership of the specified abbrev.
00460   unsigned EmitAbbrev(BitCodeAbbrev *Abbv) {
00461     // Emit the abbreviation as a record.
00462     EncodeAbbrev(Abbv);
00463     CurAbbrevs.push_back(Abbv);
00464     return static_cast<unsigned>(CurAbbrevs.size())-1 +
00465       bitc::FIRST_APPLICATION_ABBREV;
00466   }
00467 
00468   //===--------------------------------------------------------------------===//
00469   // BlockInfo Block Emission
00470   //===--------------------------------------------------------------------===//
00471 
00472   /// EnterBlockInfoBlock - Start emitting the BLOCKINFO_BLOCK.
00473   void EnterBlockInfoBlock(unsigned CodeWidth) {
00474     EnterSubblock(bitc::BLOCKINFO_BLOCK_ID, CodeWidth);
00475     BlockInfoCurBID = -1U;
00476   }
00477 private:
00478   /// SwitchToBlockID - If we aren't already talking about the specified block
00479   /// ID, emit a BLOCKINFO_CODE_SETBID record.
00480   void SwitchToBlockID(unsigned BlockID) {
00481     if (BlockInfoCurBID == BlockID) return;
00482     SmallVector<unsigned, 2> V;
00483     V.push_back(BlockID);
00484     EmitRecord(bitc::BLOCKINFO_CODE_SETBID, V);
00485     BlockInfoCurBID = BlockID;
00486   }
00487 
00488   BlockInfo &getOrCreateBlockInfo(unsigned BlockID) {
00489     if (BlockInfo *BI = getBlockInfo(BlockID))
00490       return *BI;
00491 
00492     // Otherwise, add a new record.
00493     BlockInfoRecords.push_back(BlockInfo());
00494     BlockInfoRecords.back().BlockID = BlockID;
00495     return BlockInfoRecords.back();
00496   }
00497 
00498 public:
00499 
00500   /// EmitBlockInfoAbbrev - Emit a DEFINE_ABBREV record for the specified
00501   /// BlockID.
00502   unsigned EmitBlockInfoAbbrev(unsigned BlockID, BitCodeAbbrev *Abbv) {
00503     SwitchToBlockID(BlockID);
00504     EncodeAbbrev(Abbv);
00505 
00506     // Add the abbrev to the specified block record.
00507     BlockInfo &Info = getOrCreateBlockInfo(BlockID);
00508     Info.Abbrevs.push_back(Abbv);
00509 
00510     return Info.Abbrevs.size()-1+bitc::FIRST_APPLICATION_ABBREV;
00511   }
00512 };
00513 
00514 
00515 } // End llvm namespace
00516 
00517 #endif