diff --git a/llvm/tools/dsymutil/DwarfLinker.h b/llvm/tools/dsymutil/DwarfLinker.h --- a/llvm/tools/dsymutil/DwarfLinker.h +++ b/llvm/tools/dsymutil/DwarfLinker.h @@ -65,6 +65,15 @@ void reportWarning(const Twine &Warning, const DebugMapObject &DMO, const DWARFDie *DIE = nullptr) const; + /// Flags passed to DwarfLinker::lookForDIEsToKeep + enum TraversalFlags { + TF_Keep = 1 << 0, ///< Mark the traversed DIEs as kept. + TF_InFunctionScope = 1 << 1, ///< Current scope is a function scope. + TF_DependencyWalk = 1 << 2, ///< Walking the dependencies of a kept DIE. + TF_ParentWalk = 1 << 3, ///< Walking up the parents of a kept DIE. + TF_ODR = 1 << 4, ///< Use the ODR while keeping dependents. + TF_SkipPC = 1 << 5, ///< Skip all location attributes. + }; private: /// Remembers the oldest and newest DWARF version we've seen in a unit. void updateDwarfVersion(unsigned Version) { @@ -215,15 +224,6 @@ unsigned &UnitID, bool IsLittleEndian, unsigned Indent = 0, bool Quiet = false); - /// Flags passed to DwarfLinker::lookForDIEsToKeep - enum TraversalFlags { - TF_Keep = 1 << 0, ///< Mark the traversed DIEs as kept. - TF_InFunctionScope = 1 << 1, ///< Current scope is a function scope. - TF_DependencyWalk = 1 << 2, ///< Walking the dependencies of a kept DIE. - TF_ParentWalk = 1 << 3, ///< Walking up the parents of a kept DIE. - TF_ODR = 1 << 4, ///< Use the ODR while keeping dependents. - TF_SkipPC = 1 << 5, ///< Skip all location attributes. - }; /// Mark the passed DIE as well as all the ones it depends on as kept. void keepDIEAndDependencies(RelocationManager &RelocMgr, RangesTy &Ranges, diff --git a/llvm/tools/dsymutil/DwarfLinker.cpp b/llvm/tools/dsymutil/DwarfLinker.cpp --- a/llvm/tools/dsymutil/DwarfLinker.cpp +++ b/llvm/tools/dsymutil/DwarfLinker.cpp @@ -760,129 +760,70 @@ return Flags; } -/// Mark the passed DIE as well as all the ones it depends on -/// as kept. -/// -/// This function is called by lookForDIEsToKeep on DIEs that are -/// newly discovered to be needed in the link. It recursively calls -/// back to lookForDIEsToKeep while adding TF_DependencyWalk to the -/// TraversalFlags to inform it that it's not doing the primary DIE -/// tree walk. -void DwarfLinker::keepDIEAndDependencies( - RelocationManager &RelocMgr, RangesTy &Ranges, const UnitListTy &Units, - const DWARFDie &Die, CompileUnit::DIEInfo &MyInfo, - const DebugMapObject &DMO, CompileUnit &CU, bool UseODR) { - DWARFUnit &Unit = CU.getOrigUnit(); - MyInfo.Keep = true; - - // We're looking for incomplete types. - MyInfo.Incomplete = Die.getTag() != dwarf::DW_TAG_subprogram && - Die.getTag() != dwarf::DW_TAG_member && - dwarf::toUnsigned(Die.find(dwarf::DW_AT_declaration), 0); - - // First mark all the parent chain as kept. - unsigned AncestorIdx = MyInfo.ParentIdx; - while (!CU.getInfo(AncestorIdx).Keep) { - unsigned ODRFlag = UseODR ? TF_ODR : 0; - lookForDIEsToKeep(RelocMgr, Ranges, Units, Unit.getDIEAtIndex(AncestorIdx), - DMO, CU, - TF_ParentWalk | TF_Keep | TF_DependencyWalk | ODRFlag); - AncestorIdx = CU.getInfo(AncestorIdx).ParentIdx; - } - - // Then we need to mark all the DIEs referenced by this DIE's - // attributes as kept. - DWARFDataExtractor Data = Unit.getDebugInfoExtractor(); - const auto *Abbrev = Die.getAbbreviationDeclarationPtr(); - uint64_t Offset = Die.getOffset() + getULEB128Size(Abbrev->getCode()); - - // Mark all DIEs referenced through attributes as kept. - for (const auto &AttrSpec : Abbrev->attributes()) { - DWARFFormValue Val(AttrSpec.Form); - if (!Val.isFormClass(DWARFFormValue::FC_Reference) || - AttrSpec.Attr == dwarf::DW_AT_sibling) { - DWARFFormValue::skipValue(AttrSpec.Form, Data, &Offset, - Unit.getFormParams()); - continue; - } - - Val.extractValue(Data, &Offset, Unit.getFormParams(), &Unit); - CompileUnit *ReferencedCU; - if (auto RefDie = - resolveDIEReference(*this, DMO, Units, Val, Die, ReferencedCU)) { - uint32_t RefIdx = ReferencedCU->getOrigUnit().getDIEIndex(RefDie); - CompileUnit::DIEInfo &Info = ReferencedCU->getInfo(RefIdx); - bool IsModuleRef = Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset() && - Info.Ctxt->isDefinedInClangModule(); - // If the referenced DIE has a DeclContext that has already been - // emitted, then do not keep the one in this CU. We'll link to - // the canonical DIE in cloneDieReferenceAttribute. - // FIXME: compatibility with dsymutil-classic. UseODR shouldn't - // be necessary and could be advantageously replaced by - // ReferencedCU->hasODR() && CU.hasODR(). - // FIXME: compatibility with dsymutil-classic. There is no - // reason not to unique ref_addr references. - if (AttrSpec.Form != dwarf::DW_FORM_ref_addr && (UseODR || IsModuleRef) && - Info.Ctxt && - Info.Ctxt != ReferencedCU->getInfo(Info.ParentIdx).Ctxt && - Info.Ctxt->getCanonicalDIEOffset() && isODRAttribute(AttrSpec.Attr)) - continue; - - // Keep a module forward declaration if there is no definition. - if (!(isODRAttribute(AttrSpec.Attr) && Info.Ctxt && - Info.Ctxt->getCanonicalDIEOffset())) - Info.Prune = false; - - unsigned ODRFlag = UseODR ? TF_ODR : 0; - lookForDIEsToKeep(RelocMgr, Ranges, Units, RefDie, DMO, *ReferencedCU, - TF_Keep | TF_DependencyWalk | ODRFlag); - - // The incomplete property is propagated if the current DIE is complete - // but references an incomplete DIE. - if (Info.Incomplete && !MyInfo.Incomplete && - (Die.getTag() == dwarf::DW_TAG_typedef || - Die.getTag() == dwarf::DW_TAG_member || - Die.getTag() == dwarf::DW_TAG_reference_type || - Die.getTag() == dwarf::DW_TAG_ptr_to_member_type || - Die.getTag() == dwarf::DW_TAG_pointer_type)) - MyInfo.Incomplete = true; - } - } -} - namespace { -/// This class represents an item in the work list. In addition to it's obvious -/// purpose of representing the state associated with a particular run of the -/// work loop, it also serves as a marker to indicate that we should run the -/// "continuation" code. -/// -/// Originally, the latter was lambda which allowed arbitrary code to be run. -/// Because we always need to run the exact same code, it made more sense to -/// use a boolean and repurpose the already existing DIE field. +/// The distinct types of work performed by the work loop. +enum class WorklistItemType { + LookForDIEsToKeep, + LookForChildDIEsToKeep, + UpdateChildIncompleteness, + UpdateRefIncompleteness, +}; + +/// 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. The flags +/// and info fields are optional based on the type. struct WorklistItem { + WorklistItemType Type; DWARFDie Die; + CompileUnit &CU; unsigned Flags; - bool IsContinuation; - CompileUnit::DIEInfo *ChildInfo = nullptr; + CompileUnit::DIEInfo *OtherInfo = nullptr; - /// Construct a classic worklist item. - WorklistItem(DWARFDie Die, unsigned Flags) - : Die(Die), Flags(Flags), IsContinuation(false){}; + WorklistItem(DWARFDie Die, CompileUnit &CU, unsigned Flags, + WorklistItemType T = WorklistItemType::LookForDIEsToKeep) + : Type(T), Die(Die), CU(CU), Flags(Flags){}; - /// Creates a continuation marker. - WorklistItem(DWARFDie Die) : Die(Die), IsContinuation(true){}; + WorklistItem(DWARFDie Die, CompileUnit &CU, WorklistItemType T, + CompileUnit::DIEInfo *OtherInfo = nullptr) + : Type(T), Die(Die), CU(CU), OtherInfo(OtherInfo){}; }; } // namespace -// Helper that updates the completeness of the current DIE. It depends on the -// fact that the incompletness of its children is already computed. -static void updateIncompleteness(const DWARFDie &Die, - CompileUnit::DIEInfo &ChildInfo, - CompileUnit &CU) { - // Only propagate incomplete members. - if (Die.getTag() != dwarf::DW_TAG_structure_type && - Die.getTag() != dwarf::DW_TAG_class_type) +/// Helper that updates the completeness of the current DIE based on the +/// completeness of one of its children. It depends on the incompleteness of +/// the children already being computed. +static void updateChildIncompleteness(const DWARFDie &Die, CompileUnit &CU, + CompileUnit::DIEInfo &ChildInfo) { + switch (Die.getTag()) { + case dwarf::DW_TAG_structure_type: + case dwarf::DW_TAG_class_type: + break; + default: + return; + } + + unsigned Idx = CU.getOrigUnit().getDIEIndex(Die); + CompileUnit::DIEInfo &MyInfo = CU.getInfo(Idx); + + if (ChildInfo.Incomplete || ChildInfo.Prune) + MyInfo.Incomplete = true; +} + +/// Helper that updates the completeness of the current DIE based on the +/// completeness of the DIEs referencing it. It depends on the incompleteness +/// of the referencing DIE already being computed. +static void updateRefIncompleteness(const DWARFDie &Die, CompileUnit &CU, + CompileUnit::DIEInfo &RefInfo) { + switch (Die.getTag()) { + case dwarf::DW_TAG_typedef: + case dwarf::DW_TAG_member: + case dwarf::DW_TAG_reference_type: + case dwarf::DW_TAG_ptr_to_member_type: + case dwarf::DW_TAG_pointer_type: + break; + default: return; + } unsigned Idx = CU.getOrigUnit().getDIEIndex(Die); CompileUnit::DIEInfo &MyInfo = CU.getInfo(Idx); @@ -890,49 +831,81 @@ if (MyInfo.Incomplete) return; - if (ChildInfo.Incomplete || ChildInfo.Prune) + if (RefInfo.Incomplete) MyInfo.Incomplete = true; } -/// Recursively walk the \p DIE tree and look for DIEs to -/// keep. Store that information in \p CU's DIEInfo. +static void lookForChildDIEsToKeep(const DWARFDie &Die, CompileUnit &CU, + unsigned Flags, + SmallVectorImpl &Worklist) { + // The TF_ParentWalk flag tells us that we are currently walking up the + // parent chain of a required DIE, and we don't want to mark all the children + // of the parents as kept (consider for example a DW_TAG_namespace node in + // the parent chain). There are however a set of DIE types for which we want + // to ignore that directive and still walk their children. + if (dieNeedsChildrenToBeMeaningful(Die.getTag())) + Flags &= ~DwarfLinker::TF_ParentWalk; + + if (!Die.hasChildren() || (Flags & DwarfLinker::TF_ParentWalk)) + return; + + // Add children in reverse order to the worklist to effectively process them + // in order. + for (auto Child : reverse(Die.children())) { + // Add a worklist item before every child to calculate incompleteness right + // after the current child is processed. + unsigned Idx = CU.getOrigUnit().getDIEIndex(Child); + CompileUnit::DIEInfo &ChildInfo = CU.getInfo(Idx); + Worklist.emplace_back(Die, CU, WorklistItemType::UpdateChildIncompleteness, + &ChildInfo); + Worklist.emplace_back(Child, CU, Flags); + } +} + +/// Recursively walk the \p DIE tree and look for DIEs to keep. Store that +/// information in \p CU's DIEInfo. +/// +/// This function is the entry point of the DIE selection algorithm. It is +/// expected to walk the DIE tree in file order and (though the mediation of +/// its helper) call hasValidRelocation() on each DIE that might be a 'root +/// DIE' (See DwarfLinker class comment). /// -/// This function is the entry point of the DIE selection -/// algorithm. It is expected to walk the DIE tree in file order and -/// (though the mediation of its helper) call hasValidRelocation() on -/// each DIE that might be a 'root DIE' (See DwarfLinker class -/// comment). -/// While walking the dependencies of root DIEs, this function is -/// also called, but during these dependency walks the file order is -/// not respected. The TF_DependencyWalk flag tells us which kind of -/// traversal we are currently doing. +/// While walking the dependencies of root DIEs, this function is also called, +/// but during these dependency walks the file order is not respected. The +/// TF_DependencyWalk flag tells us which kind of traversal we are currently +/// doing. /// /// The return value indicates whether the DIE is incomplete. void DwarfLinker::lookForDIEsToKeep(RelocationManager &RelocMgr, RangesTy &Ranges, const UnitListTy &Units, const DWARFDie &Die, - const DebugMapObject &DMO, CompileUnit &CU, + const DebugMapObject &DMO, CompileUnit &Cu, unsigned Flags) { // LIFO work list. SmallVector Worklist; - Worklist.emplace_back(Die, Flags); + Worklist.emplace_back(Die, Cu, Flags); while (!Worklist.empty()) { WorklistItem Current = Worklist.back(); Worklist.pop_back(); - if (Current.IsContinuation) { - updateIncompleteness(Current.Die, *Current.ChildInfo, CU); + // Look at the worklist type to decide what kind of work to perform. + switch (Current.Type) { + case WorklistItemType::UpdateChildIncompleteness: + updateChildIncompleteness(Current.Die, Current.CU, *Current.OtherInfo); continue; + case WorklistItemType::UpdateRefIncompleteness: + updateRefIncompleteness(Current.Die, Current.CU, *Current.OtherInfo); + continue; + case WorklistItemType::LookForChildDIEsToKeep: + lookForChildDIEsToKeep(Current.Die, Current.CU, Current.Flags, Worklist); + continue; + case WorklistItemType::LookForDIEsToKeep: + break; } - unsigned Idx = CU.getOrigUnit().getDIEIndex(Current.Die); - CompileUnit::DIEInfo &MyInfo = CU.getInfo(Idx); - - // At this point we are guaranteed to have a continuation marker before us - // in the worklist, except for the last DIE. - if (!Worklist.empty()) - Worklist.back().ChildInfo = &MyInfo; + unsigned Idx = Current.CU.getOrigUnit().getDIEIndex(Current.Die); + CompileUnit::DIEInfo &MyInfo = Current.CU.getInfo(Idx); if (MyInfo.Prune) continue; @@ -946,40 +919,101 @@ // We must not call shouldKeepDIE while called from keepDIEAndDependencies, // because it would screw up the relocation finding logic. if (!(Current.Flags & TF_DependencyWalk)) - Current.Flags = shouldKeepDIE(RelocMgr, Ranges, Current.Die, DMO, CU, - MyInfo, Current.Flags); + Current.Flags = shouldKeepDIE(RelocMgr, Ranges, Current.Die, DMO, + Current.CU, MyInfo, Current.Flags); + + // Finish by looking for child DIEs. Because of the LIFO worklist we need + // to schedule that work before any subsequent items are added to the + // worklist. + Worklist.emplace_back(Current.Die, Current.CU, Current.Flags, + WorklistItemType::LookForChildDIEsToKeep); + + if (AlreadyKept || !(Current.Flags & TF_Keep)) + continue; // If it is a newly kept DIE mark it as well as all its dependencies as // kept. - if (!AlreadyKept && (Current.Flags & TF_Keep)) { - bool UseOdr = (Current.Flags & TF_DependencyWalk) - ? (Current.Flags & TF_ODR) - : CU.hasODR(); - keepDIEAndDependencies(RelocMgr, Ranges, Units, Current.Die, MyInfo, DMO, - CU, UseOdr); + bool UseOdr = (Current.Flags & TF_DependencyWalk) + ? (Current.Flags & TF_ODR) + : Current.CU.hasODR(); + unsigned ODRFlag = UseOdr ? TF_ODR : 0; + + DWARFUnit &Unit = Current.CU.getOrigUnit(); + MyInfo.Keep = true; + + // We're looking for incomplete types. + MyInfo.Incomplete = + Current.Die.getTag() != dwarf::DW_TAG_subprogram && + Current.Die.getTag() != dwarf::DW_TAG_member && + dwarf::toUnsigned(Current.Die.find(dwarf::DW_AT_declaration), 0); + + // First mark all the parent chain as kept. + unsigned AncestorIdx = MyInfo.ParentIdx; + while (!Current.CU.getInfo(AncestorIdx).Keep) { + lookForDIEsToKeep( + RelocMgr, Ranges, Units, Unit.getDIEAtIndex(AncestorIdx), DMO, + Current.CU, TF_ParentWalk | TF_Keep | TF_DependencyWalk | ODRFlag); + AncestorIdx = Current.CU.getInfo(AncestorIdx).ParentIdx; } - // The TF_ParentWalk flag tells us that we are currently walking up - // the parent chain of a required DIE, and we don't want to mark all - // the children of the parents as kept (consider for example a - // DW_TAG_namespace node in the parent chain). There are however a - // set of DIE types for which we want to ignore that directive and still - // walk their children. - if (dieNeedsChildrenToBeMeaningful(Current.Die.getTag())) - Current.Flags &= ~TF_ParentWalk; + // Then we need to mark all the DIEs referenced by this DIE's attributes + // as kept. + DWARFDataExtractor Data = Unit.getDebugInfoExtractor(); + const auto *Abbrev = Current.Die.getAbbreviationDeclarationPtr(); + uint64_t Offset = + Current.Die.getOffset() + getULEB128Size(Abbrev->getCode()); + + // Mark all DIEs referenced through attributes as kept. + SmallVector, 4> ReferencedDIEs; + for (const auto &AttrSpec : Abbrev->attributes()) { + DWARFFormValue Val(AttrSpec.Form); + if (!Val.isFormClass(DWARFFormValue::FC_Reference) || + AttrSpec.Attr == dwarf::DW_AT_sibling) { + DWARFFormValue::skipValue(AttrSpec.Form, Data, &Offset, + Unit.getFormParams()); + continue; + } - if (!Current.Die.hasChildren() || (Current.Flags & TF_ParentWalk)) - continue; + Val.extractValue(Data, &Offset, Unit.getFormParams(), &Unit); + CompileUnit *ReferencedCU; + if (auto RefDie = resolveDIEReference(*this, DMO, Units, Val, + Current.Die, ReferencedCU)) { + uint32_t RefIdx = ReferencedCU->getOrigUnit().getDIEIndex(RefDie); + CompileUnit::DIEInfo &Info = ReferencedCU->getInfo(RefIdx); + bool IsModuleRef = Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset() && + Info.Ctxt->isDefinedInClangModule(); + // If the referenced DIE has a DeclContext that has already been + // emitted, then do not keep the one in this CU. We'll link to + // the canonical DIE in cloneDieReferenceAttribute. + // FIXME: compatibility with dsymutil-classic. UseODR shouldn't + // be necessary and could be advantageously replaced by + // ReferencedCU->hasODR() && CU.hasODR(). + // FIXME: compatibility with dsymutil-classic. There is no + // reason not to unique ref_addr references. + if (AttrSpec.Form != dwarf::DW_FORM_ref_addr && + (UseOdr || IsModuleRef) && Info.Ctxt && + Info.Ctxt != ReferencedCU->getInfo(Info.ParentIdx).Ctxt && + Info.Ctxt->getCanonicalDIEOffset() && + isODRAttribute(AttrSpec.Attr)) + continue; + + // Keep a module forward declaration if there is no definition. + if (!(isODRAttribute(AttrSpec.Attr) && Info.Ctxt && + Info.Ctxt->getCanonicalDIEOffset())) + Info.Prune = false; + ReferencedDIEs.emplace_back(RefDie, *ReferencedCU); + } + } - // Add children in reverse order to the worklist to effectively process - // them in order. - for (auto Child : reverse(Current.Die.children())) { - // Add continuation marker before every child to calculate incompleteness - // after the last child is processed. We can't store this information in - // the same item because we might have to process other continuations - // first. - Worklist.emplace_back(Current.Die); - Worklist.emplace_back(Child, Current.Flags); + // Add referenced DIEs in reverse order to the worklist to effectively + // process them in order. + for (auto& P : reverse(ReferencedDIEs)) { + // Add a worklist item before every child to calculate incompleteness right + // after the current child is processed. + uint32_t RefIdx = P.second.getOrigUnit().getDIEIndex(P.first); + CompileUnit::DIEInfo &Info = P.second.getInfo(RefIdx); + Worklist.emplace_back(Current.Die, Current.CU, WorklistItemType::UpdateRefIncompleteness, &Info); + Worklist.emplace_back(P.first, P.second, TF_Keep | TF_DependencyWalk | ODRFlag); } } }