[lld-macho] Allow order files and call graph sorting to be used together

[lgrey]

Summary

If both an order file and a call graph profile are present, the edges of the call graph which use symbols present in the order file are not used. All of the symbols in the order file will appear at the beginning of the section just as they do currently. In other words, the highest priority derived from the call graph will be below the lowest priority derived from the order file.

Practically, this change renames CallGraphSort.{h,cpp} to SectionPriorities.{h,cpp}, and most order file and call graph profile related code is moved into the new file to reduce duplication.

[oontvoo]

lld/MachO/SectionPriorities.cpp

39

it's confusing that this variable is named with k, which I assume means it's a constant, and yet it's updated by the function below.

(also I think this is a google specific style - the LLVM coding standard seems to suggest camel case only)

254

you're not modifying the symbol

262

You may need to check this against NULL since synthetic symbols don't have InputFile (they'd return NULL)

[lgrey]

Comment round and format

lld/MachO/SectionPriorities.cpp

254

Done (but for my edification: why pointer to const vs. const ref?)

[lgrey]

Update callsites

[lgrey]

Rebase

[oontvoo]

LG - thanks!
(will leave it open for thakis)

lld/MachO/SectionPriorities.cpp

254

(commented below also - I suggested const* because the objects themselves are stored as pointers, so you can avoid the whole deref + taking address trip. Also it's not common to see const ref in lld code)

372

i would suggest changing this to const Defined* sym too

380

nit: unless you're planning on taking care of this shortly - a bit more info on what to be done here would be helpful

[lgrey]

Ref - > pointer to const in addSym

[lgrey]

lld/MachO/SectionPriorities.cpp

380

I moved this (with minor changes) from Writer.cpp, so I actually have no context on it! I left it in since int3@ (the original author) might still have ideas/plans for it, or at the least as a signpost that there might be an unhandled case (similar proved useful in https://reviews.llvm.org/rGc4b45eeb44fdc49). Would it be better to delete?

[oontvoo]

lld/MachO/SectionPriorities.cpp

380

Ah, ok - I guess let's leave it here then. :)

[lgrey]

Rebase

[lgrey]

Format and rebase

[thakis]

I'd have one commit that does nothing but the file rename, then a 2nd commit that only moves unchanged functions around (both fine to commit directly), and then I'd rebase this on top of that so that it only shows the behavior change.

Having the file name be different from ELF and COFF is a bit unfortunate, but oh well.

[lgrey]

Rebased on rename/function move

[lgrey]

In D117354#3262502, @thakis wrote:

I'd have one commit that does nothing but the file rename, then a 2nd commit that only moves unchanged functions around (both fine to commit directly), and then I'd rebase this on top of that so that it only shows the behavior change.

Having the file name be different from ELF and COFF is a bit unfortunate, but oh well.

Done

[thakis]

Code looks fine to me.

I tried it on Chromium, and apparently there are 542489 from all cg_profile section edges in the .o files, leading to 350079 entries in config->callGraphProfile. The edges are between 122620 isecs, compared to 918787 symbols total. So 800K symbols don't end up with an edge and just 122K do. That feels surprisingly low to me.

(The 542489 seems surprisingly low already: There's ~40k TUs, so that's just 10 call edges per TU on average.)

Maybe I'm holding something wrong locally.

lld/MachO/SectionPriorities.cpp

254

(fwiw, i think references for things that can't be null is fine)

290

I would've expected this to be expensive: In Chromium Framework, we have ~500K of these edges, so this is 1M calls to getSymbolPriority() (which we later call once more for every symbol; there's ~920K symbols). But to my surprise, I can't measure a slowdown from it, so I suppose it's ok.

(The alternative would be to store the symbol's priority in the symbol or its isec and to compute it just once. But, no need, apparently.)

376–377

When does this return non-0? The call graph order omits edges where either start or end have a priority from the order file, so it can only happen if two distinct symbols have the same isec, right? Does this run after ICF? Are there things other than ICF that could trigger it?

[lgrey]

lld/MachO/SectionPriorities.cpp

376–377

In the absence of call graph sorting, this is the same logic as currently unless I broke something. I'll get back to you about ICF, but there's N_ALT_ENTRY (also theoretically a problem if there are multiple symbols via N_ALT_ENTRY and one is an order file and another has a CG edge; I think this is rare and mostly covered by order file priorities being higher).

lld/MachO/Driver.cpp

static void addFileList(StringRef path, bool isLazy) {
   Optional<MemoryBufferRef> buffer = readFile(path);
   if (!buffer)
     return;
   MemoryBufferRef mbref = *buffer;
   for (StringRef path : args::getLines(mbref))
     addFile(rerootPath(path), ForceLoad::Default, isLazy);
 }
 
-// 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.)
-//
-// The file can also have line comments that start with '#'.
 // We expect sub-library names of the form "libfoo", which will match a dylib
 // with a path of .*/libfoo.{dylib, tbd}.
 // XXX ld64 seems to ignore the extension entirely when matching sub-libraries;
 // I'm not sure what the use case for that is.
 static bool markReexport(StringRef searchName, ArrayRef<StringRef> extensions) {
   for (InputFile *file : inputFiles) {
     if (auto *dylibFile = dyn_cast<DylibFile>(file)) {
       StringRef filename = path::filename(dylibFile->getName());
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()) {
+    if (!orderFile.empty())
       parseOrderFile(orderFile);
-      config->callGraphProfileSort = false;
-    }
 
     referenceStubBinder();
 
     // FIXME: should terminate the link early based on errors encountered so
     // far?
 
     createSyntheticSections();
     createSyntheticSymbols();

lld/MachO/SectionPriorities.h

 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. If neither is present, an empty map is returned.
+// 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();
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/SectionPriorities.cpp

 ///
 //===----------------------------------------------------------------------===//
 
 #include "SectionPriorities.h"
 #include "Config.h"
 #include "InputFiles.h"
 #include "Symbols.h"
 #include "Target.h"
+
 #include "lld/Common/Args.h"
 #include "lld/Common/CommonLinkerContext.h"
 #include "lld/Common/ErrorHandler.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/TimeProfiler.h"
 #include "llvm/Support/raw_ostream.h"
 #include <numeric>
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace llvm::sys;
 using namespace lld;
 using namespace lld::macho;
 
 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) {}
 
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 = clusters.size();
+  int curOrder = lowestPriority;
   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 size_t getSymbolPriority(const SymbolPriorityEntry &entry,
-                                const InputFile *f) {
+static Optional<size_t> getSymbolPriority(const Defined *sym) {
+  if (sym->isAbsolute())
+    return None;
+
+  auto it = config->priorities.find(sym->getName());
+  if (it == config->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() {
   TimeTraceScope timeScope("Extract call graph profile");
+  bool hasOrderFile = !config->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)
+      if (!fromSym || !toSym ||
+          (hasOrderFile &&
+           (getSymbolPriority(fromSym) || getSymbolPriority(toSym))))
         continue;
       config->callGraphProfile[{fromSym->isec, toSym->isec}] += entry.count;
     }
   }
 }
 
 void macho::parseOrderFile(StringRef path) {
+  assert(config->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();
if (!symbol.empty()) {
       if (!objectFile.empty())
         entry.objectFiles.insert(std::make_pair(objectFile, priority));
       else
         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();
 }
 
-// Each section gets assigned the priority of the highest-priority symbol it
-// contains.
 DenseMap<const InputSection *, size_t> macho::buildInputSectionPriorities() {
-  if (config->callGraphProfileSort)
-    return computeCallGraphProfileOrder();
   DenseMap<const InputSection *, size_t> sectionPriorities;
+  if (config->callGraphProfileSort)
+    sectionPriorities = computeCallGraphProfileOrder();
 
   if (config->priorities.empty())
     return sectionPriorities;
 
-  auto addSym = [&](Defined &sym) {
-    if (sym.isAbsolute())
-      return;
-
-    auto it = config->priorities.find(sym.getName());
-    if (it == config->priorities.end())
+  auto addSym = [&](const Defined *sym) {
+    Optional<size_t> symbolPriority = getSymbolPriority(sym);
+    if (!symbolPriority.hasValue())
       return;
-
-    SymbolPriorityEntry &entry = it->second;
-    size_t &priority = sectionPriorities[sym.isec];
-    priority =
-        std::max(priority, getSymbolPriority(entry, sym.isec->getFile()));
+    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);
+          addSym(d);
   }
 
   return sectionPriorities;
 }

lld/test/MachO/cgprofile-orderfile.s

+# REQUIRES: x86
+
+# RUN: rm -rf %t; split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/test.s -o %t/test.o
+
+# RUN: %lld -e A %t/test.o -order_file %t/order_file -o %t/test 
+# RUN: llvm-nm --numeric-sort %t/test | FileCheck %s
+# RUN: %lld -e A %t/test.o -o %t/test 
+# RUN: llvm-nm --numeric-sort %t/test | FileCheck %s --check-prefix NO-ORDER
+
+
+#--- order_file
+B
+A
+
+#--- test.s
+
+.text
+    .globl  D
+D:
+    retq
+
+    .globl  C
+C:
+    retq
+
+    .globl  B
+B:
+    retq
+
+    .globl  A
+A:
+    retq
+
+.cg_profile A, B, 100
+.cg_profile A, C,  40
+.cg_profile C, D,  61
+
+.subsections_via_symbols
+
+# CHECK:      T B
+# CHECK-NEXT: T A
+# CHECK-NEXT: T C
+# CHECK-NEXT: T D
+
+# NO-ORDER:      T A
+# NO-ORDER-NEXT: T B
+# NO-ORDER-NEXT: T C
+# NO-ORDER-NEXT: T D
+