X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FBitcode%2FBitstreamReader.h;h=bae816675c00d785a15e7bcab1808a057d87c114;hb=4c0055402f2c82d54555c98d24e2ea1a8abbe1f5;hp=8d70f1f7133e990dbb3b47df5d5289af83a17646;hpb=2bbb703e4f84c68a9603838c32eba7423ed54b71;p=oota-llvm.git diff --git a/include/llvm/Bitcode/BitstreamReader.h b/include/llvm/Bitcode/BitstreamReader.h index 8d70f1f7133..bae816675c0 100644 --- a/include/llvm/Bitcode/BitstreamReader.h +++ b/include/llvm/Bitcode/BitstreamReader.h @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by Chris Lattner and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -12,150 +12,368 @@ // //===----------------------------------------------------------------------===// -#ifndef BITSTREAM_READER_H -#define BITSTREAM_READER_H +#ifndef LLVM_BITCODE_BITSTREAMREADER_H +#define LLVM_BITCODE_BITSTREAMREADER_H #include "llvm/Bitcode/BitCodes.h" +#include "llvm/Support/Endian.h" +#include "llvm/Support/StreamingMemoryObject.h" +#include +#include #include namespace llvm { - + +/// This class is used to read from an LLVM bitcode stream, maintaining +/// information that is global to decoding the entire file. While a file is +/// being read, multiple cursors can be independently advanced or skipped around +/// within the file. These are represented by the BitstreamCursor class. class BitstreamReader { - const unsigned char *NextChar; - const unsigned char *LastChar; - - /// CurWord - This is the current data we have pulled from the stream but have - /// not returned to the client. - uint32_t CurWord; - - /// BitsInCurWord - This is the number of bits in CurWord that are valid. This - /// is always from [0...31] inclusive. +public: + /// This contains information emitted to BLOCKINFO_BLOCK blocks. These + /// describe abbreviations that all blocks of the specified ID inherit. + struct BlockInfo { + unsigned BlockID; + std::vector> Abbrevs; + std::string Name; + + std::vector > RecordNames; + }; +private: + std::unique_ptr BitcodeBytes; + + std::vector BlockInfoRecords; + + /// This is set to true if we don't care about the block/record name + /// information in the BlockInfo block. Only llvm-bcanalyzer uses this. + bool IgnoreBlockInfoNames; + + BitstreamReader(const BitstreamReader&) = delete; + void operator=(const BitstreamReader&) = delete; +public: + BitstreamReader() : IgnoreBlockInfoNames(true) { + } + + BitstreamReader(const unsigned char *Start, const unsigned char *End) + : IgnoreBlockInfoNames(true) { + init(Start, End); + } + + BitstreamReader(std::unique_ptr BitcodeBytes) + : BitcodeBytes(std::move(BitcodeBytes)), IgnoreBlockInfoNames(true) {} + + BitstreamReader(BitstreamReader &&Other) { + *this = std::move(Other); + } + + BitstreamReader &operator=(BitstreamReader &&Other) { + BitcodeBytes = std::move(Other.BitcodeBytes); + // Explicitly swap block info, so that nothing gets destroyed twice. + std::swap(BlockInfoRecords, Other.BlockInfoRecords); + IgnoreBlockInfoNames = Other.IgnoreBlockInfoNames; + return *this; + } + + void init(const unsigned char *Start, const unsigned char *End) { + assert(((End-Start) & 3) == 0 &&"Bitcode stream not a multiple of 4 bytes"); + BitcodeBytes.reset(getNonStreamedMemoryObject(Start, End)); + } + + MemoryObject &getBitcodeBytes() { return *BitcodeBytes; } + + /// This is called by clients that want block/record name information. + void CollectBlockInfoNames() { IgnoreBlockInfoNames = false; } + bool isIgnoringBlockInfoNames() { return IgnoreBlockInfoNames; } + + //===--------------------------------------------------------------------===// + // Block Manipulation + //===--------------------------------------------------------------------===// + + /// Return true if we've already read and processed the block info block for + /// this Bitstream. We only process it for the first cursor that walks over + /// it. + bool hasBlockInfoRecords() const { return !BlockInfoRecords.empty(); } + + /// If there is block info for the specified ID, return it, otherwise return + /// null. + const BlockInfo *getBlockInfo(unsigned BlockID) const { + // Common case, the most recent entry matches BlockID. + if (!BlockInfoRecords.empty() && BlockInfoRecords.back().BlockID == BlockID) + return &BlockInfoRecords.back(); + + for (unsigned i = 0, e = static_cast(BlockInfoRecords.size()); + i != e; ++i) + if (BlockInfoRecords[i].BlockID == BlockID) + return &BlockInfoRecords[i]; + return nullptr; + } + + BlockInfo &getOrCreateBlockInfo(unsigned BlockID) { + if (const BlockInfo *BI = getBlockInfo(BlockID)) + return *const_cast(BI); + + // Otherwise, add a new record. + BlockInfoRecords.push_back(BlockInfo()); + BlockInfoRecords.back().BlockID = BlockID; + return BlockInfoRecords.back(); + } + + /// Takes block info from the other bitstream reader. + /// + /// This is a "take" operation because BlockInfo records are non-trivial, and + /// indeed rather expensive. + void takeBlockInfo(BitstreamReader &&Other) { + assert(!hasBlockInfoRecords()); + BlockInfoRecords = std::move(Other.BlockInfoRecords); + } +}; + +/// When advancing through a bitstream cursor, each advance can discover a few +/// different kinds of entries: +struct BitstreamEntry { + enum { + Error, // Malformed bitcode was found. + EndBlock, // We've reached the end of the current block, (or the end of the + // file, which is treated like a series of EndBlock records. + SubBlock, // This is the start of a new subblock of a specific ID. + Record // This is a record with a specific AbbrevID. + } Kind; + + unsigned ID; + + static BitstreamEntry getError() { + BitstreamEntry E; E.Kind = Error; return E; + } + static BitstreamEntry getEndBlock() { + BitstreamEntry E; E.Kind = EndBlock; return E; + } + static BitstreamEntry getSubBlock(unsigned ID) { + BitstreamEntry E; E.Kind = SubBlock; E.ID = ID; return E; + } + static BitstreamEntry getRecord(unsigned AbbrevID) { + BitstreamEntry E; E.Kind = Record; E.ID = AbbrevID; return E; + } +}; + +/// This represents a position within a bitcode file. There may be multiple +/// independent cursors reading within one bitstream, each maintaining their own +/// local state. +/// +/// Unlike iterators, BitstreamCursors are heavy-weight objects that should not +/// be passed by value. +class BitstreamCursor { + BitstreamReader *BitStream; + size_t NextChar; + + // The size of the bicode. 0 if we don't know it yet. + size_t Size; + + /// This is the current data we have pulled from the stream but have not + /// returned to the client. This is specifically and intentionally defined to + /// follow the word size of the host machine for efficiency. We use word_t in + /// places that are aware of this to make it perfectly explicit what is going + /// on. + typedef size_t word_t; + word_t CurWord; + + /// This is the number of bits in CurWord that are valid. This is always from + /// [0...bits_of(size_t)-1] inclusive. unsigned BitsInCurWord; - - // CurCodeSize - This is the declared size of code values used for the current - // block, in bits. + + // This is the declared size of code values used for the current block, in + // bits. unsigned CurCodeSize; - /// CurAbbrevs - Abbrevs installed at in this block. - std::vector CurAbbrevs; - + /// Abbrevs installed at in this block. + std::vector> CurAbbrevs; + struct Block { unsigned PrevCodeSize; - std::vector PrevAbbrevs; + std::vector> PrevAbbrevs; explicit Block(unsigned PCS) : PrevCodeSize(PCS) {} }; - - /// BlockScope - This tracks the codesize of parent blocks. + + /// This tracks the codesize of parent blocks. SmallVector BlockScope; - /// FirstChar - This remembers the first byte of the stream. - const unsigned char *FirstChar; + public: - BitstreamReader() { - NextChar = FirstChar = LastChar = 0; - CurWord = 0; + BitstreamCursor() { init(nullptr); } + + explicit BitstreamCursor(BitstreamReader &R) { init(&R); } + + void init(BitstreamReader *R) { + freeState(); + + BitStream = R; + NextChar = 0; + Size = 0; BitsInCurWord = 0; - CurCodeSize = 0; + CurCodeSize = 2; } - BitstreamReader(const unsigned char *Start, const unsigned char *End) { - init(Start, End); + void freeState(); + + bool canSkipToPos(size_t pos) const { + // pos can be skipped to if it is a valid address or one byte past the end. + return pos == 0 || BitStream->getBitcodeBytes().isValidAddress( + static_cast(pos - 1)); } - - void init(const unsigned char *Start, const unsigned char *End) { - NextChar = FirstChar = Start; - LastChar = End; - assert(((End-Start) & 3) == 0 &&"Bitcode stream not a multiple of 4 bytes"); - CurWord = 0; - BitsInCurWord = 0; - CurCodeSize = 2; + + bool AtEndOfStream() { + if (BitsInCurWord != 0) + return false; + if (Size != 0) + return Size == NextChar; + fillCurWord(); + return BitsInCurWord == 0; + } + + /// Return the number of bits used to encode an abbrev #. + unsigned getAbbrevIDWidth() const { return CurCodeSize; } + + /// Return the bit # of the bit we are reading. + uint64_t GetCurrentBitNo() const { + return NextChar*CHAR_BIT - BitsInCurWord; + } + + BitstreamReader *getBitStreamReader() { + return BitStream; } - - ~BitstreamReader() { - // Abbrevs could still exist if the stream was broken. If so, don't leak - // them. - for (unsigned i = 0, e = CurAbbrevs.size(); i != e; ++i) - delete CurAbbrevs[i]; - - for (unsigned S = 0, e = BlockScope.size(); S != e; ++S) { - std::vector &Abbrevs = BlockScope[S].PrevAbbrevs; - for (unsigned i = 0, e = Abbrevs.size(); i != e; ++i) - delete Abbrevs[i]; + const BitstreamReader *getBitStreamReader() const { + return BitStream; + } + + /// Flags that modify the behavior of advance(). + enum { + /// If this flag is used, the advance() method does not automatically pop + /// the block scope when the end of a block is reached. + AF_DontPopBlockAtEnd = 1, + + /// If this flag is used, abbrev entries are returned just like normal + /// records. + AF_DontAutoprocessAbbrevs = 2 + }; + + /// Advance the current bitstream, returning the next entry in the stream. + BitstreamEntry advance(unsigned Flags = 0) { + while (1) { + unsigned Code = ReadCode(); + if (Code == bitc::END_BLOCK) { + // Pop the end of the block unless Flags tells us not to. + if (!(Flags & AF_DontPopBlockAtEnd) && ReadBlockEnd()) + return BitstreamEntry::getError(); + return BitstreamEntry::getEndBlock(); + } + + if (Code == bitc::ENTER_SUBBLOCK) + return BitstreamEntry::getSubBlock(ReadSubBlockID()); + + if (Code == bitc::DEFINE_ABBREV && + !(Flags & AF_DontAutoprocessAbbrevs)) { + // We read and accumulate abbrev's, the client can't do anything with + // them anyway. + ReadAbbrevRecord(); + continue; + } + + return BitstreamEntry::getRecord(Code); } } - - bool AtEndOfStream() const { return NextChar == LastChar; } - - /// GetCurrentBitNo - Return the bit # of the bit we are reading. - uint64_t GetCurrentBitNo() const { - return (NextChar-FirstChar)*8 + (32-BitsInCurWord); + + /// This is a convenience function for clients that don't expect any + /// subblocks. This just skips over them automatically. + BitstreamEntry advanceSkippingSubblocks(unsigned Flags = 0) { + while (1) { + // If we found a normal entry, return it. + BitstreamEntry Entry = advance(Flags); + if (Entry.Kind != BitstreamEntry::SubBlock) + return Entry; + + // If we found a sub-block, just skip over it and check the next entry. + if (SkipBlock()) + return BitstreamEntry::getError(); + } } - - /// JumpToBit - Reset the stream to the specified bit number. + + /// Reset the stream to the specified bit number. void JumpToBit(uint64_t BitNo) { - unsigned ByteNo = (BitNo/8) & ~3; - unsigned WordBitNo = BitNo & 31; - assert(ByteNo < (unsigned)(LastChar-FirstChar) && "Invalid location"); - + size_t ByteNo = size_t(BitNo/8) & ~(sizeof(word_t)-1); + unsigned WordBitNo = unsigned(BitNo & (sizeof(word_t)*8-1)); + assert(canSkipToPos(ByteNo) && "Invalid location"); + // Move the cursor to the right word. - NextChar = FirstChar+ByteNo; + NextChar = ByteNo; BitsInCurWord = 0; - + // Skip over any bits that are already consumed. - if (WordBitNo) { - NextChar -= 4; + if (WordBitNo) Read(WordBitNo); + } + + void fillCurWord() { + if (Size != 0 && NextChar >= Size) + report_fatal_error("Unexpected end of file"); + + // Read the next word from the stream. + uint8_t Array[sizeof(word_t)] = {0}; + + uint64_t BytesRead = + BitStream->getBitcodeBytes().readBytes(Array, sizeof(Array), NextChar); + + // If we run out of data, stop at the end of the stream. + if (BytesRead == 0) { + Size = NextChar; + return; } + + CurWord = + support::endian::read( + Array); + NextChar += BytesRead; + BitsInCurWord = BytesRead * 8; } - - /// GetAbbrevIDWidth - Return the number of bits used to encode an abbrev #. - unsigned GetAbbrevIDWidth() const { return CurCodeSize; } - - uint32_t Read(unsigned NumBits) { + + word_t Read(unsigned NumBits) { + static const unsigned BitsInWord = sizeof(word_t) * 8; + + assert(NumBits && NumBits <= BitsInWord && + "Cannot return zero or more than BitsInWord bits!"); + + static const unsigned Mask = sizeof(word_t) > 4 ? 0x3f : 0x1f; + // If the field is fully contained by CurWord, return it quickly. if (BitsInCurWord >= NumBits) { - uint32_t R = CurWord & ((1U << NumBits)-1); - CurWord >>= NumBits; + word_t R = CurWord & (~word_t(0) >> (BitsInWord - NumBits)); + + // Use a mask to avoid undefined behavior. + CurWord >>= (NumBits & Mask); + BitsInCurWord -= NumBits; return R; } + word_t R = BitsInCurWord ? CurWord : 0; + unsigned BitsLeft = NumBits - BitsInCurWord; + + fillCurWord(); + // If we run out of data, stop at the end of the stream. - if (LastChar == NextChar) { - CurWord = 0; - BitsInCurWord = 0; + if (BitsLeft > BitsInCurWord) return 0; - } - - unsigned R = CurWord; - // Read the next word from the stream. - CurWord = (NextChar[0] << 0) | (NextChar[1] << 8) | - (NextChar[2] << 16) | (NextChar[3] << 24); - NextChar += 4; - - // Extract NumBits-BitsInCurWord from what we just read. - unsigned BitsLeft = NumBits-BitsInCurWord; - - // Be careful here, BitsLeft is in the range [1..32] inclusive. - R |= (CurWord & (~0U >> (32-BitsLeft))) << BitsInCurWord; - - // BitsLeft bits have just been used up from CurWord. - if (BitsLeft != 32) - CurWord >>= BitsLeft; - else - CurWord = 0; - BitsInCurWord = 32-BitsLeft; + word_t R2 = CurWord & (~word_t(0) >> (BitsInWord - BitsLeft)); + + // Use a mask to avoid undefined behavior. + CurWord >>= (BitsLeft & Mask); + + BitsInCurWord -= BitsLeft; + + R |= R2 << (NumBits - BitsLeft); + return R; } - - uint64_t Read64(unsigned NumBits) { - if (NumBits <= 32) return Read(NumBits); - - uint64_t V = Read(32); - return V | (uint64_t)Read(NumBits-32) << 32; - } - + uint32_t ReadVBR(unsigned NumBits) { uint32_t Piece = Read(NumBits); if ((Piece & (1U << (NumBits-1))) == 0) @@ -168,172 +386,129 @@ public: if ((Piece & (1U << (NumBits-1))) == 0) return Result; - + NextBit += NumBits-1; Piece = Read(NumBits); } } - + + // Read a VBR that may have a value up to 64-bits in size. The chunk size of + // the VBR must still be <= 32 bits though. uint64_t ReadVBR64(unsigned NumBits) { - uint64_t Piece = Read(NumBits); + assert(NumBits <= 64 && "VBR can only be up to 64 bits in size."); + uint32_t Piece = Read(NumBits); if ((Piece & (1U << (NumBits-1))) == 0) - return Piece; - + return uint64_t(Piece); + uint64_t Result = 0; unsigned NextBit = 0; while (1) { - Result |= (Piece & ((1U << (NumBits-1))-1)) << NextBit; - + Result |= uint64_t(Piece & ((1U << (NumBits-1))-1)) << NextBit; + if ((Piece & (1U << (NumBits-1))) == 0) return Result; - + NextBit += NumBits-1; Piece = Read(NumBits); } } - void SkipToWord() { +private: + void SkipToFourByteBoundary() { + // If word_t is 64-bits and if we've read less than 32 bits, just dump + // the bits we have up to the next 32-bit boundary. + if (sizeof(word_t) > 4 && + BitsInCurWord >= 32) { + CurWord >>= BitsInCurWord-32; + BitsInCurWord = 32; + return; + } + BitsInCurWord = 0; - CurWord = 0; } +public: - unsigned ReadCode() { return Read(CurCodeSize); } - //===--------------------------------------------------------------------===// - // Block Manipulation - //===--------------------------------------------------------------------===// - + // Block header: // [ENTER_SUBBLOCK, blockid, newcodelen, , blocklen] - /// ReadSubBlockID - Having read the ENTER_SUBBLOCK code, read the BlockID for - /// the block. + /// Having read the ENTER_SUBBLOCK code, read the BlockID for the block. unsigned ReadSubBlockID() { return ReadVBR(bitc::BlockIDWidth); } - - /// SkipBlock - Having read the ENTER_SUBBLOCK abbrevid and a BlockID, skip - /// over the body of this block. If the block record is malformed, return - /// true. + + /// Having read the ENTER_SUBBLOCK abbrevid and a BlockID, skip over the body + /// of this block. If the block record is malformed, return true. bool SkipBlock() { // Read and ignore the codelen value. Since we are skipping this block, we // don't care what code widths are used inside of it. ReadVBR(bitc::CodeLenWidth); - SkipToWord(); - unsigned NumWords = Read(bitc::BlockSizeWidth); - + SkipToFourByteBoundary(); + unsigned NumFourBytes = Read(bitc::BlockSizeWidth); + // Check that the block wasn't partially defined, and that the offset isn't // bogus. - if (AtEndOfStream() || NextChar+NumWords*4 > LastChar) + size_t SkipTo = GetCurrentBitNo() + NumFourBytes*4*8; + if (AtEndOfStream() || !canSkipToPos(SkipTo/8)) return true; - - NextChar += NumWords*4; - return false; - } - - /// EnterSubBlock - Having read the ENTER_SUBBLOCK abbrevid, read and enter - /// the block, returning the BlockID of the block we just entered. - bool EnterSubBlock(unsigned *NumWordsP = 0) { - BlockScope.push_back(Block(CurCodeSize)); - BlockScope.back().PrevAbbrevs.swap(CurAbbrevs); - - // Get the codesize of this block. - CurCodeSize = ReadVBR(bitc::CodeLenWidth); - SkipToWord(); - unsigned NumWords = Read(bitc::BlockSizeWidth); - if (NumWordsP) *NumWordsP = NumWords; - - // Validate that this block is sane. - if (CurCodeSize == 0 || AtEndOfStream() || NextChar+NumWords*4 > LastChar) - return true; - + + JumpToBit(SkipTo); return false; } - + + /// Having read the ENTER_SUBBLOCK abbrevid, enter the block, and return true + /// if the block has an error. + bool EnterSubBlock(unsigned BlockID, unsigned *NumWordsP = nullptr); + bool ReadBlockEnd() { if (BlockScope.empty()) return true; - + // Block tail: // [END_BLOCK, ] - SkipToWord(); + SkipToFourByteBoundary(); + + popBlockScope(); + return false; + } + +private: + + void popBlockScope() { CurCodeSize = BlockScope.back().PrevCodeSize; - - // Delete abbrevs from popped scope. - for (unsigned i = 0, e = CurAbbrevs.size(); i != e; ++i) - delete CurAbbrevs[i]; - - BlockScope.back().PrevAbbrevs.swap(CurAbbrevs); + + CurAbbrevs = std::move(BlockScope.back().PrevAbbrevs); BlockScope.pop_back(); - return false; } - + //===--------------------------------------------------------------------===// // Record Processing //===--------------------------------------------------------------------===// - - unsigned ReadRecord(unsigned AbbrevID, SmallVectorImpl &Vals) { - if (AbbrevID == bitc::UNABBREV_RECORD) { - unsigned Code = ReadVBR(6); - unsigned NumElts = ReadVBR(6); - for (unsigned i = 0; i != NumElts; ++i) - Vals.push_back(ReadVBR64(6)); - return Code; - } - - unsigned AbbrevNo = AbbrevID-bitc::FIRST_ABBREV; - assert(AbbrevNo < CurAbbrevs.size() && "Invalid abbrev #!"); - BitCodeAbbrev *Abbv = CurAbbrevs[AbbrevNo]; - - for (unsigned i = 0, e = Abbv->getNumOperandInfos(); i != e; ++i) { - const BitCodeAbbrevOp &Op = Abbv->getOperandInfo(i); - if (Op.isLiteral()) { - // If the abbrev specifies the literal value to use, use it. - Vals.push_back(Op.getLiteralValue()); - } else { - // Decode the value as we are commanded. - switch (Op.getEncoding()) { - default: assert(0 && "Unknown encoding!"); - case BitCodeAbbrevOp::FixedWidth: - Vals.push_back(Read(Op.getEncodingData())); - break; - case BitCodeAbbrevOp::VBR: - Vals.push_back(ReadVBR64(Op.getEncodingData())); - break; - } - } - } - - unsigned Code = Vals[0]; - Vals.erase(Vals.begin()); - return Code; + +public: + /// Return the abbreviation for the specified AbbrevId. + const BitCodeAbbrev *getAbbrev(unsigned AbbrevID) { + unsigned AbbrevNo = AbbrevID - bitc::FIRST_APPLICATION_ABBREV; + if (AbbrevNo >= CurAbbrevs.size()) + report_fatal_error("Invalid abbrev number"); + return CurAbbrevs[AbbrevNo].get(); } - + + /// Read the current record and discard it. + void skipRecord(unsigned AbbrevID); + + unsigned readRecord(unsigned AbbrevID, SmallVectorImpl &Vals, + StringRef *Blob = nullptr); + //===--------------------------------------------------------------------===// // Abbrev Processing //===--------------------------------------------------------------------===// - - void ReadAbbrevRecord() { - BitCodeAbbrev *Abbv = new BitCodeAbbrev(); - unsigned NumOpInfo = ReadVBR(5); - for (unsigned i = 0; i != NumOpInfo; ++i) { - bool IsLiteral = Read(1); - if (IsLiteral) { - Abbv->Add(BitCodeAbbrevOp(ReadVBR64(8))); - continue; - } + void ReadAbbrevRecord(); - BitCodeAbbrevOp::Encoding E = (BitCodeAbbrevOp::Encoding)Read(3); - if (BitCodeAbbrevOp::hasEncodingData(E)) { - Abbv->Add(BitCodeAbbrevOp(E, ReadVBR64(5))); - } else { - assert(0 && "unimp"); - } - } - CurAbbrevs.push_back(Abbv); - } + bool ReadBlockInfoBlock(); }; } // End llvm namespace