lib/Bytecode/Reader/Reader.cpp

   1 //===- Reader.cpp - Code to read bytecode files ---------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This library implements the functionality defined in llvm/Bytecode/Reader.h
  11 //
  12 // Note that this library should be as fast as possible, reentrant, and
  13 // threadsafe!!
  14 //
  15 // TODO: Allow passing in an option to ignore the symbol table
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "Reader.h"
  20 #include "llvm/Bytecode/BytecodeHandler.h"
  21 #include "llvm/BasicBlock.h"
  22 #include "llvm/Constants.h"
  23 #include "llvm/Instructions.h"
  24 #include "llvm/SymbolTable.h"
  25 #include "llvm/Bytecode/Format.h"
  26 #include "llvm/Support/GetElementPtrTypeIterator.h"
  27 #include "Support/StringExtras.h"
  28 #include <sstream>
  29
  30 using namespace llvm;
  31
  32 namespace {
  33
  34 /// @brief A class for maintaining the slot number definition
  35 /// as a placeholder for the actual definition for forward constants defs.
  36 class ConstantPlaceHolder : public ConstantExpr {
  37   unsigned ID;
  38   ConstantPlaceHolder();                       // DO NOT IMPLEMENT
  39   void operator=(const ConstantPlaceHolder &); // DO NOT IMPLEMENT
  40 public:
  41   ConstantPlaceHolder(const Type *Ty, unsigned id)
  42     : ConstantExpr(Instruction::UserOp1, Constant::getNullValue(Ty), Ty),
  43     ID(id) {}
  44   unsigned getID() { return ID; }
  45 };
  46
  47 }
  48
  49 // Provide some details on error
  50 inline void BytecodeReader::error(std::string err) {
  51   err +=  " (Vers=" ;
  52   err += itostr(RevisionNum) ;
  53   err += ", Pos=" ;
  54   err += itostr(At-MemStart);
  55   err += ")";
  56   throw err;
  57 }
  58
  59 //===----------------------------------------------------------------------===//
  60 // Bytecode Reading Methods
  61 //===----------------------------------------------------------------------===//
  62
  63 /// Determine if the current block being read contains any more data.
  64 inline bool BytecodeReader::moreInBlock() {
  65   return At < BlockEnd;
  66 }
  67
  68 /// Throw an error if we've read past the end of the current block
  69 inline void BytecodeReader::checkPastBlockEnd(const char * block_name) {
  70   if (At > BlockEnd)
  71     error(std::string("Attempt to read past the end of ") + block_name + " block.");
  72 }
  73
  74 /// Align the buffer position to a 32 bit boundary
  75 inline void BytecodeReader::align32() {
  76   BufPtr Save = At;
  77   At = (const unsigned char *)((unsigned long)(At+3) & (~3UL));
  78   if (At > Save)
  79     if (Handler) Handler->handleAlignment(At - Save);
  80   if (At > BlockEnd)
  81     error("Ran out of data while aligning!");
  82 }
  83
  84 /// Read a whole unsigned integer
  85 inline unsigned BytecodeReader::read_uint() {
  86   if (At+4 > BlockEnd)
  87     error("Ran out of data reading uint!");
  88   At += 4;
  89   return At[-4] | (At[-3] << 8) | (At[-2] << 16) | (At[-1] << 24);
  90 }
  91
  92 /// Read a variable-bit-rate encoded unsigned integer
  93 inline unsigned BytecodeReader::read_vbr_uint() {
  94   unsigned Shift = 0;
  95   unsigned Result = 0;
  96   BufPtr Save = At;
  97
  98   do {
  99     if (At == BlockEnd)
 100       error("Ran out of data reading vbr_uint!");
 101     Result |= (unsigned)((*At++) & 0x7F) << Shift;
 102     Shift += 7;
 103   } while (At[-1] & 0x80);
 104   if (Handler) Handler->handleVBR32(At-Save);
 105   return Result;
 106 }
 107
 108 /// Read a variable-bit-rate encoded unsigned 64-bit integer.
 109 inline uint64_t BytecodeReader::read_vbr_uint64() {
 110   unsigned Shift = 0;
 111   uint64_t Result = 0;
 112   BufPtr Save = At;
 113
 114   do {
 115     if (At == BlockEnd)
 116       error("Ran out of data reading vbr_uint64!");
 117     Result |= (uint64_t)((*At++) & 0x7F) << Shift;
 118     Shift += 7;
 119   } while (At[-1] & 0x80);
 120   if (Handler) Handler->handleVBR64(At-Save);
 121   return Result;
 122 }
 123
 124 /// Read a variable-bit-rate encoded signed 64-bit integer.
 125 inline int64_t BytecodeReader::read_vbr_int64() {
 126   uint64_t R = read_vbr_uint64();
 127   if (R & 1) {
 128     if (R != 1)
 129       return -(int64_t)(R >> 1);
 130     else   // There is no such thing as -0 with integers.  "-0" really means
 131            // 0x8000000000000000.
 132       return 1LL << 63;
 133   } else
 134     return  (int64_t)(R >> 1);
 135 }
 136
 137 /// Read a pascal-style string (length followed by text)
 138 inline std::string BytecodeReader::read_str() {
 139   unsigned Size = read_vbr_uint();
 140   const unsigned char *OldAt = At;
 141   At += Size;
 142   if (At > BlockEnd)             // Size invalid?
 143     error("Ran out of data reading a string!");
 144   return std::string((char*)OldAt, Size);
 145 }
 146
 147 /// Read an arbitrary block of data
 148 inline void BytecodeReader::read_data(void *Ptr, void *End) {
 149   unsigned char *Start = (unsigned char *)Ptr;
 150   unsigned Amount = (unsigned char *)End - Start;
 151   if (At+Amount > BlockEnd)
 152     error("Ran out of data!");
 153   std::copy(At, At+Amount, Start);
 154   At += Amount;
 155 }
 156
 157 /// Read a float value in little-endian order
 158 inline void BytecodeReader::read_float(float& FloatVal) {
 159   if (hasPlatformSpecificFloatingPoint) {
 160     read_data(&FloatVal, &FloatVal+1);
 161   } else {
 162     /// FIXME: This isn't optimal, it has size problems on some platforms
 163     /// where FP is not IEEE.
 164     union {
 165       float f;
 166       uint32_t i;
 167     } FloatUnion;
 168     FloatUnion.i = At[0] | (At[1] << 8) | (At[2] << 16) | (At[3] << 24);
 169     At+=sizeof(uint32_t);
 170     FloatVal = FloatUnion.f;
 171   }
 172 }
 173
 174 /// Read a double value in little-endian order
 175 inline void BytecodeReader::read_double(double& DoubleVal) {
 176   if (hasPlatformSpecificFloatingPoint) {
 177     read_data(&DoubleVal, &DoubleVal+1);
 178   } else {
 179     /// FIXME: This isn't optimal, it has size problems on some platforms
 180     /// where FP is not IEEE.
 181     union {
 182       double d;
 183       uint64_t i;
 184     } DoubleUnion;
 185     DoubleUnion.i = At[0] | (At[1] << 8) | (At[2] << 16) | (At[3] << 24) |
 186                     (uint64_t(At[4]) << 32) | (uint64_t(At[5]) << 40) |
 187                     (uint64_t(At[6]) << 48) | (uint64_t(At[7]) << 56);
 188     At+=sizeof(uint64_t);
 189     DoubleVal = DoubleUnion.d;
 190   }
 191 }
 192
 193 /// Read a block header and obtain its type and size
 194 inline void BytecodeReader::read_block(unsigned &Type, unsigned &Size) {
 195   if ( hasLongBlockHeaders ) {
 196     Type = read_uint();
 197     Size = read_uint();
 198     switch (Type) {
 199     case BytecodeFormat::Reserved_DoNotUse :
 200       error("Reserved_DoNotUse used as Module Type?");
 201       Type = BytecodeFormat::Module; break;
 202     case BytecodeFormat::Module:
 203       Type = BytecodeFormat::ModuleBlockID; break;
 204     case BytecodeFormat::Function:
 205       Type = BytecodeFormat::FunctionBlockID; break;
 206     case BytecodeFormat::ConstantPool:
 207       Type = BytecodeFormat::ConstantPoolBlockID; break;
 208     case BytecodeFormat::SymbolTable:
 209       Type = BytecodeFormat::SymbolTableBlockID; break;
 210     case BytecodeFormat::ModuleGlobalInfo:
 211       Type = BytecodeFormat::ModuleGlobalInfoBlockID; break;
 212     case BytecodeFormat::GlobalTypePlane:
 213       Type = BytecodeFormat::GlobalTypePlaneBlockID; break;
 214     case BytecodeFormat::InstructionList:
 215       Type = BytecodeFormat::InstructionListBlockID; break;
 216     case BytecodeFormat::CompactionTable:
 217       Type = BytecodeFormat::CompactionTableBlockID; break;
 218     case BytecodeFormat::BasicBlock:
 219       /// This block type isn't used after version 1.1. However, we have to
 220       /// still allow the value in case this is an old bc format file.
 221       /// We just let its value creep thru.
 222       break;
 223     default:
 224       error("Invalid module type found: " + utostr(Type));
 225       break;
 226     }
 227   } else {
 228     Size = read_uint();
 229     Type = Size & 0x1F; // mask low order five bits
 230     Size >>= 5; // get rid of five low order bits, leaving high 27
 231   }
 232   BlockStart = At;
 233   if (At + Size > BlockEnd)
 234     error("Attempt to size a block past end of memory");
 235   BlockEnd = At + Size;
 236   if (Handler) Handler->handleBlock(Type, BlockStart, Size);
 237 }
 238
 239
 240 /// In LLVM 1.2 and before, Types were derived from Value and so they were
 241 /// written as part of the type planes along with any other Value. In LLVM
 242 /// 1.3 this changed so that Type does not derive from Value. Consequently,
 243 /// the BytecodeReader's containers for Values can't contain Types because
 244 /// there's no inheritance relationship. This means that the "Type Type"
 245 /// plane is defunct along with the Type::TypeTyID TypeID. In LLVM 1.3
 246 /// whenever a bytecode construct must have both types and values together,
 247 /// the types are always read/written first and then the Values. Furthermore
 248 /// since Type::TypeTyID no longer exists, its value (12) now corresponds to
 249 /// Type::LabelTyID. In order to overcome this we must "sanitize" all the
 250 /// type TypeIDs we encounter. For LLVM 1.3 bytecode files, there's no change.
 251 /// For LLVM 1.2 and before, this function will decrement the type id by
 252 /// one to account for the missing Type::TypeTyID enumerator if the value is
 253 /// larger than 12 (Type::LabelTyID). If the value is exactly 12, then this
 254 /// function returns true, otherwise false. This helps detect situations
 255 /// where the pre 1.3 bytecode is indicating that what follows is a type.
 256 /// @returns true iff type id corresponds to pre 1.3 "type type"
 257 inline bool BytecodeReader::sanitizeTypeId(unsigned &TypeId) {
 258   if (hasTypeDerivedFromValue) { /// do nothing if 1.3 or later
 259     if (TypeId == Type::LabelTyID) {
 260       TypeId = Type::VoidTyID; // sanitize it
 261       return true; // indicate we got TypeTyID in pre 1.3 bytecode
 262     } else if (TypeId > Type::LabelTyID)
 263       --TypeId; // shift all planes down because type type plane is missing
 264   }
 265   return false;
 266 }
 267
 268 /// Reads a vbr uint to read in a type id and does the necessary
 269 /// conversion on it by calling sanitizeTypeId.
 270 /// @returns true iff \p TypeId read corresponds to a pre 1.3 "type type"
 271 /// @see sanitizeTypeId
 272 inline bool BytecodeReader::read_typeid(unsigned &TypeId) {
 273   TypeId = read_vbr_uint();
 274   if ( !has32BitTypes )
 275     if ( TypeId == 0x00FFFFFF )
 276       TypeId = read_vbr_uint();
 277   return sanitizeTypeId(TypeId);
 278 }
 279
 280 //===----------------------------------------------------------------------===//
 281 // IR Lookup Methods
 282 //===----------------------------------------------------------------------===//
 283
 284 /// Determine if a type id has an implicit null value
 285 inline bool BytecodeReader::hasImplicitNull(unsigned TyID) {
 286   if (!hasExplicitPrimitiveZeros)
 287     return TyID != Type::LabelTyID && TyID != Type::VoidTyID;
 288   return TyID >= Type::FirstDerivedTyID;
 289 }
 290
 291 /// Obtain a type given a typeid and account for things like compaction tables,
 292 /// function level vs module level, and the offsetting for the primitive types.
 293 const Type *BytecodeReader::getType(unsigned ID) {
 294   if (ID < Type::FirstDerivedTyID)
 295     if (const Type *T = Type::getPrimitiveType((Type::TypeID)ID))
 296       return T;   // Asked for a primitive type...
 297
 298   // Otherwise, derived types need offset...
 299   ID -= Type::FirstDerivedTyID;
 300
 301   if (!CompactionTypes.empty()) {
 302     if (ID >= CompactionTypes.size())
 303       error("Type ID out of range for compaction table!");
 304     return CompactionTypes[ID];
 305   }
 306
 307   // Is it a module-level type?
 308   if (ID < ModuleTypes.size())
 309     return ModuleTypes[ID].get();
 310
 311   // Nope, is it a function-level type?
 312   ID -= ModuleTypes.size();
 313   if (ID < FunctionTypes.size())
 314     return FunctionTypes[ID].get();
 315
 316   error("Illegal type reference!");
 317   return Type::VoidTy;
 318 }
 319
 320 /// Get a sanitized type id. This just makes sure that the \p ID
 321 /// is both sanitized and not the "type type" of pre-1.3 bytecode.
 322 /// @see sanitizeTypeId
 323 inline const Type* BytecodeReader::getSanitizedType(unsigned& ID) {
 324   if (sanitizeTypeId(ID))
 325     error("Invalid type id encountered");
 326   return getType(ID);
 327 }
 328
 329 /// This method just saves some coding. It uses read_typeid to read
 330 /// in a sanitized type id, errors that its not the type type, and
 331 /// then calls getType to return the type value.
 332 inline const Type* BytecodeReader::readSanitizedType() {
 333   unsigned ID;
 334   if (read_typeid(ID))
 335     error("Invalid type id encountered");
 336   return getType(ID);
 337 }
 338
 339 /// Get the slot number associated with a type accounting for primitive
 340 /// types, compaction tables, and function level vs module level.
 341 unsigned BytecodeReader::getTypeSlot(const Type *Ty) {
 342   if (Ty->isPrimitiveType())
 343     return Ty->getTypeID();
 344
 345   // Scan the compaction table for the type if needed.
 346   if (!CompactionTypes.empty()) {
 347     std::vector<const Type*>::const_iterator I =
 348       find(CompactionTypes.begin(), CompactionTypes.end(), Ty);
 349
 350     if (I == CompactionTypes.end())
 351       error("Couldn't find type specified in compaction table!");
 352     return Type::FirstDerivedTyID + (&*I - &CompactionTypes[0]);
 353   }
 354
 355   // Check the function level types first...
 356   TypeListTy::iterator I = find(FunctionTypes.begin(), FunctionTypes.end(), Ty);
 357
 358   if (I != FunctionTypes.end())
 359     return Type::FirstDerivedTyID + ModuleTypes.size() +
 360            (&*I - &FunctionTypes[0]);
 361
 362   // Check the module level types now...
 363   I = find(ModuleTypes.begin(), ModuleTypes.end(), Ty);
 364   if (I == ModuleTypes.end())
 365     error("Didn't find type in ModuleTypes.");
 366   return Type::FirstDerivedTyID + (&*I - &ModuleTypes[0]);
 367 }
 368
 369 /// This is just like getType, but when a compaction table is in use, it is
 370 /// ignored.  It also ignores function level types.
 371 /// @see getType
 372 const Type *BytecodeReader::getGlobalTableType(unsigned Slot) {
 373   if (Slot < Type::FirstDerivedTyID) {
 374     const Type *Ty = Type::getPrimitiveType((Type::TypeID)Slot);
 375     if (!Ty)
 376       error("Not a primitive type ID?");
 377     return Ty;
 378   }
 379   Slot -= Type::FirstDerivedTyID;
 380   if (Slot >= ModuleTypes.size())
 381     error("Illegal compaction table type reference!");
 382   return ModuleTypes[Slot];
 383 }
 384
 385 /// This is just like getTypeSlot, but when a compaction table is in use, it
 386 /// is ignored. It also ignores function level types.
 387 unsigned BytecodeReader::getGlobalTableTypeSlot(const Type *Ty) {
 388   if (Ty->isPrimitiveType())
 389     return Ty->getTypeID();
 390   TypeListTy::iterator I = find(ModuleTypes.begin(),
 391                                       ModuleTypes.end(), Ty);
 392   if (I == ModuleTypes.end())
 393     error("Didn't find type in ModuleTypes.");
 394   return Type::FirstDerivedTyID + (&*I - &ModuleTypes[0]);
 395 }
 396
 397 /// Retrieve a value of a given type and slot number, possibly creating
 398 /// it if it doesn't already exist.
 399 Value * BytecodeReader::getValue(unsigned type, unsigned oNum, bool Create) {
 400   assert(type != Type::LabelTyID && "getValue() cannot get blocks!");
 401   unsigned Num = oNum;
 402
 403   // If there is a compaction table active, it defines the low-level numbers.
 404   // If not, the module values define the low-level numbers.
 405   if (CompactionValues.size() > type && !CompactionValues[type].empty()) {
 406     if (Num < CompactionValues[type].size())
 407       return CompactionValues[type][Num];
 408     Num -= CompactionValues[type].size();
 409   } else {
 410     // By default, the global type id is the type id passed in
 411     unsigned GlobalTyID = type;
 412
 413     // If the type plane was compactified, figure out the global type ID
 414     // by adding the derived type ids and the distance.
 415     if (!CompactionTypes.empty() && type >= Type::FirstDerivedTyID) {
 416       const Type *Ty = CompactionTypes[type-Type::FirstDerivedTyID];
 417       TypeListTy::iterator I =
 418         find(ModuleTypes.begin(), ModuleTypes.end(), Ty);
 419       assert(I != ModuleTypes.end());
 420       GlobalTyID = Type::FirstDerivedTyID + (&*I - &ModuleTypes[0]);
 421     }
 422
 423     if (hasImplicitNull(GlobalTyID)) {
 424       if (Num == 0)
 425         return Constant::getNullValue(getType(type));
 426       --Num;
 427     }
 428
 429     if (GlobalTyID < ModuleValues.size() && ModuleValues[GlobalTyID]) {
 430       if (Num < ModuleValues[GlobalTyID]->size())
 431         return ModuleValues[GlobalTyID]->getOperand(Num);
 432       Num -= ModuleValues[GlobalTyID]->size();
 433     }
 434   }
 435
 436   if (FunctionValues.size() > type &&
 437       FunctionValues[type] &&
 438       Num < FunctionValues[type]->size())
 439     return FunctionValues[type]->getOperand(Num);
 440
 441   if (!Create) return 0;  // Do not create a placeholder?
 442
 443   std::pair<unsigned,unsigned> KeyValue(type, oNum);
 444   ForwardReferenceMap::iterator I = ForwardReferences.lower_bound(KeyValue);
 445   if (I != ForwardReferences.end() && I->first == KeyValue)
 446     return I->second;   // We have already created this placeholder
 447
 448   Value *Val = new Argument(getType(type));
 449   ForwardReferences.insert(I, std::make_pair(KeyValue, Val));
 450   return Val;
 451 }
 452
 453 /// This is just like getValue, but when a compaction table is in use, it
 454 /// is ignored.  Also, no forward references or other fancy features are
 455 /// supported.
 456 Value* BytecodeReader::getGlobalTableValue(const Type *Ty, unsigned SlotNo) {
 457   // FIXME: getTypeSlot is inefficient!
 458   unsigned TyID = getGlobalTableTypeSlot(Ty);
 459
 460   if (TyID != Type::LabelTyID) {
 461     if (SlotNo == 0)
 462       return Constant::getNullValue(Ty);
 463     --SlotNo;
 464   }
 465
 466   if (TyID >= ModuleValues.size() || ModuleValues[TyID] == 0 ||
 467       SlotNo >= ModuleValues[TyID]->size()) {
 468     error("Corrupt compaction table entry!"
 469         + utostr(TyID) + ", " + utostr(SlotNo) + ": "
 470         + utostr(ModuleValues.size()) + ", "
 471         + utohexstr(intptr_t((void*)ModuleValues[TyID])) + ", "
 472         + utostr(ModuleValues[TyID]->size()));
 473   }
 474   return ModuleValues[TyID]->getOperand(SlotNo);
 475 }
 476
 477 /// Just like getValue, except that it returns a null pointer
 478 /// only on error.  It always returns a constant (meaning that if the value is
 479 /// defined, but is not a constant, that is an error).  If the specified
 480 /// constant hasn't been parsed yet, a placeholder is defined and used.
 481 /// Later, after the real value is parsed, the placeholder is eliminated.
 482 Constant* BytecodeReader::getConstantValue(unsigned TypeSlot, unsigned Slot) {
 483   if (Value *V = getValue(TypeSlot, Slot, false))
 484     if (Constant *C = dyn_cast<Constant>(V))
 485       return C;   // If we already have the value parsed, just return it
 486     else
 487       error("Value for slot " + utostr(Slot) +
 488             " is expected to be a constant!");
 489
 490   const Type *Ty = getType(TypeSlot);
 491   std::pair<const Type*, unsigned> Key(Ty, Slot);
 492   ConstantRefsType::iterator I = ConstantFwdRefs.lower_bound(Key);
 493
 494   if (I != ConstantFwdRefs.end() && I->first == Key) {
 495     return I->second;
 496   } else {
 497     // Create a placeholder for the constant reference and
 498     // keep track of the fact that we have a forward ref to recycle it
 499     Constant *C = new ConstantPlaceHolder(Ty, Slot);
 500
 501     // Keep track of the fact that we have a forward ref to recycle it
 502     ConstantFwdRefs.insert(I, std::make_pair(Key, C));
 503     return C;
 504   }
 505 }
 506
 507 //===----------------------------------------------------------------------===//
 508 // IR Construction Methods
 509 //===----------------------------------------------------------------------===//
 510
 511 /// As values are created, they are inserted into the appropriate place
 512 /// with this method. The ValueTable argument must be one of ModuleValues
 513 /// or FunctionValues data members of this class.
 514 unsigned BytecodeReader::insertValue(Value *Val, unsigned type,
 515                                       ValueTable &ValueTab) {
 516   assert((!isa<Constant>(Val) || !cast<Constant>(Val)->isNullValue()) ||
 517           !hasImplicitNull(type) &&
 518          "Cannot read null values from bytecode!");
 519
 520   if (ValueTab.size() <= type)
 521     ValueTab.resize(type+1);
 522
 523   if (!ValueTab[type]) ValueTab[type] = new ValueList();
 524
 525   ValueTab[type]->push_back(Val);
 526
 527   bool HasOffset = hasImplicitNull(type);
 528   return ValueTab[type]->size()-1 + HasOffset;
 529 }
 530
 531 /// Insert the arguments of a function as new values in the reader.
 532 void BytecodeReader::insertArguments(Function* F) {
 533   const FunctionType *FT = F->getFunctionType();
 534   Function::aiterator AI = F->abegin();
 535   for (FunctionType::param_iterator It = FT->param_begin();
 536        It != FT->param_end(); ++It, ++AI)
 537     insertValue(AI, getTypeSlot(AI->getType()), FunctionValues);
 538 }
 539
 540 //===----------------------------------------------------------------------===//
 541 // Bytecode Parsing Methods
 542 //===----------------------------------------------------------------------===//
 543
 544 /// This method parses a single instruction. The instruction is
 545 /// inserted at the end of the \p BB provided. The arguments of
 546 /// the instruction are provided in the \p Args vector.
 547 void BytecodeReader::ParseInstruction(std::vector<unsigned> &Oprnds,
 548                                       BasicBlock* BB) {
 549   BufPtr SaveAt = At;
 550
 551   // Clear instruction data
 552   Oprnds.clear();
 553   unsigned iType = 0;
 554   unsigned Opcode = 0;
 555   unsigned Op = read_uint();
 556
 557   // bits   Instruction format:        Common to all formats
 558   // --------------------------
 559   // 01-00: Opcode type, fixed to 1.
 560   // 07-02: Opcode
 561   Opcode    = (Op >> 2) & 63;
 562   Oprnds.resize((Op >> 0) & 03);
 563
 564   // Extract the operands
 565   switch (Oprnds.size()) {
 566   case 1:
 567     // bits   Instruction format:
 568     // --------------------------
 569     // 19-08: Resulting type plane
 570     // 31-20: Operand #1 (if set to (2^12-1), then zero operands)
 571     //
 572     iType   = (Op >>  8) & 4095;
 573     Oprnds[0] = (Op >> 20) & 4095;
 574     if (Oprnds[0] == 4095)    // Handle special encoding for 0 operands...
 575       Oprnds.resize(0);
 576     break;
 577   case 2:
 578     // bits   Instruction format:
 579     // --------------------------
 580     // 15-08: Resulting type plane
 581     // 23-16: Operand #1
 582     // 31-24: Operand #2
 583     //
 584     iType   = (Op >>  8) & 255;
 585     Oprnds[0] = (Op >> 16) & 255;
 586     Oprnds[1] = (Op >> 24) & 255;
 587     break;
 588   case 3:
 589     // bits   Instruction format:
 590     // --------------------------
 591     // 13-08: Resulting type plane
 592     // 19-14: Operand #1
 593     // 25-20: Operand #2
 594     // 31-26: Operand #3
 595     //
 596     iType   = (Op >>  8) & 63;
 597     Oprnds[0] = (Op >> 14) & 63;
 598     Oprnds[1] = (Op >> 20) & 63;
 599     Oprnds[2] = (Op >> 26) & 63;
 600     break;
 601   case 0:
 602     At -= 4;  // Hrm, try this again...
 603     Opcode = read_vbr_uint();
 604     Opcode >>= 2;
 605     iType = read_vbr_uint();
 606
 607     unsigned NumOprnds = read_vbr_uint();
 608     Oprnds.resize(NumOprnds);
 609
 610     if (NumOprnds == 0)
 611       error("Zero-argument instruction found; this is invalid.");
 612
 613     for (unsigned i = 0; i != NumOprnds; ++i)
 614       Oprnds[i] = read_vbr_uint();
 615     align32();
 616     break;
 617   }
 618
 619   const Type *InstTy = getSanitizedType(iType);
 620
 621   // We have enough info to inform the handler now.
 622   if (Handler) Handler->handleInstruction(Opcode, InstTy, Oprnds, At-SaveAt);
 623
 624   // Declare the resulting instruction we'll build.
 625   Instruction *Result = 0;
 626
 627   // Handle binary operators
 628   if (Opcode >= Instruction::BinaryOpsBegin &&
 629       Opcode <  Instruction::BinaryOpsEnd  && Oprnds.size() == 2)
 630     Result = BinaryOperator::create((Instruction::BinaryOps)Opcode,
 631                                     getValue(iType, Oprnds[0]),
 632                                     getValue(iType, Oprnds[1]));
 633
 634   switch (Opcode) {
 635   default:
 636     if (Result == 0)
 637       error("Illegal instruction read!");
 638     break;
 639   case Instruction::VAArg:
 640     Result = new VAArgInst(getValue(iType, Oprnds[0]),
 641                            getSanitizedType(Oprnds[1]));
 642     break;
 643   case Instruction::VANext:
 644     Result = new VANextInst(getValue(iType, Oprnds[0]),
 645                             getSanitizedType(Oprnds[1]));
 646     break;
 647   case Instruction::Cast:
 648     Result = new CastInst(getValue(iType, Oprnds[0]),
 649                           getSanitizedType(Oprnds[1]));
 650     break;
 651   case Instruction::Select:
 652     Result = new SelectInst(getValue(Type::BoolTyID, Oprnds[0]),
 653                             getValue(iType, Oprnds[1]),
 654                             getValue(iType, Oprnds[2]));
 655     break;
 656   case Instruction::PHI: {
 657     if (Oprnds.size() == 0 || (Oprnds.size() & 1))
 658       error("Invalid phi node encountered!");
 659
 660     PHINode *PN = new PHINode(InstTy);
 661     PN->op_reserve(Oprnds.size());
 662     for (unsigned i = 0, e = Oprnds.size(); i != e; i += 2)
 663       PN->addIncoming(getValue(iType, Oprnds[i]), getBasicBlock(Oprnds[i+1]));
 664     Result = PN;
 665     break;
 666   }
 667
 668   case Instruction::Shl:
 669   case Instruction::Shr:
 670     Result = new ShiftInst((Instruction::OtherOps)Opcode,
 671                            getValue(iType, Oprnds[0]),
 672                            getValue(Type::UByteTyID, Oprnds[1]));
 673     break;
 674   case Instruction::Ret:
 675     if (Oprnds.size() == 0)
 676       Result = new ReturnInst();
 677     else if (Oprnds.size() == 1)
 678       Result = new ReturnInst(getValue(iType, Oprnds[0]));
 679     else
 680       error("Unrecognized instruction!");
 681     break;
 682
 683   case Instruction::Br:
 684     if (Oprnds.size() == 1)
 685       Result = new BranchInst(getBasicBlock(Oprnds[0]));
 686     else if (Oprnds.size() == 3)
 687       Result = new BranchInst(getBasicBlock(Oprnds[0]),
 688           getBasicBlock(Oprnds[1]), getValue(Type::BoolTyID , Oprnds[2]));
 689     else
 690       error("Invalid number of operands for a 'br' instruction!");
 691     break;
 692   case Instruction::Switch: {
 693     if (Oprnds.size() & 1)
 694       error("Switch statement with odd number of arguments!");
 695
 696     SwitchInst *I = new SwitchInst(getValue(iType, Oprnds[0]),
 697                                    getBasicBlock(Oprnds[1]));
 698     for (unsigned i = 2, e = Oprnds.size(); i != e; i += 2)
 699       I->addCase(cast<Constant>(getValue(iType, Oprnds[i])),
 700                  getBasicBlock(Oprnds[i+1]));
 701     Result = I;
 702     break;
 703   }
 704
 705   case Instruction::Call: {
 706     if (Oprnds.size() == 0)
 707       error("Invalid call instruction encountered!");
 708
 709     Value *F = getValue(iType, Oprnds[0]);
 710
 711     // Check to make sure we have a pointer to function type
 712     const PointerType *PTy = dyn_cast<PointerType>(F->getType());
 713     if (PTy == 0) error("Call to non function pointer value!");
 714     const FunctionType *FTy = dyn_cast<FunctionType>(PTy->getElementType());
 715     if (FTy == 0) error("Call to non function pointer value!");
 716
 717     std::vector<Value *> Params;
 718     if (!FTy->isVarArg()) {
 719       FunctionType::param_iterator It = FTy->param_begin();
 720
 721       for (unsigned i = 1, e = Oprnds.size(); i != e; ++i) {
 722         if (It == FTy->param_end())
 723           error("Invalid call instruction!");
 724         Params.push_back(getValue(getTypeSlot(*It++), Oprnds[i]));
 725       }
 726       if (It != FTy->param_end())
 727         error("Invalid call instruction!");
 728     } else {
 729       Oprnds.erase(Oprnds.begin(), Oprnds.begin()+1);
 730
 731       unsigned FirstVariableOperand;
 732       if (Oprnds.size() < FTy->getNumParams())
 733         error("Call instruction missing operands!");
 734
 735       // Read all of the fixed arguments
 736       for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
 737         Params.push_back(getValue(getTypeSlot(FTy->getParamType(i)),Oprnds[i]));
 738
 739       FirstVariableOperand = FTy->getNumParams();
 740
 741       if ((Oprnds.size()-FirstVariableOperand) & 1) // Must be pairs of type/value
 742         error("Invalid call instruction!");
 743
 744       for (unsigned i = FirstVariableOperand, e = Oprnds.size();
 745            i != e; i += 2)
 746         Params.push_back(getValue(Oprnds[i], Oprnds[i+1]));
 747     }
 748
 749     Result = new CallInst(F, Params);
 750     break;
 751   }
 752   case Instruction::Invoke: {
 753     if (Oprnds.size() < 3)
 754       error("Invalid invoke instruction!");
 755     Value *F = getValue(iType, Oprnds[0]);
 756
 757     // Check to make sure we have a pointer to function type
 758     const PointerType *PTy = dyn_cast<PointerType>(F->getType());
 759     if (PTy == 0)
 760       error("Invoke to non function pointer value!");
 761     const FunctionType *FTy = dyn_cast<FunctionType>(PTy->getElementType());
 762     if (FTy == 0)
 763       error("Invoke to non function pointer value!");
 764
 765     std::vector<Value *> Params;
 766     BasicBlock *Normal, *Except;
 767
 768     if (!FTy->isVarArg()) {
 769       Normal = getBasicBlock(Oprnds[1]);
 770       Except = getBasicBlock(Oprnds[2]);
 771
 772       FunctionType::param_iterator It = FTy->param_begin();
 773       for (unsigned i = 3, e = Oprnds.size(); i != e; ++i) {
 774         if (It == FTy->param_end())
 775           error("Invalid invoke instruction!");
 776         Params.push_back(getValue(getTypeSlot(*It++), Oprnds[i]));
 777       }
 778       if (It != FTy->param_end())
 779         error("Invalid invoke instruction!");
 780     } else {
 781       Oprnds.erase(Oprnds.begin(), Oprnds.begin()+1);
 782
 783       Normal = getBasicBlock(Oprnds[0]);
 784       Except = getBasicBlock(Oprnds[1]);
 785
 786       unsigned FirstVariableArgument = FTy->getNumParams()+2;
 787       for (unsigned i = 2; i != FirstVariableArgument; ++i)
 788         Params.push_back(getValue(getTypeSlot(FTy->getParamType(i-2)),
 789                                   Oprnds[i]));
 790
 791       if (Oprnds.size()-FirstVariableArgument & 1) // Must be type/value pairs
 792         error("Invalid invoke instruction!");
 793
 794       for (unsigned i = FirstVariableArgument; i < Oprnds.size(); i += 2)
 795         Params.push_back(getValue(Oprnds[i], Oprnds[i+1]));
 796     }
 797
 798     Result = new InvokeInst(F, Normal, Except, Params);
 799     break;
 800   }
 801   case Instruction::Malloc:
 802     if (Oprnds.size() > 2)
 803       error("Invalid malloc instruction!");
 804     if (!isa<PointerType>(InstTy))
 805       error("Invalid malloc instruction!");
 806
 807     Result = new MallocInst(cast<PointerType>(InstTy)->getElementType(),
 808                             Oprnds.size() ? getValue(Type::UIntTyID,
 809                                                    Oprnds[0]) : 0);
 810     break;
 811
 812   case Instruction::Alloca:
 813     if (Oprnds.size() > 2)
 814       error("Invalid alloca instruction!");
 815     if (!isa<PointerType>(InstTy))
 816       error("Invalid alloca instruction!");
 817
 818     Result = new AllocaInst(cast<PointerType>(InstTy)->getElementType(),
 819                             Oprnds.size() ? getValue(Type::UIntTyID,
 820                             Oprnds[0]) :0);
 821     break;
 822   case Instruction::Free:
 823     if (!isa<PointerType>(InstTy))
 824       error("Invalid free instruction!");
 825     Result = new FreeInst(getValue(iType, Oprnds[0]));
 826     break;
 827   case Instruction::GetElementPtr: {
 828     if (Oprnds.size() == 0 || !isa<PointerType>(InstTy))
 829       error("Invalid getelementptr instruction!");
 830
 831     std::vector<Value*> Idx;
 832
 833     const Type *NextTy = InstTy;
 834     for (unsigned i = 1, e = Oprnds.size(); i != e; ++i) {
 835       const CompositeType *TopTy = dyn_cast_or_null<CompositeType>(NextTy);
 836       if (!TopTy)
 837         error("Invalid getelementptr instruction!");
 838
 839       unsigned ValIdx = Oprnds[i];
 840       unsigned IdxTy = 0;
 841       if (!hasRestrictedGEPTypes) {
 842         // Struct indices are always uints, sequential type indices can be any
 843         // of the 32 or 64-bit integer types.  The actual choice of type is
 844         // encoded in the low two bits of the slot number.
 845         if (isa<StructType>(TopTy))
 846           IdxTy = Type::UIntTyID;
 847         else {
 848           switch (ValIdx & 3) {
 849           default:
 850           case 0: IdxTy = Type::UIntTyID; break;
 851           case 1: IdxTy = Type::IntTyID; break;
 852           case 2: IdxTy = Type::ULongTyID; break;
 853           case 3: IdxTy = Type::LongTyID; break;
 854           }
 855           ValIdx >>= 2;
 856         }
 857       } else {
 858         IdxTy = isa<StructType>(TopTy) ? Type::UByteTyID : Type::LongTyID;
 859       }
 860
 861       Idx.push_back(getValue(IdxTy, ValIdx));
 862
 863       // Convert ubyte struct indices into uint struct indices.
 864       if (isa<StructType>(TopTy) && hasRestrictedGEPTypes)
 865         if (ConstantUInt *C = dyn_cast<ConstantUInt>(Idx.back()))
 866           Idx[Idx.size()-1] = ConstantExpr::getCast(C, Type::UIntTy);
 867
 868       NextTy = GetElementPtrInst::getIndexedType(InstTy, Idx, true);
 869     }
 870
 871     Result = new GetElementPtrInst(getValue(iType, Oprnds[0]), Idx);
 872     break;
 873   }
 874
 875   case 62:   // volatile load
 876   case Instruction::Load:
 877     if (Oprnds.size() != 1 || !isa<PointerType>(InstTy))
 878       error("Invalid load instruction!");
 879     Result = new LoadInst(getValue(iType, Oprnds[0]), "", Opcode == 62);
 880     break;
 881
 882   case 63:   // volatile store
 883   case Instruction::Store: {
 884     if (!isa<PointerType>(InstTy) || Oprnds.size() != 2)
 885       error("Invalid store instruction!");
 886
 887     Value *Ptr = getValue(iType, Oprnds[1]);
 888     const Type *ValTy = cast<PointerType>(Ptr->getType())->getElementType();
 889     Result = new StoreInst(getValue(getTypeSlot(ValTy), Oprnds[0]), Ptr,
 890                            Opcode == 63);
 891     break;
 892   }
 893   case Instruction::Unwind:
 894     if (Oprnds.size() != 0)
 895       error("Invalid unwind instruction!");
 896     Result = new UnwindInst();
 897     break;
 898   }  // end switch(Opcode)
 899
 900   unsigned TypeSlot;
 901   if (Result->getType() == InstTy)
 902     TypeSlot = iType;
 903   else
 904     TypeSlot = getTypeSlot(Result->getType());
 905
 906   insertValue(Result, TypeSlot, FunctionValues);
 907   BB->getInstList().push_back(Result);
 908 }
 909
 910 /// Get a particular numbered basic block, which might be a forward reference.
 911 /// This works together with ParseBasicBlock to handle these forward references
 912 /// in a clean manner.  This function is used when constructing phi, br, switch,
 913 /// and other instructions that reference basic blocks. Blocks are numbered
 914 /// sequentially as they appear in the function.
 915 BasicBlock *BytecodeReader::getBasicBlock(unsigned ID) {
 916   // Make sure there is room in the table...
 917   if (ParsedBasicBlocks.size() <= ID) ParsedBasicBlocks.resize(ID+1);
 918
 919   // First check to see if this is a backwards reference, i.e., ParseBasicBlock
 920   // has already created this block, or if the forward reference has already
 921   // been created.
 922   if (ParsedBasicBlocks[ID])
 923     return ParsedBasicBlocks[ID];
 924
 925   // Otherwise, the basic block has not yet been created.  Do so and add it to
 926   // the ParsedBasicBlocks list.
 927   return ParsedBasicBlocks[ID] = new BasicBlock();
 928 }
 929
 930 /// In LLVM 1.0 bytecode files, we used to output one basicblock at a time.
 931 /// This method reads in one of the basicblock packets. This method is not used
 932 /// for bytecode files after LLVM 1.0
 933 /// @returns The basic block constructed.
 934 BasicBlock *BytecodeReader::ParseBasicBlock(unsigned BlockNo) {
 935   if (Handler) Handler->handleBasicBlockBegin(BlockNo);
 936
 937   BasicBlock *BB = 0;
 938
 939   if (ParsedBasicBlocks.size() == BlockNo)
 940     ParsedBasicBlocks.push_back(BB = new BasicBlock());
 941   else if (ParsedBasicBlocks[BlockNo] == 0)
 942     BB = ParsedBasicBlocks[BlockNo] = new BasicBlock();
 943   else
 944     BB = ParsedBasicBlocks[BlockNo];
 945
 946   std::vector<unsigned> Operands;
 947   while (moreInBlock())
 948     ParseInstruction(Operands, BB);
 949
 950   if (Handler) Handler->handleBasicBlockEnd(BlockNo);
 951   return BB;
 952 }
 953
 954 /// Parse all of the BasicBlock's & Instruction's in the body of a function.
 955 /// In post 1.0 bytecode files, we no longer emit basic block individually,
 956 /// in order to avoid per-basic-block overhead.
 957 /// @returns Rhe number of basic blocks encountered.
 958 unsigned BytecodeReader::ParseInstructionList(Function* F) {
 959   unsigned BlockNo = 0;
 960   std::vector<unsigned> Args;
 961
 962   while (moreInBlock()) {
 963     if (Handler) Handler->handleBasicBlockBegin(BlockNo);
 964     BasicBlock *BB;
 965     if (ParsedBasicBlocks.size() == BlockNo)
 966       ParsedBasicBlocks.push_back(BB = new BasicBlock());
 967     else if (ParsedBasicBlocks[BlockNo] == 0)
 968       BB = ParsedBasicBlocks[BlockNo] = new BasicBlock();
 969     else
 970       BB = ParsedBasicBlocks[BlockNo];
 971     ++BlockNo;
 972     F->getBasicBlockList().push_back(BB);
 973
 974     // Read instructions into this basic block until we get to a terminator
 975     while (moreInBlock() && !BB->getTerminator())
 976       ParseInstruction(Args, BB);
 977
 978     if (!BB->getTerminator())
 979       error("Non-terminated basic block found!");
 980
 981     if (Handler) Handler->handleBasicBlockEnd(BlockNo-1);
 982   }
 983
 984   return BlockNo;
 985 }
 986
 987 /// Parse a symbol table. This works for both module level and function
 988 /// level symbol tables.  For function level symbol tables, the CurrentFunction
 989 /// parameter must be non-zero and the ST parameter must correspond to
 990 /// CurrentFunction's symbol table. For Module level symbol tables, the
 991 /// CurrentFunction argument must be zero.
 992 void BytecodeReader::ParseSymbolTable(Function *CurrentFunction,
 993                                       SymbolTable *ST) {
 994   if (Handler) Handler->handleSymbolTableBegin(CurrentFunction,ST);
 995
 996   // Allow efficient basic block lookup by number.
 997   std::vector<BasicBlock*> BBMap;
 998   if (CurrentFunction)
 999     for (Function::iterator I = CurrentFunction->begin(),
1000            E = CurrentFunction->end(); I != E; ++I)
1001       BBMap.push_back(I);
1002
1003   /// In LLVM 1.3 we write types separately from values so
1004   /// The types are always first in the symbol table. This is
1005   /// because Type no longer derives from Value.
1006   if (!hasTypeDerivedFromValue) {
1007     // Symtab block header: [num entries]
1008     unsigned NumEntries = read_vbr_uint();
1009     for (unsigned i = 0; i < NumEntries; ++i) {
1010       // Symtab entry: [def slot #][name]
1011       unsigned slot = read_vbr_uint();
1012       std::string Name = read_str();
1013       const Type* T = getType(slot);
1014       ST->insert(Name, T);
1015     }
1016   }
1017
1018   while (moreInBlock()) {
1019     // Symtab block header: [num entries][type id number]
1020     unsigned NumEntries = read_vbr_uint();
1021     unsigned Typ = 0;
1022     bool isTypeType = read_typeid(Typ);
1023     const Type *Ty = getType(Typ);
1024
1025     for (unsigned i = 0; i != NumEntries; ++i) {
1026       // Symtab entry: [def slot #][name]
1027       unsigned slot = read_vbr_uint();
1028       std::string Name = read_str();
1029
1030       // if we're reading a pre 1.3 bytecode file and the type plane
1031       // is the "type type", handle it here
1032       if (isTypeType) {
1033         const Type* T = getType(slot);
1034         if (T == 0)
1035           error("Failed type look-up for name '" + Name + "'");
1036         ST->insert(Name, T);
1037         continue; // code below must be short circuited
1038       } else {
1039         Value *V = 0;
1040         if (Typ == Type::LabelTyID) {
1041           if (slot < BBMap.size())
1042             V = BBMap[slot];
1043         } else {
1044           V = getValue(Typ, slot, false); // Find mapping...
1045         }
1046         if (V == 0)
1047           error("Failed value look-up for name '" + Name + "'");
1048         V->setName(Name, ST);
1049       }
1050     }
1051   }
1052   checkPastBlockEnd("Symbol Table");
1053   if (Handler) Handler->handleSymbolTableEnd();
1054 }
1055
1056 /// Read in the types portion of a compaction table.
1057 void BytecodeReader::ParseCompactionTypes(unsigned NumEntries) {
1058   for (unsigned i = 0; i != NumEntries; ++i) {
1059     unsigned TypeSlot = 0;
1060     if (read_typeid(TypeSlot))
1061       error("Invalid type in compaction table: type type");
1062     const Type *Typ = getGlobalTableType(TypeSlot);
1063     CompactionTypes.push_back(Typ);
1064     if (Handler) Handler->handleCompactionTableType(i, TypeSlot, Typ);
1065   }
1066 }
1067
1068 /// Parse a compaction table.
1069 void BytecodeReader::ParseCompactionTable() {
1070
1071   // Notify handler that we're beginning a compaction table.
1072   if (Handler) Handler->handleCompactionTableBegin();
1073
1074   // In LLVM 1.3 Type no longer derives from Value. So,
1075   // we always write them first in the compaction table
1076   // because they can't occupy a "type plane" where the
1077   // Values reside.
1078   if (! hasTypeDerivedFromValue) {
1079     unsigned NumEntries = read_vbr_uint();
1080     ParseCompactionTypes(NumEntries);
1081   }
1082
1083   // Compaction tables live in separate blocks so we have to loop
1084   // until we've read the whole thing.
1085   while (moreInBlock()) {
1086     // Read the number of Value* entries in the compaction table
1087     unsigned NumEntries = read_vbr_uint();
1088     unsigned Ty = 0;
1089     unsigned isTypeType = false;
1090
1091     // Decode the type from value read in. Most compaction table
1092     // planes will have one or two entries in them. If that's the
1093     // case then the length is encoded in the bottom two bits and
1094     // the higher bits encode the type. This saves another VBR value.
1095     if ((NumEntries & 3) == 3) {
1096       // In this case, both low-order bits are set (value 3). This
1097       // is a signal that the typeid follows.
1098       NumEntries >>= 2;
1099       isTypeType = read_typeid(Ty);
1100     } else {
1101       // In this case, the low-order bits specify the number of entries
1102       // and the high order bits specify the type.
1103       Ty = NumEntries >> 2;
1104       isTypeType = sanitizeTypeId(Ty);
1105       NumEntries &= 3;
1106     }
1107
1108     // if we're reading a pre 1.3 bytecode file and the type plane
1109     // is the "type type", handle it here
1110     if (isTypeType) {
1111       ParseCompactionTypes(NumEntries);
1112     } else {
1113       // Make sure we have enough room  for the plane
1114       if (Ty >= CompactionValues.size())
1115         CompactionValues.resize(Ty+1);
1116
1117       // Make sure the plane is empty or we have some kind of error
1118       if (!CompactionValues[Ty].empty())
1119         error("Compaction table plane contains multiple entries!");
1120
1121       // Notify handler about the plane
1122       if (Handler) Handler->handleCompactionTablePlane(Ty, NumEntries);
1123
1124       // Convert the type slot to a type
1125       const Type *Typ = getType(Ty);
1126
1127       // Push the implicit zero
1128       CompactionValues[Ty].push_back(Constant::getNullValue(Typ));
1129
1130       // Read in each of the entries, put them in the compaction table
1131       // and notify the handler that we have a new compaction table value.
1132       for (unsigned i = 0; i != NumEntries; ++i) {
1133         unsigned ValSlot = read_vbr_uint();
1134         Value *V = getGlobalTableValue(Typ, ValSlot);
1135         CompactionValues[Ty].push_back(V);
1136         if (Handler) Handler->handleCompactionTableValue(i, Ty, ValSlot, Typ);
1137       }
1138     }
1139   }
1140   // Notify handler that the compaction table is done.
1141   if (Handler) Handler->handleCompactionTableEnd();
1142 }
1143
1144 // Parse a single type. The typeid is read in first. If its a primitive type
1145 // then nothing else needs to be read, we know how to instantiate it. If its
1146 // a derived type, then additional data is read to fill out the type
1147 // definition.
1148 const Type *BytecodeReader::ParseType() {
1149   unsigned PrimType = 0;
1150   if (read_typeid(PrimType))
1151     error("Invalid type (type type) in type constants!");
1152
1153   const Type *Result = 0;
1154   if ((Result = Type::getPrimitiveType((Type::TypeID)PrimType)))
1155     return Result;
1156
1157   switch (PrimType) {
1158   case Type::FunctionTyID: {
1159     const Type *RetType = readSanitizedType();
1160
1161     unsigned NumParams = read_vbr_uint();
1162
1163     std::vector<const Type*> Params;
1164     while (NumParams--)
1165       Params.push_back(readSanitizedType());
1166
1167     bool isVarArg = Params.size() && Params.back() == Type::VoidTy;
1168     if (isVarArg) Params.pop_back();
1169
1170     Result = FunctionType::get(RetType, Params, isVarArg);
1171     break;
1172   }
1173   case Type::ArrayTyID: {
1174     const Type *ElementType = readSanitizedType();
1175     unsigned NumElements = read_vbr_uint();
1176     Result =  ArrayType::get(ElementType, NumElements);
1177     break;
1178   }
1179   case Type::StructTyID: {
1180     std::vector<const Type*> Elements;
1181     unsigned Typ = 0;
1182     if (read_typeid(Typ))
1183       error("Invalid element type (type type) for structure!");
1184
1185     while (Typ) {         // List is terminated by void/0 typeid
1186       Elements.push_back(getType(Typ));
1187       if (read_typeid(Typ))
1188         error("Invalid element type (type type) for structure!");
1189     }
1190
1191     Result = StructType::get(Elements);
1192     break;
1193   }
1194   case Type::PointerTyID: {
1195     Result = PointerType::get(readSanitizedType());
1196     break;
1197   }
1198
1199   case Type::OpaqueTyID: {
1200     Result = OpaqueType::get();
1201     break;
1202   }
1203
1204   default:
1205     error("Don't know how to deserialize primitive type " + utostr(PrimType));
1206     break;
1207   }
1208   if (Handler) Handler->handleType(Result);
1209   return Result;
1210 }
1211
1212 // ParseType - We have to use this weird code to handle recursive
1213 // types.  We know that recursive types will only reference the current slab of
1214 // values in the type plane, but they can forward reference types before they
1215 // have been read.  For example, Type #0 might be '{ Ty#1 }' and Type #1 might
1216 // be 'Ty#0*'.  When reading Type #0, type number one doesn't exist.  To fix
1217 // this ugly problem, we pessimistically insert an opaque type for each type we
1218 // are about to read.  This means that forward references will resolve to
1219 // something and when we reread the type later, we can replace the opaque type
1220 // with a new resolved concrete type.
1221 //
1222 void BytecodeReader::ParseTypes(TypeListTy &Tab, unsigned NumEntries){
1223   assert(Tab.size() == 0 && "should not have read type constants in before!");
1224
1225   // Insert a bunch of opaque types to be resolved later...
1226   Tab.reserve(NumEntries);
1227   for (unsigned i = 0; i != NumEntries; ++i)
1228     Tab.push_back(OpaqueType::get());
1229
1230   // Loop through reading all of the types.  Forward types will make use of the
1231   // opaque types just inserted.
1232   //
1233   for (unsigned i = 0; i != NumEntries; ++i) {
1234     const Type* NewTy = ParseType();
1235     const Type* OldTy = Tab[i].get();
1236     if (NewTy == 0)
1237       error("Couldn't parse type!");
1238
1239     // Don't directly push the new type on the Tab. Instead we want to replace
1240     // the opaque type we previously inserted with the new concrete value. This
1241     // approach helps with forward references to types. The refinement from the
1242     // abstract (opaque) type to the new type causes all uses of the abstract
1243     // type to use the concrete type (NewTy). This will also cause the opaque
1244     // type to be deleted.
1245     cast<DerivedType>(const_cast<Type*>(OldTy))->refineAbstractTypeTo(NewTy);
1246
1247     // This should have replaced the old opaque type with the new type in the
1248     // value table... or with a preexisting type that was already in the system.
1249     // Let's just make sure it did.
1250     assert(Tab[i] != OldTy && "refineAbstractType didn't work!");
1251   }
1252 }
1253
1254 /// Parse a single constant value
1255 Constant *BytecodeReader::ParseConstantValue(unsigned TypeID) {
1256   // We must check for a ConstantExpr before switching by type because
1257   // a ConstantExpr can be of any type, and has no explicit value.
1258   //
1259   // 0 if not expr; numArgs if is expr
1260   unsigned isExprNumArgs = read_vbr_uint();
1261
1262   if (isExprNumArgs) {
1263     // FIXME: Encoding of constant exprs could be much more compact!
1264     std::vector<Constant*> ArgVec;
1265     ArgVec.reserve(isExprNumArgs);
1266     unsigned Opcode = read_vbr_uint();
1267
1268     // Read the slot number and types of each of the arguments
1269     for (unsigned i = 0; i != isExprNumArgs; ++i) {
1270       unsigned ArgValSlot = read_vbr_uint();
1271       unsigned ArgTypeSlot = 0;
1272       if (read_typeid(ArgTypeSlot))
1273         error("Invalid argument type (type type) for constant value");
1274
1275       // Get the arg value from its slot if it exists, otherwise a placeholder
1276       ArgVec.push_back(getConstantValue(ArgTypeSlot, ArgValSlot));
1277     }
1278
1279     // Construct a ConstantExpr of the appropriate kind
1280     if (isExprNumArgs == 1) {           // All one-operand expressions
1281       if (Opcode != Instruction::Cast)
1282         error("Only Cast instruction has one argument for ConstantExpr");
1283
1284       Constant* Result = ConstantExpr::getCast(ArgVec[0], getType(TypeID));
1285       if (Handler) Handler->handleConstantExpression(Opcode, ArgVec, Result);
1286       return Result;
1287     } else if (Opcode == Instruction::GetElementPtr) { // GetElementPtr
1288       std::vector<Constant*> IdxList(ArgVec.begin()+1, ArgVec.end());
1289
1290       if (hasRestrictedGEPTypes) {
1291         const Type *BaseTy = ArgVec[0]->getType();
1292         generic_gep_type_iterator<std::vector<Constant*>::iterator>
1293           GTI = gep_type_begin(BaseTy, IdxList.begin(), IdxList.end()),
1294           E = gep_type_end(BaseTy, IdxList.begin(), IdxList.end());
1295         for (unsigned i = 0; GTI != E; ++GTI, ++i)
1296           if (isa<StructType>(*GTI)) {
1297             if (IdxList[i]->getType() != Type::UByteTy)
1298               error("Invalid index for getelementptr!");
1299             IdxList[i] = ConstantExpr::getCast(IdxList[i], Type::UIntTy);
1300           }
1301       }
1302
1303       Constant* Result = ConstantExpr::getGetElementPtr(ArgVec[0], IdxList);
1304       if (Handler) Handler->handleConstantExpression(Opcode, ArgVec, Result);
1305       return Result;
1306     } else if (Opcode == Instruction::Select) {
1307       if (ArgVec.size() != 3)
1308         error("Select instruction must have three arguments.");
1309       Constant* Result = ConstantExpr::getSelect(ArgVec[0], ArgVec[1],
1310                                                  ArgVec[2]);
1311       if (Handler) Handler->handleConstantExpression(Opcode, ArgVec, Result);
1312       return Result;
1313     } else {                            // All other 2-operand expressions
1314       Constant* Result = ConstantExpr::get(Opcode, ArgVec[0], ArgVec[1]);
1315       if (Handler) Handler->handleConstantExpression(Opcode, ArgVec, Result);
1316       return Result;
1317     }
1318   }
1319
1320   // Ok, not an ConstantExpr.  We now know how to read the given type...
1321   const Type *Ty = getType(TypeID);
1322   switch (Ty->getTypeID()) {
1323   case Type::BoolTyID: {
1324     unsigned Val = read_vbr_uint();
1325     if (Val != 0 && Val != 1)
1326       error("Invalid boolean value read.");
1327     Constant* Result = ConstantBool::get(Val == 1);
1328     if (Handler) Handler->handleConstantValue(Result);
1329     return Result;
1330   }
1331
1332   case Type::UByteTyID:   // Unsigned integer types...
1333   case Type::UShortTyID:
1334   case Type::UIntTyID: {
1335     unsigned Val = read_vbr_uint();
1336     if (!ConstantUInt::isValueValidForType(Ty, Val))
1337       error("Invalid unsigned byte/short/int read.");
1338     Constant* Result =  ConstantUInt::get(Ty, Val);
1339     if (Handler) Handler->handleConstantValue(Result);
1340     return Result;
1341   }
1342
1343   case Type::ULongTyID: {
1344     Constant* Result = ConstantUInt::get(Ty, read_vbr_uint64());
1345     if (Handler) Handler->handleConstantValue(Result);
1346     return Result;
1347   }
1348
1349   case Type::SByteTyID:   // Signed integer types...
1350   case Type::ShortTyID:
1351   case Type::IntTyID: {
1352   case Type::LongTyID:
1353     int64_t Val = read_vbr_int64();
1354     if (!ConstantSInt::isValueValidForType(Ty, Val))
1355       error("Invalid signed byte/short/int/long read.");
1356     Constant* Result = ConstantSInt::get(Ty, Val);
1357     if (Handler) Handler->handleConstantValue(Result);
1358     return Result;
1359   }
1360
1361   case Type::FloatTyID: {
1362     float Val;
1363     read_float(Val);
1364     Constant* Result = ConstantFP::get(Ty, Val);
1365     if (Handler) Handler->handleConstantValue(Result);
1366     return Result;
1367   }
1368
1369   case Type::DoubleTyID: {
1370     double Val;
1371     read_double(Val);
1372     Constant* Result = ConstantFP::get(Ty, Val);
1373     if (Handler) Handler->handleConstantValue(Result);
1374     return Result;
1375   }
1376
1377   case Type::ArrayTyID: {
1378     const ArrayType *AT = cast<ArrayType>(Ty);
1379     unsigned NumElements = AT->getNumElements();
1380     unsigned TypeSlot = getTypeSlot(AT->getElementType());
1381     std::vector<Constant*> Elements;
1382     Elements.reserve(NumElements);
1383     while (NumElements--)     // Read all of the elements of the constant.
1384       Elements.push_back(getConstantValue(TypeSlot,
1385                                           read_vbr_uint()));
1386     Constant* Result = ConstantArray::get(AT, Elements);
1387     if (Handler) Handler->handleConstantArray(AT, Elements, TypeSlot, Result);
1388     return Result;
1389   }
1390
1391   case Type::StructTyID: {
1392     const StructType *ST = cast<StructType>(Ty);
1393
1394     std::vector<Constant *> Elements;
1395     Elements.reserve(ST->getNumElements());
1396     for (unsigned i = 0; i != ST->getNumElements(); ++i)
1397       Elements.push_back(getConstantValue(ST->getElementType(i),
1398                                           read_vbr_uint()));
1399
1400     Constant* Result = ConstantStruct::get(ST, Elements);
1401     if (Handler) Handler->handleConstantStruct(ST, Elements, Result);
1402     return Result;
1403   }
1404
1405   case Type::PointerTyID: {  // ConstantPointerRef value...
1406     const PointerType *PT = cast<PointerType>(Ty);
1407     unsigned Slot = read_vbr_uint();
1408
1409     // Check to see if we have already read this global variable...
1410     Value *Val = getValue(TypeID, Slot, false);
1411     GlobalValue *GV;
1412     if (Val) {
1413       if (!(GV = dyn_cast<GlobalValue>(Val)))
1414         error("GlobalValue not in ValueTable!");
1415     } else {
1416       error("Forward references are not allowed here.");
1417     }
1418
1419     if (Handler) Handler->handleConstantPointer(PT, Slot, GV );
1420     return GV;
1421   }
1422
1423   default:
1424     error("Don't know how to deserialize constant value of type '" +
1425                       Ty->getDescription());
1426     break;
1427   }
1428   return 0;
1429 }
1430
1431 /// Resolve references for constants. This function resolves the forward
1432 /// referenced constants in the ConstantFwdRefs map. It uses the
1433 /// replaceAllUsesWith method of Value class to substitute the placeholder
1434 /// instance with the actual instance.
1435 void BytecodeReader::ResolveReferencesToConstant(Constant *NewV, unsigned Slot){
1436   ConstantRefsType::iterator I =
1437     ConstantFwdRefs.find(std::make_pair(NewV->getType(), Slot));
1438   if (I == ConstantFwdRefs.end()) return;   // Never forward referenced?
1439
1440   Value *PH = I->second;   // Get the placeholder...
1441   PH->replaceAllUsesWith(NewV);
1442   delete PH;                               // Delete the old placeholder
1443   ConstantFwdRefs.erase(I);                // Remove the map entry for it
1444 }
1445
1446 /// Parse the constant strings section.
1447 void BytecodeReader::ParseStringConstants(unsigned NumEntries, ValueTable &Tab){
1448   for (; NumEntries; --NumEntries) {
1449     unsigned Typ = 0;
1450     if (read_typeid(Typ))
1451       error("Invalid type (type type) for string constant");
1452     const Type *Ty = getType(Typ);
1453     if (!isa<ArrayType>(Ty))
1454       error("String constant data invalid!");
1455
1456     const ArrayType *ATy = cast<ArrayType>(Ty);
1457     if (ATy->getElementType() != Type::SByteTy &&
1458         ATy->getElementType() != Type::UByteTy)
1459       error("String constant data invalid!");
1460
1461     // Read character data.  The type tells us how long the string is.
1462     char Data[ATy->getNumElements()];
1463     read_data(Data, Data+ATy->getNumElements());
1464
1465     std::vector<Constant*> Elements(ATy->getNumElements());
1466     if (ATy->getElementType() == Type::SByteTy)
1467       for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i)
1468         Elements[i] = ConstantSInt::get(Type::SByteTy, (signed char)Data[i]);
1469     else
1470       for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i)
1471         Elements[i] = ConstantUInt::get(Type::UByteTy, (unsigned char)Data[i]);
1472
1473     // Create the constant, inserting it as needed.
1474     Constant *C = ConstantArray::get(ATy, Elements);
1475     unsigned Slot = insertValue(C, Typ, Tab);
1476     ResolveReferencesToConstant(C, Slot);
1477     if (Handler) Handler->handleConstantString(cast<ConstantArray>(C));
1478   }
1479 }
1480
1481 /// Parse the constant pool.
1482 void BytecodeReader::ParseConstantPool(ValueTable &Tab,
1483                                        TypeListTy &TypeTab,
1484                                        bool isFunction) {
1485   if (Handler) Handler->handleGlobalConstantsBegin();
1486
1487   /// In LLVM 1.3 Type does not derive from Value so the types
1488   /// do not occupy a plane. Consequently, we read the types
1489   /// first in the constant pool.
1490   if (isFunction && !hasTypeDerivedFromValue) {
1491     unsigned NumEntries = read_vbr_uint();
1492     ParseTypes(TypeTab, NumEntries);
1493   }
1494
1495   while (moreInBlock()) {
1496     unsigned NumEntries = read_vbr_uint();
1497     unsigned Typ = 0;
1498     bool isTypeType = read_typeid(Typ);
1499
1500     /// In LLVM 1.2 and before, Types were written to the
1501     /// bytecode file in the "Type Type" plane (#12).
1502     /// In 1.3 plane 12 is now the label plane.  Handle this here.
1503     if (isTypeType) {
1504       ParseTypes(TypeTab, NumEntries);
1505     } else if (Typ == Type::VoidTyID) {
1506       /// Use of Type::VoidTyID is a misnomer. It actually means
1507       /// that the following plane is constant strings
1508       assert(&Tab == &ModuleValues && "Cannot read strings in functions!");
1509       ParseStringConstants(NumEntries, Tab);
1510     } else {
1511       for (unsigned i = 0; i < NumEntries; ++i) {
1512         Constant *C = ParseConstantValue(Typ);
1513         assert(C && "ParseConstantValue returned NULL!");
1514         unsigned Slot = insertValue(C, Typ, Tab);
1515
1516         // If we are reading a function constant table, make sure that we adjust
1517         // the slot number to be the real global constant number.
1518         //
1519         if (&Tab != &ModuleValues && Typ < ModuleValues.size() &&
1520             ModuleValues[Typ])
1521           Slot += ModuleValues[Typ]->size();
1522         ResolveReferencesToConstant(C, Slot);
1523       }
1524     }
1525   }
1526   checkPastBlockEnd("Constant Pool");
1527   if (Handler) Handler->handleGlobalConstantsEnd();
1528 }
1529
1530 /// Parse the contents of a function. Note that this function can be
1531 /// called lazily by materializeFunction
1532 /// @see materializeFunction
1533 void BytecodeReader::ParseFunctionBody(Function* F) {
1534
1535   unsigned FuncSize = BlockEnd - At;
1536   GlobalValue::LinkageTypes Linkage = GlobalValue::ExternalLinkage;
1537
1538   unsigned LinkageType = read_vbr_uint();
1539   switch (LinkageType) {
1540   case 0: Linkage = GlobalValue::ExternalLinkage; break;
1541   case 1: Linkage = GlobalValue::WeakLinkage; break;
1542   case 2: Linkage = GlobalValue::AppendingLinkage; break;
1543   case 3: Linkage = GlobalValue::InternalLinkage; break;
1544   case 4: Linkage = GlobalValue::LinkOnceLinkage; break;
1545   default:
1546     error("Invalid linkage type for Function.");
1547     Linkage = GlobalValue::InternalLinkage;
1548     break;
1549   }
1550
1551   F->setLinkage(Linkage);
1552   if (Handler) Handler->handleFunctionBegin(F,FuncSize);
1553
1554   // Keep track of how many basic blocks we have read in...
1555   unsigned BlockNum = 0;
1556   bool InsertedArguments = false;
1557
1558   BufPtr MyEnd = BlockEnd;
1559   while (At < MyEnd) {
1560     unsigned Type, Size;
1561     BufPtr OldAt = At;
1562     read_block(Type, Size);
1563
1564     switch (Type) {
1565     case BytecodeFormat::ConstantPoolBlockID:
1566       if (!InsertedArguments) {
1567         // Insert arguments into the value table before we parse the first basic
1568         // block in the function, but after we potentially read in the
1569         // compaction table.
1570         insertArguments(F);
1571         InsertedArguments = true;
1572       }
1573
1574       ParseConstantPool(FunctionValues, FunctionTypes, true);
1575       break;
1576
1577     case BytecodeFormat::CompactionTableBlockID:
1578       ParseCompactionTable();
1579       break;
1580
1581     case BytecodeFormat::BasicBlock: {
1582       if (!InsertedArguments) {
1583         // Insert arguments into the value table before we parse the first basic
1584         // block in the function, but after we potentially read in the
1585         // compaction table.
1586         insertArguments(F);
1587         InsertedArguments = true;
1588       }
1589
1590       BasicBlock *BB = ParseBasicBlock(BlockNum++);
1591       F->getBasicBlockList().push_back(BB);
1592       break;
1593     }
1594
1595     case BytecodeFormat::InstructionListBlockID: {
1596       // Insert arguments into the value table before we parse the instruction
1597       // list for the function, but after we potentially read in the compaction
1598       // table.
1599       if (!InsertedArguments) {
1600         insertArguments(F);
1601         InsertedArguments = true;
1602       }
1603
1604       if (BlockNum)
1605         error("Already parsed basic blocks!");
1606       BlockNum = ParseInstructionList(F);
1607       break;
1608     }
1609
1610     case BytecodeFormat::SymbolTableBlockID:
1611       ParseSymbolTable(F, &F->getSymbolTable());
1612       break;
1613
1614     default:
1615       At += Size;
1616       if (OldAt > At)
1617         error("Wrapped around reading bytecode.");
1618       break;
1619     }
1620     BlockEnd = MyEnd;
1621
1622     // Malformed bc file if read past end of block.
1623     align32();
1624   }
1625
1626   // Make sure there were no references to non-existant basic blocks.
1627   if (BlockNum != ParsedBasicBlocks.size())
1628     error("Illegal basic block operand reference");
1629
1630   ParsedBasicBlocks.clear();
1631
1632   // Resolve forward references.  Replace any uses of a forward reference value
1633   // with the real value.
1634
1635   // replaceAllUsesWith is very inefficient for instructions which have a LARGE
1636   // number of operands.  PHI nodes often have forward references, and can also
1637   // often have a very large number of operands.
1638   //
1639   // FIXME: REEVALUATE.  replaceAllUsesWith is _much_ faster now, and this code
1640   // should be simplified back to using it!
1641   //
1642   std::map<Value*, Value*> ForwardRefMapping;
1643   for (std::map<std::pair<unsigned,unsigned>, Value*>::iterator
1644          I = ForwardReferences.begin(), E = ForwardReferences.end();
1645        I != E; ++I)
1646     ForwardRefMapping[I->second] = getValue(I->first.first, I->first.second,
1647                                             false);
1648
1649   for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
1650     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
1651       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1652         if (Argument *A = dyn_cast<Argument>(I->getOperand(i))) {
1653           std::map<Value*, Value*>::iterator It = ForwardRefMapping.find(A);
1654           if (It != ForwardRefMapping.end()) I->setOperand(i, It->second);
1655         }
1656
1657   while (!ForwardReferences.empty()) {
1658     std::map<std::pair<unsigned,unsigned>, Value*>::iterator I =
1659       ForwardReferences.begin();
1660     Value *PlaceHolder = I->second;
1661     ForwardReferences.erase(I);
1662
1663     // Now that all the uses are gone, delete the placeholder...
1664     // If we couldn't find a def (error case), then leak a little
1665     // memory, because otherwise we can't remove all uses!
1666     delete PlaceHolder;
1667   }
1668
1669   // Clear out function-level types...
1670   FunctionTypes.clear();
1671   CompactionTypes.clear();
1672   CompactionValues.clear();
1673   freeTable(FunctionValues);
1674
1675   if (Handler) Handler->handleFunctionEnd(F);
1676 }
1677
1678 /// This function parses LLVM functions lazily. It obtains the type of the
1679 /// function and records where the body of the function is in the bytecode
1680 /// buffer. The caller can then use the ParseNextFunction and
1681 /// ParseAllFunctionBodies to get handler events for the functions.
1682 void BytecodeReader::ParseFunctionLazily() {
1683   if (FunctionSignatureList.empty())
1684     error("FunctionSignatureList empty!");
1685
1686   Function *Func = FunctionSignatureList.back();
1687   FunctionSignatureList.pop_back();
1688
1689   // Save the information for future reading of the function
1690   LazyFunctionLoadMap[Func] = LazyFunctionInfo(BlockStart, BlockEnd);
1691
1692   // Pretend we've `parsed' this function
1693   At = BlockEnd;
1694 }
1695
1696 /// The ParserFunction method lazily parses one function. Use this method to
1697 /// casue the parser to parse a specific function in the module. Note that
1698 /// this will remove the function from what is to be included by
1699 /// ParseAllFunctionBodies.
1700 /// @see ParseAllFunctionBodies
1701 /// @see ParseBytecode
1702 void BytecodeReader::ParseFunction(Function* Func) {
1703   // Find {start, end} pointers and slot in the map. If not there, we're done.
1704   LazyFunctionMap::iterator Fi = LazyFunctionLoadMap.find(Func);
1705
1706   // Make sure we found it
1707   if (Fi == LazyFunctionLoadMap.end()) {
1708     error("Unrecognized function of type " + Func->getType()->getDescription());
1709     return;
1710   }
1711
1712   BlockStart = At = Fi->second.Buf;
1713   BlockEnd = Fi->second.EndBuf;
1714   assert(Fi->first == Func && "Found wrong function?");
1715
1716   LazyFunctionLoadMap.erase(Fi);
1717
1718   this->ParseFunctionBody(Func);
1719 }
1720
1721 /// The ParseAllFunctionBodies method parses through all the previously
1722 /// unparsed functions in the bytecode file. If you want to completely parse
1723 /// a bytecode file, this method should be called after Parsebytecode because
1724 /// Parsebytecode only records the locations in the bytecode file of where
1725 /// the function definitions are located. This function uses that information
1726 /// to materialize the functions.
1727 /// @see ParseBytecode
1728 void BytecodeReader::ParseAllFunctionBodies() {
1729   LazyFunctionMap::iterator Fi = LazyFunctionLoadMap.begin();
1730   LazyFunctionMap::iterator Fe = LazyFunctionLoadMap.end();
1731
1732   while (Fi != Fe) {
1733     Function* Func = Fi->first;
1734     BlockStart = At = Fi->second.Buf;
1735     BlockEnd = Fi->second.EndBuf;
1736     this->ParseFunctionBody(Func);
1737     ++Fi;
1738   }
1739 }
1740
1741 /// Parse the global type list
1742 void BytecodeReader::ParseGlobalTypes() {
1743   // Read the number of types
1744   unsigned NumEntries = read_vbr_uint();
1745
1746   // Ignore the type plane identifier for types if the bc file is pre 1.3
1747   if (hasTypeDerivedFromValue)
1748     read_vbr_uint();
1749
1750   ParseTypes(ModuleTypes, NumEntries);
1751 }
1752
1753 /// Parse the Global info (types, global vars, constants)
1754 void BytecodeReader::ParseModuleGlobalInfo() {
1755
1756   if (Handler) Handler->handleModuleGlobalsBegin();
1757
1758   // Read global variables...
1759   unsigned VarType = read_vbr_uint();
1760   while (VarType != Type::VoidTyID) { // List is terminated by Void
1761     // VarType Fields: bit0 = isConstant, bit1 = hasInitializer, bit2,3,4 =
1762     // Linkage, bit4+ = slot#
1763     unsigned SlotNo = VarType >> 5;
1764     if (sanitizeTypeId(SlotNo))
1765       error("Invalid type (type type) for global var!");
1766     unsigned LinkageID = (VarType >> 2) & 7;
1767     bool isConstant = VarType & 1;
1768     bool hasInitializer = VarType & 2;
1769     GlobalValue::LinkageTypes Linkage;
1770
1771     switch (LinkageID) {
1772     case 0: Linkage = GlobalValue::ExternalLinkage;  break;
1773     case 1: Linkage = GlobalValue::WeakLinkage;      break;
1774     case 2: Linkage = GlobalValue::AppendingLinkage; break;
1775     case 3: Linkage = GlobalValue::InternalLinkage;  break;
1776     case 4: Linkage = GlobalValue::LinkOnceLinkage;  break;
1777     default:
1778       error("Unknown linkage type: " + utostr(LinkageID));
1779       Linkage = GlobalValue::InternalLinkage;
1780       break;
1781     }
1782
1783     const Type *Ty = getType(SlotNo);
1784     if (!Ty) {
1785       error("Global has no type! SlotNo=" + utostr(SlotNo));
1786     }
1787
1788     if (!isa<PointerType>(Ty)) {
1789       error("Global not a pointer type! Ty= " + Ty->getDescription());
1790     }
1791
1792     const Type *ElTy = cast<PointerType>(Ty)->getElementType();
1793
1794     // Create the global variable...
1795     GlobalVariable *GV = new GlobalVariable(ElTy, isConstant, Linkage,
1796                                             0, "", TheModule);
1797     insertValue(GV, SlotNo, ModuleValues);
1798
1799     unsigned initSlot = 0;
1800     if (hasInitializer) {
1801       initSlot = read_vbr_uint();
1802       GlobalInits.push_back(std::make_pair(GV, initSlot));
1803     }
1804
1805     // Notify handler about the global value.
1806     if (Handler) Handler->handleGlobalVariable(ElTy, isConstant, Linkage, SlotNo, initSlot);
1807
1808     // Get next item
1809     VarType = read_vbr_uint();
1810   }
1811
1812   // Read the function objects for all of the functions that are coming
1813   unsigned FnSignature = 0;
1814   if (read_typeid(FnSignature))
1815     error("Invalid function type (type type) found");
1816
1817   while (FnSignature != Type::VoidTyID) { // List is terminated by Void
1818     const Type *Ty = getType(FnSignature);
1819     if (!isa<PointerType>(Ty) ||
1820         !isa<FunctionType>(cast<PointerType>(Ty)->getElementType())) {
1821       error("Function not a pointer to function type! Ty = " +
1822             Ty->getDescription());
1823       // FIXME: what should Ty be if handler continues?
1824     }
1825
1826     // We create functions by passing the underlying FunctionType to create...
1827     const FunctionType* FTy =
1828       cast<FunctionType>(cast<PointerType>(Ty)->getElementType());
1829
1830     // Insert the place hodler
1831     Function* Func = new Function(FTy, GlobalValue::InternalLinkage,
1832                                   "", TheModule);
1833     insertValue(Func, FnSignature, ModuleValues);
1834
1835     // Save this for later so we know type of lazily instantiated functions
1836     FunctionSignatureList.push_back(Func);
1837
1838     if (Handler) Handler->handleFunctionDeclaration(Func);
1839
1840     // Get Next function signature
1841     if (read_typeid(FnSignature))
1842       error("Invalid function type (type type) found");
1843   }
1844
1845   // Now that the function signature list is set up, reverse it so that we can
1846   // remove elements efficiently from the back of the vector.
1847   std::reverse(FunctionSignatureList.begin(), FunctionSignatureList.end());
1848
1849   // If this bytecode format has dependent library information in it ..
1850   if (!hasNoDependentLibraries) {
1851     // Read in the number of dependent library items that follow
1852     unsigned num_dep_libs = read_vbr_uint();
1853     std::string dep_lib;
1854     while( num_dep_libs-- ) {
1855       dep_lib = read_str();
1856       TheModule->linsert(dep_lib);
1857     }
1858
1859     // Read target triple and place into the module
1860     std::string triple = read_str();
1861     TheModule->setTargetTriple(triple);
1862   }
1863
1864   if (hasInconsistentModuleGlobalInfo)
1865     align32();
1866
1867   // This is for future proofing... in the future extra fields may be added that
1868   // we don't understand, so we transparently ignore them.
1869   //
1870   At = BlockEnd;
1871
1872   if (Handler) Handler->handleModuleGlobalsEnd();
1873 }
1874
1875 /// Parse the version information and decode it by setting flags on the
1876 /// Reader that enable backward compatibility of the reader.
1877 void BytecodeReader::ParseVersionInfo() {
1878   unsigned Version = read_vbr_uint();
1879
1880   // Unpack version number: low four bits are for flags, top bits = version
1881   Module::Endianness  Endianness;
1882   Module::PointerSize PointerSize;
1883   Endianness  = (Version & 1) ? Module::BigEndian : Module::LittleEndian;
1884   PointerSize = (Version & 2) ? Module::Pointer64 : Module::Pointer32;
1885
1886   bool hasNoEndianness = Version & 4;
1887   bool hasNoPointerSize = Version & 8;
1888
1889   RevisionNum = Version >> 4;
1890
1891   // Default values for the current bytecode version
1892   hasInconsistentModuleGlobalInfo = false;
1893   hasExplicitPrimitiveZeros = false;
1894   hasRestrictedGEPTypes = false;
1895   hasTypeDerivedFromValue = false;
1896   hasLongBlockHeaders = false;
1897   hasPlatformSpecificFloatingPoint = false;
1898   has32BitTypes = false;
1899   hasNoDependentLibraries = false;
1900
1901   switch (RevisionNum) {
1902   case 0:               //  LLVM 1.0, 1.1 release version
1903     // Base LLVM 1.0 bytecode format.
1904     hasInconsistentModuleGlobalInfo = true;
1905     hasExplicitPrimitiveZeros = true;
1906
1907
1908     // FALL THROUGH
1909   case 1:               // LLVM 1.2 release version
1910     // LLVM 1.2 added explicit support for emitting strings efficiently.
1911
1912     // Also, it fixed the problem where the size of the ModuleGlobalInfo block
1913     // included the size for the alignment at the end, where the rest of the
1914     // blocks did not.
1915
1916     // LLVM 1.2 and before required that GEP indices be ubyte constants for
1917     // structures and longs for sequential types.
1918     hasRestrictedGEPTypes = true;
1919
1920     // LLVM 1.2 and before had the Type class derive from Value class. This
1921     // changed in release 1.3 and consequently LLVM 1.3 bytecode files are
1922     // written differently because Types can no longer be part of the
1923     // type planes for Values.
1924     hasTypeDerivedFromValue = true;
1925
1926     // FALL THROUGH
1927
1928   case 2:  /// 1.2.5 (mid-release) version
1929
1930     /// LLVM 1.2 and earlier had two-word block headers. This is a bit wasteful,
1931     /// especially for small files where the 8 bytes per block is a large fraction
1932     /// of the total block size. In LLVM 1.3, the block type and length are
1933     /// compressed into a single 32-bit unsigned integer. 27 bits for length, 5
1934     /// bits for block type.
1935     hasLongBlockHeaders = true;
1936
1937     /// LLVM 1.2 and earlier wrote floating point values in a platform specific
1938     /// bit ordering. This was fixed in LLVM 1.3, but we still need to be backwards
1939     /// compatible.
1940     hasPlatformSpecificFloatingPoint = true;
1941
1942     /// LLVM 1.2 and earlier wrote type slot numbers as vbr_uint32. In LLVM 1.3
1943     /// this has been reduced to vbr_uint24. It shouldn't make much difference
1944     /// since we haven't run into a module with > 24 million types, but for safety
1945     /// the 24-bit restriction has been enforced in 1.3 to free some bits in
1946     /// various places and to ensure consistency.
1947     has32BitTypes = true;
1948
1949     /// LLVM 1.2 and earlier did not provide a target triple nor a list of
1950     /// libraries on which the bytecode is dependent. LLVM 1.3 provides these
1951     /// features, for use in future versions of LLVM.
1952     hasNoDependentLibraries = true;
1953
1954     // FALL THROUGH
1955   case 3:               // LLVM 1.3 release version
1956     break;
1957
1958   default:
1959     error("Unknown bytecode version number: " + itostr(RevisionNum));
1960   }
1961
1962   if (hasNoEndianness) Endianness  = Module::AnyEndianness;
1963   if (hasNoPointerSize) PointerSize = Module::AnyPointerSize;
1964
1965   TheModule->setEndianness(Endianness);
1966   TheModule->setPointerSize(PointerSize);
1967
1968   if (Handler) Handler->handleVersionInfo(RevisionNum, Endianness, PointerSize);
1969 }
1970
1971 /// Parse a whole module.
1972 void BytecodeReader::ParseModule() {
1973   unsigned Type, Size;
1974
1975   FunctionSignatureList.clear(); // Just in case...
1976
1977   // Read into instance variables...
1978   ParseVersionInfo();
1979   align32();
1980
1981   bool SeenModuleGlobalInfo = false;
1982   bool SeenGlobalTypePlane = false;
1983   BufPtr MyEnd = BlockEnd;
1984   while (At < MyEnd) {
1985     BufPtr OldAt = At;
1986     read_block(Type, Size);
1987
1988     switch (Type) {
1989
1990     case BytecodeFormat::GlobalTypePlaneBlockID:
1991       if (SeenGlobalTypePlane)
1992         error("Two GlobalTypePlane Blocks Encountered!");
1993
1994       ParseGlobalTypes();
1995       SeenGlobalTypePlane = true;
1996       break;
1997
1998     case BytecodeFormat::ModuleGlobalInfoBlockID:
1999       if (SeenModuleGlobalInfo)
2000         error("Two ModuleGlobalInfo Blocks Encountered!");
2001       ParseModuleGlobalInfo();
2002       SeenModuleGlobalInfo = true;
2003       break;
2004
2005     case BytecodeFormat::ConstantPoolBlockID:
2006       ParseConstantPool(ModuleValues, ModuleTypes,false);
2007       break;
2008
2009     case BytecodeFormat::FunctionBlockID:
2010       ParseFunctionLazily();
2011       break;
2012
2013     case BytecodeFormat::SymbolTableBlockID:
2014       ParseSymbolTable(0, &TheModule->getSymbolTable());
2015       break;
2016
2017     default:
2018       At += Size;
2019       if (OldAt > At) {
2020         error("Unexpected Block of Type #" + utostr(Type) + " encountered!");
2021       }
2022       break;
2023     }
2024     BlockEnd = MyEnd;
2025     align32();
2026   }
2027
2028   // After the module constant pool has been read, we can safely initialize
2029   // global variables...
2030   while (!GlobalInits.empty()) {
2031     GlobalVariable *GV = GlobalInits.back().first;
2032     unsigned Slot = GlobalInits.back().second;
2033     GlobalInits.pop_back();
2034
2035     // Look up the initializer value...
2036     // FIXME: Preserve this type ID!
2037
2038     const llvm::PointerType* GVType = GV->getType();
2039     unsigned TypeSlot = getTypeSlot(GVType->getElementType());
2040     if (Constant *CV = getConstantValue(TypeSlot, Slot)) {
2041       if (GV->hasInitializer())
2042         error("Global *already* has an initializer?!");
2043       if (Handler) Handler->handleGlobalInitializer(GV,CV);
2044       GV->setInitializer(CV);
2045     } else
2046       error("Cannot find initializer value.");
2047   }
2048
2049   /// Make sure we pulled them all out. If we didn't then there's a declaration
2050   /// but a missing body. That's not allowed.
2051   if (!FunctionSignatureList.empty())
2052     error("Function declared, but bytecode stream ended before definition");
2053 }
2054
2055 /// This function completely parses a bytecode buffer given by the \p Buf
2056 /// and \p Length parameters.
2057 void BytecodeReader::ParseBytecode(BufPtr Buf, unsigned Length,
2058                                    const std::string &ModuleID,
2059                                    bool processFunctions) {
2060
2061   try {
2062     At = MemStart = BlockStart = Buf;
2063     MemEnd = BlockEnd = Buf + Length;
2064
2065     // Create the module
2066     TheModule = new Module(ModuleID);
2067
2068     if (Handler) Handler->handleStart(TheModule, Length);
2069
2070     // Read and check signature...
2071     unsigned Sig = read_uint();
2072     if (Sig != ('l' | ('l' << 8) | ('v' << 16) | ('m' << 24))) {
2073       error("Invalid bytecode signature: " + utostr(Sig));
2074     }
2075
2076     // Tell the handler we're starting a module
2077     if (Handler) Handler->handleModuleBegin(ModuleID);
2078
2079     // Get the module block and size and verify. This is handled specially
2080     // because the module block/size is always written in long format. Other
2081     // blocks are written in short format so the read_block method is used.
2082     unsigned Type, Size;
2083     Type = read_uint();
2084     Size = read_uint();
2085     if (Type != BytecodeFormat::ModuleBlockID) {
2086       error("Expected Module Block! Type:" + utostr(Type) + ", Size:"
2087             + utostr(Size));
2088     }
2089     if (At + Size != MemEnd) {
2090       error("Invalid Top Level Block Length! Type:" + utostr(Type)
2091             + ", Size:" + utostr(Size));
2092     }
2093
2094     // Parse the module contents
2095     this->ParseModule();
2096
2097     // Check for missing functions
2098     if (hasFunctions())
2099       error("Function expected, but bytecode stream ended!");
2100
2101     // Process all the function bodies now, if requested
2102     if (processFunctions)
2103       ParseAllFunctionBodies();
2104
2105     // Tell the handler we're done with the module
2106     if (Handler)
2107       Handler->handleModuleEnd(ModuleID);
2108
2109     // Tell the handler we're finished the parse
2110     if (Handler) Handler->handleFinish();
2111
2112   } catch (std::string& errstr) {
2113     if (Handler) Handler->handleError(errstr);
2114     freeState();
2115     delete TheModule;
2116     TheModule = 0;
2117     throw;
2118   } catch (...) {
2119     std::string msg("Unknown Exception Occurred");
2120     if (Handler) Handler->handleError(msg);
2121     freeState();
2122     delete TheModule;
2123     TheModule = 0;
2124     throw msg;
2125   }
2126 }
2127
2128 //===----------------------------------------------------------------------===//
2129 //=== Default Implementations of Handler Methods
2130 //===----------------------------------------------------------------------===//
2131
2132 BytecodeHandler::~BytecodeHandler() {}
2133
2134 // vim: sw=2