CallGraphSort.cpp revision 360784 
1//===- CallGraphSort.cpp --------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// Implementation of Call-Chain Clustering from: Optimizing Function Placement
10/// for Large-Scale Data-Center Applications
11/// https://research.fb.com/wp-content/uploads/2017/01/cgo2017-hfsort-final1.pdf
12///
13/// The goal of this algorithm is to improve runtime performance of the final
14/// executable by arranging code sections such that page table and i-cache
15/// misses are minimized.
16///
17/// Definitions:
18/// * Cluster
19///   * An ordered list of input sections which are laid out as a unit. At the
20///     beginning of the algorithm each input section has its own cluster and
21///     the weight of the cluster is the sum of the weight of all incoming
22///     edges.
23/// * Call-Chain Clustering (C��) Heuristic
24///   * Defines when and how clusters are combined. Pick the highest weighted
25///     input section then add it to its most likely predecessor if it wouldn't
26///     penalize it too much.
27/// * Density
28///   * The weight of the cluster divided by the size of the cluster. This is a
29///     proxy for the amount of execution time spent per byte of the cluster.
30///
31/// It does so given a call graph profile by the following:
32/// * Build a weighted call graph from the call graph profile
33/// * Sort input sections by weight
34/// * For each input section starting with the highest weight
35///   * Find its most likely predecessor cluster
36///   * Check if the combined cluster would be too large, or would have too low
37///     a density.
38///   * If not, then combine the clusters.
39/// * Sort non-empty clusters by density
40///
41//===----------------------------------------------------------------------===//
42
43#include "CallGraphSort.h"
44#include "OutputSections.h"
45#include "SymbolTable.h"
46#include "Symbols.h"
47
48#include <numeric>
49
50using namespace llvm;
51
52namespace lld {
53namespace elf {
54
55namespace {
56struct Edge {
57  int from;
58  uint64_t weight;
59};
60
61struct Cluster {
62  Cluster(int sec, size_t s) : next(sec), prev(sec), size(s) {}
63
64  double getDensity() const {
65    if (size == 0)
66      return 0;
67    return double(weight) / double(size);
68  }
69
70  int next;
71  int prev;
72  size_t size = 0;
73  uint64_t weight = 0;
74  uint64_t initialWeight = 0;
75  Edge bestPred = {-1, 0};
76};
77
78class CallGraphSort {
79public:
80  CallGraphSort();
81
82  DenseMap<const InputSectionBase *, int> run();
83
84private:
85  std::vector<Cluster> clusters;
86  std::vector<const InputSectionBase *> sections;
87};
88
89// Maximum amount the combined cluster density can be worse than the original
90// cluster to consider merging.
91constexpr int MAX_DENSITY_DEGRADATION = 8;
92
93// Maximum cluster size in bytes.
94constexpr uint64_t MAX_CLUSTER_SIZE = 1024 * 1024;
95} // end anonymous namespace
96
97using SectionPair =
98    std::pair<const InputSectionBase *, const InputSectionBase *>;
99
100// Take the edge list in Config->CallGraphProfile, resolve symbol names to
101// Symbols, and generate a graph between InputSections with the provided
102// weights.
103CallGraphSort::CallGraphSort() {
104  MapVector<SectionPair, uint64_t> &profile = config->callGraphProfile;
105  DenseMap<const InputSectionBase *, int> secToCluster;
106
107  auto getOrCreateNode = [&](const InputSectionBase *isec) -> int {
108    auto res = secToCluster.try_emplace(isec, clusters.size());
109    if (res.second) {
110      sections.push_back(isec);
111      clusters.emplace_back(clusters.size(), isec->getSize());
112    }
113    return res.first->second;
114  };
115
116  // Create the graph.
117  for (std::pair<SectionPair, uint64_t> &c : profile) {
118    const auto *fromSB = cast<InputSectionBase>(c.first.first->repl);
119    const auto *toSB = cast<InputSectionBase>(c.first.second->repl);
120    uint64_t weight = c.second;
121
122    // Ignore edges between input sections belonging to different output
123    // sections.  This is done because otherwise we would end up with clusters
124    // containing input sections that can't actually be placed adjacently in the
125    // output.  This messes with the cluster size and density calculations.  We
126    // would also end up moving input sections in other output sections without
127    // moving them closer to what calls them.
128    if (fromSB->getOutputSection() != toSB->getOutputSection())
129      continue;
130
131    int from = getOrCreateNode(fromSB);
132    int to = getOrCreateNode(toSB);
133
134    clusters[to].weight += weight;
135
136    if (from == to)
137      continue;
138
139    // Remember the best edge.
140    Cluster &toC = clusters[to];
141    if (toC.bestPred.from == -1 || toC.bestPred.weight < weight) {
142      toC.bestPred.from = from;
143      toC.bestPred.weight = weight;
144    }
145  }
146  for (Cluster &c : clusters)
147    c.initialWeight = c.weight;
148}
149
150// It's bad to merge clusters which would degrade the density too much.
151static bool isNewDensityBad(Cluster &a, Cluster &b) {
152  double newDensity = double(a.weight + b.weight) / double(a.size + b.size);
153  return newDensity < a.getDensity() / MAX_DENSITY_DEGRADATION;
154}
155
156// Find the leader of V's belonged cluster (represented as an equivalence
157// class). We apply union-find path-halving technique (simple to implement) in
158// the meantime as it decreases depths and the time complexity.
159static int getLeader(std::vector<int> &leaders, int v) {
160  while (leaders[v] != v) {
161    leaders[v] = leaders[leaders[v]];
162    v = leaders[v];
163  }
164  return v;
165}
166
167static void mergeClusters(std::vector<Cluster> &cs, Cluster &into, int intoIdx,
168                          Cluster &from, int fromIdx) {
169  int tail1 = into.prev, tail2 = from.prev;
170  into.prev = tail2;
171  cs[tail2].next = intoIdx;
172  from.prev = tail1;
173  cs[tail1].next = fromIdx;
174  into.size += from.size;
175  into.weight += from.weight;
176  from.size = 0;
177  from.weight = 0;
178}
179
180// Group InputSections into clusters using the Call-Chain Clustering heuristic
181// then sort the clusters by density.
182DenseMap<const InputSectionBase *, int> CallGraphSort::run() {
183  std::vector<int> sorted(clusters.size());
184  std::vector<int> leaders(clusters.size());
185
186  std::iota(leaders.begin(), leaders.end(), 0);
187  std::iota(sorted.begin(), sorted.end(), 0);
188  llvm::stable_sort(sorted, [&](int a, int b) {
189    return clusters[a].getDensity() > clusters[b].getDensity();
190  });
191
192  for (int l : sorted) {
193    // The cluster index is the same as the index of its leader here because
194    // clusters[L] has not been merged into another cluster yet.
195    Cluster &c = clusters[l];
196
197    // Don't consider merging if the edge is unlikely.
198    if (c.bestPred.from == -1 || c.bestPred.weight * 10 <= c.initialWeight)
199      continue;
200
201    int predL = getLeader(leaders, c.bestPred.from);
202    if (l == predL)
203      continue;
204
205    Cluster *predC = &clusters[predL];
206    if (c.size + predC->size > MAX_CLUSTER_SIZE)
207      continue;
208
209    if (isNewDensityBad(*predC, c))
210      continue;
211
212    leaders[l] = predL;
213    mergeClusters(clusters, *predC, predL, c, l);
214  }
215
216  // Sort remaining non-empty clusters by density.
217  sorted.clear();
218  for (int i = 0, e = (int)clusters.size(); i != e; ++i)
219    if (clusters[i].size > 0)
220      sorted.push_back(i);
221  llvm::stable_sort(sorted, [&](int a, int b) {
222    return clusters[a].getDensity() > clusters[b].getDensity();
223  });
224
225  DenseMap<const InputSectionBase *, int> orderMap;
226  int curOrder = 1;
227  for (int leader : sorted)
228    for (int i = leader;;) {
229      orderMap[sections[i]] = curOrder++;
230      i = clusters[i].next;
231      if (i == leader)
232        break;
233    }
234
235  if (!config->printSymbolOrder.empty()) {
236    std::error_code ec;
237    raw_fd_ostream os(config->printSymbolOrder, ec, sys::fs::OF_None);
238    if (ec) {
239      error("cannot open " + config->printSymbolOrder + ": " + ec.message());
240      return orderMap;
241    }
242
243    // Print the symbols ordered by C3, in the order of increasing curOrder
244    // Instead of sorting all the orderMap, just repeat the loops above.
245    for (int leader : sorted)
246      for (int i = leader;;) {
247        // Search all the symbols in the file of the section
248        // and find out a Defined symbol with name that is within the section.
249        for (Symbol *sym : sections[i]->file->getSymbols())
250          if (!sym->isSection()) // Filter out section-type symbols here.
251            if (auto *d = dyn_cast<Defined>(sym))
252              if (sections[i] == d->section)
253                os << sym->getName() << "\n";
254        i = clusters[i].next;
255        if (i == leader)
256          break;
257      }
258  }
259
260  return orderMap;
261}
262
263// Sort sections by the profile data provided by -callgraph-profile-file
264//
265// This first builds a call graph based on the profile data then merges sections
266// according to the C�� huristic. All clusters are then sorted by a density
267// metric to further improve locality.
268DenseMap<const InputSectionBase *, int> computeCallGraphProfileOrder() {
269  return CallGraphSort().run();
270}
271
272} // namespace elf
273} // namespace lld
274