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