This class discovers DIEs dependencies: marks "live" DIEs, marks DIE locations (whether DIE should be cloned as regular DIE or it should be put into the artificial type unit). More...

#include "DWARFLinker/Parallel/DependencyTracker.h"

Classes
class	LiveRootWorklistItemTy
	Class keeping live worklist item data. More...

Public Member Functions
	DependencyTracker (CompileUnit &CU)

bool	resolveDependenciesAndMarkLiveness (bool InterCUProcessingStarted, std::atomic< bool > &HasNewInterconnectedCUs)
	Recursively walk the `DIE` tree and look for DIEs to keep.

bool	updateDependenciesCompleteness ()
	Check if dependencies have incompatible placement.

void	verifyKeepChain ()
	Recursively walk the `DIE` tree and check "keepness" and "placement" information.

Protected Types
enum class	LiveRootWorklistActionTy : uint8_t { MarkSingleLiveEntry = 0 , MarkSingleTypeEntry , MarkLiveEntryRec , MarkTypeEntryRec , MarkLiveChildrenRec , MarkTypeChildrenRec }

using	RootEntriesListTy = SmallVector< LiveRootWorklistItemTy >

Protected Member Functions
bool	isLiveAction (LiveRootWorklistActionTy Action)

bool	isTypeAction (LiveRootWorklistActionTy Action)

bool	isSingleAction (LiveRootWorklistActionTy Action)

bool	isChildrenAction (LiveRootWorklistActionTy Action)

void	collectRootsToKeep (const UnitEntryPairTy &Entry, std::optional< UnitEntryPairTy > ReferencedBy, bool IsLiveParent)
	This function navigates DIEs tree starting from specified `Entry`.

bool	markCollectedLiveRootsAsKept (bool InterCUProcessingStarted, std::atomic< bool > &HasNewInterconnectedCUs)
	Examine worklist and mark all 'root DIE's as kept and set "Placement" property.

bool	markDIEEntryAsKeptRec (LiveRootWorklistActionTy Action, const UnitEntryPairTy &RootEntry, const UnitEntryPairTy &Entry, bool InterCUProcessingStarted, std::atomic< bool > &HasNewInterconnectedCUs)
	Mark whole DIE tree as kept recursively.

void	markParentsAsKeepingChildren (const UnitEntryPairTy &Entry)
	Mark parents as keeping children.

void	setPlainDwarfPlacementRec (const UnitEntryPairTy &Entry)
	Mark whole DIE tree as placed in "PlainDwarf".

bool	maybeAddReferencedRoots (LiveRootWorklistActionTy Action, const UnitEntryPairTy &RootEntry, const UnitEntryPairTy &Entry, bool InterCUProcessingStarted, std::atomic< bool > &HasNewInterconnectedCUs)
	Check referenced DIEs and add them into the worklist.

bool	isTypeTableCandidate (const DWARFDebugInfoEntry *DIEEntry)

UnitEntryPairTy	getRootForSpecifiedEntry (UnitEntryPairTy Entry)

void	addActionToRootEntriesWorkList (LiveRootWorklistActionTy Action, const UnitEntryPairTy &Entry, std::optional< UnitEntryPairTy > ReferencedBy)
	Add action item to the work list.

Static Protected Member Functions
static bool	isLiveVariableEntry (const UnitEntryPairTy &Entry, bool IsLiveParent)
	Returns true if specified variable references live code section.

static bool	isLiveSubprogramEntry (const UnitEntryPairTy &Entry)
	Returns true if specified subprogram references live code section.

Protected Attributes
CompileUnit &	CU

RootEntriesListTy	RootEntriesWorkList
	List of entries which are 'root DIE's.

RootEntriesListTy	Dependencies
	List of entries dependencies.

Detailed Description

This class discovers DIEs dependencies: marks "live" DIEs, marks DIE locations (whether DIE should be cloned as regular DIE or it should be put into the artificial type unit).

Definition at line 26 of file DependencyTracker.h.

Member Typedef Documentation

◆ RootEntriesListTy

