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 #include <setjmp.h>
  28
  29 namespace llvm {
  30
  31 class BytecodeHandler; ///< Forward declare the handler interface
  32
  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 {
  43
  44 /// @name Constructors
  45 /// @{
  46 public:
  47   /// @brief Default constructor. By default, no handler is used.
  48   BytecodeReader(BytecodeHandler* h = 0) {
  49     decompressedBlock = 0;
  50     Handler = h;
  51   }
  52
  53   ~BytecodeReader() {
  54     freeState();
  55     if (decompressedBlock) {
  56       ::free(decompressedBlock);
  57       decompressedBlock = 0;
  58     }
  59   }
  60
  61 /// @}
  62 /// @name Types
  63 /// @{
  64 public:
  65
  66   /// @brief A convenience type for the buffer pointer
  67   typedef const unsigned char* BufPtr;
  68
  69   /// @brief The type used for a vector of potentially abstract types
  70   typedef std::vector<PATypeHolder> TypeListTy;
  71
  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
  79   /// globals section.
  80   /// @brief A list of values as a User of those Values.
  81   class ValueList : public User {
  82     std::vector<Use> Uses;
  83   public:
  84     ValueList() : User(Type::VoidTy, Value::ArgumentVal, 0, 0) {}
  85
  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];
  91       ++NumOperands;
  92     }
  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) {
  98         os << i << " ";
  99         getOperand(i)->print(os);
 100         os << "\n";
 101       }
 102     }
 103   };
 104
 105   /// @brief A 2 dimensional table of values
 106   typedef std::vector<ValueList*> ValueTable;
 107
 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;
 112
 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) {}
 122   };
 123
 124   /// @brief A mapping of functions to their LazyFunctionInfo for lazy reading.
 125   typedef std::map<Function*, LazyFunctionInfo> LazyFunctionMap;
 126
 127   /// @brief A list of global variables and the slot number that initializes
 128   /// them.
 129   typedef std::vector<std::pair<GlobalVariable*, unsigned> > GlobalInitsList;
 130
 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;
 135
 136 /// @}
 137 /// @name Methods
 138 /// @{
 139 public:
 140   /// @returns true if an error occurred
 141   /// @brief Main interface to parsing a bytecode buffer.
 142   bool ParseBytecode(
 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
 147   );
 148
 149   /// @brief Parse all function bodies
 150   bool ParseAllFunctionBodies(std::string* ErrMsg);
 151
 152   /// @brief Parse the next function of specific type
 153   bool ParseFunction(Function* Func, std::string* ErrMsg) ;
 154
 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())
 162       return false;
 163     if (ParseFunction(F,ErrMsg))
 164       return true;
 165     return false;
 166   }
 167
 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))
 174       return 0;
 175     return TheModule;
 176   }
 177
 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
 180   /// state.
 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(ErrInfo);
 185     freeState();
 186     return M;
 187   }
 188
 189 /// @}
 190 /// @name Parsing Units For Subclasses
 191 /// @{
 192 protected:
 193   /// @brief Parse whole module scope
 194   void ParseModule();
 195
 196   /// @brief Parse the version information block
 197   void ParseVersionInfo();
 198
 199   /// @brief Parse the ModuleGlobalInfo block
 200   void ParseModuleGlobalInfo();
 201
 202   /// @brief Parse a symbol table
 203   void ParseSymbolTable( Function* Func, SymbolTable *ST);
 204
 205   /// @brief Parse functions lazily.
 206   void ParseFunctionLazily();
 207
 208   ///  @brief Parse a function body
 209   void ParseFunctionBody(Function* Func);
 210
 211   /// @brief Parse the type list portion of a compaction table
 212   void ParseCompactionTypes(unsigned NumEntries);
 213
 214   /// @brief Parse a compaction table
 215   void ParseCompactionTable();
 216
 217   /// @brief Parse global types
 218   void ParseGlobalTypes();
 219
 220   /// @brief Parse a basic block (for LLVM 1.0 basic block blocks)
 221   BasicBlock* ParseBasicBlock(unsigned BlockNo);
 222
 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
 227   );
 228
 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
 239   );
 240
 241   /// @brief Convert previous opcode values for ConstantExpr into the current
 242   /// value.
 243   unsigned upgradeCEOpcodes(
 244     unsigned Opcode,                      ///< Opcode read from bytecode
 245     const std::vector<Constant*> &ArgVec  ///< Arguments of instruction
 246   );
 247
 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
 252   );
 253
 254   /// @brief Parse the whole constant pool
 255   void ParseConstantPool(ValueTable& Values, TypeListTy& Types,
 256                          bool isFunction);
 257
 258   /// @brief Parse a single constant pool value
 259   Value *ParseConstantPoolValue(unsigned TypeID);
 260
 261   /// @brief Parse a block of types constants
 262   void ParseTypes(TypeListTy &Tab, unsigned NumEntries);
 263
 264   /// @brief Parse a single type constant
 265   const Type *ParseType();
 266
 267   /// @brief Parse a string constants block
 268   void ParseStringConstants(unsigned NumEntries, ValueTable &Tab);
 269
 270   /// @brief Release our memory.
 271   void freeState() {
 272     freeTable(FunctionValues);
 273     freeTable(ModuleValues);
 274   }
 275
 276 /// @}
 277 /// @name Data
 278 /// @{
 279 private:
 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
 288
 289   /// Information about the module, extracted from the bytecode revision number.
 290   ///
 291   unsigned char RevisionNum;        // The rev # itself
 292
 293   /// Flags to distinguish LLVM 1.0 & 1.1 bytecode formats (revision #0)
 294
 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;
 298
 299   /// Revision #0 also explicitly encoded zero values for primitive types like
 300   /// int/sbyte/etc.
 301   bool hasExplicitPrimitiveZeros;
 302
 303   // Flags to control features specific the LLVM 1.2 and before (revision #1)
 304
 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;
 308
 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;
 316
 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;
 326
 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.
 333   bool has32BitTypes;
 334
 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;
 339
 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.
 344   bool hasAlignment;
 345
 346   // In version 4 and earlier, the bytecode format did not support the 'undef'
 347   // constant.
 348   bool hasNoUndefValue;
 349
 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;
 353
 354   // In version 4 and earlier, there was no opcode space reserved for the
 355   // unreachable instruction.
 356   bool hasNoUnreachableInst;
 357
 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;
 362
 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;
 367
 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;
 373
 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;
 378
 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;
 382
 383   /// @brief This vector is used to deal with forward references to types in
 384   /// a module.
 385   TypeListTy ModuleTypes;
 386
 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;
 392
 393   /// @brief This vector is used to deal with forward references to types in
 394   /// a function.
 395   TypeListTy FunctionTypes;
 396
 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;
 402
 403   /// @brief This is the table of values belonging to the current function
 404   ValueTable FunctionValues;
 405
 406   /// @brief This is the table of values belonging to the module (global)
 407   ValueTable ModuleValues;
 408
 409   /// @brief This keeps track of function level forward references.
 410   ForwardReferenceMap ForwardReferences;
 411
 412   /// @brief The basic blocks we've parsed, while parsing a function.
 413   std::vector<BasicBlock*> ParsedBasicBlocks;
 414
 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;
 420
 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;
 426
 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;
 431
 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;
 441
 442
 443 /// @}
 444 /// @name Implementation Details
 445 /// @{
 446 private:
 447   /// @brief Determines if this module has a function or not.
 448   bool hasFunctions() { return ! FunctionSignatureList.empty(); }
 449
 450   /// @brief Determines if the type id has an implicit null value.
 451   bool hasImplicitNull(unsigned TyID );
 452
 453   /// @brief Converts a type slot number to its Type*
 454   const Type *getType(unsigned ID);
 455
 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 );
 459
 460   /// @brief Read in and get a sanitized type id
 461   inline const Type* readSanitizedType();
 462
 463   /// @brief Converts a Type* to its type slot number
 464   unsigned getTypeSlot(const Type *Ty);
 465
 466   /// @brief Converts a normal type slot number to a compacted type slot num.
 467   unsigned getCompactionTypeSlot(unsigned type);
 468
 469   /// @brief Gets the global type corresponding to the TypeId
 470   const Type *getGlobalTableType(unsigned TypeId);
 471
 472   /// This is just like getTypeSlot, but when a compaction table is in use,
 473   /// it is ignored.
 474   unsigned getGlobalTableTypeSlot(const Type *Ty);
 475
 476   /// @brief Get a value from its typeid and slot number
 477   Value* getValue(unsigned TypeID, unsigned num, bool Create = true);
 478
 479   /// @brief Get a value from its type and slot number, ignoring compaction
 480   /// tables.
 481   Value *getGlobalTableValue(unsigned TyID, unsigned SlotNo);
 482
 483   /// @brief Get a basic block for current function
 484   BasicBlock *getBasicBlock(unsigned ID);
 485
 486   /// @brief Get a constant value from its typeid and value slot.
 487   Constant* getConstantValue(unsigned typeSlot, unsigned valSlot);
 488
 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);
 493   }
 494
 495   /// @brief Insert a newly created value
 496   unsigned insertValue(Value *V, unsigned Type, ValueTable &Table);
 497
 498   /// @brief Insert the arguments of a function.
 499   void insertArguments(Function* F );
 500
 501   /// @brief Resolve all references to the placeholder (if any) for the
 502   /// given constant.
 503   void ResolveReferencesToConstant(Constant *C, unsigned Typ, unsigned Slot);
 504
 505   /// @brief Free a table, making sure to free the ValueList in the table.
 506   void freeTable(ValueTable &Tab) {
 507     while (!Tab.empty()) {
 508       delete Tab.back();
 509       Tab.pop_back();
 510     }
 511   }
 512
 513   inline void error(const std::string& errmsg);
 514
 515   BytecodeReader(const BytecodeReader &);  // DO NOT IMPLEMENT
 516   void operator=(const BytecodeReader &);  // DO NOT IMPLEMENT
 517
 518 /// @}
 519 /// @name Reader Primitives
 520 /// @{
 521 private:
 522
 523   /// @brief Is there more to parse in the current block?
 524   inline bool moreInBlock();
 525
 526   /// @brief Have we read past the end of the block
 527   inline void checkPastBlockEnd(const char * block_name);
 528
 529   /// @brief Align to 32 bits
 530   inline void align32();
 531
 532   /// @brief Read an unsigned integer as 32-bits
 533   inline unsigned read_uint();
 534
 535   /// @brief Read an unsigned integer with variable bit rate encoding
 536   inline unsigned read_vbr_uint();
 537
 538   /// @brief Read an unsigned integer of no more than 24-bits with variable
 539   /// bit rate encoding.
 540   inline unsigned read_vbr_uint24();
 541
 542   /// @brief Read an unsigned 64-bit integer with variable bit rate encoding.
 543   inline uint64_t read_vbr_uint64();
 544
 545   /// @brief Read a signed 64-bit integer with variable bit rate encoding.
 546   inline int64_t read_vbr_int64();
 547
 548   /// @brief Read a string
 549   inline std::string read_str();
 550
 551   /// @brief Read a float value
 552   inline void read_float(float& FloatVal);
 553
 554   /// @brief Read a double value
 555   inline void read_double(double& DoubleVal);
 556
 557   /// @brief Read an arbitrary data chunk of fixed length
 558   inline void read_data(void *Ptr, void *End);
 559
 560   /// @brief Read a bytecode block header
 561   inline void read_block(unsigned &Type, unsigned &Size);
 562
 563   /// @brief Read a type identifier and sanitize it.
 564   inline bool read_typeid(unsigned &TypeId);
 565
 566   /// @brief Recalculate type ID for pre 1.3 bytecode files.
 567   inline bool sanitizeTypeId(unsigned &TypeId );
 568 /// @}
 569 };
 570
 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 );
 575
 576
 577 } // End llvm namespace
 578
 579 // vim: sw=2
 580 #endif