1 //===- BitcodeReader.cpp - Internal BitcodeReader implementation ----------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file was developed by Chris Lattner and is distributed under
6 // the University of Illinois Open Source License.  See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This header defines the BitcodeReader class.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/Bitcode/ReaderWriter.h"
15 #include "BitcodeReader.h"
16 #include "llvm/Constants.h"
17 #include "llvm/DerivedTypes.h"
18 #include "llvm/Instructions.h"
19 #include "llvm/Module.h"
20 #include "llvm/ParameterAttributes.h"
21 #include "llvm/ADT/SmallString.h"
22 #include "llvm/Support/MathExtras.h"
23 #include "llvm/Support/MemoryBuffer.h"
24 using namespace llvm;
25 
26 BitcodeReader::~BitcodeReader() {
27   delete Buffer;
28 }
29 
30 //===----------------------------------------------------------------------===//
31 //  Helper functions to implement forward reference resolution, etc.
32 //===----------------------------------------------------------------------===//
33 
34 /// ConvertToString - Convert a string from a record into an std::string, return
35 /// true on failure.
36 template<typename StrTy>
37 static bool ConvertToString(SmallVector<uint64_t, 64> &Record, unsigned Idx,
38                             StrTy &Result) {
39   if (Record.size() < Idx+1 || Record.size() < Record[Idx]+Idx+1)
40     return true;
41 
42   for (unsigned i = 0, e = Record[Idx]; i != e; ++i)
43     Result += (char)Record[Idx+i+1];
44   return false;
45 }
46 
47 static GlobalValue::LinkageTypes GetDecodedLinkage(unsigned Val) {
48   switch (Val) {
49   default: // Map unknown/new linkages to external
50   case 0: return GlobalValue::ExternalLinkage;
51   case 1: return GlobalValue::WeakLinkage;
52   case 2: return GlobalValue::AppendingLinkage;
53   case 3: return GlobalValue::InternalLinkage;
54   case 4: return GlobalValue::LinkOnceLinkage;
55   case 5: return GlobalValue::DLLImportLinkage;
56   case 6: return GlobalValue::DLLExportLinkage;
57   case 7: return GlobalValue::ExternalWeakLinkage;
58   }
59 }
60 
61 static GlobalValue::VisibilityTypes GetDecodedVisibility(unsigned Val) {
62   switch (Val) {
63   default: // Map unknown visibilities to default.
64   case 0: return GlobalValue::DefaultVisibility;
65   case 1: return GlobalValue::HiddenVisibility;
66   case 2: return GlobalValue::ProtectedVisibility;
67   }
68 }
69 
70 static int GetDecodedCastOpcode(unsigned Val) {
71   switch (Val) {
72   default: return -1;
73   case bitc::CAST_TRUNC   : return Instruction::Trunc;
74   case bitc::CAST_ZEXT    : return Instruction::ZExt;
75   case bitc::CAST_SEXT    : return Instruction::SExt;
76   case bitc::CAST_FPTOUI  : return Instruction::FPToUI;
77   case bitc::CAST_FPTOSI  : return Instruction::FPToSI;
78   case bitc::CAST_UITOFP  : return Instruction::UIToFP;
79   case bitc::CAST_SITOFP  : return Instruction::SIToFP;
80   case bitc::CAST_FPTRUNC : return Instruction::FPTrunc;
81   case bitc::CAST_FPEXT   : return Instruction::FPExt;
82   case bitc::CAST_PTRTOINT: return Instruction::PtrToInt;
83   case bitc::CAST_INTTOPTR: return Instruction::IntToPtr;
84   case bitc::CAST_BITCAST : return Instruction::BitCast;
85   }
86 }
87 static int GetDecodedBinaryOpcode(unsigned Val, const Type *Ty) {
88   switch (Val) {
89   default: return -1;
90   case bitc::BINOP_ADD:  return Instruction::Add;
91   case bitc::BINOP_SUB:  return Instruction::Sub;
92   case bitc::BINOP_MUL:  return Instruction::Mul;
93   case bitc::BINOP_UDIV: return Instruction::UDiv;
94   case bitc::BINOP_SDIV:
95     return Ty->isFPOrFPVector() ? Instruction::FDiv : Instruction::SDiv;
96   case bitc::BINOP_UREM: return Instruction::URem;
97   case bitc::BINOP_SREM:
98     return Ty->isFPOrFPVector() ? Instruction::FRem : Instruction::SRem;
99   case bitc::BINOP_SHL:  return Instruction::Shl;
100   case bitc::BINOP_LSHR: return Instruction::LShr;
101   case bitc::BINOP_ASHR: return Instruction::AShr;
102   case bitc::BINOP_AND:  return Instruction::And;
103   case bitc::BINOP_OR:   return Instruction::Or;
104   case bitc::BINOP_XOR:  return Instruction::Xor;
105   }
106 }
107 
108 
109 namespace {
110   /// @brief A class for maintaining the slot number definition
111   /// as a placeholder for the actual definition for forward constants defs.
112   class ConstantPlaceHolder : public ConstantExpr {
113     ConstantPlaceHolder();                       // DO NOT IMPLEMENT
114     void operator=(const ConstantPlaceHolder &); // DO NOT IMPLEMENT
115   public:
116     Use Op;
117     ConstantPlaceHolder(const Type *Ty)
118       : ConstantExpr(Ty, Instruction::UserOp1, &Op, 1),
119         Op(UndefValue::get(Type::Int32Ty), this) {
120     }
121   };
122 }
123 
124 Constant *BitcodeReaderValueList::getConstantFwdRef(unsigned Idx,
125                                                     const Type *Ty) {
126   if (Idx >= size()) {
127     // Insert a bunch of null values.
128     Uses.resize(Idx+1);
129     OperandList = &Uses[0];
130     NumOperands = Idx+1;
131   }
132 
133   if (Value *V = Uses[Idx]) {
134     assert(Ty == V->getType() && "Type mismatch in constant table!");
135     return cast<Constant>(V);
136   }
137 
138   // Create and return a placeholder, which will later be RAUW'd.
139   Constant *C = new ConstantPlaceHolder(Ty);
140   Uses[Idx].init(C, this);
141   return C;
142 }
143 
144 Value *BitcodeReaderValueList::getValueFwdRef(unsigned Idx, const Type *Ty) {
145   if (Idx >= size()) {
146     // Insert a bunch of null values.
147     Uses.resize(Idx+1);
148     OperandList = &Uses[0];
149     NumOperands = Idx+1;
150   }
151 
152   if (Value *V = Uses[Idx]) {
153     assert((Ty == 0 || Ty == V->getType()) && "Type mismatch in value table!");
154     return V;
155   }
156 
157   // No type specified, must be invalid reference.
158   if (Ty == 0) return 0;
159 
160   // Create and return a placeholder, which will later be RAUW'd.
161   Value *V = new Argument(Ty);
162   Uses[Idx].init(V, this);
163   return V;
164 }
165 
166 
167 const Type *BitcodeReader::getTypeByID(unsigned ID, bool isTypeTable) {
168   // If the TypeID is in range, return it.
169   if (ID < TypeList.size())
170     return TypeList[ID].get();
171   if (!isTypeTable) return 0;
172 
173   // The type table allows forward references.  Push as many Opaque types as
174   // needed to get up to ID.
175   while (TypeList.size() <= ID)
176     TypeList.push_back(OpaqueType::get());
177   return TypeList.back().get();
178 }
179 
180 //===----------------------------------------------------------------------===//
181 //  Functions for parsing blocks from the bitcode file
182 //===----------------------------------------------------------------------===//
183 
184 bool BitcodeReader::ParseParamAttrBlock() {
185   if (Stream.EnterSubBlock())
186     return Error("Malformed block record");
187 
188   if (!ParamAttrs.empty())
189     return Error("Multiple PARAMATTR blocks found!");
190 
191   SmallVector<uint64_t, 64> Record;
192 
193   ParamAttrsVector Attrs;
194 
195   // Read all the records.
196   while (1) {
197     unsigned Code = Stream.ReadCode();
198     if (Code == bitc::END_BLOCK) {
199       if (Stream.ReadBlockEnd())
200         return Error("Error at end of PARAMATTR block");
201       return false;
202     }
203 
204     if (Code == bitc::ENTER_SUBBLOCK) {
205       // No known subblocks, always skip them.
206       Stream.ReadSubBlockID();
207       if (Stream.SkipBlock())
208         return Error("Malformed block record");
209       continue;
210     }
211 
212     if (Code == bitc::DEFINE_ABBREV) {
213       Stream.ReadAbbrevRecord();
214       continue;
215     }
216 
217     // Read a record.
218     Record.clear();
219     switch (Stream.ReadRecord(Code, Record)) {
220     default:  // Default behavior: ignore.
221       break;
222     case bitc::PARAMATTR_CODE_ENTRY: { // ENTRY: [paramidx0, attr0, ...]
223       if (Record.size() & 1)
224         return Error("Invalid ENTRY record");
225 
226       ParamAttrsWithIndex PAWI;
227       for (unsigned i = 0, e = Record.size(); i != e; i += 2) {
228         PAWI.index = Record[i];
229         PAWI.attrs = Record[i+1];
230         Attrs.push_back(PAWI);
231       }
232       ParamAttrs.push_back(ParamAttrsList::get(Attrs));
233       Attrs.clear();
234       break;
235     }
236     }
237   }
238 }
239 
240 
241 bool BitcodeReader::ParseTypeTable() {
242   if (Stream.EnterSubBlock())
243     return Error("Malformed block record");
244 
245   if (!TypeList.empty())
246     return Error("Multiple TYPE_BLOCKs found!");
247 
248   SmallVector<uint64_t, 64> Record;
249   unsigned NumRecords = 0;
250 
251   // Read all the records for this type table.
252   while (1) {
253     unsigned Code = Stream.ReadCode();
254     if (Code == bitc::END_BLOCK) {
255       if (NumRecords != TypeList.size())
256         return Error("Invalid type forward reference in TYPE_BLOCK");
257       if (Stream.ReadBlockEnd())
258         return Error("Error at end of type table block");
259       return false;
260     }
261 
262     if (Code == bitc::ENTER_SUBBLOCK) {
263       // No known subblocks, always skip them.
264       Stream.ReadSubBlockID();
265       if (Stream.SkipBlock())
266         return Error("Malformed block record");
267       continue;
268     }
269 
270     if (Code == bitc::DEFINE_ABBREV) {
271       Stream.ReadAbbrevRecord();
272       continue;
273     }
274 
275     // Read a record.
276     Record.clear();
277     const Type *ResultTy = 0;
278     switch (Stream.ReadRecord(Code, Record)) {
279     default:  // Default behavior: unknown type.
280       ResultTy = 0;
281       break;
282     case bitc::TYPE_CODE_NUMENTRY: // TYPE_CODE_NUMENTRY: [numentries]
283       // TYPE_CODE_NUMENTRY contains a count of the number of types in the
284       // type list.  This allows us to reserve space.
285       if (Record.size() < 1)
286         return Error("Invalid TYPE_CODE_NUMENTRY record");
287       TypeList.reserve(Record[0]);
288       continue;
289     case bitc::TYPE_CODE_VOID:      // VOID
290       ResultTy = Type::VoidTy;
291       break;
292     case bitc::TYPE_CODE_FLOAT:     // FLOAT
293       ResultTy = Type::FloatTy;
294       break;
295     case bitc::TYPE_CODE_DOUBLE:    // DOUBLE
296       ResultTy = Type::DoubleTy;
297       break;
298     case bitc::TYPE_CODE_LABEL:     // LABEL
299       ResultTy = Type::LabelTy;
300       break;
301     case bitc::TYPE_CODE_OPAQUE:    // OPAQUE
302       ResultTy = 0;
303       break;
304     case bitc::TYPE_CODE_INTEGER:   // INTEGER: [width]
305       if (Record.size() < 1)
306         return Error("Invalid Integer type record");
307 
308       ResultTy = IntegerType::get(Record[0]);
309       break;
310     case bitc::TYPE_CODE_POINTER:   // POINTER: [pointee type]
311       if (Record.size() < 1)
312         return Error("Invalid POINTER type record");
313       ResultTy = PointerType::get(getTypeByID(Record[0], true));
314       break;
315     case bitc::TYPE_CODE_FUNCTION: {
316       // FUNCTION: [vararg, retty, #pararms, paramty N]
317       if (Record.size() < 3 || Record.size() < Record[2]+3)
318         return Error("Invalid FUNCTION type record");
319       std::vector<const Type*> ArgTys;
320       for (unsigned i = 0, e = Record[2]; i != e; ++i)
321         ArgTys.push_back(getTypeByID(Record[3+i], true));
322 
323       // FIXME: PARAM TYS.
324       ResultTy = FunctionType::get(getTypeByID(Record[1], true), ArgTys,
325                                    Record[0]);
326       break;
327     }
328     case bitc::TYPE_CODE_STRUCT: {  // STRUCT: [ispacked, #elts, eltty x N]
329       if (Record.size() < 2 || Record.size() < Record[1]+2)
330         return Error("Invalid STRUCT type record");
331       std::vector<const Type*> EltTys;
332       for (unsigned i = 0, e = Record[1]; i != e; ++i)
333         EltTys.push_back(getTypeByID(Record[2+i], true));
334       ResultTy = StructType::get(EltTys, Record[0]);
335       break;
336     }
337     case bitc::TYPE_CODE_ARRAY:     // ARRAY: [numelts, eltty]
338       if (Record.size() < 2)
339         return Error("Invalid ARRAY type record");
340       ResultTy = ArrayType::get(getTypeByID(Record[1], true), Record[0]);
341       break;
342     case bitc::TYPE_CODE_VECTOR:    // VECTOR: [numelts, eltty]
343       if (Record.size() < 2)
344         return Error("Invalid VECTOR type record");
345       ResultTy = VectorType::get(getTypeByID(Record[1], true), Record[0]);
346       break;
347     }
348 
349     if (NumRecords == TypeList.size()) {
350       // If this is a new type slot, just append it.
351       TypeList.push_back(ResultTy ? ResultTy : OpaqueType::get());
352       ++NumRecords;
353     } else if (ResultTy == 0) {
354       // Otherwise, this was forward referenced, so an opaque type was created,
355       // but the result type is actually just an opaque.  Leave the one we
356       // created previously.
357       ++NumRecords;
358     } else {
359       // Otherwise, this was forward referenced, so an opaque type was created.
360       // Resolve the opaque type to the real type now.
361       assert(NumRecords < TypeList.size() && "Typelist imbalance");
362       const OpaqueType *OldTy = cast<OpaqueType>(TypeList[NumRecords++].get());
363 
364       // Don't directly push the new type on the Tab. Instead we want to replace
365       // the opaque type we previously inserted with the new concrete value. The
366       // refinement from the abstract (opaque) type to the new type causes all
367       // uses of the abstract type to use the concrete type (NewTy). This will
368       // also cause the opaque type to be deleted.
369       const_cast<OpaqueType*>(OldTy)->refineAbstractTypeTo(ResultTy);
370 
371       // This should have replaced the old opaque type with the new type in the
372       // value table... or with a preexisting type that was already in the
373       // system.  Let's just make sure it did.
374       assert(TypeList[NumRecords-1].get() != OldTy &&
375              "refineAbstractType didn't work!");
376     }
377   }
378 }
379 
380 
381 bool BitcodeReader::ParseTypeSymbolTable() {
382   if (Stream.EnterSubBlock())
383     return Error("Malformed block record");
384 
385   SmallVector<uint64_t, 64> Record;
386 
387   // Read all the records for this type table.
388   std::string TypeName;
389   while (1) {
390     unsigned Code = Stream.ReadCode();
391     if (Code == bitc::END_BLOCK) {
392       if (Stream.ReadBlockEnd())
393         return Error("Error at end of type symbol table block");
394       return false;
395     }
396 
397     if (Code == bitc::ENTER_SUBBLOCK) {
398       // No known subblocks, always skip them.
399       Stream.ReadSubBlockID();
400       if (Stream.SkipBlock())
401         return Error("Malformed block record");
402       continue;
403     }
404 
405     if (Code == bitc::DEFINE_ABBREV) {
406       Stream.ReadAbbrevRecord();
407       continue;
408     }
409 
410     // Read a record.
411     Record.clear();
412     switch (Stream.ReadRecord(Code, Record)) {
413     default:  // Default behavior: unknown type.
414       break;
415     case bitc::TST_CODE_ENTRY:    // TST_ENTRY: [typeid, namelen, namechar x N]
416       if (ConvertToString(Record, 1, TypeName))
417         return Error("Invalid TST_ENTRY record");
418       unsigned TypeID = Record[0];
419       if (TypeID >= TypeList.size())
420         return Error("Invalid Type ID in TST_ENTRY record");
421 
422       TheModule->addTypeName(TypeName, TypeList[TypeID].get());
423       TypeName.clear();
424       break;
425     }
426   }
427 }
428 
429 bool BitcodeReader::ParseValueSymbolTable() {
430   if (Stream.EnterSubBlock())
431     return Error("Malformed block record");
432 
433   SmallVector<uint64_t, 64> Record;
434 
435   // Read all the records for this value table.
436   SmallString<128> ValueName;
437   while (1) {
438     unsigned Code = Stream.ReadCode();
439     if (Code == bitc::END_BLOCK) {
440       if (Stream.ReadBlockEnd())
441         return Error("Error at end of value symbol table block");
442       return false;
443     }
444     if (Code == bitc::ENTER_SUBBLOCK) {
445       // No known subblocks, always skip them.
446       Stream.ReadSubBlockID();
447       if (Stream.SkipBlock())
448         return Error("Malformed block record");
449       continue;
450     }
451 
452     if (Code == bitc::DEFINE_ABBREV) {
453       Stream.ReadAbbrevRecord();
454       continue;
455     }
456 
457     // Read a record.
458     Record.clear();
459     switch (Stream.ReadRecord(Code, Record)) {
460     default:  // Default behavior: unknown type.
461       break;
462     case bitc::VST_CODE_ENTRY: {  // VST_ENTRY: [valueid, namelen, namechar x N]
463       if (ConvertToString(Record, 1, ValueName))
464         return Error("Invalid TST_ENTRY record");
465       unsigned ValueID = Record[0];
466       if (ValueID >= ValueList.size())
467         return Error("Invalid Value ID in VST_ENTRY record");
468       Value *V = ValueList[ValueID];
469 
470       V->setName(&ValueName[0], ValueName.size());
471       ValueName.clear();
472       break;
473     }
474     case bitc::VST_CODE_BBENTRY: {
475       if (ConvertToString(Record, 1, ValueName))
476         return Error("Invalid VST_BBENTRY record");
477       BasicBlock *BB = getBasicBlock(Record[0]);
478       if (BB == 0)
479         return Error("Invalid BB ID in VST_BBENTRY record");
480 
481       BB->setName(&ValueName[0], ValueName.size());
482       ValueName.clear();
483       break;
484     }
485     }
486   }
487 }
488 
489 /// DecodeSignRotatedValue - Decode a signed value stored with the sign bit in
490 /// the LSB for dense VBR encoding.
491 static uint64_t DecodeSignRotatedValue(uint64_t V) {
492   if ((V & 1) == 0)
493     return V >> 1;
494   if (V != 1)
495     return -(V >> 1);
496   // There is no such thing as -0 with integers.  "-0" really means MININT.
497   return 1ULL << 63;
498 }
499 
500 /// ResolveGlobalAndAliasInits - Resolve all of the initializers for global
501 /// values and aliases that we can.
502 bool BitcodeReader::ResolveGlobalAndAliasInits() {
503   std::vector<std::pair<GlobalVariable*, unsigned> > GlobalInitWorklist;
504   std::vector<std::pair<GlobalAlias*, unsigned> > AliasInitWorklist;
505 
506   GlobalInitWorklist.swap(GlobalInits);
507   AliasInitWorklist.swap(AliasInits);
508 
509   while (!GlobalInitWorklist.empty()) {
510     unsigned ValID = GlobalInitWorklist.back().second;
511     if (ValID >= ValueList.size()) {
512       // Not ready to resolve this yet, it requires something later in the file.
513       GlobalInits.push_back(GlobalInitWorklist.back());
514     } else {
515       if (Constant *C = dyn_cast<Constant>(ValueList[ValID]))
516         GlobalInitWorklist.back().first->setInitializer(C);
517       else
518         return Error("Global variable initializer is not a constant!");
519     }
520     GlobalInitWorklist.pop_back();
521   }
522 
523   while (!AliasInitWorklist.empty()) {
524     unsigned ValID = AliasInitWorklist.back().second;
525     if (ValID >= ValueList.size()) {
526       AliasInits.push_back(AliasInitWorklist.back());
527     } else {
528       if (Constant *C = dyn_cast<Constant>(ValueList[ValID]))
529         AliasInitWorklist.back().first->setAliasee(C);
530       else
531         return Error("Alias initializer is not a constant!");
532     }
533     AliasInitWorklist.pop_back();
534   }
535   return false;
536 }
537 
538 
539 bool BitcodeReader::ParseConstants() {
540   if (Stream.EnterSubBlock())
541     return Error("Malformed block record");
542 
543   SmallVector<uint64_t, 64> Record;
544 
545   // Read all the records for this value table.
546   const Type *CurTy = Type::Int32Ty;
547   unsigned NextCstNo = ValueList.size();
548   while (1) {
549     unsigned Code = Stream.ReadCode();
550     if (Code == bitc::END_BLOCK) {
551       if (NextCstNo != ValueList.size())
552         return Error("Invalid constant reference!");
553 
554       if (Stream.ReadBlockEnd())
555         return Error("Error at end of constants block");
556       return false;
557     }
558 
559     if (Code == bitc::ENTER_SUBBLOCK) {
560       // No known subblocks, always skip them.
561       Stream.ReadSubBlockID();
562       if (Stream.SkipBlock())
563         return Error("Malformed block record");
564       continue;
565     }
566 
567     if (Code == bitc::DEFINE_ABBREV) {
568       Stream.ReadAbbrevRecord();
569       continue;
570     }
571 
572     // Read a record.
573     Record.clear();
574     Value *V = 0;
575     switch (Stream.ReadRecord(Code, Record)) {
576     default:  // Default behavior: unknown constant
577     case bitc::CST_CODE_UNDEF:     // UNDEF
578       V = UndefValue::get(CurTy);
579       break;
580     case bitc::CST_CODE_SETTYPE:   // SETTYPE: [typeid]
581       if (Record.empty())
582         return Error("Malformed CST_SETTYPE record");
583       if (Record[0] >= TypeList.size())
584         return Error("Invalid Type ID in CST_SETTYPE record");
585       CurTy = TypeList[Record[0]];
586       continue;  // Skip the ValueList manipulation.
587     case bitc::CST_CODE_NULL:      // NULL
588       V = Constant::getNullValue(CurTy);
589       break;
590     case bitc::CST_CODE_INTEGER:   // INTEGER: [intval]
591       if (!isa<IntegerType>(CurTy) || Record.empty())
592         return Error("Invalid CST_INTEGER record");
593       V = ConstantInt::get(CurTy, DecodeSignRotatedValue(Record[0]));
594       break;
595     case bitc::CST_CODE_WIDE_INTEGER: {// WIDE_INTEGER: [n, n x intval]
596       if (!isa<IntegerType>(CurTy) || Record.empty() ||
597           Record.size() < Record[0]+1)
598         return Error("Invalid WIDE_INTEGER record");
599 
600       unsigned NumWords = Record[0];
601       SmallVector<uint64_t, 8> Words;
602       Words.resize(NumWords);
603       for (unsigned i = 0; i != NumWords; ++i)
604         Words[i] = DecodeSignRotatedValue(Record[i+1]);
605       V = ConstantInt::get(APInt(cast<IntegerType>(CurTy)->getBitWidth(),
606                                  NumWords, &Words[0]));
607       break;
608     }
609     case bitc::CST_CODE_FLOAT:     // FLOAT: [fpval]
610       if (Record.empty())
611         return Error("Invalid FLOAT record");
612       if (CurTy == Type::FloatTy)
613         V = ConstantFP::get(CurTy, BitsToFloat(Record[0]));
614       else if (CurTy == Type::DoubleTy)
615         V = ConstantFP::get(CurTy, BitsToDouble(Record[0]));
616       else
617         V = UndefValue::get(CurTy);
618       break;
619 
620     case bitc::CST_CODE_AGGREGATE: {// AGGREGATE: [n, n x value number]
621       if (Record.empty() || Record.size() < Record[0]+1)
622         return Error("Invalid CST_AGGREGATE record");
623 
624       unsigned Size = Record[0];
625       std::vector<Constant*> Elts;
626 
627       if (const StructType *STy = dyn_cast<StructType>(CurTy)) {
628         for (unsigned i = 0; i != Size; ++i)
629           Elts.push_back(ValueList.getConstantFwdRef(Record[i+1],
630                                                      STy->getElementType(i)));
631         V = ConstantStruct::get(STy, Elts);
632       } else if (const ArrayType *ATy = dyn_cast<ArrayType>(CurTy)) {
633         const Type *EltTy = ATy->getElementType();
634         for (unsigned i = 0; i != Size; ++i)
635           Elts.push_back(ValueList.getConstantFwdRef(Record[i+1], EltTy));
636         V = ConstantArray::get(ATy, Elts);
637       } else if (const VectorType *VTy = dyn_cast<VectorType>(CurTy)) {
638         const Type *EltTy = VTy->getElementType();
639         for (unsigned i = 0; i != Size; ++i)
640           Elts.push_back(ValueList.getConstantFwdRef(Record[i+1], EltTy));
641         V = ConstantVector::get(Elts);
642       } else {
643         V = UndefValue::get(CurTy);
644       }
645       break;
646     }
647 
648     case bitc::CST_CODE_CE_BINOP: {  // CE_BINOP: [opcode, opval, opval]
649       if (Record.size() < 3) return Error("Invalid CE_BINOP record");
650       int Opc = GetDecodedBinaryOpcode(Record[0], CurTy);
651       if (Opc < 0) {
652         V = UndefValue::get(CurTy);  // Unknown binop.
653       } else {
654         Constant *LHS = ValueList.getConstantFwdRef(Record[1], CurTy);
655         Constant *RHS = ValueList.getConstantFwdRef(Record[2], CurTy);
656         V = ConstantExpr::get(Opc, LHS, RHS);
657       }
658       break;
659     }
660     case bitc::CST_CODE_CE_CAST: {  // CE_CAST: [opcode, opty, opval]
661       if (Record.size() < 3) return Error("Invalid CE_CAST record");
662       int Opc = GetDecodedCastOpcode(Record[0]);
663       if (Opc < 0) {
664         V = UndefValue::get(CurTy);  // Unknown cast.
665       } else {
666         const Type *OpTy = getTypeByID(Record[1]);
667         Constant *Op = ValueList.getConstantFwdRef(Record[2], OpTy);
668         V = ConstantExpr::getCast(Opc, Op, CurTy);
669       }
670       break;
671     }
672     case bitc::CST_CODE_CE_GEP: {  // CE_GEP:        [n x operands]
673       if ((Record.size() & 1) == 0) return Error("Invalid CE_GEP record");
674       SmallVector<Constant*, 16> Elts;
675       for (unsigned i = 1, e = Record.size(); i != e; i += 2) {
676         const Type *ElTy = getTypeByID(Record[i]);
677         if (!ElTy) return Error("Invalid CE_GEP record");
678         Elts.push_back(ValueList.getConstantFwdRef(Record[i+1], ElTy));
679       }
680       V = ConstantExpr::getGetElementPtr(Elts[0], &Elts[1], Elts.size()-1);
681       break;
682     }
683     case bitc::CST_CODE_CE_SELECT:  // CE_SELECT: [opval#, opval#, opval#]
684       if (Record.size() < 3) return Error("Invalid CE_SELECT record");
685       V = ConstantExpr::getSelect(ValueList.getConstantFwdRef(Record[0],
686                                                               Type::Int1Ty),
687                                   ValueList.getConstantFwdRef(Record[1],CurTy),
688                                   ValueList.getConstantFwdRef(Record[2],CurTy));
689       break;
690     case bitc::CST_CODE_CE_EXTRACTELT: { // CE_EXTRACTELT: [opty, opval, opval]
691       if (Record.size() < 3) return Error("Invalid CE_EXTRACTELT record");
692       const VectorType *OpTy =
693         dyn_cast_or_null<VectorType>(getTypeByID(Record[0]));
694       if (OpTy == 0) return Error("Invalid CE_EXTRACTELT record");
695       Constant *Op0 = ValueList.getConstantFwdRef(Record[1], OpTy);
696       Constant *Op1 = ValueList.getConstantFwdRef(Record[2],
697                                                   OpTy->getElementType());
698       V = ConstantExpr::getExtractElement(Op0, Op1);
699       break;
700     }
701     case bitc::CST_CODE_CE_INSERTELT: { // CE_INSERTELT: [opval, opval, opval]
702       const VectorType *OpTy = dyn_cast<VectorType>(CurTy);
703       if (Record.size() < 3 || OpTy == 0)
704         return Error("Invalid CE_INSERTELT record");
705       Constant *Op0 = ValueList.getConstantFwdRef(Record[0], OpTy);
706       Constant *Op1 = ValueList.getConstantFwdRef(Record[1],
707                                                   OpTy->getElementType());
708       Constant *Op2 = ValueList.getConstantFwdRef(Record[2], Type::Int32Ty);
709       V = ConstantExpr::getInsertElement(Op0, Op1, Op2);
710       break;
711     }
712     case bitc::CST_CODE_CE_SHUFFLEVEC: { // CE_SHUFFLEVEC: [opval, opval, opval]
713       const VectorType *OpTy = dyn_cast<VectorType>(CurTy);
714       if (Record.size() < 3 || OpTy == 0)
715         return Error("Invalid CE_INSERTELT record");
716       Constant *Op0 = ValueList.getConstantFwdRef(Record[0], OpTy);
717       Constant *Op1 = ValueList.getConstantFwdRef(Record[1], OpTy);
718       const Type *ShufTy=VectorType::get(Type::Int32Ty, OpTy->getNumElements());
719       Constant *Op2 = ValueList.getConstantFwdRef(Record[2], ShufTy);
720       V = ConstantExpr::getShuffleVector(Op0, Op1, Op2);
721       break;
722     }
723     case bitc::CST_CODE_CE_CMP: {     // CE_CMP: [opty, opval, opval, pred]
724       if (Record.size() < 4) return Error("Invalid CE_CMP record");
725       const Type *OpTy = getTypeByID(Record[0]);
726       if (OpTy == 0) return Error("Invalid CE_CMP record");
727       Constant *Op0 = ValueList.getConstantFwdRef(Record[1], OpTy);
728       Constant *Op1 = ValueList.getConstantFwdRef(Record[2], OpTy);
729 
730       if (OpTy->isFloatingPoint())
731         V = ConstantExpr::getFCmp(Record[3], Op0, Op1);
732       else
733         V = ConstantExpr::getICmp(Record[3], Op0, Op1);
734       break;
735     }
736     }
737 
738     ValueList.AssignValue(V, NextCstNo);
739     ++NextCstNo;
740   }
741 }
742 
743 /// RememberAndSkipFunctionBody - When we see the block for a function body,
744 /// remember where it is and then skip it.  This lets us lazily deserialize the
745 /// functions.
746 bool BitcodeReader::RememberAndSkipFunctionBody() {
747   // Get the function we are talking about.
748   if (FunctionsWithBodies.empty())
749     return Error("Insufficient function protos");
750 
751   Function *Fn = FunctionsWithBodies.back();
752   FunctionsWithBodies.pop_back();
753 
754   // Save the current stream state.
755   uint64_t CurBit = Stream.GetCurrentBitNo();
756   DeferredFunctionInfo[Fn] = std::make_pair(CurBit, Fn->getLinkage());
757 
758   // Set the functions linkage to GhostLinkage so we know it is lazily
759   // deserialized.
760   Fn->setLinkage(GlobalValue::GhostLinkage);
761 
762   // Skip over the function block for now.
763   if (Stream.SkipBlock())
764     return Error("Malformed block record");
765   return false;
766 }
767 
768 bool BitcodeReader::ParseModule(const std::string &ModuleID) {
769   // Reject multiple MODULE_BLOCK's in a single bitstream.
770   if (TheModule)
771     return Error("Multiple MODULE_BLOCKs in same stream");
772 
773   if (Stream.EnterSubBlock())
774     return Error("Malformed block record");
775 
776   // Otherwise, create the module.
777   TheModule = new Module(ModuleID);
778 
779   SmallVector<uint64_t, 64> Record;
780   std::vector<std::string> SectionTable;
781 
782   // Read all the records for this module.
783   while (!Stream.AtEndOfStream()) {
784     unsigned Code = Stream.ReadCode();
785     if (Code == bitc::END_BLOCK) {
786       if (Stream.ReadBlockEnd())
787         return Error("Error at end of module block");
788 
789       // Patch the initializers for globals and aliases up.
790       ResolveGlobalAndAliasInits();
791       if (!GlobalInits.empty() || !AliasInits.empty())
792         return Error("Malformed global initializer set");
793       if (!FunctionsWithBodies.empty())
794         return Error("Too few function bodies found");
795 
796       // Force deallocation of memory for these vectors to favor the client that
797       // want lazy deserialization.
798       std::vector<std::pair<GlobalVariable*, unsigned> >().swap(GlobalInits);
799       std::vector<std::pair<GlobalAlias*, unsigned> >().swap(AliasInits);
800       std::vector<Function*>().swap(FunctionsWithBodies);
801       return false;
802     }
803 
804     if (Code == bitc::ENTER_SUBBLOCK) {
805       switch (Stream.ReadSubBlockID()) {
806       default:  // Skip unknown content.
807         if (Stream.SkipBlock())
808           return Error("Malformed block record");
809         break;
810       case bitc::PARAMATTR_BLOCK_ID:
811         if (ParseParamAttrBlock())
812           return true;
813         break;
814       case bitc::TYPE_BLOCK_ID:
815         if (ParseTypeTable())
816           return true;
817         break;
818       case bitc::TYPE_SYMTAB_BLOCK_ID:
819         if (ParseTypeSymbolTable())
820           return true;
821         break;
822       case bitc::VALUE_SYMTAB_BLOCK_ID:
823         if (ParseValueSymbolTable())
824           return true;
825         break;
826       case bitc::CONSTANTS_BLOCK_ID:
827         if (ParseConstants() || ResolveGlobalAndAliasInits())
828           return true;
829         break;
830       case bitc::FUNCTION_BLOCK_ID:
831         // If this is the first function body we've seen, reverse the
832         // FunctionsWithBodies list.
833         if (!HasReversedFunctionsWithBodies) {
834           std::reverse(FunctionsWithBodies.begin(), FunctionsWithBodies.end());
835           HasReversedFunctionsWithBodies = true;
836         }
837 
838         if (RememberAndSkipFunctionBody())
839           return true;
840         break;
841       }
842       continue;
843     }
844 
845     if (Code == bitc::DEFINE_ABBREV) {
846       Stream.ReadAbbrevRecord();
847       continue;
848     }
849 
850     // Read a record.
851     switch (Stream.ReadRecord(Code, Record)) {
852     default: break;  // Default behavior, ignore unknown content.
853     case bitc::MODULE_CODE_VERSION:  // VERSION: [version#]
854       if (Record.size() < 1)
855         return Error("Malformed MODULE_CODE_VERSION");
856       // Only version #0 is supported so far.
857       if (Record[0] != 0)
858         return Error("Unknown bitstream version!");
859       break;
860     case bitc::MODULE_CODE_TRIPLE: {  // TRIPLE: [strlen, strchr x N]
861       std::string S;
862       if (ConvertToString(Record, 0, S))
863         return Error("Invalid MODULE_CODE_TRIPLE record");
864       TheModule->setTargetTriple(S);
865       break;
866     }
867     case bitc::MODULE_CODE_DATALAYOUT: {  // DATALAYOUT: [strlen, strchr x N]
868       std::string S;
869       if (ConvertToString(Record, 0, S))
870         return Error("Invalid MODULE_CODE_DATALAYOUT record");
871       TheModule->setDataLayout(S);
872       break;
873     }
874     case bitc::MODULE_CODE_ASM: {  // ASM: [strlen, strchr x N]
875       std::string S;
876       if (ConvertToString(Record, 0, S))
877         return Error("Invalid MODULE_CODE_ASM record");
878       TheModule->setModuleInlineAsm(S);
879       break;
880     }
881     case bitc::MODULE_CODE_DEPLIB: {  // DEPLIB: [strlen, strchr x N]
882       std::string S;
883       if (ConvertToString(Record, 0, S))
884         return Error("Invalid MODULE_CODE_DEPLIB record");
885       TheModule->addLibrary(S);
886       break;
887     }
888     case bitc::MODULE_CODE_SECTIONNAME: {  // SECTIONNAME: [strlen, strchr x N]
889       std::string S;
890       if (ConvertToString(Record, 0, S))
891         return Error("Invalid MODULE_CODE_SECTIONNAME record");
892       SectionTable.push_back(S);
893       break;
894     }
895     // GLOBALVAR: [type, isconst, initid,
896     //             linkage, alignment, section, visibility, threadlocal]
897     case bitc::MODULE_CODE_GLOBALVAR: {
898       if (Record.size() < 6)
899         return Error("Invalid MODULE_CODE_GLOBALVAR record");
900       const Type *Ty = getTypeByID(Record[0]);
901       if (!isa<PointerType>(Ty))
902         return Error("Global not a pointer type!");
903       Ty = cast<PointerType>(Ty)->getElementType();
904 
905       bool isConstant = Record[1];
906       GlobalValue::LinkageTypes Linkage = GetDecodedLinkage(Record[3]);
907       unsigned Alignment = (1 << Record[4]) >> 1;
908       std::string Section;
909       if (Record[5]) {
910         if (Record[5]-1 >= SectionTable.size())
911           return Error("Invalid section ID");
912         Section = SectionTable[Record[5]-1];
913       }
914       GlobalValue::VisibilityTypes Visibility = GlobalValue::DefaultVisibility;
915       if (Record.size() >= 6) Visibility = GetDecodedVisibility(Record[6]);
916       bool isThreadLocal = false;
917       if (Record.size() >= 7) isThreadLocal = Record[7];
918 
919       GlobalVariable *NewGV =
920         new GlobalVariable(Ty, isConstant, Linkage, 0, "", TheModule);
921       NewGV->setAlignment(Alignment);
922       if (!Section.empty())
923         NewGV->setSection(Section);
924       NewGV->setVisibility(Visibility);
925       NewGV->setThreadLocal(isThreadLocal);
926 
927       ValueList.push_back(NewGV);
928 
929       // Remember which value to use for the global initializer.
930       if (unsigned InitID = Record[2])
931         GlobalInits.push_back(std::make_pair(NewGV, InitID-1));
932       break;
933     }
934     // FUNCTION:  [type, callingconv, isproto, linkage, alignment, section,
935     //             visibility]
936     case bitc::MODULE_CODE_FUNCTION: {
937       if (Record.size() < 7)
938         return Error("Invalid MODULE_CODE_FUNCTION record");
939       const Type *Ty = getTypeByID(Record[0]);
940       if (!isa<PointerType>(Ty))
941         return Error("Function not a pointer type!");
942       const FunctionType *FTy =
943         dyn_cast<FunctionType>(cast<PointerType>(Ty)->getElementType());
944       if (!FTy)
945         return Error("Function not a pointer to function type!");
946 
947       Function *Func = new Function(FTy, GlobalValue::ExternalLinkage,
948                                     "", TheModule);
949 
950       Func->setCallingConv(Record[1]);
951       bool isProto = Record[2];
952       Func->setLinkage(GetDecodedLinkage(Record[3]));
953       Func->setAlignment((1 << Record[4]) >> 1);
954       if (Record[5]) {
955         if (Record[5]-1 >= SectionTable.size())
956           return Error("Invalid section ID");
957         Func->setSection(SectionTable[Record[5]-1]);
958       }
959       Func->setVisibility(GetDecodedVisibility(Record[6]));
960 
961       ValueList.push_back(Func);
962 
963       // If this is a function with a body, remember the prototype we are
964       // creating now, so that we can match up the body with them later.
965       if (!isProto)
966         FunctionsWithBodies.push_back(Func);
967       break;
968     }
969     // ALIAS: [alias type, aliasee val#, linkage]
970     case bitc::MODULE_CODE_ALIAS: {
971       if (Record.size() < 3)
972         return Error("Invalid MODULE_ALIAS record");
973       const Type *Ty = getTypeByID(Record[0]);
974       if (!isa<PointerType>(Ty))
975         return Error("Function not a pointer type!");
976 
977       GlobalAlias *NewGA = new GlobalAlias(Ty, GetDecodedLinkage(Record[2]),
978                                            "", 0, TheModule);
979       ValueList.push_back(NewGA);
980       AliasInits.push_back(std::make_pair(NewGA, Record[1]));
981       break;
982     }
983     /// MODULE_CODE_PURGEVALS: [numvals]
984     case bitc::MODULE_CODE_PURGEVALS:
985       // Trim down the value list to the specified size.
986       if (Record.size() < 1 || Record[0] > ValueList.size())
987         return Error("Invalid MODULE_PURGEVALS record");
988       ValueList.shrinkTo(Record[0]);
989       break;
990     }
991     Record.clear();
992   }
993 
994   return Error("Premature end of bitstream");
995 }
996 
997 
998 bool BitcodeReader::ParseBitcode() {
999   TheModule = 0;
1000 
1001   if (Buffer->getBufferSize() & 3)
1002     return Error("Bitcode stream should be a multiple of 4 bytes in length");
1003 
1004   unsigned char *BufPtr = (unsigned char *)Buffer->getBufferStart();
1005   Stream.init(BufPtr, BufPtr+Buffer->getBufferSize());
1006 
1007   // Sniff for the signature.
1008   if (Stream.Read(8) != 'B' ||
1009       Stream.Read(8) != 'C' ||
1010       Stream.Read(4) != 0x0 ||
1011       Stream.Read(4) != 0xC ||
1012       Stream.Read(4) != 0xE ||
1013       Stream.Read(4) != 0xD)
1014     return Error("Invalid bitcode signature");
1015 
1016   // We expect a number of well-defined blocks, though we don't necessarily
1017   // need to understand them all.
1018   while (!Stream.AtEndOfStream()) {
1019     unsigned Code = Stream.ReadCode();
1020 
1021     if (Code != bitc::ENTER_SUBBLOCK)
1022       return Error("Invalid record at top-level");
1023 
1024     unsigned BlockID = Stream.ReadSubBlockID();
1025 
1026     // We only know the MODULE subblock ID.
1027     if (BlockID == bitc::MODULE_BLOCK_ID) {
1028       if (ParseModule(Buffer->getBufferIdentifier()))
1029         return true;
1030     } else if (Stream.SkipBlock()) {
1031       return Error("Malformed block record");
1032     }
1033   }
1034 
1035   return false;
1036 }
1037 
1038 
1039 bool BitcodeReader::materializeFunction(Function *F, std::string *ErrInfo) {
1040   // If it already is material, ignore the request.
1041   if (!F->hasNotBeenReadFromBytecode()) return false;
1042 
1043   DenseMap<Function*, std::pair<uint64_t, unsigned> >::iterator DFII =
1044     DeferredFunctionInfo.find(F);
1045   assert(DFII != DeferredFunctionInfo.end() && "Deferred function not found!");
1046 
1047   // Move the bit stream to the saved position of the deferred function body and
1048   // restore the real linkage type for the function.
1049   Stream.JumpToBit(DFII->second.first);
1050   F->setLinkage((GlobalValue::LinkageTypes)DFII->second.second);
1051   DeferredFunctionInfo.erase(DFII);
1052 
1053   if (ParseFunctionBody(F)) {
1054     if (ErrInfo) *ErrInfo = ErrorString;
1055     return true;
1056   }
1057 
1058   return false;
1059 }
1060 
1061 Module *BitcodeReader::materializeModule(std::string *ErrInfo) {
1062   DenseMap<Function*, std::pair<uint64_t, unsigned> >::iterator I =
1063     DeferredFunctionInfo.begin();
1064   while (!DeferredFunctionInfo.empty()) {
1065     Function *F = (*I++).first;
1066     assert(F->hasNotBeenReadFromBytecode() &&
1067            "Deserialized function found in map!");
1068     if (materializeFunction(F, ErrInfo))
1069       return 0;
1070   }
1071   return TheModule;
1072 }
1073 
1074 
1075 /// ParseFunctionBody - Lazily parse the specified function body block.
1076 bool BitcodeReader::ParseFunctionBody(Function *F) {
1077   if (Stream.EnterSubBlock())
1078     return Error("Malformed block record");
1079 
1080   unsigned ModuleValueListSize = ValueList.size();
1081 
1082   // Add all the function arguments to the value table.
1083   for(Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; ++I)
1084     ValueList.push_back(I);
1085 
1086   unsigned NextValueNo = ValueList.size();
1087   BasicBlock *CurBB = 0;
1088   unsigned CurBBNo = 0;
1089 
1090   // Read all the records.
1091   SmallVector<uint64_t, 64> Record;
1092   while (1) {
1093     unsigned Code = Stream.ReadCode();
1094     if (Code == bitc::END_BLOCK) {
1095       if (Stream.ReadBlockEnd())
1096         return Error("Error at end of function block");
1097       break;
1098     }
1099 
1100     if (Code == bitc::ENTER_SUBBLOCK) {
1101       switch (Stream.ReadSubBlockID()) {
1102       default:  // Skip unknown content.
1103         if (Stream.SkipBlock())
1104           return Error("Malformed block record");
1105         break;
1106       case bitc::CONSTANTS_BLOCK_ID:
1107         if (ParseConstants()) return true;
1108         NextValueNo = ValueList.size();
1109         break;
1110       case bitc::VALUE_SYMTAB_BLOCK_ID:
1111         if (ParseValueSymbolTable()) return true;
1112         break;
1113       }
1114       continue;
1115     }
1116 
1117     if (Code == bitc::DEFINE_ABBREV) {
1118       Stream.ReadAbbrevRecord();
1119       continue;
1120     }
1121 
1122     // Read a record.
1123     Record.clear();
1124     Instruction *I = 0;
1125     switch (Stream.ReadRecord(Code, Record)) {
1126     default: // Default behavior: reject
1127       return Error("Unknown instruction");
1128     case bitc::FUNC_CODE_DECLAREBLOCKS:     // DECLAREBLOCKS: [nblocks]
1129       if (Record.size() < 1 || Record[0] == 0)
1130         return Error("Invalid DECLAREBLOCKS record");
1131       // Create all the basic blocks for the function.
1132       FunctionBBs.resize(Record[0]);
1133       for (unsigned i = 0, e = FunctionBBs.size(); i != e; ++i)
1134         FunctionBBs[i] = new BasicBlock("", F);
1135       CurBB = FunctionBBs[0];
1136       continue;
1137 
1138     case bitc::FUNC_CODE_INST_BINOP: {    // BINOP: [opcode, ty, opval, opval]
1139       if (Record.size() < 4) return Error("Invalid BINOP record");
1140       const Type *Ty = getTypeByID(Record[1]);
1141       int Opc = GetDecodedBinaryOpcode(Record[0], Ty);
1142       Value *LHS = getFnValueByID(Record[2], Ty);
1143       Value *RHS = getFnValueByID(Record[3], Ty);
1144       if (Opc == -1 || Ty == 0 || LHS == 0 || RHS == 0)
1145          return Error("Invalid BINOP record");
1146       I = BinaryOperator::create((Instruction::BinaryOps)Opc, LHS, RHS);
1147       break;
1148     }
1149     case bitc::FUNC_CODE_INST_CAST: {    // CAST: [opcode, ty, opty, opval]
1150       if (Record.size() < 4) return Error("Invalid CAST record");
1151       int Opc = GetDecodedCastOpcode(Record[0]);
1152       const Type *ResTy = getTypeByID(Record[1]);
1153       const Type *OpTy = getTypeByID(Record[2]);
1154       Value *Op = getFnValueByID(Record[3], OpTy);
1155       if (Opc == -1 || ResTy == 0 || OpTy == 0 || Op == 0)
1156         return Error("Invalid CAST record");
1157       I = CastInst::create((Instruction::CastOps)Opc, Op, ResTy);
1158       break;
1159     }
1160     case bitc::FUNC_CODE_INST_GEP: { // GEP: [n, n x operands]
1161       if (Record.size() < 2 || (Record.size() & 1))
1162         return Error("Invalid GEP record");
1163       const Type *OpTy = getTypeByID(Record[0]);
1164       Value *Op = getFnValueByID(Record[1], OpTy);
1165       if (OpTy == 0 || Op == 0)
1166         return Error("Invalid GEP record");
1167 
1168       SmallVector<Value*, 16> GEPIdx;
1169       for (unsigned i = 1, e = Record.size()/2; i != e; ++i) {
1170         const Type *IdxTy = getTypeByID(Record[i*2]);
1171         Value *Idx = getFnValueByID(Record[i*2+1], IdxTy);
1172         if (IdxTy == 0 || Idx == 0)
1173           return Error("Invalid GEP record");
1174         GEPIdx.push_back(Idx);
1175       }
1176 
1177       I = new GetElementPtrInst(Op, &GEPIdx[0], GEPIdx.size());
1178       break;
1179     }
1180 
1181     case bitc::FUNC_CODE_INST_SELECT: { // SELECT: [ty, opval, opval, opval]
1182       if (Record.size() < 4) return Error("Invalid SELECT record");
1183       const Type *Ty = getTypeByID(Record[0]);
1184       Value *Cond = getFnValueByID(Record[1], Type::Int1Ty);
1185       Value *LHS = getFnValueByID(Record[2], Ty);
1186       Value *RHS = getFnValueByID(Record[3], Ty);
1187       if (Ty == 0 || Cond == 0 || LHS == 0 || RHS == 0)
1188         return Error("Invalid SELECT record");
1189       I = new SelectInst(Cond, LHS, RHS);
1190       break;
1191     }
1192 
1193     case bitc::FUNC_CODE_INST_EXTRACTELT: { // EXTRACTELT: [opty, opval, opval]
1194       if (Record.size() < 3) return Error("Invalid EXTRACTELT record");
1195       const Type *OpTy = getTypeByID(Record[0]);
1196       Value *Vec = getFnValueByID(Record[1], OpTy);
1197       Value *Idx = getFnValueByID(Record[2], Type::Int32Ty);
1198       if (OpTy == 0 || Vec == 0 || Idx == 0)
1199         return Error("Invalid EXTRACTELT record");
1200       I = new ExtractElementInst(Vec, Idx);
1201       break;
1202     }
1203 
1204     case bitc::FUNC_CODE_INST_INSERTELT: { // INSERTELT: [ty, opval,opval,opval]
1205       if (Record.size() < 4) return Error("Invalid INSERTELT record");
1206       const VectorType *OpTy =
1207         dyn_cast_or_null<VectorType>(getTypeByID(Record[0]));
1208       if (OpTy == 0) return Error("Invalid INSERTELT record");
1209       Value *Vec = getFnValueByID(Record[1], OpTy);
1210       Value *Elt = getFnValueByID(Record[2], OpTy->getElementType());
1211       Value *Idx = getFnValueByID(Record[3], Type::Int32Ty);
1212       if (Vec == 0 || Elt == 0 || Idx == 0)
1213         return Error("Invalid INSERTELT record");
1214       I = new InsertElementInst(Vec, Elt, Idx);
1215       break;
1216     }
1217 
1218     case bitc::FUNC_CODE_INST_SHUFFLEVEC: {// SHUFFLEVEC: [ty,opval,opval,opval]
1219       if (Record.size() < 4) return Error("Invalid SHUFFLEVEC record");
1220       const VectorType *OpTy =
1221         dyn_cast_or_null<VectorType>(getTypeByID(Record[0]));
1222       if (OpTy == 0) return Error("Invalid SHUFFLEVEC record");
1223       Value *Vec1 = getFnValueByID(Record[1], OpTy);
1224       Value *Vec2 = getFnValueByID(Record[2], OpTy);
1225       Value *Mask = getFnValueByID(Record[3],
1226                                    VectorType::get(Type::Int32Ty,
1227                                                    OpTy->getNumElements()));
1228       if (Vec1 == 0 || Vec2 == 0 || Mask == 0)
1229         return Error("Invalid SHUFFLEVEC record");
1230       I = new ShuffleVectorInst(Vec1, Vec2, Mask);
1231       break;
1232     }
1233 
1234     case bitc::FUNC_CODE_INST_CMP: { // CMP: [opty, opval, opval, pred]
1235       if (Record.size() < 4) return Error("Invalid CMP record");
1236       const Type *OpTy = getTypeByID(Record[0]);
1237       Value *LHS = getFnValueByID(Record[1], OpTy);
1238       Value *RHS = getFnValueByID(Record[2], OpTy);
1239       if (OpTy == 0 || LHS == 0 || RHS == 0)
1240         return Error("Invalid CMP record");
1241       if (OpTy->isFPOrFPVector())
1242         I = new FCmpInst((FCmpInst::Predicate)Record[3], LHS, RHS);
1243       else
1244         I = new ICmpInst((ICmpInst::Predicate)Record[3], LHS, RHS);
1245       break;
1246     }
1247 
1248     case bitc::FUNC_CODE_INST_RET: // RET: [opty,opval<optional>]
1249       if (Record.size() == 0) {
1250         I = new ReturnInst();
1251         break;
1252       }
1253       if (Record.size() == 2) {
1254         const Type *OpTy = getTypeByID(Record[0]);
1255         Value *Op = getFnValueByID(Record[1], OpTy);
1256         if (!OpTy || !Op)
1257           return Error("Invalid RET record");
1258         I = new ReturnInst(Op);
1259         break;
1260       }
1261       return Error("Invalid RET record");
1262     case bitc::FUNC_CODE_INST_BR: { // BR: [bb#, bb#, opval] or [bb#]
1263       if (Record.size() != 1 && Record.size() != 3)
1264         return Error("Invalid BR record");
1265       BasicBlock *TrueDest = getBasicBlock(Record[0]);
1266       if (TrueDest == 0)
1267         return Error("Invalid BR record");
1268 
1269       if (Record.size() == 1)
1270         I = new BranchInst(TrueDest);
1271       else {
1272         BasicBlock *FalseDest = getBasicBlock(Record[1]);
1273         Value *Cond = getFnValueByID(Record[2], Type::Int1Ty);
1274         if (FalseDest == 0 || Cond == 0)
1275           return Error("Invalid BR record");
1276         I = new BranchInst(TrueDest, FalseDest, Cond);
1277       }
1278       break;
1279     }
1280     case bitc::FUNC_CODE_INST_SWITCH: { // SWITCH: [opty, opval, n, n x ops]
1281       if (Record.size() < 3 || (Record.size() & 1) == 0)
1282         return Error("Invalid SWITCH record");
1283       const Type *OpTy = getTypeByID(Record[0]);
1284       Value *Cond = getFnValueByID(Record[1], OpTy);
1285       BasicBlock *Default = getBasicBlock(Record[2]);
1286       if (OpTy == 0 || Cond == 0 || Default == 0)
1287         return Error("Invalid SWITCH record");
1288       unsigned NumCases = (Record.size()-3)/2;
1289       SwitchInst *SI = new SwitchInst(Cond, Default, NumCases);
1290       for (unsigned i = 0, e = NumCases; i != e; ++i) {
1291         ConstantInt *CaseVal =
1292           dyn_cast_or_null<ConstantInt>(getFnValueByID(Record[3+i*2], OpTy));
1293         BasicBlock *DestBB = getBasicBlock(Record[1+3+i*2]);
1294         if (CaseVal == 0 || DestBB == 0) {
1295           delete SI;
1296           return Error("Invalid SWITCH record!");
1297         }
1298         SI->addCase(CaseVal, DestBB);
1299       }
1300       I = SI;
1301       break;
1302     }
1303 
1304     case bitc::FUNC_CODE_INST_INVOKE: { // INVOKE: [cc,fnty, op0,op1,op2, ...]
1305       if (Record.size() < 5)
1306         return Error("Invalid INVOKE record");
1307       unsigned CCInfo = Record[0];
1308       const PointerType *CalleeTy =
1309         dyn_cast_or_null<PointerType>(getTypeByID(Record[1]));
1310       Value *Callee = getFnValueByID(Record[2], CalleeTy);
1311       BasicBlock *NormalBB = getBasicBlock(Record[3]);
1312       BasicBlock *UnwindBB = getBasicBlock(Record[4]);
1313       if (CalleeTy == 0 || Callee == 0 || NormalBB == 0 || UnwindBB == 0)
1314         return Error("Invalid INVOKE record");
1315 
1316       const FunctionType *FTy =
1317         dyn_cast<FunctionType>(CalleeTy->getElementType());
1318 
1319       // Check that the right number of fixed parameters are here.
1320       if (FTy == 0 || Record.size() < 5+FTy->getNumParams())
1321         return Error("Invalid INVOKE record");
1322 
1323       SmallVector<Value*, 16> Ops;
1324       for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i) {
1325         Ops.push_back(getFnValueByID(Record[5+i], FTy->getParamType(i)));
1326         if (Ops.back() == 0)
1327           return Error("Invalid INVOKE record");
1328       }
1329 
1330       unsigned FirstVarargParam = 5+FTy->getNumParams();
1331       if (FTy->isVarArg()) {
1332         // Read type/value pairs for varargs params.
1333         if ((Record.size()-FirstVarargParam) & 1)
1334           return Error("Invalid INVOKE record");
1335 
1336         for (unsigned i = FirstVarargParam, e = Record.size(); i != e; i += 2) {
1337           const Type *ArgTy = getTypeByID(Record[i]);
1338           Ops.push_back(getFnValueByID(Record[i+1], ArgTy));
1339           if (Ops.back() == 0 || ArgTy == 0)
1340             return Error("Invalid INVOKE record");
1341         }
1342       } else {
1343         if (Record.size() != FirstVarargParam)
1344           return Error("Invalid INVOKE record");
1345       }
1346 
1347       I = new InvokeInst(Callee, NormalBB, UnwindBB, &Ops[0], Ops.size());
1348       cast<InvokeInst>(I)->setCallingConv(CCInfo);
1349       break;
1350     }
1351     case bitc::FUNC_CODE_INST_UNWIND: // UNWIND
1352       I = new UnwindInst();
1353       break;
1354     case bitc::FUNC_CODE_INST_UNREACHABLE: // UNREACHABLE
1355       I = new UnreachableInst();
1356       break;
1357     case bitc::FUNC_CODE_INST_PHI: { // PHI: [ty, #ops, val0,bb0, ...]
1358       if (Record.size() < 2 || Record.size() < 2+Record[1] || (Record[1]&1))
1359         return Error("Invalid PHI record");
1360       const Type *Ty = getTypeByID(Record[0]);
1361       if (!Ty) return Error("Invalid PHI record");
1362 
1363       PHINode *PN = new PHINode(Ty);
1364       PN->reserveOperandSpace(Record[1]);
1365 
1366       for (unsigned i = 0, e = Record[1]; i != e; i += 2) {
1367         Value *V = getFnValueByID(Record[2+i], Ty);
1368         BasicBlock *BB = getBasicBlock(Record[3+i]);
1369         if (!V || !BB) return Error("Invalid PHI record");
1370         PN->addIncoming(V, BB);
1371       }
1372       I = PN;
1373       break;
1374     }
1375 
1376     case bitc::FUNC_CODE_INST_MALLOC: { // MALLOC: [instty, op, align]
1377       if (Record.size() < 3)
1378         return Error("Invalid MALLOC record");
1379       const PointerType *Ty =
1380         dyn_cast_or_null<PointerType>(getTypeByID(Record[0]));
1381       Value *Size = getFnValueByID(Record[1], Type::Int32Ty);
1382       unsigned Align = Record[2];
1383       if (!Ty || !Size) return Error("Invalid MALLOC record");
1384       I = new MallocInst(Ty->getElementType(), Size, (1 << Align) >> 1);
1385       break;
1386     }
1387     case bitc::FUNC_CODE_INST_FREE: { // FREE: [opty, op]
1388       if (Record.size() < 2)
1389         return Error("Invalid FREE record");
1390       const Type *OpTy = getTypeByID(Record[0]);
1391       Value *Op = getFnValueByID(Record[1], OpTy);
1392       if (!OpTy || !Op)
1393         return Error("Invalid FREE record");
1394       I = new FreeInst(Op);
1395       break;
1396     }
1397     case bitc::FUNC_CODE_INST_ALLOCA: { // ALLOCA: [instty, op, align]
1398       if (Record.size() < 3)
1399         return Error("Invalid ALLOCA record");
1400       const PointerType *Ty =
1401         dyn_cast_or_null<PointerType>(getTypeByID(Record[0]));
1402       Value *Size = getFnValueByID(Record[1], Type::Int32Ty);
1403       unsigned Align = Record[2];
1404       if (!Ty || !Size) return Error("Invalid ALLOCA record");
1405       I = new AllocaInst(Ty->getElementType(), Size, (1 << Align) >> 1);
1406       break;
1407     }
1408     case bitc::FUNC_CODE_INST_LOAD: { // LOAD: [opty, op, align, vol]
1409       if (Record.size() < 4)
1410         return Error("Invalid LOAD record");
1411       const Type *OpTy = getTypeByID(Record[0]);
1412       Value *Op = getFnValueByID(Record[1], OpTy);
1413       if (!OpTy || !Op)
1414         return Error("Invalid LOAD record");
1415       I = new LoadInst(Op, "", Record[3], (1 << Record[2]) >> 1);
1416       break;
1417     }
1418     case bitc::FUNC_CODE_INST_STORE: { // STORE:[ptrty,val,ptr, align, vol]
1419       if (Record.size() < 5)
1420         return Error("Invalid LOAD record");
1421       const PointerType *OpTy =
1422         dyn_cast_or_null<PointerType>(getTypeByID(Record[0]));
1423       Value *Op = getFnValueByID(Record[1], OpTy ? OpTy->getElementType() : 0);
1424       Value *Ptr = getFnValueByID(Record[2], OpTy);
1425       if (!OpTy || !Op || !Ptr)
1426         return Error("Invalid STORE record");
1427       I = new StoreInst(Op, Ptr, (1 << Record[3]) >> 1, Record[4]);
1428       break;
1429     }
1430     case bitc::FUNC_CODE_INST_CALL: { // CALL: [cc, fnty, fnid, arg0, arg1...]
1431       if (Record.size() < 3)
1432         return Error("Invalid CALL record");
1433       unsigned CCInfo = Record[0];
1434       const PointerType *OpTy =
1435         dyn_cast_or_null<PointerType>(getTypeByID(Record[1]));
1436       const FunctionType *FTy = 0;
1437       if (OpTy) FTy = dyn_cast<FunctionType>(OpTy->getElementType());
1438       Value *Callee = getFnValueByID(Record[2], OpTy);
1439       if (!FTy || !Callee || Record.size() < FTy->getNumParams()+3)
1440         return Error("Invalid CALL record");
1441 
1442       SmallVector<Value*, 16> Args;
1443       // Read the fixed params.
1444       for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i) {
1445         Args.push_back(getFnValueByID(Record[i+3], FTy->getParamType(i)));
1446         if (Args.back() == 0) return Error("Invalid CALL record");
1447       }
1448 
1449 
1450       // Read type/value pairs for varargs params.
1451       unsigned NextArg = FTy->getNumParams()+3;
1452       if (!FTy->isVarArg()) {
1453         if (NextArg != Record.size())
1454           return Error("Invalid CALL record");
1455       } else {
1456         if ((Record.size()-NextArg) & 1)
1457           return Error("Invalid CALL record");
1458         for (unsigned e = Record.size(); NextArg != e; NextArg += 2) {
1459           Args.push_back(getFnValueByID(Record[NextArg+1],
1460                                         getTypeByID(Record[NextArg])));
1461           if (Args.back() == 0) return Error("Invalid CALL record");
1462         }
1463       }
1464 
1465       I = new CallInst(Callee, &Args[0], Args.size());
1466       cast<CallInst>(I)->setCallingConv(CCInfo>>1);
1467       cast<CallInst>(I)->setTailCall(CCInfo & 1);
1468       break;
1469     }
1470     case bitc::FUNC_CODE_INST_VAARG: { // VAARG: [valistty, valist, instty]
1471       if (Record.size() < 3)
1472         return Error("Invalid VAARG record");
1473       const Type *OpTy = getTypeByID(Record[0]);
1474       Value *Op = getFnValueByID(Record[1], OpTy);
1475       const Type *ResTy = getTypeByID(Record[2]);
1476       if (!OpTy || !Op || !ResTy)
1477         return Error("Invalid VAARG record");
1478       I = new VAArgInst(Op, ResTy);
1479       break;
1480     }
1481     }
1482 
1483     // Add instruction to end of current BB.  If there is no current BB, reject
1484     // this file.
1485     if (CurBB == 0) {
1486       delete I;
1487       return Error("Invalid instruction with no BB");
1488     }
1489     CurBB->getInstList().push_back(I);
1490 
1491     // If this was a terminator instruction, move to the next block.
1492     if (isa<TerminatorInst>(I)) {
1493       ++CurBBNo;
1494       CurBB = CurBBNo < FunctionBBs.size() ? FunctionBBs[CurBBNo] : 0;
1495     }
1496 
1497     // Non-void values get registered in the value table for future use.
1498     if (I && I->getType() != Type::VoidTy)
1499       ValueList.AssignValue(I, NextValueNo++);
1500   }
1501 
1502   // Check the function list for unresolved values.
1503   if (Argument *A = dyn_cast<Argument>(ValueList.back())) {
1504     if (A->getParent() == 0) {
1505       // We found at least one unresolved value.  Nuke them all to avoid leaks.
1506       for (unsigned i = ModuleValueListSize, e = ValueList.size(); i != e; ++i){
1507         if ((A = dyn_cast<Argument>(ValueList.back())) && A->getParent() == 0) {
1508           A->replaceAllUsesWith(UndefValue::get(A->getType()));
1509           delete A;
1510         }
1511       }
1512     }
1513     return Error("Never resolved value found in function!");
1514   }
1515 
1516   // Trim the value list down to the size it was before we parsed this function.
1517   ValueList.shrinkTo(ModuleValueListSize);
1518   std::vector<BasicBlock*>().swap(FunctionBBs);
1519 
1520   return false;
1521 }
1522 
1523 
1524 //===----------------------------------------------------------------------===//
1525 // External interface
1526 //===----------------------------------------------------------------------===//
1527 
1528 /// getBitcodeModuleProvider - lazy function-at-a-time loading from a file.
1529 ///
1530 ModuleProvider *llvm::getBitcodeModuleProvider(MemoryBuffer *Buffer,
1531                                                std::string *ErrMsg) {
1532   BitcodeReader *R = new BitcodeReader(Buffer);
1533   if (R->ParseBitcode()) {
1534     if (ErrMsg)
1535       *ErrMsg = R->getErrorString();
1536 
1537     // Don't let the BitcodeReader dtor delete 'Buffer'.
1538     R->releaseMemoryBuffer();
1539     delete R;
1540     return 0;
1541   }
1542   return R;
1543 }
1544 
1545 /// ParseBitcodeFile - Read the specified bitcode file, returning the module.
1546 /// If an error occurs, return null and fill in *ErrMsg if non-null.
1547 Module *llvm::ParseBitcodeFile(MemoryBuffer *Buffer, std::string *ErrMsg){
1548   BitcodeReader *R;
1549   R = static_cast<BitcodeReader*>(getBitcodeModuleProvider(Buffer, ErrMsg));
1550   if (!R) return 0;
1551 
1552   // Read the whole module, get a pointer to it, tell ModuleProvider not to
1553   // delete it when its dtor is run.
1554   Module *M = R->releaseModule(ErrMsg);
1555 
1556   // Don't let the BitcodeReader dtor delete 'Buffer'.
1557   R->releaseMemoryBuffer();
1558   delete R;
1559   return M;
1560 }
1561