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 = Info.Abbrevs.size(); i != e; ++i)
  74         Info.Abbrevs[i]->dropRef();
  75       BlockInfoRecords.pop_back();
  76     }
  77   }
  78   //===--------------------------------------------------------------------===//
  79   // Basic Primitives for emitting bits to the stream.
  80   //===--------------------------------------------------------------------===//
  81
  82   void Emit(uint32_t Val, unsigned NumBits) {
  83     assert(NumBits <= 32 && "Invalid value size!");
  84     assert((Val & ~(~0U >> (32-NumBits))) == 0 && "High bits set!");
  85     CurValue |= Val << CurBit;
  86     if (CurBit + NumBits < 32) {
  87       CurBit += NumBits;
  88       return;
  89     }
  90
  91     // Add the current word.
  92     unsigned V = CurValue;
  93     Out.push_back((unsigned char)(V >>  0));
  94     Out.push_back((unsigned char)(V >>  8));
  95     Out.push_back((unsigned char)(V >> 16));
  96     Out.push_back((unsigned char)(V >> 24));
  97
  98     if (CurBit)
  99       CurValue = Val >> (32-CurBit);
 100     else
 101       CurValue = 0;
 102     CurBit = (CurBit+NumBits) & 31;
 103   }
 104
 105   void Emit64(uint64_t Val, unsigned NumBits) {
 106     if (NumBits <= 32)
 107       Emit((uint32_t)Val, NumBits);
 108     else {
 109       Emit((uint32_t)Val, 32);
 110       Emit((uint32_t)(Val >> 32), NumBits-32);
 111     }
 112   }
 113
 114   void FlushToWord() {
 115     if (CurBit) {
 116       unsigned V = CurValue;
 117       Out.push_back((unsigned char)(V >>  0));
 118       Out.push_back((unsigned char)(V >>  8));
 119       Out.push_back((unsigned char)(V >> 16));
 120       Out.push_back((unsigned char)(V >> 24));
 121       CurBit = 0;
 122       CurValue = 0;
 123     }
 124   }
 125
 126   void EmitVBR(uint32_t Val, unsigned NumBits) {
 127     uint32_t Threshold = 1U << (NumBits-1);
 128
 129     // Emit the bits with VBR encoding, NumBits-1 bits at a time.
 130     while (Val >= Threshold) {
 131       Emit((Val & ((1 << (NumBits-1))-1)) | (1 << (NumBits-1)), NumBits);
 132       Val >>= NumBits-1;
 133     }
 134
 135     Emit(Val, NumBits);
 136   }
 137
 138   void EmitVBR64(uint64_t Val, unsigned NumBits) {
 139     if ((uint32_t)Val == Val)
 140       return EmitVBR((uint32_t)Val, NumBits);
 141
 142     uint64_t Threshold = 1U << (NumBits-1);
 143
 144     // Emit the bits with VBR encoding, NumBits-1 bits at a time.
 145     while (Val >= Threshold) {
 146       Emit(((uint32_t)Val & ((1 << (NumBits-1))-1)) |
 147            (1 << (NumBits-1)), NumBits);
 148       Val >>= NumBits-1;
 149     }
 150
 151     Emit((uint32_t)Val, NumBits);
 152   }
 153
 154   /// EmitCode - Emit the specified code.
 155   void EmitCode(unsigned Val) {
 156     Emit(Val, CurCodeSize);
 157   }
 158
 159   //===--------------------------------------------------------------------===//
 160   // Block Manipulation
 161   //===--------------------------------------------------------------------===//
 162
 163   /// getBlockInfo - If there is block info for the specified ID, return it,
 164   /// otherwise return null.
 165   BlockInfo *getBlockInfo(unsigned BlockID) {
 166     // Common case, the most recent entry matches BlockID.
 167     if (!BlockInfoRecords.empty() && BlockInfoRecords.back().BlockID == BlockID)
 168       return &BlockInfoRecords.back();
 169
 170     for (unsigned i = 0, e = BlockInfoRecords.size(); i != e; ++i)
 171       if (BlockInfoRecords[i].BlockID == BlockID)
 172         return &BlockInfoRecords[i];
 173     return 0;
 174   }
 175
 176   void EnterSubblock(unsigned BlockID, unsigned CodeLen) {
 177     // Block header:
 178     //    [ENTER_SUBBLOCK, blockid, newcodelen, <align4bytes>, blocklen]
 179     EmitCode(bitc::ENTER_SUBBLOCK);
 180     EmitVBR(BlockID, bitc::BlockIDWidth);
 181     EmitVBR(CodeLen, bitc::CodeLenWidth);
 182     FlushToWord();
 183
 184     unsigned BlockSizeWordLoc = Out.size();
 185     unsigned OldCodeSize = CurCodeSize;
 186
 187     // Emit a placeholder, which will be replaced when the block is popped.
 188     Emit(0, bitc::BlockSizeWidth);
 189
 190     CurCodeSize = CodeLen;
 191
 192     // Push the outer block's abbrev set onto the stack, start out with an
 193     // empty abbrev set.
 194     BlockScope.push_back(Block(OldCodeSize, BlockSizeWordLoc/4));
 195     BlockScope.back().PrevAbbrevs.swap(CurAbbrevs);
 196
 197     // If there is a blockinfo for this BlockID, add all the predefined abbrevs
 198     // to the abbrev list.
 199     if (BlockInfo *Info = getBlockInfo(BlockID)) {
 200       for (unsigned i = 0, e = Info->Abbrevs.size(); i != e; ++i) {
 201         CurAbbrevs.push_back(Info->Abbrevs[i]);
 202         Info->Abbrevs[i]->addRef();
 203       }
 204     }
 205   }
 206
 207   void ExitBlock() {
 208     assert(!BlockScope.empty() && "Block scope imbalance!");
 209
 210     // Delete all abbrevs.
 211     for (unsigned i = 0, e = CurAbbrevs.size(); i != e; ++i)
 212       CurAbbrevs[i]->dropRef();
 213
 214     const Block &B = BlockScope.back();
 215
 216     // Block tail:
 217     //    [END_BLOCK, <align4bytes>]
 218     EmitCode(bitc::END_BLOCK);
 219     FlushToWord();
 220
 221     // Compute the size of the block, in words, not counting the size field.
 222     unsigned SizeInWords = Out.size()/4-B.StartSizeWord - 1;
 223     unsigned ByteNo = B.StartSizeWord*4;
 224
 225     // Update the block size field in the header of this sub-block.
 226     Out[ByteNo++] = (unsigned char)(SizeInWords >>  0);
 227     Out[ByteNo++] = (unsigned char)(SizeInWords >>  8);
 228     Out[ByteNo++] = (unsigned char)(SizeInWords >> 16);
 229     Out[ByteNo++] = (unsigned char)(SizeInWords >> 24);
 230
 231     // Restore the inner block's code size and abbrev table.
 232     CurCodeSize = B.PrevCodeSize;
 233     BlockScope.back().PrevAbbrevs.swap(CurAbbrevs);
 234     BlockScope.pop_back();
 235   }
 236
 237   //===--------------------------------------------------------------------===//
 238   // Record Emission
 239   //===--------------------------------------------------------------------===//
 240
 241 private:
 242   /// EmitAbbreviatedField - Emit a single scalar field value with the specified
 243   /// encoding.
 244   template<typename uintty>
 245   void EmitAbbreviatedField(const BitCodeAbbrevOp &Op, uintty V) {
 246     if (Op.isLiteral()) {
 247       // If the abbrev specifies the literal value to use, don't emit
 248       // anything.
 249       assert(V == Op.getLiteralValue() &&
 250              "Invalid abbrev for record!");
 251       return;
 252     }
 253
 254     // Encode the value as we are commanded.
 255     switch (Op.getEncoding()) {
 256     default: assert(0 && "Unknown encoding!");
 257     case BitCodeAbbrevOp::Fixed:
 258       Emit((unsigned)V, (unsigned)Op.getEncodingData());
 259       break;
 260     case BitCodeAbbrevOp::VBR:
 261       EmitVBR64(V, (unsigned)Op.getEncodingData());
 262       break;
 263     case BitCodeAbbrevOp::Char6:
 264       Emit(BitCodeAbbrevOp::EncodeChar6((char)V), 6);
 265       break;
 266     }
 267   }
 268 public:
 269
 270   /// EmitRecord - Emit the specified record to the stream, using an abbrev if
 271   /// we have one to compress the output.
 272   template<typename uintty>
 273   void EmitRecord(unsigned Code, SmallVectorImpl<uintty> &Vals,
 274                   unsigned Abbrev = 0) {
 275     if (Abbrev) {
 276       unsigned AbbrevNo = Abbrev-bitc::FIRST_APPLICATION_ABBREV;
 277       assert(AbbrevNo < CurAbbrevs.size() && "Invalid abbrev #!");
 278       BitCodeAbbrev *Abbv = CurAbbrevs[AbbrevNo];
 279
 280       EmitCode(Abbrev);
 281
 282       // Insert the code into Vals to treat it uniformly.
 283       Vals.insert(Vals.begin(), Code);
 284
 285       unsigned RecordIdx = 0;
 286       for (unsigned i = 0, e = Abbv->getNumOperandInfos(); i != e; ++i) {
 287         const BitCodeAbbrevOp &Op = Abbv->getOperandInfo(i);
 288         if (Op.isLiteral() || Op.getEncoding() != BitCodeAbbrevOp::Array) {
 289           assert(RecordIdx < Vals.size() && "Invalid abbrev/record");
 290           EmitAbbreviatedField(Op, Vals[RecordIdx]);
 291           ++RecordIdx;
 292         } else {
 293           // Array case.
 294           assert(i+2 == e && "array op not second to last?");
 295           const BitCodeAbbrevOp &EltEnc = Abbv->getOperandInfo(++i);
 296
 297           // Emit a vbr6 to indicate the number of elements present.
 298           EmitVBR(Vals.size()-RecordIdx, 6);
 299
 300           // Emit each field.
 301           for (; RecordIdx != Vals.size(); ++RecordIdx)
 302             EmitAbbreviatedField(EltEnc, Vals[RecordIdx]);
 303         }
 304       }
 305       assert(RecordIdx == Vals.size() && "Not all record operands emitted!");
 306     } else {
 307       // If we don't have an abbrev to use, emit this in its fully unabbreviated
 308       // form.
 309       EmitCode(bitc::UNABBREV_RECORD);
 310       EmitVBR(Code, 6);
 311       EmitVBR(Vals.size(), 6);
 312       for (unsigned i = 0, e = Vals.size(); i != e; ++i)
 313         EmitVBR64(Vals[i], 6);
 314     }
 315   }
 316
 317   //===--------------------------------------------------------------------===//
 318   // Abbrev Emission
 319   //===--------------------------------------------------------------------===//
 320
 321 private:
 322   // Emit the abbreviation as a DEFINE_ABBREV record.
 323   void EncodeAbbrev(BitCodeAbbrev *Abbv) {
 324     EmitCode(bitc::DEFINE_ABBREV);
 325     EmitVBR(Abbv->getNumOperandInfos(), 5);
 326     for (unsigned i = 0, e = Abbv->getNumOperandInfos(); i != e; ++i) {
 327       const BitCodeAbbrevOp &Op = Abbv->getOperandInfo(i);
 328       Emit(Op.isLiteral(), 1);
 329       if (Op.isLiteral()) {
 330         EmitVBR64(Op.getLiteralValue(), 8);
 331       } else {
 332         Emit(Op.getEncoding(), 3);
 333         if (Op.hasEncodingData())
 334           EmitVBR64(Op.getEncodingData(), 5);
 335       }
 336     }
 337   }
 338 public:
 339
 340   /// EmitAbbrev - This emits an abbreviation to the stream.  Note that this
 341   /// method takes ownership of the specified abbrev.
 342   unsigned EmitAbbrev(BitCodeAbbrev *Abbv) {
 343     // Emit the abbreviation as a record.
 344     EncodeAbbrev(Abbv);
 345     CurAbbrevs.push_back(Abbv);
 346     return CurAbbrevs.size()-1+bitc::FIRST_APPLICATION_ABBREV;
 347   }
 348
 349   //===--------------------------------------------------------------------===//
 350   // BlockInfo Block Emission
 351   //===--------------------------------------------------------------------===//
 352
 353   /// EnterBlockInfoBlock - Start emitting the BLOCKINFO_BLOCK.
 354   void EnterBlockInfoBlock(unsigned CodeWidth) {
 355     EnterSubblock(bitc::BLOCKINFO_BLOCK_ID, CodeWidth);
 356     BlockInfoCurBID = -1U;
 357   }
 358 private:
 359   /// SwitchToBlockID - If we aren't already talking about the specified block
 360   /// ID, emit a BLOCKINFO_CODE_SETBID record.
 361   void SwitchToBlockID(unsigned BlockID) {
 362     if (BlockInfoCurBID == BlockID) return;
 363     SmallVector<unsigned, 2> V;
 364     V.push_back(BlockID);
 365     EmitRecord(bitc::BLOCKINFO_CODE_SETBID, V);
 366     BlockInfoCurBID = BlockID;
 367   }
 368
 369   BlockInfo &getOrCreateBlockInfo(unsigned BlockID) {
 370     if (BlockInfo *BI = getBlockInfo(BlockID))
 371       return *BI;
 372
 373     // Otherwise, add a new record.
 374     BlockInfoRecords.push_back(BlockInfo());
 375     BlockInfoRecords.back().BlockID = BlockID;
 376     return BlockInfoRecords.back();
 377   }
 378
 379 public:
 380
 381   /// EmitBlockInfoAbbrev - Emit a DEFINE_ABBREV record for the specified
 382   /// BlockID.
 383   unsigned EmitBlockInfoAbbrev(unsigned BlockID, BitCodeAbbrev *Abbv) {
 384     SwitchToBlockID(BlockID);
 385     EncodeAbbrev(Abbv);
 386
 387     // Add the abbrev to the specified block record.
 388     BlockInfo &Info = getOrCreateBlockInfo(BlockID);
 389     Info.Abbrevs.push_back(Abbv);
 390
 391     return Info.Abbrevs.size()-1+bitc::FIRST_APPLICATION_ABBREV;
 392   }
 393 };
 394
 395
 396 } // End llvm namespace
 397
 398 #endif