LLVM 24.0.0git
BitstreamReader.h
Go to the documentation of this file.
1//===- BitstreamReader.h - Low-level bitstream reader interface -*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This header defines the BitstreamReader class. This class can be used to
10// read an arbitrary bitstream, regardless of its contents.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_BITSTREAM_BITSTREAMREADER_H
15#define LLVM_BITSTREAM_BITSTREAMREADER_H
16
17#include "llvm/ADT/ArrayRef.h"
21#include "llvm/Support/Endian.h"
22#include "llvm/Support/Error.h"
25#include <algorithm>
26#include <cassert>
27#include <cinttypes>
28#include <climits>
29#include <cstddef>
30#include <cstdint>
31#include <memory>
32#include <optional>
33#include <string>
34#include <utility>
35#include <vector>
36
37namespace llvm {
38
39/// This class maintains the abbreviations read from a block info block.
41public:
42 /// This contains information emitted to BLOCKINFO_BLOCK blocks. These
43 /// describe abbreviations that all blocks of the specified ID inherit.
44 struct BlockInfo {
45 unsigned BlockID = 0;
46 std::vector<std::shared_ptr<BitCodeAbbrev>> Abbrevs;
47 std::string Name;
48 std::vector<std::pair<unsigned, std::string>> RecordNames;
49 };
50
51private:
52 std::vector<BlockInfo> BlockInfoRecords;
53
54public:
55 /// If there is block info for the specified ID, return it, otherwise return
56 /// null.
57 const BlockInfo *getBlockInfo(unsigned BlockID) const {
58 // Common case, the most recent entry matches BlockID.
59 if (!BlockInfoRecords.empty() && BlockInfoRecords.back().BlockID == BlockID)
60 return &BlockInfoRecords.back();
61
62 for (const BlockInfo &BI : BlockInfoRecords)
63 if (BI.BlockID == BlockID)
64 return &BI;
65 return nullptr;
66 }
67
68 BlockInfo &getOrCreateBlockInfo(unsigned BlockID) {
69 if (const BlockInfo *BI = getBlockInfo(BlockID))
70 return *const_cast<BlockInfo*>(BI);
71
72 // Otherwise, add a new record.
73 BlockInfoRecords.emplace_back();
74 BlockInfoRecords.back().BlockID = BlockID;
75 return BlockInfoRecords.back();
76 }
77};
78
79/// This represents a position within a bitstream. There may be multiple
80/// independent cursors reading within one bitstream, each maintaining their
81/// own local state.
83 ArrayRef<uint8_t> BitcodeBytes;
84
85 /// The number of the next bit to read.
86 uint64_t BitNo = 0;
87
88 /// Reads at bits before this can load a whole word from their first byte.
89 uint64_t WordLoadEnd = 0;
90
91public:
92 /// The type of the values returned by Read. This is specifically and
93 /// intentionally defined to follow the word size of the host machine for
94 /// efficiency. We use word_t in places that are aware of this to make it
95 /// perfectly explicit what is going on.
96 using word_t = size_t;
97
98private:
99 static constexpr unsigned BitsInWord = sizeof(word_t) * 8;
100
101public:
104 : BitcodeBytes(BitcodeBytes),
105 WordLoadEnd(BitcodeBytes.size() < sizeof(word_t)
106 ? 0
107 : (BitcodeBytes.size() - sizeof(word_t) + 1) * 8) {}
108 explicit SimpleBitstreamCursor(StringRef BitcodeBytes)
111 : SimpleBitstreamCursor(BitcodeBytes.getBuffer()) {}
112
113 bool canSkipToPos(size_t pos) const {
114 // pos can be skipped to if it is a valid address or one byte past the end.
115 return pos <= BitcodeBytes.size();
116 }
117
118 bool AtEndOfStream() { return BitNo >= sizeInBits(); }
119
120 /// Return the bit # of the bit we are reading.
121 uint64_t GetCurrentBitNo() const { return BitNo; }
122
123 // Return the byte # of the current bit.
124 uint64_t getCurrentByteNo() const { return GetCurrentBitNo() / 8; }
125
126 ArrayRef<uint8_t> getBitcodeBytes() const { return BitcodeBytes; }
127
128 /// Reset the stream to the specified bit number.
130 assert(canSkipToPos(NewBitNo / 8) && "Invalid location");
131 if (NewBitNo > sizeInBits())
132 return createStringError(std::errc::io_error,
133 "Unexpected end of file jumping to bit %" PRIu64
134 " of %" PRIu64 " bits",
135 NewBitNo, sizeInBits());
136 BitNo = NewBitNo;
137 return Error::success();
138 }
139
140 /// Get a pointer into the bitstream at the specified byte offset.
141 const uint8_t *getPointerToByte(uint64_t ByteNo, uint64_t NumBytes) {
142 return BitcodeBytes.data() + ByteNo;
143 }
144
145 /// Get a pointer into the bitstream at the specified bit offset.
146 ///
147 /// The bit offset must be on a byte boundary.
148 const uint8_t *getPointerToBit(uint64_t BitNo, uint64_t NumBytes) {
149 assert(!(BitNo % 8) && "Expected bit on byte boundary");
150 return getPointerToByte(BitNo / 8, NumBytes);
151 }
152
153private:
154 /// Return the word starting at the current bit, which must be before
155 /// WordLoadEnd. Only the low BitsInWord - 7 bits are guaranteed to be valid.
156 word_t loadWordAtBit() const {
157 assert(BitNo < WordLoadEnd && "Word load past the end of the stream");
159 BitcodeBytes.data() + BitNo / 8) >>
160 (BitNo % 8);
161 }
162
163public:
164 Expected<word_t> Read(unsigned NumBits) {
165 assert(NumBits && NumBits <= BitsInWord &&
166 "Cannot return zero or more than BitsInWord bits!");
167
168 // If the field is contained in a word starting at the current byte, load
169 // that word directly.
170 if (NumBits <= BitsInWord - 7 && BitNo < WordLoadEnd) {
171 word_t R = loadWordAtBit() & (~word_t(0) >> (BitsInWord - NumBits));
172 BitNo += NumBits;
173 return R;
174 }
175
176 return readSlow(NumBits);
177 }
178
179 /// Read \p NumBits bits that don't fit in a word load from the current byte,
180 /// or are near the end of the stream.
181 LLVM_ABI Expected<word_t> readSlow(unsigned NumBits);
182
183 Expected<uint32_t> ReadVBR(const unsigned NumBits) {
184 Expected<unsigned> MaybeRead = Read(NumBits);
185 if (!MaybeRead)
186 return MaybeRead;
187 uint32_t Piece = MaybeRead.get();
188
189 assert(NumBits <= 32 && NumBits >= 1 && "Invalid NumBits value");
190 const uint32_t MaskBitOrder = (NumBits - 1);
191 const uint32_t Mask = 1UL << MaskBitOrder;
192
193 if ((Piece & Mask) == 0)
194 return Piece;
195
196 uint32_t Result = 0;
197 unsigned NextBit = 0;
198 while (true) {
199 Result |= (Piece & (Mask - 1)) << NextBit;
200
201 if ((Piece & Mask) == 0)
202 return Result;
203
204 NextBit += NumBits-1;
205 if (NextBit >= 32)
206 return createStringError(std::errc::illegal_byte_sequence,
207 "Unterminated VBR");
208
209 MaybeRead = Read(NumBits);
210 if (!MaybeRead)
211 return MaybeRead;
212 Piece = MaybeRead.get();
213 }
214 }
215
216 // Read a VBR that may have a value up to 64-bits in size. The chunk size of
217 // the VBR must still be <= 32 bits though.
218 Expected<uint64_t> ReadVBR64(const unsigned NumBits) {
219 Expected<uint64_t> MaybeRead = Read(NumBits);
220 if (!MaybeRead)
221 return MaybeRead;
222 uint32_t Piece = MaybeRead.get();
223 assert(NumBits <= 32 && NumBits >= 1 && "Invalid NumBits value");
224 const uint32_t MaskBitOrder = (NumBits - 1);
225 const uint32_t Mask = 1UL << MaskBitOrder;
226
227 if ((Piece & Mask) == 0)
228 return uint64_t(Piece);
229
230 uint64_t Result = 0;
231 unsigned NextBit = 0;
232 while (true) {
233 Result |= uint64_t(Piece & (Mask - 1)) << NextBit;
234
235 if ((Piece & Mask) == 0)
236 return Result;
237
238 NextBit += NumBits-1;
239 if (NextBit >= 64)
240 return createStringError(std::errc::illegal_byte_sequence,
241 "Unterminated VBR");
242
243 MaybeRead = Read(NumBits);
244 if (!MaybeRead)
245 return MaybeRead;
246 Piece = MaybeRead.get();
247 }
248 }
249
251 BitNo = std::min(alignTo(BitNo, 32), sizeInBits());
252 }
253
254 /// Return the size of the stream in bytes.
255 size_t SizeInBytes() const { return BitcodeBytes.size(); }
256
257 /// Return the size of the stream in bits.
258 uint64_t sizeInBits() const { return uint64_t(BitcodeBytes.size()) * 8; }
259
260 /// Skip to the end of the file.
261 void skipToEnd() { BitNo = sizeInBits(); }
262
263 /// Check whether a reservation of Size elements is plausible.
264 bool isSizePlausible(size_t Size) const {
265 // Don't allow reserving more elements than the number of bits, assuming
266 // at least one bit is needed to encode an element.
267 return Size < BitcodeBytes.size() * 8;
268 }
269};
270
271/// When advancing through a bitstream cursor, each advance can discover a few
272/// different kinds of entries:
274 enum {
275 Error, // Malformed bitcode was found.
276 EndBlock, // We've reached the end of the current block, (or the end of the
277 // file, which is treated like a series of EndBlock records.
278 SubBlock, // This is the start of a new subblock of a specific ID.
279 Record // This is a record with a specific AbbrevID.
280 } Kind;
281
282 unsigned ID;
283
285 BitstreamEntry E; E.Kind = Error; return E;
286 }
287
289 BitstreamEntry E; E.Kind = EndBlock; return E;
290 }
291
292 static BitstreamEntry getSubBlock(unsigned ID) {
293 BitstreamEntry E; E.Kind = SubBlock; E.ID = ID; return E;
294 }
295
296 static BitstreamEntry getRecord(unsigned AbbrevID) {
297 BitstreamEntry E; E.Kind = Record; E.ID = AbbrevID; return E;
298 }
299};
300
301/// This represents a position within a bitcode file, implemented on top of a
302/// SimpleBitstreamCursor.
303///
304/// Unlike iterators, BitstreamCursors are heavy-weight objects that should not
305/// be passed by value.
307 // This is the declared size of code values used for the current block, in
308 // bits.
309 unsigned CurCodeSize = 2;
310
311 /// Abbrevs installed at in this block.
312 std::vector<std::shared_ptr<BitCodeAbbrev>> CurAbbrevs;
313
314 struct Block {
315 unsigned PrevCodeSize;
316 std::vector<std::shared_ptr<BitCodeAbbrev>> PrevAbbrevs;
317
318 explicit Block(unsigned PCS) : PrevCodeSize(PCS) {}
319 };
320
321 /// This tracks the codesize of parent blocks.
322 SmallVector<Block, 8> BlockScope;
323
324 BitstreamBlockInfo *BlockInfo = nullptr;
325
326public:
327 static const size_t MaxChunkSize = 32;
328
329 BitstreamCursor() = default;
330 explicit BitstreamCursor(ArrayRef<uint8_t> BitcodeBytes)
331 : SimpleBitstreamCursor(BitcodeBytes) {}
332 explicit BitstreamCursor(StringRef BitcodeBytes)
333 : SimpleBitstreamCursor(BitcodeBytes) {}
334 explicit BitstreamCursor(MemoryBufferRef BitcodeBytes)
335 : SimpleBitstreamCursor(BitcodeBytes) {}
336
349
350 /// Return the number of bits used to encode an abbrev #.
351 unsigned getAbbrevIDWidth() const { return CurCodeSize; }
352
353 /// Flags that modify the behavior of advance().
354 enum {
355 /// If this flag is used, the advance() method does not automatically pop
356 /// the block scope when the end of a block is reached.
358
359 /// If this flag is used, abbrev entries are returned just like normal
360 /// records.
362 };
363
364 /// Advance the current bitstream, returning the next entry in the stream.
365 Expected<BitstreamEntry> advance(unsigned Flags = 0) {
366 while (true) {
367 if (AtEndOfStream())
369
370 Expected<unsigned> MaybeCode = ReadCode();
371 if (!MaybeCode)
372 return MaybeCode.takeError();
373 unsigned Code = MaybeCode.get();
374
375 if (Code == bitc::END_BLOCK) {
376 // Pop the end of the block unless Flags tells us not to.
377 if (!(Flags & AF_DontPopBlockAtEnd) && ReadBlockEnd())
380 }
381
382 if (Code == bitc::ENTER_SUBBLOCK) {
383 if (Expected<unsigned> MaybeSubBlock = ReadSubBlockID())
384 return BitstreamEntry::getSubBlock(MaybeSubBlock.get());
385 else
386 return MaybeSubBlock.takeError();
387 }
388
389 if (Code == bitc::DEFINE_ABBREV &&
390 !(Flags & AF_DontAutoprocessAbbrevs)) {
391 // We read and accumulate abbrev's, the client can't do anything with
392 // them anyway.
393 if (Error Err = ReadAbbrevRecord())
394 return std::move(Err);
395 continue;
396 }
397
398 return BitstreamEntry::getRecord(Code);
399 }
400 }
401
402 /// This is a convenience function for clients that don't expect any
403 /// subblocks. This just skips over them automatically.
405 while (true) {
406 // If we found a normal entry, return it.
407 Expected<BitstreamEntry> MaybeEntry = advance(Flags);
408 if (!MaybeEntry)
409 return MaybeEntry;
410 BitstreamEntry Entry = MaybeEntry.get();
411
412 if (Entry.Kind != BitstreamEntry::SubBlock)
413 return Entry;
414
415 // If we found a sub-block, just skip over it and check the next entry.
416 if (Error Err = SkipBlock())
417 return std::move(Err);
418 }
419 }
420
421 Expected<unsigned> ReadCode() { return Read(CurCodeSize); }
422
423 // Block header:
424 // [ENTER_SUBBLOCK, blockid, newcodelen, <align4bytes>, blocklen]
425
426 /// Having read the ENTER_SUBBLOCK code, read the BlockID for the block.
428
429 /// Having read the ENTER_SUBBLOCK abbrevid and a BlockID, skip over the body
430 /// of this block.
432 // Read and ignore the codelen value.
434 ; // Since we are skipping this block, we don't care what code widths are
435 // used inside of it.
436 else
437 return Res.takeError();
438
441 if (!MaybeNum)
442 return MaybeNum.takeError();
443 size_t NumFourBytes = MaybeNum.get();
444
445 // Check that the block wasn't partially defined, and that the offset isn't
446 // bogus.
447 size_t SkipTo = GetCurrentBitNo() + NumFourBytes * 4 * 8;
448 if (AtEndOfStream())
449 return createStringError(std::errc::illegal_byte_sequence,
450 "can't skip block: already at end of stream");
451 if (!canSkipToPos(SkipTo / 8))
452 return createStringError(std::errc::illegal_byte_sequence,
453 "can't skip to bit %zu from %" PRIu64, SkipTo,
455
456 if (Error Res = JumpToBit(SkipTo))
457 return Res;
458
459 return Error::success();
460 }
461
462 /// Having read the ENTER_SUBBLOCK abbrevid, and enter the block.
463 LLVM_ABI Error EnterSubBlock(unsigned BlockID, unsigned *NumWordsP = nullptr);
464
466 if (BlockScope.empty()) return true;
467
468 // Block tail:
469 // [END_BLOCK, <align4bytes>]
471
472 popBlockScope();
473 return false;
474 }
475
476private:
477 void popBlockScope() {
478 CurCodeSize = BlockScope.back().PrevCodeSize;
479
480 CurAbbrevs = std::move(BlockScope.back().PrevAbbrevs);
481 BlockScope.pop_back();
482 }
483
484 //===--------------------------------------------------------------------===//
485 // Record Processing
486 //===--------------------------------------------------------------------===//
487
488public:
489 /// Return the abbreviation for the specified AbbrevId.
491 unsigned AbbrevNo = AbbrevID - bitc::FIRST_APPLICATION_ABBREV;
492 if (AbbrevNo >= CurAbbrevs.size())
493 return createStringError(
494 std::errc::illegal_byte_sequence, "Invalid abbrev number");
495 return CurAbbrevs[AbbrevNo].get();
496 }
497
498 /// Read the current record and discard it, returning the code for the record.
499 LLVM_ABI Expected<unsigned> skipRecord(unsigned AbbrevID);
500
501 LLVM_ABI Expected<unsigned> readRecord(unsigned AbbrevID,
503 StringRef *Blob = nullptr);
504
505 //===--------------------------------------------------------------------===//
506 // Abbrev Processing
507 //===--------------------------------------------------------------------===//
509
510 /// Read and return a block info block from the bitstream. If an error was
511 /// encountered, return std::nullopt.
512 ///
513 /// \param ReadBlockInfoNames Whether to read block/record name information in
514 /// the BlockInfo block. Only llvm-bcanalyzer uses this.
516 ReadBlockInfoBlock(bool ReadBlockInfoNames = false);
517
518 /// Set the block info to be used by this BitstreamCursor to interpret
519 /// abbreviated records.
520 void setBlockInfo(BitstreamBlockInfo *BI) { BlockInfo = BI; }
521};
522
523} // end llvm namespace
524
525#endif // LLVM_BITSTREAM_BITSTREAMREADER_H
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
uint64_t uint64_t
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_ABI
Definition Compiler.h:211
This file defines the SmallVector class.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:40
const T * data() const
Definition ArrayRef.h:138
This class maintains the abbreviations read from a block info block.
const BlockInfo * getBlockInfo(unsigned BlockID) const
If there is block info for the specified ID, return it, otherwise return null.
BlockInfo & getOrCreateBlockInfo(unsigned BlockID)
BitstreamCursor(StringRef BitcodeBytes)
LLVM_ABI Error ReadAbbrevRecord()
uint64_t GetCurrentBitNo() const
Return the bit # of the bit we are reading.
Expected< unsigned > ReadSubBlockID()
Having read the ENTER_SUBBLOCK code, read the BlockID for the block.
static const size_t MaxChunkSize
Expected< BitstreamEntry > advance(unsigned Flags=0)
Advance the current bitstream, returning the next entry in the stream.
BitstreamCursor(MemoryBufferRef BitcodeBytes)
Expected< BitstreamEntry > advanceSkippingSubblocks(unsigned Flags=0)
This is a convenience function for clients that don't expect any subblocks.
Expected< const BitCodeAbbrev * > getAbbrev(unsigned AbbrevID)
Return the abbreviation for the specified AbbrevId.
void setBlockInfo(BitstreamBlockInfo *BI)
Set the block info to be used by this BitstreamCursor to interpret abbreviated records.
LLVM_ABI Expected< unsigned > readRecord(unsigned AbbrevID, SmallVectorImpl< uint64_t > &Vals, StringRef *Blob=nullptr)
LLVM_ABI Error EnterSubBlock(unsigned BlockID, unsigned *NumWordsP=nullptr)
Having read the ENTER_SUBBLOCK abbrevid, and enter the block.
Error SkipBlock()
Having read the ENTER_SUBBLOCK abbrevid and a BlockID, skip over the body of this block.
LLVM_ABI Expected< unsigned > skipRecord(unsigned AbbrevID)
Read the current record and discard it, returning the code for the record.
BitstreamCursor(ArrayRef< uint8_t > BitcodeBytes)
@ AF_DontAutoprocessAbbrevs
If this flag is used, abbrev entries are returned just like normal records.
@ AF_DontPopBlockAtEnd
If this flag is used, the advance() method does not automatically pop the block scope when the end of...
Expected< unsigned > ReadCode()
LLVM_ABI Expected< std::optional< BitstreamBlockInfo > > ReadBlockInfoBlock(bool ReadBlockInfoNames=false)
Read and return a block info block from the bitstream.
Error JumpToBit(uint64_t NewBitNo)
Reset the stream to the specified bit number.
Expected< uint32_t > ReadVBR(const unsigned NumBits)
unsigned getAbbrevIDWidth() const
Return the number of bits used to encode an abbrev #.
bool canSkipToPos(size_t pos) const
Lightweight error class with error context and mandatory checking.
Definition Error.h:159
static ErrorSuccess success()
Create a success value.
Definition Error.h:336
Tagged union holding either a T or a Error.
Definition Error.h:485
Error takeError()
Take ownership of the stored error.
Definition Error.h:612
reference get()
Returns a reference to the stored T value.
Definition Error.h:582
LLVM_ABI Expected< word_t > readSlow(unsigned NumBits)
Read NumBits bits that don't fit in a word load from the current byte, or are near the end of the str...
const uint8_t * getPointerToBit(uint64_t BitNo, uint64_t NumBytes)
Get a pointer into the bitstream at the specified bit offset.
uint64_t GetCurrentBitNo() const
Return the bit # of the bit we are reading.
Expected< uint64_t > ReadVBR64(const unsigned NumBits)
size_t SizeInBytes() const
Return the size of the stream in bytes.
ArrayRef< uint8_t > getBitcodeBytes() const
Expected< word_t > Read(unsigned NumBits)
const uint8_t * getPointerToByte(uint64_t ByteNo, uint64_t NumBytes)
Get a pointer into the bitstream at the specified byte offset.
SimpleBitstreamCursor(StringRef BitcodeBytes)
SimpleBitstreamCursor(ArrayRef< uint8_t > BitcodeBytes)
SimpleBitstreamCursor(MemoryBufferRef BitcodeBytes)
size_t word_t
The type of the values returned by Read.
uint64_t getCurrentByteNo() const
bool isSizePlausible(size_t Size) const
Check whether a reservation of Size elements is plausible.
void skipToEnd()
Skip to the end of the file.
Error JumpToBit(uint64_t NewBitNo)
Reset the stream to the specified bit number.
uint64_t sizeInBits() const
Return the size of the stream in bits.
Expected< uint32_t > ReadVBR(const unsigned NumBits)
bool canSkipToPos(size_t pos) const
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Represent a constant reference to a string, i.e.
Definition StringRef.h:56
@ DEFINE_ABBREV
DEFINE_ABBREV - Defines an abbrev for the current block.
@ FIRST_APPLICATION_ABBREV
value_type read(const void *memory, endianness endian)
Read a value of a particular endianness from memory.
Definition Endian.h:53
This is an optimization pass for GlobalISel generic memory operations.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition STLExtras.h:1685
ArrayRef< CharT > arrayRefFromStringRef(StringRef Input)
Construct an array ref of bytes from a string ref.
Error createStringError(std::error_code EC, char const *Fmt, const Ts &... Vals)
Create formatted StringError object.
Definition Error.h:1321
constexpr uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition Alignment.h:149
This contains information emitted to BLOCKINFO_BLOCK blocks.
std::vector< std::pair< unsigned, std::string > > RecordNames
std::vector< std::shared_ptr< BitCodeAbbrev > > Abbrevs
When advancing through a bitstream cursor, each advance can discover a few different kinds of entries...
static BitstreamEntry getSubBlock(unsigned ID)
static BitstreamEntry getRecord(unsigned AbbrevID)
static BitstreamEntry getEndBlock()
static BitstreamEntry getError()