LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

Reader.cpp

Go to the documentation of this file.
00001 //===- Reader.cpp - Code to read bytecode files ---------------------------===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This library implements the functionality defined in llvm/Bytecode/Reader.h
00011 //
00012 // Note that this library should be as fast as possible, reentrant, and 
00013 // threadsafe!!
00014 //
00015 // TODO: Allow passing in an option to ignore the symbol table
00016 //
00017 //===----------------------------------------------------------------------===//
00018 
00019 #include "Reader.h"
00020 #include "llvm/Bytecode/BytecodeHandler.h"
00021 #include "llvm/BasicBlock.h"
00022 #include "llvm/Constants.h"
00023 #include "llvm/Instructions.h"
00024 #include "llvm/SymbolTable.h"
00025 #include "llvm/Bytecode/Format.h"
00026 #include "llvm/Support/GetElementPtrTypeIterator.h"
00027 #include "llvm/Support/Compressor.h"
00028 #include "llvm/ADT/StringExtras.h"
00029 #include <sstream>
00030 #include <algorithm>
00031 using namespace llvm;
00032 
00033 namespace {
00034 
00035 /// @brief A class for maintaining the slot number definition
00036 /// as a placeholder for the actual definition for forward constants defs.
00037 class ConstantPlaceHolder : public ConstantExpr {
00038   unsigned ID;
00039   ConstantPlaceHolder();                       // DO NOT IMPLEMENT
00040   void operator=(const ConstantPlaceHolder &); // DO NOT IMPLEMENT
00041 public:
00042   ConstantPlaceHolder(const Type *Ty, unsigned id) 
00043     : ConstantExpr(Instruction::UserOp1, Constant::getNullValue(Ty), Ty),
00044     ID(id) {}
00045   unsigned getID() { return ID; }
00046 };
00047 
00048 }
00049 
00050 // Provide some details on error
00051 inline void BytecodeReader::error(std::string err) {
00052   err +=  " (Vers=" ;
00053   err += itostr(RevisionNum) ;
00054   err += ", Pos=" ;
00055   err += itostr(At-MemStart);
00056   err += ")";
00057   throw err;
00058 }
00059 
00060 //===----------------------------------------------------------------------===//
00061 // Bytecode Reading Methods
00062 //===----------------------------------------------------------------------===//
00063 
00064 /// Determine if the current block being read contains any more data.
00065 inline bool BytecodeReader::moreInBlock() {
00066   return At < BlockEnd;
00067 }
00068 
00069 /// Throw an error if we've read past the end of the current block
00070 inline void BytecodeReader::checkPastBlockEnd(const char * block_name) {
00071   if (At > BlockEnd)
00072     error(std::string("Attempt to read past the end of ") + block_name +
00073           " block.");
00074 }
00075 
00076 /// Align the buffer position to a 32 bit boundary
00077 inline void BytecodeReader::align32() {
00078   if (hasAlignment) {
00079     BufPtr Save = At;
00080     At = (const unsigned char *)((unsigned long)(At+3) & (~3UL));
00081     if (At > Save) 
00082       if (Handler) Handler->handleAlignment(At - Save);
00083     if (At > BlockEnd) 
00084       error("Ran out of data while aligning!");
00085   }
00086 }
00087 
00088 /// Read a whole unsigned integer
00089 inline unsigned BytecodeReader::read_uint() {
00090   if (At+4 > BlockEnd) 
00091     error("Ran out of data reading uint!");
00092   At += 4;
00093   return At[-4] | (At[-3] << 8) | (At[-2] << 16) | (At[-1] << 24);
00094 }
00095 
00096 /// Read a variable-bit-rate encoded unsigned integer
00097 inline unsigned BytecodeReader::read_vbr_uint() {
00098   unsigned Shift = 0;
00099   unsigned Result = 0;
00100   BufPtr Save = At;
00101   
00102   do {
00103     if (At == BlockEnd) 
00104       error("Ran out of data reading vbr_uint!");
00105     Result |= (unsigned)((*At++) & 0x7F) << Shift;
00106     Shift += 7;
00107   } while (At[-1] & 0x80);
00108   if (Handler) Handler->handleVBR32(At-Save);
00109   return Result;
00110 }
00111 
00112 /// Read a variable-bit-rate encoded unsigned 64-bit integer.
00113 inline uint64_t BytecodeReader::read_vbr_uint64() {
00114   unsigned Shift = 0;
00115   uint64_t Result = 0;
00116   BufPtr Save = At;
00117   
00118   do {
00119     if (At == BlockEnd) 
00120       error("Ran out of data reading vbr_uint64!");
00121     Result |= (uint64_t)((*At++) & 0x7F) << Shift;
00122     Shift += 7;
00123   } while (At[-1] & 0x80);
00124   if (Handler) Handler->handleVBR64(At-Save);
00125   return Result;
00126 }
00127 
00128 /// Read a variable-bit-rate encoded signed 64-bit integer.
00129 inline int64_t BytecodeReader::read_vbr_int64() {
00130   uint64_t R = read_vbr_uint64();
00131   if (R & 1) {
00132     if (R != 1)
00133       return -(int64_t)(R >> 1);
00134     else   // There is no such thing as -0 with integers.  "-0" really means
00135            // 0x8000000000000000.
00136       return 1LL << 63;
00137   } else
00138     return  (int64_t)(R >> 1);
00139 }
00140 
00141 /// Read a pascal-style string (length followed by text)
00142 inline std::string BytecodeReader::read_str() {
00143   unsigned Size = read_vbr_uint();
00144   const unsigned char *OldAt = At;
00145   At += Size;
00146   if (At > BlockEnd)             // Size invalid?
00147     error("Ran out of data reading a string!");
00148   return std::string((char*)OldAt, Size);
00149 }
00150 
00151 /// Read an arbitrary block of data
00152 inline void BytecodeReader::read_data(void *Ptr, void *End) {
00153   unsigned char *Start = (unsigned char *)Ptr;
00154   unsigned Amount = (unsigned char *)End - Start;
00155   if (At+Amount > BlockEnd) 
00156     error("Ran out of data!");
00157   std::copy(At, At+Amount, Start);
00158   At += Amount;
00159 }
00160 
00161 /// Read a float value in little-endian order
00162 inline void BytecodeReader::read_float(float& FloatVal) {
00163   /// FIXME: This isn't optimal, it has size problems on some platforms
00164   /// where FP is not IEEE.
00165   union {
00166     float f;
00167     uint32_t i;
00168   } FloatUnion;
00169   FloatUnion.i = At[0] | (At[1] << 8) | (At[2] << 16) | (At[3] << 24);
00170   At+=sizeof(uint32_t);
00171   FloatVal = FloatUnion.f;
00172 }
00173 
00174 /// Read a double value in little-endian order
00175 inline void BytecodeReader::read_double(double& DoubleVal) {
00176   /// FIXME: This isn't optimal, it has size problems on some platforms
00177   /// where FP is not IEEE.
00178   union {
00179     double d;
00180     uint64_t i;
00181   } DoubleUnion;
00182   DoubleUnion.i = (uint64_t(At[0]) <<  0) | (uint64_t(At[1]) << 8) | 
00183                   (uint64_t(At[2]) << 16) | (uint64_t(At[3]) << 24) |
00184                   (uint64_t(At[4]) << 32) | (uint64_t(At[5]) << 40) | 
00185                   (uint64_t(At[6]) << 48) | (uint64_t(At[7]) << 56);
00186   At+=sizeof(uint64_t);
00187   DoubleVal = DoubleUnion.d;
00188 }
00189 
00190 /// Read a block header and obtain its type and size
00191 inline void BytecodeReader::read_block(unsigned &Type, unsigned &Size) {
00192   if ( hasLongBlockHeaders ) {
00193     Type = read_uint();
00194     Size = read_uint();
00195     switch (Type) {
00196     case BytecodeFormat::Reserved_DoNotUse : 
00197       error("Reserved_DoNotUse used as Module Type?");
00198       Type = BytecodeFormat::ModuleBlockID; break;
00199     case BytecodeFormat::Module: 
00200       Type = BytecodeFormat::ModuleBlockID; break;
00201     case BytecodeFormat::Function:
00202       Type = BytecodeFormat::FunctionBlockID; break;
00203     case BytecodeFormat::ConstantPool:
00204       Type = BytecodeFormat::ConstantPoolBlockID; break;
00205     case BytecodeFormat::SymbolTable:
00206       Type = BytecodeFormat::SymbolTableBlockID; break;
00207     case BytecodeFormat::ModuleGlobalInfo:
00208       Type = BytecodeFormat::ModuleGlobalInfoBlockID; break;
00209     case BytecodeFormat::GlobalTypePlane:
00210       Type = BytecodeFormat::GlobalTypePlaneBlockID; break;
00211     case BytecodeFormat::InstructionList:
00212       Type = BytecodeFormat::InstructionListBlockID; break;
00213     case BytecodeFormat::CompactionTable:
00214       Type = BytecodeFormat::CompactionTableBlockID; break;
00215     case BytecodeFormat::BasicBlock:
00216       /// This block type isn't used after version 1.1. However, we have to
00217       /// still allow the value in case this is an old bc format file.
00218       /// We just let its value creep thru.
00219       break;
00220     default:
00221       error("Invalid block id found: " + utostr(Type));
00222       break;
00223     }
00224   } else {
00225     Size = read_uint();
00226     Type = Size & 0x1F; // mask low order five bits
00227     Size >>= 5; // get rid of five low order bits, leaving high 27
00228   }
00229   BlockStart = At;
00230   if (At + Size > BlockEnd)
00231     error("Attempt to size a block past end of memory");
00232   BlockEnd = At + Size;
00233   if (Handler) Handler->handleBlock(Type, BlockStart, Size);
00234 }
00235 
00236 
00237 /// In LLVM 1.2 and before, Types were derived from Value and so they were
00238 /// written as part of the type planes along with any other Value. In LLVM
00239 /// 1.3 this changed so that Type does not derive from Value. Consequently,
00240 /// the BytecodeReader's containers for Values can't contain Types because
00241 /// there's no inheritance relationship. This means that the "Type Type"
00242 /// plane is defunct along with the Type::TypeTyID TypeID. In LLVM 1.3 
00243 /// whenever a bytecode construct must have both types and values together, 
00244 /// the types are always read/written first and then the Values. Furthermore
00245 /// since Type::TypeTyID no longer exists, its value (12) now corresponds to
00246 /// Type::LabelTyID. In order to overcome this we must "sanitize" all the
00247 /// type TypeIDs we encounter. For LLVM 1.3 bytecode files, there's no change.
00248 /// For LLVM 1.2 and before, this function will decrement the type id by
00249 /// one to account for the missing Type::TypeTyID enumerator if the value is
00250 /// larger than 12 (Type::LabelTyID). If the value is exactly 12, then this
00251 /// function returns true, otherwise false. This helps detect situations
00252 /// where the pre 1.3 bytecode is indicating that what follows is a type.
00253 /// @returns true iff type id corresponds to pre 1.3 "type type" 
00254 inline bool BytecodeReader::sanitizeTypeId(unsigned &TypeId) {
00255   if (hasTypeDerivedFromValue) { /// do nothing if 1.3 or later
00256     if (TypeId == Type::LabelTyID) {
00257       TypeId = Type::VoidTyID; // sanitize it
00258       return true; // indicate we got TypeTyID in pre 1.3 bytecode
00259     } else if (TypeId > Type::LabelTyID)
00260       --TypeId; // shift all planes down because type type plane is missing
00261   }
00262   return false;
00263 }
00264 
00265 /// Reads a vbr uint to read in a type id and does the necessary
00266 /// conversion on it by calling sanitizeTypeId.
00267 /// @returns true iff \p TypeId read corresponds to a pre 1.3 "type type"
00268 /// @see sanitizeTypeId
00269 inline bool BytecodeReader::read_typeid(unsigned &TypeId) {
00270   TypeId = read_vbr_uint();
00271   if ( !has32BitTypes )
00272     if ( TypeId == 0x00FFFFFF )
00273       TypeId = read_vbr_uint();
00274   return sanitizeTypeId(TypeId);
00275 }
00276 
00277 //===----------------------------------------------------------------------===//
00278 // IR Lookup Methods
00279 //===----------------------------------------------------------------------===//
00280 
00281 /// Determine if a type id has an implicit null value
00282 inline bool BytecodeReader::hasImplicitNull(unsigned TyID) {
00283   if (!hasExplicitPrimitiveZeros)
00284     return TyID != Type::LabelTyID && TyID != Type::VoidTyID;
00285   return TyID >= Type::FirstDerivedTyID;
00286 }
00287 
00288 /// Obtain a type given a typeid and account for things like compaction tables,
00289 /// function level vs module level, and the offsetting for the primitive types.
00290 const Type *BytecodeReader::getType(unsigned ID) {
00291   if (ID < Type::FirstDerivedTyID)
00292     if (const Type *T = Type::getPrimitiveType((Type::TypeID)ID))
00293       return T;   // Asked for a primitive type...
00294 
00295   // Otherwise, derived types need offset...
00296   ID -= Type::FirstDerivedTyID;
00297 
00298   if (!CompactionTypes.empty()) {
00299     if (ID >= CompactionTypes.size())
00300       error("Type ID out of range for compaction table!");
00301     return CompactionTypes[ID].first;
00302   }
00303 
00304   // Is it a module-level type?
00305   if (ID < ModuleTypes.size())
00306     return ModuleTypes[ID].get();
00307 
00308   // Nope, is it a function-level type?
00309   ID -= ModuleTypes.size();
00310   if (ID < FunctionTypes.size())
00311     return FunctionTypes[ID].get();
00312 
00313   error("Illegal type reference!");
00314   return Type::VoidTy;
00315 }
00316 
00317 /// Get a sanitized type id. This just makes sure that the \p ID
00318 /// is both sanitized and not the "type type" of pre-1.3 bytecode.
00319 /// @see sanitizeTypeId
00320 inline const Type* BytecodeReader::getSanitizedType(unsigned& ID) {
00321   if (sanitizeTypeId(ID))
00322     error("Invalid type id encountered");
00323   return getType(ID);
00324 }
00325 
00326 /// This method just saves some coding. It uses read_typeid to read
00327 /// in a sanitized type id, errors that its not the type type, and
00328 /// then calls getType to return the type value.
00329 inline const Type* BytecodeReader::readSanitizedType() {
00330   unsigned ID;
00331   if (read_typeid(ID))
00332     error("Invalid type id encountered");
00333   return getType(ID);
00334 }
00335 
00336 /// Get the slot number associated with a type accounting for primitive
00337 /// types, compaction tables, and function level vs module level.
00338 unsigned BytecodeReader::getTypeSlot(const Type *Ty) {
00339   if (Ty->isPrimitiveType())
00340     return Ty->getTypeID();
00341 
00342   // Scan the compaction table for the type if needed.
00343   if (!CompactionTypes.empty()) {
00344     for (unsigned i = 0, e = CompactionTypes.size(); i != e; ++i)
00345       if (CompactionTypes[i].first == Ty)
00346         return Type::FirstDerivedTyID + i; 
00347 
00348     error("Couldn't find type specified in compaction table!");
00349   }
00350 
00351   // Check the function level types first...
00352   TypeListTy::iterator I = std::find(FunctionTypes.begin(),
00353                                      FunctionTypes.end(), Ty);
00354 
00355   if (I != FunctionTypes.end())
00356     return Type::FirstDerivedTyID + ModuleTypes.size() + 
00357            (&*I - &FunctionTypes[0]);
00358 
00359   // Check the module level types now...
00360   I = std::find(ModuleTypes.begin(), ModuleTypes.end(), Ty);
00361   if (I == ModuleTypes.end())
00362     error("Didn't find type in ModuleTypes.");
00363   return Type::FirstDerivedTyID + (&*I - &ModuleTypes[0]);
00364 }
00365 
00366 /// This is just like getType, but when a compaction table is in use, it is
00367 /// ignored.  It also ignores function level types.
00368 /// @see getType
00369 const Type *BytecodeReader::getGlobalTableType(unsigned Slot) {
00370   if (Slot < Type::FirstDerivedTyID) {
00371     const Type *Ty = Type::getPrimitiveType((Type::TypeID)Slot);
00372     if (!Ty)
00373       error("Not a primitive type ID?");
00374     return Ty;
00375   }
00376   Slot -= Type::FirstDerivedTyID;
00377   if (Slot >= ModuleTypes.size())
00378     error("Illegal compaction table type reference!");
00379   return ModuleTypes[Slot];
00380 }
00381 
00382 /// This is just like getTypeSlot, but when a compaction table is in use, it
00383 /// is ignored. It also ignores function level types.
00384 unsigned BytecodeReader::getGlobalTableTypeSlot(const Type *Ty) {
00385   if (Ty->isPrimitiveType())
00386     return Ty->getTypeID();
00387   TypeListTy::iterator I = std::find(ModuleTypes.begin(),
00388                                       ModuleTypes.end(), Ty);
00389   if (I == ModuleTypes.end())
00390     error("Didn't find type in ModuleTypes.");
00391   return Type::FirstDerivedTyID + (&*I - &ModuleTypes[0]);
00392 }
00393 
00394 /// Retrieve a value of a given type and slot number, possibly creating 
00395 /// it if it doesn't already exist. 
00396 Value * BytecodeReader::getValue(unsigned type, unsigned oNum, bool Create) {
00397   assert(type != Type::LabelTyID && "getValue() cannot get blocks!");
00398   unsigned Num = oNum;
00399 
00400   // If there is a compaction table active, it defines the low-level numbers.
00401   // If not, the module values define the low-level numbers.
00402   if (CompactionValues.size() > type && !CompactionValues[type].empty()) {
00403     if (Num < CompactionValues[type].size())
00404       return CompactionValues[type][Num];
00405     Num -= CompactionValues[type].size();
00406   } else {
00407     // By default, the global type id is the type id passed in
00408     unsigned GlobalTyID = type;
00409 
00410     // If the type plane was compactified, figure out the global type ID by
00411     // adding the derived type ids and the distance.
00412     if (!CompactionTypes.empty() && type >= Type::FirstDerivedTyID)
00413       GlobalTyID = CompactionTypes[type-Type::FirstDerivedTyID].second;
00414 
00415     if (hasImplicitNull(GlobalTyID)) {
00416       if (Num == 0)
00417         return Constant::getNullValue(getType(type));
00418       --Num;
00419     }
00420 
00421     if (GlobalTyID < ModuleValues.size() && ModuleValues[GlobalTyID]) {
00422       if (Num < ModuleValues[GlobalTyID]->size())
00423         return ModuleValues[GlobalTyID]->getOperand(Num);
00424       Num -= ModuleValues[GlobalTyID]->size();
00425     }
00426   }
00427 
00428   if (FunctionValues.size() > type && 
00429       FunctionValues[type] && 
00430       Num < FunctionValues[type]->size())
00431     return FunctionValues[type]->getOperand(Num);
00432 
00433   if (!Create) return 0;  // Do not create a placeholder?
00434 
00435   // Did we already create a place holder?
00436   std::pair<unsigned,unsigned> KeyValue(type, oNum);
00437   ForwardReferenceMap::iterator I = ForwardReferences.lower_bound(KeyValue);
00438   if (I != ForwardReferences.end() && I->first == KeyValue)
00439     return I->second;   // We have already created this placeholder
00440 
00441   // If the type exists (it should)
00442   if (const Type* Ty = getType(type)) {
00443     // Create the place holder
00444     Value *Val = new Argument(Ty);
00445     ForwardReferences.insert(I, std::make_pair(KeyValue, Val));
00446     return Val;
00447   }
00448   throw "Can't create placeholder for value of type slot #" + utostr(type);
00449 }
00450 
00451 /// This is just like getValue, but when a compaction table is in use, it 
00452 /// is ignored.  Also, no forward references or other fancy features are 
00453 /// supported.
00454 Value* BytecodeReader::getGlobalTableValue(unsigned TyID, unsigned SlotNo) {
00455   if (SlotNo == 0)
00456     return Constant::getNullValue(getType(TyID));
00457 
00458   if (!CompactionTypes.empty() && TyID >= Type::FirstDerivedTyID) {
00459     TyID -= Type::FirstDerivedTyID;
00460     if (TyID >= CompactionTypes.size())
00461       error("Type ID out of range for compaction table!");
00462     TyID = CompactionTypes[TyID].second;
00463   }
00464 
00465   --SlotNo;
00466 
00467   if (TyID >= ModuleValues.size() || ModuleValues[TyID] == 0 ||
00468       SlotNo >= ModuleValues[TyID]->size()) {
00469     if (TyID >= ModuleValues.size() || ModuleValues[TyID] == 0)
00470       error("Corrupt compaction table entry!"
00471             + utostr(TyID) + ", " + utostr(SlotNo) + ": " 
00472             + utostr(ModuleValues.size()));
00473     else 
00474       error("Corrupt compaction table entry!"
00475             + utostr(TyID) + ", " + utostr(SlotNo) + ": " 
00476             + utostr(ModuleValues.size()) + ", "
00477             + utohexstr(reinterpret_cast<uint64_t>(((void*)ModuleValues[TyID])))
00478             + ", "
00479             + utostr(ModuleValues[TyID]->size()));
00480   }
00481   return ModuleValues[TyID]->getOperand(SlotNo);
00482 }
00483 
00484 /// Just like getValue, except that it returns a null pointer
00485 /// only on error.  It always returns a constant (meaning that if the value is
00486 /// defined, but is not a constant, that is an error).  If the specified
00487 /// constant hasn't been parsed yet, a placeholder is defined and used.  
00488 /// Later, after the real value is parsed, the placeholder is eliminated.
00489 Constant* BytecodeReader::getConstantValue(unsigned TypeSlot, unsigned Slot) {
00490   if (Value *V = getValue(TypeSlot, Slot, false))
00491     if (Constant *C = dyn_cast<Constant>(V))
00492       return C;   // If we already have the value parsed, just return it
00493     else
00494       error("Value for slot " + utostr(Slot) + 
00495             " is expected to be a constant!");
00496 
00497   const Type *Ty = getType(TypeSlot);
00498   std::pair<const Type*, unsigned> Key(Ty, Slot);
00499   ConstantRefsType::iterator I = ConstantFwdRefs.lower_bound(Key);
00500 
00501   if (I != ConstantFwdRefs.end() && I->first == Key) {
00502     return I->second;
00503   } else {
00504     // Create a placeholder for the constant reference and
00505     // keep track of the fact that we have a forward ref to recycle it
00506     Constant *C = new ConstantPlaceHolder(Ty, Slot);
00507     
00508     // Keep track of the fact that we have a forward ref to recycle it
00509     ConstantFwdRefs.insert(I, std::make_pair(Key, C));
00510     return C;
00511   }
00512 }
00513 
00514 //===----------------------------------------------------------------------===//
00515 // IR Construction Methods
00516 //===----------------------------------------------------------------------===//
00517 
00518 /// As values are created, they are inserted into the appropriate place
00519 /// with this method. The ValueTable argument must be one of ModuleValues
00520 /// or FunctionValues data members of this class.
00521 unsigned BytecodeReader::insertValue(Value *Val, unsigned type, 
00522                                       ValueTable &ValueTab) {
00523   assert((!isa<Constant>(Val) || !cast<Constant>(Val)->isNullValue()) ||
00524           !hasImplicitNull(type) &&
00525          "Cannot read null values from bytecode!");
00526 
00527   if (ValueTab.size() <= type)
00528     ValueTab.resize(type+1);
00529 
00530   if (!ValueTab[type]) ValueTab[type] = new ValueList();
00531 
00532   ValueTab[type]->push_back(Val);
00533 
00534   bool HasOffset = hasImplicitNull(type);
00535   return ValueTab[type]->size()-1 + HasOffset;
00536 }
00537 
00538 /// Insert the arguments of a function as new values in the reader.
00539 void BytecodeReader::insertArguments(Function* F) {
00540   const FunctionType *FT = F->getFunctionType();
00541   Function::aiterator AI = F->abegin();
00542   for (FunctionType::param_iterator It = FT->param_begin();
00543        It != FT->param_end(); ++It, ++AI)
00544     insertValue(AI, getTypeSlot(AI->getType()), FunctionValues);
00545 }
00546 
00547 //===----------------------------------------------------------------------===//
00548 // Bytecode Parsing Methods
00549 //===----------------------------------------------------------------------===//
00550 
00551 /// This method parses a single instruction. The instruction is
00552 /// inserted at the end of the \p BB provided. The arguments of
00553 /// the instruction are provided in the \p Oprnds vector.
00554 void BytecodeReader::ParseInstruction(std::vector<unsigned> &Oprnds,
00555                                       BasicBlock* BB) {
00556   BufPtr SaveAt = At;
00557 
00558   // Clear instruction data
00559   Oprnds.clear();
00560   unsigned iType = 0;
00561   unsigned Opcode = 0;
00562   unsigned Op = read_uint();
00563 
00564   // bits   Instruction format:        Common to all formats
00565   // --------------------------
00566   // 01-00: Opcode type, fixed to 1.
00567   // 07-02: Opcode
00568   Opcode    = (Op >> 2) & 63;
00569   Oprnds.resize((Op >> 0) & 03);
00570 
00571   // Extract the operands
00572   switch (Oprnds.size()) {
00573   case 1:
00574     // bits   Instruction format:
00575     // --------------------------
00576     // 19-08: Resulting type plane
00577     // 31-20: Operand #1 (if set to (2^12-1), then zero operands)
00578     //
00579     iType   = (Op >>  8) & 4095;
00580     Oprnds[0] = (Op >> 20) & 4095;
00581     if (Oprnds[0] == 4095)    // Handle special encoding for 0 operands...
00582       Oprnds.resize(0);
00583     break;
00584   case 2:
00585     // bits   Instruction format:
00586     // --------------------------
00587     // 15-08: Resulting type plane
00588     // 23-16: Operand #1
00589     // 31-24: Operand #2  
00590     //
00591     iType   = (Op >>  8) & 255;
00592     Oprnds[0] = (Op >> 16) & 255;
00593     Oprnds[1] = (Op >> 24) & 255;
00594     break;
00595   case 3:
00596     // bits   Instruction format:
00597     // --------------------------
00598     // 13-08: Resulting type plane
00599     // 19-14: Operand #1
00600     // 25-20: Operand #2
00601     // 31-26: Operand #3
00602     //
00603     iType   = (Op >>  8) & 63;
00604     Oprnds[0] = (Op >> 14) & 63;
00605     Oprnds[1] = (Op >> 20) & 63;
00606     Oprnds[2] = (Op >> 26) & 63;
00607     break;
00608   case 0:
00609     At -= 4;  // Hrm, try this again...
00610     Opcode = read_vbr_uint();
00611     Opcode >>= 2;
00612     iType = read_vbr_uint();
00613 
00614     unsigned NumOprnds = read_vbr_uint();
00615     Oprnds.resize(NumOprnds);
00616 
00617     if (NumOprnds == 0)
00618       error("Zero-argument instruction found; this is invalid.");
00619 
00620     for (unsigned i = 0; i != NumOprnds; ++i)
00621       Oprnds[i] = read_vbr_uint();
00622     align32();
00623     break;
00624   }
00625 
00626   const Type *InstTy = getSanitizedType(iType);
00627 
00628   // We have enough info to inform the handler now.
00629   if (Handler) Handler->handleInstruction(Opcode, InstTy, Oprnds, At-SaveAt);
00630 
00631   // Declare the resulting instruction we'll build.
00632   Instruction *Result = 0;
00633 
00634   // If this is a bytecode format that did not include the unreachable
00635   // instruction, bump up all opcodes numbers to make space.
00636   if (hasNoUnreachableInst) {
00637     if (Opcode >= Instruction::Unreachable &&
00638         Opcode < 62) {
00639       ++Opcode;
00640     }
00641   }
00642 
00643   // Handle binary operators
00644   if (Opcode >= Instruction::BinaryOpsBegin &&
00645       Opcode <  Instruction::BinaryOpsEnd  && Oprnds.size() == 2)
00646     Result = BinaryOperator::create((Instruction::BinaryOps)Opcode,
00647                                     getValue(iType, Oprnds[0]),
00648                                     getValue(iType, Oprnds[1]));
00649 
00650   switch (Opcode) {
00651   default: 
00652     if (Result == 0) 
00653       error("Illegal instruction read!");
00654     break;
00655   case Instruction::VAArg:
00656     Result = new VAArgInst(getValue(iType, Oprnds[0]), 
00657                            getSanitizedType(Oprnds[1]));
00658     break;
00659   case Instruction::VANext:
00660     Result = new VANextInst(getValue(iType, Oprnds[0]), 
00661                             getSanitizedType(Oprnds[1]));
00662     break;
00663   case Instruction::Cast:
00664     Result = new CastInst(getValue(iType, Oprnds[0]), 
00665                           getSanitizedType(Oprnds[1]));
00666     break;
00667   case Instruction::Select:
00668     Result = new SelectInst(getValue(Type::BoolTyID, Oprnds[0]),
00669                             getValue(iType, Oprnds[1]),
00670                             getValue(iType, Oprnds[2]));
00671     break;
00672   case Instruction::PHI: {
00673     if (Oprnds.size() == 0 || (Oprnds.size() & 1))
00674       error("Invalid phi node encountered!");
00675 
00676     PHINode *PN = new PHINode(InstTy);
00677     PN->op_reserve(Oprnds.size());
00678     for (unsigned i = 0, e = Oprnds.size(); i != e; i += 2)
00679       PN->addIncoming(getValue(iType, Oprnds[i]), getBasicBlock(Oprnds[i+1]));
00680     Result = PN;
00681     break;
00682   }
00683 
00684   case Instruction::Shl:
00685   case Instruction::Shr:
00686     Result = new ShiftInst((Instruction::OtherOps)Opcode,
00687                            getValue(iType, Oprnds[0]),
00688                            getValue(Type::UByteTyID, Oprnds[1]));
00689     break;
00690   case Instruction::Ret:
00691     if (Oprnds.size() == 0)
00692       Result = new ReturnInst();
00693     else if (Oprnds.size() == 1)
00694       Result = new ReturnInst(getValue(iType, Oprnds[0]));
00695     else
00696       error("Unrecognized instruction!");
00697     break;
00698 
00699   case Instruction::Br:
00700     if (Oprnds.size() == 1)
00701       Result = new BranchInst(getBasicBlock(Oprnds[0]));
00702     else if (Oprnds.size() == 3)
00703       Result = new BranchInst(getBasicBlock(Oprnds[0]), 
00704           getBasicBlock(Oprnds[1]), getValue(Type::BoolTyID , Oprnds[2]));
00705     else
00706       error("Invalid number of operands for a 'br' instruction!");
00707     break;
00708   case Instruction::Switch: {
00709     if (Oprnds.size() & 1)
00710       error("Switch statement with odd number of arguments!");
00711 
00712     SwitchInst *I = new SwitchInst(getValue(iType, Oprnds[0]),
00713                                    getBasicBlock(Oprnds[1]));
00714     for (unsigned i = 2, e = Oprnds.size(); i != e; i += 2)
00715       I->addCase(cast<Constant>(getValue(iType, Oprnds[i])),
00716                  getBasicBlock(Oprnds[i+1]));
00717     Result = I;
00718     break;
00719   }
00720 
00721   case Instruction::Call: {
00722     if (Oprnds.size() == 0)
00723       error("Invalid call instruction encountered!");
00724 
00725     Value *F = getValue(iType, Oprnds[0]);
00726 
00727     // Check to make sure we have a pointer to function type
00728     const PointerType *PTy = dyn_cast<PointerType>(F->getType());
00729     if (PTy == 0) error("Call to non function pointer value!");
00730     const FunctionType *FTy = dyn_cast<FunctionType>(PTy->getElementType());
00731     if (FTy == 0) error("Call to non function pointer value!");
00732 
00733     std::vector<Value *> Params;
00734     if (!FTy->isVarArg()) {
00735       FunctionType::param_iterator It = FTy->param_begin();
00736 
00737       for (unsigned i = 1, e = Oprnds.size(); i != e; ++i) {
00738         if (It == FTy->param_end())
00739           error("Invalid call instruction!");
00740         Params.push_back(getValue(getTypeSlot(*It++), Oprnds[i]));
00741       }
00742       if (It != FTy->param_end())
00743         error("Invalid call instruction!");
00744     } else {
00745       Oprnds.erase(Oprnds.begin(), Oprnds.begin()+1);
00746 
00747       unsigned FirstVariableOperand;
00748       if (Oprnds.size() < FTy->getNumParams())
00749         error("Call instruction missing operands!");
00750 
00751       // Read all of the fixed arguments
00752       for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
00753         Params.push_back(getValue(getTypeSlot(FTy->getParamType(i)),Oprnds[i]));
00754       
00755       FirstVariableOperand = FTy->getNumParams();
00756 
00757       if ((Oprnds.size()-FirstVariableOperand) & 1) 
00758         error("Invalid call instruction!");   // Must be pairs of type/value
00759         
00760       for (unsigned i = FirstVariableOperand, e = Oprnds.size(); 
00761            i != e; i += 2)
00762         Params.push_back(getValue(Oprnds[i], Oprnds[i+1]));
00763     }
00764 
00765     Result = new CallInst(F, Params);
00766     break;
00767   }
00768   case Instruction::Invoke: {
00769     if (Oprnds.size() < 3) 
00770       error("Invalid invoke instruction!");
00771     Value *F = getValue(iType, Oprnds[0]);
00772 
00773     // Check to make sure we have a pointer to function type
00774     const PointerType *PTy = dyn_cast<PointerType>(F->getType());
00775     if (PTy == 0) 
00776       error("Invoke to non function pointer value!");
00777     const FunctionType *FTy = dyn_cast<FunctionType>(PTy->getElementType());
00778     if (FTy == 0) 
00779       error("Invoke to non function pointer value!");
00780 
00781     std::vector<Value *> Params;
00782     BasicBlock *Normal, *Except;
00783 
00784     if (!FTy->isVarArg()) {
00785       Normal = getBasicBlock(Oprnds[1]);
00786       Except = getBasicBlock(Oprnds[2]);
00787 
00788       FunctionType::param_iterator It = FTy->param_begin();
00789       for (unsigned i = 3, e = Oprnds.size(); i != e; ++i) {
00790         if (It == FTy->param_end())
00791           error("Invalid invoke instruction!");
00792         Params.push_back(getValue(getTypeSlot(*It++), Oprnds[i]));
00793       }
00794       if (It != FTy->param_end())
00795         error("Invalid invoke instruction!");
00796     } else {
00797       Oprnds.erase(Oprnds.begin(), Oprnds.begin()+1);
00798 
00799       Normal = getBasicBlock(Oprnds[0]);
00800       Except = getBasicBlock(Oprnds[1]);
00801       
00802       unsigned FirstVariableArgument = FTy->getNumParams()+2;
00803       for (unsigned i = 2; i != FirstVariableArgument; ++i)
00804         Params.push_back(getValue(getTypeSlot(FTy->getParamType(i-2)),
00805                                   Oprnds[i]));
00806       
00807       if (Oprnds.size()-FirstVariableArgument & 1) // Must be type/value pairs
00808         error("Invalid invoke instruction!");
00809 
00810       for (unsigned i = FirstVariableArgument; i < Oprnds.size(); i += 2)
00811         Params.push_back(getValue(Oprnds[i], Oprnds[i+1]));
00812     }
00813 
00814     Result = new InvokeInst(F, Normal, Except, Params);
00815     break;
00816   }
00817   case Instruction::Malloc:
00818     if (Oprnds.size() > 2) 
00819       error("Invalid malloc instruction!");
00820     if (!isa<PointerType>(InstTy))
00821       error("Invalid malloc instruction!");
00822 
00823     Result = new MallocInst(cast<PointerType>(InstTy)->getElementType(),
00824                             Oprnds.size() ? getValue(Type::UIntTyID,
00825                                                    Oprnds[0]) : 0);
00826     break;
00827 
00828   case Instruction::Alloca:
00829     if (Oprnds.size() > 2) 
00830       error("Invalid alloca instruction!");
00831     if (!isa<PointerType>(InstTy))
00832       error("Invalid alloca instruction!");
00833 
00834     Result = new AllocaInst(cast<PointerType>(InstTy)->getElementType(),
00835                             Oprnds.size() ? getValue(Type::UIntTyID, 
00836                             Oprnds[0]) :0);
00837     break;
00838   case Instruction::Free:
00839     if (!isa<PointerType>(InstTy))
00840       error("Invalid free instruction!");
00841     Result = new FreeInst(getValue(iType, Oprnds[0]));
00842     break;
00843   case Instruction::GetElementPtr: {
00844     if (Oprnds.size() == 0 || !isa<PointerType>(InstTy))
00845       error("Invalid getelementptr instruction!");
00846 
00847     std::vector<Value*> Idx;
00848 
00849     const Type *NextTy = InstTy;
00850     for (unsigned i = 1, e = Oprnds.size(); i != e; ++i) {
00851       const CompositeType *TopTy = dyn_cast_or_null<CompositeType>(NextTy);
00852       if (!TopTy) 
00853         error("Invalid getelementptr instruction!"); 
00854 
00855       unsigned ValIdx = Oprnds[i];
00856       unsigned IdxTy = 0;
00857       if (!hasRestrictedGEPTypes) {
00858         // Struct indices are always uints, sequential type indices can be any
00859         // of the 32 or 64-bit integer types.  The actual choice of type is
00860         // encoded in the low two bits of the slot number.
00861         if (isa<StructType>(TopTy))
00862           IdxTy = Type::UIntTyID;
00863         else {
00864           switch (ValIdx & 3) {
00865           default:
00866           case 0: IdxTy = Type::UIntTyID; break;
00867           case 1: IdxTy = Type::IntTyID; break;
00868           case 2: IdxTy = Type::ULongTyID; break;
00869           case 3: IdxTy = Type::LongTyID; break;
00870           }
00871           ValIdx >>= 2;
00872         }
00873       } else {
00874         IdxTy = isa<StructType>(TopTy) ? Type::UByteTyID : Type::LongTyID;
00875       }
00876 
00877       Idx.push_back(getValue(IdxTy, ValIdx));
00878 
00879       // Convert ubyte struct indices into uint struct indices.
00880       if (isa<StructType>(TopTy) && hasRestrictedGEPTypes)
00881         if (ConstantUInt *C = dyn_cast<ConstantUInt>(Idx.back()))
00882           Idx[Idx.size()-1] = ConstantExpr::getCast(C, Type::UIntTy);
00883 
00884       NextTy = GetElementPtrInst::getIndexedType(InstTy, Idx, true);
00885     }
00886 
00887     Result = new GetElementPtrInst(getValue(iType, Oprnds[0]), Idx);
00888     break;
00889   }
00890 
00891   case 62:   // volatile load
00892   case Instruction::Load:
00893     if (Oprnds.size() != 1 || !isa<PointerType>(InstTy))
00894       error("Invalid load instruction!");
00895     Result = new LoadInst(getValue(iType, Oprnds[0]), "", Opcode == 62);
00896     break;
00897 
00898   case 63:   // volatile store 
00899   case Instruction::Store: {
00900     if (!isa<PointerType>(InstTy) || Oprnds.size() != 2)
00901       error("Invalid store instruction!");
00902 
00903     Value *Ptr = getValue(iType, Oprnds[1]);
00904     const Type *ValTy = cast<PointerType>(Ptr->getType())->getElementType();
00905     Result = new StoreInst(getValue(getTypeSlot(ValTy), Oprnds[0]), Ptr,
00906                            Opcode == 63);
00907     break;
00908   }
00909   case Instruction::Unwind:
00910     if (Oprnds.size() != 0) error("Invalid unwind instruction!");
00911     Result = new UnwindInst();
00912     break;
00913   case Instruction::Unreachable:
00914     if (Oprnds.size() != 0) error("Invalid unreachable instruction!");
00915     Result = new UnreachableInst();
00916     break;
00917   }  // end switch(Opcode) 
00918 
00919   unsigned TypeSlot;
00920   if (Result->getType() == InstTy)
00921     TypeSlot = iType;
00922   else
00923     TypeSlot = getTypeSlot(Result->getType());
00924 
00925   insertValue(Result, TypeSlot, FunctionValues);
00926   BB->getInstList().push_back(Result);
00927 }
00928 
00929 /// Get a particular numbered basic block, which might be a forward reference.
00930 /// This works together with ParseBasicBlock to handle these forward references
00931 /// in a clean manner.  This function is used when constructing phi, br, switch,
00932 /// and other instructions that reference basic blocks. Blocks are numbered
00933 /// sequentially as they appear in the function.
00934 BasicBlock *BytecodeReader::getBasicBlock(unsigned ID) {
00935   // Make sure there is room in the table...
00936   if (ParsedBasicBlocks.size() <= ID) ParsedBasicBlocks.resize(ID+1);
00937 
00938   // First check to see if this is a backwards reference, i.e., ParseBasicBlock
00939   // has already created this block, or if the forward reference has already
00940   // been created.
00941   if (ParsedBasicBlocks[ID])
00942     return ParsedBasicBlocks[ID];
00943 
00944   // Otherwise, the basic block has not yet been created.  Do so and add it to
00945   // the ParsedBasicBlocks list.
00946   return ParsedBasicBlocks[ID] = new BasicBlock();
00947 }
00948 
00949 /// In LLVM 1.0 bytecode files, we used to output one basicblock at a time.  
00950 /// This method reads in one of the basicblock packets. This method is not used
00951 /// for bytecode files after LLVM 1.0
00952 /// @returns The basic block constructed.
00953 BasicBlock *BytecodeReader::ParseBasicBlock(unsigned BlockNo) {
00954   if (Handler) Handler->handleBasicBlockBegin(BlockNo);
00955 
00956   BasicBlock *BB = 0;
00957 
00958   if (ParsedBasicBlocks.size() == BlockNo)
00959     ParsedBasicBlocks.push_back(BB = new BasicBlock());
00960   else if (ParsedBasicBlocks[BlockNo] == 0)
00961     BB = ParsedBasicBlocks[BlockNo] = new BasicBlock();
00962   else
00963     BB = ParsedBasicBlocks[BlockNo];
00964 
00965   std::vector<unsigned> Operands;
00966   while (moreInBlock())
00967     ParseInstruction(Operands, BB);
00968 
00969   if (Handler) Handler->handleBasicBlockEnd(BlockNo);
00970   return BB;
00971 }
00972 
00973 /// Parse all of the BasicBlock's & Instruction's in the body of a function.
00974 /// In post 1.0 bytecode files, we no longer emit basic block individually, 
00975 /// in order to avoid per-basic-block overhead.
00976 /// @returns Rhe number of basic blocks encountered.
00977 unsigned BytecodeReader::ParseInstructionList(Function* F) {
00978   unsigned BlockNo = 0;
00979   std::vector<unsigned> Args;
00980 
00981   while (moreInBlock()) {
00982     if (Handler) Handler->handleBasicBlockBegin(BlockNo);
00983     BasicBlock *BB;
00984     if (ParsedBasicBlocks.size() == BlockNo)
00985       ParsedBasicBlocks.push_back(BB = new BasicBlock());
00986     else if (ParsedBasicBlocks[BlockNo] == 0)
00987       BB = ParsedBasicBlocks[BlockNo] = new BasicBlock();
00988     else
00989       BB = ParsedBasicBlocks[BlockNo];
00990     ++BlockNo;
00991     F->getBasicBlockList().push_back(BB);
00992 
00993     // Read instructions into this basic block until we get to a terminator
00994     while (moreInBlock() && !BB->getTerminator())
00995       ParseInstruction(Args, BB);
00996 
00997     if (!BB->getTerminator())
00998       error("Non-terminated basic block found!");
00999 
01000     if (Handler) Handler->handleBasicBlockEnd(BlockNo-1);
01001   }
01002 
01003   return BlockNo;
01004 }
01005 
01006 /// Parse a symbol table. This works for both module level and function
01007 /// level symbol tables.  For function level symbol tables, the CurrentFunction
01008 /// parameter must be non-zero and the ST parameter must correspond to
01009 /// CurrentFunction's symbol table. For Module level symbol tables, the
01010 /// CurrentFunction argument must be zero.
01011 void BytecodeReader::ParseSymbolTable(Function *CurrentFunction,
01012                                       SymbolTable *ST) {
01013   if (Handler) Handler->handleSymbolTableBegin(CurrentFunction,ST);
01014 
01015   // Allow efficient basic block lookup by number.
01016   std::vector<BasicBlock*> BBMap;
01017   if (CurrentFunction)
01018     for (Function::iterator I = CurrentFunction->begin(),
01019            E = CurrentFunction->end(); I != E; ++I)
01020       BBMap.push_back(I);
01021 
01022   /// In LLVM 1.3 we write types separately from values so
01023   /// The types are always first in the symbol table. This is
01024   /// because Type no longer derives from Value.
01025   if (!hasTypeDerivedFromValue) {
01026     // Symtab block header: [num entries]
01027     unsigned NumEntries = read_vbr_uint();
01028     for (unsigned i = 0; i < NumEntries; ++i) {
01029       // Symtab entry: [def slot #][name]
01030       unsigned slot = read_vbr_uint();
01031       std::string Name = read_str();
01032       const Type* T = getType(slot);
01033       ST->insert(Name, T);
01034     }
01035   }
01036 
01037   while (moreInBlock()) {
01038     // Symtab block header: [num entries][type id number]
01039     unsigned NumEntries = read_vbr_uint();
01040     unsigned Typ = 0;
01041     bool isTypeType = read_typeid(Typ);
01042     const Type *Ty = getType(Typ);
01043 
01044     for (unsigned i = 0; i != NumEntries; ++i) {
01045       // Symtab entry: [def slot #][name]
01046       unsigned slot = read_vbr_uint();
01047       std::string Name = read_str();
01048 
01049       // if we're reading a pre 1.3 bytecode file and the type plane
01050       // is the "type type", handle it here
01051       if (isTypeType) {
01052         const Type* T = getType(slot);
01053         if (T == 0)
01054           error("Failed type look-up for name '" + Name + "'");
01055         ST->insert(Name, T);
01056         continue; // code below must be short circuited
01057       } else {
01058         Value *V = 0;
01059         if (Typ == Type::LabelTyID) {
01060           if (slot < BBMap.size())
01061             V = BBMap[slot];
01062         } else {
01063           V = getValue(Typ, slot, false); // Find mapping...
01064         }
01065         if (V == 0)
01066           error("Failed value look-up for name '" + Name + "'");
01067         V->setName(Name, ST);
01068       }
01069     }
01070   }
01071   checkPastBlockEnd("Symbol Table");
01072   if (Handler) Handler->handleSymbolTableEnd();
01073 }
01074 
01075 /// Read in the types portion of a compaction table. 
01076 void BytecodeReader::ParseCompactionTypes(unsigned NumEntries) {
01077   for (unsigned i = 0; i != NumEntries; ++i) {
01078     unsigned TypeSlot = 0;
01079     if (read_typeid(TypeSlot))
01080       error("Invalid type in compaction table: type type");
01081     const Type *Typ = getGlobalTableType(TypeSlot);
01082     CompactionTypes.push_back(std::make_pair(Typ, TypeSlot));
01083     if (Handler) Handler->handleCompactionTableType(i, TypeSlot, Typ);
01084   }
01085 }
01086 
01087 /// Parse a compaction table.
01088 void BytecodeReader::ParseCompactionTable() {
01089 
01090   // Notify handler that we're beginning a compaction table.
01091   if (Handler) Handler->handleCompactionTableBegin();
01092 
01093   // In LLVM 1.3 Type no longer derives from Value. So, 
01094   // we always write them first in the compaction table
01095   // because they can't occupy a "type plane" where the
01096   // Values reside.
01097   if (! hasTypeDerivedFromValue) {
01098     unsigned NumEntries = read_vbr_uint();
01099     ParseCompactionTypes(NumEntries);
01100   }
01101 
01102   // Compaction tables live in separate blocks so we have to loop
01103   // until we've read the whole thing.
01104   while (moreInBlock()) {
01105     // Read the number of Value* entries in the compaction table
01106     unsigned NumEntries = read_vbr_uint();
01107     unsigned Ty = 0;
01108     unsigned isTypeType = false;
01109 
01110     // Decode the type from value read in. Most compaction table
01111     // planes will have one or two entries in them. If that's the
01112     // case then the length is encoded in the bottom two bits and
01113     // the higher bits encode the type. This saves another VBR value.
01114     if ((NumEntries & 3) == 3) {
01115       // In this case, both low-order bits are set (value 3). This
01116       // is a signal that the typeid follows.
01117       NumEntries >>= 2;
01118       isTypeType = read_typeid(Ty);
01119     } else {
01120       // In this case, the low-order bits specify the number of entries
01121       // and the high order bits specify the type.
01122       Ty = NumEntries >> 2;
01123       isTypeType = sanitizeTypeId(Ty);
01124       NumEntries &= 3;
01125     }
01126 
01127     // if we're reading a pre 1.3 bytecode file and the type plane
01128     // is the "type type", handle it here
01129     if (isTypeType) {
01130       ParseCompactionTypes(NumEntries);
01131     } else {
01132       // Make sure we have enough room for the plane.
01133       if (Ty >= CompactionValues.size())
01134         CompactionValues.resize(Ty+1);
01135 
01136       // Make sure the plane is empty or we have some kind of error.
01137       if (!CompactionValues[Ty].empty())
01138         error("Compaction table plane contains multiple entries!");
01139 
01140       // Notify handler about the plane.
01141       if (Handler) Handler->handleCompactionTablePlane(Ty, NumEntries);
01142 
01143       // Push the implicit zero.
01144       CompactionValues[Ty].push_back(Constant::getNullValue(getType(Ty)));
01145 
01146       // Read in each of the entries, put them in the compaction table
01147       // and notify the handler that we have a new compaction table value.
01148       for (unsigned i = 0; i != NumEntries; ++i) {
01149         unsigned ValSlot = read_vbr_uint();
01150         Value *V = getGlobalTableValue(Ty, ValSlot);
01151         CompactionValues[Ty].push_back(V);
01152         if (Handler) Handler->handleCompactionTableValue(i, Ty, ValSlot);
01153       }
01154     }
01155   }
01156   // Notify handler that the compaction table is done.
01157   if (Handler) Handler->handleCompactionTableEnd();
01158 }
01159     
01160 // Parse a single type. The typeid is read in first. If its a primitive type
01161 // then nothing else needs to be read, we know how to instantiate it. If its
01162 // a derived type, then additional data is read to fill out the type 
01163 // definition.
01164 const Type *BytecodeReader::ParseType() {
01165   unsigned PrimType = 0;
01166   if (read_typeid(PrimType))
01167     error("Invalid type (type type) in type constants!");
01168 
01169   const Type *Result = 0;
01170   if ((Result = Type::getPrimitiveType((Type::TypeID)PrimType)))
01171     return Result;
01172   
01173   switch (PrimType) {
01174   case Type::FunctionTyID: {
01175     const Type *RetType = readSanitizedType();
01176 
01177     unsigned NumParams = read_vbr_uint();
01178 
01179     std::vector<const Type*> Params;
01180     while (NumParams--) 
01181       Params.push_back(readSanitizedType());
01182 
01183     bool isVarArg = Params.size() && Params.back() == Type::VoidTy;
01184     if (isVarArg) Params.pop_back();
01185 
01186     Result = FunctionType::get(RetType, Params, isVarArg);
01187     break;
01188   }
01189   case Type::ArrayTyID: {
01190     const Type *ElementType = readSanitizedType();
01191     unsigned NumElements = read_vbr_uint();
01192     Result =  ArrayType::get(ElementType, NumElements);
01193     break;
01194   }
01195   case Type::PackedTyID: {
01196     const Type *ElementType = readSanitizedType();
01197     unsigned NumElements = read_vbr_uint();
01198     Result =  PackedType::get(ElementType, NumElements);
01199     break;
01200   }
01201   case Type::StructTyID: {
01202     std::vector<const Type*> Elements;
01203     unsigned Typ = 0;
01204     if (read_typeid(Typ))
01205       error("Invalid element type (type type) for structure!");
01206 
01207     while (Typ) {         // List is terminated by void/0 typeid
01208       Elements.push_back(getType(Typ));
01209       if (read_typeid(Typ))
01210         error("Invalid element type (type type) for structure!");
01211     }
01212 
01213     Result = StructType::get(Elements);
01214     break;
01215   }
01216   case Type::PointerTyID: {
01217     Result = PointerType::get(readSanitizedType());
01218     break;
01219   }
01220 
01221   case Type::OpaqueTyID: {
01222     Result = OpaqueType::get();
01223     break;
01224   }
01225 
01226   default:
01227     error("Don't know how to deserialize primitive type " + utostr(PrimType));
01228     break;
01229   }
01230   if (Handler) Handler->handleType(Result);
01231   return Result;
01232 }
01233 
01234 // ParseTypes - We have to use this weird code to handle recursive
01235 // types.  We know that recursive types will only reference the current slab of
01236 // values in the type plane, but they can forward reference types before they
01237 // have been read.  For example, Type #0 might be '{ Ty#1 }' and Type #1 might
01238 // be 'Ty#0*'.  When reading Type #0, type number one doesn't exist.  To fix
01239 // this ugly problem, we pessimistically insert an opaque type for each type we
01240 // are about to read.  This means that forward references will resolve to
01241 // something and when we reread the type later, we can replace the opaque type
01242 // with a new resolved concrete type.
01243 //
01244 void BytecodeReader::ParseTypes(TypeListTy &Tab, unsigned NumEntries){
01245   assert(Tab.size() == 0 && "should not have read type constants in before!");
01246 
01247   // Insert a bunch of opaque types to be resolved later...
01248   Tab.reserve(NumEntries);
01249   for (unsigned i = 0; i != NumEntries; ++i)
01250     Tab.push_back(OpaqueType::get());
01251 
01252   if (Handler) 
01253     Handler->handleTypeList(NumEntries);
01254 
01255   // Loop through reading all of the types.  Forward types will make use of the
01256   // opaque types just inserted.
01257   //
01258   for (unsigned i = 0; i != NumEntries; ++i) {
01259     const Type* NewTy = ParseType();
01260     const Type* OldTy = Tab[i].get();
01261     if (NewTy == 0) 
01262       error("Couldn't parse type!");
01263 
01264     // Don't directly push the new type on the Tab. Instead we want to replace 
01265     // the opaque type we previously inserted with the new concrete value. This
01266     // approach helps with forward references to types. The refinement from the
01267     // abstract (opaque) type to the new type causes all uses of the abstract
01268     // type to use the concrete type (NewTy). This will also cause the opaque
01269     // type to be deleted.
01270     cast<DerivedType>(const_cast<Type*>(OldTy))->refineAbstractTypeTo(NewTy);
01271 
01272     // This should have replaced the old opaque type with the new type in the
01273     // value table... or with a preexisting type that was already in the system.
01274     // Let's just make sure it did.
01275     assert(Tab[i] != OldTy && "refineAbstractType didn't work!");
01276   }
01277 }
01278 
01279 /// Parse a single constant value
01280 Constant *BytecodeReader::ParseConstantValue(unsigned TypeID) {
01281   // We must check for a ConstantExpr before switching by type because
01282   // a ConstantExpr can be of any type, and has no explicit value.
01283   // 
01284   // 0 if not expr; numArgs if is expr
01285   unsigned isExprNumArgs = read_vbr_uint();
01286 
01287   if (isExprNumArgs) {
01288     // 'undef' is encoded with 'exprnumargs' == 1.
01289     if (!hasNoUndefValue)
01290       if (--isExprNumArgs == 0)
01291         return UndefValue::get(getType(TypeID));
01292   
01293     // FIXME: Encoding of constant exprs could be much more compact!
01294     std::vector<Constant*> ArgVec;
01295     ArgVec.reserve(isExprNumArgs);
01296     unsigned Opcode = read_vbr_uint();
01297 
01298     // Bytecode files before LLVM 1.4 need have a missing terminator inst.
01299     if (hasNoUnreachableInst) Opcode++;
01300     
01301     // Read the slot number and types of each of the arguments
01302     for (unsigned i = 0; i != isExprNumArgs; ++i) {
01303       unsigned ArgValSlot = read_vbr_uint();
01304       unsigned ArgTypeSlot = 0;
01305       if (read_typeid(ArgTypeSlot))
01306         error("Invalid argument type (type type) for constant value");
01307       
01308       // Get the arg value from its slot if it exists, otherwise a placeholder
01309       ArgVec.push_back(getConstantValue(ArgTypeSlot, ArgValSlot));
01310     }
01311     
01312     // Construct a ConstantExpr of the appropriate kind
01313     if (isExprNumArgs == 1) {           // All one-operand expressions
01314       if (Opcode != Instruction::Cast)
01315         error("Only cast instruction has one argument for ConstantExpr");
01316 
01317       Constant* Result = ConstantExpr::getCast(ArgVec[0], getType(TypeID));
01318       if (Handler) Handler->handleConstantExpression(Opcode, ArgVec, Result);
01319       return Result;
01320     } else if (Opcode == Instruction::GetElementPtr) { // GetElementPtr
01321       std::vector<Constant*> IdxList(ArgVec.begin()+1, ArgVec.end());
01322 
01323       if (hasRestrictedGEPTypes) {
01324         const Type *BaseTy = ArgVec[0]->getType();
01325         generic_gep_type_iterator<std::vector<Constant*>::iterator>
01326           GTI = gep_type_begin(BaseTy, IdxList.begin(), IdxList.end()),
01327           E = gep_type_end(BaseTy, IdxList.begin(), IdxList.end());
01328         for (unsigned i = 0; GTI != E; ++GTI, ++i)
01329           if (isa<StructType>(*GTI)) {
01330             if (IdxList[i]->getType() != Type::UByteTy)
01331               error("Invalid index for getelementptr!");
01332             IdxList[i] = ConstantExpr::getCast(IdxList[i], Type::UIntTy);
01333           }
01334       }
01335 
01336       Constant* Result = ConstantExpr::getGetElementPtr(ArgVec[0], IdxList);
01337       if (Handler) Handler->handleConstantExpression(Opcode, ArgVec, Result);
01338       return Result;
01339     } else if (Opcode == Instruction::Select) {
01340       if (ArgVec.size() != 3)
01341         error("Select instruction must have three arguments.");
01342       Constant* Result = ConstantExpr::getSelect(ArgVec[0], ArgVec[1], 
01343                                                  ArgVec[2]);
01344       if (Handler) Handler->handleConstantExpression(Opcode, ArgVec, Result);
01345       return Result;
01346     } else {                            // All other 2-operand expressions
01347       Constant* Result = ConstantExpr::get(Opcode, ArgVec[0], ArgVec[1]);
01348       if (Handler) Handler->handleConstantExpression(Opcode, ArgVec, Result);
01349       return Result;
01350     }
01351   }
01352   
01353   // Ok, not an ConstantExpr.  We now know how to read the given type...
01354   const Type *Ty = getType(TypeID);
01355   switch (Ty->getTypeID()) {
01356   case Type::BoolTyID: {
01357     unsigned Val = read_vbr_uint();
01358     if (Val != 0 && Val != 1) 
01359       error("Invalid boolean value read.");
01360     Constant* Result = ConstantBool::get(Val == 1);
01361     if (Handler) Handler->handleConstantValue(Result);
01362     return Result;
01363   }
01364 
01365   case Type::UByteTyID:   // Unsigned integer types...
01366   case Type::UShortTyID:
01367   case Type::UIntTyID: {
01368     unsigned Val = read_vbr_uint();
01369     if (!ConstantUInt::isValueValidForType(Ty, Val)) 
01370       error("Invalid unsigned byte/short/int read.");
01371     Constant* Result =  ConstantUInt::get(Ty, Val);
01372     if (Handler) Handler->handleConstantValue(Result);
01373     return Result;
01374   }
01375 
01376   case Type::ULongTyID: {
01377     Constant* Result = ConstantUInt::get(Ty, read_vbr_uint64());
01378     if (Handler) Handler->handleConstantValue(Result);
01379     return Result;
01380   }
01381 
01382   case Type::SByteTyID:   // Signed integer types...
01383   case Type::ShortTyID:
01384   case Type::IntTyID: {
01385   case Type::LongTyID:
01386     int64_t Val = read_vbr_int64();
01387     if (!ConstantSInt::isValueValidForType(Ty, Val)) 
01388       error("Invalid signed byte/short/int/long read.");
01389     Constant* Result = ConstantSInt::get(Ty, Val);
01390     if (Handler) Handler->handleConstantValue(Result);
01391     return Result;
01392   }
01393 
01394   case Type::FloatTyID: {
01395     float Val;
01396     read_float(Val);
01397     Constant* Result = ConstantFP::get(Ty, Val);
01398     if (Handler) Handler->handleConstantValue(Result);
01399     return Result;
01400   }
01401 
01402   case Type::DoubleTyID: {
01403     double Val;
01404     read_double(Val);
01405     Constant* Result = ConstantFP::get(Ty, Val);
01406     if (Handler) Handler->handleConstantValue(Result);
01407     return Result;
01408   }
01409 
01410   case Type::ArrayTyID: {
01411     const ArrayType *AT = cast<ArrayType>(Ty);
01412     unsigned NumElements = AT->getNumElements();
01413     unsigned TypeSlot = getTypeSlot(AT->getElementType());
01414     std::vector<Constant*> Elements;
01415     Elements.reserve(NumElements);
01416     while (NumElements--)     // Read all of the elements of the constant.
01417       Elements.push_back(getConstantValue(TypeSlot,
01418                                           read_vbr_uint()));
01419     Constant* Result = ConstantArray::get(AT, Elements);
01420     if (Handler) Handler->handleConstantArray(AT, Elements, TypeSlot, Result);
01421     return Result;
01422   }
01423 
01424   case Type::StructTyID: {
01425     const StructType *ST = cast<StructType>(Ty);
01426 
01427     std::vector<Constant *> Elements;
01428     Elements.reserve(ST->getNumElements());
01429     for (unsigned i = 0; i != ST->getNumElements(); ++i)
01430       Elements.push_back(getConstantValue(ST->getElementType(i),
01431                                           read_vbr_uint()));
01432 
01433     Constant* Result = ConstantStruct::get(ST, Elements);
01434     if (Handler) Handler->handleConstantStruct(ST, Elements, Result);
01435     return Result;
01436   }    
01437 
01438   case Type::PackedTyID: {
01439     const PackedType *PT = cast<PackedType>(Ty);
01440     unsigned NumElements = PT->getNumElements();
01441     unsigned TypeSlot = getTypeSlot(PT->getElementType());
01442     std::vector<Constant*> Elements;
01443     Elements.reserve(NumElements);
01444     while (NumElements--)     // Read all of the elements of the constant.
01445       Elements.push_back(getConstantValue(TypeSlot,
01446                                           read_vbr_uint()));
01447     Constant* Result = ConstantPacked::get(PT, Elements);
01448     if (Handler) Handler->handleConstantPacked(PT, Elements, TypeSlot, Result);
01449     return Result;
01450   }
01451 
01452   case Type::PointerTyID: {  // ConstantPointerRef value (backwards compat).
01453     const PointerType *PT = cast<PointerType>(Ty);
01454     unsigned Slot = read_vbr_uint();
01455     
01456     // Check to see if we have already read this global variable...
01457     Value *Val = getValue(TypeID, Slot, false);
01458     if (Val) {
01459       GlobalValue *GV = dyn_cast<GlobalValue>(Val);
01460       if (!GV) error("GlobalValue not in ValueTable!");
01461       if (Handler) Handler->handleConstantPointer(PT, Slot, GV);
01462       return GV;
01463     } else {
01464       error("Forward references are not allowed here.");
01465     }
01466   }
01467 
01468   default:
01469     error("Don't know how to deserialize constant value of type '" +
01470                       Ty->getDescription());
01471     break;
01472   }
01473   return 0;
01474 }
01475 
01476 /// Resolve references for constants. This function resolves the forward 
01477 /// referenced constants in the ConstantFwdRefs map. It uses the 
01478 /// replaceAllUsesWith method of Value class to substitute the placeholder
01479 /// instance with the actual instance.
01480 void BytecodeReader::ResolveReferencesToConstant(Constant *NewV, unsigned Slot){
01481   ConstantRefsType::iterator I =
01482     ConstantFwdRefs.find(std::make_pair(NewV->getType(), Slot));
01483   if (I == ConstantFwdRefs.end()) return;   // Never forward referenced?
01484 
01485   Value *PH = I->second;   // Get the placeholder...
01486   PH->replaceAllUsesWith(NewV);
01487   delete PH;                               // Delete the old placeholder
01488   ConstantFwdRefs.erase(I);                // Remove the map entry for it
01489 }
01490 
01491 /// Parse the constant strings section.
01492 void BytecodeReader::ParseStringConstants(unsigned NumEntries, ValueTable &Tab){
01493   for (; NumEntries; --NumEntries) {
01494     unsigned Typ = 0;
01495     if (read_typeid(Typ))
01496       error("Invalid type (type type) for string constant");
01497     const Type *Ty = getType(Typ);
01498     if (!isa<ArrayType>(Ty))
01499       error("String constant data invalid!");
01500     
01501     const ArrayType *ATy = cast<ArrayType>(Ty);
01502     if (ATy->getElementType() != Type::SByteTy &&
01503         ATy->getElementType() != Type::UByteTy)
01504       error("String constant data invalid!");
01505     
01506     // Read character data.  The type tells us how long the string is.
01507     char Data[ATy->getNumElements()]; 
01508     read_data(Data, Data+ATy->getNumElements());
01509 
01510     std::vector<Constant*> Elements(ATy->getNumElements());
01511     if (ATy->getElementType() == Type::SByteTy)
01512       for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i)
01513         Elements[i] = ConstantSInt::get(Type::SByteTy, (signed char)Data[i]);
01514     else
01515       for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i)
01516         Elements[i] = ConstantUInt::get(Type::UByteTy, (unsigned char)Data[i]);
01517 
01518     // Create the constant, inserting it as needed.
01519     Constant *C = ConstantArray::get(ATy, Elements);
01520     unsigned Slot = insertValue(C, Typ, Tab);
01521     ResolveReferencesToConstant(C, Slot);
01522     if (Handler) Handler->handleConstantString(cast<ConstantArray>(C));
01523   }
01524 }
01525 
01526 /// Parse the constant pool.
01527 void BytecodeReader::ParseConstantPool(ValueTable &Tab, 
01528                                        TypeListTy &TypeTab,
01529                                        bool isFunction) {
01530   if (Handler) Handler->handleGlobalConstantsBegin();
01531 
01532   /// In LLVM 1.3 Type does not derive from Value so the types
01533   /// do not occupy a plane. Consequently, we read the types
01534   /// first in the constant pool.
01535   if (isFunction && !hasTypeDerivedFromValue) {
01536     unsigned NumEntries = read_vbr_uint();
01537     ParseTypes(TypeTab, NumEntries);
01538   }
01539 
01540   while (moreInBlock()) {
01541     unsigned NumEntries = read_vbr_uint();
01542     unsigned Typ = 0;
01543     bool isTypeType = read_typeid(Typ);
01544 
01545     /// In LLVM 1.2 and before, Types were written to the
01546     /// bytecode file in the "Type Type" plane (#12).
01547     /// In 1.3 plane 12 is now the label plane.  Handle this here.
01548     if (isTypeType) {
01549       ParseTypes(TypeTab, NumEntries);
01550     } else if (Typ == Type::VoidTyID) {
01551       /// Use of Type::VoidTyID is a misnomer. It actually means
01552       /// that the following plane is constant strings
01553       assert(&Tab == &ModuleValues && "Cannot read strings in functions!");
01554       ParseStringConstants(NumEntries, Tab);
01555     } else {
01556       for (unsigned i = 0; i < NumEntries; ++i) {
01557         Constant *C = ParseConstantValue(Typ);
01558         assert(C && "ParseConstantValue returned NULL!");
01559         unsigned Slot = insertValue(C, Typ, Tab);
01560 
01561         // If we are reading a function constant table, make sure that we adjust
01562         // the slot number to be the real global constant number.
01563         //
01564         if (&Tab != &ModuleValues && Typ < ModuleValues.size() &&
01565             ModuleValues[Typ])
01566           Slot += ModuleValues[Typ]->size();
01567         ResolveReferencesToConstant(C, Slot);
01568       }
01569     }
01570   }
01571 
01572   // After we have finished parsing the constant pool, we had better not have
01573   // any dangling references left.
01574   if (!ConstantFwdRefs.empty()) {
01575   typedef std::map<std::pair<const Type*,unsigned>, Constant*> ConstantRefsType;
01576     ConstantRefsType::const_iterator I = ConstantFwdRefs.begin();
01577     const Type* missingType = I->first.first;
01578     Constant* missingConst = I->second;
01579     error(utostr(ConstantFwdRefs.size()) + 
01580           " unresolved constant reference exist. First one is '" + 
01581           missingConst->getName() + "' of type '" + 
01582           missingType->getDescription() + "'.");
01583   }
01584 
01585   checkPastBlockEnd("Constant Pool");
01586   if (Handler) Handler->handleGlobalConstantsEnd();
01587 }
01588 
01589 /// Parse the contents of a function. Note that this function can be
01590 /// called lazily by materializeFunction
01591 /// @see materializeFunction
01592 void BytecodeReader::ParseFunctionBody(Function* F) {
01593 
01594   unsigned FuncSize = BlockEnd - At;
01595   GlobalValue::LinkageTypes Linkage = GlobalValue::ExternalLinkage;
01596 
01597   unsigned LinkageType = read_vbr_uint();
01598   switch (LinkageType) {
01599   case 0: Linkage = GlobalValue::ExternalLinkage; break;
01600   case 1: Linkage = GlobalValue::WeakLinkage; break;
01601   case 2: Linkage = GlobalValue::AppendingLinkage; break;
01602   case 3: Linkage = GlobalValue::InternalLinkage; break;
01603   case 4: Linkage = GlobalValue::LinkOnceLinkage; break;
01604   default:
01605     error("Invalid linkage type for Function.");
01606     Linkage = GlobalValue::InternalLinkage;
01607     break;
01608   }
01609 
01610   F->setLinkage(Linkage);
01611   if (Handler) Handler->handleFunctionBegin(F,FuncSize);
01612 
01613   // Keep track of how many basic blocks we have read in...
01614   unsigned BlockNum = 0;
01615   bool InsertedArguments = false;
01616 
01617   BufPtr MyEnd = BlockEnd;
01618   while (At < MyEnd) {
01619     unsigned Type, Size;
01620     BufPtr OldAt = At;
01621     read_block(Type, Size);
01622 
01623     switch (Type) {
01624     case BytecodeFormat::ConstantPoolBlockID:
01625       if (!InsertedArguments) {
01626         // Insert arguments into the value table before we parse the first basic
01627         // block in the function, but after we potentially read in the
01628         // compaction table.
01629         insertArguments(F);
01630         InsertedArguments = true;
01631       }
01632 
01633       ParseConstantPool(FunctionValues, FunctionTypes, true);
01634       break;
01635 
01636     case BytecodeFormat::CompactionTableBlockID:
01637       ParseCompactionTable();
01638       break;
01639 
01640     case BytecodeFormat::BasicBlock: {
01641       if (!InsertedArguments) {
01642         // Insert arguments into the value table before we parse the first basic
01643         // block in the function, but after we potentially read in the
01644         // compaction table.
01645         insertArguments(F);
01646         InsertedArguments = true;
01647       }
01648 
01649       BasicBlock *BB = ParseBasicBlock(BlockNum++);
01650       F->getBasicBlockList().push_back(BB);
01651       break;
01652     }
01653 
01654     case BytecodeFormat::InstructionListBlockID: {
01655       // Insert arguments into the value table before we parse the instruction
01656       // list for the function, but after we potentially read in the compaction
01657       // table.
01658       if (!InsertedArguments) {
01659         insertArguments(F);
01660         InsertedArguments = true;
01661       }
01662 
01663       if (BlockNum) 
01664         error("Already parsed basic blocks!");
01665       BlockNum = ParseInstructionList(F);
01666       break;
01667     }
01668 
01669     case BytecodeFormat::SymbolTableBlockID:
01670       ParseSymbolTable(F, &F->getSymbolTable());
01671       break;
01672 
01673     default:
01674       At += Size;
01675       if (OldAt > At) 
01676         error("Wrapped around reading bytecode.");
01677       break;
01678     }
01679     BlockEnd = MyEnd;
01680 
01681     // Malformed bc file if read past end of block.
01682     align32();
01683   }
01684 
01685   // Make sure there were no references to non-existant basic blocks.
01686   if (BlockNum != ParsedBasicBlocks.size())
01687     error("Illegal basic block operand reference");
01688 
01689   ParsedBasicBlocks.clear();
01690 
01691   // Resolve forward references.  Replace any uses of a forward reference value
01692   // with the real value.
01693 
01694   // replaceAllUsesWith is very inefficient for instructions which have a LARGE
01695   // number of operands.  PHI nodes often have forward references, and can also
01696   // often have a very large number of operands.
01697   //
01698   // FIXME: REEVALUATE.  replaceAllUsesWith is _much_ faster now, and this code
01699   // should be simplified back to using it!
01700   //
01701   std::map<Value*, Value*> ForwardRefMapping;
01702   for (std::map<std::pair<unsigned,unsigned>, Value*>::iterator 
01703          I = ForwardReferences.begin(), E = ForwardReferences.end();
01704        I != E; ++I)
01705     ForwardRefMapping[I->second] = getValue(I->first.first, I->first.second,
01706                                             false);
01707 
01708   for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
01709     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
01710       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
01711         if (Value* V = I->getOperand(i))
01712           if (Argument *A = dyn_cast<Argument>(V)) {
01713             std::map<Value*, Value*>::iterator It = ForwardRefMapping.find(A);
01714             if (It != ForwardRefMapping.end()) I->setOperand(i, It->second);
01715           }
01716 
01717   while (!ForwardReferences.empty()) {
01718     std::map<std::pair<unsigned,unsigned>, Value*>::iterator I =
01719       ForwardReferences.begin();
01720     Value *PlaceHolder = I->second;
01721     ForwardReferences.erase(I);
01722 
01723     // Now that all the uses are gone, delete the placeholder...
01724     // If we couldn't find a def (error case), then leak a little
01725     // memory, because otherwise we can't remove all uses!
01726     delete PlaceHolder;
01727   }
01728 
01729   // Clear out function-level types...
01730   FunctionTypes.clear();
01731   CompactionTypes.clear();
01732   CompactionValues.clear();
01733   freeTable(FunctionValues);
01734 
01735   if (Handler) Handler->handleFunctionEnd(F);
01736 }
01737 
01738 /// This function parses LLVM functions lazily. It obtains the type of the
01739 /// function and records where the body of the function is in the bytecode
01740 /// buffer. The caller can then use the ParseNextFunction and 
01741 /// ParseAllFunctionBodies to get handler events for the functions.
01742 void BytecodeReader::ParseFunctionLazily() {
01743   if (FunctionSignatureList.empty())
01744     error("FunctionSignatureList empty!");
01745 
01746   Function *Func = FunctionSignatureList.back();
01747   FunctionSignatureList.pop_back();
01748 
01749   // Save the information for future reading of the function
01750   LazyFunctionLoadMap[Func] = LazyFunctionInfo(BlockStart, BlockEnd);
01751 
01752   // This function has a body but it's not loaded so it appears `External'.
01753   // Mark it as a `Ghost' instead to notify the users that it has a body.
01754   Func->setLinkage(GlobalValue::GhostLinkage);
01755 
01756   // Pretend we've `parsed' this function
01757   At = BlockEnd;
01758 }
01759 
01760 /// The ParserFunction method lazily parses one function. Use this method to 
01761 /// casue the parser to parse a specific function in the module. Note that 
01762 /// this will remove the function from what is to be included by 
01763 /// ParseAllFunctionBodies.
01764 /// @see ParseAllFunctionBodies
01765 /// @see ParseBytecode
01766 void BytecodeReader::ParseFunction(Function* Func) {
01767   // Find {start, end} pointers and slot in the map. If not there, we're done.
01768   LazyFunctionMap::iterator Fi = LazyFunctionLoadMap.find(Func);
01769 
01770   // Make sure we found it
01771   if (Fi == LazyFunctionLoadMap.end()) {
01772     error("Unrecognized function of type " + Func->getType()->getDescription());
01773     return;
01774   }
01775 
01776   BlockStart = At = Fi->second.Buf;
01777   BlockEnd = Fi->second.EndBuf;
01778   assert(Fi->first == Func && "Found wrong function?");
01779 
01780   LazyFunctionLoadMap.erase(Fi);
01781 
01782   this->ParseFunctionBody(Func);
01783 }
01784 
01785 /// The ParseAllFunctionBodies method parses through all the previously
01786 /// unparsed functions in the bytecode file. If you want to completely parse
01787 /// a bytecode file, this method should be called after Parsebytecode because
01788 /// Parsebytecode only records the locations in the bytecode file of where
01789 /// the function definitions are located. This function uses that information
01790 /// to materialize the functions.
01791 /// @see ParseBytecode
01792 void BytecodeReader::ParseAllFunctionBodies() {
01793   LazyFunctionMap::iterator Fi = LazyFunctionLoadMap.begin();
01794   LazyFunctionMap::iterator Fe = LazyFunctionLoadMap.end();
01795 
01796   while (Fi != Fe) {
01797     Function* Func = Fi->first;
01798     BlockStart = At = Fi->second.Buf;
01799     BlockEnd = Fi->second.EndBuf;
01800     this->ParseFunctionBody(Func);
01801     ++Fi;
01802   }
01803 }
01804 
01805 /// Parse the global type list
01806 void BytecodeReader::ParseGlobalTypes() {
01807   // Read the number of types
01808   unsigned NumEntries = read_vbr_uint();
01809 
01810   // Ignore the type plane identifier for types if the bc file is pre 1.3
01811   if (hasTypeDerivedFromValue)
01812     read_vbr_uint();
01813 
01814   ParseTypes(ModuleTypes, NumEntries);
01815 }
01816 
01817 /// Parse the Global info (types, global vars, constants)
01818 void BytecodeReader::ParseModuleGlobalInfo() {
01819 
01820   if (Handler) Handler->handleModuleGlobalsBegin();
01821 
01822   // Read global variables...
01823   unsigned VarType = read_vbr_uint();
01824   while (VarType != Type::VoidTyID) { // List is terminated by Void
01825     // VarType Fields: bit0 = isConstant, bit1 = hasInitializer, bit2,3,4 =
01826     // Linkage, bit4+ = slot#
01827     unsigned SlotNo = VarType >> 5;
01828     if (sanitizeTypeId(SlotNo))
01829       error("Invalid type (type type) for global var!");
01830     unsigned LinkageID = (VarType >> 2) & 7;
01831     bool isConstant = VarType & 1;
01832     bool hasInitializer = VarType & 2;
01833     GlobalValue::LinkageTypes Linkage;
01834 
01835     switch (LinkageID) {
01836     case 0: Linkage = GlobalValue::ExternalLinkage;  break;
01837     case 1: Linkage = GlobalValue::WeakLinkage;      break;
01838     case 2: Linkage = GlobalValue::AppendingLinkage; break;
01839     case 3: Linkage = GlobalValue::InternalLinkage;  break;
01840     case 4: Linkage = GlobalValue::LinkOnceLinkage;  break;
01841     default: 
01842       error("Unknown linkage type: " + utostr(LinkageID));
01843       Linkage = GlobalValue::InternalLinkage;
01844       break;
01845     }
01846 
01847     const Type *Ty = getType(SlotNo);
01848     if (!Ty) {
01849       error("Global has no type! SlotNo=" + utostr(SlotNo));
01850     }
01851 
01852     if (!isa<PointerType>(Ty)) {
01853       error("Global not a pointer type! Ty= " + Ty->getDescription());
01854     }
01855 
01856     const Type *ElTy = cast<PointerType>(Ty)->getElementType();
01857 
01858     // Create the global variable...
01859     GlobalVariable *GV = new GlobalVariable(ElTy, isConstant, Linkage,
01860                                             0, "", TheModule);
01861     insertValue(GV, SlotNo, ModuleValues);
01862 
01863     unsigned initSlot = 0;
01864     if (hasInitializer) {   
01865       initSlot = read_vbr_uint();
01866       GlobalInits.push_back(std::make_pair(GV, initSlot));
01867     }
01868 
01869     // Notify handler about the global value.
01870     if (Handler)
01871       Handler->handleGlobalVariable(ElTy, isConstant, Linkage, SlotNo,initSlot);
01872 
01873     // Get next item
01874     VarType = read_vbr_uint();
01875   }
01876 
01877   // Read the function objects for all of the functions that are coming
01878   unsigned FnSignature = read_vbr_uint();
01879 
01880   if (hasNoFlagsForFunctions)
01881     FnSignature = (FnSignature << 5) + 1;
01882 
01883   // List is terminated by VoidTy.
01884   while ((FnSignature >> 5) != Type::VoidTyID) {
01885     const Type *Ty = getType(FnSignature >> 5);
01886     if (!isa<PointerType>(Ty) ||
01887         !isa<FunctionType>(cast<PointerType>(Ty)->getElementType())) {
01888       error("Function not a pointer to function type! Ty = " + 
01889             Ty->getDescription());
01890     }
01891 
01892     // We create functions by passing the underlying FunctionType to create...
01893     const FunctionType* FTy = 
01894       cast<FunctionType>(cast<PointerType>(Ty)->getElementType());
01895 
01896 
01897     // Insert the place holder.
01898     Function* Func = new Function(FTy, GlobalValue::ExternalLinkage, 
01899                                   "", TheModule);
01900     insertValue(Func, FnSignature >> 5, ModuleValues);
01901 
01902     // Flags are not used yet.
01903     unsigned Flags = FnSignature & 31;
01904 
01905     // Save this for later so we know type of lazily instantiated functions.
01906     // Note that known-external functions do not have FunctionInfo blocks, so we
01907     // do not add them to the FunctionSignatureList.
01908     if ((Flags & (1 << 4)) == 0)
01909       FunctionSignatureList.push_back(Func);
01910 
01911     if (Handler) Handler->handleFunctionDeclaration(Func);
01912 
01913     // Get the next function signature.
01914     FnSignature = read_vbr_uint();
01915     if (hasNoFlagsForFunctions)
01916       FnSignature = (FnSignature << 5) + 1;
01917   }
01918 
01919   // Now that the function signature list is set up, reverse it so that we can 
01920   // remove elements efficiently from the back of the vector.
01921   std::reverse(FunctionSignatureList.begin(), FunctionSignatureList.end());
01922 
01923   // If this bytecode format has dependent library information in it ..
01924   if (!hasNoDependentLibraries) {
01925     // Read in the number of dependent library items that follow
01926     unsigned num_dep_libs = read_vbr_uint();
01927     std::string dep_lib;
01928     while( num_dep_libs-- ) {
01929       dep_lib = read_str();
01930       TheModule->addLibrary(dep_lib);
01931       if (Handler)
01932         Handler->handleDependentLibrary(dep_lib);
01933     }
01934 
01935 
01936     // Read target triple and place into the module
01937     std::string triple = read_str();
01938     TheModule->setTargetTriple(triple);
01939     if (Handler)
01940       Handler->handleTargetTriple(triple);
01941   }
01942 
01943   if (hasInconsistentModuleGlobalInfo)
01944     align32();
01945 
01946   // This is for future proofing... in the future extra fields may be added that
01947   // we don't understand, so we transparently ignore them.
01948   //
01949   At = BlockEnd;
01950 
01951   if (Handler) Handler->handleModuleGlobalsEnd();
01952 }
01953 
01954 /// Parse the version information and decode it by setting flags on the
01955 /// Reader that enable backward compatibility of the reader.
01956 void BytecodeReader::ParseVersionInfo() {
01957   unsigned Version = read_vbr_uint();
01958 
01959   // Unpack version number: low four bits are for flags, top bits = version
01960   Module::Endianness  Endianness;
01961   Module::PointerSize PointerSize;
01962   Endianness  = (Version & 1) ? Module::BigEndian : Module::LittleEndian;
01963   PointerSize = (Version & 2) ? Module::Pointer64 : Module::Pointer32;
01964 
01965   bool hasNoEndianness = Version & 4;
01966   bool hasNoPointerSize = Version & 8;
01967   
01968   RevisionNum = Version >> 4;
01969 
01970   // Default values for the current bytecode version
01971   hasInconsistentModuleGlobalInfo = false;
01972   hasExplicitPrimitiveZeros = false;
01973   hasRestrictedGEPTypes = false;
01974   hasTypeDerivedFromValue = false;
01975   hasLongBlockHeaders = false;
01976   has32BitTypes = false;
01977   hasNoDependentLibraries = false;
01978   hasAlignment = false;
01979   hasInconsistentBBSlotNums = false;
01980   hasVBRByteTypes = false;
01981   hasUnnecessaryModuleBlockId = false;
01982   hasNoUndefValue = false;
01983   hasNoFlagsForFunctions = false;
01984   hasNoUnreachableInst = false;
01985 
01986   switch (RevisionNum) {
01987   case 0:               //  LLVM 1.0, 1.1 (Released)
01988     // Base LLVM 1.0 bytecode format.
01989     hasInconsistentModuleGlobalInfo = true;
01990     hasExplicitPrimitiveZeros = true;
01991 
01992     // FALL THROUGH
01993 
01994   case 1:               // LLVM 1.2 (Released)
01995     // LLVM 1.2 added explicit support for emitting strings efficiently.
01996 
01997     // Also, it fixed the problem where the size of the ModuleGlobalInfo block
01998     // included the size for the alignment at the end, where the rest of the
01999     // blocks did not.
02000 
02001     // LLVM 1.2 and before required that GEP indices be ubyte constants for
02002     // structures and longs for sequential types.
02003     hasRestrictedGEPTypes = true;
02004 
02005     // LLVM 1.2 and before had the Type class derive from Value class. This
02006     // changed in release 1.3 and consequently LLVM 1.3 bytecode files are
02007     // written differently because Types can no longer be part of the 
02008     // type planes for Values.
02009     hasTypeDerivedFromValue = true;
02010 
02011     // FALL THROUGH
02012     
02013   case 2:                // 1.2.5 (Not Released)
02014 
02015     // LLVM 1.2 and earlier had two-word block headers. This is a bit wasteful,
02016     // especially for small files where the 8 bytes per block is a large
02017     // fraction of the total block size. In LLVM 1.3, the block type and length
02018     // are compressed into a single 32-bit unsigned integer. 27 bits for length,
02019     // 5 bits for block type.
02020     hasLongBlockHeaders = true;
02021 
02022     // LLVM 1.2 and earlier wrote type slot numbers as vbr_uint32. In LLVM 1.3
02023     // this has been reduced to vbr_uint24. It shouldn't make much difference
02024     // since we haven't run into a module with > 24 million types, but for
02025     // safety the 24-bit restriction has been enforced in 1.3 to free some bits
02026     // in various places and to ensure consistency.
02027     has32BitTypes = true;
02028 
02029     // LLVM 1.2 and earlier did not provide a target triple nor a list of 
02030     // libraries on which the bytecode is dependent. LLVM 1.3 provides these
02031     // features, for use in future versions of LLVM.
02032     hasNoDependentLibraries = true;
02033 
02034     // FALL THROUGH
02035 
02036   case 3:               // LLVM 1.3 (Released)
02037     // LLVM 1.3 and earlier caused alignment bytes to be written on some block
02038     // boundaries and at the end of some strings. In extreme cases (e.g. lots 
02039     // of GEP references to a constant array), this can increase the file size
02040     // by 30% or more. In version 1.4 alignment is done away with completely.
02041     hasAlignment = true;
02042 
02043     // FALL THROUGH
02044     
02045   case 4:               // 1.3.1 (Not Released)
02046     // In version 4, we did not support the 'undef' constant.
02047     hasNoUndefValue = true;
02048 
02049     // In version 4 and above, we did not include space for flags for functions
02050     // in the module info block.
02051     hasNoFlagsForFunctions = true;
02052 
02053     // In version 4 and above, we did not include the 'unreachable' instruction
02054     // in the opcode numbering in the bytecode file.
02055     hasNoUnreachableInst = true;
02056     break;
02057 
02058     // FALL THROUGH
02059 
02060   case 5:               // 1.x.x (Not Released)
02061     break;
02062     // FIXME: NONE of this is implemented yet!
02063 
02064     // In version 5, basic blocks have a minimum index of 0 whereas all the 
02065     // other primitives have a minimum index of 1 (because 0 is the "null" 
02066     // value. In version 5, we made this consistent.
02067     hasInconsistentBBSlotNums = true;
02068 
02069     // In version 5, the types SByte and UByte were encoded as vbr_uint so that
02070     // signed values > 63 and unsigned values >127 would be encoded as two
02071     // bytes. In version 5, they are encoded directly in a single byte.
02072     hasVBRByteTypes = true;
02073 
02074     // In version 5, modules begin with a "Module Block" which encodes a 4-byte
02075     // integer value 0x01 to identify the module block. This is unnecessary and
02076     // removed in version 5.
02077     hasUnnecessaryModuleBlockId = true;
02078 
02079   default:
02080     error("Unknown bytecode version number: " + itostr(RevisionNum));
02081   }
02082 
02083   if (hasNoEndianness) Endianness  = Module::AnyEndianness;
02084   if (hasNoPointerSize) PointerSize = Module::AnyPointerSize;
02085 
02086   TheModule->setEndianness(Endianness);
02087   TheModule->setPointerSize(PointerSize);
02088 
02089   if (Handler) Handler->handleVersionInfo(RevisionNum, Endianness, PointerSize);
02090 }
02091 
02092 /// Parse a whole module.
02093 void BytecodeReader::ParseModule() {
02094   unsigned Type, Size;
02095 
02096   FunctionSignatureList.clear(); // Just in case...
02097 
02098   // Read into instance variables...
02099   ParseVersionInfo();
02100   align32();
02101 
02102   bool SeenModuleGlobalInfo = false;
02103   bool SeenGlobalTypePlane = false;
02104   BufPtr MyEnd = BlockEnd;
02105   while (At < MyEnd) {
02106     BufPtr OldAt = At;
02107     read_block(Type, Size);
02108 
02109     switch (Type) {
02110 
02111     case BytecodeFormat::GlobalTypePlaneBlockID:
02112       if (SeenGlobalTypePlane)
02113         error("Two GlobalTypePlane Blocks Encountered!");
02114 
02115       if (Size > 0)
02116         ParseGlobalTypes();
02117       SeenGlobalTypePlane = true;
02118       break;
02119 
02120     case BytecodeFormat::ModuleGlobalInfoBlockID: 
02121       if (SeenModuleGlobalInfo)
02122         error("Two ModuleGlobalInfo Blocks Encountered!");
02123       ParseModuleGlobalInfo();
02124       SeenModuleGlobalInfo = true;
02125       break;
02126 
02127     case BytecodeFormat::ConstantPoolBlockID:
02128       ParseConstantPool(ModuleValues, ModuleTypes,false);
02129       break;
02130 
02131     case BytecodeFormat::FunctionBlockID:
02132       ParseFunctionLazily();
02133       break;
02134 
02135     case BytecodeFormat::SymbolTableBlockID:
02136       ParseSymbolTable(0, &TheModule->getSymbolTable());
02137       break;
02138 
02139     default:
02140       At += Size;
02141       if (OldAt > At) {
02142         error("Unexpected Block of Type #" + utostr(Type) + " encountered!");
02143       }
02144       break;
02145     }
02146     BlockEnd = MyEnd;
02147     align32();
02148   }
02149 
02150   // After the module constant pool has been read, we can safely initialize
02151   // global variables...
02152   while (!GlobalInits.empty()) {
02153     GlobalVariable *GV = GlobalInits.back().first;
02154     unsigned Slot = GlobalInits.back().second;
02155     GlobalInits.pop_back();
02156 
02157     // Look up the initializer value...
02158     // FIXME: Preserve this type ID!
02159 
02160     const llvm::PointerType* GVType = GV->getType();
02161     unsigned TypeSlot = getTypeSlot(GVType->getElementType());
02162     if (Constant *CV = getConstantValue(TypeSlot, Slot)) {
02163       if (GV->hasInitializer()) 
02164         error("Global *already* has an initializer?!");
02165       if (Handler) Handler->handleGlobalInitializer(GV,CV);
02166       GV->setInitializer(CV);
02167     } else
02168       error("Cannot find initializer value.");
02169   }
02170 
02171   /// Make sure we pulled them all out. If we didn't then there's a declaration
02172   /// but a missing body. That's not allowed.
02173   if (!FunctionSignatureList.empty())
02174     error("Function declared, but bytecode stream ended before definition");
02175 }
02176 
02177 /// This function completely parses a bytecode buffer given by the \p Buf
02178 /// and \p Length parameters.
02179 void BytecodeReader::ParseBytecode(BufPtr Buf, unsigned Length, 
02180                                    const std::string &ModuleID) {
02181 
02182   try {
02183     RevisionNum = 0;
02184     At = MemStart = BlockStart = Buf;
02185     MemEnd = BlockEnd = Buf + Length;
02186 
02187     // Create the module
02188     TheModule = new Module(ModuleID);
02189 
02190     if (Handler) Handler->handleStart(TheModule, Length);
02191 
02192     // Read the four bytes of the signature.
02193     unsigned Sig = read_uint();
02194 
02195     // If this is a compressed file
02196     if (Sig == ('l' | ('l' << 8) | ('v' << 16) | ('c' << 24))) {
02197 
02198       // Invoke the decompression of the bytecode. Note that we have to skip the
02199       // file's magic number which is not part of the compressed block. Hence,
02200       // the Buf+4 and Length-4. The result goes into decompressedBlock, a data
02201       // member for retention until BytecodeReader is destructed.
02202       unsigned decompressedLength = Compressor::decompressToNewBuffer(
02203           (char*)Buf+4,Length-4,decompressedBlock);
02204 
02205       // We must adjust the buffer pointers used by the bytecode reader to point
02206       // into the new decompressed block. After decompression, the
02207       // decompressedBlock will point to a contiguous memory area that has
02208       // the decompressed data.
02209       At = MemStart = BlockStart = Buf = (BufPtr) decompressedBlock;
02210       MemEnd = BlockEnd = Buf + decompressedLength;
02211 
02212     // else if this isn't a regular (uncompressed) bytecode file, then its
02213     // and error, generate that now.
02214     } else if (Sig != ('l' | ('l' << 8) | ('v' << 16) | ('m' << 24))) {
02215       error("Invalid bytecode signature: " + utohexstr(Sig));
02216     }
02217 
02218     // Tell the handler we're starting a module
02219     if (Handler) Handler->handleModuleBegin(ModuleID);
02220 
02221     // Get the module block and size and verify. This is handled specially
02222     // because the module block/size is always written in long format. Other
02223     // blocks are written in short format so the read_block method is used.
02224     unsigned Type, Size;
02225     Type = read_uint();
02226     Size = read_uint();
02227     if (Type != BytecodeFormat::ModuleBlockID) {
02228       error("Expected Module Block! Type:" + utostr(Type) + ", Size:" 
02229             + utostr(Size));
02230     }
02231 
02232     // It looks like the darwin ranlib program is broken, and adds trailing
02233     // garbage to the end of some bytecode files.  This hack allows the bc
02234     // reader to ignore trailing garbage on bytecode files.
02235     if (At + Size < MemEnd)
02236       MemEnd = BlockEnd = At+Size;
02237 
02238     if (At + Size != MemEnd)
02239       error("Invalid Top Level Block Length! Type:" + utostr(Type)
02240             + ", Size:" + utostr(Size));
02241 
02242     // Parse the module contents
02243     this->ParseModule();
02244 
02245     // Check for missing functions
02246     if (hasFunctions())
02247       error("Function expected, but bytecode stream ended!");
02248 
02249     // Tell the handler we're done with the module
02250     if (Handler) 
02251       Handler->handleModuleEnd(ModuleID);
02252 
02253     // Tell the handler we're finished the parse
02254     if (Handler) Handler->handleFinish();
02255 
02256   } catch (std::string& errstr) {
02257     if (Handler) Handler->handleError(errstr);
02258     freeState();
02259     delete TheModule;
02260     TheModule = 0;
02261     if (decompressedBlock != 0 ) {
02262       ::free(decompressedBlock);
02263       decompressedBlock = 0;
02264     }
02265     throw;
02266   } catch (...) {
02267     std::string msg("Unknown Exception Occurred");
02268     if (Handler) Handler->handleError(msg);
02269     freeState();
02270     delete TheModule;
02271     TheModule = 0;
02272     if (decompressedBlock != 0) {
02273       ::free(decompressedBlock);
02274       decompressedBlock = 0;
02275     }
02276     throw msg;
02277   }
02278 }
02279 
02280 //===----------------------------------------------------------------------===//
02281 //=== Default Implementations of Handler Methods
02282 //===----------------------------------------------------------------------===//
02283 
02284 BytecodeHandler::~BytecodeHandler() {}
02285 
02286 // vim: sw=2