[lld-macho] Port CallGraphSort from COFF/ELF

[lgrey]

Summary

Depends on D112160

This adds the new options --call-graph-profile-sort (default), --no-call-graph-profile-sort and --print-symbol-order=. If call graph profile sorting is enabled, reads __LLVM,__cg_profile sections from object files and uses the resulting graph to put callees and callers close to each other in the final binary via the C3 clustering heuristic.

[lgrey]

lld/MachO/CallGraphSort.cpp

153

ELF/COFF use a larger constant but the original paper says page size and I couldn't find anything in history/reviews that motivates the larger number.

lld/MachO/InputFiles.cpp

308

I couldn't find prior art on finding endianness, though there's code elsewhere that assumes little. Is there a better way to do this?

[lgrey]

Removed strays from test

[tschuett]

There are some effects when 4k pages are backed by contiguous physical memory, but that probably needs a custom loader:
https://docs.mellanox.com/display/rdmacore50/Contiguous+Pages

[lgrey]

Format

[oontvoo]

lld/MachO/CallGraphSort.cpp

252

TimeTraceScope here? (as it'd be doing non-negligible amount of work)

lld/MachO/CallGraphSort.h

17

why not #include the header instead?
(you'll need it in the .cpp anyway)

lld/MachO/Driver.cpp

1035

[optional] perhaps add a TimeTraceScope here?

1445

only if callGraphProfileSort==true ?

lld/MachO/InputFiles.cpp

308

I think the unwritten assumption here is that macho is all little-endian now.

lld/MachO/InputFiles.h

61

would be helpful to have some comment clarifying on "Index" into what.

[lgrey]

Address comments: document CallGraphEntry struct, add time traces, only extract data if --call-graph-profile-sort, shuffle includes

[lgrey]

Format

[MaskRay]

Any performance number? This is a very minor optimization and probably rarely doesn't really benefit mobile/desktop applications.

[lgrey]

Windows Chrome got 3% on Speedometer from adding this. Locally on Chromium Mac, I'm seeing about the same thing (3.3% if I'm measuring correctly: means of 151 vs 156 with similar confidence intervals).

[MaskRay]

In D112164#3094587, @lgrey wrote:

Windows Chrome got 3% on Speedometer from adding this. Locally on Chromium Mac, I'm seeing about the same thing (3.3% if I'm measuring correctly: means of 151 vs 156 with similar confidence intervals).

Ah, nice. Thanks for the number.

lld/MachO/CallGraphSort.cpp

233

https://llvm.org/docs/CodingStandards.html#don-t-use-braces-on-simple-single-statement-bodies-of-if-else-loop-statements

[lgrey]

Remove braces around single-line if

[thakis]

Cool.

lld/MachO/Driver.cpp

1401

should we warn if there's both an explicit --call-graph-profile-sort flag and an -order_file flag? Or maybe later when we know that there's call graph info in the .o file but also an order file?

(…or are you planning on adding support for both flags at the same time in a follow-up?)

lld/MachO/InputFiles.cpp

307

Should this have a TimeTrace too?

lld/MachO/Options.td

77

nit: Put just (default) here, and omit it from the line below. That's consistent with the rest of the help texts.

[lgrey]

Var renames, missing newline

[lgrey]

Restore accidentally stomped diff

[lgrey]

Add time trace for parsing section, options edit

lld/MachO/Driver.cpp

1401

Yes, planning to add support to both as a follow-up

