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 *>;
19using StringPiecePair = std::pair<CStringInputSection *, size_t>;
20
21class PriorityBuilder {
22public:
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
72private:
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
91extern PriorityBuilder priorityBuilder;
92} // namespace lld::macho
93
94#endif
95