[lld][MachO][NFC] Nest the CallGraphSort inside the PriorityBuilder class

[Roger]

Summary

The CallGraphSort class is used to inform the priorities constructed by the PriorityBuilder class. I have encapsulated config->callGraphProfile inside the CallGraphSort class. I've also nested the CallGraphSort class inside PriorityBuilder as it needs read-only access to its private fields.

I went with nesting the CallGraphSort class inside the PriorityBuilder class rather than adding to PriorityBuilder's public interface since it is only CallGraphSort that needs access to its private members and this way limits visibility to only those who need it.

[thakis]

What problem does this solve?

[int3]

+1, I'm not convinced this makes the code clearer. I would prefer not to couple the declarations of CallGraphSort and PriorityBuilder. Plus I don't think visibility of members is a big concern given that CallGraphSort is already declared in an anon namespace.

[Roger]

Never mind. I found this is unnecessary.

lld/MachO/Config.h

struct Configuration {
   std::vector<std::string> astPaths;
   std::vector<Symbol *> explicitUndefineds;
   llvm::StringSet<> explicitDynamicLookups;
   // There are typically few custom sectionAlignments or segmentProtections,
   // so use a vector instead of a map.
   std::vector<SectionAlign> sectionAlignments;
   std::vector<SegmentProtection> segmentProtections;
 
-  llvm::MapVector<std::pair<const InputSection *, const InputSection *>,
-                  uint64_t>
-      callGraphProfile;
   bool callGraphProfileSort = false;
   llvm::StringRef printSymbolOrder;
 
   SectionRenameMap sectionRenameMap;
   SegmentRenameMap segmentRenameMap;
 
   SymbolPatterns exportedSymbols;
   SymbolPatterns unexportedSymbols;

lld/MachO/SectionPriorities.h

 #define LLD_MACHO_SECTION_PRIORITIES_H
 
 #include "InputSection.h"
 #include "llvm/ADT/DenseMap.h"
 
 namespace lld {
 namespace macho {
 
+struct Edge {
+  int from;
+  uint64_t weight;
+};
+
+struct Cluster {
+  Cluster(int sec, size_t s) : next(sec), prev(sec), size(s) {}
+
+  double getDensity() const {
+    if (size == 0)
+      return 0;
+    return double(weight) / double(size);
+  }
+
+  int next;
+  int prev;
+  uint64_t size;
+  uint64_t weight = 0;
+  uint64_t initialWeight = 0;
+  Edge bestPred = {-1, 0};
+};
+
 class PriorityBuilder {
 public:
-  // Reads every input section's call graph profile, and combines them into
-  // config->callGraphProfile. If an order file is present, any edges where one
-  // or both of the vertices are specified in the order file are discarded.
-  void extractCallGraphProfile();
+  PriorityBuilder() : callGraphSort(*this) {}
+
+  void extractCallGraphProfile() { callGraphSort.extractCallGraphProfile(); }
 
   // Reads the order file at `path` into config->priorities.
   //
   // An order file has one entry per line, in the following format:
   //
   //   <cpu>:<object file>:<symbol name>
   //
   // <cpu> and <object file> are optional. If not specified, then that entry
public:
   // precedence, but the call graph profile is still used for symbols that don't
   // appear in the order file. If neither is present, an empty map is returned.
   //
   // Each section gets assigned the priority of the highest-priority symbol it
   // contains.
   llvm::DenseMap<const InputSection *, size_t> buildInputSectionPriorities();
 
