LLVM API Documentation
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