llvm/lib/DWARFLinker/Parallel/DependencyTracker.h

   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