 private:
-  llvm::Optional<size_t> getSymbolPriority(const Defined *sym);
+  llvm::Optional<size_t> getSymbolPriority(const Defined *sym) const;
   llvm::DenseMap<llvm::StringRef, SymbolPriorityEntry> priorities;
+
+  class CallGraphSort {
+    using SectionPair = std::pair<const InputSection *, const InputSection *>;
+
+  public:
+    CallGraphSort(PriorityBuilder &priorityBuilder);
+
+    llvm::DenseMap<const InputSection *, size_t> run();
+
+    // Reads every input section's call graph profile, and combines them into
+    // config->callGraphProfile. If an order file is present, any edges where
+    // one or both of the vertices are specified in the order file are
+    // discarded.
+    void extractCallGraphProfile();
+
+    const llvm::MapVector<SectionPair, uint64_t> &getProfile() {
+      return profile;
+    }
+
+  private:
+    const PriorityBuilder &builder;
+    std::vector<Cluster> clusters;
+    std::vector<const InputSection *> sections;
+
+    llvm::MapVector<SectionPair, uint64_t> profile;
+  } callGraphSort;
 };
 
 extern std::unique_ptr<PriorityBuilder> priorityBuilder;
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/SectionPriorities.cpp

 
 std::unique_ptr<PriorityBuilder> macho::priorityBuilder =
     std::make_unique<PriorityBuilder>();
 
 namespace {
 
