275 lines · c
1//===- "DependencyTracker.h" ------------------------------------*- C++ -*-===//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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIB_DWARFLINKER_PARALLEL_DEPENDENCYTRACKER_H10#define LLVM_LIB_DWARFLINKER_PARALLEL_DEPENDENCYTRACKER_H11 12#include "DWARFLinkerCompileUnit.h"13#include "llvm/ADT/PointerIntPair.h"14#include "llvm/ADT/SmallVector.h"15 16namespace llvm {17class DWARFDebugInfoEntry;18class DWARFDie;19 20namespace dwarf_linker {21namespace parallel {22 23/// This class discovers DIEs dependencies: marks "live" DIEs, marks DIE24/// locations (whether DIE should be cloned as regular DIE or it should be put25/// into the artificial type unit).26class DependencyTracker {27public:28 DependencyTracker(CompileUnit &CU) : CU(CU) {}29 30 /// Recursively walk the \p DIE tree and look for DIEs to keep. Store that31 /// information in \p CU's DIEInfo.32 ///33 /// This function is the entry point of the DIE selection algorithm. It is34 /// expected to walk the DIE tree and(through the mediation of35 /// Context.File.Addresses) ask for relocation adjustment value on each36 /// DIE that might be a 'root DIE'(f.e. subprograms, variables).37 ///38 /// Returns true if all dependencies are correctly discovered. Inter-CU39 /// dependencies cannot be discovered if referenced CU is not analyzed yet.40 /// If that is the case this method returns false.41 bool resolveDependenciesAndMarkLiveness(42 bool InterCUProcessingStarted,43 std::atomic<bool> &HasNewInterconnectedCUs);44 45 /// Check if dependencies have incompatible placement.46 /// If that is the case modify placement to be compatible.47 /// \returns true if any placement was updated, otherwise returns false.48 /// This method should be called as a followup processing after49 /// resolveDependenciesAndMarkLiveness().50 bool updateDependenciesCompleteness();51 52 /// Recursively walk the \p DIE tree and check "keepness" and "placement"53 /// information. It is an error if parent node does not have "keep" flag,54 /// while child has one. It is an error if parent node has "TypeTable"55 /// placement while child has "PlainDwarf" placement. This function dump error56 /// at stderr in that case.57 void verifyKeepChain();58 59protected:60 enum class LiveRootWorklistActionTy : uint8_t {61 /// Mark current item as live entry.62 MarkSingleLiveEntry = 0,63 64 /// Mark current item as type entry.65 MarkSingleTypeEntry,66 67 /// Mark current item and all its children as live entry.68 MarkLiveEntryRec,69 70 /// Mark current item and all its children as type entry.71 MarkTypeEntryRec,72 73 /// Mark all children of current item as live entry.74 MarkLiveChildrenRec,75 76 /// Mark all children of current item as type entry.77 MarkTypeChildrenRec,78 };79 80 /// \returns true if the specified action is for the "PlainDwarf".81 bool isLiveAction(LiveRootWorklistActionTy Action) {82 switch (Action) {83 default:84 return false;85 86 case LiveRootWorklistActionTy::MarkSingleLiveEntry:87 case LiveRootWorklistActionTy::MarkLiveEntryRec:88 case LiveRootWorklistActionTy::MarkLiveChildrenRec:89 return true;90 }91 }92 93 /// \returns true if the specified action is for the "TypeTable".94 bool isTypeAction(LiveRootWorklistActionTy Action) {95 switch (Action) {96 default:97 return false;98 99 case LiveRootWorklistActionTy::MarkSingleTypeEntry:100 case LiveRootWorklistActionTy::MarkTypeEntryRec:101 case LiveRootWorklistActionTy::MarkTypeChildrenRec:102 return true;103 }104 }105 106 /// \returns true if the specified action affects only Root entry107 /// itself and does not affect it`s children.108 bool isSingleAction(LiveRootWorklistActionTy Action) {109 switch (Action) {110 default:111 return false;112 113 case LiveRootWorklistActionTy::MarkSingleLiveEntry:114 case LiveRootWorklistActionTy::MarkSingleTypeEntry:115 return true;116 }117 }118 119 /// \returns true if the specified action affects only Root entry120 /// itself and does not affect it`s children.121 bool isChildrenAction(LiveRootWorklistActionTy Action) {122 switch (Action) {123 default:124 return false;125 126 case LiveRootWorklistActionTy::MarkLiveChildrenRec:127 case LiveRootWorklistActionTy::MarkTypeChildrenRec:128 return true;129 }130 }131 132 /// Class keeping live worklist item data.133 class LiveRootWorklistItemTy {134 public:135 LiveRootWorklistItemTy() = default;136 LiveRootWorklistItemTy(const LiveRootWorklistItemTy &) = default;137 LiveRootWorklistItemTy(LiveRootWorklistActionTy Action,138 UnitEntryPairTy RootEntry) {139 RootCU.setInt(Action);140 RootCU.setPointer(RootEntry.CU);141 142 RootDieEntry = RootEntry.DieEntry;143 }144 LiveRootWorklistItemTy(LiveRootWorklistActionTy Action,145 UnitEntryPairTy RootEntry,146 UnitEntryPairTy ReferencedBy) {147 RootCU.setPointer(RootEntry.CU);148 RootCU.setInt(Action);149 RootDieEntry = RootEntry.DieEntry;150 151 ReferencedByCU = ReferencedBy.CU;152 ReferencedByDieEntry = ReferencedBy.DieEntry;153 }154 155 UnitEntryPairTy getRootEntry() const {156 return UnitEntryPairTy{RootCU.getPointer(), RootDieEntry};157 }158 159 CompileUnit::DieOutputPlacement getPlacement() const {160 return static_cast<CompileUnit::DieOutputPlacement>(RootCU.getInt());161 }162 163 bool hasReferencedByOtherEntry() const { return ReferencedByCU != nullptr; }164 165 UnitEntryPairTy getReferencedByEntry() const {166 assert(ReferencedByCU);167 assert(ReferencedByDieEntry);168 return UnitEntryPairTy{ReferencedByCU, ReferencedByDieEntry};169 }170 171 LiveRootWorklistActionTy getAction() const {172 return static_cast<LiveRootWorklistActionTy>(RootCU.getInt());173 }174 175 protected:176 /// Root entry.177 /// ASSUMPTION: 3 bits are used to store LiveRootWorklistActionTy value.178 /// Thus LiveRootWorklistActionTy should have no more eight elements.179 180 /// Pointer traits for CompileUnit.181 struct CompileUnitPointerTraits {182 static inline void *getAsVoidPointer(CompileUnit *P) { return P; }183 static inline CompileUnit *getFromVoidPointer(void *P) {184 return (CompileUnit *)P;185 }186 static constexpr int NumLowBitsAvailable = 3;187 static_assert(188 alignof(CompileUnit) >= (1 << NumLowBitsAvailable),189 "CompileUnit insufficiently aligned to have enough low bits.");190 };191 192 PointerIntPair<CompileUnit *, 3, LiveRootWorklistActionTy,193 CompileUnitPointerTraits>194 RootCU;195 const DWARFDebugInfoEntry *RootDieEntry = nullptr;196 197 /// Another root entry which references this RootDieEntry.198 /// ReferencedByDieEntry is kept to update placement.199 /// if RootDieEntry has placement incompatible with placement200 /// of ReferencedByDieEntry then it should be updated.201 CompileUnit *ReferencedByCU = nullptr;202 const DWARFDebugInfoEntry *ReferencedByDieEntry = nullptr;203 };204 205 using RootEntriesListTy = SmallVector<LiveRootWorklistItemTy>;206 207 /// This function navigates DIEs tree starting from specified \p Entry.208 /// It puts found 'root DIE' into the worklist. The \p CollectLiveEntries209 /// instructs to collect either live roots(like subprograms having live210 /// DW_AT_low_pc) or otherwise roots which is not live(they need to be211 /// collected if they are imported f.e. by DW_TAG_imported_module).212 void collectRootsToKeep(const UnitEntryPairTy &Entry,213 std::optional<UnitEntryPairTy> ReferencedBy,214 bool IsLiveParent);215 216 /// Returns true if specified variable references live code section.217 static bool isLiveVariableEntry(const UnitEntryPairTy &Entry,218 bool IsLiveParent);219 220 /// Returns true if specified subprogram references live code section.221 static bool isLiveSubprogramEntry(const UnitEntryPairTy &Entry);222 223 /// Examine worklist and mark all 'root DIE's as kept and set "Placement"224 /// property.225 bool markCollectedLiveRootsAsKept(bool InterCUProcessingStarted,226 std::atomic<bool> &HasNewInterconnectedCUs);227 228 /// Mark whole DIE tree as kept recursively.229 bool markDIEEntryAsKeptRec(LiveRootWorklistActionTy Action,230 const UnitEntryPairTy &RootEntry,231 const UnitEntryPairTy &Entry,232 bool InterCUProcessingStarted,233 std::atomic<bool> &HasNewInterconnectedCUs);234 235 /// Mark parents as keeping children.236 void markParentsAsKeepingChildren(const UnitEntryPairTy &Entry);237 238 /// Mark whole DIE tree as placed in "PlainDwarf".239 void setPlainDwarfPlacementRec(const UnitEntryPairTy &Entry);240 241 /// Check referenced DIEs and add them into the worklist.242 bool maybeAddReferencedRoots(LiveRootWorklistActionTy Action,243 const UnitEntryPairTy &RootEntry,244 const UnitEntryPairTy &Entry,245 bool InterCUProcessingStarted,246 std::atomic<bool> &HasNewInterconnectedCUs);247 248 /// \returns true if \p DIEEntry can possibly be put into the artificial type249 /// unit.250 bool isTypeTableCandidate(const DWARFDebugInfoEntry *DIEEntry);251 252 /// \returns root for the specified \p Entry.253 UnitEntryPairTy getRootForSpecifiedEntry(UnitEntryPairTy Entry);254 255 /// Add action item to the work list.256 void257 addActionToRootEntriesWorkList(LiveRootWorklistActionTy Action,258 const UnitEntryPairTy &Entry,259 std::optional<UnitEntryPairTy> ReferencedBy);260 261 CompileUnit &CU;262 263 /// List of entries which are 'root DIE's.264 RootEntriesListTy RootEntriesWorkList;265 266 /// List of entries dependencies.267 RootEntriesListTy Dependencies;268};269 270} // end of namespace parallel271} // end of namespace dwarf_linker272} // end of namespace llvm273 274#endif // LLVM_LIB_DWARFLINKER_PARALLEL_DEPENDENCYTRACKER_H275