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 @@ -62,9 +63,12 @@ LINK_LIBS lldCommon + lldPropeller ${LLVM_PTHREAD_LIB} - + DEPENDS ELFOptionsTableGen ${tablegen_deps} ) + +add_subdirectory(Propeller) Index: lld/ELF/LinkerPropeller.h =================================================================== --- /dev/null +++ lld/ELF/LinkerPropeller.h @@ -0,0 +1,27 @@ +//===- 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 + +namespace lld { +namespace propeller { +// Propeller interface to lld. +void doPropeller(); +} // namespace propeller +} // namespace lld + +#endif Index: lld/ELF/LinkerPropeller.cpp =================================================================== --- /dev/null +++ lld/ELF/LinkerPropeller.cpp @@ -0,0 +1,106 @@ +//===- 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 "InputFiles.h" +#include "Propeller/Propeller.h" +#include "Propeller/PropellerCFG.h" +#include "Propeller/PropellerConfig.h" +#include "lld/Common/Memory.h" + +#include "lld/Common/ErrorHandler.h" + +#include +#include + +namespace lld { + +using elf::config; +using elf::InputFile; +using elf::objectFiles; + +namespace propeller { + +Propeller *prop; + +// 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(BBOrder); + COPY_CONFIG(ChainSplitThreshold); + COPY_CONFIG(DebugSymbols); + COPY_CONFIG(DumpCfgs); + COPY_CONFIG(DumpSymbolOrder); + COPY_CONFIG(FallthroughWeight); + COPY_CONFIG(ForwardJumpDistance); + COPY_CONFIG(ForwardJumpWeight); + COPY_CONFIG(Opts); + COPY_CONFIG(PrintStats); + COPY_CONFIG(ReorderBlocks); + COPY_CONFIG(ReorderFuncs); + COPY_CONFIG(SplitFuncs); + COPY_CONFIG(ReorderIP); +#undef COPY_CONFIG +} + +// Propeller framework entrance. +void doPropeller() { + if (config->propeller.empty()) + return; + + setupConfig(); + prop = make(); + + if (!prop->checkTarget()) { + warn("[Propeller]: Propeller skipped '" + config->outputFile + "'."); + return; + } + + std::vector objectViews; + std::for_each(objectFiles.begin(), objectFiles.end(), + [&objectViews](const InputFile *inf) { + auto *ov = Propeller::createObjectView( + inf->getName(), objectViews.size() + 1, inf->mb); + if (ov) + objectViews.push_back(ov); + }); + if (prop->processFiles(objectViews)) + config->symbolOrderingFile = prop->genSymbolOrderingFile(); + else + error("Propeller stage failed."); +} + +} // namespace propeller +} // namespace lld Index: lld/ELF/Propeller/CMakeLists.txt =================================================================== --- /dev/null +++ lld/ELF/Propeller/CMakeLists.txt @@ -0,0 +1,22 @@ +find_package(Protobuf) +if( Protobuf_FOUND ) + add_compile_definitions(PROPELLER_PROTOBUF GOOGLE_PROTOBUF_NO_RTTI) + include_directories( ${Protobuf_INCLUDE_DIRS} ) + protobuf_generate_cpp(PROPELLER_PROTO_SRCS PROPELLER_PROTO_HDRS propeller_cfg.proto) + set(PROPELLER_PROTOBUF_LIBS ${Protobuf_LIBRARIES}) +endif() + +add_lld_library(lldPropeller + Propeller.cpp + PropellerBBReordering.cpp + PropellerChainClustering.cpp + PropellerCFG.cpp + PropellerNodeChain.cpp + PropellerNodeChainAssembly.cpp + PropellerNodeChainBuilder.cpp + PropellerProtobuf.cpp + ${PROPELLER_PROTO_SRCS} + + LINK_LIBS + ${PROPELLER_PROTOBUF_LIBS} +) Index: lld/ELF/Propeller/Propeller.h =================================================================== --- /dev/null +++ lld/ELF/Propeller/Propeller.h @@ -0,0 +1,318 @@ +//===------------------------ Propeller.h ---------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// See README.md for propeller framework. +// +//========================================================================= +// +// Propeller.h defines Propeller framework classes: +// +// Propfile - parses and wraps propeller profile +// +// Propeller - the main propeller framework class +// +// Propeller starts by checking if "-o" file matches propeller profile +// (Propeller::checkPropellerTarget), then it enters +// Propeller::processFiles(), which builds control flow graph (CFG) +// for each valid ELF object file (Propeller::processFile -> +// CFGBuilder::buildCFGs). +// +// After control flow graphs are build, Propeller starts parsing +// Propeller profile (the Propfile class). In this step, basicblock +// (BB) symbols are created, branch/call counters are read, and *very +// importantly*, the counters are applied to the CFG. For example, +// upon seeing two consecutive branch records in the propeller +// profile: a->b, c->d, we not only increment edge counters for a->b, +// c->d, we also walks from b->c, and increment basicblock and edge +// counters in between. This last step can only be done after we have +// a complete CFG for the function. +// +// The CFG information is stored in Propeller::CFGMap. +// +// After we have CFGs with complete counters for edges/bbs, we pass the +// information to optimization passes. For now, depending on +// propellerReorderFuncs, propellerReorderBlocks or propellerSplitFuncs, +// propeller generates a list of basicblock symbol orders and feed it the origin +// linker phase. This step is done in Propeller::genSymbolOrderingFile. +// +//===----------------------------------------------------------------------===// + +#ifndef LLD_ELF_PROPELLER_H +#define LLD_ELF_PROPELLER_H + +#include "PropellerProtobuf.h" + +#include "lld/Common/ErrorHandler.h" +#include "lld/Common/LLVM.h" +#include "lld/Common/PropellerCommon.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Object/ObjectFile.h" +#include "llvm/Support/StringSaver.h" + +#include +#include +#include +#include +#include +#include +#include + +namespace lld { +namespace propeller { + +extern class Propeller *prop; + +class ControlFlowGraph; +class CFGEdge; +class CFGNode; +class ObjectView; +class Propeller; +class PropellerBBReordering; +struct PropellerConfig; + +// Propeller profile parser. +// +// A sample propeller profile is like below: +// +// Symbols +// 1 0 N.init/_init +// 2 0 N.plt +// ... +// ... +// 11 7c Nmain +// 12 f 11.1 +// 13 28 11.2 +// 14 b 11.3 +// 15 a 11.4 +// 16 65 N__libc_csu_init +// 17 2 N__libc_csu_fini +// 18 0 N.fini/_fini +// 19 5e N_ZN9assistantD2Ev/_ZN9assistantD1Ev +// Branches +// 10 12 232590 R +// 12 10 234842 C +// 12 14 143608 +// Fallthroughs +// 10 10 225131 +// !func1 +// !func2 +// +// The file consists of 4 parts, "Symbols", "Branches", "Fallthroughs" and +// Funclist. +// +// Each line in "Symbols" section contains the following field: +// index - in decimal, unique for each symbol, start from 1 +// size - in hex, without "0x" +// name - either starts with "N" or a digit. In the former case, +// everything after N is the symbol name. In the latter case, it's +// in the form of "a.b", "a" is a symbol index, "b" is the bb +// identification string (could be an index number). For the above +// example, name "11.2" means "main.bb.2", because "11" points to +// symbol main. Also note, symbols could have aliases, in such +// case, aliases are concatenated with the original name with a +// '/'. For example, symbol 19 contains 2 aliases. +// Note, the symbols listed are in strict non-decreasing address order. +// +// Each line in "Branches" section contains the following field: +// from - sym_index, in decimal +// to - sym_index, in decimal +// cnt - counter, in decimal +// C/R - a field indicate whether this is a function call or a return, +// could be empty if it's just a normal branch. +// +// Each line in "Fallthroughs" section contains exactly the same fields as in +// "Branches" section, except the "C" field. +// +// Funclist contains lines that starts with "!", and everything following that +// will be the function name that's to be consumed by compiler (for bb section +// generation purpose). +class Propfile { +public: + Propfile(const std::string &pName) + : PropfileStrSaver(BPAllocator), PropfName(pName), PropfStream(), + AllBBMode(false) {} + + // Check whether "outputFile" matches "@" directives in the propeller profile. + bool matchesOutputFileName(const StringRef outputFile); + + // Read "Symbols" sections in the propeller profile and create + // SymbolOrdinalMap and SymbolNameMap. + bool readSymbols(); + SymbolEntry *findSymbol(StringRef symName); + bool processProfile(); + + // For each function symbol line defintion, this function creates a + // SymbolEntry instance and places it in SymbolOrdinalMap and SymbolNameMap. + // Function symbol defintion line is like below. (See comments at the head of + // the file) + // 11 7c Nmain/alias1/alias2 + // ^^ ^^ ^^ + // Ordinal Size Name and aliases + SymbolEntry *createFunctionSymbol(uint64_t ordinal, const StringRef &name, + SymbolEntry::AliasesTy &&aliases, + uint64_t size) { + auto *sym = new SymbolEntry(ordinal, name, std::move(aliases), + SymbolEntry::INVALID_ADDRESS, size, + llvm::object::SymbolRef::ST_Function); + sym->BBTagType = SymbolEntry::BB_NONE; + SymbolOrdinalMap.emplace(std::piecewise_construct, + std::forward_as_tuple(ordinal), + std::forward_as_tuple(sym)); + for (auto &a : sym->Aliases) + SymbolNameMap[a][""] = sym; + + if (sym->Aliases.size() > 1) + FunctionsWithAliases.push_back(sym); + + // Function symbols is always hot. + sym->HotTag = true; + return sym; + } + + // For each bb symbol line defintion, this function creates a + // SymbolEntry instance and places it in SymbolOrdinalMap and SymbolNameMap. + // Function symbol defintion line is like below. (See comments at the head of + // the file) + // 12 f 11.1 + // ^^ ^ ^^^^ + // Ordinal Size func_ordinal.bb_index + SymbolEntry *createBasicBlockSymbol(uint64_t ordinal, SymbolEntry *function, + StringRef &bBIndex, uint64_t size, + bool HotTag) { + // bBIndex is of the form "1", "2", it's a stringref to integer. + assert(!function->BBTag && function->isFunction()); + auto *sym = + new SymbolEntry(ordinal, bBIndex, SymbolEntry::AliasesTy(), + SymbolEntry::INVALID_ADDRESS, size, + llvm::object::SymbolRef::ST_Unknown, true, function); + sym->HotTag = HotTag; + // Note, we do not have knowledge what BB type it is from propeller file, so + // we always use BB_NORMAL here. + sym->BBTagType = SymbolEntry::BB_NORMAL; + SymbolOrdinalMap.emplace(std::piecewise_construct, + std::forward_as_tuple(ordinal), + std::forward_as_tuple(sym)); + for (auto &a : function->Aliases) { + SymbolNameMap[a][bBIndex] = sym; + } + return sym; + } + + void reportParseError(StringRef msg) const; + + llvm::BumpPtrAllocator BPAllocator; + llvm::UniqueStringSaver PropfileStrSaver; + std::string PropfName; + std::ifstream PropfStream; + // Ordial -> SymbolEntry map. This also owns SymbolEntry instances. + std::map> SymbolOrdinalMap; + // SymbolNameMap is ordered in the following way: + // SymbolNameMap[foo][""] = functionSymbol; + // SymbolNameMap[foo]["1"] = fun.bb.1.Symbol; + // SymbolNameMap[foo]["2"] = fun.bb.2.Symbol; + // etc... + std::map> SymbolNameMap; + std::vector FunctionsWithAliases; + uint64_t LineNo; + char LineTag; + + std::map OrdinalRemapping; + + bool AllBBMode; +}; + +class Propeller { +public: + Propeller(); + ~Propeller(); + + // Returns true if linker output target matches propeller profile. + bool checkTarget(); + bool processFiles(std::vector &files); + void processFile(ObjectView *view); + CFGNode *findCfgNode(uint64_t symbolOrdinal); + void calculateNodeFreqs(); + std::vector genSymbolOrderingFile(); + void calculateLegacy(std::list &SymList, + std::list::iterator hotPlaceHolder, + std::list::iterator coldPlaceHolder); + template void forEachCfgRef(Visitor v) { + for (auto &p : CFGMap) + v(*(*(p.second.begin()))); + } + + bool dumpCfgs(); + + static ObjectView *createObjectView(const StringRef &vN, + const uint32_t ordinal, + const MemoryBufferRef &fR); + + std::vector> Views; + // Same named CFGs may exist in different object files (e.g. weak + // symbols.) We always choose symbols that appear earlier on the + // command line. Note: implementation is in the .cpp file, because + // ControlFlowGraph here is an incomplete type. + struct ObjectViewOrdinalComparator { + bool operator()(const ControlFlowGraph *a, const ControlFlowGraph *b) const; + }; + using CfgMapTy = + std::map>; + CfgMapTy CFGMap; + std::unique_ptr Propf; + uint32_t ProcessFailureCount; // Number of files that are not processed by + // Propeller. + // We call Propeller::processFile in parallel to create CFGs for + // each file, after the CFGs are created, each processFile thread + // then puts CFGs into Propeller::CFGMap (see above). Lock is used + // to guard this Propeller::CFGMap critical section. + std::mutex Lock; + + PropellerBBReordering *propLayout; + + llvm::StringMap> BBLayouts; + +#ifdef PROPELLER_PROTOBUF + std::unique_ptr protobufPrinter; +#endif +}; + +// When no "-propeller-keep-named-symbols" specified, we remove all BB symbols +// that are hot, and we keep only the first code BB symbol that starts the cold +// code region of the same function. See Below: +// Hot: +// foo +// foo.bb.1 <= delete +// foo.bb.2 <= delete +// bar +// bar.bb.1 <= delete +// bar.bb.3 <= delete +// Cold: +// foo.bb.3 +// foo.bb.4 <= delete +// foo.bb.5 <= delete +// bar.bb.2 +// bar.bb.4 <= delete +// bar.bb.5 <= delete +struct PropellerLegacy { + std::set BBSymbolsToKeep; + + bool shouldKeepBBSymbol(StringRef symName) { + if (!SymbolEntry::isBBSymbol(symName)) + return true; + return BBSymbolsToKeep.find(symName) != BBSymbolsToKeep.end(); + } +}; + +extern PropellerLegacy PropLeg; + +extern PropellerConfig propellerConfig; + +} // namespace propeller +} // namespace lld +#endif Index: lld/ELF/Propeller/Propeller.cpp =================================================================== --- /dev/null +++ lld/ELF/Propeller/Propeller.cpp @@ -0,0 +1,750 @@ +//===------------------------- Propeller.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 +// +//===----------------------------------------------------------------------===// +// +// Propeller.cpp is the entry point to Propeller framework. The main +// functionalities are: +// +// - parses propeller profile file, which contains profile information in the +// granularity of basicblocks. (a) +// +// - parses each ELF object file and generates CFG based on relocation +// information of each basicblock section. +// +// - maps profile in (a) onto (b) and get CFGs with profile counters (c) +// +// - calls optimization passes that uses (c). +// +//===----------------------------------------------------------------------===// + +#include "Propeller.h" +#include "PropellerBBReordering.h" +#include "PropellerCFG.h" +#include "PropellerConfig.h" + +#ifdef PROPELLER_PROTOBUF +#include "propeller_cfg.pb.h" +#endif +#include "lld/Common/ErrorHandler.h" +#include "lld/Common/Memory.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/Support/Format.h" +#include "llvm/Support/Parallel.h" +#include "llvm/Support/Path.h" +#include "llvm/Support/raw_ostream.h" + +#include +#include +#include +#if LLVM_ON_UNIX +#include +#endif + +#include +#include +#include +#include // For std::accumulate. +#include +#include + +namespace lld { +namespace propeller { + +Propeller::Propeller() : Propf(nullptr) {} + +Propeller::~Propeller() {} + +// Read the "@" directives in the propeller file, compare it against "-o" +// filename, return true "-o" file name equals to one of the "@" directives. +bool Propfile::matchesOutputFileName(const StringRef outputFileName) { + int outputFileTagSeen = 0; + std::string line; + LineNo = 0; + while ((std::getline(PropfStream, line)).good()) { + ++LineNo; + if (line.empty()) + continue; + if (line[0] != '@') + break; + ++outputFileTagSeen; + if (StringRef(line.c_str() + 1) == outputFileName) + return true; + } + if (outputFileTagSeen) + return false; + // If no @outputFileName is specified, reset the stream and assume linker + // shall proceed propellering. + PropfStream.close(); + PropfStream.open(PropfName); + LineNo = 0; + return true; +} + +// Given a symbol name, return the corresponding SymbolEntry pointer. +// This is done by looking into table SymbolNameMap, which is a 2-dimension +// lookup table. The first dimension is the function name, the second one the +// bbindex. For example, symbol "111.bb.foo" is placed in +// SymbolNameMap["foo"]["3"], symbol "foo" is placed in +// SymbolNameMap["foo"][""]. +SymbolEntry *Propfile::findSymbol(StringRef symName) { + StringRef funcName; + StringRef bbIndex; + std::string tmpStr; + if (!SymbolEntry::isBBSymbol(symName, &funcName, &bbIndex)) { + funcName = symName; + bbIndex = ""; + } else { + // When symName is like "11111.bb.foo", set BBIndex to "5". + // "1111" -> "4". + tmpStr = std::to_string(bbIndex.size()); + bbIndex = StringRef(tmpStr); + } + auto L1 = SymbolNameMap.find(funcName); + if (L1 != SymbolNameMap.end()) { + auto L2 = L1->second.find(bbIndex); + if (L2 != L1->second.end()) + return L2->second; + } + return nullptr; +} + +void Propfile::reportParseError(const StringRef msg) const { + error(PropfName + ":" + std::to_string(LineNo) + ": " + msg); +} + +// Refer header file for detailed information about symbols section. +bool Propfile::readSymbols() { + std::string line; + // A list of bbsymbols that + // appears before its wrapping function. This should be rather rare. + std::list> bbSymbols; + std::map> HotBBSymbols; + auto IsHotBB = [this, &HotBBSymbols](SymbolEntry *FuncSym, + StringRef BBIndex) -> bool { + std::string N(""); + for (auto A : FuncSym->Aliases) { + if (N.empty()) + N = A.str(); // Most of the times. + else + N += "/" + A.str(); + } + auto I0 = HotBBSymbols.find(N); + if (I0 == HotBBSymbols.end()) + return false; + // Under AllBBMode, all BBs within a hot function are hotbbs. + if (this->AllBBMode) + return true; + uint64_t index = std::stoull(BBIndex.str()); + return I0->second.find(index) != I0->second.end(); + }; + std::map>::iterator CurrentHotBBSetI = + HotBBSymbols.end(); + while (std::getline(PropfStream, line).good()) { + ++LineNo; + if (line.empty()) + continue; + if (line == "#AllBB") { + AllBBMode = true; + continue; + } + if (line[0] == '#' || line[0] == '@') + continue; + if (line[0] == '!' && line.size() > 1) { + if (AllBBMode) { + if (line[1] != '!' && + !HotBBSymbols.emplace(line.substr(1), std::set()) + .second) { + reportParseError("duplicated hot bb function field"); + return false; + } + continue; + } + // Now AllBBMode is false, we consider every function and every hot bbs. + if (line[1] == '!') { + uint64_t bbindex = std::stoull(line.substr(2)); + if (CurrentHotBBSetI == HotBBSymbols.end() || !bbindex) { + reportParseError("invalid hot bb index field"); + return false; + } + CurrentHotBBSetI->second.insert(bbindex); + } else { + auto RP = HotBBSymbols.emplace(line.substr(1), std::set()); + if (!RP.second) { + reportParseError("duplicated hot bb function field"); + return false; + } + CurrentHotBBSetI = RP.first; + } + continue; + } + if (line[0] == 'B' || line[0] == 'F') { + LineTag = line[0]; + break; // Done symbol section. + } + if (line[0] == 'S') { + LineTag = line[0]; + continue; + } + StringRef lineStrRef(line); + + uint64_t symOrdinal; + uint64_t symSize; + auto l1S = lineStrRef.split(' '); + auto l1 = l1S.first; + auto l2S = l1S.second.split(' '); + auto l2 = l2S.first; + auto ephemeralStr = l2S.second; + if (l1.getAsInteger(10, symOrdinal) /* means error happens */ || + symOrdinal == 0) { + reportParseError("invalid ordinal field"); + return false; + } + if (l2.getAsInteger(16, symSize)) { + reportParseError("invalid size field"); + return false; + } + if (ephemeralStr.empty()) { + reportParseError("invalid name field"); + return false; + } + if (ephemeralStr[0] == 'N') { // Function symbol? + // Save ephemeralStr for persistency across Propeller lifecycle. + StringRef savedNameStr = PropfileStrSaver.save(ephemeralStr.substr(1)); + SymbolEntry::AliasesTy sAliases; + savedNameStr.split(sAliases, '/'); + StringRef sName = sAliases[0]; + assert(SymbolOrdinalMap.find(symOrdinal) == SymbolOrdinalMap.end()); + createFunctionSymbol(symOrdinal, sName, std::move(sAliases), symSize); + } else { + // It's a bb symbol. + auto lineStrRef = ephemeralStr.split('.'); + uint64_t funcIndex; + if (lineStrRef.first.getAsInteger(10, funcIndex) || funcIndex == 0) { + reportParseError("invalid function index field"); + return false; + } + // Only save the index part, which is highly reusable. Note + // PropfileStrSaver is a UniqueStringSaver. + StringRef bbIndex = PropfileStrSaver.save(lineStrRef.second); + auto existingI = SymbolOrdinalMap.find(funcIndex); + if (existingI != SymbolOrdinalMap.end()) { + if (existingI->second->BBTag) { + reportParseError("index '" + std::to_string(funcIndex) + + "' is not a function index, but a bb index"); + return false; + } + createBasicBlockSymbol(symOrdinal, existingI->second.get(), bbIndex, + symSize, + IsHotBB(existingI->second.get(), bbIndex)); + } else + // A bb symbol appears earlier than its wrapping function, rare, but + // not impossible, rather play it safely. + bbSymbols.emplace_back(symOrdinal, funcIndex, bbIndex, symSize); + } + } // End of iterating all symbols. + + for (std::tuple &sym : bbSymbols) { + uint64_t symOrdinal; + uint64_t funcIndex; + uint64_t symSize; + StringRef bbIndex; + std::tie(symOrdinal, funcIndex, bbIndex, symSize) = sym; + auto existingI = SymbolOrdinalMap.find(funcIndex); + if (existingI == SymbolOrdinalMap.end()) { + reportParseError("function with index number '" + + std::to_string(funcIndex) + "' does not exist"); + return false; + } + SymbolEntry *FuncSym = existingI->second.get(); + createBasicBlockSymbol(symOrdinal, FuncSym, bbIndex, symSize, + IsHotBB(FuncSym, bbIndex)); + } + return true; +} + +// Helper method to parse a branch or fallthrough record like below +// 10 12 232590 R +static bool parseBranchOrFallthroughLine(StringRef lineRef, + uint64_t *fromNodeIdx, + uint64_t *toNodeIdx, uint64_t *count, + char *type) { + /* + auto getInt = [](const StringRef &S) -> uint64_t { + uint64_t r; + if (S.getAsInteger(10, r) // string contains more than numbers + || r == 0) + return 0; + return r; + }; + */ + auto s0 = lineRef.split(' '); + auto s1 = s0.second.split(' '); + auto s2 = s1.second.split(' '); + if (s0.first.getAsInteger(10, *fromNodeIdx) || + s1.first.getAsInteger(10, *toNodeIdx) || + s2.first.getAsInteger(10, *count)) + return false; + if (!*count) + return false; + if (!s2.second.empty()) { + if (s2.second == "C" || s2.second == "R") + *type = s2.second[0]; + else + return false; + if (!*fromNodeIdx || !*toNodeIdx) + return false; + } else + *type = '\0'; + return true; +} + +// Read propeller profile. Refer header file for detail about propeller profile. +bool Propfile::processProfile() { + std::string line; + uint64_t branchCnt = 0; + uint64_t fallthroughCnt = 0; + while (std::getline(PropfStream, line).good()) { + ++LineNo; + if (line[0] == '#' || line[0] == '!') + continue; + if (line[0] == 'S' || line[0] == 'B' || line[0] == 'F') { + LineTag = line[0]; + continue; + } + if (LineTag != 'B' && LineTag != 'F') + break; + + StringRef L(line); // LineBuf is null-terminated. + uint64_t from, to, count; + char tag; + auto UpdateOrdinal = [this](uint64_t OriginOrdinal) -> uint64_t { + auto I = OrdinalRemapping.find(OriginOrdinal); + if (I != OrdinalRemapping.end()) { + // fprintf(stderr, "Updated %lu->%lu\n", OriginOrdinal, I->second); + return I->second; + } + return OriginOrdinal; + }; + if (!parseBranchOrFallthroughLine(L, &from, &to, &count, &tag)) { + reportParseError("unrecognized line:\n" + L.str()); + return false; + } + from = UpdateOrdinal(from); + to = UpdateOrdinal(to); + CFGNode *fromN = prop->findCfgNode(from); + CFGNode *toN = prop->findCfgNode(to); + if (!fromN || !toN) + continue; + + if (LineTag == 'B') { + if (!fromN || !toN) + continue; + ++branchCnt; + if (fromN->CFG == toN->CFG) + fromN->CFG->mapBranch(fromN, toN, count, tag == 'C', tag == 'R'); + else + fromN->CFG->mapCallOut(fromN, toN, 0, count, tag == 'C', tag == 'R'); + } else { + if (fromN && toN && (fromN->CFG != toN->CFG)) + continue; + ++fallthroughCnt; + // LineTag == 'F' + ControlFlowGraph *cfg = fromN ? fromN->CFG : toN->CFG; + cfg->markPath(fromN, toN, count); + } + } + + if (!branchCnt) + warn("propeller processed 0 branch info"); + if (!fallthroughCnt) + warn("propeller processed 0 fallthrough info"); + return true; +} + +// Parse each ELF file, create CFG and attach profile data to CFG. +void Propeller::processFile(ObjectView *view) { + if (view) { + std::map OrdinalRemapping; + if (CFGBuilder(view).buildCFGs(OrdinalRemapping)) { + // Updating global data structure. + std::lock_guard lock(Lock); + Views.emplace_back(view); + for (std::pair> &P : + view->CFGs) { + auto result = CFGMap[P.first].emplace(P.second.get()); + (void)(result); + assert(result.second); + } + Propf->OrdinalRemapping.insert(OrdinalRemapping.begin(), + OrdinalRemapping.end()); + + } else { + warn("skipped building CFG for '" + view->ViewName + "'"); + ++ProcessFailureCount; + } + } +} + +CFGNode *Propeller::findCfgNode(uint64_t symbolOrdinal) { + if (symbolOrdinal == 0) + return nullptr; + assert(Propf->SymbolOrdinalMap.find(symbolOrdinal) != + Propf->SymbolOrdinalMap.end()); + SymbolEntry *symbol = Propf->SymbolOrdinalMap[symbolOrdinal].get(); + if (!symbol) { + // This is an internal error, should not happen. + error(std::string("invalid symbol ordinal: " + + std::to_string(symbolOrdinal))); + return nullptr; + } + SymbolEntry *funcSym = symbol->BBTag ? symbol->ContainingFunc : symbol; + for (auto &funcAliasName : funcSym->Aliases) { + auto cfgLI = CFGMap.find(funcAliasName); + if (cfgLI == CFGMap.end()) + continue; + + // Objects (CfgLI->second) are sorted in the way they appear on the command + // line, which is the same as how linker chooses the weak symbol definition. + if (!symbol->BBTag) { + for (auto *CFG : cfgLI->second) + // Check CFG does have name "SymName". + for (auto &node : CFG->Nodes) + if (node->ShName == funcAliasName) + return node.get(); + } else { + uint32_t NumOnes; + // Compare the number of "a" in aaa...a.BB.funcname against integer + // NumOnes. + if (symbol->Name.getAsInteger(10, NumOnes) || !NumOnes) + warn("internal error, BB name is invalid: '" + symbol->Name.str()); + else + for (auto *CFG : cfgLI->second) + for (auto &node : CFG->Nodes) { + // Skip the entry node as we know this is a BB symbol. + if (node->isEntryNode()) + continue; + // Check CFG does have name "SymName". + auto t = node->ShName.find_first_of('.'); + if (t != std::string::npos && t == NumOnes) + return node.get(); + } + } + } + return nullptr; +} + +void Propeller::calculateNodeFreqs() { + auto sumEdgeWeights = [](std::vector &edges) -> uint64_t { + return std::accumulate( + edges.begin(), edges.end(), 0, + [](uint64_t pSum, const CFGEdge *edge) { return pSum + edge->Weight; }); + }; + auto ZeroOutEdgeWeights = [](std::vector &Es) { + for (auto *E : Es) + E->Weight = 0; + }; + + for (auto &cfgP : CFGMap) { + auto &cfg = *cfgP.second.begin(); + if (cfg->Nodes.empty()) + continue; + cfg->forEachNodeRef([&cfg, &sumEdgeWeights, + &ZeroOutEdgeWeights](CFGNode &node) { + uint64_t maxCallOut = + node.CallOuts.empty() + ? 0 + : (*std::max_element(node.CallOuts.begin(), node.CallOuts.end(), + [](const CFGEdge *E1, const CFGEdge *E2) { + return E1->Weight < E2->Weight; + })) + ->Weight; + if (node.HotTag) + node.Freq = + std::max({sumEdgeWeights(node.Outs), sumEdgeWeights(node.Ins), + sumEdgeWeights(node.CallIns), maxCallOut}); + else { + node.Freq = 0; + ZeroOutEdgeWeights(node.Ins); + ZeroOutEdgeWeights(node.Outs); + ZeroOutEdgeWeights(node.CallIns); + ZeroOutEdgeWeights(node.CallOuts); + } + + cfg->Hot |= (node.Freq != 0); + + // Find non-zero frequency nodes with fallthroughs and propagate the + // weight via the fallthrough edge if no other normal edge carries weight. + if (node.Freq && node.FTEdge && node.FTEdge->Sink->HotTag) { + uint64_t sumIntraOut = 0; + for (auto *e : node.Outs) { + if (e->Type == CFGEdge::EdgeType::INTRA_FUNC) + sumIntraOut += e->Weight; + } + + if (!sumIntraOut) + node.FTEdge->Weight = node.Freq; + } + }); + + /* + if (cfg->Hot && cfg->getEntryNode()->Freq == 0) + cfg->getEntryNode()->Freq = 1; + */ + } +} + +// Returns true if linker output target matches propeller profile. +bool Propeller::checkTarget() { + if (propellerConfig.optPropeller.empty()) + return false; + std::string propellerFileName = propellerConfig.optPropeller.str(); + // Propfile takes ownership of FPtr. + Propf.reset(new Propfile(propellerFileName)); + Propf->PropfStream.open(Propf->PropfName); + if (!Propf->PropfStream.good()) { + error(std::string("failed to open '") + propellerFileName + "'"); + return false; + } + return Propf->matchesOutputFileName( + llvm::sys::path::filename(propellerConfig.optLinkerOutputFile)); +} + +// Entrance of Propeller framework. This processes each elf input file in +// parallel and stores the result information. +bool Propeller::processFiles(std::vector &views) { + if (!Propf->readSymbols()) { + error(std::string("invalid propfile: '") + + propellerConfig.optPropeller.str() + "'"); + return false; + } + + if (!propellerConfig.optBBOrder.empty()) { + for (StringRef s : propellerConfig.optBBOrder) { + auto r = s.split('.'); + std::string bbIndex = r.first.str() == "0" ? "" : r.first; + std::string funcName = r.second; + bool found = false; + auto l1 = prop->Propf->SymbolNameMap.find(funcName); + if (l1 != prop->Propf->SymbolNameMap.end()) { + auto l2 = l1->second.find(bbIndex); + if (l2 != l1->second.end()) { + BBLayouts[funcName].push_back(l2->second->Ordinal); + found = true; + } + } + if (!found) + warn("Symbol not found: " + s); + } + } + + ProcessFailureCount = 0; + llvm::parallel::for_each( + llvm::parallel::parallel_execution_policy(), views.begin(), views.end(), + std::bind(&Propeller::processFile, this, std::placeholders::_1)); + + if (ProcessFailureCount * 100 / views.size() >= 50) + warn("propeller failed to parse more than half the objects, " + "optimization would suffer"); + + /* Drop alias cfgs. */ + for (SymbolEntry *funcS : Propf->FunctionsWithAliases) { + ControlFlowGraph *primaryCfg = nullptr; + CfgMapTy::iterator primaryCfgMapEntry; + for (StringRef &AliasName : funcS->Aliases) { + auto cfgMapI = CFGMap.find(AliasName); + if (cfgMapI == CFGMap.end()) + continue; + + if (cfgMapI->second.empty()) + continue; + + if (!primaryCfg || + primaryCfg->Nodes.size() < (*cfgMapI->second.begin())->Nodes.size()) { + if (primaryCfg) + CFGMap.erase(primaryCfgMapEntry); + + primaryCfg = *cfgMapI->second.begin(); + primaryCfgMapEntry = cfgMapI; + } else + CFGMap.erase(cfgMapI); + } + } + + // Map profiles. + if (!Propf->processProfile()) + return false; + + calculateNodeFreqs(); + + dumpCfgs(); + + // Releasing all support data (symbol ordinal / name map, saved string refs, + // etc) before moving to reordering. + Propf.reset(nullptr); + return true; +} + +bool Propeller::dumpCfgs() { + if (propellerConfig.optDumpCfgs.empty()) + return true; + + std::set cfgToDump(propellerConfig.optDumpCfgs.begin(), + propellerConfig.optDumpCfgs.end()); + llvm::SmallString<128> cfgOutputDir(propellerConfig.optLinkerOutputFile); + llvm::sys::path::remove_filename(cfgOutputDir); + for (auto &cfgName : cfgToDump) { + StringRef cfgNameRef(cfgName); + if (cfgName == "@" || cfgNameRef.startswith("@@")) { +#ifdef PROPELLER_PROTOBUF + if (!protobufPrinter.get()) + protobufPrinter.reset(ProtobufPrinter::create( + Twine(propellerConfig.optLinkerOutputFile, ".cfg.pb.txt").str())); + if (cfgNameRef.consume_front("@@")) { + protobufPrinter->clearCFGGroup(); + const bool cfgNameEmpty = cfgNameRef.empty(); + for (auto &cfgMapEntry : CFGMap) + for (auto *cfg : cfgMapEntry.second) + if (cfgNameEmpty || cfg->Name == cfgNameRef) + protobufPrinter->addCFG(*cfg); + protobufPrinter->printCFGGroup(); + protobufPrinter.reset(nullptr); + } +#else + warn("dump to protobuf not supported"); +#endif + continue; + } + auto cfgLI = CFGMap.find(cfgName); + if (cfgLI == CFGMap.end()) { + warn("could not dump cfg for function '" + cfgName + + "' : no such function name exists"); + continue; + } + int Index = 0; + for (auto *CFG : cfgLI->second) + if (CFG->Name == cfgName) { + llvm::SmallString<128> cfgOutput = cfgOutputDir; + if (++Index <= 1) + llvm::sys::path::append(cfgOutput, (CFG->Name + ".dot")); + else + llvm::sys::path::append( + cfgOutput, + (CFG->Name + "." + StringRef(std::to_string(Index) + ".dot"))); + if (!CFG->writeAsDotGraph(StringRef(cfgOutput))) + warn("failed to dump CFG: '" + cfgName + "'"); + } + } + return true; +} + +ObjectView *Propeller::createObjectView(const StringRef &vN, + const uint32_t ordinal, + const MemoryBufferRef &fR) { + const char *FH = fR.getBufferStart(); + if (fR.getBufferSize() > 6 && FH[0] == 0x7f && FH[1] == 'E' && FH[2] == 'L' && + FH[3] == 'F') { + auto r = ObjectFile::createELFObjectFile(fR); + if (r) + return new ObjectView(*r, vN, ordinal, fR); + } + return nullptr; +} + +// Generate symbol ordering file according to selected optimization pass and +// feed it to the linker. +std::vector Propeller::genSymbolOrderingFile() { + int total_objs = 0; + int hot_objs = 0; + for (auto &Obj : Views) { + for (auto &CP : Obj->CFGs) { + auto &C = *(CP.second); + if (C.isHot()) { + ++hot_objs; + break; // process to next object. + } + } + ++total_objs; + } + + std::list symbolList(1, "Hot"); + const auto hotPlaceHolder = symbolList.begin(); + const auto coldPlaceHolder = symbolList.end(); + propLayout = make(); + propLayout->doSplitOrder(symbolList, hotPlaceHolder, coldPlaceHolder); +#ifdef PROPELLER_PROTOBUF + if (protobufPrinter) { + protobufPrinter->printCFGGroup(); + protobufPrinter.reset(); + } +#endif + + calculateLegacy(symbolList, hotPlaceHolder, coldPlaceHolder); + + if (!propellerConfig.optDumpSymbolOrder.empty()) { + FILE *fp = fopen(propellerConfig.optDumpSymbolOrder.str().c_str(), "w"); + if (!fp) + warn(StringRef("dump symbol order: failed to open ") + "'" + + propellerConfig.optDumpSymbolOrder + "'"); + else { + for (auto &sym : symbolList) { + auto A = sym.split(".BB."); + if (A.second.empty()) { + fprintf(fp, "%s\n", sym.str().c_str()); + } else { + fprintf(fp, "%zu.BB.%s\n", A.first.size(), A.second.str().c_str()); + } + } + fclose(fp); + llvm::outs() << "Dumped symbol order file to: '" + << propellerConfig.optDumpSymbolOrder.str() << "'\n"; + } + } + + symbolList.erase(hotPlaceHolder); + + return std::vector( + std::move_iterator::iterator>(symbolList.begin()), + std::move_iterator::iterator>(symbolList.end())); +} + +// Calculate a std::list of basicblock symbols that are to be kept in the final +// binary. For hot bb symbols, all bb symbols are to be dropped, because the +// content of all hot bb sections are grouped together with the origin function. +// For cold bb symbols, only the first bb symbols of the same function are kept. +void Propeller::calculateLegacy( + std::list &symList, + std::list::iterator hotPlaceHolder, + std::list::iterator coldPlaceHolder) { + // No function split or no cold symbols, all bb symbols shall be removed. + if (hotPlaceHolder == coldPlaceHolder) + return; + // For cold bb symbols that are split and placed in cold segements, + // only the first bb symbol of every function partition is kept. + StringRef LastFuncName = ""; + for (auto i = std::next(hotPlaceHolder), j = coldPlaceHolder; i != j; ++i) { + StringRef sName = *i; + StringRef fName; + if (SymbolEntry::isBBSymbol(sName, &fName)) { + if (LastFuncName.empty() || LastFuncName != fName) + PropLeg.BBSymbolsToKeep.insert(sName); + LastFuncName = fName; + } + } + return; +} + +bool Propeller::ObjectViewOrdinalComparator::operator()( + const ControlFlowGraph *a, const ControlFlowGraph *b) const { + return a->View->Ordinal < b->View->Ordinal; +} + +PropellerLegacy PropLeg; + +PropellerConfig propellerConfig; + +} // namespace propeller +} // namespace lld Index: lld/ELF/Propeller/PropellerCFG.h =================================================================== --- /dev/null +++ lld/ELF/Propeller/PropellerCFG.h @@ -0,0 +1,294 @@ +//===-------------------- PropellerELFCfg.h -------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// Class definitions for propeller cfg, edge, nodes and CFGBuilder. +// +// The ObjectView class represents one ELF file. The CFGBuilder class builds +// cfg for each function and store it in ObjectView::CFGs, indexed by cfg name. +// +// CFGBuilder::buildCFGs works this way: +// - groups funcName, a.BB.funcName, aa.BB.funcName and alike into one set, +// for each set, passes the set to "CFGBuilder::buildCFG" +// - each element in the set is a section, we then know from its section +// relocations the connections to other sections. (a) +// - from (a), we build CFG. +// +// Three important functions in ControlFlowGraph: +// mapBranch - apply counter to edge A->B, where A, B belong to the same func +// +// mapCallOut - apply counter to edge A->B, where A, B belong to diff funcs +// +// markPath - apply counter to all nodes/edges betwee A and B, A and B belong +// to same func +//===----------------------------------------------------------------------===// + +#ifndef LLD_ELF_PROPELLER_CFG_H +#define LLD_ELF_PROPELLER_CFG_H + +#include "Propeller.h" +#include "PropellerConfig.h" + +#include "llvm/ADT/StringRef.h" +#include "llvm/Object/ObjectFile.h" + +#include +#include +#include +#include + +using llvm::object::ObjectFile; +using llvm::object::section_iterator; +using llvm::object::SymbolRef; + +namespace lld { +namespace propeller { + +class ObjectView; +class CFGNode; +class ControlFlowGraph; +class NodeChain; + +// All instances of CFGEdge are owned by their CFG. +class CFGEdge { +public: + CFGNode *Src; + CFGNode *Sink; + uint64_t Weight; + + // Whether it's an edge introduced by recursive-self-call. (Usually + // calls do not split basic blocks and do not introduce new edges.) + enum EdgeType : char { + INTRA_FUNC, + INTRA_RSC, // Recursive call. + INTRA_RSR, // Return from recursive call. + // Intra edge dynamically created because of indirect jump, etc. + INTRA_DYNA, + // Inter function jumps / calls. + INTER_FUNC_CALL, + INTER_FUNC_RETURN, + } Type = INTRA_FUNC; + + bool isCall() const { return Type == INTER_FUNC_CALL || Type == INTRA_RSC; } + + bool isReturn() const { + return Type == INTER_FUNC_RETURN || Type == INTRA_RSR; + } + + bool isFTEdge() const; + +protected: + CFGEdge(CFGNode *N1, CFGNode *N2, EdgeType T) + : Src(N1), Sink(N2), Weight(0), Type(T) {} + + friend class ControlFlowGraph; +}; + +// All instances of CFGNode are owned by their CFG. +class CFGNode { +public: + uint64_t Shndx; + StringRef ShName; + uint64_t ShSize; + // Note, "MappedAddr"s are not real/virtual addresses, they are ordinals from + // the propeller file. However, ordinals from propeller do reflect the true + // orders of symbol address. + uint64_t MappedAddr; + uint64_t Freq; + ControlFlowGraph *CFG; + + // Containing chain for this node assigned by the ordering algorithm. + // This will be updated as chains keep merging together during the algorithm. + NodeChain *Chain; + + // Offset of this node in the assigned chain. + uint64_t ChainOffset; + + std::vector Outs; // Intra function edges. + std::vector Ins; // Intra function edges. + std::vector CallOuts; // Callouts/returns to other functions. + std::vector CallIns; // Callins/returns from other functions. + + // Fallthrough edge, could be nullptr. And if not, FTEdge is in Outs. + CFGEdge *FTEdge; + + // In Selective BB mode - if this BB appears in the hot bbs section, then this + // is true. + // In AllBBMode - this is true if the function it belongs to appears in the + // hot bbs sections, even if the BB itself is cold. + // If HotTag is false, then the node Freq and all its edges Freqs are zero-ed + // out. + bool HotTag; + + const static uint64_t InvalidAddress = -1; + + unsigned getBBIndex() const { + StringRef FName, BName; + if (SymbolEntry::isBBSymbol(ShName, &FName, &BName)) + return BName.size(); + return 0; + } + + bool isEntryNode() const; + + template void forEachInEdgeRef(Visitor V) { + for (auto &edgeList : {Ins, CallIns}) + for (CFGEdge *E : edgeList) + V(*E); + } + + template void forEachIntraOutEdgeRef(Visitor V) { + for (CFGEdge *E : Outs) + V(*E); + } + + template void forEachOutEdgeRef(Visitor V) { + for (auto &edgeList : {Outs, CallOuts}) + for (CFGEdge *E : edgeList) + V(*E); + } + +private: + CFGNode(uint64_t _Shndx, const StringRef &_ShName, uint64_t _Size, + uint64_t _MappedAddr, ControlFlowGraph *_Cfg, bool _HotTag) + : Shndx(_Shndx), ShName(_ShName), ShSize(_Size), MappedAddr(_MappedAddr), + Freq(0), CFG(_Cfg), Chain(nullptr), ChainOffset(0), Outs(), Ins(), + CallOuts(), CallIns(), FTEdge(nullptr), HotTag(_HotTag) {} + + friend class ControlFlowGraph; + friend class CFGBuilder; +}; + +class ControlFlowGraph { +public: + ObjectView *View; + StringRef Name; + uint64_t Size; + + // Whether propeller should print information about how this CFG is being + // reordered. + bool DebugCFG; + bool Hot; + + // ControlFlowGraph assumes the ownership for all Nodes / Edges. + std::vector> Nodes; // Sorted by address. + std::vector> IntraEdges; + std::vector> InterEdges; + + ControlFlowGraph(ObjectView *V, const StringRef &N, uint64_t S) + : View(V), Name(N), Size(S), Hot(false) { + DebugCFG = std::find(propellerConfig.optDebugSymbols.begin(), + propellerConfig.optDebugSymbols.end(), + Name.str()) != propellerConfig.optDebugSymbols.end(); + } + + bool markPath(CFGNode *from, CFGNode *to, uint64_t cnt = 1); + void mapBranch(CFGNode *from, CFGNode *to, uint64_t cnt = 1, + bool isCall = false, bool isReturn = false); + void mapCallOut(CFGNode *from, CFGNode *to, uint64_t toAddr, uint64_t cnt = 1, + bool isCall = false, bool isReturn = false); + + CFGNode *getEntryNode() const { + assert(!Nodes.empty()); + return Nodes.begin()->get(); + } + + bool isHot() const { + if (Nodes.empty()) + return false; + return Hot; + // return (getEntryNode()->Freq != 0); + } + + template void forEachNodeRef(Visitor V) { + for (auto &N : Nodes) + V(*N); + } + + bool writeAsDotGraph(StringRef cfgOutName); + +private: + // Create and take ownership. + CFGEdge *createEdge(CFGNode *from, CFGNode *to, + typename CFGEdge::EdgeType type); + + void emplaceEdge(CFGEdge *edge) { + if (edge->Type < CFGEdge::INTER_FUNC_CALL) + IntraEdges.emplace_back(edge); + else + InterEdges.emplace_back(edge); + } + + friend class CFGBuilder; +}; + +class CFGBuilder { +public: + ObjectView *View; + + uint32_t BB = 0; + uint32_t BBWoutAddr = 0; + uint32_t InvalidCFGs = 0; + + CFGBuilder(ObjectView *vw) : View(vw) {} + + // See implementaion comments in .cpp. + bool buildCFGs(std::map &OrdinalRemapping); + +protected: + // + std::map> buildPreCFGGroups(); + + // See implementaion comments in .cpp. + void buildCFG(ControlFlowGraph &cfg, const SymbolRef &cfgSym, + std::map> &nodeMap, + std::map &relocationSectionMap); + + std::unique_ptr + buildCFGNodes(std::map>::value_type &GE, + std::map> &tmpNodeMap, + std::map &OrdinalRemapping); + + // See implementation comments in .cpp. + void calculateFallthroughEdges( + ControlFlowGraph &cfg, + std::map> &nodeMap); + + // Build a map from section "Idx" -> Section that relocates this + // section. Only used during building phase. + std::map buildRelocationSectionMap(); + // Build a map from section "Idx" -> node representing "Idx". Only + // used during building phase. + void buildShndxNodeMap(std::map> &nodeMap, + std::map &shndxNodeMap); +}; + +// ObjectView is a structure that corresponds to a single ELF file. +class ObjectView { +public: + ObjectView(std::unique_ptr &vF, const StringRef &vN, + const uint32_t vO, const MemoryBufferRef &fR) + : ViewFile(std::move(vF)), ViewName(vN), Ordinal(vO), FileRef(fR), + CFGs() {} + + void EraseCfg(ControlFlowGraph *&cfgPtr); + + std::unique_ptr ViewFile; + StringRef ViewName; + const uint32_t Ordinal; + MemoryBufferRef FileRef; + + // Name -> ControlFlowGraph mapping. + std::map> CFGs; +}; + +std::ostream &operator<<(std::ostream &out, const CFGNode &node); +std::ostream &operator<<(std::ostream &out, const CFGEdge &edge); +std::ostream &operator<<(std::ostream &out, const ControlFlowGraph &cfg); +} // namespace propeller +} // namespace lld +#endif Index: lld/ELF/Propeller/PropellerCFG.cpp =================================================================== --- /dev/null +++ lld/ELF/Propeller/PropellerCFG.cpp @@ -0,0 +1,643 @@ +//===-------------------- PropellerELFCfg.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 file creates cfg and maps propeller profile onto cfg nodes / edges. +// +//===----------------------------------------------------------------------===// +#include "PropellerCFG.h" + +#include "Propeller.h" + +#include "llvm/Object/ELFObjectFile.h" +#include "llvm/Support/raw_ostream.h" + +#include +#include +#include +#include +#include +#include +#include +#include + +using llvm::object::ObjectFile; +using llvm::object::RelocationRef; +using llvm::object::section_iterator; +using llvm::object::SectionRef; +using llvm::object::SymbolRef; + +namespace lld { +namespace propeller { + +bool CFGNode::isEntryNode() const { return CFG->getEntryNode() == this; } + +bool ControlFlowGraph::writeAsDotGraph(StringRef cfgOutName) { + std::error_code ec; + llvm::raw_fd_ostream os(cfgOutName, ec, llvm::sys::fs::CD_CreateAlways); + if (ec.value()) { + warn("failed to open: '" + cfgOutName + "'"); + return false; + } + os << "digraph " << Name.str() << "{\n"; + forEachNodeRef([&os](CFGNode &n) { + os << n.getBBIndex() << " [size=\"" << n.ShSize << "\"];"; + }); + os << "\n"; + for (auto &e : IntraEdges) { + bool IsFTEdge = (e->Src->FTEdge == e.get()); + os << " " << e->Src->getBBIndex() << " -> " << e->Sink->getBBIndex() + << " [label=\"" << e->Weight + << "\", weight=" << (IsFTEdge ? "1.0" : "0.1") << "];\n"; + } + os << "}\n"; + llvm::outs() << "done dumping cfg '" << Name.str() << "' into '" + << cfgOutName.str() << "'\n"; + return true; +} + +// Create an edge for "from->to". +CFGEdge *ControlFlowGraph::createEdge(CFGNode *from, CFGNode *to, + typename CFGEdge::EdgeType type) { + CFGEdge *edge = nullptr; + auto CheckExistingEdge = [from, to, type, + &edge](std::vector &Edges) { + for (auto *E : Edges) { + if (E->Src == from && E->Sink == to && E->Type == type) { + edge = E; + return true; + } + } + return false; + }; + if (!from->HotTag || !to->HotTag) { + if (type < CFGEdge::EdgeType::INTER_FUNC_CALL && + CheckExistingEdge(from->Outs)) + return edge; + if (type >= CFGEdge::EdgeType::INTER_FUNC_CALL && + CheckExistingEdge(from->CallOuts)) + return edge; + } + + edge = new CFGEdge(from, to, type); + if (type < CFGEdge::EdgeType::INTER_FUNC_CALL) { + from->Outs.push_back(edge); + to->Ins.push_back(edge); + } else { + from->CallOuts.push_back(edge); + to->CallIns.push_back(edge); + } + // Take ownership of "edge", cfg is responsible for all edges. + emplaceEdge(edge); + return edge; +} + +// Apply counter (cnt) to all edges between node from -> to. Both nodes are from +// the same cfg. +bool ControlFlowGraph::markPath(CFGNode *from, CFGNode *to, uint64_t cnt) { + if (from == nullptr) { + // If the from node is null, walk backward from the to node while only + // one INTRA_FUNC incoming edge is found. + assert(to != nullptr); + CFGNode *p = to; + do { + if (p->Ins.size() == 1 && p->Ins.front()->isFTEdge()) { + p->Ins.front()->Weight += cnt; + p = p->Ins.front()->Src; + } else + p = nullptr; + } while (p && p != to); + return true; + } + + if (to == nullptr) { + // If the to node is null, walk forward from the from node while only + // one INTRA_FUNC outgoing edge is found. + assert(from != nullptr); + CFGNode *p = from; + do { + if (p->Outs.size() == 1 && p->Outs.front()->isFTEdge()) { + p->Outs.front()->Weight += cnt; + p = p->Outs.front()->Sink; + } else + p = nullptr; + } while (p && p != from); + return true; + } + + assert(from->CFG == to->CFG); + if (from == to) + return true; + CFGNode *p = from; + + // Iterate over fallthrough edges between from and to, adding every edge in + // between to a vector. + SmallVector fallThroughEdges; + while (p && p != to) { + if (p->FTEdge) { + fallThroughEdges.push_back(p->FTEdge); + p = p->FTEdge->Sink; + } else + p = nullptr; + } + if (!p) { // Fallthroughs break between from and to. + warn("Fallthrough break between " + from->ShName + " and " + to->ShName); + return false; + } + + for (auto *e : fallThroughEdges) + e->Weight += cnt; + + return true; +} + +// Apply counter (cnt) to the edge from node from -> to. Both nodes are from the +// same cfg. +void ControlFlowGraph::mapBranch(CFGNode *from, CFGNode *to, uint64_t cnt, + bool isCall, bool isReturn) { + assert(from->CFG == to->CFG); + + for (auto &e : from->Outs) { + bool edgeTypeOk = true; + if (!isCall && !isReturn) + edgeTypeOk = + e->Type == CFGEdge::INTRA_FUNC || e->Type == CFGEdge::INTRA_DYNA; + else if (isCall) + edgeTypeOk = e->Type == CFGEdge::INTRA_RSC; + if (isReturn) + edgeTypeOk = e->Type == CFGEdge::INTRA_RSR; + if (edgeTypeOk && e->Sink == to) { + e->Weight += cnt; + return; + } + } + + CFGEdge::EdgeType type = CFGEdge::INTRA_DYNA; + if (isCall) + type = CFGEdge::INTRA_RSC; + else if (isReturn) + type = CFGEdge::INTRA_RSR; + + createEdge(from, to, type)->Weight += cnt; +} + +// Apply counter (cnt) for calls/returns/ that cross function boundaries. +void ControlFlowGraph::mapCallOut(CFGNode *from, CFGNode *to, uint64_t toAddr, + uint64_t cnt, bool isCall, bool isReturn) { + assert(from->CFG == this); + assert(from->CFG != to->CFG); + CFGEdge::EdgeType edgeType = CFGEdge::INTER_FUNC_RETURN; + if (isCall || + (toAddr && to->CFG->getEntryNode() == to && toAddr == to->MappedAddr)) + edgeType = CFGEdge::INTER_FUNC_CALL; + if (isReturn) + edgeType = CFGEdge::INTER_FUNC_RETURN; + for (auto &e : from->CallOuts) + if (e->Sink == to && e->Type == edgeType) { + e->Weight += cnt; + return; + } + createEdge(from, to, edgeType)->Weight += cnt; +} + +std::map> CFGBuilder::buildPreCFGGroups() { + std::map> groups; + auto symbols = View->ViewFile->symbols(); + for (const SymbolRef &sym : symbols) { + auto r = sym.getType(); + auto s = sym.getName(); + if (r && s && *r == SymbolRef::ST_Function) { + StringRef symName = *s; + auto ri = groups.emplace(std::piecewise_construct, + std::forward_as_tuple(symName), + std::forward_as_tuple(1, sym)); + (void)(ri.second); + assert(ri.second); + } + } + + // Now we have a map of function names, group "x.bb.funcname". + for (const SymbolRef &sym : symbols) { + // All bb symbols are local, upon seeing the first global, exit. + if ((sym.getFlags() & SymbolRef::SF_Global) != 0) + break; + auto nameOrErr = sym.getName(); + if (!nameOrErr) + continue; + StringRef sName = *nameOrErr; + StringRef fName; + if (SymbolEntry::isBBSymbol(sName, &fName, nullptr)) { + auto L = groups.find(fName); + if (L != groups.end()) + L->second.push_back(sym); + } + } + return groups; +} + +// Build map: TextSection -> It's Relocation Section. +// ELF file only contains link from Relocation Section -> It's text section. +std::map CFGBuilder::buildRelocationSectionMap() { + std::map relocationSectionMap; + for (section_iterator i = View->ViewFile->section_begin(), + J = View->ViewFile->section_end(); + i != J; ++i) { + SectionRef secRef = *i; + if (llvm::object::ELFSectionRef(secRef).getType() == llvm::ELF::SHT_RELA) { + Expected rr = secRef.getRelocatedSection(); + if (rr) { + section_iterator &r = *rr; + assert(r != J); + relocationSectionMap.emplace(r->getIndex(), *i); + } + } + } + return relocationSectionMap; +} + +// Helper method, process an entry of group. +// In selective bb sections, different cold bb lables are grouped into one same +// cold section. Like below: +// +// section .txt.func: bb1 (ordinal=100) +// section .txt.func: bb2 (ordinal=101) +// section .txt.func.cold: bb3 (ordinal=102) +// bb4 (ordinal=103) +// bb5 (ordinal=104) +// +// After processing, OrdinalRemapping contains: +// 102 -> 102 +// 103 -> 102 +// 104 -> 102 +// +// And tmpNodeMap contains: +// 100 -> CfgNode(MappedAddr=100) +// 101 -> CfgNode(MappedAddr=101) +// 102 -> CfgNode(MappedAddr=102) +// +std::unique_ptr CFGBuilder::buildCFGNodes( + std::map>::value_type &GE, + std::map> &tmpNodeMap, + std::map &OrdinalRemapping) { + assert(GE.second.size() >= 1); + std::map>> + bbGroupSectionMap; + StringRef cfgName = GE.first; + std::unique_ptr cfg(new ControlFlowGraph(View, cfgName, 0)); + + for (SymbolRef sym : GE.second) { + auto symNameE = sym.getName(); + auto sectionIE = sym.getSection(); + if (!symNameE && !sectionIE && + (*sectionIE) == sym.getObject()->section_end()) { + tmpNodeMap.clear(); + break; + } + + StringRef symName = *symNameE; + uint64_t symShndx = (*sectionIE)->getIndex(); + uint64_t symSectionSize = (*sectionIE)->getSize(); + uint64_t symValue = sym.getValue(); + // Note here: BB symbols only carry size information when + // -fbasicblock-section=all. Objects built with + // -fbasicblock-section=labels do not have size information + // for BB symbols. + // uint64_t symSize = llvm::object::ELFSymbolRef(sym).getSize(); + SymbolEntry *sE = prop->Propf->findSymbol(symName); + // symValue is the offset of the bb symbol within a bbsection, if + // symValue is nonzero, it means the symbol is not on its own + // section, safe to ignore mapping with a propeller symbol. This + // is a symbol grouped together w/ other bb symbols in the same + // section (the cold section or the landing pad section), and this + // bb symbol is not the representative symbol of the bb section. + if (!sE) { + if (symValue != 0) + continue; + tmpNodeMap.clear(); + break; + } + + if (tmpNodeMap.find(sE->Ordinal) != tmpNodeMap.end()) { + tmpNodeMap.clear(); + error("Internal error checking cfg map."); + break; + } + // All cold BBs go into a single cold section. All landing pads go + // into a single landing pad section. Note, hot landing pads are + // grouped into the landing pad section. A hot land pad does not + // have its own section. + bool needGroup = + !sE->HotTag || symName.front() == 'l' || symName.front() == 'L'; + if (needGroup) { + auto groupI = bbGroupSectionMap.find(symShndx); + if (groupI != bbGroupSectionMap.end()) { + CFGNode *groupNode = groupI->second.first; + // All group nodes share the same section, so the ShSize field must + // equal. + if (groupNode->ShSize != symSectionSize) { + tmpNodeMap.clear(); + error("Check internal size error."); + break; + } + // The first node within the section is the representative node. + if (groupNode->MappedAddr > sE->Ordinal) { + groupNode->MappedAddr = sE->Ordinal; + groupNode->ShName = symName; + groupNode->ShSize = symSectionSize; + } + if (!groupI->second.second.insert(sE).second) { + tmpNodeMap.clear(); + error("Internal error grouping sections."); + break; + } + continue; // to next sym. + } + } + + // Drop bb sections with no code + if (!symSectionSize) + continue; + CFGNode *node = new CFGNode(symShndx, symName, symSectionSize, sE->Ordinal, + cfg.get(), sE->HotTag); + tmpNodeMap.emplace(sE->Ordinal, node); + if (needGroup) { + auto &P = bbGroupSectionMap[symShndx]; + P.first = node; + if (!P.second.insert(sE).second) { + error("Internal error grouping duplicated sections."); + tmpNodeMap.clear(); + break; + } + } + } + + if (tmpNodeMap.empty()) { + cfg.reset(nullptr); + return cfg; + } + + for (auto &P : bbGroupSectionMap) { + auto *Node = P.second.first; + auto &SymSet = P.second.second; + if (SymSet.size() > 1) { + SymbolEntry *FirstSymbol = *(SymSet.begin()); + if (FirstSymbol->Ordinal != Node->MappedAddr) { + error("Internal error grouping sections."); + cfg.reset(nullptr); + return cfg; + } + for (SymbolEntry *SS : SymSet) { + if (!OrdinalRemapping.emplace(SS->Ordinal, Node->MappedAddr).second + /* The representative Node must have the smallest MappedAddr + (Ordinal) */ + || SS->Ordinal < Node->MappedAddr) { + error("Internal error remapping duplicated sections."); + cfg.reset(nullptr); + return cfg; + } + } + } + } + return cfg; +} + +// This function creates CFGs for a single object file. +// +// Step 1 - scan all the symbols, for each function symbols, create an entry in +// "groups", below is what "groups" looks like: +// groups: { +// "foo": [], +// "bar": [], +// } +// +// Step 2 - scan all the symbols, for each BB symbol, find it's function's +// group, and insert the bb symbol into the group. For example, if we have BB +// symbols "a.BB.foo", "aa.BB.foo" and "a.BB.bar", after step 2, the groups +// structure looks like: +// groups: { +// "foo": ["a.BB.foo", "aa.BB.foo"], +// "bar": ["a.BB.bar"], +// } +// +// Step 3 - for each group, create CFG and tmpNodeMap, the latter is an ordered +// map of CFGNode (index key is Symbol Ordinal). For the above example, the +// following data structure is created: +// CFG[Name=foo], tmpNodeMap={1: CFGNode[BBIndex="1"], 2:CFGNode[BBIndex="2"]} +// CFG[Name=bar], tmpNodeMap={3: CFGNode[BBIndex="3"]} +// +// For each CFG and tmpNodeMap, call CFGBuilder::buildCFG(). +bool CFGBuilder::buildCFGs(std::map &OrdinalRemapping) { + std::map> groups{buildPreCFGGroups()}; + std::map relocationSectionMap{ + buildRelocationSectionMap()}; + + // Groups built in the above step are like: + // { + // { "func1", {a.BB.func1, aa.BB.func1, aaa.BB.func1} + // { "func2", {a.BB.func2, aa.BB.func2, aaa.BB.func2} + // ... + // ... + // } + for (auto &i : groups) { + std::map> tmpNodeMap; + std::unique_ptr cfg{ + buildCFGNodes(i, tmpNodeMap, OrdinalRemapping)}; + + if (cfg) { + SymbolRef cfgSym = *(i.second.begin()); + buildCFG(*cfg, cfgSym, tmpNodeMap, relocationSectionMap); + View->CFGs.emplace(cfg->Name, std::move(cfg)); + } + } // Enf of processing all groups. + return true; +} + +// Build map: basicblock section index -> basicblock section node. +void CFGBuilder::buildShndxNodeMap( + std::map> &tmpNodeMap, + std::map &shndxNodeMap) { + for (auto &nodeL : tmpNodeMap) { + auto &node = nodeL.second; + auto insertResult = shndxNodeMap.emplace(node->Shndx, node.get()); + (void)(insertResult); + assert(insertResult.second); + } +} + +// Build CFG for a single function. +// +// For each BB sections of a single function, we iterate all the relocation +// entries, and for relocations that targets another BB in the same function, +// we create an edge between these 2 BBs. +void CFGBuilder::buildCFG( + ControlFlowGraph &cfg, const SymbolRef &cfgSym, + std::map> &tmpNodeMap, + std::map &relocationSectionMap) { + std::map shndxNodeMap; + buildShndxNodeMap(tmpNodeMap, shndxNodeMap); + + // Recursive call edges. + // std::list rscEdges; + // Iterate all bb symbols. + for (auto &nPair : tmpNodeMap) { + CFGNode *srcNode = nPair.second.get(); + // For each bb section, we find its rela sections. + auto relaSecRefI = relocationSectionMap.find(srcNode->Shndx); + if (relaSecRefI == relocationSectionMap.end()) + continue; + + // Iterate all rela entries. + for (const RelocationRef &rela : relaSecRefI->second->relocations()) { + SymbolRef rSym = *(rela.getSymbol()); + bool isRSC = (cfgSym == rSym); + + // All bb section symbols are local symbols. + if (!isRSC && + ((rSym.getFlags() & llvm::object::BasicSymbolRef::SF_Global) != 0)) + continue; + + auto sectionIE = rSym.getSection(); + if (!sectionIE) + continue; + // Now we have the Shndx of one relocation target. + uint64_t symShndx((*sectionIE)->getIndex()); + CFGNode *targetNode{nullptr}; + // Check to see if Shndx is another BB section within the same function. + auto result = shndxNodeMap.find(symShndx); + if (result != shndxNodeMap.end()) { + targetNode = result->second; + if (targetNode) { + // If so, we create the edge. + // CFGEdge *e = + cfg.createEdge(srcNode, targetNode, + isRSC ? CFGEdge::INTRA_RSC : CFGEdge::INTRA_FUNC); + // If it's a recursive call, record it. + // if (isRSC) + // rscEdges.push_back(e); + } + } + } + } + + /* + // For each recursive call, we create a recursive-self-return edges for all + // exit edges. In the following example, create an edge bb5->bb3 FuncA: + // bb1: <---+ + // ... | + // bb2: | + // ... | r(ecursie)-s(elf)-C(all) edge + // bb3: | + // ... | + // call FuncA --- + + // xxx yyy <---+ + // ... | + // bb4: | + // ... | r(ecursie)-s(elf)-r(eturn) edge + // bb5: | + // ... | + // ret ----------+ + for (auto *rEdge : rscEdges) { + for (auto &nPair : tmpNodeMap) { + auto &n = nPair.second; + if (n->Outs.size() == 0 || + (n->Outs.size() == 1 && + (*n->Outs.begin())->Type == CFGEdge::INTRA_RSC)) { + // Now "n" is the exit node. + cfg.createEdge(n.get(), rEdge->Src, CFGEdge::INTRA_RSR); + } + } + } + */ + calculateFallthroughEdges(cfg, tmpNodeMap); + + // Transfer nodes ownership to cfg and destroy tmpNodeMap. + for (auto &pair : tmpNodeMap) { + cfg.Nodes.emplace_back(std::move(pair.second)); + pair.second.reset(nullptr); + } + tmpNodeMap.clear(); + + // Calculate the cfg size + cfg.Size = 0; + cfg.forEachNodeRef([&cfg](CFGNode &n) { cfg.Size += n.ShSize; }); +} + +// Calculate fallthroughs. Edge p->q is fallthrough if p & q are adjacent (e.g. +// no other bbs are between p & q), and there is a NORMAL edge from p->Q. +// +// tmpNodeMap groups nodes according to their beginning address: +// addr1: [Node1] +// addr2: [Node2] +// addr3: [Node3] +// addr4: [Node4] +// And addr1 <= addr2 <= addr3 <= addr4. +void CFGBuilder::calculateFallthroughEdges( + ControlFlowGraph &cfg, + std::map> &tmpNodeMap) { + + auto setupFallthrough = [&cfg](CFGNode *n1, CFGNode *n2) { + for (auto *e : n1->Outs) + if (e->Type == CFGEdge::INTRA_FUNC && e->Sink == n2) { + n1->FTEdge = e; + return; + } + if (n1->ShSize == 0) + // An empty section always fallthrough to the next adjacent section. + n1->FTEdge = cfg.createEdge(n1, n2, CFGEdge::INTRA_FUNC); + }; + + for (auto p = tmpNodeMap.begin(), q = std::next(p), e = tmpNodeMap.end(); + q != e; ++p, ++q) + setupFallthrough(p->second.get(), q->second.get()); +} + +std::ostream &operator<<(std::ostream &out, const CFGNode &node) { + out << "[" + << (node.ShName == node.CFG->Name + ? "Entry" + : std::to_string(node.ShName.size() - node.CFG->Name.size() - 4)) + << "]" + << " [size=" << std::noshowbase << std::dec << node.ShSize << ", " + << " addr=" << std::showbase << std::hex << node.MappedAddr << ", " + << " frequency=" << std::showbase << std::dec << node.Freq << ", " + << " shndx=" << std::noshowbase << std::dec << node.Shndx << "]"; + return out; +} + +std::ostream &operator<<(std::ostream &out, const CFGEdge &edge) { + static const char *TypeStr[] = {"", " (*RSC*)", " (*RSR*)", " (*DYNA*)"}; + out << "edge: " << *edge.Src << " -> " << *edge.Sink << " [" << std::setw(12) + << std::setfill('0') << std::noshowbase << std::dec << edge.Weight << "]" + << TypeStr[edge.Type]; + return out; +} + +std::ostream &operator<<(std::ostream &out, const ControlFlowGraph &cfg) { + out << "cfg: '" << cfg.View->ViewName.str() << ":" << cfg.Name.str() + << "', size=" << std::noshowbase << std::dec << cfg.Size << std::endl; + for (auto &n : cfg.Nodes) { + auto &node = *n; + out << " node: " << node << std::endl; + for (auto &edge : node.Outs) { + out << " " << *edge << (edge == node.FTEdge ? " (*FT*)" : "") + << std::endl; + } + for (auto &edge : node.CallOuts) { + out << " Calls: '" << edge->Sink->ShName.str() + << "': " << std::noshowbase << std::dec << edge->Weight << std::endl; + } + } + out << std::endl; + return out; +} + +bool CFGEdge::isFTEdge() const { return Src->FTEdge == this; } + +} // namespace propeller +} // namespace lld Index: lld/ELF/Propeller/PropellerConfig.h =================================================================== --- /dev/null +++ lld/ELF/Propeller/PropellerConfig.h @@ -0,0 +1,43 @@ +//===-------------------- PropellerConfig.h -------------------------------===// +// + +#ifndef LLD_ELF_PROPELLER_CONFIG_H +#define LLD_ELF_PROPELLER_CONFIG_H + +#include "llvm/ADT/StringRef.h" + +#include +#include + +using llvm::StringRef; + +namespace lld { +namespace propeller { + +struct PropellerConfig { + uint64_t optBackwardJumpDistance; + double optBackwardJumpWeight; + std::vector optBBOrder; + uint64_t optChainSplitThreshold; + std::vector optDebugSymbols; + std::vector optDumpCfgs; + StringRef optDumpSymbolOrder; + double optFallthroughWeight; + uint64_t optForwardJumpDistance; + double optForwardJumpWeight; + 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/ELF/Propeller/PropellerProtobuf.h =================================================================== --- /dev/null +++ lld/ELF/Propeller/PropellerProtobuf.h @@ -0,0 +1,59 @@ +#ifndef LLD_ELF_PROPELLER_PROTOBUF_H +#define LLD_ELF_PROPELLER_PROTOBUF_H +#ifdef PROPELLER_PROTOBUF + +#include "google/protobuf/io/zero_copy_stream_impl.h" +#include "lld/Common/ErrorHandler.h" +#include "propeller_cfg.pb.h" +#include "llvm/Support/raw_ostream.h" + +#include +#include +#include + +#include +#include + +namespace lld { +namespace propeller { + +class ControlFlowGraph; +class CFGNode; + +class ProtobufPrinter { +public: + static ProtobufPrinter *create(const std::string &name) { + int fd = open(name.c_str(), O_WRONLY | O_CREAT | O_TRUNC, + S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP | S_IROTH); + if (fd == -1) { + error(StringRef("Failed to create/open '") + name + "'."); + return nullptr; + } + return new ProtobufPrinter(name, fd); + } + + void addCFG(ControlFlowGraph &cfg, + std::list *orderedBBs = nullptr); + + void clearCFGGroup() { cfgGroupPb.clear_cfg_list(); } + + void printCFGGroup(); + + ~ProtobufPrinter() { outStream.Close(); } + +private: + ProtobufPrinter(const std::string &name, int fd) + : outName(name), outStream(fd) {} + + void populateCFGPB(llvm::plo::cfg::CFG &cfgpb, const ControlFlowGraph &cfg); + + std::string outName; + google::protobuf::io::FileOutputStream outStream; + llvm::plo::cfg::CFGGroup cfgGroupPb; +}; + +} // namespace propeller +} // namespace lld + +#endif +#endif Index: lld/ELF/Propeller/PropellerProtobuf.cpp =================================================================== --- /dev/null +++ lld/ELF/Propeller/PropellerProtobuf.cpp @@ -0,0 +1,68 @@ +#ifdef PROPELLER_PROTOBUF +#include "PropellerProtobuf.h" + +#include "PropellerCFG.h" +#include "propeller_cfg.pb.h" + +#include "google/protobuf/io/zero_copy_stream_impl.h" +#include "google/protobuf/text_format.h" + +#include + +namespace lld { +namespace propeller { + +void ProtobufPrinter::printCFGGroup() { + if (!google::protobuf::TextFormat::Print(cfgGroupPb, &outStream)) + error("Failed to dump cfg to file."); + llvm::outs() << "Printed " << cfgGroupPb.cfg_list_size() << " CFGs to '" + << outName << "'.\n"; +} + +void ProtobufPrinter::addCFG(ControlFlowGraph &cfg, + std::list *orderedBBs) { + llvm::plo::cfg::CFG &cfgpb = *(cfgGroupPb.add_cfg_list()); + cfgpb.set_name(cfg.Name.str()); + cfgpb.set_size(cfg.Size); + cfgpb.set_object_name(cfg.View->ViewName.str()); + + auto populateEdgePb = [](llvm::plo::cfg::Edge &edgepb, CFGEdge &edge) { + edgepb.set_source(edge.Src->getBBIndex()); + edgepb.set_target(edge.Sink->getBBIndex()); + edgepb.set_profile_count(edge.Weight); + edgepb.set_type(static_cast( + (int)(edge.Type) - (int)(CFGEdge::INTRA_FUNC))); + }; + + auto populateBasicBlockPb = + [&populateEdgePb](llvm::plo::cfg::BasicBlock &bbpb, CFGNode &node) { + bbpb.set_index(node.getBBIndex()); + bbpb.set_size(node.ShSize); + bbpb.set_profile_count(node.Freq); + + for (CFGEdge *e : node.Ins) + populateEdgePb(*(bbpb.add_incoming_edges()), *e); + + for (CFGEdge *e : node.Outs) + populateEdgePb(*(bbpb.add_outgoing_edges()), *e); + + if (node.FTEdge) + populateEdgePb(*(bbpb.mutable_fallthrough()), *node.FTEdge); + + bbpb.set_hot_tag(node.HotTag); + }; + + if (orderedBBs) + for (auto *node : *orderedBBs) + populateBasicBlockPb(*(cfgpb.add_basic_blocks()), *node); + else + for (auto &node : cfg.Nodes) + populateBasicBlockPb(*(cfgpb.add_basic_blocks()), *node); + + CFGNode *entryNode = cfg.getEntryNode(); + cfgpb.set_entry_block(entryNode ? entryNode->getBBIndex() : 0); +} + +} // namespace propeller +} // namespace lld +#endif Index: lld/ELF/Propeller/README.md =================================================================== --- /dev/null +++ lld/ELF/Propeller/README.md @@ -0,0 +1,68 @@ +This directory contains core source files of propeller framework. + +LLVM RFC: http://lists.llvm.org/pipermail/llvm-dev/2019-September/135393.html + +# 1. About the propeller framework. + +Propeller is framework that, with the aid of embedded information +in ELF obejct files, does optimization at the linking phase. + +# 2. How (current) propeller works. + +## [The compiler part] + + Each basicblock is represented using a standalone elf section. + +## [The profile part] + + A propeller-format profile ('propfile') is generated, which + contains counters for jumps/calls/returns of each bb. + +## [The lld part] + + LLD handles execution to propeller (Propeller.h is the interface + that works with lld), which does a few things for each ELF object + file: + + 1. generates control flow graph (CFG) for each function, this is + possible because each basicblock section resides in a single elf + section and we use relocation entries to determine jump/call + targets of each basicblock section + + 2. parses propfile (the propeller-format profile), apply + basicblock counters, edge counters to CFGs + + 3. passes information in (2) to BBReordering and FunctionOrdering + pass, which generates list of optimal basicblock symbol ordering + + 4. Propeller feeds the list (generated in (3)) back to lld, and lld + continues to work as usual. + +# Some misconections: + + - Propeller only works on top of ThinLTO (regular PGO, csPGO, etc). + + The above statement is not correct. Propeller works on any + binaries and brings performance improvement on top of the binary, + regardless of how the binaries are optimized. + + - Propeller is an extension to -ffunction-sections and -fdata-sections. + + The above statement is not correct. Propeller is a *general* + framework, it will be able to do things like reodering individual + insns, remove/insert spill insns, etc. And we have plans for + future optimizations based on propeller framework (not on bb + sections). + + However, current Propeller's main optimization + (function-splitting, function-reordering, basicblock-reordering) + is done via -fbasicblock-sections, which is an extension of + -ffunction-sections. + +# 3. Where are other propeller related files? + + - ../LinkerPropeller.h ../LinkerPropeller.cpp interfaces that + interact with lld. + + - ../../include/lld/Common/PropellerCommon.h common interfaces that + are used by create_llvm_prof. Index: lld/ELF/Propeller/propeller_cfg.proto =================================================================== --- /dev/null +++ lld/ELF/Propeller/propeller_cfg.proto @@ -0,0 +1,85 @@ +syntax = "proto2"; + +package llvm.plo.cfg; + +// Edge between basic blocks. +// Next Available: 5. +message Edge { + // Index of the source basic block. + optional int32 source = 1; + + // Index of the target basic block. + optional int32 target = 2; + + // Frequency count of the jump from profile. + optional int32 profile_count = 3; + + enum Type { + INTRA_FUNC = 0; + INTRA_RSC = 1; // Recursive call. + INTRA_RSR = 2; // Return from recursive call. + // Intra edge dynamically created because of indirect jump, etc. + INTRA_DYNA = 3; + // Inter function jumps / calls. + INTER_FUNC_CALL = 4; + // Inter function returns. + INTER_FUNC_RETURN = 5; + } + + // Edge type + optional Type type = 4; +} + +// Basic block in cfg. +// Next Available: 8. +message BasicBlock { + // 0-based index that distinguishes between different basic blocks. + optional int32 index = 1; + + // Size of the basic block. + optional int32 size = 2; + + // Frequency count of the basic block from profile, defined as + // max(sum(incoming_edges), sum(outgoing_edges)). + optional int32 profile_count = 3; + + // Edges coming into this basic block. + repeated Edge incoming_edges = 4; + + // Edges going out of this basic block. + repeated Edge outgoing_edges = 5; + + // Fallthrough edge of this basic block. + optional Edge fallthrough = 6; + + // + optional bool hot_tag = 7; +} + +// Control flow graph where basic blocks are vertices and jumps are edges. +// Next Available: 7. +message CFG { + // Name of the function. + optional string name = 1; + + // Size of the function. + optional int32 size = 2; + + // Basic blocks in the CFG. + // The sequence of the repeated field matches the after-propeller layout. + repeated BasicBlock basic_blocks = 3; + + // Basic block layout represented with sequence of bb indices (may only + // include hot bbs). + repeated int32 basic_block_layout = 6; + + // The index of the entry block in the CFG. + optional int32 entry_block = 4; + + // Object name of the function belongs to. + optional string object_name = 5; +} + +// A group of CFGs. +// Next Available: 2. +message CFGGroup { repeated CFG cfg_list = 1; } Index: lld/include/lld/Common/PropellerCommon.h =================================================================== --- /dev/null +++ lld/include/lld/Common/PropellerCommon.h @@ -0,0 +1,163 @@ +#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, bool R = false) + : 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 containsAddress(uint64_t A) const { + return Addr <= A && A < Addr + Size; + } + + bool containsAnotherSymbol(SymbolEntry *O) const { + if (O->Size == 0) { + // Note if O's size is 0, we allow O on the end boundary. For example, if + // foo.BB.4 is at address 0x10. foo is [0x0, 0x10), we then assume foo + // contains foo.BB.4. + return this->Addr <= O->Addr && O->Addr <= this->Addr + this->Size; + } + return containsAddress(O->Addr) && containsAddress(O->Addr + O->Size - 1); + } + + bool operator<(const SymbolEntry &Other) const { + return this->Ordinal < Other.Ordinal; + } + + bool isFunction() const { + return this->Type == llvm::object::SymbolRef::ST_Function; + } + + // Return true if this SymbolEntry is a containing function for BBName. For + // example, if BBName is given as "aa.BB.foo", and SymbolEntry.Name = "foo", + // then SymbolEntry.isFunctionForBBName(BBName) == true. BBNames are from ELF + // object files. + bool isFunctionForBBName(StringRef BBName) const { + auto A = BBName.split(BASIC_BLOCK_SEPARATOR); + if (A.second == Name) + return true; + for (auto N : Aliases) + if (A.second == N) + return true; + return false; + } + + // 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:; + } + 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 true; + if ((S1 && !S2) || (!S1 && !S2)) + return false; + return S1->Ordinal < S2->Ordinal; + } +}; + +} // namespace propeller +} // namespace lld +#endif Index: lld/test/ELF/propeller/Inputs/bad-propeller-1.data =================================================================== --- /dev/null +++ lld/test/ELF/propeller/Inputs/bad-propeller-1.data @@ -0,0 +1,2 @@ +Symbols +a 2b N_start Index: lld/test/ELF/propeller/Inputs/bad-propeller-2.data =================================================================== --- /dev/null +++ lld/test/ELF/propeller/Inputs/bad-propeller-2.data @@ -0,0 +1,2 @@ +Symbols +1 2b Index: lld/test/ELF/propeller/Inputs/bad-propeller-3.data =================================================================== --- /dev/null +++ lld/test/ELF/propeller/Inputs/bad-propeller-3.data @@ -0,0 +1,2 @@ +Symbols +1 2b main Index: lld/test/ELF/propeller/Inputs/bad-propeller-4.data =================================================================== --- /dev/null +++ lld/test/ELF/propeller/Inputs/bad-propeller-4.data @@ -0,0 +1,3 @@ +Symbols +1 2b Nmain +2 10 3.1 Index: lld/test/ELF/propeller/Inputs/bad-propeller-5.data =================================================================== --- /dev/null +++ lld/test/ELF/propeller/Inputs/bad-propeller-5.data @@ -0,0 +1,4 @@ +Symbols +1 2b Nmain +2 10 1.1 +3 10 2.1 Index: lld/test/ELF/propeller/Inputs/propeller-2.data =================================================================== --- /dev/null +++ lld/test/ELF/propeller/Inputs/propeller-2.data @@ -0,0 +1,34 @@ +Symbols +1 2b N_start +2 1 N_dl_relocate_static_pie +3 0 Nderegister_tm_clones +4 0 Nregister_tm_clones +5 0 N__do_global_dtors_aux +6 0 Nframe_dummy +7 57 Nthis_is_very_code +8 2c Ncompute_flag +9 c2 Nmain +10 b 9.5 +11 12 9.1 +12 24 9.2 +13 2a 9.3 +14 1f 9.4 +15 8 9.6 +16 5d N__libc_csu_init +17 1 N__libc_csu_fini +18 0 N_init +19 0 N_fini +Branches +8 11 293285 R +11 8 295501 C +11 13 181981 +13 10 283908 +Fallthroughs +8 8 286906 +10 11 281228 +11 11 179986 +11 13 94381 +13 13 178963 +!compute_flag +!main +! Index: lld/test/ELF/propeller/Inputs/propeller-3.data =================================================================== --- /dev/null +++ lld/test/ELF/propeller/Inputs/propeller-3.data @@ -0,0 +1 @@ +@not_a_valid_file_name_957349kfhskg591yjkvhsd Index: lld/test/ELF/propeller/Inputs/propeller.data =================================================================== --- /dev/null +++ lld/test/ELF/propeller/Inputs/propeller.data @@ -0,0 +1,31 @@ +Symbols +1 2b N_start +2 1 N_dl_relocate_static_pie +3 0 Nderegister_tm_clones +4 0 Nregister_tm_clones +5 0 N__do_global_dtors_aux +6 0 Nframe_dummy +7 2c Ncompute_flag +8 7b Nmain +9 b 8.3 +10 12 8.1 +11 26 8.2 +12 8 8.4 +13 5d N__libc_csu_init +14 1 N__libc_csu_fini +15 0 N_init +16 0 N_fini +Branches +7 10 282779 R +10 7 289388 C +10 9 165714 +11 9 110451 +Fallthroughs +7 7 280473 +9 10 273908 +10 10 160338 +10 11 106891 +!_start +!compute_flag +!main +! Index: lld/test/ELF/propeller/Inputs/sample.c =================================================================== --- /dev/null +++ lld/test/ELF/propeller/Inputs/sample.c @@ -0,0 +1,26 @@ +/* sample.c */ +volatile int count; + +__attribute__((noinline)) int compute_flag(int i) { + if (i % 10 < 4) /* ... in 40% of the iterations */ + return i + 1; + return 0; +} + +int main(void) { + int i; + int flag; + volatile double x = 1212121212, + y = 121212; /* Avoid compiler optimizing away */ + + for (i = 0; i < 2000000000; i++) { + flag = compute_flag(i); + + /* Some other code */ + count++; + + if (flag) + x += x / y + y / x; /* Execute expensive division if flag is set */ + } + return 0; +} Index: lld/test/ELF/propeller/propeller-bad-profile-1.s =================================================================== --- /dev/null +++ lld/test/ELF/propeller/propeller-bad-profile-1.s @@ -0,0 +1,7 @@ +# REQUIRES: x86 +## Test control flow graph is created. + +# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o +# RUN: not ld.lld -propeller=%S/Inputs/bad-propeller-1.data %t.o -o %t.out 2>&1 | FileCheck %s --check-prefix=CHECK + +# CHECK: invalid ordinal field Index: lld/test/ELF/propeller/propeller-bad-profile-2.s =================================================================== --- /dev/null +++ lld/test/ELF/propeller/propeller-bad-profile-2.s @@ -0,0 +1,7 @@ +# REQUIRES: x86 +## Test control flow graph is created. + +# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o +# RUN: not ld.lld -propeller=%S/Inputs/bad-propeller-2.data %t.o -o %t.out 2>&1 | FileCheck %s --check-prefix=CHECK + +# CHECK: invalid name field Index: lld/test/ELF/propeller/propeller-bad-profile-3.s =================================================================== --- /dev/null +++ lld/test/ELF/propeller/propeller-bad-profile-3.s @@ -0,0 +1,7 @@ +# REQUIRES: x86 +## Test control flow graph is created. + +# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o +# RUN: not ld.lld -propeller=%S/Inputs/bad-propeller-3.data %t.o -o %t.out 2>&1 | FileCheck %s --check-prefix=CHECK + +# CHECK: invalid function index field Index: lld/test/ELF/propeller/propeller-bad-profile-4.s =================================================================== --- /dev/null +++ lld/test/ELF/propeller/propeller-bad-profile-4.s @@ -0,0 +1,7 @@ +# REQUIRES: x86 +## Test control flow graph is created. + +# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o +# RUN: not ld.lld -propeller=%S/Inputs/bad-propeller-4.data %t.o -o %t.out 2>&1 | FileCheck %s --check-prefix=CHECK + +# CHECK: function with index number '3' does not exist Index: lld/test/ELF/propeller/propeller-bad-profile-5.s =================================================================== --- /dev/null +++ lld/test/ELF/propeller/propeller-bad-profile-5.s @@ -0,0 +1,8 @@ +# REQUIRES: x86 +## Test control flow graph is created. + +# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o +# RUN: not ld.lld -propeller=%S/Inputs/bad-propeller-5.data %t.o -o %t.out 2>&1 | FileCheck %s --check-prefix=CHECK + +# CHECK: index '2' is not a function index, but a bb index + Index: lld/test/ELF/propeller/propeller-bbsections-dump.s =================================================================== --- /dev/null +++ lld/test/ELF/propeller/propeller-bbsections-dump.s @@ -0,0 +1,61 @@ +# REQUIRES: x86 +## Test control flow graph is created. + +# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o +# RUN: ld.lld -propeller=%S/Inputs/propeller.data -propeller-dump-cfg=main %t.o -o %t.out + +# RUN: cat %T/main.dot | FileCheck %s --check-prefix=CFG +# CFG: 0 [size="48"];3 [size="11"];1 [size="18"];2 [size="38"];4 [size="8"]; +# CFG: 0 -> 1 +# CFG: 3 -> 4 +# CFG: 3 -> 1 [label="273908" +# CFG: 1 -> 3 [label="165714" +# CFG: 1 -> 2 [label="106891" +# CFG: 2 -> 3 [label="110451" + +.text + .section .text.compute_flag,"ax",@progbits + .globl compute_flag + .type compute_flag,@function +compute_flag: + movslq %edi, %rcx + retq +.Lfunc_end0: + .size compute_flag, .Lfunc_end0-compute_flag + + .section .text.main,"ax",@progbits + .globl main + .type main,@function +main: + pushq %rbx + jmp a.BB.main # 0 -> 1 + + .section .text.main,"ax",@progbits,unique,1 +aaa.BB.main: + je aaaa.BB.main # 3 -> 4 + jmp a.BB.main # 3 -> 1 +.Ltmp0: + .size aaa.BB.main, .Ltmp0-aaa.BB.main + + .section .text.main,"ax",@progbits,unique,2 +a.BB.main: + je aaa.BB.main # 1 -> 3 + jmp aa.BB.main # 1 -> 2 +.Ltmp1: + .size a.BB.main, .Ltmp1-a.BB.main + + .section .text.main,"ax",@progbits,unique,3 +aa.BB.main: + jmp aaa.BB.main # 2 -> 3 +.Ltmp2: + .size aa.BB.main, .Ltmp2-aa.BB.main + + .section .text.main,"ax",@progbits,unique,4 +aaaa.BB.main: + retq +.Ltmp3: + .size aaaa.BB.main, .Ltmp3-aaaa.BB.main + + .section .text.main,"ax",@progbits +.Lfunc_end1: + .size main, .Lfunc_end1-main Index: lld/test/ELF/propeller/propeller-compressed-strtab-lto.s =================================================================== --- /dev/null +++ lld/test/ELF/propeller/propeller-compressed-strtab-lto.s @@ -0,0 +1,62 @@ +# REQUIRES: x86 +## Test control flow graph is created. + +# RUN: clang -c -flto=thin -fbasicblock-sections=all -O2 %S/Inputs/sample.c -o %t.o +# RUN: file %t.o | FileCheck %s --check-prefix=FILETYPE +# FILETYPE: LLVM IR bitcode + +# RUN: clang -fuse-ld=lld -fbasicblock-sections=all -Wl,-lto-basicblock-sections=all -Wl,-propeller=%S/Inputs/propeller.data -Wl,-propeller-keep-named-symbols -O2 %t.o -o %t.out + +## We shall have "a.BB.main", "aa.BB.main", "aaa.BB.main", "aaaa.BB.main" in the symbol table. +# RUN: llvm-nm %t.out | grep -cF ".BB.main" | FileCheck %s --check-prefix=SYM_COUNT +# SYM_COUNT: 4 +## But we only have "aaaa.BB.main" in .strtab, all others are compressed. +# RUN: llvm-readelf --string-dump=.strtab %t.out | grep -cF ".BB.main" | FileCheck %s --check-prefix=STRTAB_COUNT +# STRTAB_COUNT: 1 + +.text + .section .text.compute_flag,"ax",@progbits + .globl compute_flag + .type compute_flag,@function +compute_flag: + movslq %edi, %rcx + retq +.Lfunc_end0: + .size compute_flag, .Lfunc_end0-compute_flag + + .section .text.main,"ax",@progbits + .globl main + .type main,@function +main: + pushq %rbx + jmp a.BB.main # 0 -> 1 + + .section .text.main,"ax",@progbits,unique,1 +aaa.BB.main: + je aaaa.BB.main # 3 -> 4 + jmp a.BB.main # 3 -> 1 +.Ltmp0: + .size aaa.BB.main, .Ltmp0-aaa.BB.main + + .section .text.main,"ax",@progbits,unique,2 +a.BB.main: + je aaa.BB.main # 1 -> 3 + jmp aa.BB.main # 1 -> 2 +.Ltmp1: + .size a.BB.main, .Ltmp1-a.BB.main + + .section .text.main,"ax",@progbits,unique,3 +aa.BB.main: + jmp aaa.BB.main # 2 -> 3 +.Ltmp2: + .size aa.BB.main, .Ltmp2-aa.BB.main + + .section .text.main,"ax",@progbits,unique,4 +aaaa.BB.main: + retq +.Ltmp3: + .size aaaa.BB.main, .Ltmp3-aaaa.BB.main + + .section .text.main,"ax",@progbits +.Lfunc_end1: + .size main, .Lfunc_end1-main Index: lld/test/ELF/propeller/propeller-compressed-strtab.s =================================================================== --- /dev/null +++ lld/test/ELF/propeller/propeller-compressed-strtab.s @@ -0,0 +1,60 @@ +# REQUIRES: x86 +## Test "a.BB.main", "aa.BB.main", "aaa.BB.main" and "aaaa.BB.main" are saved +## in strtab in compressed form. + +# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o +# RUN: ld.lld -propeller=%S/Inputs/propeller.data %t.o -propeller-keep-named-symbols -o %t.out + +## We shall have "a.BB.main", "aa.BB.main", "aaa.BB.main", "aaaa.BB.main" in the symbol table. +# RUN: llvm-nm %t.out | grep -cF ".BB.main" | FileCheck %s --check-prefix=SYM_COUNT +# SYM_COUNT: 4 +## But we only have "aaaa.BB.main" in .strtab, all others are compressed. +# RUN: llvm-readobj --string-dump=.strtab %t.out | grep -cF ".BB.main" | FileCheck %s --check-prefix=STRTAB_COUNT +# STRTAB_COUNT: 1 + +.text + .section .text.compute_flag,"ax",@progbits + .globl compute_flag + .type compute_flag,@function +compute_flag: + movslq %edi, %rcx + retq +.Lfunc_end0: + .size compute_flag, .Lfunc_end0-compute_flag + + .section .text.main,"ax",@progbits + .globl main + .type main,@function +main: + pushq %rbx + jmp a.BB.main # 0 -> 1 + + .section .text.main,"ax",@progbits,unique,1 +aaa.BB.main: + je aaaa.BB.main # 3 -> 4 + jmp a.BB.main # 3 -> 1 +.Ltmp0: + .size aaa.BB.main, .Ltmp0-aaa.BB.main + + .section .text.main,"ax",@progbits,unique,2 +a.BB.main: + je aaa.BB.main # 1 -> 3 + jmp aa.BB.main # 1 -> 2 +.Ltmp1: + .size a.BB.main, .Ltmp1-a.BB.main + + .section .text.main,"ax",@progbits,unique,3 +aa.BB.main: + jmp aaa.BB.main # 2 -> 3 +.Ltmp2: + .size aa.BB.main, .Ltmp2-aa.BB.main + + .section .text.main,"ax",@progbits,unique,4 +aaaa.BB.main: + retq +.Ltmp3: + .size aaaa.BB.main, .Ltmp3-aaaa.BB.main + + .section .text.main,"ax",@progbits +.Lfunc_end1: + .size main, .Lfunc_end1-main Index: lld/test/ELF/propeller/propeller-error-on-bblabels.s =================================================================== --- /dev/null +++ lld/test/ELF/propeller/propeller-error-on-bblabels.s @@ -0,0 +1,60 @@ +# REQUIRES: x86 +## Test propeller fails if it tries to process an object that is built with "-fbasicblock-sections=labels". + +# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o +# RUN: ld.lld -propeller=%S/Inputs/propeller.data %t.o -o %t.out 2>&1 | FileCheck %s --check-prefix=CHECK + +# CHECK: warning: basicblock sections must not have same section index + + .text + .globl compute_flag + .p2align 4, 0x90 + .type compute_flag,@function +compute_flag: +# %bb.0: + movslq %edi, %rcx + retq +.Ltmp0: + .size .BB.compute_flag, .Ltmp0-.BB.compute_flag +.Lfunc_end0: + .size compute_flag, .Lfunc_end0-compute_flag + .globl main + .p2align 4, 0x90 + .type main,@function +main: +# %bb.0: + pushq %rbx + subq $16, %rsp + jmp a.BB.main +.Ltmp1: + .size .BB.main, .Ltmp1-.BB.main + .p2align 4, 0x90 +aaa.BB.main: + addl $1, %ebx + cmpl $2000000000, %ebx + je aaaa.BB.main +.Ltmp2: + .size aaa.BB.main, .Ltmp2-aaa.BB.main +a.BB.main: + movl %ebx, %edi + callq compute_flag + addl $1, count(%rip) + testl %eax, %eax + je aaa.BB.main +.Ltmp3: + .size a.BB.main, .Ltmp3-a.BB.main +aa.BB.main: + movsd (%rsp), %xmm0 + jmp aaa.BB.main +.Ltmp4: + .size aa.BB.main, .Ltmp4-aa.BB.main +aaaa.BB.main: + xorl %eax, %eax + popq %rbx + retq +.Ltmp5: + .size aaaa.BB.main, .Ltmp5-aaaa.BB.main +.Lfunc_end1: + .size main, .Lfunc_end1-main + .type count,@object + .comm count,4,4 Index: lld/test/ELF/propeller/propeller-keep-bb-symbols.s =================================================================== --- /dev/null +++ lld/test/ELF/propeller/propeller-keep-bb-symbols.s @@ -0,0 +1,117 @@ +# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o +# RUN: ld.lld -propeller=%S/Inputs/propeller-2.data -propeller-dump-symbol-order=%t2.symorder %t.o -o %t.out +# RUN: cat %t2.symorder | FileCheck %s --check-prefix=SYM_ORDER +# SYM_ORDER: Hot +# SYM_ORDER: aaaa.BB.main +# SYM_ORDER: aaaaaa.BB.main + +## Symbol "aaaaaa.BB.main" is removed because it is adjacent to aaaa.BB.main. +# RUN: { llvm-nm %t.out | grep -cF "aaaaaa.BB.main" 2>&1 || true ; } | FileCheck %s --check-prefix=SYM_COUNT +# SYM_COUNT: 0 + +## Symbol "aaaa.BB.main" is kept, because it starts a new cold code section for function "main". +# Run: llvm-nm -S %t.out | grep -cF "aaaa.BB.main" | FileCheck %s --check-prefix=SYM_COUNT1 +# SYM_COUNT1: 1 + + .text + .section .rodata.cst16,"aM",@progbits,16 + .p2align 4 +.LCPI0_0: + .quad 4640642756656496640 + .zero 8 + .section .text.this_is_very_cold,"ax",@progbits + .globl this_is_very_cold + .p2align 4, 0x90 + .type this_is_very_cold,@function +this_is_very_cold: +# %bb.0: + movabsq $4749492747822432256, %rax + retq +.Lfunc_end0: + .size this_is_very_cold, .Lfunc_end0-this_is_very_cold + .section .text.compute_flag,"ax",@progbits + + .globl compute_flag + .p2align 4, 0x90 + .type compute_flag,@function +compute_flag: +# %bb.0: + movslq %edi, %rcx + cmpl $4, %edx + cmovll %ecx, %eax + retq +.Lfunc_end1: + .size compute_flag, .Lfunc_end1-compute_flag + + .section .text.main,"ax",@progbits + .globl main + .p2align 4, 0x90 + .type main,@function +main: +# %bb.0: + pushq %rbx + subq $16, %rsp + movabsq $4742870812841738240, %rax # imm = 0x41D20FE01F000000 + jmp a.BB.main + .section .text.main,"ax",@progbits,unique,1 + .p2align 4, 0x90 + +aaaaa.BB.main: + addl $1, %ebx + cmpl $2000000000, %ebx + je aaaaaa.BB.main + jmp a.BB.main +.Ltmp0: + .size aaaaa.BB.main, .Ltmp0-aaaaa.BB.main + .section .text.main,"ax",@progbits,unique,2 +a.BB.main: + + movl %ebx, %edi + callq compute_flag + addl $1, count(%rip) + testl %eax, %eax + je aaa.BB.main + jmp aa.BB.main +.Ltmp1: + .size a.BB.main, .Ltmp1-a.BB.main + .section .text.main,"ax",@progbits,unique,3 +aa.BB.main: + + movsd (%rsp), %xmm0 + jmp aaa.BB.main +.Ltmp2: + .size aa.BB.main, .Ltmp2-aa.BB.main + .section .text.main,"ax",@progbits,unique,4 +aaa.BB.main: + + movslq count(%rip), %rax + cmpl $183, %eax + jne aaaaa.BB.main + jmp aaaa.BB.main +.Ltmp3: + .size aaa.BB.main, .Ltmp3-aaa.BB.main + .section .text.main,"ax",@progbits,unique,5 +aaaa.BB.main: + + xorps %xmm0, %xmm0 + cvtsi2sdl count(%rip), %xmm0 + callq this_is_very_cold + addsd (%rsp), %xmm0 + movsd %xmm0, (%rsp) + jmp aaaaa.BB.main +.Ltmp4: + .size aaaa.BB.main, .Ltmp4-aaaa.BB.main + .section .text.main,"ax",@progbits,unique,6 +aaaaaa.BB.main: + xorl %eax, %eax + addq $16, %rsp + popq %rbx + retq +.Ltmp5: + .size aaaaaa.BB.main, .Ltmp5-aaaaaa.BB.main + .section .text.main,"ax",@progbits +.Lfunc_end2: + .size main, .Lfunc_end2-main + + .type count,@object + .comm count,4,4 Index: lld/test/ELF/propeller/propeller-lto-bbsections-dump.s =================================================================== --- /dev/null +++ lld/test/ELF/propeller/propeller-lto-bbsections-dump.s @@ -0,0 +1,63 @@ +# REQUIRES: x86 +## Test control flow graph is created. + +# RUN: clang -c -flto=thin -fbasicblock-sections=all -O2 %S/Inputs/sample.c -o %t.o +# RUN: file %t.o | FileCheck %s --check-prefix=FILE_TYPE +# FILE_TYPE: LLVM IR bitcode +# RUN: clang -fuse-ld=lld -fbasicblock-sections=all -Wl,-lto-basicblock-sections=all -Wl,-propeller-dump-cfg=main -Wl,-propeller=%S/Inputs/propeller.data -O2 %t.o -o %t.out +# RUN: cat %T/main.dot | FileCheck %s --check-prefix=LTO_CFG + +# LTO_CFG: 0 [size="48"];3 [size="11"];1 [size="18"];2 [size="38"];4 [size="8"]; +# LTO_CFG: 0 -> 1 +# LTO_CFG: 3 -> 4 +# LTO_CFG: 3 -> 1 [label="273908" +# LTO_CFG: 1 -> 3 [label="165714" +# LTO_CFG: 1 -> 2 [label="106891" +# LTO_CFG: 2 -> 3 [label="110451" + +.text + .section .text.compute_flag,"ax",@progbits + .globl compute_flag + .type compute_flag,@function +compute_flag: + movslq %edi, %rcx + retq +.Lfunc_end0: + .size compute_flag, .Lfunc_end0-compute_flag + + .section .text.main,"ax",@progbits + .globl main + .type main,@function +main: + pushq %rbx + jmp a.BB.main # 0 -> 1 + + .section .text.main,"ax",@progbits,unique,1 +aaa.BB.main: + je aaaa.BB.main # 3 -> 4 + jmp a.BB.main # 3 -> 1 +.Ltmp0: + .size aaa.BB.main, .Ltmp0-aaa.BB.main + + .section .text.main,"ax",@progbits,unique,2 +a.BB.main: + je aaa.BB.main # 1 -> 3 + jmp aa.BB.main # 1 -> 2 +.Ltmp1: + .size a.BB.main, .Ltmp1-a.BB.main + + .section .text.main,"ax",@progbits,unique,3 +aa.BB.main: + jmp aaa.BB.main # 2 -> 3 +.Ltmp2: + .size aa.BB.main, .Ltmp2-aa.BB.main + + .section .text.main,"ax",@progbits,unique,4 +aaaa.BB.main: + retq +.Ltmp3: + .size aaaa.BB.main, .Ltmp3-aaaa.BB.main + + .section .text.main,"ax",@progbits +.Lfunc_end1: + .size main, .Lfunc_end1-main Index: lld/test/ELF/propeller/propeller-skip.s =================================================================== --- /dev/null +++ lld/test/ELF/propeller/propeller-skip.s @@ -0,0 +1,9 @@ +# REQUIRES: x86 +## Test lld honors "@" directive. The input propeller-3.data contains a +## "@" with an invalid output file name. ld.lld won't activate propeller +## because "-o" output name does not match what is following "@". + +# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o +# RUN: ld.lld -propeller=%S/Inputs/propeller-3.data %t.o -o %t.out 2>&1 | FileCheck %s --check-prefix=CHECK + +# CHECK: warning: [Propeller]: Propeller skipped Index: lld/test/ELF/propeller/propeller-symbol-order-dump.s =================================================================== --- /dev/null +++ lld/test/ELF/propeller/propeller-symbol-order-dump.s @@ -0,0 +1,62 @@ +# REQUIRES: x86 +## Test dump symbol order works good. + +# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o +# RUN: ld.lld -propeller=%S/Inputs/propeller.data -propeller-dump-symbol-order=%t2.symorder %t.o -o %t.out + +# RUN: cat %t2.symorder | FileCheck %s --check-prefix=SYMBOL_ORDER + +# SYMBOL_ORDER: main +# SYMBOL_ORDER: aa.BB.main +# SYMBOL_ORDER: aaa.BB.main +# SYMBOL_ORDER: a.BB.main +# SYMBOL_ORDER: compute_flag +# SYMBOL_ORDER: Hot +# SYMBOL_ORDER: aaaa.BB.main + +.text + .section .text.compute_flag,"ax",@progbits + .globl compute_flag + .type compute_flag,@function +compute_flag: + movslq %edi, %rcx + retq +.Lfunc_end0: + .size compute_flag, .Lfunc_end0-compute_flag + + .section .text.main,"ax",@progbits + .globl main + .type main,@function +main: + pushq %rbx + jmp a.BB.main # 0 -> 1 + + .section .text.main,"ax",@progbits,unique,1 +aaa.BB.main: + je aaaa.BB.main # 3 -> 4 + jmp a.BB.main # 3 -> 1 +.Ltmp0: + .size aaa.BB.main, .Ltmp0-aaa.BB.main + + .section .text.main,"ax",@progbits,unique,2 +a.BB.main: + je aaa.BB.main # 1 -> 3 + jmp aa.BB.main # 1 -> 2 +.Ltmp1: + .size a.BB.main, .Ltmp1-a.BB.main + + .section .text.main,"ax",@progbits,unique,3 +aa.BB.main: + jmp aaa.BB.main # 2 -> 3 +.Ltmp2: + .size aa.BB.main, .Ltmp2-aa.BB.main + + .section .text.main,"ax",@progbits,unique,4 +aaaa.BB.main: + retq +.Ltmp3: + .size aaaa.BB.main, .Ltmp3-aaaa.BB.main + + .section .text.main,"ax",@progbits +.Lfunc_end1: + .size main, .Lfunc_end1-main