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,11 +108,24 @@ 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; llvm::StringRef thinLTOCacheDir; llvm::StringRef thinLTOIndexOnlyArg; + llvm::StringRef ltoBBSections; std::pair thinLTOObjectSuffixReplace; std::pair thinLTOPrefixReplace; std::string rpath; @@ -165,6 +178,7 @@ bool ltoCSProfileGenerate; bool ltoDebugPassManager; bool ltoNewPassManager; + bool ltoUniqueBBSectionNames; bool mergeArmExidx; bool mipsN32Abi = false; bool mmapOutputFile; @@ -173,17 +187,25 @@ bool nostdlib; bool oFormatBinary; bool omagic; + bool optimizeBBJumps; bool optRemarksWithHotness; bool pacPlt; bool picThunk; 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; bool singleRoRx; bool shared; + bool shrinkJumpsAggressively; bool isStatic = false; bool sysvHash = false; bool target1Rel; 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" @@ -1893,6 +1894,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,97 @@ +//===- 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" + +namespace lld { + +using elf::config; + +namespace propeller { + +// Set up PropellerConfig from global lld config instnace. +static void setupConfig() { + propellerConfig.optPropeller = config->propeller; + propellerConfig.optLinkerOutputFile = config->outputFile; + +#define COPY_CONFIG(NAME) propellerConfig.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. + propellerConfig.optFallthroughWeight *= + propellerConfig.optForwardJumpDistance * + propellerConfig.optBackwardJumpDistance; + propellerConfig.optBackwardJumpWeight *= + propellerConfig.optForwardJumpDistance; + propellerConfig.optForwardJumpWeight *= + propellerConfig.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 propellerConfig; +} // namespace propeller +} // namespace lld 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 propellerConfig; + +} // 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 A, + uint64_t S, uint8_t T, bool BB = false, + SymbolEntry *FuncPtr = nullptr) + : Ordinal(O), Name(N), Aliases(As), Addr(A), 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 this->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