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: {   // attributed load
 835         if (Oprnds.size() != 2 || !isa<PointerType>(InstTy))
 836           error("Invalid attributed load instruction!");
 837         Result = new LoadInst(getValue(iType, Oprnds[0]), "", (Oprnds[1] & 1),
 838                               (1 << (Oprnds[1]>>1)) >> 1);
 839         break;
 840       }
 841     case Instruction::Load:
 842       if (Oprnds.size() != 1 || !isa<PointerType>(InstTy))
 843         error("Invalid load instruction!");
 844       Result = new LoadInst(getValue(iType, Oprnds[0]), "");
 845       break;
 846     case 63: {   // attributed store
 847         if (!isa<PointerType>(InstTy) || Oprnds.size() != 3)
 848           error("Invalid attributed store instruction!");
 849
 850         Value *Ptr = getValue(iType, Oprnds[1]);
 851         const Type *ValTy = cast<PointerType>(Ptr->getType())->getElementType();
 852         Result = new StoreInst(getValue(getTypeSlot(ValTy), Oprnds[0]), Ptr,
 853                                (Oprnds[2] & 1),
 854                                (1 << (Oprnds[2]>>1)) >> 1);
 855         break;
 856       }
 857     case Instruction::Store: {
 858       if (!isa<PointerType>(InstTy) || Oprnds.size() != 2)
 859         error("Invalid store instruction!");
 860
 861       Value *Ptr = getValue(iType, Oprnds[1]);
 862       const Type *ValTy = cast<PointerType>(Ptr->getType())->getElementType();
 863       Result = new StoreInst(getValue(getTypeSlot(ValTy), Oprnds[0]), Ptr,
 864                              Opcode == 63);
 865       break;
 866     }
 867     case Instruction::Unwind:
 868       if (Oprnds.size() != 0) error("Invalid unwind instruction!");
 869       Result = new UnwindInst();
 870       break;
 871     case Instruction::Unreachable:
 872       if (Oprnds.size() != 0) error("Invalid unreachable instruction!");
 873       Result = new UnreachableInst();
 874       break;
 875     }  // end switch(Opcode)
 876   } // end if !Result
 877
 878   BB->getInstList().push_back(Result);
 879
 880   unsigned TypeSlot;
 881   if (Result->getType() == InstTy)
 882     TypeSlot = iType;
 883   else
 884     TypeSlot = getTypeSlot(Result->getType());
 885
 886   // We have enough info to inform the handler now.
 887   if (Handler)
 888     Handler->handleInstruction(Opcode, InstTy, &Oprnds[0], Oprnds.size(),
 889                                Result, At-SaveAt);
 890
 891   insertValue(Result, TypeSlot, FunctionValues);
 892 }
 893
 894 /// Get a particular numbered basic block, which might be a forward reference.
 895 /// This works together with ParseInstructionList to handle these forward
 896 /// references in a clean manner.  This function is used when constructing
 897 /// phi, br, switch, and other instructions that reference basic blocks.
 898 /// Blocks are numbered sequentially as they appear in the function.
 899 BasicBlock *BytecodeReader::getBasicBlock(unsigned ID) {
 900   // Make sure there is room in the table...
 901   if (ParsedBasicBlocks.size() <= ID) ParsedBasicBlocks.resize(ID+1);
 902
 903   // First check to see if this is a backwards reference, i.e. this block
 904   // has already been created, or if the forward reference has already
 905   // been created.
 906   if (ParsedBasicBlocks[ID])
 907     return ParsedBasicBlocks[ID];
 908
 909   // Otherwise, the basic block has not yet been created.  Do so and add it to
 910   // the ParsedBasicBlocks list.
 911   return ParsedBasicBlocks[ID] = new BasicBlock();
 912 }
 913
 914 /// Parse all of the BasicBlock's & Instruction's in the body of a function.
 915 /// In post 1.0 bytecode files, we no longer emit basic block individually,
 916 /// in order to avoid per-basic-block overhead.
 917 /// @returns the number of basic blocks encountered.
 918 unsigned BytecodeReader::ParseInstructionList(Function* F) {
 919   unsigned BlockNo = 0;
 920   SmallVector<unsigned, 8> Args;
 921
 922   while (moreInBlock()) {
 923     if (Handler) Handler->handleBasicBlockBegin(BlockNo);
 924     BasicBlock *BB;
 925     if (ParsedBasicBlocks.size() == BlockNo)
 926       ParsedBasicBlocks.push_back(BB = new BasicBlock());
 927     else if (ParsedBasicBlocks[BlockNo] == 0)
 928       BB = ParsedBasicBlocks[BlockNo] = new BasicBlock();
 929     else
 930       BB = ParsedBasicBlocks[BlockNo];
 931     ++BlockNo;
 932     F->getBasicBlockList().push_back(BB);
 933
 934     // Read instructions into this basic block until we get to a terminator
 935     while (moreInBlock() && !BB->getTerminator())
 936       ParseInstruction(Args, BB);
 937
 938     if (!BB->getTerminator())
 939       error("Non-terminated basic block found!");
 940
 941     if (Handler) Handler->handleBasicBlockEnd(BlockNo-1);
 942   }
 943
 944   return BlockNo;
 945 }
 946
 947 /// Parse a type symbol table.
 948 void BytecodeReader::ParseTypeSymbolTable(TypeSymbolTable *TST) {
 949   // Type Symtab block header: [num entries]
 950   unsigned NumEntries = read_vbr_uint();
 951   for (unsigned i = 0; i < NumEntries; ++i) {
 952     // Symtab entry: [type slot #][name]
 953     unsigned slot = read_vbr_uint();
 954     std::string Name = read_str();
 955     const Type* T = getType(slot);
 956     TST->insert(Name, T);
 957   }
 958 }
 959
 960 /// Parse a value symbol table. This works for both module level and function
 961 /// level symbol tables.  For function level symbol tables, the CurrentFunction
 962 /// parameter must be non-zero and the ST parameter must correspond to
 963 /// CurrentFunction's symbol table. For Module level symbol tables, the
 964 /// CurrentFunction argument must be zero.
 965 void BytecodeReader::ParseValueSymbolTable(Function *CurrentFunction,
 966                                            ValueSymbolTable *VST) {
 967
 968   if (Handler) Handler->handleValueSymbolTableBegin(CurrentFunction,VST);
 969
 970   // Allow efficient basic block lookup by number.
 971   SmallVector<BasicBlock*, 32> BBMap;
 972   if (CurrentFunction)
 973     for (Function::iterator I = CurrentFunction->begin(),
 974            E = CurrentFunction->end(); I != E; ++I)
 975       BBMap.push_back(I);
 976
 977   SmallVector<char, 32> NameStr;
 978
 979   while (moreInBlock()) {
 980     // Symtab block header: [num entries][type id number]
 981     unsigned NumEntries = read_vbr_uint();
 982     unsigned Typ = read_vbr_uint();
 983
 984     for (unsigned i = 0; i != NumEntries; ++i) {
 985       // Symtab entry: [def slot #][name]
 986       unsigned slot = read_vbr_uint();
 987       read_str(NameStr);
 988       Value *V = 0;
 989       if (Typ == LabelTySlot) {
 990         V = (slot < BBMap.size()) ? BBMap[slot] : 0;
 991       } else {
 992         V = getValue(Typ, slot, false); // Find mapping.
 993       }
 994       if (Handler) Handler->handleSymbolTableValue(Typ, slot,
 995                                                    &NameStr[0], NameStr.size());
 996       if (V == 0)
 997         error("Failed value look-up for name '" +
 998               std::string(NameStr.begin(), NameStr.end()) + "', type #" +
 999               utostr(Typ) + " slot #" + utostr(slot));
1000       V->setName(&NameStr[0], NameStr.size());
1001
1002       NameStr.clear();
1003     }
1004   }
1005   checkPastBlockEnd("Symbol Table");
1006   if (Handler) Handler->handleValueSymbolTableEnd();
1007 }
1008
1009 // Parse a single type. The typeid is read in first. If its a primitive type
1010 // then nothing else needs to be read, we know how to instantiate it. If its
1011 // a derived type, then additional data is read to fill out the type
1012 // definition.
1013 const Type *BytecodeReader::ParseType() {
1014   unsigned PrimType = read_vbr_uint();
1015   const Type *Result = 0;
1016   if ((Result = Type::getPrimitiveType((Type::TypeID)PrimType)))
1017     return Result;
1018
1019   switch (PrimType) {
1020   case Type::IntegerTyID: {
1021     unsigned NumBits = read_vbr_uint();
1022     Result = IntegerType::get(NumBits);
1023     break;
1024   }
1025   case Type::FunctionTyID: {
1026     const Type *RetType = readType();
1027     unsigned NumParams = read_vbr_uint();
1028
1029     std::vector<const Type*> Params;
1030     while (NumParams--) {
1031       Params.push_back(readType());
1032     }
1033
1034     bool isVarArg = Params.size() && Params.back() == Type::VoidTy;
1035     if (isVarArg)
1036       Params.pop_back();
1037
1038     ParamAttrsList *Attrs = ParseParamAttrsList();
1039
1040     Result = FunctionType::get(RetType, Params, isVarArg, Attrs);
1041     break;
1042   }
1043   case Type::ArrayTyID: {
1044     const Type *ElementType = readType();
1045     unsigned NumElements = read_vbr_uint();
1046     Result =  ArrayType::get(ElementType, NumElements);
1047     break;
1048   }
1049   case Type::VectorTyID: {
1050     const Type *ElementType = readType();
1051     unsigned NumElements = read_vbr_uint();
1052     Result =  VectorType::get(ElementType, NumElements);
1053     break;
1054   }
1055   case Type::StructTyID: {
1056     std::vector<const Type*> Elements;
1057     unsigned Typ = read_vbr_uint();
1058     while (Typ) {         // List is terminated by void/0 typeid
1059       Elements.push_back(getType(Typ));
1060       Typ = read_vbr_uint();
1061     }
1062
1063     Result = StructType::get(Elements, false);
1064     break;
1065   }
1066   case Type::PackedStructTyID: {
1067     std::vector<const Type*> Elements;
1068     unsigned Typ = read_vbr_uint();
1069     while (Typ) {         // List is terminated by void/0 typeid
1070       Elements.push_back(getType(Typ));
1071       Typ = read_vbr_uint();
1072     }
1073
1074     Result = StructType::get(Elements, true);
1075     break;
1076   }
1077   case Type::PointerTyID: {
1078     Result = PointerType::get(readType());
1079     break;
1080   }
1081
1082   case Type::OpaqueTyID: {
1083     Result = OpaqueType::get();
1084     break;
1085   }
1086
1087   default:
1088     error("Don't know how to deserialize primitive type " + utostr(PrimType));
1089     break;
1090   }
1091   if (Handler) Handler->handleType(Result);
1092   return Result;
1093 }
1094
1095 ParamAttrsList *BytecodeReader::ParseParamAttrsList() {
1096   unsigned NumAttrs = read_vbr_uint();
1097   ParamAttrsList *PAL = 0;
1098   if (NumAttrs) {
1099     ParamAttrsVector Attrs;
1100     ParamAttrsWithIndex PAWI;
1101     while (NumAttrs--) {
1102       PAWI.index = read_vbr_uint();
1103       PAWI.attrs = read_vbr_uint();
1104       Attrs.push_back(PAWI);
1105     }
1106     PAL = ParamAttrsList::get(Attrs);
1107   }
1108   return PAL;
1109 }
1110
1111
1112 // ParseTypes - We have to use this weird code to handle recursive
1113 // types.  We know that recursive types will only reference the current slab of
1114 // values in the type plane, but they can forward reference types before they
1115 // have been read.  For example, Type #0 might be '{ Ty#1 }' and Type #1 might
1116 // be 'Ty#0*'.  When reading Type #0, type number one doesn't exist.  To fix
1117 // this ugly problem, we pessimistically insert an opaque type for each type we
1118 // are about to read.  This means that forward references will resolve to
1119 // something and when we reread the type later, we can replace the opaque type
1120 // with a new resolved concrete type.
1121 //
1122 void BytecodeReader::ParseTypes(TypeListTy &Tab, unsigned NumEntries){
1123   assert(Tab.size() == 0 && "should not have read type constants in before!");
1124
1125   // Insert a bunch of opaque types to be resolved later...
1126   Tab.reserve(NumEntries);
1127   for (unsigned i = 0; i != NumEntries; ++i)
1128     Tab.push_back(OpaqueType::get());
1129
1130   if (Handler)
1131     Handler->handleTypeList(NumEntries);
1132
1133   // If we are about to resolve types, make sure the type cache is clear.
1134   if (NumEntries)
1135     ModuleTypeIDCache.clear();
1136
1137   // Loop through reading all of the types.  Forward types will make use of the
1138   // opaque types just inserted.
1139   //
1140   for (unsigned i = 0; i != NumEntries; ++i) {
1141     const Type* NewTy = ParseType();
1142     const Type* OldTy = Tab[i].get();
1143     if (NewTy == 0)
1144       error("Couldn't parse type!");
1145
1146     // Don't directly push the new type on the Tab. Instead we want to replace
1147     // the opaque type we previously inserted with the new concrete value. This
1148     // approach helps with forward references to types. The refinement from the
1149     // abstract (opaque) type to the new type causes all uses of the abstract
1150     // type to use the concrete type (NewTy). This will also cause the opaque
1151     // type to be deleted.
1152     cast<DerivedType>(const_cast<Type*>(OldTy))->refineAbstractTypeTo(NewTy);
1153
1154     // This should have replaced the old opaque type with the new type in the
1155     // value table... or with a preexisting type that was already in the system.
1156     // Let's just make sure it did.
1157     assert(Tab[i] != OldTy && "refineAbstractType didn't work!");
1158   }
1159 }
1160
1161 /// Parse a single constant value
1162 Value *BytecodeReader::ParseConstantPoolValue(unsigned TypeID) {
1163   // We must check for a ConstantExpr before switching by type because
1164   // a ConstantExpr can be of any type, and has no explicit value.
1165   //
1166   // 0 if not expr; numArgs if is expr
1167   unsigned isExprNumArgs = read_vbr_uint();
1168
1169   if (isExprNumArgs) {
1170     // 'undef' is encoded with 'exprnumargs' == 1.
1171     if (isExprNumArgs == 1)
1172       return UndefValue::get(getType(TypeID));
1173
1174     // Inline asm is encoded with exprnumargs == ~0U.
1175     if (isExprNumArgs == ~0U) {
1176       std::string AsmStr = read_str();
1177       std::string ConstraintStr = read_str();
1178       unsigned Flags = read_vbr_uint();
1179
1180       const PointerType *PTy = dyn_cast<PointerType>(getType(TypeID));
1181       const FunctionType *FTy =
1182         PTy ? dyn_cast<FunctionType>(PTy->getElementType()) : 0;
1183
1184       if (!FTy || !InlineAsm::Verify(FTy, ConstraintStr))
1185         error("Invalid constraints for inline asm");
1186       if (Flags & ~1U)
1187         error("Invalid flags for inline asm");
1188       bool HasSideEffects = Flags & 1;
1189       return InlineAsm::get(FTy, AsmStr, ConstraintStr, HasSideEffects);
1190     }
1191
1192     --isExprNumArgs;
1193
1194     // FIXME: Encoding of constant exprs could be much more compact!
1195     SmallVector<Constant*, 8> ArgVec;
1196     ArgVec.reserve(isExprNumArgs);
1197     unsigned Opcode = read_vbr_uint();
1198
1199     // Read the slot number and types of each of the arguments
1200     for (unsigned i = 0; i != isExprNumArgs; ++i) {
1201       unsigned ArgValSlot = read_vbr_uint();
1202       unsigned ArgTypeSlot = read_vbr_uint();
1203
1204       // Get the arg value from its slot if it exists, otherwise a placeholder
1205       ArgVec.push_back(getConstantValue(ArgTypeSlot, ArgValSlot));
1206     }
1207
1208     // Construct a ConstantExpr of the appropriate kind
1209     if (isExprNumArgs == 1) {           // All one-operand expressions
1210       if (!Instruction::isCast(Opcode))
1211         error("Only cast instruction has one argument for ConstantExpr");
1212
1213       Constant *Result = ConstantExpr::getCast(Opcode, ArgVec[0],
1214                                                getType(TypeID));
1215       if (Handler) Handler->handleConstantExpression(Opcode, &ArgVec[0],
1216                                                      ArgVec.size(), Result);
1217       return Result;
1218     } else if (Opcode == Instruction::GetElementPtr) { // GetElementPtr
1219       Constant *Result = ConstantExpr::getGetElementPtr(ArgVec[0], &ArgVec[1],
1220                                                         ArgVec.size()-1);
1221       if (Handler) Handler->handleConstantExpression(Opcode, &ArgVec[0],
1222                                                      ArgVec.size(), Result);
1223       return Result;
1224     } else if (Opcode == Instruction::Select) {
1225       if (ArgVec.size() != 3)
1226         error("Select instruction must have three arguments.");
1227       Constant* Result = ConstantExpr::getSelect(ArgVec[0], ArgVec[1],
1228                                                  ArgVec[2]);
1229       if (Handler) Handler->handleConstantExpression(Opcode, &ArgVec[0],
1230                                                      ArgVec.size(), Result);
1231       return Result;
1232     } else if (Opcode == Instruction::ExtractElement) {
1233       if (ArgVec.size() != 2 ||
1234           !ExtractElementInst::isValidOperands(ArgVec[0], ArgVec[1]))
1235         error("Invalid extractelement constand expr arguments");
1236       Constant* Result = ConstantExpr::getExtractElement(ArgVec[0], ArgVec[1]);
1237       if (Handler) Handler->handleConstantExpression(Opcode, &ArgVec[0],
1238                                                      ArgVec.size(), Result);
1239       return Result;
1240     } else if (Opcode == Instruction::InsertElement) {
1241       if (ArgVec.size() != 3 ||
1242           !InsertElementInst::isValidOperands(ArgVec[0], ArgVec[1], ArgVec[2]))
1243         error("Invalid insertelement constand expr arguments");
1244
1245       Constant *Result =
1246         ConstantExpr::getInsertElement(ArgVec[0], ArgVec[1], ArgVec[2]);
1247       if (Handler) Handler->handleConstantExpression(Opcode, &ArgVec[0],
1248                                                      ArgVec.size(), Result);
1249       return Result;
1250     } else if (Opcode == Instruction::ShuffleVector) {
1251       if (ArgVec.size() != 3 ||
1252           !ShuffleVectorInst::isValidOperands(ArgVec[0], ArgVec[1], ArgVec[2]))
1253         error("Invalid shufflevector constant expr arguments.");
1254       Constant *Result =
1255         ConstantExpr::getShuffleVector(ArgVec[0], ArgVec[1], ArgVec[2]);
1256       if (Handler) Handler->handleConstantExpression(Opcode, &ArgVec[0],
1257                                                      ArgVec.size(), Result);
1258       return Result;
1259     } else if (Opcode == Instruction::ICmp) {
1260       if (ArgVec.size() != 2)
1261         error("Invalid ICmp constant expr arguments.");
1262       unsigned predicate = read_vbr_uint();
1263       Constant *Result = ConstantExpr::getICmp(predicate, ArgVec[0], ArgVec[1]);
1264       if (Handler) Handler->handleConstantExpression(Opcode, &ArgVec[0],
1265                                                      ArgVec.size(), Result);
1266       return Result;
1267     } else if (Opcode == Instruction::FCmp) {
1268       if (ArgVec.size() != 2)
1269         error("Invalid FCmp constant expr arguments.");
1270       unsigned predicate = read_vbr_uint();
1271       Constant *Result = ConstantExpr::getFCmp(predicate, ArgVec[0], ArgVec[1]);
1272       if (Handler) Handler->handleConstantExpression(Opcode, &ArgVec[0],
1273                                                      ArgVec.size(), Result);
1274       return Result;
1275     } else {                            // All other 2-operand expressions
1276       Constant* Result = ConstantExpr::get(Opcode, ArgVec[0], ArgVec[1]);
1277       if (Handler) Handler->handleConstantExpression(Opcode, &ArgVec[0],
1278                                                      ArgVec.size(), Result);
1279       return Result;
1280     }
1281   }
1282
1283   // Ok, not an ConstantExpr.  We now know how to read the given type...
1284   const Type *Ty = getType(TypeID);
1285   Constant *Result = 0;
1286   switch (Ty->getTypeID()) {
1287   case Type::IntegerTyID: {
1288     const IntegerType *IT = cast<IntegerType>(Ty);
1289     if (IT->getBitWidth() <= 32) {
1290       uint32_t Val = read_vbr_uint();
1291       if (!ConstantInt::isValueValidForType(Ty, uint64_t(Val)))
1292         error("Integer value read is invalid for type.");
1293       Result = ConstantInt::get(IT, Val);
1294       if (Handler) Handler->handleConstantValue(Result);
1295     } else if (IT->getBitWidth() <= 64) {
1296       uint64_t Val = read_vbr_uint64();
1297       if (!ConstantInt::isValueValidForType(Ty, Val))
1298         error("Invalid constant integer read.");
1299       Result = ConstantInt::get(IT, Val);
1300       if (Handler) Handler->handleConstantValue(Result);
1301     } else {
1302       uint32_t NumWords = read_vbr_uint();
1303       SmallVector<uint64_t, 8> Words;
1304       Words.resize(NumWords);
1305       for (uint32_t i = 0; i < NumWords; ++i)
1306         Words[i] = read_vbr_uint64();
1307       Result = ConstantInt::get(APInt(IT->getBitWidth(), NumWords, &Words[0]));
1308       if (Handler) Handler->handleConstantValue(Result);
1309     }
1310     break;
1311   }
1312   case Type::FloatTyID: {
1313     float Val;
1314     read_float(Val);
1315     Result = ConstantFP::get(Ty, Val);
1316     if (Handler) Handler->handleConstantValue(Result);
1317     break;
1318   }
1319
1320   case Type::DoubleTyID: {
1321     double Val;
1322     read_double(Val);
1323     Result = ConstantFP::get(Ty, Val);
1324     if (Handler) Handler->handleConstantValue(Result);
1325     break;
1326   }
1327
1328   case Type::ArrayTyID: {
1329     const ArrayType *AT = cast<ArrayType>(Ty);
1330     unsigned NumElements = AT->getNumElements();
1331     unsigned TypeSlot = getTypeSlot(AT->getElementType());
1332     std::vector<Constant*> Elements;
1333     Elements.reserve(NumElements);
1334     while (NumElements--)     // Read all of the elements of the constant.
1335       Elements.push_back(getConstantValue(TypeSlot,
1336                                           read_vbr_uint()));
1337     Result = ConstantArray::get(AT, Elements);
1338     if (Handler) Handler->handleConstantArray(AT, &Elements[0], Elements.size(),
1339                                               TypeSlot, Result);
1340     break;
1341   }
1342
1343   case Type::StructTyID: {
1344     const StructType *ST = cast<StructType>(Ty);
1345
1346     std::vector<Constant *> Elements;
1347     Elements.reserve(ST->getNumElements());
1348     for (unsigned i = 0; i != ST->getNumElements(); ++i)
1349       Elements.push_back(getConstantValue(ST->getElementType(i),
1350                                           read_vbr_uint()));
1351
1352     Result = ConstantStruct::get(ST, Elements);
1353     if (Handler) Handler->handleConstantStruct(ST, &Elements[0],Elements.size(),
1354                                                Result);
1355     break;
1356   }
1357
1358   case Type::VectorTyID: {
1359     const VectorType *PT = cast<VectorType>(Ty);
1360     unsigned NumElements = PT->getNumElements();
1361     unsigned TypeSlot = getTypeSlot(PT->getElementType());
1362     std::vector<Constant*> Elements;
1363     Elements.reserve(NumElements);
1364     while (NumElements--)     // Read all of the elements of the constant.
1365       Elements.push_back(getConstantValue(TypeSlot,
1366                                           read_vbr_uint()));
1367     Result = ConstantVector::get(PT, Elements);
1368     if (Handler) Handler->handleConstantVector(PT, &Elements[0],Elements.size(),
1369                                                TypeSlot, Result);
1370     break;
1371   }
1372
1373   case Type::PointerTyID: {  // ConstantPointerRef value (backwards compat).
1374     const PointerType *PT = cast<PointerType>(Ty);
1375     unsigned Slot = read_vbr_uint();
1376
1377     // Check to see if we have already read this global variable...
1378     Value *Val = getValue(TypeID, Slot, false);
1379     if (Val) {
1380       GlobalValue *GV = dyn_cast<GlobalValue>(Val);
1381       if (!GV) error("GlobalValue not in ValueTable!");
1382       if (Handler) Handler->handleConstantPointer(PT, Slot, GV);
1383       return GV;
1384     } else {
1385       error("Forward references are not allowed here.");
1386     }
1387   }
1388
1389   default:
1390     error("Don't know how to deserialize constant value of type '" +
1391                       Ty->getDescription());
1392     break;
1393   }
1394
1395   // Check that we didn't read a null constant if they are implicit for this
1396   // type plane.  Do not do this check for constantexprs, as they may be folded
1397   // to a null value in a way that isn't predicted when a .bc file is initially
1398   // produced.
1399   assert((!isa<Constant>(Result) || !cast<Constant>(Result)->isNullValue()) ||
1400          !hasImplicitNull(TypeID) && "Cannot read null values from bytecode!");
1401   return Result;
1402 }
1403
1404 /// Resolve references for constants. This function resolves the forward
1405 /// referenced constants in the ConstantFwdRefs map. It uses the
1406 /// replaceAllUsesWith method of Value class to substitute the placeholder
1407 /// instance with the actual instance.
1408 void BytecodeReader::ResolveReferencesToConstant(Constant *NewV, unsigned Typ,
1409                                                  unsigned Slot) {
1410   ConstantRefsType::iterator I =
1411     ConstantFwdRefs.find(std::make_pair(Typ, Slot));
1412   if (I == ConstantFwdRefs.end()) return;   // Never forward referenced?
1413
1414   Value *PH = I->second;   // Get the placeholder...
1415   PH->replaceAllUsesWith(NewV);
1416   delete PH;                               // Delete the old placeholder
1417   ConstantFwdRefs.erase(I);                // Remove the map entry for it
1418 }
1419
1420 /// Parse the constant strings section.
1421 void BytecodeReader::ParseStringConstants(unsigned NumEntries, ValueTable &Tab){
1422   for (; NumEntries; --NumEntries) {
1423     unsigned Typ = read_vbr_uint();
1424     const Type *Ty = getType(Typ);
1425     if (!isa<ArrayType>(Ty))
1426       error("String constant data invalid!");
1427
1428     const ArrayType *ATy = cast<ArrayType>(Ty);
1429     if (ATy->getElementType() != Type::Int8Ty &&
1430         ATy->getElementType() != Type::Int8Ty)
1431       error("String constant data invalid!");
1432
1433     // Read character data.  The type tells us how long the string is.
1434     char *Data = reinterpret_cast<char *>(alloca(ATy->getNumElements()));
1435     read_data(Data, Data+ATy->getNumElements());
1436
1437     std::vector<Constant*> Elements(ATy->getNumElements());
1438     const Type* ElemType = ATy->getElementType();
1439     for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i)
1440       Elements[i] = ConstantInt::get(ElemType, (unsigned char)Data[i]);
1441
1442     // Create the constant, inserting it as needed.
1443     Constant *C = ConstantArray::get(ATy, Elements);
1444     unsigned Slot = insertValue(C, Typ, Tab);
1445     ResolveReferencesToConstant(C, Typ, Slot);
1446     if (Handler) Handler->handleConstantString(cast<ConstantArray>(C));
1447   }
1448 }
1449
1450 /// Parse the constant pool.
1451 void BytecodeReader::ParseConstantPool(ValueTable &Tab,
1452                                        TypeListTy &TypeTab,
1453                                        bool isFunction) {
1454   if (Handler) Handler->handleGlobalConstantsBegin();
1455
1456   /// In LLVM 1.3 Type does not derive from Value so the types
1457   /// do not occupy a plane. Consequently, we read the types
1458   /// first in the constant pool.
1459   if (isFunction) {
1460     unsigned NumEntries = read_vbr_uint();
1461     ParseTypes(TypeTab, NumEntries);
1462   }
1463
1464   while (moreInBlock()) {
1465     unsigned NumEntries = read_vbr_uint();
1466     unsigned Typ = read_vbr_uint();
1467
1468     if (Typ == Type::VoidTyID) {
1469       /// Use of Type::VoidTyID is a misnomer. It actually means
1470       /// that the following plane is constant strings
1471       assert(&Tab == &ModuleValues && "Cannot read strings in functions!");
1472       ParseStringConstants(NumEntries, Tab);
1473     } else {
1474       for (unsigned i = 0; i < NumEntries; ++i) {
1475         Value *V = ParseConstantPoolValue(Typ);
1476         assert(V && "ParseConstantPoolValue returned NULL!");
1477         unsigned Slot = insertValue(V, Typ, Tab);
1478
1479         // If we are reading a function constant table, make sure that we adjust
1480         // the slot number to be the real global constant number.
1481         //
1482         if (&Tab != &ModuleValues && Typ < ModuleValues.size() &&
1483             ModuleValues[Typ])
1484           Slot += ModuleValues[Typ]->size();
1485         if (Constant *C = dyn_cast<Constant>(V))
1486           ResolveReferencesToConstant(C, Typ, Slot);
1487       }
1488     }
1489   }
1490
1491   // After we have finished parsing the constant pool, we had better not have
1492   // any dangling references left.
1493   if (!ConstantFwdRefs.empty()) {
1494     ConstantRefsType::const_iterator I = ConstantFwdRefs.begin();
1495     Constant* missingConst = I->second;
1496     error(utostr(ConstantFwdRefs.size()) +
1497           " unresolved constant reference exist. First one is '" +
1498           missingConst->getName() + "' of type '" +
1499           missingConst->getType()->getDescription() + "'.");
1500   }
1501
1502   checkPastBlockEnd("Constant Pool");
1503   if (Handler) Handler->handleGlobalConstantsEnd();
1504 }
1505
1506 /// Parse the contents of a function. Note that this function can be
1507 /// called lazily by materializeFunction
1508 /// @see materializeFunction
1509 void BytecodeReader::ParseFunctionBody(Function* F) {
1510
1511   unsigned FuncSize = BlockEnd - At;
1512   GlobalValue::LinkageTypes Linkage = GlobalValue::ExternalLinkage;
1513   GlobalValue::VisibilityTypes Visibility = GlobalValue::DefaultVisibility;
1514
1515   unsigned rWord = read_vbr_uint();
1516   unsigned LinkageID =  rWord & 65535;
1517   unsigned VisibilityID = rWord >> 16;
1518   switch (LinkageID) {
1519   case 0: Linkage = GlobalValue::ExternalLinkage; break;
1520   case 1: Linkage = GlobalValue::WeakLinkage; break;
1521   case 2: Linkage = GlobalValue::AppendingLinkage; break;
1522   case 3: Linkage = GlobalValue::InternalLinkage; break;
1523   case 4: Linkage = GlobalValue::LinkOnceLinkage; break;
1524   case 5: Linkage = GlobalValue::DLLImportLinkage; break;
1525   case 6: Linkage = GlobalValue::DLLExportLinkage; break;
1526   case 7: Linkage = GlobalValue::ExternalWeakLinkage; break;
1527   default:
1528     error("Invalid linkage type for Function.");
1529     Linkage = GlobalValue::InternalLinkage;
1530     break;
1531   }
1532   switch (VisibilityID) {
1533   case 0: Visibility = GlobalValue::DefaultVisibility; break;
1534   case 1: Visibility = GlobalValue::HiddenVisibility; break;
1535   case 2: Visibility = GlobalValue::ProtectedVisibility; break;
1536   default:
1537    error("Unknown visibility type: " + utostr(VisibilityID));
1538    Visibility = GlobalValue::DefaultVisibility;
1539    break;
1540   }
1541
1542   F->setLinkage(Linkage);
1543   F->setVisibility(Visibility);
1544   if (Handler) Handler->handleFunctionBegin(F,FuncSize);
1545
1546   // Keep track of how many basic blocks we have read in...
1547   unsigned BlockNum = 0;
1548   bool InsertedArguments = false;
1549
1550   BufPtr MyEnd = BlockEnd;
1551   while (At < MyEnd) {
1552     unsigned Type, Size;
1553     BufPtr OldAt = At;
1554     read_block(Type, Size);
1555
1556     switch (Type) {
1557     case BytecodeFormat::ConstantPoolBlockID:
1558       if (!InsertedArguments) {
1559         // Insert arguments into the value table before we parse the first basic
1560         // block in the function
1561         insertArguments(F);
1562         InsertedArguments = true;
1563       }
1564
1565       ParseConstantPool(FunctionValues, FunctionTypes, true);
1566       break;
1567
1568     case BytecodeFormat::InstructionListBlockID: {
1569       // Insert arguments into the value table before we parse the instruction
1570       // list for the function
1571       if (!InsertedArguments) {
1572         insertArguments(F);
1573         InsertedArguments = true;
1574       }
1575
1576       if (BlockNum)
1577         error("Already parsed basic blocks!");
1578       BlockNum = ParseInstructionList(F);
1579       break;
1580     }
1581
1582     case BytecodeFormat::ValueSymbolTableBlockID:
1583       ParseValueSymbolTable(F, &F->getValueSymbolTable());
1584       break;
1585
1586     case BytecodeFormat::TypeSymbolTableBlockID:
1587       error("Functions don't have type symbol tables");
1588       break;
1589
1590     default:
1591       At += Size;
1592       if (OldAt > At)
1593         error("Wrapped around reading bytecode.");
1594       break;
1595     }
1596     BlockEnd = MyEnd;
1597   }
1598
1599   // Make sure there were no references to non-existant basic blocks.
1600   if (BlockNum != ParsedBasicBlocks.size())
1601     error("Illegal basic block operand reference");
1602
1603   ParsedBasicBlocks.clear();
1604
1605   // Resolve forward references.  Replace any uses of a forward reference value
1606   // with the real value.
1607   while (!ForwardReferences.empty()) {
1608     std::map<std::pair<unsigned,unsigned>, Value*>::iterator
1609       I = ForwardReferences.begin();
1610     Value *V = getValue(I->first.first, I->first.second, false);
1611     Value *PlaceHolder = I->second;
1612     PlaceHolder->replaceAllUsesWith(V);
1613     ForwardReferences.erase(I);
1614     delete PlaceHolder;
1615   }
1616
1617   // Clear out function-level types...
1618   FunctionTypes.clear();
1619   freeTable(FunctionValues);
1620
1621   if (Handler) Handler->handleFunctionEnd(F);
1622 }
1623
1624 /// This function parses LLVM functions lazily. It obtains the type of the
1625 /// function and records where the body of the function is in the bytecode
1626 /// buffer. The caller can then use the ParseNextFunction and
1627 /// ParseAllFunctionBodies to get handler events for the functions.
1628 void BytecodeReader::ParseFunctionLazily() {
1629   if (FunctionSignatureList.empty())
1630     error("FunctionSignatureList empty!");
1631
1632   Function *Func = FunctionSignatureList.back();
1633   FunctionSignatureList.pop_back();
1634
1635   // Save the information for future reading of the function
1636   LazyFunctionLoadMap[Func] = LazyFunctionInfo(BlockStart, BlockEnd);
1637
1638   // This function has a body but it's not loaded so it appears `External'.
1639   // Mark it as a `Ghost' instead to notify the users that it has a body.
1640   Func->setLinkage(GlobalValue::GhostLinkage);
1641
1642   // Pretend we've `parsed' this function
1643   At = BlockEnd;
1644 }
1645
1646 /// The ParserFunction method lazily parses one function. Use this method to
1647 /// casue the parser to parse a specific function in the module. Note that
1648 /// this will remove the function from what is to be included by
1649 /// ParseAllFunctionBodies.
1650 /// @see ParseAllFunctionBodies
1651 /// @see ParseBytecode
1652 bool BytecodeReader::ParseFunction(Function* Func, std::string* ErrMsg) {
1653
1654   if (setjmp(context)) {
1655     // Set caller's error message, if requested
1656     if (ErrMsg)
1657       *ErrMsg = ErrorMsg;
1658     // Indicate an error occurred
1659     return true;
1660   }
1661
1662   // Find {start, end} pointers and slot in the map. If not there, we're done.
1663   LazyFunctionMap::iterator Fi = LazyFunctionLoadMap.find(Func);
1664
1665   // Make sure we found it
1666   if (Fi == LazyFunctionLoadMap.end()) {
1667     error("Unrecognized function of type " + Func->getType()->getDescription());
1668     return true;
1669   }
1670
1671   BlockStart = At = Fi->second.Buf;
1672   BlockEnd = Fi->second.EndBuf;
1673   assert(Fi->first == Func && "Found wrong function?");
1674
1675   this->ParseFunctionBody(Func);
1676   return false;
1677 }
1678
1679 /// The ParseAllFunctionBodies method parses through all the previously
1680 /// unparsed functions in the bytecode file. If you want to completely parse
1681 /// a bytecode file, this method should be called after Parsebytecode because
1682 /// Parsebytecode only records the locations in the bytecode file of where
1683 /// the function definitions are located. This function uses that information
1684 /// to materialize the functions.
1685 /// @see ParseBytecode
1686 bool BytecodeReader::ParseAllFunctionBodies(std::string* ErrMsg) {
1687   if (setjmp(context)) {
1688     // Set caller's error message, if requested
1689     if (ErrMsg)
1690       *ErrMsg = ErrorMsg;
1691     // Indicate an error occurred
1692     return true;
1693   }
1694
1695   for (LazyFunctionMap::iterator I = LazyFunctionLoadMap.begin(),
1696        E = LazyFunctionLoadMap.end(); I != E; ++I) {
1697     Function *Func = I->first;
1698     if (Func->hasNotBeenReadFromBytecode()) {
1699       BlockStart = At = I->second.Buf;
1700       BlockEnd = I->second.EndBuf;
1701       ParseFunctionBody(Func);
1702     }
1703   }
1704   return false;
1705 }
1706
1707 /// Parse the global type list
1708 void BytecodeReader::ParseGlobalTypes() {
1709   // Read the number of types
1710   unsigned NumEntries = read_vbr_uint();
1711   ParseTypes(ModuleTypes, NumEntries);
1712 }
1713
1714 /// Parse the Global info (types, global vars, constants)
1715 void BytecodeReader::ParseModuleGlobalInfo() {
1716
1717   if (Handler) Handler->handleModuleGlobalsBegin();
1718
1719   // SectionID - If a global has an explicit section specified, this map
1720   // remembers the ID until we can translate it into a string.
1721   std::map<GlobalValue*, unsigned> SectionID;
1722
1723   // Read global variables...
1724   unsigned VarType = read_vbr_uint();
1725   while (VarType != Type::VoidTyID) { // List is terminated by Void
1726     // VarType Fields: bit0 = isConstant, bit1 = hasInitializer, bit2,3,4 =
1727     // Linkage, bit5 = isThreadLocal, bit6+ = slot#
1728     unsigned SlotNo = VarType >> 6;
1729     unsigned LinkageID = (VarType >> 2) & 7;
1730     unsigned VisibilityID = 0;
1731     bool isConstant = VarType & 1;
1732     bool isThreadLocal = (VarType >> 5) & 1;
1733     bool hasInitializer = (VarType & 2) != 0;
1734     unsigned Alignment = 0;
1735     unsigned GlobalSectionID = 0;
1736
1737     // An extension word is present when linkage = 3 (internal) and hasinit = 0.
1738     if (LinkageID == 3 && !hasInitializer) {
1739       unsigned ExtWord = read_vbr_uint();
1740       // The extension word has this format: bit 0 = has initializer, bit 1-3 =
1741       // linkage, bit 4-8 = alignment (log2), bit 9 = has section,
1742       // bits 10-12 = visibility, bits 13+ = future use.
1743       hasInitializer = ExtWord & 1;
1744       LinkageID = (ExtWord >> 1) & 7;
1745       Alignment = (1 << ((ExtWord >> 4) & 31)) >> 1;
1746       VisibilityID = (ExtWord >> 10) & 7;
1747
1748       if (ExtWord & (1 << 9))  // Has a section ID.
1749         GlobalSectionID = read_vbr_uint();
1750     }
1751
1752     GlobalValue::LinkageTypes Linkage;
1753     switch (LinkageID) {
1754     case 0: Linkage = GlobalValue::ExternalLinkage;  break;
1755     case 1: Linkage = GlobalValue::WeakLinkage;      break;
1756     case 2: Linkage = GlobalValue::AppendingLinkage; break;
1757     case 3: Linkage = GlobalValue::InternalLinkage;  break;
1758     case 4: Linkage = GlobalValue::LinkOnceLinkage;  break;
1759     case 5: Linkage = GlobalValue::DLLImportLinkage;  break;
1760     case 6: Linkage = GlobalValue::DLLExportLinkage;  break;
1761     case 7: Linkage = GlobalValue::ExternalWeakLinkage;  break;
1762     default:
1763       error("Unknown linkage type: " + utostr(LinkageID));
1764       Linkage = GlobalValue::InternalLinkage;
1765       break;
1766     }
1767     GlobalValue::VisibilityTypes Visibility;
1768     switch (VisibilityID) {
1769     case 0: Visibility = GlobalValue::DefaultVisibility; break;
1770     case 1: Visibility = GlobalValue::HiddenVisibility; break;
1771     case 2: Visibility = GlobalValue::ProtectedVisibility; break;
1772     default:
1773       error("Unknown visibility type: " + utostr(VisibilityID));
1774       Visibility = GlobalValue::DefaultVisibility;
1775       break;
1776     }
1777
1778     const Type *Ty = getType(SlotNo);
1779     if (!Ty)
1780       error("Global has no type! SlotNo=" + utostr(SlotNo));
1781
1782     if (!isa<PointerType>(Ty))
1783       error("Global not a pointer type! Ty= " + Ty->getDescription());
1784
1785     const Type *ElTy = cast<PointerType>(Ty)->getElementType();
1786
1787     // Create the global variable...
1788     GlobalVariable *GV = new GlobalVariable(ElTy, isConstant, Linkage,
1789                                             0, "", TheModule, isThreadLocal);
1790     GV->setAlignment(Alignment);
1791     GV->setVisibility(Visibility);
1792     insertValue(GV, SlotNo, ModuleValues);
1793
1794     if (GlobalSectionID != 0)
1795       SectionID[GV] = GlobalSectionID;
1796
1797     unsigned initSlot = 0;
1798     if (hasInitializer) {
1799       initSlot = read_vbr_uint();
1800       GlobalInits.push_back(std::make_pair(GV, initSlot));
1801     }
1802
1803     // Notify handler about the global value.
1804     if (Handler)
1805       Handler->handleGlobalVariable(ElTy, isConstant, Linkage, Visibility,
1806                                     SlotNo, initSlot, isThreadLocal);
1807
1808     // Get next item
1809     VarType = read_vbr_uint();
1810   }
1811
1812   // Read the function objects for all of the functions that are coming
1813   unsigned FnSignature = read_vbr_uint();
1814
1815   // List is terminated by VoidTy.
1816   while (((FnSignature & (~0U >> 1)) >> 5) != Type::VoidTyID) {
1817     const Type *Ty = getType((FnSignature & (~0U >> 1)) >> 5);
1818     if (!isa<PointerType>(Ty) ||
1819         !isa<FunctionType>(cast<PointerType>(Ty)->getElementType())) {
1820       error("Function not a pointer to function type! Ty = " +
1821             Ty->getDescription());
1822     }
1823
1824     // We create functions by passing the underlying FunctionType to create...
1825     const FunctionType* FTy =
1826       cast<FunctionType>(cast<PointerType>(Ty)->getElementType());
1827
1828     // Insert the place holder.
1829     Function *Func = new Function(FTy, GlobalValue::ExternalLinkage,
1830                                   "", TheModule);
1831
1832     insertValue(Func, (FnSignature & (~0U >> 1)) >> 5, ModuleValues);
1833
1834     // Flags are not used yet.
1835     unsigned Flags = FnSignature & 31;
1836
1837     // Save this for later so we know type of lazily instantiated functions.
1838     // Note that known-external functions do not have FunctionInfo blocks, so we
1839     // do not add them to the FunctionSignatureList.
1840     if ((Flags & (1 << 4)) == 0)
1841       FunctionSignatureList.push_back(Func);
1842
1843     // Get the calling convention from the low bits.
1844     unsigned CC = Flags & 15;
1845     unsigned Alignment = 0;
1846     if (FnSignature & (1 << 31)) {  // Has extension word?
1847       unsigned ExtWord = read_vbr_uint();
1848       Alignment = (1 << (ExtWord & 31)) >> 1;
1849       CC |= ((ExtWord >> 5) & 15) << 4;
1850
1851       if (ExtWord & (1 << 10))  // Has a section ID.
1852         SectionID[Func] = read_vbr_uint();
1853
1854       // Parse external declaration linkage
1855       switch ((ExtWord >> 11) & 3) {
1856        case 0: break;
1857        case 1: Func->setLinkage(Function::DLLImportLinkage); break;
1858        case 2: Func->setLinkage(Function::ExternalWeakLinkage); break;
1859        default: assert(0 && "Unsupported external linkage");
1860       }
1861     }
1862
1863     Func->setCallingConv(CC-1);
1864     Func->setAlignment(Alignment);
1865
1866     if (Handler) Handler->handleFunctionDeclaration(Func);
1867
1868     // Get the next function signature.
1869     FnSignature = read_vbr_uint();
1870   }
1871
1872   // Now that the function signature list is set up, reverse it so that we can
1873   // remove elements efficiently from the back of the vector.
1874   std::reverse(FunctionSignatureList.begin(), FunctionSignatureList.end());
1875
1876   /// SectionNames - This contains the list of section names encoded in the
1877   /// moduleinfoblock.  Functions and globals with an explicit section index
1878   /// into this to get their section name.
1879   std::vector<std::string> SectionNames;
1880
1881   // Read in the dependent library information.
1882   unsigned num_dep_libs = read_vbr_uint();
1883   std::string dep_lib;
1884   while (num_dep_libs--) {
1885     dep_lib = read_str();
1886     TheModule->addLibrary(dep_lib);
1887     if (Handler)
1888       Handler->handleDependentLibrary(dep_lib);
1889   }
1890
1891   // Read target triple and place into the module.
1892   std::string triple = read_str();
1893   TheModule->setTargetTriple(triple);
1894   if (Handler)
1895     Handler->handleTargetTriple(triple);
1896
1897   // Read the data layout string and place into the module.
1898   std::string datalayout = read_str();
1899   TheModule->setDataLayout(datalayout);
1900   // FIXME: Implement
1901   // if (Handler)
1902     // Handler->handleDataLayout(datalayout);
1903
1904   if (At != BlockEnd) {
1905     // If the file has section info in it, read the section names now.
1906     unsigned NumSections = read_vbr_uint();
1907     while (NumSections--)
1908       SectionNames.push_back(read_str());
1909   }
1910
1911   // If the file has module-level inline asm, read it now.
1912   if (At != BlockEnd)
1913     TheModule->setModuleInlineAsm(read_str());
1914
1915   // If any globals are in specified sections, assign them now.
1916   for (std::map<GlobalValue*, unsigned>::iterator I = SectionID.begin(), E =
1917        SectionID.end(); I != E; ++I)
1918     if (I->second) {
1919       if (I->second > SectionID.size())
1920         error("SectionID out of range for global!");
1921       I->first->setSection(SectionNames[I->second-1]);
1922     }
1923
1924   if (At != BlockEnd) {
1925     // Read aliases...
1926     unsigned VarType = read_vbr_uint();
1927     while (VarType != Type::VoidTyID) { // List is terminated by Void
1928       unsigned TypeSlotNo     = VarType >> 3;
1929       unsigned EncodedLinkage = VarType & 3;
1930       bool isConstantAliasee  = (VarType >> 2) & 1;
1931       unsigned AliaseeSlotNo  = read_vbr_uint();
1932
1933       const Type *Ty = getType(TypeSlotNo);
1934       if (!Ty)
1935         error("Alias has no type! SlotNo=" + utostr(TypeSlotNo));
1936
1937       if (!isa<PointerType>(Ty))
1938         error("Alias not a pointer type! Ty= " + Ty->getDescription());
1939
1940       Value* V = getValue(TypeSlotNo, AliaseeSlotNo, false);
1941       if (!V && !isConstantAliasee)
1942         error("Invalid aliasee! TypeSlotNo=" + utostr(TypeSlotNo) +
1943               " SlotNo=" + utostr(AliaseeSlotNo));
1944       if (!isConstantAliasee && !isa<GlobalValue>(V))
1945         error("Aliasee is not global value! SlotNo=" + utostr(AliaseeSlotNo));
1946
1947       GlobalValue::LinkageTypes Linkage;
1948       switch (EncodedLinkage) {
1949       case 0:
1950         Linkage = GlobalValue::ExternalLinkage;
1951         break;
1952       case 1:
1953         Linkage = GlobalValue::InternalLinkage;
1954         break;
1955       case 2:
1956         Linkage = GlobalValue::WeakLinkage;
1957         break;
1958       default:
1959        assert(0 && "Unsupported encoded alias linkage");
1960       }
1961
1962       GlobalAlias *GA = new GlobalAlias(Ty, Linkage, "",
1963                                         dyn_cast_or_null<Constant>(V),
1964                                         TheModule);
1965       insertValue(GA, TypeSlotNo, ModuleValues);
1966       if (!V && isConstantAliasee)
1967         Aliasees.push_back(std::make_pair(GA, AliaseeSlotNo));
1968
1969       if (Handler) Handler->handleGlobalAlias(Ty, Linkage,
1970                                               TypeSlotNo, AliaseeSlotNo);
1971       VarType = read_vbr_uint();
1972     }
1973   }
1974
1975   // This is for future proofing... in the future extra fields may be added that
1976   // we don't understand, so we transparently ignore them.
1977   //
1978   At = BlockEnd;
1979
1980   if (Handler) Handler->handleModuleGlobalsEnd();
1981 }
1982
1983 /// Parse the version information and decode it by setting flags on the
1984 /// Reader that enable backward compatibility of the reader.
1985 void BytecodeReader::ParseVersionInfo() {
1986   unsigned RevisionNum = read_vbr_uint();
1987
1988   // We don't provide backwards compatibility in the Reader any more. To
1989   // upgrade, the user should use llvm-upgrade.
1990   if (RevisionNum < 7)
1991     error("Bytecode formats < 7 are no longer supported. Use llvm-upgrade.");
1992
1993   if (Handler) Handler->handleVersionInfo(RevisionNum);
1994 }
1995
1996 /// Parse a whole module.
1997 void BytecodeReader::ParseModule() {
1998   unsigned Type, Size;
1999
2000   FunctionSignatureList.clear(); // Just in case...
2001
2002   // Read into instance variables...
2003   ParseVersionInfo();
2004
2005   bool SeenModuleGlobalInfo = false;
2006   bool SeenGlobalTypePlane = false;
2007   BufPtr MyEnd = BlockEnd;
2008   while (At < MyEnd) {
2009     BufPtr OldAt = At;
2010     read_block(Type, Size);
2011
2012     switch (Type) {
2013
2014     case BytecodeFormat::GlobalTypePlaneBlockID:
2015       if (SeenGlobalTypePlane)
2016         error("Two GlobalTypePlane Blocks Encountered!");
2017
2018       if (Size > 0)
2019         ParseGlobalTypes();
2020       SeenGlobalTypePlane = true;
2021       break;
2022
2023     case BytecodeFormat::ModuleGlobalInfoBlockID:
2024       if (SeenModuleGlobalInfo)
2025         error("Two ModuleGlobalInfo Blocks Encountered!");
2026       ParseModuleGlobalInfo();
2027       SeenModuleGlobalInfo = true;
2028       break;
2029
2030     case BytecodeFormat::ConstantPoolBlockID:
2031       ParseConstantPool(ModuleValues, ModuleTypes,false);
2032       break;
2033
2034     case BytecodeFormat::FunctionBlockID:
2035       ParseFunctionLazily();
2036       break;
2037
2038     case BytecodeFormat::ValueSymbolTableBlockID:
2039       ParseValueSymbolTable(0, &TheModule->getValueSymbolTable());
2040       break;
2041
2042     case BytecodeFormat::TypeSymbolTableBlockID:
2043       ParseTypeSymbolTable(&TheModule->getTypeSymbolTable());
2044       break;
2045
2046     default:
2047       At += Size;
2048       if (OldAt > At) {
2049         error("Unexpected Block of Type #" + utostr(Type) + " encountered!");
2050       }
2051       break;
2052     }
2053     BlockEnd = MyEnd;
2054   }
2055
2056   // After the module constant pool has been read, we can safely initialize
2057   // global variables...
2058   while (!GlobalInits.empty()) {
2059     GlobalVariable *GV = GlobalInits.back().first;
2060     unsigned Slot = GlobalInits.back().second;
2061     GlobalInits.pop_back();
2062
2063     // Look up the initializer value...
2064     // FIXME: Preserve this type ID!
2065
2066     const llvm::PointerType* GVType = GV->getType();
2067     unsigned TypeSlot = getTypeSlot(GVType->getElementType());
2068     if (Constant *CV = getConstantValue(TypeSlot, Slot)) {
2069       if (GV->hasInitializer())
2070         error("Global *already* has an initializer?!");
2071       if (Handler) Handler->handleGlobalInitializer(GV,CV);
2072       GV->setInitializer(CV);
2073     } else
2074       error("Cannot find initializer value.");
2075   }
2076
2077   // And aliasees
2078   while (!Aliasees.empty()) {
2079     GlobalAlias *GA = Aliasees.back().first;
2080     unsigned Slot = Aliasees.back().second;
2081     Aliasees.pop_back();
2082
2083     // Look up the aliasee value...
2084     const llvm::PointerType* GAType = GA->getType();
2085     unsigned TypeSlot = getTypeSlot(GAType);
2086     if (Constant *CV = getConstantValue(TypeSlot, Slot)) {
2087       if (GA->getAliasee())
2088         error("Aliasee was *already* set?!");
2089       GA->setAliasee(CV);
2090     } else
2091       error("Cannot find aliasee value.");
2092   }
2093
2094   if (!ConstantFwdRefs.empty())
2095     error("Use of undefined constants in a module");
2096
2097   /// Make sure we pulled them all out. If we didn't then there's a declaration
2098   /// but a missing body. That's not allowed.
2099   if (!FunctionSignatureList.empty())
2100     error("Function declared, but bytecode stream ended before definition");
2101 }
2102
2103 /// This function completely parses a bytecode buffer given by the \p Buf
2104 /// and \p Length parameters.
2105 bool BytecodeReader::ParseBytecode(volatile BufPtr Buf, unsigned Length,
2106                                    const std::string &ModuleID,
2107                                    BCDecompressor_t *Decompressor,
2108                                    std::string* ErrMsg) {
2109
2110   /// We handle errors by
2111   if (setjmp(context)) {
2112     // Cleanup after error
2113     if (Handler) Handler->handleError(ErrorMsg);
2114     freeState();
2115     delete TheModule;
2116     TheModule = 0;
2117     if (decompressedBlock != 0 ) {
2118       ::free(decompressedBlock);
2119       decompressedBlock = 0;
2120     }
2121     // Set caller's error message, if requested
2122     if (ErrMsg)
2123       *ErrMsg = ErrorMsg;
2124     // Indicate an error occurred
2125     return true;
2126   }
2127
2128   RevisionNum = 0;
2129   At = MemStart = BlockStart = Buf;
2130   MemEnd = BlockEnd = Buf + Length;
2131
2132   // Create the module
2133   TheModule = new Module(ModuleID);
2134
2135   if (Handler) Handler->handleStart(TheModule, Length);
2136
2137   // Read the four bytes of the signature.
2138   unsigned Sig = read_uint();
2139
2140   // If this is a compressed file
2141   if (Sig == ('l' | ('l' << 8) | ('v' << 16) | ('c' << 24))) {
2142     if (!Decompressor) {
2143       error("Compressed bytecode found, but not decompressor available");
2144     }
2145
2146     // Invoke the decompression of the bytecode. Note that we have to skip the
2147     // file's magic number which is not part of the compressed block. Hence,
2148     // the Buf+4 and Length-4. The result goes into decompressedBlock, a data
2149     // member for retention until BytecodeReader is destructed.
2150     unsigned decompressedLength =
2151       Decompressor((char*)Buf+4,Length-4,decompressedBlock, 0);
2152
2153     // We must adjust the buffer pointers used by the bytecode reader to point
2154     // into the new decompressed block. After decompression, the
2155     // decompressedBlock will point to a contiguous memory area that has
2156     // the decompressed data.
2157     At = MemStart = BlockStart = Buf = (BufPtr) decompressedBlock;
2158     MemEnd = BlockEnd = Buf + decompressedLength;
2159
2160   // else if this isn't a regular (uncompressed) bytecode file, then its
2161   // and error, generate that now.
2162   } else if (Sig != ('l' | ('l' << 8) | ('v' << 16) | ('m' << 24))) {
2163     error("Invalid bytecode signature: " + utohexstr(Sig));
2164   }
2165
2166   // Tell the handler we're starting a module
2167   if (Handler) Handler->handleModuleBegin(ModuleID);
2168
2169   // Get the module block and size and verify. This is handled specially
2170   // because the module block/size is always written in long format. Other
2171   // blocks are written in short format so the read_block method is used.
2172   unsigned Type, Size;
2173   Type = read_uint();
2174   Size = read_uint();
2175   if (Type != BytecodeFormat::ModuleBlockID) {
2176     error("Expected Module Block! Type:" + utostr(Type) + ", Size:"
2177           + utostr(Size));
2178   }
2179
2180   // It looks like the darwin ranlib program is broken, and adds trailing
2181   // garbage to the end of some bytecode files.  This hack allows the bc
2182   // reader to ignore trailing garbage on bytecode files.
2183   if (At + Size < MemEnd)
2184     MemEnd = BlockEnd = At+Size;
2185
2186   if (At + Size != MemEnd)
2187     error("Invalid Top Level Block Length! Type:" + utostr(Type)
2188           + ", Size:" + utostr(Size));
2189
2190   // Parse the module contents
2191   this->ParseModule();
2192
2193   // Check for missing functions
2194   if (hasFunctions())
2195     error("Function expected, but bytecode stream ended!");
2196
2197   // Tell the handler we're done with the module
2198   if (Handler)
2199     Handler->handleModuleEnd(ModuleID);
2200
2201   // Tell the handler we're finished the parse
2202   if (Handler) Handler->handleFinish();
2203
2204   return false;
2205
2206 }
2207
2208 //===----------------------------------------------------------------------===//
2209 //=== Default Implementations of Handler Methods
2210 //===----------------------------------------------------------------------===//
2211
2212 BytecodeHandler::~BytecodeHandler() {}