1 //===- BitstreamReader.h - Low-level bitstream reader interface -*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This header defines the BitstreamReader class. This class can be used to
11 // read an arbitrary bitstream, regardless of its contents.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_BITCODE_BITSTREAMREADER_H
16 #define LLVM_BITCODE_BITSTREAMREADER_H
18 #include "llvm/Bitcode/BitCodes.h"
19 #include "llvm/Support/Endian.h"
20 #include "llvm/Support/StreamingMemoryObject.h"
29 /// This class is used to read from an LLVM bitcode stream, maintaining
30 /// information that is global to decoding the entire file. While a file is
31 /// being read, multiple cursors can be independently advanced or skipped around
32 /// within the file. These are represented by the BitstreamCursor class.
33 class BitstreamReader
{
35 /// This contains information emitted to BLOCKINFO_BLOCK blocks. These
36 /// describe abbreviations that all blocks of the specified ID inherit.
39 std::vector
<IntrusiveRefCntPtr
<BitCodeAbbrev
>> Abbrevs
;
42 std::vector
<std::pair
<unsigned, std::string
> > RecordNames
;
45 std::unique_ptr
<MemoryObject
> BitcodeBytes
;
47 std::vector
<BlockInfo
> BlockInfoRecords
;
49 /// This is set to true if we don't care about the block/record name
50 /// information in the BlockInfo block. Only llvm-bcanalyzer uses this.
51 bool IgnoreBlockInfoNames
;
53 BitstreamReader(const BitstreamReader
&) LLVM_DELETED_FUNCTION
;
54 void operator=(const BitstreamReader
&) LLVM_DELETED_FUNCTION
;
56 BitstreamReader() : IgnoreBlockInfoNames(true) {
59 BitstreamReader(const unsigned char *Start
, const unsigned char *End
)
60 : IgnoreBlockInfoNames(true) {
64 BitstreamReader(std::unique_ptr
<MemoryObject
> BitcodeBytes
)
65 : BitcodeBytes(std::move(BitcodeBytes
)), IgnoreBlockInfoNames(true) {}
67 BitstreamReader(BitstreamReader
&&Other
) {
68 *this = std::move(Other
);
71 BitstreamReader
&operator=(BitstreamReader
&&Other
) {
72 BitcodeBytes
= std::move(Other
.BitcodeBytes
);
73 // Explicitly swap block info, so that nothing gets destroyed twice.
74 std::swap(BlockInfoRecords
, Other
.BlockInfoRecords
);
75 IgnoreBlockInfoNames
= Other
.IgnoreBlockInfoNames
;
79 void init(const unsigned char *Start
, const unsigned char *End
) {
80 assert(((End
-Start
) & 3) == 0 &&"Bitcode stream not a multiple of 4 bytes");
81 BitcodeBytes
.reset(getNonStreamedMemoryObject(Start
, End
));
84 MemoryObject
&getBitcodeBytes() { return *BitcodeBytes
; }
86 /// This is called by clients that want block/record name information.
87 void CollectBlockInfoNames() { IgnoreBlockInfoNames
= false; }
88 bool isIgnoringBlockInfoNames() { return IgnoreBlockInfoNames
; }
90 //===--------------------------------------------------------------------===//
92 //===--------------------------------------------------------------------===//
94 /// Return true if we've already read and processed the block info block for
95 /// this Bitstream. We only process it for the first cursor that walks over
97 bool hasBlockInfoRecords() const { return !BlockInfoRecords
.empty(); }
99 /// If there is block info for the specified ID, return it, otherwise return
101 const BlockInfo
*getBlockInfo(unsigned BlockID
) const {
102 // Common case, the most recent entry matches BlockID.
103 if (!BlockInfoRecords
.empty() && BlockInfoRecords
.back().BlockID
== BlockID
)
104 return &BlockInfoRecords
.back();
106 for (unsigned i
= 0, e
= static_cast<unsigned>(BlockInfoRecords
.size());
108 if (BlockInfoRecords
[i
].BlockID
== BlockID
)
109 return &BlockInfoRecords
[i
];
113 BlockInfo
&getOrCreateBlockInfo(unsigned BlockID
) {
114 if (const BlockInfo
*BI
= getBlockInfo(BlockID
))
115 return *const_cast<BlockInfo
*>(BI
);
117 // Otherwise, add a new record.
118 BlockInfoRecords
.push_back(BlockInfo());
119 BlockInfoRecords
.back().BlockID
= BlockID
;
120 return BlockInfoRecords
.back();
123 /// Takes block info from the other bitstream reader.
125 /// This is a "take" operation because BlockInfo records are non-trivial, and
126 /// indeed rather expensive.
127 void takeBlockInfo(BitstreamReader
&&Other
) {
128 assert(!hasBlockInfoRecords());
129 BlockInfoRecords
= std::move(Other
.BlockInfoRecords
);
133 /// When advancing through a bitstream cursor, each advance can discover a few
134 /// different kinds of entries:
135 struct BitstreamEntry
{
137 Error
, // Malformed bitcode was found.
138 EndBlock
, // We've reached the end of the current block, (or the end of the
139 // file, which is treated like a series of EndBlock records.
140 SubBlock
, // This is the start of a new subblock of a specific ID.
141 Record
// This is a record with a specific AbbrevID.
146 static BitstreamEntry
getError() {
147 BitstreamEntry E
; E
.Kind
= Error
; return E
;
149 static BitstreamEntry
getEndBlock() {
150 BitstreamEntry E
; E
.Kind
= EndBlock
; return E
;
152 static BitstreamEntry
getSubBlock(unsigned ID
) {
153 BitstreamEntry E
; E
.Kind
= SubBlock
; E
.ID
= ID
; return E
;
155 static BitstreamEntry
getRecord(unsigned AbbrevID
) {
156 BitstreamEntry E
; E
.Kind
= Record
; E
.ID
= AbbrevID
; return E
;
160 /// This represents a position within a bitcode file. There may be multiple
161 /// independent cursors reading within one bitstream, each maintaining their own
164 /// Unlike iterators, BitstreamCursors are heavy-weight objects that should not
165 /// be passed by value.
166 class BitstreamCursor
{
167 friend class Deserializer
;
168 BitstreamReader
*BitStream
;
171 // The size of the bicode. 0 if we don't know it yet.
174 /// This is the current data we have pulled from the stream but have not
175 /// returned to the client. This is specifically and intentionally defined to
176 /// follow the word size of the host machine for efficiency. We use word_t in
177 /// places that are aware of this to make it perfectly explicit what is going
179 typedef size_t word_t
;
182 /// This is the number of bits in CurWord that are valid. This is always from
183 /// [0...bits_of(size_t)-1] inclusive.
184 unsigned BitsInCurWord
;
186 // This is the declared size of code values used for the current block, in
188 unsigned CurCodeSize
;
190 /// Abbrevs installed at in this block.
191 std::vector
<IntrusiveRefCntPtr
<BitCodeAbbrev
>> CurAbbrevs
;
194 unsigned PrevCodeSize
;
195 std::vector
<IntrusiveRefCntPtr
<BitCodeAbbrev
>> PrevAbbrevs
;
196 explicit Block(unsigned PCS
) : PrevCodeSize(PCS
) {}
199 /// This tracks the codesize of parent blocks.
200 SmallVector
<Block
, 8> BlockScope
;
204 BitstreamCursor() { init(nullptr); }
206 explicit BitstreamCursor(BitstreamReader
&R
) { init(&R
); }
208 void init(BitstreamReader
*R
) {
220 bool canSkipToPos(size_t pos
) const {
221 // pos can be skipped to if it is a valid address or one byte past the end.
222 return pos
== 0 || BitStream
->getBitcodeBytes().isValidAddress(
223 static_cast<uint64_t>(pos
- 1));
226 bool AtEndOfStream() {
227 if (BitsInCurWord
!= 0)
230 return Size
== NextChar
;
232 return BitsInCurWord
== 0;
235 /// Return the number of bits used to encode an abbrev #.
236 unsigned getAbbrevIDWidth() const { return CurCodeSize
; }
238 /// Return the bit # of the bit we are reading.
239 uint64_t GetCurrentBitNo() const {
240 return NextChar
*CHAR_BIT
- BitsInCurWord
;
243 BitstreamReader
*getBitStreamReader() {
246 const BitstreamReader
*getBitStreamReader() const {
250 /// Flags that modify the behavior of advance().
252 /// If this flag is used, the advance() method does not automatically pop
253 /// the block scope when the end of a block is reached.
254 AF_DontPopBlockAtEnd
= 1,
256 /// If this flag is used, abbrev entries are returned just like normal
258 AF_DontAutoprocessAbbrevs
= 2
261 /// Advance the current bitstream, returning the next entry in the stream.
262 BitstreamEntry
advance(unsigned Flags
= 0) {
264 unsigned Code
= ReadCode();
265 if (Code
== bitc::END_BLOCK
) {
266 // Pop the end of the block unless Flags tells us not to.
267 if (!(Flags
& AF_DontPopBlockAtEnd
) && ReadBlockEnd())
268 return BitstreamEntry::getError();
269 return BitstreamEntry::getEndBlock();
272 if (Code
== bitc::ENTER_SUBBLOCK
)
273 return BitstreamEntry::getSubBlock(ReadSubBlockID());
275 if (Code
== bitc::DEFINE_ABBREV
&&
276 !(Flags
& AF_DontAutoprocessAbbrevs
)) {
277 // We read and accumulate abbrev's, the client can't do anything with
283 return BitstreamEntry::getRecord(Code
);
287 /// This is a convenience function for clients that don't expect any
288 /// subblocks. This just skips over them automatically.
289 BitstreamEntry
advanceSkippingSubblocks(unsigned Flags
= 0) {
291 // If we found a normal entry, return it.
292 BitstreamEntry Entry
= advance(Flags
);
293 if (Entry
.Kind
!= BitstreamEntry::SubBlock
)
296 // If we found a sub-block, just skip over it and check the next entry.
298 return BitstreamEntry::getError();
302 /// Reset the stream to the specified bit number.
303 void JumpToBit(uint64_t BitNo
) {
304 uintptr_t ByteNo
= uintptr_t(BitNo
/8) & ~(sizeof(word_t
)-1);
305 unsigned WordBitNo
= unsigned(BitNo
& (sizeof(word_t
)*8-1));
306 assert(canSkipToPos(ByteNo
) && "Invalid location");
308 // Move the cursor to the right word.
312 // Skip over any bits that are already consumed.
318 assert(Size
== 0 || NextChar
< (unsigned)Size
);
320 // Read the next word from the stream.
321 uint8_t Array
[sizeof(word_t
)] = {0};
324 BitStream
->getBitcodeBytes().readBytes(Array
, sizeof(Array
), NextChar
);
326 // If we run out of data, stop at the end of the stream.
327 if (BytesRead
== 0) {
333 support::endian::read
<word_t
, support::little
, support::unaligned
>(
335 NextChar
+= BytesRead
;
336 BitsInCurWord
= BytesRead
* 8;
339 word_t
Read(unsigned NumBits
) {
340 static const unsigned BitsInWord
= sizeof(word_t
) * 8;
342 assert(NumBits
&& NumBits
<= BitsInWord
&&
343 "Cannot return zero or more than BitsInWord bits!");
345 static const unsigned Mask
= sizeof(word_t
) > 4 ? 0x3f : 0x1f;
347 // If the field is fully contained by CurWord, return it quickly.
348 if (BitsInCurWord
>= NumBits
) {
349 word_t R
= CurWord
& (~word_t(0) >> (BitsInWord
- NumBits
));
351 // Use a mask to avoid undefined behavior.
352 CurWord
>>= (NumBits
& Mask
);
354 BitsInCurWord
-= NumBits
;
358 word_t R
= BitsInCurWord
? CurWord
: 0;
359 unsigned BitsLeft
= NumBits
- BitsInCurWord
;
363 // If we run out of data, stop at the end of the stream.
364 if (BitsLeft
> BitsInCurWord
)
367 word_t R2
= CurWord
& (~word_t(0) >> (BitsInWord
- BitsLeft
));
369 // Use a mask to avoid undefined behavior.
370 CurWord
>>= (BitsLeft
& Mask
);
372 BitsInCurWord
-= BitsLeft
;
374 R
|= R2
<< (NumBits
- BitsLeft
);
379 uint32_t ReadVBR(unsigned NumBits
) {
380 uint32_t Piece
= Read(NumBits
);
381 if ((Piece
& (1U << (NumBits
-1))) == 0)
385 unsigned NextBit
= 0;
387 Result
|= (Piece
& ((1U << (NumBits
-1))-1)) << NextBit
;
389 if ((Piece
& (1U << (NumBits
-1))) == 0)
392 NextBit
+= NumBits
-1;
393 Piece
= Read(NumBits
);
397 // Read a VBR that may have a value up to 64-bits in size. The chunk size of
398 // the VBR must still be <= 32 bits though.
399 uint64_t ReadVBR64(unsigned NumBits
) {
400 uint32_t Piece
= Read(NumBits
);
401 if ((Piece
& (1U << (NumBits
-1))) == 0)
402 return uint64_t(Piece
);
405 unsigned NextBit
= 0;
407 Result
|= uint64_t(Piece
& ((1U << (NumBits
-1))-1)) << NextBit
;
409 if ((Piece
& (1U << (NumBits
-1))) == 0)
412 NextBit
+= NumBits
-1;
413 Piece
= Read(NumBits
);
418 void SkipToFourByteBoundary() {
419 // If word_t is 64-bits and if we've read less than 32 bits, just dump
420 // the bits we have up to the next 32-bit boundary.
421 if (sizeof(word_t
) > 4 &&
422 BitsInCurWord
>= 32) {
423 CurWord
>>= BitsInCurWord
-32;
432 unsigned ReadCode() {
433 return Read(CurCodeSize
);
438 // [ENTER_SUBBLOCK, blockid, newcodelen, <align4bytes>, blocklen]
440 /// Having read the ENTER_SUBBLOCK code, read the BlockID for the block.
441 unsigned ReadSubBlockID() {
442 return ReadVBR(bitc::BlockIDWidth
);
445 /// Having read the ENTER_SUBBLOCK abbrevid and a BlockID, skip over the body
446 /// of this block. If the block record is malformed, return true.
448 // Read and ignore the codelen value. Since we are skipping this block, we
449 // don't care what code widths are used inside of it.
450 ReadVBR(bitc::CodeLenWidth
);
451 SkipToFourByteBoundary();
452 unsigned NumFourBytes
= Read(bitc::BlockSizeWidth
);
454 // Check that the block wasn't partially defined, and that the offset isn't
456 size_t SkipTo
= GetCurrentBitNo() + NumFourBytes
*4*8;
457 if (AtEndOfStream() || !canSkipToPos(SkipTo
/8))
464 /// Having read the ENTER_SUBBLOCK abbrevid, enter the block, and return true
465 /// if the block has an error.
466 bool EnterSubBlock(unsigned BlockID
, unsigned *NumWordsP
= nullptr);
468 bool ReadBlockEnd() {
469 if (BlockScope
.empty()) return true;
472 // [END_BLOCK, <align4bytes>]
473 SkipToFourByteBoundary();
481 void popBlockScope() {
482 CurCodeSize
= BlockScope
.back().PrevCodeSize
;
484 CurAbbrevs
= std::move(BlockScope
.back().PrevAbbrevs
);
485 BlockScope
.pop_back();
488 //===--------------------------------------------------------------------===//
490 //===--------------------------------------------------------------------===//
494 /// Return the abbreviation for the specified AbbrevId.
495 const BitCodeAbbrev
*getAbbrev(unsigned AbbrevID
) {
496 unsigned AbbrevNo
= AbbrevID
-bitc::FIRST_APPLICATION_ABBREV
;
497 assert(AbbrevNo
< CurAbbrevs
.size() && "Invalid abbrev #!");
498 return CurAbbrevs
[AbbrevNo
].get();
501 /// Read the current record and discard it.
502 void skipRecord(unsigned AbbrevID
);
504 unsigned readRecord(unsigned AbbrevID
, SmallVectorImpl
<uint64_t> &Vals
,
505 StringRef
*Blob
= nullptr);
507 //===--------------------------------------------------------------------===//
509 //===--------------------------------------------------------------------===//
510 void ReadAbbrevRecord();
512 bool ReadBlockInfoBlock();
515 } // End llvm namespace