1 //===- BPSectionOrderer.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 #include "BPSectionOrderer.h"
10 #include "InputFiles.h"
11 #include "InputSection.h"
12 #include "SymbolTable.h"
13 #include "Symbols.h"
14 #include "lld/Common/BPSectionOrdererBase.inc"
15 #include "llvm/Support/Endian.h"
16
17 using namespace llvm;
18 using namespace lld::elf;
19
20 namespace {
21 struct BPOrdererELF;
22 }
23 template <> struct lld::BPOrdererTraits<struct BPOrdererELF> {
24 using Section = elf::InputSectionBase;
25 using Defined = elf::Defined;
26 };
27 namespace {
28 struct BPOrdererELF : lld::BPOrderer<BPOrdererELF> {
29 DenseMap<const InputSectionBase *, Defined *> secToSym;
30
getSize__anon82a32a8b0211::BPOrdererELF31 static uint64_t getSize(const Section &sec) { return sec.getSize(); }
isCodeSection__anon82a32a8b0211::BPOrdererELF32 static bool isCodeSection(const Section &sec) {
33 return sec.flags & ELF::SHF_EXECINSTR;
34 }
getSymbols__anon82a32a8b0211::BPOrdererELF35 ArrayRef<Defined *> getSymbols(const Section &sec) {
36 auto it = secToSym.find(&sec);
37 if (it == secToSym.end())
38 return {};
39 return ArrayRef(it->second);
40 }
41
42 static void
getSectionHashes__anon82a32a8b0211::BPOrdererELF43 getSectionHashes(const Section &sec, SmallVectorImpl<uint64_t> &hashes,
44 const DenseMap<const void *, uint64_t> §ionToIdx) {
45 constexpr unsigned windowSize = 4;
46
47 // Calculate content hashes: k-mers and the last k-1 bytes.
48 ArrayRef<uint8_t> data = sec.content();
49 if (data.size() >= windowSize)
50 for (size_t i = 0; i <= data.size() - windowSize; ++i)
51 hashes.push_back(support::endian::read32le(data.data() + i));
52 for (uint8_t byte : data.take_back(windowSize - 1))
53 hashes.push_back(byte);
54
55 llvm::sort(hashes);
56 hashes.erase(llvm::unique(hashes), hashes.end());
57 }
58
getSymName__anon82a32a8b0211::BPOrdererELF59 static StringRef getSymName(const Defined &sym) { return sym.getName(); }
getSymValue__anon82a32a8b0211::BPOrdererELF60 static uint64_t getSymValue(const Defined &sym) { return sym.value; }
getSymSize__anon82a32a8b0211::BPOrdererELF61 static uint64_t getSymSize(const Defined &sym) { return sym.size; }
62 };
63 } // namespace
64
runBalancedPartitioning(Ctx & ctx,StringRef profilePath,bool forFunctionCompression,bool forDataCompression,bool compressionSortStartupFunctions,bool verbose)65 DenseMap<const InputSectionBase *, int> elf::runBalancedPartitioning(
66 Ctx &ctx, StringRef profilePath, bool forFunctionCompression,
67 bool forDataCompression, bool compressionSortStartupFunctions,
68 bool verbose) {
69 // Collect candidate sections and associated symbols.
70 SmallVector<InputSectionBase *> sections;
71 DenseMap<CachedHashStringRef, std::set<unsigned>> rootSymbolToSectionIdxs;
72 BPOrdererELF orderer;
73
74 auto addSection = [&](Symbol &sym) {
75 auto *d = dyn_cast<Defined>(&sym);
76 if (!d)
77 return;
78 auto *sec = dyn_cast_or_null<InputSection>(d->section);
79 // Skip empty, discarded, ICF folded sections. Skipping ICF folded sections
80 // reduces duplicate detection work in BPSectionOrderer.
81 if (!sec || sec->size == 0 || !sec->isLive() || sec->repl != sec ||
82 !orderer.secToSym.try_emplace(sec, d).second)
83 return;
84 rootSymbolToSectionIdxs[CachedHashStringRef(
85 lld::utils::getRootSymbol(sym.getName()))]
86 .insert(sections.size());
87 sections.emplace_back(sec);
88 };
89
90 for (Symbol *sym : ctx.symtab->getSymbols())
91 addSection(*sym);
92 for (ELFFileBase *file : ctx.objectFiles)
93 for (Symbol *sym : file->getLocalSymbols())
94 addSection(*sym);
95 return orderer.computeOrder(profilePath, forFunctionCompression,
96 forDataCompression,
97 compressionSortStartupFunctions, verbose,
98 sections, rootSymbolToSectionIdxs);
99 }
100