contrib/llvm/tools/lld/ELF/CallGraphSort.cpp

   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   Cluster(int sec, size_t s) : sections{sec}, size(s) {}
  60
  61   double getDensity() const {
  62     if (size == 0)
  63       return 0;
  64     return double(weight) / double(size);
  65   }
  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 CallGraphSort::CallGraphSort() {
 102   MapVector<SectionPair, uint64_t> &profile = config->callGraphProfile;
 103   DenseMap<const InputSectionBase *, int> secToCluster;
 104
 105   auto getOrCreateNode = [&](const InputSectionBase *isec) -> int {
 106     auto res = secToCluster.insert(std::make_pair(isec, clusters.size()));
 107     if (res.second) {
 108       sections.push_back(isec);
 109       clusters.emplace_back(clusters.size(), isec->getSize());
 110     }
 111     return res.first->second;
 112   };
 113
 114   // Create the graph.
 115   for (std::pair<SectionPair, uint64_t> &c : profile) {
 116     const auto *fromSB = cast<InputSectionBase>(c.first.first->repl);
 117     const auto *toSB = cast<InputSectionBase>(c.first.second->repl);
 118     uint64_t weight = c.second;
 119
 120     // Ignore edges between input sections belonging to different output
 121     // sections.  This is done because otherwise we would end up with clusters
 122     // containing input sections that can't actually be placed adjacently in the
 123     // output.  This messes with the cluster size and density calculations.  We
 124     // would also end up moving input sections in other output sections without
 125     // moving them closer to what calls them.
 126     if (fromSB->getOutputSection() != toSB->getOutputSection())
 127       continue;
 128
 129     int from = getOrCreateNode(fromSB);
 130     int to = getOrCreateNode(toSB);
 131
 132     clusters[to].weight += weight;
 133
 134     if (from == to)
 135       continue;
 136
 137     // Remember the best edge.
 138     Cluster &toC = clusters[to];
 139     if (toC.bestPred.from == -1 || toC.bestPred.weight < weight) {
 140       toC.bestPred.from = from;
 141       toC.bestPred.weight = weight;
 142     }
 143   }
 144   for (Cluster &c : clusters)
 145     c.initialWeight = c.weight;
 146 }
 147
 148 // It's bad to merge clusters which would degrade the density too much.
 149 static bool isNewDensityBad(Cluster &a, Cluster &b) {
 150   double newDensity = double(a.weight + b.weight) / double(a.size + b.size);
 151   return newDensity < a.getDensity() / MAX_DENSITY_DEGRADATION;
 152 }
 153
 154 static void mergeClusters(Cluster &into, Cluster &from) {
 155   into.sections.insert(into.sections.end(), from.sections.begin(),
 156                        from.sections.end());
 157   into.size += from.size;
 158   into.weight += from.weight;
 159   from.sections.clear();
 160   from.size = 0;
 161   from.weight = 0;
 162 }
 163
 164 // Group InputSections into clusters using the Call-Chain Clustering heuristic
 165 // then sort the clusters by density.
 166 void CallGraphSort::groupClusters() {
 167   std::vector<int> sortedSecs(clusters.size());
 168   std::vector<Cluster *> secToCluster(clusters.size());
 169
 170   for (size_t i = 0; i < clusters.size(); ++i) {
 171     sortedSecs[i] = i;
 172     secToCluster[i] = &clusters[i];
 173   }
 174
 175   llvm::stable_sort(sortedSecs, [&](int a, int b) {
 176     return clusters[a].getDensity() > clusters[b].getDensity();
 177   });
 178
 179   for (int si : sortedSecs) {
 180     // clusters[si] is the same as secToClusters[si] here because it has not
 181     // been merged into another cluster yet.
 182     Cluster &c = clusters[si];
 183
 184     // Don't consider merging if the edge is unlikely.
 185     if (c.bestPred.from == -1 || c.bestPred.weight * 10 <= c.initialWeight)
 186       continue;
 187
 188     Cluster *predC = secToCluster[c.bestPred.from];
 189     if (predC == &c)
 190       continue;
 191
 192     if (c.size + predC->size > MAX_CLUSTER_SIZE)
 193       continue;
 194
 195     if (isNewDensityBad(*predC, c))
 196       continue;
 197
 198     // NOTE: Consider using a disjoint-set to track section -> cluster mapping
 199     // if this is ever slow.
 200     for (int si : c.sections)
 201       secToCluster[si] = predC;
 202
 203     mergeClusters(*predC, c);
 204   }
 205
 206   // Remove empty or dead nodes. Invalidates all cluster indices.
 207   llvm::erase_if(clusters, [](const Cluster &c) {
 208     return c.size == 0 || c.sections.empty();
 209   });
 210
 211   // Sort by density.
 212   llvm::stable_sort(clusters, [](const Cluster &a, const Cluster &b) {
 213     return a.getDensity() > b.getDensity();
 214   });
 215 }
 216
 217 DenseMap<const InputSectionBase *, int> CallGraphSort::run() {
 218   groupClusters();
 219
 220   // Generate order.
 221   DenseMap<const InputSectionBase *, int> orderMap;
 222   ssize_t curOrder = 1;
 223
 224   for (const Cluster &c : clusters)
 225     for (int secIndex : c.sections)
 226       orderMap[sections[secIndex]] = curOrder++;
 227
 228   if (!config->printSymbolOrder.empty()) {
 229     std::error_code ec;
 230     raw_fd_ostream os(config->printSymbolOrder, ec, sys::fs::F_None);
 231     if (ec) {
 232       error("cannot open " + config->printSymbolOrder + ": " + ec.message());
 233       return orderMap;
 234     }
 235
 236     // Print the symbols ordered by C3, in the order of increasing curOrder
 237     // Instead of sorting all the orderMap, just repeat the loops above.
 238     for (const Cluster &c : clusters)
 239       for (int secIndex : c.sections)
 240         // Search all the symbols in the file of the section
 241         // and find out a Defined symbol with name that is within the section.
 242         for (Symbol *sym: sections[secIndex]->file->getSymbols())
 243           if (!sym->isSection()) // Filter out section-type symbols here.
 244             if (auto *d = dyn_cast<Defined>(sym))
 245               if (sections[secIndex] == d->section)
 246                 os << sym->getName() << "\n";
 247   }
 248
 249   return orderMap;
 250 }
 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 DenseMap<const InputSectionBase *, int> elf::computeCallGraphProfileOrder() {
 258   return CallGraphSort().run();
 259 }