fdea05e50a2cca0970fdd2d9461eaa6ece4e637d
[oota-llvm.git] / lib / CodeGen / AsmPrinter / DwarfDebug.cpp
1 //===-- llvm/CodeGen/DwarfDebug.cpp - Dwarf Debug Framework ---------------===//
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 contains support for writing dwarf debug info into asm files.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "DwarfDebug.h"
15 #include "ByteStreamer.h"
16 #include "DIEHash.h"
17 #include "DebugLocEntry.h"
18 #include "DwarfCompileUnit.h"
19 #include "DwarfExpression.h"
20 #include "DwarfUnit.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/ADT/Statistic.h"
23 #include "llvm/ADT/StringExtras.h"
24 #include "llvm/ADT/Triple.h"
25 #include "llvm/CodeGen/DIE.h"
26 #include "llvm/CodeGen/MachineFunction.h"
27 #include "llvm/CodeGen/MachineModuleInfo.h"
28 #include "llvm/IR/Constants.h"
29 #include "llvm/IR/DIBuilder.h"
30 #include "llvm/IR/DataLayout.h"
31 #include "llvm/IR/DebugInfo.h"
32 #include "llvm/IR/Instructions.h"
33 #include "llvm/IR/Module.h"
34 #include "llvm/IR/ValueHandle.h"
35 #include "llvm/MC/MCAsmInfo.h"
36 #include "llvm/MC/MCSection.h"
37 #include "llvm/MC/MCStreamer.h"
38 #include "llvm/MC/MCSymbol.h"
39 #include "llvm/Support/CommandLine.h"
40 #include "llvm/Support/Debug.h"
41 #include "llvm/Support/Dwarf.h"
42 #include "llvm/Support/Endian.h"
43 #include "llvm/Support/ErrorHandling.h"
44 #include "llvm/Support/FormattedStream.h"
45 #include "llvm/Support/LEB128.h"
46 #include "llvm/Support/MD5.h"
47 #include "llvm/Support/Path.h"
48 #include "llvm/Support/Timer.h"
49 #include "llvm/Support/raw_ostream.h"
50 #include "llvm/Target/TargetFrameLowering.h"
51 #include "llvm/Target/TargetLoweringObjectFile.h"
52 #include "llvm/Target/TargetMachine.h"
53 #include "llvm/Target/TargetOptions.h"
54 #include "llvm/Target/TargetRegisterInfo.h"
55 #include "llvm/Target/TargetSubtargetInfo.h"
56 using namespace llvm;
57
58 #define DEBUG_TYPE "dwarfdebug"
59
60 static cl::opt<bool>
61 DisableDebugInfoPrinting("disable-debug-info-print", cl::Hidden,
62                          cl::desc("Disable debug info printing"));
63
64 static cl::opt<bool> UnknownLocations(
65     "use-unknown-locations", cl::Hidden,
66     cl::desc("Make an absence of debug location information explicit."),
67     cl::init(false));
68
69 static cl::opt<bool>
70 GenerateGnuPubSections("generate-gnu-dwarf-pub-sections", cl::Hidden,
71                        cl::desc("Generate GNU-style pubnames and pubtypes"),
72                        cl::init(false));
73
74 static cl::opt<bool> GenerateARangeSection("generate-arange-section",
75                                            cl::Hidden,
76                                            cl::desc("Generate dwarf aranges"),
77                                            cl::init(false));
78
79 namespace {
80 enum DefaultOnOff { Default, Enable, Disable };
81 }
82
83 static cl::opt<DefaultOnOff>
84 DwarfAccelTables("dwarf-accel-tables", cl::Hidden,
85                  cl::desc("Output prototype dwarf accelerator tables."),
86                  cl::values(clEnumVal(Default, "Default for platform"),
87                             clEnumVal(Enable, "Enabled"),
88                             clEnumVal(Disable, "Disabled"), clEnumValEnd),
89                  cl::init(Default));
90
91 static cl::opt<DefaultOnOff>
92 SplitDwarf("split-dwarf", cl::Hidden,
93            cl::desc("Output DWARF5 split debug info."),
94            cl::values(clEnumVal(Default, "Default for platform"),
95                       clEnumVal(Enable, "Enabled"),
96                       clEnumVal(Disable, "Disabled"), clEnumValEnd),
97            cl::init(Default));
98
99 static cl::opt<DefaultOnOff>
100 DwarfPubSections("generate-dwarf-pub-sections", cl::Hidden,
101                  cl::desc("Generate DWARF pubnames and pubtypes sections"),
102                  cl::values(clEnumVal(Default, "Default for platform"),
103                             clEnumVal(Enable, "Enabled"),
104                             clEnumVal(Disable, "Disabled"), clEnumValEnd),
105                  cl::init(Default));
106
107 static const char *const DWARFGroupName = "DWARF Emission";
108 static const char *const DbgTimerName = "DWARF Debug Writer";
109
110 void DebugLocDwarfExpression::EmitOp(uint8_t Op, const char *Comment) {
111   BS.EmitInt8(
112       Op, Comment ? Twine(Comment) + " " + dwarf::OperationEncodingString(Op)
113                   : dwarf::OperationEncodingString(Op));
114 }
115
116 void DebugLocDwarfExpression::EmitSigned(int64_t Value) {
117   BS.EmitSLEB128(Value, Twine(Value));
118 }
119
120 void DebugLocDwarfExpression::EmitUnsigned(uint64_t Value) {
121   BS.EmitULEB128(Value, Twine(Value));
122 }
123
124 bool DebugLocDwarfExpression::isFrameRegister(unsigned MachineReg) {
125   // This information is not available while emitting .debug_loc entries.
126   return false;
127 }
128
129 //===----------------------------------------------------------------------===//
130
131 /// resolve - Look in the DwarfDebug map for the MDNode that
132 /// corresponds to the reference.
133 template <typename T> T *DbgVariable::resolve(TypedDebugNodeRef<T> Ref) const {
134   return DD->resolve(Ref);
135 }
136
137 bool DbgVariable::isBlockByrefVariable() const {
138   assert(Var && "Invalid complex DbgVariable!");
139   return Var->getType()
140       .resolve(DD->getTypeIdentifierMap())
141       ->isBlockByrefStruct();
142 }
143
144 const MDType *DbgVariable::getType() const {
145   MDType *Ty = Var->getType().resolve(DD->getTypeIdentifierMap());
146   // FIXME: isBlockByrefVariable should be reformulated in terms of complex
147   // addresses instead.
148   if (Ty->isBlockByrefStruct()) {
149     /* Byref variables, in Blocks, are declared by the programmer as
150        "SomeType VarName;", but the compiler creates a
151        __Block_byref_x_VarName struct, and gives the variable VarName
152        either the struct, or a pointer to the struct, as its type.  This
153        is necessary for various behind-the-scenes things the compiler
154        needs to do with by-reference variables in blocks.
155
156        However, as far as the original *programmer* is concerned, the
157        variable should still have type 'SomeType', as originally declared.
158
159        The following function dives into the __Block_byref_x_VarName
160        struct to find the original type of the variable.  This will be
161        passed back to the code generating the type for the Debug
162        Information Entry for the variable 'VarName'.  'VarName' will then
163        have the original type 'SomeType' in its debug information.
164
165        The original type 'SomeType' will be the type of the field named
166        'VarName' inside the __Block_byref_x_VarName struct.
167
168        NOTE: In order for this to not completely fail on the debugger
169        side, the Debug Information Entry for the variable VarName needs to
170        have a DW_AT_location that tells the debugger how to unwind through
171        the pointers and __Block_byref_x_VarName struct to find the actual
172        value of the variable.  The function addBlockByrefType does this.  */
173     MDType *subType = Ty;
174     uint16_t tag = Ty->getTag();
175
176     if (tag == dwarf::DW_TAG_pointer_type)
177       subType = resolve(cast<MDDerivedType>(Ty)->getBaseType());
178
179     auto Elements = cast<MDCompositeTypeBase>(subType)->getElements();
180     for (unsigned i = 0, N = Elements.size(); i < N; ++i) {
181       auto *DT = cast<MDDerivedTypeBase>(Elements[i]);
182       if (getName() == DT->getName())
183         return resolve(DT->getBaseType());
184     }
185   }
186   return Ty;
187 }
188
189 static LLVM_CONSTEXPR DwarfAccelTable::Atom TypeAtoms[] = {
190     DwarfAccelTable::Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
191     DwarfAccelTable::Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
192     DwarfAccelTable::Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)};
193
194 DwarfDebug::DwarfDebug(AsmPrinter *A, Module *M)
195     : Asm(A), MMI(Asm->MMI), PrevLabel(nullptr),
196       InfoHolder(A, "info_string", DIEValueAllocator),
197       UsedNonDefaultText(false),
198       SkeletonHolder(A, "skel_string", DIEValueAllocator),
199       IsDarwin(Triple(A->getTargetTriple()).isOSDarwin()),
200       IsPS4(Triple(A->getTargetTriple()).isPS4()),
201       AccelNames(DwarfAccelTable::Atom(dwarf::DW_ATOM_die_offset,
202                                        dwarf::DW_FORM_data4)),
203       AccelObjC(DwarfAccelTable::Atom(dwarf::DW_ATOM_die_offset,
204                                       dwarf::DW_FORM_data4)),
205       AccelNamespace(DwarfAccelTable::Atom(dwarf::DW_ATOM_die_offset,
206                                            dwarf::DW_FORM_data4)),
207       AccelTypes(TypeAtoms) {
208
209   CurFn = nullptr;
210   CurMI = nullptr;
211
212   // Turn on accelerator tables for Darwin by default, pubnames by
213   // default for non-Darwin/PS4, and handle split dwarf.
214   if (DwarfAccelTables == Default)
215     HasDwarfAccelTables = IsDarwin;
216   else
217     HasDwarfAccelTables = DwarfAccelTables == Enable;
218
219   if (SplitDwarf == Default)
220     HasSplitDwarf = false;
221   else
222     HasSplitDwarf = SplitDwarf == Enable;
223
224   if (DwarfPubSections == Default)
225     HasDwarfPubSections = !IsDarwin && !IsPS4;
226   else
227     HasDwarfPubSections = DwarfPubSections == Enable;
228
229   unsigned DwarfVersionNumber = Asm->TM.Options.MCOptions.DwarfVersion;
230   DwarfVersion = DwarfVersionNumber ? DwarfVersionNumber
231                                     : MMI->getModule()->getDwarfVersion();
232
233   // Darwin and PS4 use the standard TLS opcode (defined in DWARF 3).
234   // Everybody else uses GNU's.
235   UseGNUTLSOpcode = !(IsDarwin || IsPS4) || DwarfVersion < 3;
236
237   Asm->OutStreamer.getContext().setDwarfVersion(DwarfVersion);
238
239   {
240     NamedRegionTimer T(DbgTimerName, DWARFGroupName, TimePassesIsEnabled);
241     beginModule();
242   }
243 }
244
245 // Define out of line so we don't have to include DwarfUnit.h in DwarfDebug.h.
246 DwarfDebug::~DwarfDebug() { }
247
248 static bool isObjCClass(StringRef Name) {
249   return Name.startswith("+") || Name.startswith("-");
250 }
251
252 static bool hasObjCCategory(StringRef Name) {
253   if (!isObjCClass(Name))
254     return false;
255
256   return Name.find(") ") != StringRef::npos;
257 }
258
259 static void getObjCClassCategory(StringRef In, StringRef &Class,
260                                  StringRef &Category) {
261   if (!hasObjCCategory(In)) {
262     Class = In.slice(In.find('[') + 1, In.find(' '));
263     Category = "";
264     return;
265   }
266
267   Class = In.slice(In.find('[') + 1, In.find('('));
268   Category = In.slice(In.find('[') + 1, In.find(' '));
269   return;
270 }
271
272 static StringRef getObjCMethodName(StringRef In) {
273   return In.slice(In.find(' ') + 1, In.find(']'));
274 }
275
276 // Add the various names to the Dwarf accelerator table names.
277 // TODO: Determine whether or not we should add names for programs
278 // that do not have a DW_AT_name or DW_AT_linkage_name field - this
279 // is only slightly different than the lookup of non-standard ObjC names.
280 void DwarfDebug::addSubprogramNames(const MDSubprogram *SP, DIE &Die) {
281   if (!SP->isDefinition())
282     return;
283   addAccelName(SP->getName(), Die);
284
285   // If the linkage name is different than the name, go ahead and output
286   // that as well into the name table.
287   if (SP->getLinkageName() != "" && SP->getName() != SP->getLinkageName())
288     addAccelName(SP->getLinkageName(), Die);
289
290   // If this is an Objective-C selector name add it to the ObjC accelerator
291   // too.
292   if (isObjCClass(SP->getName())) {
293     StringRef Class, Category;
294     getObjCClassCategory(SP->getName(), Class, Category);
295     addAccelObjC(Class, Die);
296     if (Category != "")
297       addAccelObjC(Category, Die);
298     // Also add the base method name to the name table.
299     addAccelName(getObjCMethodName(SP->getName()), Die);
300   }
301 }
302
303 /// isSubprogramContext - Return true if Context is either a subprogram
304 /// or another context nested inside a subprogram.
305 bool DwarfDebug::isSubprogramContext(const MDNode *Context) {
306   if (!Context)
307     return false;
308   if (isa<MDSubprogram>(Context))
309     return true;
310   if (auto *T = dyn_cast<MDType>(Context))
311     return isSubprogramContext(resolve(T->getScope()));
312   return false;
313 }
314
315 /// Check whether we should create a DIE for the given Scope, return true
316 /// if we don't create a DIE (the corresponding DIE is null).
317 bool DwarfDebug::isLexicalScopeDIENull(LexicalScope *Scope) {
318   if (Scope->isAbstractScope())
319     return false;
320
321   // We don't create a DIE if there is no Range.
322   const SmallVectorImpl<InsnRange> &Ranges = Scope->getRanges();
323   if (Ranges.empty())
324     return true;
325
326   if (Ranges.size() > 1)
327     return false;
328
329   // We don't create a DIE if we have a single Range and the end label
330   // is null.
331   return !getLabelAfterInsn(Ranges.front().second);
332 }
333
334 template <typename Func> void forBothCUs(DwarfCompileUnit &CU, Func F) {
335   F(CU);
336   if (auto *SkelCU = CU.getSkeleton())
337     F(*SkelCU);
338 }
339
340 void DwarfDebug::constructAbstractSubprogramScopeDIE(LexicalScope *Scope) {
341   assert(Scope && Scope->getScopeNode());
342   assert(Scope->isAbstractScope());
343   assert(!Scope->getInlinedAt());
344
345   const MDNode *SP = Scope->getScopeNode();
346
347   ProcessedSPNodes.insert(SP);
348
349   // Find the subprogram's DwarfCompileUnit in the SPMap in case the subprogram
350   // was inlined from another compile unit.
351   auto &CU = SPMap[SP];
352   forBothCUs(*CU, [&](DwarfCompileUnit &CU) {
353     CU.constructAbstractSubprogramScopeDIE(Scope);
354   });
355 }
356
357 void DwarfDebug::addGnuPubAttributes(DwarfUnit &U, DIE &D) const {
358   if (!GenerateGnuPubSections)
359     return;
360
361   U.addFlag(D, dwarf::DW_AT_GNU_pubnames);
362 }
363
364 // Create new DwarfCompileUnit for the given metadata node with tag
365 // DW_TAG_compile_unit.
366 DwarfCompileUnit &
367 DwarfDebug::constructDwarfCompileUnit(const MDCompileUnit *DIUnit) {
368   StringRef FN = DIUnit->getFilename();
369   CompilationDir = DIUnit->getDirectory();
370
371   auto OwnedUnit = make_unique<DwarfCompileUnit>(
372       InfoHolder.getUnits().size(), DIUnit, Asm, this, &InfoHolder);
373   DwarfCompileUnit &NewCU = *OwnedUnit;
374   DIE &Die = NewCU.getUnitDie();
375   InfoHolder.addUnit(std::move(OwnedUnit));
376   if (useSplitDwarf())
377     NewCU.setSkeleton(constructSkeletonCU(NewCU));
378
379   // LTO with assembly output shares a single line table amongst multiple CUs.
380   // To avoid the compilation directory being ambiguous, let the line table
381   // explicitly describe the directory of all files, never relying on the
382   // compilation directory.
383   if (!Asm->OutStreamer.hasRawTextSupport() || SingleCU)
384     Asm->OutStreamer.getContext().setMCLineTableCompilationDir(
385         NewCU.getUniqueID(), CompilationDir);
386
387   NewCU.addString(Die, dwarf::DW_AT_producer, DIUnit->getProducer());
388   NewCU.addUInt(Die, dwarf::DW_AT_language, dwarf::DW_FORM_data2,
389                 DIUnit->getSourceLanguage());
390   NewCU.addString(Die, dwarf::DW_AT_name, FN);
391
392   if (!useSplitDwarf()) {
393     NewCU.initStmtList();
394
395     // If we're using split dwarf the compilation dir is going to be in the
396     // skeleton CU and so we don't need to duplicate it here.
397     if (!CompilationDir.empty())
398       NewCU.addString(Die, dwarf::DW_AT_comp_dir, CompilationDir);
399
400     addGnuPubAttributes(NewCU, Die);
401   }
402
403   if (DIUnit->isOptimized())
404     NewCU.addFlag(Die, dwarf::DW_AT_APPLE_optimized);
405
406   StringRef Flags = DIUnit->getFlags();
407   if (!Flags.empty())
408     NewCU.addString(Die, dwarf::DW_AT_APPLE_flags, Flags);
409
410   if (unsigned RVer = DIUnit->getRuntimeVersion())
411     NewCU.addUInt(Die, dwarf::DW_AT_APPLE_major_runtime_vers,
412                   dwarf::DW_FORM_data1, RVer);
413
414   if (useSplitDwarf())
415     NewCU.initSection(Asm->getObjFileLowering().getDwarfInfoDWOSection());
416   else
417     NewCU.initSection(Asm->getObjFileLowering().getDwarfInfoSection());
418
419   CUMap.insert(std::make_pair(DIUnit, &NewCU));
420   CUDieMap.insert(std::make_pair(&Die, &NewCU));
421   return NewCU;
422 }
423
424 void DwarfDebug::constructAndAddImportedEntityDIE(DwarfCompileUnit &TheCU,
425                                                   const MDImportedEntity *N) {
426   if (DIE *D = TheCU.getOrCreateContextDIE(N->getScope()))
427     D->addChild(TheCU.constructImportedEntityDIE(N));
428 }
429
430 // Emit all Dwarf sections that should come prior to the content. Create
431 // global DIEs and emit initial debug info sections. This is invoked by
432 // the target AsmPrinter.
433 void DwarfDebug::beginModule() {
434   if (DisableDebugInfoPrinting)
435     return;
436
437   const Module *M = MMI->getModule();
438
439   FunctionDIs = makeSubprogramMap(*M);
440
441   NamedMDNode *CU_Nodes = M->getNamedMetadata("llvm.dbg.cu");
442   if (!CU_Nodes)
443     return;
444   TypeIdentifierMap = generateDITypeIdentifierMap(CU_Nodes);
445
446   SingleCU = CU_Nodes->getNumOperands() == 1;
447
448   for (MDNode *N : CU_Nodes->operands()) {
449     auto *CUNode = cast<MDCompileUnit>(N);
450     DwarfCompileUnit &CU = constructDwarfCompileUnit(CUNode);
451     for (auto *IE : CUNode->getImportedEntities())
452       ScopesWithImportedEntities.push_back(std::make_pair(IE->getScope(), IE));
453     // Stable sort to preserve the order of appearance of imported entities.
454     // This is to avoid out-of-order processing of interdependent declarations
455     // within the same scope, e.g. { namespace A = base; namespace B = A; }
456     std::stable_sort(ScopesWithImportedEntities.begin(),
457                      ScopesWithImportedEntities.end(), less_first());
458     for (auto *GV : CUNode->getGlobalVariables())
459       CU.getOrCreateGlobalVariableDIE(GV);
460     for (auto *SP : CUNode->getSubprograms())
461       SPMap.insert(std::make_pair(SP, &CU));
462     for (auto *Ty : CUNode->getEnumTypes()) {
463       // The enum types array by design contains pointers to
464       // MDNodes rather than DIRefs. Unique them here.
465       CU.getOrCreateTypeDIE(cast<MDType>(resolve(Ty->getRef())));
466     }
467     for (auto *Ty : CUNode->getRetainedTypes()) {
468       // The retained types array by design contains pointers to
469       // MDNodes rather than DIRefs. Unique them here.
470       CU.getOrCreateTypeDIE(cast<MDType>(resolve(Ty->getRef())));
471     }
472     // Emit imported_modules last so that the relevant context is already
473     // available.
474     for (auto *IE : CUNode->getImportedEntities())
475       constructAndAddImportedEntityDIE(CU, IE);
476   }
477
478   // Tell MMI that we have debug info.
479   MMI->setDebugInfoAvailability(true);
480 }
481
482 void DwarfDebug::finishVariableDefinitions() {
483   for (const auto &Var : ConcreteVariables) {
484     DIE *VariableDie = Var->getDIE();
485     assert(VariableDie);
486     // FIXME: Consider the time-space tradeoff of just storing the unit pointer
487     // in the ConcreteVariables list, rather than looking it up again here.
488     // DIE::getUnit isn't simple - it walks parent pointers, etc.
489     DwarfCompileUnit *Unit = lookupUnit(VariableDie->getUnit());
490     assert(Unit);
491     DbgVariable *AbsVar = getExistingAbstractVariable(
492         InlinedVariable(Var->getVariable(), Var->getInlinedAt()));
493     if (AbsVar && AbsVar->getDIE()) {
494       Unit->addDIEEntry(*VariableDie, dwarf::DW_AT_abstract_origin,
495                         *AbsVar->getDIE());
496     } else
497       Unit->applyVariableAttributes(*Var, *VariableDie);
498   }
499 }
500
501 void DwarfDebug::finishSubprogramDefinitions() {
502   for (const auto &P : SPMap)
503     forBothCUs(*P.second, [&](DwarfCompileUnit &CU) {
504       CU.finishSubprogramDefinition(cast<MDSubprogram>(P.first));
505     });
506 }
507
508
509 // Collect info for variables that were optimized out.
510 void DwarfDebug::collectDeadVariables() {
511   const Module *M = MMI->getModule();
512
513   if (NamedMDNode *CU_Nodes = M->getNamedMetadata("llvm.dbg.cu")) {
514     for (MDNode *N : CU_Nodes->operands()) {
515       auto *TheCU = cast<MDCompileUnit>(N);
516       // Construct subprogram DIE and add variables DIEs.
517       DwarfCompileUnit *SPCU =
518           static_cast<DwarfCompileUnit *>(CUMap.lookup(TheCU));
519       assert(SPCU && "Unable to find Compile Unit!");
520       for (auto *SP : TheCU->getSubprograms()) {
521         if (ProcessedSPNodes.count(SP) != 0)
522           continue;
523         SPCU->collectDeadVariables(SP);
524       }
525     }
526   }
527 }
528
529 void DwarfDebug::finalizeModuleInfo() {
530   const TargetLoweringObjectFile &TLOF = Asm->getObjFileLowering();
531
532   finishSubprogramDefinitions();
533
534   finishVariableDefinitions();
535
536   // Collect info for variables that were optimized out.
537   collectDeadVariables();
538
539   // Handle anything that needs to be done on a per-unit basis after
540   // all other generation.
541   for (const auto &P : CUMap) {
542     auto &TheCU = *P.second;
543     // Emit DW_AT_containing_type attribute to connect types with their
544     // vtable holding type.
545     TheCU.constructContainingTypeDIEs();
546
547     // Add CU specific attributes if we need to add any.
548     // If we're splitting the dwarf out now that we've got the entire
549     // CU then add the dwo id to it.
550     auto *SkCU = TheCU.getSkeleton();
551     if (useSplitDwarf()) {
552       // Emit a unique identifier for this CU.
553       uint64_t ID = DIEHash(Asm).computeCUSignature(TheCU.getUnitDie());
554       TheCU.addUInt(TheCU.getUnitDie(), dwarf::DW_AT_GNU_dwo_id,
555                     dwarf::DW_FORM_data8, ID);
556       SkCU->addUInt(SkCU->getUnitDie(), dwarf::DW_AT_GNU_dwo_id,
557                     dwarf::DW_FORM_data8, ID);
558
559       // We don't keep track of which addresses are used in which CU so this
560       // is a bit pessimistic under LTO.
561       if (!AddrPool.isEmpty()) {
562         const MCSymbol *Sym = TLOF.getDwarfAddrSection()->getBeginSymbol();
563         SkCU->addSectionLabel(SkCU->getUnitDie(), dwarf::DW_AT_GNU_addr_base,
564                               Sym, Sym);
565       }
566       if (!SkCU->getRangeLists().empty()) {
567         const MCSymbol *Sym = TLOF.getDwarfRangesSection()->getBeginSymbol();
568         SkCU->addSectionLabel(SkCU->getUnitDie(), dwarf::DW_AT_GNU_ranges_base,
569                               Sym, Sym);
570       }
571     }
572
573     // If we have code split among multiple sections or non-contiguous
574     // ranges of code then emit a DW_AT_ranges attribute on the unit that will
575     // remain in the .o file, otherwise add a DW_AT_low_pc.
576     // FIXME: We should use ranges allow reordering of code ala
577     // .subsections_via_symbols in mach-o. This would mean turning on
578     // ranges for all subprogram DIEs for mach-o.
579     DwarfCompileUnit &U = SkCU ? *SkCU : TheCU;
580     if (unsigned NumRanges = TheCU.getRanges().size()) {
581       if (NumRanges > 1)
582         // A DW_AT_low_pc attribute may also be specified in combination with
583         // DW_AT_ranges to specify the default base address for use in
584         // location lists (see Section 2.6.2) and range lists (see Section
585         // 2.17.3).
586         U.addUInt(U.getUnitDie(), dwarf::DW_AT_low_pc, dwarf::DW_FORM_addr, 0);
587       else
588         TheCU.setBaseAddress(TheCU.getRanges().front().getStart());
589       U.attachRangesOrLowHighPC(U.getUnitDie(), TheCU.takeRanges());
590     }
591   }
592
593   // Compute DIE offsets and sizes.
594   InfoHolder.computeSizeAndOffsets();
595   if (useSplitDwarf())
596     SkeletonHolder.computeSizeAndOffsets();
597 }
598
599 // Emit all Dwarf sections that should come after the content.
600 void DwarfDebug::endModule() {
601   assert(CurFn == nullptr);
602   assert(CurMI == nullptr);
603
604   // If we aren't actually generating debug info (check beginModule -
605   // conditionalized on !DisableDebugInfoPrinting and the presence of the
606   // llvm.dbg.cu metadata node)
607   if (!MMI->hasDebugInfo())
608     return;
609
610   // Finalize the debug info for the module.
611   finalizeModuleInfo();
612
613   emitDebugStr();
614
615   if (useSplitDwarf())
616     emitDebugLocDWO();
617   else
618     // Emit info into a debug loc section.
619     emitDebugLoc();
620
621   // Corresponding abbreviations into a abbrev section.
622   emitAbbreviations();
623
624   // Emit all the DIEs into a debug info section.
625   emitDebugInfo();
626
627   // Emit info into a debug aranges section.
628   if (GenerateARangeSection)
629     emitDebugARanges();
630
631   // Emit info into a debug ranges section.
632   emitDebugRanges();
633
634   if (useSplitDwarf()) {
635     emitDebugStrDWO();
636     emitDebugInfoDWO();
637     emitDebugAbbrevDWO();
638     emitDebugLineDWO();
639     // Emit DWO addresses.
640     AddrPool.emit(*Asm, Asm->getObjFileLowering().getDwarfAddrSection());
641   }
642
643   // Emit info into the dwarf accelerator table sections.
644   if (useDwarfAccelTables()) {
645     emitAccelNames();
646     emitAccelObjC();
647     emitAccelNamespaces();
648     emitAccelTypes();
649   }
650
651   // Emit the pubnames and pubtypes sections if requested.
652   if (HasDwarfPubSections) {
653     emitDebugPubNames(GenerateGnuPubSections);
654     emitDebugPubTypes(GenerateGnuPubSections);
655   }
656
657   // clean up.
658   SPMap.clear();
659   AbstractVariables.clear();
660 }
661
662 // Find abstract variable, if any, associated with Var.
663 DbgVariable *
664 DwarfDebug::getExistingAbstractVariable(InlinedVariable IV,
665                                         const MDLocalVariable *&Cleansed) {
666   // More then one inlined variable corresponds to one abstract variable.
667   Cleansed = IV.first;
668   auto I = AbstractVariables.find(Cleansed);
669   if (I != AbstractVariables.end())
670     return I->second.get();
671   return nullptr;
672 }
673
674 DbgVariable *DwarfDebug::getExistingAbstractVariable(InlinedVariable IV) {
675   const MDLocalVariable *Cleansed;
676   return getExistingAbstractVariable(IV, Cleansed);
677 }
678
679 void DwarfDebug::createAbstractVariable(const MDLocalVariable *Var,
680                                         LexicalScope *Scope) {
681   auto AbsDbgVariable =
682       make_unique<DbgVariable>(Var, /* IA */ nullptr, /* Expr */ nullptr, this);
683   InfoHolder.addScopeVariable(Scope, AbsDbgVariable.get());
684   AbstractVariables[Var] = std::move(AbsDbgVariable);
685 }
686
687 void DwarfDebug::ensureAbstractVariableIsCreated(InlinedVariable IV,
688                                                  const MDNode *ScopeNode) {
689   const MDLocalVariable *Cleansed = nullptr;
690   if (getExistingAbstractVariable(IV, Cleansed))
691     return;
692
693   createAbstractVariable(Cleansed, LScopes.getOrCreateAbstractScope(
694                                        cast<MDLocalScope>(ScopeNode)));
695 }
696
697 void DwarfDebug::ensureAbstractVariableIsCreatedIfScoped(
698     InlinedVariable IV, const MDNode *ScopeNode) {
699   const MDLocalVariable *Cleansed = nullptr;
700   if (getExistingAbstractVariable(IV, Cleansed))
701     return;
702
703   if (LexicalScope *Scope =
704           LScopes.findAbstractScope(cast_or_null<MDLocalScope>(ScopeNode)))
705     createAbstractVariable(Cleansed, Scope);
706 }
707
708 // Collect variable information from side table maintained by MMI.
709 void DwarfDebug::collectVariableInfoFromMMITable(
710     DenseSet<InlinedVariable> &Processed) {
711   for (const auto &VI : MMI->getVariableDbgInfo()) {
712     if (!VI.Var)
713       continue;
714     assert(VI.Var->isValidLocationForIntrinsic(VI.Loc) &&
715            "Expected inlined-at fields to agree");
716
717     InlinedVariable Var(VI.Var, VI.Loc->getInlinedAt());
718     Processed.insert(Var);
719     LexicalScope *Scope = LScopes.findLexicalScope(VI.Loc);
720
721     // If variable scope is not found then skip this variable.
722     if (!Scope)
723       continue;
724
725     const MDExpression *Expr = cast_or_null<MDExpression>(VI.Expr);
726     ensureAbstractVariableIsCreatedIfScoped(Var, Scope->getScopeNode());
727     auto RegVar =
728         make_unique<DbgVariable>(Var.first, Var.second, Expr, this, VI.Slot);
729     if (InfoHolder.addScopeVariable(Scope, RegVar.get()))
730       ConcreteVariables.push_back(std::move(RegVar));
731   }
732 }
733
734 // Get .debug_loc entry for the instruction range starting at MI.
735 static DebugLocEntry::Value getDebugLocValue(const MachineInstr *MI) {
736   const MDExpression *Expr = MI->getDebugExpression();
737
738   assert(MI->getNumOperands() == 4);
739   if (MI->getOperand(0).isReg()) {
740     MachineLocation MLoc;
741     // If the second operand is an immediate, this is a
742     // register-indirect address.
743     if (!MI->getOperand(1).isImm())
744       MLoc.set(MI->getOperand(0).getReg());
745     else
746       MLoc.set(MI->getOperand(0).getReg(), MI->getOperand(1).getImm());
747     return DebugLocEntry::Value(Expr, MLoc);
748   }
749   if (MI->getOperand(0).isImm())
750     return DebugLocEntry::Value(Expr, MI->getOperand(0).getImm());
751   if (MI->getOperand(0).isFPImm())
752     return DebugLocEntry::Value(Expr, MI->getOperand(0).getFPImm());
753   if (MI->getOperand(0).isCImm())
754     return DebugLocEntry::Value(Expr, MI->getOperand(0).getCImm());
755
756   llvm_unreachable("Unexpected 4-operand DBG_VALUE instruction!");
757 }
758
759 /// Determine whether two variable pieces overlap.
760 static bool piecesOverlap(const MDExpression *P1, const MDExpression *P2) {
761   if (!P1->isBitPiece() || !P2->isBitPiece())
762     return true;
763   unsigned l1 = P1->getBitPieceOffset();
764   unsigned l2 = P2->getBitPieceOffset();
765   unsigned r1 = l1 + P1->getBitPieceSize();
766   unsigned r2 = l2 + P2->getBitPieceSize();
767   // True where [l1,r1[ and [r1,r2[ overlap.
768   return (l1 < r2) && (l2 < r1);
769 }
770
771 /// Build the location list for all DBG_VALUEs in the function that
772 /// describe the same variable.  If the ranges of several independent
773 /// pieces of the same variable overlap partially, split them up and
774 /// combine the ranges. The resulting DebugLocEntries are will have
775 /// strict monotonically increasing begin addresses and will never
776 /// overlap.
777 //
778 // Input:
779 //
780 //   Ranges History [var, loc, piece ofs size]
781 // 0 |      [x, (reg0, piece 0, 32)]
782 // 1 | |    [x, (reg1, piece 32, 32)] <- IsPieceOfPrevEntry
783 // 2 | |    ...
784 // 3   |    [clobber reg0]
785 // 4        [x, (mem, piece 0, 64)] <- overlapping with both previous pieces of
786 //                                     x.
787 //
788 // Output:
789 //
790 // [0-1]    [x, (reg0, piece  0, 32)]
791 // [1-3]    [x, (reg0, piece  0, 32), (reg1, piece 32, 32)]
792 // [3-4]    [x, (reg1, piece 32, 32)]
793 // [4- ]    [x, (mem,  piece  0, 64)]
794 void
795 DwarfDebug::buildLocationList(SmallVectorImpl<DebugLocEntry> &DebugLoc,
796                               const DbgValueHistoryMap::InstrRanges &Ranges) {
797   SmallVector<DebugLocEntry::Value, 4> OpenRanges;
798
799   for (auto I = Ranges.begin(), E = Ranges.end(); I != E; ++I) {
800     const MachineInstr *Begin = I->first;
801     const MachineInstr *End = I->second;
802     assert(Begin->isDebugValue() && "Invalid History entry");
803
804     // Check if a variable is inaccessible in this range.
805     if (Begin->getNumOperands() > 1 &&
806         Begin->getOperand(0).isReg() && !Begin->getOperand(0).getReg()) {
807       OpenRanges.clear();
808       continue;
809     }
810
811     // If this piece overlaps with any open ranges, truncate them.
812     const MDExpression *DIExpr = Begin->getDebugExpression();
813     auto Last = std::remove_if(OpenRanges.begin(), OpenRanges.end(),
814                                [&](DebugLocEntry::Value R) {
815       return piecesOverlap(DIExpr, R.getExpression());
816     });
817     OpenRanges.erase(Last, OpenRanges.end());
818
819     const MCSymbol *StartLabel = getLabelBeforeInsn(Begin);
820     assert(StartLabel && "Forgot label before DBG_VALUE starting a range!");
821
822     const MCSymbol *EndLabel;
823     if (End != nullptr)
824       EndLabel = getLabelAfterInsn(End);
825     else if (std::next(I) == Ranges.end())
826       EndLabel = Asm->getFunctionEnd();
827     else
828       EndLabel = getLabelBeforeInsn(std::next(I)->first);
829     assert(EndLabel && "Forgot label after instruction ending a range!");
830
831     DEBUG(dbgs() << "DotDebugLoc: " << *Begin << "\n");
832
833     auto Value = getDebugLocValue(Begin);
834     DebugLocEntry Loc(StartLabel, EndLabel, Value);
835     bool couldMerge = false;
836
837     // If this is a piece, it may belong to the current DebugLocEntry.
838     if (DIExpr->isBitPiece()) {
839       // Add this value to the list of open ranges.
840       OpenRanges.push_back(Value);
841
842       // Attempt to add the piece to the last entry.
843       if (!DebugLoc.empty())
844         if (DebugLoc.back().MergeValues(Loc))
845           couldMerge = true;
846     }
847
848     if (!couldMerge) {
849       // Need to add a new DebugLocEntry. Add all values from still
850       // valid non-overlapping pieces.
851       if (OpenRanges.size())
852         Loc.addValues(OpenRanges);
853
854       DebugLoc.push_back(std::move(Loc));
855     }
856
857     // Attempt to coalesce the ranges of two otherwise identical
858     // DebugLocEntries.
859     auto CurEntry = DebugLoc.rbegin();
860     auto PrevEntry = std::next(CurEntry);
861     if (PrevEntry != DebugLoc.rend() && PrevEntry->MergeRanges(*CurEntry))
862       DebugLoc.pop_back();
863
864     DEBUG({
865       dbgs() << CurEntry->getValues().size() << " Values:\n";
866       for (auto Value : CurEntry->getValues()) {
867         Value.getExpression()->dump();
868       }
869       dbgs() << "-----\n";
870     });
871   }
872 }
873
874
875 // Find variables for each lexical scope.
876 void DwarfDebug::collectVariableInfo(DwarfCompileUnit &TheCU,
877                                      const MDSubprogram *SP,
878                                      DenseSet<InlinedVariable> &Processed) {
879   // Grab the variable info that was squirreled away in the MMI side-table.
880   collectVariableInfoFromMMITable(Processed);
881
882   for (const auto &I : DbgValues) {
883     InlinedVariable IV = I.first;
884     if (Processed.count(IV))
885       continue;
886
887     // Instruction ranges, specifying where IV is accessible.
888     const auto &Ranges = I.second;
889     if (Ranges.empty())
890       continue;
891
892     LexicalScope *Scope = nullptr;
893     if (const MDLocation *IA = IV.second)
894       Scope = LScopes.findInlinedScope(IV.first->getScope(), IA);
895     else
896       Scope = LScopes.findLexicalScope(IV.first->getScope());
897     // If variable scope is not found then skip this variable.
898     if (!Scope)
899       continue;
900
901     Processed.insert(IV);
902     const MachineInstr *MInsn = Ranges.front().first;
903     assert(MInsn->isDebugValue() && "History must begin with debug value");
904     ensureAbstractVariableIsCreatedIfScoped(IV, Scope->getScopeNode());
905     ConcreteVariables.push_back(make_unique<DbgVariable>(MInsn, this));
906     DbgVariable *RegVar = ConcreteVariables.back().get();
907     InfoHolder.addScopeVariable(Scope, RegVar);
908
909     // Check if the first DBG_VALUE is valid for the rest of the function.
910     if (Ranges.size() == 1 && Ranges.front().second == nullptr)
911       continue;
912
913     // Handle multiple DBG_VALUE instructions describing one variable.
914     RegVar->setDebugLocListIndex(
915         DebugLocs.startList(&TheCU, Asm->createTempSymbol("debug_loc")));
916
917     // Build the location list for this variable.
918     SmallVector<DebugLocEntry, 8> Entries;
919     buildLocationList(Entries, Ranges);
920
921     // If the variable has an MDBasicType, extract it.  Basic types cannot have
922     // unique identifiers, so don't bother resolving the type with the
923     // identifier map.
924     const MDBasicType *BT = dyn_cast<MDBasicType>(
925         static_cast<const Metadata *>(IV.first->getType()));
926
927     // Finalize the entry by lowering it into a DWARF bytestream.
928     for (auto &Entry : Entries)
929       Entry.finalize(*Asm, DebugLocs, BT);
930   }
931
932   // Collect info for variables that were optimized out.
933   for (const MDLocalVariable *DV : SP->getVariables()) {
934     if (!Processed.insert(InlinedVariable(DV, nullptr)).second)
935       continue;
936     if (LexicalScope *Scope = LScopes.findLexicalScope(DV->getScope())) {
937       ensureAbstractVariableIsCreatedIfScoped(InlinedVariable(DV, nullptr),
938                                               Scope->getScopeNode());
939       ConcreteVariables.push_back(make_unique<DbgVariable>(
940           DV, /* IA */ nullptr, /* Expr */ nullptr, this));
941       InfoHolder.addScopeVariable(Scope, ConcreteVariables.back().get());
942     }
943   }
944 }
945
946 // Return Label preceding the instruction.
947 MCSymbol *DwarfDebug::getLabelBeforeInsn(const MachineInstr *MI) {
948   MCSymbol *Label = LabelsBeforeInsn.lookup(MI);
949   assert(Label && "Didn't insert label before instruction");
950   return Label;
951 }
952
953 // Return Label immediately following the instruction.
954 MCSymbol *DwarfDebug::getLabelAfterInsn(const MachineInstr *MI) {
955   return LabelsAfterInsn.lookup(MI);
956 }
957
958 // Process beginning of an instruction.
959 void DwarfDebug::beginInstruction(const MachineInstr *MI) {
960   assert(CurMI == nullptr);
961   CurMI = MI;
962   // Check if source location changes, but ignore DBG_VALUE locations.
963   if (!MI->isDebugValue()) {
964     DebugLoc DL = MI->getDebugLoc();
965     if (DL != PrevInstLoc) {
966       if (DL) {
967         unsigned Flags = 0;
968         PrevInstLoc = DL;
969         if (DL == PrologEndLoc) {
970           Flags |= DWARF2_FLAG_PROLOGUE_END;
971           PrologEndLoc = DebugLoc();
972           Flags |= DWARF2_FLAG_IS_STMT;
973         }
974         if (DL.getLine() !=
975             Asm->OutStreamer.getContext().getCurrentDwarfLoc().getLine())
976           Flags |= DWARF2_FLAG_IS_STMT;
977
978         const MDNode *Scope = DL.getScope();
979         recordSourceLine(DL.getLine(), DL.getCol(), Scope, Flags);
980       } else if (UnknownLocations) {
981         PrevInstLoc = DL;
982         recordSourceLine(0, 0, nullptr, 0);
983       }
984     }
985   }
986
987   // Insert labels where requested.
988   DenseMap<const MachineInstr *, MCSymbol *>::iterator I =
989       LabelsBeforeInsn.find(MI);
990
991   // No label needed.
992   if (I == LabelsBeforeInsn.end())
993     return;
994
995   // Label already assigned.
996   if (I->second)
997     return;
998
999   if (!PrevLabel) {
1000     PrevLabel = MMI->getContext().CreateTempSymbol();
1001     Asm->OutStreamer.EmitLabel(PrevLabel);
1002   }
1003   I->second = PrevLabel;
1004 }
1005
1006 // Process end of an instruction.
1007 void DwarfDebug::endInstruction() {
1008   assert(CurMI != nullptr);
1009   // Don't create a new label after DBG_VALUE instructions.
1010   // They don't generate code.
1011   if (!CurMI->isDebugValue())
1012     PrevLabel = nullptr;
1013
1014   DenseMap<const MachineInstr *, MCSymbol *>::iterator I =
1015       LabelsAfterInsn.find(CurMI);
1016   CurMI = nullptr;
1017
1018   // No label needed.
1019   if (I == LabelsAfterInsn.end())
1020     return;
1021
1022   // Label already assigned.
1023   if (I->second)
1024     return;
1025
1026   // We need a label after this instruction.
1027   if (!PrevLabel) {
1028     PrevLabel = MMI->getContext().CreateTempSymbol();
1029     Asm->OutStreamer.EmitLabel(PrevLabel);
1030   }
1031   I->second = PrevLabel;
1032 }
1033
1034 // Each LexicalScope has first instruction and last instruction to mark
1035 // beginning and end of a scope respectively. Create an inverse map that list
1036 // scopes starts (and ends) with an instruction. One instruction may start (or
1037 // end) multiple scopes. Ignore scopes that are not reachable.
1038 void DwarfDebug::identifyScopeMarkers() {
1039   SmallVector<LexicalScope *, 4> WorkList;
1040   WorkList.push_back(LScopes.getCurrentFunctionScope());
1041   while (!WorkList.empty()) {
1042     LexicalScope *S = WorkList.pop_back_val();
1043
1044     const SmallVectorImpl<LexicalScope *> &Children = S->getChildren();
1045     if (!Children.empty())
1046       WorkList.append(Children.begin(), Children.end());
1047
1048     if (S->isAbstractScope())
1049       continue;
1050
1051     for (const InsnRange &R : S->getRanges()) {
1052       assert(R.first && "InsnRange does not have first instruction!");
1053       assert(R.second && "InsnRange does not have second instruction!");
1054       requestLabelBeforeInsn(R.first);
1055       requestLabelAfterInsn(R.second);
1056     }
1057   }
1058 }
1059
1060 static DebugLoc findPrologueEndLoc(const MachineFunction *MF) {
1061   // First known non-DBG_VALUE and non-frame setup location marks
1062   // the beginning of the function body.
1063   for (const auto &MBB : *MF)
1064     for (const auto &MI : MBB)
1065       if (!MI.isDebugValue() && !MI.getFlag(MachineInstr::FrameSetup) &&
1066           MI.getDebugLoc()) {
1067         // Did the target forget to set the FrameSetup flag for CFI insns?
1068         assert(!MI.isCFIInstruction() &&
1069                "First non-frame-setup instruction is a CFI instruction.");
1070         return MI.getDebugLoc();
1071       }
1072   return DebugLoc();
1073 }
1074
1075 // Gather pre-function debug information.  Assumes being called immediately
1076 // after the function entry point has been emitted.
1077 void DwarfDebug::beginFunction(const MachineFunction *MF) {
1078   CurFn = MF;
1079
1080   // If there's no debug info for the function we're not going to do anything.
1081   if (!MMI->hasDebugInfo())
1082     return;
1083
1084   auto DI = FunctionDIs.find(MF->getFunction());
1085   if (DI == FunctionDIs.end())
1086     return;
1087
1088   // Grab the lexical scopes for the function, if we don't have any of those
1089   // then we're not going to be able to do anything.
1090   LScopes.initialize(*MF);
1091   if (LScopes.empty())
1092     return;
1093
1094   assert(DbgValues.empty() && "DbgValues map wasn't cleaned!");
1095
1096   // Make sure that each lexical scope will have a begin/end label.
1097   identifyScopeMarkers();
1098
1099   // Set DwarfDwarfCompileUnitID in MCContext to the Compile Unit this function
1100   // belongs to so that we add to the correct per-cu line table in the
1101   // non-asm case.
1102   LexicalScope *FnScope = LScopes.getCurrentFunctionScope();
1103   // FnScope->getScopeNode() and DI->second should represent the same function,
1104   // though they may not be the same MDNode due to inline functions merged in
1105   // LTO where the debug info metadata still differs (either due to distinct
1106   // written differences - two versions of a linkonce_odr function
1107   // written/copied into two separate files, or some sub-optimal metadata that
1108   // isn't structurally identical (see: file path/name info from clang, which
1109   // includes the directory of the cpp file being built, even when the file name
1110   // is absolute (such as an <> lookup header)))
1111   DwarfCompileUnit *TheCU = SPMap.lookup(FnScope->getScopeNode());
1112   assert(TheCU && "Unable to find compile unit!");
1113   if (Asm->OutStreamer.hasRawTextSupport())
1114     // Use a single line table if we are generating assembly.
1115     Asm->OutStreamer.getContext().setDwarfCompileUnitID(0);
1116   else
1117     Asm->OutStreamer.getContext().setDwarfCompileUnitID(TheCU->getUniqueID());
1118
1119   // Calculate history for local variables.
1120   calculateDbgValueHistory(MF, Asm->MF->getSubtarget().getRegisterInfo(),
1121                            DbgValues);
1122
1123   // Request labels for the full history.
1124   for (const auto &I : DbgValues) {
1125     const auto &Ranges = I.second;
1126     if (Ranges.empty())
1127       continue;
1128
1129     // The first mention of a function argument gets the CurrentFnBegin
1130     // label, so arguments are visible when breaking at function entry.
1131     const MDLocalVariable *DIVar = Ranges.front().first->getDebugVariable();
1132     if (DIVar->getTag() == dwarf::DW_TAG_arg_variable &&
1133         getDISubprogram(DIVar->getScope())->describes(MF->getFunction())) {
1134       LabelsBeforeInsn[Ranges.front().first] = Asm->getFunctionBegin();
1135       if (Ranges.front().first->getDebugExpression()->isBitPiece()) {
1136         // Mark all non-overlapping initial pieces.
1137         for (auto I = Ranges.begin(); I != Ranges.end(); ++I) {
1138           const MDExpression *Piece = I->first->getDebugExpression();
1139           if (std::all_of(Ranges.begin(), I,
1140                           [&](DbgValueHistoryMap::InstrRange Pred) {
1141                 return !piecesOverlap(Piece, Pred.first->getDebugExpression());
1142               }))
1143             LabelsBeforeInsn[I->first] = Asm->getFunctionBegin();
1144           else
1145             break;
1146         }
1147       }
1148     }
1149
1150     for (const auto &Range : Ranges) {
1151       requestLabelBeforeInsn(Range.first);
1152       if (Range.second)
1153         requestLabelAfterInsn(Range.second);
1154     }
1155   }
1156
1157   PrevInstLoc = DebugLoc();
1158   PrevLabel = Asm->getFunctionBegin();
1159
1160   // Record beginning of function.
1161   PrologEndLoc = findPrologueEndLoc(MF);
1162   if (MDLocation *L = PrologEndLoc) {
1163     // We'd like to list the prologue as "not statements" but GDB behaves
1164     // poorly if we do that. Revisit this with caution/GDB (7.5+) testing.
1165     auto *SP = L->getInlinedAtScope()->getSubprogram();
1166     recordSourceLine(SP->getScopeLine(), 0, SP, DWARF2_FLAG_IS_STMT);
1167   }
1168 }
1169
1170 // Gather and emit post-function debug information.
1171 void DwarfDebug::endFunction(const MachineFunction *MF) {
1172   assert(CurFn == MF &&
1173       "endFunction should be called with the same function as beginFunction");
1174
1175   if (!MMI->hasDebugInfo() || LScopes.empty() ||
1176       !FunctionDIs.count(MF->getFunction())) {
1177     // If we don't have a lexical scope for this function then there will
1178     // be a hole in the range information. Keep note of this by setting the
1179     // previously used section to nullptr.
1180     PrevCU = nullptr;
1181     CurFn = nullptr;
1182     return;
1183   }
1184
1185   // Set DwarfDwarfCompileUnitID in MCContext to default value.
1186   Asm->OutStreamer.getContext().setDwarfCompileUnitID(0);
1187
1188   LexicalScope *FnScope = LScopes.getCurrentFunctionScope();
1189   auto *SP = cast<MDSubprogram>(FnScope->getScopeNode());
1190   DwarfCompileUnit &TheCU = *SPMap.lookup(SP);
1191
1192   DenseSet<InlinedVariable> ProcessedVars;
1193   collectVariableInfo(TheCU, SP, ProcessedVars);
1194
1195   // Add the range of this function to the list of ranges for the CU.
1196   TheCU.addRange(RangeSpan(Asm->getFunctionBegin(), Asm->getFunctionEnd()));
1197
1198   // Under -gmlt, skip building the subprogram if there are no inlined
1199   // subroutines inside it.
1200   if (TheCU.getCUNode()->getEmissionKind() == DIBuilder::LineTablesOnly &&
1201       LScopes.getAbstractScopesList().empty() && !IsDarwin) {
1202     assert(InfoHolder.getScopeVariables().empty());
1203     assert(DbgValues.empty());
1204     // FIXME: This wouldn't be true in LTO with a -g (with inlining) CU followed
1205     // by a -gmlt CU. Add a test and remove this assertion.
1206     assert(AbstractVariables.empty());
1207     LabelsBeforeInsn.clear();
1208     LabelsAfterInsn.clear();
1209     PrevLabel = nullptr;
1210     CurFn = nullptr;
1211     return;
1212   }
1213
1214 #ifndef NDEBUG
1215   size_t NumAbstractScopes = LScopes.getAbstractScopesList().size();
1216 #endif
1217   // Construct abstract scopes.
1218   for (LexicalScope *AScope : LScopes.getAbstractScopesList()) {
1219     auto *SP = cast<MDSubprogram>(AScope->getScopeNode());
1220     // Collect info for variables that were optimized out.
1221     for (const MDLocalVariable *DV : SP->getVariables()) {
1222       if (!ProcessedVars.insert(InlinedVariable(DV, nullptr)).second)
1223         continue;
1224       ensureAbstractVariableIsCreated(InlinedVariable(DV, nullptr),
1225                                       DV->getScope());
1226       assert(LScopes.getAbstractScopesList().size() == NumAbstractScopes
1227              && "ensureAbstractVariableIsCreated inserted abstract scopes");
1228     }
1229     constructAbstractSubprogramScopeDIE(AScope);
1230   }
1231
1232   TheCU.constructSubprogramScopeDIE(FnScope);
1233   if (auto *SkelCU = TheCU.getSkeleton())
1234     if (!LScopes.getAbstractScopesList().empty())
1235       SkelCU->constructSubprogramScopeDIE(FnScope);
1236
1237   // Clear debug info
1238   // Ownership of DbgVariables is a bit subtle - ScopeVariables owns all the
1239   // DbgVariables except those that are also in AbstractVariables (since they
1240   // can be used cross-function)
1241   InfoHolder.getScopeVariables().clear();
1242   DbgValues.clear();
1243   LabelsBeforeInsn.clear();
1244   LabelsAfterInsn.clear();
1245   PrevLabel = nullptr;
1246   CurFn = nullptr;
1247 }
1248
1249 // Register a source line with debug info. Returns the  unique label that was
1250 // emitted and which provides correspondence to the source line list.
1251 void DwarfDebug::recordSourceLine(unsigned Line, unsigned Col, const MDNode *S,
1252                                   unsigned Flags) {
1253   StringRef Fn;
1254   StringRef Dir;
1255   unsigned Src = 1;
1256   unsigned Discriminator = 0;
1257   if (auto *Scope = cast_or_null<MDScope>(S)) {
1258     Fn = Scope->getFilename();
1259     Dir = Scope->getDirectory();
1260     if (auto *LBF = dyn_cast<MDLexicalBlockFile>(Scope))
1261       Discriminator = LBF->getDiscriminator();
1262
1263     unsigned CUID = Asm->OutStreamer.getContext().getDwarfCompileUnitID();
1264     Src = static_cast<DwarfCompileUnit &>(*InfoHolder.getUnits()[CUID])
1265               .getOrCreateSourceID(Fn, Dir);
1266   }
1267   Asm->OutStreamer.EmitDwarfLocDirective(Src, Line, Col, Flags, 0,
1268                                          Discriminator, Fn);
1269 }
1270
1271 //===----------------------------------------------------------------------===//
1272 // Emit Methods
1273 //===----------------------------------------------------------------------===//
1274
1275 // Emit the debug info section.
1276 void DwarfDebug::emitDebugInfo() {
1277   DwarfFile &Holder = useSplitDwarf() ? SkeletonHolder : InfoHolder;
1278   Holder.emitUnits(/* UseOffsets */ false);
1279 }
1280
1281 // Emit the abbreviation section.
1282 void DwarfDebug::emitAbbreviations() {
1283   DwarfFile &Holder = useSplitDwarf() ? SkeletonHolder : InfoHolder;
1284
1285   Holder.emitAbbrevs(Asm->getObjFileLowering().getDwarfAbbrevSection());
1286 }
1287
1288 void DwarfDebug::emitAccel(DwarfAccelTable &Accel, const MCSection *Section,
1289                            StringRef TableName) {
1290   Accel.FinalizeTable(Asm, TableName);
1291   Asm->OutStreamer.SwitchSection(Section);
1292
1293   // Emit the full data.
1294   Accel.emit(Asm, Section->getBeginSymbol(), this);
1295 }
1296
1297 // Emit visible names into a hashed accelerator table section.
1298 void DwarfDebug::emitAccelNames() {
1299   emitAccel(AccelNames, Asm->getObjFileLowering().getDwarfAccelNamesSection(),
1300             "Names");
1301 }
1302
1303 // Emit objective C classes and categories into a hashed accelerator table
1304 // section.
1305 void DwarfDebug::emitAccelObjC() {
1306   emitAccel(AccelObjC, Asm->getObjFileLowering().getDwarfAccelObjCSection(),
1307             "ObjC");
1308 }
1309
1310 // Emit namespace dies into a hashed accelerator table.
1311 void DwarfDebug::emitAccelNamespaces() {
1312   emitAccel(AccelNamespace,
1313             Asm->getObjFileLowering().getDwarfAccelNamespaceSection(),
1314             "namespac");
1315 }
1316
1317 // Emit type dies into a hashed accelerator table.
1318 void DwarfDebug::emitAccelTypes() {
1319   emitAccel(AccelTypes, Asm->getObjFileLowering().getDwarfAccelTypesSection(),
1320             "types");
1321 }
1322
1323 // Public name handling.
1324 // The format for the various pubnames:
1325 //
1326 // dwarf pubnames - offset/name pairs where the offset is the offset into the CU
1327 // for the DIE that is named.
1328 //
1329 // gnu pubnames - offset/index value/name tuples where the offset is the offset
1330 // into the CU and the index value is computed according to the type of value
1331 // for the DIE that is named.
1332 //
1333 // For type units the offset is the offset of the skeleton DIE. For split dwarf
1334 // it's the offset within the debug_info/debug_types dwo section, however, the
1335 // reference in the pubname header doesn't change.
1336
1337 /// computeIndexValue - Compute the gdb index value for the DIE and CU.
1338 static dwarf::PubIndexEntryDescriptor computeIndexValue(DwarfUnit *CU,
1339                                                         const DIE *Die) {
1340   dwarf::GDBIndexEntryLinkage Linkage = dwarf::GIEL_STATIC;
1341
1342   // We could have a specification DIE that has our most of our knowledge,
1343   // look for that now.
1344   DIEValue *SpecVal = Die->findAttribute(dwarf::DW_AT_specification);
1345   if (SpecVal) {
1346     DIE &SpecDIE = cast<DIEEntry>(SpecVal)->getEntry();
1347     if (SpecDIE.findAttribute(dwarf::DW_AT_external))
1348       Linkage = dwarf::GIEL_EXTERNAL;
1349   } else if (Die->findAttribute(dwarf::DW_AT_external))
1350     Linkage = dwarf::GIEL_EXTERNAL;
1351
1352   switch (Die->getTag()) {
1353   case dwarf::DW_TAG_class_type:
1354   case dwarf::DW_TAG_structure_type:
1355   case dwarf::DW_TAG_union_type:
1356   case dwarf::DW_TAG_enumeration_type:
1357     return dwarf::PubIndexEntryDescriptor(
1358         dwarf::GIEK_TYPE, CU->getLanguage() != dwarf::DW_LANG_C_plus_plus
1359                               ? dwarf::GIEL_STATIC
1360                               : dwarf::GIEL_EXTERNAL);
1361   case dwarf::DW_TAG_typedef:
1362   case dwarf::DW_TAG_base_type:
1363   case dwarf::DW_TAG_subrange_type:
1364     return dwarf::PubIndexEntryDescriptor(dwarf::GIEK_TYPE, dwarf::GIEL_STATIC);
1365   case dwarf::DW_TAG_namespace:
1366     return dwarf::GIEK_TYPE;
1367   case dwarf::DW_TAG_subprogram:
1368     return dwarf::PubIndexEntryDescriptor(dwarf::GIEK_FUNCTION, Linkage);
1369   case dwarf::DW_TAG_variable:
1370     return dwarf::PubIndexEntryDescriptor(dwarf::GIEK_VARIABLE, Linkage);
1371   case dwarf::DW_TAG_enumerator:
1372     return dwarf::PubIndexEntryDescriptor(dwarf::GIEK_VARIABLE,
1373                                           dwarf::GIEL_STATIC);
1374   default:
1375     return dwarf::GIEK_NONE;
1376   }
1377 }
1378
1379 /// emitDebugPubNames - Emit visible names into a debug pubnames section.
1380 ///
1381 void DwarfDebug::emitDebugPubNames(bool GnuStyle) {
1382   const MCSection *PSec =
1383       GnuStyle ? Asm->getObjFileLowering().getDwarfGnuPubNamesSection()
1384                : Asm->getObjFileLowering().getDwarfPubNamesSection();
1385
1386   emitDebugPubSection(GnuStyle, PSec, "Names",
1387                       &DwarfCompileUnit::getGlobalNames);
1388 }
1389
1390 void DwarfDebug::emitDebugPubSection(
1391     bool GnuStyle, const MCSection *PSec, StringRef Name,
1392     const StringMap<const DIE *> &(DwarfCompileUnit::*Accessor)() const) {
1393   for (const auto &NU : CUMap) {
1394     DwarfCompileUnit *TheU = NU.second;
1395
1396     const auto &Globals = (TheU->*Accessor)();
1397
1398     if (Globals.empty())
1399       continue;
1400
1401     if (auto *Skeleton = TheU->getSkeleton())
1402       TheU = Skeleton;
1403
1404     // Start the dwarf pubnames section.
1405     Asm->OutStreamer.SwitchSection(PSec);
1406
1407     // Emit the header.
1408     Asm->OutStreamer.AddComment("Length of Public " + Name + " Info");
1409     MCSymbol *BeginLabel = Asm->createTempSymbol("pub" + Name + "_begin");
1410     MCSymbol *EndLabel = Asm->createTempSymbol("pub" + Name + "_end");
1411     Asm->EmitLabelDifference(EndLabel, BeginLabel, 4);
1412
1413     Asm->OutStreamer.EmitLabel(BeginLabel);
1414
1415     Asm->OutStreamer.AddComment("DWARF Version");
1416     Asm->EmitInt16(dwarf::DW_PUBNAMES_VERSION);
1417
1418     Asm->OutStreamer.AddComment("Offset of Compilation Unit Info");
1419     Asm->emitSectionOffset(TheU->getLabelBegin());
1420
1421     Asm->OutStreamer.AddComment("Compilation Unit Length");
1422     Asm->EmitInt32(TheU->getLength());
1423
1424     // Emit the pubnames for this compilation unit.
1425     for (const auto &GI : Globals) {
1426       const char *Name = GI.getKeyData();
1427       const DIE *Entity = GI.second;
1428
1429       Asm->OutStreamer.AddComment("DIE offset");
1430       Asm->EmitInt32(Entity->getOffset());
1431
1432       if (GnuStyle) {
1433         dwarf::PubIndexEntryDescriptor Desc = computeIndexValue(TheU, Entity);
1434         Asm->OutStreamer.AddComment(
1435             Twine("Kind: ") + dwarf::GDBIndexEntryKindString(Desc.Kind) + ", " +
1436             dwarf::GDBIndexEntryLinkageString(Desc.Linkage));
1437         Asm->EmitInt8(Desc.toBits());
1438       }
1439
1440       Asm->OutStreamer.AddComment("External Name");
1441       Asm->OutStreamer.EmitBytes(StringRef(Name, GI.getKeyLength() + 1));
1442     }
1443
1444     Asm->OutStreamer.AddComment("End Mark");
1445     Asm->EmitInt32(0);
1446     Asm->OutStreamer.EmitLabel(EndLabel);
1447   }
1448 }
1449
1450 void DwarfDebug::emitDebugPubTypes(bool GnuStyle) {
1451   const MCSection *PSec =
1452       GnuStyle ? Asm->getObjFileLowering().getDwarfGnuPubTypesSection()
1453                : Asm->getObjFileLowering().getDwarfPubTypesSection();
1454
1455   emitDebugPubSection(GnuStyle, PSec, "Types",
1456                       &DwarfCompileUnit::getGlobalTypes);
1457 }
1458
1459 // Emit visible names into a debug str section.
1460 void DwarfDebug::emitDebugStr() {
1461   DwarfFile &Holder = useSplitDwarf() ? SkeletonHolder : InfoHolder;
1462   Holder.emitStrings(Asm->getObjFileLowering().getDwarfStrSection());
1463 }
1464
1465 void DwarfDebug::emitDebugLocEntry(ByteStreamer &Streamer,
1466                                    const DebugLocStream::Entry &Entry) {
1467   auto &&Comments = DebugLocs.getComments(Entry);
1468   auto Comment = Comments.begin();
1469   auto End = Comments.end();
1470   for (uint8_t Byte : DebugLocs.getBytes(Entry))
1471     Streamer.EmitInt8(Byte, Comment != End ? *(Comment++) : "");
1472 }
1473
1474 static void emitDebugLocValue(const AsmPrinter &AP, const MDBasicType *BT,
1475                               ByteStreamer &Streamer,
1476                               const DebugLocEntry::Value &Value,
1477                               unsigned PieceOffsetInBits) {
1478   DebugLocDwarfExpression DwarfExpr(*AP.MF->getSubtarget().getRegisterInfo(),
1479                                     AP.getDwarfDebug()->getDwarfVersion(),
1480                                     Streamer);
1481   // Regular entry.
1482   if (Value.isInt()) {
1483     if (BT && (BT->getEncoding() == dwarf::DW_ATE_signed ||
1484                BT->getEncoding() == dwarf::DW_ATE_signed_char))
1485       DwarfExpr.AddSignedConstant(Value.getInt());
1486     else
1487       DwarfExpr.AddUnsignedConstant(Value.getInt());
1488   } else if (Value.isLocation()) {
1489     MachineLocation Loc = Value.getLoc();
1490     const MDExpression *Expr = Value.getExpression();
1491     if (!Expr || !Expr->getNumElements())
1492       // Regular entry.
1493       AP.EmitDwarfRegOp(Streamer, Loc);
1494     else {
1495       // Complex address entry.
1496       if (Loc.getOffset()) {
1497         DwarfExpr.AddMachineRegIndirect(Loc.getReg(), Loc.getOffset());
1498         DwarfExpr.AddExpression(Expr->expr_op_begin(), Expr->expr_op_end(),
1499                                 PieceOffsetInBits);
1500       } else
1501         DwarfExpr.AddMachineRegExpression(Expr, Loc.getReg(),
1502                                           PieceOffsetInBits);
1503     }
1504   }
1505   // else ... ignore constant fp. There is not any good way to
1506   // to represent them here in dwarf.
1507   // FIXME: ^
1508 }
1509
1510 void DebugLocEntry::finalize(const AsmPrinter &AP, DebugLocStream &Locs,
1511                              const MDBasicType *BT) {
1512   Locs.startEntry(Begin, End);
1513   BufferByteStreamer Streamer = Locs.getStreamer();
1514   const DebugLocEntry::Value &Value = Values[0];
1515   if (Value.isBitPiece()) {
1516     // Emit all pieces that belong to the same variable and range.
1517     assert(std::all_of(Values.begin(), Values.end(), [](DebugLocEntry::Value P) {
1518           return P.isBitPiece();
1519         }) && "all values are expected to be pieces");
1520     assert(std::is_sorted(Values.begin(), Values.end()) &&
1521            "pieces are expected to be sorted");
1522    
1523     unsigned Offset = 0;
1524     for (auto Piece : Values) {
1525       const MDExpression *Expr = Piece.getExpression();
1526       unsigned PieceOffset = Expr->getBitPieceOffset();
1527       unsigned PieceSize = Expr->getBitPieceSize();
1528       assert(Offset <= PieceOffset && "overlapping or duplicate pieces");
1529       if (Offset < PieceOffset) {
1530         // The DWARF spec seriously mandates pieces with no locations for gaps.
1531         DebugLocDwarfExpression Expr(*AP.MF->getSubtarget().getRegisterInfo(),
1532                                      AP.getDwarfDebug()->getDwarfVersion(),
1533                                      Streamer);
1534         Expr.AddOpPiece(PieceOffset-Offset, 0);
1535         Offset += PieceOffset-Offset;
1536       }
1537       Offset += PieceSize;
1538
1539       emitDebugLocValue(AP, BT, Streamer, Piece, PieceOffset);
1540     }
1541   } else {
1542     assert(Values.size() == 1 && "only pieces may have >1 value");
1543     emitDebugLocValue(AP, BT, Streamer, Value, 0);
1544   }
1545 }
1546
1547 void DwarfDebug::emitDebugLocEntryLocation(const DebugLocStream::Entry &Entry) {
1548   Asm->OutStreamer.AddComment("Loc expr size");
1549   MCSymbol *begin = Asm->OutStreamer.getContext().CreateTempSymbol();
1550   MCSymbol *end = Asm->OutStreamer.getContext().CreateTempSymbol();
1551   Asm->EmitLabelDifference(end, begin, 2);
1552   Asm->OutStreamer.EmitLabel(begin);
1553   // Emit the entry.
1554   APByteStreamer Streamer(*Asm);
1555   emitDebugLocEntry(Streamer, Entry);
1556   // Close the range.
1557   Asm->OutStreamer.EmitLabel(end);
1558 }
1559
1560 // Emit locations into the debug loc section.
1561 void DwarfDebug::emitDebugLoc() {
1562   // Start the dwarf loc section.
1563   Asm->OutStreamer.SwitchSection(
1564       Asm->getObjFileLowering().getDwarfLocSection());
1565   unsigned char Size = Asm->getDataLayout().getPointerSize();
1566   for (const auto &List : DebugLocs.getLists()) {
1567     Asm->OutStreamer.EmitLabel(List.Label);
1568     const DwarfCompileUnit *CU = List.CU;
1569     for (const auto &Entry : DebugLocs.getEntries(List)) {
1570       // Set up the range. This range is relative to the entry point of the
1571       // compile unit. This is a hard coded 0 for low_pc when we're emitting
1572       // ranges, or the DW_AT_low_pc on the compile unit otherwise.
1573       if (auto *Base = CU->getBaseAddress()) {
1574         Asm->EmitLabelDifference(Entry.BeginSym, Base, Size);
1575         Asm->EmitLabelDifference(Entry.EndSym, Base, Size);
1576       } else {
1577         Asm->OutStreamer.EmitSymbolValue(Entry.BeginSym, Size);
1578         Asm->OutStreamer.EmitSymbolValue(Entry.EndSym, Size);
1579       }
1580
1581       emitDebugLocEntryLocation(Entry);
1582     }
1583     Asm->OutStreamer.EmitIntValue(0, Size);
1584     Asm->OutStreamer.EmitIntValue(0, Size);
1585   }
1586 }
1587
1588 void DwarfDebug::emitDebugLocDWO() {
1589   Asm->OutStreamer.SwitchSection(
1590       Asm->getObjFileLowering().getDwarfLocDWOSection());
1591   for (const auto &List : DebugLocs.getLists()) {
1592     Asm->OutStreamer.EmitLabel(List.Label);
1593     for (const auto &Entry : DebugLocs.getEntries(List)) {
1594       // Just always use start_length for now - at least that's one address
1595       // rather than two. We could get fancier and try to, say, reuse an
1596       // address we know we've emitted elsewhere (the start of the function?
1597       // The start of the CU or CU subrange that encloses this range?)
1598       Asm->EmitInt8(dwarf::DW_LLE_start_length_entry);
1599       unsigned idx = AddrPool.getIndex(Entry.BeginSym);
1600       Asm->EmitULEB128(idx);
1601       Asm->EmitLabelDifference(Entry.EndSym, Entry.BeginSym, 4);
1602
1603       emitDebugLocEntryLocation(Entry);
1604     }
1605     Asm->EmitInt8(dwarf::DW_LLE_end_of_list_entry);
1606   }
1607 }
1608
1609 struct ArangeSpan {
1610   const MCSymbol *Start, *End;
1611 };
1612
1613 // Emit a debug aranges section, containing a CU lookup for any
1614 // address we can tie back to a CU.
1615 void DwarfDebug::emitDebugARanges() {
1616   // Provides a unique id per text section.
1617   MapVector<const MCSection *, SmallVector<SymbolCU, 8>> SectionMap;
1618
1619   // Filter labels by section.
1620   for (const SymbolCU &SCU : ArangeLabels) {
1621     if (SCU.Sym->isInSection()) {
1622       // Make a note of this symbol and it's section.
1623       const MCSection *Section = &SCU.Sym->getSection();
1624       if (!Section->getKind().isMetadata())
1625         SectionMap[Section].push_back(SCU);
1626     } else {
1627       // Some symbols (e.g. common/bss on mach-o) can have no section but still
1628       // appear in the output. This sucks as we rely on sections to build
1629       // arange spans. We can do it without, but it's icky.
1630       SectionMap[nullptr].push_back(SCU);
1631     }
1632   }
1633
1634   // Add terminating symbols for each section.
1635   for (const auto &I : SectionMap) {
1636     const MCSection *Section = I.first;
1637     MCSymbol *Sym = nullptr;
1638
1639     if (Section)
1640       Sym = Asm->OutStreamer.endSection(Section);
1641
1642     // Insert a final terminator.
1643     SectionMap[Section].push_back(SymbolCU(nullptr, Sym));
1644   }
1645
1646   DenseMap<DwarfCompileUnit *, std::vector<ArangeSpan>> Spans;
1647
1648   for (auto &I : SectionMap) {
1649     const MCSection *Section = I.first;
1650     SmallVector<SymbolCU, 8> &List = I.second;
1651     if (List.size() < 2)
1652       continue;
1653
1654     // If we have no section (e.g. common), just write out
1655     // individual spans for each symbol.
1656     if (!Section) {
1657       for (const SymbolCU &Cur : List) {
1658         ArangeSpan Span;
1659         Span.Start = Cur.Sym;
1660         Span.End = nullptr;
1661         if (Cur.CU)
1662           Spans[Cur.CU].push_back(Span);
1663       }
1664       continue;
1665     }
1666
1667     // Sort the symbols by offset within the section.
1668     std::sort(List.begin(), List.end(),
1669               [&](const SymbolCU &A, const SymbolCU &B) {
1670       unsigned IA = A.Sym ? Asm->OutStreamer.GetSymbolOrder(A.Sym) : 0;
1671       unsigned IB = B.Sym ? Asm->OutStreamer.GetSymbolOrder(B.Sym) : 0;
1672
1673       // Symbols with no order assigned should be placed at the end.
1674       // (e.g. section end labels)
1675       if (IA == 0)
1676         return false;
1677       if (IB == 0)
1678         return true;
1679       return IA < IB;
1680     });
1681
1682     // Build spans between each label.
1683     const MCSymbol *StartSym = List[0].Sym;
1684     for (size_t n = 1, e = List.size(); n < e; n++) {
1685       const SymbolCU &Prev = List[n - 1];
1686       const SymbolCU &Cur = List[n];
1687
1688       // Try and build the longest span we can within the same CU.
1689       if (Cur.CU != Prev.CU) {
1690         ArangeSpan Span;
1691         Span.Start = StartSym;
1692         Span.End = Cur.Sym;
1693         Spans[Prev.CU].push_back(Span);
1694         StartSym = Cur.Sym;
1695       }
1696     }
1697   }
1698
1699   // Start the dwarf aranges section.
1700   Asm->OutStreamer.SwitchSection(
1701       Asm->getObjFileLowering().getDwarfARangesSection());
1702
1703   unsigned PtrSize = Asm->getDataLayout().getPointerSize();
1704
1705   // Build a list of CUs used.
1706   std::vector<DwarfCompileUnit *> CUs;
1707   for (const auto &it : Spans) {
1708     DwarfCompileUnit *CU = it.first;
1709     CUs.push_back(CU);
1710   }
1711
1712   // Sort the CU list (again, to ensure consistent output order).
1713   std::sort(CUs.begin(), CUs.end(), [](const DwarfUnit *A, const DwarfUnit *B) {
1714     return A->getUniqueID() < B->getUniqueID();
1715   });
1716
1717   // Emit an arange table for each CU we used.
1718   for (DwarfCompileUnit *CU : CUs) {
1719     std::vector<ArangeSpan> &List = Spans[CU];
1720
1721     // Describe the skeleton CU's offset and length, not the dwo file's.
1722     if (auto *Skel = CU->getSkeleton())
1723       CU = Skel;
1724
1725     // Emit size of content not including length itself.
1726     unsigned ContentSize =
1727         sizeof(int16_t) + // DWARF ARange version number
1728         sizeof(int32_t) + // Offset of CU in the .debug_info section
1729         sizeof(int8_t) +  // Pointer Size (in bytes)
1730         sizeof(int8_t);   // Segment Size (in bytes)
1731
1732     unsigned TupleSize = PtrSize * 2;
1733
1734     // 7.20 in the Dwarf specs requires the table to be aligned to a tuple.
1735     unsigned Padding =
1736         OffsetToAlignment(sizeof(int32_t) + ContentSize, TupleSize);
1737
1738     ContentSize += Padding;
1739     ContentSize += (List.size() + 1) * TupleSize;
1740
1741     // For each compile unit, write the list of spans it covers.
1742     Asm->OutStreamer.AddComment("Length of ARange Set");
1743     Asm->EmitInt32(ContentSize);
1744     Asm->OutStreamer.AddComment("DWARF Arange version number");
1745     Asm->EmitInt16(dwarf::DW_ARANGES_VERSION);
1746     Asm->OutStreamer.AddComment("Offset Into Debug Info Section");
1747     Asm->emitSectionOffset(CU->getLabelBegin());
1748     Asm->OutStreamer.AddComment("Address Size (in bytes)");
1749     Asm->EmitInt8(PtrSize);
1750     Asm->OutStreamer.AddComment("Segment Size (in bytes)");
1751     Asm->EmitInt8(0);
1752
1753     Asm->OutStreamer.EmitFill(Padding, 0xff);
1754
1755     for (const ArangeSpan &Span : List) {
1756       Asm->EmitLabelReference(Span.Start, PtrSize);
1757
1758       // Calculate the size as being from the span start to it's end.
1759       if (Span.End) {
1760         Asm->EmitLabelDifference(Span.End, Span.Start, PtrSize);
1761       } else {
1762         // For symbols without an end marker (e.g. common), we
1763         // write a single arange entry containing just that one symbol.
1764         uint64_t Size = SymSize[Span.Start];
1765         if (Size == 0)
1766           Size = 1;
1767
1768         Asm->OutStreamer.EmitIntValue(Size, PtrSize);
1769       }
1770     }
1771
1772     Asm->OutStreamer.AddComment("ARange terminator");
1773     Asm->OutStreamer.EmitIntValue(0, PtrSize);
1774     Asm->OutStreamer.EmitIntValue(0, PtrSize);
1775   }
1776 }
1777
1778 // Emit visible names into a debug ranges section.
1779 void DwarfDebug::emitDebugRanges() {
1780   // Start the dwarf ranges section.
1781   Asm->OutStreamer.SwitchSection(
1782       Asm->getObjFileLowering().getDwarfRangesSection());
1783
1784   // Size for our labels.
1785   unsigned char Size = Asm->getDataLayout().getPointerSize();
1786
1787   // Grab the specific ranges for the compile units in the module.
1788   for (const auto &I : CUMap) {
1789     DwarfCompileUnit *TheCU = I.second;
1790
1791     if (auto *Skel = TheCU->getSkeleton())
1792       TheCU = Skel;
1793
1794     // Iterate over the misc ranges for the compile units in the module.
1795     for (const RangeSpanList &List : TheCU->getRangeLists()) {
1796       // Emit our symbol so we can find the beginning of the range.
1797       Asm->OutStreamer.EmitLabel(List.getSym());
1798
1799       for (const RangeSpan &Range : List.getRanges()) {
1800         const MCSymbol *Begin = Range.getStart();
1801         const MCSymbol *End = Range.getEnd();
1802         assert(Begin && "Range without a begin symbol?");
1803         assert(End && "Range without an end symbol?");
1804         if (auto *Base = TheCU->getBaseAddress()) {
1805           Asm->EmitLabelDifference(Begin, Base, Size);
1806           Asm->EmitLabelDifference(End, Base, Size);
1807         } else {
1808           Asm->OutStreamer.EmitSymbolValue(Begin, Size);
1809           Asm->OutStreamer.EmitSymbolValue(End, Size);
1810         }
1811       }
1812
1813       // And terminate the list with two 0 values.
1814       Asm->OutStreamer.EmitIntValue(0, Size);
1815       Asm->OutStreamer.EmitIntValue(0, Size);
1816     }
1817   }
1818 }
1819
1820 // DWARF5 Experimental Separate Dwarf emitters.
1821
1822 void DwarfDebug::initSkeletonUnit(const DwarfUnit &U, DIE &Die,
1823                                   std::unique_ptr<DwarfUnit> NewU) {
1824   NewU->addString(Die, dwarf::DW_AT_GNU_dwo_name,
1825                   U.getCUNode()->getSplitDebugFilename());
1826
1827   if (!CompilationDir.empty())
1828     NewU->addString(Die, dwarf::DW_AT_comp_dir, CompilationDir);
1829
1830   addGnuPubAttributes(*NewU, Die);
1831
1832   SkeletonHolder.addUnit(std::move(NewU));
1833 }
1834
1835 // This DIE has the following attributes: DW_AT_comp_dir, DW_AT_stmt_list,
1836 // DW_AT_low_pc, DW_AT_high_pc, DW_AT_ranges, DW_AT_dwo_name, DW_AT_dwo_id,
1837 // DW_AT_addr_base, DW_AT_ranges_base.
1838 DwarfCompileUnit &DwarfDebug::constructSkeletonCU(const DwarfCompileUnit &CU) {
1839
1840   auto OwnedUnit = make_unique<DwarfCompileUnit>(
1841       CU.getUniqueID(), CU.getCUNode(), Asm, this, &SkeletonHolder);
1842   DwarfCompileUnit &NewCU = *OwnedUnit;
1843   NewCU.initSection(Asm->getObjFileLowering().getDwarfInfoSection());
1844
1845   NewCU.initStmtList();
1846
1847   initSkeletonUnit(CU, NewCU.getUnitDie(), std::move(OwnedUnit));
1848
1849   return NewCU;
1850 }
1851
1852 // Emit the .debug_info.dwo section for separated dwarf. This contains the
1853 // compile units that would normally be in debug_info.
1854 void DwarfDebug::emitDebugInfoDWO() {
1855   assert(useSplitDwarf() && "No split dwarf debug info?");
1856   // Don't emit relocations into the dwo file.
1857   InfoHolder.emitUnits(/* UseOffsets */ true);
1858 }
1859
1860 // Emit the .debug_abbrev.dwo section for separated dwarf. This contains the
1861 // abbreviations for the .debug_info.dwo section.
1862 void DwarfDebug::emitDebugAbbrevDWO() {
1863   assert(useSplitDwarf() && "No split dwarf?");
1864   InfoHolder.emitAbbrevs(Asm->getObjFileLowering().getDwarfAbbrevDWOSection());
1865 }
1866
1867 void DwarfDebug::emitDebugLineDWO() {
1868   assert(useSplitDwarf() && "No split dwarf?");
1869   Asm->OutStreamer.SwitchSection(
1870       Asm->getObjFileLowering().getDwarfLineDWOSection());
1871   SplitTypeUnitFileTable.Emit(Asm->OutStreamer);
1872 }
1873
1874 // Emit the .debug_str.dwo section for separated dwarf. This contains the
1875 // string section and is identical in format to traditional .debug_str
1876 // sections.
1877 void DwarfDebug::emitDebugStrDWO() {
1878   assert(useSplitDwarf() && "No split dwarf?");
1879   const MCSection *OffSec =
1880       Asm->getObjFileLowering().getDwarfStrOffDWOSection();
1881   InfoHolder.emitStrings(Asm->getObjFileLowering().getDwarfStrDWOSection(),
1882                          OffSec);
1883 }
1884
1885 MCDwarfDwoLineTable *DwarfDebug::getDwoLineTable(const DwarfCompileUnit &CU) {
1886   if (!useSplitDwarf())
1887     return nullptr;
1888   if (SingleCU)
1889     SplitTypeUnitFileTable.setCompilationDir(CU.getCUNode()->getDirectory());
1890   return &SplitTypeUnitFileTable;
1891 }
1892
1893 static uint64_t makeTypeSignature(StringRef Identifier) {
1894   MD5 Hash;
1895   Hash.update(Identifier);
1896   // ... take the least significant 8 bytes and return those. Our MD5
1897   // implementation always returns its results in little endian, swap bytes
1898   // appropriately.
1899   MD5::MD5Result Result;
1900   Hash.final(Result);
1901   return support::endian::read64le(Result + 8);
1902 }
1903
1904 void DwarfDebug::addDwarfTypeUnitType(DwarfCompileUnit &CU,
1905                                       StringRef Identifier, DIE &RefDie,
1906                                       const MDCompositeType *CTy) {
1907   // Fast path if we're building some type units and one has already used the
1908   // address pool we know we're going to throw away all this work anyway, so
1909   // don't bother building dependent types.
1910   if (!TypeUnitsUnderConstruction.empty() && AddrPool.hasBeenUsed())
1911     return;
1912
1913   const DwarfTypeUnit *&TU = DwarfTypeUnits[CTy];
1914   if (TU) {
1915     CU.addDIETypeSignature(RefDie, *TU);
1916     return;
1917   }
1918
1919   bool TopLevelType = TypeUnitsUnderConstruction.empty();
1920   AddrPool.resetUsedFlag();
1921
1922   auto OwnedUnit = make_unique<DwarfTypeUnit>(
1923       InfoHolder.getUnits().size() + TypeUnitsUnderConstruction.size(), CU, Asm,
1924       this, &InfoHolder, getDwoLineTable(CU));
1925   DwarfTypeUnit &NewTU = *OwnedUnit;
1926   DIE &UnitDie = NewTU.getUnitDie();
1927   TU = &NewTU;
1928   TypeUnitsUnderConstruction.push_back(
1929       std::make_pair(std::move(OwnedUnit), CTy));
1930
1931   NewTU.addUInt(UnitDie, dwarf::DW_AT_language, dwarf::DW_FORM_data2,
1932                 CU.getLanguage());
1933
1934   uint64_t Signature = makeTypeSignature(Identifier);
1935   NewTU.setTypeSignature(Signature);
1936
1937   if (useSplitDwarf())
1938     NewTU.initSection(Asm->getObjFileLowering().getDwarfTypesDWOSection());
1939   else {
1940     CU.applyStmtList(UnitDie);
1941     NewTU.initSection(
1942         Asm->getObjFileLowering().getDwarfTypesSection(Signature));
1943   }
1944
1945   NewTU.setType(NewTU.createTypeDIE(CTy));
1946
1947   if (TopLevelType) {
1948     auto TypeUnitsToAdd = std::move(TypeUnitsUnderConstruction);
1949     TypeUnitsUnderConstruction.clear();
1950
1951     // Types referencing entries in the address table cannot be placed in type
1952     // units.
1953     if (AddrPool.hasBeenUsed()) {
1954
1955       // Remove all the types built while building this type.
1956       // This is pessimistic as some of these types might not be dependent on
1957       // the type that used an address.
1958       for (const auto &TU : TypeUnitsToAdd)
1959         DwarfTypeUnits.erase(TU.second);
1960
1961       // Construct this type in the CU directly.
1962       // This is inefficient because all the dependent types will be rebuilt
1963       // from scratch, including building them in type units, discovering that
1964       // they depend on addresses, throwing them out and rebuilding them.
1965       CU.constructTypeDIE(RefDie, cast<MDCompositeType>(CTy));
1966       return;
1967     }
1968
1969     // If the type wasn't dependent on fission addresses, finish adding the type
1970     // and all its dependent types.
1971     for (auto &TU : TypeUnitsToAdd)
1972       InfoHolder.addUnit(std::move(TU.first));
1973   }
1974   CU.addDIETypeSignature(RefDie, NewTU);
1975 }
1976
1977 // Accelerator table mutators - add each name along with its companion
1978 // DIE to the proper table while ensuring that the name that we're going
1979 // to reference is in the string table. We do this since the names we
1980 // add may not only be identical to the names in the DIE.
1981 void DwarfDebug::addAccelName(StringRef Name, const DIE &Die) {
1982   if (!useDwarfAccelTables())
1983     return;
1984   AccelNames.AddName(Name, InfoHolder.getStringPool().getSymbol(*Asm, Name),
1985                      &Die);
1986 }
1987
1988 void DwarfDebug::addAccelObjC(StringRef Name, const DIE &Die) {
1989   if (!useDwarfAccelTables())
1990     return;
1991   AccelObjC.AddName(Name, InfoHolder.getStringPool().getSymbol(*Asm, Name),
1992                     &Die);
1993 }
1994
1995 void DwarfDebug::addAccelNamespace(StringRef Name, const DIE &Die) {
1996   if (!useDwarfAccelTables())
1997     return;
1998   AccelNamespace.AddName(Name, InfoHolder.getStringPool().getSymbol(*Asm, Name),
1999                          &Die);
2000 }
2001
2002 void DwarfDebug::addAccelType(StringRef Name, const DIE &Die, char Flags) {
2003   if (!useDwarfAccelTables())
2004     return;
2005   AccelTypes.AddName(Name, InfoHolder.getStringPool().getSymbol(*Asm, Name),
2006                      &Die);
2007 }