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
17using namespace llvm;
18using namespace lld::elf;
19
20namespace {
21struct BPOrdererELF;
22}
23template <> struct lld::BPOrdererTraits<struct BPOrdererELF> {
24 using Section = elf::InputSectionBase;
25 using Defined = elf::Defined;
26};
27namespace {
28struct BPOrdererELF : lld::BPOrderer<BPOrdererELF> {
29 DenseMap<const InputSectionBase *, Defined *> secToSym;
30
31 static uint64_t getSize(const Section &sec) { return sec.getSize(); }
32 static bool isCodeSection(const Section &sec) {
33 return sec.flags & ELF::SHF_EXECINSTR;
34 }
35 ArrayRef<Defined *> getSymbols(const Section &sec) {
36 auto it = secToSym.find(Val: &sec);
37 if (it == secToSym.end())
38 return {};
39 return ArrayRef(it->second);
40 }
41
42 static void
43 getSectionHashes(const Section &sec, SmallVectorImpl<uint64_t> &hashes,
44 const DenseMap<const void *, uint64_t> &sectionToIdx) {
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(Elt: support::endian::read32le(P: data.data() + i));
52 for (uint8_t byte : data.take_back(N: windowSize - 1))
53 hashes.push_back(Elt: byte);
54
55 llvm::sort(C&: hashes);
56 hashes.erase(CS: llvm::unique(R&: hashes), CE: hashes.end());
57 }
58
59 static StringRef getSymName(const Defined &sym) { return sym.getName(); }
60 static uint64_t getSymValue(const Defined &sym) { return sym.value; }
61 static uint64_t getSymSize(const Defined &sym) { return sym.size; }
62};
63} // namespace
64
65DenseMap<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>(Val: &sym);
76 if (!d)
77 return;
78 auto *sec = dyn_cast_or_null<InputSection>(Val: 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(Key: sec, Args&: d).second)
83 return;
84 rootSymbolToSectionIdxs[CachedHashStringRef(
85 lld::utils::getRootSymbol(Name: sym.getName()))]
86 .insert(x: sections.size());
87 sections.emplace_back(Args&: 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