148 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 "InputSection.h"11#include "Relocations.h"12#include "Symbols.h"13#include "lld/Common/BPSectionOrdererBase.inc"14#include "llvm/ADT/DenseMap.h"15#include "llvm/ADT/StableHashing.h"16#include "llvm/Support/Endian.h"17#include "llvm/Support/xxhash.h"18 19#define DEBUG_TYPE "bp-section-orderer"20 21using namespace llvm;22using namespace lld::macho;23 24namespace {25struct BPOrdererMachO;26}27template <> struct lld::BPOrdererTraits<struct BPOrdererMachO> {28 using Section = macho::InputSection;29 using Defined = macho::Defined;30};31namespace {32struct BPOrdererMachO : lld::BPOrderer<BPOrdererMachO> {33 static uint64_t getSize(const Section &sec) { return sec.getSize(); }34 static bool isCodeSection(const Section &sec) {35 return macho::isCodeSection(&sec);36 }37 static ArrayRef<Defined *> getSymbols(const Section &sec) {38 return sec.symbols;39 }40 41 // Linkage names can be prefixed with "_" or "l_" on Mach-O. See42 // Mangler::getNameWithPrefix() for details.43 std::optional<StringRef> static getResolvedLinkageName(llvm::StringRef name) {44 if (name.consume_front("_") || name.consume_front("l_"))45 return name;46 return {};47 }48 49 static void50 getSectionHashes(const Section &sec, llvm::SmallVectorImpl<uint64_t> &hashes,51 const llvm::DenseMap<const void *, uint64_t> §ionToIdx) {52 constexpr unsigned windowSize = 4;53 54 // Calculate content hashes: k-mers and the last k-1 bytes.55 ArrayRef<uint8_t> data = sec.data;56 if (data.size() >= windowSize)57 for (size_t i = 0; i <= data.size() - windowSize; ++i)58 hashes.push_back(llvm::support::endian::read32le(data.data() + i));59 for (uint8_t byte : data.take_back(windowSize - 1))60 hashes.push_back(byte);61 62 // Calculate relocation hashes63 for (const auto &r : sec.relocs) {64 uint32_t relocLength = 1 << r.length;65 if (r.referent.isNull() || r.offset + relocLength > data.size())66 continue;67 68 uint64_t relocHash = getRelocHash(r, sectionToIdx);69 uint32_t start = (r.offset < windowSize) ? 0 : r.offset - windowSize + 1;70 for (uint32_t i = start; i < r.offset + relocLength; i++) {71 auto window = data.drop_front(i).take_front(windowSize);72 hashes.push_back(xxh3_64bits(window) ^ relocHash);73 }74 }75 76 llvm::sort(hashes);77 hashes.erase(llvm::unique(hashes), hashes.end());78 }79 80 static llvm::StringRef getSymName(const Defined &sym) {81 return sym.getName();82 }83 static uint64_t getSymValue(const Defined &sym) { return sym.value; }84 static uint64_t getSymSize(const Defined &sym) { return sym.size; }85 86private:87 static uint64_t88 getRelocHash(const macho::Reloc &reloc,89 const llvm::DenseMap<const void *, uint64_t> §ionToIdx) {90 auto *isec = reloc.getReferentInputSection();91 std::optional<uint64_t> sectionIdx;92 if (auto it = sectionToIdx.find(isec); it != sectionToIdx.end())93 sectionIdx = it->second;94 uint64_t kind = -1, value = 0;95 if (isec)96 kind = uint64_t(isec->kind());97 98 if (auto *sym = reloc.referent.dyn_cast<Symbol *>()) {99 kind = (kind << 8) | uint8_t(sym->kind());100 if (auto *d = llvm::dyn_cast<Defined>(sym))101 value = d->value;102 }103 return llvm::stable_hash_combine(kind, sectionIdx.value_or(0), value,104 reloc.addend);105 }106};107} // namespace108 109DenseMap<const InputSection *, int> lld::macho::runBalancedPartitioning(110 StringRef profilePath, bool forFunctionCompression, bool forDataCompression,111 bool compressionSortStartupFunctions, bool verbose) {112 // Collect candidate sections and associated symbols.113 SmallVector<InputSection *> sections;114 DenseMap<CachedHashStringRef, std::set<unsigned>> rootSymbolToSectionIdxs;115 for (const auto *file : inputFiles) {116 for (auto *sec : file->sections) {117 for (auto &subsec : sec->subsections) {118 auto *isec = subsec.isec;119 if (!isec || isec->data.empty() || !isec->data.data())120 continue;121 // CString section order is handled by122 // {Deduplicated}CStringSection::finalizeContents()123 if (isa<CStringInputSection>(isec) || isec->isFinal)124 continue;125 // ConcatInputSections are entirely live or dead, so the offset is126 // irrelevant.127 if (isa<ConcatInputSection>(isec) && !isec->isLive(0))128 continue;129 size_t idx = sections.size();130 sections.emplace_back(isec);131 for (auto *sym : BPOrdererMachO::getSymbols(*isec)) {132 auto rootName = lld::utils::getRootSymbol(sym->getName());133 rootSymbolToSectionIdxs[CachedHashStringRef(rootName)].insert(idx);134 if (auto linkageName =135 BPOrdererMachO::getResolvedLinkageName(rootName))136 rootSymbolToSectionIdxs[CachedHashStringRef(*linkageName)].insert(137 idx);138 }139 }140 }141 }142 143 return BPOrdererMachO().computeOrder(profilePath, forFunctionCompression,144 forDataCompression,145 compressionSortStartupFunctions, verbose,146 sections, rootSymbolToSectionIdxs);147}148