318b2368cd9afbbf34c0246d3380ab79e055d36f
[oota-llvm.git] / lib / Bitcode / Reader / BitcodeReader.cpp
1 //===- BitcodeReader.cpp - Internal BitcodeReader implementation ----------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #include "llvm/Bitcode/ReaderWriter.h"
11 #include "llvm/ADT/STLExtras.h"
12 #include "llvm/ADT/SmallString.h"
13 #include "llvm/ADT/SmallVector.h"
14 #include "llvm/ADT/Triple.h"
15 #include "llvm/Bitcode/BitstreamReader.h"
16 #include "llvm/Bitcode/LLVMBitCodes.h"
17 #include "llvm/IR/AutoUpgrade.h"
18 #include "llvm/IR/Constants.h"
19 #include "llvm/IR/DebugInfo.h"
20 #include "llvm/IR/DebugInfoMetadata.h"
21 #include "llvm/IR/DerivedTypes.h"
22 #include "llvm/IR/DiagnosticPrinter.h"
23 #include "llvm/IR/GVMaterializer.h"
24 #include "llvm/IR/InlineAsm.h"
25 #include "llvm/IR/IntrinsicInst.h"
26 #include "llvm/IR/LLVMContext.h"
27 #include "llvm/IR/Module.h"
28 #include "llvm/IR/OperandTraits.h"
29 #include "llvm/IR/Operator.h"
30 #include "llvm/IR/FunctionInfo.h"
31 #include "llvm/IR/ValueHandle.h"
32 #include "llvm/Support/DataStream.h"
33 #include "llvm/Support/ManagedStatic.h"
34 #include "llvm/Support/MathExtras.h"
35 #include "llvm/Support/MemoryBuffer.h"
36 #include "llvm/Support/raw_ostream.h"
37 #include <deque>
38 using namespace llvm;
39
40 namespace {
41 enum {
42   SWITCH_INST_MAGIC = 0x4B5 // May 2012 => 1205 => Hex
43 };
44
45 /// Indicates which operator an operand allows (for the few operands that may
46 /// only reference a certain operator).
47 enum OperatorConstraint {
48   OC_None = 0,  // No constraint
49   OC_CatchPad,  // Must be CatchPadInst
50   OC_CleanupPad // Must be CleanupPadInst
51 };
52
53 class BitcodeReaderValueList {
54   std::vector<WeakVH> ValuePtrs;
55
56   /// As we resolve forward-referenced constants, we add information about them
57   /// to this vector.  This allows us to resolve them in bulk instead of
58   /// resolving each reference at a time.  See the code in
59   /// ResolveConstantForwardRefs for more information about this.
60   ///
61   /// The key of this vector is the placeholder constant, the value is the slot
62   /// number that holds the resolved value.
63   typedef std::vector<std::pair<Constant*, unsigned> > ResolveConstantsTy;
64   ResolveConstantsTy ResolveConstants;
65   LLVMContext &Context;
66 public:
67   BitcodeReaderValueList(LLVMContext &C) : Context(C) {}
68   ~BitcodeReaderValueList() {
69     assert(ResolveConstants.empty() && "Constants not resolved?");
70   }
71
72   // vector compatibility methods
73   unsigned size() const { return ValuePtrs.size(); }
74   void resize(unsigned N) { ValuePtrs.resize(N); }
75   void push_back(Value *V) { ValuePtrs.emplace_back(V); }
76
77   void clear() {
78     assert(ResolveConstants.empty() && "Constants not resolved?");
79     ValuePtrs.clear();
80   }
81
82   Value *operator[](unsigned i) const {
83     assert(i < ValuePtrs.size());
84     return ValuePtrs[i];
85   }
86
87   Value *back() const { return ValuePtrs.back(); }
88     void pop_back() { ValuePtrs.pop_back(); }
89   bool empty() const { return ValuePtrs.empty(); }
90   void shrinkTo(unsigned N) {
91     assert(N <= size() && "Invalid shrinkTo request!");
92     ValuePtrs.resize(N);
93   }
94
95   Constant *getConstantFwdRef(unsigned Idx, Type *Ty);
96   Value *getValueFwdRef(unsigned Idx, Type *Ty,
97                         OperatorConstraint OC = OC_None);
98
99   bool assignValue(Value *V, unsigned Idx);
100
101   /// Once all constants are read, this method bulk resolves any forward
102   /// references.
103   void resolveConstantForwardRefs();
104 };
105
106 class BitcodeReaderMDValueList {
107   unsigned NumFwdRefs;
108   bool AnyFwdRefs;
109   unsigned MinFwdRef;
110   unsigned MaxFwdRef;
111   std::vector<TrackingMDRef> MDValuePtrs;
112
113   LLVMContext &Context;
114 public:
115   BitcodeReaderMDValueList(LLVMContext &C)
116       : NumFwdRefs(0), AnyFwdRefs(false), Context(C) {}
117
118   // vector compatibility methods
119   unsigned size() const       { return MDValuePtrs.size(); }
120   void resize(unsigned N)     { MDValuePtrs.resize(N); }
121   void push_back(Metadata *MD) { MDValuePtrs.emplace_back(MD); }
122   void clear()                { MDValuePtrs.clear();  }
123   Metadata *back() const      { return MDValuePtrs.back(); }
124   void pop_back()             { MDValuePtrs.pop_back(); }
125   bool empty() const          { return MDValuePtrs.empty(); }
126
127   Metadata *operator[](unsigned i) const {
128     assert(i < MDValuePtrs.size());
129     return MDValuePtrs[i];
130   }
131
132   void shrinkTo(unsigned N) {
133     assert(N <= size() && "Invalid shrinkTo request!");
134     MDValuePtrs.resize(N);
135   }
136
137   Metadata *getValueFwdRef(unsigned Idx);
138   void assignValue(Metadata *MD, unsigned Idx);
139   void tryToResolveCycles();
140 };
141
142 class BitcodeReader : public GVMaterializer {
143   LLVMContext &Context;
144   DiagnosticHandlerFunction DiagnosticHandler;
145   Module *TheModule = nullptr;
146   std::unique_ptr<MemoryBuffer> Buffer;
147   std::unique_ptr<BitstreamReader> StreamFile;
148   BitstreamCursor Stream;
149   // Next offset to start scanning for lazy parsing of function bodies.
150   uint64_t NextUnreadBit = 0;
151   // Last function offset found in the VST.
152   uint64_t LastFunctionBlockBit = 0;
153   bool SeenValueSymbolTable = false;
154   unsigned VSTOffset = 0;
155   // Contains an arbitrary and optional string identifying the bitcode producer
156   std::string ProducerIdentification;
157
158   std::vector<Type*> TypeList;
159   BitcodeReaderValueList ValueList;
160   BitcodeReaderMDValueList MDValueList;
161   std::vector<Comdat *> ComdatList;
162   SmallVector<Instruction *, 64> InstructionList;
163
164   std::vector<std::pair<GlobalVariable*, unsigned> > GlobalInits;
165   std::vector<std::pair<GlobalAlias*, unsigned> > AliasInits;
166   std::vector<std::pair<Function*, unsigned> > FunctionPrefixes;
167   std::vector<std::pair<Function*, unsigned> > FunctionPrologues;
168   std::vector<std::pair<Function*, unsigned> > FunctionPersonalityFns;
169
170   SmallVector<Instruction*, 64> InstsWithTBAATag;
171
172   /// The set of attributes by index.  Index zero in the file is for null, and
173   /// is thus not represented here.  As such all indices are off by one.
174   std::vector<AttributeSet> MAttributes;
175
176   /// The set of attribute groups.
177   std::map<unsigned, AttributeSet> MAttributeGroups;
178
179   /// While parsing a function body, this is a list of the basic blocks for the
180   /// function.
181   std::vector<BasicBlock*> FunctionBBs;
182
183   // When reading the module header, this list is populated with functions that
184   // have bodies later in the file.
185   std::vector<Function*> FunctionsWithBodies;
186
187   // When intrinsic functions are encountered which require upgrading they are
188   // stored here with their replacement function.
189   typedef DenseMap<Function*, Function*> UpgradedIntrinsicMap;
190   UpgradedIntrinsicMap UpgradedIntrinsics;
191
192   // Map the bitcode's custom MDKind ID to the Module's MDKind ID.
193   DenseMap<unsigned, unsigned> MDKindMap;
194
195   // Several operations happen after the module header has been read, but
196   // before function bodies are processed. This keeps track of whether
197   // we've done this yet.
198   bool SeenFirstFunctionBody = false;
199
200   /// When function bodies are initially scanned, this map contains info about
201   /// where to find deferred function body in the stream.
202   DenseMap<Function*, uint64_t> DeferredFunctionInfo;
203
204   /// When Metadata block is initially scanned when parsing the module, we may
205   /// choose to defer parsing of the metadata. This vector contains info about
206   /// which Metadata blocks are deferred.
207   std::vector<uint64_t> DeferredMetadataInfo;
208
209   /// These are basic blocks forward-referenced by block addresses.  They are
210   /// inserted lazily into functions when they're loaded.  The basic block ID is
211   /// its index into the vector.
212   DenseMap<Function *, std::vector<BasicBlock *>> BasicBlockFwdRefs;
213   std::deque<Function *> BasicBlockFwdRefQueue;
214
215   /// Indicates that we are using a new encoding for instruction operands where
216   /// most operands in the current FUNCTION_BLOCK are encoded relative to the
217   /// instruction number, for a more compact encoding.  Some instruction
218   /// operands are not relative to the instruction ID: basic block numbers, and
219   /// types. Once the old style function blocks have been phased out, we would
220   /// not need this flag.
221   bool UseRelativeIDs = false;
222
223   /// True if all functions will be materialized, negating the need to process
224   /// (e.g.) blockaddress forward references.
225   bool WillMaterializeAllForwardRefs = false;
226
227   /// Functions that have block addresses taken.  This is usually empty.
228   SmallPtrSet<const Function *, 4> BlockAddressesTaken;
229
230   /// True if any Metadata block has been materialized.
231   bool IsMetadataMaterialized = false;
232
233   bool StripDebugInfo = false;
234
235   std::vector<std::string> BundleTags;
236
237 public:
238   std::error_code error(BitcodeError E, const Twine &Message);
239   std::error_code error(BitcodeError E);
240   std::error_code error(const Twine &Message);
241
242   BitcodeReader(MemoryBuffer *Buffer, LLVMContext &Context,
243                 DiagnosticHandlerFunction DiagnosticHandler);
244   BitcodeReader(LLVMContext &Context,
245                 DiagnosticHandlerFunction DiagnosticHandler);
246   ~BitcodeReader() override { freeState(); }
247
248   std::error_code materializeForwardReferencedFunctions();
249
250   void freeState();
251
252   void releaseBuffer();
253
254   bool isDematerializable(const GlobalValue *GV) const override;
255   std::error_code materialize(GlobalValue *GV) override;
256   std::error_code materializeModule(Module *M) override;
257   std::vector<StructType *> getIdentifiedStructTypes() const override;
258   void dematerialize(GlobalValue *GV) override;
259
260   /// \brief Main interface to parsing a bitcode buffer.
261   /// \returns true if an error occurred.
262   std::error_code parseBitcodeInto(std::unique_ptr<DataStreamer> Streamer,
263                                    Module *M,
264                                    bool ShouldLazyLoadMetadata = false);
265
266   /// \brief Cheap mechanism to just extract module triple
267   /// \returns true if an error occurred.
268   ErrorOr<std::string> parseTriple();
269
270   static uint64_t decodeSignRotatedValue(uint64_t V);
271
272   /// Materialize any deferred Metadata block.
273   std::error_code materializeMetadata() override;
274
275   void setStripDebugInfo() override;
276
277 private:
278   /// Parse the "IDENTIFICATION_BLOCK_ID" block, populate the
279   // ProducerIdentification data member, and do some basic enforcement on the
280   // "epoch" encoded in the bitcode.
281   std::error_code parseBitcodeVersion();
282
283   std::vector<StructType *> IdentifiedStructTypes;
284   StructType *createIdentifiedStructType(LLVMContext &Context, StringRef Name);
285   StructType *createIdentifiedStructType(LLVMContext &Context);
286
287   Type *getTypeByID(unsigned ID);
288   Value *getFnValueByID(unsigned ID, Type *Ty,
289                         OperatorConstraint OC = OC_None) {
290     if (Ty && Ty->isMetadataTy())
291       return MetadataAsValue::get(Ty->getContext(), getFnMetadataByID(ID));
292     return ValueList.getValueFwdRef(ID, Ty, OC);
293   }
294   Metadata *getFnMetadataByID(unsigned ID) {
295     return MDValueList.getValueFwdRef(ID);
296   }
297   BasicBlock *getBasicBlock(unsigned ID) const {
298     if (ID >= FunctionBBs.size()) return nullptr; // Invalid ID
299     return FunctionBBs[ID];
300   }
301   AttributeSet getAttributes(unsigned i) const {
302     if (i-1 < MAttributes.size())
303       return MAttributes[i-1];
304     return AttributeSet();
305   }
306
307   /// Read a value/type pair out of the specified record from slot 'Slot'.
308   /// Increment Slot past the number of slots used in the record. Return true on
309   /// failure.
310   bool getValueTypePair(SmallVectorImpl<uint64_t> &Record, unsigned &Slot,
311                         unsigned InstNum, Value *&ResVal) {
312     if (Slot == Record.size()) return true;
313     unsigned ValNo = (unsigned)Record[Slot++];
314     // Adjust the ValNo, if it was encoded relative to the InstNum.
315     if (UseRelativeIDs)
316       ValNo = InstNum - ValNo;
317     if (ValNo < InstNum) {
318       // If this is not a forward reference, just return the value we already
319       // have.
320       ResVal = getFnValueByID(ValNo, nullptr);
321       return ResVal == nullptr;
322     }
323     if (Slot == Record.size())
324       return true;
325
326     unsigned TypeNo = (unsigned)Record[Slot++];
327     ResVal = getFnValueByID(ValNo, getTypeByID(TypeNo));
328     return ResVal == nullptr;
329   }
330
331   /// Read a value out of the specified record from slot 'Slot'. Increment Slot
332   /// past the number of slots used by the value in the record. Return true if
333   /// there is an error.
334   bool popValue(SmallVectorImpl<uint64_t> &Record, unsigned &Slot,
335                 unsigned InstNum, Type *Ty, Value *&ResVal,
336                 OperatorConstraint OC = OC_None) {
337     if (getValue(Record, Slot, InstNum, Ty, ResVal, OC))
338       return true;
339     // All values currently take a single record slot.
340     ++Slot;
341     return false;
342   }
343
344   /// Like popValue, but does not increment the Slot number.
345   bool getValue(SmallVectorImpl<uint64_t> &Record, unsigned Slot,
346                 unsigned InstNum, Type *Ty, Value *&ResVal,
347                 OperatorConstraint OC = OC_None) {
348     ResVal = getValue(Record, Slot, InstNum, Ty, OC);
349     return ResVal == nullptr;
350   }
351
352   /// Version of getValue that returns ResVal directly, or 0 if there is an
353   /// error.
354   Value *getValue(SmallVectorImpl<uint64_t> &Record, unsigned Slot,
355                   unsigned InstNum, Type *Ty, OperatorConstraint OC = OC_None) {
356     if (Slot == Record.size()) return nullptr;
357     unsigned ValNo = (unsigned)Record[Slot];
358     // Adjust the ValNo, if it was encoded relative to the InstNum.
359     if (UseRelativeIDs)
360       ValNo = InstNum - ValNo;
361     return getFnValueByID(ValNo, Ty, OC);
362   }
363
364   /// Like getValue, but decodes signed VBRs.
365   Value *getValueSigned(SmallVectorImpl<uint64_t> &Record, unsigned Slot,
366                         unsigned InstNum, Type *Ty,
367                         OperatorConstraint OC = OC_None) {
368     if (Slot == Record.size()) return nullptr;
369     unsigned ValNo = (unsigned)decodeSignRotatedValue(Record[Slot]);
370     // Adjust the ValNo, if it was encoded relative to the InstNum.
371     if (UseRelativeIDs)
372       ValNo = InstNum - ValNo;
373     return getFnValueByID(ValNo, Ty, OC);
374   }
375
376   /// Converts alignment exponent (i.e. power of two (or zero)) to the
377   /// corresponding alignment to use. If alignment is too large, returns
378   /// a corresponding error code.
379   std::error_code parseAlignmentValue(uint64_t Exponent, unsigned &Alignment);
380   std::error_code parseAttrKind(uint64_t Code, Attribute::AttrKind *Kind);
381   std::error_code parseModule(uint64_t ResumeBit,
382                               bool ShouldLazyLoadMetadata = false);
383   std::error_code parseAttributeBlock();
384   std::error_code parseAttributeGroupBlock();
385   std::error_code parseTypeTable();
386   std::error_code parseTypeTableBody();
387   std::error_code parseOperandBundleTags();
388
389   ErrorOr<Value *> recordValue(SmallVectorImpl<uint64_t> &Record,
390                                unsigned NameIndex, Triple &TT);
391   std::error_code parseValueSymbolTable(unsigned Offset = 0);
392   std::error_code parseConstants();
393   std::error_code rememberAndSkipFunctionBodies();
394   std::error_code rememberAndSkipFunctionBody();
395   /// Save the positions of the Metadata blocks and skip parsing the blocks.
396   std::error_code rememberAndSkipMetadata();
397   std::error_code parseFunctionBody(Function *F);
398   std::error_code globalCleanup();
399   std::error_code resolveGlobalAndAliasInits();
400   std::error_code parseMetadata();
401   std::error_code parseMetadataAttachment(Function &F);
402   ErrorOr<std::string> parseModuleTriple();
403   std::error_code parseUseLists();
404   std::error_code initStream(std::unique_ptr<DataStreamer> Streamer);
405   std::error_code initStreamFromBuffer();
406   std::error_code initLazyStream(std::unique_ptr<DataStreamer> Streamer);
407   std::error_code findFunctionInStream(
408       Function *F,
409       DenseMap<Function *, uint64_t>::iterator DeferredFunctionInfoIterator);
410 };
411
412 /// Class to manage reading and parsing function summary index bitcode
413 /// files/sections.
414 class FunctionIndexBitcodeReader {
415   DiagnosticHandlerFunction DiagnosticHandler;
416
417   /// Eventually points to the function index built during parsing.
418   FunctionInfoIndex *TheIndex = nullptr;
419
420   std::unique_ptr<MemoryBuffer> Buffer;
421   std::unique_ptr<BitstreamReader> StreamFile;
422   BitstreamCursor Stream;
423
424   /// \brief Used to indicate whether we are doing lazy parsing of summary data.
425   ///
426   /// If false, the summary section is fully parsed into the index during
427   /// the initial parse. Otherwise, if true, the caller is expected to
428   /// invoke \a readFunctionSummary for each summary needed, and the summary
429   /// section is thus parsed lazily.
430   bool IsLazy = false;
431
432   /// Used to indicate whether caller only wants to check for the presence
433   /// of the function summary bitcode section. All blocks are skipped,
434   /// but the SeenFuncSummary boolean is set.
435   bool CheckFuncSummaryPresenceOnly = false;
436
437   /// Indicates whether we have encountered a function summary section
438   /// yet during parsing, used when checking if file contains function
439   /// summary section.
440   bool SeenFuncSummary = false;
441
442   /// \brief Map populated during function summary section parsing, and
443   /// consumed during ValueSymbolTable parsing.
444   ///
445   /// Used to correlate summary records with VST entries. For the per-module
446   /// index this maps the ValueID to the parsed function summary, and
447   /// for the combined index this maps the summary record's bitcode
448   /// offset to the function summary (since in the combined index the
449   /// VST records do not hold value IDs but rather hold the function
450   /// summary record offset).
451   DenseMap<uint64_t, std::unique_ptr<FunctionSummary>> SummaryMap;
452
453   /// Map populated during module path string table parsing, from the
454   /// module ID to a string reference owned by the index's module
455   /// path string table, used to correlate with combined index function
456   /// summary records.
457   DenseMap<uint64_t, StringRef> ModuleIdMap;
458
459  public:
460   std::error_code error(BitcodeError E, const Twine &Message);
461   std::error_code error(BitcodeError E);
462   std::error_code error(const Twine &Message);
463
464   FunctionIndexBitcodeReader(MemoryBuffer *Buffer, LLVMContext &Context,
465                              DiagnosticHandlerFunction DiagnosticHandler,
466                              bool IsLazy = false,
467                              bool CheckFuncSummaryPresenceOnly = false);
468   FunctionIndexBitcodeReader(LLVMContext &Context,
469                              DiagnosticHandlerFunction DiagnosticHandler,
470                              bool IsLazy = false,
471                              bool CheckFuncSummaryPresenceOnly = false);
472   ~FunctionIndexBitcodeReader() { freeState(); }
473
474   void freeState();
475
476   void releaseBuffer();
477
478   /// Check if the parser has encountered a function summary section.
479   bool foundFuncSummary() { return SeenFuncSummary; }
480
481   /// \brief Main interface to parsing a bitcode buffer.
482   /// \returns true if an error occurred.
483   std::error_code parseSummaryIndexInto(std::unique_ptr<DataStreamer> Streamer,
484                                         FunctionInfoIndex *I);
485
486   /// \brief Interface for parsing a function summary lazily.
487   std::error_code parseFunctionSummary(std::unique_ptr<DataStreamer> Streamer,
488                                        FunctionInfoIndex *I,
489                                        size_t FunctionSummaryOffset);
490
491  private:
492   std::error_code parseModule();
493   std::error_code parseValueSymbolTable();
494   std::error_code parseEntireSummary();
495   std::error_code parseModuleStringTable();
496   std::error_code initStream(std::unique_ptr<DataStreamer> Streamer);
497   std::error_code initStreamFromBuffer();
498   std::error_code initLazyStream(std::unique_ptr<DataStreamer> Streamer);
499 };
500 } // namespace
501
502 BitcodeDiagnosticInfo::BitcodeDiagnosticInfo(std::error_code EC,
503                                              DiagnosticSeverity Severity,
504                                              const Twine &Msg)
505     : DiagnosticInfo(DK_Bitcode, Severity), Msg(Msg), EC(EC) {}
506
507 void BitcodeDiagnosticInfo::print(DiagnosticPrinter &DP) const { DP << Msg; }
508
509 static std::error_code error(DiagnosticHandlerFunction DiagnosticHandler,
510                              std::error_code EC, const Twine &Message) {
511   BitcodeDiagnosticInfo DI(EC, DS_Error, Message);
512   DiagnosticHandler(DI);
513   return EC;
514 }
515
516 static std::error_code error(DiagnosticHandlerFunction DiagnosticHandler,
517                              std::error_code EC) {
518   return error(DiagnosticHandler, EC, EC.message());
519 }
520
521 static std::error_code error(DiagnosticHandlerFunction DiagnosticHandler,
522                              const Twine &Message) {
523   return error(DiagnosticHandler,
524                make_error_code(BitcodeError::CorruptedBitcode), Message);
525 }
526
527 std::error_code BitcodeReader::error(BitcodeError E, const Twine &Message) {
528   if (!ProducerIdentification.empty()) {
529     Twine MsgWithID = Message + " (Producer: '" + ProducerIdentification +
530                       "' Reader: 'LLVM " + LLVM_VERSION_STRING "')";
531     return ::error(DiagnosticHandler, make_error_code(E), MsgWithID);
532   }
533   return ::error(DiagnosticHandler, make_error_code(E), Message);
534 }
535
536 std::error_code BitcodeReader::error(const Twine &Message) {
537   if (!ProducerIdentification.empty()) {
538     Twine MsgWithID = Message + " (Producer: '" + ProducerIdentification +
539                       "' Reader: 'LLVM " + LLVM_VERSION_STRING "')";
540     return ::error(DiagnosticHandler,
541                    make_error_code(BitcodeError::CorruptedBitcode), MsgWithID);
542   }
543   return ::error(DiagnosticHandler,
544                  make_error_code(BitcodeError::CorruptedBitcode), Message);
545 }
546
547 std::error_code BitcodeReader::error(BitcodeError E) {
548   return ::error(DiagnosticHandler, make_error_code(E));
549 }
550
551 static DiagnosticHandlerFunction getDiagHandler(DiagnosticHandlerFunction F,
552                                                 LLVMContext &C) {
553   if (F)
554     return F;
555   return [&C](const DiagnosticInfo &DI) { C.diagnose(DI); };
556 }
557
558 BitcodeReader::BitcodeReader(MemoryBuffer *Buffer, LLVMContext &Context,
559                              DiagnosticHandlerFunction DiagnosticHandler)
560     : Context(Context),
561       DiagnosticHandler(getDiagHandler(DiagnosticHandler, Context)),
562       Buffer(Buffer), ValueList(Context), MDValueList(Context) {}
563
564 BitcodeReader::BitcodeReader(LLVMContext &Context,
565                              DiagnosticHandlerFunction DiagnosticHandler)
566     : Context(Context),
567       DiagnosticHandler(getDiagHandler(DiagnosticHandler, Context)),
568       Buffer(nullptr), ValueList(Context), MDValueList(Context) {}
569
570 std::error_code BitcodeReader::materializeForwardReferencedFunctions() {
571   if (WillMaterializeAllForwardRefs)
572     return std::error_code();
573
574   // Prevent recursion.
575   WillMaterializeAllForwardRefs = true;
576
577   while (!BasicBlockFwdRefQueue.empty()) {
578     Function *F = BasicBlockFwdRefQueue.front();
579     BasicBlockFwdRefQueue.pop_front();
580     assert(F && "Expected valid function");
581     if (!BasicBlockFwdRefs.count(F))
582       // Already materialized.
583       continue;
584
585     // Check for a function that isn't materializable to prevent an infinite
586     // loop.  When parsing a blockaddress stored in a global variable, there
587     // isn't a trivial way to check if a function will have a body without a
588     // linear search through FunctionsWithBodies, so just check it here.
589     if (!F->isMaterializable())
590       return error("Never resolved function from blockaddress");
591
592     // Try to materialize F.
593     if (std::error_code EC = materialize(F))
594       return EC;
595   }
596   assert(BasicBlockFwdRefs.empty() && "Function missing from queue");
597
598   // Reset state.
599   WillMaterializeAllForwardRefs = false;
600   return std::error_code();
601 }
602
603 void BitcodeReader::freeState() {
604   Buffer = nullptr;
605   std::vector<Type*>().swap(TypeList);
606   ValueList.clear();
607   MDValueList.clear();
608   std::vector<Comdat *>().swap(ComdatList);
609
610   std::vector<AttributeSet>().swap(MAttributes);
611   std::vector<BasicBlock*>().swap(FunctionBBs);
612   std::vector<Function*>().swap(FunctionsWithBodies);
613   DeferredFunctionInfo.clear();
614   DeferredMetadataInfo.clear();
615   MDKindMap.clear();
616
617   assert(BasicBlockFwdRefs.empty() && "Unresolved blockaddress fwd references");
618   BasicBlockFwdRefQueue.clear();
619 }
620
621 //===----------------------------------------------------------------------===//
622 //  Helper functions to implement forward reference resolution, etc.
623 //===----------------------------------------------------------------------===//
624
625 /// Convert a string from a record into an std::string, return true on failure.
626 template <typename StrTy>
627 static bool convertToString(ArrayRef<uint64_t> Record, unsigned Idx,
628                             StrTy &Result) {
629   if (Idx > Record.size())
630     return true;
631
632   for (unsigned i = Idx, e = Record.size(); i != e; ++i)
633     Result += (char)Record[i];
634   return false;
635 }
636
637 static bool hasImplicitComdat(size_t Val) {
638   switch (Val) {
639   default:
640     return false;
641   case 1:  // Old WeakAnyLinkage
642   case 4:  // Old LinkOnceAnyLinkage
643   case 10: // Old WeakODRLinkage
644   case 11: // Old LinkOnceODRLinkage
645     return true;
646   }
647 }
648
649 static GlobalValue::LinkageTypes getDecodedLinkage(unsigned Val) {
650   switch (Val) {
651   default: // Map unknown/new linkages to external
652   case 0:
653     return GlobalValue::ExternalLinkage;
654   case 2:
655     return GlobalValue::AppendingLinkage;
656   case 3:
657     return GlobalValue::InternalLinkage;
658   case 5:
659     return GlobalValue::ExternalLinkage; // Obsolete DLLImportLinkage
660   case 6:
661     return GlobalValue::ExternalLinkage; // Obsolete DLLExportLinkage
662   case 7:
663     return GlobalValue::ExternalWeakLinkage;
664   case 8:
665     return GlobalValue::CommonLinkage;
666   case 9:
667     return GlobalValue::PrivateLinkage;
668   case 12:
669     return GlobalValue::AvailableExternallyLinkage;
670   case 13:
671     return GlobalValue::PrivateLinkage; // Obsolete LinkerPrivateLinkage
672   case 14:
673     return GlobalValue::PrivateLinkage; // Obsolete LinkerPrivateWeakLinkage
674   case 15:
675     return GlobalValue::ExternalLinkage; // Obsolete LinkOnceODRAutoHideLinkage
676   case 1: // Old value with implicit comdat.
677   case 16:
678     return GlobalValue::WeakAnyLinkage;
679   case 10: // Old value with implicit comdat.
680   case 17:
681     return GlobalValue::WeakODRLinkage;
682   case 4: // Old value with implicit comdat.
683   case 18:
684     return GlobalValue::LinkOnceAnyLinkage;
685   case 11: // Old value with implicit comdat.
686   case 19:
687     return GlobalValue::LinkOnceODRLinkage;
688   }
689 }
690
691 static GlobalValue::VisibilityTypes getDecodedVisibility(unsigned Val) {
692   switch (Val) {
693   default: // Map unknown visibilities to default.
694   case 0: return GlobalValue::DefaultVisibility;
695   case 1: return GlobalValue::HiddenVisibility;
696   case 2: return GlobalValue::ProtectedVisibility;
697   }
698 }
699
700 static GlobalValue::DLLStorageClassTypes
701 getDecodedDLLStorageClass(unsigned Val) {
702   switch (Val) {
703   default: // Map unknown values to default.
704   case 0: return GlobalValue::DefaultStorageClass;
705   case 1: return GlobalValue::DLLImportStorageClass;
706   case 2: return GlobalValue::DLLExportStorageClass;
707   }
708 }
709
710 static GlobalVariable::ThreadLocalMode getDecodedThreadLocalMode(unsigned Val) {
711   switch (Val) {
712     case 0: return GlobalVariable::NotThreadLocal;
713     default: // Map unknown non-zero value to general dynamic.
714     case 1: return GlobalVariable::GeneralDynamicTLSModel;
715     case 2: return GlobalVariable::LocalDynamicTLSModel;
716     case 3: return GlobalVariable::InitialExecTLSModel;
717     case 4: return GlobalVariable::LocalExecTLSModel;
718   }
719 }
720
721 static int getDecodedCastOpcode(unsigned Val) {
722   switch (Val) {
723   default: return -1;
724   case bitc::CAST_TRUNC   : return Instruction::Trunc;
725   case bitc::CAST_ZEXT    : return Instruction::ZExt;
726   case bitc::CAST_SEXT    : return Instruction::SExt;
727   case bitc::CAST_FPTOUI  : return Instruction::FPToUI;
728   case bitc::CAST_FPTOSI  : return Instruction::FPToSI;
729   case bitc::CAST_UITOFP  : return Instruction::UIToFP;
730   case bitc::CAST_SITOFP  : return Instruction::SIToFP;
731   case bitc::CAST_FPTRUNC : return Instruction::FPTrunc;
732   case bitc::CAST_FPEXT   : return Instruction::FPExt;
733   case bitc::CAST_PTRTOINT: return Instruction::PtrToInt;
734   case bitc::CAST_INTTOPTR: return Instruction::IntToPtr;
735   case bitc::CAST_BITCAST : return Instruction::BitCast;
736   case bitc::CAST_ADDRSPACECAST: return Instruction::AddrSpaceCast;
737   }
738 }
739
740 static int getDecodedBinaryOpcode(unsigned Val, Type *Ty) {
741   bool IsFP = Ty->isFPOrFPVectorTy();
742   // BinOps are only valid for int/fp or vector of int/fp types
743   if (!IsFP && !Ty->isIntOrIntVectorTy())
744     return -1;
745
746   switch (Val) {
747   default:
748     return -1;
749   case bitc::BINOP_ADD:
750     return IsFP ? Instruction::FAdd : Instruction::Add;
751   case bitc::BINOP_SUB:
752     return IsFP ? Instruction::FSub : Instruction::Sub;
753   case bitc::BINOP_MUL:
754     return IsFP ? Instruction::FMul : Instruction::Mul;
755   case bitc::BINOP_UDIV:
756     return IsFP ? -1 : Instruction::UDiv;
757   case bitc::BINOP_SDIV:
758     return IsFP ? Instruction::FDiv : Instruction::SDiv;
759   case bitc::BINOP_UREM:
760     return IsFP ? -1 : Instruction::URem;
761   case bitc::BINOP_SREM:
762     return IsFP ? Instruction::FRem : Instruction::SRem;
763   case bitc::BINOP_SHL:
764     return IsFP ? -1 : Instruction::Shl;
765   case bitc::BINOP_LSHR:
766     return IsFP ? -1 : Instruction::LShr;
767   case bitc::BINOP_ASHR:
768     return IsFP ? -1 : Instruction::AShr;
769   case bitc::BINOP_AND:
770     return IsFP ? -1 : Instruction::And;
771   case bitc::BINOP_OR:
772     return IsFP ? -1 : Instruction::Or;
773   case bitc::BINOP_XOR:
774     return IsFP ? -1 : Instruction::Xor;
775   }
776 }
777
778 static AtomicRMWInst::BinOp getDecodedRMWOperation(unsigned Val) {
779   switch (Val) {
780   default: return AtomicRMWInst::BAD_BINOP;
781   case bitc::RMW_XCHG: return AtomicRMWInst::Xchg;
782   case bitc::RMW_ADD: return AtomicRMWInst::Add;
783   case bitc::RMW_SUB: return AtomicRMWInst::Sub;
784   case bitc::RMW_AND: return AtomicRMWInst::And;
785   case bitc::RMW_NAND: return AtomicRMWInst::Nand;
786   case bitc::RMW_OR: return AtomicRMWInst::Or;
787   case bitc::RMW_XOR: return AtomicRMWInst::Xor;
788   case bitc::RMW_MAX: return AtomicRMWInst::Max;
789   case bitc::RMW_MIN: return AtomicRMWInst::Min;
790   case bitc::RMW_UMAX: return AtomicRMWInst::UMax;
791   case bitc::RMW_UMIN: return AtomicRMWInst::UMin;
792   }
793 }
794
795 static AtomicOrdering getDecodedOrdering(unsigned Val) {
796   switch (Val) {
797   case bitc::ORDERING_NOTATOMIC: return NotAtomic;
798   case bitc::ORDERING_UNORDERED: return Unordered;
799   case bitc::ORDERING_MONOTONIC: return Monotonic;
800   case bitc::ORDERING_ACQUIRE: return Acquire;
801   case bitc::ORDERING_RELEASE: return Release;
802   case bitc::ORDERING_ACQREL: return AcquireRelease;
803   default: // Map unknown orderings to sequentially-consistent.
804   case bitc::ORDERING_SEQCST: return SequentiallyConsistent;
805   }
806 }
807
808 static SynchronizationScope getDecodedSynchScope(unsigned Val) {
809   switch (Val) {
810   case bitc::SYNCHSCOPE_SINGLETHREAD: return SingleThread;
811   default: // Map unknown scopes to cross-thread.
812   case bitc::SYNCHSCOPE_CROSSTHREAD: return CrossThread;
813   }
814 }
815
816 static Comdat::SelectionKind getDecodedComdatSelectionKind(unsigned Val) {
817   switch (Val) {
818   default: // Map unknown selection kinds to any.
819   case bitc::COMDAT_SELECTION_KIND_ANY:
820     return Comdat::Any;
821   case bitc::COMDAT_SELECTION_KIND_EXACT_MATCH:
822     return Comdat::ExactMatch;
823   case bitc::COMDAT_SELECTION_KIND_LARGEST:
824     return Comdat::Largest;
825   case bitc::COMDAT_SELECTION_KIND_NO_DUPLICATES:
826     return Comdat::NoDuplicates;
827   case bitc::COMDAT_SELECTION_KIND_SAME_SIZE:
828     return Comdat::SameSize;
829   }
830 }
831
832 static FastMathFlags getDecodedFastMathFlags(unsigned Val) {
833   FastMathFlags FMF;
834   if (0 != (Val & FastMathFlags::UnsafeAlgebra))
835     FMF.setUnsafeAlgebra();
836   if (0 != (Val & FastMathFlags::NoNaNs))
837     FMF.setNoNaNs();
838   if (0 != (Val & FastMathFlags::NoInfs))
839     FMF.setNoInfs();
840   if (0 != (Val & FastMathFlags::NoSignedZeros))
841     FMF.setNoSignedZeros();
842   if (0 != (Val & FastMathFlags::AllowReciprocal))
843     FMF.setAllowReciprocal();
844   return FMF;
845 }
846
847 static void upgradeDLLImportExportLinkage(llvm::GlobalValue *GV, unsigned Val) {
848   switch (Val) {
849   case 5: GV->setDLLStorageClass(GlobalValue::DLLImportStorageClass); break;
850   case 6: GV->setDLLStorageClass(GlobalValue::DLLExportStorageClass); break;
851   }
852 }
853
854 namespace llvm {
855 namespace {
856 /// \brief A class for maintaining the slot number definition
857 /// as a placeholder for the actual definition for forward constants defs.
858 class ConstantPlaceHolder : public ConstantExpr {
859   void operator=(const ConstantPlaceHolder &) = delete;
860
861 public:
862   // allocate space for exactly one operand
863   void *operator new(size_t s) { return User::operator new(s, 1); }
864   explicit ConstantPlaceHolder(Type *Ty, LLVMContext &Context)
865       : ConstantExpr(Ty, Instruction::UserOp1, &Op<0>(), 1) {
866     Op<0>() = UndefValue::get(Type::getInt32Ty(Context));
867   }
868
869   /// \brief Methods to support type inquiry through isa, cast, and dyn_cast.
870   static bool classof(const Value *V) {
871     return isa<ConstantExpr>(V) &&
872            cast<ConstantExpr>(V)->getOpcode() == Instruction::UserOp1;
873   }
874
875   /// Provide fast operand accessors
876   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
877 };
878 }
879
880 // FIXME: can we inherit this from ConstantExpr?
881 template <>
882 struct OperandTraits<ConstantPlaceHolder> :
883   public FixedNumOperandTraits<ConstantPlaceHolder, 1> {
884 };
885 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ConstantPlaceHolder, Value)
886 }
887
888 bool BitcodeReaderValueList::assignValue(Value *V, unsigned Idx) {
889   if (Idx == size()) {
890     push_back(V);
891     return false;
892   }
893
894   if (Idx >= size())
895     resize(Idx+1);
896
897   WeakVH &OldV = ValuePtrs[Idx];
898   if (!OldV) {
899     OldV = V;
900     return false;
901   }
902
903   // Handle constants and non-constants (e.g. instrs) differently for
904   // efficiency.
905   if (Constant *PHC = dyn_cast<Constant>(&*OldV)) {
906     ResolveConstants.push_back(std::make_pair(PHC, Idx));
907     OldV = V;
908   } else {
909     // If there was a forward reference to this value, replace it.
910     Value *PrevVal = OldV;
911     // Check operator constraints.  We only put cleanuppads or catchpads in
912     // the forward value map if the value is constrained to match.
913     if (CatchPadInst *CatchPad = dyn_cast<CatchPadInst>(PrevVal)) {
914       if (!isa<CatchPadInst>(V))
915         return true;
916       // Delete the dummy basic block that was created with the sentinel
917       // catchpad.
918       BasicBlock *DummyBlock = CatchPad->getUnwindDest();
919       assert(DummyBlock == CatchPad->getNormalDest());
920       CatchPad->dropAllReferences();
921       delete DummyBlock;
922     } else if (isa<CleanupPadInst>(PrevVal)) {
923       if (!isa<CleanupPadInst>(V))
924         return true;
925     }
926     OldV->replaceAllUsesWith(V);
927     delete PrevVal;
928   }
929
930   return false;
931 }
932
933
934 Constant *BitcodeReaderValueList::getConstantFwdRef(unsigned Idx,
935                                                     Type *Ty) {
936   if (Idx >= size())
937     resize(Idx + 1);
938
939   if (Value *V = ValuePtrs[Idx]) {
940     if (Ty != V->getType())
941       report_fatal_error("Type mismatch in constant table!");
942     return cast<Constant>(V);
943   }
944
945   // Create and return a placeholder, which will later be RAUW'd.
946   Constant *C = new ConstantPlaceHolder(Ty, Context);
947   ValuePtrs[Idx] = C;
948   return C;
949 }
950
951 Value *BitcodeReaderValueList::getValueFwdRef(unsigned Idx, Type *Ty,
952                                               OperatorConstraint OC) {
953   // Bail out for a clearly invalid value. This would make us call resize(0)
954   if (Idx == UINT_MAX)
955     return nullptr;
956
957   if (Idx >= size())
958     resize(Idx + 1);
959
960   if (Value *V = ValuePtrs[Idx]) {
961     // If the types don't match, it's invalid.
962     if (Ty && Ty != V->getType())
963       return nullptr;
964     if (!OC)
965       return V;
966     // Use dyn_cast to enforce operator constraints
967     switch (OC) {
968     case OC_CatchPad:
969       return dyn_cast<CatchPadInst>(V);
970     case OC_CleanupPad:
971       return dyn_cast<CleanupPadInst>(V);
972     default:
973       llvm_unreachable("Unexpected operator constraint");
974     }
975   }
976
977   // No type specified, must be invalid reference.
978   if (!Ty) return nullptr;
979
980   // Create and return a placeholder, which will later be RAUW'd.
981   Value *V;
982   switch (OC) {
983   case OC_None:
984     V = new Argument(Ty);
985     break;
986   case OC_CatchPad: {
987     BasicBlock *BB = BasicBlock::Create(Context);
988     V = CatchPadInst::Create(BB, BB, {});
989     break;
990   }
991   default:
992     assert(OC == OC_CleanupPad && "unexpected operator constraint");
993     V = CleanupPadInst::Create(Context, {});
994     break;
995   }
996
997   ValuePtrs[Idx] = V;
998   return V;
999 }
1000
1001 /// Once all constants are read, this method bulk resolves any forward
1002 /// references.  The idea behind this is that we sometimes get constants (such
1003 /// as large arrays) which reference *many* forward ref constants.  Replacing
1004 /// each of these causes a lot of thrashing when building/reuniquing the
1005 /// constant.  Instead of doing this, we look at all the uses and rewrite all
1006 /// the place holders at once for any constant that uses a placeholder.
1007 void BitcodeReaderValueList::resolveConstantForwardRefs() {
1008   // Sort the values by-pointer so that they are efficient to look up with a
1009   // binary search.
1010   std::sort(ResolveConstants.begin(), ResolveConstants.end());
1011
1012   SmallVector<Constant*, 64> NewOps;
1013
1014   while (!ResolveConstants.empty()) {
1015     Value *RealVal = operator[](ResolveConstants.back().second);
1016     Constant *Placeholder = ResolveConstants.back().first;
1017     ResolveConstants.pop_back();
1018
1019     // Loop over all users of the placeholder, updating them to reference the
1020     // new value.  If they reference more than one placeholder, update them all
1021     // at once.
1022     while (!Placeholder->use_empty()) {
1023       auto UI = Placeholder->user_begin();
1024       User *U = *UI;
1025
1026       // If the using object isn't uniqued, just update the operands.  This
1027       // handles instructions and initializers for global variables.
1028       if (!isa<Constant>(U) || isa<GlobalValue>(U)) {
1029         UI.getUse().set(RealVal);
1030         continue;
1031       }
1032
1033       // Otherwise, we have a constant that uses the placeholder.  Replace that
1034       // constant with a new constant that has *all* placeholder uses updated.
1035       Constant *UserC = cast<Constant>(U);
1036       for (User::op_iterator I = UserC->op_begin(), E = UserC->op_end();
1037            I != E; ++I) {
1038         Value *NewOp;
1039         if (!isa<ConstantPlaceHolder>(*I)) {
1040           // Not a placeholder reference.
1041           NewOp = *I;
1042         } else if (*I == Placeholder) {
1043           // Common case is that it just references this one placeholder.
1044           NewOp = RealVal;
1045         } else {
1046           // Otherwise, look up the placeholder in ResolveConstants.
1047           ResolveConstantsTy::iterator It =
1048             std::lower_bound(ResolveConstants.begin(), ResolveConstants.end(),
1049                              std::pair<Constant*, unsigned>(cast<Constant>(*I),
1050                                                             0));
1051           assert(It != ResolveConstants.end() && It->first == *I);
1052           NewOp = operator[](It->second);
1053         }
1054
1055         NewOps.push_back(cast<Constant>(NewOp));
1056       }
1057
1058       // Make the new constant.
1059       Constant *NewC;
1060       if (ConstantArray *UserCA = dyn_cast<ConstantArray>(UserC)) {
1061         NewC = ConstantArray::get(UserCA->getType(), NewOps);
1062       } else if (ConstantStruct *UserCS = dyn_cast<ConstantStruct>(UserC)) {
1063         NewC = ConstantStruct::get(UserCS->getType(), NewOps);
1064       } else if (isa<ConstantVector>(UserC)) {
1065         NewC = ConstantVector::get(NewOps);
1066       } else {
1067         assert(isa<ConstantExpr>(UserC) && "Must be a ConstantExpr.");
1068         NewC = cast<ConstantExpr>(UserC)->getWithOperands(NewOps);
1069       }
1070
1071       UserC->replaceAllUsesWith(NewC);
1072       UserC->destroyConstant();
1073       NewOps.clear();
1074     }
1075
1076     // Update all ValueHandles, they should be the only users at this point.
1077     Placeholder->replaceAllUsesWith(RealVal);
1078     delete Placeholder;
1079   }
1080 }
1081
1082 void BitcodeReaderMDValueList::assignValue(Metadata *MD, unsigned Idx) {
1083   if (Idx == size()) {
1084     push_back(MD);
1085     return;
1086   }
1087
1088   if (Idx >= size())
1089     resize(Idx+1);
1090
1091   TrackingMDRef &OldMD = MDValuePtrs[Idx];
1092   if (!OldMD) {
1093     OldMD.reset(MD);
1094     return;
1095   }
1096
1097   // If there was a forward reference to this value, replace it.
1098   TempMDTuple PrevMD(cast<MDTuple>(OldMD.get()));
1099   PrevMD->replaceAllUsesWith(MD);
1100   --NumFwdRefs;
1101 }
1102
1103 Metadata *BitcodeReaderMDValueList::getValueFwdRef(unsigned Idx) {
1104   if (Idx >= size())
1105     resize(Idx + 1);
1106
1107   if (Metadata *MD = MDValuePtrs[Idx])
1108     return MD;
1109
1110   // Track forward refs to be resolved later.
1111   if (AnyFwdRefs) {
1112     MinFwdRef = std::min(MinFwdRef, Idx);
1113     MaxFwdRef = std::max(MaxFwdRef, Idx);
1114   } else {
1115     AnyFwdRefs = true;
1116     MinFwdRef = MaxFwdRef = Idx;
1117   }
1118   ++NumFwdRefs;
1119
1120   // Create and return a placeholder, which will later be RAUW'd.
1121   Metadata *MD = MDNode::getTemporary(Context, None).release();
1122   MDValuePtrs[Idx].reset(MD);
1123   return MD;
1124 }
1125
1126 void BitcodeReaderMDValueList::tryToResolveCycles() {
1127   if (!AnyFwdRefs)
1128     // Nothing to do.
1129     return;
1130
1131   if (NumFwdRefs)
1132     // Still forward references... can't resolve cycles.
1133     return;
1134
1135   // Resolve any cycles.
1136   for (unsigned I = MinFwdRef, E = MaxFwdRef + 1; I != E; ++I) {
1137     auto &MD = MDValuePtrs[I];
1138     auto *N = dyn_cast_or_null<MDNode>(MD);
1139     if (!N)
1140       continue;
1141
1142     assert(!N->isTemporary() && "Unexpected forward reference");
1143     N->resolveCycles();
1144   }
1145
1146   // Make sure we return early again until there's another forward ref.
1147   AnyFwdRefs = false;
1148 }
1149
1150 Type *BitcodeReader::getTypeByID(unsigned ID) {
1151   // The type table size is always specified correctly.
1152   if (ID >= TypeList.size())
1153     return nullptr;
1154
1155   if (Type *Ty = TypeList[ID])
1156     return Ty;
1157
1158   // If we have a forward reference, the only possible case is when it is to a
1159   // named struct.  Just create a placeholder for now.
1160   return TypeList[ID] = createIdentifiedStructType(Context);
1161 }
1162
1163 StructType *BitcodeReader::createIdentifiedStructType(LLVMContext &Context,
1164                                                       StringRef Name) {
1165   auto *Ret = StructType::create(Context, Name);
1166   IdentifiedStructTypes.push_back(Ret);
1167   return Ret;
1168 }
1169
1170 StructType *BitcodeReader::createIdentifiedStructType(LLVMContext &Context) {
1171   auto *Ret = StructType::create(Context);
1172   IdentifiedStructTypes.push_back(Ret);
1173   return Ret;
1174 }
1175
1176
1177 //===----------------------------------------------------------------------===//
1178 //  Functions for parsing blocks from the bitcode file
1179 //===----------------------------------------------------------------------===//
1180
1181
1182 /// \brief This fills an AttrBuilder object with the LLVM attributes that have
1183 /// been decoded from the given integer. This function must stay in sync with
1184 /// 'encodeLLVMAttributesForBitcode'.
1185 static void decodeLLVMAttributesForBitcode(AttrBuilder &B,
1186                                            uint64_t EncodedAttrs) {
1187   // FIXME: Remove in 4.0.
1188
1189   // The alignment is stored as a 16-bit raw value from bits 31--16.  We shift
1190   // the bits above 31 down by 11 bits.
1191   unsigned Alignment = (EncodedAttrs & (0xffffULL << 16)) >> 16;
1192   assert((!Alignment || isPowerOf2_32(Alignment)) &&
1193          "Alignment must be a power of two.");
1194
1195   if (Alignment)
1196     B.addAlignmentAttr(Alignment);
1197   B.addRawValue(((EncodedAttrs & (0xfffffULL << 32)) >> 11) |
1198                 (EncodedAttrs & 0xffff));
1199 }
1200
1201 std::error_code BitcodeReader::parseAttributeBlock() {
1202   if (Stream.EnterSubBlock(bitc::PARAMATTR_BLOCK_ID))
1203     return error("Invalid record");
1204
1205   if (!MAttributes.empty())
1206     return error("Invalid multiple blocks");
1207
1208   SmallVector<uint64_t, 64> Record;
1209
1210   SmallVector<AttributeSet, 8> Attrs;
1211
1212   // Read all the records.
1213   while (1) {
1214     BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
1215
1216     switch (Entry.Kind) {
1217     case BitstreamEntry::SubBlock: // Handled for us already.
1218     case BitstreamEntry::Error:
1219       return error("Malformed block");
1220     case BitstreamEntry::EndBlock:
1221       return std::error_code();
1222     case BitstreamEntry::Record:
1223       // The interesting case.
1224       break;
1225     }
1226
1227     // Read a record.
1228     Record.clear();
1229     switch (Stream.readRecord(Entry.ID, Record)) {
1230     default:  // Default behavior: ignore.
1231       break;
1232     case bitc::PARAMATTR_CODE_ENTRY_OLD: { // ENTRY: [paramidx0, attr0, ...]
1233       // FIXME: Remove in 4.0.
1234       if (Record.size() & 1)
1235         return error("Invalid record");
1236
1237       for (unsigned i = 0, e = Record.size(); i != e; i += 2) {
1238         AttrBuilder B;
1239         decodeLLVMAttributesForBitcode(B, Record[i+1]);
1240         Attrs.push_back(AttributeSet::get(Context, Record[i], B));
1241       }
1242
1243       MAttributes.push_back(AttributeSet::get(Context, Attrs));
1244       Attrs.clear();
1245       break;
1246     }
1247     case bitc::PARAMATTR_CODE_ENTRY: { // ENTRY: [attrgrp0, attrgrp1, ...]
1248       for (unsigned i = 0, e = Record.size(); i != e; ++i)
1249         Attrs.push_back(MAttributeGroups[Record[i]]);
1250
1251       MAttributes.push_back(AttributeSet::get(Context, Attrs));
1252       Attrs.clear();
1253       break;
1254     }
1255     }
1256   }
1257 }
1258
1259 // Returns Attribute::None on unrecognized codes.
1260 static Attribute::AttrKind getAttrFromCode(uint64_t Code) {
1261   switch (Code) {
1262   default:
1263     return Attribute::None;
1264   case bitc::ATTR_KIND_ALIGNMENT:
1265     return Attribute::Alignment;
1266   case bitc::ATTR_KIND_ALWAYS_INLINE:
1267     return Attribute::AlwaysInline;
1268   case bitc::ATTR_KIND_ARGMEMONLY:
1269     return Attribute::ArgMemOnly;
1270   case bitc::ATTR_KIND_BUILTIN:
1271     return Attribute::Builtin;
1272   case bitc::ATTR_KIND_BY_VAL:
1273     return Attribute::ByVal;
1274   case bitc::ATTR_KIND_IN_ALLOCA:
1275     return Attribute::InAlloca;
1276   case bitc::ATTR_KIND_COLD:
1277     return Attribute::Cold;
1278   case bitc::ATTR_KIND_CONVERGENT:
1279     return Attribute::Convergent;
1280   case bitc::ATTR_KIND_INLINE_HINT:
1281     return Attribute::InlineHint;
1282   case bitc::ATTR_KIND_IN_REG:
1283     return Attribute::InReg;
1284   case bitc::ATTR_KIND_JUMP_TABLE:
1285     return Attribute::JumpTable;
1286   case bitc::ATTR_KIND_MIN_SIZE:
1287     return Attribute::MinSize;
1288   case bitc::ATTR_KIND_NAKED:
1289     return Attribute::Naked;
1290   case bitc::ATTR_KIND_NEST:
1291     return Attribute::Nest;
1292   case bitc::ATTR_KIND_NO_ALIAS:
1293     return Attribute::NoAlias;
1294   case bitc::ATTR_KIND_NO_BUILTIN:
1295     return Attribute::NoBuiltin;
1296   case bitc::ATTR_KIND_NO_CAPTURE:
1297     return Attribute::NoCapture;
1298   case bitc::ATTR_KIND_NO_DUPLICATE:
1299     return Attribute::NoDuplicate;
1300   case bitc::ATTR_KIND_NO_IMPLICIT_FLOAT:
1301     return Attribute::NoImplicitFloat;
1302   case bitc::ATTR_KIND_NO_INLINE:
1303     return Attribute::NoInline;
1304   case bitc::ATTR_KIND_NON_LAZY_BIND:
1305     return Attribute::NonLazyBind;
1306   case bitc::ATTR_KIND_NON_NULL:
1307     return Attribute::NonNull;
1308   case bitc::ATTR_KIND_DEREFERENCEABLE:
1309     return Attribute::Dereferenceable;
1310   case bitc::ATTR_KIND_DEREFERENCEABLE_OR_NULL:
1311     return Attribute::DereferenceableOrNull;
1312   case bitc::ATTR_KIND_NO_RED_ZONE:
1313     return Attribute::NoRedZone;
1314   case bitc::ATTR_KIND_NO_RETURN:
1315     return Attribute::NoReturn;
1316   case bitc::ATTR_KIND_NO_UNWIND:
1317     return Attribute::NoUnwind;
1318   case bitc::ATTR_KIND_OPTIMIZE_FOR_SIZE:
1319     return Attribute::OptimizeForSize;
1320   case bitc::ATTR_KIND_OPTIMIZE_NONE:
1321     return Attribute::OptimizeNone;
1322   case bitc::ATTR_KIND_READ_NONE:
1323     return Attribute::ReadNone;
1324   case bitc::ATTR_KIND_READ_ONLY:
1325     return Attribute::ReadOnly;
1326   case bitc::ATTR_KIND_RETURNED:
1327     return Attribute::Returned;
1328   case bitc::ATTR_KIND_RETURNS_TWICE:
1329     return Attribute::ReturnsTwice;
1330   case bitc::ATTR_KIND_S_EXT:
1331     return Attribute::SExt;
1332   case bitc::ATTR_KIND_STACK_ALIGNMENT:
1333     return Attribute::StackAlignment;
1334   case bitc::ATTR_KIND_STACK_PROTECT:
1335     return Attribute::StackProtect;
1336   case bitc::ATTR_KIND_STACK_PROTECT_REQ:
1337     return Attribute::StackProtectReq;
1338   case bitc::ATTR_KIND_STACK_PROTECT_STRONG:
1339     return Attribute::StackProtectStrong;
1340   case bitc::ATTR_KIND_SAFESTACK:
1341     return Attribute::SafeStack;
1342   case bitc::ATTR_KIND_STRUCT_RET:
1343     return Attribute::StructRet;
1344   case bitc::ATTR_KIND_SANITIZE_ADDRESS:
1345     return Attribute::SanitizeAddress;
1346   case bitc::ATTR_KIND_SANITIZE_THREAD:
1347     return Attribute::SanitizeThread;
1348   case bitc::ATTR_KIND_SANITIZE_MEMORY:
1349     return Attribute::SanitizeMemory;
1350   case bitc::ATTR_KIND_UW_TABLE:
1351     return Attribute::UWTable;
1352   case bitc::ATTR_KIND_Z_EXT:
1353     return Attribute::ZExt;
1354   }
1355 }
1356
1357 std::error_code BitcodeReader::parseAlignmentValue(uint64_t Exponent,
1358                                                    unsigned &Alignment) {
1359   // Note: Alignment in bitcode files is incremented by 1, so that zero
1360   // can be used for default alignment.
1361   if (Exponent > Value::MaxAlignmentExponent + 1)
1362     return error("Invalid alignment value");
1363   Alignment = (1 << static_cast<unsigned>(Exponent)) >> 1;
1364   return std::error_code();
1365 }
1366
1367 std::error_code BitcodeReader::parseAttrKind(uint64_t Code,
1368                                              Attribute::AttrKind *Kind) {
1369   *Kind = getAttrFromCode(Code);
1370   if (*Kind == Attribute::None)
1371     return error(BitcodeError::CorruptedBitcode,
1372                  "Unknown attribute kind (" + Twine(Code) + ")");
1373   return std::error_code();
1374 }
1375
1376 std::error_code BitcodeReader::parseAttributeGroupBlock() {
1377   if (Stream.EnterSubBlock(bitc::PARAMATTR_GROUP_BLOCK_ID))
1378     return error("Invalid record");
1379
1380   if (!MAttributeGroups.empty())
1381     return error("Invalid multiple blocks");
1382
1383   SmallVector<uint64_t, 64> Record;
1384
1385   // Read all the records.
1386   while (1) {
1387     BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
1388
1389     switch (Entry.Kind) {
1390     case BitstreamEntry::SubBlock: // Handled for us already.
1391     case BitstreamEntry::Error:
1392       return error("Malformed block");
1393     case BitstreamEntry::EndBlock:
1394       return std::error_code();
1395     case BitstreamEntry::Record:
1396       // The interesting case.
1397       break;
1398     }
1399
1400     // Read a record.
1401     Record.clear();
1402     switch (Stream.readRecord(Entry.ID, Record)) {
1403     default:  // Default behavior: ignore.
1404       break;
1405     case bitc::PARAMATTR_GRP_CODE_ENTRY: { // ENTRY: [grpid, idx, a0, a1, ...]
1406       if (Record.size() < 3)
1407         return error("Invalid record");
1408
1409       uint64_t GrpID = Record[0];
1410       uint64_t Idx = Record[1]; // Index of the object this attribute refers to.
1411
1412       AttrBuilder B;
1413       for (unsigned i = 2, e = Record.size(); i != e; ++i) {
1414         if (Record[i] == 0) {        // Enum attribute
1415           Attribute::AttrKind Kind;
1416           if (std::error_code EC = parseAttrKind(Record[++i], &Kind))
1417             return EC;
1418
1419           B.addAttribute(Kind);
1420         } else if (Record[i] == 1) { // Integer attribute
1421           Attribute::AttrKind Kind;
1422           if (std::error_code EC = parseAttrKind(Record[++i], &Kind))
1423             return EC;
1424           if (Kind == Attribute::Alignment)
1425             B.addAlignmentAttr(Record[++i]);
1426           else if (Kind == Attribute::StackAlignment)
1427             B.addStackAlignmentAttr(Record[++i]);
1428           else if (Kind == Attribute::Dereferenceable)
1429             B.addDereferenceableAttr(Record[++i]);
1430           else if (Kind == Attribute::DereferenceableOrNull)
1431             B.addDereferenceableOrNullAttr(Record[++i]);
1432         } else {                     // String attribute
1433           assert((Record[i] == 3 || Record[i] == 4) &&
1434                  "Invalid attribute group entry");
1435           bool HasValue = (Record[i++] == 4);
1436           SmallString<64> KindStr;
1437           SmallString<64> ValStr;
1438
1439           while (Record[i] != 0 && i != e)
1440             KindStr += Record[i++];
1441           assert(Record[i] == 0 && "Kind string not null terminated");
1442
1443           if (HasValue) {
1444             // Has a value associated with it.
1445             ++i; // Skip the '0' that terminates the "kind" string.
1446             while (Record[i] != 0 && i != e)
1447               ValStr += Record[i++];
1448             assert(Record[i] == 0 && "Value string not null terminated");
1449           }
1450
1451           B.addAttribute(KindStr.str(), ValStr.str());
1452         }
1453       }
1454
1455       MAttributeGroups[GrpID] = AttributeSet::get(Context, Idx, B);
1456       break;
1457     }
1458     }
1459   }
1460 }
1461
1462 std::error_code BitcodeReader::parseTypeTable() {
1463   if (Stream.EnterSubBlock(bitc::TYPE_BLOCK_ID_NEW))
1464     return error("Invalid record");
1465
1466   return parseTypeTableBody();
1467 }
1468
1469 std::error_code BitcodeReader::parseTypeTableBody() {
1470   if (!TypeList.empty())
1471     return error("Invalid multiple blocks");
1472
1473   SmallVector<uint64_t, 64> Record;
1474   unsigned NumRecords = 0;
1475
1476   SmallString<64> TypeName;
1477
1478   // Read all the records for this type table.
1479   while (1) {
1480     BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
1481
1482     switch (Entry.Kind) {
1483     case BitstreamEntry::SubBlock: // Handled for us already.
1484     case BitstreamEntry::Error:
1485       return error("Malformed block");
1486     case BitstreamEntry::EndBlock:
1487       if (NumRecords != TypeList.size())
1488         return error("Malformed block");
1489       return std::error_code();
1490     case BitstreamEntry::Record:
1491       // The interesting case.
1492       break;
1493     }
1494
1495     // Read a record.
1496     Record.clear();
1497     Type *ResultTy = nullptr;
1498     switch (Stream.readRecord(Entry.ID, Record)) {
1499     default:
1500       return error("Invalid value");
1501     case bitc::TYPE_CODE_NUMENTRY: // TYPE_CODE_NUMENTRY: [numentries]
1502       // TYPE_CODE_NUMENTRY contains a count of the number of types in the
1503       // type list.  This allows us to reserve space.
1504       if (Record.size() < 1)
1505         return error("Invalid record");
1506       TypeList.resize(Record[0]);
1507       continue;
1508     case bitc::TYPE_CODE_VOID:      // VOID
1509       ResultTy = Type::getVoidTy(Context);
1510       break;
1511     case bitc::TYPE_CODE_HALF:     // HALF
1512       ResultTy = Type::getHalfTy(Context);
1513       break;
1514     case bitc::TYPE_CODE_FLOAT:     // FLOAT
1515       ResultTy = Type::getFloatTy(Context);
1516       break;
1517     case bitc::TYPE_CODE_DOUBLE:    // DOUBLE
1518       ResultTy = Type::getDoubleTy(Context);
1519       break;
1520     case bitc::TYPE_CODE_X86_FP80:  // X86_FP80
1521       ResultTy = Type::getX86_FP80Ty(Context);
1522       break;
1523     case bitc::TYPE_CODE_FP128:     // FP128
1524       ResultTy = Type::getFP128Ty(Context);
1525       break;
1526     case bitc::TYPE_CODE_PPC_FP128: // PPC_FP128
1527       ResultTy = Type::getPPC_FP128Ty(Context);
1528       break;
1529     case bitc::TYPE_CODE_LABEL:     // LABEL
1530       ResultTy = Type::getLabelTy(Context);
1531       break;
1532     case bitc::TYPE_CODE_METADATA:  // METADATA
1533       ResultTy = Type::getMetadataTy(Context);
1534       break;
1535     case bitc::TYPE_CODE_X86_MMX:   // X86_MMX
1536       ResultTy = Type::getX86_MMXTy(Context);
1537       break;
1538     case bitc::TYPE_CODE_TOKEN:     // TOKEN
1539       ResultTy = Type::getTokenTy(Context);
1540       break;
1541     case bitc::TYPE_CODE_INTEGER: { // INTEGER: [width]
1542       if (Record.size() < 1)
1543         return error("Invalid record");
1544
1545       uint64_t NumBits = Record[0];
1546       if (NumBits < IntegerType::MIN_INT_BITS ||
1547           NumBits > IntegerType::MAX_INT_BITS)
1548         return error("Bitwidth for integer type out of range");
1549       ResultTy = IntegerType::get(Context, NumBits);
1550       break;
1551     }
1552     case bitc::TYPE_CODE_POINTER: { // POINTER: [pointee type] or
1553                                     //          [pointee type, address space]
1554       if (Record.size() < 1)
1555         return error("Invalid record");
1556       unsigned AddressSpace = 0;
1557       if (Record.size() == 2)
1558         AddressSpace = Record[1];
1559       ResultTy = getTypeByID(Record[0]);
1560       if (!ResultTy ||
1561           !PointerType::isValidElementType(ResultTy))
1562         return error("Invalid type");
1563       ResultTy = PointerType::get(ResultTy, AddressSpace);
1564       break;
1565     }
1566     case bitc::TYPE_CODE_FUNCTION_OLD: {
1567       // FIXME: attrid is dead, remove it in LLVM 4.0
1568       // FUNCTION: [vararg, attrid, retty, paramty x N]
1569       if (Record.size() < 3)
1570         return error("Invalid record");
1571       SmallVector<Type*, 8> ArgTys;
1572       for (unsigned i = 3, e = Record.size(); i != e; ++i) {
1573         if (Type *T = getTypeByID(Record[i]))
1574           ArgTys.push_back(T);
1575         else
1576           break;
1577       }
1578
1579       ResultTy = getTypeByID(Record[2]);
1580       if (!ResultTy || ArgTys.size() < Record.size()-3)
1581         return error("Invalid type");
1582
1583       ResultTy = FunctionType::get(ResultTy, ArgTys, Record[0]);
1584       break;
1585     }
1586     case bitc::TYPE_CODE_FUNCTION: {
1587       // FUNCTION: [vararg, retty, paramty x N]
1588       if (Record.size() < 2)
1589         return error("Invalid record");
1590       SmallVector<Type*, 8> ArgTys;
1591       for (unsigned i = 2, e = Record.size(); i != e; ++i) {
1592         if (Type *T = getTypeByID(Record[i])) {
1593           if (!FunctionType::isValidArgumentType(T))
1594             return error("Invalid function argument type");
1595           ArgTys.push_back(T);
1596         }
1597         else
1598           break;
1599       }
1600
1601       ResultTy = getTypeByID(Record[1]);
1602       if (!ResultTy || ArgTys.size() < Record.size()-2)
1603         return error("Invalid type");
1604
1605       ResultTy = FunctionType::get(ResultTy, ArgTys, Record[0]);
1606       break;
1607     }
1608     case bitc::TYPE_CODE_STRUCT_ANON: {  // STRUCT: [ispacked, eltty x N]
1609       if (Record.size() < 1)
1610         return error("Invalid record");
1611       SmallVector<Type*, 8> EltTys;
1612       for (unsigned i = 1, e = Record.size(); i != e; ++i) {
1613         if (Type *T = getTypeByID(Record[i]))
1614           EltTys.push_back(T);
1615         else
1616           break;
1617       }
1618       if (EltTys.size() != Record.size()-1)
1619         return error("Invalid type");
1620       ResultTy = StructType::get(Context, EltTys, Record[0]);
1621       break;
1622     }
1623     case bitc::TYPE_CODE_STRUCT_NAME:   // STRUCT_NAME: [strchr x N]
1624       if (convertToString(Record, 0, TypeName))
1625         return error("Invalid record");
1626       continue;
1627
1628     case bitc::TYPE_CODE_STRUCT_NAMED: { // STRUCT: [ispacked, eltty x N]
1629       if (Record.size() < 1)
1630         return error("Invalid record");
1631
1632       if (NumRecords >= TypeList.size())
1633         return error("Invalid TYPE table");
1634
1635       // Check to see if this was forward referenced, if so fill in the temp.
1636       StructType *Res = cast_or_null<StructType>(TypeList[NumRecords]);
1637       if (Res) {
1638         Res->setName(TypeName);
1639         TypeList[NumRecords] = nullptr;
1640       } else  // Otherwise, create a new struct.
1641         Res = createIdentifiedStructType(Context, TypeName);
1642       TypeName.clear();
1643
1644       SmallVector<Type*, 8> EltTys;
1645       for (unsigned i = 1, e = Record.size(); i != e; ++i) {
1646         if (Type *T = getTypeByID(Record[i]))
1647           EltTys.push_back(T);
1648         else
1649           break;
1650       }
1651       if (EltTys.size() != Record.size()-1)
1652         return error("Invalid record");
1653       Res->setBody(EltTys, Record[0]);
1654       ResultTy = Res;
1655       break;
1656     }
1657     case bitc::TYPE_CODE_OPAQUE: {       // OPAQUE: []
1658       if (Record.size() != 1)
1659         return error("Invalid record");
1660
1661       if (NumRecords >= TypeList.size())
1662         return error("Invalid TYPE table");
1663
1664       // Check to see if this was forward referenced, if so fill in the temp.
1665       StructType *Res = cast_or_null<StructType>(TypeList[NumRecords]);
1666       if (Res) {
1667         Res->setName(TypeName);
1668         TypeList[NumRecords] = nullptr;
1669       } else  // Otherwise, create a new struct with no body.
1670         Res = createIdentifiedStructType(Context, TypeName);
1671       TypeName.clear();
1672       ResultTy = Res;
1673       break;
1674     }
1675     case bitc::TYPE_CODE_ARRAY:     // ARRAY: [numelts, eltty]
1676       if (Record.size() < 2)
1677         return error("Invalid record");
1678       ResultTy = getTypeByID(Record[1]);
1679       if (!ResultTy || !ArrayType::isValidElementType(ResultTy))
1680         return error("Invalid type");
1681       ResultTy = ArrayType::get(ResultTy, Record[0]);
1682       break;
1683     case bitc::TYPE_CODE_VECTOR:    // VECTOR: [numelts, eltty]
1684       if (Record.size() < 2)
1685         return error("Invalid record");
1686       if (Record[0] == 0)
1687         return error("Invalid vector length");
1688       ResultTy = getTypeByID(Record[1]);
1689       if (!ResultTy || !StructType::isValidElementType(ResultTy))
1690         return error("Invalid type");
1691       ResultTy = VectorType::get(ResultTy, Record[0]);
1692       break;
1693     }
1694
1695     if (NumRecords >= TypeList.size())
1696       return error("Invalid TYPE table");
1697     if (TypeList[NumRecords])
1698       return error(
1699           "Invalid TYPE table: Only named structs can be forward referenced");
1700     assert(ResultTy && "Didn't read a type?");
1701     TypeList[NumRecords++] = ResultTy;
1702   }
1703 }
1704
1705 std::error_code BitcodeReader::parseOperandBundleTags() {
1706   if (Stream.EnterSubBlock(bitc::OPERAND_BUNDLE_TAGS_BLOCK_ID))
1707     return error("Invalid record");
1708
1709   if (!BundleTags.empty())
1710     return error("Invalid multiple blocks");
1711
1712   SmallVector<uint64_t, 64> Record;
1713
1714   while (1) {
1715     BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
1716
1717     switch (Entry.Kind) {
1718     case BitstreamEntry::SubBlock: // Handled for us already.
1719     case BitstreamEntry::Error:
1720       return error("Malformed block");
1721     case BitstreamEntry::EndBlock:
1722       return std::error_code();
1723     case BitstreamEntry::Record:
1724       // The interesting case.
1725       break;
1726     }
1727
1728     // Tags are implicitly mapped to integers by their order.
1729
1730     if (Stream.readRecord(Entry.ID, Record) != bitc::OPERAND_BUNDLE_TAG)
1731       return error("Invalid record");
1732
1733     // OPERAND_BUNDLE_TAG: [strchr x N]
1734     BundleTags.emplace_back();
1735     if (convertToString(Record, 0, BundleTags.back()))
1736       return error("Invalid record");
1737     Record.clear();
1738   }
1739 }
1740
1741 /// Associate a value with its name from the given index in the provided record.
1742 ErrorOr<Value *> BitcodeReader::recordValue(SmallVectorImpl<uint64_t> &Record,
1743                                             unsigned NameIndex, Triple &TT) {
1744   SmallString<128> ValueName;
1745   if (convertToString(Record, NameIndex, ValueName))
1746     return error("Invalid record");
1747   unsigned ValueID = Record[0];
1748   if (ValueID >= ValueList.size() || !ValueList[ValueID])
1749     return error("Invalid record");
1750   Value *V = ValueList[ValueID];
1751
1752   V->setName(StringRef(ValueName.data(), ValueName.size()));
1753   auto *GO = dyn_cast<GlobalObject>(V);
1754   if (GO) {
1755     if (GO->getComdat() == reinterpret_cast<Comdat *>(1)) {
1756       if (TT.isOSBinFormatMachO())
1757         GO->setComdat(nullptr);
1758       else
1759         GO->setComdat(TheModule->getOrInsertComdat(V->getName()));
1760     }
1761   }
1762   return V;
1763 }
1764
1765 /// Parse the value symbol table at either the current parsing location or
1766 /// at the given bit offset if provided.
1767 std::error_code BitcodeReader::parseValueSymbolTable(unsigned Offset) {
1768   uint64_t CurrentBit;
1769   // Pass in the Offset to distinguish between calling for the module-level
1770   // VST (where we want to jump to the VST offset) and the function-level
1771   // VST (where we don't).
1772   if (Offset > 0) {
1773     // Save the current parsing location so we can jump back at the end
1774     // of the VST read.
1775     CurrentBit = Stream.GetCurrentBitNo();
1776     Stream.JumpToBit(Offset * 32);
1777 #ifndef NDEBUG
1778     // Do some checking if we are in debug mode.
1779     BitstreamEntry Entry = Stream.advance();
1780     assert(Entry.Kind == BitstreamEntry::SubBlock);
1781     assert(Entry.ID == bitc::VALUE_SYMTAB_BLOCK_ID);
1782 #else
1783     // In NDEBUG mode ignore the output so we don't get an unused variable
1784     // warning.
1785     Stream.advance();
1786 #endif
1787   }
1788
1789   // Compute the delta between the bitcode indices in the VST (the word offset
1790   // to the word-aligned ENTER_SUBBLOCK for the function block, and that
1791   // expected by the lazy reader. The reader's EnterSubBlock expects to have
1792   // already read the ENTER_SUBBLOCK code (size getAbbrevIDWidth) and BlockID
1793   // (size BlockIDWidth). Note that we access the stream's AbbrevID width here
1794   // just before entering the VST subblock because: 1) the EnterSubBlock
1795   // changes the AbbrevID width; 2) the VST block is nested within the same
1796   // outer MODULE_BLOCK as the FUNCTION_BLOCKs and therefore have the same
1797   // AbbrevID width before calling EnterSubBlock; and 3) when we want to
1798   // jump to the FUNCTION_BLOCK using this offset later, we don't want
1799   // to rely on the stream's AbbrevID width being that of the MODULE_BLOCK.
1800   unsigned FuncBitcodeOffsetDelta =
1801       Stream.getAbbrevIDWidth() + bitc::BlockIDWidth;
1802
1803   if (Stream.EnterSubBlock(bitc::VALUE_SYMTAB_BLOCK_ID))
1804     return error("Invalid record");
1805
1806   SmallVector<uint64_t, 64> Record;
1807
1808   Triple TT(TheModule->getTargetTriple());
1809
1810   // Read all the records for this value table.
1811   SmallString<128> ValueName;
1812   while (1) {
1813     BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
1814
1815     switch (Entry.Kind) {
1816     case BitstreamEntry::SubBlock: // Handled for us already.
1817     case BitstreamEntry::Error:
1818       return error("Malformed block");
1819     case BitstreamEntry::EndBlock:
1820       if (Offset > 0)
1821         Stream.JumpToBit(CurrentBit);
1822       return std::error_code();
1823     case BitstreamEntry::Record:
1824       // The interesting case.
1825       break;
1826     }
1827
1828     // Read a record.
1829     Record.clear();
1830     switch (Stream.readRecord(Entry.ID, Record)) {
1831     default:  // Default behavior: unknown type.
1832       break;
1833     case bitc::VST_CODE_ENTRY: {  // VST_ENTRY: [valueid, namechar x N]
1834       ErrorOr<Value *> ValOrErr = recordValue(Record, 1, TT);
1835       if (std::error_code EC = ValOrErr.getError())
1836         return EC;
1837       ValOrErr.get();
1838       break;
1839     }
1840     case bitc::VST_CODE_FNENTRY: {
1841       // VST_FNENTRY: [valueid, offset, namechar x N]
1842       ErrorOr<Value *> ValOrErr = recordValue(Record, 2, TT);
1843       if (std::error_code EC = ValOrErr.getError())
1844         return EC;
1845       Value *V = ValOrErr.get();
1846
1847       auto *GO = dyn_cast<GlobalObject>(V);
1848       if (!GO) {
1849         // If this is an alias, need to get the actual Function object
1850         // it aliases, in order to set up the DeferredFunctionInfo entry below.
1851         auto *GA = dyn_cast<GlobalAlias>(V);
1852         if (GA)
1853           GO = GA->getBaseObject();
1854         assert(GO);
1855       }
1856
1857       uint64_t FuncWordOffset = Record[1];
1858       Function *F = dyn_cast<Function>(GO);
1859       assert(F);
1860       uint64_t FuncBitOffset = FuncWordOffset * 32;
1861       DeferredFunctionInfo[F] = FuncBitOffset + FuncBitcodeOffsetDelta;
1862       // Set the LastFunctionBlockBit to point to the last function block.
1863       // Later when parsing is resumed after function materialization,
1864       // we can simply skip that last function block.
1865       if (FuncBitOffset > LastFunctionBlockBit)
1866         LastFunctionBlockBit = FuncBitOffset;
1867       break;
1868     }
1869     case bitc::VST_CODE_BBENTRY: {
1870       if (convertToString(Record, 1, ValueName))
1871         return error("Invalid record");
1872       BasicBlock *BB = getBasicBlock(Record[0]);
1873       if (!BB)
1874         return error("Invalid record");
1875
1876       BB->setName(StringRef(ValueName.data(), ValueName.size()));
1877       ValueName.clear();
1878       break;
1879     }
1880     }
1881   }
1882 }
1883
1884 static int64_t unrotateSign(uint64_t U) { return U & 1 ? ~(U >> 1) : U >> 1; }
1885
1886 std::error_code BitcodeReader::parseMetadata() {
1887   IsMetadataMaterialized = true;
1888   unsigned NextMDValueNo = MDValueList.size();
1889
1890   if (Stream.EnterSubBlock(bitc::METADATA_BLOCK_ID))
1891     return error("Invalid record");
1892
1893   SmallVector<uint64_t, 64> Record;
1894
1895   auto getMD =
1896       [&](unsigned ID) -> Metadata *{ return MDValueList.getValueFwdRef(ID); };
1897   auto getMDOrNull = [&](unsigned ID) -> Metadata *{
1898     if (ID)
1899       return getMD(ID - 1);
1900     return nullptr;
1901   };
1902   auto getMDString = [&](unsigned ID) -> MDString *{
1903     // This requires that the ID is not really a forward reference.  In
1904     // particular, the MDString must already have been resolved.
1905     return cast_or_null<MDString>(getMDOrNull(ID));
1906   };
1907
1908 #define GET_OR_DISTINCT(CLASS, DISTINCT, ARGS)                                 \
1909   (DISTINCT ? CLASS::getDistinct ARGS : CLASS::get ARGS)
1910
1911   // Read all the records.
1912   while (1) {
1913     BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
1914
1915     switch (Entry.Kind) {
1916     case BitstreamEntry::SubBlock: // Handled for us already.
1917     case BitstreamEntry::Error:
1918       return error("Malformed block");
1919     case BitstreamEntry::EndBlock:
1920       MDValueList.tryToResolveCycles();
1921       return std::error_code();
1922     case BitstreamEntry::Record:
1923       // The interesting case.
1924       break;
1925     }
1926
1927     // Read a record.
1928     Record.clear();
1929     unsigned Code = Stream.readRecord(Entry.ID, Record);
1930     bool IsDistinct = false;
1931     switch (Code) {
1932     default:  // Default behavior: ignore.
1933       break;
1934     case bitc::METADATA_NAME: {
1935       // Read name of the named metadata.
1936       SmallString<8> Name(Record.begin(), Record.end());
1937       Record.clear();
1938       Code = Stream.ReadCode();
1939
1940       unsigned NextBitCode = Stream.readRecord(Code, Record);
1941       if (NextBitCode != bitc::METADATA_NAMED_NODE)
1942         return error("METADATA_NAME not followed by METADATA_NAMED_NODE");
1943
1944       // Read named metadata elements.
1945       unsigned Size = Record.size();
1946       NamedMDNode *NMD = TheModule->getOrInsertNamedMetadata(Name);
1947       for (unsigned i = 0; i != Size; ++i) {
1948         MDNode *MD = dyn_cast_or_null<MDNode>(MDValueList.getValueFwdRef(Record[i]));
1949         if (!MD)
1950           return error("Invalid record");
1951         NMD->addOperand(MD);
1952       }
1953       break;
1954     }
1955     case bitc::METADATA_OLD_FN_NODE: {
1956       // FIXME: Remove in 4.0.
1957       // This is a LocalAsMetadata record, the only type of function-local
1958       // metadata.
1959       if (Record.size() % 2 == 1)
1960         return error("Invalid record");
1961
1962       // If this isn't a LocalAsMetadata record, we're dropping it.  This used
1963       // to be legal, but there's no upgrade path.
1964       auto dropRecord = [&] {
1965         MDValueList.assignValue(MDNode::get(Context, None), NextMDValueNo++);
1966       };
1967       if (Record.size() != 2) {
1968         dropRecord();
1969         break;
1970       }
1971
1972       Type *Ty = getTypeByID(Record[0]);
1973       if (Ty->isMetadataTy() || Ty->isVoidTy()) {
1974         dropRecord();
1975         break;
1976       }
1977
1978       MDValueList.assignValue(
1979           LocalAsMetadata::get(ValueList.getValueFwdRef(Record[1], Ty)),
1980           NextMDValueNo++);
1981       break;
1982     }
1983     case bitc::METADATA_OLD_NODE: {
1984       // FIXME: Remove in 4.0.
1985       if (Record.size() % 2 == 1)
1986         return error("Invalid record");
1987
1988       unsigned Size = Record.size();
1989       SmallVector<Metadata *, 8> Elts;
1990       for (unsigned i = 0; i != Size; i += 2) {
1991         Type *Ty = getTypeByID(Record[i]);
1992         if (!Ty)
1993           return error("Invalid record");
1994         if (Ty->isMetadataTy())
1995           Elts.push_back(MDValueList.getValueFwdRef(Record[i+1]));
1996         else if (!Ty->isVoidTy()) {
1997           auto *MD =
1998               ValueAsMetadata::get(ValueList.getValueFwdRef(Record[i + 1], Ty));
1999           assert(isa<ConstantAsMetadata>(MD) &&
2000                  "Expected non-function-local metadata");
2001           Elts.push_back(MD);
2002         } else
2003           Elts.push_back(nullptr);
2004       }
2005       MDValueList.assignValue(MDNode::get(Context, Elts), NextMDValueNo++);
2006       break;
2007     }
2008     case bitc::METADATA_VALUE: {
2009       if (Record.size() != 2)
2010         return error("Invalid record");
2011
2012       Type *Ty = getTypeByID(Record[0]);
2013       if (Ty->isMetadataTy() || Ty->isVoidTy())
2014         return error("Invalid record");
2015
2016       MDValueList.assignValue(
2017           ValueAsMetadata::get(ValueList.getValueFwdRef(Record[1], Ty)),
2018           NextMDValueNo++);
2019       break;
2020     }
2021     case bitc::METADATA_DISTINCT_NODE:
2022       IsDistinct = true;
2023       // fallthrough...
2024     case bitc::METADATA_NODE: {
2025       SmallVector<Metadata *, 8> Elts;
2026       Elts.reserve(Record.size());
2027       for (unsigned ID : Record)
2028         Elts.push_back(ID ? MDValueList.getValueFwdRef(ID - 1) : nullptr);
2029       MDValueList.assignValue(IsDistinct ? MDNode::getDistinct(Context, Elts)
2030                                          : MDNode::get(Context, Elts),
2031                               NextMDValueNo++);
2032       break;
2033     }
2034     case bitc::METADATA_LOCATION: {
2035       if (Record.size() != 5)
2036         return error("Invalid record");
2037
2038       unsigned Line = Record[1];
2039       unsigned Column = Record[2];
2040       MDNode *Scope = cast<MDNode>(MDValueList.getValueFwdRef(Record[3]));
2041       Metadata *InlinedAt =
2042           Record[4] ? MDValueList.getValueFwdRef(Record[4] - 1) : nullptr;
2043       MDValueList.assignValue(
2044           GET_OR_DISTINCT(DILocation, Record[0],
2045                           (Context, Line, Column, Scope, InlinedAt)),
2046           NextMDValueNo++);
2047       break;
2048     }
2049     case bitc::METADATA_GENERIC_DEBUG: {
2050       if (Record.size() < 4)
2051         return error("Invalid record");
2052
2053       unsigned Tag = Record[1];
2054       unsigned Version = Record[2];
2055
2056       if (Tag >= 1u << 16 || Version != 0)
2057         return error("Invalid record");
2058
2059       auto *Header = getMDString(Record[3]);
2060       SmallVector<Metadata *, 8> DwarfOps;
2061       for (unsigned I = 4, E = Record.size(); I != E; ++I)
2062         DwarfOps.push_back(Record[I] ? MDValueList.getValueFwdRef(Record[I] - 1)
2063                                      : nullptr);
2064       MDValueList.assignValue(GET_OR_DISTINCT(GenericDINode, Record[0],
2065                                               (Context, Tag, Header, DwarfOps)),
2066                               NextMDValueNo++);
2067       break;
2068     }
2069     case bitc::METADATA_SUBRANGE: {
2070       if (Record.size() != 3)
2071         return error("Invalid record");
2072
2073       MDValueList.assignValue(
2074           GET_OR_DISTINCT(DISubrange, Record[0],
2075                           (Context, Record[1], unrotateSign(Record[2]))),
2076           NextMDValueNo++);
2077       break;
2078     }
2079     case bitc::METADATA_ENUMERATOR: {
2080       if (Record.size() != 3)
2081         return error("Invalid record");
2082
2083       MDValueList.assignValue(GET_OR_DISTINCT(DIEnumerator, Record[0],
2084                                               (Context, unrotateSign(Record[1]),
2085                                                getMDString(Record[2]))),
2086                               NextMDValueNo++);
2087       break;
2088     }
2089     case bitc::METADATA_BASIC_TYPE: {
2090       if (Record.size() != 6)
2091         return error("Invalid record");
2092
2093       MDValueList.assignValue(
2094           GET_OR_DISTINCT(DIBasicType, Record[0],
2095                           (Context, Record[1], getMDString(Record[2]),
2096                            Record[3], Record[4], Record[5])),
2097           NextMDValueNo++);
2098       break;
2099     }
2100     case bitc::METADATA_DERIVED_TYPE: {
2101       if (Record.size() != 12)
2102         return error("Invalid record");
2103
2104       MDValueList.assignValue(
2105           GET_OR_DISTINCT(DIDerivedType, Record[0],
2106                           (Context, Record[1], getMDString(Record[2]),
2107                            getMDOrNull(Record[3]), Record[4],
2108                            getMDOrNull(Record[5]), getMDOrNull(Record[6]),
2109                            Record[7], Record[8], Record[9], Record[10],
2110                            getMDOrNull(Record[11]))),
2111           NextMDValueNo++);
2112       break;
2113     }
2114     case bitc::METADATA_COMPOSITE_TYPE: {
2115       if (Record.size() != 16)
2116         return error("Invalid record");
2117
2118       MDValueList.assignValue(
2119           GET_OR_DISTINCT(DICompositeType, Record[0],
2120                           (Context, Record[1], getMDString(Record[2]),
2121                            getMDOrNull(Record[3]), Record[4],
2122                            getMDOrNull(Record[5]), getMDOrNull(Record[6]),
2123                            Record[7], Record[8], Record[9], Record[10],
2124                            getMDOrNull(Record[11]), Record[12],
2125                            getMDOrNull(Record[13]), getMDOrNull(Record[14]),
2126                            getMDString(Record[15]))),
2127           NextMDValueNo++);
2128       break;
2129     }
2130     case bitc::METADATA_SUBROUTINE_TYPE: {
2131       if (Record.size() != 3)
2132         return error("Invalid record");
2133
2134       MDValueList.assignValue(
2135           GET_OR_DISTINCT(DISubroutineType, Record[0],
2136                           (Context, Record[1], getMDOrNull(Record[2]))),
2137           NextMDValueNo++);
2138       break;
2139     }
2140
2141     case bitc::METADATA_MODULE: {
2142       if (Record.size() != 6)
2143         return error("Invalid record");
2144
2145       MDValueList.assignValue(
2146           GET_OR_DISTINCT(DIModule, Record[0],
2147                           (Context, getMDOrNull(Record[1]),
2148                           getMDString(Record[2]), getMDString(Record[3]),
2149                           getMDString(Record[4]), getMDString(Record[5]))),
2150           NextMDValueNo++);
2151       break;
2152     }
2153
2154     case bitc::METADATA_FILE: {
2155       if (Record.size() != 3)
2156         return error("Invalid record");
2157
2158       MDValueList.assignValue(
2159           GET_OR_DISTINCT(DIFile, Record[0], (Context, getMDString(Record[1]),
2160                                               getMDString(Record[2]))),
2161           NextMDValueNo++);
2162       break;
2163     }
2164     case bitc::METADATA_COMPILE_UNIT: {
2165       if (Record.size() < 14 || Record.size() > 15)
2166         return error("Invalid record");
2167
2168       // Ignore Record[1], which indicates whether this compile unit is
2169       // distinct.  It's always distinct.
2170       MDValueList.assignValue(
2171           DICompileUnit::getDistinct(
2172               Context, Record[1], getMDOrNull(Record[2]),
2173               getMDString(Record[3]), Record[4], getMDString(Record[5]),
2174               Record[6], getMDString(Record[7]), Record[8],
2175               getMDOrNull(Record[9]), getMDOrNull(Record[10]),
2176               getMDOrNull(Record[11]), getMDOrNull(Record[12]),
2177               getMDOrNull(Record[13]), Record.size() == 14 ? 0 : Record[14]),
2178           NextMDValueNo++);
2179       break;
2180     }
2181     case bitc::METADATA_SUBPROGRAM: {
2182       if (Record.size() != 19)
2183         return error("Invalid record");
2184
2185       MDValueList.assignValue(
2186           GET_OR_DISTINCT(
2187               DISubprogram,
2188               Record[0] || Record[8], // All definitions should be distinct.
2189               (Context, getMDOrNull(Record[1]), getMDString(Record[2]),
2190                getMDString(Record[3]), getMDOrNull(Record[4]), Record[5],
2191                getMDOrNull(Record[6]), Record[7], Record[8], Record[9],
2192                getMDOrNull(Record[10]), Record[11], Record[12], Record[13],
2193                Record[14], getMDOrNull(Record[15]), getMDOrNull(Record[16]),
2194                getMDOrNull(Record[17]), getMDOrNull(Record[18]))),
2195           NextMDValueNo++);
2196       break;
2197     }
2198     case bitc::METADATA_LEXICAL_BLOCK: {
2199       if (Record.size() != 5)
2200         return error("Invalid record");
2201
2202       MDValueList.assignValue(
2203           GET_OR_DISTINCT(DILexicalBlock, Record[0],
2204                           (Context, getMDOrNull(Record[1]),
2205                            getMDOrNull(Record[2]), Record[3], Record[4])),
2206           NextMDValueNo++);
2207       break;
2208     }
2209     case bitc::METADATA_LEXICAL_BLOCK_FILE: {
2210       if (Record.size() != 4)
2211         return error("Invalid record");
2212
2213       MDValueList.assignValue(
2214           GET_OR_DISTINCT(DILexicalBlockFile, Record[0],
2215                           (Context, getMDOrNull(Record[1]),
2216                            getMDOrNull(Record[2]), Record[3])),
2217           NextMDValueNo++);
2218       break;
2219     }
2220     case bitc::METADATA_NAMESPACE: {
2221       if (Record.size() != 5)
2222         return error("Invalid record");
2223
2224       MDValueList.assignValue(
2225           GET_OR_DISTINCT(DINamespace, Record[0],
2226                           (Context, getMDOrNull(Record[1]),
2227                            getMDOrNull(Record[2]), getMDString(Record[3]),
2228                            Record[4])),
2229           NextMDValueNo++);
2230       break;
2231     }
2232     case bitc::METADATA_TEMPLATE_TYPE: {
2233       if (Record.size() != 3)
2234         return error("Invalid record");
2235
2236       MDValueList.assignValue(GET_OR_DISTINCT(DITemplateTypeParameter,
2237                                               Record[0],
2238                                               (Context, getMDString(Record[1]),
2239                                                getMDOrNull(Record[2]))),
2240                               NextMDValueNo++);
2241       break;
2242     }
2243     case bitc::METADATA_TEMPLATE_VALUE: {
2244       if (Record.size() != 5)
2245         return error("Invalid record");
2246
2247       MDValueList.assignValue(
2248           GET_OR_DISTINCT(DITemplateValueParameter, Record[0],
2249                           (Context, Record[1], getMDString(Record[2]),
2250                            getMDOrNull(Record[3]), getMDOrNull(Record[4]))),
2251           NextMDValueNo++);
2252       break;
2253     }
2254     case bitc::METADATA_GLOBAL_VAR: {
2255       if (Record.size() != 11)
2256         return error("Invalid record");
2257
2258       MDValueList.assignValue(
2259           GET_OR_DISTINCT(DIGlobalVariable, Record[0],
2260                           (Context, getMDOrNull(Record[1]),
2261                            getMDString(Record[2]), getMDString(Record[3]),
2262                            getMDOrNull(Record[4]), Record[5],
2263                            getMDOrNull(Record[6]), Record[7], Record[8],
2264                            getMDOrNull(Record[9]), getMDOrNull(Record[10]))),
2265           NextMDValueNo++);
2266       break;
2267     }
2268     case bitc::METADATA_LOCAL_VAR: {
2269       // 10th field is for the obseleted 'inlinedAt:' field.
2270       if (Record.size() < 8 || Record.size() > 10)
2271         return error("Invalid record");
2272
2273       // 2nd field used to be an artificial tag, either DW_TAG_auto_variable or
2274       // DW_TAG_arg_variable.
2275       bool HasTag = Record.size() > 8;
2276       MDValueList.assignValue(
2277           GET_OR_DISTINCT(DILocalVariable, Record[0],
2278                           (Context, getMDOrNull(Record[1 + HasTag]),
2279                            getMDString(Record[2 + HasTag]),
2280                            getMDOrNull(Record[3 + HasTag]), Record[4 + HasTag],
2281                            getMDOrNull(Record[5 + HasTag]), Record[6 + HasTag],
2282                            Record[7 + HasTag])),
2283           NextMDValueNo++);
2284       break;
2285     }
2286     case bitc::METADATA_EXPRESSION: {
2287       if (Record.size() < 1)
2288         return error("Invalid record");
2289
2290       MDValueList.assignValue(
2291           GET_OR_DISTINCT(DIExpression, Record[0],
2292                           (Context, makeArrayRef(Record).slice(1))),
2293           NextMDValueNo++);
2294       break;
2295     }
2296     case bitc::METADATA_OBJC_PROPERTY: {
2297       if (Record.size() != 8)
2298         return error("Invalid record");
2299
2300       MDValueList.assignValue(
2301           GET_OR_DISTINCT(DIObjCProperty, Record[0],
2302                           (Context, getMDString(Record[1]),
2303                            getMDOrNull(Record[2]), Record[3],
2304                            getMDString(Record[4]), getMDString(Record[5]),
2305                            Record[6], getMDOrNull(Record[7]))),
2306           NextMDValueNo++);
2307       break;
2308     }
2309     case bitc::METADATA_IMPORTED_ENTITY: {
2310       if (Record.size() != 6)
2311         return error("Invalid record");
2312
2313       MDValueList.assignValue(
2314           GET_OR_DISTINCT(DIImportedEntity, Record[0],
2315                           (Context, Record[1], getMDOrNull(Record[2]),
2316                            getMDOrNull(Record[3]), Record[4],
2317                            getMDString(Record[5]))),
2318           NextMDValueNo++);
2319       break;
2320     }
2321     case bitc::METADATA_STRING: {
2322       std::string String(Record.begin(), Record.end());
2323       llvm::UpgradeMDStringConstant(String);
2324       Metadata *MD = MDString::get(Context, String);
2325       MDValueList.assignValue(MD, NextMDValueNo++);
2326       break;
2327     }
2328     case bitc::METADATA_KIND: {
2329       if (Record.size() < 2)
2330         return error("Invalid record");
2331
2332       unsigned Kind = Record[0];
2333       SmallString<8> Name(Record.begin()+1, Record.end());
2334
2335       unsigned NewKind = TheModule->getMDKindID(Name.str());
2336       if (!MDKindMap.insert(std::make_pair(Kind, NewKind)).second)
2337         return error("Conflicting METADATA_KIND records");
2338       break;
2339     }
2340     }
2341   }
2342 #undef GET_OR_DISTINCT
2343 }
2344
2345 /// Decode a signed value stored with the sign bit in the LSB for dense VBR
2346 /// encoding.
2347 uint64_t BitcodeReader::decodeSignRotatedValue(uint64_t V) {
2348   if ((V & 1) == 0)
2349     return V >> 1;
2350   if (V != 1)
2351     return -(V >> 1);
2352   // There is no such thing as -0 with integers.  "-0" really means MININT.
2353   return 1ULL << 63;
2354 }
2355
2356 /// Resolve all of the initializers for global values and aliases that we can.
2357 std::error_code BitcodeReader::resolveGlobalAndAliasInits() {
2358   std::vector<std::pair<GlobalVariable*, unsigned> > GlobalInitWorklist;
2359   std::vector<std::pair<GlobalAlias*, unsigned> > AliasInitWorklist;
2360   std::vector<std::pair<Function*, unsigned> > FunctionPrefixWorklist;
2361   std::vector<std::pair<Function*, unsigned> > FunctionPrologueWorklist;
2362   std::vector<std::pair<Function*, unsigned> > FunctionPersonalityFnWorklist;
2363
2364   GlobalInitWorklist.swap(GlobalInits);
2365   AliasInitWorklist.swap(AliasInits);
2366   FunctionPrefixWorklist.swap(FunctionPrefixes);
2367   FunctionPrologueWorklist.swap(FunctionPrologues);
2368   FunctionPersonalityFnWorklist.swap(FunctionPersonalityFns);
2369
2370   while (!GlobalInitWorklist.empty()) {
2371     unsigned ValID = GlobalInitWorklist.back().second;
2372     if (ValID >= ValueList.size()) {
2373       // Not ready to resolve this yet, it requires something later in the file.
2374       GlobalInits.push_back(GlobalInitWorklist.back());
2375     } else {
2376       if (Constant *C = dyn_cast_or_null<Constant>(ValueList[ValID]))
2377         GlobalInitWorklist.back().first->setInitializer(C);
2378       else
2379         return error("Expected a constant");
2380     }
2381     GlobalInitWorklist.pop_back();
2382   }
2383
2384   while (!AliasInitWorklist.empty()) {
2385     unsigned ValID = AliasInitWorklist.back().second;
2386     if (ValID >= ValueList.size()) {
2387       AliasInits.push_back(AliasInitWorklist.back());
2388     } else {
2389       Constant *C = dyn_cast_or_null<Constant>(ValueList[ValID]);
2390       if (!C)
2391         return error("Expected a constant");
2392       GlobalAlias *Alias = AliasInitWorklist.back().first;
2393       if (C->getType() != Alias->getType())
2394         return error("Alias and aliasee types don't match");
2395       Alias->setAliasee(C);
2396     }
2397     AliasInitWorklist.pop_back();
2398   }
2399
2400   while (!FunctionPrefixWorklist.empty()) {
2401     unsigned ValID = FunctionPrefixWorklist.back().second;
2402     if (ValID >= ValueList.size()) {
2403       FunctionPrefixes.push_back(FunctionPrefixWorklist.back());
2404     } else {
2405       if (Constant *C = dyn_cast_or_null<Constant>(ValueList[ValID]))
2406         FunctionPrefixWorklist.back().first->setPrefixData(C);
2407       else
2408         return error("Expected a constant");
2409     }
2410     FunctionPrefixWorklist.pop_back();
2411   }
2412
2413   while (!FunctionPrologueWorklist.empty()) {
2414     unsigned ValID = FunctionPrologueWorklist.back().second;
2415     if (ValID >= ValueList.size()) {
2416       FunctionPrologues.push_back(FunctionPrologueWorklist.back());
2417     } else {
2418       if (Constant *C = dyn_cast_or_null<Constant>(ValueList[ValID]))
2419         FunctionPrologueWorklist.back().first->setPrologueData(C);
2420       else
2421         return error("Expected a constant");
2422     }
2423     FunctionPrologueWorklist.pop_back();
2424   }
2425
2426   while (!FunctionPersonalityFnWorklist.empty()) {
2427     unsigned ValID = FunctionPersonalityFnWorklist.back().second;
2428     if (ValID >= ValueList.size()) {
2429       FunctionPersonalityFns.push_back(FunctionPersonalityFnWorklist.back());
2430     } else {
2431       if (Constant *C = dyn_cast_or_null<Constant>(ValueList[ValID]))
2432         FunctionPersonalityFnWorklist.back().first->setPersonalityFn(C);
2433       else
2434         return error("Expected a constant");
2435     }
2436     FunctionPersonalityFnWorklist.pop_back();
2437   }
2438
2439   return std::error_code();
2440 }
2441
2442 static APInt readWideAPInt(ArrayRef<uint64_t> Vals, unsigned TypeBits) {
2443   SmallVector<uint64_t, 8> Words(Vals.size());
2444   std::transform(Vals.begin(), Vals.end(), Words.begin(),
2445                  BitcodeReader::decodeSignRotatedValue);
2446
2447   return APInt(TypeBits, Words);
2448 }
2449
2450 std::error_code BitcodeReader::parseConstants() {
2451   if (Stream.EnterSubBlock(bitc::CONSTANTS_BLOCK_ID))
2452     return error("Invalid record");
2453
2454   SmallVector<uint64_t, 64> Record;
2455
2456   // Read all the records for this value table.
2457   Type *CurTy = Type::getInt32Ty(Context);
2458   unsigned NextCstNo = ValueList.size();
2459   while (1) {
2460     BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
2461
2462     switch (Entry.Kind) {
2463     case BitstreamEntry::SubBlock: // Handled for us already.
2464     case BitstreamEntry::Error:
2465       return error("Malformed block");
2466     case BitstreamEntry::EndBlock:
2467       if (NextCstNo != ValueList.size())
2468         return error("Invalid ronstant reference");
2469
2470       // Once all the constants have been read, go through and resolve forward
2471       // references.
2472       ValueList.resolveConstantForwardRefs();
2473       return std::error_code();
2474     case BitstreamEntry::Record:
2475       // The interesting case.
2476       break;
2477     }
2478
2479     // Read a record.
2480     Record.clear();
2481     Value *V = nullptr;
2482     unsigned BitCode = Stream.readRecord(Entry.ID, Record);
2483     switch (BitCode) {
2484     default:  // Default behavior: unknown constant
2485     case bitc::CST_CODE_UNDEF:     // UNDEF
2486       V = UndefValue::get(CurTy);
2487       break;
2488     case bitc::CST_CODE_SETTYPE:   // SETTYPE: [typeid]
2489       if (Record.empty())
2490         return error("Invalid record");
2491       if (Record[0] >= TypeList.size() || !TypeList[Record[0]])
2492         return error("Invalid record");
2493       CurTy = TypeList[Record[0]];
2494       continue;  // Skip the ValueList manipulation.
2495     case bitc::CST_CODE_NULL:      // NULL
2496       V = Constant::getNullValue(CurTy);
2497       break;
2498     case bitc::CST_CODE_INTEGER:   // INTEGER: [intval]
2499       if (!CurTy->isIntegerTy() || Record.empty())
2500         return error("Invalid record");
2501       V = ConstantInt::get(CurTy, decodeSignRotatedValue(Record[0]));
2502       break;
2503     case bitc::CST_CODE_WIDE_INTEGER: {// WIDE_INTEGER: [n x intval]
2504       if (!CurTy->isIntegerTy() || Record.empty())
2505         return error("Invalid record");
2506
2507       APInt VInt =
2508           readWideAPInt(Record, cast<IntegerType>(CurTy)->getBitWidth());
2509       V = ConstantInt::get(Context, VInt);
2510
2511       break;
2512     }
2513     case bitc::CST_CODE_FLOAT: {    // FLOAT: [fpval]
2514       if (Record.empty())
2515         return error("Invalid record");
2516       if (CurTy->isHalfTy())
2517         V = ConstantFP::get(Context, APFloat(APFloat::IEEEhalf,
2518                                              APInt(16, (uint16_t)Record[0])));
2519       else if (CurTy->isFloatTy())
2520         V = ConstantFP::get(Context, APFloat(APFloat::IEEEsingle,
2521                                              APInt(32, (uint32_t)Record[0])));
2522       else if (CurTy->isDoubleTy())
2523         V = ConstantFP::get(Context, APFloat(APFloat::IEEEdouble,
2524                                              APInt(64, Record[0])));
2525       else if (CurTy->isX86_FP80Ty()) {
2526         // Bits are not stored the same way as a normal i80 APInt, compensate.
2527         uint64_t Rearrange[2];
2528         Rearrange[0] = (Record[1] & 0xffffLL) | (Record[0] << 16);
2529         Rearrange[1] = Record[0] >> 48;
2530         V = ConstantFP::get(Context, APFloat(APFloat::x87DoubleExtended,
2531                                              APInt(80, Rearrange)));
2532       } else if (CurTy->isFP128Ty())
2533         V = ConstantFP::get(Context, APFloat(APFloat::IEEEquad,
2534                                              APInt(128, Record)));
2535       else if (CurTy->isPPC_FP128Ty())
2536         V = ConstantFP::get(Context, APFloat(APFloat::PPCDoubleDouble,
2537                                              APInt(128, Record)));
2538       else
2539         V = UndefValue::get(CurTy);
2540       break;
2541     }
2542
2543     case bitc::CST_CODE_AGGREGATE: {// AGGREGATE: [n x value number]
2544       if (Record.empty())
2545         return error("Invalid record");
2546
2547       unsigned Size = Record.size();
2548       SmallVector<Constant*, 16> Elts;
2549
2550       if (StructType *STy = dyn_cast<StructType>(CurTy)) {
2551         for (unsigned i = 0; i != Size; ++i)
2552           Elts.push_back(ValueList.getConstantFwdRef(Record[i],
2553                                                      STy->getElementType(i)));
2554         V = ConstantStruct::get(STy, Elts);
2555       } else if (ArrayType *ATy = dyn_cast<ArrayType>(CurTy)) {
2556         Type *EltTy = ATy->getElementType();
2557         for (unsigned i = 0; i != Size; ++i)
2558           Elts.push_back(ValueList.getConstantFwdRef(Record[i], EltTy));
2559         V = ConstantArray::get(ATy, Elts);
2560       } else if (VectorType *VTy = dyn_cast<VectorType>(CurTy)) {
2561         Type *EltTy = VTy->getElementType();
2562         for (unsigned i = 0; i != Size; ++i)
2563           Elts.push_back(ValueList.getConstantFwdRef(Record[i], EltTy));
2564         V = ConstantVector::get(Elts);
2565       } else {
2566         V = UndefValue::get(CurTy);
2567       }
2568       break;
2569     }
2570     case bitc::CST_CODE_STRING:    // STRING: [values]
2571     case bitc::CST_CODE_CSTRING: { // CSTRING: [values]
2572       if (Record.empty())
2573         return error("Invalid record");
2574
2575       SmallString<16> Elts(Record.begin(), Record.end());
2576       V = ConstantDataArray::getString(Context, Elts,
2577                                        BitCode == bitc::CST_CODE_CSTRING);
2578       break;
2579     }
2580     case bitc::CST_CODE_DATA: {// DATA: [n x value]
2581       if (Record.empty())
2582         return error("Invalid record");
2583
2584       Type *EltTy = cast<SequentialType>(CurTy)->getElementType();
2585       unsigned Size = Record.size();
2586
2587       if (EltTy->isIntegerTy(8)) {
2588         SmallVector<uint8_t, 16> Elts(Record.begin(), Record.end());
2589         if (isa<VectorType>(CurTy))
2590           V = ConstantDataVector::get(Context, Elts);
2591         else
2592           V = ConstantDataArray::get(Context, Elts);
2593       } else if (EltTy->isIntegerTy(16)) {
2594         SmallVector<uint16_t, 16> Elts(Record.begin(), Record.end());
2595         if (isa<VectorType>(CurTy))
2596           V = ConstantDataVector::get(Context, Elts);
2597         else
2598           V = ConstantDataArray::get(Context, Elts);
2599       } else if (EltTy->isIntegerTy(32)) {
2600         SmallVector<uint32_t, 16> Elts(Record.begin(), Record.end());
2601         if (isa<VectorType>(CurTy))
2602           V = ConstantDataVector::get(Context, Elts);
2603         else
2604           V = ConstantDataArray::get(Context, Elts);
2605       } else if (EltTy->isIntegerTy(64)) {
2606         SmallVector<uint64_t, 16> Elts(Record.begin(), Record.end());
2607         if (isa<VectorType>(CurTy))
2608           V = ConstantDataVector::get(Context, Elts);
2609         else
2610           V = ConstantDataArray::get(Context, Elts);
2611       } else if (EltTy->isFloatTy()) {
2612         SmallVector<float, 16> Elts(Size);
2613         std::transform(Record.begin(), Record.end(), Elts.begin(), BitsToFloat);
2614         if (isa<VectorType>(CurTy))
2615           V = ConstantDataVector::get(Context, Elts);
2616         else
2617           V = ConstantDataArray::get(Context, Elts);
2618       } else if (EltTy->isDoubleTy()) {
2619         SmallVector<double, 16> Elts(Size);
2620         std::transform(Record.begin(), Record.end(), Elts.begin(),
2621                        BitsToDouble);
2622         if (isa<VectorType>(CurTy))
2623           V = ConstantDataVector::get(Context, Elts);
2624         else
2625           V = ConstantDataArray::get(Context, Elts);
2626       } else {
2627         return error("Invalid type for value");
2628       }
2629       break;
2630     }
2631
2632     case bitc::CST_CODE_CE_BINOP: {  // CE_BINOP: [opcode, opval, opval]
2633       if (Record.size() < 3)
2634         return error("Invalid record");
2635       int Opc = getDecodedBinaryOpcode(Record[0], CurTy);
2636       if (Opc < 0) {
2637         V = UndefValue::get(CurTy);  // Unknown binop.
2638       } else {
2639         Constant *LHS = ValueList.getConstantFwdRef(Record[1], CurTy);
2640         Constant *RHS = ValueList.getConstantFwdRef(Record[2], CurTy);
2641         unsigned Flags = 0;
2642         if (Record.size() >= 4) {
2643           if (Opc == Instruction::Add ||
2644               Opc == Instruction::Sub ||
2645               Opc == Instruction::Mul ||
2646               Opc == Instruction::Shl) {
2647             if (Record[3] & (1 << bitc::OBO_NO_SIGNED_WRAP))
2648               Flags |= OverflowingBinaryOperator::NoSignedWrap;
2649             if (Record[3] & (1 << bitc::OBO_NO_UNSIGNED_WRAP))
2650               Flags |= OverflowingBinaryOperator::NoUnsignedWrap;
2651           } else if (Opc == Instruction::SDiv ||
2652                      Opc == Instruction::UDiv ||
2653                      Opc == Instruction::LShr ||
2654                      Opc == Instruction::AShr) {
2655             if (Record[3] & (1 << bitc::PEO_EXACT))
2656               Flags |= SDivOperator::IsExact;
2657           }
2658         }
2659         V = ConstantExpr::get(Opc, LHS, RHS, Flags);
2660       }
2661       break;
2662     }
2663     case bitc::CST_CODE_CE_CAST: {  // CE_CAST: [opcode, opty, opval]
2664       if (Record.size() < 3)
2665         return error("Invalid record");
2666       int Opc = getDecodedCastOpcode(Record[0]);
2667       if (Opc < 0) {
2668         V = UndefValue::get(CurTy);  // Unknown cast.
2669       } else {
2670         Type *OpTy = getTypeByID(Record[1]);
2671         if (!OpTy)
2672           return error("Invalid record");
2673         Constant *Op = ValueList.getConstantFwdRef(Record[2], OpTy);
2674         V = UpgradeBitCastExpr(Opc, Op, CurTy);
2675         if (!V) V = ConstantExpr::getCast(Opc, Op, CurTy);
2676       }
2677       break;
2678     }
2679     case bitc::CST_CODE_CE_INBOUNDS_GEP:
2680     case bitc::CST_CODE_CE_GEP: {  // CE_GEP:        [n x operands]
2681       unsigned OpNum = 0;
2682       Type *PointeeType = nullptr;
2683       if (Record.size() % 2)
2684         PointeeType = getTypeByID(Record[OpNum++]);
2685       SmallVector<Constant*, 16> Elts;
2686       while (OpNum != Record.size()) {
2687         Type *ElTy = getTypeByID(Record[OpNum++]);
2688         if (!ElTy)
2689           return error("Invalid record");
2690         Elts.push_back(ValueList.getConstantFwdRef(Record[OpNum++], ElTy));
2691       }
2692
2693       if (PointeeType &&
2694           PointeeType !=
2695               cast<SequentialType>(Elts[0]->getType()->getScalarType())
2696                   ->getElementType())
2697         return error("Explicit gep operator type does not match pointee type "
2698                      "of pointer operand");
2699
2700       ArrayRef<Constant *> Indices(Elts.begin() + 1, Elts.end());
2701       V = ConstantExpr::getGetElementPtr(PointeeType, Elts[0], Indices,
2702                                          BitCode ==
2703                                              bitc::CST_CODE_CE_INBOUNDS_GEP);
2704       break;
2705     }
2706     case bitc::CST_CODE_CE_SELECT: {  // CE_SELECT: [opval#, opval#, opval#]
2707       if (Record.size() < 3)
2708         return error("Invalid record");
2709
2710       Type *SelectorTy = Type::getInt1Ty(Context);
2711
2712       // The selector might be an i1 or an <n x i1>
2713       // Get the type from the ValueList before getting a forward ref.
2714       if (VectorType *VTy = dyn_cast<VectorType>(CurTy))
2715         if (Value *V = ValueList[Record[0]])
2716           if (SelectorTy != V->getType())
2717             SelectorTy = VectorType::get(SelectorTy, VTy->getNumElements());
2718
2719       V = ConstantExpr::getSelect(ValueList.getConstantFwdRef(Record[0],
2720                                                               SelectorTy),
2721                                   ValueList.getConstantFwdRef(Record[1],CurTy),
2722                                   ValueList.getConstantFwdRef(Record[2],CurTy));
2723       break;
2724     }
2725     case bitc::CST_CODE_CE_EXTRACTELT
2726         : { // CE_EXTRACTELT: [opty, opval, opty, opval]
2727       if (Record.size() < 3)
2728         return error("Invalid record");
2729       VectorType *OpTy =
2730         dyn_cast_or_null<VectorType>(getTypeByID(Record[0]));
2731       if (!OpTy)
2732         return error("Invalid record");
2733       Constant *Op0 = ValueList.getConstantFwdRef(Record[1], OpTy);
2734       Constant *Op1 = nullptr;
2735       if (Record.size() == 4) {
2736         Type *IdxTy = getTypeByID(Record[2]);
2737         if (!IdxTy)
2738           return error("Invalid record");
2739         Op1 = ValueList.getConstantFwdRef(Record[3], IdxTy);
2740       } else // TODO: Remove with llvm 4.0
2741         Op1 = ValueList.getConstantFwdRef(Record[2], Type::getInt32Ty(Context));
2742       if (!Op1)
2743         return error("Invalid record");
2744       V = ConstantExpr::getExtractElement(Op0, Op1);
2745       break;
2746     }
2747     case bitc::CST_CODE_CE_INSERTELT
2748         : { // CE_INSERTELT: [opval, opval, opty, opval]
2749       VectorType *OpTy = dyn_cast<VectorType>(CurTy);
2750       if (Record.size() < 3 || !OpTy)
2751         return error("Invalid record");
2752       Constant *Op0 = ValueList.getConstantFwdRef(Record[0], OpTy);
2753       Constant *Op1 = ValueList.getConstantFwdRef(Record[1],
2754                                                   OpTy->getElementType());
2755       Constant *Op2 = nullptr;
2756       if (Record.size() == 4) {
2757         Type *IdxTy = getTypeByID(Record[2]);
2758         if (!IdxTy)
2759           return error("Invalid record");
2760         Op2 = ValueList.getConstantFwdRef(Record[3], IdxTy);
2761       } else // TODO: Remove with llvm 4.0
2762         Op2 = ValueList.getConstantFwdRef(Record[2], Type::getInt32Ty(Context));
2763       if (!Op2)
2764         return error("Invalid record");
2765       V = ConstantExpr::getInsertElement(Op0, Op1, Op2);
2766       break;
2767     }
2768     case bitc::CST_CODE_CE_SHUFFLEVEC: { // CE_SHUFFLEVEC: [opval, opval, opval]
2769       VectorType *OpTy = dyn_cast<VectorType>(CurTy);
2770       if (Record.size() < 3 || !OpTy)
2771         return error("Invalid record");
2772       Constant *Op0 = ValueList.getConstantFwdRef(Record[0], OpTy);
2773       Constant *Op1 = ValueList.getConstantFwdRef(Record[1], OpTy);
2774       Type *ShufTy = VectorType::get(Type::getInt32Ty(Context),
2775                                                  OpTy->getNumElements());
2776       Constant *Op2 = ValueList.getConstantFwdRef(Record[2], ShufTy);
2777       V = ConstantExpr::getShuffleVector(Op0, Op1, Op2);
2778       break;
2779     }
2780     case bitc::CST_CODE_CE_SHUFVEC_EX: { // [opty, opval, opval, opval]
2781       VectorType *RTy = dyn_cast<VectorType>(CurTy);
2782       VectorType *OpTy =
2783         dyn_cast_or_null<VectorType>(getTypeByID(Record[0]));
2784       if (Record.size() < 4 || !RTy || !OpTy)
2785         return error("Invalid record");
2786       Constant *Op0 = ValueList.getConstantFwdRef(Record[1], OpTy);
2787       Constant *Op1 = ValueList.getConstantFwdRef(Record[2], OpTy);
2788       Type *ShufTy = VectorType::get(Type::getInt32Ty(Context),
2789                                                  RTy->getNumElements());
2790       Constant *Op2 = ValueList.getConstantFwdRef(Record[3], ShufTy);
2791       V = ConstantExpr::getShuffleVector(Op0, Op1, Op2);
2792       break;
2793     }
2794     case bitc::CST_CODE_CE_CMP: {     // CE_CMP: [opty, opval, opval, pred]
2795       if (Record.size() < 4)
2796         return error("Invalid record");
2797       Type *OpTy = getTypeByID(Record[0]);
2798       if (!OpTy)
2799         return error("Invalid record");
2800       Constant *Op0 = ValueList.getConstantFwdRef(Record[1], OpTy);
2801       Constant *Op1 = ValueList.getConstantFwdRef(Record[2], OpTy);
2802
2803       if (OpTy->isFPOrFPVectorTy())
2804         V = ConstantExpr::getFCmp(Record[3], Op0, Op1);
2805       else
2806         V = ConstantExpr::getICmp(Record[3], Op0, Op1);
2807       break;
2808     }
2809     // This maintains backward compatibility, pre-asm dialect keywords.
2810     // FIXME: Remove with the 4.0 release.
2811     case bitc::CST_CODE_INLINEASM_OLD: {
2812       if (Record.size() < 2)
2813         return error("Invalid record");
2814       std::string AsmStr, ConstrStr;
2815       bool HasSideEffects = Record[0] & 1;
2816       bool IsAlignStack = Record[0] >> 1;
2817       unsigned AsmStrSize = Record[1];
2818       if (2+AsmStrSize >= Record.size())
2819         return error("Invalid record");
2820       unsigned ConstStrSize = Record[2+AsmStrSize];
2821       if (3+AsmStrSize+ConstStrSize > Record.size())
2822         return error("Invalid record");
2823
2824       for (unsigned i = 0; i != AsmStrSize; ++i)
2825         AsmStr += (char)Record[2+i];
2826       for (unsigned i = 0; i != ConstStrSize; ++i)
2827         ConstrStr += (char)Record[3+AsmStrSize+i];
2828       PointerType *PTy = cast<PointerType>(CurTy);
2829       V = InlineAsm::get(cast<FunctionType>(PTy->getElementType()),
2830                          AsmStr, ConstrStr, HasSideEffects, IsAlignStack);
2831       break;
2832     }
2833     // This version adds support for the asm dialect keywords (e.g.,
2834     // inteldialect).
2835     case bitc::CST_CODE_INLINEASM: {
2836       if (Record.size() < 2)
2837         return error("Invalid record");
2838       std::string AsmStr, ConstrStr;
2839       bool HasSideEffects = Record[0] & 1;
2840       bool IsAlignStack = (Record[0] >> 1) & 1;
2841       unsigned AsmDialect = Record[0] >> 2;
2842       unsigned AsmStrSize = Record[1];
2843       if (2+AsmStrSize >= Record.size())
2844         return error("Invalid record");
2845       unsigned ConstStrSize = Record[2+AsmStrSize];
2846       if (3+AsmStrSize+ConstStrSize > Record.size())
2847         return error("Invalid record");
2848
2849       for (unsigned i = 0; i != AsmStrSize; ++i)
2850         AsmStr += (char)Record[2+i];
2851       for (unsigned i = 0; i != ConstStrSize; ++i)
2852         ConstrStr += (char)Record[3+AsmStrSize+i];
2853       PointerType *PTy = cast<PointerType>(CurTy);
2854       V = InlineAsm::get(cast<FunctionType>(PTy->getElementType()),
2855                          AsmStr, ConstrStr, HasSideEffects, IsAlignStack,
2856                          InlineAsm::AsmDialect(AsmDialect));
2857       break;
2858     }
2859     case bitc::CST_CODE_BLOCKADDRESS:{
2860       if (Record.size() < 3)
2861         return error("Invalid record");
2862       Type *FnTy = getTypeByID(Record[0]);
2863       if (!FnTy)
2864         return error("Invalid record");
2865       Function *Fn =
2866         dyn_cast_or_null<Function>(ValueList.getConstantFwdRef(Record[1],FnTy));
2867       if (!Fn)
2868         return error("Invalid record");
2869
2870       // Don't let Fn get dematerialized.
2871       BlockAddressesTaken.insert(Fn);
2872
2873       // If the function is already parsed we can insert the block address right
2874       // away.
2875       BasicBlock *BB;
2876       unsigned BBID = Record[2];
2877       if (!BBID)
2878         // Invalid reference to entry block.
2879         return error("Invalid ID");
2880       if (!Fn->empty()) {
2881         Function::iterator BBI = Fn->begin(), BBE = Fn->end();
2882         for (size_t I = 0, E = BBID; I != E; ++I) {
2883           if (BBI == BBE)
2884             return error("Invalid ID");
2885           ++BBI;
2886         }
2887         BB = &*BBI;
2888       } else {
2889         // Otherwise insert a placeholder and remember it so it can be inserted
2890         // when the function is parsed.
2891         auto &FwdBBs = BasicBlockFwdRefs[Fn];
2892         if (FwdBBs.empty())
2893           BasicBlockFwdRefQueue.push_back(Fn);
2894         if (FwdBBs.size() < BBID + 1)
2895           FwdBBs.resize(BBID + 1);
2896         if (!FwdBBs[BBID])
2897           FwdBBs[BBID] = BasicBlock::Create(Context);
2898         BB = FwdBBs[BBID];
2899       }
2900       V = BlockAddress::get(Fn, BB);
2901       break;
2902     }
2903     }
2904
2905     if (ValueList.assignValue(V, NextCstNo))
2906       return error("Invalid forward reference");
2907     ++NextCstNo;
2908   }
2909 }
2910
2911 std::error_code BitcodeReader::parseUseLists() {
2912   if (Stream.EnterSubBlock(bitc::USELIST_BLOCK_ID))
2913     return error("Invalid record");
2914
2915   // Read all the records.
2916   SmallVector<uint64_t, 64> Record;
2917   while (1) {
2918     BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
2919
2920     switch (Entry.Kind) {
2921     case BitstreamEntry::SubBlock: // Handled for us already.
2922     case BitstreamEntry::Error:
2923       return error("Malformed block");
2924     case BitstreamEntry::EndBlock:
2925       return std::error_code();
2926     case BitstreamEntry::Record:
2927       // The interesting case.
2928       break;
2929     }
2930
2931     // Read a use list record.
2932     Record.clear();
2933     bool IsBB = false;
2934     switch (Stream.readRecord(Entry.ID, Record)) {
2935     default:  // Default behavior: unknown type.
2936       break;
2937     case bitc::USELIST_CODE_BB:
2938       IsBB = true;
2939       // fallthrough
2940     case bitc::USELIST_CODE_DEFAULT: {
2941       unsigned RecordLength = Record.size();
2942       if (RecordLength < 3)
2943         // Records should have at least an ID and two indexes.
2944         return error("Invalid record");
2945       unsigned ID = Record.back();
2946       Record.pop_back();
2947
2948       Value *V;
2949       if (IsBB) {
2950         assert(ID < FunctionBBs.size() && "Basic block not found");
2951         V = FunctionBBs[ID];
2952       } else
2953         V = ValueList[ID];
2954       unsigned NumUses = 0;
2955       SmallDenseMap<const Use *, unsigned, 16> Order;
2956       for (const Use &U : V->uses()) {
2957         if (++NumUses > Record.size())
2958           break;
2959         Order[&U] = Record[NumUses - 1];
2960       }
2961       if (Order.size() != Record.size() || NumUses > Record.size())
2962         // Mismatches can happen if the functions are being materialized lazily
2963         // (out-of-order), or a value has been upgraded.
2964         break;
2965
2966       V->sortUseList([&](const Use &L, const Use &R) {
2967         return Order.lookup(&L) < Order.lookup(&R);
2968       });
2969       break;
2970     }
2971     }
2972   }
2973 }
2974
2975 /// When we see the block for metadata, remember where it is and then skip it.
2976 /// This lets us lazily deserialize the metadata.
2977 std::error_code BitcodeReader::rememberAndSkipMetadata() {
2978   // Save the current stream state.
2979   uint64_t CurBit = Stream.GetCurrentBitNo();
2980   DeferredMetadataInfo.push_back(CurBit);
2981
2982   // Skip over the block for now.
2983   if (Stream.SkipBlock())
2984     return error("Invalid record");
2985   return std::error_code();
2986 }
2987
2988 std::error_code BitcodeReader::materializeMetadata() {
2989   for (uint64_t BitPos : DeferredMetadataInfo) {
2990     // Move the bit stream to the saved position.
2991     Stream.JumpToBit(BitPos);
2992     if (std::error_code EC = parseMetadata())
2993       return EC;
2994   }
2995   DeferredMetadataInfo.clear();
2996   return std::error_code();
2997 }
2998
2999 void BitcodeReader::setStripDebugInfo() { StripDebugInfo = true; }
3000
3001 /// When we see the block for a function body, remember where it is and then
3002 /// skip it.  This lets us lazily deserialize the functions.
3003 std::error_code BitcodeReader::rememberAndSkipFunctionBody() {
3004   // Get the function we are talking about.
3005   if (FunctionsWithBodies.empty())
3006     return error("Insufficient function protos");
3007
3008   Function *Fn = FunctionsWithBodies.back();
3009   FunctionsWithBodies.pop_back();
3010
3011   // Save the current stream state.
3012   uint64_t CurBit = Stream.GetCurrentBitNo();
3013   assert(
3014       (DeferredFunctionInfo[Fn] == 0 || DeferredFunctionInfo[Fn] == CurBit) &&
3015       "Mismatch between VST and scanned function offsets");
3016   DeferredFunctionInfo[Fn] = CurBit;
3017
3018   // Skip over the function block for now.
3019   if (Stream.SkipBlock())
3020     return error("Invalid record");
3021   return std::error_code();
3022 }
3023
3024 std::error_code BitcodeReader::globalCleanup() {
3025   // Patch the initializers for globals and aliases up.
3026   resolveGlobalAndAliasInits();
3027   if (!GlobalInits.empty() || !AliasInits.empty())
3028     return error("Malformed global initializer set");
3029
3030   // Look for intrinsic functions which need to be upgraded at some point
3031   for (Function &F : *TheModule) {
3032     Function *NewFn;
3033     if (UpgradeIntrinsicFunction(&F, NewFn))
3034       UpgradedIntrinsics[&F] = NewFn;
3035   }
3036
3037   // Look for global variables which need to be renamed.
3038   for (GlobalVariable &GV : TheModule->globals())
3039     UpgradeGlobalVariable(&GV);
3040
3041   // Force deallocation of memory for these vectors to favor the client that
3042   // want lazy deserialization.
3043   std::vector<std::pair<GlobalVariable*, unsigned> >().swap(GlobalInits);
3044   std::vector<std::pair<GlobalAlias*, unsigned> >().swap(AliasInits);
3045   return std::error_code();
3046 }
3047
3048 /// Support for lazy parsing of function bodies. This is required if we
3049 /// either have an old bitcode file without a VST forward declaration record,
3050 /// or if we have an anonymous function being materialized, since anonymous
3051 /// functions do not have a name and are therefore not in the VST.
3052 std::error_code BitcodeReader::rememberAndSkipFunctionBodies() {
3053   Stream.JumpToBit(NextUnreadBit);
3054
3055   if (Stream.AtEndOfStream()) return error("Could not find function in stream");
3056
3057   assert(SeenFirstFunctionBody);
3058   // An old bitcode file with the symbol table at the end would have
3059   // finished the parse greedily.
3060   assert(SeenValueSymbolTable);
3061
3062   SmallVector<uint64_t, 64> Record;
3063
3064   while (1) {
3065     BitstreamEntry Entry = Stream.advance();
3066     switch (Entry.Kind) {
3067       default:
3068         return error("Expect SubBlock");
3069       case BitstreamEntry::SubBlock:
3070         switch (Entry.ID) {
3071           default:
3072             return error("Expect function block");
3073           case bitc::FUNCTION_BLOCK_ID:
3074             if (std::error_code EC = rememberAndSkipFunctionBody()) return EC;
3075             NextUnreadBit = Stream.GetCurrentBitNo();
3076             return std::error_code();
3077         }
3078     }
3079   }
3080 }
3081
3082 std::error_code BitcodeReader::parseBitcodeVersion() {
3083   if (Stream.EnterSubBlock(bitc::IDENTIFICATION_BLOCK_ID))
3084     return error("Invalid record");
3085
3086   // Read all the records.
3087   SmallVector<uint64_t, 64> Record;
3088   while (1) {
3089     BitstreamEntry Entry = Stream.advance();
3090
3091     switch (Entry.Kind) {
3092     default:
3093     case BitstreamEntry::Error:
3094       return error("Malformed block");
3095     case BitstreamEntry::EndBlock:
3096       return std::error_code();
3097     case BitstreamEntry::Record:
3098       // The interesting case.
3099       break;
3100     }
3101
3102     // Read a record.
3103     Record.clear();
3104     unsigned BitCode = Stream.readRecord(Entry.ID, Record);
3105     switch (BitCode) {
3106     default: // Default behavior: reject
3107       return error("Invalid value");
3108     case bitc::IDENTIFICATION_CODE_STRING: { // IDENTIFICATION:      [strchr x
3109                                              // N]
3110       convertToString(Record, 0, ProducerIdentification);
3111       break;
3112     }
3113     case bitc::IDENTIFICATION_CODE_EPOCH: { // EPOCH:      [epoch#]
3114       unsigned epoch = (unsigned)Record[0];
3115       if (epoch != bitc::BITCODE_CURRENT_EPOCH) {
3116         return error(
3117           Twine("Incompatible epoch: Bitcode '") + Twine(epoch) +
3118           "' vs current: '" + Twine(bitc::BITCODE_CURRENT_EPOCH) + "'");
3119       }
3120     }
3121     }
3122   }
3123 }
3124
3125 std::error_code BitcodeReader::parseModule(uint64_t ResumeBit,
3126                                            bool ShouldLazyLoadMetadata) {
3127   if (ResumeBit)
3128     Stream.JumpToBit(ResumeBit);
3129   else if (Stream.EnterSubBlock(bitc::MODULE_BLOCK_ID))
3130     return error("Invalid record");
3131
3132   SmallVector<uint64_t, 64> Record;
3133   std::vector<std::string> SectionTable;
3134   std::vector<std::string> GCTable;
3135
3136   // Read all the records for this module.
3137   while (1) {
3138     BitstreamEntry Entry = Stream.advance();
3139
3140     switch (Entry.Kind) {
3141     case BitstreamEntry::Error:
3142       return error("Malformed block");
3143     case BitstreamEntry::EndBlock:
3144       return globalCleanup();
3145
3146     case BitstreamEntry::SubBlock:
3147       switch (Entry.ID) {
3148       default:  // Skip unknown content.
3149         if (Stream.SkipBlock())
3150           return error("Invalid record");
3151         break;
3152       case bitc::BLOCKINFO_BLOCK_ID:
3153         if (Stream.ReadBlockInfoBlock())
3154           return error("Malformed block");
3155         break;
3156       case bitc::PARAMATTR_BLOCK_ID:
3157         if (std::error_code EC = parseAttributeBlock())
3158           return EC;
3159         break;
3160       case bitc::PARAMATTR_GROUP_BLOCK_ID:
3161         if (std::error_code EC = parseAttributeGroupBlock())
3162           return EC;
3163         break;
3164       case bitc::TYPE_BLOCK_ID_NEW:
3165         if (std::error_code EC = parseTypeTable())
3166           return EC;
3167         break;
3168       case bitc::VALUE_SYMTAB_BLOCK_ID:
3169         if (!SeenValueSymbolTable) {
3170           // Either this is an old form VST without function index and an
3171           // associated VST forward declaration record (which would have caused
3172           // the VST to be jumped to and parsed before it was encountered
3173           // normally in the stream), or there were no function blocks to
3174           // trigger an earlier parsing of the VST.
3175           assert(VSTOffset == 0 || FunctionsWithBodies.empty());
3176           if (std::error_code EC = parseValueSymbolTable())
3177             return EC;
3178           SeenValueSymbolTable = true;
3179         } else {
3180           // We must have had a VST forward declaration record, which caused
3181           // the parser to jump to and parse the VST earlier.
3182           assert(VSTOffset > 0);
3183           if (Stream.SkipBlock())
3184             return error("Invalid record");
3185         }
3186         break;
3187       case bitc::CONSTANTS_BLOCK_ID:
3188         if (std::error_code EC = parseConstants())
3189           return EC;
3190         if (std::error_code EC = resolveGlobalAndAliasInits())
3191           return EC;
3192         break;
3193       case bitc::METADATA_BLOCK_ID:
3194         if (ShouldLazyLoadMetadata && !IsMetadataMaterialized) {
3195           if (std::error_code EC = rememberAndSkipMetadata())
3196             return EC;
3197           break;
3198         }
3199         assert(DeferredMetadataInfo.empty() && "Unexpected deferred metadata");
3200         if (std::error_code EC = parseMetadata())
3201           return EC;
3202         break;
3203       case bitc::FUNCTION_BLOCK_ID:
3204         // If this is the first function body we've seen, reverse the
3205         // FunctionsWithBodies list.
3206         if (!SeenFirstFunctionBody) {
3207           std::reverse(FunctionsWithBodies.begin(), FunctionsWithBodies.end());
3208           if (std::error_code EC = globalCleanup())
3209             return EC;
3210           SeenFirstFunctionBody = true;
3211         }
3212
3213         if (VSTOffset > 0) {
3214           // If we have a VST forward declaration record, make sure we
3215           // parse the VST now if we haven't already. It is needed to
3216           // set up the DeferredFunctionInfo vector for lazy reading.
3217           if (!SeenValueSymbolTable) {
3218             if (std::error_code EC =
3219                     BitcodeReader::parseValueSymbolTable(VSTOffset))
3220               return EC;
3221             SeenValueSymbolTable = true;
3222             // Fall through so that we record the NextUnreadBit below.
3223             // This is necessary in case we have an anonymous function that
3224             // is later materialized. Since it will not have a VST entry we
3225             // need to fall back to the lazy parse to find its offset.
3226           } else {
3227             // If we have a VST forward declaration record, but have already
3228             // parsed the VST (just above, when the first function body was
3229             // encountered here), then we are resuming the parse after
3230             // materializing functions. The ResumeBit points to the
3231             // start of the last function block recorded in the
3232             // DeferredFunctionInfo map. Skip it.
3233             if (Stream.SkipBlock())
3234               return error("Invalid record");
3235             continue;
3236           }
3237         }
3238
3239         // Support older bitcode files that did not have the function
3240         // index in the VST, nor a VST forward declaration record, as
3241         // well as anonymous functions that do not have VST entries.
3242         // Build the DeferredFunctionInfo vector on the fly.
3243         if (std::error_code EC = rememberAndSkipFunctionBody())
3244           return EC;
3245
3246         // Suspend parsing when we reach the function bodies. Subsequent
3247         // materialization calls will resume it when necessary. If the bitcode
3248         // file is old, the symbol table will be at the end instead and will not
3249         // have been seen yet. In this case, just finish the parse now.
3250         if (SeenValueSymbolTable) {
3251           NextUnreadBit = Stream.GetCurrentBitNo();
3252           return std::error_code();
3253         }
3254         break;
3255       case bitc::USELIST_BLOCK_ID:
3256         if (std::error_code EC = parseUseLists())
3257           return EC;
3258         break;
3259       case bitc::OPERAND_BUNDLE_TAGS_BLOCK_ID:
3260         if (std::error_code EC = parseOperandBundleTags())
3261           return EC;
3262         break;
3263       }
3264       continue;
3265
3266     case BitstreamEntry::Record:
3267       // The interesting case.
3268       break;
3269     }
3270
3271
3272     // Read a record.
3273     auto BitCode = Stream.readRecord(Entry.ID, Record);
3274     switch (BitCode) {
3275     default: break;  // Default behavior, ignore unknown content.
3276     case bitc::MODULE_CODE_VERSION: {  // VERSION: [version#]
3277       if (Record.size() < 1)
3278         return error("Invalid record");
3279       // Only version #0 and #1 are supported so far.
3280       unsigned module_version = Record[0];
3281       switch (module_version) {
3282         default:
3283           return error("Invalid value");
3284         case 0:
3285           UseRelativeIDs = false;
3286           break;
3287         case 1:
3288           UseRelativeIDs = true;
3289           break;
3290       }
3291       break;
3292     }
3293     case bitc::MODULE_CODE_TRIPLE: {  // TRIPLE: [strchr x N]
3294       std::string S;
3295       if (convertToString(Record, 0, S))
3296         return error("Invalid record");
3297       TheModule->setTargetTriple(S);
3298       break;
3299     }
3300     case bitc::MODULE_CODE_DATALAYOUT: {  // DATALAYOUT: [strchr x N]
3301       std::string S;
3302       if (convertToString(Record, 0, S))
3303         return error("Invalid record");
3304       TheModule->setDataLayout(S);
3305       break;
3306     }
3307     case bitc::MODULE_CODE_ASM: {  // ASM: [strchr x N]
3308       std::string S;
3309       if (convertToString(Record, 0, S))
3310         return error("Invalid record");
3311       TheModule->setModuleInlineAsm(S);
3312       break;
3313     }
3314     case bitc::MODULE_CODE_DEPLIB: {  // DEPLIB: [strchr x N]
3315       // FIXME: Remove in 4.0.
3316       std::string S;
3317       if (convertToString(Record, 0, S))
3318         return error("Invalid record");
3319       // Ignore value.
3320       break;
3321     }
3322     case bitc::MODULE_CODE_SECTIONNAME: {  // SECTIONNAME: [strchr x N]
3323       std::string S;
3324       if (convertToString(Record, 0, S))
3325         return error("Invalid record");
3326       SectionTable.push_back(S);
3327       break;
3328     }
3329     case bitc::MODULE_CODE_GCNAME: {  // SECTIONNAME: [strchr x N]
3330       std::string S;
3331       if (convertToString(Record, 0, S))
3332         return error("Invalid record");
3333       GCTable.push_back(S);
3334       break;
3335     }
3336     case bitc::MODULE_CODE_COMDAT: { // COMDAT: [selection_kind, name]
3337       if (Record.size() < 2)
3338         return error("Invalid record");
3339       Comdat::SelectionKind SK = getDecodedComdatSelectionKind(Record[0]);
3340       unsigned ComdatNameSize = Record[1];
3341       std::string ComdatName;
3342       ComdatName.reserve(ComdatNameSize);
3343       for (unsigned i = 0; i != ComdatNameSize; ++i)
3344         ComdatName += (char)Record[2 + i];
3345       Comdat *C = TheModule->getOrInsertComdat(ComdatName);
3346       C->setSelectionKind(SK);
3347       ComdatList.push_back(C);
3348       break;
3349     }
3350     // GLOBALVAR: [pointer type, isconst, initid,
3351     //             linkage, alignment, section, visibility, threadlocal,
3352     //             unnamed_addr, externally_initialized, dllstorageclass,
3353     //             comdat]
3354     case bitc::MODULE_CODE_GLOBALVAR: {
3355       if (Record.size() < 6)
3356         return error("Invalid record");
3357       Type *Ty = getTypeByID(Record[0]);
3358       if (!Ty)
3359         return error("Invalid record");
3360       bool isConstant = Record[1] & 1;
3361       bool explicitType = Record[1] & 2;
3362       unsigned AddressSpace;
3363       if (explicitType) {
3364         AddressSpace = Record[1] >> 2;
3365       } else {
3366         if (!Ty->isPointerTy())
3367           return error("Invalid type for value");
3368         AddressSpace = cast<PointerType>(Ty)->getAddressSpace();
3369         Ty = cast<PointerType>(Ty)->getElementType();
3370       }
3371
3372       uint64_t RawLinkage = Record[3];
3373       GlobalValue::LinkageTypes Linkage = getDecodedLinkage(RawLinkage);
3374       unsigned Alignment;
3375       if (std::error_code EC = parseAlignmentValue(Record[4], Alignment))
3376         return EC;
3377       std::string Section;
3378       if (Record[5]) {
3379         if (Record[5]-1 >= SectionTable.size())
3380           return error("Invalid ID");
3381         Section = SectionTable[Record[5]-1];
3382       }
3383       GlobalValue::VisibilityTypes Visibility = GlobalValue::DefaultVisibility;
3384       // Local linkage must have default visibility.
3385       if (Record.size() > 6 && !GlobalValue::isLocalLinkage(Linkage))
3386         // FIXME: Change to an error if non-default in 4.0.
3387         Visibility = getDecodedVisibility(Record[6]);
3388
3389       GlobalVariable::ThreadLocalMode TLM = GlobalVariable::NotThreadLocal;
3390       if (Record.size() > 7)
3391         TLM = getDecodedThreadLocalMode(Record[7]);
3392
3393       bool UnnamedAddr = false;
3394       if (Record.size() > 8)
3395         UnnamedAddr = Record[8];
3396
3397       bool ExternallyInitialized = false;
3398       if (Record.size() > 9)
3399         ExternallyInitialized = Record[9];
3400
3401       GlobalVariable *NewGV =
3402         new GlobalVariable(*TheModule, Ty, isConstant, Linkage, nullptr, "", nullptr,
3403                            TLM, AddressSpace, ExternallyInitialized);
3404       NewGV->setAlignment(Alignment);
3405       if (!Section.empty())
3406         NewGV->setSection(Section);
3407       NewGV->setVisibility(Visibility);
3408       NewGV->setUnnamedAddr(UnnamedAddr);
3409
3410       if (Record.size() > 10)
3411         NewGV->setDLLStorageClass(getDecodedDLLStorageClass(Record[10]));
3412       else
3413         upgradeDLLImportExportLinkage(NewGV, RawLinkage);
3414
3415       ValueList.push_back(NewGV);
3416
3417       // Remember which value to use for the global initializer.
3418       if (unsigned InitID = Record[2])
3419         GlobalInits.push_back(std::make_pair(NewGV, InitID-1));
3420
3421       if (Record.size() > 11) {
3422         if (unsigned ComdatID = Record[11]) {
3423           if (ComdatID > ComdatList.size())
3424             return error("Invalid global variable comdat ID");
3425           NewGV->setComdat(ComdatList[ComdatID - 1]);
3426         }
3427       } else if (hasImplicitComdat(RawLinkage)) {
3428         NewGV->setComdat(reinterpret_cast<Comdat *>(1));
3429       }
3430       break;
3431     }
3432     // FUNCTION:  [type, callingconv, isproto, linkage, paramattr,
3433     //             alignment, section, visibility, gc, unnamed_addr,
3434     //             prologuedata, dllstorageclass, comdat, prefixdata]
3435     case bitc::MODULE_CODE_FUNCTION: {
3436       if (Record.size() < 8)
3437         return error("Invalid record");
3438       Type *Ty = getTypeByID(Record[0]);
3439       if (!Ty)
3440         return error("Invalid record");
3441       if (auto *PTy = dyn_cast<PointerType>(Ty))
3442         Ty = PTy->getElementType();
3443       auto *FTy = dyn_cast<FunctionType>(Ty);
3444       if (!FTy)
3445         return error("Invalid type for value");
3446
3447       Function *Func = Function::Create(FTy, GlobalValue::ExternalLinkage,
3448                                         "", TheModule);
3449
3450       Func->setCallingConv(static_cast<CallingConv::ID>(Record[1]));
3451       bool isProto = Record[2];
3452       uint64_t RawLinkage = Record[3];
3453       Func->setLinkage(getDecodedLinkage(RawLinkage));
3454       Func->setAttributes(getAttributes(Record[4]));
3455
3456       unsigned Alignment;
3457       if (std::error_code EC = parseAlignmentValue(Record[5], Alignment))
3458         return EC;
3459       Func->setAlignment(Alignment);
3460       if (Record[6]) {
3461         if (Record[6]-1 >= SectionTable.size())
3462           return error("Invalid ID");
3463         Func->setSection(SectionTable[Record[6]-1]);
3464       }
3465       // Local linkage must have default visibility.
3466       if (!Func->hasLocalLinkage())
3467         // FIXME: Change to an error if non-default in 4.0.
3468         Func->setVisibility(getDecodedVisibility(Record[7]));
3469       if (Record.size() > 8 && Record[8]) {
3470         if (Record[8]-1 >= GCTable.size())
3471           return error("Invalid ID");
3472         Func->setGC(GCTable[Record[8]-1].c_str());
3473       }
3474       bool UnnamedAddr = false;
3475       if (Record.size() > 9)
3476         UnnamedAddr = Record[9];
3477       Func->setUnnamedAddr(UnnamedAddr);
3478       if (Record.size() > 10 && Record[10] != 0)
3479         FunctionPrologues.push_back(std::make_pair(Func, Record[10]-1));
3480
3481       if (Record.size() > 11)
3482         Func->setDLLStorageClass(getDecodedDLLStorageClass(Record[11]));
3483       else
3484         upgradeDLLImportExportLinkage(Func, RawLinkage);
3485
3486       if (Record.size() > 12) {
3487         if (unsigned ComdatID = Record[12]) {
3488           if (ComdatID > ComdatList.size())
3489             return error("Invalid function comdat ID");
3490           Func->setComdat(ComdatList[ComdatID - 1]);
3491         }
3492       } else if (hasImplicitComdat(RawLinkage)) {
3493         Func->setComdat(reinterpret_cast<Comdat *>(1));
3494       }
3495
3496       if (Record.size() > 13 && Record[13] != 0)
3497         FunctionPrefixes.push_back(std::make_pair(Func, Record[13]-1));
3498
3499       if (Record.size() > 14 && Record[14] != 0)
3500         FunctionPersonalityFns.push_back(std::make_pair(Func, Record[14] - 1));
3501
3502       ValueList.push_back(Func);
3503
3504       // If this is a function with a body, remember the prototype we are
3505       // creating now, so that we can match up the body with them later.
3506       if (!isProto) {
3507         Func->setIsMaterializable(true);
3508         FunctionsWithBodies.push_back(Func);
3509         DeferredFunctionInfo[Func] = 0;
3510       }
3511       break;
3512     }
3513     // ALIAS: [alias type, addrspace, aliasee val#, linkage]
3514     // ALIAS: [alias type, addrspace, aliasee val#, linkage, visibility, dllstorageclass]
3515     case bitc::MODULE_CODE_ALIAS:
3516     case bitc::MODULE_CODE_ALIAS_OLD: {
3517       bool NewRecord = BitCode == bitc::MODULE_CODE_ALIAS;
3518       if (Record.size() < (3 + (unsigned)NewRecord))
3519         return error("Invalid record");
3520       unsigned OpNum = 0;
3521       Type *Ty = getTypeByID(Record[OpNum++]);
3522       if (!Ty)
3523         return error("Invalid record");
3524
3525       unsigned AddrSpace;
3526       if (!NewRecord) {
3527         auto *PTy = dyn_cast<PointerType>(Ty);
3528         if (!PTy)
3529           return error("Invalid type for value");
3530         Ty = PTy->getElementType();
3531         AddrSpace = PTy->getAddressSpace();
3532       } else {
3533         AddrSpace = Record[OpNum++];
3534       }
3535
3536       auto Val = Record[OpNum++];
3537       auto Linkage = Record[OpNum++];
3538       auto *NewGA = GlobalAlias::create(
3539           Ty, AddrSpace, getDecodedLinkage(Linkage), "", TheModule);
3540       // Old bitcode files didn't have visibility field.
3541       // Local linkage must have default visibility.
3542       if (OpNum != Record.size()) {
3543         auto VisInd = OpNum++;
3544         if (!NewGA->hasLocalLinkage())
3545           // FIXME: Change to an error if non-default in 4.0.
3546           NewGA->setVisibility(getDecodedVisibility(Record[VisInd]));
3547       }
3548       if (OpNum != Record.size())
3549         NewGA->setDLLStorageClass(getDecodedDLLStorageClass(Record[OpNum++]));
3550       else
3551         upgradeDLLImportExportLinkage(NewGA, Linkage);
3552       if (OpNum != Record.size())
3553         NewGA->setThreadLocalMode(getDecodedThreadLocalMode(Record[OpNum++]));
3554       if (OpNum != Record.size())
3555         NewGA->setUnnamedAddr(Record[OpNum++]);
3556       ValueList.push_back(NewGA);
3557       AliasInits.push_back(std::make_pair(NewGA, Val));
3558       break;
3559     }
3560     /// MODULE_CODE_PURGEVALS: [numvals]
3561     case bitc::MODULE_CODE_PURGEVALS:
3562       // Trim down the value list to the specified size.
3563       if (Record.size() < 1 || Record[0] > ValueList.size())
3564         return error("Invalid record");
3565       ValueList.shrinkTo(Record[0]);
3566       break;
3567     /// MODULE_CODE_VSTOFFSET: [offset]
3568     case bitc::MODULE_CODE_VSTOFFSET:
3569       if (Record.size() < 1)
3570         return error("Invalid record");
3571       VSTOffset = Record[0];
3572       break;
3573     }
3574     Record.clear();
3575   }
3576 }
3577
3578 /// Helper to read the header common to all bitcode files.
3579 static bool hasValidBitcodeHeader(BitstreamCursor &Stream) {
3580   // Sniff for the signature.
3581   if (Stream.Read(8) != 'B' ||
3582       Stream.Read(8) != 'C' ||
3583       Stream.Read(4) != 0x0 ||
3584       Stream.Read(4) != 0xC ||
3585       Stream.Read(4) != 0xE ||
3586       Stream.Read(4) != 0xD)
3587     return false;
3588   return true;
3589 }
3590
3591 std::error_code
3592 BitcodeReader::parseBitcodeInto(std::unique_ptr<DataStreamer> Streamer,
3593                                 Module *M, bool ShouldLazyLoadMetadata) {
3594   TheModule = M;
3595
3596   if (std::error_code EC = initStream(std::move(Streamer)))
3597     return EC;
3598
3599   // Sniff for the signature.
3600   if (!hasValidBitcodeHeader(Stream)) return error("Invalid bitcode signature");
3601
3602   // We expect a number of well-defined blocks, though we don't necessarily
3603   // need to understand them all.
3604   while (1) {
3605     if (Stream.AtEndOfStream()) {
3606       // We didn't really read a proper Module.
3607       return error("Malformed IR file");
3608     }
3609
3610     BitstreamEntry Entry =
3611       Stream.advance(BitstreamCursor::AF_DontAutoprocessAbbrevs);
3612
3613     if (Entry.Kind != BitstreamEntry::SubBlock)
3614       return error("Malformed block");
3615
3616     if (Entry.ID == bitc::IDENTIFICATION_BLOCK_ID) {
3617       parseBitcodeVersion();
3618       continue;
3619     }
3620
3621     if (Entry.ID == bitc::MODULE_BLOCK_ID)
3622       return parseModule(0, ShouldLazyLoadMetadata);
3623
3624     if (Stream.SkipBlock())
3625       return error("Invalid record");
3626   }
3627 }
3628
3629 ErrorOr<std::string> BitcodeReader::parseModuleTriple() {
3630   if (Stream.EnterSubBlock(bitc::MODULE_BLOCK_ID))
3631     return error("Invalid record");
3632
3633   SmallVector<uint64_t, 64> Record;
3634
3635   std::string Triple;
3636   // Read all the records for this module.
3637   while (1) {
3638     BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
3639
3640     switch (Entry.Kind) {
3641     case BitstreamEntry::SubBlock: // Handled for us already.
3642     case BitstreamEntry::Error:
3643       return error("Malformed block");
3644     case BitstreamEntry::EndBlock:
3645       return Triple;
3646     case BitstreamEntry::Record:
3647       // The interesting case.
3648       break;
3649     }
3650
3651     // Read a record.
3652     switch (Stream.readRecord(Entry.ID, Record)) {
3653     default: break;  // Default behavior, ignore unknown content.
3654     case bitc::MODULE_CODE_TRIPLE: {  // TRIPLE: [strchr x N]
3655       std::string S;
3656       if (convertToString(Record, 0, S))
3657         return error("Invalid record");
3658       Triple = S;
3659       break;
3660     }
3661     }
3662     Record.clear();
3663   }
3664   llvm_unreachable("Exit infinite loop");
3665 }
3666
3667 ErrorOr<std::string> BitcodeReader::parseTriple() {
3668   if (std::error_code EC = initStream(nullptr))
3669     return EC;
3670
3671   // Sniff for the signature.
3672   if (!hasValidBitcodeHeader(Stream)) return error("Invalid bitcode signature");
3673
3674   // We expect a number of well-defined blocks, though we don't necessarily
3675   // need to understand them all.
3676   while (1) {
3677     BitstreamEntry Entry = Stream.advance();
3678
3679     switch (Entry.Kind) {
3680     case BitstreamEntry::Error:
3681       return error("Malformed block");
3682     case BitstreamEntry::EndBlock:
3683       return std::error_code();
3684
3685     case BitstreamEntry::SubBlock:
3686       if (Entry.ID == bitc::MODULE_BLOCK_ID)
3687         return parseModuleTriple();
3688
3689       // Ignore other sub-blocks.
3690       if (Stream.SkipBlock())
3691         return error("Malformed block");
3692       continue;
3693
3694     case BitstreamEntry::Record:
3695       Stream.skipRecord(Entry.ID);
3696       continue;
3697     }
3698   }
3699 }
3700
3701 /// Parse metadata attachments.
3702 std::error_code BitcodeReader::parseMetadataAttachment(Function &F) {
3703   if (Stream.EnterSubBlock(bitc::METADATA_ATTACHMENT_ID))
3704     return error("Invalid record");
3705
3706   SmallVector<uint64_t, 64> Record;
3707   while (1) {
3708     BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
3709
3710     switch (Entry.Kind) {
3711     case BitstreamEntry::SubBlock: // Handled for us already.
3712     case BitstreamEntry::Error:
3713       return error("Malformed block");
3714     case BitstreamEntry::EndBlock:
3715       return std::error_code();
3716     case BitstreamEntry::Record:
3717       // The interesting case.
3718       break;
3719     }
3720
3721     // Read a metadata attachment record.
3722     Record.clear();
3723     switch (Stream.readRecord(Entry.ID, Record)) {
3724     default:  // Default behavior: ignore.
3725       break;
3726     case bitc::METADATA_ATTACHMENT: {
3727       unsigned RecordLength = Record.size();
3728       if (Record.empty())
3729         return error("Invalid record");
3730       if (RecordLength % 2 == 0) {
3731         // A function attachment.
3732         for (unsigned I = 0; I != RecordLength; I += 2) {
3733           auto K = MDKindMap.find(Record[I]);
3734           if (K == MDKindMap.end())
3735             return error("Invalid ID");
3736           Metadata *MD = MDValueList.getValueFwdRef(Record[I + 1]);
3737           F.setMetadata(K->second, cast<MDNode>(MD));
3738         }
3739         continue;
3740       }
3741
3742       // An instruction attachment.
3743       Instruction *Inst = InstructionList[Record[0]];
3744       for (unsigned i = 1; i != RecordLength; i = i+2) {
3745         unsigned Kind = Record[i];
3746         DenseMap<unsigned, unsigned>::iterator I =
3747           MDKindMap.find(Kind);
3748         if (I == MDKindMap.end())
3749           return error("Invalid ID");
3750         Metadata *Node = MDValueList.getValueFwdRef(Record[i + 1]);
3751         if (isa<LocalAsMetadata>(Node))
3752           // Drop the attachment.  This used to be legal, but there's no
3753           // upgrade path.
3754           break;
3755         Inst->setMetadata(I->second, cast<MDNode>(Node));
3756         if (I->second == LLVMContext::MD_tbaa)
3757           InstsWithTBAATag.push_back(Inst);
3758       }
3759       break;
3760     }
3761     }
3762   }
3763 }
3764
3765 static std::error_code typeCheckLoadStoreInst(DiagnosticHandlerFunction DH,
3766                                               Type *ValType, Type *PtrType) {
3767   if (!isa<PointerType>(PtrType))
3768     return error(DH, "Load/Store operand is not a pointer type");
3769   Type *ElemType = cast<PointerType>(PtrType)->getElementType();
3770
3771   if (ValType && ValType != ElemType)
3772     return error(DH, "Explicit load/store type does not match pointee type of "
3773                      "pointer operand");
3774   if (!PointerType::isLoadableOrStorableType(ElemType))
3775     return error(DH, "Cannot load/store from pointer");
3776   return std::error_code();
3777 }
3778
3779 /// Lazily parse the specified function body block.
3780 std::error_code BitcodeReader::parseFunctionBody(Function *F) {
3781   if (Stream.EnterSubBlock(bitc::FUNCTION_BLOCK_ID))
3782     return error("Invalid record");
3783
3784   InstructionList.clear();
3785   unsigned ModuleValueListSize = ValueList.size();
3786   unsigned ModuleMDValueListSize = MDValueList.size();
3787
3788   // Add all the function arguments to the value table.
3789   for (Argument &I : F->args())
3790     ValueList.push_back(&I);
3791
3792   unsigned NextValueNo = ValueList.size();
3793   BasicBlock *CurBB = nullptr;
3794   unsigned CurBBNo = 0;
3795
3796   DebugLoc LastLoc;
3797   auto getLastInstruction = [&]() -> Instruction * {
3798     if (CurBB && !CurBB->empty())
3799       return &CurBB->back();
3800     else if (CurBBNo && FunctionBBs[CurBBNo - 1] &&
3801              !FunctionBBs[CurBBNo - 1]->empty())
3802       return &FunctionBBs[CurBBNo - 1]->back();
3803     return nullptr;
3804   };
3805
3806   std::vector<OperandBundleDef> OperandBundles;
3807
3808   // Read all the records.
3809   SmallVector<uint64_t, 64> Record;
3810   while (1) {
3811     BitstreamEntry Entry = Stream.advance();
3812
3813     switch (Entry.Kind) {
3814     case BitstreamEntry::Error:
3815       return error("Malformed block");
3816     case BitstreamEntry::EndBlock:
3817       goto OutOfRecordLoop;
3818
3819     case BitstreamEntry::SubBlock:
3820       switch (Entry.ID) {
3821       default:  // Skip unknown content.
3822         if (Stream.SkipBlock())
3823           return error("Invalid record");
3824         break;
3825       case bitc::CONSTANTS_BLOCK_ID:
3826         if (std::error_code EC = parseConstants())
3827           return EC;
3828         NextValueNo = ValueList.size();
3829         break;
3830       case bitc::VALUE_SYMTAB_BLOCK_ID:
3831         if (std::error_code EC = parseValueSymbolTable())
3832           return EC;
3833         break;
3834       case bitc::METADATA_ATTACHMENT_ID:
3835         if (std::error_code EC = parseMetadataAttachment(*F))
3836           return EC;
3837         break;
3838       case bitc::METADATA_BLOCK_ID:
3839         if (std::error_code EC = parseMetadata())
3840           return EC;
3841         break;
3842       case bitc::USELIST_BLOCK_ID:
3843         if (std::error_code EC = parseUseLists())
3844           return EC;
3845         break;
3846       }
3847       continue;
3848
3849     case BitstreamEntry::Record:
3850       // The interesting case.
3851       break;
3852     }
3853
3854     // Read a record.
3855     Record.clear();
3856     Instruction *I = nullptr;
3857     unsigned BitCode = Stream.readRecord(Entry.ID, Record);
3858     switch (BitCode) {
3859     default: // Default behavior: reject
3860       return error("Invalid value");
3861     case bitc::FUNC_CODE_DECLAREBLOCKS: {   // DECLAREBLOCKS: [nblocks]
3862       if (Record.size() < 1 || Record[0] == 0)
3863         return error("Invalid record");
3864       // Create all the basic blocks for the function.
3865       FunctionBBs.resize(Record[0]);
3866
3867       // See if anything took the address of blocks in this function.
3868       auto BBFRI = BasicBlockFwdRefs.find(F);
3869       if (BBFRI == BasicBlockFwdRefs.end()) {
3870         for (unsigned i = 0, e = FunctionBBs.size(); i != e; ++i)
3871           FunctionBBs[i] = BasicBlock::Create(Context, "", F);
3872       } else {
3873         auto &BBRefs = BBFRI->second;
3874         // Check for invalid basic block references.
3875         if (BBRefs.size() > FunctionBBs.size())
3876           return error("Invalid ID");
3877         assert(!BBRefs.empty() && "Unexpected empty array");
3878         assert(!BBRefs.front() && "Invalid reference to entry block");
3879         for (unsigned I = 0, E = FunctionBBs.size(), RE = BBRefs.size(); I != E;
3880              ++I)
3881           if (I < RE && BBRefs[I]) {
3882             BBRefs[I]->insertInto(F);
3883             FunctionBBs[I] = BBRefs[I];
3884           } else {
3885             FunctionBBs[I] = BasicBlock::Create(Context, "", F);
3886           }
3887
3888         // Erase from the table.
3889         BasicBlockFwdRefs.erase(BBFRI);
3890       }
3891
3892       CurBB = FunctionBBs[0];
3893       continue;
3894     }
3895
3896     case bitc::FUNC_CODE_DEBUG_LOC_AGAIN:  // DEBUG_LOC_AGAIN
3897       // This record indicates that the last instruction is at the same
3898       // location as the previous instruction with a location.
3899       I = getLastInstruction();
3900
3901       if (!I)
3902         return error("Invalid record");
3903       I->setDebugLoc(LastLoc);
3904       I = nullptr;
3905       continue;
3906
3907     case bitc::FUNC_CODE_DEBUG_LOC: {      // DEBUG_LOC: [line, col, scope, ia]
3908       I = getLastInstruction();
3909       if (!I || Record.size() < 4)
3910         return error("Invalid record");
3911
3912       unsigned Line = Record[0], Col = Record[1];
3913       unsigned ScopeID = Record[2], IAID = Record[3];
3914
3915       MDNode *Scope = nullptr, *IA = nullptr;
3916       if (ScopeID) Scope = cast<MDNode>(MDValueList.getValueFwdRef(ScopeID-1));
3917       if (IAID)    IA = cast<MDNode>(MDValueList.getValueFwdRef(IAID-1));
3918       LastLoc = DebugLoc::get(Line, Col, Scope, IA);
3919       I->setDebugLoc(LastLoc);
3920       I = nullptr;
3921       continue;
3922     }
3923
3924     case bitc::FUNC_CODE_INST_BINOP: {    // BINOP: [opval, ty, opval, opcode]
3925       unsigned OpNum = 0;
3926       Value *LHS, *RHS;
3927       if (getValueTypePair(Record, OpNum, NextValueNo, LHS) ||
3928           popValue(Record, OpNum, NextValueNo, LHS->getType(), RHS) ||
3929           OpNum+1 > Record.size())
3930         return error("Invalid record");
3931
3932       int Opc = getDecodedBinaryOpcode(Record[OpNum++], LHS->getType());
3933       if (Opc == -1)
3934         return error("Invalid record");
3935       I = BinaryOperator::Create((Instruction::BinaryOps)Opc, LHS, RHS);
3936       InstructionList.push_back(I);
3937       if (OpNum < Record.size()) {
3938         if (Opc == Instruction::Add ||
3939             Opc == Instruction::Sub ||
3940             Opc == Instruction::Mul ||
3941             Opc == Instruction::Shl) {
3942           if (Record[OpNum] & (1 << bitc::OBO_NO_SIGNED_WRAP))
3943             cast<BinaryOperator>(I)->setHasNoSignedWrap(true);
3944           if (Record[OpNum] & (1 << bitc::OBO_NO_UNSIGNED_WRAP))
3945             cast<BinaryOperator>(I)->setHasNoUnsignedWrap(true);
3946         } else if (Opc == Instruction::SDiv ||
3947                    Opc == Instruction::UDiv ||
3948                    Opc == Instruction::LShr ||
3949                    Opc == Instruction::AShr) {
3950           if (Record[OpNum] & (1 << bitc::PEO_EXACT))
3951             cast<BinaryOperator>(I)->setIsExact(true);
3952         } else if (isa<FPMathOperator>(I)) {
3953           FastMathFlags FMF = getDecodedFastMathFlags(Record[OpNum]);
3954           if (FMF.any())
3955             I->setFastMathFlags(FMF);
3956         }
3957
3958       }
3959       break;
3960     }
3961     case bitc::FUNC_CODE_INST_CAST: {    // CAST: [opval, opty, destty, castopc]
3962       unsigned OpNum = 0;
3963       Value *Op;
3964       if (getValueTypePair(Record, OpNum, NextValueNo, Op) ||
3965           OpNum+2 != Record.size())
3966         return error("Invalid record");
3967
3968       Type *ResTy = getTypeByID(Record[OpNum]);
3969       int Opc = getDecodedCastOpcode(Record[OpNum + 1]);
3970       if (Opc == -1 || !ResTy)
3971         return error("Invalid record");
3972       Instruction *Temp = nullptr;
3973       if ((I = UpgradeBitCastInst(Opc, Op, ResTy, Temp))) {
3974         if (Temp) {
3975           InstructionList.push_back(Temp);
3976           CurBB->getInstList().push_back(Temp);
3977         }
3978       } else {
3979         auto CastOp = (Instruction::CastOps)Opc;
3980         if (!CastInst::castIsValid(CastOp, Op, ResTy))
3981           return error("Invalid cast");
3982         I = CastInst::Create(CastOp, Op, ResTy);
3983       }
3984       InstructionList.push_back(I);
3985       break;
3986     }
3987     case bitc::FUNC_CODE_INST_INBOUNDS_GEP_OLD:
3988     case bitc::FUNC_CODE_INST_GEP_OLD:
3989     case bitc::FUNC_CODE_INST_GEP: { // GEP: type, [n x operands]
3990       unsigned OpNum = 0;
3991
3992       Type *Ty;
3993       bool InBounds;
3994
3995       if (BitCode == bitc::FUNC_CODE_INST_GEP) {
3996         InBounds = Record[OpNum++];
3997         Ty = getTypeByID(Record[OpNum++]);
3998       } else {
3999         InBounds = BitCode == bitc::FUNC_CODE_INST_INBOUNDS_GEP_OLD;
4000         Ty = nullptr;
4001       }
4002
4003       Value *BasePtr;
4004       if (getValueTypePair(Record, OpNum, NextValueNo, BasePtr))
4005         return error("Invalid record");
4006
4007       if (!Ty)
4008         Ty = cast<SequentialType>(BasePtr->getType()->getScalarType())
4009                  ->getElementType();
4010    &