[COFF] Port CallGraphSort to COFF from ELF

[zequanwu]

Summary

Port CallGraphSort to COFF from ELF.

[zequanwu]

update

[MaskRay]

lld/COFF/CallGraphSort.cpp

95

This is pretty arbitrary as well.

198

The coefficient is pretty arbitrary. Best if you can test which constant works well.

[zequanwu]

lld/COFF/CallGraphSort.cpp

198

What is the tool I can use for testing this?

[zequanwu]

Templatize CallGraphSort and put it in Common directory.

[MaskRay]

I am on the fence about reusing the code. Adding some people for feedback.

[MaskRay]

lld/ELF/CallGraphSort.cpp

226

Why is it INT_MIN now?

lld/include/lld/Common/CallGraphSort.h

15 ↗

(On Diff #269601)

Avoid using namespace in a header file

[zequanwu]

Move using namespace llvm; from header file to cpp file.

[zequanwu]

lld/ELF/CallGraphSort.cpp

226

The order of section is sorted in increasing order, so this does not change the behavior.

Because I reuse the sortBySectionOrder of COFF's /orderoption to do sorting (https://github.com/llvm/llvm-project/blob/master/lld/COFF/Writer.cpp#L656). It assigns symbols in the given file priorities starting from INT_MIN and non present symbols get priority 0. It also sorts section in increasing order.
Or I can leave int curOrder = 1, but when copying the numbers, subtracting each number by INT_MIN.

[grimar]

A a few comments/suggestions.

lld/ELF/CallGraphSort.cpp

104

Why T and not something like Section, similar to Symbol?
Perhaps I'd use TSection and TSymbol to make clear they are template names.

lld/ELF/Writer.cpp

1310 ↗

(On Diff #269659)

I think it is common for LLD ELF to ise sec for sections. So sc -> sec probably.
I'd also leave a comment to explain for what this predicate is used. Perhaps it is better not to inline it,
but define separatelly. Like

 // A comment.
auto PrintSymbolOrderPred = [] (...) { ... };
...

return computeCallGraphProfileOrder<InputSectionBase, Symbol>(
        config->callGraphProfile, config->printSymbolOrder, PrintSymbolOrderPred );

lld/include/lld/Common/CallGraphSort.h

63 ↗

(On Diff #269659)

There is no /callgraph-profile-file option in ELF (it has --call-graph-ordering-file).

Since this is a common code, comments should be applicable for all platforms.

72 ↗

(On Diff #269659)

I think it needs a comment about what is printSymbolOrder and what is cond for.

cond here is used as a filter predicate for --print-symbol-order. Its name is probably not clear.

[grimar]

In D81429#2083172, @MaskRay wrote:

I am on the fence about reusing the code. Adding some people for feedback.

I am also not sure it is a good thing to do. It seems makes LLD ELF code a bit less readable.
I do not really like how --print-symbol-order is handled with this.

[zequanwu]

Address comments.

[MaskRay]

Parametric generalization on InputSection and Symbol may not be a good idea but they are very different in ELF and COFF. ICF.cpp is an example where we could reuse code but we choose not to.
If it is not clear reusing code will be beneficial, I think we can duplicate code for now. The algorithm is simple and there is not much duplication anyway.

[zequanwu]

I agree to adopt how ICF.cpp does.
roll back to previous version to have CallGraphSort in both ELF and COFF.

[hans]

This is looking good to me overall. Just some minor comments.

lld/COFF/CallGraphSort.cpp

12

Even if we're duplicating the code, I would suggest not duplicating the full comment, but put something like "this is based on the ELF port, see lld/ELF/CallGraphSort.cpp" or something like that.

73

Since the constructor initializes size, maybe the initializer here could be dropped?

95

I think it's fine to start by copying these values from ELF, and possibly tuning in the future.

118

The "SB" here and otherwhere is a bit confusing since I guess it stands for SectionBase in the original code, but here we're using SectionChunk. Maybe instead of "SB", "Sec" would be more clear?

198

Since this is a port of the ELF code, I think re-using the coefficient is fine, and tuning can be done later.

226

Since starting from INT_MIN here is different than in ELF, I think it would be good to at least have a comment explaining why.

227

I see the ELF code also has no curly braces around the for loop, but I think it would help readability, so I'd suggest adding them both here and in the original code.

253

Instead of nesting the if's maybe use "if (a && b)". Also maybe a comment about what you're filtering for here would be helpful.

lld/COFF/Driver.cpp

945

ELF calls maybeWarnUnorderableSymbol() here, but I suppose there's no corresponding concept for COFF?

lld/test/COFF/cgprofile-icf.s

3

Could you add a comment here that explains the intention of the test?

lld/test/COFF/cgprofile-txt.s

3

A short comment here which explains what the test is testing would be useful.

[zequanwu]

Address comments and rebase.

lld/COFF/Driver.cpp

945

I don't find corresponding concept.

lld/test/COFF/cgprofile-icf.s

3

This is ported from ELF/cgprofile-icf.s. I suppose the intention is to test the compatibility of ICF and cgprofile

[zequanwu]

remove a dummy file.

[MaskRay]

lld/COFF/Driver.cpp

945

maybeWarnUnorderableSymbol is not useful. You can omit it for COFF. The list is usually generated by the compilers - in very few circumstances a user specifies it. There is not much point diagnosing unneeded symbols in the linker.

lld/ELF/CallGraphSort.cpp

71

uint64_t may be better.

size_t is 32-bit on a 32-bit platform, while you want a 64-bit value here.

[zequanwu]

Change type of size in cluster from size_t to uint64_t.

[zequanwu]

Friendly ping.

[MaskRay]

lld/test/COFF/cgprofile-txt.s

22

Add -NEXT: whenever applicable

45

Delete trailing empty lines.

Please fix other files as well.

[zequanwu]

Remove trailing empty lines.

lld/test/COFF/cgprofile-txt.s

22

The complete output is like the following, so there is a gap.

140001000 t .text
140001000 T B
140001001 t .text
140001001 T C
140001002 t .text
140001002 T D
140001003 t .text
140001003 T A
140001004 t .text

[zequanwu]

Add option /call-graph-profile-sort in lld-link to read CGProfile data from object file (default on), equivalent to --call-graph-profile-sort in ld.lld.

[hans]

I added some more very minor comments, but overall this looks good to me. Please wait for maskray to sign off too, though.

There doesn't seem to be good documentation for the ELF feature that I could find. I'm not sure where the best way to add it would be (lld's man page?) but if you want, that would be a good thing to improve.

lld/COFF/CMakeLists.txt

8

nit: move up one line to make it more alphabetic

lld/COFF/CallGraphSort.cpp

9–10

isn't it lld/ELF/CallGraphSort.cpp?

20

is this actually needed?

lld/COFF/Driver.cpp

932

nit: period at the end

2097

What happens if the user passes /order but there is also call graphs in the object files?

2118

nit: period.

2127

nit: period

lld/COFF/Options.td

247

The order could also come from the object files, right? I mean it doesn't have to be specified y /call-graph-ordering-file (but I guess the output is useful for passing to the flag)

[zequanwu]

Address comments.

[zequanwu]

lld/COFF/Options.td

247

Yes.

[zequanwu]

Friendly ping.

[MaskRay]

lld/test/COFF/cgprofile-icf.s

3

Nit: Comments usually end with a full stop.

[zequanwu]

Rebase and comment.

lld/COFF/CMakeLists.txt

 set(LLVM_TARGET_DEFINITIONS Options.td)
 tablegen(LLVM Options.inc -gen-opt-parser-defs)
 add_public_tablegen_target(COFFOptionsTableGen)
 
 add_lld_library(lldCOFF
+  CallGraphSort.cpp
   Chunks.cpp
   DebugTypes.cpp
   DLL.cpp
   Driver.cpp
   DriverUtils.cpp
   ICF.cpp
   InputFiles.cpp
   LLDMapFile.cpp
   LTO.cpp
   MapFile.cpp

lld/COFF/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_COFF_CALL_GRAPH_SORT_H
+#define LLD_COFF_CALL_GRAPH_SORT_H
+
+#include "llvm/ADT/DenseMap.h"
+
+namespace lld {
+namespace coff {
+class SectionChunk;
+
+llvm::DenseMap<const SectionChunk *, int> computeCallGraphProfileOrder();
+} // namespace coff
+} // namespace lld
+
+#endif

lld/COFF/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
 //
 //===----------------------------------------------------------------------===//
 ///
-/// Implementation of Call-Chain Clustering from: Optimizing Function Placement
-/// for Large-Scale Data-Center Applications
-/// https://research.fb.com/wp-content/uploads/2017/01/cgo2017-hfsort-final1.pdf
-///
-/// The goal of this algorithm is to improve runtime performance of the final
-/// executable by arranging code sections such that page table and i-cache
-/// misses are minimized.
-///
-/// Definitions:
-/// * Cluster
-///   * An ordered list of input sections which are laid out as a unit. At the
-///     beginning of the algorithm each input section has its own cluster and
-///     the weight of the cluster is the sum of the weight of all incoming
-///     edges.
-/// * Call-Chain Clustering (C³) Heuristic
-///   * Defines when and how clusters are combined. Pick the highest weighted
-///     input section then add it to its most likely predecessor if it wouldn't
-///     penalize it too much.
-/// * Density
-///   * The weight of the cluster divided by the size of the cluster. This is a
-///     proxy for the amount of execution time spent per byte of the cluster.
-///
-/// It does so given a call graph profile by the following:
-/// * Build a weighted call graph from the call graph profile
-/// * Sort input sections by weight
-/// * For each input section starting with the highest weight
-///   * Find its most likely predecessor cluster
-///   * Check if the combined cluster would be too large, or would have too low
-///     a density.
-///   * If not, then combine the clusters.
-/// * Sort non-empty clusters by density
+/// This is based on the ELF port, see ELF/CallGraphSort.cpp for the details
+/// about the algorithm.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "CallGraphSort.h"
-#include "OutputSections.h"
+#include "InputFiles.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
+#include "lld/Common/ErrorHandler.h"
 
 #include <numeric>
 
 using namespace llvm;
 using namespace lld;
-using namespace lld::elf;
+using namespace lld::coff;
 
 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;
-  size_t size = 0;
+  uint64_t size;
   uint64_t weight = 0;
   uint64_t initialWeight = 0;
   Edge bestPred = {-1, 0};
 };
 
 class CallGraphSort {
 public:
   CallGraphSort();
 
-  DenseMap<const InputSectionBase *, int> run();
+  DenseMap<const SectionChunk *, int> run();
 
 private:
   std::vector<Cluster> clusters;
-  std::vector<const InputSectionBase *> sections;
+  std::vector<const SectionChunk *> sections;
 };
 
 // Maximum amount the combined cluster density can be worse than the original
 // cluster to consider merging.
 constexpr int MAX_DENSITY_DEGRADATION = 8;
 
 // Maximum cluster size in bytes.
 constexpr uint64_t MAX_CLUSTER_SIZE = 1024 * 1024;
 } // end anonymous namespace
 
-using SectionPair =
-    std::pair<const InputSectionBase *, const InputSectionBase *>;
+using SectionPair = std::pair<const SectionChunk *, const SectionChunk *>;
 
 // 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 InputSectionBase *, int> secToCluster;
+  DenseMap<const SectionChunk *, int> secToCluster;
 
-  auto getOrCreateNode = [&](const InputSectionBase *isec) -> int {
+  auto getOrCreateNode = [&](const SectionChunk *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 *fromSB = cast<InputSectionBase>(c.first.first->repl);
-    const auto *toSB = cast<InputSectionBase>(c.first.second->repl);
+    const auto *fromSec = cast<SectionChunk>(c.first.first->repl);
+    const auto *toSec = cast<SectionChunk>(c.first.second->repl);
     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 (fromSB->getOutputSection() != toSB->getOutputSection())
+    if (fromSec->getOutputSection() != toSec->getOutputSection())
       continue;
 
-    int from = getOrCreateNode(fromSB);
-    int to = getOrCreateNode(toSB);
+    int from = getOrCreateNode(fromSec);
+    int to = getOrCreateNode(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
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 InputSectionBase *, int> CallGraphSort::run() {
+DenseMap<const SectionChunk *, int> CallGraphSort::run() {
   std::vector<int> sorted(clusters.size());
   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();
   });
DenseMap<const SectionChunk *, int> CallGraphSort::run() {
   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 InputSectionBase *, int> orderMap;
-  int curOrder = 1;
-  for (int leader : sorted)
+  DenseMap<const SectionChunk *, int> orderMap;
+  // Sections will be sorted by increasing order. Absent sections will have
+  // priority 0 and be placed at the end of sections.
+  int curOrder = INT_MIN;
+  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 increasing curOrder
     // Instead of sorting all the orderMap, just repeat the loops above.
     for (int leader : sorted)
       for (int i = leader;;) {
+        const SectionChunk *sc = 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 : sections[i]->file->getSymbols())
-          if (!sym->isSection()) // Filter out section-type symbols here.
-            if (auto *d = dyn_cast<Defined>(sym))
-              if (sections[i] == d->section)
-                os << sym->getName() << "\n";
+        // and find out a DefinedCOFF symbol with name that is within the
+        // section.
+        for (Symbol *sym : sc->file->getSymbols())
+          if (auto *d = dyn_cast_or_null<DefinedCOFF>(sym))
+            // Filter out non-COMDAT symbols and section symbols.
+            if (d->isCOMDAT && !d->getCOFFSymbol().isSection() &&
+                sc == d->getChunk())
         i = clusters[i].next;
         if (i == leader)
           break;
       }
   }
 
   return orderMap;
 }
 
-// Sort sections by the profile data provided by -callgraph-profile-file
+// Sort sections by the profile data provided by  /call-graph-ordering-file
 //
 // 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 InputSectionBase *, int> elf::computeCallGraphProfileOrder() {
+DenseMap<const SectionChunk *, int> coff::computeCallGraphProfileOrder() {
   return CallGraphSort().run();
 }

lld/COFF/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_COFF_CONFIG_H
 #define LLD_COFF_CONFIG_H
 
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Object/COFF.h"
 #include "llvm/Support/CachePruning.h"
 #include <cstdint>
 #include <map>
 #include <set>
 #include <string>
 
 namespace lld {
 namespace coff {
 
 using llvm::COFF::IMAGE_FILE_MACHINE_UNKNOWN;
 using llvm::COFF::WindowsSubsystem;
 using llvm::StringRef;
 class DefinedAbsolute;
 class DefinedRelative;
 class StringChunk;
 class Symbol;
 class InputFile;
+class SectionChunk;
 
 // Short aliases.
 static const auto AMD64 = llvm::COFF::IMAGE_FILE_MACHINE_AMD64;
 static const auto ARM64 = llvm::COFF::IMAGE_FILE_MACHINE_ARM64;
 static const auto ARMNT = llvm::COFF::IMAGE_FILE_MACHINE_ARMNT;
 static const auto I386 = llvm::COFF::IMAGE_FILE_MACHINE_I386;
 
 // Represents an /export option.
struct Configuration {
   std::pair<llvm::StringRef, llvm::StringRef> thinLTOPrefixReplace;
 
   // Used for /thinlto-object-suffix-replace:
   std::pair<llvm::StringRef, llvm::StringRef> thinLTOObjectSuffixReplace;
 
   // Used for /lto-obj-path:
   llvm::StringRef ltoObjPath;
 
+  // Used for /call-graph-ordering-file:
+  llvm::MapVector<std::pair<const SectionChunk *, const SectionChunk *>,
+                  uint64_t>
+      callGraphProfile;
+  bool callGraphProfileSort = false;
+
+  // Used for /print-symbol-order:
+  StringRef printSymbolOrder;
+
   uint64_t align = 4096;
   uint64_t imageBase = -1;
   uint64_t fileAlign = 512;
   uint64_t stackReserve = 1024 * 1024;
   uint64_t stackCommit = 4096;
   uint64_t heapReserve = 1024 * 1024;
   uint64_t heapCommit = 4096;
   uint32_t majorImageVersion = 0;

lld/COFF/Driver.cpp

 #include "llvm/LTO/LTO.h"
 #include "llvm/Object/ArchiveWriter.h"
 #include "llvm/Object/COFFImportFile.h"
 #include "llvm/Object/COFFModuleDefinition.h"
 #include "llvm/Object/WindowsMachineFlag.h"
 #include "llvm/Option/Arg.h"
 #include "llvm/Option/ArgList.h"
 #include "llvm/Option/Option.h"
+#include "llvm/Support/BinaryStreamReader.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/LEB128.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/Parallel.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Process.h"
 #include "llvm/Support/TarWriter.h"
if (set.count(s) == 0) {
       if (config->warnMissingOrderSymbol)
         warn("/order:" + arg + ": missing symbol: " + s + " [LNK4037]");
     }
     else
       config->order[s] = INT_MIN + config->order.size();
   }
 }
 
+static void parseCallGraphFile(StringRef path) {
+  std::unique_ptr<MemoryBuffer> mb = CHECK(
+      MemoryBuffer::getFile(path, -1, false, true), "could not open " + path);
+
+  // Build a map from symbol name to section.
+  DenseMap<StringRef, Symbol *> map;
+  for (ObjFile *file : ObjFile::instances)
+    for (Symbol *sym : file->getSymbols())
+      if (sym)
+        map[sym->getName()] = sym;
+
+  auto findSection = [&](StringRef name) -> SectionChunk * {
+    Symbol *sym = map.lookup(name);
+    if (!sym) {
+      if (config->warnMissingOrderSymbol)
+        warn(path + ": no such symbol: " + name);
+      return nullptr;
+    }
+
+    if (DefinedCOFF *dr = dyn_cast_or_null<DefinedCOFF>(sym))
+      return dyn_cast_or_null<SectionChunk>(dr->getChunk());
+    return nullptr;
+  };
+
+  for (StringRef line : args::getLines(*mb)) {
+    SmallVector<StringRef, 3> fields;
+    line.split(fields, ' ');
+    uint64_t count;
+
+    if (fields.size() != 3 || !to_integer(fields[2], count)) {
+      error(path + ": parse error");
+      return;
+    }
+
+    if (SectionChunk *from = findSection(fields[0]))
+      if (SectionChunk *to = findSection(fields[1]))
+        config->callGraphProfile[{from, to}] += count;
+  }
+}
+
+static void readCallGraphsFromObjectFiles() {
+  for (ObjFile *obj : ObjFile::instances) {
+    if (obj->callgraphSec) {
+      ArrayRef<uint8_t> contents;
+      cantFail(
+          obj->getCOFFObj()->getSectionContents(obj->callgraphSec, contents));
+      BinaryStreamReader reader(contents, support::little);
+      while (!reader.empty()) {
+        uint32_t fromIndex, toIndex;
+        uint64_t count;
+        if (Error err = reader.readInteger(fromIndex))
+          fatal(toString(obj) + ": Expected 32-bit integer");
+        if (Error err = reader.readInteger(toIndex))
+          fatal(toString(obj) + ": Expected 32-bit integer");
+        if (Error err = reader.readInteger(count))
+          fatal(toString(obj) + ": Expected 64-bit integer");
+        auto *fromSym = dyn_cast_or_null<Defined>(obj->getSymbol(fromIndex));
+        auto *toSym = dyn_cast_or_null<Defined>(obj->getSymbol(toIndex));
+        if (!fromSym || !toSym)
+          continue;
+        auto *from = dyn_cast_or_null<SectionChunk>(fromSym->getChunk());
+        auto *to = dyn_cast_or_null<SectionChunk>(toSym->getChunk());
+        if (from && to)
+          config->callGraphProfile[{from, to}] += count;
+      }
+    }
+  }
+}
+
 static void markAddrsig(Symbol *s) {
   if (auto *d = dyn_cast_or_null<Defined>(s))
     if (SectionChunk *c = dyn_cast_or_null<SectionChunk>(d->getChunk()))
       c->keepUnique = true;
 }
 
 static void findKeepUniqueSections() {
   // Exported symbols could be address-significant in other executables or DSOs,
config->terminalServerAware =
       !config->dll && args.hasFlag(OPT_tsaware, OPT_tsaware_no, true);
   config->debugDwarf = debug == DebugKind::Dwarf;
   config->debugGHashes = debug == DebugKind::GHash;
   config->debugSymtab = debug == DebugKind::Symtab;
   config->autoImport =
       args.hasFlag(OPT_auto_import, OPT_auto_import_no, config->mingw);
   config->pseudoRelocs = args.hasFlag(
       OPT_runtime_pseudo_reloc, OPT_runtime_pseudo_reloc_no, config->mingw);
+  config->callGraphProfileSort = args.hasFlag(
+      OPT_call_graph_profile_sort, OPT_call_graph_profile_sort_no, true);
 
-  // Don't warn about long section names, such as .debug_info, for mingw or when
-  // -debug:dwarf is requested.
+  // Don't warn about long section names, such as .debug_info, for mingw or
+  // when -debug:dwarf is requested.
   if (config->mingw || config->debugDwarf)
     config->warnLongSectionNames = false;
 
   config->lldmapFile = getMapFile(args, OPT_lldmap, OPT_lldmap_file);
   config->mapFile = getMapFile(args, OPT_map, OPT_map_file);
 
   if (config->lldmapFile != "" && config->lldmapFile == config->mapFile) {
     warn("/lldmap and /map have the same output file '" + config->mapFile +
for (auto pair : config->alignComm) {
     c->setAlignment(std::max(c->getAlignment(), alignment));
   }
 
   // Windows specific -- Create a side-by-side manifest file.
   if (config->manifest == Configuration::SideBySide)
     createSideBySideManifest();
 
   // Handle /order. We want to do this at this moment because we
   // need a complete list of comdat sections to warn on nonexistent
   // functions.
-  if (auto *arg = args.getLastArg(OPT_order))
+  if (auto *arg = args.getLastArg(OPT_order)) {
+    if (args.hasArg(OPT_call_graph_ordering_file))
+      error("/order and /call-graph-order-file may not be used together");
     parseOrderFile(arg->getValue());
+    config->callGraphProfileSort = false;
+  }
+
+  // Handle /call-graph-ordering-file and /call-graph-profile-sort (default on).
+  if (config->callGraphProfileSort) {
+    if (auto *arg = args.getLastArg(OPT_call_graph_ordering_file)) {
+      parseCallGraphFile(arg->getValue());
+    }
+    readCallGraphsFromObjectFiles();
+  }
+
+  // Handle /print-symbol-order.
+  if (auto *arg = args.getLastArg(OPT_print_symbol_order))
+    config->printSymbolOrder = arg->getValue();
 
   // Identify unreferenced COMDAT sections.
   if (config->doGC)
     markLive(symtab->getChunks());
 
   // Needs to happen after the last call to addFile().
   convertResources();
 
   // Identify identical COMDAT sections to merge them.
   if (config->doICF) {
     findKeepUniqueSections();
     doICF(symtab->getChunks());
   }
 
   // Write the result.
   writeResult();
 
   // Stop early so we can print the results.
   rootTimer.stop();
   if (config->showTiming)
     Timer::root().print();
 }
 
 } // namespace coff
 } // namespace lld

lld/COFF/InputFiles.h

public:
   // Pointer to the PDB module descriptor builder. Various debug info records
   // will reference object files by "module index", which is here. Things like
   // source files and section contributions are also recorded here. Will be null
   // if we are not producing a PDB.
   llvm::pdb::DbiModuleDescriptorBuilder *moduleDBI = nullptr;
 
   const coff_section *addrsigSec = nullptr;
 
+  const coff_section *callgraphSec = nullptr;
+
   // When using Microsoft precompiled headers, this is the PCH's key.
   // The same key is used by both the precompiled object, and objects using the
   // precompiled object. Any difference indicates out-of-date objects.
   llvm::Optional<uint32_t> pchSignature;
 
   // Whether this file was compiled with /hotpatch.
   bool hotPatchable = false;
 

lld/COFF/InputFiles.cpp

if (name == ".drectve") {
     return nullptr;
   }
 
   if (name == ".llvm_addrsig") {
     addrsigSec = sec;
     return nullptr;
   }
 
+  if (name == ".llvm.call-graph-profile") {
+    callgraphSec = sec;
+    return nullptr;
+  }
+
   // Object files may have DWARF debug info or MS CodeView debug info
   // (or both).
   //
   // DWARF sections don't need any special handling from the perspective
   // of the linker; they are just a data section containing relocations.
   // We can just link them to complete debug info.
   //
   // CodeView needs linker support. We need to interpret debug info,

lld/COFF/Options.td

 def lto_obj_path : P<
     "lto-obj-path",
     "output native object for merged LTO unit to this path">;
 def dash_dash_version : Flag<["--"], "version">,
   HelpText<"Print version information">;
 def threads
     : P<"threads", "Number of threads. '1' disables multi-threading. By "
                    "default all available hardware threads are used">;
+def call_graph_ordering_file: P<
+    "call-graph-ordering-file", 
+    "Layout sections to optimize the given callgraph">;
+defm call_graph_profile_sort: B<
+    "call-graph-profile-sort",
+    "Reorder sections with call graph profile (default)",
+    "Do not reorder sections with call graph profile">;
+def print_symbol_order: P<
+    "print-symbol-order",
+    "Print a symbol order specified by /call-graph-ordering-file and "
+    "/call-graph-profile-sort into the specified file">;
 
 // Flags for debugging
 def lldmap : F<"lldmap">;
 def lldmap_file : Joined<["/", "-", "/?", "-?"], "lldmap:">;
 def map : F<"map">;
 def map_file : Joined<["/", "-", "/?", "-?"], "map:">;
 def show_timing : F<"time">;
 def summary : F<"summary">;

lld/COFF/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 "Config.h"
 #include "DLL.h"
 #include "InputFiles.h"
 #include "LLDMapFile.h"
 #include "MapFile.h"
 #include "PDB.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
private:
   void markSymbolsForRVATable(ObjFile *file,
                               ArrayRef<SectionChunk *> symIdxChunks,
                               SymbolRVASet &tableSymbols);
   void maybeAddRVATable(SymbolRVASet tableSymbols, StringRef tableSym,
                         StringRef countSym);
   void setSectionPermissions();
   void writeSections();
   void writeBuildId();
+  void sortSections();
   void sortExceptionTable();
   void sortCRTSectionChunks(std::vector<Chunk *> &chunks);
   void addSyntheticIdata();
   void fixPartialSectionChars(StringRef name, uint32_t chars);
   bool fixGnuImportChunks();
   PartialSection *createPartialSection(StringRef name, uint32_t outChars);
   PartialSection *findPartialSection(StringRef name, uint32_t outChars);
 
if (!config->mingw)
     return false;
   if (!sc || !sc->isCOMDAT())
     return false;
   return name.startswith(".text$") || name.startswith(".data$") ||
          name.startswith(".rdata$") || name.startswith(".pdata$") ||
          name.startswith(".xdata$") || name.startswith(".eh_frame$");
 }
 
+void Writer::sortSections() {
+  if (!config->callGraphProfile.empty()) {
+    DenseMap<const SectionChunk *, int> order = computeCallGraphProfileOrder();
+    for (auto it : order) {
+      if (DefinedRegular *sym = it.first->sym)
+        config->order[sym->getName()] = it.second;
+    }
+  }
+  if (!config->order.empty())
+    for (auto it : partialSections)
+      sortBySectionOrder(it.second->chunks);
+}
+
 // Create output section objects and add them to OutputSections.
 void Writer::createSections() {
   // First, create the builtin sections.
   const uint32_t data = IMAGE_SCN_CNT_INITIALIZED_DATA;
   const uint32_t bss = IMAGE_SCN_CNT_UNINITIALIZED_DATA;
   const uint32_t code = IMAGE_SCN_CNT_CODE;
   const uint32_t discardable = IMAGE_SCN_MEM_DISCARDABLE;
   const uint32_t r = IMAGE_SCN_MEM_READ;
void Writer::createSections() {
   // libraries.
   bool hasIdata = fixGnuImportChunks();
   if (!idata.empty())
     hasIdata = true;
 
   if (hasIdata)
     addSyntheticIdata();
 
-  // Process an /order option.
-  if (!config->order.empty())
-    for (auto it : partialSections)
-      sortBySectionOrder(it.second->chunks);
+  sortSections();
 
   if (hasIdata)
     locateImportTables();
 
   // Then create an OutputSection for each section.
   // '$' and all following characters in input section names are
   // discarded when determining output section. So, .text$foo
   // contributes to .text, for example. See PE/COFF spec 3.2.

lld/ELF/CallGraphSort.cpp

struct Cluster {
   double getDensity() const {
     if (size == 0)
       return 0;
     return double(weight) / double(size);
   }
 
   int next;
   int prev;
-  size_t size = 0;
+  uint64_t size;
   uint64_t weight = 0;
   uint64_t initialWeight = 0;
   Edge bestPred = {-1, 0};
 };
 
 class CallGraphSort {
 public:
   CallGraphSort();

 using SectionPair =
     std::pair<const InputSectionBase *, const InputSectionBase *>;
 
 // 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 InputSectionBase *, int> secToCluster;
 
   auto getOrCreateNode = [&](const InputSectionBase *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;
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 InputSectionBase *, int> orderMap;
   int curOrder = 1;
-  for (int leader : sorted)
+  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;
     }
 

lld/test/COFF/cgprofile-bad-clusters.s

+# REQUIRES: x86
+# This test checks that CallGraphSort ignores edges that would form "bad"
+# clusters.
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-win32 %s -o %t
+# RUN: echo "A C 1" > %t.call_graph
+# RUN: echo "E B 4" >> %t.call_graph
+# RUN: echo "C D 2" >> %t.call_graph
+# RUN: echo "B D 1" >> %t.call_graph
+# RUN: echo "F G 6" >> %t.call_graph
+# RUN: echo "G H 5" >> %t.call_graph
+# RUN: echo "H I 4" >> %t.call_graph
+# RUN: lld-link /subsystem:console /entry:A %t /call-graph-ordering-file:%t.call_graph /out:%t2 /debug:symtab
+# RUN: llvm-nm --numeric-sort %t2 | FileCheck %s
+
+    .section    .text,"ax",one_only,A
+    .globl A
+A:
+    retq
+
+    .section    .text,"ax",one_only,D
+D:
+    .fill 1000, 1, 0
+
+    .section    .text,"ax",one_only,E
+E:
+    retq
+
+    .section    .text,"ax",one_only,C
+C:
+    retq
+
+    .section    .text,"ax",one_only,B
+B:
+    .fill 1000, 1, 0
+
+    .section    .text,"ax",one_only,F
+F:
+    .fill (1024 * 1024) - 1, 1, 0
+
+    .section    .text,"ax",one_only,G
+G:
+    retq
+
+    .section    .text,"ax",one_only,H
+H:
+    retq
+
+    .section    .text,"ax",one_only,I
+I:
+    .fill 13, 1, 0
+
+# CHECK: 140001000 t H
+# CHECK: 140001001 t I
+# CHECK: 14000100e T A
+# CHECK: 14000100f t C
+# CHECK: 140001010 t E
+# CHECK: 140001011 t B
+# CHECK: 1400013f9 t D
+# CHECK: 1400017e1 t F
+# CHECK: 1401017e0 t G

lld/test/COFF/cgprofile-err.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-win32 %s -o %t
+
+# RUN: echo "A B C 100" > %t.call_graph
+# RUN: not lld-link /dll /noentry  /subsystem:console %t /call-graph-ordering-file:%t.call_graph /out:/dev/null 2>&1 | FileCheck %s
+
+# CHECK: {{.*}}.call_graph: parse error
+
+# RUN: echo "A B C" > %t.call_graph
+# RUN: not lld-link /dll /noentry  /subsystem:console %t /call-graph-ordering-file:%t.call_graph /out:/dev/null 2>&1 | FileCheck %s

lld/test/COFF/cgprofile-icf.s

+# REQUIRES: x86
+# Test the compatibility of ICF and cgprofile.
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-win32 %s -o %t
+# RUN: echo "A B 100" > %t.call_graph
+# RUN: echo "A C 40" >> %t.call_graph
+# RUN: echo "C D 61" >> %t.call_graph
+# RUN: lld-link /subsystem:console /entry:A %t /call-graph-ordering-file:%t.call_graph /out:%t2 /debug:symtab /opt:icf
+# RUN: llvm-nm --numeric-sort %t2 | FileCheck %s
+# RUN: lld-link /subsystem:console /entry:A %t /call-graph-ordering-file:%t.call_graph /out:%t2 /debug:symtab
+# RUN: llvm-nm --numeric-sort %t2 | FileCheck %s --check-prefix=NOICF
+
+    .section    .text,"x",one_only,D
+    .globl  D
+D:
+    mov $60, %rax
+    retq
+
+    .section    .text,"x",one_only,C
+    .globl  C
+C:
+    mov $60, %rax
+    retq
+
+    .section    .text,"x",one_only,B
+    .globl  B
+B:
+    mov $2, %rax
+    retq
+
+    .section    .text,"x",one_only,A
+    .globl  A
+A:
+    mov $42, %rax
+    retq
+
+# CHECK: 140001000 T A
+# CHECK: 140001008 T C
+# CHECK: 140001008 T D
+# CHECK: 140001010 T B
+
+# NOICF: 140001000 T A
+# NOICF: 140001008 T B
+# NOICF: 140001010 T C
+# NOICF: 140001018 T D

lld/test/COFF/cgprofile-obj.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-win32 %s -o %t
+# RUN: lld-link /subsystem:console /entry:A %t /out:%t2 /debug:symtab
+# RUN: llvm-nm --numeric-sort %t2 | FileCheck %s
+# RUN: lld-link /call-graph-profile-sort:no /subsystem:console /entry:A %t /out:%t3 /debug:symtab
+# RUN: llvm-nm --numeric-sort %t3 | FileCheck %s --check-prefix=NO-CG
+
+    .section    .text,"ax", one_only, D
+D:
+ retq
+
+    .section    .text,"ax", one_only, C
+    .globl  C
+C:
+ retq
+
+    .section    .text,"ax", one_only, B
+    .globl  B
+B:
+ retq
+
+    .section    .text,"ax", one_only, A
+    .globl  A
+A:
+Aa:
+ retq
+
+    .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: 140001000 T A
+# CHECK: 140001001 T B
+# CHECK: 140001002 T C
+# CHECK: 140001003 t D
+
+
+# NO-CG: 140001000 t D
+# NO-CG: 140001001 T C
+# NO-CG: 140001002 T B
+# NO-CG: 140001003 T A

lld/test/COFF/cgprofile-print.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-win32 %s -o %t
+# RUN: echo "A B 5" > %t.call_graph
+# RUN: echo "B C 50" >> %t.call_graph
+# RUN: echo "C D 40" >> %t.call_graph
+# RUN: echo "D B 10" >> %t.call_graph
+# RUN: lld-link /subsystem:console /entry:A %t /call-graph-ordering-file:%t.call_graph /out:%t2 /print-symbol-order:%t3
+# RUN: FileCheck %s --input-file %t3
+
+# CHECK: B
+# CHECK-NEXT: C
+# CHECK-NEXT: D
+# CHECK-NEXT: A
+
+.section    .text, "x", one_only, A
+.globl  A
+A:
+ nop
+
+.section    .text, "x", one_only, B
+.globl  B
+B:
+ nop
+
+.section    .text, "x", one_only, C
+.globl  C
+C:
+ nop
+
+.section    .text, "x", one_only, D
+.globl  D
+D:
+ nop

lld/test/COFF/cgprofile-txt.s

+# REQUIRES: x86
+# Test correctness of call graph ordering.
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-win32 %s -o %t
+# RUN: lld-link /subsystem:console /entry:A %t /out:%t2 /debug:symtab
+# RUN: llvm-nm --numeric-sort %t2 | FileCheck %s --check-prefix=NOSORT 
+
+# RUN: echo "A B 5" > %t.call_graph
+# RUN: echo "B C 50" >> %t.call_graph
+# RUN: echo "C D 40" >> %t.call_graph
+# RUN: echo "D B 10" >> %t.call_graph
+# RUN: lld-link /subsystem:console /entry:A %t /call-graph-ordering-file:%t.call_graph /out:%t2 /debug:symtab
+# RUN: llvm-nm --numeric-sort %t2 | FileCheck %s 
+
+# NOSORT: 140001000 T A
+# NOSORT: 140001001 T B
+# NOSORT: 140001002 T C
+# NOSORT: 140001003 T D
+
+# CHECK: 140001000 T B
+# CHECK: 140001001 T C
+# CHECK: 140001002 T D
+# CHECK: 140001003 T A
+
+.section    .text, "x", one_only, A
+.globl  A
+A:
+ nop
+
+.section    .text, "x", one_only, B
+.globl  B
+B:
+ nop
+
+.section    .text, "x", one_only, C
+.globl  C
+C:
+ nop
+
+.section    .text, "x", one_only, D
+.globl  D
+D:
+ nop