BitstreamReader.h revision 360784
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" 18#include "llvm/ADT/SmallVector.h" 19#include "llvm/Bitstream/BitCodes.h" 20#include "llvm/Support/Endian.h" 21#include "llvm/Support/ErrorHandling.h" 22#include "llvm/Support/MathExtras.h" 23#include "llvm/Support/MemoryBuffer.h" 24#include <algorithm> 25#include <cassert> 26#include <climits> 27#include <cstddef> 28#include <cstdint> 29#include <memory> 30#include <string> 31#include <utility> 32#include <vector> 33 34namespace llvm { 35 36/// This class maintains the abbreviations read from a block info block. 37class BitstreamBlockInfo { 38public: 39 /// This contains information emitted to BLOCKINFO_BLOCK blocks. These 40 /// describe abbreviations that all blocks of the specified ID inherit. 41 struct BlockInfo { 42 unsigned BlockID = 0; 43 std::vector<std::shared_ptr<BitCodeAbbrev>> Abbrevs; 44 std::string Name; 45 std::vector<std::pair<unsigned, std::string>> RecordNames; 46 }; 47 48private: 49 std::vector<BlockInfo> BlockInfoRecords; 50 51public: 52 /// If there is block info for the specified ID, return it, otherwise return 53 /// null. 54 const BlockInfo *getBlockInfo(unsigned BlockID) const { 55 // Common case, the most recent entry matches BlockID. 56 if (!BlockInfoRecords.empty() && BlockInfoRecords.back().BlockID == BlockID) 57 return &BlockInfoRecords.back(); 58 59 for (unsigned i = 0, e = static_cast<unsigned>(BlockInfoRecords.size()); 60 i != e; ++i) 61 if (BlockInfoRecords[i].BlockID == BlockID) 62 return &BlockInfoRecords[i]; 63 return nullptr; 64 } 65 66 BlockInfo &getOrCreateBlockInfo(unsigned BlockID) { 67 if (const BlockInfo *BI = getBlockInfo(BlockID)) 68 return *const_cast<BlockInfo*>(BI); 69 70 // Otherwise, add a new record. 71 BlockInfoRecords.emplace_back(); 72 BlockInfoRecords.back().BlockID = BlockID; 73 return BlockInfoRecords.back(); 74 } 75}; 76 77/// This represents a position within a bitstream. There may be multiple 78/// independent cursors reading within one bitstream, each maintaining their 79/// own local state. 80class SimpleBitstreamCursor { 81 ArrayRef<uint8_t> BitcodeBytes; 82 size_t NextChar = 0; 83 84public: 85 /// This is the current data we have pulled from the stream but have not 86 /// returned to the client. This is specifically and intentionally defined to 87 /// follow the word size of the host machine for efficiency. We use word_t in 88 /// places that are aware of this to make it perfectly explicit what is going 89 /// on. 90 using word_t = size_t; 91 92private: 93 word_t CurWord = 0; 94 95 /// This is the number of bits in CurWord that are valid. This is always from 96 /// [0...bits_of(size_t)-1] inclusive. 97 unsigned BitsInCurWord = 0; 98 99public: 100 static const constexpr size_t MaxChunkSize = sizeof(word_t) * 8; 101 102 SimpleBitstreamCursor() = default; 103 explicit SimpleBitstreamCursor(ArrayRef<uint8_t> BitcodeBytes) 104 : BitcodeBytes(BitcodeBytes) {} 105 explicit SimpleBitstreamCursor(StringRef BitcodeBytes) 106 : BitcodeBytes(arrayRefFromStringRef(BitcodeBytes)) {} 107 explicit SimpleBitstreamCursor(MemoryBufferRef BitcodeBytes) 108 : SimpleBitstreamCursor(BitcodeBytes.getBuffer()) {} 109 110 bool canSkipToPos(size_t pos) const { 111 // pos can be skipped to if it is a valid address or one byte past the end. 112 return pos <= BitcodeBytes.size(); 113 } 114 115 bool AtEndOfStream() { 116 return BitsInCurWord == 0 && BitcodeBytes.size() <= NextChar; 117 } 118 119 /// Return the bit # of the bit we are reading. 120 uint64_t GetCurrentBitNo() const { 121 return NextChar*CHAR_BIT - BitsInCurWord; 122 } 123 124 // Return the byte # of the current bit. 125 uint64_t getCurrentByteNo() const { return GetCurrentBitNo() / 8; } 126 127 ArrayRef<uint8_t> getBitcodeBytes() const { return BitcodeBytes; } 128 129 /// Reset the stream to the specified bit number. 130 Error JumpToBit(uint64_t BitNo) { 131 size_t ByteNo = size_t(BitNo/8) & ~(sizeof(word_t)-1); 132 unsigned WordBitNo = unsigned(BitNo & (sizeof(word_t)*8-1)); 133 assert(canSkipToPos(ByteNo) && "Invalid location"); 134 135 // Move the cursor to the right word. 136 NextChar = ByteNo; 137 BitsInCurWord = 0; 138 139 // Skip over any bits that are already consumed. 140 if (WordBitNo) { 141 if (Expected<word_t> Res = Read(WordBitNo)) 142 return Error::success(); 143 else 144 return Res.takeError(); 145 } 146 147 return Error::success(); 148 } 149 150 /// Get a pointer into the bitstream at the specified byte offset. 151 const uint8_t *getPointerToByte(uint64_t ByteNo, uint64_t NumBytes) { 152 return BitcodeBytes.data() + ByteNo; 153 } 154 155 /// Get a pointer into the bitstream at the specified bit offset. 156 /// 157 /// The bit offset must be on a byte boundary. 158 const uint8_t *getPointerToBit(uint64_t BitNo, uint64_t NumBytes) { 159 assert(!(BitNo % 8) && "Expected bit on byte boundary"); 160 return getPointerToByte(BitNo / 8, NumBytes); 161 } 162 163 Error fillCurWord() { 164 if (NextChar >= BitcodeBytes.size()) 165 return createStringError(std::errc::io_error, 166 "Unexpected end of file reading %u of %u bytes", 167 NextChar, BitcodeBytes.size()); 168 169 // Read the next word from the stream. 170 const uint8_t *NextCharPtr = BitcodeBytes.data() + NextChar; 171 unsigned BytesRead; 172 if (BitcodeBytes.size() >= NextChar + sizeof(word_t)) { 173 BytesRead = sizeof(word_t); 174 CurWord = 175 support::endian::read<word_t, support::little, support::unaligned>( 176 NextCharPtr); 177 } else { 178 // Short read. 179 BytesRead = BitcodeBytes.size() - NextChar; 180 CurWord = 0; 181 for (unsigned B = 0; B != BytesRead; ++B) 182 CurWord |= uint64_t(NextCharPtr[B]) << (B * 8); 183 } 184 NextChar += BytesRead; 185 BitsInCurWord = BytesRead * 8; 186 return Error::success(); 187 } 188 189 Expected<word_t> Read(unsigned NumBits) { 190 static const unsigned BitsInWord = MaxChunkSize; 191 192 assert(NumBits && NumBits <= BitsInWord && 193 "Cannot return zero or more than BitsInWord bits!"); 194 195 static const unsigned Mask = sizeof(word_t) > 4 ? 0x3f : 0x1f; 196 197 // If the field is fully contained by CurWord, return it quickly. 198 if (BitsInCurWord >= NumBits) { 199 word_t R = CurWord & (~word_t(0) >> (BitsInWord - NumBits)); 200 201 // Use a mask to avoid undefined behavior. 202 CurWord >>= (NumBits & Mask); 203 204 BitsInCurWord -= NumBits; 205 return R; 206 } 207 208 word_t R = BitsInCurWord ? CurWord : 0; 209 unsigned BitsLeft = NumBits - BitsInCurWord; 210 211 if (Error fillResult = fillCurWord()) 212 return std::move(fillResult); 213 214 // If we run out of data, abort. 215 if (BitsLeft > BitsInCurWord) 216 return createStringError(std::errc::io_error, 217 "Unexpected end of file reading %u of %u bits", 218 BitsInCurWord, BitsLeft); 219 220 word_t R2 = CurWord & (~word_t(0) >> (BitsInWord - BitsLeft)); 221 222 // Use a mask to avoid undefined behavior. 223 CurWord >>= (BitsLeft & Mask); 224 225 BitsInCurWord -= BitsLeft; 226 227 R |= R2 << (NumBits - BitsLeft); 228 229 return R; 230 } 231 232 Expected<uint32_t> ReadVBR(unsigned NumBits) { 233 Expected<unsigned> MaybeRead = Read(NumBits); 234 if (!MaybeRead) 235 return MaybeRead; 236 uint32_t Piece = MaybeRead.get(); 237 238 if ((Piece & (1U << (NumBits-1))) == 0) 239 return Piece; 240 241 uint32_t Result = 0; 242 unsigned NextBit = 0; 243 while (true) { 244 Result |= (Piece & ((1U << (NumBits-1))-1)) << NextBit; 245 246 if ((Piece & (1U << (NumBits-1))) == 0) 247 return Result; 248 249 NextBit += NumBits-1; 250 MaybeRead = Read(NumBits); 251 if (!MaybeRead) 252 return MaybeRead; 253 Piece = MaybeRead.get(); 254 } 255 } 256 257 // Read a VBR that may have a value up to 64-bits in size. The chunk size of 258 // the VBR must still be <= 32 bits though. 259 Expected<uint64_t> ReadVBR64(unsigned NumBits) { 260 Expected<uint64_t> MaybeRead = Read(NumBits); 261 if (!MaybeRead) 262 return MaybeRead; 263 uint32_t Piece = MaybeRead.get(); 264 265 if ((Piece & (1U << (NumBits-1))) == 0) 266 return uint64_t(Piece); 267 268 uint64_t Result = 0; 269 unsigned NextBit = 0; 270 while (true) { 271 Result |= uint64_t(Piece & ((1U << (NumBits-1))-1)) << NextBit; 272 273 if ((Piece & (1U << (NumBits-1))) == 0) 274 return Result; 275 276 NextBit += NumBits-1; 277 MaybeRead = Read(NumBits); 278 if (!MaybeRead) 279 return MaybeRead; 280 Piece = MaybeRead.get(); 281 } 282 } 283 284 void SkipToFourByteBoundary() { 285 // If word_t is 64-bits and if we've read less than 32 bits, just dump 286 // the bits we have up to the next 32-bit boundary. 287 if (sizeof(word_t) > 4 && 288 BitsInCurWord >= 32) { 289 CurWord >>= BitsInCurWord-32; 290 BitsInCurWord = 32; 291 return; 292 } 293 294 BitsInCurWord = 0; 295 } 296 297 /// Return the size of the stream in bytes. 298 size_t SizeInBytes() const { return BitcodeBytes.size(); } 299 300 /// Skip to the end of the file. 301 void skipToEnd() { NextChar = BitcodeBytes.size(); } 302}; 303 304/// When advancing through a bitstream cursor, each advance can discover a few 305/// different kinds of entries: 306struct BitstreamEntry { 307 enum { 308 Error, // Malformed bitcode was found. 309 EndBlock, // We've reached the end of the current block, (or the end of the 310 // file, which is treated like a series of EndBlock records. 311 SubBlock, // This is the start of a new subblock of a specific ID. 312 Record // This is a record with a specific AbbrevID. 313 } Kind; 314 315 unsigned ID; 316 317 static BitstreamEntry getError() { 318 BitstreamEntry E; E.Kind = Error; return E; 319 } 320 321 static BitstreamEntry getEndBlock() { 322 BitstreamEntry E; E.Kind = EndBlock; return E; 323 } 324 325 static BitstreamEntry getSubBlock(unsigned ID) { 326 BitstreamEntry E; E.Kind = SubBlock; E.ID = ID; return E; 327 } 328 329 static BitstreamEntry getRecord(unsigned AbbrevID) { 330 BitstreamEntry E; E.Kind = Record; E.ID = AbbrevID; return E; 331 } 332}; 333 334/// This represents a position within a bitcode file, implemented on top of a 335/// SimpleBitstreamCursor. 336/// 337/// Unlike iterators, BitstreamCursors are heavy-weight objects that should not 338/// be passed by value. 339class BitstreamCursor : SimpleBitstreamCursor { 340 // This is the declared size of code values used for the current block, in 341 // bits. 342 unsigned CurCodeSize = 2; 343 344 /// Abbrevs installed at in this block. 345 std::vector<std::shared_ptr<BitCodeAbbrev>> CurAbbrevs; 346 347 struct Block { 348 unsigned PrevCodeSize; 349 std::vector<std::shared_ptr<BitCodeAbbrev>> PrevAbbrevs; 350 351 explicit Block(unsigned PCS) : PrevCodeSize(PCS) {} 352 }; 353 354 /// This tracks the codesize of parent blocks. 355 SmallVector<Block, 8> BlockScope; 356 357 BitstreamBlockInfo *BlockInfo = nullptr; 358 359public: 360 static const size_t MaxChunkSize = sizeof(word_t) * 8; 361 362 BitstreamCursor() = default; 363 explicit BitstreamCursor(ArrayRef<uint8_t> BitcodeBytes) 364 : SimpleBitstreamCursor(BitcodeBytes) {} 365 explicit BitstreamCursor(StringRef BitcodeBytes) 366 : SimpleBitstreamCursor(BitcodeBytes) {} 367 explicit BitstreamCursor(MemoryBufferRef BitcodeBytes) 368 : SimpleBitstreamCursor(BitcodeBytes) {} 369 370 using SimpleBitstreamCursor::AtEndOfStream; 371 using SimpleBitstreamCursor::canSkipToPos; 372 using SimpleBitstreamCursor::fillCurWord; 373 using SimpleBitstreamCursor::getBitcodeBytes; 374 using SimpleBitstreamCursor::GetCurrentBitNo; 375 using SimpleBitstreamCursor::getCurrentByteNo; 376 using SimpleBitstreamCursor::getPointerToByte; 377 using SimpleBitstreamCursor::JumpToBit; 378 using SimpleBitstreamCursor::Read; 379 using SimpleBitstreamCursor::ReadVBR; 380 using SimpleBitstreamCursor::ReadVBR64; 381 using SimpleBitstreamCursor::SizeInBytes; 382 using SimpleBitstreamCursor::skipToEnd; 383 384 /// Return the number of bits used to encode an abbrev #. 385 unsigned getAbbrevIDWidth() const { return CurCodeSize; } 386 387 /// Flags that modify the behavior of advance(). 388 enum { 389 /// If this flag is used, the advance() method does not automatically pop 390 /// the block scope when the end of a block is reached. 391 AF_DontPopBlockAtEnd = 1, 392 393 /// If this flag is used, abbrev entries are returned just like normal 394 /// records. 395 AF_DontAutoprocessAbbrevs = 2 396 }; 397 398 /// Advance the current bitstream, returning the next entry in the stream. 399 Expected<BitstreamEntry> advance(unsigned Flags = 0) { 400 while (true) { 401 if (AtEndOfStream()) 402 return BitstreamEntry::getError(); 403 404 Expected<unsigned> MaybeCode = ReadCode(); 405 if (!MaybeCode) 406 return MaybeCode.takeError(); 407 unsigned Code = MaybeCode.get(); 408 409 if (Code == bitc::END_BLOCK) { 410 // Pop the end of the block unless Flags tells us not to. 411 if (!(Flags & AF_DontPopBlockAtEnd) && ReadBlockEnd()) 412 return BitstreamEntry::getError(); 413 return BitstreamEntry::getEndBlock(); 414 } 415 416 if (Code == bitc::ENTER_SUBBLOCK) { 417 if (Expected<unsigned> MaybeSubBlock = ReadSubBlockID()) 418 return BitstreamEntry::getSubBlock(MaybeSubBlock.get()); 419 else 420 return MaybeSubBlock.takeError(); 421 } 422 423 if (Code == bitc::DEFINE_ABBREV && 424 !(Flags & AF_DontAutoprocessAbbrevs)) { 425 // We read and accumulate abbrev's, the client can't do anything with 426 // them anyway. 427 if (Error Err = ReadAbbrevRecord()) 428 return std::move(Err); 429 continue; 430 } 431 432 return BitstreamEntry::getRecord(Code); 433 } 434 } 435 436 /// This is a convenience function for clients that don't expect any 437 /// subblocks. This just skips over them automatically. 438 Expected<BitstreamEntry> advanceSkippingSubblocks(unsigned Flags = 0) { 439 while (true) { 440 // If we found a normal entry, return it. 441 Expected<BitstreamEntry> MaybeEntry = advance(Flags); 442 if (!MaybeEntry) 443 return MaybeEntry; 444 BitstreamEntry Entry = MaybeEntry.get(); 445 446 if (Entry.Kind != BitstreamEntry::SubBlock) 447 return Entry; 448 449 // If we found a sub-block, just skip over it and check the next entry. 450 if (Error Err = SkipBlock()) 451 return std::move(Err); 452 } 453 } 454 455 Expected<unsigned> ReadCode() { return Read(CurCodeSize); } 456 457 // Block header: 458 // [ENTER_SUBBLOCK, blockid, newcodelen, <align4bytes>, blocklen] 459 460 /// Having read the ENTER_SUBBLOCK code, read the BlockID for the block. 461 Expected<unsigned> ReadSubBlockID() { return ReadVBR(bitc::BlockIDWidth); } 462 463 /// Having read the ENTER_SUBBLOCK abbrevid and a BlockID, skip over the body 464 /// of this block. 465 Error SkipBlock() { 466 // Read and ignore the codelen value. 467 if (Expected<uint32_t> Res = ReadVBR(bitc::CodeLenWidth)) 468 ; // Since we are skipping this block, we don't care what code widths are 469 // used inside of it. 470 else 471 return Res.takeError(); 472 473 SkipToFourByteBoundary(); 474 Expected<unsigned> MaybeNum = Read(bitc::BlockSizeWidth); 475 if (!MaybeNum) 476 return MaybeNum.takeError(); 477 size_t NumFourBytes = MaybeNum.get(); 478 479 // Check that the block wasn't partially defined, and that the offset isn't 480 // bogus. 481 size_t SkipTo = GetCurrentBitNo() + NumFourBytes * 4 * 8; 482 if (AtEndOfStream()) 483 return createStringError(std::errc::illegal_byte_sequence, 484 "can't skip block: already at end of stream"); 485 if (!canSkipToPos(SkipTo / 8)) 486 return createStringError(std::errc::illegal_byte_sequence, 487 "can't skip to bit %zu from %" PRIu64, SkipTo, 488 GetCurrentBitNo()); 489 490 if (Error Res = JumpToBit(SkipTo)) 491 return Res; 492 493 return Error::success(); 494 } 495 496 /// Having read the ENTER_SUBBLOCK abbrevid, and enter the block. 497 Error EnterSubBlock(unsigned BlockID, unsigned *NumWordsP = nullptr); 498 499 bool ReadBlockEnd() { 500 if (BlockScope.empty()) return true; 501 502 // Block tail: 503 // [END_BLOCK, <align4bytes>] 504 SkipToFourByteBoundary(); 505 506 popBlockScope(); 507 return false; 508 } 509 510private: 511 void popBlockScope() { 512 CurCodeSize = BlockScope.back().PrevCodeSize; 513 514 CurAbbrevs = std::move(BlockScope.back().PrevAbbrevs); 515 BlockScope.pop_back(); 516 } 517 518 //===--------------------------------------------------------------------===// 519 // Record Processing 520 //===--------------------------------------------------------------------===// 521 522public: 523 /// Return the abbreviation for the specified AbbrevId. 524 const BitCodeAbbrev *getAbbrev(unsigned AbbrevID) { 525 unsigned AbbrevNo = AbbrevID - bitc::FIRST_APPLICATION_ABBREV; 526 if (AbbrevNo >= CurAbbrevs.size()) 527 report_fatal_error("Invalid abbrev number"); 528 return CurAbbrevs[AbbrevNo].get(); 529 } 530 531 /// Read the current record and discard it, returning the code for the record. 532 Expected<unsigned> skipRecord(unsigned AbbrevID); 533 534 Expected<unsigned> readRecord(unsigned AbbrevID, 535 SmallVectorImpl<uint64_t> &Vals, 536 StringRef *Blob = nullptr); 537 538 //===--------------------------------------------------------------------===// 539 // Abbrev Processing 540 //===--------------------------------------------------------------------===// 541 Error ReadAbbrevRecord(); 542 543 /// Read and return a block info block from the bitstream. If an error was 544 /// encountered, return None. 545 /// 546 /// \param ReadBlockInfoNames Whether to read block/record name information in 547 /// the BlockInfo block. Only llvm-bcanalyzer uses this. 548 Expected<Optional<BitstreamBlockInfo>> 549 ReadBlockInfoBlock(bool ReadBlockInfoNames = false); 550 551 /// Set the block info to be used by this BitstreamCursor to interpret 552 /// abbreviated records. 553 void setBlockInfo(BitstreamBlockInfo *BI) { BlockInfo = BI; } 554}; 555 556} // end llvm namespace 557 558#endif // LLVM_BITSTREAM_BITSTREAMREADER_H 559