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