1 //===- SectionPriorities.h --------------------------------------*- C++ -*-===// 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 #ifndef LLD_MACHO_SECTION_PRIORITIES_H 10 #define LLD_MACHO_SECTION_PRIORITIES_H 11 12 #include "InputSection.h" 13 #include "llvm/ADT/DenseMap.h" 14 #include "llvm/ADT/MapVector.h" 15 16 namespace lld::macho { 17 18 using SectionPair = std::pair<const InputSection *, const InputSection *>; 19 using StringPiecePair = std::pair<CStringInputSection *, size_t>; 20 21 class PriorityBuilder { 22 public: 23 // Reads every input section's call graph profile, and combines them into 24 // callGraphProfile. If an order file is present, any edges where one or both 25 // of the vertices are specified in the order file are discarded. 26 void extractCallGraphProfile(); 27 28 // Reads the order file at `path` into config->priorities. 29 // 30 // An order file has one entry per line, in the following format: 31 // 32 // <cpu>:<object file>:[<symbol name> | CStringEntryPrefix <cstring hash>] 33 // 34 // <cpu> and <object file> are optional. 35 // If not specified, then that entry tries to match either, 36 // 37 // 1) any symbol of the <symbol name>; 38 // Parsing this format is not quite straightforward because the symbol name 39 // itself can contain colons, so when encountering a colon, we consider the 40 // preceding characters to decide if it can be a valid CPU type or file path. 41 // If a symbol is matched by multiple entries, then it takes the 42 // lowest-ordered entry (the one nearest to the front of the list.) 43 // 44 // or 2) any cstring literal with the given hash, if the entry has the 45 // CStringEntryPrefix prefix defined below in the file. <cstring hash> is the 46 // hash of cstring literal content. 47 // 48 // Cstring literals are not symbolized, we can't identify them by name 49 // However, cstrings are deduplicated, hence unique, so we use the hash of 50 // the content of cstring literals to identify them and assign priority to it. 51 // We use the same hash as used in StringPiece, i.e. 31 bit: 52 // xxh3_64bits(string) & 0x7fffffff 53 // 54 // The file can also have line comments that start with '#'. 55 void parseOrderFile(StringRef path); 56 57 // Returns layout priorities for some or all input sections. Sections are laid 58 // out in decreasing order; that is, a higher priority section will be closer 59 // to the beginning of its output section. 60 // 61 // If either an order file or a call graph profile are present, this is used 62 // as the source of priorities. If both are present, the order file takes 63 // precedence, but the call graph profile is still used for symbols that don't 64 // appear in the order file. If neither is present, an empty map is returned. 65 // 66 // Each section gets assigned the priority of the highest-priority symbol it 67 // contains. 68 llvm::DenseMap<const InputSection *, int> buildInputSectionPriorities(); 69 std::vector<StringPiecePair> 70 buildCStringPriorities(ArrayRef<CStringInputSection *>); 71 72 private: 73 // The symbol with the smallest priority should be ordered first in the output 74 // section (modulo input section contiguity constraints). 75 struct SymbolPriorityEntry { 76 // The priority given to a matching symbol, regardless of which object file 77 // it originated from. 78 int anyObjectFile = 0; 79 // The priority given to a matching symbol from a particular object file. 80 llvm::DenseMap<llvm::StringRef, int> objectFiles; 81 }; 82 const llvm::StringRef CStringEntryPrefix = "CSTR;"; 83 84 std::optional<int> getSymbolPriority(const Defined *sym); 85 std::optional<int> getSymbolOrCStringPriority(const StringRef key, 86 InputFile *f); 87 llvm::DenseMap<llvm::StringRef, SymbolPriorityEntry> priorities; 88 llvm::MapVector<SectionPair, uint64_t> callGraphProfile; 89 }; 90 91 extern PriorityBuilder priorityBuilder; 92 } // namespace lld::macho 93 94 #endif 95