250 lines · 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-exception6//7//===----------------------------------------------------------------------===//8///9/// This is based on the ELF port, see ELF/CallGraphSort.cpp for the details10/// about the algorithm.11///12//===----------------------------------------------------------------------===//13 14#include "CallGraphSort.h"15#include "COFFLinkerContext.h"16#include "InputFiles.h"17#include "SymbolTable.h"18#include "Symbols.h"19 20#include <numeric>21 22using namespace llvm;23using namespace lld;24using namespace lld::coff;25 26namespace {27struct Edge {28 int from;29 uint64_t weight;30};31 32struct Cluster {33 Cluster(int sec, size_t s) : next(sec), prev(sec), size(s) {}34 35 double getDensity() const {36 if (size == 0)37 return 0;38 return double(weight) / double(size);39 }40 41 int next;42 int prev;43 uint64_t size;44 uint64_t weight = 0;45 uint64_t initialWeight = 0;46 Edge bestPred = {-1, 0};47};48 49class CallGraphSort {50public:51 CallGraphSort(COFFLinkerContext &ctx);52 53 DenseMap<const SectionChunk *, int> run();54 55private:56 std::vector<Cluster> clusters;57 std::vector<const SectionChunk *> sections;58 59 COFFLinkerContext &ctx;60};61 62// Maximum amount the combined cluster density can be worse than the original63// cluster to consider merging.64constexpr int MAX_DENSITY_DEGRADATION = 8;65 66// Maximum cluster size in bytes.67constexpr uint64_t MAX_CLUSTER_SIZE = 1024 * 1024;68} // end anonymous namespace69 70using SectionPair = std::pair<const SectionChunk *, const SectionChunk *>;71 72// Take the edge list in Config->CallGraphProfile, resolve symbol names to73// Symbols, and generate a graph between InputSections with the provided74// weights.75CallGraphSort::CallGraphSort(COFFLinkerContext &ctx) : ctx(ctx) {76 const MapVector<SectionPair, uint64_t> &profile = ctx.config.callGraphProfile;77 DenseMap<const SectionChunk *, int> secToCluster;78 79 auto getOrCreateNode = [&](const SectionChunk *isec) -> int {80 auto res = secToCluster.try_emplace(isec, clusters.size());81 if (res.second) {82 sections.push_back(isec);83 clusters.emplace_back(clusters.size(), isec->getSize());84 }85 return res.first->second;86 };87 88 // Create the graph.89 for (const std::pair<SectionPair, uint64_t> &c : profile) {90 const auto *fromSec = cast<SectionChunk>(c.first.first->repl);91 const auto *toSec = cast<SectionChunk>(c.first.second->repl);92 uint64_t weight = c.second;93 94 // Ignore edges between input sections belonging to different output95 // sections. This is done because otherwise we would end up with clusters96 // containing input sections that can't actually be placed adjacently in the97 // output. This messes with the cluster size and density calculations. We98 // would also end up moving input sections in other output sections without99 // moving them closer to what calls them.100 if (ctx.getOutputSection(fromSec) != ctx.getOutputSection(toSec))101 continue;102 103 int from = getOrCreateNode(fromSec);104 int to = getOrCreateNode(toSec);105 106 clusters[to].weight += weight;107 108 if (from == to)109 continue;110 111 // Remember the best edge.112 Cluster &toC = clusters[to];113 if (toC.bestPred.from == -1 || toC.bestPred.weight < weight) {114 toC.bestPred.from = from;115 toC.bestPred.weight = weight;116 }117 }118 for (Cluster &c : clusters)119 c.initialWeight = c.weight;120}121 122// It's bad to merge clusters which would degrade the density too much.123static bool isNewDensityBad(Cluster &a, Cluster &b) {124 double newDensity = double(a.weight + b.weight) / double(a.size + b.size);125 return newDensity < a.getDensity() / MAX_DENSITY_DEGRADATION;126}127 128// Find the leader of V's belonged cluster (represented as an equivalence129// class). We apply union-find path-halving technique (simple to implement) in130// the meantime as it decreases depths and the time complexity.131static int getLeader(std::vector<int> &leaders, int v) {132 while (leaders[v] != v) {133 leaders[v] = leaders[leaders[v]];134 v = leaders[v];135 }136 return v;137}138 139static void mergeClusters(std::vector<Cluster> &cs, Cluster &into, int intoIdx,140 Cluster &from, int fromIdx) {141 int tail1 = into.prev, tail2 = from.prev;142 into.prev = tail2;143 cs[tail2].next = intoIdx;144 from.prev = tail1;145 cs[tail1].next = fromIdx;146 into.size += from.size;147 into.weight += from.weight;148 from.size = 0;149 from.weight = 0;150}151 152// Group InputSections into clusters using the Call-Chain Clustering heuristic153// then sort the clusters by density.154DenseMap<const SectionChunk *, int> CallGraphSort::run() {155 std::vector<int> sorted(clusters.size());156 std::vector<int> leaders(clusters.size());157 158 std::iota(leaders.begin(), leaders.end(), 0);159 std::iota(sorted.begin(), sorted.end(), 0);160 llvm::stable_sort(sorted, [&](int a, int b) {161 return clusters[a].getDensity() > clusters[b].getDensity();162 });163 164 for (int l : sorted) {165 // The cluster index is the same as the index of its leader here because166 // clusters[L] has not been merged into another cluster yet.167 Cluster &c = clusters[l];168 169 // Don't consider merging if the edge is unlikely.170 if (c.bestPred.from == -1 || c.bestPred.weight * 10 <= c.initialWeight)171 continue;172 173 int predL = getLeader(leaders, c.bestPred.from);174 if (l == predL)175 continue;176 177 Cluster *predC = &clusters[predL];178 if (c.size + predC->size > MAX_CLUSTER_SIZE)179 continue;180 181 if (isNewDensityBad(*predC, c))182 continue;183 184 leaders[l] = predL;185 mergeClusters(clusters, *predC, predL, c, l);186 }187 188 // Sort remaining non-empty clusters by density.189 sorted.clear();190 for (int i = 0, e = (int)clusters.size(); i != e; ++i)191 if (clusters[i].size > 0)192 sorted.push_back(i);193 llvm::stable_sort(sorted, [&](int a, int b) {194 return clusters[a].getDensity() > clusters[b].getDensity();195 });196 197 DenseMap<const SectionChunk *, int> orderMap;198 // Sections will be sorted by increasing order. Absent sections will have199 // priority 0 and be placed at the end of sections.200 int curOrder = INT_MIN;201 for (int leader : sorted) {202 for (int i = leader;;) {203 orderMap[sections[i]] = curOrder++;204 i = clusters[i].next;205 if (i == leader)206 break;207 }208 }209 if (!ctx.config.printSymbolOrder.empty()) {210 std::error_code ec;211 raw_fd_ostream os(ctx.config.printSymbolOrder, ec, sys::fs::OF_None);212 if (ec) {213 Err(ctx) << "cannot open " << ctx.config.printSymbolOrder << ": "214 << ec.message();215 return orderMap;216 }217 // Print the symbols ordered by C3, in the order of increasing curOrder218 // Instead of sorting all the orderMap, just repeat the loops above.219 for (int leader : sorted)220 for (int i = leader;;) {221 const SectionChunk *sc = sections[i];222 223 // Search all the symbols in the file of the section224 // and find out a DefinedCOFF symbol with name that is within the225 // section.226 for (Symbol *sym : sc->file->getSymbols())227 if (auto *d = dyn_cast_or_null<DefinedCOFF>(sym))228 // Filter out non-COMDAT symbols and section symbols.229 if (d->isCOMDAT && !d->getCOFFSymbol().isSection() &&230 sc == d->getChunk())231 os << sym->getName() << "\n";232 i = clusters[i].next;233 if (i == leader)234 break;235 }236 }237 238 return orderMap;239}240 241// Sort sections by the profile data provided by /call-graph-ordering-file242//243// This first builds a call graph based on the profile data then merges sections244// according to the C³ heuristic. All clusters are then sorted by a density245// metric to further improve locality.246DenseMap<const SectionChunk *, int>247coff::computeCallGraphProfileOrder(COFFLinkerContext &ctx) {248 return CallGraphSort(ctx).run();249}250