xref: /freebsd/contrib/llvm-project/llvm/lib/DWARFLinker/Parallel/DWARFLinkerImpl.cpp (revision 0fca6ea1d4eea4c934cfff25ac9ee8ad6fe95583) 
1  //=== DWARFLinkerImpl.cpp -------------------------------------------------===//
2  //
3  // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4  // See https://llvm.org/LICENSE.txt for license information.
5  // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6  //
7  //===----------------------------------------------------------------------===//
8  
9  #include "DWARFLinkerImpl.h"
10  #include "DIEGenerator.h"
11  #include "DependencyTracker.h"
12  #include "llvm/DWARFLinker/Utils.h"
13  #include "llvm/DebugInfo/DWARF/DWARFDebugAbbrev.h"
14  #include "llvm/Support/FormatVariadic.h"
15  #include "llvm/Support/Parallel.h"
16  #include "llvm/Support/ThreadPool.h"
17  
18  using namespace llvm;
19  using namespace dwarf_linker;
20  using namespace dwarf_linker::parallel;
21  
DWARFLinkerImpl(MessageHandlerTy ErrorHandler,MessageHandlerTy WarningHandler)22  DWARFLinkerImpl::DWARFLinkerImpl(MessageHandlerTy ErrorHandler,
23                                   MessageHandlerTy WarningHandler)
24      : UniqueUnitID(0), DebugStrStrings(GlobalData),
25        DebugLineStrStrings(GlobalData), CommonSections(GlobalData) {
26    GlobalData.setErrorHandler(ErrorHandler);
27    GlobalData.setWarningHandler(WarningHandler);
28  }
29  
LinkContext(LinkingGlobalData & GlobalData,DWARFFile & File,StringMap<uint64_t> & ClangModules,std::atomic<size_t> & UniqueUnitID)30  DWARFLinkerImpl::LinkContext::LinkContext(LinkingGlobalData &GlobalData,
31                                            DWARFFile &File,
32                                            StringMap<uint64_t> &ClangModules,
33                                            std::atomic<size_t> &UniqueUnitID)
34      : OutputSections(GlobalData), InputDWARFFile(File),
35        ClangModules(ClangModules), UniqueUnitID(UniqueUnitID) {
36  
37    if (File.Dwarf) {
38      if (!File.Dwarf->compile_units().empty())
39        CompileUnits.reserve(File.Dwarf->getNumCompileUnits());
40  
41      // Set context format&endianness based on the input file.
42      Format.Version = File.Dwarf->getMaxVersion();
43      Format.AddrSize = File.Dwarf->getCUAddrSize();
44      Endianness = File.Dwarf->isLittleEndian() ? llvm::endianness::little
45                                                : llvm::endianness::big;
46    }
47  }
48  
RefModuleUnit(DWARFFile & File,std::unique_ptr<CompileUnit> Unit)49  DWARFLinkerImpl::LinkContext::RefModuleUnit::RefModuleUnit(
50      DWARFFile &File, std::unique_ptr<CompileUnit> Unit)
51      : File(File), Unit(std::move(Unit)) {}
52  
RefModuleUnit(LinkContext::RefModuleUnit && Other)53  DWARFLinkerImpl::LinkContext::RefModuleUnit::RefModuleUnit(
54      LinkContext::RefModuleUnit &&Other)
55      : File(Other.File), Unit(std::move(Other.Unit)) {}
56  
addModulesCompileUnit(LinkContext::RefModuleUnit && Unit)57  void DWARFLinkerImpl::LinkContext::addModulesCompileUnit(
58      LinkContext::RefModuleUnit &&Unit) {
59    ModulesCompileUnits.emplace_back(std::move(Unit));
60  }
61  
addObjectFile(DWARFFile & File,ObjFileLoaderTy Loader,CompileUnitHandlerTy OnCUDieLoaded)62  void DWARFLinkerImpl::addObjectFile(DWARFFile &File, ObjFileLoaderTy Loader,
63                                      CompileUnitHandlerTy OnCUDieLoaded) {
64    ObjectContexts.emplace_back(std::make_unique<LinkContext>(
65        GlobalData, File, ClangModules, UniqueUnitID));
66  
67    if (ObjectContexts.back()->InputDWARFFile.Dwarf) {
68      for (const std::unique_ptr<DWARFUnit> &CU :
69           ObjectContexts.back()->InputDWARFFile.Dwarf->compile_units()) {
70        DWARFDie CUDie = CU->getUnitDIE();
71        OverallNumberOfCU++;
72  
73        if (!CUDie)
74          continue;
75  
76        OnCUDieLoaded(*CU);
77  
78        // Register mofule reference.
79        if (!GlobalData.getOptions().UpdateIndexTablesOnly)
80          ObjectContexts.back()->registerModuleReference(CUDie, Loader,
81                                                         OnCUDieLoaded);
82      }
83    }
84  }
85  
setEstimatedObjfilesAmount(unsigned ObjFilesNum)86  void DWARFLinkerImpl::setEstimatedObjfilesAmount(unsigned ObjFilesNum) {
87    ObjectContexts.reserve(ObjFilesNum);
88  }
89  
link()90  Error DWARFLinkerImpl::link() {
91    // reset compile unit unique ID counter.
92    UniqueUnitID = 0;
93  
94    if (Error Err = validateAndUpdateOptions())
95      return Err;
96  
97    dwarf::FormParams GlobalFormat = {GlobalData.getOptions().TargetDWARFVersion,
98                                      0, dwarf::DwarfFormat::DWARF32};
99    llvm::endianness GlobalEndianness = llvm::endianness::native;
100  
101    if (std::optional<std::reference_wrapper<const Triple>> CurTriple =
102            GlobalData.getTargetTriple()) {
103      GlobalEndianness = (*CurTriple).get().isLittleEndian()
104                             ? llvm::endianness::little
105                             : llvm::endianness::big;
106    }
107    std::optional<uint16_t> Language;
108  
109    for (std::unique_ptr<LinkContext> &Context : ObjectContexts) {
110      if (Context->InputDWARFFile.Dwarf == nullptr) {
111        Context->setOutputFormat(Context->getFormParams(), GlobalEndianness);
112        continue;
113      }
114  
115      if (GlobalData.getOptions().Verbose) {
116        outs() << "DEBUG MAP OBJECT: " << Context->InputDWARFFile.FileName
117               << "\n";
118  
119        for (const std::unique_ptr<DWARFUnit> &OrigCU :
120             Context->InputDWARFFile.Dwarf->compile_units()) {
121          outs() << "Input compilation unit:";
122          DIDumpOptions DumpOpts;
123          DumpOpts.ChildRecurseDepth = 0;
124          DumpOpts.Verbose = GlobalData.getOptions().Verbose;
125          OrigCU->getUnitDIE().dump(outs(), 0, DumpOpts);
126        }
127      }
128  
129      // Verify input DWARF if requested.
130      if (GlobalData.getOptions().VerifyInputDWARF)
131        verifyInput(Context->InputDWARFFile);
132  
133      if (!GlobalData.getTargetTriple())
134        GlobalEndianness = Context->getEndianness();
135      GlobalFormat.AddrSize =
136          std::max(GlobalFormat.AddrSize, Context->getFormParams().AddrSize);
137  
138      Context->setOutputFormat(Context->getFormParams(), GlobalEndianness);
139  
140      // FIXME: move creation of CompileUnits into the addObjectFile.
141      // This would allow to not scan for context Language and Modules state
142      // twice. And then following handling might be removed.
143      for (const std::unique_ptr<DWARFUnit> &OrigCU :
144           Context->InputDWARFFile.Dwarf->compile_units()) {
145        DWARFDie UnitDie = OrigCU->getUnitDIE();
146  
147        if (!Language) {
148          if (std::optional<DWARFFormValue> Val =
149                  UnitDie.find(dwarf::DW_AT_language)) {
150            uint16_t LangVal = dwarf::toUnsigned(Val, 0);
151            if (isODRLanguage(LangVal))
152              Language = LangVal;
153          }
154        }
155      }
156    }
157  
158    if (GlobalFormat.AddrSize == 0) {
159      if (std::optional<std::reference_wrapper<const Triple>> TargetTriple =
160              GlobalData.getTargetTriple())
161        GlobalFormat.AddrSize = (*TargetTriple).get().isArch32Bit() ? 4 : 8;
162      else
163        GlobalFormat.AddrSize = 8;
164    }
165  
166    CommonSections.setOutputFormat(GlobalFormat, GlobalEndianness);
167  
168    if (!GlobalData.Options.NoODR && Language.has_value()) {
169      llvm::parallel::TaskGroup TGroup;
170      TGroup.spawn([&]() {
171        ArtificialTypeUnit = std::make_unique<TypeUnit>(
172            GlobalData, UniqueUnitID++, Language, GlobalFormat, GlobalEndianness);
173      });
174    }
175  
176    // Set parallel options.
177    if (GlobalData.getOptions().Threads == 0)
178      llvm::parallel::strategy = optimal_concurrency(OverallNumberOfCU);
179    else
180      llvm::parallel::strategy =
181          hardware_concurrency(GlobalData.getOptions().Threads);
182  
183    // Link object files.
184    if (GlobalData.getOptions().Threads == 1) {
185      for (std::unique_ptr<LinkContext> &Context : ObjectContexts) {
186        // Link object file.
187        if (Error Err = Context->link(ArtificialTypeUnit.get()))
188          GlobalData.error(std::move(Err), Context->InputDWARFFile.FileName);
189  
190        Context->InputDWARFFile.unload();
191      }
192    } else {
193      DefaultThreadPool Pool(llvm::parallel::strategy);
194      for (std::unique_ptr<LinkContext> &Context : ObjectContexts)
195        Pool.async([&]() {
196          // Link object file.
197          if (Error Err = Context->link(ArtificialTypeUnit.get()))
198            GlobalData.error(std::move(Err), Context->InputDWARFFile.FileName);
199  
200          Context->InputDWARFFile.unload();
201        });
202  
203      Pool.wait();
204    }
205  
206    if (ArtificialTypeUnit != nullptr && !ArtificialTypeUnit->getTypePool()
207                                              .getRoot()
208                                              ->getValue()
209                                              .load()
210                                              ->Children.empty()) {
211      if (GlobalData.getTargetTriple().has_value())
212        if (Error Err = ArtificialTypeUnit->finishCloningAndEmit(
213                (*GlobalData.getTargetTriple()).get()))
214          return Err;
215    }
216  
217    // At this stage each compile units are cloned to their own set of debug
218    // sections. Now, update patches, assign offsets and assemble final file
219    // glueing debug tables from each compile unit.
220    glueCompileUnitsAndWriteToTheOutput();
221  
222    return Error::success();
223  }
224  
verifyInput(const DWARFFile & File)225  void DWARFLinkerImpl::verifyInput(const DWARFFile &File) {
226    assert(File.Dwarf);
227  
228    std::string Buffer;
229    raw_string_ostream OS(Buffer);
230    DIDumpOptions DumpOpts;
231    if (!File.Dwarf->verify(OS, DumpOpts.noImplicitRecursion())) {
232      if (GlobalData.getOptions().InputVerificationHandler)
233        GlobalData.getOptions().InputVerificationHandler(File, OS.str());
234    }
235  }
236  
validateAndUpdateOptions()237  Error DWARFLinkerImpl::validateAndUpdateOptions() {
238    if (GlobalData.getOptions().TargetDWARFVersion == 0)
239      return createStringError(std::errc::invalid_argument,
240                               "target DWARF version is not set");
241  
242    if (GlobalData.getOptions().Verbose && GlobalData.getOptions().Threads != 1) {
243      GlobalData.Options.Threads = 1;
244      GlobalData.warn(
245          "set number of threads to 1 to make --verbose to work properly.", "");
246    }
247  
248    // Do not do types deduplication in case --update.
249    if (GlobalData.getOptions().UpdateIndexTablesOnly &&
250        !GlobalData.Options.NoODR)
251      GlobalData.Options.NoODR = true;
252  
253    return Error::success();
254  }
255  
256  /// Resolve the relative path to a build artifact referenced by DWARF by
257  /// applying DW_AT_comp_dir.
resolveRelativeObjectPath(SmallVectorImpl<char> & Buf,DWARFDie CU)258  static void resolveRelativeObjectPath(SmallVectorImpl<char> &Buf, DWARFDie CU) {
259    sys::path::append(Buf, dwarf::toString(CU.find(dwarf::DW_AT_comp_dir), ""));
260  }
261  
getDwoId(const DWARFDie & CUDie)262  static uint64_t getDwoId(const DWARFDie &CUDie) {
263    auto DwoId = dwarf::toUnsigned(
264        CUDie.find({dwarf::DW_AT_dwo_id, dwarf::DW_AT_GNU_dwo_id}));
265    if (DwoId)
266      return *DwoId;
267    return 0;
268  }
269  
270  static std::string
remapPath(StringRef Path,const DWARFLinker::ObjectPrefixMapTy & ObjectPrefixMap)271  remapPath(StringRef Path,
272            const DWARFLinker::ObjectPrefixMapTy &ObjectPrefixMap) {
273    if (ObjectPrefixMap.empty())
274      return Path.str();
275  
276    SmallString<256> p = Path;
277    for (const auto &Entry : ObjectPrefixMap)
278      if (llvm::sys::path::replace_path_prefix(p, Entry.first, Entry.second))
279        break;
280    return p.str().str();
281  }
282  
getPCMFile(const DWARFDie & CUDie,DWARFLinker::ObjectPrefixMapTy * ObjectPrefixMap)283  static std::string getPCMFile(const DWARFDie &CUDie,
284                                DWARFLinker::ObjectPrefixMapTy *ObjectPrefixMap) {
285    std::string PCMFile = dwarf::toString(
286        CUDie.find({dwarf::DW_AT_dwo_name, dwarf::DW_AT_GNU_dwo_name}), "");
287  
288    if (PCMFile.empty())
289      return PCMFile;
290  
291    if (ObjectPrefixMap)
292      PCMFile = remapPath(PCMFile, *ObjectPrefixMap);
293  
294    return PCMFile;
295  }
296  
isClangModuleRef(const DWARFDie & CUDie,std::string & PCMFile,unsigned Indent,bool Quiet)297  std::pair<bool, bool> DWARFLinkerImpl::LinkContext::isClangModuleRef(
298      const DWARFDie &CUDie, std::string &PCMFile, unsigned Indent, bool Quiet) {
299    if (PCMFile.empty())
300      return std::make_pair(false, false);
301  
302    // Clang module DWARF skeleton CUs abuse this for the path to the module.
303    uint64_t DwoId = getDwoId(CUDie);
304  
305    std::string Name = dwarf::toString(CUDie.find(dwarf::DW_AT_name), "");
306    if (Name.empty()) {
307      if (!Quiet)
308        GlobalData.warn("anonymous module skeleton CU for " + PCMFile + ".",
309                        InputDWARFFile.FileName);
310      return std::make_pair(true, true);
311    }
312  
313    if (!Quiet && GlobalData.getOptions().Verbose) {
314      outs().indent(Indent);
315      outs() << "Found clang module reference " << PCMFile;
316    }
317  
318    auto Cached = ClangModules.find(PCMFile);
319    if (Cached != ClangModules.end()) {
320      // FIXME: Until PR27449 (https://llvm.org/bugs/show_bug.cgi?id=27449) is
321      // fixed in clang, only warn about DWO_id mismatches in verbose mode.
322      // ASTFileSignatures will change randomly when a module is rebuilt.
323      if (!Quiet && GlobalData.getOptions().Verbose && (Cached->second != DwoId))
324        GlobalData.warn(
325            Twine("hash mismatch: this object file was built against a "
326                  "different version of the module ") +
327                PCMFile + ".",
328            InputDWARFFile.FileName);
329      if (!Quiet && GlobalData.getOptions().Verbose)
330        outs() << " [cached].\n";
331      return std::make_pair(true, true);
332    }
333  
334    return std::make_pair(true, false);
335  }
336  
337  /// If this compile unit is really a skeleton CU that points to a
338  /// clang module, register it in ClangModules and return true.
339  ///
340  /// A skeleton CU is a CU without children, a DW_AT_gnu_dwo_name
341  /// pointing to the module, and a DW_AT_gnu_dwo_id with the module
342  /// hash.
registerModuleReference(const DWARFDie & CUDie,ObjFileLoaderTy Loader,CompileUnitHandlerTy OnCUDieLoaded,unsigned Indent)343  bool DWARFLinkerImpl::LinkContext::registerModuleReference(
344      const DWARFDie &CUDie, ObjFileLoaderTy Loader,
345      CompileUnitHandlerTy OnCUDieLoaded, unsigned Indent) {
346    std::string PCMFile =
347        getPCMFile(CUDie, GlobalData.getOptions().ObjectPrefixMap);
348    std::pair<bool, bool> IsClangModuleRef =
349        isClangModuleRef(CUDie, PCMFile, Indent, false);
350  
351    if (!IsClangModuleRef.first)
352      return false;
353  
354    if (IsClangModuleRef.second)
355      return true;
356  
357    if (GlobalData.getOptions().Verbose)
358      outs() << " ...\n";
359  
360    // Cyclic dependencies are disallowed by Clang, but we still
361    // shouldn't run into an infinite loop, so mark it as processed now.
362    ClangModules.insert({PCMFile, getDwoId(CUDie)});
363  
364    if (Error E =
365            loadClangModule(Loader, CUDie, PCMFile, OnCUDieLoaded, Indent + 2)) {
366      consumeError(std::move(E));
367      return false;
368    }
369    return true;
370  }
371  
loadClangModule(ObjFileLoaderTy Loader,const DWARFDie & CUDie,const std::string & PCMFile,CompileUnitHandlerTy OnCUDieLoaded,unsigned Indent)372  Error DWARFLinkerImpl::LinkContext::loadClangModule(
373      ObjFileLoaderTy Loader, const DWARFDie &CUDie, const std::string &PCMFile,
374      CompileUnitHandlerTy OnCUDieLoaded, unsigned Indent) {
375  
376    uint64_t DwoId = getDwoId(CUDie);
377    std::string ModuleName = dwarf::toString(CUDie.find(dwarf::DW_AT_name), "");
378  
379    /// Using a SmallString<0> because loadClangModule() is recursive.
380    SmallString<0> Path(GlobalData.getOptions().PrependPath);
381    if (sys::path::is_relative(PCMFile))
382      resolveRelativeObjectPath(Path, CUDie);
383    sys::path::append(Path, PCMFile);
384    // Don't use the cached binary holder because we have no thread-safety
385    // guarantee and the lifetime is limited.
386  
387    if (Loader == nullptr) {
388      GlobalData.error("cann't load clang module: loader is not specified.",
389                       InputDWARFFile.FileName);
390      return Error::success();
391    }
392  
393    auto ErrOrObj = Loader(InputDWARFFile.FileName, Path);
394    if (!ErrOrObj)
395      return Error::success();
396  
397    std::unique_ptr<CompileUnit> Unit;
398    for (const auto &CU : ErrOrObj->Dwarf->compile_units()) {
399      OnCUDieLoaded(*CU);
400      // Recursively get all modules imported by this one.
401      auto ChildCUDie = CU->getUnitDIE();
402      if (!ChildCUDie)
403        continue;
404      if (!registerModuleReference(ChildCUDie, Loader, OnCUDieLoaded, Indent)) {
405        if (Unit) {
406          std::string Err =
407              (PCMFile +
408               ": Clang modules are expected to have exactly 1 compile unit.\n");
409          GlobalData.error(Err, InputDWARFFile.FileName);
410          return make_error<StringError>(Err, inconvertibleErrorCode());
411        }
412        // FIXME: Until PR27449 (https://llvm.org/bugs/show_bug.cgi?id=27449) is
413        // fixed in clang, only warn about DWO_id mismatches in verbose mode.
414        // ASTFileSignatures will change randomly when a module is rebuilt.
415        uint64_t PCMDwoId = getDwoId(ChildCUDie);
416        if (PCMDwoId != DwoId) {
417          if (GlobalData.getOptions().Verbose)
418            GlobalData.warn(
419                Twine("hash mismatch: this object file was built against a "
420                      "different version of the module ") +
421                    PCMFile + ".",
422                InputDWARFFile.FileName);
423          // Update the cache entry with the DwoId of the module loaded from disk.
424          ClangModules[PCMFile] = PCMDwoId;
425        }
426  
427        // Empty modules units should not be cloned.
428        if (!ChildCUDie.hasChildren())
429          continue;
430  
431        // Add this module.
432        Unit = std::make_unique<CompileUnit>(
433            GlobalData, *CU, UniqueUnitID.fetch_add(1), ModuleName, *ErrOrObj,
434            getUnitForOffset, CU->getFormParams(), getEndianness());
435      }
436    }
437  
438    if (Unit) {
439      ModulesCompileUnits.emplace_back(RefModuleUnit{*ErrOrObj, std::move(Unit)});
440      // Preload line table, as it can't be loaded asynchronously.
441      ModulesCompileUnits.back().Unit->loadLineTable();
442    }
443  
444    return Error::success();
445  }
446  
link(TypeUnit * ArtificialTypeUnit)447  Error DWARFLinkerImpl::LinkContext::link(TypeUnit *ArtificialTypeUnit) {
448    InterCUProcessingStarted = false;
449    if (!InputDWARFFile.Dwarf)
450      return Error::success();
451  
452    // Preload macro tables, as they can't be loaded asynchronously.
453    InputDWARFFile.Dwarf->getDebugMacinfo();
454    InputDWARFFile.Dwarf->getDebugMacro();
455  
456    // Link modules compile units first.
457    parallelForEach(ModulesCompileUnits, [&](RefModuleUnit &RefModule) {
458      linkSingleCompileUnit(*RefModule.Unit, ArtificialTypeUnit);
459    });
460  
461    // Check for live relocations. If there is no any live relocation then we
462    // can skip entire object file.
463    if (!GlobalData.getOptions().UpdateIndexTablesOnly &&
464        !InputDWARFFile.Addresses->hasValidRelocs()) {
465      if (GlobalData.getOptions().Verbose)
466        outs() << "No valid relocations found. Skipping.\n";
467      return Error::success();
468    }
469  
470    OriginalDebugInfoSize = getInputDebugInfoSize();
471  
472    // Create CompileUnit structures to keep information about source
473    // DWARFUnit`s, load line tables.
474    for (const auto &OrigCU : InputDWARFFile.Dwarf->compile_units()) {
475      // Load only unit DIE at this stage.
476      auto CUDie = OrigCU->getUnitDIE();
477      std::string PCMFile =
478          getPCMFile(CUDie, GlobalData.getOptions().ObjectPrefixMap);
479  
480      // The !isClangModuleRef condition effectively skips over fully resolved
481      // skeleton units.
482      if (!CUDie || GlobalData.getOptions().UpdateIndexTablesOnly ||
483          !isClangModuleRef(CUDie, PCMFile, 0, true).first) {
484        CompileUnits.emplace_back(std::make_unique<CompileUnit>(
485            GlobalData, *OrigCU, UniqueUnitID.fetch_add(1), "", InputDWARFFile,
486            getUnitForOffset, OrigCU->getFormParams(), getEndianness()));
487  
488        // Preload line table, as it can't be loaded asynchronously.
489        CompileUnits.back()->loadLineTable();
490      }
491    };
492  
493    HasNewInterconnectedCUs = false;
494  
495    // Link self-sufficient compile units and discover inter-connected compile
496    // units.
497    parallelForEach(CompileUnits, [&](std::unique_ptr<CompileUnit> &CU) {
498      linkSingleCompileUnit(*CU, ArtificialTypeUnit);
499    });
500  
501    // Link all inter-connected units.
502    if (HasNewInterconnectedCUs) {
503      InterCUProcessingStarted = true;
504  
505      if (Error Err = finiteLoop([&]() -> Expected<bool> {
506            HasNewInterconnectedCUs = false;
507  
508            // Load inter-connected units.
509            parallelForEach(CompileUnits, [&](std::unique_ptr<CompileUnit> &CU) {
510              if (CU->isInterconnectedCU()) {
511                CU->maybeResetToLoadedStage();
512                linkSingleCompileUnit(*CU, ArtificialTypeUnit,
513                                      CompileUnit::Stage::Loaded);
514              }
515            });
516  
517            // Do liveness analysis for inter-connected units.
518            parallelForEach(CompileUnits, [&](std::unique_ptr<CompileUnit> &CU) {
519              linkSingleCompileUnit(*CU, ArtificialTypeUnit,
520                                    CompileUnit::Stage::LivenessAnalysisDone);
521            });
522  
523            return HasNewInterconnectedCUs.load();
524          }))
525        return Err;
526  
527      // Update dependencies.
528      if (Error Err = finiteLoop([&]() -> Expected<bool> {
529            HasNewGlobalDependency = false;
530            parallelForEach(CompileUnits, [&](std::unique_ptr<CompileUnit> &CU) {
531              linkSingleCompileUnit(
532                  *CU, ArtificialTypeUnit,
533                  CompileUnit::Stage::UpdateDependenciesCompleteness);
534            });
535            return HasNewGlobalDependency.load();
536          }))
537        return Err;
538      parallelForEach(CompileUnits, [&](std::unique_ptr<CompileUnit> &CU) {
539        if (CU->isInterconnectedCU() &&
540            CU->getStage() == CompileUnit::Stage::LivenessAnalysisDone)
541          CU->setStage(CompileUnit::Stage::UpdateDependenciesCompleteness);
542      });
543  
544      // Assign type names.
545      parallelForEach(CompileUnits, [&](std::unique_ptr<CompileUnit> &CU) {
546        linkSingleCompileUnit(*CU, ArtificialTypeUnit,
547                              CompileUnit::Stage::TypeNamesAssigned);
548      });
549  
550      // Clone inter-connected units.
551      parallelForEach(CompileUnits, [&](std::unique_ptr<CompileUnit> &CU) {
552        linkSingleCompileUnit(*CU, ArtificialTypeUnit,
553                              CompileUnit::Stage::Cloned);
554      });
555  
556      // Update patches for inter-connected units.
557      parallelForEach(CompileUnits, [&](std::unique_ptr<CompileUnit> &CU) {
558        linkSingleCompileUnit(*CU, ArtificialTypeUnit,
559                              CompileUnit::Stage::PatchesUpdated);
560      });
561  
562      // Release data.
563      parallelForEach(CompileUnits, [&](std::unique_ptr<CompileUnit> &CU) {
564        linkSingleCompileUnit(*CU, ArtificialTypeUnit,
565                              CompileUnit::Stage::Cleaned);
566      });
567    }
568  
569    if (GlobalData.getOptions().UpdateIndexTablesOnly) {
570      // Emit Invariant sections.
571  
572      if (Error Err = emitInvariantSections())
573        return Err;
574    } else if (!CompileUnits.empty()) {
575      // Emit .debug_frame section.
576  
577      Error ResultErr = Error::success();
578      llvm::parallel::TaskGroup TGroup;
579      // We use task group here as PerThreadBumpPtrAllocator should be called from
580      // the threads created by ThreadPoolExecutor.
581      TGroup.spawn([&]() {
582        if (Error Err = cloneAndEmitDebugFrame())
583          ResultErr = std::move(Err);
584      });
585      return ResultErr;
586    }
587  
588    return Error::success();
589  }
590  
linkSingleCompileUnit(CompileUnit & CU,TypeUnit * ArtificialTypeUnit,enum CompileUnit::Stage DoUntilStage)591  void DWARFLinkerImpl::LinkContext::linkSingleCompileUnit(
592      CompileUnit &CU, TypeUnit *ArtificialTypeUnit,
593      enum CompileUnit::Stage DoUntilStage) {
594    if (InterCUProcessingStarted != CU.isInterconnectedCU())
595      return;
596  
597    if (Error Err = finiteLoop([&]() -> Expected<bool> {
598          if (CU.getStage() >= DoUntilStage)
599            return false;
600  
601          switch (CU.getStage()) {
602          case CompileUnit::Stage::CreatedNotLoaded: {
603            // Load input compilation unit DIEs.
604            // Analyze properties of DIEs.
605            if (!CU.loadInputDIEs()) {
606              // We do not need to do liveness analysis for invalid compilation
607              // unit.
608              CU.setStage(CompileUnit::Stage::Skipped);
609            } else {
610              CU.analyzeDWARFStructure();
611  
612              // The registerModuleReference() condition effectively skips
613              // over fully resolved skeleton units. This second pass of
614              // registerModuleReferences doesn't do any new work, but it
615              // will collect top-level errors, which are suppressed. Module
616              // warnings were already displayed in the first iteration.
617              if (registerModuleReference(
618                      CU.getOrigUnit().getUnitDIE(), nullptr,
619                      [](const DWARFUnit &) {}, 0))
620                CU.setStage(CompileUnit::Stage::PatchesUpdated);
621              else
622                CU.setStage(CompileUnit::Stage::Loaded);
623            }
624          } break;
625  
626          case CompileUnit::Stage::Loaded: {
627            // Mark all the DIEs that need to be present in the generated output.
628            // If ODR requested, build type names.
629            if (!CU.resolveDependenciesAndMarkLiveness(InterCUProcessingStarted,
630                                                       HasNewInterconnectedCUs)) {
631              assert(HasNewInterconnectedCUs &&
632                     "Flag indicating new inter-connections is not set");
633              return false;
634            }
635  
636            CU.setStage(CompileUnit::Stage::LivenessAnalysisDone);
637          } break;
638  
639          case CompileUnit::Stage::LivenessAnalysisDone: {
640            if (InterCUProcessingStarted) {
641              if (CU.updateDependenciesCompleteness())
642                HasNewGlobalDependency = true;
643              return false;
644            } else {
645              if (Error Err = finiteLoop([&]() -> Expected<bool> {
646                    return CU.updateDependenciesCompleteness();
647                  }))
648                return std::move(Err);
649  
650              CU.setStage(CompileUnit::Stage::UpdateDependenciesCompleteness);
651            }
652          } break;
653  
654          case CompileUnit::Stage::UpdateDependenciesCompleteness:
655  #ifndef NDEBUG
656            CU.verifyDependencies();
657  #endif
658  
659            if (ArtificialTypeUnit) {
660              if (Error Err =
661                      CU.assignTypeNames(ArtificialTypeUnit->getTypePool()))
662                return std::move(Err);
663            }
664            CU.setStage(CompileUnit::Stage::TypeNamesAssigned);
665            break;
666  
667          case CompileUnit::Stage::TypeNamesAssigned:
668            // Clone input compile unit.
669            if (CU.isClangModule() ||
670                GlobalData.getOptions().UpdateIndexTablesOnly ||
671                CU.getContaingFile().Addresses->hasValidRelocs()) {
672              if (Error Err = CU.cloneAndEmit(GlobalData.getTargetTriple(),
673                                              ArtificialTypeUnit))
674                return std::move(Err);
675            }
676  
677            CU.setStage(CompileUnit::Stage::Cloned);
678            break;
679  
680          case CompileUnit::Stage::Cloned:
681            // Update DIEs referencies.
682            CU.updateDieRefPatchesWithClonedOffsets();
683            CU.setStage(CompileUnit::Stage::PatchesUpdated);
684            break;
685  
686          case CompileUnit::Stage::PatchesUpdated:
687            // Cleanup resources.
688            CU.cleanupDataAfterClonning();
689            CU.setStage(CompileUnit::Stage::Cleaned);
690            break;
691  
692          case CompileUnit::Stage::Cleaned:
693            assert(false);
694            break;
695  
696          case CompileUnit::Stage::Skipped:
697            // Nothing to do.
698            break;
699          }
700  
701          return true;
702        })) {
703      CU.error(std::move(Err));
704      CU.cleanupDataAfterClonning();
705      CU.setStage(CompileUnit::Stage::Skipped);
706    }
707  }
708  
emitInvariantSections()709  Error DWARFLinkerImpl::LinkContext::emitInvariantSections() {
710    if (!GlobalData.getTargetTriple().has_value())
711      return Error::success();
712  
713    getOrCreateSectionDescriptor(DebugSectionKind::DebugLoc).OS
714        << InputDWARFFile.Dwarf->getDWARFObj().getLocSection().Data;
715    getOrCreateSectionDescriptor(DebugSectionKind::DebugLocLists).OS
716        << InputDWARFFile.Dwarf->getDWARFObj().getLoclistsSection().Data;
717    getOrCreateSectionDescriptor(DebugSectionKind::DebugRange).OS
718        << InputDWARFFile.Dwarf->getDWARFObj().getRangesSection().Data;
719    getOrCreateSectionDescriptor(DebugSectionKind::DebugRngLists).OS
720        << InputDWARFFile.Dwarf->getDWARFObj().getRnglistsSection().Data;
721    getOrCreateSectionDescriptor(DebugSectionKind::DebugARanges).OS
722        << InputDWARFFile.Dwarf->getDWARFObj().getArangesSection();
723    getOrCreateSectionDescriptor(DebugSectionKind::DebugFrame).OS
724        << InputDWARFFile.Dwarf->getDWARFObj().getFrameSection().Data;
725    getOrCreateSectionDescriptor(DebugSectionKind::DebugAddr).OS
726        << InputDWARFFile.Dwarf->getDWARFObj().getAddrSection().Data;
727  
728    return Error::success();
729  }
730  
cloneAndEmitDebugFrame()731  Error DWARFLinkerImpl::LinkContext::cloneAndEmitDebugFrame() {
732    if (!GlobalData.getTargetTriple().has_value())
733      return Error::success();
734  
735    if (InputDWARFFile.Dwarf == nullptr)
736      return Error::success();
737  
738    const DWARFObject &InputDWARFObj = InputDWARFFile.Dwarf->getDWARFObj();
739  
740    StringRef OrigFrameData = InputDWARFObj.getFrameSection().Data;
741    if (OrigFrameData.empty())
742      return Error::success();
743  
744    RangesTy AllUnitsRanges;
745    for (std::unique_ptr<CompileUnit> &Unit : CompileUnits) {
746      for (auto CurRange : Unit->getFunctionRanges())
747        AllUnitsRanges.insert(CurRange.Range, CurRange.Value);
748    }
749  
750    unsigned SrcAddrSize = InputDWARFObj.getAddressSize();
751  
752    SectionDescriptor &OutSection =
753        getOrCreateSectionDescriptor(DebugSectionKind::DebugFrame);
754  
755    DataExtractor Data(OrigFrameData, InputDWARFObj.isLittleEndian(), 0);
756    uint64_t InputOffset = 0;
757  
758    // Store the data of the CIEs defined in this object, keyed by their
759    // offsets.
760    DenseMap<uint64_t, StringRef> LocalCIES;
761  
762    /// The CIEs that have been emitted in the output section. The actual CIE
763    /// data serves a the key to this StringMap.
764    StringMap<uint32_t> EmittedCIEs;
765  
766    while (Data.isValidOffset(InputOffset)) {
767      uint64_t EntryOffset = InputOffset;
768      uint32_t InitialLength = Data.getU32(&InputOffset);
769      if (InitialLength == 0xFFFFFFFF)
770        return createFileError(InputDWARFObj.getFileName(),
771                               createStringError(std::errc::invalid_argument,
772                                                 "Dwarf64 bits no supported"));
773  
774      uint32_t CIEId = Data.getU32(&InputOffset);
775      if (CIEId == 0xFFFFFFFF) {
776        // This is a CIE, store it.
777        StringRef CIEData = OrigFrameData.substr(EntryOffset, InitialLength + 4);
778        LocalCIES[EntryOffset] = CIEData;
779        // The -4 is to account for the CIEId we just read.
780        InputOffset += InitialLength - 4;
781        continue;
782      }
783  
784      uint64_t Loc = Data.getUnsigned(&InputOffset, SrcAddrSize);
785  
786      // Some compilers seem to emit frame info that doesn't start at
787      // the function entry point, thus we can't just lookup the address
788      // in the debug map. Use the AddressInfo's range map to see if the FDE
789      // describes something that we can relocate.
790      std::optional<AddressRangeValuePair> Range =
791          AllUnitsRanges.getRangeThatContains(Loc);
792      if (!Range) {
793        // The +4 is to account for the size of the InitialLength field itself.
794        InputOffset = EntryOffset + InitialLength + 4;
795        continue;
796      }
797  
798      // This is an FDE, and we have a mapping.
799      // Have we already emitted a corresponding CIE?
800      StringRef CIEData = LocalCIES[CIEId];
801      if (CIEData.empty())
802        return createFileError(
803            InputDWARFObj.getFileName(),
804            createStringError(std::errc::invalid_argument,
805                              "Inconsistent debug_frame content. Dropping."));
806  
807      uint64_t OffsetToCIERecord = OutSection.OS.tell();
808  
809      // Look if we already emitted a CIE that corresponds to the
810      // referenced one (the CIE data is the key of that lookup).
811      auto IteratorInserted =
812          EmittedCIEs.insert(std::make_pair(CIEData, OffsetToCIERecord));
813      OffsetToCIERecord = IteratorInserted.first->getValue();
814  
815      // Emit CIE for this ID if it is not emitted yet.
816      if (IteratorInserted.second)
817        OutSection.OS << CIEData;
818  
819      // Remember offset to the FDE record, so that we might update
820      // field referencing CIE record(containing OffsetToCIERecord),
821      // when final offsets are known. OffsetToCIERecord(which is written later)
822      // is local to the current .debug_frame section, it should be updated
823      // with final offset of the .debug_frame section.
824      OutSection.notePatch(
825          DebugOffsetPatch{OutSection.OS.tell() + 4, &OutSection, true});
826  
827      // Emit the FDE with updated address and CIE pointer.
828      // (4 + AddrSize) is the size of the CIEId + initial_location
829      // fields that will get reconstructed by emitFDE().
830      unsigned FDERemainingBytes = InitialLength - (4 + SrcAddrSize);
831      emitFDE(OffsetToCIERecord, SrcAddrSize, Loc + Range->Value,
832              OrigFrameData.substr(InputOffset, FDERemainingBytes), OutSection);
833      InputOffset += FDERemainingBytes;
834    }
835  
836    return Error::success();
837  }
838  
839  /// Emit a FDE into the debug_frame section. \p FDEBytes
840  /// contains the FDE data without the length, CIE offset and address
841  /// which will be replaced with the parameter values.
emitFDE(uint32_t CIEOffset,uint32_t AddrSize,uint64_t Address,StringRef FDEBytes,SectionDescriptor & Section)842  void DWARFLinkerImpl::LinkContext::emitFDE(uint32_t CIEOffset,
843                                             uint32_t AddrSize, uint64_t Address,
844                                             StringRef FDEBytes,
845                                             SectionDescriptor &Section) {
846    Section.emitIntVal(FDEBytes.size() + 4 + AddrSize, 4);
847    Section.emitIntVal(CIEOffset, 4);
848    Section.emitIntVal(Address, AddrSize);
849    Section.OS.write(FDEBytes.data(), FDEBytes.size());
850  }
851  
glueCompileUnitsAndWriteToTheOutput()852  void DWARFLinkerImpl::glueCompileUnitsAndWriteToTheOutput() {
853    if (!GlobalData.getTargetTriple().has_value())
854      return;
855    assert(SectionHandler);
856  
857    // Go through all object files, all compile units and assign
858    // offsets to them.
859    assignOffsets();
860  
861    // Patch size/offsets fields according to the assigned CU offsets.
862    patchOffsetsAndSizes();
863  
864    // Emit common sections and write debug tables from all object files/compile
865    // units into the resulting file.
866    emitCommonSectionsAndWriteCompileUnitsToTheOutput();
867  
868    if (ArtificialTypeUnit != nullptr)
869      ArtificialTypeUnit.reset();
870  
871    // Write common debug sections into the resulting file.
872    writeCommonSectionsToTheOutput();
873  
874    // Cleanup data.
875    cleanupDataAfterDWARFOutputIsWritten();
876  
877    if (GlobalData.getOptions().Statistics)
878      printStatistic();
879  }
880  
printStatistic()881  void DWARFLinkerImpl::printStatistic() {
882  
883    // For each object file map how many bytes were emitted.
884    StringMap<DebugInfoSize> SizeByObject;
885  
886    for (const std::unique_ptr<LinkContext> &Context : ObjectContexts) {
887      uint64_t AllDebugInfoSectionsSize = 0;
888  
889      for (std::unique_ptr<CompileUnit> &CU : Context->CompileUnits)
890        if (std::optional<SectionDescriptor *> DebugInfo =
891                CU->tryGetSectionDescriptor(DebugSectionKind::DebugInfo))
892          AllDebugInfoSectionsSize += (*DebugInfo)->getContents().size();
893  
894      SizeByObject[Context->InputDWARFFile.FileName].Input =
895          Context->OriginalDebugInfoSize;
896      SizeByObject[Context->InputDWARFFile.FileName].Output =
897          AllDebugInfoSectionsSize;
898    }
899  
900    // Create a vector sorted in descending order by output size.
901    std::vector<std::pair<StringRef, DebugInfoSize>> Sorted;
902    for (auto &E : SizeByObject)
903      Sorted.emplace_back(E.first(), E.second);
904    llvm::sort(Sorted, [](auto &LHS, auto &RHS) {
905      return LHS.second.Output > RHS.second.Output;
906    });
907  
908    auto ComputePercentange = [](int64_t Input, int64_t Output) -> float {
909      const float Difference = Output - Input;
910      const float Sum = Input + Output;
911      if (Sum == 0)
912        return 0;
913      return (Difference / (Sum / 2));
914    };
915  
916    int64_t InputTotal = 0;
917    int64_t OutputTotal = 0;
918    const char *FormatStr = "{0,-45} {1,10}b  {2,10}b {3,8:P}\n";
919  
920    // Print header.
921    outs() << ".debug_info section size (in bytes)\n";
922    outs() << "----------------------------------------------------------------"
923              "---------------\n";
924    outs() << "Filename                                           Object       "
925              "  dSYM   Change\n";
926    outs() << "----------------------------------------------------------------"
927              "---------------\n";
928  
929    // Print body.
930    for (auto &E : Sorted) {
931      InputTotal += E.second.Input;
932      OutputTotal += E.second.Output;
933      llvm::outs() << formatv(
934          FormatStr, sys::path::filename(E.first).take_back(45), E.second.Input,
935          E.second.Output, ComputePercentange(E.second.Input, E.second.Output));
936    }
937    // Print total and footer.
938    outs() << "----------------------------------------------------------------"
939              "---------------\n";
940    llvm::outs() << formatv(FormatStr, "Total", InputTotal, OutputTotal,
941                            ComputePercentange(InputTotal, OutputTotal));
942    outs() << "----------------------------------------------------------------"
943              "---------------\n\n";
944  }
945  
assignOffsets()946  void DWARFLinkerImpl::assignOffsets() {
947    llvm::parallel::TaskGroup TGroup;
948    TGroup.spawn([&]() { assignOffsetsToStrings(); });
949    TGroup.spawn([&]() { assignOffsetsToSections(); });
950  }
951  
assignOffsetsToStrings()952  void DWARFLinkerImpl::assignOffsetsToStrings() {
953    size_t CurDebugStrIndex = 1; // start from 1 to take into account zero entry.
954    uint64_t CurDebugStrOffset =
955        1; // start from 1 to take into account zero entry.
956    size_t CurDebugLineStrIndex = 0;
957    uint64_t CurDebugLineStrOffset = 0;
958  
959    // Enumerates all strings, add them into the DwarfStringPoolEntry map,
960    // assign offset and index to the string if it is not indexed yet.
961    forEachOutputString([&](StringDestinationKind Kind,
962                            const StringEntry *String) {
963      switch (Kind) {
964      case StringDestinationKind::DebugStr: {
965        DwarfStringPoolEntryWithExtString *Entry = DebugStrStrings.add(String);
966        assert(Entry != nullptr);
967  
968        if (!Entry->isIndexed()) {
969          Entry->Offset = CurDebugStrOffset;
970          CurDebugStrOffset += Entry->String.size() + 1;
971          Entry->Index = CurDebugStrIndex++;
972        }
973      } break;
974      case StringDestinationKind::DebugLineStr: {
975        DwarfStringPoolEntryWithExtString *Entry =
976            DebugLineStrStrings.add(String);
977        assert(Entry != nullptr);
978  
979        if (!Entry->isIndexed()) {
980          Entry->Offset = CurDebugLineStrOffset;
981          CurDebugLineStrOffset += Entry->String.size() + 1;
982          Entry->Index = CurDebugLineStrIndex++;
983        }
984      } break;
985      }
986    });
987  }
988  
assignOffsetsToSections()989  void DWARFLinkerImpl::assignOffsetsToSections() {
990    std::array<uint64_t, SectionKindsNum> SectionSizesAccumulator = {0};
991  
992    forEachObjectSectionsSet([&](OutputSections &UnitSections) {
993      UnitSections.assignSectionsOffsetAndAccumulateSize(SectionSizesAccumulator);
994    });
995  }
996  
forEachOutputString(function_ref<void (StringDestinationKind Kind,const StringEntry * String)> StringHandler)997  void DWARFLinkerImpl::forEachOutputString(
998      function_ref<void(StringDestinationKind Kind, const StringEntry *String)>
999          StringHandler) {
1000    // To save space we do not create any separate string table.
1001    // We use already allocated string patches and accelerator entries:
1002    // enumerate them in natural order and assign offsets.
1003    // ASSUMPTION: strings should be stored into .debug_str/.debug_line_str
1004    // sections in the same order as they were assigned offsets.
1005    forEachCompileUnit([&](CompileUnit *CU) {
1006      CU->forEach([&](SectionDescriptor &OutSection) {
1007        OutSection.ListDebugStrPatch.forEach([&](DebugStrPatch &Patch) {
1008          StringHandler(StringDestinationKind::DebugStr, Patch.String);
1009        });
1010  
1011        OutSection.ListDebugLineStrPatch.forEach([&](DebugLineStrPatch &Patch) {
1012          StringHandler(StringDestinationKind::DebugLineStr, Patch.String);
1013        });
1014      });
1015  
1016      CU->forEachAcceleratorRecord([&](DwarfUnit::AccelInfo &Info) {
1017        StringHandler(DebugStr, Info.String);
1018      });
1019    });
1020  
1021    if (ArtificialTypeUnit != nullptr) {
1022      ArtificialTypeUnit->forEach([&](SectionDescriptor &OutSection) {
1023        OutSection.ListDebugStrPatch.forEach([&](DebugStrPatch &Patch) {
1024          StringHandler(StringDestinationKind::DebugStr, Patch.String);
1025        });
1026  
1027        OutSection.ListDebugLineStrPatch.forEach([&](DebugLineStrPatch &Patch) {
1028          StringHandler(StringDestinationKind::DebugLineStr, Patch.String);
1029        });
1030  
1031        OutSection.ListDebugTypeStrPatch.forEach([&](DebugTypeStrPatch &Patch) {
1032          if (Patch.Die == nullptr)
1033            return;
1034  
1035          StringHandler(StringDestinationKind::DebugStr, Patch.String);
1036        });
1037  
1038        OutSection.ListDebugTypeLineStrPatch.forEach(
1039            [&](DebugTypeLineStrPatch &Patch) {
1040              if (Patch.Die == nullptr)
1041                return;
1042  
1043              StringHandler(StringDestinationKind::DebugStr, Patch.String);
1044            });
1045      });
1046    }
1047  }
1048  
forEachObjectSectionsSet(function_ref<void (OutputSections &)> SectionsSetHandler)1049  void DWARFLinkerImpl::forEachObjectSectionsSet(
1050      function_ref<void(OutputSections &)> SectionsSetHandler) {
1051    // Handle artificial type unit first.
1052    if (ArtificialTypeUnit != nullptr)
1053      SectionsSetHandler(*ArtificialTypeUnit);
1054  
1055    // Then all modules(before regular compilation units).
1056    for (const std::unique_ptr<LinkContext> &Context : ObjectContexts)
1057      for (LinkContext::RefModuleUnit &ModuleUnit : Context->ModulesCompileUnits)
1058        if (ModuleUnit.Unit->getStage() != CompileUnit::Stage::Skipped)
1059          SectionsSetHandler(*ModuleUnit.Unit);
1060  
1061    // Finally all compilation units.
1062    for (const std::unique_ptr<LinkContext> &Context : ObjectContexts) {
1063      // Handle object file common sections.
1064      SectionsSetHandler(*Context);
1065  
1066      // Handle compilation units.
1067      for (std::unique_ptr<CompileUnit> &CU : Context->CompileUnits)
1068        if (CU->getStage() != CompileUnit::Stage::Skipped)
1069          SectionsSetHandler(*CU);
1070    }
1071  }
1072  
forEachCompileAndTypeUnit(function_ref<void (DwarfUnit * CU)> UnitHandler)1073  void DWARFLinkerImpl::forEachCompileAndTypeUnit(
1074      function_ref<void(DwarfUnit *CU)> UnitHandler) {
1075    if (ArtificialTypeUnit != nullptr)
1076      UnitHandler(ArtificialTypeUnit.get());
1077  
1078    // Enumerate module units.
1079    for (const std::unique_ptr<LinkContext> &Context : ObjectContexts)
1080      for (LinkContext::RefModuleUnit &ModuleUnit : Context->ModulesCompileUnits)
1081        if (ModuleUnit.Unit->getStage() != CompileUnit::Stage::Skipped)
1082          UnitHandler(ModuleUnit.Unit.get());
1083  
1084    // Enumerate compile units.
1085    for (const std::unique_ptr<LinkContext> &Context : ObjectContexts)
1086      for (std::unique_ptr<CompileUnit> &CU : Context->CompileUnits)
1087        if (CU->getStage() != CompileUnit::Stage::Skipped)
1088          UnitHandler(CU.get());
1089  }
1090  
forEachCompileUnit(function_ref<void (CompileUnit * CU)> UnitHandler)1091  void DWARFLinkerImpl::forEachCompileUnit(
1092      function_ref<void(CompileUnit *CU)> UnitHandler) {
1093    // Enumerate module units.
1094    for (const std::unique_ptr<LinkContext> &Context : ObjectContexts)
1095      for (LinkContext::RefModuleUnit &ModuleUnit : Context->ModulesCompileUnits)
1096        if (ModuleUnit.Unit->getStage() != CompileUnit::Stage::Skipped)
1097          UnitHandler(ModuleUnit.Unit.get());
1098  
1099    // Enumerate compile units.
1100    for (const std::unique_ptr<LinkContext> &Context : ObjectContexts)
1101      for (std::unique_ptr<CompileUnit> &CU : Context->CompileUnits)
1102        if (CU->getStage() != CompileUnit::Stage::Skipped)
1103          UnitHandler(CU.get());
1104  }
1105  
patchOffsetsAndSizes()1106  void DWARFLinkerImpl::patchOffsetsAndSizes() {
1107    forEachObjectSectionsSet([&](OutputSections &SectionsSet) {
1108      SectionsSet.forEach([&](SectionDescriptor &OutSection) {
1109        SectionsSet.applyPatches(OutSection, DebugStrStrings, DebugLineStrStrings,
1110                                 ArtificialTypeUnit.get());
1111      });
1112    });
1113  }
1114  
emitCommonSectionsAndWriteCompileUnitsToTheOutput()1115  void DWARFLinkerImpl::emitCommonSectionsAndWriteCompileUnitsToTheOutput() {
1116    llvm::parallel::TaskGroup TG;
1117  
1118    // Create section descriptors ahead if they are not exist at the moment.
1119    // SectionDescriptors container is not thread safe. Thus we should be sure
1120    // that descriptors would not be created in following parallel tasks.
1121  
1122    CommonSections.getOrCreateSectionDescriptor(DebugSectionKind::DebugStr);
1123    CommonSections.getOrCreateSectionDescriptor(DebugSectionKind::DebugLineStr);
1124  
1125    if (llvm::is_contained(GlobalData.Options.AccelTables,
1126                           AccelTableKind::Apple)) {
1127      CommonSections.getOrCreateSectionDescriptor(DebugSectionKind::AppleNames);
1128      CommonSections.getOrCreateSectionDescriptor(
1129          DebugSectionKind::AppleNamespaces);
1130      CommonSections.getOrCreateSectionDescriptor(DebugSectionKind::AppleObjC);
1131      CommonSections.getOrCreateSectionDescriptor(DebugSectionKind::AppleTypes);
1132    }
1133  
1134    if (llvm::is_contained(GlobalData.Options.AccelTables,
1135                           AccelTableKind::DebugNames))
1136      CommonSections.getOrCreateSectionDescriptor(DebugSectionKind::DebugNames);
1137  
1138    // Emit .debug_str and .debug_line_str sections.
1139    TG.spawn([&]() { emitStringSections(); });
1140  
1141    if (llvm::is_contained(GlobalData.Options.AccelTables,
1142                           AccelTableKind::Apple)) {
1143      // Emit apple accelerator sections.
1144      TG.spawn([&]() {
1145        emitAppleAcceleratorSections((*GlobalData.getTargetTriple()).get());
1146      });
1147    }
1148  
1149    if (llvm::is_contained(GlobalData.Options.AccelTables,
1150                           AccelTableKind::DebugNames)) {
1151      // Emit .debug_names section.
1152      TG.spawn([&]() {
1153        emitDWARFv5DebugNamesSection((*GlobalData.getTargetTriple()).get());
1154      });
1155    }
1156  
1157    // Write compile units to the output file.
1158    TG.spawn([&]() { writeCompileUnitsToTheOutput(); });
1159  }
1160  
emitStringSections()1161  void DWARFLinkerImpl::emitStringSections() {
1162    uint64_t DebugStrNextOffset = 0;
1163    uint64_t DebugLineStrNextOffset = 0;
1164  
1165    // Emit zero length string. Accelerator tables does not work correctly
1166    // if the first string is not zero length string.
1167    CommonSections.getSectionDescriptor(DebugSectionKind::DebugStr)
1168        .emitInplaceString("");
1169    DebugStrNextOffset++;
1170  
1171    forEachOutputString(
1172        [&](StringDestinationKind Kind, const StringEntry *String) {
1173          switch (Kind) {
1174          case StringDestinationKind::DebugStr: {
1175            DwarfStringPoolEntryWithExtString *StringToEmit =
1176                DebugStrStrings.getExistingEntry(String);
1177            assert(StringToEmit->isIndexed());
1178  
1179            // Strings may be repeated. Use accumulated DebugStrNextOffset
1180            // to understand whether corresponding string is already emitted.
1181            // Skip string if its offset less than accumulated offset.
1182            if (StringToEmit->Offset >= DebugStrNextOffset) {
1183              DebugStrNextOffset =
1184                  StringToEmit->Offset + StringToEmit->String.size() + 1;
1185              // Emit the string itself.
1186              CommonSections.getSectionDescriptor(DebugSectionKind::DebugStr)
1187                  .emitInplaceString(StringToEmit->String);
1188            }
1189          } break;
1190          case StringDestinationKind::DebugLineStr: {
1191            DwarfStringPoolEntryWithExtString *StringToEmit =
1192                DebugLineStrStrings.getExistingEntry(String);
1193            assert(StringToEmit->isIndexed());
1194  
1195            // Strings may be repeated. Use accumulated DebugLineStrStrings
1196            // to understand whether corresponding string is already emitted.
1197            // Skip string if its offset less than accumulated offset.
1198            if (StringToEmit->Offset >= DebugLineStrNextOffset) {
1199              DebugLineStrNextOffset =
1200                  StringToEmit->Offset + StringToEmit->String.size() + 1;
1201              // Emit the string itself.
1202              CommonSections.getSectionDescriptor(DebugSectionKind::DebugLineStr)
1203                  .emitInplaceString(StringToEmit->String);
1204            }
1205          } break;
1206          }
1207        });
1208  }
1209  
emitAppleAcceleratorSections(const Triple & TargetTriple)1210  void DWARFLinkerImpl::emitAppleAcceleratorSections(const Triple &TargetTriple) {
1211    AccelTable<AppleAccelTableStaticOffsetData> AppleNamespaces;
1212    AccelTable<AppleAccelTableStaticOffsetData> AppleNames;
1213    AccelTable<AppleAccelTableStaticOffsetData> AppleObjC;
1214    AccelTable<AppleAccelTableStaticTypeData> AppleTypes;
1215  
1216    forEachCompileAndTypeUnit([&](DwarfUnit *CU) {
1217      CU->forEachAcceleratorRecord([&](const DwarfUnit::AccelInfo &Info) {
1218        uint64_t OutOffset = Info.OutOffset;
1219        switch (Info.Type) {
1220        case DwarfUnit::AccelType::None: {
1221          llvm_unreachable("Unknown accelerator record");
1222        } break;
1223        case DwarfUnit::AccelType::Namespace: {
1224          AppleNamespaces.addName(
1225              *DebugStrStrings.getExistingEntry(Info.String),
1226              CU->getSectionDescriptor(DebugSectionKind::DebugInfo).StartOffset +
1227                  OutOffset);
1228        } break;
1229        case DwarfUnit::AccelType::Name: {
1230          AppleNames.addName(
1231              *DebugStrStrings.getExistingEntry(Info.String),
1232              CU->getSectionDescriptor(DebugSectionKind::DebugInfo).StartOffset +
1233                  OutOffset);
1234        } break;
1235        case DwarfUnit::AccelType::ObjC: {
1236          AppleObjC.addName(
1237              *DebugStrStrings.getExistingEntry(Info.String),
1238              CU->getSectionDescriptor(DebugSectionKind::DebugInfo).StartOffset +
1239                  OutOffset);
1240        } break;
1241        case DwarfUnit::AccelType::Type: {
1242          AppleTypes.addName(
1243              *DebugStrStrings.getExistingEntry(Info.String),
1244              CU->getSectionDescriptor(DebugSectionKind::DebugInfo).StartOffset +
1245                  OutOffset,
1246              Info.Tag,
1247              Info.ObjcClassImplementation ? dwarf::DW_FLAG_type_implementation
1248                                           : 0,
1249              Info.QualifiedNameHash);
1250        } break;
1251        }
1252      });
1253    });
1254  
1255    {
1256      // FIXME: we use AsmPrinter to emit accelerator sections.
1257      // It might be beneficial to directly emit accelerator data
1258      // to the raw_svector_ostream.
1259      SectionDescriptor &OutSection =
1260          CommonSections.getSectionDescriptor(DebugSectionKind::AppleNamespaces);
1261      DwarfEmitterImpl Emitter(DWARFLinker::OutputFileType::Object,
1262                               OutSection.OS);
1263      if (Error Err = Emitter.init(TargetTriple, "__DWARF")) {
1264        consumeError(std::move(Err));
1265        return;
1266      }
1267  
1268      // Emit table.
1269      Emitter.emitAppleNamespaces(AppleNamespaces);
1270      Emitter.finish();
1271  
1272      // Set start offset and size for output section.
1273      OutSection.setSizesForSectionCreatedByAsmPrinter();
1274    }
1275  
1276    {
1277      // FIXME: we use AsmPrinter to emit accelerator sections.
1278      // It might be beneficial to directly emit accelerator data
1279      // to the raw_svector_ostream.
1280      SectionDescriptor &OutSection =
1281          CommonSections.getSectionDescriptor(DebugSectionKind::AppleNames);
1282      DwarfEmitterImpl Emitter(DWARFLinker::OutputFileType::Object,
1283                               OutSection.OS);
1284      if (Error Err = Emitter.init(TargetTriple, "__DWARF")) {
1285        consumeError(std::move(Err));
1286        return;
1287      }
1288  
1289      // Emit table.
1290      Emitter.emitAppleNames(AppleNames);
1291      Emitter.finish();
1292  
1293      // Set start offset ans size for output section.
1294      OutSection.setSizesForSectionCreatedByAsmPrinter();
1295    }
1296  
1297    {
1298      // FIXME: we use AsmPrinter to emit accelerator sections.
1299      // It might be beneficial to directly emit accelerator data
1300      // to the raw_svector_ostream.
1301      SectionDescriptor &OutSection =
1302          CommonSections.getSectionDescriptor(DebugSectionKind::AppleObjC);
1303      DwarfEmitterImpl Emitter(DWARFLinker::OutputFileType::Object,
1304                               OutSection.OS);
1305      if (Error Err = Emitter.init(TargetTriple, "__DWARF")) {
1306        consumeError(std::move(Err));
1307        return;
1308      }
1309  
1310      // Emit table.
1311      Emitter.emitAppleObjc(AppleObjC);
1312      Emitter.finish();
1313  
1314      // Set start offset ans size for output section.
1315      OutSection.setSizesForSectionCreatedByAsmPrinter();
1316    }
1317  
1318    {
1319      // FIXME: we use AsmPrinter to emit accelerator sections.
1320      // It might be beneficial to directly emit accelerator data
1321      // to the raw_svector_ostream.
1322      SectionDescriptor &OutSection =
1323          CommonSections.getSectionDescriptor(DebugSectionKind::AppleTypes);
1324      DwarfEmitterImpl Emitter(DWARFLinker::OutputFileType::Object,
1325                               OutSection.OS);
1326      if (Error Err = Emitter.init(TargetTriple, "__DWARF")) {
1327        consumeError(std::move(Err));
1328        return;
1329      }
1330  
1331      // Emit table.
1332      Emitter.emitAppleTypes(AppleTypes);
1333      Emitter.finish();
1334  
1335      // Set start offset ans size for output section.
1336      OutSection.setSizesForSectionCreatedByAsmPrinter();
1337    }
1338  }
1339  
emitDWARFv5DebugNamesSection(const Triple & TargetTriple)1340  void DWARFLinkerImpl::emitDWARFv5DebugNamesSection(const Triple &TargetTriple) {
1341    std::unique_ptr<DWARF5AccelTable> DebugNames;
1342  
1343    DebugNamesUnitsOffsets CompUnits;
1344    CompUnitIDToIdx CUidToIdx;
1345  
1346    unsigned Id = 0;
1347  
1348    forEachCompileAndTypeUnit([&](DwarfUnit *CU) {
1349      bool HasRecords = false;
1350      CU->forEachAcceleratorRecord([&](const DwarfUnit::AccelInfo &Info) {
1351        if (DebugNames == nullptr)
1352          DebugNames = std::make_unique<DWARF5AccelTable>();
1353  
1354        HasRecords = true;
1355        switch (Info.Type) {
1356        case DwarfUnit::AccelType::Name:
1357        case DwarfUnit::AccelType::Namespace:
1358        case DwarfUnit::AccelType::Type: {
1359          DebugNames->addName(*DebugStrStrings.getExistingEntry(Info.String),
1360                              Info.OutOffset, std::nullopt /*ParentDIEOffset*/,
1361                              Info.Tag, CU->getUniqueID(),
1362                              CU->getTag() == dwarf::DW_TAG_type_unit);
1363        } break;
1364  
1365        default:
1366          break; // Nothing to do.
1367        };
1368      });
1369  
1370      if (HasRecords) {
1371        CompUnits.push_back(
1372            CU->getOrCreateSectionDescriptor(DebugSectionKind::DebugInfo)
1373                .StartOffset);
1374        CUidToIdx[CU->getUniqueID()] = Id++;
1375      }
1376    });
1377  
1378    if (DebugNames != nullptr) {
1379      // FIXME: we use AsmPrinter to emit accelerator sections.
1380      // It might be beneficial to directly emit accelerator data
1381      // to the raw_svector_ostream.
1382      SectionDescriptor &OutSection =
1383          CommonSections.getSectionDescriptor(DebugSectionKind::DebugNames);
1384      DwarfEmitterImpl Emitter(DWARFLinker::OutputFileType::Object,
1385                               OutSection.OS);
1386      if (Error Err = Emitter.init(TargetTriple, "__DWARF")) {
1387        consumeError(std::move(Err));
1388        return;
1389      }
1390  
1391      // Emit table.
1392      Emitter.emitDebugNames(*DebugNames, CompUnits, CUidToIdx);
1393      Emitter.finish();
1394  
1395      // Set start offset ans size for output section.
1396      OutSection.setSizesForSectionCreatedByAsmPrinter();
1397    }
1398  }
1399  
cleanupDataAfterDWARFOutputIsWritten()1400  void DWARFLinkerImpl::cleanupDataAfterDWARFOutputIsWritten() {
1401    GlobalData.getStringPool().clear();
1402    DebugStrStrings.clear();
1403    DebugLineStrStrings.clear();
1404  }
1405  
writeCompileUnitsToTheOutput()1406  void DWARFLinkerImpl::writeCompileUnitsToTheOutput() {
1407    // Enumerate all sections and store them into the final emitter.
1408    forEachObjectSectionsSet([&](OutputSections &Sections) {
1409      Sections.forEach([&](std::shared_ptr<SectionDescriptor> OutSection) {
1410        // Emit section content.
1411        SectionHandler(OutSection);
1412      });
1413    });
1414  }
1415  
writeCommonSectionsToTheOutput()1416  void DWARFLinkerImpl::writeCommonSectionsToTheOutput() {
1417    CommonSections.forEach([&](std::shared_ptr<SectionDescriptor> OutSection) {
1418      SectionHandler(OutSection);
1419    });
1420  }
1421