lld/MachO/CMakeLists.txt

 set(LLVM_TARGET_DEFINITIONS Options.td)
 tablegen(LLVM Options.inc -gen-opt-parser-defs)
 add_public_tablegen_target(MachOOptionsTableGen)
 
 include_directories(${LLVM_MAIN_SRC_DIR}/../libunwind/include)
 
 add_lld_library(lldMachO
   Arch/ARM.cpp
   Arch/ARM64.cpp
   Arch/ARM64Common.cpp
   Arch/ARM64_32.cpp
   Arch/X86_64.cpp
+  CallGraphSort.cpp
   ConcatOutputSection.cpp
   Driver.cpp
   DriverUtils.cpp
   Dwarf.cpp
   ExportTrie.cpp
   ICF.cpp
   InputFiles.cpp
   InputSection.cpp

lld/MachO/CallGraphSort.h

+//===- CallGraphSort.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_CALL_GRAPH_SORT_H
+#define LLD_MACHO_CALL_GRAPH_SORT_H
+
+#include "InputSection.h"
+#include "llvm/ADT/DenseMap.h"
+
+namespace lld {
+namespace macho {
+
+llvm::DenseMap<const InputSection *, size_t> computeCallGraphProfileOrder();
+} // namespace macho
+} // namespace lld
+
+#endif

lld/MachO/CallGraphSort.cpp

+//===- CallGraphSort.cpp --------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+///
+/// This is based on the ELF port, see ELF/CallGraphSort.cpp for the details
+/// about the algorithm.
+///
+//===----------------------------------------------------------------------===//
+
+#include "CallGraphSort.h"
+#include "Config.h"
+#include "InputFiles.h"
+#include "Symbols.h"
+#include "Target.h"
+#include "lld/Common/ErrorHandler.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/MapVector.h"
+#include "llvm/Support/TimeProfiler.h"
+#include "llvm/Support/raw_ostream.h"
+#include <numeric>
+
+using namespace llvm;
+using namespace lld;
+using namespace lld::macho;
+
+namespace {
+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;
+  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) {
+    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
+    // moving them closer to what calls them.
+    if (fromSec->parent != toSec->parent)
+      continue;
+
+    int from = getOrCreateCluster(fromSec);
+    int to = getOrCreateCluster(toSec);
+
+    clusters[to].weight += weight;
+
+    if (from == to)
+      continue;
+
+    // Remember the best edge.
+    Cluster &toC = clusters[to];
+    if (toC.bestPred.from == -1 || toC.bestPred.weight < weight) {
+      toC.bestPred.from = from;
+      toC.bestPred.weight = weight;
+    }
+  }
+  for (Cluster &c : clusters)
+    c.initialWeight = c.weight;
+}
+
+// It's bad to merge clusters which would degrade the density too much.
+static bool isNewDensityBad(Cluster &a, Cluster &b) {
+  double newDensity = double(a.weight + b.weight) / double(a.size + b.size);
+  return newDensity < a.getDensity() / MAX_DENSITY_DEGRADATION;
+}
+
+// Find the leader of V's belonged cluster (represented as an equivalence
+// class). We apply union-find path-halving technique (simple to implement) in
+// the meantime as it decreases depths and the time complexity.
+static int getLeader(std::vector<int> &leaders, int v) {
+  while (leaders[v] != v) {
+    leaders[v] = leaders[leaders[v]];
+    v = leaders[v];
+  }
+  return v;
+}
+
+static void mergeClusters(std::vector<Cluster> &cs, Cluster &into, int intoIdx,
+                          Cluster &from, int fromIdx) {
+  int tail1 = into.prev, tail2 = from.prev;
+  into.prev = tail2;
+  cs[tail2].next = intoIdx;
+  from.prev = tail1;
+  cs[tail1].next = fromIdx;
+  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() {
+  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);
+  std::iota(sorted.begin(), sorted.end(), 0);
+
+  llvm::stable_sort(sorted, [&](int a, int b) {
+    return clusters[a].getDensity() > clusters[b].getDensity();
+  });
+
+  for (int l : sorted) {
+    // The cluster index is the same as the index of its leader here because
+    // clusters[L] has not been merged into another cluster yet.
+    Cluster &c = clusters[l];
+
+    // Don't consider merging if the edge is unlikely.
+    if (c.bestPred.from == -1 || c.bestPred.weight * 10 <= c.initialWeight)
+      continue;
+
+    int predL = getLeader(leaders, c.bestPred.from);
+    // Already in the same cluster.
+    if (l == predL)
+      continue;
+
+    Cluster *predC = &clusters[predL];
+    if (c.size + predC->size > maxClusterSize)
+      continue;
+
+    if (isNewDensityBad(*predC, c))
+      continue;
+
+    leaders[l] = predL;
+    mergeClusters(clusters, *predC, predL, c, l);
+  }
+  // Sort remaining non-empty clusters by density.
+  sorted.clear();
+  for (int i = 0, e = (int)clusters.size(); i != e; ++i)
+    if (clusters[i].size > 0)
+      sorted.push_back(i);
+  llvm::stable_sort(sorted, [&](int a, int b) {
+    return clusters[a].getDensity() > clusters[b].getDensity();
+  });
+
+  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();
+  for (int leader : sorted) {
+    for (int i = leader;;) {
+      orderMap[sections[i]] = curOrder--;
+      i = clusters[i].next;
+      if (i == leader)
+        break;
+    }
+  }
+  if (!config->printSymbolOrder.empty()) {
+    std::error_code ec;
+    raw_fd_ostream os(config->printSymbolOrder, ec, sys::fs::OF_None);
+    if (ec) {
+      error("cannot open " + config->printSymbolOrder + ": " + ec.message());
+      return orderMap;
+    }
+    // Print the symbols ordered by C3, in the order of decreasing curOrder
+    // Instead of sorting all the orderMap, just repeat the loops above.
+    for (int leader : sorted)
+      for (int i = leader;;) {
+        const InputSection *isec = sections[i];
+        // Search all the symbols in the file of the section
+        // and find out a Defined symbol with name that is within the
+        // section.
+        for (Symbol *sym : isec->getFile()->symbols) {
+          if (auto *d = dyn_cast_or_null<Defined>(sym)) {
+            if (d->isec == isec)
+              os << sym->getName() << "\n";
+          }
+        }
+        i = clusters[i].next;
+        if (i == leader)
+          break;
+      }
+  }
+
+  return orderMap;
+}
+
+// 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.
+DenseMap<const InputSection *, size_t> macho::computeCallGraphProfileOrder() {
+  TimeTraceScope timeScope("Call graph profile sort");
+  return CallGraphSort().run();
+}

