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 50 using namespace llvm; 51 52 namespace lld { 53 namespace elf { 54 55 namespace { 56 struct Edge { 57 int from; 58 uint64_t weight; 59 }; 60 61 struct 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 78 class CallGraphSort { 79 public: 80 CallGraphSort(); 81 82 DenseMap<const InputSectionBase *, int> run(); 83 84 private: 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. 91 constexpr int MAX_DENSITY_DEGRADATION = 8; 92 93 // Maximum cluster size in bytes. 94 constexpr uint64_t MAX_CLUSTER_SIZE = 1024 * 1024; 95 } // end anonymous namespace 96 97 using 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. 103 CallGraphSort::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. 151 static 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. 159 static 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 167 static 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. 182 DenseMap<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. 268 DenseMap<const InputSectionBase *, int> computeCallGraphProfileOrder() { 269 return CallGraphSort().run(); 270 } 271 272 } // namespace elf 273 } // namespace lld 274