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