Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/lld/ELF/CallGraphSort.cpp
Line
Count
Source (jump to first uncovered line)
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 layed 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 incomming
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 ammount 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
using namespace llvm;
49
using namespace lld;
50
using namespace lld::elf;
51
52
namespace {
53
struct Edge {
54
  int from;
55
  uint64_t weight;
56
};
57
58
struct Cluster {
59
58
  Cluster(int sec, size_t s) : sections{sec}, size(s) {}
60
61
297
  double getDensity() const {
62
297
    if (size == 0)
63
0
      return 0;
64
297
    return double(weight) / double(size);
65
297
  }
66
67
  std::vector<int> sections;
68
  size_t size = 0;
69
  uint64_t weight = 0;
70
  uint64_t initialWeight = 0;
71
  Edge bestPred = {-1, 0};
72
};
73
74
class CallGraphSort {
75
public:
76
  CallGraphSort();
77
78
  DenseMap<const InputSectionBase *, int> run();
79
80
private:
81
  std::vector<Cluster> clusters;
82
  std::vector<const InputSectionBase *> sections;
83
84
  void groupClusters();
85
};
86
87
// Maximum ammount the combined cluster density can be worse than the original
88
// cluster to consider merging.
89
constexpr int MAX_DENSITY_DEGRADATION = 8;
90
91
// Maximum cluster size in bytes.
92
constexpr uint64_t MAX_CLUSTER_SIZE = 1024 * 1024;
93
} // end anonymous namespace
94
95
using SectionPair =
96
    std::pair<const InputSectionBase *, const InputSectionBase *>;
