LLVM 20.0.0git
DependencyTracker.h
Go to the documentation of this file.
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
15
16namespace llvm {
17class DWARFDebugInfoEntry;
18class DWARFDie;
19
20namespace dwarf_linker {
21namespace 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).
27public:
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.
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().
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
59protected:
60 enum class LiveRootWorklistActionTy : uint8_t {
61 /// Mark current item as live entry.
63
64 /// Mark current item as type entry.
66
67 /// Mark current item and all its children as live entry.
69
70 /// Mark current item and all its children as type entry.
72
73 /// Mark all children of current item as live entry.
75
76 /// Mark all children of current item as type entry.
78 };
79
80 /// \returns true if the specified action is for the "PlainDwarf".
82 switch (Action) {
83 default:
84 return false;
85
89 return true;
90 }
91 }
92
93 /// \returns true if the specified action is for the "TypeTable".
95 switch (Action) {
96 default:
97 return false;
98
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.
109 switch (Action) {
110 default:
111 return false;
112
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.
122 switch (Action) {
123 default:
124 return false;
125
128 return true;
129 }
130 }
131
132 /// Class keeping live worklist item data.
134 public:
138 UnitEntryPairTy RootEntry) {
139 RootCU.setInt(Action);
140 RootCU.setPointer(RootEntry.CU);
141
142 RootDieEntry = RootEntry.DieEntry;
143 }
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
156 return UnitEntryPairTy{RootCU.getPointer(), RootDieEntry};
157 }
158
160 return static_cast<CompileUnit::DieOutputPlacement>(RootCU.getInt());
161 }
162
163 bool hasReferencedByOtherEntry() const { return ReferencedByCU != nullptr; }
164
169 }
170
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.
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
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.
203 };
204
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.
230 const UnitEntryPairTy &RootEntry,
231 const UnitEntryPairTy &Entry,
232 bool InterCUProcessingStarted,
233 std::atomic<bool> &HasNewInterconnectedCUs);
234
235 /// Mark parents as keeping children.
237
238 /// Mark whole DIE tree as placed in "PlainDwarf".
240
241 /// Check referenced DIEs and add them into the worklist.
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.
251
252 /// \returns root for the specified \p Entry.
254
255 /// Add action item to the work list.
256 void
258 const UnitEntryPairTy &Entry,
259 std::optional<UnitEntryPairTy> ReferencedBy);
260
262
263 /// List of entries which are 'root DIE's.
265
266 /// List of entries 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
#define P(N)
This file defines the PointerIntPair class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
A pointer to another debug information entry.
Definition: DIE.h:319
DWARFDebugInfoEntry - A DIE with only the minimum required data.
PointerIntPair - This class implements a pair of a pointer and small integer.
Stores all information related to a compile unit, be it in its original instance of the object file o...
DieOutputPlacement
Kinds of placement for the output die.
LiveRootWorklistItemTy(LiveRootWorklistActionTy Action, UnitEntryPairTy RootEntry)
PointerIntPair< CompileUnit *, 3, LiveRootWorklistActionTy, CompileUnitPointerTraits > RootCU
LiveRootWorklistItemTy(LiveRootWorklistActionTy Action, UnitEntryPairTy RootEntry, UnitEntryPairTy ReferencedBy)
CompileUnit * ReferencedByCU
Another root entry which references this RootDieEntry.
This class discovers DIEs dependencies: marks "live" DIEs, marks DIE locations (whether DIE should be...
void verifyKeepChain()
Recursively walk the DIE tree and check "keepness" and "placement" information.
RootEntriesListTy Dependencies
List of entries dependencies.
void markParentsAsKeepingChildren(const UnitEntryPairTy &Entry)
Mark parents as keeping children.
UnitEntryPairTy getRootForSpecifiedEntry(UnitEntryPairTy Entry)
bool markCollectedLiveRootsAsKept(bool InterCUProcessingStarted, std::atomic< bool > &HasNewInterconnectedCUs)
Examine worklist and mark all 'root DIE's as kept and set "Placement" property.
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 isLiveAction(LiveRootWorklistActionTy Action)
bool isChildrenAction(LiveRootWorklistActionTy Action)
bool isSingleAction(LiveRootWorklistActionTy Action)
bool isTypeAction(LiveRootWorklistActionTy Action)
bool markDIEEntryAsKeptRec(LiveRootWorklistActionTy Action, const UnitEntryPairTy &RootEntry, const UnitEntryPairTy &Entry, bool InterCUProcessingStarted, std::atomic< bool > &HasNewInterconnectedCUs)
Mark whole DIE tree as kept recursively.
bool isTypeTableCandidate(const DWARFDebugInfoEntry *DIEEntry)
void setPlainDwarfPlacementRec(const UnitEntryPairTy &Entry)
Mark whole DIE tree as placed in "PlainDwarf".
RootEntriesListTy RootEntriesWorkList
List of entries which are 'root DIE's.
void addActionToRootEntriesWorkList(LiveRootWorklistActionTy Action, const UnitEntryPairTy &Entry, std::optional< UnitEntryPairTy > ReferencedBy)
Add action item to the work list.
static bool isLiveSubprogramEntry(const UnitEntryPairTy &Entry)
Returns true if specified subprogram references live code section.
bool resolveDependenciesAndMarkLiveness(bool InterCUProcessingStarted, std::atomic< bool > &HasNewInterconnectedCUs)
Recursively walk the DIE tree and look for DIEs to keep.
static bool isLiveVariableEntry(const UnitEntryPairTy &Entry, bool IsLiveParent)
Returns true if specified variable references live code section.
@ MarkTypeEntryRec
Mark current item and all its children as type entry.
@ MarkLiveChildrenRec
Mark all children of current item as live entry.
@ MarkLiveEntryRec
Mark current item and all its children as live entry.
@ MarkTypeChildrenRec
Mark all children of current item as type entry.
void collectRootsToKeep(const UnitEntryPairTy &Entry, std::optional< UnitEntryPairTy > ReferencedBy, bool IsLiveParent)
This function navigates DIEs tree starting from specified Entry.
bool updateDependenciesCompleteness()
Check if dependencies have incompatible placement.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
This is a helper structure which keeps a debug info entry with it's containing compilation unit.