llvm/lib/DWARFLinkerParallel/DependencyTracker.h - third_party/github.com/llvm/llvm-project - Git at Google

 //===- "DependencyTracker.h" ------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//

 #ifndef LLVM_LIB_DWARFLINKERPARALLEL_DEPENDENCYTRACKER_H
 #define LLVM_LIB_DWARFLINKERPARALLEL_DEPENDENCYTRACKER_H

 #include "DWARFLinkerCompileUnit.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/SmallVector.h"

 namespace llvm {
 class DWARFDebugInfoEntry;
 class DWARFDie;

 namespace dwarflinker_parallel {

 /// 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).
 class DependencyTracker {
 public:
   DependencyTracker(CompileUnit &CU) : CU(CU) {}

   /// 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 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.
   bool resolveDependenciesAndMarkLiveness(
       bool InterCUProcessingStarted,
       std::atomic<bool> &HasNewInterconnectedCUs);

   /// 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().
   bool updateDependenciesCompleteness();

   /// Recursively walk the \p DIE tree and check "keepness" and "placement"
   /// information. 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.
   void verifyKeepChain();

 protected:
   enum class LiveRootWorklistActionTy : uint8_t {
     /// Mark current item as live entry.
     MarkSingleLiveEntry = 0,

     /// Mark current item as type entry.
     MarkSingleTypeEntry,

     /// Mark current item and all its children as live entry.
     MarkLiveEntryRec,

     /// Mark current item and all its children as type entry.
     MarkTypeEntryRec,

     /// Mark all children of current item as live entry.
     MarkLiveChildrenRec,

     /// Mark all children of current item as type entry.
     MarkTypeChildrenRec,
   };

   /// \returns true if the specified action is for the "PlainDwarf".
   bool isLiveAction(LiveRootWorklistActionTy Action) {
     switch (Action) {
     default:
       return false;

     case LiveRootWorklistActionTy::MarkSingleLiveEntry:
     case LiveRootWorklistActionTy::MarkLiveEntryRec:
     case LiveRootWorklistActionTy::MarkLiveChildrenRec:
       return true;
     }
   }

   /// \returns true if the specified action is for the "TypeTable".
   bool isTypeAction(LiveRootWorklistActionTy Action) {
     switch (Action) {
     default:
       return false;

     case LiveRootWorklistActionTy::MarkSingleTypeEntry:
     case LiveRootWorklistActionTy::MarkTypeEntryRec:
     case LiveRootWorklistActionTy::MarkTypeChildrenRec:
       return true;
     }
   }

   /// \returns true if the specified action affects only Root entry
   /// itself and does not affect it`s children.
   bool isSingleAction(LiveRootWorklistActionTy Action) {
     switch (Action) {
     default:
       return false;

     case LiveRootWorklistActionTy::MarkSingleLiveEntry:
     case LiveRootWorklistActionTy::MarkSingleTypeEntry:
       return true;
     }
   }

   /// \returns true if the specified action affects only Root entry
   /// itself and does not affect it`s children.
   bool isChildrenAction(LiveRootWorklistActionTy Action) {
     switch (Action) {
     default:
       return false;

     case LiveRootWorklistActionTy::MarkLiveChildrenRec:
     case LiveRootWorklistActionTy::MarkTypeChildrenRec:
       return true;
     }
   }

   /// Class keeping live worklist item data.
   class LiveRootWorklistItemTy {
   public:
     LiveRootWorklistItemTy() = default;
     LiveRootWorklistItemTy(const LiveRootWorklistItemTy &) = default;
     LiveRootWorklistItemTy(LiveRootWorklistActionTy Action,
                            UnitEntryPairTy RootEntry) {
       RootCU.setInt(Action);
       RootCU.setPointer(RootEntry.CU);

       RootDieEntry = RootEntry.DieEntry;
     }
     LiveRootWorklistItemTy(LiveRootWorklistActionTy Action,
                            UnitEntryPairTy RootEntry,
                            UnitEntryPairTy ReferencedBy) {
       RootCU.setPointer(RootEntry.CU);
       RootCU.setInt(Action);
       RootDieEntry = RootEntry.DieEntry;

       ReferencedByCU = ReferencedBy.CU;
       ReferencedByDieEntry = ReferencedBy.DieEntry;
     }

     UnitEntryPairTy getRootEntry() const {
       return UnitEntryPairTy{RootCU.getPointer(), RootDieEntry};
     }

     CompileUnit::DieOutputPlacement getPlacement() const {
       return static_cast<CompileUnit::DieOutputPlacement>(RootCU.getInt());
     }

     bool hasReferencedByOtherEntry() const { return ReferencedByCU != nullptr; }

     UnitEntryPairTy getReferencedByEntry() const {
       assert(ReferencedByCU);
       assert(ReferencedByDieEntry);
       return UnitEntryPairTy{ReferencedByCU, ReferencedByDieEntry};
     }

     LiveRootWorklistActionTy getAction() const {
       return static_cast<LiveRootWorklistActionTy>(RootCU.getInt());
     }

   protected:
     /// Root entry.
     /// ASSUMPTION: 3 bits are used to store LiveRootWorklistActionTy value.
     /// Thus LiveRootWorklistActionTy should have no more eight elements.

     /// Pointer traits for CompileUnit.
     struct CompileUnitPointerTraits {
       static inline void *getAsVoidPointer(CompileUnit *P) { return P; }
       static inline CompileUnit *getFromVoidPointer(void *P) {
         return (CompileUnit *)P;
       }
       static constexpr int NumLowBitsAvailable = 3;
       static_assert(
           alignof(CompileUnit) >= (1 << NumLowBitsAvailable),
           "CompileUnit insufficiently aligned to have enough low bits.");
     };

     PointerIntPair<CompileUnit *, 3, LiveRootWorklistActionTy,
                    CompileUnitPointerTraits>
         RootCU;
     const DWARFDebugInfoEntry *RootDieEntry = nullptr;

     /// Another root entry which references this RootDieEntry.
     /// ReferencedByDieEntry is kept to update placement.
     /// if RootDieEntry has placement incompatible with placement
     /// of ReferencedByDieEntry then it should be updated.
     CompileUnit *ReferencedByCU = nullptr;
     const DWARFDebugInfoEntry *ReferencedByDieEntry = nullptr;
   };

   using RootEntriesListTy = SmallVector<LiveRootWorklistItemTy>;

   /// This function navigates DIEs tree starting from specified \p Entry.
   /// It puts found 'root DIE' into the worklist. The \p 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).
   void collectRootsToKeep(const UnitEntryPairTy &Entry,
                           std::optional<UnitEntryPairTy> ReferencedBy,
                           bool IsLiveParent);

   /// Returns true if specified variable references live code section.
   static bool isLiveVariableEntry(const UnitEntryPairTy &Entry,
                                   bool IsLiveParent);

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

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

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

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

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

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

   /// \returns true if \p DIEEntry can possibly be put into the artificial type
   /// unit.
   bool isTypeTableCandidate(const DWARFDebugInfoEntry *DIEEntry);

   /// \returns root for the specified \p Entry.
   UnitEntryPairTy getRootForSpecifiedEntry(UnitEntryPairTy Entry);

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

   CompileUnit &CU;

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

   /// List of entries dependencies.
   RootEntriesListTy Dependencies;
 };

 } // end namespace dwarflinker_parallel
 } // end namespace llvm

 #endif // LLVM_LIB_DWARFLINKERPARALLEL_DEPENDENCYTRACKER_H
	//===- "DependencyTracker.h" ------------------------------------- C++ --===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//

	#ifndef LLVM_LIB_DWARFLINKERPARALLEL_DEPENDENCYTRACKER_H
	#define LLVM_LIB_DWARFLINKERPARALLEL_DEPENDENCYTRACKER_H

	#include "DWARFLinkerCompileUnit.h"
	#include "llvm/ADT/PointerIntPair.h"
	#include "llvm/ADT/SmallVector.h"

	namespace llvm {
	class DWARFDebugInfoEntry;
	class DWARFDie;

	namespace dwarflinker_parallel {

	/// 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).
	class DependencyTracker {
	public:
	DependencyTracker(CompileUnit &CU) : CU(CU) {}

	/// 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 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.
	bool resolveDependenciesAndMarkLiveness(
	bool InterCUProcessingStarted,
	std::atomic<bool> &HasNewInterconnectedCUs);

	/// 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().
	bool updateDependenciesCompleteness();

	/// Recursively walk the \p DIE tree and check "keepness" and "placement"
	/// information. 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.
	void verifyKeepChain();

	protected:
	enum class LiveRootWorklistActionTy : uint8_t {
	/// Mark current item as live entry.
	MarkSingleLiveEntry = 0,

	/// Mark current item as type entry.
	MarkSingleTypeEntry,

	/// Mark current item and all its children as live entry.
	MarkLiveEntryRec,

	/// Mark current item and all its children as type entry.
	MarkTypeEntryRec,

	/// Mark all children of current item as live entry.
	MarkLiveChildrenRec,

	/// Mark all children of current item as type entry.
	MarkTypeChildrenRec,
	};

	/// \returns true if the specified action is for the "PlainDwarf".
	bool isLiveAction(LiveRootWorklistActionTy Action) {
	switch (Action) {
	default:
	return false;

	case LiveRootWorklistActionTy::MarkSingleLiveEntry:
	case LiveRootWorklistActionTy::MarkLiveEntryRec:
	case LiveRootWorklistActionTy::MarkLiveChildrenRec:
	return true;
	}
	}

	/// \returns true if the specified action is for the "TypeTable".
	bool isTypeAction(LiveRootWorklistActionTy Action) {
	switch (Action) {
	default:
	return false;

	case LiveRootWorklistActionTy::MarkSingleTypeEntry:
	case LiveRootWorklistActionTy::MarkTypeEntryRec:
	case LiveRootWorklistActionTy::MarkTypeChildrenRec:
	return true;
	}
	}

	/// \returns true if the specified action affects only Root entry
	/// itself and does not affect it`s children.
	bool isSingleAction(LiveRootWorklistActionTy Action) {
	switch (Action) {
	default:
	return false;

	case LiveRootWorklistActionTy::MarkSingleLiveEntry:
	case LiveRootWorklistActionTy::MarkSingleTypeEntry:
	return true;
	}
	}

	/// \returns true if the specified action affects only Root entry
	/// itself and does not affect it`s children.
	bool isChildrenAction(LiveRootWorklistActionTy Action) {
	switch (Action) {
	default:
	return false;

	case LiveRootWorklistActionTy::MarkLiveChildrenRec:
	case LiveRootWorklistActionTy::MarkTypeChildrenRec:
	return true;
	}
	}

	/// Class keeping live worklist item data.
	class LiveRootWorklistItemTy {
	public:
	LiveRootWorklistItemTy() = default;
	LiveRootWorklistItemTy(const LiveRootWorklistItemTy &) = default;
	LiveRootWorklistItemTy(LiveRootWorklistActionTy Action,
	UnitEntryPairTy RootEntry) {
	RootCU.setInt(Action);
	RootCU.setPointer(RootEntry.CU);

	RootDieEntry = RootEntry.DieEntry;
	}
	LiveRootWorklistItemTy(LiveRootWorklistActionTy Action,
	UnitEntryPairTy RootEntry,
	UnitEntryPairTy ReferencedBy) {
	RootCU.setPointer(RootEntry.CU);
	RootCU.setInt(Action);
	RootDieEntry = RootEntry.DieEntry;

	ReferencedByCU = ReferencedBy.CU;
	ReferencedByDieEntry = ReferencedBy.DieEntry;
	}

	UnitEntryPairTy getRootEntry() const {
	return UnitEntryPairTy{RootCU.getPointer(), RootDieEntry};
	}

	CompileUnit::DieOutputPlacement getPlacement() const {
	return static_cast<CompileUnit::DieOutputPlacement>(RootCU.getInt());
	}

	bool hasReferencedByOtherEntry() const { return ReferencedByCU != nullptr; }

	UnitEntryPairTy getReferencedByEntry() const {
	assert(ReferencedByCU);
	assert(ReferencedByDieEntry);
	return UnitEntryPairTy{ReferencedByCU, ReferencedByDieEntry};
	}

	LiveRootWorklistActionTy getAction() const {
	return static_cast<LiveRootWorklistActionTy>(RootCU.getInt());
	}

	protected:
	/// Root entry.
	/// ASSUMPTION: 3 bits are used to store LiveRootWorklistActionTy value.
	/// Thus LiveRootWorklistActionTy should have no more eight elements.

	/// Pointer traits for CompileUnit.
	struct CompileUnitPointerTraits {
	static inline void getAsVoidPointer(CompileUnit P) { return P; }
	static inline CompileUnit getFromVoidPointer(void P) {
	return (CompileUnit *)P;
	}
	static constexpr int NumLowBitsAvailable = 3;
	static_assert(
	alignof(CompileUnit) >= (1 << NumLowBitsAvailable),
	"CompileUnit insufficiently aligned to have enough low bits.");
	};

	PointerIntPair<CompileUnit *, 3, LiveRootWorklistActionTy,
	CompileUnitPointerTraits>
	RootCU;
	const DWARFDebugInfoEntry *RootDieEntry = nullptr;

	/// Another root entry which references this RootDieEntry.
	/// ReferencedByDieEntry is kept to update placement.
	/// if RootDieEntry has placement incompatible with placement
	/// of ReferencedByDieEntry then it should be updated.
	CompileUnit *ReferencedByCU = nullptr;
	const DWARFDebugInfoEntry *ReferencedByDieEntry = nullptr;
	};

	using RootEntriesListTy = SmallVector<LiveRootWorklistItemTy>;

	/// This function navigates DIEs tree starting from specified \p Entry.
	/// It puts found 'root DIE' into the worklist. The \p 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).
	void collectRootsToKeep(const UnitEntryPairTy &Entry,
	std::optional<UnitEntryPairTy> ReferencedBy,
	bool IsLiveParent);

	/// Returns true if specified variable references live code section.
	static bool isLiveVariableEntry(const UnitEntryPairTy &Entry,
	bool IsLiveParent);

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

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

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

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

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

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

	/// \returns true if \p DIEEntry can possibly be put into the artificial type
	/// unit.
	bool isTypeTableCandidate(const DWARFDebugInfoEntry *DIEEntry);

	/// \returns root for the specified \p Entry.
	UnitEntryPairTy getRootForSpecifiedEntry(UnitEntryPairTy Entry);

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

	CompileUnit &CU;

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

	/// List of entries dependencies.
	RootEntriesListTy Dependencies;
	};

	} // end namespace dwarflinker_parallel
	} // end namespace llvm

	#endif // LLVM_LIB_DWARFLINKERPARALLEL_DEPENDENCYTRACKER_H