lib/Bytecode/Reader/Reader.h

   1 //===-- Reader.h - Interface To Bytecode Reading ----------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   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.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  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.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef BYTECODE_PARSER_H
  17 #define BYTECODE_PARSER_H
  18
  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"
  25 #include <utility>
  26 #include <map>
  27
  28 namespace llvm {
  29
  30 class BytecodeHandler; ///< Forward declare the handler interface
  31
  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 {
  42
  43 /// @name Constructors
  44 /// @{
  45 public:
  46   /// @brief Default constructor. By default, no handler is used.
  47   BytecodeReader(BytecodeHandler* h = 0) {
  48     decompressedBlock = 0;
  49     Handler = h;
  50   }
  51
  52   ~BytecodeReader() {
  53     freeState();
  54     if (decompressedBlock) {
  55       ::free(decompressedBlock);
  56       decompressedBlock = 0;
  57     }
  58   }
  59
  60 /// @}
  61 /// @name Types
  62 /// @{
  63 public:
  64
  65   /// @brief A convenience type for the buffer pointer
  66   typedef const unsigned char* BufPtr;
  67
  68   /// @brief The type used for a vector of potentially abstract types
  69   typedef std::vector<PATypeHolder> TypeListTy;
  70
  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
  78   /// globals section.
  79   /// @brief A list of values as a User of those Values.
  80   class ValueList : public User {
  81     std::vector<Use> Uses;
  82   public:
  83     ValueList() : User(Type::VoidTy, Value::ValueListVal, 0, 0) {}
  84
  85     // vector compatibility methods
  86     unsigned size() const { return getNumOperands(); }
  87     void push_back(Value *V) {
  88       Uses.push_back(Use(V, this));
  89       OperandList = &Uses[0];
  90       ++NumOperands;
  91     }
  92     Value *back() const { return Uses.back(); }
  93     void pop_back() { Uses.pop_back(); --NumOperands; }
  94     bool empty() const { return NumOperands == 0; }
  95     virtual void print(std::ostream& os) const {
  96       for (unsigned i = 0; i < size(); ++i) {
  97         os << i << " ";
  98         getOperand(i)->print(os);
  99         os << "\n";
 100       }
 101     }
 102   };
 103
 104   /// @brief A 2 dimensional table of values
 105   typedef std::vector<ValueList*> ValueTable;
 106
 107   /// This map is needed so that forward references to constants can be looked
 108   /// up by Type and slot number when resolving those references.
 109   /// @brief A mapping of a Type/slot pair to a Constant*.
 110   typedef std::map<std::pair<unsigned,unsigned>, Constant*> ConstantRefsType;
 111
 112   /// For lazy read-in of functions, we need to save the location in the
 113   /// data stream where the function is located. This structure provides that
 114   /// information. Lazy read-in is used mostly by the JIT which only wants to
 115   /// resolve functions as it needs them.
 116   /// @brief Keeps pointers to function contents for later use.
 117   struct LazyFunctionInfo {
 118     const unsigned char *Buf, *EndBuf;
 119     LazyFunctionInfo(const unsigned char *B = 0, const unsigned char *EB = 0)
 120       : Buf(B), EndBuf(EB) {}
 121   };
 122
 123   /// @brief A mapping of functions to their LazyFunctionInfo for lazy reading.
 124   typedef std::map<Function*, LazyFunctionInfo> LazyFunctionMap;
 125
 126   /// @brief A list of global variables and the slot number that initializes
 127   /// them.
 128   typedef std::vector<std::pair<GlobalVariable*, unsigned> > GlobalInitsList;
 129
 130   /// This type maps a typeslot/valueslot pair to the corresponding Value*.
 131   /// It is used for dealing with forward references as values are read in.
 132   /// @brief A map for dealing with forward references of values.
 133   typedef std::map<std::pair<unsigned,unsigned>,Value*> ForwardReferenceMap;
 134
 135 /// @}
 136 /// @name Methods
 137 /// @{
 138 public:
 139   /// @brief Main interface to parsing a bytecode buffer.
 140   void ParseBytecode(
 141      const unsigned char *Buf,    ///< Beginning of the bytecode buffer
 142      unsigned Length,             ///< Length of the bytecode buffer
 143      const std::string &ModuleID  ///< An identifier for the module constructed.
 144   );
 145
 146   /// @brief Parse all function bodies
 147   void ParseAllFunctionBodies();
 148
 149   /// @brief Parse the next function of specific type
 150   void ParseFunction(Function* Func) ;
 151
 152   /// This method is abstract in the parent ModuleProvider class. Its
 153   /// implementation is identical to the ParseFunction method.
 154   /// @see ParseFunction
 155   /// @brief Make a specific function materialize.
 156   virtual void materializeFunction(Function *F) {
 157     LazyFunctionMap::iterator Fi = LazyFunctionLoadMap.find(F);
 158     if (Fi == LazyFunctionLoadMap.end()) return;
 159     ParseFunction(F);
 160   }
 161
 162   /// This method is abstract in the parent ModuleProvider class. Its
 163   /// implementation is identical to ParseAllFunctionBodies.
 164   /// @see ParseAllFunctionBodies
 165   /// @brief Make the whole module materialize
 166   virtual Module* materializeModule() {
 167     ParseAllFunctionBodies();
 168     return TheModule;
 169   }
 170
 171   /// This method is provided by the parent ModuleProvde class and overriden
 172   /// here. It simply releases the module from its provided and frees up our
 173   /// state.
 174   /// @brief Release our hold on the generated module
 175   Module* releaseModule() {
 176     // Since we're losing control of this Module, we must hand it back complete
 177     Module *M = ModuleProvider::releaseModule();
 178     freeState();
 179     return M;
 180   }
 181
 182 /// @}
 183 /// @name Parsing Units For Subclasses
 184 /// @{
 185 protected:
 186   /// @brief Parse whole module scope
 187   void ParseModule();
 188
 189   /// @brief Parse the version information block
 190   void ParseVersionInfo();
 191
 192   /// @brief Parse the ModuleGlobalInfo block
 193   void ParseModuleGlobalInfo();
 194
 195   /// @brief Parse a symbol table
 196   void ParseSymbolTable( Function* Func, SymbolTable *ST);
 197
 198   /// @brief Parse functions lazily.
 199   void ParseFunctionLazily();
 200
 201   ///  @brief Parse a function body
 202   void ParseFunctionBody(Function* Func);
 203
 204   /// @brief Parse the type list portion of a compaction table
 205   void ParseCompactionTypes(unsigned NumEntries);
 206
 207   /// @brief Parse a compaction table
 208   void ParseCompactionTable();
 209
 210   /// @brief Parse global types
 211   void ParseGlobalTypes();
 212
 213   /// @brief Parse a basic block (for LLVM 1.0 basic block blocks)
 214   BasicBlock* ParseBasicBlock(unsigned BlockNo);
 215
 216   /// @brief parse an instruction list (for post LLVM 1.0 instruction lists
 217   /// with blocks differentiated by terminating instructions.
 218   unsigned ParseInstructionList(
 219     Function* F   ///< The function into which BBs will be inserted
 220   );
 221
 222   /// @brief Parse a single instruction.
 223   void ParseInstruction(
 224     std::vector<unsigned>& Args,   ///< The arguments to be filled in
 225     BasicBlock* BB             ///< The BB the instruction goes in
 226   );
 227
 228   /// @brief Parse the whole constant pool
 229   void ParseConstantPool(ValueTable& Values, TypeListTy& Types,
 230                          bool isFunction);
 231
 232   /// @brief Parse a single constant value
 233   Constant* ParseConstantValue(unsigned TypeID);
 234
 235   /// @brief Parse a block of types constants
 236   void ParseTypes(TypeListTy &Tab, unsigned NumEntries);
 237
 238   /// @brief Parse a single type constant
 239   const Type *ParseType();
 240
 241   /// @brief Parse a string constants block
 242   void ParseStringConstants(unsigned NumEntries, ValueTable &Tab);
 243
 244 /// @}
 245 /// @name Data
 246 /// @{
 247 private:
 248   char*  decompressedBlock; ///< Result of decompression
 249   BufPtr MemStart;     ///< Start of the memory buffer
 250   BufPtr MemEnd;       ///< End of the memory buffer
 251   BufPtr BlockStart;   ///< Start of current block being parsed
 252   BufPtr BlockEnd;     ///< End of current block being parsed
 253   BufPtr At;           ///< Where we're currently parsing at
 254
 255   /// Information about the module, extracted from the bytecode revision number.
 256   ///
 257   unsigned char RevisionNum;        // The rev # itself
 258
 259   /// Flags to distinguish LLVM 1.0 & 1.1 bytecode formats (revision #0)
 260
 261   /// Revision #0 had an explicit alignment of data only for the
 262   /// ModuleGlobalInfo block.  This was fixed to be like all other blocks in 1.2
 263   bool hasInconsistentModuleGlobalInfo;
 264
 265   /// Revision #0 also explicitly encoded zero values for primitive types like
 266   /// int/sbyte/etc.
 267   bool hasExplicitPrimitiveZeros;
 268
 269   // Flags to control features specific the LLVM 1.2 and before (revision #1)
 270
 271   /// LLVM 1.2 and earlier required that getelementptr structure indices were
 272   /// ubyte constants and that sequential type indices were longs.
 273   bool hasRestrictedGEPTypes;
 274
 275   /// LLVM 1.2 and earlier had class Type deriving from Value and the Type
 276   /// objects were located in the "Type Type" plane of various lists in read
 277   /// by the bytecode reader. In LLVM 1.3 this is no longer the case. Types are
 278   /// completely distinct from Values. Consequently, Types are written in fixed
 279   /// locations in LLVM 1.3. This flag indicates that the older Type derived
 280   /// from Value style of bytecode file is being read.
 281   bool hasTypeDerivedFromValue;
 282
 283   /// LLVM 1.2 and earlier encoded block headers as two uint (8 bytes), one for
 284   /// the size and one for the type. This is a bit wasteful, especially for
 285   /// small files where the 8 bytes per block is a large fraction of the total
 286   /// block size. In LLVM 1.3, the block type and length are encoded into a
 287   /// single uint32 by restricting the number of block types (limit 31) and the
 288   /// maximum size of a block (limit 2^27-1=134,217,727). Note that the module
 289   /// block still uses the 8-byte format so the maximum size of a file can be
 290   /// 2^32-1 bytes long.
 291   bool hasLongBlockHeaders;
 292
 293   /// LLVM 1.2 and earlier wrote type slot numbers as vbr_uint32. In LLVM 1.3
 294   /// this has been reduced to vbr_uint24. It shouldn't make much difference
 295   /// since we haven't run into a module with > 24 million types, but for safety
 296   /// the 24-bit restriction has been enforced in 1.3 to free some bits in
 297   /// various places and to ensure consistency. In particular, global vars are
 298   /// restricted to 24-bits.
 299   bool has32BitTypes;
 300
 301   /// LLVM 1.2 and earlier did not provide a target triple nor a list of
 302   /// libraries on which the bytecode is dependent. LLVM 1.3 provides these
 303   /// features, for use in future versions of LLVM.
 304   bool hasNoDependentLibraries;
 305
 306   /// LLVM 1.3 and earlier caused blocks and other fields to start on 32-bit
 307   /// aligned boundaries. This can lead to as much as 30% bytecode size overhead
 308   /// in various corner cases (lots of long instructions). In LLVM 1.4,
 309   /// alignment of bytecode fields was done away with completely.
 310   bool hasAlignment;
 311
 312   // In version 4 and earlier, the bytecode format did not support the 'undef'
 313   // constant.
 314   bool hasNoUndefValue;
 315
 316   // In version 4 and earlier, the bytecode format did not save space for flags
 317   // in the global info block for functions.
 318   bool hasNoFlagsForFunctions;
 319
 320   // In version 4 and earlier, there was no opcode space reserved for the
 321   // unreachable instruction.
 322   bool hasNoUnreachableInst;
 323
 324   // In version 5, basic blocks have a minimum index of 0 whereas all the
 325   // other primitives have a minimum index of 1 (because 0 is the "null"
 326   // value. In version 5, we made this consistent.
 327   bool hasInconsistentBBSlotNums;
 328
 329   // In version 5, the types SByte and UByte were encoded as vbr_uint so that
 330   // signed values > 63 and unsigned values >127 would be encoded as two
 331   // bytes. In version 5, they are encoded directly in a single byte.
 332   bool hasVBRByteTypes;
 333
 334   // In version 5, modules begin with a "Module Block" which encodes a 4-byte
 335   // integer value 0x01 to identify the module block. This is unnecessary and
 336   // removed in version 5.
 337   bool hasUnnecessaryModuleBlockId;
 338
 339   /// CompactionTypes - If a compaction table is active in the current function,
 340   /// this is the mapping that it contains.  We keep track of what resolved type
 341   /// it is as well as what global type entry it is.
 342   std::vector<std::pair<const Type*, unsigned> > CompactionTypes;
 343
 344   /// @brief If a compaction table is active in the current function,
 345   /// this is the mapping that it contains.
 346   std::vector<std::vector<Value*> > CompactionValues;
 347
 348   /// @brief This vector is used to deal with forward references to types in
 349   /// a module.
 350   TypeListTy ModuleTypes;
 351
 352   /// @brief This vector is used to deal with forward references to types in
 353   /// a function.
 354   TypeListTy FunctionTypes;
 355
 356   /// When the ModuleGlobalInfo section is read, we create a Function object
 357   /// for each function in the module. When the function is loaded, after the
 358   /// module global info is read, this Function is populated. Until then, the
 359   /// functions in this vector just hold the function signature.
 360   std::vector<Function*> FunctionSignatureList;
 361
 362   /// @brief This is the table of values belonging to the current function
 363   ValueTable FunctionValues;
 364
 365   /// @brief This is the table of values belonging to the module (global)
 366   ValueTable ModuleValues;
 367
 368   /// @brief This keeps track of function level forward references.
 369   ForwardReferenceMap ForwardReferences;
 370
 371   /// @brief The basic blocks we've parsed, while parsing a function.
 372   std::vector<BasicBlock*> ParsedBasicBlocks;
 373
 374   /// This maintains a mapping between <Type, Slot #>'s and forward references
 375   /// to constants.  Such values may be referenced before they are defined, and
 376   /// if so, the temporary object that they represent is held here.  @brief
 377   /// Temporary place for forward references to constants.
 378   ConstantRefsType ConstantFwdRefs;
 379
 380   /// Constant values are read in after global variables.  Because of this, we
 381   /// must defer setting the initializers on global variables until after module
 382   /// level constants have been read.  In the mean time, this list keeps track
 383   /// of what we must do.
 384   GlobalInitsList GlobalInits;
 385
 386   // For lazy reading-in of functions, we need to save away several pieces of
 387   // information about each function: its begin and end pointer in the buffer
 388   // and its FunctionSlot.
 389   LazyFunctionMap LazyFunctionLoadMap;
 390
 391   /// This stores the parser's handler which is used for handling tasks other
 392   /// just than reading bytecode into the IR. If this is non-null, calls on
 393   /// the (polymorphic) BytecodeHandler interface (see llvm/Bytecode/Handler.h)
 394   /// will be made to report the logical structure of the bytecode file. What
 395   /// the handler does with the events it receives is completely orthogonal to
 396   /// the business of parsing the bytecode and building the IR.  This is used,
 397   /// for example, by the llvm-abcd tool for analysis of byte code.
 398   /// @brief Handler for parsing events.
 399   BytecodeHandler* Handler;
 400
 401 /// @}
 402 /// @name Implementation Details
 403 /// @{
 404 private:
 405   /// @brief Determines if this module has a function or not.
 406   bool hasFunctions() { return ! FunctionSignatureList.empty(); }
 407
 408   /// @brief Determines if the type id has an implicit null value.
 409   bool hasImplicitNull(unsigned TyID );
 410
 411   /// @brief Converts a type slot number to its Type*
 412   const Type *getType(unsigned ID);
 413
 414   /// @brief Converts a pre-sanitized type slot number to its Type* and
 415   /// sanitizes the type id.
 416   inline const Type* getSanitizedType(unsigned& ID );
 417
 418   /// @brief Read in and get a sanitized type id
 419   inline const Type* readSanitizedType();
 420
 421   /// @brief Converts a Type* to its type slot number
 422   unsigned getTypeSlot(const Type *Ty);
 423
 424   /// @brief Converts a normal type slot number to a compacted type slot num.
 425   unsigned getCompactionTypeSlot(unsigned type);
 426
 427   /// @brief Gets the global type corresponding to the TypeId
 428   const Type *getGlobalTableType(unsigned TypeId);
 429
 430   /// This is just like getTypeSlot, but when a compaction table is in use,
 431   /// it is ignored.
 432   unsigned getGlobalTableTypeSlot(const Type *Ty);
 433
 434   /// @brief Get a value from its typeid and slot number
 435   Value* getValue(unsigned TypeID, unsigned num, bool Create = true);
 436
 437   /// @brief Get a value from its type and slot number, ignoring compaction
 438   /// tables.
 439   Value *getGlobalTableValue(unsigned TyID, unsigned SlotNo);
 440
 441   /// @brief Get a basic block for current function
 442   BasicBlock *getBasicBlock(unsigned ID);
 443
 444   /// @brief Get a constant value from its typeid and value slot.
 445   Constant* getConstantValue(unsigned typeSlot, unsigned valSlot);
 446
 447   /// @brief Convenience function for getting a constant value when
 448   /// the Type has already been resolved.
 449   Constant* getConstantValue(const Type *Ty, unsigned valSlot) {
 450     return getConstantValue(getTypeSlot(Ty), valSlot);
 451   }
 452
 453   /// @brief Insert a newly created value
 454   unsigned insertValue(Value *V, unsigned Type, ValueTable &Table);
 455
 456   /// @brief Insert the arguments of a function.
 457   void insertArguments(Function* F );
 458
 459   /// @brief Resolve all references to the placeholder (if any) for the
 460   /// given constant.
 461   void ResolveReferencesToConstant(Constant *C, unsigned Typ, unsigned Slot);
 462
 463   /// @brief Release our memory.
 464   void freeState() {
 465     freeTable(FunctionValues);
 466     freeTable(ModuleValues);
 467   }
 468
 469   /// @brief Free a table, making sure to free the ValueList in the table.
 470   void freeTable(ValueTable &Tab) {
 471     while (!Tab.empty()) {
 472       delete Tab.back();
 473       Tab.pop_back();
 474     }
 475   }
 476
 477   inline void error(std::string errmsg);
 478
 479   BytecodeReader(const BytecodeReader &);  // DO NOT IMPLEMENT
 480   void operator=(const BytecodeReader &);  // DO NOT IMPLEMENT
 481
 482 /// @}
 483 /// @name Reader Primitives
 484 /// @{
 485 private:
 486
 487   /// @brief Is there more to parse in the current block?
 488   inline bool moreInBlock();
 489
 490   /// @brief Have we read past the end of the block
 491   inline void checkPastBlockEnd(const char * block_name);
 492
 493   /// @brief Align to 32 bits
 494   inline void align32();
 495
 496   /// @brief Read an unsigned integer as 32-bits
 497   inline unsigned read_uint();
 498
 499   /// @brief Read an unsigned integer with variable bit rate encoding
 500   inline unsigned read_vbr_uint();
 501
 502   /// @brief Read an unsigned integer of no more than 24-bits with variable
 503   /// bit rate encoding.
 504   inline unsigned read_vbr_uint24();
 505
 506   /// @brief Read an unsigned 64-bit integer with variable bit rate encoding.
 507   inline uint64_t read_vbr_uint64();
 508
 509   /// @brief Read a signed 64-bit integer with variable bit rate encoding.
 510   inline int64_t read_vbr_int64();
 511
 512   /// @brief Read a string
 513   inline std::string read_str();
 514
 515   /// @brief Read a float value
 516   inline void read_float(float& FloatVal);
 517
 518   /// @brief Read a double value
 519   inline void read_double(double& DoubleVal);
 520
 521   /// @brief Read an arbitrary data chunk of fixed length
 522   inline void read_data(void *Ptr, void *End);
 523
 524   /// @brief Read a bytecode block header
 525   inline void read_block(unsigned &Type, unsigned &Size);
 526
 527   /// @brief Read a type identifier and sanitize it.
 528   inline bool read_typeid(unsigned &TypeId);
 529
 530   /// @brief Recalculate type ID for pre 1.3 bytecode files.
 531   inline bool sanitizeTypeId(unsigned &TypeId );
 532 /// @}
 533 };
 534
 535 /// @brief A function for creating a BytecodeAnalzer as a handler
 536 /// for the Bytecode reader.
 537 BytecodeHandler* createBytecodeAnalyzerHandler(BytecodeAnalysis& bca,
 538                                                std::ostream* output );
 539
 540
 541 } // End llvm namespace
 542
 543 // vim: sw=2
 544 #endif