Index: lld/ELF/Propeller.h =================================================================== --- /dev/null +++ lld/ELF/Propeller.h @@ -0,0 +1,277 @@ +//===- 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 +// +//===----------------------------------------------------------------------===// +// +// Propeller.h defines Propeller framework classes: +// +// Propfile - parses and wraps propeller profile +// +// Propeller - the main propeller framework class +// +//===----------------------------------------------------------------------===// + +#ifndef LLD_ELF_PROPELLER_H +#define LLD_ELF_PROPELLER_H + +#include "InputFiles.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 + +using llvm::StringRef; + +using std::list; +using std::map; +using std::mutex; +using std::pair; +using std::set; +using std::unique_ptr; +using std::vector; + +namespace lld { +namespace elf { +class SymbolTable; +} + +namespace propeller { + +class ELFCfg; +class ELFCfgEdge; +class ELFCfgNode; +class ELFView; +class Propeller; + +// Propeller profile parser. +// +// A sample propeller profile is like below: +// +// Symbols +// 1 0 N.init/_init +// 2 0 N.plt +// 3 0 N.plt.got +// 4 0 N.text +// 5 2b N_start +// 6 0 Nderegister_tm_clones +// 7 0 Nregister_tm_clones +// 8 0 N__do_global_dtors_aux +// 9 0 Nframe_dummy +// 10 2c Ncompute_flag +// 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 +// 14 12 227040 +// Fallthroughs +// 10 10 225131 +// 10 12 2255 +// 12 10 2283 +// 12 12 362886 +// 12 14 77103 +// 14 12 1376 +// 14 14 140856 +// !func1 +// !func2 +// !func3 +// +// 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 "14.2" means "main.bb.2", because "14" 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 17391 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(FILE *PS, Propeller &P) + : BPAllocator(), PropfileStrSaver(BPAllocator), PStream(PS), Prop(P), + SymbolOrdinalMap(), LineSize(1024) { + // LineBuf is to be used w/ getline, which requires the storage allocated by + // malloc. + LineBuf = (char *)malloc(LineSize); + } + ~Propfile() { + if (LineBuf) { + free(LineBuf); + } + BPAllocator.Reset(); + if (PStream) fclose(PStream); + } + + bool matchesOutputFileName(const StringRef &OutputFile); + bool readSymbols(); + SymbolEntry *findSymbol(StringRef SymName); + bool processProfile(); + + 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); + 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); + + return Sym; + } + + SymbolEntry *createBasicBlockSymbol(uint64_t Ordinal, SymbolEntry *Function, + StringRef &BBIndex, uint64_t Size) { + // 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); + 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; + } + + llvm::BumpPtrAllocator BPAllocator; + llvm::UniqueStringSaver PropfileStrSaver; + FILE *PStream; + Propeller &Prop; + 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... + map> SymbolNameMap; + list FunctionsWithAliases; + uint64_t LineNo; + char LineTag; + size_t LineSize; + char *LineBuf; +}; + +class Propeller { +public: + Propeller(lld::elf::SymbolTable *ST) + : Symtab(ST), Views(), CfgMap(), Propf(nullptr) {} + ~Propeller() { } + + bool checkPropellerTarget(); + bool processFiles(std::vector &Files); + void processFile(const pair &Pair); + ELFCfgNode *findCfgNode(uint64_t SymbolOrdinal); + void calculateNodeFreqs(); + vector genSymbolOrderingFile(); + void calculatePropellerLegacy(list &SymList, + list::iterator HotPlaceHolder, + list::iterator ColdPlaceHolder); + template + void forEachCfgRef(Visitor V) { + for (auto &P : CfgMap) { + V(*(*(P.second.begin()))); + } + } + + lld::elf::SymbolTable *Symtab; + + // ELFViewDeleter, which has its implementation in .cpp, saves us from having + // to have full ELFView definition visibile here. + struct ELFViewDeleter { + void operator()(ELFView *V); + }; + list> 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 + // ELFCfg here is an incomplete type. + struct ELFViewOrdinalComparator { + bool operator()(const ELFCfg *A, const ELFCfg *B) const; + }; + using CfgMapTy = map>; + CfgMapTy CfgMap; + unique_ptr Propf; + // Lock to access / modify global data structure. + mutex Lock; +}; + +// 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 { + set BBSymbolsToKeep; + + bool shouldKeepBBSymbol(StringRef SymName) { + if (!SymbolEntry::isBBSymbol(SymName)) return true; + return BBSymbolsToKeep.find(SymName) != BBSymbolsToKeep.end(); + } +}; + +extern PropellerLegacy PropLeg; + +} // namespace propeller +} // namespace lld +#endif Index: lld/ELF/Propeller.cpp =================================================================== --- /dev/null +++ lld/ELF/Propeller.cpp @@ -0,0 +1,621 @@ +//===- 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 "Config.h" +#include "PropellerBBReordering.h" +#include "PropellerELFCfg.h" +#include "PropellerFuncOrdering.h" +#include "InputFiles.h" + +#include "llvm/ADT/SmallString.h" +#include "llvm/Support/Parallel.h" +#include "llvm/Support/Path.h" +#include "llvm/Support/Format.h" +#include "llvm/Support/raw_ostream.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +using lld::elf::config; +using llvm::StringRef; + +using std::string; +using std::tuple; +using std::chrono::duration; +using std::chrono::system_clock; + +namespace lld { +namespace propeller { + +bool Propfile::matchesOutputFileName(const StringRef &OutputFileName) { + ssize_t R; + int OutputFileTagSeen = 0; + while ((R = getline(&LineBuf, &LineSize, PStream)) != -1) { + if (R == 0) continue; + if (LineBuf[R - 1] == '\n') { + LineBuf[--R] = '\0'; // Drop '\n' character at the end. + } + if (LineBuf[0] != '@') break; + ++OutputFileTagSeen; + if (StringRef(LineBuf + 1) == OutputFileName) + return true; + } + if (OutputFileTagSeen) + return false; + // If no @OutputFileName is specified, reset the stream and assume linker + // shall proceed propellering. + fseek(PStream, 0, SEEK_SET); + return true; +} + + +SymbolEntry *Propfile::findSymbol(StringRef SymName) { + std::pair SymNameSplit = SymName.split(".llvm."); + StringRef FuncName; + StringRef BBIndex; + string TmpStr; + if (!SymbolEntry::isBBSymbol(SymNameSplit.first, &FuncName, &BBIndex)) { + FuncName = SymNameSplit.first; + 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; +} + +// Refer header file for detailed information about symbols section. +bool Propfile::readSymbols() { + ssize_t R; + LineNo = 0; + LineTag = '\0'; + // A list of bbsymbols that + // appears before its wrapping function. This should be rather rare. + list> BBSymbols; + while ((R = getline(&LineBuf, &LineSize, PStream)) != -1) { + ++LineNo; + if (R == 0) + continue; + if (LineBuf[0] == '#' || LineBuf[0] == '!' || LineBuf[0] == '@') + continue; + if (LineBuf[0] == 'B' || LineBuf[0] == 'F') { + LineTag = LineBuf[0]; + break; // Done symbol section. + } + if (LineBuf[0] == 'S') { + LineTag = LineBuf[0]; + continue; + } + if (LineBuf[R - 1] == '\n') { + LineBuf[--R] = '\0'; // Drop '\n' character at the end. + } + StringRef L(LineBuf); // LineBuf is null-terminated. + + uint64_t SOrdinal; + uint64_t SSize; + auto L1S = L.split(' '); + auto L1 = L1S.first; + auto L2S = L1S.second.split(' '); + auto L2 = L2S.first; + auto EphemeralStr = L2S.second; + if (L1.getAsInteger(10, SOrdinal) /* means error happens */ || + SOrdinal == 0) { + error("[Propeller]: Invalid ordinal field, at propfile line: " + + std::to_string(LineNo) + "."); + return false; + } + if (L2.getAsInteger(16, SSize)) { + error("[Propeller]: Invalid size field, at propfile line: " + + std::to_string(LineNo) + "."); + return false; + } + if (EphemeralStr.empty()) { + error("[Propeller]: Invalid name field, at propfile line: " + + std::to_string(LineNo) + "."); + 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, '/'); + for(auto& SAlias: SAliases){ + SAlias = SAlias.split(".llvm.").first; + } + StringRef SName = SAliases[0]; + assert(SymbolOrdinalMap.find(SOrdinal) == SymbolOrdinalMap.end()); + createFunctionSymbol(SOrdinal, SName, std::move(SAliases), SSize); + } else { + // It's a bb symbol. + auto L = EphemeralStr.split('.'); + uint64_t FuncIndex; + if (L.first.getAsInteger(10, FuncIndex) || FuncIndex == 0) { + error("[Propeller]: Invalid function index field, at propfile line: " + + std::to_string(LineNo) + "."); + return false; + } + // Only save the index part, which is highly reusable. Note + // PropfileStrSaver is a UniqueStringSaver. + StringRef BBIndex = PropfileStrSaver.save(L.second); + auto ExistingI = SymbolOrdinalMap.find(FuncIndex); + if (ExistingI != SymbolOrdinalMap.end()) { + if (ExistingI->second->BBTag) { + error( + string("[Propeller]: Index '") + std::to_string(FuncIndex) + + "' is not a function index, but a bb index, at propfile line: " + + std::to_string(LineNo) + "."); + return false; + } + createBasicBlockSymbol(SOrdinal, ExistingI->second.get(), BBIndex, + SSize); + } else { + // A bb symbol appears earlier than its wrapping function, rare, but + // not impossible, rather play it safely. + BBSymbols.emplace_back(SOrdinal, FuncIndex, BBIndex, SSize); + } + } + } // End of iterating all symbols. + + for (tuple &S : BBSymbols) { + uint64_t SOrdinal; + uint64_t FuncIndex; + uint64_t SSize; + StringRef BBIndex; + std::tie(SOrdinal, FuncIndex, BBIndex, SSize) = S; + auto ExistingI = SymbolOrdinalMap.find(FuncIndex); + if (ExistingI == SymbolOrdinalMap.end()) { + error("[Propeller]: Function with index number '" + + std::to_string(FuncIndex) + "' does not exist, at propfile line: " + + std::to_string(LineNo) + "."); + return false; + } + createBasicBlockSymbol(SOrdinal, ExistingI->second.get(), BBIndex, SSize); + } + return true; +} + +// Helper method to parse a branch or fallthrough record like below +// 10 12 232590 R +static bool parseBranchOrFallthroughLine(StringRef L, uint64_t *From, + uint64_t *To, uint64_t *Cnt, char *T) { + 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 = L.split(' '); + *From = getInt(S0.first); + auto S1 = S0.second.split(' '); + *To = getInt(S1.first); + auto S2 = S1.second.split(' '); + *Cnt = getInt(S2.first); + if (!*From || !*To || !*Cnt) + return false; + if (!S2.second.empty()) { + if (S2.second == "C" || S2.second == "R") + *T = S2.second[0]; + else + return false; + } else { + *T = '\0'; + } + return true; +} + +bool Propfile::processProfile() { + ssize_t R; + uint64_t BCnt = 0; + uint64_t FCnt = 0; + while ((R = getline(&LineBuf, &LineSize, PStream)) != -1) { + ++LineNo; + if (R == 0) + continue; + if (LineBuf[0] == '#' || LineBuf[0] == '!') + continue; + if (LineBuf[0] == 'S' || LineBuf[0] == 'B' || LineBuf[0] == 'F') { + LineTag = LineBuf[0]; + continue; + } + if (LineTag != 'B' && LineTag != 'F') break; + if (LineBuf[R - 1] == '\n') { + LineBuf[--R] = '\0'; // drop '\n' character at the end; + } + StringRef L(LineBuf); // LineBuf is null-terminated. + uint64_t From, To, Cnt; + char Tag; + if (!parseBranchOrFallthroughLine(L, &From, &To, &Cnt, &Tag)) { + error(string("[Propeller]: Unrecognized propfile line: ") + + std::to_string(LineNo) + ":\n" + L.str()); + return false; + } + ELFCfgNode *FromN = Prop.findCfgNode(From); + ELFCfgNode *ToN = Prop.findCfgNode(To); + if (!FromN || !ToN) { + continue; + } + + if (LineTag == 'B') { + ++BCnt; + if (FromN->Cfg == ToN->Cfg) { + FromN->Cfg->mapBranch(FromN, ToN, Cnt, Tag == 'C', Tag == 'R'); + } else { + FromN->Cfg->mapCallOut(FromN, ToN, 0, Cnt, Tag == 'C', Tag == 'R'); + } + } else { + ++FCnt; + // LineTag == 'F' + if (FromN->Cfg == ToN->Cfg) + FromN->Cfg->markPath(FromN, ToN, Cnt); + } + } + + if (!BCnt) { + warn("[Propeller]: Zero branch info processed."); + } + if (!FCnt) { + warn("[Propeller]: Zero fallthrough info processed."); + } + return true; +} + +void Propeller::processFile(const pair &Pair) { + auto *Inf = Pair.first; + ELFView *View = ELFView::create(Inf->getName(), Pair.second, Inf->mb); + if (View) { + ELFCfgBuilder(*this, View).buildCfgs(); + { + // Updating global data structure. + std::lock_guard L(this->Lock); + this->Views.emplace_back(View); + for (auto &P : View->Cfgs) { + std::pair SplitName = P.first.split(".llvm."); + auto R = CfgMap[SplitName.first].emplace(P.second.get()); + (void)(R); + assert(R.second); + } + } + } +} + +ELFCfgNode *Propeller::findCfgNode(uint64_t SymbolOrdinal) { + assert(Propf->SymbolOrdinalMap.find(SymbolOrdinal) != + Propf->SymbolOrdinalMap.end()); + SymbolEntry *S = Propf->SymbolOrdinalMap[SymbolOrdinal].get(); + if (!S) { + // This is an internal error, should not happen. + error(string("[Propeller]: Invalid symbol ordinal: " + + std::to_string(SymbolOrdinal))); + return nullptr; + } + SymbolEntry *Func = S->BBTag ? S->ContainingFunc : S; + for (auto& FuncAliasName : Func->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 (!S->BBTag) { + for (auto *Cfg : CfgLI->second) + // Check Cfg does have name "SymName". + for (auto &N : Cfg->Nodes) + if (N->ShName.split(".llvm.").first == FuncAliasName) return N.get(); + } else { + uint32_t NumOnes; + // Compare the number of "a" in aaa...a.BB.funcname against integer + // NumOnes. + if (S->Name.getAsInteger(10, NumOnes) || !NumOnes) + warn("Internal error, BB name is invalid: '" + S->Name.str() + "'."); + else { + for (auto *Cfg : CfgLI->second) { + // Check Cfg does have name "SymName". + for (auto &N : Cfg->Nodes) { + auto T = N->ShName.find_first_of('.'); + if (T != string::npos && T == NumOnes) return N.get(); + } + } + } + } + } + return nullptr; +} + +void Propeller::calculateNodeFreqs() { + auto sumEdgeWeights = [](list &Edges) -> uint64_t { + return std::accumulate(Edges.begin(), Edges.end(), 0, + [](uint64_t PSum, const ELFCfgEdge *Edge) { + return PSum + Edge->Weight; + }); + }; + for (auto &P : CfgMap) { + auto &Cfg = *P.second.begin(); + if (Cfg->Nodes.empty()) + continue; + bool Hot = false; + Cfg->forEachNodeRef([&Hot, &sumEdgeWeights](ELFCfgNode &Node) { + uint64_t MaxCallOut = + Node.CallOuts.empty() ? + 0 : + (*std::max_element(Node.CallOuts.begin(), Node.CallOuts.end(), + [](const ELFCfgEdge *E1, const ELFCfgEdge *E2){ + return E1->Weight < E2->Weight; + }))->Weight; + Node.Freq = + std::max({sumEdgeWeights(Node.Outs), sumEdgeWeights(Node.Ins), + sumEdgeWeights(Node.CallIns), MaxCallOut}); + + Hot |= (Node.Freq != 0); + }); + if (Hot && Cfg->getEntryNode()->Freq == 0) + Cfg->getEntryNode()->Freq = 1; + } +} + +bool Propeller::checkPropellerTarget() { + if (config->propeller.empty()) return false; + string PropellerFileName = config->propeller.str(); + FILE *FPtr = fopen(PropellerFileName.c_str(), "r"); + if (!FPtr) { + error(string("[Propeller]: Failed to open '") + PropellerFileName + "'."); + return false; + } + // Propfile takes ownership of FPtr. + Propf.reset(new Propfile(FPtr, *this)); + + return Propf->matchesOutputFileName( + llvm::sys::path::filename(config->outputFile)); +} + +bool Propeller::processFiles(std::vector &Files) { + auto startReadSymbolTime = system_clock::now(); + if (!Propf->readSymbols()) { + error(string("[Propeller]: Invalid propfile: '") + config->propeller.str() + + "'."); + return false; + } + auto startCreateCfgTime = system_clock::now(); + + // Creating Cfgs. + vector> FileOrdinalPairs; + int Ordinal = 0; + for (auto &F : Files) { + FileOrdinalPairs.emplace_back(F, ++Ordinal); + } + llvm::parallel::for_each( + llvm::parallel::parallel_execution_policy(), FileOrdinalPairs.begin(), + FileOrdinalPairs.end(), + std::bind(&Propeller::processFile, this, std::placeholders::_1)); + + /* Drop alias cfgs. */ + for(SymbolEntry * F : Propf->FunctionsWithAliases){ + + ELFCfg * PrimaryCfg = nullptr; + CfgMapTy::iterator PrimaryCfgMapEntry; + + for(StringRef& AliasName : F->Aliases){ + auto L = CfgMap.find(AliasName); + if (L == CfgMap.end()) + continue; + + if (L->second.empty()) + continue; + + if (!PrimaryCfg || + PrimaryCfg->Nodes.size() < (*L->second.begin())->Nodes.size()) { + if (PrimaryCfg) + CfgMap.erase(PrimaryCfgMapEntry); + + PrimaryCfg = *L->second.begin(); + PrimaryCfgMapEntry = L; + } else { + CfgMap.erase(L); + } + } + } + + auto startProcessProfileTime = system_clock::now(); + + // Map profiles. + if (!Propf->processProfile()) { + return false; + } + + if (config->propellerPrintStats) { + duration ProcessProfileTime = + system_clock::now() - startProcessProfileTime; + duration ReadSymbolTime = startCreateCfgTime - startReadSymbolTime; + duration CreateCfgTime = + startProcessProfileTime - startCreateCfgTime; + llvm::outs() << llvm::format( + "[Propeller] Read all symbols in %f seconds.\n", + ReadSymbolTime.count()); + llvm::outs() << llvm::format( + "[Propeller] Created all cfgs in %f seconds.\n", CreateCfgTime.count()); + llvm::outs() << llvm::format( + "[Propeller] Proccesed the profile in %f seconds.\n", + ProcessProfileTime.count()); + } + + if (!config->propellerDumpCfgs.empty()) { + llvm::SmallString<128> CfgOutputDir(config->outputFile); + llvm::sys::path::remove_filename(CfgOutputDir); + for (auto &CfgNameToDump : config->propellerDumpCfgs) { + auto CfgLI = CfgMap.find(CfgNameToDump); + if (CfgLI == CfgMap.end()) { + warn("[Propeller] Could not dump cfg for function '" + CfgNameToDump + + "' : No such function name exists."); + continue; + } + int Index = 0; + for (auto *Cfg : CfgLI->second) { + if (Cfg->Name == CfgNameToDump) { + 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(CfgOutput.c_str())) { + warn("[Propeller] Failed to dump Cfg: '" + CfgNameToDump + "'."); + } + } + } + } + } + + // Releasing all support data (symbol ordinal / name map, saved string refs, + // etc) before moving to reordering. + Propf.reset(nullptr); + return true; +} + +vector Propeller::genSymbolOrderingFile() { + calculateNodeFreqs(); + + list CfgOrder; + if (config->propellerReorderFuncs) { + CCubeAlgorithm Algo; + Algo.init(*this); + auto startFuncOrderTime = system_clock::now(); + auto CfgsReordered = Algo.doOrder(CfgOrder); + if (config->propellerPrintStats){ + duration FuncOrderTime = system_clock::now() - startFuncOrderTime; + llvm::outs() << llvm::format( + "[Propeller] Reordered %u hot functions in %f seconds.\n", + CfgsReordered, FuncOrderTime.count()); + } + } else { + forEachCfgRef([&CfgOrder](ELFCfg &Cfg) { CfgOrder.push_back(&Cfg); }); + CfgOrder.sort([](const ELFCfg *A, const ELFCfg *B) { + const auto *AEntry = A->getEntryNode(); + const auto *BEntry = B->getEntryNode(); + return AEntry->MappedAddr < BEntry->MappedAddr; + }); + } + + list SymbolList(1, "Hot"); + const auto HotPlaceHolder = SymbolList.begin(); + const auto ColdPlaceHolder = SymbolList.end(); + unsigned ReorderedN = 0; + auto startBBOrderTime = system_clock::now(); + for (auto *Cfg : CfgOrder) { + if (Cfg->isHot() && config->propellerReorderBlocks) { + NodeChainBuilder(Cfg).doSplitOrder( + SymbolList, HotPlaceHolder, + config->propellerSplitFuncs ? ColdPlaceHolder : HotPlaceHolder); + ReorderedN++; + } else { + auto PlaceHolder = + config->propellerSplitFuncs ? ColdPlaceHolder : HotPlaceHolder; + Cfg->forEachNodeRef([&SymbolList, PlaceHolder](ELFCfgNode &N) { + SymbolList.insert(PlaceHolder, N.ShName); + }); + } + } + if (config->propellerPrintStats) { + duration BBOrderTime = system_clock::now() - startBBOrderTime; + llvm::outs() << llvm::format( + "[Propeller] Reordered basic blocks of %u functions in %f seconds.\n", + ReorderedN, BBOrderTime.count()); + } + + calculatePropellerLegacy(SymbolList, HotPlaceHolder, ColdPlaceHolder); + + if (!config->propellerDumpSymbolOrder.empty()) { + FILE *fp = fopen(config->propellerDumpSymbolOrder.str().c_str(), "w"); + if (!fp) { + warn(StringRef("[Propeller] Dump symbol order: failed to open ") + "'" + + config->propellerDumpSymbolOrder + "'"); + } else { + for (auto &N : SymbolList) { + fprintf(fp, "%s\n", N.str().c_str()); + } + fclose(fp); + llvm::outs() << "[Propeller] Dumped symbol order file to: '" + << config->propellerDumpSymbolOrder.str() << "'.\n"; + } + } + + SymbolList.erase(HotPlaceHolder); + + return vector( + std::move_iterator::iterator>(SymbolList.begin()), + std::move_iterator::iterator>(SymbolList.end())); +} + +void Propeller::calculatePropellerLegacy( + list &SymList, list::iterator HotPlaceHolder, + 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; +} + +void Propeller::ELFViewDeleter::operator()(ELFView *V) { + delete V; +} + +bool Propeller::ELFViewOrdinalComparator::operator()(const ELFCfg *A, + const ELFCfg *B) const { + return A->View->Ordinal < B->View->Ordinal; +} + +PropellerLegacy PropLeg; + +} // namespace propeller +} // namespace lld Index: lld/ELF/PropellerELFCfg.h =================================================================== --- /dev/null +++ lld/ELF/PropellerELFCfg.h @@ -0,0 +1,217 @@ +#ifndef LLD_ELF_PROPELLER_ELF_CFG_H +#define LLD_ELF_PROPELLER_ELF_CFG_H + +#include "Propeller.h" + +#include "llvm/ADT/StringRef.h" +#include "llvm/Object/ObjectFile.h" + +#include +#include +#include +#include +#include + +using llvm::MemoryBufferRef; +using llvm::object::ObjectFile; +using llvm::object::SymbolRef; +using llvm::object::section_iterator; +using llvm::StringRef; + +using std::list; +using std::map; +using std::ostream; +using std::pair; +using std::set; +using std::unique_ptr; + +namespace lld { +namespace propeller { + +class ELFView; +class ELFCfgNode; +class ELFCfg; + +class ELFCfgEdge { +public: + ELFCfgNode *Src; + ELFCfgNode *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 = 0, + INTRA_RSC, + INTRA_RSR, + // Intra edge dynamically created because of indirect jump, etc. + INTRA_DYNA, + INTER_FUNC_CALL, + INTER_FUNC_RETURN, + } Type {INTRA_FUNC}; + +protected: + ELFCfgEdge(ELFCfgNode *N1, ELFCfgNode *N2, EdgeType T) + :Src(N1), Sink(N2), Weight(0), Type(T) {} + + friend class ELFCfg; +}; + +class ELFCfgNode { + public: + uint64_t Shndx; + StringRef ShName; + uint64_t ShSize; + uint64_t MappedAddr; + uint64_t Freq; + ELFCfg *Cfg; + + list Outs; // Intra function edges. + list Ins; // Intra function edges. + list CallOuts; // Callouts/returns to other functions. + list CallIns; // Callins/returns from other functions. + + // Fallthrough edge, could be nullptr. And if not, FTEdge is in Outs. + ELFCfgEdge * FTEdge; + + const static uint64_t InvalidAddress = -1l; + + unsigned getBBIndex() { + StringRef FName, BName; + if (SymbolEntry::isBBSymbol(ShName, &FName, &BName)) + return BName.size(); + else + return 0; + } + +private: + ELFCfgNode(uint64_t _Shndx, const StringRef &_ShName, + uint64_t _Size, uint64_t _MappedAddr, ELFCfg *_Cfg) + : Shndx(_Shndx), ShName(_ShName), ShSize(_Size), + MappedAddr(_MappedAddr), Freq(0), Cfg(_Cfg), + Outs(), Ins(), CallOuts(), CallIns(), FTEdge(nullptr) {} + + friend class ELFCfg; + friend class ELFCfgBuilder; +}; + +class ELFCfg { +public: + ELFView *View; + StringRef Name; + uint64_t Size; + + // ELFCfg assumes the ownership for all Nodes / Edges. + list> Nodes; // Sorted by address. + list> IntraEdges; + list> InterEdges; + + ELFCfg(ELFView *V, const StringRef &N, uint64_t S) + : View(V), Name(N), Size(S) {} + ~ELFCfg() {} + + bool markPath(ELFCfgNode *From, ELFCfgNode *To, uint64_t Cnt = 1); + void mapBranch(ELFCfgNode *From, ELFCfgNode *To, uint64_t Cnt = 1, + bool isCall = false, bool isReturn = false); + void mapCallOut(ELFCfgNode *From, ELFCfgNode *To, uint64_t ToAddr, + uint64_t Cnt = 1, bool isCall = false, bool isReturn = false); + + ELFCfgNode *getEntryNode() const { + assert(!Nodes.empty()); + return Nodes.begin()->get(); + } + + bool isHot() const { + if (Nodes.empty()) + return false; + return (getEntryNode()->Freq != 0); + } + + template + void forEachNodeRef(Visitor V) { + for (auto &N: Nodes) { + V(*N); + } + } + + bool writeAsDotGraph(const char *CfgOutName); + +private: + // Create and take ownership. + ELFCfgEdge *createEdge(ELFCfgNode *From, + ELFCfgNode *To, + typename ELFCfgEdge::EdgeType Type); + + void emplaceEdge(ELFCfgEdge *Edge) { + if (Edge->Type < ELFCfgEdge::INTER_FUNC_CALL) { + IntraEdges.emplace_back(Edge); + } else { + InterEdges.emplace_back(Edge); + } + } + + friend class ELFCfgBuilder; +}; + + +class ELFCfgBuilder { +public: + Propeller *Prop; + ELFView *View; + + uint32_t BB{0}; + uint32_t BBWoutAddr{0}; + uint32_t InvalidCfgs{0}; + + ELFCfgBuilder(Propeller &P, ELFView *V) : Prop(&P), View(V) {} + void buildCfgs(); + +protected: + void buildCfg(ELFCfg &Cfg, const SymbolRef &CfgSym, + map> &NodeMap); + + void + calculateFallthroughEdges(ELFCfg &Cfg, + map> &NodeMap); + + // Build a map from section "Idx" -> Section that relocates this + // section. Only used during building phase. + void buildRelocationSectionMap( + map &RelocationSectionMap); + // Build a map from section "Idx" -> Node representing "Idx". Only + // used during building phase. + void buildShndxNodeMap(map> &NodeMap, + map &ShndxNodeMap); +}; + +// ELFView is a structure that corresponds to a single ELF file. +class ELFView { + public: + static ELFView *create(const StringRef &VN, + const uint32_t O, + const MemoryBufferRef &FR); + + ELFView(unique_ptr &VF, + const StringRef &VN, + const uint32_t VO, + const MemoryBufferRef &FR) : + ViewFile(std::move(VF)), ViewName(VN), Ordinal(VO), FileRef(FR), Cfgs() {} + ~ELFView() {} + + void EraseCfg(ELFCfg *&CfgPtr); + + unique_ptr ViewFile; + StringRef ViewName; + const uint32_t Ordinal; + MemoryBufferRef FileRef; + + // Name -> ELFCfg mapping. + map> Cfgs; +}; + +ostream & operator << (ostream &Out, const ELFCfgNode &Node); +ostream & operator << (ostream &Out, const ELFCfgEdge &Edge); +ostream & operator << (ostream &Out, const ELFCfg &Cfg); + +} +} // namespace lld +#endif Index: lld/ELF/PropellerELFCfg.cpp =================================================================== --- /dev/null +++ lld/ELF/PropellerELFCfg.cpp @@ -0,0 +1,494 @@ +#include "PropellerELFCfg.h" + +#include "Propeller.h" +#include "Symbols.h" +#include "SymbolTable.h" + +#include "llvm/Object/ObjectFile.h" +// Needed by ELFSectionRef & ELFSymbolRef. +#include "llvm/Object/ELFObjectFile.h" +#include "llvm/Support/raw_ostream.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +using llvm::object::ObjectFile; +using llvm::object::RelocationRef; +using llvm::object::SectionRef; +using llvm::object::section_iterator; +using llvm::object::SymbolRef; +using llvm::StringRef; + +using std::list; +using std::map; +using std::ostream; +using std::string; +using std::unique_ptr; + +namespace lld { +namespace propeller { + +bool ELFCfg::writeAsDotGraph(const char *CfgOutName) { + FILE *fp = fopen(CfgOutName, "w"); + if (!fp) { + warn("[Propeller]: Failed to open: '" + StringRef(CfgOutName) + "'\n"); + return false; + } + fprintf(fp, "digraph %s {\n", Name.str().c_str()); + forEachNodeRef([&fp](ELFCfgNode &N) { fprintf(fp, "%u [size=\"%lu\"];", N.getBBIndex(), N.ShSize); }); + fprintf(fp, "\n"); + for (auto &E : IntraEdges) { + bool IsFTEdge = (E->Src->FTEdge == E.get()); + fprintf(fp, " %u -> %u [label=\"%lu\", weight=%f];\n", E->Src->getBBIndex(), + E->Sink->getBBIndex(), E->Weight, IsFTEdge ? 1.0 : 0.1); + } + fprintf(fp, "}\n"); + fclose(fp); + llvm::outs() << "[Propeller]: Done dumping cfg '" << Name.str() << "' into '" + << CfgOutName << "'.\n"; + return true; +} + +ELFCfgEdge *ELFCfg::createEdge(ELFCfgNode *From, ELFCfgNode *To, + typename ELFCfgEdge::EdgeType Type) { + ELFCfgEdge *Edge = new ELFCfgEdge(From, To, Type); + if (Type < ELFCfgEdge::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); + } + emplaceEdge(Edge); // Take ownership of "Edge". + return Edge; +} + +bool ELFCfg::markPath(ELFCfgNode *From, ELFCfgNode *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); + ELFCfgNode *P = To; + do { + vector IntraInEdges; + std::copy_if(P->Ins.begin(), P->Ins.end(), + std::back_inserter(IntraInEdges), [this](ELFCfgEdge *E) { + return E->Type == ELFCfgEdge::EdgeType::INTRA_FUNC && + E->Sink != getEntryNode(); + }); + if (IntraInEdges.size() == 1) { + P = IntraInEdges.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); + ELFCfgNode *P = From; + do { + vector IntraOutEdges; + std::copy_if(P->Outs.begin(), P->Outs.end(), + std::back_inserter(IntraOutEdges), [this](ELFCfgEdge *E) { + return E->Type == ELFCfgEdge::EdgeType::INTRA_FUNC && + E->Sink != getEntryNode(); + }); + if (IntraOutEdges.size() == 1) { + P = IntraOutEdges.front()->Sink; + } else { + P = nullptr; + } + } while (P && P != From); + return true; + } + + assert(From->Cfg == To->Cfg); + if (From == To) + return true; + ELFCfgNode *P = From; + while (P && P != To) { + if (P->FTEdge) { + P->FTEdge->Weight += Cnt; + P = P->FTEdge->Sink; + } else { + P = nullptr; + } + } + if (!P) { + return false; + } + return true; +} + +void ELFCfg::mapBranch(ELFCfgNode *From, ELFCfgNode *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 == ELFCfgEdge::INTRA_FUNC || + E->Type == ELFCfgEdge::INTRA_DYNA; + } else { + if (isCall) + EdgeTypeOk = E->Type == ELFCfgEdge::INTRA_RSC; + if (isReturn) + EdgeTypeOk = E->Type == ELFCfgEdge::INTRA_RSR; + } + if (EdgeTypeOk && E->Sink == To) { + E->Weight += Cnt; + return; + } + } + + ELFCfgEdge::EdgeType Type = ELFCfgEdge::INTRA_DYNA; + if (isCall) + Type = ELFCfgEdge::INTRA_RSC; + else if (isReturn) + Type = ELFCfgEdge::INTRA_RSR; + + createEdge(From, To, Type)->Weight += Cnt; +} + +void ELFCfg::mapCallOut(ELFCfgNode *From, ELFCfgNode *To, uint64_t ToAddr, + uint64_t Cnt, bool isCall, bool isReturn) { + assert(From->Cfg == this); + assert(From->Cfg != To->Cfg); + ELFCfgEdge::EdgeType EdgeType = ELFCfgEdge::INTER_FUNC_RETURN; + if (isCall || + (ToAddr && To->Cfg->getEntryNode() == To && ToAddr == To->MappedAddr)) { + EdgeType = ELFCfgEdge::INTER_FUNC_CALL; + } + if (isReturn) { + EdgeType= ELFCfgEdge::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; +} + +void ELFCfgBuilder::buildCfgs() { + auto Symbols = View->ViewFile->symbols(); + map> Groups; + for (const SymbolRef &Sym : Symbols) { + auto R = Sym.getType(); + auto S = Sym.getName(); + if (R && S && *R == SymbolRef::ST_Function) { + StringRef SymName = *S; + /* + lld::elf::Symbol *PSym = + Plo ? Plo->Symtab->find(SymName) : Prop->Symtab->find(SymName); + if (PSym) (PSym->kind() == lld::elf::Symbol::UndefinedKind)){ + fprintf(stderr, "%s UNDEFINED KIND\n", SymName.str().c_str()); + continue; + } + */ + auto IE = Groups.emplace(std::piecewise_construct, + std::forward_as_tuple(SymName), + std::forward_as_tuple(1, Sym)); + (void)(IE.second); + assert(IE.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); + } + } + } + + for (auto &I : Groups) { + assert(I.second.size() >= 1); + map> TmpNodeMap; + SymbolRef CfgSym = *(I.second.begin()); + StringRef CfgName = I.first; + unique_ptr Cfg(new ELFCfg(View, CfgName, 0)); + for (SymbolRef Sym : I.second) { + auto SymNameE = Sym.getName(); + auto SectionIE = Sym.getSection(); + if (SymNameE && SectionIE && + (*SectionIE) != Sym.getObject()->section_end()) { + StringRef SymName = *SymNameE; + uint64_t SymShndx = (*SectionIE)->getIndex(); + // 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(); + // Drop bb sections with no code + if (!SymSize) + continue; + auto *SE = Prop->Propf->findSymbol(SymName); + if (SE) { + if (TmpNodeMap.find(SE->Ordinal) != TmpNodeMap.end()) { + error("Internal error checking Cfg map."); + return; + } + TmpNodeMap.emplace( + std::piecewise_construct, std::forward_as_tuple(SE->Ordinal), + std::forward_as_tuple(new ELFCfgNode(SymShndx, SymName, SE->Size, + SE->Ordinal, Cfg.get()))); + continue; + } + // Otherwise fallthrough to ditch Cfg & TmpNodeMap. + } + TmpNodeMap.clear(); + Cfg.reset(nullptr); + break; + } + + if (TmpNodeMap.empty()) + Cfg.reset(nullptr); + + if (!Cfg){ + continue; // to next Cfg group. + } + + uint32_t GroupShndx = 0; + for (auto &T : TmpNodeMap) { + if (GroupShndx != 0 && T.second->Shndx == GroupShndx) { + Cfg.reset(nullptr); + TmpNodeMap.clear(); + error("[Propeller]: Basicblock sections must not have same section " + "index, this is usually caused by -fbasicblock-sections=labels. " + "Use -fbasicblock-sections=list/all instead."); + return ; + } + GroupShndx = T.second->Shndx; + } + + if (Cfg) { + buildCfg(*Cfg, CfgSym, TmpNodeMap); + View->Cfgs.emplace(Cfg->Name, std::move(Cfg)); + } + } // Enf of processing all groups. +} + +void ELFCfgBuilder::buildRelocationSectionMap( + 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) { + section_iterator R = SecRef.getRelocatedSection(); + assert(R != J); + RelocationSectionMap.emplace(R->getIndex(), *I); + } + } +} + +void ELFCfgBuilder::buildShndxNodeMap( + map> &TmpNodeMap, + map &ShndxNodeMap) { + for (auto &NodeL : TmpNodeMap) { + auto &Node = NodeL.second; + auto InsertResult = ShndxNodeMap.emplace(Node->Shndx, Node.get()); + (void)(InsertResult); + assert(InsertResult.second); + } +} + +void ELFCfgBuilder::buildCfg( + ELFCfg &Cfg, const SymbolRef &CfgSym, + map> &TmpNodeMap) { + map ShndxNodeMap; + buildShndxNodeMap(TmpNodeMap, ShndxNodeMap); + + map RelocationSectionMap; + buildRelocationSectionMap(RelocationSectionMap); + + list RSCEdges; + for (auto &NPair : TmpNodeMap) { + ELFCfgNode *SrcNode = NPair.second.get(); + auto RelaSecRefI = RelocationSectionMap.find(SrcNode->Shndx); + if (RelaSecRefI == RelocationSectionMap.end()) + continue; + + 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; + uint64_t SymShndx((*SectionIE)->getIndex()); + ELFCfgNode *TargetNode{nullptr}; + auto Result = ShndxNodeMap.find(SymShndx); + if (Result != ShndxNodeMap.end()) { + TargetNode = Result->second; + if (TargetNode) { + ELFCfgEdge *E = Cfg.createEdge(SrcNode, TargetNode, + IsRSC ? ELFCfgEdge::INTRA_RSC + : ELFCfgEdge::INTRA_FUNC); + if (IsRSC) + RSCEdges.push_back(E); + } + } + } + } + + // Create 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 == ELFCfgEdge::INTRA_RSC)) { + // Now "N" is the exit node. + Cfg.createEdge(N.get(), REdge->Src, ELFCfgEdge::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(); + + // Set Cfg size and re-calculate size of the entry basicblock, which is + // initially the size of the whole function. + Cfg.Size = Cfg.getEntryNode()->ShSize; + Cfg.forEachNodeRef([&Cfg](ELFCfgNode &N) { + if (&N != Cfg.getEntryNode()) + Cfg.getEntryNode()->ShSize -= N.ShSize; + }); +} + +// Calculate fallthroughs. Edge P->Q is fallthrough if P & Q are +// adjacent, and there is a NORMAL edge from P->Q. +void ELFCfgBuilder::calculateFallthroughEdges( + ELFCfg &Cfg, map> &TmpNodeMap) { + /* + TmpNodeMap groups nodes according to their address: + addr1: [Node1] + addr2: [Node2] + addr3: [Node3] + addr4: [Node4] + And addr1 < addr2 < addr3 < addr4. + */ + auto SetupFallthrough = [&Cfg](ELFCfgNode *N1, ELFCfgNode *N2) { + for (auto *E : N1->Outs) { + if (E->Type == ELFCfgEdge::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, ELFCfgEdge::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()); + } +} + +ELFView *ELFView::create(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 ELFView(*R, VN, Ordinal, FR); + } + } + return nullptr; +} + +ostream &operator<<(ostream &Out, const ELFCfgNode &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; +} + +ostream &operator<<(ostream &Out, const ELFCfgEdge &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; +} + +ostream &operator<<(ostream &Out, const ELFCfg &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; +} + +} // namespace plo +} // namespace lld Index: lld/include/lld/Common/PropellerCommon.h =================================================================== --- /dev/null +++ lld/include/lld/Common/PropellerCommon.h @@ -0,0 +1,111 @@ +#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" + +using llvm::SmallVector; +using llvm::StringRef; + +#include + +using std::string; + +namespace lld { +namespace propeller { + +static const char BASIC_BLOCK_SEPARATOR[] = ".BB."; +static const char BASIC_BLOCK_UNIFIED_CHARACTER = 'a'; + +// This data structure is shared between lld propeller component and +// create_llvm_prof. +// The basic block symbols are encoded in this way: +// index.'bb'.function_name +struct SymbolEntry { + + using AliasesTy = SmallVector; + SymbolEntry(uint64_t O, const StringRef &N, AliasesTy &&As, uint64_t A, + uint64_t S, uint8_t T, bool BB = false, + SymbolEntry *FuncPtr = nullptr) + : Ordinal(O), Name(N), Aliases(As), Addr(A), Size(S), Type(T), + BBTag(BB), ContainingFunc(FuncPtr) {} + ~SymbolEntry() {} + + 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. + StringRef Name; + // Aliases[0] always equals to Name. + 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. + // For BBTag symbols, this is the containing fuction pointer, for + // a normal function symbol, this points to itself. + SymbolEntry *ContainingFunc; + + 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; + } + + bool isFunctionForBBName(StringRef BBName) { + 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; + } + + static std::string toCompactBBName(StringRef UnifiedBBName) { + StringRef FName, BName; + if (isBBSymbol(UnifiedBBName, &FName, &BName)) { + return FName.str() + BASIC_BLOCK_SEPARATOR + std::to_string(BName.size()); + } + return ""; + } + + 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 (*I != BASIC_BLOCK_UNIFIED_CHARACTER) return false; + if (FuncName) + *FuncName = R.second; + if (BBIndex) + *BBIndex = R.first; + return true; + } + + static const uint64_t INVALID_ADDRESS = uint64_t(-1); +}; + +} +} +#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,28 @@ +/* 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, at propfile line: 2 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, at propfile line: 2 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, at propfile line: 2 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: [Propeller]: 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,61 @@ +# 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: not ld.lld -propeller=%S/Inputs/propeller.data %t.o -o %t.out 1>%t2.out 2>&1 +# RUN: cat %t2.out | FileCheck %s --check-prefix=CHECK + +# CHECK: 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-opt-all-combinations.s =================================================================== --- /dev/null +++ lld/test/ELF/propeller/propeller-opt-all-combinations.s @@ -0,0 +1,295 @@ +# REQUIRES: x86 +## Basic propeller tests. +## This test exercises all combinations of propeller options (reorder-funcs, reorder-blocks, +## and split-funcs) on four functions. + +# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o +# RUN: ld.lld %t.o -o %t.out +# RUN: llvm-objdump -d %t.out| FileCheck %s --check-prefix=BEFORE + +# BEFORE: Disassembly of section .text: +# BEFORE-EMPTY: +# BEFORE-NEXT: foo: +# BEFORE-NEXT: xorb %al, 0 +# BEFORE-NEXT: int3 +# BEFORE-EMPTY: +# BEFORE-NEXT: bar: +# BEFORE-NEXT: xorb %al, 1 +# BEFORE-NEXT: je 9 +# BEFORE-EMPTY: +# BEFORE-NEXT: a.BB.bar: +# BEFORE-NEXT: xorb %al, 2 +# BEFORE-NEXT: jmp 7 +# BEFORE-EMPTY: +# BEFORE-NEXT: aa.BB.bar: +# BEFORE-NEXT: xorb %al, 3 +# BEFORE-EMPTY: +# BEFORE-NEXT: aaa.BB.bar: +# BEFORE-NEXT: xorb %al, 4 +# BEFORE-EMPTY: +# BEFORE-NEXT: baz: +# BEFORE-NEXT: xorb %al, 5 +# BEFORE-NEXT: int3 +# BEFORE-EMPTY: +# BEFORE-NEXT: qux: +# BEFORE-NEXT: xorb %al, 6 +# + +## Create a propeller profile for four functions foo, bar, baz, and qux based on the cfg below: +## +## +## bar +## / \ +## / \100 +## / \ +## 100 v v +## foo <----- a.BB.bar aa.BB.bar baz qux ---+ +## \ / ^ | +## \ /100 | 1 | +## \ / +-----+ +## v v +## aaa.BB.bar +## + +# RUN: echo "Symbols" > %t_prof.propeller +# RUN: echo "1 8 Nfoo" >> %t_prof.propeller +# RUN: echo "2 20 Nbar" >> %t_prof.propeller +# RUN: echo "3 9 2.1" >> %t_prof.propeller +# RUN: echo "4 7 2.2" >> %t_prof.propeller +# RUN: echo "5 7 2.3" >> %t_prof.propeller +# RUN: echo "6 8 Nbaz" >> %t_prof.propeller +# RUN: echo "7 7 Nqux" >> %t_prof.propeller +# RUN: echo "Branches" >> %t_prof.propeller +# RUN: echo "2 4 100" >> %t_prof.propeller +# RUN: echo "4 1 100 C" >> %t_prof.propeller +# RUN: echo "7 7 10 C" >> %t_prof.propeller +# RUN: echo "Fallthroughs" >> %t_prof.propeller +# RUN: echo "4 5 100" >> %t_prof.propeller + +# RUN: ld.lld %t.o -propeller=%t_prof.propeller --verbose -propeller-keep-named-symbols -o %t.propeller.reorder.out +# RUN: llvm-objdump -d %t.propeller.reorder.out| FileCheck %s --check-prefix=REORDER + +# REORDER: Disassembly of section .text: +# REORDER-EMPTY: +# REORDER-NEXT: bar: +# REORDER-NEXT: xorb %al, 1 +# REORDER-NEXT: jne 30 +# REORDER-EMPTY: +# REORDER-NEXT: aa.BB.bar: +# REORDER-NEXT: xorb %al, 3 +# REORDER-EMPTY: +# REORDER-NEXT: aaa.BB.bar: +# REORDER-NEXT: xorb %al, 4 +# REORDER-NEXT: int3 +# REORDER-EMPTY: +# REORDER-NEXT: foo: +# REORDER-NEXT: xorb %al, 0 +# REORDER-NEXT: int3 +# REORDER-EMPTY: +# REORDER-NEXT: qux: +# REORDER-NEXT: xorb %al, 6 +# REORDER-EMPTY: +# REORDER-NEXT: a.BB.bar: +# REORDER-NEXT: xorb %al, 2 +# REORDER-NEXT: jmp -32 +# REORDER-EMPTY: +# REORDER-NEXT: baz: +# REORDER-NEXT: xorb %al, 5 +# + +# RUN: ld.lld %t.o -propeller=%t_prof.propeller -propeller-opt=no-reorder-blocks -propeller-keep-named-symbols -o %t.propeller.noreorderblocks.out 2>&1 | FileCheck %s --check-prefixes=WARN,IMPLICITNOSPLIT +# WARN-NOT: warning: +# IMPLICITNOSPLIT: warning: propeller: no-reorder-blocks implicitly sets no-split-funcs. +# +# RUN: llvm-objdump -d %t.propeller.noreorderblocks.out| FileCheck %s --check-prefix=NO_REORDER_BB +# +# NO_REORDER_BB: Disassembly of section .text: +# NO_REORDER_BB-EMPTY: +# NO_REORDER_BB-NEXT: bar: +# NO_REORDER_BB-NEXT: xorb %al, 1 +# NO_REORDER_BB-NEXT: je 9 +# NO_REORDER_BB-EMPTY: +# NO_REORDER_BB-NEXT: a.BB.bar: +# NO_REORDER_BB-NEXT: xorb %al, 2 +# NO_REORDER_BB-NEXT: jmp 7 +# NO_REORDER_BB-EMPTY: +# NO_REORDER_BB-NEXT: aa.BB.bar: +# NO_REORDER_BB-NEXT: xorb %al, 3 +# NO_REORDER_BB-EMPTY: +# NO_REORDER_BB-NEXT: aaa.BB.bar: +# NO_REORDER_BB-NEXT: xorb %al, 4 +# NO_REORDER_BB-EMPTY: +# NO_REORDER_BB-NEXT: foo: +# NO_REORDER_BB-NEXT: xorb %al, 0 +# NO_REORDER_BB-NEXT: int3 +# NO_REORDER_BB-EMPTY: +# NO_REORDER_BB-NEXT: qux: +# NO_REORDER_BB-NEXT: xorb %al, 6 +# NO_REORDER_BB-NEXT: int3 +# NO_REORDER_BB-EMPTY: +# NO_REORDER_BB-NEXT: baz: +# NO_REORDER_BB-NEXT: xorb %al, 5 + +# RUN: ld.lld %t.o -propeller=%t_prof.propeller -propeller-opt=no-reorder-funcs -propeller-keep-named-symbols -o %t.propeller.noreorderfuncs.out +# RUN: llvm-objdump -d %t.propeller.noreorderfuncs.out| FileCheck %s --check-prefix=NO_REORDER_FUNC +# +# NO_REORDER_FUNC: Disassembly of section .text: +# NO_REORDER_FUNC-EMPTY: +# NO_REORDER_FUNC-NEXT: foo: +# NO_REORDER_FUNC-NEXT: xorb %al, 0 +# NO_REORDER_FUNC-NEXT: int3 +# NO_REORDER_FUNC-EMPTY: +# NO_REORDER_FUNC-NEXT: bar: +# NO_REORDER_FUNC-NEXT: xorb %al, 1 +# NO_REORDER_FUNC-NEXT: jne 22 +# NO_REORDER_FUNC-EMPTY: +# NO_REORDER_FUNC-NEXT: aa.BB.bar: +# NO_REORDER_FUNC-NEXT: xorb %al, 3 +# NO_REORDER_FUNC-EMPTY: +# NO_REORDER_FUNC-NEXT: aaa.BB.bar: +# NO_REORDER_FUNC-NEXT: xorb %al, 4 +# NO_REORDER_FUNC-NEXT: int3 +# NO_REORDER_FUNC-EMPTY: +# NO_REORDER_FUNC-NEXT: qux: +# NO_REORDER_FUNC-NEXT: xorb %al, 6 +# NO_REORDER_FUNC-EMPTY: +# NO_REORDER_FUNC-NEXT: a.BB.bar: +# NO_REORDER_FUNC-NEXT: xorb %al, 2 +# NO_REORDER_FUNC-NEXT: jmp -24 +# NO_REORDER_FUNC-EMPTY: +# NO_REORDER_FUNC-NEXT: baz: +# NO_REORDER_FUNC-NEXT: xorb %al, 5 +# + +# RUN: ld.lld %t.o -propeller=%t_prof.propeller -propeller-opt=no-split-funcs -propeller-keep-named-symbols -o %t.propeller.nosplitfuncs.out +# RUN: llvm-objdump -d %t.propeller.nosplitfuncs.out| FileCheck %s --check-prefix=NO_SPLIT_FUNC +# +# NO_SPLIT_FUNC: Disassembly of section .text: +# NO_SPLIT_FUNC-EMPTY: +# NO_SPLIT_FUNC-NEXT: bar: +# NO_SPLIT_FUNC-NEXT: xorb %al, 1 +# NO_SPLIT_FUNC-NEXT: jne 14 +# NO_SPLIT_FUNC-EMPTY: +# NO_SPLIT_FUNC-NEXT: aa.BB.bar: +# NO_SPLIT_FUNC-NEXT: xorb %al, 3 +# NO_SPLIT_FUNC-EMPTY: +# NO_SPLIT_FUNC-NEXT: aaa.BB.bar: +# NO_SPLIT_FUNC-NEXT: xorb %al, 4 +# NO_SPLIT_FUNC-EMPTY: +# NO_SPLIT_FUNC-NEXT: a.BB.bar: +# NO_SPLIT_FUNC-NEXT: xorb %al, 2 +# NO_SPLIT_FUNC-NEXT: jmp -16 +# NO_SPLIT_FUNC-EMPTY: +# NO_SPLIT_FUNC-NEXT: foo: +# NO_SPLIT_FUNC-NEXT: xorb %al, 0 +# NO_SPLIT_FUNC-NEXT: int3 +# NO_SPLIT_FUNC-EMPTY: +# NO_SPLIT_FUNC-NEXT: qux: +# NO_SPLIT_FUNC-NEXT: xorb %al, 6 +# NO_SPLIT_FUNC-NEXT: int3 +# NO_SPLIT_FUNC-EMPTY: +# NO_SPLIT_FUNC-NEXT: baz: +# NO_SPLIT_FUNC-NEXT: xorb %al, 5 +# + +## Check that the combination of no-reorder-blocks and split-funcs makes lld fail. +# RUN: not ld.lld %t.o -propeller=%t_prof.propeller -propeller-opt=no-reorder-blocks -propeller-opt=split-funcs 2>&1 -o /dev/null | FileCheck %s --check-prefix=FAIL +# FAIL: propeller: Inconsistent combination of propeller optimizations 'split-funcs' and 'no-reorder-blocks'. + + +# RUN: ld.lld %t.o -propeller=%t_prof.propeller -propeller-opt=no-split-funcs -propeller-opt=no-reorder-funcs -propeller-keep-named-symbols -o %t.propeller.nosplitreorderfuncs.out +# RUN: llvm-objdump -d %t.propeller.nosplitreorderfuncs.out| FileCheck %s --check-prefix=NO_SPLIT_REORDER_FUNC +# +# NO_SPLIT_REORDER_FUNC: Disassembly of section .text: +# NO_SPLIT_REORDER_FUNC-EMPTY: +# NO_SPLIT_REORDER_FUNC-NEXT: foo: +# NO_SPLIT_REORDER_FUNC-NEXT: xorb %al, 0 +# NO_SPLIT_REORDER_FUNC-NEXT: int3 +# NO_SPLIT_REORDER_FUNC-EMPTY: +# NO_SPLIT_REORDER_FUNC-NEXT: bar: +# NO_SPLIT_REORDER_FUNC-NEXT: xorb %al, 1 +# NO_SPLIT_REORDER_FUNC-NEXT: jne 14 +# NO_SPLIT_REORDER_FUNC-EMPTY: +# NO_SPLIT_REORDER_FUNC-NEXT: aa.BB.bar: +# NO_SPLIT_REORDER_FUNC-NEXT: xorb %al, 3 +# NO_SPLIT_REORDER_FUNC-EMPTY: +# NO_SPLIT_REORDER_FUNC-NEXT: aaa.BB.bar: +# NO_SPLIT_REORDER_FUNC-NEXT: xorb %al, 4 +# NO_SPLIT_REORDER_FUNC-EMPTY: +# NO_SPLIT_REORDER_FUNC-NEXT: a.BB.bar: +# NO_SPLIT_REORDER_FUNC-NEXT: xorb %al, 2 +# NO_SPLIT_REORDER_FUNC-NEXT: jmp -16 +# NO_SPLIT_REORDER_FUNC-EMPTY: +# NO_SPLIT_REORDER_FUNC-NEXT: baz: +# NO_SPLIT_REORDER_FUNC-NEXT: xorb %al, 5 +# NO_SPLIT_REORDER_FUNC-NEXT: int3 +# NO_SPLIT_REORDER_FUNC-EMPTY: +# NO_SPLIT_REORDER_FUNC-NEXT: qux: +# NO_SPLIT_REORDER_FUNC-NEXT: xorb %al, 6 + +.section .text,"ax",@progbits +# -- Begin function foo +.type foo,@function +.align 4 +foo: + xor %al,0 + +.Lfoo_end: + .size foo, .Lfoo_end-foo +# -- End function foo + +.section .text,"ax",@progbits,unique,1 +# -- Begin function bar +.type bar,@function +.align 4 +bar: + xor %al,1 + je aa.BB.bar + jmp a.BB.bar + +.section .text,"ax",@progbits,unique,2 +a.BB.bar: + xor %al,2 + jmp aaa.BB.bar +.La.BB.bar_end: + .size a.BB.bar, .La.BB.bar_end-a.BB.bar + +.section .text,"ax",@progbits,unique,3 +aa.BB.bar: + xor %al,3 + jmp aaa.BB.bar +.Laa.BB.bar_end: + .size aa.BB.bar, .Laa.BB.bar_end-aa.BB.bar + +.section .text,"ax",@progbits,unique,4 +aaa.BB.bar: + xor %al,4 +.Laaa.BB.bar_end: + .size aaa.BB.bar, .Laaa.BB.bar_end-aaa.BB.bar + +.section .text,"ax",@progbits,unique,1 +.Lbar_end: + .size bar, .Lbar_end-bar +# -- End function bar + +.section .text,"ax",@progbits,unique,5 +# -- Begin function baz +.type baz,@function +.align 4 +baz: + xor %al,5 + +.Lbaz_end: + .size baz, .Lbaz_end-baz +# -- End function baz + +.section .text,"ax",@progbits,unique,6 +# -- Begin function qux +.type qux,@function +.align 4 +qux: + xor %al,6 + +.Lqux_end: + .size qux, .Lqux_end-qux +# -- End function qux 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