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

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