BitcodeReader.cpp revision 0eef08046e0758f1800f32c63b817fd22264577b 
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 "BitcodeReader.h"
15#include "llvm/Bitcode/BitstreamReader.h"
16#include "llvm/Constants.h"
17#include "llvm/DerivedTypes.h"
18#include "llvm/Module.h"
19#include "llvm/ADT/SmallString.h"
20#include "llvm/Support/MathExtras.h"
21using namespace llvm;
22
23/// ConvertToString - Convert a string from a record into an std::string, return
24/// true on failure.
25template<typename StrTy>
26static bool ConvertToString(SmallVector<uint64_t, 64> &Record, unsigned Idx,
27                            StrTy &Result) {
28  if (Record.size() < Idx+1 || Record.size() < Record[Idx]+Idx+1)
29    return true;
30
31  for (unsigned i = 0, e = Record[Idx]; i != e; ++i)
32    Result += (char)Record[Idx+i+1];
33  return false;
34}
35
36static GlobalValue::LinkageTypes GetDecodedLinkage(unsigned Val) {
37  switch (Val) {
38  default: // Map unknown/new linkages to external
39  case 0: return GlobalValue::ExternalLinkage;
40  case 1: return GlobalValue::WeakLinkage;
41  case 2: return GlobalValue::AppendingLinkage;
42  case 3: return GlobalValue::InternalLinkage;
43  case 4: return GlobalValue::LinkOnceLinkage;
44  case 5: return GlobalValue::DLLImportLinkage;
45  case 6: return GlobalValue::DLLExportLinkage;
46  case 7: return GlobalValue::ExternalWeakLinkage;
47  }
48}
49
50static GlobalValue::VisibilityTypes GetDecodedVisibility(unsigned Val) {
51  switch (Val) {
52  default: // Map unknown visibilities to default.
53  case 0: return GlobalValue::DefaultVisibility;
54  case 1: return GlobalValue::HiddenVisibility;
55  }
56}
57
58
59const Type *BitcodeReader::getTypeByID(unsigned ID, bool isTypeTable) {
60  // If the TypeID is in range, return it.
61  if (ID < TypeList.size())
62    return TypeList[ID].get();
63  if (!isTypeTable) return 0;
64
65  // The type table allows forward references.  Push as many Opaque types as
66  // needed to get up to ID.
67  while (TypeList.size() <= ID)
68    TypeList.push_back(OpaqueType::get());
69  return TypeList.back().get();
70}
71
72
73bool BitcodeReader::ParseTypeTable(BitstreamReader &Stream) {
74  if (Stream.EnterSubBlock())
75    return Error("Malformed block record");
76
77  if (!TypeList.empty())
78    return Error("Multiple TYPE_BLOCKs found!");
79
80  SmallVector<uint64_t, 64> Record;
81  unsigned NumRecords = 0;
82
83  // Read all the records for this type table.
84  while (1) {
85    unsigned Code = Stream.ReadCode();
86    if (Code == bitc::END_BLOCK) {
87      if (NumRecords != TypeList.size())
88        return Error("Invalid type forward reference in TYPE_BLOCK");
89      return Stream.ReadBlockEnd();
90    }
91
92    if (Code == bitc::ENTER_SUBBLOCK) {
93      // No known subblocks, always skip them.
94      Stream.ReadSubBlockID();
95      if (Stream.SkipBlock())
96        return Error("Malformed block record");
97      continue;
98    }
99
100    if (Code == bitc::DEFINE_ABBREV) {
101      Stream.ReadAbbrevRecord();
102      continue;
103    }
104
105    // Read a record.
106    Record.clear();
107    const Type *ResultTy = 0;
108    switch (Stream.ReadRecord(Code, Record)) {
109    default:  // Default behavior: unknown type.
110      ResultTy = 0;
111      break;
112    case bitc::TYPE_CODE_NUMENTRY: // TYPE_CODE_NUMENTRY: [numentries]
113      // TYPE_CODE_NUMENTRY contains a count of the number of types in the
114      // type list.  This allows us to reserve space.
115      if (Record.size() < 1)
116        return Error("Invalid TYPE_CODE_NUMENTRY record");
117      TypeList.reserve(Record[0]);
118      continue;
119    case bitc::TYPE_CODE_META:      // TYPE_CODE_META: [metacode]...
120      // No metadata supported yet.
121      if (Record.size() < 1)
122        return Error("Invalid TYPE_CODE_META record");
123      continue;
124
125    case bitc::TYPE_CODE_VOID:      // VOID
126      ResultTy = Type::VoidTy;
127      break;
128    case bitc::TYPE_CODE_FLOAT:     // FLOAT
129      ResultTy = Type::FloatTy;
130      break;
131    case bitc::TYPE_CODE_DOUBLE:    // DOUBLE
132      ResultTy = Type::DoubleTy;
133      break;
134    case bitc::TYPE_CODE_LABEL:     // LABEL
135      ResultTy = Type::LabelTy;
136      break;
137    case bitc::TYPE_CODE_OPAQUE:    // OPAQUE
138      ResultTy = 0;
139      break;
140    case bitc::TYPE_CODE_INTEGER:   // INTEGER: [width]
141      if (Record.size() < 1)
142        return Error("Invalid Integer type record");
143
144      ResultTy = IntegerType::get(Record[0]);
145      break;
146    case bitc::TYPE_CODE_POINTER:   // POINTER: [pointee type]
147      if (Record.size() < 1)
148        return Error("Invalid POINTER type record");
149      ResultTy = PointerType::get(getTypeByID(Record[0], true));
150      break;
151    case bitc::TYPE_CODE_FUNCTION: {
152      // FUNCTION: [vararg, retty, #pararms, paramty N]
153      if (Record.size() < 3 || Record.size() < Record[2]+3)
154        return Error("Invalid FUNCTION type record");
155      std::vector<const Type*> ArgTys;
156      for (unsigned i = 0, e = Record[2]; i != e; ++i)
157        ArgTys.push_back(getTypeByID(Record[3+i], true));
158
159      // FIXME: PARAM TYS.
160      ResultTy = FunctionType::get(getTypeByID(Record[1], true), ArgTys,
161                                   Record[0]);
162      break;
163    }
164    case bitc::TYPE_CODE_STRUCT: {  // STRUCT: [ispacked, #elts, eltty x N]
165      if (Record.size() < 2 || Record.size() < Record[1]+2)
166        return Error("Invalid STRUCT type record");
167      std::vector<const Type*> EltTys;
168      for (unsigned i = 0, e = Record[1]; i != e; ++i)
169        EltTys.push_back(getTypeByID(Record[2+i], true));
170      ResultTy = StructType::get(EltTys, Record[0]);
171      break;
172    }
173    case bitc::TYPE_CODE_ARRAY:     // ARRAY: [numelts, eltty]
174      if (Record.size() < 2)
175        return Error("Invalid ARRAY type record");
176      ResultTy = ArrayType::get(getTypeByID(Record[1], true), Record[0]);
177      break;
178    case bitc::TYPE_CODE_VECTOR:    // VECTOR: [numelts, eltty]
179      if (Record.size() < 2)
180        return Error("Invalid VECTOR type record");
181      ResultTy = VectorType::get(getTypeByID(Record[1], true), Record[0]);
182      break;
183    }
184
185    if (NumRecords == TypeList.size()) {
186      // If this is a new type slot, just append it.
187      TypeList.push_back(ResultTy ? ResultTy : OpaqueType::get());
188      ++NumRecords;
189    } else if (ResultTy == 0) {
190      // Otherwise, this was forward referenced, so an opaque type was created,
191      // but the result type is actually just an opaque.  Leave the one we
192      // created previously.
193      ++NumRecords;
194    } else {
195      // Otherwise, this was forward referenced, so an opaque type was created.
196      // Resolve the opaque type to the real type now.
197      assert(NumRecords < TypeList.size() && "Typelist imbalance");
198      const OpaqueType *OldTy = cast<OpaqueType>(TypeList[NumRecords++].get());
199
200      // Don't directly push the new type on the Tab. Instead we want to replace
201      // the opaque type we previously inserted with the new concrete value. The
202      // refinement from the abstract (opaque) type to the new type causes all
203      // uses of the abstract type to use the concrete type (NewTy). This will
204      // also cause the opaque type to be deleted.
205      const_cast<OpaqueType*>(OldTy)->refineAbstractTypeTo(ResultTy);
206
207      // This should have replaced the old opaque type with the new type in the
208      // value table... or with a preexisting type that was already in the
209      // system.  Let's just make sure it did.
210      assert(TypeList[NumRecords-1].get() != OldTy &&
211             "refineAbstractType didn't work!");
212    }
213  }
214}
215
216
217bool BitcodeReader::ParseTypeSymbolTable(BitstreamReader &Stream) {
218  if (Stream.EnterSubBlock())
219    return Error("Malformed block record");
220
221  SmallVector<uint64_t, 64> Record;
222
223  // Read all the records for this type table.
224  std::string TypeName;
225  while (1) {
226    unsigned Code = Stream.ReadCode();
227    if (Code == bitc::END_BLOCK)
228      return Stream.ReadBlockEnd();
229
230    if (Code == bitc::ENTER_SUBBLOCK) {
231      // No known subblocks, always skip them.
232      Stream.ReadSubBlockID();
233      if (Stream.SkipBlock())
234        return Error("Malformed block record");
235      continue;
236    }
237
238    if (Code == bitc::DEFINE_ABBREV) {
239      Stream.ReadAbbrevRecord();
240      continue;
241    }
242
243    // Read a record.
244    Record.clear();
245    switch (Stream.ReadRecord(Code, Record)) {
246    default:  // Default behavior: unknown type.
247      break;
248    case bitc::TST_CODE_ENTRY:    // TST_ENTRY: [typeid, namelen, namechar x N]
249      if (ConvertToString(Record, 1, TypeName))
250        return Error("Invalid TST_ENTRY record");
251      unsigned TypeID = Record[0];
252      if (TypeID >= TypeList.size())
253        return Error("Invalid Type ID in TST_ENTRY record");
254
255      TheModule->addTypeName(TypeName, TypeList[TypeID].get());
256      TypeName.clear();
257      break;
258    }
259  }
260}
261
262bool BitcodeReader::ParseValueSymbolTable(BitstreamReader &Stream) {
263  if (Stream.EnterSubBlock())
264    return Error("Malformed block record");
265
266  SmallVector<uint64_t, 64> Record;
267
268  // Read all the records for this value table.
269  SmallString<128> ValueName;
270  while (1) {
271    unsigned Code = Stream.ReadCode();
272    if (Code == bitc::END_BLOCK)
273      return Stream.ReadBlockEnd();
274
275    if (Code == bitc::ENTER_SUBBLOCK) {
276      // No known subblocks, always skip them.
277      Stream.ReadSubBlockID();
278      if (Stream.SkipBlock())
279        return Error("Malformed block record");
280      continue;
281    }
282
283    if (Code == bitc::DEFINE_ABBREV) {
284      Stream.ReadAbbrevRecord();
285      continue;
286    }
287
288    // Read a record.
289    Record.clear();
290    switch (Stream.ReadRecord(Code, Record)) {
291    default:  // Default behavior: unknown type.
292      break;
293    case bitc::TST_CODE_ENTRY:    // VST_ENTRY: [valueid, namelen, namechar x N]
294      if (ConvertToString(Record, 1, ValueName))
295        return Error("Invalid TST_ENTRY record");
296      unsigned ValueID = Record[0];
297      if (ValueID >= ValueList.size())
298        return Error("Invalid Value ID in VST_ENTRY record");
299      Value *V = ValueList[ValueID];
300
301      V->setName(&ValueName[0], ValueName.size());
302      ValueName.clear();
303      break;
304    }
305  }
306}
307
308/// DecodeSignRotatedValue - Decode a signed value stored with the sign bit in
309/// the LSB for dense VBR encoding.
310static uint64_t DecodeSignRotatedValue(uint64_t V) {
311  if ((V & 1) == 0)
312    return V >> 1;
313  if (V != 1)
314    return -(V >> 1);
315  // There is no such thing as -0 with integers.  "-0" really means MININT.
316  return 1ULL << 63;
317}
318
319bool BitcodeReader::ParseConstants(BitstreamReader &Stream) {
320  if (Stream.EnterSubBlock())
321    return Error("Malformed block record");
322
323  SmallVector<uint64_t, 64> Record;
324
325  // Read all the records for this value table.
326  const Type *CurTy = Type::Int32Ty;
327  while (1) {
328    unsigned Code = Stream.ReadCode();
329    if (Code == bitc::END_BLOCK) {
330      // If there are global var inits to process, do so now.
331      if (!GlobalInits.empty()) {
332        while (!GlobalInits.empty()) {
333          unsigned ValID = GlobalInits.back().second;
334          if (ValID >= ValueList.size())
335            return Error("Invalid value ID for global var init!");
336          if (Constant *C = dyn_cast<Constant>(ValueList[ValID]))
337            GlobalInits.back().first->setInitializer(C);
338          else
339            return Error("Global variable initializer is not a constant!");
340          GlobalInits.pop_back();
341        }
342      }
343
344      return Stream.ReadBlockEnd();
345    }
346
347    if (Code == bitc::ENTER_SUBBLOCK) {
348      // No known subblocks, always skip them.
349      Stream.ReadSubBlockID();
350      if (Stream.SkipBlock())
351        return Error("Malformed block record");
352      continue;
353    }
354
355    if (Code == bitc::DEFINE_ABBREV) {
356      Stream.ReadAbbrevRecord();
357      continue;
358    }
359
360    // Read a record.
361    Record.clear();
362    Value *V = 0;
363    switch (Stream.ReadRecord(Code, Record)) {
364    default:  // Default behavior: unknown constant
365    case bitc::CST_CODE_UNDEF:     // UNDEF
366      V = UndefValue::get(CurTy);
367      break;
368    case bitc::CST_CODE_SETTYPE:   // SETTYPE: [typeid]
369      if (Record.empty())
370        return Error("Malformed CST_SETTYPE record");
371      if (Record[0] >= TypeList.size())
372        return Error("Invalid Type ID in CST_SETTYPE record");
373      CurTy = TypeList[Record[0]];
374      continue;  // Skip the ValueList manipulation.
375    case bitc::CST_CODE_NULL:      // NULL
376      V = Constant::getNullValue(CurTy);
377      break;
378    case bitc::CST_CODE_INTEGER:   // INTEGER: [intval]
379      if (!isa<IntegerType>(CurTy) || Record.empty())
380        return Error("Invalid CST_INTEGER record");
381      V = ConstantInt::get(CurTy, DecodeSignRotatedValue(Record[0]));
382      break;
383    case bitc::CST_CODE_WIDE_INTEGER: {// WIDE_INTEGER: [n, n x intval]
384      if (!isa<IntegerType>(CurTy) || Record.empty() ||
385          Record.size() < Record[0]+1)
386        return Error("Invalid WIDE_INTEGER record");
387
388      unsigned NumWords = Record[0];
389      uint64_t *Data = new uint64_t[NumWords];
390      for (unsigned i = 0; i != NumWords; ++i)
391        Data[i] = DecodeSignRotatedValue(Record[i+1]);
392      V = ConstantInt::get(APInt(cast<IntegerType>(CurTy)->getBitWidth(),
393                                 NumWords, Data));
394      break;
395    }
396    case bitc::CST_CODE_FLOAT:     // FLOAT: [fpval]
397      if (Record.empty())
398        return Error("Invalid FLOAT record");
399      if (CurTy == Type::FloatTy)
400        V = ConstantFP::get(CurTy, BitsToFloat(Record[0]));
401      else if (CurTy == Type::DoubleTy)
402        V = ConstantFP::get(CurTy, BitsToDouble(Record[0]));
403      else
404        V = UndefValue::get(CurTy);
405      break;
406    }
407
408    ValueList.push_back(V);
409  }
410}
411
412bool BitcodeReader::ParseModule(BitstreamReader &Stream,
413                                const std::string &ModuleID) {
414  // Reject multiple MODULE_BLOCK's in a single bitstream.
415  if (TheModule)
416    return Error("Multiple MODULE_BLOCKs in same stream");
417
418  if (Stream.EnterSubBlock())
419    return Error("Malformed block record");
420
421  // Otherwise, create the module.
422  TheModule = new Module(ModuleID);
423
424  SmallVector<uint64_t, 64> Record;
425  std::vector<std::string> SectionTable;
426
427  // Read all the records for this module.
428  while (!Stream.AtEndOfStream()) {
429    unsigned Code = Stream.ReadCode();
430    if (Code == bitc::END_BLOCK) {
431      if (!GlobalInits.empty())
432        return Error("Malformed global initializer set");
433      return Stream.ReadBlockEnd();
434    }
435
436    if (Code == bitc::ENTER_SUBBLOCK) {
437      switch (Stream.ReadSubBlockID()) {
438      default:  // Skip unknown content.
439        if (Stream.SkipBlock())
440          return Error("Malformed block record");
441        break;
442      case bitc::TYPE_BLOCK_ID:
443        if (ParseTypeTable(Stream))
444          return true;
445        break;
446      case bitc::TYPE_SYMTAB_BLOCK_ID:
447        if (ParseTypeSymbolTable(Stream))
448          return true;
449        break;
450      case bitc::VALUE_SYMTAB_BLOCK_ID:
451        if (ParseValueSymbolTable(Stream))
452          return true;
453        break;
454      case bitc::CONSTANTS_BLOCK_ID:
455        if (ParseConstants(Stream))
456          return true;
457        break;
458      }
459      continue;
460    }
461
462    if (Code == bitc::DEFINE_ABBREV) {
463      Stream.ReadAbbrevRecord();
464      continue;
465    }
466
467    // Read a record.
468    switch (Stream.ReadRecord(Code, Record)) {
469    default: break;  // Default behavior, ignore unknown content.
470    case bitc::MODULE_CODE_VERSION:  // VERSION: [version#]
471      if (Record.size() < 1)
472        return Error("Malformed MODULE_CODE_VERSION");
473      // Only version #0 is supported so far.
474      if (Record[0] != 0)
475        return Error("Unknown bitstream version!");
476      break;
477    case bitc::MODULE_CODE_TRIPLE: {  // TRIPLE: [strlen, strchr x N]
478      std::string S;
479      if (ConvertToString(Record, 0, S))
480        return Error("Invalid MODULE_CODE_TRIPLE record");
481      TheModule->setTargetTriple(S);
482      break;
483    }
484    case bitc::MODULE_CODE_DATALAYOUT: {  // DATALAYOUT: [strlen, strchr x N]
485      std::string S;
486      if (ConvertToString(Record, 0, S))
487        return Error("Invalid MODULE_CODE_DATALAYOUT record");
488      TheModule->setDataLayout(S);
489      break;
490    }
491    case bitc::MODULE_CODE_ASM: {  // ASM: [strlen, strchr x N]
492      std::string S;
493      if (ConvertToString(Record, 0, S))
494        return Error("Invalid MODULE_CODE_ASM record");
495      TheModule->setModuleInlineAsm(S);
496      break;
497    }
498    case bitc::MODULE_CODE_DEPLIB: {  // DEPLIB: [strlen, strchr x N]
499      std::string S;
500      if (ConvertToString(Record, 0, S))
501        return Error("Invalid MODULE_CODE_DEPLIB record");
502      TheModule->addLibrary(S);
503      break;
504    }
505    case bitc::MODULE_CODE_SECTIONNAME: {  // SECTIONNAME: [strlen, strchr x N]
506      std::string S;
507      if (ConvertToString(Record, 0, S))
508        return Error("Invalid MODULE_CODE_SECTIONNAME record");
509      SectionTable.push_back(S);
510      break;
511    }
512    // GLOBALVAR: [type, isconst, initid,
513    //             linkage, alignment, section, visibility, threadlocal]
514    case bitc::MODULE_CODE_GLOBALVAR: {
515      if (Record.size() < 6)
516        return Error("Invalid MODULE_CODE_GLOBALVAR record");
517      const Type *Ty = getTypeByID(Record[0]);
518      if (!isa<PointerType>(Ty))
519        return Error("Global not a pointer type!");
520      Ty = cast<PointerType>(Ty)->getElementType();
521
522      bool isConstant = Record[1];
523      GlobalValue::LinkageTypes Linkage = GetDecodedLinkage(Record[3]);
524      unsigned Alignment = (1 << Record[4]) >> 1;
525      std::string Section;
526      if (Record[5]) {
527        if (Record[5]-1 >= SectionTable.size())
528          return Error("Invalid section ID");
529        Section = SectionTable[Record[5]-1];
530      }
531      GlobalValue::VisibilityTypes Visibility = GlobalValue::DefaultVisibility;
532      if (Record.size() >= 6) Visibility = GetDecodedVisibility(Record[6]);
533      bool isThreadLocal = false;
534      if (Record.size() >= 7) isThreadLocal = Record[7];
535
536      GlobalVariable *NewGV =
537        new GlobalVariable(Ty, isConstant, Linkage, 0, "", TheModule);
538      NewGV->setAlignment(Alignment);
539      if (!Section.empty())
540        NewGV->setSection(Section);
541      NewGV->setVisibility(Visibility);
542      NewGV->setThreadLocal(isThreadLocal);
543
544      ValueList.push_back(NewGV);
545
546      // Remember which value to use for the global initializer.
547      if (unsigned InitID = Record[2])
548        GlobalInits.push_back(std::make_pair(NewGV, InitID-1));
549      break;
550    }
551    // FUNCTION:  [type, callingconv, isproto, linkage, alignment, section,
552    //             visibility]
553    case bitc::MODULE_CODE_FUNCTION: {
554      if (Record.size() < 7)
555        return Error("Invalid MODULE_CODE_FUNCTION record");
556      const Type *Ty = getTypeByID(Record[0]);
557      if (!isa<PointerType>(Ty))
558        return Error("Function not a pointer type!");
559      const FunctionType *FTy =
560        dyn_cast<FunctionType>(cast<PointerType>(Ty)->getElementType());
561      if (!FTy)
562        return Error("Function not a pointer to function type!");
563
564      Function *Func = new Function(FTy, GlobalValue::ExternalLinkage,
565                                    "", TheModule);
566
567      Func->setCallingConv(Record[1]);
568      Func->setLinkage(GetDecodedLinkage(Record[3]));
569      Func->setAlignment((1 << Record[4]) >> 1);
570      if (Record[5]) {
571        if (Record[5]-1 >= SectionTable.size())
572          return Error("Invalid section ID");
573        Func->setSection(SectionTable[Record[5]-1]);
574      }
575      Func->setVisibility(GetDecodedVisibility(Record[6]));
576
577      ValueList.push_back(Func);
578      // TODO: remember initializer/global pair for later substitution.
579      break;
580    }
581    }
582    Record.clear();
583  }
584
585  return Error("Premature end of bitstream");
586}
587
588
589bool BitcodeReader::ParseBitcode(unsigned char *Buf, unsigned Length,
590                                 const std::string &ModuleID) {
591  TheModule = 0;
592
593  if (Length & 3)
594    return Error("Bitcode stream should be a multiple of 4 bytes in length");
595
596  BitstreamReader Stream(Buf, Buf+Length);
597
598  // Sniff for the signature.
599  if (Stream.Read(8) != 'B' ||
600      Stream.Read(8) != 'C' ||
601      Stream.Read(4) != 0x0 ||
602      Stream.Read(4) != 0xC ||
603      Stream.Read(4) != 0xE ||
604      Stream.Read(4) != 0xD)
605    return Error("Invalid bitcode signature");
606
607  // We expect a number of well-defined blocks, though we don't necessarily
608  // need to understand them all.
609  while (!Stream.AtEndOfStream()) {
610    unsigned Code = Stream.ReadCode();
611
612    if (Code != bitc::ENTER_SUBBLOCK)
613      return Error("Invalid record at top-level");
614
615    unsigned BlockID = Stream.ReadSubBlockID();
616
617    // We only know the MODULE subblock ID.
618    if (BlockID == bitc::MODULE_BLOCK_ID) {
619      if (ParseModule(Stream, ModuleID))
620        return true;
621    } else if (Stream.SkipBlock()) {
622      return Error("Malformed block record");
623    }
624  }
625
626  return false;
627}
628