include/llvm/Bitcode/BitstreamWriter.h

   1 //===- BitstreamWriter.h - Low-level bitstream writer interface -*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Chris Lattner and is distributed under
   6 // the University of Illinois Open Source 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 current
  33   // block, in bits.
  34   unsigned CurCodeSize;
  35
  36   /// CurAbbrevs - Abbrevs installed at in this block.
  37   std::vector<BitCodeAbbrev*> CurAbbrevs;
  38
  39   struct Block {
  40     unsigned PrevCodeSize;
  41     unsigned StartSizeWord;
  42     std::vector<BitCodeAbbrev*> PrevAbbrevs;
  43     Block(unsigned PCS, unsigned SSW) : PrevCodeSize(PCS), StartSizeWord(SSW) {}
  44   };
  45
  46   /// BlockScope - This tracks the current blocks that we have entered.
  47   std::vector<Block> BlockScope;
  48
  49 public:
  50   BitstreamWriter(std::vector<unsigned char> &O)
  51     : Out(O), CurBit(0), CurValue(0), CurCodeSize(2) {}
  52
  53   ~BitstreamWriter() {
  54     assert(CurBit == 0 && "Unflused data remaining");
  55     assert(BlockScope.empty() && CurAbbrevs.empty() && "Block imbalance");
  56   }
  57   //===--------------------------------------------------------------------===//
  58   // Basic Primitives for emitting bits to the stream.
  59   //===--------------------------------------------------------------------===//
  60
  61   void Emit(uint32_t Val, unsigned NumBits) {
  62     assert(NumBits <= 32 && "Invalid value size!");
  63     assert((Val & ~(~0U >> (32-NumBits))) == 0 && "High bits set!");
  64     CurValue |= Val << CurBit;
  65     if (CurBit + NumBits < 32) {
  66       CurBit += NumBits;
  67       return;
  68     }
  69
  70     // Add the current word.
  71     unsigned V = CurValue;
  72     Out.push_back((unsigned char)(V >>  0));
  73     Out.push_back((unsigned char)(V >>  8));
  74     Out.push_back((unsigned char)(V >> 16));
  75     Out.push_back((unsigned char)(V >> 24));
  76
  77     if (CurBit)
  78       CurValue = Val >> (32-CurBit);
  79     else
  80       CurValue = 0;
  81     CurBit = (CurBit+NumBits) & 31;
  82   }
  83
  84   void Emit64(uint64_t Val, unsigned NumBits) {
  85     if (NumBits <= 32)
  86       Emit((uint32_t)Val, NumBits);
  87     else {
  88       Emit((uint32_t)Val, 32);
  89       Emit((uint32_t)(Val >> 32), NumBits-32);
  90     }
  91   }
  92
  93   void FlushToWord() {
  94     if (CurBit) {
  95       unsigned V = CurValue;
  96       Out.push_back((unsigned char)(V >>  0));
  97       Out.push_back((unsigned char)(V >>  8));
  98       Out.push_back((unsigned char)(V >> 16));
  99       Out.push_back((unsigned char)(V >> 24));
 100       CurBit = 0;
 101       CurValue = 0;
 102     }
 103   }
 104
 105   void EmitVBR(uint32_t Val, unsigned NumBits) {
 106     uint32_t Threshold = 1U << (NumBits-1);
 107
 108     // Emit the bits with VBR encoding, NumBits-1 bits at a time.
 109     while (Val >= Threshold) {
 110       Emit((Val & ((1 << (NumBits-1))-1)) | (1 << (NumBits-1)), NumBits);
 111       Val >>= NumBits-1;
 112     }
 113
 114     Emit(Val, NumBits);
 115   }
 116
 117   void EmitVBR64(uint64_t Val, unsigned NumBits) {
 118     if ((uint32_t)Val == Val)
 119       return EmitVBR((uint32_t)Val, NumBits);
 120
 121     uint64_t Threshold = 1U << (NumBits-1);
 122
 123     // Emit the bits with VBR encoding, NumBits-1 bits at a time.
 124     while (Val >= Threshold) {
 125       Emit(((uint32_t)Val & ((1 << (NumBits-1))-1)) |
 126            (1 << (NumBits-1)), NumBits);
 127       Val >>= NumBits-1;
 128     }
 129
 130     Emit((uint32_t)Val, NumBits);
 131   }
 132
 133   /// EmitCode - Emit the specified code.
 134   void EmitCode(unsigned Val) {
 135     Emit(Val, CurCodeSize);
 136   }
 137
 138   //===--------------------------------------------------------------------===//
 139   // Block Manipulation
 140   //===--------------------------------------------------------------------===//
 141
 142   void EnterSubblock(unsigned BlockID, unsigned CodeLen) {
 143     // Block header:
 144     //    [ENTER_SUBBLOCK, blockid, newcodelen, <align4bytes>, blocklen]
 145     EmitCode(bitc::ENTER_SUBBLOCK);
 146     EmitVBR(BlockID, bitc::BlockIDWidth);
 147     EmitVBR(CodeLen, bitc::CodeLenWidth);
 148     FlushToWord();
 149     BlockScope.push_back(Block(CurCodeSize, Out.size()/4));
 150     BlockScope.back().PrevAbbrevs.swap(CurAbbrevs);
 151
 152     // Emit a placeholder, which will be replaced when the block is popped.
 153     Emit(0, bitc::BlockSizeWidth);
 154
 155     CurCodeSize = CodeLen;
 156   }
 157
 158   void ExitBlock() {
 159     assert(!BlockScope.empty() && "Block scope imbalance!");
 160
 161     // Delete all abbrevs.
 162     for (unsigned i = 0, e = CurAbbrevs.size(); i != e; ++i)
 163       CurAbbrevs[i]->dropRef();
 164
 165     const Block &B = BlockScope.back();
 166
 167     // Block tail:
 168     //    [END_BLOCK, <align4bytes>]
 169     EmitCode(bitc::END_BLOCK);
 170     FlushToWord();
 171
 172     // Compute the size of the block, in words, not counting the size field.
 173     unsigned SizeInWords = Out.size()/4-B.StartSizeWord - 1;
 174     unsigned ByteNo = B.StartSizeWord*4;
 175
 176     // Update the block size field in the header of this sub-block.
 177     Out[ByteNo++] = (unsigned char)(SizeInWords >>  0);
 178     Out[ByteNo++] = (unsigned char)(SizeInWords >>  8);
 179     Out[ByteNo++] = (unsigned char)(SizeInWords >> 16);
 180     Out[ByteNo++] = (unsigned char)(SizeInWords >> 24);
 181
 182     // Restore the inner block's code size and abbrev table.
 183     CurCodeSize = B.PrevCodeSize;
 184     BlockScope.back().PrevAbbrevs.swap(CurAbbrevs);
 185     BlockScope.pop_back();
 186   }
 187
 188   //===--------------------------------------------------------------------===//
 189   // Record Emission
 190   //===--------------------------------------------------------------------===//
 191
 192 private:
 193   /// EmitAbbreviatedField - Emit a single scalar field value with the specified
 194   /// encoding.
 195   template<typename uintty>
 196   void EmitAbbreviatedField(const BitCodeAbbrevOp &Op, uintty V) {
 197     if (Op.isLiteral()) {
 198       // If the abbrev specifies the literal value to use, don't emit
 199       // anything.
 200       assert(V == Op.getLiteralValue() &&
 201              "Invalid abbrev for record!");
 202       return;
 203     }
 204
 205     // Encode the value as we are commanded.
 206     switch (Op.getEncoding()) {
 207     default: assert(0 && "Unknown encoding!");
 208     case BitCodeAbbrevOp::Fixed:
 209       Emit(V, Op.getEncodingData());
 210       break;
 211     case BitCodeAbbrevOp::VBR:
 212       EmitVBR(V, Op.getEncodingData());
 213       break;
 214     }
 215   }
 216 public:
 217
 218   /// EmitRecord - Emit the specified record to the stream, using an abbrev if
 219   /// we have one to compress the output.
 220   void EmitRecord(unsigned Code, SmallVectorImpl<uint64_t> &Vals,
 221                   unsigned Abbrev = 0) {
 222     if (Abbrev) {
 223       unsigned AbbrevNo = Abbrev-bitc::FIRST_APPLICATION_ABBREV;
 224       assert(AbbrevNo < CurAbbrevs.size() && "Invalid abbrev #!");
 225       BitCodeAbbrev *Abbv = CurAbbrevs[AbbrevNo];
 226
 227       EmitCode(Abbrev);
 228
 229       // Insert the code into Vals to treat it uniformly.
 230       Vals.insert(Vals.begin(), Code);
 231
 232       unsigned RecordIdx = 0;
 233       for (unsigned i = 0, e = Abbv->getNumOperandInfos(); i != e; ++i) {
 234         assert(RecordIdx < Vals.size() && "Invalid abbrev/record");
 235         const BitCodeAbbrevOp &Op = Abbv->getOperandInfo(i);
 236         if (Op.isLiteral() || Op.getEncoding() != BitCodeAbbrevOp::Array) {
 237           EmitAbbreviatedField(Op, Vals[RecordIdx]);
 238           ++RecordIdx;
 239         } else {
 240           // Array case.
 241           assert(i+2 == e && "array op not second to last?");
 242           const BitCodeAbbrevOp &EltEnc = Abbv->getOperandInfo(++i);
 243
 244           // Emit a vbr6 to indicate the number of elements present.
 245           EmitVBR(Vals.size()-RecordIdx, 6);
 246
 247           // Emit each field.
 248           for (; RecordIdx != Vals.size(); ++RecordIdx)
 249             EmitAbbreviatedField(EltEnc, Vals[RecordIdx]);
 250         }
 251       }
 252       assert(RecordIdx == Vals.size() && "Not all record operands emitted!");
 253     } else {
 254       // If we don't have an abbrev to use, emit this in its fully unabbreviated
 255       // form.
 256       EmitCode(bitc::UNABBREV_RECORD);
 257       EmitVBR(Code, 6);
 258       EmitVBR(Vals.size(), 6);
 259       for (unsigned i = 0, e = Vals.size(); i != e; ++i)
 260         EmitVBR64(Vals[i], 6);
 261     }
 262   }
 263
 264   /// EmitRecord - Emit the specified record to the stream, using an abbrev if
 265   /// we have one to compress the output.
 266   void EmitRecord(unsigned Code, SmallVectorImpl<unsigned> &Vals,
 267                   unsigned Abbrev = 0) {
 268     if (Abbrev) {
 269       unsigned AbbrevNo = Abbrev-bitc::FIRST_APPLICATION_ABBREV;
 270       assert(AbbrevNo < CurAbbrevs.size() && "Invalid abbrev #!");
 271       BitCodeAbbrev *Abbv = CurAbbrevs[AbbrevNo];
 272
 273       EmitCode(Abbrev);
 274
 275       // Insert the code into Vals to treat it uniformly.
 276       Vals.insert(Vals.begin(), Code);
 277
 278       unsigned RecordIdx = 0;
 279       for (unsigned i = 0, e = Abbv->getNumOperandInfos(); i != e; ++i) {
 280         assert(RecordIdx < Vals.size() && "Invalid abbrev/record");
 281         const BitCodeAbbrevOp &Op = Abbv->getOperandInfo(i);
 282
 283         if (Op.isLiteral() || Op.getEncoding() != BitCodeAbbrevOp::Array) {
 284           EmitAbbreviatedField(Op, Vals[RecordIdx]);
 285           ++RecordIdx;
 286         } else {
 287           assert(i+2 == e && "array op not second to last?");
 288           const BitCodeAbbrevOp &EltEnc = Abbv->getOperandInfo(++i);
 289
 290           // Emit a vbr6 to indicate the number of elements present.
 291           EmitVBR(Vals.size()-RecordIdx, 6);
 292
 293           // Emit each field.
 294           for (; RecordIdx != Vals.size(); ++RecordIdx)
 295             EmitAbbreviatedField(EltEnc, Vals[RecordIdx]);
 296         }
 297       }
 298       assert(RecordIdx == Vals.size() && "Not all record operands emitted!");
 299     } else {
 300       // If we don't have an abbrev to use, emit this in its fully unabbreviated
 301       // form.
 302       EmitCode(bitc::UNABBREV_RECORD);
 303       EmitVBR(Code, 6);
 304       EmitVBR(Vals.size(), 6);
 305       for (unsigned i = 0, e = Vals.size(); i != e; ++i)
 306         EmitVBR(Vals[i], 6);
 307     }
 308   }
 309
 310   //===--------------------------------------------------------------------===//
 311   // Abbrev Emission
 312   //===--------------------------------------------------------------------===//
 313
 314   /// EmitAbbrev - This emits an abbreviation to the stream.  Note that this
 315   /// method takes ownership of the specified abbrev.
 316   unsigned EmitAbbrev(BitCodeAbbrev *Abbv) {
 317     // Emit the abbreviation as a record.
 318     EmitCode(bitc::DEFINE_ABBREV);
 319     EmitVBR(Abbv->getNumOperandInfos(), 5);
 320     for (unsigned i = 0, e = Abbv->getNumOperandInfos(); i != e; ++i) {
 321       const BitCodeAbbrevOp &Op = Abbv->getOperandInfo(i);
 322       Emit(Op.isLiteral(), 1);
 323       if (Op.isLiteral()) {
 324         EmitVBR64(Op.getLiteralValue(), 8);
 325       } else {
 326         Emit(Op.getEncoding(), 3);
 327         if (Op.hasEncodingData())
 328           EmitVBR64(Op.getEncodingData(), 5);
 329       }
 330     }
 331
 332     CurAbbrevs.push_back(Abbv);
 333     return CurAbbrevs.size()-1+bitc::FIRST_APPLICATION_ABBREV;
 334   }
 335 };
 336
 337
 338 } // End llvm namespace
 339
 340 #endif