 size_t lowestPriority = std::numeric_limits<size_t>::max();
 
-struct Edge {
-  int from;
-  uint64_t weight;
-};
-
-struct Cluster {
-  Cluster(int sec, size_t s) : next(sec), prev(sec), size(s) {}
-
-  double getDensity() const {
-    if (size == 0)
-      return 0;
-    return double(weight) / double(size);
-  }
-
-  int next;
-  int prev;
-  uint64_t size;
-  uint64_t weight = 0;
-  uint64_t initialWeight = 0;
-  Edge bestPred = {-1, 0};
-};
-
-class CallGraphSort {
-public:
-  CallGraphSort();
-
-  DenseMap<const InputSection *, size_t> run();
-
-private:
-  std::vector<Cluster> clusters;
-  std::vector<const InputSection *> sections;
-};
 // Maximum amount the combined cluster density can be worse than the original
 // cluster to consider merging.
 constexpr int MAX_DENSITY_DEGRADATION = 8;
 } // end anonymous namespace
 
-using SectionPair = std::pair<const InputSection *, const InputSection *>;
-
 // Take the edge list in config->callGraphProfile, resolve symbol names to
 // Symbols, and generate a graph between InputSections with the provided
 // weights.
-CallGraphSort::CallGraphSort() {
-  MapVector<SectionPair, uint64_t> &profile = config->callGraphProfile;
+macho::PriorityBuilder::CallGraphSort::CallGraphSort(
+    PriorityBuilder &priorityBuilder)
+    : builder(priorityBuilder) {
   DenseMap<const InputSection *, int> secToCluster;
 
   auto getOrCreateCluster = [&](const InputSection *isec) -> int {
     auto res = secToCluster.try_emplace(isec, clusters.size());
     if (res.second) {
       sections.push_back(isec);
       clusters.emplace_back(clusters.size(), isec->getSize());
     }
static void mergeClusters(std::vector<Cluster> &cs, Cluster &into, int intoIdx,
   into.size += from.size;
   into.weight += from.weight;
   from.size = 0;
   from.weight = 0;
 }
 
 // Group InputSections into clusters using the Call-Chain Clustering heuristic
 // then sort the clusters by density.
-DenseMap<const InputSection *, size_t> CallGraphSort::run() {
+DenseMap<const InputSection *, size_t>
+macho::PriorityBuilder::CallGraphSort::run() {
   const uint64_t maxClusterSize = target->getPageSize();
 
   // Cluster indices sorted by density.
   std::vector<int> sorted(clusters.size());
   // For union-find.
   std::vector<int> leaders(clusters.size());
 
   std::iota(leaders.begin(), leaders.end(), 0);
for (int leader : sorted)
         if (i == leader)
           break;
       }
   }
 
   return orderMap;
 }
 
-Optional<size_t> macho::PriorityBuilder::getSymbolPriority(const Defined *sym) {
+Optional<size_t>
+macho::PriorityBuilder::getSymbolPriority(const Defined *sym) const {
   if (sym->isAbsolute())
     return None;
 
   auto it = priorities.find(sym->getName());
   if (it == priorities.end())
     return None;
   const SymbolPriorityEntry &entry = it->second;
   const InputFile *f = sym->isec->getFile();
   if (!f)
     return entry.anyObjectFile;
   // We don't use toString(InputFile *) here because it returns the full path
   // for object files, and we only want the basename.
   StringRef filename;
   if (f->archiveName.empty())
     filename = path::filename(f->getName());
   else
     filename = saver().save(path::filename(f->archiveName) + "(" +
                             path::filename(f->getName()) + ")");
   return std::max(entry.objectFiles.lookup(filename), entry.anyObjectFile);
 }
 
-void macho::PriorityBuilder::extractCallGraphProfile() {
+void macho::PriorityBuilder::CallGraphSort::extractCallGraphProfile() {
   TimeTraceScope timeScope("Extract call graph profile");
-  bool hasOrderFile = !priorities.empty();
+  bool hasOrderFile = !builder.priorities.empty();
   for (const InputFile *file : inputFiles) {
     auto *obj = dyn_cast_or_null<ObjFile>(file);
     if (!obj)
       continue;
     for (const CallGraphEntry &entry : obj->callGraph) {
       assert(entry.fromIndex < obj->symbols.size() &&
              entry.toIndex < obj->symbols.size());
       auto *fromSym = dyn_cast_or_null<Defined>(obj->symbols[entry.fromIndex]);
       auto *toSym = dyn_cast_or_null<Defined>(obj->symbols[entry.toIndex]);
       if (!fromSym || !toSym ||
-          (hasOrderFile &&
-           (getSymbolPriority(fromSym) || getSymbolPriority(toSym))))
+          (hasOrderFile && (builder.getSymbolPriority(fromSym) ||
+                            builder.getSymbolPriority(toSym))))
         continue;
-      config->callGraphProfile[{fromSym->isec, toSym->isec}] += entry.count;
+      profile[{fromSym->isec, toSym->isec}] += entry.count;
     }
   }
 }
 
 void macho::PriorityBuilder::parseOrderFile(StringRef path) {
-  assert(config->callGraphProfile.empty() &&
+  assert(callGraphSort.getProfile().empty() &&
          "Order file must be parsed before call graph profile is processed");
   Optional<MemoryBufferRef> buffer = readFile(path);
   if (!buffer) {
     error("Could not read order file at " + path);
     return;
   }
 
   MemoryBufferRef mbref = *buffer;
if (!symbol.empty()) {
         entry.anyObjectFile = std::max(entry.anyObjectFile, priority);
     }
 
     --priority;
   }
   lowestPriority = priority;
 }
 
-// Sort sections by the profile data provided by __LLVM,__cg_profile sections.
-//
-// This first builds a call graph based on the profile data then merges sections
-// according to the C³ heuristic. All clusters are then sorted by a density
-// metric to further improve locality.
-static DenseMap<const InputSection *, size_t> computeCallGraphProfileOrder() {
-  TimeTraceScope timeScope("Call graph profile sort");
-  return CallGraphSort().run();
-}
-
 DenseMap<const InputSection *, size_t>
 macho::PriorityBuilder::buildInputSectionPriorities() {
   DenseMap<const InputSection *, size_t> sectionPriorities;
-  if (config->callGraphProfileSort)
-    sectionPriorities = computeCallGraphProfileOrder();
+  if (config->callGraphProfileSort) {
+    // Sort sections by the profile data provided by __LLVM,__cg_profile
+    // sections.
+    //
+    // This first builds a call graph based on the profile data then merges
+    // sections according to the C³ heuristic. All clusters are then sorted by a
+    // density metric to further improve locality.
+    TimeTraceScope timeScope("Call graph profile sort");
+    sectionPriorities = callGraphSort.run();
+  }
 
   if (priorities.empty())
     return sectionPriorities;
 
   auto addSym = [&](const Defined *sym) {
     Optional<size_t> symbolPriority = getSymbolPriority(sym);
     if (!symbolPriority.hasValue())
       return;