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