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 static StringRef getSectionName(const Section &sec) { return sec.name; }
36 ArrayRef<Defined *> getSymbols(const Section &sec) {
37 auto it = secToSym.find(Val: &sec);
38 if (it == secToSym.end())
39 return {};
40 return ArrayRef(it->second);
41 }
42
43 static void
44 getSectionHashes(const Section &sec, SmallVectorImpl<uint64_t> &hashes,
45 const DenseMap<const void *, uint64_t> &sectionToIdx) {
46 constexpr unsigned windowSize = 4;
47
48 // Calculate content hashes: k-mers and the last k-1 bytes.
49 ArrayRef<uint8_t> data = sec.content();
50 if (data.size() >= windowSize)
51 for (size_t i = 0; i <= data.size() - windowSize; ++i)
52 hashes.push_back(Elt: support::endian::read32le(P: data.data() + i));
53 for (uint8_t byte : data.take_back(N: windowSize - 1))
54 hashes.push_back(Elt: byte);
55
56 llvm::sort(C&: hashes);
57 hashes.erase(CS: llvm::unique(R&: hashes), CE: hashes.end());
58 }
59
60 static StringRef getSymName(const Defined &sym) { return sym.getName(); }
61 static uint64_t getSymValue(const Defined &sym) { return sym.value; }
62 static uint64_t getSymSize(const Defined &sym) { return sym.size; }
63};
64} // namespace
65
66DenseMap<const InputSectionBase *, int> elf::runBalancedPartitioning(
67 Ctx &ctx, StringRef profilePath,
68 ArrayRef<BPCompressionSortSpec> compressionSortSpecs,
69 bool forFunctionCompression, bool forDataCompression,
70 bool compressionSortStartupFunctions, bool verbose) {
71 // Collect candidate sections and associated symbols.
72 SmallVector<InputSectionBase *> sections;
73 DenseMap<CachedHashStringRef, std::set<unsigned>> rootSymbolToSectionIdxs;
74 BPOrdererELF orderer;
75
76 auto addSection = [&](Symbol &sym) {
77 auto *d = dyn_cast<Defined>(Val: &sym);
78 if (!d)
79 return;
80 auto *sec = dyn_cast_or_null<InputSection>(Val: d->section);
81 // Skip section symbols. Skip empty, discarded, ICF folded sections, .bss.
82 // ICF folded sections are already dead (!isLive()), so no separate check
83 // is needed.
84 if (sym.isSection() || !sec || sec->size == 0 || !sec->isLive() ||
85 !sec->content().data() || !orderer.secToSym.try_emplace(Key: sec, Args&: d).second)
86 return;
87 rootSymbolToSectionIdxs[CachedHashStringRef(
88 lld::utils::getRootSymbol(Name: sym.getName()))]
89 .insert(x: sections.size());
90 sections.emplace_back(Args&: sec);
91 };
92
93 for (Symbol *sym : ctx.symtab->getSymbols())
94 addSection(*sym);
95 for (ELFFileBase *file : ctx.objectFiles)
96 for (Symbol *sym : file->getLocalSymbols())
97 addSection(*sym);
98 return orderer.computeOrder(profilePath, compressionSortSpecs,
99 forFunctionCompression, forDataCompression,
100 compressionSortStartupFunctions, verbose,
101 sections, rootSymbolToSectionIdxs);
102}
103