[lld-macho] Consolidate all priority assignments under `buildInputSectionPriorities()`

[Roger]

Summary

The previous code assigned priorities for sections across different call stacks from Driver.cpp. The data gathered to assign priorities seems to be spread across different call stacks by necessity (test fails when I try to put them all together). However, the actual priority assignments do not need to be. After all of the relevant data has been collected, we can make all the priority assignments under one function (ie, buildInputSectionPriorities()) specific for that purpose. This is the change for this diff.

This diff is almost completely a NFC but there is one slight functional change that I believe corrects a bug. The existing code for extractCallGraphProfile() filters data about calls from or to symbols that already has a priority (based on the order file). There are two ways for a symbol to have a priority at that point in time:

1. The symbol is specifically referenced by name and its order file in the order file.
2. The symbol is indirectly referenced by an entry in the order file that contains its name but specifies no order file.

If two order files each have a symbol using the same name and the order file includes one of the symbols (specifying its order file), the existing code produced a side effect of giving all symbols of the same name a default priority of zero. Having a priority of zero is not the same as having no priority at all as now those symbols with default priority zero will have their calls ignored by extractCallGraphProfile().

My diff changes this behavior so that an entry in the order file for one symbol in a specific object file will have no effect on the priority of symbols with the same name in other object files.

[Roger]

Update

[Roger]

Rebase

[Roger]

add comment

[Roger]

Ready for review

lld/MachO/SectionPriorities.cpp

323–325

honestly, this condition feels a little weird to me because this boolean can short circuit the expression and skip checking for symbol priority, but this also skips checking if the symbol is absolute/not.

I'm just retaining the existing logic, but I question the correctness of the existing logic.

[Roger]

After having spoken to @int3 , we decided to adjust the code in a couple ways so I'll be reworking this diff.

lld/MachO/Driver.cpp

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()) {
       priorityBuilder.parseOrderFile(orderFile);
-      priorityBuilder.populatePriorities();
     }
 
     referenceStubBinder();
 
     // FIXME: should terminate the link early based on errors encountered so
     // far?
 
     createSyntheticSections();

lld/MachO/SectionPriorities.h

 //===- SectionPriorities.h --------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_MACHO_SECTION_PRIORITIES_H
 #define LLD_MACHO_SECTION_PRIORITIES_H
 
 #include "InputSection.h"
 #include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/SetVector.h"
 
 namespace lld {
 namespace macho {
 
 using SectionPair = std::pair<const InputSection *, const InputSection *>;
 
 class PriorityBuilder {
 public:
public:
   // 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.)
   //
   // The file can also have line comments that start with '#'.
   void parseOrderFile(StringRef path);
 
-  // Constructs internal mapping of section to priority based on order file
-  // data.
-  //
-  // Should only be called after `parseOrderFile()`.
-  void populatePriorities();
-
   // 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:
-  // The symbol with the highest priority should be ordered first in the output
-  // section (modulo input section contiguity constraints). Using priority
-  // (highest first) instead of order (lowest first) has the convenient property
-  // that the default-constructed zero priority -- for symbols/sections without
-  // a user-defined order -- naturally ends up putting them at the end of the
-  // output.
-  struct SymbolPriorityEntry {
-    // The priority given to a matching symbol, regardless of which object file
-    // it originated from.
-    size_t anyObjectFile = 0;
-    // The priority given to a matching symbol from a particular object file.
-    llvm::DenseMap<llvm::StringRef, size_t> objectFiles;
-  };
-
-  llvm::Optional<size_t> getSymbolPriority(const Defined *sym);
+  // Represents a symbol specification.
+  // First element holds a symbol name.
+  // The second element holds an object file name or an empty string if we want
+  // to specify all symbols of a given name.
+  using SymbolSpecification = std::pair<std::string, std::string>;
+  using SymbolOrder =
+      llvm::SetVector<SymbolSpecification, std::vector<SymbolSpecification>,
+                      std::set<SymbolSpecification>>;
 
-  using SymbolObjectFile = std::pair<std::string, std::string>;
-  using SymbolOrder = llvm::SmallVector<SymbolObjectFile, 0>;
+private:
   // This will be populated with symbols ordered so that the earlier
   // symbols will have higher priority than the later symbols.
   SymbolOrder inputOrder;
-  llvm::DenseMap<llvm::StringRef, SymbolPriorityEntry> priorities;
   llvm::MapVector<SectionPair, uint64_t> callGraphProfile;
 };
 
 extern PriorityBuilder priorityBuilder;
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/SectionPriorities.cpp

 using namespace llvm::MachO;
 using namespace llvm::sys;
 using namespace lld;
 using namespace lld::macho;
 
 PriorityBuilder macho::priorityBuilder;
 
 namespace {
-
+struct SymbolPriorityEntry;
+using SymbolPriorites = llvm::DenseMap<llvm::StringRef, SymbolPriorityEntry>;
 size_t highestAvailablePriority = std::numeric_limits<size_t>::max();
 
+// The symbol with the highest priority should be ordered first in the output
+// section (modulo input section contiguity constraints). Using priority
+// (highest first) instead of order (lowest first) has the convenient property
+// that the default-constructed zero priority -- for symbols/sections without
+// a user-defined order -- naturally ends up putting them at the end of the
+// output.
+struct SymbolPriorityEntry {
+  // The priority given to a matching symbol, regardless of which object file
+  // it originated from.
+  size_t anyObjectFile = 0;
+  // The priority given to a matching symbol from a particular object file.
+  llvm::DenseMap<llvm::StringRef, size_t> objectFiles;
+};
+
 struct Edge {
   int from;
   uint64_t weight;
 };
 
 struct Cluster {
   Cluster(int sec, size_t s) : next(sec), prev(sec), size(s) {}
 
for (int leader : sorted)
         if (i == leader)
           break;
       }
   }
 
   return orderMap;
 }
 
-Optional<size_t> macho::PriorityBuilder::getSymbolPriority(const Defined *sym) {
+// Returns how an order file would specify this file.
+// ie, "(archive_name_base_name)object_file_base_name"
+static StringRef getOrderFileName(const InputFile &file) {
+  if (file.archiveName.empty())
+    return path::filename(file.getName());
+  return saver().save(path::filename(file.archiveName) + "(" +
+                      path::filename(file.getName()) + ")");
+}
+
+Optional<size_t> getSymbolPriority(const SymbolPriorites &priorities,
+                                   const Defined *sym) {
   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()) + ")");
+  StringRef filename = getOrderFileName(*f);
   return std::max(entry.objectFiles.lookup(filename), entry.anyObjectFile);
 }
 
