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 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 void 43 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 } // namespace 64 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