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