using llvm::dwarf_linker::parallel::DependencyTracker::RootEntriesListTy = SmallVector<LiveRootWorklistItemTy>

protected

Definition at line 205 of file DependencyTracker.h.

Member Enumeration Documentation

◆ LiveRootWorklistActionTy

enum class llvm::dwarf_linker::parallel::DependencyTracker::LiveRootWorklistActionTy : uint8_t

strongprotected

Enumerator
MarkSingleLiveEntry	Mark current item as live entry.
MarkSingleTypeEntry	Mark current item as type entry.
MarkLiveEntryRec	Mark current item and all its children as live entry.
MarkTypeEntryRec	Mark current item and all its children as type entry.
MarkLiveChildrenRec	Mark all children of current item as live entry.
MarkTypeChildrenRec	Mark all children of current item as type entry.

Definition at line 60 of file DependencyTracker.h.

Constructor & Destructor Documentation

◆ DependencyTracker()

llvm::dwarf_linker::parallel::DependencyTracker::DependencyTracker ( CompileUnit & CU )

inline

Definition at line 28 of file DependencyTracker.h.

Member Function Documentation

◆ addActionToRootEntriesWorkList()

void DependencyTracker::addActionToRootEntriesWorkList	(	LiveRootWorklistActionTy	Action,
		const UnitEntryPairTy &	Entry,
		std::optional< UnitEntryPairTy >	ReferencedBy
	)

protected

Add action item to the work list.

Definition at line 123 of file DependencyTracker.cpp.

References llvm::SmallVectorImpl< T >::emplace_back(), and RootEntriesWorkList.

Referenced by collectRootsToKeep(), markParentsAsKeepingChildren(), and maybeAddReferencedRoots().

◆ collectRootsToKeep()

void DependencyTracker::collectRootsToKeep	(	const UnitEntryPairTy &	Entry,
		std::optional< UnitEntryPairTy >	ReferencedBy,
		bool	IsLiveParent
	)

protected

This function navigates DIEs tree starting from specified Entry.

It puts found 'root DIE' into the worklist. The CollectLiveEntries instructs to collect either live roots(like subprograms having live DW_AT_low_pc) or otherwise roots which is not live(they need to be collected if they are imported f.e. by DW_TAG_imported_module).

Definition at line 134 of file DependencyTracker.cpp.

References addActionToRootEntriesWorkList(), collectRootsToKeep(), isLiveSubprogramEntry(), isLiveVariableEntry(), llvm_unreachable, MarkLiveEntryRec, MarkSingleLiveEntry, MarkSingleTypeEntry, and MarkTypeEntryRec.

Referenced by collectRootsToKeep(), and resolveDependenciesAndMarkLiveness().

◆ getRootForSpecifiedEntry()

UnitEntryPairTy DependencyTracker::getRootForSpecifiedEntry ( UnitEntryPairTy Entry )

protected

Returns: root for the specified Entry.

Definition at line 694 of file DependencyTracker.cpp.

References isNamespaceLikeEntry().

Referenced by maybeAddReferencedRoots().

◆ isChildrenAction()

bool llvm::dwarf_linker::parallel::DependencyTracker::isChildrenAction ( LiveRootWorklistActionTy Action )

inlineprotected

