[lld][Macho][NFC] Encapsulate priorities map in a priority class

[Roger]

Summary

config->priorities has been used to hold the intermediate state during the construction of the order in which sections should be laid out. This is not a good place to hold this state since the intermediate state is not a "configuration" for LLD. It should be encapsulated in a class for building a mapping from section to priority (which I created in this diff as the PriorityBuilder class).

The same thing is being done for config->callGraphProfile.

[int3]

lld/MachO/SectionPriorities.cpp

37–38

I don't think this needs to be a pointer (can just be a PriorityBuilder)

[Roger]

Added config->callGraphProfile to PriorityBuilder

[Roger]

I applied the same idea to config->callGraphProfile. @int3 Could you take a look?

[Roger]

Change PriorityBuilder from a unique pointer to a regular object.

[Roger]

Remove duplicated code representing "maximum priority"

[int3]

lld/MachO/SectionPriorities.cpp

305

I think you're confused about the intention of the code. numeric_limits::max() is the *highest* priority, not the lowest. But it's used to initialize the default value of the lowestPriority variable because if there are no entries in the order file, then the lowest priority is also the highest priority.

Now that we have the PriorityBuilder class, I think lowestPriority can be a member there. And maybe add a comment so future readers won't get confused :)

[Roger]

lld/MachO/SectionPriorities.cpp

305

lowestPriority actually represents the highest priority that has not been assigned (ie, the priority lower than the lowest priority that has so far been assigned). lowestPriority is used to keep track of the highest priority CallGraphSort should use because the code aims to make sure that all priorities assigned by CallGraphSort should be lower than those assigned by the order file.

At the time this line of code is called, lowestPriority will always be set to its initial value of std::numeric_limits<size_t>::max(). There is no need to specify std::numeric_limits<size_t>::max() both here and at the initialization of lowestPriority.

I considered making lowestPriority a member of PriorityBuilder but it would be a bit more than just moving the field and changing some names because lowestPriority is read and written to by CallGraphSort as well. I didn't include that change here but it could possibly be done.

[thevinster]

lld/MachO/SectionPriorities.cpp

37

nit: Since we are already namespacing macho, can we drop the macho:: everywhere in this file?

[Roger]

lld/MachO/SectionPriorities.cpp

37

the code does not compile without macho::. I'm not sure exactly why but it appears to be necessary.

[int3]

lld/MachO/SectionPriorities.cpp

37

not for declarations :)

macho:: here tells the compiler that this is a declaration in the macho:: namespace, not the global one.

305

ah okay, I see how you're thinking about it. I still think priority = lowestPriority is confusing though, because it's not obvious that we really mean "lowest priority unassigned by the order file" instead of "lowest possible priority". Also come to think of it, the local priority variable is kind of redundant. How about using lowestPriority directly but renaming it to something like lowestUnusedPriority?

[Roger]

lld/MachO/SectionPriorities.cpp

305

Actually, it may be better to rename lowestPriority to highestAvailablePriority.

[int3]

lld/MachO/SectionPriorities.cpp

305

sgtm

[Roger]

Rename lowestPriority to highestAvailablePriority.

[Roger]

lld/MachO/SectionPriorities.cpp

305

As I was reading the code, I got the sense that assigning priority = lowestPriority was done intentionally. I was wondering if this is a speed optimization (incrementing the stack copy priority many times and writing to the global lowestPriority just at the end). WDYT?

[int3]

lld/MachO/SectionPriorities.cpp

305

As I was reading the code, I got the sense that assigning priority = lowestPriority was done intentionally. I was wondering if this is a speed optimization (incrementing the stack copy priority many times and writing to the global lowestPriority just at the end). WDYT?

I don't think you posted this comment before I replied (my "sgtm" was in response to the rename), but it seems like Phab has recorded them out of order...

I doubt it's an intentional speed optimization; the difference is really not that significant, and I would expect a comment or something if profiling had indeed identified this as a bottleneck. Otherwise it's just unnecessary microoptimization :)

Also given that it's a static, there's a decent chance the compiler can optimize it anyway.

[Roger]

Get rid of unnecessary priority variable.

[Roger]

lld/MachO/SectionPriorities.cpp

305

Gotcha. I removed the priority variable.

[int3]

lld/MachO/SectionPriorities.cpp

252

oh yeah -- unlike global functions, class method definitions don't actually need the macho:: prefix (I believe because clang first performs name lookup on PriorityBuilder, so it knows in which namespace this code belongs to)

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::DenseMap<llvm::StringRef, SymbolPriorityEntry> priorities;
-  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/Driver.cpp