97
98
// Take the edge list in Config->CallGraphProfile, resolve symbol names to
99
// Symbols, and generate a graph between InputSections with the provided
100
// weights.
101
11
CallGraphSort::CallGraphSort() {
102
11
  MapVector<SectionPair, uint64_t> &profile = config->callGraphProfile;
103
11
  DenseMap<const InputSectionBase *, int> secToCluster;
104
11
105
104
  auto getOrCreateNode = [&](const InputSectionBase *isec) -> int {
106
104
    auto res = secToCluster.insert(std::make_pair(isec, clusters.size()));
107
104
    if (res.second) {
108
58
      sections.push_back(isec);
109
58
      clusters.emplace_back(clusters.size(), isec->getSize());
110
58
    }
111
104
    return res.first->second;
112
104
  };
113
11
114
11
  // Create the graph.
115
53
  for (std::pair<SectionPair, uint64_t> &c : profile) {
116
53
    const auto *fromSB = cast<InputSectionBase>(c.first.first->repl);
117
53
    const auto *toSB = cast<InputSectionBase>(c.first.second->repl);
118
53
    uint64_t weight = c.second;
119
53
120
53
    // Ignore edges between input sections belonging to different output
121
53
    // sections.  This is done because otherwise we would end up with clusters
122
53
    // containing input sections that can't actually be placed adjacently in the
123
53
    // output.  This messes with the cluster size and density calculations.  We
124
53
    // would also end up moving input sections in other output sections without
125
53
    // moving them closer to what calls them.
126
53
    if (fromSB->getOutputSection() != toSB->getOutputSection())
127
1
      continue;
128
52
129
52
    int from = getOrCreateNode(fromSB);
130
52
    int to = getOrCreateNode(toSB);
131
52
132
52
    clusters[to].weight += weight;
133
52
134
52
    if (from == to)
135
3
      continue;
136
49
137
49
    // Remember the best edge.
138
49
    Cluster &toC = clusters[to];
139
49
    if (toC.bestPred.from == -1 || 
toC.bestPred.weight < weight17
) {
140
36
      toC.bestPred.from = from;
141
36
      toC.bestPred.weight = weight;
142
36
    }
143
49
  }
144
11
  for (Cluster &c : clusters)
145
58
    c.initialWeight = c.weight;
146
11
}
147
148
// It's bad to merge clusters which would degrade the density too much.
149
27
static bool isNewDensityBad(Cluster &a, Cluster &b) {
150
27
  double newDensity = double(a.weight + b.weight) / double(a.size + b.size);
151
27
  return newDensity < a.getDensity() / MAX_DENSITY_DEGRADATION;
152
27
}
153
154
26
static void mergeClusters(Cluster &into, Cluster &from) {
155
26
  into.sections.insert(into.sections.end(), from.sections.begin(),
156
26
                       from.sections.end());
157
26
  into.size += from.size;
158
26
  into.weight += from.weight;
159
26
  from.sections.clear();
160
26
  from.size = 0;
161
26
  from.weight = 0;
162
26
}
163
164
// Group InputSections into clusters using the Call-Chain Clustering heuristic
165
// then sort the clusters by density.
166
11
void CallGraphSort::groupClusters() {
167
11
  std::vector<int> sortedSecs(clusters.size());
168
11
  std::vector<Cluster *> secToCluster(clusters.size());
169
11
170
69
  for (size_t i = 0; i < clusters.size(); 
++i58
) {
171
58
    sortedSecs[i] = i;
172
58
    secToCluster[i] = &clusters[i];
173
58
  }
174
11
175
103
  llvm::stable_sort(sortedSecs, [&](int a, int b) {
176
103
    return clusters[a].getDensity() > clusters[b].getDensity();
177
103
  });
178
11
179
58
  for (int si : sortedSecs) {
180
58
    // clusters[si] is the same as secToClusters[si] here because it has not
181
58
    // been merged into another cluster yet.
182
58
    Cluster &c = clusters[si];
183
58
184
58
    // Don't consider merging if the edge is unlikely.
185
58
    if (c.bestPred.from == -1 || 
c.bestPred.weight * 10 <= c.initialWeight32
)
186
27
      continue;
187
31
188
31
    Cluster *predC = secToCluster[c.bestPred.from];
189
31
    if (predC == &c)
190
3
      continue;
191
28
192
28
    if (c.size + predC->size > MAX_CLUSTER_SIZE)
193
1
      continue;
194
27
195
27
    if (isNewDensityBad(*predC, c))
196
1
      continue;
197
26
198
26
    // NOTE: Consider using a disjoint-set to track section -> cluster mapping
199
26
    // if this is ever slow.
200
26
    for (int si : c.sections)
201
30
      secToCluster[si] = predC;
202
26
203
26
    mergeClusters(*predC, c);
204
26
  }
205
11
206
11
  // Remove empty or dead nodes. Invalidates all cluster indices.
207
58
  llvm::erase_if(clusters, [](const Cluster &c) {
208
58
    return c.size == 0 || 
c.sections.empty()32
;
209
58
  });
210
11
211
11
  // Sort by density.
212
32
  llvm::stable_sort(clusters, [](const Cluster &a, const Cluster &b) {
213
32
    return a.getDensity() > b.getDensity();
214
32
  });
215
11
}
216
217
11
DenseMap<const InputSectionBase *, int> CallGraphSort::run() {
218
11
  groupClusters();
219
11
220
11
  // Generate order.
221
11
  DenseMap<const InputSectionBase *, int> orderMap;
222
11
  ssize_t curOrder = 1;
223
11
224
11
  for (const Cluster &c : clusters)
225
32
    for (int secIndex : c.sections)
226
58
      orderMap[sections[secIndex]] = curOrder++;
227
11
228
11
  if (!config->printSymbolOrder.empty()) {
229
2
    std::error_code ec;
230
2
    raw_fd_ostream os(config->printSymbolOrder, ec, sys::fs::F_None);
231
2
    if (ec) {
232
0
      error("cannot open " + config->printSymbolOrder + ": " + ec.message());
233
0
      return orderMap;
234
0
    }
235
2
236
2
    // Print the symbols ordered by C3, in the order of increasing curOrder
237
2
    // Instead of sorting all the orderMap, just repeat the loops above.
238
2
    for (const Cluster &c : clusters)
239
4
      for (int secIndex : c.sections)
240
8
        // Search all the symbols in the file of the section
241
8
        // and find out a Defined symbol with name that is within the section.
242
8
        for (Symbol *sym: sections[secIndex]->file->getSymbols())
243
40
          if (!sym->isSection()) // Filter out section-type symbols here.
244
40
            if (auto *d = dyn_cast<Defined>(sym))
245
32
              if (sections[secIndex] == d->section)
246
8
                os << sym->getName() << "\n";
247
2
  }
248
11
249
11
  return orderMap;
250
11
}
251
252
// Sort sections by the profile data provided by -callgraph-profile-file
253
//
254
// This first builds a call graph based on the profile data then merges sections
255
// according to the C³ huristic. All clusters are then sorted by a density
256
// metric to further improve locality.
257
11
DenseMap<const InputSectionBase *, int> elf::computeCallGraphProfileOrder() {
258
11
  return CallGraphSort().run();
259
11
}