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