include/llvm/Bitcode/BitstreamWriter.h

   1 //===- BitstreamWriter.h - Low-level bitstream writer interface -*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This header defines the BitstreamWriter class.  This class can be used to
  11 // write an arbitrary bitstream, regardless of its contents.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef BITSTREAM_WRITER_H
  16 #define BITSTREAM_WRITER_H
  17
  18 #include "llvm/Bitcode/BitCodes.h"
  19 #include <vector>
  20
  21 namespace llvm {
  22
  23 class BitstreamWriter {
  24   std::vector<unsigned char> &Out;
  25
  26   /// CurBit - Always between 0 and 31 inclusive, specifies the next bit to use.
  27   unsigned CurBit;
  28
  29   /// CurValue - The current value.  Only bits < CurBit are valid.
  30   uint32_t CurValue;
  31
  32   /// CurCodeSize - This is the declared size of code values used for the
  33   /// current block, in bits.
  34   unsigned CurCodeSize;
  35
  36   /// BlockInfoCurBID - When emitting a BLOCKINFO_BLOCK, this is the currently
  37   /// selected BLOCK ID.
  38   unsigned BlockInfoCurBID;
  39
  40   /// CurAbbrevs - Abbrevs installed at in this block.
  41   std::vector<BitCodeAbbrev*> CurAbbrevs;
  42
  43   struct Block {
  44     unsigned PrevCodeSize;
  45     unsigned StartSizeWord;
  46     std::vector<BitCodeAbbrev*> PrevAbbrevs;
  47     Block(unsigned PCS, unsigned SSW) : PrevCodeSize(PCS), StartSizeWord(SSW) {}
  48   };
  49
  50   /// BlockScope - This tracks the current blocks that we have entered.
  51   std::vector<Block> BlockScope;
  52
  53   /// BlockInfo - This contains information emitted to BLOCKINFO_BLOCK blocks.
  54   /// These describe abbreviations that all blocks of the specified ID inherit.
  55   struct BlockInfo {
  56     unsigned BlockID;
  57     std::vector<BitCodeAbbrev*> Abbrevs;
  58   };
  59   std::vector<BlockInfo> BlockInfoRecords;
  60
  61 public:
  62   explicit BitstreamWriter(std::vector<unsigned char> &O)
  63     : Out(O), CurBit(0), CurValue(0), CurCodeSize(2) {}
  64
  65   ~BitstreamWriter() {
  66     assert(CurBit == 0 && "Unflused data remaining");
  67     assert(BlockScope.empty() && CurAbbrevs.empty() && "Block imbalance");
  68
  69     // Free the BlockInfoRecords.
  70     while (!BlockInfoRecords.empty()) {
  71       BlockInfo &Info = BlockInfoRecords.back();
  72       // Free blockinfo abbrev info.
  73       for (unsigned i = 0, e = static_cast<unsigned>(Info.Abbrevs.size());
  74            i != e; ++i)
  75         Info.Abbrevs[i]->dropRef();
  76       BlockInfoRecords.pop_back();
  77     }
  78   }
  79
  80   std::vector<unsigned char> &getBuffer() { return Out; }
  81
  82   //===--------------------------------------------------------------------===//
  83   // Basic Primitives for emitting bits to the stream.
  84   //===--------------------------------------------------------------------===//
  85
  86   void Emit(uint32_t Val, unsigned NumBits) {
  87     assert(NumBits <= 32 && "Invalid value size!");
  88     assert((Val & ~(~0U >> (32-NumBits))) == 0 && "High bits set!");
  89     CurValue |= Val << CurBit;
  90     if (CurBit + NumBits < 32) {
  91       CurBit += NumBits;
  92       return;
  93     }
  94
  95     // Add the current word.
  96     unsigned V = CurValue;
  97     Out.push_back((unsigned char)(V >>  0));
  98     Out.push_back((unsigned char)(V >>  8));
  99     Out.push_back((unsigned char)(V >> 16));
 100     Out.push_back((unsigned char)(V >> 24));
 101
 102     if (CurBit)
 103       CurValue = Val >> (32-CurBit);
 104     else
 105       CurValue = 0;
 106     CurBit = (CurBit+NumBits) & 31;
 107   }
 108
 109   void Emit64(uint64_t Val, unsigned NumBits) {
 110     if (NumBits <= 32)
 111       Emit((uint32_t)Val, NumBits);
 112     else {
 113       Emit((uint32_t)Val, 32);
 114       Emit((uint32_t)(Val >> 32), NumBits-32);
 115     }
 116   }
 117
 118   void FlushToWord() {
 119     if (CurBit) {
 120       unsigned V = CurValue;
 121       Out.push_back((unsigned char)(V >>  0));
 122       Out.push_back((unsigned char)(V >>  8));
 123       Out.push_back((unsigned char)(V >> 16));
 124       Out.push_back((unsigned char)(V >> 24));
 125       CurBit = 0;
 126       CurValue = 0;
 127     }
 128   }
 129
 130   void EmitVBR(uint32_t Val, unsigned NumBits) {
 131     uint32_t Threshold = 1U << (NumBits-1);
 132
 133     // Emit the bits with VBR encoding, NumBits-1 bits at a time.
 134     while (Val >= Threshold) {
 135       Emit((Val & ((1 << (NumBits-1))-1)) | (1 << (NumBits-1)), NumBits);
 136       Val >>= NumBits-1;
 137     }
 138
 139     Emit(Val, NumBits);
 140   }
 141
 142   void EmitVBR64(uint64_t Val, unsigned NumBits) {
 143     if ((uint32_t)Val == Val)
 144       return EmitVBR((uint32_t)Val, NumBits);
 145
 146     uint64_t Threshold = 1U << (NumBits-1);
 147
 148     // Emit the bits with VBR encoding, NumBits-1 bits at a time.
 149     while (Val >= Threshold) {
 150       Emit(((uint32_t)Val & ((1 << (NumBits-1))-1)) |
 151            (1 << (NumBits-1)), NumBits);
 152       Val >>= NumBits-1;
 153     }
 154
 155     Emit((uint32_t)Val, NumBits);
 156   }
 157
 158   /// EmitCode - Emit the specified code.
 159   void EmitCode(unsigned Val) {
 160     Emit(Val, CurCodeSize);
 161   }
 162
 163   // BackpatchWord - Backpatch a 32-bit word in the output with the specified
 164   // value.
 165   void BackpatchWord(unsigned ByteNo, unsigned NewWord) {
 166     Out[ByteNo++] = (unsigned char)(NewWord >>  0);
 167     Out[ByteNo++] = (unsigned char)(NewWord >>  8);
 168     Out[ByteNo++] = (unsigned char)(NewWord >> 16);
 169     Out[ByteNo  ] = (unsigned char)(NewWord >> 24);
 170   }
 171
 172   //===--------------------------------------------------------------------===//
 173   // Block Manipulation
 174   //===--------------------------------------------------------------------===//
 175
 176   /// getBlockInfo - If there is block info for the specified ID, return it,
 177   /// otherwise return null.
 178   BlockInfo *getBlockInfo(unsigned BlockID) {
 179     // Common case, the most recent entry matches BlockID.
 180     if (!BlockInfoRecords.empty() && BlockInfoRecords.back().BlockID == BlockID)
 181       return &BlockInfoRecords.back();
 182
 183     for (unsigned i = 0, e = static_cast<unsigned>(BlockInfoRecords.size());
 184          i != e; ++i)
 185       if (BlockInfoRecords[i].BlockID == BlockID)
 186         return &BlockInfoRecords[i];
 187     return 0;
 188   }
 189
 190   void EnterSubblock(unsigned BlockID, unsigned CodeLen) {
 191     // Block header:
 192     //    [ENTER_SUBBLOCK, blockid, newcodelen, <align4bytes>, blocklen]
 193     EmitCode(bitc::ENTER_SUBBLOCK);
 194     EmitVBR(BlockID, bitc::BlockIDWidth);
 195     EmitVBR(CodeLen, bitc::CodeLenWidth);
 196     FlushToWord();
 197
 198     unsigned BlockSizeWordLoc = static_cast<unsigned>(Out.size());
 199     unsigned OldCodeSize = CurCodeSize;
 200
 201     // Emit a placeholder, which will be replaced when the block is popped.
 202     Emit(0, bitc::BlockSizeWidth);
 203
 204     CurCodeSize = CodeLen;
 205
 206     // Push the outer block's abbrev set onto the stack, start out with an
 207     // empty abbrev set.
 208     BlockScope.push_back(Block(OldCodeSize, BlockSizeWordLoc/4));
 209     BlockScope.back().PrevAbbrevs.swap(CurAbbrevs);
 210
 211     // If there is a blockinfo for this BlockID, add all the predefined abbrevs
 212     // to the abbrev list.
 213     if (BlockInfo *Info = getBlockInfo(BlockID)) {
 214       for (unsigned i = 0, e = static_cast<unsigned>(Info->Abbrevs.size());
 215            i != e; ++i) {
 216         CurAbbrevs.push_back(Info->Abbrevs[i]);
 217         Info->Abbrevs[i]->addRef();
 218       }
 219     }
 220   }
 221
 222   void ExitBlock() {
 223     assert(!BlockScope.empty() && "Block scope imbalance!");
 224
 225     // Delete all abbrevs.
 226     for (unsigned i = 0, e = static_cast<unsigned>(CurAbbrevs.size());
 227          i != e; ++i)
 228       CurAbbrevs[i]->dropRef();
 229
 230     const Block &B = BlockScope.back();
 231
 232     // Block tail:
 233     //    [END_BLOCK, <align4bytes>]
 234     EmitCode(bitc::END_BLOCK);
 235     FlushToWord();
 236
 237     // Compute the size of the block, in words, not counting the size field.
 238     unsigned SizeInWords= static_cast<unsigned>(Out.size())/4-B.StartSizeWord-1;
 239     unsigned ByteNo = B.StartSizeWord*4;
 240
 241     // Update the block size field in the header of this sub-block.
 242     BackpatchWord(ByteNo, SizeInWords);
 243
 244     // Restore the inner block's code size and abbrev table.
 245     CurCodeSize = B.PrevCodeSize;
 246     BlockScope.back().PrevAbbrevs.swap(CurAbbrevs);
 247     BlockScope.pop_back();
 248   }
 249
 250   //===--------------------------------------------------------------------===//
 251   // Record Emission
 252   //===--------------------------------------------------------------------===//
 253
 254 private:
 255   /// EmitAbbreviatedLiteral - Emit a literal value according to its abbrev
 256   /// record.  This is a no-op, since the abbrev specifies the literal to use.
 257   template<typename uintty>
 258   void EmitAbbreviatedLiteral(const BitCodeAbbrevOp &Op, uintty V) {
 259     assert(Op.isLiteral() && "Not a literal");
 260     // If the abbrev specifies the literal value to use, don't emit
 261     // anything.
 262     assert(V == Op.getLiteralValue() &&
 263            "Invalid abbrev for record!");
 264   }
 265
 266   /// EmitAbbreviatedField - Emit a single scalar field value with the specified
 267   /// encoding.
 268   template<typename uintty>
 269   void EmitAbbreviatedField(const BitCodeAbbrevOp &Op, uintty V) {
 270     assert(!Op.isLiteral() && "Literals should use EmitAbbreviatedLiteral!");
 271
 272     // Encode the value as we are commanded.
 273     switch (Op.getEncoding()) {
 274     default: assert(0 && "Unknown encoding!");
 275     case BitCodeAbbrevOp::Fixed:
 276       Emit((unsigned)V, (unsigned)Op.getEncodingData());
 277       break;
 278     case BitCodeAbbrevOp::VBR:
 279       EmitVBR64(V, (unsigned)Op.getEncodingData());
 280       break;
 281     case BitCodeAbbrevOp::Char6:
 282       Emit(BitCodeAbbrevOp::EncodeChar6((char)V), 6);
 283       break;
 284     }
 285   }
 286
 287 public:
 288
 289   /// EmitRecord - Emit the specified record to the stream, using an abbrev if
 290   /// we have one to compress the output.
 291   template<typename uintty>
 292   void EmitRecord(unsigned Code, SmallVectorImpl<uintty> &Vals,
 293                   unsigned Abbrev = 0) {
 294     if (!Abbrev) {
 295       // If we don't have an abbrev to use, emit this in its fully unabbreviated
 296       // form.
 297       EmitCode(bitc::UNABBREV_RECORD);
 298       EmitVBR(Code, 6);
 299       EmitVBR(static_cast<uint32_t>(Vals.size()), 6);
 300       for (unsigned i = 0, e = static_cast<unsigned>(Vals.size()); i != e; ++i)
 301         EmitVBR64(Vals[i], 6);
 302       return;
 303     }
 304
 305     unsigned AbbrevNo = Abbrev-bitc::FIRST_APPLICATION_ABBREV;
 306     assert(AbbrevNo < CurAbbrevs.size() && "Invalid abbrev #!");
 307     BitCodeAbbrev *Abbv = CurAbbrevs[AbbrevNo];
 308
 309     EmitCode(Abbrev);
 310
 311     // Insert the code into Vals to treat it uniformly.
 312     Vals.insert(Vals.begin(), Code);
 313
 314     unsigned RecordIdx = 0;
 315     for (unsigned i = 0, e = static_cast<unsigned>(Abbv->getNumOperandInfos());
 316          i != e; ++i) {
 317       const BitCodeAbbrevOp &Op = Abbv->getOperandInfo(i);
 318       if (Op.isLiteral()) {
 319         assert(RecordIdx < Vals.size() && "Invalid abbrev/record");
 320         EmitAbbreviatedLiteral(Op, Vals[RecordIdx]);
 321         ++RecordIdx;
 322       } else if (Op.getEncoding() == BitCodeAbbrevOp::Array) {
 323         // Array case.
 324         assert(i+2 == e && "array op not second to last?");
 325         const BitCodeAbbrevOp &EltEnc = Abbv->getOperandInfo(++i);
 326
 327         // Emit a vbr6 to indicate the number of elements present.
 328         EmitVBR(static_cast<uint32_t>(Vals.size()-RecordIdx), 6);
 329
 330         // Emit each field.
 331         for (; RecordIdx != Vals.size(); ++RecordIdx)
 332           EmitAbbreviatedField(EltEnc, Vals[RecordIdx]);
 333       } else if (Op.getEncoding() == BitCodeAbbrevOp::Blob) {
 334         // Emit a vbr6 to indicate the number of elements present.
 335         EmitVBR(static_cast<uint32_t>(Vals.size()-RecordIdx), 6);
 336         // Flush to a 32-bit alignment boundary.
 337         FlushToWord();
 338         assert((Out.size() & 3) == 0 && "Not 32-bit aligned");
 339
 340         // Emit each field as a literal byte.
 341         for (; RecordIdx != Vals.size(); ++RecordIdx) {
 342           assert(Vals[RecordIdx] < 256 && "Value too large to emit as blob");
 343           Out.push_back((unsigned char)Vals[RecordIdx]);
 344         }
 345         // Align end to 32-bits.
 346         while (Out.size() & 3)
 347           Out.push_back(0);
 348
 349       } else {  // Single scalar field.
 350         assert(RecordIdx < Vals.size() && "Invalid abbrev/record");
 351         EmitAbbreviatedField(Op, Vals[RecordIdx]);
 352         ++RecordIdx;
 353       }
 354     }
 355     assert(RecordIdx == Vals.size() && "Not all record operands emitted!");
 356   }
 357
 358   //===--------------------------------------------------------------------===//
 359   // Abbrev Emission
 360   //===--------------------------------------------------------------------===//
 361
 362 private:
 363   // Emit the abbreviation as a DEFINE_ABBREV record.
 364   void EncodeAbbrev(BitCodeAbbrev *Abbv) {
 365     EmitCode(bitc::DEFINE_ABBREV);
 366     EmitVBR(Abbv->getNumOperandInfos(), 5);
 367     for (unsigned i = 0, e = static_cast<unsigned>(Abbv->getNumOperandInfos());
 368          i != e; ++i) {
 369       const BitCodeAbbrevOp &Op = Abbv->getOperandInfo(i);
 370       Emit(Op.isLiteral(), 1);
 371       if (Op.isLiteral()) {
 372         EmitVBR64(Op.getLiteralValue(), 8);
 373       } else {
 374         Emit(Op.getEncoding(), 3);
 375         if (Op.hasEncodingData())
 376           EmitVBR64(Op.getEncodingData(), 5);
 377       }
 378     }
 379   }
 380 public:
 381
 382   /// EmitAbbrev - This emits an abbreviation to the stream.  Note that this
 383   /// method takes ownership of the specified abbrev.
 384   unsigned EmitAbbrev(BitCodeAbbrev *Abbv) {
 385     // Emit the abbreviation as a record.
 386     EncodeAbbrev(Abbv);
 387     CurAbbrevs.push_back(Abbv);
 388     return static_cast<unsigned>(CurAbbrevs.size())-1 +
 389       bitc::FIRST_APPLICATION_ABBREV;
 390   }
 391
 392   //===--------------------------------------------------------------------===//
 393   // BlockInfo Block Emission
 394   //===--------------------------------------------------------------------===//
 395
 396   /// EnterBlockInfoBlock - Start emitting the BLOCKINFO_BLOCK.
 397   void EnterBlockInfoBlock(unsigned CodeWidth) {
 398     EnterSubblock(bitc::BLOCKINFO_BLOCK_ID, CodeWidth);
 399     BlockInfoCurBID = -1U;
 400   }
 401 private:
 402   /// SwitchToBlockID - If we aren't already talking about the specified block
 403   /// ID, emit a BLOCKINFO_CODE_SETBID record.
 404   void SwitchToBlockID(unsigned BlockID) {
 405     if (BlockInfoCurBID == BlockID) return;
 406     SmallVector<unsigned, 2> V;
 407     V.push_back(BlockID);
 408     EmitRecord(bitc::BLOCKINFO_CODE_SETBID, V);
 409     BlockInfoCurBID = BlockID;
 410   }
 411
 412   BlockInfo &getOrCreateBlockInfo(unsigned BlockID) {
 413     if (BlockInfo *BI = getBlockInfo(BlockID))
 414       return *BI;
 415
 416     // Otherwise, add a new record.
 417     BlockInfoRecords.push_back(BlockInfo());
 418     BlockInfoRecords.back().BlockID = BlockID;
 419     return BlockInfoRecords.back();
 420   }
 421
 422 public:
 423
 424   /// EmitBlockInfoAbbrev - Emit a DEFINE_ABBREV record for the specified
 425   /// BlockID.
 426   unsigned EmitBlockInfoAbbrev(unsigned BlockID, BitCodeAbbrev *Abbv) {
 427     SwitchToBlockID(BlockID);
 428     EncodeAbbrev(Abbv);
 429
 430     // Add the abbrev to the specified block record.
 431     BlockInfo &Info = getOrCreateBlockInfo(BlockID);
 432     Info.Abbrevs.push_back(Abbv);
 433
 434     return Info.Abbrevs.size()-1+bitc::FIRST_APPLICATION_ABBREV;
 435   }
 436 };
 437
 438
 439 } // End llvm namespace
 440
 441 #endif