Returns: true if the specified action affects only Root entry itself and does not affect it`s children.

Definition at line 121 of file DependencyTracker.h.

References MarkLiveChildrenRec, and MarkTypeChildrenRec.

Referenced by markDIEEntryAsKeptRec().

◆ isLiveAction()

bool llvm::dwarf_linker::parallel::DependencyTracker::isLiveAction ( LiveRootWorklistActionTy Action )

inlineprotected

Returns: true if the specified action is for the "PlainDwarf".

Definition at line 81 of file DependencyTracker.h.

References MarkLiveChildrenRec, MarkLiveEntryRec, and MarkSingleLiveEntry.

Referenced by markDIEEntryAsKeptRec(), and maybeAddReferencedRoots().

◆ isLiveSubprogramEntry()

bool DependencyTracker::isLiveSubprogramEntry ( const UnitEntryPairTy & Entry )

staticprotected

Returns true if specified subprogram references live code section.

Definition at line 770 of file DependencyTracker.cpp.

References llvm::DIDumpOptions::ChildRecurseDepth, llvm::DIE::dump(), llvm::DIE::getTag(), Info, llvm::outs(), llvm::dwarf::toAddress(), UINT64_MAX, and llvm::DIDumpOptions::Verbose.

Referenced by collectRootsToKeep(), and verifyKeepChain().

◆ isLiveVariableEntry()

bool DependencyTracker::isLiveVariableEntry	(	const UnitEntryPairTy &	Entry,
		bool	IsLiveParent
	)

staticprotected

Returns true if specified variable references live code section.

Definition at line 725 of file DependencyTracker.cpp.

References llvm::DIDumpOptions::ChildRecurseDepth, llvm::DIE::dump(), Info, llvm::outs(), and llvm::DIDumpOptions::Verbose.

Referenced by collectRootsToKeep().

◆ isSingleAction()

bool llvm::dwarf_linker::parallel::DependencyTracker::isSingleAction ( LiveRootWorklistActionTy Action )

inlineprotected

Returns: true if the specified action affects only Root entry itself and does not affect it`s children.

Definition at line 108 of file DependencyTracker.h.

References MarkSingleLiveEntry, and MarkSingleTypeEntry.

Referenced by markDIEEntryAsKeptRec().

◆ isTypeAction()

bool llvm::dwarf_linker::parallel::DependencyTracker::isTypeAction ( LiveRootWorklistActionTy Action )

inlineprotected

Returns: true if the specified action is for the "TypeTable".

Definition at line 94 of file DependencyTracker.h.

References MarkSingleTypeEntry, MarkTypeChildrenRec, and MarkTypeEntryRec.

Referenced by markDIEEntryAsKeptRec(), and maybeAddReferencedRoots().

◆ isTypeTableCandidate()

bool DependencyTracker::isTypeTableCandidate ( const DWARFDebugInfoEntry * DIEEntry )

protected

Returns: true if DIEEntry can possibly be put into the artificial type unit.

Definition at line 564 of file DependencyTracker.cpp.

Referenced by markDIEEntryAsKeptRec().

◆ markCollectedLiveRootsAsKept()

bool DependencyTracker::markCollectedLiveRootsAsKept	(	bool	InterCUProcessingStarted,
		std::atomic< bool > &	HasNewInterconnectedCUs
	)

protected

Examine worklist and mark all 'root DIE's as kept and set "Placement" property.

Definition at line 225 of file DependencyTracker.cpp.

