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