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