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