if (config->timeTraceEnabled)
     for (const Arg *arg : args.filtered(OPT_mllvm))
       parseClangOption(arg->getValue(), arg->getSpelling());
 
     compileBitcodeFiles();
     replaceCommonSymbols();
 
     StringRef orderFile = args.getLastArgValue(OPT_order_file);
     if (!orderFile.empty())
-      parseOrderFile(orderFile);
+      priorityBuilder.parseOrderFile(orderFile);
 
     referenceStubBinder();
 
     // FIXME: should terminate the link early based on errors encountered so
     // far?
 
     createSyntheticSections();
     createSyntheticSymbols();
if (config->timeTraceEnabled)
     for (const Arg *arg : args.filtered(OPT_add_empty_section)) {
       StringRef segName = arg->getValue(0);
       StringRef sectName = arg->getValue(1);
       inputFiles.insert(make<OpaqueFile>(MemoryBufferRef(), segName, sectName));
     }
 
     gatherInputSections();
     if (config->callGraphProfileSort)
-      extractCallGraphProfile();
+      priorityBuilder.extractCallGraphProfile();
 
     if (config->deadStrip)
       markLive();
 
     // ICF assumes that all literals have been folded already, so we must run
     // foldIdenticalLiterals before foldIdenticalSections.
     foldIdenticalLiterals();
     if (config->icfLevel != ICFLevel::none)

lld/MachO/SectionPriorities.h

 #define LLD_MACHO_SECTION_PRIORITIES_H
 
 #include "InputSection.h"
 #include "llvm/ADT/DenseMap.h"
 
 namespace lld {
 namespace macho {
 
+using SectionPair = std::pair<const InputSection *, const InputSection *>;
+
+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.
+  // 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();
 
   // 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
   // matches any symbol of that name. Parsing this format is not quite
   // straightforward because the symbol name itself can contain colons, so when
   // encountering a colon, we consider the preceding characters to decide if it
   // can be a valid CPU type or file path.
   //
-// If a symbol is matched by multiple entries, then it takes the lowest-ordered
-// entry (the one nearest to the front of the list.)
+  // If a symbol is matched by multiple entries, then it takes the
+  // lowest-ordered entry (the one nearest to the front of the list.)
   //
   // The file can also have line comments that start with '#'.
   void parseOrderFile(StringRef path);
 
   // Returns layout priorities for some or all input sections. Sections are laid
   // out in decreasing order; that is, a higher priority section will be closer
   // to the beginning of its output section.
   //
   // If either an order file or a call graph profile are present, this is used
   // as the source of priorities. If both are present, the order file takes
   // 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::DenseMap<llvm::StringRef, SymbolPriorityEntry> priorities;
+  llvm::MapVector<SectionPair, uint64_t> callGraphProfile;
+};
+
+extern PriorityBuilder priorityBuilder;
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/SectionPriorities.cpp

 #include <numeric>
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace llvm::sys;
 using namespace lld;
 using namespace lld::macho;
 
+PriorityBuilder macho::priorityBuilder;
+
 namespace {
 
-size_t lowestPriority = std::numeric_limits<size_t>::max();
+size_t highestAvailablePriority = 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) {}
struct Cluster {
   uint64_t size;
   uint64_t weight = 0;
   uint64_t initialWeight = 0;
   Edge bestPred = {-1, 0};
 };
 
 class CallGraphSort {
 public:
-  CallGraphSort();
+  CallGraphSort(const MapVector<SectionPair, uint64_t> &profile);
 
   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;
+// Take the edge list in callGraphProfile, resolve symbol names to Symbols, and
+// generate a graph between InputSections with the provided weights.
+CallGraphSort::CallGraphSort(const MapVector<SectionPair, uint64_t> &profile) {
   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());
     }
     return res.first->second;
   };
 
   // Create the graph
-  for (std::pair<SectionPair, uint64_t> &c : profile) {
+  for (const std::pair<SectionPair, uint64_t> &c : profile) {
     const auto fromSec = c.first.first->canonical();
     const auto toSec = c.first.second->canonical();
     uint64_t weight = c.second;
     // Ignore edges between input sections belonging to different output
     // sections.  This is done because otherwise we would end up with clusters
     // containing input sections that can't actually be placed adjacently in the
     // output.  This messes with the cluster size and density calculations.  We
     // would also end up moving input sections in other output sections without
DenseMap<const InputSection *, size_t> CallGraphSort::run() {
   });
 
   DenseMap<const InputSection *, size_t> orderMap;
 
   // Sections will be sorted by decreasing order. Absent sections will have
   // priority 0 and be placed at the end of sections.
   // NB: This is opposite from COFF/ELF to be compatible with the existing
   // order-file code.
-  int curOrder = lowestPriority;
+  int curOrder = highestAvailablePriority;
   for (int leader : sorted) {
     for (int i = leader;;) {
       orderMap[sections[i]] = curOrder--;
       i = clusters[i].next;
       if (i == leader)
         break;
     }
   }
for (int leader : sorted)
         if (i == leader)
           break;
       }
   }
 
   return orderMap;
 }
 
