contrib/llvm/lib/Bitcode/Reader/MetadataLoader.cpp

   1 //===- MetadataLoader.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 "MetadataLoader.h"
  11 #include "ValueList.h"
  12
  13 #include "llvm/ADT/APFloat.h"
  14 #include "llvm/ADT/APInt.h"
  15 #include "llvm/ADT/ArrayRef.h"
  16 #include "llvm/ADT/DenseMap.h"
  17 #include "llvm/ADT/DenseSet.h"
  18 #include "llvm/ADT/None.h"
  19 #include "llvm/ADT/STLExtras.h"
  20 #include "llvm/ADT/SmallString.h"
  21 #include "llvm/ADT/SmallVector.h"
  22 #include "llvm/ADT/Statistic.h"
  23 #include "llvm/ADT/StringRef.h"
  24 #include "llvm/ADT/Twine.h"
  25 #include "llvm/Bitcode/BitcodeReader.h"
  26 #include "llvm/Bitcode/BitstreamReader.h"
  27 #include "llvm/Bitcode/LLVMBitCodes.h"
  28 #include "llvm/IR/Argument.h"
  29 #include "llvm/IR/Attributes.h"
  30 #include "llvm/IR/AutoUpgrade.h"
  31 #include "llvm/IR/BasicBlock.h"
  32 #include "llvm/IR/CallingConv.h"
  33 #include "llvm/IR/Comdat.h"
  34 #include "llvm/IR/Constant.h"
  35 #include "llvm/IR/Constants.h"
  36 #include "llvm/IR/DebugInfo.h"
  37 #include "llvm/IR/DebugInfoMetadata.h"
  38 #include "llvm/IR/DebugLoc.h"
  39 #include "llvm/IR/DerivedTypes.h"
  40 #include "llvm/IR/DiagnosticPrinter.h"
  41 #include "llvm/IR/Function.h"
  42 #include "llvm/IR/GVMaterializer.h"
  43 #include "llvm/IR/GlobalAlias.h"
  44 #include "llvm/IR/GlobalIFunc.h"
  45 #include "llvm/IR/GlobalIndirectSymbol.h"
  46 #include "llvm/IR/GlobalObject.h"
  47 #include "llvm/IR/GlobalValue.h"
  48 #include "llvm/IR/GlobalVariable.h"
  49 #include "llvm/IR/InlineAsm.h"
  50 #include "llvm/IR/InstrTypes.h"
  51 #include "llvm/IR/Instruction.h"
  52 #include "llvm/IR/Instructions.h"
  53 #include "llvm/IR/IntrinsicInst.h"
  54 #include "llvm/IR/Intrinsics.h"
  55 #include "llvm/IR/LLVMContext.h"
  56 #include "llvm/IR/Module.h"
  57 #include "llvm/IR/ModuleSummaryIndex.h"
  58 #include "llvm/IR/OperandTraits.h"
  59 #include "llvm/IR/TrackingMDRef.h"
  60 #include "llvm/IR/Type.h"
  61 #include "llvm/IR/ValueHandle.h"
  62 #include "llvm/Support/AtomicOrdering.h"
  63 #include "llvm/Support/Casting.h"
  64 #include "llvm/Support/CommandLine.h"
  65 #include "llvm/Support/Compiler.h"
  66 #include "llvm/Support/Debug.h"
  67 #include "llvm/Support/Error.h"
  68 #include "llvm/Support/ErrorHandling.h"
  69 #include "llvm/Support/ManagedStatic.h"
  70 #include "llvm/Support/MemoryBuffer.h"
  71 #include "llvm/Support/raw_ostream.h"
  72 #include <algorithm>
  73 #include <cassert>
  74 #include <cstddef>
  75 #include <cstdint>
  76 #include <deque>
  77 #include <limits>
  78 #include <map>
  79 #include <memory>
  80 #include <string>
  81 #include <system_error>
  82 #include <tuple>
  83 #include <utility>
  84 #include <vector>
  85
  86 using namespace llvm;
  87
  88 #define DEBUG_TYPE "bitcode-reader"
  89
  90 STATISTIC(NumMDStringLoaded, "Number of MDStrings loaded");
  91 STATISTIC(NumMDNodeTemporary, "Number of MDNode::Temporary created");
  92 STATISTIC(NumMDRecordLoaded, "Number of Metadata records loaded");
  93
  94 /// Flag whether we need to import full type definitions for ThinLTO.
  95 /// Currently needed for Darwin and LLDB.
  96 static cl::opt<bool> ImportFullTypeDefinitions(
  97     "import-full-type-definitions", cl::init(false), cl::Hidden,
  98     cl::desc("Import full type definitions for ThinLTO."));
  99
 100 static cl::opt<bool> DisableLazyLoading(
 101     "disable-ondemand-mds-loading", cl::init(false), cl::Hidden,
 102     cl::desc("Force disable the lazy-loading on-demand of metadata when "
 103              "loading bitcode for importing."));
 104
 105 namespace {
 106
 107 static int64_t unrotateSign(uint64_t U) { return U & 1 ? ~(U >> 1) : U >> 1; }
 108
 109 class BitcodeReaderMetadataList {
 110   /// Array of metadata references.
 111   ///
 112   /// Don't use std::vector here.  Some versions of libc++ copy (instead of
 113   /// move) on resize, and TrackingMDRef is very expensive to copy.
 114   SmallVector<TrackingMDRef, 1> MetadataPtrs;
 115
 116   /// The set of indices in MetadataPtrs above of forward references that were
 117   /// generated.
 118   SmallDenseSet<unsigned, 1> ForwardReference;
 119
 120   /// The set of indices in MetadataPtrs above of Metadata that need to be
 121   /// resolved.
 122   SmallDenseSet<unsigned, 1> UnresolvedNodes;
 123
 124   /// Structures for resolving old type refs.
 125   struct {
 126     SmallDenseMap<MDString *, TempMDTuple, 1> Unknown;
 127     SmallDenseMap<MDString *, DICompositeType *, 1> Final;
 128     SmallDenseMap<MDString *, DICompositeType *, 1> FwdDecls;
 129     SmallVector<std::pair<TrackingMDRef, TempMDTuple>, 1> Arrays;
 130   } OldTypeRefs;
 131
 132   LLVMContext &Context;
 133
 134 public:
 135   BitcodeReaderMetadataList(LLVMContext &C) : Context(C) {}
 136
 137   // vector compatibility methods
 138   unsigned size() const { return MetadataPtrs.size(); }
 139   void resize(unsigned N) { MetadataPtrs.resize(N); }
 140   void push_back(Metadata *MD) { MetadataPtrs.emplace_back(MD); }
 141   void clear() { MetadataPtrs.clear(); }
 142   Metadata *back() const { return MetadataPtrs.back(); }
 143   void pop_back() { MetadataPtrs.pop_back(); }
 144   bool empty() const { return MetadataPtrs.empty(); }
 145
 146   Metadata *operator[](unsigned i) const {
 147     assert(i < MetadataPtrs.size());
 148     return MetadataPtrs[i];
 149   }
 150
 151   Metadata *lookup(unsigned I) const {
 152     if (I < MetadataPtrs.size())
 153       return MetadataPtrs[I];
 154     return nullptr;
 155   }
 156
 157   void shrinkTo(unsigned N) {
 158     assert(N <= size() && "Invalid shrinkTo request!");
 159     assert(ForwardReference.empty() && "Unexpected forward refs");
 160     assert(UnresolvedNodes.empty() && "Unexpected unresolved node");
 161     MetadataPtrs.resize(N);
 162   }
 163
 164   /// Return the given metadata, creating a replaceable forward reference if
 165   /// necessary.
 166   Metadata *getMetadataFwdRef(unsigned Idx);
 167
 168   /// Return the the given metadata only if it is fully resolved.
 169   ///
 170   /// Gives the same result as \a lookup(), unless \a MDNode::isResolved()
 171   /// would give \c false.
 172   Metadata *getMetadataIfResolved(unsigned Idx);
 173
 174   MDNode *getMDNodeFwdRefOrNull(unsigned Idx);
 175   void assignValue(Metadata *MD, unsigned Idx);
 176   void tryToResolveCycles();
 177   bool hasFwdRefs() const { return !ForwardReference.empty(); }
 178   int getNextFwdRef() {
 179     assert(hasFwdRefs());
 180     return *ForwardReference.begin();
 181   }
 182
 183   /// Upgrade a type that had an MDString reference.
 184   void addTypeRef(MDString &UUID, DICompositeType &CT);
 185
 186   /// Upgrade a type that had an MDString reference.
 187   Metadata *upgradeTypeRef(Metadata *MaybeUUID);
 188
 189   /// Upgrade a type ref array that may have MDString references.
 190   Metadata *upgradeTypeRefArray(Metadata *MaybeTuple);
 191
 192 private:
 193   Metadata *resolveTypeRefArray(Metadata *MaybeTuple);
 194 };
 195
 196 void BitcodeReaderMetadataList::assignValue(Metadata *MD, unsigned Idx) {
 197   if (auto *MDN = dyn_cast<MDNode>(MD))
 198     if (!MDN->isResolved())
 199       UnresolvedNodes.insert(Idx);
 200
 201   if (Idx == size()) {
 202     push_back(MD);
 203     return;
 204   }
 205
 206   if (Idx >= size())
 207     resize(Idx + 1);
 208
 209   TrackingMDRef &OldMD = MetadataPtrs[Idx];
 210   if (!OldMD) {
 211     OldMD.reset(MD);
 212     return;
 213   }
 214
 215   // If there was a forward reference to this value, replace it.
 216   TempMDTuple PrevMD(cast<MDTuple>(OldMD.get()));
 217   PrevMD->replaceAllUsesWith(MD);
 218   ForwardReference.erase(Idx);
 219 }
 220
 221 Metadata *BitcodeReaderMetadataList::getMetadataFwdRef(unsigned Idx) {
 222   if (Idx >= size())
 223     resize(Idx + 1);
 224
 225   if (Metadata *MD = MetadataPtrs[Idx])
 226     return MD;
 227
 228   // Track forward refs to be resolved later.
 229   ForwardReference.insert(Idx);
 230
 231   // Create and return a placeholder, which will later be RAUW'd.
 232   ++NumMDNodeTemporary;
 233   Metadata *MD = MDNode::getTemporary(Context, None).release();
 234   MetadataPtrs[Idx].reset(MD);
 235   return MD;
 236 }
 237
 238 Metadata *BitcodeReaderMetadataList::getMetadataIfResolved(unsigned Idx) {
 239   Metadata *MD = lookup(Idx);
 240   if (auto *N = dyn_cast_or_null<MDNode>(MD))
 241     if (!N->isResolved())
 242       return nullptr;
 243   return MD;
 244 }
 245
 246 MDNode *BitcodeReaderMetadataList::getMDNodeFwdRefOrNull(unsigned Idx) {
 247   return dyn_cast_or_null<MDNode>(getMetadataFwdRef(Idx));
 248 }
 249
 250 void BitcodeReaderMetadataList::tryToResolveCycles() {
 251   if (!ForwardReference.empty())
 252     // Still forward references... can't resolve cycles.
 253     return;
 254
 255   // Give up on finding a full definition for any forward decls that remain.
 256   for (const auto &Ref : OldTypeRefs.FwdDecls)
 257     OldTypeRefs.Final.insert(Ref);
 258   OldTypeRefs.FwdDecls.clear();
 259
 260   // Upgrade from old type ref arrays.  In strange cases, this could add to
 261   // OldTypeRefs.Unknown.
 262   for (const auto &Array : OldTypeRefs.Arrays)
 263     Array.second->replaceAllUsesWith(resolveTypeRefArray(Array.first.get()));
 264   OldTypeRefs.Arrays.clear();
 265
 266   // Replace old string-based type refs with the resolved node, if possible.
 267   // If we haven't seen the node, leave it to the verifier to complain about
 268   // the invalid string reference.
 269   for (const auto &Ref : OldTypeRefs.Unknown) {
 270     if (DICompositeType *CT = OldTypeRefs.Final.lookup(Ref.first))
 271       Ref.second->replaceAllUsesWith(CT);
 272     else
 273       Ref.second->replaceAllUsesWith(Ref.first);
 274   }
 275   OldTypeRefs.Unknown.clear();
 276
 277   if (UnresolvedNodes.empty())
 278     // Nothing to do.
 279     return;
 280
 281   // Resolve any cycles.
 282   for (unsigned I : UnresolvedNodes) {
 283     auto &MD = MetadataPtrs[I];
 284     auto *N = dyn_cast_or_null<MDNode>(MD);
 285     if (!N)
 286       continue;
 287
 288     assert(!N->isTemporary() && "Unexpected forward reference");
 289     N->resolveCycles();
 290   }
 291
 292   // Make sure we return early again until there's another unresolved ref.
 293   UnresolvedNodes.clear();
 294 }
 295
 296 void BitcodeReaderMetadataList::addTypeRef(MDString &UUID,
 297                                            DICompositeType &CT) {
 298   assert(CT.getRawIdentifier() == &UUID && "Mismatched UUID");
 299   if (CT.isForwardDecl())
 300     OldTypeRefs.FwdDecls.insert(std::make_pair(&UUID, &CT));
 301   else
 302     OldTypeRefs.Final.insert(std::make_pair(&UUID, &CT));
 303 }
 304
 305 Metadata *BitcodeReaderMetadataList::upgradeTypeRef(Metadata *MaybeUUID) {
 306   auto *UUID = dyn_cast_or_null<MDString>(MaybeUUID);
 307   if (LLVM_LIKELY(!UUID))
 308     return MaybeUUID;
 309
 310   if (auto *CT = OldTypeRefs.Final.lookup(UUID))
 311     return CT;
 312
 313   auto &Ref = OldTypeRefs.Unknown[UUID];
 314   if (!Ref)
 315     Ref = MDNode::getTemporary(Context, None);
 316   return Ref.get();
 317 }
 318
 319 Metadata *BitcodeReaderMetadataList::upgradeTypeRefArray(Metadata *MaybeTuple) {
 320   auto *Tuple = dyn_cast_or_null<MDTuple>(MaybeTuple);
 321   if (!Tuple || Tuple->isDistinct())
 322     return MaybeTuple;
 323
 324   // Look through the array immediately if possible.
 325   if (!Tuple->isTemporary())
 326     return resolveTypeRefArray(Tuple);
 327
 328   // Create and return a placeholder to use for now.  Eventually
 329   // resolveTypeRefArrays() will be resolve this forward reference.
 330   OldTypeRefs.Arrays.emplace_back(
 331       std::piecewise_construct, std::forward_as_tuple(Tuple),
 332       std::forward_as_tuple(MDTuple::getTemporary(Context, None)));
 333   return OldTypeRefs.Arrays.back().second.get();
 334 }
 335
 336 Metadata *BitcodeReaderMetadataList::resolveTypeRefArray(Metadata *MaybeTuple) {
 337   auto *Tuple = dyn_cast_or_null<MDTuple>(MaybeTuple);
 338   if (!Tuple || Tuple->isDistinct())
 339     return MaybeTuple;
 340
 341   // Look through the DITypeRefArray, upgrading each DITypeRef.
 342   SmallVector<Metadata *, 32> Ops;
 343   Ops.reserve(Tuple->getNumOperands());
 344   for (Metadata *MD : Tuple->operands())
 345     Ops.push_back(upgradeTypeRef(MD));
 346
 347   return MDTuple::get(Context, Ops);
 348 }
 349
 350 namespace {
 351
 352 class PlaceholderQueue {
 353   // Placeholders would thrash around when moved, so store in a std::deque
 354   // instead of some sort of vector.
 355   std::deque<DistinctMDOperandPlaceholder> PHs;
 356
 357 public:
 358   ~PlaceholderQueue() {
 359     assert(empty() && "PlaceholderQueue hasn't been flushed before being destroyed");
 360   }
 361   bool empty() { return PHs.empty(); }
 362   DistinctMDOperandPlaceholder &getPlaceholderOp(unsigned ID);
 363   void flush(BitcodeReaderMetadataList &MetadataList);
 364
 365   /// Return the list of temporaries nodes in the queue, these need to be
 366   /// loaded before we can flush the queue.
 367   void getTemporaries(BitcodeReaderMetadataList &MetadataList,
 368                       DenseSet<unsigned> &Temporaries) {
 369     for (auto &PH : PHs) {
 370       auto ID = PH.getID();
 371       auto *MD = MetadataList.lookup(ID);
 372       if (!MD) {
 373         Temporaries.insert(ID);
 374         continue;
 375       }
 376       auto *N = dyn_cast_or_null<MDNode>(MD);
 377       if (N && N->isTemporary())
 378         Temporaries.insert(ID);
 379     }
 380   }
 381 };
 382
 383 } // end anonymous namespace
 384
 385 DistinctMDOperandPlaceholder &PlaceholderQueue::getPlaceholderOp(unsigned ID) {
 386   PHs.emplace_back(ID);
 387   return PHs.back();
 388 }
 389
 390 void PlaceholderQueue::flush(BitcodeReaderMetadataList &MetadataList) {
 391   while (!PHs.empty()) {
 392     auto *MD = MetadataList.lookup(PHs.front().getID());
 393     assert(MD && "Flushing placeholder on unassigned MD");
 394 #ifndef NDEBUG
 395     if (auto *MDN = dyn_cast<MDNode>(MD))
 396       assert(MDN->isResolved() &&
 397              "Flushing Placeholder while cycles aren't resolved");
 398 #endif
 399     PHs.front().replaceUseWith(MD);
 400     PHs.pop_front();
 401   }
 402 }
 403
 404 } // anonynous namespace
 405
 406 static Error error(const Twine &Message) {
 407   return make_error<StringError>(
 408       Message, make_error_code(BitcodeError::CorruptedBitcode));
 409 }
 410
 411 class MetadataLoader::MetadataLoaderImpl {
 412   BitcodeReaderMetadataList MetadataList;
 413   BitcodeReaderValueList &ValueList;
 414   BitstreamCursor &Stream;
 415   LLVMContext &Context;
 416   Module &TheModule;
 417   std::function<Type *(unsigned)> getTypeByID;
 418
 419   /// Cursor associated with the lazy-loading of Metadata. This is the easy way
 420   /// to keep around the right "context" (Abbrev list) to be able to jump in
 421   /// the middle of the metadata block and load any record.
 422   BitstreamCursor IndexCursor;
 423
 424   /// Index that keeps track of MDString values.
 425   std::vector<StringRef> MDStringRef;
 426
 427   /// On-demand loading of a single MDString. Requires the index above to be
 428   /// populated.
 429   MDString *lazyLoadOneMDString(unsigned Idx);
 430
 431   /// Index that keeps track of where to find a metadata record in the stream.
 432   std::vector<uint64_t> GlobalMetadataBitPosIndex;
 433
 434   /// Populate the index above to enable lazily loading of metadata, and load
 435   /// the named metadata as well as the transitively referenced global
 436   /// Metadata.
 437   Expected<bool> lazyLoadModuleMetadataBlock();
 438
 439   /// On-demand loading of a single metadata. Requires the index above to be
 440   /// populated.
 441   void lazyLoadOneMetadata(unsigned Idx, PlaceholderQueue &Placeholders);
 442
 443   // Keep mapping of seens pair of old-style CU <-> SP, and update pointers to
 444   // point from SP to CU after a block is completly parsed.
 445   std::vector<std::pair<DICompileUnit *, Metadata *>> CUSubprograms;
 446
 447   /// Functions that need to be matched with subprograms when upgrading old
 448   /// metadata.
 449   SmallDenseMap<Function *, DISubprogram *, 16> FunctionsWithSPs;
 450
 451   // Map the bitcode's custom MDKind ID to the Module's MDKind ID.
 452   DenseMap<unsigned, unsigned> MDKindMap;
 453
 454   bool StripTBAA = false;
 455   bool HasSeenOldLoopTags = false;
 456   bool NeedUpgradeToDIGlobalVariableExpression = false;
 457   bool NeedDeclareExpressionUpgrade = false;
 458
 459   /// True if metadata is being parsed for a module being ThinLTO imported.
 460   bool IsImporting = false;
 461
 462   Error parseOneMetadata(SmallVectorImpl<uint64_t> &Record, unsigned Code,
 463                          PlaceholderQueue &Placeholders, StringRef Blob,
 464                          unsigned &NextMetadataNo);
 465   Error parseMetadataStrings(ArrayRef<uint64_t> Record, StringRef Blob,
 466                              function_ref<void(StringRef)> CallBack);
 467   Error parseGlobalObjectAttachment(GlobalObject &GO,
 468                                     ArrayRef<uint64_t> Record);
 469   Error parseMetadataKindRecord(SmallVectorImpl<uint64_t> &Record);
 470
 471   void resolveForwardRefsAndPlaceholders(PlaceholderQueue &Placeholders);
 472
 473   /// Upgrade old-style CU <-> SP pointers to point from SP to CU.
 474   void upgradeCUSubprograms() {
 475     for (auto CU_SP : CUSubprograms)
 476       if (auto *SPs = dyn_cast_or_null<MDTuple>(CU_SP.second))
 477         for (auto &Op : SPs->operands())
 478           if (auto *SP = dyn_cast_or_null<DISubprogram>(Op))
 479             SP->replaceUnit(CU_SP.first);
 480     CUSubprograms.clear();
 481   }
 482
 483   /// Upgrade old-style bare DIGlobalVariables to DIGlobalVariableExpressions.
 484   void upgradeCUVariables() {
 485     if (!NeedUpgradeToDIGlobalVariableExpression)
 486       return;
 487
 488     // Upgrade list of variables attached to the CUs.
 489     if (NamedMDNode *CUNodes = TheModule.getNamedMetadata("llvm.dbg.cu"))
 490       for (unsigned I = 0, E = CUNodes->getNumOperands(); I != E; ++I) {
 491         auto *CU = cast<DICompileUnit>(CUNodes->getOperand(I));
 492         if (auto *GVs = dyn_cast_or_null<MDTuple>(CU->getRawGlobalVariables()))
 493           for (unsigned I = 0; I < GVs->getNumOperands(); I++)
 494             if (auto *GV =
 495                     dyn_cast_or_null<DIGlobalVariable>(GVs->getOperand(I))) {
 496               auto *DGVE = DIGlobalVariableExpression::getDistinct(
 497                   Context, GV, DIExpression::get(Context, {}));
 498               GVs->replaceOperandWith(I, DGVE);
 499             }
 500       }
 501
 502     // Upgrade variables attached to globals.
 503     for (auto &GV : TheModule.globals()) {
 504       SmallVector<MDNode *, 1> MDs;
 505       GV.getMetadata(LLVMContext::MD_dbg, MDs);
 506       GV.eraseMetadata(LLVMContext::MD_dbg);
 507       for (auto *MD : MDs)
 508         if (auto *DGV = dyn_cast_or_null<DIGlobalVariable>(MD)) {
 509           auto *DGVE = DIGlobalVariableExpression::getDistinct(
 510               Context, DGV, DIExpression::get(Context, {}));
 511           GV.addMetadata(LLVMContext::MD_dbg, *DGVE);
 512         } else
 513           GV.addMetadata(LLVMContext::MD_dbg, *MD);
 514     }
 515   }
 516
 517   /// Remove a leading DW_OP_deref from DIExpressions in a dbg.declare that
 518   /// describes a function argument.
 519   void upgradeDeclareExpressions(Function &F) {
 520     if (!NeedDeclareExpressionUpgrade)
 521       return;
 522
 523     for (auto &BB : F)
 524       for (auto &I : BB)
 525         if (auto *DDI = dyn_cast<DbgDeclareInst>(&I))
 526           if (auto *DIExpr = DDI->getExpression())
 527             if (DIExpr->startsWithDeref() &&
 528                 dyn_cast_or_null<Argument>(DDI->getAddress())) {
 529               SmallVector<uint64_t, 8> Ops;
 530               Ops.append(std::next(DIExpr->elements_begin()),
 531                          DIExpr->elements_end());
 532               auto *E = DIExpression::get(Context, Ops);
 533               DDI->setOperand(2, MetadataAsValue::get(Context, E));
 534             }
 535   }
 536
 537   /// Upgrade the expression from previous versions.
 538   Error upgradeDIExpression(uint64_t FromVersion,
 539                             MutableArrayRef<uint64_t> &Expr,
 540                             SmallVectorImpl<uint64_t> &Buffer) {
 541     auto N = Expr.size();
 542     switch (FromVersion) {
 543     default:
 544       return error("Invalid record");
 545     case 0:
 546       if (N >= 3 && Expr[N - 3] == dwarf::DW_OP_bit_piece)
 547         Expr[N - 3] = dwarf::DW_OP_LLVM_fragment;
 548       LLVM_FALLTHROUGH;
 549     case 1:
 550       // Move DW_OP_deref to the end.
 551       if (N && Expr[0] == dwarf::DW_OP_deref) {
 552         auto End = Expr.end();
 553         if (Expr.size() >= 3 &&
 554             *std::prev(End, 3) == dwarf::DW_OP_LLVM_fragment)
 555           End = std::prev(End, 3);
 556         std::move(std::next(Expr.begin()), End, Expr.begin());
 557         *std::prev(End) = dwarf::DW_OP_deref;
 558       }
 559       NeedDeclareExpressionUpgrade = true;
 560       LLVM_FALLTHROUGH;
 561     case 2: {
 562       // Change DW_OP_plus to DW_OP_plus_uconst.
 563       // Change DW_OP_minus to DW_OP_uconst, DW_OP_minus
 564       auto SubExpr = ArrayRef<uint64_t>(Expr);
 565       while (!SubExpr.empty()) {
 566         // Skip past other operators with their operands
 567         // for this version of the IR, obtained from
 568         // from historic DIExpression::ExprOperand::getSize().
 569         size_t HistoricSize;
 570         switch (SubExpr.front()) {
 571         default:
 572           HistoricSize = 1;
 573           break;
 574         case dwarf::DW_OP_constu:
 575         case dwarf::DW_OP_minus:
 576         case dwarf::DW_OP_plus:
 577           HistoricSize = 2;
 578           break;
 579         case dwarf::DW_OP_LLVM_fragment:
 580           HistoricSize = 3;
 581           break;
 582         }
 583
 584         // If the expression is malformed, make sure we don't
 585         // copy more elements than we should.
 586         HistoricSize = std::min(SubExpr.size(), HistoricSize);
 587         ArrayRef<uint64_t> Args = SubExpr.slice(1, HistoricSize-1);
 588
 589         switch (SubExpr.front()) {
 590         case dwarf::DW_OP_plus:
 591           Buffer.push_back(dwarf::DW_OP_plus_uconst);
 592           Buffer.append(Args.begin(), Args.end());
 593           break;
 594         case dwarf::DW_OP_minus:
 595           Buffer.push_back(dwarf::DW_OP_constu);
 596           Buffer.append(Args.begin(), Args.end());
 597           Buffer.push_back(dwarf::DW_OP_minus);
 598           break;
 599         default:
 600           Buffer.push_back(*SubExpr.begin());
 601           Buffer.append(Args.begin(), Args.end());
 602           break;
 603         }
 604
 605         // Continue with remaining elements.
 606         SubExpr = SubExpr.slice(HistoricSize);
 607       }
 608       Expr = MutableArrayRef<uint64_t>(Buffer);
 609       LLVM_FALLTHROUGH;
 610     }
 611     case 3:
 612       // Up-to-date!
 613       break;
 614     }
 615
 616     return Error::success();
 617   }
 618
 619   void upgradeDebugInfo() {
 620     upgradeCUSubprograms();
 621     upgradeCUVariables();
 622   }
 623
 624 public:
 625   MetadataLoaderImpl(BitstreamCursor &Stream, Module &TheModule,
 626                      BitcodeReaderValueList &ValueList,
 627                      std::function<Type *(unsigned)> getTypeByID,
 628                      bool IsImporting)
 629       : MetadataList(TheModule.getContext()), ValueList(ValueList),
 630         Stream(Stream), Context(TheModule.getContext()), TheModule(TheModule),
 631         getTypeByID(std::move(getTypeByID)), IsImporting(IsImporting) {}
 632
 633   Error parseMetadata(bool ModuleLevel);
 634
 635   bool hasFwdRefs() const { return MetadataList.hasFwdRefs(); }
 636
 637   Metadata *getMetadataFwdRefOrLoad(unsigned ID) {
 638     if (ID < MDStringRef.size())
 639       return lazyLoadOneMDString(ID);
 640     if (auto *MD = MetadataList.lookup(ID))
 641       return MD;
 642     // If lazy-loading is enabled, we try recursively to load the operand
 643     // instead of creating a temporary.
 644     if (ID < (MDStringRef.size() + GlobalMetadataBitPosIndex.size())) {
 645       PlaceholderQueue Placeholders;
 646       lazyLoadOneMetadata(ID, Placeholders);
 647       resolveForwardRefsAndPlaceholders(Placeholders);
 648       return MetadataList.lookup(ID);
 649     }
 650     return MetadataList.getMetadataFwdRef(ID);
 651   }
 652
 653   MDNode *getMDNodeFwdRefOrNull(unsigned Idx) {
 654     return MetadataList.getMDNodeFwdRefOrNull(Idx);
 655   }
 656
 657   DISubprogram *lookupSubprogramForFunction(Function *F) {
 658     return FunctionsWithSPs.lookup(F);
 659   }
 660
 661   bool hasSeenOldLoopTags() { return HasSeenOldLoopTags; }
 662
 663   Error parseMetadataAttachment(
 664       Function &F, const SmallVectorImpl<Instruction *> &InstructionList);
 665
 666   Error parseMetadataKinds();
 667
 668   void setStripTBAA(bool Value) { StripTBAA = Value; }
 669   bool isStrippingTBAA() { return StripTBAA; }
 670
 671   unsigned size() const { return MetadataList.size(); }
 672   void shrinkTo(unsigned N) { MetadataList.shrinkTo(N); }
 673   void upgradeDebugIntrinsics(Function &F) { upgradeDeclareExpressions(F); }
 674 };
 675
 676 Expected<bool>
 677 MetadataLoader::MetadataLoaderImpl::lazyLoadModuleMetadataBlock() {
 678   IndexCursor = Stream;
 679   SmallVector<uint64_t, 64> Record;
 680   // Get the abbrevs, and preload record positions to make them lazy-loadable.
 681   while (true) {
 682     BitstreamEntry Entry = IndexCursor.advanceSkippingSubblocks(
 683         BitstreamCursor::AF_DontPopBlockAtEnd);
 684     switch (Entry.Kind) {
 685     case BitstreamEntry::SubBlock: // Handled for us already.
 686     case BitstreamEntry::Error:
 687       return error("Malformed block");
 688     case BitstreamEntry::EndBlock: {
 689       return true;
 690     }
 691     case BitstreamEntry::Record: {
 692       // The interesting case.
 693       ++NumMDRecordLoaded;
 694       uint64_t CurrentPos = IndexCursor.GetCurrentBitNo();
 695       auto Code = IndexCursor.skipRecord(Entry.ID);
 696       switch (Code) {
 697       case bitc::METADATA_STRINGS: {
 698         // Rewind and parse the strings.
 699         IndexCursor.JumpToBit(CurrentPos);
 700         StringRef Blob;
 701         Record.clear();
 702         IndexCursor.readRecord(Entry.ID, Record, &Blob);
 703         unsigned NumStrings = Record[0];
 704         MDStringRef.reserve(NumStrings);
 705         auto IndexNextMDString = [&](StringRef Str) {
 706           MDStringRef.push_back(Str);
 707         };
 708         if (auto Err = parseMetadataStrings(Record, Blob, IndexNextMDString))
 709           return std::move(Err);
 710         break;
 711       }
 712       case bitc::METADATA_INDEX_OFFSET: {
 713         // This is the offset to the index, when we see this we skip all the
 714         // records and load only an index to these.
 715         IndexCursor.JumpToBit(CurrentPos);
 716         Record.clear();
 717         IndexCursor.readRecord(Entry.ID, Record);
 718         if (Record.size() != 2)
 719           return error("Invalid record");
 720         auto Offset = Record[0] + (Record[1] << 32);
 721         auto BeginPos = IndexCursor.GetCurrentBitNo();
 722         IndexCursor.JumpToBit(BeginPos + Offset);
 723         Entry = IndexCursor.advanceSkippingSubblocks(
 724             BitstreamCursor::AF_DontPopBlockAtEnd);
 725         assert(Entry.Kind == BitstreamEntry::Record &&
 726                "Corrupted bitcode: Expected `Record` when trying to find the "
 727                "Metadata index");
 728         Record.clear();
 729         auto Code = IndexCursor.readRecord(Entry.ID, Record);
 730         (void)Code;
 731         assert(Code == bitc::METADATA_INDEX && "Corrupted bitcode: Expected "
 732                                                "`METADATA_INDEX` when trying "
 733                                                "to find the Metadata index");
 734
 735         // Delta unpack
 736         auto CurrentValue = BeginPos;
 737         GlobalMetadataBitPosIndex.reserve(Record.size());
 738         for (auto &Elt : Record) {
 739           CurrentValue += Elt;
 740           GlobalMetadataBitPosIndex.push_back(CurrentValue);
 741         }
 742         break;
 743       }
 744       case bitc::METADATA_INDEX:
 745         // We don't expect to get there, the Index is loaded when we encounter
 746         // the offset.
 747         return error("Corrupted Metadata block");
 748       case bitc::METADATA_NAME: {
 749         // Named metadata need to be materialized now and aren't deferred.
 750         IndexCursor.JumpToBit(CurrentPos);
 751         Record.clear();
 752         unsigned Code = IndexCursor.readRecord(Entry.ID, Record);
 753         assert(Code == bitc::METADATA_NAME);
 754
 755         // Read name of the named metadata.
 756         SmallString<8> Name(Record.begin(), Record.end());
 757         Code = IndexCursor.ReadCode();
 758
 759         // Named Metadata comes in two parts, we expect the name to be followed
 760         // by the node
 761         Record.clear();
 762         unsigned NextBitCode = IndexCursor.readRecord(Code, Record);
 763         assert(NextBitCode == bitc::METADATA_NAMED_NODE);
 764         (void)NextBitCode;
 765
 766         // Read named metadata elements.
 767         unsigned Size = Record.size();
 768         NamedMDNode *NMD = TheModule.getOrInsertNamedMetadata(Name);
 769         for (unsigned i = 0; i != Size; ++i) {
 770           // FIXME: We could use a placeholder here, however NamedMDNode are
 771           // taking MDNode as operand and not using the Metadata infrastructure.
 772           // It is acknowledged by 'TODO: Inherit from Metadata' in the
 773           // NamedMDNode class definition.
 774           MDNode *MD = MetadataList.getMDNodeFwdRefOrNull(Record[i]);
 775           assert(MD && "Invalid record");
 776           NMD->addOperand(MD);
 777         }
 778         break;
 779       }
 780       case bitc::METADATA_GLOBAL_DECL_ATTACHMENT: {
 781         // FIXME: we need to do this early because we don't materialize global
 782         // value explicitly.
 783         IndexCursor.JumpToBit(CurrentPos);
 784         Record.clear();
 785         IndexCursor.readRecord(Entry.ID, Record);
 786         if (Record.size() % 2 == 0)
 787           return error("Invalid record");
 788         unsigned ValueID = Record[0];
 789         if (ValueID >= ValueList.size())
 790           return error("Invalid record");
 791         if (auto *GO = dyn_cast<GlobalObject>(ValueList[ValueID]))
 792           if (Error Err = parseGlobalObjectAttachment(
 793                   *GO, ArrayRef<uint64_t>(Record).slice(1)))
 794             return std::move(Err);
 795         break;
 796       }
 797       case bitc::METADATA_KIND:
 798       case bitc::METADATA_STRING_OLD:
 799       case bitc::METADATA_OLD_FN_NODE:
 800       case bitc::METADATA_OLD_NODE:
 801       case bitc::METADATA_VALUE:
 802       case bitc::METADATA_DISTINCT_NODE:
 803       case bitc::METADATA_NODE:
 804       case bitc::METADATA_LOCATION:
 805       case bitc::METADATA_GENERIC_DEBUG:
 806       case bitc::METADATA_SUBRANGE:
 807       case bitc::METADATA_ENUMERATOR:
 808       case bitc::METADATA_BASIC_TYPE:
 809       case bitc::METADATA_DERIVED_TYPE:
 810       case bitc::METADATA_COMPOSITE_TYPE:
 811       case bitc::METADATA_SUBROUTINE_TYPE:
 812       case bitc::METADATA_MODULE:
 813       case bitc::METADATA_FILE:
 814       case bitc::METADATA_COMPILE_UNIT:
 815       case bitc::METADATA_SUBPROGRAM:
 816       case bitc::METADATA_LEXICAL_BLOCK:
 817       case bitc::METADATA_LEXICAL_BLOCK_FILE:
 818       case bitc::METADATA_NAMESPACE:
 819       case bitc::METADATA_MACRO:
 820       case bitc::METADATA_MACRO_FILE:
 821       case bitc::METADATA_TEMPLATE_TYPE:
 822       case bitc::METADATA_TEMPLATE_VALUE:
 823       case bitc::METADATA_GLOBAL_VAR:
 824       case bitc::METADATA_LOCAL_VAR:
 825       case bitc::METADATA_EXPRESSION:
 826       case bitc::METADATA_OBJC_PROPERTY:
 827       case bitc::METADATA_IMPORTED_ENTITY:
 828       case bitc::METADATA_GLOBAL_VAR_EXPR:
 829         // We don't expect to see any of these, if we see one, give up on
 830         // lazy-loading and fallback.
 831         MDStringRef.clear();
 832         GlobalMetadataBitPosIndex.clear();
 833         return false;
 834       }
 835       break;
 836     }
 837     }
 838   }
 839 }
 840
 841 /// Parse a METADATA_BLOCK. If ModuleLevel is true then we are parsing
 842 /// module level metadata.
 843 Error MetadataLoader::MetadataLoaderImpl::parseMetadata(bool ModuleLevel) {
 844   if (!ModuleLevel && MetadataList.hasFwdRefs())
 845     return error("Invalid metadata: fwd refs into function blocks");
 846
 847   // Record the entry position so that we can jump back here and efficiently
 848   // skip the whole block in case we lazy-load.
 849   auto EntryPos = Stream.GetCurrentBitNo();
 850
 851   if (Stream.EnterSubBlock(bitc::METADATA_BLOCK_ID))
 852     return error("Invalid record");
 853
 854   SmallVector<uint64_t, 64> Record;
 855   PlaceholderQueue Placeholders;
 856
 857   // We lazy-load module-level metadata: we build an index for each record, and
 858   // then load individual record as needed, starting with the named metadata.
 859   if (ModuleLevel && IsImporting && MetadataList.empty() &&
 860       !DisableLazyLoading) {
 861     auto SuccessOrErr = lazyLoadModuleMetadataBlock();
 862     if (!SuccessOrErr)
 863       return SuccessOrErr.takeError();
 864     if (SuccessOrErr.get()) {
 865       // An index was successfully created and we will be able to load metadata
 866       // on-demand.
 867       MetadataList.resize(MDStringRef.size() +
 868                           GlobalMetadataBitPosIndex.size());
 869
 870       // Reading the named metadata created forward references and/or
 871       // placeholders, that we flush here.
 872       resolveForwardRefsAndPlaceholders(Placeholders);
 873       upgradeDebugInfo();
 874       // Return at the beginning of the block, since it is easy to skip it
 875       // entirely from there.
 876       Stream.ReadBlockEnd(); // Pop the abbrev block context.
 877       Stream.JumpToBit(EntryPos);
 878       if (Stream.SkipBlock())
 879         return error("Invalid record");
 880       return Error::success();
 881     }
 882     // Couldn't load an index, fallback to loading all the block "old-style".
 883   }
 884
 885   unsigned NextMetadataNo = MetadataList.size();
 886
 887   // Read all the records.
 888   while (true) {
 889     BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
 890
 891     switch (Entry.Kind) {
 892     case BitstreamEntry::SubBlock: // Handled for us already.
 893     case BitstreamEntry::Error:
 894       return error("Malformed block");
 895     case BitstreamEntry::EndBlock:
 896       resolveForwardRefsAndPlaceholders(Placeholders);
 897       upgradeDebugInfo();
 898       return Error::success();
 899     case BitstreamEntry::Record:
 900       // The interesting case.
 901       break;
 902     }
 903
 904     // Read a record.
 905     Record.clear();
 906     StringRef Blob;
 907     ++NumMDRecordLoaded;
 908     unsigned Code = Stream.readRecord(Entry.ID, Record, &Blob);
 909     if (Error Err =
 910             parseOneMetadata(Record, Code, Placeholders, Blob, NextMetadataNo))
 911       return Err;
 912   }
 913 }
 914
 915 MDString *MetadataLoader::MetadataLoaderImpl::lazyLoadOneMDString(unsigned ID) {
 916   ++NumMDStringLoaded;
 917   if (Metadata *MD = MetadataList.lookup(ID))
 918     return cast<MDString>(MD);
 919   auto MDS = MDString::get(Context, MDStringRef[ID]);
 920   MetadataList.assignValue(MDS, ID);
 921   return MDS;
 922 }
 923
 924 void MetadataLoader::MetadataLoaderImpl::lazyLoadOneMetadata(
 925     unsigned ID, PlaceholderQueue &Placeholders) {
 926   assert(ID < (MDStringRef.size()) + GlobalMetadataBitPosIndex.size());
 927   assert(ID >= MDStringRef.size() && "Unexpected lazy-loading of MDString");
 928   // Lookup first if the metadata hasn't already been loaded.
 929   if (auto *MD = MetadataList.lookup(ID)) {
 930     auto *N = dyn_cast_or_null<MDNode>(MD);
 931     if (!N->isTemporary())
 932       return;
 933   }
 934   SmallVector<uint64_t, 64> Record;
 935   StringRef Blob;
 936   IndexCursor.JumpToBit(GlobalMetadataBitPosIndex[ID - MDStringRef.size()]);
 937   auto Entry = IndexCursor.advanceSkippingSubblocks();
 938   ++NumMDRecordLoaded;
 939   unsigned Code = IndexCursor.readRecord(Entry.ID, Record, &Blob);
 940   if (Error Err = parseOneMetadata(Record, Code, Placeholders, Blob, ID))
 941     report_fatal_error("Can't lazyload MD");
 942 }
 943
 944 /// Ensure that all forward-references and placeholders are resolved.
 945 /// Iteratively lazy-loading metadata on-demand if needed.
 946 void MetadataLoader::MetadataLoaderImpl::resolveForwardRefsAndPlaceholders(
 947     PlaceholderQueue &Placeholders) {
 948   DenseSet<unsigned> Temporaries;
 949   while (1) {
 950     // Populate Temporaries with the placeholders that haven't been loaded yet.
 951     Placeholders.getTemporaries(MetadataList, Temporaries);
 952
 953     // If we don't have any temporary, or FwdReference, we're done!
 954     if (Temporaries.empty() && !MetadataList.hasFwdRefs())
 955       break;
 956
 957     // First, load all the temporaries. This can add new placeholders or
 958     // forward references.
 959     for (auto ID : Temporaries)
 960       lazyLoadOneMetadata(ID, Placeholders);
 961     Temporaries.clear();
 962
 963     // Second, load the forward-references. This can also add new placeholders
 964     // or forward references.
 965     while (MetadataList.hasFwdRefs())
 966       lazyLoadOneMetadata(MetadataList.getNextFwdRef(), Placeholders);
 967   }
 968   // At this point we don't have any forward reference remaining, or temporary
 969   // that haven't been loaded. We can safely drop RAUW support and mark cycles
 970   // as resolved.
 971   MetadataList.tryToResolveCycles();
 972
 973   // Finally, everything is in place, we can replace the placeholders operands
 974   // with the final node they refer to.
 975   Placeholders.flush(MetadataList);
 976 }
 977
 978 Error MetadataLoader::MetadataLoaderImpl::parseOneMetadata(
 979     SmallVectorImpl<uint64_t> &Record, unsigned Code,
 980     PlaceholderQueue &Placeholders, StringRef Blob, unsigned &NextMetadataNo) {
 981
 982   bool IsDistinct = false;
 983   auto getMD = [&](unsigned ID) -> Metadata * {
 984     if (ID < MDStringRef.size())
 985       return lazyLoadOneMDString(ID);
 986     if (!IsDistinct) {
 987       if (auto *MD = MetadataList.lookup(ID))
 988         return MD;
 989       // If lazy-loading is enabled, we try recursively to load the operand
 990       // instead of creating a temporary.
 991       if (ID < (MDStringRef.size() + GlobalMetadataBitPosIndex.size())) {
 992         // Create a temporary for the node that is referencing the operand we
 993         // will lazy-load. It is needed before recursing in case there are
 994         // uniquing cycles.
 995         MetadataList.getMetadataFwdRef(NextMetadataNo);
 996         lazyLoadOneMetadata(ID, Placeholders);
 997         return MetadataList.lookup(ID);
 998       }
 999       // Return a temporary.
1000       return MetadataList.getMetadataFwdRef(ID);
1001     }
1002     if (auto *MD = MetadataList.getMetadataIfResolved(ID))
1003       return MD;
1004     return &Placeholders.getPlaceholderOp(ID);
1005   };
1006   auto getMDOrNull = [&](unsigned ID) -> Metadata * {
1007     if (ID)
1008       return getMD(ID - 1);
1009     return nullptr;
1010   };
1011   auto getMDOrNullWithoutPlaceholders = [&](unsigned ID) -> Metadata * {
1012     if (ID)
1013       return MetadataList.getMetadataFwdRef(ID - 1);
1014     return nullptr;
1015   };
1016   auto getMDString = [&](unsigned ID) -> MDString * {
1017     // This requires that the ID is not really a forward reference.  In
1018     // particular, the MDString must already have been resolved.
1019     auto MDS = getMDOrNull(ID);
1020     return cast_or_null<MDString>(MDS);
1021   };
1022
1023   // Support for old type refs.
1024   auto getDITypeRefOrNull = [&](unsigned ID) {
1025     return MetadataList.upgradeTypeRef(getMDOrNull(ID));
1026   };
1027
1028 #define GET_OR_DISTINCT(CLASS, ARGS)                                           \
1029   (IsDistinct ? CLASS::getDistinct ARGS : CLASS::get ARGS)
1030
1031   switch (Code) {
1032   default: // Default behavior: ignore.
1033     break;
1034   case bitc::METADATA_NAME: {
1035     // Read name of the named metadata.
1036     SmallString<8> Name(Record.begin(), Record.end());
1037     Record.clear();
1038     Code = Stream.ReadCode();
1039
1040     ++NumMDRecordLoaded;
1041     unsigned NextBitCode = Stream.readRecord(Code, Record);
1042     if (NextBitCode != bitc::METADATA_NAMED_NODE)
1043       return error("METADATA_NAME not followed by METADATA_NAMED_NODE");
1044
1045     // Read named metadata elements.
1046     unsigned Size = Record.size();
1047     NamedMDNode *NMD = TheModule.getOrInsertNamedMetadata(Name);
1048     for (unsigned i = 0; i != Size; ++i) {
1049       MDNode *MD = MetadataList.getMDNodeFwdRefOrNull(Record[i]);
1050       if (!MD)
1051         return error("Invalid record");
1052       NMD->addOperand(MD);
1053     }
1054     break;
1055   }
1056   case bitc::METADATA_OLD_FN_NODE: {
1057     // FIXME: Remove in 4.0.
1058     // This is a LocalAsMetadata record, the only type of function-local
1059     // metadata.
1060     if (Record.size() % 2 == 1)
1061       return error("Invalid record");
1062
1063     // If this isn't a LocalAsMetadata record, we're dropping it.  This used
1064     // to be legal, but there's no upgrade path.
1065     auto dropRecord = [&] {
1066       MetadataList.assignValue(MDNode::get(Context, None), NextMetadataNo);
1067       NextMetadataNo++;
1068     };
1069     if (Record.size() != 2) {
1070       dropRecord();
1071       break;
1072     }
1073
1074     Type *Ty = getTypeByID(Record[0]);
1075     if (Ty->isMetadataTy() || Ty->isVoidTy()) {
1076       dropRecord();
1077       break;
1078     }
1079
1080     MetadataList.assignValue(
1081         LocalAsMetadata::get(ValueList.getValueFwdRef(Record[1], Ty)),
1082         NextMetadataNo);
1083     NextMetadataNo++;
1084     break;
1085   }
1086   case bitc::METADATA_OLD_NODE: {
1087     // FIXME: Remove in 4.0.
1088     if (Record.size() % 2 == 1)
1089       return error("Invalid record");
1090
1091     unsigned Size = Record.size();
1092     SmallVector<Metadata *, 8> Elts;
1093     for (unsigned i = 0; i != Size; i += 2) {
1094       Type *Ty = getTypeByID(Record[i]);
1095       if (!Ty)
1096         return error("Invalid record");
1097       if (Ty->isMetadataTy())
1098         Elts.push_back(getMD(Record[i + 1]));
1099       else if (!Ty->isVoidTy()) {
1100         auto *MD =
1101             ValueAsMetadata::get(ValueList.getValueFwdRef(Record[i + 1], Ty));
1102         assert(isa<ConstantAsMetadata>(MD) &&
1103                "Expected non-function-local metadata");
1104         Elts.push_back(MD);
1105       } else
1106         Elts.push_back(nullptr);
1107     }
1108     MetadataList.assignValue(MDNode::get(Context, Elts), NextMetadataNo);
1109     NextMetadataNo++;
1110     break;
1111   }
1112   case bitc::METADATA_VALUE: {
1113     if (Record.size() != 2)
1114       return error("Invalid record");
1115
1116     Type *Ty = getTypeByID(Record[0]);
1117     if (Ty->isMetadataTy() || Ty->isVoidTy())
1118       return error("Invalid record");
1119
1120     MetadataList.assignValue(
1121         ValueAsMetadata::get(ValueList.getValueFwdRef(Record[1], Ty)),
1122         NextMetadataNo);
1123     NextMetadataNo++;
1124     break;
1125   }
1126   case bitc::METADATA_DISTINCT_NODE:
1127     IsDistinct = true;
1128     LLVM_FALLTHROUGH;
1129   case bitc::METADATA_NODE: {
1130     SmallVector<Metadata *, 8> Elts;
1131     Elts.reserve(Record.size());
1132     for (unsigned ID : Record)
1133       Elts.push_back(getMDOrNull(ID));
1134     MetadataList.assignValue(IsDistinct ? MDNode::getDistinct(Context, Elts)
1135                                         : MDNode::get(Context, Elts),
1136                              NextMetadataNo);
1137     NextMetadataNo++;
1138     break;
1139   }
1140   case bitc::METADATA_LOCATION: {
1141     if (Record.size() != 5)
1142       return error("Invalid record");
1143
1144     IsDistinct = Record[0];
1145     unsigned Line = Record[1];
1146     unsigned Column = Record[2];
1147     Metadata *Scope = getMD(Record[3]);
1148     Metadata *InlinedAt = getMDOrNull(Record[4]);
1149     MetadataList.assignValue(
1150         GET_OR_DISTINCT(DILocation, (Context, Line, Column, Scope, InlinedAt)),
1151         NextMetadataNo);
1152     NextMetadataNo++;
1153     break;
1154   }
1155   case bitc::METADATA_GENERIC_DEBUG: {
1156     if (Record.size() < 4)
1157       return error("Invalid record");
1158
1159     IsDistinct = Record[0];
1160     unsigned Tag = Record[1];
1161     unsigned Version = Record[2];
1162
1163     if (Tag >= 1u << 16 || Version != 0)
1164       return error("Invalid record");
1165
1166     auto *Header = getMDString(Record[3]);
1167     SmallVector<Metadata *, 8> DwarfOps;
1168     for (unsigned I = 4, E = Record.size(); I != E; ++I)
1169       DwarfOps.push_back(getMDOrNull(Record[I]));
1170     MetadataList.assignValue(
1171         GET_OR_DISTINCT(GenericDINode, (Context, Tag, Header, DwarfOps)),
1172         NextMetadataNo);
1173     NextMetadataNo++;
1174     break;
1175   }
1176   case bitc::METADATA_SUBRANGE: {
1177     if (Record.size() != 3)
1178       return error("Invalid record");
1179
1180     IsDistinct = Record[0];
1181     MetadataList.assignValue(
1182         GET_OR_DISTINCT(DISubrange,
1183                         (Context, Record[1], unrotateSign(Record[2]))),
1184         NextMetadataNo);
1185     NextMetadataNo++;
1186     break;
1187   }
1188   case bitc::METADATA_ENUMERATOR: {
1189     if (Record.size() != 3)
1190       return error("Invalid record");
1191
1192     IsDistinct = Record[0];
1193     MetadataList.assignValue(
1194         GET_OR_DISTINCT(DIEnumerator, (Context, unrotateSign(Record[1]),
1195                                        getMDString(Record[2]))),
1196         NextMetadataNo);
1197     NextMetadataNo++;
1198     break;
1199   }
1200   case bitc::METADATA_BASIC_TYPE: {
1201     if (Record.size() != 6)
1202       return error("Invalid record");
1203
1204     IsDistinct = Record[0];
1205     MetadataList.assignValue(
1206         GET_OR_DISTINCT(DIBasicType,
1207                         (Context, Record[1], getMDString(Record[2]), Record[3],
1208                          Record[4], Record[5])),
1209         NextMetadataNo);
1210     NextMetadataNo++;
1211     break;
1212   }
1213   case bitc::METADATA_DERIVED_TYPE: {
1214     if (Record.size() < 12 || Record.size() > 13)
1215       return error("Invalid record");
1216
1217     // DWARF address space is encoded as N->getDWARFAddressSpace() + 1. 0 means
1218     // that there is no DWARF address space associated with DIDerivedType.
1219     Optional<unsigned> DWARFAddressSpace;
1220     if (Record.size() > 12 && Record[12])
1221       DWARFAddressSpace = Record[12] - 1;
1222
1223     IsDistinct = Record[0];
1224     DINode::DIFlags Flags = static_cast<DINode::DIFlags>(Record[10]);
1225     MetadataList.assignValue(
1226         GET_OR_DISTINCT(DIDerivedType,
1227                         (Context, Record[1], getMDString(Record[2]),
1228                          getMDOrNull(Record[3]), Record[4],
1229                          getDITypeRefOrNull(Record[5]),
1230                          getDITypeRefOrNull(Record[6]), Record[7], Record[8],
1231                          Record[9], DWARFAddressSpace, Flags,
1232                          getDITypeRefOrNull(Record[11]))),
1233         NextMetadataNo);
1234     NextMetadataNo++;
1235     break;
1236   }
1237   case bitc::METADATA_COMPOSITE_TYPE: {
1238     if (Record.size() != 16)
1239       return error("Invalid record");
1240
1241     // If we have a UUID and this is not a forward declaration, lookup the
1242     // mapping.
1243     IsDistinct = Record[0] & 0x1;
1244     bool IsNotUsedInTypeRef = Record[0] >= 2;
1245     unsigned Tag = Record[1];
1246     MDString *Name = getMDString(Record[2]);
1247     Metadata *File = getMDOrNull(Record[3]);
1248     unsigned Line = Record[4];
1249     Metadata *Scope = getDITypeRefOrNull(Record[5]);
1250     Metadata *BaseType = nullptr;
1251     uint64_t SizeInBits = Record[7];
1252     if (Record[8] > (uint64_t)std::numeric_limits<uint32_t>::max())
1253       return error("Alignment value is too large");
1254     uint32_t AlignInBits = Record[8];
1255     uint64_t OffsetInBits = 0;
1256     DINode::DIFlags Flags = static_cast<DINode::DIFlags>(Record[10]);
1257     Metadata *Elements = nullptr;
1258     unsigned RuntimeLang = Record[12];
1259     Metadata *VTableHolder = nullptr;
1260     Metadata *TemplateParams = nullptr;
1261     auto *Identifier = getMDString(Record[15]);
1262     // If this module is being parsed so that it can be ThinLTO imported
1263     // into another module, composite types only need to be imported
1264     // as type declarations (unless full type definitions requested).
1265     // Create type declarations up front to save memory. Also, buildODRType
1266     // handles the case where this is type ODRed with a definition needed
1267     // by the importing module, in which case the existing definition is
1268     // used.
1269     if (IsImporting && !ImportFullTypeDefinitions && Identifier &&
1270         (Tag == dwarf::DW_TAG_enumeration_type ||
1271          Tag == dwarf::DW_TAG_class_type ||
1272          Tag == dwarf::DW_TAG_structure_type ||
1273          Tag == dwarf::DW_TAG_union_type)) {
1274       Flags = Flags | DINode::FlagFwdDecl;
1275     } else {
1276       BaseType = getDITypeRefOrNull(Record[6]);
1277       OffsetInBits = Record[9];
1278       Elements = getMDOrNull(Record[11]);
1279       VTableHolder = getDITypeRefOrNull(Record[13]);
1280       TemplateParams = getMDOrNull(Record[14]);
1281     }
1282     DICompositeType *CT = nullptr;
1283     if (Identifier)
1284       CT = DICompositeType::buildODRType(
1285           Context, *Identifier, Tag, Name, File, Line, Scope, BaseType,
1286           SizeInBits, AlignInBits, OffsetInBits, Flags, Elements, RuntimeLang,
1287           VTableHolder, TemplateParams);
1288
1289     // Create a node if we didn't get a lazy ODR type.
1290     if (!CT)
1291       CT = GET_OR_DISTINCT(DICompositeType,
1292                            (Context, Tag, Name, File, Line, Scope, BaseType,
1293                             SizeInBits, AlignInBits, OffsetInBits, Flags,
1294                             Elements, RuntimeLang, VTableHolder, TemplateParams,
1295                             Identifier));
1296     if (!IsNotUsedInTypeRef && Identifier)
1297       MetadataList.addTypeRef(*Identifier, *cast<DICompositeType>(CT));
1298
1299     MetadataList.assignValue(CT, NextMetadataNo);
1300     NextMetadataNo++;
1301     break;
1302   }
1303   case bitc::METADATA_SUBROUTINE_TYPE: {
1304     if (Record.size() < 3 || Record.size() > 4)
1305       return error("Invalid record");
1306     bool IsOldTypeRefArray = Record[0] < 2;
1307     unsigned CC = (Record.size() > 3) ? Record[3] : 0;
1308
1309     IsDistinct = Record[0] & 0x1;
1310     DINode::DIFlags Flags = static_cast<DINode::DIFlags>(Record[1]);
1311     Metadata *Types = getMDOrNull(Record[2]);
1312     if (LLVM_UNLIKELY(IsOldTypeRefArray))
1313       Types = MetadataList.upgradeTypeRefArray(Types);
1314
1315     MetadataList.assignValue(
1316         GET_OR_DISTINCT(DISubroutineType, (Context, Flags, CC, Types)),
1317         NextMetadataNo);
1318     NextMetadataNo++;
1319     break;
1320   }
1321
1322   case bitc::METADATA_MODULE: {
1323     if (Record.size() != 6)
1324       return error("Invalid record");
1325
1326     IsDistinct = Record[0];
1327     MetadataList.assignValue(
1328         GET_OR_DISTINCT(DIModule,
1329                         (Context, getMDOrNull(Record[1]),
1330                          getMDString(Record[2]), getMDString(Record[3]),
1331                          getMDString(Record[4]), getMDString(Record[5]))),
1332         NextMetadataNo);
1333     NextMetadataNo++;
1334     break;
1335   }
1336
1337   case bitc::METADATA_FILE: {
1338     if (Record.size() != 3 && Record.size() != 5)
1339       return error("Invalid record");
1340
1341     IsDistinct = Record[0];
1342     MetadataList.assignValue(
1343         GET_OR_DISTINCT(
1344             DIFile,
1345             (Context, getMDString(Record[1]), getMDString(Record[2]),
1346              Record.size() == 3 ? DIFile::CSK_None
1347                                 : static_cast<DIFile::ChecksumKind>(Record[3]),
1348              Record.size() == 3 ? nullptr : getMDString(Record[4]))),
1349         NextMetadataNo);
1350     NextMetadataNo++;
1351     break;
1352   }
1353   case bitc::METADATA_COMPILE_UNIT: {
1354     if (Record.size() < 14 || Record.size() > 19)
1355       return error("Invalid record");
1356
1357     // Ignore Record[0], which indicates whether this compile unit is
1358     // distinct.  It's always distinct.
1359     IsDistinct = true;
1360     auto *CU = DICompileUnit::getDistinct(
1361         Context, Record[1], getMDOrNull(Record[2]), getMDString(Record[3]),
1362         Record[4], getMDString(Record[5]), Record[6], getMDString(Record[7]),
1363         Record[8], getMDOrNull(Record[9]), getMDOrNull(Record[10]),
1364         getMDOrNull(Record[12]), getMDOrNull(Record[13]),
1365         Record.size() <= 15 ? nullptr : getMDOrNull(Record[15]),
1366         Record.size() <= 14 ? 0 : Record[14],
1367         Record.size() <= 16 ? true : Record[16],
1368         Record.size() <= 17 ? false : Record[17],
1369         Record.size() <= 18 ? false : Record[18]);
1370
1371     MetadataList.assignValue(CU, NextMetadataNo);
1372     NextMetadataNo++;
1373
1374     // Move the Upgrade the list of subprograms.
1375     if (Metadata *SPs = getMDOrNullWithoutPlaceholders(Record[11]))
1376       CUSubprograms.push_back({CU, SPs});
1377     break;
1378   }
1379   case bitc::METADATA_SUBPROGRAM: {
1380     if (Record.size() < 18 || Record.size() > 21)
1381       return error("Invalid record");
1382
1383     IsDistinct =
1384         (Record[0] & 1) || Record[8]; // All definitions should be distinct.
1385     // Version 1 has a Function as Record[15].
1386     // Version 2 has removed Record[15].
1387     // Version 3 has the Unit as Record[15].
1388     // Version 4 added thisAdjustment.
1389     bool HasUnit = Record[0] >= 2;
1390     if (HasUnit && Record.size() < 19)
1391       return error("Invalid record");
1392     Metadata *CUorFn = getMDOrNull(Record[15]);
1393     unsigned Offset = Record.size() >= 19 ? 1 : 0;
1394     bool HasFn = Offset && !HasUnit;
1395     bool HasThisAdj = Record.size() >= 20;
1396     bool HasThrownTypes = Record.size() >= 21;
1397     DISubprogram *SP = GET_OR_DISTINCT(
1398         DISubprogram,
1399         (Context,
1400          getDITypeRefOrNull(Record[1]),                     // scope
1401          getMDString(Record[2]),                            // name
1402          getMDString(Record[3]),                            // linkageName
1403          getMDOrNull(Record[4]),                            // file
1404          Record[5],                                         // line
1405          getMDOrNull(Record[6]),                            // type
1406          Record[7],                                         // isLocal
1407          Record[8],                                         // isDefinition
1408          Record[9],                                         // scopeLine
1409          getDITypeRefOrNull(Record[10]),                    // containingType
1410          Record[11],                                        // virtuality
1411          Record[12],                                        // virtualIndex
1412          HasThisAdj ? Record[19] : 0,                       // thisAdjustment
1413          static_cast<DINode::DIFlags>(Record[13]),          // flags
1414          Record[14],                                        // isOptimized
1415          HasUnit ? CUorFn : nullptr,                        // unit
1416          getMDOrNull(Record[15 + Offset]),                  // templateParams
1417          getMDOrNull(Record[16 + Offset]),                  // declaration
1418          getMDOrNull(Record[17 + Offset]),                  // variables
1419          HasThrownTypes ? getMDOrNull(Record[20]) : nullptr // thrownTypes
1420          ));
1421     MetadataList.assignValue(SP, NextMetadataNo);
1422     NextMetadataNo++;
1423
1424     // Upgrade sp->function mapping to function->sp mapping.
1425     if (HasFn) {
1426       if (auto *CMD = dyn_cast_or_null<ConstantAsMetadata>(CUorFn))
1427         if (auto *F = dyn_cast<Function>(CMD->getValue())) {
1428           if (F->isMaterializable())
1429             // Defer until materialized; unmaterialized functions may not have
1430             // metadata.
1431             FunctionsWithSPs[F] = SP;
1432           else if (!F->empty())
1433             F->setSubprogram(SP);
1434         }
1435     }
1436     break;
1437   }
1438   case bitc::METADATA_LEXICAL_BLOCK: {
1439     if (Record.size() != 5)
1440       return error("Invalid record");
1441
1442     IsDistinct = Record[0];
1443     MetadataList.assignValue(
1444         GET_OR_DISTINCT(DILexicalBlock,
1445                         (Context, getMDOrNull(Record[1]),
1446                          getMDOrNull(Record[2]), Record[3], Record[4])),
1447         NextMetadataNo);
1448     NextMetadataNo++;
1449     break;
1450   }
1451   case bitc::METADATA_LEXICAL_BLOCK_FILE: {
1452     if (Record.size() != 4)
1453       return error("Invalid record");
1454
1455     IsDistinct = Record[0];
1456     MetadataList.assignValue(
1457         GET_OR_DISTINCT(DILexicalBlockFile,
1458                         (Context, getMDOrNull(Record[1]),
1459                          getMDOrNull(Record[2]), Record[3])),
1460         NextMetadataNo);
1461     NextMetadataNo++;
1462     break;
1463   }
1464   case bitc::METADATA_NAMESPACE: {
1465     // Newer versions of DINamespace dropped file and line.
1466     MDString *Name;
1467     if (Record.size() == 3)
1468       Name = getMDString(Record[2]);
1469     else if (Record.size() == 5)
1470       Name = getMDString(Record[3]);
1471     else
1472       return error("Invalid record");
1473
1474     IsDistinct = Record[0] & 1;
1475     bool ExportSymbols = Record[0] & 2;
1476     MetadataList.assignValue(
1477         GET_OR_DISTINCT(DINamespace,
1478                         (Context, getMDOrNull(Record[1]), Name, ExportSymbols)),
1479         NextMetadataNo);
1480     NextMetadataNo++;
1481     break;
1482   }
1483   case bitc::METADATA_MACRO: {
1484     if (Record.size() != 5)
1485       return error("Invalid record");
1486
1487     IsDistinct = Record[0];
1488     MetadataList.assignValue(
1489         GET_OR_DISTINCT(DIMacro,
1490                         (Context, Record[1], Record[2], getMDString(Record[3]),
1491                          getMDString(Record[4]))),
1492         NextMetadataNo);
1493     NextMetadataNo++;
1494     break;
1495   }
1496   case bitc::METADATA_MACRO_FILE: {
1497     if (Record.size() != 5)
1498       return error("Invalid record");
1499
1500     IsDistinct = Record[0];
1501     MetadataList.assignValue(
1502         GET_OR_DISTINCT(DIMacroFile,
1503                         (Context, Record[1], Record[2], getMDOrNull(Record[3]),
1504                          getMDOrNull(Record[4]))),
1505         NextMetadataNo);
1506     NextMetadataNo++;
1507     break;
1508   }
1509   case bitc::METADATA_TEMPLATE_TYPE: {
1510     if (Record.size() != 3)
1511       return error("Invalid record");
1512
1513     IsDistinct = Record[0];
1514     MetadataList.assignValue(GET_OR_DISTINCT(DITemplateTypeParameter,
1515                                              (Context, getMDString(Record[1]),
1516                                               getDITypeRefOrNull(Record[2]))),
1517                              NextMetadataNo);
1518     NextMetadataNo++;
1519     break;
1520   }
1521   case bitc::METADATA_TEMPLATE_VALUE: {
1522     if (Record.size() != 5)
1523       return error("Invalid record");
1524
1525     IsDistinct = Record[0];
1526     MetadataList.assignValue(
1527         GET_OR_DISTINCT(DITemplateValueParameter,
1528                         (Context, Record[1], getMDString(Record[2]),
1529                          getDITypeRefOrNull(Record[3]),
1530                          getMDOrNull(Record[4]))),
1531         NextMetadataNo);
1532     NextMetadataNo++;
1533     break;
1534   }
1535   case bitc::METADATA_GLOBAL_VAR: {
1536     if (Record.size() < 11 || Record.size() > 12)
1537       return error("Invalid record");
1538
1539     IsDistinct = Record[0] & 1;
1540     unsigned Version = Record[0] >> 1;
1541
1542     if (Version == 1) {
1543       MetadataList.assignValue(
1544           GET_OR_DISTINCT(DIGlobalVariable,
1545                           (Context, getMDOrNull(Record[1]),
1546                            getMDString(Record[2]), getMDString(Record[3]),
1547                            getMDOrNull(Record[4]), Record[5],
1548                            getDITypeRefOrNull(Record[6]), Record[7], Record[8],
1549                            getMDOrNull(Record[10]), Record[11])),
1550           NextMetadataNo);
1551       NextMetadataNo++;
1552     } else if (Version == 0) {
1553       // Upgrade old metadata, which stored a global variable reference or a
1554       // ConstantInt here.
1555       NeedUpgradeToDIGlobalVariableExpression = true;
1556       Metadata *Expr = getMDOrNull(Record[9]);
1557       uint32_t AlignInBits = 0;
1558       if (Record.size() > 11) {
1559         if (Record[11] > (uint64_t)std::numeric_limits<uint32_t>::max())
1560           return error("Alignment value is too large");
1561         AlignInBits = Record[11];
1562       }
1563       GlobalVariable *Attach = nullptr;
1564       if (auto *CMD = dyn_cast_or_null<ConstantAsMetadata>(Expr)) {
1565         if (auto *GV = dyn_cast<GlobalVariable>(CMD->getValue())) {
1566           Attach = GV;
1567           Expr = nullptr;
1568         } else if (auto *CI = dyn_cast<ConstantInt>(CMD->getValue())) {
1569           Expr = DIExpression::get(Context,
1570                                    {dwarf::DW_OP_constu, CI->getZExtValue(),
1571                                     dwarf::DW_OP_stack_value});
1572         } else {
1573           Expr = nullptr;
1574         }
1575       }
1576       DIGlobalVariable *DGV = GET_OR_DISTINCT(
1577           DIGlobalVariable,
1578           (Context, getMDOrNull(Record[1]), getMDString(Record[2]),
1579            getMDString(Record[3]), getMDOrNull(Record[4]), Record[5],
1580            getDITypeRefOrNull(Record[6]), Record[7], Record[8],
1581            getMDOrNull(Record[10]), AlignInBits));
1582
1583       DIGlobalVariableExpression *DGVE = nullptr;
1584       if (Attach || Expr)
1585         DGVE = DIGlobalVariableExpression::getDistinct(
1586             Context, DGV, Expr ? Expr : DIExpression::get(Context, {}));
1587       if (Attach)
1588         Attach->addDebugInfo(DGVE);
1589
1590       auto *MDNode = Expr ? cast<Metadata>(DGVE) : cast<Metadata>(DGV);
1591       MetadataList.assignValue(MDNode, NextMetadataNo);
1592       NextMetadataNo++;
1593     } else
1594       return error("Invalid record");
1595
1596     break;
1597   }
1598   case bitc::METADATA_LOCAL_VAR: {
1599     // 10th field is for the obseleted 'inlinedAt:' field.
1600     if (Record.size() < 8 || Record.size() > 10)
1601       return error("Invalid record");
1602
1603     IsDistinct = Record[0] & 1;
1604     bool HasAlignment = Record[0] & 2;
1605     // 2nd field used to be an artificial tag, either DW_TAG_auto_variable or
1606     // DW_TAG_arg_variable, if we have alignment flag encoded it means, that
1607     // this is newer version of record which doesn't have artificial tag.
1608     bool HasTag = !HasAlignment && Record.size() > 8;
1609     DINode::DIFlags Flags = static_cast<DINode::DIFlags>(Record[7 + HasTag]);
1610     uint32_t AlignInBits = 0;
1611     if (HasAlignment) {
1612       if (Record[8 + HasTag] > (uint64_t)std::numeric_limits<uint32_t>::max())
1613         return error("Alignment value is too large");
1614       AlignInBits = Record[8 + HasTag];
1615     }
1616     MetadataList.assignValue(
1617         GET_OR_DISTINCT(DILocalVariable,
1618                         (Context, getMDOrNull(Record[1 + HasTag]),
1619                          getMDString(Record[2 + HasTag]),
1620                          getMDOrNull(Record[3 + HasTag]), Record[4 + HasTag],
1621                          getDITypeRefOrNull(Record[5 + HasTag]),
1622                          Record[6 + HasTag], Flags, AlignInBits)),
1623         NextMetadataNo);
1624     NextMetadataNo++;
1625     break;
1626   }
1627   case bitc::METADATA_EXPRESSION: {
1628     if (Record.size() < 1)
1629       return error("Invalid record");
1630
1631     IsDistinct = Record[0] & 1;
1632     uint64_t Version = Record[0] >> 1;
1633     auto Elts = MutableArrayRef<uint64_t>(Record).slice(1);
1634
1635     SmallVector<uint64_t, 6> Buffer;
1636     if (Error Err = upgradeDIExpression(Version, Elts, Buffer))
1637       return Err;
1638
1639     MetadataList.assignValue(
1640         GET_OR_DISTINCT(DIExpression, (Context, Elts)), NextMetadataNo);
1641     NextMetadataNo++;
1642     break;
1643   }
1644   case bitc::METADATA_GLOBAL_VAR_EXPR: {
1645     if (Record.size() != 3)
1646       return error("Invalid record");
1647
1648     IsDistinct = Record[0];
1649     Metadata *Expr = getMDOrNull(Record[2]);
1650     if (!Expr)
1651       Expr = DIExpression::get(Context, {});
1652     MetadataList.assignValue(
1653         GET_OR_DISTINCT(DIGlobalVariableExpression,
1654                         (Context, getMDOrNull(Record[1]), Expr)),
1655         NextMetadataNo);
1656     NextMetadataNo++;
1657     break;
1658   }
1659   case bitc::METADATA_OBJC_PROPERTY: {
1660     if (Record.size() != 8)
1661       return error("Invalid record");
1662
1663     IsDistinct = Record[0];
1664     MetadataList.assignValue(
1665         GET_OR_DISTINCT(DIObjCProperty,
1666                         (Context, getMDString(Record[1]),
1667                          getMDOrNull(Record[2]), Record[3],
1668                          getMDString(Record[4]), getMDString(Record[5]),
1669                          Record[6], getDITypeRefOrNull(Record[7]))),
1670         NextMetadataNo);
1671     NextMetadataNo++;
1672     break;
1673   }
1674   case bitc::METADATA_IMPORTED_ENTITY: {
1675     if (Record.size() != 6 && Record.size() != 7)
1676       return error("Invalid record");
1677
1678     IsDistinct = Record[0];
1679     bool HasFile = (Record.size() == 7);
1680     MetadataList.assignValue(
1681         GET_OR_DISTINCT(DIImportedEntity,
1682                         (Context, Record[1], getMDOrNull(Record[2]),
1683                          getDITypeRefOrNull(Record[3]),
1684                          HasFile ? getMDOrNull(Record[6]) : nullptr,
1685                          HasFile ? Record[4] : 0, getMDString(Record[5]))),
1686         NextMetadataNo);
1687     NextMetadataNo++;
1688     break;
1689   }
1690   case bitc::METADATA_STRING_OLD: {
1691     std::string String(Record.begin(), Record.end());
1692
1693     // Test for upgrading !llvm.loop.
1694     HasSeenOldLoopTags |= mayBeOldLoopAttachmentTag(String);
1695     ++NumMDStringLoaded;
1696     Metadata *MD = MDString::get(Context, String);
1697     MetadataList.assignValue(MD, NextMetadataNo);
1698     NextMetadataNo++;
1699     break;
1700   }
1701   case bitc::METADATA_STRINGS: {
1702     auto CreateNextMDString = [&](StringRef Str) {
1703       ++NumMDStringLoaded;
1704       MetadataList.assignValue(MDString::get(Context, Str), NextMetadataNo);
1705       NextMetadataNo++;
1706     };
1707     if (Error Err = parseMetadataStrings(Record, Blob, CreateNextMDString))
1708       return Err;
1709     break;
1710   }
1711   case bitc::METADATA_GLOBAL_DECL_ATTACHMENT: {
1712     if (Record.size() % 2 == 0)
1713       return error("Invalid record");
1714     unsigned ValueID = Record[0];
1715     if (ValueID >= ValueList.size())
1716       return error("Invalid record");
1717     if (auto *GO = dyn_cast<GlobalObject>(ValueList[ValueID]))
1718       if (Error Err = parseGlobalObjectAttachment(
1719               *GO, ArrayRef<uint64_t>(Record).slice(1)))
1720         return Err;
1721     break;
1722   }
1723   case bitc::METADATA_KIND: {
1724     // Support older bitcode files that had METADATA_KIND records in a
1725     // block with METADATA_BLOCK_ID.
1726     if (Error Err = parseMetadataKindRecord(Record))
1727       return Err;
1728     break;
1729   }
1730   }
1731   return Error::success();
1732 #undef GET_OR_DISTINCT
1733 }
1734
1735 Error MetadataLoader::MetadataLoaderImpl::parseMetadataStrings(
1736     ArrayRef<uint64_t> Record, StringRef Blob,
1737     function_ref<void(StringRef)> CallBack) {
1738   // All the MDStrings in the block are emitted together in a single
1739   // record.  The strings are concatenated and stored in a blob along with
1740   // their sizes.
1741   if (Record.size() != 2)
1742     return error("Invalid record: metadata strings layout");
1743
1744   unsigned NumStrings = Record[0];
1745   unsigned StringsOffset = Record[1];
1746   if (!NumStrings)
1747     return error("Invalid record: metadata strings with no strings");
1748   if (StringsOffset > Blob.size())
1749     return error("Invalid record: metadata strings corrupt offset");
1750
1751   StringRef Lengths = Blob.slice(0, StringsOffset);
1752   SimpleBitstreamCursor R(Lengths);
1753
1754   StringRef Strings = Blob.drop_front(StringsOffset);
1755   do {
1756     if (R.AtEndOfStream())
1757       return error("Invalid record: metadata strings bad length");
1758
1759     unsigned Size = R.ReadVBR(6);
1760     if (Strings.size() < Size)
1761       return error("Invalid record: metadata strings truncated chars");
1762
1763     CallBack(Strings.slice(0, Size));
1764     Strings = Strings.drop_front(Size);
1765   } while (--NumStrings);
1766
1767   return Error::success();
1768 }
1769
1770 Error MetadataLoader::MetadataLoaderImpl::parseGlobalObjectAttachment(
1771     GlobalObject &GO, ArrayRef<uint64_t> Record) {
1772   assert(Record.size() % 2 == 0);
1773   for (unsigned I = 0, E = Record.size(); I != E; I += 2) {
1774     auto K = MDKindMap.find(Record[I]);
1775     if (K == MDKindMap.end())
1776       return error("Invalid ID");
1777     MDNode *MD = MetadataList.getMDNodeFwdRefOrNull(Record[I + 1]);
1778     if (!MD)
1779       return error("Invalid metadata attachment");
1780     GO.addMetadata(K->second, *MD);
1781   }
1782   return Error::success();
1783 }
1784
1785 /// Parse metadata attachments.
1786 Error MetadataLoader::MetadataLoaderImpl::parseMetadataAttachment(
1787     Function &F, const SmallVectorImpl<Instruction *> &InstructionList) {
1788   if (Stream.EnterSubBlock(bitc::METADATA_ATTACHMENT_ID))
1789     return error("Invalid record");
1790
1791   SmallVector<uint64_t, 64> Record;
1792   PlaceholderQueue Placeholders;
1793
1794   while (true) {
1795     BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
1796
1797     switch (Entry.Kind) {
1798     case BitstreamEntry::SubBlock: // Handled for us already.
1799     case BitstreamEntry::Error:
1800       return error("Malformed block");
1801     case BitstreamEntry::EndBlock:
1802       resolveForwardRefsAndPlaceholders(Placeholders);
1803       return Error::success();
1804     case BitstreamEntry::Record:
1805       // The interesting case.
1806       break;
1807     }
1808
1809     // Read a metadata attachment record.
1810     Record.clear();
1811     ++NumMDRecordLoaded;
1812     switch (Stream.readRecord(Entry.ID, Record)) {
1813     default: // Default behavior: ignore.
1814       break;
1815     case bitc::METADATA_ATTACHMENT: {
1816       unsigned RecordLength = Record.size();
1817       if (Record.empty())
1818         return error("Invalid record");
1819       if (RecordLength % 2 == 0) {
1820         // A function attachment.
1821         if (Error Err = parseGlobalObjectAttachment(F, Record))
1822           return Err;
1823         continue;
1824       }
1825
1826       // An instruction attachment.
1827       Instruction *Inst = InstructionList[Record[0]];
1828       for (unsigned i = 1; i != RecordLength; i = i + 2) {
1829         unsigned Kind = Record[i];
1830         DenseMap<unsigned, unsigned>::iterator I = MDKindMap.find(Kind);
1831         if (I == MDKindMap.end())
1832           return error("Invalid ID");
1833         if (I->second == LLVMContext::MD_tbaa && StripTBAA)
1834           continue;
1835
1836         auto Idx = Record[i + 1];
1837         if (Idx < (MDStringRef.size() + GlobalMetadataBitPosIndex.size()) &&
1838             !MetadataList.lookup(Idx)) {
1839           // Load the attachment if it is in the lazy-loadable range and hasn't
1840           // been loaded yet.
1841           lazyLoadOneMetadata(Idx, Placeholders);
1842           resolveForwardRefsAndPlaceholders(Placeholders);
1843         }
1844
1845         Metadata *Node = MetadataList.getMetadataFwdRef(Idx);
1846         if (isa<LocalAsMetadata>(Node))
1847           // Drop the attachment.  This used to be legal, but there's no
1848           // upgrade path.
1849           break;
1850         MDNode *MD = dyn_cast_or_null<MDNode>(Node);
1851         if (!MD)
1852           return error("Invalid metadata attachment");
1853
1854         if (HasSeenOldLoopTags && I->second == LLVMContext::MD_loop)
1855           MD = upgradeInstructionLoopAttachment(*MD);
1856
1857         if (I->second == LLVMContext::MD_tbaa) {
1858           assert(!MD->isTemporary() && "should load MDs before attachments");
1859           MD = UpgradeTBAANode(*MD);
1860         }
1861         Inst->setMetadata(I->second, MD);
1862       }
1863       break;
1864     }
1865     }
1866   }
1867 }
1868
1869 /// Parse a single METADATA_KIND record, inserting result in MDKindMap.
1870 Error MetadataLoader::MetadataLoaderImpl::parseMetadataKindRecord(
1871     SmallVectorImpl<uint64_t> &Record) {
1872   if (Record.size() < 2)
1873     return error("Invalid record");
1874
1875   unsigned Kind = Record[0];
1876   SmallString<8> Name(Record.begin() + 1, Record.end());
1877
1878   unsigned NewKind = TheModule.getMDKindID(Name.str());
1879   if (!MDKindMap.insert(std::make_pair(Kind, NewKind)).second)
1880     return error("Conflicting METADATA_KIND records");
1881   return Error::success();
1882 }
1883
1884 /// Parse the metadata kinds out of the METADATA_KIND_BLOCK.
1885 Error MetadataLoader::MetadataLoaderImpl::parseMetadataKinds() {
1886   if (Stream.EnterSubBlock(bitc::METADATA_KIND_BLOCK_ID))
1887     return error("Invalid record");
1888
1889   SmallVector<uint64_t, 64> Record;
1890
1891   // Read all the records.
1892   while (true) {
1893     BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
1894
1895     switch (Entry.Kind) {
1896     case BitstreamEntry::SubBlock: // Handled for us already.
1897     case BitstreamEntry::Error:
1898       return error("Malformed block");
1899     case BitstreamEntry::EndBlock:
1900       return Error::success();
1901     case BitstreamEntry::Record:
1902       // The interesting case.
1903       break;
1904     }
1905
1906     // Read a record.
1907     Record.clear();
1908     ++NumMDRecordLoaded;
1909     unsigned Code = Stream.readRecord(Entry.ID, Record);
1910     switch (Code) {
1911     default: // Default behavior: ignore.
1912       break;
1913     case bitc::METADATA_KIND: {
1914       if (Error Err = parseMetadataKindRecord(Record))
1915         return Err;
1916       break;
1917     }
1918     }
1919   }
1920 }
1921
1922 MetadataLoader &MetadataLoader::operator=(MetadataLoader &&RHS) {
1923   Pimpl = std::move(RHS.Pimpl);
1924   return *this;
1925 }
1926 MetadataLoader::MetadataLoader(MetadataLoader &&RHS)
1927     : Pimpl(std::move(RHS.Pimpl)) {}
1928
1929 MetadataLoader::~MetadataLoader() = default;
1930 MetadataLoader::MetadataLoader(BitstreamCursor &Stream, Module &TheModule,
1931                                BitcodeReaderValueList &ValueList,
1932                                bool IsImporting,
1933                                std::function<Type *(unsigned)> getTypeByID)
1934     : Pimpl(llvm::make_unique<MetadataLoaderImpl>(
1935           Stream, TheModule, ValueList, std::move(getTypeByID), IsImporting)) {}
1936
1937 Error MetadataLoader::parseMetadata(bool ModuleLevel) {
1938   return Pimpl->parseMetadata(ModuleLevel);
1939 }
1940
1941 bool MetadataLoader::hasFwdRefs() const { return Pimpl->hasFwdRefs(); }
1942
1943 /// Return the given metadata, creating a replaceable forward reference if
1944 /// necessary.
1945 Metadata *MetadataLoader::getMetadataFwdRefOrLoad(unsigned Idx) {
1946   return Pimpl->getMetadataFwdRefOrLoad(Idx);
1947 }
1948
1949 MDNode *MetadataLoader::getMDNodeFwdRefOrNull(unsigned Idx) {
1950   return Pimpl->getMDNodeFwdRefOrNull(Idx);
1951 }
1952
1953 DISubprogram *MetadataLoader::lookupSubprogramForFunction(Function *F) {
1954   return Pimpl->lookupSubprogramForFunction(F);
1955 }
1956
1957 Error MetadataLoader::parseMetadataAttachment(
1958     Function &F, const SmallVectorImpl<Instruction *> &InstructionList) {
1959   return Pimpl->parseMetadataAttachment(F, InstructionList);
1960 }
1961
1962 Error MetadataLoader::parseMetadataKinds() {
1963   return Pimpl->parseMetadataKinds();
1964 }
1965
1966 void MetadataLoader::setStripTBAA(bool StripTBAA) {
1967   return Pimpl->setStripTBAA(StripTBAA);
1968 }
1969
1970 bool MetadataLoader::isStrippingTBAA() { return Pimpl->isStrippingTBAA(); }
1971
1972 unsigned MetadataLoader::size() const { return Pimpl->size(); }
1973 void MetadataLoader::shrinkTo(unsigned N) { return Pimpl->shrinkTo(N); }
1974
1975 void MetadataLoader::upgradeDebugIntrinsics(Function &F) {
1976   return Pimpl->upgradeDebugIntrinsics(F);
1977 }