Index: lld/MachO/CMakeLists.txt =================================================================== --- lld/MachO/CMakeLists.txt +++ lld/MachO/CMakeLists.txt @@ -10,7 +10,6 @@ Arch/ARM64Common.cpp Arch/ARM64_32.cpp Arch/X86_64.cpp - CallGraphSort.cpp ConcatOutputSection.cpp Driver.cpp DriverUtils.cpp @@ -26,6 +25,7 @@ OutputSection.cpp OutputSegment.cpp Relocations.cpp + SectionPriorities.cpp SymbolTable.cpp Symbols.cpp SyntheticSections.cpp Index: lld/MachO/CallGraphSort.h =================================================================== --- lld/MachO/CallGraphSort.h +++ /dev/null @@ -1,22 +0,0 @@ -//===- CallGraphSort.h ------------------------------------------*- C++ -*-===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef LLD_MACHO_CALL_GRAPH_SORT_H -#define LLD_MACHO_CALL_GRAPH_SORT_H - -#include "InputSection.h" -#include "llvm/ADT/DenseMap.h" - -namespace lld { -namespace macho { - -llvm::DenseMap computeCallGraphProfileOrder(); -} // namespace macho -} // namespace lld - -#endif Index: lld/MachO/Driver.cpp =================================================================== --- lld/MachO/Driver.cpp +++ lld/MachO/Driver.cpp @@ -15,6 +15,7 @@ #include "ObjC.h" #include "OutputSection.h" #include "OutputSegment.h" +#include "SectionPriorities.h" #include "SymbolTable.h" #include "Symbols.h" #include "SyntheticSections.h" @@ -434,74 +435,6 @@ addFile(rerootPath(path), ForceLoad::Default); } -// An order file has one entry per line, in the following format: -// -// :: -// -// and are optional. If not specified, then that entry -// matches any symbol of that name. Parsing this format is not quite -// straightforward because the symbol name itself can contain colons, so when -// encountering a colon, we consider the preceding characters to decide if it -// can be a valid CPU type or file path. -// -// If a symbol is matched by multiple entries, then it takes the lowest-ordered -// entry (the one nearest to the front of the list.) -// -// The file can also have line comments that start with '#'. -static void parseOrderFile(StringRef path) { - Optional buffer = readFile(path); - if (!buffer) { - error("Could not read order file at " + path); - return; - } - - MemoryBufferRef mbref = *buffer; - size_t priority = std::numeric_limits::max(); - for (StringRef line : args::getLines(mbref)) { - StringRef objectFile, symbol; - line = line.take_until([](char c) { return c == '#'; }); // ignore comments - line = line.ltrim(); - - CPUType cpuType = StringSwitch(line) - .StartsWith("i386:", CPU_TYPE_I386) - .StartsWith("x86_64:", CPU_TYPE_X86_64) - .StartsWith("arm:", CPU_TYPE_ARM) - .StartsWith("arm64:", CPU_TYPE_ARM64) - .StartsWith("ppc:", CPU_TYPE_POWERPC) - .StartsWith("ppc64:", CPU_TYPE_POWERPC64) - .Default(CPU_TYPE_ANY); - - if (cpuType != CPU_TYPE_ANY && cpuType != target->cpuType) - continue; - - // Drop the CPU type as well as the colon - if (cpuType != CPU_TYPE_ANY) - line = line.drop_until([](char c) { return c == ':'; }).drop_front(); - - constexpr std::array fileEnds = {".o:", ".o):"}; - for (StringRef fileEnd : fileEnds) { - size_t pos = line.find(fileEnd); - if (pos != StringRef::npos) { - // Split the string around the colon - objectFile = line.take_front(pos + fileEnd.size() - 1); - line = line.drop_front(pos + fileEnd.size()); - break; - } - } - symbol = line.trim(); - - if (!symbol.empty()) { - SymbolPriorityEntry &entry = config->priorities[symbol]; - if (!objectFile.empty()) - entry.objectFiles.insert(std::make_pair(objectFile, priority)); - else - entry.anyObjectFile = std::max(entry.anyObjectFile, priority); - } - - --priority; - } -} - // We expect sub-library names of the form "libfoo", which will match a dylib // with a path of .*/libfoo.{dylib, tbd}. // XXX ld64 seems to ignore the extension entirely when matching sub-libraries; @@ -1057,25 +990,6 @@ assert(inputOrder <= UnspecifiedInputOrder); } -static void extractCallGraphProfile() { - TimeTraceScope timeScope("Extract call graph profile"); - for (const InputFile *file : inputFiles) { - auto *obj = dyn_cast_or_null(file); - if (!obj) - continue; - for (const CallGraphEntry &entry : obj->callGraph) { - assert(entry.fromIndex < obj->symbols.size() && - entry.toIndex < obj->symbols.size()); - auto *fromSym = dyn_cast_or_null(obj->symbols[entry.fromIndex]); - auto *toSym = dyn_cast_or_null(obj->symbols[entry.toIndex]); - - if (!fromSym || !toSym) - continue; - config->callGraphProfile[{fromSym->isec, toSym->isec}] += entry.count; - } - } -} - static void foldIdenticalLiterals() { // We always create a cStringSection, regardless of whether dedupLiterals is // true. If it isn't, we simply create a non-deduplicating CStringSection. @@ -1480,10 +1394,8 @@ replaceCommonSymbols(); StringRef orderFile = args.getLastArgValue(OPT_order_file); - if (!orderFile.empty()) { + if (!orderFile.empty()) parseOrderFile(orderFile); - config->callGraphProfileSort = false; - } referenceStubBinder(); Index: lld/MachO/SectionPriorities.h =================================================================== --- /dev/null +++ lld/MachO/SectionPriorities.h @@ -0,0 +1,56 @@ +//===- SectionPriorities.h --------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLD_MACHO_CALL_SECTION_PRIORITIES_H +#define LLD_MACHO_CALL_SECTION_PRIORITIES_H + +#include "InputSection.h" +#include "llvm/ADT/DenseMap.h" + +namespace lld { +namespace macho { + +// Reads every input section's call graph profile, and combines them into +// config->callGraphProfile. If an order file is present, any edges where one +// or both of the vertices are specified in the order file are discarded. +void extractCallGraphProfile(); + +// Reads the order file at `path` into config->priorities. +// +// An order file has one entry per line, in the following format: +// +// :: +// +// and are optional. If not specified, then that entry +// matches any symbol of that name. Parsing this format is not quite +// straightforward because the symbol name itself can contain colons, so when +// encountering a colon, we consider the preceding characters to decide if it +// can be a valid CPU type or file path. +// +// If a symbol is matched by multiple entries, then it takes the lowest-ordered +// entry (the one nearest to the front of the list.) +// +// The file can also have line comments that start with '#'. +void parseOrderFile(StringRef path); + +// Returns layout priorities for some or all input sections. Sections are laid +// out in decreasing order; that is, a higher priority section will be closer +// to the beginning of its output section. +// +// If either an order file or a call graph profile are present, this is used +// as the source of priorities. If both are present, the order file takes +// precedence, but the call graph profile is still used for symbols that don't +// appear in the order file. If neither is present, an empty map is returned. +// +// Each section gets assigned the priority of the highest-priority symbol it +// contains. +llvm::DenseMap buildInputSectionPriorities(); +} // namespace macho +} // namespace lld + +#endif Index: lld/MachO/SectionPriorities.cpp =================================================================== --- lld/MachO/SectionPriorities.cpp +++ lld/MachO/SectionPriorities.cpp @@ -1,4 +1,4 @@ -//===- CallGraphSort.cpp --------------------------------------------------===// +//===- SectionPriorities.cpp --------------------------------------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. @@ -11,23 +11,32 @@ /// //===----------------------------------------------------------------------===// -#include "CallGraphSort.h" +#include "SectionPriorities.h" #include "Config.h" #include "InputFiles.h" #include "Symbols.h" #include "Target.h" + +#include "lld/Common/Args.h" #include "lld/Common/ErrorHandler.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/MapVector.h" +#include "llvm/ADT/Optional.h" +#include "llvm/Support/Path.h" #include "llvm/Support/TimeProfiler.h" #include "llvm/Support/raw_ostream.h" #include using namespace llvm; +using namespace llvm::MachO; +using namespace llvm::sys; using namespace lld; using namespace lld::macho; namespace { + +size_t kLowestPriority = std::numeric_limits::max(); + struct Edge { int from; uint64_t weight; @@ -202,7 +211,7 @@ // priority 0 and be placed at the end of sections. // NB: This is opposite from COFF/ELF to be compatible with the existing // order-file code. - int curOrder = clusters.size(); + int curOrder = kLowestPriority; for (int leader : sorted) { for (int i = leader;;) { orderMap[sections[i]] = curOrder--; @@ -241,12 +250,134 @@ return orderMap; } +static Optional getSymbolPriority(Defined& sym) { + if (sym.isAbsolute()) + return None; + + auto it = config->priorities.find(sym.getName()); + if (it == config->priorities.end()) + return None; + const SymbolPriorityEntry &entry = it->second; + const InputFile *f = sym.isec->getFile(); + // We don't use toString(InputFile *) here because it returns the full path + // for object files, and we only want the basename. + StringRef filename; + if (f->archiveName.empty()) + filename = path::filename(f->getName()); + else + filename = saver.save(path::filename(f->archiveName) + "(" + + path::filename(f->getName()) + ")"); + return std::max(entry.objectFiles.lookup(filename), entry.anyObjectFile); +} + +void macho::extractCallGraphProfile() { + TimeTraceScope timeScope("Extract call graph profile"); + bool hasOrderFile = !config->priorities.empty(); + for (const InputFile *file : inputFiles) { + auto *obj = dyn_cast_or_null(file); + if (!obj) + continue; + for (const CallGraphEntry &entry : obj->callGraph) { + assert(entry.fromIndex < obj->symbols.size() && + entry.toIndex < obj->symbols.size()); + auto *fromSym = dyn_cast_or_null(obj->symbols[entry.fromIndex]); + auto *toSym = dyn_cast_or_null(obj->symbols[entry.toIndex]); + if (!fromSym || !toSym || (hasOrderFile && (getSymbolPriority(*fromSym) || getSymbolPriority(*toSym)))) + continue; + config->callGraphProfile[{fromSym->isec, toSym->isec}] += entry.count; + } + } +} + +void macho::parseOrderFile(StringRef path) { + assert(config->callGraphProfile.empty() && "Order file must be parsed before call graph profile is processed"); + Optional buffer = readFile(path); + if (!buffer) { + error("Could not read order file at " + path); + return; + } + + MemoryBufferRef mbref = *buffer; + size_t priority = std::numeric_limits::max(); + for (StringRef line : args::getLines(mbref)) { + StringRef objectFile, symbol; + line = line.take_until([](char c) { return c == '#'; }); // ignore comments + line = line.ltrim(); + + CPUType cpuType = StringSwitch(line) + .StartsWith("i386:", CPU_TYPE_I386) + .StartsWith("x86_64:", CPU_TYPE_X86_64) + .StartsWith("arm:", CPU_TYPE_ARM) + .StartsWith("arm64:", CPU_TYPE_ARM64) + .StartsWith("ppc:", CPU_TYPE_POWERPC) + .StartsWith("ppc64:", CPU_TYPE_POWERPC64) + .Default(CPU_TYPE_ANY); + + if (cpuType != CPU_TYPE_ANY && cpuType != target->cpuType) + continue; + + // Drop the CPU type as well as the colon + if (cpuType != CPU_TYPE_ANY) + line = line.drop_until([](char c) { return c == ':'; }).drop_front(); + + constexpr std::array fileEnds = {".o:", ".o):"}; + for (StringRef fileEnd : fileEnds) { + size_t pos = line.find(fileEnd); + if (pos != StringRef::npos) { + // Split the string around the colon + objectFile = line.take_front(pos + fileEnd.size() - 1); + line = line.drop_front(pos + fileEnd.size()); + break; + } + } + symbol = line.trim(); + + if (!symbol.empty()) { + SymbolPriorityEntry &entry = config->priorities[symbol]; + if (!objectFile.empty()) + entry.objectFiles.insert(std::make_pair(objectFile, priority)); + else + entry.anyObjectFile = std::max(entry.anyObjectFile, priority); + } + + --priority; + } + kLowestPriority = priority; +} + // Sort sections by the profile data provided by __LLVM,__cg_profile sections. // // This first builds a call graph based on the profile data then merges sections // according to the C³ heuristic. All clusters are then sorted by a density // metric to further improve locality. -DenseMap macho::computeCallGraphProfileOrder() { +static DenseMap computeCallGraphProfileOrder() { TimeTraceScope timeScope("Call graph profile sort"); return CallGraphSort().run(); } + +DenseMap macho::buildInputSectionPriorities() { + DenseMap sectionPriorities; + if (config->callGraphProfileSort) + sectionPriorities = computeCallGraphProfileOrder(); + + if (config->priorities.empty()) + return sectionPriorities; + + auto addSym = [&](Defined &sym) { + Optional symbolPriority = getSymbolPriority(sym); + if (!symbolPriority.hasValue()) + return; + size_t &priority = sectionPriorities[sym.isec]; + priority = std::max(priority, symbolPriority.getValue()); + }; + + // TODO: Make sure this handles weak symbols correctly. + for (const InputFile *file : inputFiles) { + if (isa(file)) + for (Symbol *sym : file->symbols) + if (auto *d = dyn_cast_or_null(sym)) + addSym(*d); + } + + return sectionPriorities; +} Index: lld/MachO/Writer.cpp =================================================================== --- lld/MachO/Writer.cpp +++ lld/MachO/Writer.cpp @@ -7,7 +7,6 @@ //===----------------------------------------------------------------------===// #include "Writer.h" -#include "CallGraphSort.h" #include "ConcatOutputSection.h" #include "Config.h" #include "InputFiles.h" @@ -15,6 +14,7 @@ #include "MapFile.h" #include "OutputSection.h" #include "OutputSegment.h" +#include "SectionPriorities.h" #include "SymbolTable.h" #include "Symbols.h" #include "SyntheticSections.h" @@ -850,54 +850,6 @@ : 0)); } -static size_t getSymbolPriority(const SymbolPriorityEntry &entry, - const InputFile *f) { - // We don't use toString(InputFile *) here because it returns the full path - // for object files, and we only want the basename. - StringRef filename; - if (f->archiveName.empty()) - filename = path::filename(f->getName()); - else - filename = saver.save(path::filename(f->archiveName) + "(" + - path::filename(f->getName()) + ")"); - return std::max(entry.objectFiles.lookup(filename), entry.anyObjectFile); -} - -// Each section gets assigned the priority of the highest-priority symbol it -// contains. -static DenseMap buildInputSectionPriorities() { - if (config->callGraphProfileSort) - return computeCallGraphProfileOrder(); - DenseMap sectionPriorities; - - if (config->priorities.empty()) - return sectionPriorities; - - auto addSym = [&](Defined &sym) { - if (sym.isAbsolute()) - return; - - auto it = config->priorities.find(sym.getName()); - if (it == config->priorities.end()) - return; - - SymbolPriorityEntry &entry = it->second; - size_t &priority = sectionPriorities[sym.isec]; - priority = - std::max(priority, getSymbolPriority(entry, sym.isec->getFile())); - }; - - // TODO: Make sure this handles weak symbols correctly. - for (const InputFile *file : inputFiles) { - if (isa(file)) - for (Symbol *sym : file->symbols) - if (auto *d = dyn_cast_or_null(sym)) - addSym(*d); - } - - return sectionPriorities; -} - // Sorting only can happen once all outputs have been collected. Here we sort // segments, output sections within each segment, and input sections within each // output segment. Index: lld/test/MachO/cgprofile-orderfile.s =================================================================== --- /dev/null +++ lld/test/MachO/cgprofile-orderfile.s @@ -0,0 +1,50 @@ +# REQUIRES: x86 + +# RUN: rm -rf %t; split-file %s %t +# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/test.s -o %t/test.o + +# RUN: %lld -e A %t/test.o -order_file %t/order_file -o %t/test +# RUN: llvm-nm --numeric-sort %t/test | FileCheck %s +# RUN: %lld -e A %t/test.o -o %t/test +# RUN: llvm-nm --numeric-sort %t/test | FileCheck %s --check-prefix NO-ORDER + + +#--- order_file +B +A + +#--- test.s + +.text + .globl D +D: + retq + + .globl C +C: + retq + + .globl B +B: + retq + + .globl A +A: + retq + +.cg_profile A, B, 100 +.cg_profile A, C, 40 +.cg_profile C, D, 61 + +.subsections_via_symbols + +# CHECK: T B +# CHECK-NEXT: T A +# CHECK-NEXT: T C +# CHECK-NEXT: T D + +# NO-ORDER: T A +# NO-ORDER-NEXT: T B +# NO-ORDER-NEXT: T C +# NO-ORDER-NEXT: T D + Index: llvm/utils/gn/secondary/lld/MachO/BUILD.gn =================================================================== --- llvm/utils/gn/secondary/lld/MachO/BUILD.gn +++ llvm/utils/gn/secondary/lld/MachO/BUILD.gn @@ -27,7 +27,6 @@ "Arch/ARM64Common.cpp", "Arch/ARM64_32.cpp", "Arch/X86_64.cpp", - "CallGraphSort.cpp", "ConcatOutputSection.cpp", "Driver.cpp", "DriverUtils.cpp", @@ -43,6 +42,7 @@ "OutputSection.cpp", "OutputSegment.cpp", "Relocations.cpp", + "SectionPriorities.cpp", "SymbolTable.cpp", "Symbols.cpp", "SyntheticSections.cpp",