LLVM API Documentation

lib/Bytecode/Reader/Reader.h

Go to the documentation of this file.
00001 //===-- Reader.h - Interface To Bytecode Reading ----------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by Reid Spencer and is distributed under the
00006 // University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 //  This header file defines the interface to the Bytecode Reader which is
00011 //  responsible for correctly interpreting bytecode files (backwards compatible)
00012 //  and materializing a module from the bytecode read.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #ifndef BYTECODE_PARSER_H
00017 #define BYTECODE_PARSER_H
00018 
00019 #include "llvm/Constants.h"
00020 #include "llvm/DerivedTypes.h"
00021 #include "llvm/GlobalValue.h"
00022 #include "llvm/Function.h"
00023 #include "llvm/ModuleProvider.h"
00024 #include "llvm/Bytecode/Analyzer.h"
00025 #include <utility>
00026 #include <map>
00027 
00028 namespace llvm {
00029 
00030 class BytecodeHandler; ///< Forward declare the handler interface
00031 
00032 /// This class defines the interface for parsing a buffer of bytecode. The
00033 /// parser itself takes no action except to call the various functions of
00034 /// the handler interface. The parser's sole responsibility is the correct
00035 /// interpretation of the bytecode buffer. The handler is responsible for
00036 /// instantiating and keeping track of all values. As a convenience, the parser
00037 /// is responsible for materializing types and will pass them through the
00038 /// handler interface as necessary.
00039 /// @see BytecodeHandler
00040 /// @brief Bytecode Reader interface
00041 class BytecodeReader : public ModuleProvider {
00042 
00043 /// @name Constructors
00044 /// @{
00045 public:
00046   /// @brief Default constructor. By default, no handler is used.
00047   BytecodeReader(BytecodeHandler* h = 0) {
00048     decompressedBlock = 0;
00049     Handler = h;
00050   }
00051 
00052   ~BytecodeReader() {
00053     freeState();
00054     if (decompressedBlock) {
00055       ::free(decompressedBlock);
00056       decompressedBlock = 0;
00057     }
00058   }
00059 
00060 /// @}
00061 /// @name Types
00062 /// @{
00063 public:
00064 
00065   /// @brief A convenience type for the buffer pointer
00066   typedef const unsigned char* BufPtr;
00067 
00068   /// @brief The type used for a vector of potentially abstract types
00069   typedef std::vector<PATypeHolder> TypeListTy;
00070 
00071   /// This type provides a vector of Value* via the User class for
00072   /// storage of Values that have been constructed when reading the
00073   /// bytecode. Because of forward referencing, constant replacement
00074   /// can occur so we ensure that our list of Value* is updated
00075   /// properly through those transitions. This ensures that the
00076   /// correct Value* is in our list when it comes time to associate
00077   /// constants with global variables at the end of reading the
00078   /// globals section.
00079   /// @brief A list of values as a User of those Values.
00080   class ValueList : public User {
00081     std::vector<Use> Uses;
00082   public:
00083     ValueList() : User(Type::VoidTy, Value::ArgumentVal, 0, 0) {}
00084 
00085     // vector compatibility methods
00086     unsigned size() const { return getNumOperands(); }
00087     void push_back(Value *V) {
00088       Uses.push_back(Use(V, this));
00089       OperandList = &Uses[0];
00090       ++NumOperands;
00091     }
00092     Value *back() const { return Uses.back(); }
00093     void pop_back() { Uses.pop_back(); --NumOperands; }
00094     bool empty() const { return NumOperands == 0; }
00095     virtual void print(std::ostream& os) const {
00096       for (unsigned i = 0; i < size(); ++i) {
00097         os << i << " ";
00098         getOperand(i)->print(os);
00099         os << "\n";
00100       }
00101     }
00102   };
00103 
00104   /// @brief A 2 dimensional table of values
00105   typedef std::vector<ValueList*> ValueTable;
00106 
00107   /// This map is needed so that forward references to constants can be looked
00108   /// up by Type and slot number when resolving those references.
00109   /// @brief A mapping of a Type/slot pair to a Constant*.
00110   typedef std::map<std::pair<unsigned,unsigned>, Constant*> ConstantRefsType;
00111 
00112   /// For lazy read-in of functions, we need to save the location in the
00113   /// data stream where the function is located. This structure provides that
00114   /// information. Lazy read-in is used mostly by the JIT which only wants to
00115   /// resolve functions as it needs them.
00116   /// @brief Keeps pointers to function contents for later use.
00117   struct LazyFunctionInfo {
00118     const unsigned char *Buf, *EndBuf;
00119     LazyFunctionInfo(const unsigned char *B = 0, const unsigned char *EB = 0)
00120       : Buf(B), EndBuf(EB) {}
00121   };
00122 
00123   /// @brief A mapping of functions to their LazyFunctionInfo for lazy reading.
00124   typedef std::map<Function*, LazyFunctionInfo> LazyFunctionMap;
00125 
00126   /// @brief A list of global variables and the slot number that initializes
00127   /// them.
00128   typedef std::vector<std::pair<GlobalVariable*, unsigned> > GlobalInitsList;
00129 
00130   /// This type maps a typeslot/valueslot pair to the corresponding Value*.
00131   /// It is used for dealing with forward references as values are read in.
00132   /// @brief A map for dealing with forward references of values.
00133   typedef std::map<std::pair<unsigned,unsigned>,Value*> ForwardReferenceMap;
00134 
00135 /// @}
00136 /// @name Methods
00137 /// @{
00138 public:
00139   /// @brief Main interface to parsing a bytecode buffer.
00140   void ParseBytecode(
00141      const unsigned char *Buf,    ///< Beginning of the bytecode buffer
00142      unsigned Length,             ///< Length of the bytecode buffer
00143      const std::string &ModuleID  ///< An identifier for the module constructed.
00144   );
00145 
00146   /// @brief Parse all function bodies
00147   void ParseAllFunctionBodies();
00148 
00149   /// @brief Parse the next function of specific type
00150   void ParseFunction(Function* Func) ;
00151 
00152   /// This method is abstract in the parent ModuleProvider class. Its
00153   /// implementation is identical to the ParseFunction method.
00154   /// @see ParseFunction
00155   /// @brief Make a specific function materialize.
00156   virtual bool materializeFunction(Function *F, std::string *ErrInfo = 0) {
00157     LazyFunctionMap::iterator Fi = LazyFunctionLoadMap.find(F);
00158     if (Fi == LazyFunctionLoadMap.end()) return false;
00159     try {
00160       ParseFunction(F);
00161     } catch (std::string &ErrStr) {
00162       if (ErrInfo) *ErrInfo = ErrStr;
00163       return true;
00164     } catch (...) {
00165       return true;
00166     }
00167     return false;
00168   }
00169 
00170   /// This method is abstract in the parent ModuleProvider class. Its
00171   /// implementation is identical to ParseAllFunctionBodies.
00172   /// @see ParseAllFunctionBodies
00173   /// @brief Make the whole module materialize
00174   virtual Module* materializeModule(std::string *ErrInfo = 0) {
00175     try {
00176       ParseAllFunctionBodies();
00177     } catch (std::string &ErrStr) {
00178       if (ErrInfo) *ErrInfo = ErrStr;
00179       return 0;
00180     } catch (...) {
00181       return 0;
00182     }
00183     return TheModule;
00184   }
00185 
00186   /// This method is provided by the parent ModuleProvde class and overriden
00187   /// here. It simply releases the module from its provided and frees up our
00188   /// state.
00189   /// @brief Release our hold on the generated module
00190   Module* releaseModule(std::string *ErrInfo = 0) {
00191     // Since we're losing control of this Module, we must hand it back complete
00192     Module *M = ModuleProvider::releaseModule();
00193     freeState();
00194     return M;
00195   }
00196 
00197 /// @}
00198 /// @name Parsing Units For Subclasses
00199 /// @{
00200 protected:
00201   /// @brief Parse whole module scope
00202   void ParseModule();
00203 
00204   /// @brief Parse the version information block
00205   void ParseVersionInfo();
00206 
00207   /// @brief Parse the ModuleGlobalInfo block
00208   void ParseModuleGlobalInfo();
00209 
00210   /// @brief Parse a symbol table
00211   void ParseSymbolTable( Function* Func, SymbolTable *ST);
00212 
00213   /// @brief Parse functions lazily.
00214   void ParseFunctionLazily();
00215 
00216   ///  @brief Parse a function body
00217   void ParseFunctionBody(Function* Func);
00218 
00219   /// @brief Parse the type list portion of a compaction table
00220   void ParseCompactionTypes(unsigned NumEntries);
00221 
00222   /// @brief Parse a compaction table
00223   void ParseCompactionTable();
00224 
00225   /// @brief Parse global types
00226   void ParseGlobalTypes();
00227 
00228   /// @brief Parse a basic block (for LLVM 1.0 basic block blocks)
00229   BasicBlock* ParseBasicBlock(unsigned BlockNo);
00230 
00231   /// @brief parse an instruction list (for post LLVM 1.0 instruction lists
00232   /// with blocks differentiated by terminating instructions.
00233   unsigned ParseInstructionList(
00234     Function* F   ///< The function into which BBs will be inserted
00235   );
00236 
00237   /// @brief Parse a single instruction.
00238   void ParseInstruction(
00239     std::vector<unsigned>& Args,   ///< The arguments to be filled in
00240     BasicBlock* BB             ///< The BB the instruction goes in
00241   );
00242 
00243   /// @brief Parse the whole constant pool
00244   void ParseConstantPool(ValueTable& Values, TypeListTy& Types,
00245                          bool isFunction);
00246 
00247   /// @brief Parse a single constant pool value
00248   Value *ParseConstantPoolValue(unsigned TypeID);
00249 
00250   /// @brief Parse a block of types constants
00251   void ParseTypes(TypeListTy &Tab, unsigned NumEntries);
00252 
00253   /// @brief Parse a single type constant
00254   const Type *ParseType();
00255 
00256   /// @brief Parse a string constants block
00257   void ParseStringConstants(unsigned NumEntries, ValueTable &Tab);
00258 
00259 /// @}
00260 /// @name Data
00261 /// @{
00262 private:
00263   char*  decompressedBlock; ///< Result of decompression
00264   BufPtr MemStart;     ///< Start of the memory buffer
00265   BufPtr MemEnd;       ///< End of the memory buffer
00266   BufPtr BlockStart;   ///< Start of current block being parsed
00267   BufPtr BlockEnd;     ///< End of current block being parsed
00268   BufPtr At;           ///< Where we're currently parsing at
00269 
00270   /// Information about the module, extracted from the bytecode revision number.
00271   ///
00272   unsigned char RevisionNum;        // The rev # itself
00273 
00274   /// Flags to distinguish LLVM 1.0 & 1.1 bytecode formats (revision #0)
00275 
00276   /// Revision #0 had an explicit alignment of data only for the
00277   /// ModuleGlobalInfo block.  This was fixed to be like all other blocks in 1.2
00278   bool hasInconsistentModuleGlobalInfo;
00279 
00280   /// Revision #0 also explicitly encoded zero values for primitive types like
00281   /// int/sbyte/etc.
00282   bool hasExplicitPrimitiveZeros;
00283 
00284   // Flags to control features specific the LLVM 1.2 and before (revision #1)
00285 
00286   /// LLVM 1.2 and earlier required that getelementptr structure indices were
00287   /// ubyte constants and that sequential type indices were longs.
00288   bool hasRestrictedGEPTypes;
00289 
00290   /// LLVM 1.2 and earlier had class Type deriving from Value and the Type
00291   /// objects were located in the "Type Type" plane of various lists in read
00292   /// by the bytecode reader. In LLVM 1.3 this is no longer the case. Types are
00293   /// completely distinct from Values. Consequently, Types are written in fixed
00294   /// locations in LLVM 1.3. This flag indicates that the older Type derived
00295   /// from Value style of bytecode file is being read.
00296   bool hasTypeDerivedFromValue;
00297 
00298   /// LLVM 1.2 and earlier encoded block headers as two uint (8 bytes), one for
00299   /// the size and one for the type. This is a bit wasteful, especially for
00300   /// small files where the 8 bytes per block is a large fraction of the total
00301   /// block size. In LLVM 1.3, the block type and length are encoded into a
00302   /// single uint32 by restricting the number of block types (limit 31) and the
00303   /// maximum size of a block (limit 2^27-1=134,217,727). Note that the module
00304   /// block still uses the 8-byte format so the maximum size of a file can be
00305   /// 2^32-1 bytes long.
00306   bool hasLongBlockHeaders;
00307 
00308   /// LLVM 1.2 and earlier wrote type slot numbers as vbr_uint32. In LLVM 1.3
00309   /// this has been reduced to vbr_uint24. It shouldn't make much difference
00310   /// since we haven't run into a module with > 24 million types, but for safety
00311   /// the 24-bit restriction has been enforced in 1.3 to free some bits in
00312   /// various places and to ensure consistency. In particular, global vars are
00313   /// restricted to 24-bits.
00314   bool has32BitTypes;
00315 
00316   /// LLVM 1.2 and earlier did not provide a target triple nor a list of
00317   /// libraries on which the bytecode is dependent. LLVM 1.3 provides these
00318   /// features, for use in future versions of LLVM.
00319   bool hasNoDependentLibraries;
00320 
00321   /// LLVM 1.3 and earlier caused blocks and other fields to start on 32-bit
00322   /// aligned boundaries. This can lead to as much as 30% bytecode size overhead
00323   /// in various corner cases (lots of long instructions). In LLVM 1.4,
00324   /// alignment of bytecode fields was done away with completely.
00325   bool hasAlignment;
00326 
00327   // In version 4 and earlier, the bytecode format did not support the 'undef'
00328   // constant.
00329   bool hasNoUndefValue;
00330 
00331   // In version 4 and earlier, the bytecode format did not save space for flags
00332   // in the global info block for functions.
00333   bool hasNoFlagsForFunctions;
00334 
00335   // In version 4 and earlier, there was no opcode space reserved for the
00336   // unreachable instruction.
00337   bool hasNoUnreachableInst;
00338 
00339   /// In release 1.7 we changed intrinsic functions to not be overloaded. There
00340   /// is no bytecode change for this, but to optimize the auto-upgrade of calls
00341   /// to intrinsic functions, we save a mapping of old function definitions to
00342   /// the new ones so call instructions can be upgraded efficiently.
00343   std::map<Function*,Function*> upgradedFunctions;
00344 
00345   /// CompactionTypes - If a compaction table is active in the current function,
00346   /// this is the mapping that it contains.  We keep track of what resolved type
00347   /// it is as well as what global type entry it is.
00348   std::vector<std::pair<const Type*, unsigned> > CompactionTypes;
00349 
00350   /// @brief If a compaction table is active in the current function,
00351   /// this is the mapping that it contains.
00352   std::vector<std::vector<Value*> > CompactionValues;
00353 
00354   /// @brief This vector is used to deal with forward references to types in
00355   /// a module.
00356   TypeListTy ModuleTypes;
00357   
00358   /// @brief This is an inverse mapping of ModuleTypes from the type to an
00359   /// index.  Because refining types causes the index of this map to be
00360   /// invalidated, any time we refine a type, we clear this cache and recompute
00361   /// it next time we need it.  These entries are ordered by the pointer value.
00362   std::vector<std::pair<const Type*, unsigned> > ModuleTypeIDCache;
00363 
00364   /// @brief This vector is used to deal with forward references to types in
00365   /// a function.
00366   TypeListTy FunctionTypes;
00367 
00368   /// When the ModuleGlobalInfo section is read, we create a Function object
00369   /// for each function in the module. When the function is loaded, after the
00370   /// module global info is read, this Function is populated. Until then, the
00371   /// functions in this vector just hold the function signature.
00372   std::vector<Function*> FunctionSignatureList;
00373 
00374   /// @brief This is the table of values belonging to the current function
00375   ValueTable FunctionValues;
00376 
00377   /// @brief This is the table of values belonging to the module (global)
00378   ValueTable ModuleValues;
00379 
00380   /// @brief This keeps track of function level forward references.
00381   ForwardReferenceMap ForwardReferences;
00382 
00383   /// @brief The basic blocks we've parsed, while parsing a function.
00384   std::vector<BasicBlock*> ParsedBasicBlocks;
00385 
00386   /// This maintains a mapping between <Type, Slot #>'s and forward references
00387   /// to constants.  Such values may be referenced before they are defined, and
00388   /// if so, the temporary object that they represent is held here.  @brief
00389   /// Temporary place for forward references to constants.
00390   ConstantRefsType ConstantFwdRefs;
00391 
00392   /// Constant values are read in after global variables.  Because of this, we
00393   /// must defer setting the initializers on global variables until after module
00394   /// level constants have been read.  In the mean time, this list keeps track
00395   /// of what we must do.
00396   GlobalInitsList GlobalInits;
00397 
00398   // For lazy reading-in of functions, we need to save away several pieces of
00399   // information about each function: its begin and end pointer in the buffer
00400   // and its FunctionSlot.
00401   LazyFunctionMap LazyFunctionLoadMap;
00402 
00403   /// This stores the parser's handler which is used for handling tasks other
00404   /// just than reading bytecode into the IR. If this is non-null, calls on
00405   /// the (polymorphic) BytecodeHandler interface (see llvm/Bytecode/Handler.h)
00406   /// will be made to report the logical structure of the bytecode file. What
00407   /// the handler does with the events it receives is completely orthogonal to
00408   /// the business of parsing the bytecode and building the IR.  This is used,
00409   /// for example, by the llvm-abcd tool for analysis of byte code.
00410   /// @brief Handler for parsing events.
00411   BytecodeHandler* Handler;
00412 
00413 
00414 /// @}
00415 /// @name Implementation Details
00416 /// @{
00417 private:
00418   /// @brief Determines if this module has a function or not.
00419   bool hasFunctions() { return ! FunctionSignatureList.empty(); }
00420 
00421   /// @brief Determines if the type id has an implicit null value.
00422   bool hasImplicitNull(unsigned TyID );
00423 
00424   /// @brief Converts a type slot number to its Type*
00425   const Type *getType(unsigned ID);
00426 
00427   /// @brief Converts a pre-sanitized type slot number to its Type* and
00428   /// sanitizes the type id.
00429   inline const Type* getSanitizedType(unsigned& ID );
00430 
00431   /// @brief Read in and get a sanitized type id
00432   inline const Type* readSanitizedType();
00433 
00434   /// @brief Converts a Type* to its type slot number
00435   unsigned getTypeSlot(const Type *Ty);
00436 
00437   /// @brief Converts a normal type slot number to a compacted type slot num.
00438   unsigned getCompactionTypeSlot(unsigned type);
00439 
00440   /// @brief Gets the global type corresponding to the TypeId
00441   const Type *getGlobalTableType(unsigned TypeId);
00442 
00443   /// This is just like getTypeSlot, but when a compaction table is in use,
00444   /// it is ignored.
00445   unsigned getGlobalTableTypeSlot(const Type *Ty);
00446 
00447   /// @brief Get a value from its typeid and slot number
00448   Value* getValue(unsigned TypeID, unsigned num, bool Create = true);
00449 
00450   /// @brief Get a value from its type and slot number, ignoring compaction
00451   /// tables.
00452   Value *getGlobalTableValue(unsigned TyID, unsigned SlotNo);
00453 
00454   /// @brief Get a basic block for current function
00455   BasicBlock *getBasicBlock(unsigned ID);
00456 
00457   /// @brief Get a constant value from its typeid and value slot.
00458   Constant* getConstantValue(unsigned typeSlot, unsigned valSlot);
00459 
00460   /// @brief Convenience function for getting a constant value when
00461   /// the Type has already been resolved.
00462   Constant* getConstantValue(const Type *Ty, unsigned valSlot) {
00463     return getConstantValue(getTypeSlot(Ty), valSlot);
00464   }
00465 
00466   /// @brief Insert a newly created value
00467   unsigned insertValue(Value *V, unsigned Type, ValueTable &Table);
00468 
00469   /// @brief Insert the arguments of a function.
00470   void insertArguments(Function* F );
00471 
00472   /// @brief Resolve all references to the placeholder (if any) for the
00473   /// given constant.
00474   void ResolveReferencesToConstant(Constant *C, unsigned Typ, unsigned Slot);
00475 
00476   /// @brief Release our memory.
00477   void freeState() {
00478     freeTable(FunctionValues);
00479     freeTable(ModuleValues);
00480   }
00481 
00482   /// @brief Free a table, making sure to free the ValueList in the table.
00483   void freeTable(ValueTable &Tab) {
00484     while (!Tab.empty()) {
00485       delete Tab.back();
00486       Tab.pop_back();
00487     }
00488   }
00489 
00490   inline void error(std::string errmsg);
00491 
00492   BytecodeReader(const BytecodeReader &);  // DO NOT IMPLEMENT
00493   void operator=(const BytecodeReader &);  // DO NOT IMPLEMENT
00494 
00495 /// @}
00496 /// @name Reader Primitives
00497 /// @{
00498 private:
00499 
00500   /// @brief Is there more to parse in the current block?
00501   inline bool moreInBlock();
00502 
00503   /// @brief Have we read past the end of the block
00504   inline void checkPastBlockEnd(const char * block_name);
00505 
00506   /// @brief Align to 32 bits
00507   inline void align32();
00508 
00509   /// @brief Read an unsigned integer as 32-bits
00510   inline unsigned read_uint();
00511 
00512   /// @brief Read an unsigned integer with variable bit rate encoding
00513   inline unsigned read_vbr_uint();
00514 
00515   /// @brief Read an unsigned integer of no more than 24-bits with variable
00516   /// bit rate encoding.
00517   inline unsigned read_vbr_uint24();
00518 
00519   /// @brief Read an unsigned 64-bit integer with variable bit rate encoding.
00520   inline uint64_t read_vbr_uint64();
00521 
00522   /// @brief Read a signed 64-bit integer with variable bit rate encoding.
00523   inline int64_t read_vbr_int64();
00524 
00525   /// @brief Read a string
00526   inline std::string read_str();
00527 
00528   /// @brief Read a float value
00529   inline void read_float(float& FloatVal);
00530 
00531   /// @brief Read a double value
00532   inline void read_double(double& DoubleVal);
00533 
00534   /// @brief Read an arbitrary data chunk of fixed length
00535   inline void read_data(void *Ptr, void *End);
00536 
00537   /// @brief Read a bytecode block header
00538   inline void read_block(unsigned &Type, unsigned &Size);
00539 
00540   /// @brief Read a type identifier and sanitize it.
00541   inline bool read_typeid(unsigned &TypeId);
00542 
00543   /// @brief Recalculate type ID for pre 1.3 bytecode files.
00544   inline bool sanitizeTypeId(unsigned &TypeId );
00545 /// @}
00546 };
00547 
00548 /// @brief A function for creating a BytecodeAnalzer as a handler
00549 /// for the Bytecode reader.
00550 BytecodeHandler* createBytecodeAnalyzerHandler(BytecodeAnalysis& bca,
00551                                                std::ostream* output );
00552 
00553 
00554 } // End llvm namespace
00555 
00556 // vim: sw=2
00557 #endif