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