1 //===- CallGraphSort.cpp --------------------------------------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
12 /// arranging code sections so that i-TLB misses and i-cache misses are reduced.
18 ///  - a simpler one, referred to as Call-Chain Clustering (C^3), that follows
19 ///    "Optimizing Function Placement for Large-Scale Data-Center Applications"
20 /// https://research.fb.com/wp-content/uploads/2017/01/cgo2017-hfsort-final1.pdf
21 /// - a more advanced one, referred to as Cache-Directed-Sort (CDSort), which
24 //===----------------------------------------------------------------------===//
59   Edge bestPred = {-1, 0};
62 /// Implementation of the Call-Chain Clustering (C^3). The goal of this
64 /// code sections such that page table and i-cache misses are minimized.
72 /// * Call-Chain Clustering (C³) Heuristic
88 /// * Sort non-empty clusters by density
111 // Take the edge list in Config->CallGraphProfile, resolve symbol names to
115   MapVector<SectionPair, uint64_t> &profile = config->callGraphProfile;  in CallGraphSort()
118   auto getOrCreateNode = [&](const InputSectionBase *isec) -> int {  in CallGraphSort()
122       clusters.emplace_back(clusters.size(), isec->getSize());  in CallGraphSort()
124     return res.first->second;  in CallGraphSort()
139     if (fromSB->getOutputSection() != toSB->getOutputSection())  in CallGraphSort()
152     if (toC.bestPred.from == -1 || toC.bestPred.weight < weight) {  in CallGraphSort()
168 // class). We apply union-find path-halving technique (simple to implement) in
191 // Group InputSections into clusters using the Call-Chain Clustering heuristic
209     if (c.bestPred.from == -1 || c.bestPred.weight * 10 <= c.initialWeight)  in run()
217     if (c.size + predC->size > MAX_CLUSTER_SIZE)  in run()
227   // Sort remaining non-empty clusters by density.  in run()
246   if (!config->printSymbolOrder.empty()) {  in run()
248     raw_fd_ostream os(config->printSymbolOrder, ec, sys::fs::OF_None);  in run()
250       error("cannot open " + config->printSymbolOrder + ": " + ec.message());  in run()
260         for (Symbol *sym : sections[i]->file->getSymbols())  in run()
261           if (!sym->isSection()) // Filter out section-type symbols here.  in run()
263               if (sections[i] == d->section)  in run()
264                 os << sym->getName() << "\n";  in run()
274 // Sort sections by the profile data using the Cache-Directed Sort algorithm.
275 // The placement is done by optimizing the locality by co-locating frequently
285   auto getOrCreateNode = [&](const InputSectionBase *inSec) -> size_t {  in computeCacheDirectedSortOrder()
290       funcSizes.push_back(inSec->getSize());  in computeCacheDirectedSortOrder()
293     return res.first->second;  in computeCacheDirectedSortOrder()
297   for (std::pair<SectionPair, uint64_t> &c : config->callGraphProfile) {  in computeCacheDirectedSortOrder()
301     if (fromSB->getOutputSection() != toSB->getOutputSection())  in computeCacheDirectedSortOrder()
311     // Ignore self-edges (recursive calls).  in computeCacheDirectedSortOrder()
335 // Sort sections by the profile data provided by --callgraph-profile-file.
338 // according either to the C³ or Cache-Directed-Sort ordering algorithm.
340   if (config->callGraphProfileSort == CGProfileSortKind::Cdsort)  in computeCallGraphProfileOrder()