lib/Bytecode/Reader/Reader.cpp

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