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"
31 class BytecodeHandler; ///< Forward declare the handler interface
33 /// This class defines the interface for parsing a buffer of bytecode. The
34 /// parser itself takes no action except to call the various functions of
35 /// the handler interface. The parser's sole responsibility is the correct
36 /// interpretation of the bytecode buffer. The handler is responsible for
37 /// instantiating and keeping track of all values. As a convenience, the parser
38 /// is responsible for materializing types and will pass them through the
39 /// handler interface as necessary.
40 /// @see BytecodeHandler
41 /// @brief Bytecode Reader interface
42 class BytecodeReader : public ModuleProvider {
44 /// @name Constructors
47 /// @brief Default constructor. By default, no handler is used.
48 BytecodeReader(BytecodeHandler* h = 0) {
49 decompressedBlock = 0;
55 if (decompressedBlock) {
56 ::free(decompressedBlock);
57 decompressedBlock = 0;
66 /// @brief A convenience type for the buffer pointer
67 typedef const unsigned char* BufPtr;
69 /// @brief The type used for a vector of potentially abstract types
70 typedef std::vector<PATypeHolder> TypeListTy;
72 /// This type provides a vector of Value* via the User class for
73 /// storage of Values that have been constructed when reading the
74 /// bytecode. Because of forward referencing, constant replacement
75 /// can occur so we ensure that our list of Value* is updated
76 /// properly through those transitions. This ensures that the
77 /// correct Value* is in our list when it comes time to associate
78 /// constants with global variables at the end of reading the
80 /// @brief A list of values as a User of those Values.
81 class ValueList : public User {
82 std::vector<Use> Uses;
84 ValueList() : User(Type::VoidTy, Value::ArgumentVal, 0, 0) {}
86 // vector compatibility methods
87 unsigned size() const { return getNumOperands(); }
88 void push_back(Value *V) {
89 Uses.push_back(Use(V, this));
90 OperandList = &Uses[0];
93 Value *back() const { return Uses.back(); }
94 void pop_back() { Uses.pop_back(); --NumOperands; }
95 bool empty() const { return NumOperands == 0; }
96 virtual void print(std::ostream& os) const {
97 for (unsigned i = 0; i < size(); ++i) {
99 getOperand(i)->print(os);
105 /// @brief A 2 dimensional table of values
106 typedef std::vector<ValueList*> ValueTable;
108 /// This map is needed so that forward references to constants can be looked
109 /// up by Type and slot number when resolving those references.
110 /// @brief A mapping of a Type/slot pair to a Constant*.
111 typedef std::map<std::pair<unsigned,unsigned>, Constant*> ConstantRefsType;
113 /// For lazy read-in of functions, we need to save the location in the
114 /// data stream where the function is located. This structure provides that
115 /// information. Lazy read-in is used mostly by the JIT which only wants to
116 /// resolve functions as it needs them.
117 /// @brief Keeps pointers to function contents for later use.
118 struct LazyFunctionInfo {
119 const unsigned char *Buf, *EndBuf;
120 LazyFunctionInfo(const unsigned char *B = 0, const unsigned char *EB = 0)
121 : Buf(B), EndBuf(EB) {}
124 /// @brief A mapping of functions to their LazyFunctionInfo for lazy reading.
125 typedef std::map<Function*, LazyFunctionInfo> LazyFunctionMap;
127 /// @brief A list of global variables and the slot number that initializes
129 typedef std::vector<std::pair<GlobalVariable*, unsigned> > GlobalInitsList;
131 /// This type maps a typeslot/valueslot pair to the corresponding Value*.
132 /// It is used for dealing with forward references as values are read in.
133 /// @brief A map for dealing with forward references of values.
134 typedef std::map<std::pair<unsigned,unsigned>,Value*> ForwardReferenceMap;
140 /// @returns true if an error occurred
141 /// @brief Main interface to parsing a bytecode buffer.
143 volatile BufPtr Buf, ///< Beginning of the bytecode buffer
144 unsigned Length, ///< Length of the bytecode buffer
145 const std::string &ModuleID, ///< An identifier for the module constructed.
146 std::string* ErrMsg = 0 ///< Optional place for error message
149 /// @brief Parse all function bodies
150 bool ParseAllFunctionBodies(std::string* ErrMsg);
152 /// @brief Parse the next function of specific type
153 bool ParseFunction(Function* Func, std::string* ErrMsg) ;
155 /// This method is abstract in the parent ModuleProvider class. Its
156 /// implementation is identical to the ParseFunction method.
157 /// @see ParseFunction
158 /// @brief Make a specific function materialize.
159 virtual bool materializeFunction(Function *F, std::string *ErrMsg = 0) {
160 LazyFunctionMap::iterator Fi = LazyFunctionLoadMap.find(F);
161 if (Fi == LazyFunctionLoadMap.end())
163 if (ParseFunction(F,ErrMsg))
168 /// This method is abstract in the parent ModuleProvider class. Its
169 /// implementation is identical to ParseAllFunctionBodies.
170 /// @see ParseAllFunctionBodies
171 /// @brief Make the whole module materialize
172 virtual Module* materializeModule(std::string *ErrMsg = 0) {
173 if (ParseAllFunctionBodies(ErrMsg))
178 /// This method is provided by the parent ModuleProvde class and overriden
179 /// here. It simply releases the module from its provided and frees up our
181 /// @brief Release our hold on the generated module
182 Module* releaseModule(std::string *ErrInfo = 0) {
183 // Since we're losing control of this Module, we must hand it back complete
184 Module *M = ModuleProvider::releaseModule();
190 /// @name Parsing Units For Subclasses
193 /// @brief Parse whole module scope
196 /// @brief Parse the version information block
197 void ParseVersionInfo();
199 /// @brief Parse the ModuleGlobalInfo block
200 void ParseModuleGlobalInfo();
202 /// @brief Parse a symbol table
203 void ParseSymbolTable( Function* Func, SymbolTable *ST);
205 /// @brief Parse functions lazily.
206 void ParseFunctionLazily();
208 /// @brief Parse a function body
209 void ParseFunctionBody(Function* Func);
211 /// @brief Parse the type list portion of a compaction table
212 void ParseCompactionTypes(unsigned NumEntries);
214 /// @brief Parse a compaction table
215 void ParseCompactionTable();
217 /// @brief Parse global types
218 void ParseGlobalTypes();
220 /// @brief Parse a basic block (for LLVM 1.0 basic block blocks)
221 BasicBlock* ParseBasicBlock(unsigned BlockNo);
223 /// @brief parse an instruction list (for post LLVM 1.0 instruction lists
224 /// with blocks differentiated by terminating instructions.
225 unsigned ParseInstructionList(
226 Function* F ///< The function into which BBs will be inserted
229 /// Convert previous opcode values into the current value and/or construct
230 /// the instruction. This function handles all *abnormal* cases for
231 /// instruction generation based on obsolete opcode values. The normal cases
232 /// are handled by the ParseInstruction function.
233 Instruction* upgradeInstrOpcodes(
234 unsigned &opcode, ///< The old opcode, possibly updated by this function
235 std::vector<unsigned> &Oprnds, ///< The operands to the instruction
236 unsigned &iType, ///< The type code from the bytecode file
237 const Type* InstTy, ///< The type of the instruction
238 BasicBlock* BB ///< The basic block to insert into, if we need to
241 /// @brief Convert previous opcode values for ConstantExpr into the current
243 unsigned upgradeCEOpcodes(
244 unsigned Opcode, ///< Opcode read from bytecode
245 const std::vector<Constant*> &ArgVec ///< Arguments of instruction
248 /// @brief Parse a single instruction.
249 void ParseInstruction(
250 std::vector<unsigned>& Args, ///< The arguments to be filled in
251 BasicBlock* BB ///< The BB the instruction goes in
254 /// @brief Parse the whole constant pool
255 void ParseConstantPool(ValueTable& Values, TypeListTy& Types,
258 /// @brief Parse a single constant pool value
259 Value *ParseConstantPoolValue(unsigned TypeID);
261 /// @brief Parse a block of types constants
262 void ParseTypes(TypeListTy &Tab, unsigned NumEntries);
264 /// @brief Parse a single type constant
265 const Type *ParseType();
267 /// @brief Parse a string constants block
268 void ParseStringConstants(unsigned NumEntries, ValueTable &Tab);
270 /// @brief Release our memory.
272 freeTable(FunctionValues);
273 freeTable(ModuleValues);
280 std::string ErrorMsg; ///< A place to hold an error message through longjmp
281 jmp_buf context; ///< Where to return to if an error occurs.
282 char* decompressedBlock; ///< Result of decompression
283 BufPtr MemStart; ///< Start of the memory buffer
284 BufPtr MemEnd; ///< End of the memory buffer
285 BufPtr BlockStart; ///< Start of current block being parsed
286 BufPtr BlockEnd; ///< End of current block being parsed
287 BufPtr At; ///< Where we're currently parsing at
289 /// Information about the module, extracted from the bytecode revision number.
291 unsigned char RevisionNum; // The rev # itself
293 /// Flags to distinguish LLVM 1.0 & 1.1 bytecode formats (revision #0)
295 /// Revision #0 had an explicit alignment of data only for the
296 /// ModuleGlobalInfo block. This was fixed to be like all other blocks in 1.2
297 bool hasInconsistentModuleGlobalInfo;
299 /// Revision #0 also explicitly encoded zero values for primitive types like
301 bool hasExplicitPrimitiveZeros;
303 // Flags to control features specific the LLVM 1.2 and before (revision #1)
305 /// LLVM 1.2 and earlier required that getelementptr structure indices were
306 /// ubyte constants and that sequential type indices were longs.
307 bool hasRestrictedGEPTypes;
309 /// LLVM 1.2 and earlier had class Type deriving from Value and the Type
310 /// objects were located in the "Type Type" plane of various lists in read
311 /// by the bytecode reader. In LLVM 1.3 this is no longer the case. Types are
312 /// completely distinct from Values. Consequently, Types are written in fixed
313 /// locations in LLVM 1.3. This flag indicates that the older Type derived
314 /// from Value style of bytecode file is being read.
315 bool hasTypeDerivedFromValue;
317 /// LLVM 1.2 and earlier encoded block headers as two uint (8 bytes), one for
318 /// the size and one for the type. This is a bit wasteful, especially for
319 /// small files where the 8 bytes per block is a large fraction of the total
320 /// block size. In LLVM 1.3, the block type and length are encoded into a
321 /// single uint32 by restricting the number of block types (limit 31) and the
322 /// maximum size of a block (limit 2^27-1=134,217,727). Note that the module
323 /// block still uses the 8-byte format so the maximum size of a file can be
324 /// 2^32-1 bytes long.
325 bool hasLongBlockHeaders;
327 /// LLVM 1.2 and earlier wrote type slot numbers as vbr_uint32. In LLVM 1.3
328 /// this has been reduced to vbr_uint24. It shouldn't make much difference
329 /// since we haven't run into a module with > 24 million types, but for safety
330 /// the 24-bit restriction has been enforced in 1.3 to free some bits in
331 /// various places and to ensure consistency. In particular, global vars are
332 /// restricted to 24-bits.
335 /// LLVM 1.2 and earlier did not provide a target triple nor a list of
336 /// libraries on which the bytecode is dependent. LLVM 1.3 provides these
337 /// features, for use in future versions of LLVM.
338 bool hasNoDependentLibraries;
340 /// LLVM 1.3 and earlier caused blocks and other fields to start on 32-bit
341 /// aligned boundaries. This can lead to as much as 30% bytecode size overhead
342 /// in various corner cases (lots of long instructions). In LLVM 1.4,
343 /// alignment of bytecode fields was done away with completely.
346 // In version 4 and earlier, the bytecode format did not support the 'undef'
348 bool hasNoUndefValue;
350 // In version 4 and earlier, the bytecode format did not save space for flags
351 // in the global info block for functions.
352 bool hasNoFlagsForFunctions;
354 // In version 4 and earlier, there was no opcode space reserved for the
355 // unreachable instruction.
356 bool hasNoUnreachableInst;
358 // In version 6, the Div and Rem instructions were converted to be the
359 // signed instructions UDiv, SDiv, URem and SRem. This flag will be true if
360 // the Div and Rem instructions are signless (ver 5 and prior).
361 bool hasSignlessDivRem;
363 // In version 7, the Shr, Cast and Setcc instructions changed to their
364 // signed counterparts. This flag will be true if these instructions are
365 // signless (version 6 and prior).
366 bool hasSignlessShrCastSetcc;
368 /// In release 1.7 we changed intrinsic functions to not be overloaded. There
369 /// is no bytecode change for this, but to optimize the auto-upgrade of calls
370 /// to intrinsic functions, we save a mapping of old function definitions to
371 /// the new ones so call instructions can be upgraded efficiently.
372 std::map<Function*,Function*> upgradedFunctions;
374 /// CompactionTypes - If a compaction table is active in the current function,
375 /// this is the mapping that it contains. We keep track of what resolved type
376 /// it is as well as what global type entry it is.
377 std::vector<std::pair<const Type*, unsigned> > CompactionTypes;
379 /// @brief If a compaction table is active in the current function,
380 /// this is the mapping that it contains.
381 std::vector<std::vector<Value*> > CompactionValues;
383 /// @brief This vector is used to deal with forward references to types in
385 TypeListTy ModuleTypes;
387 /// @brief This is an inverse mapping of ModuleTypes from the type to an
388 /// index. Because refining types causes the index of this map to be
389 /// invalidated, any time we refine a type, we clear this cache and recompute
390 /// it next time we need it. These entries are ordered by the pointer value.
391 std::vector<std::pair<const Type*, unsigned> > ModuleTypeIDCache;
393 /// @brief This vector is used to deal with forward references to types in
395 TypeListTy FunctionTypes;
397 /// When the ModuleGlobalInfo section is read, we create a Function object
398 /// for each function in the module. When the function is loaded, after the
399 /// module global info is read, this Function is populated. Until then, the
400 /// functions in this vector just hold the function signature.
401 std::vector<Function*> FunctionSignatureList;
403 /// @brief This is the table of values belonging to the current function
404 ValueTable FunctionValues;
406 /// @brief This is the table of values belonging to the module (global)
407 ValueTable ModuleValues;
409 /// @brief This keeps track of function level forward references.
410 ForwardReferenceMap ForwardReferences;
412 /// @brief The basic blocks we've parsed, while parsing a function.
413 std::vector<BasicBlock*> ParsedBasicBlocks;
415 /// This maintains a mapping between <Type, Slot #>'s and forward references
416 /// to constants. Such values may be referenced before they are defined, and
417 /// if so, the temporary object that they represent is held here. @brief
418 /// Temporary place for forward references to constants.
419 ConstantRefsType ConstantFwdRefs;
421 /// Constant values are read in after global variables. Because of this, we
422 /// must defer setting the initializers on global variables until after module
423 /// level constants have been read. In the mean time, this list keeps track
424 /// of what we must do.
425 GlobalInitsList GlobalInits;
427 // For lazy reading-in of functions, we need to save away several pieces of
428 // information about each function: its begin and end pointer in the buffer
429 // and its FunctionSlot.
430 LazyFunctionMap LazyFunctionLoadMap;
432 /// This stores the parser's handler which is used for handling tasks other
433 /// just than reading bytecode into the IR. If this is non-null, calls on
434 /// the (polymorphic) BytecodeHandler interface (see llvm/Bytecode/Handler.h)
435 /// will be made to report the logical structure of the bytecode file. What
436 /// the handler does with the events it receives is completely orthogonal to
437 /// the business of parsing the bytecode and building the IR. This is used,
438 /// for example, by the llvm-abcd tool for analysis of byte code.
439 /// @brief Handler for parsing events.
440 BytecodeHandler* Handler;
444 /// @name Implementation Details
447 /// @brief Determines if this module has a function or not.
448 bool hasFunctions() { return ! FunctionSignatureList.empty(); }
450 /// @brief Determines if the type id has an implicit null value.
451 bool hasImplicitNull(unsigned TyID );
453 /// @brief Converts a type slot number to its Type*
454 const Type *getType(unsigned ID);
456 /// @brief Converts a pre-sanitized type slot number to its Type* and
457 /// sanitizes the type id.
458 inline const Type* getSanitizedType(unsigned& ID );
460 /// @brief Read in and get a sanitized type id
461 inline const Type* readSanitizedType();
463 /// @brief Converts a Type* to its type slot number
464 unsigned getTypeSlot(const Type *Ty);
466 /// @brief Converts a normal type slot number to a compacted type slot num.
467 unsigned getCompactionTypeSlot(unsigned type);
469 /// @brief Gets the global type corresponding to the TypeId
470 const Type *getGlobalTableType(unsigned TypeId);
472 /// This is just like getTypeSlot, but when a compaction table is in use,
474 unsigned getGlobalTableTypeSlot(const Type *Ty);
476 /// @brief Get a value from its typeid and slot number
477 Value* getValue(unsigned TypeID, unsigned num, bool Create = true);
479 /// @brief Get a value from its type and slot number, ignoring compaction
481 Value *getGlobalTableValue(unsigned TyID, unsigned SlotNo);
483 /// @brief Get a basic block for current function
484 BasicBlock *getBasicBlock(unsigned ID);
486 /// @brief Get a constant value from its typeid and value slot.
487 Constant* getConstantValue(unsigned typeSlot, unsigned valSlot);
489 /// @brief Convenience function for getting a constant value when
490 /// the Type has already been resolved.
491 Constant* getConstantValue(const Type *Ty, unsigned valSlot) {
492 return getConstantValue(getTypeSlot(Ty), valSlot);
495 /// @brief Insert a newly created value
496 unsigned insertValue(Value *V, unsigned Type, ValueTable &Table);
498 /// @brief Insert the arguments of a function.
499 void insertArguments(Function* F );
501 /// @brief Resolve all references to the placeholder (if any) for the
503 void ResolveReferencesToConstant(Constant *C, unsigned Typ, unsigned Slot);
505 /// @brief Free a table, making sure to free the ValueList in the table.
506 void freeTable(ValueTable &Tab) {
507 while (!Tab.empty()) {
513 inline void error(const std::string& errmsg);
515 BytecodeReader(const BytecodeReader &); // DO NOT IMPLEMENT
516 void operator=(const BytecodeReader &); // DO NOT IMPLEMENT
519 /// @name Reader Primitives
523 /// @brief Is there more to parse in the current block?
524 inline bool moreInBlock();
526 /// @brief Have we read past the end of the block
527 inline void checkPastBlockEnd(const char * block_name);
529 /// @brief Align to 32 bits
530 inline void align32();
532 /// @brief Read an unsigned integer as 32-bits
533 inline unsigned read_uint();
535 /// @brief Read an unsigned integer with variable bit rate encoding
536 inline unsigned read_vbr_uint();
538 /// @brief Read an unsigned integer of no more than 24-bits with variable
539 /// bit rate encoding.
540 inline unsigned read_vbr_uint24();
542 /// @brief Read an unsigned 64-bit integer with variable bit rate encoding.
543 inline uint64_t read_vbr_uint64();
545 /// @brief Read a signed 64-bit integer with variable bit rate encoding.
546 inline int64_t read_vbr_int64();
548 /// @brief Read a string
549 inline std::string read_str();
551 /// @brief Read a float value
552 inline void read_float(float& FloatVal);
554 /// @brief Read a double value
555 inline void read_double(double& DoubleVal);
557 /// @brief Read an arbitrary data chunk of fixed length
558 inline void read_data(void *Ptr, void *End);
560 /// @brief Read a bytecode block header
561 inline void read_block(unsigned &Type, unsigned &Size);
563 /// @brief Read a type identifier and sanitize it.
564 inline bool read_typeid(unsigned &TypeId);
566 /// @brief Recalculate type ID for pre 1.3 bytecode files.
567 inline bool sanitizeTypeId(unsigned &TypeId );
571 /// @brief A function for creating a BytecodeAnalzer as a handler
572 /// for the Bytecode reader.
573 BytecodeHandler* createBytecodeAnalyzerHandler(BytecodeAnalysis& bca,
574 std::ostream* output );
577 } // End llvm namespace