Index: lld/ELF/CMakeLists.txt =================================================================== --- lld/ELF/CMakeLists.txt +++ lld/ELF/CMakeLists.txt @@ -32,6 +32,7 @@ InputFiles.cpp InputSection.cpp LTO.cpp + LinkerPropeller.cpp LinkerScript.cpp MapFile.cpp MarkLive.cpp Index: lld/ELF/Config.h =================================================================== --- lld/ELF/Config.h +++ lld/ELF/Config.h @@ -108,6 +108,18 @@ llvm::StringRef optRemarksPasses; llvm::StringRef optRemarksFormat; llvm::StringRef progName; + llvm::StringRef propeller; + llvm::StringRef propellerDumpSymbolOrder; + uint64_t propellerFallthroughWeight; + uint64_t propellerForwardJumpWeight; + uint64_t propellerBackwardJumpWeight; + uint64_t propellerClusterMergeSizeThreshold; + uint64_t propellerForwardJumpDistance; + uint64_t propellerBackwardJumpDistance; + uint64_t propellerChainSplitThreshold; + std::vector propellerDumpCfgs; + std::vector propellerDebugSymbols; + std::vector propellerOpts; llvm::StringRef printSymbolOrder; llvm::StringRef soName; llvm::StringRef sysroot; @@ -179,6 +191,12 @@ bool pie; bool printGcSections; bool printIcfSections; + bool propellerKeepNamedSymbols; + bool propellerPrintStats; + bool propellerReorderIP = false; + bool propellerReorderBlocks; + bool propellerReorderFuncs; + bool propellerSplitFuncs; bool relocatable; bool relrPackDynRelocs; bool saveTemps; Index: lld/ELF/Driver.cpp =================================================================== --- lld/ELF/Driver.cpp +++ lld/ELF/Driver.cpp @@ -27,6 +27,7 @@ #include "ICF.h" #include "InputFiles.h" #include "InputSection.h" +#include "LinkerPropeller.h" #include "LinkerScript.h" #include "MarkLive.h" #include "OutputSections.h" @@ -922,6 +923,77 @@ args.hasFlag(OPT_print_gc_sections, OPT_no_print_gc_sections, false); config->printSymbolOrder = args.getLastArgValue(OPT_print_symbol_order); + + config->propeller = args.getLastArgValue(OPT_propeller); + + config->propellerKeepNamedSymbols = + args.hasFlag(OPT_propeller_keep_named_symbols, + OPT_no_propeller_keep_named_symbols, false); + + config->propellerClusterMergeSizeThreshold = args::getInteger( + args, OPT_propeller_cluster_merge_size_threshold, 1 << 21); + + config->propellerDumpSymbolOrder = + args.getLastArgValue(OPT_propeller_dump_symbol_order); + + config->propellerPrintStats = args.hasFlag( + OPT_propeller_print_stats, OPT_no_propeller_print_stats, false); + + config->propellerDumpCfgs = args::getStrings(args, OPT_propeller_dump_cfg); + + config->propellerDebugSymbols = + args::getStrings(args, OPT_propeller_debug_symbol); + + config->propellerReorderBlocks = config->propellerReorderFuncs = + config->propellerSplitFuncs = !config->propeller.empty(); + + config->propellerFallthroughWeight = + args::getInteger(args, OPT_propeller_fallthrough_weight, 10); + config->propellerForwardJumpWeight = + args::getInteger(args, OPT_propeller_forward_jump_weight, 1); + config->propellerBackwardJumpWeight = + args::getInteger(args, OPT_propeller_backward_jump_weight, 1); + + config->propellerForwardJumpDistance = + args::getInteger(args, OPT_propeller_forward_jump_distance, 1024); + config->propellerBackwardJumpDistance = + args::getInteger(args, OPT_propeller_backward_jump_distance, 640); + config->propellerChainSplitThreshold = + args::getInteger(args, OPT_propeller_chain_split_threshold, 1024); + + // Parse Propeller flags. + auto propellerOpts = args::getStrings(args, OPT_propeller_opt); + bool splitFuncsExplicit = false; + for (auto &propellerOpt : propellerOpts) { + if (propellerOpt == "reorder-ip") { + config->propellerReorderIP = true; + } else if (propellerOpt == "reorder-funcs") { + config->propellerReorderFuncs = true; + } else if (propellerOpt == "no-reorder-funcs") { + config->propellerReorderFuncs = false; + } else if (propellerOpt == "reorder-blocks") { + config->propellerReorderBlocks = true; + } else if (propellerOpt == "no-reorder-blocks") { + config->propellerReorderBlocks = false; + } else if (propellerOpt == "split-funcs") { + config->propellerSplitFuncs = true; + splitFuncsExplicit = true; + } else if (propellerOpt == "no-split-funcs") { + config->propellerSplitFuncs = false; + } else + error("unknown propeller option: " + propellerOpt); + } + + if (!config->propeller.empty() && !config->propellerReorderBlocks) { + if (splitFuncsExplicit) { + error("propeller: Inconsistent combination of propeller optimizations" + " 'split-funcs' and 'no-reorder-blocks'."); + } else { + warn("propeller: no-reorder-blocks implicitly sets no-split-funcs."); + config->propellerSplitFuncs = false; + } + } + config->rpath = getRpath(args); config->relocatable = args.hasArg(OPT_relocatable); config->saveTemps = args.hasArg(OPT_save_temps); @@ -1893,6 +1965,8 @@ for (InputSectionBase *s : f->getSections()) inputSections.push_back(cast(s)); + lld::propeller::doPropeller(); + llvm::erase_if(inputSections, [](InputSectionBase *s) { if (s->type == SHT_LLVM_SYMPART) { readSymbolPartitionSection(s); Index: lld/ELF/LinkerPropeller.h =================================================================== --- /dev/null +++ lld/ELF/LinkerPropeller.h @@ -0,0 +1,33 @@ +//===- LinkerPropeller.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 +// +//===----------------------------------------------------------------------===// +// +// This is the interface between LLD/ELF and Propeller. All interactions +// between LLD/ELF and propeller must be defined here. +// +// All dependencies on lld/ELF/*.h must happen in this file and +// LinkerPropeller.cpp. +// +//===----------------------------------------------------------------------===// + +#ifndef LLD_ELF_LINKER_PROPELLER_H +#define LLD_ELF_LINKER_PROPELLER_H + +#include "llvm/ADT/StringRef.h" + +namespace lld { +namespace propeller { +// Propeller interface to lld. +void doPropeller(); + +// Returns true if this is a BB symbol and shall be kept in the final binary's +// strtab. +bool isBBSymbolAndKeepIt(llvm::StringRef N); +} // namespace propeller +} // namespace lld + +#endif Index: lld/ELF/LinkerPropeller.cpp =================================================================== --- /dev/null +++ lld/ELF/LinkerPropeller.cpp @@ -0,0 +1,95 @@ +//===- LinkerPropeller.cpp ------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// This is the implementation of interface between LLD/ELF and Propeller. +// +// Current implementation first copies propeller parameters from +// lld::elf::Config instances into PropellerConfig. Then it transforms the +// vector into vector. +// +// "doPropeller" then passes PropellerConfig and vector to Propeller +// instance, and finally, after Propeller is done with its work, doPropeller +// passes the resulting symboll ordering back to lld. +// +// In summary, the dependencies of Propeller are: +// - a set of "lld::elf::InputFile"s. +// - command line arguments in lld::elf::Config +// - lld's being able to arrange section orders according to a vector of +// symbol names. +// +// All lld/ELF/Propeller/* only uses headers from lld/include, and llvm/include. +// +//===----------------------------------------------------------------------===// + +#include "LinkerPropeller.h" + +#include "Config.h" +#include "Propeller/PropellerConfig.h" +#include "lld/Common/PropellerCommon.h" + +namespace lld { + +using elf::config; + +namespace propeller { + +// Set up PropellerConfig from global lld config instnace. +static void setupConfig() { + propConfig.optPropeller = config->propeller; + propConfig.optLinkerOutputFile = config->outputFile; + +#define COPY_CONFIG(NAME) propConfig.opt##NAME = config->propeller##NAME + COPY_CONFIG(BackwardJumpDistance); + COPY_CONFIG(BackwardJumpWeight); + COPY_CONFIG(ChainSplitThreshold); + COPY_CONFIG(ClusterMergeSizeThreshold); + COPY_CONFIG(DebugSymbols); + COPY_CONFIG(DumpCfgs); + COPY_CONFIG(DumpSymbolOrder); + COPY_CONFIG(FallthroughWeight); + COPY_CONFIG(ForwardJumpDistance); + COPY_CONFIG(ForwardJumpWeight); + COPY_CONFIG(KeepNamedSymbols); + COPY_CONFIG(Opts); + COPY_CONFIG(PrintStats); + COPY_CONFIG(ReorderBlocks); + COPY_CONFIG(ReorderFuncs); + COPY_CONFIG(ReorderIP); + COPY_CONFIG(SplitFuncs); +#undef COPY_CONFIG + + // Scale weights for use in the computation of ExtTSP score. + propConfig.optFallthroughWeight *= + propConfig.optForwardJumpDistance * propConfig.optBackwardJumpDistance; + propConfig.optBackwardJumpWeight *= propConfig.optForwardJumpDistance; + propConfig.optForwardJumpWeight *= propConfig.optBackwardJumpDistance; +} + +// Propeller framework entrance. +void doPropeller() { + if (config->propeller.empty()) + return; + + setupConfig(); + + // Propeller work starts here. In next CL. + + // prop = make(); + // ... + // ... + // ... +} + +bool isBBSymbolAndKeepIt(llvm::StringRef name) { + // Real work done in next CL. + return false; +} + +PropellerConfig propConfig; +} // namespace propeller +} // namespace lld Index: lld/ELF/Options.td =================================================================== --- lld/ELF/Options.td +++ lld/ELF/Options.td @@ -296,6 +296,51 @@ defm print_symbol_order: Eq<"print-symbol-order", "Print a symbol order specified by --call-graph-ordering-file into the specified file">; +defm propeller: Eq<"propeller", "Propeller profile">; + +defm propeller_opt: Eq<"propeller-opt", + "Propeller optimization flags: reorder-blocks, reorder-funcs, and split-funcs is on by the default when -propeller is specified.">, + MetaVarName<"[reorder-ip, no-reorder-ip, reorder-blocks, no-reorder-blocks, reorder-funcs, no-reorder-funcs, split-funcs, no-split-funcs]">; + +defm propeller_keep_named_symbols: B<"propeller-keep-named-symbols", + "Do not delete basic block section symbols", + "Delete unused basic block section symbols (default)">; + +defm propeller_print_stats: B<"propeller-print-stats", + "Print propeller statistics.", + "Do not print propeller statistics (default)">; + +defm propeller_cluster_merge_size_threshold: Eq<"propeller-cluster-merge-size-threshold", + "Maximum size of a cluster which could be merged with other clusters (default: 2M).">; + +defm propeller_dump_symbol_order: Eq<"propeller-dump-symbol-order", + "Dump the propeller-generated symbol ordering into the file.">, + MetaVarName<"">; + +defm propeller_dump_cfg: Eq<"propeller-dump-cfg", + "Dump the cfg of the function in DOT format (in a file named the same as the function).">; + +defm propeller_debug_symbol: Eq<"propeller-debug-symbol", + "Print information about propeller actions related to the given symbol.">; + +defm propeller_fallthrough_weight: Eq<"propeller-fallthrough-weight", + "Fallthrough weight parameter to use in ExtTSP algorithm (default: 10).">; + +defm propeller_forward_jump_weight: Eq<"propeller-forward-jump-weight", + "(Near) forward jump weight parameter to use in ExtTSP algorithm (default: 1).">; + +defm propeller_backward_jump_weight: Eq<"propeller-backward-jump-weight", + "(Near) backward jump weight parameter to use in ExtTSP algorithm (default: 1).">; + +defm propeller_forward_jump_distance: Eq<"propeller-forward-jump-distance", + "Maximum distance for a forward jump in ExtTSP algorithm (default: 1024).">; + +defm propeller_backward_jump_distance: Eq<"propeller-backward-jump-distance", + "Maximum distance for a backward jump in ExtTSP algorithm (default: 640).">; + +defm propeller_chain_split_threshold: Eq<"propeller-chain-split-threshold", + "Maximum binary size of a chain which could be split in ExtTSP algorithm (default: 1024).">; + def pop_state: F<"pop-state">, HelpText<"Undo the effect of -push-state">; Index: lld/ELF/Propeller/PropellerConfig.h =================================================================== --- /dev/null +++ lld/ELF/Propeller/PropellerConfig.h @@ -0,0 +1,42 @@ +//===-------------------- PropellerConfig.h -------------------------------===// +// + +#ifndef LLD_ELF_PROPELLER_CONFIG_H +#define LLD_ELF_PROPELLER_CONFIG_H + +#include "llvm/ADT/StringRef.h" + +#include +#include + +namespace lld { +namespace propeller { + +struct PropellerConfig { + uint64_t optBackwardJumpDistance; + uint64_t optBackwardJumpWeight; + uint64_t optChainSplitThreshold; + std::vector optDebugSymbols; + std::vector optDumpCfgs; + uint64_t optClusterMergeSizeThreshold; + StringRef optDumpSymbolOrder; + uint64_t optFallthroughWeight; + uint64_t optForwardJumpDistance; + uint64_t optForwardJumpWeight; + bool optKeepNamedSymbols; + StringRef optLinkerOutputFile; + std::vector optOpts; + bool optPrintStats; + StringRef optPropeller; + bool optReorderBlocks; + bool optReorderFuncs; + bool optSplitFuncs; + bool optReorderIP; +}; + +extern PropellerConfig propConfig; + +} // namespace propeller +} // namespace lld + +#endif Index: lld/include/lld/Common/PropellerCommon.h =================================================================== --- /dev/null +++ lld/include/lld/Common/PropellerCommon.h @@ -0,0 +1,133 @@ +#ifndef LLD_ELF_PROPELLER_COMMON_H +#define LLD_ELF_PROPELLER_COMMON_H + +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Object/ObjectFile.h" + +#include + +using llvm::SmallVector; +using llvm::StringRef; + +namespace lld { +namespace propeller { + +static const char BASIC_BLOCK_SEPARATOR[] = ".BB."; +static const char BASIC_BLOCK_UNIFIED_CHARACTERS[] = "arlL"; + +// This data structure is shared between lld propeller components and +// create_llvm_prof. In short, create_llvm_prof parses the binary, wraps all the +// symbol information using SymbolEntry class, whereas in Propeller, PropFile +// class parses the propeller profile (which is generated by create_llvm_prof), +// and wraps the symbol information in SymbolEntry. In other words, SymbolEntry +// is the interface shared between create_llvm_prof and Propeller. +// [create_llvm_prof refer to: +// https://github.com/shenhanc78/autofdo/tree/plo-dev] +struct SymbolEntry { + enum BBTagTypeEnum : unsigned char { + BB_NONE = 0, // For functions. + BB_NORMAL, // Ordinary BB, 'a'. + BB_RETURN, // Return BB, 'r'. + BB_LANDING_PAD, // Landing pad BB, 'l'. + BB_RETURN_AND_LANDING_PAD // Landing pad and return BB, 'L'. + }; + + using AliasesTy = SmallVector; + + SymbolEntry(uint64_t o, const StringRef &n, AliasesTy &&as, uint64_t address, + uint64_t s, uint8_t t, bool bb = false, + SymbolEntry *funcptr = nullptr) + : ordinal(o), name(n), aliases(as), addr(address), size(s), type(t), + bbTag(bb), bbTagType(BB_NONE), hotTag(false), containingFunc(funcptr) {} + + // Unique index number across all symbols that participate linking. + uint64_t ordinal; + // For a function symbol, it's the full name. For a bb symbol this is only the + // bbIndex part, which is the number of "a"s before the ".bb." part. For + // example "8", "10", etc. Refer to Propfile::createFunctionSymbol and + // Propfile::createBasicBlockSymbol. + StringRef name; + // Only valid for function (bbTag == false) symbols. And aliases[0] always + // equals to name. For example, SymbolEntry.name = "foo", SymbolEntry.aliases + // = {"foo", "foo2", "foo3"}. + AliasesTy aliases; + uint64_t addr; + uint64_t size; + uint8_t type; // Of type: llvm::objet::SymbolRef::type. + bool bbTag; // Whether this is a basic block section symbol. + BBTagTypeEnum bbTagType; + + bool hotTag; // Whether this symbol is listed in the propeller section. + // For bbTag symbols, this is the containing fuction pointer, for a normal + // function symbol, this points to itself. This is neverl nullptr. + SymbolEntry *containingFunc; + + bool isReturnBlock() const { + return bbTagType == BB_RETURN || bbTagType == BB_RETURN_AND_LANDING_PAD; + } + + bool isLandingPadBlock() const { + return bbTagType == BB_LANDING_PAD || + bbTagType == BB_RETURN_AND_LANDING_PAD; + } + + bool operator<(const SymbolEntry &other) const { + return ordinal < other.ordinal; + } + + bool isFunction() const { + return type == llvm::object::SymbolRef::ST_Function; + } + + // Return true if "symName" is a BB symbol, e.g., in the form of + // "a.BB.funcname", and set funcName to the part after ".BB.", bbIndex to + // before ".BB.", if the pointers are nonnull. + static bool isBBSymbol(const StringRef &symName, + StringRef *funcName = nullptr, + StringRef *bbIndex = nullptr) { + if (symName.empty()) + return false; + auto r = symName.split(BASIC_BLOCK_SEPARATOR); + if (r.second.empty()) + return false; + for (auto *i = r.first.bytes_begin(), *j = r.first.bytes_end(); i != j; ++i) + if (strchr(BASIC_BLOCK_UNIFIED_CHARACTERS, *i) == NULL) + return false; + if (funcName) + *funcName = r.second; + if (bbIndex) + *bbIndex = r.first; + return true; + } + + static BBTagTypeEnum toBBTagType(const char c) { + switch (c) { + case 'a': + return BB_NORMAL; + case 'r': + return BB_RETURN; + case 'l': + return BB_LANDING_PAD; + case 'L': + return BB_RETURN_AND_LANDING_PAD; + default: + assert(false); + } + return BB_NONE; + } + + static const uint64_t INVALID_ADDRESS = uint64_t(-1); +}; + +struct SymbolEntryOrdinalLessComparator { + bool operator()(SymbolEntry *s1, SymbolEntry *s2) const { + if (s1 && s2) + return s1->ordinal < s2->ordinal; + return !!s1 < !!s2; + } +}; + +} // namespace propeller +} // namespace lld +#endif