+// Return true iff symbolOrder contains `symbol` with the provided `objectFile`
+// or with no object file.
+bool isOrdered(const Defined &symbol, StringRef objectFile,
+               const PriorityBuilder::SymbolOrder &symbolOrder) {
+  if (symbol.isAbsolute())
+    return true;
+
+  auto symbolWithoutFile = std::make_pair(symbol.getName().str(), "");
+  if (symbolOrder.contains(symbolWithoutFile)) {
+    return true;
+  }
+
+  auto symbolWithFile = std::make_pair(symbol.getName().str(), objectFile.str());
+  return symbolOrder.contains(symbolWithFile);
+}
+
 void macho::PriorityBuilder::extractCallGraphProfile() {
   TimeTraceScope timeScope("Extract call graph profile");
-  bool hasOrderFile = !priorities.empty();
+  bool hasInputOrder = !inputOrder.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))))
+          (!hasInputOrder ||
+           (!isOrdered(*fromSym, getOrderFileName(*file), inputOrder) &&
+            !isOrdered(*toSym, getOrderFileName(*file), inputOrder))))
         callGraphProfile[{fromSym->isec, toSym->isec}] += entry.count;
     }
   }
 }
 
 void macho::PriorityBuilder::parseOrderFile(StringRef path) {
   assert(callGraphProfile.empty() &&
          "Order file must be parsed before call graph profile is processed");
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()) {
-      inputOrder.push_back(std::make_pair(symbol.str(), objectFile.str()));
+      inputOrder.insert(std::make_pair(symbol.str(), objectFile.str()));
     }
   }
 }
 
-void macho::PriorityBuilder::populatePriorities() {
+static SymbolPriorites
+populatePriorities(const PriorityBuilder::SymbolOrder &inputOrder) {
+  SymbolPriorites priorities;
   for (const auto &symbolObjectFile : inputOrder) {
     StringRef symbol = symbolObjectFile.first;
     StringRef objectFile = symbolObjectFile.second;
     SymbolPriorityEntry &entry = priorities[symbol];
     if (!objectFile.empty())
       entry.objectFiles.insert(
           std::make_pair(objectFile, highestAvailablePriority));
     else
       entry.anyObjectFile =
           std::max(entry.anyObjectFile, highestAvailablePriority);
 
     --highestAvailablePriority;
   }
+  return priorities;
 }
 
 DenseMap<const InputSection *, size_t>
 macho::PriorityBuilder::buildInputSectionPriorities() {
+  SymbolPriorites priorities = populatePriorities(inputOrder);
   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.
     TimeTraceScope timeScope("Call graph profile sort");
     sectionPriorities = CallGraphSort(callGraphProfile).run();
   }
 
   if (priorities.empty())
     return sectionPriorities;
 
   auto addSym = [&](const Defined *sym) {
-    Optional<size_t> symbolPriority = getSymbolPriority(sym);
+    Optional<size_t> symbolPriority = getSymbolPriority(priorities, sym);
     if (!symbolPriority.hasValue())
       return;
     size_t &priority = sectionPriorities[sym->isec];
     priority = std::max(priority, symbolPriority.getValue());
   };
 
   // TODO: Make sure this handles weak symbols correctly.
   for (const InputFile *file : inputFiles) {
     if (isa<ObjFile>(file))
       for (Symbol *sym : file->symbols)
         if (auto *d = dyn_cast_or_null<Defined>(sym))
           addSym(d);
   }
 
   return sectionPriorities;
 }