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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef LLVM_LIB_DWARFLINKER_PARALLEL_DEPENDENCYTRACKER_H 10 #define LLVM_LIB_DWARFLINKER_PARALLEL_DEPENDENCYTRACKER_H 11 12 #include "DWARFLinkerCompileUnit.h" 13 #include "llvm/ADT/PointerIntPair.h" 14 #include "llvm/ADT/SmallVector.h" 15 16 namespace llvm { 17 class DWARFDebugInfoEntry; 18 class DWARFDie; 19 20 namespace dwarf_linker { 21 namespace parallel { 22 23 /// This class discovers DIEs dependencies: marks "live" DIEs, marks DIE 24 /// locations (whether DIE should be cloned as regular DIE or it should be put 25 /// into the artificial type unit). 26 class DependencyTracker { 27 public: 28 DependencyTracker(CompileUnit &CU) : CU(CU) {} 29 30 /// Recursively walk the \p DIE tree and look for DIEs to keep. Store that 31 /// information in \p CU's DIEInfo. 32 /// 33 /// This function is the entry point of the DIE selection algorithm. It is 34 /// expected to walk the DIE tree and(through the mediation of 35 /// Context.File.Addresses) ask for relocation adjustment value on each 36 /// DIE that might be a 'root DIE'(f.e. subprograms, variables). 37 /// 38 /// Returns true if all dependencies are correctly discovered. Inter-CU 39 /// 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 after 49 /// 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 error 56 /// at stderr in that case. 57 void verifyKeepChain(); 58 59 protected: 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 entry 107 /// 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 entry 120 /// 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 placement 200 /// 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 CollectLiveEntries 209 /// instructs to collect either live roots(like subprograms having live 210 /// DW_AT_low_pc) or otherwise roots which is not live(they need to be 211 /// 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 type 249 /// 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 void 257 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 parallel 271 } // end of namespace dwarf_linker 272 } // end of namespace llvm 273 274 #endif // LLVM_LIB_DWARFLINKER_PARALLEL_DEPENDENCYTRACKER_H 275