lld/MachO/Config.h

 //===- Config.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_CONFIG_H
 #define LLD_MACHO_CONFIG_H
 
 #include "llvm/ADT/CachedHashString.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/BinaryFormat/MachO.h"
 #include "llvm/Support/CachePruning.h"
 #include "llvm/Support/GlobPattern.h"
 #include "llvm/Support/VersionTuple.h"
 #include "llvm/TextAPI/Architecture.h"
 #include "llvm/TextAPI/Platform.h"
 #include "llvm/TextAPI/Target.h"
 
 #include <vector>
 
 namespace lld {
 namespace macho {
 
+class InputSection;
 class Symbol;
 struct SymbolPriorityEntry;
 
 using NamePair = std::pair<llvm::StringRef, llvm::StringRef>;
 using SectionRenameMap = llvm::DenseMap<NamePair, NamePair>;
 using SegmentRenameMap = llvm::DenseMap<llvm::StringRef, llvm::StringRef>;
 
 struct PlatformInfo {
struct Configuration {
   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;
 
   bool zeroModTime = false;
 

lld/MachO/Driver.cpp

for (const SubsectionMap &map : file->subsections) {
           llvm_unreachable("unexpected input section kind");
         }
       }
     }
   }
   assert(inputOrder <= UnspecifiedInputOrder);
 }
 
+static void extractCallGraphProfile() {
+  TimeTraceScope timeScope("Extract call graph profile");
+  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)
+        continue;
+      config->callGraphProfile[{fromSym->isec, toSym->isec}] += entry.count;
+    }
+  }
+}
+
 static void foldIdenticalLiterals() {
   // We always create a cStringSection, regardless of whether dedupLiterals is
   // true. If it isn't, we simply create a non-deduplicating CStringSection.
   // Either way, we must unconditionally finalize it here.
   in.cStringSection->finalizeContents();
   if (in.wordLiteralSection)
     in.wordLiteralSection->finalizeContents();
 }
