1 //===-- Reader.h - Interface To Bytecode Reading ----------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Reid Spencer and is distributed under the
6 // University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This header file defines the interface to the Bytecode Reader which is
11 // responsible for correctly interpreting bytecode files (backwards compatible)
12 // and materializing a module from the bytecode read.
14 //===----------------------------------------------------------------------===//
16 #ifndef BYTECODE_PARSER_H
17 #define BYTECODE_PARSER_H
19 #include "llvm/Constants.h"
20 #include "llvm/DerivedTypes.h"
21 #include "llvm/GlobalValue.h"
22 #include "llvm/Function.h"
23 #include "llvm/ModuleProvider.h"
24 #include "llvm/Bytecode/Analyzer.h"
30 class BytecodeHandler; ///< Forward declare the handler interface
32 /// This class defines the interface for parsing a buffer of bytecode. The
33 /// parser itself takes no action except to call the various functions of
34 /// the handler interface. The parser's sole responsibility is the correct
35 /// interpretation of the bytecode buffer. The handler is responsible for
36 /// instantiating and keeping track of all values. As a convenience, the parser
37 /// is responsible for materializing types and will pass them through the
38 /// handler interface as necessary.
39 /// @see BytecodeHandler
40 /// @brief Bytecode Reader interface
41 class BytecodeReader : public ModuleProvider {
43 /// @name Constructors
46 /// @brief Default constructor. By default, no handler is used.
47 BytecodeReader(BytecodeHandler* h = 0) {
48 decompressedBlock = 0;
54 if (decompressedBlock) {
55 ::free(decompressedBlock);
56 decompressedBlock = 0;
65 /// @brief A convenience type for the buffer pointer
66 typedef const unsigned char* BufPtr;
68 /// @brief The type used for a vector of potentially abstract types
69 typedef std::vector<PATypeHolder> TypeListTy;
71 /// This type provides a vector of Value* via the User class for
72 /// storage of Values that have been constructed when reading the
73 /// bytecode. Because of forward referencing, constant replacement
74 /// can occur so we ensure that our list of Value* is updated
75 /// properly through those transitions. This ensures that the
76 /// correct Value* is in our list when it comes time to associate
77 /// constants with global variables at the end of reading the
79 /// @brief A list of values as a User of those Values.
80 struct ValueList : public User {
81 ValueList() : User(Type::VoidTy, Value::ValueListVal) {}
83 // vector compatibility methods
84 unsigned size() const { return getNumOperands(); }
85 void push_back(Value *V) { Operands.push_back(Use(V, this)); }
86 Value *back() const { return Operands.back(); }
87 void pop_back() { Operands.pop_back(); }
88 bool empty() const { return Operands.empty(); }
90 virtual void print(std::ostream& os) const {
91 for ( unsigned i = 0; i < size(); i++ ) {
93 getOperand(i)->print(os);
99 /// @brief A 2 dimensional table of values
100 typedef std::vector<ValueList*> ValueTable;
102 /// This map is needed so that forward references to constants can be looked
103 /// up by Type and slot number when resolving those references.
104 /// @brief A mapping of a Type/slot pair to a Constant*.
105 typedef std::map<std::pair<const Type*,unsigned>, Constant*> ConstantRefsType;
107 /// For lazy read-in of functions, we need to save the location in the
108 /// data stream where the function is located. This structure provides that
109 /// information. Lazy read-in is used mostly by the JIT which only wants to
110 /// resolve functions as it needs them.
111 /// @brief Keeps pointers to function contents for later use.
112 struct LazyFunctionInfo {
113 const unsigned char *Buf, *EndBuf;
114 LazyFunctionInfo(const unsigned char *B = 0, const unsigned char *EB = 0)
115 : Buf(B), EndBuf(EB) {}
118 /// @brief A mapping of functions to their LazyFunctionInfo for lazy reading.
119 typedef std::map<Function*, LazyFunctionInfo> LazyFunctionMap;
121 /// @brief A list of global variables and the slot number that initializes
123 typedef std::vector<std::pair<GlobalVariable*, unsigned> > GlobalInitsList;
125 /// This type maps a typeslot/valueslot pair to the corresponding Value*.
126 /// It is used for dealing with forward references as values are read in.
127 /// @brief A map for dealing with forward references of values.
128 typedef std::map<std::pair<unsigned,unsigned>,Value*> ForwardReferenceMap;
134 /// @brief Main interface to parsing a bytecode buffer.
136 const unsigned char *Buf, ///< Beginning of the bytecode buffer
137 unsigned Length, ///< Length of the bytecode buffer
138 const std::string &ModuleID ///< An identifier for the module constructed.
141 /// @brief Parse all function bodies
142 void ParseAllFunctionBodies();
144 /// @brief Parse the next function of specific type
145 void ParseFunction(Function* Func) ;
147 /// This method is abstract in the parent ModuleProvider class. Its
148 /// implementation is identical to the ParseFunction method.
149 /// @see ParseFunction
150 /// @brief Make a specific function materialize.
151 virtual void materializeFunction(Function *F) {
152 LazyFunctionMap::iterator Fi = LazyFunctionLoadMap.find(F);
153 if (Fi == LazyFunctionLoadMap.end()) return;
157 /// This method is abstract in the parent ModuleProvider class. Its
158 /// implementation is identical to ParseAllFunctionBodies.
159 /// @see ParseAllFunctionBodies
160 /// @brief Make the whole module materialize
161 virtual Module* materializeModule() {
162 ParseAllFunctionBodies();
166 /// This method is provided by the parent ModuleProvde class and overriden
167 /// here. It simply releases the module from its provided and frees up our
169 /// @brief Release our hold on the generated module
170 Module* releaseModule() {
171 // Since we're losing control of this Module, we must hand it back complete
172 Module *M = ModuleProvider::releaseModule();
178 /// @name Parsing Units For Subclasses
181 /// @brief Parse whole module scope
184 /// @brief Parse the version information block
185 void ParseVersionInfo();
187 /// @brief Parse the ModuleGlobalInfo block
188 void ParseModuleGlobalInfo();
190 /// @brief Parse a symbol table
191 void ParseSymbolTable( Function* Func, SymbolTable *ST);
193 /// @brief Parse functions lazily.
194 void ParseFunctionLazily();
196 /// @brief Parse a function body
197 void ParseFunctionBody(Function* Func);
199 /// @brief Parse the type list portion of a compaction table
200 void ParseCompactionTypes(unsigned NumEntries);
202 /// @brief Parse a compaction table
203 void ParseCompactionTable();
205 /// @brief Parse global types
206 void ParseGlobalTypes();
208 /// @brief Parse a basic block (for LLVM 1.0 basic block blocks)
209 BasicBlock* ParseBasicBlock(unsigned BlockNo);
211 /// @brief parse an instruction list (for post LLVM 1.0 instruction lists
212 /// with blocks differentiated by terminating instructions.
213 unsigned ParseInstructionList(
214 Function* F ///< The function into which BBs will be inserted
217 /// @brief Parse a single instruction.
218 void ParseInstruction(
219 std::vector<unsigned>& Args, ///< The arguments to be filled in
220 BasicBlock* BB ///< The BB the instruction goes in
223 /// @brief Parse the whole constant pool
224 void ParseConstantPool(ValueTable& Values, TypeListTy& Types,
227 /// @brief Parse a single constant value
228 Constant* ParseConstantValue(unsigned TypeID);
230 /// @brief Parse a block of types constants
231 void ParseTypes(TypeListTy &Tab, unsigned NumEntries);
233 /// @brief Parse a single type constant
234 const Type *ParseType();
236 /// @brief Parse a string constants block
237 void ParseStringConstants(unsigned NumEntries, ValueTable &Tab);
243 char* decompressedBlock; ///< Result of decompression
244 BufPtr MemStart; ///< Start of the memory buffer
245 BufPtr MemEnd; ///< End of the memory buffer
246 BufPtr BlockStart; ///< Start of current block being parsed
247 BufPtr BlockEnd; ///< End of current block being parsed
248 BufPtr At; ///< Where we're currently parsing at
250 /// Information about the module, extracted from the bytecode revision number.
252 unsigned char RevisionNum; // The rev # itself
254 /// Flags to distinguish LLVM 1.0 & 1.1 bytecode formats (revision #0)
256 /// Revision #0 had an explicit alignment of data only for the
257 /// ModuleGlobalInfo block. This was fixed to be like all other blocks in 1.2
258 bool hasInconsistentModuleGlobalInfo;
260 /// Revision #0 also explicitly encoded zero values for primitive types like
262 bool hasExplicitPrimitiveZeros;
264 // Flags to control features specific the LLVM 1.2 and before (revision #1)
266 /// LLVM 1.2 and earlier required that getelementptr structure indices were
267 /// ubyte constants and that sequential type indices were longs.
268 bool hasRestrictedGEPTypes;
270 /// LLVM 1.2 and earlier had class Type deriving from Value and the Type
271 /// objects were located in the "Type Type" plane of various lists in read
272 /// by the bytecode reader. In LLVM 1.3 this is no longer the case. Types are
273 /// completely distinct from Values. Consequently, Types are written in fixed
274 /// locations in LLVM 1.3. This flag indicates that the older Type derived
275 /// from Value style of bytecode file is being read.
276 bool hasTypeDerivedFromValue;
278 /// LLVM 1.2 and earlier encoded block headers as two uint (8 bytes), one for
279 /// the size and one for the type. This is a bit wasteful, especially for
280 /// small files where the 8 bytes per block is a large fraction of the total
281 /// block size. In LLVM 1.3, the block type and length are encoded into a
282 /// single uint32 by restricting the number of block types (limit 31) and the
283 /// maximum size of a block (limit 2^27-1=134,217,727). Note that the module
284 /// block still uses the 8-byte format so the maximum size of a file can be
285 /// 2^32-1 bytes long.
286 bool hasLongBlockHeaders;
288 /// LLVM 1.2 and earlier wrote type slot numbers as vbr_uint32. In LLVM 1.3
289 /// this has been reduced to vbr_uint24. It shouldn't make much difference
290 /// since we haven't run into a module with > 24 million types, but for safety
291 /// the 24-bit restriction has been enforced in 1.3 to free some bits in
292 /// various places and to ensure consistency. In particular, global vars are
293 /// restricted to 24-bits.
296 /// LLVM 1.2 and earlier did not provide a target triple nor a list of
297 /// libraries on which the bytecode is dependent. LLVM 1.3 provides these
298 /// features, for use in future versions of LLVM.
299 bool hasNoDependentLibraries;
301 /// LLVM 1.3 and earlier caused blocks and other fields to start on 32-bit
302 /// aligned boundaries. This can lead to as much as 30% bytecode size overhead
303 /// in various corner cases (lots of long instructions). In LLVM 1.4,
304 /// alignment of bytecode fields was done away with completely.
307 // In version 4 and earlier, the bytecode format did not support the 'undef'
309 bool hasNoUndefValue;
311 // In version 4 and earlier, the bytecode format did not save space for flags
312 // in the global info block for functions.
313 bool hasNoFlagsForFunctions;
315 // In version 4 and earlier, there was no opcode space reserved for the
316 // unreachable instruction.
317 bool hasNoUnreachableInst;
319 // In version 5, basic blocks have a minimum index of 0 whereas all the
320 // other primitives have a minimum index of 1 (because 0 is the "null"
321 // value. In version 5, we made this consistent.
322 bool hasInconsistentBBSlotNums;
324 // In version 5, the types SByte and UByte were encoded as vbr_uint so that
325 // signed values > 63 and unsigned values >127 would be encoded as two
326 // bytes. In version 5, they are encoded directly in a single byte.
327 bool hasVBRByteTypes;
329 // In version 5, modules begin with a "Module Block" which encodes a 4-byte
330 // integer value 0x01 to identify the module block. This is unnecessary and
331 // removed in version 5.
332 bool hasUnnecessaryModuleBlockId;
334 /// CompactionTypes - If a compaction table is active in the current function,
335 /// this is the mapping that it contains. We keep track of what resolved type
336 /// it is as well as what global type entry it is.
337 std::vector<std::pair<const Type*, unsigned> > CompactionTypes;
339 /// @brief If a compaction table is active in the current function,
340 /// this is the mapping that it contains.
341 std::vector<std::vector<Value*> > CompactionValues;
343 /// @brief This vector is used to deal with forward references to types in
345 TypeListTy ModuleTypes;
347 /// @brief This vector is used to deal with forward references to types in
349 TypeListTy FunctionTypes;
351 /// When the ModuleGlobalInfo section is read, we create a Function object
352 /// for each function in the module. When the function is loaded, after the
353 /// module global info is read, this Function is populated. Until then, the
354 /// functions in this vector just hold the function signature.
355 std::vector<Function*> FunctionSignatureList;
357 /// @brief This is the table of values belonging to the current function
358 ValueTable FunctionValues;
360 /// @brief This is the table of values belonging to the module (global)
361 ValueTable ModuleValues;
363 /// @brief This keeps track of function level forward references.
364 ForwardReferenceMap ForwardReferences;
366 /// @brief The basic blocks we've parsed, while parsing a function.
367 std::vector<BasicBlock*> ParsedBasicBlocks;
369 /// This maintains a mapping between <Type, Slot #>'s and forward references
370 /// to constants. Such values may be referenced before they are defined, and
371 /// if so, the temporary object that they represent is held here. @brief
372 /// Temporary place for forward references to constants.
373 ConstantRefsType ConstantFwdRefs;
375 /// Constant values are read in after global variables. Because of this, we
376 /// must defer setting the initializers on global variables until after module
377 /// level constants have been read. In the mean time, this list keeps track
378 /// of what we must do.
379 GlobalInitsList GlobalInits;
381 // For lazy reading-in of functions, we need to save away several pieces of
382 // information about each function: its begin and end pointer in the buffer
383 // and its FunctionSlot.
384 LazyFunctionMap LazyFunctionLoadMap;
386 /// This stores the parser's handler which is used for handling tasks other
387 /// just than reading bytecode into the IR. If this is non-null, calls on
388 /// the (polymorphic) BytecodeHandler interface (see llvm/Bytecode/Handler.h)
389 /// will be made to report the logical structure of the bytecode file. What
390 /// the handler does with the events it receives is completely orthogonal to
391 /// the business of parsing the bytecode and building the IR. This is used,
392 /// for example, by the llvm-abcd tool for analysis of byte code.
393 /// @brief Handler for parsing events.
394 BytecodeHandler* Handler;
397 /// @name Implementation Details
400 /// @brief Determines if this module has a function or not.
401 bool hasFunctions() { return ! FunctionSignatureList.empty(); }
403 /// @brief Determines if the type id has an implicit null value.
404 bool hasImplicitNull(unsigned TyID );
406 /// @brief Converts a type slot number to its Type*
407 const Type *getType(unsigned ID);
409 /// @brief Converts a pre-sanitized type slot number to its Type* and
410 /// sanitizes the type id.
411 inline const Type* getSanitizedType(unsigned& ID );
413 /// @brief Read in and get a sanitized type id
414 inline const Type* readSanitizedType();
416 /// @brief Converts a Type* to its type slot number
417 unsigned getTypeSlot(const Type *Ty);
419 /// @brief Converts a normal type slot number to a compacted type slot num.
420 unsigned getCompactionTypeSlot(unsigned type);
422 /// @brief Gets the global type corresponding to the TypeId
423 const Type *getGlobalTableType(unsigned TypeId);
425 /// This is just like getTypeSlot, but when a compaction table is in use,
427 unsigned getGlobalTableTypeSlot(const Type *Ty);
429 /// @brief Get a value from its typeid and slot number
430 Value* getValue(unsigned TypeID, unsigned num, bool Create = true);
432 /// @brief Get a value from its type and slot number, ignoring compaction
434 Value *getGlobalTableValue(unsigned TyID, unsigned SlotNo);
436 /// @brief Get a basic block for current function
437 BasicBlock *getBasicBlock(unsigned ID);
439 /// @brief Get a constant value from its typeid and value slot.
440 Constant* getConstantValue(unsigned typeSlot, unsigned valSlot);
442 /// @brief Convenience function for getting a constant value when
443 /// the Type has already been resolved.
444 Constant* getConstantValue(const Type *Ty, unsigned valSlot) {
445 return getConstantValue(getTypeSlot(Ty), valSlot);
448 /// @brief Insert a newly created value
449 unsigned insertValue(Value *V, unsigned Type, ValueTable &Table);
451 /// @brief Insert the arguments of a function.
452 void insertArguments(Function* F );
454 /// @brief Resolve all references to the placeholder (if any) for the
456 void ResolveReferencesToConstant(Constant *C, unsigned Slot);
458 /// @brief Release our memory.
460 freeTable(FunctionValues);
461 freeTable(ModuleValues);
464 /// @brief Free a table, making sure to free the ValueList in the table.
465 void freeTable(ValueTable &Tab) {
466 while (!Tab.empty()) {
472 inline void error(std::string errmsg);
474 BytecodeReader(const BytecodeReader &); // DO NOT IMPLEMENT
475 void operator=(const BytecodeReader &); // DO NOT IMPLEMENT
478 /// @name Reader Primitives
482 /// @brief Is there more to parse in the current block?
483 inline bool moreInBlock();
485 /// @brief Have we read past the end of the block
486 inline void checkPastBlockEnd(const char * block_name);
488 /// @brief Align to 32 bits
489 inline void align32();
491 /// @brief Read an unsigned integer as 32-bits
492 inline unsigned read_uint();
494 /// @brief Read an unsigned integer with variable bit rate encoding
495 inline unsigned read_vbr_uint();
497 /// @brief Read an unsigned integer of no more than 24-bits with variable
498 /// bit rate encoding.
499 inline unsigned read_vbr_uint24();
501 /// @brief Read an unsigned 64-bit integer with variable bit rate encoding.
502 inline uint64_t read_vbr_uint64();
504 /// @brief Read a signed 64-bit integer with variable bit rate encoding.
505 inline int64_t read_vbr_int64();
507 /// @brief Read a string
508 inline std::string read_str();
510 /// @brief Read a float value
511 inline void read_float(float& FloatVal);
513 /// @brief Read a double value
514 inline void read_double(double& DoubleVal);
516 /// @brief Read an arbitrary data chunk of fixed length
517 inline void read_data(void *Ptr, void *End);
519 /// @brief Read a bytecode block header
520 inline void read_block(unsigned &Type, unsigned &Size);
522 /// @brief Read a type identifier and sanitize it.
523 inline bool read_typeid(unsigned &TypeId);
525 /// @brief Recalculate type ID for pre 1.3 bytecode files.
526 inline bool sanitizeTypeId(unsigned &TypeId );
530 /// @brief A function for creating a BytecodeAnalzer as a handler
531 /// for the Bytecode reader.
532 BytecodeHandler* createBytecodeAnalyzerHandler(BytecodeAnalysis& bca,
533 std::ostream* output );
536 } // End llvm namespace