-static Optional<size_t> getSymbolPriority(const Defined *sym) {
+Optional<size_t> macho::PriorityBuilder::getSymbolPriority(const Defined *sym) {
   if (sym->isAbsolute())
     return None;
 
-  auto it = config->priorities.find(sym->getName());
-  if (it == config->priorities.end())
+  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::extractCallGraphProfile() {
+void macho::PriorityBuilder::extractCallGraphProfile() {
   TimeTraceScope timeScope("Extract call graph profile");
-  bool hasOrderFile = !config->priorities.empty();
+  bool hasOrderFile = !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))))
         continue;
-      config->callGraphProfile[{fromSym->isec, toSym->isec}] += entry.count;
+      callGraphProfile[{fromSym->isec, toSym->isec}] += entry.count;
     }
   }
 }
 
-void macho::parseOrderFile(StringRef path) {
-  assert(config->callGraphProfile.empty() &&
+void macho::PriorityBuilder::parseOrderFile(StringRef path) {
+  assert(callGraphProfile.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;
-  size_t priority = std::numeric_limits<size_t>::max();
+  size_t priority = highestAvailablePriority;
   for (StringRef line : args::getLines(mbref)) {
     StringRef objectFile, symbol;
     line = line.take_until([](char c) { return c == '#'; }); // ignore comments
     line = line.ltrim();
 
     CPUType cpuType = StringSwitch<CPUType>(line)
                           .StartsWith("i386:", CPU_TYPE_I386)
                           .StartsWith("x86_64:", CPU_TYPE_X86_64)
for (StringRef fileEnd : fileEnds) {
         objectFile = line.take_front(pos + fileEnd.size() - 1);
         line = line.drop_front(pos + fileEnd.size());
         break;
       }
     }
     symbol = line.trim();
 
     if (!symbol.empty()) {
-      SymbolPriorityEntry &entry = config->priorities[symbol];
+      SymbolPriorityEntry &entry = priorities[symbol];
       if (!objectFile.empty())
         entry.objectFiles.insert(std::make_pair(objectFile, priority));
       else
         entry.anyObjectFile = std::max(entry.anyObjectFile, priority);
     }
 
     --priority;
   }
-  lowestPriority = priority;
+  highestAvailablePriority = priority;
 }
 
-// Sort sections by the profile data provided by __LLVM,__cg_profile sections.
+DenseMap<const InputSection *, size_t>
+macho::PriorityBuilder::buildInputSectionPriorities() {
+  DenseMap<const InputSection *, size_t> sectionPriorities;
+  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.
-static DenseMap<const InputSection *, size_t> computeCallGraphProfileOrder() {
+    // 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");
-  return CallGraphSort().run();
+    sectionPriorities = CallGraphSort(callGraphProfile).run();
   }
 
-DenseMap<const InputSection *, size_t> macho::buildInputSectionPriorities() {
-  DenseMap<const InputSection *, size_t> sectionPriorities;
-  if (config->callGraphProfileSort)
-    sectionPriorities = computeCallGraphProfileOrder();
-
-  if (config->priorities.empty())
+  if (priorities.empty())
     return sectionPriorities;
 
   auto addSym = [&](const Defined *sym) {
     Optional<size_t> symbolPriority = getSymbolPriority(sym);
     if (!symbolPriority.hasValue())
       return;
     size_t &priority = sectionPriorities[sym->isec];
     priority = std::max(priority, symbolPriority.getValue());

lld/MachO/Writer.cpp

 // Sorting only can happen once all outputs have been collected. Here we sort
 // segments, output sections within each segment, and input sections within each
 // output segment.
 static void sortSegmentsAndSections() {
   TimeTraceScope timeScope("Sort segments and sections");
   sortOutputSegments();
 
   DenseMap<const InputSection *, size_t> isecPriorities =
-      buildInputSectionPriorities();
+      priorityBuilder.buildInputSectionPriorities();
 
   uint32_t sectionIndex = 0;
   for (OutputSegment *seg : outputSegments) {
     seg->sortOutputSections();
     // References from thread-local variable sections are treated as offsets
     // relative to the start of the thread-local data memory area, which
     // is initialized via copying all the TLV data sections (which are all
     // contiguous). If later data sections require a greater alignment than