bool macho::link(ArrayRef<const char *> argsArr, bool canExitEarly,
   config->emitFunctionStarts =
       args.hasFlag(OPT_function_starts, OPT_no_function_starts, true);
   config->emitBitcodeBundle = args.hasArg(OPT_bitcode_bundle);
   config->emitDataInCodeInfo =
       args.hasFlag(OPT_data_in_code_info, OPT_no_data_in_code_info, true);
   config->icfLevel = getICFLevel(args);
   config->dedupLiterals = args.hasArg(OPT_deduplicate_literals) ||
                           config->icfLevel != ICFLevel::none;
+  config->callGraphProfileSort = args.hasFlag(
+      OPT_call_graph_profile_sort, OPT_no_call_graph_profile_sort, true);
+  config->printSymbolOrder = args.getLastArgValue(OPT_print_symbol_order);
 
   // FIXME: Add a commandline flag for this too.
   config->zeroModTime = getenv("ZERO_AR_DATE");
 
   std::array<PlatformKind, 3> encryptablePlatforms{
       PlatformKind::iOS, PlatformKind::watchOS, PlatformKind::tvOS};
   config->emitEncryptionInfo =
       args.hasFlag(OPT_encryptable, OPT_no_encryption,
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();
for (const Arg *arg : args.filtered(OPT_sectcreate)) {
       StringRef sectName = arg->getValue(1);
       StringRef fileName = arg->getValue(2);
       Optional<MemoryBufferRef> buffer = readFile(fileName);
       if (buffer)
         inputFiles.insert(make<OpaqueFile>(*buffer, segName, sectName));
     }
 
     gatherInputSections();
+    if (config->callGraphProfileSort)
+      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)
       foldIdenticalSections();

lld/MachO/InputFiles.h

 // symbol boundaries. The field offset represents the offset of the subsection
 // from the start of the original pre-split InputSection.
 struct SubsectionEntry {
   uint64_t offset;
   InputSection *isec;
 };
 using SubsectionMap = std::vector<SubsectionEntry>;
 
+// Represents a call graph profile edge.
+struct CallGraphEntry {
+  // The index of the caller in the symbol table.
+  uint32_t fromIndex;
+  // The index of the callee in the symbol table.
+  uint32_t toIndex;
+  // Number of calls from callee to caller in the profile.
+  uint64_t count;
+};
+
 class InputFile {
 public:
   enum Kind {
     ObjKind,
     OpaqueKind,
     DylibKind,
     ArchiveKind,
     BitcodeKind,

 public:
   ObjFile(MemoryBufferRef mb, uint32_t modTime, StringRef archiveName);
   static bool classof(const InputFile *f) { return f->kind() == ObjKind; }
 
   llvm::DWARFUnit *compileUnit = nullptr;
   const uint32_t modTime;
   std::vector<ConcatInputSection *> debugSections;
   ArrayRef<llvm::MachO::data_in_code_entry> dataInCodeEntries;
+  std::vector<CallGraphEntry> callGraph;
 
 private:
   template <class LP> void parse();
   template <class Section> void parseSections(ArrayRef<Section>);
   template <class LP>
   void parseSymbols(ArrayRef<typename LP::section> sectionHeaders,
                     ArrayRef<typename LP::nlist> nList, const char *strtab,
                     bool subsectionsViaSymbols);

lld/MachO/InputFiles.cpp

 
 #include "lld/Common/DWARF.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "lld/Common/Reproduce.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/BinaryFormat/MachO.h"
 #include "llvm/LTO/LTO.h"
+#include "llvm/Support/BinaryStreamReader.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/TarWriter.h"
 #include "llvm/TextAPI/Architecture.h"
 #include "llvm/TextAPI/InterfaceFile.h"
 
 using namespace llvm;
if (sectionType(sec.flags) == S_CSTRING_LITERALS ||
       } else {
         isec = make<WordLiteralInputSection>(segname, name, this, data, align,
                                              flags);
       }
       subsections.push_back({{0, isec}});
     } else if (auto recordSize = getRecordSize(segname, name)) {
       splitRecords(*recordSize);
     } else if (segname == segment_names::llvm) {
+      if (name == "__cg_profile" && config->callGraphProfileSort) {
+        BinaryStreamReader reader(data, support::little);
+        while (!reader.empty()) {
+          uint32_t fromIndex, toIndex;
+          uint64_t count;
+          if (Error err = reader.readInteger(fromIndex))
+            fatal(toString(this) + ": Expected 32-bit integer");
+          if (Error err = reader.readInteger(toIndex))
+            fatal(toString(this) + ": Expected 32-bit integer");
+          if (Error err = reader.readInteger(count))
+            fatal(toString(this) + ": Expected 64-bit integer");
+          callGraph.emplace_back();
+          CallGraphEntry &entry = callGraph.back();
+          entry.fromIndex = fromIndex;
+          entry.toIndex = toIndex;
+          entry.count = count;
+        }
+      }
       // ld64 does not appear to emit contents from sections within the __LLVM
       // segment. Symbols within those sections point to bitcode metadata
       // instead of actual symbols. Global symbols within those sections could
       // have the same name without causing duplicate symbol errors. Push an
       // empty map to ensure indices line up for the remaining sections.
       // TODO: Evaluate whether the bitcode metadata is needed.
       subsections.push_back({});
     } else {

lld/MachO/InputSection.h

public:
   // offset from the beginning of its parent OutputSection.
   virtual uint64_t getOffset(uint64_t off) const = 0;
   // The offset from the beginning of the file.
   uint64_t getVA(uint64_t off) const;
   // Whether the data at \p off in this InputSection is live.
   virtual bool isLive(uint64_t off) const = 0;
   virtual void markLive(uint64_t off) = 0;
   virtual InputSection *canonical() { return this; }
+  virtual const InputSection *canonical() const { return this; }
 
   OutputSection *parent = nullptr;
 
   uint32_t align = 1;
   uint32_t callSiteCount : 31;
   // is address assigned?
   uint32_t isFinal : 1;
 
public:
   bool isHashableForICF() const;
   void hashForICF();
   void writeTo(uint8_t *buf);
 
   void foldIdentical(ConcatInputSection *redundant);
   InputSection *canonical() override {
     return replacement ? replacement : this;
   }
+  const InputSection *canonical() const override {
+    return replacement ? replacement : this;
+  }
 
   static bool classof(const InputSection *isec) {
     return isec->kind() == ConcatKind;
   }
 
   // Points to the surviving section after this one is folded by ICF
   InputSection *replacement = nullptr;
   // Equivalence-class ID for ICF

lld/MachO/Options.td

def lto_O: Joined<["--"], "lto-O">,
     HelpText<"Set optimization level for LTO (default: 2)">,
     MetaVarName<"<opt-level>">,
     Group<grp_lld>;
 def thinlto_cache_policy: Joined<["--"], "thinlto-cache-policy=">,
     HelpText<"Pruning policy for the ThinLTO cache">,
     Group<grp_lld>;
 def O : JoinedOrSeparate<["-"], "O">,
     HelpText<"Optimize output file size">;
+def call_graph_profile_sort: Flag<["--"], "call-graph-profile-sort">,
+    HelpText<"Reorder sections with call graph profile (default: true)">,
+    Group<grp_lld>;
+def no_call_graph_profile_sort : Flag<["--"], "no-call-graph-profile-sort">,
+    HelpText<"Do not reorder sections with call graph profile (default: false)">,
+    Group<grp_lld>;
+def print_symbol_order: Joined<["--"], "print-symbol-order=">,
+    HelpText<"Print a symbol order specified by --call-graph-profile-sort into the specified file">,
+    Group<grp_lld>;
 
 // This is a complete Options.td compiled from Apple's ld(1) manpage
 // dated 2018-03-07 and cross checked with ld64 source code in repo
 // https://github.com/apple-opensource/ld64 at git tag "512.4" dated
 // 2018-03-18.
 
 // Flags<[HelpHidden]> marks options that are not yet ported to lld,
 // and serve as a scoreboard for annotating our progress toward

lld/MachO/Writer.cpp

 //===- Writer.cpp ---------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "Writer.h"
+#include "CallGraphSort.h"
 #include "ConcatOutputSection.h"
 #include "Config.h"
 #include "InputFiles.h"
 #include "InputSection.h"
 #include "MapFile.h"
 #include "OutputSection.h"
 #include "OutputSegment.h"
 #include "SymbolTable.h"
else
     filename = saver.save(path::filename(f->archiveName) + "(" +
                           path::filename(f->getName()) + ")");
   return std::max(entry.objectFiles.lookup(filename), entry.anyObjectFile);
 }
 
 // Each section gets assigned the priority of the highest-priority symbol it
 // contains.
 static DenseMap<const InputSection *, size_t> buildInputSectionPriorities() {
+  if (config->callGraphProfileSort)
+    return computeCallGraphProfileOrder();
   DenseMap<const InputSection *, size_t> sectionPriorities;
 
   if (config->priorities.empty())
     return sectionPriorities;
 
   auto addSym = [&](Defined &sym) {
     if (sym.isAbsolute())
       return;

lld/test/MachO/cgprofile-icf.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t
+
+# RUN: %lld -e A %t -o %t.out --icf=all
+# RUN: llvm-nm --numeric-sort %t.out | FileCheck %s
+# RUN: %lld -e A %t -o %t2.out
+# RUN: llvm-nm --numeric-sort %t2.out | FileCheck %s --check-prefix=NOICF
+
+.text
+    .globl  D
+D:
+    mov $60, %rax
+    retq
+
+    .globl  C
+C:
+    mov $60, %rax
+    retq
+
+    .globl  B
+B:
+    mov $2, %rax
+    retq
+
+    .globl  A
+A:
+    mov $42, %rax
+    retq
+
+.cg_profile A, B, 100
+.cg_profile A, C,  40
+.cg_profile C, D,  61
+
+.subsections_via_symbols
+
+# CHECK:      0000000100000290 T A
+# CHECK-NEXT: 0000000100000298 T C
+# CHECK-NEXT: 0000000100000298 T D
+# CHECK-NEXT: 00000001000002a0 T B
+
+# NOICF:      0000000100000290 T A
+# NOICF-NEXT: 0000000100000298 T B
+# NOICF-NEXT: 00000001000002a0 T C
+# NOICF-NEXT: 00000001000002a8 T D
+

lld/test/MachO/cgprofile-obj.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t.o
+# RUN: %lld -lSystem -e A -o %t.out %t.o
+# RUN: llvm-nm --numeric-sort %t.out | FileCheck %s
+# RUN: %lld --no-call-graph-profile-sort -lSystem -e A -o %t.out %t.o
+# RUN: llvm-nm --numeric-sort %t.out | FileCheck %s --check-prefix=NO-CG
+
+.text
+
+D:
+  retq
+.globl C
+C:
+  retq
+.globl B
+B:
+  retq
+.globl A
+A:
+Aa:
+  retq
+.subsections_via_symbols
+
+
+
+    .cg_profile A, B, 10
+    .cg_profile A, B, 10
+    .cg_profile Aa, B, 80
+    .cg_profile A, C, 40
+    .cg_profile B, C, 30
+    .cg_profile C, D, 90
+
+# CHECK: 00000001000002c8 T A
+# CHECK: 00000001000002c9 T B
+# CHECK: 00000001000002ca T C
+# CHECK: 00000001000002cb t D
+
+# NO-CG: 00000001000002c8 t D
+# NO-CG: 00000001000002c9 T C
+# NO-CG: 00000001000002ca T B
+# NO-CG: 00000001000002cb T A

lld/test/MachO/cgprofile-print.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t
+# RUN: %lld -e A %t -o %t2  --print-symbol-order=%t3
+# RUN: FileCheck %s --input-file %t3
+
+# CHECK: B
+# CHECK-NEXT: C
+# CHECK-NEXT: D
+# CHECK-NEXT: A
+
+.text
+.globl  A
+A:
+ nop
+
+.globl  B
+B:
+ nop
+
+.globl  C
+C:
+ nop
+
+.globl  D
+D:
+ nop
+
+.subsections_via_symbols
+
+.cg_profile A, B, 5
+.cg_profile B, C, 50
+.cg_profile C, D, 40
+.cg_profile D, B, 10

llvm/utils/gn/secondary/lld/MachO/BUILD.gn

include_dirs = [
     "//libunwind/include",
   ]
   sources = [
     "Arch/ARM.cpp",
     "Arch/ARM64.cpp",
     "Arch/ARM64Common.cpp",
     "Arch/ARM64_32.cpp",
     "Arch/X86_64.cpp",
+    "CallGraphSort.cpp",
     "ConcatOutputSection.cpp",
     "Driver.cpp",
     "DriverUtils.cpp",
     "Dwarf.cpp",
     "ExportTrie.cpp",
     "ICF.cpp",
     "InputFiles.cpp",
     "InputSection.cpp",