102 lines · cpp
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-exception6//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(&sec);37 if (it == secToSym.end())38 return {};39 return ArrayRef(it->second);40 }41 42 static void43 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 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} // namespace64 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>(&sym);76 if (!d)77 return;78 auto *sec = dyn_cast_or_null<InputSection>(d->section);79 // Skip section symbols. Skip empty, discarded, ICF folded sections, .bss.80 // Skipping ICF folded sections reduces duplicate detection work in81 // BPSectionOrderer.82 if (sym.isSection() || !sec || sec->size == 0 || !sec->isLive() ||83 sec->repl != sec || !sec->content().data() ||84 !orderer.secToSym.try_emplace(sec, d).second)85 return;86 rootSymbolToSectionIdxs[CachedHashStringRef(87 lld::utils::getRootSymbol(sym.getName()))]88 .insert(sections.size());89 sections.emplace_back(sec);90 };91 92 for (Symbol *sym : ctx.symtab->getSymbols())93 addSection(*sym);94 for (ELFFileBase *file : ctx.objectFiles)95 for (Symbol *sym : file->getLocalSymbols())96 addSection(*sym);97 return orderer.computeOrder(profilePath, forFunctionCompression,98 forDataCompression,99 compressionSortStartupFunctions, verbose,100 sections, rootSymbolToSectionIdxs);101}102