diff --git a/llvm/lib/DWARFLinker/DWARFLinker.cpp b/llvm/lib/DWARFLinker/DWARFLinker.cpp --- a/llvm/lib/DWARFLinker/DWARFLinker.cpp +++ b/llvm/lib/DWARFLinker/DWARFLinker.cpp @@ -242,9 +242,72 @@ } } +/// The distinct types of work performed by the work loop in +/// analyzeContextInfo. +enum class ContextWorklistItemType : uint8_t { + AnalyzeContextInfo, + UpdateChildPruning, + UpdatePruning, +}; + +/// This class represents an item in the work list. The type defines what kind +/// of work needs to be performed when processing the current item. Everything +/// but the Type and Die fields are optional based on the type. +struct ContextWorklistItem { + DWARFDie Die; + unsigned ParentIdx; + union { + CompileUnit::DIEInfo *OtherInfo; + DeclContext *Context; + }; + ContextWorklistItemType Type; + bool InImportedModule; + + ContextWorklistItem(DWARFDie Die, ContextWorklistItemType T, + CompileUnit::DIEInfo *OtherInfo = nullptr) + : Die(Die), ParentIdx(0), OtherInfo(OtherInfo), Type(T), + InImportedModule(false) {} + + ContextWorklistItem(DWARFDie Die, DeclContext *Context, unsigned ParentIdx, + bool InImportedModule) + : Die(Die), ParentIdx(ParentIdx), Context(Context), + Type(ContextWorklistItemType::AnalyzeContextInfo), + InImportedModule(InImportedModule) {} +}; + +static bool updatePruning(const DWARFDie &Die, CompileUnit &CU, + uint64_t ModulesEndOffset) { + CompileUnit::DIEInfo &Info = CU.getInfo(Die); + + // Prune this DIE if it is either a forward declaration inside a + // DW_TAG_module or a DW_TAG_module that contains nothing but + // forward declarations. + Info.Prune &= (Die.getTag() == dwarf::DW_TAG_module) || + (isTypeTag(Die.getTag()) && + dwarf::toUnsigned(Die.find(dwarf::DW_AT_declaration), 0)); + + // Only prune forward declarations inside a DW_TAG_module for which a + // definition exists elsewhere. + if (ModulesEndOffset == 0) + Info.Prune &= Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset(); + else + Info.Prune &= Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset() > 0 && + Info.Ctxt->getCanonicalDIEOffset() <= ModulesEndOffset; + + return Info.Prune; +} + +static void updateChildPruning(const DWARFDie &Die, CompileUnit &CU, + CompileUnit::DIEInfo &ChildInfo) { + CompileUnit::DIEInfo &Info = CU.getInfo(Die); + Info.Prune &= ChildInfo.Prune; +} + /// Recursive helper to build the global DeclContext information and /// gather the child->parent relationships in the original compile unit. /// +/// This function uses the same work list approach as lookForDIEsToKeep. +/// /// \return true when this DIE and all of its children are only /// forward declarations to types defined in external clang modules /// (i.e., forward declarations that are children of a DW_TAG_module). @@ -255,67 +318,78 @@ swiftInterfacesMap *ParseableSwiftInterfaces, std::function ReportWarning, bool InImportedModule = false) { - unsigned MyIdx = CU.getOrigUnit().getDIEIndex(DIE); - CompileUnit::DIEInfo &Info = CU.getInfo(MyIdx); + // LIFO work list. + std::vector Worklist; + Worklist.emplace_back(DIE, CurrentDeclContext, ParentIdx, InImportedModule); - // Clang imposes an ODR on modules(!) regardless of the language: - // "The module-id should consist of only a single identifier, - // which provides the name of the module being defined. Each - // module shall have a single definition." - // - // This does not extend to the types inside the modules: - // "[I]n C, this implies that if two structs are defined in - // different submodules with the same name, those two types are - // distinct types (but may be compatible types if their - // definitions match)." - // - // We treat non-C++ modules like namespaces for this reason. - if (DIE.getTag() == dwarf::DW_TAG_module && ParentIdx == 0 && - dwarf::toString(DIE.find(dwarf::DW_AT_name), "") != - CU.getClangModuleName()) { - InImportedModule = true; - analyzeImportedModule(DIE, CU, ParseableSwiftInterfaces, ReportWarning); - } - - Info.ParentIdx = ParentIdx; - bool InClangModule = CU.isClangModule() || InImportedModule; - if (CU.hasODR() || InClangModule) { - if (CurrentDeclContext) { - auto PtrInvalidPair = Contexts.getChildDeclContext( - *CurrentDeclContext, DIE, CU, StringPool, InClangModule); - CurrentDeclContext = PtrInvalidPair.getPointer(); - Info.Ctxt = - PtrInvalidPair.getInt() ? nullptr : PtrInvalidPair.getPointer(); - if (Info.Ctxt) - Info.Ctxt->setDefinedInClangModule(InClangModule); - } else - Info.Ctxt = CurrentDeclContext = nullptr; - } + while (!Worklist.empty()) { + ContextWorklistItem Current = Worklist.back(); + Worklist.pop_back(); - Info.Prune = InImportedModule; - if (DIE.hasChildren()) - for (auto Child : DIE.children()) - Info.Prune &= analyzeContextInfo(Child, MyIdx, CU, CurrentDeclContext, - StringPool, Contexts, ModulesEndOffset, - ParseableSwiftInterfaces, ReportWarning, - InImportedModule); + switch (Current.Type) { + case ContextWorklistItemType::UpdatePruning: + updatePruning(Current.Die, CU, ModulesEndOffset); + continue; + case ContextWorklistItemType::UpdateChildPruning: + updateChildPruning(Current.Die, CU, *Current.OtherInfo); + continue; + case ContextWorklistItemType::AnalyzeContextInfo: + break; + } - // Prune this DIE if it is either a forward declaration inside a - // DW_TAG_module or a DW_TAG_module that contains nothing but - // forward declarations. - Info.Prune &= (DIE.getTag() == dwarf::DW_TAG_module) || - (isTypeTag(DIE.getTag()) && - dwarf::toUnsigned(DIE.find(dwarf::DW_AT_declaration), 0)); + unsigned Idx = CU.getOrigUnit().getDIEIndex(Current.Die); + CompileUnit::DIEInfo &Info = CU.getInfo(Idx); + + // Clang imposes an ODR on modules(!) regardless of the language: + // "The module-id should consist of only a single identifier, + // which provides the name of the module being defined. Each + // module shall have a single definition." + // + // This does not extend to the types inside the modules: + // "[I]n C, this implies that if two structs are defined in + // different submodules with the same name, those two types are + // distinct types (but may be compatible types if their + // definitions match)." + // + // We treat non-C++ modules like namespaces for this reason. + if (Current.Die.getTag() == dwarf::DW_TAG_module && + Current.ParentIdx == 0 && + dwarf::toString(Current.Die.find(dwarf::DW_AT_name), "") != + CU.getClangModuleName()) { + Current.InImportedModule = true; + analyzeImportedModule(Current.Die, CU, ParseableSwiftInterfaces, + ReportWarning); + } - // Only prune forward declarations inside a DW_TAG_module for which a - // definition exists elsewhere. - if (ModulesEndOffset == 0) - Info.Prune &= Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset(); - else - Info.Prune &= Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset() > 0 && - Info.Ctxt->getCanonicalDIEOffset() <= ModulesEndOffset; + Info.ParentIdx = Current.ParentIdx; + bool InClangModule = CU.isClangModule() || Current.InImportedModule; + if (CU.hasODR() || InClangModule) { + if (Current.Context) { + auto PtrInvalidPair = Contexts.getChildDeclContext( + *Current.Context, Current.Die, CU, StringPool, InClangModule); + Current.Context = PtrInvalidPair.getPointer(); + Info.Ctxt = + PtrInvalidPair.getInt() ? nullptr : PtrInvalidPair.getPointer(); + if (Info.Ctxt) + Info.Ctxt->setDefinedInClangModule(InClangModule); + } else + Info.Ctxt = Current.Context = nullptr; + } - return Info.Prune; + Info.Prune = Current.InImportedModule; + // Add children in reverse order to the worklist to effectively process + // them in order. + Worklist.emplace_back(Current.Die, ContextWorklistItemType::UpdatePruning); + for (auto Child : reverse(Current.Die.children())) { + CompileUnit::DIEInfo &ChildInfo = CU.getInfo(Child); + Worklist.emplace_back( + Current.Die, ContextWorklistItemType::UpdateChildPruning, &ChildInfo); + Worklist.emplace_back(Child, Current.Context, Idx, + Current.InImportedModule); + } + } + + return CU.getInfo(DIE).Prune; } static bool dieNeedsChildrenToBeMeaningful(uint32_t Tag) {