References Dependencies, llvm::SmallVectorBase< Size_T >::empty(), llvm::dwarf_linker::parallel::DependencyTracker::LiveRootWorklistItemTy::getAction(), llvm::dwarf_linker::parallel::DependencyTracker::LiveRootWorklistItemTy::getRootEntry(), llvm::dwarf_linker::parallel::DependencyTracker::LiveRootWorklistItemTy::hasReferencedByOtherEntry(), markDIEEntryAsKeptRec(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and RootEntriesWorkList.

Referenced by resolveDependenciesAndMarkLiveness().

◆ markDIEEntryAsKeptRec()

bool DependencyTracker::markDIEEntryAsKeptRec	(	LiveRootWorklistActionTy	Action,
		const UnitEntryPairTy &	RootEntry,
		const UnitEntryPairTy &	Entry,
		bool	InterCUProcessingStarted,
		std::atomic< bool > &	HasNewInterconnectedCUs
	)

protected

Mark whole DIE tree as kept recursively.

Definition at line 428 of file DependencyTracker.cpp.

References assert(), getFinalPlacementForEntry(), Info, isAlreadyMarked(), isChildrenAction(), isLiveAction(), isSingleAction(), isTypeAction(), isTypeTableCandidate(), markDIEEntryAsKeptRec(), markParentsAsKeepingChildren(), maybeAddReferencedRoots(), Placement, llvm::dwarf_linker::parallel::CompileUnit::PlainDwarf, and llvm::dwarf_linker::parallel::CompileUnit::TypeTable.

Referenced by markCollectedLiveRootsAsKept(), and markDIEEntryAsKeptRec().

◆ markParentsAsKeepingChildren()

void DependencyTracker::markParentsAsKeepingChildren ( const UnitEntryPairTy & Entry )

protected

Mark parents as keeping children.

Definition at line 329 of file DependencyTracker.cpp.

References addActionToRootEntriesWorkList(), llvm::DWARFDebugInfoEntry::getParentIdx(), Info, isAlreadyMarked(), isNamespaceLikeEntry(), MarkLiveChildrenRec, MarkTypeChildrenRec, llvm::dwarf_linker::parallel::CompileUnit::PlainDwarf, and llvm::dwarf_linker::parallel::CompileUnit::TypeTable.

Referenced by markDIEEntryAsKeptRec(), and setPlainDwarfPlacementRec().

◆ maybeAddReferencedRoots()

bool DependencyTracker::maybeAddReferencedRoots	(	LiveRootWorklistActionTy	Action,
		const UnitEntryPairTy &	RootEntry,
		const UnitEntryPairTy &	Entry,
		bool	InterCUProcessingStarted,
		std::atomic< bool > &	HasNewInterconnectedCUs
	)

protected

Check referenced DIEs and add them into the worklist.

Definition at line 612 of file DependencyTracker.cpp.

References addActionToRootEntriesWorkList(), assert(), llvm::dwarf_linker::parallel::AvoidResolving, llvm::Data, llvm::DWARFFormValue::extractValue(), llvm::DWARFFormValue::FC_Reference, llvm::dwarf_linker::parallel::getODRAttributes(), getRootForSpecifiedEntry(), llvm::getULEB128Size(), llvm::is_contained(), llvm::DWARFFormValue::isFormClass(), isLiveAction(), isNamespaceLikeEntry(), isTypeAction(), MarkLiveEntryRec, MarkSingleLiveEntry, MarkSingleTypeEntry, MarkTypeEntryRec, llvm::Offset, llvm::dwarf_linker::parallel::Resolve, and llvm::DWARFFormValue::skipValue().

Referenced by markDIEEntryAsKeptRec().

◆ resolveDependenciesAndMarkLiveness()

bool DependencyTracker::resolveDependenciesAndMarkLiveness	(	bool	InterCUProcessingStarted,
		std::atomic< bool > &	HasNewInterconnectedCUs
	)

Recursively walk the DIE tree and look for DIEs to keep.

Store that information in CU's DIEInfo.

This function is the entry point of the DIE selection algorithm. It is expected to walk the DIE tree and(through the mediation of Context.File.Addresses) ask for relocation adjustment value on each DIE that might be a 'root DIE'(f.e. subprograms, variables).

Returns true if all dependencies are correctly discovered. Inter-CU dependencies cannot be discovered if referenced CU is not analyzed yet. If that is the case this method returns false.

Definition at line 108 of file DependencyTracker.cpp.

References llvm::SmallVectorImpl< T >::clear(), collectRootsToKeep(), CU, markCollectedLiveRootsAsKept(), llvm::dwarf_linker::parallel::CompileUnit::PlainDwarf, RootEntriesWorkList, and llvm::dwarf_linker::parallel::CompileUnit::DIEInfo::setPlacement().

◆ setPlainDwarfPlacementRec()

void DependencyTracker::setPlainDwarfPlacementRec ( const UnitEntryPairTy & Entry )

protected

Mark whole DIE tree as placed in "PlainDwarf".

Definition at line 272 of file DependencyTracker.cpp.

References Info, markParentsAsKeepingChildren(), llvm::dwarf_linker::parallel::CompileUnit::PlainDwarf, and setPlainDwarfPlacementRec().

Referenced by setPlainDwarfPlacementRec(), and updateDependenciesCompleteness().

◆ updateDependenciesCompleteness()

bool DependencyTracker::updateDependenciesCompleteness ( )

Check if dependencies have incompatible placement.

If that is the case modify placement to be compatible.

Returns: true if any placement was updated, otherwise returns false. This method should be called as a followup processing after resolveDependenciesAndMarkLiveness().

Definition at line 245 of file DependencyTracker.cpp.

References assert(), llvm::dwarf_linker::parallel::UnitEntryPairTy::CU, Dependencies, llvm::dwarf_linker::parallel::UnitEntryPairTy::DieEntry, llvm::dwarf_linker::parallel::CompileUnit::getDIEInfo(), llvm::dwarf_linker::parallel::CompileUnit::DIEInfo::needToPlaceInTypeTable(), and setPlainDwarfPlacementRec().

◆ verifyKeepChain()

void DependencyTracker::verifyKeepChain ( )

Recursively walk the DIE tree and check "keepness" and "placement" information.

Verify the keep chain by looking for DIEs that are kept but who's parent isn't.

It is an error if parent node does not have "keep" flag, while child has one. It is an error if parent node has "TypeTable" placement while child has "PlainDwarf" placement. This function dump error at stderr in that case.

Definition at line 28 of file DependencyTracker.cpp.

References assert(), llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::DWARFDie::children(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::SmallVectorBase< Size_T >::empty(), llvm::WithColor::error(), llvm::errs(), llvm::formatv(), llvm::DWARFDie::getDebugInfoEntry(), isLiveSubprogramEntry(), llvm::DWARFDie::isValid(), llvm::dwarf_linker::parallel::CompileUnit::DIEInfo::needToKeepInPlainDwarf(), llvm::dwarf_linker::parallel::CompileUnit::DIEInfo::needToPlaceInTypeTable(), llvm::SmallVectorTemplateBase< T, bool >::pop_back(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::report_fatal_error(), and llvm::reverse().

Member Data Documentation

◆ CU

CompileUnit& llvm::dwarf_linker::parallel::DependencyTracker::CU

protected

Definition at line 261 of file DependencyTracker.h.

Referenced by resolveDependenciesAndMarkLiveness().

◆ Dependencies

RootEntriesListTy llvm::dwarf_linker::parallel::DependencyTracker::Dependencies

protected

List of entries dependencies.

Definition at line 267 of file DependencyTracker.h.

Referenced by markCollectedLiveRootsAsKept(), and updateDependenciesCompleteness().

◆ RootEntriesWorkList

RootEntriesListTy llvm::dwarf_linker::parallel::DependencyTracker::RootEntriesWorkList

protected

List of entries which are 'root DIE's.

Definition at line 264 of file DependencyTracker.h.

Referenced by addActionToRootEntriesWorkList(), markCollectedLiveRootsAsKept(), and resolveDependenciesAndMarkLiveness().

The documentation for this class was generated from the following files:

lib/DWARFLinker/Parallel/DependencyTracker.h
lib/DWARFLinker/Parallel/DependencyTracker.cpp

Classes

Public Member Functions

Protected Types

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ RootEntriesListTy

Member Enumeration Documentation

◆ LiveRootWorklistActionTy

Constructor & Destructor Documentation

◆ DependencyTracker()

Member Function Documentation

◆ addActionToRootEntriesWorkList()

◆ collectRootsToKeep()

◆ getRootForSpecifiedEntry()

◆ isChildrenAction()

◆ isLiveAction()

◆ isLiveSubprogramEntry()

◆ isLiveVariableEntry()

◆ isSingleAction()

◆ isTypeAction()

◆ isTypeTableCandidate()

◆ markCollectedLiveRootsAsKept()

◆ markDIEEntryAsKeptRec()

◆ markParentsAsKeepingChildren()

◆ maybeAddReferencedRoots()

◆ resolveDependenciesAndMarkLiveness()

◆ setPlainDwarfPlacementRec()

◆ updateDependenciesCompleteness()

◆ verifyKeepChain()

Member Data Documentation

◆ CU

◆ Dependencies

◆ RootEntriesWorkList