1 //===--- DebugInfo.cpp - Debug Information Helper Classes -----------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the helper classes used to build and interpret debug
11 // information in LLVM IR form.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/IR/DebugInfo.h"
16 #include "LLVMContextImpl.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/ADT/SmallString.h"
20 #include "llvm/ADT/StringSwitch.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/IR/Constants.h"
23 #include "llvm/IR/DIBuilder.h"
24 #include "llvm/IR/DerivedTypes.h"
25 #include "llvm/IR/Instructions.h"
26 #include "llvm/IR/IntrinsicInst.h"
27 #include "llvm/IR/Intrinsics.h"
28 #include "llvm/IR/Module.h"
29 #include "llvm/IR/ValueHandle.h"
30 #include "llvm/Support/Debug.h"
31 #include "llvm/Support/Dwarf.h"
32 #include "llvm/Support/raw_ostream.h"
33 using namespace llvm;
34 using namespace llvm::dwarf;
35 
36 //===----------------------------------------------------------------------===//
37 // DIDescriptor
38 //===----------------------------------------------------------------------===//
39 
40 unsigned DIDescriptor::getFlag(StringRef Flag) {
41   return StringSwitch<unsigned>(Flag)
42 #define HANDLE_DI_FLAG(ID, NAME) .Case("DIFlag" #NAME, Flag##NAME)
43 #include "llvm/IR/DebugInfoFlags.def"
44       .Default(0);
45 }
46 
47 const char *DIDescriptor::getFlagString(unsigned Flag) {
48   switch (Flag) {
49   default:
50     return "";
51 #define HANDLE_DI_FLAG(ID, NAME)                                               \
52   case Flag##NAME:                                                             \
53     return "DIFlag" #NAME;
54 #include "llvm/IR/DebugInfoFlags.def"
55   }
56 }
57 
58 unsigned DIDescriptor::splitFlags(unsigned Flags,
59                                   SmallVectorImpl<unsigned> &SplitFlags) {
60   // Accessibility flags need to be specially handled, since they're packed
61   // together.
62   if (unsigned A = Flags & FlagAccessibility) {
63     if (A == FlagPrivate)
64       SplitFlags.push_back(FlagPrivate);
65     else if (A == FlagProtected)
66       SplitFlags.push_back(FlagProtected);
67     else
68       SplitFlags.push_back(FlagPublic);
69     Flags &= ~A;
70   }
71 
72 #define HANDLE_DI_FLAG(ID, NAME)                                               \
73   if (unsigned Bit = Flags & ID) {                                             \
74     SplitFlags.push_back(Bit);                                                 \
75     Flags &= ~Bit;                                                             \
76   }
77 #include "llvm/IR/DebugInfoFlags.def"
78 
79   return Flags;
80 }
81 
82 bool DIDescriptor::Verify() const {
83   return DbgNode &&
84          (DIDerivedType(DbgNode).Verify() ||
85           DICompositeType(DbgNode).Verify() || DIBasicType(DbgNode).Verify() ||
86           DIVariable(DbgNode).Verify() || DISubprogram(DbgNode).Verify() ||
87           DIGlobalVariable(DbgNode).Verify() || DIFile(DbgNode).Verify() ||
88           DICompileUnit(DbgNode).Verify() || DINameSpace(DbgNode).Verify() ||
89           DILexicalBlock(DbgNode).Verify() ||
90           DILexicalBlockFile(DbgNode).Verify() ||
91           DISubrange(DbgNode).Verify() || DIEnumerator(DbgNode).Verify() ||
92           DIObjCProperty(DbgNode).Verify() ||
93           DITemplateTypeParameter(DbgNode).Verify() ||
94           DITemplateValueParameter(DbgNode).Verify() ||
95           DIImportedEntity(DbgNode).Verify() || DIExpression(DbgNode).Verify());
96 }
97 
98 static Metadata *getField(const MDNode *DbgNode, unsigned Elt) {
99   if (!DbgNode || Elt >= DbgNode->getNumOperands())
100     return nullptr;
101   return DbgNode->getOperand(Elt);
102 }
103 
104 static MDNode *getNodeField(const MDNode *DbgNode, unsigned Elt) {
105   return dyn_cast_or_null<MDNode>(getField(DbgNode, Elt));
106 }
107 
108 static StringRef getStringField(const MDNode *DbgNode, unsigned Elt) {
109   if (MDString *MDS = dyn_cast_or_null<MDString>(getField(DbgNode, Elt)))
110     return MDS->getString();
111   return StringRef();
112 }
113 
114 StringRef DIDescriptor::getStringField(unsigned Elt) const {
115   return ::getStringField(DbgNode, Elt);
116 }
117 
118 uint64_t DIDescriptor::getUInt64Field(unsigned Elt) const {
119   if (auto *C = getConstantField(Elt))
120     if (ConstantInt *CI = dyn_cast<ConstantInt>(C))
121       return CI->getZExtValue();
122 
123   return 0;
124 }
125 
126 int64_t DIDescriptor::getInt64Field(unsigned Elt) const {
127   if (auto *C = getConstantField(Elt))
128     if (ConstantInt *CI = dyn_cast<ConstantInt>(C))
129       return CI->getZExtValue();
130 
131   return 0;
132 }
133 
134 DIDescriptor DIDescriptor::getDescriptorField(unsigned Elt) const {
135   MDNode *Field = getNodeField(DbgNode, Elt);
136   return DIDescriptor(Field);
137 }
138 
139 GlobalVariable *DIDescriptor::getGlobalVariableField(unsigned Elt) const {
140   return dyn_cast_or_null<GlobalVariable>(getConstantField(Elt));
141 }
142 
143 Constant *DIDescriptor::getConstantField(unsigned Elt) const {
144   if (!DbgNode)
145     return nullptr;
146 
147   if (Elt < DbgNode->getNumOperands())
148     if (auto *C =
149             dyn_cast_or_null<ConstantAsMetadata>(DbgNode->getOperand(Elt)))
150       return C->getValue();
151   return nullptr;
152 }
153 
154 Function *DIDescriptor::getFunctionField(unsigned Elt) const {
155   return dyn_cast_or_null<Function>(getConstantField(Elt));
156 }
157 
158 /// \brief Return the size reported by the variable's type.
159 unsigned DIVariable::getSizeInBits(const DITypeIdentifierMap &Map) {
160   DIType Ty = getType().resolve(Map);
161   // Follow derived types until we reach a type that
162   // reports back a size.
163   while (Ty.isDerivedType() && !Ty.getSizeInBits()) {
164     DIDerivedType DT(&*Ty);
165     Ty = DT.getTypeDerivedFrom().resolve(Map);
166   }
167   assert(Ty.getSizeInBits() && "type with size 0");
168   return Ty.getSizeInBits();
169 }
170 
171 bool DIExpression::isBitPiece() const {
172   unsigned N = getNumElements();
173   return N >=3 && getElement(N-3) == dwarf::DW_OP_bit_piece;
174 }
175 
176 uint64_t DIExpression::getBitPieceOffset() const {
177   assert(isBitPiece() && "not a piece");
178   return getElement(getNumElements()-2);
179 }
180 
181 uint64_t DIExpression::getBitPieceSize() const {
182   assert(isBitPiece() && "not a piece");
183   return getElement(getNumElements()-1);
184 }
185 
186 DIExpression::iterator DIExpression::Operand::getNext() const {
187   iterator it(I);
188   return ++it;
189 }
190 
191 //===----------------------------------------------------------------------===//
192 // Simple Descriptor Constructors and other Methods
193 //===----------------------------------------------------------------------===//
194 
195 void DIDescriptor::replaceAllUsesWith(LLVMContext &, DIDescriptor D) {
196   assert(DbgNode && "Trying to replace an unverified type!");
197   assert(DbgNode->isTemporary() && "Expected temporary node");
198   TempMDNode Temp(get());
199 
200   // Since we use a TrackingVH for the node, its easy for clients to manufacture
201   // legitimate situations where they want to replaceAllUsesWith() on something
202   // which, due to uniquing, has merged with the source. We shield clients from
203   // this detail by allowing a value to be replaced with replaceAllUsesWith()
204   // itself.
205   if (Temp.get() == D.get()) {
206     DbgNode = MDNode::replaceWithUniqued(std::move(Temp));
207     return;
208   }
209 
210   Temp->replaceAllUsesWith(D.get());
211   DbgNode = D.get();
212 }
213 
214 void DIDescriptor::replaceAllUsesWith(MDNode *D) {
215   assert(DbgNode && "Trying to replace an unverified type!");
216   assert(DbgNode != D && "This replacement should always happen");
217   assert(DbgNode->isTemporary() && "Expected temporary node");
218   TempMDNode Node(get());
219   Node->replaceAllUsesWith(D);
220 }
221 
222 bool DICompileUnit::Verify() const {
223   if (!isCompileUnit())
224     return false;
225 
226   // Don't bother verifying the compilation directory or producer string
227   // as those could be empty.
228   return !getFilename().empty();
229 }
230 
231 bool DIObjCProperty::Verify() const { return isObjCProperty(); }
232 
233 /// \brief Check if a value can be a reference to a type.
234 static bool isTypeRef(const Metadata *MD) {
235   if (!MD)
236     return true;
237   if (auto *S = dyn_cast<MDString>(MD))
238     return !S->getString().empty();
239   return isa<MDType>(MD);
240 }
241 
242 /// \brief Check if a value can be a ScopeRef.
243 static bool isScopeRef(const Metadata *MD) {
244   if (!MD)
245     return true;
246   if (auto *S = dyn_cast<MDString>(MD))
247     return !S->getString().empty();
248   return isa<MDScope>(MD);
249 }
250 
251 #ifndef NDEBUG
252 /// \brief Check if a value can be a DescriptorRef.
253 static bool isDescriptorRef(const Metadata *MD) {
254   if (!MD)
255     return true;
256   if (auto *S = dyn_cast<MDString>(MD))
257     return !S->getString().empty();
258   return isa<MDNode>(MD);
259 }
260 #endif
261 
262 bool DIType::Verify() const {
263   auto *N = getRaw();
264   if (!N)
265     return false;
266   if (!isScopeRef(N->getScope()))
267     return false;
268 
269   // FIXME: Sink this into the various subclass verifies.
270   uint16_t Tag = getTag();
271   if (!isBasicType() && Tag != dwarf::DW_TAG_const_type &&
272       Tag != dwarf::DW_TAG_volatile_type && Tag != dwarf::DW_TAG_pointer_type &&
273       Tag != dwarf::DW_TAG_ptr_to_member_type &&
274       Tag != dwarf::DW_TAG_reference_type &&
275       Tag != dwarf::DW_TAG_rvalue_reference_type &&
276       Tag != dwarf::DW_TAG_restrict_type && Tag != dwarf::DW_TAG_array_type &&
277       Tag != dwarf::DW_TAG_enumeration_type &&
278       Tag != dwarf::DW_TAG_subroutine_type &&
279       Tag != dwarf::DW_TAG_inheritance && Tag != dwarf::DW_TAG_friend &&
280       getFilename().empty())
281     return false;
282 
283   // DIType is abstract, it should be a BasicType, a DerivedType or
284   // a CompositeType.
285   if (isBasicType())
286     return DIBasicType(DbgNode).Verify();
287   else if (isCompositeType())
288     return DICompositeType(DbgNode).Verify();
289   else if (isDerivedType())
290     return DIDerivedType(DbgNode).Verify();
291   else
292     return false;
293 }
294 
295 bool DIBasicType::Verify() const { return getRaw(); }
296 
297 bool DIDerivedType::Verify() const {
298   auto *N = getRaw();
299   if (!N)
300     return false;
301   if (getTag() == dwarf::DW_TAG_ptr_to_member_type) {
302     auto *D = dyn_cast<MDDerivedType>(N);
303     if (!D)
304       return false;
305     if (!isTypeRef(D->getExtraData()))
306       return false;
307   }
308   return isTypeRef(N->getBaseType());
309 }
310 
311 bool DICompositeType::Verify() const {
312   auto *N = getRaw();
313   return N && isTypeRef(N->getBaseType()) && isTypeRef(N->getVTableHolder()) &&
314          !(isLValueReference() && isRValueReference());
315 }
316 
317 bool DISubprogram::Verify() const {
318   auto *N = getRaw();
319   if (!N)
320     return false;
321 
322   if (!isScopeRef(N->getScope()))
323     return false;
324 
325   if (auto *Op = N->getType())
326     if (!isa<MDNode>(Op))
327       return false;
328 
329   if (!isTypeRef(getContainingType()))
330     return false;
331 
332   if (isLValueReference() && isRValueReference())
333     return false;
334 
335   // If a DISubprogram has an llvm::Function*, then scope chains from all
336   // instructions within the function should lead to this DISubprogram.
337   if (auto *F = getFunction()) {
338     for (auto &BB : *F) {
339       for (auto &I : BB) {
340         DebugLoc DL = I.getDebugLoc();
341         if (DL.isUnknown())
342           continue;
343 
344         MDNode *Scope = nullptr;
345         MDNode *IA = nullptr;
346         // walk the inlined-at scopes
347         while ((IA = DL.getInlinedAt()))
348           DL = DebugLoc::getFromDILocation(IA);
349         DL.getScopeAndInlinedAt(Scope, IA);
350         if (!Scope)
351           return false;
352         assert(!IA);
353         while (!DIDescriptor(Scope).isSubprogram()) {
354           DILexicalBlockFile D(Scope);
355           Scope = D.isLexicalBlockFile()
356                       ? D.getScope()
357                       : DebugLoc::getFromDILexicalBlock(Scope).getScope();
358           if (!Scope)
359             return false;
360         }
361         if (!DISubprogram(Scope).describes(F))
362           return false;
363       }
364     }
365   }
366 
367   return true;
368 }
369 
370 bool DIGlobalVariable::Verify() const {
371   auto *N = getRaw();
372 
373   if (!N)
374     return false;
375 
376   if (N->getDisplayName().empty())
377     return false;
378 
379   if (auto *Op = N->getScope())
380     if (!isa<MDNode>(Op))
381       return false;
382 
383   if (auto *Op = N->getStaticDataMemberDeclaration())
384     if (!isa<MDNode>(Op))
385       return false;
386 
387   return isTypeRef(N->getType());
388 }
389 
390 bool DIVariable::Verify() const {
391   auto *N = getRaw();
392 
393   if (!N)
394     return false;
395 
396   if (auto *Op = N->getScope())
397     if (!isa<MDNode>(Op))
398       return false;
399 
400   return isTypeRef(N->getType());
401 }
402 
403 bool DIExpression::Verify() const {
404   // FIXME: This should return false if it's null!
405   auto *N = getRaw();
406   return !N || N->isValid();
407 }
408 
409 bool DILocation::Verify() const { return getRaw(); }
410 bool DINameSpace::Verify() const { return getRaw(); }
411 bool DIFile::Verify() const { return getRaw(); }
412 bool DIEnumerator::Verify() const { return getRaw(); }
413 bool DISubrange::Verify() const { return getRaw(); }
414 bool DILexicalBlock::Verify() const { return getRaw(); }
415 bool DILexicalBlockFile::Verify() const { return getRaw(); }
416 bool DITemplateTypeParameter::Verify() const { return getRaw(); }
417 bool DITemplateValueParameter::Verify() const { return getRaw(); }
418 bool DIImportedEntity::Verify() const { return getRaw(); }
419 
420 void DICompositeType::setArraysHelper(MDNode *Elements, MDNode *TParams) {
421   TypedTrackingMDRef<MDCompositeTypeBase> N(getRaw());
422   if (Elements)
423     N->replaceElements(cast<MDTuple>(Elements));
424   if (TParams)
425     N->replaceTemplateParams(cast<MDTuple>(TParams));
426   DbgNode = N;
427 }
428 
429 DIScopeRef DIScope::getRef() const {
430   if (!isCompositeType())
431     return DIScopeRef(*this);
432   DICompositeType DTy(DbgNode);
433   if (!DTy.getIdentifier())
434     return DIScopeRef(*this);
435   return DIScopeRef(DTy.getIdentifier());
436 }
437 
438 void DICompositeType::setContainingType(DICompositeType ContainingType) {
439   TypedTrackingMDRef<MDCompositeTypeBase> N(getRaw());
440   N->replaceVTableHolder(ContainingType.getRef());
441   DbgNode = N;
442 }
443 
444 bool DIVariable::isInlinedFnArgument(const Function *CurFn) {
445   assert(CurFn && "Invalid function");
446   if (!getContext().isSubprogram())
447     return false;
448   // This variable is not inlined function argument if its scope
449   // does not describe current function.
450   return !DISubprogram(getContext()).describes(CurFn);
451 }
452 
453 Function *DISubprogram::getFunction() const {
454   if (auto *N = getRaw())
455     if (auto *C = dyn_cast_or_null<ConstantAsMetadata>(N->getFunction()))
456       return dyn_cast<Function>(C->getValue());
457   return nullptr;
458 }
459 
460 bool DISubprogram::describes(const Function *F) {
461   assert(F && "Invalid function");
462   if (F == getFunction())
463     return true;
464   StringRef Name = getLinkageName();
465   if (Name.empty())
466     Name = getName();
467   if (F->getName() == Name)
468     return true;
469   return false;
470 }
471 
472 GlobalVariable *DIGlobalVariable::getGlobal() const {
473   return dyn_cast_or_null<GlobalVariable>(getConstant());
474 }
475 
476 DIScopeRef DIScope::getContext() const {
477 
478   if (isType())
479     return DIType(DbgNode).getContext();
480 
481   if (isSubprogram())
482     return DIScopeRef(DISubprogram(DbgNode).getContext());
483 
484   if (isLexicalBlock())
485     return DIScopeRef(DILexicalBlock(DbgNode).getContext());
486 
487   if (isLexicalBlockFile())
488     return DIScopeRef(DILexicalBlockFile(DbgNode).getContext());
489 
490   if (isNameSpace())
491     return DIScopeRef(DINameSpace(DbgNode).getContext());
492 
493   assert((isFile() || isCompileUnit()) && "Unhandled type of scope.");
494   return DIScopeRef(nullptr);
495 }
496 
497 StringRef DIScope::getName() const {
498   if (isType())
499     return DIType(DbgNode).getName();
500   if (isSubprogram())
501     return DISubprogram(DbgNode).getName();
502   if (isNameSpace())
503     return DINameSpace(DbgNode).getName();
504   assert((isLexicalBlock() || isLexicalBlockFile() || isFile() ||
505           isCompileUnit()) &&
506          "Unhandled type of scope.");
507   return StringRef();
508 }
509 
510 StringRef DIScope::getFilename() const {
511   if (auto *N = getRaw())
512     return ::getStringField(dyn_cast_or_null<MDNode>(N->getFile()), 0);
513   return "";
514 }
515 
516 StringRef DIScope::getDirectory() const {
517   if (auto *N = getRaw())
518     return ::getStringField(dyn_cast_or_null<MDNode>(N->getFile()), 1);
519   return "";
520 }
521 
522 void DICompileUnit::replaceSubprograms(DIArray Subprograms) {
523   assert(Verify() && "Expected compile unit");
524   getRaw()->replaceSubprograms(cast_or_null<MDTuple>(Subprograms.get()));
525 }
526 
527 void DICompileUnit::replaceGlobalVariables(DIArray GlobalVariables) {
528   assert(Verify() && "Expected compile unit");
529   getRaw()->replaceGlobalVariables(
530       cast_or_null<MDTuple>(GlobalVariables.get()));
531 }
532 
533 DILocation DILocation::copyWithNewScope(LLVMContext &Ctx,
534                                         DILexicalBlockFile NewScope) {
535   assert(Verify());
536   assert(NewScope && "Expected valid scope");
537 
538   const auto *Old = cast<MDLocation>(DbgNode);
539   return DILocation(MDLocation::get(Ctx, Old->getLine(), Old->getColumn(),
540                                     NewScope, Old->getInlinedAt()));
541 }
542 
543 unsigned DILocation::computeNewDiscriminator(LLVMContext &Ctx) {
544   std::pair<const char *, unsigned> Key(getFilename().data(), getLineNumber());
545   return ++Ctx.pImpl->DiscriminatorTable[Key];
546 }
547 
548 DIVariable llvm::createInlinedVariable(MDNode *DV, MDNode *InlinedScope,
549                                        LLVMContext &VMContext) {
550   assert(DIVariable(DV).Verify() && "Expected a DIVariable");
551   return cast<MDLocalVariable>(DV)
552       ->withInline(cast_or_null<MDLocation>(InlinedScope));
553 }
554 
555 DIVariable llvm::cleanseInlinedVariable(MDNode *DV, LLVMContext &VMContext) {
556   assert(DIVariable(DV).Verify() && "Expected a DIVariable");
557   return cast<MDLocalVariable>(DV)->withoutInline();
558 }
559 
560 DISubprogram llvm::getDISubprogram(const MDNode *Scope) {
561   DIDescriptor D(Scope);
562   if (D.isSubprogram())
563     return DISubprogram(Scope);
564 
565   if (D.isLexicalBlockFile())
566     return getDISubprogram(DILexicalBlockFile(Scope).getContext());
567 
568   if (D.isLexicalBlock())
569     return getDISubprogram(DILexicalBlock(Scope).getContext());
570 
571   return DISubprogram();
572 }
573 
574 DISubprogram llvm::getDISubprogram(const Function *F) {
575   // We look for the first instr that has a debug annotation leading back to F.
576   for (auto &BB : *F) {
577     auto Inst = std::find_if(BB.begin(), BB.end(), [](const Instruction &Inst) {
578       return !Inst.getDebugLoc().isUnknown();
579     });
580     if (Inst == BB.end())
581       continue;
582     DebugLoc DLoc = Inst->getDebugLoc();
583     const MDNode *Scope = DLoc.getScopeNode();
584     DISubprogram Subprogram = getDISubprogram(Scope);
585     return Subprogram.describes(F) ? Subprogram : DISubprogram();
586   }
587 
588   return DISubprogram();
589 }
590 
591 DICompositeType llvm::getDICompositeType(DIType T) {
592   if (T.isCompositeType())
593     return DICompositeType(T);
594 
595   if (T.isDerivedType()) {
596     // This function is currently used by dragonegg and dragonegg does
597     // not generate identifier for types, so using an empty map to resolve
598     // DerivedFrom should be fine.
599     DITypeIdentifierMap EmptyMap;
600     return getDICompositeType(
601         DIDerivedType(T).getTypeDerivedFrom().resolve(EmptyMap));
602   }
603 
604   return DICompositeType();
605 }
606 
607 DITypeIdentifierMap
608 llvm::generateDITypeIdentifierMap(const NamedMDNode *CU_Nodes) {
609   DITypeIdentifierMap Map;
610   for (unsigned CUi = 0, CUe = CU_Nodes->getNumOperands(); CUi != CUe; ++CUi) {
611     DICompileUnit CU(CU_Nodes->getOperand(CUi));
612     DIArray Retain = CU.getRetainedTypes();
613     for (unsigned Ti = 0, Te = Retain.getNumElements(); Ti != Te; ++Ti) {
614       if (!Retain.getElement(Ti).isCompositeType())
615         continue;
616       DICompositeType Ty(Retain.getElement(Ti));
617       if (MDString *TypeId = Ty.getIdentifier()) {
618         // Definition has priority over declaration.
619         // Try to insert (TypeId, Ty) to Map.
620         std::pair<DITypeIdentifierMap::iterator, bool> P =
621             Map.insert(std::make_pair(TypeId, Ty));
622         // If TypeId already exists in Map and this is a definition, replace
623         // whatever we had (declaration or definition) with the definition.
624         if (!P.second && !Ty.isForwardDecl())
625           P.first->second = Ty;
626       }
627     }
628   }
629   return Map;
630 }
631 
632 //===----------------------------------------------------------------------===//
633 // DebugInfoFinder implementations.
634 //===----------------------------------------------------------------------===//
635 
636 void DebugInfoFinder::reset() {
637   CUs.clear();
638   SPs.clear();
639   GVs.clear();
640   TYs.clear();
641   Scopes.clear();
642   NodesSeen.clear();
643   TypeIdentifierMap.clear();
644   TypeMapInitialized = false;
645 }
646 
647 void DebugInfoFinder::InitializeTypeMap(const Module &M) {
648   if (!TypeMapInitialized)
649     if (NamedMDNode *CU_Nodes = M.getNamedMetadata("llvm.dbg.cu")) {
650       TypeIdentifierMap = generateDITypeIdentifierMap(CU_Nodes);
651       TypeMapInitialized = true;
652     }
653 }
654 
655 void DebugInfoFinder::processModule(const Module &M) {
656   InitializeTypeMap(M);
657   if (NamedMDNode *CU_Nodes = M.getNamedMetadata("llvm.dbg.cu")) {
658     for (unsigned i = 0, e = CU_Nodes->getNumOperands(); i != e; ++i) {
659       DICompileUnit CU(CU_Nodes->getOperand(i));
660       addCompileUnit(CU);
661       DIArray GVs = CU.getGlobalVariables();
662       for (unsigned i = 0, e = GVs.getNumElements(); i != e; ++i) {
663         DIGlobalVariable DIG(GVs.getElement(i));
664         if (addGlobalVariable(DIG)) {
665           processScope(DIG.getContext());
666           processType(DIG.getType().resolve(TypeIdentifierMap));
667         }
668       }
669       DIArray SPs = CU.getSubprograms();
670       for (unsigned i = 0, e = SPs.getNumElements(); i != e; ++i)
671         processSubprogram(DISubprogram(SPs.getElement(i)));
672       DIArray EnumTypes = CU.getEnumTypes();
673       for (unsigned i = 0, e = EnumTypes.getNumElements(); i != e; ++i)
674         processType(DIType(EnumTypes.getElement(i)));
675       DIArray RetainedTypes = CU.getRetainedTypes();
676       for (unsigned i = 0, e = RetainedTypes.getNumElements(); i != e; ++i)
677         processType(DIType(RetainedTypes.getElement(i)));
678       DIArray Imports = CU.getImportedEntities();
679       for (unsigned i = 0, e = Imports.getNumElements(); i != e; ++i) {
680         DIImportedEntity Import = DIImportedEntity(Imports.getElement(i));
681         DIDescriptor Entity = Import.getEntity().resolve(TypeIdentifierMap);
682         if (Entity.isType())
683           processType(DIType(Entity));
684         else if (Entity.isSubprogram())
685           processSubprogram(DISubprogram(Entity));
686         else if (Entity.isNameSpace())
687           processScope(DINameSpace(Entity).getContext());
688       }
689     }
690   }
691 }
692 
693 void DebugInfoFinder::processLocation(const Module &M, DILocation Loc) {
694   if (!Loc)
695     return;
696   InitializeTypeMap(M);
697   processScope(Loc.getScope());
698   processLocation(M, Loc.getOrigLocation());
699 }
700 
701 void DebugInfoFinder::processType(DIType DT) {
702   if (!addType(DT))
703     return;
704   processScope(DT.getContext().resolve(TypeIdentifierMap));
705   if (DT.isCompositeType()) {
706     DICompositeType DCT(DT);
707     processType(DCT.getTypeDerivedFrom().resolve(TypeIdentifierMap));
708     if (DT.isSubroutineType()) {
709       DITypeArray DTA = DISubroutineType(DT).getTypeArray();
710       for (unsigned i = 0, e = DTA.getNumElements(); i != e; ++i)
711         processType(DTA.getElement(i).resolve(TypeIdentifierMap));
712       return;
713     }
714     DIArray DA = DCT.getElements();
715     for (unsigned i = 0, e = DA.getNumElements(); i != e; ++i) {
716       DIDescriptor D = DA.getElement(i);
717       if (D.isType())
718         processType(DIType(D));
719       else if (D.isSubprogram())
720         processSubprogram(DISubprogram(D));
721     }
722   } else if (DT.isDerivedType()) {
723     DIDerivedType DDT(DT);
724     processType(DDT.getTypeDerivedFrom().resolve(TypeIdentifierMap));
725   }
726 }
727 
728 void DebugInfoFinder::processScope(DIScope Scope) {
729   if (Scope.isType()) {
730     DIType Ty(Scope);
731     processType(Ty);
732     return;
733   }
734   if (Scope.isCompileUnit()) {
735     addCompileUnit(DICompileUnit(Scope));
736     return;
737   }
738   if (Scope.isSubprogram()) {
739     processSubprogram(DISubprogram(Scope));
740     return;
741   }
742   if (!addScope(Scope))
743     return;
744   if (Scope.isLexicalBlock()) {
745     DILexicalBlock LB(Scope);
746     processScope(LB.getContext());
747   } else if (Scope.isLexicalBlockFile()) {
748     DILexicalBlockFile LBF = DILexicalBlockFile(Scope);
749     processScope(LBF.getScope());
750   } else if (Scope.isNameSpace()) {
751     DINameSpace NS(Scope);
752     processScope(NS.getContext());
753   }
754 }
755 
756 void DebugInfoFinder::processSubprogram(DISubprogram SP) {
757   if (!addSubprogram(SP))
758     return;
759   processScope(SP.getContext().resolve(TypeIdentifierMap));
760   processType(SP.getType());
761   DIArray TParams = SP.getTemplateParams();
762   for (unsigned I = 0, E = TParams.getNumElements(); I != E; ++I) {
763     DIDescriptor Element = TParams.getElement(I);
764     if (Element.isTemplateTypeParameter()) {
765       DITemplateTypeParameter TType(Element);
766       processType(TType.getType().resolve(TypeIdentifierMap));
767     } else if (Element.isTemplateValueParameter()) {
768       DITemplateValueParameter TVal(Element);
769       processType(TVal.getType().resolve(TypeIdentifierMap));
770     }
771   }
772 }
773 
774 void DebugInfoFinder::processDeclare(const Module &M,
775                                      const DbgDeclareInst *DDI) {
776   MDNode *N = dyn_cast<MDNode>(DDI->getVariable());
777   if (!N)
778     return;
779   InitializeTypeMap(M);
780 
781   DIDescriptor DV(N);
782   if (!DV.isVariable())
783     return;
784 
785   if (!NodesSeen.insert(DV).second)
786     return;
787   processScope(DIVariable(N).getContext());
788   processType(DIVariable(N).getType().resolve(TypeIdentifierMap));
789 }
790 
791 void DebugInfoFinder::processValue(const Module &M, const DbgValueInst *DVI) {
792   MDNode *N = dyn_cast<MDNode>(DVI->getVariable());
793   if (!N)
794     return;
795   InitializeTypeMap(M);
796 
797   DIDescriptor DV(N);
798   if (!DV.isVariable())
799     return;
800 
801   if (!NodesSeen.insert(DV).second)
802     return;
803   processScope(DIVariable(N).getContext());
804   processType(DIVariable(N).getType().resolve(TypeIdentifierMap));
805 }
806 
807 bool DebugInfoFinder::addType(DIType DT) {
808   if (!DT)
809     return false;
810 
811   if (!NodesSeen.insert(DT).second)
812     return false;
813 
814   TYs.push_back(DT);
815   return true;
816 }
817 
818 bool DebugInfoFinder::addCompileUnit(DICompileUnit CU) {
819   if (!CU)
820     return false;
821   if (!NodesSeen.insert(CU).second)
822     return false;
823 
824   CUs.push_back(CU);
825   return true;
826 }
827 
828 bool DebugInfoFinder::addGlobalVariable(DIGlobalVariable DIG) {
829   if (!DIG)
830     return false;
831 
832   if (!NodesSeen.insert(DIG).second)
833     return false;
834 
835   GVs.push_back(DIG);
836   return true;
837 }
838 
839 bool DebugInfoFinder::addSubprogram(DISubprogram SP) {
840   if (!SP)
841     return false;
842 
843   if (!NodesSeen.insert(SP).second)
844     return false;
845 
846   SPs.push_back(SP);
847   return true;
848 }
849 
850 bool DebugInfoFinder::addScope(DIScope Scope) {
851   if (!Scope)
852     return false;
853   // FIXME: Ocaml binding generates a scope with no content, we treat it
854   // as null for now.
855   if (Scope->getNumOperands() == 0)
856     return false;
857   if (!NodesSeen.insert(Scope).second)
858     return false;
859   Scopes.push_back(Scope);
860   return true;
861 }
862 
863 //===----------------------------------------------------------------------===//
864 // DIDescriptor: dump routines for all descriptors.
865 //===----------------------------------------------------------------------===//
866 
867 void DIDescriptor::dump() const {
868   print(dbgs());
869   dbgs() << '\n';
870 }
871 
872 void DIDescriptor::print(raw_ostream &OS) const {
873   if (!get())
874     return;
875   get()->print(OS);
876 }
877 
878 static void printDebugLoc(DebugLoc DL, raw_ostream &CommentOS,
879                           const LLVMContext &Ctx) {
880   if (!DL.isUnknown()) { // Print source line info.
881     DIScope Scope(DL.getScope(Ctx));
882     assert(Scope.isScope() && "Scope of a DebugLoc should be a DIScope.");
883     // Omit the directory, because it's likely to be long and uninteresting.
884     CommentOS << Scope.getFilename();
885     CommentOS << ':' << DL.getLine();
886     if (DL.getCol() != 0)
887       CommentOS << ':' << DL.getCol();
888     DebugLoc InlinedAtDL = DebugLoc::getFromDILocation(DL.getInlinedAt(Ctx));
889     if (!InlinedAtDL.isUnknown()) {
890       CommentOS << " @[ ";
891       printDebugLoc(InlinedAtDL, CommentOS, Ctx);
892       CommentOS << " ]";
893     }
894   }
895 }
896 
897 void DIVariable::printExtendedName(raw_ostream &OS) const {
898   const LLVMContext &Ctx = DbgNode->getContext();
899   StringRef Res = getName();
900   if (!Res.empty())
901     OS << Res << "," << getLineNumber();
902   if (MDNode *InlinedAt = getInlinedAt()) {
903     DebugLoc InlinedAtDL = DebugLoc::getFromDILocation(InlinedAt);
904     if (!InlinedAtDL.isUnknown()) {
905       OS << " @[";
906       printDebugLoc(InlinedAtDL, OS, Ctx);
907       OS << "]";
908     }
909   }
910 }
911 
912 template <> DIRef<DIDescriptor>::DIRef(const Metadata *V) : Val(V) {
913   assert(isDescriptorRef(V) &&
914          "DIDescriptorRef should be a MDString or MDNode");
915 }
916 template <> DIRef<DIScope>::DIRef(const Metadata *V) : Val(V) {
917   assert(isScopeRef(V) && "DIScopeRef should be a MDString or MDNode");
918 }
919 template <> DIRef<DIType>::DIRef(const Metadata *V) : Val(V) {
920   assert(isTypeRef(V) && "DITypeRef should be a MDString or MDNode");
921 }
922 
923 template <>
924 DIDescriptorRef DIDescriptor::getFieldAs<DIDescriptorRef>(unsigned Elt) const {
925   return DIDescriptorRef(cast_or_null<Metadata>(getField(DbgNode, Elt)));
926 }
927 template <>
928 DIScopeRef DIDescriptor::getFieldAs<DIScopeRef>(unsigned Elt) const {
929   return DIScopeRef(cast_or_null<Metadata>(getField(DbgNode, Elt)));
930 }
931 template <> DITypeRef DIDescriptor::getFieldAs<DITypeRef>(unsigned Elt) const {
932   return DITypeRef(cast_or_null<Metadata>(getField(DbgNode, Elt)));
933 }
934 
935 bool llvm::StripDebugInfo(Module &M) {
936   bool Changed = false;
937 
938   // Remove all of the calls to the debugger intrinsics, and remove them from
939   // the module.
940   if (Function *Declare = M.getFunction("llvm.dbg.declare")) {
941     while (!Declare->use_empty()) {
942       CallInst *CI = cast<CallInst>(Declare->user_back());
943       CI->eraseFromParent();
944     }
945     Declare->eraseFromParent();
946     Changed = true;
947   }
948 
949   if (Function *DbgVal = M.getFunction("llvm.dbg.value")) {
950     while (!DbgVal->use_empty()) {
951       CallInst *CI = cast<CallInst>(DbgVal->user_back());
952       CI->eraseFromParent();
953     }
954     DbgVal->eraseFromParent();
955     Changed = true;
956   }
957 
958   for (Module::named_metadata_iterator NMI = M.named_metadata_begin(),
959          NME = M.named_metadata_end(); NMI != NME;) {
960     NamedMDNode *NMD = NMI;
961     ++NMI;
962     if (NMD->getName().startswith("llvm.dbg.")) {
963       NMD->eraseFromParent();
964       Changed = true;
965     }
966   }
967 
968   for (Module::iterator MI = M.begin(), ME = M.end(); MI != ME; ++MI)
969     for (Function::iterator FI = MI->begin(), FE = MI->end(); FI != FE;
970          ++FI)
971       for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE;
972            ++BI) {
973         if (!BI->getDebugLoc().isUnknown()) {
974           Changed = true;
975           BI->setDebugLoc(DebugLoc());
976         }
977       }
978 
979   return Changed;
980 }
981 
982 unsigned llvm::getDebugMetadataVersionFromModule(const Module &M) {
983   if (auto *Val = mdconst::dyn_extract_or_null<ConstantInt>(
984           M.getModuleFlag("Debug Info Version")))
985     return Val->getZExtValue();
986   return 0;
987 }
988 
989 llvm::DenseMap<const llvm::Function *, llvm::DISubprogram>
990 llvm::makeSubprogramMap(const Module &M) {
991   DenseMap<const Function *, DISubprogram> R;
992 
993   NamedMDNode *CU_Nodes = M.getNamedMetadata("llvm.dbg.cu");
994   if (!CU_Nodes)
995     return R;
996 
997   for (MDNode *N : CU_Nodes->operands()) {
998     DICompileUnit CUNode(N);
999     DIArray SPs = CUNode.getSubprograms();
1000     for (unsigned i = 0, e = SPs.getNumElements(); i != e; ++i) {
1001       DISubprogram SP(SPs.getElement(i));
1002       if (Function *F = SP.getFunction())
1003         R.insert(std::make_pair(F, SP));
1004     }
1005   }
1006   return R;
1007 }
1008