lib/IR/DebugInfoMetadata.cpp

   1 //===- DebugInfoMetadata.cpp - Implement debug info metadata --------------===//
   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 // This file implements the debug info Metadata classes.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/IR/DebugInfoMetadata.h"
  14 #include "LLVMContextImpl.h"
  15 #include "MetadataImpl.h"
  16 #include "llvm/ADT/SmallSet.h"
  17 #include "llvm/ADT/StringSwitch.h"
  18 #include "llvm/IR/DIBuilder.h"
  19 #include "llvm/IR/Function.h"
  20 #include "llvm/IR/Instructions.h"
  21
  22 #include <numeric>
  23
  24 using namespace llvm;
  25
  26 DILocation::DILocation(LLVMContext &C, StorageType Storage, unsigned Line,
  27                        unsigned Column, ArrayRef<Metadata *> MDs,
  28                        bool ImplicitCode)
  29     : MDNode(C, DILocationKind, Storage, MDs) {
  30   assert((MDs.size() == 1 || MDs.size() == 2) &&
  31          "Expected a scope and optional inlined-at");
  32
  33   // Set line and column.
  34   assert(Column < (1u << 16) && "Expected 16-bit column");
  35
  36   SubclassData32 = Line;
  37   SubclassData16 = Column;
  38
  39   setImplicitCode(ImplicitCode);
  40 }
  41
  42 static void adjustColumn(unsigned &Column) {
  43   // Set to unknown on overflow.  We only have 16 bits to play with here.
  44   if (Column >= (1u << 16))
  45     Column = 0;
  46 }
  47
  48 DILocation *DILocation::getImpl(LLVMContext &Context, unsigned Line,
  49                                 unsigned Column, Metadata *Scope,
  50                                 Metadata *InlinedAt, bool ImplicitCode,
  51                                 StorageType Storage, bool ShouldCreate) {
  52   // Fixup column.
  53   adjustColumn(Column);
  54
  55   if (Storage == Uniqued) {
  56     if (auto *N = getUniqued(Context.pImpl->DILocations,
  57                              DILocationInfo::KeyTy(Line, Column, Scope,
  58                                                    InlinedAt, ImplicitCode)))
  59       return N;
  60     if (!ShouldCreate)
  61       return nullptr;
  62   } else {
  63     assert(ShouldCreate && "Expected non-uniqued nodes to always be created");
  64   }
  65
  66   SmallVector<Metadata *, 2> Ops;
  67   Ops.push_back(Scope);
  68   if (InlinedAt)
  69     Ops.push_back(InlinedAt);
  70   return storeImpl(new (Ops.size()) DILocation(Context, Storage, Line, Column,
  71                                                Ops, ImplicitCode),
  72                    Storage, Context.pImpl->DILocations);
  73 }
  74
  75 const DILocation *DILocation::getMergedLocation(const DILocation *LocA,
  76                                                 const DILocation *LocB) {
  77   if (!LocA || !LocB)
  78     return nullptr;
  79
  80   if (LocA == LocB)
  81     return LocA;
  82
  83   SmallPtrSet<DILocation *, 5> InlinedLocationsA;
  84   for (DILocation *L = LocA->getInlinedAt(); L; L = L->getInlinedAt())
  85     InlinedLocationsA.insert(L);
  86   SmallSet<std::pair<DIScope *, DILocation *>, 5> Locations;
  87   DIScope *S = LocA->getScope();
  88   DILocation *L = LocA->getInlinedAt();
  89   while (S) {
  90     Locations.insert(std::make_pair(S, L));
  91     S = S->getScope();
  92     if (!S && L) {
  93       S = L->getScope();
  94       L = L->getInlinedAt();
  95     }
  96   }
  97   const DILocation *Result = LocB;
  98   S = LocB->getScope();
  99   L = LocB->getInlinedAt();
 100   while (S) {
 101     if (Locations.count(std::make_pair(S, L)))
 102       break;
 103     S = S->getScope();
 104     if (!S && L) {
 105       S = L->getScope();
 106       L = L->getInlinedAt();
 107     }
 108   }
 109
 110   // If the two locations are irreconsilable, just pick one. This is misleading,
 111   // but on the other hand, it's a "line 0" location.
 112   if (!S || !isa<DILocalScope>(S))
 113     S = LocA->getScope();
 114   return DILocation::get(Result->getContext(), 0, 0, S, L);
 115 }
 116
 117 Optional<unsigned> DILocation::encodeDiscriminator(unsigned BD, unsigned DF, unsigned CI) {
 118   SmallVector<unsigned, 3> Components = {BD, DF, CI};
 119   uint64_t RemainingWork = 0U;
 120   // We use RemainingWork to figure out if we have no remaining components to
 121   // encode. For example: if BD != 0 but DF == 0 && CI == 0, we don't need to
 122   // encode anything for the latter 2.
 123   // Since any of the input components is at most 32 bits, their sum will be
 124   // less than 34 bits, and thus RemainingWork won't overflow.
 125   RemainingWork = std::accumulate(Components.begin(), Components.end(), RemainingWork);
 126
 127   int I = 0;
 128   unsigned Ret = 0;
 129   unsigned NextBitInsertionIndex = 0;
 130   while (RemainingWork > 0) {
 131     unsigned C = Components[I++];
 132     RemainingWork -= C;
 133     unsigned EC = encodeComponent(C);
 134     Ret |= (EC << NextBitInsertionIndex);
 135     NextBitInsertionIndex += encodingBits(C);
 136   }
 137
 138   // Encoding may be unsuccessful because of overflow. We determine success by
 139   // checking equivalence of components before & after encoding. Alternatively,
 140   // we could determine Success during encoding, but the current alternative is
 141   // simpler.
 142   unsigned TBD, TDF, TCI = 0;
 143   decodeDiscriminator(Ret, TBD, TDF, TCI);
 144   if (TBD == BD && TDF == DF && TCI == CI)
 145     return Ret;
 146   return None;
 147 }
 148
 149 void DILocation::decodeDiscriminator(unsigned D, unsigned &BD, unsigned &DF,
 150                                      unsigned &CI) {
 151   BD = getUnsignedFromPrefixEncoding(D);
 152   DF = getUnsignedFromPrefixEncoding(getNextComponentInDiscriminator(D));
 153   CI = getUnsignedFromPrefixEncoding(
 154       getNextComponentInDiscriminator(getNextComponentInDiscriminator(D)));
 155 }
 156
 157
 158 DINode::DIFlags DINode::getFlag(StringRef Flag) {
 159   return StringSwitch<DIFlags>(Flag)
 160 #define HANDLE_DI_FLAG(ID, NAME) .Case("DIFlag" #NAME, Flag##NAME)
 161 #include "llvm/IR/DebugInfoFlags.def"
 162       .Default(DINode::FlagZero);
 163 }
 164
 165 StringRef DINode::getFlagString(DIFlags Flag) {
 166   switch (Flag) {
 167 #define HANDLE_DI_FLAG(ID, NAME)                                               \
 168   case Flag##NAME:                                                             \
 169     return "DIFlag" #NAME;
 170 #include "llvm/IR/DebugInfoFlags.def"
 171   }
 172   return "";
 173 }
 174
 175 DINode::DIFlags DINode::splitFlags(DIFlags Flags,
 176                                    SmallVectorImpl<DIFlags> &SplitFlags) {
 177   // Flags that are packed together need to be specially handled, so
 178   // that, for example, we emit "DIFlagPublic" and not
 179   // "DIFlagPrivate | DIFlagProtected".
 180   if (DIFlags A = Flags & FlagAccessibility) {
 181     if (A == FlagPrivate)
 182       SplitFlags.push_back(FlagPrivate);
 183     else if (A == FlagProtected)
 184       SplitFlags.push_back(FlagProtected);
 185     else
 186       SplitFlags.push_back(FlagPublic);
 187     Flags &= ~A;
 188   }
 189   if (DIFlags R = Flags & FlagPtrToMemberRep) {
 190     if (R == FlagSingleInheritance)
 191       SplitFlags.push_back(FlagSingleInheritance);
 192     else if (R == FlagMultipleInheritance)
 193       SplitFlags.push_back(FlagMultipleInheritance);
 194     else
 195       SplitFlags.push_back(FlagVirtualInheritance);
 196     Flags &= ~R;
 197   }
 198   if ((Flags & FlagIndirectVirtualBase) == FlagIndirectVirtualBase) {
 199     Flags &= ~FlagIndirectVirtualBase;
 200     SplitFlags.push_back(FlagIndirectVirtualBase);
 201   }
 202
 203 #define HANDLE_DI_FLAG(ID, NAME)                                               \
 204   if (DIFlags Bit = Flags & Flag##NAME) {                                      \
 205     SplitFlags.push_back(Bit);                                                 \
 206     Flags &= ~Bit;                                                             \
 207   }
 208 #include "llvm/IR/DebugInfoFlags.def"
 209   return Flags;
 210 }
 211
 212 DIScope *DIScope::getScope() const {
 213   if (auto *T = dyn_cast<DIType>(this))
 214     return T->getScope();
 215
 216   if (auto *SP = dyn_cast<DISubprogram>(this))
 217     return SP->getScope();
 218
 219   if (auto *LB = dyn_cast<DILexicalBlockBase>(this))
 220     return LB->getScope();
 221
 222   if (auto *NS = dyn_cast<DINamespace>(this))
 223     return NS->getScope();
 224
 225   if (auto *CB = dyn_cast<DICommonBlock>(this))
 226     return CB->getScope();
 227
 228   if (auto *M = dyn_cast<DIModule>(this))
 229     return M->getScope();
 230
 231   assert((isa<DIFile>(this) || isa<DICompileUnit>(this)) &&
 232          "Unhandled type of scope.");
 233   return nullptr;
 234 }
 235
 236 StringRef DIScope::getName() const {
 237   if (auto *T = dyn_cast<DIType>(this))
 238     return T->getName();
 239   if (auto *SP = dyn_cast<DISubprogram>(this))
 240     return SP->getName();
 241   if (auto *NS = dyn_cast<DINamespace>(this))
 242     return NS->getName();
 243   if (auto *CB = dyn_cast<DICommonBlock>(this))
 244     return CB->getName();
 245   if (auto *M = dyn_cast<DIModule>(this))
 246     return M->getName();
 247   assert((isa<DILexicalBlockBase>(this) || isa<DIFile>(this) ||
 248           isa<DICompileUnit>(this)) &&
 249          "Unhandled type of scope.");
 250   return "";
 251 }
 252
 253 #ifndef NDEBUG
 254 static bool isCanonical(const MDString *S) {
 255   return !S || !S->getString().empty();
 256 }
 257 #endif
 258
 259 GenericDINode *GenericDINode::getImpl(LLVMContext &Context, unsigned Tag,
 260                                       MDString *Header,
 261                                       ArrayRef<Metadata *> DwarfOps,
 262                                       StorageType Storage, bool ShouldCreate) {
 263   unsigned Hash = 0;
 264   if (Storage == Uniqued) {
 265     GenericDINodeInfo::KeyTy Key(Tag, Header, DwarfOps);
 266     if (auto *N = getUniqued(Context.pImpl->GenericDINodes, Key))
 267       return N;
 268     if (!ShouldCreate)
 269       return nullptr;
 270     Hash = Key.getHash();
 271   } else {
 272     assert(ShouldCreate && "Expected non-uniqued nodes to always be created");
 273   }
 274
 275   // Use a nullptr for empty headers.
 276   assert(isCanonical(Header) && "Expected canonical MDString");
 277   Metadata *PreOps[] = {Header};
 278   return storeImpl(new (DwarfOps.size() + 1) GenericDINode(
 279                        Context, Storage, Hash, Tag, PreOps, DwarfOps),
 280                    Storage, Context.pImpl->GenericDINodes);
 281 }
 282
 283 void GenericDINode::recalculateHash() {
 284   setHash(GenericDINodeInfo::KeyTy::calculateHash(this));
 285 }
 286
 287 #define UNWRAP_ARGS_IMPL(...) __VA_ARGS__
 288 #define UNWRAP_ARGS(ARGS) UNWRAP_ARGS_IMPL ARGS
 289 #define DEFINE_GETIMPL_LOOKUP(CLASS, ARGS)                                     \
 290   do {                                                                         \
 291     if (Storage == Uniqued) {                                                  \
 292       if (auto *N = getUniqued(Context.pImpl->CLASS##s,                        \
 293                                CLASS##Info::KeyTy(UNWRAP_ARGS(ARGS))))         \
 294         return N;                                                              \
 295       if (!ShouldCreate)                                                       \
 296         return nullptr;                                                        \
 297     } else {                                                                   \
 298       assert(ShouldCreate &&                                                   \
 299              "Expected non-uniqued nodes to always be created");               \
 300     }                                                                          \
 301   } while (false)
 302 #define DEFINE_GETIMPL_STORE(CLASS, ARGS, OPS)                                 \
 303   return storeImpl(new (array_lengthof(OPS))                                   \
 304                        CLASS(Context, Storage, UNWRAP_ARGS(ARGS), OPS),        \
 305                    Storage, Context.pImpl->CLASS##s)
 306 #define DEFINE_GETIMPL_STORE_NO_OPS(CLASS, ARGS)                               \
 307   return storeImpl(new (0u) CLASS(Context, Storage, UNWRAP_ARGS(ARGS)),        \
 308                    Storage, Context.pImpl->CLASS##s)
 309 #define DEFINE_GETIMPL_STORE_NO_CONSTRUCTOR_ARGS(CLASS, OPS)                   \
 310   return storeImpl(new (array_lengthof(OPS)) CLASS(Context, Storage, OPS),     \
 311                    Storage, Context.pImpl->CLASS##s)
 312 #define DEFINE_GETIMPL_STORE_N(CLASS, ARGS, OPS, NUM_OPS)                      \
 313   return storeImpl(new (NUM_OPS)                                               \
 314                        CLASS(Context, Storage, UNWRAP_ARGS(ARGS), OPS),        \
 315                    Storage, Context.pImpl->CLASS##s)
 316
 317 DISubrange *DISubrange::getImpl(LLVMContext &Context, int64_t Count, int64_t Lo,
 318                                 StorageType Storage, bool ShouldCreate) {
 319   auto *CountNode = ConstantAsMetadata::get(
 320       ConstantInt::getSigned(Type::getInt64Ty(Context), Count));
 321   return getImpl(Context, CountNode, Lo, Storage, ShouldCreate);
 322 }
 323
 324 DISubrange *DISubrange::getImpl(LLVMContext &Context, Metadata *CountNode,
 325                                 int64_t Lo, StorageType Storage,
 326                                 bool ShouldCreate) {
 327   DEFINE_GETIMPL_LOOKUP(DISubrange, (CountNode, Lo));
 328   Metadata *Ops[] = { CountNode };
 329   DEFINE_GETIMPL_STORE(DISubrange, (CountNode, Lo), Ops);
 330 }
 331
 332 DIEnumerator *DIEnumerator::getImpl(LLVMContext &Context, int64_t Value,
 333                                     bool IsUnsigned, MDString *Name,
 334                                     StorageType Storage, bool ShouldCreate) {
 335   assert(isCanonical(Name) && "Expected canonical MDString");
 336   DEFINE_GETIMPL_LOOKUP(DIEnumerator, (Value, IsUnsigned, Name));
 337   Metadata *Ops[] = {Name};
 338   DEFINE_GETIMPL_STORE(DIEnumerator, (Value, IsUnsigned), Ops);
 339 }
 340
 341 DIBasicType *DIBasicType::getImpl(LLVMContext &Context, unsigned Tag,
 342                                   MDString *Name, uint64_t SizeInBits,
 343                                   uint32_t AlignInBits, unsigned Encoding,
 344                                   DIFlags Flags, StorageType Storage,
 345                                   bool ShouldCreate) {
 346   assert(isCanonical(Name) && "Expected canonical MDString");
 347   DEFINE_GETIMPL_LOOKUP(DIBasicType,
 348                         (Tag, Name, SizeInBits, AlignInBits, Encoding, Flags));
 349   Metadata *Ops[] = {nullptr, nullptr, Name};
 350   DEFINE_GETIMPL_STORE(DIBasicType, (Tag, SizeInBits, AlignInBits, Encoding,
 351                       Flags), Ops);
 352 }
 353
 354 Optional<DIBasicType::Signedness> DIBasicType::getSignedness() const {
 355   switch (getEncoding()) {
 356   case dwarf::DW_ATE_signed:
 357   case dwarf::DW_ATE_signed_char:
 358     return Signedness::Signed;
 359   case dwarf::DW_ATE_unsigned:
 360   case dwarf::DW_ATE_unsigned_char:
 361     return Signedness::Unsigned;
 362   default:
 363     return None;
 364   }
 365 }
 366
 367 DIDerivedType *DIDerivedType::getImpl(
 368     LLVMContext &Context, unsigned Tag, MDString *Name, Metadata *File,
 369     unsigned Line, Metadata *Scope, Metadata *BaseType, uint64_t SizeInBits,
 370     uint32_t AlignInBits, uint64_t OffsetInBits,
 371     Optional<unsigned> DWARFAddressSpace, DIFlags Flags, Metadata *ExtraData,
 372     StorageType Storage, bool ShouldCreate) {
 373   assert(isCanonical(Name) && "Expected canonical MDString");
 374   DEFINE_GETIMPL_LOOKUP(DIDerivedType,
 375                         (Tag, Name, File, Line, Scope, BaseType, SizeInBits,
 376                          AlignInBits, OffsetInBits, DWARFAddressSpace, Flags,
 377                          ExtraData));
 378   Metadata *Ops[] = {File, Scope, Name, BaseType, ExtraData};
 379   DEFINE_GETIMPL_STORE(
 380       DIDerivedType, (Tag, Line, SizeInBits, AlignInBits, OffsetInBits,
 381                       DWARFAddressSpace, Flags), Ops);
 382 }
 383
 384 DICompositeType *DICompositeType::getImpl(
 385     LLVMContext &Context, unsigned Tag, MDString *Name, Metadata *File,
 386     unsigned Line, Metadata *Scope, Metadata *BaseType, uint64_t SizeInBits,
 387     uint32_t AlignInBits, uint64_t OffsetInBits, DIFlags Flags,
 388     Metadata *Elements, unsigned RuntimeLang, Metadata *VTableHolder,
 389     Metadata *TemplateParams, MDString *Identifier, Metadata *Discriminator,
 390     StorageType Storage, bool ShouldCreate) {
 391   assert(isCanonical(Name) && "Expected canonical MDString");
 392
 393   // Keep this in sync with buildODRType.
 394   DEFINE_GETIMPL_LOOKUP(
 395       DICompositeType, (Tag, Name, File, Line, Scope, BaseType, SizeInBits,
 396                         AlignInBits, OffsetInBits, Flags, Elements, RuntimeLang,
 397                         VTableHolder, TemplateParams, Identifier, Discriminator));
 398   Metadata *Ops[] = {File,     Scope,        Name,           BaseType,
 399                      Elements, VTableHolder, TemplateParams, Identifier,
 400                      Discriminator};
 401   DEFINE_GETIMPL_STORE(DICompositeType, (Tag, Line, RuntimeLang, SizeInBits,
 402                                          AlignInBits, OffsetInBits, Flags),
 403                        Ops);
 404 }
 405
 406 DICompositeType *DICompositeType::buildODRType(
 407     LLVMContext &Context, MDString &Identifier, unsigned Tag, MDString *Name,
 408     Metadata *File, unsigned Line, Metadata *Scope, Metadata *BaseType,
 409     uint64_t SizeInBits, uint32_t AlignInBits, uint64_t OffsetInBits,
 410     DIFlags Flags, Metadata *Elements, unsigned RuntimeLang,
 411     Metadata *VTableHolder, Metadata *TemplateParams, Metadata *Discriminator) {
 412   assert(!Identifier.getString().empty() && "Expected valid identifier");
 413   if (!Context.isODRUniquingDebugTypes())
 414     return nullptr;
 415   auto *&CT = (*Context.pImpl->DITypeMap)[&Identifier];
 416   if (!CT)
 417     return CT = DICompositeType::getDistinct(
 418                Context, Tag, Name, File, Line, Scope, BaseType, SizeInBits,
 419                AlignInBits, OffsetInBits, Flags, Elements, RuntimeLang,
 420                VTableHolder, TemplateParams, &Identifier, Discriminator);
 421
 422   // Only mutate CT if it's a forward declaration and the new operands aren't.
 423   assert(CT->getRawIdentifier() == &Identifier && "Wrong ODR identifier?");
 424   if (!CT->isForwardDecl() || (Flags & DINode::FlagFwdDecl))
 425     return CT;
 426
 427   // Mutate CT in place.  Keep this in sync with getImpl.
 428   CT->mutate(Tag, Line, RuntimeLang, SizeInBits, AlignInBits, OffsetInBits,
 429              Flags);
 430   Metadata *Ops[] = {File,     Scope,        Name,           BaseType,
 431                      Elements, VTableHolder, TemplateParams, &Identifier,
 432                      Discriminator};
 433   assert((std::end(Ops) - std::begin(Ops)) == (int)CT->getNumOperands() &&
 434          "Mismatched number of operands");
 435   for (unsigned I = 0, E = CT->getNumOperands(); I != E; ++I)
 436     if (Ops[I] != CT->getOperand(I))
 437       CT->setOperand(I, Ops[I]);
 438   return CT;
 439 }
 440
 441 DICompositeType *DICompositeType::getODRType(
 442     LLVMContext &Context, MDString &Identifier, unsigned Tag, MDString *Name,
 443     Metadata *File, unsigned Line, Metadata *Scope, Metadata *BaseType,
 444     uint64_t SizeInBits, uint32_t AlignInBits, uint64_t OffsetInBits,
 445     DIFlags Flags, Metadata *Elements, unsigned RuntimeLang,
 446     Metadata *VTableHolder, Metadata *TemplateParams, Metadata *Discriminator) {
 447   assert(!Identifier.getString().empty() && "Expected valid identifier");
 448   if (!Context.isODRUniquingDebugTypes())
 449     return nullptr;
 450   auto *&CT = (*Context.pImpl->DITypeMap)[&Identifier];
 451   if (!CT)
 452     CT = DICompositeType::getDistinct(
 453         Context, Tag, Name, File, Line, Scope, BaseType, SizeInBits,
 454         AlignInBits, OffsetInBits, Flags, Elements, RuntimeLang, VTableHolder,
 455         TemplateParams, &Identifier, Discriminator);
 456   return CT;
 457 }
 458
 459 DICompositeType *DICompositeType::getODRTypeIfExists(LLVMContext &Context,
 460                                                      MDString &Identifier) {
 461   assert(!Identifier.getString().empty() && "Expected valid identifier");
 462   if (!Context.isODRUniquingDebugTypes())
 463     return nullptr;
 464   return Context.pImpl->DITypeMap->lookup(&Identifier);
 465 }
 466
 467 DISubroutineType *DISubroutineType::getImpl(LLVMContext &Context, DIFlags Flags,
 468                                             uint8_t CC, Metadata *TypeArray,
 469                                             StorageType Storage,
 470                                             bool ShouldCreate) {
 471   DEFINE_GETIMPL_LOOKUP(DISubroutineType, (Flags, CC, TypeArray));
 472   Metadata *Ops[] = {nullptr, nullptr, nullptr, TypeArray};
 473   DEFINE_GETIMPL_STORE(DISubroutineType, (Flags, CC), Ops);
 474 }
 475
 476 // FIXME: Implement this string-enum correspondence with a .def file and macros,
 477 // so that the association is explicit rather than implied.
 478 static const char *ChecksumKindName[DIFile::CSK_Last] = {
 479   "CSK_MD5",
 480   "CSK_SHA1"
 481 };
 482
 483 StringRef DIFile::getChecksumKindAsString(ChecksumKind CSKind) {
 484   assert(CSKind <= DIFile::CSK_Last && "Invalid checksum kind");
 485   // The first space was originally the CSK_None variant, which is now
 486   // obsolete, but the space is still reserved in ChecksumKind, so we account
 487   // for it here.
 488   return ChecksumKindName[CSKind - 1];
 489 }
 490
 491 Optional<DIFile::ChecksumKind> DIFile::getChecksumKind(StringRef CSKindStr) {
 492   return StringSwitch<Optional<DIFile::ChecksumKind>>(CSKindStr)
 493       .Case("CSK_MD5", DIFile::CSK_MD5)
 494       .Case("CSK_SHA1", DIFile::CSK_SHA1)
 495       .Default(None);
 496 }
 497
 498 DIFile *DIFile::getImpl(LLVMContext &Context, MDString *Filename,
 499                         MDString *Directory,
 500                         Optional<DIFile::ChecksumInfo<MDString *>> CS,
 501                         Optional<MDString *> Source, StorageType Storage,
 502                         bool ShouldCreate) {
 503   assert(isCanonical(Filename) && "Expected canonical MDString");
 504   assert(isCanonical(Directory) && "Expected canonical MDString");
 505   assert((!CS || isCanonical(CS->Value)) && "Expected canonical MDString");
 506   assert((!Source || isCanonical(*Source)) && "Expected canonical MDString");
 507   DEFINE_GETIMPL_LOOKUP(DIFile, (Filename, Directory, CS, Source));
 508   Metadata *Ops[] = {Filename, Directory, CS ? CS->Value : nullptr,
 509                      Source.getValueOr(nullptr)};
 510   DEFINE_GETIMPL_STORE(DIFile, (CS, Source), Ops);
 511 }
 512
 513 DICompileUnit *DICompileUnit::getImpl(
 514     LLVMContext &Context, unsigned SourceLanguage, Metadata *File,
 515     MDString *Producer, bool IsOptimized, MDString *Flags,
 516     unsigned RuntimeVersion, MDString *SplitDebugFilename,
 517     unsigned EmissionKind, Metadata *EnumTypes, Metadata *RetainedTypes,
 518     Metadata *GlobalVariables, Metadata *ImportedEntities, Metadata *Macros,
 519     uint64_t DWOId, bool SplitDebugInlining, bool DebugInfoForProfiling,
 520     unsigned NameTableKind, bool RangesBaseAddress, StorageType Storage,
 521     bool ShouldCreate) {
 522   assert(Storage != Uniqued && "Cannot unique DICompileUnit");
 523   assert(isCanonical(Producer) && "Expected canonical MDString");
 524   assert(isCanonical(Flags) && "Expected canonical MDString");
 525   assert(isCanonical(SplitDebugFilename) && "Expected canonical MDString");
 526
 527   Metadata *Ops[] = {
 528       File,      Producer,      Flags,           SplitDebugFilename,
 529       EnumTypes, RetainedTypes, GlobalVariables, ImportedEntities,
 530       Macros};
 531   return storeImpl(new (array_lengthof(Ops)) DICompileUnit(
 532                        Context, Storage, SourceLanguage, IsOptimized,
 533                        RuntimeVersion, EmissionKind, DWOId, SplitDebugInlining,
 534                        DebugInfoForProfiling, NameTableKind, RangesBaseAddress,
 535                        Ops),
 536                    Storage);
 537 }
 538
 539 Optional<DICompileUnit::DebugEmissionKind>
 540 DICompileUnit::getEmissionKind(StringRef Str) {
 541   return StringSwitch<Optional<DebugEmissionKind>>(Str)
 542       .Case("NoDebug", NoDebug)
 543       .Case("FullDebug", FullDebug)
 544       .Case("LineTablesOnly", LineTablesOnly)
 545       .Case("DebugDirectivesOnly", DebugDirectivesOnly)
 546       .Default(None);
 547 }
 548
 549 Optional<DICompileUnit::DebugNameTableKind>
 550 DICompileUnit::getNameTableKind(StringRef Str) {
 551   return StringSwitch<Optional<DebugNameTableKind>>(Str)
 552       .Case("Default", DebugNameTableKind::Default)
 553       .Case("GNU", DebugNameTableKind::GNU)
 554       .Case("None", DebugNameTableKind::None)
 555       .Default(None);
 556 }
 557
 558 const char *DICompileUnit::emissionKindString(DebugEmissionKind EK) {
 559   switch (EK) {
 560   case NoDebug:        return "NoDebug";
 561   case FullDebug:      return "FullDebug";
 562   case LineTablesOnly: return "LineTablesOnly";
 563   case DebugDirectivesOnly: return "DebugDirectivesOnly";
 564   }
 565   return nullptr;
 566 }
 567
 568 const char *DICompileUnit::nameTableKindString(DebugNameTableKind NTK) {
 569   switch (NTK) {
 570   case DebugNameTableKind::Default:
 571     return nullptr;
 572   case DebugNameTableKind::GNU:
 573     return "GNU";
 574   case DebugNameTableKind::None:
 575     return "None";
 576   }
 577   return nullptr;
 578 }
 579
 580 DISubprogram *DILocalScope::getSubprogram() const {
 581   if (auto *Block = dyn_cast<DILexicalBlockBase>(this))
 582     return Block->getScope()->getSubprogram();
 583   return const_cast<DISubprogram *>(cast<DISubprogram>(this));
 584 }
 585
 586 DILocalScope *DILocalScope::getNonLexicalBlockFileScope() const {
 587   if (auto *File = dyn_cast<DILexicalBlockFile>(this))
 588     return File->getScope()->getNonLexicalBlockFileScope();
 589   return const_cast<DILocalScope *>(this);
 590 }
 591
 592 DISubprogram::DISPFlags DISubprogram::getFlag(StringRef Flag) {
 593   return StringSwitch<DISPFlags>(Flag)
 594 #define HANDLE_DISP_FLAG(ID, NAME) .Case("DISPFlag" #NAME, SPFlag##NAME)
 595 #include "llvm/IR/DebugInfoFlags.def"
 596       .Default(SPFlagZero);
 597 }
 598
 599 StringRef DISubprogram::getFlagString(DISPFlags Flag) {
 600   switch (Flag) {
 601   // Appease a warning.
 602   case SPFlagVirtuality:
 603     return "";
 604 #define HANDLE_DISP_FLAG(ID, NAME)                                             \
 605   case SPFlag##NAME:                                                           \
 606     return "DISPFlag" #NAME;
 607 #include "llvm/IR/DebugInfoFlags.def"
 608   }
 609   return "";
 610 }
 611
 612 DISubprogram::DISPFlags
 613 DISubprogram::splitFlags(DISPFlags Flags,
 614                          SmallVectorImpl<DISPFlags> &SplitFlags) {
 615   // Multi-bit fields can require special handling. In our case, however, the
 616   // only multi-bit field is virtuality, and all its values happen to be
 617   // single-bit values, so the right behavior just falls out.
 618 #define HANDLE_DISP_FLAG(ID, NAME)                                             \
 619   if (DISPFlags Bit = Flags & SPFlag##NAME) {                                  \
 620     SplitFlags.push_back(Bit);                                                 \
 621     Flags &= ~Bit;                                                             \
 622   }
 623 #include "llvm/IR/DebugInfoFlags.def"
 624   return Flags;
 625 }
 626
 627 DISubprogram *DISubprogram::getImpl(
 628     LLVMContext &Context, Metadata *Scope, MDString *Name,
 629     MDString *LinkageName, Metadata *File, unsigned Line, Metadata *Type,
 630     unsigned ScopeLine, Metadata *ContainingType, unsigned VirtualIndex,
 631     int ThisAdjustment, DIFlags Flags, DISPFlags SPFlags, Metadata *Unit,
 632     Metadata *TemplateParams, Metadata *Declaration, Metadata *RetainedNodes,
 633     Metadata *ThrownTypes, StorageType Storage, bool ShouldCreate) {
 634   assert(isCanonical(Name) && "Expected canonical MDString");
 635   assert(isCanonical(LinkageName) && "Expected canonical MDString");
 636   DEFINE_GETIMPL_LOOKUP(DISubprogram,
 637                         (Scope, Name, LinkageName, File, Line, Type, ScopeLine,
 638                          ContainingType, VirtualIndex, ThisAdjustment, Flags,
 639                          SPFlags, Unit, TemplateParams, Declaration,
 640                          RetainedNodes, ThrownTypes));
 641   SmallVector<Metadata *, 11> Ops = {
 642       File,        Scope,         Name,           LinkageName,    Type,       Unit,
 643       Declaration, RetainedNodes, ContainingType, TemplateParams, ThrownTypes};
 644   if (!ThrownTypes) {
 645     Ops.pop_back();
 646     if (!TemplateParams) {
 647       Ops.pop_back();
 648       if (!ContainingType)
 649         Ops.pop_back();
 650     }
 651   }
 652   DEFINE_GETIMPL_STORE_N(
 653       DISubprogram,
 654       (Line, ScopeLine, VirtualIndex, ThisAdjustment, Flags, SPFlags), Ops,
 655       Ops.size());
 656 }
 657
 658 bool DISubprogram::describes(const Function *F) const {
 659   assert(F && "Invalid function");
 660   if (F->getSubprogram() == this)
 661     return true;
 662   StringRef Name = getLinkageName();
 663   if (Name.empty())
 664     Name = getName();
 665   return F->getName() == Name;
 666 }
 667
 668 DILexicalBlock *DILexicalBlock::getImpl(LLVMContext &Context, Metadata *Scope,
 669                                         Metadata *File, unsigned Line,
 670                                         unsigned Column, StorageType Storage,
 671                                         bool ShouldCreate) {
 672   // Fixup column.
 673   adjustColumn(Column);
 674
 675   assert(Scope && "Expected scope");
 676   DEFINE_GETIMPL_LOOKUP(DILexicalBlock, (Scope, File, Line, Column));
 677   Metadata *Ops[] = {File, Scope};
 678   DEFINE_GETIMPL_STORE(DILexicalBlock, (Line, Column), Ops);
 679 }
 680
 681 DILexicalBlockFile *DILexicalBlockFile::getImpl(LLVMContext &Context,
 682                                                 Metadata *Scope, Metadata *File,
 683                                                 unsigned Discriminator,
 684                                                 StorageType Storage,
 685                                                 bool ShouldCreate) {
 686   assert(Scope && "Expected scope");
 687   DEFINE_GETIMPL_LOOKUP(DILexicalBlockFile, (Scope, File, Discriminator));
 688   Metadata *Ops[] = {File, Scope};
 689   DEFINE_GETIMPL_STORE(DILexicalBlockFile, (Discriminator), Ops);
 690 }
 691
 692 DINamespace *DINamespace::getImpl(LLVMContext &Context, Metadata *Scope,
 693                                   MDString *Name, bool ExportSymbols,
 694                                   StorageType Storage, bool ShouldCreate) {
 695   assert(isCanonical(Name) && "Expected canonical MDString");
 696   DEFINE_GETIMPL_LOOKUP(DINamespace, (Scope, Name, ExportSymbols));
 697   // The nullptr is for DIScope's File operand. This should be refactored.
 698   Metadata *Ops[] = {nullptr, Scope, Name};
 699   DEFINE_GETIMPL_STORE(DINamespace, (ExportSymbols), Ops);
 700 }
 701
 702 DICommonBlock *DICommonBlock::getImpl(LLVMContext &Context, Metadata *Scope,
 703                                       Metadata *Decl, MDString *Name,
 704                                       Metadata *File, unsigned LineNo,
 705                                       StorageType Storage, bool ShouldCreate) {
 706   assert(isCanonical(Name) && "Expected canonical MDString");
 707   DEFINE_GETIMPL_LOOKUP(DICommonBlock, (Scope, Decl, Name, File, LineNo));
 708   // The nullptr is for DIScope's File operand. This should be refactored.
 709   Metadata *Ops[] = {Scope, Decl, Name, File};
 710   DEFINE_GETIMPL_STORE(DICommonBlock, (LineNo), Ops);
 711 }
 712
 713 DIModule *DIModule::getImpl(LLVMContext &Context, Metadata *Scope,
 714                             MDString *Name, MDString *ConfigurationMacros,
 715                             MDString *IncludePath, MDString *ISysRoot,
 716                             StorageType Storage, bool ShouldCreate) {
 717   assert(isCanonical(Name) && "Expected canonical MDString");
 718   DEFINE_GETIMPL_LOOKUP(
 719       DIModule, (Scope, Name, ConfigurationMacros, IncludePath, ISysRoot));
 720   Metadata *Ops[] = {Scope, Name, ConfigurationMacros, IncludePath, ISysRoot};
 721   DEFINE_GETIMPL_STORE_NO_CONSTRUCTOR_ARGS(DIModule, Ops);
 722 }
 723
 724 DITemplateTypeParameter *DITemplateTypeParameter::getImpl(LLVMContext &Context,
 725                                                           MDString *Name,
 726                                                           Metadata *Type,
 727                                                           StorageType Storage,
 728                                                           bool ShouldCreate) {
 729   assert(isCanonical(Name) && "Expected canonical MDString");
 730   DEFINE_GETIMPL_LOOKUP(DITemplateTypeParameter, (Name, Type));
 731   Metadata *Ops[] = {Name, Type};
 732   DEFINE_GETIMPL_STORE_NO_CONSTRUCTOR_ARGS(DITemplateTypeParameter, Ops);
 733 }
 734
 735 DITemplateValueParameter *DITemplateValueParameter::getImpl(
 736     LLVMContext &Context, unsigned Tag, MDString *Name, Metadata *Type,
 737     Metadata *Value, StorageType Storage, bool ShouldCreate) {
 738   assert(isCanonical(Name) && "Expected canonical MDString");
 739   DEFINE_GETIMPL_LOOKUP(DITemplateValueParameter, (Tag, Name, Type, Value));
 740   Metadata *Ops[] = {Name, Type, Value};
 741   DEFINE_GETIMPL_STORE(DITemplateValueParameter, (Tag), Ops);
 742 }
 743
 744 DIGlobalVariable *
 745 DIGlobalVariable::getImpl(LLVMContext &Context, Metadata *Scope, MDString *Name,
 746                           MDString *LinkageName, Metadata *File, unsigned Line,
 747                           Metadata *Type, bool IsLocalToUnit, bool IsDefinition,
 748                           Metadata *StaticDataMemberDeclaration,
 749                           Metadata *TemplateParams, uint32_t AlignInBits,
 750                           StorageType Storage, bool ShouldCreate) {
 751   assert(isCanonical(Name) && "Expected canonical MDString");
 752   assert(isCanonical(LinkageName) && "Expected canonical MDString");
 753   DEFINE_GETIMPL_LOOKUP(DIGlobalVariable, (Scope, Name, LinkageName, File, Line,
 754                                            Type, IsLocalToUnit, IsDefinition,
 755                                            StaticDataMemberDeclaration,
 756                                            TemplateParams, AlignInBits));
 757   Metadata *Ops[] = {Scope,
 758                      Name,
 759                      File,
 760                      Type,
 761                      Name,
 762                      LinkageName,
 763                      StaticDataMemberDeclaration,
 764                      TemplateParams};
 765   DEFINE_GETIMPL_STORE(DIGlobalVariable,
 766                        (Line, IsLocalToUnit, IsDefinition, AlignInBits), Ops);
 767 }
 768
 769 DILocalVariable *DILocalVariable::getImpl(LLVMContext &Context, Metadata *Scope,
 770                                           MDString *Name, Metadata *File,
 771                                           unsigned Line, Metadata *Type,
 772                                           unsigned Arg, DIFlags Flags,
 773                                           uint32_t AlignInBits,
 774                                           StorageType Storage,
 775                                           bool ShouldCreate) {
 776   // 64K ought to be enough for any frontend.
 777   assert(Arg <= UINT16_MAX && "Expected argument number to fit in 16-bits");
 778
 779   assert(Scope && "Expected scope");
 780   assert(isCanonical(Name) && "Expected canonical MDString");
 781   DEFINE_GETIMPL_LOOKUP(DILocalVariable,
 782                         (Scope, Name, File, Line, Type, Arg, Flags,
 783                          AlignInBits));
 784   Metadata *Ops[] = {Scope, Name, File, Type};
 785   DEFINE_GETIMPL_STORE(DILocalVariable, (Line, Arg, Flags, AlignInBits), Ops);
 786 }
 787
 788 Optional<uint64_t> DIVariable::getSizeInBits() const {
 789   // This is used by the Verifier so be mindful of broken types.
 790   const Metadata *RawType = getRawType();
 791   while (RawType) {
 792     // Try to get the size directly.
 793     if (auto *T = dyn_cast<DIType>(RawType))
 794       if (uint64_t Size = T->getSizeInBits())
 795         return Size;
 796
 797     if (auto *DT = dyn_cast<DIDerivedType>(RawType)) {
 798       // Look at the base type.
 799       RawType = DT->getRawBaseType();
 800       continue;
 801     }
 802
 803     // Missing type or size.
 804     break;
 805   }
 806
 807   // Fail gracefully.
 808   return None;
 809 }
 810
 811 DILabel *DILabel::getImpl(LLVMContext &Context, Metadata *Scope,
 812                           MDString *Name, Metadata *File, unsigned Line,
 813                           StorageType Storage,
 814                           bool ShouldCreate) {
 815   assert(Scope && "Expected scope");
 816   assert(isCanonical(Name) && "Expected canonical MDString");
 817   DEFINE_GETIMPL_LOOKUP(DILabel,
 818                         (Scope, Name, File, Line));
 819   Metadata *Ops[] = {Scope, Name, File};
 820   DEFINE_GETIMPL_STORE(DILabel, (Line), Ops);
 821 }
 822
 823 DIExpression *DIExpression::getImpl(LLVMContext &Context,
 824                                     ArrayRef<uint64_t> Elements,
 825                                     StorageType Storage, bool ShouldCreate) {
 826   DEFINE_GETIMPL_LOOKUP(DIExpression, (Elements));
 827   DEFINE_GETIMPL_STORE_NO_OPS(DIExpression, (Elements));
 828 }
 829
 830 unsigned DIExpression::ExprOperand::getSize() const {
 831   uint64_t Op = getOp();
 832
 833   if (Op >= dwarf::DW_OP_breg0 && Op <= dwarf::DW_OP_breg31)
 834     return 2;
 835
 836   switch (Op) {
 837   case dwarf::DW_OP_LLVM_convert:
 838   case dwarf::DW_OP_LLVM_fragment:
 839   case dwarf::DW_OP_bregx:
 840     return 3;
 841   case dwarf::DW_OP_constu:
 842   case dwarf::DW_OP_consts:
 843   case dwarf::DW_OP_deref_size:
 844   case dwarf::DW_OP_plus_uconst:
 845   case dwarf::DW_OP_LLVM_tag_offset:
 846   case dwarf::DW_OP_entry_value:
 847   case dwarf::DW_OP_regx:
 848     return 2;
 849   default:
 850     return 1;
 851   }
 852 }
 853
 854 bool DIExpression::isValid() const {
 855   for (auto I = expr_op_begin(), E = expr_op_end(); I != E; ++I) {
 856     // Check that there's space for the operand.
 857     if (I->get() + I->getSize() > E->get())
 858       return false;
 859
 860     uint64_t Op = I->getOp();
 861     if ((Op >= dwarf::DW_OP_reg0 && Op <= dwarf::DW_OP_reg31) ||
 862         (Op >= dwarf::DW_OP_breg0 && Op <= dwarf::DW_OP_breg31))
 863       return true;
 864
 865     // Check that the operand is valid.
 866     switch (Op) {
 867     default:
 868       return false;
 869     case dwarf::DW_OP_LLVM_fragment:
 870       // A fragment operator must appear at the end.
 871       return I->get() + I->getSize() == E->get();
 872     case dwarf::DW_OP_stack_value: {
 873       // Must be the last one or followed by a DW_OP_LLVM_fragment.
 874       if (I->get() + I->getSize() == E->get())
 875         break;
 876       auto J = I;
 877       if ((++J)->getOp() != dwarf::DW_OP_LLVM_fragment)
 878         return false;
 879       break;
 880     }
 881     case dwarf::DW_OP_swap: {
 882       // Must be more than one implicit element on the stack.
 883
 884       // FIXME: A better way to implement this would be to add a local variable
 885       // that keeps track of the stack depth and introduce something like a
 886       // DW_LLVM_OP_implicit_location as a placeholder for the location this
 887       // DIExpression is attached to, or else pass the number of implicit stack
 888       // elements into isValid.
 889       if (getNumElements() == 1)
 890         return false;
 891       break;
 892     }
 893     case dwarf::DW_OP_entry_value: {
 894       // An entry value operator must appear at the begin and the size
 895       // of following expression should be 1, because we support only
 896       // entry values of a simple register location.
 897       return I->get() == expr_op_begin()->get() && I->getArg(0) == 1 &&
 898              getNumElements() == 2;
 899     }
 900     case dwarf::DW_OP_LLVM_convert:
 901     case dwarf::DW_OP_LLVM_tag_offset:
 902     case dwarf::DW_OP_constu:
 903     case dwarf::DW_OP_plus_uconst:
 904     case dwarf::DW_OP_plus:
 905     case dwarf::DW_OP_minus:
 906     case dwarf::DW_OP_mul:
 907     case dwarf::DW_OP_div:
 908     case dwarf::DW_OP_mod:
 909     case dwarf::DW_OP_or:
 910     case dwarf::DW_OP_and:
 911     case dwarf::DW_OP_xor:
 912     case dwarf::DW_OP_shl:
 913     case dwarf::DW_OP_shr:
 914     case dwarf::DW_OP_shra:
 915     case dwarf::DW_OP_deref:
 916     case dwarf::DW_OP_deref_size:
 917     case dwarf::DW_OP_xderef:
 918     case dwarf::DW_OP_lit0:
 919     case dwarf::DW_OP_not:
 920     case dwarf::DW_OP_dup:
 921     case dwarf::DW_OP_regx:
 922     case dwarf::DW_OP_bregx:
 923       break;
 924     }
 925   }
 926   return true;
 927 }
 928
 929 bool DIExpression::isImplicit() const {
 930   unsigned N = getNumElements();
 931   if (isValid() && N > 0) {
 932     switch (getElement(N-1)) {
 933       case dwarf::DW_OP_stack_value:
 934       case dwarf::DW_OP_LLVM_tag_offset:
 935         return true;
 936       case dwarf::DW_OP_LLVM_fragment:
 937         return N > 1 && getElement(N-2) == dwarf::DW_OP_stack_value;
 938       default: break;
 939     }
 940   }
 941   return false;
 942 }
 943
 944 bool DIExpression::isComplex() const {
 945   if (!isValid())
 946     return false;
 947
 948   if (getNumElements() == 0)
 949     return false;
 950
 951   // If there are any elements other than fragment or tag_offset, then some
 952   // kind of complex computation occurs.
 953   for (const auto &It : expr_ops()) {
 954     switch (It.getOp()) {
 955       case dwarf::DW_OP_LLVM_tag_offset:
 956       case dwarf::DW_OP_LLVM_fragment:
 957         continue;
 958       default: return true;
 959     }
 960   }
 961
 962   return false;
 963 }
 964
 965 Optional<DIExpression::FragmentInfo>
 966 DIExpression::getFragmentInfo(expr_op_iterator Start, expr_op_iterator End) {
 967   for (auto I = Start; I != End; ++I)
 968     if (I->getOp() == dwarf::DW_OP_LLVM_fragment) {
 969       DIExpression::FragmentInfo Info = {I->getArg(1), I->getArg(0)};
 970       return Info;
 971     }
 972   return None;
 973 }
 974
 975 void DIExpression::appendOffset(SmallVectorImpl<uint64_t> &Ops,
 976                                 int64_t Offset) {
 977   if (Offset > 0) {
 978     Ops.push_back(dwarf::DW_OP_plus_uconst);
 979     Ops.push_back(Offset);
 980   } else if (Offset < 0) {
 981     Ops.push_back(dwarf::DW_OP_constu);
 982     Ops.push_back(-Offset);
 983     Ops.push_back(dwarf::DW_OP_minus);
 984   }
 985 }
 986
 987 bool DIExpression::extractIfOffset(int64_t &Offset) const {
 988   if (getNumElements() == 0) {
 989     Offset = 0;
 990     return true;
 991   }
 992
 993   if (getNumElements() == 2 && Elements[0] == dwarf::DW_OP_plus_uconst) {
 994     Offset = Elements[1];
 995     return true;
 996   }
 997
 998   if (getNumElements() == 3 && Elements[0] == dwarf::DW_OP_constu) {
 999     if (Elements[2] == dwarf::DW_OP_plus) {
1000       Offset = Elements[1];
1001       return true;
1002     }
1003     if (Elements[2] == dwarf::DW_OP_minus) {
1004       Offset = -Elements[1];
1005       return true;
1006     }
1007   }
1008
1009   return false;
1010 }
1011
1012 const DIExpression *DIExpression::extractAddressClass(const DIExpression *Expr,
1013                                                       unsigned &AddrClass) {
1014   const unsigned PatternSize = 4;
1015   if (Expr->Elements.size() >= PatternSize &&
1016       Expr->Elements[PatternSize - 4] == dwarf::DW_OP_constu &&
1017       Expr->Elements[PatternSize - 2] == dwarf::DW_OP_swap &&
1018       Expr->Elements[PatternSize - 1] == dwarf::DW_OP_xderef) {
1019     AddrClass = Expr->Elements[PatternSize - 3];
1020
1021     if (Expr->Elements.size() == PatternSize)
1022       return nullptr;
1023     return DIExpression::get(Expr->getContext(),
1024                              makeArrayRef(&*Expr->Elements.begin(),
1025                                           Expr->Elements.size() - PatternSize));
1026   }
1027   return Expr;
1028 }
1029
1030 DIExpression *DIExpression::prepend(const DIExpression *Expr, uint8_t Flags,
1031                                     int64_t Offset) {
1032   SmallVector<uint64_t, 8> Ops;
1033   if (Flags & DIExpression::DerefBefore)
1034     Ops.push_back(dwarf::DW_OP_deref);
1035
1036   appendOffset(Ops, Offset);
1037   if (Flags & DIExpression::DerefAfter)
1038     Ops.push_back(dwarf::DW_OP_deref);
1039
1040   bool StackValue = Flags & DIExpression::StackValue;
1041   bool EntryValue = Flags & DIExpression::EntryValue;
1042
1043   return prependOpcodes(Expr, Ops, StackValue, EntryValue);
1044 }
1045
1046 DIExpression *DIExpression::prependOpcodes(const DIExpression *Expr,
1047                                            SmallVectorImpl<uint64_t> &Ops,
1048                                            bool StackValue,
1049                                            bool EntryValue) {
1050   assert(Expr && "Can't prepend ops to this expression");
1051
1052   if (EntryValue) {
1053     Ops.push_back(dwarf::DW_OP_entry_value);
1054     // Add size info needed for entry value expression.
1055     // Add plus one for target register operand.
1056     Ops.push_back(Expr->getNumElements() + 1);
1057   }
1058
1059   // If there are no ops to prepend, do not even add the DW_OP_stack_value.
1060   if (Ops.empty())
1061     StackValue = false;
1062   for (auto Op : Expr->expr_ops()) {
1063     // A DW_OP_stack_value comes at the end, but before a DW_OP_LLVM_fragment.
1064     if (StackValue) {
1065       if (Op.getOp() == dwarf::DW_OP_stack_value)
1066         StackValue = false;
1067       else if (Op.getOp() == dwarf::DW_OP_LLVM_fragment) {
1068         Ops.push_back(dwarf::DW_OP_stack_value);
1069         StackValue = false;
1070       }
1071     }
1072     Op.appendToVector(Ops);
1073   }
1074   if (StackValue)
1075     Ops.push_back(dwarf::DW_OP_stack_value);
1076   return DIExpression::get(Expr->getContext(), Ops);
1077 }
1078
1079 DIExpression *DIExpression::append(const DIExpression *Expr,
1080                                    ArrayRef<uint64_t> Ops) {
1081   assert(Expr && !Ops.empty() && "Can't append ops to this expression");
1082
1083   // Copy Expr's current op list.
1084   SmallVector<uint64_t, 16> NewOps;
1085   for (auto Op : Expr->expr_ops()) {
1086     // Append new opcodes before DW_OP_{stack_value, LLVM_fragment}.
1087     if (Op.getOp() == dwarf::DW_OP_stack_value ||
1088         Op.getOp() == dwarf::DW_OP_LLVM_fragment) {
1089       NewOps.append(Ops.begin(), Ops.end());
1090
1091       // Ensure that the new opcodes are only appended once.
1092       Ops = None;
1093     }
1094     Op.appendToVector(NewOps);
1095   }
1096
1097   NewOps.append(Ops.begin(), Ops.end());
1098   return DIExpression::get(Expr->getContext(), NewOps);
1099 }
1100
1101 DIExpression *DIExpression::appendToStack(const DIExpression *Expr,
1102                                           ArrayRef<uint64_t> Ops) {
1103   assert(Expr && !Ops.empty() && "Can't append ops to this expression");
1104   assert(none_of(Ops,
1105                  [](uint64_t Op) {
1106                    return Op == dwarf::DW_OP_stack_value ||
1107                           Op == dwarf::DW_OP_LLVM_fragment;
1108                  }) &&
1109          "Can't append this op");
1110
1111   // Append a DW_OP_deref after Expr's current op list if it's non-empty and
1112   // has no DW_OP_stack_value.
1113   //
1114   // Match .* DW_OP_stack_value (DW_OP_LLVM_fragment A B)?.
1115   Optional<FragmentInfo> FI = Expr->getFragmentInfo();
1116   unsigned DropUntilStackValue = FI.hasValue() ? 3 : 0;
1117   ArrayRef<uint64_t> ExprOpsBeforeFragment =
1118       Expr->getElements().drop_back(DropUntilStackValue);
1119   bool NeedsDeref = (Expr->getNumElements() > DropUntilStackValue) &&
1120                     (ExprOpsBeforeFragment.back() != dwarf::DW_OP_stack_value);
1121   bool NeedsStackValue = NeedsDeref || ExprOpsBeforeFragment.empty();
1122
1123   // Append a DW_OP_deref after Expr's current op list if needed, then append
1124   // the new ops, and finally ensure that a single DW_OP_stack_value is present.
1125   SmallVector<uint64_t, 16> NewOps;
1126   if (NeedsDeref)
1127     NewOps.push_back(dwarf::DW_OP_deref);
1128   NewOps.append(Ops.begin(), Ops.end());
1129   if (NeedsStackValue)
1130     NewOps.push_back(dwarf::DW_OP_stack_value);
1131   return DIExpression::append(Expr, NewOps);
1132 }
1133
1134 Optional<DIExpression *> DIExpression::createFragmentExpression(
1135     const DIExpression *Expr, unsigned OffsetInBits, unsigned SizeInBits) {
1136   SmallVector<uint64_t, 8> Ops;
1137   // Copy over the expression, but leave off any trailing DW_OP_LLVM_fragment.
1138   if (Expr) {
1139     for (auto Op : Expr->expr_ops()) {
1140       switch (Op.getOp()) {
1141       default: break;
1142       case dwarf::DW_OP_plus:
1143       case dwarf::DW_OP_minus:
1144         // We can't safely split arithmetic into multiple fragments because we
1145         // can't express carry-over between fragments.
1146         //
1147         // FIXME: We *could* preserve the lowest fragment of a constant offset
1148         // operation if the offset fits into SizeInBits.
1149         return None;
1150       case dwarf::DW_OP_LLVM_fragment: {
1151         // Make the new offset point into the existing fragment.
1152         uint64_t FragmentOffsetInBits = Op.getArg(0);
1153         uint64_t FragmentSizeInBits = Op.getArg(1);
1154         (void)FragmentSizeInBits;
1155         assert((OffsetInBits + SizeInBits <= FragmentSizeInBits) &&
1156                "new fragment outside of original fragment");
1157         OffsetInBits += FragmentOffsetInBits;
1158         continue;
1159       }
1160       }
1161       Op.appendToVector(Ops);
1162     }
1163   }
1164   Ops.push_back(dwarf::DW_OP_LLVM_fragment);
1165   Ops.push_back(OffsetInBits);
1166   Ops.push_back(SizeInBits);
1167   return DIExpression::get(Expr->getContext(), Ops);
1168 }
1169
1170 bool DIExpression::isConstant() const {
1171   // Recognize DW_OP_constu C DW_OP_stack_value (DW_OP_LLVM_fragment Len Ofs)?.
1172   if (getNumElements() != 3 && getNumElements() != 6)
1173     return false;
1174   if (getElement(0) != dwarf::DW_OP_constu ||
1175       getElement(2) != dwarf::DW_OP_stack_value)
1176     return false;
1177   if (getNumElements() == 6 && getElement(3) != dwarf::DW_OP_LLVM_fragment)
1178     return false;
1179   return true;
1180 }
1181
1182 DIGlobalVariableExpression *
1183 DIGlobalVariableExpression::getImpl(LLVMContext &Context, Metadata *Variable,
1184                                     Metadata *Expression, StorageType Storage,
1185                                     bool ShouldCreate) {
1186   DEFINE_GETIMPL_LOOKUP(DIGlobalVariableExpression, (Variable, Expression));
1187   Metadata *Ops[] = {Variable, Expression};
1188   DEFINE_GETIMPL_STORE_NO_CONSTRUCTOR_ARGS(DIGlobalVariableExpression, Ops);
1189 }
1190
1191 DIObjCProperty *DIObjCProperty::getImpl(
1192     LLVMContext &Context, MDString *Name, Metadata *File, unsigned Line,
1193     MDString *GetterName, MDString *SetterName, unsigned Attributes,
1194     Metadata *Type, StorageType Storage, bool ShouldCreate) {
1195   assert(isCanonical(Name) && "Expected canonical MDString");
1196   assert(isCanonical(GetterName) && "Expected canonical MDString");
1197   assert(isCanonical(SetterName) && "Expected canonical MDString");
1198   DEFINE_GETIMPL_LOOKUP(DIObjCProperty, (Name, File, Line, GetterName,
1199                                          SetterName, Attributes, Type));
1200   Metadata *Ops[] = {Name, File, GetterName, SetterName, Type};
1201   DEFINE_GETIMPL_STORE(DIObjCProperty, (Line, Attributes), Ops);
1202 }
1203
1204 DIImportedEntity *DIImportedEntity::getImpl(LLVMContext &Context, unsigned Tag,
1205                                             Metadata *Scope, Metadata *Entity,
1206                                             Metadata *File, unsigned Line,
1207                                             MDString *Name, StorageType Storage,
1208                                             bool ShouldCreate) {
1209   assert(isCanonical(Name) && "Expected canonical MDString");
1210   DEFINE_GETIMPL_LOOKUP(DIImportedEntity,
1211                         (Tag, Scope, Entity, File, Line, Name));
1212   Metadata *Ops[] = {Scope, Entity, Name, File};
1213   DEFINE_GETIMPL_STORE(DIImportedEntity, (Tag, Line), Ops);
1214 }
1215
1216 DIMacro *DIMacro::getImpl(LLVMContext &Context, unsigned MIType,
1217                           unsigned Line, MDString *Name, MDString *Value,
1218                           StorageType Storage, bool ShouldCreate) {
1219   assert(isCanonical(Name) && "Expected canonical MDString");
1220   DEFINE_GETIMPL_LOOKUP(DIMacro, (MIType, Line, Name, Value));
1221   Metadata *Ops[] = { Name, Value };
1222   DEFINE_GETIMPL_STORE(DIMacro, (MIType, Line), Ops);
1223 }
1224
1225 DIMacroFile *DIMacroFile::getImpl(LLVMContext &Context, unsigned MIType,
1226                                   unsigned Line, Metadata *File,
1227                                   Metadata *Elements, StorageType Storage,
1228                                   bool ShouldCreate) {
1229   DEFINE_GETIMPL_LOOKUP(DIMacroFile,
1230                         (MIType, Line, File, Elements));
1231   Metadata *Ops[] = { File, Elements };
1232   DEFINE_GETIMPL_STORE(DIMacroFile, (MIType, Line), Ops);
1233 }